SYSTEM AND METHOD FOR THREAD HANDLING IN MULTITHREADED PARALLEL COMPUTING OF NESTED THREADS

• US 20090125907A1
• Filed: 01/19/2007
• Published: 05/14/2009
• Est. Priority Date: 01/19/2006
• Status: Active Grant

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Vishkin, Uzi Yehoshua, Wen, Xingzhi
• Granted Patent: US 8,209,690 B2
• Time in Patent Office: Days
• US Class Current: 718/101
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

An Explicit Multi-Threading (XMT) system and method is provided for processing multiple spawned threads associated with SPAWN-type commands of an XMT program. The method includes executing a plurality of child threads by a plurality of TCUs including a first TCU executing a child thread which is allocated to it; completing execution of the child thread by the first TCU; announcing that the first TCU is available to execute another child thread; executing by a second TCU a parent child thread that includes a nested spawn-type command for spawning additional child threads of the plurality of child threads, wherein the parent child thread is related in a parent-child relationship to the child threads that are spawned in conjunction with the nested spawn-type command; assigning a thread ID (TID) to each child thread, wherein the TID is unique with respect to the other TIDs; and allocating a new child thread to the first TCU.

Claims

1. An Explicit Multi-Threading (XMT) system for processing multiple spawned threads associated with an XMT program, the XMT system comprising:

at least one processor;

a plurality of thread control units (TCUs) each having an associated ID (TCU-ID) and including at least one series of programmable instructions executable by the at least one processor for executing a plurality of child threads, wherein each TCU executes a child thread which is allocated to the TCU, and upon completion of execution of the child thread the TCU is available to execute another child thread, and at least one TCU executes a parent child thread of the plurality of child threads that includes a nested spawn-type command for spawning additional child threads of the plurality of child threads, wherein the parent child thread is related in a parent-child relationship to the child threads that are spawned in conjunction with the nested spawn-type command; and

a function module for assigning a thread ID (TID) to each child thread which is unique with respect to the other TIDs, and allocating the plurality of child threads to respective TCUs of the plurality of TCUs.

2. The XMT system according to claim 1, wherein:

a parent thread and a child thread are related to one another, and otherwise the child threads are not related to one another; and

the plurality of TCUs and the function module interact for providing synchronization of execution of related threads with respect to one another, and for providing substantially asynchronous execution of unrelated threads with respect to one another.

3. The XMT system according to claim 2, wherein for a pair of related threads including a child thread and a parent thread, a first TCU executing the child thread reads initialization data for execution of the child thread from a location designated for storing the initialization data of the child thread, and a second TCU executing the parent thread writes the initialization data into the designated location.

4. The XMT system according to claim 3, wherein the designated location is referenced using the TID of the child thread for which the location is designated for storing its initialization data.

5. The XMT system according to claim 4, wherein when the first TCU is available to execute a child thread it requests and receives from the function module a TID for a child thread to execute, and the synchronization includes:

the first TCU accessing the designated location suing the TID received from the function module, and waiting for the initialization data to be successfully written into the designated location.

6. The XMT system according to claim 1, wherein:

a first TCU executing a nested spawn-type command requests from the function module a TID for each child thread being spawned, and each TID received is designated as a valid TID;

a second TCU that is available to execute a child thread requests a TID from the function module; and

the synchronization includes the second TCU waiting for the TED that it requested to become valid before executing the child thread associated with the TID.

7. The XMT system according to claim 2, wherein:

executing a nested spawn-type command by a parent thread includes requesting from the function module a TID for each child thread being spawned; and

the function module further comprises at least one global register including GR-HIGH and GR-LOW, wherein GR-LOW is incremented each time that a TCU of the plurality of TCUs completes executing a child thread; and

OR-HIGH is incremented each time that a TCU executing a parent thread requests a TED for a child thread being spawned.

8. The XMT system according to claim 7, the function module further comprising a prefix-sum functional unit (PSFU), wherein when a first TCU is available to execute a child thread it requests that the PSFU perform a prefix-sum operation using a base equal to GR-LOW and an increment of 1 to provide a TID, upon which the PSFU provides a TID having the value of GR-LOW to the first TCU and increments GR-LOW.

9. The XMT system according to claim 8, wherein execution of a nested SPAWN-type command by a second TCU executing a parent thread includes requesting that the PSFU perform a prefix-sum operation using a base equal to GR-HIGH and an increment of 1 to provide a TID for each child thread being spawned, for each prefix-sum operation the PSFU provides to the second TCU a unique TID for a respective child thread being spawned, having the initial value of GR-HIGH at the time the prefix-sum operation and increments GR-HIGH.

10. The XMT system according to claim 9, wherein allocating the child thread to the first TCU includes the function module providing the TID associated with the child thread to each of the first and second TCUs.

