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

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

Лаходынова Надежда Владимировна

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

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

АВТОРЕФЕРАТ

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

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

Работа выполнена в Томском государственном-архитектурно-строительном университете

Научный консультант -

доктор технических наук, профессор Воробьев ВА. Официальные оппоненты:

доктор технических наук, профессор Водяхо А.И." доктор технических наук, доцент Димитриев Ю1. доктор технических наук, профессор Щербаков О.В.

Ведущая организация - Институт вычислительной математика

и математической геофизики (ИВМ и МГ) Сибирского отделения РАН

Защита диссертации состоится ««¿/ » 2004 г. в /У час

на заседании диссертационного совета Д 212.238.01 Санкт-Петербургского грсударственного электротехнического университета «ЛЭТИ» им. В.И.Ульянова (Ленина) по адресу: 197376, Санкт-Петербург,ул. Проф.'Попова, 5.

С диссертацией молено ознакомиться в библиотеке университета.

Автореферат разослан

Ученый секретарь диссертационного совета

Пантелеев М Т.

йо^ 0.49 (с $42-

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

Актуальность исследования. Одним из прорывных направлений современной науки и техники является достижение общедоступной сверхвысокой производительности ЭВМ - более чем 10|3-й014 флопс. От успешного внедрения и использования таких супер-ЭВМ зависит стратегическая позиция современных государств в нарождающемся сложном постиндустриальном мире. Так для всемирного экологической (и, очевидно, не только экологического) мониторинга США построили массово-параллельный суперкомпьютер с объявленным быстродействием ЗхЮ13 флопс.

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

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

Концепция ОВС занимает видное место в развитии супер-ЭВМ. Например, вычислительные кластеры серии МВС-100 и МВС-ЮОХ, предлагаемые НПО «Квант», реально представляют собой ОВС на про-

РОС. НАиь-ьНАЛЬНАЯ БИБЛИОТЕКА и СйетсрСург

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

Концепция ОВС была сформулирована в Институте математики СО АН СССР под руководством Э.В. Евреиновав 1962 году и успешно развивается в настоящее время, являясь ведущей при построении систем сверхвысокой производительности. В России значительный вклад в развитие ОВС внесли Косарев Ю.Г., Хорошевский В.Г., Бандман O.JI., Пран-гишвили И.В., Медведев И.Л., Воробьев В.А., Димитриев Ю.К., Корне-ев В.В., Глушков В.М., Каляев A.B., Лазарев В.Г., Додонов А.Г., Артамонов Г.Т. и многие другие.

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

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

Проблема обеспечения отказоустойчивости НПМ СБИС была сформулирована ещё в 80-х годах. Технологические трудности при изготовлении НПМ, низкий выход годных, дорогостоящее производство привели к тому, что до настоящего времени их использование в качестве базы для реализации ОВС остается проблематичным. Ясно, что технология

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

1) невозможность замены отказавших элементов;

2) отказы не только процессорных элементов, но и связей между ними; , '

3) однородность и близкодействие структур связей;

4) стремление к экономии оборудования.

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

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

Цель исследования - развитие теоретических основ построения отказоустойчивых ОВС, разработка программно-аппаратных методов обеспечения отказоустойчивости процессорных матриц с программируемой структурой, в том числе (и в особенности) НПМ СБИС.

Основные задачи диссертации:

1. Разработка математических моделей ОВС, позволяющих исследовать отказоустойчивость ОВС и методы ее обеспечения, как аналитически, так и моделированием на ЭВМ.

2. Исследование фундаментальных пределов отказоустойчивости и надежности однородных структур.

3. Разработка и исследование новых парадигм обеспечения отказоустойчивости ПМ и НПМ СБИС.

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

5. Исследование работоспособности, эффективности и статистических

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

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

1. Разработаны математические модели, предназначенные для исследования надёжности и отказоустойчивости ОВС, отличающиеся от известных учетом влияния структуры связей.

2. Исследованы фундаментальные пределы отказоустойчивости однородных коммутационных структур ПМ и НПМ СБИС.

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

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

5. Предложен новый подход к обеспечению отказоустойчивости НПМ: консенсус-парадигма.

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

Основные положения, выносимые на защиту:

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

2. Консенсус-парадигма - новый, наиболее эффективный подход к обеспечению отказоустойчивости как процессорных матриц, так и НПМ СБИС.

3. Методы реконфигурации структуры процессорной матрицы (и с программируемым резервом, и без него) обеспечивают реализацию отка-

зоустойчивой ОВС на ПМ и НПМ СБИС. 4. Архитектура ОВС на ПМ и НПМ СБИС позволяет неограниченно наращивать её производительность и обеспечить необходимую живучесть.

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

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

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

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

Использование результатов подтверждается соответствующими актами.

Апробация. Результаты исследования:

• обсуждались на семинарах в Институте математики СО РАН (г. Новосибирск), Московском институте связи, Красноярском государственном электротехническом университете, на семинаре Отдела проблем информатизации Томского научного центра СО РАН, кафедре прикладной математики Томского государственного архитектурно-

I строительного университета.;

® докладывались на 12-ти международных, всесоюзных и всероссийских, а также на региональных, городских и вузовских конференциях, ь совещаниях и школах-семинарах в Москве, Минске, Риге, Новосибир-

ске, Томске, Екатеринбурге, Байконуре, Красноярске;

• поддерживались фондом грантов Министерства образования РФ.

Публикации. По теме диссертации опубликованы 33 научные работы, из них: 1 - монография, 1 - учебное пособие, 17 статей в научных журналах, 4 доклада и тезисы к 10 докладам на всесоюзных, всероссийских и международных научно-технических конференциях.

Структура и объём диссертационной работы. Диссертация состо-

ит из введения, четырёх глав, заключения, одного приложения и списка литературы, включающего 276 наименований. Основная часть работы изложена на 203 страницах машинописного текста. Работа содержит 28 рисунков и 14 таблиц.

Краткое изложение диссертации

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

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

В п.1.1. дан краткий обзор развития и современного состояния рынка ЭВМ сверхвысокой производительности. Показана ведущая роль концепции ОВС в этом процессе.

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

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

Структурой системы является однородный граф О (Ь, Е), где Ь -множество нумерованных вершин, Е - множество пар элементов из Ь, связанных в (]. Мы полагаем по определению, что существует транзитивная подгруппа группы автоморфизмов Аш графа (7.

Множество 9/ вершин графа <?, находящихся на расстоянии 1 от вершины /, называется окрестностью или ближайшими соседями вершины /, множество 5*7 вершин графа <У, находящихся на расстоянии не более чем к от вершины / и /гЭ/, называется окрестностью к-го порядка вершины /. Аналогично для любого множества КеЬ определяются его окрестности д'К, причём Кп д'К~ 0, и, кроме того

/< ; -> д'К с д'К.

Элементарным автоматом динамической клеточной системы является асинхронный вероятностный автомат М = (X, XT', Л), где Л" - выходной алфавит автомата М, совпадающий с алфавитом его состояний X, входной алфавит А™ — состояния окрестности 31, содержащей т элементов, А = ) / х,у eXh у& е Ya } - система интенсивностей перехода. Веро-

ятность перехода из хщХ ъуеХза время At при условии^ е Xп равна Pxyiyai) = К(Угд At + о(Дг) Функция х(Г), сопоставляющая каждому leL состояние х(1)вХ (иначе х(Г): L называется конфигурацией. Множество Y всех конфигура-

ций - декартова степень множества X:

Пусть KcL и х(/): К X; такое сужение функции х(Г) называется конфигурацией на К и обозначается хк, у к, в частности л:/ есть состояние /-го автомата - случайная величина, называемая также компонентой. Введём операцию объединения на множестве непересекающихся сужений конфигураций. Пусть К а L, М а L н К г\ М- 0, тогда (ук, ум) -уким - конфигурация на Kvj М. совпадающая с ук яз. К и с ум на М. Будем говорить, что хмсодержит хк_ если КсМ ихм= (х^хм к). Элементарный автомат задаётся системой подстановок П = { П(х,хд) /хеХ, хя еХя}, где П(х,ха) : (х,хд{) г sh...,yi; Ъ/хл), Xxs(xjd,...,XXy(xji) - стационарные неймановские подстановки. Здесь rt, si ,...,yi - это возможные значения /го элемента в результате применения подстановки IJ(x,xsi), rt, si,...,yi е X; список Кг(хд /), ^(xod'-^xyixad ~ соответствующие интенсивности реализаций этих альтернативных значений, X„(xgi), ^(хэд^—Л^хзд е Л.

Таким образом, стохастическая клеточная модель S задана, если задана её структура G и автомат М.

Конфигурация есть состояние системы S, которое изменяется при переходе любого из автоматов М из состояния в состояние. Функционирование всей системы задаётся графом конфигураций (состояний)

fV= < V, V>

где: Y- множество конфигураций; V - множество дуг, ve V имеет своим началом хе Y и концом zeY, если х заменяется на z при изменении состояния некоторого подмножества KczL автоматовМв системеS.

Граф конфигураций W предназначен для изучения функционирования системы S при синхронной и асинхронной интерпретации в общем случае. Запрет одновременного срабатывания нескольких подстановок задает ординарное множество Z(y) конфигураций, достижимое из у таким

применением системы П. Срабатывание подстановок в ординарной динамической' клеточной системе можно рассматривать как ординарный поток событий, а-всё функционирование как марковский процесс с системой состояний У.

Таким образом, каждая дуга графа конфигураций И^о помечена соответствующей интенсивностью перехода из системы интенсивностей Л:

1Уо=:<Г,Уо, Л, у: -» Л > где: У0 £ У\ у : Уо —> А - отношение, сопоставляющее каждой 'дуге графа конфигураций интенсивность из системы Л.

Граф конфигураций изображает марковский процесс, сопряжённый с функционированием системы 5 и задающий вероятностную меру Р на ст-алгебре конфигураций Р. Таким образом, системе £ соответствует вероятностное пространство

где: Г - множество конфигураций - пространство элементарных событий; F - а-алгебра на У; Р — вероятностная мера на Р.

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

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

Рассмотрим стационарное (равновесное) состояние ординарной динамической клеточной системы.

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

Состояние ц есть марковское случайное поле на <?, если для всякого / е х имеем /¿(х, / х п,) = /.¡(х, / хг1).

Пусть случайный процесс задан интенсивностями перехода/?^, у, у' е У. Тогда условие обратимости для конечного У выглядит следующим образом

КШ^РЛУ'Щу.уеУ'У'еУ^У-

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

Генератор (7 полугруппы {Р,},,0, описывающий эту модель, будет определяться так: в(у',у") = ^(1,у'), у'ы = у"а1, У',*у",, для всех других пар V', V"еУ 0(у',у") = 0, а С?(У,У) определяется из условия 2 (?(У, У') = 0. Здесь а и Ь - состояния компоненты. Полугруппу, отве-

у-сУ

чающую такому генератору, назовем ординарной.

Полугруппу {Р, назовем полугруппой ближайшего соседства, если

Р*V,*) = Р*ь(Л>««*), У1еЬ,хеУ.

Состояние % называется равновесным состоянием для полугруппы

Мигели 1>(У)Р,(/,/') = ^(/') Уу'' е Г, V; > 0.

/сУ

Имеет место следующая

ТЕОРЕМА 1. Пусть {Р,},г0 - обратимая ординарная полугруппа ближайшего соседства, л- - равновесное состояние. Тогда к - марковское случайное поле.

Условие обратимости накладывает ограничения на интенсивности перехода Д<4.

ТЕОРЕМА 2. Следующие условия эквивалентны:

(1) Ординарная полугруппа {Р,}№0 обратима.

(2) Р*УУ) РЛУ) РЛУ) РЛУ)'

где ЫЬ\ух ,уг ,у1 еУ;у\м = у\ч;у'/ = с;/, =Ь;у', =а и од-

новременно

Р*УУ) &„(/„/) = РЛЬУ) РЛУ) Р*«У) РЛ^У) РЛ^У) РьЛУУ

где/,/, *Цу1У,у*У еГ;

