A study of dynamic scheduling techniques for multiscalar processors

The multiscalar processing model is a recently proposed model for exploiting large amounts of instruction level parallelism from programs written in ordinary, high-level languages. It splits a sequential program into smaller tasks, and exploits instruction level parallelism by executing multiple tasks in parallel using multiple execution units. The parallelly executed tasks can have both control and data dependencies between them. Because the original sequential program was not written with the multiscalar processing model in mind, it is difficult to get good performance without doing further, multiscalar-specific code scheduling. This paper compares two different ways of doing multiscalar-specific dynamic scheduling. In the first method, each execution unit has a scheduling hardware that collects decoded instructions in a buffer, and reorders them based on the run-time availability of dates. Although additional parallelism is extracted by this run-time reordering, the reordering hardware is in the critical path of program execution, and can potentially impact the cycle time. In the second approach that we investigate, called dynamic off-line scheduling, the reordering hardware is in a non-critical path of instruction execution. The off-line scheduling hardware observes the execution behavior of the instructions in a task, and reorders them with a view to speed up the task´s execution the next time the task is executed. The paper presents the results of simulation studies that were conducted using the SPEC benchmarks to evaluate both of these scheduling strategies for the multiscalar processor