Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,441

ON-BOARD FUNCTIONAL ORIENTED PROCESSORS BASED ON HOMOGENOUS COMPUTER ENVIRONMENT FOR MOBILE REAL-TIME SYSTEMS

Lukin N.A. 1
1 Institute of Engineering Sciences, Ural Branch of Russian Academy of Sciences
В работе описаны особенности архитектур однородных вычислительных сред как основы для создания функционально-ориентированных процессоров для систем реального времени. Излагаются основные проблемы реализации однородных вычислительных сред. Предлагаются возможные варианты оптимизации архитектур однородных функционально-ориентированных процессоров. Приводятся результаты разработки двух функционально-ориентированных процессоров с однородной архитектурой. Первый процессор основан на принципе управления вычислительным процессом «один поток команд – много потоков данных», он предназначен для обработки изображений в реальном времени на борту летательного аппарата. Второй процессор основан на принципе управления «много потоков команд – много потоков данных», он предназначен для мультиконвейерной обработки данных в реальном времени, например сигналов с выходов многоканального датчика.
This paper describes the features of the architecture of homogeneous computing environments as a basis for development a functional-oriented processors for real-time systems. The main problems of implementation of homogeneous computing environments discussed. The possible variants of the optimization of homogeneous functionally oriented processors are presented. The results of the development of two functionally-oriented processors with homogenous architecture are described. The first processor is based on the principle of management of computations «single instructions – multiple data» and is designed for image processing in real time on board the aircraft. The second processor is based on the principle of control «multiple instructions – multiple data» and design for multi-pipeline data processing in real time, for example, signals from a multichannel sensor outputs.
functional oriented processor
homogenous computer environment
very large scale integration
real-time system
1. Bogachev M.P. Arhitektura vychislitelnoj sistemy s odnorodnoj strukturoj. V kn. Odnorodnye vychislitelnye sredy (Architecture of Computer System with Homogenous Structure). Lvov. FMI AN USSR (Physics and Mechanics Institute of Ukranian Academy of Sciences). 1981.
2. Kaljaev I.A., Levin I.I., Semernikov E.A., Shmojlov V.I. Rekonfiguriruemye multikonvejernye vychislitelnye struktury (Reconfigurable Multipipeline Computer Structures). Rostov-na-Donu: Izd-vo JuNC RAN 2008 (Rostov-on-Don, Publisher South Scientific Center of Russian Academy of Sciences), 397 р.
3. Lookin N.A. Rekonfiguriruemye processornye massivy dlja sistem realnogo vremeni: arhitektury, jeffektivnost, oblasti primenenija (Reconfigurable Processing Arrays for Real-Time Systems: Architectures, Efficiency and Application). Izvestija TRTU. Tematicheskij vypusk «Intellektualnye i mnogoprocessornye sistemy». Taganrog: Izd-vo TRTU (TRTU News. Intelligent and Multiprocessor Systems. Special Issue), 2004, no. 9.
4. Prangishvili I.V., Abramova N.A., Babicheva, E.V., Ignatushhenko V.V. Mikrojelektronika i odnorodnye struktury dlja postroenija logicheskih i vychislitelnyh ustrojstv (Microelectronics and Homogenous Structures for Design of Logic and Computation Devices). M.: Nauka (Moscow, Science), 1967.
5. Slajdy k otchetnomu dokladu o vypolnenii rabot v 2000 g. po sovmestnoj programme SKIF «Razrabotka i osvoenie v serijnom proizvodstve semejstva vysokoproizvoditelnyh vychislitelnyh sistem s parallelnoj arhitekturoj (superkompjuterov) i sozdanie prikladnyh programmno-apparatnyh kompleksov na ih osnove» (Development and Production of High Performance Computer Systems with Parallel Architecture (Supercomputers) and Development of Hard-n-Soft Computer Complexes based on them) (Dogovor No VS-491 ot 09 avgusta 2000 g.) (Agreement no VS-491; 2000/08/09) http://www.botik.ru/~abram/slides06032001/00-list_of_tasks.ru.html
6. Shmojlov V.I. Pulsirujushhie informacionnye reshetki i superkompjutery klassa A (Pulsating Information Grills and Supercomputer A Class). Lvov: Merkator, 2005. 902 р.
7. Lookin N., Bersenev V. Functional-Oriented Processors And Parallel Data Processing In Integrated Navigation Systems // IP-Embedded Systems Conference, Dec. 1–3, 2009, Session «Embedded Systems».

Развитие бортовых систем управления (БСУ) подвижными объектами характеризуется наращиванием «интеллекта» систем, обусловленным необходимостью повышения точности и надежности решения основных задач; уменьшением времени цикла решения основных задач; ужесточением требований на объемно-массовые характеристики и потребляемую мощность аппаратуры.

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

Увеличение производительности бортовых вычислительных средств заключается в переходе от универсального параллелизма к специализированному [3]. Это означает, что:

1) основой архитектуры БЦВС будут являться ФОП, несущие основную вычислительную нагрузку, а универсальные процессоры будут выполнять системные функции (диспетчирование, контроль, диагностику и т.п.);

