The Semantics and Execution of a Synchronous Block-Diagram Language

Stephen A. Edwards and Edward A. Lee

Science of Computer Programming, Vol. 48 No.1, pp. 21-42,July, 2003

[PDF]

 

ABSTRACT

We present a new block diagram language for describing synchronous software. It coordinates the execution of synchronous, concurrent software modules, allowing real-time systems to be assembled from precompiled blocks specified in other languages. The semantics we present, based on fixed points, is deterministic even in the presence of instantaneous feedback. The execution policy develops a static schedule - a fixed order in which to execute the blocks that makes the system execution predictable.

We present exact and heuristic algorithms for finding schedules that minimize system execution time, and show that good schedules can be found quickly. The scheduling algorithms are applicable to other problems where large systems of equations need to be solved.