Research Group:

Cellular Algorithms and Architectures

Head of the Group: O.Bandman, Doctor of Sciences.

A research group for fine-grained parallelism and cellular architecture study consists of four researchers and works as a part of the Parallel Algorithms and Architecture Laboratory. The main research goal is to develop fundamental concepts, formal methods and computer tools for designing algorithmic oriented architecture for data array processing.

A formal model called Parallel Substitution Algorithm (PSA) has been proposed, which conceptually ascends to fon-Neumann cellular automaton, but has more powerful expressive capability.

The main peculiarities of the model are the following:

  1. in that computation space it is introduced in explicit form so that the structure of intercell exchanges is expressed in the form of functions determined in this space,
  2. the concept of context allows to express the controlling function directly in the representation of the algorithm. Based on PSA concepts a theory has been developed which comprise the correctness conditions, equivalent transformations and a number of methods for algorithm and architecture synthesis. A computer simulation system was elaborated, which allows to construct cellular algorithms and observe computation processes in dynamics.

The following researches and projects are under way:

Main project: "Formal model of distributed computing /parallel substitution algorithms/" (Supported by the Russian Foundation of Fundamental Research under grant N93-01-01000).


Last update: October 18, 1997