CS704 — Final Term Summary (Lectures 23–45)

📘 Lecture 23 — Instruction Level Parallelism (Hardware Support at Compile Time)

📖 Overview: This lecture explores hardware support techniques used at compile time to overcome the limitations of static scheduling in exploiting Instruction-Level Parallelism (ILP). It focuses on two key methods: conditional/predicated instructions to eliminate branches and convert control dependence into data dependence, and hardware-based compiler speculation to safely move instructions across branches while preserving program behavior.

🗂️ Topics Covered

This lecture begins with a recap of dynamic and static ILP exploitation techniques and their limitations due to control dependences and ambiguous memory references. It then introduces hardware support for VLIW processors, discussing Conditional/Predicated Instructions as an Instruction Set Extension, including Conditional Move, Conditional ADD, and Conditional Load with examples like absolute value and if-conversion. The lecture covers the advantages and limitations of predicated code, introduces Compiler Speculation, and details hardware support methods for speculative execution, including methods to preserve exceptions using poison bits and hardware buffering.

📝 Lecture Summary

Recap: H/W and S/W Exploitation

Both dynamic and static scheduling techniques aim to exploit ILP for single or multiple instruction issue per clock cycle. Dynamic approaches use hardware modifications resulting in superscalar and VLIW processors. Pipeline enhancements include Tomasulo’s pipeline to overcome structural and data hazards, and branch predictors to minimize control hazard stalls. Static scheduling approaches include Loop Unrolling, Software Pipelining, Trace Scheduling, and Superblock Scheduling. These techniques give better performance when branch behavior is correctly predictable at compile time. Otherwise, parallelism cannot be completely exposed due to two reasons: (1) control dependences limit the amount of parallelism that can be exploited, and (2) dependence between memory reference instructions could prevent code movement necessary to increase parallelism.

Hardware Support for VLIW

These limitations, particularly for VLIW processors, can be overcome by providing hardware support at the compile time. The most commonly used techniques are:

• Extension of the Instruction Set by including Conditional or Predicated Instructions
• Hardware speculation to enhance the compiler's ability to move code over branches while preserving exceptional behavior
• Allowing the compiler to reorder load/store instructions when no conflict is suspected but not certain

1: Instruction Set Extension

The extended instruction set including Conditional or Predicated Instructions allows the compiler to group instructions across branches, eliminate branches, and convert control dependence into data dependence. These approaches are equally useful for hardware-intensive (dynamic) and software-intensive (static) scheduling schemes. Predicate registers are included in the IA64 processor to implement predicated instructions.

🔑 Definition — Predicate Register: A one-bit register that controls whether a predicated instruction executes normally (if the condition is true) or acts as a no-operation (if the condition is false).

Conditional Instructions

Conditional instructions have an extra operand—a one-bit predicate register. A condition is evaluated as part of instruction execution to set the value of the predicate register. In HPL-PD from HP Lab, the value of the predicate register is typically set by a Compare-to-predicate operation, e.g., p1 = CMPP <= r1, r2 (here predicate register p1 is set if r2 <= r1). If the condition is true (p1=1), the instruction is executed normally. If false (p1=0), the instruction execution continues as if it were a no-operation. Typical conditional instructions include:

• Conditional Move – CMOVZ R1, R2, R3: moves the value from one register to another if the condition is true (the third operand—predicate register R3—is Zero)
• Conditional ADD – (R8) ADD R1, R2, R3: assumes R1 = R2 + R3 occurs if the predicate register R8 is 1
• Conditional Load – LWC R1, 0(R2), R3: assumes the load occurs unless the third operand R3 is Zero

Example 1: Conditional or Predicated Instructions

Consider the conditional statement: If (A==0) { S=T; }. Assuming registers R1, R2, R3 hold A, S, and T respectively:

Traditional code:

BNEZ  R1, L    ; No-op if A (R1)!= 0
ADDU R2, R3, R0 ; Else replace S (R2) by T (R3)L

Using Conditional Move: CMOVZ R2, R3, R1 (Move R3 to R2 if the third operand R1=0). Using CMOVZ converts the control dependence into a data dependence, resolved where the register-write occurs rather than near the front of the pipe (as with branches). This transformation is used in vector computers as if-conversion, which replaces conditional branches with predicated operations.

Example 2: Absolute Value Function

Conditional move implements the absolute value function: A = abs(B), implemented as:

if B<0 {A=-B;} else {A=B;}

This can be implemented as a pair of conditional moves:

CMOVZ R2, -R3, R1
CMOVZ R2, R3, R4

Or one unconditional move A=B and one conditional move A=-B.

📐 Formula: Conditional Move operation: CMOVZ dest, src, pred → destination register gets source value only if the predicate register is zero (condition true).

📌 Example: For A = abs(B): If R1 holds a comparison flag (B<0), CMOVZ R2, -R3, R1 moves -B to A if B<0; CMOVZ R2, R3, R4 moves B to A if B≥0.

Conditional MOVE Instruction

Conditional moves eliminate branches and improve pipeline behavior but are useful only for short sequences. When predication eliminates branches guarding large blocks of code, many conditional moves are needed. To remedy this, some architectures support full predication, where execution of all instructions is controlled by a predicate. Full prediction allows conversion of large blocks of branch-dependent code. For example, an if-then-else statement within a loop is converted to predicated execution, where code in the if case executes only if the condition is true, and code in the else case executes only if the condition is false.

Predicated LOAD Instructions

Consider a two-issue superscalar that can issue a combination of one memory reference and one ALU operation or a branch every cycle. Original code sequence:

Here, the second LW (LW R9, 0(R8)) depends on the prior load (LW R8, 0(R10)), causing a data dependence stall if the branch is not taken. Using the predicated version LWC: LWC R8, 0(R10), R10 (load occurs unless R10 is 0). This instruction is moved up to the second issue slot:

💡 Why this matters: This improves execution time by eliminating one instruction issue slot and reducing the pipeline stall for the last instruction. However, if the compiler mispredicts the branch, the mispredicated instruction has no effect and does not improve running time—making the transformation speculative.

Advantages of Predicated Code

Conditional or predicated instructions are extremely useful for: implementing short alternative control flows, eliminating some unpredictable branches, and reducing the overhead of global code scheduling.

Limitations on Conditional Instructions

Moving an instruction across a branch and making it conditional will slow the program whenever the moved instruction would not have been normally executed. Predicating a control dependent and eliminating a branch may slow down the processor if that code would not have been executed. Key limitations include:

• Predicated instructions are useful only when the predicate can be evaluated early
• Conditional instructions may cause a stall for data hazard if the condition evaluation and predicated instructions are not separated
• Conditional instructions may have speed penalty compared to unconditional instructions
• Use is limited when control flow involves more than a simple alternative sequence—moving an instruction across multiple branches requires making it conditional on both, requiring additional instructions to compute the controlling predicate

Architectures with Conditional Instructions

Due to these limitations, most architectures include only a few conditional instructions, mostly CMOV. The MIPS, Alpha, PowerPC, SPARC, and Intel (Pentium) all support Conditional Move. The IA-64 Micro Architecture supports full predication of all instructions.

Introduction to Compiler Speculation

Where programs have branches predictable at compile time, the compiler speculates to either improve scheduling and/or increase the issue rate. Predicated instructions may help speculate, but they are more useful when they can eliminate control dependence by if-conversion. However, in most cases, speculated instructions must be moved before the condition evaluation—something that cannot be done by predication alone. This motivates three capabilities for ambitious speculation:

1. The ability to find instructions that can be speculatively moved without affecting program data flow
2. The ability to ignore exceptions in speculated instructions until we know such exception would really occur
3. The ability to speculatively interchange loads and stores, or stores and stores, which may have address conflicts

Note: The first is a compiler capability; the other two can be achieved by hardware support.

📐 Formula: Hardware speculation approach: Supports reordering loads and stores by checking for potential address conflicts at runtime, allowing the compiler to reorder loads and stores when it suspects they do not conflict.

Methods to Preserve Exceptions

Four hardware methods support more ambitious speculation without introducing erroneous exception behavior. The key is that results of a mispredicted speculated sequence will not be used in the final computation, so exceptions are preserved.

Method 1: The hardware and operating system cooperatively ignore exceptions for speculative instructions in the incorrect program path. Exception behavior for the correct program is preserved; for the incorrect one it is ignored. This is used as a "fast mode" under program control. Examples: Memory protection violation (indicates program error, normally causes termination) and Page fault (handles program error, normally resumed).

Method 2: Speculative instructions that never raise an exception are used, and checks are introduced to determine when an exception should occur.

Method 3: A set of bits called poison bits are attached to the result register. These bits are written by speculated instructions when the instruction causes exceptions. The poison bits cause a fault when a normal instruction attempts to use the register. This approach tracks exceptions as they occur but postpones any terminating exception until a value is actually used. The scheme adds a poison bit to every register and another bit to every instruction to indicate if it is speculative. The poison bit of the destination register is set whenever a speculative instruction results in a terminating exception. All other exceptions are handled immediately. If a speculative instruction uses a register with poison bit on, the destination register has its poison bit on. If a normal instruction attempts a register source with poison bit on, the instruction causes a fault.

🔑 Definition — Poison Bits: Bits attached to result registers that are set when a speculative instruction causes an exception; they cause a fault only when a normal instruction attempts to use the register, postponing terminating exceptions until the value is actually used.

Method 4: A mechanism is provided to indicate that an instruction is speculative, and the hardware buffers the instruction result until it is certain that the instruction is no longer speculative.

Summary

Both hardware and software mechanisms provide approaches to exploit ILP. There are certain limitations on both mechanisms.

⭐ Key Takeaways

The critical concepts from this lecture are that conditional/predicated instructions convert control dependence into data dependence by using an extra predicate register to determine execution, allowing branches to be eliminated and ILP to be increased at compile time. The Conditional Move (CMOV) is the most common implementation, but full predication (as in IA-64) is needed for large blocks of code. Hardware-based compiler speculation allows the compiler to move instructions across branches more ambitiously by providing runtime capabilities to check for address conflicts and preserve exception behavior. The key hardware mechanisms for preserving exceptions include ignoring exceptions for mispredicted paths, using speculative instructions that never raise exceptions, poison bits that track exceptions until a register is actually used, and hardware buffering of speculative results until they are confirmed.

🧠 Quick Revision Questions

1. How do conditional/predicated instructions convert control dependence into data dependence?
2. What are the three typical conditional instructions given in the lecture, and what does each do?
3. What are the four hardware methods to preserve exceptions in speculative execution?
4. Explain how poison bits work and when they cause a fault.
5. Why can't predication alone solve all speculative code movement problems, and what additional capabilities does hardware provide?

📘 Lecture 24 — Instruction Level Parallelism (Concluding Instruction Level Parallelism)

📖 Overview: This lecture concludes the discussion on Instruction Level Parallelism (ILP) by exploring compile-time hardware support methods to preserve exceptions during speculation and to handle memory reference speculation. It details four key methods for preserving exception behavior and compares hardware versus software-based speculation approaches, highlighting their respective advantages and limitations for modern computer architecture.

🗂️ Topics Covered

This lecture begins with a recap of previously discussed hardware support for exposing parallelism, including predicated instructions and methods for preserving exception behavior. It then provides an in-depth analysis of four methods to preserve exceptions: Fast Mode, Speculative Instructions, Poison-bit Register, and Hardware (Re-order) Buffering. The lecture proceeds to discuss hardware support for memory reference speculation, including memory disambiguation using speculative load and verify instructions. Finally, it concludes with a comprehensive summary comparing hardware versus software speculation approaches.

📝 Lecture Summary

Recap: Compile Time H/W Support

Last time, we discussed methods to provide hardware support for exposing more parallelism at compile time. This included extending the instruction set with conditional or predicated instructions to eliminate branches and convert control dependence into data dependence, improving processing performance. We also introduced hardware and software-based abilities required to move speculated instructions before branch condition evaluation while preserving exception behavior. We distinguished between exceptions that indicate program error and cause termination (e.g., memory protection violation) and those that can be handled and resumed normally (e.g., page fault in virtual memory). For terminating exceptions in speculated instructions, we cannot take the exception, while for resumable exceptions, they are preserved and processed when the instruction is no longer speculative.

Methods to preserve exception behavior

The four methods to preserve exceptions are: Fast Mode, Speculative-instructions method, Poison-bit Register method, and Hardware (Re-order) buffering.

Methods 1: Fast Mode

The Fast Mode approach is the simplest method where hardware works cooperatively with the operating system to handle presumable exceptions under program control. Here, hardware and software preserve exception behavior for the correct program but ignore it for incorrect programs.

🔑 Definition — Correct Program: A program where the instruction generating a terminating exception is speculative, and the speculative result is simply unused and not harmful.

🔑 Definition — Incorrect Program: A program that previously received a terminating exception and will get an incorrect result in the present instruction, meaning the exception behavior is mispredicted.

📌 Example: Consider the IF-THEN-ELSE code fragment: If (A==0) A = B; Else A = A + 4; Assuming A is at 0(R3) and B is at 0(R2), and speculating the THEN clause is almost always executed:

LD      R1,0(R3) ;load A
BNEZ    R1,L1 ;test A
LD      R1,0(R2) ;then clause (speculative)
J       L2 ;skip else
L1: DADDUI R1,R1,#4 ;else clause
L2: SD     R1,0(R3) ;store A

To preserve speculation, use a temporary register (R14) to avoid destroying R1 when B is loaded:

LD      R1,0(R3) ;load A
LD      R14,0(R2) ;speculative load B
BEQZ    R1,L3 ;other branch of IF
DADDUI  R14,R1,#4 ;else clause
L3: SD   R14,0(R3) ;non-speculative store A

Method 2: Speculative Instructions

This approach introduces speculative versions of instructions, such as Speculative Load (sLD) and Speculative Check (SPECCK). These instructions don't generate terminating exceptions but rather check for such exceptions, preserving exception behavior exactly.

📌 Example: Reconsidering the IF-THEN-ELSE statement using speculative instructions:

LD      R1,0(R3) ;load A
sLD     R14,0(R2) ;speculative, no termination
BNEZ    R1,L1 ;test A
SPECCK  0(R2) ;speculative check
J       L2 ;skip else
L1: DADDUI R1,R1,#4 ;else clause
L2: SD    R1,0(R3) ;store A

The load instruction speculates whether the branch will be taken or not-taken. The speculation check maintains a basic block for the THEN clause, preserving exception behavior. However, extra code is required to check for possible exceptions, resulting in overhead.

💡 Why this matters: This method preserves exception behavior exactly rather than speculatively, making it more precise but introducing code overhead.

Method 3: Poison Bit

The Poison Bit approach attaches a set of bits to every instruction and result register to indicate whether the instruction is speculative. These bits track exceptions as they occur but postpone any terminating exception until a value is actually used. When a bit is set in the result register, it indicates an exceptional condition. When a non-speculative operation encounters a register with the speculative bit set, an exception is raised.

Sequence of steps:

1. The poison bit of the destination register is set whenever a speculative instruction results in a terminating exception
2. All other exceptions are handled immediately
3. If a speculative instruction uses a register with poison-bit turned ON, the destination register simply has its poison-bit turned ON
4. If a normal instruction attempts to use a register source with poison-bit ON, the instruction causes a fault

Resulting Behavior: Any program that would have generated an exception still generates one, but at the first instant where a result is used by a non-speculative instruction. STORES are never speculative as poison-bits exist on registers only.

📌 Example: Using SLD and register R14 with poison-bit for the IF-THEN-ELSE statement:

LD      R1,0(R3) ;load A
sLD     R14,0(R2) ;speculative load B
BEQZ    R1,L3
DADDUI  R14,R1,#4
L3: SD  R14,0(R3) ;store A

If the speculative sLD generates a terminating exception, the poison bit of R14 is turned ON. When the non-speculative SW instruction occurs, it raises an exception if the poison bit for R14 is ON.

Method 4: Hardware Buffering

A hardware buffer, such as the reorder buffer, is provided. The compiler marks instructions as speculative and includes an indicator of how many branches the instruction was moved speculatively. This can be done using either a single bit for branch taken/not-taken path, or a sentinel (guard) marking the original location. Instructions marked as speculative are placed in the re-order buffer, which tracks when instructions are ready to commit and delays write-back. Speculative instructions are not allowed to commit until:

• Either the branches have been speculatively moved and are ready to commit
• Or the corresponding sentinel is reached

Memory Reference Speculation

Hardware support for memory disambiguation (Address Certainty) is needed when optimizing codes by moving LOADs across STOREs. If the latency of LOAD is high, it may be desirable to move LOAD before STORE. However, this optimization is not valid if LOAD and STORE reference the same location and the compiler is uncertain at compile time.

To resolve this, two special instructions are included in the ISA:

• LDS R1, 0(R2) — Load Speculatively: Initiates a load like a normal load instruction, but a log entry is made in a table to store the memory location
• LDV R2, 0(R2) — Load Verify: Checks if a store to the memory location has occurred since the LDS. If so, the new load is issued and the pipeline stalls; otherwise, it's a NO-OP

Process: When LDS is executed, the hardware saves the address in a log table. If a subsequent STORE changes the location before LDV, speculation has failed. If the STORE doesn't touch the location, speculation is successful.

Handling speculation failure can be done in two ways:

1. If only the load was speculated: redo the load using LDV, which supplies the target register in addition to memory address
2. If the additional instruction (LDV) is also speculated: re-execute all speculated instructions starting with the LOAD using a fix-up sequence, where LDV specifies the address of the fix-up code

Example: Conditional Moving up the Branch

Using conditional move instructions can eliminate branches and guard against memory access violations. Consider a 2-issue superscalar code where LW after Branch depends on prior load:

LW    R1,40(R2)     ADD   R3,R4,R5
                    ADD   R6,R3,R7
BEQZ  R10,L  
LW    R8,0(R10)  
LW    R9,0(R8)

Revised code using conditional move: Assuming R29 contains a safe address, R30 saves original R8:

DADDI       R29,R0,#1000 ;initialize R29 to safe address
LW          R1,40(R2)    ;first load
MOV         R30,R8       ;save R8 in unused R30
CMOVNZ      R29,R10,R10  ;R29=R10 if R10 is safe and non-zero
LW          R8,0(R29)    ;speculative load
CMOVZ       R8,R30,R10   ;restore R8 if R10=0
BEQZ        R10,L
LW          R9,0(R8)

Branch-free code using two additional registers (R30, R31):

ADDI        R29,R0,#1000
LW          R1,40(R2)
MOV         R30,R8
MOV         R31,R9       ;save R9 in unused R31
CMOVNZ      R29,R10,R10
LW          R8,0(R29)
LW          R9,0(R8)     ;load speculated
CMOVZ       R8,R30,R10
CMOVZ       R9,R31,R10   ;restore R9 if needed

Summary: Hardware versus software speculation

The limitations of both approaches are summarized as follows:

1. Memory reference certainty: To speculate extensively, we must ascertain memory references, which is difficult at compile time. In hardware-based schemes, dynamic run-time certainty of memory address uses Tomasulo's pipelined structure to move loads past stores at run time.

2. Control flow unpredictability: Hardware-based speculation works better when control flow is unpredictable and when hardware-based branch prediction is superior to compile-time software-based branch prediction.

3. Precise exception model: Hardware-based speculation maintains a completely precise exception model for speculated instructions.

4. No compensation needed: Hardware-based speculation does not require compensation needed by ambitious software speculation mechanisms.

5. Compiler advantage: Compiler-based approaches have the ability to see further in the code sequence, potentially providing better code scheduling than purely hardware-driven approaches (e.g., conditional move instructions).

6. Implementation independence: Hardware-based speculation with dynamic scheduling does not require different code sequences for different architecture implementations. However, the major disadvantage is the extra hardware resources and complexity of the structure.

⭐ Key Takeaways

A student must remember the four distinct methods for preserving exception behavior during speculation: Fast Mode (cooperative OS-HW ignoring incorrect program exceptions), Speculative Instructions (using sLD and SPECCK for exact preservation), Poison Bits (attaching bits to results to postpone exceptions until use), and Hardware Buffering (using reorder buffers with sentinels). The critical distinction between correct programs (where speculative result is unused) and incorrect programs (where exception is mispredicted) is essential. For memory reference speculation, the LDS/LDV instruction pair provides runtime memory disambiguation, allowing loads to be moved speculatively before stores with verification. Hardware speculation excels with unpredictable control flow and provides precise exception models but requires significant hardware complexity, while compiler speculation can see further ahead in code and uses techniques like conditional move instructions for branch elimination.

🧠 Quick Revision Questions

1. What are the four methods discussed for preserving exception behavior during speculation, and how does the Fast Mode approach differ from the others?
2. Explain the role of poison bits in preserving exception behavior. When is an exception actually raised when using poison bits?
3. How do the LDS and LDV instructions work together to support memory reference speculation, and what happens when speculation fails?
4. Compare hardware-based speculation with compiler-based speculation regarding memory reference certainty, control flow handling, and hardware complexity.
5. In the conditional moving example, why is an unused register (R29) initialized to a safe address, and what happens to the original register value (R8) during speculative execution?

📘 Lecture 25 — Memory Hierarchy Design (Storage Technologies Trends and Caching)

📖 Overview: This lecture explores what lies outside the processor, focusing on the memory hierarchy and storage technologies. It explains how the principle of locality allows systems to achieve fast access speeds at low cost by organizing memory into levels, from fast but expensive SRAM to slow but cheap disk storage, and details the design and operation of key memory types.

🗂️ Topics Covered

The lecture begins by recapping processor performance and defining the I/O system outside the processor. It introduces the memory hierarchy and the principle of locality. It then categorizes storage systems, with a deep dive into Random-Access Memory (RAM) types: Static RAM (SRAM) and Dynamic RAM (DRAM), including their cell structures and organization. Enhanced DRAM types are covered, followed by nonvolatile memories, disk geometry and capacity, disk access time with a concrete example, and logical disk blocks. It concludes with the CPU-memory gap and a summary.

📝 Lecture Summary

Recap: Processor Performance

The lecture recaps that processor performance involves the design of the data path and control, utilizing hardware-based and software-based techniques to expose Instruction-Level Parallelism (ILP).

What is outside processor?

The performance of a computer is heavily influenced by what is outside the processor, referred to as the I/O system. This system includes the memory system, buses, and controllers. The design goal of the memory system for high-performance computers is to present the user with as much memory as is available. Since fast memory is expensive and cheap memory is slow, a memory hierarchy is organized into several levels. This hierarchy aims to achieve a cost as low as the cheapest memory and a speed as fast as the fastest memory.

Principle of Memory hierarchy

The principle of memory hierarchy is based on "The principle of locality", which determines where each type of module is located in the memory system. The advantage of this principle is that it provides an average access speed very close to that of the fastest technology, at a cost very close to that of the cheapest technology.

Storage Type in Memory System

Semiconductor memories such as registers, Static RAM, and Dynamic RAM are fast in access speed but expensive. They are used in small sizes and are placed either inside or closest to the processor. Secondary storage devices, which offer huge storage at the lowest cost per bit, are placed farthest away from the processor.

Storage Systems

Memory systems can be classified based on different attributes:

• Material: Semiconductor, magnetic, optical
• Accessing: Random, Sequential, Hybrid
• Store/Retrieve: ROM (Read Only Memory), RMM (Read Mostly Memory), and RWM (Read Write Memory)

Random-Access Memory (RAM)

RAM is packaged as a chip, with the basic storage unit being a cell (one bit per cell). Multiple RAM chips form a memory. The two main types are Static RAM (SRAM) and Dynamic RAM (DRAM).

Static RAM: Basic Cell

SRAM uses a flip-flop circuit (typically 6 transistors) to store a bit. The state is stable as long as power is applied.

• Write: Drive the bit lines (bit=1, bit=0) and then select the row.
• Read: Pre-charge bit and bit to Vdd, then select the row. The cell pulls one line low, and a sense amplifier on the column detects the difference between bit and bit.

🔑 Definition — SRAM (Static RAM): A type of semiconductor memory that uses a bistable latching circuit (flip-flop) to store each bit. It is faster and more expensive than DRAM but does not require refreshing.

Dynamic Random Access Memory (DRAM)

Each DRAM cell stores a bit using a capacitor and a transistor. The value must be refreshed every 10-100 ms. DRAM is sensitive to disturbances and is slower and cheaper than SRAM.

🔑 Definition — DRAM (Dynamic RAM): A type of semiconductor memory that stores each bit as a charge on a tiny capacitor. It requires periodic refreshing to maintain the stored data, making it slower but denser and cheaper than SRAM.

Basic DRAM Cell

• Write: Drive the bit line and select the row by turning on the pass transistor.
• Read: Pre-charge the bit line to Vdd and select the row. The cell and bit line share charges, causing a very small voltage change on the bit line. A sensitive sense amplifier detects this change. The read operation is destructive, so an automatic write-back (restore) must be performed at the end of every read.
• Refresh is achieved by performing a dummy read to every cell.

📐 Formula: The operation of a DRAM cell is based on charge sharing between the cell's capacitor and the bit line capacitance.

Reading DRAM Supercell (2,1)

A DRAM chip is organized as a matrix of supercells.

• Step 1(a): The Row Access Strobe (RAS) selects row 2.
• Step 1(b): The entire row 2 is copied from the DRAM array to the row buffer.
• Step 2(a): The Column Access Strobe (CAS) selects column 1.
• Step 2(b): Supercell (2,1) is copied from the buffer to the data lines, and eventually back to the CPU.

Enhanced DRAMs

Several enhancements have been made to standard DRAM to improve performance:

1. Fast Page Mode DRAM (FPM DRAM): In normal DRAM, each M-bit access requires a RAS/CAS cycle. In FPM DRAM, a row is saved into an N x M register. Subsequent accesses to the same row (page) can be performed by only providing a column address, which is faster.
2. Extended Data Out DRAM (EDO DRAM): An enhanced FPM DRAM with more closely spaced CAS signals, allowing for faster burst transfers.
3. Synchronous DRAM (SDRAM): Driven with the rising clock edge instead of asynchronous control signals, simplifying the interface and increasing speed.
4. Double Data Rate synchronous DRAM (DDR SDRAM): An enhancement of SDRAM that uses both the rising and falling edges of the clock as control signals, effectively doubling the data transfer rate.
5. Video RAM (VRAM): Like FPM DRAM, but output is produced by shifting the row buffer. It is dual-ported to allow concurrent reads and writes, useful for video graphics.

Nonvolatile Memories

DRAM and SRAM are volatile memories; they lose information when powered off. Nonvolatile memories retain their value even when powered off. The generic name for these is Read-Only Memory (ROM), which is misleading as some types can be read and modified.

• Types of ROMs: Programmable ROM (PROM), Erasable Programmable ROM (EPROM), Electrically Erasable PROM (EEPROM), and Flash memory.
• Firmware is a program stored in a ROM, such as boot-time code (BIOS) or code for graphics cards and disk controllers.

Disk Geometry

A disk consists of one or more platters, each with a magnetic surface. The surface is divided into concentric circles called tracks, and each track is further divided into sectors. A cylinder is the set of aligned tracks across multiple platters.

Disk Capacity

Capacity is the maximum number of bits that can be stored on a disk. It is determined by:

• Recording density (bits/in): number of bits in a 1-inch segment of a track.
• Track density (tracks/in): number of tracks in a 1-inch radial segment.
• Areal density (bits/in²): the product of recording and track density.

Disk Access Time

The average time to access a target sector is approximated by: Taccess = Tavg seek + Tavg rotation + Tavg transfer

• Seek time (Tavg seek): Time to position the read/write head over the correct cylinder. Typical Tavg seek = 9 ms.
• Rotational latency (Tavg rotation): Time waiting for the first bit of the target sector to rotate under the read/write head. Tavg rotation = 1/2 × 1/RPMs × 60 sec/1 min.
• Transfer time (Tavg transfer): Time to read the bits in the target sector. Tavg transfer = 1/RPM × 1/(avg # sectors/track) × 60 secs/1 min.

📐 Formula: Taccess = Tavg seek + Tavg rotation + Tavg transfer Plain-English Meaning: The total time to read a sector is the sum of the time to move the head to the right track, the time to wait for the disk to spin the sector under the head, and the time to read the data.

📌 Example: Disk Access Time Calculation

• Given: Rotational rate = 7,200 RPM, Avg seek time = 9 ms, Avg # sectors/track = 400.
• Derived:
  • Tavg rotation = 1/2 × (60 secs / 7200 RPM) × 1000 ms/sec = 4 ms.
  • Tavg transfer = 60/7200 RPM × 1/400 secs/track × 1000 ms/sec = 0.02 ms.
  • Taccess = 9 ms + 4 ms + 0.02 ms = 13.02 ms.
• Important Points: Access time is dominated by seek time and rotational latency. The first bit in a sector is the most expensive; the rest are free. SRAM access time is about 4 ns/doubleword, and DRAM about 60 ns. A disk is about 40,000 times slower than SRAM and 2,500 times slower than DRAM.

Logical Disk Blocks

The set of available sectors is modeled as a sequence of b-sized logical blocks. The mapping between logical blocks and actual (physical) sectors is maintained by the disk controller, a hardware/firmware device. It converts requests for logical blocks into (surface, track, sector) triples.

CPU-Memory Gap

The gap between the speed of the processor and the speed of storage devices (DRAM, SRAM, and Disk) is increasing with time, making memory hierarchy design a critical challenge for computer architects.

💡 Why this matters: The CPU-memory gap is the fundamental reason why memory hierarchy and caching are necessary for modern computer performance. Without them, the processor would spend most of its time waiting for data.

⭐ Key Takeaways

The memory hierarchy uses the principle of locality to create a system that appears as fast as the fastest level and as cheap as the cheapest level. SRAM is fast, expensive, and does not require refreshing, while DRAM is slower, cheaper, and must be refreshed, making it suitable for main memory. Disk storage is orders of magnitude slower than DRAM and SRAM, with access time dominated by mechanical seek time and rotational latency. Enhanced DRAMs like FPM, EDO, SDRAM, and DDR improve upon standard DRAM to reduce access latency. The growing CPU-memory gap is the primary motivation for sophisticated memory hierarchies and caching strategies.

🧠 Quick Revision Questions

1. What is the principle of locality and how does it benefit memory hierarchy design?
2. Explain the difference in the read and write operations of an SRAM cell versus a DRAM cell.
3. What are the components of disk access time, and which of them contribute the most to the total time?
4. How does Fast Page Mode (FPM) DRAM improve upon the performance of regular DRAM?
5. What is the "CPU-memory gap" and why is it a significant problem in computer architecture?

📘 Lecture 26 — Memory Hierarchy Design (Concept of Caching and Principle of Locality)

📖 Overview: This lecture introduces the foundational concepts of memory hierarchy design, focusing on caching mechanisms and the principle of locality. It explains how different memory technologies (SRAM, DRAM, disk) are organized hierarchically to bridge the growing speed gap between the CPU and main memory, and why caching is essential for modern computer performance.

🗂️ Topics Covered

The lecture begins with a recap of storage trends and device characteristics, then introduces the concept of cache memory as a staging area for frequently used data. It explains the principle of locality (temporal and spatial) with detailed examples, covers cache addressing techniques including direct mapping, and concludes with an analysis of cache transactions (hits, misses, and penalty calculations) along with placement and replacement policies.

📝 Lecture Summary

Recap: Storage Devices

The lecture reviews semiconductor memories including SRAM, DRAM, and magnetic disk storage. DRAM is slow but cheap relative to SRAM and serves as main memory for holding moderately large amounts of data and instructions. Disk storage is the slowest and cheapest, used for secondary storage to hold bulk data and instructions. The CPU-Memory Gap — the speed difference between DRAM/Disk and the processor compared to SRAM — is increasing very rapidly over time.

Memory Hierarchy Principles

The speed of DRAM and CPU complement each other. Memory is organized in a hierarchy based on two concepts: Concept of Caching and Principle of Locality.

1: Concept of Caching

A cache is a staging area or temporary place to store a frequently-used subset of data or instructions from the relatively cheaper, larger, and slower memory. This avoids having to go to main memory every time the information is needed.

Memory devices of different types are used for each level k. The faster, smaller device at level k serves as a cache for the larger, slower device at level k+1. Programs tend to access data at level k more often than at level k+1. Storage at level k+1 can be slower, but larger and cheaper per bit. The result is a large pool of memory that costs as much as the cheap storage at the highest level (near bottom in hierarchy) but serves data at the rate of fast storage at the lowest level (near top in hierarchy).

2: Principle of Locality

Programs access a relatively small portion of the address space at any instant of time. This principle has two types:

🔑 Definition — Temporal locality: If an item is referenced, it will tend to be referenced again soon (locality in time).

🔑 Definition — Spatial locality: If an item is referenced, items whose addresses are close by tend to be referenced soon (locality in space).

A well-written program tends to reuse data and instructions that are either near those used recently or that were recently referenced themselves.

Locality Example — Program:

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

• Spatial Locality: All array elements a[i] (data) are referenced in succession at each loop iteration, so all array elements should be located at the same level. All instructions of the loop are referenced repeatedly in sequence, therefore should be located at the same level.
• Temporal Locality: The variable sum is referenced each iteration (recently referenced data is used again). The instructions of the loop sum += a[i] cycle through the loop repeatedly.

💡 Why this matters: The memory hierarchy keeps more recently accessed data items closer to the processor because the processor will likely access them again soon. Not only do we move the item just accessed closer, but we also move adjacent data items.

Hierarchy List

• Register File — Level 0 — Datapath
• L1 — Level 1 — Cache on Chip
• L2 — Level 2 — External Cache
• Main memory — Level 3 — System Board DRAM
• Disk cache — Level 4 — Disk drive
• Disk — Level 5 — Magnetic disk
• Optical — Level 6 — CDs etc. — bulk storage
• Tape — Level 7 — Huge cheapest storage

Intel Processor Cache Evolution

• 80386 — No on-chip cache
• 80486 — 8K byte lines
• Pentium (all versions) — Two on-chip L1 caches for Data & Instructions
• Pentium 4 — L1 caches: Two 8K bytes; L2 cache: 256K feeding both L1 caches

Cache Devices

Cache device is a small SRAM made directly accessible to the processor. DRAM, accessible by the cache as well as by the user or programmer, is placed at the next higher level as Main Memory. Larger storage such as disk is placed away from the main memory.

Memory Hierarchy Terminology

🔑 Definition — Hit: Data the processor wants to access appears in some block in the upper level.

• Hit Rate: The fraction of memory accesses that are found in the upper level (HIT).
• Hit Time: Time to access the upper level, consisting of: (i) RAM access time, (ii) Time to determine if this is a hit or miss.

🔑 Definition — Miss: Data needed by the processor is not found in the upper level and must be retrieved from a block in the lower level.

• Miss Rate = 1 - (Hit Rate)
• Miss Penalty: The sum of time to replace a block in the upper level and to deliver the block to the processor.

📐 Formula: Miss Rate = 1 - Hit Rate

📌 Recommendation: Hit Time must be much much smaller than Miss Penalty, otherwise no need for memory hierarchy.

Cache Hit

When the CPU needs object d stored in block b (e.g., block 14) of the level k+1 memory, and the corresponding block (e.g., block 2) exists in the cache at level k, the program finds block b in the cache and object d is transferred directly to the CPU.

Cache Miss

When the program needs object A stored in block C (e.g., block 12) at level k+1, but block C is not at level k, a cache miss occurs. Level k cache must fetch it from level k+1 and then transfer object A to the CPU.

Placement and Replacement Policies

If level k cache is full, some current block must be replaced (evicted). The "victim" depends on:

• Cache design defining the relationship of cache addresses with higher level memory addresses
• Placement policy: Determines where the new block can go
• Replacement policy: Defines which block should be evicted

Types of Misses

🔑 Definition — Cold (compulsory) miss: Occurs when the cache is empty, at the beginning of cache access.

🔑 Definition — Capacity miss: Occurs when the set of active cache blocks (working set) is larger than the cache.

🔑 Definition — Conflict miss: Occurs when the level k cache is large enough, but multiple data objects all map to the same level k block.

📌 Example: Conflict Miss If the placement policy is based on direct addressing, then Block n at level k+1 must be placed in block (n mod 4) at level k. In this case, referencing blocks 0, 8, 0, 8, 0, 8... would miss every time because 8 mod 4 = 0, as both blocks 0 and 8 of level k+1 are placed at location 00 at level k.

Cache Design — Tags

More than one block from level k+1 memory (main memory, with N blocks) may be placed at the same location (given by N MOD M) in level-k memory (cache, with M blocks). Therefore, a tag must be associated with each block in the level-k (cache) memory to identify its position in the level k+1 memory (Main memory).

Direct Mapping Example

A 16 MB main memory has a 24-bit address bus. It is organized in 32-bit blocks. A 16K word (64 KB) cache requires a 16-bit address and 8-bit tag.

📐 Address Structure (24-bit):

• 2 bits: Word identifier (4-byte block)
• 22 bits: Block identifier for main memory
  • 8 bits: Tag (= 22 - 14)
  • 14 bits: Slot or line or index value for cache

🔑 Key Rule: No two blocks in the same line have the same Tag field. Check contents of cache by finding line and checking Tag.

Cache Design — Another Example

Assume a 1 KB direct mapped cache with block size = 32 bytes. Each block associated with the cache tag will have 32 bytes.

Address Translation — Direct Mapped Cache

Assume level k+1 main memory of 4 GB, with Block Size = 32 bytes, and level k cache of 1 Kbyte.

📐 Address Breakdown:

• 5 least significant bits (bits 0-4): Used as byte select within the cache block (since 2⁵ = 32 bytes)
• 32 - 10 = 22 bits: The upper bits stored as cache tag (since 1 KB = 2¹⁰ bytes)
• Bits 5 through 9 (the middle bits): Used as Cache Index to select the proper cache block entry

⭐ Key Takeaways

The memory hierarchy works because of the principle of locality: programs tend to reuse recently accessed data (temporal locality) and nearby data (spatial locality). Cache acts as a small, fast staging area between the processor and slower main memory, storing frequently used subsets to minimize access time. Understanding hit rate, miss rate, and miss penalty is critical because the penalty for a miss must be much larger than hit time for caching to be beneficial. Direct mapping uses a simple address structure where block identifier bits are split into tag and index, with the index determining the cache line and the tag verifying whether the correct block is present. The three types of misses (cold, capacity, and conflict) arise from different limitations in cache design and program behavior.

🧠 Quick Revision Questions

1. What are the two types of locality, and how do they affect memory hierarchy design?
2. Why must Hit Time be much smaller than Miss Penalty for memory hierarchy to be effective?
3. How does direct mapping determine which cache line a main memory block will occupy?
4. What is the difference between a compulsory miss, a capacity miss, and a conflict miss?
5. In the direct mapping example with a 1 KB cache and 32-byte blocks, which bits of the address are used for the byte offset, cache index, and tag?

📘 Lecture 27 — Memory Hierarchy Design (Cache Design Techniques)

📖 Overview: This lecture explores the critical aspects of cache memory design within the memory hierarchy. It covers cache performance metrics like miss rate and miss penalty, and delves into three fundamental cache organization techniques: direct mapped, fully associative, and set associative caches. Understanding these designs is crucial for optimizing data access speed in modern computer architecture.

🗂️ Topics Covered

The lecture begins with a recap of caching principles and locality, then introduces key performance metrics such as miss rate, miss penalty, and average access time. It presents a detailed performance example. The core of the lecture covers block size trade-offs and the three categories of cache organization based on block placement: direct mapped, fully associative, and set associative mapping, including their address structures, advantages, and disadvantages.

📝 Lecture Summary

Recap: Memory Hierarchy Principles

The memory hierarchy is designed to provide high-speed storage at the cheapest cost per byte. It organizes different memory modules based on the concept of caching and the principle of locality. Caching uses a small, fast, and expensive storage as a staging area for a frequently-used subset of data from larger, slower memory. The principle of locality states that a processor accesses a relatively small portion of the address space at any time, which includes temporal locality (recently accessed items will be accessed again) and spatial locality (items near accessed items will be accessed soon).

Recap: Working and Operation of Memory Hierarchy & Cache

The memory hierarchy moves recently accessed data items closer to the processor, along with their adjacent items. A cache device is a small SRAM that sits between the CPU and main memory. Data transfer between cache and CPU is word transfer, while between cache and main memory it is block transfer. The cache controller checks for data on a CPU request. If present, it's a HIT and data is delivered fast. If not present, it's a MISS, and the required block is read from main memory to cache, then delivered to the CPU.

Cache Memory Performance

Cache memory performance is a trade-off primarily measured by miss rate, miss penalty, and average access time. Miss Rate is the fraction of memory accesses not found in the cache, calculated as number of misses / total memory accesses. Since Hit Rate is the fraction found, Miss Rate = 1 – Hit Rate. Miss Penalty is the number of stall cycles incurred during a miss, including time to replace a block and deliver it to the processor. The formula for performance is:

• Average Access Time = Hit Time x (Hit Rate) + Miss Penalty x Miss Rate
• CPU Execution Time = (CPU Clock Cycles + Memory Stall Cycles) x clock cycle time
• Memory stall cycles = Number of Misses x Miss Penalty = IC x (Misses / Instructions) x Miss Penalty = IC x (Memory Access per Instruction) x Miss Rate x Miss Penalty

💡 Why this matters: These formulas are essential for quantifying the impact of cache misses on overall CPU performance, allowing architects to make informed design choices.

Cache Performance Example

• Assume: CPI=1.0 (all hits), 50% of instructions are load/store, miss rate = 2%, miss penalty = 25 clock cycles.
• Execution Time for all Hit: IC x 1.0 x cycle time
• Memory Stall Cycles: IC x (1 + 0.5) x 0.02 x 25 = IC x 0.75
• CPU Execution Time (with cache): (IC x 1.0 + IC x 0.75) x cycle time = 1.75 x IC x cycle time
• Conclusion: The computer with no cache misses is 1.75 times faster.

Block Size Tradeoff: Miss Rate, Miss Penalty, and Average Access Time

As block size increases, the miss rate initially decreases due to spatial locality but will eventually increase, a phenomenon called the ping pong effect, where data bounces in and out of the cache. The miss penalty also increases with block size because more data must be transferred. Therefore, beyond a certain point, the average access time becomes a more comprehensive performance metric than either miss rate or miss penalty alone.

How do you Design a Cache?

The design process involves decoding the memory address from the CPU into a physical address. For a read, data is loaded from the memory location at that address. For a write, data is stored to that address. The core decision is how to place a block from main memory into the cache.

Categories of Cache Organization

There are three block placement policies for cache organization:

1. Direct Mapped: Each block has only one place it can appear in the cache.
2. Fully Associative: A block can be placed anywhere in the cache.
3. Set Associative: A block can be placed in a restricted set of places (a group of blocks).

Direct Mapped Cache Organization

In a direct mapped cache, each main memory block maps to only one specific cache line. The mapping is determined by: (Block address) MOD (Number of blocks in the cache). For example, with 16 MB main memory and 1 MB cache organized in 4-byte blocks, main memory (1M blocks) is divided into 16 sections, each with 256K blocks. A block at line 0CE7 from any section will always map to line 0CE7 in the cache.

🔑 Definition — Direct Mapping Address Structure: A 24-bit address is divided into a 2-bit word identifier (for 4-byte block), an 8-bit tag, and a 14-bit slot/line/index for the cache. The tag for blocks in the same cache line must be different.

📐 Formula: (Block address) MOD (Number of Blocks in the cache) → This determines the unique cache line where a block can be placed.

📌 Example: For a 1 KB direct mapped cache with a 32-byte block size, the address is split into a Byte Select field (5 bits for 32 bytes), a Cache Index field (5 bits for 32 sets, as 1 KB / 32 bytes = 32), and a Tag field (the remaining bits from a 32-bit address, e.g., 22 bits for a 4GB main memory).

Direct Mapping pros & cons

• Pros: Simple and inexpensive.
• Cons: If a program repeatedly accesses two blocks that map to the same line, cache misses are very high, a problem known as conflict misses. A valid bit is included to check if the cache contents are valid.

Associative Mapping (Fully Associative)

In associative mapping, a main memory block can load into any line of the cache. The memory address is interpreted as tag and word. The tag uniquely identifies the block of memory, and every line's tag is examined for a match. This eliminates the cache index.

Fully Associative Cache Organization

This design forgets about the cache index, allowing any block to be placed anywhere. It stores all upper bits of the address (except byte select) as the cache tag and uses one comparator for every cache entry. The address is sent to all entries in parallel for an associative lookup.

🔑 Definition — Associative Mapping Address Structure: A 22-bit tag is stored with each 32-bit block of data. The tag field is compared with the tag entry in the cache to check for a hit. The least significant 2 bits identify the word within the block.

📌 Example: The address FFFFC has a tag 3FFFFC and data 24682468 stored in cache line 3FFF. There is no index; the tag must match any entry.

Characteristics of Fully Associative Cache

• This is the most complex end of the cache design spectrum (hardware intensive) and is limited to 64 or fewer entries.
• Conflict miss is zero, as any block can go anywhere.
• When more blocks are accessed than the cache can hold, a Capacity Miss occurs, requiring an existing block to be evicted.

Set Associative Mapping Summary

• Address length: (s + w) bits; Number of addressable units: 2^(s+w); Block size: 2^w words/bytes.
• Number of blocks in main memory: 2^d; Number of lines in set: k; Number of sets: v = 2^d.
• Number of lines in cache: kv = k * 2^d; Size of tag: (s – d) bits.

Set Associative Mapping

The cache is divided into a number of sets, each containing a number of lines. A given block maps to any line within a specific set, chosen by: (block address) MOD (Number of sets in cache). If there are n blocks in a set, it's an n-way set associative cache. For example, a 2-way set associative cache has two cache entries for each cache index.

🔑 Definition — Set Associative Mapping Address Structure: The address is divided into a Tag field, a Set field (used to determine the cache set), and a Word field (for the specific word within the block). The tags in the selected set are compared in parallel.

📌 Example (2-way): The address 1FF 7FFC has tag 1FF and data 12345678 in set number 1FFF. The address 001 7FFC has tag 001 and can be placed in the same set (1FFF) but in a different line within that set.

Working and Disadvantages of a 2-way Set Associative Cache

• How it works: The cache index selects a set. The two tags in that set are compared in parallel with the upper bits of the address. If neither matches, it's a miss. If one matches, the data from that side is selected.
• Disadvantages:
  1. Requires N comparators instead of one.
  2. Slower due to extra multiplexer delay.
  3. Data is available only after the hit/miss signal is valid. In a direct mapped cache, data is available before the hit/miss signal, allowing the processor to speculatively use the data (which is safe 90% of the time due to high hit rates). This speculation is not possible with a set-associative cache.

⭐ Key Takeaways

A student must understand that cache performance is governed by the trade-off between miss rate, miss penalty, and block size, which is encapsulated in the average access time formula. The three fundamental cache organizations—direct mapped, fully associative, and set associative—offer a spectrum of complexity and performance, balancing hardware cost against conflict misses. Direct mapped caches are simple and fast but prone to high conflict misses, while fully associative caches eliminate conflict misses but are hardware-intensive and slow. Set associative caches provide a practical compromise, with the number of ways being a key design parameter that affects both miss rates and access latency.

🧠 Quick Revision Questions

1. Define the three key performance metrics for a cache and write the formula for Average Access Time.
2. How does the direct mapping function (Block address) MOD (Number of blocks in the cache) determine where a main memory block is placed?
3. In a fully associative cache, what is the primary hardware requirement that makes it difficult to scale to large sizes?
4. What is the key advantage of a direct mapped cache over a set-associative cache regarding data availability?
5. A 2-way set associative cache has a miss rate of 1% and a miss penalty of 20 cycles. Calculate the Average Access Time if the hit time is 1 cycle.

📘 Lecture 28 — Memory Hierarchy Design (Cache Design and policies)

📖 Overview: This lecture explores memory hierarchy design, specifically focusing on cache memory design and policies. It covers block placement, identification, replacement, and write strategies, explaining how these policies impact cache performance and overall system efficiency in modern computer architectures.

🗂️ Topics Covered

Recap of cache addressing techniques and organizations (Direct Mapped, Fully Associative, Set Associative). Detailed coverage of memory hierarchy designer's concerns including block placement, identification, replacement policies, and write strategies. Discussion on write buffer management and write-miss policies with examples comparing no-write allocate versus write allocate.

📝 Lecture Summary

Recap: Block Size Trade off

The lecture reviews the impact of block size on cache performance, noting that larger block sizes reduce miss rate, but if block size is too big relative to cache size, miss rate increases. Miss penalty also increases with block size, and these parameters combine to affect Average Access Time.

Recap: Cache Organizations

Three cache organizations are reviewed based on block placement policy:

• Direct Mapped: each block has only one place it can appear in the cache, leading to Conflict Miss
• Fully Associative Mapped: any block of main memory can be placed anywhere in the cache
• Set Associative Mapped: allows placement of a block in a set of places in the cache

Memory Hierarchy Designer’s Concerns

Four key concerns for memory hierarchy designers:

1. Block placement: Where can a block be placed in the upper level?
2. Block identification: How is a block found if it is in the upper level?
3. Block replacement: Which block should be replaced on a miss?
4. Write strategy: What happens on a write?

Block Placement Policy

• Fully Associative: Block can be placed anywhere in the upper level (Cache). Example: Block 12 from main memory can be placed at block 2, 6 or any of the 8 block locations in cache.

• Set Associative: Block can be placed anywhere in a set in upper level (cache). The set number is given by: (Block No) MOD (number of sets). Example: an 8-block, 2-way set associative mapped cache has 4 sets [0-3] each of two blocks; block 12 or 16 of main memory can go anywhere in set #0 as (12 MOD 4 = 0) and (16 MOD 4 = 0). Block 14 can be placed at any of the 2 locations in set#2 (14 MOD 4 = 2).

• Direct Mapped (1 way associative): Block can be placed at only one specific location in upper level (Cache). The location is given by: Block number MOD No. of cache blocks. Example: block 12 or block 20 can be placed at location 4 in cache having 8 blocks as (12 MOD 8 = 4).

Block Identification

A TAG is associated with each block frame giving the block address. All possible tags where a block may be placed are checked in parallel. A Valid bit is used to identify whether the block contains correct data. No need to check index or block offset.

🔑 Definition — Direct Mapped Identification: Lower Level memory of 4GB uses a 32-bit address, with fields split between tag, index, and block offset for identification purposes.

Block Replacement Policy

On a cache miss, a new block needs to be brought in. If existing block locations are filled, an existing block must be replaced based on cache mapping and replacement policy.

Three main replacement policies:

• Random: Replace any block. Simple and easiest to implement. The candidate for replacement is randomly selected. Some designers use pseudo random block numbers.

• Least Recently Used (LRU): Replace the block either never used or used long ago. Reduces chances of throwing out information that may be needed soon. Access time and number of times a block is accessed is recorded. The block replaced is one that has not been used for the longest time. Example: if blocks are accessed in sequence 0,2,3,0,4,3,0,1,8,0, the victim to replace is block 2.

• First-in, First-out (FIFO): The block first placed in the cache is thrown out first. Example: if blocks are accessed in sequence 2,3,4,5,3,4, then to bring in a new block, block 2 will be thrown out as it is the oldest accessed block. FIFO is used as approximation to LRU as LRU can be complicated to calculate.

📌 Conclusion - Miss Rate Comparison Table:

💡 Why this matters: For larger caches (256 KB), LRU and Random perform similarly, but for smaller caches (16 KB), LRU provides better miss rates, making it the preferred choice for performance-critical systems.

Write Strategy

Memory hierarchy must not overwrite a cache block unless main memory is up to date. Multiple CPUs may have individual caches, and I/O may address main memory directly. Instruction cache accesses are read, writes are typically 10% of cache access. Data cache writes are 10%-20% of overall memory access.

• Write back: Information is written only to the block in the cache. The modified cache block is written to main memory only when it is replaced.

  • Pros: No write to lower level for repeated writes to cache; a dirty bit indicates if cache block is modified (dirty) or not modified (clean)
  • Cons: More complex replacement procedure; reduces memory-bandwidth and power requirements

• Write through: Information is written to both the block in the cache and to the block in the lower-level memory.

  • Pros: Simplifies replacement procedure; block is always clean; simplifies data-coherency
  • Cons: Higher memory traffic; always combined with write buffers so CPU doesn't wait for lower level memory

Write Buffer for Write Through

A write buffer is a FIFO with typical number of entries: 4. Once data is written into the write buffer (assuming cache hit), CPU is done with the write. The memory controller moves the write buffer's contents to real memory behind the scene. DRAM cycle time sets the upper limit on write frequency.

🔑 Definition — Write Buffer Saturation: Occurs when Store frequency approaches 1 over DRAM Write Cycle Time, i.e., CPU Cycle Time <= DRAM Write Cycle Time. In saturation, no matter how big the write buffer, it will still overflow because items are fed in faster than they can be emptied.

Two solutions to Write Buffer Saturation:

• Replace write through cache with write back cache

Write-Miss Policy

Two options for handling write-misses:

• Write Allocate: A block is allocated on a write-miss, followed by the write hit action. The rest of the block is read from memory (Byte 2, 3, ... Byte 31) after writing the tag and data.

• No-write Allocate: Write-misses do not affect the cache; the block is modified only in the lower level memory. The blocks stay out of the cache until the program tries to read them. This practice uses sub-blocking to tell the processor the rest of the block is no longer valid.

📌 Example: No write-allocate vs write allocate

Consider a fully associative write-back cache with empty entries and the following sequence:

1. Write Mem [100]
2. Write Mem [100]
3. Read Mem [200]
4. Write Mem [200]
5. Write Mem [100]

For no-write allocate:

• First write [100]: MISS (tag not in cache)
• Second write [100]: MISS
• Read [200]: MISS
• Write [200]: HIT
• Write [100]: MISS
• Result: 4 MISSes and 1 HIT

For write-allocate:

• First access to [100]: MISS
• First access to [200]: MISS
• Rest are HITS (both [100] and [200] found in cache)
• Result: 2 MISSes and 3 HITs

Conclusion:

• Write-back caches normally use write-allocate, hoping subsequent writes to the block will be captured by the cache
• Write-through caches often use No Write Allocate, because even if subsequent writes occur, they must go to lower level memory

⭐ Key Takeaways

This lecture establishes that cache design involves four critical decisions: block placement (determining where blocks go), block identification (using tags and valid bits), replacement policy (LRU generally outperforms Random for smaller caches but performs similarly for larger ones), and write strategy (write-back with dirty bits reduces memory traffic while write-through simplifies coherency). Write buffer management is crucial to prevent saturation, especially when CPU cycle time approaches DRAM write cycle time. For write-miss policies, write-back caches typically use write-allocate while write-through caches prefer no-write allocate, and these choices significantly impact hit/miss ratios as demonstrated by the example showing 4 misses vs 2 misses for the same access sequence.

🧠 Quick Revision Questions

1. What are the four main concerns of a memory hierarchy designer when designing cache?
2. How does LRU replacement policy differ from FIFO, and why is LRU generally preferred for smaller caches?
3. What is the key difference between write-back and write-through strategies, and what advantage does each provide?
4. What is write buffer saturation, and what are the two solutions to address it?
5. In the example comparing no-write allocate versus write allocate for a sequence of five memory operations, why does write-allocate result in fewer misses (2 vs 4)?

📘 Lecture 29 — Memory Hierarchy Design

Cache Performance Enhancement by: Reducing Cache Miss Penalty

📖 Overview: This lecture focuses on techniques to reduce the cache miss penalty, a critical factor in improving overall CPU performance. Starting with a recap of cache design fundamentals, it explores five key methods: multilevel caches, critical word first/early restart, priority to read misses, merging write buffers, and victim caches. These strategies aim to minimize the time penalty incurred when a cache miss occurs, directly impacting the average memory access time and CPU execution time.

🗂️ Topics Covered

Recap of cache design concepts including block placement, identification, replacement, and write strategies, along with write buffer and write miss policies. The lecture then derives CPU performance impact using miss rate and miss penalty, introduces the average memory access time formula, and details five specific techniques for reducing miss penalty: multilevel caches, critical word first and early restart, priority to read misses over write misses, merging write buffers, and victim caches.

📝 Lecture Summary

Recap: Memory Hierarchy Designer’s Concerns

The designer must consider four key concerns for the memory hierarchy. Block placement determines where a block can be placed in the upper level. Block identification determines how a block is found if it is in the upper level. Block replacement decides which block should be replaced on a miss. Write strategy governs what happens on a write.

Recap: Write Buffer for Write Through

Cache write strategies include write back and write through. A write-buffer is used in write through to hold data waiting to be written to memory, allowing the processor to continue. A level-2 cache can be introduced between the L1 cache and DRAM. Two write miss policies are Write Allocate, where a block is allocated in the cache on a write miss, and No-Write Allocate, where the block stays out of the cache until the program tries to read it.

🔑 Definition — Write Allocate: A block is allocated in the cache on a write miss, i.e., the block to be written is available in the cache. 🔑 Definition — No-Write Allocate: The blocks stay out of the cache until the program tries to read the blocks; i.e., the block is modified only in the lower level memory.

Impact of Caches on CPU Performance

The CPU execution time is given by: 📐 Formula: CPU Execution Time = (CPU Execution clock cycles + Memory Stall cycles) x Clock Cycle Time

Example:

• Assumptions: cache miss penalty = 100 clock cycles, all instructions take 1 clock cycle, average miss rate = 2%, average memory references per instruction = 1.5, average number of cache misses per 1000 instructions = 30.
• Find the impact of cache on CPU performance considering both misses per instruction and miss rate.

📌 Solution (misses per instruction): CPU Time = IC x (1.0 + (30/1000 x 100)) x clock cycle time = IC x 4.00 x clock cycle time

📌 Solution (miss rate): CPU Time = IC x (1.0 + (1.5 x 2% x 100)) x clock cycle time = IC x 4.00 x clock cycle time

Cache Performance (Review)

Memory stall clock cycles are the sum of:

• IC x Reads per instruction x Read miss rate x Read Miss Penalty
• IC x Writes per instruction x Write Miss Rate x Write Miss Penalty

By averaging read and write miss rates: 📐 Memory stall clock cycles = Number of memory accesses x Miss rate x Miss penalty

📐 Average Memory Access Time = Hit Time + Miss rate x Miss penalty 💡 Why this matters: The average memory access time is an indirect measure of CPU performance and is not a substitute for execution time. However, this formula can decide about split caches (instruction and data) vs. unified caches.

Example: Split vs. Unified Caches

• Statement: Consider a 32KB unified cache with misses per 1000 instructions = 43.3, and 16KB instruction/data split caches with instruction misses per 1000 = 3.82 and data misses per 1000 = 40.9. Assume 36% of instructions are data transfer, 74% of memory references are instruction references, hit takes 1 clock cycle, miss penalty = 100 cycles, and a load/store takes one extra cycle on unified cache. Find the average memory access time for each case (write-through with write-buffer, ignoring write buffer stalls).

📌 Solution:

1. Miss Rate = (Misses/1000) / (Accesses/instruction)

   • Miss Rate₁₆KB Inst = (3.82/1000) / 1.0 = 0.0038
   • Miss Rate₁₆KB data = (40.9/1000) / 0.36 = 0.114
   • Overall miss rate for split caches = (74% x 0.0038) + (26% x 0.114) = 0.0324
   • Miss Rate₃₂KB unified = (43.3/1000) / (1+0.36) = 0.0318

2. Average Memory Access Time = %inst x (Hit time + Inst. Miss rate x miss penalty) + %data x (Hit time + data Miss rate x miss penalty)

   • Average Memory Access Time_split = 74% x (1 + 0.0038 x 100) + 26% x (1 + 0.114 x 100) = 4.24
   • Average Memory Access Time_unified = 74% x (1 + 0.0318 x 100) + 26% x (1+1+0.0318 x 100) = 4.44
   • Result: Split caches have slightly better average access time (4.24 vs. 4.44) and avoid structural hazards, even though the unified cache has a slightly lower miss rate.

Improving Cache Performance

The average memory access time formula provides a framework to optimize cache performance: Average Memory Access Time = Hit Time + Miss Rate x Miss Penalty. Four general options exist: 1) Reduce the miss penalty, 2) Reduce the miss rate, 3) Reduce miss penalty or miss rate via parallelism, and 4) Reduce the time to hit in the cache.

Reducing Miss Penalty

Five techniques are covered: 1) Multilevel Caches, 2) Critical Word First and Early Restart, 3) Priority to Read Misses Over Write Misses, 4) Merging Write Buffers, and 5) Victim Caches.

1: Multilevel Caches

This technique ignores the CPU but concentrates on the interface between cache and main memory. Multiple levels of caches create a tradeoff between cache size (effectiveness) and cost (access time), with a small fastest memory used as level-1 cache.

Performance Analysis: 📐 Average Access Time = Hit TimeL1 + Miss RateL1 x Miss PenaltyL1 Where, Miss PenaltyL1 = Hit TimeL2 + Miss RateL2 x Miss PenaltyL2

📐 Average memory access time = Hit TimeL1 + Miss RateL1 x (Hit TimeL2 + Miss RateL2 x Miss PenaltyL2)

📐 Stall per instruction_average = Misses per instructionL1 x Hit TimeL2 + Misses per instructionL2 x Miss PenaltyL2

🔑 Definition — Local Miss Rate: Measure of misses in a cache divided by the total number of misses in this cache. 🔑 Definition — Global Miss Rate: Measure of the number of misses in the cache divided by the total number of memory accesses generated by the CPU. For L1: Miss RateL1. For L2: Miss RateL1 x Miss RateL2.

Example:

• Given: For 1000 references with 40 misses in L1 and 20 in L2. Miss penalty for L2 cache-memory = 100 clock cycles, hit time for L2 = 10 clock cycles, hit time for L1 = 1 clock cycle, memory references per instruction = 1.5.

📌 Solution:

• L1 cache miss rate = 4% (40/1000 x 100)
• Local Miss Rate for L2 = 50% (20/40)
• Global Miss Rate for L2 = 2% (20/1000 x 100)
• Average Memory Access Time = 1 + 4% x (10 + 50% x 100) = 1 + 0.04 x (10 + 50) = 1 + 2.4 = 3.4 cycles
• Misses per instruction for L1 = 40 x 1.5 = 60 per 1000 instructions
• Misses per instruction for L2 = 20 x 1.5 = 30 per 1000 instructions
• Average Memory Stalls per instruction = (60/1000) x 10 + (30/1000) x 100 = 0.6 + 3.0 = 3.6 clock cycles
• Result: The average miss penalty using multilevel caches reduces by a factor of 100 / 3.6 ≈ 28 relative to the single level cache.

2: Critical Word First and Early Restart

Don‘t wait for the full block to be loaded before restarting the CPU. The CPU normally needs one word of a block at a time.

🔑 Definition — Early Restart: Request the words in a block in normal order. As soon as the requested word of the block arrives, send it to the CPU and let the CPU continue execution. 🔑 Definition — Critical Word First: Request the missed word from memory first; the memory sends it to the CPU as soon as it arrives. The CPU continues filling the rest of the words in the block afterward.

Example:

• A computer uses 64-byte (8 word) cache blocks. An L2 cache takes 11 clock cycles to get the first 8-byte (critical word) and then 2 clock cycles per 8-byte word for the rest of the block (2 issues per cycle). Compare:
  1. With critical word first (assuming no other access to the rest of the block)
  2. Without critical word first (assuming instructions read data sequentially 8-byte words at a time from the rest of the block, requiring a block load)

📌 Solution:

1. With Critical Word First: Average miss penalty = Miss Penalty of critical word + Miss penalty of remaining words = 11 x 1 + (8-1) x 2 = 11 + 14 = 25 clock cycles
2. Without Critical Word First: Average miss penalty = [Miss Penalty of first word + miss penalty of remaining words] + clock cycles to issue the load = [11 x 1 + (8-1) x 2] + 8/4 = 25 + 4 = 29 clock cycles (8 issues / 2 issues per cycle = 4 cycles)

Merit: This technique doesn‘t require extra hardware. Drawback: It is generally useful only in large blocks; programs exhibiting spatial locality may face a problem accessing data or instructions from memory if the next miss is to the remainder of the block.

3: Priority to Read Miss over the Write Misses

This technique reduces the average miss penalty by considering the overlap between the CPU and cache miss penalty. Write-buffers ensure that writes to memory do not stall the processor. However, a write-buffer may hold the updated value of a location needed on a read miss, and the processor is blocked until the read returns. Write buffers complicate memory access.

🔑 Definition — Raw Data Hazard (RAW): A situation where a read after a write to the same location may get the old value if the write has not completed.

Example Program Segment:

SW R3, 512(R0) ; M[512] ← R3 (Cache index 0)
LW R1, 1024(R0) ; R1 ← M[1024] (Cache index 0)
LW R2, 512(R0) ; R2 ← M[512] (Cache index 0)

Assume a direct-mapped, write-through cache that maps 512 and 1024 to the same block, and a 4-word write buffer. Find if the value in R2 will always equal the value in R3.

📌 Analysis: The data in R3 is placed in the write-buffer after the first instruction. The second load (to 1024) is a miss. The third load (to 512) also results in a miss. If the write buffer hasn‘t completed writing to location 512 in memory, the read of location 512 will put the old value into the cache and then into R2. Thus, R3 would not equal R2.

Solution: Give priority to read misses. This can be done by either waiting for the write buffer to empty, or by checking write buffer contents on a read miss. If there are no conflicts and the memory system is available, let the memory access continue for the read. By giving priority to read misses, the cost (penalty) of writes can be reduced. In write-back caches, a better alternative to writing a dirty block to memory before a read is to copy the dirty block to a write-buffer, then do the read, then do the write. The CPU stalls less since it restarts as soon as the read is done.

4: Merging Write Buffer

Write-through caches rely on write-buffers as all stores must be sent to the lower level. Even write-back caches use a simple buffer when a block is replaced. A small write-buffer may end up stalling the processor if it fills up. This is resolved by merging cache-block entries in the write buffer. Multiword writes are faster than writes performed one at a time. If a write buffer already contains some words from a given data block, the current modified word can be merged with the block parts already in the buffer.

🔑 Definition — Write Merge: If the buffer contains other modified blocks, the address is checked to see if the address of the new data matches the address of a valid write buffer entry. If so, the new data are combined with the existing entry.

💡 Why this matters: This technique reduces the number of stalls due to the write-buffer being full, thereby reducing the miss penalty through improvement in the efficiency of the write-buffer.

5: Victim Caches

Another way to reduce the miss penalty is to remember what was discarded, as it may be needed again. The victim cache contains only discarded blocks because of some earlier miss. On another miss, the victim cache is checked to see if it has the desired data before going to the next lower-level memory. If the desired data is found, the victim block and cache block are swapped. This recycling requires a small fully associative cache between a cache and its refill path, called the victim cache.

⭐ Key Takeaways

The first and most important technique to reduce miss penalty is the use of multilevel caches, which can dramatically reduce the effective miss penalty by a factor proportional to the product of local miss rates. The Critical Word First and Early Restart technique reduces the penalty by not waiting for the entire block to load before restarting the CPU. Giving priority to read misses over write misses avoids RAW hazards and reduces stalls in both write-through and write-back caches. Merging write buffers improves efficiency by combining multiple writes to the same block, reducing the number of stalls. Finally, victim caches provide a small, fast buffer for recently evicted blocks, reducing the penalty for blocks that are quickly re-referenced. All these methods aim to optimize the average memory access time by directly reducing the miss penalty component of the formula: Average Memory Access Time = Hit Time + Miss Rate x Miss Penalty.

🧠 Quick Revision Questions

1. What is the formula for CPU Execution Time, and how does the cache miss penalty affect it?
2. Explain the difference between local and global miss rates in a multilevel cache hierarchy, and calculate them for a system with 50 L1 misses and 10 L2 misses out of 1000 memory accesses.
3. How does the "Critical Word First" technique reduce the average miss penalty, and what is a potential drawback of this technique?
4. Describe the RAW data hazard in a write-through cache with a write buffer. How does giving priority to read misses resolve this hazard?
5. What is a victim cache, and how does it reduce the miss penalty compared to directly accessing the next level of memory?

📘 Lecture 30 — Memory Hierarchy Design Cache Performance Enhancement (Reducing Miss Rate)

📖 Overview: This lecture focuses on reducing cache miss rate as a key strategy for improving cache performance. It classifies the three types of cache misses and presents five hardware and software techniques to minimize them, including larger block sizes, larger caches, higher associativity, way prediction, and compiler optimizations.

🗂️ Topics Covered

The lecture begins with a recap of reducing miss penalty through multilevel caches, critical word first, priority to read misses, merging write buffers, and victim caches. It then introduces the three C’s classification of cache misses: compulsory, capacity, and conflict misses. The main focus is on five techniques for reducing miss rate: larger block size, larger cache size, higher associativity, way prediction and pseudo-associativity, and compiler optimization including loop interchange and blocking. A final example compares average memory access time across different associativity levels.

📝 Lecture Summary

Recap: Improving Cache Performance

Cache performance can be improved by addressing miss penalty, miss rate, parallelism, or hit time. The miss penalty can be reduced through several techniques: Multilevel Caches (more cache levels reduce penalty), Critical Word First and Early Restart (request the needed word first), Priority to Read Misses Over Writes (read misses get higher priority), Merging Write Buffers (combining writes to same block), and Victim Caches (small fully-associative cache to hold evicted blocks).

Cache Misses

Cache misses are classified into three types:

• Compulsory Misses (cold start or first reference misses): occur when a block is first accessed and must be brought into the cache
• Capacity Misses: occur in a fully associative cache when the working set exceeds cache size
• Conflict Misses (collision or interference misses): occur when multiple blocks map to the same cache set or address

💡 Why this matters: Understanding miss classification helps target the right technique for each type.

1: Larger Block Size

Larger blocks reduce miss rate by exploiting spatial locality — larger blocks bring more data or instructions per access. However, in small caches, larger blocks may increase miss rate due to fewer total blocks available.

🔑 Definition — Miss Penalty: the time to fetch a block from lower memory levels 📐 Formula: Average Memory Access Time = Hit time + Miss Rate × Miss Penalty 📌 Example: With 80 clock cycles overhead, 16 bytes every 2 clock cycles delivery, hit time = 1 clock cycle

• For a 4KB cache, miss rate = 7.24%
• Miss penalty = 80 + 4 = 84 clocks (80 overhead + 4 for 16 bytes/2 cycles = 8 cycles, wait — correction: 80 + 4? Actually the text says: Miss penalty = 80 + 4 = 84 clocks)
• Average Memory Access Time = 1 + (7.25% × 84) = 7.082 Clock cycles
• Larger blocks exploit high latency and high bandwidth of lower level memory

2: Large Cache Size

Larger caches reduce capacity misses. By 2001, processors used 2nd-level and 3rd-level caches. Drawbacks include longer hit time and higher cost (access time increases with cache size).

3: Higher Associativity

Higher associativity reduces conflict misses but increases hit time. The cache cycle time (CCT) ratios relative to direct-mapped (1-way):

• CCT 2way = 1.36 × CCT 1way
• CCT 4way = 1.44 × CCT 1way
• CCT 8way = 1.56 × CCT 1way

4: Way Prediction and Pseudo-associativity

This technique combines the fast hit time of direct-mapped caches with the lower conflict misses of set-associative caches.

Way Prediction predicts which block in a set will be accessed. Steps:

1. Extra bits — 2-way prediction or 4-way prediction
2. Multiplexer — single tag check

Other blocks are checked for matches in subsequent clock cycles. The Alpha 21264 uses this with 1 clock cycle latency and 3 clock cycles for miss handling.

Pseudo-associative (column associative) caches — on a miss, the cache checks a "pseudo-set" to find the block. Performance involves a "slower hit" when the prediction is wrong.

5: Compiler Optimization

Compiler optimizations reduce both data and instruction cache misses.

Instruction cache optimization:

• Code reordering — determines conflicts between procedures
• Code-line alignment — decreases cache miss by ensuring entry points align with cache block boundaries

Data cache optimization:

• Improves spatial locality and temporal locality
• Array calculations — using loop interchange and blocking

📌 Example — Loop Interchange: The first version accesses data non-sequentially for j (0→100) and sequentially for i (0→5000):

/* First Version */
for (k = 0; k < 100; k = k+1)
  for (j = 0; j < 100; j = j+1)
    for (i = 0; i < 5000; i = i+1)
      x[i][j] = 2 * x[i][j];

Reordered version swaps j and i loops to access memory sequentially:

/* Reordered version */
for (k = 0; k < 100; k = k+1)
  for (i = 0; i < 5000; i = i+1)
    for (j = 0; j < 100; j = j+1)
      x[i][j] = 2 * x[i][j];

📌 Example — Blocking for Matrix Multiplication: Blocking improves temporal locality. The example uses row-major order and column-major order for matrix multiplication:

/* Initial version of matrix multiplication code */
for (i = 0; i < N; i = i+1)
  for (j = 0; j < N; j = j+1)
  {r = 0;
  for (k = 0; k < N; k = k+1) {
    r = r + y[i][k]*z[k][j]; };
  x[i][j] = r;
  };

⭐ Key Takeaways

The most critical points for exam understanding: (1) Cache misses are classified into three types — compulsory, capacity, and conflict — each requiring different reduction strategies. (2) Larger block sizes reduce compulsory misses but can increase miss rate in small caches; larger caches reduce capacity misses but increase hit time. (3) Higher associativity reduces conflict misses but increases cache cycle time, with ratios of 1.36x for 2-way to 1.56x for 8-way relative to direct-mapped. (4) Way prediction techniques check a section of cache first (for fast hit) then fall back to checking the rest on a miss, balancing speed and miss rate. (5) Compiler optimizations like loop interchange and blocking are software approaches that improve spatial and temporal locality without hardware changes.

🧠 Quick Revision Questions

1. What are the three types of cache misses (the "Three C's") and what causes each?
2. Calculate the average memory access time for a 4KB cache with 7.24% miss rate, 80 clock overhead, 16 bytes/2 cycles delivery, and 1 clock hit time.
3. What is the cache cycle time (CCT) ratio for an 8-way set-associative cache compared to direct-mapped?
4. How does way prediction differ from pseudo-associativity in handling cache accesses?
5. Explain how loop interchange reduces cache misses in nested loops that access a 2D array non-sequentially.

📘 Lecture 31 — Memory Hierarchy Design

📖 Overview: This lecture explores advanced cache performance enhancement techniques focused on reducing miss penalty and miss rate through parallelism, as well as reducing hit time. Building on earlier concepts of the 3C model, it introduces non-blocking caches, hardware and software prefetching, and practical methods to minimize the time to access the cache, all crucial for modern high-performance processors.

🗂️ Topics Covered

The lecture begins with a recap of reducing miss rate using the 3C model (compulsory, capacity, conflict misses). It then introduces parallelism-based techniques: non-blocking caches (hit under miss/multiple misses), hardware prefetching with stream buffers (including a detailed UltraSPARC III example), and compiler-controlled prefetching (register and cache variants). Finally, it covers four techniques to reduce hit time: small and simple caches, avoiding address translation during indexing (virtual caches), pipelined cache access, and trace caches, concluding with a comprehensive summary table of cache optimization techniques.

📝 Lecture Summary

Recap: 3 C Model and Reducing Miss Rate

• Large block size reduces compulsory misses.
• Large cache size reduces capacity misses.
• Higher associativity reduces conflict misses.
• Way-prediction checks a section of cache for hit first; on miss, it checks the rest.
• Compiler-based techniques include loop interchange and blocking to optimize cache performance.
• Today's focus is on other enhancement methods: 1. Reducing Miss Penalty or Miss Rate via parallelism – overlapping execution of instructions with memory hierarchy activities. 2. Reducing the hit time.

Reducing Miss Penalty or Rate via Parallelism

• The basic idea is to reduce miss penalty or miss rate by performing multiple outstanding memory operations through overlapping memory activities and instruction execution activities in the processor.
• This can be accomplished using three techniques:
  1. Non-blocking Caches: reduces stall on misses.
  2. Hardware Prefetch: reduces number of misses.
  3. Software (compiler controlled) Prefetch: reduces number of misses.

Non-blocking Caches

• Memory hierarchy involves decoupled instruction and data caches in an out-of-order execution CPU.
• Non-blocking or lockup-free caches allow the processor to continue during a miss.
• Key concepts include "hit under miss", "hit under multiple miss", and "miss under miss".
• Complexity: For example, a miss to address 1000 and later a miss to address 1032; the complexity of the cache controller increases.
• The memory system can service multiple misses.
• Example processor: Pentium Pro.

Hardware Prefetch: Reduces Misses

• Prefetches 2 blocks: the requested block and the next sequential block.
• Uses a "stream buffer" : if the next requested block is already available in the stream buffer:
  1. Original cache request is cancelled.
  2. Block is read from the stream buffer.
  3. Next prefetch request is issued.
• Reduces "demand misses" .
• Jouppi in 1990 found: 15% - 25% of misses reduced with 1 block stream buffer; 4 blocks stream buffer achieved 43% for stream fetching; 50% at the same address; 16-block stream buffer achieved 72% miss reduction.
• Works efficiently for data caches.
• Hardware identifies the stream of accesses.
• Palacharla & Kessler in 1994: using 8 stream buffers achieved 50% to 70% miss reduction for 64KB, 4-way set associative caches.

📌 Example: For UltraSPARC III, 64 KB data cache and 256 KB cache have average misses per 1000 instructions of 36.9 and 326 respectively, assuming:

1. prefetching hit rate equals 20%
2. hit time is 1 clock cycle
3. miss penalty is 15 cycles
4. 1 extra clock cycle if data misses the cache but found in prefetch buffer
5. data references equal 22%

Solution:

1. Miss rate_prefetch = [Misses/1000] / data references = [36.9 / 1000] / [22 / 100] = 36.9 / 220 = 16.7%

2. Average memory access time_prefetch = Hit Time + Miss rate × Prefetch hit time × 1 + Miss rate × (1 - prefetch hit time) × miss penalty Average memory access time_prefetch = 1 + (16.7% × 20% × 1) + (16.7% × (1-20%) × 15) = 3.046

a) Effective Miss rate_prefetched 64K = [Average memory access time – Hit time] / Miss Penalty = [3.064 – 1] / [15] = 2.064 / 15 = 13.6%

b) From the given data, 256KB data cache yields miss rate: Miss rate_256KB = 33.6 / (22% × 1000) = 14.8%

Software (Compiler Controlled) Prefetch:

• Two variants of prefetch:

  • Register Prefetch: Load data into register (HP RISC).
  • Cache Prefetch: Load data only into cache, not the register (MIPS IV, PowerPC, SPARC v.9).

• Issues and limitations of compiler prefetching:

  1. Faulting prefetch vs. Non-faulting prefetch.
  2. Compiler prefetching is semantically invisible; it cannot cause virtual memory faults.
  3. Caches do not stall.
  4. Overhead of issuing the prefetch instructions.

Summary: Reducing Cache Miss Penalty or Miss Rate via Parallelism

• The non-blocking caches.
• Bandwidth behind the cache and Instruction-level parallelism.
• Hardware and Software prefetching.

Final Component to Reduce Average Memory Access Time - Hit Time

• Five techniques to reduce the miss penalty.
• Five methods to reduce the miss rate.
• Three approaches to reduce the miss penalty and miss rate in parallel to reduce the average memory access time.
• Hit time is the final component to optimize.

Reducing Hit Time

1. Clock rate of the processor.
2. Cache Access time.

The four commonly used techniques:

1. Small and Simple Caches
2. Avoiding Address Translation during Indexing
3. Pipelined Cache Access
4. Trace Cache

Small and Simple Caches

• The most time-consuming operation in a cache hit is comparing the long address tag.
• This operation requires a bigger circuit which is always slower compared to smaller circuits.
• An obvious approach to keep hit time small is to keep the cache smaller and simpler.
• The cache should be kept small to fit on the same chip as the processor to avoid off-chip time penalty; and simpler, such as direct-mapped, where tag comparison can be overlapped with data transmission.
• The impact of cache size and complexity (associativity and number of read/write ports) is significant.
• Size of L1 caches: 16KB L1 cache on Pentium III, 8KB on Pentium IV.

Avoiding Address Translation during Indexing

• For a small and simple cache, Translation Look-aside Buffer (TLB) is used. The virtual address from the CPU goes through the virtual memory system.
• Two levels of address mapping: address from virtual memory to main memory, and main memory to cache.
• Using a virtual address for the cache allows directly mapped access.
• Virtual caches vs. Physical cache: the virtual address translation step is eliminated from cache hit time (Amdahl's rule).
• Limitation of virtually addressed caches: issues include protection, page address, physical address difference (a virtual address may refer to different physical addresses), and aliasing/synonyms (two different virtual addresses or two processes pointing to the same physical address).
• Hardware solution to synonyms: 2-way set associative cache.
• Software solution: share some address bits.

Pipelined Cache Access

• Cache hit time can be improved by pipelining the cache access.
• This increases the latency of the first level cache-hit but enables a faster cycle time which increases the bandwidth of instructions.
• Example: Pentium I takes 1 clock cycle to access the instruction cache; Pentium Pro through Pentium II takes 2 clock cycles; Pentium IV takes 4 clock cycles.

Trace Caches

• For multiple-issue processors, trace caches store the dynamic sequence of instructions.
• Instructions are loaded into the cache block based on branch prediction and instruction prefetching.
• Advantages: No wasted words and no conflicts; conflicts are avoided.
• Demerit: Complicates the address mapping because blocks are no longer aligned to power-of-2 multiples of words. Requires a more complex address mapping.
• Disadvantage: The same instruction may be stored multiple times.

Summary – Cache Optimization

• 5 methods to reduce the miss penalty.
• 7 ways to reduce 3Cs (compulsory, capacity, conflict misses).
• 3 methods for reducing miss rate and miss penalty via parallelism.
• 4 techniques to reduce hit time.

Table 1: Cache Optimization Techniques – Miss Penalty, Miss Rate, and Hit Time

Table 2: Cache Optimization Techniques – Parallelism and Hit Time

⭐ Key Takeaways

This lecture presents a comprehensive toolkit for improving cache performance. The primary strategies target three key metrics: miss penalty, miss rate, and hit time. To reduce miss penalty and miss rate through parallelism, the core techniques are non-blocking caches (allowing hits/misses under outstanding misses), hardware prefetching (using stream buffers to anticipate data needs and reduce demand misses), and compiler-controlled prefetching (inserting explicit prefetch instructions). To reduce hit time, the essential approaches are keeping caches small and simple (to minimize tag comparison time), using virtual addresses to avoid costly TLB translation during indexing, pipelining cache access (to support higher clock frequencies), and employing trace caches (to store dynamic instruction sequences and improve instruction fetch bandwidth in wide-issue processors). The final summary tables categorize all optimization techniques by their impact on miss penalty, miss rate, and hit time, along with their complexity, providing a clear decision framework for architects.

🧠 Quick Revision Questions

1. What is the fundamental difference between "hit under miss" and "hit under multiple miss" in a non-blocking cache?
2. In hardware prefetching with a stream buffer, what three steps are taken if a requested block is found in the buffer?
3. For the UltraSPARC III example, calculate the effective miss rate for a 64KB cache with prefetching, given the average memory access time is 3.046 cycles, hit time is 1 cycle, and miss penalty is 15 cycles.
4. What are the two main issues that arise when using virtually addressed caches, and what is the hardware solution for one of them?
5. How does pipelining cache access improve performance even though it increases the latency of the first-level cache hit?

📘 Lecture 32 — Memory Hierarchy Design (Main and Virtual Memories)

📖 Overview: This lecture completes the memory hierarchy discussion by examining main memory and virtual memory performance. It explains how DRAM organization impacts memory bandwidth, introduces techniques for improving main memory performance, and contrasts virtual memory with cache memory. Understanding these concepts is critical for designing systems that balance speed, cost, and capacity across the memory hierarchy.

🗂️ Topics Covered

The lecture recaps cache design and performance metrics, then dives into main memory organization and DRAM types (Fast Page Mode, SDRAM, DDR). It presents three techniques for improving main memory performance: wider main memory, interleaved memory, and independent memory banks, with detailed bandwidth calculations. The final sections introduce virtual memory concepts, protection, relocation, page faults, and compare virtual memory design issues with cache memory.

📝 Lecture Summary

Recap: Memory Hierarchy

The design goal of a memory system is to achieve the low cost of the cheapest memory combined with the fast speed of the fastest memory. The fastest, smallest, and most costly memories sit at the top, while the slowest, biggest, and cheapest memories sit at the bottom. Key parameters are average access speed, cost, and the cheapest technology available. Semiconductor memories include Static and Dynamic RAMs, which occupy the upper levels of the memory hierarchy.

💡 Why this matters: This hierarchy concept explains why computers use multiple memory types rather than relying on a single technology.

Recap: Caches Design

Caches use Static Random Access Memory (SRAM) , while Main Memory is Dynamic Random Access Memory (DRAM) (with access time ~8 ms, occurring <5% of the time). The magnetic, optical, or other media form the lower levels (e.g., disk). Virtual memory extends this hierarchy further. Cache and main memory are organized in equal sized blocks. Word transfer is fast for data requested by the CPU, while block transfer moves larger chunks between levels.

Recap: Cache Performance

If misses occur, the miss penalty (time to fetch a block from lower level) becomes critical. Cache design and performance depend on techniques that optimize miss rate, miss penalty, and hit time.

Main Memory Organization

Main memory serves as the source for caches (providing data on cache misses) and the destination for virtual memory (holding pages from disk). The DRAM logical organization (4 M Bit) consists of a memory array arranged in rows and columns, controlled by RAS (Row Address Strobe) and CAS (Column Address Strobe).

Main Memory Performance

Performance of DRAM is characterized by three types:

1. Fast page mode DRAM – Optimizes sequential access by keeping the row address constant while changing column addresses.
2. Synchronous DRAM (SDRAM) – Avoids handshaking by using a clock to synchronize operations.
3. Double Data Rate (DDR) DRAM – Transmits data on both rising and falling clock edges.

Key performance metrics are Latency (average memory access time) and Bandwidth (number of bytes read/write per unit time). These depend on Access Time and Cycle Time. Inputs/outputs and multiprocessors require higher bandwidth; low-latency memory helps single-thread performance. Multiprocessors demand higher bandwidth, often using 2nd level caches with larger block size to reduce the effective miss penalty.

Improving Main Memory Performance

The most commonly used techniques are: ✓ Wider Main Memory ✓ Simple Interleaved Memory ✓ Independent Memory Banks

1: Wider Main Memory — Example

Consider a 4-word block (i.e., 32 bytes). Timing parameters:

• Time to send address = 4 clock cycles
• Time to send the data word = 4 clock cycles
• Access time per word = 56 clock cycles

Miss Penalty Formula: No. of words × [time to: send address + send data word + access word]

For 1-word organization: Miss Penalty = 4 × (4 + 4 + 56) = 4 × (64) = 256 Clock Cycles

Memory bandwidth = bytes/clock cycle = 32/256 = 1/8 byte/cycle (0.125)

For 4-word organization: Miss Penalty = 1 × (4 + 4 + 56) = 64 Clock Cycles

Memory bandwidth = 32/64 = 1/2 bytes/cycle (0.5)

💡 Why this matters: Wider memory delivers 4× the bandwidth by transferring the entire block in a single access, dramatically reducing miss penalty.

2: Interleaved Memory

Memory is divided into banks based on address:

• bank 0 has all words whose Address MOD 4 = 0
• bank 1 has all words whose Address MOD 4 = 1
• bank 2 has all words whose Address MOD 4 = 2
• bank 3 has all words whose Address MOD 4 = 3

Bandwidth Calculation Example: Using the same timing model, the miss penalty for 4-word interleaved memory is: = time to send address + time to access + number of banks × time to send data = 4 + 56 + 4 × 4 = 76 clock cycles

Bandwidth = 32/76 = 0.4 byte per clock cycle

Compare to 1-word organization: Bandwidth = 32/256 = 1/8 = 0.125 byte per clock cycle

💡 Why this matters: Interleaving achieves 3.2× bandwidth improvement over the 1-word organization by overlapping accesses across banks.

3: Independent Memory Banks

Memory banks offer independent accesses, allowing simultaneous operations in:

• Multiprocessors (each processor can access a different bank)
• I/O (input/output devices can use separate banks)
• CPU with Hit under n Misses (the CPU can continue processing hits while servicing a miss)
• Non-blocking Caches (cache continues to serve hits during a miss)

An input device may use one controller and one bank, the cache read may use another bank, and the cache write still another bank.

Summary: Main Memory Bandwidth

Three approaches can be combined:

• Using memory banks
• Making memory and its bus wider
• Doing both (wider memory with banks)

How many banks should there be? This decision is essential to ensure that if memory is being accessed sequentially (e.g., when processing an array), by the time you try to read a second word from a bank, the first access has finished. Otherwise, it will return to the original bank before it has the next word ready.

Example with 8 banks, each 64-bit, access time 10 clock cycles:

• Clock cycle 1: Bank 0 starts access (result ready after 10 clock cycles)
• After 10 clock cycles: Bank 0 result available
• 7 banks are accessed sequentially till the 18th clock cycle
• 18th clock: Bank 0 is accessed again
• CPU cannot start fetching immediately; wait another 10 clock cycles
• Clock cycle 20: Results ready

🔑 Definition — Bank Rule: Number of banks ≥ Number of clock cycles to access a word in a bank

Virtual Memory

Multiple processes or a single process may exceed physical memory available. The increasing gap between CPU speed and memory speed, plus the high cost of main memory, leads to treating physical DRAM as a cache for the disk (a single level store or single level storage concept). A Virtual Memory System manages two levels of the memory hierarchy: main memory and secondary storage. Memory is divided into segments, named as a page (a fixed-size block of contiguous pages).

Attributes: ✓ Protection – Different processes operate in different address spaces with different permissions; they cannot access privileged information. ✓ Relocation – Simplifies loading of programs and allows placing a program anywhere in memory, managed by hardware and software.

Cache vs. Virtual Memory

• Page or segment is used for block
• Page fault or address fault is used for miss
• CPU produces virtual address
• Virtual addresses are translated to main memory or physical addresses via address translation
• Mapping of virtual address to physical address uses a page table (contains the physical address of the segment or page)
• Replacement on cache miss = page fault
• The size of processor address is independent; cache size is independent of the processor address
• Secondary storage is the lower-level backing store for main memory
• File system occupies space on secondary storage

Issues of Virtual Memory Design

• Line size: Large, since disk is better at transferring large blocks
• Associativity: High (fully associative) to minimize miss rate
• Write Strategy: Write through or write back
• Miss rate: Extremely low (<< 1%)
• Hit time: Must match cache/main memory performance
• Miss latency: Very high (~20 ms)
• Tag storage overhead: Low, relative to block size

Typical System with Virtual Memory

The CPU generates the Virtual Address. The operating system manages a lookup table that records the location of the page or segment, translating virtual addresses to physical addresses.

Page Faults (like “Cache Misses”)

A page fault indicates the virtual address is not in memory. The OS exception handler is invoked. The current process suspends while the OS fetches the page from disk. The OS has full control over placement of pages in memory.

💡 Why this matters: A page fault costs ~20 milliseconds (millions of clock cycles) compared to a cache miss which costs tens of cycles — this huge penalty drives the design decisions for virtual memory (large pages, high associativity, low miss rates).

⭐ Key Takeaways

Main memory bandwidth can be improved by widening the memory bus (one wide memory fetch) or by interleaving memory across banks (parallel access to multiple narrower memories). The interleaved approach offers excellent bandwidth with standard memory chips, requiring that the number of banks at least equals the access latency to avoid stalls. Virtual memory treats DRAM as a cache for the disk, using pages as blocks, with page faults triggering OS exception handling. Unlike caches, virtual memory uses very large blocks, full associativity, and extremely low miss rates because the miss penalty is approximately 20 milliseconds. Protection and relocation are fundamental attributes of virtual memory systems, enabling multiple processes to share memory safely while allowing programs to be loaded anywhere in physical memory.

🧠 Quick Revision Questions

1. Formula: Write the miss penalty formula for a cache using a wider main memory, and calculate the penalty when transferring a 4-word block with 4-cycle address, 4-cycle data send, and 56-cycle access per word.
2. Concept: Why does interleaved memory require that the number of memory banks be at least equal to the memory access time (in clock cycles)?
3. Comparison: List three key differences between cache memory and virtual memory in terms of block size, associativity, and miss penalty.
4. Definition: What is a page fault, and what role does the operating system play when one occurs?
5. Problem: For a system with a 4-word block, compare the miss penalty and bandwidth for (a) 1-word wide memory, (b) 4-word wide memory, and (c) 4-bank interleaved memory.

📘 Lecture 33 — Memory Hierarchy Design (Virtual Memory System)

📖 Overview: This lecture completes the memory hierarchy discussion by focusing on virtual memory systems, including address translation mechanisms, page table operations, and protection schemes for multiple processes. It explains how virtual addresses are mapped to physical addresses, the role of the Translation Lookaside Buffer (TLB) for fast translation, and how memory protection is implemented to isolate processes.

🗂️ Topics Covered

The lecture covers virtual memory address translation concepts including page table operation in three steps, address translation via page tables with a simple memory system example, fast address translation using TLB with fully associative placement, an address translation example with 64-bit virtual addresses, and virtual memory protection mechanisms using base and bound registers and protection attribute bits in PTEs.

📝 Lecture Summary

Recap: Main Memory and Virtual Memory Design

The lecture begins by recapping main memory organization using banks of memory arrays called DIMMs (Dual Inline Memory Modules). Three types of DRAM are reviewed: Fast Page Mode, Synchronous DRAM (SDRAM), and Double Data Rate (DDR) DRAM, with focus on latency and bandwidth as key performance metrics. The performance concern for caches is bandwidth, especially for inputs/outputs and multiprocessors, which can be improved using Wider Main Memory, Simple Interleaved Memory, and Independent Memory Banks.

Virtual memory allows multiple processes to each have a dedicated full address space. Memory is divided into fix-sized fragments (pages) or variable-sized fragments (segments). Contiguous pages in virtual memory may be physically available on the main memory in non-contiguous locations. Virtual memory provides protection (processes cannot access each other's memory) and relocation (programs can be loaded anywhere in physical memory).

Recap: Cache vs Virtual Memory

In virtual memory, a page fault or address fault occurs when a referenced page is not in main memory. The CPU produces a virtual address which must be mapped to a physical address. Replacement strategies determine which page to evict when memory is full. The size of the processor address determines the virtual address space. Secondary storage (disk) holds pages not currently in main memory.

The page replacement strategies discussed include FIFO (First-In-First-Out), LRU (Least Recently Used), and Approximation to LRU, which uses a reference bit that is periodically reset; a page with a reference bit set indicates recent use. VM write strategies may be Write Back or Write Through, but Write Through is impossible because of: too long access to disk, the write buffer limitations, and the I/O system constraints.

💡 Why this matters: Write-back is the only practical strategy for virtual memory because writing through to disk for every write would be catastrophically slow.

Recap: Virtual Memory Operation

The CPU generates the Virtual Address, then a lookup table (page table) is consulted to find the location of the page or segment. This translates virtual addresses to physical addresses. On a page fault, the OS has full control over placement, the OS exception handler is invoked, and the current process suspends while data is brought to main memory by the OS. The contents of the page table are updated after the transfer completes.

VM Address Translation Concept

Assume Virtual Address space V comprises a set of N pages V = {0, 1, ..., N–1}, and Physical Address space P comprises a set of M pages P = {0, 1, ..., M–1} where M < N (physical memory is smaller than virtual address space).

Assuming n-bit virtual address, m-bit physical address, and p-bit page offset, the limits are:

• Virtual address limit = N = 2ⁿ
• Physical address limit = M = 2ᵐ
• Page size (bytes) = PS = 2ᵖ

The virtual address is divided into page offset (lower p bits) and page number (upper n-p bits). The page number indexes into a Page Table to find the corresponding physical page frame number.

🔑 Definition — Page Table: A data structure maintained by the OS that stores the mapping from virtual page numbers to physical page frame numbers, along with protection and status bits.

Page Table Operation: 3 Steps

The page table operates in three distinct steps:

1. Translation: Use the virtual page number to index into the page table and find the corresponding page table entry (PTE)
2. Computing Physical Address: Combine the physical page frame number from the PTE with the page offset from the virtual address to form the complete physical address
3. Checking Protection: Verify that the access type (read, write, execute) is permitted according to the protection bits in the PTE

📐 Formula: Physical Address = (Physical Page Frame Number × Page Size) + Page Offset

Simple Memory System Example

The example uses:

• 14-bit virtual addresses (16,384 byte address space)
• 12-bit physical address (4,096 byte address space)
• Page size = 64 bytes (2⁶, so 6-bit page offset)

📌 Example: With 14-bit virtual addresses and 64-byte pages:

• Virtual page number uses 14 - 6 = 8 bits (256 virtual pages)
• Page offset uses 6 bits
• With 12-bit physical addresses: physical page frame number uses 12 - 6 = 6 bits (64 physical frames)
• The page table contains 256 entries, each mapping a virtual page to a physical frame (or indicating invalid)

Fast Address Translation

The page table is large and in the main memory, causing a high miss penalty if every translation required two memory accesses: one memory access to obtain the physical address and a second to get the data. This miss penalty can be reduced using specialized hardware.

Fast Translation with a TLB

The Translation Lookaside Buffer (TLB) is a small, fast cache that stores recently used virtual-to-physical address translations. It uses fully associative placement policy and includes protection information in the TLB entries. The TLB outputs the physical address while the page offset passes through unchanged to form a full physical address.

Merits of TLB:

• Can be fully associative, set associative, or direct mapped
• Typically contains 128-256 entries
• Mid-range machines use small n-way set associative organizations for good performance with reasonable complexity

Address Translation Example

The example uses a 64-bit virtual address with:

• Physical Address: 41 bits
• TLB – direct mapped with 256 entries
• First Level Caches: direct mapped with 8KB entries, block size 64 bytes
• Second Level Cache: direct mapped 4MB direct mapped; block size 64 bytes

This example shows how virtual addresses traverse through TLB and multiple cache levels to reach main memory.

VM Protection Process

The address translation mechanism is the foundation of memory protection. Protection attribute bits in the PTE (Page Table Entry) and TLB enforce access control. If a process attempts an access it does not have permission for, an exception is raised.

The protection mechanism ensures that an address is said to be valid if Base <= address <= Bound, using Base and Bound registers to define the valid address range for a process. Multiple processes have separate page tables each pointing to distinct pages of memory, and processes are prevented from modifying these tables to maintain security.

⭐ Key Takeaways

The critical concepts from this lecture are the three-step page table operation (translation, physical address computation, protection checking) that forms the core of virtual memory address translation. The TLB is essential for performance because it eliminates the need for two memory accesses per translation, reducing the miss penalty. Protection is built into the virtual memory system through PTE protection bits and base/bound registers, ensuring that processes cannot access each other's memory space. The mathematical relationship between virtual address bits, physical address bits, and page size determines the structure of the page table and the size of the virtual and physical address spaces. Replacement strategies, particularly the distinction between FIFO and LRU (with its approximation using reference bits), determine how virtual memory systems handle page faults efficiently.

🧠 Quick Revision Questions

1. What are the three steps of page table operation during virtual address translation?
2. How does a TLB improve the performance of address translation compared to accessing the page table in main memory?
3. In a system with 14-bit virtual addresses, 12-bit physical addresses, and 64-byte pages, how many entries does the page table have?
4. Why is write-through strategy impossible for virtual memory, and what alternative is used instead?
5. How do base and bound registers work together with page tables to provide memory protection for multiple processes?

📘 Lecture 34 — Multiprocessors (Shared Memory Architectures)

📖 Overview: This lecture introduces parallel processing architectures as a means to further improve computer performance beyond instruction-level parallelism. It covers the fundamental classification of parallel computers, the distinction between centralized and distributed memory architectures for MIMD machines, and explores shared address space and message passing programming models. The lecture emphasizes performance limitations like Amdahl’s Law and communication latency.

🗂️ Topics Covered

Today's topics include a recap of ILP exploitation techniques, an introduction to parallel processing and the limitations outlined by Amdahl's Law and communication costs, Flynn's taxonomy of parallel computers (SISD, SIMD, MISD, MIMD), a detailed look at MIMD classification into centralized shared-memory (SMP/UMA) and distributed memory (NUMA) architectures, the fundamental issues of naming, synchronization, and latency/bandwidth in parallel machines, and the framework for parallel processing using shared address space and message passing models, concluding with examples of each architectural type.

📝 Lecture Summary

Recap

So far, our focus has been on studying the performance of a single instruction stream computer and methodologies to enhance its performance. We studied how Instruction Level Parallelism (ILP) is exploited among the instructions of a stream and how control, data, and memory dependencies are resolved. These characteristics are realized through pipelining the datapath, Superscalar Architecture, Very Long Instruction Word (VLIW) Architecture, and out-of-order execution.

Parallel Processing and Parallel Architecture

Further improvements in performance may be achieved by exploiting parallelism among multiple instruction streams, which uses multithreading (number of instruction streams running on one CPU) and multiprocessing (streams running on multiple CPUs where each CPU can itself be multithreaded). While evaluating performance enhancement due to parallel processing, two important challenges are the limited parallelism available in a program and the high cost of communication. These limitations make it difficult to achieve good speedup in any parallel processor. Parallel Architecture is a collection of processing elements that cooperate and communicate to solve larger problems fast. Parallel computers extend traditional computer architecture with a communication architecture to achieve synchronization between threads and consistency of data in cache.

Parallel Computers Performance: Amdahl’s Law

If a portion of the program is sequential, it limits the speedup. Amdahl's Law quantifies this limitation.

📌 Example: What fraction of original computation can be sequential to achieve speedup of 80 with 100 processors?

• Given: Target Speedup = 80, Number of Processors (Speedup of parallel part) = 100.
• Formula: Speedup = 1 / [ (Fraction_parallel / Speedup_parallel) + (1 - Fraction_parallel) ]
  • 80 = 1 / [ (Fraction_parallel / 100) + (1 - Fraction_parallel) ]
• Calculation:
  • 0.8 * Fraction_parallel + 80 * (1 - Fraction_parallel) = 1
  • 80 - 79.2 * Fraction_parallel = 1
  • Fraction_parallel = (80 - 1) / 79.2 = 0.9975
• Result: To achieve a speedup of 80 with 100 processors, only 0.25% of the computation can be sequential!

Another major challenge is the communication cost involving the latency of remote access. 📌 Example: Consider an application running on a 32-processor multiprocessor, with a 40 nsec time to handle a remote memory reference. Assume base IPC (Instructions Per Cycle) for all memory reference hits is 2 and the processor clock rate is 1GHz.

• Given: Base IPC = 2, Remote access time = 40 nsec, Clock rate = 1 GHz (1 cycle = 1 nsec). Remote access cost = 40 nsec / 1 nsec/cycle = 400 cycles.
• Formula: CPI = Base CPI + (Remote request rate x Remote access cost)
  • Base CPI = 1 / Base IPC = 1 / 2 = 0.5
• Scenario 1: 0.2% of instructions involve remote access.
  • CPI = 0.5 + (0.002 x 400 cycles) = 0.5 + 0.8 = 1.3
• Scenario 2: No remote references (all local).
  • CPI = 0.5
• Result: The multiprocessor with all local references is 1.3 / 0.5 = 2.6 times faster than one with 0.2% remote references.

Parallel Computer Categories

In 1966, Flynn proposed a categorization based on parallelism in the instruction and data streams.

1. SISD (Single Instruction Single Data): This is a Uniprocessor.
2. SIMD (Single Instruction Multiple Data): The same instruction is executed by multiple processors using different data streams. It has a single instruction memory and control processor but multiple data memories. Examples: Illiac-IV and CM-2. It offers a simple programming model, low overhead, and flexibility.
3. MISD (Multiple Instruction Single Data): Multiple processors or functional units work on a single data stream. No commercial multiprocessor of this type is available.
4. MIMD (Multiple Instruction Multiple Data): Each processor fetches its own instructions and operates on its own data. Examples: Sun Enterprise 5000, Cray T3D, SGI Origin. Its characteristics include flexibility to function as a single-user or multi-programmed multiprocessor and the use of off-the-shelf microprocessors.

MIMD and Thread Level Parallelism

MIMD machines can be used with each processor executing different processes in a multi-program environment, or multiple processors executing a single program sharing code and address space. In the latter case, these processes are referred to as threads. Threads may be large-scale independent processes or parallel iterations of loops. This parallelism is called Thread Level Parallelism.

MIMD Classification

Based on memory organization and interconnect strategy, MIMD machines are classified as:

1. Centralized Shared Memory Architecture
2. Distributed Memory Architecture

Centralized Shared-Memory

In small-level designs, processor-cache subsystems share the same physical centralized memory connected by a bus. In larger designs, the single bus is replaced with multiple buses or a switch. The key architectural property is Uniform Memory Access (UMA) , meaning the access time to all memory from all processors is the same. These multiprocessors are referred to as Symmetric (Shared Memory) Multi-Processors (SMP) .

🔑 Definition — UMA (Uniform Memory Access): A memory architecture where the access time to all memory locations is the same for all processors. 🔑 Definition — SMP (Symmetric Multi-Processor): A multiprocessor architecture based on UMA where the single main memory has a symmetric relationship to all processors.

Decentralized or Distributed Memory

This design consists of individual nodes containing a processor, some memory, I/O, and an interface to an interconnection network. It is a cost-effective way to scale memory bandwidth if most accesses are to local memory. Distributed memory provides more memory bandwidth and lower memory latency for local accesses. The disadvantage is that data communication between processors is more complex as there is no direct connection.

Parallel Architecture Issues

The fundamental issues that characterize parallel machines are: how large is the collection of processors, how powerful are they, how do they cooperate and communicate, how are data transmitted, and what is the interconnection type. These issues can be classified into three main categories:

Fundamental Issue #1: Naming Naming deals with how to solve large problems fast, what data is shared, how it is addressed, and how processes refer to each other. The segmented shared address space is named uniformly as <process number, address>. The choice of naming affects the code produced by a compiler, data replication in cache, and the global physical and virtual address space.

Fundamental Issue #2: Synchronization Processes must coordinate. In message passing, coordination is implicit with the transmission or arrival of data. In shared address space, processes must explicitly coordinate through additional operations like writing a flag, awakening a thread, or interrupting a processor.

Fundamental Issue #3: Latency and Bandwidth

• Bandwidth: High bandwidth is needed in parallel communication, but it cannot always be scaled and must match limits in network, memory, and processor. Overhead to communicate is a problem.
• Latency: It affects performance because a processor may have to wait, and it affects ease of programming because it requires more thought to overlap communication and computation.
• Latency Hiding: As latency increases the programming system burden, mechanisms are found to help hide latency. Examples include overlapping message send with computation, prefetching data, and switching to other tasks.

💡 Why this matters: A high-bandwidth, low-latency interconnect is critical for performance. The ability to hide this latency through techniques like prefetching is what allows many parallel programs to scale efficiently.

Framework for Parallel processing

The framework for parallel architecture is defined as a two-layer representation: Programming and Communication Models. These models present sharing of address space and message passing.

• Shared Address Space Model: At the communication layer, it defines communication via memory (load, store). At the programming layer, it defines handling several processors operating on several data sets simultaneously to exchange information globally.
• Message Passing Model: At the communication layer, it defines sending and receiving messages via library calls. At the programming layer, it provides a multiprogramming model to conduct jobs without I/O communication.

Shared Address Space Architecture (for Decentralized Memory Architecture)

Shared address space is referred to as Distributed Shared Memory (DSM) . Each processor can name every physical location, and each process can name all data it shares with other processes. Data transfer takes place via load and store. It often uses virtual memory to map to local or remote physical memory.

Programming Model: A process is defined as a virtual address space plus one or more threads of control. All threads share a process address space. Writes to the shared address space by one thread are visible to reads of all threads in other processes. Popular shared address space architectures include:

1. Main Frame Computers: Motivated by multiprogramming, it uses a crossbar for processor interface to memory modules. It was initially limited by processor cost, then by the cost of the crossbar (e.g., IBM S/390).
2. Minicomputers – Symmetric Multi Processors (SMP): Motivated by multiprogramming and multi-transaction processing. All components are on a shared bus (e.g., Intel Pentium Pro Quad). The bus is a bandwidth bottleneck, and caching is key to the coherence problem.
3. Dance Hall: All processors are on one side of the network, all memories on the other. It offers a scalable interconnect network where bandwidth is scalable, but has larger access latency.
4. Distributed Memory – Non-Uniform Multiprocessor Architecture (NUMA): A large-scale multiprocessor where memory is distributed with non-uniform access time (e.g., Cray T3E). Non-local references are accessed using communication requests generated by the memory controller, and directory-based cache-coherence protocols are used.

Message Passing Architecture

In this model, whole computers (CPU, memory, I/O devices) communicate as explicit I/O operations. It is essentially NUMA but integrated at the I/O devices vs. the memory system.

Programming Model: Local memory is directly accessed via private address space. Communication takes place via explicit send and receive. Send specifies a local buffer and the receiving process on a remote computer. Receive specifies the sending process on a remote computer and a local buffer to place data. Send and receive is a memory-memory copy where each supplies a local address, and it performs pair-wise synchronization.

• Synchronization: receive waits for send when the send completes, the buffer is free, and the request is accepted.

Communication Model: Communication is integrated at the I/O level, not into the memory system. It has networks of workstations (clusters) but with tighter integration. It is easier to build than scalable shared address space machines. A typical example is the IBM SP, made from RS6000 workstations with network interface integrated in the I/O bus, where bandwidth is limited by the I/O bus.

⭐ Key Takeaways

Amdahl's Law is critical for understanding the practical limits of parallel speedup, showing that even a tiny sequential fraction drastically limits performance, especially as processor count increases. Communication cost, measured in latency for remote memory accesses, significantly impacts effective CPI and overall performance. Flynn's taxonomy (SISD, SIMD, MISD, MIMD) provides the fundamental classification for parallel architectures, with MIMD being dominant. The key architectural distinction in MIMD is memory organization: UMA (SMP) offers uniform access times but limited scaling, while NUMA (distributed memory) offers better scalability but complex data communication. The two primary programming models are shared address space, which is simpler for complex communication patterns, and message passing, which makes communication explicit and is easier for sender-initiated operations.

🧠 Quick Revision Questions

1. According to Amdahl's Law, what fraction of a program must be parallelizable to achieve a speedup of 10 with 20 processors? Show your calculation.
2. What is the key architectural difference between a Symmetric Multi-Processor (SMP) and a Non-Uniform Memory Access (NUMA) machine?
3. In Flynn's taxonomy, what is the key difference in data handling between an SIMD and an MIMD machine?
4. Explain the three fundamental issues (Naming, Synchronization, Latency/Bandwidth) in the context of designing a parallel machine.
5. How does the communication abstraction differ in the programming layer between a shared address space architecture and a message-passing architecture?

📘 Lecture 35 — Multiprocessors (Cache Coherence Problem)

📖 Overview: This lecture addresses the critical issue of cache coherence in multiprocessor systems, where shared data replicated across multiple caches can lead to inconsistencies. Understanding this problem is fundamental to designing efficient parallel computing architectures, as it directly impacts data integrity and system performance in both symmetric shared-memory and distributed memory systems.

🗂️ Topics Covered

The lecture begins with a recap of parallel processing architecture, MIMD classification, and the framework for parallel processing. It then introduces the multiprocessor cache sharing concept and the cache coherence problem, explaining formal definitions and features of a coherent system. The main body covers cache coherence on buses, coherence with write-through caches, cache coherence protocols including snooping and directory-based schemes, and a detailed examination of write invalidate versus write broadcast protocols. The lecture concludes with an example snooping protocol using finite state machines for write invalidation and write-back caches.

📝 Lecture Summary

Recap: Parallel Processing Architecture

Last time, the concept of parallel processing was introduced to improve computer performance by using a collection of processing elements that cooperate and communicate. Flynn‘s four categories of computers—SISD (Single Instruction Single Data), SIMD (Single Instruction Multiple Data), MISD (Multiple Instruction Single Data), and MIMD (Multiple Instruction Multiple Data)—form the basis for implementing programming and communication models. The MIMD machines implement parallel processing architecture.

Recap: MIMD Classification

Based on memory organization and interconnect strategy, MIMD machines are classified as Centralized Shared Memory Architecture and Distributed Memory Architecture. In centralized shared memory, subsystems share the same physical centralized memory connected by a bus, characterized by Uniform Memory Access (UMA)—where access time to all memory from all processors is the same. Distributed memory consists of individual nodes containing a processor, some memory, I/O, and an interface to an interconnection network, providing more memory bandwidth and lower memory latency.

Recap: Framework for Parallel Processing

The framework defines programming and communication models for centralized shared-memory and distributed memory parallel processing architectures. These models present address space sharing and message passing. The shared-memory communication model has compatibility with SMP hardware and offers ease of programming when communication patterns are complex or vary dynamically. The message-passing communication model has explicit communication that is simple to understand and easier to use for sender-initiated communication.

Multiprocessor Cache Sharing

Today, we examine caching for multi-processing in the symmetric shared-memory architecture, where each processor has the same relationship to the single memory. Small-scale shared-memory machines support caching of both private data and shared data. Private data is used by a single processor, while shared data is replicated in caches of multiple processors for simultaneous use. The program behavior for caching private data is identical to a uniprocessor since no other processor uses the same data.

Multiprocessor Cache Coherence

When shared data are cached, the shared value may be replicated in multiple caches, reducing access latency and fulfilling bandwidth requirements. However, due to differences in communication for load/store and write strategies in caches, values in different caches may not be consistent. This conflict for shared data being read by multiple processors simultaneously is referred to as the cache coherence problem. Informally, a memory system is coherent if any read of a data item returns the most recently written value of that data item.

🔑 Definition — Cache Coherence Problem: The conflict or contention arising when shared data is replicated in multiple caches and values become inconsistent due to different write strategies and communication patterns in multiprocessor systems.

This definition contains two aspects: Coherence, which defines what value can be returned by a read, and Consistency, which determines when a written value will be returned by a read.

Cache Coherency Problem?

Processors P1, P2, and P3 see old values in their caches because there exist several alternatives to write to caches. In write-back caches, the value written back to memory depends on which cache flushes or writes back the value and when—the value returned depends on program order, program issue order, or order of completion. The cache coherency problem exists even on uniprocessors where interaction between caches and I/O devices requires infrequent software solutions. However, the problem is performance-critical in multiprocessors where order among multiple processes is crucial and must be treated as a basic hardware design issue.

Order among multiple processes?

Consider a single shared memory with no caches. Every read/write to a location accesses the same physical location, and the operation completes when it does so. This imposes a serial or total order on operations to the location: operations from a given processor are in program order, and the order from different processors is some interleaving that preserves individual program orders. With caches, the "latest" means the most recent in a serial order with operations to a location from a given processor in program order. For the serial order to be consistent, all processors must see writes to the location in the same order.

Formal Definition of Coherence

A memory system is coherent if the results of any execution of a program are such that for each location, it is possible to construct a hypothetical serial order of all operations to the location that is consistent with the execution results. In a coherent system, the operations issued by any particular process occur in the order issued by that process, and the value returned by a read is the value written by the last write to that location in the serial order.

Features of Coherent System

Two features of a coherent system are:

• Write propagation: Value written must become visible to others—any write must eventually be seen by a read
• Write serialization: Writes to a location are seen in the same order by all

Cache Coherence on buses

Bus transactions and Cache state transitions are fundamentals of uniprocessor systems. Bus transactions pass through three phases: arbitration, command/address, and data transfer. Cache state transition deals with every block as a finite state machine. Write-through, write no-allocate caches have two states: valid and invalid. Write-back caches have one more state: modified (dirty).

Coherence with write-through caches!

The controller snoops on bus events (write transactions) and invalidates/updates cache. In write-through, memory is always up-to-date, so invalidation causes the next read to miss and fetch the new value from memory—the bus transaction is indeed write propagation. Bus transactions impose write serialization as writes are seen in the same order.

Cache Coherence Protocols

In a coherent multiprocessor, caches provide both relocation (migration) and replication (duplication) of shared data items. Protocols use different techniques to track sharing status to maintain coherence for multiprocessors, referred to as Cache Coherence Protocols.

Potential HW Coherency Solutions

Two fundamental classes of Coherence protocols are:

• Snooping Protocols: All cache controllers monitor or snoop on the bus to determine whether they have a copy of the block requested on the bus
• Directory-Based Protocols: The sharing status of a block of physical memory is kept in one location, called a directory

Snoopy solutions: Send all requests for data to all processors; processors snoop to see if they have a copy and respond accordingly; requires broadcast since caching information is at processors; works well with bus (natural broadcast medium); dominates for small-scale machines.

Directory-Based schemes: Keep track of what is being shared in one centralized place; distributed memory employs distributed directory for scalability and to avoid bottlenecks; send point-to-point requests to processors via network; scales better than snooping; actually existed before snooping-based schemes.

Basic Snooping Protocols

There are two ways to maintain coherence requirements using snooping protocols: 1. Write Invalidate Method: Ensures that processor has exclusive access to the data item before it writes that item, and all other cached copies are invalidated or canceled on write. Exclusive access ensures no other readable or writable copies of an item exist when the write occurs.

Write Invalidate Protocol uses multiple readers and single writer. For write to shared data, an invalidate information is sent to all caches, and the controller snoops and invalidates any copies. For read miss in write-through, memory is always up-to-date; in write-back, it snoops in caches to find the most recent copy.

📌 Example: Invalidation protocol for snooping bus with write-back cache assuming both CPU A and B caches do not initially hold X, and memory value of X is 0. When CPU A writes 1 to X, exclusive access is required, and any copy held by the reading processor must be invalidated. When B reads, it misses in cache and is forced to get a new copy of data. The exclusive write access prevents any other processor from writing simultaneously. When 2nd miss by B occurs, CPU A responds with the value, canceling memory response. Both B‘s cache and memory contents of X are updated. The invalidation for memory location X occurs when A attempts to write 1.

2. Write Broadcast Protocol: Instead of invalidating, this protocol updates all cached copies of a data item when that item is written. It is particularly used for write-through caches. For write to shared data, processors snoop and update any copies by broadcasting on the bus.

📌 Example: Write update protocol for snooping bus with write-back cache assuming both CPU A and B caches do not initially hold X, and memory value is 0. When CPU A writes a 1 to memory X, it updates the value in caches of A and B and the memory.

Write Invalidate versus Broadcast

Invalidate requires one transaction for multiple writes to the same word. Invalidate uses spatial locality: one transaction for write to different words in the same block. Broadcast has lower latency between write and read.

An Example Snooping Protocol

A bus-based protocol is implemented by incorporating a finite state machine controller in each node. This controller responds to requests from the processor and from the bus based on the type of request, whether it is hit or miss in the cache, and the state of the cache block specified in the request.

Each block of memory is in one of three states: (Shared) Clean in all caches and up-to-date in memory, OR (Exclusive) Dirty in exactly one cache, OR Not in any caches. Each cache block is in one of three states: Shared (block can be read), OR Exclusive (cache has only copy, writable, and dirty), OR Invalid (block contains no data). Read misses cause all caches to snoop bus. Writes to clean line are treated as misses.

Finite State Machine for Write Invalidation Protocol and Write Back Caches

The state machine has three states: Invalid, Shared (read only), and Exclusive (read/write). Cache states are shown in circles where access permitted by CPU without a state transition is shown in parenthesis. The stimulus causing state transition is shown on the transition arc in yellow, and the bus action generated is shown in orange. The state in each cache node represents the state of the selected cache block specified by the processor or bus request. For simplicity, states of the protocol are duplicated to represent transitions based on CPU request and transitions based on bus request.

Snoopy-Cache State Machine-I (CPU requests): A read miss in exclusive or shared state and a write miss in the exclusive state occurs when the address requested by CPU does not match the address in the cache block. An attempt to write a block in shared state always generates a miss, even if the block is present in cache, since the block must be made exclusive. In read hit, shared and exclusive states read data in cache and address the conflict miss. The invalid state places read miss on the bus. For write hit, exclusive state writes data in cache, and shared state places write miss on bus. In write miss, invalid state places miss on bus; shared and exclusive states address conflict miss; shared state places write miss on bus, while exclusive state writes back block and then places write miss on bus.

Snoopy-Cache State Machine-II (Bus requests): Whenever a bus transaction occurs, all caches containing the cache block specified in the bus transaction take action according to this state machine. Memory provides data on a read miss for a block that is clean in all caches. For read miss, the shared state takes no action and allows memory to service the read miss; the exclusive state attempts to share the data, places the cache block on the bus, and changes state to shared. For write miss, the shared state attempts to write a shared block and invalidates the block. The exclusive state attempts to write a block that is exclusive elsewhere; writes back the cache block and makes the state invalid.

⭐ Key Takeaways

The cache coherence problem is a fundamental challenge in multiprocessor systems where shared data replicated in multiple caches can become inconsistent. The two essential features of a coherent system are write propagation (writes become visible to all) and write serialization (writes to a location are seen in the same order by all). Two main classes of coherence protocols exist: snooping protocols (where cache controllers monitor the bus) and directory-based protocols (where sharing status is kept in a centralized directory). The two basic snooping techniques are write invalidate (which grants exclusive access before writing and invalidates other copies) and write broadcast (which updates all cached copies on writes). Finite state machines with three states (Invalid, Shared, Exclusive) provide the hardware implementation mechanism for snooping protocols, with separate state transitions for CPU requests and bus requests.

🧠 Quick Revision Questions

1. What are the two fundamental aspects of memory behavior in a coherent system, and how do they differ?
2. Explain the difference between write invalidate and write broadcast protocols, and give one advantage of each.
3. What are the three states in the finite state machine for write invalidation protocol with write-back caches?
4. How does a snooping protocol handle a write to a shared block when using write invalidation?
5. Why is write serialization important in a coherent multiprocessor system?

📘 Lecture 36 — Multiprocessors (Cache Coherence Problem … Cont’d)

📖 Overview: This lecture continues the discussion on cache coherence in symmetric shared-memory multiprocessors, focusing on the practical implementation of snooping protocols using finite state machine controllers. It then introduces coherence solutions for distributed memory architectures, specifically directory-based protocols, and compares their performance and complexity with snooping approaches.

🗂️ Topics Covered

The lecture begins with a detailed recap of the cache coherence problem, write propagation, and serialization, followed by a step-by-step example of an invalidation-based snooping protocol. It then covers implementation complications like write races and snooping cache conflicts, explores variations like MESI, Berkeley, and Illinois protocols, and concludes with a thorough explanation of directory-based protocols for distributed shared memory systems, including state transition diagrams and message types.

📝 Lecture Summary

Recap: Cache Coherence Problem

Last time, we discussed the sharing of caches for multi-processing in the symmetric shared-memory architecture, where each processor has the same relationship to the single memory. We distinguished between private data (used by a single processor) and shared data (replicated in caches of multiple processors). The cache coherence problem results from inconsistency in caching shared data being read simultaneously. Using write-back caches (where values written back depend on which cache flushes), we saw that the coherency problem exists even on uniprocessors due to I/O interaction, but in multiprocessors it is performance-critical.

Recap: Order among multiple processes

For a single shared memory without caches, a serial or total order is imposed on operations. With caches, the serial order must be consistent — all processors must see writes to a location in the same order. In a coherent system: operations from any process occur in the order issued, and a read returns the value written by the last write in the serial order. Two features of a coherent system are write propagation and write serialization.

Recap: Multiprocessor cache Coherence & Coherency Solutions

To implement cache coherence, multiprocessors extend both bus transactions and state transitions. The cache controller snoops on bus events (write transactions) and invalidates/updates cache. Two fundamental classes of coherence protocols are:

• Snooping Protocols: All cache controllers monitor (snoop) the bus to detect if they have a copy of the requested block.
• Directory-Based Protocols: The sharing status of a block is kept in one location called a directory.

Recap: Basic Snooping Protocols

Snooping protocols use two techniques: write invalidate (processor gets exclusive access before writing, invalidating all other copies) and write broadcast (all cached copies are updated). Invalidate uses spatial locality (one transaction for multiple writes to the same block), while broadcast has lower latency between write and read. The finite state machine controller implements snooping protocols, responding to processor and bus requests based on request type, hit/miss status, and cache block state (Shared, Exclusive, or Invalid).

Example: Working of Finite State Machine Controller

Today we continue with an example assuming two processors P1 and P2, each with its own cache, sharing memory on a bus. The table shows processor status, bus transactions, and memory. Initially, cache state is Invalid (block not in cache); memory blocks A1 and A2 map to the same cache block (A1 ≠ A2).

🔑 Definition — Write-Back Cache: A cache where write operations update the cache block, and the updated value is only written to memory when the block is evicted.

Step 1 – P1 writes 10 to A1: A write miss on the bus occurs; the state transitions from Invalid → Exclusive. Step 2 – P1 reads A1: CPU read HIT occurs; the FSM stays in Exclusive state. Step 3 – P2 reads A1: P2 (in Invalid) has a read miss; its state changes from Invalid → Shared. P1 (in Exclusive) sees a remote read write-back, its state changes from Exclusive → Shared. The value (10) is read from shared memory into both caches at A1. Step 4 – P2 writes 20 to A2: P1 sees a remote write, state changes from Shared → Invalid. P2 sees a CPU write, places write miss on bus, state changes from Shared → Exclusive, and writes value 20 to A1. Step 5 – P2 writes 40 to A2: P2 (in Exclusive) has a CPU write miss and initiates write-back to P2 at A2, remaining in Exclusive state with address A2 and value 40.

📐 Formula: State Transition Logic → The cache controller transitions states based on: (CPU request or Bus snoop) AND (Hit/Miss status).

📌 Example: In the step-by-step sequence, when P2 writes 20 to A2, P1’s cache is invalidated because it held a shared copy of A1 (same cache block mapping). This demonstrates the write invalidate protocol in action.

Implementation Complications

While the FSM works well, these complications arise:

• Write Races: Occur when one processor wants to update a cache block but another gets the bus first and writes the same block. The bus transaction is a two-step process: arbitrate for bus, then place miss and complete. If a miss occurs while waiting for bus, the processor must handle the miss (invalidate) and restart. Split transaction buses allow multiple outstanding transactions for a block, preventing races but requiring tracking of multiple misses for one block.

Snooping Cache Conflict

The CPU accesses cache while bus transactions check cache tags. Since every bus transaction checks tags, interference with CPU can occur. Two methods to reduce interference:

1. Duplicate set of tags for L1 caches: CPU uses one set, snoop uses another. The CPU stalls only when snoop detects a copy and tags need updating.
2. Multi-level caches with inclusion: L2 cache duplicates L1 content, provided L2 obeys inclusion (L1 content is in L2). CPU activity goes to L1, snoop activity to L2. If snoop hits, it arbitrates L1 to update/get data, stalling the CPU. This can be combined with duplicate tags.

Snooping Cache Variations: MESI Protocol

The MESI Protocol has four states: Modified, Exclusive, Shared, Invalid. Here, Exclusive means exclusively cached but clean upon loading (memory up-to-date). Bus serializes writes; getting the bus ensures no one else can perform memory operations.

Snooping Cache Variations: Berkeley Protocol

The Berkeley Protocol allows cache-to-cache transfers on the shared bus. It adds the notion of owner — the cache that has the block in a Dirty state is the owner (the last one who wrote). The owner is responsible to transfer data on reads and update main memory. If no cache owns the block, memory is the owner.

Summary Snooping Cache Variations

• Illinois Protocol: States are Private Dirty, Private Clean, Shared, Invalid.
• MESI Protocol: Modified (private, memory not up-to-date), eXclusive (private, memory up-to-date), Shared (shared, memory up-to-date), Invalid.
• If read sourced from memory → Private Clean; if sourced from another cache → Shared. Can write in cache if held Private Clean or Private Dirty.

Snoop Cache Extensions

Extensions include:

• Berkeley: Fourth state Ownership; Shared → Modified needs only invalidate (upgrade request, no memory read).
• MESI: Clean exclusive state (no miss for private data on write).
• Illinois: Cache supplies data when in Shared state (no memory access).

🔑 Definition — Upgrade Request: A bus transaction that requests permission to write a shared block without fetching the data from memory, as the block already exists in the requesting cache.

Larger Microprocessors & Directory Based Protocol

Larger systems use separate memory per processor (distributed memory) with local/remote access via a memory controller. One coherency solution uses non-cached pages; the alternative is a directory containing information for every block in memory, tracking state and which caches have copies. Using information per memory block (vs. per cache block):

• PLUS: Simpler protocol (centralized location).
• MINUS: Directory size is a function of memory size (vs. cache size for simpler protocols).

Directory Based Protocol: Distributed Shared Memory

The directory-based protocol is similar to snoopy protocols but uses the directory. Three states:

• Shared: ≥1 processor has data, memory up-to-date.
• Uncached: No processor has it; not valid in any cache.
• Exclusive: 1 processor (owner) has data; memory out-of-date. In addition, must track which processors have data when in Shared state (usually using a bit vector). Key assumptions: writes to non-exclusive data cause a write miss; processor blocks until access completes; messages are received and acted upon in order sent. Three processor nodes involved: Local node (request originates), Home node (memory location resides), Remote node (has a copy of cache block).

📌 Example: Message types include: Read miss (P, A) — request data; Write miss (P, A) — request exclusive ownership; Invalidate (A) — invalidate shared copies; Fetch (A) — fetch block to home directory; Data value reply (Data) — return data as read miss response; Data write-back (A, Data) — write-back data as invalidate response.

State Transition Diagram for an Individual Cache Block in a Directory Based System

States are identical to the snoopy case. Transactions are caused by read misses, write misses, invalidates, and data fetch requests. Write misses that were broadcast on the bus for snooping now result in explicit invalidate and data fetch requests. On a write, the full cache block must be read.

State Transition Diagram for the Directory

The directory uses the same states and structure. Two actions: update directory state and send messages to satisfy requests. The controller tracks all copies of a memory block and updates the sharing set (Sharers) while sending messages.

Example Directory Protocol

Messages sent to the directory cause: update the directory and send more messages to satisfy the request.

• Block in Uncached state (memory has current value):
  • Read miss: Requesting processor gets data from memory; becomes only sharing node; state becomes Shared.
  • Write miss: Requesting processor gets value and becomes the sharing node; state becomes Exclusive; Sharers indicates owner.
• Block in Shared state (memory up-to-date):
  • Read miss: Requesting processor gets data from memory; added to sharing set.
  • Write miss: Requesting processor gets value; all processors in Sharers get invalidate messages; Sharers set to requesting processor; state becomes Exclusive.
• Block in Exclusive state (value in owner's cache, identified by Sharers):
  • Read miss: Owner processor sent a data fetch message; owner's block state transitions to Shared; owner sends data to directory, which is written to memory and sent to requestor; requesting processor added to Sharers (owner still has readable copy); state becomes Shared.
  • Data write-back: Owner is replacing the block, writes it back; memory copy becomes up-to-date; block becomes Uncached; Sharers becomes empty.
  • Write miss: A message sent to old owner causes it to send the block value to directory, which sends it to requesting processor (new owner); Sharers set to new owner; state becomes Exclusive.

💡 Why this matters: Directory-based protocols scale to larger systems than snooping protocols because they avoid broadcasting on a shared bus. The directory acts as a centralized coherency point, eliminating bus arbitration bottlenecks and enabling distributed shared memory architectures.

Summary

• Caches contain all information on state of cached memory blocks.
• Snooping and Directory Protocols are similar in logic.
• The bus makes snooping easier because of broadcast capability.
• Directory has an extra data structure to keep track of the state of all cache blocks.

⭐ Key Takeaways

The write invalidate snooping protocol using a finite state machine with Invalid/Shared/Exclusive states is the foundational coherence mechanism, and its step-by-step operation with two processors demonstrates how cache states transition during reads, writes, and remote accesses. Implementation complications like write races and snooping cache conflicts require solutions such as split transaction buses, duplicate tags, and multi-level caches with inclusion. Protocol variations (MESI, Berkeley, Illinois) each add optimizations: MESI's clean exclusive avoids write misses for private data, Berkeley adds ownership for cache-to-cache transfers, and Illinois allows cache supply on shared reads. For larger systems, directory-based protocols scale better than snooping by avoiding broadcast, using a directory to track which processors share each block and sending explicit invalidate/fetch messages only to affected nodes, though at the cost of extra storage for directory entries.

🧠 Quick Revision Questions

1. In the example FSM protocol, what state transition occurs for P1 when P2 reads A1 from Exclusive state?
2. What two methods reduce interference between CPU cache access and snooping bus transactions?
3. What is the key difference between the MESI protocol's 'Exclusive' state and the basic three-state protocol's 'Exclusive' state?
4. In a directory-based protocol, what messages are sent to the old owner when a write miss occurs on a block in Exclusive state?
5. What are the two main actions performed by the directory state machine when it receives a message?

📘 Lecture 37 — Multiprocessors (Performance and Synchronization)

📖 Overview: This lecture examines the performance of multiprocessors using symmetric shared-memory and distributed shared-memory architectures. It then introduces hardware synchronization primitives and techniques essential for coordinating access to shared data in parallel systems.

🗂️ Topics Covered

The lecture covers performance analysis of multiprocessors including coherence misses like true-sharing and false-sharing, performance factors for both bus-based and directory-based systems. It then explores synchronization mechanisms, focusing on hardware primitives such as atomic exchange, test-and-set, and the load-linked/store-conditional instruction pair, with examples of building locks and atomic operations.

📝 Lecture Summary

Recap: Cache Coherence Problem

The lecture begins by recapping that cache coherence is a performance-critical problem in both symmetric shared-memory and distributed shared-memory architectures. The protocols used to maintain coherence include snooping protocols (using write invalidate and write broadcast) and directory-based protocols. Snooping protocols use a three-state FSM (Shared, Exclusive, Invalid) with variations like MESI (Modify, Exclusive, Shared, Invalid), Barkley (Owned-Exclusive, Owned-Shared, Shared, Invalid), and Illinois (Private Dirty, Private Clean, Shared, Invalid). Directory-based protocols are used in larger systems with distributed memory, tracking the state of every block in every cache via a directory.

Example: Working of Finite State Machine Controller

A detailed example with two processors P1 and P2, each with its own cache, memory, and directory, illustrates directory-based protocol operation. The FSM transitions from the Uncached state (data in memory only) based on messages like read miss, write miss, invalidates, and data fetch requests.

A walkthrough assumes A1 and A2 map to the same cache block:

• Step 1: P1 writes 10 to A1. A write miss occurs. The data value reply message is sent to the controller. P1 is inserted in the directory sharer-set {P1}. The state transitions from Uncached to Exclusive.
• Step 2: P1 reads A1. A CPU read hit occurs, so the FSM stays in Exclusive state.
• Step 3: P2 reads A1. A read miss occurs. P1, being in Exclusive state, asserts remote read write-back and changes to Shared. P2 changes from Uncached to Shared. The value 10 is read into both caches, and the sharer-set becomes {P1, P2}.
• Step 4: P2 writes 20 to A2. Since A1 and A2 map to the same block, P1 sees a remote write and changes from Shared to Invalid. P2 places a write miss on the bus and changes from Shared to Exclusive, writing value 20 to A1. The directory for A1 now has sharer-set {P2}.
• Step 5: P2 writes 40 to A2. P2, in Exclusive state, experiences a write miss at A2. The directory for A2 is in Exclusive state with P2 in the sharer-set. P2 write-backs 20 at A1, making the directory for A1 Uncached with an empty sharer-set and value 20 in memory. P2 remains in Exclusive state with address A2 and value 40.

🔑 Definition — True Sharing Miss: A miss that arises from the communication of data through the cache-coherence mechanism, where data is actually shared between processors. 🔑 Definition — False Sharing Miss: A miss that occurs when a block is invalidated and a subsequent reference causes a miss, even though the word being written and the word being read are different. The miss occurs because of the single valid bit per cache block, not because of actual data sharing.

📌 Example of True and False Sharing: Consider words A1 and A2 in the same cache block, in Shared state in caches of P1 and P2.

• Event 1: P1 Write A1 — True sharing miss (A1 was read by P2 and must be invalidated from P2).
• Event 2: P2 Read A2 — False sharing miss (A2 was invalidated by P1's write to A1, but the value of A1 is not used in P2).
• Event 3: P1 Write A1 — False sharing miss (block is marked shared due to P2's read, but P2 did not read A1).
• Event 4: P2 Write A2 — False sharing miss (block is marked shared due to P2's read in event 2, but P2 did not write A2).
• Event 5: P1 Read A2 — True sharing miss (the value being read by P2 was written by P2 in event 4).

Performance of Multiprocessors: Symmetric Shared-Memory Architecture

In bus-based multiprocessors using invalidation protocols, overall cache performance is a combination of uniprocessor cache miss-traffic and traffic caused by communication (invalidation and subsequent cache misses). Changing processor count, cache size, and block size affects these components. Coherence misses arise from inter-processor communication and come from two sources:

• True Sharing: Arises from actual communication of data. The first write by a processor to a shared cache block causes an invalidation to establish ownership. When another processor reads the modified word, a miss occurs and the block is transferred.
• False Sharing: Arises from the use of invalidation-based coherence algorithms with a single valid bit per cache block. A block is invalidated even when the word being written and the word being read are different, causing an extra cache miss without actual data communication.

💡 Why this matters: Distinguishing true from false sharing is critical for optimizing parallel programs. False sharing can be reduced by increasing block size or restructuring data layout, while true sharing is inherent to the algorithm's communication pattern.

Performance of Multiprocessors: Distributed Shared-Memory Architecture

The performance of directory-based multiprocessors depends on factors like processor count, cache size, and block size. Additionally, the location of requested data — dependent on initial allocation and sharing pattern — significantly influences performance. The distribution of memory requests between local memory and remote memory is key, as it affects global bandwidth consumption and request latency. Graphs show that as cache size grows, miss rates decrease; local miss rates decline steadily, while the decline in remote miss rates depends on coherence misses. Similarly, increasing block size reduces miss rates.

Synchronization

Synchronization is needed to ensure it is safe for different processes to use shared data. Mechanisms are built with user-level software routines that rely on hardware-supplied synchronization instructions. For small multiprocessors, uninterruptable instructions that fetch and update memory atomically are used (atomic operations). For large-scale multiprocessors, synchronization can be a bottleneck, and techniques are needed to reduce contention and latency.

🔑 Definition — Atomic Operation: An operation that reads and updates a memory value in a single, indivisible step, preventing other processors from interfering.

Hardware Primitives: Uninterruptable Instructions

The basic requirement for implementing synchronization is a set of hardware primitives with the ability to atomically read and modify a memory location. One typical operation is Atomic exchange, which interchanges a value in a register for a value in memory. Other primitives include Test-and-Set (tests a value and sets it if the test passes) and Fetch-and-Increment (returns a memory value and atomically increments it).

• Atomic Exchange for a Simple Lock: A lock where 0 indicates free and 1 indicates unavailable. A processor exchanges 1 (in a register) with the memory address of the lock. If the returned value is 1, another processor has claimed access; if 0, the processor acquires the lock (and the memory value is changed to 1, preventing other exchanges from retrieving 0).

📌 Example of Simultaneous Exchange: If two processors try to exchange simultaneously, the race is broken when one exchanges first and returns 0, and the second returns 1.

Because implementing a single atomic instruction in hardware is complex, modern multiprocessors use a pair of instructions: Load Linked (LL) and Store Conditional (SC).

• Load Linked (LL): Returns the initial value from a memory location.
• Store Conditional (SC): Returns 1 if it succeeds (no other store to the same memory location since the preceding LL) and 0 otherwise.

If the contents of the memory location specified by LL are changed before the SC to the same address occurs, the SC fails.

📌 Example: Implementing Atomic Exchange with LL & SC

try: MOV R3,R4        ; mov exchange value
     ll R2,0(R1)      ; load linked
     sc R3,0(R1)      ; store conditional
     beqz R3,try      ; branch if store fails (R3 = 0)
     mov R4,R2        ; put load value in R4

At the end, R4 and the memory location specified by R1 have been atomically exchanged.

📌 Example: Implementing Atomic Fetch & Increment with LL & SC

try: ll R2,0(R1)      ; load linked
     addi R2,R2,#1    ; increment (OK if reg–reg)
     sc R2,0(R1)      ; store conditional
     beqz R2,try      ; branch if store fails (R2 = 0)

Since SC only checks that its address matches the link register, register-register instructions can safely be placed after LL, but the number of instructions between LL and SC must be kept small.

Summary

The lecture concludes the series on multiprocessors by stating that multiprocessors are highly effective for multi-programmed workloads and commercial workloads like web searching. The centralized memory architecture (SMPs) maintains a single centralized memory with uniform access time, while distributed shared-memory multiprocessors (DSMs) have non-uniform memory architecture and achieve greater scalability. These advantages can be partially combined in architectures like Sun Microsystems' Wildfire, where large SMPs (e.g., E6000) are used as nodes to maximize uniform memory access, and scalability is achieved via the Wildfire Interface (WFI), which can connect 2 or 4 E6000 multiprocessors.

⭐ Key Takeaways

The key performance issue in multiprocessors is coherence misses, which are classified as true-sharing misses (arising from actual data communication) and false-sharing misses (arising from the block-based invalidation mechanism when different words within a block are accessed by different processors). Performance in distributed shared-memory architectures is additionally influenced by the location of data, making the distribution of local versus remote memory requests critical. Synchronization is implemented using hardware primitives that allow atomic read-modify-write operations, with modern systems typically using the Load Linked/Store Conditional instruction pair to build locks and atomic operations like exchange and fetch-and-increment. The FSM controller for directory-based protocols tracks block states (Uncached, Shared, Exclusive) and uses messages between local, home, and remote nodes to maintain cache coherence.

🧠 Quick Revision Questions

1. What is the difference between a true-sharing miss and a false-sharing miss? Provide a specific example with two processors and two addresses in the same cache block.
2. In the FSM controller example, what happens when P2 writes to address A2 while P1 has A1 (same cache block) in Shared state? Describe the state transitions for both processors and the directory.
3. How does the Load Linked/Store Conditional (LL/SC) pair implement an atomic operation? Write the assembly code sequence for an atomic exchange using LL/SC.
4. Why is the distribution of memory requests between local and remote memory critical for performance in distributed shared-memory architectures?
5. Explain how a simple lock works using the atomic exchange primitive. What does it mean if the exchange returns a value of 1 versus 0?

📘 Lecture 38 — Input Output Systems (Storage and I/O Systems)

📖 Overview: This lecture transitions from parallel processing architectures to the critical role of I/O systems in overall computer performance. It introduces storage technologies, focusing on magnetic disks, and explains how neglecting I/O can severely limit system speed-up according to Amdahl's Law. The lecture also covers I/O performance metrics and processor-interface control structures.

🗂️ Topics Covered

A recap of multiprocessing architectures (SIMD, MISD, MIMD, cache coherence) is followed by a discussion of why I/O systems are now the dominant performance bottleneck. The lecture then introduces magnetic disk storage technology, its historical evolution from 1956 to the 1990s, and alternative storage technologies like tape and optical disk. Key I/O performance parameters (diversity, capacity, latency, bandwidth) and the producer-server model are explained, along with processor interface issues including isolated I/O, memory-mapped I/O, programmed I/O, interrupts, DMA, and I/O processors.

📝 Lecture Summary

Recap: Multiprocessing & The Outside Processor

The lecture begins by recapping that Parallel Architecture uses cooperating processing elements to solve large problems fast. This includes SIMD, MISD, and MIMD machines, where MIMD facilitates complete parallel processing. MIMD is classified into Centralized Shared Memory Architecture (uniform access time) and Distributed Memory Architecture (non-uniform memory, greater scalability). The cache coherence problem is solved via Snooping algorithms (for centralized) and Directory Based Protocols (for distributed).

The crucial transition is that while processing power and memory size double every 18 months, disk positioning rate (seek + rotate) doubles only every 10 years. This creates a massive performance gap, making I/O the dominant bottleneck.

💡 Why this matters: The lecture establishes that a fast processor is useless without a fast I/O system to feed it data.

Introduction: Outside the Processor

The overall computer performance is measured by throughput, which is heavily influenced by I/O. Neglecting I/O is like a car with a powerful engine but no wheels. Using Amdahl's Law, the lecture shows the impact: If CPU time is sped up 10x but I/O is ignored, the overall speedup is only 5 (a 50% loss). If CPU is sped up 100x, the overall speedup is only 10 (a 90% loss). Therefore, I/O performance increasingly limits the system.

An I/O System comprises Storage I/Os (secondary/tertiary storage like magnetic disk, tape, CD) and Communication I/Os (I/O Bus system interconnecting processor/memory with devices).

Disk Storages: Technology Trends & Historical Perspective

Disk capacity has improved dramatically. Before 1990, it doubled every 36 months; now it doubles every 18 months. This is driven by computing paradigm shifts from batch to on-line processing (1950s) to ubiquitous computing (1990s) in phones, books, and cars. This motivated smaller, cheaper embedded storage and high-capacity data utilities.

The historical development of magnetic disks:

• 1956-1970s: IBM Ramac and Winchester for mainframes; form factor shrinking from 27” to 14”.
• 1970s: 5.25” floppy disk; early industry standard interfaces (ST506, SASI, SMD, ESDI).
• Early 1980s: Era of PCs; end of proprietary interfaces.
• Mid 1980s: Client/server computing; accelerated disk downsizing to 5.25” and 3.5”; industry standards like SCSI, IPI, IDE.
• Late 1980s-1990s: Era of laptops; 2.5” and 1.8” form factors. DRAM and flash RAM challenged disks but were still expensive. Optical disks (CD-ROM) found a niche despite poor performance.

A key trend shows the DRAM to Disk ratio: It peaked at ~40% in 1986 but fell to ~15% by 1998.

Devices: Magnetic Disks

• Purpose: Long-term, nonvolatile, large, inexpensive, slow level in the storage hierarchy.
• Characteristics: Seek Time (~8 ms avg) – positional latency; Rotational Latency (half a revolution); Transfer rate (~a sector per ms, 5-15 MB/s).
• Capacity: Gigabytes, quadruples every 3 years.
• Speed Example: 7200 RPM = 120 RPS → 8 ms per revolution → avg rotational latency = 4 ms. 128 sectors/track → 0.25 ms per sector. 1 KB per sector → 16 MB/s.

I/O Performance Parameters

I/O performance has unique parameters with no CPU counterpart:

• Diversity: Which I/O devices can connect to the CPU.
• Capacity: How many I/O devices can connect.
• Latency: Overall response time to complete a task.
• Bandwidth: Number of tasks completed in a specified time (throughput).

An I/O system is in equilibrium when the rate of arriving I/O requests equals the rate of departing requests after being serviced. The producer-server model (a FIFO queue with a server) is used: Response Time = Queue Time + Device Service Time.

📐 Formula: Response Time = Time to Queue + Device Service Time → The total time from when a task arrives in the I/O buffer to when the server finishes it.

📌 Example: A graph shows that minimum response time is achieved at only 10% throughput, while achieving 100% throughput takes 7-8 times the minimum response time. This illustrates the tradeoff between response time and throughput.

I/O Transaction Time

The transaction time of a computer is the sum of three times:

• Entry Time: Time for user to enter a command (avg 0.25 sec; from keyboard 4.0 sec).
• System Response Time: Time between command entry and system response.
• Think Time: Time from reception of response until user enters next command.

📌 Example: What happens if system response time shrinks from 1.0 sec to 0.3 sec?

• With Keyboard (entry 4.0 sec, think 9.4 sec): Shaving off 0.7 sec from response saves 4.9 sec (34%).
• With Graphics (entry 0.25 sec, think 1.6 sec): Shaving off 0.7 sec saves 2.0 sec (70%). This shows that faster response time leads to greater productivity.

Processor Interface Issues

• Processor Interface Types:

  • Isolated I/O: Uses a separate I/O bus and requires special in/out instructions.
  • Memory Mapped I/O: I/O devices appear as memory locations; uses standard load/store instructions.
  • Interrupts: Devices signal the processor when ready.

• I/O Control Structures:

  • Polling (Programmed I/O): CPU continuously checks device status; inefficient.
  • Interrupt Driven I/O: CPU continues working; device interrupts CPU when ready.
  • Direct Memory Access (DMA): A DMAC (DMA Controller) handles data transfer between device and memory. CPU sends starting address, direction, and length, then issues "start". DMAC provides handshake signals.
  • I/O Processors (IOP): More intelligent than DMAC. The CPU issues an instruction to the IOP, the IOP looks in memory for commands, directly controls device-to-memory transfers, and interrupts CPU when done.

⭐ Key Takeaways

The most critical point is that I/O systems, not just the CPU, are the primary bottleneck to overall computer performance, as dramatically illustrated by Amdahl's Law where a 100x CPU speedup is reduced to 10x by a slow I/O system. Students must understand the tradeoff between response time and throughput in an I/O system, and know the three components of I/O transaction time: entry, system response, and think time. Magnetic disk performance is governed by seek time, rotational latency, and transfer rate. Finally, the different processor interfaces (isolated vs. memory-mapped) and control structures (polling, interrupt, DMA, IOP) represent a hierarchy of efficiency for managing I/O operations.

🧠 Quick Revision Questions

1. According to Amdahl's Law, if CPU time is sped up 100 times but I/O time is not improved, what is the overall system speedup?
2. List the three components of a disk's I/O transaction time.
3. What are the four main I/O control structures, and which one offloads the most work from the CPU?
4. What are the two key performance parameters for an I/O system that have no direct counterpart in CPU performance metrics?
5. In the producer-server model for I/O, what is the formula for a task's total response time?

📘 Lecture 39 — Input Output Systems (Bus Structures Connecting I/O Devices)

📖 Overview: This lecture explores the critical role of bus structures in connecting I/O devices to computer systems. It explains the trade-offs between different bus designs, the protocols governing bus transactions and arbitration, and how these choices impact overall system performance. Understanding bus architectures is essential for designing efficient I/O subsystems that do not become performance bottlenecks.

🗂️ Topics Covered

The lecture begins with a recap of I/O system performance, including the producer-server model and metrics like response time and throughput, illustrated with a comparison of flash memory vs. disk. It then covers I/O interconnect trends and the fundamental concept of bus-based interconnects, including their advantages and disadvantages. The bulk of the lecture details bus transactions (read/write), transition protocols (synchronous and asynchronous), and bus arbitration protocols (daisy chain, centralized parallel, and distributed). It concludes with bus design decisions, the SCSI standard, and a survey of historical bus standards.

📝 Lecture Summary

Recap: I/O System

The overall performance of a computer is measured by its throughput, which is strongly influenced by the I/O system. Amdahl's Law highlights that system speed-up is limited by the slowest component, making I/O a critical factor. An I/O system comprises storage I/Os (secondary and tertiary storage) and communication I/Os (the I/O bus system interconnecting the microprocessor, memory, and I/O devices). Key performance parameters for I/O are diversity, capacity, latency, and bandwidth. The I/O system operates on a producer-server model, which includes a queue where tasks accumulate while waiting to be serviced. The metrics for disk I/O performance are Response Time (Queue time + Device Service time) and Throughput (percentage of total bandwidth).

💡 Why this matters: This recap establishes that neglecting I/O performance can severely limit overall system speed, and it introduces the fundamental models and metrics used to analyze and compare I/O systems.

📌 Example: Comparing the time to read and write a 64Kbyte block to flash memory and disk.

• Flash memory: read 1 byte in 65 ns, write 1 byte in 1.5 μsec, erase 4KB in 5 msec.
• Disk Storage: average seek time = 4.0 msec, average rotational delay = 8.3 msec, transfer time = 4.2 MB/sec, controller overhead = 0.1 msec.
• Average read/write time for disk: 4.0 ms + 8.3 ms + 64KB/4.2 MB/sec + 0.1 ms = 27.3 msec.
• Read time for flash: 64KB / 1B/65ns = 4.3 ms. Flash is about 6 times faster than the disk for reading.
• Write time for flash: (64KB/4KB/5ms) + (64KB/1B/1.5μs) = 80 ms + 96 ms = 178.3 ms. The disk is about 6 times faster than the flash for writing.

Interconnect Trends

The I/O interconnect is the glue that interfaces computer system components. It is facilitated using high-speed hardware interfaces and logical protocols. Based on distance, bandwidth, latency, and reliability, interconnects are classified as backplanes, channels, and networks.

Bus-Based Interconnect

Communication on different interconnects is done via buses, which are shared communication links between subsystems.

• Advantages: Low cost (a single set of wires is shared) and versatility (easy to add new devices).
• Disadvantages: Creates a communication bottleneck, limiting maximum I/O throughput, especially in server systems where designing a bus to meet processor demand is a challenge.
• Limitations: Bus speed is limited by physical factors like bus length and bus loading (number of connected devices).
• Classification:
  • I/O busses: Long, connect many types of devices, offer a wide range of bandwidth, and follow a bus standard (also called a channel).
  • CPU–memory buses: High speed, matched to the memory system, and connect to a single device (also called a backplane).

Bus Transactions

Bus transactions are defined with reference to memory (memory read or memory write). A transaction includes two parts: sending the address and receiving the data.

• Read Transaction: The address and read signal are sent to the memory. The memory responds by sending the data and de-asserting the wait signal.
• Write Transaction: The address and data are sent to the memory with the write signal. The memory stores the data and de-asserts the wait signal.

Bus Transition Protocols

Bus transition or bus communication protocols specify the sequence of events and timing for information transfer.

• Synchronous Bus Transfers: Follow a sequence of operations relative to a common clock.
• Asynchronous Bus Transfers: Not clocked; uses control lines (req, ack) for handshaking among devices.

Synchronous Bus Protocols: The address is transmitted in the 1st clock, using control lines to indicate the request type. The read begins when NOT READ is asserted. The data is not ready until the wait signal is reasserted.

Asynchronous Handshake: The bus is self-timed. The protocol for a write transaction is:

1. t0: Master asserts address, direction, data; waits for slaves to decode.
2. t1: Master asserts the request line.
3. t2: Slave asserts ack, indicating data received.
4. t3: Master releases req.
5. t4: Slave releases ack.

For a read transaction:

1. t0: Master asserts address, direction, data; waits for slaves to decode.
2. t1: Master asserts request line.
3. t2: Slave asserts ack, indicating ready to transmit data.
4. t3: Master releases req, data received.
5. t4: Slave releases ack.

Bus Arbitration Protocols

To manage multiple devices needing bus access, bus masters are introduced. A Bus Master can control bus requests and initiate a transaction. A Bus Slave is activated by the master. The protocol to manage transactions by more than one master is the Bus Arbitration Protocol. It provides a mechanism for arbitrating access to the bus so it is used cooperatively. The arbitration schemes balance two factors: bus priority (highest priority device serviced first) and fairness (every device wanting the bus is eventually guaranteed access).

Bus Arbitration Schemes:

1. Daisy Chain Arbitration: The bus-grant line runs from highest to lowest priority device. A device intercepts the grant signal, preventing lower-priority devices from seeing it if it wants the bus. The sequence is: request, wait for grant, intercept grant, use bus, signal release.
2. Centralized Parallel Arbitration: Uses multiple request lines. Devices independently request the bus, and a centralized arbiter chooses which device becomes the bus master.
3. Distributed Arbitration:
   • Self-selection: Each device wanting access places its identity code on the bus. Devices then examine the code to determine the highest-priority requester.
   • Collision Detection: Devices independently request the bus. Multiple simultaneous requests result in a collision, and a device is selected based on priority.

Bus Options: Design Decisions

The design of a bus system depends on:

1. Bus Bandwidth: High performance uses separate address & data lines; low cost uses multiplexed lines.
2. Data width: High performance uses wider (e.g., 64-bit) data buses; low cost uses narrower (e.g., 8-bit) ones.
3. Transfer size: High performance uses multiple-word transfers for less overhead; low cost uses single-word transfers for simplicity.
4. Bus masters: High performance uses multiple masters (requires arbitration); low cost uses a single master.
5. Split transaction: High performance uses separate request and reply packets (needs multiple masters); low-cost has a continuous connection.
6. Clocking: High performance uses synchronous; low cost uses asynchronous.

Synchronous Bus Protocols – Multiple Masters

With multiple masters, the bus can offer higher bandwidth using split transaction or pipelined buses. In this technique, bus events are divided into requests and replies, making the bus available for other masters while memory reads the requested data.

Bus Standards

The SCSI (Small Computer System Interface) is a standard bus.

• Clock rate: 5 MHz, 10 MHz (fast), 20 MHz (ultra).
• Width: 8 or 16 bits.
• Devices can be slave (target) or master (initiator).
• SCSI protocol phases:
  • Bus Free: No device is accessing the bus.
  • Arbitration: Devices may request the bus; fixed priority by address.
  • Selection: Informs the target it will participate.
  • Command: The initiator reads commands from host memory and sends them to the target.
  • Data Transfer: Data in or out, initiator to target.
  • Message Phase: Message in or out, initiator to target.
  • Status Phase: Target sends status, just before command complete.

The lecture also notes a 1993 I/O Bus Survey and a 1993 MP Server Memory Bus Survey, showing the characteristics of historical standards like SCSI, PCI, and various memory buses.

⭐ Key Takeaways

The most critical takeaway is that the bus is the central communication link for I/O, and its design is a fundamental trade-off between performance and cost. Key design decisions like bus width, transfer size, and clocking (synchronous vs. asynchronous) directly impact throughput and latency. To manage multiple devices, understanding bus arbitration schemes—daisy chain, centralized parallel, and distributed—is essential, as they determine how bus access is prioritized and shared, balancing priority with fairness. Finally, protocols like the synchronous and asynchronous handshake define the precise sequence of events for read and write transactions, while split transactions allow for higher bandwidth by not holding the bus for the entire transaction.

🧠 Quick Revision Questions

1. What are the two main components of a bus transaction, and how do they differ for a read operation vs. a write operation?
2. Explain the primary difference between synchronous and asynchronous bus protocols, and give one advantage of each.
3. Describe the daisy chain arbitration scheme, including how priority is established and how a device signals it wants the bus.
4. List three key design decisions for a bus and state the typical choice for a high-performance system versus a low-cost system for each.
5. In the context of SCSI, what are the roles of an "initiator" and a "target," and what occurs during the "Arbitration" phase?

📘 Lecture 40 — Input Output Systems (RAID and I/O System Design)

📖 Overview: This lecture covers the evaluation and improvement of storage I/O system performance through reliability, availability, and dependability metrics. It introduces RAID (Redundant Array of Inexpensive Disks) levels as a solution to improve both availability and performance of storage systems, explaining the trade-offs between redundancy, capacity, and performance for each RAID level.

🗂️ Topics Covered

The lecture begins with a recap of I/O device performance, interconnects, and bus arbitration protocols. It then introduces storage I/O performance evaluation through reliability, availability, and dependability metrics. The core content covers RAID architectures including RAID 0, RAID 1, RAID 3, RAID 4, and RAID 5, with detailed comparisons of their fault tolerance, capacity overhead, and performance characteristics for small writes and reads.

📝 Lecture Summary

Recap: I/O device’s performance

Last time we compared the performance of disk storage and flash memory. We noticed that flash is six times faster than the disk for read and the disk is six times faster than the flash for data write. Then we discussed the trends in I/O interconnects as: the networks, channels and backplanes. The networks offer message-based narrow-pathway for distributed processors over long distance.

Recap: I/O Interconnects

The backplanes offer memory-mapped wide pathway for centralized processing over short distance. The interconnects are implemented via buses. The buses are classified in two major categories as the I/O bus and CPU-Memory bus. The channels are implemented using I/O buses and backplanes using CPU-Memory buses.

Recap: I/O buses

Then we discussed the bus transition protocols which specify the sequence of events and timing requirements in transferring information as synchronous or asynchronous communication. We also discussed bus arbitration protocols — the protocols to reserve the bus by a device that wishes to communicate when multiple devices need the bus access. Here, we noticed that the bus arbitration schemes usually try to balance two factors.

Recap: I/O System

• Bus-priority: the device with highest priority should be serviced first
• Fairness: every device that wants to use the bus is guaranteed to get the bus eventually
• The three bus arbitration schemes are: ✓ Daisy Chain Arbitration ✓ Centralized Parallel Arbitration ✓ Distributed Arbitration

Storage I/O Performance

Now having discussed the basic types of storage devices and the ways to interconnect them to the CPU, we are going to look into the ways to evaluate the performance of storage I/O systems. We know that if a storage device crashes then the prime objective of a storage device should be to remember the original information to make the storage device reliable.

Reliability Improvement

The reliability of a system can be improved by using the following four methods:

• Fault Avoidance – prevent fault occurrence by construction
• Fault Tolerance – providing service complying with the service specification by redundancy
• Error Removal – minimizing the presence of errors by verification
• Error Forecasting – to estimate the presence, creation and consequence of errors by evaluation

Reliability, availability and dependability

The performance of storage I/Os is measured in terms of its reliability, availability and dependability. These terminologies have been defined by Laprie in the paper entitled 'Dependable Computing and Fault Tolerance: Concepts and Terminology', published in the Digest of papers of 15th Annual Symposium on Fault Tolerant Computing (1985).

Dependability

Laprie defined dependability as the quality of delivered service such that reliance can justifiably be placed on this service. The service delivered by a system is its observed actual behavior and the system failure occurs when actual behavior deviates from the specified behavior. A user perceives a system alternating between two states of delivered service:

• Service Accomplishment – service is delivered as specified
• Service Interruption – delivered service is different from the specified service

Quantifying the transitions between service accomplishment and service interruption is the measure of the dependability. The dependability is measured in terms of:

• module reliability, which is the measure of the continuous service accomplishment
• module availability, which is the measure of the swinging between the accomplishment and interruption states of delivered service

💡 Why this matters: Dependability is the overarching concept that combines reliability and availability. Understanding these terms precisely is critical for designing fault-tolerant storage systems.

Measuring Reliability

The reliability of a module is the measure of the time to failure from a reference initial instant. The Mean Time To Failure (MTTF) of a storage module, a disk, is the measure of reliability. The reciprocal of the MTTF is the rate of failure. The service interruption is measured as the Mean Time To Repair (MTTR).

🔑 Definition — MTTF: Mean Time To Failure — the measure of reliability, representing the average time a device operates before failing. 🔑 Definition — MTTR: Mean Time To Repair — the measure of service interruption, representing the average time to repair a failed device. 📐 Formula: Failure Rate = 1 / MTTF 📐 Formula: System Failure Rate = Sum of individual component failure rates

📌 Example: Consider a disk subsystem comprising the following components:

• 10 disks, each with MTTF = 1,000,000 Hrs
• 1 SCSI controller with MTTF = 500,000 Hrs
• 1 SCSI cable with MTTF = 1,000,000 Hrs
• 1 power supply with MTTF = 200,000 Hrs
• 1 fan with MTTF = 200,000 Hrs

Solution: System Failure Rate = 10(1/1,000,000) + 1/500,000 + 1/1,000,000 + 1/200,000 + 1/200,000 = 23/1,000,000 Hrs System MTTF = 1/Failure Rate = 1,000,000/23 = 43,500 Hrs = 5 years

Availability

The availability of a module is the measure of the service accomplishment with respect to the swinging between the two states of accomplishment and interruption. The module availability is quantified as the ratio of the MTTF and Mean Time Between Failure — MTBF (which is equal to the sum of MTTF and MTTR).

📐 Formula: Availability = MTTF / (MTTF + MTTR) = MTTF / MTBF

Network Attached Storages and Reliability

A network provides well-defined physical and logical interfaces to interconnect separate CPU and storage systems at long distances. The networks are capable of sustaining high bandwidth transfer and their file-server Operating system supports remote file access. Hence, the network attached storages are more vulnerable to reliability issues and their dependability requirement is very high.

To improve both the availability and performance of storage systems, disk arrays are introduced, which contain many low-cost disks. The throughput of disk arrays is improved by having high bandwidth disk systems which employ many small disk drives. The throughput is increased by having many small arms on small (3.00" – 1.8") disk drives rather than one long arm on a larger disk (14" – 24").

🔑 Definition — Disk Array: A storage system containing many low-cost disks to improve both availability and performance.

Array Reliability: Example

📌 Example: Reliability of N disks = Reliability of 1 Disk ÷ N Disk system MTTF = 50,000 Hours ÷ 70 disks = 700 hours (drops from 6 years to 1 month!)

Arrays without redundancy are too unreliable to be useful. However, the dependability can be improved by adding redundant disks to the array to tolerate faults.

Redundant Arrays of Disks

In a disk array, files are "striped" across multiple spindles. Adding a redundant disk to achieve high fault tolerance yields high data availability. If a disk fails, the contents are reconstructed from data redundantly stored in the array. The drawbacks of redundant disks are:

• Capacity penalty to store it
• Bandwidth penalty to update

These systems are known as RAID: Redundant Array of Inexpensive Disks or Redundant Array of Independent Disks. There exist several different approaches to include redundant disks in the disk array, classified by a numerical value which identifies the RAID level.

RAID Level Characteristics (for 8 user data disks):

RAID 0 – Non Redundant Striped

RAID 0 is the disk array without any redundant disk. The data is stripped across a set of disks, making the collection appear to the software as a single large disk. Note that the taxonomy RAID 0 is a misnomer as there is no redundant disk, but it is still referred to as RAID due to data striping.

RAID 1: Disk Mirroring/Shadowing

Each disk is fully duplicated onto its "shadow". Targeted for high I/O rate. Whenever data are written to one disk, those data are also written to the redundant disk. If a disk fails, the system goes to the mirror, so there are 8 survivals in this example (provided one disk of mirrored pair fails). It is the most expensive solution: 100% capacity overhead. One logical write = two physical writes.

There are two ways to stripe data with RAID 1:

1. RAID 1+0: Create 4 pairs of disks, each organized as RAID 1, then strip data across the 4 RAID pairs
2. RAID 0+1: Create two sets of 4-disks, each organized as RAID 0, and mirror write to both RAID 0

RAID 3: Bit-Interleaved Parity Disk

Rather than having a complete copy of the original disk, RAID 3 achieves desired dependability by adding enough redundant information to restore the lost information on failure. RAID 3 uses one extra disk, called Parity disk, that holds the check information in case of failure. RAID 3 acts logically as a single high-capacity, high-transfer-rate disk. The arms are synchronized logically and spindles rotationally.

Every read or write access goes to all the disks. For every read access, the parity is computed across the recovery group to protect against hard disk failures. For the RAID 3 shown, there is 33% capacity cost for parity. Wider arrays reduce capacity costs but decrease expected availability and increase reconstruction time.

RAID 4: Block-Interleaved Parity and RAID 5: Distributed Block-Interleaved Parity

Both RAID 4 and RAID 5 use the same ratio of data disk to parity disk as RAID 3, but they access data differently. In the Block-Interleaved Parity RAID 4, the parity disk is associated with each data block, identical to RAID 3. It supports a mixture of small reads, small writes, large reads, and large writes. However, a drawback is that the parity disk must be updated on every write, which is a bottleneck for back-to-back writes.

This bottleneck is resolved in Block interleaved parity RAID 5, where the parity disk is distributed among the blocks. The parity associated with each row of the data block is no longer restricted to a single disk. This allows multiple writes to occur simultaneously as long as the stripe-units are not located in the same disk.

📌 Example — Parallel writes in RAID 5:

• 1st write to block 8 must also access its parity block P2 (two reads from two disks – the 1st and 3rd disks)
• 2nd write to block 5 implies an update in P1 (two reads from two disks – the 2nd and 4th disks)
• Thus, the two writes could occur at the same time in parallel

In RAID 4, both P1 and P2 are on the same disk (5th disk), so it would be a bottleneck and could not be written simultaneously.

RAID 3 vs. RAID 4 and RAID 5

In RAID 3, every access goes to all the disks, while levels 4 and 5 use smaller accesses which allow independent access to occur in parallel. In RAID 4 and RAID 5, error detection information in each sector is checked independently for 'small reads' to see if the data are correct in one sector.

For small writes, RAID 3 reads blocks D1, D2, and D3 before adding Block D0' to calculate the new parity P'. Note that the new data D0 comes directly from CPU, so disks are not involved in reading it.

For small writes in RAID 4/5, the old value of D0 is read (1: Read) and compared with new value D0' to see which bit will change. Once checked, the old parity P is read and corresponding bits are changed to form P' using logical EX-ORs.

📌 Example — RAID 4/5 Small Write Efficiency:

• RAID 3: 3 disk reads (D1, D2, D3) and 2 disk writes (D0', P') involving all disks
• RAID 4/5: 2 disk reads (D0, P) and 2 disk writes (D0', P'), each involving just 2 disks
• One (1) Logical Write in RAID 4 and RAID 5 is equivalent to 2 Physical Reads and 2 Physical Writes

⭐ Key Takeaways

The most critical concept is the trade-off between reliability and redundancy in storage systems — adding more disks increases throughput but decreases reliability, requiring redundant disks to restore dependability. Understanding the distinction between MTTF (reliability measure), MTTR (repair measure), and availability (MTTF/MTBF) is essential for quantifying storage system performance. RAID levels represent different approaches to balancing capacity overhead, fault tolerance, and performance — RAID 1 offers 100% overhead with mirroring, while RAID 3/4/5 use parity disks with lower overhead but different write performance characteristics. The key difference between RAID 4 and RAID 5 is that RAID 5 distributes parity across disks to eliminate the parity disk bottleneck, enabling parallel writes. For exams, remember the system reliability calculation formula (sum of failure rates = 1/MTTF), the relationship between disk count and reliability, and the specific read/write characteristics of each RAID level.

🧠 Quick Revision Questions

1. A disk subsystem has 10 disks (MTTF = 500,000 Hrs each), 1 controller (MTTF = 250,000 Hrs), and 1 power supply (MTTF = 100,000 Hrs). Calculate the system MTTF.
2. If a system has MTTF = 10,000 hours and MTTR = 100 hours, what is its availability?
3. Why is RAID 0 considered a misnomer, and what is the primary benefit of using it?
4. In RAID 4/5, why does one logical write require only 2 disk reads and 2 disk writes instead of accessing all disks like in RAID 3?
5. What is the fundamental difference between RAID 4 and RAID 5 that allows RAID 5 to perform multiple small writes simultaneously?

📘 Lecture 41 — Networks and Clusters (Networks: Interconnection and Topology)

📖 Overview: This lecture shifts focus from single computer architecture to interconnection networks, explaining how computers are connected to form networks. It covers fundamental network concepts, communication models, performance parameters, physical media, and various network topologies, establishing the foundation for understanding clusters and internetworking.

🗂️ Topics Covered

The lecture begins with a recap of I/O systems, storage dependability, and RAID levels before introducing interconnection networks. It covers network communication models, message formats, software protocols, performance parameters (bandwidth, latency), physical media (twisted pair, coaxial cable, fiber optics), bus-based networks, and both centralized (crossbar, multistage Omega) and distributed (ring, 2D grid/torus) switch topologies.

📝 Lecture Summary

Recap: I/O Systems and Storages

The lecture begins by concluding the discussion on storage I/Os and communication I/Os. The dependability, reliability, and availability of storage I/Os significantly influence overall computer system performance. Dependability is the quality of delivered service such that confidence can be placed on this service, measured by quantifying transitions between service accomplishment and service interruption. Reliability measures continuous service accomplishment or time to failure from a reference initial instant. Availability measures service accomplishment with respect to swinging between accomplishment and interruption states.

Recap: I/O and Storage Systems & Network Attached Storages

Storages interface with processors using channel, backplane, and network interconnects. Networks sustain high bandwidth transfers, and their file-server operating system supports remote file access. Network Attached Storages (NAS) have high dependability but are vulnerable to reliability issues. To improve availability and performance, disk arrays are introduced where data is striped across a set of disks, making the collection appear as a single large disk. Throughput improves due to many small disk drives having high bandwidth. The drawback is that with N devices, reliability decreases to 1/N of a single device.

Recap: Redundant Arrays of Disks

RAID (Redundant Array of Inexpensive Disks) improves disk array dependability by adding redundant disks to tolerate faults. Different RAID levels exist:

• RAID 0: Disk array without redundant disks, but employs data striping
• RAID 1: Disk Mirroring — each disk is fully duplicated onto its "shadow"
• RAID 3: Bit-Interleaved Parity Disk — uses one parity disk per group of data, parity computed across recovery group to protect against hard disk failures
• RAID 4: Block Interleaved Parity — parity disk associated to each data block, supports both small and large reads/writes
• RAID 5: Block Interleaved Distributed Parity — parity associated to each data block, data blocks distributed among different disks in each row, allowing simultaneous read/write of multiple blocks

🔑 Definition — RAID: A disk array with redundant disks added to tolerate faults, classified by numerical levels.

Interconnection Networks

The lecture shifts focus from single computer architecture to connecting computers into networks. Standard components include:

• Computer nodes (host or end system)
• H/W and S/W interface
• Links to the interconnection network
• Interconnection networks (network or communication subnet)

The coordinated use of interconnected computers in a machine room is a cluster. Connecting two or more interconnection networks is called Internetworking, with the Internet being the prime example. Internetworking relies on communication standards to convert information between network types.

Based on nodes and proximity, interconnections are designated as:

• Local Area Network (LAN): Hundreds of computers in a building, up to a few kilometers
• Wide Area Network (WAN): Thousands of computers worldwide, thousands of kilometers — ATM (Automatic Teller Machine) is a typical example
• System Area Network (SAN): Hundreds of nodes within a machine room, less than 100 meters — this is basically the cluster

Moore's Law has contracted the network definition to include interconnection of components within a single computer.

Networks Communication Model

A simple model shows two machines connected via two unidirectional wires with a FIFO (queue) at each end to hold data. Machine A sends a request to B to get data; B responds with a reply containing the data. Messages contain extra information beyond data.

Networks Message Format

A basic message format uses:

• A 1-bit header specifying request (header=0) or reply (header=1)
• The request carries the address of the data word
• The reply carries the data word

Networks Interconnection Software

Interconnection networks involve software to establish communication. The network software:

• Cooperates with the OS to distinguish between processes on other networks
• Protects processes running on networks
• Ensures reliable delivery — message is neither distorted nor lost in transit

For reliability, the message format is modified by adding an error detection code (checksum or CRC) and using a 2-bit header. The sender calculates and adds this information; the receiver checks it and sends an acknowledgment if the test passes. The sender activates a timer each time a message is sent and copies data into an operating system buffer to resend if acknowledgment doesn't arrive before timer expiry.

Networks Interconnection Protocol

The acknowledgment protocol ensures reliable communication, but additional issues include:

• Different byte-order conventions (Big Endian or Little Endian) between manufacturers
• Duplicate delivery prevention when the original message is delayed in the network
• Sequence numbers to maintain message order
• Feedback mechanism when receiver's FIFO is full

Networks Performance Model

Network performance can be modeled at any level (chip, PCB, cluster) through interconnection performance parameters:

• Bandwidth: Maximum rate at which the network can propagate information
• Time of Flight: Time for the first bit from departure to arrival at receiver
• Transmission Time: Time for message to pass through network, excluding time of flight — time between first and last bit arriving
• Transport Latency: Sum of time of flight and transmission time
• Sender Overhead: Time for processor to inject message into network (hardware + software)
• Receiver Overhead: Time for receiver to pull message from network (hardware + software)

📐 Formula: Total Latency = Sender Overhead + Time of Flight + (Message Size / Bandwidth) + Receiver Overhead

Interconnection Network Media Hierarchy

Similar to memory hierarchy, interconnect media varies in cost, performance, and reliability based on maximum distance between nodes.

Twisted Pair (of Copper Wire): Two insulated copper wires (~1mm thick) twisted together to reduce electrical interference. Original telephone lines give a few megabits/sec (Level-1 or Category-1 UTP). Cat-3 UTP supports 10M bits/sec Ethernet; Cat-5 supports 100M bits/sec up to 1000M bits/sec over 100 meters.

Coaxial Cable: A stiff single copper wire surrounded by insulating material covered by cylindrical woven sheath. A 50 ohm base-band coaxial cable delivers 10M bits/sec over a kilometer. Offers high bandwidth and good noise immunity over several kilometers.

Fiber Optics: One-way (simplex) media — two fibers used for full-duplex. Contains a glass fiber core surrounded by cladding to confine light, covered by a protective buffer. Uses LED or laser as transmitter and photo diode as detector. Two forms:

• Multimode Fiber: Inexpensive light source, wavelength larger than light, wider dispersion, limited to ~1000M bit/sec over hundreds of meters or 100M bit/sec over a few kilometers
• Single-mode Fiber: More expensive lasers, single wavelength, transmits G bits/sec for hundreds of kilometers. Drawbacks: difficult connectors, less reliable, more expensive, bending restrictions

Interconnection Networks (Bus-Based)

Interconnecting hundreds of computers is more challenging. The bus-based LAN or Ethernet is the simplest way to interconnect more than two computers sharing a single media. Processors and memory connect through a "bus." It is simple and cost-effective for small-scale multiprocessors, but bus bandwidth limits the number of processors. Coordination and arbitration are required as multiple computers may need the same media simultaneously.

For small networks (a few hundred meters), centralized arbitration may be used. For networks spanning kilometers, distributed arbitration is needed. Arbitration works on "look before you leap," but looking first doesn't guarantee success — if two nodes transmit simultaneously, collision occurs. Techniques to avoid collision include collision detection and token passing. An alternative to sharing media is switching, where switches provide dedicated lines to all destinations, enabling faster point-to-point communication. Switches are also called data switching exchanges, multistage interconnection networks, or interface message processors (IMPs).

Network Topology

The most popular switch-based topologies are classified as:

• Centralized Switch Topologies: Crossbar, Multistage
• Distributed Switch Topologies: 2D Grid/Mesh, 2D Torus, Hypercube Tree

Crossbar Switch Topology

A crossbar switch is a non-blocking switch that facilitates unidirectional interconnection of all inputs to any output. It uses n² switches where n is the number of processors. Links are unidirectional. Routing depends on addressing style:

• Source-based routing: Message specifies the path to destination; includes sequence of out-bound arcs; once an arc is picked, that portion is dropped from the packet
• Destination-based routing: Message contains destination address; a program in the switch decides from a routing table which port to take

A crossbar switch offers low latency and high throughput.

Multistage Interconnection Topology

An intermediate class between crossbar and bus-based networks — more scalable than bus in performance, more scalable than crossbar in cost. Built from small (e.g., 2×2 crossbar) switch nodes with regular interconnection patterns. The Omega Topology is a typical implementation with:

• Each switch is a 2×2 crossbar
• Has log₂ n identical stages
• Uses n/2 × log₂ n switches versus n² in crossbar

Omega Interconnection Topology: Connections depend on communication patterns and may cause blocking. For example, a message from P1 to P7 blocks while waiting for a message from P0 to P6 as they follow the same path.

Fully Connected Switching Network

A distributed switching network distributes switching throughout the network. A fully connected network interconnects all nodes to each other.

Terminology of Distributed Network

• Degree: Number of links to each node
• Diameter: Number of nodes between source and destination

For a fully connected network:

• Diameter = 1
• Degree = K - 1 (K = number of nodes)
• Links = K × (K-1) / 2
• Bisect = K × K / 5

Distributed Switch Topologies — Ring Network

The simplest low-cost alternative to fully interconnected networks is a ring network. A small switch is placed at every computer. Only two nodes connect to a particular node, so messages must hop through intermediate nodes until they reach the destination. For example, connecting the 1st node to the 4th node requires hopping through the 2nd and 3rd nodes. A variation is the Token Ring, where a single token goes around the ring to determine which node can send — a node can send only when it gets the token.

Ring network measures:

• Degree: 2
• Diameter: N/2
• Bisect: 2
• Bandwidth: N
• Latency: N/2

2D Grid and 2D Torus Mesh

Connecting switches associated with each node to switches on the left, right, up, and down, and connecting top and bottom rows gives a grid structure. Connecting the switches of left and right columns gives 2D Torus Mesh.

⭐ Key Takeaways

1. Network performance is quantified by total latency = Sender Overhead + Time of Flight + (Message Size / Bandwidth) + Receiver Overhead — this formula is essential for comparing network designs.
2. Three levels of networks exist based on scale: LAN (building), WAN (world), and SAN (machine room/cluster), each with different distance and node constraints.
3. Crossbar switches offer non-blocking, low-latency interconnects but scale poorly (n² switches), while multistage networks like Omega offer better cost scaling (n/2 × log₂ n switches) but can suffer from blocking.
4. Physical media (twisted pair, coaxial, fiber optics) trade off cost, bandwidth, distance, and reliability, with single-mode fiber offering the highest performance at highest cost.
5. Distributed topologies (ring, 2D grid/torus) balance cost and performance — ring has degree 2 but diameter N/2, while fully connected has diameter 1 but K-1 links per node.

🧠 Quick Revision Questions

1. What is the formula for total latency of a message in a network, and what does each term represent?
2. How does RAID 5 differ from RAID 4 in terms of parity disk placement and data distribution?
3. What is the difference between source-based routing and destination-based routing in a crossbar switch?
4. For a ring network with N nodes, what are the degree, diameter, and bisect width?
5. Why does the Omega multistage topology use fewer switches than a crossbar, and what trade-off does this create?

📘 Lecture 42 — Networks and Clusters (Networks Topology and Internetworking ... Cont’d)

📖 Overview: This lecture continues the discussion on network topologies, focusing on centralized switching topologies like Multistage and Omega networks, then moves to distributed switch topologies including Linear Array, Ring, 2D Mesh, Torus, Tree, and Hypercube networks. It also introduces internetworking and clusters, explaining how independent networks communicate reliably.

🗂️ Topics Covered

The lecture covers the continuation of switch topologies, including Multistage Interconnect Networks and Omega Network topology with connection rules, Butterfly Network, then transitions to Distributed Switch Networks with performance measure criteria. It details various distributed switch topologies like Linear Array/Ring, Fully Connected, 2D Mesh and Torus, Tree and Fat Tree networks, Hypercube and K-ary n-cube topologies. The lecture concludes with a comparison of network topologies based on bisection bandwidth and cost, followed by brief discussions on internetworking and clusters.

📝 Lecture Summary

Recap: Lecture 41

The recap reviews that a generic interconnection network consists of computer nodes, H/W and S/W interfaces, links, and a communication subnet. Interconnections are classified as LAN, WAN, and SAN based on node count and distance. The communication model uses two unidirectional wires with FIFO queues, and performance is defined by latency as the sum of sender overhead, time to flight, receiver overhead, and message size/bandwidth. Bus-based LANs share a single media but require coordination, while switches provide dedicated lines for faster point-to-point communication. The Crossbar switch is a non-blocking switch using n² switches for n processors, with either source-based or destination-based routing.

Multistage Interconnect Network

Continuing centralized switching topologies, an intermediate class called Multistage network topology lies between crossbar and bus-based networks. It is built from multiple stages of switch boxes, with each stage containing small crossbar switches allowing straight or cross connections. Its performance and cost are more scalable than bus-based networks. The number of identical stages (Nₛ) for n nodes with m x m switches is:

🔑 Definition — Multistage Network: A centralized network topology built from multiple stages of crossbar switches to interconnect all nodes, with cost and performance scalable between crossbar and bus-based networks. 📐 Formula: Nₛ = logₘ n → The number of stages equals the logarithm base m (switch size) of n (number of nodes). 📐 Formula: Total switches = n/m × logₘ n → The total number of switches in a multistage network, giving cost O(n log n) compared to O(n²) for crossbar.

Omega Topology: Multistage Interconnect

The Omega Network is a typical multistage network implementation. For 8 nodes addressed with 3-bit code, it uses 3 stages (log₂ 8 = 3) of 2x2 crossbar switches, with 4 switches per stage (8/2 = 4). To find the connection pattern, XOR the source and destination addresses. For example, Src (010) → Dest (110): XOR results in 100, meaning Cross at stage S₂, Straight at S₁, Straight at S₀.

🔑 Definition — Omega Network Connection Rule: For stage i, if the source and destination differ in the iᵗʰ bit, connection is Cross; otherwise, connection is Straight. 📌 Example: Source 010 → Destination 110. XOR = 100. Since bit 2 differs (0 vs 1), stage S₂ is Cross; bits 1 and 0 are same (1 vs 1, 0 vs 0), so stages S₁ and S₀ are Straight.

Characteristics of Omega

The Omega network is a blocking network because there exists only a single path from source to destination, unlike the non-blocking crossbar. For example, path 010→110 and path 110→100 have blockage at S₂ for 110 as it must wait for 010 to pass, otherwise collision occurs. To minimize collisions and improve fault tolerance for high reliability, extra pathways can be added.

Butterfly Network

An alternative to Omega topology is the Butterfly Network. Regardless of source address, for destination a₂a₁a₀, the iᵗʰ stage switch sends to the upper port if aᵢ = 0 and to the lower port if aᵢ = 1. 💡 Why this matters: The Butterfly network provides a different routing strategy compared to Omega, offering alternative path determination based solely on destination bits.

Distributed Switch Networks

Distributed switching networks have switches distributed throughout the network, allowing interconnection of one node to either all nodes or a limited number of nodes. A network where each node interconnects all nodes is called a Fully connected network.

🔑 Definition — Interconnect Performance Measure Criteria:

• Latency: Number of links; should be small.
• Bandwidth: Number or length of messages; should be large.
• Node Degree: Number of links connected to a node.
• Diameter: Maximum distance between any two processors (maximum latency measure).
• Bisect: Imaginary line dividing the interconnect into two equal halves.
• Bisection Bandwidth: Sum of bandwidth of lines crossing the bisection line, measuring communication volume between two halves of the network.

Linear Array / Ring

The simplest distributed switch topology is a Linear Array, where a small switch at every node connects node i to node (i-1) and (i+1) except at endpoints. Messages hop along intermediate nodes until reaching the destination. The Ring network is formed by connecting the 1ˢᵗ and nᵗʰ nodes. A variation called Token Ring uses a single token going around the ring to determine which node can send.

Performance metrics: Cost is O(n) (cheap), overall bandwidth is high, but latency is high at O(N).

🔑 Definition — Token Ring: A ring network variation where a single slot (token) circulates to determine which node is allowed to send a message.

Performance Comparison: Array vs Ring

• Linear Array: Degree = 2, Diameter = N, Bisection width = 1, Bandwidth = N-1, Mean Latency = N/2, Asymmetric, Heterogeneous
• Ring: Degree = 2, Diameter = N/2, Bisection Width = 2, Bandwidth = N, Latency = N/2, Symmetric, Homogeneous

Fully Connected

A Fully connected network is symmetric but expensive, equivalent to crossbar. Every node has a direct link to all other nodes. Performance metrics: Diameter = 1, Degree = n-1, Links = n × (n-1)/2, Bisects = n × n/5, Bisection bandwidth proportional to (n/2)².

2D Mesh and 2D Torus

2D Mesh or Grid is an asymmetric network where nodes are arranged in an array structure. Each switch has one port for the processor and four ports for nearest-neighbor nodes (left, right, up, down), forming a NEWS communication pattern (North, East, West, South). Connecting unused ports of top/bottom rows and left/right columns with wraparound links forms a 2D Torus.

Performance metrics for n-node 2D Mesh/Torus: Degree = 4, Diameter = 2√N, Bisection width = √N, Bandwidth = N, Asymmetric.

Tree Network Topology

In a Tree Network, switches at each node have ports equal to the number of branches plus one for the processor. For a Binary Tree with two branches per node: Cost is O(N) (cheap), Degree = number of branches (1, 2, 3...), Latency = O(log_deg N), Diameter = 2log_deg N, Bisection Width = 1.

Bottlenecks: The root and branch nodes are bottlenecks. For example, leaf-nodes 1,2 of branch node 9 and 3,4 of branch node 10 can interconnect simultaneously, but leaf-nodes 1,3 and 2,4 cannot due to collision at branch nodes 13, 9, and 10.

Fat Tree Network

To avoid root bottlenecks, multiple paths are provided between nodes in a Fat Tree. Processor-memory nodes connect through multiple stages of crossbars (2×2, 4×2+2, 8×4+4, etc.). This 3D switching increases bandwidth via extra links at each level. The CM-5 uses the Fat Tree concept as a centralized switching network.

Hypercube Network Topology

The Hypercube (binary n-cube) is an n-dimensional interconnect for 2ⁿ nodes. For 16 nodes (16 = 2⁴, n=4), it's a 4D structure. It requires n ports per switch plus one for the processor, with n nearest neighbor nodes. This minimizes hops with latency O(log₂ N).

Performance metrics: Nodes = N = 2ⁿ, Degree = n, Diameter = n, Links = n × 2⁽ⁿ⁻¹⁾, Bisection width = 2⁽ⁿ⁻¹⁾. Other topologies like tree or mesh can be embedded in hypercube. It has good bisection bandwidth but is difficult to layout in 3D space. Popular in early message passing machines like Intel iPSC, NCUBE.

K-ary n-cube Network Topology

The generalization of hypercube is to interconnect k nodes of n-cubes in a string. Total nodes: N = kⁿ. For example, 64 = 4³ (4-ary 3-cube). This structure allows wider channels but requires more hops.

Comparing Network Topologies

Comparison for 64-node network:

Bus is the standard reference at unit cost; all transfers take time units equal to number of messages. Fully connected has maximum links and ports, all transfers in parallel taking unit time. Ring topology nodes have differing distances.

Internetworking

Internetworking deals with communication of computers on independent and incompatible networks reliably and efficiently. Software standards are enabling technologies, with TCP/IP (Transmission Control Protocol/Internet Protocol) being the most popular internetworking standard. Detailed discussion is beyond this course scope.

🔑 Definition — Internetworking: The process of enabling communication between computers on independent and incompatible networks reliably and efficiently through software standards like TCP/IP.

Cluster

Cluster refers to a group of interconnected computers working together as a single system. The lecture text shows the same definition as internetworking, suggesting clusters utilize internetworking principles for their communication infrastructure.

⭐ Key Takeaways

The critical points for exam preparation are: first, understand that Multistage networks provide scalable cost at O(n log n) compared to O(n²) for crossbar, with the Omega network being a blocking network using XOR-based routing where connection is Cross if source and destination bits differ at that stage. Second, master the performance parameters (latency, bandwidth, node degree, diameter, bisection bandwidth) and their values for each distributed topology. Third, remember that Linear Array has diameter N while Ring has diameter N/2 with symmetric structure, 2D Mesh/Torus has degree 4 and diameter 2√N, and Hypercube has degree n and diameter n with 2ⁿ nodes. Fourth, know the cost-performance tradeoffs: bus is cheapest but slowest, fully connected is fastest but most expensive, and multistage/torus offer balanced solutions. Finally, recognize that internetworking relies on TCP/IP standards and clusters represent groups of interconnected computers working collectively.

🧠 Quick Revision Questions

1. How do you calculate the number of stages and total switches in a Multistage network with n nodes and m×m switches?
2. What is the connection rule for Omega Network when routing from source to destination, and why is Omega considered a blocking network?
3. What are the six performance measure criteria for distributed switch networks, and what does each measure?
4. Compare the diameter, degree, and bisection width of Linear Array, Ring, 2D Torus, and Hypercube for a 64-node network.
5. What is the primary internetworking standard mentioned, and what is the purpose of a Fat Tree network?

📘 Lecture 43 — Networks and Clusters (Internetworks and Clusters)

📖 Overview: This lecture concludes the module on Networks and Clusters by discussing how multiple independent networks are connected together through internetworking, specifically focusing on the TCP/IP protocol suite and the OSI 7-layer model. It then transitions to a detailed study of computer clusters, their design challenges, and four practical cluster design examples, providing a comprehensive understanding of how interconnected systems are built and evaluated in modern computing environments.

🗂️ Topics Covered

The lecture begins with a recap of interconnection networks, communication models, software, protocols, and network topologies. It then introduces internetworking, explaining how independent and incompatible networks communicate reliably using protocol families. The OSI 7-layer model and the TCP/IP protocol suite are detailed, followed by an introduction to clusters as System Area Networks. The lecture concludes with four practical cluster design examples comparing uniprocessor, 2-way SMP, and 8-way SMP configurations, including considerations for local disk, storage area networks, other costs, and transaction processing.

📝 Lecture Summary

Recap:

The lecture begins by recapping the previous two lectures on Networks and Clusters. A generic interconnection network comprises Computer nodes, H/W and S/W interface, Links to the interconnection network, and a Communication subnet. The interconnect communication model connects two machines via two unidirectional wires with a FIFO (queue) at the end to hold data. Communication software separates the header and trailer from the message and identifies requests, replies, acknowledgments, and error checking codes. Communication protocols provide the sequence of steps for reliable communication.

The lecture revisits properties and performance of network media (unshielded twisted pair (UTP), coaxial cable, and fiber optics) and the formation of bus-based and switch-based communication subnets. Bus-based subnets share common media where arbitration is the bottleneck, while switch-based networks provide dedicated lines and facilitate faster point-to-point communication. Switch-based networks are classified as centralized and distributed switch networks. Performance of a distributed network is measured by Latency (number of Links between source and destination), Bandwidth (number or length of messages passing per second), Degree (number of links connected to a node), Diameter (number of nodes between source and destination, a measure of maximum latency), Bisection (an imaginary line dividing the interconnect into two equal halves), and Bisection Bandwidth (the volume of communication allowed between any two halves of the network).

The recap also covers the Multistage Switch network, built from large switch boxes each containing small crossbars, whose performance lies between non-locking crossbar and bus-based networks. Distributed-switch interconnects were categorized as fully-connected and partially-connected, symmetric or asymmetric interconnects, with topologies like linear array, ring, 2D mesh/torus, and hypercube studied. The relative cost and performance of these topologies for 64 nodes were compared in a table showing Bisection Bandwidth (Bus: 1, Ring: 2, 2D Torus: 16, Fully Connected: 1024) and Total Links (Bus: 1, Ring: 128, 2D Torus: 192, Fully Connected: 2080).

Internetworking

So far, the discussion focused on interconnection networks. Now, the lecture discusses the connection of two or more interconnection networks, called Internetworking, with the Internet being a typical example. Internetworking deals with the communication of computers on independent and incompatible networks reliably and efficiently. It relies on communication standards to convert information from one kind of network to another. These standards are composed of a hierarchy of layers, where each layer is responsible for a portion of overall communication. Each computer, network, and switch implements its layer of standards, called Protocol Families or Protocol suites, which facilitates applications to work with any inter-connection.

OSI: 7- Layer Model

The Open Systems Interconnect (OSI) developed a 7-layer model describing a network as a series of layers. The Application layer (layer 7) is at the top, and the Physical layer (layer 1) is at the bottom, with Presentation, Session, Transport, Network, and Data Link layers in between.

🔑 Definition — Application Layer (Layer 7): Used for applications specifically written to run over the network, e.g., Network File System (NFS).

🔑 Definition — Presentation Layer (Layer 6): Translates from application to network format and vice versa.

🔑 Definition — Session Layer (Layer 5): Establishes, maintains, and ends the sessions across the network.

🔑 Definition — Transport Layer (Layer 4): Facilitates additional connection below the session layer; the protocol is referred to as the Transmission Control Protocol (TCP).

🔑 Definition — Network Layer (Layer 3): Translates the network address and names to their physical address, e.g., computer name to Media Access Control (MAC); the layer-3 protocol is referred to as Internet Protocol (IP).

🔑 Definition — Data Link Layer (Layer 2): Turns packets into raw bits and, at the receiving end, turns bits into packets; an example protocol is Ethernet.

🔑 Definition — Physical Layer (Layer 1): Transmits raw bit-stream over physical cable/media; IEEE 802 is a typical example physical layer protocol.

TCP/IP Families

The protocol family divides responsibilities among layers, with each layer offering services needed by the layer above. The Transmission Control Protocol/Internet Protocol (TCP/IP) is the most popular internetworking standard and the basis of the Internet.

The protocol at each level is implemented by adding headers and trailers at the sending layer and removing them at the receiving layer. The original message from the top layer includes a header and trailer sent by the lower-level protocol. The next-lower protocol in turn adds its own header (and possibly trailer) to the message, and so on. If the message is too large for a particular layer, it is broken into smaller messages. This division and addition of headers/trailers continues until the message descends to the physical transmission media.

At the receiving end, each level of the protocol family, from bottom to top, checks the message at its level, removes its header and trailer, and passes it to the next higher level. The message is rebuilt by putting the pieces together. This nesting of protocol layers is referred to as the Protocol Stack, reflecting the Last-in First-out nature of addition and removal of headers and trailers.

A typical TCP/IP datagram has standard IP and TCP headers that are 20 bytes each, stacked as shown in the lecture's figure. The length can optionally be increased, specified by the length field (L). The length of the whole datagram is identified by a separate field 'Length' in the IP header, while the TCP header includes this information in the 'sequences number field'.

The lecture notes that detailed discussion on TCP/IP is beyond the scope of this course, and interested students may consult literature on Computer Networks and Internetworking.

Clusters – System Area Networks

The coordinated use of interconnected computers in a machine room is referred to as a cluster or System Area Network. Massively parallel machines providing high bandwidth can be built from off-the-shelf components instead of custom machines or networks. A cluster, a collection of desktop computers and disks, offers low-cost computing infrastructure that can tackle very large problems and applications such as databases, file servers, Web servers, simulation, and multiprogramming/batch processing.

Clusters face performance confronts: Non-standard connections and Division of memory.

🔑 Definition — Non-Standard Connection Confront: Multiprocessors are usually connected via a memory bus with high bandwidth and low latency, but clusters are connected using the I/O bus of the computer, thus having large conflicts at high speed.

🔑 Definition — Division of Memory Confront: A large single program running on a cluster of N machines requires N independent memory units and N copies of the operating system. In contrast, a shared address multiprocessor allows using almost all memory in the computer.

Despite these challenges, clusters have advantages in dependability and scalability. The weakness of separate memories for program size is a strength in terms of system availability and expandability (scalability). As clusters consist of independent computers connected through LAN, and cluster software runs on top of the local operating system, it is easier than a multiprocessor to replace any computer without bringing down all computers in the cluster. This offers high dependability and scalability, making clusters attractive to worldwide web service providers.

Cluster Design Examples

To study practical aspects of cluster designs, the lecture discusses different cluster designs comprising 32 processors, 32 GB DRAM, and 32 or 64 disks. The designs consider P-III processors operating at 700 MHz and 1000 MHz with L2 cache ranging from 256 KB to 1 MB. Due to larger die size, the processor chip price with 1 MB cache is double that with 256 KB cache, but the objective is to minimize cost for a desired performance target.

Four cases are considered:

1. Cost of cluster hardware with local disk
2. Cost of cluster hardware with disk over SAN (System or Storage Area Network)
3. Cost of cluster options that is more realistic
4. Cost and Performance of a cluster for transaction processing

Example 1: Cost of cluster hardware with local disk Three logical organizations are considered: a. Uniprocessor Cluster: 32 xSeries 300 computers (for 32 processors). Maximum memory is 1.5 GB per computer, easily allowing 32 GB (1x32). Each computer has 2 disk drives of 36.4 GB, yielding 32 x 2 x 36.4 = 2330 GB. 32 cables are available for the 1GB Ethernet switch. Since the switch has 30 ports, 2 switches are used, connected together with 4 cables, leaving 56 ports for 32 computers. A standard rack (19" x 30" x 72") accommodates 32 uniprocessor computers and 2 switches (34 rack units). This design is cost-effective.

b. 2-way SMP Cluster: Using 2-processor xSeries 330 computers, everything is halved. 32 processors need only 16 computers. A single 30-port switch works as there are 16 cables. Rack size is 18 RU instead of 44 RU, less than half the standard size.

c. 8-way SMP Cluster: Using 8-processor xSeries 370 computers, only 4 computers are used (4 x 8 = 32 processors). Maximum memory is 32 GB, but only 8 GB per computer is needed, so an 8-port switch is sufficient. At 2 disks per computer, 4 computers can hold 8 disks with maximum capacity of 73.4 GB each, so an expansion storage box (up to 14 disks) and 2 racks are needed.

Comparison of 3-Cluster Designs: The price comparison for 32 processors, 32 GB memory, and 2.3 TB disk shows that network cost decreases as the size of the SMP increases because memory buses supply more inter-processor communication. The 4 of the 8-way SMP cost more than 32 Uniprocessor computers.

Example 2: Cost of cluster hardware using SAN for disks Using local disks reduces cost and space but offers problems: no protection against single disk failure, and state in each computer must be managed separately, resulting in system-down on disk failure. To overcome this, a RAID controller and Fiber Channel Arbitrated Loop (FC-AL) are used as the storage area network (SAN). All SCSI disks are replaced with FC-AL disks behind the RAID storage server. FC-AL can be connected in a loop with up to 127 devices. The price comparison shows that SAN cost also shrinks as servers increase in the number of processors per computer.

Example 3: Cluster design considering other costs The first two designs considered hardware cost only, but software (database) cost and hardware maintenance cost (operator cost) were not considered. Other costs include backup tapes and space to house servers. A complete comparison shows that 2-way SMP using SAN is lowest in total price. Notably, over 3 years, the cost of the operator will be more than the cost of hardware, so the purchase cost of old computers must be reduced to reduce overall cost.

Example 4: Cluster design for transaction processing Using 32 P-III processors with the same IBM computer building block, key differences are:

• Disk Size: Small and fast disks are used as this structure cares more about I/Os per second (IOPS).
• RAID: No RAID is required as the performance benchmark doesn't include human cost.
• Memory: Maximum DRAM is packed into servers, so each of the four 8-way SMPs has 32 GB, yielding 128 GB.
• Processor: 900 MHz P-III with 2 MB L2 cache is used.

The cost-performance analysis shows that almost half of the cost is in software, installation, and maintenance. The lecture concludes that as the purchase cost is less than half the cost of ownership, the cost of hardware solves only a part of the problem.

Summary

The module on Networks and Clusters covered the formation of generic interconnection networks comprising computer nodes (host or end system), H/W and S/W interface, links to the interconnection network, and communication subnet. Interconnections are designated as Local Area Network (LAN), Wide Area Network (WAN), and System (or Storage) Area Network (SAN).

The interconnect communication model shows two machines connected via two unidirectional wires with a FIFO (queue) at the end. Communication software separates header and trailer from the message. Communication protocols suggest steps for reliable communication. Network performance defines message latency as the sum of sender overhead, time to flight, receiver overhead, and the ratio of message size to bandwidth.

The Multistage Switch lies between crossbar and bus-based networks. The number of identical stages (Ns) of large switch boxes, each having m x m crossbar switches, in a network with n nodes, is equal to logm n, and the switches per stage is n/m. The cost of a multistage switch network is O(n log n), considerably smaller than a crossbar network's O(n2) for large n. Examples are Omega and Butterfly networks.

Distributed-switch interconnect topologies include linear array, ring, 2D mesh/torus, and hypercube. The lecture today discussed internetworking, i.e., the connection of two or more interconnection networks to communicate reliably and efficiently. Internetworking relies on communication standards composed of a hierarchy of layers. The Transmission Control Protocol/Internet Protocol - TCP/IP is the most popular internetworking standard. The protocol at each level is implemented by adding headers and trailers at the sending layer and removing at the receiving layer.

After introducing internetworking, the lecture discussed computer clusters, which are the coordinated use of interconnected computers in a machine room. Clusters face challenges of Non-standard connections and Division of memory, but have advantages in dependability and scalability. The practical aspects of cluster designs were studied through four examples.

⭐ Key Takeaways

Internetworking connects independent, incompatible networks reliably through layered communication standards like the OSI 7-layer model and TCP/IP protocol suite, where each layer adds or removes headers/trailers in a protocol stack. Clusters are cost-effective, scalable, and dependable systems built from off-the-shelf components connected via I/O buses, though they face challenges from non-standard connections and divided memory. In cluster design, network cost decreases as SMP size increases because memory buses handle more inter-processor communication, but larger SMPs can be more expensive overall. For transaction processing, maximizing IOPS with small, fast disks and packing maximum DRAM is critical, while software and maintenance costs often exceed hardware costs over a system's lifetime. The multistage switch network offers a cost-efficient O(n log n) interconnect solution that balances performance between crossbar and bus-based networks.

🧠 Quick Revision Questions

1. What are the four components of a generic interconnection network?
2. What is internetworking, and why does it rely on communication standards composed of a hierarchy of layers?
3. What are the two main performance confronts (challenges) of clusters compared to multiprocessors?
4. In the cluster design examples, why does network cost decrease as the size of the SMP increases?
5. What key insight does the fourth cluster design example (for transaction processing) reveal about the total cost of ownership of a cluster?

📘 Lecture 44 — Putting It All Together (Case Studies)

📖 Overview: This lecture serves as a capstone, analyzing three real-world advanced computer architectures: the PowerPC 750, the PowerPC 970 FX, and the Intel Pentium VI (P6). By studying these specific implementations, all the theoretical concepts of superscalar, out-of-order, and speculative execution are brought together to show how they work in practice and how different design choices impact performance.

🗂️ Topics Covered

This lecture provides detailed case studies of three advanced microarchitectures: the PowerPC 750, a 32-bit RISC superscalar processor with six execution units and out-of-order completion; the PowerPC 970 FX, a 64-bit deeply pipelined implementation with aggressive branch prediction and out-of-order execution; and the Intel Pentium VI (P6), which introduced Intel's dynamic execution micro-architecture with an in-order fetch/decode, out-of-order dispatch/execute, and in-order retire unit.

📝 Lecture Summary

PowerPC 750 - General

The PowerPC 750 is a high-performance implementation of the 32-bit portion of the PowerPC architecture, a reduced instruction set computer (RISC) microprocessor. It provides 32-bit effective addresses for integer data types (8, 16, and 32 bits) and floating-point data types (32 and 64 bits). Its superscalar architecture features six execution units and two register files, allowing it to fetch up to four instructions per cycle from the instruction cache, dispatch as many as two instructions per clock, and execute up to six instructions per clock.

PowerPC Instructions are encoded as single-word (32-bit) with consistent formats across all instruction types, permitting efficient decoding in parallel with operand accesses. This fixed instruction length greatly simplifies instruction pipelining. Instructions are categorized as: Integer (arithmetic, compare, logical, rotate, shift), Floating-point (arithmetic, multiply/add, rounding, conversion, compare, status/control), Load/store (integer and floating-point loads/stores, atomic memory operations like lwarx and stwcx), Flow control (branching, condition register logical, trap), Processor control (synchronizing memory accesses, cache, TLB, segment register management), and Memory control (control of caches, TLBs, and SRs).

💡 Why this matters: The consistent instruction format is a hallmark of RISC design, directly enabling the parallel decode and pipelining that give the 750 its high performance.

PowerPC 750 – Instruction Flow

The instruction flow in PowerPC 750 includes three stages: Instruction fetch, Instruction decode, and Instruction dispatch. The architecture allows a maximum of four instructions to be fetched per clock cycle. The number of clock cycles necessary to request instructions from the memory system depends on where the target instruction is located: the branch target instruction cache (BTIC), the on-chip instruction L1 cache, or the L2 cache.

In the decode/dispatch stage, instructions can only be dispatched from the two lowest instruction queue entries, IQ0 and IQ1. A maximum of two instructions can be dispatched per clock cycle, although an additional branch instruction can be handled by the Branch Processing Unit (BPU). Only one instruction can be dispatched to each execution unit per clock cycle. For a dispatch to occur, there must be: a vacancy in the specified execution unit, a rename register available for each destination operand, and an open position in the completion queue. If no entry is available in the completion queue, the instruction remains in the instruction queue (IQ).

PowerPC 750 – Execution Units

The PowerPC 750 superscalar pipeline contains two integer units (IUs). IU1 can execute any integer instruction, while IU2 can execute all integer instructions except multiply and divide. These share thirty-two General Purpose Registers (GPRs) and a single-entry reservation station for each. It also features a three-stage floating-point unit (FPU) that supports both single- and double-precision operations with hardware support for denormalized numbers and a single-entry reservation station, using thirty-two 64-bit FPRs. The two-stage Load/Store Unit (LSU) contains a two-entry reservation station, provides single-cycle pipelined cache access, and has a three-entry store queue. It supports both big- and little-endian modes and has a dedicated adder for effective address (EA) calculations. It also performs alignment and precision conversion for floating-point data and sign extension for integer data.

PowerPC 750: Completion Unit

The Completion unit retires an instruction from the six-entry reorder buffer (completion queue) when three conditions are met: all instructions ahead of it have been completed, the instruction has finished execution, and no exceptions are pending. The completion unit guarantees the sequential programming model (precise exception model). It monitors all dispatched instructions, retires them in order, tracks unresolved branches, flushes instructions from mispredicted branches, and can retire as many as two instructions per clock.

PowerPC 750 Rename Buffers

The 750 provides rename registers to hold instruction results before the completion unit commits them to the architected register. There are six GPR rename registers, six FPR rename registers, and one each for the Condition Register (CR), Link Register (LR), and Count Register (CTR). When an instruction is dispatched, a rename register for its results is assigned, and the dispatcher provides a tag to the execution unit identifying the rename register that will forward required data. Results are transferred from the rename registers to the architected registers by the completion unit when an instruction is retired. Results of squashed instructions are flushed from the rename registers.

PowerPC 750 Branch Prediction Unit

The Branch Prediction Unit supports both static and dynamic branch predictions, only one of which is used at any given time. Static branch prediction is defined by the PowerPC architecture, using the BO field in branch instructions to allow software to hint whether a branch is likely to be taken. The 750 uses this encoding to predict the branch direction before the condition is known. Dynamic branch prediction uses a 512-entry Branch History Table (BHT) with two bits per entry, allowing predictions of: Not-taken, Strongly not-taken, Taken, Strongly taken.

PowerPC 750 Branch Target Cache - BTC

The 750 uses the Branch Target Instruction Cache (BTIC) to reduce the time required for fetching target instructions when a branch is predicted to be taken. The BTIC is a 64-entry (16-set, four-way set-associative) cache of branch instructions. When a BTIC hit occurs, instructions are fetched into the instruction queue a cycle sooner than they could be made available from the instruction cache.

PowerPC 750 Multiple Branch Prediction

The 750 executes through two levels of prediction. Instructions from the first unresolved branch can execute, but they cannot complete until the branch is resolved. If a second branch instruction is encountered in the predicted instruction stream, it can be predicted, and instructions can be fetched (but not executed) from the second branch. No action can be taken for a third branch instruction until at least one of the two previous branch instructions is resolved.

PowerPC 750 Cache

The 750 has separate on-chip instruction and data caches. The instruction cache is 32-Kbyte, eight-way set-associative using a Pseudo Least-Recently-Used (PLRU) replacement policy. Both caches have 32-byte (eight-word) cache blocks, are physically indexed with physical tags, and support per-block cache write-back or write-through operation. The caches can be disabled or locked in software. Data cache coherency (MEI) is maintained in hardware. The critical double word is made available to the requesting unit first, and the cache is non-blocking.

The Data Cache is organized with 32-word blocks (5 bits), 128 sets (7 bits), Tags (20 bits), and uses the MEI state (Modified, Exclusive, Invalid). The Instruction Cache has a similar structure (32-word blocks, 128 sets, 20-bit tags) but uses a Valid/Not valid state and is not snooped.

PowerPC 750: Multiprocessing

The 750's multiprocessing support features a hardware-enforced, three-state cache coherency protocol (MEI) for the data cache and a load/store with reservation instruction pair for atomic memory references and semaphores. The MEI protocol supports the Modified, Exclusive, and Invalid states. Notably, there is no shared state in this protocol.

💡 Why this matters: The lack of a 'Shared' state in the MEI protocol is a simpler, less expensive design choice compared to protocols like MESI, but it may lead to more cache-to-cache transfers in a multiprocessor system.

PowerPC 970 FX

The PowerPC 970 FX is a 64-bit implementation of the PowerPC® AS Architecture (version 2.01) that includes Vector/SIMD Multimedia eXtension. It is a deeply pipelined design with varying pipeline depths: 16 stages for most fixed-point register-register operations, 18 stages for most load/store operations (assuming an L1 D-cache hit), up to 25 stages for floating-point operations, and 19 stages for vector permute operations. A key feature is dynamic instruction cracking, where some complex instructions are broken into two simpler, more RISC-like instructions, allowing for a simpler inner core dataflow.

PowerPC 970 FX: General

This processor features aggressive branch prediction, capable of predicting up to two branches per cycle and supporting up to 16 predicted branches in flight, including both branch direction and branch addresses. It has in-order dispatch of up to five operations into a distributed issue queue structure and out-of-order issue of up to 10 operations into 10 execution pipelines: two load/store, two fixed-point, two floating-point, one branch, one condition register, one vector permute, and one vector ALU operation. It employs register renaming and uses the MERSI (Modified/Exclusive/Recent/Shared/Invalid) cache coherency protocol. It supports a theoretical maximum of 215 instructions in flight, distributed across various buffers and queues. It features fast, selective flush of incorrect speculative instructions and results, with a specific focus on storage latency management, including out-of-order and speculative issue of loads, support for up to eight outstanding L1 cache line misses, hardware-initiated instruction prefetching from L2 cache, and software-initiated data stream prefetching.

PowerPC 970 FX: Instruction Fetch

The instruction fetch unit uses a 64KB, direct-mapped instruction cache (I-cache) with 128-byte lines broken into four 32-byte sectors and a dedicated 32-byte read/write interface from the L2 cache using a critical sector first reload policy. It has a four-entry, 128-byte, instruction prefetch queue above the I-cache with hardware-initiated prefetches. It can fetch a 32-byte aligned block of eight instructions per cycle.

PowerPC 970 FX: Branch Prediction

The branch predictor can scan all eight fetched instructions for branches each cycle and predict up to two branches per cycle. It uses a three-table prediction structure: a local predictor (16K entries, 1-bit each, Taken/Not taken), a global predictor (16K entries, 1-bit each, with an 11-bit history XORed with the branch instruction address), and a selector (16K entries, 1-bit each, indexed similarly, choosing between the local and global predictor). This combination produces very accurate predictions. It also has a 16-entry link stack for address prediction of subroutine returns (with stack recovery) and a 32-entry count cache for predicting the target address of bcctr instructions.

PowerPC 970 FX: Instruction Decode and Preprocessing

This unit has a three-cycle pipeline to decode and preprocess instructions, including cracking one instruction into two internal operations. Cracked and micro-coded instructions have access to renamed emulation registers: eGPRs (4), eFPR (1), and eCR field (1), in addition to architected facilities. It includes an 8-entry (16 bytes per entry) instruction fetch buffer that can take up to eight instructions in and output five instructions out each cycle.

PowerPC 970 FX: Instruction Dispatch and Completion Control

The dispatch unit has four dispatch buffers that can hold up to four dispatch groups when the global completion table (GCT) is full. It uses a 20-entry global completion table for group-oriented tracking, associating a five-operation dispatch group with a single GCT entry. This tracks internal operations from dispatch to completion for up to 100 operations and supports precise exceptions. It is capable of very fast restoration for instructions on group boundaries (e.g., branches) and slower restoration for instructions contained within a group.

PowerPC 970 FX: Branch and Condition Register Execution Pipeline

There is one branch execution pipeline that computes the actual branch address and direction for comparison with the prediction. If prediction was incorrect, it redirects instruction fetching and assists in training the branch table predictors, link stack, and count cache. There is one condition register logical pipeline that executes CR logical instructions, CR movement operations, and some mtspr/mfspr instructions. It uses out-of-order issue with a bias towards the oldest operations first.

PowerPC 970 FX: Data Stream Prefetch

The 970 FX supports eight (modeable) data prefetch streams in hardware. All eight are available if vector prefetch instructions are disabled. If vector prefetch is enabled, four vector prefetch streams are supported using four of the eight hardware streams. The vector prefetch mapping algorithm supports the most commonly used forms of vector prefetch instructions.

Intel P-VI: General

The Intel P6 family of processors succeeds the Pentium® line and implements Intel's dynamic execution micro-architecture, which combines multiple branch prediction, data flow analysis, and speculative execution.

Intel P-VI: Major Units

The P6 architecture has three main engines and a bus interface unit. The FETCH/DECODE unit is an in-order unit that takes the user program instruction stream from the instruction cache, decodes them into a series of μ-operations (μops), representing the dataflow. The pre-fetch is speculative. The DISPATCH/EXECUTE unit is an out-of-order unit that accepts the dataflow stream, schedules execution of the μops subject to data dependencies and resource availability, and temporarily stores the speculative results. The RETIRE unit is an in-order unit that knows how and when to commit (or "retire") the temporary, speculative results to the permanent architectural state. The BUS INTERFACE unit communicates directly with the L2 cache, supporting up to four concurrent cache accesses and controlling a transaction bus with the MESI snooping protocol to system memory.

Intel P-VI: Inside Fetch

The L1 Instruction Cache fetches the cache line corresponding to the Next_IP and presents 16 aligned bytes to the decoder. The decoder converts Intel Architecture instructions into triadic μops (two logical sources, one logical destination). Most instructions are converted into single μops, some into one-to-four μops, and complex instructions require microcode. The μops are queued and sent to the Register Alias Table (RAT), where logical register references are converted into physical register references. The μops are then entered into the instruction pool, which is implemented as a Content Addressable Memory called the Re-Order Buffer (ROB).

Intel P-VI: Inside Dispatch/Execute

The Dispatch unit selects μops from the instruction pool based on their status. If a μop has all its operands and the required execution resource is available, the Reservation Station removes the μop and sends it for execution. The results are later returned to the pool. There are five ports on the Reservation Station, allowing a peak rate of 5 μops per clock, though a sustained rate of 3 is more typical. The Branch Target Buffer (BTB) correctly predicts most branches. If a branch is mispredicted, the Jump Execution Unit (JEU) changes the status of all μops behind the branch to remove them from the instruction pool, and the proper branch destination is provided to the BTB to restart the pipeline.

Intel P-VI: Inside Retire

The Retire Unit checks the status of μops in the instruction pool. To retire a μop, it must re-impose the original program order. It reads the instruction pool to find candidates for retirement and determines which are next in the original program order. It then writes the results to the Retirement Register File (RRF). The Retire Unit is capable of retiring 3 μops per clock.

Intel P-VI: Bus Interface Unit

Loads are encoded into a single μop, while stores require two μops: one to generate the address and one to generate the data. These μops must later re-combine for the store to complete. Stores are never performed speculatively because there is no transparent way to undo them. Stores are also never re-ordered among themselves. A store is dispatched only when both the address and data are available and there are no older stores awaiting dispatch. A study of memory access reordering concluded that: constraining stores from passing other stores has a small performance impact; constraining stores from passing loads has an inconsequential loss; and constraining loads from passing other loads or stores has a significant impact on performance. The Memory Order Buffer (MOB) allows loads to pass other loads and stores, acting like a reservation station and re-order buffer for suspended loads and stores.

⭐ Key Takeaways

The three case studies demonstrate different design philosophies for achieving high performance. The PowerPC 750 is a classic RISC superscalar design with in-order dispatch and out-of-order completion, relying on a straightforward 6-stage pipeline and simple branch prediction. In contrast, the PowerPC 970 FX is a deeply pipelined, heavily out-of-order design with sophisticated features like dynamic instruction cracking, a three-table branch predictor, and a large instruction window of up to 215 instructions. The Intel P6 introduces a radically different "dynamic execution" micro-architecture with a clear separation of concerns: an in-order fetch/decode unit that cracks CISC instructions into RISC-like μops, a central out-of-order execution engine, and an in-order retire unit to ensure precise exceptions. A critical design lesson from the P6 is the importance of load-load and load-store reordering for performance, while store-store and store-load ordering can be more constrained without significant loss.

🧠 Quick Revision Questions

1. What are the three conditions that must be met for an instruction to be dispatched in the PowerPC 750?
2. How does the PowerPC 970 FX's three-table branch prediction structure (local, global, selector) improve prediction accuracy over the simpler BHT used in the 750?
3. In the Intel P6 architecture, why can't stores be performed speculatively, and how does this constraint affect the Memory Order Buffer (MOB)?
4. What is "dynamic instruction cracking" in the PowerPC 970 FX, and what is its primary benefit?
5. What is the key difference in the cache coherency protocols between the PowerPC 750 (MEI) and the PowerPC 970 FX (MERSI)? What does the extra state ('Recent') imply?

📘 Lecture 45 — Putting It All Together (Review: Lecture 1 - 43)

📖 Overview: This lecture provides a comprehensive review of the entire Advanced Computer Architecture course, covering all nine modules from Introduction and Quantitative Principles through Networks and Clusters. It systematically revisits the key concepts, definitions, formulas, and techniques studied across all lectures, serving as a final consolidation for exam preparation.

🗂️ Topics Covered

The lecture reviews all nine course modules in sequence: Introduction and Quantitative Principles including price-performance design and Amdahl's Law; Instruction Set Architecture covering ISA taxonomy, operand types, and addressing modes; Computer Hardware Design including datapath implementations, single/multiple cycle approaches, and pipelining with hazards; Dynamic ILP techniques including scoreboarding, Tomasulo's algorithm, branch prediction, and speculation; Static ILP approaches including superscalar, VLIW, and vector processors along with compiler scheduling techniques; Memory Hierarchy System covering caching principles and locality; Multiprocessing including parallel architectures and cache coherence; I/O Systems covering interconnects, bus protocols, and arbitration schemes; and Networks and Clusters including interconnection topologies and internetworking.

📝 Lecture Summary

Module 1: Introduction and Quantitative Principles

The course began by distinguishing computer organization from computer architecture. Architecture refers to attributes visible to the programmer or compiler writer such as instruction set, memory addressing, and I/O mechanisms. Organization refers to how features are implemented, for example, control signals generated using FSM or microprogramming principles. The architecture of processor family members is identical, whereas organization may differ between family members.

Computer development began academically in 1944-49 when John von Neumann introduced the stored-program computer concept called EDVAC (Electronic Discrete Variable Automatic Computer). Commercially, the first machine was built by Eckert-Mauchly Computer Corporation in 1949. In 1971, Intel introduced the first cheap microprocessor, the 4004, followed by the 80x86 series. By 1998, over 350 million microprocessors were in use, rising to over a billion by 2006. Technological developments from vacuum tubes to VLSI circuits produced four computer generations. The course viewed Computer Architecture from four perspectives: Processor Design, Memory Hierarchy, Input/output and Storage, and Multiprocessor and Network Interconnection.

🔑 Definition — Price-performance design: The balancing act where high-performance designers may not prioritize cost, while low-cost designers may sacrifice performance, lying between these extremes to balance cost versus performance.

🔑 Definition — Benchmarks: Programs specifically chosen to measure performance; five levels include Real Applications (scientific programs), Modified Applications (real programs with modified blocks), Kernels (small key pieces from real programs), Toy Benchmarks (small codes for beginners), and Synthetic Benchmarks (artificially created programs).

📐 Amdahl's Law: Speedup (E) = Execution Time without Enhancement / Execution Time with Enhancement = Performance with Enhancement / Performance without Enhancement. This defines speedup due to enhancement E that accelerates a fraction F of the task. 💡 Why this matters: Amdahl's Law quantifies that system speedup is limited by the slowest part of the system, making it fundamental for performance analysis.

Module 2: Instruction Set Architecture

The three pillars of computer architecture are hardware, instruction set, and software. Hardware facilitates software execution, and the instruction set serves as the interface between hardware and software. Focus areas included ISA Taxonomy, operand types, operation types, and memory addressing modes.

🔑 Definition — ISA Taxonomy: Classification of instruction set architectures including Stack Architecture, Accumulator Architecture, and General Purpose Register Architecture (further divided into Register-Memory, Register-Register/Load-Store, and Memory-Memory, which is obsolete).

Operand Types: Integer, FP (Floating Point), and Character. Operand Sizes: Half word, word, double word. Classification of operations: Arithmetic, data transfer, control, and support operations.

Operand Addressing Modes: Immediate, register, direct (absolute), and Indirect. Classification of Indirect Addressing: Register, indexed, relative (with displacement), and memory. Special Addressing Modes: Auto-increment, auto-decrement, and scaled. Control Instruction Addressing Modes: Branch, jump, and procedure call/return.

Module 3: Computer Hardware Design

At a higher level, the CPU consists of two sub-systems: Datapath (the path facilitating information transfer between registers/memory/I/O) and Control (hardware generating signals to control step sequences and direct information flow through the datapath).

🔑 Definition — Datapath: The arithmetic organ of Von Neumann's stored-program organization, typically implemented as Unibus structure, 2-bus structure, or 3-bus structure, based on single cycle, multiple cycle, or pipelined architecture concepts. It consists of registers, internal buses, arithmetic units, and shifters.

Each register in the register file has: a load control line enabling data load, a set of tri-state buffers between output and bus, and a read control line enabling buffer and placing register on bus.

Single Cycle vs Multiple Cycle: In Single Cycle implementation, cycle time accommodates the longest instruction (Load instruction). In Multiple Cycles implementation, cycle time accommodates the longest step (memory read/write). Consequently, Single Cycle cycle time can be five times longer than Multiple Cycle implementation.

Pipelining is a fundamental concept where instructions complete in multiple steps using distinct resources, starting the next instruction while working on the current one. Pipeline Hazards include Structural hazards (same resource accessed by multiple instructions, removed by multiple resources or inserting stalls), Data hazards (attempt to read invalid data, removed by stalls and forwarding), and Control hazards (attempt to branch before condition evaluation).

Four ways to handle control hazards: 1) Stall until branch direction is clear, 2) Predict Branch Not Taken, 3) Execute successor instructions in sequence (Predict Branch Taken), 4) Delayed Branch (define branch to take place AFTER a following instruction).

Module 4: Instruction Level Parallelism – Dynamic

Simple pipelines facilitate in-order execution, but performance enhancement requires out-of-order execution when data operands are available. Out-of-order execution may introduce data hazards of type WAR (Write After Read) and WAW (Write After Write). Instruction Level Parallelism (ILP) can be achieved by Hardware or Software.

Dynamic Scheduling techniques exploit ILP when dependencies cannot be determined at run time. It divides the ID stage into two parts: Issue the instruction in-order, and Read operand out-of-order. The two major techniques studied were Scoreboarding and Tomasulo's Algorithm.

Tomasulo's Approach for IBM 360/91 achieves high performance without special compilers. Control and buffers are distributed with Function Units (FU). Registers in instructions are replaced by values or pointers to Reservation Stations (RS) — this is register renaming. Unlike Scoreboard, Tomasulo can have multiple loads outstanding.

Hardware-based Speculation allows speculation that a branch is correctly predicted, executing out-of-order but committing in-order after confirming correctness and no exceptions exist.

Module 5: Instruction Level Parallelism – Static

Multiple-instruction-issue per cycle processors are high-performance processors existing in three flavors: Superscalar Processors (exploit ILP using static and dynamic scheduling), VLIW processors (exploit ILP using static scheduling only), and Vector Processors.

Module 6: Memory Hierarchy System

The gap between processor speed and storage devices (DRAM, SRAM, Disk) increases with time. To obtain high-speed storage at cheapest cost per byte, different memory types are organized in a hierarchy based on Caching and the Principle of Locality.

🔑 Definition — Principle of Locality: The processor accesses a relatively small portion of address space of the fastest memory closest to the processor at any instant. Temporal locality is locality in time; Spatial locality is locality in space.

🔑 Definition — Caching: Using a small, fastest, and most expensive storage as a staging area to store frequently-used subsets of data/instructions from cheaper, larger, slower memory, avoiding main memory access every time information is needed.

Cache performance is improved using four options to reduce: miss penalty, miss penalty or miss rate via parallelism, miss rate, and time to hit in the cache.

Module 7: Multiprocessing

Parallel Architecture is a collection of processing elements that cooperate and communicate to solve larger problems faster. Four categories: SISD, SIMD, MISD, and MIMD architecture. Based on memory organization and interconnect strategy, MIMD machines are classified as Centralized Shared Memory Architecture and Distributed Memory Architecture.

Cache Coherence Problem: occurs in symmetric shared-memory multiprocessing. Two resolution methods are Write Invalidation and Write Broadcasting schemes. The Snooping Algorithm implements cache coherence using a finite state machine.

Module 8: I/O Systems

Overall computer performance is measured by throughput, heavily influenced by external systems. Neglecting I/Os is visualized by Amdahl's Law: system speedup limited by the slowest part.

I/O Interconnect Trends: Networks offer message-based narrow-pathway for distributed processors over long distance. Backplanes offer memory-mapped wide pathway for centralized processing over short distance. Channels use I/O buses; backplanes use CPU-Memory buses.

Bus Transition Protocols specify the sequence of events and timing requirements for information transfer as synchronous or asynchronous communication. Bus Arbitration Protocols reserve the bus, balancing Bus-priority (highest priority device serviced first) and Fairness (every device guaranteed eventual bus access).

Three bus arbitration schemes: Daisy Chain Arbitration, Centralized Parallel Arbitration, Distributed Arbitration.

Reliability improvement methods: Fault Avoidance (prevent fault by construction), Fault Tolerance (provide service complying with specification via redundancy), Error Removal (minimize errors by verification), Error Forecasting (estimate presence, creation, and consequence of errors by evaluation).

Module 9: Networks and Clusters

A generic interconnection network comprises computer nodes (host/end system), H/W and S/W interface, links to the interconnection network, and communication subnet. Interconnections are designated as Local Area Network (LAN), Wide Area Network (WAN), and System/Storage Area Network (SAN).

The interconnect communication model shows two machines connected via two unidirectional wires with a FIFO queue at the end. Communication software separates header and trailer, identifying request, reply, acknowledgments, and error checking codes. Communication protocols suggest the sequence of steps for reliable communication.

Distributed switch interconnects are classified as fully/partially connected and symmetric/asymmetric. Topologies include linear array, ring, 2D mesh/torus, and hypercube with their performance measures.

Internetworking connects two or more interconnection networks for reliable and efficient communication, relying on communication standards composed of hierarchy of layers. Internet communication protocol families facilitate applications to work with any interconnection.

⭐ Key Takeaways

The most critical concepts for examination include Amdahl's Law as the fundamental performance metric where speedup equals execution time without enhancement divided by execution time with enhancement. The three pillars of computer architecture—hardware, instruction set, and software—with ISA taxonomy distinguishing stack, accumulator, and general purpose register architectures. Pipeline hazards must be mastered: structural (same resource), data (invalid reads resolved by forwarding and stalling), and control (branches resolved by stalling, prediction, or delayed branching). Dynamic scheduling through Tomasulo's approach with register renaming and reservation stations enables out-of-order execution with in-order commitment through speculation. Memory hierarchy relies on the principle of locality (temporal and spatial) and caching, with four optimization options targeting miss penalty, miss rate, and hit time. For multiprocessing, the cache coherence problem requires write invalidation or broadcasting protocols implemented via snooping algorithms.

🧠 Quick Revision Questions

1. What is Amdahl's Law and how does it relate to the concept that system speedup is limited by the slowest part?

2. What are the three types of pipeline hazards and what techniques are used to resolve each type?

3. How does Tomasulo's algorithm achieve out-of-order execution through register renaming and reservation stations, and what advantage does it have over Scoreboarding?

4. What is the Principle of Locality, what are its two types, and how does caching exploit this principle in memory hierarchy design?

5. What are the three bus arbitration schemes, and how do they balance bus-priority with fairness in I/O systems?