Отражение и транспонирование данных в матрице клеточно-автоматного вычислителя

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