Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
An Isotropic Optimum-Time FSSP Algorithm for Two-Dimensional Cellular Automata
verfasst von : Hiroshi Umeo, Keisuke Kubo, Yusuke Takahashi
Erschienen in: Parallel Computing Technologies
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata, known as firing squad synchronization problem (FSSP), has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed for not only one-dimensional but two-dimensional arrays. In the present paper, we propose a new recursive-halving based optimum-time synchronization algorithm that can synchronize any rectangle two-dimensional (2D) arrays of size
m
×
n
with a general at one corner in
m
+
n
+ max (
m
,
n
) − 3 steps. The algorithm proposed is quite different from previous designs and it can be easily generalized to 2D arrays with a general at any position of the array. The algorithm is isotropic concerning the side-lengths of 2D arrays and its correctness is transparent and easily verified.