Assignment : Fundamentals of Information Technology
Neatly write or type your answers to the following problems on a separate sheet of paper and submit a hard copy at the start of lecture on the due date. For any problems involving mathematical calculations you must show all work to receive full credit.
1. Suppose a computer using direct mapped cache has 232 bytes of byte-addressable main memory, and a cache of 1024 blocks, where each cache block contains 32 bytes.
a. How many blocks of main memory are there?
b. What is the format of a memory address as seen by the cache, i.e., what are the sizes of the tag, block, and offset ?elds?
c. To which cache block will the memory address 0x000063FA map?
2. Suppose a computer using fully associative cache has 224 bytes of byte-addressable main memory and a cache of 128 blocks, where each cache block contains 64 bytes.
a. How many blocks of main memory are there?
b. What is the format of a memory address as seen by the cache, i.e., what are the sizes of the tag and offset ?elds?
c. To which cache block will the memory address 0x01D872 map?
3. Consider a byte-addressable computer with 24-bit addresses, a cache capable of storing a total of 64K bytes of data and blocks of 32 bytes. Show the format of a 24-bit memory address for:
a. direct mapped cache
b. associative cache
4. Assume a direct-mapped cache that holds 4096 bytes, where each block is 16 bytes.
a. Assuming an address is 32 bits and that cache is initially empty, complete the table below. (Use hexadecimal numbers for all answers.)
|
Address
|
TAG
|
Cache location (block)
|
Offset within block
|
|
OxOFFOFABA
|
|
|
|
|
Ox00000011
|
|
|
|
|
OxOFFFFFFE
|
|
|
|
|
Ox23456719
|
|
|
|
|
OxCAFEBABE
|
|
|
|
b. [1 pt] Which, if any of the addresses will cause a collision (forcing the block that was just brought in to be overwritten) if they are accessed one right after the other?
5. Suppose you have a byte-addressable virtual address memory system with 8 virtual pages of 64 bytes each, and 4 page frames. Assuming the following page table, answer the questions below.
|
Frame #
|
Valid Bit
|
|
1
|
1
|
|
3
|
0
|
|
-
|
0
|
|
0
|
1
|
|
2
|
1
|
|
-
|
0
|
|
|
0
|
|
-
|
0
|
a. How many bits are in a virtual address?
b. How many bits are in a physical address?
c. What physical address corresponds to the following virtual addresses (if the address causes a page fault, simply indicate this is the case)? Give your answers in hexadecimal.
i. 0x00
ii. 0x44
iii. 0xC2
iv. 0x80
6. Suppose we have 210 bytes of virtual memory and 28 bytes of physical main memory. Suppose the page size is bytes.
a. How many pages are there in virtual memory?
b. How many page frames are there in main memory?
c. How many entries are in the page table for a process that uses all of virtual memory?
7. Consider a system with a main memory access time of 100ns supported by a cache having a 8ns access time and a hit rate of 98%. What is the effective access time (EAT) in nanoseconds if:
a. access to cache and main memory occur concurrently? Give your answer to two decimal places to the right of the decimal point.
b. access to cache and main memory occur sequentially? Give your answer to two decimal places to the right of the decimal point.
8. [4 pts] Suppose a main memory access takes 300 ns, the page fault rate is 1%, and it takes 20 ms to load a page from disk. What is the expected access time in nanoseconds assuming we ignore the in?uence of cache memory? Give your answer to two decimal places to the right of the decimal point.
9. Suppose a program makes a sequence of memory references that cause the following memory blocks to be read, in this order: A, B, D, E, A, C, E, A, C, B, E, A. The CPU's cache has 4 blocks and uses LRU as the replacement policy. Show the state of the cache after each memory block access, indicating the age of a block by giving the sequence number of when the block was last referenced. Begin the sequence numbers at 1 for the ?rst memory reference.
10. Suppose a program makes a sequence of memory references that cause the following memory blocks to be read, in this order: A, B, D, E, A, C, E, A, C, B, E, A. The CPU's cache has 4 blocks and uses FIFO as the replacement policy. Show the state of the cache after each memory block access. Assume the left-hand side of the queue is the head of the queue. Use an arrow to mark the oldest block in the queue.