Issue |
RAIRO-Theor. Inf. Appl.
Volume 34, Number 6, November/December 2000
|
|
---|---|---|
Page(s) | 549 - 564 | |
DOI | https://doi.org/10.1051/ita:2000130 | |
Published online | 15 April 2002 |
A Compositional Approach to Synchronize Two Dimensional Networks of Processors
1
Department of Computer and Information Science,
University of Pennsylvania, 200 South 33rd Street, Philadelphia, PA 19104-638, U.S.A.
2
Dipartimento di Informatica ed Applicazioni,
Università degli Studi di Salerno "Renato M. Capocelli", 84081 Baronissi (SA),
Italy.
Received:
10
August
2000
Accepted:
16
February
2001
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, ,
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.
Mathematics Subject Classification: 37B15
Key words: Cellular automata / synchronization.
© EDP Sciences, 2000
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.