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.
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
Send comments to S. Sriram at firstname.lastname@example.org.