Main Menu/ Search/ Help
Publications of the Ptolemy Group

Synthesis of Parallel Hardware Implementations from Synchronous Dataflow Graph Specifications

Michael Cameron Williamson

[Postscript] [PDF]


This dissertation describes an approach to digital hardware design for embedded signal processing systems that addresses synthesis, simulation, and interactive design. The objective is to improve productivity and interactivity during design without sacrificing design quality. Our approach consists of automated register-transfer level (RTL) VHDL code generation from synchronous dataflow (SDF) graph specifications, with automated and interactive optimization phases, followed by RTL synthesis and simulation. Our approach is implemented within the Ptolemy simulation and prototyping environment.

We present techniques for mapping applications specified in SDF to parallel digital hardware implementations. Two styles of architecture generation are described. They are a general resource sharing style for flexibility, and the mapping of sequenced groups for compact communication and interconnect. A design flow for hardware synthesis from SDF graphs is presented. In order to minimize cost while meeting performance requirements, we take advantage of opportunities for resource sharing at the coarse-grain task level. Since there are fewer task nodes than in a fine-grain or arithmetic representation of the task graph, determining a near-optimal partitioning is faster in our approach than in behavioral synthesis.

Our approach supports verification through co-simulation. We have constructed simulation techniques for VHDL models generated from SDF semantics. They address partitioned simulation of VHDL models derived from SDF, and simulation of VHDL subsystems derived from SDF within an SDF code-generation subsystems framework. A design flow for simulation of hardware synthesized from SDF graphs is presented. Our approach guarantees that the partitioning does not introduce deadlock or corrupt synchronization, issues that many algorithm-to-implementation design tools do not explicitly address.

An important stage in our approach is the interactive scheduling and partitioning phase for providing feedback to the designer as well as allowing feedback from the designer for finetuning optimization after the automated phase. We characterize useful features for an interactive design tool for hardware synthesis from SDF graph specifications. A prototype of such a tool, integrated into the hardware design flow, is presented. The result is the leveraging of the strengths of both the designer and the tool, rather than the replacement of one by the other.

Send comments to Edward A. Lee at