Deck 6: Memory

Question 1

Suppose a computer using direct mapped cache has
bytes of byte-addressable main memory and a cache of 32 blocks, where each cache block contains 16 bytes.
a) How many blocks of main memory are there
b) What is the format of a memory address as seen by the cache; that is, what are the sizes of the tag, block, and offset fields
c) To which cache block will the memory address 0x0DB63 map

Answer 1

a)
Main memory size
bytes
Cache size =
bytes
Cache block size=
bytes
As the memory is direct-mapped, hence the main memory block size is identical to the cache block size.
Hence, number of blocks is calculated as follows:
Hence, the number of blocks is 65536.
b)
The main memory address is split into sections called fields. Each field has its own significant meaning.
• The block field identifies a unique block in the cache.
• The offset field accesses the required address within the block.
• The remaining bits make up the tag field which uniquely identifies a block when it's copied to the cache.
As there are 1M bytes in main memory which is byte addressable, it requires log 2 (M)= 20 bits bits to make up the main memory address.
• As there are 32 blocks in the cache, 5 bits are needed to identify each one.
• As each block has 16 bytes and the memory is byte-addressable, 4 bits are needed for the offset field.
• The remaining bits i.e. 20-5-4= 11 bits would be used for the tag.
Hence, the main memory address would appear as follows:
c)
The type of cache is direct mapped. Hence, there is a designated block in the cache for every main memory block.
The cache consists of 32 blocks and each block of main memory maps to a particular block in the cache by means of modular arithmetic. Hence, blocks 0, 32, 64 etc. of main memory map to block 0 in the cache. Blocks 1, 33, 65 etc. of main memory map to block 1 in the cache.
The given main memory address is: (0DB63) 16
Converting to binary, the address is: (0000 1101 1011 0110 0011) 2
Now, since the 5 bits beginning from the 12 th till the 16 th identify the block, the number of the block in the cache is identified by the series: (10110) 2.
Hence, the block index in the cache is (22) 10

Question 2

Suppose a byte-addressable computer using set associative cache has
bytes of main memory and a cache of 32 blocks, and each cache block contains 8 bytes.
a) If this cache is 2-way set associative, what is the format of a memory address as seen by the cache; that is, what are the sizes of the tag, set, and offset fields
b) If this cache is 4-way set associative, what is the format of a memory address as seen by the cache

Answer 2

a) 2-way set associative:
As there are
bytes in main memory which is byte addressable, log 2 (
)= 16 bits are required to make up the main memory address.
• In case of a 2-way set associative cache, the 32 blocks would be bunched into 2 sets, so (32/2 =16) it results in 16. Thus, 4 bits (16 =2 4 ) are needed to identify a set.
• Each block has 8 bytes and the memory is byte-addressable. So, 3 (8= 2 3 ) bits are required for the offset field to identify the required data within a block.
• The number of bits used for tag can be identified by subtracting the number of bits used for set and offset from size of main memory.
o The remaining bits. 16-4-3=9 bits would be used for the tag.
Thus, the format of main memory address is as follows:
b) 4-way set associative:
As there are
bytes in main memory which is byte addressable, log 2 (
)= 16 bits are required to make up the main memory address.
• In case of a 4-way set associative cache, the 32 blocks would be bunched into 4 sets, So (32/4 =8) it results in 8 sets.Thus, 3 bits (8 =2 3 ) are needed to identify a set.
• Each block has 8 bytes and the memory is byte-addressable. So, 3 (8= 2 3 ) bits are required for the offset field to identify the required data within a block.
• The number of bits used for tag can be identified by subtracting the number of bits used for set and offset from size of main memory.
o The remaining bits. 16-3-3=10 bits would be used for the tag.
Thus, the format of main memory address is as follows:

Question 3

Redo exercise 16, assuming now that cache is 16-way set associative.

Reference of Exercise 16:
Assume a direct mapped cache that holds 4096 bytes, in which each block is 16 bytes. Assuming that an address is 32 bits and that cache is initially empty, complete the table that follows. (You should use hexadecimal numbers for all answers.) 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

Answer 3

NO ANSWER

Question 4

What are the advantages of a Harvard cache

Question 5

What is a TLB, and how does it improve EAT

Question 6

Which is faster, SRAM or DRAM

Question 7

Cache is accessed by its ________, whereas main memory is accessed by its _______.

