Введение
ГЛАВА 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
