Modulo scheduling with rational initiation intervals

It was great to have Patrick Sittel visit our group earlier this year. This blog post is about the work he and I did during his visit, which has been accepted as a paper (co-authored with Martin Kumm and Peter Zipf) at ASP-DAC 2020.

Suppose we wish to fit a row of tiles to a bathroom wall in a rather particular way. Our endeavour can be broken down into the following five tasks, each of which must be performed on each tile.

  • Task 1. Collect a tile and fix it to the next position on the wall.
  • Task 2. Select any colour except the final (i.e. post-varnishing) colour of the previous-but-one tile.
  • Task 3. Paint the tile with the chosen colour.
  • Task 4. Apply a coat of varnish to the tile.
  • Task 5. Sprinkle the tile with glitter.

Let us assume that each task takes exactly one minute. If we hire just one worker, we would expect them to be able to process one tile every five minutes. But if we can afford to hire more workers, can we get the job done faster?

We can, but before we start them all working at once, we need to be careful about which tasks depend on each other. For instance, we cannot sprinkle the tile with glitter (Task 5) until we have varnished it (Task 4), or else the glitter might not stick to the tile. We cannot varnish the tile until it has been painted (Task 3). And we cannot paint the tile until we have collected the tile (Task 1) and selected a colour for it (Task 2). The most subtle dependency is between Task 2 and Task 4: we cannot select a colour for the current tile until we have varnished the last-but-one tile, since varnishing a tile might alter its colour.

We can depict all these dependencies in the following diagram.

Screenshot 2019-09-05 at 10.17.44

The arrow labelled “2” means that Task 2 depends on Task 4 being completed from two tiles ago. The other arrows represent dependencies between tasks on the same tile. (We can imagine that they are labelled with “0”.)

Now, suppose we have three workers available. How should we allocate tasks to them, and in which order? The table below shows one possible schedule for the workers.

Screenshot 2019-09-05 at 10.51.00

Worker A alternates between Task 1 and Task 3, Worker B alternates between Task 2 and Task 4, and Worker C is responsible only for Task 5. Note that each tile has its tasks done in an appropriate order: Task 1 and Task 2 are done simultaneously, and then Task 3, Task 4, and Task 5 follow in sequence. And crucially, note that we do not begin Task 2 until Task 4 has been completed on the previous-but-one tile. For instance, note that Task 2 on tile 5 is scheduled after Task 4 on tile 3.

On the left-hand side of the table, a little blue triangle indicates the times when a new tile is collected. We see that this happens every two minutes. So, the benefit of trebling our workforce is that we can improve our tiling rate from 0.2 tiles per minute to 0.5 tiles per minute — we are now 2.5 times faster!

We’re not thrilled by this outcome, however. From a 3x increase in workforce, we might hope for a 3x increase in productivity! The crux of the problem is obvious enough: Worker C is scheduled to do nothing half of the time. Can we do anything to improve this situation? It’s not obvious that we can, given the awkwardness of trying to split five tasks evenly between three workers.

It turns out that we can do better if we allow our tiling rate to fluctuate over time. Here is a schedule that does that.

Screenshot 2019-09-05 at 11.13.29

In this schedule, each tile is processed by just one worker – for instance, tile 1 has all of its tasks performed by Worker A. Except for the first few minutes, all three workers are kept busy the whole time (unlike in our first schedule). And unlike our first schedule, the rate at which tiles are collected is not constant – as shown by the blue triangles, the interval between tile collections is two minutes, then two minutes, then one minute, and then the pattern repeats. In other words, this schedule is able to process three tiles every five minutes, or 0.6 tiles per minute. We are now 3x faster than the 0.2 tiles per minute that we managed with just one worker, just as we would hope.

Now, our paper is not actually about fixing tiles to walls, but about scheduling operations when designing a piece of hardware. Traditional hardware design tools limit themselves to schedules where the interval between operations is a fixed integer, as in the first schedule above. In our work, we present a tool that also considers schedules where this interval fluctuates, as in the second schedule above. We call these intervals “rational” because the average among these fluctuations can be interpreted as a rational number. We show that, just like we saw in our tiling example, this additional flexibility can lead to the discovery of better schedules that keep all the hardware components busy all of the time, and ultimately, lead to faster hardware.

2 thoughts on “Modulo scheduling with rational initiation intervals”

  1. This reminds me of a board game! I highly recommend it : Azul

    Nice writeup, a really neat and descriptive way of explaining the concept 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s