A Compositional Approach to Synchronize Two Dimensional Networks of Processors

La Torre, Salvatore, Napoli, Margherita, and Parente, Mimmo. "A Compositional Approach to Synchronize Two Dimensional Networks of Processors." RAIRO - Theoretical Informatics and Applications 34.6 (2010): 549-564. <http://eudml.org/doc/222098>.

@article{LaTorre2010,
abstract = { The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of m rows and n columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of (n × n) processors and give some general constructions to synchronize arrays of (m × n) processors. Algorithms are given to synchronize in time n2, $n \lceil \log n\rceil$, $n\lceil\sqrt n \rceil$ and 2n a square array of (n × n) processors. Our approach is a modular description of synchronizing algorithms in terms of "fragments" of cellular automata that are called signals. Compositional rules to obtain new signals (and new synchronization times) starting from known ones are given for an (m × n) array. Using these compositional rules we construct synchronizations in any "feasible" linear time and in any time expressed by a polynomial with nonnegative coefficients. },
author = {La Torre, Salvatore, Napoli, Margherita, Parente, Mimmo},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Cellular automata; synchronization.; cellular automata},
language = {eng},
month = {3},
number = {6},
pages = {549-564},
publisher = {EDP Sciences},
title = {A Compositional Approach to Synchronize Two Dimensional Networks of Processors},
url = {http://eudml.org/doc/222098},
volume = {34},
year = {2010},
}

TY - JOUR
AU - La Torre, Salvatore
AU - Napoli, Margherita
AU - Parente, Mimmo
TI - A Compositional Approach to Synchronize Two Dimensional Networks of Processors
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 6
SP - 549
EP - 564
AB - The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of m rows and n columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of (n × n) processors and give some general constructions to synchronize arrays of (m × n) processors. Algorithms are given to synchronize in time n2, $n \lceil \log n\rceil$, $n\lceil\sqrt n \rceil$ and 2n a square array of (n × n) processors. Our approach is a modular description of synchronizing algorithms in terms of "fragments" of cellular automata that are called signals. Compositional rules to obtain new signals (and new synchronization times) starting from known ones are given for an (m × n) array. Using these compositional rules we construct synchronizations in any "feasible" linear time and in any time expressed by a polynomial with nonnegative coefficients.
LA - eng
KW - Cellular automata; synchronization.; cellular automata
UR - http://eudml.org/doc/222098
ER -