Экономичные коммутационные схемы и распараллеливание программ

• Автор: Адигеев, Михаил Георгиевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Ростов-на-Дону
• Количество страниц: 143 с. : ил.

Содержание
Введение
Глава 1. Проблемы коммутации и распараллеливания для
суперкомпьютеров
1.1. Основные классы суперкомпьютеров
1.2. Системы коммутации
1.3. Распараллеливание программ и размещение данных
Глава 2. Полнодоступные неразделенные коммутационные
схемы
2.1. Постановка задачи и определения
2.2. Семейство коммутационных графов, их свойства
2.3. Построение полнодоступных неразделенных схем
Глава 3. Коммутационные схемы для реализации семейства
решеток
3.1. Постановка задачи и определения
3.1.1. Модель МВС
3.1.2. Основные определения
3.2. Описание коммутационной схемы
3.2.1. Базовый блок коммутатора
3.2.2. Построение коммутационной схемы из блоков
3.3. Коммутационная схема для семейства решеток
3.3.1. Двум ерные решетки
3.3.2. Решетки произвольной размерности
3.4. Доказательства и вспомогательные результаты

Глава 4. МВС с фиксированными соединениями
4.1. Модель МВС
4.1.1. Описание архитектуры
4.1.2. Графовая модель
4.2. Выполнение программ на МВС
4.2 .1. Граф зависимостей
4.2.2. Условия реализации программ на МВС
Глава 5. Распараллеливающие преобразования программ для
суперпроцесеора со структурной реализацией вычислений
5.1. Общие сведения об МВС и компиляторе
5.1.1. Описание архитектуры суперпроцессора
5.1.2. Структура распараллеливающего компилятора
5.2. Преобразования, выполняемые компилятором
5.2.1. Распределение переменных по страницам памяти
5.2.2. Разбиение программы на кадры
Заключение
Библиография
Приложение. Термины теории графов

ВВЕДЕНИЕ
Цель и основные результаты диссертации.
Целью диссертации является комплексное изучение возможностей снижения затрат времени на межпроцессорные пересылки данных при параллельных вычислениях.
Двумя важными проблемами использования многопроцессорных вычислительных систем (МВС) с параллельной памятью являются: проблема обеспечения эффективной, и при этом экономичной коммутации, и проблема распараллеливания, т.е. адаптации программы к структуре МВС. Важной частью проблемы распараллеливания программ является проблема размещения данных в памяти для бесконфликтного и эффективного доступа к ним в процессе выполнения программы.
Этим проблемам посвящены многочисленные исследования и публикации. Связь между коммутацией и распараллеливанием обычно рассматривается в одном направлении — при разработке методов распараллеливания программ и размещения данных учитывается структура системы коммутации МВС [22]. Некоторыми исследователями (см., например, работы Валяха [17], A.B. Каляева [26], В .И. Кодачигова [30]) проводится также анализ систем коммутации с точки зрения их эффективности для параллельных вычислений. Однако большинством исследователей эти проблемы изучаются по отдельности, без учета их взаимной связи и влияния.
Таким образом, поставленная в данной диссертации задача исследования комплексного подхода к проблемам коммутации и распараллеливания программ является актуальной.

веришн множества Ь2, при которой все вершины множества М являются вершинами типа I, а все остальные вершины — вершинами типа II.
Доказательство. Применим описанный выше алгоритм и проанализируем полученную настройку а'.
1. Пусть к — индекс, выбранный в пункте 2 алгоритма. Тогда а'(2/1+1) ='х'. Так как М {хк} = 2т - — нечетное число, то при выполнении алгоритма текущее значение Т изменится нечетное число раз. Следовательно, при последнем выполнении пункта 4 (т.е. при г =к-) <тгк) = ег'(2(+1) ='=’. Таким образом, о'(рк)ф <т'(гк+,).
2. Пусть }{ф к) — такой индекс, что ду е М, текущее значение Т =Т0,
/ = / — 1. Выполняя пункт 4, получим o'{Zj) = ог'(д|+1)- 70, и затем г :=»! =/. Условие пункта б выполнено {Xj еМ), а / = у *-к — поэтому Т:=Т = Т0, и, возвращаясь к пункту 3, имеем: а'(л 1+1) = Т = Т0. Таким образом, опять а'(гк) ф о'(гк+1).
3. Пусть j:Xj ёМ, /:= к - 1(тоб N/2), текущее значение Т — Т0. Тогда сг'(г) = <т'(г/+1) = /:=( + ! (то44Г?2) = у. Так как х]ёМ, то
текущее значение Т='Т0 не изменяется, и <т'(г;+1) = Ту. Поэтому <т'(д;) = ст'( г/+1).
Следовательно, после выполнения алгоритма для каждой вершины х, е Ь1 справедливо следующее утверждение: если х, еМ, то а'(е1)ф<у'(гм), а если х,- ёМ, то Из рис.2.5 видно,
что это означает справедливость утверждения леммы. □
Следствие Пусть М<х1Л, |М| = 2 т. Тогда существует настройка сг: и Ь2 -у {=,х}, при которой все вершины множества М