Data processing apparatus and method for performing lock-protected processing operations for multiple threads

• US 10,423,467 B2
• Filed: 05/19/2015
• Issued: 09/24/2019
• Est. Priority Date: 07/08/2014
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: Mansell, David Hennah, Glauert, Timothy Holroyd
• Primary Examiner(s): Kim, Sisley N
• Application Number:
  US15/322,882
• Publication Number:
  US 20170139757A1
• Time in Patent Office: 1,589 Days
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A data processing apparatus and method are provided for executing a plurality of threads. Processing circuitry performs processing operations required by the plurality of threads, the processing operations including a lock-protected processing operation with which a lock is associated, where the lock needs to be acquired before the processing circuitry performs the lock-protected processing operation. Baton maintenance circuitry is used to maintain a baton in association with the plurality of threads, the baton forming a proxy for the lock, and the baton maintenance circuitry being configured to allocate the baton between the threads. Via communication between the processing circuitry and the baton maintenance circuitry, once the lock has been acquired for one of the threads, the processing circuitry performs the lock-protected processing operation for multiple threads before the lock is released, with the baton maintenance circuitry identifying a current thread amongst the multiple threads for which the lock-protected processing operation is to be performed by allocating the baton to that current thread. The baton can hence be passed from one thread to the next, without needing to release and re-acquire the lock. This provides a significant performance improvement when performing lock-protected processing operations across multiple threads.

Claims

1. A data processing apparatus for executing a plurality of threads, the data processing apparatus being coupled to memory via an interconnect, and comprising:

processing circuitry configured to perform processing operations required by said plurality of threads, said processing operations including a lock-protected processing operation with which a lock is associated, the lock needing to be acquired in memory before the processing circuitry performs the lock-protected processing operation;

baton maintenance circuitry configured to maintain a baton in association with the plurality of threads, the baton forming a proxy for the lock, and the baton maintenance circuitry being configured to allocate the baton between the plurality of threads; and

a storage structure, separate from memory and associated with said plurality of threads, in which the baton maintenance circuitry is configured to maintain the baton;

the processing circuitry being configured to communicate with the baton maintenance circuitry so that, once the lock has been acquired in memory for one of said plurality of threads, the processing circuitry performs the lock-protected processing operation for multiple threads of said plurality of threads before the lock is released in memory, the baton maintenance circuitry being configured to identify a current thread amongst said multiple threads for which the lock-protected processing operation is to be performed by allocating the baton to that current thread;

wherein when the processing circuitry has performed the lock-protected processing operation for a thread, the processing circuitry is configured to issue a pass baton request to the baton maintenance circuitry, the baton maintenance circuitry being responsive to the pass baton request to determine whether there are any remaining threads amongst said multiple threads for which the lock-protected processing operation still needs to be performed, and if so, to allocate the baton to one of said remaining threads; and

wherein each thread comprises a sequence of instructions, and for a thread that requires the lock-protected processing operation to be performed, the thread includes a pass baton instruction which is executed by the processing circuitry once the lock-protected processing operation has been performed for that thread, and which causes the processing circuitry to issue the pass baton request to the baton maintenance circuitry.

2. A data processing apparatus as claimed in claim 1, wherein the baton maintenance circuitry is configured to allocate the baton to one thread at a time.

3. A data processing apparatus as claimed in claim 1, wherein, for a requiring thread that requires the lock-protected processing operation to be performed, the processing circuitry is configured to request the baton maintenance circuitry to allocate the baton to that requiring thread, the baton maintenance circuitry being configured, if the baton is not currently allocated to another thread, to allocate the baton to the requiring thread and to cause the processing circuitry to acquire the lock.

4. A data processing apparatus as claimed in claim 3, wherein when the processing circuitry requests the baton maintenance circuitry to allocate the baton to a requiring thread that requires the lock-protected processing operation to be performed, the baton maintenance circuitry is configured, if the baton is currently allocated to another thread, to maintain in association with the baton an indication that that requiring thread is awaiting the baton, and to cause the processing circuitry to stall execution of that requiring thread whilst awaiting allocation of the baton.

5. A data processing apparatus as claimed in claim 3, wherein each thread comprises a sequence of instructions, and for a requiring thread that requires the lock-protected processing operation to be performed, the requiring thread includes a get baton instruction which when executed by the processing circuitry causes the processing circuitry to request the baton maintenance circuitry to allocate the baton to that requiring thread.

6. A data processing apparatus as claimed in claim 5, wherein execution of the get baton instruction causes control data to be stored in a register to indicate whether the baton maintenance circuitry requires the processing circuitry to acquire the lock.

7. A data processing apparatus as claimed in claim 5, wherein the sequence of instructions includes lock acquiring code, and execution of the get baton instruction causes processing to branch past the lock acquiring code if the baton maintenance circuitry does not require the processing circuitry to acquire the lock.

8. A data processing apparatus as claimed in claim 1, wherein if the baton maintenance circuitry determines that there are no remaining threads amongst said multiple threads for which the lock-protected processing operation still needs to be performed, the baton maintenance circuitry is configured to de-allocate the baton and to cause the processing circuitry to release the lock.

9. A data processing apparatus as claimed in claim 1, wherein execution of the pass baton instruction causes control data to be stored in a register to indicate whether the baton maintenance circuitry requires the processing circuitry to release the lock.

10. A data processing apparatus as claimed in claim 1, wherein the sequence of instructions includes lock releasing code, and execution of the pass baton instruction causes processing to branch past the lock releasing code if the baton maintenance circuitry does not require the processing circuitry to release the lock.

