A 1D cellular automaton that moves particles until regular spatial placement

Luidnel Maignan 1, * Frédéric Gruau 1, 2
* Auteur correspondant
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, LRI - Laboratoire de Recherche en Informatique
Abstract : We consider a finite cellular automaton with particles where each site can host at most one particle. Starting from an arbitrary initial configuration, our goal is to move the particles between neighbor sites until the distance to the nearest particle is minimized globally. Such a configuration corresponds in fact to a regular placement. This problem is a cellular automata equivalent of load-balancing in parallel computing, where each task is a particle and each processor a connected set of sites. We present a cellular automata rule that solves this problem in the 1D case, and is convergent, i.e. once the regular placement is achieved, the configuration does not change anymore. The rule is inspired from the Lloyd algorithm, computing a centroidal Voronoi tessellation. The dynamic of the rule is described at a higher level, using self-explanatory space-time diagrams. They exhibit signals acting as quantity of movement carrying the energy of system. Each signal bounces or pass through particles, causing their movement, until it eventually reaches the border and vanishes. When signals have all vanished, particles are regularly placed.
Type de document :
Article dans une revue
Parallel Processing Letters, World Scientific Publishing, 2009, 19 (2), pp.315--331
Liste complète des métadonnées

Contributeur : Frederic Gruau <>
Soumis le : lundi 29 novembre 2010 - 22:56:57
Dernière modification le : jeudi 24 mai 2018 - 15:59:23


  • HAL Id : inria-00541142, version 1



Luidnel Maignan, Frédéric Gruau. A 1D cellular automaton that moves particles until regular spatial placement. Parallel Processing Letters, World Scientific Publishing, 2009, 19 (2), pp.315--331. 〈inria-00541142〉



Consultations de la notice