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

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

Специальность 05.13.05 "Элементы и устройства вычислительной техники и систем управления"

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

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

БАБКИН •Геннадий Викторович

УДК 681.325.5

Курск - 1996

- г -

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

Научные руководители: дойтор технических наук, профессор кафедры ВТ КГТУ Типикин А. П.

кандидат технических наук, доцент кафедры ВТ КГТУ Колосков В.А.

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

доктор технических наук, профессор Дрейзин В.Э. кандидат технических наук, доцент Сусин В.Н.

Ведущая организация - в/ч 257Н

Защита диссертации состоится "27»-УУ 1996 г. в 1§_часов на заседании специализированного совета Д 064.50.02 по защитам диссертаций на соискание ученой степени кандидата технических наук при Курской государственном техническом университете (305039, Курск, ул. 50 лет Октября. 94)

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

Отзывы ка автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу: 305039. г.Курск, ул.50 лет Октября. 94, ученому секретарю специализированного совета Д 064.50.02.

Автореферат разослан 4 0 1996 г.

Ученый секретарь специализированного лппйтя

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

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

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

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

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

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

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

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

1) анализ методов реконфигурации матричных мультипроцессоров:

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

3) построение имитационных моделей методов перестройки мультипроцессоров и оценка эффективности предлояенных решений;

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

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

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

1) созданы алгоритмы перестройки матричных мультипроцессоров, основанные на учете использованного резерва и диагональном поиске путей перестройки матриц;

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

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

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

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

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

На основе результатов диссертации созданы:

1) алгоритмы реконфигурации;

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

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

Реализация и внедрение результатов работы. Созданный на основе результатов диссертационной работы отказоустойчивый акселераторный матричный мультипроцессор (ОАММП) используется АО "Прибор".

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

Публикации. По материалам диссертации опубликовано 14 работ.

Структура и обьем диссертационной работы. Диссертационная работа состоит из введения, четырех глав и заключения, содержащих 101 страницы основного текста, 70 рисунков и 8 таблиц, а также списка литературы из 89 наименований.на 10 страницах и 1 приложения на 32 страницах.

На защиту выносятся:

1. Множество показателей эффективности ОАММП. позволивших провести сравнительный многовариантный анализ методов реконфигурации.

ОЛИМП.

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

3. Секцйонированная топология структуры ОАММП с двухуровневой организацией введения избыточных ПЭ.

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

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

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

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

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

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

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

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

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

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

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

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

Среди известных методов реконфигурации выделены следующие:

1) метод с непосредственной перестройкой;

2) метод ограниченного захвата соседних ПЭ ;

3) метод свободного захвата соседних ПЭ;

4) метод двунаправленного свободного захвата соседних ПЭ;

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

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

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

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

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

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

1) при одновременном отказе по два ПЭ в соседних (1-1),1.(1+1) строках матрицы, которые соответствуют двум столбцам;

2) при возникновении двух парных отказов в строке 1 и [двух парных отказов в строке 1+2.

Из проведенного анализа известных методов реконфигурации сформулированы следующие направления совершенствования методов реконфигурации для ОАММП:

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

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

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

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

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

Учитывая приведенные выше направления автором предложены следую-Ецие методы реконфигурации:

1) метод ограниченного ортогонального захвата (МООЗ);

2) метод свободного ортогонального захвата (МСОЗ);

3) метод диагонального захвата (МДЗ);

МООЗ отличается от соответствующего метода Сами тем. что при захвате соседних ПЭ учитывается наличие незадействованных резервных ПЭ, расположенных ниже анализируемой строки. Если ниже анализируемой строки есть хотя бы один неиспользованный резервный ПЭ и в данной строке необходим захват соседнего ПЭ. то он осуществляется прежде; всего из нижней строки, а если это невозможно, то - из верхней. Таким образом, существенно повышается процент использования резервных ПЭ. Фатальный отказ матрицы, восстанавливаемой данным методом, появляется при отказе трех ПЭ подряд в одном и том же столбце ПЭ(1-1.Д).* ПЭ(1. Д). ПЭ(1+1.^. где 1 - номер строки, а 3 - номер столбца, и наличии в строке 1 еще хотя бы одного отказавшего или захваченного ПЭ с номером столбца меньше, чем ^

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

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

В тексте главы для каждого метода реконфигурации приведены:

1) его алгоритмы функционирования;

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

