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

СЮ34843Ыа

На правах рукописи

Яньков Сергей Георгиевич

Исследование и разработка методики отображения задач на кластерные системы с иерархически-неоднородной коммуникационной средой

Специальность 05.13.15 «Вычислительные машины и системы»

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

2 6 НОЯ 2009

Москва —2009

003484389

Работа выполнена на кафедре вычислительных машин, систем и сетей Московского энергетического института (технического университета)

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

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

кандидат технических наук профессор

Ладыгин Игорь Иванович

доктор технических наук старший научный сотрудник Каравай Михаил Федорович

кандидат технических наук

стя питий HЯV^T^TT,TЙ Р.ГУГПУЛНИК'

----1- - V - ~ - - -1 ^ ^

Костенко Валерий Алексеевич

Ведущая организация: ОАО «Научно-исследовательский

институт вычислительных комплексов им. М.А. Карцева»

Защита состоится 18 декабря 2009 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.16 при Московском энергетическом институте (техническом университете) по адресу 111250, г. Москва, ул. Красноказарменная, д. 17, ауд. Г-306.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г. Москва, ул. Красноказарменная, д. 14, Ученый Совет МЭИ (ТУ).

Автореферат разослан 17 ноября 2009 г. Ученый секретарь

диссертационного совета Д 212.157.16 кандидат технических наук, доцент

С. А. Чернов

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

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

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

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

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

1. Выявлены особенности ИНКС КлС, влияющие на время выполнения ПП. Получены реальные времена передачи данных между вычислителями на разных уровнях иерархии ИНКС кластера МЭИ.

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

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

4. На основе предложенного алгоритма разработана методика статического отображения задач на выделенные вычислители КлС с ИНКС.

Практическая значимость работы заключается в получении численных значений времен передачи данных между вычислителями на разных уровнях иерархии ИНКС кластера МЭИ, которые могут быть использованы при разработке сложных ПП и планировании их выполнения на современных КлС, а также в создании программных средств, обеспечивающих существенную инструментальную поддержку разработанной методики отображения задач.

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

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

Результаты диссертационной работы внедрены также в учебный процесс кафедры ВМСиС МЭИ (ТУ) и используются при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы».

Внедрение результатов работы подтверждено соответствующими актами.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 13-й и 14-й Международных научно-технических конференциях «Информационные средства и технологнн^ ^г Москва, 2006—2007 гг.), на 15-м Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации» (Украина, г. Алушта, 2006 г.) и на 2-й международной конференции «Надежность компьютерных систем» (DepCoS RELCOMEX 2007, Польша, 2007 г.).

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

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 6 печатных работах.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (76 наименований) и 7 приложений. Диссертация содержит 168 страниц машинописного текста.

Содержание работы

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

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

В разд. 1.1, на примере кластера МЭИ, подробно рассмотрены особенности современных КлС и используемых в них ИНКС. Исследована организация современных КлС: объединение многопроцессорных вычислительных узлов (ВУ) в подсети с помощью высокопроизводительных сетей (например, InfiniBand), а подсетей — через коммутаторы и маршрутизаторы. Так кластер МЭИ (рис. 1) состоит из 16 двухпроцессорных ВУ (C/V), объединенных сетью

1 Пакет ANES разрабатывается на кафедре инженерной теплофизики МЭИ (ТУ) при финансовой поддержке Российского фонда фундаментальньк исследований (¡рант № 06-08-01330-а).

InfiniBand и одного управляющего узла (ConN). В качестве процессоров (РМ) используются двухядерные (Core 0, Core 1) процессоры AMD с шиной Ну-perTransport. Под вычислителем понимается ядро процессора. На примере кластера МЭИ рассмотрен способ организации ИНКС современных КлС.

Рис. 1. Структурная схема кластера МЭИ Для передачи данных ме-

жду различными вычислителями (рис. 1) используются различные механизмы: обращение к памяти (внутри процессора); использование канала HyperTransport (между процессорами уз-

-Ч Т Г* *Г> 7 /. _______ТЛЧГ\ Т4. ____ _ г___ ____ц 1ГГЧТГ

ли) и сети lnjiruDurm (между и у ). халим ииргиим для Kjiaiacpa ivjoa-i характерна трехуровневая организация ИНКС, включающая уровни передачи данных между ядрами внутри процессора, между процессорами и между узлами. Очевидно, что в результате различия характеристик коммуникационных сетей на указанных уровнях время передачи данных между вычислителями кластера различно. В кластерных системах больших масштабов (RoadRunner, BlueGene и пр.) можно выделить большее число уровней иерархии, что приводит к еще большей неоднородности КС и существенному различию времени передачи данных между вычислителями. Поэтому, при отображении задач на вычислители таких КлС необходимо учитывать их ИНКС.

В этом же разделе подробно рассмотрены и проанализированы основные характеристики сетевых технологий InfiniBand и Hyper Transport.

В результате проведенного в разд. 1.1 анализа установлено, что наличие ИНКС в современных КлС определяет различное время передачи данных между различными вычислителями системы, что существенным образом сказывается на времени выполнения ПП.

Разд. 1.2 посвящен анализу наиболее часто применяемых в настоящее время методов отображения задач.

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

