摘要:

This paper presents an alternate quadrant interlocking factorization (A.Q.I.F.) method for the solution of the linear systems that is suitable for S.I.M.D. parallel computers. A.Q.I.E is a variant of Gaussian elimination that works from the middle outward rather than from top down. This factorization generalizes the new quadrant interlocking factorization of M. M. Chawla and K. Passi [1]. This paper includes the proofs of existence of the factorization in the symmetric positive definite and nonsingular diagonally dominant cases. Results of A.Q.I.E method arc compared with quadrant interlocking factorization (Q.I.E) method of D. J. Evans and M. Hatzopoulos [2] and with Gaussian elimination.

ISSN:1063-7192    

DOI:10.1080/10637199408915451

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper we describe a systematic technique for designing parallel algorithms to solve linear systems. Our approach is based on the logic derivation of a target algorithm from specification of basic relations in the linear equations domain and their properties. Both input specification and the resulting algorithm are expressed in the declarative computer-independent form. The methodology is illustrated by deriving the parallel Gaussian triangular solver.

ISSN:1063-7192    

DOI:10.1080/10637199408915452

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

The estimation of spectral density functions for singular Sturm-Liouville problems having continuous spectrum is a computationally intensive task. In this paper we adapt the algorithm from the software package SLEDGE, which was written for serial machines, to a hypcrcube environment.

ISSN:1063-7192    

DOI:10.1080/10637199408915453

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We present in this paper the parallelization of fast matrix multiplication algorithms of Strassen and Wino-grad on MIMD distributed architectures whose interconnection networks are ring and torus. Complexity and efficiency are analyzed and good asymptotic behaviour is proved. These new parallel algorithms are compared with standard algorithms on a 128-processor parallel computer; experiments confirm the theoretical results.

ISSN:1063-7192    

DOI:10.1080/10637199408915454

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

GivenNdata items, this paper presents a parallel sorting algorithm on two-dimensional mesh-connected computers with segmented multiple buses (2-MCCSMB). The algorithm takesO(N1/4) time on anNxN3/42-MCCSMB, while the previous algorithm of Lung [4] takesO(N1/2) time on aN1/2xN1/2two-dimensional mesh-connected computers with multiple buses (2-MCCMB). Further, our algorithm is competitive with the algorithm of Krishnan and Murthy [3] which takesO(N1/3) time and uses anN x N2/32-MCCMB.

ISSN:1063-7192    

DOI:10.1080/10637199408915455

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this article, we present the method of space domain decomposition for the initial-boundary value problem of a class of multidimensional nonlinear parabolic systems. Firstly, by discretization of the timet, we reduce the original problem to the boundary value problem of the nonlinear elliptic systems. Secondly, making use of the Leary-Schauder fixed point theorem, we prove the existence of the solution for this boundary value problem of elliptic type. Finally, applying the prior estimations, we prove the convergence of the semi-discrete solution.

ISSN:1063-7192    

DOI:10.1080/10637199408915456

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this work, we propose parallel FFT algorithms, for medium-to-coarse grain hypercube-connected multicomputers, which are more elegant and efficient than the existing ones. The proposed algorithms achieve perfect load-balance for the efficient simplified-butterfly scheme, minimize the communication overhead by decreasing both the number and the volume of concurrent communications. Communication and computation cannot be overlapped easily due to the strong data dependencies in the FFT algorithm. In this paper, we propose a restructuring for the FIT algorithm which enables overlapping each communication with one fifth of the local computations involved in a stage. Two of the proposed parallel FFT algorithms achieve overlapping by exploiting this restructuring while using the efficient table-lookup scheme for complex coefficients. The proposed algorithms are implemented on an Intel's 32-node iPSC/2 hypercube multicomputer. High efficiency values are obtained even for small size FFT problems.

ISSN:1063-7192    

DOI:10.1080/10637199408915457

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Fast Fourier Transforms (FFTs) are frequently employed in various applications such as image processing and speech recognition. Though FFT calculations can be speeded up considerably, real time processing requirements are well above that of modern day uniprocessor systems. Computing power can be substantially increased through the exploitation of the inherent parallelism available in FFT calculations. However, experimental performance analysis of the Parallel FFT (PFFT) algorithm has not been sufficiently investigated in a loosely coupled multiprocessor environment. In this paper, we evaluate the implementation of a PFFT on a network of T800 series transputers connected in the form of a linear pipeline and a binary cube. We analyse the speedup obtained, taking into account both computation load and communication overhead. A new load balancing algorithm has been incorporated so that load balancing takes into account both computation and communication loads. Realistic performance figures obtained through actual measurements on the system are compared with figures obtained from an analysis of the practical complexity of the implementation.

ISSN:1063-7192    

DOI:10.1080/10637199408915458

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper we propose a simple and elegant distributed self-stabilizing algorithm to solve the all-pairs shortest path problem in graph theory. We have proved the correctness of our algorithm without using a bounded function (which is customary for proving correctness of self-stabilizing algorithms); the new approach is simple and seems to have potential in developing self-stabilizing algorithms for other graph-theoretical problems.

ISSN:1063-7192    

DOI:10.1080/10637199408915459

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper, we introduce a memory storage scheme allowing conflict-free parallel access to rows, columns, square blocks, distributed blocks, and positive and negative diagonals of two dimensional arrays. Unlike the existing schemes, the proposed scheme can be used for an arbitrary number of memory modules and an arbitrary size of matrices. We develop a systematic procedure for the memory allocation based on a placement matrix constructed using circulant matrices. We, also, analyze the data alignment requirements of the proposed scheme, and demonstrate that the data vectors read from memory modules can be aligned for the processors using a set of shift, flip, and shuffle operations, which can be implemented by a data manipulation network.

ISSN:1063-7192    

DOI:10.1080/10637199408915460

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor