Dynamic load balancing of parallel cellular automata

Marc Mazzariol; Benoit A. Gennart; Roger David Hersch

doi:10.1117/12.403602

9 October 2000 Dynamic load balancing of parallel cellular automata

Marc Mazzariol, Benoit A. Gennart, Roger David Hersch

Proceedings Volume 4118, Parallel and Distributed Methods for Image Processing IV; (2000) https://doi.org/10.1117/12.403602
Event: International Symposium on Optical Science and Technology, 2000, San Diego, CA, United States

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.

Citation Download Citation

Marc Mazzariol, Benoit A. Gennart, and Roger David Hersch "Dynamic load balancing of parallel cellular automata", Proc. SPIE 4118, Parallel and Distributed Methods for Image Processing IV, (9 October 2000); https://doi.org/10.1117/12.403602

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available