Авторитетность издания
Добавить в закладки
Следующий номер на сайте
Аналитическая модель оценки производительности распределенных систем
Аннотация:В работе рассматривается подход к определению понятия производительности в распределенных вычислительных системах и к анализу эффективности их работы. Отсутствие адекватных характеристик ограничивает возможности для количественного анализа эффективности систем данного класса, которые становятся все более распространенными.
Abstract:Parallel computing allows for solving large problems much faster and the efficiency metrics are defined and well-known. There are no such metrics or performance models for distributed systems that are becoming more widely spread. In this paper, we address the problem of defining what does it mean a distributed system is efficient or has high performance? We propose a natural extension of a classical analytical performance model to distributed systems.
Авторы: Афанасьев А.П. (apa@isa.ru) - Институт проблем передачи информации им. А.А. Харкевича РАН (ИППИ РАН), Московский государственный университет им. М.В. Ломоносова (профессор), Москва, Россия, доктор физико-математических наук, Посыпкин М.А. (mposypkin@mail.ru) - Институт системного анализа РАН, Центр грид-технологий и распределенных вычислений, г. Москва, Хританков А.С. (ahritankov@hotmail.ru) - Московский физико-технический институт | |
Ключевые слова: закон амдала, распределенные вычисления, анализ производительности |
|
Keywords: Amdahl’s Law, distributed computing, performance modeling |
|
Количество просмотров: 12871 |
Версия для печати Выпуск в формате PDF (4.85Мб) |
Анализ эффективности использования высокопроизводительных вычислительных систем является неотъемлемой частью разработки и тестирования параллельных приложений и используется владельцами кластерных систем коллективного доступа для формирования рекомендаций пользователям, оценки целесообразности предоставления ресурсов [1]. Для проведения подобных исследований был разработан теоретический аппарат [2], базовыми понятиями которого являются ускорение – отношение времени работы алгоритма в последовательном и параллельном вариантах и эффективность – отношение ускорения к числу процессоров, участвующих в вычислениях. Впоследствии эти понятия были обобщены для параллельных систем, включающих устройства различной производительности [2]. Были установлены фундаментальные соотношения, связывающие долю последовательных вычислений в программе с ускорением и эффективностью, – законы Амдала и Густавсона–Барсиса. Вероятно, из-за простоты и универсальности данная теория широко применяется для анализа параллельных приложений и многопроцессорных систем. В последнее десятилетие появились и получили развитие технологии распределенных вычислений [3], применяющиеся для проведения длительных расчетов, в которых участвуют разнородные вычислительные ресурсы различных организаций. Основной особенностью таких систем является неоднородная и динамически изменяющаяся структура ресурсов: вычислительные узлы могут подключаться к расчетам или выходить из них на протяжении всего времени расчетов. Традиционные модели для параллельных систем предполагают постоянный состав вычислительного пространства и не применяются для описания распределенных систем. Поэтому производительность распределенных приложений описывается, как правило, на качественном уровне. Данная работа посвящена анализу производительности распределенных вычислительных систем, в состав которых входят узлы различной производительности. При этом узлы участвуют в вычислениях в соответствии с некоторым расписанием – функцией, принимающей значение 1 в моменты, когда узел выделяется для вычислений, и 0 в противном случае. Такие системы далее именуются системами с расписанием. Для подобных систем авторами разработана методика анализа эффективности, основанная на сравнении с гипотетической эталонной системой. Варьирование эталонной системы позволяет получать количественные оценки различных характеристик производительности исследуемой распределенной системы. С помощью предложенной модели обобщаются понятия ускорения, эффективности, выводятся соотношения, связывающие эти величины. В частности, показывается, что традиционное понятие эффективности допускает различные обобщения для рассматриваемых систем. Описывается частный случай систем с расписанием, в которых все вычислительные узлы доступны на протяжении всего времени расчетов. Для таких систем выводится аналог закона Амдала. Представленная модель была реализована в системе BNB-Grid [4], опыт ее применения для анализа эффективности решения задач глобальной оптимизации в распределенной вычислительной среде подробно опи- сан в [5]. Системы с расписанием Основные определения. Построение модели производительности систем с расписанием следует начать с рассмотрения традиционной модели, применяемой для анализа производительности однородных параллельных систем [2]. Вычислительная система рассматривается как совокупность n вычислителей, способных решать некоторую общую задачу. Структура связей между вычислителями не учитывается. Модель для однородных систем обобщим для описания распределенных вычислительных систем. Системой с расписанием Â назовем совокупность n вычислителей, объединенных вычислительной сетью и работающих совместно для решения задачи A из некоторого класса А. Вычислители в процессе решения задачи могут быть доступны системе только часть времени. Расписание работы вычислителя i описывается функцией
Выберем некоторый эталонный алгоритм, с помощью которого принципиально возможно решить задачу A на каждом вычислителе системы. Для последовательного решения в качестве эталонного алгоритма можно использовать параллельный алгоритм, реализованный в системе. Временем решения задачи будем называть промежуток от начала процесса вычислений до прекращения использования всех вычислителей системы. Обозначим эталонное время решения задачи A вычислителем i при помощи эталонного алгоритма через Вычислительной системой с расписанием Далее по тексту будем опускать задачу A в обозначениях, если это не приводит к противоречиям. Характеристики производительности. Для определения характеристик производительности систем с расписанием потребуется понятие модели системы с расписанием, или эталонной системы. Эталонная система с расписанием – это модель системы с расписанием Â(A), позволяющая рассчитать время решения произвольной задачи А из класса А. Эталонная система может быть построена различными способами в зависимости от целей исследования. Построим универсальную эталонную систему Уточним понятие трудоемкости, введенной как нормировочный коэффициент ранее. Будем полагать, что трудоемкость отражает объективную сложность решения задачи. Выберем некоторый способ оценки трудоемкости решения задачи L(×) так, что для каждой задачи AÎА можно определить трудоемкость L=L(A). Трудоемкость задачи характеризует сложность получения ответа в некоторой постановке задачи. Для конкретного алгоритма трудоемкость выражается количеством операций некоторого исполнителя, выполняющего алгоритм, например, машины Тьюринга. Трудоемкость решения задачи можно определить и иначе. Рассмотрим задачу определения площади фигуры на плоскости с некоторой заданной точностью. При использовании алгоритма Монте-Карло трудоемкость решения задачи определяется как количество итераций метода, требуемых для достижения необходимой точности. Будем полагать, что при переходе от последовательного решения к параллельному трудоемкость остается постоянной. В большинстве случаев при рассмотрении задачи целиком, без ограничения общности, можно принять L(A)=1. Согласно сделанным предположениям, эталонное время решения
где При этом полагаем, что эталонная система прекращает использование вычислителей системы в момент Величина p(t) называется эталонной производительностью системы Â. Так как p(t)³0 для всех t, задача имеет единственное решение: Эффективностью по времени, или просто эффективностью E системы Â, назовем отношение эталонного времени решения
Согласно построению эталонной системы при отсутствии сверхлинейного ускорения эталонное время По аналогии с моделью производительности для однородных систем введем характеристику производительности системы, определяющую, насколько быстрее решает задачу параллельная система, чем вычислители, из которых она составлена. Коэффициентом ускорения Si системы Â по отношению к вычислителю i будем называть отношение эталонного времени решения вычислителя
Коэффициентом эталонного ускорения Приведем несколько соотношений, вытекающих из определения эффективности и коэффициентов ускорения. Пусть имеется система с расписанием Â и заданы эталонные системы
где Ea – эффективность системы Â по отношению к системе
Легко показать справедливость следующего утверждения, устанавливающего связь между эффективностью и коэффициентами ускорения. Утверждение 1. Эффективность E системы Â может быть рассчитана по формуле
Ресурсная модель производительности. Введенное ранее понятие эффективности является количественной характеристикой, показывающей, насколько реальный эффект сокращения времени расчетов близок к предполагаемому при заданном расписании. Полученное значение эффективности при этом зависит от расписания, что сужает предсказательную силу рассчитанных характеристик. Вместе с тем целесообразно также оценивать избыточность затрат вычислительных ресурсов. Введенное понятие эффективности не подходит для этого, так как ее значение зависит от выбранного расписания. Поясним сказанное на примере. Пусть имеется система с расписанием из одного вычислителя производительности p1=1. Предположим, что при первом запуске вычислитель сразу выделяется для решения задачи и решает ее за время T1=2, при этом функция расписания Введем характеристики производительности системы, не зависящие от конкретного вида расписания, что позволит сохранить значение эффективности при неизменности некоторых параметров расписания. Рассмотрим простую модель учета затрат на вычисления, в которой задана удельная стоимость ci>0 использования вычислителя i в единицу времени. Будем полагать, что стоимость использования Под стоимостью использования вычислителя можно понимать и количество условных элементарных операций, в которых измеряется трудоемкость L. В этом случае Ресурсной эффективностью системы Â будем называть отношение стоимости использования эталонной системы для решения задачи к реальной стоимости: Функция стоимости Средняя стоимость использования Отсюда следует, что средняя стоимость fi(t) не может превышать удельную стоимость ci:
Следующее соотношение устанавливает связь между эффективностью по времени E и ресурсной эффективностью
Вкладом ki(t) вычислителя i в стоимость использования назовем отношение средней стоимости использования вычислителя к средней стоимости использования системы:
Введем понятие, которое аналогично коэффициенту ускорения в традиционной модели производительности. Удешевлением вычислений системы по отношению к вычислителю i назовем отношение стоимости эталонного решения на вычислителе i к действительной стоимости решения в системе:
Для ресурсной эффективности справедливо соотношение, аналогичное (7):
Рассчитаем ресурсную эффективность системы в приведенном примере. Будем полагать удельную стоимость вычислений равной эталонной производительности c1=p1. При первом запуске Поэтому ресурсная эффективность во втором случае Величина В приведенном примере во втором случае использовалось расписание с растущей стоимостью, или, для краткости, растущее расписание, в котором суммарная стоимость вычислений при Если все вычислители системы доступны на протяжении всего времени решения задачи, то Q=1, следовательно, ресурсная эффективность и эффективность по времени совпадают. Обратное неверно, то есть из того, что Q=1, не следует, что в системе с расписанием вычислители доступны на протяжении всего времени решения. Например, для распределенной системы, работающей с эффективностью 1, ресурсная эффективность и эффективность также совпадают и коэффициент формы расписания равен 1. Эталонная система для задач с последовательной частью Рассмотрим возможность применения модели систем с расписанием к неоднородным вычислительным системам. Обычно под неоднородной системой понимают совокупность неодинаковых вычислителей. В качестве примера неоднородной системы можно привести сеть рабочих станций, объединенных локальной сетью и используемых в монопольном режиме. Другим примером неоднородной системы может служить совокупность центрального процессора и графического ускорителя рабочей станции. Распределенная система, включающая несколько вычислительных кластеров на некотором промежутке времени, когда состав системы постоянен, также будет неоднородной системой. Одним из подходов к описанию производительности неоднородных систем является модель системы функциональных устройств [2]. Рассмотрим неоднородную систему как частный случай системы с расписанием и построим эталонную систему для оценки характеристик производительности системы при решении задач с последовательной частью. Представим класс Аb задач с последовательной и параллельной частями. Пусть для каждой задачи A доля последовательных вычислений составляет b. Для решения последовательной части может использоваться только один вычислитель. Для оценки производительности неоднородных систем применим подход, использованный в модели систем с расписанием, и построим эталонную систему Для неоднородных систем сформулируем утверждение, аналогичное известному закону Амдала для однородных систем. Для расчета характеристик производительности системы Утверждение. Пусть в системе Так как время решения T задачи эталонной системой Следствие (закон Амдала). Пусть вычислители неоднородной системы Оценим характеристики производительности Eb и В итоге следует отметить, что в работе предложен подход к количественной оценке характеристик производительности приложений, работающих в распределенной вычислительной среде. Обобщены традиционные для параллельных систем понятия ускорения и эффективности, выведены различные соотношения, связывающие эти величины с расписанием работы вычислительных узлов и их производительностью. Для неоднородных систем, в которых все узлы работают на протяжении всего времени расчета, получены выражения для максимальной эффективности и ускорения, аналогичные закону Амдала. Практическая ценность предложенного подхода была продемонстрирована на примере расчетов энергетически оптимальных конфигураций молекулярных кластеров, проведенных в вычислительной среде, состоящей из нескольких суперкомпьютеров [5]. Разработанный теоретический аппарат в дальнейшем планируется использовать для анализа различных распределенных приложений, а также для построения критериев оценки качества работы алгоритмов управления вычислительной нагрузкой в распределенной среде. Литература 1. Воеводин Вл.В. НИВЦ МГУ: широким фронтом совместных дел // Численные методы, параллельные вычисления и информационные технологии: сб. науч. тр.; под ред. Вл.В. Воеводина и Е.Е. Тыртышникова. М.: Изд-во МГУ, 2008. 2. Хританков А.С. Модели и алгоритмы балансировки нагрузки // Информационные технологии и вычислительные системы. 2009. № 2. С. 65–80. 3. Emelyanov S.V., Afanasiev A.P., Grinberg Y.R., Krivtsov V.Y., Peltsverger B.V., Sukhoroslov O.V., Taylor R.G., Voloshinov V.V. Distributed Computing and Its Applications. Editor: Velikhov, E.P. Bristol, ME, USA: Felicity Press, 2005. 4. Афанасьев А.П., Посыпкин М.А., Сигал И.Х. Проект BNB-Grid: решение задач глобальной оптимизации в распределенной среде // Системный анализ и информационные технологии (САИТ-2007): тр. Второй междунар. конф. 2007. М.: Изд-во ЛКИ/URSS, 2008. Т. 2. С. 177–181. 5. Посыпкин М.А., Хританков А.С. О понятии ускорения и эффективности в распределенных системах // Научный сервис в сети Интернет: решение больших задач: тр. 10-й Всерос. конф. 2008. С. 149–156. |
Постоянный адрес статьи: http://swsys.ru/index.php?id=2372&like=1&page=article |
Версия для печати Выпуск в формате PDF (4.85Мб) |
Статья опубликована в выпуске журнала № 4 за 2009 год. |
Возможно, Вас заинтересуют следующие статьи схожих тематик:
- Решение задач глобальной оптимизации в среде распределенных вычислений
- Среда визуального программирования для разработки параллельного программного обеспечения обработки изображений и сигналов
- Разработка архитектуры универсального фреймворка федеративного обучения
- Интегрированная инструментальная среда организации проблемно-ориентированных распределенных вычислений
- Программный модуль автоматизированного расчета параметров экранов защиты бортовой электронной аппаратуры от радиационного воздействия
Назад, к списку статей