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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТОМСКИМ ГОСУДАРСТВЕННЫЙ РГБ ОД ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

1'» ^г г::)

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

Ерёмина Наталия Леонидовна

РЕКОНФИГУРАЦИЯ ОТКАЗОУСТОЙЧИВОЙ НЕРАЗРЕЗНОЙ ПРОЦЕССОРНОЙ МАТРИЦЫ

05.13.01 - Управление в технических системах

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

Томск - 2000

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

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

доктор технических наук Воробьев В.А.

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

доктор технических наук Бандман О.Л. доктор технических наук Матросова А.Ю.

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

Объединенный институт информатики Сибирского отделения Российской Академии наук (г. Новосибирск)

Защита состоится « июня 2000 г. в час. ВО мин на заседании диссертационного совета Д 063.53.03 при Томском государственном университете по присуждению ученой степени кандидата технических наук по адресу: 634050, г. Томск, пр. Ленина, 36.

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

Автореферат разослан «мая 2000 г.

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

доцент

Тривоженко Б.Е.

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

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

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

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

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

Практическая значимость работы.

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

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

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

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

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

2. Алгоритм адресации для перестройки по диагональному захвату.

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

4. Программная система ЛОГИКА, обеспечивающая реализацию метода программной реконфигурации неразрезной процессорной матрицы, разработку и моделирование микропрограммных клеточных автоматов для реконфигурации матрицы и иных приложений.

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

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

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

Личный вклад автора.

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

Апробация работы.

Основные результаты диссертации докладывались и обсуждались на Всероссийской конференции "Новые информационные технологии в исследовании дискретных структур" (Екатеринбург, 1996), на региональной научно-технической конференции молодых специалистов "Радиотехнические и информационные системы и устройства" (Томск, 1994), на Международном конгрессе студентов, аспирантов и молодых ученых (Томск, 1999), на семинарах кафедр математической логики и проектирования (радиофизический факультет) и программирования (факультет прикладной математики и кибернетики) Томского государственного университета (Томск, 1994; 2000).

Публикации.

Результаты исследований по диссертационной работе опубликованы в виде 4 статей в научных журналах, 2 докладов, 2 тезисов выступлений на конференциях (всего 8 печатных работ).

Струюура и объем работы.

Диссертация состоит из введения, трех глав, заключения и библиографии. Она изложена на 128 страницах, содержит 24 иллюстрации, 7 таблиц. Библиографический список литературы цитированной литературы включает 76 наименований. Диссертация имеет 10 приложений на 72 страницах.

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

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

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

Объект исследования - процессорная матрица, представляющая собой прямоугольный массив процессоров, расположенных на одной пластине СБИС. Введем следующие обозначения: I-число строк в матрице, ./ - число столбцов. Процессор, находящийся в строке 0<г'</-1, и в столбце ], 0</:^/-1 имеет физические координаты (х,}), отражающие его положение в матрице. Каждый процессор (за исключением находящихся на краю матрицы) соседствует с четырьмя процессорами, имеющими физические координаты (М,_/), (г,7-1), (1+1,7), (',7+1) (рис. 1). С точки зрения программирования процессорная матрица представляет собой квадратную решетку размера Ш, в узлах которой расположены процессорные элементы. Будем считать систему работоспособной в том случае, если она сохраняет исходную структуру квадратной решетки.

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

}

Предполагается, что процессорная матрица имеет средства самотестирования и для каждого процессорного элемента с физическими координатами (1,7) известно значение двоичного сигнала неисправности е (г,/). Множество {е (/,7) / 1<г</-1, 1 </¿7-1} образует синдром неисправности процессорной матрицы и служит исходной информацией для ее коррекции. Если в вычислительной системе есть отказы, происходит перестройка процессорной матрицы: избыточные связи исправных элементов активизируются, так, чтобы система сохраняла исходную структуру; у неисправных элементов, вырабатывающих сигнал е (/,/) = 1, наоборот, все связи блокируются, в связи с чем они не могут участвовать в вычислениях и, фактически, исключаются из процессорной матрицы.

Рис. 1. Процессорная матрица

Рис. 2. Структура процессорного элемента

при схемной реализации реконфигурации процессорной матрицы.

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

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

