| Автор | La Torre, Salvatore |
| Автор | Napoli, Margherita |
| Автор | Parente, Mimmo |
| Дата выпуска | 2000 |
| dc.description | 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 n <sup>2</sup>, $n \lceil \log n\rceil$, $n\lceil\sqrt n \rceil$ and 2<sup> n </sup> 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. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 2000 |
| Тема | Cellular automata |
| Тема | synchronization. |
| Название | A Compositional Approach to Synchronize Two Dimensional Networks of Processors |
| Тип | research-article |
| DOI | 10.1051/ita:2000130 |
| Electronic ISSN | 1290-385X |
| Print ISSN | 0988-3754 |
| Журнал | RAIRO - Theoretical Informatics and Applications |
| Том | 34 |
| Первая страница | 549 |
| Последняя страница | 564 |
| Аффилиация | La Torre Salvatore; Department of Computer and Information Science, University of Pennsylvania, 200 South 33rd Street, Philadelphia, PA 19104-638, U.S.A.; Dipartimento di Informatica ed Applicazioni, Università degli Studi di Salerno "Renato M. Capocelli", 84081 Baronissi (SA), Italy. |
| Аффилиация | Napoli Margherita; Dipartimento di Informatica ed Applicazioni, Università degli Studi di Salerno "Renato M. Capocelli", 84081 Baronissi (SA), Italy. |
| Аффилиация | Parente Mimmo; Dipartimento di Informatica ed Applicazioni, Università degli Studi di Salerno "Renato M. Capocelli", 84081 Baronissi (SA), Italy. |
| Выпуск | 6 |
