MiA: Superscalar and Out-of-Order Logic Elements [Copied from gitea]

[AlexanderRipar]

This is a copy of an old gitea issue

It outlines the then-current state of the logic elements necessary to model Superscalar Out-of-Order cores in the MiA, problems with them and potential solutions.

As an old issue it contains some stuff that is now irrelevant as far as I know (e.g. micro-ops in the MiA). I'm putting it here as a reference point for further ideas on how superscalar out-of-order architectures might be specified in future.

---

Related issues:

vadl/vadl#671 Mapping between ISA and MiA

This issue tracks the discussion of the necessary logic element types needed to model superscalar and out-of-order (OoO) execution in the MiA.

The issue itself contains the current state as shown in the VADL paper, identifies some issues with it and sketches potential solutions to some of them.

Any contributions, whether in the form of clarifications, additional problems, or alternative solutions are greatly appreciated.

Current State

Disclaimer

Please forgive my abuse of type signatures, as I am not yet familiar with how these are supposed to be specified in VADL.
I am barely familiar with the functions of the logic elements described hereafter, so please take everything you read with a pile of salt.
This does not yet include information from the VADL language reference.

While the logic elements and built-ins necessary to describe OoO and superscalar microarchitectures are not yet implemented in any generators, some are briefly described in The Vienna Architecture Description Language (pages 17 and 18):

[reservation station] logic

A reservation station sits somewhere ahead of the functional units of a superscalar processor as a sort of "staging area" where instructions wait for their inputs to be ready. As soon as all inputs are available instructions can leave the reservation station and continue down the pipeline in any order, facilitating out-of-order execution.
The only additional annotation that appears on [reservation station] in the paper is [size = ⟨N⟩], indicating the available buffer size.

[reorder buffer] logic

A reorder buffer takes the results of instructions that (may) have been executed out-of-order and reorders their stores so that they once again appear in program order.
The reorder buffer also seems to usually (always?) take care of register renaming, storing results to available internal registers and establishing the mapping from architectural registers to these. Additionally, it has a connection back to the reservation station(s), letting it know when results are available for further instructions.
In the paper, [reorder buffer] is annotated with the [renames ⟨register file⟩] and [size = ⟨N⟩] annotations. These indicate the renamed register file and the number of internal registers available for renaming respectively.

operation ⟨foo⟩ = { ⟨instruction names⟩ }

As far as I see this seems to be specifically intended for use with filter.

filter( instructions, ⟨operation set⟩ )

This along with dispatch described below appears to be the central mechanism for describing dispatch to multiple functional units in VADL. It takes a vector of instructions and a previously defined operation set as inputs, and returns only those instructions that match the set.

[reservation station].dispatch( instructions )

Takes a vector of instructions and "dispatches" them to the reservation station. I believe this is meant to model the splitting of instructions to multiple functional units when used together with filter to split up an instruction stream and consume to perform further processing on it.

[reservation station].consume

Removes a ready instruction (i.e. an instruction with all of its inputs available) from the reservation station and returns it.

| (Combine operator)

As the name implies, this combines multiple (potentially empty?) instructions which have previously been split using filter and dispatch. In the paper this is used to mark instructions from multiple execution units as completed after they have executed.

instructions.markAsCompleted( [reorder buffer] )

Not sure what this does. Any input is appreciated. The paper only has the following to say (second-to-last paragraph on page 17):

The processor then marks all instructions in the joined instruction stream as completed in the reorder buffer.
Note that this step happens in the order of the instruction execution, not the program order.

[reorder buffer].retire( UInt (?) )

Removes the instruction from the reorder buffer and "publishes" all of its side-effects. This happens in program order, and basically models the main functionality of the reorder buffer.

Potential problems

This section outlines problems identified by @LHalder and @aripar, particularly with respect to the current state of reservation station and its associated built-in functions.
Note that some of these problems - and particularly their potential solutions - partially overlap.

Unclear semantics of filter with overlapping operation sets

It is not clear to me what happens when a single instruction is filtered more than once and then dispatched multiple times. Is it actually dispatched to each reservation station that is listed or is one selected (possibly nondeterministically or at least in a non-user-visible way)?
The paper appears to imply that multiple equivalent functional units are currently realised by letting them consume from the same reservation station. The problem with this appears to be twofold: First, it does not allow having separate reservation stations (and thus separate buffers) on identical functional units, forcing them to share a single one. Secondly, it prohibits functional units with partially overlapping functionality, which appear to be quite common in modern architectures (imagine two integer ALUs, but one implementing IDIV, the other IMUL).

No mechanism for prioritising dispatch

In many modern architectures a single instruction can be dispatched to more than one functional unit. The decision to which unit it is actually dispatched is likely quite involved and dynamic.
As a concrete example given by Anton Ertl, some Intel chipsets decide on which functional unit ("Port" in intel parlance) an instruction will be dispatched from the (unified) reservation station a few cycles ahead of the actual dispatch. This can be measured by closely looking at throughput under certain workloads, as the selected functional unit might be at capacity when dispatch actually occurs. (citation needed)

Redundant modelling of equivalent functional units

Equivalent functional units must be modelled by copy-pasting all of their stages. The paper quickly mentions this by indicating a setup with two integer units, with one's EXECUTE stage only specified as

stage IntegerExu2 = // equal to IntegerExu1

As far as I can tell this goes directly against VADL's spirit of eliminating redundant specifications.

This will be covered by the macro system extended to the MiA section.

Mismatch between VADL reservation station semantics and some actual architectures (in particular "unified" reservation stations)

VADL only supports reservation stations after dispatch (with the caveat that it only supports them before selecting between equivalent functional units, as these are modelled using consume?), since the dispatch built-in dispatches directly to a reservation station. However, the relation between dispatch and reservation stations in real architectures seems more complex.
Some architectures have a single "unified" reservation station, which holds all instructions and from which they are dispatched to the functional units.
Other architectures seem to employ a setup where each reservation station serves a few functional units, or even have a 1:1 mapping between reservation stations and functional units, putting the reservation stations after the dispatch logic as in VADL.
Lack of micro-ops which are usually the thing actually handled at this level instead of ISA instructions

As far as I understand the Instruction type used in the MiA covers this problem pretty well. The one place where this could turn into a problem is with operation sets, which seem to identify instructions by their names. However, this seems pretty fundamental to any other form of implementing dispatch logic, so it might be a more inherent issue.

Potential solutions

One approach that seems to solve out most of the above problems is to create a new logic element [functional unit] (or some more fitting name, I do not know the details of what distinguishes a functional unit from a functional core or such). This would then take over as the target for dispatching from [reservation station].
Additionally, it could support an annotation such as [multiplicity = ⟨N⟩], which would solve the need for redundant equal stage definitions by instantiating ⟨N⟩ stages for each consume from the annotated functional unit. This would require some logic to (optionally?) carry forward the behaviour of multiple stage definitions through further stages that use the consuming stage's results. The devil is likely in the details here.
This would solve all listed problems apart from dispatch prioritisation and lack of micro-ops.

Additionally, dispatch prioritisation could be solved either by additional annotations on functional units, or maybe on an additional dispatch logic element for central specifications that only need to be specified once.
Alternatively, if this does not provide sufficient flexibility, users might be allowed to specify free-form functions that implement this behaviour, similar to how e.g. address mapping is currently implemented.

The problem of missing micro-ops seems like a bigger nut to crack, but might not even be a problem in the first place.