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

/>// Л / /А/ ^

т у Цу и —- ) / ✓ - у . Д ¿й

-у >у ^ / / и О с^

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

УНИВЕРСИТЕТ

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

МЕЛЬНИК ЭДУАРД ВСЕВОЛОДОВИЧ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АППАРАТНО-ПРОГРАММНЫХ СРЕДСТВ КОНТРОЛЯ ПОТОКА УПРАВЛЕНИЯ В МИКРОПРОЦЕССОРНЫХ СИСТЕМАХ

Специальность 05.13.13 -Вычислительные машины, комплексы, системы и сети Диссертация на соискание ученой степени кандидата технических лаук

Научный руководитель доктор технических наук, профессор И.А.Каляев

Таганрог - 1998 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 4

1 ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА КОНТРОЛЯ

ПОТОКА УПРАВЛЕНИЯ 10

1.1 Примеры отказоустойчивых систем 10

1.2 Анализ традиционных методов контроля 24

1.3 Известные методы КПУ 33

1.4 Модифицированный анализ сигнатуры пути 39

1.5 Размещение контрольной информации 49

1.6 Автоматизация встраивания контрольной информации в тело 82 программы

1.7 Выводы 89

2 ИССЛЕДОВАНИЕ И РАЗРАБОТКА АППАРАТНЫХ СРЕДСТВ 94 ДЛЯ РЕАЛИЗАЦИИ КОНТРОЛЯ ПОТОКА УПРАВЛЕНИЯ

2.1 Анализ способов подключения устройств контроля потока 94

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

2.2 Задачи, решаемые при проектировании сопроцессора контроля 100 потока управления

2.3 Синтез обобщенной структуры сопроцессора контроля потока 109 управления

2.4 Возможность реализации устройства контроля в виде сопроцессора 120

2.5 Организация встроенного контроля микропроцессоров методами 123 контроля потока управления, контроль работы микропрограммных устройств управления

2.6 Выводы 132 3 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДА

«МОДИФИЦИРОВАННЫЙ АНАЛИЗ СИГНАТУРЫ ПУТИ» 134

3.1 Структура экспериментальной вычислительной системы 134

3.2 Имитатор неисправностей 137

3.3 Сопроцессор КПУ 143

3.4 Программное обеспечение экспериментальной вычислительной системы 148

3.5 Организация эксперимента 149

3.6 Описание тестовых программ 151

3.7 Выводы 166 ЗАКЛЮЧЕНИЕ 172 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 173 ПРИЛОЖЕНИЕ 180

ВВЕДЕНИЕ

Актуальность проблемы. Задача обеспечения отказоустойчивости вычислительных систем (ВС) встала одновременно с их появлением. В качестве примера можно привести ВС SAPO (ЧССР), в которой было применено тройное модульное резервирование с голосованием в центральном процессоре /1/. Если для первых ВС необходимость обеспечения отказоустойчивости была связана, в первую очередь, с низкой надежностью элементной базы, то в настоящее время, когда доля отказов аппаратуры составляет около 20% /2/, /3/, необходимость введения отказоустойчивости обусловлена наличием целого ряда областей применения, где отказ может повлечь человеческие жертвы, нанести большой материальный ущерб, а также в случае невозможности проведения обслуживания ВС. К таковым можно отнести военную область, управление транспортными средствами, космическими аппаратами /4/-/6/ и т. д. Также методы обеспечения отказоустойчивости применяются в сверхпроизводительных ВС с целью уменьшения времени простоев 111.

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

В настоящее время проблемой создания отказоустойчивых ВС занимаются такие известные зарубежные ученые /8/ как Д.Севиорек (Center for Dependable Systems, университет Карнеги-Меллон), Э.Маккласки (Center for Reliable Computing, Стендфордский университет), А.Авиженис, Д.Реннелс (Jet Propolution Laboratory, Калифорнийский университет), В.Рэндол (Ньюкаслский университет) и М.Малек (Техасский университет). Также работы в этой области ведутся в Японии, Франции, Германии. В странах СНГ данной проблемой занимаются такие ученые как А.Г.Додонов (г.Киев), Е.С.Согомонян (г.Москва), Е.В.Слабаков (г.Москва), В.Г.Хорошевский (г.Новосибирск).

В России работы в области отказоустойчивых ВС традиционно ведутся в

интересах министерства обороны и в аэрокосмической отрасли. Можно упомянуть такие центры как Институт космических исследований РАН, КБ космического приборостроения.

Можно упомянуть такие работы, посвященные проблемам обеспечения отказоустойчивости /1/, /9/ - /27/.

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

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

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

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

Для достижения поставленной цели поставлены и решены следующие задачи.

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

2. Разработан алгоритм автоматизации размещения контрольной информации, позволяющий реализовать встраивание в программу такой информации на этапе компиляции.

3. Разработана методика проектирования устройства контроля для реализации методов КПУ.

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

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

Основные положения, выносимые на защиту. На защиту выносятся следующие положения и результаты:

- новый метод контроля потока управления;

- алгоритм размещения эталонной информации в теле программы для разработанного метода;

- методика проектирования устройства КПУ в виде сопроцессора.

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Результаты диссертационной работы были использованы при разработке и создании бортовой отказоустойчивой ВС космического аппарата в рамках работ по международной космической программе "Марс 94-96" (х/д НЦ-637-51, шифр "Аргус"):

1. "Разработка технологий обеспечения отказоустойчивости многопроцессорных вычислительных систем с программируемой архитектурой" 04 ГР 0193.0010509).

2."Разработка и исследование методов организации отказоустойчивых систем самоорганизующихся систем управления на базе нейроподобных сетей для комплексного решения задач обработки сенсорной информации, принятия решений и адаптивного управления мобильными объектами" (постановление Правительства РФК 1314-68 от 21.12.93г.).

Результаты работы используются в ряде организаций г. Санкт-Петербурга и г.Таганрога.

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

- Пятом Международном семинаре "Распределенная обработка информации", г.Новосибирск, 1995г.;

- Третьей Всероссийской конференции по механике и управлению движением шагающих машин, г.Волгоград, 1995г.;

- Третьей Всероссийской научной конференции студентов и аспирантов

- Третьей Всероссийской конференции по механике и управлению движением шагающих машин, г.Волгоград, 1995г.;

- Третьей Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления", г.Таганрог, 1996г.;

- Всероссийской научной конференции студентов и аспирантов "Радиоэлектроника, микроэлектроника, системы связи и управления", г.Таганрог, 1997г.;

- VIII научно-технической конференции "Экстремальная робототехника", г. Санкт-Петербург, 1997г.;

- Межвузовской конференции "Микроэлектроника и информатика -97"(МИЭТ, 1997г.)

По результатам работы опубликовано 7 печатных работ /28/-/34/. Также результаты работы изложены в 4 отчетах о выполнении НИР.

Из работ, выполненных в соавторстве, в диссертации использованы результаты, полученные лично автором. В работах [28], [29], [31] личный вклад автора состоит в предложенном новом методе контроля потока управления, в работах [30], [33], [34] - в методике проектирования сопроцессора контроля потока управления, в работе [32] - в предложенном алгоритме размещения контрольной информации в программе.

Структура работы. Диссертационная работа состоит из введения, трех разделов и заключения, изложенных на 170 страницах, содержит 66 рисунков, 12 таблиц, 84 наименования библиографии. Всего 179 страниц.

1 ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА КОНТРОЛЯ ПОТОКА УПРАВЛЕНИЯ

1.1 Примеры отказоустойчивых систем

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

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

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

2) управление технологическими процессами, коммутация систем связи, обслуживание множества терминалов в оперативном режиме (отказ ведет к большому экономическому ущербу);

3) использование вычислительных систем на объектах, где обслуживание затруднено или невозможно (искусственные спутники, межпланетные корабли и т. д.).

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

Рассмотрим некоторые существующие отказоустойчивые системы.

Одной из ведущих фирм в области разработки и создания коммерческих ОУВС является фирма Tandem Computers Inc. Эта фирма была основана в 1976 г. для построения ОУВС оперативной обработки данных. К системам оперативной обработки данных, называемым также системами обработки транзакций, относятся различные системы резервирования билетов, банковские системы безналичных расчетов и др. Архитектура ОУВС фирмы Tandem /35/-/38/ остается неизменной с момента выпуска первой коммерческой отказоустойчивой системы Tandem Non Stop 1. Цели создания архитектуры Tandem включают:

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

- обеспечение целостности данных (одиночный отказ аппаратуры не может разрушить общие данные системы);

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

Структура машины представлена на рисунке 1.1. Система включает в свой состав от 2 до 16 процессорных модулей (ПМ), которые могут функционально заменять друг друга. Процессорные модули объединяются в единую систему с помощью двух высокоскоростных параллельных шин Dynabus. Каждое периферийное устройство (ПУ) имеет два канала связи и доступно для двух процессорных модулей. В состав ПМ входят:

- центральный процессор (ЦП);

- оперативная память (ОЗУ);

- контроллер шины Dynabus (КШ).

Периферийные устройства состоят из накопителей на магнитных дисках (НМД) и контроллеров НМД (КНМД).

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

Шина Dinabus

Рисунок 1.1 - Структура ОУВС Tandem

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

Каждый процессорный модуль системы Tandem имеет свою копию операционной системы Guardia