Topological transformations as a tool in the design of systolic networks (Q1069704): Difference between revisions

A systolic network, or more generally a computational network (CN), is a formal model of an arbitrary system of parallel processors. It is described by an ordered (generally infinite) digraph with several mappings assigned to its nodes and edges. Some of them express a computational process performed the others can be interpreted as synchronization functions. One of the main notions studied in the paper is the concept of equivalence of two CN's which is defined on the basis of an isomorphism of their space-time diagrams (unrollings). The main tool, a topological transformation of one CN into an equivalent one is used for proving several theorems including systolic conversion theorem. Another important notion describing situations when two CN's performs essentially identical computations is the concept of simulation of one CN on another one. This, as well as the whole article, is illustrated by a number of examples enabling to understand the rather complicated formalism.