Collision handling apparatus and method

• US 20050055490A1
• Filed: 12/12/2001
• Published: 03/10/2005
• Est. Priority Date: 12/12/2001
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Dahlstrom, Marcus, Holmberg, Per, Widell, Anders
• Granted Patent: US 8,028,132 B2
• Time in Patent Office: Days
• US Class Current: 711/1
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

The present invention relates to mechanisms for handling and detecting collisions between threads (5, 6, 7) that execute computer program instructions out of program order. According to an embodiment of the present invention each of a plurality of threads (5, 6, 7) are associated with a respective data structure (9, 10, 11) comprising a number of bits (12) that correspond to memory elements (m₀, m₁, m₂, m_n) of a shared memory (4). When a thread accesses a memory element in the shared memory, it sets a bit in its associated data structure, which bit corresponds to the accessed memory element. This indicates that the memory element has been accessed by the thread. Collision detection may be carried out after the thread has finished executing by means of comparing the data structure of the thread with the data structures of other threads on which the thread may depend.

Claims

1. An apparatus that supports execution of computer program instructions speculatively out of program order comprising:

a plurality of threads for executing computer program instructions, and a shared memory, which comprises a number of shared memory elements accessible to the plurality of threads;

wherein each of the threads is associated with a respective data structure for collision detection between the plurality of threads, said data structure being arranged to store information indicating which of said number of shared memory elements the associated thread has accessed, and wherein each of the threads includes means for accessing a selected shared memory element in the shared memory, and means for storing information in the associated data structure of the thread, said information indicating the thread'"'"'s access to the selected shared memory element.

2. The apparatus according to claim 1, wherein the data structures are one of the following types of structures:

an unsorted list, a sorted list, a tree and a table.

3. The apparatus according to claim 1, wherein each data structure comprises a number of bits that correspond to the shared memory elements of the shared memory, and wherein the means for storing information include means for setting at least one chosen bit, corresponding to the selected shared memory element.

4. The apparatus according to claim 3, wherein the data structure comprises a load vector and a store vector, wherein the means for setting at least one chosen bit is arranged to set a bit in the load vector when the first thread accesses the selected shared memory element in order to read it, and wherein the means for setting at least one chosen bit is arranged to set a bit in the store vector when the first thread accesses the selected shared memory element in order to write to it.

5. The apparatus according to claim 3, wherein the data structure comprises a single combined load and store vector.

6. The apparatus according to claim 4, wherein there is a one-to-one correspondence between the shared memory elements in the shared memory and the bits in the, or each, vector of the data structure.

7. The apparatus according to claim 4, wherein there is a many-to-one correspondence between the shared memory elements in the shared memory and the bits in the, or each, vector of the data structure.

8. The apparatus according to claim 7, wherein the correspondence between the bits in the, or each vector, and the shared memory elements is determined by a hash function that maps the shared memory elements to the bits in the, or each, vector.

9. The apparatus according to claim 1, further comprising:

means for checking whether a thread has a private copy of the selected shared memory element;

means for creating a private copy of the selected shared memory element and

means for reading and writing to a private copy of the selected shared memory element.

10. The apparatus according to claim 1, further comprising means for storing a backup copy of the selected shared memory element.

11. The apparatus according to claim 1, further comprising:

means for determining, when a first thread has finished execution, whether each of the threads on which the first thread may depend is ready to be committed; and

means for checking for a collision between the first thread and each of the threads on which the first thread may depend, said means for checking including means for comparing the data structure associated with the first thread with each respective data structure associated with the threads on which the first thread may depend.

12. The apparatus according to claim 11, further comprising means for creating a dependence list associated with the first thread before execution of the first thread, said dependence list including a reference to each thread which has not yet been committed and which comes before the first thread in program order.

13. The apparatus according to claim 11, further comprising:

means for committing the first thread if no collision is detected between the first thread and any of the threads on which the first thread may depend; and

means for restarting execution of the first thread if a collision is detected between the first thread and any of the threads on which the first thread may depend.

14. The apparatus according to claim 13, further comprising means for delaying a restart of execution of the first thread until the threads or each of the threads, with which the first thread has collided has been committed.

15. The apparatus according to claim 14, further comprising means for giving priority to committing and/or executing the thread, or each of the threads, with which the first thread has collided.

16. The apparatus according to claim 11, further comprising means for performing a partial check for collisions between the first thread and at least one of the threads on which the first thread may depend, said means for performing a partial check including means for comparing the data structure associated with the first thread with the respective data structure associated with the at least one of the threads on which the first thread may depend.

17. A method for recording information regarding accesses to a number of shared memory elements of a shared memory, said shared memory being accessible by a plurality of threads that are arranged to execute computer program instructions speculatively out of program order, wherein each of the threads is associated with a respective data structure for collision detection between the plurality of threads, said data structure being arranged to store information indicating which of said number of shared memory elements the associated thread has accessed, said method comprising the steps of:

accessing by a first of the plurality of threads, a selected shared memory element in the shared memory, and

storing by the first thread, information in the associated data structure of the first thread, information indicating the first thread'"'"'s access to the selected shared memory element.

18. The method according to claim 17, wherein the data structure is one of the following types of structures:

an unsorted list, a sorted list, a tree and a table.

19. The method according to claim 17, wherein each data structure comprises a number of bits that correspond to the shared memory elements of the shared memory, and wherein the step of storing information includes setting a chosen bit in the data structure corresponding to the selected shared memory element.

20. The method according to claim 19, wherein the data structure comprises a load vector and a store vector, wherein the chosen bit is a bit in the load vector if the first thread accesses the selected shared memory element in order to read it, and wherein the chosen bit is a bit in the store vector if the first thread accesses the selected shared memory element in order to write to it.

21. The method according to claim 19, wherein the data structure comprises a single combined load and store vector.

22. The method according to claim 20, wherein there is a one-to-one correspondence between the shared memory elements in the shared memory and the bits in the, or each, vector of the data structure.

23. The method according to claim 20, wherein there is a many-to-one correspondence between the shared memory elements in the shared memory and the bits in the, or each, vector of the data structure.

24. The method according to claim 23, wherein the correspondence between the bits in the, or each, vector and the shared memory elements is determined by means of mapping the memory elements to the bits in the, or each, vector using a hash function.

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

determining by the first thread, whether the first thread has a private copy of the selected shared memory element;

if the first thread has a private copy and the first thread accesses the selected shared memory element in order to read it, reading by the first thread from the private copy;

if the first thread does not have a private copy and the first thread accesses the selected shared memory element in order to read it, reading by the first thread from the selected shared memory element in the shared memory;

if the first thread has a private copy and the first thread accesses the selected shared memory element in order to write to it, writing by the first thread to the private copy; and

if the first thread does not have a private copy and the first thread accesses the selected shared memory element in order to write to it, creating by the first thread a private copy of the selected shared memory element, and writing by the first thread to the private copy.

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

if the first thread accesses the selected shared memory element in order to write to it, storing by the first thread, a backup copy of the selected shared memory element; and

writing by the first thread to the selected shared memory element in the shared memory after the backup copy is stored.

27. A method for handling possible collisions between a plurality of threads, said threads being arranged to execute computer program instructions speculatively out of program order and to access shared memory elements of a shared memory, said method comprising the steps of:

executing a first thread;

determining, when the first thread has finished execution, whether each of the threads on which the first thread may depend is ready to be committed;

waiting until each of the threads on which the first thread may depend is ready to be committed, if each of the threads on which the first thread may depend is not ready to be committed; and

checking for a collision between the first thread and each of the threads on which the first thread may depend by comparing a data structure associated with the first thread with a data structure associated with the thread on which the first thread may depend, said data structure storing information regarding which of the shared memory elements the thread with which the data structure is associated has accessed during execution of the thread.

28. The method according to claim 27, wherein each data structure includes a number of bits that correspond to the shared memory elements of the shared memory, and wherein a bit is set if the shared memory element to which the bit corresponds has been accessed by the thread with which the data structure is associated during execution of the thread.

29. The method according to claim 28, wherein each data structure includes a load vector and a store vector, wherein a bit in the load vector is set if the memory element to which the bit corresponds has been read by the thread with which the data structure is associated during execution of the thread, and wherein a bit in the store vector is set if the memory element to which the bit corresponds has been written to by the thread with which the data structure is associated during execution of the thread.

30. The method according to claim 28, wherein each data structure comprises a single combined load and store vector.

31. The method according to claim 27, further comprising creating a dependence list associated with the first thread before execution of the first thread, said dependence list including a reference to each thread which has not yet been committed and which comes before the first thread in program order.

32. The method according to claim 27, wherein the first thread is committed if no collision is detected, and wherein the execution of the first thread is restarted if a collision is detected.

33. The method according to claim 32, wherein the restart of execution of the first thread is delayed until the thread, or each of the threads, with which the first thread collided has been committed.

34. The method according to claim 33, wherein priority is given to committing and/or executing the thread, or each of the threads, with which the first thread collided.

35. The method according to claim 27, further comprising performing a partial check for collisions between the first thread and at least one of the threads on which the first thread may depend by comparing the data structure associated with the first thread with the respective data structure associated with the at least one of the threads on which the first thread may depend, wherein no locking of the data structures takes place while the partial check is performed.

36-37. -37. (Canceled)