1561-5405 10.24151/1561-5405 Proceedings of Universities. Electronics Scientifical and technical journal "Proceedings of Universities. Electronics" Научно-технический журнал «Известия высших учебных заведений. Электроника» 1561-5405 2587-9960 National Research University of Electronic Technology Национальный исследовательский университет "Московский институт электронной техники" 10.24151/1561-5405-2019-24-1-51-63004.272:004.021Информационно-коммуникационные технологииData Reflection and Transposition in the Matrix of a Cellular Automata ComputatorОтражение и транспонирование данных в матрице клеточно-автоматного вычислителяМатюшкин Игорь Валерьевич МатюшкинИгорь Валерьевич ValerevichMatyushkin IgorMatyushkin Igor ValerevichЗаплетина Мария АндреевнаЗаплетинаМария АндреевнаZapletinaMariya A.Mariya A. ZapletinaИнститут проблем проектирования в микроэлектронике Российской академии наук, г. Москва, Россия; Национальный исследовательский университет «МИЭТ», г. Москва, РоссияИнститут проблем проектирования в микроэлектронике Российской академии наук, г. Москва, Россия5163http://ivuz-e.ru/issues/1-_2019/trazhenie_i_transponirovanie_dannykh_v_matritse_kletochno_avtomatnogo_vychislitelya/http://ivuz-e.ru/download/1_2019_2356.pdf

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).

Параллельные архитектуры вычислительных систем, в том числе с массивным параллелизмом, в настоящее время интересуют исследователей в области теоретической информатики. Основной задачей при этом становится аппаратное или алгоритмическое ускорение межпроцессорного обмена. Одним из подходов к построению алгоритмов может быть использование нетрадиционного формализма - нейронных сетей или клеточных автоматов (КА), реализующих модель ближнего взаимодействия элементарных вычислителей. В работе рассмотрены три операции с матричными данными: унарная (поэлементная), отражение, транспонирование. Операции реализованы параллельными алгоритмами в формализме КА в предположении, что данные введены в КА до начала расчета. Показано, что все представленные алгоритмы имеют линейную по размеру матрицы сложность. Движение и преобразование данных осуществлено с помощью введения в состояние ячейки битовых и/или тритовых, т.е. с тремя состояниями, флагов-компонент. Условия останова расчета - наступление stop-состояния флага выделенной ячейки КА или всех ячеек поля КА, т.е. их «заморозка». Освоение техники клеточно-автоматной алгоритмики на примере элементарных операций над матрицами может служить базой для решения более сложных задач (например, вычисление детерминанта матрицы), возникающих в рамках численного моделирования процессов, операций и устройств микроэлектроники.

клеточные автоматыматрицылинейная алгебрапараллельные вычислениянетрадиционные архитектуры Van Schaik A., Delbruck T., Hasler J. Neuromorphic engineering systems and applications // Frontiers Media SA, 2015. – 182 p.Матюшкин И.В. Коннекционистское расширение минимальной модели вы-числений. Ч. 1 // Философские проблемы информационных технологий и кибер-пространства. – 2016. – Т. 11. – № 1. – C. 103–120.Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем: учеб. пособие. – Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. – 184 с.Ефимов С.С. Обзор методов распараллеливания алгоритмов решения некото-рых задач вычислительной дискретной математики // Математические структуры и моделирование. – 2007. – № 17. – C. 72–93.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.Матюшкин И.В., Жемерикин А.В., Заплетина М.А. Клеточно-автоматные алгоритмы сортировки строк и умножения целых чисел по схеме Атрубина // Изв. вузов. Электроника. – 2016. – Т.21. – №6. – С. 557–565.Atrubin A.J. A one-dimensional real-time iterative multiplier // IEEE Trans. on Electronic Computers. – 1965. – Vol. EC-14. – No.3. – P. 394–399.Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. Анализ. Синтез. Поведение. – М.: Энергия, 1973. – С. 112–123.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.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.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.Болотов А.А., Кудрявцев В.Б., Подколзин А.С. Теория однородных структур. – М.: Наука, 1990. – 296 с.