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

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M95/70
September 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/ERL-95-70.pdf

This paper introduces a technique, called resynchronization, for reducing synchronization overhead in embedded multiprocessor implementations. The technique exploits the well-known observation [39] that in a given multiprocessor implementation, certain synchronization operations may be redundant in the sense that their associated sequencing requirements are ensured by other synchronizations in the system. The goal of resynchronization is to introduce new synchronizations in such a way that the number of additional synchronizations that become redundant exceeds the number of new synchronizations that are added, and thus the net synchronization cost is reduced. First, we define the general form of our resynchronization problem; we show that it is NP hard by establishing a correspondence to the set covering problem; and based on this correspondence, we specify how an arbitray heuristic for set covering can be applied to yield a heuristic for resynchronization. Next, we show that for a certain class of applications, optimal resynchronizations can be computed efficiently by means of pipelining. These pipelined solutions, however, can suffer from significantly increased latency, and this motivates the latency-constrained resynchronization problem, which we address for a restricted class of graphs that permit efficient computation of latency. Again using a reduction from set covering (although the construction is significantly different), we show that latency-constrained resynchronization is NP hard. However, we show that for the special case in which there are only two processors, latency-constrained resynchronization can be solved in polynomial time. We also present a heuristic for latency-constrained resynchronization, and through a practical example, we demonstrate that this heuristic gives an efficient means for systematically trading off between synchronization overhead and latency.

BibTeX citation:

@techreport{Bhattacharyya:M95/70,
    Author = {Bhattacharyya, S.S. and Sriram, S. and Lee, Edward A.},
    Title = {Resynchronization for Embedded Multiprocessors},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2854.html},
    Number = {UCB/ERL M95/70},
    Abstract = {This paper introduces a technique, called resynchronization, for reducing synchronization overhead in embedded multiprocessor implementations. The technique exploits the well-known observation [39] that in a given multiprocessor implementation, certain synchronization operations may be redundant in the sense that their associated sequencing requirements are ensured by other synchronizations in the system. The goal of resynchronization is to introduce new synchronizations in such a way that the number of additional synchronizations that become redundant exceeds the number of new synchronizations that are added, and thus the net synchronization cost is reduced. First, we define the general form of our resynchronization problem; we show that it is NP hard by establishing a correspondence to the set covering problem; and based on this correspondence, we specify how an arbitray heuristic for set covering can be applied to yield a heuristic for resynchronization. Next, we show that for a certain class of applications, optimal resynchronizations can be computed efficiently by means of pipelining. These pipelined solutions, however, can suffer from significantly increased latency, and this motivates the latency-constrained resynchronization problem, which we address for a restricted class of graphs that permit efficient computation of latency. Again using a reduction from set covering (although the construction is significantly different), we show that latency-constrained resynchronization is NP hard. However, we show that for the special case in which there are only two processors, latency-constrained resynchronization  can be solved in polynomial time. We also present a heuristic for latency-constrained resynchronization, and through a practical example, we demonstrate that this heuristic gives an efficient means for systematically trading off between synchronization overhead and latency.}
}

EndNote citation:

%0 Report
%A Bhattacharyya, S.S.
%A Sriram, S.
%A Lee, Edward A.
%T Resynchronization for Embedded Multiprocessors
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/ERL M95/70
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2854.html
%F Bhattacharyya:M95/70