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.