This paper presents a parallel programming model, Parallel Phase Model (PPM), for next-generation high-end parallel machines based on a distributed memory architecture consisting of a networked cluster of nodes with a large number of cores on each node. PPM has a unified high-level programming abstraction that facilitates the design and implementation of parallel algorithms to exploit both the parallelism of the many cores and the parallelism at the cluster level. The programming abstraction will be suitable for expressing both fine-grained and coarse-grained parallelism. It includes a few high-level parallel programming language constructs that can be added as an extension to an existing (sequential or parallel) programming language such as C; and the implementation of PPM also includes a light-weight runtime library that runs on top of an existing network communication software layer (e.g. MPI). Design philosophy of PPM and details of the programming abstraction are also presented. Several unstructured applications that inherently require high-volume random fine-grained data accesses have been implemented in PPM with very promising results.

Bundle-exchange-compute (BEC) is a new virtual shared memory parallel programming environment for distributed-memory machines. Different from and complementary to other global address space (GAS) programming model research efforts, BEC has built-in efficient support for unstructured applications that inherently require high-volume random fine-grained communication, such as parallel graph algorithms, sparse-matrices, and large-scale physics simulations. In BEC, the global view of shared data structures enables ease of algorithm design and programming; and for good application performance, fine-grained (random) accesses to shared data are automatically and dynamically bundled together for coarse-grained message-passing. BEC frees the users from explicit management of data distribution, locality, and communication. Therefore, BEC is much easier to program than MPI, while achieving comparable application performance. This paper presents some initial BEC applications, which show that simple BEC programs can match very complex and highly optimized MPI codes.

No abstract available.

The problem of merging k (k/spl ges/2) sorted lists is considered. We give an optimal parallel algorithm which takes O((n log k/p)+log n) time using p processors on a parallel random access machine that allows concurrent reads and exclusive writes, where n is the total size of the input lists. This algorithm achieves O(log n) time using p=n log k/log n processors. Most of the previous log n research for this problem has been focused on the case when k=2. Very recently, parallel solutions for the case when k=2 have been reported. Our solution is the first logarithmic time optimal parallel algorithm for the problem when k/spl ges/2. It can also be seen as a unified optimal parallel algorithm for sorting and merging. In order to support the algorithm, a new processor assignment strategy is also presented.

The problem of merging k (k \geqslant 2) sorted lists is considered. We give an optimal parallel algorithm which takes O\left( {\frac{{n\log k}} {p} + \log n} \right) time using p processors on the CREW PRAM, where n is the total size of the input lists. The algorithm can be seen as a unified algorithm for parallel sorting and merging. To obtain this algorithm, interesting techniques for designing algorithms are also discussed, including a new processor assignment strategy.

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).

An adaptive parallel algorithm for inducing a priority queue structure on an n-element array is presented. The algorithm is extended to provide optimal parallel construction algorithms for three other heap-like structures useful in implementing double-ended priority queues, namely min-max heaps, deeps, and min-max-pair heaps. It is shown that an n-element array can be made into a heap, a deap, a min-max heap, or a min-max-pair heap in O(log n+(n/p)) time using no more than n/log n processors, in the exclusive-read-exclusive-write parallel random-access machine model.>