摘要:

In this paper, by using the asynchronous iteration model presented by Bertsekas [1], a sufficient condition for monotone convergence of asynchronous iterative methods for computing fixed points on a distributed computer is given and the convergence rate shows the asynchronous parallel iterative (method is superior to that of its synchronous counterpart but its communication complexity, however, can be worse. Moreover, by producing a sequence of random vectors, we present a method to simulate an asynchronous parallel environment which can possess arbitrary communication delays like a real distributed computer.

ISSN:1063-7192    

DOI:10.1080/10637199708915583

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

Higher-order L0-stable parallel methods are proposed for the multi-dimensional diffusion equation with constant coefficients. These methods require the application of tridiagonal solvers with complex arithmetic.

ISSN:1063-7192    

DOI:10.1080/10637199708915584

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper presents a novel interprocessor communication network which has been designed to be integrated on a specialized low-cost massively parallel system, PAPRICA-3, featuring 256 single-bit processors arranged as a linear array. This communication network is of basic importance in the implementation of communications among processors not directly connected, and can solve efficiently problems involving non-local exchange of information such as image transforms, seed-propagation, labeling of connected components, or the handling of hierarchical data structures.

ISSN:1063-7192    

DOI:10.1080/10637199708915585

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper presents a systolic design for flexible string matching. Initially a sequential algorithm is discussed which consists of two phases, i.e. pre-processing and searching, and a matrix vector notation of the algorithm is proposed. Then, starting from the computational schedule of the searching phase a systolic algorithm is derived which can be realised directly onto a special purpose VLSI processor array architecture for string matching. Further the pre-processing phase is also accommodated onto the same VLSI design. Finally extensions to approximate pattern matching are discussed.

ISSN:1063-7192    

DOI:10.1080/10637199708915586

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

We present a parallelization of Parlett's algorithm for computing arbitrary functions of upper triangular matrices. The parallel algorithm preserves the numerical stability properties of the serial algorithm, and is suitable for implementation on coarse-grain parallel computers. Our experiments on a 16-processor Meiko CS-2 multiprocessor indicate that the algorithm obtains nearly constant efficiency (linear speedup) for small number of processors and for matrices of size greater than 500.

ISSN:1063-7192    

DOI:10.1080/10637199708915587

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

The Modified Covariance method of spectral estimation, proposed as a replacement of the conventional short term Fourier transform for use with pulsed Doppler ultrasound blood flow detectors in order to improve time/frequency resolution, is computationally far more demanding. The use of an application specific architecture for real-time implementation is of interest. A cost/benefit selection of systolic arrays, firstly for a matrix solution method with suitable bus width and secondly for calculation of covariance matrix elements, led to the choice of Cholesky matrix decomposition, 12 bit bus width and a bi-linear systolic array designed using a data dependence graph method.

ISSN:1063-7192    

DOI:10.1080/10637199708915588

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper presents bulk-synchronous parallel (BSP) algorithms for linear system solving through QR and QZ factorisation. The two new algorithms are analysed in terms of the BSP cost model, and portable implementations of the QR and QZ decomposition methods are devised using the Oxford BSP Library. The experimental results obtained on a shared-memory multiprocessor accurately match the theoretical predictions, permitting a thorough comparison of the two algorithms.

ISSN:1063-7192    

DOI:10.1080/10637199708915589

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

We set up a class of multi-parameter relaxed parallel matrix multisplitting methods for solving the linear complementarity problems on the SIMD multiprocessor systems. This class of methods can not only includes all the existing relaxed methods for the linear complementarity problems, but also can yields a lot of novel ones in the sense of multisplitting. Thus, it is reasonably general. We set up the convergence theory of these relaxed methods under the condition that the system matrix is an H-matrix with positive diagonal elements.

ISSN:1063-7192    

DOI:10.1080/10637199708915590

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

With the expanding role of computers in society, some assumptions underlying well known theorems in the theory of parallel computation no longer hold universally. In particular, the speedup theorem and Brent's theorem do not apply to dynamic computers that interact with their environment. The phenomenon of a disproportionate decrease in execution time ofP2over p1processors for p2> p1is referred to as superunitary speedup. An analogous phenomenon that we call superunilary 'success ratio’ occurs in dealing with tasks that can either succeed or fail, when there is a disproportionate increase in the success of p2 over p1 processors executing a task. We identify a range of conditions that may lead to superunitary speedup or success ratio, and propose several new paradigms for problems that admit such superunitary behaviour. Our results suggest that a new theory of parallel computation may be required to accommodate these new paradigms.

ISSN:1063-7192    

DOI:10.1080/10637199708915591

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper describes the parallelisation of a state estimator with confidence limit analysis. State estimation involves the optimal fitting of an overdetermined set of measurements to the corresponding values calculated from the mathematical model of the system. The inaccuracies associated with measurements lead to discrepancies within the state estimate. Consequently for the state estimation algorithm to be of practical use it needs to quantify the effect of these discrepancies in the form of state confidence limits [2], However, the quasi-quadratic numerical complexity of the state estimation algorithms suggests a need for parallel implementation of the probabilistic state estimation, so that the real-time performance may be maintained also for large-scale systems. The algorithm is based on the idea of ‘tearing’ the original system into subsystems and then coordination of the resulting subsystem solutions. The algorithm has been tested in the context of water distribution systems state estimation.

ISSN:1063-7192    

DOI:10.1080/10637199708915592

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor