摘要:

We propose new deadlock-free routing and broadcasting algorithms for incomplete hypercube network that have optimal communication and computation time. Broadcasting algorithm may run on one-port communication model of hypercube and is suitable for both the asynchronous (MIMD, or distributed) and synchronous (SIMD, or parallel) hypercube models. Routing and broadcasting procedures have optimal distance paths between any two nodes. We then introduce a new model of computation, Gray code incomplete hypercube (GCIH), which is an interval of nodes of hypercube in Gray code order, and obtain similar results for the new model.

ISSN:1063-7192    

DOI:10.1080/10637199308915439

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

We develop efficient reconfigurable mesh (RMESH) algorithms to compute the histogram of an image and to perform histogram modification. The histogram of anN × Nimage is computed by anN × NRMESH inO(√Blog√B(N/√B) forB < N,O(√N) forB = N, andO(√B) forN < B ≤ N2.Bis the number of gray scale values. Histogram modification is done inO(√N) time by anN × NRMESH.

ISSN:1063-7192    

DOI:10.1080/10637199308915440

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

Algorithms for efficient implementation of computation of prefix produce on mesh-connected processor arrays are presented. Assuming that an arithmetic operation takes unit time and communication/computation ratio for a single input item isτ, we show that the prefixes ofnitems can be computed in time 2τ√n + O(logn) on a square mesh withnprocessors. Ifnprocessors are configured as a disc with respect to the Manhattan metric, then the parallel time for the problem becomes √2τ√n + O(√τ4√n. We show that both of these algorithms are asymptotically optimal.

ISSN:1063-7192    

DOI:10.1080/10637199308915441

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

This paper shows how to parallelize tree-structured computations ford-dimensional (d ≥ 1) mesh-connected arrays of processors. A tree-structured computationTconsists ofncomputational tasks whose dependencies form a task treeTofnconstant degree nodes. Each task can be executed in unit time, and sends one value to its parent task after it has executed. Lethbe the height ofT. We present linear time algorithms for partitioning and mapping the task treeTonto ap1/d × … × p1/dmesh-connected array of processors so that we can schedule the processors to perform computationTinO(n/p) time, forp ≤ min{n/h,nd/(d + 1)}. TheO(max{h,n1/(d+1)}) time bound achieved whenp = min{n/h,nd/(d + 1)} is the best possible (upto a constant factor) over allp ≥ 1. The best previous bound wasO((√n + h) · logn) achieved on a linear array of min{n/h,n1/2} processors, and could not be generalized to higher dimensional meshes. As a consequence, we obtain a mapping and schedule of ann-node expression tree of associative operators over ap1/d × … × p1/dmesh-connected processor array, which evaluates the expression tree inO(n/p) time, forp ≤ nd/(d + 1)

ISSN:1063-7192    

DOI:10.1080/10637199308915442

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

Several low-level vision algorithms have been implemented on a 16-node hypercube processor (AMETEK S-14) by exploitation of its network embedding feature. This includes edge detection with the Sobel operator, histogramming, one-pass parallel binary image thinning, and noise-cleaning. The primary objective is to parallelize these algorithms by achieving a proper image-to-processor topology mapping and to determine the actual speedup factor of parallel implementation over the sequential programming. Two basic topologies used are the ring and the nearest-neighbor networks, which are mapped onto the hypercube system.

ISSN:1063-7192    

DOI:10.1080/10637199308915443

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

Several algorithms have appeared for solving the Ordinary Linear Model (OLM), after a number of observations have been added or deleted. In this paper we employ Householder transformations and Givens rotations to solve the updated and downdated OLM, using a massively parallel SIMD computer. Some of our methods are modified versions of serial algorithms published previously while others appear for the first time. The execution time models of all algorithms are studied and compared.

ISSN:1063-7192    

DOI:10.1080/10637199308915444

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

ISSN:1063-7192    

DOI:10.1080/10637199308915445

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor