Lock sequencing

• US 20070022429A1
• Filed: 07/25/2005
• Published: 01/25/2007
• Est. Priority Date: 07/25/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Rosenbluth, Mark, Wolrich, Gilbert, Jain, Sanjeev
• Granted Patent: US 7,853,951 B2
• Time in Patent Office: Days
• US Class Current: 718/108
• 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.

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 3, wherein the circuitry further comprises circuitry to add to the queue of pending requests with requests in the sequence.

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

6. 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.

7. 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.

8. 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.

9. The processor of claim 1, wherein the circuitry comprises circuitry 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.

10. 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.

11. 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.

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

13. 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.

14. The processor of claim 13,

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.

15. A computer program, the program including instructions for at least one thread to be executed by at least one of multiple multi-threaded programmable units integrated within a single die, the instructions to cause the at least one thread to:

issue a request for a place in a sequence of lock grants;

receiving a reply to the request identifying a sequence number;

issue a request for the lock identifying the sequence number; and

receive a lock grant in accordance with the sequence.

16. The computer program of claim 15, wherein the instructions comprise instructions to make the thread stall execution until receiving the lock grant.

17. The computer program of claim 15, wherein the request for the place in the sequence comprises identification of one of multiple sequence domains.

18. The computer program of claim 17, further comprising instructions to cause the threads to issue a request for a lock without previously requesting a place in a sequence for the lock request.

21. The method of claim 18, further comprising maintaining a queue of pending requests for a lock.

22. The method of claim 21, further comprising adding to the queue of pending requests with requests in the sequence.

19. A method, comprising:

at circuitry coupled to multiple multi-threaded programmable units integrated on a single die, reordering and granting locks for lock requests received from threads of the multiple programmable units, the reordering based on an order in which threads requested insertion into a sequence of lock grants.

20. The method of claim 19, 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.

23. The method of claim 19, wherein the sequence comprises a sequence in one of multiple sequence domains.

24. The method of claim 19, 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.

25. 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.

26. The device of claim 25, 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.

27. The device of claim 25, wherein the sequence comprises a sequence in one of multiple sequence domains.

28. The device of claim 25, 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.