Наумов Лев Александрович

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

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

Положения, выносимые на защиту и их научная новизна

Практическая полезность

Клеточный автомат
Клеточный автомат A представляет собой четверку объектов {G, Z, N, f}, где:
G – дискретное метрическое пространство, решетка автомата;
Z – конечное множество возможных состояний клетки. Таким образом, состояние всей решетки является элементом множества Z|G|;
N – конечное множество, определяющее окрестность клетки, то есть те |N| клеток, которые влияют на новое состояние данной. Элементы этого множества будем называть "соседями" клетки;
f – функция переходов или правила автомата. Вычислимая функция, действующая Z×Z|N| → Z для автоматов с клетками с памятью и Z|N| → Z для автоматов с клетками без памяти.
Клеточные автоматы в общем случае характеризуются следующими фундаментальными свойствами:
Решетка однородна – никакие две области не могут быть отличены друг от друга по ландшафту. Это обеспечивается семантикой пространства G, а также единственностью определения окрестности N, множества значений Z и функции переходов f.
Взаимодействия локальны. Состояния только клеток окрестности влияют на состояние данной клетки, что обеспечивается семантикой функции f.
Обновление значений состояний всех клеток решетки происходит одновременно после вычисления нового состояния каждой из них (такие автоматы называются "синхронными").

Обобщённые координаты
Обобщённая координата – неотрицательное целое число, однозначно указывающее на клетку решетки клеточного автомата произвольной размерности.
Метод введения обобщённых координат обеспечит единообразие представления данных для различных решеток.
Он заключается в нумерации клеток неотрицательными целыми числами.
Необходимо обеспечить нахождение непосредственных соседей данной клетки.
Без перехода к декартовым координатам.
Это позволит работать с более сложными окрестностями (искать соседей рекурсивно).

Обобщённые координаты для треугольной решетки, базирующиеся на спиральных обобщённых координатах для шестиугольной решетки
Спиральные обобщённые координаты для шестиугольной решетки
Различные способы введения обобщённых координат
Спиральные обобщённые координаты для квадратной решетки
Спиральные обобщённые координаты для треугольной решетки

Координаты углов
Номер кольца
Координаты соседей
, где
Спиральные обобщённые координаты для решетки из шестиугольников

Сравнение эффективности различных способов введения обобщённых координат
Приняв за единицу измерения производительности средние показатели самого медленного способа – спиральных координат для треугольной решетки, можно заключить, что остальные варианты быстрее его в следующее число раз:
спиральные координаты для квадратной решетки – в 3,9 раза;
обобщённые координаты для треугольной решетки, основанные на спиральных координатах для шестиугольной решетки – в 4,4 раза;
спиральные координаты для шестиугольной решетки – в 6,2 раза.
По вертикальной оси откладывается количество клеток, для которых удается определить соседей за одну секунду. Данные приводятся для различных способов введения обобщённых координат. Одним цветом показаны результаты, полученные на конкретной однопроцессорной системе.

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

Компонентная модель декомпозиции клеточных автоматов
Каждый клеточный автомат целесообразно представлять набором компонентов следующих четырех типов:
Решетка (grid) – осуществляет визуализацию автомата и навигацию;
Метрика (metrics) – сопоставляет клеткам координаты, вводит отношение соседства и функции вычисления расстояний между клетками.
Выделение этого типа компонентов позволит использовать обобщённые координаты и переходить от одних координат к только сменой компонента.
Хранилище данных (datum) – обеспечивает хранение, обмен и преобразования состояний клеток, а также некоторые аспекты визуализации;
Правила (rules) – описывает итерацию, задаёт не только функцию переходов, но и метод разделения задачи на подзадачи, оптимизацию вычислений и т.п.
При реализации целесообразно ввести дополнительный тип компонента:
Анализатор (analyzer) – позволяет наблюдать динамику изменения ключевых параметров эксперимента, строить графики, файлы отчетов и т.п.
Необходимо отметить, что речь идет не о четырех составляющих из определения клеточного автомата ({G, Z, N, f}). В данном случае декомпозицию логичнее вести по другим принципам и руководствоваться вопросам реализации автомата и проектирования вычислительного эксперимента.
Модель компонентной декомпозиции клеточных автоматов позволяет "собирать" автоматы с различной функциональностью, посредством незначительных изменений переходить от одной задачи к другой, пробовать решать одну и ту же задачу на разных решетках, с различными метриками и т.д.
Кроме того, она предоставляет возможность распределять разработку программного обеспечения эксперимента между различными исполнителями.

