The parallel architectures of computing systems, including the massively parallel ones, attract a particular interest of modern researchers in the theoretical informatics field. In this connection the hardware or algorithmic acceleration of the interprocessor exchange becomes the main objective. One of the approaches to creation of algorithms can be the use of nonconventional formalism-neural networks or cellular automata (CA), to realize the model of near interaction of elementary calculators. In the work three operations with matrix data have been considered: unary, reflection, transposing. The operations have been realized by parallel algorithms in the formalism of the cellular automata in an assumption that the data had been loaded into CA before the calculation. It has been shown that all presented algorithms have linear complexity of the matrix size. Movement and modification of the data have been executed by means of introducing the bit or/and trit flag components into a cell state description. The calculation stop-conditions are the occurrence of a stop-condition of a special CA cell or of all cells of the CA field, i.e. their «freezing». The development of the cellular automata algorithmization on an example of elementary operations over matrices can be used as a base for solving more difficult tasks (for example, the calculations of a determinant of a matrix).
Mariya A. Zapletina
Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow, Russia
1. Van Schaik A., Delbruck T., Hasler J. Neuromorphic engineering systems and applications // Frontiers Media SA, 2015. – 182 p.
2. Матюшкин И.В. Коннекционистское расширение минимальной модели вы-числений. Ч. 1 // Философские проблемы информационных технологий и кибер-пространства. – 2016. – Т. 11. – № 1. – C. 103–120.
3. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем: учеб. пособие. – Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. – 184 с.
4. Ефимов С.С. Обзор методов распараллеливания алгоритмов решения некото-рых задач вычислительной дискретной математики // Математические структуры и моделирование. – 2007. – № 17. – C. 72–93.
5. Gavrilov S.V., Matyushkin I.V., Stempkovsky A.L. Computability via cellular au-tomata // Scientific and Technical Information Processing. – 2017. – Vol. 44. – No. 5. – P. 1–15.
6. Матюшкин И.В., Жемерикин А.В., Заплетина М.А. Клеточно-автоматные алгоритмы сортировки строк и умножения целых чисел по схеме Атрубина // Изв. вузов. Электроника. – 2016. – Т.21. – №6. – С. 557–565.
7. Atrubin A.J. A one-dimensional real-time iterative multiplier // IEEE Trans. on Electronic Computers. – 1965. – Vol. EC-14. – No.3. – P. 394–399.
8. Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. Анализ. Синтез. Поведение. – М.: Энергия, 1973. – С. 112–123.
9. Legendi T., Katona E. Megacell machine // Proc. of the International Conference on Vector and Parallel Processors in Computational Science III (25–28 August 1987). – 1987. – Vol.8. – Iss.2. – P. 195–199.
10. Katona E. Cellular algorithms for binary matrix operations // Lecture Notes in Computer Science: International Conf. on Parallel Processing, CONPAR 1981. – Berlin, Heidelberg: Springer, 1981. – Vol.111. – P. 205–209.
11. Stojanović N.M., Milovanović I.Ž., Stojčev M.K., Milovanović E.I. Matrix-vector multiplication on a fixed size unidirectional systolic array // Computers and Mathematics with Applications. – 2000. – Vol.40. – P. 1189–1203.
12. Болотов А.А., Кудрявцев В.Б., Подколзин А.С. Теория однородных структур. – М.: Наука, 1990. – 296 с.