### Bounds on the speedup and efficiency of partial synchronization in parallel processing systemsBounds on the speedup and efficiency of partial synchronization in parallel processing systems

Access Restriction
Subscribed

 Author Chang, C. S. ♦ Nelson, R. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1995 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Large deviations theory ♦ Synchronization Abstract In this paper, we derive bounds on the speedup and efficiency of applications that schedule tasks on a set of parallel processors. We assume that the application runs an algorithm that consists of $\textit{N}$ iterations and before starting its $\textit{i}+1st$ iteration, a processor must wait for data (i.e., synchronize) calculated in the $\textit{i}th$ iteration by a subset of the other processors of the system. Processing times and interconnections between iterations are modeled by random variables with possibly deterministic distributions. Scientific applications consisting of iterations of recursive equations are examples of such applications that can be modeled within this formulation. We consider the efficiency of applications and show that, although efficiency decreases with an increase in the number of processors, it has a nonzero limit when the number of processors increases to infinity. We obtain a lower bound for the efficiency by solving an equation that depends on the distribution of task service times and the expected number of tasks needed to be synchronized. We also show that the lower bound is approached if the topology of the processor graph is ldquo;spread-out,” a notion we define in the paper. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1995-01-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 42 Issue Number 1 Page Count 28 Starting Page 204 Ending Page 231

#### Open content in new tab

Source: ACM Digital Library