Question

Would an application of Tomasulo reservation stations improve instruction misses in the L2 cache and front-end stalling? A yes or no answer is not sufficient – explain your reasoning in detail, preferably with a quantitative example.

Answer 1

The answer is Yes, Tomasulo's algorithm is absolutely revolutionary. And you can certainly create a pipeline without ever using it. University students from around the world do this every year in their computer architecture courses. In fact, you can even create a machine out of service (OOO) without touching Tomasulo's algorithm (see scoring table). For now, we do not know anything about pipes and try to dive into the beauty that Tomasulo had seen almost 60 years ago.

I want you to come back and consider some of the assembly codes you wrote. Since you're talking about Tomasulo's algorithm (or reading more!), I guess you've written enough to have a level of familiarity. At least you need to know the sequential execution model. That is, we followed an instructional program by instruction and executed one at a time. Each instruction is obtained, decoded, executed, and its result stored (if any) before the next instruction goes through the same process. There is no overlap in the execution of instructions. This model is important for processor architects, because that's how compilers and humans work, with the exception of our chips. Technically, there is some room for maneuver (see: precise status and imprecise exceptions), but the sequential execution model is often followed very closely, otherwise the programs are almost impossible to eliminate.

Anyway, when you write a program in assembly language, for example in MIPS, you not only specify the instructions to execute to the processor, but you also specify an order to execute them. This raises the question: are some legal systems better than others? And this answer is absolutely. Realizing this opens up a lot of possibilities and raises many questions.

Now we can deepen the details of CPU architecture and microarchitecture and explain why orders may or may not matter. And there are many wonderful things out there. But for now, consider that some instructions can be executed faster than others. This could be due to something as simple as complexity. For example, adding two whole numbers probably takes less time than multiplying or dividing two numbers. Or, it may be that for some instructions, you still have no data. There are other reasons as well, but they do not matter here.

When you think of a typical assembly statement like the one that follows, you tend to think of what the processor is doing at a high level. The following instruction reads registers r1 and r2, adds them and stores the result in register r0.

    add r0, r1, r2

One could also say that this instruction consumes the registers r1 and r2 and produces a result in the register r0. We can also say that this instruction depends on the instructions that produced r1 and r2. This is a data dependency and usually refers to a read after write (RAW) data dependency. As other authors have pointed out, WAR (write after read or anti-dependency) and WAW (write after write). or exit dependency) also exist. This is not important yet, but we will succeed.

In warehousing architectures (for reasons of simplicity, without loss of generality in the response), we can unify instructions using registers. When you make one instruction produce a value and another instruction consumes it, we can build something more interesting than an individual instruction. It is this ability that allows us to assign all these wonderful high-level language constructs to assembly language instructions in general.

So, how can we represent this information in a slightly different way? Well, one thing we could do is have a graph, where each node represents an instruction, and a vertex directed between these nodes indicates that one node consumes the result of the other.

This may sound a bit odd, especially when you are used to recordings that provide data between instructions. Each MIPS statement reads up to two records and possibly writes to one, after all. But consider the sequential execution model. The archives, as they are, already represent in a certain sense the last instruction he has written to them. In fact, they do not just represent that statement, but all the instructions that generated the values it consumed.