9 October 2000 Dynamic load balancing of parallel cellular automata
Author Affiliations +
We are interested in running in parallel cellular automata. We present an algorithm which explores the dynamic remapping of cells in order to balance the load between processing nodes. The parallel application runs on a cluster of PCs connected by Fast-Ethernet. A general cellular automaton can be described as a set of cells where each cell is a state machine. To compute the next cell state, each cell needs some information from neighbouring cells. There are no limitations on the kind of information exchanged nor on the computation itself. Only the automaton topology defining the neighbours of each cell remains unchanged during the automaton's life. As a typical example of cellular automation we consider the image skeletonization problem. Skeletonization requires spatial filtering to be repetitively applied to the image. Each step erodes a thin part of the original image. After the last step, only the image skeleton remains. Skeletonization algorithms require vast amounts of computing power, especially when applied to large images. Therefore, skeletonization application can potentially benefit from the use of parallel processing. Two different parallel alogorithms are proposed, one with a static load distribution consisting in splitting the cells over several processing nodes and the other with a dynamic load balancing scheme capable of remapping cells during the program execution. Performance measurements shows that the cell migration doesn't reduce the speedup if the program is already load balanced. It greatly improves the performance if the parallel application is not well balanced.
© (2000) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Marc Mazzariol, Marc Mazzariol, Benoit A. Gennart, Benoit A. Gennart, Roger David Hersch, Roger David Hersch, } "Dynamic load balancing of parallel cellular automata", Proc. SPIE 4118, Parallel and Distributed Methods for Image Processing IV, (9 October 2000); doi: 10.1117/12.403602; https://doi.org/10.1117/12.403602


New approach to the design of a system for feature...
Proceedings of SPIE (August 17 1994)
Multi-Processor For Vision
Proceedings of SPIE (October 14 1987)
New automatic liver segmentation and extraction method
Proceedings of SPIE (November 14 2007)
Parallel DC notch filter
Proceedings of SPIE (December 01 1991)
Real-time system for road following and obstacle detection
Proceedings of SPIE (October 03 1994)

Back to Top