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

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

Трунов Дмитрий Алексеевич

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

Специальность -05.13.01 «Системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

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

Курск - 2005

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

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

д. т. н., профессор Колосков В.А.

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

д. т. н., профессор Лопин В.Н. к. т. н., доцент Жмакин А.П.

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

Защита состоится 28 июня 2005 г. в 16:00 часов на заседании диссертационного совета Д 212.105.03 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, коференц-зал.

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

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

диссертационного совета

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

Старков Ф.А.

еъов

Ячьэ и>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов в диссертационной работе. Результаты работы внедрены в учебном процессе Курского государственного технического университета по дисциплинам "Информационные технологии в проектировании многопроцессорных систем", «Моделирование систем»

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: III Международной научно-технической конференции «Материалы и технологии XXI века» (г.Пенза, 2005 г.), Международной молодежной научной конференции «XXXI Гагаринские чтения» (г. Москва, 2005 г.), Международных научно-технических конференциях «Медико-экологические информационные технологии» (Курск, 2004, 2005), Научно-технической конференции "Материалы и упрочняющие технологии" (г. Курск, 2004 г.), 12-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2005» (г. Зеленоград, 2005 г.), III Межвузовской конференции по научному программному обеспечению «Практика применения научного программного обеспечения в образовании и научных исследованиях» (Санкт-Петербург, 2005).

Публикации. Основные результаты диссертационной работы опубликованы в 1 ¿"работах, в том числе в 8 статьях, в 3 тезисах докладов, в ^материалах конференций.

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

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

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

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

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

Личный вклад автора. В работах [4, 10,12], опубликованных в соавторстве, лично автором разработана инструментальная система для исследования

клеточных алгоритмов самоорганизации мультиконтроллеров. В работах [1, 2,3,11,15] автором разработаны методология и алгоритмы адаптивной реструктуризации матричных процессоров и мультиконтроллеров.

Объем и структура работы Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников. Общий объем диссертации составляет 153 страницы, содержащих 65 рисунков и графиков, и 5 таблиц, 8 страниц — список литературы из 80 использованных источников.

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

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

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

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

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

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

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

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

Для формального обоснования принципов реструктуризации ММК введена графовая модель 0(¥,и) с топологией, повторяющей исходную микроконтроллерную сеть (тор размерностью М х Ы). В графовой решетке с замкнутыми границами 0(У,11), вершины которой соответствуют микроконтроллерам сети, а ребра - связям между ними, задаются варианты назначения резервных узлов (веса соответствующих вершин = 1) и расположение отказавших элементов (веса отказавших вершин = /).

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

Для реализации управления реструктуризацией мультиконтроллера разработан алгоритм адаптивной реструктуризации, который обрабатывает данные о фатальных отказах в ММК, используя в качестве основной операцию параллельной маршрутизации, и выполняет поиск минимального варианта переотображения программных модулей по схеме ПОМ+ГГКМ. Пример поэтапного выполнения алгоритма реструктуризации ММК с заданным вариантом размещения резервных (12, 14, 21, 23, 41) и отказавших (22, 31, 32, 33, 42) узлов иллюстрируют рис. 1 и 2.

а)

б)

Рис.1. Пример построения маршрута реструктуризации По результатам маршрутизации определяется схема ПОМ переотображения ПОМ: {4.1, 3.1} =>{3.1, 3.2}. Множество работоспособных узлов-соседей для элементов 4.1, 3.1 состоит из вершин {1.1, 2.1, 3.4, 4.1, 4.4}. Схема ПКМ переотображения копий ПМ с соответствующих направлений включает по одной копии от вершины найденного маршрута (табл. 1).

Таблица 1

После выполнения переотображения по схемам ПОМ и ПКМ и восстановления исходного отказового состояния решетки для фатально отказавше-

У 1.1 2.1 3.4 4.1 4.4

—>•

4.1/3 1 3 1/3 2

•<- 3 1/32 4.1/3.1

т 3.1/3.2

го узла устанавливается признак х1}г = 1 (рис. 2,а) и в режиме функционирования выполняется самоорганизация ММК, которая успешно завершается репро-

дуцированием всех исходных функций системы (рис 2,6 - отказавшие вершины отмечены весом <10>).

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

а) б)

Рис.2. Пример адаптации к фатальному отказу

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

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

Были сформулированы и доказаны утверждения, определяющие для каждого из методов реконфигурации координаты удаляемых из сегментов столбцов (строк), называемые далее координатами базовых линеек реструктуризации, что обеспечивало перевод фатальных конфигураций в область исправляемых отказов. Структура исходной сегментированной процессорной матрицы представляется решеткой с разомкнутыми границами Лтх„ , произвольный сегмент tк е Д тХ„ обозначается в виде пары координат левого нижнего <И,/1>

и правого верхнего <i2,j2> элементов- tk = H,jl>,^i2,j2>) Предлагаемый подход к реструктуризации сегментов матрицы базируется на двух понятиях: слияния сегментов и исключения столбцов или строк сегмента, для формального описания которых введены операции: WE(tl,t2), WS(tl,t2) - слияния сегмен-

«

tob tl,t2 по горизонтали / вертикали; Dl(tljk), D2(t],ik) - исключения столбцаjk / строки ik сегмента tl.

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

V WE(tm,tn) (tl(jk:jk)etm, tl(jljl)etn)^\tl(jkjk)\=\ tl(jljl)\, (1)

V WS(tm,tn) (t2(ikik)etm, t2(ilil) etn)=$\ t2(ibik)\=\ t2(ilil)\ (2) Условия повторного слияния произвольного сегмента t3=<(iljl), (i3,j3)>,

полученного в результате горизонтальной /вертикальной реструктуризации вида {WE(<(UJl), (i3J2)>,<(ilJ2+1), (i3j3)>)*Dl(<(iljl), (i3J2)>Jl)}/

{WS(<(iljl), (i2-l),j3)>,<(i2jl), (i3J3)>)a D2(<(i2jl), (i3J3)>,il)}, имеют вид:

VDl(t3,jk) => jk>j2лjl<j2 (3) либо \/D2(t3,ik) =>ik<i2л il>i2, (4)

где il, jl - номера исключенных ранее строки/столбца; ik, jk - номера исключаемых строки/столбца.

Для управления реструктуризацией сегментированных процессорных матриц разработан алгоритм адаптивной реструктуризации, выполняющий по* иск координат исключаемых при объединении сегментов строк/столбцов, проверку условий (1) - (4) допустимости слияния сегментов и определение облас-t тей переотображения сегментов при горизонтальной / вертикальной ресегмен-тациях WE (t3,t4) *Dl(t3,jk) / WS(t3,t5)лD2(t3,ik)

В работе исследовались несколько модификаций алгоритма реструктуризации (слияние по горизонтали; слияние по вертикали; комбинированное слияние) применительно к различным алгоритмам реконфигурации. На рис 3 при-

11

веден пример моделирования алгоритма горизонтальной реструктуризации для матрицы, реконфигурируемой методом непосредственной перестройки Наличие фатальной комбинации отказов в левом сегменте (рис.3,а) инициировало ресегментацию WE ((<4,1>,<1,4>),(<4,5>,<1,8>)) лD1((<4,1>,<1,4>),4).

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

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

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

Предлагаемая методология разрушения фатальных конфигураций осно- *

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

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

а)

1.1 1.0 1.2 1.0 1.3 1.4 1.5 1.6 1.7

2.1 2.0 2.2 2.0 Тз1 2.4 2.6 2.7

3.1 3.2 3.3 3.0 3.4 0.5 оТ| 3.7 3.8

4.1 оТ| 43 4.0 4.4 3.5 3 6 4.7 4.8

« Ш у -Ал 4.5 4.6 «V- *

1.8

б)

Рис.3. Пример реструктуризации

ризации сегментов Выбор направления реструктуризации выполнялся в соответствии с условиями (1), (2) (см.гл.З). Доказано, что возможность повторной реструктуризации произвольного сегмента, полученного в результате ресегмен-тации вида {\¥Е(П(1: ]к,), <(И,]2+1), (В,]3)>) лШ(/к,)} /

