Содержание к диссертации
Введение
Глава 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.1. Оценка времени программной реализации алгоритмов планирования размещения 74
3.3. Выводы по главе 77
Глава 4. Акселератор вычислительного процесса определения коммуникационной задержки 78
4.1. Структурно-функциональная организация акселератора вычислительного процесса определения коммуникационной задержки 78
4.2. Организация блока определения промежуточных значений коммуникационной задержки 81
4.3. Оценка времени определения коммуникационной задержки и аппаратной сложности 2 и 3 ступени акселератора 86
4.4. Выводы по главе 111
Заключение 112
Библиографический список 114
- Принципы построения систем реального времени
- Математическое описание задачи размещения подпрограмм
- Оценка степени уменьшения коммуникационной задержки и степени её близости к нижней оценке
- Организация блока определения промежуточных значений коммуникационной задержки
Введение к работе
Актуальность темы. Создание многопроцессорных вычислительных систем (ВС) является одним из наиболее важных приоритетов развития вычислительной техники. Данные системы нашли применение при решении вычислительных задач, которые имеют ограничения по времени выполнения. Частный случай таких систем – матричные мультипроцессоры (ММП), которые являются перспективным базисом для построения систем реального времени (СРВ). Сочетание в архитектуре ММП таких свойств, как параллельность и однородность, создает необходимые условия для реализации комплексных алгоритмов теоретически неограниченной сложности, а устойчивость ММП к отказам отдельных процессоров и межпроцессорных каналов связи обеспечивает повышенный уровень надежности ВС. Многомодульность позволяет повысить производительность ВС при сопоставимой тактовой частоте процессорных модулей и умеренном энергопотреблении.
Одной из важных задач в ММП является планирование размещения подпрограмм по множеству обрабатывающих процессоров. Целью планирования является минимизация величин коммуникационных задержек при передаче данных между процессорами, что особенно важно при решении сильносвязных задач. Длинные составные и перекрывающиеся маршруты транзитной передачи данных приводят к возрастанию коммуникационных задержек, что существенно снижает реальную производительность ВС.
Теория параллельной организации и планирования размещения подпрограмм в многопроцессорных системах достаточно широко разработана. Большой вклад в эту область внесли работы отечественных и зарубежных ученых: В.П. Гергеля, А.В. Каляева, И.А. Каляева, И.И. Левина, И.В. Зотова, Вл.В. Воеводина, В.В. Воеводина, В.М. Курейчика, Д. Гроссмана, Р. Хокни, М. Бергера и др. В данных работах вопросы минимизации величин коммуникационных задержек рассматривались, но без учёта требований быстрого восстановления системы, возникающих при отказах процессорных модулей. Отказы процессоров и межпроцессорных каналов связи требуют повторной прокладки маршрутов передачи данных, которая может увеличить степень перекрытий каналов передачи данных и привести к возрастанию коммуникационной задержки, что, в свою очередь, вызывает необходимость переразмещения подпрограмм. При этом для оценки коммуникационной задержки при планировании размещения подпрограмм в ММП необходим анализ физической топологии мультипроцессора с целью выявления перекрывающихся маршрутов передачи данных, которые могут привести к увеличению коммуникационной задержки после маршрутизации. В то же время анализ физической топологии ММП, содержащего большое количество процессорных модулей, с учётом перекрытий маршрутов, повышает вычислительную сложность алгоритмов планирования размещения и время восстановления системы после отказа, что не позволяет использовать данные алгоритмы в СРВ при наличии требования высокой готовности.
Таким образом, существует противоречие между необходимостью уменьшения коммуникационной задержки для повышения реальной производительности вычислительной системы и необходимостью оперативного восстановления работоспособности системы после отказов.
В связи с изложенным выше актуальной является научно-техническая задача разработки методов и средств автоматического определения коммуникационной задержки, учитывающих возможные пересечения маршрутов передачи данных, обеспечивающих повышение реальной производительности вычислительной системы.
Цель работы: повышение реальной производительности вычислительной системы путём уменьшения коммуникационной задержки на основе разработки методов планирования размещения подпрограмм, учитывающих возможные пересечения маршрутов передачи данных, и сокращение времени планирования размещения путём аппаратной реализации вычисления задержки.
Научно-техническая задача декомпозируется на следующие задачи:
-
Анализ состояния вопроса планирования размещения параллельных подпрограмм в матричных многопроцессорных системах. Обоснование основных направлений исследований.
-
Разработка методов планирования размещения подпрограмм на основе анализа топологии многопроцессорной системы и учёта пересечений каналов передачи данных.
-
Создание аппаратно-ориентированного алгоритма определения коммуникационной задержки с учётом пересечений каналов передачи данных.
-
Разработка имитационной модели процесса планирования размещения для оценки времени вычисления коммуникационной задержки при программной реализации.
5. Разработка структурно-функциональной схемы акселератора
вычислительного процесса определения коммуникационной задержки при
планировании размещения подпрограмм, и её экспериментальное исследование.
Объект исследования: матричные мультипроцессоры систем реального времени.
Предмет исследования: алгоритмы и устройства планирования размещения параллельных подпрограмм по процессорам матричных мультипроцессоров.
Работа выполнена при поддержке гранта Президента РФ МД-2218.2011.8 и в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг, проект 14.B37.21.0598.
Научная новизна и положения, выносимые на защиту:
-
Метод определения коммуникационной задержки при планировании размещения подпрограмм, отличающийся введением этапов вычисления суммарных задержек на множестве кратчайших путей; нахождения минимальной суммарной задержки для каждой пары процессоров; позволяющий определить максимальную задержку при планировании размещения подпрограмм.
-
Метод планирования размещения подпрограмм, отличающийся редукцией числа рабочих процессоров путём исключения отказавших, позволяющий минимизировать максимальную задержку при размещении и повысить производительность вычислительной системы.
-
Имитационная модель процесса планирования размещения, особенностью которой является учёт данных по кратчайшим путям, пересечениям кратчайших каналов, а также определение на их основе максимальной задержки.
-
Структурно-функциональная схема акселератора вычислительного процесса определения коммуникационной задержки при планировании размещения подпрограмм, включающая блоки: хранения данных о кратчайших путях и каналах; вычисления промежуточных значений коммуникационной задержки; попарных сравнений с конвейерной структурой обработки данных, и связи между ними, позволяющая сократить время планирования размещения подпрограмм.
Достоверность результатов диссертационной работы обеспечивается
корректным и обоснованным применением положений и методов комбинаторной
оптимизации, теорий: множеств, графов, вероятностей и математической статистики,
проектирования цифровых устройств, а также подтверждается результатами
имитационного моделирования с использованием зарегистрированных в
установленном порядке программных средств и экспертизой Роспатента.
Практическая ценность работы состоит в следующем:
-
Время вычисления показателя задержки уменьшено на 16 % по сравнению с программной реализацией разработанного алгоритма путём вынесения на аппаратный уровень вычислительно сложных процедур анализа базы данных кратчайших путей, что уменьшает время поиска варианта размещения и восстановления системы при отказе.
-
Применение метода планирования размещения позволяет уменьшить коммуникационную задержку путём планирования размещения подпрограмм, в результате чего производится нахождение решений в 2 раза ближе к нижней оценке для матрично-тороидальной топологии в конфигурации 88 и в 2,37 раз для матричной топологии в конфигурации 88 по сравнению с известными аналогами.
-
Созданная имитационная модель позволяет оценивать степень близости коммуникационной задержки к нижней оценке при планировании размещения подпрограмм по минимаксиминному показателю для различных топологий мультипроцессоров, а также оценивать время вычисления задержки.
Результаты диссертационной работы найдут применение в бортовых системах, системах слежения, наблюдения, системах цифровой обработки сигналов в реальном времени, системах управления и т.д. Результаты также могут использоваться при проектировании мультикомпьютеров в условиях наличия требования высокой готовности. Кроме того, применение разработанного акселератора позволит уменьшить время переразмещения подпрограмм и повысить коэффициент готовности системы.
Практическое использование результатов работы. Результаты, полученные в
диссертационной работе, внедрены в Курском ОАО «Прибор» ОХП ОКБ
«Авиаавтоматика», а также используются в учебном процессе на кафедре
вычислительной техники ЮЗГУ при проведении занятий по дисциплинам «ЭВМ и
периферийные устройства», «Теоретические основы организации
многопроцессорных комплексов и систем», «Отказоустойчивые многопроцессорные платформы», «Вычислительные системы повышенной надёжности».
Соответствие паспорту специальности. Содержание диссертации
соответствует п.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 таблиц.
Принципы построения систем реального времени
В настоящее время среди приоритетов развития средств вычислительной техники специалистами отмечается необходимость разработки многопроцессорных вычислительных систем ВС [1].
Устойчивой тенденцией развития науки и техники является постоянное появление новых вычислительных задач, для решения которых за приемлемое время недостаточно производительности последовательных однопроцессорных ВС, что способствует широкому распространению многоядерных и многопроцессорных ВС. Под производительностью понимают количество операций, выполняемых системой в единицу времени.
Многопроцессорные ВС имеют широкий спектр областей применения, в которых решаются вычислительно сложные задачи, требующие параллельных вычислений. Использование данных ВС необходимо для научных исследований в различных областях физики. Среди технических проблем, требующих применения высокопроизводительных ВС, отмечаются задачи аэрокосмической и автомобильной промышленности, ядерной энергетики. Кроме того, данные ВС необходимы для финансового и экономического прогнозирования, нефтегазовой разведки, прогнозирования погоды и климата, оптимизации транспортных потоков в мегаполисах, исследований в биологии и генетике. Многопроцессорные ВС широко используются в химии, в военных проектах разработки оружия и военной техники: бесшумных подводных лодок, систем противоракетной обороны и т.д., а также применяются в критических системах реального времени.
Отечественные разработки многопроцессорных ВС относятся к классу суперЭВМ с кластерной архитектурой, представляющих собой объединение множества типовых процессорных модулей с помощью стандартных коммуникационных средств. Отмечается, что кластерные суперЭВМ имеют существенные недостатки, связанные с относительно низкой скоростью обмена данными между процессорами, ограниченной пропускной способностью коммуникационной среды, необходимостью синхронизации множества взаимодействующих последовательных процессов, каждый из которых выполняется на отдельном процессоре, и т.д. В результате производительность, близкую к пиковой, суперЭВМ кластерного типа демонстрируют, в основном, при решении «слабосвязных» задач, не требующих интенсивного обмена данными между процессорными модулями.
Описанные выше недостатки кластерных ВС характерны для многопроцессорных систем с «жёсткой» архитектурой, которая применяется также в матричных мультипроцессорах критических систем, работающих в реальном времени, где выполнение задач ограничивается временными рамками, определяемыми разработчиком [2]. Данное обстоятельство обуславливает необходимость повышения производительности критических систем.
В реконфигурируемых вычислительных системах на основе ПЛИС, пользователю доступна адаптация архитектуры вычислительной системы под структуру графа информационных зависимостей решаемой задачи [1,3-8]. Данный подход заключается в создании в базовой архитектуре ПЛИС виртуальных специализированных мультиконвейерных вычислителей, по структуре связей адекватных графу решаемой задачи, что позволяет существенно повысить реальную производительность вычислительной системы по сравнению с жёсткой архитектурой, приближая рост производительности к линейному при наращивании вычислительного ресурса.
В то же время в работе [9] отмечается, что широкое применение реконфигурируемых вычислительных систем сдерживается сложностью их программирования, требующего больших временных затрат, достигающих нескольких месяцев. При этом программы, созданные для одной архитектуры системы, необходимо существенно перерабатывать для другой архитектуры или конфигурации. Применение систем программирования, использующих синтаксис и семантику языка С для создания в ПЛИС виртуальных процессов или наложения на ПЛИС промежуточных архитектурных решений значительно снижает реальную производительность вычислительной системы. Предлагаемый в работе [9] препроцессор языка программирования высокого уровня COLAMO позволяет сократить время портации параллельно-конвейерных программ с одной конфигурации вычислительной системы на другую, но не устраняет полностью проблему сложности программирования реконфигурируемых вычислительных систем.
Кроме того, к критическим системам реального времени предъявляется требование высокой готовности, что предполагает отказоустойчивую реконфигурацию структуры ВС и оперативное восстановление работоспособности системы после сбоя. Примерами таких систем являются бортовые системы, системы слежения и управления и др. Сложность программирования реконфигурируемых вычислительных систем усложняет оперативное восстановление работоспособности вычислительной системы без существенной потери её реальной производительности. Поэтому в данной работе рассматриваются вычислительные системы с «жёсткой» архитектурой.
В то же время ВС с «жёсткой» архитектурой при наличии требования высокой готовности требуют оперативного планирования размещения подпрограмм с целью снижения коммуникационных задержек в линиях связи между процессорами для повышения реальной производительности вычислительной системы.
Математическое описание задачи размещения подпрограмм
Отдельное место занимают системы, обеспечивающие непрерывную готовность. Если система непрерывной готовности работает корректно, устраняется любое время простоя. Разработка такой системы охватывает как аппаратные средства, так и программное обеспечение и позволяет проводить модернизацию и обслуживание в режиме online. Для таких систем также требуется отсутствие деградации в случае отказа, а время их восстановления после отказа не превышает секунду.
Мультипроцессорные системы на кристалле не имеют резервных модулей, поэтому в данных системах при отказах необходимо решать задачу «миграции процессов», заключающуюся в перемещении подпрограмм отказавших модулей в исправные с помощью механизма точек восстановления, называемых также контрольными точками, с которых производится перезапуск системы. При этом в случае превышения количества подпрограмм над количеством исправных модулей часть подпрограмм необходимо передавать уже загруженным модулям в зависимости от вычислительной сложности размещённых в них подпрограмм. Данное обстоятельство приводит к деградации производительности из-за возможности увеличения времени вычислений и коммуникационной задержки, вызванной возросшими объёмами передаваемых данных между модулями. Последняя уменьшается путём планирования размещения подпрограмм. Высокая готовность необходима в критических системах управления сложными объектами, работающих в реальном времени, а также кластерных вычислительных системах.
Топологии и принципы построения многопроцессорных систем Для обеспечения высокой реальной производительности и готовности вычислительной системы важно правильно выбрать топологию и способ построения системы. Многопроцессорные вычислительные системы (МВС) существуют в различных конфигурациях и считаются идеальной схемой для повышения надежности информационно-вычислительных систем [11]. Благодаря единому представлению, неисправные узлы или компоненты МВС могут заменяться незаметно для пользователя, что обеспечивает непрерывность и безотказную работу приложений.
Многопоточные системы используются для обеспечения единого интерфейса для ряда ресурсов, которые могут со временем произвольно наращиваться (или сокращаться). Примером таких систем является группа web-серверов.
Существенное влияние на реальную производительность
вычислительной системы оказывает топология связей между процессорами. Критическим параметром, влияющим на реальную производительность, является «расстояние» между процессорами, которое выражается в количестве межпроцессорных каналов связи. Под межпроцессорным каналом связи понимается совокупность технических средств, обеспечивающих взаимодействие двух соседних процессоров: передачу данных и служебной информации. Канал обмена данными между не соседними процессорами состоит из 2 и более последовательно соединённых межпроцессорных каналов связи. Теория показывает, что система не может работать эффективно, если максимальное расстояние между процессорами больше 4 межпроцессорных каналов [11]. Одним из способов уменьшения
Топология «гиперкуб» максимального расстояния является использование топологии гиперкуба (рис. 1.1.) вместо плоской решётки, а также трёхмерного тора, «звезды», кольца (рис. 1.2) и др.
Кластерная архитектура "Fatree" процессорами является топология "толстого дерева" (fatree) (рис. 1.3). Топология "fatree" (hypertree) была предложена Лейзерсоном (Charles E. Leiserson) в 1985 году для кластерных мультикомпьютеров [12]. Процессоры локализованы в листьях дерева, в то время как внутренние узлы дерева скомпонованы во внутреннюю сеть. Поддеревья могут общаться между собой, не затрагивая более высоких уровней сети. Данная топология характерна для кластерных межсоединений на основе технологии Infiniband.
Одними из распространенных топологий, характерных для мультипроцессоров, являются матричные топологии, которые приспособлены для решения задач, характеризующихся параллелизмом независимых объектов или данных. Организация систем подобного типа, относящихся к классу MIMD (множество потоков команд – множество потоков данных), заключается в наличии ведущей ЭВМ, генерирующей поток команд, и большого числа процессорных элементов, работающих параллельно и обрабатывающих каждый свой поток данных. Таким образом, пиковая производительность системы равна сумме производительностей всех процессорных элементов. Однако на практике для достаточной эффективности системы при решении широкого спектра задач, необходимо правильно организовать связи между процессорными элементами с целью максимального использования вычислительных возможностей многопроцессорной системы.
Для построения систем, содержащих десятки процессоров используются разновидности матричных топологий, изображенные на рис. 1.4. Данные топологии упрощают наращивание размерности процессорной системы (ПС) и позволяют создавать отказоустойчивые системы [13] за счет логического исключения отказавшего модуля из пространства рабочих процессоров и заменой его резервным, или обеспечивая обход модуля без замены при отсутствии резерва.
Оценка степени уменьшения коммуникационной задержки и степени её близости к нижней оценке
Для получения худшего случая коммуникационной задержки допустим, что приведенные в таблице 1 однонаправленные обмены данными между процессорами, расположенными на разных горизонталях и вертикалях, будут проложены по указанному выше кратчайшему пути, и прибавим суммарную задержку для них к минимально возможной нс. На рис. 3.6б показан вариант субоптимального размещения, полученный с применением минимаксного показателя для оценки качества размещения, на рис. 3.6в – с применением минимаксиминного показателя.
Так как ни один из полученных вариантов не гарантирует наличия в любой паре взаимодействующих процессоров хотя бы одного кратчайшего пути, освобождённого от перекрытий, целесообразно оценивать коммуникационную задержку в полученных субоптимальных вариантах размещения по минимаксиминному показателю.
В соответствии с описанным выше получено максимальное время передачи данных для рис. 3.6б – 8400 нс для процессоров 17 – 29 и для рис. 3.6в – 4560 нс для процессоров 3 – 37.
Аналогично первоначальному размещению оценим минимально возможную суммарную задержку для кратчайших путей описанных выше пар процессоров. Кратчайшие пути между процессорами 17 и 29 лежат в пределах выделенного на рис. 3.6б блока. Из рис. 3.6б следует, что в полученном с применением минимаксного критерия варианте размещения ни один процессор из выделенного блока не остался свободным, поэтому при полносвязности обмена данными между подпрограммами для любого кратчайшего пути между процессорами 17 и 29 возможен случай максимальной степени перекрытий. Рассмотрим вариант кратчайшего пути 17-18-19-20-21-29 длиной 5. В нём существуют следующие пары процессоров, лежащие на одной горизонтали или одной вертикали: 17-18, 17-19, 17-20, 17-21, 18-19, 18-20, 18-21, 19-20, 19-21, 20-21, 21-29. Рассчитаем минимально возможную суммарную задержку при таком списке фактических перекрытий в соответствии с длинами вышеуказанных каналов передачи данных
Аналогично рис. 3.6а на рис. 3.6б показано минимальное количество перекрывающихся обменов данными на межпроцессорных каналах выделенного пути. Полученное минимально возможное значение суммарной задержки совпадает с аналогичным значением для начального размещения, поэтому размещение, полученное с применением минимаксного критерия, гарантирует уменьшение только худшего случая перекрытий кратчайших каналов передачи данных.
Кратчайшие пути между процессорами 3 и 37, для которых при имитационном моделировании получено максимальное время передачи данных, лежат в пределах выделенного на рис. 3.6в блока. Наименьшее количество загруженных процессоров – 4 – входит в кратчайшие пути 3-4-5-13-21-29-37, 3-4-12-13-21-29-37, 3-11-12-13-21-29-37, поэтому вероятность того, что данные пути окажутся наименее загруженными, наиболее высокая.
В любом из описанных выше вариантов кратчайших маршрутов занятыми являются только процессоры 3, 21, 29 и 37, из которых процессоры 21, 29 и 37 лежат на одной вертикали. Рассчитаем минимально возможную суммарную задержку между 3 и 37 процессорами с учётом длин перекрывающихся каналов 3-37, 21-29, 21-37 и 29-37 TSUM=(2461+2412+2421)10=240(6+2+2)=2400 нс. Аналогично рис. 3.6а и 3.6б, на рис. 3.6в показано минимальное количество перекрывающихся обменов данными на межпроцессорных каналах выделенного пути.
Рассчитаем худший случай перекрытий пути 3-4-5-13-21-29-37 при допущении, что все однонаправленные обмены между 3, 21, 29 и 37 процессорами будут проложены по данному пути. Тогда фактический список перекрытий данного пути будет следующим 3-21, 3-29, 3-37, 21-29, 21-37, 29-37 и TSUM=(244+245+246+2412+242)10=240(4+5+6+2+2)=4560 нс.
Оба полученных результата меньше минимально возможной суммарной задержки для пары процессоров 17-29 в варианте размещения, полученном с применением минимаксного критерия, что позволяет сделать вывод о целесообразности применения минимаксиминного критерия при планировании размещения параллельных подпрограмм в матричных мультипроцессорах. Полученные значения коммуникационной задержки приведены в таблице. Минимально и максимально возможные значения коммуникационной задержки для рис. 3. Задержка Начальное размещение Размещение поминимаксномукритерию Размещение поминимаксиминномукритерию
Данные результаты позволяют сделать вывод, что применение минимаксиминного критерия увеличивает реальную производительность на 50 % по сравнению с применением минимаксного критерия в рассматриваемой задаче.
С помощью имитационной модели выполнена оценка времени программной реализации используемых алгоритмов. Для оценки времени используется счётчик тактов, который имеется во всех современных микропроцессорах. С помощью счётчика тактов с применением привязки потока к одному ядру процессора и поднятия приоритета процесса определено количество тактов, затрачиваемое процессором на выполнение заданного фрагмента кода.
Разделение базы данных кратчайших путей на независимые части, количество которых равно количеству процессоров матричного мультипроцессора, позволяет ускорить создание базы путём параллельного построения данных частей. На примере конфигурации 88 оценено время построения одной независимой части базы данных различными микропроцессорами для матричной и матрично-тороидальной топологии (рис. 3.7). Результаты позволяют сделать вывод, что увеличение длин кратчайших каналов и количества вариантов кратчайших маршрутов увеличивает время построения базы данных и снижает коэффициент готовности системы. Поэтому увеличение размерности процессорной матрицы нецелесообразно, а при необходимости увеличения количества процессоров целесообразно формировать блоки в конфигурации 88, обрабатываемые по отдельности.
Организация блока определения промежуточных значений коммуникационной задержки
При количестве базовых блоков не более 8-ми будем использовать линейную организацию, и использовать блоки памяти размерностью 205256. Таким образом, общее количество столбцов при 2 блоках равно 512, при 4 – 1024, при 8 – 2048, следовательно, необходимо использовать 9-разрядный счётчик столбцов в первом случае, 10-разрядный во втором и 11-разрядный в третьем. В первом случае 8-й разряд счётчика подаётся на вход CS первого блока через инвертор, и на вход второго блока напрямую. Остальные разряды счётчика подаются одинаково на адресные шины CA обоих блоков. Таким образом, адресное пространство столбцов разделяется поровну между блоками.
При 4 блоках в модуль памяти вводится дешифратор типа 2-4 номеров базовых блоков, подключаемый к 8 и 9 разряду счётчика столбцов, выполняющий функцию селектора блоков посредством подачи выходных сигналов на CS-входы блоков. Аппаратная сложность дешифратора составляет 2+4=6 эквивалентных вентилей, что в миллионы раз меньше аппаратной сложности блоков и позволяет пренебречь дешифратором номеров блоков при оценке данного параметра. При этом данный дешифратор не увеличивает длину цепочки распространения сигнала, так как длина его цепочки меньше длины цепочки дешифратора 4-16, применяемого в дешифраторах блоков памяти.
При 8 блоках необходимо использовать дешифратор номеров блоков типа 3-8, подключаемый к 8-10 разрядам счётчика столбцов. Аппаратная сложность дешифратора в данном случае пренебрежимо мала по сравнению с общей сложностью памяти, а цепочка распространения сигнала так же позволяет подключать его выход к дешифраторам базовых блоков без увеличения общей длины цепочки.
При количестве блоков более 8 целесообразно организовывать базовые блоки в матрицу, каждая строка которой содержит 8 базовых блоков, что позволяет ограничиться применением дешифраторов типа 3-8 для выбора блока. В этом случае необходимо использование двух дешифраторов, сигналы которых для каждого базового блока соединяются 2-входовым элементом И, выполняющим функцию коммутатора. При этом счётчики разрядность счётчика строк увеличивается до 9-11 разрядов, а цепочка распространения сигнала увеличивается на 1 эквивалентный вентиль за счёт коммутаторов базовых блоков. Для упрощения адресации строк целесообразно использовать базовые блоки памяти 256256 во всех строках матрицы, кроме последней строки, для которой использовать необходимое и достаточное количество строк базовых блоков для хранения оставшейся части данных. В этом случае для 16 блоков будет 8 блоков 256256 (524288 ячеек) и 8 блоков 154256 (315392 ячеек). Для 32 блоков – 24 блока 256256 (1572864 ячеек) и 8 блоков 51256 (104448 ячеек). Для 64 блоков – 48 блоков 256256 (3145728 ячеек) и 8 блоков 102256 (208896 ячеек).
На основании описанного выше анализа блоков памяти определим аппаратную сложность памяти 1 для хранения приведенного количества фрагментов (таблица 4.3). При этом не будем учитывать дешифраторы адреса строки и столбца, на которые приходится менее 1 % вентилей.
Рассмотрим организацию памяти 2. В данном модуле памяти хранится поэлементное произведение матрицы обмена данными (МОД) и матрицы кратчайших расстояний (МКР), для которого 8-разрядных ячеек памяти
недостаточно. С учётом получаемых при исследовании производительности матричного мультипроцессора данных предлагается использовать 16-разрядные ячейки памяти, имеющие диапазон значений [0…65535] и организованные в матрицу 6464 в соответствии с размерностью МОД и МКР. Таким образом, для адресации памяти 2 достаточно 6 бит адресов строки и столбца. При этом следует отметить, что в режиме чтения адреса строки и столбца поступают из памяти 1 и имеют значения от 1 до 64, тогда как 6-битное адресное пространство лежит в интервале [0…63], поэтому для расшифровки адресов строк и столбцов матрицы ячеек в режиме чтения необходимо уменьшать поступающие значения на единицу. В общем виде количество ячеек памяти 2 равно Nпр2, где Nпр – количество процессоров исследуемой матричной вычислительной системы.
Для построения дешифраторов типа 6-64 адресов строки и столбца матрицы ячеек используем схему, аналогичную приложению С.12, где вместо дешифраторов типа 4-16 используются дешифраторы 3-8. При этом в случае памяти 2 нет необходимости в сигнале CS, поэтому в дешифраторе старших разрядов не используется сигнал разрешения работы, что уменьшает длину цепочки распространения сигнала и позволяет не учитывать дешифратор старших разрядов в оценке максимальной длины цепочки.
