Main Menu/ Search/ Help
Publications of the Ptolemy Group

Optimizing Synchronization In Multiprocessor Dsp Systems

by Shuvra S. Bhattacharyya, Sundararajan Sriram, and Edward A. Lee

IEEE Transactions on Signal Processing, Vol. 45, No. 6, June 1997.

ABSTRACT

This paper is concerned with multiprocessor implementations of embedded applications specified as iterative dataflow programs, in which synchronization overhead can be significant. We develop tech niques to alleviate this overhead by determining a minimal set of processor synchronizations that are essential for correct execution. Our study is based in the context of self-timed execution of iterative data flow programs. An iterative dataflow program consists of a dataflow representation of the body of a loop that is to be iterated an indefinite number of times; dataflow programming in this form has been studied and applied extensively, particularly in the context of signal processing software. Self-timed execution refers to a combined compile-time/run-time scheduling strategy in which processors synchronize with one another only based on inter-processor communication requirements, and thus, synchronization of proces sors at the end of each loop iteration does not generally occur.

We introduce a new graph-theoretic framework, based on a data structure called the synchroniza tion graph, for analyzing and optimizing synchronization overhead in self-timed, iterative dataflow pro grams. We show that the comprehensive techniques that have been developed for removing redundant synchronizations in non-iterative programs can be extended in this framework to optimally remove redun dant synchronizations in our context. We also present an optimization that converts a feedforward dataflow graph into a strongly connected graph in such a way as to reduce synchronization overhead without slow ing down execution.

Send comments to S. Sriram at sriram@hc.ti.com.