close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
Бобынцев Денис Олегович
Методы и средства планирования размещения параллельных подпрограмм в
матричных мультипроцессорах
Специальность 05.13.05 – Элементы и устройства
вычислительной техники и систем управления
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Курск – 2014
2
Работа выполнена в федеральном государственном бюджетном образовательном
учреждении
высшего
профессионального
образования
«Юго-Западный
государственный университет»
Научный руководитель:
доктор технических наук, профессор
Титов Виталий Семенович
Официальные оппоненты:
Бурковский Виктор Леонидович
доктор технических наук, профессор,
федеральное государственное бюджетное
образовательное учреждение высшего
профессионального образования «Воронежский
государственный технический университет» (г.
Воронеж), заведующий кафедрой
электропривода, автоматики и управления в
технических системах
Прилуцкий Сергей Викторович
кандидат технических наук, федеральное
государственное унитарное предприятие «18
Центральный научно-исследовательский
институт» Министерства обороны Российской
Федерации, начальник отдела научноисследовательского центра (г. Курск)
Ведущая организация:
федеральное государственное бюджетное
образовательное учреждение высшего
профессионального образования «Тульский
государственный университет» (г. Тула)
Защита диссертации состоится 3 июля 2014 г. в 12:00 часов на заседании
диссертационного совета Д 212.105.02, созданного на базе Юго-Западного
государственного университета по адресу: 305040, г. Курск, ул. 50 лет Октября, 94
(конференц-зал).
С диссертацией можно ознакомиться в библиотеке и на сайте Юго-Западного
государственного университета, адрес сайта http://www.swsu.ru/ds/diss-swsu/.
Автореферат разослан
30 мая 2014 г.
Ученый секретарь
диссертационного совета
Титенко Евгений Анатольевич
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Создание многопроцессорных вычислительных систем
(ВС) является одним из наиболее важных приоритетов развития вычислительной
техники. Данные системы нашли применение при решении вычислительных задач,
которые имеют ограничения по времени выполнения. Частный случай таких систем –
матричные мультипроцессоры (ММП), которые являются перспективным базисом
для построения систем реального времени (СРВ). Сочетание в архитектуре ММП
таких свойств, как параллельность и однородность, создает необходимые условия
для реализации комплексных алгоритмов теоретически неограниченной сложности, а
устойчивость ММП к отказам отдельных процессоров и межпроцессорных каналов
связи обеспечивает повышенный уровень надежности ВС. Многомодульность
позволяет повысить производительность ВС при сопоставимой тактовой частоте
процессорных модулей и умеренном энергопотреблении.
Одной из важных задач в ММП является планирование размещения
подпрограмм по множеству обрабатывающих процессоров. Целью планирования
является минимизация величин коммуникационных задержек при передаче данных
между процессорами, что особенно важно при решении сильносвязных задач.
Длинные составные и перекрывающиеся маршруты транзитной передачи данных
приводят к возрастанию коммуникационных задержек, что существенно снижает
реальную производительность ВС.
Теория параллельной организации и планирования размещения подпрограмм в
многопроцессорных системах достаточно широко разработана. Большой вклад в эту
область внесли работы отечественных и зарубежных ученых: В.П. Гергеля, А.В.
Каляева, И.А. Каляева, И.И. Левина, И.В. Зотова, Вл.В. Воеводина, В.В. Воеводина,
В.М. Курейчика, Д. Гроссмана, Р. Хокни, М. Бергера и др. В данных работах вопросы
минимизации величин коммуникационных задержек рассматривались, но без учёта
требований быстрого восстановления системы, возникающих при отказах
процессорных модулей. Отказы процессоров и межпроцессорных каналов связи
требуют повторной прокладки маршрутов передачи данных, которая может
увеличить степень перекрытий каналов передачи данных и привести к возрастанию
коммуникационной задержки, что, в свою очередь, вызывает необходимость
переразмещения подпрограмм. При этом для оценки коммуникационной задержки
при планировании размещения подпрограмм в ММП необходим анализ физической
топологии мультипроцессора с целью выявления перекрывающихся маршрутов
передачи данных, которые могут привести к увеличению коммуникационной
задержки после маршрутизации. В то же время анализ физической топологии ММП,
содержащего большое количество процессорных модулей, с учётом перекрытий
маршрутов, повышает вычислительную сложность алгоритмов планирования
размещения и время восстановления системы после отказа, что не позволяет
использовать данные алгоритмы в СРВ при наличии требования высокой готовности.
Таким образом, существует противоречие между необходимостью уменьшения
коммуникационной задержки для повышения реальной производительности
вычислительной системы и необходимостью оперативного восстановления
работоспособности системы после отказов.
4
В связи с изложенным выше актуальной является научно-техническая задача
разработки методов и средств автоматического определения коммуникационной
задержки, учитывающих возможные пересечения маршрутов передачи данных,
обеспечивающих повышение реальной производительности вычислительной
системы.
Цель работы: повышение реальной производительности вычислительной
системы путём уменьшения коммуникационной задержки на основе разработки
методов планирования размещения подпрограмм, учитывающих возможные
пересечения маршрутов передачи данных, и сокращение времени планирования
размещения путём аппаратной реализации вычисления задержки.
Научно-техническая задача декомпозируется на следующие задачи:
1. Анализ состояния вопроса планирования размещения параллельных
подпрограмм в матричных многопроцессорных системах. Обоснование основных
направлений исследований.
2. Разработка методов планирования размещения подпрограмм на основе
анализа топологии многопроцессорной системы и учёта пересечений каналов
передачи данных.
3. Создание
аппаратно-ориентированного
алгоритма
определения
коммуникационной задержки с учётом пересечений каналов передачи данных.
4. Разработка имитационной модели процесса планирования размещения для
оценки времени вычисления коммуникационной задержки при программной
реализации.
5.
Разработка
структурно-функциональной
схемы
акселератора
вычислительного процесса определения коммуникационной задержки при
планировании размещения подпрограмм, и её экспериментальное исследование.
Объект исследования: матричные мультипроцессоры систем реального
времени.
Предмет исследования: алгоритмы и устройства планирования размещения
параллельных подпрограмм по процессорам матричных мультипроцессоров.
Работа выполнена при поддержке гранта Президента РФ МД-2218.2011.8 и в
рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на
2009-2013 гг, проект 14.B37.21.0598.
Научная новизна и положения, выносимые на защиту:
1. Метод определения коммуникационной задержки при планировании
размещения подпрограмм, отличающийся введением этапов вычисления суммарных
задержек на множестве кратчайших путей; нахождения минимальной суммарной
задержки для каждой пары процессоров; позволяющий определить максимальную
задержку при планировании размещения подпрограмм.
2. Метод планирования размещения подпрограмм, отличающийся редукцией
числа рабочих процессоров путём исключения отказавших, позволяющий
минимизировать максимальную задержку при размещении и повысить
производительность вычислительной системы.
5
3. Имитационная модель процесса планирования размещения, особенностью
которой является учёт данных по кратчайшим путям, пересечениям кратчайших
каналов, а также определение на их основе максимальной задержки.
4. Структурно-функциональная схема акселератора вычислительного процесса
определения коммуникационной задержки при планировании размещения
подпрограмм, включающая блоки: хранения данных о кратчайших путях и каналах;
вычисления промежуточных значений коммуникационной задержки; попарных
сравнений с конвейерной структурой обработки данных, и связи между ними,
позволяющая сократить время планирования размещения подпрограмм.
Достоверность результатов диссертационной работы обеспечивается
корректным и обоснованным применением положений и методов комбинаторной
оптимизации, теорий: множеств, графов, вероятностей и математической статистики,
проектирования цифровых устройств, а также подтверждается результатами
имитационного моделирования с использованием зарегистрированных в
установленном порядке программных средств и экспертизой Роспатента.
Практическая ценность работы состоит в следующем:
1. Время вычисления показателя задержки уменьшено на 16 % по сравнению с
программной реализацией разработанного алгоритма путём вынесения на
аппаратный уровень вычислительно сложных процедур анализа базы данных
кратчайших путей, что уменьшает время поиска варианта размещения и
восстановления системы при отказе.
2. Применение метода планирования размещения позволяет уменьшить
коммуникационную задержку путём планирования размещения подпрограмм, в
результате чего производится нахождение решений в 2 раза ближе к нижней оценке
для матрично-тороидальной топологии в конфигурации 8×8 и в 2,37 раз для
матричной топологии в конфигурации 8×8 по сравнению с известными аналогами.
3. Созданная имитационная модель позволяет оценивать степень близости
коммуникационной задержки к нижней оценке при планировании размещения
подпрограмм по минимаксиминному показателю для различных топологий
мультипроцессоров, а также оценивать время вычисления задержки.
Результаты диссертационной работы найдут применение в бортовых системах,
системах слежения, наблюдения, системах цифровой обработки сигналов в реальном
времени, системах управления и т.д. Результаты также могут использоваться при
проектировании мультикомпьютеров в условиях наличия требования высокой
готовности. Кроме того, применение разработанного акселератора позволит
уменьшить время переразмещения подпрограмм и повысить коэффициент
готовности системы.
Практическое использование результатов работы. Результаты, полученные в
диссертационной работе, внедрены в Курском ОАО «Прибор» ОХП ОКБ
«Авиаавтоматика», а также используются в учебном процессе на кафедре
вычислительной техники ЮЗГУ при проведении занятий по дисциплинам «ЭВМ и
периферийные
устройства»,
«Теоретические
основы
организации
многопроцессорных комплексов и систем», «Отказоустойчивые многопроцессорные
платформы», «Вычислительные системы повышенной надёжности».
6
Соответствие
паспорту
специальности.
Содержание
диссертации
соответствует п.2 паспорта специальности 05.13.05 – Элементы и устройства
вычислительной техники и систем управления, так как в ней проведён теоретический
анализ
функционирования
многопроцессорных
вычислительных
систем,
позволивший выявить необходимость анализа топологии вычислительной системы и
тем самым улучшить показатель коммуникационной задержки в линиях связи между
процессорами. Содержание диссертации соответствует п.3 паспорта специальности
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 таблиц.
7
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулированы цель
и задачи исследований, приведены научная новизна, практическая ценность,
результаты реализации работы.
В первом разделе рассматриваются топологии матричных ВС, методы и
средства планирования размещения подпрограмм. В результате анализа сделан вывод
о необходимости оперативного размещения параллельных подпрограмм при наличии
требования высокой готовности без существенной потери производительности,
вызванной возрастанием коммуникационных задержек. Последнее обусловлено
перекрывающимися путями передачи данных между процессорами. Наиболее
приемлемым с точки зрения времени планирования размещения является метод
целенаправленных перестановок подпрограмм с целью распределения связей с
наибольшим весом на наиболее короткие каналы передачи данных в
многопроцессорной системе. Особенностью данного метода является наличие
дополнительных критериев целесообразности перестановок, позволяющих ускорить
сходимость алгоритма планирования размещения подпрограмм, разработанного на
основе данного метода. При этом отмечено незначительное снижение оптимальности
получаемого варианта размещения, которая оценивается как степень близости
максимальной задержки в линиях связи между процессорами к гипотетической
нижней оценке размещения. Для реализации данного метода созданы программноаппаратные средства, подключаемые к ведущей ЭВМ многопроцессорной
вычислительной системы. Данный метод позволяет значительно сократить время
поиска варианта размещения по сравнению с другими методами.
Недостатками данного метода являются:
1) отсутствие анализа пересечений каналов передачи данных, что не позволяет
отслеживать возможное увеличение задержки вследствие пересечения каналов;
2) метод не предполагает изменений количества рабочих процессоров и
переопределение кратчайших расстояний в многопроцессорной системе при отказах
процессоров и межпроцессорных каналов связи, что не позволяет применять его в
матричных мультипроцессорах при отсутствии резерва.
В то же время задача анализа пересечений каналов передачи данных при
большой размерности мультипроцессора предполагает обработку больших объёмов
данных, следовательно, существенно замедляет процесс планирования размещения
подпрограмм. Кроме того, время выполнения комплекса подпрограмм определяется
как сумма времени вычислений и времени обменов данными, поэтому увеличение
производительности в результате планирования размещения подпрограмм не
пропорционально уменьшению коммуникационной задержки.
В связи с изложенным выше сделаны выводы о необходимости модификации
метода целенаправленных перестановок, позволяющей выполнять редукцию числа
рабочих
процессоров
при
отказах,
разработки
метода
определения
коммуникационной задержки, позволяющего учитывать пересечения каналов
передачи данных, создания акселератора вычислительного процесса определения
коммуникационной задержки, позволяющего уменьшить время восстановления
системы после отказов.
8
Во втором разделе осуществляется математическое описание задачи
размещения подпрограмм, описывается процесс анализа перекрытий кратчайших
каналов передачи данных, приводится метод планирования размещения и метод
определения коммуникационной задержки, рассматривается обобщённый алгоритм
планирования размещения подпрограмм.
Задача размещения формализуется следующим образом.
Множество
подпрограмм
описывается
ориентированным
графом
взаимодействия I=<AI,VI>, где AI={a1, a2, …, aNa}, |AI|=Na – множество вершин графа
I, вершины ai  A которого соответствуют подпрограммам, а взвешенные дуги
vij VI описывают связи между подпрограммами, Na – количество подпрограмм.
Весами дуг являются объёмы передаваемых данных между подпрограммами mij в
байтах. Граф I представляется матрицей обмена данными (МОД): M=||mij||, i, j  1, N a .
Мультипроцессор представляется топологической моделью в виде графа
H=<P,VH>, где P={p1, p2, …, pNпр} – множество идентификаторов процессоров, VH –
множество межпроцессорных связей, задаваемых матрицей смежности Q размером
2
2
Nпр= nстр
, где Nпр – количество процессоров, nстр – количество строк, nст –
 nст
