автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Оценка производительности распределенных вычислительных комплексов на основе модели эталонных систем

На правах рукописи /Л./7

Уй

6 У

Хританков Антон Сергеевич

ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ НА ОСНОВЕ МОДЕЛИ ЭТАЛОННЫХ СИСТЕМ

Специальность 05.13.01 «Системный анализ, управление и обработка информации» (информационно-вычислительное обеспечение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

ЗАПР,

'0:0

МОСКВА-2010

004601723

Работа выполнена на кафедре управления развитием высоких и инновационных технологий Московского физико-технического института (государственного

университета)

доктор физико-математических наук, профессор Афанасьев Александр Петрович

доктор технических наук, профессор Бухановский Александр Валерьевич

кандидат физико-математических наук Усков Анатолий Васильевич

Учреждение Российской академии наук Институт прикладной математики им. М.В. Келдыша РАН

Защита состоится « 17 » мая 2010 года в 11 часов на заседании диссертационного совета Д-002.086.02 в Учреждении Российской академии наук Институте системного анализа РАН по адресу: 117312, Москва, проспект 60-летия Октября, 9.

С диссертацией можно ознакомиться в библиотеке Учреждении Российской академии наук Институте системного анализа РАН по адресу: (Москва, проспект 60-летия Октября, 9)

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 117312, Москва, проспект 60-летия Октября, 9, диссертационный совет Д-002.086.02.

Автореферат разослан « 16 » апреля 2010 г.

Ученый секретарь диссертационного совета Д.002.086.02 доктор технических наук, профессор А.И. Пропой

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Распределенные вычисления и Грид-технологии применяются для решения многих сложных вычислительных задач науки и техники, которые не могут быть решены за приемлемое время на однопроцессорной рабочей станции или даже в рамках одного многопроцессорного вычислительного комплекса. Однако, применение распределенных вычислительных комплексов (РВК) и Грид-систем осложняется тем, что они имеют неоднородную структуру вычислительного пространства, которая может изменяться с течением времени и не допускает централизованного управления всеми аспектами процесса решения задачи, то есть являются сложными неоднородными системами.

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

Цели и задачи работы. Целями настоящей работы являются:

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

• Разработка универсального подхода к решению задачи оценки производительности распределенных вычислительных комплексов. При этом подход должен быть применим также к многопроцессорным и мультикластерным комплексам. Определение и формулировка количественных характеристик производительности.

• Применение разработанного подхода к анализу производительности при решении декомпозируемых задач на мультикластерных вычисли-

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

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

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

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

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

Подход был разработан в виде совокупности моделей, характеристик производительности и методики применения. Процедуры расчета характеристик были реализованы в программном комплексе, примененном к анализу нескольких распределенных вычислительных систем. Таким образом, предлагаемый под-

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

Методы исследования. В данной диссертационной работе используются методы математического моделирования и системного анализа, методы оптимизации, математической статистики и теории вероятностей, анализа производительности параллельных вычислительных комплексов. При разработке программного комплекса использованы современные методы инженер™ программного обеспечения с использованием средств UML, языка программирования Java и промежуточного программного обеспечения Ice .

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

Предложенные методы и разработанный комплекс программ были применены для анализа нескольких РВК.

Апробация работы. Результаты диссертации и материалы исследований докладывались, обсуждались и получили одобрение специалистов на: 24-ой «Международной конференции по суперкомпьютерам» (Гамбург, Германия, 2009); X и XI Всероссийских научных конференциях «Научный сервис в сети Интернет» (Новороссийск, 2008, 2009); III и IV Международных научно-практических конференциях «Современные информационные технологии и ИТ-образование» (Москва, 2008, 2009); III Международной научной конференции «Параллельные вычислительные технологии» (Нижний Новгород, 2009); 50, 51 и 52-ой научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2007, 2008, 2009); 17-ой Международной научной конференции «Математика. Компьютер. Образование» (Дубна, 2010); II сессии научной школы-практикума «Технологии вы-

сокопроизводительных вычислений и компьютерного моделирования» в рамках VI Всероссийской межвузовской конференции молодых ученых Санкт-Петербургского государственного университета, Института точной механики и оптики (Санкт-Петербург, 2009); научных семинарах кафедры прикладной математики и моделирования систем Московского государственного университета печати.

По материалам работы опубликовано 14 печатных работ, пять из них в изданиях из списка ВАК [1,2,3,7,11].

Структура и объем работы. Общий объем диссертации включает 148 страниц. Работа состоит из введения, пяти глав, заключения, списка литературы (89 наименований).

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В ПЕРВОЙ ГЛАВЕ анализируется состояние исследований в области анализа производительности распределенных вычислительных комплексов. Произведен аналитический обзор моделей процесса решения отдельной задачи, применимых для анализа производительности распределенных и параллельных вычислительных комплексов. Подробно рассмотрены модели однородной вычислительной системы, функциональных устройств и сети рабочих станций, имеющие непосредственное отношение к тематике работы. В результате анализа было обнаружено, что для распределенных систем отсутствует целостный подход к оценке производительности и лишь небольшое количество моделей применимы для описания процесса решения (одна модель), в то время как большая часть работ посвящена анализу неоднородных систем. Была исследована возможность развития и обобщения применяемых для однородных систем

подходов для распределенных систем, в результате были сформулированы требования к моделям процесса решения и выработана постановка задачи оценки производительности РВК.

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

