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

• Автор: Сластен, Любовь Михайловна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Таганрог
• Количество страниц: 214 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 Методы отображения алгоритмов на архитектуру многопроцессорных вычислительных систем.
1.1 Архитектура вычислительных систем й методы распараллеливания последовательных алгоритмов

1.2 Анализ коммутационных структур для многопроцессорных систем

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

1.4 Отображение параллельных алгоритмов с использованием ПЛИСтехнологии.

1.5 Принципы отображения параллельных алгоритмов на архитектуру системы.

1.5.1 Описание архитектуры МВС СПРВ

1.5.2 Описание структурнореализуемого фрагмента алгоритма

1.6 Выводы
2 Методы и алгоритмы реализации графов кадров на МВС со структурнопроцедурной реализацией вычислений
2.1 Методы и алгоритмы упорядочивания и выбора вершин для размещения при реализации информационного графа кадра на МВС с ортогональной коммутационной структурой.
2.2 Методы и алгоритмы одновременного размещения вершин и трассировки информационных каналов при реализации информационного графа кадра на МВС с ортогональной
коммутационной структурой.
2.2.1 Методы и алгоритмы размещения вершин.
2.2.2 Графовый метод трассировки информационных каналов
2.2.3 Схемный метод трассировки информационных каналов.
2.3 Методы и алгоритмы реализации графа задачи на МВС с произвольной коммутационной структурой
2.3.1 Метод группировки размещаемых вершин информационного графа кадра.
2.3.2 Методы выбора размещаемой вершины информационного графа
кадра.
2.3.3 Обобщенный алгоритм отображения информационного графа кадра
на архитектуру МВС
2.3.4 Алгоритм трассировки информационных каналов между секциями
МВС с произвольной коммутационной структурой
2.4 Выводы
3 Методы и алгоритмы распределения памяти при реализации многокадровых задач на МВС со структурнопроцедурной реализацией вычислений
3.1 Методы размещения информационных вершин
3.2 Методы и алгоритмы реализации много кадровой задачи на МВС с ортогональной системой коммутации и фиксированными секциями памяти
3.3 Методы и алгоритмы реализации многокадровой задачи на МВС с произвольной системой коммутации и произвольно заданными секциями памяти
3.3.1 Обобщенные методы группировки и выбора размещаемых вершин информационного графа кадра
3.3.2 Обобщенный метод и алгоритм отображения много кадровой задачи
на архитектуру МВС СПРВ
3.4 Выводы.
4 Программная реализация алгоритмов для МВС с программируемой архитектурой и структурнопроцедурной реализацией вычислений
4.1 Описание функции транслятора, реализующей алгоритмы отображения информационных графов на МВС с программируемой
архитектурой
4.2 Примеры задач, реализованных на МВС с различными типами коммутационных структур
4.2.1 Задача быстрого преобразования Фурье. 0 .
4.2.2 Задача решения уравнения Пуассона
4.2.3 Многокадровая задача.
4.3 Анализ эффективности средств отображения информационных графов на МВС с программируемой архитектурой для различных типов коммутационных систем
4.4 Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Сеть это множество виртуальных процессоров, а также механизм, с помощью которого программист абстрагируется от реальных процессов параллельной программы. По умолчанию трСсистема предполагает, что виртуальные процессоры сетей выполняют одинаковые объемы вычислений, и поэтому отображает их так, чтобы общее количество отображенных виртуальных процессоров было пропорционально их мощности. При этом все процессы, на которые отображены виртуальные процессоры, выполняют вычисления с одной скоростью, и параллельная программа является сбалансированной, по если в объемах вычислений наблюдаются значительные различия, подобное распределение может существенно замедлить программу. В конце х годов прошлого столетия в Институте программных систем РАН г. ПереславльЗалесский начались разработки Тсистемы 2, , технологии автоматического динамического распараллеливания программ, использующей парадигму функционального программирования для динамического распараллеливания программ. Явные параллельные конструкции в языке отсутствуют. Одним из базовых понятий Тсистемы является чистая функция, обозначающая функции без побочных эффектов. На основе графа, узлы которого представляют вызванные функции, а дуги соответствуют отношению подвыражение выражение, в каждый момент времени выделяются готовые к вычислению подвыражения и распределяются по имеющимся процессорам. Типичным недостатком являются очень большие накладные расходы при пересылке данных из одного узла кластера в другой, которые необходимо учесть при проектировании программы, иначе возникнут проблемы с ее эффективностью. Тсистема выполняет балансировку вычислений, но не гарантирует оптимальность. Тфункций может привести к чрезмерным накладным расходам, а слишком большая к малому количеству порождаемых в процессе параллельных фрагментов, вследствие чего вычислительные узлы будут загружены неравномерно. Разработанный в Институте прикладной математики им. М.В. Келдыша РАН язык НОРМА 2, это специализированный непроцедурный язык, предназначенный для спецификации задач вычислительного характера, в частности, задач математической физики. Основное назначение языка состоит в автоматизации процесса разработки программ, в предоставлении разработчику возможности работать почти в терминах математических формул, значительно упрощая его работу и усложняя задачи транслятора. Разработчик прикладных программ мыслит в привычных терминах своей предметной области, абстрагируясь от особенностей вычислительных систем. Запись программы на языке НОРМА не требует информации о порядке выполнения операций порядок предложений языка может быть произвольным. Запрос на вычисления формулируется без уточнений организации вычислений, а выявление информационных связей, выбор способа организации вычислений выполняет трансляторсинтезатор при анализе исходной программы и синтезе выходного текста. Математические соотношения близки разработчикам численных методов и прикладным программистам, не используют памяти, в них отсутствует пересчет значений переменных и сохраняется внутренний параллелизм алгоритма. Недостаток языка НОРМА в том, что он предназначен только для одной проблемной области для упрощения решения класса задач математической физики, специфика которых в том, что они ориентированы на сеточные методы. Обобщающий недостаток всех рассмотренных технологий и систем параллельного программирования в том, что они распараллеливают локальные участки циклы, ветви, процедуры последовательных алгоритмов, не уделяя внимания общей информационной структуре задачи и зачастую выполняя далеко не самые важные вычисления. В настоящее время широчайшее распространение получили кластерные системы, причина распространения которых носит не столько технический, сколько экономический характер. Кластеры создаются из унифицированных узлов и блоков, что позволяет неуклонно снижать такой важный параметр суперкомпьютеров как стоимостьпроизводительность. Остановимся на рассмотрении методов отображения параллельных алгоритмов на кластерные системы более подробно.