Cellular Automata Computational Parallelism of Elementary Matrix Operations

Matyushkin I.V., Zapletina M.A. (IPPM RAS)
Abstract - The algorithms of strict classical cellular automata formalization with initial states declaration, local rule and neighborhood definitions for some elementary operations on vectors and matrices in the requirements of mass parallelism are presented. The dynamics of cellular automata field state is presented clearly. Among the tasks are the unary element operation, the matrix reflection and transposition. The origi-nal solutions meet the more stringent parallelization condi-tions for a computer with the cellular automata architecture in compare to traditional methods. There is no attachment to concrete hardware model that makes the represented algo-rithms more universal. The methods for matrix reflecting and transposition introduce special global break criteria based on compositions of flags states of local cells and their first-order neighbors. The break on cellular automata state invariance was considered. All the algorithms have the complexity according to the linear dimension of the matrix.

Keywords - cellular automata, matrix operations, linear algebra, parallel computing, non-traditional architectures.

Клеточно-автоматный вычислительный параллелизм элементарных матричных операций

Матюшкин И.В., Заплетина М.А. (Институт проблем проектирования в микроэлектронике РАН, г. Зеленоград)
Аннотация - Представлены алгоритмы классической клеточно-автоматной формализации для некоторых элементарных операций над векторами и матрицами: унарной поэлементной операции, задач отражения и транспонирования матрицы – в требованиях массового параллелизма, более жестких по сравнению с крупно-зернистым параллелизмом. Все алгоритмы имеют линейную по размеру матрицы сложность.

Ключевые слова - клеточные автоматы, матрицы, линейная алгебра, параллельные вычисления, нетрадиционные архитектуры.