Home
Authors Papers Year of conference Themes Organizations To MES conference
Algorithms of the parallel computations in the formalization of cellular automata: the sorting of strings and the multiplication of numbers by Atrubin’s method 
 


Authors 
 Matyushkin I.V. 
Date of publication 
 2016 

Abstract 
 Clear statements in the language of cellular automata (CA) are given for the algorithms of parallel sorting. We have no found such statements in literature during visible time in view of relative elementary nature of tasks. The sorting by the array of symbols (we call it onedimensional) is supported by bubble method and famous Margolus automaton. The sorting by the array of strings, which demand the regulation of words (we call it twodimensional, hence every symbol is written in one CA cell), is supported by onedimensional sorting. The complexity of algorithms is linear. CA of onedimensional sorting by the state of a cell using the structure, which is called “bitsymbol”. CA of twodimensional sorting using the structure, which is called “trittritsymbol”, i. e., two flags (blockiness and comparison), each of them have three states, is joined to data symbol.
We improve the algorithm of two natural numbers multiplication (in numerical system, which base is N) that first time formulated by Atrubin in 1965 for binary notation. This algorithm demands five registers of processor, because it was primarily adapting to the systolic array of processors. In spite of adaption to the CA language introduced algorithm demands four components instead of five, namely the structure, which is called “bitbitsymbolsymbol”. Our algorithm differs from Atrubin’s multiplier in the next aspects: 1) in an initial state the numbers is considered like it introduced in the data string (second component); 2) the numbers of one data moves through the numbers of another; 3) answer string is dynamically changing and corresponds to output signal of Atrubin processors. 
Keywords 
 parallel computations, cellular automata, algorithm, multiplication, sorting, Atrubin’s multiplier 
Library reference 
 Matyushkin I.V. Algorithms of the parallel computations in the formalization of cellular automata: the sorting of strings and the multiplication of numbers by Atrubin’s method // Problems of Perspective Micro and Nanoelectronic Systems Development  2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 4. P. 7781. 
URL of paper 
 http://www.mesconference.ru/data/year2016/pdf/D031.pdf 

