Share Email Print

Proceedings Paper

Dynamic load balancing of parallel cellular automata
Author(s): Marc Mazzariol; Benoit A. Gennart; Roger David Hersch
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 9 October 2000
PDF: 9 pages
Proc. SPIE 4118, Parallel and Distributed Methods for Image Processing IV, (9 October 2000); doi: 10.1117/12.403602
Show Author Affiliations
Marc Mazzariol, Ecole Polytechnique Federale de Lausanne (Switzerland)
Benoit A. Gennart, Ecole Polytechnique Federale de Lausanne (Switzerland)
Roger David Hersch, Ecole Polytechnique Federale de Lausanne (Switzerland)

Published in SPIE Proceedings Vol. 4118:
Parallel and Distributed Methods for Image Processing IV
Hongchi Shi; Patrick C. Coffield; Divyendu Sinha, Editor(s)

© SPIE. Terms of Use
Back to Top