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

Актуальность проблемы. Задача обеспечения отказоустойчивости вычислительных систем (ВС) встала одновременно с их появлением. В качестве примера можно привести ВС 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.10 509).

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 страниц.

3.7 Выводы.

1. Для исследования предложенного метода ЮТУ — «Модифицированного анализа сигнатуры пути» разработан и создан экспериментальный стенд, в состав которого входят: экспериментальная ВС, сопроцессор ЮТУ и имитатор неисправностей. При проектировании и настройке сопроцессора ЮТУ была применена на практике и отработана методика проектирования, разработанная в разделе 2.

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

3. Проведены экспериментальные исследования метода «Модифицированный анализ сигнатуры пути», которые подтвердили справедливость приведенной методики оценки времени обнаружения ошибки для данного метода.

4. Произведены расчеты, позволившие оценить эффект от применения разработанного метода.

ЗАКЛЮЧЕНИЕ

.

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

Основные теоретические и практические результаты следующие.

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

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

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

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

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

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

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