срщ

CoreО

CPi\ CoreO Corel

I ОТ,

HyperTransport

Управление -

ConN

хода можно выделить отсутствие в настоящее время стратегий, в полной мере учитывающих ИНКС современных КлС.

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

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

Рассмотрены также возможности встроенных планировщиков КлС по эффективному отображению задач.

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

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

В разд. 2.1 приведен пример, иллюстрирующий эффективность учета ИНКС кластера при отображении задач.

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

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

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

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

Начальная вершина а1 >

Ранг

ных с решением систем диффе-

2

0 ренциальных уравнений и уравнений в частных производных, а

1 также задач анализа структурной надежности систем и т.д.

С формальной точки зрения задача рассматриваемого класса представлялась в виде безконтур-ного орграфа (рис. 2), множество

ВерШИН КОТОРОГО 5 = {5], ..., соответствуют сегментам задачи, а множество дуг Е = {(?;,.?,) | 1 < г, / <

• •

< «5} — связям сегментов по данным.

а„5. ¿«1-0

Рис. 2. Пример графа задачи рассматриваемого класса

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

сегмента на вычислителе с заданным быстродействием (V), и величина ¿¡, определяющая объем данных, передаваемых сегментом каждому из сегментов, связанных с ним по выходу.

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

Во внутреннем машинном представлении граф задачи был представлен:

- матрицей смежности У= |[уу||, 1 </',/ </У(Лт— число вершин в полном ярусе графа), определяющей связь сегментов друг с другом;

- векторами А = ||а,-|| и В = ||6,||, 1 </ <>Ы, содержащими веса вершин графа — времена выполнения сегментов на вычислителях с заданным быстродействием и объемы передаваемых из сегментов данных, соответственно.

Матрица смежности Г описывает связь сегментов двух последовательных итераций, поэтому ее размерность — А7у,М.

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

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

При моделировании КлС задавалась числом узлов пМ, числом процессоров в узле nPN, и ядер в процессоре пСР.

Для внутреннего машинного представления временных характеристик ИНКС, использовалась матрица 2 = Цг^Ц, 1 < ], р < пС удельных времен

передачи данных между вычислителями КлС. Элементы матрицы принимали значения tp, tc и 0, соответствующие удельным временам передачи данных между вычислителями разных узлов (сеть InfiniBand), вычислителями разных процессоров одного узла (сеть HyperTransport), вычислителями разных ядер одного процессора (общая память) и время передачи данных самому себе. Под удельным временем передачи понимается время передачи единицы данных.

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

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

