Formula Vault · CO
Computer Organization
Sheet 1
Memory Hierarchy & Cache
4 formulasCore concepts
- Address split: [ Tag | Set index | Block offset ]
Key formulas
Average Memory Access Time
☆
\[ AMAT = \text{Hit time} + \text{Miss rate}\times\text{Miss penalty} \]
Miss rate = 1 − Hit ratio
2-Level Cache AMAT
☆
\[ AMAT_{2\text{-level}} = t_{L1} + m_{L1}\big(t_{L2} + m_{L2}\, p_{L2}\big) \]
Cache Size
☆
\[ \text{Lines} \times \text{Block size} \]
Number of Sets
☆
\[ \frac{\text{Cache size}}{\text{Block size}\times\text{Associativity}} \]
Test your recall
Can you recall the average memory access time formula?
Reveal formula
\[ AMAT = \text{Hit time} + \text{Miss rate}\times\text{Miss penalty} \]
GATE traps 4 traps
Fully associative has no index bits
Fully associative cache has NO set-index bits at all (a block can go anywhere) -- forgetting to drop the index field when computing tag size for a fully associative cache is a common error.
Write-back needs a dirty bit
Write-back needs a dirty bit (memory updated only on eviction); write-through updates memory on every write and needs no dirty bit -- GATE often asks which policy requires the extra bit.
Check what 'miss penalty' already includes
In AMAT problems, check carefully whether 'miss penalty' already includes hit time or is purely the EXTRA cost on a miss -- misreading this is the #1 source of wrong answers here.
Direct-mapped and fully associative are endpoints
Direct-mapped = 1-way set-associative; fully associative = N-way with a single set -- recognizing these as endpoints of the same general formula saves memorizing three separate ones.
Sheet 2
Pipelining
3 formulasCore concepts
- Ideal throughput = 1 instruction/cycle
Key formulas
Test your recall
Can you recall the pipeline speedup formula?
Reveal formula
\[ \text{Speedup}(k,n) = \frac{kn}{k+n-1} \]
GATE traps 4 traps
Three different hazard types
Structural, data, and control hazards are three DIFFERENT causes of stalls -- identify which type applies before computing stall cycles, don't jump straight to arithmetic.
Forwarding doesn't erase load-use stalls
Forwarding reduces but doesn't always eliminate stalls -- a load-use hazard typically still needs at least 1 stall cycle even with forwarding, since the loaded value isn't ready until after the MEM stage.
Branch penalty depends on resolution stage
Branch penalty depends on which pipeline stage actually resolves the branch, NOT automatically the full pipeline depth -- read the problem's branch-resolution stage carefully.
Ideal speedup ignores hazards
The ideal speedup formula assumes uniform stage delay and zero stalls -- real numericals usually add hazards on top, so treat this as step one, not the final answer.
Sheet 3
Instruction Formats & Addressing Modes
3 formulasKey formulas
Test your recall
Can you recall the instruction length formula?
Reveal formula
\[ \text{Opcode bits} + (\text{Operand bits}\times\text{operands}) \]
GATE traps 4 traps
Indirect addressing costs an extra access
Indirect addressing needs an EXTRA memory access to fetch the actual address before fetching the operand -- this extra access is exactly what memory-access-count questions are testing.
Immediate mode needs zero memory accesses
Immediate addressing needs NO memory access for the operand (it's embedded in the instruction) -- often the 'trick' fastest-mode answer in an access-count comparison.
Expanding opcodes save average bits
Expanding-opcode schemes pack more instructions into fewer average bits by giving common opcodes shorter codes -- a classic 'how many k-address instructions fit' numerical.
Addressing mode ≠ instruction format
Addressing mode (how the operand is located) and instruction format (how many operands/addresses) are different concepts -- GATE sometimes tests both within one question.
Sheet 4
Computer Arithmetic
1 formulaCore concepts
- Booth's algorithm handles both positive and negative multipliers directly in 2's complement, without special-casing the sign
- Restoring division subtracts and undoes (restores) on a negative remainder; non-restoring division skips the restore and adjusts the next step's sign instead, saving a step per iteration
Key formulas
Signed Overflow Detection
☆
\[ \text{Overflow} = C_{in} \oplus C_{out} \]
carry into vs. out of the sign bit
Test your recall
Can you recall the signed overflow detection formula?
Reveal formula
\[ \text{Overflow} = C_{in} \oplus C_{out} \]
Reference table
| Qn | Qn+1 | Operation |
|---|---|---|
| 0 | 0 | No operation (arithmetic shift right only) |
| 0 | 1 | A = A + M, then shift right |
| 1 | 0 | A = A - M, then shift right |
| 1 | 1 | No operation (arithmetic shift right only) |
GATE traps 4 traps
Overflow is Cin XOR Cout of the sign bit
Overflow in signed addition happens exactly when the carry INTO the sign bit differs from the carry OUT of the sign bit -- checking the operand signs alone (same-sign operands producing an opposite-sign result) is an equivalent but easy-to-misapply shortcut.
Booth's isn't always faster
Booth's algorithm can take MORE cycles than plain shift-add for an isolated run of alternating 1s and 0s in the multiplier -- it's not universally faster, just handles signed numbers uniformly.
A run of 1s: subtract low, add high
In Booth's recoding, a run of 1s becomes subtract at the LOW end (10) and add at the HIGH end (01), with no-ops in between -- swapping which end gets subtract vs. add is the most common Booth's-trace mistake.
Non-restoring division skips the restore step
Restoring division must complete a subtract-and-check-sign step every single iteration (even when it 'fails' and restores) -- this is exactly why non-restoring division, which never explicitly restores, is preferred for hardware efficiency.