Memory Latency Reduction Via Data Prefetching And Data Forwarding In Shared Memory Multiprocessors

Memory Latency Reduction Via Data Prefetching and Data Forwarding in Shared Memory Multiprocessors

This dissertation considers the use of data prefetching and an alternative mechanism, data forwarding, for reducing memory latency due to interprocessor communication in cache coherent, shared memory multiprocessors. The benefits of prefetching and forwarding are considered for large, numerical application codes with loop-level and vector parallelism. Data prefetching is applied to these applications using two different multiprocessor prefetching algorithms implemented within a parallelizing compiler. Data forwarding considers array references involved in communication-related accesses between successive parallel loops, rather than within a single loop nest. A hybrid prefetching and forwarding scheme and a compiler algorithm for data forwarding are also presented. EPG-sim, a system of execution-driven simulation tools for studying parallel architectures, algorithms, and applications, was developed as a prerequisite for this work. EPG-sim performs execution-driven simulation and critical path simulation within a single, integrated environment. EPG-sim provides an extremely wide range of cost/accuracy trade-offs and a number of novel features compared to existing execution-driven systems. The parallelism and communication behavior of numerical application codes are studied via EPG-sim critical path simulation, which establishes the potential performance of prefetching and forwarding for these codes. The evaluation of prefetching and forwarding is accomplished via detailed EPG-sim execution-driven simulations of optimized, parallel versions of these application codes. Two multiprocessor prefetching algorithms are presented and compared. A simple blocked vector prefetching algorithm, considerably less complex than existing software pipelined prefetching algorithms, is shown to be effective in reducing memory latency and increasing performance. A Forwarding Write operation is used to evaluate the effectiveness of forwarding. Data forwarding results in significant performance improvements over data prefetching for codes exhibiting less spatial locality. A new hybrid prefetching and forwarding scheme is presented that provides increased performance stability by adapting to varying application characteristics and architectural parameters. The hybrid scheme is shown to be effective in improving the performance of forwarding in reduced cache sizes. A compiler algorithm for data forwarding is presented that implements point-to-point forwarding, hybrid prefetching and forwarding, and selective forwarding. Software and hardware support for prefetching and forwarding are also discussed.

Euro-Par 2000 Parallel Processing

Euro-Par – the European Conference on Parallel Computing – is an international conference series dedicated to the promotion and advancement of all aspects of parallel computing. The major themes can be divided into the broad categories of hardware, software, algorithms, and applications for parallel computing. The objective of Euro-Par is to provide a forum within which to promote the dev- opment of parallel computing both as an industrial technique and an academic discipline, extending the frontier of both the state of the art and the state of the practice. This is particularlyimportant at a time when parallel computing is - dergoing strong and sustained development and experiencing real industrial take up. The main audience for and participants of Euro-Par are seen as researchers in academic departments, government laboratories, and industrial organisations. Euro-Par’s objective is to become the primarychoice of such professionals for the presentation of new results in their speci?c areas. Euro-Par is also interested in applications that demonstrate the e?ectiveness of the main Euro-Par themes. Euro-Par now has its own Internet domain with a permanent Web site where the historyof the conference series is described: http://www. euro-par. org. The Euro-Par conference series is sponsored bythe Association of Computer Machineryand the International Federation of Information Processing.

Proceedings of the 1994 International Conference on Parallel Processing, August 15-19, 1994: Software