задачи А одним элементом системы; и коэффициента эффективности Е, определяемого как отношение коэффициента ускорения к количеству элементов п системы: 51 = 7]1Т, Е = 5/и. При этом справедлив закон Амдапа для параллельного ускорения в случае, когда доля (3 вычислений при решении задачи должна быть проведена на одном элементе последовательно, 5<(Р + (1-Р)/пГ-

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

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

определяется как отношение времени решения задачи наиболее «быстрым» с точки зрения используемого понятия производительности элементом системы ко времени решения задачи всей системой. В моделях сетей неодинаковых процессоров (heterogeneous computing network) неоднородность учитывается указанием вектора времен решения элементами всей задачи, либо матрицей решения элементами каждой из частей задачи. В последнем случае, при сильной неоднородности системы, показывается, что коэффициент ускорения не ограничен сверху в отсутствие- каких-либо ограничений на неоднородность системы. Основная идея экономических моделей эффективного управления процессом решения состоит в рассмотрении пользователей и владельцев ресурсов как участников рынка, максимизирующих свою «полезность». Понятия эффективности и ускорения напрямую обычно не вводятся.

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

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

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

применим к различным классам распределенных комплексов, в том числе муль-тикластерным и многопроцессорным вычислительным кластерам.

Для решения задачи разработан подход эталонных систем, который заключается в выделении моделей двух уровней: модели системы, описывающей процесс решения задачи на комплексе и указывающей измеряемые параметры, и эталонной модели, позволяющей рассчитать время решения задачи на основе параметров модели системы. Далее делается вывод о необходимости создания новых моделей систем и эталонных моделей. Модели должны быть применимы для различных классов распределенных комплексов и позволять учитывать их особенности, быть сводимыми к общепринятым моделям в частных случаях.

ВТОРАЯ ГЛАВА посвящена разработанным в рамках подхода эталонных систем линейным моделям процесса решения задач на распределенных вычислительных комплексах, для которых известно, в какие моменты времени для решения задачи использовались элементы системы. Показано, что предлагаемая модель, называемая системой с расписанием, в совокупности с линейной эталонной моделью, является обобщением модели для однородных систем на распределенные вычислительные системы.

В модели систем с расписанием элементы называются вычислителями. Доступность вычислителя г описывается при помощи функции расписания А, (0—> {0,1}. При этом АД/) = 1, если вычислитель доступен для системы, и А;(/) = 0 в противном случае. Количественная характеристика доступности вводится как доля времени, в течение которой вычислитель был предоставлен для решения задачи, р,(0 = СОЛ, р,(г) < 1. Для описания различной производительности вычислителей используется время решения всей задачи выбираемым в зависимости от целей анализа эталонным алгоритмом, который может быть как последовательным, так и параллельным.

Для описания возможного изменения размера задачи при переходе к параллельному решению или при делении задачи на части, вводится понятие трудоемкости Ь(А) решения задачи. При этом трудоемкость понимается как функция /.(■), определенная для класса задач А и указывающая способ расчета значения трудоемкости для каждой задачи класса, например, как количество опе-

раций в эталонном алгоритме решения задачи в выбранной модели вычислений. Эталонной производительностью называется отношение щ(А) = L(A)/TI(A). Временем решения Т задачи А называется величина Т = max,v {/¡ДО > 0}.

Определение 1. Вычислительной системой с расписанием R{A) для решения задачи А называется совокупность /г(-) и л {A), R(A) =< h(-),Ti(A)>.

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

Определение 2. Эталонной моделью 9Í(A) системы с расписанием будем называть модель системы с расписанием 9?(Л), которая позволяет рассчитать время решения произвольной задачи А из класса А на данной системе.

Линейная эталонная модель. Построим линейную эталонную модель R, сравнение с которой позволит количественно оценить величину накладных расходов, связанных с распараллеливанием решения задачи. Модель R состоит из вычислителей системы R, работающих по тому же расписанию h(-) и обладающих такой же эталонной производительностью тс(А). В модели R отсутствуют накладные расходы, связанные с распараллеливанием, не проявляются эффекты сверхлинейного ускорения, и задача полагается произвольно делимой в указанном ранее смысле.

Эталонное время решения Т задачи в модели R определяется как решение задачи оптимизации, имеющей не более одного решения:

min/, при условии

г "

\n(x)di = L(A), где 7i(t) = £тсА(т).

о н

Величина 7l(t) называется эталонной производительностью системы R.

Для описания распределения расчетов между вычислителями системы в процессе решения задачи используется понятие части задачи. Частью а задачи А при решении на системе R(A) будем называть долю расчетов, проведенных

системой или вычислителем в некотором промежутке времени, длительность которого обозначим t(a). В линейной эталонной модели можно рассчитать долю трудоемкости /(а ), соответствующую части задачи д, решенной вычислителем i, ¡(а) = ht(t)dí, ЦА) = ■ Часть а задачи А называется делимой, если существует система R(A), в которой часть а делится на части <з , при этом вычислитель i решает часть а, и выполняется равенство 1(a) = > 1(а,) > 0. В противном случае, часть называется неделимой.

Линейная эталонная модель R(Á) является линейной в том смысле, что для каждого расписания h(í) выполняется /(а,) = я,р,(7*)Г = n,í„ где /, = t(a. ) = р .(Т)-Т - время решения вычислителем i части а,.

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

Коэффициентом эффективности по времени Е системы R называется отношение эталонного времени решения Т к действительному времени решения задачи Т, Е = Т/Т.

Коэффициентом ускорения S: системы R по отношению к вычислителю i называется отношение эталонного времени решения вычислителя Т: к действительному времени решения Т, S,=T¡JT.

Утверждение 1. Коэффициент эффективности Е системы R по отношению к модели R(A) выражается формулой Е = р, (Г) / ) .

Для оценки количества использованных ресурсов зададим удельную стоимость с, > 0 использования вычислителя i в единицу времени. Стоимость использования Ф(/) системы R к моменту времени t складывается только из стоимостей использования Ф,(() вычислителей и рассчитывается по формулам:

Коэффициентом ресурсной (стоимостной) эффективности системы R, или ресурсной эффективностью, называется отношение Е( = Ф(Т)/Ф(Т).

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

Определение 3. Неоднородной вычислительной системой Rназывается система с расписанием R, в которой k{t) = 1 при /е [О,Г]. Однородной вычислительной системой R называется неоднородная вычислительная система, в которой л. = Tíj для всех i Ф j.

Для неоднородных систем доступность р.(/) = 1, поэтому Е^= Е. Утверждение 1 для неоднородных и однородных систем будет иметь вид, соответственно: Ек =(¿,",,1 /S¡f , Ер — ~S!n. Для однородных систем все элементы вектора ускорения равны, их значение совпадает с традиционным определением коэффициента ускорения S = max(. S¡ = S,.

Закон Амдала для задач с последовательной частью. В разделе 2.2.3 построена модель процесса решения класса Af задач с последовательной и параллельной частями, в котором каждая задача А для всех систем Rha является делимой на части а, и ар, при этом L(A) = l(al)+l(af), ¡(at) = f>L(A). Последовательная часть а, является неделимой, параллельная часть ар является делимой для всех Rk¡, поэтому Т(А) = í (а,) + í (ар).

Эталонная модель /?&„(Ар), позволяющая оценить производительность неоднородных систем при решении задач класса Ар, отличается от R только другой моделью структуры задачи А и тем, что все вычислители доступны все время решения.

Утверждение 2. (закон Амдала для неоднородных систем) Пусть вычислители неоднородной системы Rупорядочены по убыванию эталонной производительности п] >тс, >...> ка, тогда по отношению к модели R( А) справедливы соотношения:

ТРЕТЬЯ ГЛАВА посвящена моделированию процесса решения декомпозируемых задач на распределенных вычислительных комплексах. Вводится определение декомпозируемой задачи, разработана интервальная модель процесса решения задачи. Предложен оптимальный алгоритм управления вычислениями линейной сложности. Кроме того, разработана более общая интервальная модель для задач переменного размера. Предложен экспериментальный метод оценки трудоемкости решения задачи переменного размера и получены оценки его точности. Модель применена для анализа производительности комплекса ВпВ-Грид.

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

Определение 4. Вычислительная задача А называется декомпозируемой на М подзадач , являющихся задачами, если для решения задачи А необходимо решить все подзадачи. При этом ¿(А) — ЦА^.

Предлагаемое определение описывает широкий класс задач, в том числе задачи глобальной оптимизации, решаемые методами типа Монте-Карло.

Модель интервальных систем. Интервальная система Кк{Ам) для решения декомпозируемых задач - это система с расписанием из я вычислителей, каждый из которых принадлежит одному из кластеров Рк из множества кластеров Р, к = \..К, по пк> 0 в кластере Ру, при этом Щ(А) = лу(Л), ЛД0 = ^/(0> г, _/' е Рк. Кластеры, в отличие от вычислителей, доступны для решения задачи на протяжении не более одного интервала времени, что обуславливает название системы. Подзадачи передаются на кластер пакетами для решения вычислителями. Следующий пакет передается кластеру после окончания решения предыдущего пакета.

Определение 5. Интервальной системой RK{AU) называется совокупность ЯЛЛЛ =<£(•),й(Л),й,Л/>, при Л1(А) = Л1(А), Л (/) = А ДО, /, j е и указанных выше ограничениях.

Пусть имеется задача Адекомпозируемая на несколько подзадач j-\..M одинаковой трудоемкости L(Aj) = а. Построим эталонную интервальную модель йк.„(A„ J для решения задач класса А„о. Будем полагать, что каждому вычислителю назначается не более одной подзадачи, которую он решает последовательно, независимо от других вычислителей. Эталонным временем решения Т называется минимальное по всем возможным назначениям пакетов кластерам время завершения решения всех подзадач. Этапом решения вычислителя будем называть промежуток времени решения подзадачи в пакете, этапы решения вычислителей одного кластера имеют одинаковую продолжительность. Перенумеруем все этапы всех вычислителей всех кластеров и обозначим время завершения решения этапа через t,, i = \..Mj. Пусть s, =1, если на данный этап назначен пакет, и st = 0 иначе. Задача нахождения эталонного времени решения и распределения подзадач по этапам решения вычислителей имеет вид:

и,

minmaxs:t,, ^st>M, se {0,1}"'. (А)

* ' ы

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

тахХ^,2*,<Л/,*б{0Д}м'. (В)

' ы f 1=\

Утверждение 3. Пусть времена окончания этапов вычислителей упорядочены г, > tp i> j, i' = l.М,, j = 1 ..Mj. Тогда справедливы утверждения.

1) Для того чтобы задача (А) имела решение необходимо и достаточно, чтобы Mj>M.

2) При Mj>M множества решений задач (А) и (В) совпадают.

3) Задача (В) имеет решение s' =(1,..1,0,..0), где s' =1, i-\..M.

Пусть /1} - количество задач, назначенных для решения на этапе у кластера к, к-\..К, у = 1.^, 0<<ск. Для нахождения / предложен алгоритм 1, основанный на решении задачи (В). Сложность алгоритма составляет 0(М,). На основе распределения подзадач flj предложен динамический алгоритм 2. балансировки и управления вычислительным пространством без обратной связи.

Структурной неэффективностью АЕ = 1 - Е называется снижение эффективности системы вследствие невозможности управления отдельными ее элементами.

Утверждение 4 (о структурной неэффективности). Эффективность Ер интервальной модели Як.?, в которой только рк < пк вычислителей кластера решают подзадачи, по отношению к линейной эталонной модели К лежит в пределах

\\-^ЛЪг<ЬЕ +АЕ <^,АЕ =1 -Е , АЕ =1 -Е ,

I п I у ' Р' у ' Р Р ' Р» Рп '

V « у р р

где Е - эффективность модели /?*г,Р(АМа) по отношению к модели Л*,* (А,,о), - количество подзадач в пакете, назначенном на последнем этапе решения в модели Лд>, п1 — число вычислителей в кластере, решавшем данный пакет задач, хс - продолжительность этапа решения вычислителей кластера, Тр — эталонное время решения задачи в модели Як.Р.

Интервальная модель для задач переменной трудоемкости. Расширим интервальную модель Ллг,.(АМо) для описания решения класса АЛ/Рг декомпозируемых задач с переменной трудоемкостью. Обозначим такую модель Лг,»(АМРг), в дополнение к условиям модели Ик,»(Аиа), предполагается, что независимые в совокупности случайные величины, на вычислитель может назначаться несколько подзадач пакета. Рассмотрим модель отдельного кластера Рт из р вычислителей модели Лк,„.(АМ Рг) как эталонную модель для решения одного пакета подзадач размера М =т-р. На кластере применяется

алгоритм балансировки, который направляет по т подзадач на каждый вычислитель. Причиной структурной неэффективности является то, что подзадачи имеют разную трудоемкость, и вычислители, завершившие последовательный расчет т подзадач, будут простаивать. При больших М, так как = ^Г^ Ц, распределение Ь можно полагать приближенно нормальным М(А/Ц, Мг), где цио1- математическое ожидание и дисперсия .

Пусть Х1 - случайная величина, выражающая суммарную стоимость решения т подзадач на вычислителе ( кластера, со средним значением цт и дисперсией о*. Пусть Д = тах Х1 - X,, в результате аппроксимации была получе-

Ы1.-Р

на эмпирическая зависимость ЕА, = а 1пр■ <ТЯ, а^-т-с2. Положим для вычислителей из одного кластера с., = с0 = сг / р. Обозначим С = а0, где 9 - коэффициент вариации. Долю ер стоимости вычислений, затраченных на решение подзадач, можно в среднем оценить как

ЕЕр~[1 + С(р-\)\пр14Мр)\ По построению, величина гр является оценкой сверху ресурсной эффективности эталонной модели Рт по отношению к линейной модели Я, усредненной по различным трудоемкостям подзадач. Также получена функция изоэффек-тивности вида М = ,Р(/>,£0), указывающая, сколько подзадач должно быть в пакете, чтобы эффективность системы составила е0 при р вычислителях в кластере, Р(р,Е0) = С3(еа/(1-е0))2р1п2р.

В модели имеется К кластеров, долю кластера к в полной стои-

мости решения задачи обозначим через >0, ^ = 1. Ресурсная эффективность Е^ всей системы составит Е^ > гЯе К ~ ресурсная эффективность кластера к.

Метод экспериментальной оценки трудоемкости решения задач класса АМ Рг состоит в последовательном решении ограниченного набора N«М подзадач, измерения трудоемкости их решения и оценки параметров распределения трудоемкости подзадач. После этого, используя предположение о нор-

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

Относительная погрешность в определении ресурсной эффективности равна точности определения трудоемкости. Доя среднего и дисперсии используются оценки т„ = / N и = , - т)1 /{И -1). Тогда оценки среднего значения = М ■ и стандартного отклонения ог=М-хк для трудоемкости всей задачи . Рассматривается центральный доверительный интервал вида '«л гае ¿а? =Е(111 +аа^ + (3/0(ц7+аоЗ. Обозначим коэффи-

циент эксцесса к, коэффициент корреляции между оценками среднего и дисперсии р. При N ~ 4м, а = 1, Р = 1, выражение для Ьар имеет вид:

А, =Аф-9

г\ 1 -/к+6 р - + -== +—¡=- + —

К+2+0( 1/^)1.

-/М 2 -/¿V Ы\к+6 В эксперименте наблюдались значения Кб [2;4], 8е [0,3;0,5], значит, по порядку величины, при N = 25: /,, ~ [0,85 • Мтх; 1,15 - Миу ].

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

Применение модели интервальных систем. Для комплекса ВпВ-Грид при выделении пяти модельных кластеров на МВС-100К в силу схемы управления вычислителями количество задач в пакете составляет М = р. Результаты экспериментов, рассчитанные значения ресурсной эффективности и полученные функции оценок приведены на рис. 1. Полученная модель оценивает эффективность сверху, отклонения экспериментальных данных при ре {7,..12} объясня-

ются простоем вычислителей кластера при недостатке подзадач. При этом определение трудоемкости по выборке размера с погрешностью около 15% (границы интервала показаны пунктиром) позволило бы обнаружить данное снижение эффективности. Погрешность оценки трудоемкости при

Рис. 1.Опенка ресурсной эффективности Е^ комплекса ВпВ-Грнд в зависимости от количества вычислителей р в кластере.

В ЧЕТВЕРТОЙ ГЛАВЕ разработанные в рамках подхода эталонных систем модели рассматриваются в совокупности, с точки зрения связей и отношений между ними. В результате сформулирована методика анализа производительности с помощью подхода эталонных систем.

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

Таблица 1. Перечень разработанных моделей с кратким описанием

Модель Описание

ЩА) Система с расписанием

ВД Линейная модель для систем с расписанием в предположении о произвольно делимой задаче

КХА) Неоднородная система как частный случай систем с расписанием

КМ) Однородная система как частный случай неоднородной

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

Интервальная система, состоящая из кластеров вычислителей, на которые задачи назначаются последовательно решаемьми пакетами

Модель интервальной системы для подзадач одинаковой трудоемкости

йкДА^) Модель интервальной системы для подзадач переменной трудоемкости

Отношения между моделями приведены на рис. 2.

—^ Я(А)

«„(Л)

I

Д*.„(А>/Р1)

Системы с расписанием / дд^ )

Интервальные системы

->

Обобщение

Модель системы

Эталонная модель

Рис. 2. Отношения между моделями в подходе эталонных систем.

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

В ПЯТОЙ ГЛАВЕ приводится описание комплекса программ, реализующего разработанные модели и подключаемого к вычислительной инфраструктуре ВпВ-Грид, представлены результаты исследования производительности различных РВК. В экспериментах с использованием ВпВ-Грид показана применимость подхода для анализа производительности. Анализ производительности комплекса НРС-ЫАЗГБ демонстрирует применение параллельного алгоритма в качестве эталонного. В результате анализа системы метакомпьютинга Х-Сош2 были сформулированы принципы управления процессом решения задачи, которые бы позволили увеличить эффективность использования ресурсов. При ана-

лизе производительности среды CAS Maxima Desktop Grid демонстрируется применение обобщения закона Амдала для неоднородных вычислительных систем.

Программный компонент управления процессом решения задачи bnb-balancer предоставляет инструментарий по выработке решений по управлению процессом вычислений: построению вычислительного пространства, распределению нагрузки и сбору информации о процессе решения задачи. Компонент используется в вычислительной инфраструктуре BnB-Грид для выработки решений по управлению вычислительным пространством. Компонент включает следующие программные модули:

• Управления и балансировки нагрузки (balancer);

• Ведения журнала работы системы и сбора данных (stats);

• Анализа и расчета характеристик производительности (analyzer).

Программный модуль управления balancer основан на интервальной модели,

что подразумевает решение декомпозируемой задач, и предоставляет интерфейс прикладного программирования (API) для управления процессом вычислений в рамках данной модели.

Анализ производительности ВпВ-Грид. Для вычислительного эксперимента была выбрана известная задача нахождения расположения атомов в кластере с минимальной потенциальной энергией. В начале вычислений алгоритмом Multistart формировался пул подзадач из 24 случайных стартовых точек для алгоритма монотонного спуска из произвольной точки окрестности (MBH). Для проведения экспериментов использовались ресурсы МВС-100К, MBC-6000IM, кластера Тамбовского государственного технического университета и рабочая станция DCS. Для анализа использована линейная эталонная модель, результаты приведены в таблице 1, на их основе сделан вывод о применимости модели систем с расписанием к оценке производительности распределенных вычислительных комплексов.

№ Конфигурация Количество кластеров Всего ядер Е т, с

1 ОСЙ, ТГТУ, МВС-ЮОК, МВС-60001М 6 17 0,58 0,54 420

2 МВС-ЮОК, МВС-60001М 4 12 0,72 0,79 358

3 МВС-ЮОК 2 6 0,71 0,75 636

4 МВС-60001М 2 6 0,86 0,81 2218

5 ТГТУ 1 4 0,75 0,75 2319

6 БСБ 1 1 1 1 7342

Анализ производительности НРС-КАБК. Программный комплекс НРС-NASIS, разрабатываемый в СПбГУ ИТМО, предназначен для проведения кван-тово-механических расчетов, компьютерного моделирования, расчета наноструктур и наноматериалов с заданными свойствами в различных условиях эксплуатации. Входные данные для оценки получены из журнала программного комплекса НРС-ЫАЗК в эксперименте по расчету транспортных свойств на-нотрубок. На первом этапе было решено 7 задач из 10 шагов алгоритма на кластере из 16 ядер, на втором этапе те же задачи были решены как совокупная задача на кластере из 80 ядер. Время, затраченное на организацию вычислений, передачу входных данных и результатов, в каждом случае составляет Г, = 51 ±2 секунды.

Для анализа использовалась линейная эталонная модель, дополненная ограничениями, что в состав вычислительного пространства входит 5 модельных последовательных вычислителей, сопоставленных кластерам из 16 ядер (в сумме 80), доступным через время ожидания Те на неограниченное время. Эталонное время составило Т-Тв + Т ~ 93 с.

При с, = 1 эффективность и ресурсная эффективность составили, соответственно: = 96%, = 95%. Можно сделать вывод, что решение частей декомпозируемой задачи на кластере из 16 ядер было бы так же эффективно, как и решение частей данной задачи на кластере из 80 ядер.

Анализ производительности Х-Сот2. Целью анализа было понять, каким образом можно было бы повысить эффективность использования вычислительных ресурсов для решения задачи докинга протеин-лиганд. Система метаком-пьютинга Х-Сот2 разрабатывается в НИВЦ МГУ. Система построена по иерар-

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

Входные данные получены из журнала работы системы. В эксперименте было решено 5217 подзадач на более чем 1600 ядрах вычислительных кластеров Скиф-МГУ, Скиф-Урал и кластера НКС-160. Для анализа была использована системы с расписанием и линейная эталонная модель. Вычислителям системы были сопоставлены экземпляры программы SOL, расположенные на узлах и непосредственно решающие подзадачи. Наряду с используемой схемой Rdmr выделения ресурсов сразу на всем кластере на промежуток времени, была рассмотрена оптимальная, согласно линейной эталонной системе, схема реализующая управление каждым вычислителем в отдельности.

Значения эффективностей систем Rc¡Uf¡, и ^„ajg по отношению к линеиным эталонным моделям Rdu.« и Rwb приведены в таблице 3. Системы используют разные расписания, поэтому значения ресурсных эффективностей отличаются при тех же значениях эффективности по времени Е.

