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

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

Во Минь Тунг

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

программ

Специальность: 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

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

■/Л;

7

864604547

Москва-2010

004604547

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

Защита состоится 24 июня 2010 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.16 при Московском энергетическом институте (техническом университете) по адресу 111250, г. Москва, ул. Красноказарменная, д. 13, ауд. М-510

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

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

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

профессор

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

Официальные оппоненты: доктор технических наук

профессор

Кутепов Виталий Павлович

кандидат физико-математических наук доцент

Кивгушенку Александр Петрович

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

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

(ТУ).

Автореферат разослан

Ученый секретарь

диссертационного совета Д 212.157.16

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

доцент

С.А. Чернов

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

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

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

Объектом исследования в работе являются кластерные вычислительные системы на примере кластеров МЭИ и Ханойского Технологического Университета (ХТУ), предметом исследования — особенности организации памяти и КС КВС, учет которых позволит сократить время выполнения параллельных программ на КВС за счет эффективного назначения ФПП на выделенные вычислительные ресурсы.

Цель работы и задачи исследования.

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

Поставленная цель определяет следующие основные задачи исследования.

1. Анализ современных КВС с точки зрения оценки влияния особенностей

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

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

3. Проведение тестирования указанных выше реальных КВС с целью JкщчeiyI^кcпepимeнтaльныxJ^aнньIX,лIpeдcтaвлeнньIX-в-BИдe-кoэффициeнтoв— накладных расходов.

4. Разработка имитационной модели процесса выполнения задач на КВС и алгоритма статического назначения ФПП на вычислители КВС, основанного на аппарате теории генетических алгоритмов, учитывающего особенности организация памяти и КС, для КВС МЭИ и ХТУ.

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

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

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

3. Проведена адаптация генетического алгоритма для задачи эффективного назначения ФПП на вычислители КВС, построена имитационная модель процесса выполнения ПП на КВС и разработана методика статического назначения ФПП на выделенные вычислители КВС.

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

Внедрение результатов работы.

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

Достоверность результатов работы подтверждена экспериментальным исследованием решения различных задач на кластерах МЭИ, МГУ и ХТУ.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 15-й Международной научно-технической конференции «Информационные средства и технологии», г. Москва, 2008 г., а также на 16-й Международной научно-технической конференции студентов и аспирантов, г. Москва, 2010 г.

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

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

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

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

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

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

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

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

Для решения поставленной задачи предложено формальное описание КВС и выполняемых на них задач. В диссертации рассмотрены две моделей КВС, соответствующие различным, применяемым в настоящее время аппаратным платформам. В основной модели КВС представляется в виде дерева (рис. 1), состоящего из Ш уровней 5 = {«1, «2, ..., Каждый уровень дерева ассоциирован с определенными вычислительными ресурсами, которые объединены КС соответствующего уровня иерархии. В нашем случае (рис. 1), первый уровень представляет саму КВС, которая состоит из и вычислительных узлов, каждый узел состоит из т процессоров, а процессоры состоят из к ядер. Таким образом, КВС состоит из КК = пхтхк ядер (заметим, что в данной работе термины «ядро» и «вычислитель» используются как синонимы). Для каждого уровня я,, е 5 КС известен показатель производительности В5Г ([£„] = байт/сек).

Рис. 1. Модельное представление КВС с иерархической организацией памяти и КС

Параллельный алгоритм в диссертации представляется в виде ациклического графа. Для обозначения графа применяется стандартная символика G = <А, Е>, где А ={«ь •••) а/> •■ •> ам} ~ конечное множество вершин, а Е - отношение инцидентности между парами, отображающее информационно-логические связи между вершинами. Вершины графа ПА соответствуют фрагментам ПП, а дуги - связям по данным между вершинами. Вершины взвешены временем выполнения ti на вычислителе с заданным быстродействием и емкостью памяти V., требуемой для хранения как командной последовательности г-ой вершины, так и ее данных. Граф алгоритма не имеет циклов и условий, он имеет только одну начальную и только одну конечную вершину, соответствующие началу и концу выполнения ПА.

Назначение вершин графа алгоритма на вычислители КВС, определяется соответствующими значениями матрицы назначения X, X = {xwJie[l,N],de[i,K]}; хш=\, если i вершина назначена на d вычислитель, и x:d= 0 в противном случае. Необходимо назначить фрагменты ПП на выбранные К вычислителей из NK вычислителей системы таким образом, чтобы время решения было минимальным (близким к минимальному) с учетом характеристик задачи, характеристик КВС и вышеперечисленных факторов, которые влияют на время выполнения ПП. Такой вариант назначения в работе называется эффективным назначением. Каждая задача, решаемая на КВС, может характеризоваться максимальным теоретическим временем выполнения и минимальным теоретическим временем выполнения. Считается, что минимальное теоретическое время выполнения ТКПж т) определяется как

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

вычислителе. Следовательно, справедливо следующее соотношение: Гю,(в„рт,т, < Т (ЛГ) < Тта, где Т(Х) время решения ПП при варианте назначения X.

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

-Вторая глава посвящена экспериментальному йсслёдойанйю^

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

Введены следующие коэффициенты накладных расходов, определяемых

для каждого уровня иерархии при обращении к памяти £ = ÈL и _ Мх

1 Г, 2 г,

передачи данных. Здесь At, - временные затраты, определяемые накладными расходами из-за конфликтов при обращении к используемому уровню памяти, 7j - время обращения к используемому уровню памяти без конфликтов, дг, -временные затраты, определяемые накладными расходами из-за конфликтов при передаче данных на используемый уровень КС, Тг - время передачи данных без конфликтов на используемый уровень КС. Описаны разработанные программные средства тестирования КВС, служащие для определения времени передачи данных и обращения к памяти, а так же вычисления накладных расходов возникающих на разных уровнях иерархии. В разделе 2.2 приведены результаты экспериментального исследования времени обращения к памяти, по которым определяются значения введенных автором коэффициентов замедления времени обращения к памяти на разных уровнях иерархии д\,д],д" (КЭШ, ОЗУ, внешний носитель). Так же определены значения коэффициентов накладных расходов £„£',£", возникающих при конфликтах одновременного обращения к памяти на разных уровнях иерархии для КВС МЭИ и ХТУ. В качестве примера, в таблицах 1 и 2 представлены значения коэффициентов накладных расходов для КВС МЭИ и ХТУ, построенных на разных аппаратных платформах (вычислительные узлы КВС МЭИ построены на основе двух двуядерных процессоров AMD Opteron 254, а КВС ХТУ построены на двух двуядерных процессорах Xeon £5410), при обращении к памяти, для разных значений объема обрабатываемых данных, числа вычислителей и их местоположения в КВС. Выявлено, что если в одном ВУ выполняются две пользовательские ПП от разных пользователей, время выполнения ПП увеличивается. Автор предполагает, что данный фактор связан с распределением ресурсов операционной системой между пользователями при мультипрограммном режиме.

Значение коэффициентов накладных расходов г, КВС МЭИ Таблица 1.

Кол-во ядер ЧислоВ X число вычислит елей от 50КБ-5000К5 от 2Г.!|3.3300М5 4 6 ГО дс б Гб

номера вычислителен номеоз вычислителей ног.'есэ сычислителеп

1 2 3 4 1 2 2 4 1 2 3 4

2 1x2 0 С 005 0 03 0 026 -

2x1 0 01 0.006 0.1 0 003

3 1x3 0 01 0 003 0 003 0 043 0 043 0 01

3x1 0 003 0.002 0 01 0 053 0 11 0.008

4 1x4 0.01 С С02 0 01 0 003 о ом а 075 0 06 0 05:. 0 06 0 01 с об 0 01

2x2 0.003 0.003 0,001 0,002 0.06 0 075 0 1 0.078

4x1 0 0 0 01 0 005 0 001 0 01 0 005 0 007

Значение коэффициентов накладных расходов г, КВС ХТУ Таблица 2.

КоЛ-БО рлео Число Б У х число ВЫЧИСЛИТ елей от 2000КБ-5000К6 от 121',<5-15001.16 4 6 Го до 5 Гб

измерз вычислителей ншеса вычислителен ьсмеса Бычиспителей

1 2 3 I 4 1 2 3 4 1 2 3 4

2 1x2 0 02? 0.006 0 3 0 35

2x1 0 1 0 1 I 0,006 0 01

3 1x3 0 13 0 02 0 13 I 0 37 0.13 04 -

3x1 0 02 0 005 001 | 0 012 0 0006 0 01 -

4 1x4 0.Т9 0.16 0 15 | 0 15 ООЭЗ 0 67 0 72 0 0Е9 0 05 02 1 04 1 01

2x2 0 04 0 01 0 033 ! 0 000 0 37 0 24 0 23 0 21

