What is the primary benefit of pipelining?

Increased instruction throughput

In a direct-mapped cache, if two memory blocks map to the same cache line, what happens?

One block replaces the other (conflict).

What is the role of the TLB?

To cache virtual-to-physical address translations

Digital Logic, MIPS, and Cache Memory Essentials

This cheat sheet covers fundamental concepts in digital logic, MIPS assembly programming, pipeline performance, and cache memory organization, providing a concise reference for key principles and calculations.

Core Principles

Sequential circuits involve D flip-flops triggered by clock edges.
2's complement addition requires checking for overflow.
MIPS assembly uses registers for variables and memory addresses.
Pipeline stages (IF, ID, EX, MEM, WB) determine clock cycle time and instruction latency.
Data hazards in pipelines can be resolved with NOPs or forwarding.
Cache memory uses tags, indices, and offsets to map memory addresses.
Direct-mapped and set-associative caches have different structures and hit/miss behaviors.
Virtual memory uses page tables for address translation.
TLB (Translation Look-aside Buffer) caches page table entries for faster access.

Action Steps

For sequential circuits, trace Y and Z values cycle by cycle.
For 2's complement addition, perform binary addition and check sign bits for overflow.
Translate C/Java statements to MIPS assembly using appropriate registers and instructions.
Calculate pipeline performance metrics (clock cycle time, latency, computation time).
Determine NOP insertion or forwarding needs based on data dependencies.
Analyze cache references by calculating binary address, tag, and index.
Track cache state (valid bits, tags) through a series of memory accesses.
Convert virtual addresses to physical addresses using page tables and TLB.
Calculate total page table size based on virtual address size, page size, and table structure.

Formulas

Non-pipelined clock cycle time = Sum of all stage latencies
Pipelined clock cycle time = Maximum stage latency
Pipelined instruction latency = Number of stages * Clock cycle time
Total computation time (pipelined) = (Number of instructions + Number of stages - 1) * Clock cycle time

Key Terms

D Flip-flop: A sequential logic circuit that stores a single bit of data, changing its output only on the rising edge of a clock signal.
2's Complement: A method for representing signed integers in binary, where the most significant bit indicates the sign.
Overflow: In arithmetic operations, occurs when the result is too large to be represented by the given number of bits.
MIPS Assembly: A low-level programming language for the MIPS Reduced Instruction Set Computer (RISC) architecture.
Pipeline: A technique used in processor design to execute multiple instructions concurrently by breaking instruction execution into stages.
Data Hazard: A situation in a pipelined processor where an instruction depends on the result of a previous instruction that has not yet completed.
Forwarding: A technique to resolve data hazards by sending the result of an instruction directly from the execution stage to subsequent dependent instructions.
Cache Memory: A small, fast memory used to store frequently accessed data from main memory, reducing access time.
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 line within a specific set of cache lines.
Virtual Address: An address generated by the CPU that is mapped to a physical address by the memory management unit.
Page Table: A data structure used by the virtual memory system to store the mapping between virtual pages and physical frames.
TLB (Translation Look-aside Buffer): A cache for page table entries, used to speed up virtual-to-physical address translation.
Page Fault: An event that occurs when a program tries to access a page that is not currently in main memory.

Pro Tips

When calculating 2's complement overflow, check if the signs of the operands are the same and the sign of the result is different.
In MIPS, use $t registers for temporary values and $s registers for saved values.
Always account for the overhead of NOP instructions when calculating total execution time.
Forwarding can significantly reduce pipeline stalls but adds complexity to the datapath.
Cache block size, associativity, and cache size all impact performance.
TLB misses require a page table lookup, which is slower.
The 'Valid' bit in cache and page table entries is crucial for correctness.

Pitfalls to Avoid

Incorrectly calculating 2's complement addition or misidentifying overflow.
Using the wrong registers or instructions in MIPS assembly.
Forgetting to insert NOPs or incorrectly applying forwarding rules.
Miscalculating tag, index, or offset bits for cache addressing.
Confusing word addresses with byte addresses.
Assuming TLB hits when page faults occur.
Incorrectly calculating page table sizes, especially with multi-level structures.

Real World Examples

A CPU executing a program with multiple instructions.: Pipelining speeds up execution by overlapping instruction stages, similar to an assembly line.
Accessing frequently used data in a web browser.: Cache memory stores recently viewed web page elements, allowing faster loading on subsequent visits.
Running multiple applications simultaneously on an operating system.: Virtual memory allows programs to use more memory than physically available by swapping pages between RAM and disk.

Timeline

1950s-1960s: Early concepts of memory hierarchy and caching emerge.
1970s: Development of virtual memory systems and demand paging.
1980s: Introduction of RISC architectures (like MIPS) and pipelining techniques.
1990s: Widespread adoption of pipelined processors and multi-level caches.
2000s-Present: Advanced pipelining, out-of-order execution, and complex cache hierarchies become standard.

People

John L. Hennessy: Pioneer in RISC architecture and co-founder of MIPS Computer Systems.
David A. Patterson: Co-pioneer of RISC architecture and author of influential computer architecture textbooks.

Quiz

What is the primary benefit of pipelining?: Increased instruction throughput
In a direct-mapped cache, if two memory blocks map to the same cache line, what happens?: One block replaces the other (conflict).
What is the role of the TLB?: To cache virtual-to-physical address translations