International Journal of High Speed Computing

In this paper a parallel algorithm for solving systems of linear equation on the k-ary n-cube is presented and evaluated for the first time. The proposed algorithm is of O(N³/kⁿ) computation complexity and uses O(Nn) communication time to factorize a matrix of order N on the k-ary n-cube. This is better than the best known results for the hypercube, O(N log kⁿ), and the mesh, , each with approximately kⁿ nodes. The proposed parallel algorithm takes advantage of the extra connectivity in the k-ary n-cube in order to reduce the communication time involved in tasks such as pivoting, row/column interchanges, and pivot row and multipliers column broadcasts.

In this work we apply a methodology for the parallelization of algorithms for tridiagonal solvers. We classify tridiagonal solvers as a function of their data flows and present a unified version of the projection of these algorithms onto computers with mesh topology and distributed memory. Finally, we evaluate the algorithms and compare them through specific tests on the Fujitsu AP1000.

We present an alternative way of designing new as well as using existing coordination models for parallel and distributed environments. This approach is based on a complete symmetry between and decoupling of producers and consumers, as well as a clear distinction between the computation and the coordination/ communication work performed by each process. The novel ideas are: (i) to allow both producer and consumer processes to communicate with each other in a fashion that does not dictate any one of them to have specific knowledge about the rest of the processes involved in a coordinated activity, and (ii) to introduce control or state driven changes (as opposed to the data-driven changes usually employed) to the current state of a computation. Although a direct realisation of this model in terms of a concrete coordination language does exist, we argue that the underlying principles can be applied to other similar models. We demonstrate our point by showing how the functionality of the proposed model can be realised in a general coordination framework, namely the Shared Dataspace one, using as driving force the Linda-based formalism. Our demonstration achieves the following objectives: (i) yields an alternative (control- rather than data-driven) Linda-based coordination framework, and (ii) does it in such a way that the proposed apparatus can be used for other Shared-Dataspace-like coordination formalisms with little modification.

Given the large communication overheads characteristic of modern parallel machines, optimizations that improve locality by executing tasks close to data that they will access may improve the performance of parallel computations. This paper describes our experience automatically applying locality optimizations in the context of Jade, a portable, implicitly parallel programming language designed for exploiting task-level concurrency. Jade programmers start with a program written in a standard serial, imperative language, then use Jade constructs to declare how parts of the program access data. The Jade implementation uses this data access information to automatically extract the concurrency and apply locality optimizations. We present performance results for several Jade applications running on the Stanford DASH machine. We use these results to characterize the overall performance impact of the locality optimizations. In our application set the locality optimization level has little effect on the performance of two of the applications and a large effect on the performance of the rest of the applications. We also found that, if the locality optimization level had a significant effect on the performance, the maximum performance was obtained when the programmer explicitly placed tasks on processors rather than relying on the scheduling algorithm inside the Jade implementation.