代写program、Java，Python程序代写

日期：2023-05-25 08:45

Computer Architecture I Homework 8 2023

Homework 8

10 1. Put T (True) or F (False) for each of following statement. [10 points]

(1) ( ) One of the main advantages of using virtual memory is that it allows the OS to use

a single address space for all processes.

(2) ( ) The translation lookside buffer (TLB) generally holds the most-recently-used page

table entries that are used to translate memory page numbers to corresponding disk block

numbers where pages are stored on disk.

(3) ( ) The size of the virtual address space accessible to the program cannot be larger than

the size of the physical address space.

(4) ( ) In practice, most of virtual memory systems in modern OS employ direct-mapped

strategy to place memory pages for simplicity and low miss rate.

(5) ( ) Page tables make it possible to store the pages of a program non-contiguously and

add disk in the memory hierarchy

Email: Homework, Page 2 of 10 Computer Architecture I 2023

20 2. TLB Replacement [20 points]

A processor has 16-bit addresses, 256 byte pages, and an 8-entry fully associative TLB with

LRU replacement (the LRU field is 3 bits and encodes the order in which pages were accessed,

0 being the most recent). At some time instant, the TLB for the current process is the initial

state given in the Table 2. Assume that all current page table entries are in the initial TLB.

Assume also that all pages can be read from and written to.

Fill in the final state of the TLB in Table 3 according to the access pattern in Table 1. Free

physical pages: 0x17, 0x18, 0x19.

Table 1: Access Pattern for Memory

No. Access Pattern

1 Write 0x2333

2 Read 0x11F0

3 Write 0x2023

4 Write 0x1301

5 Read 0x20FF

6 Write 0x3415

Table 2: Initial TLB

VPN PPN Valid Dirty LRU

0x01 0x11 1 1 0

0x00 0x00 0 0 7

0x10 0x13 1 1 1

0x20 0x12 1 0 5

0x00 0x00 0 0 7

0x11 0x14 1 0 4

0xAC 0x15 1 1 2

0xFF 0x16 1 0 3

Table 3: Final TLB

VPN PPN Valid Dirty LRU

Email: Homework, Page 3 of 10 Computer Architecture I 2023

25 3. Page Table Walk [25 points]

Suppose there is a virtual memory system with 64KB page which has 2-level hierarchical

page table. The physical address of the base of the level 1 page table (0x01000) is stored in the

Page Table Base Register. The system uses 20-bit virtual address and 20-bit physical address.

Figure 1 summarizes the page table structure in this system.

Page Table

Base Register L1 Table

L2 Table

Data Pages

P1

L2 Table

P2

Data Pages

Data Pages

offset

Figure 1: Two-level Hierarchical Page Table

The size of both level 1 and level 2 page table entries is 4 bytes and the memory is byteaddressed. Assume that all pages and all page tables are loaded in the main memory. The

breakdown of a virtual address is:

19 18 17 16 15 0

L1 Index (p1) L2 Index (p2) Page Offset

Each entry of the level 1 page table contains the physical address of the base of each level

2 page tables, and each of the level 2 page table entries holds the PTE of the data page. As

described in Figure 1, L1 index and L2 index are used as an index to locate the corresponding

4-byte entry in Level 1 and Level 2 page tables.

A PTE in level 2 page tables can be broken into the following fields (Don’t worry about status

bits for the entire part).

31 20 19 16 15 0

0 Physical Page Number (PPN) Status Bits

Email: Homework, Page 4 of 10 Computer Architecture I 2023

10 (a) A [10 points]

Assuming the initial TLB and memory states are in Table 4 and Table 6, respectively,

what will be the final TLB states after accessing the virtual address given below? Please

fill out the table with the final TLB states in Table 5. You only need to write VPN and

PPN fields of the TLB. The TLB has 4 slots and is fully associative and if there are empty

lines they are taken first for new entries. Also, translate the virtual address (VA) to the

physical address (PA).