{\¥Б(12(13 .Чк1), <(И,]1), (¡2-11]2)>)лЯ2(1к,)}, определяется условиями У Я 1(]к2) => )к2>)2 (5) либо Я2(1к2) => ¿к2<12, (6) где Я1(]к2) / К2(1к]) - операции деактивизации и переведения в резерв столбца jk| /строки /А:/; ¡к2, ]к2 - номера деактивизируемых строки/столбца в текущей реструктуризации.

Разработанный алгоритм реструктуризации базируется на данных о конфигурации отказов в матрице и условиях (1), (2), (5), (6), допустимости реструктуризации. На рис.4, представлены результаты моделирования алгоритма реструктуризации, позволившего разрушить две фатальные комбинации (реконфигурация - непосредственная перестройка) перемещением резерва в фатальные области отказов.

11 1.0 12 10 1 3 1 4 1 5 1 6 1 7 18 19 1 10|1 11И 12|1.0|

21 22 20 23 24 2.0 25 26 2.0 27 28 29 210.211 212

31 32 3 0 0.« 34 0.5 36 Э-0 37 38 39 310 311 : 1 |Л)|

41 0.2 40 33 44 35 46 40 0.8 48 49 14101411 4Ч|401 ооТпТ о т!о п[о 1/00 11114 11

J 1 42 £1 43 и и 45 0.6 0 1 47

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

I В данной главе приведены также варианты функциональной организации

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

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

В качестве показателя, характеризующего способность алгоритма к адаптивной реструктуризации, выбрана вероятность сохранения работоспособности состояния мультипроцессора А"^ при заданном числе п отказавших элементов (корректирующая способность):

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

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

где К1 - корректирующая способность /-го варианта реструктуризации; К0 -корректирующая способность базового варианта; п - количество отказов/дефектов.

Результаты оценки значений //, показали, что в диапазоне числа п отказов [100, 250] разработанные алгоритмы реконфигурации имеют существенный выигрыш. Так, при числе отказов, равных 100, количество фатальных ситуаций в матрице уменьшилось в 7,5 раз.

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

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

Чх\'Ч \-К1 (п) '

т 1=0

где Р, - вероятность безотказной работы отказоустойчивой однородной систе-

С

мы ;-го варианта реструктуризации; - число сочетании из т+п по} эле-

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

На рис. 5 представлены графики зависимости Р, = /(р) для матрицы размерности 48x48, разбитой на сегменты 6x6 (графики Р0 ,Р;, Р2 соответствуют базовому варианту без адаптации и вариантам реструктуризации методом слияния и перемещения резерва).

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

Реализация алгоритмов реструктуризации мультиконтроллеров не требует дополнительных аппаратурных затрат, а связана только с локальным перепрограммированием. Временные затраты на перезагрузку программных модулей в режиме реструктуризации составляют для одиночных и двойных фатальных комбинаций 6-9%, для более сложных комбинаций отказов не более 18% от общего объема перезагрузки системы. При этом достигается существенное повышение корректирующей способности К по сравнению с базовым вариантом (К0).

Р1

Р

Рис.5. Графики функций надежности

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

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

При решении поставленной задачи получены следующие результаты:

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

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

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

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

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

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

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

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

1. Трунов, Д.А. Алгоритмы реструктуризации мультиконтроллеров [Текст] / Трунов Д.А., В.А Колосков // Известия КГТУ. Курск: Курск, гос. техн. ун-т. 2005. №2 (15). С.79-85.

2. Трунов, Д.А. Метод ресегментации структуры матричных процессоров [Текст] / Д.А. Трунов, В.А. Колосков // Известия КГТУ. Курск: Курск, гос. техн. ун-т. 2005. №2 (15). С.93-99.

3. Трунов, Д.А. Теоретико-множественный подход к решению задачи ресегментации структуры матричных процессоров [Текст] / Д.А. Трунов, В.А. Колосков //Телекоммуникации. 2005. №6. С.8-15.

4. Трунов, Д.А. Алгоритмы самоорганизации мультиконтроллеров с гибким резервированием столбцов [Текст] / Д.А. Трунов , В.А. Колосков // «Информационная математика». 2004. №2. Москва. С. 106-114.

