- •Оглавление
- •Глава 1. Архитектура вычислительных систем 11
- •Глава 2. Реализация параллельных алгоритмов 63
- •Глава 3. Надежность и живучесть вычислительных систем 96
- •Глава 4. Библиотека параллельных программ 120
- •Глава 5. Граф-схемы параллельных алгоритмов 150
- •Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений 182
- •Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений 204
- •1.Количественные характеристики, применяемые для оценок параметров вычислительных систем
- •Глава 1. Архитектура вычислительных систем
- •Для случая неоднородной системы номинальное быстродействие выразится как
- •Здесь – вероятность выбора j-й операции, , . Для однородной вс её быстродействие по Гибсону выразится соотношением
- •Для неоднородной вс это быстродействие может быть определено, как
- •1.1.1. Вопросы к разделу 1.1.
- •2.Понятие о современных вычислительных системах
- •Пример графа регулярной вычислительной системы представлен на рисунке 1.2.1.
- •Примечание: Для регулярной вычислительной системы
- •2.1. Вопросы к разделу 1.2.
- •3.Структура современных вычислительных систем
- •3.1.Схема обмена с помощью структуры «Общая шина»
- •3.2.Схема обмена с помощью структуры «Линейка»
- •3.3.Вычислительная система, имеющая структуру типа «Кольцо»
- •3.4.Схема обмена с помощью структуры типа «Решётка»
- •1.3.5. Схема обмена с помощью структуры типа «Двумерный тор»
- •3.1.Схема обмена с помощью структуры типа «n-мерный двоичный гиперкуб» или «nD-куб»
- •3.2.Реализация обмена с помощью структуры типа «Обобщенный nD-куб»
- •3.3.Структура вс типа «n-мерный обобщённый тор»
- •3.4.Структура вс с сетью типа «Циркулянт»
- •1.3.10. Вычислительная система «Максимальный обхват»
- •1.3.11. Вычислительные системы со структурой сетей типа «Симметричные графы»
- •На рисунке 1.3.11. Представлена вс с симметричным графом.
- •1.3.12. Вычислительные системы с сетью связей типа «Гомоморфные графы»
- •1.3.13. Вычислительные системы с сетью связей типа «Граф л(n,V,g)»
- •1.3.14. Структура вычислительной системы типа «Бинарное дерево t0(n) глубины n»
- •1.3.15. Структура вычислительной системы типа «Мультидерево глубины n и ширины k t1(n,k)»
- •3.5. Вопросы к разделу 1.3
- •4.Коммуникационные среды вычислительных систем
- •Коммуникационная среда должна удовлетворять следующим требованиям:
- •4.1.Коммуникационная среда на основе масштабируемого когерентного интерфейса sci
- •4.2.Коммуникационная среда на основе технологии Myrinet
- •1.4.3. Краткая характеристика коммуникационной среды QsNet II
- •4.3. Вопросы к разделу 1.4
- •5.Коммутаторы вычислительных систем
- •1.5.1. Типы коммутаторов
- •5.1. Управление коммутаторами
- •5.2. Алгоритмы определения маршрутов
- •5.3. Дедлоки в составных коммутаторах
- •5.4.Вопросы к разделу 1.5
- •6.Процесс функционирования вычислительных систем
- •6.1. Вопросы к разделу 1.6.
- •7.Принципы технической реализации вс
- •1.7.1. Вопросы к разделу 1.7
- •1.8. Архитектурные особенности вс
- •1.8.1. Архитектурные свойства вс
- •1.8.2. Схема обмена информацией между ветвями параллельных алгоритмов
- •7.1.Опыт применения методики крупноблочного распараллеливания сложных задач
- •7.2.Архитектурные аспекты при создании ос вс
- •7.3.Структурные характеристики вс
- •7.4.Классификация структур вс
- •7.5.Вопросы к разделу 1.8.
- •Глава 2. Реализация параллельных алгоритмов
- •2.1. Реализация параллельных алгоритмов
- •2.1.1. Определение параллельного алгоритма
- •7.6.Организация динамического распараллеливания в суперскалярных микропроцессорах
- •2.1.3. Предварительная выборка команд и предсказание переходов
- •7.7.Декодирование команд, переименование ресурсов и диспетчеризация
- •7.8.Исполнение команд
- •2.1.6. Работа с памятью
- •2.1.7. Завершение выполнение команды
- •2.1.8. Направления развития суперскалярной архитектуры
- •7.9.Мультитредовая модель выполнения программы
- •7.10.Аппаратные и программные средства, необходимые для мультитредовой архитектуры
- •2.1.11. Специфика мультитредовых моделей распараллеливания
- •2.1.12. Вопросы к разделу 2.1
- •2.2.Организация распараллеливания на уровне программных модулей
- •2.2.1. Примеры организации вычислений на уровне программных модулей
- •2.2.2. Решение системы линейных уравнений методом Гаусса с помощью вс типов «решётка» и «линейка»
- •2.2.3. Исполнение алгоритма Гаусса на «решётке» n*n вm
- •2.2.4. Исполнение алгоритма Гаусса на «линейке», состоящей из n вм
- •2.2.5. Показатели эффективности параллельных алгоритмов
- •2.2.6. Понятие о сложных задачах
- •2.2.7. Вопросы к разделу 2.2
- •Глава 3. Надежность и живучесть вычислительных систем
- •8.Основные задачи создания отказоустойчивых систем
- •8.1.Вопросы к разделу 3.1
- •9.Классификация типов отказоустойчивости сложных систем и ее критерии
- •9.1.Вопросы к разделу 3.2
- •10.Способы обеспечения отказоустойчивого функционирования вс
- •3.3.1. Диагностическое тестирование вс
- •3.3.3. Способы восстановления отказоустойчивых вс
- •10.1.Вопросы к разделу 3.3
- •3.4. Построение живучих вс на основе экспоненциально- надежностного подхода
- •3.4.1. Показатели надежности вс
- •10.2. Методика расчета показателей надежности вс
- •3.4.3. Живучесть вс
- •3.4.4. Вопросы к разделу 3.4
- •11.Построение живучих вс, работоспособных в расчетном диапазоне кратностей отказов
- •3.6.1. Горячий резерв
- •3.6.2. Репликация
- •3.6.3. Кластеры высокой готовности
- •3.5.1. Вопросы к разделу 3.5
- •3.6. Реализация модели отказоустойчивых систем
- •4.1.2. Принципиальная схема программирования в OpenMp
- •11.2. Описание основных конструкций open mp
- •4.1.4. Способы построения параллельных программ
- •4.1.6. Вопросы к разделу 4.1
- •4.2. Основы построения библиотеки mpi
- •4.2.1. Основные понятия
- •4.2.2. Структура программ в mpi
- •4.2.3. Определение структуры приходящего сообщения
- •4.2.4. Определение базовых характеристик коммуникационной сети
- •11.4.Анализ тупиковых ситуаций при обмене
- •4.2.6. Организация передачи-приёма сообщений без блокировки
- •4.2.7. Реализация отложенных запросов на взаимодействие
- •4.2.8. Сравнительная оценка различных способов обмена данными
- •4.2.9. Использование глобальных операций в mpi
- •4.2.10. Взаимодействие процессов в mpi
- •4.2.11. Вопросы к раделу 4.2
- •Глава 5. Граф-схемы параллельных алгоритмов
- •5.1. Представление параллельных алгоритмов в виде граф-схем
- •5.1.1. Преобразование последовательных алгоритмов в параллельные
- •5.1.2.Использование граф-схем для представления параллельных алгоритмов
- •5.1.3. Вопросы к разделу 5.1
- •5.2.1. Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями
- •5.2.2. Вопросы к разделу 5.2
- •11.5.Построение матрицы логической несовместимости.
- •5.3.2. Построение матрицы логической несовместимости операторов
- •5.3.3. Вопросы к разделу 5.3
- •5.4.1. Построение множеств взаимно независимых операторов.
- •5.4.2. Вопросы к разделу 5.4
- •Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений
- •6.1. Численные характеристики информационных граф-схем со скалярными весами
- •6.1.1 Определение ранних и поздних сроков окончания выполнения операторов.
- •11.6.Определение функций плотности загрузки, и минимальной загрузки для информационных граф-схем
- •6.1.3. Вопросы к разделу 6.1
- •6.2.1. Распределение операторов по вм вычислительной системы с общим полем памяти для информационной граф-схемы
- •6.2.2. Распределение операторов по вм вычислительной системы с общим полем памяти для информационно-логической граф-схемы
- •При срабатывании условного оператора «один», дуги 1.1 требуется 10 вм. Время решения задачи составит 22 условные единицы.
- •6.2.3. Распределение операторов по вм вычислительной системы с распределённой памятью для информационной граф-схемы
- •6.2.4. Реализация диаграмм для общепринятых способов обмена данными между вм вычислительной системы с распределённой памятью для информационной граф-схемы
- •6.2.5. Вопросы к разделу 6.2
- •Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений
- •7.1 Информационная граф-схема решаемых задач с векторными весами вершин
- •7.1.1 Понятие об неоднородных системах
- •7.1.2. Основные определения, используемые для неоднородных вс
- •7.1.3. Вопросы к разделу 7.1
- •Литература
3.4.3. Живучесть вс
Живучесть является более ёмким понятием, чем надёжность ВС. Живучесть определяет способность вычислительной системы (достигаемая программной организацией структуры и функционального воздействия между её компонентами) в любой момент функционирования использовать суммарную производительность всех исправных ресурсов для решения задач.
Живучесть ВС должна достигаться при решении задач, представленных программами с любым допустимым числом параллельных ветвей или, что то же самое, с любым рангом r, 1 ≤ r ≤ N, где N – общее число BМ в системе. Исключением не должны быть задачи с переменным рангом. Живучесть должна обеспечиваться и в монопрограммном, и в мультипрограммных режимах работы ВС. При монопрограммном режиме для определённости будем полагать, что переменный ранг задачи ограничен снизу n и сверху N. Величина n одновременно является и нижней границей числа работоспособных BМ (считается, что при числе отказавших BМ, равном N-n+1, имеет место полный отказ ВС). При мультипрограммировании сумма рангов одновременно решаемых задач не превышает N.
Живучесть ВС рассматривается в двух аспектах: потенциальном и структурном. При анализе потенциальной живучести ВС особенности структуры или сети межмашинных связей в прямом виде не учитываются, и считается, что в системе обеспечиваются возможности по достижению необходимой связности исправных ВМ. При изучении структурной живучести ВС, учитываются топологический вид сети межмашинных связей и надёжностные характеристики компонентов этой сети.
Программы, при реализации которых автоматически устанавливается число параллельных ветвей, равное числу работоспособных машин в текущий момент времени, относятся к адаптирующимся. Теоретически и экспериментально установлено, что для достаточно широкого круга задач могут быть составлены эффективные параллельные программы, обладающие способностью адаптации к составу работоспособных вычислительных ресурсов.
Под живучей вычислительной системой понимается (виртуальная) конфигурация из N элементарных машин, в которой:
1) указано минимально допустимое число n работоспособных ВМ, обеспечивающее производительность системы не менее требуемой;
2) реализована возможность решения сложных задач, представленных адаптирующимися параллельными программами;
3) отказы любых ВМ (вплоть до числа N-n) и восстановления отказавших машин приводят только к увеличению или уменьшению времени реализации параллельной программы;
4) при изменении состояния k = 0, 1, …, N производительность подчиняется следующему закону:
где An – коэффициент;
где – Ω(k) производительность (точнее, один из показателей производительности) элементарной машины; – неубывающая функция от n и (как правило, ).
Следует обратить внимание на то, что в
живучей ВС вычислительное ядро составляют
все
исправных ВМ и что число избыточных ВМ
в ней переменное и заключено между 0
и N-n.
В живучей системе нет резервирования,
нет простоев исправных машин. Все
исправные BМ такой ВС включаются в
вычислительное ядро и участвуют в
реализации параллельных процессов, что
приводит к сокращению времени решения
задач.
Итак, в живучих ВС отказы вычислительных модулей не приводят к отказу систем в целом. Более того, в таких ВС при выходе машин из строя сохраняется возможность продолжения счёта на всех исправных ВМ (при наличии отказавших вплоть до N-n). Реализация такого виртуального механизма переменной избыточности машин уменьшает время решения сложной задачи на вычислительной системе.
Показатели живучести ВС должны учитывать то обстоятельство, что при решении задач используются все исправные ВМ, число которых не есть постоянная величина. Говоря иначе, при определении показателей живучести следует учесть то, что параллельные программы сложных задач при их реализации на живучих ВС способны задействовать суммарную производительность всех работоспособных BМ системы.
Качество функционирования живучих ВС
будем характеризовать функциями
потенциальной живучести ВС
и занятости восстанавливающей системы
M(i,
t) вектор-функциями
R(t), U(t) и S(t) ВС.
Функции N(i, t) и M(i, t) характеризуют среднюю производительность ВС и среднюю загруженность восстанавливающей системы, если ВС начала функционировать с i работоспособными ВМ. Можно дополнить эту системы функций обобщенными функциями надежности, восстановимости и готовности ВС.
Функцией потенциальной живучести ВС назовём отношение
,
где N(i, t) – среднее число
работоспособных ВМ в момент
при условии, что в момент начала
функционирования в системе было i
работоспособных ВМ, N – общее число
ВМ системы.
Функцией занятости восстанавливающей системы назовём
где M(i,t) – математическое ожидание числа занятых восстанавливающих устройств в момент времени t 0 при условии, что в момент начала функционирования в системе было i работоспособных ВМ, m – число устройств в восстанавливающей системе.
Функция потенциальной живучести ВС информирует о том:
1) как быстро система, начавшая функционировать в одном из возможных состояний, войдёт в стационарный режим работы;
2) какую производительность в среднем может обеспечить система в любой момент времени или при длительной эксплуатации, говоря иначе, на сколько машин в среднем можно рассчитывать в момент поступления задачи;
3) сколько машин в среднем может быть использовано при решении задачи (сколько в среднем ветвей будет иметь место при реализации адаптирующейся параллельной программы).
Функция занятости восстанавливающей системы даёт следующую информацию:
1) за какое время после начала работы ВС наступит установившийся режим восстановления отказавших машин;
2) как загружены в среднем восстанавливающие устройства на начальном участке работы ВС и после длительной её эксплуатации или насколько эффективен выбранный состав восстанавливающих устройств.
При численном экспериментировании введенные функции потенциальной живучести ВС и занятости восстанавливающей системы позволяют подобрать оптимальные параметры единого комплекса «вычислительная система – восстанавливающая система».
Расчёт функций потенциальной живучести ВС – N(i, t) и занятости восстанавливающей системы M(i, t) сводится к вычислению математических ожиданий соответственно числа N(i, t) исправных ВМ и числа M(i, t), занятых ВУ в момент времени t 0. При этом должно быть выполнено условие, что в начальный момент t = 0 было i работоспособных машин.
Можно показать, что будет справедливо следующее уравнение:
'
при чем
Рассмотрим два случая в зависимости от производительности восстанавливающей системы:
1) Восстанавливающая система имеет
высокую производительность, то есть
для любого t
0
выполняется условие: N-N(i,t)
m.
Опустим математические выкладки и запишем результат:
,
.
Таким образом можно записать выражения для коэффициентов потенциальной живучести и занятости восставливающей системы:
;
.
2) Восстанавливающая система имеет
невысокую производительность, то есть
для любого t
0
выполняется условие:
.
Очевидно, что коэффициент занятости восстанавливающей системы тождественно равен единице: M = M(i,t) =5.
Запишем выражение для среднего числа работоспособных ВМ:
.
Соответственно, коэффициент потенциальной живучести будет равен:
.
