Main Menu/ Search/ Help
Publications of the Ptolemy Group

Resynchronization for multiprocessor DSP implementation - part 2: Latency-constrained resynchronization.

S. S. Bhattacharyya, S. Sriram, and E. A. Lee

Tech. Rep., Digital Signal Processing Laboratory, University of Maryland, College Park, July 1998. Revised from Technical Memorandum UCB/ERL 96/56, Electronics Research Laboratory, University of California at Berkeley, October, 1996.

[Postscript] [PDF]

ABSTRACT

The companion paper [1] introduced the concept of resynchronization, a post-optimization for static multiprocessor schedules in which extraneous synchronization operations are introduced in such a way that the number of original synchronizations that consequently become redundant significantly exceeds the number of additional synchronizations. Redundant synchronizations are synchronization operations whose corresponding sequencing requirements are enforced completely by other synchronizations in the system. The amount of run-time overhead required for synchronization can be reduced significantly by eliminating redundant synchronizations [2, 3]. Thus, effective resynchronization reduces the net synchronization overhead in the implementation of a multiprocessor schedule, and improves the overall throughput.
However, since additional serialization is imposed by the new synchronizations, resynchronization can produce significant increase in latency. The companion paper [1] develops fundamental properties of resynchronization and studies the problem of optimal resynchronization under the assumption that arbitrary increases in latency can be tolerated ("maximum-throughput resynchronization"). Such an assumption is valid, for example, in a wide variety of simulation applications. This paper addresses the problem of computing an optimal resynchronization among all resynchronizations that do not increase the latency beyond a prespecified upper bound Lmax.
  1. S. S. Bhattacharyya, S. Sriram, and E. A. Lee, Resynchronization for Multiprocessor DSP Implementation Ñ Part 1: Maximum-throughput Resynchronization, Digital Signal Processing Laboratory, University of Maryland at College Park, July, 1998.
  2. S. S. Bhattacharyya, S. Sriram, and E. A. Lee. "Optimizing synchronization in multiprocessor DSP systems," IEEE Transactions on Signal Processing, vol. 45, no. 6, June 1997.
  3. P. L. Shaffer, "Minimization of Interprocessor Synchronization in Multiprocessors with Shared and Private Memory,"International Conference on Parallel Processing, 1989.


Send comments to Edward A. Lee at eal@eecs.berkeley.edu.