Formal methods, language, and tools for the synthesis of cellular automata and architectures

This paper presents methods for mapping deeply parallel algorithms onto architectures of special processors with the mass, spatial and time parallelism. These methods are based on the model of distributed (cellular) calculations called the Algorithm of Parallel Substitutions (APS) and supported by the ALT modeling system. It is typical for the APS to use everywhere and simultaneously the application of instructions (substitutions) to multidimensional data arrays and to explicitly point out the spatial relations among data in instructions. The particular feature of the ALT is the use of graphic and text elements in constructing descriptions of parallel algorithms. The methods are checked by constructing a number of cellular algorithms and structures.