Table 4: Initial TLB State

VPN PPN

0x8 0x3

– –

– –

– –

Table 5: Final TLB State

VPN PPN

0x8 0x3

VA: 0xD180B −→ PA:

Table 6: Initial Memory State

Address (PA) Content

0x0104C 0x71A02

0x01048 0x30044

0x01044 0x20560

0x01040 0xA0FFF

0x0103C 0xCD031

0x01038 0xA6213

0x01034 0x91998

0x01030 0xDAB04

0x0102C 0xFA000

0x01028 0x60020

0x01024 0x51040

0x01020 0x4AA40

0x0101C 0x310EF

0x01018 0xBEA46

0x01014 0x2061B

0x01010 0x10040

0x0100C 0x01020

0x01008 0x01048

0x01004 0x01010

0x01000 0x01038

15 (b) B [15 points]

Li Hua wants to reduce the amount of physical memory required to store the page table,

so he decided to only put the level 1 page table in the physical memory and use the virtual

memory to store level 2 page tables. Now, each entry of the level 1 page table contains

the virtual address of the base of each level 2 page tables, and each of the level 2 page

table entries contains the PTE of the data page. Other system specifications remain the

same. (The size of both level 1 and level 2 page table entries is 4 bytes.)

Assuming the initial TLB and memory states are in Table 7 and Table 9, respectively,

what will be the final TLB states after accessing the virtual address given below? Please

fill out the table with the final TLB states in Table 8. You only need to write VPN and

PPN fields of the TLB. The TLB has 4 slots and it is fully associative and if there are

Email: Homework, Page 5 of 10 Computer Architecture I 2023

empty lines they are taken first for new entries. Also, translate the virtual address to the

physical address.

Table 7: Initial TLB State

VPN PPN

0x8 0x1

– –

– –

– –

Table 8: Final TLB State

VPN PPN

0x8 0x1

VA: 0x987DA −→ PA:

Table 9: Initial Memory State

Address (PA) Content

0x11048 0xA0044

0x11044 0xD0560

0x11040 0x10FFF

0x1103C 0xCD031

0x11038 0xA6213

0x11034 0x91998

0x11030 0xC2022

...... ......

0x10018 0xFA000

0x10014 0x60020

0x10010 0x11040

0x1000C 0x4AA40

0x10008 0x310EF

0x10004 0xBEA46

0x10000 0xD001B

...... ......

0x01010 0x10040

0x0100C 0x01020

0x01008 0x20008

0x01004 0x80010

0x01000 0x81038

Email: Homework, Page 6 of 10 Computer Architecture I 2023

25 4. Huge Page [25 points]

Small fixed-sized pages (e.g. 4 KB) reduce internal fragmentation and the page fault penalty

compared to large fixed-sized pages. However, when we run an application with a large working set, they may degrade a processor’s performance by incurring a number of TLB misses

because of their small TLB reach. Therefore, researchers have proposed to support variablesized pages to increase the TLB reach without losing the benefits of small fixed-sized pages.

For example, Linux supports 2MB and 1GB huge pages, besides 4KB data pages.

Li Hua wants to support 2MB huge in his processor. Assume that the system uses 43-bit

virtual addresses. 4KB pages are mapped using a three-level hierarchical page table. 2MB

pages are mapped using the first two levels of the same page table. An L2 Page Table Entry

(PTE) contains information which indicates if it points to an L3 table or a 2MB data page. All

PTEs are 8 Bytes. Figure 2 summarizes the page table structure and indicates the sizes of the

page tables and data pages.

Root Pointer L1 Table L2 Table L3 Table 4KB Page

2MB Page Figure 2: Page Table Structure for Variable-sized Pages

The processor has a data TLB with 64 entries, and each entry can map either a 4KB page or a

2MB page. After a TLB miss, a hardware engine walks the page table to reload the TLB. The

TLB uses a first-in/first-out (FIFO) replacement policy.

