Analysis of asynchronous SPMD execution of data parallel algorithms in massively parallel systems

Massively parallel computing systems by their very nature, are suited for problems with a very high degree of parallelism. For this reason, data parallel algorithms are a good match for efficient execution on these architectures. Many real world parallel systems on a massive scale have been limited to SIMD architectures due to the prohibitive cost of multiple instruction memories for each processor. These systems can reap a performance benefit from an asynchronous control structure. However, it is unlikely that every processing element will execute a different set of instructions. This dissertation presents a novel instruction caching system that extends asynchronous execution to a SIMD system without storing multiple copies of the program (as MIMD systems do). Operation in this SPMD paradigm is the most natural fit for data parallel applications. By comparing two very similar systems, one SPMD and one SIMD, the advantages of asynchronously executing: different program blocks (loops, conditionals, and synchronization points) are quantified. Actual multiprocessor algorithms are simulated to generate performance data. It is shown that the benefit of a SPMD system remains in spite of the synchronization overhead. An analytical model is constructed to represent parallel program execution streams and used to drive the instruction caches. The model\u27s predictions are supported by multiprocessor simulation data. The caching system architecture is validated and its feasibility shown. The results are used to examine the important parameters affecting caching performance. Traces are derived from parallel program execution and are used to set design parameters of the individual cache units. Results show that a reasonable cache design is able to meet the performance criteria for the efficient operation of the I-caching system