A Compositional Approach to Synchronize Two Dimensional Networks of Processors

Salvatore La Torre; Margherita Napoli; Mimmo Parente

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 6, page 549-564
  • ISSN: 0988-3754

Abstract

top
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 log n , n n 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.

How to cite

top

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 -

References

top
  1. R. Balzer, An 8-states minimal time solution to the firing squad synchronization problem. Inform. and Control10 (1967) 22-42.  Zbl1347.68249
  2. K. Culik, Variations of the firing squad problem and applications. Inform. Process. Lett.30 (1989) 153-157.  Zbl0665.68043
  3. K. Imai and K. Morita, Firing squad synchronization problem in reversible cellular automata. Theoret. Comput. Sci.165 (1996) 475-482.  Zbl0872.68122
  4. K. Imai, K. Morita and K. Sako, Firing squad synchronization problem in number-conserving cellular automata, in Proc. of the IFIP Workshop on Cellular Automata. Santiago, Chile (1998).  Zbl1011.68056
  5. K. Kobayashy, The Firing Squad Synchronization Problem for Two Dimensional Arrays. Inform. and Control34 (1977) 153-157.  
  6. K. Kobayashy, On Time Optimal Solutions of the Two-Dimensional Firing Squad Synchronization Problem, MFCS Workshop On Cellular Automata (1998).  
  7. S. La Torre, M. Napoli and D. Parente, Synchronization of One-Way Connected Processors. Complex Systems10 (1996) 239-255.  Zbl1010.68023
  8. S. La Torre, M. Napoli and D. Parente, Synchronization of a Line of Identical Processors at a Given Time. Fund. Inform.34 (1998) 103-128.  Zbl0908.68005
  9. J. Mazoyer, A six states minimal time solution to the firing squad synchronization problem. Theoret. Comput. Sci.50 (1987) 183-238.  Zbl0635.68042
  10. J. Mazoyer, On optimal solutions to the firing squad synchronization problem. Theoret. Comput. Sci.168 (1996) 367-404.  Zbl0878.68088
  11. F. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1967).  Zbl0195.02402
  12. E.F. Moore, Sequential Machines, Selected Papers. Addison-Wesley, Reading, Mass (1964).  Zbl0147.24107
  13. Y. Nishitani and N. Honda, The firing squad synchronization problem for graphs. Theoret. Comput. Sci.14 (1981) 39-61.  Zbl0454.68041
  14. Z. Roka, The Firing Squad Synchronization Problem on Caley Graphs, in Proc. of MFCS'95. Prague, Czech Republic (1995). Lecture Notes in Comput. Sci.969 (1995) 402-411.  Zbl1193.68170
  15. I. Shinair, Two and Three-Dimensional Firing Squad Synchronization Problems. Inform. and Control24 (1974) 163-180.  Zbl0292.94039
  16. A. Waksman, An optimum solution to the firing squad synchronization problem. Inform. and Control9 (1966) 66-78.  Zbl1111.68527

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.