|Advisor:||Edward A. Lee|
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)  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 .
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 , at the risk of possible loss of parallelism.
Past work focused on scheduling SDF graphs on heterogeneous multiprocessors with interprocessor communication , and optimizing the tradeoff between SDF clustering and exploitability of parallelism . Current research will attempt to extend these techniques to schedule SDF/FSM descriptions onto multiple heterogeneous processors.