Но полученным в экспериментах данным определено, что значение коэффициентов 5Ро, Д " для КВС ХТУ меньше, чем для КВС МЭИ. Но как только возникают конфликты при одновременном обращении к памяти всех четырех вычислителей, время обращения к памяти для ВУ КВС ХТУ резко возрастает, и превышает время обращения к памяти ВУ КВС МЭИ. Очевидно, что влияние особенности организации памяти в ВУ может привести к увеличению времени выполнения ПП. В разделе 2.3 приведены результаты экспериментального исследования времени передачи данных на разных уровнях иерархии. Определены реальные времена передачи данных, по которым были определены коэффициенты замедления времени передачи данных на разных уровнях иерархиях д2,д2',Э2' (между вычислителями, находящимися в одном процессоре, между вычислителями находящимися в разных процессорах, но в одном ВУ, между вычислителями в разных ВУ). Для КВС МЭИ д2 = о2=1, д'2 = 2; Для КВС ХТУ д'2 =52' = 1, д'2 = 21 Результаты

экспериментов представлены в таблице 3 и 4.

Время передачи данных между КС для КВС МЭИ Таблица 3

Объем передаваемых данных, Кб 1,6 8 48 80 800

время передачи данных (мкс) между вычислителями в одном ВУ 2,68 10,5 54,1 79,6 590

время передачи данных (мкс) между вычислителями в разных ВУ 10,1 26,3 88,1 133,6 1180

Время передачи данных между КС для КВС ХТУ Таблица 4

Объем передаваемых данных, Кб 1,2 12 60 120 240 1200

время передачи данных (мкс) между вычислителями в одном ВУ 2,5 15,Э 77,49 88,7 166 780

время передачи данных (мкс) между вычислителями в разных ВУ 35,56 347,5 1707 1841,6 3825,2 16860

Результаты приведенные в таблицах показывают, что полученные коэффициенты для двух КВС имеют большие различия. Время на межузловые передачи данных для КВС МЭИ в 2 раза дольше, чем при передаче данных внутри узла, а для КВС ХТУ эта разница составляет 21 раз. Столь разные значения связано с техническими характеристиками КВС (КВС МЭИ использует технологию Infmband, а КВС ХТУ использует технологию Gigabit Ethernet). Определены коэффициенты накладных расходов sj.ej ej при передаче данных на разных уровнях иерархии, которые возникают когда идет нагрузка на сетевой адаптер в ВУ. По результатам проведенных исследований автор предлагает сделать преобразование графа ПА с учетом влияния вышеперечисленных факторов на время выполнения вершин графа и время передачи данных. Данное представление графа алгоритма будет использоваться при решении задачи назначения. Пример результата преобразования графа преде хавлен на рИС. 2.

t:"SWN)*Knp

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

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

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

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

Кпр =U (PL)x(l-t- Eps(SW(V), Conf))

SW(V) - функция принимающая значение 5, или 5, " или Э, "в зависимости от объема обрабатываемых данных.

U (PL) - коэффициент уменьшения производительности вычислителя, определяемый количеством пользователей, использующих модуль памяти I в ВУ.

