Workload Arbiter

Here we give an example application where a scheduler dynamically determines which worker should receive which packet at runtime. We create an architecture shown in the animation on the right.

Architectural Description: There is a scheduler is responsible for reading data from a work list in DRAM. It should distribute this data by issuing each packet to one of three workers, based on a schedule that attempts to issue the newest command to the “least busy” worker. Each worker processes to the end of its inbound work queue, and remains idle if the queue is empty. After all packets have been processed, the scheduler broadcasts a “done” packet to all of its workers. When each worker sees this packet, it issues a signal to the final stage to wrap up the computation. This final stage has three inbound streams and will begin only when all three have valid data.

Function Descriptions (not shown in animation): The scheduling function we use keeps a score for each worker, where the “length” of a packet is added to the score when the new packet is issued, and decrements one from the score each cycle. Each worker parses the integer “payload” of the packet, and increments an external counter for that many counts. It also tracks the “index” of the payload in a local history so that we can reconstruct which worker processed which packet afterwards. The finisher reports the status of the architecture, and interleaves the histories of the three workers into a single list.

Note, there are cleaner ways to express this particular application, but we choose to sprawl much of the code to demonstrate the concepts. The functions in this particular architecture are contrived, but learning the concepts from this example will help you generalize to more complicated apps without making common mistakes.

We start by defining a full_packet type. which describes the data fields we will have in our “packet.”

We then define some properties that we will use later in the application. maxQueue is a sizing parameter for on-chip memories. HEAVY, MEDIUM, LIGHT, and DONE are values that the payload field of a packet may take.

We allow the total number of packets to be set at runtime, as long as it is less than maxQueue. We set up the DRAM which will hold all of the packets. For no particular reason, we choose to have a heavy packet, followed by a medium packet, followed by light packets, and repeat this pattern for every 7 packets.

We create counters as HostIOs, which will be responsible for logging the amount of “work” each worker has done. We initialize them all to 0 (don’t want any workers to cheat!)

We also create a status reg, we use to guarantee that the final stage has a side effect and none of the primitives inside of it will be eliminated as dead code.

While this app can be written as a tiled application, we choose to load the entire work list on chip in the localQueue.

We create a separate, tiny queue for each worker. The reason we chose to set the queue so small is to stress-test the case where the scheduler wants to issue a new packet to a worker who is already full. Because of implementation details of the backend, if the scheduler chooses a filled queue, it will wait until it drains one of its packets rather than issuing to a different worker.

We also allocate a history FIFO for each worker and size it so that we are guaranteed it will not fill up for any one worker and stall the entire app. We also inject a dummy value into each, because it will be read down below in the FINISHER stage of the processor. If, for some reason, one of the workers never activated, this pre-enqueue of a dummy value guarantees that the final stage will not be stalled forever while it waits for all three history FIFOs to have at least one element. We can choose to ignore the dummy value later, if we want.

We create boolean registers that will be used later in the application by each worker to forcibly break out of an infinite loop. These will only be triggered when the DONE packet is processed by the worker.

We create FIFORegs as the interface between each worker and the final stage. We know that each worker will need to send the done signal once, so we want a FIFO of size one to mediate the interaction between the workers and the final stage. We can create a FIFO of size one to handle this, or we can use the FIFOReg, which is a simplified FIFO with only one element.

We define what we want the scheduling function to be, given a new packet. In this example, we create a workLoad register for each worker. Each time we enqueue to that worker, we add the payload for the packet to this register. We decrement these registers each time this scheduler runs.

We also define the rules for processing a packet. Specifically, we just enqueue the idx part of the packet payload to the history for this worker, and increment the worker’s counter as many times as the payload dictates.

The key concept in this app is to bind all of the controllers outlined in the animation above in a Stream controller. We want the controller to run once, so we can dump the code for all of the children controllers directly into the body of the Stream. Each of the five controller blocks shown in the animation is tagged with its name: SCHEDULER, WORKER1, WORKER2, WORKER3, and FINISHER.

In the SCHEDULER controller, we iterate over each of the packets in the work list. We send the packet to our scheduler function, who will populate the correct queue with the new packet. The last thing this controller does is check if this is the last packet, and issue the DONE packet if so. The tricky part about this is that we need to guarantee that this special packet will not jump ahead of a true work packet. Without this Pipe explicitly gating the final packet generation from the rest of the controller, the retimer inside of Spatial will see a short chain of primitives being used to generate the DONE enqueue, and potentially a long but independent chain of primitives being used to generate the work packet enqueue (inside of schedule()). Retiming preserves program order in some cases, but this is not one of those cases in the current version of Spatial.

Next, we create three WORKERs. The only difference between each worker is that they operate on a different history queue and counter register. Each counter is set to run forever, using the Foreach(*) syntax. We choose to use an infinite counter in these controllers because we want each worker to run any time it receives a packet, regardless of how many packets it has processed already. The direct parent of these workers is the Stream controller, so as long as the inbound work queue has a valid element, the controller will get to run for another iteration. The only way these workers can send a done signal to their parent is when their respective breakWhen register raises. We allocated these registers previously, but we set them inside the body of the worker. Spatial only supports breakWhen for unparallelized Sequential and Stream controllers. Breaking a Sequential controller is the safest way to map the idea of a loop break to hardware, because the scheduling ensures there is no pipelining and no way for previous iterations to still be draining through the retime chains when the break condition is raised. Because of this, using this syntax for Stream controllers is strongly discouraged, because it can easily lead to unexpected behavior. There are only a few limited and specific cases where a Stream should be used with a breakWhen condition.

We finish by using the three done FIFORegs to trigger the FINISHER pipe. Only when all three of these registers have valid data will the controller enable and process its body. We start by setting the status ArgOut, and then we interleave the history data from each of the workers. We choose to use an FSM here, which dequeues from one FIFO at a time and determines which one has the lowest index. We then tag the aggregatedHistory with an id for the worker that worked on a particular packet until all three history packets have been drained. We then send this information out to DRAM.

On the host, we check if the app did what we expected it to do. We ensure that all three workers combined have processed the entire work list by checking if the sum of the three counters is equal to the sum of the work list. We expect that each worker processed roughly the same amount, especially if a large number of packets was used. We also check to make sure each of the packets was truly claimed by one of the workers by looking at the aggregated history. We expect to see that the workload was distributed evenly among the workers by a somewhat random pattern in the history.