Two algorithms for barrier synchronization (Q1114381): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01379320 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2084557272 / rank | |||
Normal rank |
Latest revision as of 11:16, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two algorithms for barrier synchronization |
scientific article |
Statements
Two algorithms for barrier synchronization (English)
0 references
1988
0 references
We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to \textit{E. D. Brooks} [ibid. 15, 295-307 (1986; Zbl 0641.68010)]. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brooks' communication pattern with an information dissemination algorithm described by Hand and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brooks' original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of the n processes meeting at the barrier must be assigned identifiers i such that \(0\leq i<n\).
0 references
barrier synchronization
0 references
shared-memory multicomputer
0 references