CS-343 Assignment 7 Solutions

• Memory Hierarchy The division of the memory of a computer in to layers, with the smallest, fastest, and most expensive memory at the top, inside the CPU. Data located in one level is a subset of the data contained in the next lower layer.
• Address Space A range of memory locations. The address space of a program is the range of memory locations occupied by the program.
• Spatial Locality One of the factors that makes memory hierarchies efficient, spatial locality refers to the tendency of programs to access limited subsets of their address space at a time.
• Temporal Locality The tendency of a program to re-access a location or set of locations multiple times during a short time period.
• Cache The part of the memory hierarchy between main memory and the CPU. There may be several cache layers, with L1 being closest to the CPU, normally on the same integrated circuit. L2 is typically on the same chip as the CPU in current processors, and L3 is typically off-chip.
• Virtual Memory The part of a memory hierachy that relates main memory to disk.
• Physical Memory The main memory that is actually present in a computer system.
• Interleaved Memory A way of organizing main memory so that multiple sections of memory can be accessed simultaneously. An n-way interleaved memory allows n accesses to be initiated at the same time.
• Cache Hit A cache hit occurs when a CPU's memory access can be satisfied using data currently available in the cache.
• Hit Ratio The ratio of the number of cache hits to total number of memory accesses.
• Cache Miss A cache miss occurs when a CPU's memory access cannot be satisfied using data currently available in the cache.
• Miss Penalty The additional time it takes to satisfy a memory access because of a cache miss.
• Direct Mapped A cache design in which each block of main memory maps onto a single block of cache. Same as set associative (see below) with a set size of 1.
• Set Associative A cache design in which a block of main memory may be found in any of a set of cache blocks. Typical set sizes are 2 or 4.
• Fully Associative A cache design in which a block of main memory may be found in any block of cache. The same as set associative with a set size equal to the total number of cache blocks.
• Write Back A cache management technique in which write operations are made to the cache, but main memory is not updated until the cache block contents have to be replaced with another block of main memory.
• Write Through A cache management technique in which write operations are immediately passed through to main memory, insuring that main memory and the cache are coherent (contain the same information).
• Cache Block The memory in a cache that can hold one block of main memory. Cache block sizes for different processors may have values ranging from 8 to 64 bytes or words.
• Cache Line A cache block and its associated housekeeping data (tags, valid, and dirty bits).
• Tag Field The part of a memory address that identifies which block contains the address.
• Block Index Field The part of a memory address that tells which block or blocks of cache might contain the memory block. For a fully associative cache, this field is not used because a memory block can occupy any cache block.
• Offset Field The bits on the right end of a memory address that tell which byte or word within a memory block is being accessed.
• Page The unit of information transferred between the disk and main memory in a virtual memory system. Always a multiple of the disk's sector size, typica page sizes range from 512 to 4096 bytes.
• Split Cache A cache design that uses separate caches for instructions and data. Also called the Harvard Architecture.
• Unified Cache A cache that holds both instructions and data.
• Page Table A data struture maintained by the operating system kernel and referenced by the CPU to translate virtual page addresses to physical page addresses.
• Translation Lookaside Buffer A cache of the a subset of the page table kept inside the CPU and managed by the processor; without it each memory access by a program would require two accesses, one to the page table and the second one to complete the program's memory request.
• Valid Bit In both cache and virtual memory systems, a bit associated with each cache block or page table entry that tells whether the block or page contains actual data from the next lower level in the hierarchy.
• Replacement Algorithm The rule used by the cache hardware or by the kernel's virtual memory management software to determine which block or page is to be invalidated because a miss or fault requires loading information from the next layer down in the hierarchy and all candidate target positions are already occupied.
• LRU and referece bits Least Recently Used is an algorithm that chooses which block or page to replace by associating one or more reference bits with each one. Every time the block or page is accessed, the processor turns on the reference bit, and the victim is chosen from those blocks or pages with their reference bits off. If there are multiple bits, they act as a counter that is set to zero on each reference, and incremented by a clock; blocks or pages with the largest values in their counters are the least recently used ones.
• Dirty Bit A bit associated with each block or page that tells whether it has been modified since being loaded from the next lower level of the hierarchy. Used to determine whether the block or page has to be written back when it is replaced.
• Compulsory or cold-start miss A cache miss or page fault caused when a program starts running and blocks or pages haven't been loaded yet, misses that occur during the process of initially filling up the cache or physical memory. These misses or faults never involve writing anything back to the next lower leve in the hierarchy.
• Capacity miss Misses or faults that occur because the cache or physical memory is full and a new block or page has to be brought in, replacing a block or page that is currently loaded.
• Conflict or collision miss In a less than fully associative cache, a miss caused by all the blocks in the target set being occupied, even though other blocks in the cache might (or might not) be free.

7.1 The authors' answer:

The authors provide a blanket answer for 7.2 through 7.4:

7.5 Use write-back for data-intensive applications. There will probably be multiple writes to each block before it needs to be replaced, and delaying the memory update until they have all completed can reduce the bandwidth demands on the memory bus. But for the best reliability, use write-through so the data in memory is always valid, and can be re-read in case of a cache failure.

7.9 2: miss, 3: miss, 11: miss, 16: miss, 21: miss, 13: miss, 64: miss, 48: miss, 19: miss, 11: hit, 3: miss, 22: miss, 4: miss, 27: miss, 6: miss, 11: miss. Final contents are in boldface:

Cache Set	Addresses
0000	16, 64, 48
0001
0010	2
0011	3, 19, 3
0100	4
0101	21
0110	22, 6
0111
1000
1001
1010
1011	11, 11(hit), 27, 11
1100
1101	13
1110
1111

7.10 2: miss, 3: hit, 11: miss, 16: miss, 21: miss, 13: miss, 64: miss, 48: miss, 19: miss, 11: hit, 3: miss, 22: hit, 4: miss, 27: miss, 6: hit, 11: miss

Cache Set	Addresses
00	1, 3(h), 16, 64, 48, 19, 3
01	21, 22(h), 4, 6(h)
10	11, 11(h), 27, 11
11	13

7.12 Sixteen words per block is 2⁴ * 2⁵ = 2⁹ = 512 bits per block. Each tag field is 32 - (8+6) = 18 bits, and there is one valid bit, so there are 512 + 18 + 1 = 531 bits per block. There are 256 blocks, for a total of 135,936 bits of storage in the cache.

7.14 The miss penalty is the time to transfer one block from main memory to the cache. Assume that it takes 1 clock cycle to send the address to the main memory.

• Configuration (a) requires 16 main memory accesses to retrieve a cache block, and words of the block are transferred 1 at a time. Miss penalty = 1 + 16 × 10 + 16 × 1 = 177 clock cycles.
• Configuration (b) requires 4 main memory accesses to retrieve a cache block, and words of the block are transferred 4 at a time. Miss penalty = 1 + 4 × 10 + 4 × 1 = 45 clock cycles.
• Configuration (c) requires 4 main memory accesses to retrieve a cache block, and words of the block are transferred 1 at a time. Miss penalty = 1 + 4 × 10 + 16 × 1 = 57 clock cycles.