Term
| Caches often have at least _____ levels. |
|
Definition
|
|
Term
| What can we do to use caches well? |
|
Definition
| cache-lines, pages, locality, capacity |
|
|
Term
| Memory is broken into 64 byte aligned, 64 byte chunks called _____-_____. When you access an address, the _____-_____ containing that address is brought as close to the processor as possible (into L1 cache). There is an incentive to place data that will be accessed together (with temporal locality) into the same 64 byte chunk, when possible. This is part of the reason that arrays are so much faster than linked lists. Multiple entries can fit into the same _____-_____, so fetching a single _____-_____ into L1 also fetches adjacent entries. |
|
Definition
|
|
Term
| Virtual address translations are done at the _____ granularity - at chunks of 4KB. Parsing through _____-_____ to translate a _____'s virtual address to a physical address is expensive - 2 (4) memory accesses on x86 (x86-64). To avoid this cost on every memory access, the _____ _____ _____ (_____) caches translations. |
|
Definition
| page, page-tables, page Translation Lookaside Buffer (TLB) |
|
|
Term
| TLB caches are virtually _____ and _____. This means that they must either be _____, or _____ when address spaces are _____. The implication of _____ the TLB is that _____ memory accesses will need to be translated through the page-tables. |
|
Definition
| tagged, indexed, tagged, flushed, switched, flushing, subsequent |
|
|
Term
| Inside a cache-line and inside a page are 2 forms of _____ _____. |
|
Definition
|
|
Term
| Caches have capacities that increase with increasing cache _____. The more data that gets accessed, the more _____ it puts on the caches. Any operations that require large amounts of data accesses _____ the previous contents of the cache. |
|
Definition
| levels, pressure, pressure |
|
|
Term
| Counting the number of cache-lines, and pages touched for key operations is a reasonable approximation of performance. Multiply those numbers by 3 to assess the best possible performance. For a reasonable approximation of performance, calculate _____ the number of cache-line accesses _____ _____ the number of TLB accesses where: _____=_____ for optimistic estimates of performance appropriate for workloads with very high temporal locality (based on _____ access times), _____=_____ for somewhat realistic estimates performance for kernel code (based on somewhere between _____ and _____ access times), _____=_____ for pessimistic estimates of performance (based on a combination of _____ and _____ _____ times) |
|
Definition
| Nx, plus, 2nx, N, 3, L1, N, 20, L2, L3, N, 100, L3, memory access |
|
|
Term
| Items in an array are stored sequentially (spatial locality), therefore there are fewer cache misses when iterating through an array as opposed to a linked list, whose items typically do not have spatial locality. Fewer cache misses mean _____ iteration time. |
|
Definition
|
|
Term
| If the addresses of every node in a linked list are prefetched, then the items in the linked list have temporal locality and iteration through the list will be _____ than if the addresses were not prefetched. |
|
Definition
|
|
Term
| Addresses with _____ locality are easily pulled into the cache the first time they are accessed, as well as subsequent times. When a group of addresses have _____ locality, that means it took a relatively long time for the addresses to be pulled into cache the first time, since they are not close together, but afterwards, while they still have _____ locality, the time to access the addresses are significantly shorter. |
|
Definition
| spatial, temporal, temporal |
|
|
Term
| Use arrays and tight loops in _____ for spatial locality. In _____, using primitive data types can help increase locality by decreasing the number of references to more complex objects. |
|
Definition
|
|
