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

На правах рукописи

Минайлов Виктор Викторович

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 О ДЕК 2012

Курск-2012

005047605

Работа выполнена в ФГБОУ ВПО «Юго на кафедре вычислительной техники

'-Западный государственный университет

Научный руководитель: доктор технических наук, профессор,

заслуженный деятель науки Российской Федерации Титов Виталий Семенович

Официальные оппоненты: Сизов Александр Семенович

доктор технических наук, профессор, заслуженный деятель науки Российской Федерации,

Научно-исследовательский центр (г. Курск) ФГУП «18 ЦНИИ» МО РФ, главный научный сотрудник

Малышев Александр Васильевич

кандидат технических наук, доцент, Юго-западный государственный университет,

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

тет

Защита диссертации состоится «24» декабря 2012 г. в 11:00 часов на заседани диссертационного совета Д 212.105.02 при Юго-западном государственно! университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал). С диссертацией можно ознакомиться в библиотеке Юго-западного государственног университета.

Автореферат разослан «24» ноября 2012 г.

Ученый секретарь диссертационного совета

Зотов Игорь Валерьеви1

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

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

Теория параллельной организации и отказоустойчивой работы мультиконтроллеров достаточно широко разработана. Большой вклад в эту область внесли работы отечественных ученых: Вл. В. Воеводин, В.В. Воеводин, A.B. Каляев, И.А. Каляев, И.И. Левин, А.П. Типикин, а также зарубежных ученых: М. Флинн, К. Ванг, Д. Скилликорн, Э.А. Трахтенгерц. Однако в данных работах вопросы построения отказоустойчивых реконфигурируемых СЛУ высокой готовности рассматривались частично. В то время как при использовании устройств на ПЛИС в таких системах при возникновении функционального отказа, необходима оперативная ее реконфигурация.

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

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

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

конфигурирование внутренних связей в случае выхода из строя одного из внутре] них модулей СЛУ.

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

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

Объект исследования: системы логического управления высокой готовности.

Предмет исследования: Метод, алгоритмы и аппаратные средства планиров; ния топологии программируемых логических интегральных схем.

Работа выполнена по плану инициативных НИР 2009-2013 г.г. кафедры вь числительной техники Юго-западного государственного университета.

Задачи исследований:

1. Анализ состояния вопроса и обоснование необходимости создания устройся планирования топологии ПЛИС в реконфигурируемых многозадачных СЛУ выс< кой готовности в динамическом режиме.

2. Создание метода планирования топологии ПЛИС в многозадачных СЛ5 обеспечивающего сокращение времени реконфигурации.

3. Разработка методики и алгоритма планирования размещения подпрограмм ПЛИС, позволяющих сократить время поиска варианта размещения.

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

Научна новизна н положения выносимые на защиту:

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

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

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

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

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

Практическая ценность результатов исследований:

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

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

3. Разработанная методика ускоренного планирования топологии ПЛИС позволяет уменьшить коммуникационные задержки в 1.4-2.95 раза.

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

Практическое использование результатов работы. Результаты, полученные в диссертационной работе, внедрены в филиале ОАО «РЖД, Курская дистанция энергоснабжения», ООО ПП «Микрокод», ООО «Совтест-АТЕ», ОАО «Союз Телефон-строй» СМУ в г. Курске, а также используются в учебном процессе на кафедре вычислительной техники ЮЗГУ при проведении занятий по дисциплинам «Организация ЭВМ и систем», «Теоретические основы организации многопроцессорных комплексов и систем».

Соответствие паспорту специальности. Согласно паспорту специальности 05.13.05 - Элементы и устройства вычислительной техники и систем управления, проблематика, рассмотренная в диссертации, соответствует пунктам 1 и 2 паспорта специальности (1. Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления. 2. Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико-экономических и эксплуатационных характеристик).

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

лись и получили положительную оценку на следующих конференциях и семинара; XIII Международной научно-технической конференции «Машиностроение и технс сфера XXI века» (Донецк-Севастополь, 2011), всероссийской научно-техническо конференции «Интеллектуальные и информационные системы» (Тула, 2011) и : Международной конференции «Оптико-электронные приборы и устройства в сиг темах распознавания образов, обработки изображений и символьной информаци (Курск, 2010).

Публикации. Содержание диссертации опубликовано в 12 научных работа; среди которых имеются 3 статьи в рецензируемых научных журналах и издания; два патента РФ на изобретение и два свидетельства о регистрации программы ЭВМ.

Личный вклад соискателя. Все выносимые на защиту научные результат! получены соискателем лично. В работах по теме диссертации, опубликованных соавторстве, лично соискателем предложено: в [1,9,11] алгоритм и методика поиск размещения, в [4,5,6,8] принцип построения аппаратной части акселератора, в [2,2 критерий оценки качества размещения, в [12] методика тестирования программы.

Структура и объем работы. Диссертация включает введение, четыре главь заключение, список литературы из 85 наименований, приложения. Основная част диссертации изложена на 114 страницах машинописного текста, содержит 35 рисук ков и 10 таблиц.

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

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

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

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

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

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

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

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

Программа (подпрограмма) представлена графом взаимодействия задач: 0=<Х,Е>, (1)

где Х =

VI

множество вершин графа О, вершины хцк е X которого соответствуют задачам (подпрограммам), а дуги е^ е Е связям между ними, которые передаются между подзадачами и сведены в матрицу смежности (МС) М = \\тп II , где N = \х\.

II •'ВДхЯ|' ' '

Топология ПЛИС задана графом Н, который представлен как:

А,1 Р1.2 - Ртё Р\, п

н= Р2,\ Рг,г - Рш,0 Рг,п

Рт,\ Рт,2 ■ Рш,в Рт,п

где Рш в -отдельные модули ПЛИС, причем {т = \,т, в = \.п). Модуль представляется в виде функции Р(0,Х), т.е.

Ра,в=Р{0,Х), (2)

где 0 = о1,о2,...,о:с - множество входов модуля, а Х = хих2,...,х^ - множество выходо!

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

01-

02-О)-

°Г

Рш,в

Рис. 1. Схема модуля ПЛИС Как видно из рисунка 1, величина Е, (количество входов и/или выходов), пред ставленная в (2) зависит от конкретной схемной реализации модуля ПЛИС и не и-вестна заранее. Под межсоединением в модуле ПЛИС будем понимать трассу от о; ного вывода о, или Xj (/ = (1,£),у = (1,#)) модуля к другому. На рис. 2 приведен прр мер межсоединения.

1 2 3

3 2

1 1 0 0

2 0 1 0

3 1 0 1

4 1 0 0

5 0 1 1

1 2 3 4 5 Рис. 2. Межсоединения в модуле ПЛИС

Рис. 3. Матрица цепей по рис. 2.

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

Матрицей цепей (МЦ), описывающая вариант размещения модулей ПЛИС, на зывается прямоугольная матрица К = где / = = п = \Х\, а представляв

собой суммарное количество межсоединений, полученных в результате размещени подпрограмм в модулях ПЛИС. Вариант МЦ приведен на рис. 3.

На рис. 3 приведена матрица цепей, соответствующая варианту размещения представленному на рис. 2. В данном случае в строках представлены выводы моду ля(ей) ПЛИС, а в столбцах — межсоединения, соответствующие данному вариант размещения.

Мощность множества |Р| зависит от числа межсоединений, полученных в ре зультате размещения модулей в ПЛИС. Параметр а соответствует количеству меж

соединений и заранее неизвестен. В работе показано, что должно выполняться соотношение:

а-»тт, (3)

Тогда размещение модулей в ПЛИС может быть описано отображением:

4.1 4.2 ■• 4.* • •• 4.л А.1 Р\, 2 ■ ■ Р\,к ■ Р\,п

4.1 4.2 •• 4• • 4.„ Рг,\ Р2,2 • ■ Р2,к • Р2,п

А=< 4.. 4.. ■■ 4* ■ • ->■ Рч, 1 Рч. 2 ' ■ Рч,к ■ Рч (4)

.4.1 4.2 • •• 4.* • • ХЧ Рт,\ Рт,2 ■ Рт,к ■ ' Рт,п

где ¿>=1,ЛП. В (4) символ —» означает отображение одной из вершин х5 к е X на один из модулей рд к е Н. Здесь 5 - номер очередной перестановки, соответствующий 5-му варианту размещения. Мощность множества у/ = {Рв} всевозможных отображений (4) равна числу всевозможных перестановок задач хдкеХ в матрице М:

и=т.

Пусть ¥ — множество всевозможных отображений вида (4). Тогда задачу размещения, можно сформулировать как поиск отображения Р'еЧ*, такого, что Г.=шт{тах{Тд(|У| )}},

Р ч> р^т ^ рч.к Р;

где ТА(М ) _ задержка при передаче данных в модуле р^, соответствующая

отображению р„. В выражении (5) тах означает поиск максимальной задержки в _ _АеЧ»

процессоре рчк, где q = l,п, к = 1,а; выражение гшп соответствует поиску минимально возможного значения задержки для максимального тах \ Тп I М

ДеЧЧ'Н рч*.

Под смежным контактом (СК) будем понимать такое расположение выводов модулей ПЛИС при котором выполняется условие:

,7-1

= 1

(6)

При поиске варианта размещения модулей ПЛИС должно выполнялись соотношение:

£бд->тах, (7)

где Д=1 ,п.

Поиск наилучшего варианта размещения р* по критерию (5) является трудоемкой переборной задачей. Одним из путей решения этой задачи может быть применение целенаправленных перестановок строк и столбцов МЦ так, чтобы выполнялись соотношения (3) и (7).

В работе показано, что ускорение поиска возможно за счет допустимого сниже-

ния выигрыша величины коммуникационной задержки по сравнению с лучшими р< зультатами, достигаемыми при больших затратах времени на поиск. Для этого неоГ ходимо в ходе поиска контролировать степень уменьшения величины образующей« коммуникационной задержки (5) и принимать решение о целесообразности пpoдoJ жения поисковых перестановок строк и столбцов матрицы МЦ. Предложенная пр< цедура основана на вычислении недостижимого минимального значения размещ! ния Т^, как минимума коммуникационной задержки, который может быть дости нут при допущении, что топологии графов в и Н тождественны. При вычислен« нижней оценки будем назначать дуги графа в на самые короткие маршруты в гра<| Н, пренебрегая ограничениями, накладываемыми на фактические связи между по; программами в графе О. Ниже приведен соответствующий алгоритм:

1. Переписать элементы тк/ (к = 1~й, 1 = 1,Ы) матрицы Л/ = ||/Лу||^ ^ в векто[

строку М' = ||ту||, где т - порядковый номер элемента в М', причем к = 1^77, / = При этом г, >г2 и г2 - порядковые номера элементов в М'.

2. Вычислить

где i' = l,|£|, 2 = 1,|£| ,|£|- мощность множества Е в графе G; mz— одноименные эл( менты векторам'.

Для ускорения поиска разработана методика ускоренного выполнения процеду планирования размещения подпрограмм. Этапы методики:

1. Производится первичное размещение вершин графа G. Размещение реализ) ется путем наложения матрицы МС на матрицу МЦ, находится задержка Гн, соот ветствующую данному варианту размещения.

2. Для сопоставления вариантов размещения по критерию (5) вначале осущест вляется поиск нижней оценки Тн для графа G по алгоритму поиска порогового знг чения. Затем вычисляется степень близости максимальной задержки Т„, соответсп вующей первичному варианту размещения, к нижней оценке Тт{ в виде:

Т

с

3. Осуществляется перемещение строки так, чтобы после перестановки и расч£ та Т по (8) оценка:

снижалась по сравнению с г/н (9) и оценками т] по предыдущим вариантам разме щения.

4. Анализ достигнутой величины 77 (10) и оценка степени улучшения размеще ния выполняется по следующей формуле выигрыша в снижении коммуникационно! задержки.

(

1н _ТИ

На основании описанного выше метода и методики ускорения поиска выполнения процедур планирования топологии ПЛИС создан аппаратно-ориентированный алгоритм, реализованный в микропроцессорном акселераторе.

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

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

Целью исследования было определение величины а снижения задержки в результате применения разработанного метода при разных размерах МЦ, соответствующих различным степеням связности между подпрограммами. Результаты моделирования, а именно начальное и достигнутое отклонение задержки Т от Тм, разность необходимых при этом количества перестановок Q, а так же время, затраченная на поиск, выводятся на экран.

На рис. 4. Приведены результаты вычислительного эксперимента на ЭВМ, представленные в виде зависимости показателей а от т]н и т] от <3 (рис. 4).

ПЛИС.

I

N а

ти= тах I X V.. .(=1 /=1

Т0=ТН,М\ = М к = Ы, 1 = N

I

J

Trtf- 123 К0л-вс перестамово* :>21 T-161 Бремя - 2345mscck

I 175 fr

i 150

I 125

0

| 100

1 75 |

M 50 25

А УЧ А Ь

\т

T»f

---3>

Количество перестановок

Рис. 5. Зависимость показателя а от и rj от Q На рис. 5 представлена величина коммуникационной задержки с при первоначальном размещении Т„, и изменение величины коммуникационной задержки Т в ходе поисковых перестановок Q. На графике видно, что в результате величину коммуникационной задержки удалось улучшить со значения 175 до 161, приблизив его к минимальной нижней оценке Tinf, которая равна 123.

Таблица 1.

V 5 9 10 20 25 50 60

V 5! 9! 10! 20! 25! 50! 60!

Q 5 16 21 51 66 141 171

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

Таблица 2

V 9x9 10x10 10x15 15x15 20x20 20x25 25x25 50x50 60x60

rinf 33 53 67 73 204 243 317 1239 1832

Т 1 н 18 35 36 45 109 127 163 450 585

т 23 40 49 54 125 142 179 461 620

t, МКС 73 110 155 635 754 828 839 13323 16677

Q 16 20 21 19 51 51 66 141 171

91 10! 10! 15! 20! 25! 25! 50! 60!

Т Т 1.2 1.14 1.3 1.2 1.14 1.11 1.09 1.0 1.0

Т 1.43 1.3 1.36 1.35 1.63 1.71 1.77 2.68 2.95

т 1.8 1.5 1.0 1.6 1.8 1.9 1.9 2.75 3.8

ложенного критерия поиска позволяет приближаться к Тт{. Приведенные расчета данные свидетельствуют о целесообразности применения предложенного мето при выполнении «больших» вычислительных задач. Из таблицы 2 следет, что вр менные затраты при выполнении поисковых перестановок сущетвенно увеличиЕ ются с ростом размеренности задачи.

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

МП

оп

кпдп

Ппорт

контроллер

Прпорт

О

УУ =>{МО}

БПТПЛИС

к управляющей

. мс

МЦ -

БНО

БНЗ

Рис. 6. Структурная схема акселератора планирования топологии ПЛИС На рисунке 6 обозначены: БПТПЛИС — блок планирования топологии ПЛИС МП - микропроцессор, ОП - оперативная память, КПРДП - контроллер прямо1 доступа в память, Пппорт - параллельный порт, Мс - матрица смежности, МЦ матрица цепей, БПП - блок поисковых перестановок, БНО - блок нахождения м] нимальной нижней оценки, БНЗ - блок поиска начального значения коммуникащ онной задержки, БПП - блок поисковых перестановок.

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

необходим оперативный поиск нового варианта топологии, т.е. переразмещение подпрограмм, соответствующих решаемый в ПЛИС программе. Если необходимо составление нового варианта топологии, то в блок БПТПЛИС передаются нулевые матрицы МС и МЦ.

Блок планирования топологии ПЛИС функционирует следующим образом (рис. 5). В соответствии с алгоритмом составления плана топологии ПЛИС необходимо выполнить следующие шаги: 1) поиск порогового значения коммуникационной задержки, эта задача реализуется в БНО; 2) вычисление показателя коммуникационной задержки и соответствующего значения до начала выполнения поисковых перестановок, которая выполняется в блоке БНЗ; 3) выполнение поисковых перестановок с последующим вычислением достигнутого эффекта и анализ целесообразности дальнейшего продолжения работы алгоритма, что выполняется блоком БПП.

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

Рис. 7. Функциональная схема блока «Целенаправленная перестановка» В работе выполнен сравнительный анализ результатов экспериментальных исследований временной и аппаратной сложности, вычисленной в эквивалентных вентилях И, после чего было выполнено сопоставление с аналогичной программной реализацией (табл.3). На рис. 8 приведен результат анализа аппаратной сложности устройства.

А

Щр^Щ в

.Ум ч |НМ|

■ -г? ^еа. Шв 1 ■

V "

9x9

10*10 10*15 15x15 20x20 30*25 25*25

Разм ерность матрицы цепей Рис. 8. Зависимость аппаратной сложности от размерности матриц цепей

Таблица

Размеры МЦ ^р, мкс МКС

9x9 73 20

15x15 635 180

20x20 754 200

20x25 828 220

25x25 1839 300

В первом столбце приведены размеры МЦ (табл. 3), во втором - время, затр ченное программным способом обработки МЦ при составлении плана топологии, третьем - при соответствующей аппаратной реализации. Оценка аппаратных затр, осуществлялась для условий использования серии микросхем К1533.

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

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

ты.

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

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ в рецензируемых научных журналах и изданиях

1. Минайлов В.В. Методика планирования топологии программируемых логич ских интегральных схем в многопроцессорных системах [Текст] / B.B. М найлов, Д.Б. Борзов, В.В. Руденко, С.П. Гнездилова // Вестник КГСХА. 2012. №2, С. 126-129.

2. Минайлов В.В. Метод и алгоритм планирования топологии ПЛИС в мног процессорных системах [Текст] / В.В. Минайлов, Д.Б. Борзов // Известия Юг западного государственного университета. Серия. Управление, вычислител ная техника, информатика. Медицинское приборостроение. 2012. №2. Часть С. 23-27.

3. Минайлов В.В., Акселераторные средства составления плана топологии пр граммируемых логических интегральных схем [Текст] / Д.Б. Борзс И.В.Зотов, В.В. Минайлов // Известия Юго-западного государственного ун верситета. Серия. Управление, вычислительная техника, информатика. Мед цинское приборостроение. 2012. №2. Ч. 2, С. 30-35.

Патенты на изобретение

4. Патент 2379749 Российская Федерация G06F7/00. Устройство для подсче минимального значения интенсивности размещения в системах с древовиднс организацией [Текст] / В.В. Минайлов, Д.В. Борзов, заявл. 06.08.2008, опуб 20.01.2010, БИ№2,2010.

5. Патент 2010153834 Российская Федерация МПК G06F7/76, G06F17/10 Ус ройство поиска нижней оценки размещения в полносвязных матричных си темах при однонаправленной передаче информации [Текст] / Минайлов B.I Борзов Д.Б., Родин A.A., Соколова Ю.В. заявл. 27.12.2010, опубл. 10.07.201 бюл,№10.

Другие публикации

6. Минайлов В.В.Устройство выявления параллелизма внутри линейных учас ков программ со связями по управлению [Текст] / В.В. Минайлов, Д.Б. Борзо С.А. Дюбрюкс // Компьютерные технологии в науке, производстве, социал ных и экономических процессах: материалы VIII МНТК. Новочеркасс ЮРГТУ (НПИ), 2007,- С.114-117.

7. Минайлов В.В. Организация акселератора вычисления минимального знач ния коммуникационной задержки в полносвязных матричных мультиконтро. лерах [Текст] / В.В. Минайлов, Д.Б. Борзов, A.A. Родин, Ю.В. Соколова // М териалы и упрочняющие технологии-2010: сборник материалов XVII РоссиГ ской научно-технической конференции с международным участием, Курс КГТУ, 2010. Часть 2. С. 195-199.

8. Минайлов В.В. Методика минимизации длины межмодульных связей в ПЛИ [Текст] / В.В. Минайлов, Д.Б. Борзов, A.A. Родин, // Машиностроение и те: носфера XXI века: сборник трудов XVIII МНТК. Курск: ДонНТУ, 2011. 1 С.86-89.

9. Минайлов В.В. Подход к решению задачи планирования топологии ПЛИС [Текст] / В.В. Минайлов, Д.Б. Борзов // Интеллектуальные и информационные системы: МНТК. Курск: ТГУ, 2011. С. 24-25.

Ю.Минайлов В.В. Алгоритм планирования топологии ПЛИС [Текст] / В.В. Минайлов, Д.Б. Борзов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: сборник материалов X МК: Курск: ЮЗГУ, 2010. С. 236-238.

11.Минайлов В.В. Моделирование перестановок при размещении подпрограмм в ПЛИС [Текст] / В.В. Минайлов, Д.Б. Борзов, A.A. Родин // Свидетельство о регистрации программы для ЭВМ №2012619272. заявл. 10.05.2012, опубл. 15.10.2012.

12.Минайлов В.В. Моделирование планирования топологии ПЛИС [Текст] / В.В. Минайлов, Д.Б. Борзов, A.A. Родин // Свидетельство о регистрации программы для ЭВМ №2012619271. заявл. 10.05.2012, опубл. 15.10.2012.

Подписано в печать 23.11.2012. Формат 60x84 1/16. Печ. л. И). Тираж 100 экз. Заказ 78 Юго-западный государственный университет.

Издательско-полиграфический центр Юго-западный государственный университет 305040, г. Курск, ул. 50 лет Октября, 94

ВВЕДЕНИЕ.

1 АНАЛИЗ ИЗВЕСТНЫХ МЕТОДОВ И АЛГОРИТМОВ ПЛАНИРОВАНИЯ ТОПОЛОГИИ ПЛИС.

1.1 Архитектура ПЛИС, общие особенности.

1.2 Общая постановка задачи размещения на ПЛИС и СБИС.

1.3 Классификация методов и алгоритмов планирования топологии ПЛИС.

1.4 Обзор методов и алгоритмов размещения подпрограмм.

1.5 Анализ аппаратных методов планирования размещения ПЛИС и целесообразность их аппаратной реализации.

1.6 Выводы.

2 МЕТОД ПЛАНИРОВАНИЯ ТОПОЛОГИИ ПЛИС.

2.1 Математическая постановка задачи планирования топологии ПЛИС.

2.2 Метод минимизации длины межсоединений проводников модулей ПЛИС

2.2.1 Постановка задачи минимизации длины межсоединений.

2.2.2 Поиск нижней оценки суммарной длины межсоединений модулей ПЛИС.

2.3 Алгоритм планирования размещения подпрограмм в ПЛИС.

2.3.1 Этапы поискарешения.

2.3.2 Операция перестановки строк матрицы цепей.

2.4 Перестановочный алгоритм планирования размещения подпрограмм в ПЛИС.

2.4.1 Обобщенный алгоритм.

2.4.2 Формализованный алгоритм размещения подпрограмм в ПЛИС.

2.5 Выводы.

3 МОДЕЛИРОВАНИЕ ПРОЦЕДУРЫ ПЛАНИРОВАНИЯ РАЗМЕЩЕНИЯ ПЛИС.

3.1 Методы моделирования.

3.2 Результаты исследования на модели эффективности алгоритма планирования топологии ПЛИС.

3.3 Выводы.

4 ОРГАНИЗАЦИЯ МИКРОПРОЦЕССОРНОГО АКСЕЛЕРАТОРА ПЛАНИРОВАНИЯ ТОПОЛОГИИ ПЛИС.

4.1 Принципы аппаратной реализации процедур планирования топологии ПЛИС.

4.2 Структурная организация микропроцессорного акселератора планирования топологии ПЛИС.

4.3 Алгоритмы функционирования акселератора.

4.4 Функциональная организация акселератора планирования топологии ПЛИС.

4.4.1 Функциональная организация блока поиска нижней оценки.

4.4.2 Функциональная организация блока поиска начального значения.

4.4.3 Функциональная организация блока поисковых перестановок.

4.4.4 Анализ производительности и быстродействия акселератора.

4.5 Выводы.

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

СЛУ (мультиконтроллеров), а также отказоустойчивость систем высокой готовности (системы бортовой авиации, слежения, прогнозирования и т.п.).

Теория параллельной организации и отказоустойчивой работы мультиконтроллеров достаточно широко разработана. Большой вклад в эту область внесли работы отечественных ученых: Вл. В. Воеводина, В.В. Воеводина, A.B. Каляева, И.А. Каляева, И.И. Левина, А.П. Типикина, а также зарубежных ученых: М. Флинна, К. Ванга, Д. Скилликорна, Э.А. Трахтенгерца. В данных работах вопросы построения отказоустойчивых реконфигурируе-мых СЛУ высокой готовности рассматривались частично. Однако, в случае возникновения функционального отказа при использовании устройств на ПЛИС, необходима оперативная ее реконфигурация.

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

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

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

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

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

Объект исследования: системы логического управления высокой готовности.

Предмет исследования: Метод, алгоритмы и аппаратные средства планирования топологии программируемых логических интегральных схем.

Работа выполнена по плану инициативных НИР 2009-2013 г.г. кафедры вычислительной техники Юго-Западного государственного университе та.

Задачи исследований:

1. Анализ состояния вопроса и обоснование необходимости создания устройств планирования топологии ПЛИС в реконфигурируемых многозадачных СЛУ высокой готовности в динамическом режиме.

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

3. Разработка методики и алгоритма планирования размещения подпрограмм в ПЛИС, позволяющих сократить время поиска варианта размещения.

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

Научная новизна и положения, выносимые на защиту:

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

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

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

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

Практическая ценность результатов исследований:

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

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

3. Программное моделирование разработанного алгоритма ускоренного планирования топологии ПЛИС позволяет уменьшить коммуникационную задержку в 1,4-2,95 раза.

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

4.5 Выводы

1. Разработаны алгоритмы, структурные и функциональные схемы микропроцессорного акселератора планирования топологии ПЛИС.

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

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

4. При аппаратной реализации предложенного устройства малой и средней степени интеграции, например, для плана топологии ПЛИС размером 25x25 требуется 300 мкс, а при программной - 839 мкс.

Заключение

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

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

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

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

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

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

1. Стешенко В.Б., Шишкин Г.В., Евстифеев A.B., Седякин Ю.М. Школа разработки аппаратуры цифровой обработки сигналов на ПЛИС. Занятие 4. Язык описания аппаратуры VHDL.// Chip News. 2000.- №1.-С 17-22.

2. Стешенко В. Школа разработки аппаратуры цифровой обработки сигналов на ПЛИС. Занятие 3. Программное обеспечение проектирования на ПЛИС фирмы Xilinx.// Chip News. 1999,- №10,- С 34-42.

3. Губанов Д.А., Стешенко В.Б., Храпов В.Ю., Шипулин С.Н. Перспективы реализации алгоритмов цифровой фильтрации на основе ПЛИС фирмы ALTERA. // Chip News. 1997.-№ 9-10.-C. 26-33.

4. Стешенко В. Б. Школа схемотехнического проектирования устройств обработки сигналов. // Компоненты и технологии. 2000.-№ 3-6.-С. 11-23.

5. Грушвицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах программируемой логики.-СПб.: БХВ-Петербург,2002,-608 с.

6. Бродин В.Б., Калинин A.B. Системы на микроконтроллерах и БИС программируемой логики.-М.: Издательство ЭКОМ, 2002,- 400 с.

7. Угрюмов Е.П. Цифровая схемотехника.- СПб.: БХВ-Пегербург,2001 .-528 с.

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

9. Стешенко В.Б. ПЛИС фирмы "ALTERA": элементная база, система проектирования и языки описания аппаратуры,- М.: Издательский дом, ДО-ДЕКА XXI,- 2002,- 576 с.

10. Муренко JI.JI. и др. Программаторы запоминающих и логических интегральных микросхем/ Л.Л. Муренко, В.Н. Чурков, Ю.Ф. Широков М.: Энергоатомиздат, 1988.- 128 с.

11. Стешенко В.Б. ПЛИС фирмы "ALTERA": элементная база, система проектирования и языки описания аппаратуры.- М.: Издательский дом, ДО-ДЕКА XXI. - 2002. - 576 с.

12. Антонов А.1Т. Язык описания цифровых устройств. ALTERA HDL. Практический курс.- М.: ИП Радио Софт, 2002.- 224 с.

13. Стешенко В.Б. ПЛИС фирмы "ALTERA": элементая база, система проектирования и языки описания аппаратуры.- М.: Издательский дом, ДО ДЕКА XXI2002.- 576 с.

14. Anderson G.A., Jensen L.D. Computer interconnection structures, taxonomy, characteristics and examples // Computing Surveys of AC. 1975. - Vol. 7, №4.-PP. 197-213.

15. Feng T-Y. A survey of interconnection network // IEEE Computer. 1981. -Vol. 14, №12.-PP. 12-27.

16. Wittie L.D. Communication structures for large networks of microcomputers // IEEE Transactions on Computers. 1981. - Vol. C-30, №4. - PP. 264-273.

17. K. Windisc, V.M. Lo, B. Bose. Contiguous and noncontiguous processor allocation algorithms for k-ary n-cubes // Proc. Int'l Conf. Parallel processing. -1995. Vol. 4, №12. - PP.22-27.

18. Ma P.R., Lee E.Y.S., Tsuchiya M. A task allocation model for distributed computing systems // IEEE Transactions on Computers. 1982. - Vol. C-31, №1. - PP. 41-47.

19. Chu W.W., Holloway L.J., Lan M.-T., Efe K. Task allocation in distributed data processing // IEEE Computer. — 1980. — №11. — PP. 57-69.

20. Lee Ch.-H., Lee D., Kim M. Optimal task assignment in linear array networks// IEEE Transactions on Computers.— 1992. — Vol. 41, №7. — PP. 877-880.

21. G.S. Rao, H.S. Stone, T.C. Hu. Assignment of tasks in a distributed processor system with limited memory // IEEE Trans. Comput. C-28 (4). - 1979. -PP. 291 -299.

22. Jo B.-L. et al. Task assignment in homogeneous linear array networks // IEICE Trans. 1991. - Vol. 74. №9. pp. 2642-2648.

23. H.S. Stone, S.H. Bokhair. Control of distributed processes // Computer. -1978,-№6.-PP. 97-106.

24. L.M. Ni, K. Hwang. Optimal load balancing strategies for a multiply processor system // Proc. Inernat. Conf. Parallel. Proc. 1981. - PP. 352 - 357.

25. Despain A.M., Patterson D.A. X-tree: a tree structured multiprocessor computer architecture / Proceedings of 5th Symp. on Computer Architecture, Palo Alto, Calif. 1978. - PP. 144-151.

26. Gottlieb A., Schawarts J.T. Networks and algorithms for very-large-scale parallel computation // Computer. 1982. - Vol. 15, №1. - PP. 27-36.

27. H.S. Stone. Multiprocessor scheduling with the aid of network flow algorithms // IEEE Trans. Software Eng. 1977. - Vol. SE-3. - PP. 85-93.

28. Wu S.S., Sweeting D. Heuristic algorithms for task assignment and scheduling in a processor network // Parallel Computing. 1994. — №20. — PP. 1-14.

29. Bokhari Sh. H. On the mapping problem // IEEE Transactions on Computers. 1981,—Vol. C-30, №3,— PP. 207-214.

30. Sadayappan P., Ercal F. Nearest-neighbor mapping of finite element graphs onto processor meshes // IEEE Transactions on Computers. — 1987. — Vol. C-36, №12. — PP. 1408-1424.

31. V.M. Lo. Heuristic algorithms for task assignment in distributed systems // IEEE Transactions on Computers 1988. - Vol. C-37 (11). -PP. 1384-1397.

32. K. Efe. Heuristic models for task assignment scheduling in distributed systems //IEEE Comput. 1982. - 15(6). - PP. 50-56.

33. B. W. Kerninghan, S. Lin. An efficient heuristic procedure for partitioning graph // Bell Syst. Tech J. 1970. - №2, PP. 291-307.

34. Virginia Lo, Wanqian Liu. Noncontiguous processor allocation algorithms for mesh-connected multicomputers // IEEE Transactions on parallel and dist. Systems. 1997. - Vol. 8, №7. - PP. 712-725.

35. Shen Ch.-Ch., Tsai W.-H. A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion // IEEE Transactions on Computers. — 1985. — Vol. C-34, №3. — PP. 197-203.

36. P. Chuang, N. Tseng. An efficient submesh allocation strategy for mesh computer systems // Proc. 1991 Int'l Conf. Distributed Computer Systems. 1991. -PP. 256-263.

37. Y. Zhu. Efficient processor allocation strategies for mesh-connected parallel computers // Parallel and distributed computers. 1992. - Vol. 16. - PP. 328337.

38. D.P. LaPotin and S.W.Director, " Mason; A global floorplaning tool," in Proc .IEEE Int.Conf.on Computer Aided Design, Santa Clara, CA, 1985, p.p. 143145.

39. C.Sechen and A.Sangiovanni Vincentelli, " The Timberwolf placement and routing package," IEEE J. Solid.State Circuits, Vol. SC-20, 1985,p.p.510-522.

40. D.F.Wong, H.W.Leong, and C.E.Lin . Simulated Annealing for VLSI Design. Boston, MA : Kluwer Academic, 1988, p.p. 248-265.

41. J.P.Cohoon, S.U.Hegde, W.N.Martin, D.Richards, " Distributed genetic algorithms for the floorplan design problem ", in Proc. IEEE Transactions on Computer Aided Design, Vol.10.No 4, April 1991, p.p.483-492.

42. Саломатин В.А., Струнилин B.H. Итерационный алгоритм распределения конструктивных элементов при задании электрической схемы в виде гиперграфа. М.: Высш. шк., 1998. -412 с.

43. H.Murata, K.Fujioshi, S.Nakatake. and Y.Kajitani, "VLSI module placement based on restanglepacking by the sequence pair". IEEE Trans. Computer -Aided Design, vol. 15, Dec.1996, p.p.1518-1524.

44. Селютин B.A. Автоматизация проектирования топологии БИС. — М.: Радио и связь. 2006 112 с.

45. Савельев А.Я., Овчинников В.В. Конструирование ЭВМ и систем. — М.:Высш. шк. —312 с.

46. Саломатин В.А., Струнилин В.Н. Последовательный алгоритм компоновки конструктивных элементов на основе задания схемы в виде гиперграфа / Науков1 пращ ДонНТУ, сер1я 'Чнформатика, юбернетика та об-числювальна техшка", выпуск 10(153) С. 198-201.

47. ВОЙТЮК. В.В. Алгоритм одновременного размещения и трассировки 49. для рядных плис / Сп-Б гос. электр.-тех у-т., 2004.-234 с.

48. S. Brown, R. Francis, J. Rose and Z. Vranesic, "Field-Programmable Gate Arrays", Kluwer Academic Publishers, vol. 5, 1992, p.p. 518-524

49. Д.Б. Борзов, B.B. Минайлов. Устройство для подсчета минимального значения интенсивности размещения в системах с древовидной организацией / Патент РФ № 2379749, БИ №2, 20010.

50. Д.Б. Борзов, В.В. Минайлов, А.А. Родин, Ю.В. Соколова. Устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации. Заявка на изобретение №2012148209 от 14.11.12.

51. Оре О. Теория графов. —М.: Наука, 1968. — 352 с.

52. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоато-миздат, 1987.-496 с.

53. Зотов И.В.и др. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления. Тула.: Тул. гос. ун-т, 1997. - 226 с.

54. Минайлов В.В. Методика минимизации длины межмодульных связей в ПЛИС Текст. /В.В. Минайлов, Д.Б. Борзов, А.А. Родин, // Машиностроение и техносфера XXI века: сборник трудов XVIII МНТК. Курск: ДонНТУ, 2011. Т2 С.86-89.

55. Минайлов В.В. Методика планирования топологии программируемых логических интегральных схем в многопроцессорных системах Текст. /

56. B.B. Минайлов, Д.Б. Борзов, B.B. Руденко, С.П. Гнездилова // Вестник КГСХА. 2012. №2, С. 126-129.

57. Медведев А. Печатные платы. Конструкции и материалы. М.: Техносфера, 2005. -671с.

58. Арсентьев С., Медведев А. Анатомия сквозного металлизированного отверстия. Технологии в электронной промышленности, 2008, №5, С.84-87.

59. Медведев А. Электронные компоненты и монтажные подложки. Постоянная интеграция. Компоненты и технологии, 2006.- №12.-С 45-51.

60. Шерстнев В.В. Конструирование и микроминиатюризация ЭВС: Учебник для вузов.- М.: Радио и связь, 1989. 272 с.

61. Преснухин Л.Н., Шахнов В.А. Конструирование электронных вычислительных машин и систем: Учебник для втузов по спец. "ЭВМ" и "Конструирование и производство ЭВС". М.: Высш. шк., 1988. -512 с.

62. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем: Учебник для технических вузов по специальности "ЭВМ". М.: Высш. шк. 1992.-248 с.

63. Пикуль М. И., Русак И.М., Цырельчук H.A. Конструирование и технология производства ЭВМ: Учебник для вузов. Мн.: Выш. шк., 1996.-263с.

64. Куземин А.Я. Конструирование и микроминиатюризация электронно-вычислительной аппаратуры: Учеб. пособие для вузов.- М.: Радио и связь, 1985. -280 с.

65. Минайлов B.B. Моделирование перестановок при размещении подпрограмм в ПЛИС Текст. / В.В. Минайлов, Д.Б. Борзов, A.A. Родин // Свидетельство о регистрации программы для ЭВМ №2012619272. заявл. 10.05.2012, опубл. 15.10.2012.

66. Минайлов В.В. Моделирование планирования топологии ПЛИС Текст. / В.В. Минайлов, Д.Б. Борзов, A.A. Родин // Свидетельство о регистрации программы для ЭВМ №2012619271. заявл. 10.05.2012, опубл. 15.10.2012.

67. Баас Р., Фервай М., Гюнтер X. Delphi 4: полное руководство. К.: Издательская группа BHV, 1998. - 800 с.

68. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. М.: «Радио и связь», 1983. - 280 с.

69. Курейчик В.М., Глушань В.М. Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: «Радио и связь», 1990. - 216 с.

70. Новиков Ю.В., Калашников O.A., Гуляев С.Э. Разработка устройств сопряжения. М.: «ЭКОМ», 1997. - 224 с.

71. Гук М. Аппаратные интерфейсы ПК. СПб.: Питер, 2003 - 528 с.

72. Танэнбаум Э. Архитектура компьютера. 4-е издание. СПб.: Питер, 2003.-704 с.

73. Пестерев К. Л., Захаров И.С. Периферийные устройства: Учеб. Пособие / Курск, гос. тех. ун-т: Курск, 1999 205 с.

74. Шило В.Л. Популярные цифровые микросхемы: Справочник. Металлургия, Челябинск, 1988. -352 с.

75. Микросхемы и их применение / Батушев В.А., Вениаминов В.Н., Ковалев В.-М.: Энергия, 1978.-248 с.

76. Интегральные микросхемы: Справочник / Тарабрин Б.В., Лунин Л.Ф., Смирнов Ю.Н. М.: Радио и связь, 1984. -528 с.

77. Петровский И.И. и др. Логические ИС КР1533, КР1554: Справочник в 2-х ч. -М.: ТОО «Бином», 1993.-473 с.

78. Кобзарь, А. И. Прикладная математическая статистика Текст. — М.: Физматлит, 2006. -816 с.

79. Макарова Н.В. Статистика в Excel. М.: Финансы и статистика, 2009. -368 с.

80. Закс Л. Статистическое оценивание. М.: Статистика, 2008.- 598 с.

81. Кулаичев А.П. Методы и средства анализа данных в среде Windows. STADIA 6.0. М.: Информатика и компьютеры, 2006. -270 с.

82. Лобанов В.И. Азбука разработчика цифровых устройств. М.: Горячая линия - Телеком, 2001. - 192с.

83. Стешенко. В. Школа разработки аппаратуры цифровой обработки сигналов на ПЛИС // Chip News, 1999,- № 8-10,- С. 3-5.

84. Пухальский Г. И., Новосельцева Т. Я. Цифровые устройства: учебное пособие для втузов. СПб.: Политехника, 2006. -885 с.