Synthesis of Embedded Software using Dataflow Schedule Graphs

Abstract

In the design and implementation of digital signal processing (DSP) systems, dataflow is recognized as a natural model for specifying applications, and dataflow enables useful model-based methodologies for analysis, synthesis, and optimization of implementations. A wide range of embedded signal processing applications can be designed efficiently using the high level abstractions that are provided by dataflow programming models. In addition to their use in parallelizing computations for faster execution, dataflow graphs have additional advantages that stem from their modularity and formal foundation. An important problem in the development of dataflow-based design tools is the automated synthesis of software from dataflow representations. In this thesis, we develop new software synthesis techniques for dataflow based design and implementation of signal processing systems. An important task in software synthesis from dataflow graphs is that of {\em scheduling}. Scheduling refers to the assignment of actors to processing resources and the ordering of actors that share the same resource. Scheduling typically involves very complex design spaces, and has a significant impact on most relevant implementation metrics, including latency, throughput, energy consumption, and memory requirements. In this thesis, we integrate a model-based representation, called the {\em dataflow schedule graph} ({\em DSG}), into the software synthesis process. The DSG approach allows designers to model a schedule for a dataflow graph as a separate dataflow graph, thereby providing a formal, abstract (platform- and language-independent) representation for the schedule. While we demonstrate this DSG-integrated software synthesis capability by translating DSGs into OpenCL implementations, the use of a model-based schedule representation makes the approach readily retargetable to other implementation languages. We also investigate a number of optimization techniques to improve the efficiency of software that is synthesized from DSGs. Through experimental evaluation of the generated software, we demonstrate the correctness and efficiency of our new techniques for dataflow-based software synthesis and optimization.