International Journal of High Speed Computing

We study both shared and distributed approaches for the parallel implementation of the SSOR and Jacobi block preconditioned Krylov methods on a distributed virtual shared memory computer: a BBN TC2000. We consider the solution of block tridiagonal systems arising from the discretization of 3D partial differential equations, which diagonal blocks correspond to the discretization of 2D partial differential equations. The solution of the diagonal subproblems required for the preconditionings are performed using a domain decomposition method with overlapped subdomains: a variant of the Schwarz alternating method.

An iterative method for solving large linear systems with sparse symmetric positive definite matrices on massively parallel computers is suggested. The method is based on the Factorized Sparse Approximate Inverse (FSAI) preconditioning of ‘parallel’ CG iterations. Efficiency of a concurrent implementation of the FSAI-CG iterations is analyzed for a model hypercube, and an estimate of the optimal hypercube dimension is derived. For finite element applications, two strategies for selecting the preconditioner sparsity pattern are suggested. A high convergence rate of the resulting iterations is demonstrated numerically for the 3D equilibrium equations for linear elastic orthotropic materials approximated using both h- and p-versions of the FEM.

High performance of mathematical functions is essential to speed up scientific calculations because they are very frequently used in scientific computing. This paper presents performance of important Fortran intrinsic functions on the fastest vector supercomputers.

It is assumed that a relationship between CPU-time and the number of function arguments given to calculate function values is linear, and speeds of a function were measured using the parameters and . The author also examines how the speed of the function varies with respect to the selection of arguments. The computers tested in the present paper are Cray C9016E/16256– 4, Fujitsu VP2600/10, Hitachi S-3800/480 and NEC SX-3/14R.

In addition to load balancing and synchronization overhead, affinity is an important consideration for loop scheduling algorithms in modern multiprocessors. Algorithms based on affinity, like affinity scheduling (AFS), do perform better than dynamic algorithms, such as guided self-scheduling (GSS) and trapezoid self-scheduling (TSS). However, there is still room for improvement in affinity scheduling. This paper suggests a modification to AFS which combines the advantages of both GSS and AFS. Experimental results confirm the effectiveness of the proposed modification.

In this paper we introduce a class of trees, called generalized compressed trees. Generalized compressed trees can be derived from complete binary trees by performing certain ‘contraction’ operations. A generalized compressed tree CT of height h has approximately 25% fewer nodes than a complete binary tree T of height h. We show that these trees have smaller (up to a 74% reduction) 2-dimensional and 3-dimensional VLSI layouts than the complete binary trees. We also show that algorithms initially designed for T can be simulated by CT with at most a constant slow-down. In particular, algorithms having non-pipelined computation structure and originally designed for T can be simulated by CT with no slow-down.

An important part of a parallelizing compiler is the restructuring phase, which extracts parallelism from a sequential program. We consider an important restructuring transformation called cycle shrinking [5], which partitions the iteration space of a loop so that the iterations within each group of the partition can be executed in parallel. The method in [5] mainly deals with dependences with constant distances. In this paper, we propose certain extensions to the cycle shrinking transformation. For dependences with constant distances, we present an algorithm which, under certain fairly general conditions, partitions the iteration space in a minimal number of groups. Under such conditions, our method is optimal while the previous methods are not. We have also proposed an algorithm to handle a large class of loops which have dependences with variable distances. This problem is considerably harder and has not been considered before in full generality.

A parallel sorting algorithm is presented for general purpose internal sorting on MIMD machines. The algorithm initially sorts the elements within each node using a serial sorting algorithm, then proceeds with a two-phase parallel merge. The algorithm is comparison-based and requires additional storage of order the square root of the number of elements in each node. Performance of the algorithm on the Fujitsu AP1000 MIMD supercomputer is discussed.

We consider the problem of dynamic load balancing in an n processor parallel system. The scheduling process of a parallel program is modeled by randomly throwing weighted balls into n holes. For a given program A, the ball weights (task lengths) are chosen according to a probability distribution , for which we know only some of the following parameters: the expectation μ, variance σ², maximum M and minimum m. From these parameters, we derive an upper bound for the number of tasks to be generated by A in order to achieve a load balancing ratio for which the run-time is optimal up to a factor (1+ε)² for any 0<ε≤0.5, with very high probability. Using the derived relations, the programmer may control the load-balancing of his program by tuning the global parameters of the generated tasks. This can be done regardless of the underlying scheduler used by the parallel machine. We also give experimental results of marine-life simulation in support of our claims.