Collision handling apparatus and method

A method of supporting speculative execution of a plurality of speculative threads, the threads comprising computer program instructions, said method comprising the steps of:

• executing the speculative threads by one or more processors, the executing step including:
• accessing by the one or more processors, selected shared memory elements in a shared memory;
• creating by each processor, each time the processor executes one of the speculative threads, a software data structure corresponding to the speculative thread the processor is executing, each software data structure indicating which of the shared memory elements the processor accessed while executing the data structure's corresponding speculative thread, wherein each software data structure has a one-to-one relation with a corresponding speculative thread allowing only information relating to execution of the corresponding speculative thread to be stored in the data structure;
• and
• detecting collisions between threads when a given speculative thread and other speculative threads on which the given speculative thread depends have finished executing their computer program instructions, said detecting step including comparing by a comparing processor, the data structure of the given speculative thread with the data structures corresponding to the other speculative threads on which the given speculative thread depends, wherein the comparing occurs serially after the speculative threads have been executed and prior to being committed.

A method for handling possible collisions between a plurality of speculative threads, said speculative threads comprising computer program instructions to be executed by one or more processors by accessing shared memory elements of a shared memory, said method comprising the steps of:

• executing by the one or more processors, a first speculative thread and speculative threads upon which the first speculative thread depends;
• creating by the one or more processors, a plurality of software data structures that store information indicating which shared memory elements were read or modified during execution of the threads, wherein each time one of the speculative threads is executed, the processor executing the speculative thread stores the information in a corresponding separate data structure having a one-to-one relation with the speculative thread being executed, the data structure allowing only information relating to execution of the corresponding speculative thread to be stored in the data structure;
• when the first speculative thread is ready to be committed, determining by a comparing processor whether each of the speculative threads upon which the first speculative thread depends is ready to be committed;
• if each of the speculative threads upon which the first speculative thread depends is not ready to be committed, waiting by the comparing processor until each of the speculative threads upon which the first speculative thread depends is ready to be committed;
• and
• when each of the speculative threads upon which the first speculative thread depends is ready to be committed, checking for a collision between the first speculative thread and each of the speculative threads upon which the first speculative thread depends by comparing by the comparing processor, the first speculative thread's corresponding software data structure with software data structures corresponding to the speculative threads upon which the first thread depends, wherein the comparing step occurs serially after the first speculative thread has finished executing its computer program instructions and prior to being committed.