Отношение ресурсной эффективности системы Rcbl¡ к эффективности системы Я^ь показывает, насколько меньше вычислительных ресурсов использует система R^, чем система Rch¡l, то есть на 68% в данном случае. Приблизиться к указанному сокращению использованных ресурсов получилось бы, если узлы выделялись бы согласно эмпирическим правилам, изложенным в разделе 5.3.3, суть которых сводится к управлению отдельными вычислителями при помощи системы пакетной обработки и избеганию принудительного завершения решения подзадач.

Таблица 3. Эффективность при использовании различных схем управления

Схема управления Т Т Е

по кластерам 16,3 часа 47,8 часов 0,34 0,45

R«a по узлам 16,3 часа 47,8 часов 0,35 0,66

Анализ производительности CAS Maxima Desktop Grid. Система представляет собой вычислительную среду, сформированную из сервисов удаленного доступа к системам компьютерной алгебры Maxima. Производительность среды была оценена на основе предоставленных разработчиками данных вы-

числительного эксперимента по обращению матриц Гильберта с помощью Ш-разложения и параллельного вычисления столбцов обратной матрицы на узлах {та, уу,ю-,у/,/я} .

Для анализа применена эталонная модель Д/,»(Ар), параметр (3 был рассчитан на основе данных о долях длительности решения частей в последовательном режиме для каждой размерности задачи. В таблице 4 приведены результаты расчета характеристик производительности для различного размера матриц N по сравнению с моделью Коэффициент Е' показывает эффектив-

ность модели Л*«(Аг) по отношению к линейной эталонной модели Я. Полученные количественные значения ускорения и эффективности подтвердили качественные ожидания.

Таблица 4. Результаты оценки производительности системы CAS Maxima Desktop Grid

N Т, с т mo+v» ' ® Р Е Е' s. S,

100 14,173 15,55 0,341 0,78 0,260 1,91 1,89 3,23 3,14 3,70

150 53,563 59,06 0,335 0,83 0,277 2,02 2,29 3,68 3,89 4,00

200 153,124 168,3 0,335 0,92 0,263 2,20 2,40 3,70 4,02 4,22

250 360,421 389,8 0,364 0,956 0,263 2,18 2,29 3,73 4,20 6,87

300 734,156 795,8 0,360 0,96 0,262 2,36 2,28 3,73 4,31 6,84

Для сравнения был рассмотрен вариант решения задачи с использованием

только вычислителей двух узлов та и уу. Экспериментально полученное время решения задачи при N = 300 составляет Т^т~Н02, что отличается от рассчитанного на основе обобщения закона Амдала значения Т^^ = 795,8 на 1%.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3) Для описания процесса решения важного с прикладной точки зрения класса декомпозируемых задач разработана эталонная модель, в рамках которой разработан алгоритм управления процессом вычислений, минимизирующий время решения, и получены оценки структурной неэффективности. Модель также обобщена на случай декомпозируемых задач переменного размера, таких как задачи глобальной оптимизации решаемые методами типа Монте-Карло. Получены новые аналитические выражения для эффективности в зависимости от конфигурации вычислительного пространства, а также функция изоэффективности. Предложен экспериментальный метод оценки трудоемкости решения декомпозируемых задач переменного размера по небольшому набору подзадач и получены оценки точности данного метода. Применимость модели и метода для анализа производительности показана на примере вычислительной инфраструктуры ВпВ-Грид.

4) Разработан комплекс программ, реализующий линейную эталонную модель и позволяющий рассчитывать значения характеристик производительности. Сформулирована схема применения разработанных методов оценки производительности и комплекса программ, которая была успешно применена к анализу производительности вычислительной инфраструктуры ВпВ-Грид, вычислительного комплекса HPC-NASIS, распределенной системы CAS Maxima Desktop Grid и системы метакомпьютин-га Х-Сош2.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Хританков A.C. Модели и алгоритмы распределения нагрузки. Алгоритмы на основе сетей СМО // Информационные технологии и вычислительные системы. -2009. -№ 3. - с. 33-48.

2. Хританков A.C. Модели и алгоритмы балансировки нагрузки. Модели коллектива вычислителей. Модели с соперником // Информационные технологии и вычислительные системы. - 2009. - № 2. - с. 65-80.

3. Афанасьев А.П., Посыпкин М.А., Хританков A.C. Аналитическая модель оценки производительности распределенных систем // Программные продукты и системы. - 2009. - № 4. - с. 60-64.

4. Хританков A.C. Математическая модель характеристик производительности распределенных вычислительных систем // Труды 50-й научной конференции МФТИ. - 2007. - с. 86-88.

5. Хританков A.C. Оценка характеристик производительности распределенных вычислительных систем // Труды XV Научной конференции студентов, аспирантов и молодых ученых «Ломоносов». - 2008. - с. 53-54.

6. Посыпкин М.А., Хританков A.C. О понятии ускорения и эффективности в распределенных системах // Труды Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач». - 2008. - с. 149-155.

7. Посыпкин М.А., Хританков A.C. О понятии производительности в распределенных вычислительных системах П Труды ИСА РАН. - 2008. - Т. 32.-с. 26-32.

8. Хританков A.C. Об одном алгоритме балансировки вычислительной нагрузки в распределенных системах // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Новгород, 30 марта - 3 апреля 2009 г.). - Челябинск: Изд. ЮУрГУ, 2009. - 839 с. - с. 778-783.

9. Хританков A.C. О характеристиках производительности распределенных систем // Труды 51-ой научной конференции МФТИ. - 2008.

ЮХританков A.C. Оценка эффективности распределённых систем при решении задач переменного размера // Труды 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть IX. Инновации и высокие технологии. - 2009. - с. 32-35.

11 .Хританков A.C. Оценка эффективности распределенных систем при решении задач переменного размера. // Научно-технический вестник СПбГУ ИТМО. - 2010. - № 2(66). - с. 66-71.

12.Хританков A.C. Анализ производительности распределенных вычислительных комплексов на примере системы X-Com // Труды Всероссийской суперкомпьютерной конференции "Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность (г. Новороссийск, 2126 сентября 2009 г.). - 2009. - с. 46-52.

ХЪХританков A.C. Анализ эффективности системы метакомпьютинга X-Сот в эксперименте по докингу протеин-лиганд // Труды Третьей Международной научно-практической конференции "Современные информационные технологии и ИТ-образование" (Москва, 6-9 декабря 2008 г.). -М.: МАКС ПРЕСС, 2008. - с. 799-806.

\ А Хританков A.C. Анализ эффективности распределенного решения некоторых видов задач глобальной оптимизации // Тезисы докладов 17-ой Международной научной конференции «Математика. Компьютер. Образование» (25-30 января 2010). - Ижевск: РХД, 2010. - с. 190.

Подписано в печать:

15.04.2010

Заказ № 3562 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 И 5230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autorefera.tru

Введение

Цели и задачи работы

Научная новизна

Методы исследования

Практическая ценность работы

Апробация работы

Структура работы

Благодарности

Глава 1. Модели производительности распределенных вычислительных комплексов

1.1. Модель однородной вычислительной системы без структуры

1.2. Модель коллектива вычислителей