5. Трунов, Д.А. Реконфигурирование сегментированной процессорной матрицы [Текст] / Д.А. Трунов // Сборник материалов Российской научно-технической конференции «Материалы и упрочняющие технологии - 2004». Курск, 2004. С. 213-216.

6. Трунов, Д.А. Алгоритмы повышения отказоустойчивости сегментированных процессорных матриц [Текст] / Д.А. Трунов,// Сборник статей III Международной научно-технической конференции «Материалы и технологии XXI века». Пенза, 2005. С.151-154.

7. Трунов, Д.А. Алгоритмы ресегментации отказоустойчивых мультипроцессоров [Текст] / Д.А. Трунов // Сборник статей молодых ученых «Приборы и управление» - Тула, 2004. №2. С.38-45.

8. Трунов, Д.А. Исследование алгоритмов ресегментации структуры мультипроцессорных систем [Текст] / Д.А. Трунов // Сборник статей молодых ученых «Приборы и управление». Тула, 2005. №3. С. 52-57.

9 Трунов, Д.А. Адаптивная реструктуризация многопроцессорных систем [Текст] / Д.А. Трунов // Сборник научных трудов «Инновационные методы в образовании, науке и медицине». Курск: КГУ. 2005. С.111-115.

10 Трунов, Д.А. Исследование методов реструктуризации многопроцессорных систем [Текст] / Д. А. Трунов, И Б. Борисовский // Сборник материалов YIII Международной научно-технической конференции «Медико-экологические информационные технологии - 2005». Курск, 2005. С. 131-136.

11. Трунов, Д.А. Оптимизация загрузки параллельных систем обработки данных генетическим методом [Текст] / Д.А. Трунов, И.Б. Борисовский // Сборник научных трудов «Инновационные методы в образовании, науке и медицине». Курск: КГУ. 2005. С.18-22.

12. Трунов, Д.А. Моделирование среды самоорганизации отказоустойчивых мультипроцессорных систем [Текст] / Д.А. Трунов, В.А. Колосков // Тезисы докладов III межвузовской конференции по научному программному обеспечению «Практика применения научного программного обеспечения в образовании и научных исследованиях». СПб. 2005. С. 46-48.

13. Трунов, Д.А. Моделирование пересегментации отказоустойчивых матриц процессорных элементов [Текст] / Д.А. Трунов //Тезисы докладов III межвузовской конференции по научному программному обеспечению «Практика применения научного программного обеспечения в образовании и научных исследованиях». СПб. 2005. С. 43-45.

14. Трунов Д.А. Метод репрограммирования структуры сегментированных процессорных матриц [Текст] / Д.А. Трунов // Тезисы докладов международной молодежной научной конференции «XXXI Гагаринские чтения». М.: MATH. 2005. С.77-78.

15. Трунов Д.А. Репродуцирование логической структуры отказоустойчивых мультиконтроллеров [Текст] / Д.А. Трунов, A.A. Абуджахал // Тезисы докладов 12-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика -2005». М.: МИЭТ. 2005. С.241.

Соискатель

Трунов Д.А.

Подписано к печати 19.05.2005 Формат 60 х 84 1/16

Печатных листов 1,0 Тираж 100 экз. Заказ 256

Курский государственный технический университет, 305040, г. Курск, ул. 50 лет Октября, 94.

un 109

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

2006-4 6305

ВВЕДЕНИЕ.

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

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

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

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

1.4. Выводы к главе.

2. АЛГОРИТМ АДАПТИВНОЙ РЕСТРУКТУРИЗАЦИИ ОТКАЗОУСТОЙЧИВЫХ МУЛЬТИКОНТРОЛЛЕРОВ. л 2.1. Принципы адаптивной реструктуризации мультиконтроллеров.

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

2.3. Примеры реализации алгоритма.

2.4. Выводы к главе.

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

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

V сегментов.

3.2. Определение базовой линейки ресегментации.

3.3. Алгоритм ресегментации методом слияния сегментов.

3.4. Примеры реализации алгоритма.

3.4. Выводы к главе.

4. РЕСТРУКТУРИЗАЦИЯ ПРОЦЕССОРНЫХ МАТРИЦ МЕТОДОМ ПЕРЕМЕЩЕНИЯ РЕЗЕРВА.

4.1. Характеристика метода перемещения резервных линеек.

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

4.3. Аппаратная реализация среды реструктуризации.

4.4. Выводы к главе.

5. ИССЛЕДОВАНИЕ АЛГОРИТМОВ АДАПТИВНОЙ

РЕСТРУКТУРИЗАЦИИ.

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

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

5.3. Выводы к главе.

Актуальность работы. К качественно яовым требованиям, предъявляемым к функциональным характеристикам приводной техники для технологических машин, относятся: способность системы к реконфигурации в зависимости от выполняемой конкретной задачи или операции и обеспечение высокой надежности и безопасности функционирования. Встроенные интеллектуальные устройства, реализованные на новой элементной базе, позволяют получить компактные и надежные мехатронные узлы и строить на их основе многокоординатные мехатронные системы с децентрализованным управлением [1,2]. Интеллектуальные распределенные системы управления могут обеспечить не только выполнение сложных движений, но и приспособиться к возникающим при эксплуатации внутренним нарушениям, и перестроиться при фатальных ситуациях для продолжения работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты работы внедрены в учебном процессе Курского государственного технического университета по дисциплинам "Информационные технологии в проектировании многопроцессорных систем", «Моделирование систем».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: III Международной научно-технической конференции «Материалы и технологии XXI века» (г.Пенза, 2005 г.), Международной молодежной научной конференции «XXXI Гагаринские чтения» (г. Москва, 2005 г.), Международных научно-технических конференциях «Медико-экологические информационные технологии» (Курск, 2004, 2005), Научно-технической конференции "Материалы и упрочняющие технологии" (г. Курск, 2004 г.), 12-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2005» (г. Зеленоград, 2005 г.), III Межвузовской конференции по научному программному обеспечению «Практика применения научного программного обеспечения в образовании и научных исследованиях» (Санкт-Петербург, 2005).

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

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

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

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

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

4. Результаты исследований на программной модели алгоритмов реструктуризации, позволившие оценить их предельные возможности. Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников. Общий объем диссертации составляет 000 страниц, содержащих 00 рисунков и графиков, и 0 таблиц, 00 страниц - список использованных источников.

5.3. Выводы к главе

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

1. Сироткин, У.С. Механотронные технологические машины в машиностроении. Текст. / Подураев, Ю.В., Богачев, Ю.П. Мехатроника, автоматизация, управление. 2003. №4.

2. Методы классической и современной теории автоматического управления Текст.: учебник в 3-х т. М.: МГТУ. 2000.

3. Богданов, Ю.И. Статистические модели управления дефектностью и выходом годных в микроэлектронике Текст. Т. 32 / Богданова, Н.А., Дшхуян, В.Л.: Микроэлектроника. 2003. №1 С. 62-76.

4. Lombardi, F. Guest Editors Introduction Текст. / Sami, M. : IEEE Transactions an computers. Vol.49 no.6 2000. pp 529-530.

5. Mangir, Т.Е. Fault-tolerant design for VLSI : effect of incorrect requirements on Yield Improvement of VLSI designs Текст. / Avizienis, A. : IEEE Transactions an computers. Vol. C-31, no.7 1982 pp. 609-615.

6. Koren, I. Fault-tolerant in VLSI circuits. / Singh, A.D. : Computer, special issue an Fault-tolerant Systems. July 1990. V.23. p.73-83.

7. Koren, I. Defect Tolerance in VLSI Circuits : Techniques and Yield Analusis. Текст. / Koren, Z. : Proceeding af the IEEE. Sept. 1998. V.86 p. 18171836.

8. Немудрое, В. Системы на кристалле. Проектирование и развитие. Текст. / Мартин Г. : М. : Техносфера 2004. 216 с.

9. Горлов, М.И. Технологические методы повышения надежности ИС в процессе серийного производства. Текст. / Андреев, А.В. и др.: Макроэлектроника. 2004. №1. С. 24-34.

