Executing speculative parallel instructions threads with forking and inter-thread communication

A method of executing instructions on a computer system with a central processing apparatus, comprising the steps of:

• a. Generating a static sequence of instructions, and analyzing the static sequence of instructions to determine a set of fork points;
• b. Inserting zero or more FORK instructions at zero or more of the fork points;
• c. Loading the static sequence of instructions into a main memory starting at a fixed location in the memory and transferring a subsequence of the static sequence to an instruction cache;
• d. Fetching the instruction sequence from the instruction cache by addressing the sequence through a main program counter starting at a current address, as a main thread, and checking to determine if there is one or more unmerged future threads starting at the current address;
• e. Checking the validity of the unmerged future threads;
• f. Merging the validly executed portions of the zero or more unmerged future threads into the main thread;
• g. Decoding the fetched instructions in a dispatcher, and checking to see if one or more of the instructions are decoded as a FORK instruction;
• h. For instructions decoded as other than FORK instructions, executing the main thread by analyzing intra-thread instruction dependencies, and by scheduling the instructions for execution on appropriate functional units;
• i. Completing instruction execution through a completion unit, and repeating steps (d) through this step;
• j. For an instruction decoded as a FORK instruction, checking to determine the availability of machine resources for forking an additional future thread;
• k. Forking a future thread, if there are resources available, by loading the address associated with the FORK instruction into a future program counter;
• and
• l. Executing a future thread in parallel with the forking thread execution, by performing steps (d) through (h) by using one of the future program counters and one of the future thread dispatchers, instead of the main program counter and the main thread dispatcher, respectively, and suspending the future thread execution if the future thread is merged with the main thread or the future thread is killed by the thread management unit and where data is accessed from a register file by any one of the future threads in order to resolve data dependences between the future thread and the main thread.

A central processing apparatus in a computer comprising:

• a. an instruction cache memory having a plurality of instructions, the instruction cache further having one or more instruction cache ports;
• b. a program counter bank of more than one program counter, each program counter capable of independently addressing one or more instructions in the instruction cache, and porting the addressed instructions to one of the instruction cache ports;
• c. a register file including a fixed set of one or more general purpose architected registers;
• d. a thread management unit, under control of one or more of the instructions, that forks one or more threads, each thread having a sequence of the instructions that is executed by being addressed by one of the program counters, the thread management unit further handling zero or more inter-thread communications, the inter-thread communications capable of communicating controls between one or more pairs of the threads, the controls resolving zero or more inter-thread control dependences between any of the pairs of threads, and the inter-thread communications further capable of communicating data through one or more of the architected registers resolving zero or more inter-thread data dependences between any of the pairs of threads, each pair of threads having a former thread and a latter thread, the register file being accessible by instructions in every thread and suspending the latter thread of the pair if and only if one or more of the dependences between the latter thread and the former thread prevents speculative execution of the latter thread, and communicating any data and controls resolving the dependences between the former and latter thread only at a point of merger of the former thread with the latter thread;
• e. a dispatcher bank of more than one dispatcher, each dispatcher having an associated instruction buffer and each dispatcher being capable of receiving instructions from one or more of the instruction cache ports, placing the received instruction in the respective associated instruction buffer, decoding the instructions, and performing an intra-thread dependency analysis that analyzes intra-thread dependences among the instructions in the respective associated instruction buffer;
• and
• f. a scheduler that receives instructions from all the dispatchers and schedules the instructions for execution on one or more functional units,
• whereby one or more instruction threads are executed by the functional units in parallel.