Multi-thread execution method and parallel processor system

• US 7,082,601 B2
• Filed: 07/17/2002
• Issued: 07/25/2006
• Est. Priority Date: 07/18/2001
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Shibayama, Atsufumi, Matsushita, Satoshi, Ohsawa, Taku
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): DENG, ANNA CHEN
• Application Number:
  US10/196,613
• Publication Number:
  US 20030018684A1
• Time in Patent Office: 1,469 Days
• Field of Search: 717/149, 717/148, 717/153, 717/162, 717/143, 717/124, 717/126, 717/157, 712/228, 712/238, 712/15, 712/216, 711/118, 711/137, 711/206, 718/102, 718/103, 709/201, 714/38
• US Class Current: 717/149
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/4806 Task transfer initiation or dispatching

Abstract

In a parallel processor system for executing a plurality of threads in parallel to each other by a plurality of thread execution units, the respective thread execution units allow for forking of a slave thread from an individual thread execution unit into another arbitrary thread execution unit. The respective thread execution units are managed in three states, a free state where fork is possible, a busy state where a thread is being executed, and a term state where a thread being terminated and yet to be settled exists. At the time of forking of a new thread, when there exists no thread execution unit at the free state, a thread that the thread execution unit at the term state has is merged into its immediately succeeding slave thread to bring the thread execution unit in question to the free state and conduct forking of a new thread.

Claims

1. A multi-thread execution method in a parallel processor system, said parallel processor system including a plurality of thread execution units and a main memory, each thread execution unit of said plurality of thread execution units having a processor for executing threads, said parallel processor system allowing for execution of a plurality of threads of a program in parallel to each other by using the plurality of thread execution units, said multi-thread execution method comprising:

executing, by a first thread execution unit of said plurality of thread execution units, a first thread of said plurality of threads, said first thread including a fork instruction to fork a second thread of said plurality of threads;

forking by said first thread execution unit, said second thread to a second thread execution unit of said plurality of thread execution units when said first thread execution unit executes said fork instruction; and

merging said first thread of the first thread execution unit, which thread is terminated and yet to be settled, into said second thread of said second thread execution unit to allow for forking of a new thread of said plurality of threads to said first thread execution unit.

2. The multi-thread execution method as set forth in claim 1, wherein

a temporary buffer is provided for each individual thread execution unit to, at the merging of a thread that the thread execution unit at a term state has into an immediately succeeding slave thread, transfer a temporary execution result preserved in the temporary buffer of the thread execution unit at the term state to the temporary buffer of the thread execution unit which executes said slave thread.

3. The multi-thread execution method as set forth in claim 1, wherein

a cache memory serving also as a temporary buffer is provided for each individual thread execution unit to hold, for each cache line of said cache memory, version information which distinguishes data generated by a thread being terminated and yet to be settled and data generated by a thread newly generated after said merging, said cache memory of each thread execution unit making a selective response taking said version information and a thread sequential execution order into consideration in response to access from another thread execution unit.

4. The multi-thread execution method as set forth in claim 3, wherein

at the time of writing by a thread executed by each thread execution unit to the own cache memory, when the version information of the cache line as a target of write is older than the version of the own thread, queuing is conducted until the version of the cache line in question is appropriately changed according to termination of a master thread to coincide with the version of the own thread.

5. A multi-thread execution method in a parallel processor system, said parallel processor system including a plurality of thread execution units, each thread execution unit of said plurality of thread execution units having a processor for executing threads, said parallel processor system allowing for execution of a plurality of threads of a program in parallel to each other by using the plurality of thread execution units, said multi-thread execution method comprising;

managing each respective thread execution unit of the plurality of thread execution units as being in one of three states, said three states including (i) a free state where a fork to said thread execution unit is possible, (ii) a busy state where a thread of said plurality of threads is being executed by said thread execution unit, and (iii) a term state where a particular thread of said plurality of threads that is terminated and yet to be settled exists; and

merging, at a time of forking of a new thread of said plurality of threads when there exists no thread execution unit of said plurality of thread execution units at the free state, a specific thread of a specific thread execution unit at the term state into an immediately succeeding slave thread of the specific thread, said slave thread being executed on another thread execution unit of said plurality of thread execution units, whereby the specific thread execution unit is brought to the free state for permitting forking of the new thread to the specific thread execution unit.

6. The multi-thread execution method as set forth in claim 5, wherein

a temporary buffer is provided for each individual thread execution unit to, at the merging of the specific thread that the specific thread execution unit at the term state has into said immediately succeeding slave thread, transfer a temporary execution result preserved in the temporary buffer of the specific thread execution unit at the term state to the temporary buffer of a thread execution unit which executes said slave thread.