1.3. Модели системы функциональных устройств и сети неодинаковых процессоров

1.4. Модель производительности сети рабочих станций

1.5. Модели структуры вычислительных задач

1.6. Постановка задачи оценки производительности распределенных вычислительных комплексов

Глава 2. Модель производительности распределенных вычислительных комплексов

2.1. Линейная модель для задач без внутренней структуры

2.1.1. Основные определения модели производительности

2.1.2. Линейная эталонная модель для произвольно делимых задач

2.1.3. Модель внутренней структуры задачи в линейной эталонной модели

2.1.4. Характеристики производительности. Коэффициент эффективности и вектор ускорений

2.1.5. Учет затрат на вычисления. Ресурсная модель производительности

2.2. Модели для неоднородных вычислительных комплексов

2.2.1. Применение модели систем с расписанием к анализу производительности неоднородных комплексов

2.2.2. Пример верификации характеристик производительности

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

2.2.4. Применимость модели задач с последовательной частью к распределенным системам

Глава 3. Декомпозируемые задачи и интервальная модель, вычислений

3.1. Понятие декомпозируемой задачи

3.2. Модель интервальных систем в простом случае

3.2.1. Постановка задачи

3.2.2. Оптимальный алгоритм управления процессом вычислений

3.3. Интервальная модель для задач переменной трудоемкости

3.3.1. Моделирование решения задач глобальной оптимизации стохастическими методами

3.3.2. Обобщение интервальной модели на случай задач переменной трудоемкости

3.3.3. Оценка структурной неэффективности и расчет функции изоэффективности

3.3.4. Метод экспериментальной оценки трудоемкости задачи

3.3.5. Оценка вида распределения трудоемкости для одного алгоритма глобальной оптимизации

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

Глава 4. Структура и методика применения подхода эталонных систем

4.1. Классификация моделей в подходе эталонных систем

4.1.1. Структура моделей и использованные допущения

4.1.2. Параметры и допущения моделей систем и эталонных моделей

4.1.3. Анализ взаимосвязей и отношений между моделями интервальных систем и систем с расписанием

4.2. Методика оценки производительности распределенных вычислительных комплексов на основе моделей эталонных систем

Глава 5. Применение подхода к анализу производительности распределенных вычислительных комплексов

5.1. Оценка производительности вычислительной инфраструктуры BnB-Грид в задаче конформации атомных кластеров

5.1.1. Описание распределенной вычислительной инфраструктуры ВпВ-Грид

5.1.2. Описание программного компонента управления процессом решения задачи

5.1.3. Применение линейной эталонной модели для анализа производительности комплекса ВпВ-Грид

5.2. Оценка эффективности работы программного комплекса HPC-NASIS

5.2.1. Компонент управления платформами исполнения

5.2.2. Описание работы модуля Трансивер

5.2.3. Компонент управления параллельным исполнением (PES)

5.2.4. Цель эксперимента и постановка задачи

5.2.5. Результаты экспериментов

5.3. Исследование производительности системы метакомпьютинга Х-Сош2 в эксперименте по докингу

5.3.1. Описание системы и постановка задачи исследования

5.3.2. Анализ производительности системы метакомпьютинга Х-Сош

5.3.3. Анализ результатов и правила организации вычислений

5.4. Оценка производительности CAS Maxima Desktop Grid

Распределенные вычисления и Грид-технологии применяются для решения многих сложных вычислительных задач науки и техники, которые не могут быть решены за приемлемое время на однопроцессорной рабочей станции или даже в рамках одного многопроцессорного вычислительного комплекса. Однако, применение распределенных вычислительных комплексов (РВК) и Грид-систем осложняется тем, что они имеют неоднородную структуру вычислительного пространства, которая может изменяться с течением времени и не допускает централизованного управления всеми аспектами процесса решения задачи, то есть являются сложными неоднородными системами.

Вследствие указанных особенностей, численные алгоритмы решения, допускающие эффективную реализацию на распределенных системах, должны быть основаны на декомпозиции исходной задачи на достаточно независимые подзадачи, которые могут выполняться одновременно. К таким методам можно отнести классические методы оптимизации: метод ветвей и границ, широко применяемый в различных задачах дискретной и глобальной оптимизации, методы стохастической оптимизации. Многие важные прикладные задачи могут быть сформулированы как задачи оптимизации большой размерности, решение которых на последовательных вычислительных машинах не позволяет достичь требуемой точности получаемого результата или требует недопустимо большого времени расчета, что связано с перебором большого числа вариантов, включая решение многочисленных «оценочных» вспомогательных задач, работой эвристических алгоритмов улучшения ранее найденных решений. Поэтому задачи данного класса могут быть достаточно просто декомпозированы для решения на распределенных вычислительных комплексах. Различные возможные области применения распределенных и параллельных вычислений представлены в работах [1, 2, 3].

Следует также выделить класс мультикластерных распределенных вычислительных комплексов, объединяющих ресурсы нескольких географически удаленных многопроцессорных систем коллективного доступа и обладающих двухуровневой структурой вычислительного пространства. На нижнем уровне располагаются процессоры и вычислительные ядра, на верхнем - «виртуальные кластеры», совокупности процессоров, выделенные на данной многопроцессорной системе для использования в рамках распределенного вычислительного комплекса.

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

Цели и задачи работы

Целями настоящей работы являются:

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

• Разработка универсального подхода к решению задачи оценки производительности распределенных вычислительных комплексов. При этом подход должен быть применим также к многопроцессорным и мультикластерным комплексам. Определение и формулировка количественных характеристик производительности.

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

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

Научная новизна

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

Как следствие широкого применения и накопления- опыта разработки распределенных вычислительных комплексов, стало возможным рассмотреть задачу оценки производительности с точки зрения методов системного анализа как целостную задачу для класса систем, что и было сделано в данной работе.

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

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

По-результатам анализа-состояния исследований можно судить, что данный подход ранее не применялся в полной мере к анализу производительности вычислительных комплексов. Сходные идеи использовались при анализе производительности многопроцессорных комплексов в работах [4, 5].

Методы исследования

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

Практическая ценность работы

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

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

Апробация работы

Результаты диссертации и материалы исследований докладывались, обсуждались и получили одобрение специалистов на:

• 24-ой «Международной конференции- по суперкомпьютерам» (Гамбург, Германия, 2009);

• Х и XI Всероссийских научных конференциях «Научный сервис в сети Интернет» (Новороссийск, 2008^ 2009);

•• III и IV Международных научно-практических конференциях «Современные информационные технологии и ИТ-образование» (Москва, 2008, 2009);

• III Международной научной конференции- «Параллельные вычислительные технологии» (Нижний Новгород; 2009);

• 50, 51 и 52-ой научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2007, 2008, 2009);

•' 17-ой Международной научной конференции «Математика. Компьютер. Образование» (Дубна, 2010);

• II сессии научной школы-практикума «Технологии высокопроизводительных вычислений и компьютерного моделирования» В; рамках VI Всероссийской межвузовской конференции молодых ученых Санкт-Петербургского государственного университета, Институт точной механики и оптики (Санкт-Петербург, 2009);

