Improving efficiency of a global barrier operation in a parallel computer

Patent metadata

Field	Value
Publication number	US-9459934-B2
Application number	US-201213683726-A
Country	US
Kind code	B2
Filing date	Nov 21, 2012
Priority date	Aug 10, 2011
Publication date	Oct 4, 2016
Grant date	Oct 4, 2016

Abstract

Performing a global barrier operation in a parallel computer that includes compute nodes coupled for data communications, where each compute node executes tasks, with one task on each compute node designated as a master task, including: for each task on each compute node until all master tasks have joined a global barrier: determining whether the task is a master task; if the task is not a master task, joining a single local barrier; if the task is a master task, joining the global barrier and the single local barrier only after all other tasks on the compute node have joined the single local barrier.

First claim

What is claimed is:

1. A method of performing a global barrier operation in a parallel computer, the parallel computer comprising a plurality of compute nodes, the compute nodes coupled for data communications, each compute node executing a plurality of tasks, with one task on each compute node designated as a master task, the method comprising:
for each task on each compute node until all master tasks have joined a global barrier:
determining whether the task is a master task, wherein each task includes an indicator indicating whether the task is or is not a master task;
if the task is not a master task, joining a single local barrier on a compute node of the plurality of compute nodes;
if the task is a master task, joining both the single local barrier on the compute node and the global barrier only after all other tasks on the compute node have joined the single local barrier on the compute node; and
wherein joining the single local barrier includes atomically incrementing a value of a counter, which tracks tasks that joined the single local barrier, and a number of times equivalent to a result of a difference between a total number of tasks joining the single local barrier and a replacement value, the replacement value comprising a power-of-two greater than or equal to the total number of tasks joining the single local barrier on the compute node.

2. The method of claim 1 wherein joining the single local barrier on the compute node further comprises:
for each task on the compute node:
retrieving a present value of the counter that tracks tasks that joined the single local barrier for the compute node;
calculating, in dependence upon the present value of the counter and the total number of tasks joining the single local barrier on the compute node, a base value of the counter, the base value representing the counter's value prior to any task joining the single local barrier on the compute node;
calculating, in dependence upon the base value and the total number of tasks joining the single local barrier on the compute node, a target value of the counter, the target value representing the counter's value when all tasks have joined the single local barrier on the compute node; and
repetitively, until the present value of the counter is no less than the target value of the counter: retrieving the present value of the counter and determining whether the present value equals the target value.

3. The method of claim 2 wherein:
calculating the base value of the counter further comprises: calculating the base value as zero if the present value of the counter is less than the total number of tasks joining the single local barrier on the compute node, and calculating the base value as the difference between the present value of the counter and a remainder after division of the present value of the counter by the total number of tasks joining the single local barrier on the compute node, if the present value of the counter is not less than or equal to the total number of tasks; and
calculating the target value of the counter further comprises calculating the target value as the sum of the base value and the total number of tasks joining the single local barrier on the compute node.

4. The method of claim 2 wherein:
calculating the base value of the counter further comprises:
establishing the replacement value;
establishing a bitmask, including calculating a bitwise inverse of one less than the replacement value; and
calculating the base value as a result of a bitwise AND operation with the bitmask and the present counter value; and

calculating the target value of the counter further comprises calculating the target value as the sum of the base value and the replacement value.

5. The method of claim 2 wherein calculating the base value of the counter includes establishing the replacement value.

6. The method of claim 2 wherein calculating the target value of the counter further comprises calculating the target value as the sum of the base value and the replacement value.

7. The method of claim 1 wherein the compute nodes of the parallel computer are coupled for data communications by a plurality of data communications networks, the plurality of data communication networks comprising a mesh network and a torus network.

8. The method of claim 1 further comprising, for each task on each compute node until all master tasks have joined the global barrier, if the task is the master task and all other tasks on the compute node have not joined the single local barrier on the compute node, waiting a predefined amount of time before proceeding again to determine whether all tasks have joined the single local barrier.

Assignees

• IBM

Inventors

• Archer Charles J
• Blocksome Michael A
• Ratterman Joseph D
• Smith Brian E

Classifications

• G06F9/46

  Multiprogramming arrangements · CPC title

• G06F9/522 Primary

  Barrier synchronisation · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title

• G06F15/17318

  Parallel communications techniques, e.g. gather, scatter, reduce, roadcast, multicast, all to all · CPC title

• G06F9/542

  Event management; Broadcasting; Multicasting; Notifications · CPC title