Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы

Курносов, Михаил Георгиевич

Вычислительные машины и системы

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

кандидата технических наук: Курносов, Михаил Георгиевич
город: Новосибирск
год: 2008
специальность ВАК РФ: 05.13.15
цена: 450 рублей

Диссертация по информатике, вычислительной технике и управлению на тему «Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы»

Автореферат диссертации по теме "Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы"

Курносов Михаил Георгиевич

МОДЕЛИ И АЛГОРИТМЫ ВЛОЖЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

003453772

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

Курносов Михаил Георгиевич

МОДЕЛИ II АЛГОРИТМЫ ВЛОЖЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

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

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

профессор

член-корреспондент РАН Хорошевский Виктор Гаврилович

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

профессор

лауреат государственной премии СССР Рынков Александр Дмитриевич

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

Резник Александр Львович

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

Защита состоится "У/" д&мьЗЪ^ 2008 г. В " /У " часов на заседании Диссертационного совета^ 219.(/05.02 при ГОУ ВПО "Сибирский государственный университет телекоммуникаций и информатики", по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО "СибГУТИ".

Автореферат разослан " 7 " _2008 г.

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

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

доцент ДА)__- Иван Иванович Резван

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

Актуальность работы. Возрастающая потребность в решении сложных задач науки и техники привела к созданию распределенных вычислительных систем (ВС). В архитектурном плане распределенная ВС представляется множеством взаимодействующих элементарных машин, оснащенных средствами коммуникаций и внешними устройствами. Элементарная машина (ЭМ) - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ. Все основные ресурсы распределенных ВС (арифметико-логические устройства, память, средства управления и коммуникаций) являются логически и технически рассредоточенными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в МВС-15000ВМ число процессоров равно 1148, в IBM Roadrunner- 122400, а в системах IBM BlueGene второго поколения до 884736).

Современные распределенные ВС являются мультиархитектурпыми. В зависимости от уровня рассмотрения их функциональных структур, они могут выглядеть и как MISD, и как SIMD, и как MIMD системы. Для таких систем характерны иерархическая организация и различные пропускные способности каналов связи между их ресурсами (вычислительными узлами, ЭМ, процессорами и их ядрами).

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

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

Исследования в области распределенных ВС ведутся с середины XX столетия. В нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы: "Минск-222", СУММА, МИНИМАКС. МИКРОС, МВС и др.

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли выдающиеся учёные, среди которых: Е. П. Балашов, В. Б. Ветелин, В. С. Бурцев, В. В. Васильев, В. В. Воеводин, В. М. Глушков, В. Ф. Евдокимов, Э. В. Евреинов,

A. В. Забродин, В. П. Иванников, М. Б. Игнатьев, А. В. Каляев, И. А. Каляев, JI. Н. Королев, В. Г. Лазарев, С. А. Лебедев, В. К. Левин, Г. И. Марчук,

B. А. Мельников, Ю. И. Митропольский, Д. А. Поспелов, И. В. Прангишвили, Д. В. Пузанков, Г. Е. Пухов, А. Д. Рычков, Г. Г. Рябов, А. А. Самарский, В. Б. Смолов, А. Н. Томилин, Я. А. Хетагуров, В. Г. Хорошевский, Б. Н. Четверушкин, Ю. И. Шокин, H. Н. Яненко, S. Cray, M. Flynn, I. Foster,

A. Gara, D. Grice, D. Hillis, C. Kesselman, D. L. Slotnick и другие.

B. Л. Береснева, Э. X. Гимади, В. Т. Дементьева, С. В. Емельянова, Ю. И. Журавлева, А. А. Корбут, С. К. Коровина, Ю. С. Попкова, К. В. Рудакова, D. P. Agrawal, R. Baraglia, S. H. Bokhari, P. Bouviy, A. Gara, G. Karypis, B. W. Kernighan, V. Kumar, S. Lin, C. H. Papadimitriou, R. Perego, K. Steiglitz и др.

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

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

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

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

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

3. Создание методов и алгоритмов вложения параллельных программ в пространственно-распределенные ВС.

4. Разработка программного инструментария оптимизации вложения параллельных MPI-программ в ВС на базе многоядерных процессоров.

5. Формирование средств анализа производительности параллельных MPI-программ.

Методы исследования. Для достижения поставленной цели и решения

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

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

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

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

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

4. Реализованы алгоритм формирования в пространственно-распределенных ВС гомогенных подсистем и вложения в них параллельных программ.

5. Осуществлено параллельное моделирование разработанных алгоритмов на мультикластерной ВС Центра параллельных вычислительных технологий ГОУ ВПО "Сибирский государственный университет телекоммуникаций и информатики" (ЦПВТ ГОУ ВПО "СибГУТИ") и Лаборатории вычислительных систем Института физики полупроводников им. А. В. Ржанова СО РАН (ИФП СО РАН).

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

Созданные алгоритмы легли в основу пакета оптимизации вложения параллельных МРЬпрограмм в кластерные ВС. Применение реализованных средств позволяет сократить время выполнения параллельных программ.

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

Программные средства внедрены в действующую пространственно-распределенную мультикластерную вычислительную систему ЦПВТ ГОУ ВПО "СибГУТИ" и Лаборатории вычислительных систем ИФП СО РАН.

Реализация и внедрение результатов работы. Основные результаты диссертационной работы нашли применение в работах по созданию и развитию пространственно-распределенной мультикластерной вычислительной системы ЦПВТ ГОУ ВПО "СибГУТИ" и Лаборатории вычислительных систем ИФП СО РАН.

Диссертационные исследования выполнялись в рамках проекта №4.6.1.1 "Методы и алгоритмы анализа и организации функционирования распределенных вычислительных систем, параллельное мультипрограммирование и аппаратурно-программный инструментарий для моделирования технологий обработки информации" (программа 4.6.1 фундаментальных исследований СО РАН). Работа поддержана грантами Российского фонда фундаментальных исследований №08-07-00018 (научный руководитель - Курносов М. Г.), 08-07-00022, 06-07-89089, 05-07-90009, грантами Президента РФ по поддержке ведущих научных школ № НШ-9505.2006.9, НШ-2121.2008.9, стипендиальными грантами компаний Intel и Alcatel, а также грантом по Программе "У.М.Н.И.К." Фонда содействия развитию малых форм предприятий в научно-технической сфере.

Результаты диссертации внедрены в учебный процесс. Они использовались при чтении курсов лекций на Кафедре вычислительных систем ГОУ ВПО "СибГУТИ" по дисциплинам "Теория функционирования распределенных вычислительных систем" и "Высокопроизводительные вычислительные системы".

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на Международных, Всероссийских и региональных научных конференциях, в том числе: Международной научной конференции "Моде-лирование-2008" ("Simulation-2008", г. Киев, Украина, 2008 г.), Международной научной конференции "Информационные технологии и математическое моделирование систем" (г. Майорка, Испания, 2008 г.), Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" ("ICAM-2008", г. Томск, 2008 г.), Международной научной студенческой конференции "Студент и научно-технический прогресс (г. Новосибирск, 2006, 2007, 2008 гг.), Всероссийской научно-технической конференции "Информатика и проблемы телекоммуникаций" (г. Новосибирск, 2006,2007, 2008 гг.), Всероссийской научной конференции "Наука. Технологии. Инновации" (г. Новосибирск, 2007 г.), Сибир-

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

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

Основные положения диссертации, выносимые на защиту.

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

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

3. Последовательный и параллельный стохастические алгоритмы вложения параллельных программ в пространственно-распределенные ВС.

4. Алгоритмы формирования в пространственно-распределенных ВС однородных подсистем и вложения в них параллельных программ.

5. Программный инструментарий оптимизации вложения параллельных МР1-программ в ВС на базе многоядерных процессоров.

6. Средства анализа производительности параллельных МР1-программ.

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

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

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

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

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

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

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

накладных расходов на межмашинные обмены информацией и дисбаланса загрузки ЭМ.

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

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

Применимость известных методов и алгоритмов вложения параллельных программ в современные распределенные ВС ограничена рядом причин. 1) Часть известных алгоритмов опираются на модели ВС, которые неадекватны мульгиархитектурной организации современных систем. Многие описанные в литературе алгоритмы изначально ориентированы на ВС с однородной структурой сети межмашинных связей (например, в виде гиперкуба, 3£>-тора или Д,-графа). 2) В ряде работ учитывается лишь структура информационного графа программы и игнорируются объемы и интенсивности обменов данными между ветвями параллельной программы. Однако, учет таких параметров практически необходим.

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

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

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

п! - количество элементов на уровне / е {1, 2, ...,£}; пц~ количество прямых дочерних узлов элемента к е {1,2,..., nj), находящегося на уровне /; g(l, кк2) - номер уровня, на котором находится элемент, являющийся ближайшим общим предком для элементов к\, к2 е {1,2,..., щ} с уровня /; bi - значение пропускной способности каналов связи на уровне 1 ([¿J = байт/с); С/* - множество элементарных машин, принадлежащих потомкам элемента А; с уровня /; сд = )С/*|; Си = С\ С — {1,2, ..., N}.

На рис. 1 приведен пример иерархической организации коммуникационной среды вычислительного кластера из трех двухпроцессорных узлов на базе двухъядерных процессоров AMD Opteron 275. В качестве элементарных машин выступают процессорные ядра. Первый уровень коммуникационной среды образован сетью связи стандарта InfiniBand, через которую взаимодействуют узлы; второй уровень представлен шиной HyperTransport, через которую взаимодействую процессоры узла; третий уровень - средства доступа процессорных ядер к их общей памяти.

|1 |2| |ЗМ| |5|6| |7|а| |9|10] Irjftz] ЗМ (про^корнье ядра)

Рис. 1. Пример иерархической организации коммуникационной среды ВС: N= 12; L = 3; л23 = 2; С23 = {9,10, И, 12}; g(3, 3, 4) = 2; z( 1, 7) = 1

Параллельная программа характеризуется информационным графом G = (V,E), где V= {1, 2,..., М} - множество ветвей программы; £сСхК - множество информационно-логических связей между ветвями (обмены информацией). Через dv обозначен вес ребра (i,j) е Е, отражающий объем данных, передаваемых по нему за время выполнения программы ([d,j] = байт)

Вложение параллельной программы в ВС определяется инъективной функцией /: С, ставящей в соответствие ветвям программы элементарные машины системы. Функция / задается значениями х,/. Х= {хц | » е V,j е С};хц = 1, если_/[*) =_/', их0 = 0 в противном случае.

Время Т выполнения параллельной программы с заданным вложением X определяется максимальным из времен выполнения ее ветвей. Время взаимодействия между ветвями / и j, назначенными на ЭМ р и q, соответственно, выражается как d4 / Ь,(я ч) (для оценки времени передачи данных используется модель Хокни (R. Hockney)). Функция :{р, q) ставит в соответствие ЭМ р и q

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

Требуется построить вложение X, доставляющее минимум времени Т выполнения параллельной программы.

(м N N ]

Т(Х) = тах< НЕЕ х,р ■ xjq ■ d f -> min (1)

при ограничениях:

£ xv = 1, /' = 1,2, ..., M, (2)

/=1 м

5>V<1, j=l,2,...,N, (3)

/=1

x,j e {0,1}, / 6 V, j € C. (4)

Ограничения (2), (4) гарантируют назначение каждой ветви параллельной программы на единственную ЭМ, ограничения (3) обеспечивают назначение на машину не более одной ветви параллельной программы.

Задача (1) - (4) является трудноразрешимой. Для её решения предложены метод TMGP и алгоритм TMMGP вложения параллельных программ в ВС с иерархической организацией коммуникационных сред.

В методе TMGP вложение параллельной программы формируется путем разбиения её информационного графа на к = [(М- 1)/ cL{\ + 1 подмножеств F,, V2,V/t, так, чтобы \V,\ < с/Л /=1,2, к. Ветви из подмножества V, вкладываются в ЭМ с номерами из С/.,. Разбиение графа строится с целью минимизации максимальной суммы весов ребер, инцидентных любому подмножеству V,. В качестве веса ребра (и, v), инцидентного подмножествам V, и Vp берется значение d,n / Ь^/ , Это обеспечивает локализацию в каждом из подмножеств ветвей, обменивающихся большими объемами данных, что приводит к сокращению времени межмашинных обменов. На основе метода TMGP и многоуровневых схем разбиения графов (Barnard S. Т., Hendrickson В. А., Karypis G., Kumar V., Leland R.) создан алгоритм TMMGP.

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

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

Гтср= 0(TGP + М), Т7ШЮР = ОЩХо&к), Тп-;ат~ 0(N2 + М |£|),

где top - трудоемкость алгоритма разбиения графа на к подмножеств.

Натурные эксперименты по вложению параллельных MPI-программ из пакетов NAS Parallel Benchmarks, SPEC МР12007 и High-Performance Linpack в действующие вычислительные кластеры подтвердили результаты численного моделирования работы алгоритмов и адекватность используемых моделей. В экспериментах использовались SMP-кластеры на базе многоядерных процессоров компаний Intel и AMD. Количество ЭМ в системах варьировалось от 10 до 32. Коммуникационные среды кластеров построены на базе технологий Fast и Gigabit Ethernet.

В среднем, время выполнения тестовых MPI-программ с вложением алгоритмами TMMGP и TMGT было в 1,46 раз меньше времени выполнения программ с вложением средствами библиотек MPI (MPICH2 и OpenMPI).

Вложения в ВС параллельных программ, для которых не заданы информационные графы, осуществляется путем формирования подсистем элементарных машин и распределения по ним ветвей. Формируемая подсистема должна обеспечивать эффективную реализацию коллективных схем межмашинных обменов информацией. В качестве показателя, характеризующего эффективность подсистемы X, используется среднее геометрическое значение L(X) кратчайших расстояний 1РЧ (в смысле теории графов) в структуре ВС между ЭМ (р, q е{1, 2, ..., и}). Через Х= {хихг, обозначен вектор, за-

дающий номера ЭМ, входящих в подсистему; п - количество ЭМ в системе; хр = 1, если ЭМ р включена в подсистему, иначе хр = 0.

Требуется найти такие хр, чтобы значение ЦХ) было минимальным.

L(X) = при ограничениях:

.....РЛЧ^РЧ ' ■ \ ,r \

р=1 q=p+l J Iлр>

п-1 п У'(п-1) . /с-,

П II (W«-1) + 1) Fl ' ( )

Цхр=М, (6)

р= 1

хр е {0, 1}, р = 1, 2, ..., п. (7)

Для систем с иерархической организацией коммуникационных сред в качестве функции (5) рассматривается показатель В(Х)

' П-1 п 1и(я-1) /0\

В(Х)= П П (хрхд(Ьрч-\)+\)\ <8>

(,/7=1 д=р +1 )

и задача (8), (6), (7) решается на максимум; Ьрч - пропускная способность каната связи между ЭМ р и д

Для решения задач (5) - (7) и (8), (6), (7) предложены нетрудоемкие алгоритмы РАСБ и РАбСБ поиска субоптимальных решений. Алгоритм РЛСЭ формирует подсистему, включая в её состав ЭМ, находящиеся на минималь-

ном среднем расстоянии от машин подсистемы.

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

Трудоемкости алгоритмов составляют:

Tpags = 0(п\ TPAGCS = 0(п2 + п тах{п, \Е\)), где Е' - множество ребер структуры ВС.

Проведено моделирование работы алгоритмов на моделях кластерных ВС и системах с однородными структурами (рассматривались 20-решетки, гиперкубы и D„-графы). В среднем алгоритм PAGS формировал подсистемы по значению целевых функций (5), (8) в 1,1 - 3 раза лучше известных алгоритмов PAL и PAR. Алгоритм PAL формирует подсистему из М первых доступных ЭМ; алгоритм PAR выделят случайное подмножество М доступных элементарных машин.

Созданные алгоритмы рекомендованы к использованию в MPI-библиотеках для оптимизации вложения параллельных программ и формирования виртуальных топологий (функции MPI_Graph_create, MPI_Cart_create), а также в средствах управления ресурсами распределенных ВС (например, TORQUE) для выделения субоптимальных подсистем ЭМ.

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

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

Время выполнения параллельных программ на пространственно-распределенных ВС включает время доставки файла программы и данных до ЭМ, выделенных для выполнения её ветвей.

Вложение осуществляется с подсистемы se {1, 2,..., Н). Требуется найти х,р доставляющие минимум времени Т выполнения программы и удовлетворяющие ограничениям (2) - (4).

í к ] í n w м n n i

т'(х) = max £ /(s,v(/>),z)U max £ х,„--+ £ I Y.hp-*lq Аи>Р>Я)Г (9)

leV [p=l J |p=l a>v(p) ]=\p=\q=\ )

где t{s, v(p), z) - время передачи сообщения размером z байт между подсистемами s и v(p)\ v(p) - номер подсистемы, которой принадлежит элементарная машина р\ w, - количество элементарных операций (арифметических и логических), выполняемых ветвью íe V параллельной программы; cOj - производительность ЭМ подсистемы j ([ц] = FLOPS); í(i,J,p, q) - время

взаимодействия между ветвями i,je. V, назначенными на элементарные машины р и q, соответственно.

Для приближенного решения задачи (9), (2) - (4) вложения параллельных программ в пространственно-распределенные ВС предложен стохастический алгоритм TMSA. Для большемасштабных ВС предложена его параллельная версия TMPSA. Алгоритм TMSA основан на метаэвристике "имитация отжига" (Simulated Annealing, Kirkpatrick S., Ingberg L.). На каждом шаге в окрестности текущего решения А'осуществляется случайный выбор нового решения X'. Векторы Xи X' сравниваются по значению целевой функции (9). За текущее принимается решение с меньшим значением целевой функции. Кроме того, даже если соседнее решение А" по целевой функции превосходит чек) -щее А', то с заданной вероятностью решение X' принимается за текущее. Данный шаг позволяет алгоритму не "застревать" в локальных минимумах и исследовать большее количество допустимых решении.

Для вложения параллельных программ в подсистемы пространственно-распределенных ВС предложен алгоритм TMDS. В алгоритм введен параметр 5, который позволяет приоритезировать выбор подсистем по производительности ЭМ и скорости передачи данных по каналам межмашинных связей. Алгоритм осуществляет рекурсивный обход дерева коммуникационной среды системы. Среди дочерних подмножеств текущего узла С/к, в зависимости от значения параметра 5, выбирается подмножество С ¡г с максимальным значением производительности его ЭМ или каналов связи между ними. Обход подмножеств Сдпродолжается до тех пор, пока в состав подсистемы не будет включено количество ЭМ достаточное для реализации параллельной программы. После чего, как и в алгоритме TMGT, осуществляется обход информационного графа программы и распределение ветвей по ЭМ.

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

В качестве оценок эффективности работы алгоритмов TMSA и TMDS рассматривались величины: Oi = (F-F{) / Fx, 62 = (F-F2)/F:, где F\, F2, F- значения целевой функции от решения, получаемого алгоритмом TMSA, TMDS и случайным вложением, соответственно. Рассматривались модели пространственно-распределенных мультикластерных ВС с конфигурациями подсистем типичными для систем из списка Тор500. Моделирование показало, что качество формируемых алгоритмами вложений, по значениям показателей 5, и 52, на один - два порядка превосходит случайное распределение ветвей по ЭМ. Качество формируемых вложений возрастает с увеличением количества уровней в коммуникационной среде системы и разброса значений показателей производительностей каналов связи на них.

Предложенный алгоритм ТМРБЛ характеризуется ускорением, близким к линейному, и предназначен для вложения программ с количеством

Рис. 2. Пример вложения параллельной программы в распределенную ВС алгоритмом TMDS: 8~ 0; Л' = 18; Af- 9

Трудоемкости предложенных алгоритмов составляют:

Тпш = 0(тах{М + Н, Я-К-М2}), Тпш = 0(max{h N2, М+1£|}), где R, К- параметры алгоритма TMS A, h— высота дерева коммуникационной среды пространственно-распределенной ВС.

Для формирования в пространственно-распредленных ВС гомогенных подсистем предложен алгоритм PADS. Однородные подсистемы формируются с сохранением заданного уровня коэффициента вариации производительности ЭМ в подсистеме. После чего осуществляется рекурсивный обход дерева коммуникационной среды и включения элементарных машин из подмножеств С¡t так, чтобы значение целевой функции (8) было максимальным, а подсистема удовлетворяла ограничениям (6) - (7). Трудоемкость алгоритма PADS равна TPADS = 0(h-N2).

Алгоритм позволяет формировать эффективные подсистемы по значению показателя В{Х) в распределенных ВС с иерархической организацией коммуникационных сред. Его возможности по созданию подсистем с рангом, не превышающим количества ЭМ в подсистемах, ограничены.

Предложенные алгоритмы ориентированы на использование в GRID-брокерах (GRID-диспетчерах) для минимизации времени выполнения параллельных программ на пространственно-распределенных ВС.

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

Система объединяет 8 пространственно-распределенных кластерных ВС, причем кластеры A-F расположены в ЦПВТ ГОУ ВПО "СибГУТИ", а кластеры G, Н - в Лаборатории ВС ИФП СО РАН. Любой из кластеров способен функционировать как автономно так и в составе распределенной ВС. В каче-

стве базовых составляющих для построения кластеров A-D, H использованы стандартные персональные компьютеры на базе процессоров компании Intel. Кластер G состоит из б двухпроцессорных узлов, каждый из которых представляет собой систему N1JMA на базе процессоров AMD Opteron 248, кластер Е укомплектован 4 двухпроцессорными узлами на базе двухядерных процессоров Intel Xeon 5150. Кластер F оснащен четырехъядерными процессорами Intel Xeon Е5345, в состав кластера включено 32 вычислительных ядра с суммарной производительностью 298 GFLOPS.

Рис. 3. Конфигурация пространственно-распределенной мультшсласгерной ВС

Коммуникационные среды вычислительных кластеров построены на базе технологий Gigabit и Fast Ethernet. Для объединения кластеров используется сеть Internet (технология VPN). Связь осуществляется через выделенные серверы сегментов ЦПВТ ГОУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН. Система включает больше 100 процессоров и имеет пиковую производительность 690 GFLOPS.

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

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

Для анализа производительности MPI-программ и автоматизации формирования их информационных графов разработано программное средство OTFStat. Поддерживаются протоколы выполнения MPI-программ в формате Open Trace Format (OTF). Созданное средство позволяет получать информацию о структуре обменов между параллельными ветвями, дисбалансе их загрузки и коэффициентах накладных расходов.

Разработанные программные средства позволяют повысить эффективность эксплуатации ресурсов распределенных ВС при выполнении параллельных MPI-программ.

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

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

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

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

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

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

1.2. Предложены метод и эффективные алгоритмы вложения параллельных программ в иерархические ВС. Алгоритмы в сравнении со стандартными средствами сокращают время выполнения промышленных MPI-программ в 1,5 - 2 раза.

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

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

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

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

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

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

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

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

Основные результаты диссертации опубликованы в работах [1-31].

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Хорошевский, В Г Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем / В Г Хорошевский, M Г Курносов II Автометрия -2008 -Т 44, №2 - С 56-67

2 Курносов, M Г Опыт построения кластерных вычислительных систем с удаленной загрузкой узлов / M Г Курносов // Материалы пятого Международного научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах" -Нижний Новгород Изд-во ННГУ, 2005 - С 149-154

j Курносов, M Г, Задача стохастически оптимального распределения машин по терминалам распределенной вычислительной системы / M Г Курносов // Материалы XL1V Международной научной студенческой конференции "Студент и научно-технический прогресс" - Новосибирск Изд-во НГУ, 2006 - С 16-17

4 Курносов, M Г Построение учебных кластерных вычислительных систем с удаленной загрузкой узлов / M Г Курносов // Вестник СибГУТИ "Тенденции модернизации высшего образования" -Новосибирск Изд-во СибГУТИ, 2006 - С 52-54

5 Курносов, M Г Об одной задаче организации стохастически оптимального функционирования распределенных вычислительных систем / M Г Курносов // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" - Новосибирск Изд-во НГУ, 2006 - С 63-66

6 Курносов,M Г, Об одной задаче оптимального назначения ветвей параллельной программы «а процессорные ядра распределенной вычислительной системы / M Г Курносов, А В Половинквн // Материалы Международной научной конференции "Студент и научно-технический npoipecc" - Новосибирск . НГУ, 2007 - С 41

7 Курносов, M Г Планирование выполнения параллельных программ набора на распределенной вычислш-ельной системе / M Г. Курносов, С В Рыбалко // Материалы XLV Международной научной студенческой конференции "Студент и научно-технический прогресс" - Новосибирск Изд-воНГУ,2007 -С 42-43

8 Курносов, M Г Задача назначения ветвей параллельной программы на процессорные ядра распределенной вычислительной системы / M Г Курносов, А В ГТоловинкин // Материалы Российской научной конференции "Информатика и проблемы телекоммуникаций" - Новосибирск Изд-во СибГУТИ, 2007 - С 270-272

9 Курносов, M Г Синтез расписания запуска параллельных программ на распределенной вычислительной системе / M Г Курносов, С В Рыбалко // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" - Новосибирск Изд-во СибГУТИ, 2007 -С 272-274

10 Курносов, M Г Оптимизация выполнения параллельных MPI-программ на мультикла-стерных вычислительных системах / M Г Курносов // Материалы Сибирской школы-семанара по параллельным и высокопроизводительным вычислениям - Томск ТГУ, 2007. - С 168-175

11 Курносов. M Г. Назначение ветвей параллельной программы на процессорные ядра распределенной вычислительной системы / M Г Курносов // Материалы Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы". -Таганрог Изд-во ТТИ ЮФУ, 2007 - T 1 - С 227-231

12 Курносов, M Г Алгоритмы распределения ветвей параллельных программ по процессорным ядрам мультикластерных вычислительных систем / M Г Курносов // Материалы Всероссийской научной конференции "Наука Технологии Инновации" - Новосибирск НГТУ, 2007 - С 258-260

13 Курносов, M Г Разработка программного средства анализа параллельных MPI-программ /МГ. Курносов // Тезисы докладов Всероссийской конференции молодых ученых ¡¡о математическому моделированию и информационным технологиям - Новосибирск ИВТ СО РАН, 2007 - С 101

14 Курносов, M Г Об оптимизации распределения ветвей параллельных MPI программ по процессорным ядрам вычислительного кластера / M Г Курносов, А А Пазников II Материалы седьмой Международной конференции-семинара "Высокопроизводительные вычисления на кластерных, системах" - Нижний Новгород Изд-во ННГУ,2007 - С 218-225

15 Курносов, M Г Параллельный алгоритм отображения информационного графа MPI-программы на процессорные ядра распределенной вычислительной системы / M Г Курносов // Труды Международной научной конференции "Параллельные вычислительные технологии" -Челябинск Изд-во ЮУрГУ, 2008 - С 532

16 Курносов, M Г Оптимизация вложения параллельных программ в однородные вычислительные кластеры / M Г Курносов // Материалы Всероссийской научной конференции "Молодежь и современные информационные технологии" - Томск ТПУ, 200S -С 43-44

17 Курносов, M Г Применение средств анализа производительности MPI-программ при подготовке специалистов в области параллельных вычислительных технологий IM Г Курносов // Тезисы докладов научно-методической конференции "Проблемы перехода на многоуровневую систему образования" - Новосибирск СибГУТИ, 2008 - С. 39

18 Курносов, М. Г. Вложение параллельных программ в однородные вычислшельные системы / M Г Курносов // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций". - Новосибирск • СибГУТИ, 2008 - Т. 1 - С 138-140

19 Курносов, M Г Средства оптимизации вложения MPI-программ в вычислительные кластеры / M Г. Курносов, А, H Парыгин // Материалы Российской научно-технической конферен-

ции "Информатика и проблемы телекоммуникаций" - Новосибирск СибГУТИ, 2008 - Т 1 -С 140-141

20 Курносов, М Г Применение иерархических методов разбиения графов для вложения параллельных программ в вычислительные системы / М Г Курносов // Материалы III Международной научно-технической конференции "Инфокоммуникационные технологии в науке, производстве и образовании (Инфоком-3)" -Ставрополь СевКавГТУ,2008 -Ч 1 -С 76-82

21 Мамойленко, С Н Использование мультикластерной вычислительной системы для подготовки специалистов в области параллельных вычислительных технологий /СИ Мамойленко, М Г Курносов [и др ] // Тезисы докладов XLIX научно-методической конференции "Проблемы перехода на многоуровневую систему образования" - Новосибирск СибГУТИ, 2008 - С 38

22 Курносов, М Г Об организации функционирования вычислительных систем с оптимизацией вложения параллельных программ / М Г Курносов // Материалы Международной научной студенческой конференции "Студент и научно-технический прогресс" - Новосибирск НГУ, 2008 - С 217-218

23 Курносов, М Г Организация функционирования вычислительных систем с учетом архитектуры их коммуникационных сред / М Г Курносов // Материалы II Международной научной студенческой конференции "Научный потенциал студенчества - будущему России" - Ставрополь СевКавГТУ, 2008 -Т 3 -180с

24 Курносов, М Г Оптимизация вложения параллельных программ при диспетчеризации заданий в GRID-системах / М Г Курносов // Материалы Всероссийской конференции ' Современные информационные технологии для научных исследований" - Магадан СВНЦ ДВО РАН, 2008 -С 87-89

25 Курносов, М Г Моделирование алгоритмов вложения параллельных программ в вычис-лтельные кластеры на базе миогоядерных процессоров / М Г Курносов // Сборник статей третьей всероссийской зимней школы-семинара аспирантов и молодых ученых "Актуальные проблемы в науке и технике" - Уфа Диалог, 2008 - Т 1 -С 538-544

26 Хорошевский, В Г Моделирование алгоритмов вложения параллельных программ в структуры распределенных вычислительных систем / В Г Хорошевский, М Г Курносов // Труды Международной научной конференции "Моделирование-2008" (Simulation-200d) - Киев ИПМЭ НАН Украины, 2008 - Т 2 - С 435-440

27 Курносов, М Г Организация функционирования вычислительных систем с учетом их структур / М Г Курносов // Тезисы докладов Седьмой Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур (1САМ-2008)" - Томск НТЛ, 2008 - С 69

28 Хорошевский, В Г Архитектурные концепции, анализ и организация функционирования вычислительных систем с программируемой структурой / В Г Хорошевский, С Н Мамойленко, М Г Курносов // Труды Международной научной конференции "Информационные технологии и математическое моделирование систем" - М РАН, 2008

29 Курносов, М Г Эвристический алгоритм формирования подсистем а вычисли|ельных системах // Материалы 9 Международной научно-практической конференции "Искусственный интеллект-2008 Интеллектуальные системы" - Таганрог НИИ МВС ЮФУ, 2С08 -4 2 -С 346-351

30 Khoroshevsky, V G Space-distributed multi-cluster computer system for training ш parallel computational technologies / V G Khoroshevsky, S N Mamoilenlco, M G Kumosov, N A Medvedeva // Proceedings of 7th International Siberian Workshop and Tutorial (EDM-2006) -Erlagol IEEEPress, 2006 -P 218-219

31 Khoroshevsky, V G Algorithms for Assigning Parallel Program Branches to Computer System Processor Cores / V G Khoroshevsky, M G Kumosov // Optoelectronics, Instrumentation and Data Processing -2008 -Vol 44,№2 -P 135-143

Курносов Михаил Георгиевич

Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать "29" октября 2008 г. Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л. 1,6, заказ № 86, тираж 100 экз., ГОУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

Оглавление автор диссертации — кандидата технических наук Курносов, Михаил Георгиевич

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ С ПРОГРАММИРУЕМОЙ СТРУКТУРОЙ.

1.1. Понятие о распределенных ВС с программируемой структурой.

1.1.1. Модель коллектива вычислителей. Классификация ВС.

1.1.2. Архитектурные особенности ВС с программируемой структурой

1.1.3. Параллельные алгоритмы и программы.

1.2. Кластерные, и мультикластерные ВС и GRID-системы.

1.2.1. Принципы построения кластерных ВС.

1.2.2. Мультикластерные ВС и GRID-системы.

1.2.3. Разработка параллельных программ для кластерных ВС.

1.3. Основные режимы функционирования ВС.

1.3.1. Монопрограммный режим.

1.3.2. Мультипрограммные режимы.

1.4. Вложение параллельных программ в распределенные ВС.

1.4.1. Задача оптимального вложения параллельных программ.

1.4.2. Алгоритмы вложения параллельных программ.

1.4.3. Алгоритмы формирования подсистем в ВС.

1.4.4. Обзор средств вложения параллельных программ и формирования подсистем.

1.5. Выводы.

ГЛАВА 2. АЛГОРИТМЫ ВЛОЖЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ.

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

2.1.1. Модель ВС с иерархической организацией коммуникационной среды.

2.1.2. Оценка ожидаемого времени выполнения параллельных программ на вычислительных системах.

2.1.3. Задача оптимального вложения параллельных программ в ВС.

2.2. Иерархический метод вложения параллельных программ в ВС.

2.2.1. Задача оптимального разбиения графа на к непересекающихся подмножеств.

2.2.2. Метод вложения параллельных программ в ВС.

2.2.3. Многоуровневые методы разбиения графов.

2.2.4. Алгоритм вложения параллельных программ в ВС.

2.3. Эвристический алгоритм вложения параллельных программ в подсистемы ВС.

2.3.1. Модель подсистемы ВС с иерархической организацией коммуникационной среды.

2.3.2. Эвристический алгоритм вложения параллельных программ в подсистему ВС.

2.4. Оценка производительности ВС при реализации основных схем межмашинных обменов.

2.5. Алгоритмы формирования подсистем ВС.

2.6. Выводы.

ГЛАВА 3. АЛГОРИТМЫ ВЛОЖЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ.

3.1. Оптимизация вложения параллельных программ в пространственно-распределенные ВС.

3.1.1. Модель пространственно-распределенной ВС.

3.1.2. Организации выполнения параллельных программ на распределенной ВС.

3.1.3. Задача оптимального вложения параллельных программ в распределенную ВС.

3.2. Стохастический алгоритм вложения параллельных программ в пространственно-распределенные ВС.

3.2.1. Последовательный алгоритм вложения.

3.2.2. Параллельный алгоритм вложения.

3.3. Алгоритм вложения параллельных программ в подсистемы пространственно-распределенных ВС.

3.4. Алгоритм формирования подсистем в пространственно-распределенных ВС.

3.4.1. Показатель однородности подсистемы распределенной ВС.

3.4.2. Алгоритм формирования подсистем.

3.5. Выводы.

ГЛАВА 4. ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННАЯ МУЛЬТИКЛАСТЕРНАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА.

4.1. Архитектура пространственно-распределенной мультикластерной вычислительной системы.

4.2. Программное обеспечение мультикластерной ВС.

4.2.1. Стандартные компоненты.

4.2.2. Средства оптимизации вложения параллельных МР1-программ.

4.2.3. Средства анализа параллельных MPI-программ.

4.3. Моделирование алгоритмов вложения параллельных программ в распределенные ВС.

4.4. Моделирование алгоритмов формирования подсистем в распределенных ВС.

4.5. Выводы.

Введение 2008 год, диссертация по информатике, вычислительной технике и управлению, Курносов, Михаил Георгиевич

Актуальность работы. Возрастающая потребность в решении сложных задач науки и техники привела к созданию распределенных вычислительных систем (ВС) [27, 95]. В архитектурном плане распределенная ВС представляется множеством взаимодействующих элементарных машин, оснащенных средствами коммуникаций и внешними устройствами. Элементарная машина (ЭМ) - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах — от процессорного ядра до ЭВМ. Все основные ресурсы распределенных ВС (арифметико-логические устройства, память, средства управления и коммуникаций) являются логически и технически рассредоточенными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в МВС-15000ВМ число процессоров равно 1148, в IBM Roadrunner— 122400, а в системах IBM BlueGene второго поколения до 884736).

Современные распределенные ВС являются мультиархитектурны-ми [92, 94, 95]. В зависимости от уровня рассмотрения их функциональных структур, они могут выглядеть и как MISD, и как SIMD, и как MIMD системы. Для таких систем характерны иерархическая организация и различные пропускные способности каналов связи между их ресурсами (вычислительными узлами, ЭМ, процессорами и их ядрами).

Время выполнения параллельных программ на распределенных ВС существенно зависит от того насколько они эффективно вложены в систему [40-45, 90, 93, 106-107, 116, 133, 144, 164]. Под эффективным вложением понимается такое распределение ветвей параллельной программы между ЭМ системы, при котором достигаются минимумы накладных расходов на межмашинные обмены информацией и дисбаланса загрузки ЭМ.

Исследования в области распредёленных ВС ведутся с середины XX столетия. В нашей стране и за рубежом выполнен ряд фундаментальных работ, посвящённых проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы: "Минск-222", СУММА, МИНИМАКС, МИКРОС, МВС и др.

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли выдающиеся учёные, среди которых: Е. П. Балашов, В. Б. Бетелин, В. С. Бурцев, В. В. Васильев, В. В. Воеводин, В. М. Глушков, В. Ф. Евдокимов, Э. В. Евреинов,

B. А. Мельников, Ю. И. Митропольский, Д. А. Поспелов, И. В. Прангишвили, Д. В. Пузанков, Г. Е. Пухов, А. Д. Рычков, Г. Г. Рябов,

A. А. Самарский, В. Б. Смолов, А. Н. Томилин, Я. А. Хетагуров,

B. Г. Хорошевский, Б. Н. Четверушкин, Ю. И. Шокин, Н. Н. Яненко, S. Cray, М. Flynn, I. Foster, A. Gara, D. Grice, D. Hillis, C. Kesselman, D. L. Slotnick и другие.

При решении проблем оптимизации вложения параллельных программ в распределенные ВС большую роль сыграли фундаментальные работы по исследованию операций и оптимальному управлению выдающихся ученых: В. Л. Береснева, Э. X. Гимади, В. Т. Дементьева, С. В. Емельянова, Ю. И. Журавлева, А. А. Корбут, С. К. Коровина, Ю. С. Попкова, К. В. Рудакова, D. P. Agrawal, R. Baraglia, S. Н. Bokhari, P. Bouvry, A. Gara, 8

G. Karypis, В. W. Kernighan, V. Kumar, S. Lin, С. H. Papadimitriou, R. Perego, K. Steiglitz и др.

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

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

3. Создание методов и алгоритмов вложения параллельных программ в пространственно-распределенные ВС.

5. Формирование средств анализа производительности параллельных MPI-программ.

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

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

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

Созданные алгоритмы легли в основу пакета оптимизации вложения параллельных MPI-программ в кластерные ВС. Применение реализованных средств позволяет сократить время выполнения параллельных программ.

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

Диссертационные исследования выполнялись в рамках проекта №4.6.1.1 "Методы и алгоритмы анализа и организации функционирования распределенных вычислительных систем, параллельное мультипрограммирование и аппаратурно-программный инструментарий для моделирования технологий обработки информации" (программа 4.6.1 фундаментальных исследований СО РАН). Работа поддержана грантами Российского фонда фундаментальных исследований № 08-07-00018 (научный руководитель — Курносов М.Г.), 08-07-00022, 06-07-89089, 05-07-90009, грантами Президента РФ по поддержке ведущих научных школ № НШ-9505.2006.9, НШ-2121.2008.9, стипендиальными грантами компаний Intel и Alcatel, а также грантом по Программе "У.М.Н.И.К." Фонда содействия развитию малых форм предприятий в научно-технической сфере.

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

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

- Международной научной конференции "Моделирование-2008" ("Simulation-2008", г. Киев, Украина, 2008 г.).

- Международной научной конференции "Информационные технологии и математическое моделирование систем" (г. Майорка, Испания, 2008 г.).

-Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" ("ICAM-2008", г. Томск, 2008 г.).

- Международной научно студенческой конференции "Студент и научно-технический прогресс (г. Новосибирск, 2006, 2007, 2008 гг.).

- Всероссийской научно-технической конференции "Информатика и проблемы телекоммуникаций" (г. Новосибирск, 2006, 2007, 2008 гг.).

- Всероссийской научной конференции "Наука. Технологии. Инновации" (г. Новосибирск, 2007 г.).

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

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

Основные положения диссертации, выносимые на защиту.

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

5. Программный инструментарий оптимизации вложения параллельных MPI-программ в ВС на базе многоядерных процессоров.

6. Средства анализа производительности параллельных MPI-программ.

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

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

Заключение диссертация на тему "Модели и алгоритмы вложения параллельных программ в распределенные вычислительные системы"

Основные результаты диссертации опубликованы в работах [36-59, 66, 96-98, 150-151]. J i

ЗАКЛЮЧЕНИЕ

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

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

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

Библиография Курносов, Михаил Георгиевич, диссертация по теме Вычислительные машины и системы

1. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, В. Д. Хопкрофт, Дж. Д. Ульман ; пер. с англ. под ред. А. А. Минько. - Издательский дом "Вильяме", 2001. - 3 84 с.

2. Бабаян, Б. А. Многопроцессорные ЭВМ и методы их проектирования / Б.А.Бабаян, А. В. Бочаров, А. Волин. - М. : Высшая школа, 1990. -143 с.

3. Бетелин, В. Б. Архитектура цифровых процессоров обработки сигналов / В. Б. Бетелин и др... - М . : РАН, 1993. - 20 с.

4. Балашов, Е. П. Микро и мини-ЭВМ учеб. пособие для ВУЗов / Е. П. Балашов, В.Л. Григорьев, Г.А. Петров. - Л. : Энергоатомиздат, 1984. - 376 с.

5. Балашов, Е. П. Микропроцессоры и микропроцессорные системы / Е. П. Балашов, Д. В. Пузанков, В. Б. Смолов. - М. : Радио и связь, 1981. -326 с.

6. Барский, А. Б. Планирование параллельных вычислительных процессов / А. Б. Барский. - М.: Машиностроение, 1980. - 192 с.

7. Барский, А. Б. Параллельные процессы в вычислительных системах / А. Б. Барский. - М. : Изд-во "Радио и связь", 1990. - 256 с.

8. Береснев, В. Л. Экстремальные задачи стандартизации / В. Л. Береснев, Э. X. Гимади, В. Т. Дементьев. - Новосибирск : Наука, 1978. - 336 с.

9. Вальковский, В. А. Распараллеливание алгоритмов и программ. Структурный подход / В. А. Вальковский. - М. : Радио и связь, 1989. — 176 с.

10. Васильев, В. В. Многопроцессорные вычислительные структуры для анализа задач на сетях / В. В. Васильев, А. Г. Додонов // Проблемы электроники и вычислительной техники. - 1976. - №4. - 85-97.

11. Водяхо, А. И. Высокопроизводительные системы обработки данных / А. И. Водяхо, Н. Н. Горпец, Д. В. Пузанков. - М. : Высшая школа, 1997. -304 с.

12. Воеводин, В. В. Математические модели и методы в параллельных процессах / В. В. Воеводин. - М. : Наука, 1986. - 296 с.

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

14. Гергель, В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем / В. П. Гергель, Р. Г. Стронгин. - Нижний Новгород : Изд-во ННГУ, 2003. - 184 с.

15. Гери, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон ; пер. с англ. - М. : Мир, 1982. - 416 с.

16. Гимади, Э. X. Дискретные экстремальные задачи принятия решений / Э. X. Гимади, Н. И. Глебов. - Новосибирск : НГУ, 1991. - 76 с.

17. Грэхэм, Р. Конкретная математика. Основания информатики / Р. Грэхэм, Д. Кнут, О. Поташник ; пер. с англ. - 2-е изд. - М. : Мир, 2006. - 703 с.

18. Додонов, А. Г. Введение в теорию живучести вычислительных систем / А. Г. Додонов, М. Г. Кузнецова, Е. Горбачик. - Киев : Наук. Думка, 1990.-180 с.

19. Дмитриев, Ю. К. Вычислительные системы из мини-ЭВМ / Ю. К. Дмитриев, В. Г. Хорошевский. - М. : Радио и связь, 1982. - 304 с.

20. Евдокимов, В. Ф. Параллельные вычислительные структуры на основе разрядных методов / В. Ф. Евдокимов, А. И. Стасюк. - К.: Наукова думка, 1987.-311 с.

21. Евреинов, Э. В. О возможности построения вычислительных систем в условиях запаздывания сигналов / Э. В. Евреинов // Вычислительные системы. - 1962.-№ 3 . - С . 3-16.

22. Евреинов, Э. В. Однородные вычислительные системы, структуры и среды / Э. В. Евреинов. - М.: Радио и связь, 1981. - 208 с.

23. Евреинов, Э. В. Однородные универсальные вычислительные системы высокой производительности / Э. В. Евреинов, Ю. Г. Косарев. - Новосибирск : Наука. Сибирское отд-е, 1966. - 308 с.

24. Евреинов, Э.В. Однородные вычислительные системы / Э.В. Евреинов, В.Г. Хорошевский. - Новосибирск : Наука. Сибирское отд-е, 1978. - 319 с.

25. Каляев, А. В. Параллельный компьютер с программируемой под структуру задачи архитектурой / А. В. Каляев и др.. // Труды Шестого Международного семинара "Распределённая обработка информации". - Новосибирск: СО РАН, 1998. - 25-29.

26. Корнеев, В. В. Архитектура вычислительных систем с программируемой структурой / В. В. Корнеев. - Новосибирск : Наука, 1985. - 164 с. ЗЗ.Корнеев, В. В. Вычислительные системы / В. В. Корнеев. - М. : Гелиос АРВ,2004.-512с.

27. Косарев, Ю. Г. Распараллеливание по циклам / Ю. Г. Косарев // Вычислительные системы. - 1967. - Вып. 24. - 3-20. !

28. Курносов, М. Г. Построение учебных кластерных вычислительных систем с удаленной загрузкой узлов / М. Г. Курносов // Вестник СибГУТИ "Тенденции модернизации высшего образования". - Новосибирск: Изд-во СибГУТИ, 2006. - 52-54.

29. Левин, В. К. Современные суперкомпьютеры семейства МВС Электронный ресурс. / В. К. Левин. - Электрон, текст, дан. - Б. м., 2002. - Режим доступа : http://www.parallel.ru/mvs/levin.html.

30. Левитин, А. В. Алгоритмы: введение в разработку и анализ / A. В. Левитин ; пер. с англ. под ред. И. В. Красикова. - М. : Издательский дом "Вильяме", 2006. - 576 с.

31. Лопатин, А. Метод отжига / А. Лопатин. — Стохастическая оптимизация в информатике. - 2005. - Вып. 1.-С. 133-149.

32. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер ; пер. с англ. - М. : БИНОМ. Лаборатория знаний, 2006. - 406 с.

33. Миренков, Н. Н. Параллельное программирование для многомодульных вычислительных систем / Н. Н. Миренков. - М. : Радио и связь, 1989. -319 с.

34. Монахов, О. Г. Параллельные системы с распределенной памятью: структуры и организация взаимодействий / О. Г. Монахов, Э. А. Монахова. -Новосибирск : Изд-во СО РАН, 2000. - 242 с.

35. Монахов, О. Г. Параллельные системы с распределенной памятью: управление ресурсами и заданиями / О. Г. Монахов, Э. А. Монахова. - Новосибирск : Изд-во ИВМиМГ СО РАН, 2001. - 168 с.

36. Павский, В. А. Организация функционирования однородных вычислительных систем и стохастическое программирование / В. А. Павский, B. Г. Хорошевский // Вычислительные системы. - 1975. - Вып. 63. -C. 3-16.

37. Панфилов, И. В. Вычислительные системы / И. В. Панфилов, А. М. По- ловко. - М.: Изд-во "Советское радио", 1980. - 302 с.

38. Поспелов, Д. А. Введение в теорию вычислительных систем / Д. А. Поспелов. — М.: Изд-во "Советское радио", 1972. - 280 с.

39. Пискунов, В. Построение микропрограммных описаний однородных вычислительных структур / В. Пискунов // Моделирование дискретных управляющих и вычислительных систем. - Свердловск : СвердГУ, 1981. — 55-57.

40. Прангишвили, И. В. Параллельные вычислительные системы с общим управлением / И. В. Прангишвили, Я. Виленкин, И. Л. Медведев. -М. : Энергопромиздат, 1983. -313 с.

41. Прангишвили, И. В. Многопроцессорные и локальные сети микро-ЭВМ в распределенных системах управления / И. В. Прангишвили. - М. : Энерго-атомиздат, 1985. - 272 с.

42. Пухов, Г. Е. Разрядно-аналоговые вычислительные системы / Г. Е. Пухов, В. Ф. Евдокимов, М. В. Синьков. - М.: Советское радио, 1978. - 255 с.

43. Сайт проекта MPICH2 Электронный ресурс.. — Режим доступа : http://www.mcs.anl.gov/research/projects/mpich2/, свободный.

44. Сайт проекта OpenMPI Электронный ресурс.. - Режим доступа : http://www.open-mpi.org, свободный.

45. Сайт проекта Тор500 Электронный ресурс.. - Режим доступа : http://www.top500.org, свободный.

46. Сайт проекта TORQUE Электронный ресурс.. - Режим доступа : http://www.clusterresources.com/pages/products/torque-resource-manager.php, свободный.

47. Таненбаум, Э. Распределенные системы: принципы и парадигмы / Эндрю Таненбаум, Стен М. Ван; пер. с англ. А. Леонтьев. - СПб. : Питер, 2003. -877 с.

48. Тарков, М.С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем / М. Тарков // Автометрия. - 2003. - Том 39, № 3. - 84-96.

49. Таха, X. А. Введение в исследование операций, 7-е издание / X. А. Таха ; пер. с англ. под ред. А. А. Минько. - М. : Издательский дом "Вильяме", 2005.-912 с.

50. Томилин, А. Н. Применение метода математического моделирования к выбору структурной схемы машины БЭСМ-6 и разработки программы диспетчера машины БЭСМ-6: автореф. дис. ... канд. физ.-мат. наук. / Александр Николаевич Томилин.-М., 1969.-23 с.

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

52. Фортов, В. Е. Создание и применение высокопроизводительных вычислений на базе высокопроизводительных вычислительных технологий / В. Е. Фортов, Г. И. Савин, В. К. Левин // Информационные технологии и вычислительные системы. - 2001. — № 1. — 3-10.

53. Харари, Ф. Теория графов / Ф. Харари ; пер. с англ. под ред. Г. П. Гаврилова. - М. : КомКнига, 2006. - 296 с.

54. Хетагуров, Я. А. Основы проектирования управляющих вычислительных систем / Я. А. Хетагуров. - М. : Радио и связь, 1991. - 287 с.

55. Хокни, Р. Параллельные ВС. Архитектура, программирование и алгоритмы / Роджер Хокни, Карл Джессоуп; пер. с англ. Д. Н. Абашкина. - М. : Радио и связь, 1986. - 392 с.

56. Хокни, Р. Параллельные ЭВМ / Роджер Хокни, Карл Джессоуп; пер. с англ. Д. Н. Абашкина. - М. : Радио и связь, 1986. — 390 с.

57. Хорошевский, В. Г. Вычислительная система МИКРОС / В.Г.Хорошевский. - Новосибирск : Препринт ИМ СО АН СССР 38 (ОВС-19),1983.-52с.

58. Хорошевский, В. Г. Инженерный анализ функционирования вычислительных машин и систем / В. Г. Хорошевский. — М. : Радио и связь, 1987. — 256 с.

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

60. Хорошевский, В. Г. Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем / B. Г. Хорошевский, М. Г. Курносов // Автометрия. - 2008. - Т. 44, № 2. -C. 56-67.

61. Элементы параллельного программирования / В. А. Вальковский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков. - М.: Радио и связь, 1983. -240 с.

62. Эндрюс, Г. Основы многопоточного, параллельного и распределенного программирования / Г. Эндрюс; пер. с англ. А. Подосельника и др. — М. : Вильяме, 2003. - 512 с.

63. Языки и параллельные ЭВМ : сб. ст. /А. А. Самарский. - М.: Наука, 1990.-91 с.

64. Яненко, Н. Н. Параллельные вычисления в задачах математической физики на вычислительных системах с программируемой структурой / Н. Н. Яненко, В. Г. Хорошевский, А. Д. Рычков // Электронное моделирование. - 1984. - Т. 6, № 1. - 3-8.

65. Agarwal, Т. Topology-aware task mapping for reducing communication contention on large parallel machines / T. Agarwal et al.. // Parallel and Distributed Processing Symposium. - 2006. - P. 10

66. Ahmad, I. A Parallel Algorithm for Optimal Task Assignment in Distributed Systems / I. Ahmad, M. Kafil // Proceedings of the 1997 Advances in Parallel and Distributed Computing Conference. - 1997. - P. 284.

67. Bani-Mohammed, S. An efficient non-contiguous processor allocation strategy for 2D mesh connected multicomputers / S. Bani-Mohammed et al.. // Information Sciences: an International Journal. - 2007.- Vol.177, № 1 4 . -P. 2867-2883.

68. Barnard, S. T. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems / S. T. Barnard, H. D. Simon. - Concurrency - Practice and Experience. - 1994. - Vol. 5, № 2. - P. 107-117.

69. Bender, M. A. Communication-Aware Processor Allocation for Supercomputers / M. A. Bender et al.. // Algorithmica. - 2008. - Vol. 50, № 2. -P. 279-298.

70. Bokhari, S. H. On the mapping problem / S. H. Bokhari // IEEE Transactions on Computers. - 1981. - Vol. 30, №3. - P. 207-214.

71. Bouvry, P. Mapping and load balancing on distributed memory systems / P. Bouvry et al.. //Proceedings of Microprocessing. -Budapest, 1994.

72. Bui, T. N. Genetic algorithm and graph partition / T. N. Bui, B. R. Moon // IEEE Transactions on Computers. - 1996. - Vol. 45, № 7. - P. 841-855.

73. Chen, Hu. MPIPP: An Automatic Profileguided Parallel Process Placement Toolset for SMP Clusters and Multiclusters / Hu Chen // Proceedings of the 20th annual international conference on Supercomputing. -2006. - P . 353-360.

74. Chen, S. A fast recursive mapping algorithm / S. Chen, M. M. Eshaghian // Concurrency: Practice and Experience. - 1995. - Vol. 7, № 5. - P. 391-409.

75. Cho, S.-Y. Dynamic task assignment in heterogeneous linear array networks for metacomputing / S.-Y. Cho, К. H. Park // Heterogeneous Computing Workshop. - 1994. - P. 66-71.

76. Choo, H. Processor Scheduling and Allocation for 3D Torus Multicomputer Systems / H. Choo et al.. // IEEE Transactions on Parallel and Distributed Systems. - 2000. - Vol. 11, № 5. - P. 475-484.

77. Coli, M. Global execution time minimization by allocating tasks in parallel systems / M. Coli, P. Palazzari // Proceedings of the 3rd Euromicro Workshop on Parallel and Distributed Processing. - 1995. - P. 91.

78. De Rose, С A. F. Distributed algorithms for processor management in message-passing / С A. F. De Rose, H.-U. Heiss // In Proc. 12th Int. Symp. on Computer and Information Sciences. - 1997. - P. 221-229.

79. De Rose, С A. F. Distributed processor allocation in large PC clusters / C. A. F. De Rose et al.. // High-Performance Distributed Computing. - 2000. -P. 288-289.

80. Distributed and parallel systems: cluster and GRID computing / ed. by Z. Juhasz et al... - Boston : Springer. - 212 p.

81. Dongarra, J. Sourcebook of parallel computing / J. Dongarra et al... - San Francisco : Morgan Kaufmann Publ., 2003. - 842 p.

82. El-Rewini, H. Advanced computer architecture and parallel processing / H. El-Rewini, M. Abd-El-Barr. - New Jersey : John Wiley & Sons, 2005. -272 p.

83. Ercal, F. Task allocation onto a hypercube by recursive mincut bipartitioning / F. Ercal, J. Ramanujan, P. Sadayappan // Journal of Parallel and Distributed Computing. - 1990. -Vol. 10, № 1, - P . 35-44.

85. Flynn, M. Very high-speed computing system / M. Flynn // Proc. of IEEE, 1966. - № 5 4 . - P . 1901-1909.

86. Flynn, M. Some Computer Organisations and Their Effectiveness // IEEE Trans. Computers. - 1972. -Vol. 21, № 9. - P. 948-960.

87. Foster, I. Globus: A Metacomputing Infrastructure Toolkit / I. Foster, С Kesselman. - 1997. - Intl J. Supercomputer Applications. - Vol. 11, №3. — P. 115-128.

88. Foster, I. The Grid: Blueprint for a New Computing Infrastructure / I. Foster, C. Kesselman. - Morgan-Kaufmann, 1998.

89. Foster, I. The Anatomy of the Grid: Enabling Scalable Virtual Organizations / I. Foster // Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, 2001. - P. 1-4.

90. Foster, I. What is the Grid? A Three Point Checklist Электронный ресурс.. -Режим доступа : http://www-fp.mcs.anl.gov/foster/Articles/ WhatIsTheGrid.pdf, свободный.

91. Foster, I. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration / I. Foster et al.. // Global Grid Forum, 2002.

92. Garey, M. Some simplified NP-complete graph problems / M. Garey, D. Johnson, L. Stockmeyer. - Theoretical Computer Science. - 1976. - Vol. 1. -P. 237-267.

93. Grama, A. Introduction to parallel computing / A. Grama. - Harlow : Addison Wesley, 2003. - 856 p.

94. Heiss, H.-U. Mapping large parallel simulation programs to multicomputer systems / H.-U. Heiss, M. Dormanns // Proceedings of the 1994 simulation mul-ticonference on Grand challenges in computer simulation. — 1994. — P. 285-290.

95. Hendrickson, B. A multilevel algorithm for partitioning graphs / B. Hendrickson, R. Leland // Proc. of ACM/IEEE conference on Supercomput-ing. - San Diego : IEEE Press, 1995.

96. Hluchy, L. Static Mapping Methods for Processor Networks Электронный ресурс. / L. Hluchy, M. Dobrovodsky, M. Dobrucky // CiteSeer.IST, 2008. -Режим доступа: http://citeseer.ist.psu.edu/472693.html.

97. Hockney, R.. Parallel Computers 2: Architecture, Programming and Algorithms / R. Hockney, K. Jesshope. - Philadelphia : Hilger, 1988.

98. Hockney, R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 / R. Hockney. - Parallel Computing. - 1994. - Vol. 20, № 3. -P. 389-398.

99. Hsu, H.-S. Task Allocation on a Network of Processors / H.-S. Hsu et al.. // IEEE Transactions on Computers. - 2000. - Vol. 49, № 12. - P. 1339-1353.

100. Jacob, J. C. Task Spreading and Shrinking on Multiprocessor Systems and Networks of Workstations / J. C. Jacob, S.-Y. Lee // IEEE Transactions on Parallel and Distributed Systems. - 1999. - Vol. 10, № 10. - P. 1082-1101.

101. Jose, A. An approach to mapping parallel programs on hypercube multiprocessors / A. Jose // Proceedings of Workshop Parallel and Distributed Processing. - 1999. - P. 221-225.

102. Ingber, L. Simulated annealing: Practice versus theory / L. Ingber. - Mathl. Comput. Modelling. - 1993. - Vol. 18, № 11. - P. 29-57.

103. Kafil, M. Optimal Task Assignment Heterogeneous Distributed Computing Systems / M. Kafil, I. Ahmad // IEEE Concurrency. - 1998. - Vol. 6, № 3. -P. 42-51.

104. Kalinowski, T. Solving the mapping problem with a genetic algorithm on the MasPar-1 / T. Kalinowski // Proceedings of the First International Conference on Massively Parallel Computing Systems. - 1994. - P. 370-374.

105. Kartik, S. Task Allocation Algorithms for Maximizing Reliability of Distributed Computing Systems / S. Kartik, C. S. R. Murthy // IEEE Transactions on Computers. - 1997. - Vol. 46, № 6. - P. 719-724.

106. Karypis, G. Multilevel k-way partitioning scheme for irregular graphs / G. Karypis, V. Kumar // Journal of Parallel and Distributed computing. - 1998. -Vol. 4 8 . - P . 96-129.

107. Karypis, G. Analysis of multilevel graph partitioning / G. Karypis, V. Kumar // Proc. of ACM/IEEE conference on Supercomputing. - San Diego : IEEE Press, 1995.

108. Karypis, G. A fast and high quality multilevel scheme for partitioning iregu- lar graphs / G. Karypis, V. Kumar // Journal on Scientific computing. - 1998. -Vol. 20, № 1 . - P . 359-392.

109. Khan, M. S. Fast graph partitioning algorithms / M. S. Khan, K. F. Li // Proc. of Int. IEEE conference "Communications, Computers, and Signal Processing". - Victoria : IEEE Press, 1995. - P. 337-342.

110. Khoroshevsky, V. G. Algorithms for Assigning Parallel Program Branches to Computer System Processor Cores / V. G. Khoroshevsky, M. G. Kurnosov // Optoelectronics, Instrumentation and Data Processing. - 2008. - Vol. 44, № 2 . - P . 135-143.

111. Kirkpatrick, S. Optimization by Simulated Annealing / S. Kirpatrick, C D . Gelatt, M. P. Vecchi. - Science. - 1983. - Vol. 220, № 4598. -P. 671-680.

112. Koziris, N. An efficient algorithm for the physical mapping of clustered taskgraphs onto multiprocessor architectures / N. Koziris et al.. // Proceedings of Parallel and Distributed Processing. - 2000. - P. 406-413.

113. Lastovetsky, A. L. Parallel Computing on Heterogeneous Networks / A. L. Lastovetsky. - John Wiley & Sons, 2003. - 423 p.

114. Lee, On the mapping problem using simulated annealing / С Lee, L. Bic // Proceedings of Computers and Communications. - 1989. - P. 40-44.

115. Lee, C.-H. Optimal task assignment in homogeneous networks / C.-H. Lee, K. G. Shin // IEEE Transactions on Parallel and Distributed Systems. - 1997. -Vol. 8, № 2 . - P . 119-129.

116. Leiserson, C. E. Fat-Trees: Universal Networks for Hardware-Efficient Su- percomputing / С E. Leiserson// Proc. of. ICPP, 1985. - P. 393-402.

117. Leung, V. J. Processor Allocation on Cplant: Achieving General Processor 1.ocality Using One-Dimensional Allocation Strategies 7 V.J.Leung etal.. // Proceedings of the IEEE International Conference on Cluster Computing. -. 2002.-P.296.

118. Lo, V. Noncontiguous Processor Allocation Algorithms for Mesh-Connected Multicomputers / V. Lo et al.. // IEEE Transactions on Parallel and Distributed Systems.-1997.-Vol. 8, № 7 . - P . 712-726. : */ •

119. Mache, J. Minimizing Message-Passing Contention in Fragmentation-Free Processor Allocation / J. Mache et al.. // In Proceedings of the 10th International Conference on Parallel and Distributed Computing Systems. - 1997. -P. 120-124.

120. Malony, A. D. The open trace format (OTF) and open tracing for HPC 7 A. D. Malony, W. E. Nagel // Proceedings of the 2006 АСМЛЕЕЕ conference on Supercomputing, 2006. - P. 24.

121. Miquel, A. Clustering and reassignment-based mapping strategy for message-passing architectures / A. Miquel et al.. 7/ Journal of Systems Architecture. - 2003.-Vol. 48, № 8-10. - P. 267-283.

122. Moh, S. Mapping strategies for switch-based cluster systems of irregular topology / S. Moh etal.. // Proceedings of Parallel and Distributed Systems. -2001.-P. 733-740.

123. Optimizing task layout on the Blue Gene/L supercomputer / G. Bhanot et al.. // IBM Journal of Research and Development. - 2005. - Vol. 49, № 2. -P. 489-500.

124. Perego, R. A mapping heuristic for minimizing network contention / R. Pe- rego // Journal of Systems Architecture. - 1998. - Vol. 45, № 1. - P. 65-82.

125. Perego, R. Minimizing network contention for mapping tasks onto massively parallel computers / R. Perego, G. De Petris // Proceedings of the 3rd Euromi-cro Workshop on Parallel and Distributed Processing. - 1995. - P. 210.

126. Sadayappan, P. Cluster-partitioning approaches to mapping parallel programs onto a hypercube / P. Sadayappan, F. Ercal // Proceedings of the 1st International Conference on Supercomputing. - 1988. - P . 475-497.

127. Salcedo-Sanz, S. Hybrid meta-heuristics algorithms for task assignment in heterogeneous computing systems / S. Salcedo-Sanz, Y. Hu, X. Yao // Computers and Operations Research. - 2006. - Vol. 33, № 3. - P. 820-835.

128. Schloegel, K. Graph partitioning for high-performance scientific simulations / K. Schloegel, G. Karypis, V. Kumar // Sourcebook of parallel computing. — San Franciso : Morgan Kaufmann Publish, 2003. - P. 491-541.

129. Shen, C.-C. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion / C.-C. Shen, W.-H. Tsai // IEEE Transactions on Computers. - 1985. - Vol. 34, № 3. -P. 197-203.

130. Simon, H. D. How good is recursive bisection / H. D. Simon, S.-h. Teng // SIAM Journal on Scientific computing. - 1997. - Vol. 18. - P. 1436-1445.

131. Sloan, J. D. High Performance Linux Clusters with OSCAR, Rocks, Open- Mosix, and MPI / J. D. Sloan. - O'Reilly, 2004. - 360 p.

132. Srinivasan, S. Safety and Reliability Driven Task Allocation in Distributed Systems / S. Srinivasan, N. K. Jha // IEEE Transactions on Parallel and Distributed Systems. - 1999. - Vol. 10, № 3. - P. 238-251.

133. Subramani, V. Selective Buddy Allocation for Scheduling Parallel Jobs on Clusters / V. Subramani et al.. // In Proceedings of the International Conference on Cluster Computing. - 2002. - P. 107-116.

134. Sunderam, V. The PVM Concurrent Computing System: Evolution, Experiences, and Trends / V. Sunderam et al... - Parallel Computing. - 1994. -Vol. 20, № 4 . - P . 531-547.

135. Tarkov, M. S. Mapping parallel programs onto distributed computer systems with faulty elements / M. S. Tarkov et al.. // Lecture Notes in Computer Science: Computational Science. - 2001. - P . 148-157.

136. Tarkov, M. S. Mapping parallel programs onto distributed robust computer systems / M. S. Tarkov // Proc. Of 15th IMACS World Congress on Scientific Computation. - 1997. - P . 365-370.

137. Traff, J. L. Implementing the MPI Process Topology Mechanism / J. L. Traff // Proceedings of the ACM/IEEE conference on Supercomputing. - 2002. -P. 1-14.

138. Parhami, B. Introduction to Parallel Processing: Algorithms and Architectures / B. Parhami. - New York : Kluwer Academic Publ., 2002. - 532 p.

139. Prakash, D. Cluster-based multiple task allocation in distributed computing system / D. Prakash et al.. // Parallel and Distributed Processing Symposium. -2004.-P. 239.

140. Ucar, В. Task assignment in heterogeneous computing systems / B. Ucar etal.. // Journal of Parallel and Distributed Computing. - 2006.-Vol. 66, № 1 . - P . 32-46.

141. Yau, S. A task allocation algorithm for distributed computing systems / S. Yau, V. R. Satish // Proceedings of Computer Software and Applications Conference. - 1993. - P. 336-342.

142. Yu, H. Topology Mapping for Blue Gene/L Supercomputer / H. Yu, I-H. Chung, J. Moreira // Proceedings of АСМЯЕЕЕ Conference Supercomputing.-2006.-P. 52.

143. Zabrodin, A. V. The massively parallel computer system MBC-100 / A. V. Zabrodin, V. K. Levin, V. V. Korneev // Parallel Computing Technolo gies, 1995.-P. 341-355.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00