Требования к инструментальным средствам (1)
Предоставлять пользователям дружественный, удобный, современный интерфейс с богатым набором возможностей для работы.
Наглядно визуализировать состояния решетки, обеспечивать удобную навигацию по ней.
Быть максимально универсальным, не накладывать ограничений на множество автоматов, которые можно использовать.
Выполнять итерации, используя современные вычислительные и коммуникационные технологии, быстро и эффективно распараллеливая вычисления автомата с помощью доступных ресурсов (машин вычислительного кластера, процессоров многопроцессорной системы и т.д.).
Оптимизировать вычисления, например, исключать не обновляемые зоны решетки из рассмотрения, использовать шаблоны для сравнения окрестностей во избежание лишних трудоемких вычислений и т.п.
Позволять удобно и надежно проводить продолжительные (возможно, многомесячные) вычислительные эксперименты. Несмотря на то, что почти все вычислительные ресурсы системы будут заняты осуществлением итераций, программа должна продолжать быть интерактивной и отвечать на запросы пользователя.
Позволять производить не только сами вычисления, но и анализ результатов вычислений, а именно, поддерживать построение разнообразных графиков, демонстрировать изменения различных параметров моделируемой системы и т.п.

Требования к инструментальным средствам (2)
Предоставлять пользователям дружественный, удобный, современный интерфейс с богатым набором возможностей для работы.
Наглядно визуализировать состояния решетки, обеспечивать удобную навигацию по ней.
Быть максимально универсальным, не накладывать ограничений на множество автоматов, которые можно использовать.
Выполнять итерации, используя современные вычислительные и коммуникационные технологии, быстро и эффективно распараллеливая вычисления автомата с помощью доступных ресурсов (машин вычислительного кластера, процессоров многопроцессорной системы и т.д.).
Оптимизировать вычисления, например, исключать не обновляемые зоны решетки из рассмотрения, использовать шаблоны для сравнения окрестностей во избежание лишних трудоемких вычислений и т.п.
Позволять удобно и надежно проводить продолжительные (возможно, многомесячные) вычислительные эксперименты. Несмотря на то, что почти все вычислительные ресурсы системы будут заняты осуществлением итераций, программа должна продолжать быть интерактивной и отвечать на запросы пользователя.
Позволять производить не только сами вычисления, но и анализ результатов вычислений, а именно, поддерживать построение разнообразных графиков, демонстрировать изменения различных параметров моделируемой системы и т.п.
Интерфейс предложенного инструментального средства чрезвычайно богат и поддерживает множество типичных функций, присутствия которых пользователь в праве ожидать от современного программного обеспечения.
За визуализацию состояния решетки и удобную навигацию по ней отвечает отдельный класс компонентов. Пользователю предоставляется стандартный набор средств для этих целей, кроме того, он может быть расширен с помощью новых компонентов, обладающих конкретными специфическими свойствами, необходимыми для решения задач.
Инструментальное средство позволяет моделировать класс систем даже более широкий, чем класс "клеточные автоматы".
Средство позволяет организовывать вычисления, как на отдельном персональном компьютере, так и на многопроцессорной системе и в вычислительном кластере.
Средства для оптимизации вычислений включены в стандартный пакет программного обеспечения и могут быть применены при решении пользовательских задач. Этот набор также может быть легко расширен пользователями при необходимости.
Проект позволяет удобно и надежно проводить продолжительные вычислительные эксперименты, сохраняя при этом интерактивность и предоставляя возможности управления его течением.
Инструментальное средство использует специальные компоненты-анализаторы для наблюдений и изучения динамики ключевых параметров эксперимента, построения графиков, файлов-отчетов и прочих задач такого рода.

Структурная схема инструментального средства
CAME&L = среда выполнения + библиотека CADLib + стандартные компоненты
CAME&L – Cellular Automata Modeling Environment & Library

Методика организации и проведения вычислительных экспериментов
Запуск среды выполнения.
При проведении эксперимента в вычислительном кластере, необходимо запустить среду на всех вычислительных узлах.
Выбор решетки. Если подходящая решетка есть в наборе стандартных компонентов, то выбрать ее. Иначе – создать новый компонент.
Выбор метрики. Если подходящая метрика есть в наборе стандартных компонентов, то выбрать ее. Иначе – создать новый компонент.
Выбор хранилища данных. Если подходящее хранилище данных есть в наборе стандартных компонентов, то выбрать его. Иначе – создать новый компонент.
Выбор правил. Если подходящие правила есть в наборе стандартных компонентов, то выбрать их. Иначе – создать новый компонент.
Настройка компонентов. Установить требуемые значения параметров.
Запуск эксперимента путем выбора соответствующей команды в среде.
Создание и выбор нового компонента
Разработка компонента. С помощью привычного средства разработки (например, Microsoft Visual C++ 6) создать библиотеку, содержащую класс требуемого компонента, являющийся наследником класса базового класса из библиотеки CADLib.
Компиляция компонента в DLL-библиотеку.
Установка компонента в инструментальном средстве. Для установки, удаления и изучения компонентов в среде выполнения имеется инструмент "Components Manager". Им и необходимо воспользоваться.
Выбор компонента.