7. The multi-thread execution method as set forth in claim 5, wherein

a cache memory serving also as a temporary buffer is provided for each individual thread execution unit to hold, for each cache line of said cache memory, version information which distinguishes data generated by a thread being terminated and yet to be settled and data generated by a thread newly generated after said merging, said cache memory of each thread execution unit making a selective response taking said version information and a thread sequential execution order into consideration in response to access from another thread execution unit.

8. The multi-thread execution method as set forth in claim 7, wherein

at the time of writing by a thread executed by each thread execution unit to the own cache memory, when the version information of the cache line as a target of write is older than the version of the own thread, queuing is conducted until the version of the cache line in question is appropriately changed according to termination of a master thread to coincide with the version of the own thread.

9. A parallel processor system for executing a plurality of threads of a program in parallel to each other by a plurality of thread execution units, said parallel processor system comprising:

the plurality of thread execution units, each thread execution unit of said plurality of thread execution units having a processor for executing threads, a first thread execution unit of said plurality of thread execution units being configured to execute a first thread of said plurality of threads, said first thread including a fork instruction to fork a second thread of said plurality of threads, said first thread execution unit being configured to fork said second thread to a second thread execution unit of said plurality of thread execution units when said first thread execution unit executes said fork instruction;

a communication path for connecting the plurality of thread execution units with each other; and

means for merging said first thread of the first thread execution unit, when the first thread is terminated and yet to be settled, into said second thread of said second thread execution unit, so as to allow for forking of a new thread of said plurality of treads to said first thread execution unit.

10. The parallel processor system as set forth in claim 9, comprising

a temporary buffer provided for each individual thread execution unit for, at the merging of a thread that a thread execution unit at a term state has into an immediately succeeding slave thread, transferring a temporary execution result preserved in the temporary buffer of the thread execution unit at the term state to the temporary buffer of the thread execution unit which executes said slave thread.

11. The parallel processor system as set forth in claim 9, comprising

a cache memory serving also as a temporary buffer provided for each individual thread execution unit for holding, for each cache line of said cache memory, version information which distinguishes data generated by a thread being terminated and yet to be settled and data generated by a thread newly generated after said merging, said cache memory of each thread execution unit making a selective response taking said version information and a thread sequential execution order into consideration in response to access from another thread execution unit.

12. The parallel processor system as set forth in claim 11, wherein

the cache memory of each thread execution unit, at the time of writing by a thread executed by the own thread execution unit, when the version information of the cache line as a target of write is older than the version of said thread, waits for the version of the cache line in question to be appropriately changed according to termination of a master thread and to coincide with the version of said thread.

13. A parallel processor system for executing a plurality of threads of a program in parallel to each other by a plurality of thread execution units, comprising:

the plurality of thread execution units, each thread execution unit of said plurality of thread execution units having a processor for executing threads;

a communication path for connecting the plurality of thread execution units with each other;

means for managing each respective thread execution unit of said plurality of thread execution units as being in one of three states , said three states including (i) a free state where a fork to said thread execution unit is possible, (ii) a busy state where a thread of said plurality of threads is being executed, and (iii) a term state where a particular thread of said plurality of threads that is terminated and yet to be settled exists; and

means for, at a time of forking of a new thread of said plurality of threads when there exists no thread execution unit of said plurality of thread execution units at the free state, merging a specific thread of a specific thread execution unit at the term state into an immediately succeeding slave thread of the specific thread to bring the specific thread execution unit to the free state and to conduct forking of the new thread to the specific thread execution unit, said slave thread being executed on another thread execution unit of said plurality of thread execution units.

14. The parallel processor system as set forth in claim 13, comprising

a temporary buffer provided for each individual thread execution unit for, at the merging of a thread that a thread execution unit at the term state has into an immediately succeeding slave thread, transferring a temporary execution result preserved in the temporary buffer of the thread execution unit at the term state to the temporary buffer of the thread execution unit which executes said slave thread.

15. The parallel processor system as set forth in claim 13, comprising

a cache memory serving also as a temporary buffer which is provided for each individual thread execution unit for holding, for each cache line of said cache memory, version information which distinguishes data generated by a thread being terminated and yet to be settled and data generated by a thread newly generated after said merging, said cache memory of each thread execution unit making a selective response taking said version information and a thread sequential execution order into consideration in response to access from another thread execution unit.

16. The parallel processor system as set forth in claim 15, wherein

the cache memory of each thread execution unit, at the time of writing by a thread executed by the own thread execution unit, when the version information of the cache line as a target of write is older than the version of said thread, waits for the version of the cache line in question to be appropriately changed according to termination of a master thread and coincide with the version of said thread.