TDT4255: Computer Design
Things I should read about:
- Out of order execution, re-order buffers
- (Carry look-ahead adders)
- register renaming
Useful basic components
Flip-flops, latches
Memory. Holds a single bit of memory. The difference between flip-flops and latches is that flip-flops are edge-triggered (by the clock), and latches are asynchronous.
Performance
Performance depends on
- Algorithm: affects IC, possibly CPI
- Programming language: affects IC, CPI
- Compiler: affects IC, CPI
- Instruction set architecture: affects IC, CPI, Clock cycle time
Caches
n-way set associative cache
The cache is divided in sets of n lines each. The address is divided in three parts, tag, index and block offset. The index tells us which set the data should be in. Each element in the set is then matched against the tag to see if the set contains the item.
Example from exam 2011:
You have a 32b physical address, a 64B cache line, and an 8-way set associative cache. The cache size is 2MB. How many bits are needed for the block offset, the index, and the tag?
You have 2MB of cache, and each line is 64B, which gives us the following expression for the number of cache lines:
Each set contains 8 lines, so the expression for the number of sets you have to calculate is
The simplest thing to calculate is the block offset in the cache line, this is typically a byte-offset. In this example, the block offset needs
Next we need to be able to store the set index, which requires
Finally we use the rest of the address to store the tag,
Hazards and dependencies
In pipelined processors there may be situations where more than one instruction will try to use the same data or instruction within the same frame of time. This may cause inconsistencies. The simple way to handle this is to stall the processor for a few cycles when this happens, but this sacrifice of cycles might not be neccessary, as we often can fix the problem runtime with custom hardware.
Pipeline bubbling
Before talking about the hazards, the term pipeline hazard is important. Pipeline bubbling is simply to delay the execution of an instruction until it is safe to run it.
Data hazards
When two instructions read or write to the same data they may end up with one of the following errors: RAW, WAR or WAW. This is fixed runtime by using the raw data from steps deeper into the pipeline, rather than the data as they are stored. This is called register forwarding.
Structural hazards
When more than one stage of the pipeline use the same resource. This might me something like a situation where the memory is used in multiple stages, and two operations use this resource in the same cycle. This is a bit hard to fix, but may be resolved with out of order execution or pipeline bubbling.
Control hazards
Also known as branch hazards occur when you try to fill the pipeline with instructions after starting a branch instruction. If the branching occurs we may have data running through the pipeline that was not meant to run. Branch prediction may ensure that most of the hazards pass without errors, but when the branch prediction fails we have to use pipeline bubbling.