International Journal of High Speed Computing

In this paper, we propose a new parallel bidirectional algorithm, based on Cholesky factorization, for the solution of sparse symmetric system of linear equations. Unlike the existing algorithms, the numerical factorization phase of our algorithm is carried out in such a manner that the entire back substitution component of the substitution phase is replaced by a single step division. Since there is a substantial reduction in the time taken by the repeated execution of the substitution phase, our algorithm is particularly suited for the solution of systems with multiple b-vectors. The effectiveness of our algorithm is demonstrated by comparing it with the existing parallel algorithm, based on Cholesky factorization, using extensive simulation studies on two-dimensional problems discretized by FEM.

In Part I of this paper, we proposed a new parallel bidirectional algorithm, based on Cholesky factorization, for the solution of sparse symmetric system of linear equations. In this paper, we propose a new parallel bidirectional algorithm, based on LU factorization, for the solution of general sparse system of linear equations having non symmetric coefficient matrix. As with the sparse symmetric systems, the numerical factorization phase of our algorithm is carried out in such a manner that the entire back substitution component of the substitution phase is replaced by a single step division. However, due to absence of symmetry, important differences arise in the ordering technique, the symbolic factorization phase, and message passing during numerical factorization phase. The bidirectional substitution phase for solving general sparse systems is the same as that for sparse symmetric systems. The effectiveness of our algorithm is demonstrated by comparing it with the existing parallel algorithm, based on LU factorization, using extensive simulation studies.

In this paper, we propose a new mapping of the Cyclic Elimination (CE) algorithm for the solution of block tridiagonal linear system of equations onto hypercube multiprocessors. Unlike the previous mapping schemes, in our mapping of the CE algorithm all communications are restricted to physically adjacent processors, using the concept of data replication. The effectiveness of our mapping is demonstrated by comparing it with the existing mapping of the Cyclic Reduction algorithm onto hypercubes using both analytical and simulation methods.

In this paper, we propose a mesh with a global bus as a multi-computer topology. This structure enhances the communication capability of the mesh and shows that the mesh with a global bus has more salient properties than the mesh, the hypercube, or other variants. These properties includes a small diameter, a relatively small degree, small average distance, suitability for broadcasting, small initial data distribution time, etc. We propose a dynamic load distribution algorithm to utilize the enhanced communication capability of the mesh with a global bus. Also, asynchronous bus control and arbitration logics are designed to support the proposed algorithm efficiently. It has been shown through simulation that the proposed dynamic load distribution is superior to the Receiver Initiated Diffusion method, previously known as the best to-date. The proposed algorithm shows better total task execution time and better processor utilization with a smaller number of task migrations.

High bandwidth and low latency switches are commercially available. Using these switches, it becomes possible to build a system area network to interconnect workstations and processor clusters together to provide a cost-effective parallel computing platform. A processor cluster may be a shared-memory multiprocessor or a mesh-connected multicomputer, etc. The interconnection topology on this kind of platform, called switch-based NOWP, is usually irregular. On such systems, multicast is an important collective communication operation. Two steps are involved in a multicast: (1) the source node sends the multicast message to the destinations which are connected to a switch directly or are the leader of a processor cluster, and (2) the leader node of each cluster sends the message to other destinations in the same cluster. In this paper, we propose two unicast-based multicast algorithms. Algorithm Multicast_1 performs those two steps sequentially; while Algorithm Multicast_2 overlaps them. Performance of the two algorithms will be evaluated and compared.