next up previous contents
Next: Continuation to Multiple Phases Up: Continuing Operators Previous: Continuing Operators

Simple Continuation

The first issue to realize is that it is not sufficient to place a copy of the operator in each phase--e.g., to have a separate broadcast from node zero added to the set of operators in each phase from the example above. If this was done, there would be separate VFSMs associated with the operator in each phase, and the compiler (or application) would have to ensure that all the VFSMs from the previous phase had cleared before switching to the new phase; however, the semantics of a continuing operator is that the source may write data into it at any time, so it is difficult to guarantee that the operator's stream(s) from the previous phase are empty before switching to the new phase.

Instead, the compiler simply forces the stream to use the same VFSMs in the following phase(s). This way, the stream can simply be ignored during any phase changes; any buffered data in an intermediate VFSM will simply be re-launched once the schedule for the new phase is initiated, since the VFSM will be the same in both the new and old schedule.

In this simple case, continuing streams do not have to be scheduled in the same time slots. The buffering associated with a VFSM means that the compiler can safely stop scheduling a VFSM for some period of time, then reschedule it, without losing any data; the data will simply wait in the buffer. If no buffering were allocated to VFSMs (perhaps because the compiler were able to assert that the receiving processors could always keep up with the data flow), it would be impossible to switch phases like this, since data would be dropped as soon as the compiler stopped scheduling a VFSM belonging to a stream actively carrying data.

Furthermore, a continuing stream can be rescheduled to have different bandwidth if necessary. Consider the case where the continuing operator shares one phase with some operator with traffic 4T , and the next phase with an operator with traffic T . The continuing operator should end up with proportionately more bandwidth in the second phase, since the continuing operator is likely to be in the critical path unless its bandwidth is increased.

Regardless of the scheduling, the exact sequence of VFSMs that carry data must be preserved. In particular, this requires that the stream follow the same route, use the same pipelines on each node, and even include delays in the same point(s) in the new routing. When routing the stream in the second and following phases, this is given as a requirement for the stream router. Doing so reduces the router's flexibility somewhat, but still allows it to choose arbitrary timeslots in the global schedule to place the stream in the new schedule.


next up previous contents
Next: Continuation to Multiple Phases Up: Continuing Operators Previous: Continuing Operators
Back to Chris Metcalf's home page