ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ДЛЯ АВИОНИКИ ПЯТОГО ПОКОЛЕНИЯ
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
УДК 629.7.05
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
ДЛЯ АВИОНИКИ ПЯТОГО ПОКОЛЕНИЯ
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
Рассматриваются принципы построения бортовой цифровой вычислительной системы в классе структур интегрированной модульной авионики. Определены значимые архитектурные признаки вычислительных систем. Рассмотрены модель ресурсов вычислительной системы и трехступенчатая иерархическая веерная модель. Рассмотрен метод декомпозиции функциональных задач бортовой вычислительной системы и их назначение на доступные вычислительные ресурсы. Ключевые слова: принципы построения, бортовая вычислительная система, крейт.
Введение
Авиационные комплексы, находящиеся сегодня в эксплуатации, имеют системноориентированную детерминированную структурную организацию. Вычислительный ресурс этих комплексов регулярно распределен между информационными каналами связи посредством организации отдельных подсистем (перераспределение задач между подсистемами на системном уровне не предусматривается), что не обеспечивает достаточной и гибкой интеграции бортового оборудования. Реализуется лишь резервирование наиболее важных функций, решаемых средствами бортовой цифровой вычислительной системы (БЦВС). Кроме того, невозможна полномасштабная адекватная адаптация функциональных ресурсов БЦВС к различным ситуационным изменениям внешней обстановки. При этом возможность программного управления потоками информации (программная коммутация) в архитектурах современных БЦВС не реализуется вообще.
Для радикального повышения эффективности функционирования БЦВС разработчиками сегодня предпринимаются попытки ее реализации и проектирования в классе мультимикропроцессорных структур интегрированной модульной авионики (ИМА) с программируемой архитектурой, допускающей динамическое перераспределение вычислительной мощности аппаратуры в зависимости от приоритета решаемых задач. В связи с этим оказывается актуальной задача разработки такой вычислительной системы, организованной по типу интегрированной вычислительной среды, в которой изначально отсутствует регулярное распределение средств вычислительной техники по функциональным подсистемам и информационным каналам связи.
Иерархическая трехступенчатая веерная модель БЦВС
Открытая архитектура интегрированной модульной авионики строится по иерархическому принципу [1]: нижний уровень иерархии образуют унифицированные быстросъемные функциональные модули различного назначения, имеющие собственные вычислительные средства в компактном стандартном исполнении (европлаты с типоразмерами 3U, 6U, 9U); средний уровень иерархии образуют мультипроцессорные вычислительные системы, создаваемые из модулей нижнего уровня и конструктивно интегрированные в стандартный крейт; высший уровень иерархии представляет собой бортовую локальную вычислительную сеть, интегрирующую вычислительные средства боксов среднего уровня, на основе центрального сетевого интерфейса высокой пропускной способности.
В иерархической структуре ИМА заложен принцип присвоения более высокого ранга тем подсистемам управления и информационного обеспечения летательного аппарата (ЛА), которые в большей степени способствуют повышению эффективности использования ЛА в целом. Согласно принятой терминологии [2], схема иерархической организации БЦВС по концепции ИМА относится к классу трехступенчатых веерных структур, определяющих систему, в которой существует один привилегированный субъект (центр), который имеет возможность управлять остальными субъектами – посредниками П. Це-
левая функция центра Ц имеет вид Ц Ц rx1 ,rx2 ,...,rxk ; ry1 ,ry2 ,...,ryk , где rx1 ,rx2 ,...,rxk ресурс управле-
ния, который находится в распоряжении центра Ц (воздействие центра на посредников П1, П2, …, Пk).
Целевые функции посредников Пi имеют вид Пi Пi ryi1 ,ryi2 ,...,ryiz ; rzi1 ,rzi2 ,...,rziz , i=1, 2, …, k , где ryij
это управление Пi , его воздействие на исполнителей Иij (исполнителя номер j, подчиненного по уровню иерархии посреднику Пi).
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
21
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ...
Таким образом, интересы посредников определяются ресурсом ryi1 ,ryi2 ,...,ryiz , который находится
в их собственном распоряжении, и ресурсом rx1 ,rx2 ,...,rxk , которым распоряжается центр.
Иерархия представляет собой свойство упорядоченного множества компонентов, между которыми установлено отношение приоритета. Компоненты комплекса, между которыми отсутствует предпочтительность, образуют один иерархический уровень. Приоритет субъектов проявляется в том, что центр
назначает правила использования ресурса rx1 ,rx2 ,...,rxk , который зависит тем или иным образом от дей-
ствий посредников, от их выбора ryi1 ,ryi2 ,...,ryiz . Посредникам эти правила становятся известными в тот
момент, когда они принимают решения об использовании ryi1 ,ryi2 ,...,ryiz , тем самым центр в иерархиче-
ской системе имеет возможность (правило первого хода) направлять в нужное русло усилия элементов низшего иерархического уровня, что создает предпосылки для организации реконфигурируемых вычислительных структур.
Целевые функции исполнителей Иij Иij r ;ryij zij , i 1,2,...,k ; j 1,2,...,zi , где величины rzij
характеризуют действия исполнителей. Первый ход в трехступенчатой иерархической структуре делает
центр – он сообщает посредникам правила назначения ресурсов rx1 ,rx2 ,...,rxk в зависимости от их выбо-
ра. Следующий ход производит посредник, который сообщает правила выбора ryi1 ,ryi2 ,...,ryiz .
Модель вычислительных ресурсов БЦВС
У каждого типа ресурса ri
существует набор функций
f
f1i
,
f
i 2
,...,
f
i fi
, которые он способен
выполнять на множестве заданий Z Z1 ,Z2 ,...,Zz . Выполнение одного задания Zi требует выполне-
ния набора функций f f1 , f2 ,..., ff . При этом [3]:
– ресурс ri R считается способным к работе над заданием Zi Z , i=1, 2, …, z, если существует функция f : f f i и f f j ;
– ресурс ri R считается способным к работе над набором заданий Zi Z , i=1, 2, …, 2z, если Z jk Z j ,
где Z – множество всех подмножеств заданий Z; – совокупность ресурсов ri R считается способной к работе над заданием Zi Z , i=1, 2, …, z, если
ri R , где R – множество всех подмножеств ресурсов R; – совокупность ресурсов ri R считается способной к работе над набором Zi Z , i=1, 2, …, 2z, если
Z jk Z j ,rik ri , способный к работе над Z jk .
Распределением заданий считается назначение совокупности ri R для каждого задания Zi Z , пригодной к работе над ними, с условием, что никакие два ri rj не выполняют одну и ту же функцию f одного и того же задания Z.
Принципы построения аппаратных средств БЦВС
Детализация ИМА-структуры крейта вычислительной системы БЦВС показана на рис. 1 [4]. Приняты следующие обозначения: БР – буферный регистр, ЛОП – локальная оперативная память, ПДП – узел прямого доступа к памяти. Обмен данными между вычислителями МВi, i=1, 2, …, n, осуществляется через системный интерфейс СИ и общий модуль памяти МП. Физическую основу реализации БЦВС ИМА-структуры (см. рис. 2) составляют модули-вычислители типа МВ80, модули памяти МП80, разработанные в ФГУП «СПб ОКБ „Электроавтоматика“ им. П. А. Ефимова» и выполненные по стандарту 6U на базе отечественного микропроцессорного комплекта «Мультиборт», который отвечает требованиям стандарта высокоскоростных коммуникаций системного интерфейса SpaceWire ECSS-E-50-12A, внедренного и поддерживаемого ESA (European Space Agency), NASA (США), JAXA (Япония), CSA (Канада) и Российским космическим агентством.
Идея реализации задач комплекса на вычислителях класса МВ1, МВ2, …, МВn заключается в следующем. Каждый из МВi, i=1, 2, …, n, функционирует по своей циклограмме, задаваемой препроцессором форматирования. Препроцессор форматирования ПФi, i=1, 2, …, n, распознает данные из общего
22 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
потока к абонентам или от абонентов, предназначенные для обработки на соответствующем вычислителе МВi, i=1, 2, …, n. В каждом из вычислителей МВi, i=1, 2, …, n, помимо препроцессора форматирования, имеются вычислительный узел ВУ, блок памяти БП и, в случае децентрализованного управления обменом с системным интерфейсом СИ, процессор обмена ПО. От соответствующего препроцессора форматирования в блок обмена БО поступают данные согласно принятому на борту ЛА протоколу взаимодействия. Согласно системе классификации Флинна, такая БЦВС относится к классу многопроцессорных систем с множественным потоком команд и множественным потоком данных (MIMD).
Рис.1. Обобщенная структура многопроцессорной вычислительной системы
Рис. 2. Прототип бортовой цифровой вычислительной платформы „Крейт-6U“, разработанной в ФГУП «СПб ОКБ „Электроавтоматика“ им. П. А. Ефимова»
В архитектуре БЦВС структуры ИМА средствами модулей МВi, i=1, 2, …, n предусматриваются три типа препроцессорной обработки [4]: – форматирование с разделением каналов, когда ПФ устанавливает биективное соответствие между каналами связи с абонентами комплекса и каналами шины данных вычислителей МВi, i=1, 2, …, n; – совмещение каналов, когда соответствия между каналами обменов и каналами шины данных вычислителей МВi, i=1, 2, …, n являются произвольными (каждый с каждым, т.е. реализуется свойство отказоустойчивости – БЦВС остается работоспособной при наличии хотя бы одного исправного ресурса каждого типа);
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
23
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ...
– форматирование данных в условиях биномиального резервирования каналов обмена (при этом препроцессор форматирования устанавливает соответствие между каналами абонентов комплекса и каналами шины данных вычислителя МВi, i=1, 2, …, n с учетом введенной аппаратурной избыточности, обусловленной резервированием).
В соответствии с принятыми [4] способами препроцессорной обработки вычислители МВi, i=1, 2, …, n реализуют функции: – препроцессорной обработки Θ средствами препроцессора форматирования ПФ; – промежуточного хранения данных Ω (буферизацию), осуществляемого блоком памяти БП; – обмена I с системным интерфейсом СИ с помощью процессора ПО или вычислительного узла ВУ; – обработки Р на вычислительном узле; – управления U обменом. При централизованном управлении обменом функция U реализуется ВУ, а процессор обмена ПО отсутствует.
Соответствующие этим функциям архитектурные признаки БЦВС структуры ИМА являются наи-
более значимыми и имеют вид Θ θ1 ,θ2 ,θ3 , где θ1 – разделение, θ2 – совместное использование, θ3 –
биномиальное резервирование каналов обмена; Ω ω1 ,ω2 , где ω1 – наличие, ω2 – отсутствие буфе-
ризации данных; I = { i1, i2 }, где i1 – пословный обмен, i2 – обмен блоками слов в системном интерфейсе; P = { p1, p2, p3, p4 }, где p1 – обработка слов сразу после форматирования, p2, p3 – обработка перед буферизацией и после считывания данных из буфера обмена (блока памяти) соответственно, p4 – обработка до и после буферизации; U = { u1, u2 }, где u1 и u2 обозначают соответственно централизованное и децентрализованное управление.
Правила синтеза описаний Λ Θ j1 ,Ω j2 ,I j3 ,Pj4 ,U j5 формируются на основе известных знаний [4]
о предметной области (назначения БЦВС) и исходя из допустимых принципов сочетаний вычислительных ресурсов в заданном наборе архитектурных признаков. Подмножество разрешенных частных описаний вычислителей МВi, i=1, 2, …, n и их композиции в составе БЦВС определяется набором допустимых
сочетаний Λ1 θ1 ,ω1 ,i1 , p1 ,u1 ; Λ2 θ j ,ω1 ,i1 , p2 ,u1 , j = 1, 2, 3; Λ3 θ j ,ω1 ,i1 , p3 ,u1 , j = 1, 2, 3;
Λ4 θ j ,ω1 ,i1 , p4 ,u1 , j = 1, 2, 3; Λ5 θ j ,ω1 ,i2 , p1 ,u1 , j = 1, 2, 3; Λ6 θ j ,ω1 ,i2 , p3 ,u2 , j = 1, 2, 3;
Λ7 θ j ,ω1 ,i2 , p4 ,u2 , j = 1, 2, 3; Λ8 θ j ,ω2 ,i1 , p1 ,u1 , j = 2, 3. Сами по себе правила формирования опи-
саний не формализуют конструктивного приема порождения вариантов (проектных альтернатив) архитектуры БЦВС. Эти правила лишь допускают либо запрещают определенные комбинации архитектурных признаков базиса модулей МВi, i=1, 2, …, n. Сама же процедура синтеза связана с отображением операционной модели БЦВС на ее целевую структуру.
Отображение операционной модели БЦВС на доступные вычислительные ресурсы
Сущность метода отображения операционной модели на доступные вычислительные ресурсы заключается в следующем [5]. Пусть имеется n информационно связанных задач, которые необходимо решать с помощью крейта ИМА, и соответствующие задачам алгоритмы. Каждый алгоритм может быть представлен как некоторая последовательность функциональных операторов.
Граф, соответствующий результирующему вычислительному алгоритму, образуется следующим образом. Каждому, например, i-му функциональному оператору Фi алгоритма ставится в соответствие вершина графа νi, возле которой записывается ее вес – время выполнения данного функционального оператора в относительных единицах. Вершины νi и νj соединяются линией со стрелкой (дугой графа), направленной в νi только в том случае, если результат, полученный после выполнения νj, является одним из аргументов для νi. Всякая дуга выражает либо вычислительную зависимость между соответствующими функциональными операторами, либо требования порядка выполнения соединяемых вершин, либо то и другое. Совокупность графов n задач составляют метаграф GВС процесса решения n задач всей вычислительной системы. Так как рассматриваемые задачи информационно связаны, то и граф GВС является связным. Проектирование модели крейта ИМА состоит в выборе числа вычислителей (модулейвычислителей МВ) и в определении электрических (логических) связей между ними в соответствии с графом GВС, ограничениями (время, надежность и т.д.) и некоторым функционалом оптимальности.
Назовем вершины графа GВС, в которые входят дуги исходных данных, начальными, а вершины, из которых выходят дуги результата решения задач или фрагментов вычисления, – конечными (так, на рис. 3 вершины ν1, ν5, ν9 являются начальными, а вершины ν6, ν7, ν11 – конечными). Назовем также подграф GВСi графа GВС независимым, если ни в одну его вершину не входит дуга другого подграфа. Нетрудно видеть, что для организации вычислительного процесса необходимо разложить граф GВС на независимые подграфы GВСi. Действительно, для независимого подграфа не нужны промежуточные результаты опера-
24 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
торов, не входящих в этот подграф, и, следовательно, каждый из них можно реализовать на отдельном МВ, обменивающимся информацией по «медленному» интерфейсу. Очевидно, число задействованных вычислителей МВ будет зависеть от числа независимых подграфов. Поскольку все вычислители будут работать параллельно, время выполнения всех n задач tр при такой структуре будет минимальным, т.е. дальнейшее увеличение числа процессоров не уменьшит tр.
V13 V12
V11
V1 V2 V3
V4
V10 V5
V9 V8
V6
V7
Рис. 3. Операционная модель GBC вычислительной системы в виде многосвязного графа операций обмена и обработки информации
Рассмотрим основные положения, на которых строится алгоритм декомпозиции графа на независимые подграфы. Если существует множество вершин νi1, νi2,…, νik, из которых дуги выходят и входят в вершину νi, то это множество принадлежит независимым подграфам, в которые входит вершина νi. В то же время вершина νi будет входить в независимые подграфы, строящиеся на базе вершин, в которые входят дуги, выходящие из вершины νi.
Определим матрицу размерностью m m (m – число вершин графа), у которой элемент на пересечении i-й строки и j-го столбца равен 1, если имеется дуга, направленная от i-й вершины к j-й вершине. Если дуга имеет противоположное направление, соответствующий элемент равен –1. При отсутствии такой дуги рассматриваемый элемент определяется как 0.
На первом этапе алгоритма рассматриваются строки матрицы графа GВС с целью выявления строки, имеющей только отрицательные единицы (тем самым определяется конечная вершина). Номер вершины данной сроки будет составлять первый элемент образуемого массива Е.
На втором этапе по полученной строке определяются столбцы, которые имеют на пересечении с ней отрицательные элементы. Тем самым выявляются вершины, входящие в независимый подграф найденной конечной вершины. Номера этих вершин вводятся в массив Е.
На третьем этапе просматриваются элементы найденных выше столбцов, и отрицательные из них обнуляются. Этим исключается возможность последующего просмотра уже найденных вершин при наличии в графе контуров. Далее повторяются манипуляции второго этапа со строками, соответствующими указанным выше столбцам, и т.д. После того как исчерпаны все строки, имеющие отрицательные элементы, массив Е, образованный в результате реализации алгоритма, выводится на печать. Этот массив дает перечисление всех вершин, входящих в первый независимый подграф.
На четвертом этапе происходит подготовка к реализации следующего цикла алгоритма. С этой целью стертые ранее отрицательные элементы восстанавливаются, а полученные на первом этапе строки и соответствующие им столбцы обнуляются. Далее процедура повторяется (начиная с первого этапа).
Алгоритм прекратит реализацию, после того как все строки, имеющие только отрицательные элементы, будут исчерпаны. Если каждый независимый i-й подграф реализуется на отдельном МВ за время
l
tpi, то tp=max{ tp1, tp2,…, tpN}. Если имеются ограничения вида tpij tp , тогда l подграфов, которым j 1
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
25
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ...
принадлежит суммарное время решения, могут быть реализованы последовательно на одном бортовом вычислителе, при этом общее время tp решения n задач не увеличится. Конструктивная реализация многомашинной вычислительной системы дает оптимум по критерию минимума числа вычислителей МВ, задействованных в составе крейта БЦВС ИМА.
Применение алгоритма функционального разделения графа, показанного на рис. 3, позволяет получить три его независимых подграфа (см. рис. 4), каждый из которых соответствует своему алгоритму, исполняемому на отдельном МВ.
GBC 1
V10
V13
V1
V3 V4
V9 V8
V12
V1
GV11 BC 2
V5 V6
V3 V3
GBC 3
V13 V2
V5 V7
Рис. 4. Независимые подграфы GBC 1, GBC 2, GBC 3 многосвязного графа GВС
Заключение
В согласии с результатами работы [4] можно сделать вывод, что наиболее экономичным и предпочтительным по реализации мультипроцессорной БЦВС в условиях компромисса в пространстве состояний (|HW|, |SW|, T), где |HW| – затраты на реализацию аппаратной платформы модулей МВ, |SW| – сложность программного кода, Т – ограничение на время выполнения бортовой задачи в вычислительной системе соответствующей архитектуры Λi , является вариант многопроцессорной системы «Крейт-6U»
(см. рис. 2) с архитектурными признаками Λ3 θ1 ,ω1 ,i1 , p3 ,u1 – вычислители типа МВ80, модуль памя-
ти МП80, разработанные в ФГУП «СПб ОКБ „Электроавтоматика“ им. П.А. Ефимова» в рамках реализации концепции ИМА бортовой авионики.
Рассмотренные в работе принципы построения БЦВС в соответствии с основными положениями концепции ИМА и методика оценки сложности вычислительного алгоритма БЦВС были применены также к анализу комплектов документации бортовых комплексов (систем) К-130, СОИ-У-25-1, СОИ-У25-2, ССИ-80. Расчеты показывают, что внедрение структур ИМА на базе унифицированных конструктивно-функциональных модулей стандарта 6U с крейтово-модульным конструктивом БЦВС для решения бортовых задач указанных комплексов (систем) приводит к экономии материальных средств аппаратного обеспечения от 19% до 48%.
26 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
Литература
1. Павлов А.М. Принцип организации бортовых вычислительных систем перспективных летательных аппаратов // Мир компьютерной автоматизации. – 2001. – № 4 [Электронный ресурс]. – Режим доступа: www.mka.ru/?p=41177, открытый.
2. Моисеев Н.Н. Математические задачи системного анализа. – М.: Наука, Главная редакция физикоматематической литературы, 1981. – 488 с.
3. Ивченко В. Д., Корнеев А. А. Анализ методов распределения заданий в задачах управления коллективом роботов // Мехатроника, Автоматизация, Управление. – 2009. – № 7. – С. 36–42.
4. Топорков В. В. Модели распределенных вычислений. – М.: ФизМатЛит, 2004. – 320 с. 5. Копорский Н. С., Видин Б. В., Жаринов И. О. Организация вычислительного процесса в многома-
шинном бортовом вычислительном комплексе // Известия вузов. Приборостроение. – 2006. – Т. 49. –
№ 6. – С. 4150.
Жаринов Олег Олегович
Видин Борис Викторович Шек-Иовсепянц Рубен Ашотович
– Санкт-Петербургский государственный университет аэрокосмического
приборостроения, кандидат технических наук, доцент,
zharinov@hotbox.ru
– ФГУП «СПб ОКБ “Электроавтоматика” имени П. А. Ефимова», кандидат
технических наук, зам. главного конструктора, postmaster@elavt.spb.ru
– ФГУП «СПб ОКБ “Электроавтоматика” имени П. А. Ефимова», доктор
технических
наук,
профессор,
главный
конструктор,
postmaster@elavt.spb.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
27
УДК 629.7.05
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
ДЛЯ АВИОНИКИ ПЯТОГО ПОКОЛЕНИЯ
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
Рассматриваются принципы построения бортовой цифровой вычислительной системы в классе структур интегрированной модульной авионики. Определены значимые архитектурные признаки вычислительных систем. Рассмотрены модель ресурсов вычислительной системы и трехступенчатая иерархическая веерная модель. Рассмотрен метод декомпозиции функциональных задач бортовой вычислительной системы и их назначение на доступные вычислительные ресурсы. Ключевые слова: принципы построения, бортовая вычислительная система, крейт.
Введение
Авиационные комплексы, находящиеся сегодня в эксплуатации, имеют системноориентированную детерминированную структурную организацию. Вычислительный ресурс этих комплексов регулярно распределен между информационными каналами связи посредством организации отдельных подсистем (перераспределение задач между подсистемами на системном уровне не предусматривается), что не обеспечивает достаточной и гибкой интеграции бортового оборудования. Реализуется лишь резервирование наиболее важных функций, решаемых средствами бортовой цифровой вычислительной системы (БЦВС). Кроме того, невозможна полномасштабная адекватная адаптация функциональных ресурсов БЦВС к различным ситуационным изменениям внешней обстановки. При этом возможность программного управления потоками информации (программная коммутация) в архитектурах современных БЦВС не реализуется вообще.
Для радикального повышения эффективности функционирования БЦВС разработчиками сегодня предпринимаются попытки ее реализации и проектирования в классе мультимикропроцессорных структур интегрированной модульной авионики (ИМА) с программируемой архитектурой, допускающей динамическое перераспределение вычислительной мощности аппаратуры в зависимости от приоритета решаемых задач. В связи с этим оказывается актуальной задача разработки такой вычислительной системы, организованной по типу интегрированной вычислительной среды, в которой изначально отсутствует регулярное распределение средств вычислительной техники по функциональным подсистемам и информационным каналам связи.
Иерархическая трехступенчатая веерная модель БЦВС
Открытая архитектура интегрированной модульной авионики строится по иерархическому принципу [1]: нижний уровень иерархии образуют унифицированные быстросъемные функциональные модули различного назначения, имеющие собственные вычислительные средства в компактном стандартном исполнении (европлаты с типоразмерами 3U, 6U, 9U); средний уровень иерархии образуют мультипроцессорные вычислительные системы, создаваемые из модулей нижнего уровня и конструктивно интегрированные в стандартный крейт; высший уровень иерархии представляет собой бортовую локальную вычислительную сеть, интегрирующую вычислительные средства боксов среднего уровня, на основе центрального сетевого интерфейса высокой пропускной способности.
В иерархической структуре ИМА заложен принцип присвоения более высокого ранга тем подсистемам управления и информационного обеспечения летательного аппарата (ЛА), которые в большей степени способствуют повышению эффективности использования ЛА в целом. Согласно принятой терминологии [2], схема иерархической организации БЦВС по концепции ИМА относится к классу трехступенчатых веерных структур, определяющих систему, в которой существует один привилегированный субъект (центр), который имеет возможность управлять остальными субъектами – посредниками П. Це-
левая функция центра Ц имеет вид Ц Ц rx1 ,rx2 ,...,rxk ; ry1 ,ry2 ,...,ryk , где rx1 ,rx2 ,...,rxk ресурс управле-
ния, который находится в распоряжении центра Ц (воздействие центра на посредников П1, П2, …, Пk).
Целевые функции посредников Пi имеют вид Пi Пi ryi1 ,ryi2 ,...,ryiz ; rzi1 ,rzi2 ,...,rziz , i=1, 2, …, k , где ryij
это управление Пi , его воздействие на исполнителей Иij (исполнителя номер j, подчиненного по уровню иерархии посреднику Пi).
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
21
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ...
Таким образом, интересы посредников определяются ресурсом ryi1 ,ryi2 ,...,ryiz , который находится
в их собственном распоряжении, и ресурсом rx1 ,rx2 ,...,rxk , которым распоряжается центр.
Иерархия представляет собой свойство упорядоченного множества компонентов, между которыми установлено отношение приоритета. Компоненты комплекса, между которыми отсутствует предпочтительность, образуют один иерархический уровень. Приоритет субъектов проявляется в том, что центр
назначает правила использования ресурса rx1 ,rx2 ,...,rxk , который зависит тем или иным образом от дей-
ствий посредников, от их выбора ryi1 ,ryi2 ,...,ryiz . Посредникам эти правила становятся известными в тот
момент, когда они принимают решения об использовании ryi1 ,ryi2 ,...,ryiz , тем самым центр в иерархиче-
ской системе имеет возможность (правило первого хода) направлять в нужное русло усилия элементов низшего иерархического уровня, что создает предпосылки для организации реконфигурируемых вычислительных структур.
Целевые функции исполнителей Иij Иij r ;ryij zij , i 1,2,...,k ; j 1,2,...,zi , где величины rzij
характеризуют действия исполнителей. Первый ход в трехступенчатой иерархической структуре делает
центр – он сообщает посредникам правила назначения ресурсов rx1 ,rx2 ,...,rxk в зависимости от их выбо-
ра. Следующий ход производит посредник, который сообщает правила выбора ryi1 ,ryi2 ,...,ryiz .
Модель вычислительных ресурсов БЦВС
У каждого типа ресурса ri
существует набор функций
f
f1i
,
f
i 2
,...,
f
i fi
, которые он способен
выполнять на множестве заданий Z Z1 ,Z2 ,...,Zz . Выполнение одного задания Zi требует выполне-
ния набора функций f f1 , f2 ,..., ff . При этом [3]:
– ресурс ri R считается способным к работе над заданием Zi Z , i=1, 2, …, z, если существует функция f : f f i и f f j ;
– ресурс ri R считается способным к работе над набором заданий Zi Z , i=1, 2, …, 2z, если Z jk Z j ,
где Z – множество всех подмножеств заданий Z; – совокупность ресурсов ri R считается способной к работе над заданием Zi Z , i=1, 2, …, z, если
ri R , где R – множество всех подмножеств ресурсов R; – совокупность ресурсов ri R считается способной к работе над набором Zi Z , i=1, 2, …, 2z, если
Z jk Z j ,rik ri , способный к работе над Z jk .
Распределением заданий считается назначение совокупности ri R для каждого задания Zi Z , пригодной к работе над ними, с условием, что никакие два ri rj не выполняют одну и ту же функцию f одного и того же задания Z.
Принципы построения аппаратных средств БЦВС
Детализация ИМА-структуры крейта вычислительной системы БЦВС показана на рис. 1 [4]. Приняты следующие обозначения: БР – буферный регистр, ЛОП – локальная оперативная память, ПДП – узел прямого доступа к памяти. Обмен данными между вычислителями МВi, i=1, 2, …, n, осуществляется через системный интерфейс СИ и общий модуль памяти МП. Физическую основу реализации БЦВС ИМА-структуры (см. рис. 2) составляют модули-вычислители типа МВ80, модули памяти МП80, разработанные в ФГУП «СПб ОКБ „Электроавтоматика“ им. П. А. Ефимова» и выполненные по стандарту 6U на базе отечественного микропроцессорного комплекта «Мультиборт», который отвечает требованиям стандарта высокоскоростных коммуникаций системного интерфейса SpaceWire ECSS-E-50-12A, внедренного и поддерживаемого ESA (European Space Agency), NASA (США), JAXA (Япония), CSA (Канада) и Российским космическим агентством.
Идея реализации задач комплекса на вычислителях класса МВ1, МВ2, …, МВn заключается в следующем. Каждый из МВi, i=1, 2, …, n, функционирует по своей циклограмме, задаваемой препроцессором форматирования. Препроцессор форматирования ПФi, i=1, 2, …, n, распознает данные из общего
22 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
потока к абонентам или от абонентов, предназначенные для обработки на соответствующем вычислителе МВi, i=1, 2, …, n. В каждом из вычислителей МВi, i=1, 2, …, n, помимо препроцессора форматирования, имеются вычислительный узел ВУ, блок памяти БП и, в случае децентрализованного управления обменом с системным интерфейсом СИ, процессор обмена ПО. От соответствующего препроцессора форматирования в блок обмена БО поступают данные согласно принятому на борту ЛА протоколу взаимодействия. Согласно системе классификации Флинна, такая БЦВС относится к классу многопроцессорных систем с множественным потоком команд и множественным потоком данных (MIMD).
Рис.1. Обобщенная структура многопроцессорной вычислительной системы
Рис. 2. Прототип бортовой цифровой вычислительной платформы „Крейт-6U“, разработанной в ФГУП «СПб ОКБ „Электроавтоматика“ им. П. А. Ефимова»
В архитектуре БЦВС структуры ИМА средствами модулей МВi, i=1, 2, …, n предусматриваются три типа препроцессорной обработки [4]: – форматирование с разделением каналов, когда ПФ устанавливает биективное соответствие между каналами связи с абонентами комплекса и каналами шины данных вычислителей МВi, i=1, 2, …, n; – совмещение каналов, когда соответствия между каналами обменов и каналами шины данных вычислителей МВi, i=1, 2, …, n являются произвольными (каждый с каждым, т.е. реализуется свойство отказоустойчивости – БЦВС остается работоспособной при наличии хотя бы одного исправного ресурса каждого типа);
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
23
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ...
– форматирование данных в условиях биномиального резервирования каналов обмена (при этом препроцессор форматирования устанавливает соответствие между каналами абонентов комплекса и каналами шины данных вычислителя МВi, i=1, 2, …, n с учетом введенной аппаратурной избыточности, обусловленной резервированием).
В соответствии с принятыми [4] способами препроцессорной обработки вычислители МВi, i=1, 2, …, n реализуют функции: – препроцессорной обработки Θ средствами препроцессора форматирования ПФ; – промежуточного хранения данных Ω (буферизацию), осуществляемого блоком памяти БП; – обмена I с системным интерфейсом СИ с помощью процессора ПО или вычислительного узла ВУ; – обработки Р на вычислительном узле; – управления U обменом. При централизованном управлении обменом функция U реализуется ВУ, а процессор обмена ПО отсутствует.
Соответствующие этим функциям архитектурные признаки БЦВС структуры ИМА являются наи-
более значимыми и имеют вид Θ θ1 ,θ2 ,θ3 , где θ1 – разделение, θ2 – совместное использование, θ3 –
биномиальное резервирование каналов обмена; Ω ω1 ,ω2 , где ω1 – наличие, ω2 – отсутствие буфе-
ризации данных; I = { i1, i2 }, где i1 – пословный обмен, i2 – обмен блоками слов в системном интерфейсе; P = { p1, p2, p3, p4 }, где p1 – обработка слов сразу после форматирования, p2, p3 – обработка перед буферизацией и после считывания данных из буфера обмена (блока памяти) соответственно, p4 – обработка до и после буферизации; U = { u1, u2 }, где u1 и u2 обозначают соответственно централизованное и децентрализованное управление.
Правила синтеза описаний Λ Θ j1 ,Ω j2 ,I j3 ,Pj4 ,U j5 формируются на основе известных знаний [4]
о предметной области (назначения БЦВС) и исходя из допустимых принципов сочетаний вычислительных ресурсов в заданном наборе архитектурных признаков. Подмножество разрешенных частных описаний вычислителей МВi, i=1, 2, …, n и их композиции в составе БЦВС определяется набором допустимых
сочетаний Λ1 θ1 ,ω1 ,i1 , p1 ,u1 ; Λ2 θ j ,ω1 ,i1 , p2 ,u1 , j = 1, 2, 3; Λ3 θ j ,ω1 ,i1 , p3 ,u1 , j = 1, 2, 3;
Λ4 θ j ,ω1 ,i1 , p4 ,u1 , j = 1, 2, 3; Λ5 θ j ,ω1 ,i2 , p1 ,u1 , j = 1, 2, 3; Λ6 θ j ,ω1 ,i2 , p3 ,u2 , j = 1, 2, 3;
Λ7 θ j ,ω1 ,i2 , p4 ,u2 , j = 1, 2, 3; Λ8 θ j ,ω2 ,i1 , p1 ,u1 , j = 2, 3. Сами по себе правила формирования опи-
саний не формализуют конструктивного приема порождения вариантов (проектных альтернатив) архитектуры БЦВС. Эти правила лишь допускают либо запрещают определенные комбинации архитектурных признаков базиса модулей МВi, i=1, 2, …, n. Сама же процедура синтеза связана с отображением операционной модели БЦВС на ее целевую структуру.
Отображение операционной модели БЦВС на доступные вычислительные ресурсы
Сущность метода отображения операционной модели на доступные вычислительные ресурсы заключается в следующем [5]. Пусть имеется n информационно связанных задач, которые необходимо решать с помощью крейта ИМА, и соответствующие задачам алгоритмы. Каждый алгоритм может быть представлен как некоторая последовательность функциональных операторов.
Граф, соответствующий результирующему вычислительному алгоритму, образуется следующим образом. Каждому, например, i-му функциональному оператору Фi алгоритма ставится в соответствие вершина графа νi, возле которой записывается ее вес – время выполнения данного функционального оператора в относительных единицах. Вершины νi и νj соединяются линией со стрелкой (дугой графа), направленной в νi только в том случае, если результат, полученный после выполнения νj, является одним из аргументов для νi. Всякая дуга выражает либо вычислительную зависимость между соответствующими функциональными операторами, либо требования порядка выполнения соединяемых вершин, либо то и другое. Совокупность графов n задач составляют метаграф GВС процесса решения n задач всей вычислительной системы. Так как рассматриваемые задачи информационно связаны, то и граф GВС является связным. Проектирование модели крейта ИМА состоит в выборе числа вычислителей (модулейвычислителей МВ) и в определении электрических (логических) связей между ними в соответствии с графом GВС, ограничениями (время, надежность и т.д.) и некоторым функционалом оптимальности.
Назовем вершины графа GВС, в которые входят дуги исходных данных, начальными, а вершины, из которых выходят дуги результата решения задач или фрагментов вычисления, – конечными (так, на рис. 3 вершины ν1, ν5, ν9 являются начальными, а вершины ν6, ν7, ν11 – конечными). Назовем также подграф GВСi графа GВС независимым, если ни в одну его вершину не входит дуга другого подграфа. Нетрудно видеть, что для организации вычислительного процесса необходимо разложить граф GВС на независимые подграфы GВСi. Действительно, для независимого подграфа не нужны промежуточные результаты опера-
24 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
торов, не входящих в этот подграф, и, следовательно, каждый из них можно реализовать на отдельном МВ, обменивающимся информацией по «медленному» интерфейсу. Очевидно, число задействованных вычислителей МВ будет зависеть от числа независимых подграфов. Поскольку все вычислители будут работать параллельно, время выполнения всех n задач tр при такой структуре будет минимальным, т.е. дальнейшее увеличение числа процессоров не уменьшит tр.
V13 V12
V11
V1 V2 V3
V4
V10 V5
V9 V8
V6
V7
Рис. 3. Операционная модель GBC вычислительной системы в виде многосвязного графа операций обмена и обработки информации
Рассмотрим основные положения, на которых строится алгоритм декомпозиции графа на независимые подграфы. Если существует множество вершин νi1, νi2,…, νik, из которых дуги выходят и входят в вершину νi, то это множество принадлежит независимым подграфам, в которые входит вершина νi. В то же время вершина νi будет входить в независимые подграфы, строящиеся на базе вершин, в которые входят дуги, выходящие из вершины νi.
Определим матрицу размерностью m m (m – число вершин графа), у которой элемент на пересечении i-й строки и j-го столбца равен 1, если имеется дуга, направленная от i-й вершины к j-й вершине. Если дуга имеет противоположное направление, соответствующий элемент равен –1. При отсутствии такой дуги рассматриваемый элемент определяется как 0.
На первом этапе алгоритма рассматриваются строки матрицы графа GВС с целью выявления строки, имеющей только отрицательные единицы (тем самым определяется конечная вершина). Номер вершины данной сроки будет составлять первый элемент образуемого массива Е.
На втором этапе по полученной строке определяются столбцы, которые имеют на пересечении с ней отрицательные элементы. Тем самым выявляются вершины, входящие в независимый подграф найденной конечной вершины. Номера этих вершин вводятся в массив Е.
На третьем этапе просматриваются элементы найденных выше столбцов, и отрицательные из них обнуляются. Этим исключается возможность последующего просмотра уже найденных вершин при наличии в графе контуров. Далее повторяются манипуляции второго этапа со строками, соответствующими указанным выше столбцам, и т.д. После того как исчерпаны все строки, имеющие отрицательные элементы, массив Е, образованный в результате реализации алгоритма, выводится на печать. Этот массив дает перечисление всех вершин, входящих в первый независимый подграф.
На четвертом этапе происходит подготовка к реализации следующего цикла алгоритма. С этой целью стертые ранее отрицательные элементы восстанавливаются, а полученные на первом этапе строки и соответствующие им столбцы обнуляются. Далее процедура повторяется (начиная с первого этапа).
Алгоритм прекратит реализацию, после того как все строки, имеющие только отрицательные элементы, будут исчерпаны. Если каждый независимый i-й подграф реализуется на отдельном МВ за время
l
tpi, то tp=max{ tp1, tp2,…, tpN}. Если имеются ограничения вида tpij tp , тогда l подграфов, которым j 1
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
25
ПРИНЦИПЫ ПОСТРОЕНИЯ КРЕЙТА БОРТОВОЙ МНОГОПРОЦЕССОРНОЙ ...
принадлежит суммарное время решения, могут быть реализованы последовательно на одном бортовом вычислителе, при этом общее время tp решения n задач не увеличится. Конструктивная реализация многомашинной вычислительной системы дает оптимум по критерию минимума числа вычислителей МВ, задействованных в составе крейта БЦВС ИМА.
Применение алгоритма функционального разделения графа, показанного на рис. 3, позволяет получить три его независимых подграфа (см. рис. 4), каждый из которых соответствует своему алгоритму, исполняемому на отдельном МВ.
GBC 1
V10
V13
V1
V3 V4
V9 V8
V12
V1
GV11 BC 2
V5 V6
V3 V3
GBC 3
V13 V2
V5 V7
Рис. 4. Независимые подграфы GBC 1, GBC 2, GBC 3 многосвязного графа GВС
Заключение
В согласии с результатами работы [4] можно сделать вывод, что наиболее экономичным и предпочтительным по реализации мультипроцессорной БЦВС в условиях компромисса в пространстве состояний (|HW|, |SW|, T), где |HW| – затраты на реализацию аппаратной платформы модулей МВ, |SW| – сложность программного кода, Т – ограничение на время выполнения бортовой задачи в вычислительной системе соответствующей архитектуры Λi , является вариант многопроцессорной системы «Крейт-6U»
(см. рис. 2) с архитектурными признаками Λ3 θ1 ,ω1 ,i1 , p3 ,u1 – вычислители типа МВ80, модуль памя-
ти МП80, разработанные в ФГУП «СПб ОКБ „Электроавтоматика“ им. П.А. Ефимова» в рамках реализации концепции ИМА бортовой авионики.
Рассмотренные в работе принципы построения БЦВС в соответствии с основными положениями концепции ИМА и методика оценки сложности вычислительного алгоритма БЦВС были применены также к анализу комплектов документации бортовых комплексов (систем) К-130, СОИ-У-25-1, СОИ-У25-2, ССИ-80. Расчеты показывают, что внедрение структур ИМА на базе унифицированных конструктивно-функциональных модулей стандарта 6U с крейтово-модульным конструктивом БЦВС для решения бортовых задач указанных комплексов (систем) приводит к экономии материальных средств аппаратного обеспечения от 19% до 48%.
26 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)
О.О. Жаринов, Б.В. Видин, Р.А. Шек-Иовсепянц
Литература
1. Павлов А.М. Принцип организации бортовых вычислительных систем перспективных летательных аппаратов // Мир компьютерной автоматизации. – 2001. – № 4 [Электронный ресурс]. – Режим доступа: www.mka.ru/?p=41177, открытый.
2. Моисеев Н.Н. Математические задачи системного анализа. – М.: Наука, Главная редакция физикоматематической литературы, 1981. – 488 с.
3. Ивченко В. Д., Корнеев А. А. Анализ методов распределения заданий в задачах управления коллективом роботов // Мехатроника, Автоматизация, Управление. – 2009. – № 7. – С. 36–42.
4. Топорков В. В. Модели распределенных вычислений. – М.: ФизМатЛит, 2004. – 320 с. 5. Копорский Н. С., Видин Б. В., Жаринов И. О. Организация вычислительного процесса в многома-
шинном бортовом вычислительном комплексе // Известия вузов. Приборостроение. – 2006. – Т. 49. –
№ 6. – С. 4150.
Жаринов Олег Олегович
Видин Борис Викторович Шек-Иовсепянц Рубен Ашотович
– Санкт-Петербургский государственный университет аэрокосмического
приборостроения, кандидат технических наук, доцент,
zharinov@hotbox.ru
– ФГУП «СПб ОКБ “Электроавтоматика” имени П. А. Ефимова», кандидат
технических наук, зам. главного конструктора, postmaster@elavt.spb.ru
– ФГУП «СПб ОКБ “Электроавтоматика” имени П. А. Ефимова», доктор
технических
наук,
профессор,
главный
конструктор,
postmaster@elavt.spb.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)
27