количество столбцов матрицы мультипроцессора, при этом Na≤Nпр. По матрице
смежности строится матрица кратчайших расстояний (МКР): D=||dij||, i, j  1, N пp .
Если непосредственной связи между процессорами нет, то элемент МКР dij –
минимальное топологическое расстояние между ними, вычисляемое как кратчайший
путь от вершины pi до вершины pj в графе Н, длина которого равна количеству
последовательно соединённых межпроцессорных каналов связи. При этом любое
минимальное топологическое расстояние между работающим и неработающим
процессорами условно принимается равным нулю. Множество вариантов
кратчайших путей между процессорами pi и pj формирует кратчайший канал между
ними.
База данных кратчайших путей строится по матрице смежности Q и
представляется кортежем B=<C,W,O>, где C={c1,c2,…,ck} – множество кратчайших
каналов между процессорами, W={w1,w2,…,wy} – множество вариантов кратчайших
путей между процессорами, O={o1,o2,…,oy} – множество списков перекрытий
кратчайших путей. Мощности данных множеств следующие: |C|=Nпр2-Nпр, |W|=|O| –
число вариантов кратчайших маршрутов. При этом ci=<pн,pк>, pн и pк – номера
начального и конечного процессоров канала ci, соответственно, wi=<r1, ... ,rdi+1> –
последовательность номеров процессоров, составляющих путь wi, di – длина i-го
кратчайшего пути, oi ={q1,q2,…,qNq} – множество кратчайших каналов,
соответствующих кратчайшим путям, перекрывающимся с i-м путём, с длинами
данных путей d j
(q)
d (i )
≤d i , где j  1, N q , N q   l .
l 1
Размещение в мультипроцессоре комплекса подпрограмм, описываемых графом
I, аналитически описывается следующим отображением:
9
 a( S ) a( S ) ... a ( S ) 
1
2
Na 
s  
,
 p1
p2 ... pNпp 


(1)
где S – это номер очередной перестановки, соответствующей s-му варианту
размещения. Все варианты размещения βS образуют множество всевозможных
N пр !
отображений φ={βS},  
.
N пр  N a !


Пусть
задержка между процессорами pi и pj определяется как
где Zt – кратчайший путь между процессорами pi и pj, g –
постоянный сомножитель, обратный пропускной способности, Tβs(Zt)(pi,pj) – задержка
при передаче данных по Zt-му пути для размещения  S  . На основе Tβs(Zt)(pi,pj)
Tβs(Zt)(pi,pj)=dij(Zt)∙mij∙g,
введём показатель f a 
nkt
 T(SZt )  pi , p j  ,
Zt 1
представляющий собой сумму задержек
для kt-го кратчайшего пути k-го кратчайшего канала, где nkt – количество Zt-х
кратчайших путей с длинами d(Zt)≤ d(k), перекрывающихся с kt-м кратчайшим путём.
Актуальным для практики является случай, когда для любого k-го кратчайшего
канала fa→min, что соответствует выбору наименее загруженного пути между любой
парой процессоров из множества кратчайших путей между ними. Аналитически
данное условие описывается как
fa(pi,pj,βS,k,t)→min.
(2)
При рассмотрении всех кратчайших каналов имеет место матрица минимальных
суммарных задержек M(T)=||mij(T)||, где mij(T)=fa(pi,pj,βS,k,t) – минимальная суммарная
задержка для пары процессоров pi и pj. Скорость работы вычислительной системы
лимитируется худшей попарной задержкой из всех задержек mij(T), которая
вычисляется как
 
fb   S   max mij(T ) .
i, j
(3)
Полученная величина fb(βS) является величиной задержки для размещения βS.
Задача размещения формулируется как поиск такого субоптимального
отображения b* Оj множества A вершин графа I на множество P вершин графа H, что
величина задержки
fb(β*)→min.
(4)
Метод планирования размещения состоит из следующих этапов:
1. По матрице смежности Q формируется матрица кратчайших расстояний
(МКР) и база данных кратчайших путей. При этом строки и столбцы МКР,
соответствующие нерабочим процессорам, являются нулевыми для исключения
данных процессоров из пространства поиска варианта размещения.
2. Путём наложения матрицы обмена данными (МОД) на МКР реализуется
произвольное начальное размещение β1.
3. Вычисляется начальная задержка Tβ1=fb(β1). При этом постоянный
сомножитель g, не влияющий на результаты планирования размещения, временно
опускается с целью сокращения количества арифметических операций.
10
4. Начиная с элемента mij, которому соответствует max{mij∙dij}, столбец элемента
в МОД перемещается на место другого столбца по следующему условию: dix  dij ,
где i,j – координаты перемещаемого элемента МОД; dij – расстояние в МКР, с
которым совпадает элемент МОД; dix – расстояние в МКР, куда целесообразно
переместить элемент mij МОД, i,x – координаты элемента mix на место которого
перемещается в ходе перестановки элемент mij; i – номер строки в МОД и МКР, в
пределах которой выполняется перестановка элементов столбцов j и x; j и x – номера
переставляемых столбцов МОД с обязательной последующей перестановкой
соответствующих им строк. При этом dix≠0, что гарантирует невозможность
назначения подпрограммы в отказавший процессор.
5. После формирования нового варианта размещения по (3) вычисляется
задержка T= fb(βS) и введённая ранее степень уменьшения задержки:

T1
T
.
(5)
6. В случае увеличения значения σ по сравнению с предыдущим значением
дальнейшие перестановки строк и столбцов выполняются на S-м варианте
размещения, в противном случае S-й вариант исключается с возвратом к
предыдущему варианту.
Результатом поиска варианта размещения является матрица обмена данными
Mβ*. Для оценки результата используется введённое ранее понятие гипотетической
нижней оценки размещения Tinf, для вычисления которой элементы МОД
выстраиваются в вектор M ′ по убыванию, а элементы МКР – в вектор D′ по
возрастанию. Значения Tinf и степени близости задержки Tβ* к нижней оценке η
вычисляются по формулам:
Tinf =max{mi ∙di},
(6)
T*

,

(7)
Tinf
где i  1,( N 2p  N p ) .
Метод определения коммуникационной задержки состоит из следующих этапов:
1. По матрицам M и D вычисляются задержки на всех k-х кратчайших каналах
без учёта перекрытий: {Tβs(k)(pi,pj)}={mij∙dij(k)}, где при g=const величина g временно
опускается.
2. Для каждого kt-го кратчайшего пути вычисляется суммарная задержка:
fa 
nkt
 T(SZt )  pi , p j  .
Zt 1
3. По каждому k-му каналу с идентификатором ij определяется минимальная
суммарная задержка Tkmin=min{fa}.
Из всех {Tkmin} находится максимум, который считается величиной
коммуникационной задержки: fb(βS)=max{Tkmin}.
11
База данных кратчайших путей хранится в виде списка записей (строк)
следующего формата: [Nн,Nк][Nн1Nк1,Nн2Nк2, … ,NнnNкn], где Nн и Nк – номера
начального и конечного процессоров кратчайшего пути, соответственно, являющиеся
идентификатором кратчайшего канала, которому соответствует данный путь; Nн1Nк1,
Nн2Nк2, …, NнnNкn – список перекрытий кратчайшего пути. Алгоритм определения
коммуникационной задержки (3), используемый в алгоритме планирования
размещения, состоит из следующих шагов:
1. Принять МОД (М).
2. Принять МКР (D).
3. Принять базу данных кратчайших путей (B).
4. Ввести T=||tij||, где tij=mij∙dij – задержки без учёта перекрытий.
5. Ввести S=||sij|| - матрицу минимальных суммарных задержек. i, j  1, N пр , Sij:=0.
6. Положить i=0.
7. Если i≤NB, прочитать строку B[i], иначе перейти к п. 12.
8. Если М[Nн, Nк]=0, то i=i+1, переход к п.7, иначе к п. 9.
n
9. FS   t[ N нj , N кj ] .
j 1
10. Если S[Nн, Nк]=0 или FS<S[Nн, Nк], то S[Nн, Nк]= FS, иначе перейти к п.11.
11. i=i+1, переход к п.7.
12. fb   S   max sij  , конец алгоритма.
i , j
Описанный алгоритм положен в основу акселератора вычислительного процесса
определения коммуникационной задержки.
В третьем разделе описывается имитационная модель процесса планирования
размещения подпрограмм, приводится оценка показателей эффективности
разработанных методов планирования размещения.
В основе имитационной модели процесса планирования размещения лежат
алгоритмы:
1) построения матрицы кратчайших расстояний и базы данных кратчайших
путей;
2) обобщённый алгоритм планирования размещения подпрограмм;
3) алгоритм определения коммуникационной задержки.
Имитационная модель позволяет определить среднюю степень уменьшения
коммуникационной задержки и среднюю степень её близости к нижней оценке
размещения, а также время выполнения основных алгоритмов, применяемых при
планировании размещения подпрограмм. Кроме того, имитационная модель
допускает применение разработанного ранее минимаксного показателя при
планировании размещения, что позволяет сравнить показатели получаемой
производительности мультипроцессора.
Получена зависимость степени снижения задержки σ(Tн,Тк,R) при использовании
показателя (4) от минимальной степени перекрытия кратчайшего канала R на
примере канала передачи данных между процессорами 1 и 20, так как возрастание
коммуникационной задержки обусловлено перекрывающимися маршрутами
передачи данных. Данный канал имеет длину 5, следовательно, длина списка
12
5
перекрытий каждого кратчайшего пути n   l  15 . Межпроцессорные связи,
l 1
входящие в состав путей канала 1-20, выделены на рис. 1. В соответствии с базой
данных, данный канал имеет 10 кратчайших путей. Минимальной степенью
перекрытия любого кратчайшего канала является величина R  min  Nо( w)  , где
w
– количество элементов списка перекрытий кратчайшего пути w,
которым соответствуют ненулевые элементы матрицы обмена данными (МОД), Nw –
количество кратчайших путей данного канала. При исследовании были использованы
МОД начального размещения, в которых все задачи, имеющие связи между собой,
размещены в выделенной на рис. 1 части, а связи – ненулевые элементы МОД –
генерируются с целью достижения заданной величины R для канала 1-20.
Зависимость σ(Tн,Тк,R) от R построена по результатам работы алгоритма
планирования размещения для описанных выше МОД и приведена на рис. 2, где Тн –
задержка начального варианта размещения, Тк – задержка конечного варианта
размещения. График позволяет сделать вывод о возможности существенного
уменьшения коммуникационной задержки путём планирования размещения при
наличии перекрытий, при этом, чем больше минимальная степень перекрытия, тем
выше степень снижения задержки.
В соответствии с определённой выше тенденцией для сравнения эффективности
применения показателя (4) с ранее применявшимся при планировании размещения
минимаксным показателем выбрана сильносвязная задача гравитационного
взаимодействия N тел, заключающаяся в пошаговом расчёте динамики изменения
координат тел через определенные шаги времени. Параллельными подпрограммами в
данном случае являются задачи расчёта новой координаты для каждого тела. Так как
координата любого из тел используется для расчёта координат всех остальных тел на
2
следующей итерации цикла, граф взаимодействия подпрограмм содержит (N - 1)
обменов при расчете расстояний, что существенно увеличивает степень перекрытий
каналов передачи данных. При этом дуги графа имеют одинаковые веса, равные
количеству байт, необходимому для хранения значения координат (8 байт для чисел
с плавающей точкой двойной точности).
Вводится показатель производительности вычислительной системы:
Vвыч
,
(8)

w  1, N w , No
(w)
Т выч  Т ком
где Vвыч – объём вычислений (число операций с плавающей точкой, FLOPs), Твыч –
время вычислений в секундах, Тком – время передачи данных, которое оценивается
как максимальное время передачи данных в любой паре процессоров и зависит от
результата планирования размещения подпрограмм. Для сравнения получаемых
показателей производительности планирование размещения выполнено на МОД
задачи 16 тел (1/4 заполнения мультипроцессора) с применением сначала
минимаксного показателя, затем показателя (4). Коммуникационная задержка для
полученных вариантов размещения вычисляется по формуле (3) с применением
постоянного сомножителя g, обратного пропускной способности, что позволяет
оценить время передачи данных Тком для обоих вариантов размещения.
13
Рис. 1. Матрично-тороидальная
Рис. 2. Зависимость степени уменьшения
топология с выделением путей
коммуникационной задержки от минимальной
канала 1-20
степени перекрытия для канала 1-20
В результате экспериментов получено отношение:

(9)
 1,
2
где λ1≈0,48 Гфлоп/с – получаемый показатель производительности при планировании
на основе показателя (4), λ2≈0,32 Гфлоп/с – на основе минимаксного показателя. Так
как объём и время вычислений не зависят от варианта размещения, величина ψ
зависит только от Тком. Для описанной выше задачи 16 тел получена оценка
увеличения реальной производительности в ψ=1,5 раза по сравнению с минимаксным
показателем, что позволяет сделать вывод о возможности увеличения реальной
производительности при применении показателя (4) по сравнению с минимаксным
показателем.
В результате имитационного моделирования также оценена средняя степень
близости коммуникационной задержки (4) к нижней оценке размещения Tinf (6).
Степень близости η вычисляется по формуле 7. При планировании размещения по
минимаксному показателю получены значения η=26,77±2,07 для матричной
топологии и η=10,68±0,42 для матрично-тороидальной топологии. При планировании
размещения по показателю (4) η=11,29±0,57 для матричной топологии и η=5,33±0,1
для матрично-тороидальной топологии. Таким образом, применение показателя (4)
позволяет находить варианты размещения в среднем не менее чем в 2 раза ближе к
нижней оценке по сравнению с применением минимаксного показателя.
В четвёртом разделе представлена схема программно-аппаратного комплекса
планирования размещения подпрограмм, структурно-функциональная схема
акселератора вычислительного процесса определения коммуникационной задержки
при планировании размещения подпрограмм и структурная схема его основного
блока, приведены результаты расчёта времени аппаратной реализации определения
задержки, а также аппаратной сложности 2 и 3 ступени акселератора.
На рис. 3 приведена схема программно-аппаратного комплекса планирования
размещения подпрограмм. Микропроцессорный контроллер (МПК) программно
формирует матрицу кратчайших расстояний (МКР) и базу данных кратчайших путей
14
по матрице смежности процессоров Q и выполняет перестановочный алгоритм
формирования нового варианта размещения. Так как имеется возможность
параллельного построения N частей базы данных, где N – количество процессоров
анализируемой матричной системы, целесообразно использовать в контроллере
многоядерный процессор для ускорения построения базы данных. Матрица обмена
данными каждого варианта размещения, матрица кратчайших расстояний и база
данных передаются в акселератор для вычисления задержки, значение которой
возвращается в МПК. МПК возвращает в ведущую ЭВМ конечный вариант
размещения Mβ*.
Рис. 3. Схема программно-аппаратного комплекса планирования размещения
подпрограмм
Структурно-функциональная схема акселератора приведена на рис. 4. Матрицы
МОД и МКР загружаются в ОЗУ1 и ОЗУ2 акселератора соответственно. Записи базы
данных кратчайших путей загружаются в блок ОЗУ3. Для ускорения обработки
данных записи делятся на n блоков, обрабатываемых параллельно. В каждой
оперативной памяти (ОП) блока ОЗУ3 содержится фрагмент базы данных, размер
которого выбирается при проектировании.
Конвейерная организация акселератора позволяет одновременно проводить
обработку данных об очередном варианте размещения и записывать в память данные
о следующем варианте. Конвейер содержит 3 ступени:
1) ОЗУ1, ОЗУ2 и конвейеризованный блок умножения БУК, вычисляющий
поэлементное произведение МОД и МКР;
2) блоки памяти БП1 и БП2;
3) мультиплексор данных, накапливающие блоки суммирования (НСМ),
определения минимума (HMIN) и максимума (HMAX), входящие в ЛМАХ, и блок
ПК МАХ, вычисляющие значение коммуникационной задержки.
Структурная схема блока ЛМАХ вычисления промежуточного значения
задержки, обрабатывающего данные i-го модуля оперативной памяти блока ОЗУ 5,
приведена на рис. 5.
В памяти 1 хранится обрабатываемый фрагмент базы данных, в памяти 2 –
данные, поступающие с БУК. Значения из памяти 2 выбираются при чтении списков
перекрытий кратчайших путей из памяти 1. Суммарные задержки по кратчайшим
путям вычисляются сумматором 17. Компаратор 8 определяет минимальное из
последовательно поступающих значений суммарных задержек, компаратор 9
определяет максимальное из последовательно поступающих значений минимальных
суммарных задержек, которое поступает в блок ПК МАХ.
Блок ПК МАХ является иерархической структурой цифровых компараторов.
Компараторы нижнего уровня попарно сравнивают значения, поступающие из
блоков ЛМАХ, и передают результаты компараторам следующего уровня для
15
дальнейшего попарного сравнения. Если количество блоков ЛМАХ нечётное, данные
одного из них передаются на один из последующих уровней. Количество уровней
равно log 2 n , где n – количество блоков ЛМАХ.
Рис. 4. Структурно-функциональная схема акселератора вычислительного процесса
определения коммуникационной задержки
Для 2 и 3 ступени акселератора проведены расчёты быстродействия и построены
зависимости времени расчёта величины задержки (рис. 6) и общей аппаратной
сложности (рис. 7) от количества параллельно работающих блоков ЛМАХ.
Вычисление значения задержки в блоке ЛМАХ выполняется сумматором,
получающим данные из памяти 2, и двумя компараторами 15 и 16 на схеме. Адрес
ячейки памяти 2 формируется на основании данных, последовательно поступающих
из памяти 1, причём существуют данные, которые в формировании адреса не
участвуют. Поэтому наибольшую длительность имеет процесс получения значения
из памяти 2, который определяется временами срабатывания: счётчиков 3 и 4 – tсч,
регистров 10 – 13 – tрг, компараторов 6 и 7 – tкомп, многовходового элемента И 29 – t8И,
элементов И 32 и 33 – tИ, элемента ИЛИ-НЕ 28 – t3ИЛИ-НЕ и мультиплексоров 40 и 41 –
tMUX, а также временами чтения данных памяти 1 и 2 – tRAM1 и tRAM2.
В соответствии с изложенным выше и алгоритмом работы блока ЛМАХ время
чтения строки базы данных из памяти 1 определяется следующей формулой:
Tчт.стр=(tсч+tRAM1+tрг+tкомп)∙2+((tсч+tRAM1+t8И+tИ+t3ИЛИ-НЕ+tрг+tMUX)∙2+tRAM2)∙Nпер,
где Nпер – длина списка перекрытий, t – времена срабатывания соответствующих
цифровых узлов. Время обработки всего фрагмента базы данных из памяти 1 с
учётом чтения кода разделения строк определяется по следующей формуле:
Tобщ=Tчт.стр.∙Nстр∙t8И, где Nстр – количество строк базы данных в памяти 1.
16
Рис. 5. Структурная схема блока ЛМАХ определения промежуточного значения
задержки
В соответствии с количеством эквивалентных вентилей, приходящихся на
используемые элементы, наибольшее количество вентилей при любом количестве
блоков ЛMAX приходится на модули памяти 1, так как объём базы данных
значительно превышает объём матрицы задержек, загружаемой в память 1. При этом
максимальное количество блоков ЛMAX ограничено возможностями разделения
базы данных на независимые фрагменты так, чтобы все кратчайшие пути любого
канала находились в пределах одного блока ЛMAX. Следовательно, максимальное
количество блоков ЛМАХ равно количеству каналов передачи данных – 4032 для
мультипроцессора в конфигурации 8×8. При этом количество уровней блока ПК
МАХ равно 12.
В соответствии со схемой блока ЛMAX количество эквивалентных вентилей в
блоке рассчитывается следующей формулой:
M=3mсч+mRAM1+mRAM2+NНЕ∙mНЕ+7mИ+3mИЛИ+2mMUX+3mтг+7mрг+mSUM+4mкомп+7mз,
где N – количество элементов в блоке, m – количество эквивалентных вентилей на
элемент данного типа.
С помощью программных средств была проведена оценка времени программной
реализации определения задержки для различных моделей микропроцессоров (рис.
8): 1 – Intel Atom N280, 1,67 ГГц; 2 – Intel Pentium E5500, 2,8 ГГц; 3 – Intel Core2Duo
E8400, 3 ГГц; 4 – Intel Core i5 М480, 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 ГГц.
Результаты экспериментов позволяют сделать вывод, что выполнение процедуры
расчёта задержки для матрично-тороидальной топологии в конфигурации 8×8 в
представленных выше микропроцессорах составляет менее секунды, однако при N-
17
кратном вызове данной процедуры, что предполагает алгоритм планирования, время
расчёта увеличится в N раз. При этом по результатам исследований можно сделать
вывод, что время расчёта показателя при программной реализации не зависит от
частоты процессора.
Кроме того, проведено сравнение времени определения задержки tз со временем
формирования следующего варианта размещения – временем целенаправленной
перестановки строк и столбцов МОД tп. Рис. 8 позволяет сделать вывод, что
отношение tз к tп лежит в интервале (503…839), поэтому для ускорения планирования
размещения целесообразно выносить определение задержки на аппаратный уровень.
Рис. 6. Зависимость времени расчёта
задержки от количества блоков ЛМАХ
Рис. 7. Зависимость аппаратной
сложности 2 и 3 ступени акселератора от
количества блоков ЛМАХ
1
t, мс 278,1
45
95,4
45
88,945
67,245
2
99,9
45
3
147,0
45
132,5
45
111,7
45
54,145
58,445
10
1
0,01
0,38
2
0,14
3
0,13
4
0,13
5
0,15
6
0,23
7
0,20
8
0,13
9
0,07
10
0,08
Процессоры
Рис. 8. Сводная диаграмма времени программной реализации целенаправленных
перестановок (3), времени программного определения коммуникационной задержки
(1) и времени определения задержки аппаратных способом при 2 блоках ЛМАХ (2)
Согласно рис. 8 наименьшее время программной реализации определения
задержки из полученных составляет 54,1 мс, поэтому, в соответствии с рис. 6
уменьшение времени достигается при количестве блоков ЛМАХ от 2. В соответствии
с базой данных кратчайших путей канал наибольшей длины для матричнотороидальной топологии имеет 280 вариантов кратчайшего маршрута, каждый из
которых имеет список перекрытий длиной 36. Это позволяет сделать вывод, что
время работы блока ПК МАХ пренебрежимо мало по сравнению с временем работы
блока ЛМАХ, поэтому при расчёте времени аппаратной реализации блок ПК МАХ не
учитывается. В соответствии с диаграммой на рис. 8 время расчёта задержки при 2
блоках ЛМАХ составляет 84 % от наименьшего времени программной реализации, то
есть меньше на 16 %. Увеличение количества блоков ЛМАХ, согласно рис. 7 не
приводит к пропорциональному увеличению аппаратной сложности, что позволяет
использовать
параллельную
организацию
акселератора
в
матричных
вычислительных системах реального времени.
В заключении сформулированы основные результаты диссертационной работы.
18
В приложениях представлены листинги программ моделирования процедур
планирования размещения, фрагмент базы данных кратчайших путей, типовые схемы
цифровых устройств, а также акты о внедрении результатов исследований.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Диссертационная работа посвящена решению научно-технической задачи
разработки методов и средств автоматического определения коммуникационной
задержки, учитывающих возможные пересечения маршрутов передачи данных,
обеспечивающих повышение реальной производительности вычислительной
системы. В ходе решения этой задачи получены следующие основные результаты.
1. Проведен анализ состояния вопроса планирования размещения параллельных
подпрограмм в матричных многопроцессорных системах, обоснована необходимость
разработки методов и средств планирования размещения подпрограмм, позволяющих
учитывать пересечения каналов передачи данных, выполнять редукцию числа
рабочих процессоров при отказах и оперативно восстанавливать работоспособность
системы после отказов.
2. Разработаны методы планирования размещения, отличающиеся анализом
топологии матричного мультипроцессора и редукцией числа рабочих процессоров
при отказах, позволяющие повысить реальную производительность вычислительной
системы.
3. Создан
аппаратно-ориентированный
алгоритм
определения
коммуникационной задержки, который положен в основу функционирования
акселератора вычислительного процесса.
4. Разработана имитационная модель планирования размещения, с помощью
которой оценены основные показатели эффективности разработанных методов:
время
их
программной
реализации,
степень
увеличения
реальной
производительности вычислительной системы при планировании размещения;
обоснована
целесообразность
аппаратной
реализации
определения
коммуникационной задержки.
5. Разработана
структурно-функциональная
схема
акселератора
вычислительного процесса определения коммуникационной задержки при
планировании размещения подпрограмм, особенностью которой являются блоки:
хранения данных о кратчайших путях и каналах; вычисления промежуточных
значений коммуникационной задержки; попарных сравнений с конвейерной
структурой обработки данных, и связи между ними, позволяющая сократить время
планирования размещения подпрограмм.
6. Проведено экспериментальное исследование схемы, в результате которого
получена оценка сокращения времени определения коммуникационной задержки при
аппаратной реализации на 16 % по сравнению с программной реализацией.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ
в рецензируемых научных журналах и изданиях
1. Бобынцев, Д.О. Минимаксиминный критерий оценки качества размещения
параллельных подпрограмм в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б.
Борзов // Известия Юго-Западного государственного университета. Серия.
19
Управление, вычислительная техника, информатика. Медицинское приборостроение.
– 2012. – №2. – Ч.1. – С.27-31.
2. Бобынцев, Д.О. Влияние латентной составляющей коммуникационной
задержки
на
размещение
параллельных
подпрограмм
в
матричных
мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов, С.Г. Емельянов, В.С. Титов //
Известия Юго-Западного государственного университета. – 2012. – №3. – Ч.1. – С.5458.
3. Бобынцев, Д.О. Анализ качества размещения параллельных подпрограмм в
матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов, А.П. Типикин //
Известия высших учебных заведений. Приборостроение. – 2013. – Т.56. – №6. – С.3539.
4. Бобынцев, Д.О. Оценка производительности матричного мультипроцессора
при выполнении параллельного алгоритма решения задачи гравитационного
взаимодействия N тел / Д.О. Бобынцев, Э.И. Ватутин, В.С. Титов // Известия ЮгоЗападного государственного университета. Серия. Управление, вычислительная
техника, информатика. Медицинское приборостроение. – 2013. – №4. – С.20-28.
Патенты на изобретение
5. Патент №2406135 Российская Федерация G06F17/50. Устройство поиска
нижней оценки размещения в системах с матричной организацией при направленной
передаче информации / Д.О. Бобынцев, Д.Б. Борзов, заявл. 09.02.2009, опубл.
10.12.2010.
6. Патент №2460126 Российская Федерация G06F17/00. Устройство анализа
перекрытий
каналов
при
размещении
параллельных
подпрограмм
в
многопроцессорных системах / Д.О. Бобынцев, Д.Б. Борзов, В.С. Титов, А.П.
Типикин, заявл. 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
11. Бобынцев, Д.О. Применение минимаксиминного критерия для управления
качеством размещения задач в многопроцессорных системах / Д.О. Бобынцев, Д.Б.
Борзов, А.П. Типикин // Распознавание – 2010: сб. материалов IX Международной
конференции. – Курск: ЮЗГУ, 2010. – С. 152-154.
12. Бобынцев, Д.О. Организация конвейерно-параллельного акселератора
вычисления коммуникационной задержки / Д.О. Бобынцев, Д.Б. Борзов, А.П.
Типикин // Материалы и упрочняющие технологии-2010: сб. материалов XVII
Российской научно-техн. конф. с международным участием. Ч.2. – Курск: ЮЗГУ,
2010. – С. 191-195.
13. Бобынцев, Д.О. Методика исследования влияния латентной составляющей
коммуникационной задержки в матричных мультиконтроллерах / Д.О. Бобынцев,
Д.Б. Борзов, А.П. Типикин // Информационно-измерительные диагностические и
управляющие системы: сб. мат. II Международной научно-технической
конференции. – Курск: ЮЗГУ, 2011. – С. 103-104.
14. Бобынцев, Д.О. Устройство анализа перекрытий каналов при размещении
параллельных подпрограмм в многопроцессорных системах / Д.О. Бобынцев, Д.Б.
Борзов // Практика и перспективы развития партнёрства в сфере высшей школы:
материалы 12 междунар. научно-практического семинара. – Донецк, ДонНТУ, 2011.
– С. 25-28.
15. Бобынцев, Д.О. Использование многопроцессорных систем в технологии
IPTV / Д.О. Бобынцев // Научно-техн. междун. молодёжная конф. «Системы,
методы, техника и технологии обработки медиаконтента»: сборник тезисов. – М.:
МГУП им. Ивана Фёдорова, 2011. – С. 14-15.
16. Бобынцев, Д.О. Применение параллельных вычислительных систем в
биоинформатике / Д.О. Бобынцев, Д.Б. Борзов // Распознавание – 2012: сб. мат. Х
Междунар. научно-технической конференции. – Курск, ЮЗГУ, 2012. С. 133-134.
17. Бобынцев, Д.О. Программная модель процедур планирования размещения
задач в матричных мультиконтроллерах / Д.О. Бобынцев, Д.Б. Борзов //
Информационные системы и технологии: сб. докладов. – Курск, ЮЗГУ, 2012. С. 6364.
18. Бобынцев, Д.О. Программа построения базы данных избыточных
кратчайших путей в графе / Д.О. Бобынцев // свидетельство о государственной
регистрации программы для ЭВМ №2010614500, заявл. 19.05.2010, зарег. 08.07.2010.
19. Бобынцев, Д.О. Программа оценки качества размещения параллельных
подпрограмм в матричном мультиконтроллере / Д.О. Бобынцев // свидетельство о
государственной регистрации программы для ЭВМ №2010614501, заявл. 19.05.2010,
зарег. 08.07.2010.
Подписано в печать ________________. Формат 6084 1/16.
Печ. л. 1.0. Тираж ___ экз. Заказ __
Юго-Западный государственный университет.
Издательско-полиграфический центр
Юго-Западный государственный университет
305040, г. Курск, ул. 50 лет Октября, 94
Документ
Категория
Без категории
Просмотров
12
Размер файла
744 Кб
Теги
размещения, метод, подпрограмма, мультипроцессорах, матричный, планирование, средств, параллельное
1/--страниц
Пожаловаться на содержимое документа