Eps(SW(V),Conf) коэффициент уменьшения производительности вычислителя, принимающий значение е[ или г," или г, " в зависимости от уровня иерархии доступа к памяти и количества вычислителей, использующих данный модуль память.

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

Вх. Данные 1

Вх. Данные 2

Алгоритм

назначание [ Х1 Хгп

Мат.

T(X1)..T(Xm)j Анал,3 Модель I \ рузультата

_I I_

Вых. данные

N\ Xm'..X'nm

Рис. 3. Процесс решения оптимизационной задачи

Здесь Вх. Данные 1 - характеристики прикладной задачи (например, граф алгоритма представленный в виде матрицы связанности и т.д.), Вх. Данные 2 -характеристики модели КВС, XI..Хт - варианты матрицы назначений, ^У -число циклов поиска оптимального результата.

Автором предлагается два варианта решения поставленной задачи.

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

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

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

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

/ iL Л \

у At xxmj, xxi ä xSW(Ve,) x Knp. + -

max- 1 iä<K I ' ft min 1=1 ' ' N К К ¡j { M rf=l 9=1 D:(.<!.q) J ■

V /

г, к .

Ki = X xmnxV™+Ттт<1,х max \xldx(V>-V'"'}

■ • ' Т.ш&Т.т,*- ■ >

= 1> ixj,< = 1> w d,qe{\..K]

I 9=1

Vt, - Vjht, - Vmap, > 0 ->min Объяснение индексов используемых в математической модели:

ее{1 ,..,Р), где Р количество ярусов в графе. y=min - номер младшей вершины на ярусе "е" Ye max - номер старшей вершины на ярусе "е"

матрица Я, где объём передаваемых данных (байт) от вершины i к вершине j. l<i,j<N. из данной матрицы Я можно найти объём данных

N

передаваемых i-й вершиной всем последователям У°ш Из матрицы Я

j--

можно найти объём принимаемых данных для j-й вершины от

N

предшественников V'" .

L общее число модулей памяти в системе, где I е [1,..,/-]. [I] - емкость

свободной памяти в модуле I. V [I] - ёмкость памяти на внешнем носителе,

выделяемой КВС при свопинге для ВУ, к которому подключен модуль памяти I

ХМ матрица назначения вершины на использование модуля памяти /, xmu = 1, если вершина i использует модуль памяти 1, где V/ е N\VleL.

ММ матрица, mmd, = 1, если процессор d подключен к модулю I, 0 в противном случае, где Уd е K;Vl е L.

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

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

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

|

Т(х)=<£

е-1

Г г г

(м.

тах

ми<к

I

А, х хт1, х х: х Б\У(Уе,) х Кпр. +

N К К 1

а»]

В

2(4.4)

IV

тт

КI = хт, I * К"' тти I х тах {х, ^ X (У - V'"" }

Уе[1..К];с!(Че[1..К] У . - У/т, - У™, > 0 -> тт

Критерием оптимизации является время выполнения ПП. В результате оптимизации должна быть получена матрица X, определяющая эффективное назначение ФПП на выделенные вычислители КВС. Решение задачи оптимизации на представленной модели назначения является весьма трудоёмким процессом, поэтому для «больших задач» применить модель невозможно. Обычно для реализации данной оптимизационной модели используют эвристические алгоритмы назначения и имитационное моделирование. В разделе 3.2.4 подробно описан принцип работы имитационной модели, а так же представлена схема алгоритма. В качестве алгоритма назначения был выбран генетический алгоритм (ГА). В разделе 3.3 подробно описан принцип работы и схема ГА. Одним из важных моментов для использования ГА является представление параметров объектов рассматриваемой предметной области исследований в виде генов особей. Для решения поставленной задачи в диссертации используются следующие представления.

1. Особь - носитель генетического кода, для нашей задачи это массив назначений вершины «.графа ПА на вычислители КВС.

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

3. Хромосома - ячейка в массиве назначения вершин на вычислители КВС.

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

5. Популяция - набор особей - для нашей задачи это множество массивов назначений.

Подробная схема ГА для задачи назначения представлен на рис. 4.

СНГ)

¡Ввод данной

|1Ш РорвЬе. 1л( 0еНа. 1п( СепСсил!

Создвн * в канальной популяции

Вызов процесса имитации для кажлсго «о1: зита, с сохранением рагупыжса моделировании в качестве значения целевой функции

а/ Л'ОтРосЗи»»! ДоРор

Ц8Л0ВШ функции

Скрашиааиые особей Рэ(Ьвг И Мо'.Гиг

Вычьд решения к результатов

Рис. 4. Схема генетического алгоритма для задачи назначения

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

Время выполнения задачи при использовании ГА и полного перебора Таблица 5

Чпспо используемых вычислителен 3 3 3 3 3 3 3 3 4 4

Располслеиие используемых вычислителей в КБС все 3 а одном ВУ 2 е одном ВУ 1 а другой БУ все 3 в разные ВУ все 3 в одном ВУ 2 в одном БУ.1 в другой ВУ все 3 в разных ВУ 2 в одном ВУ.1 а другой ВУ все 3 в одном ВУ 3 а одном ВУ.1 в друго.1 ВУ 3 В ОДНОМ БУ 1 в другом ВУ

Номер графз алгоритма 1 1 2 2 2 3 3 4 5

Количество вершин /дуг 12/15 12/15 12,15 13/19 13/19 13/19 14/21 14/21 14,19 13/20

Кол-во матриц назначения для решения задачи при полном переборе 531441 531441 531441 1554323 1504323 1594323 4702509 4>02Э63 263435436 67106654

Ксл-оо вариантов матрну назначении при ГА 11001} 11000 11000 11000 11000 11000 6000 6000 51000 5,000

Минимальное теор Время решення{Т<р| 23 23 23 160 160 160 130 190 213 212

Максимальное теор врема решения; Тоосл1, 43 48 43 370 370 370 460 4£0 440 400

Минимальное время решения задачи при полном пеоесоре 33 37 37 209 193 197 226 247 ■

Мннимнньние ьрвмн решен,-л .одачн при ГА 37 37 ! 39 1 I 210 | 217 1 211 246 251 I 231 I ! 223 |

В работе исследовались различные варианты сочетания параметров ГА для проверки достоверности полученных результатов. Так как ГА является эвристическим алгоритмом, то для достоверности полученных результатов был рассчитан доверительный интервал на модельных задачах, Для задачи № 2 из таблицы 5, где все 3 вычислителя расположены в одном ВУ при доверительной вероятности равной 0,95 и при выборке равной тридцати, доверительный интервал составил (208, 212). Для задачи № 3 из таблицы 5, где все 3 вычислителя расположены в одном ВУ, доверительный интервал составил (250, 254). Полученный результат показал узкий диапазон сходимости результатов, что подтверждает правильность работы ГА. Для доказательства адекватности разработанной модели было проведено сравнение реального времени решения ПП на КВС и времени решения данной ПП на модели для разных вариантов матриц назначениях XI и XI.

г 4 8 12 16

Рис.5 Зависимость коэффициента ускорения от количества вычислителей и матрицы назначения на КВС.

2

8 К

12

Рис.6 Зависимость коэффициента ускорения от количества вычислителей и матрицы назначения на модели.

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

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

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

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

12 4 6

Рис.7 Зависимость коэффициента ускорения от количества вычислителей и алгоритма назначения.

Т«»КЖС ДЛЯ 2Н2ЛИЗ£1 эффАКТИВНОСТИ р£13р£ООТЗНКОГО °ГТГСГ>Т^ТЛТ° г

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

1. ПП задачи перемножения матриц,

2. ПП анализа наделшости1 методом моделирования по интервалам времени.

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

Экспериментальные исследования показали, что конфликты на одновременное обращение к памяти влияют на эффективность выполнения параллельных программ, относящихся к слабосвязанным классам задач (т.е. время выполнения ФПП намного больше, чем время передачи данных между фрагментами), такие как задача перемножения матриц или задача теплопроводности1. На рис. 8 представлена зависимость коэффициента ускорения от количества вычислителей и матриц назначения ГА и X при решении задачи перемножения матриц на КВС МЭИ (матрица X получена с помощью эвристического метода, основанного на минимизации времени передачи данных). На рис. 9 представлена аналогичная зависимость, что и на рис. 8, при выполнении задачи на КВС МГУ и ХТУ (матрица X получена по принципу, заложенному в планировщике КВС)

1 Автореферат. Янькоз Сергей Георгиевич. Исследование и разработка методики отображения задач на кластерные системы с иерархически-неоднородной коммуникационной средой.

Кол-во вычислителей, К.

Рис. 8. Зависимость коэффициента ускорения от количества вычислителей и алгоритма назначения.

Кол-во вычислителей, К

Рис. 9. Зависимость коэффициента ускорения от количества вычислителей и алгоритма назначения.

При решении задачи моделирования процесса остывания нагретого объекта на КВС МЭИ и МГУ, несмотря на различные варианты назначения, коэффициент ускорения имеет одинаковое значение рис.10. Данный результат объясняется характеристикой данной задачи, объем обрабатываемых данных в задаче минимален и помещается в КЭШ памяти, следовательно, конфликты и накладные расходы на обращения к памяти почти отсутствуют. Интенсивность передачи данных между ФПП минимальна и не соизмерима с временем выполнения ФПП, следовательно, накладные расходы при передачи данных или иерархия КС не могут повлиять на время выполнения ПП.

Рис.10 Зависимость коэффициента ускорения от количества вычислителей и алгоритма назначения на КВС МЭИ

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

Рис. 11 Зависимость коэффициента ускорения от количества вычислителей и алгоритма назначения

Таким образом, применение разработанного алгоритма назначения позволило повысить эффективность выполнения ПП на КВС рассматриваемых задач на 6-12% по сравнению с принципом назначения, заложенным в планировщике КВС или в существующих эвристических методах назначения.

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

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

2. Формальное представление решаемой задачи и КВС.

3. Тестирование КВС для получения характеристик, необходимых для имитационной модели.

4. Назначение фрагментов ПП на вычислители КВС с помощью разработанного алгоритма.

5. .Оценку результатов выполнения ПП на КВС.

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

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

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

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

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

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

5. На основания проведенных в диссертации исследований и разработанног алгоритма назначения, была разработана методика назначения ФПП н вычислители КВС.

6. Проведены экспериментальные исследования эффективност разработанного ГА назначения на КВС МЭИ, МГУ, ХТУ. Полученны результат продемонстрировал повышение эффективности выполнения I на 6-12% по сравнению с алгоритмом назначения, заложенным планировщике КВС, или другими эвристическими методами.

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

Во Минь Тунг. Исследование методов распределения данных п процессорам кластерной системы для заданного класса прикладных задач. Труды международной научно-технической конференции «Информационны средства и технологии». 2008 . — С. 118-123.

Во Минь Тунг. Генетические алгоритмы в задаче о назначении. Шестнадцатая международная научно-техническая конференция студентов аспирантов . 2010 г. — С. 401 -402.

Во Минь Тунг. Оценка характеристик кластерных вычислительных cиcтe^ // Вестник МЭИ. — М.: Издательский дом МЭИ, 2010. — №2. — С. 133-140.

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

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

Содержание.

Сокращения.

Аннотация работы.

Введение.

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

Классификация параллельных компьютеров и систем.

1.1.2. Обзор современных суперкомпьютерных систем СНГ.

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

1.3. Классификация кластерных вычислительных систем.

1.4. Структуры кластеров, построенных на разных аппаратных платформах на примере кластеров МЭИ И ХТУ.

1.5. Принципы организации памяти кластерной вычислительной системы на примере кластера МЭИ И ХТУ.

1.6. Коммутационные среды кластерной вычислительной системы.

1.7. Анализ современных методов распределения задач.

1.7.1. Режимы функционирования кластерных вычислительных систем.

1.7.2. Управление ресурсами в распределенных вычислительных системах.

1.7.3. Планировщики кластерных вычислительных систем.

1.8. Модели и алгоритмы назначения задач на КВС.

1.8.1. Понятие назначения задач на КВС.

1.8.2. Обзор моделей распределения ресурсов и алгоритмов назначения.

1.9. Постановка задачи решаемой в диссертации.

1.9.1. Формальное описание модели кластерной вычислительной системы.

1.9.2. Формализованное описание класса задач.

1.9.3. Задача эффективного назначения фрагментов параллельных программ на вычислители КВС.

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

В настоящее время понятия «Многопроцессорные вычислительные системы» и «Многомашинные вычислительные системы» (МВС)[1] широко применяются при рассмотрении вопросов, связанных с параллельными вычислениями. В развитии вычислительной техники многое определяется стремлением повысить производительность существующих систем[1]. Мощность первых компьютеров была очень мала, поэтому решение многих прикладных задач (ПЗ) на них было невозможным или уходило немыслимое количество времени, для их решения. Сразу после появления первых компьютеров, стали придумывать различные методы для объединения нескольких компьютеров в одну единую систему, чтобы повысить производительность и минимизировать время решения задачи. Идея была проста - если мощности одного компьютера не хватает для решения ПЗ, то надо разделить задачу на две или более части и решать каждую часть на своем компьютере. Это и предопределило появление МВС, основным представителем которых являются кластерные вычислительные системы (КВС). КВС - это совокупность вычислительных узлов (ВУ), объединенных в рамках некоторой коммуникационной среды и нацеленных для решения одной сложной или множества независимых задач[1]. В качестве ВУ для кластеров некоторое время назад использовались доступные на рынке однопроцессорные компьютеры, в настоящее время используются 2-х или 4-х процессорные платформы, которые имеют различные архитектурные решения. В последнее время КВС становятся общедоступными аппаратными платформами для высокопроизводительных вычислений, обладающими неплохим соотношением стоимости и производительности.

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

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

В работе приводится подход, основанный на предварительном исследовании конкретных КВС (кластер МЭИ (ТУ) и кластер Ханойского Технологического Университета (ХТУ)) с целью получения значений их характеристик, которые дополнительно необходимо учитывать при решении задачи назначения фрагментов программы на вычислители КВС так, чтобы минимизировать время её выполнения.

Таким образом, решаемая задача в диссертации - исследование влияния характеристик современных КВС и варианта назначения фрагментов параллельной программы (Ф1111) на вычислители КВС на время выполнения ПП с последующим учетом этого влияния при минимизации времени решения и, следовательно, повышении эффективности применения КВС. Само время выполнения задач в сильной степени определяется механизмом назначения 8 фрагментов программы на вычислители KB С. Под назначением понимается процесс распределения ФПП (сегмент задачи) по вычислителям КВС, определяющее на каком вычислителе будет выполняться тот или иной фрагмент ПП. Обычно при выполнении 1111 на КВС выделяется определенное количество свободных ресурсов (вычислителей, емкость памяти и т.д.) на момент запроса обработки, поэтому вычислители могут находиться в разных местах КВС (в одном или разных процессорах, в одном или разных ВУ), связанных коммутационными сетями разных уровней и иметь различную свободную емкость памяти. Поэтому время передачи данных между вычислителями, а так же время обращения к памяти в зависимости от свободной емкости памяти на разных уровнях могут различаться, из-за этого время выполнения ПП на одном и том же количестве вычислителей может различаться в зависимости от того, какие именно вычислители используются. Поэтому при неудачном назначении, время выполнения задачи намного возрастает за счет появления накладных расходов. Под накладными расходами в работе понимаются те временные затраты, которые определяются факторами замедляющими время выполнения задачи. Следовательно, это непроизводительное время, связанное с обменом блоками данных между оперативной и дисковой памятью, время на разрешение конфликтов, которые возникают при учете приоритетов на обращения к памяти, передачи данных между КС с более низкой пропускной способности, латентность коммутационной сети (КС) при загруженном состоянии.

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

Цель работы и задачи исследования.

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

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

- архитектура ВС;

- вид организации памяти ВС;

- тип коммутационной сети;

- способ организации параллельных вычислений;

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

Объектом исследования в работе являются кластерные вычислительные системы на примере кластеров МЭИ и Ханойского Технологического Университета (ХТУ), предметом исследования — особенности организации памяти и КС КВС, учет которых позволит сократить время выполнения параллельных программ на КВС за счет эффективного назначения ФПП на выделенные вычислительные ресурсы.

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

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

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

3. Проведена адаптация генетического алгоритма для задачи эффективного назначения ФПП на вычислители КВС, построена имитационная модель процесса выполнения 1111 на КВС и разработана методика статического назначения ФПП на выделенные вычислители КВС.

Основные задачи диссертации. В диссертации ставятся и решаются следующие задачи.

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

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

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

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

11 организация памяти и КС, для КВС МЭИ и ХТУ.

5. Оценка эффективности предложенной методики статического назначения ФПП по вычислителям КВС на примере выполнения заданных прикладных задач.

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

Достоверность результатов работы подтверждена экспериментальным исследованием решения различных задач на кластерах МЭИ, МГУ и ХТУ.

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

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

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

Реализация результатов работы.

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

Результаты диссертационной работы Во Минь Тунга применяются в учебном процессе в Ханойском Технологическом Университете при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы».

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

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

Во Минь Тунг. Исследование методов распределения данных по процессорам кластерной системы для заданного класса прикладных задач // Труды междун. науч.-техн. конф. «Информационные средства и технологии».2008 г. С. 118—123.

Во Минь Тунг. Генетические алгоритмы в задаче о назначении // «Шестнадцатая международная научно-техническая конференция студентов и аспирантов» .2010 г. С. 401 -402.

Во Минь Тунг. Оценка характеристик кластерных вычислительных систем // Вестник МЭИ. — М.: Издательский дом МЭИ, 2010. — №2. — С. 133-140.

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

1. Приведены критерии для анализа эффективности разработанного ГА назначения ФПП на вычислители КВС, так же проведен анализ для сравнения разработанного алгоритма назначения с полным перебором на модельных задачах.

2. Разработаны ПП для оценки эффективности выполнения ГА назначения в частности параллельная MPI программа расчета освещенности виртуальных экранов (ЗЕ)-рефрактограмм) и визуализации освещенности экрана в интерференционной схеме для модели сферически неоднородной среды.

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

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

Заключение

Перечислим основные результаты, полученные в работе:

1. Проведен анализ и рассмотрены принципы построения современных КВС на разных аппаратных платформах, выявлено, что КВС являются мультиархитектурными, так как на разных уровнях детализации КВС применяются различные способы их организации. Написаны тестовые программы для исследования особенности иерархической организация КС и памяти КВС. Экспериментально получены следующие результаты: а) реальное время обращения к памяти на разных уровнях иерархии для КВС МЭИ и ХТУ. Полученный результат показал, на сколько может повыситься время выполнения ПП при обращения за данными находящимися в памяти высокого уровня; б) реальное время передачи данных на разных уровнях иерархии КС для КВС МЭИ, ХТУ. Реальная скорость обмена оказалось, намного меньше, чем заявленная производителем, связано это с латентностью и временем, затрачиваемым на организацию функций обмена; в) определены накладные расходы, возникающие в процессе обращения к памяти и при передаче данных на разных уровнях иерархии для КВС МЭИ и ХТУ. Полученный результат показал что эффективность выполнения ПП может существенно снизиться от 5% до десятков %.

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

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

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

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

4. Разработан алгоритм назначения ФПП на вычислители КВС основанный на эволюционных алгоритмов[24].

5. Написана параллельная MPI программа расчета освещенности виртуальных экранов (ЗО-рефрактограмм) и визуализации освещенности экрана в интерференционной схеме для модели сферически неоднородной среды.

6. На основе оптимизационной модели задачи назначения разработанной имитационной модели и ГА назначения, который реализован в программный продукт. Использования данной программы позволяет автоматизировать процесс выбора эффективного варианта назначения для заданных исследуемых классов задач. Применения предложенной оптимизационной модели задачи назначения позволило решить задачу назначения для множества задач, такие как, перемножения матриц, решения задачи надежности [3], расчета изображения светового излучения в трехмерном пространстве для оптически сферической неоднородной среды.

7. Предложенный ГА назначение имеет достаточно простое программное реализация. Затраты времени на поиск варианта эффективного назначения на порядки меньше чем при полном переборе. а) рассчитан доверительный интервал для разработанного ГА поиска варианта эффективного назначения, который показал узкий диапазон сходимости результатов для выбранных тип задач. Так же было доказана адекватность разработанной модели на примере перемножения матриц. б) отметим, что разработанный ГА назначения может быть использован для улучшения разработанных алгоритмов назначения. Так же разработанная имитационная модель выполнения ПП на КВС может быть использована для других алгоритмов назначения.