3) логические адреса и активные линии' связи после проведения реконфигурации;

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

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

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

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

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

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

В реамз полного перебора вычисляются следующие характеристики эффективности кетодов реконфигурации ОАММП:

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

И.

С(Ч») - . (1)

С!(я1)

где М, - количество работоспособных состояний системы для обобщенного отказа q1-i¡ кратности; 0,(4*) - общее количество работоспособных и неработоспособных состояний системы для обобщенных отказов Ч1-й кратности; д1 - кратность обобщенного отказа при конкретной распределении; 1 - количество ПЭ системы;

- l'l -

2) функция вероятности возникновения фатального отказа, которая определяется как отношение количества неработоспособных состояний Nj ко всей совокупности состояний Cj(q1) и представляет собой функцию вероятности возникновения-фатального отказа F(q') системы для данного обобщенного отказа :

Ni

Ftq1)-—"Г . (2)'

Ci (q1)

где Nj - количество неработоспособных состояний системы для обобщенного отказа q1-кратности. ....

3) коэффициент потенциального использования резерва Kr(q1) для обобщенного отказа q1-кратности, который вычисляется по формуле :

Ч1.

Kr (q1) = G(q') ■ - . (3)

Ri

где Gtq1) - коэффициент отказоустойчивости системы для обобщен-, ного отказа q1-кратности: Rj - общее количество резервных процессорных элементов:

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

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

т Hi 1 v т щ ,

у „ z —Mcv/з--I i —-г- ■ (-D

i.i W) V Cj(q1)

где V - объем выборки; Т - общее количество шагов реконфигурации за все время до наступления фатального отказа.

2) вероятность невосстановления Р системы вычисляется по формуле

т Я, • 1 v т н1-3

Р - I -—; МЕР]--I I --г- : ■ (5)

1.1 Сх(q1) V 1., Ci(q1)

3) коэффициент надежности Q(t) процессорной ?*атрицы вычисляется по формуле :

n'(t) l.v n',(t)

Q(t)--— ; MiQ(t)]-- I —2—. (6).

N(t) V Hj ct)

где n*(t) - количество вариантов распределения отказов, выдержавших t шагов реконфигурации; N(t) - общее количество вариантов.

4) коэффициент востребованного резерва Кгеа показывает относительную долю резервных ПЭ, использованных при наступлении фатального

отказа в матрице :

Ч1 1 V ч1,

Кгез» —Г— : К[КГ„] = — I —. (7)

К1 » 3-1

5) коэффициент реакции системы Бт на возникающие отказы характеризует возможности метода по восстановлению секции ОАММП при воздействии потока отказов различной кратности и вычисляется по формуле:

Т г ДдЧ '1 V Т ( Дч1, \

Б. - I 1--- ; М[Бт] = — I I 1 - —1 . (8)

1 ■ О Ч1 > V 1т01 Я1;, )

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

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

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

В работе также проведен сравнительный анализ эффективности всех методов реконфигурации по коэффициенту отказоустойчивости на квадратных секциях размером 6-6 ПЭ. Результаты этого анализа приведены на рис. 2. Они показывают, что предложенные автором методы перестройки позволяют повысить коэффициент отказоустойчивости при высоких крат-ностях отказов до 78 - 90% по сравнению с 28 - 40% в известных методах.

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

