Blocking local sense synchronization barrier

• US 7,770,170 B2
• Filed: 07/12/2005
• Issued: 08/03/2010
• Est. Priority Date: 07/12/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Morrison, Jonathan D., Clift, Neill M., Kishan, Arun U., Rector, John
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): To; Jennifer N
• Application Number:
  US11/180,338
• Publication Number:
  US 20070016905A1
• Time in Patent Office: 1,848 Days
• Field of Search: 718100-108, 717/100, 717/158, 710/200, 707/999.08, 711/145, 711/149
• US Class Current: 718/102
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/522 Barrier synchronisation
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A blocking local sense synchronization barrier is provided. The local sense variable is not processor private or global, but truly local to the synchronization barrier function. Safe deletion is provided by making sure the last operation a thread performs on a barrier is a write. Just before returning, threads increment a field that indicates the count of threads that have left the barrier. Blocking is supported such that threads spin for some interval, and when they decide to block, examine and set (if not already set) the indication of whether a thread is blocking that is to be examined by the last thread to arrive at the barrier to determine whether to set an event to release blocking threads.

Claims

1. A method comprising:

concurrently executing software threads on parallel processors;

synchronizing the concurrently executing software threads via a synchronization barrier implemented via a synchronization barrier method having a property that no thread of the concurrently executing software threads can return from a call before all threads of the concurrently executing software threads have entered it; and

providing a variable that is to be changed within the synchronization barrier method, and read to determine when software threads should be released, wherein said variable is a local sense variable that is strictly local to the synchronization barrier method and neither a global variable nor a processor private variable, and wherein said variable is known within a block of code associated with the synchronization barrier method, but inaccessible to code outside the block.

2. The method of claim 1 wherein the value of the variable is not stored outside of the synchronization barrier method.

3. The method of claim 1 wherein the value of the variable is not stored across calls to the synchronization barrier method.

4. A method comprising:

concurrently executing software threads on parallel processors;

synchronizing the concurrently executing software threads via a synchronization barrier implemented via a synchronization barrier method having a property that no thread of the concurrently executing software threads can return from a call before all threads of the concurrently executing software threads have entered it; and

ensuring a last operation each thread performs before returning from the synchronization barrier method is a write operation on a count variable within said synchronization barrier method which indicates a number of threads that have left the synchronization barrier; and

reclaiming the synchronization barrier when said count variable indicates that all threads have left the synchronization barrier, wherein the count variable is known within a block of code associated with the synchronization barrier method, but inaccessible to code outside the block.

5. The method of claim 4 wherein said count variable serves a dual role of storing a total number of threads that have arrived at the synchronization barrier and counting the number of threads which have left the synchronization barrier.

6. The method of claim 4 further comprising initializing the count variable by setting a field to be a predetermined value by a last thread to arrive at the barrier before releasing other threads from the barrier;

and wherein a thread performs a write operation on said count variable by incrementing a count value in the field before that thread returns.

7. The method of claim 4 further comprising:

using an indication of whether a thread is blocking to determine whether a thread is blocking;

resetting a previous event by a last thread to arrive at the barrier;

determining whether to reset a current event by the last thread to arrive at the barrier by examining the indication of whether a thread is blocking;

releasing spinning threads waiting for the last thread to arrive at the barrier; and

setting a current event by the last thread to arrive at the barrier to release threads that are blocking while waiting for the last thread to arrive if indicated to do so by the examination of the indication of whether a thread is blocking.

8. The method of claim 7 wherein the act of using an indication of whether a thread is blocking to determine whether a thread is blocking comprises:

examining the indication of whether a thread is blocking by a thread deciding to block;

setting the indication of whether a thread is blocking by a thread deciding to block, if the indication of whether a thread is blocking is not set, in order to indicate that the last thread to arrive at the barrier must set the event;

examining a variable by the thread deciding to block that indicates whether the last thread has arrived at the barrier;

waiting by blocking until the event is set, if the variable examined indicated that the last thread has not arrived at the barrier.

9. A method comprising:

concurrently executing software threads on parallel processors;

synchronizing the concurrently executing software threads via a synchronization barrier implemented via a synchronization barrier method having a property that no thread of the concurrently executing software threads can return from a call before all threads of the concurrently executing software threads have entered it;

providing a variable that is to be changed within the synchronization barrier method, and examined to determine when software threads should be released, wherein said variable is a local sense variable that is strictly local to the synchronization barrier method and neither a global variable nor a processor private variable;

providing an indication of whether a thread is blocking, which is used to determine whether a thread is blocking, wherein the indication of whether a thread is blocking is created only at a time when a thread decides to block;

when a last thread arrives at the synchronization barrier,

resetting a previous event;

