International Journal of High Speed Computing

The knapsack problem is known to be a typical NP-complete problem, which has 2ⁿ possible solutions to search over. Thus a task for solving the knapsack problem can be accomplished in 2ⁿ trials if an exhaustive search is applied. In the past decade, much effort has been devoted in order to reduce the computation time of this problem instead of exhaustive search. In 1984, Karnin proposed a brilliant parallel algorithm, which needs O(2^n/6) processors to solve the knapsack problem in O(2^n/2) time; that is, the cost of Karnin's parallel algorithm is O(2^2n/3). In this paper, we propose a fast search technique to improve Karnin's parallel algorithm by reducing the search time complexity of Karnin's parallel algorithm to be O(2^n/3) under the same O(2^n/6) processors available. Thus, the cost of the proposed parallel algorithm is O(2^n/2). Furthermore, we extend this search technique to the case that the number of available processors is P = O(2^x), where x ≥ 1. From the analytical results, we see that our search technique is indeed superior to the previously proposed methods. We do believe our proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular.

This paper presents an algorithm for the Gaussian elimination problem that reduces the length of the critical path compared to the algorithm of Lord et al. This is done by redefining the notion of a task. For all practical purposes, the issues of communication overhead and pivoting cannot be overlooked. We consider these issues for the new algorithm as well. Timing results of this algorithm as executed on the CM-2 model of the Connection Machine are presented. Another contribution of this paper is the use of logical pivoting for stable computation of the Gaussian elimination algorithm. Pivoting is essential in producing stable results. When pivoting occurs, an interchange of two rows is required. A physical interchange of the values can be avoided by providing a permutation vector in a globally accessible location. We show experimental results that substantiate the use of logical pivoting.

In this paper, we present a parallel SIMD algorithm for radix sorting of N numbers of w bits each, taking O(w + N^1/4) time with the VLSI area of O(N^3/2 w²), 0 < w < N^1/4. For w = log N, our algorithm improves a previous known solution on a similar architecture in time complexity by a factor of log N. Since our algorithm uses only radix sort for sorting of subsets and merging of them, no comparator is needed. Our algorithm satisfies the lower bound of AT² complexity which mainly restricts the VLSI implementation of most sorting algorithms. The same result is obtained in another previously known solution, but it requires a comparator of size w.

The Artificial Neural Networks (ANNs) are being used to solve a variety of problems in pattern recognition, robotic control, VLSI CAD and other areas. In most of these applications, a speedy response from the ANNs is imperative. However, ANNs comprise a large number of artificial neurons, and a massive interconnection network among them. Hence, implementation of these ANNs involves execution of computer-intensive operations. The usage of multiprocessor systems therefore becomes necessary.

In this article, we have presented the implementation of ART1 and ART2 ANNs on ring and mesh architectures. The overall system design and implementation aspects are presented. The performance of the algorithm on ring, 2-dimensional mesh and n-dimensional mesh topologies is presented. The parallel algorithm presented for implementation of ART1 is not specific to any particular architecture. The parallel algorithm for ART2 is more suitable for a ring architecture.

In this paper, we consider the problem of solving sparse linear systems occurring in finite difference applications (or N × N grid problems, N being the size of the linear system). We propose a new algorithm for the problem which is based on the Cholesky factorization, a symmetric variant of Gaussian elimination tailored to symmetric positive definite systems. The algorithm employs a new technique called bidirectional factorization to produce the complete solution vector by solving only one triangular system against two triangular systems in the existing Cholesky factorization after the factorization phase. The effectiveness of the new algorithm is demonstrated by comparing its performance with that of the existing Cholesky factorization for solving regular finite difference grid problems on hypercube multiprocessors.

Recently, the waveform generalized minimal residual method (WGMRES) was proposed for solving differential-algebraic equations problems. Based on this, several waveform Krylov subspace methods are developed for comparison. Particularly, we propose using an adjoint operator for the waveform bi-conjugate gradient method and the waveform quasi-minimal residual method. The difficulties of developing the adjoint operator will be addressed. Furthermore, these methods are applied to solve a large sparse linear system of ordinary differential equations arising from a parabolic partial differential equation on a DECmpp 12000/Sx parallel computer for comparison. Numerical results show that the WGMRES method and the waveform bi-conjugate gradient stabilized method can achieve better performance than the conventional waveform relaxation methods.