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

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

Бобынцев Денис Олегович

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

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

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

5 ш т

Курск-2014

005549709

Работа выполнена в федеральном государственном бюджетном образовательное учреждении высшего профессионального образования «Юго-Западньп государственный университет»

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

' Титов Виталий Семенович

Официальные оппоненты: Бурковский Виктор Леонидович

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

Прилуцкий Сергей Викторович

кандидат технических наук, федеральное государственное унитарное предприятие «18 Центральный научно-исследовательский институт» Министерства обороны Российской Федерации, начальник отдела научно-исследовательского центра (г. Курск)

Ведущая организация: федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Тульский государственный университет» (г. Тула)

Защита диссертации состоится 3 июля 2014 г. в 12:00 часов на заседании диссертационного совета Д 212.105.02, созданного на базе Юго-Западного государственного университета по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

С диссертацией можно ознакомиться в библиотеке и на сайте Юго-Западного государственного университета, адрес сайта http://www.swsu.ru/ds/diss-swsu/.

Автореферат разослан 30 мая 2014 г.

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

Титенко Евгений Анатольевич

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

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

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

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

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

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

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

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

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. Созданная имитационная модель позволяет оценивать степень близости оммуникационной задержки к нижней оценке при планировании размещения одпрограмм по минимаксиминному показателю для различных топологий ультипроцессоров, а также оценивать время вычисления задержки.

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

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

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

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

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

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

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

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

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

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

Недостатками данного метода являются:

1) отсутствие анализа пересечений каналов передачи данных, что не позволяет отслеживать возможное увеличение задержки вследствие пересечения каналов;

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

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

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

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

Задача размещения формализуется следующим образом.

Множество подпрограмм описывается ориентированным графо! взаимодействия 1=<АГ,УГ>, где Л/={я/, а2, ..., аЛ'а}, \А\=Ыа - множество вершин граф I, вершины я, е А которого соответствуют подпрограммам, а взвешенные дул Гу е У1 описывают связи между подпрограммами, — количество подпрограмм Весами дуг являются объёмы передаваемых данных между подпрограммами ту байтах. Граф / представляется матрицей обмена данными (МОД): М=\\т^\\, /,у = 1,Ыа

Мультипроцессор представляется топологической моделью в виде граф Н=<Р,Ун>, где Р={р1, р2, ■■•, Р.Упр} ~ множество идентификаторов процессоров, Ун -множество межпроцессорных связей, задаваемых матрицей смежности Q размера Аир™ пстр х пст> где Кг.р - количество процессоров, пстр - количество строк, пст количество столбцов матрицы мультипроцессора, при этом Иа<Ипр. По матрице смежности строится матрица кратчайших расстояний (МКР): Г)=\\с1у\\, =

Если непосредственной связи между процессорами нет, то элемент МКР ¿4 -минимальное топологическое расстояние между ними, вычисляемое как кратчайший путь от вершины р,- до вершины pj в графе Н, длина которого равна количеству последовательно соединённых межпроцессорных каналов связи. При этом любо минимальное топологическое расстояние между работающим и неработающш процессорами условно принимается равным нулю. Множество варианте кратчайших путей между процессорами р, и pj формирует кратчайший канал между ними.

База данных кратчайших путей строится по матрице смежности <2 представляется кортежем В=<С,1¥,0>, где С={с1,с},...,ск} - множество кратчайши каналов между процессорами, - множество вариантов кратчайших

путей между процессорами, 0={0г,02,...,0у} - множество списков перекрытий кратчайших путей. Мощности данных множеств следующие: \Ц=М„р2-Мпр, -

число вариантов кратчайших маршрутов. При этом с,=<рН)р,>, ри и рк - номера начального и конечного процессоров канала С/, соответственно, 'И'/=<г;, ... —

последовательность номеров процессоров, составляющих путь и'/, с/, - длина г'-го кратчайшего пути, — множество кратчайших каналов,

соответствующих кратчайшим путям, перекрывающимся с г'-м путём, с длинами

__¿С)

данных путей <1/ч><4и где ] = \,Ы„ , N. = £ /.

/=1

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

ßs =

a(S) JS) (S)

al 2 ■■■ aNa

KPl Pl - PNnp

(1)

где S - это номер очередной перестановки, соответствующей 5-му варианту размещения. Все варианты размещения ßs образуют множество всевозможных

N '

отображений rp={ßs\, U - --й£1-

Пусть задержка между процессорами р, и pj определяется как Tßs ' (PuPß-dij^-my-g, где Zt - кратчайший путь между процессорами pt и pj, g -постоянный сомножитель, обратный пропускной способности, Tßs-°(pi,pß - задержка при передаче данных по 2Гму пути для размещения ßs е (р. На основе Tßs<z,)(p„pj)

введём показатель fа = ZI представляющий собой сумму задержек

для kt-то кратчайшего пути к-го кратчайшего канала, где пк, - количество Z,-х кратчайших путей с длинами cf°< dk>, перекрывающихся с kt-м кратчайшим путём. Актуальным для практики является случай, когда для любого к-го кратчайшего канала/;—>min, что соответствует выбору наименее загруженного пути между любой парой процессоров из множества кратчайших путей между ними. Аналитически данное условие описывается как

fa(p„pj,ßs, к, 0—'min. (2)

При рассмотрении всех кратчайших каналов имеет место матрица минимальных суммарных задержек Л^НК/0!!, где тут=/а(р:,р^,к,t) - минимальная суммарная задержка для пары процессоров pt и рг Скорость работы вычислительной системы лимитируется худшей попарной задержкой из всех задержек mjv, которая вычисляется как

fb{ßs) = max \т\Р\- (3)

Полученная величинаß,(ßs) является величиной задержки для размещения ßs.

Задача размещения формулируется как поиск такого субоптимального отображения ß' б <р множества А вершин графа I на множество Р вершин графа Я, что величина задержки

fb(ß')-*mn. (4)

Метод планирования размещения состоит из следующих этапов:

1. По

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

2. Путём наложения матрицы обмена данными (МОД) на МКР реализуется произвольное начальное размещение ßj.

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

4. Начиная с элемента т0, которому соответствует тах{ту^}, столбец элемента в МОД перемещается на место другого столбца по следующему условию: с!1х < <1Ц, где /,/ — координаты перемещаемого элемента МОД; — расстояние в МКР, с которым совпадает элемент МОД; с11Х - расстояние в МКР, куда целесообразно переместить элемент ту МОД, ¡,х - координаты элемента т« на место которого перемещается в ходе перестановки элемент тф г - номер строки в МОД и МКР, в пределах которой выполняется перестановка элементов столбцов у и х; / и х - номера переставляемых столбцов МОД с обязательной последующей перестановкой соответствующих им строк. При этом ¿¿#0, что гарантирует невозможность назначения подпрограммы в отказавший процессор.

5. После формирования нового варианта размещения по (3) вычисляется задержка Т=/Ь(рз) и введённая ранее степень уменьшения задержки:

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

Результатом поиска варианта размещения является матрица обмена данными Мр*. Для оценки результата используется введённое ранее понятие гипотетической нижней оценки размещения Т,„/, для вычисления которой элементы МОД выстраиваются в вектор М ' по убыванию, а элементы МКР - в вектор П по возрастанию. Значения Тш/ и степени близости задержки Тр. к нижней оценке т| вычисляются по формулам:

Тш/=тах{т1 -с!,}, (6)

гд е1 = 1,(Лг2-ЛГр).

Метод определения коммуникационной задержки состоит из следующих этапов:

1. По матрицам М и £> вычисляются задержки на всех к-х кратчайших каналах без учёта перекрытий: {Т^к)(рир])}={ту^к)}, где при ¿=сопЩ величина ё временно опускается.

2. Для каждого Ы-то кратчайшего пути вычисляется суммарная задержка:

3. По каждому к-щ каналу с идентификатором у определяется минимальная суммарная задержка Тыт~шшЮ •

Из всех {ТШп} находится максимум, который считается величиной коммуникационной задержки:

База данных кратчайших путей хранится в виде списка записей (строк) следующего формата: [NH,NK][NHlNKbNH2Ns2, ... ,NHnNKn], где N„ и NK - номера начального и конечного процессоров кратчайшего пути, соответственно, являющиеся идентификатором кратчайшего канала, которому соответствует данный путь; NHlNKl, Nh2Nk2, ..., NA ~ список перекрытий кратчайшего пути. Алгоритм определения коммуникационной задержки (3), используемый в алгоритме планирования размещения, состоит из следующих шагов:

1. Принять МОД (М).

2. Принять МКР (D).

3. Принять базу данных кратчайших путей (В).

4. Ввести T=||tij||, где tlj=mij-di¡ - задержки без учёта перекрытий.

5. Ввести S=||Sij|| - матрицу минимальных суммарных задержек. V/, j = 1 ,Nnp , Sy:=0.

6. Положить i=0.

7. Если i<NB, прочитать строку B[i], иначе перейти к п. 12.

8. Если M[N„, NK]=0, то i=i+l, переход к п.7, иначе к п. 9.

9. Fs=Ít[NHj,NKj}.

>1

10. Если S[N„, NK]=0 или Fs<S[NH, NJ, то S[NH, NK]= Fs, иначе перейти к n.l 1.

11. i=i+l, переход к п.7.

12. fb(Ps)= шах {íy}, конец алгоритма.

Vi, у

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

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

В основе имитационной модели процесса планирования размещения лежат алгоритмы:

1) построения матрицы кратчайших расстояний и базы данных кратчайших путей;

2) обобщённый алгоритм планирования размещения подпрограмм;

3) алгоритм определения коммуникационной задержки.

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

Получена зависимость Степени снижения задержки ü(TH,TK,R) при использовании показателя (4) от минимальной степени перекрытия кратчайшего канала R на примере канала передачи данных между процессорами 1 и 20, так как возрастание коммуникационной задержки обусловлено перекрывающимися маршрутами передачи данных. Данный канат имеет длину 5, следовательно, длина списка

перекрытий каждого кратчайшего пути п = ]Г / = 15. Межпроцессорные связи,

ы

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

= , - количество элементов списка перекрытий кратчайшего пути V/, которым соответствуют ненулевые элементы матрицы обмена данными (МОД), Л^, -количество кратчайших путей данного канала. При исследовании были использованы МОД начального размещения, в которых все задачи, имеющие связи между собой, размещены в выделенной на рис. 1 части, а связи - ненулевые элементы МОД -генерируются с целью достижения заданной величины Я для канала 1-20.

Зависимость а(Т„,Тк,К) от Я построена по результатам работы алгоритма планирования размещения для описанных выше МОД и приведена на рис. 2, где Т„ -задержка начального варианта размещения, Тк - задержка конечного варианта размещения. График позволяет сделать вывод о возможности существенного уменьшения коммуникационной задержки путём планирования размещения при наличии перекрытий, при этом, чем больше минимальная степень перекрытия, тем выше степень снижения задержки.

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

Вводится показатель производительности вычислительной системы:

X =-^-, (8)

т + т

вын ком

где Увыч - объём вычислений (число операций с плавающей точкой, РШРв), Твыч -время вычислений в секундах, Тком - время передачи данных, которое оценивается как максимальное время передачи данных в любой паре процессоров и зависит от результата планирования размещения подпрограмм. Для сравнения получаемых показателей производительности планирование размещения выполнено на МОД задачи 16 тел (1/4 заполнения мультипроцессора) с применением сначала минимаксного показателя, затем показателя (4). Коммуникационная задержка для полученных вариантов размещения вычисляется по формуле (3) с применением постоянного сомножителя g, обратного пропускной способности, что позволяет оценить время передачи данных Тком для обоих вариантов размещения.

Рис. 1. Матрично-тороидальная Рис. 2. Зависимость степени уменьшения топология с выделением путей коммуникационной задержки от минимальной канала 1-20 степени перекрытия для канала 1-20

В результате экспериментов получено отношение:

где А.(==0,48 Гфлоп/с - получаемый показатель производительности при планировании на основе показателя (4), \2~0,32 Гфлоп/с - на основе минимаксного показателя. Так как объём и время вычислений не зависят от варианта размещения, величина \|/ зависит только от Тком. Для описанной выше задачи 16 тел получена оценка увеличения реальной производительности в \|/=1,5 раза по сравнению с минимаксным показателем, что позволяет сделать вывод о возможности увеличения реальной производительности при применении показателя (4) по сравнению с минимаксным показателем.

В результате имитационного моделирования также оценена средняя степень близости коммуникационной задержки (4) к нижней оценке размещения Тш/ (6). Степень близости г/ вычисляется по формуле 7. При планировании размещения по минимаксному показателю получены значения /;=26,77±2,07 для матричной топологии и 7=10,68±0,42 для матрично-тороидальной топологии. При планировании размещения по показателю (4) >7=11,29±0,57 для матричной топологии и >/=5,33±0,1 для матрично-тороидальной топологии. Таким образом, применение показателя (4) позволяет находить варианты размещения в среднем не менее чем в 2 раза ближе к нижней оценке по сравнению с применением минимаксного показателя.

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

На рис. 3 приведена схема программно-аппаратного комплекса планирования размещения подпрограмм. Микропроцессорный контроллер (МПК) программно формирует матрицу кратчайших расстояний (МКР) и базу данных кратчайших путей

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

Рис. 3. Схема программно-аппаратного комплекса планирования размещения

подпрограмм

Структурно-функциональная схема акселератора приведена на рис. 4. Матрицы МОД и МКР загружаются в ОЗУ1 и ОЗУ2 акселератора соответственно. Записи базы данных кратчайших путей загружаются в блок ОЗУЗ. Для ускорения обработки данных записи делятся на п блоков, обрабатываемых параллельно. В каждой оперативной памяти (ОП) блока ОЗУЗ содержится фрагмент базы данных, размер которого выбирается при проектировании.

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

1) ОЗУ1, ОЗУ2 и конвейеризованный блок умножения БУК, вычисляющий поэлементное произведение МОД и МКР;

2) блоки памяти БП1 и БП2;

3) мультиплексор данных, накапливающие блоки суммирования (НСМ), определения минимума (НМШ) и максимума (НМАХ), входящие в ЛМАХ, и блок ПК МАХ, вычисляющие значение коммуникационной задержки.

Структурная схема блока ЛМАХ вычисления промежуточного значения задержки, обрабатывающего данные 1-го модуля оперативной памяти блока ОЗУ 5, приведена на рис. 5.

В памяти 1 хранится обрабатываемый фрагмент базы данных, в памяти 2 -данные, поступающие с БУК. Значения из памяти 2 выбираются при чтении списков перекрытий кратчайших путей из памяти 1. Суммарные задержки по кратчайшим путям вычисляются сумматором 17. Компаратор 8 определяет минимальное из последовательно поступающих значений суммарных задержек, компаратор 9 определяет максимальное из последовательно поступающих значений минимальных суммарных задержек, которое поступает в блок ПК МАХ.

Блок ПК МАХ является иерархической структурой цифровых компараторов. Компараторы нижнего уровня попарно сравнивают значения,' поступающие из блоков ЛМАХ, и передают результаты компараторам следующего уровня для

дальнейшего попарного сравнения. Если количество блоков ЛМАХ нечётное, данные одного из них передаются на один из последующих уровней. Количество уровней равно |~1о§2 п\ где п - количество блоков ЛМАХ.

Обтая тина микропроцессорного контроллера

определения коммуникационной задержки

Для 2 и 3 ступени акселератора проведены расчёты быстродействия и построены зависимости времени расчёта величины задержки (рис. 6) и общей аппаратной сложности (рис. 7) от количества параллельно работающих блоков ЛМАХ. Вычисление значения задержки в блоке ЛМАХ выполняется сумматором, получающим данные из памяти 2, и двумя компараторами 15 и 16 на схеме. Адрес ячейки памяти 2 формируется на основании данных, последовательно поступающих из памяти 1, причём существуют данные, которые в формировании адреса не участвуют. Поэтому наибольшую длительность имеет процесс получения значения из памяти 2, который определяется временами срабатывания: счётчиков 3 и 4 -регистров 10 — 13 — (р.,, компараторов 6 и 7 - 1кот„ многовходового элемента И 29 — ¡аи, элементов И 32 и 33 — элемента ИЛИ-НЕ 28 — 1зили-пе и мультиплексоров 40 и 41 -Нюх, а также временами чтения данных памяти 1 и 2 - /«л,и/ и /идя-

В соответствии с изложенным выше и алгоритмом работы блока ЛМАХ время чтения строки базы данных из памяти 1 определяется следующей формулой:

где Аг„ер - длина списка перекрытий, / — времена срабатывания соответствующих цифровых узлов. Время обработки всего фрагмента базы данных из памяти 1 с учётом чтения кода разделения ¿трок-определяется по следующей формуле: ТодигТчт.стр;Иещ>^аи, где Ыстр - количество строк-базы-данных'в' памятй' >1 ¡' > .»-¡г > .

Рис. 5. Структурная схема блока JIMAX определения промежуточного значения

задержки

В соответствии с количеством эквивалентных вентилей, приходящихся на используемые элементы, наибольшее количество вентилей при любом количестве блоков J1MAX приходится на модули памяти 1, так как объём базы данных значительно превышает объём матрицы задержек, загружаемой в память 1. При этом максимальное количество блоков JIMAX ограничено возможностями разделения базы данных на независимые фрагменты так, чтобы все кратчайшие пути любого канала находились в пределах одного блока JIMAX. Следовательно, максимальное количество блоков JIMAX равно количеству каналов передачи данных - 4032 для мультипроцессора в конфигурации 8x8. При этом количество уровней блока ПК МАХ равно 12.

В соответствии со схемой блока JIMAX количество эквивалентных вентилей в блоке рассчитывается следующей формулой:

M=3mC4+mR_4Ml+mRAhl2+N„E-m„E+ 7т1^ЗтИли+2тМиХ+Зттг+ 7mp,,+msmi+ 4ткомп+ 7т3, где N - количество элементов в блоке, m - количество эквивалентных вентилей на элемент данного типа.

С помощью программных средств была проведена оценка времени программной реализации определения задержки для различных моделей микропроцессоров (рис. 8): 1 - Intel Atom N280, 1,67 ГГц; 2 - Intel Pentium Е5500, 2,8 ГГц; 3 - Intel Core2Duo E8400, 3 ГГц; 4 - Intel Core i5 M480, 2,67 ГГц; 5 - Intel Core2 Quard Q8400,2,67 ГГц; 6 - Intel Pentium E2160, 1,8 ГГц; 7 - Intel Pentium E2180, 2 ГГц; 8 - AMD Athlon II X4 651, 3 ГГц; 9 - Intel Core i3-2120, 3,3 ГГц, 10 - Intel Core i3-2130, 3,4 ГГц. Результаты экспериментов позволяют сделать вывод, что выполнение процедуры расчёта задержки для матрично-тороидальной топологии в конфигурации 8x8 в представленных выше микропроцессорах составляет менее секунды, однако при N-

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

Кроме того, проведено сравнение времени определения задержки г3 со временем формирования следующего варианта размещения - временем целенаправленной перестановки строк и столбцов МОД t„. Рис. 8 позволяет сделать вывод, что отношение к /п лежит в интервале (503.. .839), поэтому для ускорения планирования размещения целесообразно выносить определение задержки на аппаратный уровень.

Рис. 6. Зависимость времени расчёта Рис. 7. Зависимость аппаратной

задержки от количества блоков ЛМАХ сложности 2 и 3 ступени акселератора от

количества блоков ЛМАХ

Процессоры

Рис. 8. Сводная диаграмма времени программной реализации целенаправленных перестановок (3), времени программного определения коммуникационной задержки (1) и времени определения задержки аппаратных способом при 2 блоках ЛМАХ (2) Согласно рис. 8 наименьшее время программной реализации определения задержки из полученных составляет 54,1 мс, поэтому, в соответствии с рис. 6 уменьшение времени достигается при количестве блоков ЛМАХ от 2. В соответствии с базой данных кратчайших путей канал наибольшей длины для матрично-тороидальной топологии имеет 280 вариантов кратчайшего маршрута, каждый из которых имеет список перекрытий длиной 36. Это позволяет сделать вывод, что время работы блока ПК МАХ пренебрежимо мало по сравнению с временем работы блока ЛМАХ, поэтому при расчёте времени аппаратной реализации блок ПК МАХ не учитывается. В соответствии с диаграммой на рис. 8 время расчёта задержки при 2 блоках ЛМАХ составляет 84 % от наименьшего времени программной реализации, то есть меньше на 16 %. Увеличение количества блоков ЛМАХ, согласно рис. 7 не приводит к пропорциональному увеличению аппаратной сложности, что позволяет использовать параллельную организацию акселератора в матричных вычислительных системах реального времени.

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

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

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

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

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

системы после отказов.

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

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

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

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

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

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

1.Бобынцев, Д.О. Минимаксиминный критерий оценки качества размещения параллельных подпрограмм в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов // Известия Юго-Западного государственного университета. Серия.

Управление, вычислительная техника, информатика. Медицинское приборостроение - 2012. - №2. - Ч. 1. - С.27-31.

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

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

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

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

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

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

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

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

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

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

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

20

/4

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

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

13. Бобынцев, Д.О. Методика исследования влияния латентной составляющей коммуникационной задержки в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин // Информационно-измерительные диагностические и управляющие системы: сб. мат. П Международной научно-технической конференции. - Курск: ЮЗГУ, 2011. - С. 103-104.

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

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

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

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

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

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

Подписано в печать_. Формат 60x84 1/16.

Печ. л. Г0. Тираж 40С экз. Заказ Юго-Западный государственный университет.

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Юго-Западный государственный университет»

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

Бобынцев Денис Олегович

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

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

систем управления

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

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

Курск-2014

Оглавление

Введение...................................................................................................................4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение...........................................................................................................112

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

Приложение А......................................................................................................122

Приложение В......................................................................................................135

Приложение С......................................................................................................141

Приложение D......................................................................................................145

Введение

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

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

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

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

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

зарубежных ученых: В.П. Гергеля, 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].

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

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