Реконфигурация отказоустойчивой неразрезной процессорной матрицы тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Ерёмина, Наталия Леонидовна

• Ерёмина, Наталия Леонидовна
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Ерёмина, Наталия Леонидовна

Введение

Глава 1. Реконфигурация процессорной матрицы как метод обеспечения отказоустойчивости СБИС

1.1. Проблема отказоустойчивости СБИС и возможные пути ее решения

1.2. Реконфигурация процессорной матрицы

1.3. Алгоритмы реконфигурации процессорной матрицы

1.3.1. Алгоритм непосредственной перестройки

1.3.2. Алгоритм ограниченного захвата

1.3.3. Алгоритм свободного захвата

1.4. Выводы

Глава 2. Алгоритм диагонального захвата

2.1. Содержательное описание алгоритма

2.2. Сигналы перестройки

2.3. Соотношения между сигналами перестройки

2.4. Условия возникновения коммутаций

2.5. Логический анализ коммутаций

2.6. Алгоритм перенумерации

2.7. Корректность алгоритма перенумерации

2.8. Сравнение эффективности алгоритмов реконфигурации

2.9. Выводы

Глава 3. Метод программной реализации алгоритмов реконфигурации процессорной матрицы

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

3.2. Архитектура СБИС с программной реализацией реконфигурации

3.3. Язык ЛОГИКА для описания клеточных автоматов

3.4. Программное обеспечение реконфигурации матрицы

3.5. Отладка алгоритмов реконфигурации с помощью системы ЛОГИКА

3.5.1. Алгоритм непосредственной перестройки

3.5.2. Алгоритм ограниченного захвата

Введение диссертации (часть автореферата) на тему «Реконфигурация отказоустойчивой неразрезной процессорной матрицы»

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

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

Целью диссертационной работы является анализ и разработка методов обеспечения реконфигурации отказоустойчивой неразрезной процессорной матрицы на СБИС.

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

- разработка алгоритмов реконфигурации избыточной ОВС, сохраняющей структуру связей;

- моделирование процесса реконфигурации микропрограммными клеточными автоматами;

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

- проверка с использованием этой системы ранее известных и модифицированных нами алгоритмов реконфигурации ОВС. 5

Методы исследования.

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

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

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

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

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

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

Практическая значимость работы.

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

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

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

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

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

2. Алгоритм адресации для перестройки по диагональному захвату.

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

4. Программная система ЛОГИКА, обеспечивающая реализацию метода программной реконфигурации процессорной матрицы, разработку и моделирование микропрограммных клеточных автоматов для реконфигурации матрицы и иных приложений.

Реализация результатов работы.

Работа выполнена в соответствии с планом научно-исследовательских работ кафедры информационных технологий Томского государственного педагогического университета.

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

Личный вклад автора.

Основные результаты диссертационной работы получены автором лично. 7

Апробация работы.

Основные результаты диссертации докладывались и обсуждались на Всероссийской конференции "Новые информационные технологии в исследовании дискретных структур" (Екатеринбург, 1996), на региональной научно-технической конференции молодых специалистов "Радиотехнические и информационные системы и устройства" (Томск, 1994), на Международном конгрессе студентов, аспирантов и молодых ученых (Томск, 1999), на семинарах кафедр математической логики и проектирования (радиофизический факультет) и программирования (факультет прикладной математики и кибернетики) Томского государственного университета (Томск, 1994; 2000).

Публикации.

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

Структура и объем работы.

Диссертация состоит из введения, трех глав, заключения и библиографии. Она изложена на 128 страницах, содержит 24 иллюстрации, 7 таблиц. Библиографический список литературы цитированной литературы включает 76 наименований. Диссертация имеет 10 приложений на 72 страницах.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Ерёмина, Наталия Леонидовна

3.6. Выводы

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

Разработан язык ЛОГИКА для описания клеточных автоматов. Предлагается программная система ЛОГИКА для моделирования микропрограммных клеточных автоматов (МПКА) на ЭВМ.

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

120 на языке ЛОГИКА каждого из этих алгоритмов, а также алгоритма диагонального захвата.

С помощью программной системы ЛОГИКА описаны и отлажены четыре алгоритма реконфигурации процессорной матрицы.

121

Заключение

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

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

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

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

122 метода программной реконфигурации структуры предлагается программная система ЛОГИКА, позволяющая осуществлять реконфигурацию матрицы в управляющей ЭВМ. Данное программное обеспечение также может применяться для разработки новых алгоритмов реконфигурации процессорной матрицы.

В заключение перечислим основные результаты исследования:

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

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

3. Предлагается программная система ЛОГИКА для реконфигурации неразрезной процессорной матрицы.

123

Список литературы диссертационного исследования кандидат технических наук Ерёмина, Наталия Леонидовна, 2000 год

1. Движение А., Лаири Ж.-К. Гарантоспособные вычисления: от идей до реализации в проектах// ТИИЭР. 1986. Т. 74. № 5. С. 8-21.

2. Мангир Т.Э. Источники отказов и повышение выхода годных СБИС // ТИИЭР. 1984. Т. 72. № 6. 1984. С. 36-56.

3. Колбурн Е.Д., Коверли Г.П., Бехера С.К. Надежность МОП БИС // ТИИЭР. 1974. Т. 62. №2. С. 154-178.

4. Секен К.Х. Управление сложностью СБИС: Современное состояние и перспективы // ТИИЭР. 1983. Т. 71. № 1. С. 184-211.

5. Абрахам Дж.А., Фукс У.К. Модели неисправностей и ошибок для проектирования СБИС // ТИИЭР. 1986. Т. 74. № 5. С. 22-41.

6. Carter P.M., Wilkins B.R. Alpha particle induced soft errors in NMOS: a review // IEEE Proc. 1987. Y. 134. № 1. P. 32-44.

7. Browning J.S., Koda R., Kolasinski A. // IEEE Trans. Nucl. Sci. 1985. V. 32. № 6.

8. Харченко B.C., Литвиненко В.Г., Мельников В.А. Методы повышения отказоустойчивости СБИС бортовых цифровых вычислительных комплексов // Зарубежная радиоэлектроника. 1990. № 12. С. 56-69.

9. Stapper С.Н. Large-area fault clusters and fault tolerance in VLSI circuits: a review // IBM J. Res. Develop. 1989. У. 33. № 2. P. 162-173.

10. Stapper C.H. Small-area fault clusters and fault tolerance in VLSI circuits // IBM J. Res. Develop. 1989. V. 33. № 2. P. 174-177.

11. Нейман Дж. фон. Вероятностная логика и синтез надежных организмов из ненадежных компонент // Автоматы / Под ред. К.Э. Шеннона и Дж. Маккарти. М.: Иностранная литература, 1956. С. 68-139.

12. Мур Е., Шеннон К. Надежные схемы из ненадежных реле // Работы по теории информации и кибернетике. М., 1963. С. 114-153.

13. Serlin О. Fault-tolerant computers //Data Process. 1983. V. 25, № 10. P. 28-31.

14. Ebihara Y. Fault-diagnosis and automatic reconfiguration for a ring subsstem // Comput. Networks and ISDN Syst. 1986. V. 10. № 2. P. 97-109.

15. Leighton F.T., Leiserson C.E. // IEEE Trans. Comput. 1984. V. 33. № 1.

16. Cliff R.A. // IEEE Trans. Comput. 1980. V. 29. № 2.124

17. Tamir Y., Seqwin C.H. // IEEE Trans. Comput. 1984. Y. 33. № 6.

18. Мельников В .А., Кальченко С.Б., Харченко B.C. Динамическая архитектура и модульные вычислительные системы на БИС // Зарубежная радиоэлектроника, 1990. № 1.С. 64-84.

19. Armsrong J.R., Gray F.G. // IEEE Trans. Comput. 1981. Y. 30. № 8. P.

20. Abraham S., Padmanabhan K. // Proceeding International Conference on Parallel Processing, Aug., 1988. P.

21. Nanya Т., Kawamyra T. // IEEE Trans. Comput. 1988. V. 37. № 1. P. .

22. Singh A.D. // IEEE Trans. Comput. 1988. V. 37. № 1. P. .

23. Пархоменко П.П. Организация распределенного резервирования в параллельных вычислителях//Всеросс. конф. «Новые информационные технологии в исследовании дискретных структур»: Докл. Екатеринбург, 1996. С. 182-185.

24. Chen H.-L., Tzeng N.-F. Efficient resource placement in hypercubes using multiple-adjacency codes // IEEE Trans. Comput. 1994. V. 43. № 1. P. 23-33.

25. Banerjee P., Peerce M. Design and evaluation of hard ware strategies for reconfiguring hypercubes and meshes under faults // IEEE Trans. Comput. 1994. V. 43. №7. P. 841-848.

26. Сами M., Стефанелли P. Перестраиваемые архитектуры матричных процессорных СБИС // ТИИЭР. 1986. т. 74. № 5. С. 93-107.

27. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966. 308 с.

28. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. Новосибирск: Наука, 1978. 319 с.

29. Димитриев Ю.К., Хорошевский В.Г. Вычислительные системы из мини-ЭВМ. М.: Радио и связь, 1982. 304 с.

30. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Энергоатомиздат, 1983. 311 с.

31. Каляев А.В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1984. 240 с.125

32. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск : Наука, 1985. 166 с.

33. Архитектура ОВС. Отчёты по НИР, рук. Воробьёв В.А., этапы 1,2,3,4 за 1991-92 гг., НИИ САПР АН, ОСОО ИНТЕРЧИП, ВСЕМИРНАЯ ЛАБОРАТОРИЯ, Томск, 1991.

34. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MBC-100. // Lecture Notes in Computer Science, 1995, № 964 /Third Int. Conf. Parallel Computer Technologies (PaCT-95), St. Petersburg, Russia, September 12-25, 1995, Proc./

35. Мишин А.И., Седухин С.Г. Вычислительные системы и параллельные вычисления с локальными взаимодействиями //Вычислительные системы. 1979. Вып. 78. С. 90-103.

36. Мишин А.И., Седухин С.Г. Однородные вычислительные системы и параллельные вычисления // Автоматика и вычислительная техника. 1981. № 1. С. 20-24.

37. Воробьёв В.А. О содержании теории однородных вычислительных систем // XXIV области, научно-техн. конф., посвященная Дню радио: Тез. докл. Новосибирск, 1981. С. 70-71.

38. Воробьёв В.А. Модель коллектива вычислителей, основанная на принципе близкодействия//Вычислительные системы. 1982. Вып. 94. С. 103-119.

39. Воробьёв В.А., Лаходынова Н.В. Теория модели коллектива вычислителей, основанная на принципе близкодействия // XXV области, научно-техн. конференция, посвященная 60-й годовщине образования СССР и Дню радио: Тез. докл. Новосибирск, 1982.

40. Валиев М.К., Мишин А.И. Организация параллельных вычислений на системах с локальными взаимодействиями элементов // Автометрия. 1983. № 6. С.88-96.

41. Завьялов Ю.С.,Мишин А.И. Временная сложность алгоритмов задач гидроаэродинамики и производительность параллельных вычислительных систем. СО АН СССР, Институт математики, Препринт № 20. Новосибирск, 1985.

42. Воробьёв В.А., Иноземцев С.П., Коновалов Н.Н. Исследование принципов построения специализированной системы управления. Отчет по НИР. М.: МАИ, 1986.40 с.126

43. Воробьёв В.А., Лаходынова H.B. Близкодействующая архитектура вычислительной системы // III Всесоюзн. симпозиум «Перспективы развития вычислительных систем»: Тез. докл. Рига, 1989. С. 20.

44. Воробьёв В.А. Преодоление светового барьера в вычислительной технике. В кн.: Методы и средства проектирования специализированных вычислительных систем. Ленинск, 1989.

45. Лаходынова Н.В. Стохастическая модель однородной вычислительной системы, учитывающая межмашинные связи // Вычислительные системы. 1982. Вып. 94. С. 130-137.

46. Воробьев В.А., Корнеев В.В. Некоторые вопросы теории структур вычислительных систем // Вычислительные системы. 1974. Вып. 60. С. 3-16.

47. Воробьев В.А. Простейшие структуры однородных вычислительных систем // Вычислительные системы. 1974. Вып. 60. С. 35-49.

48. Воробьев В.А. Относительная адресация элементов циклического графа // Вычислительные системы. 1983. Вып. 97. С. 87-103.

49. Воробьёв В.А., Лаходынова Н.В. Пределы надежности однородных структур // Известия АН СССР. Техническая кибернетика. 1989. № 3. С. 110-113.

50. Воробьёв В.А., Лаходынова Н.В. Критическое протекание в плоских решетках // Специализированные вычислительные системы, методы и средства обработки информации: Сб.: научных трудов МАИ. М., 1987. С. 13-15.

51. Воробьёв В.А., Лаходынова Н.В. Пределы надежности однородных вычислительных систем // Вычислительные системы. 1988. Вып. 126. С. 122-149.