releasing spinning threads waiting for the last thread to arrive at the synchronization barrier by changing the local sense variable;

examining the indication of whether a thread is blocking to determine whether a thread is blocking; and

setting a current event to release threads that are blocking while waiting for the last thread to arrive, if indicated to do so by the examination of the indication of whether a thread is blocking.

10. A computer readable storage medium having computer-executable instructions stored thereon, wherein the computer executable instructions are executable by a computer to perform the steps of:

concurrently executing software threads on parallel processors;

synchronizing the concurrently executing software threads via a synchronization barrier implemented via a synchronization barrier method having a property that no thread of the concurrently executing software threads can return from a call before all threads of the concurrently executing software threads have entered it; and

providing a variable that is to be changed within the synchronization barrier method, and read to determine when software threads should be released, wherein said variable is a local sense variable that is strictly local to the synchronization barrier method and neither a global variable nor a processor private variable, and wherein said variable is known within a block of code associated with the synchronization barrier method, but inaccessible to code outside the block.

11. The computer readable storage medium of claim 10 wherein the value of the variable is not stored outside of the synchronization barrier method.

12. The computer readable storage medium of claim 10 wherein the value of the variable is not stored across calls to the synchronization barrier method.

13. A computer readable storage medium having computer-executable instructions stored thereon, wherein the computer executable instructions are executable by a computer for performing the steps of:

concurrently executing software threads on parallel processors;

synchronizing the concurrently executing software threads via a synchronization barrier implemented via a synchronization barrier method having a property that no thread of the concurrently executing software threads can return from a call before all threads of the concurrently executing software threads have entered it;

ensuring a last operation each thread performs before returning from the synchronization barrier method is a write operation on a count variable within said synchronization barrier method which indicates a number of threads that have left the synchronization barrier; and

reclaiming the synchronization barrier when said count variable indicates that all threads have left the synchronization barrier, wherein the count variable is known within a block of code associated with the synchronization barrier method, but inaccessible to code outside the block.

14. The computer readable storage medium of claim 13 wherein said count variable serves a dual role of storing a total number of threads that have arrived at the synchronization barrier and counting the number of threads which have left the synchronization barrier.

15. The computer readable storage medium of claim 13, further comprising initializing the count variable by setting a field to be a predetermined value by a last thread to arrive at the barrier before releasing other threads from the barrier;

and wherein a thread performs a write operation on said count variable by incrementing a count value in the field before that thread returns.

16. The computer readable storage medium of claim 13 having computer-executable instructions stored thereon, wherein the computer executable instructions are executable by a computer to further perform the steps of:

using an indication of whether a thread is blocking to determine whether a thread is blocking;

resetting a previous event by a last thread to arrive at the barrier;

determining whether to reset a current event by the last thread to arrive at the barrier by examining the indication of whether a thread is blocking;

releasing spinning threads waiting for the last thread to arrive at the barrier; and

setting a current event by the last thread to arrive at the barrier to release threads that are blocking while waiting for the last thread to arrive if indicated to do so by the examination of the indication of whether a thread is blocking.

17. The computer readable storage medium of claim 16 wherein the act of using an indication of whether a thread is blocking to determine whether a thread is blocking comprises:

examining the indication of whether a thread is blocking by a thread deciding to block;

setting the indication of whether a thread is blocking by a thread deciding to block, if the indication of whether a thread is blocking is not set, in order to indicate that the last thread to arrive at the barrier must set the event;

examining a variable by the thread deciding to block that indicates whether the last thread has arrived at the barrier;

waiting by blocking until the event is set, if the variable examined indicated that the last thread has not arrived at the barrier.

18. A computer readable storage medium having computer-executable instructions stored thereon, wherein the computer executable instructions are executable by a computer to perform method the steps of:

concurrently executing software threads on parallel processors;

synchronizing the concurrently executing software threads via a synchronization barrier implemented via a synchronization barrier method having a property that no thread of the concurrently executing software threads can return from a call before all threads of the concurrently executing software threads have entered it;

providing a variable that is to be changed within the synchronization barrier method, and examined to determine when software threads should be released, wherein said variable is a local sense variable that is strictly local to the synchronization barrier method and neither a global variable nor a processor private variable;

providing an indication of whether a thread is blocking, which is used to determine whether a thread is blocking, wherein the indication of whether a thread is blocking is created only at a time when a thread decides to block;

when a last thread arrives at the synchronization barrier,

resetting a previous event

releasing spinning threads waiting for the last thread to arrive at the synchronization barrier by changing the local sense variable;

examining the indication of whether a thread is blocking to determine whether a thread is blocking; and

setting a current event to release threads that are blocking while waiting for the last thread to arrive, if indicated to do so by the examination of the indication of whether a thread is blocking.