Применение методики на примере игры "Жизнь"
Выбор решетки. Для моделирования требуется двумерная квадратная решетка. Компонент, "Square Basic Grid", реализующий функциональность такой решетки, имеется в наборе стандартных компонентов.
Выбор метрики. Используем декартовы координаты. Компонент "Cartesians", реализующий функциональность декартовой метрики, существует в наборе стандартных.
Выбор хранилища данных. Компонент "Booleans for Cartesians", реализующий функциональность хранилища булевых данных для декартовой метрики, имеется в наборе стандартных.
Выбор правил. Предположим, что компонент, реализующий правила игры "Жизнь" не входит в набор стандартных компонентов. Создадим новый компонент.
Настройка компонентов. Необходимо изменить значение параметра "Double" хранилища данных "Booleans for Cartesians" на "true", выбрав тем самым синхронный клеточный автомат.
Запуск эксперимента.
Создание и выбор нового компонента
Разработка компонента. Создадим класс наследник класса CAUniRules. Переопределим его функцию SubCompute следующим образом:
DATUM(CACrtsBool2DDatum);
CACell c;
CACell neig[12];
int alive=0;
for(CACell i=z.a1; i<=z.b1; i++)
for(CACell j=z.a2; j<=z.b2; j++) {
alive=0;
c=GET_METRICS->ToCell(i,j,0);
GET_METRICS->GetNeighbours(c,neig);
for (unsigned int k=0;
k
GetNeighboursCount();
k++) if (datum->Get(neig[k]))alive++;
if (datum->Get(c))
datum->Set(c,alive==2||alive==3);
else
datum->Set(c,alive==3);
}
return true;
Компиляция компонента в DLL-библиотеку.
Установка компонента в инструментальном средстве.
Выбор компонента.

Уравнение теплопроводности
Непрерывный вариант:
Дискретный вариант (при a, dx и dy = 1):

Существует 256 функций переходов для простейших одномерных двоичных клеточных автоматов.
Рассмотрены и пронумерованы 256 структур, порождаемых во времени с помощью этих функций из точечного зародыша.
Наиболее интересны те из них, которые обладают свойством самовоспроизведения:
Структура № 90. Салфетка Серпинского
Структура № 22. Салфетка Серпинского из "пьедесталов "
Структура № 60. Треугольник Паскаля
000000010000000
000000101000000
000001000100000
000010101010000
000100000001000
001010000010100
010001000100010
101010101010101
Классификация структур, порождаемых простейшими клеточными автоматами из точечного зародыша (1)

Классификация структур, порождаемых простейшими клеточными автоматами из точечного зародыша (2)
Впервые проведена полная классификация этих структур относительно различных операций инвариантности.
E
EM
EI
E(I+M)
EIM
EIMO
EIMOL6

Классификация структур, порождаемых простейшими клеточными автоматами из точечного зародыша (3)
Число классов при разных вариантах классификации без сдвигов
Число классов при разных вариантах классификации со сдвигами

Внедрение
Научные исследования
В СПбГУ ИТМО при исследованиях по грантам Министерства образования и науки РФ, а также РФФИ.
В Университете Амстердама для организации вычислительных экспериментов на FPGA-системах и многих других задач.
Политехническом университете Бухареста при создании инструментального средства для обработки изображений.
Обучение
В СПбГУ ИТМО на кафедре "Компьютерные технологии":
при чтении лекций по курсу "Теория автоматов в программировании";
в курсовых работах студентов по курсу "Теория автоматов в программировании".
В СПбГУ на кафедре "Вычислительная физика":
при чтении лекций по курсу "Современные технологии программирования для научных работников";
для демонстрации решения уравнений вычислительной физики посредством клеточных автоматов.
В Университете Амстердама:
при чтении лекций по курсу "Моделирование поведения сложных систем";
написании дипломных проектов.

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

