- •Оглавление
- •Глава 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
- •Литература
8.1.Вопросы к разделу 3.1
1.Что понимается под отказом системы?
2. Дать определение отказоустойчивых систем.
3. Как влияет улучшение надежностных характеристик отдельных компонентов ВС?
4. Какие существуют эффективные методы устранения отказов в ВС?
5. Причины появления отказов в системе.
9.Классификация типов отказоустойчивости сложных систем и ее критерии
Сложные технические системы в процессе эксплуатации подвергаются детерминированным и стохастическим внешним воздействиям, приводящим к различного вида повреждениям элементов и связей: износу, поломке, засорению, выгоранию, обрыву и т.п. Накапливаясь, повреждения приводят к отказу - нарушению работоспособности объекта, которое определяется перечнем заданных параметров и допустимыми пределами их изменения. Нарушение работоспособности может произойти при выходе значения хотя бы одного параметра за пределы, установленные требованиями нормативно-технической документации. Признаки, позволяющие установить факт такого нарушения, являются критериями отказа. Для сложных технических систем этот критерий отказоустойчивости не всегда показателен, поскольку нарушение работоспособности отдельного элемента может не сказаться на работоспособности всей системы в целом. В сложных системах возможно большое количество мест повреждений. Вероятность ее безотказной работы может быть оценена статистически в результате проведения серии экспериментов (рисунок 3.2.1), связывающих отказоустойчивость с количеством возникших повреждений, при этом:
р – статистическая оценка вероятности отказа системы;
n – количество отказавших элементов и/или связей между ними;
n1 – максимальное количество отказавших элементов и/или связей, при которых вероятность отказа равна нулю;
n2 – минимальное количество отказавших элементов и/или связей, при которых вероятность отказа равна единице.
Полученное семейство экспериментальных точек условно разбито на три зоны:
зона I: 0 < n < n1; p = 0 – повреждений не больше, чем n1; система абсолютно работоспособна;
зона II: n1 < n < n2; 0 < p < 1 – повреждений больше, чем n1, но меньше, чем n2; система сохраняет работоспособность лишь при некотором наборе этих повреждений;
зона III: n2 < n; p = 1 – повреждений больше, чем n2 - 1; система неработоспособна при любом их наборе.
Рисунок 3.2.1 Результаты экспериментальной статистической оценки вероятности отказа сложной технической системы
Очевидно, что отказоустойчивость системы зависит от значений n1 и n2 и тем выше, чем дольше сохраняется нулевая вероятность отказа (т.е., чем больше n1), и чем больше наклонена к оси абсцисс прямая, аппроксимирующая экспериментальные точки в зоне II, (т.е. чем больше (n2 - n1)).
В зависимости от наличия и протяженности вдоль оси n этих зон, можно классифицировать четыре типа отказоустойчивости системы (см. таблицу 3.2.1).
Таблица 3.2.1
-
№ п/п
Тип
отказоустойчивости
Графическая аппроксимация
Значения границ зон
Характеристика
5.
Абсолютно неустойчива
n1 = 0; n2 = 1
Первое же любое повреждение приводит к отказу
2.
Негарантированная отказоустойчивость
n1 = 0; n2 > 1
Отказоустойчивость пропорциональна р при n >0
3.
Гарантированная отказоустойчивость I
n1 > 0; n2 - n1 = 1
Система отказоустойчива до n< n1.
При n > n1 первое же любое повреждение приводит к отказу
4.
Гарантированная отказоустойчивость II
n1 > 0;
n2 - n1 > 1
Система отказоустойчива до n< n1.
Приведенные типы отказоустойчивости представляют собой условную аппроксимацию экспериментальных точек прямыми.
Первый тип по своим показателям соответствует абсолютно неустойчивой и в этом смысле ненадежной системе, первое же любое повреждение любого элемента (или связи) приводит к отказу. Естественно, такая система не нуждается в критериях оценки отказоустойчивости.
Второй тип соответствует системе с негарантированной отказоустойчивостью, т.к. первое же любое повреждение может привести к отказу.
Третий тип отказоустойчивости также является ненадежным с точки зрения эксплуатационных характеристик системы, поскольку после некоторого количества повреждений вероятность отказа скачком превращается из 0 в 1.
Четвертый тип сочетает в себе свойства второго и третьего.
По способу реализации отказоустойчивость подразделяется на активную и пассивную.
Активная отказоустойчивость базируется на отдельно выделенных процессах обнаружения отказа, локализации отказа и реконфигурации системы. Отказы обнаруживаются средствами контроля, локализуются при помощи средств диагностики и устраняются автоматической реконфигурацией системы. Последняя заключается в перестройке структуры системы таким образом, чтобы ее отказавшие компоненты были устранены от участия в работе.
Пассивная отказоустойчивость заключается в способности системы не потерять свои функциональные свойства в случае отказа отдельных элементов. В таких случаях говорят, что отказ маскируется системой. Пассивная отказоустойчивость связана с увеличением количества аппаратуры в несколько раз; она применяется обычно тогда, когда недопустимы даже кратковременные перерывы в работе ВС, а также для обеспечения отказоустойчивости важнейших блоков или устройств системы.
Применение активной отказоустойчивости характеризуется более экономным расходом аппаратных средств, однако связано с некоторыми потерями времени при восстановлении работы системы после отказа (иногда возможны потери некоторой части данных). Активная отказоустойчивость реализуема только в многопроцессорных системах. В то же время применение пассивной отказоустойчивости гарантирует практически бесперебойную работу ВС и сохранение всей информации. Эти обстоятельства определяют области применения активной и пассивной отказоустойчивости.
Введение отказоустойчивости является одним из способов повышения надежности ВС. Вопрос о построении и применении отказоустойчивых систем возникает тогда, когда другие пути повышения надежности не обеспечивают требуемого ее уровня по техническим или экономическим причинам.
Отказоустойчивость системы обеспечивается введением избыточности, т.е. созданием определенных запасов или резервов. В отказоустойчивых ВС может быть использована избыточность параметрическая, временная, алгоритмическая и структурная.
Параметрическая избыточность выражается в облегчении режимов работы элементов и узлов аппаратуры с целью повышения их надежности. Однако, для правильно спроектированной системы эксплуатационные и другие параметры выбраны близкими к оптимальным, поэтому существенного увеличения надежности за счет параметрической избыточности, достигнуто быть не может.
Временная избыточность заключается в наличии дополнительного времени для решения задачи, с тем, чтобы в случае возникновения сбоев можно было исправлять их путем повторной обработки данных. Временная избыточность создает предпосылки для реализации ресурсов по повышению отказоустойчивости, имеющихся в данной системе (реконфигурация, повторение вычислений), поскольку для этого требуется дополнительное время.
Алгоритмическая избыточность заключается в применении таких алгоритмов, которые обеспечивают удовлетворительные результаты в случае наличия или возникновения ошибок в процессе обработки информации. Алгоритмическая избыточность предполагает наличие временной избыточности и является средством ее реализации. Например, свойствами избыточных алгоритмов обладают итерационные алгоритмы, обеспечивающие сходимость при больших случайных отклонениях промежуточных результатов.
Структурная избыточность является наиболее эффективным видом избыточности. Она выражается в наличии дополнительных элементов, узлов, устройств в структуре системы, предназначенных для автоматической замены отказавших компонентов.
Структура пассивно отказоустойчивых систем основана либо на мажоритарном принципе, либо на резервировании с контролем. Количество резервной и дополнительной аппаратуры в таких системах превышает количество основной аппаратуры.
Структура активно отказоустойчивых систем может быть различной. Активная отказоустойчивость может быть применена в многопроцессорных системах c общей памятью, общей шиной, кольцевой, иерархической или другой структурой.
