International Journal of High Speed Computing

In this paper we demonstrate the parallelism of the spectral division using the matrix sign function for the generalized nonsymmetric eigenproblem. We employ the so–called generalized Newton iterative scheme in order to compute the sign function of the matrix pair. A recent study showed a considerable reduction (by 75%) in the computational cost of this iteration, making this approach competitive when compared to the traditional QZ algorithm.

The experimental results on an IBM SP3 multicomputer report the parallel performance (efficiency around 60–80%) and scalability of this approach.

We investigate the average-case speed and scalability of parallel algorithms executing on multiprocessors. Our performance metrics are average-speed and isospeed scalability. For the purpose of average-case performance prediction, we formally define the concepts of average-case average-speed and average-case isospeed scalability. By modeling parallel algorithms on multiprocessors using task precedence graphs, we are mainly interested in the effects of synchronization overhead and load imbalance on the performance of parallel computations. Thus, we focus on the structures of parallel computations, whose inherent sequential parts are limitations to high performance. Task execution times are treated as random variables, so that we can analyze the average-case performance of parallel computations. For several typical classes of task graphs, including iterative computations, search trees, partitioning algorithms, and diamond dags, we derive the growth rate of the number of tasks as well as isospeed scalability in keeping constant average-speed. In addition to analytical results, extensive numerical data are also demonstrated. An important discovery of our study is that while a parallel computation can be made scalable by increasing the problem size together with the system size, it is actually the amount of parallelism that should scale up with the system size. We also argue that under our probabilistic model of parallel algorithms and the list scheduling strategy, the number of tasks should grow at least at the rate of Θ(P log P), where P is the number of processors, so that a constant average-speed can be maintained. Furthermore, Θ(log P/ log P') is the highest isospeed scalability achievable.

The Vector Multiprocessor brings to the multiprocessor what vectorization brought to the single processor. In addition to the usual complement of logic and arithmetic units, each processor contains a programmable communication unit with registers that communicate directly with comparable registers in neighboring processors via an n-dimensional interconnection network. Interprocessor communication tasks are performed to and from these registers in the same way that computational tasks are performed on a vector uniprocessor. Communication is shown to be optimal for a large class of communication tasks. Elements are transmitted, in parallel, to their destination processors at an average rate of one per communication cycle. This result, called O(1) access, is used to develop a balanced communication system where local and global access are comparable. It is also used to support the "vector parallel paradigm" where all arrays are uniformly distributed and the user interface "looks" like a vector uniprocessor interface. Both coarse- and fine-grain performance models are provided, which demonstrate the unexpected result that communication is asymptotically negligible compared to computational time. Finally, three performance models are presented for the spherical harmonic transform, which is the most communication-intensive part of climate model dynamics.

We present a parallel 2D wavelet transform algorithm with modest communication requirements. Data are transmitted between nearest neighbors only and the amount is independent of the problem size as well as the number of processors. An analysis of the theoretical performance shows that the algorithm is scalable approaching perfect speedup as the problem size is increased. This performance is realized in practice on the IBM SP2 as well as on the Fujitsu VPP300 where it will form part of the Scientific Software Library.