International Journal of High Speed Computing

This paper presents a new improved architecture, named a hyper-channel broadcast communication model, as a computational model. The hyper-channel broadcast communication model consists of processors shared by some channels, and there are no local links between processors. Based on such an improved architecture, we first design two O(log N) cycles basic operations for finding the maximum/minimum of N real numbers and the ranks of a linked list using N and N×N processors, respectively. Then based on these proposed operations, two O(log N) cycles sorting algorithms are derived by either using N×N processors for the concurrent-write case or using N×N×N processors for the conflict-free case, respectively.

The development and applications of a parallel, time-dependent, three-dimensional incompressible Navier-Stokes flow solver and a parallel multigrid elliptic kernel are described. The flow solver is based on a second-order projection method applied to a staggered finite-difference grid. The multigrid algorithms implemented in the parallel elliptic kernel, which is used by the flow solver, are V-cycle and full V-cycle schemes. A grid-partition strategy is used in the parallel implementations of both the flow solver and the multigrid kernel on all fine and coarse grids. Numerical experiments and parallel performance measurements show the parallel solver package is numerically stable, physically robust and computationally efficient. Both the multigrid kernel and the flow solver scale well to a large number of processors on Intel Paragon and Cray T3D/T3E for two-and three-dimensional problems with moderate granularity. The solver package has been carefully designed and implemented so that it can be easily adapted to solve a variety of interesting scientific and engineering flow problems. The code is portable to parallel computers that support MPI, PVM and NX for interprocessor communications.

In this paper, we study issues of the multicast communication in the multistage interconnection networks (MINs) for large-scale multicomputers. In addition to point-to-point communication among processing nodes, efficient collective communication is critical to the performance of multicomputers. Multicast communication in which the same packet is delivered from a source node to an arbitrary number of destination nodes is fundamental in supporting collective communication primitives including broadcast, reduction, and barrier synchronization operations. This paper presents a new approach to support multicast communication, on the basis of a restricted address encoding scheme which constructs a short fixed-size multicast header, and a recursive scheme that recycles a multicast packet one or more times through the MIN to send it to the desired destination nodes. We propose a recursive multicast algorithm which provides deadlock-freedom for multiple multicast packets in MIN-based multicomputers. We also present performance model for the unbuffered MIN using the multicast algorithm and analyze its performance in terms of the network throughput, where several multicast communications are considered. The proposed algorithm can be easily applied to wormhole or virtual cut-through MIN-based multicomputers.

Distributed Computing Systems (DCS) promise a convenient platform for parallel processing and consequently can be expected to provide highly improved throughput and turnaround characteristics for all types of computing jobs. Task allocation in DCS remains to be an important and relevant problem attracting the attention of researchers in the discipline. Genetic Algorithms (GA) have successfully been used to solve various optimization problems. A GA based task allocation model for multiprocessors has been proposed by Hou, Ansari & Ren [3]. We present a Genetic Task Allocation Algorithm for DCS, wherein we have considered the underlying interconnection network of the processors, communication requirements among modules of the tasks apart from the precedence relation of the task graph that has been considered in [3] also. We have also considered multiprogramming at every processing nodes with related characteristic values. We have, intentionally, made use of the finding [4] that the incorporation of the problem specific knowledge in construction of GAs improves the initial population structures. The model and algorithm proposed by us is sufficiently simple and adequately usable for the purpose of simulation experiments and its possible incorporation in future operating systems of DCS.

This paper makes an efficient improvement of processor complexity while solving some connectivity problems on a reconfigurable meshes. We first derive two constant time algorithms in the proposed parallel processing system for computing the dominators and the dominator tree of an undirected graph either using a 3-D n×n×n processors or a 2-D n²×n² processors, where n is the number of vertices of the graph. Then based on the dominator tree algorithm, we also solve many other graph connectivity problems in a constant time. They are the articulation points, bridges, biconnected components, and bridge-connected components problem in undirected graphs.