У - Ун + (Ук " Уи>"11 " (9)

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

а, - агеь,/1 + а3еьг" - 0 . (10)

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

функциональные модули

исполнительные модули

Супервизор

Интерактивный режим работы

Режим полного перебора

Моделирование секционированной матрицы

Режим случайной выборки

Ввод-вывод данных

Анализ параметров модели

Генератор подсказок и сообщений об ошибках

Генератор отказов Подсчет результатов модели

1 1

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

Генератор окон

Анализатор горячих клавиш

Анализатор наличия логического соседа в строке

Анализатор наличия логичес-крго соседа'в столбце

Анализатор положения

контекстнозависимой

помощи

Преобразователь файлов помощи

Метод ограниченного захвата

Метод свободного захвата

Метод двунаправленного захвата

Метод ограниченно-

ортогонального

захвата

Метод свободного

ортогонального

захвата

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

- 14 -

Коэффициент сгпказоустойчиЬости Коэффициент надежности

100 90 80 70 60 50 40 30 20 10 О

N н

\ \ Ч5'4 I

,г Vi 3

\ i 1

\\ 1

\\\ 1

i

\

1

i

1234567 123 4 567

Кратность отказов . Количество шагой реконфигурации

Рис. 2. Рис. 3.

1 - МОЗ; 2 - МСЗ; 3 - МДСЗ; 4 - МООЗ; 5 - Г1С03: 6 - ИДЗ; пунктиром обозначен боберишельмый интерйал

7 7 7 7 7 7

5 5 5 5 5 5 Рис. 4. Структурная схема процессорной ячейки

где а,-(уг-у3). а2-(у,-у3). а3=(у,-у2). Ь1=(х1-хг). Ь2=(х,-х3). а неизвестные ун.ук вычисляются'по следующим формулам :

уг . у1.е(Х1-х2)/1

Ун ■ У1-ех1/' - Ук ех1/' + ук . (12)

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

Кроме того в работе выполнено поверочное имитационное моделирование в режиме случайной выборки, показавшее, что погрешность аналитической экстраполяции не превышает 2 - 3%.

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

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

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

Проведенные исследования частот возникновения отказов высокого порядка кратности показали, что при вероятности отказа процессорного элемента Р < 2-10"2 основную долю среди возникающих отказов составляют однократные отказы в строке, а отказы второго порядка кратности и выше - всего 7.78%.

В связи с этим предложено наиболее часто возникающие однократные

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

Общая процедура парироБан;:я отказов разбита на две части одна из которых реализована аппаратно. а другая - программно. Каждая процессорная ячейка (ПЯ). структурная схема которой представлена на рис. 4, имеет в своем составе ПЭ (1). два коммутатора (2) и схему аппаратной реконфигурации (3). ПЯ между собой соединены.шестью линиями связи в каждом из четырех направлений. Схема аппаратной реконфигурации (рис.5) позволяет-автоматически парировать однократные отказы в строке. а при возникновении многократных отказов - вызывает прерывание работы ведущей ЭВМ. которая управляет дальнейшей реконфигурацей. Предложенные в работе устройства используют три различных способа тестирования, которые взаимно дополняют друг друга: тестирование по методу подвески процессора; периодическое тестирование ПЭ в моменты . времени, незадействованные решением прикладной задачи ОАММП; глобальное тестирование ОАММП с помощью ведущей ЭВМ.

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

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

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

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

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

- 17 - 1<1.Д

АО,/—1) _

— 1

С5рос _ R Т Q

— S <

-(i. i)

ЛебыО ПЗ

Правый ПЗ

Верхний Q1

МижниО ПЗ

к

к

к

г.»

■t 4

&

4 6

к « 2

K'.j)

A(i.j)

12 3 4-5

к Дешифратору

состоянио коммутаторой

tx(i+1.j)

Рис. 5 Схема аппаратной реконфигурации

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

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

1. Разработаны математическая и имитационная модели процедур реконфигурации для многовариантных сравнительных исследований отказоустойчивых акселераторных матричных мультипроцессоров (ОАММП). отличающиеся существенным расширением множества вычисляемых показателей эффективности и введением защиты от некорректностей сложного программного пакета и сбоев ЭВМ в ходе длительного процесса моделирования. В результате исследования на моделях трех известных и трех предложенных автором методов реконфигурации показано, что предлагаемые методы повышают коэффициент отказоустойчивости до 70 - 90% по сравнению с 28 -40% в известных методах, или примерно в два раза. <

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

3. Разработаны аппаратно-программные средства парирования отказов, основанные на гибком разделении функций контроля, 'тестирования и управления реконфигурацией между программной и аппаратной частями, которые в два раза снижают дополнительные аппаратные затраты по сравнению с известными подходами при незначительном снижении производительности вычислительной системы (не более 1,6-10*7%).

4. Предложена секционированная топология структуры резервированной матрицы ОАММП. позволяющая за счет двухуровневой организации обхода отказавших ПЭ как в пределах каждой из секций, так и путем замены неисправных секций повысить показатели эффективности реконфигурации на 5 - 20% по сравнению с одноуровневым резервированием без секционирования. Показано, что наилучшее сочетание показателей эффективности по коэффициентам отказоустойчивости и использования резерва имеют квадратные секции с размерами 4-4 ... 8-8 ПЭ.

5. Разработан вариант структурной и функциональной организации транспьютерного ОАММП, основанный на использовании встроенных аппа-

ратных распределенных средств реконфигурации, которые автоматически обнаруживают и парируют однократные отказы в каждой из строк матрицы ОАММП и позволяют осуществлять ее перестройку под управлением ведущей ЭВМ в случае многократных отказов в строке. Благодаря возможности парирования отказов ьысокой кратности созданы необходимые предпосылки для продления срока эксплуатации ОАММП в 1,5 раза, или до 12 - 20 лет по сравнению с 9 - 12 годами при использовании известных алгоритмов.

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

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

1. Колосков В.А., Колоскова Г. П.. Бабкин Г.В. Помехоустойчивое программное обеспечение микропроцессорной управляющей системы // Микропроцессорные комплексы для управления технологическими процессами : Всесоюзная научно-техническая конференция. Грозный. 1989. 2с

2. Колосков В. А., Колоскова Г. П., Бабкин Г. В. Проектирование специализированной базы данных на персональной ЭВМ // Интегрированные системы автоматизированного проектирования : Тезисы докладов Всесоюзной научно-технической конференции Москва'1989 г. 2с

3. Колосков В.А., Колоскова Г.П.. Бабкин Г. В.... Реализация процедур автоматизированного конструирования на персональной ЭВМ // Вопросы технической диагностики. Сб. научн. трудов. Ростов на Дону. РИСИ, 1990. 4с

'4. Колосков В.А., Колоскова Г.П.. ч Бабкин Г.В. Проектирование универсального постпроцессора на персональной ЭВМ // Алгоритмы и структуры систем обработки информации. Тула: ТПИ, 1990. 5с

5. Колосков 3. А.. Бабкин Г. В. Малая локальная сеть персональных ЭВМ // Новые информационные технологии, распознавание образов и анализ изображений. Курск, 1992. Зс

6. Колосков В.А.. Бабкин Г.В. Принцип обеспечения дефектоустойчивости систем управления // Новые информационные технологии, распознавание образов и анализ .изображений. Курск. 1992. 4с

7. Колосков В.А., Бабкин Г.В. Статическая самоорганизация однородной управляющей системы // Оптико-йлектронные приборы и устройства и системах распознавания образов, обработки изображений и символьной информации. Материалы международной НТК. Курск. 1993. 2с

8. Колосков В. А., Бабкин Г. В. Имиташ^нная модель однородной де-фектоустойчивой управляющей сети // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и

символьной информации. Материалы международной НТК, Курск, 1993. 2с

9. Бабкин Г.В., Колосков fe.A., Титов B.C. Самоорганизация дефек-тоустойчивой системы логического управления // Деп. рукопись N 1068-В93 от 21.04.93. Библ. указатель ЕИНИТИ "Депонированные рукописи". 1993. N 8. б/о 111.

10! Байсин Г. В., Колосков В. А. Декомпозиция микроконтроллерной сети // Тезисы докладов юбилейной конференции ученых Курского политехнического института. Курск, 1994. 2с

И. Колосков В.А.. Колоскова Г.П., Бабкин Г.В. Однородные управляющие самодиагностируемые сети с оперативной перестройкой // Микропроцессорные системы связи и управления на железнодорожном транспорте.-(тезисы докладов школы-семинара, (18 сентября 1994 г., г. Алушта). Харьков, 1994, 1с

12. Бабкин Г.В., Колосков В.А., Титов B.C. Моделирование распределенной реконфигурации микроконтроллерной сети // Приборы и приборные системы. Тезисы докладов. Тула, 26-29 сентября 1994 г., 2с

13. Бабкин Г.В., Колосков В.А., Титов B.C. Адаптивная логическая микроконтроллерная сеть // НейроСетевые и транспьютерные технологии и пути их использования в специальных технических комплексах. Материалы III научно-технического семинара 26-27 мая 1994 г., г. Курск. 4с

14. Бабкин Г. В., Колосков В. А. Распределенный алгоритм реконфигурации микроконтроллерной сети // Материалы и упрочняющие техноло-гии-94. Тезисы и материалы докладов Российской научно-технической конференции., Курск, 4ппл

Соискатель

Бабкин Г. В.

Подписано к печати

Печатных листов

_ Формат 60 X 84 1/16

Тираж 100 экз. Заказ _ЦЗ

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