We describe two simple optimal-work parallelalgorithms for sorting a list £ = (X1, x2,....,Xm) of m strings over an arbitrary alphabet Σ, where Σi=1m|Xi | = n. the first algorithm is a deterministic algorithm ...
详细信息
ISBN:
(纸本)0818656026
We describe two simple optimal-work parallelalgorithms for sorting a list £ = (X1, x2,....,Xm) of m strings over an arbitrary alphabet Σ, where Σi=1m|Xi | = n. the first algorithm is a deterministic algorithm that runs in O(log log m/log(2)m) time and the second is a randomized algorithm that runs in O(log m) time. Bothalgorithms use O(m log m + n) operations.
In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficien...
详细信息
ISBN:
(纸本)0818656026
In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.
We present SIMD hypercube algorithms for transforming between any pair of the following binary image representations: boundary codes, quadtrees, and run length codes. Unlike previous parallelalgorithms, ours do not h...
详细信息
ISBN:
(纸本)0818656026
We present SIMD hypercube algorithms for transforming between any pair of the following binary image representations: boundary codes, quadtrees, and run length codes. Unlike previous parallelalgorithms, ours do not have restrictions on the shape of the images. In particular, our algorithms allow holes in the image regions. We believe that our algorithm for transformation from quadtrees to boundary codes is the first such algorithm on the SIMD hypercube. the algorithms for transforming between boundary codes and quadtrees are modified to work for the transformations between these representation and run length codes.
this work deals with evaluation of hardware implementations of image processingalgorithms for real time applications, using SRAM based Field Programmable Gate Arrays. We discuss a generic architectural model adapted ...
详细信息
We have studied a variety of switch architectures for use in the multistage interconnection network of a shared memory multiprocessor. In this paper, we investigate two techniques for improving network performance in ...
详细信息
ISBN:
(纸本)0818656026
We have studied a variety of switch architectures for use in the multistage interconnection network of a shared memory multiprocessor. In this paper, we investigate two techniques for improving network performance in the presence of contention: the use of multiple handshaking signals and the use of message combining. Simulation results are provided for implementation alternatives using switches of varying capabilities, in order to compare the effectiveness of different methods. We show that a practical combining switch design, the two-and-a-half-way combining switch, provides performance equivalent to that of other more expensive designs for systems with up to 1024 PEs.
this paper describes several algorithms to perform all-to-all communication on a two-dimensional mesh connected computer with wormhole routing. We discuss both direct algorithms, in which data is sent directly from so...
详细信息
ISBN:
(纸本)0818656026
this paper describes several algorithms to perform all-to-all communication on a two-dimensional mesh connected computer with wormhole routing. We discuss both direct algorithms, in which data is sent directly from source to destination processor, and indirect algorithms in which data is sent through one or more intermediate processors. We propose algorithms for both power-of-two and non power-of-two meshes as well as an algorithm which works for any arbitrary mesh. We have developed analytical models to estimate the performance of the algorithms on the basis of system parameters. Performance results obtained on the Intel Touchstone Delta are compared withthe estimated values.
Matching is an important pari of a model-based object recognition system. Matching is a difficult task, for a number of reasons. First, in a number of recognition systems matching is formulated as a combinatorial prob...
详细信息
Concepts and algorithms from a generalization of the stable marriage problem are used to optimally match machine features to task computational requirements in heterogeneous processing. Given bilateral group-to-group ...
详细信息
ISBN:
(纸本)0818656026
Concepts and algorithms from a generalization of the stable marriage problem are used to optimally match machine features to task computational requirements in heterogeneous processing. Given bilateral group-to-group linear preference order and a linear objective function, we can always find a one-to-one matching of machines and tasks in which no machine and task jointly prefer each other to their current assignments (stability). Among such matchings, there is one which is optimal with regard to the objective function. the algorithms to find it have polynomial-time complexity. Goals such as the majority assignment, Pareto efficiency and static load-balancing are achieved simultaneously.
parallelalgorithms for lossless data compression via dictionary compression using the longest fragment first (LFF) and greedy parsing strategies are described. Dictionary compression removes redundancy by replacing s...
详细信息
ISBN:
(纸本)0818656026
parallelalgorithms for lossless data compression via dictionary compression using the longest fragment first (LFF) and greedy parsing strategies are described. Dictionary compression removes redundancy by replacing substrings of the input by references to strings stored in a dictionary. Given a static dictionary stored as a suffix tree, we present PRAM CREW algorithms for LFF compression which run in O(log2n) time with O(n/log n) processors where it is assumed that the maximum dictionary entry is of length O(log n). We also describe a logarithmic time and linear processor algorithm for greedy parsing.
Non-wave shaping parallel bidirectional heuristic search algorithms have been reported to suffer of the bidirectional search anomaly. Although wave-shaping is considered as the most natural approach, parallel bidirect...
详细信息
ISBN:
(纸本)0818656026
Non-wave shaping parallel bidirectional heuristic search algorithms have been reported to suffer of the bidirectional search anomaly. Although wave-shaping is considered as the most natural approach, parallel bidirectional wave-shaping algorithms are extremely scare. We introduce a wave-shaping algorithm for parallel bidirectional heuristic search in distributed memory environments. the method is inspired by the celebrated uniprocessor bidirectional wave-shaping algorithm of DeChampeaux-Sint. Our performance evaluation shows that the proposed method scales well, maintains good performance for increasing problem sizes, and attains close to linear speedup over the sequential DeChampeaux-Sint algorithm.
暂无评论