'

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

Понравилась презентация – покажи это...





Слайд 0

НАНОТЕХНОЛОГИЯ НА ПУТИ К РЕЛЯТИВИСТСКИМ КОМПЬЮТЕРАМ Проф. Воробьёв Владимир Анатольевич Архангельск, ПГУ им. М.В. Ломоносова, Математический факультет vva100@atnet.ru


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

СИЛА ПАРАЛЛЕЛИЗМА Пусть происходит умножение матриц 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?), мы должны обеспечить одну из следующих альтернатив.


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА Пусть 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.


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА как следствие светового барьера В общем случае для 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 – время доставки данных, т.е. задержка, необходимая для перемещения и размещения данных в местах продолжения вычислений.


Слайд 33

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


Слайд 34

ВЫРОЖДЕНИЕ ПАРАЛЛЕЛИЗМА как следствие светового барьера Реалистично полагать для одномерных систем: 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 ? ? В ОБЩЕМ СЛУЧАЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ МЕДЛЕННЕЕ ПОСЛЕДОВАТЕЛЬНЫХ!?


Слайд 35

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


Слайд 36

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


Слайд 37

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


Слайд 38

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


Слайд 39

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


Слайд 40

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


Слайд 41

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


Слайд 42

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


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 48

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


Слайд 49

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


Слайд 50

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


Слайд 51

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


Слайд 52

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


Слайд 53

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


Слайд 54

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


Слайд 55

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


Слайд 56

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


Слайд 57

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


Слайд 58

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


Слайд 59

НПМ с ОГРАНИЧЕННЫМ ВОССТАНОВЛЕНИЕМ Пусть 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, стационарное состояние НПМ есть состояние отказа.


Слайд 60

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


Слайд 61

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


Слайд 62

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


Слайд 63

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


Слайд 64

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


Слайд 65

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


Слайд 66

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


Слайд 67

ВОЛНОВОЙ АЛГОРИТМ ПОИСКА КОНСЕНСУСА Каждый ПЭ тестируется и результаты тестирования сравниваются с результатами тестирования соседей. По результатам тестирования в каждом ПЭ создается список соседей, с которыми ПЭ согласен. Дуга отмечается флагом несогласия, если хотя бы один инцидентный ей ПЭ “не согласен” с соседом. Прямой ход. Начиная с верхнего левого угла матрицы ПЭ передают свои логические номера согласным соседям. Для того, чтобы логический номер (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") считается допустимым в ПЭ, если ранее он уже был получен в процессе прямого хода. Таким образом, после обратного хода в списках допустимых номеров ПЭ остаётся только пересечение множеств номеров прямого и обратного хода. Остальные номера не имеют отношения к искомой решётке и уничтожаются. ПЭ с фиксированными логическими номерами отмечается как включённый в решётку


Слайд 68

СРАВНЕНИЕ АЛГОРИТМОВ ОТКАЗОУСТОЙЧИВОСТИ


Слайд 69

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


Слайд 70

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


Слайд 71

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


Слайд 72

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


Слайд 73

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


Слайд 74

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


Слайд 75

ОЦЕНКА МЛП-умножения матриц Сложность параллельного алгоритма 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.


Слайд 76

Благодарю за внимание РЕЛЯТИВИСТСКИЙ КОМПЬЮТЕР ВОЗМОЖЕН, МЛП-АЛГОРИТМЫ СУЩЕСТВУЮТ для всех важнейших задач математической физики, линейной алгебры и дискретной математики. ДЕРЗАЙТЕ!


×

HTML:





Ссылка: