MIT 6.004 - Computation Structures Flashcards

Question 1

Static Discipline

Accepted Answer

A contract between digital circuit components requiring that if inputs meet valid logic thresholds, the circuit guarantees outputs that meet valid logic thresholds. Valid levels satisfy $V_{OUT,LOW} \le V_{IN,LOW} < V_{IN,HIGH} \le V_{OUT,HIGH}$ to ensure noise margins.

Question 2

Noise Margin

Accepted Answer

The maximum amount of spurious voltage noise that can be added to a signal without altering its logical interpretation. 
- High Noise Margin: $NM_H = V_{OH} - V_{IH}$
- Low Noise Margin: $NM_L = V_{IL} - V_{OL}$

Question 3

CMOS Logic Gate Structure

Accepted Answer

A Complementary Metal-Oxide-Semiconductor gate consists of two complementary networks:
1. **Pull-Up Network (PUN):** Made of pFETs connected to $V_{DD}$, active when inputs are `0`.
2. **Pull-Down Network (PDN):** Made of nFETs connected to $GND$, active when inputs are `1`.

Question 4

De Morgan's Laws

Accepted Answer

Fundamental rules in Boolean algebra used to simplify logical expressions:
1. $\overline{A \cdot B} = \overline{A} + \overline{B}$
2. $\overline{A + B} = \overline{A} \cdot \overline{B}$

Question 5

Sum-of-Products (SOP) Form

Accepted Answer

A canonical Boolean expression formed by OR-ing multiple AND terms (minterms), where each minterm evaluates to `1` for a specific combination of inputs. For example: $F = (\overline{A} \cdot B) + (A \cdot \overline{B})$.

Question 6

Propagation Delay ($t_{PD}$) vs. Contamination Delay ($t_{CD}$)

Accepted Answer

- **Propagation Delay ($t_{PD}$):** The maximum time from an input transition until the output reaches a stable, valid value.
- **Contamination Delay ($t_{CD}$):** The minimum time from an input transition until the output starts to change.

Question 7

D Flip-Flop Setup and Hold Times

Accepted Answer

- **Setup Time ($t_S$):** The minimum time the input data `D` must remain stable *before* the active clock edge.
- **Hold Time ($t_H$):** The minimum time the input data `D` must remain stable *after* the active clock edge.

Question 8

Dynamic Discipline

Accepted Answer

The requirement that inputs to sequential logic devices must be stable during a window around the clock edge: $[t_{clk} - t_S, t_{clk} + t_H]$. Violating this can cause **metastability**.

Question 9

D Latch vs. D Flip-Flop

Accepted Answer

- **D Latch:** Level-sensitive device; output `Q` transparently follows input `D` while clock is HIGH.
- **D Flip-Flop:** Edge-triggered device; captures input `D` only at a specific transition (e.g., rising edge) of the clock.

Question 10

Moore vs. Mealy Finite State Machines (FSMs)

Accepted Answer

- **Moore Machine:** Outputs depend *only* on the current state. $Outputs = g(State)$
- **Mealy Machine:** Outputs depend on both the current state and current inputs. $Outputs = g(State, Inputs)$

Question 11

Karnaugh Map (K-Map)

Accepted Answer

A visual tool for simplifying Boolean expressions by arranging truth table values in a grid ordered by Gray code, allowing adjacencies to reveal minimized logic terms via grouping powers of 2 ($2^n$ cells).

Question 12

Ripple-Carry Adder vs. Carry-Lookahead Adder (CLA)

Accepted Answer

- **Ripple-Carry:** Simple $N$-bit adder cascading $N$ full adders; delay scales linearly as $\mathcal{O}(N)$.
- **Carry-Lookahead:** Computes carry bits in parallel using Generate ($G_i = A_i B_i$) and Propagate ($P_i = A_i \oplus B_i$) signals; delay scales logarithmically as $\mathcal{O}(\log N)$.

Question 13

Pipelining Performance Metrics

Accepted Answer

- **Latency:** The total time required to process a single instruction from start to finish.
- **Throughput:** The number of instructions completed per unit of time.
*Note:* Pipelining increases throughput but may slightly increase latency per instruction due to register overhead.

Question 14

Data Hazards in Pipelining

Accepted Answer

Occurs when an instruction depends on the result of a previous instruction that has not yet completed execution. Solved via:
1. **Stalling (Bubbles)**
2. **Bypassing/Forwarding** (routing data directly from ALU/MEM stage back to EX stage)

Question 15

Control Hazards in Pipelining

Accepted Answer

Occurs when the pipeline cannot determine the next instruction to fetch due to a conditional branch. Solved via branch prediction, branch target buffers (BTB), or flushing instructions.

Question 16

Principle of Locality

Accepted Answer

- **Temporal Locality:** If a memory location is referenced, it is likely to be referenced again in the near future (e.g., loop variables).
- **Spatial Locality:** If a memory location is referenced, nearby memory locations are likely to be referenced soon (e.g., sequential array traversal).

Question 17

Direct-Mapped Cache

Accepted Answer

A cache organization where each main memory block maps to exactly one cache line, calculated via:
$$	ext{Cache Index} = (	ext{Block Address}) \bmod (	ext{Number of Cache Lines})$$

Question 18

N-Way Set-Associative Cache

Accepted Answer

A cache structure where memory addresses map to a specific set containing $N$ cache lines. A block can be placed in *any* of the $N$ locations within that set, reducing conflict misses compared to direct-mapped caches.

Question 19

Average Memory Access Time (AMAT)

Accepted Answer

The expected time to access memory considering cache hits and misses:
$$	ext{AMAT} = 	ext{Hit Time} + (	ext{Miss Rate} 	imes 	ext{Miss Penalty})$$

Question 20

Virtual Memory & Page Tables

Accepted Answer

An abstraction that provides each process with a contiguous virtual address space. The CPU translates a **Virtual Page Number (VPN)** to a **Physical Page Number (PPN)** using a data structure called a **Page Table** managed by the OS.

Question 21

Translation Lookaside Buffer (TLB)

Accepted Answer

A small, fast, hardware lookup cache within the Memory Management Unit (MMU) that stores recent Virtual-to-Physical page address translations to accelerate memory access.

MIT 6.004 - Computation Structures

Cards in this deck

Related Flashcard Sets

Korean TOPIK I - Essential Grammar & Vocab

French A1 - Essential Vocabulary & Grammar

Machine Learning - Supervised Learning Algorithms

Immunology - Adaptive & Innate Immunity