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 one-dimensional) 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 two-dimensional, hence every symbol is written in one CA cell), is supported by one-dimensional sorting. The complexity of algorithms is linear. CA of one-dimensional sorting by the state of a cell using the structure, which is called “bit-symbol”. CA of two-dimensional sorting using the structure, which is called “trit-trit-symbol”, 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 “bit-bit-symbol-symbol”. 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. 77-81.
URL of paper
	http://www.mes-conference.ru/data/year2016/pdf/D031.pdf