use by following instructions, even in the same cycle, and even if the
operation is totally different. Thus, unlike in a
traditional vectore architecture, ALUs may be occupied by elements from
-other "Lanes", because of the pre-existing decoupling between the multi-issue
-instruction queue and the ALUs.
+other "Lanes", because the pre-existing decoupling between the multi-issue
+instruction queue and the ALUs is efficiently leveraged.
Simple!
-[[reorder_buffer.jpg]]
+# Tomasulo Algorithm and Reorder Buffers
There are many other benefits to a multi-issue microarchitecture, and
these are being discussed
commonly taught in Universities, and, secondly, patents on the algorithm
have long since expired.
+[[reorder_buffer.jpg]]
+
Also, there are both memory hazards and register hazards that a Reorder
Buffer augmented Tomasulo algorithm takes care of, whilst also allowing
for branch prediction and really simple roll-back, preservation of
simply does not care. In addition, there may be a really simple way to
extend the Reorder Buffer tags to accomodate SIMD-style characteristics.
-We also may need to have simple Branch Prediction, because some of the
-loops in [Kazan](https://salsa.debian.org/Kazan-team/kazan/) are particularly
-tight. A Reorder Buffer can easily be used to implement Branch Prediction,
-because, just as with an Exception, the ROB needs to be cleared out
-(flushed) if the branch is mispredicted. As it is necessary to respect
-Exceptions, the logic has to exist to clear out the ROB: Branch Prediction
-simply uses this pre-existing logic.
+We also may need to have simple Branch Prediction, because some of
+the loops in [Kazan](https://salsa.debian.org/Kazan-team/kazan/)
+are particularly tight. A Reorder Buffer (ROB) can easily be used
+to implement Branch Prediction, because, just as with an Exception,
+the ROB can to be cleared out (flushed) if the branch is mispredicted.
+As it is necessary to respect Exceptions, the logic has to exist to
+clear out the ROB: Branch Prediction simply uses this pre-existing logic.
The other way in which out-of-order execution can be handled is called
scoreboarding, as well as explicit register renaming. These schemes
* There's no clear way to handle branch prediction, where the Reorder
Buffer of Tomasulo handles it really cleanly.
+However there are downsides to Reorder Buffers:
+
+* The Common Data Bus may become a serious bottleneck, as it delivers
+ data from multiple ALUs which may be generating results simultaneously.
+ To keep up with result generation, *multiple* CDBs may be needed, which
+ results in each receiver having multiple ports
+* The Destination field in the ROB has to act as a key in a CAM (Content
+ Addressble Memory). As a result, power consumption of the ROB may be
+ quite high. It may or may not be possible to reduce power consumption
+ by testing an "active" bitfield (separate from but augmenting the ROB)
+ to indicate whether Destination Registers are in use. If inactive,
+ the CAM lookup need not take place.
+
Whilst nothing's firmly set in stone, here, as we have a Charter that
requires unanimous decision-making from contributors, so far it's leaning
towards Reorder Buffers and Tomasulo as a good, clean fit. In part that
is down to more research having been done on that particular algorithm.
-More as it happens...
+For completeness, scoreboarding and explicit register renaming need
+to be properly and comprehensively investigted.
+
+# Scoreboarding
+
+[Scoreboards](https://en.wikipedia.org/wiki/Scoreboarding) are an
+effort to keep "score" of whether an instruction has all of its
+operands (and the hardware that uses them) ready to go, without conflict.
+Everything about the scheme, unfortunately, says that it is an incomplete
+mechanism. Unlike the Tomasulo algorithm when augmented with a Reorder
+Buffer, there's no way to "undo" a completed operation: the operation
+proceeds and modifies registers or memory, in an out-of-order fashion,
+regardless of consequences. If an exception occurred *tough*!
+
+Hence, it was quite hard to accept scoreboarding enough to understand it.
+It wasn't until
+[this message](http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2018-December/000223.html)
+that I realised that there is near-direct equivalence between the features
+of scoreboarding and the Tomasulo Algorithm. It's not complete equivalence,
+because the Reorder Buffer is what keeps everything transactional and clean.
+However, at least the scoreboard does have direct equivalence to the
+Reservation Station concept: the scoreboard records whether the source
+registers are ready or not (and so does the Reservation Station).
+
+The problem is: there are far too many things missing from the scoreboard
+concept:
+
+* Register-renaming has to be done separately (the Tomasulo Reservation
+ Stations, in combination with the ROB, handle that implicitly).
+* Scoreboarding introduces the concept of "waffly exceptions"
+ (the ROB can even record exceptions that are only actioned if they
+ make it to the head of the queue).
+* Scoreboarding does not provide a means to do multi-issue (the ROB
+ does: you just put more than one entry per cycle into the buffer)
+
+# Next step
+
+The project is being run along ethical lines. That in particular means
+unanimous decision-making. Nobody gets to over-rule anyone else: everyone
+matters, and everyone's input matters. So if I, personally, think that
+Tomasulo is better, it's up to me to keep on researching and evaluating
+and reasoning until I have convinced everyone else... or they have convinced
+me otherwise.
+
+I have it on good authority from some extremely comprehensive research
+that this is a hell of a lot better way to do decision-making than
+"mob-rule" voting. "Mob-rule" voting (aka "democracy") basically
+*automatically* destroys the morale and discounts the will of the
+"minority". No wonder democratic countries have "Minority Representation
+Political Groups", because it's heavily brainwash-ingrained into people
+living in such countries that the "Minority" view *shall* be disregarded;
+of *course* they feel the need to shout and get angry!
+
+Learning from these mistakes, which are often copied and reflected
+in Software Libre groups, is I feel very important, to try something
+different. In previous Libre projects that I've run, I was the
+kind-of informal "technical lead", where I never actually defined any
+guidelines or rules about how the project should make decisions: basically
+I let people do what they liked unless it disrupted the project for
+everyone else. I set myself up as the "arbitrator", so to speak.
+The way that this project will be run is very much new and experimental,
+even to me. We'll see how it goes.
+
projects / crowdsupply.git / blobdiff