CS 3339 Computer Architecture Exam Cards Lee Hinkle

Moore's Law

Integrated circuit resources double every 18-24 months.

Power Wall

Period where lowering voltage was impossible because it made transistors too "leaky". This was circumvented by multiprocessors.

Deeper, higher-complexity pipelines led to...

Multicore

Formula(s) for CPU Time

(instructions/program)*(cycles/instruction)*(time/clock cycle)
OR
(instructions/program)*(cycles/CPI)

Amdahl's Law

T improved = (T affected/improvement factor) + T unaffected

There are __ x 32-bit registers.

31

The $____ register is constantly zero, and can't be overwritten. It is useful for common operations.

zero

R-type instruction format

[opcode (6)] [rs (5)] [rt (5)] [rd (5)] [shamt (5)] [funct (6)]

I-type instruction format

[opcode (6)] [rs (5)] [rt (5)] [immediate [16]

Software generally lives ______ than hardware.

longer

There's ____ money invested in software than hardware.

more

Companies tend to focus efforts on new _____________ rather than changing software to run on different platforms.

functionality

______ _______ provide a new platform with no old software binaries needing support.

mobile devices

RISC

== MIPS. Simplifies hardware, designed for pipelining. Features a larger register set, fixed instruction word length, and register-register operations.

CISC

== x86. Provides higher code density. Features few general purpose registers, one source overlaps destination, variable-length instruction words, memory operands, and micro-coded in hardware.

In Project 1, you extracted _________ from instruction word in C/C++.

bitfields

MIPS integer ALU operation 00 == ___.

ADD

MIPS integer ALU operation 01 == ___.

SUB

MIPS integer ALU operation 10 == ___.

AND

MIPS integer ALU operation 11 == ___.

OR

What is Fast Multiply?

Use multiple adders (Cost/performance tradeoff), can be pipelined (several multiplications performed in parallel)

What is Fast Divide

Can't use parallel hardware (subtraction is conditional on sign of reminder), faster methods like SRT division generate multiple quotient bits per step (still requires multiple steps).

In floating point addition, there is a loss of _____________ when adding one big number to a bunch of smaller numbers.

associativity

Floating point addition takes longer than integer addition because it ___ ____ _____.

has more steps

4 steps of floating point addition

(1) Align binary points
(2) Add significands
(3) Normalize result & check for over/underflow
(4) Round and renormalize if necessary

5 steps of floating point multiplication

(1) Add exponents
(2) Multiply significands
(3) Normalize result and check for over/underflow
(4) Round and renormalize if necessary
(5) Determine sign of result from signs of operands

Round to nearest

The default mode. Round to nearest representable value. If midway between two representable values, use the even (lowest-order bit) representable.

Round toward plus infinity, Round toward + infinity

All results rounded to smallest representable value greater than result.

Round toward minus infinity, Round toward - infinity

All results rounded to largest representable value less than result.

Round toward zero, Round toward 0

All results rounded to largest representable value whose magnitude is less than result (if negative, round up. If positive, round down).

________ _____ _____ matters. Associativity does not always hold.

Floating point order (or FP order)

SIMD instructions, vector instructions

Adds 4 x 128-bit registers, extended to 8 registers in AMD64/EM64T.
Can be used for multiple FP operads: 2 x 64-bit double precision and 4 x 32-bit double precision. Instructions operate on them simultaneously; Single Instruction Multiple Data.

4 types of datapath elements

Instruction Memory, Register File, Arithmetic Logic Unit (ALU), Data Memory

R-type arithmetic

Read two register operands, perform arithmetic/logical operation, write register result.

Load-store operation

Read register operands, calculate address using 16-bit offset (use ALU, but sign-extend offset), Load: read memory and update register, Store: Write register value to memory

Branch instruction

Read register operands, compare operands (use ALU, subtract and check zero output), calculate target address (sign-extend displacement, shift left 2 places (word displacement), add to PC + 4 (already calculated by instruction fetch))

In Project 2, you were given an instruction, had to identify its datapath, and generate _______ _______ to execute instruction.

control signals

We don't use single-cycle implementation because it is ___ _________.

not efficient

MIPS Pipeline Datapath - Stage IF:

instruction fetch from memory

MIPS Pipeline Datapath - Stage ID

instruction decode, and register read

MIPS Pipeline Datapath - Stage EX, EXE

execute operation or calculate address

MIPS Pipeline Datapath - Stage MEM

access memory operand

MIPS Pipeline Datapath - Stage WB

write result back to register

Theoretical peak speedup formula

Time pipelined = Time nonpipelined/stages

Two reasons we don't achieve peak speedup are __________ ______ and _______.

unbalanced stages, hazards

What is a structural hazard?

Hardware can't support the combination of instructions we want on the same clock cycle

True or False: MIPS 5-stage pipeline has no structural hazard.

True

You can impose a structural hazard by using a single ______ instead of multiple.

memory

What is a data hazard?

When a pipeline stalls waiting for a step to complete to start the next.

To detect a data hazard, check for ____________ when going through instructions.

dependencies

You can fix a data hazard with ______.

bubble(s)

forwarding

resolving data hazards by retrieving the missing data element from internal buffers. AKA bypassing.

What is a control hazard?

Arises from need to decide based on the result of one instruction while others are executing.

Branches are resolved at the __ stage because branches received in IF just arrived in the same clock cycle.

ID

You can fix control hazards with _______.

flush(es)

branch prediction

Resolves control hazards by assuming the result of the branch.

In a branch prediction, it is assumed that branches ____ be taken.
When does this make the program faster?
When does this make it slower?

won't
Faster if prediction is correct.
Slow if prediction is wrong.

How can we always fix a hazard?

Stalling.

Load use hazards happen because...

it occurs later in the pipeline. Can't always avoid stalls by forwarding (value not computed when needed, can't forward back in time!)

