Фронтальный клеточный автомат


Фронтальный клеточный автомат

Фронтальный клеточный автомат (англ. frontal cellular automata, FCA) - специальный тип вычислительных алгоритмов, основанных на моделях клеточных автоматов.

Название «фронтальный» происходит от одного из популярных применений, а именно, рост кристаллов, когда граница растущего кристалла рассматривается как фронт изменения в его структуре. Главная особенность фронтальных клеточных автоматов – изменение направления информационного потока для ячеек (клеток), и как результат использование при вычислениях в каждом шаге только малой части всех ячеек.

Главным элементом алгоритма клеточных автоматов является определение состояния клетки с помощью так называемых правил перехода. Эти правила описывают состояние ячеек в следующем шаге на основании определения состояния ячеек в его соседстве (текущее состояние клетки часто не учитывается). Классический алгоритм клеточных автоматов использует это правило напрямую, то есть ячейка собирает информацию. Пример показан на рисунке 1а. Для ячейка в середине рисунка проверяются правила перехода и она получает информацию , исследуя состояние своих соседей (например в окружении фон Неймана). Поэтому для реализации вычислений в одном шаге необходимо изучить всё клеточное пространство (стрелка в верхней части рисунка), проверяя правила перехода для каждой ячейки и состояние всех соседей для каждой ячейки пространства. Во фронтальных клеточных автоматах направление передачи информации изменяется на противоположное, как это показано на рисунке 1b. Это первый шаг, который не дает каких-либо видимых преимуществ потому, что и в этом случае приходится исследовать всё клеточное пространство и нет существенной разницы будет ли ячейка получать или отправлять информацию ко всем своим соседям.

Разница между этими алгоритмами появляется, если мы рассматриваем переходные и установившиеся состояния. Если в соседстве ячейки не происходят изменения, она остается в том же состоянии, и можно сказать, что она находится в устойчивом установившемся состоянии. И наоборот, если происходят изменения в соседстве, она может изменить свое состояние, то есть будет в переходном состоянии. Уже на этом этапе проявляются различия между двумя алгоритмами, так как сбор информации от соседей не создает каких-либо предпосылок, которые указывали бы, следует ли собирать такую информацию, или нет. Однако, при распространении (рассылке) информации от ячейки к соседям решение может быть принято на основании знания, изменилось ли состояние этой ячейки или нет. Ячейка, которая не изменяет своего состояния, не будет посылать информацию к своему окружению, однако, если изменения в ее состоянии произошли, ячейки во всём её окружении получат сообщение, и на основании этой информации произведут проверку правил перехода, без изучения своего соседства. Это второй шаг, второе отличие.

Третий и последний шаг заключается в использовании для расчета только ячеек в переходном состоянии. Если сущностью второго шага была рассылка сигналов только от ячеек в переходном состоянии и неизменным исследованием всего клеточного пространства, то главным элементом третьего этапа модернизации алгоритма является ограничение исследования ячеек только теми из них, которые находятся в переходном состоянии.

Как пример эффективного применения может быть показан процесс роста кристалла. Фрагмент пространства с растущим кристаллом показан на рисунке 2. В любом процессе роста кристалла или зерна, можно выделить три зоны. В первой зоне (a) не произошло никаких изменений исходного состояния. Во второй зоне (b) такие изменения закончились, и дальнейшие изменения больше происходить не будут. Наконец, в третьей зоне (c) изменения происходят в данный момент времени и, следовательно, только ячейки из третьей зоне используются в расчетах. И первая, и вторая зоны должны быть исключены из расчетов в текущем шаге, поскольку изменения в ячейках этих зон не ожидаются и не произойдут. Для выбранной ячейки на рисунке 2 в переходном состоянии показано стрелками направление передачи информации, существенной для соседей. Таким образом, в текущем шаге только шесть ячеек в зоне (c) будут участвовать в расчете.

FCA4.jpg

Использование FCA, вместо обычных клеточных автоматов, позволяет снизить вычислительные затраты в двумерных (2D) моделях, но особенно существенно в трехмерных (3D CA), потому что значительные области пространства исключаются из расчета в каждом шаге по времени, и лишь тонкий слой участвует в расчете. В классических CA практически каждый шаг требует таких же затрат и время его вычисления в течение всего процесса моделирования остается неизменной. Время же расчета одного шага FCA зависит от количества клеток, участвующих в расчете, и изменяется в широких пределах, оставаясь всегда лишь малой частью по сравнению со временем вычислений одного шага в классических CA. Каждая ячейка FCA в действительности участвует в расчетах только один раз в течение всего процесса расчета, в то время, как в классическом алгоритме, на каждом шаге вычислений.

Примеры оценки вычислительных затрат для нескольких простых вариантов.

Первый вариант: двумерное клеточное пространство 100x100 ячеек с одним зародышем. Расчеты до момента заполнения всего пространства с соседством фон Неймана (четыре соседа) без задержек.

Второй вариант: трехмерное клеточное пространство 100x100x100 ячеек с одним зародышем. Расчеты до момента заполнения всего пространства с соседством Мура (26 соседей), кристалл растет в формы сферы со средней задержкой в переходном состоянии равной трём шагам.

Затраты на вычисления отличаться на несколько порядков. При этом, чем большее число шагов, тем больше эта разница (табл.).

Классический алгоритм Фронтальный автомат Отношение классического к фронтальному
Вар. 1 Вар. 2 Вар. 1 Вар. 2 Вар. 1 Вар. 2
Число циклов от появления зародыша до заполнения всего простраснтва 50 184 50 184 1 1
Число исследуемых ячеек во всех циклах 5*105 1,84*108 104 3*106 50 61
Число межклеточных коммуникатов во всем моделировании 2*106 4,78*109 4*104 2,6*107 50 184

Литература

  1. Dmytro Svyetlichnyy "Modelling of the microstructure: From classical cellular automata approach to the frontal one ", Computational Materials Science, t. 50, 2010, s. 92-97
  2. Łukasz Łach, Dmytro Svyetlichnyy "Modelowanie za pomocą frontalnych automatów komórkowych rozwoju mikrostruktury podczas walcowania", Hutnik-Wiadomości Hutnicze, 2010, s.725-735
  3. Dmytro Svyetlichnyy "Proc. COMPLAS IX", Barcelona 2007, s. 983
  4. Dmytro S. Svyetlichnyy (2011). Modeling of Macrostructure Formation during the Solidification by using Frontal Cellular Automata, Cellular Automata - Innovative Modelling for Science and Engineering, Alejandro Salcido (Ed.), ISBN 978-953-307-172-5, InTech

Wikimedia Foundation. 2010.