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

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

УДК 681.324

Майданов Юрий Сергеевич

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

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

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

Новосибирск - 2004

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

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

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

член-корреспондент РАН Хорошевский Виктор Гаврилович

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

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

Попков Владимир Константинович

кандидат технических наук Зыбарев Юрий Михайлович

Ведущая организация -

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

Защита состоится "_" декабря 2004 г. в 10 часов на заседании

Диссертационного совета Д219.005.02 при ГОУ ВПО "Сибирский государственный университет телекоммуникации и информатики", по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО "СибГУТИ".

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

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

Диссертационного совета Д219.005.02 кандидат технических наук, доцент

Общая характеристика работы

Актуальность проблемы. Потребность в высокопроизводительных средствах обработки информации привела к созданию распределенных вычислительных систем (ВС). В общем случае, функциональная структура распределенных ВС представляется композицией из элементарных машин (ЭМ) и коммуникационной сети. Все основные ресурсы таких систем (не только арифметико-логические устройства, но и память, средства управления и коммуникационная сеть) являются логически и технически распределёнными. Число ЭМ уже в современных распределенных ВС допускает варьирование от нескольких единиц до 10б (например, в российской системе МВС-1000М это число равно 768, а в создаваемой системе IBM Blue Gene должно достигнуть 1 000 000). Распространенный режим функционирования распределенных ВС -монопрограммный, в нем все ресурсы используются для решения одной задачи. Распределенные ВС, обладая колоссальными вычислительными ресурсами, должны эффективно работать и в мультипрограммных режимах. В последнем случае ресурсы ВС делятся между несколькими задачами. Существует класс задач, где ВС применяются в качестве средств управления, и их отказ может повлечь за собой серьезные экономические потери, экологические катастрофы и даже человеческие жертвы. Поэтому для решения таких задач необходимо чтобы ВС обладали свойством живучести, т.е. способностью продолжать вычисления даже при отказе части ресурсов. Одними из самых важных этапов в организации живучего мультипрограммного функционирования распределенных ВС являются контроль и диагностика, позволяющие своевременно обнаружить наличие отказов и локализовать неисправные ресурсы. Из сказанного следует актуальность проблем повышения эффективности использования ресурсов распределенных ВС за счет параллельного мультипрограммирования и создания децентрализованных средств обнаружения отказов и локализации неисправностей.

Исследования в области распределенных вычислительных систем ведутся с 1960-х годов. В нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам разработки высокопроизводительных вычислительных средств: проведены исследования по организации функционирования и оптимизации (макро)структур ВС, проработаны многие аспекты разработки программного обеспечения, исследован широкий круг задач, допускающий эффективную реализацию на распределённых ВС. В качестве примеров можно привести отечественные системы "Минск-222", СУММА, МИНИМАКС, семейства систем МИКРОС и МВС.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П.Балашов, В.Б.Бетелин, В.С.Бурцев, В.В.Васильев, В.М.Вишневский, В.В.Воеводин, В.М.Глушков, В.Ф.Евдокимов Э.В.Евреинов, А.В.Забродин, В.П.Иванников, М.Б. Игнатьев, А.В.Каляев, М.А.Карцев, Л.Н.Королев, Н.А.Кузнецов, В.Г.Лазарев, С.А.Лебедев, В.К.Левин, Г.И.Марчук, Ю.И.Митропольский, В.К.Попков, Д.А.Поспелов, И.В.Прангишвили, Д.В.Пузанков, Г.Е.Пухов,

Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко и другие.

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

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

К основным задачам исследований относятся:

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

ВС;

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

-построение процедур определения технического состояния ВС на основе результатов взаимотестирования элементарных машин;

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

- реализация программных средств оценки технического состояния ВС.

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

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

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

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

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

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

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

5. Функциональная структура пространственно распределенной мультикластерной вычислительной системы и программные средства мультипрограммирования и поддержки живучести ВС.

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

Оригинальные параллельные алгоритмы распределения пакетов задач по элементарным машинам ВС позволяют на этапе планирования вычислений вводить операции контроля и диагностики.

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

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

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

Мультикластерная ВС и созданное программное обеспечение используются для исследований в области распределенной обработки информации и в учебном процессе СибГУТИ.

Реализация и внедрение. Результаты диссертации применены в распределенной мультикластерной вычислительной системе Центра параллельных вычислительных технологий СибГУТИ (см. рис. 3). Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-09380, 03-07-06008, 02-0390379. Основные положения диссертационной работы использовались автором при разработке и чтении учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Отказоустойчивые вычислительные системы», «Операционные системы» и «Организация ЭВМ и систем».

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

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

• Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2001, 2002 гг., г. Новосибирск);

• Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003 г., г. Геленджик);

• Международной научно-технической конференции "Информационные системы и технологии" (2003 г., г. Новосибирск);

• Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., г. Москва);

• Региональной научной конференции студентов, аспирантов и молодых ученых «Наука. Техника. Инновации» (2003 г., г. Новосибирск);

• Школе-семинаре «Распределённые кластерные вычисления» (2001 г., г. Красноярск).

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

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

Содержание работы

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

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

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

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

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

Решение прикладной задачи описывается графом Б = (Ж,Р, Г) информационных связей фрагментов задач. Множество его вершин №={ц>} соответствует множеству фрагментов программ. Наличие в графе дуги (м>,,Щ) еГ говорит о том, что результаты выполнения фрагмента используются в качестве исходных данных в фрагменте Каждой вершине графа приписан некоторый вес р.е Р, соответствующий времени выполнения данного фрагмента. При

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

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

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

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

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

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

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

Любой план работы распределенной живучей ВС должен удовлетворять следующим требованиям:

{к^еГ^^-^гр,-, (1)

(3)

где ^ - время начала выполнения фрагмента п - количество элементарных машин ВС; , Тд - время начала и окончания q-го цикла диагностирования; р1 -вес ;-ой вершины Б = (Ж, Р, Г), соответствующий времени выполнения

{1, если в момент времени к машина и, решает щ, О, в противном случае.

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

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

Решена задача формирования диаграммы загрузки ВС при ограниченном времени диагностирования (Тд Т^), минимизируется время решения (V»шп).

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

Аналогичная задача решена для систем с использованием парных диагностических проверок. В этом случае при формировании диаграммы загрузки должно учитываться еще одно ограничение:

УкУще Ш £/>,,(£) 5 2,

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

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

вычислительной системы, учитывающей диагностические операции, показана на рис.1. Расчеты проводились на основе графа, количество вершин которого - 800, количество ребер - 20000.

Количество элементарных мшив В алгоритм 2, алгоритм 1

Рис. 1. Зависимость коэффициента ускорения от числа элементарных машин

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

0-1--- ■ * , ■ ..........

1 3 5 7 9 11 13 15 17 19

Количество элементарных машин

• алгоритм 2. —алгоритм 1

Рис. 2. Зависимость времени построения диаграммы загрузки ВС от числа элементарных машин

Разработаны методы решения задачи формирования диаграммы загрузки ВС с минимальным временем диагностирования (Тд-) min) при ограниченном времени решения (Т й Ттш). Формируемая при этом диаграмма загрузки также должна удовлетворять ограничениям (1-3).

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

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

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

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

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

где 0 - диаграмма загрузки , т - количество связей диагностического графа, X -время цикладиагностирования, /(т, у) - функция, которая показывает занятость ] - ой элементарной машины на Т-м такте работы системы в диагностических процедурах и определяется как

{1, если в такте т машина и1 задействована в диагностике,

О, в противном случае.

При проведении парных элементарных проверок независимо от специфики задачи, графа информационных связей фрагментов задач и диагностического графа, функция Щ), т, X) неизменно принимает значение ¿(2, т,Х) = Ь\ = 2.

КТ,}) =

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

сравнений. Число mi соответствует проведению всех возможных элементарных проверок между этими r + 1 элементарными машинами.

Тогда функция L(Q, m, А,) принимает следующее значение:

где

_ in-F(î)+1, прип-F(t)>О,

74 [ 0, при и - Fir) = О

Функция плотности загрузки системы F(y показывает количество

элементарных машин, загруженных решением фрагментов задачи в момент времени т.

Несложно показать, что L2 <L1 для любой диаграммы загрузки системы. Если в данной диаграмме загрузки находится такой такт работы, на котором более двух элементарных машин не заняты решением прикладной задачи, то L2 < L1.

На основании вышеизложенного предложен следующий метод проведения взаимных тестов между элементарными машинами. В вычислительной системе выделяется множество элементарных машин Tf" s U, | С/**' | = г. Все элементарные машины из множества загружаются одинаковыми исходными данными, соответствующими некоторому фрагменту wt прикладной задачи W. После независимой обработки исходных данных элементарными машинами м,€ lfesl получают множество результатов решения О ={о,}, где \ 0\ = г. Любое парное сравнение полученных результатов ot , os е О, i * j, может быть рассмотрено как элементарная проверка, соответствующая ребру диагностического графа (и„ и) еГ, результатом которой является «О», если ot = os и «1» в противном случае.

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

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

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

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

mi г. ^ Н — ^шаха

где пшЛ - минимальнее количество элементарных машин, необходимых для решения прикладной задачи; пш11 - максимальное количество исправных элементарных машин в вычислительной системе.

Ширина поля «состояние» определяется диагностическим графом с максимальным количеством вершин. Поле «синдром» зависит от конфигурации используемых диагностических графов.

Обозначим как G = (Г' , U'') диагностический граф, используемый в системе из i элементарных машин, где птЛ < / < пщш.

Если в графе G = <j"mn) U...U Ср U tf"0 U...U G1"""' будет минимальное количество связей, то минимальным также будут ширина поля «синдром» и общий объем памяти, необходимый для хранения таблицы неисправностей.

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

Предложенный подход предполагает использование диагностических графов,

построенных по следующим правилам: _

U={u,}, / = 1,и; (ии Uj) s Го (/ + и - г) mod и < s / 2; где п - количество вершин диагностического графа, s = deg(U') = const - локальная степень вершин графа.

При построении таблицы неисправностей, общей для графов G'+1) и G'', сначала предлагается сформировать ее для и затем дополнить столбцами,

соответствующими тем связям, которые есть в графе Cf', но отсутствуют в Gf'+1) Таблица будетдополненаг = ]Г'\ Tl+1')| столбцами. Очевидно, что z = s/2.

Для каждой конкретной диагностической модели можно показать, что максимальную степень диагностируемом^ обеспечивает граф G ""''. При этом U'> U , если i < nmax. Поэтому количество строк е1 в таблице определяется количеством допустимых состояний системы с использованием этого графа:

•■I.

Ширина с2 поля «синдром» определяется следующим образом: С2 = s * Птгх—S * Ищщ / 2.

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

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

Однако некоторые модем допускают неоднозначность результата элементарной проверки (0,1 или X - неопределенно). В этом случае для кодирования одного элемента потенциального синдрома необходимо с3 - 2 битов информации. Для таких моделей объем необходимой памяти составляет

С32 =1С' (2 *"тт+ Ищи)-

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

Очевидно, что С21 > С31, С22 > С32, и, следовательно, предлагаемый способ хранения таблицы потенциальных синдромов требует меньших затрат памяти по сравнению с традиционным методом.

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

(и, е Ц"лике еЦ"лике {/")л(иу€ Vяли, е 1Гще Или^. Vй), (8) то sj = sы. Здесь sj - результат элементарной проверки, соответствующей дуге диагностического графа (и, и), V - множество исправных элементарных машин, V - множество неисправных элементарных машин.

Рассмотрим два диагностических графа 01 = (и,, Т) и 02= (V, Т). Допустим, что каждой связи (и„ и) еТ1 поставлена в соответствие связь (и„ Тт Совпадение значений соответствующих элементов синдромов и 82 гарантируется только в том случае, если для каждой связи (и„ иг)е Т1 выполняется условие (8). Это означает, что для каждой вершины и1 существует множество [/'"(и) = {и), где [/'"(и) с {/ все элементы которого должны находиться в том же состоянии, что и элементарная машина (и). Тогда соответствие между синдромом 81 для 01 и 82 для 02 можно представить в виде функции = Р(8).

Равенство соответствующих элементов синдромов может быть выполнено дня любого допустимого значения Sp если для любых различных ut, и выполняется условие if^iu) n if^fuj) = 0.

Тогда дешифрация синдрома St может быть произведена выбором из таблицы неисправностей для G2 строки, удовлетворяющей следующим двум требованиям:

УщУи^це if** (и,) => и, е If л Uj€ Ifv и,е Улце If.

В качестве графа G2 предлагается использовать несвязанный граф G - (Ua, Т), для которого | Ua\ = nmti + s. Связь между его вершинами ut, и и существует только в том случае, если выполняются одно из следующих условий:

(иавх<1< Ита^ i / 2 ) Л ( игах+ s/2<j ).

Граф Ga состоит из двух компонент связности (подграф G, построенный на вершинах и.... ипmax) и подграф G,, включающий остальные вершины).

При таком способе задания Ga может быть определено соответствие связей Та и любого диагностического графа (G"n = (U<nn,Tnn) из множества предусматриваемых к использованию графов G" max) ... G" mm). Такое соответствие можно определить следующим образом:

- для любой дуги (u, и) вТ"", где 0 < i -j < s / 2, выполняется требование (»• »)€(/ "»О Г):

-каждой дуге (и„ ¡ф Тп>, где i + n-j<s/2, ставится в соответствие связь

(Un-j+n max* Un max+fe+i^ Ta

Для графа Gt строится таблица потенциальных синдромов. Объем памяти, необходимой для хранения такой таблицы, составит

с= XCL -(5/2)2 + s/2 + nmx) + min {2*, ic^ } *((s/2? + s/2).

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

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

F(b, b2, ...,b"),

где b- это двоичная переменная, обозначающая техническое состояние и..

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

F(b,, b,, ...,b)=\.

Вычислительная сложность алгоритма определяется размером выражения F и оценивается как 0(3 т n/t!), где п - количество элементарных машин ВС, т -

171 - количество связей диагностического графа, t - оценка меры диагностируемости для данного диагностического графа G.

Для диагностических моделей (0,1,0,0), (0,1,0,1), (0,1,0,Х), (0,1,1,1) и (0,1,1,0) разработаны алгоритмы ускоренной дешифрации синдрома системы. Их применение позволит сократить трудоемкость процесса определения технического состояния системы за счет учета частных свойств используемой модели.

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

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

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

Таким образом, если возможно выделить такое множество элементарных машин Up что |[/i[>/ и при выполнении коллективных проверок все элементарные машины up Uj получают одинаковые результаты, то все «(е Uj исправны, т.е. Ujcff. Эти элементарные машины могут образовать диагностическое ядро. В последующих коллективных проверках все элементарные машины, получающие такие же результаты, как и элементарные машины, входящие в диагностическое ядро, считаются исправными и включаются в состав ядра. Неисправные элементарные машины получают другие результаты (отличные от полученных в диагностическом ядре).

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

В четвертой главе описана архитектура и программное обеспечение пространственно-распределённой мультикластерной вычислительной системы, эксплуатируемой Центром параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (ЦПВТСибГУТИ).

Система представляется совокупностью сосредоточенных кластеров, часть из которых располагается в ЦПВТ СибГУТИ, а другая часть - в Сибирском отделении РАН.

ВС ЦПВТ СибГУТИ состоит из 4 сегментов, каждый их которых (в свою очередь) является сосредоточенным многомашинным кластером. Любой из сегментов способен функционировать как автономно, так и в составе ВС (рис. 3).

Кластеры созданы на основе стандартных персональных компьютеров (ПК) на базе процессоров семейства Intel. Все ПК оборудованы собственной оперативной памятью, сетевым адаптером стандарта Fast Ethernet (максимальная

скорость передачи данных 100 Мбит/с), клавиатурой, манипулятором типа «мышь», жестким диском, видеоадаптером и монитором. Для организации сети передачи данных используются четыре коммутатора (switch) фирмы 3COM, использована топология типа "звезда", соединение организовано с помощью медного кабеля «витой пары» категории 5.

Рис. 3. Архитектура пространственно-распределённой мультикластерной ВС

Кластеры имеют выходы в Internet и модемные соединения с телефонной линией, что позволяет осуществлять взаимодействие с другими системами (в частности, друг с другом). Связь осуществляется через один из ПК кластера ЦПВТ СибГУТИ и один ПК системы ИФП СО РАН, которые также могут выполнять функции серверов (файловых или приложений) для всей системы.

Кластерная ВС допускает масштабирование и способна взаимодействовать с множеством другим кластеров. Все персональные компьютеры функционируют под управлением ОС Linux (дистрибутив ASPLinux v.9.2, ядро 2.4.26). Для разработки и реализации параллельных программ используется технология MPI (реализация LAM v.7.0.2 или MPICH v. 1.2.0).

Для межкластерных взаимодействий через телефонный канал используется пакет программ, реализующий протокол взаимодействия Point-to-Point (PPP). В состав программного обеспечения также входят компоненты (ssh, telnet), позволяющие получить удаленный доступ к кластеру.

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

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

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

ьеккщдные программы!

.1

диспетчер распределенных ресурсов

—

средства параллельного программирования • диагнййтйческие средства подсистема

анализа

) "1 рекокфигуратор системы эффективности

_ 1 — ' —

средства межмашинного взаимодействия

сетевые протоколы _ _ _ * " 1 ___________ !

операционная система

Рис. 4. Структура ПО живучей кластерной системы

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

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

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

В приложениях представлены исходные тексты разработанных библиотек программ.

Основные результаты работы

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

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

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

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

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

1.4. Осуществлено моделирование алгоритмов мультипрограммирования на распределенной ВС и оценена их эффективность.

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

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

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

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

Список публикаций

1. Хорошевский В.Г., Мамойленко С.Н., Майданов Ю.С. Смирнов СВ. Об организации функционирования кластерных вычислительных систем // Автометрия. -2004. - № 1. -С. 41 -51.

2. Майданов Ю.С. Подходы к организации контроля, диагностики и реконфигурации структуры вычислительных систем // Материалы Международной научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск. - 2001. С. 86-88.

3. Хорошевский В.Г., Майданов Ю.С. Средства самодиагностики кластерных вычислительных систем // Труды школы-семинара «Распределённые кластерные вычисления». - Красноярск. - 2001. - С. 105-109.

4. Хорошевский В.Г., Майданов Ю.С, Мамойленко С.Н., Павский К.В. Живучая кластерная вычислительная система // Труды школы-семинара «Распределённые кластерные вычисления». - Красноярск. - 2001. - С. 109-113.

5. Майданов Ю.С. Формирование базиса для исследования децентрализованных алгоритмов самодиагностики кластерных вычислительных систем // Материалы Международной научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск. - 2002. С 130131.

6. Майдановз Ю.С. Программный инструментарий исследования средств самодиагностики кластерных вычислительных систем // Тезисы Научно-методической конференции СибГУТИ «Основы и сущность междисциплинарной организации образования». - Новосибирск. - 2002. - С. 38-40.

7. Мамойленко С.Н., Майданов Ю.С. Разработка аппаратно-программного инструментария для моделирования большемасштабных вычислительных систем // Тезисы Научно-методической конференции СибГУТИ «Основы и сущность междисциплинарной организации образования». - Новосибирск. - 2002. — С. 3637.

8. Мамойленко С.Н., Майданов Ю.С. Развитие кластерной вычислительной системы // Тезисы Научно-методической конференции СибГУТИ «Основы и сущность междисциплинарной организации образования». - Новосибирск. - 2003. - С. 19-20.

9. Хорошевский В.Г., Мамойленко С.Н., Майданов Ю.С. Распределённые кластерные вычислительные системы // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы». -Геленжик. - том. 1 - С. 36-38.

10. Хорошевский В.Г., Мамойленко С.Н., Майданов Ю.С. Живучие кластерные вычислительные системы // Материалы Первой всероссийской научной конференции «Методы и средства обработки информации». - МГУ. -2003.-С. 148-150.

11. Майданов Ю.С. Оптимизация проведения диагностических операций в параллельных вычислительных системах // Материалы докладов всероссийской научной конференции молодых ученых «Наука технологии инновации». -Новосибирск.-2003.-С. 16-18.

12. Khoroshevsky V.G., Mamoilenko S.N., Maidanov Y.S., Smirnov S.V. Robust cluster computer systems // Optoelectronics, instrumentation and data processing, vol. 40, no 1,2004, pp. 41-51.

»23472

Майданов Юрий Сергеевич Разработка и исследование средств параллельного мультипрограммирования и поддержки живучести для распределенных вычислительных систем

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

Подписано в печать "12" ноября 2004 г. Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л. 1,6, заказ № 125, тираж 140 экз, ГОУ ВПО «СибГУТИ». 630102, г. Новосибирск, ул. Кирова, 86.

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

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

1.1. Понятие о живучих вычислительных системах.

1.1.1. Функциональные структуры живучих ВС.

1.1.2. Средства поддержки живучести ВС.

1.2. Графовые модели живучих вычислительных систем.

1.3. Локализация неисправных элементарных машин в вычислительных системах.

1.4. Средства самодиагностики вычислительных систем.

1.4.1. Диагностические модели ВС.

1.5. Методы дешифрации синдрома ВС.

1.5.1. Табличный метод. ф 1.5.2. Аналитический метод.

1.6. Выводы.

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

2.1. Алгоритмы распределения параллельных задач по элементарным машинам вычислительной системы.

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

2.2.1. Последовательная версия алгоритма.

2.2.2. Параллельная версия алгоритма.

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

2.2.1. Последовательная версия алгоритма.

2.2.2. Параллельная версия алгоритма.

2.4. Алгоритм распределения задач по элементарным машинам вычислительной системы с учетом операций диагностирования.

2.5. Алгоритм распределения задач по элементарным машинам вычислительной системы при коллективных взаимопроверках элементарных машин.

2.6. Минимизация времени решения прикладных задач.

2.6.1. Использование парных диагностических взаимопроверок элементарных машин.

2.6.2. Использование коллективных диагностических взаимопроверок элементарных машин.

2.7. Динамическое распределение фрагментов задач по элементарным машинам вычислительной системы.

2.8. Алгоритм распределения задач по элементарным машинам вычислительной системы при произвольной трудоемкости фрагментов.

2.8.1 Минимизация времени диагностирования.

2.8.2 Минимизация времени решения прикладных задач.

2.9 Выводы.

ГЛАВА 3. МЕТОДЫ ОПРЕДЕЛЕНИЯ ТЕХНИЧЕСКОГО СОСТОЯНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

3.1. Формирование таблицы неисправностей вычислительной системы при их автоматической реконфигурации.

3.1.1. Структура универсальной таблицы неисправностей элементарных машин ВС.

3.1.2. Оценка объема требуемой памяти.

3.1.2. Сокращение таблицы неисправностей ВС за счет временной избыточности.

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

3.3. Аналитический метод дешифрации синдрома вычислительной системы.

3.3.1. Дешифрация синдрома ВС в реальном времени.

3.3.2. Оценка необходимых ресурсов ВС.

3.4. Алгоритмы ускоренной дешифрации синдрома вычислительной системы.

3.4.1. Методы для несимметричных диагностических моделей.

3.4.2. Методы для симметричных диагностических моделей.

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

3.6. Выводы.

ГЛАВА 4. ЖИВУЧИЕ КЛАСТЕРНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ

СИСТЕМЫ.

4 Л. Классификация кластерных вычислительных систем. Принципы построения живучих кластерных вычислительных систем.

4.2. Архитектура и программное обеспечение пространственно-распределенной мультикластерной вычислительной системы Центра параллельных вычислительных технологий СибГУТИ.

4.3. Моделирование на кластерной вычислительной системе потоков параллельных задач.

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

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

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

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

4.8. Выводы.

Актуальность проблемы. Потребность в высокопроизводительных средствах обработки информации привела к созданию распределенных вычислительных систем (ВС). В общем случае, функциональная структура распределенных ВС представляется композицией из элементарных машин (ЭМ) и коммуникационной сети; Все основные ресурсы таких: систем (не только арифметико-логические устройства, но и память, средства управления и коммуникационная сеть) являются логически и технически распределёнными. Число ЭМ уже в современных распределенных ВС допускает варьирование от нескольких единиц до 106 (например, в российской системе MBС-1000М это число равно 768, а в создаваемой системе IBM Blue Gene должно достигнуть 1 ООО ООО). Распространенный режим функционирования распределенных ВС - монопрограммный, в нем все ресурсы используются для решения одной задачи. Распределенные ВС, обладая колоссальными вычислительными ресурсами, должны эффективно работать и в мультипрограммных режимах. В последнем случае ресурсы ВС делятся между несколькими задачами. Существует класс задач, где ВС применяются в качестве средств управления, и их отказ может повлечь за собой серьезные экономические потери, экологические катастрофы и даже человеческие жертвы. Поэтому для решения таких задач необходимо чтобы ВС обладали свойством живучести, т.е. способностью продолжать вычисления даже при отказе части ресурсов. Одними из самых важных этапов в организации живучего мультипрограммного функционирования распределенных ВС являются контроль и диагностика, позволяющие своевременно обнаружить наличие отказов и локализовать неисправные ресурсы. Из сказанного следует актуальность проблем по-вышения-эффективности-использования.ресурсов-распределенных ВС за.счет-параллельного мультипрограммирования и создания децентрализованных средств обнаружения отказов и локализации неисправностей.

Исследования в области распределенных вычислительных систем ведутся с 1960-х годов. В нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам разработки высокопроизводительных вычислительных средств: проведены исследования-по организации функционирования и оптимизации (макро)структур ВС, проработаны многие аспекты разработки программного обеспечения, исследован широкий круг задач, допускающий эффективную реализацию на распределённых ВС. В качестве примеров можно привести отечественные системы "Минск-222", СУММА, МИНИМАКС, семейства систем МИКРОС и МВС.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П.Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М. Глушков, В.Ф. Евдокимов Э.В: Евреинов, А.В; Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, М.А.Карцев, Л.Н.Королев, Н.А.Кузнецов, В.Г.Лазарев, С.А.Лебедев, В.К.Левин, Г.И. Марчук, Ю.И. Митропольский, В.К.Попков, Д.А.Поспелов, И.В. Прангишвили, Д.В. Пузанков, F.E. Пухов, Г.Г.Рябов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я:А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко и другие.

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

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

К основным задачам исследований относятся:

- анализ методов организации функционирования распределенных живучих ВС;

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

- построение процедур определения технического состояния ВС на основе результатов взаимотестирования элементарных машин;

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

- реализация программных средств оценки технического состояния ВС.

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

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

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

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

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

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

5. Функциональная структура пространственно распределенной мультик-ластерной вычислительной системы и программные средства мультипрограммирования и поддержки живучести ВС.

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

Оригинальные параллельные алгоритмы распределения пакетов задач по элементарным машинам ВС позволяют на этапе планирования вычислений вводить операции контроля и диагностики.

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

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

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

Мультикластерная ВС и созданное программное обеспечение используются для исследований в области распределенной обработки информации и в учебном процессе СибГУТИ.

Реализация и внедрение. Результаты диссертации применены в распределенной мультикластерной вычислительной системе Центра параллельных вычислительных технологий СибГУТИ (см. рис. 3). Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-09380, 03-07-06008, 02-03-90379. Основные положения диссертационной работы использовались автором при разработке и чтении учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Отказоустойчивые вычислительные системы», «Операционные системы» и «Организация ЭВМ и систем».

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

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

• Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2001, 2002 гг., г. Новосибирск);

• Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003 г., г. Геленджик);

• Международной научно-технической конференции "Информационные системы и технологии" (2003 г., г. Новосибирск);

• Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., г. Москва);

• Региональной научной-конференции студентов, аспирантов-и молодых ученых «Наука. Техника. Инновации» (2003 г., г. Новосибирск);

• Школе-семинаре «Распределённые кластерные вычисления» (2001 г., г. Красноярск).

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

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

4.8. Выводы

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

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

ЗАКЛЮЧЕНИЕ

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

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

1.1. Осуществлен анализ режимов функционирования ВС и сформулированы требования к алгоритмам распределения задач по элементарным машинам.

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

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

1.4. Осуществлено моделирование алгоритмов мультипрограммирования на распределенной ВС и оценена их эффективность.

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

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

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

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

1. Авиженис А. Отказоустойчивость - свойство, обеспечивающее постоянную работоспособность цифровых систем 7/ ТИИЭР. 1978. Т. 66. № 10. С. 5-25.

2. Аксенова Г.П. Восстановление в дублированных устройствах методом инвертирования данных // Автоматика и телемеханика. 1987. № 10. С. 144-153.

3. Балакин В.Н., Барашенков В.В;, Усачев Ю.Е. Проектирование системы самодиагностирования управляющей микропроцессорной системы // УСиМ. 1984. №2. С. 39-43.

4. Балашов Е.П., Пузанков Д.В. Микропроцессоры и микропроцессорные системы: уч. пособие для ВУЗов / В.Б.Смолов. М.: Радио и связь, 1981. -326 с.

5. Барни К. Старая компьютерная архитектура фирмы Tandem на новых рынках//Электроника 1986. № 8. С. 74-77.

6. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. 256 с.

7. Баумс А.К. О планировании задач и времени реакции распределенных систем реального времени // Автоматика и вычислительная техника. 1998. № 3. С. 50-59.

8. Берников Д.В. Способ тестирования операционных устройств микропроцессоров // Известия вузов Приборостроение. 1994. № 11-12. С. 32-35. •

9. Богданов Ю.Ю. О двух диагностических моделях распределенных цифровых систем//Автоматика и телемеханика. 1986. № 8. С. 127-132.

10. Богуславский Л.Б., Ляхов А.И. Моделирование многосерверных локальных сетей // Автоматика и телемеханика. 1998. № 8. С. 109-123.

11. Буймов А.Г. Использование преобразований Уолша-Адамара для диагностирования вычислительных систем // Автоматика и вычислительная техника. 1998. № 3. С. 38-42.

12. Бурцев B.C. Параллелизм вычислительных процессов и развитие архитектур суперЭВМ. М.: ИВВС РАН, 1997.

13. Ведешенков В.А., Нестеров A.M. О двух методах дешифрации результатов диагностирования цифровых систем // Электронное моделирование. 1981. № 2. С. 53-58.

14. Ведешенков В.А. Об организации самодиагностируемых цифровых систем // Автоматика и телемеханика. 1983. № 7. С. 133-144.

15. Ведешенков В.А., Котельников В.Ю. О диагностировании неисправных модулей в цифровых системах при использовании неполных тестов // Автоматика и телемеханика. 1985. № 8. С. 122-132.

16. Власкина В.В., Лобков С.Н., Сердюченко П.Я. и др. Методика оптимального распределения заданий в отказоустойчивой многопроцессорной вычислительной системе // Автоматика и вычислительная техника. 1998. № 1. С. 30^1.

17. Галушкин А.Н., Грачев Л.В., Толстых М.М. и др. Оценка алгоритмов реконфигурации структуры вычислительных систем с MIMD архитектурой//Кибернетика. 1990. № 2. С. 35-41.

18. Генинсон Б.А., Панкова Л.А., Трахтенгерц Э.А. Отказоустойчивые методы обеспечения взаимной согласованности в распределенных вычислительных системах//Автоматика и телемеханика. 1989. № 5. С. 3-18.

19. Гессель М., Дмитриев A.B., Сапожников В.В. и др. Самотестируемая структура для функционального обнаружения отказов в комбинационных системах //Автоматика и телемеханика. 1989. № 5. С. 162-174.

20. Глушков В.М., Ющенко Е.Л. Вычислительная машина «Киев». Математическое описание. Киев: ГоС. тех. изд-во УССР, 1962. - 183 с.

21. Гобземис А. Классификация объектов распределенных систем по степени работоспособности // Автоматика и вычислительная техника. 1998. №3. С. 6065.

22. Голдберг Дж., Уэнсли Дж. X., Лэмпорт Л. и др. SIFT: Проектирование и анализ отказоустойчивой вычислительной-системы для управления.полетом летательного аппарата//ТИИЭР. 1978. Т. 10. С. 166186.

23. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995. 320 с.

24. Головкин Б.А. Исследование некоторых расписаний работы мультипроцессорных вычислительных систем // Труды МФТИ. Сер Радиотехника и электроника. 1975. № 10. С. 6574.

25. Головкин Б.А. Сравнение методов планирования параллельных вычислений в многопроцессорных системах // Известия РАН. Техническая кибернетика. 1982. № 3. С. 150162.

26. Головкин Б.А., Егисапетов Э.Г., Макеев В.Г. Программное обеспечение отказоустойчивости вычислительных систем на базе ЭВМ М-10 // Электронное моделирование. 1987. Т. 9. № 3. С. 5862.

27. Горелов О.И., Плотников Е.В. Представление открытых вычислительных сетей моделью самодиагностируемой системы с распределенным диагностическим ядром // Автоматика и вычислительная техника. 1983. № 4. С. 6470.

28. Горелов О.И., Плотников Е.В. Анализ степени диагностируем ости открытых вычислительных сетей // Автоматика и вычислительная техника. 1983. №6. С. 6166.

29. Горелов О.И., Плотников Е.В. Об одном методе анализа вычислительных сетей // Автоматика и вычислительная техника. 1986. № 1. С. 30-35.

30. Горелов О.И. Поиск дефектов в сложных технических системах методами анализа диагностических графов. Вычисление дефектных компонент // Автоматика и телемеханика. 1987. № 10. С. 153165.

31. Горелов О.И. Поиск устойчивых и перемежающихся дефектов в сложных технических системах, проверяемых неполными тестами // Автоматика и телемеханика. 1991. № 7. С. 136148.

32. Гостилова G.B., Никитин А.И. Глобальное состояние распределенной базы данных и глобальная контрольная точка // УС и М. 1991. № 8. С. 6876.

33. Губарев В.В. Концептуальные вопросы информатики. Новосибирск: НГТУ, 2002. - 120 с.

34. Гуляев В.А., Додонов А.Г., Пелехов С.П. Организация живучих вычислительных структур. Киев: Наук, думка, 1982. 138 с.

35. Димитриев Ю.К. Диагностирование вычислительных систем с несимметричными оценками // Автоматика и телемеханика. 1995. № 12. С. 106112.

36. Димитриев Ю.К. Об одной модели самодиагностируемых систем // Электронное моделирование. 1991. № 1. С. 107108.

37. Дмитриев Ю.К., Хорошевский В.Г. Вычислительные системы из мини-ЭВМ. / Э.В. Евреинов. М.: Радио и связь, 1982. - 304 с.

38. Дмитриев А.К. Диагностическое обеспечение надежности сложных технических систем //НКК. 1997. № 10. С. 4855.

39. Евдокимов В.Ф. Вопросы исследования и применения электронных моделей систем с распределёнными параметрами. Автореф. диС. на соиск. уч. сТ. к.т.н. Киев, 1968. - 23 с.

40. Евреинов Э.В. О возможности построения вычислительных систем в-условиях-запаздывания-сигналов // Вычислительные системы. Новосибирск, 1962. - Вып. 3. - С. 316.

41. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. М.: Радио и связь, 1981. - 208 с.

42. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука. Сибирское отд-е, 1966. - 308 с.

43. Иванников В.П. Операционная систем НД-70 для БЭСМ-6. Авто-реф. диС. на соиск. уч. сТ. к.ф.-м.н. М., 1971.

44. Игнатущенко В.В., Подшивалова И.Ю. Динамическое управление надежным выполнением параллельных вычислительных процессов для систем реального времени // Автоматика и телемеханика. 1999. № 6. С. 142-157.

45. Иыуду К.А., Кривощеков С.А. Математические модели отказоустойчивых вычислительных систем. М.: Изд-во МАИ, 1989. 144 с.

46. Каляев A.B., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003. 380 с.

47. Каравай М.Ф., Уваров С.И. О минимальной избыточности в рекон-фигурируемых однородных многопроцессорных вычислительных системах // Автоматика и телемеханика. 1988. № 2. С. 149-1591

48. Каравай М.Ф. Инвариантно-групповой подход к исследованию к-отказоустойчивых структур // Автоматика и телемеханика. 2000. №1. С. 144-156.

49. Кардаш Д.И:, Кудрявцев A.B., Фрид А.И. Об одном методе тестового диагностирования сложных систем // Информационные технологии. 1998. № 3. С. 30-36.

50. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика. М.: Радио и связь, 1981. - 359 с.

51. Коваленко А.Е., Гула В.В. Отказоустойчивые многопроцессорные системы. Киев: Техника 1986. 326 с.

52. Колосков В.А., Титов В. С. Метод самоорганизации отказоустойчивой мультимикроконтроллерной сети // Автоматика и телемеханика. 1998. № 3; С. 173-183.

53. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование / Под ред. Юдина Д.Б. М.: Наука, 1969. 368с.

54. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985. - 166 с.

55. Корячко В.П., Скворцов C.B., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления: Учебное пособие М.: Высшая школа, 1999. 235 с.

56. Крамаренко М.Б. Анализ самодиагностирования отказов вычислительной системы//Электронное моделирование, 1987. № 6. С. 61-64.

57. Крамаренко М.Б. Модели диагностирования отказов параллельной вычислительной системы // Электронное моделирование. 1989. № 3. С. 60-65.

58. Комплексное проектирование элементно-конструкторской базы суперЭВМ / В. А. Мельников, Ю. И. Митропольский .- 1988. 128 с.

59. Кузнецов H.A., Кульба В.В., Ковалевский С.Е. Методы анализа синтеза модульных информационно управляющих систем. М.: Физмалит, 2002. - 797 с.

60. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками в сетях. М.: Радио и связь, 1983. - 216 с.

61. Лебедев С.А. Быстродействующие универсальные вычислительные машины.- Mi.' Наук, 1956. - 15 е.

62. Левин В.И. Анализ загрузки вычислительных систем // Автоматика и вычислительная техника. 1983. № 6. С. 67-73.66: Левин В.И. К планированию работы вычислительных систем. Математический аппарат // Автоматика и вычислительная техника. 1982. №5. С. 52-58.

63. Леонтьев В.К., Морено О. О нулях булевых полиномов // Журнал вычислительной математики и математической физики. 1998. Т. 38. № 9. С. 1608-1615.

64. Лобанов- A.B. Обнаружение и идентификация- неисправностей в распределенных управляющих вычислительных системах с программно-управляемой сбое- и отказоустойчивостью // Автоматика и телемеханика. 1998. № 1. С. 55-164.

65. Лобанов A.B. Взаимное информационное согласование с идентификацией неисправностей на основе глобального синдрома // Автоматика и телемеханика. 1996. № 5. С. 150-159.

66. Лобанов A.B. Взаимное информационное согласование с идентификацией неисправностей в распределенных вычислительных системах // Автоматика и телемеханика. 1992. № 4. С. 137-146.

67. Лобанов A.B. Обнаружение и идентификация«враждебных» неисправностей путем одновременного сочетания функционального и тестового диагностирования в многомашинных вычислительных системах // Автоматика и телемеханика. 1999. № 1. С. 159-165.

68. Майданов Ю.С. Оптимизация проведения диагностических операций в параллельных вычислительных системах // Материалы докладов всероссийской научной конференции молодых ученых «Наука технологии инновации». Новосибирск. - 2003. - С. 16-18.

69. Мамедли Э.М., Самедов Р.Я., Соболев H.A. Метод локализации «дружественных» и «враждебных» неисправностей // Автоматика и телемеханика. 1992. № 5. с. 126-138.

70. Мамедли Э.М., Соболев H.A. Механизмы операционных систем, обеспечивающие отказоустойчивость в управляющих многомашинных вычислительных системах // Автоматика и телемеханика. 1995. № 8. С. 3-63.

71. Мамзелев И.А., Николаенко H.H., Русаков М.Ю. Отказоустойчивые вычислительные системы // Зарубежная радиоэлектроника. 1983. №11. С. 3-28.

72. Марчук Г.И. Введение в методы вычислительной математики. Курс лекций. Новосибирск, 1971. - 233 с.

73. Микеладзе М.А. Развитие основных моделей самодиагностирования сложных технических систем // Автоматика и телемеханика. 1995. № 5. С. 3-18.

74. Новиков H.H., Козлов В.Н., Емелин Н.М., Астапенко Ю.В. Применение булевых матриц в решении задач контроля технического состояния дискретных устройств и систем // НКК. 1998. № 3. С. 33-40.

75. Параллельные вычислительные- технологии. Состояние и перспективы / A.B. Забродин. М., 1995. - (Препр. / РАН, Ин-т прикл. матем. им. М.В. Келдыша, 99-71).

76. Пархоменко П.П. Гиперкубовая архитектура многопроцессорных вычислительных систем с реберным расположением процессорных элементов // Известия РАН Техническая кибернетика. 1994. № 2. С. 170-182.

77. Пархоменко П.П., Согомонян Е. С. Основы технической диагностики. М.: Энергия, 1981. 320 с.

78. Основы технической диагностики. В 2-х книгах. Кн. 1. Модели объектов, методы и алгоритмы диагноза / Под ред. П.П. Пархоменко М.: Энергия, 1976.

79. Платанов G.B., Романовский A.C., Чухров С.Ю. Методы обеспечения отказоустойчивости вычислительных систем, ориентированные на решение задач цифровой обработки сигналов // Вестник МГТУ. 1999. №2. С. 70-77.

80. Попков В.К. Моделирование информационных сетей. Новосибирск: ВЦ СО РАН, 1994. - 163.

81. Попков В.К., Мухопад Ю.Ф. Специализированные вычислительные среды / В.Б. Смолов. Улан-Уде: Бурятское книжн. изд-во, 1982. - 189 с.

82. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Советское радио, 1972. - 280 С.

83. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Энергопромиздат, 1983.-313 е.

84. Прангишвили И.В., Резанов В.В. Многопроцессорные управляющие вычислительные комплексы с перестраиваемой структурой. М.: 1977

85. Препринт /АН СССР, Институт точной механики и вычислительной техники, № 10).

86. Принципы обеспечения отказоустойчивости многопроцессорых вычислительных систем: Сб. трудов. М: Ин-т проблем управления, 1987. 82 с.

87. Прицкер, Алан Введение в имитационное моделирование и язык СЛАМ II. М.: Мир, 1987. 644 с.

88. Пухов F.E., Евдокимов- В.Ф., Синьков М.В. Разрядно-аналоговые вычислительные системы. М.: Советское радио, 1978. - 255 с.

89. Радойчевски В.Д., Шалаев А.Я. Параллельная диагностируемое^ модульных систем при централизованной дешифрации синдрома // Электронное моделирование. 1992. № 1. С. 5763.

90. Радойчевски В.Д., Шалаев А.Я. О последовательной диагностируемое™ при централизованной дешифрации синдрома // Электронное моделирование. 1992. № 4. С. 90-93.

91. Рекурсивная машина и вычислительная техника / В.М. Глушков, М.В. Игнатьев, В.А. Мясников, В.А. Торгашев. Киев: Препринт АН УССР Институт кибернетики, 74 - 75, 1974. - 120 с.

92. Росляков Д.И., Терехов И.А. Новые технологические решения в построении отказоустойчивых систем // Информационные технологии. 1998. № 1.С. 30-36.

93. Росляков Д.И., Терехов И.А. Отказоустойчивая технология фирмы Sequoia // Успехи современной радиоэлектроники. 1998. № 1. С. 69-79.

94. Рябов F.F., Чупаев B.C. и др. Выбор интегральных схем узлов ЭВМ для интегрального исполнения. М.:Наука, 1969. - 83 с.

95. Савельев А.Я., Овчинников А.Г., Конструирование ЭВМ и систем // учебник для техн. вузов по специальности «электрон.выч.машины». М.: Высшая школа, 1984. 248 с.

96. Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высшая школа, 1987. 226 с.

97. Сами М., Стефанелли Р. Перестраиваемые архитектуры матричных процессорных СБИС // ТИИЭР. 1986. № 5. Т. 74. С. 107-118.

98. Согомонян Е.С., Шагаев И.В. Аппаратурное и программное обеспечение отказоустойчивости вычислительных систем // Автоматика и телемеханика. 1988. №2. С. 3-39.

99. Супер-ЭВМ. Сборник научных трудов. / B.C. Бурцев. М.: АН СССР, отдел вычислительной математики, 1992. - 95 с.

100. Томилин А.Н. Применение метода математическиого моделирования к выбору структурной схемы машины БЭСМ-6 и разработки программы диспетчера машины БЭСМ-6. Автореф. дис. на соиск. уч. ст. к.ф.-м.н.

101. Томфельд Ю.Л. Структурные задачи организации ремонтных взаимодействий компонент цифрового устройства // Автоматика и телемеханика. 1999. № 6. С. 130-141.

102. Трусов С.С. Об Эффективности простых диспетчеров // Изв. АН СССР. Техническая кибернетика. 1973. № 4. С. 150-160.

103. Ш.Федоров И.И. Модель самодиагностирования для распределенных отказоустойчивых систем с деградацией структуры // Автоматика и телемеханика. 1990. № 1. С. 136-144.

104. Флинн М. Сверхбыстродействующие вычислительные системы // ТИИЭР. 1966. № 12. С. 311-320.

105. Хетагуров Я.А. Основы проектирования управляющих вычислительных систем. М.: Радио и связь, 1991. - 287 с.

106. Хорошевский В.Г. Вычислительная система МИКРОС. Новосибирск: Препринт СО АН СССР № 38 (ОВС-19), 1983. - 45 с.

107. Хорошевский В.Г. Инженерный анализ функционирования вычислительных систем. М.: Радио и связь, 1978. - 256 с.

108. Хорошевский. В.Г.- Исследование, функционирования однородных вычислительных систем. Автореферат дис. на соиск. уч. ст. д.т.н. Л.: 1973. -32 с.

109. Хорошевский В.Г. Об алгоритмах функционирования однородных вычислительных систем // Вычислительные системы. Новосибирск, 1970. -Вып. 39. - С. 3-25.

110. Хорошевский В.F. Состояние и перспективы работ в области вычислительных систем с программируемой структурой // ЭВМ. Перспективы и гипотезы. Новосибирск: ПрепринТ. СО АН СССР. Институт теоретической и прикладной механики,- № 46: - 1981. —90-с.

111. Хорошевский В.Г. и др. Архитектура вычислительных систем для управления в электроэнергетике // Труды пятого международного семинара : «Распределенная обработка информации». Новосибирск. - 1995. - С. 53-63.

112. Хорошевский В.Г., Майданов Ю.С., Мамойленко С.Н., Павский К.В., и др. Живучая кластерная вычислительная система7/ Труды школы-семинара «Распределенные кластерные вычисления». Красноярск. - 2001. -С.109-113.

113. Хорошевский В.F., Майданов Ю.С. Средства самодиагностики кластерных вычислительных систем // Труды школы-семинара «Распределённые кластерные вычисления». Красноярск. - 2001. - С. 105-109.

114. Хорошевский В.Г., Мамойленко С.Н. Стратегии стохастически оптимального функционирования распределенных вычислительных систем // Автометрия. том 39. -№ 2. - 2003. - С. 81-91.

115. Хорошевский В.Г., Мамойленко С.Н., Майданов Ю.С. Смирнов C.B. Об организации функционирования кластерных вычислительных систем // Автометрия. -2004. №1. -С. 41-51.

116. Хендри. Полностью аппаратное резервирование без участия программ //Электроника. 1983. № 2. С. 39-43.

117. Чеботарев П.Ю., Шамис Е.В. Матричная теорема о лесах и измерение связей в малых социальных группах // Автоматика и телемеханика. 1997. №9. С. 125-137.

118. Хопкинс A.JL, Смит Т.Б., Лала Дж.Х. FTMP высоконадежный устойчивый к отказам мультипроцессор для управления самолетом ТИИЭР. 1978. Т. 66. № 10. С. 142-165.

119. Чеботарев П.Ю., Шамис Е.В. О показателях близости вершин графов // Автоматика и телемеханика. 1998. № 10. С. 113-133.

120. Четверушкин Б.Н. Математическое моделирование задач динамики излучающего газа. -М.: Наука, 1985. 304 с.

121. Шестакова Т.В. Центры управления сетью. Организация управления и контроля в современных сетях ЭВМ // Зарубежная радиоэлектроника. 1984. №3. С. 19^4.

122. Шнитман В. Отказоустойчивые компьютеры компании Stratus // Открытые системы. № 1. 1998. С. 12-22.

123. Шокин Ю.И. Численные методы газовой динамики и инвариантные разностные схемы. Новосибирск, 1977. - 84 с.

124. Шубинский И.Б. Об одном подходе к обеспечению надежности модульных систем обработки информации // Надежность и контроль качества. 1984. №9. С. 10-15.

125. Шубинский И.Б. Активная защита от отказов вычислительных систем в условиях соизмеримых длительностей решения задач и пауз между ними // Кибернетика и системный анализ. 1991. № 4. С. 42-47.

126. Языки и параллельные ЭВМ: сб. сТ. / A.A. Самарский. М.:Наука, 1990.-91 е.

127. Яненко H.H., Хорошевский В.Г., Рычков А.Д. Параллельные вычисления в задачах математической физики на вычислительных системах с программируемой структурой // Электронное моделирование, 1984. Т. 6, № 1 -С.3-8.

128. Arge J.R. A Message-Based Fault Diagnosis Procedure // Computer Communication Review. 1986. V. 16. № 3. P. 328-337.

129. Chwa K.Y., HakimiS.L. On Fault Identification in Diagnosable Systems Systems // IEEE Trans. Comput. 1981. V. C-30. N 6. P. 414-422.

130. Computer and job-shop scheduling theory/Ed.by E.G.Coffman/. Jon Wily & Suns. - 1976.

131. Gonzalez M.J. Deterministic processor scheduling.-Computing Surveys, 1977,vol. 9,№ 3.p. 173-204.

132. Hanchek F., Dutt S. Methodologies for tolerating cell and interconnect faults in FPGAs// IEEE Trans. Comput. 1988.V. 47. No. 1. P. 15-33.

133. Harmat L. A New Model for Self-Testing and Self-Diagnosing Multi-microprocessor Systems // Proc. Int. Symp. on Fault-Tolerant Computing (FTCS-11), 1981. P. 170-172.

134. Holt C.S., Smith J.E. Diagnosis of Systems with Asymmetric Invalidation //Trans. Comput. 1981. V. C-30. N 9. P. 679-690.

135. Kavianpour A., Friedman A.D. Different Diagnostic Models for Multiprocessor Systems // Information Processing 80: Proc. IFIP Congr. Tokyo-Melburn, 1980. P. 157-162.

136. Khanna S., Fuchs W.K. A graph partitioning approach to sequential diagnosis // IEEE Trans. Comput. 1997.V. 46.No. l.P. 39-47.

137. MaengJ., Malek M.A. A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor System // Proc. Int.Symp. on Fault-Tolerant Computing (FTCS-11), 1981. P. 173-175.

138. J.Von Neumann,"Probabilistic logics and the synthesis of reliable organisms from unreliable components", Automata Studies,№ 34 , P. 43-49. Princeton, NJ : Princeton University Press.

139. Preparata F.P., Metze G., Chien R.T. On the Connection Assignment Problem of Diagnosable Systems // IEEE Trans. Electron. Comput. 1967. V. EC-16. N6. P. 848-854.

140. Russel J.D.,Kime C.R. On the diagnosability of Digital Systems.-Digest of FTC/3 Palo- Alto, June 1973,p. 139-144.

141. Siewiorec D.P. Architecture of Fault-Tolerant Computers // Computer. 1984. V. 17. N8. P. 9-18.

142. Tryon J.G. "Quadded logic" in Redundancy Techniques for Computing Systems? Wilcox and Mann, Eds: Washington, DC: Spartan Books, P. 205-228, 1962.