Small barrier with local spinning

• US 20080288750A1
• Filed: 05/15/2007
• Published: 11/20/2008
• 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.
• Granted Patent: US 8,060,881 B2
• Time in Patent Office: Days
• US Class Current: 712/202
• 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 barrier component for processing threads locally at corresponding memory locations when meeting a process barrier; and

a stack component for processing stack blocks associated with the threads at the barrier.

2. The system of claim 1, wherein the barrier component spins on a thread local in a corresponding thread local memory location.

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

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

5. The system of claim 1, wherein the barrier component processes the threads according to barrier object represented as a bit vector of a pointer.

6. The system of claim 5, wherein the barrier object is a pointer when a value of the bit vector is set to one.

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

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

9. The system of claim 1, further comprising a timing component for waking a sleeping thread based on arrival of another thread to the process barrier.

10. The system of claim 1, wherein a stack block is a tuple that 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, a pointer for pointing to a next stack block, or an original thread count.

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

processing a thread received at a process barrier according to a barrier object, the barrier object defined as a bit vector of a pointer; and

controlling the thread at a local memory location based on state of a next thread relative to the barrier.

12. The method of claim 11, wherein the pointer points to a stack block list that tracks each thread that arrives at the process barrier.

13. The method of claim 12, further comprising pushing a stack local block associated with the thread onto a head of the list pointed to by the barrier when the thread arrives at the barrier.

14. The method of claim 12, further comprising reading a top stack block when the thread arrives at the barrier.

15. The method of claim 12, further comprising controlling the thread by locally spinning the thread on a value in the stack block before blocking.

16. The method of claim 15, further comprising controlling the thread by locally spinning the thread based on time associated with arrival of remaining threads to the process barrier.

17. The method of claim 11, further comprising spinning the thread locally based on arrival of remaining threads at a barrier associated with a process of a different microprocessor.

18. The method of claim 11, further comprising controlling the thread by waking the thread based on arrival of a last thread to the barrier.

19. The method of claim 11, further comprising maintaining a thread count in each stack block associated with a thread that arrives at the barrier.

20. A computer-implemented system, comprising:

computer-implemented means for processing a thread received at a process barrier according to a barrier object, the barrier object defined as a bit vector of a pointer; and

computer-implemented means for controlling the thread at a local memory location based on state of a next thread relative to the barrier.