11. A data processing apparatus as claimed in claim 1, wherein the apparatus is configured to acquire the lock via performance of an atomic operation.

12. A data processing apparatus as claimed in claim 1, wherein the storage structure comprises an entry for the baton, the entry comprising a lock identifier field identifying the lock for which the baton is forming a proxy, and a remaining threads field identifying any remaining threads amongst said multiple threads for which the lock-protected processing operation still needs to be performed.

13. A data processing apparatus as claimed in claim 12, wherein said entry further comprises an active thread field identifying the thread currently allocated the baton.

14. A data processing apparatus as claimed in claim 1, wherein said processing operations include multiple lock-protected processing operations, at least some of which have different locks associated therewith, and the baton maintenance circuitry is configured to maintain, in association with the plurality of threads, a plurality of batons, each baton being a proxy for one of the locks.

15. A data processing apparatus as claimed in claim 14, wherein the storage structure comprises a plurality of entries, each entry being associated with a different baton.

16. A data processing apparatus as claimed in claim 1, wherein the data processing apparatus comprises one or more baton domains, and for each baton domain the baton maintenance circuitry is configured to maintain a separate baton to form a proxy for the lock in that baton domain.

17. A data processing apparatus as claimed in claim 16, wherein said plurality of threads form a thread group, and the processing circuitry is further configured to perform processing operations required by threads of at least one further thread group, the threads of said at least one further thread group also requiring the lock-protected processing operation to be performed.

18. A data processing apparatus as claimed in claim 17, wherein one baton domain comprises multiple thread groups, such that the baton maintenance circuitry is configured to maintain the same baton for those multiple thread groups.

19. A data processing apparatus as claimed in claim 17, wherein each thread group is in a different baton domain, such that the baton maintenance circuitry is configured to maintain a separate baton in association with each thread group.

20. A data processing apparatus as claimed in claim 17, wherein for at least one thread group, the plurality of threads within that thread group are processed in parallel with a common program being executed for each thread of the thread group.

21. A data processing apparatus as claimed in claim 1, wherein the processing circuitry is configured to perform the processing operations required by said plurality of threads according to Single Instruction Multiple Thread (SIMT) processing.

24. A computer program product storing in a non-transitory form a computer program for controlling a computer to provide a virtual machine execution environment for program instructions corresponding to a data processing apparatus as claimed in claim 1.

22. A method of executing a plurality of threads within a data processing apparatus, each thread comprising a sequence of instructions, the method comprising:

performing processing operations required by said plurality of threads within processing circuitry of the data processing apparatus, said processing operations including a lock-protected processing operation with which a lock is associated, the lock needing to be acquired in memory before the processing circuitry performs the lock-protected processing operation;

employing baton maintenance circuitry to maintain a baton in a storage structure separate from memory and associated with said plurality of threads,

in association with the plurality of threads, the baton forming a proxy for the lock, and allocating the baton between the plurality of threads;

once the lock has been acquired in memory for one of said plurality of threads, performing the lock-protected processing operation for multiple threads of said plurality of threads before the lock is released in memory, and identifying to the processing circuitry a current thread amongst said multiple threads for which the lock-protected processing operation is to be performed by allocating the baton to that current thread; and

when the lock-protected processing operation has been performed for a thread, issuing a pass baton request to the baton maintenance circuitry, the baton maintenance circuitry being responsive to the pass baton request to determine whether there are any remaining threads amongst said multiple threads for which the lock-protected processing operation still needs to be performed, and if so, to allocate the baton to one of said remaining threads; and

for a thread that requires the lock-protected processing operation to be performed, the thread includes a pass baton instruction which is executed once the lock-protected processing operation has been performed for that thread, and which causes the pass baton request to be issued to the baton maintenance circuitry.

23. A data processing apparatus for executing a plurality of threads, comprising:

means for performing processing operations required by said plurality of threads, said processing operations including a lock-protected processing operation with which a lock is associated, the lock needing to be acquired in memory before the processing means performs the lock-protected processing operation;

means for maintaining a baton in association with the plurality of threads, the baton forming a proxy for the lock, and the means for maintaining a baton further for allocating the baton between the plurality of threads; and

a storage structure, separate from memory and associated with said plurality of threads, in which the means for maintaining a baton is configured to maintain the baton;

the means for performing processing operations including means for communicating with the means for maintaining a baton so that, once the lock has been acquired in memory for one of said plurality of threads, the means for performing processing operations performs the lock-protected processing operation for multiple threads of said plurality of threads before the lock is released in memory, the means for maintaining a baton including means for identifying a current thread amongst said multiple threads for which the lock-protected processing operation is to be performed by allocating the baton to that current thread;

wherein when the means for performing processing operations has performed the lock-protected processing operation for a thread, the means for performing processing operations is configured to issue a pass baton request to the baton maintenance circuitry, the means for maintaining a baton being responsive to the pass baton request to determine whether there are any remaining threads amongst said multiple threads for which the lock-protected processing operation still needs to be performed, and if so, to allocate the baton to one of said remaining threads; and

wherein each thread comprises a sequence of instructions, and for a thread that requires the lock-protected processing operation to be performed, the thread includes a pass baton instruction which is executed by the means for performing processing operations once the lock-protected processing operation has been performed for that thread, and which causes the means for performing processing operations to issue the pass baton request to the means for maintaining a baton.