Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array A affinely aligned t...
详细信息
ISBN:
(纸本)0897915895
Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array A affinely aligned to a template that is distributed across p processors with a cyclic(κ) distribution, and a computation involving the regular section A(: h: s), the local memory access sequence for any processor is characterized by a finite state machine of at most κ;states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time.
Data-flow analysis of scalar variables and data dependence analysis on array elements are two important program analyses used in optimizing and parallelizing compilers. Traditional data-flow analysis models accesses o...
详细信息
ISBN:
(纸本)0897915607
Data-flow analysis of scalar variables and data dependence analysis on array elements are two important program analyses used in optimizing and parallelizing compilers. Traditional data-flow analysis models accesses of array elements simply as accesses to the entire array, and is inadequate for parallelizing loops in array-based programs. On the other hand, data dependence analysis differentiates between different array elements but is flow-insensitive. This paper studies the combination of these two analyses - data-flow analysis of accesses to individual array elements. The problem of finding precise array data-flow information in the domain of loop nests where the loop bounds and array indices are affine functions of loop indices was first formulated by Feautrier. Feautrier's algorithm, based on parametric integer programming techniques, is general but inefficient. This paper presents an efficient algorithm that can find the same precise information for many of the programs found in practice. In this paper, we argue that data-flow analysis of individual array elements is necessary for effective automatic parallelization. In particular, we demonstrate the use of array data-flow analysis in an important optimization known as array privatization. By demonstrating that array data-flow analysis can be computed efficiently and by showing the importance of the optimizations enabled by the analysis, this paper suggests that array data-flow analysis may become just as important in future optimizing and parallelizing compilers as data-flow and data dependence analysis are in today's compilers.
Several novel techniques for efficient implementation of concurrent object-oriented languages on general purpose, stock multicomputers are presented. These techniques have been developed in implementing our concurrent...
详细信息
ISBN:
(纸本)0897915895
Several novel techniques for efficient implementation of concurrent object-oriented languages on general purpose, stock multicomputers are presented. These techniques have been developed in implementing our concurrent object-oriented language ABCL on a Fujitsu Laboratory's experimental multicomputer AP1000 consisting of 512 SPARC chips. The proposed intra-node scheduling mechanism reduces the cost of local message passing. The cost of intra-node asynchronous message passing is about 20 SPARC instructions in the best case, including locality checking, dynamic method lookup, and scheduling. The minimum latency of asynchronous internode message passing is about 9 μs, or about 120 instructions, employing the self-dispatching mechanism independently proposed by Eicken et al. A large scale benchmark which involves 9,000,000 message passings shows 440 times speedup on the 512 nodes system compared to the sequential version of the same algorithm. We rely on simple hardware support for message passing and use no specialized architectural supports for object-oriented computing. Thus, we are able to enjoy the benefits of future progress in standard processor technology. Our result shows that concurrent object-oriented languages can be implemented efficiently on conventional multicomputers.
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of mo...
详细信息
ISBN:
(纸本)0897915895
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of formal loopholes, rather than rewarding development of techniques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. It is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers. Such a model must strike a balance between detail and simplicity in order to reveal important bottlenecks without making analysis of interesting problems intractable. The model is based on four parameters that specify abstractly the computing bandwidth, the communication bandwidth, the communication delay, and the efficiency of coupling communication and computation. Portable parallel algorithms typically adapt to the machine configuration, in terms of these parameters. The utility of the model is demonstrated through examples that are implemented on the CM-5.
The proceedings contain 21 papers. The topics discussed include: optimal schedules for parallel prefix computation with bounded resources;parallel-program transformation using a metalanguage;mapping concurrent program...
ISBN:
(纸本)0897913906
The proceedings contain 21 papers. The topics discussed include: optimal schedules for parallel prefix computation with bounded resources;parallel-program transformation using a metalanguage;mapping concurrent programs to VLIW Processors;a unified framework for systematic loop transformations;scanning polyhedra with DO loops;removal of redundant dependence in DOACROSS constant dependence;exploitation of APL data parallelism on a shared-memory MIMD machine;Andorra-I: a parallel prolog system that transparently exploits both and- and or-parallelism;and scalable reader- writer synchronization for shared-memory multiprocessors.
This paper presents Jade, a language which allows a programmer to easily express dynamic coarse-grain parallelism. Starting with a sequential program, a programmer augments those sections of code to be parallelized wi...
详细信息
Andorra-I is an experimental parallel Prolog system that transparently exploits both dependent and-parallelism and or-parallelism. It constitutes the first implementation of the Basic Andorra model, a parallel executi...
详细信息
暂无评论