Дана вычислительная задача, заданная матрицей смежности У = ¡[у,-,! и векторами А = ||а,-||, В = ||6;||, 1 </,/ <N.

Дана кластерная система, в которой для решения задачи выделено К вычислителей, имеющих вполне определенную локализацию в системе. Удельные времена передачи данных между выделенными вычислителями заданы матрицей Z = \\zJtP\\, 1 <j,p<K.

Необходимо отыскать вариант отображения задачи на кластер, описываемый матрицей отображения Х= ¡¡х^Ц, 1 < г < N, 1 <j < К, такой, что xLJ = 1, если сегмент st распределен на вычислитель с;-, и xtJ = 0 в противном случае, обеспечивающей минимальное или близкое к минимальному (субоптимальное) время решения задачи Грш. Такой вариант отображения в работе назван эффективным отображением задачи на кластер.

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

Третья глава посвящена экспериментальному исследованию ИНКС КлС, на примере кластера МЭИ.

В разд. 3.1 представлено описание разработанных M/Y-программ для исследования ИНКС КлС.

Рис. 3 Графическое представление КлС

В разд. 3.2 приведены результаты экспериментального исследования времени передачи данных между различными вычислителями при использовании блокирующих функций посылки. Эксперименты проводились для двух вариантов условий: передачи данных по ИНКС без нагрузки и по загруженной сети. Загруженность сети моделировалась путем одновременного выполнения передачи данных по анализируемой сети несколькими парами вычислителей. Время передачи данных между ядрами одного процессора замерялось в момент одновременной передачи данных в другом процессоре узла; время передачи данных между парой ядер из разных процессоров одного узла замерялось в момент передачи данных между другой парой ядер этих же процессоров; время передачи данных между парой ядер из разных узлов замерялось в момент одновременной передачи данных другими парами ядер этих же узлов. Результаты экспериментов приведены на рис. 4. Количественные оценки, полученные в эксперименте, показали, что время передачи данных в ИНКС определяется не только ее характеристиками, но и существенно зависит от различных накладных расходов, таких как задержки в различном оборудовании узла (например, адаптер InfiniBand, при обращении к памяти и пр.), что хорошо демонстрируют результаты экспериментов для загруженной сети.

По результатам проведенных экспериментов были определены реальные значения tK, tP, tc времен передачи данных, по которым составлена матрица Z удельных времен передачи данных между различными ядрами кластера МЭИ, которая использовалась при отображении задач в экспериментальной части работы.

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

Результаты экспериментов по определению времени обработки функции MPlJsend приведены на рис. 5 и свидетельствуют о следующем.

1. Время обработки функции MPI_Isend зависит от объема передаваемых данных и от характеристик сети по которым они передаются.

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

400 350 300 250 200 150 100 50 0

КС \ i < i /

/ /

i ЗУ У /

" 1 1 ✓ /

1 /

_ i_ / j T

i 2

1/ I___

[/' ...J-- 1 j

10 30 50 70 Объем передаваемых данных, кбайт

Рис. 4. Зависимость времени передачи данных от объема передаваемой информации:

по сети без нагрузки: 1 — между ядрами одного процессора (¡с); 2 — между процессорами одного узла (//>); 3 — между узлами (/»,■); по загруженной сети: 1' — между ядрами одного процессора (Гс); 2' — между процессорами одного узла (/р); 3' — между узлами

вызова функции резко снижается. Указанная особенность объясняется спецификой внутренней реализации данной функции в конкретной версии библиотеки параллельного программирования MPI.

3. При небольших объемах передаваемых данных время только вызова функции MPI_Isend превосходит время передачи тех же данных с

применением функции

Рис. 5. Зависимость времени обработки функции j^jpj Send (см рис 4 5) MFIJisenà от объема передаваемой информации: _

по сети без нагрузки: между ядрами одного процес- результатам экспери-

сора (!)■ между узлами (2); ментов были определены вре-

по загруженной сети: между ядрами одного процес- мена вызова функции сора (Г); между узлами (2'). неблокирующей посылки еди-

ницы данных для различных сетей КлС, которые были сведены в матрицу W= ¡|w;J|, \<j,p<K.

В разд. 3,4 представлены результаты анализа влияния характеристик ИНКС современных КлС на время решения задач, на примере двух задач: анализа надежности и расчета поля температур применительно к двумерной задаче теплопроводности, относящихся к рассматриваемому в работе классу задач.

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

Таблица 1

Время выполнения ПП (задача теплопроводности)

Число вычислителей 1 2 3 4

Число узлов х число ядер в узле 1x1 1x2 2x1 1x3 3x1 1x4 2x2 4x1

Время выполнения, с 710 512 363 362 247 272 263 188

Продолжение табл. 1

Число вычислителей 6 8 9

Число узлов х число ядер в узле 2x3 3x2 6x1 2x4 4x2 8x1 3x3

Время выполнения, с 174 171 123 126 123 97 105

Продолжение табл. 1

Число вычислителей 12 16

Число узлов х число ядер в узле 3x4 4x3 ! 6x2 12x1 4x4 8x2 16x1

Время выполнения, с 74 72 | 72 62 55 53 45

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

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

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

Таблица 2

Время выполнения ГШ (задача анализа надежности)_

Число вычислителей 1 2 4

Число узлов х число ядер в узле 1x1 2x1 1x2 2x2 4x1 1x4

Время выполнения, с 731 448 L 376 358 303 216

Продолжение табл. 2

Число вычислителей 8 10 16

Число узлов х число ядер в узле 2x4 4x2 8x1 5x2 4x4 8x2 16x1

Время выполнения, с 47! 312 208 442 Г493 322 179

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

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

Полученные результаты (табл. 2) противоположны результатам первого эксперимента (табл. 1). Выполнение задачи на четырех ядрах одного узла (1x4, 216 с) происходит быстрее, чем на четырех ядрах из разных узлов (4x1, 303 с). Данный результат объясняется отсутствием конфликтов при работе с памятью, так как все необходимые данные умещаются в кэш и интенсивность обращений к памяти минимальна, а ускорение обеспечивается применением более быстрых коммуникаций (внутри узла). Полученные результаты продемонстрировали существенное влияние характеристик ИНКС на время выполнения ПП.

Результаты проведенных в третьей главе экспериментов показали, следующее:

- использование различных сетевых технологий в КлС существенно влияют на общее время решения задач;

- эффективное отображение задачи на вычислители позволяет существенно сократить время ее решения;

- отображение задачи на вычислители должно проводиться с учетом характеристик задачи и КлС, в том числе с учетом характеристик ИНКС;

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

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

В разд. 4.1. разработана оптимизационная модель отображения регулярных задач.

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

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

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

В общем виде время решения задачи на КлС представляется функцией Т^/{ТН,СН,БО,Х), (1)

где ТН — характеристики задачи; СН — характеристики кластерной системы; Ж — накладные расходы (системные задержки); X— вариант отображения задачи на кластерную систему.

Для рассматриваемых в работе условий, общее время решения регулярной задачи на КлС с ИНКС может быть представлено в виде

тгеш = тРиг,А,в,г,ж,Х). (2)

Для регулярных задач время решения складывается из времени выполнения регулярной и нерегулярной частей их алгоритма

греш=т^+г™. (3)

Для задач рассматриваемого класса временем выполнения нерегулярной части алгоритма можно пренебречь, а время выполнения регулярной части определяется временем решения Ь идентичных ярусов графа задачи:

Треш=Третуя=1хТярусз. (4)

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

Г"иса = тах (г,), (5)

11

где 7} — время работы /-го вычислителя при выполнении назначенных на него сегментов одного яруса графа задачи. При этом под временем работы понимается сумма времен как непосредственно вычислений, так и процессов приема исходных данных и передачи результатов. При решении конкретной вычислительной задачи на выделенном числе вычислителей заданной КлС параметры У, А, В, 2, IV являются постоянными величинами. Поэтому указанные временные характеристики зависят только от переменной X— варианта отображения задачи:

гяруса = ^^вычисл. ^ + ^риема/передачи _ (6)

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

Г (

N

к ¿=1

Ь х шах

1 <,]<К

I

1=1

тах

1<1<К Ыг

V

р=1 р*]

\Л

JJ

+1

¡=1

к

Р=1

тах

1 йШ м

(Ъ1х1,рУц™],р)

)

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

