Download An LLVM Back-end for REPLICA: Code Generation for a Multi

40
Optimization
5. Was the recently scheduled sub-instruction an OP sub-instruction?
• Yes, then add the following sub-instruction that uses the result from the
OP sub-instruction to the priority list. The resources needed by the subinstruction were checked when the OP sub-instruction was scheduled. Go to
step 6.
• No, then go to step 6.
6. Get the sub-instructions freed by scheduling the current sub-instruction and add
them to the ready list or, if the current sub-instruction was a WB, to the delay list.
Go to step 1.
4.3.2
Similarities to task scheduling
The algorithm is similar to Grahams task scheduling algorithm [16]. In Grahams task
scheduling algorithm we have a system with m tasks that should be processed by n
processors [16]. There can be dependencies between tasks so if task Tj is dependent on
task Ti then Tj must be processed later than Ti [16]. Tasks are kept on a list ordered
according to dependencies so for example Ti would come before Tj on this list [16]. A
processor searches the list from beginning to end looking for a task that can be processed.
If no task was found then the processor becomes idle until another processor finishes and
new tasks becomes available [16].
If we let Grahams processors correspond to our functional units and let tasks correspond to our sub-instructions then we can compare it to our scheduling approach for
REPLICA. REPLICA has several functional units that are assigned sub-instructions by
our algorithm. Our sub-instructions are ordered so that a sub-instruction I1 must be
executed before sub-instruction I2 if I2 depends on I1 . Functional units that are not assigned any sub-instruction can be seen as idle until a sub-instruction that matches that
functional unit is found.
Grahams processors can execute any task [16] while REPLICA sub-instructions are
keyed to a specific type of functional unit. Either operator, ALU, memory unit, compare
unit, sequencer or writeback. Hence functional units may be idle even though free subinstructions are available.
MBTACs chaining capability lets dependent sub-instructions be executed in parallel
in most cases. Writebacks is an exception where the sub-instruction dependent on the
writeback needs to wait until the next execution step. Grahams tasks on the other hand
have no chaining capability so if two tasks are dependent then the second task will have
to wait until the first has been executed before it can be scheduled [16].
The tasks in Grahams list scheduling algorithm do not have the constraint that certain
tasks must be executed in parallel [16] as REPLICAs OP sub-instructions have.
4.3.3
Time complexity
In any given basic block there would always be at least one sub-instruction that can be
scheduled in the current execution step. In a worst case scenario we could have a basic
block with n sub-instructions which consists of first k independent sub-instructions, that
uses the same functional unit, and then m sub-instructions where each sub-instruction is
dependent on the previous. Figure 4.5 shows how a worst case dependence DAG might
look like.
• At the start of the algorithm the k sub-instructions and the first of the m subinstructions are added to the ready list.