Small barrier with local spinning

• US 8,060,881 B2
• Filed: 05/15/2007
• Issued: 11/15/2011
• Est. Priority Date: 05/15/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Clift, Neill M., Kishan, Arun U.
• Primary Examiner(s): Bullock, Jr.; Lewis
• Assistant Examiner(s): MILLS, PAUL V
• Application Number:
  US11/803,457
• Publication Number:
  US 20080288750A1
• Time in Patent Office: 1,645 Days
• Field of Search: None
• 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

Abstract

A barrier with local spinning. The barrier is described as a barrier object having a bit vector embedded as a pointer. If the vector bit is zero, the object functions as a counter; if the vector bit is one, the object operates as a pointer to a stack. The object includes the total number of threads required to rendezvous at the barrier to trigger release of the threads. The object points to a stack block list that describes each thread that has arrived at the barrier. Arriving at the barrier involves reading the top stack block, pushing onto the list a stack block for the thread that just arrived, decrementing the thread count, and spinning on corresponding local memory locations or timing out and blocking. When the last thread arrives at the barrier, the barrier is reset and all threads at the barrier are awakened for the start of the next process.

Claims

1. A computer-implemented system for thread management, comprising:

a processor; and

a memory comprising computer-readable instructions executable by the processor, the instructions including;

a barrier component for spinning threads at corresponding local memory locations when meeting a process barrier according to a barrier object by invoking a stack component as the threads arrive at the process barrier, wherein the barrier object is defined as a bit vector that functions as a counter that specifies a total number of threads required to rendezvous at the process barrier to trigger release of the threads when no threads are waiting at the barrier, and as a pointer to a stack block list when at least one thread is waiting at the process barrier; and

the stack component for creating and linking the stack blocks of the stack block list, wherein each stack block is associated with a respective one of the threads waiting at the barrier and is a tuple having at least a field related to the total number of threads.

2. The system of claim 1, wherein the local memory location is in cache memory accessible by one or more processes and the processor.

3. The system of claim 1, wherein the barrier component sleeps a thread local to the corresponding memory location based on timeout of the spin process.

4. The system of claim 1, wherein when the barrier object is a pointer a wait bit of the bit vector is set to one.

5. The system of claim 1, wherein when the barrier object is a counter a wait bit of the bit vector is reset to zero.

6. The system of claim 1, further comprising a timing component for maintaining a thread waiting at the process barrier in a spin mode based on arrival of another thread to the process barrier.

7. The system of claim 1, further comprising a timing component for waking a sleeping thread based on arrival of a last thread at the process barrier.

8. The system of claim 1, wherein the stack block tuple further includes fields associated with at least one of a remaining count of the threads yet to reach the barrier, a spin bit for awaking threads when the barrier reaches thread capacity, and a pointer for pointing to a next stack block.

9. A computer-implemented method of managing threads, comprising acts of:

processing threads received at a process barrier according to a barrier object by creating and linking blocks of a block list as the threads arrive at the process barrier, the barrier object defined as a bit vector that functions as a counter that specifies a total number of threads required to rendezvous at the process barrier to trigger release of the threads when no threads are waiting at the process barrier, and as a pointer to the block list when at least one thread is waiting at the process barrier, wherein each block of the block list corresponds to a respective thread that is waiting at the process barrier;

spinning a waiting thread at a local memory location specified in the corresponding stack block based on arrival of a next thread relative to the barrier; and

utilizing a processor to execute instructions stored in memory to perform at least one of the acts of processing or controlling.

10. The method of claim 9, wherein the block list comprises a stack block list that tracks each thread that arrives at the process barrier.

11. The method of claim 10, wherein linking blocks of the block list comprises pushing a stack local block associated with a thread onto a head of the list pointed to by the barrier when the thread arrives at the barrier.

12. The method of claim 10, wherein creating blocks of the block list comprises reading a top stack block when a thread arrives at the barrier.

13. The method of claim 10, wherein spinning the waiting thread further comprises spinning the waiting thread based on time associated with arrival of remaining threads to the process barrier.

14. The method of claim 9, wherein the waiting thread and the next thread are associated with processes of different microprocessors.

15. The method of claim 9, further comprising waking a sleeping thread based on arrival of a last thread at the process barrier.

16. The method of claim 9, further comprising maintaining a thread count in each block of the block list.

17. A computer-implemented system, comprising:

computer-implemented means for processing threads received at a process barrier according to a barrier object by creating and linking blocks of a block list as the threads arrive at the process barrier, the barrier object defined as a bit vector that functions as a counter that specifies a total number of threads required to rendezvous at the process barrier to trigger release of the threads when no threads are waiting at the process barrier, and as a pointer to the block list when at least one thread is waiting at the process barrier, wherein each block of the block list corresponds to a respective thread that is waiting at the process barrier;

computer-implemented means for spinning a waiting thread at a local memory location specified in the corresponding stack block based on arrival of a next thread relative to the barrier; and

a processor configured to execute computer-executable instructions associated with the computer-implemented means for processing and spinning.