Согласно построенной аналитической зависимости оптимизационная модель отображения регулярных задач на КлС с ИНКС имеет вид: г г дл Л

1х тах

\<1<К

¡=1

V

тах

\<.\<ы ш

р=1 р*}

N

1=1

; +

(

N !=1

Ч

„■I

р=1 Р*1

тах

1<1<,Ы

ш

• тт,

(8)

1Х;=1>

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

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

®2>

нет •(

есть ли еще нераспределенные сегменты задачи?

выбрать такую пару сегмент-вычислитель, которая при распределении выбранного

сегмента на выбранный вычислитель дает минимально возможное значение максикапьнаго времени передачи данных какого-либо вычислителя

Г 3

выбрать из них сегмент с минимальным числом связей с другими сегментами

- 4

распределить выбранный сегмент на вычислитель с

минимальным числом сегментов и максимально удаленный от наиболее загруженных вычислителей

одна ли такая пара?

распределить зыбранный сегмент на соответствующий вычислитель

10 -

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

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

Рис. 6. Схема алгоритма отображения задачи на вычислители

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

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

Для разработанного алгоритма определена область применения, проведена оценка объема перебора ~ (лг2/Г^2 и точности результатов, показана сходимость.

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

- сначала из списка готовых к выполнению в данный момент времени сегментов задачи выбирается сегмент, принадлежащий КП;

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

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

В пятой главе на основе предложенного алгоритма отображения разработана методика отображения задач на выделенные вычислители КлС с учетом особенностей ИНКС, приведена схема работ по методике и пример использования методики на модельной задаче. Также в данной главе проведено исследование эффективности разработанной методики на примере двух задач, относящихся к рассматриваемому в работе классу.

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

1. Формализованное описание решаемой задачи и выделенных для ее решения вычислителей кластера.

2. Предварительная оценка эффективности решения задачи на выделенных вычислителях кластера.

3. Отображение задачи на выделенные вычислители кластера.

4. Выполнение ПП, решающей задачу, и оценка результатов.

Методика описывает весь процесс решения задачи на КлС, начиная с

анализа параллельного алгоритма до реализации ПП, решающей задачу.

В разд. 5.2 представлена схема работ при отображении регулярных задач по разработанной методике (рис. 7).

В данном разделе приведен также пример использования разработанной методики отображения на модельной задаче. Результаты отображения продемонстрировали эффективность методики на уровне -15% по сравнению с алгоритмами отображения не учитывающими особенности ИНКС КлС. Под эффективностью методики понимается сокращение времени выполнения ПП.

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

Эффективность разработанной методики отображения на примере ПП, реализующей задачу анализа надежности, определялась путем сравнения времени выполнения программы, с отображением задачи по разработанной методике, со временем выполнения аналогичной программы, но с отображением другими методами, не учитывающими особенности ИНКС. Эксперименты проводились для различного числа вычислителей.

Размерность задачи в экспериментах была следующая: интервалов моделирования — 105—106; сегментов на каждом ярусе — 102—103. Результаты эксперимента приведены в табл. 3 и свидетельствуют о том, что время выполнения ПП зависит как от числа вычислителей, так и от варианта отображения задачи. Разработанная автором методика позволила сократить время выполнения ПП, при этом максимальное значение эффективности составило величину порядка ~17%.

Таблица 3

Время выполнения ПП (задача надежности), с___

Число используемых ядер 1 28 32 36 40 44 48 52 56

Отображение по методике 8945 448 387 367 311 301 278 256 247

Альтернативный алгоритм отображения 1 8945 464 407 382 329 318 317 303 257

Альтернативный алгоритм отображения 2 8945 461 417 402 332 327 327 310 252

Сокращение Методика/ отображение 1 0,0 3,4 4,9 3,9 5,5 5,3 12,3 15,5 3,9

времени, % Методика/ отображение 2 2,8 7,2 8,7 6,3 8,0 15,0 17,4 2,0

начало

г- 1

получение входных данных — распараллеленной задачи

адцч

представление задачи в виде графа; составление матриц связности У, множеств./! и Л, и удельных времен передачи данных 2

Л

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

нет

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

г- 7

внесение возможных изменений

отображение задачи на выделенные вычислители кластера посредством разработанного алгоритма отображения; построение матрицы X

г разработка

параллельной программы с учетом полученной матрицы отображения задачи на выделенные вычислители

•11-

параллельной программы и анализ полученных результатов

Г13

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

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

0

-14-\-

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

конец

Рпс. 7. Схема работ при отображении регулярных задач 18

Эффективность методики на примере ПП численного решения двумерной задачи теплопроводности определялась путем сравнения времени выполнения программы с отображением по разработанной в диссертации методике со временем выполнения ПП при использовании оригинального алгоритма отображения, реализованного в параллельной версии пакета прикладных программ ANES, развиваемого на кафедре ИТФ МЭИ (ТУ).

Максимальная эффективность разработанной методики в данном эксперименте составила величину порядка 15%. Поскольку полученные результаты оказались весьма существенными для данного класса задач, разработанная методика отображения была внедрена разработчиками ANES в параллельную версию пакета.

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

ТЗ те щщташш ттчттул лrmwQttQJ1' т 0С110ЕГТТ 1 а раотггтт тотг т гглmт .

ченные в диссертационной работе.

1. Проведен обзор современного состояния КлС и выявлены особенности, влияющие на время выполнения ПП.

2. Выполнен анализ использующихся в настоящее время методов отображения задач и анализ их особенностей.

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

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

5. Разработанный алгоритм отображения задач на вычислители КлС реализован в виде отдельного программного продукта.

6. Проведено экспериментальное исследование эффективности разработанной методики на кластере МЭИ. Полученная экспериментально максимальная эффективность разработанной методики составила величину порядка 17%.

7. Материалы проведенных в работе исследований легли в основу учебного пособия «Кластеры на многоядерных процессорах» и используются при проведении лекционных занятий по курсу «Вычислительные системы» на кафедре ВМСиС.

8. Программная реализация разработанного алгоритма отображения задач на вычислители применяется в учебном процессе при проведении лабораторных работ по курсу «Вычислительные системы».

9. Предложенная автором методика использована при разработке параллельной версии пакета прикладных программ ANES, развиваемого в МЭИ (ТУ) при финансовой поддержке Российского фонда фундаментальных исследований (грант № 06-08-01330-а).

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

1. Яньков С.Г. Особенности реализации параллельных программ на кластерных вычислительных системах // Вестник МЭИ. — М.: Издательский дом МЭИ, 2008. — №5. — С. 113—119.

2. Яньков С.Г., Ладыгин И.И. Распараллеливание задачи расчета надежности ВС // Труды междун. науч.-техн. конф. «Информационные средства и технологии». — М.: Янус-К, 2005. — Т.З. — С. 110—113.

3. Яньков С.Г., Ладыгин И.И. Решение задач моделирования по интервалам времени на кластерной вычислительной системе // Труды междун. науч.-техн. конф. «Информационные средства и технологии». — М.: Янус-К, 2006. — Т.2. — С. 200—202.

4. Яньков С.Г., Ладыгин И.И. Решение сложной задачи расчета надежности на кластерной вычислительной системе // Труды XV междун. науч.-техн. семинара «Современные технологии в задачах управления, автоматики и обработки информации». — М.: МИФИ, 2006. — С. 269.

5. Yankov S.G., Ladygin I.I. Technique for Analyzing Items Reliability by Simulating their Behaviour over Time Intervals // Proc. of 2nd Int. Conf. On Dependability of Computer System (DepCoS RELCOMEX 2007). — 2007. — P. 115—118. Яньков С.Г., Ладыгин И.И. Метод анализа надежности объектов путем моделирования их поведения по интервалам времени / Тр. второй межд. конф. по надежности компьютерных систем. — 2007. — С. 115—118.

6. Кластеры на многоядерных процессорах / Ладыгин И.И., ЛогиновД ß Филатов A.B., Яньков С.Г. — М.: Издательский дом МЭИ, 2008. —-112 с.

Подписано к печати Зак. т Тир. 100 Печ.л.

Отпечатано в Полиграфическом центре МЭИ (ТУ) Красноказарменная ул., д. 13

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

Глава 1. Современные кластерные системы и методы отображения задач на них.

1.1. Современные кластерные системы и их коммуникационные среды.

1.1.1. Организация кластерных вычислительных систем.

1.1.2. Особенности современных кластерных систем на примере кластера МЭИ.

1.1.3. Коммуникационные среды современных кластерных систем.

1.2. Методы отображения задач на кластерные системы.

1.2.1. Аппарат теории расписаний.

1.2.2. Поярусное распределение сегментов при отображении задач.

1.2.3. Прочие алгоритмы отображения задач.

Быстро растущие потребности человека в решении сложных задач обработки данных определяют темп развития компьютерной техники. Компьютерные системы и /Г-технологии стали одной из наиболее активно развивающихся технических отраслей в современном мире. Для решения задач, постоянно возникающих в разных сферах человеческой деятельности, все чаще применяются многомашинные вычислительные системы, существенно превосходящие по производительности отдельно взятые персональные компьютеры. Современные многомашинные вычислительные системы перестают быть уникальными техническими комплексами, становясь все более доступными.

Одним из наиболее популярных направлений в развитии многомашинных вычислительных систем, в настоящее время, являются кластерные системы [1—4], обладающие неплохим соотношением стоимости и производительности. Однако, наряду с многочисленными очевидными достоинствами кластерных систем, присутствует ряд трудностей в их применении для решения сложных задач [1], требующих значительных интеллектуальных усилий для их устранения.

В общем виде время решения задачи на кластерной системе можно представить в виде функции

Грей, =ДШ, СН, SD, X), где ТН — характеристики задачи; СН — характеристики кластерной системы; SD — накладные расходы (системные задержки); X — вариант отображения задачи на кластерную систему.

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна диссертационной работы обуславливается следующими факторами.

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

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

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

4. Разработана методика статического отображения задач на выделенные вычислители кластерных систем с иерархически-неоднородной коммуникационной средой.

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

Практическая значимость работы подтверждается использованием разработанной методики при создании параллельной версии пакета анализа процессов теплообмена ANES [24], а также применением результатов проведенных в работе исследований в учебном процессе кафедры ВМСиС МЭИ (ТУ), о чем имеются акты о внедрении. Результаты проведенных исследований также нашли свое отражение в учебном пособии «Кластеры на многоядерных процессорах», выпущенном Издательским домом МЭИ в 2008 году.

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

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

- разработан эвристический алгоритм отображения задачи на выделенные вычислители кластерной системы с учетом характеристик иерархически-неоднородной коммуникационной среды;

- разработана методика отображения задач на кластерные системы с учетом характеристик их иерархически-неоднородных коммуникационных сред;

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

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

Область применения разработанной методики. Необходимо отметить ряд ограничений применения разработанной методики:

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

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

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

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

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

Результаты диссертационной работы были использованы в учебном процессе кафедры ВМСиС МЭИ (ТУ) при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы». Планируется даль

1 Проект осуществлен при финансовой поддержке РФФИ (грант № 06-08-01330-а).

10 нейшее использование материалов диссертации и разработанных программных средств в учебном процессе кафедры.

Публикации. Всего по теме диссертационной работы было опубликовано 5 статьей и выпущено одно учебное пособие.

1. Яньков С.Г., Ладыгин И.И. Распараллеливание задачи расчета надежности ВС // Труды междун. науч.-техн. конф. «Информационные средства и технологии». — М.: Янус-К, 2005. — Т.З. — С. 110—113.

2. Яньков С.Г., Ладыгин И.И. Решение задач моделирования по интервалам времени на кластерной вычислительной системе // Труды междун. науч.-техн. конф. «Информационные средства и технологии». — М.: Янус-К, 2006. — Т.2. — С. 200-202.

3. Яньков С.Г., Ладыгин И.И. Решение сложной задачи расчета надежности на кластерной вычислительной системе // Труды XV междун. науч.-техн. семинара «Современные технологии в задачах управления, автоматики и обработки информации». — М.: МИФИ, 2006. — С. 269.

4. Yankov S.G., Ladygin I.I Technique for Analyzing Items Reliability by Simulating their Behaviour over Time Intervals // Proc. of 2nd Int. Conf on Dependability of Computer System (DepCoS RELCOMEX 2007). — 2007. — P. 115—118.

5. Яньков С.Г. Особенности реализации параллельных программ на кластерных вычислительных системах // Вестник МЭИ. — М.: Издательский дом МЭИ, 2008. — №5. — С. 113—119.

6. Кластеры на многоядерных процессорах / И.И. Ладыгин, А.В. Логинов, А.В. Филатов, С.Г. Яньков. — М.: Издательский дом МЭИ, 2008. — 112 с.

5.4. Основные результаты и выводы

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

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

- эффективность разработанной методики существенно зависит от исходных данных, то есть от параллельной формы задачи и реализующей ее параллельной программы, качество которых зависит от «мастерства» пользователя;

2. Приведен пример использования разработанной методики на модельной задаче:

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

3. Проведены экспериментальные исследования эффективности разработанной методики, которые показали, что:

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

- эффективность разработанной методики зависит от характеристик кластерных систем — числа используемых вычислителей и характеристик иерархически-неоднородных коммуникационных сред;

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

- максимальная эффективность разработанной методики в проведенных экспериментах составила величину порядка 17%.

4. Программная реализация алгоритма отображения регулярных задач на вычислители нашла свое применение в учебном процессе при проведении лабораторных работ по курсу «Вычислительные системы».

5. Разработанная методика отображения задач на кластерные системы нашла свое применение в математическом пакете ANES, разработанном на кафедре ИТФ МЭИ (ТУ), для решения стационарной двумерной задачи теплопроводности численным методом контрольных объемов на кластере МЭИ.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Поэтому в диссертации разработана методика отображения задач на кластерные системы с иерархически-неоднородными коммуникационными средами.

В рамках диссертационной работы получены следующие результаты:

1. Проведен обзор современного состояния кластерных систем и выявлены особенности, влияющие на время выполнения параллельных программ.

2. Проведен обзор использующихся в настоящее время методов отображения задач и анализ их особенностей.

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

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

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

6. Проведено экспериментальное исследование эффективности разработанной методики на кластерной системе МЭИ (ТУ). Полученная экспериментально максимальная эффективность разработанной методики составила величину порядка 17%.

7. Материалы проведенных в работе исследований легли в основу учебного пособия «Кластеры на многоядерных процессорах», выпущенного в 2008 г. и используемого при проведении лекционных занятий по курсу «Вычислительные системы» на кафедре ВМСиС.

8. Программная реализация разработанного алгоритма отображения задач на вычислители нашла свое применение в учебном процессе при проведении лабораторных работ по курсу «Вычислительные системы».

9. Разработанная методика использована при создании модифицированной версии математического пакета ANES, создаваемой в МЭИ (ТУ) при финансовой поддержке РФФИ (грант № 06-08-01330-а).

1. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. — Спб.: БХВ-Петербург, 2002. — 608 с.

2. Кластеры на многоядерных процессорах: учебное пособие / И.И. Ладыгин, А.В. Логинов, А.В. Филатов, С.Г. Яньков; под ред. И.И. Ладыгина. — М.: Издательский дом МЭИ, 2008. — 112 с.

3. Информационно аналитический центр по параллельным вычислениям в сети Интернет http://www.parallel.ru.

4. Сервер информационных технологий http://www.citforum.ru.

5. The Infiniband Trade Association official website http://www. infinibandta. org.

6. HyperTransport Consortium official website http://www. hypertransport. org

7. Топорков B.B. Модели распределенных вычислений. — M.: ФИЗМАТЛИТ, 2004. — 320 с.

8. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные процессы. — М.: Наука, 1984. — 334 с.

9. Топорков В.В. Совместное планирование и назначение процессов как метод оптимизации архитектурных решений вычислительных систем // Автоматика и телемеханика. — 2001. —№ 12. — С. 107—116.

10. Котляров Д.В., Кутепов В.П., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах // Известия РАН. Теория и системы управления. — 2005, — № 1. — С. 75—96.

11. Mike Houston, Ji-Young Park, Маптап Ren et al, «А Portable Runtime Interface For Multi-Level Memory Hierarchies», PPoPP, 2008, February 20—23, Salt Lake City, Utah, USA.

12. Ладыгин И.И., Калинина Г.А. Лабораторные работы по курсу «Вычислительные системы» — М.: Издательство МЭИ, 1999, 32 с.

13. Дзегеленок И.И. и др. Декомпозиционный подход к осуществлению Gft/D-технологий / Информационная математика. — Изд-во РАЕН АСТ-Физматлит, № 1(5), 2005, с. 139—148.

14. Интернет-портал по грид-технологиям http://www.gridclub.ru.

15. Message Passing Interface Forum www.mpi-forum.org.

16. Головкин Б.А. Параллельные вычислительные системы. — М. Наука, 1980. —520 с.

17. Штейнберг Б. Открытая распараллеливающая система // Открытые системы. — 2007. — № 9.

18. The SUIF Group official website http://suifstanford.edu.

19. The PIPS Workbench Project http://www.cri.ensmp.fr/~pips.

20. Кутепов В.П. Организация параллельных вычислений на системах. — М.: Издательство МЭИ, 1988.

21. Яньков С.Г., Ладыгин И.И. Решение задач моделирования по интервалам времени на кластерной вычислительной системе // Труды междун. науч.-техн. конф. «Информационные средства и технологии». — М.: Янус-К, 2006. — Т.2. — С. 200—202.

22. Yankov S.G., Ladygin I.I. Technique for Analyzing Items Reliability by Simulating their Behaviour over Time Intervals // Proc. of 2nd Int. Conf. on Dependability of Computer System (DepCoS RELCOMEX 2007). — 2007. — P. 115—118.

23. Кутепов В.П. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения // Известия РАН. Теория и системы управления. — 1996. —№ 5.

24. Артемов В.И. Развернутый отчет по проекту 06-08-01330-а за 2007 г.

25. Яньков С.Г. Исследование процесса решения прикладных задач на параллельной вычислительной системе // Магистр. Дисс. — 2005 г. — 137 с.

26. Ладыгин И.И., Калинина Г.А. Исследование надежности вычислительных систем. — М.: Издательство МЭИ, 1999. — 32 с.

27. Яньков С.Г., Ладыгин И.И. Распараллеливание задачи расчета надежности ВС // Труды междун. науч.-техн. конф. «Информационные средства и технологии». — М.: Янус-К, 2005. — Т.З. — С. 110—113.

28. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. — М.: Наука, 1965.

29. Беллман Р., Калаб Р. Динамическое программирование и современная теория управления. — М.: Наука, 1969.

30. Вентцель Е.С. Исследование операций: задачи, принципы, методология. — 2-е изд., стер. — М.: Наука. Гл. ред. Физ.-мат. лит., 1988. — 208 с.

31. Ставцев А.В. Построение классификации многокомпонентных вычислительных систем // Вестник РУДН. Прикладная и компьютерная математика. — 2005 г, — № 5. — С. 126—134.

32. Система пакетной обработки заданий Torque http://www.clusterresources.com/pages/products/torque-resource-manager.php

33. Официальный сайт команды BOINC SETI@HOME Russia о ПВР www. setiathome. ru.

34. The Great Internet Mersenne Prime Search GIMPS official website www. mersenne. org.

35. Climate Prediction project www.climateprediction.net.

36. Einstein@Home Project http://einstein.phys.uwm.edu.

37. Проект распределенных вычислений для проведения компьютерной симуляции свертывания молекул белка http://folding.stanford.edu/russian/main.

38. Таненбаум Э. Архитектура компьютера. — СПб.: Питер, 2002. —704 с.

39. Кэрниган Б., Ритчи Д. Язык программирования С. СПб.: Невский диалект, 2000. — 352 с.

40. Герберг Ш. Полный справочник по С. — М.: Вильяме, 2007. —704 с.

41. Саттер Г. Решение сложных задач на С++. — М.: Вильяме, 2002. —400 с.

42. Артемов И.Л. Fortran. Основы программирования. — М.: Диалог МИФИ, 206. — 304 с.

43. Рыжиков Ю.И. Современный Фортран. Учебник. — Корона Принт, 2007. —288 с.

44. Немнюгин С.А. Современный Фортран. Самоучитель. — СПб.: BHV-Петербург, 2003. — 496 с.

45. Инструкция по эксплуатации вычислительного кластера НРС-0011015-001. — Т-Платформы, 2007.

46. Ian Foster. What is the Grid? A Three point checklist. — 2002.

47. Корнеев B.B. Параллельные вычислительные системы. — M.: Но-лидж, 1999. —320 с.

48. Портал про Linux и Unix, http://www.linuxcenter.ru.

49. Артман Б. Linux по-человечески. Как установить и настроить Suse Linux 10. — М.: Триумф, 2006. — 304 с.

50. Бовет Д., Чезати М. Ядро Linux. — 3-е изд. — СПб.: BHV-Петербург, 2007. — 1104 с.

51. AMD Russia. Официальный сайт AMD. http://www.amd.com/ru-ru.

52. Gigabit Ethernet Technology, www.gigabit-ethernet.org.

53. Sun Microsystems Russia, http://ru.sun.com.

54. Гук M. Аппаратные средства IBM PC. Энциклопедия. — 2-е изд. — СПб.: Издательский дом «Питер», 2002.

55. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. — 2-е изд. — СПб.: Издательский дом «Питер», 2004.

56. Олифер В.Г., Олифер Н.А. Сетевые операционные системы СПб.: Издательский дом «Питер», 2001.

57. Гук М. Процессоры Intel: от 8086 до Pentium II. — СПб.: «Питер Ком», 1997.

58. Гук М., Юров В. Процессоры Intel Pentium IV, Pentium III, AMD Athlon и Duron. — СПб.: Издательский дом «Питер», 2001.

59. Intel Corporation. Official site with technical documentation. — Santa Clara: Intel Corporation, CA, USA, 2005. http://www.intel.com.

60. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. — М.: Наука, 1984.

61. Немнюгин С.А., Стесик O.JI. Параллельное программирование для многопроцессорных вычислительных систем. — СПб.: БХВ-Петербург, 2002. — 400 с.

62. Грегори Р. Эндрюс. Основы многопоточного параллельного и распределенного программирования. — М.: Изд. дом «Вильяме», 2003 г.

63. Г. Корн, Т. Корн. Справочник по математике (для научных работников и инженеров); под общ. ред. И.Г. Арамановича. — пер. с англ. — М.: Наука, 1974.

64. Bourbonnais et al., Towards an Information Infrastructure for the Grid, IBM System journal; 2004, vol. 43, no. A, p. 665—668.

65. Мжельский Б.И. Математические модели для решения проблем анализа. — М. издательство МЭИ, 200. — 24 с.

66. SSH Communications Security website, http://www.ssh.com.

67. Поспелов Д. А. Введение в теорию вычислительных систем. М., «Советское радио», 1972. 280 с.

68. Дерюгин А.А. Коммутаторы вычислительных систем: учебное пособие / А.А. Дерюгин. — М.: Издательский дом МЭИ, 2008. — 112 с.

69. Хорошевский В.Г. Архитектура вычислительных систем: учебное пособие. — 2-е изд., перераб. и доп. — М.: Издательство МГТУ им. Н.Э. Баумана, 2008. — 520 е.: ил. — (Информатика в техническом университете).

70. Левченко В.Д. Асинхронные параллельные алгоритмы как способ достижения 100% эффективности вычислений // Сб. Будущее вычислительной математики. М.: УРСС. 2004.

71. Кутепов В.П., Котляров Д.В. Управление загруженностью кластерных вычислительных систем // матер. Четвертого международ, научно-практического семинара и Всероссийской молодежной школы, Изд-во СНЦ РАН, 2004.

72. Организация параллельных вычислений на многомашинных (многопроцессорных) вычислительных системах : Диссертация кандидата технических наук: В 2-х ч. 4.1; 4.2: Приложение / П. Г. Тиц, Моск. энерг. ин-т (МЭИ). — М., 1975 . — 142 с

73. Современное состояние и перспектива развития суперкомпьютерных технологий для стратегически важных задач // Сб. науч. Тр. ИТМиВТ, № 1, 2008, мат. Конф. Перспективы развития высокопроизводительных архитектур.

74. Яньков С.Г. Особенности реализации параллельных программ на кластерных вычислительных системах // Вестник МЭИ. — М.: Издательский дом МЭИ, 2008. —№5. —С. 113—119.

75. Курносов М.Г. Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы. Автореф. дис. . канд. техн. наук. Новосибирск, 2008