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

• Автор: Сальников, Алексей Николаевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 92 с. : ил.

Оглавление
1. Введение
1.1. Необходимость разработки высокоуровневых средств для создания параллельных программ

1.2. Цель работы

1.3. Проблема оптимизации последовательной части параллельной программы

1.4. Проблема тестирования производительности процессоров многопроцессорной системы

1.5. Тестирование производительности внутренней коммуникационной среды многопроцессорной системы

1.6. Виды зависимостей по данным

2. Обзор существующих подходов к созданию параллельных программ.

2.1. V система.

2.2. Тсистема.

2.3. шрС.
2.4. Отличительные черты подхода.
3. Обзор алгоритмов планирования вычислений для многопроцессорных систем
3.1. Постановка задачи планирования вычислений.
3.2. Списочные алгоритмы.
3.3. Алгоритм, основанный на множестве очередей
3.4. Алгоритм имитации отжига
3.5. Генетический алгоритм.
3.6. Алгоритм поиска критического пути.
3.7. Алгоритм обратного заполнения.
3.8. Алгоритм управления группами работ с прерываниями.
3.9. Особенности алгоритмов планирования вычислений в
4. Система
4.1. Краткое описание
4.2. Механизм преобразования графа зависимости в параллельную программу.
4.3. Организация передачи данных между вершинами графа.
4.4. Работа координирующего МРпроцссса.
4.5. Алгоритм выбора назначаемой вершины графа на МРпроцесс
4.5.1. Статический режим.
4.5.2. Динамический режим
4.5.3. Комбинированный режим.
4.6. Генетический алгоритм построения расписания назначений вершин графа по Iпроцессам.
4.7. Система тестирования многопроцессорной системы
4.8. Анализатор зависимостей по данным в Спрограмме.
4.8.1. Общее описание
4.8.2. Анализ зависимостей.
4.8.3. Построение графа
4.8.4. Определение весов операторов
4.9. Редактор графа и расписаний.
4 Визуализатор данных о производительности сети и процессоров
5. Примеры использования системы
5.1. Распределенная операция над массивом модельная задача.
5.2. Параллельная реализация перцептрона модельная задача
5.3. Частотный фильтр звуковых сигналов
5.4. Построение множественного выравнивая нуклеотидных и белковых последовательностей.
5.4.1. Общие сведения о выравниваниях
5.4.2. Парное выравнивание.
5.4.3. Множественное выравнивание
6. Тестирование системы .
6.1. Описание машин, на которых производилось тестирование.
6.2. Результаты тестирования коммуникационной среды
6.3. Особенности реализаций примеров использования на многопроцессорных системах
6.3.1. Особенности исполнения параллельной реализации перцептрона на машине
6.3.2. Исследование эффективности реализации распределнной операции над массивом для МВСМ
6.3.3. Параллельный способ выравнивания всех 5 в человеческом геноме.
6.3.4. интерфейс к построителю выравниваний
7. Результаты и выводы
7.1. Достоверность и практическая значимость результатов диссертационной работы
7.2. Основные результаты диссертационной работы
Список литературы


Разработать алгоритмы планирования вычислений для гетерогенных многопроцессорных систем, учитывающие нелинейность задержек от размера сообщения при передаче данных в многопроцессорной системе. Эти алгоритмы должны работать в статическом и динамическом режимах, а также в режиме с учётом подсказок пользователя. Для создания среды программирования нужно решить ряд перечисленных ниже подзадач. В любой параллельной программе всегда остаётся доля последовательных вычислений, распараллеливание которых может оказаться весьма трудоёмкой задачей. Получается, что важно знать, как быстро выполняется тот или иной фрагмент последовательной программы и как оптимизировать последовательный код таким образом, чтобы он наиболее быстро выполнился на определённой платформе. Существует множество средств, предназначенных для поиска «узких» мест в программе, например, средства профилирования программ (такие, как gprof[ ], Vtune[], Хргоб1ет[6]). Существуют также более специализированные средства, предназначенные для выявления конкретной проблемы в коде программы -например, Valgrind[7,8,9], Intel Thread Checker. С точки зрения планирования вычислений чрезвычайно важно знать производительность определённой платформы многопроцессорной вычислительной системы, на которой в дальнейшем предполагается производить вычисления. Под платформой будем понимать аппаратную составляющую и операционную систему без систем ввода-вывода и внешней памяти. Иными словами, это операционная система, кэш-память и процессор. Для планирования вычислений необходимо получить сведения о производительности процессоров и задержках при передаче данных по коммуникационной среде многопроцессорной системы. Физически коммуникационная среда многопроцессорной системы может быть гетерогенна. Система тестирования должна быть устроена таким образом, чтобы информация о несбалансированности пропускной способности коммуникаций попала на этап планирования в форме, унифицированной для произвольной многопроцессорной системы. Производительность процессоров обычно определяется на основе набора эталонных тестов, например теста LAPACK, на основе которого строится список 0 наиболее производительных вычислительных систем мира - Тор0. Одной из наиболее важных проблем при создании параллельных программ является проблема учета производительности обменов данными между процессорами. Процесс выяснения обстоятельств определённого поведения коммуникационной среды весьма сложен, и на текущий момент нет общего механизма, который позволил бы дать ответ на вопрос: какой промежуток времени будет задействован при передачи порции данных определённой длины от одного процессора к другому. При ответе на него главной трудностью является выяснение всех деталей поведения каждого элемента коммуникационной среды, что почти всегда очень трудно сделать. Поэтому существует потребность в создании средств, способных выдавать какие-либо оценки относительно поведения сети, не опираясь на детальную информацию о физической составляющей коммуникационной среды. Предложенная в данной работе система тестирования коммуникационной среды многопроцессорной системы позволяет отчасти разрешить данную проблему. Одной из проблем, которую приходится решать при создании параллельной программы, является проблема собственно распараллеливания вычислений. Как правило, на этапе распараллеливания приходится анализировать зависимости по данным между отдельными шагами и действиями алгоритма. Зависимость по данным - одно из наиболее важных понятий, которое в дальнейшем будет активно использоваться в работе. В плаве, посвящённой реализации системы «PARUS», присутствует описание разработанного в диссертации анализатора зависимостей в С-программе. По С-программе строится граф зависимостей по данным, который в дальнейшем может быть использован для поиска фрагментов кода, которые могут быть распараллелены. Для анализатора зависимостей, предлагаемого в данной работе, зависимость по данным определяется как зависимость между отдельными операторами языка программирования С. Понятие зависимости может быть расширено до зависимостей по данным между отдельными шагами алгоритма и в таком виде использоваться для описания параллельного алгоритма.