A new methodology named CALMANT (CC-cube algorithms on Meshes and Ton) for mapping a kind of algorithms that we call CC-cube algorithm onto multicomputers with hypercube, mesh, or torus interconnection topology is pro...
详细信息
A new methodology named CALMANT (CC-cube algorithms on Meshes and Ton) for mapping a kind of algorithms that we call CC-cube algorithm onto multicomputers with hypercube, mesh, or torus interconnection topology is proposed. This methodology is suitable when the initial problem can:be expressed as a set of processes that communicate through a hypercube topology (a CC-cube algorithm). There are many important algorithms that fit into the CC-cube type. CALMANT is based on three different techniques: a) the standard embedding to assign the processes of the algorithm to the nodes of the mesh multicomputer;b) the communication pipelining technique to increase-the level of communication parallelism inherent in the CC-cube algorithms;and c) optimal message-scheduling algorithms proposed in this work in order to avoid conflicts and minimizing in this way the communication time. Although CALMANT is proposed for multicomputers with different interconnection network topologies, this paper only focuses on the particular case of meshes.
This paper describes parallel algorithms for the following operations on quadtrees-boolean operations (union, intersection, complement), collapsing a quadtree, and neighbor finding in an image represented by a quadtre...
详细信息
This paper describes parallel algorithms for the following operations on quadtrees-boolean operations (union, intersection, complement), collapsing a quadtree, and neighbor finding in an image represented by a quadtree. The architecture assumed in this paper is a hypercube with one processing element (PE) per hypercube node. It is assumed that the architecture is SIMD. i.e. all PEs work under the control of a single control unit.
We present parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing. These algorithms achieve linear speedups ...
详细信息
We present parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles, for any number p of processors satisfying 1 less-than-or-equal-to p less-than-or-equal-to n/((log3 n)(10 log n)2), where n is the input size. The lower bound results are established under no restriction on how the input is mapped into the local memories of the different processors.
Consider a n x n binary image. Given a direction D, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the...
详细信息
Consider a n x n binary image. Given a direction D, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the image) in direction D from infinity. A related problem, referred to as point visibility, is to compute for each pixel the portion that is visible from a given point p. In this paper, we derive O(log n) time SIMD algorithms for each of these two problems on the hypercube, where one processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in a n2-processor hypercube is 2 log n, it follows that both of the above algorithms are asymptotically optimal.
Sparse arrays are arrays in which the number of non-zero elements is a small fraction of the total number of array elements. Parallel algorithms are presented using sparse representations for arrays. It is shown that ...
详细信息
Sparse arrays are arrays in which the number of non-zero elements is a small fraction of the total number of array elements. Parallel algorithms are presented using sparse representations for arrays. It is shown that adopting such a representation not only reduces the processor/space requirement, but also provides efficient load balancing at no increase in time complexity. New parallel primitives needed to work with such a representation are defined. Sample algorithms from the areas of image processing and computer vision are presented. Alternative schemes for dealing with arrays containing large contiguous blocks of elements with identical array values are considered. The parallel architecture considered is a strict SIMD hypercube, and the applicability of the results presented to other architectures is described.
We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n x n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also ...
详细信息
We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n x n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here, n is the number of squares in the MAT, and the algorithms use O(n2) processors.
暂无评论