This chapter and the next one are important. It covers cpu design. In the early days, computing was hard. Engineers realized they could make it easy by encoding instructions as bit strings. The bit strings get stored in memory. Then the cpu uses the control unit to grab an instruction, decode it, and either use hard wired “random” logic circuitry to execute the instruction, or use a microcode approach in which there is a microcode system that uses an even smaller processor to do micro instructions.
The random logic approach uses latches, counters, etc, and has circuitry for every possible instruction.
Breaking down how CPUs execute mov, add, loop, and jnz
There are detailed breakdowns in the book, but not that important to remember everything. The point is to know how things work in the circuitry intuitively.
Note: All of the assembly stuff I will get from doing a deep dive on x64 with my assembly book
Parallelism One original goal of RISC was to make it so that an instruction would take one clock cycle. However, each instruction has multiple things that need to get done, each stage taking one cycle. So how did it aim to achieve that? Parallelism.
The key here is that each instruction, like mov or something, has a set of things that need to be achieved. However, sometimes those things don’t depend on each other. When that is the case, you can do those in parallel. The key point is that you save cycles by executing individual stages in parallel when possible, and you can bring your average instruction execution down to one cycle per.
There are some nuances to this, for example you can easily parallelize IP updates because the control bus and data bus are different. You cannot yet parallelize gathering the value from a memory address and a register because you only have one data bus. However, there is a sort of solution to this: the prefetch queue.
Note that you cannot send two values through the data bus at once, nor can you run two operations on a logical unit concurrently(for example you can’t process two operations on an alu in parallel). However, if we rearrange the steps and do some magic, we can parallelize some things so that they work in different logical units.
There are detailed examples of this in the book, and that’s pretty neat.
Also, note that for something like a move instruction that requires memory access(not register), you need to calculate the offset into memory. You can wait to do this until after the instruction is decoded(since you don’t actually know if you need to fetch that offset until you know that the instruction is a mov), but you can actually shave cycles off by always fetching the offset anyway at the same time as the instruction decoding happens, and using that offset only if the instruction requires it. This saves time and costs little extra logic, so it’s worth it. You’re essentially pre fetching offsets. Should draw this out in a diagram, that’s really neat actually. We assume the byte coming after the op code is a memory offset, so we grab it. This is wizard stuff, because since we have 64 big data bus, we grab 8 bytes. The byte after the memory address is the op code for the next instruction. So we can keep doing this.
Further improvements come out when you consider that in some of the instruction steps, the data bus is empty. During this time, we can pre fetch the next instruction op code and use the unused data bus cycles. We save these bytes into the prefetch queue.
This needs to be drawn out and diagramed and written about in detail as an article later.
We can also overlap decoding of the next instruction’s opcode with execution of the last step in the previous instruction. This works great, except when the previous instruction changes EIP. But it’s still worth doing. (this is eerily similar to cache hits and misses actually).
Because of all of these optimizations, jumping instructions really mess with things and slow things down. Thus, for fast code, it’s important to not jump around. Note that conditional jumps only invalidate the queue if the branch is taken. Tend towards using shorter instructions.
The prefetch queue is a special example of the more general technique of pipelining. Assuming you’re willing to add hardware, you can execute almost anything in parallel, not just fetching and decoding.
With some intelligent design, you can break each instruction down into uniform steps, and add some silicon and hardware. Then overlay them in a pipeline. This requires more explanation in an article later, it would be fun to write some assembly that is the slowest possible, invalidating all modern performance controls.
There are many cases of issues in pipelines, for example jumps require that the pipeline is flushed which is expensive, and there can be contention for the bus. You don’t want to solve data bus contention by stalling(giving priority to one instruction and waiting in a noop until it’s done just for the next instruction to take place), so we do what engineers do to solve every problem and add in an instruction cache. This way, the prefetch queue gets instructions from the instruction cache(inside the cpu) which means that the data bus is free to use unless there is a cache miss.
Caches are fixed size, so you want to keep your instructions short which allows more of them to be in the cache. So again, short instructions, avoid jumps.
control hazards are the ones that we mentioned that flush the pipeline. data hazards occur when the next instruction needs to load data that the previous instruction stores, but does it before the previous instruction actually stores the data. I should draw this out too. This is some more wizard shit too. Regular cisc processors handle these hazards by introducing delays in the pipeline. However, you can get rid of these often times by rearranging instructions. Check page 251.
This is totally sick. I need to write more assembly so I can do the optimizations myself and then compare them to how the compiler does it. Make the assembly purposefully super slow or super fast.
It turns out that all of this is a scheduling problem, which is eerily similar to the operating systems scheduling problem. The way you order instructions, and which ones you choose to use, dictates how they get scheduled(especially on cpus that are superscalar and have multiple execution units that may process things out of order etc).
All of this stuff is also similar to lisp and how you want to have as little state as possible when worried about parallel executions. Or even goroutines and having them stuck waiting to read from a channel. That is essentially the equivalent of a pipeline stall, or at least similar.
Often times, registers aren’t actually registers. The programmer sees EAX, but EAX in the CPU is a bank of registers, namely EAX[0], EAX[1], etc. The cpu automatically uses different spots in the banks so that you can run multiple mov(eax, 5) instructions in parallel for example.