Параллельные архитектуры вычислительных систем, в том числе с массивным параллелизмом, в настоящее время интересуют исследователей в области теоретической информатики. Основной задачей при этом становится аппаратное или алгоритмическое ускорение межпроцессорного обмена. Одним из подходов к построению алгоритмов может быть использование нетрадиционного формализма - нейронных сетей или клеточных автоматов (КА), реализующих модель ближнего взаимодействия элементарных вычислителей. В работе рассмотрены три операции с матричными данными: унарная (поэлементная), отражение, транспонирование. Операции реализованы параллельными алгоритмами в формализме КА в предположении, что данные введены в КА до начала расчета. Показано, что все представленные алгоритмы имеют линейную по размеру матрицы сложность. Движение и преобразование данных осуществлено с помощью введения в состояние ячейки битовых и/или тритовых, т.е. с тремя состояниями, флагов-компонент. Условия останова расчета - наступление stop-состояния флага выделенной ячейки КА или всех ячеек поля КА, т.е. их «заморозка». Освоение техники клеточно-автоматной алгоритмики на примере элементарных операций над матрицами может служить базой для решения более сложных задач (например, вычисление детерминанта матрицы), возникающих в рамках численного моделирования процессов, операций и устройств микроэлектроники.
Игорь Валерьевич Матюшкин
Институт проблем проектирования в микроэлектронике Российской академии наук, г. Москва, Россия; Национальный исследовательский университет «МИЭТ», г. Москва, Россия
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 с.