What is the primary benefit of pipelining in a processor?

Increased instruction throughput

In 2's complement addition, when does an overflow occur?

When adding two positive numbers results in a negative number, or vice versa

What is the purpose of a TLB?

To speed up virtual-to-physical address translation

Computer Architecture & Memory Systems

This cheat sheet covers fundamental concepts in computer architecture, including sequential circuits, 2's complement arithmetic, MIPS assembly, pipelining, cache memory, and virtual memory management.

Core Principles

Sequential circuits use flip-flops to store state, changing output based on clock edges.
2's complement is the standard for signed integer representation and arithmetic.
MIPS assembly provides a low-level instruction set for processor operations.
Pipelining improves processor throughput by overlapping instruction execution stages.
Cache memory speeds up access by storing frequently used data closer to the CPU.
Virtual memory allows programs to use more memory than physically available, managed by the OS and hardware.

Action Steps

For sequential circuits, trace Y and Z values through each clock cycle, noting next-state logic.
Perform 2's complement addition, checking the sign bit of operands and result for overflow.
Translate C/Java statements to MIPS assembly, mapping variables to registers and using appropriate instructions.
Insert NOPs or use forwarding to resolve data hazards in pipelined execution.
Calculate tag, index, and offset for cache accesses based on block size and cache configuration.
Determine hit/miss status for cache references based on tag and index matching.
Calculate total bits for cache implementation, including data and metadata.
Convert virtual addresses to physical addresses using page tables and frame numbers.
Analyze TLB, cache, and page table interactions to understand memory access performance.

Formulas

Clock Cycle Time (Non-pipelined) = Sum of latencies of all stages
Clock Cycle Time (Pipelined) = Maximum latency of any single stage
Total Latency (Pipelined) = (Number of instructions + Number of stages - 1) * Clock Cycle Time
Cache Block Size (bytes) = 2 ^ Offset bits
Number of Blocks = Cache Size (bytes) / Block Size (bytes)
Number of Sets = Number of Blocks / Associativity
Tag Bits = Address Bits - Index Bits - Offset Bits
Total VM Size / Page Size = Number of Pages
Page Table Size = Number of Pages * Page Table Entry Size

Key Terms

D Flip-Flop: A sequential logic circuit that stores one bit of information, changing state on a clock edge.
2's Complement: A binary representation for signed integers, where negation is achieved by inverting bits and adding 1.
Overflow: Occurs in arithmetic when the result exceeds the representable range for the given number of bits.
MIPS Assembly: A reduced instruction set computer (RISC) architecture instruction set, commonly used in educational contexts.
Pipelining: A technique to improve instruction-level parallelism by executing multiple instructions in different stages concurrently.
Data Hazard: A situation in pipelined execution where an instruction depends on the result of a previous instruction not yet completed.
Forwarding: A hardware technique to resolve data hazards by sending results from later pipeline stages back to earlier ones.
NOP Instruction: No Operation; an instruction that does nothing, used to stall the pipeline.
Cache Memory: A small, fast memory that stores copies of frequently used data from main memory.
Direct-Mapped Cache: A cache organization where each memory block can map to only one specific cache line.
Set-Associative Cache: A cache organization where a memory block can map to any one of a small set of cache lines.
Virtual Address: An address generated by the CPU, which is then translated to a physical address.
Physical Address: The actual address in the main memory hardware.
Page Table: A data structure used by the virtual memory system to store mappings from virtual pages to physical frames.
Page Fault: An exception raised by hardware when a program accesses a memory page that is not currently mapped by the OS.
TLB (Translation Look-aside Buffer): A cache for page table entries, speeding up virtual-to-physical address translation.

Real World Examples

Executing a C program like `B[5] = B[3];`: Translates to MIPS assembly using `lw` and `sw` instructions with register offsets to access memory.
Adding two 8-bit 2's complement numbers: Requires checking for overflow by examining the sign bits of the operands and the result.
A pipelined processor executing 100 instructions: Achieves faster computation time compared to a non-pipelined processor due to overlapping stages, assuming no hazards.
Accessing data in a direct-mapped cache: The memory address is split into tag, index, and offset to locate data; hits occur when the tag matches the stored tag for the index.
A program accessing memory pages not currently in RAM: Triggers a page fault, requiring the OS to load the required page from disk into a physical frame.

Timeline

Cycle 0: Initial state: Y=0, Z=0
Cycle 1: Flip-flops update based on clock edge and current inputs.
Cycle 2: State transitions continue based on the circuit's logic.
Cycle 3: Observe the pattern of Y and Z values.
Cycle 4: Final state for the first 4 cycles.

People

Various Computer Architects: Designed and analyzed sequential circuits, arithmetic units, and processor architectures.
MIPS Architecture Designers: Developed the MIPS instruction set architecture and its associated assembly language.
Operating System Developers: Implement virtual memory management, including page tables and TLBs.
Cache Designers: Optimize cache structures (direct-mapped, set-associative) for performance.

Quiz

What is the primary benefit of pipelining in a processor?: Increased instruction throughput
In 2's complement addition, when does an overflow occur?: When adding two positive numbers results in a negative number, or vice versa
What is the purpose of a TLB?: To speed up virtual-to-physical address translation