Multiprocessor Code Generation from Control and Dataflow Descriptions

Researchers: Geroncio Galicia
Advisor:Edward A. Lee

This work is concerned with the generation of efficient code for reactive multiprocessor-based systems from a control and dataflow description. This task is complicated by the requirements of reactive systems, the presence of heterogeneous processors in the target implementation, interprocessor communication costs, and a design space that can grow exponentially relative to the application's size and complexity.

Reactive systems are systems that interact continuously with their environment at that environment's speed. They are also typically embedded systems with limited resources. Therefore candidate implementations are constrained to those with predictable execution times and those that avoid deadlock in their execution. Modelling the specification using a restricted form of dataflow called synchronous dataflow (SDF) [1] ensures that a valid execution of the SDF graph will have a static schedule, will have bounded communication buffer sizes, and will not deadlock. SDF is useful for modelling concurrency and numerical computations but is inadequate for modelling sequential control. Certain combinations of hierarchical finite state machine (FSM) and SDF semantics allow modelling of both computation and control while keeping the determination of deadlock and bounded memory execution decidable [2].

Another problem with scheduling SDF graphs onto multiple processors occurs when a directed acyclic graph (DAG) of SDF actor firings is constructed. A small multirate SDF graph can result in a DAG with actor nodes that number in the thousands. To combat this complexity, SDF actors can be clustered into larger grain nodes, in accordance with the SDF composition theorem [4], at the risk of possible loss of parallelism.

Past work focused on scheduling SDF graphs on heterogeneous multiprocessors with interprocessor communication [3], and optimizing the tradeoff between SDF clustering and exploitability of parallelism [4]. Current research will attempt to extend these techniques to schedule SDF/FSM descriptions onto multiple heterogeneous processors.

E. A. Lee and D. G. Messerschmitt, ``Synchronous data flow,'' Proceedings of the IEEE, vol. 75, pp. 1235-1245, September 1987.
A. Girault, B. Lee, and E. A. Lee, A Preliminary Study of Hierarchical Finite State Machines with Multiple Concurrency Models. Memorandum No. UCB/ERL M97/57, University of California at Berkeley, 1997.
G. C. Sih, Multiprocessor Scheduling to Account for Interprocessor Communication. Memorandum No. UCB/ERL M91/29, University of California at Berkeley, 1991.
J. L. Pino, S. S. Bhattacharyya, and E. A. Lee, A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs. Memorandum No. UCB/ERL M95/36, University of California at Berkeley, 1995.