автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Метод введения обобщенных координат и инструментальное средство для автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов

На правах рукописи

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

Метод введения обобщенных координат и инструментальное средство для автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов

Специальность 05.13.12. Системы автоматизации проектирования (приборостроение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2007

003068260

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики

Научный руководитель

доктор технический наук, профессор

Шалыто Анатолий Абрамович

Официальные оппоненты

доктор технических наук Бухановский Александр Валерьевич

кандидат физико-математических наук, старший научный сотрудник Новиков Фёдор Александрович

Ведущая организация Санкт-Петербургский государственный

электротехнический университет "ЛЭТИ" имени В.И. Ульянова (Ленина)

Защита диссертации состоится 22 м;ш 2007 года в 15 часов 50 минут на заседании диссертационного совета Д 212.227.05 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО.

Автореферат разослан 11 апреля 2007 г.

Ученый секретарь совета Д 212.227.05, кандидат технических наук, доцент

Поляков Владимир Иванович

Общая характеристика работы

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

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

Существует ряд математических моделей параллельных и распределенных вычислений. Одной из них являются клеточные автоматы, применению которых и посвящена настоящая диссертация.

Клеточные автоматы - это дискретные динамические системы, поведение которых может быть полностью описано в терминах локальных зависимостей. Эти автоматы представляют собой модели параллельных вычислений, которые обладают сколь угодно большой степенью параллелизма. Можно считать, что они представляют собой дискретный эквивалент понятия "поле". Клеточные автоматы применяются для проведения различных вычислительных экспериментов, так как они удобны, например, для численного решения дифференциальных уравнений и уравнений в частных производных. Они также широко используются для моделирования поведения сложных систем.

Существует ряд средств автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов таких, как, например, средство SIMP/STEP (реализующее набор функций для решения задач физического моделирования), CAGE (инструмент для образовательных целей) или Mirek's Cellebration (MCelt) (средство для визуализации простых алгоритмов) и CDL (инструмент, позволяющий использовать FPGA-системы для выполнения вычислительных экспериментов). Однако все эти средства имеют ограничения, которые накладываются на предметные области решаемых задач, реализуемые клеточные автоматы или используемые вычислительные архитектуры. Не существует единого средства, пригодного, как для образовательных, так и для научных целей. Поэтому для автоматизации проектирования программного обеспечения вычислительных экспериментов на основе клеточных автоматов необходимо разработать универсальное, расширяемое инструментальное средство, обладающее широким спектром функциональных возможностей, так как существующие инструменты не позволяют решать задачи из различных предметных областей с помощью разнообразных клеточных автоматов. Так, например, далеко пе каждое средство позволяет моделировать автоматы, как с двумерными, так и с трехмерными решетками. Малая их часть поддерживает использование разнообразных окрестностей. Например, окрестность Марголуса поддерживают всего несколько специализированных средств. Не одно из них не допускает хранения строк в клетках, что необходимо при реализации задач параллельного синтаксического анализа Только некоторые позволяют описывать структуры данных, хранимые в клетках.

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

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

необходимо отметить, что сложность современного параллельного программного обеспечения такова, что средство автоматизации его проектирования необходимо.

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

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

Основные задачи диссертационной работы состоят в следующем:

1. Разработка метода введения обобщенных координат для решеток клеточных автоматов.

2. Разработка на основе метода введения обобщенных координат инструментального средства CAMEiL (Cellular Automata Modeling Environment & Library), включающего в себя среду выполнения и библиотеку для создания клеточных автоматов, которое предназначено для автоматизации проектирования программного обеспечения вычислительных экспериментов с их использованием.

3. Применение инструментального средства САМЕЛ, для автоматизации проектирования программного обеспечения ряда вычислительных экспериментов с использованием клеточных автоматов на различных вычислительных архитектурах.

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

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

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

1. Метод введения обобщенных координат для клеточных автоматов обеспечивает единообразие представления данных для автоматов с различными решетками, в том числе, и разной размерности.

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

Методы исследования. В работе использованы методы теории автоматов, теории множеств, теории параллельных вычислений, теории алгоритмов, математической физики, основы объектно-ориентированного программирования.

Достоверность и обоснованность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается доказательствами, обоснованием постановок задач, точной формулировкой критериев, компьютерным моделированием, а также результатами использования методов, предложенных в диссертации, в ходе выполнения вычислительных экспериментов.

Практическое значение работы состоит в том, что разработано универсальное и расширяемое инструментальное средство CAMEtL для автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием широкого спектра клеточных автоматов, которое позволяет проводить вычислительные эксперименты на однопроцессорных, многопроцессорных и кластерных платформах.

Реализация результатов работы (имеются акты внедрения). Для образовательных целей результаты используются в Санкт-Петербургском государственном университете

информационных технологий, механики и оптики (СПбГУ ИТМО), в Санкт-Петербургском государственном университете и в Университете Амстердама (Нидерланды). Для научно-исследовательских целей результаты используются в СПбГУ ИТМО, в Университете Амстердама и в Политехническом университете Бухареста (Румыния).

Научно-исследовательские работы. Результаты диссертации получены в ходе выполнения в СПбГУ ИТМО научно-исследовательских работ по теме "Разработка технологии автоматного программирования", выполненной по гранту РФФИ № 02-07-90114 в 2002-2003 грдах; по теме "Разработка технологии программного обеспечения Систем управления на основе автоматного подхода", выполняемой по заказу Министерства образования РФ в 2002-2005 годах; по гранту конкурса персональных грантов для студентов и аспирантов вузов Санкт-Петербурга в 2004 году; по теме "Разработка среды и библиотеки "CAME.L" для организации параллельных и распределенных вычислений на основе клеточных автоматов", выполненной по гранту РФФИ № 05-07-90086 в 2005-2006 годах. При выполнении работ по этому гранту автор был ответственным исполнителем. Научно-исследовательская деятельность автора дважды отмечена стипендией Президента РФ.

Апробация результатов работы. Основные положения диссертационной работы докладывались на международной научной конференции "International Conference of Computational Sciences" (Санкт-Петербург - Мельбурн, 2003 г.), на международной научной конференции "Cellular Automata for Research and Industry" (Амстердам, 2004 г.), на научной школе "Joint Advanced Students School" (Санкт-Петербург, 2004 г.), на научно-методических конференциях "Телематика-2004", "Телематика-2005", "Телематика-2006" (Санкт-Петербург), на научной школе "Ferienakademie" (Южный Тироль, 2005 г.), на всероссийской научной конференции "Научный сервис в сети Интернет: технологии распределенных вычислений" (Дюрсо, 2005 г.), на международной научной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (Санкт-Петербург, 2006 г.).

Публикации. По теме диссертации опубликовано 14 печатных работ, в том числе, в журналах "Известия РАН. Теория и системы управления" (входит в перечень ВАК), "Информационно-управляющие системы", "Телекоммуникации и информатизация образования", а также в материалах конференций "International Conference of Computational Sciences", "Cellular Automata for Research and Industry", "Телематика" и "Научный сервис в сети Интернет: технологии распределенных вычислений".

Структура диссертации. Диссертация изложена на 283 страницах и состоит из оглавления, введения, четырех глав, заключения, списка терминов, предметного указателя, списка литературы и двух приложений. Список литературы состоит из 97 наименований. Работа содержит 44 рисунка и 13 таблиц.

Содержание работы

Во введении описывается объект и предмет исследования, ставятся цели и задачи исследования, обосновывается актуальность темы диссертационной работы. Дается оценка новизны полученных результатов, формулируются положения, выносимые на защиту.

Первая глава содержит введете в теорию клеточпых автоматов и исторический обзор их практического использования в различных предметных областях. Кроме того, в главе предложена компонентная модель декомпозиции клеточных автоматов, ,v ,,, (...'. .

Диссертация развивает исследования в области клеточных автоматов таких учёных, как, например, Джон фон Нейман, Томас Уорш, Иорг Веймар и Томазо Тоффоли.

На основе изучения литературы и опыта проведения экспериментов производится анализ инструментальных средств автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов и требований к таким средствам. Установлено, что инструментальное средство должно:

1. Предоставлять пользователям дружественный, удобный, современный интерфейс с

богатым набором возможностей для работы.

2. Наглядно визуализировать состояния решетки, обеспечивать удобную навигацию по ней.

3. Быть универсальным и не накладывать ограничений множество реализуемых автоматов.

4. Выполнять итерации, используя современные вычислительные и коммуникационные технологии.

5. Оптимизировать вычисления, например, исключать не обновляемые зоны решетки, использовать шаблоны для сравнения окрестностей и т.п.

6. Удобно и надежно проводить продолжительные вычислительные эксперименты, продолжать постоянно быть интерактивным и отвечать на запросы пользователя.

7. Позволять производить не только вычисления, но и анализ их результатов, поддерживать построение графиков, демонстрировать изменения параметров системы и т.п.

В работе рассматриваются более двадцати существующих инструментальных средств, приводятся их краткие характеристики, ссылки на сайты или статьи, в которых они были описаны, условия распространения и системные требования. Результаты их сравнения приведены в таблице 1.

Название 1 CAGE САМ Simulator 1 CANL 1 5 £ й 5 i CAT/ CARP CDL CDM' SLANG ^ О CELLAS S 3 Cellular/ Cellang CEPROL DDLab ! H1CAL LCAU I MCell_1 SCARLET SIMP/ STEP WinCA

I + - - + + - - - - - - + + - + + - + + - +

2 + + + + + + + + - +

3 + +

4 - - + + - - - + - + - - - - - - - - _ + -

5 - - - - - - - - - - - - - - - - - - + -

6 + + + + + + + + + + + + + + + + + + + + -

7 + +

"+" - свойство выполняется в должной мере <под таблицей>; "-" - свойство в должной мере не выполняется.

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

Для обеспечения выполнения всех указанных требований предлагается использовать модель декомпозиции клеточных автоматов, в соответствии с которой клеточный автомат должен быть реализован, как совокупность четырех взаимодействующих компонентов:

• решетки (grid), осуществляющей визуализацию автомата и навигацию по его клеткам;

• метрики (metrics), которая сопоставляет клеткам их координаты и вводит отношение соседства и функции вычисления расстояний между клетками по разным направлениям;

• хранилища данных (datum), обеспечивающего хранение, обмен и преобразования состояний клеток, а также некоторые аспекты визуализации (соответствие между состоянием клетки и цветами, используемыми для ее отображения);

• правил (rules), описывающих итерацию (не только функцию переходов, но и метод разделения задачи на подзадачи, оптимизацию вычислений и т.д.).

1 ' ' По иронии судьбы, это инструментальное средство является практически тезкой

средства, предложенного в настоящей диссертации. Амперсант в названии последнего появился Именно в связи с существованием проекта "CAMEL". Это название также является аббревиатурой, но в данном случае оно означает "Cellular Automata environMent for systEms modeLing". Кроме похожих названий и использования клеточных автоматов для организации вычислительных экспериментов инструментальные средства "CAMEL" и "CAMEtL" не связывает больше ничего.

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

Каждый компонент декларирует список собственных параметров, изменение значений которых обеспечивает настройку компонента.

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

Одним из основных недостатков известных подходов к реализации клеточных автоматов, является то, что не был известен метод, обеспечивающий единообразие представления данных для различных клеточных автоматов.

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

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

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

Одной из клеток присваивается номер ноль, она принимается за начало координат. Номера остальных клеток характеризуют их положение относительно него.

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

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

Метод иллюстрируется примерами для двумерных автоматов, для которых вводятся:

• спиральные обобщешше координаты для решеток из треугольников (рис. 1 .а);

• спиральные обобщешше координаты для решеток из квадратов (рис. 1.6);

• спиральные обобщенные координаты для решеток из шестиугольников (рис. 1.в);

• координаты для решеток из треугольников, базирующиеся на спиральных обобщенных

координатах для решеток из шестиугольников (рис. 1.г);

• обобщенные координаты для решеток из квадратов, основанные на кривых Пеано (рис.

1.д).

г. Обобщенные координаты лдя треугольной решегки, базирующиеся »а спиральных обобщенных для шестиугольной решетки

а. Спнраяьнью обобшетше координаты дня треугольной решетки

в. Спиральные обобщенные координаты для шестиугольной решетки

д. Обобщенные координаты для квадратной решетки, основанные на кривой Пеано Рис, 1. Примеры введения об об шейных координат

Приняв за единицу измерения производительности средние показатели самого медленного метода - спиральных координат для треугольной решетки, экспериментально установлено, что реализация спиральных координат для квадратной решетки функционирует в 3,9 раза быстрее, реализация обобщенных координат для треугольной решетки, базирующихся на спиральных координатах для шестиугольной - в 4,4 раза быстрее, а реализация спиральных координат для шестиугольной решетки - быстрее в 6,2 раза

Перечислим основные преимущества использовшгая обобщенных координат.

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

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

3. Одномерный массив можно рассматривать, как последовательность данных, а последовательность данных удобно сериализовывать и хранить.

4. Обобщенные координаты - это идея, которая может быть адаптирована под конкретную задачу с учетом, например, внутренней симметрии моделируемой системы и т.п.

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

6. Для некоторых решеток понятие декартовых координат неоднозначно. Например, для решетки шестиугольников неясно, почему клеткам необходимо присваивать одинаковые координаты вдоль той или иной оси, когда их центры не лежат на одной прямой параллельной этой оси. Для более "вычурных" решеток подобные проблемы еще актуальнее.

Возможность введения этпх и других разновидностей координат поддерживается разработанным в диссертации инструментальным средством. Обсуждаемые примеры введения обобщенных координат были апробированы при проведении вычислительных экспериментов.

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

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

• Среда выполнения - приложение с ясным и дружественным пользовательским интерфейсом. Базовой абстракцией в ней является понятие "эксперимент" -вычислительная задача, описанная в терминах клеточных автоматов. Среда может работать на однопроцессорном компьютере, многопроцессорной системе или в вычислительном кластере. Она имеет многодокументный интерфейс {Multi-Document Interface) для того, чтобы управлять несколькими экспериментами одновременно, а также реализовывать межавтоматные взаимодействия в процессе моделирования. Помимо этого она обеспечивает сохранение документов в формате XML (файлы с расширением "camel"), что позволяет пользователям хранить и обмениваться описаниями экспериментов. Для уменьшения размера этих файлов информация о состоянии решетки автомата, может быть

Стандартные компоненты

|Т Решётка

'¿''У^Кражпищё т. у данных

" ■■■ ... ,..г..,......—-—-—~

Пользовательские

ЯнВЯН h компоненты ,-

Правила

ч Настройки

"эксперимента v ______

ijii.si'V""

V^—;—--Ч*-:

An an изаторТАн an и за i о рТАнап и за i op);;

.-. .. ■■■■■■¿.»У .;--.. .К?-..^ :■■■;■ У

Библиотека CADLib

сжата внутри документа с помощью алгоритма B'/tp2. Рассматриваются основные принципы работы в среде, назначения всех пунктов меню, формат файлов и т. д.

• Стандартные компоненты - базовый набор решеток, хранилищ данных, метрик, правил и анализаторов, из которых могут быть построены решения пользовательских задач.

• Библиотека д;1я разработки клеточных автоматов CADLib ("Cellular Automata Development Library") - набор С+ +-классов, которые предназначены для создания пользователями новых компонентов, предназначенных для решения их задач. Приводятся описания большинства классов, функций, макроопределений и констант, содержащихся в библиотеке. Излагаются особенности использования библиотеки для создания компонентов.

Структурная схема, показывающая основные составные части предложен но it» инструментального средства и эксперимента, выполняемого в нем, приведена на рис 2.

Среда выполнения

Вычислительный эксперимент

Рис. 2. Структурная слома предложенного инструме!гтального средства и эксперимента в нем.

Жирным шрифтом |[а рисунке показаны три основные части инструментального срелстъа CAMEaL.

Вычислительный эксперимент, выполняемый а среде, характеризуется набором выбранных компонентов и установленными нас1рон*ами. Н набор компонентой может аходи^ъ произвольное ко-личссгао анализаторов, а также решетка, хранитище данных, метрика и правила в единственном экземпляре. Компоненты выбираются из числа стандартных (поставляемых и составе инструмснта;|ьногосредства) или пользовательских (разработанаык с

помощью библиотеки CADLib).

В главе описывается также использование компонентой модели декомпозиции клеточных автоматов при разработке пользовательских компонентов для проведения вычислительных экспериментов. See стандартные компоненты создавались аналогично.

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

В четвертой г.чаве приводятся результаты использования рассматриваемого инструментального средства для автоматизации проектирования программного обеспечения вычислительных экспериментов.

Первый из них был проведен для тестирования предложенного средства на однопроцессорной, многопроцессорной и кластерной вычислительных архитектурах, применения

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

Рассмотрим методику проведения вычислительных экспериментов с помощью предложенного инструментального средства на примере игры "Жизнь".

После запуска среды выполнения и создания в ней нового окна для проводимого эксперимента, в дереве компонентов необходимо выбрать набор' компонентов (решетку, хранилище данных, метрику и правила), которые будут использоваться в эксперименте.

В случае отсутствия требуемых компонентой, их необходимо создать. Опишем процедуру выбора и создания компонентов. ■ i : /

1. Выбор решетки. Как известно из описания игры "Жизнь1!; для ее моделирования требуется квадратная решетка. Компонент, реализующий функциональность такой решетки, имеется в наборе стандартных компонентов и называется "Square Basic Grid'.

2. Выбор метрики. Будем моделировать игру "Жизнь" в декартовых координатах. Компонент, реализующий функциональность декартовой метрики, существует в наборе стандартных компонентов и называется "Cartesians".

3. Выбор хранилища данных. Как известно из описания игры "Жизнь", при ее моделирований состояние клетки автомата описывается переменной булева типа. Таким образом, требуется компонент, реализующий функциональность хранилища булевых данных для декартовой метрики. Он имеется в наборе стандартных компонентов и называется "Booleans for Cartesians".

4. Выбор правил. Предположим, что компонент, реализующий правила игры "Жизнь" не входит в набор стандартных компонентов. Разработаем новый компонент и используем его в эксперименте.

4.1. Разработка компонента. Запустим средство разработки программ на языке программирования С++ (обычно - Microsoft Visual С++ 6) и создадим в нем библиотеку, содержащую класс требуемого компонента. Он должен был. наследником класса CAUniRules библиотеки CADLib, так как именно этот базовый класс обеспечивает независимость выполняемого компонента от вычислительной платформы. В разрабатываемом классе необходимо переопределить только функцию переходов SubCompute, которая примет вид:

Доступ к хранилищу данных. Переменная для хранения текущей клетки.

Массив для хранения соседей. Переменная для хранения числа "живых" соседей. Цикл по всем клеткам.

Обнуляем число "живых" соседей. Получаем идентификатор текущей клетки. ,

Получаем идентификаторы всех соседей.

Цикл по всем соседям.

Вычисляем количество "живых " соседей.

Если клетка "жива

она выживет при двух или трех "живых" соседях. Иначе (если клетка "мертва "}, она оживет при трех "живых" соседях. Эксперимент не закончен.

DATUM (CACrtsBool2DDatum) ; CACell c;

CACell neig[12]; int alive=0;

forICACell i-z.al; i<-z.bl; H + ) for(CACell j=z.a2; j<=z.b2; j++) { alive=0;

c=GET_METRICS->ToCell(i,;

GET_METRICS->GetNeighbours(c,neig) ,-

for (unsigned int k=0; k<GET_METRICS->GetUeighboarsCount (> ; k++) if (datum->Get(neig[k]))alive++;

if (datum->Get (c) )

datum->Set(c,alive=-21lalive^-i; ;

eise

datum->Set(c,alive=-3) ;

1

return true;

За основу компонента правил можно взять один из стандартных. Большую часть кода занимают операции общие для всех правил автомата: перебор клеток в цикле, доступ к соседям и т.п. Реализацию операций такого рода можно заимствовать из многочисленных примеров, которыми сопровождается инструментальное средство или из соответствующих статей автора и вспомогательных файлов. Те строки, которые имеют непосредственное отношение к логике игры "Жизнь" (тело функции переходов), выделены в приведенном фрагменте кода курсивом.

4.2. Компиляция компонента. Компонент, с помощью компилятора, собирается в .DLL-библиотеку.

4.3. Установка компонента в инструментальном средстве. Для установки, удаления и изучения компонентов в средстве CAMEtL имеется специальный инструмент, "Components Manager". Необходимо установить созданный компонент с его помощью.

4.4. Выбор компонента. Теперь новый компонент появится в дереве компонентов и его следует выбрать.

5. Настройка компонентов. Для проведения описываемого эксперимента необходимо установить значение параметра "Double" хранилища данных "Booleans for Cartesians" в значение "true", выбрав тем самым синхронный клеточный автомат для моделирования, так как игра "Жизнь" должна выполняться именно на синхронном автомате. Когда все описанные действия выполнены, можно переходить к запуску вычислительного эксперимента. Перед этим пользователь имеет возможность изменить начальные состояния клеток.

На уровне базового класса, в разработанном компоненте правил, имеется параметр "Platform", позволяющий выбрать платформу (однопроцессорную, многопроцессорную или кластерную), на которой будет выполняться эксперимент.

В случае если была выбрана кластерная платформа, то достаточно запустить эксперимент только на одной вычислительной машине кластера. Эта машина станет "владельцем эксперимента". Среда выполнения, запущенная на ней, разделит решетку на части, сопоставит идентификаторы всем вычислительным узлам сети и отправит каждому из них фрагмент решетки, с которым тому предстоит работать. Для этого на вычислительных узлах, вовлеченных в эксперимент, должна быть открыта среда выполнения, входящая в состав предложенного инструментального средства.

Главная функция "владельца эксперимента" заключается в том, что он управляет и координирует выполнение шагов остальными узлами и именно на этом вычислительном узле формируется состояние всей решетки в целом.

Если принять за единицу измерения промежуток времени, требуемый для выполнения одной итерации при моделировании игры "Жизнь" для однопроцессорной платформы, то экспериментально было установлено, что на двухпроцессорной вычисления выполняются в 1,9 раза быстрее2, а на кластерной из четырех вычислительных узлов - в 3,5 раза быстрее3. Измерения проводились, используя решетку размером 1001x1001 клетку.

При моделировании игры "Жизнь" на кластерной платформе, при возникновении популяции "планер", можно наблюдать интересный эффект: перемещаясь по решетке, планер будет перелетать с одного вычислительного узла на другой. В таблице 2 показан этот эффект: для двух вычислительных узлов, которые делят решетку так, что клетки с координатами абсцисс

2 Сравнивалось среднее время, необходимое на выполнение итерации при помощи вычислительного узла на базе процессора AMD Athlon XI 4800+ и двумя гигабайтами памяти с использованием разработанного компонента правил, работающего в режимах однопроцессорной и многопроцессорной вычислительных архитектур.

Сравнивалось среднее время, необходимое на выполнение итерации на одном и на четырех вычислительных узлах на базе процессоров Intel Pentium 4 3400 и одним гигабайтом памяти с использованием разработанного компонента правил, работающего в режимах однопроцессорной и кластерной вычислительных архитектур. При работе в кластере, четыре узла были соединены в квадрат с помощью сети Ethernet 100. Задача делилась на четыре часта, один из ухтов выступал и как "владелец", и как вычислитель.

1 U) Ni j - сз Е

ШШШШШШШШШШШШ ШШШШШШ (ШИШЕ шгашшшшшмшшш ЕШШШШЙШШШШШШ шшшшшшшшшшшш шшишш шшшшшш ШШШЕШШ шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш & s к i Й " « я п § si TJ kj 1 о

ШШШШШШ шшшшшш шшшшшш ШШШЙШШШШШШШШ шшшшшшшшшшшш шшшшшшшшшшшш ШШШШШШ шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш

- о чО оо -J SK 3 s? В £ ' С

ЬШШШШШ щшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш ШШШШШШ шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш ЕШЕГГ Ш шшшшшш шшшшшш 8 CT s g 3 g

шшшшшш шшшшшш ШШШЕППШ шшшшшшшшшшшш ШШШШШШ шшшшшш шшшшшшшшшшшш ШШШШШШ шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш шшшшшш ft» g < й = g ® to

меньшими либо равными минус двум принадлежат первому узлу, а с большими - второму. Приведены фрагменты решеток на первых двенадцати шагах.

Для того чтобы промоделировать игру "Жизнь" в спиральных обобщенных координатах для квадратной решетки, необходимо выбрать другой компонент-метрику (а именно, "Square Grids Generalized') и, как следствие, другое хранилище данных ("Booleans for Generalized'). Изменений в правила вносить не потребуется.

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

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

Все возможные функции переходов одномерного клеточного автомата с окрестностью, состоящей из правой и левой соседних клеток, были пронумерованы целыми числами от 0 до 255. Двоичную запись номера функции можно получить, транспонировав столбец матрицы переходов, содержащий результирующие состояния. Для точечного зародыша были построены все 256 возможных структур. Далее они были сгруппированы в различные классы, используя разнообразные классы эквивалентности.

Простейшая, классификация, получившая название ¿"-классификации4 (от англ. "Equality"), представляет собой объединение в один класс идентичных структур. Далее, при ¿^/-классификации (от англ. "Inverse"), в один класс попадают одинаковые структуры, а также те из них, которые являются инверсией друг друга При £М-классификации (от англ. "Mirror"), в одном классе оказываются идентичные структуры и те из них, которые представляют собой зеркальное отображение друг друга. При Е/М-классификации, в одном классе оказываются одинаковые структуры, а также те из них, которые представляют собой зеркальное отображение или инвертированную версию друг друга. При £(/+А/)-классификации, в одном классе оказываются идентичные структуры и те из них, которые представляют собой инвертированное зеркальное отображение друг друга

Далее все эти классификации были выполнены с точностью до сдвига вверх, вниз, вправо или влево на одну клетку. Так появились ЕО-, EIO-, ЕМО-, EIMO- и £(/+Л/)0-классификации (от англ. "Offset'). Затем было решено проверять принадлежность структуры классу, допуская несовпадения в состояниях от одной до пяти клеток. Так появились ELn-, EILn-, EMLn-, EIMLn-, E(I+M)Ln-, а также EOLn-, EIOLn-, EMOLn-, EIMOLn-, £(/+Л/)0£и-классификации (от англ. "Lapse"), где n может принимать значения от одного до пяти. Можно считать, что первые построенные варианты классификации относились к ¿О-классификациям.

Показано, что существуют автоматы с клетками с памятью и с клетками без памяти, демонстрирующие одинаковое поведение.

Таким образом, в работе выполнен детальный анализ простейших клеточных автоматов, порождающих сложное поведение (в том числе, самовоспроизведение).

В заключительном разделе главы описан набор средств, разработанный для того, чтобы выполнять вычислительные эксперименты с помощью инструментального средства CAMEiL на FPGA-CBCreuax (Field Programmable Gate Array). Это расширяет множество вычислительных архитектур, на которых могут быть организованы вычислительные эксперименты, используя метод и инструментальное средство, разработанные в диссертации.

4 Было решено называть варианты классификации по аналогии с вариантами классификаций булевых функций.

Идея использования FPG^-npoueccopoB для выполнения вычислений при помощи клеточных автоматов не нова. Применение этих систем позволяет существенно повысить эффективность вычислений. При использовании FPGA-процессоров, вычисления могут производиться в тысячи раз быстрее, чем па однопроцессорном персональном компьютере. Так, например, Университет Эдинбурга (Шотландия) недавно создал и использует мощпейший суперкомпьютер "Maxwell", состоящий из вычислительных узлов, на основе FPG/1-процессоров, отличающийся чрезвычайно низким, для подобного компьютера, энергопотреблением.

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

Таким образом, инструментальное средство CAMEtL обеспечивает автоматизацию проектирования программного обеспечения FPG/f-систем, а методы, изложенные в настоящей работе, имеют практическую ценность для автоматизации проектирования различных устройств и вычислительных систем.

Заключение

В диссертации получены следующие результаты:

1. Введено понятие "обобщенных координат" для решеток клеточных автоматов. Разработан метод введения таких координат.

2. На основе метода введения обобщенных координат разработано инструментальное средство автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клегочных автоматов CAME*L.

3. Метод и инструментальное средство САМЕ.Х апробированы при автоматизащш проектировать программного обеспечения ряда вычислительных экспериментов с использованием клеточных автоматов на однопроцессорной, многопроцессорной и кластерной и FPGA вычислительных системах. Ранее было невозможно выполнить это с помощью одного и того же инструментального средства.

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

5. Результаты были внедрены в учебном процессе и при проведении научных исследований в ряде университетов.

На основе выполненной работы создан информационный ресурс "CAMEL Laboratory" -http://cameilab.spb.ru, который содержит инструментальное средство CAMEsL, доступное для свободного использования вместе с множеством разработанных компонентов и примеров его применения.

Список публикаций

1. Наумов Л. Как увеличить скорость "Жизни", или Эффективная организация дашшх для повышения скорости поиска клеток и разрешения отношений соседства при реализации клеточного автомата Джона Хортона Конвея "Жизнь". Части I и II // Информатика. -2001. - № 33 (322) - С. 25-27; - № 34 (323) - С. 20-24.

2. Наумов Л. Как увеличить скорость "Жизни", или Эффективная организация данных для повышения скорости поиска клеток и разрешеши отношений соседства при реализации

клеточного автомата Джона Хортона Конвея: "Жизнь" // Компьютеры + Программы. -2001.-№ 10 — С. 68-73.

3. Naumov L. Generalized Coordinates for Cellular Automata Grids / Computational Science - ICCS 2003. - Springer-Verlag. - 2003. Part 2 - pp. 8(59-878.

4. Наумов J!., Шалыто А. Клеточные автоматы. Реализация и эксперименты // Мир ПК. -2003.-№8-С. 71-78.

5. Наумов Л. СЛМЕ Л . - среда моделирования и библиотека разработчика клеточных автоматов / Труды XI Всероссийской научно-методической конференции Телематика'2004. - СПб.: СПбГУ ИТМО. - 2004. - Том 1 - С. 184-186.

6. Наумов Л. СТР (Commands Transfer Protocol) - Сетевой протокол для высокопроизводительных вычислений / Труда XI Всероссийской научно-методической конференции Телематика'2004. - СПб.: СПбГУ ИТМО. - 2004. Том 1 - С. 188-189.

7. Наумов Л., Шалыто А. "Цветные" клеточные автоматы // Мир ПК. - 2004. - № 5 - С. 64-71.

8. Naumov L. CAMEiL - Cellular Automata Modeling Environment & Library / Cellular Automata. Sixth International Conference on Cellular Automata for Research and Industry, ACRI-2004. -Springer-Verlag. - 2004 - pp. 735-744.

9. Наумов Л. СТР (Commands Transfer Protocol) v. 1.2 - Новая версия сетевого протокола для высокопроизводительных вычислений / Труда XII Всероссийской научно-методической конференции Телемэтика'2005. - СПб.: СПбГУ ИТМО. - 2005. Том 1 - С. 92-93.

10. Наумов Л. CAMEiL - средство для осущестЕления параллельных и распределенных вычисления на основе клеточных автоматов / Технологии распределенных вычислений. — 2005-С. 284-286.

11. Наумов Л. Решение задач с помощью клеточных автоматов посредством программного обеспечения CAMEiL (Части I и II) // Информационно-управляющие системы. - 2005. -№ 5 - С. 22-30; - № 6 - С. 30-38.

12. Наумов Л., Шалыто А. Классификация структур, порождаемых одномерными двоичными клеточными автоматами из точечного зародыша // Известия РАН. Теория и системы управления. - 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.

13. Наумов Л. Сравните специализированных сетевых протоколов СТР (Commands Transfer Protocol) и IL (Internet Link) / Труды ХШ Всероссийской научио-методической конференции Телематика'2006. - СПб.: СПбГУ ИТМО. - 2006. Том 1 - С. 266-267.

14. Наумов Л. Обзор программного обеспечения для решения задач с использованием клеточных автоматов // Телекоммуникации и информатизация образования. - 2006. - № 2 -С.114-125.

Тиражирование и брошюровка выполнены в це1гтре "Университетские телекоммуникация", Са[псг-Пстербург, Кронверкский пр., д. 49; тел.: (812) 233-46-69 Тираж 100 экз.

ВВЕДЕНИЕ.

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КЛЕТОЧНЫХ АВТОМАТОВ. ОБЗОР ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ ДЛЯ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ С ИХ ИСПОЛЬЗОВАНИЕМ.

1.1. Введение в историю и идеологию клеточных автоматов.

1.2. Определение клеточного автомата.

1.3. Теорема о трех двумерных решетках из правильных многоугольников.

1.4. Кольца. Свойства колец.

1.5. Метрика.

1.6. Теорема об эквивалентности клеточного автомата набору конечных автоматов.

1.7. Аппаратные и программные реализации клеточных автоматов.

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

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

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

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

Выводы по главе 1.

ГЛАВА 2. МЕТОД ВВЕДЕНИЯ ОБОБЩЕННЫХ КООРДИНАТ ДЛЯ РЕШЕТОК КЛЕТОЧНЫХ АВТОМАТОВ.

2.1. Основы метода введения обобщенных координат для решеток клеточных автоматов.

2.2. Спиральные обобщенные координаты для квадратной решетки.

2.3. Спиральные обобщенные координаты для шестиугольной решетки

2.4. Спиральные обобщенные координаты для треугольной решетки.

2.5. Обобщенные координаты для треугольной решетки, базирующиеся на спиральных обобщенных координатах для шестиугольной решетки.

2.6. Обобщенные координаты для квадратной решетки, основанные на кривой Пеано.

2.7. Преимущества обобщенных координат. Изоморфизм двумерных решеток.

Выводы по главе 2.

ГЛАВА 3. РАЗРАБОТКА ИНСТРУМЕНТАЛЬНОГО СРЕДСТВА CAME&L ДЛЯ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ

ЭКСПЕРИМЕНТОВ С ПОМОЩЬЮ КЛЕТОЧНЫХ АВТОМАТОВ.

3.1. Принципы проектирования предлагаемого инструментального средства.

3.2. Среда выполнения.

3.2.1. Главное окно и окна документов.

3.2.2. Главное меню.

3.2.2.1. Меню W.

3.2.2.2. Меню "Edit".

3.2.2.3. Меню "View".

3.2.2.4. Меню "Modeling".

3.2.2.5. Меню "Tools".

3.2.2.6. Меню "Debug".

3.2.2.7. Меню "Window".

3.2.2.8. Меню "Help".

3.2.3. Формат файлов документов.

3.3. Библиотека для разработки клеточных автоматов CADLib.

3.3.1. Диаграмма классов библиотеки.

3.3.2. Ключевые классы.

3.3.3. Класс CAComponent.

3.3.4. Классы CAUnion и CAUnionMember.

3.3.5. Класс CAGrid.

3.3.6. Класс CAMetrics.

3.3.7. Класс CADatum и шаблоны CATypedDatum, CABasicCrtsDatum, CABasicGenDatum.

3.3.8. Класс CARules.

3.3.9. Классы параметров компонентов и диалогов для запросов значений параметров.

3.4. Разработка библиотеки, содержащей компонент.

Выводы по главе 3.

ГЛАВА 4. ПРИМЕНЕНИЕ ИНСТРУМЕНТАЛЬНОГО СРЕДСТВА CAME&L ДЛЯ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ С ИСПОЛЬЗОВАНИЕМ КЛЕТОЧНЫХ АВТОМАТОВ.

4.1. Проектирование вычислительных экспериментов с помощью инструментального средства CAME&L.

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

4.2.1. Простая реализация, без указания вычислительной архитектуры и оптимизации.

4.2.2. Реализация с зональной оптимизацией.

4.2.3. Реализация для многопроцессорной системы.

4.2.4. Реализация для вычислительного кластера.

4.2.5. Реализация для обобщенных координат.

4.2.6. Универсальная реализация, не зависящая от вычислительной платформы.

4.3. Проектирование и реализация клеточного автомата для решения уравнения теплопроводности.

4.4. Проектирование и реализация вычислительного эксперимента для классификации структур, порождаемых одномерными двоичными клеточными автоматами из точечного зародыша.

4.4.1. Задание функции переходов одномерного двоичного клеточного автомата.

4.4.2. Начальные условия.

4.4.3. Инвариантность относительно операции "равенство".

4.4.3.1. Поведение типа "салфетка Серпинского".

4.4.3.2. Поведение типа "двоичный треугольник Паскаля".

4.4.4. Инвариантность относительно операций "равенство" и "инверсия".

4.4.5. Инвариантность относительно операций "равенство" и "зеркальное отображение".

4.4.6. Инвариантность относительно операций "равенство", "инверсия" и "зеркальное отображение".

4.4.7. Инвариантность относительно операций "равенство" и "инверсно-зеркальное отображение".

4.4.8. Классификации с учетом сдвигов на одну клетку.

4.4.9. Классификации с учетом погрешностей.

4.4.10. Дополнительные материалы.

4.5. Автоматизация проектирования программного обеспечения FPGA-систем с помощью инструментального средства CAME&L.

4.6. Практическое использование результатов работы.

Выводы по главе 4.

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

Принимая во внимание то обстоятельство, что сейчас при разработке сложных программно-аппаратных комплексов значительная доля затрат идёт на разработку программного обеспечения и эти показатели неуклонно растут, необходимость создания инструментального средства для автоматизации проектирования программного обеспечения систем с параллельной и распределенной вычислительными архитектурами становится актуальной.

Существует ряд математических моделей параллельных и распределенных вычислений. Одной из них являются клеточные автоматы [1,2], применению которых и посвящена настоящая диссертация.

Клеточные автоматы [3] - это дискретные динамические системы, поведение которых может быть полностью описано в терминах локальных зависимостей [1]. Эти автоматы представляют собой модели параллельных вычислений, которые обладают сколь угодно большой степенью параллелизма. Можно считать, что они представляют собой дискретный эквивалент понятия "поле". Клеточные автоматы применяются для проведения различных вычислительных экспериментов, так как они удобны, например, для численного решения дифференциальных уравнений и уравнений в частных производных. Они также широко используются для моделирования поведения сложных систем [2,4,5].

Существует ряд средств автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов таких, как, например, средство SIMP/STEP (реализующее набор функций для решения задач физического моделирования), CAGE (инструмент для образовательных целей) или Mirek's Cellebration (.MCell) (средство для визуализации) и CDL (инструмент, позволяющий использовать FPGA-системы для выполнения вычислительных экспериментов). Однако все эти средства имеют ограничения, которые накладываются на предметные области решаемых задач, реализуемые клеточные автоматы или используемые вычислительные архитектуры. Не существует единого средства, пригодного, как для образовательных, так и для научных целей. Поэтому для автоматизации проектирования программного обеспечения вычислительных экспериментов на основе клеточных автоматов необходимо разработать универсальное, расширяемое инструментальное ■ средство, обладающее широким спектром функциональных возможностей, так как существующие инструменты не позволяют решать разнообразные задачи из различных предметных областей с помощью широкого спектра клеточных автоматов. Так, например, далеко не каждое средство позволяет моделировать автоматы, как с двумерными, так и с трехмерными решетками. Малая их часть поддерживает использование разнообразных окрестностей. Например, окрестность Марголуса поддерживают всего несколько специализированных средств. Не одно из них не допускает хранения строк в клетках, что необходимо при реализации задач параллельного синтаксического анализа. Только некоторые позволяли описывать структуры данных, хранимые в клетках.

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

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

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

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

Основные задачи диссертационной работы состоят в следующем.

1. Разработка метода введения обобщенных координат для решеток клеточных автоматов.

2. Разработка на основе метода введения обобщенных координат инструментального средства CAME&L [6, 83-85] {Cellular Automata Modeling Environment & Library), включающего в себя среду выполнения и библиотеку для создания клеточных автоматов, которое предназначено для автоматизации проектирования программного обеспечения вычислительных экспериментов с их использованием.

3. Применение инструментального средства САМЕлЬ для автоматизации проектирования программного обеспечения ряда вычислительных экспериментов с использованием клеточных автоматов на различных вычислительных архитектурах.

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

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

1. Метод введения обобщенных координат для клеточных автоматов обеспечивает единообразие представления данных для автоматов с различными решетками, в том числе, и разной размерности.

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

Методы исследования. В работе использованы методы теории автоматов, теории множеств, теории параллельных вычислений, теории алгоритмов, математической физики, основы объектно-ориентированного программирования.

Достоверность н обоснованность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается доказательствами, обоснованием постановок задач, точной формулировкой критериев, компьютерным моделированием, а также результатами использования методов, предложенных в диссертации, в ходе выполнения вычислительных экспериментов.

Практическое значение работы состоит в том, что разработано универсальное и расширяемое инструментальное средство CAME&L для автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием широкого спектра клеточных автоматов, которое позволяет проводить вычислительные эксперименты на однопроцессорных, многопроцессорных и кластерных платформах.

Реализация результатов работы (имеются акты внедрения). Для образовательных целей результаты используются в Санкт-Петербургском государственном университете информационных технологий, механики и оптики (СПбГУ ИТМО), в Санкт-Петербургском государственном университете и в Университете Амстердама (Нидерланды). Для научно-исследовательских целей результаты используются в СПбГУ ИТМО, в

Университете Амстердама и в Политехническом университете Бухареста (Румыния).

Научно-исследовательские работы. Результаты диссертации получены в ходе выполнения в СПбГУ ИТМО научно-исследовательских работ по теме "Разработка технологии автоматного программирования", выполненной по грату РФФИ № 02-07-90114 в 2002-2003 годах; по теме "Разработка технологии программного обеспечения систем управления на основе автоматного подхода", выполняемой по заказу Министерства образования РФ в 2002-2005 годах; по гранту конкурса персональных грантов для студентов и аспирантов вузов Санкт-Петербурга в 2004 году; по теме "Разработка среды и библиотеки "CAMEJL" для организации параллельных и распределенных вычислений на основе клеточных автоматов", выполненной по гранту РФФИ № 05-07-90086 в 2005-2006 годах. При выполнении работ по этому гранту автор был ответственным исполнителем. Научно-исследовательская деятельность автора дважды отмечена стипендией Президента РФ.

Апробация результатов работы. Основные положения диссертационной работы докладывались на международной научной конференции "International Conference of Computational Sciences" (Санкт-Петербург - Мельбурн, 2003 г.), на международной научной конференции "Cellular Automata for Research and Industry" (Амстердам, 2004 г.), на научной школе "Joint Advanced Students School" (Санкт-Петербург, 2004 г.), на научно-методических конференциях "Телематика-2004", "Телематика-2005", "Телематика-2006" (Санкт-Петербург), на научной школе "Ferienakademie" (Южный Тироль, 2005 г.), на всероссийской научной конференции "Научный сервис в сети Интернет: технологии распределенных вычислений" (Дюрсо, 2005 г.), на международной научной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (Санкт-Петербург, 2006 г.).

Публикации. По теме диссертации опубликовано 14 печатных работ, в том числе, в журналах "Известия РАН. Теория и системы управления" (входит в перечень ВАК), "Информационно-управляющие системы", "Телекоммуникации и информатизация образования", а также в материалах конференций "International Conference of Computational Sciences", "Cellular Automata for Research and Industry", "Телематика" и "Научный сервис в сети Интернет: технологии распределенных вычислений".

Структура диссертации. Диссертация изложена на 283 страницах и состоит из оглавления, введения, четырех глав, заключения, списка терминов, предметного указателя, списка литературы и двух приложений. Список литературы состоит из 97 наименований. Работа содержит 44 рисунка и 13 таблиц.

Выводы по главе 4

1. Описан процесс проектирования вычислительных экспериментов на основе клеточных автоматов с помощью разработанного инструментального средства САМЕлЬ.

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

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

4. Разработан подход и набор инструментов для автоматизации проектирования программного обеспечения вычислительных экспериментов с помощью клеточных автоматов на FPGA-системах, что расширяет область использования инструментального средства САМЕлЬ.

5. Показано, что инструментальное средство CAMEaL успешно внедрено в учебный и научно-исследовательский процессы ряда университетов.

Заключение

В настоящей работе разработаны метод введения обобщенных координат для клеточных автоматов, обеспечивающий универсальность организации данных для разнообразных решеток произвольной размерности, а также инструментальное средство САМЕлЬ для автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов, которое обеспечивает единообразие подхода к решению задачи вне зависимости от применяемой вычислительной платформы. При этом отметим, что разработанный метод вносит вклад в теорию клеточных автоматов, что подтверждается публикацией в материалах одной из крупнейших конференций по вычислительным наукам "Cellular Automata for Research and Industry" (Амстердам, 2004).

Проект САМЕлЬ - первая попытка создания универсального расширяемого инструмента, пригодного для проведения широкого круга вычислительных экспериментов с помощью клеточных автоматов. Библиотека CADLib, входящая в пакет, обладает широким спектром функциональных возможностей. Например, она обеспечивает детальное описание клеточных автоматов, сбор статистики, анализ и вывод полученных данных в различных формах и т.д.

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

Одним из ключевых преимуществ, которыми обладает предложенное средство, является поддержка проведения вычислительных экспериментов с помощью разнообразных метрик и, в частности, обобщенных координат.

В работе приводятся примеры использования разработанного инструментального средства для ряда предметных областей и вычислительных платформ. Так, в частности, описан набор средств для автоматизации проектирования программного обеспечения FPGA-систем с помощью инструментального средства CAME*L.

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

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

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

2. На основе метода введения обобщенных координат разработано универсальное и расширяемое инструментальное средство автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов САМЕлЬ.

3. Метод и инструментальное средство САМЕлЬ апробированы при автоматизации проектирования программного обеспечения ряда вычислительных экспериментов с использованием клеточных автоматов на однопроцессорной, многопроцессорной и кластерной и FPGA вычислительных системах. Это было невозможно выполнить ранее с помощью одного и того же инструментального средства.

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

5. Результаты были внедрены в учебном процессе и при проведении научных исследований в ряде университетов.

На основе выполненной работы создан информационный ресурс "CAMEL Laboratory" - http: / /cameilab. spb. ru, который содержит инструментальное средство CAMEaL, доступное для свободного использования вместе с множеством разработанных компонентов и примеров его применения.

1. Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир. 1991.

2. Wolfram S. A New Kind of Science. Wolfram Media Inc. 2002.3. фон Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир. 1971.

3. Cellular Automata. Ed. Р.М.А. Sloot, В. Chopard, A. Hoekstra / Sixth International Conference on Cellular Automata for Research and Industry, ACRI-2004. Springer-Verlag. 2004.

4. Sarkar P. A Brief History of Cellular Automata // ACM Computing Surveys. Vol. 32.2000. №1.

5. Сайт "CAMEL Laboratory" http: //cameilab. spb. ru.

6. Ulam S. Random Processes and Transformations / Proceedings of the International Congress of Mathematicians. Rhode Island: American Mathematical Society. 1952. Vol. 2.

7. Zuse K. Calculating Space. Massachusetts Institute of Technology Technical Translation AZT-70-164-GEMIT (Project MAC). Cambridge. 1970.

8. Hedlung G. A. Endomorphism and Automorphism of the Shift Dynamic System // Mathematical Systems Theoiy. 1969. № 3.

9. Holland J. Universal Spaces: A Basis for Studies in Adaptation // Automata Theoiy. Academic Press. 1966.

10. Richardson D. Tessellation with Local Transformations // Journal of Computer and System Sciences. 1972. № 6.

11. Варшавский В.И, Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. М.: Энергия. 1973.

12. Qi A., Zheng X., Du С, An В. A cellular automation model of cancerous growth // Journal of Theoretical Biology. 1993. № 161.

13. Mansury Y., Kimuraz M., Lobozy J., Deisboeck T. S. Emerging Patterns in Tumour Systems: Simulating the Dynamics of Multicellular Clusters with an Agent-based Spatial Agglomeration Model // Journal of Theoretical Biology. 2002. №219.

14. Dormann S., Deutsch A. Modeling of self-organized avascular tumour growth with a hybrid cellular automaton // In Silico Biology 2.2002.

15. Moore J., Hahn L. A cellular automata approach to detecting interactions among single-nucleotide polymorphisms in complex multifactorial diseases / Pacific Symposium on Biocomputing. 2002.

16. Ward D.P., Murray А. Т., Phinn S.R. An optimized cellular automata approach for sustainable urban development in rapidly urbanizing regions / Geocomutation 1999.1999.

17. Chopard В., Luthi P., Masselot A. Cellular automata and lattice boltzmann techniques: An approach to model and simulate complex systems // Advances in Physics, submitted, 1998. № 137.

18. Sullivan A., Knight I. A hybrid cellular automata/semi-physical model of fire growth / Proceedings of the 7th Asia-Pacific Conference on Complex Systems. 2004.

19. Chavez F., Vicente L. Cellular automata approach to dissociative adsorption of diatomic molecules on a substrate with reconstruction // Molecular Physics. Vol. 96. 1999. №6.

20. Swiecicka A., Seredynski F. Cellular automata approach to scheduling problem // Parallel Computing in Electrical Engineering. 2000. № 1.

21. Janowicz M, Orlowski A. Cellular automaton approach to light propagation in dispersive periodic and disordered media // Transparent Optical Networks. Vol. 2. 2004.

22. Lee et. al Adaptive Stochastic Cellular Automata: Theory // Physica D: Nonlinear Phenomena. Cellular Automata: Theory and Experiment, 1990.

23. Janawicz M., Ashbourn J., Orlowski A., et al Cellular automaton approach to electromagnetic wave propagation in dispersive media // Royal Society of London. Vol. 462.2006 № 2074.

24. Biondini F., Bontempi F., Frangopol D., Malerba P. Cellular Automata Approach to Durability Analysis of Concrete Structures in Aggressive Environments // J. Struct. Engrg. Vol. 130.2004. № 11.

25. Keedwell E., Soon-Thiam K. Novel Cellular Automata Approach to Optimal Water Distribution Network Design // J. Сотр. in Civ. Engrg. Vol. 20.2006. № 1.

26. Zoran A. Computation in Inhomogenous Celluar Automata / Complex Systems: From Biology to Computation. 2003

27. Gardner M. The Fantastic Combinations of John Conway's New Solitaire Game "Life" // Scientific American. 1970. № 223.

28. Гарднер M. Математические досуги. M.: Мир. 1972.

29. Гарднер М. Крестики-нолики. М.: Мир. 1988.

30. Berlekamp К, Conway J. Guy R. What Is Life? // Winning Ways. Vol. 2. Academic Press. 1982.

31. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). М.: Наука. 1978.

32. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь. 1987.

33. Шалыто А. А. Switch-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. 1998.

34. Margolus N. САМ-8: computer architecture based on cellular automata / Pattern Formation and Lattice-Gas Automata. Addison-Wesley. 1996.

35. Броуди JI. Начальный курс программирования на языке FORTH. М.: Финансы и статистика. 1990.

36. Toffoli Т. Cellular Automata Mechanics // Tech. Rep. 208. Сотр. Comm. Sci. Dept., The University of Michigan. 1977.

37. Сайт "Sigis.net"-http://lamp.sigis.net/article/articleview/2/1/5/.39. Сайт "UCLA Gateway" ftp://ftp.lifesci.ucla.edu/pub/alife/public/cam.zip.

38. Сайт Доменико Талия http://isi-cnr.deis.unical.it:1080/~talia/.

39. MacDonald N., Minty E., Harding Т., Brown S. Writing Message Passing Parallel Programs with MPI Edinburgh Parallel Computing Center. The University of Edinburgh. 1996.

40. Spezzano G., Talia D. Designing Parallel Models of Soil Contamination by the CARPET Language. 1998.

41. Сайт "Department of Computer Science San Jose State University"http://www.mathcs.sj su.edu/capow/capow4a.zip.

42. Сайт "Friedrich-Schiller-Universitat" http://www.unijena.de/~msk/bin/casim.tar.gz.

43. Сайт "Gesellschaft fur Mathematik und Datenverarbeitung"ftp://ftp.gmd.de:/GMD/cat/.

44. Сайт "Technische Universitat Darmstadt" ftp: //ftp. informatik. thdarmstadt.de/pub/MP/CDL/.47. Сайт "Essex.ac.uk" ftp://ftp.essex.ac.uk/pub/robots/ArtificialLife/public/cdm/.

45. Сайт "Index Librorum Liberorum by John Walker"http://www.fourmilab.ch/cellab/cellab.zip.

46. Сайт "Santa Fe Institute. Artificial Life"ftp: //alife.santafe■edu/pub/SOFTWARE/Cellsim/.50. Сайт "Radford University" ftp://rucs2.sunlab.cs.runet.edu/pub/ca/cellular.tar.gz.

47. Сайт "Santa Fe Institute" ftp: //ftp. santafe. edu/pub/wuensch/.

48. Сайт Томаса Уорша http; //liinwww. ira. uka. de/~worsch/.

49. Сайт "Departamento De Computacion. Cinvestav"http://delta.cs.cinvestav.mx/~mcintosh/newweb/software.html.

50. Сайт "Mirek's Free Software Site" http: / / www. mi re kw. com.5 5. Сайт "Mirek's Personal Homepage" http: / / www. mi rwo j. opus. che lm. pi /.

51. Сайт "Pea Soup" http://psoup.math.wisc.edu/mcell/.

52. Сайт Мартина Кутриба http: //www. inf ormatik. uni-giessen.de/staff/kutrib.html.

53. Сайт "BU Programmable Matter" http: //pm.bu. edu/step.

54. Сайт "University of Wisconsin-Madison. Mathematics Department"ftp://cam8.math.wise.edu/pub/winca 10.exe.

55. Sagan H. Space Filling Curves. Springer. 2006.

56. Bungartz H-J., Mehl M., Weinzierl T. A Parallel Adaptive Cartesian PDE Solver Using Space-Filling Curves / Proceedings of "Euro-Par 2006". 2006.

57. Страуструп Б. Язык программирования С++. СПб: Невский диалект. 1999.

58. Weimar J.R. Simulation with Cellular Automata. Braunschweig. 1996.

59. Спэйнауэр С., Экштейн P. Справочник вебмастера. СПб.: Символ-Плюс. 2001.

60. Мешков А., Тихомиров Ю. Visual С++ и MFC. СПб.: БХВ-Санкт-Петербург. 2000.

61. Сайт "GNU + Cygnus + Windows = Cygwin" http: / /www. cygwin. com.

62. Гордеев А., Молчанов А. Системное программное обеспечение. СПб.: Питер. 2001.

63. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. М.: Триумф. 2003.

64. Газете М. Гномон. От фараонов до фракталов. Москва-Ижевск: Институт компьютерных исследований. 2002.

65. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект. 2001.

66. Сайт кафедры "Технологии программирования" Санкт-Петербургского государственного университета информационных технологий, механики И оптики http://is.ifmo.ru.

67. WolfW. FPGA-Based System Design. Prentice Hall Ptr. 2004.

68. Lee S. Advanced Digital Logic Design Using VHDL, State Machines, and Synthesis for FPGA's. Thomson-Engineering. 2005.

69. Coffman K. Real World FPGA Design with Verilog. Prentice Hall Ptr. 1999.

70. Woudenberg M. Using FPGAs to Speed Up Cellular Automata Computations / Master's thesis for University of Amsterdam. 2006.

71. Venkatachalam D. Reconfigurable Processors: Changing the Systems Design

72. Paradigm, http: //www. techonline. com/coromunity/ed resource/ featurearticle/38022.

73. Shackleford В., Tanaka M., Carter R.J., Snider G. FPGA Implementation of Neighborhood-of-Four Cellular Automata Random Number Generators / Proceedings of FPGA'2002.2002.

74. Halbach M., Hoffmann R. Implementing Cellular Automata in FPGA Logic / Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS*04). 2004.

75. Керниган R, Пайк P. UNIX. Программное окружение. СПб.: Символ-Плюс. 2003.

76. Pedroni V. Circuit Design with VHDL. The MIT Press. 2004.82. Xilinx APPnote 213.http://direct.xilinx.com/bvdocs/appnotes/xapp213.pdf.

77. Публикации автора по теме диссертации

78. 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.

79. Наумов Л. CAME&L среда моделирования и библиотека разработчика клеточных автоматов / Труды XI Всероссийской научно-методической конференции Телематика'2004. Том 1. СПб.: СПбГУ ИТМО. 2004. с. 184-186.

80. Наумов Л. CAME&L средство для осуществления параллельных и распределенных вычисления на основе клеточных автоматов / Технологии распределенных вычислений. 2005. с. 284-286.

81. Наумов Л., Шалыто А. Клеточные автоматы. Реализация и эксперименты // Открытые системы. Мир ПК. 2003. №8. с. 71-78.

82. Наумов Д, Шалыто А. "Цветные" клеточные автоматы // Открытые системы. Мир ПК. 2004. №5. с. 64-71.

83. Наумов Л. Как увеличить скорость "Жизни", или Эффективная организация данных для повышения скорости поиска клеток и разрешения отношений соседства при реализации клеточного автомата

84. Джона Хортона Конвея "Жизнь". Части I и II // Информатика. 2001. № 33 (322). с. 25-27; № 34 (323). с. 20-24.

85. Наумов Л. Обзор программного обеспечения для решения задач с использованием клеточных автоматов / Телекоммуникации и информатизация образования. 2006. №2. с. 114-125.

86. Наумов Л. СТР (Commands Transfer Protocol) Сетевой протокол для высокопроизводительных вычислений / Труды XI Всероссийской научно-методической конференции Телематика'2004. Том 1. СПб.: СПбГУ ИТМО. 2004. с. 188-189.

87. Наумов Л. СТР (Commands Transfer Protocol) v. 1.2 Новая версия сетевого протокола для высокопроизводительных вычислений / Труды XII Всероссийской научно-методической конференции Телематика'2005. Том 1. СПб.: СПбГУ ИТМО. 2005. с. 92-93.

88. Наумов Л. Сравнение специализированных сетевых протоколов СТР (Commands Transfer Protocol) и IL (Internet Link) / Труды ХП1 Всероссийской научно-методической конференции Телематика'2006. Том 1. СПб.: СПбГУ ИТМО. 2006. с. 266-261.

89. Naumov L. Generalized Coordinates for Cellular Automata Grids / Computational Science ICCS 2003. Part 2. Springer-Verlag. 2003. c. 869878.

90. Наумов Л. Решение задач с помощью клеточных автоматов посредством программного обеспечения CAMEL (Части I и II) // Информационно-управляющие системы. 2005. № 5. с. 22-30; № 6. с. 30-38.

91. Наумов Л., Шалыто А. Классификация структур, порождаемых одномерными двоичными клеточными автоматами из точечного зародыша // Известия РАН. Теория и системы управления. №5.2005. с. 137-145. Журнал из списка ВАК.

92. 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. c. 800-807.