Multi-phased and multi-threaded program execution based on SIMD ratio
A microprocessor is configured to execute programs divided into discrete phases. A scheduler is provided for scheduling instructions. A plurality of resources are for executing instructions issued by the scheduler, wherein the scheduler is configured to schedule each phase of the program only after receiving an indication that execution of the preceding phase of the program has been completed. By splitting programs into multiple phases and providing a scheduler that is able to determine whether execution of a phase has been completed, each phase can be separately scheduled and the results of preceding phases can be used to inform the scheduling of subsequent phases. In one example, different numbers of threads and/or different numbers of data instances per thread may be processed for different phases of the same program.
1. A non-transitory machine readable medium having stored thereon a program executable on a single instruction multiple data (SIMD) processor, the program being divided into a plurality of phases by phase instructions,
the phase instructions being provided at points in the program where processing of different data instances in SIMD parallel fashion during one phase of the plurality of phases may branch to different instructions during a subsequent phase of the plurality of phases, and
in each phase of the plurality of phases, the program contains data to be used, by a scheduler, to dynamically calculate resource requirements for executing that phase of the program, prior to executing that phase, wherein the scheduler is configured to schedule each subsequent phase of the program separately by emitting threads and assigning data instances to said threads according to the dynamically calculated resource requirements of that subsequent phase, results of executing a preceding phase of the program, and a total number of data instances to be processed by that subsequent phase of the program.
2. The non-transitory machine readable medium according to claim 1 , wherein the scheduler is configured to determine a number of data instances for each of the threads for each subsequent phase of program instructions, for a particular program of a plurality of programs, based on the results of executing a respective preceding phase of that particular program.
3. The non-transitory machine readable medium according to claim 1 , wherein the scheduler is configured to maintain a record for each phase of program instructions that is scheduled, during execution of that phase of program instructions, the record maintained to track a number of threads remaining to be completed for that phase of program instructions.
4. The non-transitory machine readable medium according to claim 1 , further comprising a queue comprising program description data describing programs waiting to begin execution, the queue being coupled to provide input to the scheduler, wherein the program description data comprises, for a particular program, program phase data and a number defining how many data instances are to be processed by a first phase of the particular program.
5. The non-transitory machine readable medium according to claim 4 , wherein each program in the queue is further associated with an initial number of data instances per thread, and wherein the number of data instances per thread may vary between different phases of program execution.
6. A method for scheduling instructions of a program on a single instruction multiple data (SIMD) processor, the program being divided into a plurality of phases by phase instructions, the method comprising:
providing phase instructions at points in the program where processing of different data instances in SIMD parallel fashion during one phase of the plurality of phases may branch to different instructions during a subsequent phase of the plurality of phases;
dynamically calculating resource requirements in each phase of the plurality of phases prior to executing that phase; and
separately scheduling each subsequent phase of the program by emitting threads and assigning data instances to said threads according to the dynamically calculated resource requirements of that subsequent phase, results of executing a preceding phase of the program, and a total number of data instances to be processed by that subsequent phase of the program.
7. The method according to claim 6 , further comprising determining a number of data instances for each of the threads for each subsequent phase of program instructions, for a particular program of a plurality of programs, based on the results of executing a respective preceding phase of that particular program.
8. The method according to claim 6 , further comprising maintaining a record for each phase of program instructions that is scheduled, during execution of that phase of program instructions, the record maintained to track a number of threads remaining to be completed for that phase of program instructions.
9. The method according to claim 6 , further comprising providing input from a queue comprising program description data describing programs waiting to begin execution, wherein the program description data comprises, for a particular program, program phase data and a number defining how many data instances are to be processed by a first phase of the particular program.
10. The method according to claim 9 , wherein each program in the queue is further associated with an initial number of data instances per thread, and wherein the number of data instances per thread may vary between different phases of program execution.
11. A scheduler for scheduling instructions of a program on a multithreaded single instruction multiple data (SIMD) processor, the program being divided into a plurality of phases by phase instructions, the scheduler being configured to:
receive phase instructions at points in a program where processing of different data instances in SIMD parallel fashion during one phase of the plurality of phases may branch to different instructions during a subsequent phase of the plurality of phases;
dynamically calculate resource requirements in each phase of the plurality of phases prior to executing that phase; and
separately schedule each subsequent phase of the program by emitting threads and assigning data instances to said threads according to the dynamically calculated resource requirements of that subsequent phase, results of executing a preceding phase of the program, and a total number of data instances to be processed by that subsequent phase of the program.
12. The scheduler according to claim 11 , wherein the scheduler is configured to determine a number of data instances for each of the threads for each subsequent phase of program instructions, for a particular program of a plurality of programs, based on the results of executing a respective preceding phase of that particular program.
13. The scheduler according to claim 11 , wherein the scheduler is configured to maintain a record for each phase of program instructions that is scheduled, during execution of that phase of program instructions, the record maintained to track a number of threads remaining to be completed for that phase of program instructions.
14. The scheduler according to claim 11 , wherein the scheduler is coupled to receive input from a queue, the queue comprising program description data describing programs waiting to begin execution, wherein the program description data comprises, for a particular program, program phase data and a number defining how many data instances are to be processed by a first phase of the particular program.
15. The scheduler according to claim 14 , wherein each program in the queue is further associated with an initial number of data instances per thread, and wherein the number of data instances per thread may vary between different phases of program execution.