Interconnection networks and compiler algorithms for multiprocessors
Kyungsook Yoon Lee · 1983
In this thesis the rearrangeability of interconnection networks and the data movement between the global memory and the processor local memory are studied. A new rearrangeability proof for interconnection networks is developed, with the same lower bound hardware requirement as the Benes network but for a general configuration. This new proof technique is universal, in the sense that it can be applied to any lower bound rearrangeable interconnection network. It is also a constructive proof which yields a control algorithm. Another problem studied is the effect of global delays on system speed, caused by the traffic between local memory and global memory in parallel processor systems. The memory bandwidth, memory conflicts and interconnection conflicts contribute to global delays. A Prefetch/Execute/Poststore pipeline is introduced to reduce the performance degradation due to global delays for innermost vector loops. The analyzing vectorizer PARAFRASE is used to measure the speedup loss on 31 scientific programs with and without the pipeline.