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

• Автор: Курносов, Михаил Георгиевич
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Новосибирск
• Количество страниц: 177 с. : ил.

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

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

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

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

1.2. Кластерные, и мультикластерные ВС и вЛГОсистемы.

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

1.2.2. Мультикластерные ВС и вЯЮсистемы

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. Задача оптимального разбиения 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. Средства оптимизации вложения параллельных Iпрограмм.
4.2.3. Средства анализа параллельных Iпрограмм
4.3. Моделирование алгоритмов вложения параллельных программ в распределенные ВС
4.4. Моделирование алгоритмов формирования подсистем в распределенных ВС
4.5. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Сибирской школесеминаре по параллельным и высокопроизводительным вычислениям г. Публикации. По теме диссертации опубликована работа, включая 2 статьи в рецензируемых изданиях. Результаты исследований отражены в отчетах но грантам и НИР. Личный вклад. Все основные результаты диссертационной работы получены автором лично. Основные положении диссертации, выносимые на защиту. Метод и алгоритмы вложения параллельных программ в ВС с иерархической организацией коммуникационных сред. Эвристические алгоритмы формирования в пределах ВС подсистем, обеспечивающих эффективную реализацию основных схем межмашинных обменов, и вложения в них параллельных программ. Последовательный и параллельный стохастические алгоритмы вложения параллельных программ в пространственнораспределенные ВС. Алгоритмы формирования в пространственнораспределенных ВС однородных подсистем и вложения в них параллельных программ. Программный инструментарий оптимизации вложения параллельных Iпрограмм в ВС на базе многоядерных процессоров. Средства анализа производительности параллельных Iпрограмм. Функциональная структура пространственнораспределенной мультикластериой ВС, оснащенная средствами оптимизации вложения параллельных программ. Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка используемых литературных источников, изложенных на 0 страницах, а также приложений на 7 страницах. Содержание работы. В первой главе описывается архитектура распределенных ВС с программируемой структурой, приводятся основные понятия параллельного профаммирования, дается описание основных принципов построения и архитектурных особенностей современных кластерных, мультикластерных ВС и I систем. Рассмотрена задача вложения параллельных программ в распределенные ВС и основные режимы их функционирования, произведен анализ известных методов и алгоритмов вложения параллельных программ. Во второй главе предложена математическая модель коммуникационной среды ВС с иерархической организацией, сформулирована задача оптимального вложения параллельных программ в такие системы, описаны алгоритмы приближенного решения задачи. Приведены эвристические алгоритмы формирования в пределах ВС подсистем, допускающих эффективную реализацию основных схем межмашинных обменов, и вложения в них параллельных программ. В третьей главе рассмотрена задача оптимального вложения параллельных программ в пространственнораспределенные ВС, предложены последовательный и параллельный стохастические алгоритмы решения задачи. Описаны алгоритмы формирования однородных подсистем ЭМ и вложения в них параллельных программ. В четвертой главе описана архитектура пространственнораспределенной мультикластерной вычислительной системы, в разработке которой диссертант принимал непосредственное участие. Приведено описание реализованных на базе предложенных алгоритмов средств анализа производительности и оптимизации вложения параллельных МР1программ в ВС на базе многоядерных процессоров. Отражены результаты моделирования работы алгоритмов. В заключении сформулированы основные результаты диссертационной работы. В приложениях приведены сводные данные о предложенных алгоритмах и описание структурной организации сегментов мультикластернной ВС. ГЛАВА 1. Модель коллектива вычислителей. Модель вычислителя сформулирована в и наиболее полно по отношению к вычислительным машинам отражена в . Для этой модели характерны последовательное выполнение операций, фиксированная структура, неоднородность связей и функциональных элементов. Использование модели вычислителя для построения высокопроизводительных вычислительных средств ограничено теоретическими и техническими пределами скорости выполнения операций возможностями элементной базы и фундаментальными физическими законами . Модель коллектива вычислителей сформулирована в работах и получила дальнейшее развитие в работах , , . Под коллективом вычислителей понимается совокупность вычислительных машин, программноаппаратурным способом настраиваемая на решение общей задачи.