Method and system for executing a program within a multiscalar processor by processing linked thread descriptors

A multiscalar processor for executing a multiscalar program, said multiscalar program including first, second, and third threads that are each composed of a plurality of instructions of a selected instruction set architecture, said third thread having an instruction among said plurality forming a single entry point and others of said plurality of instructions forming first and second possible exit points, said multiscalar program further including first, second, and third data structures that are each associated with a corresponding one of said first, second, and third threads, said multiscalar processor comprising:

• a plurality of processing elements that execute threads;
• a thread scheduler, including:
• means, responsive to receipt of said third data structure, said third data structure associating said first data structure with said first possible exit point and associating said second data structure with a second possible exit point, for assigning said third thread to a selected processing element among said plurality of processing elements for execution;
• means for selecting one of said first and said second possible exit points of said third thread prior to said selected processing element completing execution of said third thread;
• and
• means, responsive to said selection, for loading an associated one of said first and second data structures into said thread scheduler for processing.

A method, comprising:

• providing a program including a plurality of threads, each of said plurality of threads including a plurality of instructions that each form a respective one of a plurality of possible thread exit points;
• initiating execution of a first thread among said plurality of threads;
• prior to executing an actual thread exit point of the first thread, predicting which of the plurality of possible thread exit points of the first thread will be the actual thread exit point;
• and
• in response to said prediction, initiating scheduling of a second thread among said plurality of threads that is associated with the possible thread exit point that was predicted.

A processor, comprising:

• a plurality of processing elements for concurrently executing at least two of a plurality of threads of a program, each of said plurality of threads including a plurality of instructions that each form a respective one of a plurality of possible thread exit points;
• a thread scheduler, including:
• means for initiating execution of a first thread among said plurality of threads;
• means for predicting which of the plurality of possible thread exit points of the first thread will be the actual thread exit point prior to execution of the actual thread exit point of the first thread;
• and
• means, responsive to said prediction, for initiating scheduling of a second thread among said plurality of threads that is associated with the possible thread exit point that was predicted.