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

Введение.

Об отказоустойчивости.

О степени отказоустойчивости.Л

Основные задачи, решаемые в диссертации.

Методы решения проблемы.

Объем и структура диссертации, краткое содержание.

Теоретическая и практическая ценность диссертации.16

Апробация результатов работы.18

Публикации.19

Глава I. Основные понятия отказоустойчивости.20

§1-1. Таксономия отказоустойчивости.20

I-1. Факторы ухудшения.20

1-2. Количественные характержЛики.23

1-3. Исходные требования к отказоустойчивым системам.24

§1-2. Интуитивный подход к отказоустойчивости.27

2-1. Шесть основных принципов.27

2-2. Критика шести принципов.31

§1-3. Краткая характеристика методов обнаружения и поиска отказов.33

3 -1. Средства, используемые для противодействия дефектам.34

3-2. Отказоустойчивость и надежность.35

§1-4. Обзор методов обнаружения и поиска дефектов.36

4-1. Алгебраические коды с обнаружением и исправлением ошибок.37

4-2. Самопроверяемые схемы.38

4-3. Схемы проверки на основе дублирования.39

4-4. Учетверенные комплексы.42

4-5. Мажорированные комплексы.45

4-6. Программные методы проверки.48

4-7. Временной контроль процессов.49

§1-5. Дальнейшие системные действия.50

5-1. Предотвращение распространения ошибок.50

5-2. Поиск источников ошибок.52

5-3. Реконфигурация.52

5-4. Восстановление процесса.54

§1-6. Системы реального времени и отказоустойчивость.55

§1-7. Параллельные архитектуры.60.

7-1. Параллелизм и производительность.60.

7-2. О сохранении логической структуры.62

Выводы к главе I.!.65

Глава И. Анализ структур одно- и многопроцессорных ОУ систем. .66

§11-1. Обзор. Исследование структур (архитектур) ОУ систем.68

§11-2. Структуры однопроцессорных ОУ вычислительных систем.70

§11-3. ОУ по отношению к кратным дефектам.79

§11-4. Структуры ОУ многопроцессорных вычислительных систем.83

§11-5. Сетевые ОУ структуры.89

§11-6. Общие черты и различия в структурах одно- и многопроцессорных ОУ ЭВМ.94

Выводы к главе II.97

ВЫВОДЫ К ГЛАВЕ I

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

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

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

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

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

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

Глава II Анализ структур одно- и многопроцессорных отказоустойчивых систем

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

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

По методам встроенного и тестового контроля, включая и поиск места обнаруженного дефекта, затронутым в главе I, опубликовано довольно много обзорного материала по ранней истории вопроса, часть которого можно найти в [20,21,22,23,24].

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

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

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

§ II-1 Обзор. Исследование структур (архитектур) отказоустойчивых систем

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

Введение

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

1. Мы начнем исследование со структур однопроцессорных отказоустойчивых ЭВМ, стараясь выявить те их свойства, которые унаследуются многопроцессорными системами.§11-2 Структуры однопроцессорных отказоустойчивых ВС.

2. По приведенной структуре были выполнены, в частности, такие системы как Центр коммутации сообщений 28., ЭВМ серии ряд (ЕС 1046), вй-айю-Зг [20], ЕЗБ-ЗА [25] и др.

3. Структура, приведенная на рис. П-8, устойчива к отказу любого одного процессора Рг и голосующего органа МО-. (¿./=1,2,3), гдестепень отказоустойчивости г = 1. Отказоустойчивость здесь достигается ценой более чем трехкратной избыточности.

4. Обобщением троированнных мажоритарных структур являются

5. Находят распространение в специальных применениях однопроцессорные отказоустойчивые структуры, изображенные на1. ИНФОРМАЦИОННЫЕ ВХОДЫ1. ПроцессорЗ1. Мажоритарный орган 11. Мажоритарный орган 21. Мажоритарный орган 3V1. ИНФОРМАЦИОННЫЕ ВЫХОДЫ

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

7. Рис. И-9 Четырехпроцессорная отказоустойчивая структуракоторыми автоматическими средствами представляет значительную трудность.

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

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

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

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

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

13. Самовосстановление от устойчивых дефектов осуществляется на основе кодов с повторением в пространстве, а от неустойчивых дефектов (сбоев) — на основе кодов с повторением во времени.

14. Рассмотренные на рис. II- 7,8,9 структуры по существу исчерпывают разнообразие однопроцессорных отказоустойчивых систем. Между некоторыми из них (11-76,8) не всегда можно проложить разделяющую грань их структурных различий.

15. Практически все рассмотренные методы находят применение и в многомашинных, и в многопроцессорных отказоустойчивых вычислительных системах.§11-4 Структуры отказоустойчивых многопроцессорных вычислительных систем

16. На рис.И-10 приведен пример многомашинной (N = 7) структуры, где каждый процессор может тестировать любой другой. Корректное определение неисправных процессоров возможно при t<3.

17. Если загрузить все процессоры одной и той же задачей, то с точки зрения структурной организации отказоустойчивости рассмотренные многомашинные ВС не будут отличаться от структуры на рис. П-7 "б".1. Неисправный процессор

18. Рис.П- 10 Структурная модель взаимных проверок процессоров (21+1=7,1<3 диагностируемость)

19. Системы с несколькими программными регистрами и с более тесным обменом информацией принято называть многопроцессорными системами типа МКМД (много потоков команд — много потоков данных).

20. Однако в интересующем нас структурном рассмотрении FTMP и SIFT практически идентичны.

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

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

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