автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Асинхронная организация вычислений в многопроцессорных вычислительных системах

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

ЛП МАИ

6 од

ДЬК 1996

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

БУЯНОВ Сергей Васильевич

УДК 681.324

АСИНХРОННАЯ ОРГАНИЗАЦИЯ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Специальность 05.13.13 - "Вычислительные машины, комплексы, системы и сети"

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1996

Работа выполнена на кафедре вычислительных машин, систем и сетей с культета систем управления, информатики и электроэнергетики летательных ап ратов Московского государственного авиационного института (технического унив ситета)

Научный руководитель: доктор технических наук,

профессор Г.Т.Артамонов

Официальные оппоненты: доктор технических наук,

профессор Г.Н. Валаев доктор физико-математических наук, профессор А.С.Марков

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

Защита состоится "_"_1996г. в _час._мин. на заседа»

диссертационного совета Д053.18.02 при Московском государственном авиаци ном институте (техническом университете) по адресу: 125871, г. Москва, Волокол; ское шоссе, д.4.

Отзыв на автореферат в двух экземплярах, заверенных печатью, просим сылать по адресу: 125871, ГСП, г. Москва, Волоколамское шоссе, д.4, Ученый Сое ученому секретарю диссертационного совета Д053.18.02

Автореферат разослан "_"_1996г.

Ученый секретарь

диссертационного совета, у/

кандидат технических наук, доцент / Ю.В.Горбатов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

В последнее время все большее распространение пслучзют распределенные вычислительные системы с массовым параллелизмом (МРР-системы). Главной проблемой паралельных вычислений является проблема синхронизации вычислительных процессов внутри системы. В многопроцессорных вычислительных системах принципиально возможны три вида синхронизации: "жесткая", глобальная синхронизация, самосинхронизация^ частности по потоку данных) и асинхронные вычисления. Первый вид - это глобальная синхронизация (синхронизация с внешним синхрогенератором). В этом случае обмен информации между процессорными элементами (ПЭ) системы возможен только в строго определенные моменты времени, которые задаются синхрогенетратором или системным контроллером. Этот способ оправдывает себя при сравнительно • небольшом числе ПЭ или в узкоспециализированных (систолических) сетях ПЭ. Существенным недостатком таких систем является неудовлетворительная наращиваемость или расширяемость. Частично эта проблема решается использованием самосинхронизации по потоку данных (или запросов). В этом случае обмен информации между ПЭ осуществляется по мере готовности данных. Если нужных данных нет, то ПЭ находится в состоянии ожидания.

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

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

Н

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

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

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

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

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

- проведено исследование временных задержек в асинхронных сетях ПЭ, которое позволило получить предельные оценки временных параметров асинхронной сети ПЭ;

- сделан анализ дополнительных временных задержек, возникающих в асинхронных конвейерах;

- исследовано изменение области устойчивости системы управления при введении асинхронных вычислений;

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

- разработана методика определения влияния асинхронности на качестве управления системы управления, путем определения индекса изменения качества системы управления;

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

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

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

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

1) метод асинхронной организации вычислений в сетях ПЭ, работающих в реальном времени;

2) метод определения задержек в асинхронных сетях ПЭ;

3) метод определения устойчивости асинхронных систем управления;

4) метод оценки влияния асинхронности на качество управления;

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались на шести научно-технических конференциях и семинарах:

III Российско-китайский семинар. Красноярск,1994.

Межвузовская научно-техническая конференция ДНДС-95. Чебоксары, 1995.

Международный научно-технический семинар "Проблемы передачи и обработки информации в информационно-вычислительных сетях." Рязань, 1995.

Всероссийская научно-техническая конференция "Вычислительные системы бортового базирования -95", Москва, 1995.

Научно-техническая конференция "Высокопроизводительные

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

Международный научно-технический семинар "Современные технологии в задачах управления и обработки информации", Алушта, 1996.

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

Структура диссертации. Диссертация состоит из 4 глав, введения, заключения и 6 приложений, содержание которых изложено на 135 страницах, содержит 20 рисунков, 9 таблиц, список литературы на 75 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

систолических матричных процессоров и вычислительных машин самосинхронизацией (управление по потоку данных).

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

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

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

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

Месте?/, г.р'.".',сисяиг; могут бить итерационный алгоритмы ¿дотационного, агрегатного и тактического уровня управления ЛА. Кроме того, целесообразно отдать предпочтение асинхронным связям между уровнями иерархической бортовой вычислительной системы (ВВС) перед самосинхронизацией.

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

Каждый ПЭ имеет:

множество входных коммуникационных буферов ИХ]-,

множество выходных буферов

логическую схему, осуществляющую преобразование входных данных в выходные ЯУ|=р!(КХ|), которое осуществляется за время к|.

Сеть ПЭ описывается:

матрицей связей С всех выходных буферов сети со всеми входными: С:(ЯУ->НХ).

матрицей связей всех входных буферов сети со всеми выходными буферами: 0:(Г*Х->ргУ).

Вводится ¿-функция:

есда в мзмгнт граени t ПЭ сшеет данн>е если в марант гремм* 1 Ю не снимает гонньв

Таким образом, состояние входных и выходных буферов в произвольный момент времени I определяется системой уравнений:

п п

геад +1) = £ & № + код + £ <5 а + 1>»о*гес(и

н з-1

п п

гага +1) = £ й (ъ +1>0(* щ № ^ +1)) + £ й К + ^н^код

н 1-1

где С| - матрица связей выходов \-го ПЭ с входными регистрами сети; О, -матрица связей входов Ко ПЭ с выходными регистрами сети; Н) - матрицы, содержащие один ненулевой элемент индексами^), который равен единице.

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

Рассматривается как детерминированная,так и недетерминировання модель вычислений.

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

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

При самосинхронизации по потоку данных максимальная задержке формирования результата в цепи п ПЭ (конвейере) оценивается путе!^ суммирования времен счета ПЭ, входящих в конвейер.

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

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

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

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

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

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

Дан анализ временных задержек, возникающих в последовательной цепи ПЭ. Пусть асинхронный конвейер состоит из п ПЭ (ступеней). Время работы ¡-й ступени составляют k¡ тактов. Поскольку каждая ступень работает независимо, то можно говорить об уникальном времени каждой ступени. Работа конвейера в общем случае может быть описана следующими уравнениями работы ступеней:

х, (k1(tl +1)) = (х(k,* t,))

х2 (k,(t, + 1) ) = К,(х,(кг» t,))

x„..<k„..<t„., + 1)) = F^íx^dc,.,* t„_,))

_y(k„(tn+l)) = F„(x„ - l(k„* t„)

где F¡(X|(k*t¡)) - функция преобразования входных данных ¡-ступени (в общег; случае нелинейная). t¡=0,1,2,... - номер цикла обработки ¡-ступени. За счет того, что 1< - разные, то в произвольный момент времени t каждый ПЭ будет иметь свое значение t¡.

На основе формулы согласования времен

»п.,=г-(к„*1п-{кпИл)тос) к„.,)-1 Кп-1

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

п-1 п-1

y<k„(t + 1)) = F„(F„.,. ..(F2(F,(x(k„»t - - Z^ít) >>>•••>

i-i i-i

где

1-1 n-l

au|t) = (k„»t - 2 kn-) " 2 ai-)-"(t> )raod k"-i

3-1 j-¡

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

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

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

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

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

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

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

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

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

Уравнения работы асинхронной вычислительной системы приводятся к матричному виду:

Хк=М-Хк.,+Ьик, ик=0, Ук.

Это уравнение полностью описывает свободное движение асинхронной линейной дискретной системы. Переменная состояния Z объединяет входные и выходне буферы системы

Z(t)= (RY(t) RX(t))7

Матрица перехода от текущего состояния к последующему F(t) зависит от времени t.

Gyv.( t) MGxy( t) + Gw(t) G^itJMG^ftA

G,y(t) Gxx(t) J

где

G,y(t) = Y. <?l!t + 1)Ci

G (t) = £ <?,(t + 1) L,

)■>

GyJt) = £ <*jlt + 1)DJ l-i

G ,,.(t) = ^ i,(t + 1) Hj J-i

Для детерминированных асинхронных вычислений изменения матрицы носят циклический характер ввиду того, что каждая компонента имеет свой цикл счета. Это обстоятельство позволяет свести итерационный процесс с изменяемой матрицей к эквивалентному по устойчивости итерационному процессу с постоянной матрицей. Вся система в целом будет иметь глобальный цикл изменения матрицы F(t) на временном промежутке Т, где Т-наименьшее общее кратное дискретных времен счета всех ПЭ.

Можно ввести матрицу Н такую, что при рассмотрении свободногс движения данной системы в укрупненном масштабе времени обнаружится, чтс матрица перехода Н из текущего состояния Z(Tm) в последующее Z(T(m+l)) не зависит от времени,и уравнение [1] можно записать в виде:

Z(T(m+1))= Н Z(Tm)

На основе исследования свойств матриц F сформулированы достаточные условия для определения устойчивости асинхронных дискретных линейных систем Приведены модели оценки качества управления с асинхронными вычислениями

F(t + 1) =

1 5

Асинхронные вычисления в общем случае могут понизить качество управления, если при проектировании СУ использовались стандартные методы, ориентированные на синхронное вычисления. Поэтому необходимо уметь оценить качество СУ для различных способов организации вычислений. Для оценки влияния асинхронности вычислений рассмотривались две системы —образцовая и асинхронная. С работой образцовой системы (например с синхронной) свяжем интегральный критерий качества и (см. стр.13). Асинхронной системе будет соответствовать критерий Т.

Значение критерия J' по величине может оказаться больше, чем значение критерия J.Различие величин J и .Г покажет влияние дополнительных задержек на функционирование системы.

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

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

Предлагается методика для определения индекса изменения качества. Проведены исследование влияния асинхронных вычислений в стандартных звеньях при типовых входных воздействиях. Проведенные исследования свидетельствуют о том, что подавляющем большинстве случаев асинхронные вычислительные системы по сравнению с синхронными обеспечивают более высокое качество управления (тср=1,5) . В остальных случаях, в окресности равенства дискретных периодов счета ПЭ, возможо снижение качества, которое не превосходит 35%.

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

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

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

Число транспьютеров в модуле определяется характеристиками алгоритме решения функциональных задач (ФЗ).

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

При использовании асинхронных вычислений загрузка ФЗ должна реша' задачу "загрузки рюкзака" в более сложных условиях нескольких "рюкзако (транспьютеров) и нескольких параметров загрузки. В один транспьютер мож» загрузить несколько ФЗ, если суммарный объем памяти, требуемый ФЗ, I превосходит памяти транспьютера, а максимальное время счета по комплексу ФЗ I превосходит заданных ограничений. Требования по надежности и живучести мог учитываться при загрузке коэффицентами резервирования каждой ФЗ. При эте необходимо исключить попадание более одной копии одной ФЗ в один транспьюте Специализация аппаратных и программных средств транспьютерного моду, приводит к тому, что некоторые ФЗ жестко привязываются к определеннь транспьютерам, т.е. данная ФЗ должен быть размещена только в данж транспьютере.

Созданы средства загрузки программ функциональных задач с разньн периодами реализации для организации трех различных режимов рабо операционной системы транспьютера: пакетный режим, с разделением времен!' одинаковым квантом времени, выделяемым каждой ФЗ и режим с разделени времени с настраиваемым квантом времени.

Пакетный режим требует равенства периодов обработки ФЗ. Однозначн порядок выполнения приводит к тому, что первыми формируют свои результаты задачи, которые предшествуют остальным по очереди. При пакетной обрабо"

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

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

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

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

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

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

Качество загрузки дополнительно проверяется вычислением запаздываний выходных сигналов по отношению к входным для всго комплекса ФЗ. Поэтому в состав САПР входят средства и программы определения задержек в многопроцессорной вычислительной сети.

Функциональные задачи объединяются в полетное задание. В графе полетного задания анализируются все пути прохождения данных с целью

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

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

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

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

