The Memory Hierarchy

Class: CSCE-312

Notes:

Today

• Storage technologies and trends
• Locality of reference
• Caching in the memory hierarchy

Storage Technologies and Trends

Random-Access Memory (RAM)

• Key features

  • RAM is traditionally packaged as a chip.
  • Basic storage unit is normally a cell (one bit per cell).
  • Multiple RAM chips form a memory.

• RAM comes in two varieties:

  • SRAM (Static RAM)
  • DRAM (Dynamic RAM)

SRAM vs DRAM Summary

• SRAM we typically do not need error detection and correction
  • Does not forget the value that was stored until the power goes off
  • Does not need error detection and correction
    • Algorithms that allow memory to detect and correct errors
    • Example: cosmic radiation flipping bits or the capacitor being weak and not remembering some bits
    • Technique example: Error detection with the parity function
  • Used for small memories where latency is more important than capacity
• DRAM: we need error detection and correction
  • These are actual physical devices that can be faulty because of many factors
  • Requires error detection and correction
  • It is smaller and slower, does need refresh, the capacitor forgets the value that was stored at some point.
    • Every few cycles it needs a refresh
  • Used in things like main memories for computers
    • When you buy a PC: 16GB RAM usually means 16GB DRAM

Nonvolatile Memories

"read only memory"

• DRAM and SRAM are volatile memories
  • Lose information if powered off.
• Nonvolatile memories retain value even if powered off
  • Read-only memory (ROM): programmed during production
  • Programmable ROM (PROM): can be programmed once
  • Eraseable PROM (EPROM): can be bulk erased (UV, X-Ray)
  • Electrically eraseable PROM (EEPROM): electronic erase capability
  • Flash memory: EEPROMs. with partial (block-level) erase capability
    • Wears out after about 100,000 erasings
• Uses for Nonvolatile Memories
  • Firmware programs stored in a ROM (BIOS, controllers for disks, network cards, graphics accelerators, security subsystems,…)
  • Solid state disks (replace rotating disks in thumb drives, smart phones, mp3 players, tablets, laptops,…)
    • Flash memory is a very popular type of nonvolatime memory
    • Unfortunately nonvolatile memory often wheres out, but there is technology to mitigate this degradation using certain algorithms to spread the degradation around many blocks in memory
  • Disk caches
    • A lot of space

Traditional Bus Structure Connecting CPU and Memory

• A bus is a collection of parallel wires that carry address, data, and control signals.
• Buses are typically shared by multiple devices.

• Think of it as a network, the network that connects all of these things, CPU, memory, and all those other things
• A bus is a particular kind of network where pretty much is connected to everything else, that makes it simple.
• Inside the CPU:
  • Registers
  • ALU = Arithmetic Logic Unit
  • Bus interface
• I/O bridge = input and output interface
• Main memory = allows memory reads/writes
  • A set of addresses

Memory Read Transaction (1)

• CPU places address A on the memory bus.
  

Memory Read Transaction (2)

• Main memory reads A from the memory bus, retrieves word x, and places it on the bus.
  

Memory Read Transaction (3)

• CPU read word x from the bus and copies it into register %rax.
  

Memory Write Transaction

• "The same thing, just that we are storing a value in main memory"

• CPU places address A on bus. Main memory reads it and waits for the corresponding data word to arrive.

• CPU places data word y on the bus.

• Main memory reads data word y from the bus and stores it at address A.

What's Inside a Disk Drive?

• Still are used a lot in data centers, big desktop computers
• They have a higher capacity than solid state disks
• SCSI connector
  • Interface not very used anymore
  • Ribbon cable that connects to something on the motherboard
• Arm
  • Goes back and forth on the platters (like CDs)
  • As it goes over, it can read different sections of the platter as it speeds up
• Actuator
  • Moves the arm to read something at some place in the platter
• Platters:
  • As two surfaces so that you can record on the bottom and on the top

Disk Geometry

• Disks consist of platters, each with two surfaces.
• Each surface consists of concentric rings called tracks.
• Each track consists of sectors separated by gaps.

• Reads 1s and 0s in terms on whether something is magnetized or if it is not.
• Change the magnetism with respect to error correcting codes.

Disk geometry (Muliple-Platter View)

• Aligned tracks form a cylinder.

• It is convenient to put data in a cylinder because the actuator is on the same place on both sides

Disk Capacity

• Capacity: maximum number of bits that can be stored.

  • Vendors express capacity in units of gigabytes (GB),  where 1 GB = 10^9 Bytes.
  • Why do they do this?
    • Because of marketing, they wanted to have an advantage:
      • "I will call my gigabyte 10^9 instead so that it sounds like I have more gigabytes than others"

• Capacity is determined by these technology factors:

  • Recording density (bits/in): number of bits that can be squeezed into a 1 inch segment of a track.
  • Track density (tracks/in): number of tracks that can be squeezed into a 1 inch radial segment.
    • It has just keep going up and up and up over time
  • Areal density (bits/in2): product of recording and track density.

Recording zones

• Modern disks partition tracks into disjoint subsets called recording zones
  • Each track in a zone has the same number of sectors, determined by the circumference of innermost track.
  • Each zone has a different number of sectors/track, outer zones have more sectors/track than inner zones.
  • So we use average number of sectors/track when computing capacity.

Computing Disk Capacity

Capacity = (# bytes/sector) x (avg. # sectors/track) x (# tracks/surface) x (# surfaces/platter) x (# platters/disk)

Example:

• 512 bytes/sector
• 300 sectors/track (on average)
• 20,000 tracks/surface
• 2 surfaces/platter
• 5 platters/disk

Capacity = 512 x 300 x 20000 x 2 x 5 = 30,720,000,000 = 30.72 GB

Disk Operation (Single-Platter View)

Disk Operation (Multi-Platter View)

Disk Access

• Your disk needs to rotate to go to the actual section that you want to
• The head needs to rotate to the sector you want
  
• Head in position above a track

Disk Access - Service Time Components

1. Head in position above a track
2. Rotation is counter-clockwise
3. About to read sector
4. After reading blue sector
5. Red request scheduled next
6. Seek to red's track
7. Wait for red sector to rotate around
8. Complete read of red

Disk Access Time

• Average time to access some target sector approximated by :

  • Taccess = Tavg seek +  Tavg rotation + Tavg transfer 

• Seek time (Tavg seek)

  • Time to position heads over cylinder containing target sector.
  • Typical Tavg seek is 3—9 ms (Given)
  • Can be a handful of milliseconds
    • One thousand of a second, it is too long to wait for data
    • This is a human amount of time, you can think of how long that took you
    • How many instructions can we run in just 1 ms?
      • ~3 million instructions! in one blink!

• Rotational latency (Tavg rotation)

  • Time waiting for first bit of target sector to pass under r/w head.
  • Tavg rotation = 1/2 x 1/RPMs x 60 sec/1 min
  • Typical Tavg rotation = 7200 RPMs
    • This is considered really fast, so it is not that bad but still adds time to access

• Transfer time (Tavg transfer)

  • Time to read the bits in the target sector.
  • Tavg transfer = 1/RPM x 1/(avg # sectors/track) x 60 secs/1 min.
  • Also not that bad but still adds time to access

Notes:

• More complicated than SSDs because it involves average seek time + average rotation delay + average transfer time
• Seek time is the factor that adds the more time to disk access time

Disk Access Time Example

• Given:

  • Rotational rate = 7,200 RPM
  • Average seek time = 9 ms.
  • Avg # sectors/track = 400.

• Derived:

  • Tavg rotation = 1/2 x (60 secs/7200 RPM) x 1000 ms/sec = 4 ms.
  • Tavg transfer = 60/7200 RPM x 1/400 secs/track x 1000 ms/sec = 0.02 ms
  • Taccess  = 9 ms + 4 ms + 0.02 ms

• Important points:

  • Access time dominated by seek time and rotational latency.
  • First bit in a sector is the most expensive, the rest are free.
  • SRAM access time is about  4 ns/doubleword, DRAM about 60 ns
    • Disk is about 40,000 times slower than SRAM,
    • 2,500 times slower then DRAM.
    • Can we access SRAM directly?
      • Usually you are accessing SRAM
      • When you say mov address to rax, that load instruction will result in the address going over a short bus to access the first level cache (an SRAM) if its not there, then you go to a second level cache (an SRAM), and so on, until you go to a DRAM, or finally to a disk!

Logical Disk Blocks

• Modern disks present a simpler abstract view of the complex sector geometry:

  • The set of available sectors is modeled as a sequence of b-sized logical blocks (0, 1, 2, ...)
  • Disk controller abstracts complex access operations to sectors

• Mapping between logical blocks and actual (physical) sectors

  • Maintained by hardware/firmware device called disk controller.
  • Converts requests for logical blocks into (surface,track,sector) triples.

• Allows controller to set aside spare cylinders for each zone.

  • Accounts for the difference in “formatted capacity” and “maximum capacity”.

Notes;

• Mapping between block numbers and actual physical space in the disk is managed by the controller of the disk
• With SRAM we just never do that, with disk you get these defects, so you have to do bad sector retrieve

I/O Bus

• This bus gives devices access to the memory
• The CPU has access to the memory, and these devices have access to the memory also!
  • In the old days there was a cooperation within the CPU and the Disk controller in order to be able to access main memory, they needed to synchronize in order to write correctly.
  • Now DMA (Direct Memory Access) enables the disk itself to access memory directly, so the CPU can run in parallel while the disk is taking some time retrieving data.
• Inside the Disk controller we also have a tiny CPU with a small ALU that can perform complex Disk sector access operations

Reading Sector

• CPU initiates a disk read by writing a command, logical block number, and destination memory address to a port (address) associated with disk controller.
• Disk controller reads the sector and performs a direct memory access (DMA) transfer into main memory.
• When the DMA transfer completes, the disk controller notifies the CPU with an interrupt (i.e., asserts a special “interrupt” pin on the CPU)

Solid State Disks (SSDs)

• Pages: 512KB to 4KB, Blocks: 32 to 128 pages
• Data read/written in units of pages.
• Page can be written only after its block has been erased
• A block wears out after about 100,000 repeated writes.

Notes:

• Consists of different blocks instead of a physical movement
• It can read one page for one cell, but if it wants to write it needs to re-write the whole block
  • Which mean wearing out the whole block sooner
  • Is more expensive
• The advantage is that there are no moving parts so it is faster

SSD Performance Characteristics

Sequential read tput	550 MB/s	Sequential write tput	470 MB/s
Random read tput	    365 MB/s	Random write tput	303 MB/s
Avg seq read time	    50 us		Avg seq write time	60 us

• Sequential access faster than random access
  • Common theme in the memory hierarchy
• Random writes are somewhat slower
  • Erasing a block takes a long time (~1 ms)
  • Modifying a block page requires all other pages to be copied to new block
  • In earlier SSDs, the read/write gap was much larger.

The CPU-Memory Gap

The gap widens between DRAM, disk, and CPU speeds.

• CPU just gets faster and faster and faster over the years
• SRAM keeps getting faster as well, CPU and SRAM is built in the same technology: NMOS
  • Moores Law: Improving transistor count every 18 months (doubles)
  • Density is increasing but also maybe the size of the circuit is increasing as well
  • Because the physics of scaling transistors in size it also gives us reduces amount of energy for operations between them
  • This stops around early 2000s
    • Though, density continues to increase but the speed advantage is gone because the energy advantage already went away because of physics limits
    • But you can still scale with area
• DRAM is on a different technology, still following Moores Law but not at the same pace
  • Still get fast but not as fast as the CPU
  • Not that much faster from previous
• SSDs are faster than disks but still much more slower than RAM
• If your memory is not that fast, why bothering building faster CPUs?

Locality to the Rescue!

The key to bridging this CPU-Memory gap is a fundamental property of computer programs known as locality

Locality

Locality

• Principle of Locality: Programs tend to use data and instructions with addresses near or equal to those they have used recently

• Temporal locality:

  • Recently referenced items are likely to be referenced again in the near future
    

• Spatial locality:

  • Items with nearby addresses tend to be referenced close together in time
    

Notes:

• Data structures that do not have good spatial locality?
  • A linked List for example
    • If you allocated the nodes at all times of different places
    • Trees might but not necessarily
  • Hash map/Hash table
    • Asymptotically the fastest container
    • But it has terrible spatial locality
    • We still use them because asymptotically is what matters usually (it is more important than spatial locality)

Locality Example

sum = 0;
for (i = 0; i < n; i++)
	sum += a[i];
return sum;

• Data references
  • Reference array elements in succession (stride-1 reference pattern).
    • Spatial Locality
  • Reference variable sum each iteration.
    • Temporal locality
• Instruction references
  • Reference instructions in sequence.
    • Spatial locality
  • Cycle through loop repeatedly.
    • Temporal locality

Qualitative Estimates of Locality

• Claim: Being able to look at code and get a qualitative sense of its locality is a key skill for a professional programmer.

• Question: Does this function have good locality with respect to array a?

int sum_array_rows(int a[M][N])
{
    int i, j, sum = 0;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

• Yes, this is good locality
• When the second index changes faster you go up column by column in row major order
• No cache friendly: accessing something very random at some place and then jumping to something very random at another place.

Locality Example (1)

• Question: Does this function have good locality with respect to array a?

int sum_array_cols(int a[M][N])
{
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

• This is bad locality
• We are accessing in a column major order in a row major language

Locality Example (2)

• Question: Can you permute the loops so that the function scans the 3-d array a with a stride-1 reference pattern (and thus has good spatial locality)?

int sum_array_3d(int a[M][N][N])
{
    int i, j, k, sum = 0;
	
    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            for (k = 0; k < N; k++)
                sum += a[k][i][j];
    return sum;
}

• Note access is sum += a[k][i][j];
  • The last index is j.
  • But the innermost loop is k, which changes the first index.
  • Changing the first index jumps by about N * N ints each step → bad spatial locality.

In C, a 3-D array a[M][N][N] is stored so that the rightmost index varies fastest in memory. So these are contiguous:

a[x][y][0], a[x][y][1], a[x][y][2], ...

A stride-1 reference pattern means the innermost loop should change the last subscript. To fix the above code, make the loop over j innermost (so we walk contiguous memory), and move k outside:

int sum_array_3d(int a[M][N][N])
{
    int i, j, k, sum = 0;
	
    for (k = 0; k < M; k++)        // k indexes the first dimension
        for (i = 0; i < N; i++)    // i indexes the second
            for (j = 0; j < N; j++)// j indexes the last -> stride-1
                sum += a[k][i][j];
    return sum;
}

Now, for fixed k and i, j runs through:

a[k][i][0], a[k][i][1], a[k][i][2], ...

• Which are contiguous → stride-1, good spatial locality.

Memory Hierarchies

• Some fundamental and enduring properties of hardware and software:

  • Fast storage technologies cost more per byte, have less capacity, and require more power (heat!).
  • The gap between CPU and main memory speed is widening.
  • Well-written programs tend to exhibit good locality.

• These fundamental properties complement each other beautifully.

• They suggest an approach for organizing memory and storage systems known as a memory hierarchy.

Notes:

• This lets us build fast systems with slow memories!

Caching in the memory hierarchy

Example Memory Hierarchy

• Registers:
  • The fastest thing
  • Very expensive
  • Change the instruction set:
    • Long conversations with CEOs of Intel and AMD
    • Only a billionare could influence intel to put in a new register
• L1 cache (SRAM)
  • Very small (some Kb only) and holds the most frequently used data or instructions that your program uses
  • Very fast: speed of register is a quarter of a millisecond
• L2 cache (SRAM)
  • Bigger and slower
• L3 cache (SRAM)
  • Bigger and slower but still in CMOS architecture so relatively fast
• Main memory
  • It is a lot bigger, reaching GBs, but of course slower
  • We can use fast DRAM as a cache but that is a little weird
• Local secondary storage (local disks)
  • We do not want to be running at that latency
• Network attached filesystems
  • (Access network-attached storage (NFS and Samba))
  • The last level of memory hierarchy

Summary:

Notes:

• L1, L2, and L3 caches are built with the same architecture (CMOS) but vary increase in size and distance from the CPU.
• "It is easier to find something in a small room than in a large room"

Caches

• Cache:_ A smaller, faster storage device that acts as a staging area for a subset of the data in a larger, slower device.

• Fundamental idea of a memory hierarchy:

  • For each k, the faster, smaller device at level k serves as a cache for the larger, slower device at level k+1.

• Why do memory hierarchies work?

  • Because of locality, programs tend to access the data at level k more often than they access the data at level k+1.
  • Thus, the storage at level k+1 can be slower, and thus larger and cheaper per bit.

• Big Idea:  The memory hierarchy creates a large pool of storage that costs as much as the cheap storage near the bottom, but that serves data to programs at the rate of the fast storage near the top.

Notes:

• If we didn't have locality, caches wouldn't work!
• Memory hierarchy creates a large pull of storage that costs as much as the storage in the bottom layer but can be as fast as the top layer

General Cache Concepts

• Replacement policy:
  • LRU (Least Recently Used)
  • MRU (Most Recently Used)
  • Something that needs to be decided dynamically, because it varies from program to program

General Cache Concepts: Hit

• "You can find a piece of data inside your cache"

General Cache Concepts: Miss

General Caching Concepts: Types of Cache Misses

• Cold (compulsory) miss
  • Cold misses occur because the cache is empty.
• Conflict miss
  • Most caches limit blocks at level k+1 to a small subset (sometimes a singleton) of the block positions at level k.
    • E.g. Block i at level k+1 must be placed in block (i mod 4) at level k.
  • Conflict misses occur when the level k cache is large enough, but multiple data objects all map to the same level k block.
    • E.g. Referencing blocks 0, 8, 0, 8, 0, 8, ... would miss every time.
• Capacity miss
  • Occurs when the set of active cache blocks (working set) is larger than the cache.

Examples of Caching in the Mem. Hierarchy

• TLB: translation of virtual addresses to physical addresses
  • One of the reasons for this is security

Summary

• The speed gap between CPU, memory and mass storage continues to widen.
• Well-written programs exhibit a property called locality.
• Memory hierarchies based on caching close the gap by exploiting locality.