Заключение
В диссертации получены следующие результаты:
Введено понятие "обобщенные координаты" для решеток клеточных автоматов. Разработан метод введения таких координат.
На основе метода введения обобщенных координат и компонентной модели декомпозиции разработано инструментальное средство автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов CAME&L.
Метод и инструментальное средство CAME&L апробированы при автоматизации проектирования программного обеспечения ряда вычислительных экспериментов с использованием клеточных автоматов на однопроцессорных, многопроцессорных, кластерных и FPGA вычислительных системах. Ранее было невозможно выполнить это с помощью одного и того же инструментального средства.
Проведена классификация всех возможных структур, порождаемых одномерными клеточными автоматами из точечного зародыша. Построено множество разнообразных классов эквивалентности. Показано, что автоматы с клетками с памятью и автоматы с клетками без памяти могут демонстрировать одинаковое поведение. Таким образом, выполнен анализ простейших клеточных автоматов, порождающих сложное поведение (в том числе, самовоспроизведение).
Результаты были внедрены в учебном процессе и при проведении научных исследований в ряде университетов.

Публикации
Наумов Л. Как увеличить скорость "Жизни", или Эффективная организация данных для повышения скорости поиска клеток и разрешения отношений соседства при реализации клеточного автомата Джона Хортона Конвея "Жизнь". Части I и II // Информатика. 2001. № 33 (322). с. 25–27; № 34 (323). с. 20–24; Компьютеры + Программы. 2001. № 10. с. 68–73.
Naumov L. Generalized Coordinates for Cellular Automata Grids / Computational Science – ICCS 2003. Part 2. Springer-Verlag. 2003, c. 869–878.
Наумов Л., Шалыто А. Клеточные автоматы. Реализация и эксперименты // Мир ПК. 2003. № 8, c. 71–78.
Наумов Л. CAME&L – среда моделирования и библиотека разработчика клеточных автоматов / Труды XI Всероссийской научно-методической конференции Телематика’2004. Том 1. СПб.: СПбГУ ИТМО. 2004, c. 184–186.
Наумов Л. CTP (Commands Transfer Protocol) – Сетевой протокол для высокопроизводительных вычислений / Труды XI Всероссийской научно-методической конференции Телематика’2004. Том 1. СПб.: СПбГУ ИТМО. 2004, c. 188–189.
Наумов Л., Шалыто А. "Цветные" клеточные автоматы // Мир ПК. 2004. № 5, c. 64–71.
Naumov L. CAME&L – Cellular Automata Modeling Environment & Library / Cellular Automata. Sixth International Conference on Cellular Automata for Research and Industry, ACRI-2004. Springer–Verlag. 2004, c. 735–744.
Наумов Л. CTP (Commands Transfer Protocol) v. 1.2 – Новая версия сетевого протокола для высокопроизводительных вычислений / Труды XII Всероссийской научно-методической конференции Телематика’2005. Том 1. СПб.: СПбГУ ИТМО. 2005, с. 92–93.
Наумов Л. Преимущества использования обобщённых координат для многомерных решёток клеточных автоматов / Труды XII Всероссийской научно-методической конференции Телематика’2005. Том 1. СПб.: СПбГУ ИТМО. 2005. с. 93–95.
Наумов Л. CAME&L – средство для осуществления параллельных и распределенных вычисления на основе клеточных автоматов / Технологии распределенных вычислений. 2005, с. 284–286.
Наумов Л. Решение задач с помощью клеточных автоматов посредством программного обеспечения CAMEL (Части I и II) // Информационно-управляющие системы. 2005. № 5, c. 22–30; № 6, c. 30–38.
Наумов Л., Шалыто А. Классификация структур, порождаемых одномерными двоичными клеточными автоматами из точечного зародыша // Известия РАН. Теория и системы управления. 2005. № 5, с. 137–145. Журнал из списка ВАК.
Naumov L., Shalyto A. Classification of Structures Generated by One-Dimensional Binary Cellular Automata from a Point Embryo // Journal of Computer and Systems Sciences International. Vol. 44. 2005. № 5, pp. 800–807.
Наумов Л. Сравнение специализированных сетевых протоколов CTP (Commands Transfer Protocol) и IL (Internet Link) / Труды XIII Всероссийской научно-методической конференции Телематика’2006. Том 1. СПб.: СПбГУ ИТМО. 2006, с. 266–267.
Наумов Л. Обзор программного обеспечения для решения задач с использованием клеточных автоматов // Телекоммуникации и информатизация образования. 2006. № 2, c. 114–125.
Все статьи и инструментальное средство – опубликованы на сайте http://camellab.spb.ru.