Cosynthesis of Control and Dataflow

Researchers: Geroncio Galicia
Advisor:Edward A. Lee
Sponsor:
This project is concerned with the development of software tools and methodologies to aid the electronic systems designer with the specification and synthesis of large, complex, and adaptive DSP systems consisting of heterogeneous components. For any given task addressed by the specification there are a myriad of possible solutions in each of the implementation domains: custom ASICs, commercial off-the-shelf processors, pre-existing embedded subsystems, software modules, etc. Moreover, in networked environments, the computational resources available to accomplish a task may vary dynamically. Mapping available resources into an efficient and integrated implementation that meets hard real-time deadlines while keeping the exploration of the large design space manageable is the goal of this research. Here efficiency is defined with respect to a combination of quality of service, area, power, and cost.

The initial models of computation (MoC) considered are hierarchical finite-state machine (FSM) and synchronous dataflow (SDF) [1] for the specification of the control and dataflow portions of a system, respectively. SDF is the preferred MoC for high-throughput DSP where no task-level control or decision is involved. It is related to models used in SPW by the Alta Group of Cadence and COSSAP by Synopsys. Hierarchical FSM can describe the evolution of states, or modes of operation, within a system. Combination of the two allows the description of a larger set of applications [2].

This research will attempt to determine limitations on the scope of applications described by hierarchical FSM/SDF, algorithms for optimal mappings of FSM/SDF descriptions into hardware and software, an extension of the extended partitioning algorithm [3] to encompass hierarchical FSM/SDF, and mappings onto process networks (PN) [4] to determine boundedness and termination properties of the description. These investigations will be carried out within the Ptolemy environment [5] where several MoCs, including hierarchical FSM/SDF and PN, coexist in a heterogeneous framework. Of current interest are automated code generation tools and performance estimation models for high-throughput and high-bandwidth interconnect embedded multicomputer architectures such as the Mercury RACEway [6][7].

[1]
E. A. Lee and D. G. Messerschmitt, ``Synchronous data flow,'' Proceedings of the IEEE, vol. 75, pp. 1235-1245, September 1987.
[2]
W.-T. Chang, A. Kalavade, and E. A. Lee, ``Effective heterogeneous design and cosimulation,'' in Hardware/Software Co-Design (G. De Micheli and M. Sami, eds.), pp. 187-212, Kluwer Academic Publishers, 1996.
[3]
A. Kalavade and E. A. Lee, ``The extended partitioning problem: Hardware/software mapping and implementation-bin selection,'' in IEEE International Workshop on Rapid System Prototyping, pp. 12-18, June 1995.
[4]
T. M. Parks, Bounded Scheduling of Process Networks. Memorandum No. UCB/ERL M95/105, University of California at Berkeley, 1995.
[5]
J. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt, ``Ptolemy: A framework for simulating and prototyping heterogeneous systems,'' Int. J. of Comput. Sim., vol. 4, pp. 155-182, April 1994.
[6]
E. K. Pauer and J. B. Prime, ``An architectural trade capability using the Ptolemy kernel,'' in IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 2, pp. 1252-1255, May 1996.
[7]
B. C. Kuszmaul, ``The RACE network architecture,'' in International Parallel Processing Symposium, pp. 508-513, April 1995.