by S Achasova, O Bandman, V Markova, & S Piskunov

Parallel Substitution Algorithm (PSA) is a new model for distributed (cellular) computations. It provides a concise mapping of distributed computation processes into cellular arrays. A PSA is specified by a set of parallel substitutions operating over a cellular array.

Two concepts make PSA a powerful tool for modelling cellular computations: 1) naming functions which allow the specification of any type of interactions in the computation space, 2) a context which serves to represent control of a computational process in time.

The foundation of PSA theory comprises validity conditions of computations in the synchronous and asynchronous modes, space-time, space-space (2D ⇒ 3D) and global-local equivalent transformations of PSAs, composition and decomposition of PSAs and interpretation of PSAs with automata nets.

On the basis of the PSA theory, a variety of tools and techniques is developed for designing algorithmic-oriented cellular VLSI and optical architectures.

• Parallel Substitution Algorithm:
  • Basic Notions and Definitions
  • PSA Subclasses and Extensions
  • Interpretation of Stationary PSAs by Automata Nets
• Validity of Parallel Substitution Systems:
  • Synchronous and Asynchronous Modes of Execution of Parallel Substitution Systems
  • Validity Conditions of Parallel Substitution Systems
  • Correctness of PSSs with Substitutions of Different Execution Times
• Asynchronous Composition of Parallel Substitution Algorithms:
  • Two Types of Parallel Asynchronous Composition
  • Validity of Asynchronous Composition of PSAs
  • Construction of Composed PSAs
• Equivalent Transformations of PSAs:
  • 2D → 3D PSA Transformation
  • Synchronous–Asynchronous Transformation of PSAs, Space–Time Transformation of PSAs
• PSA Application to Cellular Architecture Design:
  • Computer Simulation of Cellular Computations
  • PSAs and Architectures of 2D Cellular Processors, PSAs and Architectures of 3D Cellular Processors