Architectures specific compilation for efficient execution of esterel
Simon Yuan · ResearchSpace (University of Auckland) · 2013
Software for embedded systems has traditionally been written in languages such as C. However, C does not provide primitives for describing concurrency and typically requires an operating system (OS) for emulating concurrency. The combined e ect of scheduling in the OS and the lack of semantics introduce non-deterministic behaviour to the system. Subsequently, when problems arise, they are often di cult to reproduce and debug. The synchronous programming paradigm o ers a refreshing approach to speci cation of system level design. The formal semantics of synchronous programming languages established a well de ned behaviour of the primitives provided by them such that the behaviour of any implementation of these languages strictly follow their semantics. As a result, both the high level speci cations and their implementation are closely associated. Esterel is one of such synchronous languages, featuring imperative style syntax, native concurrency, preemption and exception. While Esterel o ers powerful features, compiling Esterel has been challenging. The conventional approaches to Esterel compilation for software require implementing an Esterel program with complex and low level control- ow using C. The overhead from such implementations often rivals the actual control code of Esterel. Alternatively, Esterel programs can be translated to digital circuits as the synchronous nature of Esterel maps well to the behaviour of logic gates. This hardware approach o ers the best performance at the cost of exibility compared to the software approach. This thesis seeks to address these problems with a novel intermediate approach by compiling Esterel for hardware architectures tailored for execution of Esterel. To overcome the limitations of the software and hardware implementation of Esterel, we introduce an execution platform that accelerates the execution of Esterel with a set of Esterel-oriented instructions for handling concurrency and preemption in hardware. Experimental results have shown signi cant reduction in generated code size while gaining speedups compared to the pure software approach. Another aspect of compilation of Esterel that has been relatively unexplored is the implementation of its concurrency with true parallelism on multi-core architectures. There have been minimal attempts to address compilation of Esterel for multi-cores due to the challenges of preserving Esterel semantics with true parallelism and gain speedups against sequential execution. To address the problem of compiling Esterel for multi-core, we have adopted the dynamic scheduling technique such that the problem scheduling and load distribution can be addressed independently. This thesis covers a static approach and a dynamic approach for distributed execution on multi-cores. Experimental results have shown that the speedups gained from static distribution are highly dependent on the amount of data code in Esterel, whereas speedups are achieved with both control and data-dominated Esterel programs using the dynamic distribution approach.