Question 8

Why is the optimal cache replacement policy important

Question 9

a) If you are a computer builder trying to make your system as price-competitive as possible, what features and organization would you select for its memory hierarchy
b) If you are a computer buyer trying to get the best performance from a system, what features would you look for in its memory hierarchy

Question 10

What are the advantages and disadvantages of virtual memory

Question 11

Suppose a computer using direct mapped cache has
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; that is, what are the sizes of the tag, block, and offset fields
c) To which cache block will the memory address 0x000063FA map

Question 12

Suppose a byte-addressable computer using set associative cache has
bytes of main memory and a cache of 64 blocks, where each cache block contains 4 bytes.
a) If this cache is 2-way set associative, what is the format of a memory address as seen by the cache; that is, what are the sizes of the tag, set, and offset fields
b) If this cache is 4-way set associative, what is the format of a memory address as seen by the cache

Question 13

Suppose a process page table contains the entries shown below. Using the format shown in Figure 6.17a, indicate where the process pages are located in memory.

Question 14

Why would a system contain a victim cache A trace cache

Question 15

When would a system ever need to page its page table

Question 16

What are the advantages of using DRAM for main memory

Question 17

What are the three fields in a direct mapped cache address How are they used to access a word located in cache

Question 18

What is the worst-case cache behavior that can develop using LRU and FIFO cache replacement policies

Question 19

Consider a system that has multiple processors where each processor has its own cache, but main memory is shared among all processors.
a) Which cache write policy would you use
b) The Cache Coherency Problem. With regard to the system just described, what problems are caused if a processor has a copy of memory block A in its cache and a second processor, also having a copy of A in its cache, then updates main memory block A Can you think of a way (perhaps more than one) of preventing this situation, or lessening its effects

Question 20

What causes external fragmentation, and how can it be fixed

Question 21

Suppose a computer using direct mapped cache has
bytes of byte-addressable main memory and a cache size of 512 bytes, and 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 cache; that is, what are the sizes of the tag, block, and offset fields
c) To which cache block will the memory address 0x13A4498A map

Question 22

Suppose we have a computer that uses a memory address word size of 8 bits. This computer has a 16-byte cache with 4 bytes per block. The computer accesses a number of memory locations throughout the course of running a program.
Suppose this computer uses direct-mapped cache. The format of a memory address as seen by the cache is shown here:

The system accesses memory addresses in this exact order: 0x6E, 0xB9, 0x17, 0xE0, 0x4E, 0x4F, 0x50, 0x91, 0xA8, 0xA9, 0xAB, 0xAD, 0x93, and 0x94. The memory addresses of the first four accesses have been loaded into the cache blocks as shown below. (The contents of the tag are shown in binary, and the cache "contents" are simply the address stored at that cache location.)

a) What is the hit ratio for the entire memory reference sequence given above, assuming that we count the first four accesses as misses
b) What memory blocks will be in the cache after the last address has been accessed

Question 23

Suppose a process page table contains the entries shown below. Using the format shown in Figure 6.22a, indicate where the process pages are located in memory.

Question 24

Explain the differences among L1, L2, and L3 cache.

Question 25

Name three different applications where ROMs are often used.

Question 26

How does associative memory differ from regular memory Which is more expensive and why

Question 27

What, exactly, is effective access time (EAT)

Question 28

Pick a specific architecture (other than the one covered in this chapter). Do research to find out how your architecture approaches the concepts introduced in this chapter, as was done for Intel's Pentium.

Question 29

Suppose a computer using fully associative cache has
bytes of byte-addressable main memory and a cache of 64 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; that is, what are the sizes of the tag and offset fields
c) To which cache block will the memory address 0xF8C9 map

Question 30

Given a byte-addressable memory with 256 bytes, suppose a memory dump yields the results shown below. The address of each memory cell is determined by its row and column. For example, memory address 0x97 is in the 9th row, 7th column, and contains the hexadecimal value 43. Memory location 0xA3 contains the hexadecimal value 58.

