Фронтальний клітинний автомат

Фронтальний клітинний автомат (frontal cellular automata, FCA) — спеціальний тип обчислювальних алгоритмів, збудованих на моделях клітинних автоматів.

Назва «фронтальний» походить від одного з популярних застосувань, а саме, зростання кристалів, коли границя зростаючого кристала розглядається як фронт зміни в його структурі. Головна особливість фронтальних клітинних автоматів - зміна напрямку інформаційного струменю для клітин, і як наслідок, використання при обчисленнях у кожному кроці тільки малої частини всіх клітин.

Головним елементом алгоритму клітинних автоматів є визначення стану клітини за допомогою так званих правил переходу. Ці правила описують стан клітини в наступному кроці на підставі визначення стану всіх клітин в його сусідстві (поточний стан клітини часто не враховується). Класичний алгоритм клітинних автоматів використовує це правило безпосередньо, тобто збирає інформацію. Приклад зображений на малюнку 1а. Для клітини в середині малюнка перевіряються правила переходу і вона отримує інформацію, досліджуючи стан своїх сусідів (наприклад в оточенні фон Неймана). Тому для реалізації обчислень в одному кроці необхідно вивчити цілий клітинний простір (стрілка у верхній частині малюнка), перевіряючи правила переходу для кожної клитини і стан усіх сусідів для кожної клитини простору. У фронтальних клітинних автоматах напрямок передачі змінюється на протилежний, як це показано на малюнку 1b. Це перший крок, який ще не дає будь-яких видимих переваг тому, що і в цьому випадку доводиться досліджувати весь клітинний простір і немає істотної різниці, чи буде клитина отримувати або відправляти інформацію до всіх своїх сусідів.

a)

b)

Рис.1

Різниця між цими алгоритмами з'являється, якщо ми розглядаємо перехідний та сталий стани. Якщо в сусідстві клітинки не відбуваються зміни, вона залишається в тому ж стані, і можна сказати, що вона знаходиться в сталому стані. І навпаки, якщо відбуваються зміни в сусідстві, вона може змінити свій стан, тобто буде в перехідному стані. Вже на цьому етапі виявляються відмінності між двома алгоритмами, так як збір інформації від сусідів не створює будь-яких передумов, які вказували б, чи слід збирати таку інформацію, чи ні. Однак, при поширенні (розсилці) інформації від клітини до сусідів рішення може бути прийняте на підставі знання, чи змінився стан цієї клітини чи ні. Клітина, яка не змінює свого стану, не буде посилати інформацію до свого оточення, однак, якщо зміни в її стані відбулися, клітини в усьому її оточенні отримають повідомлення, і на підставі цієї інформації здійснюють перевірку правил переходу, без вивчення свого сусідства. Це другий крок, друга відмінність.

Третій і останній крок полягає у використанні для розрахунку тільки клітин у перехідному стані. Якщо сутністю другого кроку була розсилка сигналів тільки від клітин в перехідному стані і незмінним дослідженням усього клітинного простору, то головним елементом третього етапу модернізації алгоритму є обмеження дослідження клітин тільки тими з них, які знаходяться в перехідному стані.

Як приклад ефективного застосування може бути показаний процес зростання кристала. Фрагмент простору зі зростаючим кристалом зображений на малюнку 2. У будь-якому процесі росту кристалу або зерна, можна виділити три зони. У першій зоні (a) не відбулося жодних змін початкового стану. У другій зоні (b) такі зміни закінчилися, і подальші зміни більше відбуватися не будуть. Нарешті, в третій зоні (c) зміни відбуваються в цей час часу і, отже, тільки клітини з третьої зони використовуються в розрахунках. І перша, і друга зони повинні бути виключені з розрахунків у поточному кроці, оскільки зміни в клітинах цих зон не очікуються і не відбудуться. Для вибраної клітини на малюнку 2 в перехідному стані показано стрілками напрямок передачі інформації, істотною для сусідів. Таким чином, в поточному кроці тільки шість клітин в зоні (c) братимуть участь у розрахунку.

Рис.2

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

Приклади оцінки обчислювальних витрат для декількох простих варіантів.

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

Другий варіант: тривимірний клітинний простір 100x100x100 клітин з одним зародком. Розрахунки до моменту заповнення всього простору з сусідством Мура (26 сусідів), кристал росте у кшталті сфери з середньою затримкою в перехідному стані, що дорівнює трьом крокам.

Витрати на обчислення відрізнятися на декілька порядків. При цьому, чим більше число кроків, тим більше ця різниця (табл.).