International Journal of High Speed Computing

The software package COLNEW [G. Bader and U. Ascher, SIAM J. Sci. Statist. Comput., 8 (1987), pp. 483–500], which implements the method of spline collocation at Gauss points, has been widely used for the solution of mixed-order systems of boundary value problems in ordinary differential equations. Considerable attention has been given in recent years to the development of efficient algorithms for the solution of the almost block diagonal (ABD) linear systems of the type which arise in this method, and some of these algorithms have been designed to exploit parallelism. However, in COLNEW, the solution of the ABD systems contributes only a modest amount to the overall execution time, thus limiting the potential of these new solvers. In this paper, we examine the linear system setup, which is the primary bottleneck in COLNEW and has not been addressed previously. We describe PCOLNEW, a modified version of COLNEW which incorporates coarse-grained parallelism to minimize the cost of this bottleneck. Numerical results of tests conducted on a variety of shared-memory machines are presented which demonstrate the efficacy of this parallel implementation.

In this paper we report on our first experience with a portable, easily usable communication environment, 'Sciddle', for distributing computations over a homogeneous network of UNIX computers. We demonstrate the usefulness of the system with applications from linear algebra and quantum chemistry on a network of Ethernet-connected Sun workstations and of Internet-connected Cray supercomputers, respectively.

The purpose of this paper is to suggest a new parallel algorithm for the knapsack problem. The design of the proposed parallel algorithm is based on a shared memory SIMD machine with a heap tree data structure. It can solve a general n-component knapsack problem in time O(2^n/2) with memory-processor tradeoff M²P = O(2^n/2). The proposed technique can have better performance in terms of cost as the number of processors needed can be offset by increasing memory space. The performance is compared with those of other algorithms to demonstrate its superiority. We believe that the proposed algorithm is pragmatically feasible at the moment when multiprocessor systems are gradually becoming popular.

In this paper, we propose a new top-down subcube allocation scheme, called HSA (Heuristic Subcube Allocation) strategy, and also present a task migration scheme to solve the fragmentation problem in a hypercube. An undirected graph, called SC (Subcube)-graph, whose vertices represent the available subcubes in the hypercube is used for the subcube allocation, and the higher dimension subcube is generated by the cycle detection using the SC-graph. When a subcube is released, a heuristic algorithm is used to maintain the available subcubes as large as possible and to reduce the response time. It is theoretically shown that the HSA strategy is not only statically optimal but also it has a complete subcube recognition capability in the dynamic environment. Extensive simulation results show that the HSA strategy improves the efficiency and significantly reduces the response time with a lower migration cost compared to the previously proposed schemes.

This paper deals with the Gauss elimination for solving general dense linear systems on distributed memory multiprocessors. A row oriented parallel algorithm is proposed and implemented on the NCUBE distributed memory multiprocessor. We study in some detail various implementation choices which are important factors affecting the algorithm's performance. These factors include: mapping of rows into processors, pivoting implementation, message passing, communication granularity and pipelining. Experiments with these on the NCUBE are reported which illustrate the algorithms performance characteristics. Both standard and memory scaled speed up are measured which show that the algorithm is very efficient. Comparisons with previous approaches which mix row and column operations show an obvious gain in efficiency.