Методы и средства планирования размещения параллельных подпрограмм в матричных мультипроцессорах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Бобынцев, Денис Олегович

• Бобынцев, Денис Олегович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Бобынцев, Денис Олегович

Оглавление

Введение

Глава 1. Анализ методов и средств планирования размещения подпрограмм в матричных вычислительных системах

1.1. Направления развития многопроцессорных вычислительных систем

1.2. Принципы построения систем реального времени

1.3. Топологии и принципы построения многопроцессорных систем

1.4. Классификация методов размещения подпрограмм в матричных системах

1.5. Алгоритмы планирования размещения подпрограмм и их аппаратная реализация

1.6. Выводы по главе

Глава 2. Методы и алгоритмы планирования размещения подпрограмм в матричных мультипроцессорах

2.1. Типовая структура матричных мультипроцессоров

2.2. Математическое описание задачи размещения подпрограмм

2.3. Метод планирования размещения подпрограмм

2.4. Алгоритмы планирования размещения подпрограмм

2.5. Выводы по главе

Глава 3. Имитационное моделирование планирования размещения подпрограмм

3.1. Имитационная модель планирования размещения подпрограмм

3.2. Исследования показателей эффективности методов планирования размещения

3.2.1. Оценка степени уменьшения коммуникационной задержки и степени её близости к нижней оценке

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

3.3.3. Оценка времени программной реализации алгоритмов планирования размещения

3.3. Выводы по главе

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

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

4.2. Организация блока определения промежуточных значений коммуникационной задержки

4.3. Оценка времени определения коммуникационной задержки и аппаратной сложности 2 и 3 ступени акселератора

4.4. Выводы по главе

Заключение

Библиографический список

Приложение А

Приложение В

Приложение С

Приложение D

Введение диссертации (часть автореферата) на тему «Методы и средства планирования размещения параллельных подпрограмм в матричных мультипроцессорах»

Введение

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

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

Теория параллельной организации и планирования размещения

подпрограмм в многопроцессорных системах достаточно широко

разработана. Большой вклад в эту область внесли работы отечественных и

зарубежных ученых: В.П. Гергеля, A.B. Каляева, И.А. Каляева, И.И. Левина,

И.В. Зотова, Вл.В. Воеводина, В.В. Воеводина, В.М. Курейчика, Д.

Гроссмана, Р. Хокни, М. Бергера и др. В данных работах вопросы

минимизации величин коммуникационных задержек рассматривались, но без

4

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

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

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

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

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

Научно-техническая задача декомпозируется на следующие подзадачи:

1. Анализ состояния вопроса планирования размещения параллельных подпрограмм в матричных многопроцессорных системах. Обоснование основных направлений исследований.

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

3. Создание аппаратно-ориентированного алгоритма определения коммуникационной задержки с учётом пересечений каналов передачи данных.

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

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

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

Предмет исследования: алгоритмы и устройства планирования размещения параллельных подпрограмм по процессорам матричных мультипроцессоров.

Работа выполнена при поддержке гранта Президента РФ МД-2218.2011.8 и в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг, проект 14.В37.21.0598.

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

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

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

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

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

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

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

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

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

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

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

Практическое использование результатов работы. Результаты,

полученные в диссертационной работе, внедрены в Курском ОАО «Прибор»

ОХП ОКБ «Авиаавтоматика», а также используются в учебном процессе на

кафедре вычислительной техники ЮЗГУ при проведении занятий по

дисциплинам «ЭВМ и периферийные устройства», «Теоретические основы

8

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

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

Апробация работы. Основные положения и результаты диссертации обсуждались и получили положительную оценку на региональных российских и международных конференциях: «Системы, методы, техника и технологии обработки медиаконтента» (Москва, 2011), "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (Курск, 2010, 2012), «Материалы и упрочняющие технологии-2010» (Курск), «Практика и перспективы развития партнёрства в сфере высшей школы» (Донецк, 2011), «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (Новочеркасск, 2008), «Информационно-измерительные, диагностические и управляющие системы» (Курск, 2009, 2011), «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2010), «Информационные системы и технологии» (Курск, 2012), а также на

научно-технических семинарах кафедры «Вычислительная техника» Юго-Западного государственного университета (КурскГТУ) с 2009 по 2013 гг.

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

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В работах по теме диссертации, опубликованных в соавторстве, лично соискателем предложено: в [69 -71,73,76] метод определения коммуникационной задержки при планировании размещения подпрограмм и методика оценки степени близости к нижней оценке, в [82 - 84] принцип построения акселератора, в [58,59] устройство вычисления нижней оценки размещения, в [79] программная модель процедур планирования размещения, в [62 - 65] методика исследования эффективности поиска варианта размещения, в [81] оценка производительности матричного мультипроцессора.

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

Глава 1. Анализ методов и средств планирования размещения подпрограмм в матричных вычислительных системах 1.1. Направления развития многопроцессорных вычислительных систем

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

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

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

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

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

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

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

В то же время в работе [9] отмечается, что широкое применение

реконфигурируемых вычислительных систем сдерживается сложностью их

программирования, требующего больших временных затрат, достигающих

12

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

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

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

1.2. Принципы построения систем реального времени

Системой реального времени называется система с ограничениями на временные характеристики работы, то есть правильность её функционирования зависит не только от логической корректности вычислений, но и от времени, за которое они производятся [2]. Таким образом, быстродействие системы должно быть адекватно скорости протекания физических процессов на объектах контроля или управления. В теории СРВ используются понятия жёсткого и мягкого реального времени. Системой жесткого реального времени или критической системой называется система, в которой неспособность реагировать на какие-либо события в заданное время считается отказом и ведет к невозможности решения поставленной задачи. Большинство систем жесткого реального времени являются системами контроля и управления. Примерами встраиваемых систем жёсткого реального времени являются бортовые системы, системы контроля и управления промышленными объектами.

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

Одной из проблем построения критических СРВ является задача

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

14

составляющих: надёжность, готовность и удобство обслуживания [10], предполагающих главным образом обеспечение отказоустойчивости данных систем.

В основе повышения надёжности лежит принцип предотвращения неисправностей путём снижения интенсивности отказов и сбоев. Единицей измерения надёжности является среднее время наработки на отказ (MTBF -Mean Time Between Failure).

Повышение готовности состоит в подавлении в определенных пределах влияния отказов и сбоев на работу системы с помощью средств контроля, коррекции ошибок и автоматического восстановления вычислительного процесса после отказов, включая аппаратную и программную избыточность. На основе избыточности реализуются различные варианты отказоустойчивых архитектур. Характеристикой такой системы является коэффициент готовности, определяющий вероятность пребывания системы в работоспособном состоянии в любой произвольный момент времени: MTBF/(MTBF+MTTR), где MTTR (Mean Time То Repair) - среднее время между моментом обнаружения неисправности и моментом рестарта системы.

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

В критических системах реального времени, к которым предъявляется требование высокой готовности, выделяют такие термины, как эластичность к отказам, устойчивость к отказам и непрерывная готовность. Ключевым моментом в определении эластичности к отказам является более короткое время восстановления, которое позволяет выполнить быстрый «откат» назад после обнаружения неисправности.

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

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

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

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

1.3. Топологии и принципы построения многопроцессорных систем

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

Многопоточные системы используются для обеспечения единого интерфейса для ряда ресурсов, которые могут со временем произвольно наращиваться (или сокращаться). Примером таких систем является группа \уеЬ-серверов.

Существенное влияние на реальную производительность вычислительной системы оказывает топология связей между процессорами. Критическим параметром, влияющим на реальную производительность, является «расстояние» между процессорами, которое выражается в количестве межпроцессорных каналов связи. Под межпроцессорным каналом связи понимается совокупность технических средств, обеспечивающих взаимодействие двух соседних процессоров: передачу данных и служебной информации. Канал обмена данными между не соседними процессорами состоит из 2 и более последовательно соединённых межпроцессорных каналов связи. Теория показывает, что система не может работать эффективно, если максимальное расстояние между процессорами больше 4 межпроцессорных каналов [11]. Одним из способов уменьшения

максимального расстояния является использование топологии гиперкуба (рис. 1.1.) вместо плоской решётки, а также трёхмерного тора, «звезды», кольца (рис. 1.2) и др.

Рис. 1.1. Топология «гиперкуб»

Рис. 1.2. Топология «кольцо» Наиболее эффективной с точки зрения расстояний между процессорами является топология "толстого дерева" (fat-tree) (рис. 1.3). Топология "fat-tree" (hypertree) была предложена Лейзерсоном (Charles Е. Leiserson) в 1985 году для кластерных мультикомпьютеров [12]. Процессоры локализованы в листьях дерева, в то время как внутренние узлы дерева скомпонованы во внутреннюю сеть. Поддеревья могут общаться между собой, не затрагивая более высоких уровней сети. Данная топология характерна для кластерных межсоединений на основе технологии Infmiband.

Список литературы диссертационного исследования кандидат наук Бобынцев, Денис Олегович, 2014 год

Библиографический список

1. Каляев, И.А. Реконфигурируемые мультиконвейерные вычислительные структуры: монография / И.А. Каляев, И.И. Левин, Е.А. Семерников,

B.И. Шмойлов. - Ростов-на-Дону: ЮРЦ РАН, 2008. - 393 с.

2. Сорокин, С. Системы реального времени / С. Сорокин // Современные технологии автоматизации. М.: СТА-Пресс, 1997. - №2. - С. 22 - 29.

3. Левин, И.И. Реконфигурируемые вычислительные системы с открытой архитектурой / И.И. Левин // Доклады 5-й межд. конф. «Параллельные вычисления и задачи управления». - М.: ИПУ РАН, 2010. - С. 84 - 96.

4. Дордопуло, А.И. Высокопроизводительные реконфигурируемые вычислительные системы нового поколения / А.И. Дордопуло, И.А. Каляев, И.И. Левин, Е.А. Семерников // Вычислительные методы и программирование: новые вычислительные технологии. М.: НИВЦ МГУ им. М.В. Ломоносова, 2011. - Т. 12. - №2. - С. 82-29.

5. Каляев, И.А. Реконфигурируемые вычислительные системы на основе ПЛИС семейства Virtex-6 / И.А. Каляев, И.И. Левин, Е.А., Семерников,

A.И. Дордопуло // Вестник Уфимского гос. авиац. техн. университета. УФА: УГАТУ, 2011. - Т. 15. - №5(45). - С. 148 - 154.

6. Каляев, И.А. Семейство вычислительных систем с высокой реальной производительностью на основе ПЛИС / И.А. Каляев, И.И. Левин, Е.А. Семерников // Вестник Уфимского гос. авиац. техн. университета. УФА: УГАТУ, 2010. - Т.14. - №5(40). - С. 91 - 101.

7. Каляев, И.А. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач / И.А. Каляев, И.И. Левин // Информационные технологии и вычислительные системы для решения потоковых задач. - М.: Институт системного анализа РАН, 2011. - №2. -

C.12 - 22.

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

9. Коваленко, А.Г. Препроцессор языка программирования высокого уровня для реконфигурируемых вычислительных систем: автореф. дис. на соиск. учёной степ. канд. техн. наук: 05.13.11 / А.Г. Коваленко. Таганрог, 2013. - 19 с.

10. Системы высокой готовности и отказоустойчивые системы [Электронный ресурс] // Онлайн-библиотека CITForum.ru. - Режим доступа: http://citforum.ru/hardware/svk/ glaval2.shtml.

П.Богданов, A.B. Архитектуры и топологии многопроцессорных вычислительных систем: учебное пособие / A.B. Богданов, В.В. Корхов,

B.В. Мареев, E.H. Станкова. - М.: Интернет-университет информационных технологий, 2004. - 171 с.

12. Leiserson, Ch.E. Fat-Trees: Universal Network for Hardware-Efficient Supercomputing / Ch.E. Leiserson // IEEE Transactions on Computers. -1985.-Vol. C.34, №10. - PP. 892-901.

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

14. Вранчич, А. Высокопроизводительные вычисления на многоядерных процессорах в реальном времени / А. Вранчич, Д. Мейзел // Электронные компоненты. - М.: 2009. - №9. - С. 67 - 69.

15.Калачёв, А. Процессоры GreenArrays - GA144 / А. Калачёв // Компоненты и технологии. - СПб.: 2011.-№11.-С. 111-118.

16. Калачёв, А. Высокопроизводительные многоядерные процессоры для встраиваемых систем / А. Калачёв // Компоненты и технологии. — 2010. — №2. - С.92-102.

17. Абдель-Джалил, Дж.Н. Алгоритмы межпроцессорного взаимодействия в отказоустойчивых многопроцессорных системах / Дж.Н. Абдель-Джалил, Э.И. Ватутин, И.В. Зотов [и др.] // Методы и системы обработки информации. - Муром, 2004. - С. 117-125.

18. Абдель-Джалил, Дж.Н. Организация отказоустойчивого межпроцессорного взаимодействия в матричных мультикомпьютерах / Дж.Н. Абдель-Джалил, А. Аль-Хади, И.В. Зотов [и др.] // Известия ТулГУ. Бизнес-процессы и бизнес-системы. - 2006. - Вып. 4. - С. 3 - 9.

19. Анпилогов, Е.Г. Модель квазиадаптивной маршрутизации сообщений и ее оценка / Е.Г. Анпилогов, И.В. Зотов, B.C. Титов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы 5-й Междунар. науч.-техн. конф. - Курск: Курск, гос. техн. ун-т, 2001. - 4.2. -С. 235-237.

20. Abdel-Jalil, J.N. A fault-tolerant message routing procedure with rotating coordinates / J.N. Abdel-Jalil, M.H. Najajra, E.I. Vatutin [et al.] // Proc. 3 Int. Conf. Information and Telecommunication Technologies in Intelligent Systems (Spain, Mallorca, June 02-09 2005). - Mallorca, 2005. - P. 88-92.

21. Al-Sadi, J. Probability-based fault-tolerant routing in hypercubes / J. Al-Sadi, K. Day, M. Ould-Khaoua // The Computer Journal. - 2001. - Vol.44, N5. - P. 368-373.

22. Chalasani, S. Communication in multicomputers with nonconvex faults / S. Chalasani, R.V. Boppana // IEEE Transactions on Computers. - 1997. -Vol.46, N5.-P. 616-622.

23. Chen, C.-L. A fault-tolerant routing scheme for meshes with nonconvex faults / Chun-Lung Chen, Ge-Ming Chiu // IEEE Transactions on Parallel and Distributed Systems. - 2001. - Vol.12, N5. - P. 467-475.

24. Chen, Y.-S. Multinode broadcasting in a wormhole-routed 2-D torus using an aggregation-then-distribution strategy / Y.-S. Chen, C.-Y. Chen // IEE

Proceedings - Computers and Digital Techniques. - 2000. - Vol.147, N6. -P. 403-413.

25. Duato, J. A theory of fault-tolerant routing in wormhole networks / J. Duato // Proc. Intl Conf. Parallel and Distributed Systems, ICPDS 1994, 19-21 Dec. -1994.-P. 600-607.

26. Gao, F. Fault-tolerant routing algorithms based on optimal path matrices / Feng Gao, Zhongchen Li // Proc. Pacific Rim Intl Symp. Dependable Computing. - IEEE/IFIP: 1999. - P. 227-233.

27. Ho, C.-T. A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers / C.-T. Ho, L. Stockmeyer // IEEE Transactions on Computers. - 2004. Vol.53, N4. - P. 427-438.

28. Jiang, Z. A limited-global information model for dynamic fault-tolerant routing in cube-based multicomputers / Z. Jiang, J. Wu // Proc. 2nd IEEE Intl Symp. Network Computing and Applications, NCA 2003. - 2003. - P. 333340.

29. Theiss, I. FRoots: a fault tolerant and topology-flexible routing technique /1. Theiss, O. Lysne // IEEE Transactions on Parallel and Distributed Systems. -2006.-Vol.17, N10.-P. 1136-1150.

30. Wang, G. A new fault-tolerant routing scheme for 2-dimensional mesh networks / G. Wang, J. Chen // Proc. 4th Intl Conf. Parallel and Distributed Computing, Applications and Technologies, PDCAT'2003. - 2003. - P. 9598.

31. Wang, G. A probabilistic approach to fault-tolerant routing algorithm on mesh networks / G. Wang, T. Li, J. Chen // Proc. 10th Intl Conf. Parallel and Distributed Systems, ICPADS 2004. - 2004. - P. 577-584.

32. Wu, J. On constructing the minimum orthogonal convex polygon for the fault-tolerant routing in 2-D faulty meshes / J. Wu, Z. Jiang // IEEE Transactions on Reliability. - 2005. - Vol.54, N3. - P. 449-458.

33. Xiang, D. Fault-tolerant routing in meshes/tori using planarly constructed fault blocks / D. Xiang, J.-G. Sun, J. Wu [et al.] // Proc. Intl Conf. Parallel Processing, ICPP 2005. - 2005. - P. 577-584.

34. Zotov, I.V. Model of fault-tolerant message routing for matrix-type microcontroller networks / I.V. Zotov // Automatic Control and Computer Sciences. - 2002. - Vol.36, N2. - P. 15-26.

35. Типикин, А.П. Проблема создания быстродействующего устройства планирования размещения параллельных процедур логического управления в мультиконтроллерах / А.П. Типикин, Д.Б. Борзов // Известия ЮЗГУ. - Курск, 2011. - №6. - 4.2. - С. 28 - 32.

36. Андерсон, Д. Дискретная математика и комбинаторика / Д. Андерсон. -М.: Вильяме, 2003. - 960 с.

37. Dorigo, М. The Ant Colony Optimization Metaheuristic: Algorithms, Applications and Advances / M. Dorigo, T. Stiitzle // Handbook of Metaheuristics. - 2003. - P. 251-286.

38. Андреев, А.Е. Алгоритм глобального размещения структурированных заказных схем / А.Е. Андреев, И. Пависич, A.C. Русаков // Проблемы разработки перспективных микро- и наноэлектронных систем - 2012. Сборник трудов / под общ. ред. академика РАН A.JI. Стемпковского. -М.: ИППМ РАН, 2012. - С. 231-236.

39. Горшков, А.Ф. Метод замещений / А.Ф. Горшков. - М.: КноРус, 2004. -184 с.

40. Карманов, В.Г. Математическое программирование / В.Г. Карманов. - 5-е издание. - М.: Физматлит, 2004. - 264 с.

41. Аль-Мараят, Б.И. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности: дисс. на соиск. учёной степ. канд. техн. наук: 05.13.05 / Б.И. Аль-Мараят. Курск, 2008. - 147 с.

42. Engelbrecht, А.Р. Particle swarm optimization: an introduction and its recent developments / A.P. Engelbrecht, X. Li // Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation. - London: ACM, 2007.-pp. 3391 -3414.

43. Belal, M. Parallel Models for Particle Swarm Optimizers / M. Belal, T. El-Ghazawi // International Journal of Intelligent Computing and Information Sciences. - 2004, v. 1. - PP. 100-111.

44. Костенко, B.A. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС / В. А. Костенко // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения». - М.: Изд-во МГУ, 2000. - С. 123 - 127.

45. Абакаров, А.Ш. Статистическое исследование одного алгоритма глобальной оптимизации [Электронный ресурс] / А.Ш. Абакаров, Ю.А. Сушков // Труды ФОРА. - 2004. - Режим доступа: http: // fora. ad у gnet.ru/ 72004.

46. Костенко, B.A. Генетические алгоритмы решения смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур ВС / В.А. Костенко, А.Г. Трекин // Искусственный интеллект. - Донецк, 2000. - №2. - С.90-96.

47. Емельянов, В.В. Теория и практика эволюционного моделирования / В.В. Емельянов, В.В. Курейчик, В.М. Курейчик. - М.: Физматлит, 2003. -432 с.

48. Гладков, JI.A. Генетические алгоритмы: учебное пособие / JI.A. Гладков, В.В. Курейчик, В.М. Курейчик. - 2-е изд. - М: Физматлит, 2006. - 320 с.

49. Борзов, Д.Б. Модели и методы размещения задач в параллельных системах и устройства для их реализации: дисс. на соиск. учёной степ, канд. техн. наук: 05.13.05 / Д.Б. Борзов. Курск, 2002. - 180 с.

50. Патент РФ .№2285289. Устройство планирования размещения задач в системах с кольцевой организацией при направленной передаче

информации / Д.Б. Борзов, Д.С. Горощенков. Заявл. 18.01.2005; опубл. 10.10.2006.

51. Патент РФ №2297027. Устройство подсчёта минимального значения интенсивности размещения в системах с кольцевой организацией / Д.Б. Борзов, Т.А. Заикина, О.С. Чернышёва, Е.Е. Ураева. Заявл. 3.10.2005, опубл. 10.04.2007.

52. Патент РФ №2296359. Устройство размещения задач в кольцевых системах/ Д.Б. Борзов. Заявл. 3.10.2005, опубл. 27.03.2007.

53. Патент РФ №2319204. Устройство для формирования размещения в системах с линейной организацией / С.А. Дюбрюкс, Д.Б. Борзов, B.C. Титов. Заявл. 01.08.2006, опубл. 10.03.2008.

54. Патент РФ №2345410. Устройство планирования размещения задач в системах с кольцевой организацией / Д.Б. Борзов, Д.С. Горощенков, Н.В. Ермолаева. Заявл. 14.12.2004, опубл. 27.01.2009.

55. Патент РФ №2279709. Устройство для оценки качества размещения в матричных системах / Д.Б. Борзов, A.A. Жолобов. Заявл. 28.03.2005, опубл. 10.07.2006.

56. Патент РФ №2421805. Устройство поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче информации / Д.Б. Борзов, Е.О. Чеснокова, A.JI. Марухленко, М.М.Я Аль-Ашвал. Заявл. 24.11.2008, опубл. 20.06.2011.

57. Патент РФ №2275681. Устройство поиска нижней оценки размещения в матричных системах / Д.Б. Борзов. Заявл. 06.10.2004, опубл. 27.04.2006.

58. Патент РФ №2406135. Устройство поиска нижней оценки размещения в системах с матричной организацией при направленной передаче информации / Д.О. Бобынцев, Д.Б. Борзов. Заявл. 9.02.2009, опубл. 10.12.2010.

59. Бобынцев, Д.О. Организация устройства поиска нижней оценки размещения задач в системах с матричной организацией / Д.О. Бобынцев, Д.Б. Борзов // Компьютерные технологии в науке, производстве, социальных и экономических процессах: материалы IX Международной научно-практической конференции. - Новочеркасск: ЮРГТУ, 2008. - С. 101-103.

60. Патент РФ № 2447485. Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации / Д.Б. Борзов, Ю.В. Соколова. Заявл. 11.09.2009, опубл. 10.04.2012.

61. Патент РФ №2470357. Устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации / В.В. Минайлов, Д.Б. Борзов, A.A. Родин, Ю.В. Соколова. Заявл. 27.12.2010, опубл. 20.12.2012.

62. Бобынцев, Д.О. Методика исследования влияния латентной составляющей коммуникационной задержки в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин //

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

- Курск: ЮЗГУ, 2011. - С. 103-104.

63.Бобынцев, Д.О. Влияние латентной составляющей коммуникационной задержки на размещение параллельных подпрограмм в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов, С.Г. Емельянов, B.C. Титов // Известия Юго-Западного государственного университета. -2012. -№3.- 4.1. -С.54-58.

64. Бобынцев, Д.О. Сравнительный анализ критериев минимизации коммуникационных задержек в мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов // Методы и алгоритмы прикладной математики в технике, медицине и экономике: материалы X Международной научно-практической конференции. - Новочеркасск: ЮРГТУ, 2010. - С. 26-29.

65. Бобынцев, Д.О. Анализ качества размещения параллельных подпрограмм в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин // Известия высших учебных заведений. Приборостроение. - 2013. - Т.56. - №6. - С.35-39.

66. Гергель, A.B. Оценка сложности коммуникационных операций в кластерных вычислительных системах / A.B., Гергель, Р.В. Виноградов // Материалы II Межд. научно-практ. Семинара «Высокопроизводительные вычисления на кластерных системах». -Нижегор. гос. тех. ун-т им. Н.И. Лобачевского, 2002. - С. 73-77.

67. Андреев, А.Н. Методика измерения основных характеристик программно-аппаратной среды [Электронный ресурс] / А.Н. Андреев, В.В. Воеводин. - Режим доступа: http://www.parallel.ru/testmpi/

68. Масолов, A.C. Метод снижения коммуникационной задержки путём субоптимального размещения задач в матричных базовых блоках кластера / A.C. Масолов, Д.Б. Борзов, Б.И. Аль-Мараят // Телекоммуникации. - Курск, 2008. - С. 21 - 25.

69. Бобынцев, Д.О. Использование избыточных кратчайших путей при переразмещении параллельных подпрограмм в матричных мультикомпьютерах / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин // Распознавание - 2010: сб. материалов IX Международной конференции.

- Курск: ЮЗГУ, 2010. - С. 158-160.

70. Бобынцев, Д.О. Минимаксиминный критерий оценки качества размещения параллельных подпрограмм в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов // Известия ЮЗГУ. Серия «Управление, вычислительная техника, информатика. Медицинское приборостроение». - Курск, 2012. - №2. - 4.1. - С.27 - 31.

71. Бобынцев, Д.О. Применение минимаксиминного критерия для управления качеством размещения задач в многопроцессорных системах / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин // Распознавание - 2010: сб.

материалов IX Международной конференции. - Курск: ЮЗГУ, 2010. - С. 152-154.

72. Бобынцев, Д.О. Использование многопроцессорных систем в технологии IPTV / Д.О. Бобынцев // Научно-техн. междун. молодёжная конф. «Системы, методы, техника и технологии обработки медиаконтента»: сборник тезисов. -М.: МГУПим. Ивана Фёдорова, 2011. - С. 14-15.

73. Бобынцев, Д.О. Применение параллельных вычислительных систем в биоинформатике / Д.О. Бобынцев, Д.Б. Борзов // Распознавание - 2012: сб. мат. X Междунар. научно-технической конференции. - Курск: ЮЗГУ, 2012. С. 133-134.

74. Харари, Ф. Теория графов: пер. с англ. / Ф. Харари. - 3-е изд., стер. - М.: Эдиториал УРСС, 2006 . - 296 с.

75. Зыков, А. А. Основы теории графов / A.A. Зыков. - М.: «Вузовская книга», 2004. - 664 с.

76. Бобынцев, Д.О. Методика определения кратчайших расстояний при размещении задач в многопроцессорных системах / Д.О. Бобынцев, А.П. Типикин // Диагностика - 2009: сб. материалов Международной научно-технической конференции. - Курск: КурскГТУ, 2009. - С.205-208.

77. Свидетельство о государственной регистрации программы для ЭВМ №2010614500. Программа построения базы данных избыточных кратчайших путей в графе / Д.О. Бобынцев. Заявл. 19.05.2010, зарег. 08.07.2010.

78. Свидетельство о государственной регистрации программы для ЭВМ №2010614501. Программа оценки качества размещения параллельных подпрограмм в матричном мультиконтроллере / Д.О. Бобынцев. Заявл. 19.05.2010, зарег. 08.07.2010.

79. Бобынцев, Д.О. Программная модель процедур планирования размещения задач в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов // Информационные системы и технологии: сб. докладов. -Курск: ЮЗГУ, 2012. - С. 63-64.

80. Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. - М.: Высшая школа, 2003. - 479 с.

81. Бобынцев, Д.О. Оценка производительности матричного мультипроцессора при выполнении параллельного алгоритма решения задачи гравитационного взаимодействия N тел / Д.О. Бобынцев, Э.И. Ватутин, B.C. Титов // Известия Юго-Западного государственного университета. Серия. Управление, вычислительная техника, информатика. Медицинское приборостроение. - 2013. - №4. - С.20-28.

82. Бобынцев, Д.О. Организация конвейерно-параллельного акселератора вычисления коммуникационной задержки / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин // Материалы и упрочняющие технологии-2010: сб. материалов XVII Российской научно-техн. конф. с международным участием. 4.2. - Курск: ЮЗГУ, 2010. - С. 191-195.

83. Патент РФ №2460126. Устройство анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах / Д.О. Бобынцев, Д.Б. Борзов, B.C. Титов, А.П. Типикин. Заявл. 20.05.2011, опубл. 27.08.2012.

84. Бобынцев, Д.О. Устройство анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах / Д.О. Бобынцев, Д.Б. Борзов // Практика и перспективы развития партнёрства в сфере высшей школы: материалы 12 между нар. научно-практического семинара. - Донецк: ДонНТУ, 2011. - С. 25-28.

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