ИССЛЕДОВАНИЕ АБСТРАКТНОГО КЛЕТОЧНОГО АВТОМАТА НЕЗАВИСИМОГО ОТ ВРЕМЕНИ


УДК 519.713.1
doi: 10.26102/2310-6018/2019.24.1.037

А.А. Уманов


Актуальность исследования обусловлена всё возрастающим количеством, как вычислительных ядер у отдельно взятого вычислительного устройства, так и общего числа таких устройств. При этом многие алгоритмы рассчитаны на работу в строго определенной последовательности, в результате чего, либо часть вычислительной мощности простаивает, либо поверх основных вычислений достраивается дополнительная логика, которая не только усложняет разработку, но и требует дополнительных вычислений, единственной целью которых является синхронизация между узлами/ядрами/потоками. В связи с этим, данное исследование направлено на выявление способа выполнения вычислений без необходимости синхронизации как таковой, на примере работы клеточного автомата. Ведущим методом исследования данной проблемы является математическое и компьютерное моделирование работы клеточного автомата, позволяющие комплексно рассмотреть первопричину возникновения необходимости выполнения синхронизации – времени. В статье представлен способ описания клеточного автомата, в котором исключены все излишние сущности, одной из которых стало время, в результате чего исчезла необходимость и в синхронизации. Выявлены ключевые сущности, которых достаточно для полноценного описания работы произвольного клеточного автомата. Обоснована применимость минимального набора сущностей на примере элементарного одномерного клеточного автомата.

Ключевые слова: клеточный автомат, абстрактный клеточный автомат, правило, состояние, суперпозиция, пространство, время, матрица.

Полный текст статьи:
Umanov_1_19_1.pdf