Two algorithms for barrier synchronization (Q1114381)

From MaRDI portal
Revision as of 14:38, 13 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    0 references
    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

    Identifiers