Synchronous-asynchronous transformation of cellular algorithms

Asynchronous versus synchronous cellular computations are investigated in terms of Parallel Substitution Algorithm (a formal model of fine-grained parallel data processing). A general method for constructing asynchronous cellular computation equivalent to a given cellular algorithm execution is presented. It is shown that more than a twofold increase in cell-complexity should be paid for the abandonment of synchronizing clock in cellular VLSI systems.