• научных семинарах кафедры прикладной математики и моделирования систем Московского государственного,университета печати.

По материалам работы, опубликовано 14 печатных работ, пять из них в изданиях из списка ВАК [6, 7, 39, 44, 59].

Структура работы

Работа состоитиз данного введения, пяти глав и заключения.

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

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

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

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

В главе 5 приводится описание комплекса программ, реализующих данные модели, представлены результаты исследования производительности различных РВК на основе данного подхода, показана применимость предлагаемого подхода к оценке производительности.

Благодарности

Результаты, представленные в разделах 2.1.4, 2.2.3, 5.1.1 и 5.1.3, получены в соавторстве с Посыпкиным М.А. Необходимые данные для исследования производительности системы Х-Com , проведенного в разделе 5.3, были предоставлены Соболевым С.И. Результаты численных экспериментов, использованных для анализа производительности системы CAS Maxima Desktop Grid в разделе 5.4, были предоставлены Волошиновым В.В.

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

Следует также упомянуть важную роль и участие моего коллеги, Посыпки-на М.А., в подготовке нескольких совместных статей по теме данной работы. Критический подход к тексту, готовность доводить его до практически идеального состояния и обоснованные требования к простоте понимания текста, несомненно, способствовали повышению качества данной работы.

Результаты работы были получены при поддержке программы № 15П фундаментальных исследований Президиума РАН «Разработка фундаментальных основ создания научной распределенной информационно — вычислительной среды на основе технологий GRID», проектов РФФИ 08-07-00072-а, 09-07-12076-офи м, 09-07-00352-а, 09-07-09232-мобз, 09-07-16022-мобзрос. Результаты раздела 5.2 получены за время научной стажировки в СПбГУ ИТМО в рамках мероприятия 1.4 программы «Кадры» в области «Мобильность молодых ученых».

Основные результаты работы состоят в следующем:

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

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

3) Для описания процесса решения важного с прикладной точки зрения класса декомпозируемых задач разработана эталонная модель, в рамках которой разработан алгоритм управления процессом вычислений, минимизирующий время решения, и получены оценки структурной неэффективности. Модель также обобщена на случай декомпозируемых задач переменного размера, таких как задачи глобальной оптимизации, решаемые методами типа Монте-Карло. Получены новые аналитические выражения для эффективности в зависимости от конфигурации вычислительного пространства, а также функция изоэффективности. Предложен экспериментальный метод оценки трудоемкости решения декомпозируемых задач переменного размера по небольшому набору подзадач и получены оценки точности данного метода. Применимость модели и метода для анализа производительности показана на примере вычислительной инфраструктуры ВпВ-Грид.

4) Разработан комплекс программ, реализующий линейную эталонную модель и позволяющий рассчитывать значения характеристик производительности. Сформулирована схема применения разработанных методов оценки производительности и комплекса программ, которая была успешно применена к анализу производительности вычислительной инфраструктуры ВпВ-Грид, вычислительного комплекса HPC-NASIS, распределенной системы CAS Maxima Desktop Grid и системы метакомпьютинга Х-Сот2.

Направления дальнейших исследований

Вследствие того, что предложенный подход к оценке производительности распределенных вычислительных комплексов является новым, имеется множество возможных направлений его развития и применения. Упомянем некоторые из них.

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

Для решения задачи управления необходимо получить оценки трудоемкости решения задач различных типов в дополнение к оценкам, полученным в данное работе для алгоритма локальной оптимизации SMBH в некоторых частных случаях. Возможно, будут полезны некоторые результаты работы [42].

В связи с тем, что в состав распределенного вычислительного комплекса будут входить многопроцессорные машины с коллективным доступом, необходимо разработать модели выделения ресурсов и получить оценки времени ожидания их предоставления в зависимости от запрашиваемого количества процессоров и сроков выделения. Имеется множество результатов в данном направлении, например, [87, 88, 89].

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

Учитывая опыт применения подхода эталонных систем к оценке производительности можно сделать вывод, что в будущем потребуется разработать эталонные модели для описания вычислительных комплексов, не рассмотренных в данной работе типов, и структур задач. На данный момент представляется важным с прикладной точки зрения разработка эталонной модели для решения задач методом ветвей и границ на распределенных вычислительных комплексах. В более общем случае, в разрабатываемых эталонных моделях будут учитываться различные зависимости между подзадачами, которые на данный момент полагаются независимыми в интервальной модели решения декомпозируемых задач. С точки зрения применимости, важным результатом будет обобщение модели на случай совместно используемых вычислительных ресурсов. На данный момент функция расписания описывает предоставление ресурсов в выделенном режиме. Модель, учитывающая возможность совместного с другими программами, использования узлов распределенных вычислительных комплексов позволит более точно описать процесс решения задачи в системах массовых добровольных вычислений (public computing). Эталонная модель, явно учитывающая задержки при коммуникации через вычислительную сеть, скорее всего, также будет востребована при описании данного класса систем.

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

Заключение

Полученные результаты

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

1. Воеводин Вл.В. НИВЦ МГУ: широким фронтом совместных дел // Численные методы, параллельные вычисления и информационные технологии: Сборник научных трудов. - М.: МГУ, 2008.

2. Emelyanov S.V., Afanasiev А.Р., Grinberg Y.R., Krivtsov V.Y., Peltsverger В.V., Sukhoroslov О. V., Taylor R.G., Voloshinov V.V. Distributed Computing and Its Applications. Bristol, ME, USA: Felicity Press, 2005.

3. Проблемы вычислений в распределенной среде: организация вычислений в глобальных сетях // Труды ИСА РАН / под. ред. Емельянова С.В., Афанасьева А.П. М.: РОХОС, 2004.

4. Nussbaum D., Agarwal A. Scalability of parallel machines // Commun. ACM. -1991.- vol. 34, no. 3 (Mar. 1991). pp. 57-61.

5. Van-Catledge F.A. Toward a General Model for Evaluating the Relative Performance of Computer Systems // International Journal of High Performance Computing Applications. 1989. - vol. 3, no. 2. - pp. 100-108.

6. Хританков A.C. Модели и алгоритмы балансировки нагрузки. Модели коллектива вычислителей. Модели с соперником // Информационные Технологии и Вычислительные Системы. 2009. - № 2. - с. 65-80.

7. Хританков А. С. Модели и алгоритмы распределения нагрузки. Алгоритмы на основе сетей СМО // Информационные Технологии и Вычислительные Системы. 2009. - № 3. - с. 33-48.

8. Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing. -2nd ed. USA: Addison Wesley, 2003.

9. Kotsis G. Interconnection Topologies for Parallel Processing Systems // In Proc. of Parallele Systeme und Algorithmen. 1993.

10. Flynn M, Some Computer Organizations and Their Effectiveness // IEEE Trans. Comput.- 1972.-vol. C-21.-p. 948.

11. Darema F., George D.A., Norton V.A., Pfister G.F. A single-program-multiple-data computational model for epex/fortran // Parallel Computing. -1988. vol. 7. -pp. 11-24.