11. The XMT system according to claim 10, wherein the synchronization is provided when the TID is provided to the first TCU before the second TCU and vice versa.

12. The XMT system according to claim 7, wherein the function module provides a transmission announcing an updated value each time that GR-HIGH is updated and the plurality of TCUs store the updated GR-HIGH.

13. The XMT system according to claim 12, wherein when a TCU is available to execute a child thread it requests and receives from the function module a TID for a child thread to execute, the TCU compares the TID with GR-HIGH, and if the TID is greater than GR-HIGH the TCU enters an idle state in which it waits until the function module announces a value of GR-HIGH which is greater than the TID upon which the TCU executes child tread that is associated with the TID.

14. The XMT system according to claim 8, wherein the nested SPAWN-type command is a k-SPAWN command for spawning k child threads, wherein the PSFU performs a prefix-sum operation for each of the k-child threads and allocates each of the k-child threads to a TCU.

15. The XMT system according to claim 9, further comprising a task array including an array of elements, each element storing initialization data for a child thread of the plurality of child threads;

wherein;

before the second TCU requests the PSFU to perform each of the respective prefix-sum operations for providing the TIDs for the respective child thread being spawned, the second TCU requests the PSFU to perform a preliminary prefix-sum operation using a place holder base and an increment of one, to provide a value for a place holder index;

the second TCU stores initialization data for the respective child thread in the element of the task array indexed by the place holder index.

16. The XMT system according to claim 15, further comprising a relay array including an array of elements, each element storing a place holder index that corresponds to the child thread associated with the TID that indexes the element, wherein the elements of the relay array are initialized to an invalid value, and wherein for each respective child thread being spawned after the second TCU is provided by the PSFU with the TID corresponding to the respective child thread:

the second TCU stores the placeholder index for the respective child thread in the element of the relay array indexed by the TID associated with the respective child thread; and

the first TCU determines if the value stored in the element of the TCU indexed by the TID that the PSFU provided to the first TCU is valid;

if the value is determined to be invalid the first TCU spin-waits until it becomes valid;

when the value is determined to be valid the first TCU accesses initialization data stored in the element of the task array indexed by the valid value; and

the first TCU executes the child thread associated with the TID that the PSFU provided to it using the accessed initialization data.

17. The XMT system according to claim 16, wherein the second TCU confirms that the storing of the initialization data for the respective child thread is completed.

18. The XMT system according to claim 9, further comprising:

a task array including an array of elements, each element storing initialization data for a child thread of the plurality of child threads; and

a special location array including an array of elements indexed by TID, each respective element having a TCU-ID field for storing the TCU-ID of a TCU that attempts to access data stored by the element, and valid field for storing an indicator value that indicates when valid initialization data for the child thread associated with the TID indexing the element is ready to be accessed, wherein the indicator value for each element is initialized with a value indicating that the initialization data is invalid;

wherein after the second TCU is provided with the TIDs for the child threads being spawned;

the second TCU stores initialization data associated with each respective child thread being spawned in the element of the task array indexed by the TID associated with the child thread being spawned;

the second TCU stores a value indicating that the initialization data is ready to be accessed in the valid field of each of the respective elements of the special location array indexed by the respective TIDs of each of the child threads being spawned; and

the TCU having the TCU-ID stored in the TCU-ID field is notified that the initialization data is ready to be accessed.

19. The XMT system according to claim 18, wherein:

if the value is determined to indicate that the initialization data is not ready, the first TCU waits to be notified that the initialization data is ready to be accessed and stores its TCU-ID in the TCU-ID field indexed by the TID provided to the first TCU by the PSFU;

when the value stored in the valid field of the element of the special location array indexed by the TID provided to it by the PSFU indicates that the initialization data is ready to be accessed the first TCU is notified; and

once the first TCU-ID is notified that the initialization data is ready the first TCU accesses the initialization data stored in the element of the task array that is indexed by the TI) provided to the first TCU by the PSFU and proceeds to execute the thread having the TID provided to the first TCU by the PSFU.

20. The XMT system according to claim 18, wherein the second TCU confirms that the storing of the initialization data for the respective child thread is completed before storing the value in the valid field of the respective elements of the special location array.

21. A method for processing multiple spawned threads associated with SPAWN-type commands of an Explicit Multi-Threading (XMT) program, the method comprising the steps of:

executing a plurality of child threads by a plurality of TCUs including a first TCU of the plurality of TCUs executing a child thread which is allocated to it;

completing execution of the child thread by the first TCU;

announcing that the first TCU is available to execute another child thread;

executing by a second TCU a parent child thread of the plurality of child threads that includes a nested spawn-type command for spawning additional child threads of the plurality of child threads, wherein the parent child thread is related in a parent-child relationship to the child threads that are spawned in conjunction with the nested spawn-type command;

assigning a thread ID (TID) to each child thread of the plurality of child threads which is unique with respect to the other TIDs; and

allocating a new child thread to the first TCU.

22. The method according to claim 21 further comprising the steps of:

reading by the first TCU initialization data for execution of the new child thread from a location designated for storing the initialization data of the child thread; and

writing by the second TCU the initialization data into the designated location.

23. The method according to claim 22, wherein the designated location is referenced using the TID of the child thread for which the location is designated for storing its initialization data;

and the method further comprising;

requesting and receiving by the first TCU a TID for a child thread to execute when the first TCU is available to execute a child thread; and

wherein reading the initialization data by the first TCU includes accessing the designated location using the TID received from the function module.

24. The method according to claim 22, further comprising the step of waiting by the first TCU for the initialization data to be successfully written into the designated location before reading the initialization data.

25. The method according to claim 23, further comprising the steps of:

designating the TIDs associated with the respective child threads being spawned to be valid as they are assigned;

waiting by the first TCU for the TID that it requested and received to become valid before executing the child thread associated with the TID.

26. The method according to claim 23, wherein executing the nested spawn-type command includes requesting a TID for each child thread being spawned, wherein the method further comprises:

providing at least one global register including GR-HIGH and GR-LOW;

incrementing GR-LOW each time that a TCU of the plurality of TCUs completes executing a child thread;

incrementing GR-HIGH each time that a TCU executing a parent thread requests a TID for a child thread being spawned; and

announcing updated values for OR-HIGH to the plurality of TCUs.

27. The method according to claim 26, further comprising the steps of:

comparing the difference between OR-HIGH and GR-LOW to a predetermined first threshold; and

entering a mode to suspend spawning of child threads when the difference exceeds the first threshold until the difference drops below a second predetermined threshold, upon which spawning of child threads is resumed.

28. The method according to claim 26, the method further comprising:

comparing by the first TCU the TID requested and received with the updated version of GR-HIGH;

entering an idle state by the first TCU if the TID is greater than GR-HIGH;

exiting the idle state when the value of GR-HIGH is updated to be greater than the TID; and

executing the child thread that is associated with the requested and received TID by the first TCU when the first TCU exits the idle state.

29. A method for processing multiple spawned threads associated with SPAWN-type commands of an Explicit Multi-Threading (XMT) program, the method comprising the steps of:

executing a plurality of child threads by a plurality of TCUs including a first TCU of the plurality of TCUs executing a child thread which is allocated to it;

completing execution of the child thread by the first TCU;

announcing that the first TCU is available to execute another child thread;

executing by a second TCU a parent child thread of the plurality of child threads that includes a nested spawn-type command for spawning additional child threads of the plurality of child threads, wherein the parent child thread is related in a parent-child relationship to the child threads that are spawned in conjunction with the nested spawn-type command;

assigning a thread ID (TID) to each child thread of the plurality of child threads which is unique with respect to the other TIDs;

allocating a new child thread to the first TCU;

writing by the second TCU the initialization data into the designated location;

reading by the first TCU initialization data for execution of the new child thread from a location designated for storing the initialization data of the new child thread; and

waiting by the first TCU for the initialization data to be successfully written into the designated location before reading the initialization data if the initialization data is not yet written into the designated location;

wherein the designated location is referenced using the TID of the new child thread.

30. The method according to claim 29, further comprising the steps of:

designating the TIDs associated with the respective child threads being spawned to be valid as they are assigned; and

waiting by the first TCU for the TID that it requested and received to become valid before reading the initialization data.

31. The method according to claim 30, further comprising the steps of:

providing a task array including an array of elements, each element provided for storing initialization data for a child thread of the plurality of child threads;

providing a special location array including an array of elements indexed by TID, each respective element having a TCU-ID field for storing the TCU-ID of a TCU that attempts to access data stored by the element, and valid field for storing an indicator value that indicates when valid initialization data for the child thread associated with the TID indexing the element is ready to be accessed, wherein the indicator value for each element is initialized with a value indicating that the initialization data is invalid;

after the second TCU is provided with the TIDs for the child threads being spawned;

storing initialization data associated with each respective child thread being spawned in the element of the task array indexed by the TID associated with the child thread being spawned;

storing a value indicating that the initialization data is ready to be accessed in the valid field of each of the respective elements of the special location array indexed by the respective TIDs of each of the child threads being spawned; and

notifying the TCU having the TCU-ID stored in the TCU-ID field that the initialization data is ready to be accessed.

32. The method according to claim 31, further comprising the steps of:

waiting by the first TCU, if the value is determined to indicate that the initialization data is not ready, to be notified that the initialization data is ready to be accessed;

storing the first TCU'"'"'s TCU-ID in the TCU-ID field indexed by the TID provided to the first TCU;

accessing the initialization data stored in the element of the task array that is indexed by the TID provided to the first TCU; and

executing the thread having the TID provided to the first TCU.