|
1. |
ROUTING AND BROADCASTING ON INCOMPLETE AND GRAY CODE INCOMPLETE HYPERCUBES |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 167-177
IVAN STOJMENOVIĆ,
Preview
|
PDF (258KB)
|
|
摘要:
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
|
2. |
HISTOGRAMMING ON A RECONFIGURABLE MESH COMPUTER* |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 179-190
JING-FU JENQ,
SARTAJ SAHNI,
Preview
|
PDF (251KB)
|
|
摘要:
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
|
3. |
OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 191-209
ÖMER EĞECIOĞLU,
ASHOK SRINIVASAN,
Preview
|
PDF (283KB)
|
|
摘要:
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
|
4. |
MAPPING TREE-STRUCTURED COMPUTATIONS ONTO MESH-CONNECTED ARRAYS OF PROCESSORS |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 211-220
JYH-JONG TSAY,
Preview
|
PDF (188KB)
|
|
摘要:
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
|
5. |
SPEEDUP ANALYSIS OF HYPERCUBE ARRAY PROCESSOR FOR MACHINE VISION APPLICATIONS |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 221-242
MEHMET CELENK,
Preview
|
PDF (267KB)
|
|
摘要:
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
|
6. |
SOLVING THE UPDATED AND DOWNDATED ORDINARY LINEAR MODEL ON MASSIVELY PARALLEL SIMD SYSTEMS |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 243-252
E. J. KONTOGHIORGHES,
M. R. B. CLARKE,
Preview
|
PDF (168KB)
|
|
摘要:
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
|
7. |
P.A.A. CONFERENCE DIARY |
|
Parallel Algorithms and Applications,
Volume 1,
Issue 3,
1993,
Page 253-253
Preview
|
PDF (11KB)
|
|
ISSN:1063-7192
DOI:10.1080/10637199308915445
出版商:Taylor & Francis Group
年代:1993
数据来源: Taylor
|
|