Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений

• Автор: Левин, Илья Израилевич
• Шифр специальности: 05.13.11, 05.13.15
• Научная степень: Докторская
• Год защиты: 2004
• Место защиты: Таганрог
• Количество страниц: 363 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

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

1.1. Методы организации параллельных вычислений

1.2. Модели параллельных вычислений

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

1.4. Основные принципы преобразования задачи в структурнопроцедурную форму.

1.5. Выводы

2. МЕТОДЫ ПРЕОБРАЗОВАНИЯ ЗАДАЧИ К ЭФФЕКТИВНОЙ СТРУКТУРНОПРОЦЕДУРНОЙ ФОРМЕ

2.1. Преобразование функциональнорегулярных графов

2.2. Преобразование в структурнопроцедурную форму информационных графов нерегулярной структуры.
2.3. Структурнопроцедурная реализация нерегулярных информационных графов
2.4. Эффективность структурнопроцедурных вычислений.
2.5. Выводы.
3. СРЕДСТВА ОПИСАНИЯ СТРУКТУРНОПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ.
3.1. Описание языка параллельного программирования высокого
уровня для структурнопроцедурной организации вычислений.
3.2. Некоторые особенности и алгоритмы трансляции
3.3. Выводы.
4. ТЕХНОЛОГИЯ ИНДУКТИВНЫХ СТРУКТУРНОПРОЦЕДУРНЫХ ПРОГРАММ.
4.1. Принципы построения технологии индуктивных структурнопроцедурных программ.
4.2. Планировщик индуктивных заданий
4.3. Система посттрансляции индуктивных заданий.
4.4. Программные средства поддержки технологии индуктивных программ.
4.5. Выводы.
5. ЭЛЕМЕНТНАЯ БАЗА МНОГОПРОЦЕССОРНЫХ СИСТЕМ С ПРОГРАММИРУЕМОЙ АРХИТЕКТУРОЙ И СТРУКТУРНОПРОЦЕДУРНОЙ ОРГАНИЗАЦИЕЙ ВЫЧИСЛЕНИЙ И СРЕДСТВА ЕЕ
.ПРОГРАММИРОВАНИЯ.
5.1. Макропроцессор.
5.1.1. Структура макропроцессора.
5.1.2. Программирование макроопераций.
5.2. Макрокоммутатор.
5.2.1. Структура макрокоммутатора
5.2.2. Описание коммутационных структур
5.3. Контроллер распределенной памяти
5.3.1. Структура КРП.
5.3.2. Программирование РП.
5.4. Выводы
6. АРХИТЕКТУРА МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ ДЛЯ
СТРУКТУРНОПРОЦЕДУРНОГО РЕШЕНИЯ ЗАДАЧ РАЗЛИЧНЫХ .ПРОБЛЕМНЫХ ОБЛАСТЕЙ.
6.1. Синтез структуры многопроцессорной вычислительной системы для
решения задач структурнопроцедурным методом распараллеливания
6.2. Анализ вариантов построения коммутационных структур МВС со структурнопроцедурной организацией вычислений
6.2.1. МВС с фиксированной топологией информационных связей
6.2.2. Иерархическая коммутационная система
6.2.3. Ортогональная система коммутации
6.2.4. МВС с коммутационной системой косвенного бинарного пкуба
. 6.2.5. Многоуровневая коммутационная структура.
6.3. Модульная организация МВС.
6.3.1. Структура базового модуля МВС с иерархической коммутационной системой.
6.3.2. Структурная схема базового модуля с ортогональной системой коммутации.
6.3.3. Конструкция базового модуля.
6.4. Выводы
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


В теории вычислительных систем под эффективностью понимается отношение ускорения решения задачи, достигаемого на МВС, по сравнению с одним процессором, к числу процессоров в системе [,]. Параметр “эффективность” характеризует качество реализации параллельной программы. Для мультипроцедурных методов организации параллельных вычислений широкое распространение получили ярусно-параллельные формы (ЯПФ) []. Представление графа алгоритма в ярусно-параллельной форме заключается в упорядочении вершин графа по подграфам 0У( разбиения (1. Упорядоченные подмножества называются ярусами. Множество нулевого яруса У0 определяет совокупность входных вершин X. Очевидно, что не существует ни одной дуги (а,Ь где Ь е X. Вершина с принадлежит ярусу У/ тогда и только тогда, когда существует, по крайней мере, одна дуга <(1, с>, где с - вершина, принадлежащая У0. Таким образом, первый ярус ЯПФ включает в себя те и только те вершины, которые являются приемниками входных вершин графа. Множество вершин второго яруса содержит те вершины, которые связаны, по крайней мере, одной дугой с вершинами первого яруса. В общем случае, вершина (I принадлежит /-му ярусу тогда и только тогда, если существует, по крайней мере, хотя бы одна дуга А=(с1, с), где с - вершина, принадлежащая ярусу с номером /-/. К, = (сА№с)) л Уит (1. На рис. Рис. Ярусно-параллельный граф задачи. Для традиционных методов организации параллельных вычислений распараллеливание выполняется только в пределах яруса. При этом множество операционных вершин соответствуют множеству независимых процедур обработки данных в процессорах системы, а информационные зависимости между ярусами, в общем случае, могут существовать в виде сложных информационных зависимостей, реализация которых требует выполнения специальных процедур межпроцессорных обменов. ЯПФ задачи соответствует реализации информационного графа в соответствии с утверждениями (1. Вышеперечисленные формы запрещают существование обратных связей и требуют итерировать участки вычислений столько раз, сколько они выполняются при реализации данного алгоритма [, , ,]. Обобщенная форма информационного графа, реализующего только утверждение (1. Однако данная параллельная форма не позволяет определить подходы к преобразованию задачи в параллельнопоследовательную форму, которая может быть реализована в реальных вычислительных системах. Каляевым Л. В. была предложена параллельно-конвейерная форма представления задачи [, ]. Параллельно-конвейерная форма представления задачи итерирования циклически повторяющихся участков вычислений разрешает обратные связи. При реализации параллельно-конвейерной формы реализуется только утверждение (1. Задача, представленная в параллельно-конвейерной форме, описывается некоторым графом G, в котором наряду с прямыми связями между операционными вершинами существуют обратные связи, которые определяют рекурсивную зависимость по данным. При этом предполагается, что параллельно-конвейерный граф может быть прямо реализован в вычислительной системе. Примером реализации параллельно-конвейерной формы является задача реализации многослойной нейронной сети. Если все вычисления, описываемые графом нейронной сети, могут быть аппаратно реализованы в многопроцессорной системе, то для организации итерационного процесса обучения нейронной сети информация с выходов одних процессорных элементов через элементы задержки поступает на входы других процессорных элементов, при этом множество дуг обратных связей прямо отображается на множество соединений между процессорными элементами. На рис. Циклически итерируемые участки вычислений заменены подграфом с рекурсивными информационными связями. На данном рисунке дуги, изображенные пунктирными линиями, соответствуют инициализации рекурсии. Достоинством параллельно-конвейерной формы представления задач является ее большая компактность по сравнению с ярусно-параллельной формой. Однако если необходимо перейти к другому варианту распараллеливания задачи, требуется разрывать рекурсивные связи, что представляет сложную проблему при реализации эффективных параллельных программ.