What is a branch source hazard?

When you can't tell where the branch will go

In Project 3, you were given an instruction sequence and pipeline design, and counted the number of _______ required to correctly execute the sequence.

bubbles

Why do we use a 2-bit saturating counter operation over a 1-bit counter?

It is possible to wrongly predict a branch prediction, change, and then wrongly predict again. Instead, wait until the prediction is wrong twice before changing the prediction.

In Project 4, you modified the simulator to model a pipeline with full __________ _____.

forwarding paths

In Instruction-Level Parallelism, why do we use IPC instead of CPI?

CPI < 1, so use IPC instead.

What is in-order static multiple issue?

- Compiler groups instructions to be issued together
- Packages them into "issue slots"
- Compiler detects and avoid hazards

What are some disadvantages to compiler management?

- Not all stalls are predictable
- Can't always schedule around branches b/c they are dynamically determined
- Different ISAs mean different latencies and hazards

What is Dynamically-Scheduled In-Order Superscaling?

CPU executes instructions out of order avoiding stalls

What is the difference between Instruction-Level Parallelism and Thread-Level Parallelism?

ILP: execute multiple instructions in parallel
TLP: execute multiple threads in parallel

Most instructions need inputs in the ____ stage. jr, beq, and bne need inputs in the __ stage. sw instruction's store data is needed in the ____ stage.

EXE1, ID, MEM1

ALU produces data at the end of ____ but it can't be forwarded until ____.
Most instruction results are produced at the ____ stage. lw, mult, and div produce results at the ____ stage. jal's result becomes available at the __ stage.

EXE2, MEM1.
EXE2, MEM2, ID.

In a memory hierarchy:
higher levels have ______ speeds, _______ sizes, and ____ distance from the CPU.
lower levels have ______ speeds, ______ sizes, and ____ distance from the CPU.

faster, smaller, less.
slower, bigger, more.

What is latency?

Time to get data from first access

What is bandwidth?

Amount of data that can be transferred in a "stream".

What is DRAM? (4 items)

- Main memory
- cells are small capacitors
- must be refreshed to hold data
- slow but less $

What is SRAM? (4 items)

- caches
- cells composed of ~6 logic gates
- multiple transistors
- fast but more $

DRAM and SRAM are both ________ and ___-________ options, using _____ and ________ media.

volatile, non-volatile, flash, magnetic

Temporal Locality and 2 examples

Items accessed recently are likely to be accessed again soon
Examples: loop instructions, induction variables

Spatial Locality and 2 examples

Items near those accessed recently are likely to be accessed soon
Examples: sequential instructions, array data

Valid bit

Indicates if data is in a location. 1 if there is, 0 if not.

When is a valid bit dirty?

When the location was recently written to and not written out.

Tags

high-order address bits that tell what block is stored in a cache location

Direct Mapped Cache (3 items)

- Location determined by address
- Direct mapped: only one choice (1 way)
- (Block address) modulo (#Blocks in cache)

Fully Associative Cache (2 items)

- No index bits, a block can go in any entry
- Usually increases hit rate

What is the shortcoming of a fully associative cache?

All entries must be searched instead of the one with the correct index, and comparator per entry is expensive.

n-way Set Associative Cache (4 items)

- Sets contain n entries
- Block # determines set [(Block #) modulo (#Sets)]
- Search all entries (ways) in a given set at once
- n comparators (less expensive)

What happens on a store hit?

the CPU proceeds normally

What happens on a cache miss?

CPU pipeline stalls, block from next hierarchical level fetched.
If instruction cache miss, restart instruction fetch. If data cache miss, complete data access.

Unlike a Write-Back cache, Write-Through updates the block in the cache AND the ______.

memory

Write-Back takes a _______ amount of time compared to Write-Through

shorter

Write-Through caches have access to a _____ ______, but it still slows down if it is full.

write buffer

What happens when a dirty block is replaced in a Write-Back cache?

It writes it back to memory, but it can use a write buffer to allow replaced block to be read first.

On a write-allocate store miss:
What happens when write-allocate (allocate on miss) is used?
What happens when write around (no write-allocate) is used?

It fetches the block.
It doesn't fetch the block.

Least Recently Used (LRU) Replacement

Replace when hasn't been used the longest.

What do LRU and Random Replacement policies have in common.

Approx. the same performance

The L2 cache (4 items)

- larger
- slower
- services misses from primary cache
- access when L1 is missed

The L1 cache (2 items)

- minimize hit time
- split into I and D caches

Cache Design Trad-Offs:
Increasing cache size __________ capacity misses and may ________ access time.

decreases, increase

Cache Design Trad-Offs:
Increasing associativity __________ conflict misses and may ________ access time.

decreases, increase

Cache Design Trad-Offs:
Increasing block size decreases __________ misses, __________ miss penalty, and for very large block sizes, increases ____ ____ due to pollution.

compulsory, increases, miss rate

What is a Cold (Compulsory) miss?

first time data accessed