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

Гуленок Андрей Александрович С*-

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

Специальность 05,13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

2 8 ИЮЛ 2011

Таганрог - 2011

4851842

Работа выполнена на кафедре Интеллектуальных и многопроцессорных систем (ИМС) Технологического института Южного федерального университета в г. Таганроге и в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика A.B. Каляева федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» (НИИ МВС ЮФУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук,

Левин Илья Израилевич

ОФИЦИАЛЬНЫЕ

ОППОНЕНТЫ: доктор технических наук,

профессор

Курейчик Владимир Викторович

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

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: ЗАО «ЭВРИКА», г. Санкпг-Петербург

Защита диссертации состоится «26» августа 2011 г. в 1410 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корп. «И», комн. 347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «/Я »¿¿М.\stJL_2011 г.

Просим Вас прислать отзыв, заверенный печатью учреждения, по адресу: 347928, г. Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44, Технологический институт Южного федерального университета в г. Таганроге, Ученому секретарю диссертационного совета Д 212.208.24 Кухаренко Анатолию Павловичу.

Ученый секретарь диссертационного совета кандидат технических наук, доцент " А.П. Кухаренко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- ОКР «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе

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

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

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

- ОКР «Разработка технологии ресурсонезависимого параллельного программирования для многопроцессорных вычислительных систем различных классов» по государственному контракту № 02.447.11.1005 от 22 июля 2005 г.;

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

Результаты диссертации внедрены в НИВЦ МГУ (г. Москва), ФГУП «НИИ «Квант» (г. Москва), ФГУП «Курский НИИ» МО РФ (г. Курск), Южном научном центре РАН (г. Ростов-на-Дону), НИИ МВС ЮФУ (г. Таганрог).

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

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

(2007 г. Москва); на Пятой Международной научной молодежной школе «Высокопроизводительные вычислительные системы» (с. Кацивели, Украина, 2008); на Международной научной молодежной школе «Системы и средства искусственного интеллекта (ССИИ-2008) (с. Кацивели, Украина, 2008); на Международной научно-технической конференции «Суперкомпыотерные технологии: разработка, программирование, применение (СКТ-2010)» (с. Дивноморское, Россия, 2010); на Седьмой Международной научной молодежной школе «Высокопроизводительные вычислительные системы» (с. Дивноморское, Россия, 2010).

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

Публикации. По результатам диссертации опубликовано 15 печатных работ, из них 6 статей, из которых 2 статьи опубликованы в ведущих рецензируемых научных журналах, входящих в Перечень ВАК РФ, тезисы и материалы 9 докладов на международных и российских научно-технических конференциях. По теме исследования получено 2 свидетельства об официальной регистрации программ для ЭВМ, результаты работы отражены в 9 отчетах о НИОКР.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников и четырёх приложений. Работа содержит 156 страниц основного текста, 50 рисунков, список используемой литературы из 99 источников, 45 страниц приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

- компоновка информационных графов структурных программ;

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

- трассировка внешних связей размещённых подграфов.

Разработан общий алгоритм работы синтезатора структурных параллельных прикладных программ для многокристальных РВС (рис. 1), отличающийся от известных включением этапа загрузки описания структуры РВС. В предложенном алгоритме перед началом отображения информационного графа на ресурс РВС загружается описание структуры реконфигурируемого вычислителя S=<Si,S2,...SK>, где 5} - описание кристалла ПЛИС с номером j=J..N. На h-й итерации решения задачи отображения структурных программ на РВС в множестве параметров РА определяется выбор одного из реализованных алгоритмов компоновки информационных графов и указываются различные критерии для данного алгоритма.

Файлы описаний структур мнсгокристапьных рве

Описание информационного графа параллельной прикладкой nporpawwai '

С

Начало

J

/ загрузка описания —/ структуры РВС / S=<Si.S7....Sw> /

/ Загрузка -уинформ ационного граф; /_задачи G

1 (Формирование кортежа | параметров компоновки Р=<Р,.Р,....РЯ:

1

Формирование кортежа вариантов размещения A=<AlÄ?.-Am>

q=1

" Размещение подграфов ~ согласно варианту А,:

Рис. 1. Структурная схема общего алгоритма работы синтезатора

Если в результате компоновки информационных графов сформировано множество подграфов {Gi,G2, — GJ, удовлетворяющих существующим ограничениям, то алгоритм работы синтезатора переходит на этап формирования кортежа вариантов размещения подграфов в ПЛИС многокристальной РВС А=<А/,А!,...А„,>. Варианты размещения выбираются из кортежа А последовательно. После того как из кортежа А выбран вариант размещения Aq, подграфы С(, /=7..« размещаются в тех ПЛИС, которые заданы в Aq, что в структурной схеме алгоритма задаётся функцией PfSj^G,.

Когда подграфы размещены в соответствующих ПЛИС, необходимо решить задачу трассировки всех внешних связей подграфов. Формирование трассы в структурной схеме алгоритма определяется функцией T(L(F4(Sk))—*L(Fq(S^)), где функция L(x) определяет множество внешних связей для подграфа х.

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

Если ни для одного из вариантов размещения не удалось решить задачу трассировки, то переменная h наращивается: h=h+l, и отображение информационного графа на ресурс многокристальной РВС повторяется с этапа компоновки.

Основным этапом задачи отображения информационных графов расчётоёмких задач, определяющим эффективность структурных программ, является компоновка. Классическая задача компоновки заключается в разделении исходного графа G=(V,E) на множество непересекающиеся подграфов Graphs={Gi, G2, ... G„J.

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

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

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

В первой главе рассмотрены существующие программные средства, эффективно решающие задачу компоновки в её классической постановке (СНАСО, METIS, JOSTLE, PARTY), а также методы и алгоритмы, использованные в них. Показано, что для эффективного решения задачи компоновки информационных графов параллельных прикладных программ данные программные средства не подходят из-за существующих дополнительных ограничений. Среди рассмотренных методов и алгоритмов компоновки наиболее перспективными для решения задачи компоновки информационных графов структурных программ являются следующие:

- многоуровневая схема компоновки (multilevel partitioning scheme);

- метод рекурсивной бисекции;

- последовательный алгоритм «жадного» роста регионов (greedy region growing).

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

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

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

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

Для компоновки графов больших размерностей зачастую используется многоуровневая схема компоновки. Идея многоуровневой схемы компоновки заключается в последовательном прохождении 3-х этапов: «огрубления» исходного графа до нескольких сотен вершин; компоновки огрублённого графа; восстановления огрублённого графа и оптимизации сформированных подграфов.

Для эффективного решения задачи автоматического отображения информационных графов структурных программ результаты, формируемые на этапе компоновки, должны быть адекватны имеющейся структуре физических каналов связей в многокристальной РВС. Поэтому в многоуровневую схему компоновки информационных графов структурных программ в начало добавлен этап расчёта ограничений на сумму внешних связей подграфов. Показано, что необходимым условием существования решения задачи трассировки является существование хотя бы одного соответствия между элементами множества Graphs и множества кристаллов ПЛИС - Bodies такого, что для любого DD е Bodies и соответствующего ему SubGe Graphs выполняется неравенство: Out(DD)>l(SubG), где Out(DD) - сумма линий связи, подключенных к кристаллу DD, L(SubG) - сумма внешних связей подграфа SubG.

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

В диссертации показано, что стремление сформировать наибольшее количество стягиваемых пар на каждой итерации часто приводит к плохим результатам для информационных графов задач, решаемых на РВС. Происходит это за счёт стягивания пар «слабосвязанных» вершин (число кратных рёбер между которыми относительно невелико), когда все смежные для них вершины уже присутствуют в сформированных парах. Чтобы снизить количество стягиваний «слабосвязанных» вершин, алгоритм попарного стягивания предлагается разделить на 2 этапа На первом этапе из множества вершин V выбираются лары смежных вершин х,е V, х,е V, l<i<\V|, l<j<\V|, itj: L(0(x„xj)<L(xJ и L(0(Xi,Xj))<L(xj), где 0(xltxj) - стянутая вершина, Цх) - количество внешних связей для вершины х.

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

На основании предложенных модификаций для этапа огрубления информационных графов разработан следующий модифицированный алгоритм попарного стягивания вершин:

1°. Оптимизация стянутых вершин;

2°. Если хоть одна вершина исходного информационного графа в ходе оптимизации была перемещена, то переход к п. 1

3°. Если число вершин в огрублённом графе меньше либо равно некоторому значению MAX., то переход к п .8°;

4°. Производится выбор множества непересекающихся пар стягиваемых вершин Pairs: V(a,b)e Pairs,: L(0(a,b))<L(a) и L(0(a,b))<L(b)\

5°. Если Pairsfo, то осуществляется процедура стягивания пар вершин из множества Pairs и переход к п .1°;

6°. Производится выбор множества непересекающихся пар стягиваемых вершин Pairs в соответствии с классическим алгоритмом попарного стягивания;

7°. Если Pairsfo, то осуществляется процедура стягивания пар вершин из множества Pairs и переход к п . 1°;

8°. Конец.

Параметр МАХ определяет максимальное число вершин, которое должно получиться после последней итерации алгоритма огрубления. На практике этот параметр варьируется от числа ПЛИС в РВС и равен 10- j Bodies |.

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

Широкое применение в существующих программах компоновки находят известные методы рекурсивной бисскции (recursive bisection). Для компоновки огрублённых информационных графов структурных программ были выбраны два существующих способа рекурсивной бисекции. Первый способ: на ;-й итерации от нераспределённой части графа GOl=i(V-Vi-Vr...Vj.i, Еаа) отрезается подграф Gi=(Vi,EJ, максимальный ресурс которого не превышает ресурс одной ПЛИС. Второй способ рекурсивной бисекции предполагает последовательное разделение исходного графа на 2, 4, 8 и т.д. подграфов. Так, на первой итерации необходимо получить 2 подграфа, ресурс каждого из которых не превышает суммарный ресурс половины множества ПЛИС в РВС. На второй итерации каждый из полученных подграфов разрезается на 2 новых подграфа, ресурс которых не превышает суммарного ресурса четверти имеющихся ПЛИС, и так далее.

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

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

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

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

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

Входными данными для этапа размещения являются множество подграфов Graphs и множество ПЛИС многокристальной РВС - Bodies.

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

п-1 п п т m-1 m

Z d(GltGj) + (I. I c(Gt,Gj)+ £ Z dG»Gj)),

/=1 j=i+1 i—l J —ff+l i=Л+1 y=/+l

где m=\Graphs\, d(G„GJ - функция, задающее предполагаемое количество занимаемых линий связей, необходимых для трассировки связей между размещёнными подграфами Gt и G,, c(GiyGj) — функция, задающее суммарное количество связей между подграфами G, и G}, п - количество размещённых подграфов на текущей итерации алгоритма

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

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

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

Классический волновой алгоритм Ли не позволяет использовать при формировании трассы ранее проложенные равнопотенциальные шины. На рис. 2а) представлен пример работы классического волнового алгоритма Ли (стрелками обозначены разрешённые направления распространения волны). Пунктиром обозначена ранее проложенная равнопотенциальная шина, которая имеет разрядность «27». Сплошной линией указаны возможные трассы с минимальным числом дискретов, сформированные классическим алгоритмом Ли для текущей шины, которая имеет разрядность «32». Количество занятых линий связи для всех возможных трасс, построенных классическим волновым алгоритмом Ли, составляет «128».

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

1.5.

TL

4 - - 2

128 к 2 Т i 1 f i . .L 1

HI т 0

U 4

— 3

2

а)

б)

Рис. 2. Результаты работы волновых алгоритмов

На рис. 26) представлен результат работы волнового алгоритма Ли с модифицированной процедурой формирования карты волновых фронтов. Связям между кристаллами поставлено в соответствие число линий связи, необходимых для трассировки текущей шины. Сплошной линией показана трасса с минимальным числом занимаемых линий связей, полученная с помощью модифицированного волнового алгоритма Ли. Количество занятых линий связи в данном случае составило « Ш».

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

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

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

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

На рис. 3 представлены основная экранная форма синтезатора и результат его работы - сгенерированный УНОЬ-код, описывающий информационный граф задачи.

Рис.3. Синтезатор структурных параллельных прикладных программ

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

На рис. 4 представлен результат отображения информационного графа задачи «Томографии дорожных покрытий» на реконфигурируемый вычислитель «Алькор» (НИИ МВС ЮФУ), содержащий 16 пользовательских ПЛИС У^ех 5.

Рис.4. Результат отображения задачи «Томографии дорожных покрытий» на

реконфигурируемый вычислитель «Алькор»

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

НИИ многопроцессорных вычислительных систем ЮФУ. В таблице представлены максимальные показатели, достигнутые за время эксплуатации синтезатора.

Таблица

Результаты эксплуатации синтезатора

Максимальное суммарное число вершин в графе 2 508 944

Максимальное число дуг в графе 34 498160

Максимальный процент заполнения базового модуля (по LUT таблицам) 78%

Максимальный процент заполнения базового модуля (по максимальному ресурсу) 92%

Ускорение на задачах с целочисленными операциями (по сравнению с ПК) 1.5* I0J

Ускорение на задачах с битовыми операциями (по сравнению с ПК) 1.8*10'*

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

схему компоновки;

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1) Гуленок, A.A. Методы и алгоритмы отображения графов задач на реконфигурируемые вычислительные системы [Текст] / A.A. Гуленок, И.И. Левин // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2011. -№6. - С. 3-11 (ведущий рецензируемый журнал, входит в перечень ВАК);

2) Гуленок, A.A. Средства программирования реконфигурируемых многопроцессорных вычислительных систем [Текст] / В.А. Гудков, A.A. Гуленок, А.И. Дордопуло, Л.М. Сластен // Известия ТРТУ. - Таганрог: Изд-во ТРТУ, 2006. - №16. - С. 16-20 (ведущий рецензируемый журнал, входит в перечень ВАК);

3) Гуленок, A.A. Оптимизация алгоритма попарного стягивания для многоуровневой схемы для графов задач, решаемых на РВС. [Текст] / A.A. Гуленок // Материалы конференции «Искусственный интеллект. Интеллектуальные системы. ИИ-2010». - Донецк: Изд-во ИЛИИ «Наука i освгга», 2010. - Т. 1. - С. 100-104;

4) Гуленок, A.A. Синтезатор для формирования разбиения информационных графов прикладных задач для многоплатных реконфигурируемых вычислительных систем [Текст] / A.A. Гуленок // Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС-2009). - Таганрог: Изд-во ТТИ ЮФУ, 2009,- Т. 1,- С. 154-157;

5) Гуленок, A.A. Среда разработки масштабируемых структурных компонентов для реконфигурируемых систем [Текст] / A.A. Гуленок // Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы - 2007». - Таганрог: Изд-во ТТИ ЮФУ, 2007. - С. 289-292.

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

ЛР №020565 от 23 пот 1997г. Подписано к печати_.07.2011 г.

Формат 60x841/16. Букага офсетная. Печать офсетнах. Усл. п.л. - 1А. Уч.-шдл. -1,1.

Заказ № ><5 Т Тираж 120экз.

ГСП 17А, Таганрог, 28, Нскрасо некий, 44 Типография Технологического института Южного федерального университета в г. Таганроге

ВВЕДЕНИЕ.

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].

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

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

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

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. П.З. СИНХРОНИЗАЦИЯ ИНФОРМАЦИОННЫХ И УПРАВЛЯЮЩИХ ПОТОКОВ В ИЕРАРХИЧНЫХ ИНФОРМАЦИОННЫХ ГРАФАХ