«Бобынцев Денис Олегович Методы и средства планирования размещения параллельных подпрограмм в матричных мультипроцессорах Специальность 05.13.05 – Элементы и устройства вычислительной техники и систем управления ...»

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Приложение А

Приложение В

Приложение С

Приложение D

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

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

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

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

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

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

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

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

подзадачи:

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

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

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

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

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

реального времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объем работы. Диссертация включает введение, четыре раздела, заключение, список литературы из 85 наименований, приложения.

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

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

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

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

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

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

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

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

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

COLAMO

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

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

архитектурой.

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

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

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

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

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

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

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

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

MTBF/(MTBF+MTTR), где MTTR (Mean Time To Repair) – среднее время между моментом обнаружения неисправности и моментом рестарта системы.

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

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

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

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

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

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

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

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

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

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

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

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

процессорами является топология "толстого дерева" (fat-tree) (рис. 1.3).

Топология "fat-tree" (hypertree) была предложена Лейзерсоном (Charles E.

Leiserson) в 1985 году для кластерных мультикомпьютеров [12]. Процессоры локализованы в листьях дерева, в то время как внутренние узлы дерева скомпонованы во внутреннюю сеть. Поддеревья могут общаться между собой, не затрагивая более высоких уровней сети. Данная топология характерна для кластерных межсоединений на основе технологии Infiniband.

приспособлены для решения задач, характеризующихся параллелизмом независимых объектов или данных. Организация систем подобного типа, относящихся к классу MIMD (множество потоков команд – множество потоков данных), заключается в наличии ведущей ЭВМ, генерирующей поток команд, и большого числа процессорных элементов, работающих параллельно и обрабатывающих каждый свой поток данных. Таким образом, пиковая производительность системы равна сумме производительностей всех эффективности системы при решении широкого спектра задач, необходимо правильно организовать связи между процессорными элементами с целью многопроцессорной системы.

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

1.4. Данные топологии упрощают наращивание размерности процессорной системы (ПС) и позволяют создавать отказоустойчивые системы [13] за счет логического исключения отказавшего модуля из пространства рабочих процессоров и заменой его резервным, или обеспечивая обход модуля без замены при отсутствии резерва.

Рис. 1.4. Существующие матричные топологии систем средних и больших Система с матричной организацией может иметь двунаправленные или однонаправленные связи между процессорами (рис. 1.4 а, б, г). В матричнотороидальной ПС, рассматриваемой как суперпозиция кольцевых структур, отдельные модули отображены на двумерной решётке – матрице. Каждый из модулей связан с 4 «соседями»: слева, справа, сверху и снизу. Любой процессорный модуль идентифицируется номером соответсвующей строки и столбца. Передача данных при двунаправленной ПС (рис. 1.4а) выполняется по всем направлениям. При однонаправленной ПС, изображенной на рис.

1.4б, данные могут передаваться только слева – направо и снизу – вверх.

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

Наряду с матричными структурами, использующими только 4 связи у каждого процессора, используются гексональные структуры, в которых каждый модуль соединён с 8 модулями за счёт добавления диагональных связей к ортогональным связям (рис. 1.4в). Несмотря на рост аппаратной сложности, это позволяет уменьшить максимальное расстояние между процессорными модулями, что сокращает время передачи данных и загрузку каналов связи. Недостатком существующих разновидностей матричных структур является увеличение времени передачи данных между процессорами при увеличении размерности, так как увеличивается максимальное расстояние между процессорами, определяемое количеством последовательно соединённых межпроцессорных каналов связи (линков) для наиболее «удалённых» друг от друга процессоров. Для матричной топологии наиболее «удалёнными» друг от друга являются процессоры, расположенные в противоположных углах матрицы, максимальное расстояние равно 2 N 2, если матрица является квадратом из N процессоров, и n+m2, если матрица имеет прямоугольную структуру из n строк и m столбцов. При наличии диагональных связей между процессорами максимальное расстояние уменьшается в 2 раза по сравнению с матричной структурой, имеющей только ортогональные связи.

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

Параллельная структурная организация описанного выше матричного типа является основным способом построения сложных критических систем, работающих в реальном времени, представляющих собой мультипроцессоры матричного типа. Такой подход к организации позволяет повысить производительность системы без увеличения тактовой частоты более 1 ГГц, при умеренном энергопотреблении системы и её охлаждении, а также достичь отказоустойчивости и высокой готовности [14-16].

Особенностью матричных мультипроцессоров является усложнение процедур управления межмодульным обменом данными. Чтобы обеспечить доставку данных между двумя процессорами, требуется организовать выбор маршрута передачи. Применяемые в матричных структурах алгоритмы и средства маршрутизации позволяют строить маршруты при наличии дефектов и отказов отдельных процессоров [17-34]. При этом необходимо учитывать, что динамические алгоритмы носят локальный характер, учитывая только состояние соседних процессоров и каналов связи.

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

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

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

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

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

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

В общем виде графо-теоретические методы представляют прикладную задачу в виде ориентированного графа, вершинами которого являются подпрограммы, размещённые по вычислительным узлам, а рёбрами – связи взаимодействия, заключающаяся в оптимальной прокладке маршрутов, происходит по алгоритму минимального сечения на графе. Примером является метод последовательного размещения, применяемый при проектировании СБИС [38] и состоящий из следующих этапов:

множество вершин графа делится на 2 подобласти;

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

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

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

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

оптимального решения. Технология метода представляет задачу размещения в виде поиска на дереве решений и подробно рассмотрена в работе [41].

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

1) формулируется функция оценки (целевая функция) степени взаимодействия между процессорами;

2) формируется набор ограничений, встречающихся в различных прикладных задачах;

3) реализуется итерационный алгоритм для нахождения общего решения.

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

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

Среди приближённых методов наиболее высокой степени близости решений к оптимальному позволяют достичь итерационные методы [42-45], которые предполагают перебор различных решений и состоят из 2 этапов:

1) переход от одних решений к другим с помощью парных или групповых перестановок вершин графа взаимодействия подпрограмм;

2) сравнительная оценка решений.

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

К итерационным методам относятся генетические методы [46-48], в общем виде состоящие из следующих этапов:

формирование произвольного набора случайных вариантов размещения;

2) вычисление «функции приспособленности» для каждого варианта размещения;

3) применение к наиболее «приспособленным» вариантам генетических операторов скрещивания и мутации;

4) отбор в следующее поколение.

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

В связи с большим временем поиска, препятствующим быстрому переразмещению задач в случае отказов процессоров, в работе [41] разработан метод планирования размещения на основе итерационного метода субоптимального размещения. Метод позволяет сократить время решения задачи размещения подпрограмм за счёт допустимой потери результата в снижении коммуникационных задержек по сравнению с известными точными методами, а также за счёт аппаратной реализации определения коммуникационной задержки. Планирование размещения в соответствии с данным методом состоит в целенаправленных перестановках подпрограмм между процессорами, предшествует маршрутизации передачи данных. Цель перестановок подпрограмм – создавать необходимые возможности прокладки в топологии вычислительной системы наиболее коротких параллельных маршрутов без их перекрытия (наложения) в межпроцессорных каналах связи [49]. При этом сокращение времени планирования размещения не должно снижать качество получаемого варианта размещения подпрограмм, вызванного перекрытиями маршрутов передачи данных и возрастанием из-за этого коммуникационной задержки.

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

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

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

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

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

Комплекс взаимодействующих подпрограмм представляется в виде ориентированного графа G=, вершины x i X которого соответствуют подпрограммам, а дуги e ij E X X определяют обмены данными между ними. Процесс размещения комплекса подпрограмм выполняется в два этапа:

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

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

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

Устройство для оценки качества размещения в матричных системах в [55] реализует оценку по критерию загрузки канала между смежными модулями матричной системы. Размещаемый процесс (задача) отображается однородной средой, содержащей mn элементов однородной среды. При моделируется перестановка пары строк (столбцов) элементов однородной среды. После очередной перестановки предлагаемое устройство вычисляет значения критериев оценки и выдает указанные значения ВУУ. Последнее анализирует принятые значения и либо фиксирует полученное размещение как более оптимальное (если значения критериев улучшают ранее найденные значения), либо игнорирует его.

Рис. 1.5. Варианты размещения подпрограмм в матричной системе На рис. 1.5а и 1.5б предлагаются варианты размещения подпрограмм в матричной системе. Модули системы на рис. 1.5а и 1.5б представлены квадратами с номерами, а внутри модулей кружками обозначены вершины графа G c соответствующими номерами. Пунктирные линии обозначают связи модулей матричной системы. Из рис. 1.5а видно, что загрузка канала в модулях 4-5-6 и 7-8-9 значительно больше, чем в модулях 1-2-3. Это влияет на общее время выполнения задачи и влечет за собой его увеличение.

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

Схема устройства для оценки качества размещения в матричных системах [55] представлена на рис. 1.6.

Рис. 1.6. Устройство оценки качества размещения в матричных системах следующее.

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

Дешифратор 2 выбора строки необходим для выбора очередной строки матрицы моделируемой системы.

Мультиплексор 3 выбора элемента служит для подачи с выходов группы 10.1, 10.2,..., 10.m триггеров информации о наличии зафиксированной вершины графа в (j)-м модуле (i=1, 2,..., m, j=1, 2,..., n) матричной системы.

Дешифратор 4 зафиксированного модуля предназначен для подачи информации о загрузке канала в i-й (i=1, 2,..., m) строке j-го (j=1, 2,..., n) модуля матричной системы в соответствующий счетчик 9.i (i=1, 2,..., m) загрузки канала.

Счетчик 5 строк накапливает информацию о текущей обрабатываемой строке матрицы моделируемой системы.

моделируемой системы.

Счетчик 7 текущей строки необходим для подсчета номера текущей обрабатываемой строки матрицы моделируемой системы для обеспечения корректного накапливания информации в соответствующих счетчиках 9.i (i=1, 2,..., m) загрузки каналов.

поступление значений от элементов с первой по m-ю строк матрицы моделируемой системы на соответствующие элементы группы 12.1, 12.2,..., 12.m элементов ИЛИ соответственно.

Группа 9.1, 9.2,..., 9.m счетчиков загрузки каналов предназначена для накапливания информации о суммарной загрузке каналов в соответствующих строках матричной системы.

Группа 10.1, 10.2,..., 10.m триггеров служит для хранения информации о наличии зафиксированных вершин в модулях выбранной строки матричной системы.

Блок 11 оценки качества размещения необходим для оценки качества размещения в матричных системах.

Группа 12.1, 12.2,..., 12.m элементов ИЛИ выполняет объединение сигналов с выходов группы 8.1, 8.2,..., 8.m блоков элементов запрета.

Вход 13 запуска устройства необходим для подачи сигнала запуска генератора 1 импульсов от ВУУ.

Выходы 14.1, 14.2,..., 14.m загрузки каналов устройства предназначен для подачи на ВУУ соответствующих кодов загрузки каналов в строках МС для данного варианта размещения.

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

Устройство в работе [56] позволяет определять нижнюю оценку размещения в полносвязных матричных системах при двунаправленной передаче данных. Аналогично рассмотренным выше принципам аппаратной реализации планирования размещения подпрограмм в работе [56] используется граф взаимодействия подпрограмм G, описываемый матрицей обмена информацией (МОИ) и граф топологической модели матричной системы.

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

Сущность предлагаемой нижней оценки размещения поясняется рис.

1.7. Топологическое представление матричной системы (МС) и вершин графа взаимодействия подпрограмм аналогично рис. 1.5. Пунктирные линии обозначают связи модулей МС, а сплошные линии рядом с пунктирными – гипотетические зафиксированные дуги, правая диагональ располагается между модулями МС 2 и 4, а левая между модулями МС 1 и 2. Из фиг. 1.7а видно, что связи между модулями 1-2 и 1-3 распределены неравномерно, что увеличивает суммарное время выполнения задачи, так как модули 1 и 2 будут загружены сильнее, чем модули 4 и 3. Время выполнения задачи уменьшается за счет переназначения дуг так, как показано на фиг. 1.7б.

Такой вариант размещения одновременно считается нижней оценкой размещения для МС. Определение нижней оценки аппаратно реализовано в специальном блоке устройства [56].

Рис. 1.7. Поясняющая иллюстрация к нижней оценке размещения Аналогичный принцип работы имеет устройство поиска нижней оценки в системах с матричной организацией без диагональных связей [57].

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

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

В матрице 22.i.j (i=1, 2,…, m, j=1, 2,…, n) счетчиков фиксированных модулей хранится информация о зафиксированных вершинах графа G. На вход 23 подаётся сигнал запуска генератора 14 импульсов от ВУУ. В матрице 24.i.j (i=1, 2,…, m, j=1, 2,…, n) D-триггеров хранится информация о текущем варианте размещения. Мультиплексор 15 выбора элемента используется для подачи с выходов матрицы 24.i.j D-триггеров информации о назначенной (размещенной) вершине в (i.j)-м модуле МС. Счетчик 18 содержит номер текущего элемента матрицы смежности. Счётчики 19 и 20 управляют дешифраторами 16 и 17. Матрица 25.i.j (i=1, 2,…, m, j=1, 2, …, n) элементов И предназначена для объединения сигналов с выходов дешифратора выбора строки и дешифратора 17 выбора столбца для последующей подачи на соответствующие счетные входы матрицы 22.i.j. Матрица 26.i.j (i=1, 2, …, m, j=1, 2, …, n) выходов значений интенсивности необходима для подачи на ВУУ кодов значений интенсивности взаимодействия модулей МС. На выход 27 остановки устройства поступает информация о переполнении счетчика текущего элемента, что и является сигналом окончания работы блока 21.

Аналогичные принципы аппаратной реализации лежат в основе устройств в работах [60,61].

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

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

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

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

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

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

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

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

Глава 2. Методы и алгоритмы планирования размещения подпрограмм 2.1. Типовая структура матричных мультипроцессоров Матричный мультипроцессор, как правило, представляет собой процессор, имеющий десятки ядер в одном кристалле. Примерами таких мультипроцессоров являются процессоры Tilera [16]. Структура ядер важна с точки зрения низкоуровнего программирования, при проектировании и оптимизации приложений. Она определяет возможности процессора в плане вычислений. При этом важной задачей является распределение или передача данных между ядрами. Среда передачи данных должна обладать высокой пропускной способностью, малым временем задержки распространения данных. Пропускная способность среды передачи и её топология влияют на производительность процессора на многопоточных приложениях, определяют задержки распространения данных.

Мультипроцессор Tile64Pro является процессором общего назначения с MIMD-архитектурой [16]. Каждое ядро может работать под управлением собственной операционной системы, так и под управлением системы типа SMP Linux, соответственно, одновременно процессор может выполнять различные приложения, к примеру, обработку видеокадров, шифрование данных и обработку стека сетевых протоколов.

Процессор содержит 64 идентичные вычислительные ячейки (tile), организованные в двумерный массив 88 (рис. 2.1). Ячейка является базовым блоком процессора и состоит из комбинации коммутатора и RISC-ядра общего назначения. Каждое ядро представляет собой полноценный RISCпроцессор, работающий на частотах от 600 МГц до 1 ГГц, содержит кэши первого и второго уровней (L1, L2 cache).

Рис. 2.1. Структурная схема процессора Tile64Pro Ядро имеет все основные возможности обычного процессора, такие как:

1) полный доступ к памяти и портам ввода/ вывода;

2) виртуальная память и защита данных (MMU/TLB);

3) иерархический кэш с отдельными уровнями L1-I и L1-D;

4) многоуровневая система прерываний;

инструкции за цикл.

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

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

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

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

Задача размещения может быть представлена как выбор варианта распределения подпрограмм между процессорами (ядрами), при котором время обменов данными между подпрограммами будет минимальным.

2.2. Математическое описание задачи размещения подпрограмм При оценке оптимальности размещения подпрограмм необходимо определить методику расчёта времени передачи данных. В большинстве коммуникационных сред для передачи данных используется метод передачи пакетов, заключающийся в пересылке данных блоками (пакетами) одинакового размера. Как правило, каждый пакет содержит помимо исходных передаваемых данных некоторый набор служебных полей (заголовок пакета). В соответствии с данными обстоятельствами, в работе [66] время передачи данных tпд в паре процессорных узлов, между которыми длина маршрута равна l последовательных соединенных сетевых каналов где tн – время подготовки данных к передаче (латентность), которое является характеристикой сети, tk – время передачи одного байта данных через один сетевой канал (определяется пропускной способностью канала R, то есть tk=1/R), tc – время передачи через сетевой канал служебных данных;

длина маршрута l считается постоянной, не зависящей от объема передаваемых данных; время передачи служебных данных tc не зависит от объема m передаваемых пакетов. Для приложений с тонкой параллельной структурой (fine-grained parallelism), какими, как правило, являются вычислительные программы, важно малое значение латентности.

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

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

На основании описанного критерия задача размещения подпрограмм по процессорам формулируется в следующей математической постановке.

Множество подпрограмм описывается ориентированным графом взаимодействия I=, где AI={a1, a2, …, aNa}, |AI|=Na – множество вершин графа I, вершины ai A которого соответствуют подпрограммам, а взвешенные дуги vij VI описывают связи между подпрограммами, Na – количество подпрограмм. Весами дуг являются объёмы передаваемых данных между подпрограммами mij в байтах. Граф I представляется матрицей обмена данными (МОД): M=||mij||, i, j 1, N a.

Матричный мультипроцессор представляется топологической моделью в виде графа H=, где P={p1, p2, …, pNпр} – множество идентификаторов процессоров, VH – множество межпроцессорных связей, задаваемых матрицей смежности Q размером Nпр= nстр nст, где Nпр – количество процессоров, nстр – количество строк, nст – количество столбцов матрицы мультипроцессора, при этом NaNпр. По матрице смежности строится непосредственной связи между процессорами нет, то элемент МКР dij – минимальное топологическое расстояние между ними, вычисляемое как кратчайший путь от вершины pi до вершины pj в графе Н, длина которого равна количеству последовательно соединённых межпроцессорных каналов связи. При этом любое минимальное топологическое расстояние между работающим и неработающим процессорами условно принимается равным нулю. Множество вариантов кратчайших путей между процессорами pi и pj формирует кратчайший канал между ними.

Для анализа перекрытий маршрутов передачи данных по матрице смежности Q строится база данных кратчайших путей [69] и представляется кортежем B=, где C={c1,c2,…,ck} – множество кратчайших каналов между процессорами, W={w1,w2,…,wy} – множество вариантов кратчайших путей между процессорами, O={o1,o2,…,oy} – множество списков перекрытий кратчайших путей. Мощности данных множеств следующие: |C|=Nпр2-Nпр, |W|=|O| – число вариантов кратчайших маршрутов. При этом ci=, pн и pк – номера начального и конечного процессоров канала ci, соответственно, wi= – последовательность номеров процессоров, составляющих путь wi, di – длина i-го кратчайшего пути, oi ={q1,q2,…,qNq} – множество перекрывающимся с i-м путём, с длинами данных путей d j ( q ) d i, где Размещение в матричном мультипроцессоре комплекса подпрограмм, отображением:

где S – это номер очередной перестановки, соответствующей s-му варианту параллельных подпрограмм по процессорам должно быть таким, чтобы 1) для наибольших объёмов передаваемых данных выделялись наиболее короткие пути в топологии многопроцессорной системы;

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

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

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

2) степень перекрытия каналов будет минимизирована.

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

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

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

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

На основании описанных правил вычисления коммуникационной задержки определим критерий поиска варианта размещения. Пусть задержка между процессорами pi и pj определяется как Ts(Zt)(pi,pj)=dij(Zt)mijg, где Zt – кратчайший путь между процессорами pi и pj, g – постоянный сомножитель, обратный пропускной способности, Ts(Zt)(pi,pj) – задержка при передаче данных по Zt-му пути для размещения S. На основе Ts(Zt)(pi,pj) введём показатель f a для kt-го кратчайшего пути k-го кратчайшего канала, где nkt – количество Zt-х кратчайших путей с длинами d(Zt) d(k), перекрывающихся с kt-м кратчайшим путём. Актуальным для практики является случай, когда для любого k-го загруженного пути между любой парой процессоров из множества кратчайших путей между ними. Аналитически данное условие описывается как При рассмотрении всех кратчайших каналов имеет место матрица минимальных суммарных задержек M(T)=||mij(T)||, где mij(T)=fa(pi,pj,S,k,t) – минимальная суммарная задержка для пары процессоров pi и pj. Скорость работы вычислительной системы лимитируется худшей попарной задержкой из всех задержек mij(T), которая вычисляется как Полученная величина fb(S) является величиной задержки для размещения S.

Задача размещения формулируется как поиск такого субоптимального отображения множества A вершин графа I на множество P вершин графа H, что В соответствии с полученными соотношениями 2.3 – 2.5 предлагаемый минимаксиминный критерий поиска варианта размещения [70 – 73] описывается следующей формулой:

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

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

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

Для оценки результата используется введённое ранее понятие гипотетической нижней оценки размещения Tinf, для вычисления которой элементы МОД выстраиваются в вектор M по убыванию, а элементы МКР – в вектор D по возрастанию. Значения Tinf и степени близости задержки T* к нижней оценке вычисляются по формулам:

маршрутизации, поэтому матрица смежности процессоров является бинарной и отражает наличие или отсутствие связи между i-м и j-м процессорами.

Каждая строка матрицы кратчайших расстояний рассчитывается по матрице смежности процессоров с помощью метода поиска в ширину [74 – 76], заключающегося в просмотре уровней графа, начиная с корневой вершины, и состоящего из следующих этапов:

1. Выбирается корневая вершина – процессор, номер которого равен номеру формируемой строки матрицы кратчайших расстояний. Корневая вершина становится вершиной нулевого уровня.

2. По матрице смежности формируется список вершин следующего уровня, смежных с вершинами текущего уровня, после чего выполняется переход к вершинам следующего уровня. При этом все просматриваемые вершины помечаются номером соответствующего уровня.

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

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

Пример определения кратчайших расстояний от 1-го процессора до всех остальных процессоров для процессорной матрицы 33 приведен на рис. 2.2. На рис. 2.2а показана матрица процессоров, на рис. 2.2б – определение кратчайших расстояний до всех процессоров при условии, что процессор 1 является корневым.

Рис. 2.2. Пример определения кратчайших расстояний от процессора 1:

а) – процессорная матрица 33, б) – кратчайшие расстояния в соответствии с Описанный выше метод определения кратчайших расстояний и кратчайших путей в матричном мультипроцессоре использован в методе планирования размещения, состоящем из следующих этапов:

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

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

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

4. Начиная с элемента mij, которому соответствует max{mijdij}, столбец элемента в МОД перемещается на место другого столбца по следующему условию: dix dij, где i,j – координаты перемещаемого элемента МОД; dij – расстояние в МКР, с которым совпадает элемент МОД;

dix – расстояние в МКР, куда целесообразно переместить элемент mij МОД, i,x – координаты элемента mix на место которого перемещается в ходе перестановки элемент mij; i – номер строки в МОД и МКР, в пределах которой выполняется перестановка элементов столбцов j и x; j и x – номера переставляемых столбцов МОД с обязательной последующей перестановкой соответствующих им строк. При этом dix0, что гарантирует невозможность назначения подпрограммы в отказавший процессор.

5. После формирования нового варианта размещения по (2.4) вычисляется задержка T=fb(S) и введённая ранее степень уменьшения задержки 6. В случае увеличения значения по сравнению с предыдущим значением дальнейшие перестановки строк и столбцов выполняются на S-м варианте размещения, в противном случае S-й вариант исключается с возвратом к предыдущему варианту.

Результатом поиска варианта размещения является матрица обмена данными M*. Метод определения коммуникационной задержки состоит из следующих этапов:

1. По матрицам M и D вычисляются задержки на всех k-х кратчайших каналах без учёта перекрытий: {Ts(k)(pi,pj)}={mijdij(k)}, где при g=const величина g временно опускается.

2. Для каждого kt-го кратчайшего пути вычисляется суммарная 3. По каждому k-му каналу с идентификатором ij определяется минимальная суммарная задержка Tkmin=min{fa}.

4. Из всех {Tkmin} находится максимум, который считается величиной коммуникационной задержки: fb(S)=max{Tkmin}.

Учитывая большую вычислительную сложность задачи определения коммуникационной задержки, связанную с большим объёмом данных о кратчайших путях и их пересечениях (перекрытиях), целесообразно перенести её вычисление на аппаратный уровень. Оценка времени программной реализации определения задержки и сравнение со временем целенаправленных перестановок приводится в главе 3.

2.4. Алгоритмы планирования размещения подпрограмм коммуникационной задержки создан аппаратно-ориентированный алгоритм.

Исходными данными для определения задержки являются матрица обмена данными и формируемые программным способом матрица кратчайших расстояний и база данных кратчайших путей. Последняя хранится в виде списка записей следующего формата: [Nн,Nк][Nн1Nк1,Nн2Nк2,…,NнnNкn], где Nн и Nк – номера начального и конечного процессоров кратчайшего пути, соответственно, являющиеся идентификатором кратчайшего канала, которому соответствует данный путь; Nн1Nк1, Nн2Nк2, …, NнnNкn – список перекрытий кратчайшего пути.

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

Ввести x0 – номер корневого процессора, D=||dij|| - матрица кратчайших расстояний.

мультипроцессора.

Ввести М2=|m2i|, где m2i – кратчайшие расстояния от процессора x0 до всех процессоров.

Ввести М3=|m3i|, где m3i – номера процессоров текущего уровня.

Ввести М4=|m4i|, где m4i – номера процессоров следующего уровня.

Ввести N1 – количество рабочих процессоров Положить i=1, x0=i.

Если i=Nпр, то п. 30, иначе п.10.

Если k 1, N пр, Qik=0 и Qki=0, то i=i+1, п.10, иначе п.11.

10.

11. j 1, N пр M1j=M2j=0.

Ввести cв=0 – счётчик просмотренных вершин.

12.

Ввести cву=0 – счётчик просмотренных вершин текущего уровня.

13.

Положить xт= x0 – номер процессора – текущей вершины.

14.

Положить l=M2xт+1 – расстояние от x0 до вершин, смежных с xт.

15.

Положить j=1.

16.

Если j=Nпр, то п. 21, иначе п.18.

17.

Если ji и Qxтj=1, то п.19, иначе j=j+1, п.18.

18.

Если M2j=0, то M2j=l, добавить j в М4, иначе п.20.

19.

20.

21. M1xт=1, cв=cв+1.

Если cв=N1, то п.23, иначе п. 24.

22.

j 1, N пр Dij=M2j, M3j=M4j=0, i=i+1, п.9.

23.

cву=cву+1, ввести NM3 – количество процессоров текущего уровня.

24.

Если cву=NM3, то ввести NM4 – количество процессоров следующего 25.

уровня, п. 26, иначе п.29.

26.

27.

xт=M31, cву=0, п.15.

28.

xт= M3cву+1, п.15.

29.

Конец алгоритма.

30.

Блок-схема алгоритма приведена на рис. 2.3. Перестановочный алгоритм планирования размещения основан на алгоритме, приведенном в работе [41] и отличается способом определения коммуникационной задержки. Алгоритм записывается в виде следующей последовательности шагов:

1. Ввести M= mij 2. Ввести D= d ij 3.1. Ввести M1= m1ij 3.2. Ввести M2= m2ij 3.3. Ввести M3= m3ij 4. Переписать mij в M = mij так, что m '1 ' m ''2 '' z1 z2, где z1 и z номера элементов M.

номера элементов D.

7. Положить Т0=Тн.

9. Положить k=1.

10. Выбрать mk из M.

11. Найти из M2 элемент m2 mk, и соответствующий ему d из D.

12. Если d =1, то M 2 1, k=k+1 и перейти к п.10, иначе п.13;

13. Положить i=1.

14. Если i 64, то перейти к п. 15, иначе – п.24.

15. Если di S и di 0, то перейти к п.16, иначе i=i+1, п.14.

16. Для М выполнить i и сформировать M 1 :

17. Определить Т1. Если Т1B) где n – разрядность чисел A и B. Схема многоразрядного компаратора «>»

приведена в приложении C.6.

Определим зависимости количества эквивалентных вентилей на все части схемы. Для формирования функции Xi необходим 1 двухвходовой элемент И, 1 инвертор. Ещё один данный набор элементов участвует в формировании функции Yi, причём формирование Y0 не требуется. Поэтому зависимость количества данных вентилей от разрядности Nр определяется как (2Nр1)2=4Nр2.

В формировании функции Yi участвует также двухвходовой элемент И с инверсными входами, который представляется как 2 инвертора и двухвходовой элемент И. Таким образом, количество вентилей на данные элементы равно (Nр1)3=3Nр3.

Начиная с (Nр2)-го разряда необходимо соединять функции Yi старших разрядов двухвходовыми элементами И по ступенчатой схеме, поэтому количество вентилей данного типа равно Nр2. Начиная с (Nр1)-го разряда необходимо соединять функции Xi c результатами соединения функций Yi старших разрядов двухвходовыми элементами И, поэтому количество вентилей данного типа равно Nр1.

Результаты конъюнкций Xi и Yi старших разрядов подаются на многовходовой элемент И-НЕ с инверсными входами. Представим его как ступенчатую схему двухвходовых элементов И, вершиной которой является двухвходовой элемент И-НЕ, а сигналы на входы схемы подаются через инверторы. Тогда для её реализации необходимо Nр инверторов и Nр элементов И/И-НЕ. Таким образом, для данной схемы необходимо 2Nр эквивалентных вентилей.

В соответствии с анализом схемы многоразрядного компаратора «>»

количество эквивалентных вентилей для данного компаратора mк=4Nр2+3Nр3+Nр2+Nр1+2Nр1=11Nр9.

Наибольшая длина цепочки распространения сигнала определяется длиной цепочки получения функции Yn…Y1X0, то есть результата сравнения в самом младшем разряде. Функции Yn, …, Y1 зависят только от значений соответствующих разрядов, поэтому могут формироваться параллельно.

Цепочка прохождения сигнала в данном случае представлена двумя инверторами и двумя 2-входовыми элементами И, то есть 4 эквивалентными последовательную схему 2-входовых элементов И, количество которых равно Nр2. После этого 2-входовым элементом И выполняется конъюнкция результата с функцией Х0, затем инвертирование результата и прохождение через ступенчатую схему элементов И/И-НЕ, число ярусов которой равно На основании описанного выше максимальная длина цепочки распространения сигнала определяется следующей формулой:

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

Схема синхронного D-триггера имеет 4 элемента И-НЕ с длиной цепочки распространения сигнала в 2 вентиля, поэтому количество эквивалентных вентилей для построения синхронного регистра определяется как 6Nр, а длина цепочки распространения сигнала равна 4 вентилям.

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

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

Комбинационная схема одноразрядного сумматора приведена в приложении С.8. Схема состоит из 7 эквивалентных вентилей и 4-входового элемента ИЛИ, который представляется в виде 2-ступенчатой схемы из 3 элементов ИЛИ. Таким образом, аппаратная сложность одноразрядного сумматора равна 10 эквивалентным вентилям и имеет длину цепочки распространения сигнала 5 вентилей.

вспомогательные функции генерации и прозрачности [85]. Первая принимает единичное значение, если перенос появляется независимо от наличия или отсутствия входного переноса: gi=aibi. Функция прозрачности принимает единичное значение при наличии входного переноса: hi ai bi. Тогда сигнал переноса в старший разряд определяется следующей функцией: Pi gi hi Pi 1.

Определим функции переноса для 4 разрядов на основе функций генерации и прозрачности и значения входного переноса.

В приведенных формулах функции генерации и прозрачности целесообразно использовать ступенчатые схемы конъюнкции. При этом чем старше разряд, тем длиннее цепочка, поэтому формирование функций переноса не является полностью параллельным. Схема параллельного переноса приведена в приложении С.9. Чтобы уменьшить аппаратную сложность в случае суммирования 16-разрядных слов, целесообразно составлять блок ускоренного переноса из 4 блоков описанного типа, соединяя выход Р3 каждого блока с входом Рвх последующего блока.

Блок в приложении С.9 состоит из 19 эквивалентных вентилей, одного 3-входового, одного 4-входового и одного 5-входового элемента ИЛИ. На 3входовой элемент ИЛИ приходится 2 вентиля, 4-входовой – 3 вентиля, 5входовой – 4 вентиля. Следовательно, аппаратная сложность блока составляет 28 эквивалентных вентилей. Наибольшую длину имеет цепочка распространения сигнала функции Р3 – 5 эквивалентных вентилей до 5входового элемента ИЛИ, в котором длина цепочки составляет 3 вентиля.

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

LP=7(Nгр2)+8+5=7Nгр14+8+5=7Nгр1, где Nгр – количество групп.

Суммарная аппаратная сложность блока равна 28Nгр эквивалентных вентилей.

На основании описанного выше общая длина цепочки распространения сигнала для сумматора с цепным межгрупповым переносом равна сумме длины цепочки формирования переноса последнего разряда и длины цепочки сложность сумматора определяется mSUM=10Nр+28Nгр, где Nр – разрядность суммируемых операндов.

Для построения модулей памяти 1 и 2 целесообразно использовать быстродействием по сравнению с динамической памятью. В качестве ячеек памяти целесообразно использовать регистры, организованные в матрицу, что позволяет использовать словарную адресацию памяти, используя адресные шины – RA для адресации строк и CA для адресации столбцов.

Общая схема ячейки памяти приведена в приложении С.10а.

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

Длина цепочки распространения сигнала в регистре равна 2 вентилям, а аппаратная сложность равна 4Nр1 вентилей.

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

Данные элементы раскладываются на 3 эквивалентных вентиля. Общая аппаратная сложность коммутаторов, используемых в ячейке, равна 3Nр1+2.

Таким образом, аппаратная сложность ячейки mя=4Nр1+3Nр1+2=7Nр1+2.

Для кодирования номеров 64 процессоров так, чтобы код 11…1 не входил в диапазон, достаточно 7 разрядов, следовательно, аппаратная сложность ячейки памяти в этом случае составляет 51 вентиль.

дешифраторами адреса строки и столбца, на входы которых поступают многоразрядные двоичные адреса строк и столбцов матрицы ячеек. В памяти 2 хранится результат поэлементного произведения матрицы обмена данными и матрицы кратчайших расстояний, поступающих в акселератор. Данные матрицы имеют 64 строки и 64 столбца, поэтому для памяти 2 используется матрица 6464. Для адресации данной матрицы необходимы дешифраторы 6Для хранения 52408 байт в памяти 1 необходима матрица 205256, для её адресации требуются дешифраторы 8-256.

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

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

Для кодирования 256 столбцов необходим 8-разрядный код. Для построения дешифратора воспользуемся дешифраторами подключаемыми к разрядам адреса 0…3, и 1 дешифратором 4-16, подключаемым к разрядам 4…7, выходы которого подключаются к разрешающим входам дешифраторов младших разрядов, а на разрешающий вход подаётся сигнал CS выбора данного блока памяти. Общая схема построения дешифратора 8-256 приведена в приложении С.12а.

Определим аппаратную сложность и длину цепочки распространения сигнала дешифратора 8-256. В дешифраторе используются 5-входовые элементы И, поэтому цепочка распространения сигнала максимальной длины представлена инвертором и тремя 2-входовыми элементами И, то есть эквивалентными вентилями. В дешифраторах младших разрядов инвертирование и объединение разрядов адреса совмещается по времени с аналогичным процессом в дешифраторе старших разрядов путём подачи разрешающего сигнала из дешифратора старших разрядов на последний 2входовой элемент И (приложение С.12б). Таким образом, длина цепочки распространения сигнала дешифратора 8-256 составляет 5 вентилей. Все дешифраторы 4-16 состоят из 16 инверторов и 16 5-входовых элементов И, раскладываемых на 4 2-входовых элемента И, следовательно, их аппаратная сложность равна 80 эквивалентных вентилей. Таким образом, общая аппаратная сложность дешифратора 8-256 равна 1360 эквивалентных вентилей.

Для дешифратора 205 строк матрицы памяти 1 достаточно дешифраторов младших разрядов типа 4-16, поэтому в данном случае общая аппаратная сложность равна 1120 эквивалентных вентилей. Определим зависимость необходимого количества NDC дешифраторов 4-16 от количества строк Nстр:

дешифратора столбцов посредством замены количества строк Nстр на количество столбцов Nст. Тогда аппаратная сложность дешифратора строк или столбцов равна 80NDC.

Структурная схема памяти 256256 приведена на рис. 4.4. При необходимости ненужные строки матрицы ячеек, например, для построения блока 205256, удаляются для уменьшения аппаратной сложности памяти 1.

Определим суммарную аппаратную сложность блока и длину цепочки распространения сигнала. Запись в ячейку памяти осуществляется по фронту сигнала на входе W регистра. Данный сигнал формируется 3-входовым элементом И (2 вентиля), объединяющим сигналы дешифраторов адресов строки и столбца типа 8-256 (5 вентилей) и сигнала WR, поступающего на вход памяти. Длина цепочки распространения сигнала в регистре ячейки памяти составляет 2 вентиля. Таким образом, общая длина цепочки записи равна 9 вентилей.

Рис. 4.4. Структурная схема памяти на 256256 ячеек Для чтения данных из ячейки необходимо дождаться разрешающих информационные сигналы ячейки проходят через 4-входовые элементы И ( вентиля) и многовходовые элементы ИЛИ, в которых длина цепочки распространения сигнала равна log 2 N я вентилей, где Nя – количество ячеек, которое зависит от объёма данных, которые необходимо загрузить в память 1. Таким образом, длина цепочки распространения сигнала при чтении данных определяется следующей формулой:

Общая аппаратная сложность элементов ИЛИ, формирующих выходные сигналы памяти, равна (Nя1)Nр. Тогда общая аппаратная сложность блока памяти, состоящего из 2 дешифраторов 8-256, Nя ячеек и Nр многовходовых элементов ИЛИ определяется следующей формулой:

mRAM=mDCстр+mDCст+(7Nр1+2)Nя+(Nя1)Nр1= =mDCстр+mDCст+7Nр1Nя+2Nя+Nр1NяNр= mDCстр+mDCст+8Nр1Nя+2NяNр1;

где mDCстр – количество эквивалентных вентилей в дешифраторе строк, mDCст – количество эквивалентных вентилей в дешифраторе столбцов.

Определим аппаратную сложность блока 205256, достаточного для хранения 51 КБ данных, при 7-разрядных ячейках mRAM=8014+8017+82052567+22052567=3046313 ЭВ.

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

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

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

Таблица 4.2. Оценка требуемой ёмкости памяти Количество блоков данных 52408 байт Суммарный объём данных, байт При количестве базовых блоков не более 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 ( ячеек) и 8 блоков 154256 (315392 ячеек). Для 32 блоков – 24 блока (1572864 ячеек) и 8 блоков 51256 (104448 ячеек). Для 64 блоков – 48 блоков 256256 (3145728 ячеек) и 8 блоков 102256 (208896 ячеек).

На основании описанного выше анализа блоков памяти определим аппаратную сложность памяти 1 для хранения приведенного количества фрагментов (таблица 4.3). При этом не будем учитывать дешифраторы адреса строки и столбца, на которые приходится менее 1 % вентилей.

Таблица 4.3. Аппаратная сложность памяти Количество Количество базовых блоков Количество Рассмотрим организацию памяти 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, поэтому в дешифраторе старших разрядов не используется сигнал разрешения работы, что уменьшает длину цепочки распространения сигнала и позволяет не учитывать дешифратор старших разрядов в оценке максимальной длины цепочки.

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

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

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