Processor architecture and organization
Summing a matrix by traversing it by columns instead of by rows can drop the cache hit rate from 87 % to 0 %. The algorithm is the same; what changes is the order.
01Architecture and organization
There are two ways of looking at a processor. The architecture is the contract with the software: the instruction set, the visible registers, the addressing modes, the memory model. The organization (or microarchitecture) is how that contract is fulfilled in silicon: how many stages the pipeline has, which caches there are, how many instructions are executed at once. Two processors with the same architecture, such as a Cortex-M0 and a Cortex-M7, run the same code with very different organizations and performance. The general view of CPU, memory and buses is in the computer system page of Computer Science I and in microprocessor architecture, from the technician program.
The first organization decision is how instructions and data arrive. In the von Neumann architecture they share memory and bus; in the Harvard architecture, they have separate memories and buses and can be read at the same time. Almost all current processors are modified Harvard: a single main memory, but separate instruction and data caches.
02The instruction set
| CISC | RISC | |
|---|---|---|
| Instructions | Many, some of them complex, of variable length | Few and simple, of fixed length (32 bits) |
| Memory access | Almost any instruction can operate on memory | Only the load and store instructions |
| Registers | Few, with special uses | Many general-purpose ones (32 in RISC-V) |
| Examples | x86, 8051 | ARM, RISC-V, AVR, MIPS |
The simplicity of RISC is what allows execution to be pipelined efficiently: all instructions go through the same stages and take the same time in each one. Modern x86 processors translate their complex instructions internally into RISC-like micro-operations.
03The performance equation
The compiler and the instruction set decide \( N_{instr} \); the organization decides the CPI; the technology and the depth of the pipeline decide the clock. Comparing processors by their clock frequency alone ignores the other two factors.
04Pipelining
A pipeline divides execution into stages, and each stage works on a different instruction at the same time, like an assembly line. The classic five stages: instruction fetch (IF), decode and register read (ID), execute (EX), memory access (MEM) and write-back of the result (WB). Ideally it finishes one instruction per cycle, and the clock can be up to five times faster than without pipelining.
| Hazard | Cause | Solution |
|---|---|---|
| Structural | Two stages need the same resource | Duplicate the resource: separate instruction and data memories |
| Data | An instruction needs a result that has not been written yet | Forwarding from the later stages; if that is not enough, a bubble |
| Control | A branch is resolved only in EX, with instructions already fetched behind it | Branch prediction; if it fails, the fetched instructions are discarded |
05Memory hierarchy and cache
A processor executes an instruction per nanosecond, and a DRAM takes tens of nanoseconds to respond. The solution is a hierarchy: a small, fast memory, the cache, keeps copies of what was used recently. It works because programs have locality: temporal (what was used is used again) and spatial (after one address, the next one is used). That is why the cache brings in entire lines of 32 or 64 bytes.
The address is divided into three fields: the offset chooses the byte within the line, the index chooses the set where it can be, and the tag is compared to find out whether the stored line is the one sought. In a direct-mapped cache each line has only one possible place; in an n-way set-associative cache, n places.
Misses have three causes: compulsory (the first access to a line), capacity (the program uses more data than fits) and conflict (lines that compete for the same set even though there is room in others). The last depend on the addresses, and the same algorithm can be fast or slow depending on how it traverses the data.
A data cache with LRU replacement receives the address sequence of a short program. The strip at the top shows the first 512 accesses (green, hit; red, miss) and the grid shows which array occupies each line at the end. 1 cycle per hit and 100 per miss are assumed.
06Beyond one instruction per cycle
| Technique | What it does | Where |
|---|---|---|
| Superscalar | Several instructions per cycle, with out-of-order execution | Computer and phone processors |
| SIMD | One instruction operates on several data items at once | Vector extensions for audio, video and neural networks |
| Multicore | Several complete processors on one chip, with shared caches | Almost everything that is not a simple microcontroller |
| DSP | Multiply-accumulate in one cycle and circular addressing | Digital filters and signal processing |
07In the lab
Write in C the sum of a 2048 × 2048 matrix traversed by rows and by columns, measure the times on a computer and explain the difference in terms of the cache.
On a microcontroller with a cycle counter, measure how many cycles a loop takes and compare it with the assembly code the compiler generated.
Draw the diagram of a five-stage pipeline for a sequence of six instructions with two data dependencies, with and without forwarding, and count the cycles.
08Common mistakes
- Comparing processors by clock alone. The CPI and the number of instructions weigh just as much.
- Traversing a matrix against the way it is stored. In C it is stored by rows; traversing it by columns can multiply the time.
- Using power-of-two sizes and spacings without thinking. They make the cache indices coincide and cause conflict misses.
- Confusing architecture with organization. The same ARM binary runs on very different processors.
09Self-assessment
How is a 32-bit address divided in a 4 KB direct-mapped cache with 32 B lines?
5 offset bits, 7 index bits (128 lines) and 20 tag bits.
What average access time does a 2 % miss rate give with 1 cycle for a hit and 80 of penalty?
\( 1 + 0.02 \cdot 80 = 2.6 \) cycles.
A program goes from CPI 2 to CPI 1.2, but the clock drops from 1 GHz to 800 MHz. Is it an improvement?
Yes: the time per instruction goes from 2 ns to 1.5 ns.
What type of miss does increasing associativity eliminate?
Conflict misses. Capacity misses need a larger cache, and compulsory misses, longer lines or prefetching.
10Further reading
- David A. Patterson and John L. Hennessy. Computer Organization and Design: RISC-V Edition. 2nd ed., Morgan Kaufmann, 2020. The course text: instruction set, pipeline and memory hierarchy on RISC-V.
- John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. 6th ed., Morgan Kaufmann, 2017. The next level: instruction-level parallelism, advanced caches and accelerators.
- Sarah L. Harris and David Harris. Digital Design and Computer Architecture: RISC-V Edition. Morgan Kaufmann, 2021. Builds a complete RISC-V processor in HDL, starting from the gates.