НАНОТЕХНОЛОГИЯ НА ПУТИ К РЕЛЯТИВИСТСКИМКОМПЬЮТЕРАМ

ПРОБЛЕМА БЫСТРОДЕЙСТВИЯ
Фундаментальная задача современной науки и техники - достижение быстродействия компьютеров
1012 ÷1016 Flops и более.
От решения этой проблемы зависит дальнейшее продвижение во многих стратегически важных отраслях науки, техники, экономики.

ИСТОРИЯ СУПЕРКОМПЬЮТЕРОВ
В РОССИИ
1958 – клеточные автоматы фон Неймана (теория)
1962 – однородная машина Холланда (теория).
1964 – ОВС МИНСК-222 (Э.В.Евреинов, Ю.Г.Косарев)
1975 – ОВС СУММА (В.Г. Хорошевский, В.А.Воробьёв, С.Г.Седухин и др.)
1978 – ОВС МИНИМАКС (В.Г. Хорошевский, Ю.К. Димитриев, Л.С. Шум, Н.Н. Меренков и др.)
1980 – ПС-2000 (И.В.Прангишвили, С.И.Медведев, Я.С.Виленкин и др.)
1995 – МВС-100 (А.В.Забродин, В.К.Левин, В.В.Корнеев)
2000 – МВС-100Х (А.В.Забродин, В.К.Левин, В.В.Корнеев)
2005-2010 – Вычислительные кластеры «Чебышев» и «Ломоносов», ВЦ МГУ

ПУТИ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ
1. БУФЕРИЗАЦИЯ,
обеспечивающая сглаживание потоков команд и данных. Буферизация применяется, в первую очередь, при организации иерархической памяти компьютера: сверхбыстродействующая регистровая память, КЕШ, основное ОЗУ, встроенные накопители, сменные накопители.
Не менее успешно применяются и буферы команд, которые открывают новые возможности для управления счётом: конвейер обработки команд, захват циклов, планирование загрузки устройств и так далее.

ПУТИ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ
2. КОНВЕЙЕРИЗАЦИЯ,
позволяющая ускорить исполнение повторяющихся последовательностей действий при приемлемом увеличении оборудования.
Наиболее известны: векторные арифметические устройства (микроконвейеры).
Конвейеризации поддаются и потоки команд (командные магистрали),
и последовательности этапов обработки (макроконвейеры).

ПУТИ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ
3. СТРУКТУРНАЯ РЕАЛИЗАЦИЯ,
позволяющая настроить аппаратуру специально для решения данной задачи. Структурная (аппаратурная) реализация − основа вычислительной техники. В современных компьютерах структурно реализованы алгоритмы управления внешними устройствами, функциональные устройства для отдельных команд, протоколы обменов. Архитектура компьютера с сокращённой системой команд (RISC-архитектура) открывает возможности для структурной реализации команд и соответствующего роста производительности.
На системном уровне структурная реализация состоит в соединении элементов системы в соответствии со структурой задачи − программировании структуры.

ПУТИ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ
4. РАСПАРАЛЛЕЛИВАНИЕ,
позволяющее максимально использовать естественный параллелизм вычислений и привлечь к вычислениям большое число процессоров. Параллелизм используется повсеместно:
1. параллельное считывание слов в расщеплённом ОЗУ,
2. параллельные процессоры для управления периферией,
3. параллельно работающие векторные и скалярные арифметические устройства конвейерных супер-компьютеров,
4. многопроцессорные системы и суперкомпьютеры,
5. Однородные Вычислительные Системы (ОВС) и их зарубежные реализации − Массово Параллельные Процессоры (МПП).

ПУТИ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ
5. БАЛАНСИРОВКА НАГРУЗКИ,
то есть такое планирование работ, при котором вся аппаратура загружается равномерно и не простаивает в ожидании. Методы балансировки могут быть как аппаратурными, так и программными и зависят от архитектуры компьютера.
Упомянутые принципы встречаются во всех современных компьютерах.

ИСТОЧНОКИ ПАРАЛЛЕЛИЗМА
Существует два источника параллелизма
1. Независимые операторы алгоритма.
2. Независимые вычисления над разными данными.
Независимость операторов дает параллелизм, ограниченный малым числом операторов.
Независимые вычисления над данными могут выполняться параллельно, причем число параллельных ветвей вычисления задается количеством получаемых результатов, обычно очень большим.
Иными словами, в первом случае стоит задача распараллеливания на множестве операторов в заданном алгоритме, во втором случае распараллеливается множество возможных исполнений этих операторов.
Второе множество значительно больше первого.

СИЛА ПАРАЛЛЕЛИЗМА
Пусть происходит умножение матриц C=A∙B размера (N×N). Тогда в каждом витке ijk-цикла выполняется
cij (k + 1) := aik × bkj + cij (k) , k = 1,…, N
Если иметь N ² вычислителей для каждого элемента cij матрицы C, вычисление было бы завершено в N² раз быстрее. Такова «сила параллелизма».
Емкостная сложность последовательного алгоритма O(3N²). В параллельном способе каждый из N 2 вычислителей должен иметь 2N чисел в качестве исходных данных и одно число cij на выходе. Емкостная сложность, следовательно,
O(2N³ + N²).
Если мы хотим сохранить оценку O(3N²), мы должны обеспечить одну из следующих альтернатив.

СИЛА ПАРАЛЛЕЛИЗМА
1. Работу всех N ² вычислителей над общей памятью.
2. Хранение в памяти каждого вычислителя минимальной части информации (3 числа: cik, bkj, cij ) и обмен данными N3 раз.
Параллельные компьютеры, реализующие первую альтернативу, называются системами с общей (разделяемой) памятью.
Параллельные компьютеры, реализующие вторую альтернативу, называются системами с локальной (распределенной) памятью.
В системах с общей памятью коммутатор соединяет процессоры с блоками расщеплённой памяти.
В системах с локальной памятью коммутатор соединяет только процессоры
Поэтому иногда говорят о системах с разделённым и неразделённым коммутатором.

ДВА КЛАССА ПАРАЛЛЕЛЬНЫХ СИСТЕМ

КЛАССИФИКАЦИЯ ПАРАЛЛЕЛЬНЫХ СИСТЕМ
Э.Таннен-баум.
Архи-тектура компью-тера. –
Питер, 2006.

КЛАССИФИКАЦИЯ ПАРАЛЛЕЛЬНЫХ СИСТЕМ
Пусть (О/М)К МД означает ОКМД либо МКМД. Например, ОКМД (О/Л)П – класс ОКМД систем, включающий системы и с общей ОП, и с локальной ЛП памятью П. Введём дополнительно:
1) для указания типа коммутатора К – буквы Ц и Р:
ЦК– централизованный, РК – распределённый коммутатор
2) типа структуры С: ЖС – жесткая или ПС – программируемая структура.
Получим классификацию параллельных компьютеров, содержащую 16 типов:
(О/М)К МД (О/Л)П (Ц/Р)К (Ж/П)С.

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
1. ВЫСОКАЯ СТОИМОСТЬ.
В соответствии с законом Гроша (Grosch), производительность компьютера П возрастает пропорционально квадрату его стоимости Ц:
П = kЦ2
В результате гораздо выгоднее получить требуемое быстродействие приобретением одного производительного процессора, чем использование нескольких менее быстро-действующих процессоров.

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
2. ПОТЕРИ ПРОИЗВОДИТЕЛЬНОСТИ ПРИ ОРГАНИЗАЦИИ ПАРАЛЛЕЛИЗМА.
Согласно гипотезе Минского (Minsky), ускорение, достигаемое при использовании параллельной системы, пропорционально двоичному логарифму от числа N процессоров (??):
S = О(log2 N)
Так на 1000 процессорах возможное ускорение оказывается равным
log2 1000 ≈10 (??)

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
3. ОПЕРЕЖАЮЩЕЕ СОВЕРШЕНСТВОВАНИЕ ПОСЛЕДОВАТЕЛЬНЫХ КОМПЬЮТЕРОВ.
По закону Мура (Moore) быстродействие последовательных процессоров возрастает практически в 2 раза каждые 18 месяцев. История показывает, что быстродействие компьютера увеличивалось на порядок каждые 5 лет.
Необходимая производительность могла быть достигнута и на последовательных компьютерах.

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
4. НЕИЗБЕЖНОСТЬ ПОСЛЕДОВАТЕЛЬНЫХ ВЫЧИСЛЕНИЙ.
В соответствии с законом Амдаля (Amdahl) ускорение S процесса вычислений при использовании N процессоров составит всего
S ≤ [α - (1- α)/N]-1
где α – доля последовательных вычислений, т.е., при наличии 10% последовательных команд, эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных.

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
Закон Амдаля
а - доля последовательных вычислений

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
5. ЗАВИСИМОСТЬ ЭФФЕКТИВНОСТИ ОТ СТРУКТУРЫ СИСТЕМЫ
Параллельные системы отличаются существенным разнообразием архитектурных принципов построения, и максимальный эффект от использования параллелизма может быть получен
только при полном использовании всех особенностей аппаратуры.
Перенос параллельных алгоритмов и программ между разными типами систем становится затруднительным (если вообще возможен).

ПРЕПЯТСТВИЯ НА ПУТИ ПАРАЛЛЕЛЬНЫХ КОМПЬЮТЕРОВ
6. ОТСУТСТВИЕ ЭФФЕКТИВНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.
Существующее программное обеспечение ориентировано, в основном, на последовательные компьютеры.
Для большого количества задач уже имеются готовые программы и все они ориентированы, главным образом, на последовательные компьютеры.
Переработка такого количества программ для параллельных систем не всегда оправдана.

ПАРАМЕТРЫ ПАРАЛЛЕЛИЗМА
Степенью параллелизма алгоритма называется число p операций, которые можно выполнять одновременно.
Пусть:
Vp(N) – число операций параллельного алгоритма
k - число этапов параллельного алгоритма.
Средней степенью параллелизма pср называется отношение
pср = Vp(N)/ k

ПАРАМЕТРЫ ПАРАЛЛЕЛИЗМА
Пусть:
Т1 – время исполнения алгоритма на одном процессоре.
Tпар – время исполнения параллельного алгоритма на р
процессорах.
Ускорением параллельного алгоритма называется величина:
Sпар = T1/ Tпар
Эффективностью параллельного алгоритма называется величина:
Eпар = Sпар /p,
где p – максимальная степень параллелизма

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
Редукция вектора – пример вырождения параллелизма
Редукция вектора X = xn-1> – получение суммы его элементов
x0n = ∑j = 0...n-1 xj
получается сдваиванием. Получение частичных сумм
x0i = ∑j = 0...i xj
получается рекурсивным сдваиванием.

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
Для алгоритма сдваивания число операций равно
Vp(N) = N – 1,
число этапов сдваивания k = log2N ,
средняя степень параллелизма равна:
pср= (N-1)/ log2N

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
Для рекурсивного сдваивания
Vp(n) = N log2N – (N + 1)
число этапов сдваивания равно k = log2N
pср = N – (N + 1)/ log2N
Здесь степень параллелизма p = N / 2

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
Пусть
t – время сложения,
β – коэффициент затрат на передачу данных
βt – время переноса данных на каждом этапе сдваивания. Игнорируя прочие издержки, имеем :
T1 = (N – 1)t = (2p –1)t
Tпар = [log2N] (t + βt) = (1 + log2p)(1 + β)t
Ускорение Sпар = T1/Tпар= (N-1)/(1 + β)log2p
Даже при β = 1 имеем Sпар = (N-1)/2log2p
т.е. ускорение падает вдвое по сравнению с идеальным случаем, когда нет потерь на передачу информации и β = 0.

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
как следствие его недостаточности
При больших p и при β = p
ускорение параллельного сдваивания:
Sпар = O(p/log2p)
эффективность параллельного сдваивания:
Eпар= 2/log2N → 0 при p = N/2 →∞
Итак, недостаток параллелизма приводит к неполной загрузке параллельной системы и к низкой эффективности.
Возникающая отсюда проблема называется балансировкой нагрузки или задачей вложения параллельных вычислений в систему. Плохое вложение может не только снижать полезную нагрузку на процессор, но и увеличивать время обмена информацией, т.е. величину β.

ФУНДАМЕНТАЛЬНЫЕ ПРЕДЕЛЫ ПРОИЗВОДИТЕЛЬНОСТИ
Наблюдение за развитием современной вычислительной техники говорит о достижении ФУНДАМЕНТАЛЬНЫХ ПРЕДЕЛОВ роста производительности и последовательных и параллельных компьютеров:
светового и теплового.
Старые методы вычислений оказываются менее чувствительными к этим пределам.
Это не удивительно, поскольку они разрабатывались для человека с его низкой скоростью последовательной обработки информации и высшей степени параллелизма восприятия, распознавания и обработки зрительных образов.

СВЕТОВОЙ БАРЬЕР
Световой барьер ограничивает размер синхронного компьютера соотношением:
f⋅d ≤ c
с – скорость света
(2⋅1011мм/с ≤ c ≤ 3⋅1011мм/с),
f – тактовая частота,
d – диаметр системы.

СВЕТОВОЙ И ТЕПЛОВОЙ БАРЬЕРЫ
ТРИ НАПРАВЛЕНИЯ развития параллельных вычислительных систем:
1. Классическое
2. Технологическое
3. Релятивистское

ЕСТЬ ДВЕ ТЕОРИИ ВЫЧИСЛЕНИЙ:
КЛАССИЧЕСКАЯ И РЕЛЯТИВИСТСКАЯ
Классическая теория вычислений пренебрегает временем доставки данных к процессору. Это теория медленных вычислений, как и вся классическая механика – теория медленных движений. И уже там происходит вырождение!
Релятивистская теория вычислений основное внимание уделяет доставке данных к процессорам. Это, как и релятивистская механика, теория быстрых вычислений.

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
как следствие светового барьера
В общем случае для p процессоров имеем ускорение:
Sp= T1 / [T1(α1+ k -1α2 + p-1 α3) + td] для обменов данными перемежающихся с вычислениями.
Sp= T1 / max[T1(α1+ k -1α2 + p-1 α3), td] для обменов данными параллельных с вычислениями.
Где:
α1 – доля операции, выполненные одним процессором,
α2– доля операции со средним ускорением k,
α3 – доля операции с максимальным ускорением p,
td – время доставки данных, т.е. задержка, необходимая для перемещения и размещения данных в местах продолжения вычислений.

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА как следствие светового барьера
Закон Амдаля получается как в классической механике, если положить,
td = 0, α2 = 0, α1 = α, α3 = 1 – α
где α – доля последовательных операций.
Поступим наоборот. В духе релятивистской теории
не будем пренебрегать величиной td. Положим α1 = α2 = 0, α3 = 1, т.е. все вычисления параллельны в максимальной степени p.
где l1 и l2 – некоторые константы.

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА
как следствие светового барьера
Реалистично полагать для одномерных систем:
td = l1p f(T1, p)
а для двумерных систем:
td = l2p1/2 f(T1, p)
Пусть f(T1, p) = О(T1) ,
т.е. пропорционально числу T1 вычислительных операций,
Тогда даже при максимальном параллелизме имеем
Sпар,1= О(p/(l1p2) → 0 при p → ∞
Sпар,2= О(p/(l1p1,5) → 0 при p → ∞
В ОБЩЕМ СЛУЧАЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ МЕДЛЕННЕЕ ПОСЛЕДОВАТЕЛЬНЫХ!?

ПРИНЦИП ЛОКАЛЬНОСТИ
Для параллельных вычислений нужны такие функции td = f(T1, p), которые
1. отражают технические возможности коммутаторов,
2. ограничивают рост затрат на взаимодействие td.
Подходящие функции
f1(T1, p) = O(T1⋅ p-1),
O(T1 ⋅p-1) ≤ f2(T1, p) ≤ O(T1 ⋅p–½)

ПРИНЦИП ЛОКАЛЬНОСТИ
Параллельные вычисления
не вырождаются при
td1 = l1p f(T1, p) = l1pkT1⋅ p-1 = lT1
p-1/2 ≤ td2 ≤ lT1
Требуемый вид функции f(T1,p) обеспечивается
параллельными операциями обмена информаций.
Это возможно в двух случаях.

ПРИНЦИП ЛОКАЛЬНОСТИ
1. В системе с общей памятью все запросы от p процессоров идут к различным банкам памяти, а коммутатор между процессорами и памятью допускает все p соединений одновременно.
2. В системе с локальной памятью обмены данными происходят так, что все p (или p1/2 ) процессоров передают, и все p (или p1/2 ) процессоров принимают информацию локально (соседям) и одновременно.
Второй подход назван нами мелкозернистое локально-параллельное программирование
(МЛП-программирование).

КЛАССИЧЕСКИЕ КОММУТАТОРЫ
Коммутатор – схема обеспечивающая соединение p входов и q выходов.
Рис. 1 – разделённый коммутатор кроссбар
Рис. 2 – неразделённый коммутатор кроссбар
Рис. 3 – разделённый коммутатор Баттерфляй (Δ - сеть)

СЛОЖНОСТЬ и ЗАДЕРЖКА КЛАССИЧЕСКИХ КОММУТАТОРОВ
ТЕОРЕМА ШЕННОНА.
Сложность (число узлов коммутации) неблокирующего коммутатора на p входов и p выходов
s ≥ p log2 p
Сложность неразделённого коммутатора на p входов-выходов
s ≥ (p/2)log2(p/2)
Задержка коммутатора τmin ≥ О(log2 p)
Сложность коммутатора кросс-бар О(p2)
Задержка коммутатора кросс-бар τ ≥ О(2p)
ВЫВОД: КЛАССИЧЕСКИЕ КОММУТАТОРЫ НЕ ОБЕСПЕЧИВАЮТ РЕЛЯТИВИСТСКИЕ ВЫЧИСЛЕНИЯ

ЛОКАЛЬНЫЕ КОММУТАТОРЫ
ЛОКАЛЬНЫЕ КОММУТАТОРЫ СОЕДИНЯЮТ ТОЛЬКО СОСЕДЕЙ И ТОЛЬКО НА ОГРАНИЧЕННОМ РАССТОЯНИИ
СЛОЖНОСТЬ ЛОКАЛЬНОГО КОММУТАТОРА ПРОПОРЦИОНАЛЬНА РАЗМЕРУ СИСТЕМЫ
sлок ≥ pсоседей log2 pсоседей = const,
S = p× sлок = p× const
ЗАДЕРЖКА ЛОКАЛЬНОГО КОММУТАТОРА
НЕ ЗАВИСИТ ОТ РАЗМЕРА СИСТЕМЫ
τ = log2 pсоседей = const,
ВЫВОД:
ТОЛЬКО ЛОКАЛЬНЫЕ КОММУТАТОРЫ ОБЕСПЕЧИВАЮТ РЕЛЯТИВИСТСКИЕ ВЫЧИСЛЕНИЯ

ЛОКАЛЬНЫЕ ОДНОРОДНЫЕ СТРУКТУРЫ
Структура вычислительной системы – граф связей между её элементами. Структура однородна, если она обладает транзитивной группой автоморфизмов, сохраняющей отметки рёбер.
Теорема Вагнера. Структура однородна тогда и только тогда, когда она есть групп-граф с точностью до направлений дуг.
Структура локальна, если она вкладывается в физическое пространство так, что сохраняется ограниченное расстояние между соседями.
Теорема Воробьёва. Однородны и локальны двумерные структуры, порождаемые квадратной решёткой и расположенные на торе, и только они.

ЛОКАЛЬНЫЕ ОДНОРОДНЫЕ СТРУКТУРЫ
Примеры локальных однородных структур и тороидальный конструктив системы
Qa
4
b
Qa
9
b
-3
Q a
b

ПРОБЛЕМА РЕЛЯТИВИСТСКОГО КОМПЬЮТЕРА
Релятивистский компьютер технически возможен поскольку:
1. Существуют локальные однородные структуры связей с линейной оценкой сложности и постоянной задержкой передачи между соседями.
2. Очевидно существование локально-параллельных протоколов взаимодействий и синхронизации событий.
Для релятивистских вычислений необходимы:
1. Локально-паралллельные вычислительные алгоритмы и
2. МЛП-программирование.

РЕЛЯТИВИСТСКАЯ
Однородная Вычислительная Система
Архитектура ОВС на Неразрезных Процессорных
Матрицах СБИС
ПК - Мониторная подсистема на основе персонального компьютера
УУ − Устройство управления решающим полем
МК − Магистральный канал (магистральная шина)
РК − Регулярный канал (КАИС ‑ структура)
КД – Канал данных
РП − Решающее поле на неразрезных процессорных матрицах НПМ СБИС
(КАИС‑ структура)

РЕШАЮЩЕЕ ПОЛЕ – НЕРАЗРЕЗНАЯ ПРОЦЕССОРНАЯ МАТРИЦА СБИС
Современная НАНОТЕХНОЛОГИЯ позволяет вплотную подойти к изготовлению неразрезных процессорных матриц (НПМ) СБИС, содержащих сотни процессорных элементов с локальной памятью и программируемой КАИС-структурой коммутатора
НПМ СБИС наилучшим образом соответствуют идеологии ОВС и потребностям дальнейшего развития компактных массово-параллельных (мозгоподобных) вычислительных устройств.

КЛАССИЧЕСКАЯ ПАРАДИГМА ОТКАЗОУСТОЙЧИВОСТИ
1. Контролируемое и диагностируемое устройство присутствует в системе в единственном экземпляре.
2. Это устройство имеет высокую цену.
3. Элементы устройства можно заменять по мере их отказов. Минимальный заменяемый блок – типовой элемент замены (ТЭЗ) можно контролировать, диагностировать и ремонтировать на специальном стенде вплоть до замены отдельных электронных компонент.
4. Связи между ТЭЗ-ами дёшевы и либо абсолютно надёжны, либо их отказы приписываются элементам. И, вообще, проверка связей - вопрос отдельный.
5. Имеются абсолютно надёжные элементы, например, смесители Дж. фон Неймана

1. Невозможность замены отказавших элементов;
2. Отказы не только процессорных элементов, но и связей между ними;
3. Однородность и близкодействие структуры связей;
4. Стремление к экономии коммутационного оборудования
Важнейшие особенности неразрезной технологии СБИС

Указанные особенности СБИС создают принципиальные сложности и фундаментальные ограничения при производстве и обеспечения отказоустойчивости НПМ СБИС.
ПРОБЛЕМА НПМ СБИС - ОТКАЗОУСТОЙЧИВОСТЬ

1. Отказавшие ПЭ следует обходить, используя резервные элементы
2. Отказавшие связи следует заменять резервными связями.
3. Однородность и локальность структуры следует сохранить.
4. Резерв ПЭ и Связей следует минимизировать
ПРОБЛЕМА НПМ СБИС - ОТКАЗОУСТОЙЧИВОСТЬ

ПРОСАЧИВАНИЕ – ФУНДАМЕНТАЛЬНЫЙ ПРЕДЕЛ ОТКАЗОУСТОЙЧИВОСТИ НПМ
Задача Хаммерсли (1963г.)
Будем удалять узлы и связи случайным образом, до тех пор пока ток не прекратится.
Каковы вероятности исправных узлов pH и связей rH в момент прекращения тока?

КРИТЕРИЙ ПРОСАЧИВАНИЯ (ПЕРКОЛЯЦИИ)
Пусть на множестве локальных однородных структур одного типа, вложенных в R2 с абсолютно надёжными связями,
p – вероятность исправности ПЭ,
pH − критическая вероятность просачивания по узлам
Утверждение 1. С ростом избыточности НПМ СБИС становится сколь угодно надёжной,
если p > pн, и сколь угодно ненадёжной,
если p < pн.

МОДЕЛЬ ПРОСАЧИВАНИЯ
(ПЕРКОЛЯЦИИ)
Шаблон соседства для решетки К

МОДЕЛЬ ПРОСАЧИВАНИЯ
(ПЕРКОЛЯЦИИ)

МОДЕЛЬ ПРОСАЧИВАНИЯ
(ПЕРКОЛЯЦИИ)
Шаблоны соседства и области просачивания для некоторых решеток

ПОРОГИ ПРОСАЧИВАНИЯ

ДИНАМИЧЕСКАЯ МОДЕЛЬ
ОТКАЗОУСТОЙЧИВОСТИ НПМ
Пусть время безотказного функционирования ЭМ распределено по экспоненциальному закону с параметром α при условии p ≥ pH Среднее время наработки на отказ для ЭМ равно τ = α -1. Величина α − интенсивность отказов ЭМ, τ − время жизни. Отказавшая ЭМ обнаруживается и восстанавливается с интенсивностью β за среднее время восстановления β -1.
dp(t)= [β(1− p(t)) − α p(t)] dt - уравнение процесса гибели − восстановления в бесконечном ансамбле ЭМ.
Начальные условия:
p0 = p(0)
p0 = 1 если бракованные ЭМ можно заменить
Решение уравнения при указанных начальных условиях имеет вид
p = p∞ + [p0 − p∞] e− t(α + β ),
где − финальная вероятность исправного состояния ЭМ.

ОТКАЗОУСТОЙЧИВОСТЬ НПМ
БЕЗ ВОССТАНОВЛЕНИЯ
Утверждение 2. Время существования бесконечного исправного кластера в локальной однородной структуре без восстановления равно
t = τ ln(p0 / pH) ≤ τ ln(p-1)
где τ = α - 1 − время жизни одного элемента.
Избыточность не увеличивает времени
жизни локальной однородной структуры.

РЕКОНФИГУРАЦИЯ НПМ по
САМИ и СТЕФАНЕЛЛИ
Сами и Стефанелли предложили несколько алгоритмов реконфигурации НПМ для обхода неисправных узлов решётки в следующих предположениях:
1. Края НПМ (строка или столбец) резервируются.
2. Связи абсолютно надёжны.
3. Неисправные узлы обнаруживаются при тестировании извне.
4. Каждый ПЭ имеет коммутационное окружение, вычисляющее реконфигурацию структуры связей по сигналам неисправностей ПЭ.

НПМ с ОГРАНИЧЕННЫМ ВОССТАНОВЛЕНИЕМ
Пусть N − число ЭМ; m − число восстанавливающих органов, работающих параллельно; α и β − интенсивности потока отказов и восстановлений.
При m > N(1− p) система ведёт себя как самовосстанавливающаяся.
При m < N(1− p) имеет место ограниченное восстановление.
Условие равенства потоков отказов и восстановлений :
N α p = m β
При полной загрузке ограниченной восстанавливающей системы
математическое ожидание числа исправных элементов равно mβα-1.
Потребуем, чтобы это число превышало N0 и, кроме того, выполнялось
p > pH .
Утверждение 3. НПМ с ограниченным восстановлением работоспособна если выполняется условие
N0 < m β α-1 ≤ N ≤ m β (α pH)-1
При N > mβ(αpH)-1, стационарное состояние НПМ есть состояние отказа.

КОММУТАЦИОННОЕ ОКРУЖЕНИЕ ПЭ по САМИ И СТЕФАНЕЛЛИ

РЕЗЕРВНЫЕ СВЯЗИ ПЭ
по Сами и Стефанелли

РЕКОНФИГУРАЦИЯ НПМ по
В.А.Воробьёву – Н.В.Лаходыновой
В.А. Воробьёв и Н.В. Лаходынова модифицировали те же алгоритмы реконфигурации НПМ для обхода неисправных узлов решётки в иных предположениях:
1. Резервируются любые строки и столбцы в любых количествах.
2. Связи абсолютно надёжны.
3. Неисправные узлы самодиагностируются тестовой программой или аппаратно.
4. Каждый ПЭ имеет коммутационное окружение и программу вычисляющую реконфигурацию структуры связей по сигналам неисправностей от ПЭ.

КОММУТАЦИОННОЕ ОКРУЖЕНИЕ по В.А.Воробьёву– Н.В.Лаходыновой

РЕКОНФИГУРАЦИЯ НПМ по В.А. Воробьёву – Н.В. Лаходыновой

ВИЗАНТИЙСКАЯ ПАРАДИГМА ОТКАЗОУСТОЙЧИВОСТИ НПМ
1. Элементом замены является элементарная машина (ЭМ) − устройство, которое обычно само по себе снабжается средствами самодиагностики. Для неразрезной пластины СБИС − замена вообще невозможна, поэтому выбор минимального диагностируемого элемента является предметом особого рассмотрения.
2. Структура системы однородна и локальна - связаны только соседи.
3. В силу одинаковости ЭМ каждый элемент окрестности ЭМ является для неё эталоном и таких эталонов достаточно много (8 ÷16 и более).
4. Наличие большого числа эталонных модулей позволяет упростить ЭМ за счёт удаления средств индивидуальной самодиагностики, но в то же время требует системной самодиагностики. Основная идея состоит в том, что достаточно сложные модули могут диагностировать друг друга.
5. Алгоритм самодиагностики пытается восстановить образ неисправности, то есть выделить неисправные модули. Эта задача известна как проблема византийских генералов, пытающихся путём взаимопроверок и обменов результатами найти генералов-предателей, подсчитать число верных генералов и всех их включить в систему.
6. Для византийского согласия характерны все исходные предположения о диагностируемой системе, кроме единственности устройства.

КОНСЕНСУС-ПАРАДИГМА ОТКАЗОУСТОЙЧИВОСТИ НПМ
1. ПЭ много и они связаны однородной, локальной сетью связи.
2. Число связей у каждого ПЭ ограничено.
3. Связи можно программно включать, выключать и коммутировать.
4. Отдельные ПЭ и связи дёшевы относительно цены исправной НПМ.
5. Абсолютно надёжных ПЭ и связей нет.
6. Заменить отказавшие ПЭ и связи невозможно.
7. Византийское согласие всех исправных ПЭ ненужно и нереально.
8. Аппаратура самодиагностики не нужна. Соседние ПЭ могут служить эталонами друг для друга, их число достаточно, чтобы изолировать неисправный ПЭ надёжнее чем самодиагностика.
9. Резервные ПЭ и связи не выделяются.
10.Отказоустойчивость достигается за счёт программирования структуры и избыточного числа ПЭ и связей между ними. Задача состоит в том, чтобы вложить требуемый граф в избыточный граф с отказами элементов и связей.

ВОЛНОВОЙ АЛГОРИТМ ПОИСКА КОНСЕНСУСА
Каждый ПЭ тестируется и результаты тестирования сравниваются с результатами тестирования соседей. По результатам тестирования в каждом ПЭ создается список соседей, с которыми ПЭ согласен. Дуга отмечается флагом несогласия, если хотя бы один инцидентный ей ПЭ “не согласен” с соседом.
Прямой ход. Начиная с верхнего левого угла матрицы ПЭ передают свои логические номера согласным соседям. Для того, чтобы логический номер (i,j) стал возможен необходимо найти среди предшественников некоторое множество уже вычисленных номеров.
Для квадратной решётки это пара {(i1, j1),(i2, j2)}, удовлетворяющая условиям
(1) [⏐ i1 − i2⏐ = 1] ∧ [⏐ j1 − j2⏐ = 1]
(2) [(i1 < i2) → (j1 > j2)] ∨ [(i1 > i2 ) → (j1 < j2)]
Для треугольной решётки это тройка {(i0, j0),(i1, j1),(i2, j2)}, удовлетворяющая ещё одному условию:
(3) (i0, j0) = (min (i1,i2 ), min (j1,j2))
Для решётки К* это уже четвёрка {(i0, j0), (i1, j1), (i2 , j2), (i4, j4)}, удовлетворяющая ещё одному дополнительному условию:
(4) (i4, j4) = (max (i1, i2) +1, min (j1, j2))
Наконец, для решётки Ш необходимая конфигурация передающих, согласных соседей есть “прореженная” конфигурация квадратной решётки. Например, если чётности строк и столбцов совпадают, требуются условия (1) и (2), если не совпадают, достаточно одного передающего и согласного соседа слева.
Логический номер (i,j) во всех случаях вычисляется по формуле
( i, j ) = ( max (i1, i2), max (j1, j2) )
Обратный ход подобен прямому ходу, только передача информации идёт в обратном направлении, а логический номер (i", j") вычисляется по правилу
(i", j") = (min(i, i'), min(j, j')).
Вычисленный номер (i", j") считается допустимым в ПЭ, если ранее он уже был получен в процессе прямого хода.
Таким образом, после обратного хода в списках допустимых номеров ПЭ остаётся только пересечение множеств номеров прямого и обратного хода. Остальные номера не имеют отношения к искомой решётке и уничтожаются. ПЭ с фиксированными логическими номерами отмечается как включённый в решётку

СРАВНЕНИЕ АЛГОРИТМОВ
ОТКАЗОУСТОЙЧИВОСТИ
Вероятность P(n,p) сохранения работоспособности НПМ 20×20.
А - волновой алгоритм
В - алгоритм свободного захвата с программируемым резервом.

СИНДРОМ НЕСОГЛАСИЯ в НПМ размера 8×8 (фрагмент)

КОНСЕНСУС В НПМ размера 8×8 (фрагмент)

1. Выполняется на локальных однородных структурах
2. Параллелизм максимален
3. Объём данных и вычислений в ЭМ минимален (1 виток цикла)
4. Взаимодействуют только соседи
5. Глобальные взаимодействия единичны: типа пуск и останов.
МЛП-ВЫЧИСЛЕНИЕ

суммирует параллельно N строк за время Nt с ускорением (N−1) и эффективностью
(N −1)/N →1 при N → ∞.
Каждая ЭМ содержит в локальной памяти один столбец длинны N и на индекс-регистре адреса − номер строки, сумму которой она накапливает на текущем этапе.
Символ sijk обозначает сумму от i-го до j­-го элементов k-той строки, перечисляемых циклически слева направо.
МЛП-РЕДУКЦИЯ СТРОК МАТРИЦЫ

МЛП-УМНОЖЕНИЕ МАТРИЦ
Одним из примеров мелкозернистого распараллеливания может служить умножение матриц размера n2 при использовании n2 процессоров. Все три матрицы можно поэлементно распределить по клеткам, так что в каждой клетке Кij в начальный момент располагаются три элемента
аik , bkj и cij = 0.
Тогда, при соответствующих сдвигах строк и столбцов, в каждом процессе можно выполнять операцию накопления
cij = aik ×bkj + cij
Для выполнения такого параллельного алгоритма требуется всего по O(n) этапа сдвига, умножения и сложения.

МЛП-УМНОЖЕНИЕ МАТРИЦ

ОЦЕНКА
МЛП-умножения матриц
Сложность параллельного алгоритма O(n).
Процесс вычислений состоит из 3-х команд:
1. пересылка исходных данных aik и bkj на каждый процессор;
2. вычисление произведения блоков;
3. суммирование и запоминание результата cij.
Всего потребуется n таких действий. Тогда имеем:
t1(n) = n3 Tmult – время умножения матриц размерности n×n
tp(n) = n Tmult – время умножения матриц в p = n2 ЭМ
Sp(n) = t1(n)/ tp(n) = n3 Tmult/(n Tmult) = n2
Итак, ускорение МЛП- алгоритма по сравнению
с наилучшим последовательным алгоритмом равно n2.