52. Воробьёв В.А., Лаходынова Н.В. Пороги просачивания и надежность однородных структур. В кн.: Методы и средства проектирования специализированных вычислительных систем. Ленинск, 1989.

53. Лаходынова Н.В. Анализ и разработка методов обеспечения отказоустойчивости однородных вычислительных систем. Автореф. дисс. . канд. техн. наук. Москва, 1991. 18 с.

54. Кестен X. Теория просачивания для математиков. М.: Мир, 1986. 387 с.

55. Пирс У. Построение надежных вычислительных машин. М.: Мир, 1968. 270 с.127

56. Воробьев В.А., Лаходынова Н.В. Алгоритм реконфигурации процессорной матрицы на основе сигналов согласия // Международн. конф. «Автоматизация проектирования дискретных систем»: Тез. докл. Т. 1. Минск, 1993. С. 13.

57. Воробьев В.А. Лаходынова Н.В. Реконфигурация отказоустойчивой процессорной матрицы на основе сигналов согласия И Автометрия. 1997. № 6. С. 108-113.

58. Воробьев В.А., Лаходынова Н.В. Вложение решеток в процессорную матрицу с отказами на основе сигналов согласия //Всеросс. конф. «Новые информационные технологии в исследовании дискретных структур»: Докл. Екатеринбург, 1998.

59. Воробьёв В.А., Лаходынова Н.В. Процессорная матрица с перестраиваемой структурой и перестраиваемым резервом // Автометрия. 1994. № 5. С. 90-98.

60. Лаходынова Н.В. Отказоустойчивые ОВС с перестраиваемой структурой. В кн.: Районные распределенные вычислительные системы. М., 1990.

61. Лаходынова Н.В. Отказоустойчивые ОВС с программируемым резервом // Распределенные вычислительные системы и сети. М., 1990.

62. Ерёмина Н.Л. Алгоритм диагонального захвата для реконфигурации процессорной матрицы и его эффективность // Вестник Томского государственного педагогического университета. 1999. № 7. С. 42-47.

63. Воробьев В.А., Ерёмина Н.Л. Программная реализация реконфигурации отказоустойчивой процессорной матрицы // Автометрия. 1996. № 2. С. 111-121.

64. Ерёмина Н.Л. Процессорная матрица с реконфигурацией по алгоритму диагонального захвата // Международн. конгресс «Наука, образование, культура на рубеже тысячелетий»: Труды II Сибирской школы молодого ученого. Томск, 2000. С. 67-71.

65. Воробьев В.А., Ерёмина Н.Л., Лаходынова Н.В. Алгоритмы адресации отказоустойчивой процессорной матрицы на СБИС // Всеросс. конф. «Новые информационные технологии в исследовании дискретных структур»: Докл. Екатеринбург, 1996. С. 109-111.

66. Ерёмина Н.Л. Алгоритм адресации для реконфигурации процессорной матрицы путем диагонального захвата // Вестник Томского государственного педагогического университета. 1999. №7. С. 47-51.128

67. Wolfram S. "Mathematica": A System for Doing Mathematics by Computer. Addison-Wesley Publishing Company, 1991.

68. Gray J.W. Mastering Mathematica: Programming Methods and Application AP Professional, 1994.

69. Воробьев B.A., Ерёмина H.Jl., Лаходынова H.B. Анализ алгоритмов перестройки структуры процессорной матрицы //Автометрия. 1996. № 3. С. 69-77.

70. Ерёмина Н.Л. Моделирование отказоустойчивой процессорной матрицы // Всеросс. конф. «Новые информационные технологии в исследовании дискретных структур»: Докл. Екатеринбург, 1996. С. 112-116.

71. Ачасова C.B. Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990. 250 с.

72. Ерёмина Н.Л., Воробьев В.А. Отказоустойчивая матрица для обработки изображений // Региональная научно-техническая конференция «Радиотехнические и информационные системы и устройства»: Тез. докл. Томск, 1994. С. 7-9.

73. Флинн М.Дж. Сверхбыстродействующие вычислительные системы // ТИИЭР. 1966. Т. 54. № 12. С. 311-320.

74. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. 520 с

75. Димитриев Ю.К. Алгоритм самодиагностики вычислительных систем с программируемой структурой // Электронное моделирование. 1985. № 5. С. 20-26.

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