The system from which this memory dump was produced contains 4 blocks of cache, where each block consists of 8 bytes. Assume that the following sequence of memory addresses takes place: 0x2C, 0x6D, 0x86, 0x29, 0xA5, 0x82, 0xA7, 0x68, 0x80, and 0x2B.
a) How many blocks of main memory are there
b) Assuming a direct mapped cache:
i. Show the format for a main memory address assuming that the system uses direct mapped cache. Specify field names and sizes.
ii. What does cache look like after the 10 memory accesses have taken place Draw the cache and show contents and tags.
iii. What is the hit rate for this cache on the given sequence of memory accesses
c) Assuming a fully associative cache:
i. Show the format for a main memory address. Specify field names and sizes.
ii. Assuming that all cache blocks are initially empty, blocks are loaded into the first available empty cache location, and cache uses a first-in, first-out replacement policy, what does cache look like after the 10 memory accesses have taken place
iii. What is the hit rate for this cache on the given sequences of memory accesses
d) Assuming a 2-way set associative cache:
i. Show the format for a main memory address. Specify field names and sizes.
ii. What does cache look like after the 10 memory accesses have taken place
iii. What is the hit ratio for this cache on the given sequence of memory accesses
iv. If a cache hit retrieves a value in 5ns, and retrieving a value from main memory requires 25ns, what is the average effective access time for this cache, assuming that all memory accesses exhibit the same hit rate as the sequence of 10 given, and assuming that the system uses a nonoverlapped (sequential) access strategy

Question 31

Suppose you have a byte-addressable virtual address memory system with eight virtual pages of 64 bytes each, and four page frames. Assuming the following page table, answer the questions below:

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.)
i. 0x0
ii. 0x44
iii. 0xC2
iv. 0x80

Question 32

Explain the differences between inclusive and exclusive cache.

Question 33

Explain the concept of a memory hierarchy. Why did your authors choose to represent it as a pyramid

Question 34

Explain how fully associative cache is different from direct mapped cache.

Question 35

Explain how to derive an effective access time formula.

Question 36

Name two ways that, as a programmer, you can improve cache performance.

Question 37

Suppose a computer using fully associative cache has
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; that is, what are the sizes of the tag and offset fields
c) To which cache block will the memory address 0x01D872 map

Question 38

A direct mapped cache consists of 8 blocks. Byte-addressable main memory contains 4K blocks of 8 bytes each. Access time for the cache is 22ns, and the time required to fill a cache slot from main memory is 300ns. (This time allows us to determine that the block is missing and bring it into cache.) Assume that a request is always started in parallel to both cache and to main memory (so if it is not found in cache, we do not have to add this cache search time to the memory access). If a block is missing from cache, the entire block is brought into the cache and the access is restarted. Initially, the cache is empty.
a) Show the main memory address format that allows us to map addresses from main memory to cache. Be sure to include the fields as well as their sizes.
b) Compute the hit ratio for a program that loops 4 times from addresses 0x0 to 0x43 in memory.
c) Compute the effective access time for this program.

Question 39

Suppose we have
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

Question 40

What is the advantage to a nonblocking cache

Question 41

Explain the concept of locality of reference, and state its importance to memory systems.

Question 42

Explain how set associative cache combines the ideas of direct and fully associative cache.

Question 43

When does caching behave badly

Question 44

Look up a specific vendor's specifications for memory, and report the memory access time, cache access time, and cache hit rate (and any other data the vendor provides).

Question 45

Suppose a computer using fully associative cache has
bytes of byte-addressable main memory and a cache of 128 blocks, where each 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 cache; that is, what are the sizes of the tag and offset fields
c) To which cache block will the memory address 0x01D872 map

Question 46

Consider a byte-addressable computer with 24-bit addresses, a cache capable of storing a total of 64KB of data, and blocks of 32 bytes. Show the format of a 24-bit memory address for:
a) direct mapped
b) associative
c) 4-way set associative

Question 47

You have a byte-addressable virtual memory system with a two-entry TLB, a 2-way set associative cache, and a page table for a process P. Assume cache blocks of 8 bytes and page size of 16 bytes. In the system below, main memory is divided into blocks, where each block is represented by a letter. Two blocks equal one frame.

