- •Оглавление
- •Глава 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. Надежность и живучесть вычислительных систем 96
8. Основные задачи создания отказоустойчивых систем 96
8.1. Вопросы к разделу 3.1 96
9. Классификация типов отказоустойчивости сложных систем и ее критерии 97
9.1. Вопросы к разделу 3.2 99
10. Способы обеспечения отказоустойчивого функционирования ВС 100
3.3.1. Диагностическое тестирование ВС 101
3.3.3. Способы восстановления отказоустойчивых ВС 103
10.1. Вопросы к разделу 3.3 104
3.4. Построение живучих ВС на основе экспоненциально- надежностного подхода 105
3.4.1. Показатели надежности ВС 107
10.2. Методика расчета показателей надежности ВС 107
3.4.3. Живучесть ВС 109
3.4.4. Вопросы к разделу 3.4 111
11. Построение живучих ВС, работоспособных в расчетном диапазоне кратностей отказов 112
3.5.1. Вопросы к разделу 3.5 116
3.6. Реализация модели отказоустойчивых систем 116
3.6.1. Горячий резерв 116
3.6.2. Репликация 117
3.6.3. Кластеры высокой готовности 117
3.6.4. Вопросы к разделу 3.6 119
Глава 4. Библиотека параллельных программ 120
4.1 Характеристика параллельных языков программирования 120
11.1. Характеристика спецификаций OpenMP 120
4.1.2. Принципиальная схема программирования в OpenMP 121
11.2. Описание основных конструкций OPEN MP 123
4.1.4. Способы построения параллельных программ 128
11.3. Спецификация OpenMP для языков C и C++ 130
4.1.6. Вопросы к разделу 4.1 131
4.2. Основы построения библиотеки MPI 132
4.2.1. Основные понятия 132
4.2.2. Структура программ в MPI 134
4.2.3. Определение структуры приходящего сообщения 137
4.2.4. Определение базовых характеристик коммуникационной сети 138
11.4. Анализ тупиковых ситуаций при обмене 140
4.2.6. Организация передачи-приёма сообщений без блокировки 141
4.2.7. Реализация отложенных запросов на взаимодействие 143
4.2.8. Сравнительная оценка различных способов обмена данными 144
4.2.9. Использование глобальных операций в MPI 145
4.2.10. Взаимодействие процессов в MPI 145
4.2.11. Вопросы к раделу 4.2 148
Глава 5. Граф-схемы параллельных алгоритмов 150
5.1. Представление параллельных алгоритмов в виде граф-схем 150
5.1.1. Преобразование последовательных алгоритмов в параллельные 150
150
158
158
158
158
158
5.1.2.Использование граф-схем для представления параллельных алгоритмов 160
5.1.3. Вопросы к разделу 5.1 162
5.2.1. Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями 162
166
168
168
168
169
5.2.2. Вопросы к разделу 5.2 171
11.5. Построение матрицы логической несовместимости. 171
5.3.2. Построение матрицы логической несовместимости операторов 175
5.3.3. Вопросы к разделу 5.3 178
5.4.1. Построение множеств взаимно независимых операторов. 179
5.4.2. Вопросы к разделу 5.4 181
Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений 182
6.1. Численные характеристики информационных граф-схем со скалярными весами 182
6.1.1 Определение ранних и поздних сроков окончания выполнения операторов. 182
11.6. Определение функций плотности загрузки, и минимальной загрузки для информационных граф-схем 184
6.1.3. Вопросы к разделу 6.1 188
6.2.1. Распределение операторов по ВМ вычислительной системы с общим полем памяти для информационной граф-схемы 189
6.2.2. Распределение операторов по ВМ вычислительной системы с общим полем памяти для информационно-логической граф-схемы 192
6.2.3. Распределение операторов по ВМ вычислительной системы с распределённой памятью для информационной граф-схемы 194
6.2.4. Реализация диаграмм для общепринятых способов обмена данными между ВМ вычислительной системы с распределённой памятью для информационной граф-схемы 200
6.2.5. Вопросы к разделу 6.2 203