Проведенные испытания полетов по машругам подтверждают ранее сделанный теоретический вывод, что асинхронные вычисления могут обеспечить лучшее качество навигации (согласно интегральному критерию), чем самосйнхронизирующиеся. При небольшом уменьшении периода счета задач навигационно-пилотажного комплекса (на 20%) качество навигации заметно повышается (около 10%), при существенном увеличении периода счета задач (на 40%) качество навигации ухудшается несущественно (порядка 2-3%). Эти выводы создают базу для внедрения асинхронных алгоритмов в системы управления повижными объектами, работающими в реальном масштабе времени.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

1) Проведены классификация и анализ возможных методов синхронизации вычислительных систем реального времени и определено место асинхронных вычислений в БВС;

2) Раэаработана методика анализа временных параметров многопроцессорной асинхронной системы;

3) Предложены и доказаны условия устойчивости асинхронных дискретных

систем;

4) Разаработана методика оценки влияния асинхронности на качество уравпения;

5) Разработано программное обеспечение системы автоматизированного проектирования транспьютерной бортовой вычислительной системы;

6) Результаты диссертации внедрены в практику научно-исследовательских работ и учебного процесса в Московском Государственном авиационном институте (Техническом университете).

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

ПУБЛИКАЦИИ

1. Артамонов Г.Т. Буянов C.B. Климовец E.H. Программный инструментарий для проектирования вычислительной среды перспективного летательного аппарата. // Отчет о НИР: Структура бортового вычислительного комплекса с элементами

искусственного интеллекта перспективного летательного аппарата. Этап 66.- М., МАИ, 1993. с.30-71.

2. Артамонов Г.Т.,Буянов C.B. Концепция построения многоуровневой системы управления перспективным летательным аппаратом.//Материалы III Российско-Китайского семинара. Теэ.докл. Красноярск, 1994.

3. Артамонов Г.Т.,Буянов C.B. Асинхронные вычисления в управляющих многопроцессорных системах реального времени.// Материалы межвузовской научно-технической конференции ДНДС-95, Чебоксары, ЧГУ, 1995.

4. Артамонов Г.Т.,Буянов C.B. Асинхронная обработка информации в информационно-вычислительных сетях.// Материалы международного научно-технического семинара "Проблемы передачи и обработки информации в информационно-вычислительных сетях.", Рязань, РГРТА, 1995.

5. Артамонов Г.Т.,Буянов C.B. Устойчивость асинхронных дискретных линейных систем.// Материалы международного научно-технического семинара "Современные технологии в задачах управления и обработки информации", Алушта, МАИ,1996.

6. Артамонов Г.Т., Буянов С. В. Проблемы синхронизации при выполнении алгоритмов управления ПА на сети процессорных элементов. Депонировано в ВИНИТИ N442-B96 от 08.02.96.

7. Артамонов Г.Т., Буянов С. В. Оценка влияния дополнительных задержек на качество управления асинхронных детерминированных конвейерных вычислителей, депонировано в ВИНИТИ N443-B96 от 08.02.96.

8. Буянов C.B. Проблемы синхронизации в многопроцессорных вычислительных системах.// Отчет о НИР: Структура бортового вычислительного комплекса с элементами искусственного интеллекта перспективного летательного аппарата. Этап 66,- М„ МАИ, 1993. с.80-93.

9. Буянов C.B. Инструментарий для поддержки процессов размещения задач в транспьютерной сети.// Отчет о НИР: Структура бортового вычислительного комплекса с элементами искусственного интеллекта перспективного летательного аппарата. Этап 4,- М„ МАИ, 1994. с.138-159.

10. Буянов C.B. Развитие системы автоматизации проектирования и использования транспьютерной бортовой вычислительной системы.// Отчет о НИЭР

"Разработка перспективной бортовой транспьютерной вычислительной системы вертолета", М.:МАИ,1995, с.341-412.

11. Буянов C.B. Программный инструментарий для проектирования вычислительной среды перспективного вертолета. // Отчет о НИЭР "Разработка перспективной бортовой транспьютерной вычислительной системы вертолета", М.:"у"АИ,1333, с.233-335.

12. Буянов C.B. Средства автоматизации проектирования транспьютерных бортовых вычислительных систем. II Отчет о НИЭР "Разработка перспективной бортовой транспьютерной вычислительной системы вертолета", М..МАИ, 1994, с.320-360.