Given the system state as depicted above, answer the following questions:
a) How many bits are in a virtual address for process P Explain.
b) How many bits are in a physical address Explain.
c) Show the address format for virtual address 0x12 (specify field name and size) that would be used by the system to translate to a physical address and then translate this virtual address into the corresponding physical address. (Hint: Convert the address to its binary equivalent and divide it into the appropriate fields.) Explain how these fields are used to translate to the corresponding physical address.
d) Given virtual address 0x06 converts to physical address 0x36. Show the format for a physical address (specify the field names and sizes) that is used to determine the cache location for this address. Explain how to use this format to determine where physical address 0x36 would be located in cache. (Hint: Convert 0x36 to binary and divide it into the appropriate fields.)
e) Given virtual address 0x19 is located on virtual page 1, offset 9. Indicate exactly how this address would be translated to its corresponding physical address an how the data would be accessed. Include in your explanation how the TLB, the page table, cache, and memory are used.

Question 48

What is the difference between a virtual memory address and a physical memory address Which is larger Why

Question 49

What are the three forms of locality

Question 50

Direct mapped cache is a special case of set associative cache where the set size is 1. So fully associative cache is a special case of set associative cache where the set size is ___.

Question 51

What is a dirty block

Question 52

What is the objective of paging

Question 53

Assume that a system's memory has 128M bytes. Blocks are 64 bytes in length, and the cache consists of 32K blocks. Show the format for a main memory address assuming a 2-way set associative cache mapping scheme and byte addressing. Be sure to include the fields as well as their sizes.

Question 54

Suppose a byte-addressable computer using 4-way set associative cache has 216 words of main memory (where each word is 32 bits) and a cache of 32 blocks, where each block is 4 words. Show the main memory address format for this machine. (Hint: Because this architecture is byte addressable, and the number of addresses is critical in determining the address format, you must convert everything to bytes.)

Question 55

Given a virtual memory system with a TLB, a cache, and a page table, assume the following:
• A TLB hit requires 5ns.
• A cache hit requires 12ns.
• A memory reference requires 25ns.
• A disk reference requires 200ms (this includes updating the page table, cache, and TLB).
• The TLB hit ratio is 90%.
• The cache hit rate is 98%.
• The page fault rate is.001%.
• On a TLB or cache miss, the time required for access includes a TLB and/or cache update, but the access is not restarted.
• On a page fault, the page is fetched from disk, and all updates are performed, but the access is restarted.
• All references are sequential (no overlap, nothing done in parallel).
For each of the following, indicate whether or not it is possible. If it is possible, specify the time required for accessing the requested data.
a) TLB hit, cache hit
b) TLB miss, page table hit, cache hit
c) TLB miss, page table hit, cache miss
d) TLB miss, page table miss, cache hit
e) TLB miss, page table miss
Write down the equation to calculate the effective access time.

Question 56

Discuss the pros and cons of paging.

Question 57

Give two noncomputer examples of the concept of cache.

Question 58

What are the three fields in a set associative cache address, and how are they used to access a location in cache

Question 59

Describe the advantages and disadvantages of the two cache write policies.

Question 60

What is a page fault

Question 61

A 2-way set associative cache consists of 4 sets. Main memory contains 2K blocks of 8 bytes each and byte addressing is used.
a) Show the main memory address format that allows us to map addresses from main memory to cache. Be sure to include the fields as well as their sizes.
b) Compute the hit ratio for a program that loops 3 times from addresses 0x8 to 0x33 in main memory. You may leave the hit ratio in terms of a fraction.

Question 62

Assume a direct mapped cache that holds 4096 bytes, in which each block is 16 bytes. Assuming that an address is 32 bits and that cache is initially empty, complete the table that follows. (You should use hexadecimal numbers for all answers.) 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

Question 63

Explain the difference between a unified cache and a Harvard cache.

Question 64

What causes internal fragmentation

Question 65

Which of L1 or L2 cache is faster Which is smaller Why is it smaller

Question 66

Explain the four cache replacement policies presented in this chapter.

Question 67

A system implements a paged virtual address space for each process using a one-level page table. The maximum size of virtual address space is 16MB. The page table for the running process includes the following valid entries (the notation indicates that a virtual page maps to the given page frame; that is, it is located in that frame):
Virtual page 2 Page frame 4 Virtual page 4 Page frame 9
Virtual page 1 Page frame 2 Virtual page 3 Page frame 16
Virtual page 0 Page frame 1
The page size is 1024 bytes and the maximum physical memory size of the machine is 2MB.
a) How many bits are required for each virtual address
b) How many bits are required for each physical address
c) What is the maximum number of entries in a page table
d) To which physical address will the virtual address 0x5F4 translate
e) Which virtual address will translate to physical address 0x400

Question 68

What are the components (fields) of a virtual address