Abstract: Variable Instruction Scheduling for MIMD Interpretation on Pipelined SIMD Machines and for Compositional Instruction Sets.

Functional parallelism may be supported on SIMD machines by interpretation. The programs and data of each function 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 these functions. The performance of this paradigm has been shown to benefit considerably from a variable instruction issue schedule that delays execution of expensive and rarely occuring operations. Two new features of the interpretation paradigm, namely pipelinined SIMD machines and compositional instruction sets, change the nature of the mathematical model used for variable instruction scheduling significantly. In this paper, a previously developed mathematical model of the interpretation process is extended to allow for compositional instructions and pipelining. We develop and present algorithms that produce variable instruction schedules for the extended model and investigate whether variable instruction issue is useful for these cases. We show that variable instruction issue improves the performance of pipelined machines but is not very effective for compositional instruction sets, especially when the composition matrix is not sparse.
Back to Nael's homepage , or view my resume .