10. Цилькер, Б.Я. Организация ЭВМ и систем Текст. : учеб. для вузов / Орлов, С.А. : СПб.: Питер 2004. 668 с.

11. Хамахер, К. Организация ЭВМ. Текст. / Вранешич 3., Заки С. Изд. 5-е.: СПб.: Питер. 2003. 848 с.

12. Воеводин, В.В. Параллельные вычисления. Текст. / Воеводин, Вл.В. : СПб. : БХВ Петербург 2002 - 608 с.

13. Таненбаум, Э. Архитектура компьютера СПб. : Питер 2002 704 с.

14. Бахтеяров С.А. Транспьютерная технология Текст. / Под редакцией C.B. Емельянова. М.: Радио и связь, 1993. 304 с.15. , Иыуду, К.А. Надежность контроль и диагностика вычислительных машин и систем. Текст. М. : Высшая школа, 1989 260 с.

15. Каравай, М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры. Текст. / Автоматика и телемеханика. №12. 2004. С. 159-177.

16. Каравай, М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и к-отказоустойчивость. Текст. / Автоматика и телемеханика. №1. 2005. С. 175-189.

17. Левин, В.К. Высокопроизводительные мультимикропр9цессорные системы Текст. Информационные технологии и вычислительные системы. 1995. №1. С. 12-21.

18. Хорошевский, В.Г. Вычислительные системы с программируемой структурой. Текст. / Информационные технологии и вычислительные системы. 1997. №2. С. 13-23.

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

20. Корнеев, В.В. Параллельные вычислительные системы. Текст. / М. «Нолидж». 1999. 320 с.

21. Захаров, И.С. Информационные технологии проектирования отказоустойчивых мультиконтроллеров. Текст. : учебное пособие /

22. Колосков, В.А., Медведева, M.B. : Курский государственный технический университет. Курск. 2003. 271 с.

23. Погребииский, С.Б. Проектирование и надежность ЭВМ. Текст. / Стрельников, В.П.: Москва : Радио и связь. 1988. 168 с.

24. Митрофанов, В. Направления развития отечественных высокопроизводи-тельных систем. Текст. / Слуцкий, А., Ларионов, К., Эйсымонт, Л. : Открытые системы. №5.2003. С. 29-35.

25. Пат. 2197745 Российская федерация. Ячейка однородной среды. Текст. / Колосков В.А. и др. / Бк>л. №3. 2003.

26. Пат. 2177169 Российская федерация. Ячейка однородной среды процессорных элементов. Текст. / Колосков В.А. и др. / Бюл. №35. 2001.

27. Пат. 2156492 Российская федерация. Отказоустойчивый мультимикроконтроллер. Текст. / Колосков В.А. и др. / Бюл. №26. 2000.

28. Пат. 2133054 Российская федерация. Распределенная система для программного управления. Текст. / Колосков В.А. и др. / Бюл. №19. 1999.

29. Пат. 2198417 Российская федерация. Распределенная система для программного управления. Текст. / Колосков В.А. и др. / Бюл. №4. 2003.

30. Пат. 2122229 Российская федерация. Распределенная система для программного управления. Текст. / Колосков В.А. и др. / Бюл. №32. 1998.

31. Пат. 2110827 Российская федерация. Дискретная микроконтроллерная сеть. Текст. / Колосков В.А. и др. / Бюл. №13. 1998.

32. Пат. 2103724 Российская федерация. Ячейка однородной среды. Текст. / Колосков В.А. и др. / Бюл. №3. 1998.

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

34. Медведева, М.В. Клеточная самоорганизация программируемых отказоустойчивых мультимикроконтроллеров. Текст. / Медведев, A.B., Колосков, В.А., Старков, В.А. : Курский гуманитарно-технический институт, 2000.

35. Кун, С. Матричные процессоры на СБИС. Текст. / Пер. с англ. М. : Мир, 1991.672 с.

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

37. Горяшко, А.П. Специализированные вычислительные структуры. Текст. / В 3-х кн. Кн.З Программные и аппаратные средства : Справочник / Под редакцией Захарова, В.Н., Хорошевского, В.Ф. М. : Радио и звязь, 1990. С.258-284.

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

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

