Chapter 5

Question 1

Define

Block

Answer 1

Minimum unit of transfer between cache and main memory

Question 2

Define

Frame

Answer 2

To distinguish between the data transferred and the chunk of physical memory.

Question 3

Define

Line

Answer 3

A portion of cache memory capable of holding one block, so-called because it is usually drawn as a horizontal object

Question 4

Define

Tag

Answer 4

A portion of a cache line that is used for addressing purposes

Question 5

Define

Line size

Answer 5

The number of data bytes, or block size, contained in a line

Question 6

List

Elements of Cache design

Answer 6

Cache address (logical, physical)
Cache size
Mapping function (direct, fully associative, set associative)
Replacement algorithm
Write policy
Line size
Number of caches (single or two level, unified or split)

Question 7

Define

Virtual memory

Answer 7

Facility that allows programs to address memory from a virtual pov, without regard to the amount of main memory physically available. When used, the address fields of machine instructions contain virtual addresses. For reads and writes from main memory, a hardware memory management unit (MMU) translates each virtual address into a physical address in main memory

Question 8

Some thoughts about

Cache Size

Answer 8

Preferable to be small enough that overall avg cost per bit is close to that of main memory alone, but large enough that overall avg access time is close to that of cache alone

Speed decreases with size, more gates needed. Limited by amount of space on board and chip.

Optimal size depends on nature of workload

Question 9

Define

Direct mapped

cache access method

Answer 9

Organization: sequence of m lines
Mapping: each block of main memory maps to one unique line of cache
Access: Line portion of address used to access cache line; tag portion used to check for hit on that line.

Question 10

Define

Fully Associative

cache access methods

Answer 10

Organization: sequence of m lines
Mapping: each block of main memory can map to any line of cache
Access: tag portion of address used to check every line for hit on that line

Question 11

Define

Set Associative

Answer 11

Organization: sequence of m lines organized as v sets of k lines each
Mapping: each block of main memory maps to one unique cache set
Access: Line portion of address used to access cache set; tag portion used to check every line in that set for hit on that line.

Compromise with strengths of direct and fully associative.

Question 12

Define

Content-addressable memory

CAM

Answer 12

Also known as Associative storage

Is constructed of static RAM (SRAM) cells, but more expensive and less storage than regular SRAM

Designed such that when a bit string is supplied, the CAM searches its entire memory in parallel for a match. If found, returns address and sometimes data. Only takes one clock cycle

Question 13

Define need for

Replacement Algorithms

Answer 13

When new block is brought into cache, one of the existing blocks must be replaced. Direct, don’t get a choice. For high speed, algorithm must be implemented in hardware.

Question 14

List

Most common replacement algorithms

Answer 14

Least recently used (LRU)- most effective
FIFO
Least frequently used (LFU)

Question 15

Define

Two cases to consider with write policy

Answer 15

If the block has not been altered then it may be overwritten with a new block without first writing out the old block.

If at least one write operation has been performed on a word in that line, main memory must be updatedby writing line of cache to block of memory before bringing new block

Question 16

Define

Write through

Answer 16

Simplest technique, all write operations made to main memory as well as to cache.

Main disadvantage, generates substantial memory traffic and may create a bottleneck

Question 17

Define

Write Back

Answer 17

Minimizes memory writes, updates made only in cache. Portions of main memory are invalid, hence accesses by I/O modules only allowed through cache. Complex circuitry and potential bottleneck

Question 18

Define

Write miss alternatives

Answer 18

Write allocate: the block containing the word to be written is fetched from main memory (or next level cache) into cache and processor proceeds with the write cycle. Most common with write back

No write allocate: the block containing the word to be written is modified in mm and not loaded into the cache. Most common with write through

Question 19

List

Cache coherency approaches

Answer 19

Bus watching write-thru
Hardware transparency
Noncacheable memory

Question 20

Define

Bus watching write through

Answer 20

Each cache controller monitors the address lines to detect write operations to memory by other bus masters. If another master writes to a location in shared memory that also resides in cache memory, cache controller invalidates cache entry.

Depends on write through by all cache controllers

Question 21

Define

Hardware transparency

Answer 21

Additional hardware is used to ensure that all updates to mm via cache are reflected in all caches. Modifications written to mm

Question 22

Define

Noncacheable memory

Answer 22

Only a portion is shared by more than one processor, and this is designated as noncacheable. All accesses to shared memory are cache misses because never copied to cache. Noncacheable memory can be identified using chip select logic or high-address bits

Question 23

Read about line size

Answer 23

Did you do it?? Does hit ratio make enough sense to even study now???!!!!

Question 24

Define

Multilevel caches

Answer 24

As logic density has increased, it has become possible to have a cache on the same chip as the processor. The on-chip cache reduces the processor’s external bus activity and speeds up execution time and increases overall system performance. With two level cache, internal cache designated L1, external L2

Question 25

Define

What determines the impact of a multilevel cache?

Answer 25

Depends on the hit rates in both the L1 and L2 caches

Question 26

Define

Split cache

Answer 26

One dedicated to instructions, the other dedicated to data. Both exist at the same level, typically as two L1 caches

Question 27

Define

Advantages of split cache

Answer 27

Eliminates cache contention between instructions fetch/decode unit and execution unit (important in pipelining

Trend is towards split caches on L1, unified for higher levels

Question 28

Define

Advantages of unified cache

Answer 28

Higher hit rate: balances load of instructions and data fetches automatically. Only one cache needs to be designed and implemented

Trend is towards split caches on L1, unified for higher levels

Question 29

Define

Inclusion policy

Answer 29

Dictates that a piece of data in one cache is guaranteed to also be found in all lower levels of that cache.
Advantage is that it simplifies searching for data when there are multiple processors in the computing system.
This property is useful in enforcing cache coherency

Question 30

Define

Exclusive policy

Answer 30

Dictates that a piece of data in one cache is guaranteed not to be found in all lower levels of caches.
The advantage is it does not waste cache capacity since it does not store multiple copies of the same data in all caches.
Disadvantage is the need to search multiple levels of when invalidating or updating a block

To minimize search time, the highest-level tag sets are typically duplicated at the lowest cache level to centralize searching

Question 31

Define

Cache timing model: Direct mapped cache access

Answer 31

The 1st operation is checking the tag field of an address against the tag value in the line designated by the line field.
If there is not a match (miss), the operation is complete.
If there is a match (hit), the cache hardware reads the data block from the line in the cache and fetches the byte or word indicated by the offset field of the address.
Allows for simple and fast speculation

Question 32

Define

Non inclusive policy

Answer 32

A piece of data in one cache may or may not be found in lower levels of caches.
As with exclusive, the highest-level tag sets are typically duplicated at the lowest cache level to centralize searching

Question 33

Define

Cache timing model: Fully associative cache

Answer 33

The line number is not known until the tag comparison is completed.
The hit time is the same as for direct mapped.
Because this is a content-addressable memory, the miss time is simply the tag comparison time.

Question 34

Define

Cache timing model: Set associative

Answer 34

It is not possible to transmit bytes and compare tags in parallel as can be done with direct mapped with speculative access.
However, the circuitry can be designed so that the data block from each line in a set can be loaded then transmitted once the tag check is made.

Question 35

Define

Hit Ratio

from cloudflare

Answer 35

A measurement of how many content requests a cache is able to fulfill successfully, compared to how many requests it receives.