Умл, = У2щм = Ушл, = у1м,ч ; V/ = а, у< = с, у) = а, у' = <1; У, = Ь,у[ = с; у) = Ь,у\ = с1.

(3) Существует потенциал К: Г Л такой, что

М^ = ехР{к(У)-Г(У)}, где у1, =у[и; у]=Ь,у\ = й. А, (Л У )

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

ся слишком жесткими для реальных систем. Этим вызвана ограниченность применения результатов по марковским случайным полям. С другой стороны, очевйдна и недостаточность модели "идеального коллектива" вычислителей, в которой структурные характеристики ОВС не учитываются вовсе. Приведем соответствующий пример. Элементарные машины выходят из строя с интенсивностью ¡5 и восстанавливаются с интенсивностью 8. Интенсивности р и 8 зависят от состояния окрестности

/

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

[р, к<п _ (8, к<п

Р [Рс, к = п'' \8ь,к = п'

Коэффициент готовности в этом случае имеет вид

(а +1)" , Рс Р

р--ь-- Где =

' {а + \)"-а\а-Ь) 5„ 8

На Рис. 1 показана область (и=5), в которой учет влияния межмашинных связей не дает существенной поправки к результатам модели "идеального коллектива".

Рис. 1.

Очевидна необходимость дальнейших исследований. Обнадеживающие результаты в этом направлении дает использование результатов

теории просачивания.

Во второй главе представлены результаты исследований отказоустойчивости ОВ6, основанные на результатах теории просачивания и опубликованные в серии работ [4-6, 23, 24, 26 ].

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

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

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

Наращивание избыточности ПМ понимается теперь как неограни-

ченный рост размера N выделенного блока. Ясно, что существует такой размер N, что наличие N/: > N0 элементов в исправном кластере будет гарантировано. Решающее значение имеет только факт существования или несуществования исправного кластера. По предположению, алгоритмы самодиагностики и реконфигурации его обнаружат и полностью используют для организации вычислений. Например, это может быть сделано с помощью корневого дерева на связном множестве исправных ЭМ.

Увеличивая размер N, мы должны требовать увеличения размера исправного кластера. В пределе, при N —> со, в бесконечной структуре должен существовать бесконечный исправный кластер. В противном случае структура "рассыплется" на несвязные куски, то есть выйдет из строя.

Имея в виду применение достаточно больших ОВС при N> 102, мы ограничимся исследованием их бесконечных представителей. Проблема надёжности свелась теперь к следующему вопросу: при каких вероятностях р и г в бесконечной локальной однородной структуре данного типа существует бесконечный исправный кластер?

Ответ на этот вопрос является основной задачей теории просачивания. Содержание основной задачи просачивания состоит в поиске области просачивания, точнее, такой функции f(p, г), что при f(p, г) < О исправный кластер отсутствует, а при f(p, г) > О - существует. Частные задачи были поставлены Хаммерсли ещё в 1957 году: просачивание по вершинам, когда р < 1 и г = 1, и просачивание по связям, когда р- 1, а г < 1. Вторая задача сводится к первой. Основной результат теории просачивания заключается в существовании критических вероятностей рн, таких, что если р < рц, то бесконечный исправный кластер существует в G с вероятностью 0, и если р > рц, то с вероятностью 1 в G существует, и притом единственный, бесконечный исправный кластер. Здесь G периодический граф, вложенный в R2.

Существование критической вероятности не подвергается сомне- I

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

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

одного типа.

Пусть Р(Ы, р) — вероятность просачивания через структуру размера N в данный момент времени. Следующее утверждение о свойствах Р(И,р) является, по существу, перефразировкой основного утверждения.

Утверждение 1. На множестве локальных однородных структур одного типа, вложенных в Д2,

Иными словами, с ростом избыточности ОВС становится сколь угодно надёжной, если р > рт и сколь угодно ненадёжной, если р <рн. Таким образом, нельзя построить сколь угодно надежную ОВС из сколь угодно ненадежных элементов. Это утверждение противоречит результатам Шеннона-Мура и многих последующих работ. Причина противоречия в том, что мы ограничены в выборе структуры. Требования локальности и однородности лишают нас возможности использовать слишком ненадёжные элементы.

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

Пусть время безотказного функционирования ЭМ распределено по экспоненциальному закону с параметром а при условии ptpu Среднее время наработки на отказ для ЭМ равно г = а'1. Величина а - интенсивность отказов ЭМ, т - время жизни. Отказавшая ЭМ обнаруживается и восстанавливается с интенсивностью /3 за среднее время восстановления /Г1.

Уравнение dp(t)= [P(l- p(t)) - a p(t)] dt описывает процесс гибели - восстановления в бесконечном ансамбле ЭМ. Пусть ро = р(0) и р = p(t). Вероятность ро называется "выходом годных элементов" и характеризует качество СБИС при неразрезной технологии. Если бракованные ЭМ можно заменить, то ро - 1. Решение уравнения при указанных начальных условиях имеет вид

где ра - limp = --финальная вероятность исправного состояния

- ;(о + Р )

Рис. 2. Динамика гибели-восстановления ОВС: ha h- время жизни при разных начальных условиях

Учитывая условие связности локальной однородной структуры р > рн, легко получить следующее утверждение.

Утверждение 2. Время существования бесконечного исправного кластера в локальной однородной структуре равно

0,Ро<Ра<Р,П

t =

1

-In

_ Ра ~ А» <* + рШРи-Ра}

[со,рн <ра.

>Р»<Рн <А»

В частности, в системе без восстановления с t = X 1п(ро / Рн) ^ т 1п(рн '). где г = а "1 - время жизни одного элемента. Эта формула представляется более реальной оценкой, чем утверждение 1, поскольку диагностика и восстановление изолированного элемента проблематично.

Итак, избыточность не увеличивает времени жизни локальной однородной структуры.

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

наших целей достаточно воспользоваться приближённым методом динамики средних и рассмотреть только стационарное состояние.

Пусть N - число ЭМ; т - число восстанавливающих органов, работающих параллельно; а и ¡5— интенсивности потока отказов и восстановлений.

При m>N(\-p) система ведёт себя как самовосстанавливающаяся. При т < N( 1—р) имеет место ограниченное восстановление, а условие равенства потоков отказов и восстановлений имеет вид

Nap = тр

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

Утверждение 3. ОВС с ограниченным восстановлением работоспособна если выполняется условие

N0 < т 3 а< N < т 0 (а р„)А

При N > т Р (а Рн)'\ стационарное состояние ОВС есть состояние отказа.

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

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

В п. 2.4. исследуются пороги просачивания однородных структур, предлагаются новые методы их определения. Метод моделирующих решеток позволяет аналитически определить значения критических вероятностей рн(К), Ря(ШЛ рн(К* ). Метод второй производной позволяет определить критические вероятности для различных структур.

Утверждение 4. Точка перегиба функции P(N,p) при N-* со является порогом просачивания для соответствующего периодического графа.

Функция P(N,p) -полином iV-той степени относительно р.

P(N,p) = Ei,,.MC,pXl-pf-' где С,- - число конфигураций с просачиванием, в которых i элементов исправно, a N-i элементов неисправно. Определение точного аналитического выражения для P{N,p) сводится к подсчёту коэффициентов Ct. Для небольших N вычисления проводятся на ЭВМ полным перебором всех конфигураций и проверкой их на просачиваемость (Рис. 3.).

¡3,41 0,5

I ' '

0,37 0,4 0,5

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

Моделирование задачи просачивания в более общей постановке позволяет экспериментально определить границу области просачивания /(р, г)- О для разных типов решеток. На Рис.4, изображены границы области просачивания для четырех решеток.

Нижняя соответствует Р(к, р, г) = 0, верхняя соответствует Р(М, р, г) = 1. В заштрихованной области - переходная зона.

1

09 08 07 06 0.5

0.4 03

0.2 0.3 0.4 0.5 0 6 0.7 0.8 0 9 1 Рис. 4. Области просачивания для решеток К*,Т, К, Ш

Итак, показано, что для исследования живучести ОВС на ПМ и НПМ СБИС необходимо учитывать её структуру и надёжность как ПЭ так и связей. Без этого выводы теории могут быть неверными.

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

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

Далее нашей целью будет разработка методов обеспечения отказ о-устойчивости'ПМ и НПМ СБИС за счёт избыточности и специальных методов реконфигурации структуры.

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

В п. 3.1. рассматриваются источники отказов СБИС и методы обеспечения отказоустойчивости путем программирования структуры.

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

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

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

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

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

Рис. 5. Перестройка матрицы по алгоритму свободного захвата.

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

В н. 3.3. исследуется эффективность и работоспособность алгоритмов реконфигурации, с программируемым резервом. Показана их высокая эффективность по сравнению с известными алгоритмами (Рис. 6.). Даются рекомендации по программированию резерва (строки или столбцы резервировать?).

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

Р(п,т,р)

1,0

0,8 0,6 0,4 0,2 0,0

Су .'/ /| •

в У / » ' г/ / • ' / '' / ' ' ' • '

/ */• / / * 1 / ' / в-',: А ,\(

/ / * / / 1 / / * / / * / » ' , 1 # '

# » ф » т ♦ • * 9

0,88

0,91

0,94

0,97

1,0

Рис. б. Сравнение алгоритмов перестройки для матрицы 20x20:

- с резервом по краям (пунктирная линия);

- с дополнительными строкой и столбцом (сплошная линия)

А- алгоритм непосредственной перестройки

В - алгоритм ограниченного захвата

С - алгоритм свободного захвата

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

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

числе блок управления сигналами перестройки и блок управления коммутациями. Существенным недостатком этих методов является требование абсолютной надежности блока управления. При этом к фатальному отказу всей матрицы ведет отказ блоков управления как исправных, так и неисправных процессоров. Это обусловлено тем, что сигнал отказа e(i,j) соответствует отказу самого процессорного элемента (/,_/) либо eró коммутаторов. При выходе из строя блока управления неисправность распространяется на всю матрицу. '

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

структуры связей между ПЭ.

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

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

В п. 4.1. даётся критический анализ имеющихся подходов к обеспечению отказоустойчивости вычислительных систем. Делается вывод об их недостаточности и даже непригодности для распределённых ОВС в условиях близкодействия и неразрезной технологии СБИС.

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

1. Контролируемое и диагностируемое устройство присутствует в системе в единственном экземпляре.

2. Это устройство имеет высокую цену.

3. Элементы устройства можно заменять по мере их отказов. Минимальный заменяемый блок - типовой элемент замены (ТЭЗ) можно контролировать, диагностировать и ремонтировать на специальном

L стенде вплоть до замены отдельных электронных компонент.

4. Связи между ТЭЗ-ами дёшевы и либо абсолютно надёжны, либо их отказы приписываются элементам. И, вообще, проверка связей -вопрос отдельный.

5. Имеются абсолютно надёжные элементы, например, смесители Неймана.

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

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

Отметим особенности задачи диагностики для ОВС и, вообще, для вычислительных систем, состоящих из одинаковых модулей.

1. Элементом замены в ОВС является элементарная машина (ЭМ) -устройство, которое обычно само по себе снабжается средствами самодиагностики.

2. Для предмета нашего исследования - ОВС на ПМ и, особенно, НПМ СБИС - замена вообще невозможна, поэтому выбор минимального диагностируемого элемента является предметом особого рассмотрения.

3. Структура системы однородна и локальна - связаны только соседи по месту.

4. В силу одинаковости ЭМ каждый элемент окрестности ЭМ является для неё эталоном и таких эталонов достаточно много (8 и более).

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

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

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

1. ПЭ много и они связаны однородной, локальной сетью связи.

2. Число связей у каждого ПЭ ограничено.

3. Связи можно программно включать, выключать и коммутировать.

4. Отдельные ПЭ и связи дёшевы относительно цены исправной НПМ.

5. Абсолютно надёжных ПЭ и связей нет.

6. Заменить отказавшие ПЭ й связи невозможно.

7. Византийское согласие всех исправных ПЭ ненужно и нереально.

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

9. Резервные ПЭ и связи не выделяются.

Ю.Отказоустойчивость достигается за счёт программирования структуры и избыточного числа ПЭ и связей между ними. Задача состоит в том, чтобы вложить требуемый граф в избыточный граф с отказами элементов и связей.

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

Перестройка структуры ПМ проводится за счет использования резервных связей. Резервные элементы не выделяются. Каждый ПЭ можно использовать в качестве резервного. Каждый ПЭ тестируется и результаты тестирования сравниваются с результатами тестирования соседей. По результатам тестирования в каждом ПЭ создается список согласных с ним соседей.

Реконфигурация структуры ПМ (волновой алгоритм) на основе сигналов согласия проводится в четыре этапа: прямой ход, обратный ход, фиксация и настройка. На этапе прямого хода каждый ПЭ составляет список своих возможных логических номеров, основываясь на логических номерах согласных с ним соседей. Начиная с верхнего левого угла, ПЭ передают свои возможные логические номера согласным соседям с большими физическими номерами. Если физические номера несравнимы, то передача делается только в одном направлении, например от (г +1,у) к (/,/+1 ). ПЭ получает логический номер (/, Д если возможные логические номера согласных с ним соседям удовлетворяют определенным условиям, зависящим от типа требуемой решетки.

Для того, чтобы логический номер (/, у") стал возможен необходимо найти среди йредшественников некоторое множество уже вычисленных номеров. %

Для квадратной решётки это пара {(w'i),(4/:>))> удовлетворяющая условиям

(1)[l fi—fei =1]Д[1Л-Л1 =1]

(2) [Q, < Щ Q, >Л)] V [(i, > i2 ) Ul </2Я

Для треугольной решётки это тройка {(ioj'o),(ii>jr),(i2,Ji)y, удовлетворяющая ещё Одному условию:

(3) {¡о, jo) = (min (ii,i2 ), min (ji,j2))

Для решётки К* это уже четвёрка {(¡о,Jo), (ii,Ji), (hji), 0■*/<)}> Удовлетворяющая ещё одному дополнительному условию:

(4) (iV.jfV) = {max {ih i2) +1, min (jhj2))

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

Логический номер (i,J) во всех случаях вычисляется по формуле (i,j) = ( max (//, /Д max (j/,j2))

В результате прямого хода каждый ПЭ имеет множество возможных логических номеров. Если в результате прямого хода правый и нижний края ПМ оказались недостижимы, вырабатывается глобальный сигнал фатального отказа. Реконфигурация невозможна. В противном случае начинается обратный ход. При обратном ходе направления передачи логических номеров меняются на противоположные. Возможные логические номера вычисляются аналогично вычислениям прямого хода, а логический номер (ij) вычисляется как (ij)=(min (ij, i2), min (jj,j2 )), где (ij, ¡2), (ji,j2) - логические номера соседей, удовлетворяющих условиям для решетки заданного типа. Логический номер (i,j ) считается допустимым для ПЭ, если он уже был получен в результате прямого хода. После обратного хода в списке допустимых логических номеров ПЭ остается пересечение множеств логических номеров прямого и обратного хода. Каждый ПЭ, имеющий несколько возможных логических номеров вырабатывает сигнал неоднозначности, который по магистральному каналу поступает в управляющую ЭВМ. На этапе фиксации выбирается единственный вариант решетки, после чего выполняется настройка физической структуры связей на полученную логическую нумерацию.

На Рис. 7. показана неисправная матрица размером 3x4. Элементы

0-ой и 4-ой строки, 0-го и 5-го столбца фиктивные. Связи с несогласными элементами отмечены штриховой линией. Конфигурация несогласных связей такова, что неисправности возможно были бы отнесены к заштрихованным ПЭ. При такой конфигурации неисправных ПЭ все алгоритмы главы 3 дают фатальный отказ. Использование волнового алгоритма позволяет получить работающую матрицу размером 3x3 (Рис. 8.).

Рис.8. Консенсус процессорной матрицы

Таблица 1.

Логические номера элементов процессор>_ной матрицы Рис. 8._

.1

1 2 3 4

1,1 1,2 2,2 1,3

2,1 2,3

3,1 3,2 3,3

В п. 43. моделируется волновой алгоритм и исследуется его эффективность и работоспособность. На Рис. 9. представлена зависимость вероятности сохранения работоспособности Р(п, р) для волнового алгоритма (А) и алгоритма свободного захвата с программируемым резервом (В) - одного из наиболее эффективных алгоритмов, основанных на синдроме неисправности. Результаты получены для матрицы размером 20x20. Учитывая результаты моделирования и уменьшение аппаратных издержек, можно сделать вывод о большей эффективности волнового алгоритма.

Р(п.р)

Рис. 9.

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

элементов и связей не рассматриваются. Неисправности представлены только сигналами согласия между соседними ПЭ.

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

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

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

Выводы и основные результаты

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

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

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

1. Подтверждена перспективность и решающая роль концепция ОВС в развитии современных массово-параллельных процессоров.

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

3. Исследована перколяционная модель структурной надежности. Показано, что требования локальности и однородности структуры не позволяют использовать слишком ненадёжные элементы. Рассмотрены динамические модели структурной живучести при различных предположениях. Показано, что пределы надёжности однородной структуры являются величинами того же порядка, что и надёжность вентиля, а минимальный выход годных ПЭ на НПМ должен быть не ниже порога просачивания.

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

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

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

На основе анализа источников отказов в СБИС и исследования пределов их надёжности сформулирована реальная парадигма живучести » НПМ СБИС, учитывающая отказы ПЭ и связей и позволяющая использовать все полученные СБИС.

5. Предложены и исследованы новые методы обеспечения отказоустойчивости ОВС на ПМ и НПМ СБИС.

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

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

Предложена архитектура ОВС на неразрезных процессорных матрицах СБИС с программируемым резервом.

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

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

элементами и не требующая аппаратуры самодиагностики.

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

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

Предложена архитектура ОВС на неразрезных процессорных матри-| цах СБИС с программной реализацией метода консенсуса.

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

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

Список публикаций по теме диссертации

1. Лаходынова Н.В. Стохастическая модель однородной вычислительной системы, учитывающая межмашинные связи // Вычислительные системы с программируемой структурой: Вычислительные системы, 94. -Новосибирск, Институт математики СОАНСССР. - 1982.-С. ПОПУ.

2. Лаходынова Н.В., Воробьёв В.А. Теория модели коллектива вычислителей, основанная на принципе близкодействия // Тезисы докладов

• XXV областной научно-технической конференции, посвященной 60-й

годовщине образования СССР и Дшо радио. -Новосибирск, 1982 . - С. 9.

р 3. Лаходынова Н.В, Воробьёв В.А.. Критическое протекание в плоских

решетках // Специализированные вычислительные системы, методы и средства обработки информации: Тематический сборник научных трудов. - М.: Изд-во МАИ , 1987. - С. 13-15. 4. Воробьёв В.А., Лаходынова Н.В. Пределы надёжности однородных вычислительных систем // Экспертные системы и распознавание образов: Вычислительные системы, 126. - Новосибирск, Институт математики СО АН СССР, 1988. - С. 122-149.

5. Воробьёв В .А., Лаходьшова Н.В. Пределы надежности однородных структур // Известия АН СССР: Техническая кибернетика, № 3. - 1989. -С. 110-114. "

6. Воробьёв В.А., Лаходынова Н.В. Пороги просачивания и надежность однородных структур И Методы и средства проектирования специализированных вычислительных систем. - Ленинск: Изд-во МО, 1989. -С. 9.

7. Лаходынова Н.В., Соловьев В-В. Смирнов IO.B. Совершенствование программирования в задачах логического управления технологическими системами // Технический прогресс в атомной промышленности. Серия: Организация производства: прогрессивная технология. Вып. 12 (277). - М.: Атоминформиздат, 1989. - С. 37-42.

8. Воробьёв В.А., Лаходынова Н.В. Близкодействующая архитектура вычислительной системы // Перспективы развития вычислительных систем. III Всесоюзный симпозиум, Рига, 31.10-2.11, 1989: Тезисы докладов. - Рига, 1989. - С. 20.

9. Лаходынова Н.В. Отказоустойчивые ОВС с перестраиваемой структурой // «Районные распределенные вычислительные системы»: Тез. докл. — М., 1990.-С. 15.

10.Лаходынова Н.В. Отказоустойчивые ОВС с программируемым резервом //'«Распределенные вычислительные системы и сети»: Тез. докл. -М., 1990.-С. 11.

П.Бондарев A.A., Воробьёв В.А., Лаходынова Н.В. Реализация ПРАЛУ на программируемом логическом контролере. Алгоритмическое и техническое обеспечение для проектирования систем управления движущимися объектами. - М.: Изд-во МАИ, 1991, - С. 110.

12.Воробьёв В.А., Лаходынова И.В. Программное обеспечение систем логического управления ЛА: Учебное пособие. -М.: Изд-во МАИ, 1991,- 39 с.

13.Воробьев В.А., Лаходынова Н. В. Процессорная матрица с перестраиваемой структурой и перестраиваемым резервом // Автометрия, № 5. - 1994. - С. 90-98.

14.Vorobyev V. A., Lakhodinova N.V. Reconfigurable processing arrays with a rearrangeable redundancy (Процессорная матрица с перестраиваемой структурой и перестраиваемым резервом) // Optoelectronics, Instrumentation and Data Processing, № 5. - 1994. - P. 90-98.

15.Воробьёв B.A., Лаходынова H.B. Алгоритм реконфигурации процессорной матрицы на основе сигналов согласия // Международная кон-

ференция "Автоматизация проектирования дискретных систем": Тезисы докладов. - Минск, 1995, Т. 1. - С. 13.

16.Воробьёв В.А.,-Ерёмина H.JL, Лаходынова Н.В. Анализ алгоритмов перестройки структуры процессорной матрицы // Автометрия, № 3 - 1996.-С. 69-77.

17.Vorobyev V.A., Eremina N.L., Lakhodinova N.V. Analysis of the algorithms of a processor array structure reconfiguration (Анализ алгоритмов перестройки структуры процессорной матрицы)// Optoelectronics, Instrumentation and Data Processing, № 3. - 1996. - P. 69-77.

18.Воробьёв В.А., Ерёмина Н.Л., Лаходынова H.B. Алгоритмы адресации отказоустойчивой процессорной матрицы на СБИС // Новые информационные технологии в исследовании дискретных структур: Доклады всероссийской конференции. -Екатеринбург: УрО РАН, 1996. -С. 109-111.

19.Воробьёв В.А., Лаходынова Н.В. Реконфигурация отказоустойчивой процессорной матрицы на основе сигналов согласия // Автометрия, №6.- 1997. -С. 108-113.

20.Vorobyev V.A., Lakhodinova N.V. Reconfiguration of fault-tolerant processor arrays on the basis of agreement signals (Реконфигурация отказоустойчивой процессорной матрицы на основе сигналов согласия) // Optoelectronics, Instrumentation and Data Processing, № 6. - 1997. - P. 108-113.

21. Воробьёв B.A., Лаходынова H.B. Вложение решёток в процессорную матрицу с отказами на основе сигналов согласия // Новые информационные технологии в исследовании дискретных структур: Доклады всероссийской конференции. -Екатеринбург: УрО РАН, 1998. -С. 153-156.

22.Лаходынова Н. В. Исследование алгоритмов реконфигурации процессорной матрицы и задача просачивания // Моделирование неравновесных систем, материалы III Всероссийского семинара, - Красноярск, 20-22 октября 2000 года. - С. 145-146.

23.Лаходынова Н. В., Воробьева Т.В. Задача просачивания для моделирования финансовых потоков // Моделирование неравновесных систем, материалы IV Всероссийского семинара, - Красноярск, 12-14 октября 2001 года. - С. 23.

24.Лаходынова Н. В. Анализ алгоритмов реконфигурации структуры процессорной матрицы на основе сигналов согласия // Радиоэлектроника. Информатика. Управление. № 2, 2001. - С. 98-102.

25. Лаходынова Н. В. Просачивание в однородных структурах с согласием // Материалы П Всесибирского конгресса женщин-математиков, Красноярск, 15-20 января 2002 года. - С. 17.

26.Лаходынова Н.В. , Воробьев В.А., Еремина H.JI. Отказоустойчивость однородных процессорных матриц. - Томск: Томский государственный архитектурно-строительный университет, 2002. - 154 с.

27. Лаходынова Н. В. Об эффективности алгоритмов реконфигурации процессорной матрицы на основе консенсуса // Вестник Томского государственного университета, приложение №1, сентябрь 2002. Материалы научных конференций, симпозиумов, школ, проводимых в ТГУ. С. 320-325.

28.Воробьев В.А., Лаходынова Н. В. Отказоустойчивость процессорных матриц: консенсус-парадигма // Вестник Томского государственного университета, приложение №1, сентябрь 2002. Материалы научных конференций, симпозиумов, школ, проводимых в ТГУ. С.339-343.

29.Лаходынова Н.В. Об одном методе обеспечения отказоустойчивости процессорных матриц // Автометрия, № 6, т. 38. - 2002. - С.79-87.

30.Lakchodinova. N.V. About one method of ensuring of fault tolerance of without-cut processor arrays VLCI. (Об одном методе обеспечения отказоустойчивости процессорных матриц) // Optoelectronics, Instrumentation arid Data Processing, № 6, v. 38. - 2002. - P. 79-87.

31.Лаходынова H. В. Задача просачивания и надежность однородных структур. Радиоэлектроника. Информатика. Управление. № 2, 2002. -С. 96-100.

32.Лаходынова Н.В. О порогах просачивания в однородных структурах // Автометрия, № 3, т. 39. - 2003. - С. 35-42.

33.Lakchodinova. N.V. About limits of penetration in homogenous structures (О порогах просачивания в однородных структурах) // Optoelectronics, Instrumentation and Data Processing, № 3, v. 39. - 2003. - P.35-42.

Изд. лиц. №021253 от 31.10.97. Подписано в печать /£.£>3. Формат 60x90/16. Бумага офсет. Гарнитура Тайме, печать офсет. Уч.-изд.л. Тираж экз. Заказ № ¿/'/У

Изд-во ТГАСУ, 634003, г. Томск, пл. Соляная, 2 Отпечатано с оригинал-макета в ООП ТГАСУ. 634003, г. Томск, ул. Партизанская, 15.

РНБ Русский фонд

20074 14864

21 с:,: m

ВВЕДЕНИЕ

ГЛАВА 1. ОВС КАК СЛУЧАЙНОЕ ПОЛЕ

1.1. Концепция ОВС

1.1.1. Основные принципы построения параллельных вычислительных систем

1.1.2. ОВС с программируемой структурой

• 1.1.3. Современное состояние параллельных систем

1.2. Локальные однородные структуры

1.2.1. Структура вычислительной системы

1.2.2. Локальность

1.2.3. Однородность

1.2.4. Периодичность

1.3. Ординарная динамическая модель ОВС

1.3.1. Модели коллективов вычислителей

1.3.2. Структурные характеристики ОВС

1.3.3. Ординарная динамическая клеточная модель

1.4. Состояния ординарных динамических систем

1.4.1. О теории случайных полей

1.4.2. Состояния на конечных графах

1.4.3. Эргодичность

1.4.4. Обратимые системы л 1.4.5. Надежность однородных структур

1.4.6. Резюме

1.5. Основные результаты главы

ГЛАВА 2. ОТКАЗОУСТОЙЧИВОСТЬ НПМ С ТОЧКИ ЗРЕНИЯ ТЕОРИИ ПРОСАЧИВАНИЯ

2.1. Проблема надежности

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

2.1.2. Традиционные подходы к обеспечению отказоустойчивости

2.1.3. Необходимость новой парадигмы структурной живучести

2.2. Статическая модель структурной надежности.

2.2.1. Проблема живучести ОВС

2.2.2. Статическая модель структурной надежности

2.3. Динамические модели живучести ОВС

2.4. Исследование порогов просачивания

2.4.1. Постановка задачи

2.4.2. Метод моделирующей решётки

2.4.3 Метод второй производной

2.4.4. Смешанная задача просачивания

2.4.5. Обсуждение результатов

2.5. Реальная парадигма живучести ОВС

2.6. Основные результаты главы

ГЛАВА 3. АЛГОРИТМЫ РЕКОНФИГУРАЦИИ

НЕРАЗРЕЗНЫХ ПРОЦЕССОРНЫХ МАТРИЦ (НПМ)

I 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.3. Эффективность алгоритмов реконфигурации

3.3.1. Эффективность алгоритмов реконфигурации

3.3.2. Выбор резерва

3.3.3. Работоспособность алгоритмов реконфигурации

3.3.4. Резюме

3.4. Архитектура ОВС на НПМ с программируемым резервом

3.4.1. Архитектура ОВС

3.4.2. Недостатки схемной реализации

3.4.3. Архитектура ОВС с программной реконфигурацией НПМ

3.4.4. Резюме

3.5. Основные результаты главы

ГЛАВА 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. Оценка эффективность волнового алгоритма

4.3.3. Волновой алгоритм и задача просачивания

4.3.4. Резюме

4.4. Основные результаты главы

Актуальность исследования. Одним из прорывных направлений современной науки и техники является достижение общедоступной сверхвысокой производительности ЭВМ - более чем 1013-*-1014 флопс. От успешного внедрения и использования таких супер-ЭВМ зависит стратегическая позиция современных государств в нарождающемся сложном постиндустриальном мире. Так для всемирного экологического (и, очевидно, не только экологического) мониторинга США построили массово-параллельный суперкомпьютер с объявленным быстродействием ЗхЮ13 флопс.

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

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

Концепция ОВС занимает видное место в развитии супер-ЭВМ. Например, вычислительные кластеры серии МВС-100 и МВС-100Х, предлагаемые НПО «Квант», реально представляют собой ОВС на процессорных матрицах, а полносвязность структуры их межмашинных связей является виртуальной [8]. К тому же классу относится упомянутая выше стратегическая вычислительная система США. Растет число публикаций, теоретических и практических разработок в рамках этой концепции. Результаты этого развития впечатляющие. Достигнута пиковая производительность стратегических массово-параллельных систем, исчисляемая десятками терафлопс, однако такие системы всё ещё уникальны, крупногабаритны и слишком дороги.

Концепция ОВС была сформулирована в Институте математики СО АН СССР под руководством Э.В. Евреинова [1] в 1962 году и успешно развивается в настоящее время, являясь ведущей при построении систем сверхвысокой производительности. В России значительный вклад в развитие ОВС внесли Косарев Ю.Г., Хорошевский В.Г., Бандман О.Л., Прангишвили И.В., Медведев И.Л., Воробьев В.А., Корнеев В.В., Димитриев Ю.К., Глушков В.М., Каляев А.В., Лазарев В.Г., Додонов А.Г., Артамонов Г.Т. и многие другие.

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

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

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

Важнейшие особенности неразрезной технологии СБИС:

1) невозможность замены отказавших элементов;

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

3) однородность и близкодействие структур связей;

4) стремление к экономии оборудования.

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

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

Цель исследования — развитие теоретических основ построения отказоустойчивых ОВС, разработка программно-аппаратных методов обеспечения отказоустойчивости процессорных матриц с программируемой структурой, в том числе (и в особенности) НПМ СБИС.

Основные задачи диссертации: I. Разработка математических моделей ОВС, позволяющих исследовать отказоустойчивость ОВС и методы ее обеспечения, как аналитически, так и моделированием на ЭВМ.

2. Исследование фундаментальных пределов отказоустойчивости и надежности однородных структур (графов).

3. Разработка и исследование новых парадигм обеспечения отказоустойчивости ПМ и НПМ СБИС.

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

5. Исследование работоспособности, эффективности и статистических свойств разработанных алгоритмов.

6. Разработка архитектуры ОВС на ПМ и НПМ СБИС.

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

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

1. Разработаны математические модели, предназначенные для исследования надёжности и отказоустойчивости ОВС, отличающиеся от известных учетом влияния структуры связей.

2. Исследованы фундаментальные пределы отказоустойчивости однородных коммутационных структур ПМ и НПМ СБИС.

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

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

5. Предложен новый подход к обеспечению отказоустойчивости НПМ: консенсус-парадигма.

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

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

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

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

• кафедре прикладной математики Томского государственного архитектурно-строительного университета.;

• докладывались на 12-ти международных, всесоюзных и всероссийских, а также на региональных, городских и вузовских конференциях, совещаниях и школах-семинарах в Москве, Минске, Риге, Новосибирске, Томске, Екатеринбурге, Байконуре, Красноярске;

• поддерживались фондом грантов Министерства образования РФ.

Публикации. По тематике диссертации опубликовано 34 научных работы, из них: печатных - 33, из них: монографий - 1, учебных пособий — 1, в центральных изданиях - более десятка, в трудах всесоюзных, всероссийских и международных конференций - 9, в трудах региональных конференций — 3, в иностранной печати - 7.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, библиографии и приложения. Общий объём диссертации - 236 страницы. Из них: 1 страница титульная; 3 страницы содержания (83 пункта); 207 страниц основного текста, содержащего 28 рисунков и 14 таблиц; 23 страницы библиографии на 276 названий; 2 страницы приложения. В приложение вынесено описание языка ЛОГИКА.

4.4. Основные результаты главы 4

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

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

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

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

4. Предложена архитектура ОВС на ПМ и НПМ СБИС с программной реализацией метода консенсуса. Эта архитектура требует функциональной неразличимости вертикальных и горизонтальных связей в процессорной матрице, что полностью соответствует теории КАИС-структур ОВС.

5. Исследована методом моделирования на ЭВМ работоспособность и эффективность метода консенсуса. Эксперимент подтвердил, что он является наиболее эффективным по сравнению с известными алгоритмами. В этом смысле он является предельным.

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

ЗАКЛЮЧЕНИЕ

Перечислим основные результаты диссертации.

I. Подтверждена перспективность и решающая роль концепция ОВС в развитии современных массово-параллельных процессоров.

II. Построена ординарная динамическая клеточная модель параллельной вычислительной системы. Исследованы ее стохастические свойства.

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

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

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

III. Исследована перколяционная модель структурной надежности.

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

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

3. Даны два метода поиска порогов просачивания для произвольных однородных структур: метод моделирующей решётки и метод второй производной. Приведено точное решение классической задачи Хаммерсли для квадратной и шестиугольной решёток.

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

IY. Исследованы подходы (парадигмы) к проблеме отказоустойчивости

1. Критически рассмотрены традиционные методы обеспечения отказоустойчивости вычислительных систем, в том числе основанные на взаимопроверках с построением синдрома неисправностей, и показана их недостаточность для решения проблемы отказоустойчивости ПМ и НПМ СБИС.

2. Обоснована необходимость смены подхода к обеспечению отказоустойчивости НПМ СБИС из-за невозможности замены отдельных элементов, неограниченных требований к степени связности модулей, отсутствия близкодействия и неадекватности "византийского согласия" всех исправных ПЭ.

3. На основе анализа источников отказов в СБИС и исследования пределов их надёжности сформулирована реальная парадигма живучести НПМ СБИС, учитывающая отказы ПЭ и связей и позволяющая использовать все полученные СБИС.

5. Y. Предложены и исследованы новые методы обеспечения отказоустойчивости ОВС на ПМ и НПМ СБИС.

6. На основе анализа источников отказов в СБИС и реальной парадигмы живучести НПМ СБИС, учитывающей отказы ПЭ и связей, предложен метод программирования резерва ПМ и НПМ СБИС, позволяющий менять избыточность от нуля или минимума в одну строку или столбец до максимума — четырёхкратной избыточности.

7. Предложены и исследованы алгоритмы реконфигурации НПМ СБИС с программируемым резервом: вертикальной перестройки, непосредственной перестройки, ограниченного захвата и свободного захвата.

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

9. Предложена архитектура ОВС на неразрезных процессорных матрицах СБИС с программируемым резервом.

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

11. Показана возможность программной реализации МПКА, свободной от неконтролируемых элементов процессорной матрицы.

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

YI. Предложена новая консенсус-парадигма структурной живучести.

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

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

3. Предложена архитектура ОВС на неразрезных процессорных матрицах СБИС с программной реализацией метода консенсуса. Эта архитектура требует неразличимости вертикальных и горизонтальных связей в решающем поле, что полностью соответствует требованиям теории КАИС-структур.

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

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

6. Попутно получены приближенные значения для вероятностей просачивания по узлам и связям для случая смешанной задачи просачивания.

1. Евреинов Э.В. О возможности построения вычислительных систем высокой производительности / Э.В. Евреинов, Ю.Г. Косарев Новосибирск: Институт математики СОАН СССР, 1962.

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

3. Евреинов Э.В. Однородные вычислительные системы / Э.В. Евреинов, В.Г. Хорошевский Новосибирск: Наука, 1978.

4. Мамзелев И.А. Некоторые вопросы теории модели коллектива вычислителей // Вычислительные системы, М.: Финансы и статистика, 1981.- Вып. 2. - С. 63-68.

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

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

7. Каляев А.В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1984.

8. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. -320 с.

9. ТИИЭР, T.72, № 1, Супер-ЭВМ: воздействие на развитие науки и техники /пер. с англ./. М.: Мир, 1984.

10. П.Хокни Р., Параллельные ЭВМ. / Р. Хокни., К. Джесхоуп.-М.: Радио и связь, 1986.

11. Фрир Дж. Построение вычислительных систем на базе перспективных микропроцессоров. М.: Мир, 1990.

12. Anthes G.H., . INTERVIEW: Seymour R.Cray, Head of Cray Computer Corp/ G.H. Anthes, C. Babcock // Computer World, № 35 . Moskow, 1994, - C. 51.

13. Babcock C. Will the Cray-4 Be the Next Supercomputing Coup // Computer World, № 35. Moskow, 1994. - C. 50.

14. ЭВМ с массовым параллелизмом завоёвывают сферу бизнеса// Computer World-Moskow, № 49.-1994, С. 53,55-58.

15. Mokhoff N. Parallelism makes strong big for a next generation computers // Comput. Des., V.23, № 10.-1984.- P. 104-108,110,112-114,116-118,120-124, 126-131.

16. Christ N.H. A very fast parallel processor / N.H. Christ, A.Terrano // IEEE Trans. Comput., V.33, № 4 .-1984.- P. 344-350.

17. Killmon P. Computers tackle callenges of the 90s // Comput. Des, V.24, № 17.- 1986.-P. 47-50,52,56.19.0hr S. Engineering computers. Technology forecast // Electron. Des., V.35, № 1.- 1987.-P. 104-107,112-113, 116,118.

18. Соколова Г.Н. Состояние и тенденции развития зарубежной высокопроизводительной вычислительной техники // Вычислительная техника за рубежом в 1986-87 г. -М.: Изд-во ИТМ и ВТ, 1987.- С.3-22.

19. Головня В.Н. Особенности развития архитектуры высокопроизводительных вычислительных машин // Вычислительная техника за рубежом в 1986-87 г. М.: Изд-во ИТМ и ВТ, 1987. - С.102-139.

20. Peacock J.K. Application dictates your choice of a multiprocessor model // EDN, V.32, № 13.- 1987.-P. 241-248.

21. ТП1 J. Computer sistem architecture // Electron. Des., V.37, №1.-1989. P. 1,50-54, 56, 58, 60, 62-63.

22. Bond J. Parallel-processing concepts finally come together in rial systems // Comput. Des., V.26, № 11. -1987. P. 51-52, 54, 56, 58, 60-65, 67-68, 73-74.

23. Hwang K. Advanced parallel processing with supercomputer architectures // Proceedings of the IEEE / ТИИЭР, перевод с англ./ V.75, № 10.- 1987. С. 4- 40.

24. Головкин Б.А. Технико-экономические модели и оценки ЭВМ // Зарубежная радиоэлектроника, №1. -1988. С. 3-25.

25. Weiss S. Scalar Supercomputer Architecture.// Proceeding IEEE / ТИИЭР, перевод с англ. / У .11, №12 .- 1989.-С. 197-211.

26. Rau B.R. Efficient code generation for horizontsl architectures: Compiler techniques and architecturl support / B.R.Rau, C.D.Glaeser, R.L. Picard // Proc. 9tn Int. Symp. Computer Architecture (Austin, TX, Apr.1982), P. 131-139.

27. Cohler E.U., Stohrer J.T. Functionally parallel architectures for array processors // Compuer, V.14, №9.-1981. P. 28-36.

28. Fisher J.A. The VLIW machine: A multiprocesor for compiling scientific code // Computer, V.17, №7.-1984. P. 45-53.31 .Fisher J.A. VLIW architectures: Supercomputing via overlapped execution // Second Int. Conf. Supercomputing. -1987.

29. Colwell R.P. and other. A VLIW arxhitecture for a trace schelduling compiler // Second Int. Conf. on Architecture Support for Programming Languages and Operating Systems, Palo Alto, CA, Oct. 1987.

30. Smith J.E. and other, The ZS-1 Central Processor.// Second Int. Conf. on Architecture Support for Programming Languages and Operating Systems, Palo Alto, CA, Oct. 1987.

31. Rau B.R. and other // IEEE Comput., V.22, №1 .-P. 12-35.

32. Charlesworth A.E. An approach to scientific array procesing: The architectural desing ofthe АР-120B/FSP-164 family.// Computer, 1981, V.14, №9, P. 18-27.

33. Головкин Б.А. Параллельные вычислительные системы.-М.: Наука, 1980.

34. Королёв JI.H. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1974.

35. Parhi К.К. Algorithm Transformation Techniques for Concurrent Proceccors // Proceedings ofthe IEEE /ТИИЭР, перевод с англ./, V.77, №12.- 1989. С. 96-115.

36. Шпаковский Г.И. Метод планирования трасс и архитектуры ЭВМ со сверхдлинной командой // Зарубежная радиоэлектроника, № 11. -1991. С.10-27.

37. Власов В.В. Организация и функционирование специализированных вычислительных систем, управляемых потоком данных / В.В.Власов, О.А.Рахматулин, Вл.К Ю // Зарубежная радиоэлектроника, № 7,8,9. -1993. С. 18-31.

38. Крайников А.В. СБИС-архитектура высокопроизводительных процессоров потоков данных / А.В.Крайников, О.А.Рахматулин, Вл.К. Ю //Зарубежная радиоэлектроника, № 8.-1992. С. 111-134.

39. Potter J.L. Array Processor Supercomputers // Proceedings of the IEEE, /ТИИЭР, перевод с англ./ V.77, №12. -1989. С. 115-135.

40. Siegel H.J. and other. PASM: A partitionable SIMD/MIMD system for image processing and pattern recognition // IEEE Trans. Comput., V.C-30, №12. 1981. - P. 934-947.

41. Stoflo S J. DADO: A parallel processor for expert systems / S J.Stoflo , D.P. Miranker // Proc. 1984 Int. Conf. Parallel Processing. -1984. -P. 74-82.

42. Show D.E. "NON-VON"s applicability to three A1 task areas // Proc. 9th Int. Joint Conf. Artificial Intelligence (Los Angeles, CA, Aug. 18-23, 1985). P. 61-72.

43. Воробьёв К.Ю. Иерархическая обработка изображений и пирамидальные системы / К.Ю.Воробьёв, Г.Н.Тимонькин, В.С.Харченко, В.А. Мельников // Зарубежная радиоэлектроника, №7. 1991. - С. 51-60.

44. Палташёв Т.Т. Растрирование и распределённая обработка в системах генерации реалистических изображений / Т.Т.Палташёв, С.И.Климина // Зарубежная радиоэлектроника, №11. 1992. - С. 3-22.

45. Бандман О.Л. Организация массовых вычислений в оптических компьютерах: обзор // Зарубежная радиоэлектроника, № 2. 1992. - С. 64-75.

46. Berra Р. В. and other. Optics and Supercomputing // Proceedings of the IEEE /ТИИЭР, перевод с англ./, V.77, №12. 1989. - С. 5-23.

47. Streibl N. and oter. Digital Optics // Proceedings of the IEEE /ТИИЭР, перевод с англ./, V.77, №12. 1989. - С. 179-196.

48. Spectrum, V.25, № 3. -1988.- P. 36-41.

49. Чебатко М.И. Нейронные сети для решения задач на борту летательных аппаратов.// Зарубежная радиоэлектроника, №11,12.- 1994. С. 40-44.

50. Forrest В.М., and other, Implementing neural network models on parallel computers // Comput. J., V.30, № 5,- 1986.- P. 413-419.

51. Milutinovic V. Mapping of Neural Networks on the Honeycomb Architecture // Proceeding of the IEEE, 1989, V.77, №12, /ТИИЭР, перевод с англ., С. 91-95./

52. Kung Н.Т. Systolic arrays (for VLSI). / H.T.Kung, G.E.Leiserson In: Proc. Symp. Sparse Matrix Computations and Applications. Society for Industr. and Applied Math., 1979, P. 256-289.

53. Kung H.T. The Structure of Parallel Algorithms // Advances in Computers, V.19. New-York, 1980.-P. 65-112.

54. Moldovan D.I. On the Desing of Algorithms for VLSI Systolic Arrays // Proceedings of the IEEE, /ТИИЭР, перевод с англ./, V.71, №1.-1983. С. 140-149.

55. IEEE Trans. Comput., V.33, №4.- P. 361-364.

56. Kung H.T. Why Systolic Architectures? // Computer, V.15, № 1. 1982.-P. 37-46.

57. Kung S.-Y. Wavefront array processor: lanquage, architecture and aplications / S.-Y.Kung, K.S.Arun, RJ.Gal-Ezer, V.Bhaskar Rood. // IEEE Trans. Comput., V.31, N11.-1982.- P. 1054-1066.

58. Kung S.-Y. On Supercomputing with Systolic Wavefront Array Processors // Proceedings of the IEEE /ТИИЭР, перевод с англ./, V.72, №7. -1984. - С. 133- 153.

59. Anaratone М. and other, The Warp computer: architecture, implementation and performance // IEEE Trans. Comput., V.36, № 12.- 1987.- P. 1523-1538.

60. Барон И. Транспьютер // Электроника, Т.56, № 23.-1983. С. 104.

61. Транспьютеры. Архитектура и программное обеспечение. /Пер. с англ. под ред. Г.Харпа/. М.: Радио связь, 1993.

62. Мишин А.И., Однородные вычислительные системы и параллельные вычисления / А.И.Мишин, С.Г.Седухин // Автоматика и вычислительная техника, N1.- 1981.-С. 20-24.

63. Воробьёв В.А. Модель коллектива вычислителей, основанная на принципе близко-действия // Вычислительные системы с программируемой структурой: Вычислительные системы, 94. -Новосибирск: Институт математики СОАН СССР, 1982 . -С.103-119.

64. А.И.Мишин // Институт математики СО АН СССР, Препринт № 20. Новосибирск, 1985.

65. В.А.Воробьёв В.А. Близкодействующая архитектура вычислительной системы /В.А.Воробьёв, Н.ВЛаходынова // Перспективы развития вычислительных систем. III Всесоюзный симпозиум, Рига, 31.10-2.11, 1989: Тезисы докладов. -Рига, 1989. -С. 20.

66. Воробьёв В.А. Теоретические основы построения однородных вычислительных систем на неразрезных процессорных матрицах. Дис. .докт. наук. /ИПУ/.- Москва. 1999. -350 с. -рук.

67. Михайлов С.А. Перспективные принципы построения сверхбольших интегральных схем // Зарубежная радиоэлектроника, №12 . -1991. С. 3-14,33.

68. Бубенников А.Н. Мировые программы освоения высоких субмикронных технологий конкурентноспособных СБИС / А.Н.Бубенников, А.А. Бубенников // Зарубежная Радиоэлектроника, № 2. -1993. С. 75-85.

69. Бубенников А.Н. Тенденции развития конкурентноспособных кремниевых КИзд-во МОП-, биполярных и БИКИзд-во МОП-СБИС / А.Н.Бубенников, А.А. Бубенников //Зарубежная Радиоэлектроника, № 1. -1994.-С. 2-3.

70. Васильев Б.М. Микропроцессоры: история, развитие, технология / Б.М.Васильев, А.П.Частиков // Зарубежная Радиоэлектроника, № 2-3. -1994. С. 52-61.

71. Рогожин В.Б. Два миллиарда операций в секунду // Мир ПК, №7.-1994. С. 23-26.

72. Борзенко А. На пути в будущее: микропроцессор Petium Pro // Компьютер Пресс, № 12.-декабрь 1995.-С. 131.

73. Батыгов М. Современные процессоры для ПК: сравнение производительности / М.Батыгов, О.Денисов // Компьютер Пресс, № 12.- декабрь 1996. С. 94-106.

74. Рыбаков А. Процессоры семейства Power PC // Компьютер Пресс, № 2.-1996. С. 86-88, 90, 92-93.

75. Черняк Л. Рабочие станции Ultra шаг Sun в XXI век // Компьютер Пресс, № 2,1996. - С. 95-100.

76. Поляков В. Микропроцессоры: между прошлым и будущим // Компьютер пресс, №4.-1996. С. 62-67.

77. Кииз Р.У. Физические ограничения цифровых электронных схем // ТИИЭР, Т. 63, № 5. -1975. С. 5-38.

78. Кииз Р.У. Фундаментальные пределы в цифровой обработке информации // ТИИЭР, Т. 62 , №2 .-1981. С. 152-166.

79. Schorr A. Pysical parallel devices are not mach faster then sequential ones // Inf. Process Lett.,V.17, №2. -1983. P. 103-106.

80. KOTOB B.E. Перспективы и проблемы создания ЭВМ на сверхбольших интегральных схемах. — // Теоретические вопросы параллельного программирования и многопроцессорных ЭВМ. -Новосибирск: ВЦ СО АН СССР, 1983.

81. Grosch H.R.J // J. Optical Soc. America, V.43, № 4. -1953.

82. Amdahl G. The validity of the single processor approach to achieving large-scale computing capabilities // Proc. AFTPS Spring Joint Computer Conf. V.30, (Atlantic City, NJ, Apr. 18-20). Reston: AFTPS Press, VA, 1967.- P. 483-485.

83. Gallant J. Parallel processing ushers in a revolution in computing // EDN, V.33, № 18.1988.- P. 86,89-94,96,98,100.

84. Gustafson J.L. Reevaluation Amdal's law // Commun. ACM, V.31, №5. -1988.- P. 532533.

85. Buzbee B. Parallel processing makes tough demands // Comput. Des., V.23, №10.1984.- P. 137-140.

86. Hillis W.D. Data parallel algorithms / W.D.Hillis, G.L.Steele // Commun. ACM, V.29, № 12.-1986.- P. 1170-1183.

87. Косарев Ю.Г. О схемах обмена между ветвями параллельных алгоритмов // Вычислительные системы, Вып 52, Новосибирск: Институт математики СО АН СССР, 1972, С. 70-75.

88. Вальковский В.А. Синтез параллельных программ и систем на вычислительных моделях. / В.А.Вальковский, В.Э.Малышкин — Новосибирск: Наука, Сибирское отделение, 1988,- 128 с.

89. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989.

90. Волович В.М. О решении систем линейных алгебраических уравнений клеточными методами // Вычислительные методы и программирование. М.: Изд-во МГУ.-Вып.З,- С. 106-133.

91. Миренков Н.Н. Параллельное программирование мультимодульных вычислительных систем. М.: Радио и связь, 1989.99.0ртега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991.

92. Воробьёв В.А. Эффективность параллельных вычислений // Автометрия. № 1, -2001,-С. 50-57.

93. Седухин С.Г. Параллельно-поточная интерпретация метода Гаусса // Вычислительные системы с программируемой структурой: Вычислительные системы, 97.-Новосибирск: Институт математики СОАН СССР, 1983. С. 10-27.

94. Корнеев В.В. Современные микропроцессоры / В.В. Корнеев, А.В. Киселев . 2-е изд. - М. : Нолидж, 2000. - 315 с.

95. ЮЗ.Седухин С.Г. Параллельно-поточная интерпретация метода Холецкого // Электронное моделирование, Т.6, № 6.-1984. С. 3-6.

96. Мишин А.И. Асинхронно-локальные вычислительные системы и среды / А.И.Мишин, В.А.Леус -Новосибирск: Институт математики СОАН СССР, 1991. -178 с.

97. Ачасова С.М. // Корректность параллельных вычислительных процессов / С.М.Ачасова, О.Л Бандман -Новосибирск: Наука, Сиб. отделение, 1990.

98. Воробьёв В.А. Программное обеспечение систем логического управления ДА: Учебное пособие. /В.А. Воробьёв, Н.В.Лаходынова М.: Изд-во МАИ , 1991.- 39 с.

99. Achasova S.M. Correctness of mixed cellular computations // Bulletin of the Novosibirsk Computing Center, Series: Computer Science, Issue: 2(1993), P. 1-11.

100. Ю.Фон Нейман Дж. Теория самовоспроизводящихся автоматов. — М.: Мир, 1971.

101. Ш.Корнев Ю.Н. Алгоритмы обобщенных подстановок и их интерпретация сетями автоматов и однородными машинами / Ю.Н.Корнев, С.Н.Пискунов, С.Г.Сергеев // Изв. АН СССР. Техническая кибернетика, № 6.-1971. С. 131-142.

102. Варшавский В.И. Коллективное поведение автоматов. М.: Наука, 1973.

103. ПЗ.Бандман O.JI. Асинхронная интерпретация параллельных микропрограмм: Препринт ОВС-14. Новосибирск: Институт математики СО АН СССР.- 1981.-36 с.

104. Тоффоли Т. Машины клеточных автоматов / Т.Тоффоли, Н.Марголус /Перевод с англ. под ред. Баталова Б.В./. М.: Мир, 1991.

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

106. Абрамова НА. Однородные логические сети и их группы автомофизмов // Автоматика и телемеханика, № 11.-1970.

107. Евреинов Э.В. Цифровые автоматы с настраиваемой структурой. Однородные среды. / Э.В.Евреинов, И.В.Прангишвили М.: Энергия, 1974.

108. Воробьёв В.А. Простейшие структуры однородных вычислительных систем // Вычислительные системы.-Новосибирск: Институт математики СО АН СССР. -Вып.60. 1974.- С. 35-49.

109. Воробьёв В.А. Некоторые вопросы теории структур однородных вычислительных систем / В.А.Воробьёв, В.В.Корнеев // Вычислительные системы.-Новосибирск: Институт математики СОАН СССР. -Вып.60. 1974.- С. 3-16.

110. Воробьёв В.А. Элементы теории структур однородных вычислительных систем / В.А.Воробьёв, В.В.Корнеев // Однородные вычислительные системы и среды: Материалы IV Всесоюзной конференции. -Киев. 1975.-Ч.1.- С. 33-34.

111. Монахов О.А. Параметрическое описание структур ОВС // Вычислительные системы. -Новосибирск: Институт математики СОАН СССР. Вып.80. - 1979.- С. 3-17.

112. Воробьёв В.А. К теории структур однородных вычислительных систем /

113. B.А.Воробьёв, Ю.А.Гавырин // XXXIII Всесоюзная научная сессия, посвященная дню радио. Аннотация и тезисы докладов. — Москва. 1978, - С. 44.

114. Монахова Э.А. Синтез оптимальных диофантовых структур // Вопросы теории и построения вычислительных систем: Вычислительные системы, 80.-Новосибирск: Институт математики СОАН СССР.-1979. С. 18-35.

115. Сыскин С.А. О существовании предельных КАИС-структур // Однородные вычислительные системы: Вычислительные системы. 90.- Новосибирск: Институт математики СОАН СССР.-1981. - С. 78-80.

116. Монахова Э.А. Об аналитическом задании оптимальных двумерных диофантовых структур однородных вычислительных систем // Однородные вычислительные системы: Вычислительные системы. 90.- Новосибирск: Институт математики СОАН СССР.-1981. - С. 81-91.

117. Кестен X. Теория просачивания для математиков. — М.: Мир, 1986.

118. Лаходынова Н.В. Анализ и разработка методов обеспечения отказоустойчивости однородных вычислительных систем: Дис. . канд. техн. наук. /МИС/.- Москва. -1991.-135 с.-рук.

119. Аверинцев М.Б. Об одном способе описания случайных полей с дискретным аргументом // Проблемы передачи информации. 6. 2. - 1970. - С 100-108.

120. Басис В.Я. О стационарности. и эргодичности многокомпонентных марковских процессов с локальными взаимодействиями. // В сб.: Многокомпонентные случайные системы. М.: Наука. - 1978. - С. 31-46.

121. Васильев Н.Б. Обратимые цепи Маркова с локальными взаимодействиями / Н.Б.Васильев, О.К.Козлов // В сб.: Многокомпонентные случайные системы. М.: Наука. - 1978. - С.83-99.

122. Добрушин P.JI. Задание системы случайных величин при помощи условных распределений // Теория вероятностей и ее применения . 15. № 3. - 1970. - С.469-497.

123. Добрушин P.JI. Описание случайного поля при помощи условных вероятностей и условия его регулярности. // Теория вероятностей и ее применения. 13. № 2. -1968. - С. 201-229.

124. Добрушин P.JI. Описание случайного поля при помощи условных вероятностей и приложения к статистической физике. // Институт проблем передачи информации АН СССР. М. - 1968. С. 61.

125. Добрушин P.JI. Марковские процессы с большим числом компонент обратимый случай и некоторые обобщения. // Проблемы передачи информации. - 7. №3. -1971. - С.57-66.

126. Розанов Ю.А. Исследование свойства марковости случайных полей // В сб.: Итоги науки и техники ВИНИТИ. Современные проблемы математики, 14. 1979. - С. 3-70.

127. Розанов Ю.А. О гауссовских полях с заданными условными распределениями. // Теория вероятностей и ее применения. 12. № 3. - 1967. - С. 433-443.

128. Вассерштейн JI.M. Марковские процессы на счетном произведении пространств, описывающие большие системы автоматов.//Проблемы передачи информации. 5. № 3. - 1969. С. 64-71

129. Goldstein Sheldon. Remarks on the global Markov property. // Commun. Math. Phys. -74. № 3. 1980. - P.223-234.

130. Dang-Ngoe N. Markov property of extremal local fields // N.Dang-Ngoe, G. Royer -Proc. Amer. Math. Soc. 70, №2. - 1978. - P.185-188.

131. Kesten Harry. Existeme and uniqueness of countable one-dimensional Markov random fields // Ann. Probab. 4. № 4. - 1976. - P.557-569.

132. Moran P.A.P. Nesessary conditions for Marcovian processes on a lattice // J. Appe. Probab. 10, № 3. - 1973. - P.605-612.

133. Nelson Edward. Markov fields // Proc. Int. Congr. Math. Vancouver. V.2. S.l. - 1974.- P.395-398.

134. Spitzer Frank. Markov random fields on an infinite tree. // Ann. Probab. 3. 1975. - P. 387-398.

135. Аверинцев М.Б. Описание марковских случайных полей при помощи гиббсовских условных вероятностей // Теория вероятностей и ее применения. 17. № 1. - 1972. -С.21-35.

136. Аверинцев М.Б. Гиббсовское описание случайных полей, условные вероятности которых могут обращаться в ноль // Проблемы передачи информации. — 11. №4. -1975. С.86-96.

137. Герцик В.М. Условия неединственности гиббсовского состояния для решетчатых моделей с финитным потенциалом взаимодействия // Изв. АН СССР, Сер. Мат.- 40. №2. 1976. - С. 448-462.

138. Добрушин Р.Л. Марковские процессы с большим числом компонент обратимый случай и некотрые обобщения // Проблемы передачи информации. - 7. № 3. - 1971.- С. 57-66,

139. Добрушин Р.Л. Исследование гиббсовских состояний для трехмерных решетчатых систем // Теория вероятностей и ее применения, 8. № 2. - 1973. - С.261-279.

140. Добрушин Р.Л. Гиббсовское состояние, описывающее существование фаз для трехмерной модели Изинга // Теория вероятностей и ее применения, 17, № 4. -1972. - С.619-639.

141. Добрушин Р.Л. Задача единственности гиббсовского случайного поля и проблема фазовых переходов // Функциональный анализ и его приложения, 2. №4. 1968. -С.44-57.

142. Козлов O.K. Гиббсовское описание точечных случайных полей // Теория вероятностей и ее применения. 21, № 2. - 1976. - С.348-365.

143. Козлов O.K. Гиббсовское описание системы случайных величин // Проблемы передачи информации. -. 10, №3. 1973. - С.94-103.

144. Мартиросян Д.Г. Периодические гиббсовские состояния для классических решетчатых систем // Изв. АН АРМ СССР, серия математика. 14, № 1. - 1979. - С.21-41.

145. Престон К. Гиббсовские состояния на счетных множествах. М., Мир, 1977. -122 с.

146. Geogii Hans-Otto. Canonical and grand canonical Gibbs states for continuum systems // Commun. Math. Phys. 48, № 1. - 1976. - P.31-51.

147. Georgii Hans-Otto. Canonical Gibbs measures. Some extensions of the Finetti representation theorem for interacting particle systems // Lect. Notes. Math. 760, 8. -1979.-P.190.

148. Grosso G. Del. On the local central limit theorem for Gibbs processes // Communs. Math. Phys. 37, № 2. - 1974. - P. 141-160.

149. Higuchi Yasunari. Remarks on the timiting Gibbs states on a (1+3) tree // Publ. Res. Inst.Math.Sci. 13, №2. - 1977. - P.335-348.

150. Moussouris John. Gibbs and Markov random systems with constraints // J.Statist. Phys. 10, № 1.- 1974.- P.l 1-33.

151. Preston Christopher J. Gibbs states on countable sets . London. Cambridge Univ. Press.- 1974.-P. 128.

152. Preston C. Random fields // Lect Notes Math. v. 534. 1976. - P.200 .

153. Spitzer Frank. Markov random fields and Gibbs ensembles // Amer. Math. Mon. 78,2.-1971.-P. 142-154. 165.Sullivan W.G. Potentials for Almost Markovian Random Fields // Commun. Math. Phys. 33, №1. - 1973. - P.61-74.

154. Wagner E.G. On connecting modules together uniformly to form a modular computer // IEEE Trans, on EC. V.EC-15, № 6.- 1965.-P. 863-972.

155. Воробьёв B.A. Критическое протекание в плоских решетках / В.А. Воробьёв, Н.В.Лаходынова// Специализированные вычислительные системы, методы и средства обработки информации: Тематический сборник научных трудов. М.: Изд-воМАИ, 1987.-С. 13-15.

156. Воробьёв В.А. Пределы надёжности однородных вычислительных систем / В.А. Воробьёв, Н.В.Лаходынова // Экспертные системы и распознавание образов: Вычислительные системы, 126). Новосибирск, Институт математики СО АН СССР, 1988.-С. 122-149.

157. Воробьёв В.А. Пределы надежности однородных структур / В.А. Воробьёв, Н.В.Лаходынова // Известия АН СССР: Техническая кибернетика, № 3. 1989. -С. 110-114.

158. Воробьёв В.А. Пороги просачивания и надежность однородных структур / , В.А. Воробьёв, Н.В.Лаходынова // Методы и средства проектирования специализированных вычислительных систем. Ленинск: Изд-во МО, 1989.

159. Воробьев В.А. Отказоустойчивость однородных процессорных матриц / В.А. Воробьев, Н. В. Лаходынова, Н.Л. Еремина. Томск: Томский государственный архитектурно-строительный университет, 2002. - 154 с.

160. Лаходынова Н. В. Исследование алгоритмов реконфигурации процессорной матрицы и задача просачивания // Моделирование неравновесных систем, материалы III Всероссийского семинара, Красноярск, 20-22 октября 2000 года. - С. 145-146.

161. Лаходынова Н. В. Задача просачивания для моделирования финансовых потоков / Н. В. Лаходынова, Т.В. Воробьева // Моделирование неравновесных систем, материалы IV Всероссийского семинара, Красноярск, 12-14 октября 2001 года. - С. 23.

162. Лаходынова Н. В. Просачивание в однородных структурах с согласием // Материалы II Всесибирского конгресса женщин-математиков, Красноярск, 15-20 января 2002 года.

163. Фон Нейман Дж. Вероятностная логика и синтез надёжных организмов из ненадёжных компонент // Автоматы. М.: ИЛ, 1956.

164. Мур Е. Надёжные схемы из ненадёжных реле / Е.Мур, К.Шеннон // Работы по теории информации и кибернетике. М.: ИЛ, 1963 - С. 114-153.

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

166. ТИИЭР, Т.74, № 5 Отказоустойчивость СБИС . -1986.

167. Авидженис А. Гарантоспособные вычисления: от идей до реализации в проектах / А.Авидженис, К.К.Лапри -ТИИЭР, Т.74, № 5. -1986. С. 8-21.

168. Погребинский С.Б. Проектирование и надёжность многопроцессорных ЭВМ / С.Б.Погребинский, В.П.Стрельников — М.: Радио и связь, 1988. — 166 с.

169. Serlin О. Fault tolerant computers // Data Process., V.25, №10. 1983. -P. 28-31.

170. Ebihara Y. at al. Fault diagnosis and automatic reconfiguration for a ring subsystem // Comput. Networks and ISDN Syst., V.10, № 2. 1986. - P. 97-109.

171. Додонов А.Г. Введение в теорию живучести вычислительных систем / А.Г.Додонов, М.Г.Кузнецова, Е.С.Горбачик Киев: Наукова думка, 1990. -182 с.

172. Jeng М. Desing and analysis of dynamic redundancy networks / M.Jeng, H.J. Siegel // IEEE Trans. Comput., V.C-37, № 9. 1988. - P. 1019-1029.

173. Adams G.B. The extra stage cube: A fault-tolerant interconnection network for supersystems / G.B.Adams, H.J.Siegel // IEEE Trans. Comput., V.C-31, №5. 1982. . p. 443-454.

174. Adams G.B. Asurvey and comparison of fault-tolerant multistage interconnection networks / G.B.Adams, D.P.Agrawal, H.J.Siegel // Computer, V.20, № 6. -1987. P. 1427.

175. Kruskal C.P. The performance of multistage interconnection networks for multiprocessors / C.P.Kruskal, M.Snir // IEEE Trans. Comput., V.C-32, №12. -1983. -P: 1091-1098.

176. Horowitz E. The Binary Tree as an Interconnection Network: Application to Multiprocessor System and VLSI / E.Horowitz, A.Zorat // IEEE Trans. Comput., V.C-30, № 4. 1981. - P. 247-253.

177. Hassan A.S.M. A Fault-Tolerant Modular Architecture for Binary Trees / A.S.M.Hassan, V.K.Agarwal // IEEE Trans. Comput., V.C-35, № 4. P. 356-361.

178. Grassi V. Yield evaluation of VLSI reconfigurable binari tree architectures // FTDS-13 (13-th Int. Conf. on fault-tolerant systems and diagnostics), Varna, Bulgaria, june 20-22, 1990.-P. 106-119.

179. Yingquan Z. A Kind of Multistage Interconnection Networks with Multiple Paths / Z.Yingquan, M. Yinghua // J. of computer science and technology, V.ll, № 4. 1996.- P. 395-404.

180. Seban R.R. FTN (fault-tolerant networks) Topology and Protocols // J. of Parallel and Distributed Computing, V.l 1, № 1.- 1991. -P. 51-62.

181. Raghavendra O.S. Fault-Tolerant multiprocessors with reduandant-path interconnection networks / O.S.Raghavendra, A.Varma // IEEE Trans. Comput., V.35, № 4. 1986. -P. 307-316.

182. Choi Y-H. A fault-tolerant FFT processor / Y-H.Choi, M.Malek // IEEE Trans. Comput., V.37, № 5. -1988. P. 617-621.

183. Воробьёв В.А. О структурной живучести однородных вычислительных систем / В.А.Воробьёв, В.В.Корнеев // Тезисы докладов II Всесоюзной конференции "Алгоритмические методы проектирования цифровых систем". Ленинград, 1972.

184. Pradhan D.K. A fault-tolerant communication architecture for distributed systems / D.K.Pradhan, S.M. Reddy// IEEE Trans. Comput., V.C-31.-1982 . P. 863-870.

185. Pradhan D.K.,. Communication Structures in Fault-Tolerant Distributed Systems / D.K.Pradhan, F.J Meyer // FTDS-10 (10-th Int. Conf. on fault-tolerant systems and diagnostics). Varna, 1987. - P. 193-202.

186. Pradhan D.K. The De Bruijn Multiprocessor Network: A versative parallel processing and sorting networks / D.K.Pradhan, Samatham M. // IEEE Trans. Comput., V.C-39, №4.- 1989.-P. 567-581.

187. Pradhan D.K. Fault-tolerant VLSI Architectures Based on De Bruijn Graphs (or Old Graphs / New Tricks) // FTDS-13 (13-th Int. Conf. on fault-tolerant systems and diagnostics,Varna, Bulgaria, june 20-22, 1990).-P. 9-27.

188. Bruck J. Fault-Tolerant de Bruijn and Shuffle-Exchange Networks / J.Bruck, R.Cypher // IEEE Trans, on Parallel and Distributed Systems, V.5, № 5. 1994. - P. 548-553.

189. Alam M.S. Routing in Modular Fault-Tolerant Multiprocessor System / M.S.Alam, R.G.Melhem // IEEE Trans, on Parallel and Distributed Systems, V.6, №11. 1995.- P. 1206-1220.

190. Tzeng N.-F. A Pairwise Substitutional Fault-Tolerant Technique for Cube-Connected Cycles Architecture / N.-F.Tzeng, P. -J.Chang // IEEE Trans, on Parallel and Distributed Systems, V.5, №4.- 1994. P. 433-438.

191. Yang C.S. A Recofigurable Modular Fault-Tolerant Hypercube Architecture / C.S.Yang, L.P.Zu, Y.N.Wu // IEEE Trans, on Parallel and Distributed Systems, V.5, № 10.- 1994.-P. 1018-1032.

192. Vinnakota B. Design of Algoritm-Based Fault-Tolerant Multiprocessor Systems for Concurrent Error Detection and Fault Diagnosis / B.Vinnakota, N.K.Jha // IEEE Trans, on Parallel and Distributed Systems, V.5, №10. 1994. - P. 1099-1106.

193. Ramanathan P. Resource Placement with Multiple Adjacenty Constraits in k-ary n-Cubes / P.Ramanathan, S.Chalasani // IEEE Trans, on Parallel and Distributed Systems, V.6,№ 5.- 1995.-P.511-519.

194. Trobec R. A fault-tolerant routing in parallel systems // FTDS-10 (10-th Int. Conf. on fault-tolerant systems and diagnostics). Varna, 1987. -P. 95-100.

195. Lan Y. An Adaptive Fault-Tolerant Routing Algorithm for Hypercube Multiprocessors // IEEE Trans, on Parallel and Distributed Systems, V. 6, № 11. 1995. - P. 1147-1152.

196. Pifarre G.D. Adaptive Deedlock- and Livelock-Free Routing in the Hypercube Network / G.D.Pifarre, L.Gravano, G.Denicolay, J.L.Sanz // IEEE Trans, on Parallel and Distributed Systems, V.5, № 11. 1994. - P. 1121-1139.

197. Duato J. A Theory of Deedlock-Free Adaptive Multicast Routing in Wormhole Networks // IEEE Trans, on Parallel and Distributed Systems, V. 6, № 9. 1995. - P. 976987.

198. Shin C.J. Adding Multiple- Fault Tolerance to Generalizad Cube Networks / C.J.Shin, K.E.Batcher // IEEE Trans, on Parallel and Distributed Systems, V.5, № 8. 1994. -P. 785-792.

199. Граф Ш.:. Схемы поиска неисправностей / Ш.Граф, М.Гессель /перевод с немецкого под редакцией Д.А. Поспелова/. М.: Энергоатомиздат, 1989. — 145 с.

200. Согомонян Е.С. Самопроверяемые устройства и отказоустойчивые системы /

201. E.С.Согомонян, Е.В.Слабаков М.: Радио и связь, 1989. - 208 с.

202. Матросова А.Ю. Алгоритмические методы синтеза тестов. — Томск: Из-во ТГУ, 1990. 208 с.

203. Preparata F.P. Оп connection assignement problem of diagnosable systems /

204. F.P.Preparata, G.Metze, R.J.Chien // IEEE Trans. El. Comput.,V. EC-16, № 12, 1967.- P.848-854.

205. Holt C.S. Self-diagnosis in distributed systems / C.S.Holt, J.E. Smith // IEEE Trans. Comput., V.34, №1. 1985. - P. 19-32.

206. Usluel A.K. Concurent error detection and reconfiguration in sistolic arrays / A.K.Usluel, P. K.Lala // FTDS-10 (10-th Int. Conf. on fault-tolerant systems and diagnostics). Varna, 1987. - P. 101-112.

207. Sapiecha K. Fault tolerant WSI architecture with random spare part distribution // FTDS-10 (10-th Int. Conf. on fault-tolerant systems and diagnostics). Varna, 1987.- P. 81-94.

208. Димитриев Ю.К. Самодиагностика модульных вычислительных систем. Новосибирск: Наука, 1993.

209. Димитриев Ю.К. Анализ самодиагностических свойств структур распределённых живучих вычислительных систем // Автометрия, №5.-1996 С. 71-84.

210. Hammersley J.M. Percolation processes lower bounds for critical probability // Ann. Math. Statist., V.28. 1957. - P. 790-795.

211. Mc Leod R.D. Percolation and Anomalous Transport as Tools in Analyzing Parallel Processing Interconnect Network / R.D.Mc Leod, JJ.Schellenberg // J. of Parallel and Distributed Computing, V.8, № 4. 1990. - P. 376-387.

212. B.A. Воробьев B.A. Процессорная матрица с перестраиваемой структурой и перестраиваемым резервом /В.А. Воробьев, Н. В. Лаходынова // Автометрия, № 5.- 1994. С. 90-98.

213. Vorobyev V. A. Reconfigurable processing arrays with a rearrangeable redundancy /V.A. Vorobyev, N.V. Lakhodinova // Optoelectronics, Instrumentation and Data Processing, № 5. 1994. -P. 90-98.

214. Воробьёв В.А. Программная реализация реконфигурации отказоустойчивой процессорной матрицы / В.А.Воробьёв, Н.Л.Ерёмина // Автометрия, № 2: Перспективные вычислительные системы. 1996. - С. 111-121.

215. Воробьёв В.А. Анализ алгоритмов перестройки структуры процессорной матрицы / В.А.Воробьёв, Н.В.Лаходынова, Н.Л.Ерёмина // Автометрия, № 3 1996. -С. 69-77.

216. Vorobyev V.A. Analysis of the algorithms of a processor array structure reconfiguration /V.A. Vorobyev , N.V. Lakhodinova // Optoelectronics, Instrumentation and Data Processing, № 3. 1996. -P. 69-77.

217. Ерёмина Н.Л. Моделирование отказоустойчивой процессорной матрицы. // Новые информационные технологии в исследовании дискретных структур: Доклады всероссийской конференции. Екатеринбург: УрО РАН, 1996. - С. 112-116.

218. Воробьёв В.А. Алгоритм реконфигурации процессорной матрицы на основе сигналов согласия / В.А. Воробьёв, Н.В.Лаходынова // Международная конференция "Автоматизация проектирования дискретных систем": Тезисы докладов. Минск, 1995, Т. 1.-С. 13.

219. Воробьёв В.А. Реконфигурация отказоустойчивой процессорной матрицы на основе сигналов согласия /В.А. Воробьёв, Н.В.Лаходынова // Автометрия, № 6. 1997. -С. 108-113.

220. Vorobyev V.A. Reconfiguration of fault-tolerant processor arrays on the basis of agreement signals / V.A. Vorobyev, N.V. Lakhodinova, // Optoelectronics, Instrumentation and Data Processing, № 6. 1997. -P. 108-113.

221. Артамонов Г.Т. Об одном способе построения однородных эквицентральных сетей // Техническая кибернетика, № 6. -1970.

222. Шум JI.C. О функциональной организации вычислительных систем // Вычислительные системы. -Новосибирск: Институт математики СО АН СССР, 1970. -Вып.39. -С. 81-88.

223. Воробьёв В.А. Организация путевых процедур в диофантовых структурах однородных вычислительных систем / В.А.Воробьёв, Э.А.Монахова // XXIV областная научно-техническая конференция, посвящённая Дню Радио: Тезисы докладов. -Новосибирск, 1981. С. 70-71.

224. Монахова Э.А. Алгоритмы межмашинных обменов и реконфигурации межмашинных графов в вычислительной системе с программируемой структурой // Вычислительные системы, Вып 94, Новосибирск: Институт математики СОАН СССР. -1982,-С. 81-102.

225. Воробьёв В.А. Относительная адресация элементов циклического графа. В кн: Однородные вычислительные системы из микро-ЭВМ: Вычислительные системы, 97. -Новосибирск: Институт математики СО АН СССР. -1983. С. 87-103.

226. Upfal Е. Tolerating a Linear Number of Faults in Networks of Baunded Degree // Information and Computation, V.115. 1994. - P. 312-320.

227. Dwork D. et al. Fault tolerance in networks of bounded degree // SLAM J. Computing, V.17.- 1988.-P. 975-988.

228. Dolev D. et al. An efficient algorithm for Byzantine agreement without authentication // Ifjrm. and Control, V.52, № 3. 1992 . - P. 256-274.

229. Harris Т.Е. A lower bound for the critical probability in a certain percolation process // Proceeding of Cambridge Philosofical Society, V.56. I960 - P. 13- 20.

230. Боровков A.A. Теория вероятностей. — M.: Наука, 1976. 351 с.

231. Берж К. Теория графов и её применения. М.: ИЛ, 1962. 247.3акревский А.Д. Алгоритмы синтеза дискретных автоматов. - М.: Наука, 1974. 248.Сами М. Перестраиваемые архитектуры матричных процессорных СБИС. /

232. М.Сами, Р.Стефанелли -ТИИЭР, Т.74, № 5. 1986. - С. 107-118.

233. Мангир Т.Э. Источники отказов и повышение выхода годных СБИС // ТИИЭР, Т.72. 1984. № 7.- С. 37-56.

234. Секен К.Х. Управление сложностью СБИС: Современное состояние и перспективы//ТИИЭР, Т.71,№ 1.- 1983.-С. 184-211.

235. Корен И. Избыточность как средство повышения надёжности и выхода годных мультипроцессорных систем с интеграцией на уровне кристаллов и пластин / И.Корен, Д.Прадхан // ТИИЭР, Т.74, № 5. 1986. - С. 93-106.

236. Мур У.З. Обзор методов повышения отказоустойчивости, повышающих выход годных интегральных схем // ТИИЭР, Т.74, № 5. 1986. - С. 76-92.

237. Харченко B.C. Методы повышения отказоустойчивости СБИС бортовых цифровых вычислительных комплексов / В.С.Харченко , В.Г.Литвиненко, В.А.Мельников // Зарубежная радиоэлектроника, № 12. 1990. - С. 56-69.

238. Stapper С.Н. Large-area fault clusters and fault tolerance in VLSI circuits: a review // IBM J. Res. Develop., V.33, № 2. 1989. - P. 162-173.

239. Stapper C.H. Small-area fault clusters and fault tolerance in VLSI circuits // IBM J. Res. Develop., V.33, № 2. 1989. - P. 174-177.

240. Hosseini S.H. On fault-tolerant structure, distributed fault-diagnosis, reconfiguration and recovery ofthe array processors // IEEE Trans. Comput., V.38, № 7. 1989. - P. 932942.

241. Singh A.D. IEEE Trans. Comput., V.37, № 11. -1988.

242. Lam C.W.H. A study of two approaches for reconfiguring fault-tolerant systolic arrays / C.W.H.Lam, H.F.Li // IEEE Trans. Comput., V.38, № 6. 1989. - P. 833-844.

243. Мямлин A.H. Об одном методе повышения надёжности матричных многопроцессорных систем / А.Н.Мямлин, Л.А.Поздняков, Е.И.Котов, И.Б.Задыхайло // Электронная вычислительная техника: Сб. научных трудов. — М., 1988. -Вып.2 . - С. 2637.

244. Kuo S.-Y. Reconfigurable Cube-Connected Cycles Architectures / S.-Y.Kuo, W.K.Fuchs // J. of Parallel and Distributed Computing, V.9, № 1. 1990.

245. Dutt S. On designing and reconfiguring k-fault-tolerant tree architecture / S.Dutt, J.P.Hays // IEEE Trans. Comput., V.39, № 4. 1990. - P. 490-503.

246. Chan M.Y. Distributed Fault-Tolerant Embeddings of Rings in Hypercubes / M.Y.Chan, S.-J Lee.// J. of Parallel and Distributed Computing, V.ll, № 1.-1991. -P. 63-71.

247. Lin R. Reconfigurable Buses with Shift Switching: Concepts and Applications / R.Lin, S.Olarin // IEEE Trans, on Parallel and Distributed Systems, V.6, №1. 1995. - P. 93102.

248. ГалушкинА. Оценка алгоритмов реконфигурации структуры вычислительных систем с МИМД- архитектурой / А.Н.Галушкин, Л.В.Грачёв, М.М.Толстых, В.А.Точёнов // Кибернетика, №2. -1990.

249. Миренков Н.Н. Алгоритмы распознавания подсистем заданных структур в ОВС / Н.Н.Миренков, С.Б.Фишерман // Теория однородных вычислительных систем: Вычислительные системы. 63. Новосибирск: Институт математики СО АН СССР. -1975.-С. 44-53.

250. ChenM.-S. Processor allocation in an N-cube multiprocessor using Gray codes / M.S.Chen, K.G.Shin// IEEE Trans. Comput., V.36, № 12.-1981.- P. 1396-1407.

251. Воробьёв B.A. Вложение КАИС-структур в физическое пространство / В.А.Воробьёв, А.Д.Саенко // Методы и средства проектирования специализированных вычислительных систем. Ленинск, Изд-во МО, 1989.

252. Scott S.L. The Impact of Pipelined Channels on k-ary n-Cube Networks / S.L.Scott, J.K.Goodman // IEEE Trans, on Parallel and Distributed Systems, V.5, №1.-1994.- P. 216.

253. ChenY.-L. A Fault-Tolerant Distributed Subcube Management Scheme for Hypercub Multicomputer Systems / Y.-L.Chen, J.-C.Lin // IEEE Trans, on Parallel and Distributed Systems, V.6, №7. -1995. -P. 766-772.

254. Еремина Н.Л. Реконфигурация отказоустойчивой неразрезной процессорной матрицы: Дис. канд. техн. наук. /ТГУ/.- Томск, 2000. -128 с. -рук.

255. Еремина H.JI. Алгоритм диагонального захвата для реконфигурации процессорной матрицы и его эффективность // Вестник Томского государственного педагогического университета. 1999. № 7.-С. 42-47

256. Лаходынова Н. В. Анализ алгоритмов реконфигурации структуры процессорной матрицы на основе сигналов согласия // Радиоэлектроника. Информатика. Управление. № 2, 2001. С. 98-102.

257. Лаходынова Н.В. Об одном методе обеспечения отказоустойчивости процессорных матриц // Автометрия, № 6. 2002.

258. Lakchodinova N.V. About one method of ensuring of fault tolerance of without-cut processor arrays VLCI. // Optoelectronics, Instrumentation and Data Processing, № 6. -2002.