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

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

Глухих Михаил Игоревич

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

Специальность 05.13.15 - Вычислительные машины и системы

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2006

Работа выполнена на кафедре «Автоматика и вычислительная техника» государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный политехнический университет».

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

доктор технических наук, профессор

Мелехин Виктор Федорович

Официальные оппоненты

доктор технических наук, профессор

Черкесов Геннадий Николаевич

кандидат технических наук, доцент

Скорубский Владимир Иванович

Ведущая организация ФГУП НПО «Импульс»

Защита состоится 25 января 2007 г. в 16 часов на заседании Диссертационного Совета Д 212.229.18 при ГОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу: 195251, Санкт-Петербург, ул. Политехническая, д, 29,9-й учебный корпус, ауд. 325.

С диссертацией можно ознакомиться в фундаментальной библиотеке ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Автореферат разослан » декабря 2006 г.

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

диссертационного совета ^_Шашихин В.Н,

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

Актуальность темы. Информационно-управляющие системы специального назначения (ИУССН) используются для автоматизации контроля и управления в сложных технических системах различного назначения: космических комплексах, летательных аппаратах разного класса, наземных станциях контроля и управления, судах различного назначения, энергетических комплексах и др.

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

Проблема повышения надежности вычислительных систем изучается довольно давно. Первая работа на эту тему датируется 1952 годом и принадлежит Джону фон Нейману. Сейчас широко разработанными являются задачи, связанные с повышением надежности отдельных компонент системы (работы У, Пирса, Д. Трайона, Э. Мура), с повышением надежности передачи данных (работы К. Шеннона, М. Голея, Р. Хэмминга), с определением надежностных характеристик вычислительных систем (работы И. А. Рябинина, Г. Н. Черкесова, А. М. Половко). Разработан рад стандартов и рекомендаций, связанных с надежностью систем и их элементов,

ИУССН относятся к вычислительным системам, ошибка на выходе которых может иметь критические последствия для их окружения - иначе говоря, к системам высокой достоверности (и1Ьга<Зерепс)аЫе зуз1еш8).При проектировании такого рода систем следует учитывать не только их надежность, но и их безопасность.

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург

ОЭ аоо-ЬятЦ

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

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

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

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

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

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

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

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

2. Безотказность. Система должна обеспечивать требуемый уровень безотказности.

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

4. Невосстанавливаемость элементов. Во время работы системы, отказавшие элементы не могут быть восстановлены.

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

Задачи исследования.

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

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

3. Создание методики поиска наилучшей структуры из ограниченного множества вариантов.

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

Методы il средства исследования. Для теоретических исследований применяются методы теории отношений, теории графов, теории надежности, логико-вероятностные методы, теории случайных процессов, математического моделирования, математического программирования. Для построения моделей устройств использовались системы автоматизированного проектирования MAX+PLUS II, Quartus II и среда программирования Microsoft Visual Studio.

Положения, выносимые на защиту.

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

2. Выделение подмножества структур ИУССН, оптимальных по комбинированному критерию надежности, безопасности и стоимости -доменных структур, включающих множество независимых узлов доменов с голосующим устройством на входе каждого.

3. Методика синтеза структур ИУССН с доменной организацией.

Научная новизна работы.

1. Разработана модель структуры ИУССН - динамический типизированный граф. Модель обладает возможностью рассматривать на функциональном уровне процессы распространения отказов и полнотой представления множества вариантов структуры ИУССН. Разработана программа расчета вероятности безотказной работы системы по динамическому типизированному графу.

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

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

4. Выделен новый класс из множества доменных структур ИУССН -масштабируемые структуры с резервированием. Главное преимущество данного класса структур заключается в возможности увеличения надежности системы путем увеличения числа однотипных устройств без изменения структуры голосующих устройств.

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

Достоверность результатов. Достоверность методики упорядочения

структур и тезис о возможности разбиения оптимальной структуры на

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

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

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

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

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

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

1, Разработка методики и инструментария для проектирования и верификации высоконадежных специализированных процессоров на базе СБИС ПЛ. Программа министерства образования РФ, подпрограмма

«Международное научно-образовательное сотрудничество», проект №1283 за 2003 год.

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

j СБИС ГШ. Программа министерства науки и образования РФ,

федерального агентства по образованию «Федерально-региональная политика в науке и образовании», подпрограмма «Международное научно-образовательное сотрудничество», проект №1647 за 2004 год.

3. Создание центра по коммерциализации разработок Санкт-Петербургского государственного политехнического университета в области проектирования радиоэлектронной аппаратуры с использованием технологий FPGA и ASIC. Программа министерства науки и образования РФ, федерального агентства по образованию «Развитие научного потенциала высшей школы», подпрограмма 3 «Развитие инфраструктуры научно-технической и инновационной деятельности высшей школы и ее кадрового потенциала» на 2005 год.

4. Развитие центра трансфера технологий проектирования ASIC/FPGA на базе Санкт-Петербургского государственного политехнического университета для промышленности региона. Программа и подпрограмма п. 3,2005 год.

5. Развитие международного центра трансфера технологий проектирования ASIC на базе Санкт-Петербургского государственного политехнического университета. Программа и подпрограмма п. 3,2005 год.

Апробация работы. Результаты работы докладывались и обсуждались на VIII Всероссийской конференции «Фундаментальные исследования в технических университетах» (2004 год) и на ежегодной конференции «Практические аспекты разработки отечественных СБИС класса «система на кристалле»» (2006 год).

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

ведомости СПбГТУ» (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»). Всего опубликовано три журнальных статьи и три тезиса конференций.

Структура и объем работы. Диссертационная работа состоит из <.

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

и

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

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

В первой главе рассматриваются основные требования при решении задачи синтеза ИУССН:

1. Система должна удовлетворять всем функциональным требованиям.

2. Заданы типовые устройства, входящие в ее состав, и характеристики этих устройств (показатели надежности, безопасности и стоимости),

3. Система должна обеспечивать требуемый уровень надежности и безопасности.

4. Стоимость системы должна быть минимальной.

В целях уточнения формулировки задачи синтеза ИУССН проводится обзор научных работ в следующих направлениях:

1. Терминология теории надежности и безопасности, употребляемые показатели качества.

2. Классификация методов повышения надежности и безопасности.

3. Основные методы расчета показателей надежности.

4. Существующие архитектуры вычислительных систем с резервированием.

5. Известные постановки и методы решения задачи синтеза.

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

В новой постановке с учетом сформулированных выше требований задача синтеза разбивается на следующие зтапы;

1. Порождение множества решений.

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

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

4. Реализация полученной структуры на практике. Для проверки теоретических положений синтезируется прототип ИУССН.

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

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

1. Вычислительная подсистема - отвечает за выполнение основной функциональной задачи ИУССН.

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

3. Подсистема конфигурации - решает задачи диагностики и изоляции отказов.

Выделяются элементы окружения ИУССН:

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

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

Функциональная схема ИУССН приведена на рис. 1. По своему составу функциональная схема не является новой. Она необходима для конкретизации названий подсистем и как база для функциональной декомпозиции - основы процесса синтеза структуры.

{ычислительная подсисте

Блок процессоров

П1 ГО

Блок ЗУ

31

32 33

Подсистема коммутации и контроля

Подсистема конфигурации

ОПЕРАТОР

Уникальное устройство ввода-вывода

ПОЛЬЗОВАТЕЛЬ

Рис, 1. Функциональная схема ИУССН и ее окружения.

Рассматриваются основные алгоритмы функционирования устройств коммутации и контроля (УКК) в зависимости от количества экземпляров коммутируемых устройств. Выделены три случая:

1. Дублирование (два экземпляра). В случае несовпадения результатов происходит остановка УКК и всех связанных с ним устройств.

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

3, ¡У-кратное резервирование (N>3 экземпляров). Если М>№2 устройств дают совпадающие данные, они считаются верными. Другие результаты маскируются. При систематическом несовпадении устройство изолируется, УКК переходит в режим работы с N-1 устройством. Если не существует М>№2 устройств, дающих совпадающие результаты, система останавливается,

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

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

2. Связи между блоками - для определения направления распространения информации в системе.

3. Состояния блоков, характеризующие их работоспособность.

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

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

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

Вторым видом модификации орграфа являются пометки вершин графа состоянием блока, характеризующим его работоспособность. Это состояние может изменяться при возникновении и распространении отказов. Выделяются работоспособное состояние (W, Work), состояние остановки, вызываемое обнаружением отказа внутри данного устройства или устройства, связанного с ним (S, Stop), и состояние аварии, вызываемое поступлением в устройство неверных результатов без обнаружения отказа (F, Fail).

С учетом отмеченных модификаций орграф, предложенный в качестве модели структуры системы, назван динамическим типизированным графом (ДТГ),

В разделе 2.3 формулируются правила работы с моделью ДТГ. Правила основаны на неформальных требованиях к структурам систем с резервированием и разделены на 6 групп:

1. Правила представления системы в виде ДТГ, Устройство системы представляется вершиной. Связи для передачи информации представляются дугами. ВУ представляются основными вершинами, УКК - промежуточными вершинами.

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

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

4. Правила изменения состояний вершин. Три состояния - работа W, остановка S, авария F. Начальное состояние - W. В вершинах могут происходить обнаруженные и необнаруженные отказы, переводящие их в состояние S или F. Отказы могут повлечь за собой изменение состояния связанных вершин.

5. Правила распространения отказа. При изменении состояния формирующей вершины основная вершина переходит в то же состояние. Изменение состояния вершины X, входной для промежуточной вершины К, ведет к изменению состояния вершины К. При отсутствии входных вершин одного типа с X, вершина К переходит в то же состояние. При наличии одной вершины того же типа, вершина К переходит в состояние S. При наличии двух и более вершин того же типа, вершина К остается в состоянии W.

6. Правила изменения состояния ДТГ, ДТГ находится в состоянии W, если и только если существует связный подграф из вершин в состоянии W, включающий, по меньшей мере, одну вершину каждого типа. В противном случае, ДТГ находится в состоянии S, если хотя бы одна его вершина перешла в это состояние. Иначе ДТГ находится в состоянии F.

В разделе 2,4 определяется и формализуется постановка задачи синтеза ИУССН с использованием модели ДТГ. Функциональность системы обеспечивается наличием заданного набора типов основных вершин графов. При этом отдельно выделяется множество типов вершин D, соответствующих уникальным устройствам - решающих вершин, и множество типов остальных вершин Р. На основании этого, выделяется множество ДТГ, совместимых по типам, обозначаемое G(P, D).

С учетом введенных понятий, задача синтеза формулируется следующим образом. Заданы множества типов основных вершин PhD. Для всех элементов этих множеств заданы характеристики вычислительных устройств, соответствующих данным типам вершин. Выбрать из множества G(P, D) динамический типизированный граф g, обеспечивающий выполнение требований по надежности и безопасности и минимальное значение стоимости.

Решение задачи синтеза предполагает полный или частичный перебор множества G(P, D) и выбор лучшего решения по заданному критерию. Применение полного перебора крайне трудоемко. Частичный перебор требует усечения множества G(P, D) без потери оптимального решения.

Поэтому необходим аппарат, позволяющий отбросить решения из G(P, D), обладающие заведомо худшими характеристиками. Одним из возможных аппаратов является теория отношений.

Для его применения необходимо задание на множестве G(P, D) отношения порядка с точки зрения заданных критериев оптимальности. В этом случае, перебор решений может быть ограничен множеством максимальных элементов для заданного отношения.

В третьей главе для сокращения перебора элементов множества G(P, D) ставится и решается задача выделения подмножества элементов, оптимальных по критериям надежности, безопасности и стоимости. Для этой цели, на множестве G(P, D) задаются бинарные отношения порядка, отдельно для критериев надежности, безопасности и стоимости. Эти отношения обозначаются Rt,, Tb, Сь, где символы R, Т и С соответствуют надежности (Reliability), безопасности (safeTy) и стоимости (Cost). Например, для графов g, е G.gj е G выполняется отношение Rb (giRbgj), если граф g2 может быть заменен графом gi с получением выигрыша в надежности системы.

Данный набор отношений позволяет задать общее отношение порядка для комбинации заданных критериев. Это отношение обозначается символом О (Optimal). Отношение gjOg2 выполнено, если граф g2 может быть заменен

графом с получением выигрыша в надежности, безопасности и стоимости системы. Это происходит при gtR^,g2, В|ТЬ§2, g|Cbg2 (оптимизация по Слейтеру).

В разделе 3.1 формулируются отношения порядка на множестве С(Р, Б). Для формулировки этих отношений необходимо знать, как соотносятся друг с другом характеристики различных устройств, входящих в систему, и соответствующих им вершин ДТГ. Для основных вершин характеристики считаются известными, причем для однотипных вершин они совпадают. Для сравнения характеристик промежуточных вершин формулируется отношение порядка по критерию стоимости Сь, определяемое числом их связей с другими вершинами (при увеличении числа связей соответствующее устройство становится хуже по критерию стоимости, а также по критериям надежности и безопасности).

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

Рис. 2. ДТГ простой системы.

Рис, 3, Графы надежности (слева) и безопасности (справа).

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

1. Если любая вершина ДТГ g| не уступает в стоимости соответствующей верщине §2, и хотя бы одна вершина gt выигрывает в стоимости у соответствующей вершины то glCьg2 (на практике система или устройство являются более дешевыми).

2. Если графы надежности для ДТГ g[ и g2 имеют совпадающую структуру и выполняется условие п.1 о стоимости вершин и g2t то

3. Если граф надежности для ДТГ %г отличается от графа надежности для ДТГ gl последовательным добавлением дуги, то g2R.bg|.

4. Если граф надежности для ДТГ отличается от графа надежности для ДТГ gt параллельным добавлением дуги, то g^Rъg2.

В разделе 3.2 производится упорядочение множества в(Р, О) по критерию безопасности. Безопасность системы напрямую связана с наличием в ее составе уникальных вершин. В леммах 3.2.1 - 3.2.3 доказывается, что отказ любой решающей вершины ДТГ, а также любой вершины, формирующей для решающей вершины, всегда приводит к его переходу в состояние Р.

В теореме 3.2.4 определяется оптимальная по критерию безопасности структура ДТГ для случая, когда множество решающих вершин Б содержит одну вершину, В оптимальной структуре, решающая вершина о «м»»т

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

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

Рис, 4. Пример ДТГ, оптимального по критерию безопасности.

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

В леммах 3.3.1 - 3.3.3 обосновываются три возможных преобразования структуры ДТГ 8!-^2, обеспечивающие и

1. Устранение из ДТГ избыточных связей, не обеспечивающих сдерживание отказов.

2. Устранение связей между независимыми частями ДТГ, каждая из которых обеспечивает сдерживание отказов.

3. Устранение связей между однотипными вершинами.

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

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

2. Внутренние вершины узлов доменов не имеют входных вершии, принадлежащих другим узлам.

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

В подразделе 3.3.5 анализируются доменные структуры. В рамках используемого подхода (сравнение графов состояний) определение лучшей или худшей из двух доменных структур невозможно. Поэтому необходима параметризация доменной структуры с целью упрощения поиска оптимальной из них путем сравнения численных показателей. Вводятся следующие параметры; число доменов в ДТГ, максимальное число однотипных вершин в каждом домене (размер домена) <*00 и устойчивость домена к отказам на его входе ф(Ь) (максимальное число вершин входного домена, отказ которых не влияет на состояние данного домена).

В лемме 3.3.6 и теореме 3.3-7 анализируется структура домена с заданными параметрами. Доказывается связь параметров входного домена и выходного домена о(Ьвх)>ф(Ьвш)+2. Учитывая это соотношение, в подразделе 3,3.8 доменные структуры делятся на два класса. 1. Последовательно-параллельные структуры, о(11и)=<р(ЬВ1Л)+2, В них резервирование осуществляется на уровне групп устройств. Пример приведен на рис. 5. Во всех доменах, кроме одного, имеется о=3 узла, число входных вершин для сдерживающих вершин совпадает с размером домена, устойчивость доменов ф=о-2.

Рис. 5. ДТГ с последовательно-параллельной структурой.

2. Класс структур, не упоминающийся в литературе - масштабируемые структуры с резервированием, а(Ьвк)>ф(Ь[1Ь1х)+2. В приведенном на рис. б примере сдерживающие распространение отказа вершины К, Ь имеют по три входа (меньше размера домена). Достоинством данного класса структур является возможность добавления узлов в домены без модификации используемых устройств коммутации и контроля (при этом структура с с=4, <р=1 преобразуется в структуру с <т=5, <р=1).

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

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

В разделе 4.1 для ускорения процесса расчета характеристик разрабатывается программа расчета ВБР системы по ДТТ. Программа работает путем формирования функции работоспособного состояния (ФРС) для ДТГ в виде совершенной дизъюнктивной нормальной формы (СДНФ). СДНФ формируется полным перебором возможных комбинаций состояний вершин (для сокращения перебора каждый узел домена представляется одной вершиной). Затем осуществляется переход к вероятностной функции и упрощение получившегося полинома.

В разделе 4,2 анализируется характер зависимости ВБР от параметров доменной структуры - числа доменов, устойчивости доменов, размера доменов. С этой целью для каждого из трех параметров рассматриваются структуры, в которых изменяется только данный параметр. С помощью программы расчета вычисляются ВБР для некоторого количества структур, после чего делаются выводы о характере рассматриваемых зависимостей.

Основные результаты сравнительного анализа структур: 1. Эффект от увеличения устойчивости доменов быстро снижается с ее повышением. Для высоких начальных значений устойчивости дальнейшее ее повышение может приводить к ухудшению показателей системы. Влияние устойчивости на показатели системы выше при сравнительно высокой ВБР используемых УКК по сравнению с ВБР используемых ВУ (рис. 7, здесь и далее логарифмическая ВБР системы рассчитывается как -1ё(1-ВБР)).

-уел-1

---уст2

----устЗ

.....усг4

Рис. 7. Зависимость ВБР системы от ВБР ее устройств при различной устойчивости доменов системы (2 домена, о=б).

2. Эффект от увеличения размера доменов может носить ступенчатый характер - ВБР системы меняется скачком при определенных значениях размера. Влияние размера на показатели не зависит от сравнительной ВБР используемых УКК и ВУ (рис. 8).

-размера

— ——размер 7

----раэмерб

.....размере

----размер 4

размер 3

Рис. 8. Зависимость ВБР системы от ВБР ее устройств при различном размере доменов системы (2 домена, <р=1).

3. Для заданных значений (<р, о) и вероятностей безотказной работы устройств системы существует некоторое оптимальное число доменов д. Оно увеличивается при сравнительно высокой ВБР используемых УКК по сравнению с ВБР используемых ВУ (рис. 9).

числе доменов системы (<р=1, о=3).

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

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

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

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

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

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

В пятой главе рассматривается задача синтеза на примере прототипа ИУССН на основе СБИС программируемой логики семейства Stratix.

В разделе 5.1 определяется функциональный состав системы. Для синтеза системы-прототипа используется инструментальная ЭВМ и три высоконадежных платы, включающих в себя СБИС ПЛ Stratix фирмы Altera. Для контроля надежности платы связываются друг с другом по LVDS-интерфейсу. В качестве вычислительного ядра системы используется готовый процессорный модуль Nios, применяемый в системах на кристалле.

В разделе 5.2 производится синтез структуры системы-прототипа с использованием разработанного подхода. На рис. 10 приведен пример структуры узла домена. Здесь доменный коммутатор - устройство, принимающее данные от трех узлов домена и сравнивающее их друг с другом. На основании сравнения производится диагностика состояния отдельных устройств системы.

Рис. 10. Функциональная схема узла домена.

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

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

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

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

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

3. В множестве доменных структур выделен класс новых структур -масштабируемые структуры с резервированием, позволяющие повышать уровень надежности без изменения используемых блоков.

4. Разработана программа расчета вероятности безотказной работы системы по ДТГ. Рассчитаны функциональные зависимости показателей надежности системы от параметров доменной структуры. Определены основные правила разбиения системы на домены. На основе данных результатов разработана методика синтеза ИУССН с доменной структурой.

5. Разработана структура прототипа ИУССН и определены функциональные спецификации к ее блокам. Обоснован функциональный состав системы-прототипа, предназначенной для экспериментальной проверки теоретических положений по синтезу структур ИУССН,

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Глухих М.И. Оптимизация структуры информационно-управляющей системы специального назначения по критерию надежности // Научно-технические ведомости СПбГТУ. - 2006. №4, - С. 39-44.

2. Глухих М.И. Формализация представления отказоустойчивых систем при проектировании структуры системы Н Информационно-управляющие системы. - 2005. №3. - С. 27-35.

3. Глухих М.И. Расчет показателей надежности по модели структуры вычислительной системы Н Вычислительные, измерительные и управляющие системы: Сборник научных трудов / под ред. Ю.Б. Сениченкова. - СПб.: СПбГПУ, 2005. - С. 57-64.

4. Глухих М.И., Мелехин В.Ф. Методика синтеза и анализа высоконадежных схем Н Материалы VIII всероссийской конференции «Фундаментальные исследования в технических университетах». - СПб.: СПбГПУ, 2004. - С. 145.

5. Глухих М.И., Максименко С.Л., Мелехин В.Ф. Методология и инструментальные средства создания специализированных процессоров // XXIX неделя науки СПбГТУ. Часть V: Материалы межвузовской научной конференции. - СПб.: СПбГТУ, 2000. ~ С. 36-38.

6. Глухих М.И., Мелехин В.Ф. Разработка и исследование специализированного процессора для отказоустойчивой системы И XXX юбилейная неделя науки СПбГТУ. Часть VII: Материалы межвузовской научной конференции. - СПб.: СПбГТУ, 2001. - С. 152.

I

I

I

I I

L

Подписано в печать 4.12.2006. Формат <50*84/16. Усл. пен.л. 1.00, Уч.-изд.л. 1.00. Тираж 100 экз.

Отпечатано с оригинал-макета авторов в центре оперативной полиграфии факультета технической кибернетики СП6ГПУ. 195251 Санкт-Петербург, Политехническая ул., 21

СПИСОК ИСПОЛЬЗУЕМЫХ ТЕРМИНОВ И ОБОЗНАЧЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ НАДЕЖНОСТИ И БЕЗОПАСНОСТИ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ.

1.1. Анализ требований к надежности и безопасности систем.

1.1.1. Терминология надежности и безопасности.

1.1.2. Основные показатели качества резервированных вычислительных систем.

1.2. Основные методы повышения надежности вычислительных систем.

1.2.1. Классификация методов резервирования.

1.2.2. Методы структурного резервирования.

1.2.3. Методы голосования.

1.3. Основные методы анализа надежности вычислительных систем и устройств.

1.3.1. Потоки отказов, используемые при анализе надежности.

1.3.2. Логико-вероятностные методы расчета показателей надежности.

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

1.4. Архитектуры вычислительных систем со структурным резервированием.

1.4.1. Отказоустойчивый вычислительный кластер.

1.4.2. Архитектура с раздельным резервированием процессора.

1.5. Основные методы решения задачи синтеза вычислительной системы.

1.5.1. Применение точных методов для решения задачи синтеза.

1.5.2. Применение эвристических методов для решения задачи синтеза.

1.6. Этапы решения задачи синтеза вычислительной системы с резервированием.

Выводы.

ГЛАВА 2. ФОРМАЛИЗОВАННАЯ МОДЕЛЬ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ

СИСТЕМ СО СТРУКТУРНЫМ РЕЗЕРВИРОВАНИЕМ.

2.1. Анализ функциональной организации системы.

2.1.1. Основные задачи информационно-управляющей системы со структурным резервированием.

• 2.1.2. Функциональный состав системы и ее окружения.

2.1.3. Принципы функционирования подсистемы коммутации и контроля.

2.2. Основные предпосылки и примципы построения модели структуры информационно-управляющей системы со структурным резервированием в виде динамического типизированного графа.

2.2.1. Идея использования модели. Требования к модели, основные принципы ее построения.

2.2.2. Иллюстрация представления структуры вычислительной системы графом.

2.2.3. Разбиение вершин па классы и типы.

2.2.4. Изменение состояний вершин и графа.

2.3. Правила построения и модификации динамического типизированного графа.

2.3.1. Правила представления системы в виде динамического типизированного графа (группа I).

2.3.2. Правила соединений вершин динамического типизированного графа (группа II)

2.3.3. Правила введения типов вершин (группа III).

1> 2.3.4. Правила изменения состояний вершин (группа IV).

2.3.5. Правила распространения отказа (группа V).

2.3.6. Правила изменения состояния динамического типизированного графа (группа VI).

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

2.4.1. Общая постановка задачи синтеза.

2.4.2. Представление задачи синтеза в терминах динамических типизированных графов.

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

Выводы.

ГЛАВА 3. УПОРЯДОЧЕНИЕ МНОЖЕСТВА ДИНАМИЧЕСКИХ ТИПИЗИРОВАННЫХ ГРАФОВ ПО КРИТЕРИЯМ НАДЕЖНОСТИ, БЕЗОПАСНОСТИ И СТОИМОСТИ.

ДОМЕННЫЕ СТРУКТУРЫ РЕЗЕРВИРОВАННЫХ СИСТЕМ.

3.1. Отношения порядка на множестве динамических типизированных графов.

3.1.1. Отношения порядка па множестве типов вершин.

3.1.2. Принципы построения графов состояний системы но динамическому типизированному графу.

3.1.3. Определение отношений порядка на множестве динамических типизированных графов.

3.2. Упорядочение множества динамических типизированных графов по критерию безопасности.

3.2.1. Распространение отказа из решающих вершин, лемма.

3.2.2. Состояние динамического типизированного графа при аварии решающей вершины, лемма.

3.2.3. Распространение отказа из формирующих вершин, лемма.

3.2.4. Максимальные элементы по критерию безопасности, теорема.

3.2.5. Динамические типизированные графы с несколькими решающими вершинами

3.3. Упорядочение множества динамических типизированных графов по критериям надежности и стоимости.

3.3.1. Устранение избыточных дуг, лемма.

3.3.2. Устранение связей между однотипными вершинами, лемма.

3.3.3. Устранение связей между независимыми участками графа, лемма.

3.3.4. Разбиение на узлы доменов, теорема.

3.3.5. Параметризация доменных структур.

3.3.6. Распространение отказа из парных вершин, лемма.

3.3.7. Распространение отказа из вершин одного типа, теорема.

3.3.8. Варианты оптимальных структур.

3.3.9. Упорядочение множества динамических типизированных графов по комбинированному критерию.

Выводы.

ГЛАВА 4. АНАЛИЗ НАДЕЖНОСТНЫХ ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С ДОМЕННОЙ СТРУКТУРОЙ. МЕТОДИКА СИНТЕЗА СТРУКТУР

РЕЗЕРВИРОВАННЫХ СИСТЕМ.

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

4.1.1. Принцип автоматизированного расчета вероятности безотказной работы.

4.1.2. Краткое описание программы расчета.

4.1.3. Расчет показателей надежности варианта масштабируемой системы с резервированием.

4.1.4. Расчет показателей надежности двухдоменной системы.

4.2. Сравнительный анализ вариантов доменной организации резервированных систем

4.2.1. Зависимость показателей надежности и стоимости устройств коммутации и контроля от числа их входов.

4.2.2. Сравнительный анализ структур с изменяющейся устойчивостью доменов.

4.2.3. Сравнительный анализ структур с изменяющимся размером доменов.

4.2.4. Сравнительный анализ структур с изменяющимся числом доменов.

4.2.5. Сравнительный анализ структур с различным распределением устройств между доменами.

4.3. Синтез структуры системы с доменной организацией.

4.3.1. Сводка полученных при анализе рекомендаций.

4.3.2. Методика синтеза структур вычислительных систем с доменной организацией

Выводы.

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

5.1. Функциональный состав и надежностные характеристики узлов системы-прототипа

5.1.1. Относительные надежностные характеристики компонентов вычислительной системы.

5.1.2. Функциональный состав системы-прототипа.

5.1.3. Подсистема коммутации и контроля.

5.1.4. Функциональный состав высоконадежной платы.

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

5.2.1. Выбор количества доменов в системе.

5.2.2. Распределение устройств между доменами.

5.2.3. Структура системы с одним доменом.

5.2.4. Структура системы с двумя доменами.

5.2.5. Обобщенная структура системы с большим количеством доменов.

5.2.6. Структурная схема системы-прототипа.

5.3. Требования к устройствам системы-прототипа.

5.3.1. Доменная шина.

5.3.2. Доменный коммутатор.

I 5.3.3. Контроллер связи.

5.4. Основные проблемы доменной организации системы и подходы к их решению.

5.4.1. Проблема синхронизации вычислений.

5.4.2. Проблема конфигурации и реконфигурации системы.

Выводы.

Актуальность темы. Информационно-управляющие системы специального назначения (ИУССН) используются для автоматизации контроля и управления в сложных технических системах различного назначения: космических комплексах, летательных аппаратах разного класса, наземных станциях контроля и управления, судах различного назначения, энергетических комплексах и др.

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

Проблема повышения надежности вычислительных систем изучается довольно давно. Первая работа на эту тему датируется 1952 годом и принадлежит Джону фон Нейману [38]. Сейчас широко разработанными I являются задачи, связанные с повышением надежности отдельных компонент системы (работы У. Пирса, Д. Трайона, Э. Мура [29, 37, 46, 49, 57, 84, 85, 86]), с повышением надежности передачи данных (работы К.

Шеннона, М. Голея, Р. Хэмминга [26, 59, 65, 70, 72, 74, 75]), с определением надежностных характеристик вычислительных систем (работы И. А. Рябинина, Г. Н. Черкесова, А. М. Половко [20, 22, 30, 47, 51, 55, 61, 62, 63]). Разработан ряд стандартов и рекомендаций, связанных с надежностью систем и их элементов [1,4].

ИУССН относятся к вычислительным системам, ошибка на выходе которых может иметь критические последствия для их окружения - иначе говоря, к системам высокой достоверности (ultradependable systems) [87]. При проектировании такого рода систем следует учитывать не только их надежность, но и их безопасность. Теория безопасности по сравнению с теорией надежности изучается не так давно, в этой области могут быть названы работы [51, 77] и стандарты [2, 3].

По этой причине в ИУССН крайне важно своевременное обнаружение отказа. Механизмы контроля надежности, применяющиеся в типовых элементах системы, обычно недостаточны или отсутствуют. В этом случае необходимо применение структурного резервирования, контроль надежности осуществляется на системном уровне с помощью решающих элементов [30, 38,46,51,61,77, 87].

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

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

Существующие автоматизированные подходы связаны с выбором оптимальной структуры из множества некоторого узкого класса - в частности, из множества последовательно-параллельных систем [78, 79, 80, 89] с различной кратностью. Недостаток такого подхода состоит в том, что оптимальная структура может не принадлежать выбранному множеству.

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

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

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

Особенностью многих ИУССН являются сравнительно умеренные

Щ требования к производительности в сравнении с суперкомпьютерами и системами с массовым параллелизмом [28, 33]. Как правило, производительности современного процессора вполне достаточно для решения задач, определенных для одного прибора. Это ограничивает класс рассматриваемых в данной работе вычислительных систем. Рассматриваются следующие свойства системы.

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

2. Безотказность. Система должна обеспечивать требуемый уровень безотказности.

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

4. Невосстанавливаемость элементов. Во время работы системы, отказавшие элементы не могут быть восстановлены.

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

Задачи исследования.

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

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

3. Создание методики поиска наилучшей структуры из ограниченного множества вариантов.

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

Методы и средства исследования. Для теоретических исследований применяются методы теории отношений, теории графов, теории надежности, логико-вероятностные методы, теории случайных процессов, математического моделирования, математического программирования. Для построения моделей устройств использовались системы автоматизированного проектирования MAX+PLUS И, Quartus II и среда программирования Microsoft Visual Studio.

Положения, выносимые на защиту.

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

2. Выделение подмножества структур ИУССН, оптимальных по комбинированному критерию надежности, безопасности и стоимости -доменных структур, включающих множество независимых узлов доменов с голосующим устройством на входе каждого.

3. Методика синтеза структур ИУССН с доменной организацией.

Научная новизна работы.

1. Разработана модель структуры ИУССН - динамический типизированный граф. Модель обладает возможностью рассматривать на функциональном уровне процессы распространения отказов и полнотой представления множества вариантов структуры ИУССН. Разработана программа расчета вероятности безотказной работы системы по динамическому типизированному графу.

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

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

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

4. Выделен новый класс из множества доменных структур ИУССН -масштабируемые структуры с резервированием. Главное преимущество данного класса структур заключается в возможности увеличения надежности системы путем увеличения числа однотипных устройств без изменения структуры голосующих устройств.

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

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

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

Практическая значимость работы. Полученные в диссертационной работе методики синтеза и анализа структур позволяют снизить трудоемкость и повысить качество проектирования, а также обосновать t правильность принятых решений на системном этапе проектирования. С использованием предложенных методик разработан прототип ИУССН на основе СБИС ПЛ. Он позволяет проводить экспериментальные исследования в системном окружении и трансформировать разработанные блоки на отечественную базу БМК. Результаты диссертационной работы могут быть использованы в проектных организациях при создании отказоустойчивых вычислительных систем, а также в соответствующих дисциплинах при обучении студентов.

Реализация результатов работы. Результаты, полученные в диссертации, используются в учебном процессе на кафедре автоматики и вычислительной техники ГОУ ВПО «СПбГПУ» при чтении лекций по курсу * «Проектирование аппаратных средств вычислительных систем», а также при выполнении практических занятий на экспериментальной установке системы-прототипа, спроектированной с использованием теоретических результатов работы.

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

1. Разработка методики и инструментария для проектирования и верификации высоконадежных специализированных процессоров на базе СБИС ПЛ. Программа министерства образования РФ, подпрограмма «Международное научно-образовательное сотрудничество», проект №1283 за 2003 год.

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

Р СБИС ПЛ. Программа министерства науки и образования РФ, федерального агентства но образованию «Федерально-региональная политика в науке и образовании», подпрограмма «Международное t научно-образовательное сотрудничество», проект №1647 за 2004 год.

3. Создание центра по коммерциализации разработок Санкт-Петербургского государственного политехнического университета в области проектирования радиоэлектронной аппаратуры с использованием технологий FPGA и ASIC. Программа министерства науки и образования РФ, федерального агентства по образованию «Развитие научного потенциала высшей школы», подпрограмма 3 «Развитие инфраструктуры научно-технической и инновационной деятельности высшей школы и ее кадрового потенциала» на 2005 год.

4. Развитие центра трансфера технологий проектирования AS1C/FPGA на базе Санкт-Петербургского государственного политехнического университета для промышленности региона. Программа и подпрограмма п. 3, 2005 год.

5. Развитие международного центра трансфера технологий проектирования ASIC на базе Санкт-Петербургского государственного политехнического университета. Программа и подпрограмма п. 3,2005 год.

Апробация работы. Результаты работы докладывались и обсуждались на VIII Всероссийской конференции «Фундаментальные исследования в технических университетах» (2004 год) и на ежегодной конференции «Практические аспекты разработки отечественных СБИС класса «система на кристалле»» (2006 год).

Публикации. По результатам диссертационной работы опубликовано шесть печатных работ, в том числе в журнале «Научно-технические ведомости СПбГТУ» (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»). Всего I опубликовано три журнальных статьи и три тезиса конференций.

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

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

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

2. На множестве динамических типизированных графов определено отношение порядка по комбинированному критерию надежности, безопасности и стоимости (раздел 3.1). Доказано, что динамические типизированные графы из множества максимальных элементов для данного отношения могут быть разбиты на непересекающиеся узлы доменов - ациклические связные подграфы без однотипных начальных вершин, связанные друг с другом начальными и конечными вершинами и обладающие возможностью сдерживать процессы распространения отказов (разделы 3.2,3.3).

3. В множестве доменных структур выделен класс новых структур -масштабируемые структуры с резервированием, позволяющие повышать уровень надежности без изменения используемых блоков (подраздел 3.3.8).

4. Разработана программа расчета вероятности безотказной работы системы по динамическому типизированному графу. На примерах показана простота применения программы и корректность ее результатов (раздел 4.1). Проанализировано влияние количества доменов, варианта разбиения системы на домены, характеристик доменов на показатели надежности системы, сформулированы основные правила разбиения системы на домены (раздел 4.2). Сформулирована методика синтеза вычислительных систем с доменной структурой и рассмотрены условия ее применимости (раздел 4.3).

5. Разработана структура прототипа информационно-управляющей системы * специального назначения и определены функциональные спецификации к ее блокам. Обоснован—функциональный" состав системы-прототипа, предназначенной для экспериментальной проверки теоретических положений по синтезу структур вычислительных систем с резервированием (разделы 5.1, 5.2).

Определены ближайшие задачи дальнейшей работы. Дальнейшее развитие диссертационной работы предполагает.

1. Синтез отдельных устройств системы-прототипа, сборку системы-прототипа и последующее экспериментальное исследование. Решение сформулированных в разделе 5.4 проблем. Анализ основных проблем доменной организации, указанных выше, исследование эффективности различных способов их разрешения на базе системы-прототшта. Исследование возможности использования устройств системы-прототипа в составе информационно-управляющей системы специального

I назначения.

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

ЗАКЛЮЧЕНИЕ

1. ГОСТ 27.002-89. Надежность в технике. Основные понятия, термины и определения. М.: Изд-во стандартов, 1989. - 39 с.

2. ГОСТ ЕН 1070-2003. Межгосударственный стандарт. Безопасность оборудования. Термины и определения. М.: Изд-во стандартов, 2003. -23 с.

3. ГОСТ ИСО/ТО 12100-1-2001. Межгосударственный стандарт. Безопасность оборудования. Основные понятия, общие принципы конструирования. Часть 1. Основные термины, методика. М.: Изд-во стандартов, 2001. - 17 с.

4. Надежность в технике. Выбор способов и методов резервирования. * Рекомендации Р50-54-82-88. М.: Изд-во стандартов, 1988. - 94 с.

5. Авен О.И., Гурин Н.Н., Коган А.Я. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.-464 с.

6. Акимов О.Е. Дискретная математика: логика, группы, графы. М.: Лаборатория базовых знаний, 2003. - 376 с.

7. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов: Учебное пособие. М.: МГУ, 2000. - 59 с.

8. Антонов А.П. Язык описания цифровых устройств AlteraHDL. СПб.: Радиософт, 2001.-224 с.

9. Антонов А.П., Мелехин В.Ф., Филиппов А.С. Обзор элементной базы фирмы Altera. СПб.: ЭФО, 1997. - 142 с.

10. Ю.Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и микропроцессорных систем. М.: PC, 1991.-248 с.

11. Берж К. Теория графов и ее применения: Пер. с франц. М.: ИЛ, 1962. -( 320 с.

12. Воеводин В.В., Воеводин Вл.В. Параллельные системы. СПб.: БХВ-Петербург, 2002. - 600 с.

13. Ганнетт Дж., Томич А., Катевенис М. и др. Электроника СБИС. Проектирование микроструктур: Пер. с англ. / Под ред. Н. Айспрука. М.: Мир, 1989.-256 с.

14. М.Глухих М.И. Расчет показателей надежности по модели структуры вычислительной системы // Вычислительные, измерительные и управляющие системы: сборник научных трудов / под ред. Ю.Б. Сениченкова. СПб.: СПбГПУ, 2005. - С. 57-64.

15. Глухих М.И., Максименко С.Л., Мелехин В.Ф. Методология и инструментальные средства создания специализированных процессоров // XXIX неделя науки СПбГТУ. Часть V: Материалы межвузовской научной конференции. СПб.: СПбГТУ, 2000. - С. 36-38.

16. Глухих М.И., Мелехин В.Ф. Разработка и исследование * специализированного процессора для отказоустойчивой системы // XXXюбилейная неделя науки СПбГТУ. Часть VII: Материалы межвузовской научной конференции. СПб.: СПбГТУ, 2001. - С. 152.

17. Глухих М.И., Мелехин В.Ф. Методика анализа эффективностиархитектуры процессора // XXXII неделя науки СПбГПУ. Часть V:

18. Материалы межвузовской научно-технической конференции. СПб.: СПбГПУ, 2003.-С. 76-78.

19. Гнеденко Б.В., Беляев Ю.К., Соколов А.Д. Математические методы теории надежности. М.: Наука, 1965. - 524 с.

20. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: PC, 1995.-320 с.

21. Горский JI.K. Статистические алгоритмы исследования надежности. М.: Наука, 1970.-400 с.

22. Евстигнеев В.Н., Касьянов В.А. Толковый словарь по теории графов. -Новосибирск: НГУ, 1996.-291 с.

23. Иванова А.П., Сигал И.Х. Введение в прикладное дискретное программирование. М.: Физматлит, 2002. - 240 с.

24. Иыуду К.А. Оптимизация устройств автоматики по критерию надежности. -М.: Энергия, 1966.

25. Колесников Е.Д., Мирончиков Е.Т. Декодирование циклических кодов. -М.: Связь, 1968.-251 с.

26. Колмогоров А.Н. Об аналитических методах в теории вероятностей // УМН.- 1938. №5.-С. 5-41.

27. Колосов В.Г., Мелехин В.Ф. Проектирование узлов и систем автоматики и вычислительной техники. JL: Энергоатомиздат, 1983. - 256 с.

28. Кузьмин Ф.И. Задачи и методы оптимизации показателей надежности. -М.: Сов. радио, 1972. 224 с.

29. Курочкин Ю.А., Смирнов А.С., Степанов В.А. Надежность и диагностирование цифровых устройств и систем. СПб.: Издательство СПбГТУ, 1993.-320 с.

30. Макаров С.В. Вероятностные расчеты однотактных схем // * Вычислительные системы. 1962. Вып. 4.

31. Марков А.А. Исследование замечательного случая зависимых испытаний // Известия Петербургской академии наук. 1907. Том 1. №3. С. 61-80.

32. Мелехин В.Ф. Вычислительные машины, системы и сети: Учебник для вузов / В.Ф. Мелехин, Е.Г. Павловский. М.: Издательский центр «Академия», 2006. - 555 с.

33. Мерекин Ю.В. Решение задач вероятностного расчета однотактных схем методом ортогонализации // Вычислительные системы. 1962. Вып. 5.

34. Алгоритмы и программы решения задач на графах и сетях / Под ред. Нечепуренко М.И. Новосибирск: Наука, 1990. - 520 с.

35. Нечипоренко В.И. Структурный анализ систем. М.: Сов. радио, 1977. -216с.

36. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, ► 2000.-301 с.

37. Носов В.А. Комбинаторика и теория графов: Учебное пособие. М.: МГТУ, 1999.- 116 с.

38. Ope О. Теория графов: Пер. с англ. М.: Наука, 1980. - 336 с.44.0ре О. Графы и их применение: Пер. с англ. М.: Мир, 1965. - 175 с.

39. Парфенов Ю.М. Надежность, живучесть и эффективность корабельных энергетических систем. Л.: ВМА, 1989. - 324 с.

40. Пирс У. Построение надежных вычислительных машин. М.: Мир, 1968. -270 с.

41. Половко A.M. Основы теории надежности. М.: Наука, 1964. - 447 с.

42. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1964.-368 с.

43. Поспелов И.Г. Разработка и исследование методов анализа и обеспечения отказоустойчивости управляющих иерархических вычислительных систем реального времени. Дис. . канд. техн. наук. М.: 2002. - 156 с.

44. Рудометов Е., Рудометов В. Архитектура ПК, комплектующие,мультимедиа. СПб.: Питер, 2000. - 416 с.

45. Рябинин И.А. Надежность и безопасность структурно-сложных систем. -СПб.: Политехника, 2000. 248 с.

46. Рябинин И.А. Основы теории и расчета надежности судовых энергетических систем. Л.: Судостроение, 1967. - 362 с.

47. Рябинин И.А., Парфенов Ю.М. Определение «веса» и «значимости» * отдельных элементов при оценке надежности сложной системы // Изв. АН СССР. Энергетика и транспорт. - 1978. №6. - С. 22-32.

48. Рябинин И.А., Смирнов А.С. Схемно-логический метод исследования структурной надежности сложных невосстанавливаемых систем // Электричество. 1971. №5.

49. Рябинин И.А., Черкесов Г.Н. Логико-вероятностные методы исследования надежности структурно-сложных систем. М.: Радио и связь, 1981. - 264с.

50. Сенин Д. Использование технологии кластеризации в сетях хранения данных // RM magazine. 2004. #4/5. - С. 66-69.

51. Трайон Д. Четырехкратная логика / Методы введения избыточности для вычислительных систем: Пер. с англ. / Под ред. В. С. Пугачева. М.: Сов. радио, 1966.-С. 241-265.

52. Федотов Я. Проблемы интегральной электроники // Электронные компоненты. 2000. №3. - С. 8-11.

53. Финк JT.M. Теория передачи дискретных сообщений. М.: Сов. радио, 1963.-576 с.бО.Французов Д. Оценка производительности вычислительных систем // Открытые системы. 1996. №2. - С. 58-66.

54. Черкесов Т.Н. Надежность аппаратно-программных комплексов. СПб.: Питер, 2005.-480 с.

55. Черкесов Т.Н., Можаев А.С. Логико-вероятностные методы расчета надежности структурно-сложных систем // Качество и надежность изделий. Вып. 3 (15).-М.: Знание, 1991.-С. 3-65.

56. Черкесов Т.Н., Степанов Ю.В. Логико-вероятностный анализ надежности сложных систем на основе общего решения систем логических уравнений // Научно-технические ведомости СПбГТУ. 2003. №2. - С. 149-158.

57. Черноруцкий И.Г. Методы принятия решений. СПб.: БХВ-Петербург, 2005.-416 с.

58. Шеннон К. Математическая теория связи // Работы по теории информации и кибернетике: Пер. с англ. / Под ред. Р.Л. Добрушина и О.В. Ляпунова. -М.: ИЛ, 1963.-С. 243-332.

59. Avalon bus interface // Altera corporation, 2005. 90 p.

60. Nios development board. Reference manual, Stratix edition // Altera corporation, 2004. 52 p.

61. Nios II processor reference handbook // Altera corporation, 2004. 212 p.

62. Stratix device handbook (complete two-volume set) // Altera corporation, 2004.- 866 p.

63. Armstrong D.B. A General Method of Applying Error Correction to Synchronous Digital Systems // Bell Systems Technical Journal. 1961. #40. Pp. 577-593.

64. Chatelet E., Chu C., Yalaoui A. A new dynamic programming method for reliability and redundancy allocation in a parallel-series system // IEEE Transactions on Reliability, Vol. 54, #2, Jun. 2005. Pp. 254-261.

65. Forney G.D., Jr. Convolutional codes I: Algebraic structure // IEEE Trans. Inform. Theory. Vol. IT-16, Sept, 1970. - Pp. 720-738.

66. Glover F., Laguna M. Tabu search // Kluwer Academic Publishers, Boston, Hardbound. July 1997. - 408 pp.

67. Golay, Marcel J.E. Notes on Digital Coding // Proceedings of the IRE. Vol. 37, June, 1949.-Pp. 657.

68. Hamming R.W. Error Detecting and Error Correcting Codes // The Bell System

69. Technical Journal. 1950. #29. - Pp. 147-161.

70. Heimendinger W., Weinstock C. A conceptual framework for system fault tolerance. Pittsburgh (PA): Carnegie Melon University, 1992. - 36 p.

71. Johnson Y. The analysis of two fault-tolerant architectures using safety related metrics // International conference on dependable systems and networks. -2003.

72. Kuo W., Rajendra Prasad V. An Annotated Overview of System-Reliability Optimization // IEEE Transactions on Reliability, Vol. 49, #2, Jun. 2000. Pp. 176-187.

73. Levitin G. Consecutive k-Out-of-r-From-n Systems With Multiple Failure Criteria // IEEE Transactions on Reliability, Vol. 53, #3, Sep. 2004. Pp. 394400.

74. Levitin G., Lisnianski A., Ben-Haim H., Elmakis D. Redundancy Optimization I for Series-Parallel Multi-State Systems // IEEE Transactions on Reliability,

75. Vol. 47, #2, Jun. 1998. Pp. 165-172.

76. Liang Y., Smith A. An ant colony optimization algorithm for the redundancy allocation problem // IEEE Transactions on Reliability, Vol. 53, #3, Sep. 2004. -Pp. 417-423.

77. Single/dual LVDS line receivers with in-path fail-safe // Maxim integrated products. 2002. - 11 p.

78. A general design guide for national's low voltage differential signaling (LVDS) and bus LVDS products: LVDS owner's manual, 2nd edition // National semiconductor, 2000.- 101 p.

79. Pierce W.H. A Proposed System of Redundancy to Improve the Reliability of Digital Computers: Technical Report #1552-1 // Stanford University, Stanford Electron. Labs. 1960.

80. Pierce W.H. Improving Reliability of Digital Systems by Redundancy and Adaptation. PhD thesis. Electrical Engineering, Stanford University. 1961.

81. Pierce W.H. Interwoven Redundant Logic // J. Franklin Institute. 1964. #277. -Pp. 55-85.

82. Rennels D. Fault-Tolerant Computing Concepts and Examples // IEEE Transactions on Computers C-33. #12. Dec. 1984. - Pp. 1116-1129.

83. Rodrig M., LaMarca A. Decentralized weighted voting for P2P data management // MobiDE, 2003. Pp. 85-92.

84. Scheuer E.M. Reliability of an m-out-of-n System When Component Failure Induces Higher Failure Rates in Survivors // IEEE Transactions on Reliability, Vol. 37, #1, Apr. 1988.-Pp. 73-74.