TY - GEN
T1 - Analysis of composite synchronization
AU - Nicol, D.
N1 - Funding Information:
This research is supported in part by DARPA Contract N66001-96-C-8530, NSF Grant ANI-98 08964, NSF Grant EIA-98-02068, and Dept. of Justice contract 2000-CX-K001
Publisher Copyright:
© 2002 IEEE.
PY - 2002
Y1 - 2002
N2 - Composite synchronization is a new algorithm that combines localized asynchronous coordination, with a global synchronization window. It was developed to simultaneously address the vulnerability of local synchronization to high model connectivity, and the vulnerability that a global window approach has to a very small minimal channel delay. Under composite synchronization, every channel is classified as being either synchronous or asynchronous; the behavior of the algorithm is then determined by the assignment. In an earlier work we proposed the algorithm, and showed that the channel assignment which minimizes the sum of all synchronization overhead, on an architecture with uniform memory access costs, has a threshold structure. The current paper extends that work, showing how speedup depends upon model topology, and that the assignment which maximizes speedup on a multi-costmemory system likewise has a threshold structure, but need not be exactly the same policy as that which minimizes total overhead.
AB - Composite synchronization is a new algorithm that combines localized asynchronous coordination, with a global synchronization window. It was developed to simultaneously address the vulnerability of local synchronization to high model connectivity, and the vulnerability that a global window approach has to a very small minimal channel delay. Under composite synchronization, every channel is classified as being either synchronous or asynchronous; the behavior of the algorithm is then determined by the assignment. In an earlier work we proposed the algorithm, and showed that the channel assignment which minimizes the sum of all synchronization overhead, on an architecture with uniform memory access costs, has a threshold structure. The current paper extends that work, showing how speedup depends upon model topology, and that the assignment which maximizes speedup on a multi-costmemory system likewise has a threshold structure, but need not be exactly the same policy as that which minimizes total overhead.
UR - http://www.scopus.com/inward/record.url?scp=84964475918&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964475918&partnerID=8YFLogxK
U2 - 10.1109/PADS.2002.1004207
DO - 10.1109/PADS.2002.1004207
M3 - Conference contribution
AN - SCOPUS:84964475918
T3 - Proceedings - 16th Workshop on Parallel and Distributed Simulation, PADS 2002
SP - 104
EP - 113
BT - Proceedings - 16th Workshop on Parallel and Distributed Simulation, PADS 2002
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 16th Workshop on Parallel and Distributed Simulation, PADS 2002
Y2 - 12 May 2002 through 15 May 2002
ER -