8. Приведены критерии для анализа эффективности разработанного ГА назначения по сравнению с другими алгоритмами или полным переборам.

9. Проведены экспериментальные исследования эффективности разработанного ГА назначения на КВС МЭИ, МГУ, ХТУ. Полученный результат продемонстрировал повышение эффективности выполнения ПП на 612% по сравнению с алгоритмом назначения, заложенным в планировщике КВС, или другими эвристическими методами.

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

10. На основания проведенных в диссертации исследований и разработанного алгоритма назначения, была разработана методика назначения ФПП на вычислители КВС.

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

2. Кутепов В. П. Интеллектуальное управление процессами и загруженностью в вычислительных системах/Изв. РАН ТиСУ 2007.№ 5

3. Яньков Сергей Георгиевич. Исследование и разработка методики отображения задач на кластерные системы с иерархически-неоднородной коммуникационной средой диссертация 2009.-168с

4. Тиц П. Г. Организация параллельных вычислений на многомашинных(многопроцессорных) вычислительных системах — диссертация 1975.-142 с.

5. Хорошевский В. Г. Архитектура вычислительных систем изд. МГТУ имени Н.Э.Баумана, 2008. 520с.

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

7. Ладыгин И.И. Курс лекций «Вычислительные системы».8. http://www.supercomputers.ru

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

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

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

