4 ms·
CPUs run Tomasulos algorithm ( https://en.m.wikipedia.org/wiki/Tomasulo_algorithm https://en.m.wikipedia.org/wiki/Tomasulo_algorithm ). Then the outputs of Tom
by dragontamer 6y ago
CPUs run Tomasulos algorithm
( https://en.m.wikipedia.org/wiki/Tomasulo_algorithm https://en.m.wikipedia.org/wiki/Tomasulo_algorithm ). Then the outputs of Tomasulos algorithm allows for out of order execution across multiple execution units.
Note that Intel chips have many (at least 10) execution units, and AMD also has 10. You need to split instructions to the different pipelines for efficient execution. I forget exactly how much... but far more than one pipeline in any case.
If pipeline0 is busy doing a divide, run additions in Pipeline5. Tomasulos algorithm converts typical assembly language into this multi-pipeline form. It also keeps track of which pipelines are busy, and finally puts things back together in the right order when done. (Division can take 80 clock cycles, while addition takes 1. You gotta stall the results of the addition instruction until after division is complete. If division came first in the machine code)
- Waterluvian 6y agoThanks for this. I had no idea what to search for but this is a good start. I guess it's unsurprising to find that even at the single cpu core level, there's another layer of parallelism. And that will of course complicate things further.
- dragontamer 6y agoNote: Parallelism comes in many forms on CPUs. Pipelines, superscalar, out-of-order, and speculative. Of these concepts, Tomasulo's algorithm covers Pipelines, Superscalar, and out-of-order. So its the "most complex example", but that should get you up to speed the quickest. (Branch prediction / speculative is its own thing, but I've always found the concept to be simple to grasp: you're executing instructions in parallel, so you need to guess the results of a branch before the branch is even calculated). When it comes to actual execution of the final microop itself, its surprisingly simple. You put the bits in the right location, then a circuit magically calculates the result. XOR and Add are simple enough (https://en.wikipedia.org/wiki/Carry-save_adder https://en.wikipedia.org/wiki/Carry-save_adder). A multiplier is harder to think about, but yes, its just a bunch of wires hooked up to NAND gates: https://www.slideshare.net/suryakrishna3785/wallace-tree-multiplierpptx1 https://www.slideshare.net/suryakrishna3785/wallace-tree-mul... Division and Modulo are traditionally executed with microops in a multi-step process. Addition becomes subtraction through the magic of 2s complement. AND, OR, XOR, are trivial logic gates. Memory lookup is complicated, but mostly due to caching. The core concept of memory lookup (put value onto address pins, wait for memory to respond with the stored value) is simple enough. Memory is traditionally on a "bus". The idea of a "bus" (multiple different CPU components talking on the same set of wires) is hard to grasp. But when you learn about tri-state logic (https://en.wikipedia.org/wiki/Three-state_logic https://en.wikipedia.org/wiki/Three-state_logic), the 5V state, 0V state, and "High Impedance" state, it becomes simple. "High Impedance" means that someone connected to the wires simply won't read, or write, on those wires. The CURRENT (amps) going in, or out, is set to zero through the magic of transistors. If you have 5 different components (C0, C1, C2, C3, and C4) on a set of wires, if C1/C2/C3 are in "High Impedance", then C0 and C4 can talk without any issues (because C1 through C3 won't use up any electricity from the wires). The key is coordinating who can talk and at what times. But that's where "link level protocols" start to come in. Tri-state logic (in particular: high impedance) is what makes it possible. And there ya go. A fully working CPU. That's all it is.
- kens 6y agoNice description! Even a simple ALU has a lot more complexity than you're giving it credit for, though. It's not "just" a bunch of gates, but is usually highly optimized with dynamic logic and pass-transistor logic. Addition in particular is not "simple", but uses various tricks to avoid carry propagation delay. And the various ALU operations are smashed together in clever ways to avoid separate circuits for XOR, add, AND, OR, etc. Even XOR is not a "trivial logic gate"; building XOR from e.g. NAND gates is surprisingly inefficient, so processors use a variety of special tricks for XOR. My point is that actual ALUs haven't matched the simple description since about 1972.
- dragontamer 6y ago> Addition in particular is not "simple" Well... optimized addition isn't simple. But any beginner can implement naive carry-save adders on a breadboard (or Verilog/FPGAs) and get a functional Adder (maybe even ALU) in a weekend. But you're right. To optimize addition (in particular: the propagation of carries), you need to use a Kogge-Stone Adder, which is pretty sophisticated (https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder). And that's from my Bachelor's degree: I'm sure there are newer algorithms that are more sophisticated than Kogge-Stone. There's a lot of issues at play here at the electricity level. IE: Fanout. All components can only carry so much current (amps). For example, a transistor may only be able to feed 5 to 10 other transistors, so building "Buffers" to increase the current so that you can actually turn on all the transistors is a thing. Each CMOS transistor has capacitance: so you need a certain amount of electrons before the transistor turns on. Given a level of current (amps), this means you need to wait for enough electrons to get onto the input before the transistor responds. Doing all of this with the minimal energy usage and maximum speed (minimum latency) is surely complicated. But the "naive" version suitable for beginner play is pretty simple. Like raytracers: you can write a raytracer in just 100 lines of code (it won't be as fast as a professional raytracer, nor have as many features, but you'd get the gist in a single weekend project: https://github.com/matt77hias/smallpt https://github.com/matt77hias/smallpt) --------- In any case, once you get to the final decoded instruction, its "just" a circuit. Sure, Kogge-Stone and Wallace Tree multipliers need a bit of study before you understand them. But they're simple black-boxes. Stick the bits into the correct wires and then a few hundred picoseconds later, you got the result coming out of another wire.
- jasonwatkinspdx 6y agoThis is THE textbook on the subject: https://www.amazon.com/Computer-Architecture-Quantitative-John-Hennessy/dp/012383872X https://www.amazon.com/Computer-Architecture-Quantitative-Jo... There are older editions available free online that cover the same concepts, they just don't have the very latest info.
- tpxl 6y agoI will add a reference to one of the highest rated stack overflow posts about branch prediction (speculative execution): https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...