Кроме физических координат (/, у) каждый процессор имеет логические координаты (Г,/). Первоначально логические координаты совпадают с физическими. В процессе реконфигурации логи-

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

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

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

Процессорная матрица просматривается построчно снизу вверх, начиная от строки с наибольшим номером I =/-1 и заканчивая второй сверху строкой с номером 1 = 1. В каждой строке процесс реконфигурации идет слева направо, от элемента с наименьшим номером столбца у = 0 до его максимального номера}- J-\.

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

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

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

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

Итак, для каждого отказа либо захваченного ранее элемента (к, I), 0<к<1Л, 0</5/-1, выполняется следующая процедура.

1. ЕСЛИ (к, I) - самый правый отказ в строке и в строке к не было горизонтального отказа,

ТО (к, 0 считается горизонтальным отказом и нейтрализуется перестройкой вправо; переход к п. 5;

ИНАЧЕ переход к п. 2.

2. ЕСЛИ элемент (к-\, Г) исправен и не захвачен по диагонали элементом (к, I-1),

ТО происходит прямой захват; переход к п. 5;

ИНАЧЕ переход к п. 3.

3. ЕСЛИ отказ (к, I) не принадлежит резервному столбцу, т.е. МЛ, и элемент {к-1, /+1) исправен,

ТО происходит диагональный захват; переход к п. 5;

ИНАЧЕ переход к п. 4;

4. ЕСЛИ в строке к не было горизонтального отказа,

ТО {к, I) считается горизонтальным отказом и нейтрализуется перестройкой вправо; переход к п. 5;

ИНАЧЕ возникает ситуация фатального отказа и перестройка матрицы невозможна (аварийное завершение процедуры);

5. КОНЕЦ процедуры.

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

1) если в некоторой строке к (не резервной) существуют неисправные либо захваченные процессорные элементы с номерами (к, т) и (к, п), причем неисправны также элементы с номерами (к-1, т), (кЛ, от+1), {к, л+1), а элемент (кЛ, и) неисправен либо захвачен;

2) если в некоторой строке к (не резервной) существуют неисправные либо захваченные процессорные элементы с номерами (к, т) и {к, /-1), причем неисправны также элементы с номерами (¿-1, т), (к-1, т+1), а элемент (к-1,7-1) неисправен либо захвачен.

□

1.1 -1

□

2.1

2.2

3.1

2.3 -1

1.3 3"

Г 3.2

3.3

4.1

4.2 — ГТ

ж

4.3

т

□

1.4

Ц 2.4 4-

3.4

4.4

I___1

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

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

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

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

ГГ(1,Л = ё О",/И) & 2 (1+1,7+1) & й (/+1,7)& г/((,7+1) V а (/,/); рг (¿,7) = гГ(и) & [е 0',7) V ^ (¿+1,7) V й (/+1,7-1)];

8Г0.Л = а 0,У-1) & [Н г&Л = [е (У) Vг 0+1,7) Vй0+1,7-1)] & Ь (1,7) & &[рг (},Г>чрг(1,Я&&{1,]-\)]& ё 0-1,7) & ^ 0,7-1); 4 (и) = [е Л V 2 (¡+1,Л чс! (¡+1,^1)] & а 0,7) & Ь (/,7) & &[рг 0,7)^^0,7) 7-1)] & 2 (1,7) & ё 0-1,7+1); А ('",7") = 0,7-1) & [е (/,7) V г 0+1,7) V <10+1,7-1)] & Ъ (/,7) &

&[рг(¿,7> 2 0,7) & 0,м, Е 0,7) = {£ 0,7-1) V [е (у) V г (ИЛ,]) V й 0+1,7-1)] & Ъ 0,7) & & 2 (1,7) & (¡.у) & Л (1,7-)} & а (/,7-1) ;

где:

а (/,7) - признак принадлежности резервному столбцу; Ъ (¡,7) - признак принадлежности резервной строке; е 0.7) ~ сигнал отказа; г/(г,/) — сигнал отсутствия отказа справа; г (/,7) - признак прямого захвата элементом (1,7); й - признак диагонального захвата элементом (1,7); Рг (/,7) _ признак самого правого отказа в строке;

