Search

The Parallel Random Access Machine is a very strong model of parallel computing that has resisted cost-efficient implementation attempts for decades. Recently, the development of VLSI technology has provided means for indirect on-chip implementation, but there are different variants of the PRAM model that provide different performance, area and power figures and it is not known how their implementations compare to each others. In this paper we measure the performance and estimate the cost of practical implementations of four PRAM models including EREW, Limited Arbitrary CRCW, Full Arbitrary CRCW, Full Arbitrary Multioperation CRCW on our Eclipse chip multiprocessor framework. Interestingly, the most powerful model shows the lowest simulation cost and highest performance/area and performance/power figures. [ABSTRACT FROM AUTHOR]

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Ω(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n, d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n. [ABSTRACT FROM AUTHOR]

Connected component labeling is a process that assigns unique labels to the connected components of a binary image. The main contribution of this paper is to present a low-latency hardware connected component labeling algorithm for k-concave binary images designed and implemented in FPGA. Pixels of a binary image are given to the FPGA in raster order, and the resulting labels are also output in the same order. The advantage of our labeling algorithm is low latency and to use a small internal storage of the FPGA. We have implemented our hardware labeling algorithm in an Altera Stratix Family FPGA, and evaluated the performance. The implementation result shows that for a 10-concave binary image of 2048 × 2048, our connected component labeling algorithm runs in approximately 70ms and its latency is approximately 750µs. [ABSTRACT FROM AUTHOR]

We investigate the computational power of parallel models with directed reconfigurable buses and with shared memory. Based on feasibility considerations present in the literature, we split these models into "heavyweight" (directed reconfigurable buses, the Combining PRAM, and the BSR) and "lightweight" (all the other PRAMs) and then find that the heavyweight class is strictly more powerful than the lightweight class, as expected. On the other hand, we contradict the long held belief that the heavyweight models form a hierarchy, showing that all of them are identical in computational power with each other. We start the process by showing that the Collision write conflict resolution rule is universal on models with reconfigurable buses (in the sense that complex conflict resolution rules such as Priority and Combining can be simulated with constant overhead by Collision). [ABSTRACT FROM AUTHOR]

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 7.6|Dopt|+1.4, where Dopt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree. [ABSTRACT FROM AUTHOR]