- •Оглавление
- •Глава 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
- •Литература
4.1.6. Вопросы к разделу 4.1
1. Какая модель параллельных вычислений используется в библиотеке OpenMP?
2. Какие директивы используются для создания и ликвидации нитей?
3. Какие существуют способы построения параллельных программ ?
4. Охарактеризуйте нисходящие и восходящие к корню, покрывающие ориентированные деревья.
5. Каким способом определяются области действия переменных в компиляторах Open MP?
6. В чём специфика использования потоков OpenMP на основе потоков Windows?
7. Какие этапы надо выполнить перед запуском программы в Open MP?
4.2. Основы построения библиотеки mpi
4.2.1. Основные понятия
Одной из распространённых технологий программирования для создания параллельных программ в настоящее время является библиотека МРI (Message Passing Interfase – интерфейс передачи данных) [29]. Для этой библиотеки выработано несколько стандартов. Наиболее часто используемым стандартом в настоящее время является стандарт МРI 1.1 образца 1997 – 1998гг. Последняя версия стандарта - 2.0. В этой версии к MPI добавлены такие важные элементы функциональности, как динамическое управление процессами, односторонние коммуникации (Put/Get), параллельный ввод/вывод. Однако ни в одной реализации на настоящее время интерфейс MPI 2.0 полностью не поддерживается. Основным способом взаимодействия параллельных процессов в этой библиотеке является передача сообщений. Стандарт МPI фиксирует интерфейс, который должен соблюдаться как рассматриваемой библиотекой на каждой вычислительной платформе, так и пользователем при создании своих программ.
Библиотека МРI поддерживает работу с языками Фортран и Си. В данном разделе будут изложены основные положения MPI стандарта. Более подробные сведения приведены в интернете [28].
Далее в тексте примеры и описания всех процедур будут даны с использованием языка Си иллюстрирующие основные возможности этой библиотеки. Полная версия MPI стандарта содержит описание более 125 процедур и функций. Интерфейс МPI поддерживает создание параллельных программ в стиле МIМD, что подразумевает объединение процессов с различными программными модулями. При использовании стандарта MPI компиляция программы требует подключения модулей библиотеки MPI. Это можно сделать в командной строке или воспользоваться предусмотренными в большинстве систем командами или скриптами mрicc (для программ на языке Си), mрiСС (для программ на языке Си++), и mрif77/mpif90 (для программ на языках Фортран 77/90). Опция компилятора <—о паmе> позволяет задать имя nаше для получаемого выполнимого файла, по умолчанию выполнимый файл называется а.оut, например:
mрiCC -о рrоgrаm рrоgrаm.c
После получения выполнимого файла необходимо запустить его на требуемом количестве процессоров. Для этого обычно предоставляется команда запуска МPI-приложений mрiruп, например:
mрirun -nр N <программа с аргументами>,
где N – число процессов, которое должно быть не более разрешенного в данной системе числа процессов для одной задачи. После запуска одна и та же программа будет выполняться всеми запущенными процессами, результат выполнения в зависимости от системы будет выдаваться на терминал или записываться в файл с предопределенным именем.
Все дополнительные объекты: имена процедур, константы, предопределенные типы данных и т.п., используемые в МРI, описаны в библиотеке mpi.h и имеют префикс MPI_. В языке Си, кроме того, является существенным регистр символов в названиях функций. Обычно в названиях функций МPI первая буква после префикса MPI_ пишется в верхнем регистре, последующие буквы — в нижнем регистре, а названия констант МPI записываются целиком в верхнем регистре.
МPI-программа – это множество параллельных взаимодействующих процессов. Все процессы порождаются один раз, образуя параллельную часть программы. В ходе выполнения МPI-программы не допускается порождение дополнительных процессов или уничтожение уже существующих. Каждый процесс работает в своем адресном пространстве , никаких общих переменных или данных в МPI нет. Основным способом взаимодействия между процессами является явная посылка сообщений.
Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения – коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах , не пересекаются и не мешают друг другу. Коммуникаторы имеют в языке Си — предопределенный тип MPI_Соmm. При старте программы всегда считается, что все порожденные процессы работают в рамках всеобъемлющего коммуникатора, имеющего предопределенное имя MPI_СOMM_WORLD. Этот коммуникатор существует всегда и служит для взаимодействия всех запущенных процессов МPI-программы. Кроме него при старте программы имеется коммуникатор MPI_СOMM_SELF, содержащий только один текущий процесс, а также коммуникатор MPI_СOMM_NULL, не содержащий ни одного процесса. Каждый процесс MPI-программы имеет в каждой группе, в которую он входит, уникальный атрибут - номер процесса, который является целым неотрицательным числом. С помощью этого атрибута происходит значительная часть взаимодействия процессов между собой. Ясно, что в одном и том же коммуникаторе все процессы имеют различные номера. Но поскольку процесс может одновременно входить в разные коммуникаторы, то его номер в одном коммуникаторе может отличаться от его номера в другом. Отсюда становятся понятными два основных атрибута процесса коммуникатор и номер в коммуникаторе. Если группа содержит n процессов, то номер любого процесса в данной группе лежит в пределах от 0 до n — 1.
Основным способом общения процессов между собой является явная посылка сообщений. Сообщение – это набор данных некоторого типа. Каждое сообщение имеет несколько атрибутов, в частности, номер процесса-отправителя, номер процесса-получателя, идентификатор сообщения и другие. По идентификатору процесс, принимающий сообщение, например, может различить два сообщения, пришедшие к нему от одного и того же процесса. Сам идентификатор сообщения является целым неотрицательным числом, лежащим в диапазоне от 0 до MPI_TAG_UP, причем гарантируется, что MPI_TAG_UP не меньше 32767. Для работы с атрибутами сообщений введен массив (в языке Си — структура), элементы которого дают доступ к их значениям.
В последнем аргументе (в языке Си — в возвращаемом значении функции) большинство процедур МРI возвращают информацию об успешности завершения. В случае успешного выполнения возвращается значение MPI_SUССESS, иначе — код ошибки. Вид ошибки, которая произошла при выполнении процедуры, можно будет определить из ее описания. Предопределенные значения, соответствующие различным ошибочным ситуациям, перечислены в файле mрif.h.
Рассмотрим часто используемые функции MPI:
INTEGER IERR;
MPI_INIT(IERR);
Инициализация параллельной части программы. Все другие процедуры МРI могут быть вызваны только после вызова MPI_INIT. Инициализация параллельной части для каждого приложения должна выполняться только один раз. В языке Си функции MPI_Iпit передаются указатели на аргументы командной строки программы аrgc и аrgv, из которых системой могут извлекаться и передаваться в параллельные процессы некоторые параметры запуска программы:
MPI_FINALIZE(IERR)
Завершение параллельной части приложения. Все последующие обращения к любым процедурам МРI, в том числе к MPI_INIT, запрещены. К моменту вызова MPI_FINALIZE каждым процессом программы все действия, требующие его участия в обмене сообщениями, должны быть завершены.