International Journal of High Speed Computing

The leapfrog scheme is a commonly used second-order difference scheme for solving differential equations. If Z(t) denotes the state of a system at a particular time step t, the leapfrog scheme computes the state at the next time step as Z(t+1)=H(Z(t),Z(t-1),W), where H is the nonlinear time-stepping operator and W represents parameters that are not time-dependent. In this note, we show how the associativity of the chain rule of differential calculus can be used to compute a so-called adjoint, the derivative of a scalar-valued function applied to the final state Z(T) with respect to some chosen parameters, efficiently in a parallel fashion. To this end, we (1) employ the reverse mode of automatic differentiation at the outermost level, (2) use a sparsity-exploiting version of the forward mode of automatic differentiation to compute derivatives of H at every time step, and (3) exploit chain rule associativity to compute derivatives at individual time steps in parallel. We report on experimental results with a 2-D shallow water equations model problem on an IBM SP parallel computer and a network of Sun SPARCstations.

This paper describes a new fault-tolerant routing algorithm for k-ary n-cubes using the concept of "probability vectors". To compute these vectors, a node determines first its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty links. Each node then calculates a probability vector, where the lth element represents the probability that a destination node at distance l cannot be reached through a minimal path due to a faulty node or link. The probability vectors are used by all the nodes to achieve an efficient fault-tolerant routing in the network. An extensive performance analysis conducted in this study reveals that the proposed algorithm exhibits good fault-tolerance properties in terms of the achieved percentage of reachability and routing distances.

In this paper we compare various parallel preconditioners for solving large sparse nonsymmetric linear systems. They are Block Jacobi, Point-SSOR, ILU(0) in the wavefront order, ILU(0) in the multi-color order, SPAI(SParse Approximate Inverse), and Multi-Color Block SOR. The Block Jacobi and Point-SSOR are well-known, and ILU(0) is one of the most popular preconditioners, but it is inherently serial. ILU(0) in the wavefront order maximizes the parallelism, and ILU(0) in the multi-color order achieves the parallelism of order (N), where N is the order of the matrix. The SPAI tries to capture the approximate inverse in sparse form, which, then, is expected to be a scalable preconditioner. Finally, we implemented the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver. For the Laplacian matrix the SOR method is known to have a non-deteriorating rate of convergence when used with Multi-Color ordering. Since most of the time is spent on the diagonal inversion, which is done on each processor, we expect it to be a good scalable preconditioner. Finally, due to the blocking effect, it will be effective for ill-conditioned problems. Experiments were conducted for the Finite Difference discretizations of two problems with various meshsizes varying up to 1024×1024, and for an ill-conditioned matrix from the shell problem from the Harwell–Boeing collection. CRAY-T3E with 128 nodes was used. MPI library was used for interprocess communications. The results show that Multi-Color Block SOR and ILU(0) with Multi-Color ordering give the best performances for the finite difference matrices and for the shell problem only the Multi-Color Block SOR and Block Jacobi converges. Based on this we recommend that the Multi-Color Block SOR is the most robust preconditioner out of the preconditioners considered.

The Communication Machine brings to the multicomputer what vectorization brought to the uniprocessor. It provides the same tools to speed communication that have traditionally been used to speed computation; namely, the capability to program optimal communication algorithms on an architecture that can, to the extent possible, replicate their performance in terms of wall-clock time. In addition to the usual complement of logic and arithmetic units, each module contains a programmable communication unit that orchestrates traffic between the network and registers that communicate directly with comparable registers in neighboring modules. Communication tasks are performed out of these registers like computational tasks on a vector uniprocessor. The architecture is balanced in the sense that, on average, the speed of local and global memory is comparable. Theoretical performance is tabulated for both hypercube and mesh interconnection networks. The Communication Machine returns to the somewhat beleaguered, yet intuitive concept that the performance we ultimately seek must come from a truly massive number of processors.