Analysis of composite synchronization
David M. Nicol · 2002
Composite synchronization isa new algorithm that com-bines localized asynchronous coordination, with a global synchronization window. It was developed to simultane-ously address the vulnerability of local synchronization to high model connectivity, and the vulnerability that a global window approach as to a very small minimal channel de-lay. Under composite synchronization, every channel is classified as being either synchronous or asynchronous; the behavior of the algorithm is then determined by the assign-ment. 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 struc-ture. The current paper extends that work, showing how speedup depends upon model topology, and that the assign-ment which maximizes speedup on a multi-cost memory sys-tem likewise has a threshold structure, but need not be ex-actly the same policy as that which minimizes total over-head. I.