Quiz 4 comprehensive study guide csi 2440 comp systems

Temporal Locality

A principle stating that if a memory location is referenced once it is likely to be referenced again multiple times in the near future

Spatial Locality

A principle stating that if a memory location is referenced once the program is likely to reference a nearby memory location soon

Memory Hierarchy Structure (Speed/Cost)

Fast/Expensive/Small memory is at the top (Registers L0, L1). Slow/Cheap/Large memory is at the bottom (Disk/Tape)

L0 Memory Level

CPU Registers (fastest access)

The goal of the Memory Hierarchy

To create a large pool of storage that costs as much as the cheap bottom layers but serves data at the speed of the top layers

Supercell

A group of adjacent DRAM cells (bits) that are always accessed together. It usually holds 1 byte (8 bits)

DRAM Address Pins Rule

The number of pins is determined by the larger of the Row bits or Column bits (Multiplexing)

Data Pins calculation

It is equal to the number of bits stored in a single supercell (usually 8)

DRAM: 16 Supercells (8 bits each). Find Pins.

Address Pins: 2 (Split 4x4 grid. log2(4)=2). Data Pins: 8

DRAM: 32 Supercells (8 bits each). Find Pins.

Address Pins: 3 (Split 8x4 grid. log2(8)=3). Data Pins: 8

DRAM: 64 Supercells (8 bits each). Find Pins.

Address Pins: 3 (Split 8x8 grid. log2(8)=3). Data Pins: 8

DRAM: 128 Supercells (8 bits each). Find Pins.

Address Pins: 4 (Split 16x8 grid. log2(16)=4). Data Pins: 8

DRAM: Given 3 Address Pins. Calculate Max Supercells.

64 Supercells (2^3 Rows x 2^3 Cols = 8x8 = 64)

DRAM: Given 4 Address Pins. Calculate Max Supercells.

256 Supercells (2^4 Rows x 2^4 Cols = 16x16 = 256)

T-S-O Rule

The order of reading address bits from Left to Right: Tag - Set - Offset

Block Offset bits (b)

Determined by Block Size (B). Formula: b = log2(B)

Set Index bits (s)

Determined by Number of Sets (S). Formula: s = log2(S)

Tag bits (t)

Determined by leftovers. Formula: t = Address_Length - s - b

Cache: Valid Bit

Indicates if the data in a specific cache line is meaningful (1) or empty/garbage (0). When present, is in leftmost position.

Cache: Tag Column

Contains the high-order bits of the address stored in that line. Used to verify if we have a specific block

Cache Hit

Occurs when the Set is Valid AND the Tag in the table matches the Tag in the address

Cache Miss

Occurs if the Set is Invalid OR the Tag does not match

Calc: 8-bit Addr | 4 Sets | 4-Byte Block

Offset=2 bits. Set=2 bits. Tag=4 bits

Calc: 8-bit Addr | 8 Sets | 4-Byte Block

Offset=2 bits. Set=3 bits. Tag=3 bits

Calc: 10-bit Addr | 16 Sets | 8-Byte Block

Offset=3 bits. Set=4 bits. Tag=3 bits

Calc: 6-bit Addr | 2 Sets | 2-Byte Block

Offset=1 bit. Set=1 bit. Tag=4 bits

Map: 11010011 (t=4 s=2 b=2)

Tag: 1101. Set: 00 (Row 0). Offset: 11 (Byte 3)

Map: 00111100 (t=4 s=2 b=2)

Tag: 0011. Set: 11 (Row 3). Offset: 00 (Byte 0)

Map: 10101 (5-bit addr | t=2 s=2 b=1)

Tag: 10. Set: 10 (Row 2). Offset: 1

Write Hit

When the CPU writes to an address that is ALREADY in the cache

Write Miss

When the CPU writes to an address that is NOT in the cache

Write-Allocate

On a write miss load the block from memory into the cache then update it. (Good for locality)

No-Write-Allocate

On a write miss bypass the cache and write directly to lower memory. (Simple hardware)

Problem: A DRAM chip has 32 supercells (8 bits each). Calculate Rows/Cols layout and required Address Pins.

