Abstract: Synthesizing Variable Instruction Issue Interpreters for Implementing Functional Parallelism on SIMD Computers.
Functional parallelism can be supported on SIMD machines by
interpretation. Under such a scheme the programs and data of each
task are loaded on the processing elements (PEs) and the Control
Unit of the machine executes a central control algorithm that
causes the concurrent interpretation of the tasks on the PEs. The
central control algorithm is, in many respects, analogous to the
control store program on microprogrammed machines. Accordingly, the
organization of the control algorithm greatly influences the
performance of the synthesized MIMD environment.
Most central control algorithms are constructed to interpret the
execution phase of all instructions during every cycle (iteration).
However, it is possible to delay the interpretation of infrequent and
costly instructions to improve the overall performance. Interpreters
that attempt improved performance by delaying the issue of infrequent
instructions are referred to as variable issue control
algorithms. This paper examines the construction of optimized
variable issue control algorithms. In particular, a mathematical
model for the interpretation process is built and two objective
functions (instruction throughput and PE utilization) are defined.
The problem of deriving variable issue control algorithms for these
criteria has been shown elsewhere to be NP-complete. Therefore, this
paper investigates three heuristic algorithms for constructing near
optimal variable issue control algorithms. The performance of the
algorithms is studied on 4 different instruction sets and the trends
of the schedulers with respect to the instruction sets and the
objective functions are analyzed.
Back to Nael's homepage , or view