摘要:

We present efficient algorithms for the nearest neighbor problem defined in an n × n binary image. We show that using a linear array with a reconfigurable pipelined bus system (LARPBS) of n2processors, the nearest neighbor problem can be solved in O(loglogn) time, and using an LARPBS of n2+εprocessors, for any fixed constant ε>0. the nearest neighbor problem can be solved in O(l) time. We also show that the nearest neighbor problem can be solved on an LARPBS of n2processors in O(1) time with high probability.

ISSN:1063-7192    

DOI:10.1080/01495739808947358

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

We design linear time systolic-based parallel algorithms that run on two-dimensional arrays for both computing the length and recovering a longest common subsequence of three given sequences that are appropriate for very large-scale integration (VLSI) implementation. These problems have been qualified to be difficult to be solved in linear time in [14], and our approach, which generalizes the methods used for determining a longest common subsequence of two strings [28,38] to the case of three strings, enables to solve both problems in linear time. Given the three sequences A, B and C of length n, m and l (n ≤ m ≤ l;), we provide an algorithm that computes the length p of their longest common subsequence on a modular I/O bounded one-way two-dimensional array of nm processors in n + 2m + l− 1 time-steps. To compute a longest common subsequence of the three given strings, we show that each processor of the above array requires an O(min{n,p\) local storage to solve the problem in In + 1m + 1 + p — 2 time-steps.

ISSN:1063-7192    

DOI:10.1080/01495739808947359

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

This paper describes nPSA, a parallel algorithm for distributed asynchronous simulation of digital circuits with nominal delays in a massively parallel SIMD environment. Glitch detection and suppression are included, together with a discussion of other factors, such as recon-vergent fan-out and feedback lines. A new set of metrics is also proposed for evaluation purposes. nPSA combines demand-driven and deadlock avoidance protocols in order to deliver high performance compared to typical synchronous parallel simulators. Although its performance greatly depends on the quality of circuit embedding on the host machine, nPSA is independent of the computer architecture and communication protocol used.

ISSN:1063-7192    

DOI:10.1080/01495739808947360

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

In this paper we present two parallel versions of bisection method to compute the spectrum of symmetric Toeplitz matrices. Both parallel algorithms have been implemented and analysed on a virtual shared memory multiprocessor using a portable message-passing environment. The algorithms very efficiently parallelize the sequential method, and the application of a dynamic strategy to distribute the computations produces better results than the use of a static method. We also improve the performance of the original sequential algorithm by applying Newton's method for the final approximation of the eigenvalues. However, the bad results of the sequential algorithm produce low speedups when we compare the parallel methods with the best available sequential algorithm.

ISSN:1063-7192    

DOI:10.1080/01495739808947361

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor