Software & Systems

Анализ эффективности использования высокопроизводительных вычислительных систем является неотъемлемой частью разработки и тестирования параллельных приложений и используется владельцами кластерных систем коллективного доступа для формирования рекомендаций пользователям, оценки целесообразности предоставления ресурсов [1]. Для проведения подобных исследований был разработан теоретический аппарат [2], базовыми понятиями которого являются ускорение – отношение времени работы алгоритма в последовательном и параллельном вариантах и эффективность – отношение ускорения к числу процессоров, участвующих в вычислениях. Впоследствии эти понятия были обобщены для параллельных систем, включающих устройства различной производительности [2]. Были установлены фундаментальные соотношения, связывающие долю последовательных вычислений в программе с ускорением и эффективностью, – законы Амдала и Густавсона–Барсиса. Вероятно, из-за простоты и универсальности данная теория широко применяется для анализа параллельных приложений и многопроцессорных систем.

В последнее десятилетие появились и получили развитие технологии распределенных вычислений [3], применяющиеся для проведения длительных расчетов, в которых участвуют разнородные вычислительные ресурсы различных организаций. Основной особенностью таких систем является неоднородная и динамически изменяющаяся структура ресурсов: вычислительные узлы могут подключаться к расчетам или выходить из них на протяжении всего времени расчетов. Традиционные модели для параллельных систем предполагают постоянный состав вычислительного пространства и не применяются для описания распределенных систем. Поэтому производительность распределенных приложений описывается, как правило, на качественном уровне.

Данная работа посвящена анализу производительности распределенных вычислительных систем, в состав которых входят узлы различной производительности. При этом узлы участвуют в вычислениях в соответствии с некоторым расписанием – функцией, принимающей значение 1 в моменты, когда узел выделяется для вычислений, и 0 в противном случае. Такие системы далее именуются системами с расписанием. Для подобных систем авторами разработана методика анализа эффективности, основанная на сравнении с гипотетической эталонной системой. Варьирование эталонной системы позволяет получать количественные оценки различных характеристик производительности исследуемой распределенной системы. С помощью предложенной модели обобщаются понятия ускорения, эффективности, выводятся соотношения, связывающие эти величины. В частности, показывается, что традиционное понятие эффективности допускает различные обобщения для рассматриваемых систем. Описывается частный случай систем с расписанием, в которых все вычислительные узлы доступны на протяжении всего времени расчетов. Для таких систем выводится аналог закона Амдала. Представленная модель была реализована в системе BNB-Grid [4], опыт ее применения для анализа эффективности решения задач глобальной оптимизации в распределенной вычислительной среде подробно опи- сан в [5].

  Системы с расписанием  

Основные определения. Построение модели производительности систем с расписанием следует начать с рассмотрения традиционной модели, применяемой для анализа производительности однородных параллельных систем [2]. Вычислительная система рассматривается как совокупность n вычислителей, способных решать некоторую общую задачу. Структура связей между вычислителями не учитывается. Модель для однородных систем обобщим для описания распределенных вычислительных систем. Системой с расписанием Â назовем совокупность n вычислителей, объединенных вычислительной сетью и работающих совместно для решения задачи A из некоторого класса А. Вычислители в процессе решения задачи могут быть доступны системе только часть времени. Расписание работы вычислителя i описывается функцией . При этом , если вычислитель доступен для системы, и  в противном случае. Введем характеристику доступности  вычислителя i, выражающую время, которое вычислитель был доступен к моменту t:

, ri(t)£1.                               (1)

Выберем некоторый эталонный алгоритм, с помощью которого принципиально возможно решить задачу A на каждом вычислителе системы. Для последовательного решения в качестве эталонного алгоритма можно использовать параллельный алгоритм, реализованный в системе. Временем решения задачи будем называть промежуток от начала процесса вычислений до прекращения использования всех вычислителей системы. Обозначим эталонное время решения задачи A вычислителем i при помощи эталонного алгоритма через . Время  может быть получено экспериментально или оценено теоретически в зависимости от класса задач А. Эталонной производительностью  вычислителя i при решении задачи A будем называть величину , где L – коэффициент, характеризующий трудоемкость решения задачи A.

Вычислительной системой с расписанием  для решения задачи A назовем совокупность вектора расписания системы  и вектора эталонных производительностей вычислителей : , , .

Далее по тексту будем опускать задачу A в обозначениях, если это не приводит к противоречиям.

Характеристики производительности. Для определения характеристик производительности систем с расписанием потребуется понятие модели системы с расписанием, или эталонной системы. Эталонная система с расписанием – это модель системы с расписанием Â(A), позволяющая рассчитать время решения произвольной задачи А из класса А. Эталонная система может быть построена различными способами в зависимости от целей исследования.

Построим универсальную эталонную систему , сравнение с которой позволит количественно оценить величину накладных расходов, связанных с распараллеливанием решения. Система  состоит из вычислителей системы Â, работающих по тому же расписанию  и имеющих такую же эталонную производительность . Будем полагать, что в системе  отсутствуют накладные расходы, связанные с распараллеливанием, и задача произвольно делится на подзадачи, выполняемые параллельно на произвольном количестве вычислителей. Вычислители эталонной системы управляются произвольным образом, на распределение задач не накладывается никаких ограничений. Примем, что в эталонной системе не проявляются эффекты сверхлинейного ускорения. При необходимости может быть построена эталонная система, учитывающая возможность сверхлинейного ускорения.

Уточним понятие трудоемкости, введенной как нормировочный коэффициент ранее. Будем полагать, что трудоемкость отражает объективную сложность решения задачи. Выберем некоторый способ оценки трудоемкости решения задачи L(×) так, что для каждой задачи AÎА можно определить трудоемкость L=L(A). Трудоемкость задачи характеризует сложность получения ответа в некоторой постановке задачи. Для конкретного алгоритма трудоемкость выражается количеством операций некоторого исполнителя, выполняющего алгоритм, например, машины Тьюринга. Трудоемкость решения задачи можно определить и иначе. Рассмотрим задачу определения площади фигуры на плоскости с некоторой заданной точностью. При использовании алгоритма Монте-Карло трудоемкость решения задачи определяется как количество итераций метода, требуемых для достижения необходимой точности. Будем полагать, что при переходе от последовательного решения к параллельному трудоемкость остается постоянной. В большинстве случаев при рассмотрении задачи целиком, без ограничения общности, можно принять L(A)=1.

Согласно сделанным предположениям, эталонное время решения  задачи системой  определяется как решение задачи оптимизации:  при условии

,                                                  (2)

где .

При этом полагаем, что эталонная система прекращает использование вычислителей системы в момент .

Величина p(t) называется эталонной производительностью системы Â. Так как p(t)³0 для всех t, задача имеет единственное решение: >0. Введем характеристики производительности системы с расписанием, используя эталонную систему в качестве образца таким образом, чтобы полученные характеристики являлись обобщением известных понятий коэффициентов эффективности и ускорения для однородных систем.

Эффективностью по времени, или просто эффективностью E системы Â, назовем отношение эталонного времени решения  к действительному времени решения задачи T:

.                                                                    (3)

Согласно построению эталонной системы при отсутствии сверхлинейного ускорения эталонное время  не превышает реальное T, поэтому эффективность не превышает единицу, E£1.

По аналогии с моделью производительности для однородных систем введем характеристику производительности системы, определяющую, насколько быстрее решает задачу параллельная система, чем вычислители, из которых она составлена. Коэффициентом ускорения Si системы Â по отношению к вычислителю i будем называть отношение эталонного времени решения вычислителя  к действительному времени решения T:

.                                                                  (4)

Коэффициентом эталонного ускорения  назовем коэффициент ускорения эталонной системы: .

Приведем несколько соотношений, вытекающих из определения эффективности и коэффициентов ускорения. Пусть имеется система с расписанием Â и заданы эталонные системы  и . Тогда эффективность системы Â по отношению к системе  равна:

,                                                           (5)

где Ea – эффективность системы Â по отношению к системе ; Eab – эффективность системы  по отношению к системе . Коэффициент эталонного ускорения  может быть использован для вычисления ускорения Si через эффективность по формуле

.                                                               (6)

Легко показать справедливость следующего утверждения, устанавливающего связь между эффективностью и коэффициентами ускорения.

Утверждение 1. Эффективность E системы Â может быть рассчитана по формуле

.                                               (7)

Ресурсная модель производительности. Введенное ранее понятие эффективности является количественной характеристикой, показывающей, насколько реальный эффект сокращения времени расчетов близок к предполагаемому при заданном расписании. Полученное значение эффективности при этом зависит от расписания, что сужает предсказательную силу рассчитанных характеристик. Вместе с тем целесообразно также оценивать избыточность затрат вычислительных ресурсов. Введенное понятие эффективности не подходит для этого, так как ее значение зависит от выбранного расписания. Поясним сказанное на примере.

Пусть имеется система с расписанием из одного вычислителя производительности p1=1. Предположим, что при первом запуске вычислитель сразу выделяется для решения задачи и решает ее за время T1=2, при этом функция расписания . Эффективность системы составляет E1=1/2. Пусть при втором запуске вычислитель выделяется только через t0=1, при расписании , t>t0 и , t£t0. Время решения задачи составляет T2=t0+T1=3. Эффективность системы теперь составляет E2=2/3.

Введем характеристики производительности системы, не зависящие от конкретного вида расписания, что позволит сохранить значение эффективности при неизменности некоторых параметров расписания. Рассмотрим простую модель учета затрат на вычисления, в которой задана удельная стоимость ci>0 использования вычислителя i в единицу времени. Будем полагать, что стоимость использования  системы Â к моменту t складывается только из стоимостей использования вычислителей  и вычисляется по формулам , .

Под стоимостью использования вычислителя можно понимать и количество условных элементарных операций, в которых измеряется трудоемкость L. В этом случае  и соотношение  выполняется.

Ресурсной эффективностью системы Â будем называть отношение стоимости использования эталонной системы для решения задачи к реальной стоимости: .

Функция стоимости  не убывает, и , поэтому ресурсная эффективность не превосходит единицы: .

Средняя стоимость использования  системы и вычислителя  к моменту t определяются соотношениями , fi(t)=Fi(t)/t= =ciri(t).

Отсюда следует, что средняя стоимость fi(t) не может превышать удельную стоимость ci:

.

Следующее соотношение устанавливает связь между эффективностью по времени E и ресурсной эффективностью :

.

Вкладом ki(t) вычислителя i в стоимость использования назовем отношение средней стоимости использования вычислителя к средней стоимости использования системы:

.

Введем понятие, которое аналогично коэффициенту ускорения в традиционной модели производительности. Удешевлением вычислений системы по отношению к вычислителю i назовем отношение стоимости эталонного решения на вычислителе i к действительной стоимости решения в системе:

, .

Для ресурсной эффективности справедливо соотношение, аналогичное (7):

.

Рассчитаем ресурсную эффективность системы в приведенном примере. Будем полагать удельную стоимость вычислений равной эталонной производительности c1=p1. При первом запуске . Эталонное время решения для второго запуска , отношение средней стоимости за эталонное время к средней стоимости за реальное время составляет: .

Поэтому ресурсная эффективность во втором случае  и совпадает с ресурсной эффективностью для первого запуска.

Величина  – это коэффициент формы расписания. Форма расписания характеризует распределение стоимости вычислений относительно эталонного и реального времени решения задачи. Эффективность по времени может быть рассчитана как отношение ресурсной эффективности, не зависящей от расписания, к коэффициенту формы расписания: .

В приведенном примере во втором случае использовалось расписание с растущей стоимостью, или, для краткости, растущее расписание, в котором суммарная стоимость вычислений при  больше стоимости вычислений на промежутке . Для растущего расписания Q<1 и ресурсная эффективность  меньше эффективности по времени E. Примером расписания с убывающей стоимостью может служить расписание для системы из двух вычислителей, которые сначала при  работают вместе, а на интервале  работает только второй вычислитель. Для убывающего расписания Q>1 и ресурсная эффективность больше эффективности по времени.

Если все вычислители системы доступны на протяжении всего времени решения задачи, то Q=1, следовательно, ресурсная эффективность и эффективность по времени совпадают. Обратное неверно, то есть из того, что Q=1, не следует, что в системе с расписанием вычислители доступны на протяжении всего времени решения. Например, для распределенной системы, работающей с эффективностью 1, ресурсная эффективность и эффективность также совпадают и коэффициент формы расписания равен 1.

  Эталонная система для задач с последовательной частью

Рассмотрим возможность применения модели систем с расписанием к неоднородным вычислительным системам. Обычно под неоднородной системой понимают совокупность неодинаковых вычислителей. В качестве примера неоднородной системы можно привести сеть рабочих станций, объединенных локальной сетью и используемых в монопольном режиме.

Другим примером неоднородной системы может служить совокупность центрального процессора и графического ускорителя рабочей станции. Распределенная система, включающая несколько вычислительных кластеров на некотором промежутке времени, когда состав системы постоянен, также будет неоднородной системой. Одним из подходов к описанию производительности неоднородных систем является модель системы функциональных устройств [2].

Рассмотрим неоднородную систему как частный случай системы с расписанием и построим эталонную систему для оценки характеристик производительности системы при решении задач с последовательной частью.

Представим класс Аb задач с последовательной и параллельной частями. Пусть для каждой задачи A доля последовательных вычислений составляет b. Для решения последовательной части может использоваться только один вычислитель. Для оценки производительности неоднородных систем применим подход, использованный в модели систем с расписанием, и построим эталонную систему  для решения задач класса Аb. Будем полагать, что параллельная часть является произвольно делимой на подзадачи, выполняемые параллельно на произвольном количестве вычислителей, при этом трудоемкость L остается постоянной. Накладные расходы, связанные с распараллеливанием, и эффекты сверхлинейного ускорения в эталонной системе отсутствуют.

Для неоднородных систем сформулируем утверждение, аналогичное известному закону Амдала для однородных систем. Для расчета характеристик производительности системы  воспользуемся эталонной системой с расписанием .

Утверждение. Пусть в системе  последовательная часть задачи была решена на вычислителе s, тогда для эффективности E* и коэффициентов ускорения  справедливы соотношения , .

Так как время решения T задачи эталонной системой  не превосходит времени решения системой Â, Tb£T, справедливо следующее.

Следствие (закон Амдала). Пусть вычислители неоднородной системы  упорядочены по убыванию эталонной производительности p1³ p2³…³pn, тогда справедливы соотношения , .

Оценим характеристики производительности Eb и  системы Â по отношению к эталонной системе , из соотношений (5) и (6) получим Eb=E/E*, .

В итоге следует отметить, что в работе предложен подход к количественной оценке характеристик производительности приложений, работающих в распределенной вычислительной среде. Обобщены традиционные для параллельных систем понятия ускорения и эффективности, выведены различные соотношения, связывающие эти величины с расписанием работы вычислительных узлов и их производительностью. Для неоднородных систем, в которых все узлы работают на протяжении всего времени расчета, получены выражения для максимальной эффективности и ускорения, аналогичные закону Амдала. Практическая ценность предложенного подхода была продемонстрирована на примере расчетов энергетически оптимальных конфигураций молекулярных кластеров, проведенных в вычислительной среде, состоящей из нескольких суперкомпьютеров [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.