Split: 32 is not a perfect square. Closest power-of-2 rectangle is 8 Rows x 4 Cols. Pins: Max(log2(8)

Problem: A DRAM chip has 128 supercells. Calculate Rows/Cols layout and required Address Pins.

Split: 128 splits into 16 Rows x 8 Cols. Pins: Max(log2(16)

Problem: A DRAM chip has 512 supercells. Calculate Rows/Cols layout and required Address Pins.

Split: 512 splits into 32 Rows x 16 Cols. Pins: Max(log2(32)

Problem: A DRAM chip has 3 Address Pins and 8 Data Pins. What is the maximum capacity in Bytes?

Grid: 3 pins support max 8 Rows x 8 Cols = 64 Supercells. Capacity: 64 Supercells x 1 Byte/cell = 64 Bytes.

Problem: A DRAM chip has 4 Address Pins. What is the maximum capacity in Bytes?

Grid: 4 pins support max 16 Rows x 16 Cols = 256 Supercells. Capacity: 256 Supercells x 1 Byte/cell = 256 Bytes.

Calc: 8-bit Addr | 4 Sets | 4-Byte Block. Find bits (t / s / b).

Offset (b): log2(4)=2. Set (s): log2(4)=2. Tag (t): 8 - 2 - 2 = 4 bits.

Calc: 8-bit Addr | 8 Sets | 4-Byte Block. Find bits (t / s / b).

Offset (b): log2(4)=2. Set (s): log2(8)=3. Tag (t): 8 - 3 - 2 = 3 bits.

Calc: 12-bit Addr | 16 Sets | 8-Byte Block. Find bits (t / s / b).

Offset (b): log2(8)=3. Set (s): log2(16)=4. Tag (t): 12 - 4 - 3 = 5 bits.

Calc: 16-bit Addr | 64 Sets | 16-Byte Block. Find bits (t / s / b).

Offset (b): log2(16)=4. Set (s): log2(64)=6. Tag (t): 16 - 6 - 4 = 6 bits.

Task: Map Address 11010110 using (t=4

s=2

Task: Map Address 11011011 using (t=3

s=3

Task: Map Address 01111010 using (t=3

s=3

Task: Map Address 10011001 using (t=4

s=2

Scenario: Addr 1101 10 01 maps to Set 2. Table Row 2 shows: [Valid=1

Tag=1101]. Result?

Scenario: Addr 1101 10 01 maps to Set 2. Table Row 2 shows: [Valid=1

Tag=0011]. Result?

Scenario: Addr 1101 10 01 maps to Set 2. Table Row 2 shows: [Valid=0

Tag=1101]. Result?

Action: You encounter a Read MISS on Set 5. What happens to the Cache Table?

The cache fetches the block from memory and OVERWRITES the Tag in Set 5 with the new Address's Tag. Valid bit becomes 1.

Action: You encounter a Read HIT on Set 5. What happens to the Cache Table?

Nothing changes in the Tag/Set columns (for a Direct Mapped cache). You simply return the data value found at the Offset.

Explain "Write-Allocate" steps (Write Miss)

1. Detect Miss. 2. Fetch block from Memory. 3. Load into Cache. 4. Update the value in Cache. (Standard for caches that want to exploit locality)

Explain "No-Write-Allocate" steps (Write Miss)

1. Detect Miss. 2. Skip Cache. 3. Write value directly to Lower Memory. (Cache remains unchanged/empty for that address)

Why use No-Write-Allocate?

It is simpler to implement hardware-wise and avoids fetching data if you don't plan to read it again soon (avoiding cache pollution).

CRITICAL: Order of Bit Extraction

Always read Left to Right: 1. TAG (Top bits) -> 2. SET (Middle bits) -> 3. OFFSET (Bottom bits)

Visualizing the Address (8-bit Example)

[ T T T T | S S | O O ]. Tag is the MSB (Most Significant). Offset is the LSB (Least Significant)

Trap Question: If an address is 00001111 and the split is 4-2-2. What is the Set?

Set is 11 (Decimal 3). Do NOT grab the first 11 you see. Ignore the first 4 bits (Tag 0000)

Trap Question: If an address is 11110000 and the split is 4-2-2. What is the Set?

Set is 00 (Decimal 0). Ignore the first 4 bits (Tag 1111)

Step-by-Step Lookup: You calculated Set=2 (Binary 10) and Tag=1101. What is the EXACT first move?

Look strictly at Row 2 (or Row 10) of the table. Ignore all other rows.

Step-by-Step Lookup: You are at Row 2. Valid=1. Table Tag is 1101. What do you do now?

Compare Table Tag (1101) vs Address Tag (1101). They match -> HIT.

Step-by-Step Lookup: It is a HIT. Offset is 01. How do you find the return value?

Look at the Data Columns in Row 2. Find the column labeled 01 (or 1). The value in that box is your answer.

Interpretation: Row 2 has Valid: 0. Address maps to Set 2. Result?

MISS. You do not even need to check the Tag. Invalid means the shelf is empty.

Why is the answer "4 pins" for 128 supercells (2^7) instead of 7 pins?

Because DRAM uses Multiplexing. We split the 7 bits into Rows and Cols. We reuse the same pins for both. We only need enough pins for the largest side (16 rows = 4 bits).

Logic Check: 32 Supercells. Why 3 pins and not 5?

32 splits into 8x4. To address the 8 Rows

Exact Definition: Write Miss

The CPU attempts to modify/save a value to an address

Distinction: Read Miss vs Write Miss

A Read Miss always results in fetching data to cache. A Write Miss might not fetch data (if using No-Write-Allocate policy).

Scenario: Write Miss with "No-Write-Allocate". What happens to the cache?

Nothing. The cache stays empty/unchanged for that address. The data is written directly to Main Memory.