Вычислительных систем
 Скачать 0.78 Mb.
|
|
42 Глава 3. Организация функционирования ВС Тогда ?????? (??????) = max ??????∈?????? {︃ ?????? ∑︁ ??????=1 ?????? ∑︁ ??????=1 ?????? ∑︁ ??????=1 ?????? ???????????? ?????? ???????????? ??????(??????, ??????, ??????, ??????) }︃ Значение функции ??????(??????, ??????, ??????, ??????) может быть получено согласно модели Хокни: ??????(??????, ??????, ??????, ??????) = ?????? ???????????? ??????(??????, ??????) , где ??????(??????, ??????) – пропускная способность канала связи между процессорами ?????? и ??????. Сформулируем задачу оптимального вложения параллельной програм- мы в ВС с иерархической организацией: ?????? (??????) = max ??????∈?????? {︃ ?????? ∑︁ ??????=1 ?????? ∑︁ ??????=1 ?????? ∑︁ ??????=1 ?????? ???????????? ?????? ???????????? ??????(??????, ??????, ??????, ??????) }︃ → min (?????? ???????????? ) (3.12) при ограничениях: ?????? ∑︁ ??????=1 ?????? ???????????? = 1, ?????? = 1, 2, . . . , ??????, (3.13) ?????? ∑︁ ??????=1 ?????? ???????????? = 1, ?????? = 1, 2, . . . , ??????, (3.14) ?????? ???????????? ∈ {0, 1}. (3.15) Ограничения (3.13) и (3.15) гарантируют назначение каждой ветви па- раллельной программы на единственную ЭМ. Ограничение (3.14) обеспе- чивает назначение на машину одной ветви. Задача (3.12)–(3.15) относится к дискретной оптимизации и является трудноразрешимой. 3.4.2. Эвристический метод вложения параллельных программ в ВС Метод H IERARCHIC M AP [5] вложения параллельных программ основан на рекурсивном разбиении графа параллельной программы на подмноже- ства интенсивно обменивающихся параллельных ветвей и отображения их на ЭМ, связанные быстрыми каналами связи. Цель разбиения – миними- зация суммы весов ребер, инцидентных разным подмножествам разбиения. Разбиение выполняется многократно для каждого уровня иерархии коммуникационной среды. Функция P ART G RAPH возвращает список под- графов, получаемых в результате разбиения исходного графа. Ниже приведен псевдокод метода H IERARCHIC M AP , на вход которого подается граф ??????, номер ?????? уровня коммуникационной среды и номер ?????? эле- 3.4. Вложение параллельных программ в ВС 43 мента на уровне ??????. Проиллюстрируем метод на примере отображения параллельной про- граммы на подсистему из 16 ЭМ (рис. 3.2). На первом шаге выполняется разбиение (P ART G RAPH ) исходного графа ?????? на ?????? 11 подграфов (?????? 21 и ?????? 22 ) по ?????? 21 и ?????? 22 вершин. Далее графы ?????? 21 и ?????? 22 рекурсивно разбиваются на ?????? 21 и ?????? 22 частей. Полученные в результате этого разбиения подграфы ?????? 31 , ?????? 32 , ?????? 33 (их вершины – ветви программы) назначаются на узел 1 (процес- сорные ядра 1, 2, 3, 4) и узел 2 (процессорные ядра 5, 6, 7, 8) кластера ?????? и узел 1 (процессорные ядра 9, 10, . . . , 16) кластера ??????. 1 function H IERARCHIC M AP (??????, ??????, ??????) 2 if ?????? = ?????? then 3 return ?????? ??????,1 , ?????? ??????,2 , . . . , ?????? ??????,?????? ?????? 4 else 5 (?????? ??????+1,1 , . . . , ?????? ??????+1,?????? ???????????? ) = P ART G RAPH (?????? ???????????? , ?????? ???????????? , ?????? ??????+1,1 , . . . , ?????? ??????+1,?????? ???????????? ) 6 for ?????? = 1 to ?????? ???????????? do 7 H IERARCHIC M AP (?????? ??????+1,?????? , ?????? + 1, ??????) 8 end for 9 end if 10 end function 3.4.3. Задание 1. Написать программу, реализующую метод H IERARCHIC M AP вложе- ния параллельных программ в распределенные ВС. 2. Построить графики зависимости времени выполнения алгоритма и значения целевой функции ?????? (??????) от числа ?????? параллельных ветвей для разных алгоритмов разбиения графов. Для разбиения графов рекомендуется использовать пакеты METIS или Scotch. Информационные графы параллельных программ для различного числа ?????? параллельных ветвей находятся на сетевом ресурсе, доступ к которому следует получить у преподавателя. В качестве модельной ВС использовать конфигурацию вычислительно- го кластера на базе SMP-узлов. В котором: уровень 1 – сеть связи между серверными стойками (InfiniBand QDR), уровень 2 – сеть связи внутри сто- ек между узлами (InfiniBand QDR), уровень 3 – разделяемая память узлов (DDR3-1600). Каждый вычислительный узел содержит два четырехъядер- ных процессора. Подсистемы формируются из полностью выделенных для решения задачи вычислительных узлов. В качестве значений пропускной способности ??????(??????, ??????) между процес- сорными ядрами рекомендуется взять пиковую пропускную способность (оценку сверху) для соответствующего канала связи. 44 Глава 3. Организация функционирования ВС 3.4.4. Контрольные вопросы 1. Описать модель распределенной ВС с иерархической структурой. 2. Что такое информационный граф задачи? Как его получить для параллельных программ в стандарте MPI? 3. Дать определение задачи вложения. Почему важно учитывать иерар- хическую структуру распределенных ВС при реализации параллельных программ на них? 4. От чего зависит эффективность метода H IERARCHIC M AP ? В каких случаях он неэффективен? 4. Приложения 4.1. Функции округления Округление вещественного числа ?????? до меньшего ближайшего целого числа обозначается как ⌊??????⌋ или floor(??????) – пол. Также эту функцию назы- вают антье (от фр. entier) – целая часть вещественного числа ?????? − 1 < ⌊??????⌋ ≤ ??????. В литературе можно встретить альтернативное обозначение целой ча- сти части числа ?????? (функции пол) – это обозначение Гаусса [??????]. Примеры использования функции пол: – ⌊1.3⌋ = 1; – ⌊1.7⌋ = 1; – ⌊−3.7⌋ = −4; – ⌊−4⌋ = −4. Округление вещественного числа ?????? до большего ближайшего целого числа обозначается как ⌈??????⌉ или ceil(??????) – потолок ?????? ≤ ⌈??????⌉ < ?????? + 1. Примеры использования функции потолок: – ⌈1.3⌉ = 2; – ⌈1.7⌉ = 2; – ⌈−3.7⌉ = −3; – ⌈−4⌉ = −4. Функции пол и потолок введены 1962 г. К. Айверсоном [6]. Для них справедливы следующие соотношения ⌊??????⌋ ≤ ?????? ≤ ⌈??????⌉. Целочисленное слагаемое ?????? можно вносить и выносить за скобки функций пол/потолок ⌊?????? + ??????⌋ = ⌊??????⌋ + ??????, ⌈?????? + ??????⌉ = ⌈??????⌉ + ??????. 46 Глава 4. Приложения 4.2. Факториалы Факториал (factorial) целого числа ?????? – это произведение натуральных чисел от 1 до ?????? включительно ??????! = 1 · 2 · . . . · ??????, ??????! = ?????? · (?????? − 1)!, 0! = 1. Асимптотическая формула Стирлинга для приближенного вычисле- ния факториала целого числа ?????? ??????! = √ 2???????????? (︁ ?????? ?????? )︁ ?????? (︂ 1 + ?????? (︂ 1 ?????? )︂)︂ , ??????! ≈ √ 2???????????? (︁ ?????? ?????? )︁ ?????? 4.3. Элементарная обработка результатов измерений Пусть требуется измерить некоторую величину ??????. Например, время выполнения программы, реализующей некоторый алгоритм. Рассмотрим основные этапы измерения величины ?????? и обработки полученных резуль- татов. 1. Выполняем серию измерений. Для уменьшения влияния случай- ных ошибок выполняем ?????? измерений величины ??????. Обозначим результаты измерений через ?????? 1 , ?????? 2 , . . . , ?????? ?????? Такой ряд значений величины ?????? называют выборкой (sample). 2. Вычисляем характеристики выборки. При конечном числе ?????? из- мерений в качестве оценки истинного значения измеряемой величины ис- пользуют среднее арифметическое ¯?????? результатов измерений или, как его еще называют, выборочное среднее (sample mean). Вычисляем его по сле- дующей формуле ¯ ?????? = 1 ?????? ?????? ∑︁ ??????=1 ?????? ?????? Перед вычислением среднего значения ¯?????? можно провести анализ вы- борки и отбросить промахи измерений (выбросы, outliers). Например, мож- но упорядочить выборку по значениям ?????? ?????? и отбросить 25% первых и по- следних элементов (наименьших и наибольших). 4.3. Элементарная обработка результатов измерений 47 Вычисляем несмещенную оценку ?????? 2 дисперсии величины ?????? (unbiased sample variance) ?????? 2 = 1 ?????? − 1 ?????? ∑︁ ??????=1 (?????? ?????? − ¯ ??????) 2 = 1 ??????(?????? − 1) (︃ ?????? ?????? ∑︁ ??????=1 ?????? 2 ?????? − ( ?????? ∑︁ ??????=1 ?????? ?????? ) 2 )︃ (4.1) Отклонение ?????? отдельного результата измерения ?????? ?????? от среднего значе- ния ¯?????? называют средней квадратичной ошибкой или cредней квадрати- ческой ошибкой (sample standard deviation, StdDev) ?????? = √ ?????? 2 = ⎯ ⎸ ⎸ ⎷ 1 ?????? − 1 ?????? ∑︁ ??????=1 (?????? ?????? − ¯ ??????) 2 = ⎯ ⎸ ⎸ ⎷ 1 ??????(?????? − 1) (︃ ?????? ?????? ∑︁ ??????=1 ?????? 2 ?????? − ( ?????? ∑︁ ??????=1 ?????? ?????? ) 2 )︃ Среднеквадратичной ошибкой среднего арифметического (standard error of the mean, StdErr) называется величина ?????? ¯ ?????? , которая характеризует точность, с которой получено среднее значение ¯??????. Вычисляем ?????? ¯ ?????? по следу- ющей формуле ?????? ¯ ?????? = ?????? √ ?????? = √︂ ?????? 2 ?????? = ⎯ ⎸ ⎸ ⎸ ⎷ ?????? ∑︀ ??????=1 (?????? ?????? − ¯ ??????) 2 ??????(?????? − 1) 3. Строим доверительный интервал. Для расчета абсолютной ошиб- ки при малом количестве измерений вводится специальный коэффициент, зависящий от надежности (вероятности) ?????? и числа измерений ??????, называе- мый коэффициентом Стьюдента ?????? ??????,?????? Задаем уровень доверительной вероятности (например, ?????? = 0.99) и по табл. 4.1 находим значение коэффициента ?????? ??????,?????? . Вычисляем абсолютную ошибку Δ?????? Δ?????? = ?????? ¯ ?????? · ?????? ??????,?????? Доверительный интервал (confidence interval) записываем в виде ?????? = ¯ ?????? ± ?????? ¯ ?????? · ?????? ??????,?????? Последняя запись говорит о том, что с вероятностью ?????? истинное значение измеренной величины ?????? лежит в интервале [¯ ?????? − ?????? ¯ ?????? · ?????? ??????,?????? , ¯ ?????? + ?????? ¯ ?????? · ?????? ??????,?????? ]. 48 Глава 4. Приложения Таблица 4.1. Значения коэффициентов Стьюдента ?????? ??????,?????? ?????? ?????? 0.95 0.99 0.999 2 12.706 63.657 636.61 3 4.303 9.925 31.598 4 3.182 5.841 12.941 5 2.776 4.604 8.610 6 2.571 4.032 6.859 7 2.447 3.707 5.959 8 2.365 3.499 5.405 9 2.306 3.355 5.041 10 2.262 3.250 4.781 20 2.093 2.861 3.883 30 2.045 2.756 3.659 40 2.021 2.704 3.551 50 2.021 2.704 3.551 ∞ 1.960 2.576 3.291 4.3.1. Метод Велфорда вычисления среднего квадратичного отклонения При вычислении ?????? 2 по формуле (4.1) значение ?????? 2 может быть меньше нуля. Следовательно, при вычислении ?????? = √ ?????? 2 мы получим ошибку. В работе [7, С. 259] для нахождения значения ?????? рассмотрен метод Велфорда (B.P. Welford), основанный на следующих рекуррентных соотношениях ?????? 1 = ?????? 1 , ?????? ?????? = ?????? ??????−1 + (?????? ?????? − ?????? ??????−1 )/??????, ?????? 1 = 0, ?????? ?????? = ?????? ??????−1 + (?????? ?????? − ?????? ??????−1 ) · (?????? ?????? − ?????? ?????? ), для ?????? = 2, 3, . . . , ??????. Откуда ?????? = √︀ ?????? ?????? /(?????? − 1). 4.4. Вопросы к экзамену 49 4.4. Вопросы к экзамену 4.4.1. Надежность и живучесть вычислительных систем 1. Архитектурные особенности современных распределенных вычисли- тельных систем. Режимы функционирования вычислительных систем. 2. Модели вычислительной системы со структурной избыточностью. Показатели надежности вычислительных систем в переходном и стацио- нарном режимах функционирования. 3. Методика расчета показателей надежности вычислительных систем в переходном и стационарном режимах функционирования. 4. Живучие вычислительные системы. Потенциальная и структурная живучесть. Показатели потенциальной живучести вычислительных систем. 5. Расчет показателей живучести вычислительных систем. Контину- альный подход к анализу живучести вычислительных систем. 6. Показатели структурной живучести распределенных вычислитель- ных систем. Перспективные структуры распределенных вычислительных систем. 7. Осуществимость решения задач на вычислительных системах. 8. Технико-экономическая эффективность функционирования вычис- лительных систем. 9. Экспресс-анализ функционирования вычислительных систем. 4.4.2. Организация функционирования вычислительных систем 1. Цели и задачи организации функционирования распределенных вы- числительных систем. 2. Мультипрограммные режимы функционирования распределенных вычислительных систем. Режим обработки набора параллельных задач. Ре- жим обслуживания потока параллельных задач. 3. Методы построения расписаний выполнения параллельных программ на ВС. 4. Эвристические алгоритмы упаковки прямоугольников в полуограни- ченную полосу. Вычислительная сложность алгоритмов. 5. Теоретико-игровой подход к организации функционирования рас- пределенных вычислительных систем. Игра «диспетчер-вычислительный центр». 6. Методы решения теоретико-игровых задач. Итеративный метод Бра- уна. 7. Подход к организации функционирования распределенных вычисли- тельных систем с привлечением аппарата стохастического программирова- 50 Глава 4. Приложения ния. 8. Методы решения задач стохастического программирования при об- служивании потоков параллельных программ. 9. Децентрализованные алгоритмы обслуживания потоков задач в рас- пределенных вычислительных системах. 10. Вложение в распределенные вычислительные системы параллель- ных программ с целью минимизации времени их выполнения. 11. Задача разбиения вычислительной системы на подсистемы элемен- тарных машин. 12. Алгоритмы реализации коллективных информационных обменов в распределенных вычислительных системах. Литература [1] Хорошевский В. Г. Архитектура вычислительных систем – 2-е изд. — М. : МГТУ им. Н.Э. Баумана, 2008. — 520 с. [2] Алгоритмы: построение и анализ. – 3-е изд. / Т. Х. Кормен, Ч. И. Лей- зерсон, Р. Л. Ривест, К. Штайн. — М. : Вильямс, 2013. — 1328 с. [3] Евреинов Э. В., Хорошевский В. Г. Однородные вычислительные си- стемы. — Н. : Наука. Сибирское отд-е, 1978. — 319 с. [4] Хедли Дж. Нелинейное и динамическое программирование. — М. : Мир, 1967. — 508 с. [5] Курносов М. Г., Пазников А. А. Эвристические алгоритмы отображе- ния параллельных MPI-программ на мультикластерные вычислитель- ные и GRID-системы // Вычислительные методы и программирова- ние. — 2013. — № 14. — С. 1–10. [6] Грэхем Р., Кнут Д.Э., Паташник О. Конкретная математика. Матема- тические основы информатики. — М. : Вильямс, 2010. — 784 с. [7] Кнут Д.Э. Искусство программирования. Том 2. Получисленные ал- горитмы. — М. : Вильямс, 2011. — 832 с. [8] Хорошевский В. Г. Инженерный анализ функционирования вычисли- тельных машин и систем. — М. : Радио и связь. — 256 с. [9] Кнут Д.Э. Искусство программирования. Том 1. Основные алгорит- мы. — М. : Вильямс, 2010. — 720 с. [10] Кнут Д.Э. Искусство программирования. Том 3. Сортировка и по- иск. — М. : Вильямс, 2012. — 824 с. [11] М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — М. : Мир, 1982. — 416 с. [12] С. Танаев В., В. Шкурба В. Введение в теорию расписаний. — М. : Наука, 1975. — 256 с. Практикум Курносов Михаил Георгиевич Пазников Алексей Александрович О ÑÍÎÂÛ ÒÅÎÐÈÈ ÔÓÍÊÖÈÎÍÈÐÎÂÀÍÈß ÐÀÑÏÐÅÄÅËÅÍÍÛÕ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÑÈÑÒÅÌ Подписано в печать 25.09.2015. Формат 70 × 100 1 / 16 Бумага офсетная. Печать цифровая. Усл. печ. л. 4,19. Уч.-изд. л. 1,6. Тираж 300. Заказ 0925. Отпечатано в ООО «Автограф». 630090, Новосибирск, Весенний пр., 4. Тел. (383) 330-26-98. |