Agner`s CPU blog

Thank you for the reference to Explicit Data Graph Execution (EDGE) https://en.wikipedia.org/wiki/Explicit_data_graph_execution
If the EDGE principle can be implemented smoothly, it might be more efficient than splitting a job into multiple threads running in multiple cores. The thread management, synchronization, and communication between threads is very complicated and inefficient in current systems. An alternative would certainly be worth exploring.

However, I don't quite understand how the Hyperblocks are coded and delimited.

- Registers are the accumulator (ac), and a rotating register file with 4 partitions of 16 registers (a0-a15, b0-b15, c0-c15, d0-d15). The ALLOC instruction shifts down register file names, so for instance ALLOC d10..d15 will move down the previous contents of d15 to d9, the content of d14 to d8, d13->d7, d12->d6, d11->d5, d10->d4, d9->d3, d8->d2, d7->d1, d6->d0, and the contents of d0..d5 are lost. The new values in registers d10..d15 are marked as "uninitialized" and instructions that try to read them will stall until the registers are written to. ALLOC is always in the form of aN..b15, bN..b15, cN..c15, dN..d15 and can allocate from multiple partitions at the same time.

- Each non-accumulator register can only be written to once (!). This means that it's basically a form of hardware SSA. This is why there are multiple partitions: values have multiple classes of life duration: extremely short (accumulator), very short (would probably use d0..d15, typically used for multi-use temporary values and merging 2 branches of calculation), loop counters (c0..c15, get rewritten every loop), and then various long lived values like loop constants and stack pointers and the like (aN and bN).

- Instructions come in groups. Each group is a sequence of serial instructions, and operates on the accumulator: the first operation of the group must not have any dependency on the previous state of the accumulator, but then subsequent instructions modify the accumulator. Every instruction always writes to the accumulator, plus optionally also has a store to a register from the rotating register file. Example of group:
mul ac, d14, b15 ;no dependency on the previous state of the accumulator, start of group
sar ac, 16
add ac, d13, st d12 ;result goes in both accumulator and d12
add ac, d15, st d11 ;result goes to both accumulator and d11, group ends

- Memory loads/stores must use [register+immediate] as addressing mode (it's not possible to use the accumulator as part of address calculations), and are separately issued in-order, independent of ALU instruction grouping.

- The ALLOC instruction is also not part of ALU instruction grouping.

- The reason for this weird design is that it makes register renaming very easy: every time an ALLOC instruction comes up, you simply increase the rotation index for the target register partitions and clear the 'value ready' bit for the new register names (and also check that the physical registers you're using are free). Once that is done, every single following ALU operation group is _guaranteed_ to be parallelizable (aside from the memory loads/stores) because every register name is unique!

- Each new ALU instruction group is queued to a free ALU, and each ALU runs one instruction per cycle from its group of cycles. If the instruction's rotating register file operand doesn't have its 'value ready' bit on, then this instruction group stalls until the value becomes ready (in other words, it waits until the value gets stored by an ALU or memory load operation).

- Register file renaming can be done late by the ALUs, since the rotating register file index of each partition is recorded when the group starts. This also means that every ALU can practically have its own ICACHE - they can be _scheduled_ 100% independently from other instructions!

- Multiple ALU groups can be scheduled per cycle, in any order(!). The only thing that has to be done in order is register renaming using the ALLOC instruction and memory loads and stores.

- For the C++ compiler, working from SSA, it has to tag all the operations that are part of a series of operations, to form groups. This is not that hard as far as I can tell: every time a value is only used by the next operation in the sequence, then it can be passed using the accumulator instead. Generally, all single-destination values can be assigned to the accumulator. Since the compiler knows how long each value lives, it can make sure register file renames using ALLOC never wipe out values that are still in use (although it does have to figure out the lifespan of each value).

This design still needs lots of refinement (especially in the area of loads/stores, calling convention...) and is more complex than I'd like (hence the 'this is weird' warning), and probably also fairly out-there, and potentially doesn't gain too much over the traditional out-of-order RISC (if the whole thing is limited by memory performance in particular), and reminds me of the Itanium at times, but it does have the advantage of being relatively implementable and compilable, and in theory there's no limit to the number of ALUs you can run in parallel (I can easily see designs with 4, 8, even more ALUs).