Синтезатор структурных параллельных прикладных программ для многокристальных реконфигурируемых вычислителей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Гуленок, Андрей Александрович

• Гуленок, Андрей Александрович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Гуленок, Андрей Александрович

ВВЕДЕНИЕ.

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

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

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

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

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

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

1.6. Выводы.

2. КОМПОНОВКА ИНФОРМАЦИОННЫХ ГРАФОВ ПРИКЛАДНЫХ ЗАДАЧ.

2.1. Представление входных данных для описания методов и алгоритмов компоновки.

2.2. Общий алгоритм компоновки информационных графов прикладных задач.

2.3. Методы расчёта ограничений на сумму внешних связей подграфов.

2.4. Методы и алгоритмы огрубления информационных графов.

2.5. Методы и алгоритмы компоновки информационных графов.

2.6. Методы и алгоритмы восстановления огрублённого графа и оптимизации результатов компоновки.

2.7. Выводы.

3. РАЗМЕЩЕНИЕ И ТРАССИРОВКА ИНФОРМАЦИОННЫХ ГРАФОВ

ПРИКЛАДНЫХ ЗАДАЧ.

3.1. Обобщённый алгоритм размещения и трассировки.

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], созданные из унифицированных узлов на базе универсальных процессоров, однако такие системы эффективны только для решения слабосвязных задач, где количество информационных обменов между различными процессорами относительно невелико. При решении сильносвязных расчётоёмких задач (когда число информационных обменов соизмеримо с числом вычислительных операций) на многопроцессорных системах существенное влияние на реальную производительность оказывает организация информационных связей между процессорами. Реальная производительность кластерных систем при решении таких задач меньше декларируемой пиковой в десятки и даже сотни раз [2, 3]. Более того, при увеличении числа процессоров кластерных МВС, используемых для решения сильносвязной задачи, рост реальной производительности начинает замедляться [4], так как накладное время на организацию параллельных вычислений превышает время самих вычислений. Таким образом, увеличение задействованных в вычислениях процессоров для решения сильносвязной расчётоёмкой задачи будет приводить к снижению реальной производительности системы.

Для решения расчётоёмких задач создаются и развиваются новые архитектуры вычислительных систем. В последнее время широкое распространение получили альтернативные гибридные архитектуры высокопроизводительных вычислительных систем, в состав которых, наряду с процессорами общего назначения, входят графические векторные процессоры [5] или программируемые логические интегральные схемы (ПЛИС) [6]. Кристаллы ПЛИС (в зарубежной литературе FPGA - Field-Programmable Gate Array) содержат множество логических ячеек, блоки коммутации и другие элементы, которые могут быть сконфигурированы для совместного решения прикладной задачи или какой-то её части.

Однако гибридные системы хоть и показывают более высокую реальную производительность по сравнению с системами, построенными только лишь на универсальных процессорах, они обладают такими же недостатками, связанными с большими накладными расходами при информационном обмене между процессорами. Несоответствие архитектур подобных вычислительных систем структуре решаемой задачи значительно снижает качество масштабирования решений расчётоёмких задач.

Принципиально новыми свойствами обладают реконфигурируемые вычислительные системы (РВС) [7]: архитектура самого вычислителя подстраивается под структуру решаемой задачи. В настоящее время основным аппаратным компонентом реконфигурируемых вычислительных систем является совокупность ПЛИС. Подобные системы могут быть сконфигурированы под решение конкретной прикладной задачи и могут обеспечить высокую реальную производительность для различных расчётоёмких задач. Кроме того, РВС потенциально обладают близким к линейному ростом производительности при увеличении вычислительного ресурса [8].

На данный момент производительность устройств ПЛИС растёт гораздо быстрее производительности традиционных микропроцессоров [9]. Развитие высокопроизводительных кристаллов с FPGA-архитектурой показывает постоянное снижение в отношении «стоимость/производительность» в каждом новом поколении кристаллов данного семейства.

Из зарубежных производителей, ведущих разработку вычислителей на ПЛИС, можно выделить компании Starbridge Systems, Nallatech и DiniGroup. Наиболее успешными отечественными разработками в данной области являются реконфигурируемые вычислители производства НПО «Роста» (г. Москва), НИИ МВС ТРТУ (ЮФУ) (г. Таганрог) и ФГУП «НИИ «Квант» (г. Москва).

С программированием реконфигурируемых систем связана парадигма структурной организации вычислений, согласно которой программа прикладной задачи формируется в виде информационного графа, вершины которого соответствуют операциям, а дуги — информационным зависимостям между ними [11] (в зарубежной литературе известна аналогичная парадигма -dataflow programming paradigm [10]). Программы, созданные на основе парадигмы структурной организации вычислений, будем называть структурными программами.

В отличие от процедурного программирования, когда текст исходной программы транслируется компилятором в набор инструкций, последовательно во времени исполняемых на процессоре (или совокупности процессоров), текст структурной программы для РВС преобразуется с помощью программы-синтезатора в совокупность логических блоков, команд функциональных устройств, расположенных в кристаллах ПЛИС, и связей между ними.

Для решения расчётоёмких задач из различных предметных областей при разработке структурных параллельных прикладных программ часто недостаточно одной ПЛИС, так как информационный граф задачи превышает ресурс кристалла. Поэтому для реализации структурных параллельных прикладных программ требуется множество взаимосвязанных ПЛИС. В этом случае информационный граф структурной параллельной прикладной программы должен быть разделён на непересекающиеся подграфы, каждый из которых структурно реализуется в отдельном кристалле ПЛИС реконфигурируемого вычислителя. Подобные структурные параллельные прикладные программы будем называть многокристальными.

В настоящее время для программирования РВС используются языки HDL-группы (Hardware Description Language — язык описания аппаратуры) [12] и различные графические системы, которые предназначены для программирования отдельных ПЛИС, а не их совокупности. Программирование РВС на языках HDL представляет собой разработку отдельных проектов для каждой ПЛИС. При разработке многокристальных решений пользователю РВС приходится распределять элементы информационного графа алгоритма расчётоёмкой задачи между различными проектами, каждый из которых структурно реализует фрагмент параллельной прикладной программы в отдельной ПЛИС реконфигурируемого вычислителя. При этом программист должен следить за корректностью структуры связей между элементами информационного графа из разных проектов и обеспечивать синхронизацию потоков данных и управляющих сигналов как внутри каждого проекта, так и в общем графе алгоритма решаемой задачи.

Ещё одной актуальной проблемой при программировании многокристальных реконфигурируемых вычислителей является переносимость разрабатываемой программы с одной РВС на другую. Частично эту проблему решает переход к единому стандарту описания структурной программы в существующих системах разработки, а именно - к языкам HDL-группы. Тем не менее, разработчик проектирует не только вычислительную часть задачи, но и интерфейсы подключения различных внешних устройств (управляющей host-машины, модулей памяти, других реконфигурируемых вычислителей), а также осуществляет синхронизацию управляющих и информационных потоков внутри информационного графа. Таким образом, при переходе от одного реконфигурируемого вычислителя к другому текст структурной программы может потребовать существенных изменений.

При использовании известных средств программирования ПЛИС срок разработки структурной параллельной прикладной программы для многокристальной РВС может составлять несколько месяцев, что может оказаться неприемлемым. В то же время существует большой класс задач, при решении которых реконфигурируемые вычислители показывают производительность на два-четыре десятичных порядка выше, чем у традиционных МВС - это так называемые потоковые задачи [46], для которых характерна обработка больших массивов данных по фиксированному алгоритму.

В настоящий момент применение РВС для решения расчётоёмких задач сдерживается отсутствием качественного системного программного обеспечения. Существуют различные языки высокого уровня программирования приложений для ПЛИС (Handel-C [13], Mitrion-C [14] и другие), которые позволяют в короткие сроки создавать структурные программы для однокристальных РВС. В то же время на данный момент не существует эффективных синтезаторов, которые обеспечат автоматическое решение задачи отображения информационных графов параллельных прикладных программ на многокристальные РВС.

Среди существующих многокристальных синтезаторов, доведённых до практической реализации, наиболее известным является синтезатор компании Starbridge Systems, входящий в среду разработки Viva. Несмотря на ряд достоинств среды Viva (которая подробно рассмотрена в первой главе), реальная производительность реконфигурируемого вычислителя для структурных программ, сформированных с помощью синтезатора Starbridge Systems, не превышала 30% от пиковой [16, 17]. Кроме того, данный синтезатор применяется только для программирования РВС производства Starbridge Systems, что не позволяет его использовать для реконфигурируемых вычислителей других архитектур и конфигураций. и

В этой связи актуальной является разработка методов и средств автоматического отображения ресурсонезависимых информационных графов структурных параллельных прикладных программ на аппаратный ресурс многокристальных РВС, которые позволят значительно сократить время разработки структурных программ и обеспечат высокую реальную производительность многокристальных РВС при решении расчётоёмких задач из различных предметных областей. Данные методы и средства должны обеспечить автоматическое разбиение информационных графов на подграфы, каждый из которых отображается в кристалл ПЛИС определённой РВС, осуществить пространственную коммутацию информационных связей между всеми задействованными в вычислениях кристаллами и обеспечить синхронизацию управляющих и информационных потоков как в отдельных кристаллах, так и в общем графе прикладной задачи. Также данные средства должны осуществлять автоматизированный перенос готовых прикладных программ на РВС различных архитектур и разной производительности.

Объектом исследований являются методы автоматического отображения информационных графов параллельных прикладных программ на аппаратный ресурс многокристальных реконфигурируемых вычислительных систем.

Целью диссертационной работы является сокращение времени разработки ресурсонезависимых параллельных прикладных программ для многокристальных РВС.

Методы исследований. При проведении исследований были использованы основы теории графов, теории множеств, методы потокового программирования, методы структурного программирования.

Экспериментальные исследования проведены на действующих образцах многокристальных реконфигурируемых вычислительных систем.

Научная задача, решаемая в диссертации, - создание методов и алгоритмов автоматического отображения информационных графов на ресурс многокристальных РВС, обеспечивающих сокращение времени создания ресурсонезависимых параллельных прикладных программ для многокристальных РВС при высокой реальной производительности формируемых решений.

Для достижения указанной цели решены следующие задачи:

1) проведён анализ существующих методов и средств разработки решений трудоёмких прикладных задач для многокристальных РВС;

2) разработан общий алгоритм работы синтезатора структурных параллельных прикладных программ для многокристальных реконфигурируемых вычислительных систем, независимый от архитектуры РВС;

3) разработаны и исследованы методы компоновки информационных графов параллельных прикладных программ, решаемых на многокристальных РВС;

4) разработаны и исследованы методы размещения и трассировки информационных графов параллельных прикладных программ;

5) на основании разработанных и исследованных методов компоновки, размещения и трассировки разработан синтезатор для автоматического отображения информационных графов параллельных прикладных программ на аппаратный ресурс многокристальных РВС.

Научная новизна диссертации состоит в том, что в ней разработаны:

1) новый алгоритм работы синтезатора структурных параллельных прикладных программ для многокристальных РВС, отличающийся от известных включением этапа загрузки описания структуры РВС и обеспечивающий автоматическое отображение информационных графов на аппаратный ресурс многокристальных РВС различных архитектур и конфигураций с высокой реальной производительностью формируемых решений;

2) модернизированная многоуровневая схема компоновки (multilevel partitioning scheme) информационных графов структурных параллельных прикладных программ, отличающаяся от известной введением этапа расчёта ограничений для формируемых подграфов, а также введением новых алгоритмов для этапов огрубления и восстановления;

3) новые методы компоновки информационных графов структурных параллельных прикладных программ, отличающиеся от известных введением модернизированной многоуровневой схемы компоновки, а также процедуры последовательной компоновки, основанной на модернизированном алгоритме «жадного» роста регионов (greedy graph growing) и разработанном алгоритме обхода локально-оптимальных решений (локальных тупиков);

4) модифицированный волновой алгоритм Ли для трассировки информационных связей подграфов структурных параллельных прикладных программ, который отличается от известного приращением значений волнового фронта не на единицу, а на минимальное число занимаемых физических каналов связей для трассируемой шины, что позволяет улучшить качество трассировки.

Практическая значимость. В диссертации решена актуальная научная задача разработки методов и средств автоматического отображения информационных графов структурных параллельных прикладных программ на ресурс многокристальных РВС. Разработанные методы и средства позволяют в 5-10 раз сократить время создания структурных параллельных прикладных программ для многокристальных РВС по сравнению с временем разработки в существующих графических средах, а также в 10-20 раз сократить время портации многокристальных проектов на РВС различных архитектур и конфигураций.

Использование результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР. К наиболее значимым НИОКР относятся:

- ОКР «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», выполняемой в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы» по государственному контракту № 02.524.12.4002 от 20.04.2007 г. на выполнение опытно-конструкторских работ, шифр «Большая медведица», №ГР 01.2.007 05707;

- ОКР «Разработка эскизной конструкторской документации на макет базового модуля модульно-наращиваемой мультипроцессорной системы (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса» в рамках мероприятия 1.12-GA3 по программе Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем» (шифр «Триада», 2006 г.), №ГР 01.2.00611470;

- ОКР «Разработка технологии создания высокопроизводительных модульно-наращиваемых многопроцессорных вычислительных систем с программируемой архитектурой на основе реконфигурируемой. элементной базы», шифр «Медведь», выполняемая в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 гг.» по госконтракту №02.447.11.1007 от «6» июля 2005 года, №ГР0122.0510630;

- ОКР «Разработка технологии ресурсонезависимого параллельного программирования для многопроцессорных вычислительных систем различных классов» по государственному контракту от 22 июля 2005 г. № 02.447.11.1005 (шифр ИТ-22.4/005), №ГР0120.0511686;

- НИР «Исследование возможности создания модульно-наращиваемой многопроцессорной вычислительной системы на основе унифицированных базовых модулей для мониторинга систем цифровой связи», выполняемая в рамках договора с ФГУПРНИИРС, № ГР 01.2.00613841.

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:

- на II, III, IV, V, VI Ежегодных научных конференциях студентов и аспирантов базовых кафедр Южного научного центра (ЮНЦ) Российской академии наук (РАН) (2006, 2007, 2008, 2009, 2010 гг., г. Ростов-на-Дону); на Седьмой Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы-2006» (с. Кацивели, Украина,, 2006); на Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы — 2007, 2009» (с. Дивноморское, Россия, 2007, 2009); на Всероссийской научной конференции «Научный сервис в сети ИНТЕРНЕТ: многоядерный компьютерный мир. 15 лет РФФИ» (2007 г. Москва); на Пятой Международной научной молодежной школе «Высокопроизводительные вычислительные системы» (с. Кацивели, Украина, 2008); на Международной научной молодежной школе «Системы и средства искусственного интеллекта (ССИИ-2008) (с. Кацивели, Украина, 2008); на Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)» (с. Дивноморское, Россия, 2010); на Седьмой Международной научной молодежной школе «Высокопроизводительные вычислительные системы» (с. Дивноморское, Россия, 2010).

Положения, выдвигаемые на защиту:

- использование процедуры оптимизации на этапе огрубления информационного графа структурной параллельной прикладной программы для многоуровневой схемы компоновки позволяет сократить суммарное число внешних связей в формируемых подграфах и, тем самым, обеспечить лучшие условия для этапа трассировки;

- использование модифицированной процедуры формирования карты волновых фронтов в алгоритме трассировки информационных связей подграфов структурных параллельных прикладных программ, которая отличается от известной тем, что значение волны равно минимальному числу занимаемых каналов связи от источника сигнала, позволяет проводить трассы с использованием ранее проложенных равнопотенциальных связей и шин и, тем самым, снижает суммарное число занятых каналов связи.

Результаты, выносимые на защиту:

- новый алгоритм работы синтезатора ресурсонезависимых структурных параллельных прикладных программ для многокристальных РВС;

- метод компоновки информационных графов структурных параллельных прикладных программ, содержащий модифицированную многоуровневую схему и модифицированный последовательный алгоритм компоновки с обходом локальных тупиков;.

- метод трассировки внешних связей размещённых подграфов структурных параллельных прикладных программ, содержащий модифицированную процедуру формирования карты волновых фронтов для волнового алгоритма трассировки Ли;

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

Диссертация соответствует пункту 8 («Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования») паспорта специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей».

Структура диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка использованных источников и шести приложений.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Гуленок, Андрей Александрович

4.6. Выводы

1)На основе методов и алгоритмов, описанных в главах 2 и 3, был разработан синтезатор для автоматического решения задачи отображения информационных графов параллельных прикладных программ на аппаратный ресурс РВС. Входными данными для синтезатора являются информационные графы параллельных прикладных программ, которые вводятся в виде граф-схем или автоматически генерируются транслятором языка высокого уровня COLAMO. Результатом работы синтезатора являются файлы VHDL-описаний и файлы временных и топологических ограничений User Constraints File (UCF), на основе которых генерируются конфигурационные файлы ПЛИС для РВС.

2) На основе метода разметки изоморфных структур, реализованного в трансляторе COLAMO, предложен метод формирования иерархичных информационных графов структурных параллельных прикладных программ, содержащих изоморфные подграфы. Иерархичная форма представления информационного графа позволяет в ряде случаев* в десятки раз сократить время решения задачи отображения информационных графов структурных параллельных прикладных программ на аппаратный ресурс РВС.

3) Для графов задач, состоящих из конвейерных блоков с одинаковым темпом обработки данных, был разработан алгоритм синхронизации информационных и управляющих потоков, который обеспечивает автоматическое выравнивание всех входных потоков на каждом конвейерном блоке. Также была разработана модификация алгоритма синхронизации для графов с изоморфными включениями.

4) Работа синтезатора была проверена на десятках графах реальных задач из областей математической физики, линейной алгебры, цифровой обработки сигналов и на более чем двухстах тестовых примерах.

5) Разработанные методы и алгоритмы компоновки позволили на 20%-30% сократить число внешних связей в формируемых подграфах по сравнению с числом внешних связей в результатах, полученных классическими методами и алгоритмами компоновки информационных графов структурных программ. Снижение суммы внешних связей в подграфах структурных программ не приводило к увеличению среднего процента занимаемого ресурса в кристаллах ПЛИС многокристальной РВС.

6) Разработанный алгоритм поиска множества вариантов размещения снизил на 15% число занимаемых линий связи по сравнению с алгоритмом поиска одного оптимального решения. Разработанный модифицированный алгоритм волновой трассировки снизил на 1,5% число занимаемых линий связи по сравнению с трассировкой известным волновым алгоритмом. Линии связи в РВС являются самым востребованным ресурсом. Сокращение линий связи, используемых на этапе трассировки, может оказать существенное влияние на нахождение результата трассировки всех внешних информационных связей подграфов.

7) Разработанные методы и алгоритмы для автоматического отображения информационных графов структурных параллельных прикладных программ позволили приблизительно в 1,7-2,5 раза повысить качество разрабатываемых структурных программ по сравнению с качеством программ, разработанных с помощью существующих многокристальных синтезаторов. Разработанные методы и алгоритмы позволяют в 5-10 раз сократить время проектирования решений трудоёмких задач на РВС по сравнению с временем разработки в существующих графических средах и позволяют существенно сократить время портации структурной параллельной прикладной программы на многокристальные РВС различных архитектур и конфигураций.

155

ЗАКЛЮЧЕНИЕ

Основной научный результат диссертации заключается в разработке методов и средств автоматического отображения информационных графов параллельных прикладных программ на аппаратный ресурс многокристальных реконфигурируемых вычислительных систем, обеспечивающих сокращение времени разработки ресурсонезависимых параллельных прикладных программ для многокристальных РВС при высокой реальной производительности формируемых решений.

При проведении исследований и разработок в диссертации получены следующие теоретические и прикладные результаты:

- разработан новый алгоритм работы синтезатора ресрсонезависимых структурных программ для многокристальных РВС, отличающийся от известных включением этапа загрузки описания архитектуры РВС;

- разработан обобщённый алгоритм компоновки информационных графов прикладных задач, который представляет собой модифицированную многоуровневую схему компоновки;

- разработан модифицированный алгоритм огрубления графов для многоуровневой схемы компоновки информационных графов структурных программ, который отличается от известных включением процедуры оптимизации стянутых вершин;

- разработан модифицированный алгоритм восстановления огрублённых информационных графов структурных программ, который отличается от известных включением процедуры дублирования вершин;

- разработан алгоритм поиска множества рациональных вариантов размещения подграфов в ПЛИС многокристальных РВС;

- доказано, что использование модернизированной процедуры формирования карты волновых фронтов в алгоритме трассировки информационных связей подграфов структурных параллельных прикладных программ, которая отличается от известной тем, что значение волны равно минимальному числу занимаемых каналов связи от источника сигнала, позволяет проводить трассы с использованием ранее проложенных равнопотенциальных связей и шин и, тем самым, снижает суммарное число занятых каналов связи;

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

Основные научные результаты диссертации опубликованы в работах [90, 92, 93, 96, 98].

Предложенные в диссертации новые результаты строго аргументированы и оценены по сравнению с известными работами в рассматриваемой области. Полученные научные результаты используются на различных предприятиях и в организациях России, что подтверждается соответствующими актами о внедрении.

Все научные результаты, полученные при решении научной задачи создания методов и алгоритмов автоматического отображения информационных графов структурных параллельных прикладных программ на ресурс многокристальных РВС, обеспечивающих сокращение времени создания ресурсонезависимых параллельных прикладных программ для многокристальных РВС при высокой реальной производительности формируемых решений, получены автором лично.

Таким образом, в диссертации решена новая научная задача, которая является актуальной и имеет существенное научно-практическое значение. Внедрение полученных в диссертации результатов вносит значительный вклад в развитие высокопроизводительных вычислительных систем.

Список литературы диссертационного исследования кандидат технических наук Гуленок, Андрей Александрович, 2011 год

1. Гергель, В.П. Технологии построения и использования кластерных систем / Интернет университет информационных технологий intuit.ru -электронный ресурс. http://www.intuit.ru/department/supercomputing/tbucs/

2. Слуцкин А.И. Направления развития отечественных высокопроизводительных систем. Текст. / А.И. Слуцкин, Л.К. Эйсымонт // «Открытые системы». М., 2004. - № 5.

3. Воеводин, В л.В. «Вычислительное дело и кластерные системы» Текст.: монография / Вл.В. Воеводин, С.А. Жуматий. М.: Изд-во МГУ, 2007. -150 с.

4. Корнеев, В.В. Параллельные вычислительные системы Текст.: монография / В.В. Корнеев; под ред. В.В. Корнеева. М.: «Нолидж», 1999. — 320 с.

5. Гибридные вычислительные системы на основе графических процессоров NVIDIA Tesla / «Открытые технологии» электронный ресурс. -http://www.ot.ru/press20110215 .html

6. ПЛИС Xilinx. Итоги 2006 года и тенденции развития Текст. Компоненты и технологии №12 2006

7. Каляев, A.B. Многопроцессорные системы с перестраиваемой архитектурой: концепции развития и применения Текст. / A.B. Каляев, И.И. Левин // Наука производству, 1999. - № 11.-С.11-19.

8. Каляев A.B. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений Текст.: монография / A.B. Каляев, И.И. Левин; под ред. A.B. Каляева. М.: Янус-К, 2003. - 380 с.

9. Состояние рынка и расширение сферы применения ПЛИС Текст. Компоненты и технологии №5 2004

10. Advances in dataflow programming languages. Wesley M. Johnston, J. R. Paul Hanna, Richard J. Millar. ACM Computing Surveys (CSUR) Volume 36 Issue 1, March 2004

11. П.Котляров Д.В., Кутепов В.П., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах Текст. М: Из-во РАН, Теория и системы управления, 2005, №1.

12. Botros, Nazeih "HDL Основы программирования VHDL И Verilog" Текст.: монография / Nazeih Botros. Изд-во "Da Vinci инженерно Пресс", 2006. - 506 с.

13. Rajanish К. Kamat. Unleash the System On Chip using FPGAs and Handel С Текст. / Rajanish К. Kamat, Santosh A. Shinde, Vinod G Shelake. 2009 г., 176 стр.14. http://www.parallel.ru

14. An Overview and Benchmark Study of the Starbridge Reconfigurable Computing Platform. David Tamjidi, UNIVERSITY OF CALIFORNIA, SAN DIEGO, 2005

15. Porting EDIF Netlists to the Viva Environment for Integrated Custom Computing Applications. Sreesa Akella. MAPLD-2003: Military Applications of Programmable Logic Devices

16. Кластеры на многоядерных процессорах Текст. / И.И. Ладыгин, А.В. Логинов, А.В. Филатов, С.Г. Яньков. М.: Издательский дом МЭИ, 2008. -112 с.

17. Корнеев В.Д. Параллельное программирование в MPI Текст. / 2-е изд., испр. Новосибирск: Изд-во ИВМиМГ СО РАН, 2002. - 215 с.

18. Левин, М.П. Параллельное программирование с использованием ОрепМР Текст.: монография / М.П. Левин. Изд-во Бином. Лаборатория знаний, 2008.

19. PVM: Parallel Virtual Machine. A Users Guide and Tutorial for Networked Parallel Computing 1994 Massachusetts Institute of Technology

20. Соловьев В.В., Климович А. Логическое проектирование цифровых систем на основе программируемых логических интегральных схем Текст. Изд-во: Горячая Линия Телеком, 2008 г. 376 с.29. http://fyga.parallel.ru/cpld.html

21. Пряхин В.Н. Обзор отечественных суперкомпьютеров последнего десятилетия. Текст. / «Мир ПК», № 09, 2010

22. Черняк Л.А. НРС конец мелового периода. Текст. / «Открытые системы», № 03, 201032. http://www.starbridgesystems.com33. http://www.nallatech.com34. http:// www.dinigroop.com35. http://www.nallatech.com/PCIe-280/overview.html

23. DIMEtalk User Guide. Nallatech Limited. Issue 1 October 19, 200537. http://www.rosta.ru38. http://www.mvs.tsure.ru39. http://www.rdi-kvant.ru/

24. Зотов В.Ю. Проектирование цифровых устройств на основе ПЛИС фирмы XILINX в САПР WebPACK ISE Текст. М.: Горячая линия-Телеком. 2003 624 с.

25. Quartus II Handbook Version 10.1 Volume 1: Design and Synthesis. Altera Corporation 2010.

26. Libero IDE v9.1 User's Guide. Actel Corporation 2010.

27. Altium Designer FPGA Design Basics. Altium Limited 2008.45. http://www.starbridgesystems.com/viva-software

28. Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные структуры Текст.: монография / И.А. Каляев, И.И. Левин, Е.А. Семерников, В.И. Шмойлов; под общ. ред. И.А. Каляева. 2-е изд., перераб. и доп. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009. - 344 с.

29. Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations. Bradford L. Chamberlain. 1998

30. Пирогов E.B. Проектирование и технология печатных плат. Текст.: Учебник. М.: ФОРУМ: ИНФРА-М, 2005. - 560 с.

31. Multilevel Graph Partitioning Schemes. George Karypis and Vipin Kumar. Technical report. Department of Computer Science, University of Minnesota, Minneapolis 1995.

32. George Karypis and Vipin Kumar. Analysis of Multilevel Graph Partitioning. In Proceedings of the 1995 ACM/IEEE Supercomputing Conference, page 658-677. ACM/IEEE, December 1995.

33. Stephen Т. Barnard. PMRSB: Parallel multilevel recursive spectral bisection. In Proceedings of the 1995 ACM/IEEE Supercomputing Conference, page 602-625. ACM/IEEE, December 1995.

34. Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? SIAM Journal of Scientific Computing, 18(5): 1436-1445, September 1997.

35. В. Hendricson and R. Leland. Multidemensional spectral load balancing. Sandia National Laboratories, Albuquerque, NM, January 1993

36. B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970

37. С. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proc. 19th IEEE Design Automation Conference, 1982.

38. George Karypis and Vipin Kumar. A Fast And High Quality Multilevel Scheme For Partitioning Irregular Graphs. SIAM Journal of Scientific Computing, 20(1): 359-392, 1998.

39. Soper A.J, Walshaw C., Cross M., A Combined Evolutionary Search and Multilevel Optimization Approach to Graph Partitioining, 2004.

40. Архив графов С. Walshaw, http://staffweb.cms.gre.ac.uk/~c.walshaw64. http://www.aco-metaheuristic.org/

41. A.L. Vizine, L.N.D. Castro, E.R. Hruschka, and R.R. Gudwin, "Towards Improving Clustering Ants: An Adaptive Ant Clustering Algorithm", presented at Informatica (Slovenia), 2005, pp. 143-154.

42. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Текст. / М.: Радио и связь, 1990.-352 с.

43. Основы проектирования интегральных схем и систем. Г.Г.Казённов Текст. / М.: БИНОМ. Лаборатория знаний, 2005. 295 с.

44. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. 2-е изд., перераб. и доп. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. -336

45. Xilinx. Virtex-6 Family Overview. Advance Product Specification, ver 2.2, January 28, 2010

46. Altera. Stratix V Device Handbook, Volume 1: Overview and Datasheet (ver 1.2, May 2011, 1 MB)

47. Суворова E.A. Проектирование цифровых систем на VHDL Текст. / Суворова Е.А., Шейнин Ю.Е. // СПб.: БХВ-Петербург, 2003. 576 с

48. Харари Фрэнк. Теория графов Текст. / Под ред. Г. П. Гаврилова. Изд. 2-е. М.: Едиториал УРСС, 2003. - 296 с.

49. Свами М., Тхуласираман К. Графы, сети и алгоритмы. Текст. / М.: Мир, 1984.-455 с.

50. Малика, А.С. Автоматизация конструирования РЭА Текст. / А.С. Малика, В.А. Деньдобренко. М.: Высшая школа, 1988. 304 с.

51. Bruce Hendrickson, Tamara G. Kolda. Graph partitioning models for parallel computing. Parallel Computing Journal 26 (2000)

52. Martin J.G. Spectral techniques for graph bisection in genetic algorithms. — Gecco'06. Washington, DC (USA), 2006.

53. H. D. Simon. Partitioning of unstructured problems for parallel processing. Proc. Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications Pergammon Press. 1991.

54. Якобовский M.B. Распределенные системы и сети. Текст. / Учебное пособие. // М.: МГТУ «Станкин», 2000.- 118с.

55. Michael Т. Heath and Padma Raghavan. A cartesian parallel nested dissection-algorithm. SI AM Journal on Matrix Analysis and Applications, 16(1):235-253, January 1995.

56. Pothen A. Graph partitioning algorithms with applications to scientific computing. Kluwer Academic Press, 1996

57. Karypis G. and Kumar V. Multilevel algorithms for multi-constraint graph partitioning. Technical Report, Department of Computer Science, University of Minnesota, 1998.

58. Karypis G. and Kumar V. A Fast And High Quality Multilevel Scheme For Partitioning Irregular Graphs. SIAM Journal of Scientific Computing, 20(1): 359392, 1998.

59. Bruce Hendrickson and Robert Lelad. A multilevel algorithm for partitioning graphs. In Proceedings of the 1995 ACM/IEEE Supercomputing Conference, page 626-657. ACM/IEEE, December 1995.

60. Karypis G. and Kumar V. Multilevel k-way Partitioning Scheme for Irregular Graphs. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 48, 96-129 (1998)

61. T. Goehring and Y. Saad, Heuristic Algorithms for Automatic Graph Partitioning, Tech. rep., Department of Computer Science, University of Minnesota, Minneapolis, 1994.

62. Галкина B.A. Дискретная математика. Комбинаторная оптимизация на графах. Текст. / Учебное пособие. // М.: Гелиос АРВ, 2003. 232 с.

63. Головицына М.В. Автоматизированное проектирование промышленных изделий / Интернет университет информационных технологий intuit.ru электронный ресурс. http://www.intuit.rU/department/hardware/autprpi/l

64. Миков А.И., Замятина Е.Б. Распределенные системы и алгоритмы / Интернет университет информационных технологий intuit.ru электронный ресурс. - http://www.intuit.ru/department/algorithms/distrsa/12

65. Дордопуло А.И. Средства программирования реконфигурируемых многопроцессорных вычислительных систем / Текст. / Дордопуло А.И. Гудков, В.А., Сластен JI.M., Гуленок А.А. Известия ТРТУ. // Тематический выпуск

66. Интеллектуальные и многопроцессорные системы». — Таганрог: Изд-во ТРТУ, 2006. № 16 (71). Специальный выпуск. — С. 16-20.

67. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов. Текст. / Учебное пособие. Таганрог ТРТУ 1995 90 стр.

68. Гуленок A.A. Методы и алгоритмы отображения графов задач на реконфигурируемые вычислительные системы. Текст. / Вестник компьютерных и информационных технологий. М.: Машиностроение, 2011. -№6.-С. 3-11.

69. Коваленко А.Г. Решение задачи диагностики дорожных покрытий на реконфигурируемой вычислительной системе с применением языка COLAMO. Текст. / Искусственный интеллект. // Донецк: Наука i освгта, 2009. №.3 -С.64-67.

70. Черняк JI.A. Архитектура фон Неймана, реконфигурируемые компьютерные системы и антимашина. Текст. / Открытые системы №6, 2008.

71. РАСЧЁТ ОГРАНИЧЕНИЯ НА СУММУ ВНЕШНИХ СВЯЗЕЙ НА ПРИМЕРЕ БАЗОВЫХ МОДУЛЕЙ С ОРТОГОНАЛЬНОЙ ТОПОЛОГИЕЙ1. СВЯЗЕЙ

72. ГУЛЕНОК АНДРЕЙ АЛЕКСАНДРОВИЧ

73. СИНТЕЗАТОР СТРУКТУРНЫХ ПАРАЛЛЕЛЬНЫХ ПРИКЛАДНЫХ ПРОГРАММ ДЛЯ МНОГОКРИСТАЛЬНЫХ РЕКОНФИГУРИРУЕМЫХ1. ВЫЧИСЛИТЕЛЕЙ0513.11 Математическое и программное обеспечение вычислительных машин,комплексов и компьютерных сетей

74. П. 1. РАСЧЁТ ОГРАНИЧЕНИЯ НА СУММУ ВНЕШНИХ СВЯЗЕЙ НА ПРИМЕРЕ БАЗОВЫХ МОДУЛЕЙ С ОРТОГОНАЛЬНОЙ ТОПОЛОГИЕЙ1. СВЯЗЕЙ

75. На рис. П.1 представлены структуры базовых модулей с различной ортогональной топологией связей, встречаемых на практике.

76. Рис. П.1. Различные топологии базовых модулей

77. Всего в базовом модуле, представленном на рис. П. 1а), количество связей между кристаллами ПЛИС равно 24Ь. Тогда теоретически Ьтах можно рассчитать по следующей формуле:1.241

78. ФАЙЛ ОПИСАНИЯ СТРУКТУРЫ РЕКОНФИГУРИРУЕМЫХ1. ВЫЧИСЛИТЕЛЕЙ

79. ГУЛЕНОК АНДРЕЙ АЛЕКСАНДРОВИЧ

80. СИНТЕЗАТОР СТРУКТУРНЫХ ПАРАЛЛЕЛЬНЫХ ПРИКЛАДНЫХ ПРОГРАММ ДЛЯ МНОГОКРИСТАЛЬНЫХ РЕКОНФИГУРИРУЕМЫХ1. ВЫЧИСЛИТЕЛЕЙ0513.11 Математическое и программное обеспечение вычислительных машин,комплексов и компьютерных сетей

81. П.2. ФАЙЛ ОПИСАНИЯ СТРУКТУРЫ РЕКОНФИГУРИРУЕМЫХ1. ВЫЧИСЛИТЕЛЕЙ

82. Описание архитектуры РВС включает в себя описание кристаллов ПЛИС, блоков распределенной памяти (РП), контроллера базового модуля (КБМ), их связей и разрядность связей.

83. Создание файла архитектуры реконфигурируемой МВС1. Конец ^

84. Рис. П.2. Структурная схема алгоритма работы программы ВМОезспр1:ог

85. Структура описания архитектуры реконфигурируемой МВС выглядитследующим образом:

86. БМ1> <Количество ПЛИС> </Количество ПЛИС> <ПЛИС №1> <Имя ПЛИС> </Имя ПЛИС>

87. Количество смежных элементов> </Количество смежных элементов> <Смежный элемент №1> <Тип смежного элемента>

88. ПЛИС в данном БМ, ПЛИС в другом БМ, КЕМ или РП.1. Тип смежного элемента>1. Имя смежного элемента>1. Имя смежного элемента>1. Разрядность соединения>

89. Разрядность соединения> <Имена выводов ПЛИС> </Имена выводов ПЛИС> <Смежный элемент №1>

90. Смежный элемент №2>. .</Смежный элемент №2>

91. Ресурс, предоставляемый ПЛИС> </Ресурс, предоставляемый ПЛИС> </ПЛИС №1>

92. ПЛИС №2>. .</ПЛИС №2> </БМ1>

93. СИНХРОНИЗАЦИЯ ИНФОРМАЦИОННЫХ И УПРАВЛЯЮЩИХ ПОТОКОВ В ИЕРАРХИЧНЫХ ИНФОРМАЦИОННЫХ ГРАФАХ

94. ГУЛЕНОК АНДРЕЙ АЛЕКСАНДРОВИЧ

95. СИНТЕЗАТОР СТРУКТУРНЫХ ПАРАЛЛЕЛЬНЫХ ПРИКЛАДНЫХ ПРОГРАММ ДЛЯ МНОГОКРИСТАЛЬНЫХ РЕКОНФИГУРИРУЕМЫХ1. ВЫЧИСЛИТЕЛЕЙ0513.11 Математическое и программное обеспечение вычислительных машин,комплексов и компьютерных сетей

96. П.З. СИНХРОНИЗАЦИЯ ИНФОРМАЦИОННЫХ И УПРАВЛЯЮЩИХ ПОТОКОВ В ИЕРАРХИЧНЫХ ИНФОРМАЦИОННЫХ ГРАФАХ