Lab 3: Scheduling Impact on Used Memory Size

Designers must be aware of how the different decisions they take influence both the targeted and other properties of their final system. Scheduling, for instance, although primarily targeting latency/throughput, will also affect the memory usage due to the data stored and passed around throughout the system. This lab will look at how a schedule for an SDF impacts the size of the memory needed for the channel buffers.

Assume you have the SDF in the figure below, with actors A, B, C, D, and the specified token production/consumption specified in the figure. For this exercise, disregard the actual functionality and treat them as generic SDF actors that can fire when there are enough tokens on their inputs.

For the moment, let's work on a single processor. The order of firing these actors will affect how the tokens are produced in the channels between them and therefore affect the buffer sizes needed to store these tokens. For this purpose, we created a Ptolemy model that can help with examining these sizes: ScheduleABCD.xml 

In this model, there is a Scheduler composite actor that accepts as parameters:

• a string of letters, ABBBAABCCDBAADD..., representing the firing order of the actors
• the length of this sequence (in characters)

The Scheduler issues firing commands to four other composite actors modeling our actors A, B, C, D plus their input buffer - in order to keep track of the number of tokens in the buffers (Note: we found no easier way of monitoring buffer sizes in Ptolemy directly). These four actors output the current size of their input buffer - which is the plot using a SequencePlotter. These actors also have two other ports, an input and an output which have their purpose - left for you to determine as an exercise.

At the moment, the Scheduler generates a very simple round-robin schedule: ABCD. Running this system will show that certain buffers will grow forever, requiring infinite memory - obviously not feasible in practice. Note also that not all actors will be able to fire every time so switching to actors that cannot fire will make the schedule even more suboptimal.

Starting with this model and adding any observation points or displays or aggregates your task is to experiment with and figure out the following:

1. Derive and solve the balance equations for the given model. (see 6.3.2 in the Lee&Seshia book)
2. What schedule (sequence of letters) of the format AAA...ABB...BCC...CDD...D will result in a bound buffer utilization when repeated forever? How many A, B, C, Ds does such a sequence have? What are the maximum buffer sizes needed for this?
3. Is there another schedule that minimizes these buffer sizes? What is the size of the largest buffer in this case?
4. Assume all buffers from before share the same memory. Find a schedule that minimizes this memory, e.g. at any moment the total number of tokens is minimized (you can safely assume all tokens have the same size of 1).
5. Assume we would like to use two processors so that some actors will run on the first processor and the rest on the second - making it possible for two actors to run in parallel. Modify the model to reflect this change (no need to change the internals of the actors!). How will this affect the buffer sizes above?

For a pass, you should show simulations supporting your finds for each of the above. A theoretical background can be found in 6.3.2 of the Lee&Seshia book.