Spawn-join instruction set architecture for providing explicit multithreading

• US 6,463,527 B1
• Filed: 09/07/1999
• Issued: 10/08/2002
• Est. Priority Date: 03/21/1997
• Status: Expired due to Fees

• Current Assignee: Uzi Y. Vishkin
• Original Assignee: Uzi Y. Vishkin
• Inventors: Vishkin, Uzi Y.
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US09/380,571
• Time in Patent Office: 1,127 Days
• Field of Search: 709/100, 709/106, 709/103, 709/108, 709/223, 709/315, 709/316, 709/107, 707/3, 707/533, 712/22, 712/23, 712/30, 712/203, 712/216, 712/200, 712/215, 712/24, 712/25, 712/204, 712/205, 712/206, 712/207, 712/217, 712/223, 712/226, 712/235, 712/245, 712/208, 712/209, 712/213, 712/210, 712/211, 712/212, 712/218, 712/219, 712/228, 712/227, 712/237, 712/238, 712/21, 712/42, 712/41, 712/242, 712/243, 717/150
• US Class Current: 712/245
• 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/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

The invention presents a unique computational paradigm that provides the tools to take advantage of the parallelism inherent in parallel algorithms to the full spectrum from algorithms through architecture to implementation. The invention provides a new processing architecture that extends the standard instruction set of the conventional uniprocessor architecture. The architecture used to implement this new computational paradigm includes a thread control unit (34), a spawn control unit (30), and an enabled instruction memory (50). The architecture initiates multiple threads and executes them in parallel. Control of the threads is provided such that the threads may be suspended or allowed to execute each at its own pace.

Claims

1. A processor comprising:

first processing element that controls execution of computer processing instruction groups;

second processing elements, coupled to said first processing element, each of said second processing elements respectively executing selected ones of said instruction groups in response to said first processing element, said second processing elements independently executing the selected instruction groups in parallel relative to other second processing elements; and

a third processing element, coupled to said second processing elements, having a plurality of storage sections for respectively storing ones of said instruction groups respectively executed by said second processing elements, wherein each said second processing elements executes individual instructions in stored instruction group that are enabled for execution in corresponding sections of said third processing element.

2. The processor recited in claim 1, further comprising a fourth processing element for handling competing requests for ones of said instruction groups.

3. The processor recited in claim 2, wherein said instruction groups are computer instruction threads, and wherein said first processing element is a spawn control unit that generates a spawn command for execution of the computer instruction threads by said second processing elements.

4. The processor recited in claim 3, wherein said second processing elements are thread control units that execute selected ones of the computer instruction threads in response to the spawn command from said spawn control unit, wherein each of said thread control units execute individual computer instruction threads independent of any order of execution relative to other thread control units;

the processor further comprising a bus providing a transmission path for signals from said spawn control unit to said thread control units.

5. The processor recited in claim 4, wherein each of the computer program instruction groups includes a plurality of assembly language instructions, and wherein each of said thread control units includes a superscalar processing section that executes the assembly language instructions within its own thread.

6. The processor recited in claim 5, wherein said third processing element is an enabled instruction memory storing said computer program instruction groups in one of a plurality of memory portions.

7. The processor recited in claim 6, wherein said enabled instruction memory is organized in a hierarchical arrangement, at least one of said computer program instruction groups includes a spawn command to permit nested threads, and wherein said enabled instruction memory moves the computer program instruction group to a memory portion lower in the hierarchical arrangement.

8. The processor recited in claim 3, wherein said fourth processing element is a prefix-sum circuit calculating prefix sums based on outputs from said second processing elements.

9. The processor recited in claim 8, wherein said second processing elements derive thread identification numbers from outputs of said prefix-sum circuit.

10. A computer system for processing a parallel algorithm having a parallel code block with n virtual threads, the computer system comprising:

a spawn control unit initiating execution of k physical threads by generating a thread control unit enable signal in a form of a spawn command, assigning each thread a thread identification number;

a plurality of thread control units, wherein each thread control unit receives the spawn command from said spawn control unit, and in response to the spawn command, retrieves a series of spawn-join instructions from a global instruction memory, each series of spawn-join instructions including a join command signaling a termination of a thread upon execution by a thread control unit, wherein said thread control units execute their respective series of spawn-join instructions in concurrently, and wherein each thread control unit executes its respective series of spawn-join instructions independent of any order of execution of spawn-join instructions by other thread control units;

a prefix-sum unit, coupled to each of said thread control units, calculating a plurality of prefix sums based on outputs from said thread control units, and wherein thread identification numbers are assigned to said thread control units based on calculations of the prefix sums;

wherein each of said thread control units sends an output to said prefix-sum unit in response to execution of a join command, and if the number of k physical threads is less than the number of n virtual threads, said spawn control unit issues a thread control unit enable signal in a form of a spawn-recur command when at least one of said thread control units has executed a join command, wherein each thread control unit receiving said spawn-recur command commences recurrent execution of its respective series of spawn-join instructions with a new thread identification number from said prefix-sum unit.

11. The computer system of claim 10, further comprising:

an enabled instruction memory, coupled to said thread control units, said enabled instruction memory storing, for each thread control unit, in a corresponding section of memory, its respective series of spawn-join instructions in response to an enable signal from said spawn control unit;

wherein each thread control unit executes the series of spawn-join instructions stored in its corresponding section, and wherein, when a thread control unit executes a nested spawn instruction in its series of spawn-join instructions, said enabled instruction memory moves the stored series of spawn-join instructions containing the nested spawn instruction and stores in its place in said enabled instruction memory a new series of spawn-join instructions.

12. The computer system of claim 11, further comprising a plurality of local and global registers used by said thread control units during execution of the spawn-join instructions.

13. In a computer system, the method of processing a parallel algorithm having n virtual threads, the method comprising the steps of:

initiating execution of k physical threads by generating a thread enable signal in a form of a spawn command and assigning each thread a thread identification number;

receiving the spawn command, and in response to the spawn command, retrieving a series of spawn-join instructions, each series of spawn-join instructions including a join command signaling a termination of a thread upon execution;

executing respective series of spawn-join instructions in parallel and independent of any order of execution of spawn-join instructions;

calculating a plurality of prefix sums based on terminating ones of the k physical threads, and assigning thread identification numbers based on calculations of the prefix sums; and

wherein, if the number of k physical threads is less than the number of n virtual threads, issuing a thread enable signal in a form of a spawn-recur command when at least one join command has been executed, wherein in response to said spawn-recur command, commencing recurrent execution of a series of spawn-join instructions with a new thread identification number output from said prefix-sum step.

14. The method of claim 13, further comprising the steps of:

storing in an enabled instruction memory in corresponding sections of memory respective series of spawn-join instructions in response to an enable signal;

wherein said executing step further comprises executing the series of spawn-join instructions stored in its corresponding section, and wherein, when a nested spawn instruction is executed in a series of spawn-join instructions, moving the stored series of spawn-join instructions containing the nested spawn instruction and storing in its place in the enabled instruction memory a nested series of spawn-join instructions.