Four-ary tree-based barrier synchronization for 2D meshes without nonmember involvement

This paper proposes a Barrier Tree for Meshes (BTM) to minimize the barrier synchronization latency for two-dimensional (2D) meshes. The proposed BTM scheme has two distinguishing features. First, the synchronization tree is 4-ary. The synchronization latency of the BTM scheme is asymptotically Theta (log(4) n), while that of the fastest scheme reported in the literature is bounded between Omega (log(3) n) and O(n(1/2)), where n is the number of member nodes. Second, nonmember nodes are neither involved in the construction of a BTM nor actively participate in the synchronization operations, which avoids interference among different process groups during synchronization. This not only results in low setup overhead, but also reduces the synchronization latency. The low setup overhead is particularly effective for the dynamic process model provided in MPI-2. Extensive simulation study shows that, for up to 64 x 64 meshes, the BTM scheme results in about 40 similar to 70 percent shorter synchronization latency and is more scalable than conventional schemes.
Publisher
IEEE COMPUTER SOC
Issue Date
2001-08
Language
ENG
Keywords

WORMHOLE; COMMUNICATION; IMPLEMENTATION; MULTICOMPUTERS; NETWORKS

Citation

IEEE TRANSACTIONS ON COMPUTERS, v.50, no.8, pp.811 - 823

ISSN
0018-9340
URI
http://hdl.handle.net/10203/85037
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 155
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 4 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0