(/,7) - сигнал наличия в строке горизонтального отказа; А (/,7) - сигнал горизонтального отказа; Е (1,7") - сигнал фатального отказа.

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

На основе сигналов перестройки можно вычислить сигналы коммутаций для процессорных элементов. Каждый из этих сигналов соответствует одной из возможных вертикальных или горизонтальных связей процессора. Если связь активна, то соответствующий сигнал коммутации принимает значение 1, в противном случае сигнал равен 0.

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

Алгоритм перенумерации служит для вычисления новых логических координат (¿',/)> отражающих изменение места процессорного элемента (/,_/') в структуре процессорной матрицы после реконфигурации.

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

Для вычисления логических координат процессоров предлагаются следующие формулы:

(¿,Л = {I- (и)_+ [2 (¿+1 V а (1+1, >1)]} х х{ё {!,])& [а (и)&Ь (/,./) V2 0+1,7) V

V«/(/+1,7-1)]};

Г = V (и) + 1 - [ г О+М & А (М,Я) & ^(¿,7) V V г(/+1,7) &яД/+1,7) V ¿(/+1,7-1) &^ (/+1 у-1)] - й(/+1,7-1)} * х{ё (!,])& [а (/,7)&Ь (1,7) VО',/) Vг(1+1,7) V V«/0+1,7-1)]}.

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

двоичные значения 0 и 1 преобразуются в целые числа 0 и 1 соответственно; результат вычислений всегда является целым неотрицательным числом.

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

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

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

Отказоустойчивость процессорной матрицы характеризуется вероятностью сохранения работоспособности /'(/,У,р), где /количество строк в процессорной матрице, У - количество столбцов, р - вероятность исправности одного процессорного элемента. Сравнительный анализ алгоритмов реконфигурации был проведен методом второй производной. Для матриц небольших размеров вид функции Р (/, У,р) может быть получен аналитически:

1=0

где коэффициент а, равен количеству различных конфигураций I отказов в процессорной матрице. Эти коэффициенты определяются полным перебором всех возможных конфигураций отказов и подсчетом числа тех из них, которые позволяют получить квадратную решетку из оставшихся исправными процессоров. Абсцисса точки перегиба кривой функции Р(/, У,/>), 0<р<1 задает критическое значение вероятности р=рп исправности процессорного элемента. Если р<рп, значение функции Р(1, У, р) резко падает до нуля при уменьшении р, при р>рп оно стремится к единице. Значение рп является корнем уравнения Р" (/, У, р) = 0. Следует подчеркнуть, что полученный результат носит аналитический, а не статистический характер.

Были исследованы структуры, содержащие до 30 элементов. Для каждой из них и каждого алгоритма реконфигурации получен аналитический вид функций Р (/, У, р), построены графики Р (/, У, р) и найдено значение критической вероятности рп.

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

Рис. 4. Вероятность Р(5,5,р) сохранения работоспособности процессорной матрицы 5x5 при различных способах реконфигурации:

1, 2,3,4 - алгоритмы диагонального захвата, свободного захвата, прямой перестройки и ограниченного захвата, соответственно, с резервной строкой и столбцом; 5 - алгоритмы захвата, в которых резервировался только столбец.

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

Третья глава посвящена микропрограммному управлению реконфигурацией процессорной матрицы на СБИС.

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

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

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

Сопоставим всем сигналам булевы переменные. Введем следующие обозначения: Е (г,/) - множество сигналов перестройки, АТ (;',/) - множество сигналов управления коммутатором, Z(i,j) - множество сигналов внутреннего состояния автомата (г, у). Пусть 11 (г, у) обозначает множество всех соседей автомата (г,у), включая сам автомат (7,у), а сГ (г,у) - множество соседей, исключая автомат (г,у), т.е. с?' (г,у) = с1 (¿,у) \ (г,у). Соответственно символы ¿Е (г,у), с1К{иу), ¿2(1,]), (ТЕ (г,у) следует понимать как множество сигналов в указанной окрестности. Тогда описание элементарного автомата будет выглядеть следующим образом:

где Р2 - системы булевых функций (рис. 5).

Е(к. I)

а (И) Ь(1,Л е(1.Й

^К(и)

Рис. 5. Схема элементарного автомата.

Обратим внимание также на тот факт, что множество переменных 2 (г,у) является только входным. В общем случае некоторые элементы этого множества могут быть функциями аргументов йЕ (г,у), ¿/^ (/,_/). Отсутствие этой зависимости означает, что блок управления (г,у) представляет собой комбинационную схему.

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

Булевы переменные множества К управляют коммутаторами, причем каждая переменная у1 из К включает одну из связей между процессорными элементами. В каждом процессорном элементе должны быть включены одна вертикальная, одна горизонтальная связи и не более чем одна перемычка, вертикальная либо горизонтальная. Следовательно, для каждого элемента (/,у) не более трех элементов множества К (г,у) принимают единичное значение. Множество К (г,у) можно рассматривать как микрокоманду для коммутационного окружения процессора 0',у) а вся система К есть параллельная микрокоманда реконфигурации процессорной матрицы.

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

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

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

Рис. 6. Структура матричной ЭВМ.

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

Массовая память в простейшем случае реализуется средствами ПЭВМ.

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

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

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

Все описанные устройства присутствуют и для систем класса МКМД.

При переходе к программной реализации реконфигурации структура ячейки процессорной матрицы также изменяется (рис. 7).

Для реализации метода программной реконфигурации структуры разработаны:

1) язык ЛОГИКА описания клеточных автоматов;

2) программа трансляции с языка ЛОГИКА в язык троичных матриц, удобный для дальнейшей обработки;

3) программа-интерпретатор, вычисляющая функции микропрограммного клеточного автомата по его описанию;

4) средства визуализации состояния процессорной матрицы на дисплее.

Язык ЛОГИКА предназначен для описания параллельного микропрограммного клеточного автомата и представляет собой язык алгебры логики с некоторыми особенностями.

Полное описание клеточного автомата нерационально, поскольку число элементов в матрице велико и не определено заранее. Однако, в силу однородности структуры, достаточно описать функции одной клетки и сигналы, поступающие на входы граничных элементов. В языке ЛОГИКА эта возможность обеспечивается тем, что каждая переменная имеет физические координаты (!,_/). Над ними можно производить операции типа (/±с1,у±с2), где сь с2 -константы. Это позволяет записывать булевы функции, зависящие от состояния самого элемента и его окрестности. Таким образом, в машинной памяти хранятся функции, описывающие только одну клетку, но характеризующие каждый элемент матрицы, что ведет к значительному сокращению затрат памяти. При этом файл с записью алгоритма реконфигурации на языке ЛОГИКА не требуется изменять каждый раз при изменении размеров матрицы. Кроме того, такое представление частично упорядочивает систему функций, облегчая тем самым процесс их вычисления. Язык ЛОГИКА обеспечивает произвольный шаблон соседства, произвольное число состояний элементарного автомата, произвольное число переменных и при этом не требует для своей реализации специализированной ЭВМ.

Для описания функций граничных элементов матрицы в языке ЛОГИКА предусмотрена возможность в качестве координат

использовать константы и символ *, обозначающий максимально возможный номер строки/столбца.

Булева функция на языке ЛОГИКА задается произвольной скобочной формой. В ней допустимы логические операции инверсии конъюнкции &, дизъюнкции V и др. Кроме того, для вычисления логических координат используются арифметические операции: сложение +, вычитание умножение * и деление /. Операция присваивания значения в языке ЛОГИКА обозначается двоеточием «:».

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

Программа-транслятор преобразует описание автомата на языке ЛОГИКА в ДНФ логических функций. Интерпретатор сканирует матрицу по координатам (г, у) в прямом и обратном направлениях и вычисляет значения всех функций, используя специальную троичную логику с множеством значений {0,1,~}. Функции, вычисленные в процессе сканирования, имеют значения {0,1}, а невычисленные - {~}. Сканирование продолжается до тех пор, пока не будут вычислены все функции системы, либо пока не будет установлено, что невозможно более вычислить значение ни одной функции. Сначала программа находит значение сигналов перестройки, затем сигналов коммутации, после чего по инверсной записи вычисляет значение новых логических индексов (Г,у") для каждого процессорного элемента. Выбор режима интерпретации при вычислении функций обеспечивает простоту имитации и позволяет варьировать размеры матрицы без ретрансляции системы функций.

Резигры мзтрмцы—

Стрп.

г

: -Отказы : ■■-

02Т]. '

40 —1

1 з_I

52. .

53 * '

. Р л] Строк«'

15-3 ОолЗец

■ Дабааитъ -с [

•грезе ра~ ' Строек -

'гз

>- -г-- Добавить,

" Готово-3.

Рис. 8.

Диалоговое окно программной системы ЛОГИКА.

Рис. 9. Окно выдачи результатов программной системы ЛОГИКА.

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

Описанная система имеет следующее применение:

1) вычисление функций реконфигурации матрицы в управляющей ЭВМ;

2) отладка новых алгоритмов реконфигурации структуры;

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

С помощью программной системы ЛОГИКА описаны и отлажены четыре алгоритма реконфигурации процессорной матрицы.

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

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

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

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

3. Предлагается программная система ЛОГИКА для реконфигурации неразрезной процессорной матрицы.

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

1. Ерёмина Н.Л., Воробьев В.А. Отказоустойчивая матрица для обработки изображений П Региональная научно-техническая конференция «Радиотехнические и информационные системы и устройства»: Тез. докл. Томск, 1994. С. 7-9.

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

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

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

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

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

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

8. Ерёмина Н.Л. Процессорная матрица с реконфигурацией по алгоритму диагонального захвата // Международн. конгресс «Наука, образование, культура на рубеже тысячелетий»: Труды II Сибирской школы молодого ученого. Томск, 2000.

С. 67-71.

Введение

Глава 1. Реконфигурация процессорной матрицы как метод обеспечения отказоустойчивости СБИС

1.1. Проблема отказоустойчивости СБИС и возможные пути ее решения

1.2. Реконфигурация процессорной матрицы

1.3. Алгоритмы реконфигурации процессорной матрицы

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

1.3.2. Алгоритм ограниченного захвата

1.3.3. Алгоритм свободного захвата

1.4. Выводы

Глава 2. Алгоритм диагонального захвата

2.1. Содержательное описание алгоритма

2.2. Сигналы перестройки

2.3. Соотношения между сигналами перестройки

2.4. Условия возникновения коммутаций

2.5. Логический анализ коммутаций

2.6. Алгоритм перенумерации

2.7. Корректность алгоритма перенумерации

2.8. Сравнение эффективности алгоритмов реконфигурации

2.9. Выводы

Глава 3. Метод программной реализации алгоритмов реконфигурации процессорной матрицы

3.1. Недостатки схемной реализации коммутационного окружения и возможный путь их преодоления

3.2. Архитектура СБИС с программной реализацией реконфигурации

3.3. Язык ЛОГИКА для описания клеточных автоматов

3.4. Программное обеспечение реконфигурации матрицы

3.5. Отладка алгоритмов реконфигурации с помощью системы ЛОГИКА

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

3.5.2. Алгоритм ограниченного захвата

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

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

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

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

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

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

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

- проверка с использованием этой системы ранее известных и модифицированных нами алгоритмов реконфигурации ОВС. 5

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

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

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

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

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

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

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

Практическая значимость работы.

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

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

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

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

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

2. Алгоритм адресации для перестройки по диагональному захвату.

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

4. Программная система ЛОГИКА, обеспечивающая реализацию метода программной реконфигурации процессорной матрицы, разработку и моделирование микропрограммных клеточных автоматов для реконфигурации матрицы и иных приложений.

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

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

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

Личный вклад автора.

Основные результаты диссертационной работы получены автором лично. 7

Апробация работы.

Основные результаты диссертации докладывались и обсуждались на Всероссийской конференции "Новые информационные технологии в исследовании дискретных структур" (Екатеринбург, 1996), на региональной научно-технической конференции молодых специалистов "Радиотехнические и информационные системы и устройства" (Томск, 1994), на Международном конгрессе студентов, аспирантов и молодых ученых (Томск, 1999), на семинарах кафедр математической логики и проектирования (радиофизический факультет) и программирования (факультет прикладной математики и кибернетики) Томского государственного университета (Томск, 1994; 2000).

Публикации.

Результаты исследований по диссертационной работе опубликованы в виде 4 статей в научных журналах, 2 докладов, 2 тезисов выступлений на конференциях (всего 8 печатных работ).

Структура и объем работы.

Диссертация состоит из введения, трех глав, заключения и библиографии. Она изложена на 128 страницах, содержит 24 иллюстрации, 7 таблиц. Библиографический список литературы цитированной литературы включает 76 наименований. Диссертация имеет 10 приложений на 72 страницах.

3.6. Выводы

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

Разработан язык ЛОГИКА для описания клеточных автоматов. Предлагается программная система ЛОГИКА для моделирования микропрограммных клеточных автоматов (МПКА) на ЭВМ.

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

120 на языке ЛОГИКА каждого из этих алгоритмов, а также алгоритма диагонального захвата.

С помощью программной системы ЛОГИКА описаны и отлажены четыре алгоритма реконфигурации процессорной матрицы.

121

Заключение

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

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

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

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

122 метода программной реконфигурации структуры предлагается программная система ЛОГИКА, позволяющая осуществлять реконфигурацию матрицы в управляющей ЭВМ. Данное программное обеспечение также может применяться для разработки новых алгоритмов реконфигурации процессорной матрицы.

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

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

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

3. Предлагается программная система ЛОГИКА для реконфигурации неразрезной процессорной матрицы.

123

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

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

3. Колбурн Е.Д., Коверли Г.П., Бехера С.К. Надежность МОП БИС // ТИИЭР. 1974. Т. 62. №2. С. 154-178.

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

5. Абрахам Дж.А., Фукс У.К. Модели неисправностей и ошибок для проектирования СБИС // ТИИЭР. 1986. Т. 74. № 5. С. 22-41.

6. Carter P.M., Wilkins B.R. Alpha particle induced soft errors in NMOS: a review // IEEE Proc. 1987. Y. 134. № 1. P. 32-44.

7. Browning J.S., Koda R., Kolasinski A. // IEEE Trans. Nucl. Sci. 1985. V. 32. № 6.

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

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

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

11. Нейман Дж. фон. Вероятностная логика и синтез надежных организмов из ненадежных компонент // Автоматы / Под ред. К.Э. Шеннона и Дж. Маккарти. М.: Иностранная литература, 1956. С. 68-139.

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

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

14. Ebihara Y. Fault-diagnosis and automatic reconfiguration for a ring subsstem // Comput. Networks and ISDN Syst. 1986. V. 10. № 2. P. 97-109.

15. Leighton F.T., Leiserson C.E. // IEEE Trans. Comput. 1984. V. 33. № 1.

16. Cliff R.A. // IEEE Trans. Comput. 1980. V. 29. № 2.124

17. Tamir Y., Seqwin C.H. // IEEE Trans. Comput. 1984. Y. 33. № 6.

18. Мельников В .А., Кальченко С.Б., Харченко B.C. Динамическая архитектура и модульные вычислительные системы на БИС // Зарубежная радиоэлектроника, 1990. № 1.С. 64-84.

19. Armsrong J.R., Gray F.G. // IEEE Trans. Comput. 1981. Y. 30. № 8. P.

20. Abraham S., Padmanabhan K. // Proceeding International Conference on Parallel Processing, Aug., 1988. P.

21. Nanya Т., Kawamyra T. // IEEE Trans. Comput. 1988. V. 37. № 1. P. .

22. Singh A.D. // IEEE Trans. Comput. 1988. V. 37. № 1. P. .

23. Пархоменко П.П. Организация распределенного резервирования в параллельных вычислителях//Всеросс. конф. «Новые информационные технологии в исследовании дискретных структур»: Докл. Екатеринбург, 1996. С. 182-185.

24. Chen H.-L., Tzeng N.-F. Efficient resource placement in hypercubes using multiple-adjacency codes // IEEE Trans. Comput. 1994. V. 43. № 1. P. 23-33.

25. Banerjee P., Peerce M. Design and evaluation of hard ware strategies for reconfiguring hypercubes and meshes under faults // IEEE Trans. Comput. 1994. V. 43. №7. P. 841-848.

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

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

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

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

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

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

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

33. Архитектура ОВС. Отчёты по НИР, рук. Воробьёв В.А., этапы 1,2,3,4 за 1991-92 гг., НИИ САПР АН, ОСОО ИНТЕРЧИП, ВСЕМИРНАЯ ЛАБОРАТОРИЯ, Томск, 1991.

34. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MBC-100. // Lecture Notes in Computer Science, 1995, № 964 /Third Int. Conf. Parallel Computer Technologies (PaCT-95), St. Petersburg, Russia, September 12-25, 1995, Proc./

35. Мишин А.И., Седухин С.Г. Вычислительные системы и параллельные вычисления с локальными взаимодействиями //Вычислительные системы. 1979. Вып. 78. С. 90-103.

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

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

38. Воробьёв В.А. Модель коллектива вычислителей, основанная на принципе близкодействия//Вычислительные системы. 1982. Вып. 94. С. 103-119.

39. Воробьёв В.А., Лаходынова Н.В. Теория модели коллектива вычислителей, основанная на принципе близкодействия // XXV области, научно-техн. конференция, посвященная 60-й годовщине образования СССР и Дню радио: Тез. докл. Новосибирск, 1982.

40. Валиев М.К., Мишин А.И. Организация параллельных вычислений на системах с локальными взаимодействиями элементов // Автометрия. 1983. № 6. С.88-96.

41. Завьялов Ю.С.,Мишин А.И. Временная сложность алгоритмов задач гидроаэродинамики и производительность параллельных вычислительных систем. СО АН СССР, Институт математики, Препринт № 20. Новосибирск, 1985.

42. Воробьёв В.А., Иноземцев С.П., Коновалов Н.Н. Исследование принципов построения специализированной системы управления. Отчет по НИР. М.: МАИ, 1986.40 с.126

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

44. Воробьёв В.А. Преодоление светового барьера в вычислительной технике. В кн.: Методы и средства проектирования специализированных вычислительных систем. Ленинск, 1989.

45. Лаходынова Н.В. Стохастическая модель однородной вычислительной системы, учитывающая межмашинные связи // Вычислительные системы. 1982. Вып. 94. С. 130-137.

46. Воробьев В.А., Корнеев В.В. Некоторые вопросы теории структур вычислительных систем // Вычислительные системы. 1974. Вып. 60. С. 3-16.

47. Воробьев В.А. Простейшие структуры однородных вычислительных систем // Вычислительные системы. 1974. Вып. 60. С. 35-49.

48. Воробьев В.А. Относительная адресация элементов циклического графа // Вычислительные системы. 1983. Вып. 97. С. 87-103.

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

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

51. Воробьёв В.А., Лаходынова Н.В. Пределы надежности однородных вычислительных систем // Вычислительные системы. 1988. Вып. 126. С. 122-149.

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

53. Лаходынова Н.В. Анализ и разработка методов обеспечения отказоустойчивости однородных вычислительных систем. Автореф. дисс. . канд. техн. наук. Москва, 1991. 18 с.

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

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

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

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

58. Воробьев В.А., Лаходынова Н.В. Вложение решеток в процессорную матрицу с отказами на основе сигналов согласия //Всеросс. конф. «Новые информационные технологии в исследовании дискретных структур»: Докл. Екатеринбург, 1998.

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

60. Лаходынова Н.В. Отказоустойчивые ОВС с перестраиваемой структурой. В кн.: Районные распределенные вычислительные системы. М., 1990.

61. Лаходынова Н.В. Отказоустойчивые ОВС с программируемым резервом // Распределенные вычислительные системы и сети. М., 1990.

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

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

64. Ерёмина Н.Л. Процессорная матрица с реконфигурацией по алгоритму диагонального захвата // Международн. конгресс «Наука, образование, культура на рубеже тысячелетий»: Труды II Сибирской школы молодого ученого. Томск, 2000. С. 67-71.

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

66. Ерёмина Н.Л. Алгоритм адресации для реконфигурации процессорной матрицы путем диагонального захвата // Вестник Томского государственного педагогического университета. 1999. №7. С. 47-51.128

67. Wolfram S. "Mathematica": A System for Doing Mathematics by Computer. Addison-Wesley Publishing Company, 1991.

68. Gray J.W. Mastering Mathematica: Programming Methods and Application AP Professional, 1994.

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

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

71. Ачасова C.B. Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990. 250 с.

72. Ерёмина Н.Л., Воробьев В.А. Отказоустойчивая матрица для обработки изображений // Региональная научно-техническая конференция «Радиотехнические и информационные системы и устройства»: Тез. докл. Томск, 1994. С. 7-9.

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

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

75. Димитриев Ю.К. Алгоритм самодиагностики вычислительных систем с программируемой структурой // Электронное моделирование. 1985. № 5. С. 20-26.

76. Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991. 278 с.129