40. Головко, В.А. Методы обеспечения отказоустойчивости линейных систолических процессоров. Текст. / Микроэлектроника, 1995. т.24. №3. С.229-240.

41. Kung, S.Y. Fault-Tolerant Array Processor Using Single-Track Switches. Текст. / IEEE Trans, on Computers, 1989. Vol. 38. №4. pp. 501-514.

42. Roychowdhuru, V.P. Efficient Algoritms for Reconstruction in VLSI/WSI Array. Текст. / IEEE Trans. Computers 1989. Vol.49. №6. pp. 480-489.

43. Low, C.P. An Efficient Reconfiguration Algorithm for Degradable VLSI/WSI Array. Текст. / IEEE Trans, on Computers, 1989. vol.49. №6. pp.553559.

44. Ozguner, F. A Reconfiguration Algorithm for Fault Tolerance in a Hypercube Multiprocessor. Текст. / Aykanat, C. Information Processing Letters, vol.29, pp.247-254. nov.1998.

45. Sridar, M.A. On Finding Maximal Subcubes in Residal Hypercubes. Текст. / Raghavendra C.S. Proc. Second IEEE Symp. Parallel and Distributed Processing, pp. 870-873. Dec. 1990.

46. Latifi, S. Distributed Subcube Identification Algorithm for Reliable Hypercubes. Текст. / Information Processing Letters, vol.38, pp.315-321, June 1991.

47. Numata, J. Reconfigurable Architectures for Mesh-Interconnected Multiprocessor System. Текст. / Horiguchi, S. IFICE Technical Report WS192, №6, 1992.

48. Bruck, J. Efficient Fault-Tolerant Mesh and Hypercube Architectures. Текст. / Cypher, R., C.-T.Ho Proc.22 Int'l Symp. Fault-tolerant Computing, pp. 162-169, July 1992.

49. Kim, J.H. The Rule-Based Approach to Reconfiguration of 2-D Processor Arrays. Текст. / Rhee, P.K. IEEE Trans. Computers, vol.42, no.ll. pp.1403-1408, Nov. 1993.

50. Varvarigou, T.A. A Polynomial Time Algoritm for Reconfiguring Multipl-Track Models Текст. / IEEE Trans, on Computers, vol.42 no.4. pp. 385-395.

51. Varvarigou, T.A. Reconfiguring Processor Arrays Using Multiple-Track Models: The 3-Track-1-Spare-Approach. Текст. / Roychowdhury, V.P., Kailath. T. IEEE Trans. Computers, vol.42, no 11. pp. 1281-1293.

52. Chandra A. Reconfiguration in 3D Meshes. Текст. / Proc. 1994 Int'l Workshop Deffect and Fault Tolerance in VLSI Systems, pp. 194-202. 1994.

53. Takanami, I. A Neural Algorithm for Reconstructing Mesh-Connected Processor Arrays Using Singl-Track Switcher. Текст. / Proc. Int. Conf. WSI, 1995. pp. 101-110.

54. Tzeng N.F. Maximum Reconfiguration of 2-D Mesh Systems with Faults. Текст. / Proc. 25 IntM Conf. Parallel Processing, pp.I-77-I-84. Aug.1996.

55. Low, C.P. Minimum Fault Coverage in Memory Arrays : A New Algorithm and Probablistic Analysis. Текст. / IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, pp. 681-690. June 1996.

56. Horita, T. A Built-in Self-Reconstructions Approash for Partitioned Mesh-Arrays Using Neural Algorithm. Текст. / Takanami, I. IEICE Trans. Inf. And System, 1996. Vol. E79-D, №8, pp. 1,160-1,167.

57. Chen, H.L. «Subcube Determination in Faulty Hypercubes.» Текст. / Tzeng, N.F. IEEE Trans. Computers, Vol.46, no.8, pp.871-879, Aug. 1997.

58. Chen, H.L. «А Boolean Expression-Based Approach for Maximum Incomplete Subcube Identification in Faulty Hypercubes» Текст. / Tzeng, N.F. IEEE Trans. Parallel and Distributed Systems, Vol.8, no.ll, pp.1171-1183, Nov. 1997.

59. Horita, T. Fault-Tolerant Processor Arrays Based on the 1 V2 Track Switsnes with Flexible Spare Distributions. Текст. / Takanami, I. IEEE Trans, on Computers, 2000. Vol.49, №6, pp. 542-552.

60. Беляев, Ю.К. Надежность технических систем. Текст. / Богатырев,

61. B.А., Болотин, В.В. и др. : справочник под редакцией Ушакова И.А. : М. : Радио и связь, 1985. — 608 с.

62. Смирнов Н.И. Оценка безотказности интегральных микросхем. Текст. / Широков Б.Б. М. : Радио и связь 1983. 104 с.

63. Горяшко, А.П. Методы оценки отказоустойчивых структур СБИС. Текст. / Шура-Бура, А.Э. Изв. АН.СССР. Сер. Техн. кибернетика 1988. №6.1. C.133-142.

64. Головко, В.А. Некоторые аспекты определения выхода годных для отказоустойчивых схем на кристалле. Текст. / Микроэлектроника 1992. т.21. №5. С.37-44.

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

66. Стэппер, Ч. Статические модели выхода годных интегральных микросхем. Текст. / Армстронг, Ф., Саджи, К. ТИИЭР 1983. т.74. №4. С.6-26.

67. Трунов, Д.А. Реконфигурирование сегментированной процессорной матрицы Текст. / Д.А. Трунов // Сборник материалов Российской научно-технической конференции «Материалы и упрочняющие технологии 2004». Курск: КГТУ, 2004. С. 213-216.

68. Трунов, Д.А. Алгоритмы ресегментации отказоустойчивых мультипроцессоров Текст. / Д.А. Трунов // Сборник статей молодых ученых «Приборы и управление» Тула: ТГУ, 2004. №2. С.38-45.

69. Трунов, Д.А. Исследование алгоритмов ресегментации структуры мультипроцессорных систем Текст. / Д.А. Трунов // Сборник статей молодых ученых «Приборы и управление». Тула: ТГУ, 2005. №3. С. 52-57.

70. Трунов, Д.А. Алгоритмы повышения отказоустойчивости сегментированных процессорных матриц Текст. / Д.А. Трунов,// Сборник статей III Международной научно-технической конференции «Материалы и технологии XXI века». Пенза. 2005. С.151-154.

71. Трунов Д.А. Метод репрограммирования структуры сегментированных процессорных матриц Текст. / Д.А. Трунов // Тезисы докладов международной молодежной научной конференции «XXXI Гагаринские чтения». М.: МАТИ. 2005. С.77-78.

72. Трунов, Д.А. Теоретико-множественный подход к решению задачи ресегментации структуры матричных процессоров Текст. / Д.А. Трунов, В.А. Колосков //Телекоммуникации. 2005. №6. С.8-15.

73. Трунов, Д.А. Алгоритмы самоорганизации мультиконтроллеров с гибким резервированием столбцов Текст. / Д.А. Трунов , В.А. Колосков //

74. Научно-технический журнал «Информационная математика». 2004. №2. Москва. С. 106-114.

75. Трунов, Д.А. Метод ресегментации структуры матричных процессоров Текст. / Д.А. Трунов, В.А. Колосков // Известия КГТУ. Курск: Курск, гос. техн. ун-т. 2005. №2 (15). С. 93-99.

76. Трунов, Д.А. Адаптивная реструктуризация многопроцессорных систем Текст. / Д.А. Трунов // Сборник научных трудов «Инновационные методы в образовании, науке и медицине». Курск. 2005. С.111-115.

77. Трунов, Д.А. Алгоритмы реструктуризации мультиконтроллеров Текст. / Трунов Д.А., В.А. Колосков // Известия КГТУ. Курск: Курск, гос. техн. ун-т. 2005. №2 (15). С. 79-85.

78. Трунов, Д.А. Оптимизация загрузки параллельных систием обработки данных генетическим методом / Д.А. Трунов, И.Б. Борисовский // Сборник научных трудов «Инновационные методы в образовании, науке и медицине». Курск. 2005. С. 18-22.