12. Donaldson V., Berman F., Paturi R. Program speedup in a heterogeneous computing network // J. Parallel Distrib. Comput. vol. 21, no. 3 (Jun. 1994). - pp. 316-322.

13. Market-Based Control: a Paradigm for Distributed Resource Allocation / S. H. Clearwater, Ed. River Edge, NJ: World Scientific Publishing Co., Inc., 1996.

14. Yan Y., Zhang X., Song Y. An Effective Performance Prediction Model for Parallel Computing on Non-dedicated Heterogeneous Networks of Workstations // J. of Parallel and Distributed Computing. 1996. - vol. 38, no. 1. - p. 63-80.

15. Culler D., Karp R., Patterson D., Sahay A., Schauser К. E., Santos E., Subramo-nian R., von Eicken T. LogP: towards a realistic model of parallel computation // SIGPLAN Not. vol. 28, no. 7 (Jul. 1993). - p. 1-12.

16. Valiant L. G. A bridging model for parallel computation // Commun. ACM. -vol. 33, no. 8 (Aug. 1990).-p. 103-111.

17. Bosque J. L., Pastor L. A Parallel Computational Model for Heterogeneous Clusters // IEEE Trans. Parallel Distrib. Syst. vol. 17, no. 12 (Dec. 2006). - pp. 1390-1400.

18. Drozdowski M. Scheduling for Parallel Processing. (s.l.): Springer, 2009. - 388 P

19. Robertazzi T.G. Networks and Grids: Technology and Theory. New York: Springer, 2007.

20. Bharadwaj V., Ghose D., Robertazzi T. G. Divisible Load Theory: A New Paradigm for Load Scheduling in Distributed Systems // Cluster Computing. vol. 6, no. 1 (Jan. 2003).-pp. 7-17.

21. Febish G. J. Experimental software physics // Experimental computer performance evaluation. Amsterdam, North-Holland, 1981. - pp. 33-55.

22. Muthukrishnan S., Rajamaran R. An Adversarial Model for Distributed Dynamic Load Balancing I I In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures. June 1998. - pp. 47-54.

23. Kwok Y., Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors // ACM Comput. Surv. vol. 31, no. 4 (Dec. 1999). -pp. 406-471.

24. High-Performance LINPACK Benchmark Электронный ресурс.: http://www.netlib.org/benchmark/hpl/

25. NAS Parallel Benchmarks Электронный ресурс.: http://www.nas.nasa.gov/Resources/Software/npb.html38. van der Wijngaart R. NAS Parallel Benchmarks Version 2.4: NAS Technical Report NAS-02-00 / NASA Ames Research Center. Moffett Field, CA: (s.n), 2002.

26. Хританков А. С. Оценка характеристик производительности распределенных вычислительных систем // Труды XV Научной конференции студентов, аспирантов и молодых ученых «Ломоносов». — 2008. с. 53-54.

27. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. М.:ФИЗМАТЛИТ, 2008. - 304 с.

28. Посыпкин М.А., Хританков А. С. О понятии ускорения и эффективности в распределенных системах // Труды Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач». — 2008. с. 149-155.

29. Соболев С.И. Использование распределенных компьютерных ресурсов для решения вычислительно сложных задач // Системы управления и информационные технологии. 2007. - №1.3 (27). - с. 391-395.

30. Афанасьев А.П., Волошинов В.В., Посыпкин М.А., Сигал И.Х., Хуторной Д.А. Программный комплекс для решения задач оптимизации методом ветвей и границ на распределенных вычислительных системах // Труды ИСА РАН. -2006.-Т. 25.-с. 5-17.

31. Афанасьев А.П., Посыпкин М.А., Сигал И.Х. Проект BNB-Grid: решение задач глобальной оптимизации в распределенной среде // Труды второй международной конференции "Системный анализ и информационные технологии" (САИТ-2007). Т. 2. - с. 177-181.

32. Павловский Ю.Н. Проблема декомпозиции в математическом моделировании // Матем. моделирование. — 1991. Т.З. № 6. - с. 93-122.5\.Павловский Ю.Н., Смирнова Т.Г. Проблема декомпозиции в математическом моделировании. М.: Фазис, 1998. - 272 с.

33. Leary R.H. Global Optimization on Funneling Landscapes // Journal of Global Optimization. 2000. - vol. 18, no. 4. - pp. 367-383.

34. Хританков А.С. Оценка эффективности распределенных систем при решении задач переменного размера. // Научно-технический вестник СПбГУ ИТМО. 2010. - № 2(66). - с. 66-71

35. Крамер Г. Математические методы статистики. 2-е изд. - М.:Мир, 1975. -648 с.

36. Посыпкин М.А. Архитектура и программная организация библиотеки для решения задач дискретной оптимизации методом ветвей и границ на многопроцессорных вычислительных комплексах // Труды ИСА РАН. 2006. -Т. 25.-с. 18-25.

37. ByrdR.H., Lu P., Nocedal J. A Limited Memory Algorithm for Bound Constrained Optimization 11 SIAM Journal on Scientific and Statistical Computing. -1995. vol. 16, no. 5. - pp. 1190-1208.

38. Суперкомпьютер "MBC-100K" / Межведомственный Суперкомпьютерный Центр РАН Электронный ресурс.: http://www.jscc.ru.

39. Ивченко Г.И., Медведев Ю.И. Математическая статистика: Учеб. Пособие для втузов. М.: Высш. Шк., 1984. - 248 е., ил.

40. Гамма Э., Хелм Р., Джонсон Р. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — СПб.:Питер, 2001. 368 с.

41. Суперкомпьютер "MBC-6000IM" / Межведомственный Суперкомпьютерный Центр РАН Электронный ресурс.: http://www.iscc.ru.

42. Вычислительный кластер Тамбовского государственного технического университета Электронный ресурс.: http://www.tstu.ru

43. А.Ковальчук С.В. и др. Особенности проектирования высокопроизводительных программных комплексов для моделирования сложных систем // Информационно-управляющие системы. 2008. - 3(34). - с. 10-18.

44. Бухановский А.В., Ковальчук С.В., Марьин С.В. Интеллектуальные высокопроизводительные программные комплексы моделирования сложных систем: концепция, архитектура и примеры реализации. // Изв. Вузов. Приборостроение. 2009. - т. 52, № 10. - с. 5-24.

45. Суперкомпьютерный комплекс МГУ Электронный ресурс.: http://parallel.ru/cluster/.

46. Суперкомпьютерный центр Южно-Уральского государственного университета Электронный ресурс.: http://supercomputer.susu.ru/.

47. Сибирский Суперкомпьютерный Центр Коллективного Пользования (ССКЦКП) Электронный ресурс.: http://www2.sscc.ru.

48. Веб-сайт разработчиков системы CAS Maxima Электронный ресурс.: http://maxima.sourceforge.net.

49. Henning М. A New Approach to Object-Oriented Middleware // IEEE Internet Computing. 2004. - vol. 8, no. 1, (Jan 2004). - pp. 66-75.

50. BrevikJ., Nurmi D., Wolski R. Predicting bounds on queuing delay for batch-scheduled parallel machines // In Proceedings of the Eleventh ACM SIGPLAN