Search

The exploitation of today's high-performance computer systems requires the effective use of parallelism in many forms and at numerous levels. This survey article discusses program analysis and restructuring techniques that target parallel architectures. We first describe various categories of architectures that are oriented toward parallel computation models: vector architectures, shared-memory multiprocessors, massively parallel machines, message-passing architectures, VLIWs, and multithreaded architectures. We then describe a variety of optimization techniques that can be applied to sequential programs to effectively utilize the vector and parallel processing units. After an overview of basic dependence analysis, we present restructuring transformations on DO loops targeted both to vectorization and to concurrent execution, interprocedural and pointer analysis, task scheduling, instruction-level parallelization, and compiler-assisted data placement. We conclude that although tremendous advances have been made in dependence theory and in the development of a “toolkit” of transformations, parallel systems are used most effectively when the programmer interacts in the optimization process.

Preface. 1. Introductory Tutorial. 1.1 Getting Started. 1.2 Private and Shared Data. 1.3 Shared Arrays and Affinity of Shared Data. 1.4 Synchronization and Memory Consistency. 1.5 Work Sharing. 1.6 UPC Pointers. 1.7 Summary. Exercises. 2. Programming View and UPC Data Types. 2.1 Programming Models. 2.2 UPC Programming Model. 2.3 Shared and Private Variables. 2.4 Shared and Private Arrays. 2.5 Blocked Shared Arrays. 2.6 Compiling Environments and Shared Arrays. 2.7 Summary. Exercises. 3. Pointers and Arrays. 3.1 UPC Pointers. 3.2 Pointer Arithmetic. 3.3 Pointer Casting and Usage Practices. 3.4 Pointer Information and Manipulation Functions. 3.5 More Pointer Examples. 3.6 Summary. Exercises. 4. Work Sharing and Domain Decomposition. 4.1 Basic Work Distribution. 4.2 Parallel Iterations. 4.3 Multidimensional Data. 4.4 Distributing Trees. 4.5 Summary. Exercises. 5. Dynamic Shared Memory Allocation. 5.1 Allocating a Global Shared Memory Space Collectively. 5.2 Allocating Multiple Global Spaces. 5.3 Allocating Local Shared Spaces. 5.4 Freeing Allocated Spaces. 5.5 Summary. Exercises. 6. Synchronization and Memory Consistency. 6.1 Barriers. 6.2 Split-Phase Barriers. 6.3 Locks. 6.4 Memory Consistency. 6.5 Summary. Exercises. 7. Performance Tuning and Optimization. 7.1 Parallel System Architectures. 7.2 Performance Issues in Parallel Programming. 7.3 Role of Compilers and Run-Time Systems. 7.4 UPC Hand Optimization. 7.5 Case Studies. 7.6 Summary. Exercises. 8. UPC Libraries. 8.1 UPC Collective Library. 8.2 UPC-IO Library. 8.3 Summary. References. Appendix A: UPC Language Specifications, v1.1.1. Appendix B: UPC Collective Operations Specifications, v1.0. Appendix C: UPC-IO Specifications, v1.0. Appendix D: How to Compile and Run UPC Programs. Appendix E: Quick UPC Reference. Index.

We have modified the C language to support a programming model based on a shared address space with physically distributed memory. With this model users can write programs in which the nodes of a massively parallel processor can access remote memory without message passing. AC provides support for distributed arrays as well as pointers to distributed data. Simple array references and pointer dereferencing are sufficient to generate low-overhead remote reads and writes. We have implemented these ideas in a compiler based on the GNU C compiler and targeted at Cray Research's T3D. Initial performance measurements show that AC generates code for remote accesses which is considerably faster than that of the native compiler for structures up to about 16 words in size and virtually equivalent for larger transfers.