2) архитектуры и системы команд ФОП должны быть ориентированы на эффективную реализацию конкретных функций, процедур или алгоритмов.

ОВС – адаптивная технология реализации специализированного параллелизма

Для первых поколений спецпроцессоров было характерным использование полностью специализированного параллелизма, что практически сразу выявило зависимость между степенью специализации их архитектур и их программируемостью. Это представляло собой одну из основных проблем на пути создания эффективных спецпроцессоров, поэтому появились ЭВМ с реконфигурируемой архитектурой, для которых характерно смещение акцентов с программирования алгоритмов на программирование архитектур [2]. Такие ЭВМ требуют специальных подходов к программированию и создания новых языковых средств.

Другим подходом к созданию архитектур высокопроизводительных спецпроцессоров является использование однородных вычислительных сред (ОВС), которые теоретически позволяют обеспечить предельную производительность при решении конкретных вычислительных задач. Кроме того, однородные архитектуры идеальны с точки зрения использования особенностей полупроводниковой микроэлектроники. Это направление возникло в середине 1960-х годов [3], но недостаточный уровень развития технологии не позволил широко использовать ОВС для создания спецпроцессоров. В течение последних 20 лет ОВС вновь служат объектом исследований и разработок, создаются новые подходы к проектированию ОВС и систем на их основе. В ряде случаев имеются положительные результаты практической реализации ОВС [1, 6].

Проблемы реализации ОВС

Как правило, ОВС представляет собой в общем случае N-мерную решетку, в узлах которой располагаются ПЭ, при этом чаще всего каждый ПЭ соединен с другими с помощью только локальных связей. Например, наиболее распространенным случаем является двумерный массив ПЭ только с «вертикальными» и «горизонтальными» локальными связями, что дает существенную экономию числа связей и полное отсутствие их пересечений, что принципиально важно для микроэлектронной реализации [4].

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

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

В настоящее время практически все проекты ОВС реализуют два типа параллельной обработки – SIMD и MIMD. Топология большинства современных ОВС – 2D.

Для обеспечения разработки и успешного применения ОВС требуется решение целого ряда проблем. Основными из них являются:

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

? Проблемы программирования. В настоящее время большинство используемых в компьютерной практике языков программирования являются императивными (например, С). Большинство ОВС являются машинами потоков данных, и непосредственное применение таких языков затруднительно. Более предпочтительными являются функциональные языки (например, Haskell), гораздо менее разработанные. Кроме того, отсутствует теория построения компиляторов, основанных на процессах «упаковки» алгоритмических конструкций в двумерную решетку ПЭ.

? Проблемы физической реализации. Значительное число ПЭ, требуемое для реализации современных алгоритмов (порядка сотен тысяч), входит в противоречие с ограничением на число внешних контактов и потребляемой мощности современных СБИС.

Проектирование ФОП на базе ОВС

Как следует из сказанного выше, ОВС – это своего рода матрица для формирования на ее основе различных архитектур, которые могут быть как статическими, так и динамически изменяющимися. Каждая из архитектур представляет собой ФОП, предназначенный для реализации алгоритма либо класса алгоритмов. В этом смысле программируемые логические интегральные схемы (или FPGA – англ.) являются естественным средством реализации ФОП на основе ОВС (ОВС-ФОП), при этом сам проект представляет собой виртуальный специализированный процессор, существующий лишь в процессе реализации конкретного алгоритма. С другой стороны, ОВС в виде заказной СБИС (или ASIC – англ.) дает практически такие же возможности по созданию ФОП, что и FPGA. В этом состоит существо центральной идеи ОВС – совместное программирование алгоритма и архитектуры с целью обеспечения оптимума с точки зрения применения ФОП в составе СРВ.

В случае ОВС-ФОП возможные варианты оптимизации могут быть сформулированы в виде соотношений, описывающих взаимосвязи между параметрами аппаратной, временной или коммуникационной сложности вычислений в базисе схем из функциональных элементов [1], частотой переключения компонентов ПЭ (т.е. вентилей) и параметрами алгоритмов (число переменных, разрядность, арность преобразований, погрешность вычислений и т.п.).

Отметим архитектурные особенности ФОП

Для архитектуры ФОП типа SIMD – это аппаратно реализованный двумерный массив ПЭ, который потактно выполняет одну общую программу и реализует конкретный алгоритм под управлением одного потока команд. Конфигурация массива ПЭ не зависит от реализуемого алгоритма, а в большей степени определяется структурой массива обрабатываемых данных (например, геометрическими характеристиками изображения).

Для архитектуры ФОП типа MIMD – это подмножество ПЭ, соединенных локально и предварительно настроенных на реализацию конкретной операции. Конфигурация массива ПЭ в большей степени определяется реализуемым алгоритмом.

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

Практические решения в области ОВС-ФОП

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

С точки зрения использования ФОП можно выделить несколько основных уровней обработки данных в этой СРВ.

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

Уровень БЦВС. С помощью ФОП, как правило, реализуются алгоритмы, требующие порядка сотен миллионов операций в секунду при отведенных на них интервалах времени порядка сотен микросекунд. В качестве примера можно привести задачу корреляционно-экстремальной навигации летательного аппарата [7].

Уровень БЦВМ. На этом уровне ФОП реализуют более локальные преобразования. Как правило, это математические функции типа sin(Х) или ln(X), для их реализации могут быть использованы однокристальные ФОП.

Уровень ЦП. Для этого уровня ФОП – это блоки, расширяющие возможности ЦП по выполнению отдельных преобразований (умножение, деление, lukin01.wmf).

На рис. 1 приведена архитектура БЦВК, где показаны ФОП на различных уровнях обработки данных.

Таким образом, ФОП уже сейчас широко применяются на различных уровнях обработки данных в бортовых СРВ.

ОВС-ФОП с архитектурой SIMD

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

На базе совместных исследований и разработок ряда академических институтов и предприятий-разработчиков бортовых систем управления и микроэлектроники было разработано систолическое операционное устройство (СОУ) и на его основе двумерный ОВС-ФОП. На рис. 2 изображена структура одиночного ПЭ, на рис. 3 – архитектура систолического ОВС-ФОП.

В течение 1992–1994 гг. была проведена разработка заказной СБИС систолического операционного устройства (СОУ), которая представляла собой квадратную матрицу размерностью 8?8 ПЭ. Каждый ПЭ содержит битовое АЛУ, систему коммутаторов и ОЗУ емкостью 128 бит. Все ПЭ связаны между собой ортогонально. Микрофотография СБИС СОУ приведена на рис. 4, а. Для обеспечения реализации ОВС-ФОП была разработана однослойная ситалловая печатная микроплата размером 60?48 мм2, на которой размещаются 8 бескорпусных кристаллов СБИС, что позволяет иметь 512 ПЭ на одну плату. Изображение микроплаты приведено на рис. 4, б.

pic_36.wmf

Рис. 1. Архитектура БЦВК со встроенными ФОП

pic_37.tif

Рис. 2. Структура ПЭ ОВС-ФОП с архитектурой SIMD

Массив ПЭ в составе ОВС-ФОП имел размерность 128?128. Такая размерность являлась минимально необходимой для реализации базовых алгоритмов обработки 2D-изображений (оконтуривание, контрастирование, выделение особенностей) в реальном времени (цикл 10 мс). Проработки полномасштабного ОВС-ФОП показали, что для обработки видеоизображений в реальном времени достаточно 32 микроплат, что дает суммарную массу ФОП не более 150 г.

Архитектура ФОП позволяет вводить пикселы изображения в темпе поступления и обрабатывать их таким образом, чтобы завершить обработку к моменту прихода следующего кадра. Исследования возможностей двумерного систолического ФОП показали, что по сравнению с другими архитектурами он обеспечивает наивысшую скорость внутрикадровой обработки изображений. Например, оконтуривание произвольного числа протяженных изображений, попавших в плоскость датчика, занимает 9 тактов.

Уровень современной наноэлектронной технологии СБИС позволяет реализовать 2D-массив ПЭ размерностью 128?128 в одном кристалле. Это дает возможность использования СБИС ОВС-ФОП в качестве видеопроцессоров в бортовых ЦВС.

ОВС-ФОП с архитектурой MIMD

Второй архитектурной разновидностью ОВС-ФОП являются MIMD-системы. В рамках российской части проекта СКИФ [5] была проведена разработка СБИС «Minitera», архитектура которой развивает концепцию MIMD-ОВС.

Каждая СБИС содержит 25 ПЭ и работает на частоте 30 МГц, структура одного ПЭ приведена на рис. 5.

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

pic_38.tif

Рис. 3. Архитектура ОВС-ФОП (SIMD)

pic_39.tif pic_40.tif

а б

Рис. 4. а – СБИС СОУ; б – ситалловая микроплата для ОВС-ФОП

pic_41.wmf

Рис. 5. Структура ПЭ ОВС Mtera 2

Заключение

ФОП на базе ОВС представляют собой архитектуры с массовым параллелизмом обработки данных, они позволяют существенно ускорить вычисления по сравнению с большинством параллельных процессорных архитектур. К настоящему времени разработаны ОВС-ФОП с архитектурами SIMD и MIMD. Параметры архитектуры SIMD-ОВС (конфигурация и размерность массива ПЭ) связаны с особенностями структур массивов обрабатываемых данных, что делает эффективным их применение в задачах цифровой обработки изображений в бортовых системах видеонаблюдения, мониторинга и раннего предупреждения. Параметры архитектуры MIMD-ОВС связаны с особенностями информационной структуры алгоритмов. Это делает эффективным их применение для реализации алгоритмов сигнальной и видеообработки (оптические датчики различных спектральных диапазонов), сортировки больших массивов (распознавание), вычисления математических функций (БИНС), криптографии (телеметрия). Для разработки и успешного применения ОВС необходимо полномасштабное решение проблем алгоритмизации, программирования и физической реализации. После решения указанных проблем ОВС-ФОП могут эффективно применяться в качестве сопроцессоров для вычислительной техники реального времени различного назначения – от бортовых ЦВМ до встроенной электроники инерциальных датчиков.