Содержание к диссертации
Введение
ГЛАВА 1. ОВС как случайное поле 37
1.1. Концепция ОВС 38
1.1.1. Основные принципы построения параллельных вычислительных систем 38
1.1.2. ОВС с программируемой структурой 40
1.1.3. Современное состояние параллельных систем 41
1.2. Локальные однородные структуры 47
1.2.1. Структура вычислительной системы 47
1.2.2. Локальность 47
1.2.3. Однородность 49
1.2.4. Периодичность 50
1.3. Ординарная динамическая модель ОВС 50
1.3.1. Модели коллективов вычислителей 50
1.3.2. Структурные характеристики ОВС 53
1.3.3. Ординарная динамическая клеточная модель 55
1.4. Состояния ординарных динамических систем 60
1.4.1. О теории случайных полей 60
1.4.2. Состояния на конечных графах 64
1.4.3. Эргодичность 70
1.4.4. Обратимые системы 74
1.4.5. Надежность однородных структур 82
1.4.6. Резюме 89
1.5. Основные результаты главы 1 90
ГЛАВА 2. Отказоустойчивость ним с точки зрения теории просачивания 91
2.1. Проблема надежности 91
2.1.1. Отказоустойчивые вычислительные системы 91
2.1.2. Традиционные подходы к обеспечению отказоустойчивости 94
2.1.3. Необходимость новой парадигмы структурной живучести 100
2.2. Статическая модель структурной надежности 101
2.2.1. Проблема живучести ОВС 101
2.2.2. Статическая модель структурной надежности 103
2.3. Динамические модели живучести ОВС 106
2.4. Исследование порогов просачивания 109
2.4.1. Постановка задачи 109
2.4.2. Метод моделирующей решётки 111
2.4.3 Метод второй производной 117
2.4.4. Смешанная задача просачивания 118
2.4.5. Обсуждение результатов 121
2.5. Реальная парадигма живучести ОВС 127
2.6. Основные результаты главы 2 128
ГЛАВА 3. Алгоритмы реконфигурации неразрезных процессорных матриц (НПМ) 130
3.1. Отказоустойчивые НПМ 130
3.1.1. Источники отказов СБИС 131
3.1.2. Обеспечение отказоустойчивости НПМ 135
3.1.3. НПМ с перестраиваемой структурой и программируемым резервом 138
3.2. Реконфигурация НПМ с программируемым резервом 143
3.2.1. Алгоритм непосредственной перестройки 143
3.2.2. Алгоритм вертикальной перестройки 152
3.2.3. Алгоритм ограниченного захвата 153
3.2.4. Алгоритм свободного захвата 158
3.3. Эффективность алгоритмов реконфигурации 164
3.3.1. Эффективность алгоритмов реконфигурации 164
3.3.2. Выбор резерва 165
3.3.3. Работоспособность алгоритмов реконфигурации 169
3.3.4. Резюме 169
3.4. Архитектура ОВС на НПМ с программируемым резервом 170
3.4.1. Архитектура ОВС 171
3.4.2. Недостатки схемной реализации 172
3.4.3. Архитектура ОВС с программной реконфигурацией НПМ 176
3.4.4. Резюме 177
3.5. Основные результаты главы 3 179
ГЛАВА 4. Консенсус-парадигма отказоустойчивости неразрезных процессорных матриц 180
4.1. Консенсус-парадигма отказоустойчивости НПМ СБИС 180
4.1.1. Пределы отказоустойчивости однородных структур 181
4.1.2. Классическая парадигма отказоустойчивости 182
4.1.3. Византийская парадигма отказоустойчивости 183
4.1.4. Консенсус-парадигма отказоустойчивости 185
4.2. Реконфигурация НПМ на основе консенсуса 187
4.2.1. Метод консенсуса 187
4.2.2. ОВС с программной реконфигурацией НПМ методом консенсуса 188
4.2.3. Локальная самодиагностика НПМ 189
4.2.4. Волновой алгоритм поиска консенсуса 192
4.2.5. Примеры реконфигурации 196
4.3. Эффективность метода консенсуса 200
4.3.1. Моделирование волнового алгоритма 200
4.3.2. Оценка эффективность волнового алгоритма 200
4.3.3. Волновой алгоритм и задача просачивания 202
4.3.4. Резюме 205
4.4. Основные результаты главы 4 207
Заключение 209
Список литературы 212
Приложение 1. 235
- Основные принципы построения параллельных вычислительных систем
- Традиционные подходы к обеспечению отказоустойчивости
- НПМ с перестраиваемой структурой и программируемым резервом
- Волновой алгоритм поиска консенсуса
Введение к работе
Актуальность исследования. Одним из прорывных направлений современной науки и техники является достижение общедоступной сверхвысокой производительности ЭВМ - более чем 1013-*-1014 флопс. От успешного внедрения и использования таких супер-ЭВМ зависит стратегическая позиция современных государств в нарождающемся сложном постиндустриальном мире. Так для всемирного экологического (и, очевидно, не только экологического) мониторинга США построили массово-параллельный суперкомпьютер с объявленным быстродействием ЗхЮ13 флопс.
Нет смысла приводить обширный список современных научных и информационных проблем, решение которых невозможно из-за вычислительных трудностей. Мы не можем даже вообразить, какие достижения и проблемы ждут человечество, когда такие и ещё более мощные вычислительные средства станут общедоступными. Примером является информационная революция, которая грянула с появлением миллионов персональных компьютеров. Однако на пути к такому, казалось бы близкому, будущему нас поджидают фундаментальные ограничения: физические, технологические, алгоритмические и экономические. Дальнейшее развитие информатики требует нового теоретического, технологического и внедренческого прорыва. Такой прорыв возможен в рамках рассматриваемой ниже концепции ОВС на пути преодоления её фундаментальных ограничений надёжности и микроминиатюризации.
Однородная Вычислительная Система (ОВС) — вычислительная система, состоящая из большого числа одинаковых элементарных вычислительных машин (ЭМ) или процессорных элементов (ПЭ), соединенных регулярной программно-управляемой коммуникационной сетью — программируемым (перестраиваемым) регулярным каналом (РК). Принципы, положенные в основу ОВС: массовый параллелизм вычислений; однородность и программируемость структуры - структурная реализация вычислений на макроуровне; технологичность — возможность строить ОВС из серийных БИС и НПМ СБИС; наращиваемость; живучесть — функционирование при выходе из строя всё большего числа ЭМ с постепенной деградацией функций и производительности.
Концепция ОВС занимает видное место в развитии супер-ЭВМ. Например, вы-
.6 числительные кластеры серии МВС-100 и МВС-100Х, предлагаемые НПО «Квант», реально представляют собой ОВС на процессорных матрицах, а полносвязность структуры их межмашинных связей является виртуальной [8]. К тому же классу относится упомянутая выше стратегическая вычислительная система США. Растет число публикаций, теоретических и практических разработок в рамках этой концепции. Результаты этого развития впечатляющие. Достигнута пиковая производительность стратегических массово-параллельных систем, исчисляемая десятками терафлопс, однако такие системы всё ещё уникальны, крупногабаритны и слишком дороги.
Концепция ОВС была сформулирована в Институте математики СО АН СССР под руководством Э.В. Евреинова [1] в 1962 году и успешно развивается в настоящее время, являясь ведущей при построении систем сверхвысокой производительности. В России значительный вклад в развитие ОВС внесли Косарев Ю.Г., Хорошевский В.Г., Бандман О.Л., Прангишвили И.В., Медведев И.Л., Воробьев В.А., Корнеев В.В., Димитриев Ю.К., Глушков В.М., Каляев А.В., Лазарев В.Г., Додонов А.Г., Артамонов Г.Т. и многие другие.
Предмет диссертационного исследования — отказоустойчивая Однородная Вычислительная Система (ОВС) на Процессорных Матрицах (ПМ), в частности на Неразрезных ПМ СБИС (НПМ СБИС). Натурные эксперименты с предметом нашего исследования недоступны по очевидным экономическим и техническим причинам. Главным направлением исследований является поиск теоретических обоснований будущих технических решений.
В работе исследуется проблема создания отказоустойчивых процессорных матриц (ПМ) и неразрезных процессорных матриц (НПМ). Предлагаемый подход к решению этой проблемы базируется на принципах избыточности и программируемое структуры регулярного канала (РК) системы. Что касается НПМ, то в настоящее время неразрезная технология не позволяет использовать их в качестве базы для реализации ОВС. Для успешного применения НПМ требуются новые технические, алгоритмические и программные решения, позволяющие компенсировать технологические трудности. Поэтому особое внимание было уделено проблеме обеспечения отказоустойчивости ОВС на неразрезных процессорных матрицах (НПМ).
Проблема обеспечения отказоустойчивости НПМ СБИС была сформулирована
7 ещё в 80-х годах. Технологические трудности при изготовлении НПМ, низкий выход годных, дорогостоящее производство привели к тому, что до настоящего времени их использование в качестве базы для реализации ОВС остается проблематичным. Ясно, что технология обозримого будущего не избавит НПМ СБИС от указанных трудностей и ограничений. С другой стороны, очевидно, что именно НПМ наилучшим образом соответствуют идеологии ОВС и потребностям дальнейшего развития компактных массово-параллельных (мозгоподобных) вычислительных устройств. Важнейшие особенности неразрезной технологии СБИС:
невозможность замены отказавших элементов;
отказы не только процессорных элементов, но и связей между ними;
однородность и близкодействие структур связей;
4) стремление к экономии оборудования.
Указанные особенности создают принципиальные сложности и фундаментальные ограничения при производстве и обеспечения отказоустойчивости НПМ СБИС. Эти ограничения до сих пор не удавалось полностью осознать и обойти. В связи с этим необходимость и актуальность реализации отказоустойчивых НПМ СБИС постоянно имелась ввиду, и все предлагаемые подходы и решения рассматривались прежде всего с этой точки зрения. Таким образом, в отношении НПМ данная работа носит опережающий характер.
Ясно, что при таком подходе получаются решения пригодные и для ПМ на дискретных компонентах (микропроцессорах). Кроме того, проблема обеспечения отказоустойчивости актуальна для любых вычислительных систем. Результаты исследований, полученные в диссертации, могут быть использованы и в других интерпретациях. Цель исследования — развитие теоретических основ построения отказоустойчивых ОВС, разработка программно-аппаратных методов обеспечения отказоустойчивости процессорных матриц с программируемой структурой, в том числе (и в особенности) НПМ СБИС.
Основные задачи диссертации: I. Разработка математических моделей ОВС, позволяющих исследовать отказоустойчивость ОВС и методы ее обеспечения, как аналитически, так и моделированием на ЭВМ.
Исследование фундаментальных пределов отказоустойчивости и надежности однородных структур (графов).
Разработка и исследование новых парадигм обеспечения отказоустойчивости ИМ и НПМ СБИС.
Разработка алгоритмов реконфигурации коммутационных структур избыточных ПМ и НПМ СБИС, сохраняющих заданную структуру связей (решётку) при отказах некоторой доли элементов и связей.
Исследование работоспособности, эффективности и статистических свойств разработанных алгоритмов.
Разработка архитектуры ОВС на ПМ и НПМ СБИС.
Методы исследования. При проведении исследований использовался следующий математический аппарат: многокомпонентные случайные системы, случайные поля, теория просачивания, теория графов, вычисления и имитационное моделирование на ЭВМ.
Научная новизна работы заключается в следующем.
Разработаны математические модели, предназначенные для исследования надёжности и отказоустойчивости ОВС, отличающиеся от известных учетом влияния структуры связей.
Исследованы фундаментальные пределы отказоустойчивости однородных коммутационных структур ПМ и НПМ СБИС.
Предложены практические методы определения предельных характеристик надежности - порогов просачивания - как для отдельного элемента, так и для ПМ в целом.
Предложены и исследованы метод программирования резерва и локально-параллельные алгоритмы реконфигурации структуры отказоустойчивой процессорной матрицы, имеющие более высокую эффективность по сравнению с предшественниками.
Предложен новый подход к обеспечению отказоустойчивости НПМ: консенсус-парадигма.
Разработан и исследован метод консенсуса, обеспечивающий реконфигурацию структуры процессорной матрицы, наиболее полное использование ее исправ-
9 ной части, не требующий аппаратуры самодиагностики и выделения резервных элементов.
Личный вклад автора. Основные результаты диссертационной работы получены автором лично как в индивидуальных исследованиях, так и при участии в работах, где развивались основные положения теории ОВС. Последние представлены частично или ссылками.
Практическая ценность исследования заключается в том, что предлагаемые методы обеспечения отказоустойчивости НПМ повышают выход годных СБИС при уже имеющемся уровне технологии и являются важным шагом на пути к реализации ОВС на НПМ. Разработанные методы определения предельных характеристик надежности однородных структур и обеспечения отказоустойчивости ПМ и НПМ имеют практическое значение независимо от элементной базы, и могут применяться в условиях функционирования, исключающих диагностику и ремонт оборудования.
Реализация результатов исследования состоит в использовании их в учебном процессе в Вузах и при разработке отказоустойчивых ОВС. Использование результатов подтверждается соответствующими актами. Апробация. Результаты исследования: обсуждались на семинарах в Институте математики СО РАН (г. Новосибирск), Московском институте связи, Красноярском государственном электротехническом университете, на семинаре Отдела проблем информатизации Томского научного центра СО РАН, кафедре прикладной математики Томского государственного архитектурно-строительного университета.;
кафедре прикладной математики Томского государственного архитектурно-строительного университета.;
докладывались на 12-ти международных, всесоюзных и всероссийских, а также на региональных, городских и вузовских конференциях, совещаниях и школах-семинарах в Москве, Минске, Риге, Новосибирске, Томске, Екатеринбурге, Байконуре, Красноярске;
поддерживались фондом грантов Министерства образования РФ.
Публикации. По тематике диссертации опубликовано 34 научных работы, из них: печатных - 33, из них: монографий - 1, учебных пособий - 1, в центральных изда-
10 ниях - более десятка, в трудах всесоюзных, всероссийских и международных конференций - 9, в трудах региональных конференций — 3, в иностранной печати - 7.
Структура и объем работы. Диссертация состоит из введения, четырёх глав, заключения, библиографии и приложения. Общий объём диссертации - 236 страницы. Из них: 1 страница титульная; 3 страницы содержания (83 пункта); 207 страниц основного текста, содержащего 28 рисунков и 14 таблиц; 23 страницы библиографии на 276 названий; 2 страницы приложения. В приложение вынесено описание языка ЛОГИКА.
Основные положения, выносимые на защиту:
Математические модели ОВС - многокомпонентные случайные системы и критическое просачивание - дают необходимую базу для исследования отказоустойчивости и разработки эффективных методов ее обеспечения. В процессе этих исследований выявлено решающее влияние структуры на работоспособность системы. Определены пределы надежности, не позволяющие строить сколь угодно надёжную ОВС из элементов, коэффициент готовности которых ниже порога просачивания для выбранной структуры.
Консенсус-парадигма - новый наиболее эффективный подход к обеспечению отказоустойчивости как процессорных матриц, так и НПМ СБИС.
Методы реконфигурации структуры процессорной матрицы (и с программируемым резервом, и без него) обеспечивают реализацию отказоустойчивой ОВС на ПМ и НПМ СБИС.
Архитектура ОВС на ПМ и НПМ СБИС позволяет неограниченно наращивать её производительность и обеспечить необходимую живучесть.
Краткое изложение диссертации
Во введении обоснована актуальность темы, сформулированы цели и задачи работы, перечислены основные результаты, показана их научная новизна и практическая ценность, дано краткое изложение работы.
В первой главе представлена концепция ОВС в связи с общемировыми тенденциями в области разработки параллельных вычислительных систем сверхвысокой производительности. Построена математическая модель, позволяющая исследовать
11 различные аспекты разработки и функционирования параллельных систем. Основное внимание сосредоточено на исследовании стохастических свойств и показателей эффективности параллельных систем.
В п.1.1. дан краткий обзор развития и современного состояния рынка ЭВМ сверхвысокой производительности [1+115]. Показана ведущая роль концепции ОВС в этом процессе.
В п. 1.2. излагаются требования к структуре однородной вычислительной системы, обеспечивающие реализацию основных принципов построения ЭВМ сверхвысокой производительности: наращиваемость, конструктивная однородность, близко-действие [1-71, 98-104].
В п. 1.3. предлагается ординарная динамическая клеточная модель ОВС [67,68,105,111,129]. Особенностями ординарной динамической модели являются асинхронность, описание её стохастических свойств, как многокомпонентной случайной системы, учет структуры связей системы, зависимость поведения отдельного элемента системы от ближайших соседей [129].
Структурой системы является однородный граф G (L, Е), где L — множество нумерованных вершин, Е — множество пар элементов из L, связанных в G. Мы полагаем по определению, что существует транзитивная подгруппа группы автоморфизмов АШ графа G.
Множество Э/ вершин графа G, находящихся на расстоянии 1 от вершины /, на
зывается окрестностью или ближайшими соседями вершины /, множество дк1 вершин
графа G, находящихся на расстоянии не более чем к от вершины /и /«2 Э/, называется
окрестностью к-то порядка вершины /. Аналогично для любого множества KeL опре
деляются его окрестности Э 'К, причём К п Э 'К = 0, и, кроме того
i
Как и в [111] будем считать, что существуют рекурсивно-вычислимые функции ф„ и ф,"1, такие, что дії = ф,(0> I - ф<"1(Э //), где /, j = 0,1,.., тЛ — отметки рёбер, причём в последнем случае отметки одного и того же ребра; Э /, є Э / — элемент окрестности, соединённый с /-тым элементом /-тым ребром. Независимость вида функций нумерации от / - следствие однородности графа G.
12 Элементарным автоматом динамической клеточной системы является асинхронный вероятностный автомат М = {X, Хт, Л), где X - выходной алфавит автомата М, совпадающий с алфавитом его состояний X, входной алфавит X"1 - состояния окрестности 31, содержащей т элементов, Л = {'Куіуді) І х,у єХ\, ум є Уд}- система интенсивностей перехода. Вероятность перехода из хєХ в уеХ за время At при условии уы є X"1 равна
Рху(Уді) = ^ху(Уді) Ar + o(Af)
Функция х(1), сопоставляющая каждому leL состояние х(Г)єХ (иначе х{1): L —» X), называется конфигурацией. Множество Y всех конфигураций - декартова степень множествах: Y = XN, \ y\ = \x\N
Пусть KczLn x(t): К —» X ; такое сужение функции х(Г) называется конфигурацией на К и обозначается хк, у к, в частности xi есть состояние /-го автомата — случайная величина, называемая также компонентой. Введём операцию объединения на множестве непересекающихся сужений конфигураций. Пусть Ka.L,MczLnKnM = 0, тогда (ук, ум) = уКим - конфигурация на К u М. совпадающая с ук на К и с ум на М. Будем говорить, что хм содержит xKf если KczM ихм= (хк,хм\к)-
Элементарный автомат задаётся системой подстановок П = { П(х,Хді) /хє Х,Хді еГ}, где П(х,ха ) : (xLxdt) -> г si,...,yi; КАхді), К*(Хді),-,Ку(хзі) - стационарные неймановские подстановки. Здесь г/, si,...,yi— это возможные значения 1-го элемента в результате применения подстановки П(х,Хді), rif si,...,yi є X; список Ххг(хаі), ^«(хэ/)»—Лсу(*эі) -соответствующие интенсивности реализаций этих альтернативных значений, \хг{х^ /),
^xs(Xd І),-Лху(хд і) Є Л.
Итак, стохастическая клеточная модель 5 задана, если задана её структура G и автомат М. Динамическая клеточная модель это двойка S = {G,M) или шестёрка
S = (L,E,Aut,X,Xm,lT). Конфигурация есть состояние системы S, которое изменяется при переходе любого из автоматов М из состояния в состояние. Функционирование всей системы задаётся графом конфигураций (состояний)
W=
13 где: У - множество конфигураций; V — множество дуг, ve V имеет своим началом хє Y и концом гє У, если х заменяется на z при изменении состояния некоторого подмножества KczL автоматов М в системе S.
Граф конфигураций W предназначен для изучения функционирования системы S при синхронной и асинхронной интерпретации в общем случае. Запрет одновременного срабатывания нескольких подстановок задает ординарное множество Z(y) конфигураций, достижимое из у таким применением системы П. Однородная динамическая система называется ординарной, если для любого уе У множество Z(y) достижимых конфигураций ординарно.
Срабатывание подстановок в ординарной динамической клеточной системе можно рассматривать как ординарный поток событий, а всё функционирование как марковский процесс с системой состояний У.
В терминах теории графов ординарная интерпретация задаёт ординарный граф конфигураций W0, каждая дуга которого помечена соответствующей интенсивностью перехода из системы интенсивностей Л:
W0 =
Ординарный граф конфигураций изображает марковский процесс, сопряжённый с функционированием системы S и задающий вероятностную меру Р на а—алгебре конфигураций F. Таким образом, системе 5 соответствует вероятностное пространство
алгебра на У; Р - вероятностная мера на У.
Естественным образом переносится на стохастическую клеточную модель и все другие термины, относящиеся к теории марковских процессов. Итак, представленная модель позволяет рассматривать ОВС как многокомпонентную случайную систему, стационарным состоянием которой является случайное поле.
В п. 1.4. рассмотрены состояния ординарных динамических систем на конечных
графах с конечным числом состояний. Получены условия, при которых стационарный режим системы описывается марковским полем. Обсуждаются условия эргодичности. Исследованы обратимые системы, их связь с марковскими полями.
Рассмотрим стационарное (равновесное) состояние ординарной динамической клеточной системы.
Всякая положительная вероятностная мера /1 на F называется состоянием на G.
Совокупность всех таких мер называется множеством состояний на G.
Состояние jU есть марковское случайное поле на G, если для всякого /є X имеем ц(х, I ххч ) = (I(jc, / xai) .
Пусть случайный процесс задан интенсивностями перехода ft,$,у,у' Y . Тогда условие обратимости для конечного Y выглядит следующим образом
PoWs^PoiyWb.yeYjeYKy.
Свойства обратимых процессов на конечных графах можно описать полугруппой ближайшего соседства \Pt }іг0 с генератором G.
Генератор G полугруппы \Pt jti0, описывающий эту модель, будет определяться
так: G(y\y") = f5ab(l,y'), УМ/ = У'П/, У, */',, для всех других пар у\у"є Y
G(y',y") = 0, a G(y\y') определяется из условия ^Giy^y") = 0. Здесь а и Ъ -
состояния компоненты. Полугруппу, отвечающую такому генератору, назовем ординарной.
Полугруппу {Pt }t20 назовем полугруппой ближайшего соседства, если
РаЬ (*» *) = РаЬ (^ */Ы/ > *WW ) , V/ Є L, X Є Y .
Состояние К называется равновесным состоянием для полугруппы {Р, }(&0, если
Z*(y)W,/,)=*0'M) vyGy,Vr>o.
Имеет место следующая
ТЕОРЕМА 1. Пусть {Р,}гг0 - обратимая ординарная полугруппа ближайшего
соседства, К - равновесное состояние. Тогда П - марковское случайное поле.
Условие обратимости накладывает ограничения на интенсивности перехода
А..
ТЕОРЕМА 2. Следующие условия эквивалентны: (1) Ординарная полугруппа {Р, }/г0 обратима.
т РаеУ,у1) = Р+«,у1) РЛ1уг)
рсмУ) рьліУ) рла,у*У
где le L;yl,y2,y3 eY;ylL\i = у\м = y\\r,y\ =c;y2t =Ь;у\ =а и
одновременно
Р+У*У1) Ры«гУ) = Ры«гУ) РМУ4)
РьЛ1уг) РМ.у1) РМУ) РьЛіУУ
где U, є L; у1, у2,у\у4 є У;
УІмл» = Укч = Ушг* = Ущч 5 З7/4 = «. J/' =c,y)=a,y\=d; у2 =b,y2h=c; yl=b,yl=d.
(3) Существует потенциал V: Y —> R такой, что
М^ = ^^)-У(У)},т^ у2ш = у1ш; y2=b,yl =а.
Рассмотренная модель позволяет учесть, хотя бы в некоторой степени, межмашинные взаимодействия. Однако, условия обратимости являются слишком жесткими для реальных систем. Этим вызвана ограниченность применения результатов по марковским случайным полям. С другой стороны, очевидна и недостаточность модели "идеального коллектива" вычислителей [3], в которой структурные характеристики ОВС не учитываются вовсе. Приведем соответствующий пример. Элементарные машины выходят из строя с интенсивностью /3 и восстанавливаются с интенсивностью 8. Интенсивности Р и 8 зависят от состояния окрестности следующим образом: пусть п - количество соседей отдельного автомата, к - количество неисправных соседей, тогда
Р = Коэффициент готовности в этом случае имеет вид
Р,к<п
8, к <п
8ь,к = п
(fl+1)"
,где b = ^;a = ^r
p,=
(a + l)n-an(a-b)
8. 8
a
На Рис. 1 показана область (n=5), в которой учет влияния межмашинных связей не дает существенной поправки к результатам модели "идеального коллектива". Очевидна необходимость дальнейших исследований. Обнадеживающие результаты в этом направлении дает использование результатов теории просачивания.
Рис. 1.
Во второй главе представлены результаты исследований отказоустойчивости ОВС, основанные на результатах теории просачивания и опубликованные в серии работ [128, 167-175].
В п.2.1. даётся критический анализ традиционных методов [176-5-222] обеспечения отказоустойчивости ВС и делается вывод об их недостаточности для ПМ, основанных на принципе близкодействия и, особенно, на неразрезной технологии СБИС. Во-первых, поскольку замена отказавших ЭМ на неразрезной пластине невозможна, методы диагностики с ремонтом неприменимы. Во-вторых, в этих методах нет учета ненадежности межмашинных связей. Построение синдрома состояния системы, основанное на взаимопроверках, приводит к тому, что не всякая ЭМ, признанная исправной может быть включена в однородную подсистему. И наоборот, не всякая неисправная ЭМ на самом деле является таковой. Поскольку все неисправности связей относятся к неисправности процессора, для признания ЭМ неисправной достаточно неисправности одной связи с диагностирующей ее ЭМ. Такой подход приводит к тому, что исправная часть системы используется недостаточно эффективно.
В п.2.2. обсуждается проблема надежности однородных структур. Строится
17 статическая модель структурной живучести: Надёжность ПМ рассматривается при следующих предположениях: ресурсы ПМ, то есть число ЭМ и связей, не ограничены; структура ПМ удовлетворяет требованиям локальности и однородности; алгоритмы самодиагностики и реконфигурации ПМ используют возможности структуры наилучшим образом; элементы и связи ПМ выходят из строя независимо друг от друга.
Предположим, что элемент структуры исправен с вероятностью р и неисправен с вероятностью (1-р), а связь (дуга или ребро) исправна с вероятностью г и неисправна с вероятностью (1 - г). Структура считается исправной, если возможно просачивание информации от входов к выходам через исправные элементы и связи., и неисправной в противном случае. В исправной НПМ существует связная подсистема -кластер, содержащая Л^ элементов, включая входы и выходы. Пусть N0 - число элементарных машин, необходимых для решения задачи. При Nk
Наращивание избыточности ПМ понимается теперь как неограниченный рост размера N выделенного блока. Ясно, что существует такой размер N, что наличие Nk>N0 элементов в исправном кластере будет гарантировано. Решающее значение имеет только факт существования или несуществования исправного кластера. По предположению, алгоритмы самодиагностики и реконфигурации его обнаружат и полностью используют для организации вычислений. Например, это может быть сделано с помощью корневого дерева на связном множестве исправных ЭМ, как в [8].
Увеличивая размер N, мы должны требовать увеличения размера исправного кластера. В пределе, при N —> , в бесконечной структуре должен существовать бесконечный исправный кластер. В противном случае структура "рассыплется" на несвязные куски, то есть выйдет из строя.
Имея в виду применение достаточно больших ОВС при N> 10 , мы ограничимся исследованием их бесконечных представителей. Проблема надёжности свелась теперь к следующему вопросу: при каких вероятностях р и г в бесконечной локальной однородной структуре данного типа существует бесконечный исправный кластер?
Ответ на этот вопрос является основной задачей теории просачивания. Содержание основной задачи просачивания состоит в поиске области просачивания, точнее,
такой функции f(p, г), что при f(p, г) < 0 исправный кластер отсутствует, а при f(p, г) > О - существует. Частные задачи были поставлены Хаммерсли [223] ещё в 1957 году: просачивание по вершинам, когда р < 1 и г=1, и просачивание по связям, когда р = 1, а г < 1. Вторая задача сводится к первой. Основной результат теории просачивания заключается в существовании критических вероятностей рн, таких, что если р <рн, то бесконечный исправный кластер существует в G с вероятностью 0, и если р>рн, то с вероятностью 1 в G существует, и притом единственный, бесконечный исправный кластер. Здесь G периодический граф, вложенный в R2.
Существование критической вероятности не подвергается сомнению и для периодических графов, вложенных в R , однако, в этом случае нет единственности бесконечного исправного кластера. Для практических целей достаточно ограничиться двумерным случаем, так как системы наращиваются на поверхности кристалла или размещаются на поверхности несущей конструкции (тора).
Критическая вероятность рн - единый показатель, характеризующий предельную надежность всех локальных однородных структур одного типа.
Пусть P(N> р) - вероятность просачивания через структуру размера N в данный момент времени. Следующее утверждение о свойствах P(N, р) является, по существу, перефразировкой основного утверждения.
Утверждение 1. На множестве локальных однородных структур одного типа, вложенных в R2,
lim P(N,p) = <
0,р<рн
Ірїрн
Иными словами, с ростом избыточности ОВС становится сколь угодно надёжной, если р > рн, и сколь угодно ненадёжной, если р <рн. Таким образом, нельзя построить сколь угодно надежную ОВС из сколь угодно ненадежных элементов. Это утверждение противоречит результатам Шеннона-Мура [177] и многих последующих работ (см., например, [3,178,181]). Причина противоречия в том, что мы ограничены в выборе структуры. Требования локальности и однородности лишают нас возможности использовать слишком ненадёжные элементы.
В п.2.3. рассматриваются динамические модели структурной живучести при
19 различных предположениях. Исследуется влияние избыточности на надежность системы в целом.
Пусть время безотказного функционирования ЭМ распределено по экспоненциальному закону с параметром а при условии р^рн Среднее время наработки на отказ для ЭМ равно т= а'1. Величина а — интенсивность отказов ЭМ, т — время жизни. Отказавшая ЭМ обнаруживается и восстанавливается с интенсивностью j3 за среднее время восстановления ft"l.
Уравнение dp(t)= [P(l— p{t)) - OLp(t)] dt описывает процесс гибели - восстановления в бесконечном ансамбле ЭМ. Пусть р0 = р(0) и р = p(t). Вероятность р0 называется "выходом годных элементов" и характеризует качество СБИС при неразрезной технологии. Если бракованные ЭМ можно заменить, то р0 = 1. Решение уравнения (2.3.2.) при указанных начальных условиях имеет вид
р=р~+[ро-р~\е-'(а+*\
Р
где рт = lim р = финальная вероятность исправного состояния ЭМ.
г_>оо СС + р
Наглядно этот процесс представлен на Рис. 2.
Учитывая условие связности локальной однородной структуры р > рн, легко получить следующее утверждение.
Утверждение 2. Время существования бесконечного исправного кластера в локальной однородной структуре равно
0,Ро<Р-<Рн>
t = <
ЫРо Р~ ,р„<рн<р0,
а + Р РН-РУ
{00>Рн<Р--
В частности, в системе без восстановления с
t = т 1п(ро I рн) < х Ырн~'), где т = а '1 — время жизни одного элемента. Эта формула представляется более реальной оценкой, чем утверждение 1, поскольку диагностика и восстановление изолированного элемента проблематично.
Итак, избыточность не увеличивает времени жизни локальной однородной структуры.
ІР 1 I-
РН>Роо - Роо
Рн < Р-
0 и t2
Рис. 2. Динамика гибели-восстановления ОВС: ti и t2 - время жизни при разных начальных условиях
Особенно ярко последствия чрезмерной избыточности выявляются на модели конечной ОВС с ограниченным восстановлением. Для наших целей достаточно воспользоваться приближённым методом динамики средних и рассмотреть только стационарное состояние.
Пусть N— число ЭМ; т - число восстанавливающих органов, работающих параллельно; а и /3 - интенсивности потока отказов и восстановлений. При m > N{\—p) система ведёт себя как самовосстанавливающаяся. При m
Nap=m$
Известно также, что при полной загрузке ограниченной восстанавливающей системы математическое ожидание числа исправных элементов равно тра'1. Потребуем, чтобы это число превышало N0 и, кроме того, выполнялось р>рн. Получаем следующее утверждение.
Утверждение 3. ОВС с ограниченным восстановлением работоспособна если выполняется условие
21 N0 < m P a"1 < N< m |3 (apH)'1 При N>m$ (<хрн)\ стационарное состояние ОВС есть состояние отказа.
Последнее утверждение есть одно из проявлений "закона Мэрфи", который гласит: дополнительное оборудование, введённое в систему для обеспечения её надёжности, выводит систему из строя.
Итак, порог просачивания важная характеристика отказоустойчивости локальной однородной структуры.
В п.2.4. исследуются пороги просачивания однородных структур, предлагаются новые методы их определения. Метод моделирующих решеток позволяет аналитически определить значения критических вероятностей рн(Ю, Р//ІЩ Рн(К* ). Метод второй производной позволяет определить критические вероятности для любых структур. Утверждение 4. Точка перегиба функции P(N,p) при N —> о является порогом просачивания для соответствующего периодического графа.
Функция P(N, р) -полином iV-той степени относительно р.
P(N,p) = Y,i = i..NCipX\-p)N-i где С, - число конфигураций с просачиванием, в которых і элементов исправно (чёрные), aN—i элементов неисправно (белые). Определение точного аналитического выражения для P(N, р) сводится к подсчёту коэффициентов С,. Для небольших N вычисления проводятся на ЭВМ полным перебором всех конфигураций и проверкой их на просачиваемость (Рис. 3.).
В таблице 1 приводятся пороги просачивания для популярных структур. Значения взяты как из литературы [127], так и получены в данной работе.
Моделирование задачи просачивания в более общей постановке позволяет экс периментально определить границу области просачивания Др], р2) = О для разных типов решеток. На Рис.4, изображены границы области просачивания для четырех решеток. Нижняя соответствует P(N, р, г) = 0, верхняя соответствует P(N, р, г) = 1. В заштрихованной области - переходная зона.
0,37 0,44 0,59
Рис. 3. Метод второй производной. Результаты вычислений функции Р(п,р) для различных типов структур ОВС. Показаны точки перегибов и соответствующие значения порога рн.
Таблица 1. Критические вероятности просачивания для различных решёток
0.9 0.6 0.7 0.6 0.5 0.4
J 1 L
" 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Рис. 4. Области просачивания для решеток К*,Т, К, Ш
Итак, показано, что для исследования живучести ОВС на ПМ и НПМ СБИС необходимо учитывать её структуру и надёжность как ПЭ так и связей. Без этого выводы теории могут быть неверными.
В п.2.5. обсуждается реальная парадигма структурной живучести однородных систем, в которой принимается во внимание как отказ ПЭ, так и коммутационного оборудования.
В связи с реальной парадигмой живучести неразрезных процессорных матриц СБИС выделяются три категории качества: непригодные (в них нет доступного извне
24 исправного кластера необходимой мощности); ограниченно годные (имеется доступный извне исправный кластер необходимой мощности, но структура решётки не может быть восстановлена наличными методами реконфигурации); годные ( в них может быть восстановлена решётка (матрица) ЭМ необходимой мощности).
Далее нашей целью будет разработка методов обеспечения отказоустойчивости ПМ и НПМ СБИС за счёт избыточности и специальных методов реконфигурации структуры.
В третьей главе рассматриваются алгоритмы реконфигурации ПМ и НПМ СБИС, отличающиеся от известных [248] возможностью программного задания количества и расположения резервных элементов. Исследуется их эффективность и работоспособность.
В п. 3.1. рассматриваются источники отказов СБИС и методы обеспечения отказоустойчивости [128,241+243,248-264] путем программирования структуры.
Задача обеспечения отказоустойчивости неразрезной процессорной матрицы
имеет несколько различных постановок в зависимости от категории годности пластин
СБИС. В случае ограниченно годных СБИС задача состоит в разработке оптимальных
структур и реализации отказоустойчивых связных процедур
[118+120,122,123,196,238-5-240]. В случае годных СБИС задача обеспечения отказоустойчивости сводится к вложению требуемой структуры в исправную часть неразрезной пластины [265-5-270]. Наиболее перспективными для модификации и развития представляются, с нашей точки зрения, алгоритмы реконфигурации с постоянным резервом, расположенным по краям матрицы, предложенные М. Сами и Р. Стефанелли [248].
В п.3.2. предлагаются локально-параллельные алгоритмы реконфигурации, обеспечивающие программное задание резерва.
Идея алгоритмов реконфигурации с программируемым резервом заключается в следующем. Избыточная система связей между ПЭ позволяет вкладывать в физическую структуру матрицы решетки заданного типа. Количество физических соседей одного ПЭ может достигать 14-16. Количество логических соседей определяется типом решетки. Реконфигурация структуры проводится на основе сигналов неисправности ПЭ. Множество таких сигналов образует синдром неисправностей, на основе ко-
25 торого происходит перестройка структуры ПМ. Каждый ПЭ имеет устройство управления, выполняющее перестройку коммутационных соединений. Сигналы перестройки формируются на основе сигналов, определяющих состояния ПЭ. Вычисление сигналов перестройки реализуется комбинационной схемой формирования сигналов перестройки. Расположение резервных элементов и их количество в [248] неизменно.
Сущность и изюминка предлагаемого подхода в том [225], резерв располагается в строках и столбцах исходной матрицы, задаваемых программно. Предлагаются четыре алгоритма: вертикальной перестройки, непосредственной перестройки, ограниченного захвата и свободного захвата. На Рис.5, показана реконфигурация процессорной матрицы по алгоритму свободного захвата.
Применение предлагаемых алгоритмов обеспечивает более высокую живучесть ПМ и НПМ СБИС благодаря возможности построения систем более низкой производительности [225-234] и постепенной деградации системы.
В п. 3.3. исследуется эффективность и работоспособность алгоритмов реконфигурации, с программируемым резервом. Показана их высокая эффективность по сравнению с известными алгоритмами (Рис. 6.). Даются рекомендации по программированию резерва (строки или столбцы резервировать?).
В п. 3.4. предлагается архитектура ОВС на НПМ с программируемым резервом. Система, использующая отказоустойчивую ПМ состоит из трех подсистем: монитор-ной, решающего поля и массовой памяти. Решающее поле - это множество ПЭ на одной или нескольких неразрезных пластинах. ПЭ соединены двумя каналами: регулярным и магистральным. Регулярный канал обеспечивает локальные информационные связи между соседними (достаточно близко расположенными друг к другу) ПЭ, а также связывает решающее поле с массовой памятью с параллельным доступом. Связи, обеспечиваемые регулярным каналом, функционально эквивалентны. При вложении 2-мерной решетки любая из них может быть назначена горизонтальной или вертикальной, входной или выходной по любому направлению. Информация передается по связи в обоих направлениях. Магистральный канал связывает все ПЭ с мониторной подсистемой, включающей в себя управляющую ЭВМ, и служит для передачи общей для всех ПЭ информации.
-й—и—й
нр—ф—ф—ф
Рис. 5. Перестройка матрицы по алгоритму свободного захвата.
Методы обеспечения отказоустойчивости процессорной матрицы [128,225,248] предполагают схемную реализацию коммутационного окружения процессорных элементов. В предлагаемых алгоритмах реконфигурации предполагается, что каждый ПЭ имеет коммутационное окружение, в том числе блок управления сигналами перестройки и блок управления коммутациями. Существенным недостатком этих методов является требование абсолютной надежности блока управления. При этом к фатальному отказу всей матрицы ведет отказ блоков управления как исправных, так и неисправных процессоров. Это обусловлено тем, что сигнал отказа e(i, j) соответствует от-
казу самого процессорного элемента (i,j) либо его коммутаторов. При выходе из строя блока управления неисправность распространяется на всю матрицу.
0,88
0,91
0,97
1,0
0,94
Рис. 6. Сравнение алгоритмов перестройки для матрицы 20x20:
с резервом по краям (пунктирная линия);
с дополнительными строкой и столбцом (сплошная линия) А- алгоритм непосредственной перестройки
В - алгоритм ограниченного захвата С - алгоритм свободного захвата
Программная реализация алгоритмов реконфигурации позволяет избавиться от неконтролируемого блока управления и исключить его из структуры процессорной матрицы. При этом снижаются аппаратные затраты и существенно повышается отказоустойчивость структуры. Тем не менее, остается нереальное предположение об абсолютной надежности структуры связей между ПЭ.
В четвертой главе предлагается новая консенсус-парадигма живучести процессорных матриц СБИС, более полно учитывающая особенности и реалии их использования при построении супер-ЭВМ. Следует заметить, что предлагаемый под-
28 ход может быть использован не только для неразрезных процессорных матриц, а и для любых систем, содержащих большое количество вычислительных модулей.
В п. 4.1. даётся критический анализ имеющихся подходов [176-5-222] к обеспечению отказоустойчивости вычислительных систем. Делается вывод об их недостаточности и даже непригодности для распределённых ОВС в условиях близкодействия и неразрезной технологии СБИС.
Развитие методов контроля и диагностики радиоэлектронной аппаратуры началось при следующих условиях.
Контролируемое и диагностируемое устройство присутствует в системе в единственном экземпляре.
Это устройство имеет высокую цену.
Элементы устройства можно заменять по мере их отказов. Минимальный заменяемый блок - типовой элемент замены (ТЭЗ) можно контролировать, диагностировать и ремонтировать на специальном стенде вплоть до замены отдельных электронных компонент.
Связи между ТЭЗ-ами дёшевы и либо абсолютно надёжны, либо их отказы приписываются элементам. И, вообще, проверка связей - вопрос отдельный.
5. Имеются абсолютно надёжные элементы, например, смесители Неймана [176].
Эти предположения сохранили свою силу и с появлением таких сложных уст
ройств, как ЭВМ. Однако в приложении к ЭВМ были развиты мощные программно-
аппаратные методы самотестирования и самодиагностики, без которых не приступает
к работе ни один современный компьютер. Отказоустойчивость ЭВМ и систем обес
печивается избыточностью и мажорированием [215]. Такой подход мы называем
классической парадигмой отказоустойчивости.
Отметим особенности задачи диагностики для ОВС и, вообще, для вычислительных систем, состоящих из одинаковых модулей.
Элементом замены в ОВС является элементарная машина (ЭМ) — устройство, которое обычно само по себе снабжается средствами самодиагностики.
Для предмета нашего исследования - ОВС на ПМ и, особенно, НПМ СБИС -замена вообще невозможна, поэтому выбор минимального диагностируемого элемента является предметом особого рассмотрения.
Структура системы однородна и локальна — связаны только соседи по месту.
В силу одинаковости ЭМ каждый элемент окрестности ЭМ является для неё эталоном и таких эталонов достаточно много (8 -5-16 и более).
Наличие большого числа эталонных модулей позволяет упростить ЭМ за счёт удаления средств индивидуальной самодиагностики, но в то же время требует разработки системной самодиагностики.
Эти мысли были высказаны ещё в 60-е годы [217] и породили целое направление исследований и разработок самодиагностирующихся модульных вычислительных систем. Основная идея состоит в том, что достаточно сложные модули могут диагностировать друг друга и по результатам взаимопроверок строится синдром состояния системы, в котором перечисляются все результаты взаимопроверок модулей. Далее по синдрому вычисляется "д:-разметка" множества модулей, в которой алгоритм самодиагностики пытается восстановить истинный образ неисправности, то есть выделить неисправные модули. Эта задача известна как проблема византийских генералов, пытающихся путём взаимопроверок и обменов результатами найти генералов-предателей и подсчитать число верных генералов. Указанная проблема далеко не всегда имеет однозначное решение. Более того, после установления всех исправных ПЭ необходимо соединить их всех в связную подсистему. Такой подход к обеспечению отказоустойчивости мы называем византийской парадигмой [127,129,177] или парадигмой византийского согласия всех исправных ПЭ. Для византийского согласия приняты все классические предположения о диагностируемой системе, кроме первого.
Мы предлагаем реальную консенсус-парадигму, суть которой заключается в следующем.
ПЭ много и они связаны однородной, локальной сетью связи.
Число связей у каждого ПЭ ограничено.
Связи можно программно включать, выключать и коммутировать.
Отдельные ПЭ и связи дёшевы относительно цены исправной НПМ.
Абсолютно надёжных ПЭ и связей нет.
Заменить отказавшие ПЭ и связи невозможно.
Византийское согласие всех исправных ПЭ ненужно и нереально.
Аппаратура самодиагностики не нужна. Соседние ПЭ могут служить эталонами
зо друг для друга, их число достаточно, чтобы изолировать неисправный ПЭ надёжнее чем самодиагностика.
Резервные ПЭ и связи не выделяются.
Отказоустойчивость достигается за счёт программирования структуры и избыточного числа ПЭ и связей между ними. Задача состоит в том, чтобы вложить требуемый граф в избыточный граф с отказами элементов и связей.
В п. 4.2. на основе консенсус-парадигмы предлагается новый подход к решению задачи реконфигурации 171,232-5-235,273,274] - метод консенсуса. Метод консенсуса не требует выделения резерва и учитывает как отказы процессоров, так и отказы связей.
Перестройка структуры ПМ проводится за счет использования резервных связей. Резервные элементы не выделяются. Каждый ПЭ можно использовать в качестве резервного. Каждый ПЭ тестируется и результаты тестирования сравниваются с результатами тестирования соседей. По результатам тестирования в каждом ПЭ создается список согласных с ним соседей.
Реконфигурация структуры ПМ (волновой алгоритм) на основе сигналов согласия проводится в четыре этапа: прямой ход, обратный ход, фиксация и настройка. На этапе прямого хода каждый ПЭ составляет список своих возможных логических номеров, основываясь на логических номерах согласных с ним соседей. Начиная с верхнего левого угла, ПЭ передают свои возможные логические номера согласным соседям с большими физическими номерами. Если физические номера несравнимы, то передача делается только в одном направлении, например от (і +1,7 ) к (i,j+l ). ПЭ получает логический номер (i,j), если возможные логические номера согласных с ним соседям удовлетворяют определенным условиям, зависящим от типа требуемой решетки.
Для того, чтобы логический номер (i,j) стал возможен необходимо найти среди предшественников некоторое множество уже вычисленных номеров.
Для квадратной решётки это пара {(ii,j]),(h> 7г)}. удовлетворяющая условиям
(1)[1 //-^1=1]л[|у;-у2|=1]
(2) [(/у < I2) -> (Jl >J2)] V [(І! > І2 ) -> (JJ
Для треугольной решётки это тройка {(ioiJo)>(ihJi)Ah>J2)}t удовлетворяющая
31 ещё одному условию:
(3) (iojo) = (тіл (i],i2 ), min (ji,j2))
Для решётки К* это уже четвёрка {(io,Jo), (hJA (h,j2), (UJ4)}, удовлетворяющая ещё одному дополнительному условию:
(4) (i4, м) = (max (ih i2) +1, min (J1J2))
Наконец, для решётки Ш необходимая конфигурация передающих, согласных соседей есть "прореженная" конфигурация квадратной решётки. Например, если чётности строк и столбцов совпадают, требуются условия (1) и (2), если не совпадают, достаточно одного передающего и согласного соседа слева.
Логический номер (/, J) во всех случаях вычисляется по формуле
(/,7) = ( max (i;, i2), max (jj,j2))
В результате прямого хода каждый ПЭ имеет множество возможных логических номеров. Если в результате прямого хода правый и нижний края ПМ оказались недостижимы, вырабатывается глобальный сигнал фатального отказа. Реконфигурация невозможна. В противном случае начинается обратный ход. При обратном ходе направления передачи логических номеров меняются на противоположные. Возможные логические номера вычисляются аналогично вычислениям прямого хода, а логический номер (i,j) вычисляется как (i,j)=(min ( і/, i2), min (7/,72 ))» гДе ( '/, h)» (7/,72) - логические номера соседей, удовлетворяющих условиям для решетки заданного типа. Логический номер (i,j ) считается допустимым для ПЭ, если он уже был получен в результате прямого хода. После обратного хода в списке допустимых логических номеров ПЭ остается пересечение множеств логических номеров прямого и обратного хода. Каждый ПЭ, имеющий несколько возможных логических номеров вырабатывает сигнал неоднозначности, который по магистральному каналу поступает в управляющую ЭВМ. На этапе фиксации выбирается единственный вариант решетки, после чего выполняется настройка физической структуры связей на полученную логическую нумерацию.
На Рис. 7. показана неисправная матрица размером 3x4. Элементы 0-ой и 4-ой строки, 0-го и 5-го столбца фиктивные. Связи с несогласными элементами отмечены штриховой линией. Конфигурация несогласных связей такова, что неисправности возможно были бы отнесены к заштрихованным ПЭ. При такой конфигурации неис-
правных ПЭ все алгоритмы главы 3 дают фатальный отказ. Использование волнового алгоритма позволяет получить работающую матрицу размером 3x3 (Рис. 8.).
Таблица 2.
Рис. 7. Синдром несогласия процессорной матрицы
Рис. 8. Консенсус процессорной матрицы
В п. 4.3. моделируется волновой алгоритм и исследуется его эффективность и работоспособность. На Рис. 9. представлена зависимость вероятности сохранения работоспособности Р{п, р) для волнового алгоритма (А) и алгоритма свободного захвата с программируемым резервом (В) - самого эффективного алгоритма из [225], осно-
Q75 Q8 Ц85 Q9 Q95
Рис. 9.
ванного на синдроме неисправности. Результаты получены для матрицы размером 20x20. Учитывая результаты моделирования и уменьшение аппаратных издержек, можно сделать вывод о большей эффективности волнового алгоритма.
Моделирование волнового алгоритма позволяет оценить пределы надежности однородных систем с согласием. Порог просачивания по согласным ПЭ характеризует живучесть системы с учетом ненадежности узлов и связей. В исследуемом алгоритме неисправности процессорных элементов и связей не рассматриваются. Неисправности представлены только сигналами согласия между соседними ПЭ.
Порог просачивания по ПЭ, имеющим хотя бы одного согласного соседа, характеризует отказоустойчивость системы с учетом ненадежности узлов и связей.
Рассматривается также связь просачивания по согласным элементам со смешанной задачей просачивания.
В заключении перечислены основные результаты диссертации. I. Подтверждена перспективность и решающая роль концепция ОВС в развитии со-
34 временных массово-параллельных процессоров.
II. Построена ординарная динамическая клеточная модель параллельной вычисли
тельной системы. Исследованы ее стохастические свойства.
Получены условия обратимости для систем на конечных графах с конечным числом состояний, устанавливающие связь между ординарными динамическими моделями и марковскими процессами.
Продемонстрирована возможность вычисления коэффициента готовности системы с учетом межмашинных взаимодействий.
Показана ограниченность модели случайного поля, связанная со слишком жестким для реальных систем требованием обратимости. Установлена область применения этой модели, а так же ее связь с теорией идеального коллектива.
III. Исследована перколяционная модель структурной надежности.
Показано, что требования локальности и однородности структуры не позволяют использовать слишком ненадёжные элементы.
Рассмотрены динамические модели структурной живучести при различных предположениях. Показано, что пределы надёжности однородной структуры являются величинами того же порядка, что и надёжность вентиля, а минимальный выход годных ПЭ на НПМ должен быть не ниже порога просачивания.
Даны два метода поиска порогов просачивания для произвольных однородных структур: метод моделирующей решётки и метод второй производной. Приведено точное решение классической задачи Хаммерсли для квадратной и шестиугольной решёток.
Разработана программа, моделирующая смешанную задачу просачивания. Получены критические области просачивания для наиболее популярных решеток. Показано, что с увеличением размеров матрицы пороговые эффекты теории просачивания становятся ярче выраженными.
IY. Исследованы подходы (парадигмы) к проблеме отказоустойчивости 1. Критически рассмотрены традиционные методы обеспечения отказоустойчивости вычислительных систем, в том числе основанные на взаимопроверках с построением синдрома неисправностей, и показана их недостаточность для решения проблемы отказоустойчивости ПМ и НПМ СБИС.
Обоснована необходимость смены подхода к обеспечению отказоустойчивости НПМ СБИС из-за невозможности замены отдельных элементов, неограниченных требований к степени связности модулей, отсутствия близкодействия и неадекватности "византийского согласия" всех исправных ПЭ.
На основе анализа источников отказов в СБИС и исследования пределов их надёжности сформулирована реальная парадигма живучести НПМ СБИС, учитывающая отказы ПЭ и связей и позволяющая использовать все полученные СБИС.
Y. Предложены и исследованы новые методы обеспечения отказоустойчивости ОВС на ПМ и НПМ СБИС.
На основе анализа источников отказов в СБИС и реальной парадигмы живучести НПМ СБИС, учитывающей отказы ПЭ и связей, предложен метод программирования резерва ПМ и НПМ СБИС, позволяющий менять избыточность от нуля или минимума в одну строку или столбец до максимума — четырёхкратной избыточности.
Предложены и исследованы алгоритмы реконфигурации НПМ СБИС с программируемым резервом: вертикальной перестройки, непосредственной перестройки, ограниченного захвата и свободного захвата.
Показана их высокая эффективность по сравнению с предшествующими алгоритмами Сами и Стефанелли.
Предложена архитектура ОВС на неразрезных процессорных матрицах СБИС с программируемым резервом.
Рассмотрена схемная реализация алгоритмов реконфигурации с помощью комбинационных микропрограммных клеточных автоматов (МПКА) и указано, что такая реализация предполагает абсолютную надёжность МПКА и всех связей в процессорной матрице.
Показана возможность программной реализации МПКА, свободной от неконтролируемых элементов процессорной матрицы.
Предложена стратегия самодиагностики неразрезной ПЭ, позволяющая построить синдром несогласия между соседними процессорными элементами и не требующая аппаратуры самодиагностики.
YI. Предложена новая консенсус-парадигма структурной живучести.
36 Показаны ее преимущества перед традиционными подходами к обеспечению отказоустойчивости ВС, в том числе основанных на взаимопроверках с построением синдрома неисправностей.
Разработан новый подход к решению задачи реконфигурации - метод консенсуса. Метод консенсуса опирается непосредственно на синдром несогласия, не требует выделения резерва и аппаратуры самодиагностики ПЭ, учитывает отказы процессоров и отказы связей и превышает по эффективности все другие методы. Предложена архитектура ОВС на неразрезных процессорных матрицах СБИС с программной реализацией метода консенсуса. Эта архитектура требует неразличимости вертикальных и горизонтальных связей в решающем поле, что полностью соответствует требованиям теории КАИС-структур.
Исследована работоспособность и эффективность метода консенсуса. Показано, что он является наиболее эффективным по сравнению с известными алгоритмами. Исследовано просачивание по согласным элементам в однородных структурах. Получены пороговые значения вероятности просачивания по согласным элементам для наиболее популярных структур, которые характеризуют живучесть системы с учетом ненадежности и узлов и связей.
Попутно получены приближенные значения для вероятностей просачивания по узлам и связям для случая смешанной задачи просачивания.
Основные принципы построения параллельных вычислительных систем
Программная реализация алгоритмов реконфигурации позволяет избавиться от неконтролируемого блока управления и исключить его из структуры процессорной матрицы. При этом снижаются аппаратные затраты и существенно повышается отказоустойчивость структуры. Тем не менее, остается нереальное предположение об абсолютной надежности структуры связей между ПЭ.
В четвертой главе предлагается новая консенсус-парадигма живучести процессорных матриц СБИС, более полно учитывающая особенности и реалии их использования при построении супер-ЭВМ. Следует заметить, что предлагаемый под 28 ход может быть использован не только для неразрезных процессорных матриц, а и для любых систем, содержащих большое количество вычислительных модулей.
В п. 4.1. даётся критический анализ имеющихся подходов [176-5-222] к обеспечению отказоустойчивости вычислительных систем. Делается вывод об их недостаточности и даже непригодности для распределённых ОВС в условиях близкодействия и неразрезной технологии СБИС. Развитие методов контроля и диагностики радиоэлектронной аппаратуры началось при следующих условиях. 1. Контролируемое и диагностируемое устройство присутствует в системе в единственном экземпляре. 2. Это устройство имеет высокую цену. 3. Элементы устройства можно заменять по мере их отказов. Минимальный заменяемый блок - типовой элемент замены (ТЭЗ) можно контролировать, диагностировать и ремонтировать на специальном стенде вплоть до замены отдельных электронных компонент. 4. Связи между ТЭЗ-ами дёшевы и либо абсолютно надёжны, либо их отказы приписываются элементам. И, вообще, проверка связей - вопрос отдельный. 5. Имеются абсолютно надёжные элементы, например, смесители Неймана [176]. Эти предположения сохранили свою силу и с появлением таких сложных уст ройств, как ЭВМ. Однако в приложении к ЭВМ были развиты мощные программно аппаратные методы самотестирования и самодиагностики, без которых не приступает к работе ни один современный компьютер. Отказоустойчивость ЭВМ и систем обес печивается избыточностью и мажорированием [215]. Такой подход мы называем классической парадигмой отказоустойчивости. Отметим особенности задачи диагностики для ОВС и, вообще, для вычислительных систем, состоящих из одинаковых модулей. 1. Элементом замены в ОВС является элементарная машина (ЭМ) — устройство, которое обычно само по себе снабжается средствами самодиагностики. 2. Для предмета нашего исследования - ОВС на ПМ и, особенно, НПМ СБИС -замена вообще невозможна, поэтому выбор минимального диагностируемого элемента является предметом особого рассмотрения. 3. Структура системы однородна и локальна — связаны только соседи по месту. 4. В силу одинаковости ЭМ каждый элемент окрестности ЭМ является для неё эталоном и таких эталонов достаточно много (8 -5-16 и более). 5. Наличие большого числа эталонных модулей позволяет упростить ЭМ за счёт удаления средств индивидуальной самодиагностики, но в то же время требует разработки системной самодиагностики. Эти мысли были высказаны ещё в 60-е годы [217] и породили целое направление исследований и разработок самодиагностирующихся модульных вычислительных систем. Основная идея состоит в том, что достаточно сложные модули могут диагностировать друг друга и по результатам взаимопроверок строится синдром состояния системы, в котором перечисляются все результаты взаимопроверок модулей. Далее по синдрому вычисляется "д:-разметка" множества модулей, в которой алгоритм самодиагностики пытается восстановить истинный образ неисправности, то есть выделить неисправные модули. Эта задача известна как проблема византийских генералов, пытающихся путём взаимопроверок и обменов результатами найти генералов-предателей и подсчитать число верных генералов. Указанная проблема далеко не всегда имеет однозначное решение. Более того, после установления всех исправных ПЭ необходимо соединить их всех в связную подсистему. Такой подход к обеспечению отказоустойчивости мы называем византийской парадигмой [127,129,177] или парадигмой византийского согласия всех исправных ПЭ. Для византийского согласия приняты все классические предположения о диагностируемой системе, кроме первого. Мы предлагаем реальную консенсус-парадигму, суть которой заключается в следующем. 1. ПЭ много и они связаны однородной, локальной сетью связи. 2. Число связей у каждого ПЭ ограничено. 3. Связи можно программно включать, выключать и коммутировать. 4. Отдельные ПЭ и связи дёшевы относительно цены исправной НПМ. 5. Абсолютно надёжных ПЭ и связей нет. 6. Заменить отказавшие ПЭ и связи невозможно. 7. Византийское согласие всех исправных ПЭ ненужно и нереально. 8. Аппаратура самодиагностики не нужна. Соседние ПЭ могут служить эталонами зо друг для друга, их число достаточно, чтобы изолировать неисправный ПЭ надёжнее чем самодиагностика. 9. Резервные ПЭ и связи не выделяются. 10. Отказоустойчивость достигается за счёт программирования структуры и избыточного числа ПЭ и связей между ними. Задача состоит в том, чтобы вложить требуемый граф в избыточный граф с отказами элементов и связей.
В п. 4.2. на основе консенсус-парадигмы предлагается новый подход к решению задачи реконфигурации 171,232-5-235,273,274] - метод консенсуса. Метод консенсуса не требует выделения резерва и учитывает как отказы процессоров, так и отказы связей.
Перестройка структуры ПМ проводится за счет использования резервных связей. Резервные элементы не выделяются. Каждый ПЭ можно использовать в качестве резервного. Каждый ПЭ тестируется и результаты тестирования сравниваются с результатами тестирования соседей. По результатам тестирования в каждом ПЭ создается список согласных с ним соседей.
Реконфигурация структуры ПМ (волновой алгоритм) на основе сигналов согласия проводится в четыре этапа: прямой ход, обратный ход, фиксация и настройка. На этапе прямого хода каждый ПЭ составляет список своих возможных логических номеров, основываясь на логических номерах согласных с ним соседей. Начиная с верхнего левого угла, ПЭ передают свои возможные логические номера согласным соседям с большими физическими номерами. Если физические номера несравнимы, то передача делается только в одном направлении, например от (і +1,7 ) к (i,j+l ). ПЭ получает логический номер (i,j), если возможные логические номера согласных с ним соседям удовлетворяют определенным условиям, зависящим от типа требуемой решетки.
Традиционные подходы к обеспечению отказоустойчивости
Однородная вычислительная система (ОВС) — система, состоящая из большого числа одинаковых элементарных вычислительных машин (ЭМ), соединенных регулярной программно-управляемой коммуникационной сетью - регулярным каналом (РК). Каждая ЭМ снабжена устройством управления (УУ), как обычная ЭВМ, и системным устройством (СУ).
Предполагается, что ЭМ представляет собой универсальную ЭВМ в современном исполнении с применением всех известных идей ускорения вычислений. Каждая ЭМ имеет свое устройство управления, что избавляет от необходимости выключать ЭМ из процесса вычислений. Каждая ЭМ реализует свою ветвь параллельной программы по своим внутренним условиям. СУ обеспечивает межмашинные взаимодействия в процессе счёта и управление коммутациями в системе связи. Функции СУ: коммутация каналов, передача и приём сообщений. ОВС не имеет общего УУ, которое осуществляло бы управление ходом вычислительного процесса по значениям переменных, общих для всех ветвей параллельной программы или нескольких программ, выполняемых параллельно. Каналы, образуемые в системе связи ОВС, являются асинхронными, а отсчёт времени свой в каждой ЭМ. В отличие от систем с общим управлением ОВС не имеет тактового генератора. Управление ходом вычислений в ОВС состоит из управления порядком действий и синхронизации параллельных ветвей. По способу организации системы связей ОВС напоминают вычислительные сети. В вычислительной сети связи между ЭВМ используются в режиме управления заданиями и для передачи массивов данных от задачи к задаче или просто между ЭВМ. В ОВС система связи используется для других целей и с большей интенсивностью: регулярная сеть связи ОВС функционирует в режиме счёта при реализации параллельной программы.
Программируемость структуры является основополагающим принципом, на него опирается возможность создания живучих отказоустойчивых систем. Работы над ОВС начались в СССР в ИМ СО АН СССР под руководством Э.В. Евреинова в 1962 году [1,2] и продолжались Институте математики СО АН СССР [3,5,8]. Направление ОВС успешно развивается, как в России, так и за рубежом, тесно переплетаясь с развитием других типов [6,7] параллельных систем, основанных на идее однородности [116,117]. В дальнейшем идеология ОВС обогащалась, развивалась [5] и в понятие ОВС вошли самые разнообразные однородные системы с программируемой структурой [8]. Родственные направления- развития параллельных архитектур: пирамидальные системы обработки изображений, содержащие несколько слоев (пирамиду) матричных структур [46,47]; оптические ЭВМ [48-н49]; систолические массивы [55-5-62]; транспьютерные системы (примеры можно найти в [14]); нейронные сети [51-Ї-54]. Последние исследования автора на эту тему [171,172,175,225,226,228-230,232-235,273] относятся к разработке ОВС с программируемой структурой на неразрезной СБИС в условиях невозможности замены неисправных ЭМ. В настоящее время концепция ОВС стала ведущей для параллельных суперЭВМ. Теоретические исследования и проекты, успешно развивающиеся с 60-х годов, воплощаются в жизнь, становятся частью реальности. Господствующее положение занимают массово-параллельные процессоры (МПП, МРР) - параллельные вычислительные системы, построенные на принципах ОВС. Особенно важно, с точки зрения дальнейшего развития, что МПП активно используются не только в научно-технических исследованиях, но и в коммерческих проектах. МПП находят применение в области управления сложными техническими системами и в обработке коммерческой информации для решения стратегических задач бизнеса, для работы с реляционными базами данных и для обработки запросов в сетях с технологией клиент-сервер. Крупнейшие производители ЭВМ для коммерческих применений -фирмы IBM и Amdahl с 1994 года выпускают параллельные суперсерверы для сетей ЭВМ [15]. Ускоренному развитию приложений МПП способствуют национальные и международные государственные программы содействия: в 1995 г. в США была принята Программа Ускоренной стратегической компьютерной инициативы (Accelerated Strategic Computing Initiative - ASCI), рассчитанная на 10 лет, инициатива НРСС (высокопроизводительная вычислительная техника и средства связи) ассигнует по несколько сот миллионов долларов в год на разработку МПП, в Европе - проекты Esprit и Framework-4. Свои программы имеют Япония Китай и Индия. К исследованиям в этом направлении подключились крупнейшие университеты США. Комитета по техническим исследованиям при Министерстве обороны США (DARPA) в рамках Стратегической Компьютерной Программы. DARPA профинансировал разработки Connection Machine фирмы Thinking Machine, Batterfly фирмы BBN, Warp университета Карнеги-Меллона для машинного зрения в автоматическом транспортном средстве фирмы Martin-Marietta. Отметим, что все современные МПП отказоустойчивы и наращиваемы, подавляющее большинство имеют архитектуру класса МКМД (много команд, много данных), снабжены компиляторами для параллельных версий популярных языков: С, C++, Fortran, Pascal, Prolog, Cobol, ADA и других, все они могут работать в современных ОС, таких как Unix в различных версиях.
НПМ с перестраиваемой структурой и программируемым резервом
В работах [1-5-9] ОВС рассмотрены как коллективы вычислителей, основанные на принципах параллельности вычислений, программируемое структуры и конструктивной однородности. Идея коллектива вычислителей является общей. Сформулированная в терминах вычислительной техники (регистр, устройство, схема, канал), она отражает конкретные технические представления разработчиков. В формализованном виде рассматриваются математические модели и соответствующие средствах имитационного моделирования.
В техническом описании ОВС и первой модели параллельных вычислений [1,2] нет формального аппарата, позволяющего учесть реальную асинхронность системы, неодновременность событий, происходящих в различных ЭМ. Согласно этой модели, параллельные вычисления есть набор последовательных вычислений над различными частями данных одной и той же задачи. Все элементы данных должны взаимодействовать между собой в процессе вычислений, для этого вычисления время от времени приостанавливаются и начинается массовый обмен данными. При этом все выделенные для этого обмена ЭМ должны вступить во взаимодействие одновременно. Однако, требование одновременности взаимодействий противоречит идее создания вычислительных систем неограниченной производительности, то есть таких систем, производительность которых всегда можно увеличивать, добавив ещё один вычислитель.
В дальнейшем предпринимались попытки формализации технического описания ОВС с учётом асинхронности системы [4].
Другим важным недостатком технического описания ОВС является отсутствие средств анализа случайностей в поведении системы. В системах , насчитывающих десятки тысяч вычислителей сбои и отказы будут происходить настолько часто, что ими уже нельзя пренебрегать. Компенсацией этого недостатка явились работы, обобщённые в [3], рассматривавшие ОВС как статистический ансамбль. Каждому элементу системы ставится в соответствие марковский процесс, протекающий независимо от остальных. Поведение конечной системы в этом случае также описывается обобщённым марковским процессом. В [3] представлены основные результаты предшествующих исследований в области теории однородных вычислительных систем. Получены оценки и расчётные формулы для надёжности, стоимости и производительности ОВС, предложены алгоритмы функционирования, то есть алгоритмы, управляющие работой системы. В основу большинства этих исследований положено представление об ОВС, как идеальном коллективе элементарных машин. Это означает, что: ОВС состоит из взаимодействующих, ненадёжных, но независимых, то есть не мешающих друг другу при сбоях, ЭМ; структура система связей ОВС абсолютно надёжна и обеспечивает любые коммутации между ЭМ; производительность ОВС прямо пропорциональна числу ЭМ; все потоки заявок в ОВС - простейшие. При таком взгляде на ОВС в поле зрения исследователя попадает только множество ЭМ и его возможности в обеспечении заданных требований при некоторой идеальной организации. Будем условно называть такую теорию — теорией идеального коллектива. Соответственно и предложенные алгоритмы функционирования устанавливают только внешнюю дисциплину ОВС. Их задача состоит в выборе задач из заданного пакета или потока (управляемого или нет) и в выделении отдельных подсистем (подмножеств ЭМ) для решения этих задач. Внешняя дисциплина минимизирует суммарный штраф за задержку решения или общее время решения.
Для решения задач, связанных с разработкой архитектуры вычислительной системы, построением и анализом операционных систем, более удобным оказывается алгоритмическое описание, предназначенное для исследования ОВС на функциональном и системном уровне. Недостатком алгоритмического описания является тот факт, что для разностороннего анализа поведения ОВС используется в основном трудоёмкий метод имитационного моделирования.
Исследования коллективного поведения восходят ещё к Дж.фон Нейману, предложившему [ПО] клеточные автоматы. В дальнейшем это направление получило значительное развитие ([110-ьІ 13]). Параллельные подстановки являются обобщением нормальных алгоритмов Маркова, пригодным для описания клеточных автоматов. В [111] рассмотрена синхронная интерпретация параллельных подстановок, в [113] — асинхронная. Вычислительная машина представляет собой объект, имеющий достаточную сложность, чтобы интерпретировать программу, записанную в её память. Теория автоматов не располагает ни языком для компактного описания такого объекта, ни средствами для его анализа. Отказ от автоматного рассмотрения клеточных систем [114] привел к построению машины клеточных автоматов с возможностями программирования на языке высокого уровня.
Рассмотрение имеющихся моделей ОВС приводит к необходимости разработки математической модели ОВС, предназначенной для анализа проектируемых систем и получения характеристик их эффективности. Эта модель должна быть достаточно простой, а, следовательно, отражать только наиболее существенные свойства ОВС — взаимодействия между элементарными вычислителями. Анализ показывает, что однородная вычислительная система, обладающая сверхвысокой производительностью, должна удовлетворять следующим требованиям: асинхронность - отсутствие единого дискретного времени; децентрализация — отсутствие единого управляющего органа; распределенность - отсутствие ресурса, общего для всех элементов; близкодействие - наличие взаимодействия только с ближайшими соседями в некоторой структуре. Этим требованиям удовлетворяет конечное множество асинхронных марковских автоматов, соединенных между собой регулярным способом. Математической моделью такой системы являются обобщенные, асинхронные, недетерменированные, параллельные подстановки со следующими свойствами.
Волновой алгоритм поиска консенсуса
Свойство марковости случайных полей является объектом пристального внимания математиков [150-165] и в ряде случаев позволяет строго получить гиббсовское описание стационарного состояния поля. Подавляющее большинство работ посвящено марковским полям, в частности, полям на с/-мерной целочисленной решетке, элементы которой принимают два значения (модель Изинга). Модель Изинга нашла широкое применение в статистической физике, а также в биологии при исследовании популяций. Случай двоичного поля хорошо исследован и для другой простой структуры - дерева.
Популярность двоичного поля [151,156,163,164] объясняется тем, что в этом случае легко получаются и, главное, имеют полезную интерпретацию аналитические результаты для некоторых частных случаев: поле с положительной мерой, все мыслимые состояния которого имеют ненулевую вероятность; обратимые системы, функционирование которых не зависит от направления хода времени. Многие физические системы обладают этими свойствами.
В приложении к теории ОВС двоичный случай полезен, но явно недостаточен. Во-первых, элементарные автоматы - экспликации системных блоков элементарных машин - могут иметь достаточно большой внутренний алфавит. Во-вторых, не все конфигурации будут достижимы при функционировании. В третьих, при разных начальных условиях случайный процесс, протекающий в системе, в общем случае неэргодичен, но может иметь несколько эргодических множеств, или не иметь ни одного. В-четвертых, поведение исследуемых систем вовсе необязательно будет обратимым, чаще наоборот. Конструктивных результатов по теории дискретных случайных полей, относящихся к общему случаю, крайне мало.
Наиболее подробно рассмотрен случай гиббсовского описания, соответствующий стационарному (равновесному) состоянию стохастической клеточной модели. Для существования и единственности такого описания кроме свойства марковости необходима вакуумность поля, т. е. наличие вакуумного состояния элемента (компоненты), переход в которое возможен в любых условиях. Интерпретацией такого состояния служит, например, выход элемента из строя. Вакуумность автоматически выполняется для полей с положительной мерой. Эквивалентность марковских случайных полей с положительной вероятностной мерой и гиббсовских состояний с потенциалом ближайшего соседства была показана Аверинцевым М.Б. для конечных подмножеств целочисленной решетки для случая, когда компоненты принимают произвольное конечное число значений [146,147]. Для конечного поля на конечных и счетных графах этот вопрос решен в монографии Престона К. [156,163]. Оказывается, что для полей с конечным числом элементов соответствующие результаты легко переносятся на случай произвольного графа и конечного алфавита элементарного автомата. Этот перенос подробно проделан в настоящей работе в п. 1.4.6.
Динамика поведения случайных систем: эргодичность процесса на бесконечной d - мерной решетке и конечные обратимые системы для двоичного случая исследованы в [130-136,156,163].
Эргодичность исследована Р.А. Добрушиным для локальных систем интенсивностей переходов в предположении ординарности потока событий в системе. Получено достаточное условие эргодичности бесконечной системы в случае d - мерной целочисленной решетки [149-152]. При независимых компонентах это условие сводится к эргодичности отдельной компоненты. Кроме того, предполагается, что конечное множество тех же компонент таково, что его поведение описывается эргодическим процессом. Таким образом, вопрос об эргодичности сводится Р.А. Добрушиным к вопросу существования и единственности финальной вероятности состояний элемента, т. е. к вопросу о сходимости вероятностных мер на бесконечной решетке.
Результат Добрушина заслуживает отдельного комментария. Оказывается, эргодичность бесконечной системы зависит от соотношения двух величин/; и gi, где fi - мера минимальной интенсивности переходов внутри / - той компоненты, gi - мера максимального влияния (изменения интенсивностей переходов в компоненте) окрестности / - той компоненты на ее поведение. Теорема Добрушина гарантирует эргодичность бесконечной а - мерной системы только тогда, когда fi gu т. е. когда внутренние причины изменений в компоненте превышают внешние влияния на нее. Системы с превалирующим «индивидуальным» поведением эргодичны; для систем, элементы которых ориентируются на «коллективные» тенденции, этого сказать нельзя.
Для ординарной динамической клеточной модели типичным оказывается случай, когда интенсивности переходов компонент могут обращаться в нуль при некоторых окрестностях. В этих условиях невозможно гарантировать эргодичность компоненты, а тем более их (пускай конечного) множества. Вопрос об эргодичности стохастической клеточной модели оказывается вопросом о беступиковой работе соответствующей системы параллельных подстановок. Эта проблема выходит за рамки рассматриваемого направления.
Многие вопросы, касающиеся общих свойств таких полей решены, но самые интересные с точки зрения ординарной динамической клеточной модели ждут своего решения. Таковы вопросы о соотношении локальности системы интенсивностей перехода и марковости поля, о свойствах систем, в которых интенсивности перехода могут обращаться в нуль, о системах с несколькими эргодическими множествами состояний. Следует отметить случай, когда существующие методы теории случайных полей могут дать немедленный результат. Это случай, когда компоненты случайного поля вообще не зависят друг от друга. Но в этом случае теория случайных полей есть просто одно из возможных строгих обоснований метода динамики средних, который успешно применен в В.Г. Хорошевским [3] для исследования живучести ОВС. Более того, метод динамики средних позволяет учесть влияние общих ресурсов (например, восстанавливающих устройств) на поведение системы. Таким образом, если говорить о соотношении теории случайных полей и теории идеального коллектива, развитой В.Г. Хорошевским, то можно констатировать только их вырожденное пересечение. Теория идеального коллектива не учитывает влияния структуры связей, теория случайных полей не учитывает общих ресурсов. Там, где нет ни структуры, ни общих ресурсов, годны обе модели.
