Lock sequencing to reorder and grant lock requests from multiple program threads

• US 7,853,951 B2
• Filed: 07/25/2005
• Issued: 12/14/2010
• Est. Priority Date: 07/25/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Rosenbluth, Mark, Wolrich, Gilbert, Jain, Sanjeev
• Primary Examiner(s): Do; Chat C
• Assistant Examiner(s): Tang; Kenneth
• Application Number:
  US11/190,112
• Publication Number:
  US 20070022429A1
• Time in Patent Office: 1,968 Days
• Field of Search: 718/104, 711/152, 707/8, 370/389
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

In general, in one aspect, the disclosure describes a processor that includes multiple multi-threaded programmable units integrated on a single die. The die also includes circuitry communicatively coupled to the programmable units that reorders and grants lock requests received from the threads based on an order in which the threads requested insertion into a sequence of lock grants.

Claims

1. A processor, comprising:

multiple programmable units integrated on a single die, each of the multiple programmable units to provide multiple program threads of execution; and

circuitry integrated on the die, communicatively coupled to the multiple programmable units, the circuitry to reorder and grant lock requests received from the threads provided by the multiple programmable units based on an order in which the threads requested insertion into a sequence of lock grants, said circuitry configured to;

(1) (a) receive a request for a sequence number for a specified lock from a one of the multiple programmable units, the request specifying the lock and one of multiple sequence domains;

(b) in response to the received request for the sequence number;

determine a sequence number for the request within the specified sequence number domain; and

send a response identifying the determined sequence number within the specified sequence number domain to the one of the multiple programmable units;

(2) (a) receive a lock request specifying a sequence number and a sequence number domain;

(b) in response to the received lock request;

determine if the sequence number is the next sequence number in the sequence;

if the sequence number is not the next sequence number in the sequence, store an identifier of the received lock request in a memory based on the specified sequence number and sequence number domain;

if the sequence number is the next sequence number in the sequence, add the lock request to a queue of pending lock requests if the lock is currently locked and granting the lock request if the lock is currently unlocked;

(3) (a) receive a lock request not specifying a sequence number;

(b) in response to the lock request not specifying a sequence number;

determine if the lock is currently granted to another thread;

if the lock is currently granted to another thread, adding a queue entry for the received lock request;

if the lock is not currently granted to another thread, granting the lock;

(4) (a) receive an unlock request;

(b) in response to the unlock request;

determining if a queue associated with the lock has a pending lock request; and

if it is determined the queue associated with the lock has a pending lock request, granting the lock to the pending lock request.

2. The processor of claim 1, wherein the circuitry comprises circuitry to allocate sequence numbers to, respective, threads of the multiple programmable units, the sequence numbers representing a place in the sequence of lock grants.

3. The processor of claim 1, wherein the circuitry further comprises circuitry to maintain a queue of pending requests for a lock.

4. The processor of claim 1, wherein the sequence comprises a sequence in one of multiple sequence domains.

5. The processor of claim 1, wherein the circuitry to grant the lock comprises circuitry to send a signal to a one of the multiple programmable units associated with the thread making the granted request.

6. The processor of claim 1, wherein the circuitry further comprises circuitry to issue a memory read operation for data associated with a lock and to cause the data to be delivered to the programmable unit receiving a lock grant.

7. The processor of claim 1, wherein each of the multiple programmable units comprises a programmable unit having an instruction set that enables a thread to be stalled until a lock grant is received.

8. The processor of claim 1, wherein the multiple programmable units each have an instruction set that includes one or more instructions to:

request a sequence number;

request a lock specifying the sequence number;

request a lock without specifying a sequence number; and

request a lock and delivery of data associated with the lock.

9. The processor of claim 1, further comprising memory to store data associated with different sequence domains, the data including a reference to a next sequence number awaiting servicing.

10. The processor of claim 9, wherein the data associated with different sequence domains comprises identification of a received lock request having a most terminal order in the sequence.

11. The processor of claim 1, wherein the circuitry comprises a content addressable memory, some of the entries in the content addressable memory specify a sequence number domain and identify a lock request.

12. The processor of claim 11,

wherein the some of the entries in the content addressable memory are identified by a first flag value;

and

wherein other ones of the entries of the content addressable memory are identified by a second flag value and identify locks.

13. A method, comprising:

(1) (a) receiving a request for a sequence number for a specified lock from at least one programmable unit, the request specifying the lock and one of multiple sequence domains;

(b) in response to the received request for the sequence number;

determining a sequence number for the request within the specified sequence number domain; and

sending a response identifying the determined sequence number within the specified sequence number domain to the programmable unit;

(2) (a) receiving a lock request specifying a sequence number and a sequence number domain;

(b) in response to the received lock request;

determining if the sequence number is the next sequence number in the sequence;

if the sequence number is not the next sequence number in the sequence, storing an identifier of the received lock request in a memory based on the specified sequence number and sequence number domain;

if the sequence number is the next sequence number in the sequence, adding the lock request to a queue of pending lock requests if the lock is currently locked and granting the lock request if the lock is currently unlocked;

(3) (a) receiving a lock request not specifying a sequence number;

(b) in response to the lock request not specifying a sequence number;

determining if the lock is currently granted to another thread;

if the lock is currently granted to another thread, adding a queue entry for the received lock request;

if the lock is not currently granted to another thread, granting the lock;

(4) (a) receiving an unlock request;

(b) in response to the unlock request;

determining if a queue associated with the lock has a pending lock request; and

if it is determined the queue associated with the lock has a pending lock request, granting the lock to the pending lock request.

14. The method of claim 13, further comprising allocating sequence numbers to, respective, threads of the multiple programmable units, the sequence numbers representing a place in the sequence of lock grants.

15. The method of claim 13, further comprising maintaining a queue of pending requests for a lock.

16. The method of claim 13, wherein the sequence comprises a sequence in one of multiple sequence domains.

17. The method of claim 13, further comprising issuing a memory read operation for data associated with a lock and to cause the data to be delivered to the programmable unit receiving a lock grant.

18. A network device, comprising:

a switch fabric; and

multiple blades coupled to the switch fabric, at least one of the multiple blades including a processor having multiple multi-threaded programmable units integrated on a single die and circuitry, communicatively coupled to the multiple programmable units, the circuitry to reorder and grant received lock requests received from the multiple programmable units based on an order in which threads requested insertion into a sequence of lock grants, said circuitry configured to;

(1) (a) receive a request for a sequence number for a specified lock from a one of the multiple programmable units, the request specifying the lock and one of multiple sequence domains;

(b) in response to the received request for the sequence number;

determine a sequence number for the request within the specified sequence number domain; and

send a response identifying the determined sequence number within the specified sequence number domain to the one of the multiple programmable units;

(2) (a) receive a lock request specifying a sequence number and a sequence number domain;

(b) in response to the received lock request;

determine if the sequence number is the next sequence number in the sequence;

if the sequence number is not the next sequence number in the sequence, store an identifier of the received lock request in a memory based on the specified sequence number and sequence number domain;

if the sequence number is the next sequence number in the sequence, add the lock request to a queue of pending lock requests if the lock is currently locked and granting the lock request if the lock is currently unlocked;

(3) (a) receive a lock request not specifying a sequence number;

(b) in response to the lock request not specifying a sequence number;

determine if the lock is currently granted to another thread;

if the lock is currently granted to another thread, adding a queue entry for the received lock request;

if the lock is not currently granted to another thread, granting the lock;

(4) (a) receive an unlock request;

(b) in response to the unlock request;

determining if a queue associated with the lock has a pending lock request; and

if it is determined the queue associated with the lock has a pending lock request, granting the lock to the pending lock request.

19. The device of claim 18, wherein the circuitry comprises circuitry to allocate sequence numbers to, respective, threads of the multiple programmable units, the sequence numbers representing a place in the sequence of lock grants.

20. The device of claim 18, wherein the sequence comprises a sequence in one of multiple sequence domains.

21. The device of claim 18, wherein the circuitry further comprises circuitry to issue a memory read operation for data associated with a lock and to cause the data to be delivered to the programmable unit receiving a lock grant.