11. HyperTransport Consortium official website http://www.hypertransport.org14. www.intel.com

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

13. Курносов М.Г. Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы. диссертация 2008.

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

15. Рахман Павел Азизурович. Разработка методики повышения эффективности использования вычислительных ресурсов при применении технологии виртуальных машин : Дис. . канд. техн. наук : 05.13.13 : Москва, 2005 400 с

16. Немнюгин С.А., Стесик O.JI. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ - Петербург, 2002.-400 с.21. "Вычислительная математика и структура алгоритмов.".-М.: Изд-во МГУ, 2006.-112 с.

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

18. Введение в математическое моделирование: Учеб. Пособие/ Под ред. П.В. Трусова. М.: Университетская книга, Логос, 2007.-440 с.

19. Эволюционная кибернетика: курс лекции/ Редько В.Г. Интернет адрес: http://www.keldysh.ru/pages/BioCyber/Lectures.html

20. Цой Ю.Р. Нейроэволюционный алгоритм и программные средства для обработки изображений диссертация,2007. - 209 с.

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

22. Во М.Т. Исследование решения прикладных задач на кластерах Магистерская диссертация — М.: — 116 с

23. Барун С.М. Исследование эффективности решения сильносвязных и среднесвязных задач на кластерных системах. Магистерская диссертация -М.: -266 с.29. http://www.citforum.ru

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

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

26. Энциклопедия / Сост. А.А. Грицанов, B.JI. Абушенко, Г.М. Евелькин, Г.Н. Соколова, О.В. Терещенко. Мн.: Книжный Дом, 2003. - 1312 с

27. Нгуен Ван Тханг. Расчет освещенности экрана астигматическим пучком при распространении его в неоднородной среде диссертация 2009.

28. Барский А.Б., Две задачи оптимизации использования неоднородных вычислительных систем, "Известие АН СССР", Техническая кибернетика №4 1971.

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

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

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

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

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

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

35. Корнеев В.В. Параллельные вычислительные системы. — М.: Нолидж, 1999. — 320 с.

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

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

38. В л.В.Воеводин, С.А.Жуматий. Вычислительное дело и кластерные системы.

39. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления.

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