Exam #3 Review Part 2

Question 1

Memory Hierarchy

Answer 1

A structure that uses multiple levels of memories; as the distance from the processor increases, the size of the memories and the access time both increase.

Question 2

Compare/Constrast SRAM and DRAM

Answer 2

SRAM(Static Random Access Memory): Also memory built as an integrated circuit, but faster and less dense than DRAM.

• Fast
• Expensive
• Small
• uses flip-flops, like a register file
• non-destructive read-out
• fast (down to 0.5 ns access time for small memories)

DRAM(Dynamic Random Access Memory): Memory built as an integrated circuit; it provides random access to any location.

• Slow
• Large
• Cheap
• uses a single transistor to store each bit
• simpler structure makes memory cheaper (now < 5 cents/MB)
• and allows for larger capacity chips (now typically 1 - 2 Gb on a chip)
• destructive read-out
• requires regular refresh
• slower (access time for random word (latency) as high as 50 ns)

Question 3

Principle of Locality

Answer 3

Temporal Locality(Locality in Time)

• The locality principle stating that if a data location is referenced then it will tend to be referenced again soon.
• if an item is referenced, it will tend to be referenced again soon. If you recently brought a book to your desk to look at, you will probably need to look at it again soon.
• If a program referenced a location, more likely to reference this location again in the near future that it is to reference another random location.

Spatial Locality(Locality in Space)

• The locality principle stating that if a data location is referenced, data locations with nearby addresses will tend to be referenced soon.
• If program referenced a location, more likely to reference nearby locations in the near future than it is to reference other random locations

Question 4

3C of cache misses: Compulsory, Capacity, Conflict

Answer 4

Compulsory
-Also called cold-start miss.
-A cache miss caused by the first access to a block that has never been in the cache.
-cold start
–don’t have a choice
–except that by increasing block size, can reduce the number of distinct blocks that are requested

Capacity

• A cache miss that occurs because the cache, even with full associativity, cannot contain all the blocks needed to satisfy the request.
• Cache is much smaller than total addressable memory

Conflict
-Also called collision miss.
-A cache miss that occurs in a set-associative or direct-mapped cache when multiple blocks compete for the same set and that are eliminated in a fully associative cache of the same size.
-collision within a set
–requested block was thrown out when some other block wanted to occupy the same position
–can reduce by increasing assiciativity
(each block has more options)

Question 5

Virtual Memory: How is it implemented?

Answer 5

• A technique that uses main memory as a “cache” for secondary storage.
• Implemented: Need to Know

Question 6

Virtual Memory: What is a Page, Page Fault

Answer 6

Page

Page Fault
-An event that occurs when an accessed page is not presented in main memory

Question 7

Cache Schemes: Direct Mapped, Set-Associative, Fully Associative

Answer 7

Direct Mapped

• A cache structure in which each memory location is mapped to exactly one location in the cache.
• if cache has N words, location k of memory goes into word (k mod N) of cache
• simplest cache design
• conflict between memory locations with same (k mod N) reduces performance, as compared to fully associative cache

Set-Associative

• A cache that has a fixed number of locations (at least two) where each block can be placed.
• typical designs are 2-way or 4-way set associative
• somewhat greater complexity than direct mapped (more comparators and multiplexers)
• for 2-way, organize cache as S=N/2 sets of 2 words each
• location k of memory goes into set (k mod S) of cache
• approaches performance of fully associative

Fully Associative

• A cache structure in which a block can be placed in any location in the cache.
• Any word of memory can be stored into any word in the cache.
• Not practical except for very small caches
• If cache is full, evict least recently used entry in cache

Question 8

Write-Back v. Write-Through for cache, virtual memory

Answer 8

Write-Back

• A scheme that handles writes by updating values only to the block in the cache, then writing the modified block to the lower level of the hierarchy when the block is replaced.
• writes only update the block in the cache; when the block is replaced in the cache, the modified words are written back to main memory. This is more complex but reduces the main memory traffic, since a program may modify a memory word several times while it is in the cache.

Write-Through

• A scheme in which writes always update both the cache and the next lower level of the memory hierarchy, ensuring that data is always consistent between the two.
• writes always update both cache and memory. So that processor does not have to wait for memory write to finish, we include a write buffer (which holds information on store instructions which have not yet been written to main memory)

Question 9

?Cache Coherence

Answer 9

Defines what values can be returned by a read.

Question 10

Cache Design by Level: L1, L2 Hit Time, Miss Rate

Answer 10

L1

• is the fastest memory that is present in a computer system.
• L1 cache has the data the CPU is most likely to need while completing a certain task.

L2 Hit Time
-The fraction of memory accesses found in a level of the memory hierarchy

Miss Rate
-The fraction of memory accesses not found in a level of the memory hierarchy.