You also need to help Li Hua evaluate the memory usage and execution of the following

program which adds the elements from two 1MB arrays and stores the results in a third 1MB

array (note that, 1MB = 1,048,576 Bytes):

1 uint8_t A[1048576] = 0; // 1MB array

2 uint8_t B[1048576] = 0; // 1MB array

3 uint8_t C[1048576] = 0; // 1MB array

4 for (int j = 0; j < 1048576; j++) {

5 C[j] = A[j] + B[j];

6 }

Assume that the A, B, and C arrays are allocated in a contiguous 3MB region of physical

memory. We will consider two possible virtual memory mappings:

• 4KB: the arrays are mapped using 768 4KB pages (each array uses 256 pages).

Email: Homework, Page 7 of 10 Computer Architecture I 2023

• 2MB: the arrays are mapped using two 2MB pages.

For the following questions, assume that the above program is the only process in the system,

and ignore any instruction memory or operating system overheads. Assume that the arrays are

aligned in memory to minimize the number of page table entries needed. The system also is

trying to use the least number of page table entries needed.

5 (a) Virtual Address [5 points]

This is the breakdown of a virtual address which maps to a 4KB page:

42 32 31 21 20 12 11 0

L1 Index L2 Index L3 Index Page Offset

Show the corresponding breakdown of a virtual address which maps to a 2MB page.

Include the field names and bit ranges in your answer.

42 0

5 (b) Page Table Overhead [5 points]

We define page table overhead (PTO) as:

PTO =

physical memory that is allocated to page tables

physical memory that is allocated to data pages

For the given program, what is the PTO for each of the two mappings?

PTO4KB =

PTO2MB =

5 (c) Page Fragmentation Overhead [5 points]

We define page fragmentation overhead (PFO) as:

PFO =

physical memory that is allocated to data pages but is never accessed

physical memory that is allocated to data pages and is accessed

For the given program, what is the PTO for each of the two mappings?

PFO4KB =

PFO2MB =

Email: Homework, Page 8 of 10 Computer Architecture I 2023

10 (d) TLB [10 points]

Consider the execution of the given program, assuming that the data TLB is initially

empty. For each of the two mappings, how many TLB misses occur, and how many page

table memory references are required per miss to reload the TLB?

Mapping Data TLB misses Page table memory references (per miss)

4KB

2MB

Email: Homework, Page 9 of 10 Computer Architecture I 2023

20 5. Virtual Memory and TLB [20 points]

Li Hua creates a machine which is byte-addressed with 20-bit virtual addresses and 16-bit

physical addresses. The processor manual only specifies that the machine uses a 3-level page

table with the following virtual-address breakdown.

L1 Index L2 Index L3 Index Page Offset

4 bits 4 bits 4 bits 8 bits

6 (a) Physical Address [6 points]

What is the page size of Li Hua’s machine?

How many bits do physical page number (PPN) and page offset need in physical address,

respectively?

PPN: bits

Page offset: bits

14 (b) TLB [14 points]

Li Hua executes the following snippet of code on his new processor. Assume integers

are 4-bytes long, and the array elements are mapped to virtual addresses 0x6000 through

physical address 0x1FFC. Assume array and sum have been suitably initialized.

1 int List[4096] = 0;

2 while (1) {

3 for (j = 1; j < 5; j++) {

4 sum += List[j * 512]

5 }

6 }

The processor manual states this machine has a TLB with 16 entries. Assume that variables j and sum are stored in registers, and ignore address translation for instruction

fetches; only accesses to array require address translation.

In steady state, how many misses from the TLB and total memory accesses will Li Hua

observe per iteration of the while loop (lines 3, 4) on average, if (state your reasoning):

1. the TLB is direct-mapped

Misses from the TLB:

Total memory accesses:

Email: Homework, Page 10 of 10 Computer Architecture I 2023

2. the TLB is fully-associative (assume LRU replacement policy)

Misses from the TLB:

Total memory accesses: