Содержание к диссертации
Введение
1 Методы отображения алгоритмов на архитектуру многопроцессорных вычислительных систем 14
1.1 Архитектура вычислительных систем и методы распараллеливания последовательных алгоритмов 14
1.2 Анализ коммутационных структур для многопроцессорных систем 22
1.3 Многопроцессорные вычислительные системы со структурно-процедурной организацией вычислений 27
1.4 Отображение параллельных алгоритмов с использованием ПЛИС-технологии 32
1.5 Принципы отображения параллельных алгоритмов на архитектуру системы 37
1.5.1 Описание архитектуры МВС СПРВ 40
1.5.2 Описание структурно-реализуемого фрагмента алгоритма 44
1.6 Выводы 48
2 Методы и алгоритмы реализации графов кадров на МВС со структурно-процедурной реализацией вычислений 49.
2.1 Методы и алгоритмы упорядочивания и выбора вершин для размещения при реализации информационного графа кадра на МВС с ортогональной коммутационной структурой 49 -
2.2 Методы и алгоритмы одновременного размещения вершин и трассировки информационных каналов при реализации информационного графа кадра на МВС с ортогональной коммутационной структурой 59
2.2.1 Методы и алгоритмы размещения вершин 59
2.2.2 Графовый метод трассировки информационных каналов 72
2.2.3 Схемный метод трассировки информационных каналов 80
2.3 Методы и алгоритмы реализации графа задачи на МВС с произвольной коммутационной структурой 83
2.3.1 Метод группировки размещаемых вершин информационного графа кадра 84
2.3.2 Методы выбора размещаемой вершины информационного графа
кадра 87
2.3.3 Обобщенный алгоритм отображения информационного графа кадра на архитектуру МБ С 99
2.3.4 Алгоритм трассировки информационных каналов между секциями МВС с произвольной коммутационной структурой 104
2.4 Выводы 108
3 Методы и алгоритмы распределения памяти при реализации многокадровых задач на МВС со структурно-процедурной реализацией вычислений 109
3.1 Методы размещения информационных вершин 109
3.2 Методы и алгоритмы реализации многокадровой задачи на МВС с ортогональной системой коммутации и фиксированными секциями памяти 114
3.3 Методы и алгоритмы реализации многокадровой задачи на МВС с произвольной системой коммутации и произвольно заданными секциями памяти 123
3.3.1 Обобщенные методы группировки и выбора размещаемых вершин информационного графа кадра 123
3.3.2 Обобщенный метод и алгоритм отображения многокадровой задачи на архитектуру МВС СПРВ 129
3.4 Выводы 135
4 Программная реализация алгоритмов для МВС с программируемой архитектурой и структурно-процедурной реализацией вычислений 136
4.1 Описание функции транслятора, реализующей алгоритмы отображения информационных графов на МВС с программируемой архитектурой 136
4.2 Примеры задач, реализованных на МВС с различными типами коммутационных структур 140
4.2.1 Задача быстрого преобразования Фурье 140
4.2.2 Задача решения уравнения Пуассона 144
4.2.3 Многокадровая задача 149
4.3 Анализ эффективности средств отображения информационных графов
на МВС с программируемой архитектурой для различных типов коммутационных систем 152
4.4 Выводы 156
Заключение 157
Список использованных источников
- Анализ коммутационных структур для многопроцессорных систем
- Методы и алгоритмы одновременного размещения вершин и трассировки информационных каналов при реализации информационного графа кадра на МВС с ортогональной коммутационной структурой
- Методы и алгоритмы реализации многокадровой задачи на МВС с ортогональной системой коммутации и фиксированными секциями памяти
- Примеры задач, реализованных на МВС с различными типами коммутационных структур
Введение к работе
з ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Современные научно-технические проблемы и задачи в различных областях требуют для своего решения все более быстродействующие' вычислительные средства. Быстродействие последовательных ЭВМ обычно ограничено и недостаточно' для эффективного решения вычислительных задач, требующих больших объемов вычислений. Поэтому в течение нескольких десятилетий в России и за рубежом активно развиваются технологии создания высокопроизводительных многопроцессорных вычислительных систем и разнообразных методов параллельного программирования, позволяющих максимально использовать возможности архитектуры системы для наиболее эффективного решения задач. Однако при решении реальных задач на существующих многопроцессорных системах производительность оказывается существенно ниже пиковой. Это объясняется тем, что при отображении параллельного алгоритма на архитектуру традиционных многопроцессорных вычислительных систем (МВС) возникают накладные расходы на организацию параллельного вычислительного процесса.
Данная проблема может быть решена с помощью создания специализированных вычислительных устройств, структура которых адекватна структуре решаемой задачи, вследствие чего достигается наибольшая производительность при реализации сложных алгоритмов. Однако создание парка специализированных вычислителей для решения задач различных классов чрезвычайно дорого.
Альтернативным подходом, позволяющим решить эту проблему, является создание многопроцессорных вычислительных систем с программируемой архитектурой и структурно-процедурной реализацией вычислений (МВС СПРВ), которые позволяют достичь высокой реальной производительности при решении различных задач путем формирования в рамках своей архитектуры виртуальных специализированных вычислителей со структурой, адекватной структуре решаемой задачи или ее фрагмента. При решении задач на МВС СПРВ параллельный алгоритм представляется в виде информационного графа, который в свою очередь разбивается на взаимосвязанные фрагменты (подграфы), каждый из которых должен быть структурно реализован на архитектуре МВС СПРВ. Для этого создается структурно-процедурная программа, с помощью которой выполняется отображение подграфов на аппаратный ресурс МВС СПРВ и которая представляет собой процедуру последовательного вызова структурно реализуемых фрагментов.
Одним из основных этапов создания эффективных структурно-процедурньгх программ является отображение параллельного алгоритма на архитектуру МВС СПРВ. Отображение параллельного алгоритма на архитектуру МВС СПРВ не является сложной проблемой, когда коммутационная структура МВС СПРВ является полнодоступной. Однако создание таких полнодоступных коммутаторов требует больших аппаратных затрат, поэтому на практике при проектировании многопроцессорных систем используются, как правило, ограниченные коммутационные структуры.
До настоящего времени создание структурно-процедурных программ осуществлялось с помощью эвристических методов отображения, что требовало привлечения высококвалифицированных специалистов и больших временных затрат. Существующие методы и средства, выполняющие отображение алгоритмов на архитектуру вычислительных систем, например такие как система Viva (фирмы Star Bridge Systems), различные САПР для разработки ПЛИС, не могут быть использованы для отображения взаимосвязанных структурно-реализуемых подграфов задачи на архитектуру МВС СПРВ, поскольку ориентированы на обработку алгоритма, представляющего собой единственный фрагмент, в то время как структурно-процедурный алгоритм представляется в виде упорядоченного множества структурнс~.реализуемых подграфов задачи.
ЗЯЙЙ
В связи с этим необходимо создание новых методов и средств, которые обеспечат автомати
зированное отображение взаимосвязанных структурно-реализуемых подграфов задачи на архитек
туру МВС, а также позволят реализовать созданную сціуівдонигйШЦНіШіїши іцюгоамму на раз
личных конфигурациях МВС СПРВ с ограниченной комі^ й-_Ыяалкнж* Г
Цель работы и задачи исследования. Целью диссертации является сокращение времени создания параллельных структурно-процедурных программ для МВС СПРВ с ограниченной коммутационной структурой за счет создания методов и средств автоматического отображения взаимосвязанных фрагментов информационного графа задачи на архитектуру системы.
Для достижения поставленной цели в работе решены следующие задачи:
исследованы коммутационные системы МВС и принципы отображения параллельных алгоритмов на архитектуру системы;
разработаны принципы отображения информационного графа задачи на архитектуру МВС СПРВ с ограниченной коммутационной структурой;
разработаны методы отображения операционных вершин структурно-реализуемого подграфа информационного графа на вычислительные устройства МВС СПРВ;
разработаны методы распределения секций памяти при отображении взаимосвязанных структурно-реализуемых подграфов информационного графа на МВС СПРВ;
разработан алгоритм отображения взаимосвязанных структурно-реализуемых подграфов на архитектуру МВС СПРВ с различными типами коммутационных структур;
создана программа автоматического отображения взаимосвязанных подграфов информационного графа на МВС СПРВ с произвольной коммутационной структурой;
проведен анализ эффективности разработанных методов и алгоритмов.
Методы исследования. При проведении исследований и решении поставленных задач были использованы элементы теории вычислительных систем, теория графов, теория множеств, реляционное исчисление.
Научная новизна диссертации состоит в том, что в ней разработаны:
- новые методы и алгоритмы автоматического отображения на архитектуру МВС
СПРВ множества взаимосвязанных структурно-реализуемых подграфов информационного
графа;
методы и алгоритмы отображения информационного подграфа на МВС СПРВ с различными типами коммутационных структур, отличающиеся от известных совмещением процесса размещения вершин и трассировки информационных каналов;
методы и алгоритмы распределения памяти при отображении множества взаимосвязанных информационных подграфов на МВС СПРВ для различных типов коммутационных структур, обеспечивающие в отличие от известных более плотное размещение вершин подграфов на аппаратном ресурсе МВС СПРВ.
Достоверность и обоснованность полученных в работе результатов подтверждается полнотой и корректностью исходных посылок, теоретическим обоснованием, непротиворечивостью математических выкладок. Исследования и эксперименты проведены на действующих образцах МВС СПРВ различной конфигурации. Получено свидетельство о регистрации программ для ЭВМ.
Научная и практическая ценность работы. Разработанные в диссертации методы и алгоритмы позволяют существенно сократить время разработки структурно-процедурных программ для МВС СПРВ с ограниченной коммутационной структурой за счет алгоритмизации и автоматизации процедуры отображения информационного графа задачи на архитектуру системы, а также обеспечить их переносимость на МВС СПРВ различных конфигураций.
Применение разработанных методов обеспечивает возможность минимизации аппаратных затрат на создание коммутационных структур на МВС СПРВ в процессе их синтеза.
Разработанное программное средство отображения информационного графа алгоритма на МВС СПРВ позволит существенно снизить требования к квалификации программиста и тем самым уменьшить стоимость создания структурно-процедурных программ для МВС СПРВ.
Реализация и внедрение результатов работы. Материалы диссертации использованы при проведении ряда госбюджетных и хоздоговорных НИОКР, выполняемых в Научно-исследовательском институте многопроцессорных вычислительных систем Таганрогского государ-
ственното радиотехнического университета (НИИ МВС ТРТУ). Предложенные методы внедрены в НИИ МВС ТРТУ, г.Таганрог, Южном научном центре Российской академии наук (ЮНЦ РАН), г. Ростов-на-Дону, Московском институте электронной техники, г. Москва, в/ч 26165, г.Москва.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:
на международной научно-технической конференции "СуперЭВМ и многопроцессорные вычислительные системы", г. Таганрог, 2002 г.;
на всероссийских научных конференциях "Методы и средства обработки информации", г. Москва, 2003, 2005 гг.;
на 9-й всероссийской межвузовской научно-технической конференции студентов и аспирантов "Микроэлектроника и информатика - 2002", г. Москва;
на международных научно-технических конференциях "Искусственный интеллект. Интеллектуальные и многопроцессорные системы", пос. Дивноморское, 2003, 2005 гг., пос. Кацивели, 2002,2004 гг.;
на республиканских научно-практических конференциях "Информационные и телекоммуникационные системы: сетевые технологии", г. Махачкала, 2003,2005 гг.;
на научной международной школе "Высокопроизводительные вычислительные системы (ВПВС) - 2004", пос. Кацивели, Украина, 2004;
на всероссийской научно-технической конференции "Параллельные вычисления в задачах математической физики", г. Ростов-на-Дону, 2004.
Основные положения и результаты, выдвигаемые на зашиту:
новые методы автоматического отображения множества взаимосвязанных структурно-реализуемых подграфов информационного графа задачи на МВС СПРВ для различных типов ограниченных коммутационных структур, основанные на совмещении процессов размещения вершин и трассировки информационных каналов;
совмещение процессов размещения вершин и трассировки информационных каналов при отображении информационных графов позволяет повысить плотность размещения структурно-реализуемых подграфов на аппаратном ресурсе МВС СПРВ;
новый метод распределения памяти при отображении информационных графов, состоящих из множества взаимосвязанных структурно-реализуемых подграфов, на МВС СПРВ для различных типов коммутационных структур, основанный на принципе формирования клик информационных подграфов;
программа автоматического отображения информационных подграфов параллельных алгоритмов на МВС СПРВ для различных типов коммутационных структур.
Личный вклад автора. Все научные и практические результаты получены автором лично.
Публикации. По теме диссертации опубликовано 16 печатных работ, из них: 5 статей, 10 тезисов и материалов докладов на российских и международных научно-технических конференциях, 1 свидетельство о регистрации программ для ЭВМ.
Структура и обьем работы. Диссертация состоит из введения, четырех глав с выводами, заключения, списка использованных источников из 94 наименований и приложений. Диссертация содержит 214 страниц печатного текста, из которых 165 страниц основного текста, 49 страниц приложений и 72 рисунка.
Анализ коммутационных структур для многопроцессорных систем
Технология SCI оптимизирована для работы с динамическим трафиком. На основе этой технологии построены компьютеры серии hpcLine от Siemens или модульные серверы NUMA-Q от IBM [28], кластерные системы SCALI Computer.
Недостатками SCI является то, что стандарт ориентирован на динамический трафик, имеет достаточно сложный протокол управления трафиком, требует наличие развитого программного обеспечения. Технология Memory Channel [12, 29], разработанная фирмой DEC, предназначена для создания эффективных вычислительных систем. В каждом модуле имеется адаптер, соединенный с коммутатором, выполняющим соединения «точка-точка» или «точка — всем точкам». Передачи через Memory Channel программируются как доступ в память.
При доступе к удаленной памяти Memory Channel поддерживает идею передачи данных между процессами, минуя операционную систему, что позволяет сократить задержку, которая возникает в высокоскоростных сетях при передаче данных. При использовании Memory Channel организуется виртуальная память, которая физически размещена в других модулях и к которой регламентирован доступ.
Memory Channel обладает следующими недостатками: - технология ориентирована на создание кластерных систем; - коммутаторы Memory Channel имеют ограничения, препятствующие масштабируемости сети; - протокол передачи данных сложен.
Технология Fast Ethernet (100BaseT) [30] является расширением стандарта Ethernet (lOBaseT) и обладает достоинствами, позволяющими перейти к скоростным сетям, сохраняя преемственность: - обеспечивает пропускную способность сегмента сети до 100 Мб/с; - обеспечивает метод случайного доступа Ethernet; - сохраняет топологию «звезда» и поддержку традиционных сред передачи данных, которая осуществляется по протоколу CSMA/CD (Carrier Sense Multiple Access/Collision Detection).
В последнее время технология Fast Ethernet широко используется при создании вычислительных кластеров благодаря дешевизне и относительно большой скорости.
В то же время технологии Fast Ethernet присущ ряд недостатков: - мощности Fast Ethernet недостаточно для создания универсальных вычислительных систем, применяемых для решения задач, требующих больших объемов вычислений, и задач, ориентированных на интенсивные межпроцессорные обмены; - возникновение больших задержек при коэффициенте использования среды выше 40-50% по причине применения алгоритма CSMA/CD; - отсутствие поддержки приоритетного трафика для приложений реального времени; - технология ориентирована преимущественно на создание кластеров.
Технология Gigabit Ethernet [31] является дальнейшим развитием стандартов для сетей Ethernet с пропускной способностью 10 и 100 Мбит/с, резко повышая скорость передачи данных. В основе Gigabit Ethernet лежит схема передачи без установления соединения, а пакеты могут быть переменной длины. Проект стандарта технологии Gigabit Ethernet описывает типы физических сред, в которых она может функционировать, например, 1000Base-CX —соединения оборудования внутри кластеров.
Технологии Gigabit Ethernet присущи следующие недостатки. Gigabit Ethernet не гарантирует устойчивую работу приложений, которые требуют высокой степени синхронизации. В Gigabit Ethernet отсутствует встроенная поддержка качества услуг (QOS). По аналогии со своими предшественниками Gigabit Ethernet предполагает конкуренцию при доступе к передаче данных, не гарантируя QOS. Для обеспечения качества услуг можно использовать протоколы на базе IP, которые позволят резервировать ресурсы маршрутизаторов для обеспечения адекватной скорости передачи. Однако такой подход неприемлем в случае, когда объемы передаваемого в среде трафика велики, а характеристики различны. Технология Gigabit Ethernet не обеспечивает резервирование пропускной способности канала для приложений реального времени.
Спецификация InfiniBand [32] является совместной разработкой компаний Compaq, IBM, HP, Dell, Sun и Intel и была принята в 2000 году. InfiniBand предусматривает скорость передачи до 30 Гбит/с и время задержки до 10 мкс.
Коммутатор InfiniBand Topspin 360, являющийся уникальной разработкой фирмы Topspin Communications, наряду с установкой связи между узлами кластера позволяет изменить контекст конфигурации кластерной сети «на лету». Для коммутатора разработано управляющее программное обеспечение, а также пакет библиотек с интерфейсом прикладного программирования, предоставляющий возможность разработчикам управлять конфигурацией кластерной сети, включая функции управления в свои программы, то есть прикладная программа, в зависимости от набора приложений и объема вычислений может менять конфигурацию сети и кластерных узлов.
Наряду с вышеперечисленными достоинствами технологии InfiniBand присущи и недостатки, включая сложность, ограничения по расстоянию, отсутствие готовых продуктов. InfiniBand реализует последовательный обмен, недостатком которого при использовании механизма предварительного соединения является большое время задержки — следствие непроизводительных затрат протокола.
Альтернативой InfiniBand на сегодняшний день также является технология Myrinet [12, 32], разработанная в рамках проектов Caltech Submicron Systems Architecture Project и Caltech Project и USC Information Sciences Institute ATOMIC project, финансируемых ARPA министерства обороны США.
Технология Myrinet [33], впервые предложенная в 1994 году, на сегодняшний день получила широкое распространение. В основу Myrinet положено использование многопортовых коммутаторов при ограниченных несколькими метрами длинах связей узлов с портами коммутатора.
Коммуникационная среда, созданная на основе Myrinet, образуется адаптерами «шина компьютера — л инк сети» и коммутаторами линков сети, стандартизует формат пакета, способ адресации вычислительных модулей, набор управляющих символов протокола передачи пакетов, и не предъявляет никаких требований к адаптеру, кроме реализации протокола.
Методы и алгоритмы одновременного размещения вершин и трассировки информационных каналов при реализации информационного графа кадра на МВС с ортогональной коммутационной структурой
Рассмотрим процедуру размещения операционных вершин графа кадра в секциях макропроцессора базового модуля и трассировки информационных каналов. Размещение вершин, как правило, производится таким образом, чтобы суммарная длина предполагаемых трасс, которые впоследствии будут созданы, была бы минимальна. На рисунке 2.14 а) и рисунке 2.14 б) показаны результаты вычисления суммарных длин трасс для различных секций МВС СПРВ.
Будем считать, что для всех секций МВС СПРВ величина задержки при транзитной передаче данных постоянна и равна S. Тогда при попытке размещения вершины в секции МАР5 и MAPI 1 суммарные длины трасс каждой из данных секций с секциями, содержащими ранее размещенные предшественники/последователи размещаемой вершины, вычисляются так, показано в таблице 2.1.
Однако на практике в ряде случаев формируемая трасса может иметь не предполагаемую длину, а существенно большую. Кроме того, некоторые трассы вообще не будут созданы по причине отсутствия свободных входов/выходов в секциях, через которые должна пройти трасса.
Ситуацию, когда невозможно создать трассу, иллюстрируют рисунок 2.15 и рисунок 2.16. На рисунке 2.15 приведен информационный граф кадра, который необходимо отобразить на архитектуру МВС СПРВ.
На рисунке 2.16 приведен промежуточный результат отображения графа кадра на архитектуру МВС СПРВ. Тупиковая ситуация возникла при попытке разместить вершину 61 в секцию МАР4. Для вершины 61 в момент ее размещения существуют ранее размещенные предшественники — 58 и 59, а так же размещенный последователь — вершина 62.
Невозможно сформировать трассу между вершинами 61 и 62, не заблокировав дальнейшее формирование трасс для ранее размещенных вершин. Но если вершину 61 разместить в секцию МАР5, то все трассы рассматриваемого примера будут созданы успешно.
Безусловно, если какую-либо из трасс не удастся создать, то дальнейшее решение задачи трассировки и общей задачи отображения графа кадра окажется невозможным. Принимая во внимание возможность таких ситуаций, размещение вершины предлагается совместить с трассировкой информационных каналов, соответствующих связям вершины с ранее размещенными вершинами.
Для описания размещения вершин формализуем отношение Set(x, sj, которое ставит в соответствие имени вершины информационного графа кадра х имя секции s базового модуля. Очевидно, что процесс размещения вершин завершается формированием отношения Setfx, s)y где s — секция, в которой вершина х размещена.
Пусть функцией Vertex выбрана операционная вершина х графа обрабатываемого кадра cdr (не нарушая общности, будем полагать, что размещение информационных вершин в секциях макропамяти известно). Для проверки условия возможности создания всех трасс для каждой размещаемой вершины х формируется множество предшественников/последователей Qx по следующему правилу:
Для выбора секции s, удовлетворяющей этому критерию, необходимо вычислить сумму длин трасс для каждой секции макропроцессора базового модуля, предполагая, что х будет размещена в ней, т.е. сформировать отношение Sum по следующему правилу: Sum={ s, sum(sx, sy, qx, qy) \ Cell(s, sx, sy)ACell(qs, qx, qy)A ASet(q, qs)AQx(q,_,J}, (2.10) где qs - имя секции, в которой размещена вершина q, являющаяся предшественником/последователем вершины х; sx и sy - номера секции s по координатам х и у, соответственно; qx и qy - номера секции qs по координатам хиу, соответственно; sum - функция вычисления суммарной длины трасс секции s.
Суммарная длина кратчайших трасс рассчитывается с учетом топологии базового модуля. В рассматриваемой архитектуре МВС СПРВ топология базового модуля представляет собой цилиндр: информационные связи замкнуты вдоль оси X. Длина соединения между двумя секциями постоянна и равна двум дискретам. Длина соединения внутри секции так же постоянна и равна единице. На рисунке 2.17 приведен пример, для которого необходимо вычислить суммарную длину трасс.
Методы и алгоритмы реализации многокадровой задачи на МВС с ортогональной системой коммутации и фиксированными секциями памяти
На основе принципов, сформулированных в главе 1, и методов размещения информационных вершин разрабатываются методы и алгоритмы, позволяющие реализовать многокадровую задачу на МВС СПРВ с ортогональной системой коммутаций и фиксированными секциями памяти. Прежде, чем рассматривать методы и алгоритмы, поясним, что такое фиксированные секции памяти.
Секции памяти, расположенные в строго определенном порядке и не меняющиеся от задачи к задаче, называются фиксированными. Схема расположения секций памяти для ортогональной системы коммутации приведена на рисунке 3.4. Секции памяти ММ0-ММ7, выделенные серым цветом, расположены в крайних столбцах.
Поиск первой размещаемой вершины выполняется следующим образом. Для каждой вершины графа обрабатываемого кадра необходимо вычислить степень связности путем суммирования количества предшественников и количества последователей вершины, и сформировать множество TRD (Тор Relation Degree), элементами которого являются пары t, rd , где t - имя вершины, ard- степень связности.
Далее из множества TRD нужно выбрать вершины с максимальной степенью связности и сформировать множество MRD (Maximum Relation Degree). Для этого множество TRD необходимо преобразовать в кортеж TupletTRD по правилу (2.12) и найти максимальный элемент кортежа по аналогии с правилом (2.14).
Множество MRD формируется по правилу MRD={mrd Cadrfcdr, C)AC(mrd,_ _,_,_}ATRD(mrd, т)л /\Max(TupletTRD, т,_)}, (3.3) где mrd - имя вершины; т - максимальная степень связности.
Множество MRD может содержать несколько вершин с максимальной степенью связности, поэтому необходимо выбрать такую вершину, которая принадлежит минимальному количеству графов кадров. Следует учитывать, что вершина будет размещена первой, но, поскольку ни один из предшественников/последователей вершины не размещен, невозможно определить секцию, в которую размещение вершины на данном шаге алгоритма будет наилучшим. Так же нельзя гарантировать, что размещение вершины не
окажется неудачным и в дальнейшем не повлияет на отображение других вершин обрабатываемого кадра и всех последующих кадров.
Для каждой вершины из множества MRD определяется количество кадров и формируется множество TCN (Top Cadrs Number), элементами которого являются пары t, tc , где t — имя вершины, a tc — количество кадров, графам которых принадлежит вершина L Для поиска вершины, принадлежащей минимальному количеству графов кадров нужно из множества TCN выбрать вершины с минимальным значением tc и сформировать множество MCN (Minimum Cadrs Number). Для этого множество TCN необходимо преобразовать в кортеж TupletTCN по правилу (2.12) и найти максимальный элемент кортежа по аналогии с правилом (2.14). Множество MCN формируется по правилу MCN={mcn MRD(mcn,jATCN(mcn, т)лМах(ТирШТСИ, m,J), (3.4) где men — имя вершины; m — минимальное количество кадров. В случае, когда среди вершин информационного графа отображаемого кадра существуют размещенные вершины, выбор вершины для размещения происходит следующим образом. Для обрабатываемого кадра cdr формируется множество размещенных вершин CFr(Cadr Placed Tops) CPT={cpt I Cadr(cdr, C)AC(cptt _t_,jASet(cpt,J}, (3.5) где cpt — имя вершины. Далее формируется множество неразмещенных вершин FCT (Free Cadr Tops) графа кадра, для которых существует хотя бы один размещенный предшественник/последователь FCT={fct Cadr(cdr, C)AC(fct,_,_,_,S)A %et(fct,jA A(S(v, J\tfarget(fct, T)AT(v}_,J)ASet(V,J}, (3.6) где fct — имя вершины графа кадра; v — имя предшественника/последователя вершины fct.
Из множества FCT необходимо выбрать такие вершины, которые имеют максимальное количество размещенных предшественников/последователей и которые должны быть размещены в первую очередь, сформировав множество MaxR Т (Maximum Relatives Tops), которое содержит имена вершин, имеющих максимальное количество размещенных предшественников/последователей.
Для этого множество FCT необходимо преобразовать в кортеж TupleFCT по правилу (2,12) и найти максимальный элемент кортежа по аналогии с правилом (2.14). Множество MaxR Т формируется по правилу MaxRT={mrt \ FCT(mrt)APRN(mrt, msf)AMax(TupletFCT, msf,J}, (3.7) где mrt — имя вершины графа кадра; msf - максимальное количество . размещенных предшественников/последователей.
Множество MaxRT может содержать более одного элемента и необходимо выбрать такие вершины, которые принадлежат минимальному количеству кадров, так как чем большему количеству кадров принадлежит вершина, тем более трудоемка операция ее переразмещения, если впоследствии окажется, что размещение неудачно.
Из множества MaxRT нужно выбрать вершины с минимальным количеством номеров кадров и сформировать множество вершин для размещения STS (Search Top Set). Для этого необходимо в кортеже TupletTCN найти минимальный элемент. Мноржество STS формируется по правилу
Примеры задач, реализованных на МВС с различными типами коммутационных структур
Аналогично обобщенному алгоритму отображения информационного графа задачи на архитектуру МВС СПРВ, который рассматривался в главе 2, необходимо сформировать множество макровершин СМ, в которые можно добавить вершины первого или второго приоритета согласно правилу (2.48).
Если множество СМ пустое, то в графе обрабатываемого кадра не содержится размещенных вершин, и необходимо выбрать первую размещаемую вершину. Алгоритм выбора первой размещаемой вершины рассмотрен ранее.
Для размещения вершины может быть выбрана любая секция МВС СПРВ, соответствующая типу вершины и удовлетворяющая условиям, сформулированным в главе 1.
Если же множество СМ не пустое, то в графе обрабатываемого кадра содержатся размещенные вершины и необходимо сформировать множество вершин для размещения APL согласно (3.13). Множество APL содержит вершины, для которых существует, по крайней мере, один размещенный предшественник/последователь.
Обработка макровершин множества СМ выполняется аналогично методу, разработанному в главе 2. Из множества СМ необходимо выбрать макровершину т, для которой затем найти неразмещенную вершину первого или второго приоритета. Если вершина найдена, то она добавляется в макровершину и выполняется процедура трассировки, после чего макровершина т исключается из множества СМ, если является закрытой. Если вершина не найдена, макровершина т удаляется из множества СМ. Процесс продолжается до тех пор, пока множество СМ не станет пустым. Если из множества СМ удалены все макровершины, то нужно искать вершину третьего приоритета.
После размещения вершины третьего приоритета снова формируется множество СМ, и процесс поиска вершин первого или второго приоритета, процедура трассировки и размещения вершин повторяется. Если размещение ни в одну из секций выполнить не удается, совершается откат и переразмещение ранее размещенных вершин.
Пусть с помощью функций поиска выбрана размещаемая вершина х и секция для размещения s. Для размещаемой вершины х графа обрабатываемого кадра cdr необходимо сформировать множество размещенных предшественников/последователей PLR согласно (2.49). Для трасс, которые будут соединять секцию s с секциями, в которых размещены предшественники/последователи вершины х, нужно рассчитать длины и сформировать отношение TL согласно (2.50). Далее из множества TL необходимо выбрать кортежи, содержащие максимальные длины трасс, из которых сформировать множество MTL согласно (2.51). После того, как множество MTL сформировано, нужно выбрать кортеж, характеризующий трассу, которая впоследствии будет создана, и выполнить трассировку информационного канала.
В случае удачной трассировки выбранный кортеж параметров удаляется из множества TL. Если множество TL не пустое, снова формируется множество MTL, в противном случае все трассы для вершины х сформированы. Пара х, cdr и добавляется в кортеж размещенных вершин Z. Указатели iz и cz инкрементируются.
Далее, по аналогии с методом реализации многокадровой задачи на МВС СПРВ с ортогональной системой коммутации и фиксированными секциями памяти, вершина х должна быть размещена в одном из свободных элементов секции s. Поэтому для секции s согласно (3.1) необходимо сформировать множество свободных элементов ELF, из которого случайным образом выбрать элемент el, в котором разместится вершина х, а затем проверить, не является ли вершина информационной. Если вершина х — информационная, то в канале el необходимо сократить объем свободной памяти на величину, соответствующую объему данных вершины.
Для размещенной вершины х необходимо сформировать множество неразмещенных предшественников/последователей FR согласно (2.52), которым дополнить множество размещаемых вершин APL.
Из множества вершин для размещения APL вершину х необходимо удалить и добавить в множество макровершин СМ макровершину, содержащую вершину х.
Когда трассировка неудачна, последовательность действий полностью аналогична действиям метода реализации графа задачи на МВС СПРВ с произвольной системой коммутации, рассмотренного в главе 2.
Если результатами функций поиска размещаемой вершины являются нулевые значения, нужно переразместить ранее размещенных вершин. Процесс переразмещения практически полностью аналогичен процессу переразмещения, который реализован в методе отображения графа задачи на МВС СПРВ с произвольной системой коммутации, разработанном в главе 2.
Однако действия при переразмещении ранее размещенных вершин, выполняемые при реализации многокадровой задачи на МВС СПРВ с произвольной системой коммутаций и произвольно заданными секциями памяти, необходимо расширить. Элемент секции, которому была назначена переразмещаемая вершина, должен быть освобожден. Если переразмещаемая вершина - информационная, то в секции, в которой она была размещена, необходимо освободить занимаемый ею канал и изменить объем свободной памяти в канале, увеличив на величину, соответствующую объему данных вершины.
Вершина х принимает значение переразмещаемой вершины и размещается снова, а обрабатываемым кадром становится кадр, при обработке которого была размещена вершина х.
Если все вершины графа обрабатываемого кадра размещены, то есть множество вершин для размещения APL пустое, то выбирается следующий обрабатываемый кадр, при условии, что он существует. Если обработаны все кадры многокадровой задачи, то алгоритм завершает свою работу.
