Topological transformations as a tool in the design of systolic networks

Planar graphs; geometric and topological aspects of graph theory (05C10) Cellular automata (computational aspects) (68Q80) Applications of graph theory to circuits and networks (94C15)

Review text

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.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Topological transformations as a tool in the design of systolic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069704)