摘要:

AbstractThis paper investigates the use of large grain size multi‐computers for solving low‐ and intermediate‐level computer vision problems. The realization of a general multi‐resolution framework requiring a two‐dimensional grid of communicating processors is analysed, and the resulting speed‐up and total solution time as a function of software and hardware parameters is presented. The scheme is then specialized for two significant problems: surface reconstruction and optical flow. While the first can be solved with the standard full multigrid approach, the second requires an adaptive grid determined by a local decision: the appropriate resolution for different parts of the image is tuned in order to minimize the error in the coefficients of the differentia

ISSN:1040-3108    

DOI:10.1002/cpe.4330030202

出版商:John Wiley&Sons, Ltd    

年代:1991

数据来源: WILEY

摘要:

AbstractWe give two parallel algorithms for sequence comparison on the Connection Machine 2 (CM‐2). The specific comparison measure we compute is theedit distance: given a finite alphabet ∑ and two input sequencesXϵ ∑+andYϵ ∑+the edit distanced(X,Y)is the minimum cost of transformingXintoYvia a series of weighted insertions, deletions and substitutions of characters. The edit distance comparison measure is equivalent to or subsumes a broad range of well known sequence comparison measures.The CM‐2 is very fast at performing parallel prefix operations. Our contribution consists of casting the problem in terms of these operations. Our first algorithm computesd(X,Y)usingNprocessors andO(M S)time units, whereM= min(|X|,||Y|) + 1,N= max(|X|,|Y|) + 1 andSis the time required for a parallel prefix operation. The second algorithm computesd(X,Y)usingNMprocessors andO((logNlogM)(S+R)) time units, whereRis the time for a ‘router’ communication step—one in which each processor is able to read data, in parallel, from the memory of any other processor. Our algorithms can also be applied to several variants of the problem, such as subsequence comparisons, and one—many and many‐many comparisons on

ISSN:1040-3108    

DOI:10.1002/cpe.4330030203

出版商:John Wiley&Sons, Ltd    

年代:1991

数据来源: WILEY

摘要:

AbstractWe describe a benchmark parallel version of the Van Slyke and Wets (1969) algorithm for two‐stage stochastic programs and an implementation of that algorithm on the Sequent/Balance. We also report results of a numerical experiment using random test problems and our implementation. These performance results, to the best of our knowledge, are the first available for the Van Slyke and Wets (1969) algorithm on a parallel processor. They indicate that the benchmark implementation parallelizes wel

ISSN:1040-3108    

DOI:10.1002/cpe.4330030204

出版商:John Wiley&Sons, Ltd    

年代:1991

数据来源: WILEY

摘要:

AbstractMonte Carlo cluster update algorithms are extremely efficient for simulating spin models near their phase transitions, where local update algorithms suffer severe critical slowing down. Unfortunately, as the cluster algorithms are highly irregular as well as nonlocal, they are much more difficult to parallelize efficiently. The main difficulty lies in identifying which spins belong to which cluster. In this paper we investigate a number of cluster identification algorithms, both sequential and parallel, which we have implemented on serial, SIMD and MIMD computers.

ISSN:1040-3108    

DOI:10.1002/cpe.4330030205

出版商:John Wiley&Sons, Ltd    

年代:1991

数据来源: WILEY

ISSN:1040-3108    

DOI:10.1002/cpe.4330030201

出版商:John Wiley&Sons, Ltd    

年代:1991

数据来源: WILEY