Синтезатор структурных параллельных прикладных программ для многокристальных реконфигурируемых вычислителей

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

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

1. АНАЛИЗ СРЕДСТВ РАЗРАБО ТКИ ПРИКЛАДНЫХ

СХЕМОТЕХНИЧЕСКИХ РЕШЕНИЙ НА КРИСТАЛЛАХ ПЛИС.

1.1. Архитектура реконфигурируемых вычислительных систем

1.2. Системы проектирования решений задач на ПЛИС и РВС.

1.3. Постановка задачи отображения информационного графа на ресурс

.4. Анализ существующих методов и алгоритмов компоновки, размещения

и трассировки.

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

1.6. Выводы.

2. КОМПОНОВКА ИНФОРМАЦИОННЫХ ГРАФОВ ПРИКЛАДНЫХ ЗАДАЧ.
2.1. Представление входных данных для описания методов и алгоритмов компоновки
2.2. Общий алгоритм компоновки информационных графов прикладных задач.
2.3. Методы расчта ограничений на сумму внешних связей подграфов
2.4. Методы и алгоритмы огрубления информационных графов
2.5. Методы и алгоритмы компоновки информационных графов
2.6. Методы и алгоритмы восстановления огрублнного графа и оптимизации результатов компоновки
2.7. Выводы.
3. РАЗМЕЩЕНИЕ И ТРАССИРОВКА ИНФОРМАЦИОННЫХ ГРАФОВ
ПРИКЛАДНЫХ ЗАДАЧ
3.1. Обобщнный алгоритм размещения и трассировки.
I
3.2. Методы и алгоритмы размещения сформированных подграфов в кристаллах ПЛИС реконфигурируемых вычислителей
3.3. Методы и алгоритмы трассировки связей в базовом модуле
3.3.1. Трассировка связей.
3.4. Размещение и трассировка для РВС, состоящей из нескольких базовых модулей
3.5. Выводы
4. СИНТЕЗАТОР СТРУКТУРНЫХ ПАРАЛЛЕЛЬНЫХ ПРИКЛАДНЫХ ПРОГРАММ.
4.1. Обобщенный алгоритм работы синтезатора структурных параллельных прикладных программ
4.2. Синхронизация информационных и управляющих потоков в информационных графах параллельных прикладных программ.
4.3. Метод разметки изоморфных подграфов на основе текста параллельной прикладной программы
4.4. Примеры применения синтезатора
4.5. Анализ эффективности синтезатора
4.5.1. Сравнение решения задачи отображения для плоских и иерархичиых графов.
4.5.2. Сравнение алгоритмов, используемых на этапе компоновки
4.5.3. Сравнение алгоритмов, используемых на этапе размещения
4.5.4. Сравнение алгоритмов, используемых на этапе трассировки.
4.6. Выводы
ЗАКЛЮЧЕНИЕ.
СПИСОК ИС1ЮЛЬЗОВАННЫХ ИСТОЧНИКОВ.
ПРИЛОЖЕНИЕ 1. РАСЧТ ОГРАНИЧЕНИЯ НА СУММУ ВНЕШНИХ СВЯЗЕЙ НА ПРИМЕРЕ БАЗОВЫХ МОДУЛЕЙ С ОРТОГОНАЛЬНОЙ
ТОПОЛОГИЕЙ СВЯЗЕЙ
ПРИЛОЖЕНИЕ 2. ФАЙЛ ОПИСАНИЯ СТРУКТУРЫ
РЕКОНФИГУ РИРУЕМЫХ ВЫЧИСЛИТЕЛЕЙ
ПРИЛОЖЕНИЕ 3. СИНХРОНИЗАЦИЯ ИНФОРМАЦИОННЫХ И УПРАВЛЯЮЩИХ ПОТОКОВ В ИЕРАРХИ ЧНЫХ
ИНФОРМАЦИОННЫХ ГРАФАХ
ПРИЛОЖЕНИЕ 4. ОПИСАНИЕ ФУIПСЦИОНАЛЬНЫХ
ВОЗМОЖНОСТЕЙ СИНТЕЗАТОРА.
ПРИЛОЖЕНИЕ 5. ЗАДАЧА ФИЛЬТРАЦИИ ЖИДКОСТИ В ПОРИСТОЙ
ПРИЛОЖЕНИЕ 6. АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ.
ВВЕДЕНИЕ


РВС и осуществляющий автоматическое отображение информационных графов на аппаратный ресурс многокристальных реконфигурируемых вычислителей различных архитектур и конфигураций. Во второй главе описаны входные и выходные данные для этапа компоновки информационных графов структурных программ. Описаны методы расчта ограничений на общую сумму внешних связей для формируемых подграфов. Представлены разработанные автором модифицированные методы и алгоритмы для реализации каждого из этапов многоуровневой схемы компоновки информационных графов прикладных задач, решаемых на РВС. РВС. Представлен разработанный автором модифицированный алгоритм размещения подграфов параллельных прикладных программ, который за один проход позволяет формировать множество решений, включающий оптимальное решение и несколько решений, близких к оптимальному. В главе представлены существующие и предложены новые критерии ранжирования множества связей для последовательного алгоритма трассировки. Описан разработанный модифицированный волновой алгоритм Ли, обеспечивающий трассировки шин, которые могут содержать равнопотенциальные связи. В четвертой главе представлено описание разработанного алгоритма синхронизации информационных и управляющих потоков для конвейерных вычислительных блоков, характеризующихся одинаковыми темпами обработки данных. Описана новая иерархичная форма представления информационных графов параллельных программ. С помощью разработанного синтезатора проведены исследования методов и алгоритмов компоновки информационных графов и размещения сформированных подграфов параллельных прикладных программ. В главе представлены примеры применения синтезатора при решении прикладных задач и данные результатов исследований эффективности синтезатора. В заключении изложен основной научный результат диссертации, а также сформулированы теоретические и прикладные результаты, полученные в диссертационной работе. В приложениях описаны структура файла описания архитектуры РВС основные функциональные возможности синтезатора структурных параллельных прикладных программ математическая постановка задачи фильтрации жидкости в пористой среде из области математической физики представлены копии актов о внедрении результатов диссертационной работы от следующих организаций НИВЦ МГУ г. Москва, ФГУП НИИ Квант г. Москва, ФГУП Курский НИИ МО РФ г. Курск, Южного научного центра РАН г. РостовнаДону, НИИ МВС ЮФУ г. Таганрог. В настоящее время широкое распространение получили кластерные системы , что обусловлено низкой стоимостью их серийно выпускаемых составных компонентов процессоров общего назначения и графических процессоров. Программирование кластерных систем чаще всего осуществляется на традиционных языках высокого уровня с использованием дополнительных библиотек МР1 , ОрепМР , РУМ или с помощью специальных расширений традиционных языков программирования. Однако кластерные системы имеют серьзный недостаток их реальная производительность на различных прикладных задачах составляет от заявленной пиковой производительности 2, 3. Большие временные расходы на информационный обмен между узлами кластера приводят к тому, что рост производительности при увеличении числа узлов, задействованных для решения сильносвязной задачи, является нелинейным 4. Более того, с некоторого значения числа задействованных узлов кластера рост производительности при добавлении нового узла начинает замедляться. В определнный момент увеличение накладных расходов, связанных с межпроцессорным обменом данных, приведт к тому, что добавление каждого нового узла для решения силыюсвязной задачи будет приводить к снижению производительности . Дополнительно снижение производительности происходит изза простоя части АЛУ, присутствующих в кластерных системах в процессорах общего назначения, при решении тех или иных прикладных задач. Подобные несоответствия между имеющейся архитектурой кластерной системы и структурой решаемой задачи сказываются на снижении эффективности распараллеливания решения сильносвязных задач между узлами кластера.