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

РГ6 од - 7 11101! 1993

ХАРЬКОВСКИЕ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

На правах рукописи. Нуньес Игурри Сиро Хааьер.

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

05.13.05. - элементы и устройства вычислительной техники и систем управления.

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

Харькое-1993

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

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

профессор Дербунович Л. В.

Официальные оппоненты - доктор технических наук,

профессор Поляков Г. А.

кандидат технических наук, доцент Сытник Б. Т.

Ведущее предприятие - НПО "Теплоавтомат" (г. Харьков.)

Зашита состоится 1993 г. в час. За

мин. на заседании Специализированного совета Д 068.39.02 при Харьковском политехническом институте (310002, г. Харьков, ГСП, ул Фрунзе, 21.)

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

Автореферат разослан ' Д-Л^АЯ 1993 г.

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

Киэилов В. У.

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

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

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

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

Несмотря на то, что задачи синтеза систолических процес-

соров привлекают внимание многих исследователей, вопросы проектирования легко диагностируемых и самопроверяемых систолических процессоров и ИЛМ, ориентированных на их исполнение в виде СБИС, до настоящего времени недостаточно хорошо исследованы.

Поэтому создание легко диагностируемых систолических про--цессоров и ИЛМ на основе использования современной технологии СБИС и их применение в управлявших и вычислительных системах является актуальной и перспективной задачей..

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

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

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

- разработка эффективных методов тестового диагностирования ИЯМ;

- разработка методов тестопригодного проектирования Ш1М;

- разработка методов автономного тестирования ИЛМ;

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

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

Научные результаты и основные положения, выносимые на эав<иту:

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

2.Структура встроенных средств тестового диагностирования для обнаружения кратных функциональных неисправностей в ИЛМ.

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

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

систолических процессоров (С-СП) на основе пространственно-временного анализа алгоритмов, реализуемых в С-СП.

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на республиканской научно-технической конференции "Функционально Ориентированные Вычислительные Системы" (г. Алушта, Октябрь, 1990 г.) и на республиканской научно-технической конференции "Микропроцессорные системы связи и управления на железнодорожном транслорте"Сг. Киев, 1990).

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

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

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

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

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

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

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

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

В работе используется автоматное представление ИЛМ, в котором поведение каждой ячейки ИЛМ описывается моделью детерминированного конечного автомата А(Х,У,2,<5Д), где Х,У- множества входных и выходных символов, 2- множество состояний, 6,\- функции переходов и выходов, соответственно.

Предложен метод тестового диагностирования, в котором правильность откликов ИЛМ на тестовые вектора можно проверить простой схемой равнозначности, поскольку отклики ячеек идентичны между собой (I- тестирование). Действительно, если разбить таблицу переходов-выходов (ТПВ) Рва ч частичных таблиц переходов-выходов |Т|=ч, то каждая из составляющих частичных таблиц Гк Ск=1,...ч) содержит переходы ДСг^.х^З, где

ХСг^х^ ук, у Xj6X, укеУ.

Нижеследующая теорема определяет необходимые и достаточные условия I-тестируемости ИЛМ для МКН.

Теорема 1. Множество тестов (1Т) проверяет таблицу истинности проверяемой ИЛМ (Ат), если для каждой частичной ТПВ Гк ячейки выполняются следующие условия:

1)каждый возможный переход в Гк проверяется подмножеством

Ч

тестов Цс 1Т; 1Т= и 1Т„ ;

к-1

2)отклики ИЛМ на доступных выходах ячейки в Ат идентичны

гкликам на наблюдаемых выходах соответствующей ячейки в Аи, а е«ячеечные состояния в обоих ИЛМ взаимно однозначно соответ-твуют друг другу. Если эти состояния наблюдаемы, то они иден-ичны между собой.

Как показано на рис.1, процедура синтеза проверяющей оследовательности 1Т основана на свойствах I-отличительных екторов (ЮтЮ и множеств I- отличительных векторов СМЮтВ). ля пары состояний ^ б Гк, в ячейке Р И-ячеечной ИЛМ можно пределить вектор входных символов 10тВкСг^,2^Н-Р), подаваемый [а входные полюса ячеек от Р+1-ой до М-ой, с помощью которого южно однозначно отличить по откликам на выходах ИЛМ состояние от состоянии 2^ МЮтВ^г^.Н-РЭ- множество I- отличительных )екторов, с помощью которого можно однозначно отличить z^ от юех других состоянии в Гк ; т. е.

М10тВкСг^,Н-Р)=<10тВк(2|^,Н-Р),у ъ^у еГк),

МЮтВ^Сг! ,1ЬР )

21

1 2.1

—» с, • ъ 1 Ср

Рис.1. I-тестируемые ИЛМ.

Тогла имеет место следующее утверждение. Теорема 2. 1Т является множеством тестов для Ат в условиях МКН, если у Рк множество I-отличительных векторов (М10тВкЗ формируется по следующей методике: для любой ячейки Р выбирается только одна пара векторов ЮтВк(2^^ ,Н-Р), ЮтВ^г^г^.Н-Р) для каждой пары состояний е Гк.

Из теоремы 2 следует, что для проверки переходов в Гк используются только I-отличительные векторы, число которых не превышает ЬКСЬК~1Э, где количество состояний вТк.

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

минимизации длины проверяющей последовательности для МКН.

Дальнейшее развите методов ТД для ИЛМ обусловлено совмещением свойств, присущих 1-тетстируемым ИЛМ и С-тестируемы) ИЛМ. ИЛМ является С- тестируемой, если она может быть проверена постоянным числом тестовых векторов независимо от размеро! ИЛМ. ИЛМ является С1-тестируемой, если она являете* I-тестируемой и длина проверяющей последовательности не зависит от размеров ИЛМ. ,

В работе предложена процедура синтеза множества тестов (СП) для С1- тестируемых ИЛМ в условиях МКН. Процедура синтеза СП основана на свойствах I-отличительных последовательностей СЮтП^.) и множеств I-отличительных последовательностей смютгу.

Для пары состояний можно определить ЮтП^г^гр

как последовательность входных символов, подаваемую на входы автомата, представленного таблицей переходов-выходов Г^, с помощью которой можно однозначно отличить состояние г^ от состояния Различие между ЮтВк и 10тПк заключается в том, что процедура синтеза ЮтПк определяется только ТПВ ячейки и не зависит от ее относительного положения в ИЛМ, поскольку в этом случае все ячейки идентичны.

,Достоинство процедуры С1- тестирования для МКН заключается в том, что С1Т может быть сгенерировано путем циклического сдвига одного или нескольких тестовых векторов, при этом количество ячеек в ИЛМ может быть переменным. Способ проверки откликов аналогичен случаю I- тестирования.

Пусть и: Сг]Ь=(5С2а,ха) ^^(г^Хд)) - переход в Гк, тогда для этого перехода С1ТС1о) определяется в виде

С1ТС1о)={С1Трио) * гъУ;

где СПрСи)- последовательность, проверяющая таблицу . переходов-выходов Гк с начальным состоянием 2&: СГк/га), такая, что в свою очередь последовательность С1ТрС1о) определяется формулой

С1ТрС1о-)=С.ха,10тПкС2ь,7 ) ДП)* ;

где СБ)*= 8,8,3,..,; ХП-переводящая последовательность, которая переводит автомат обратно в Гк/га; ЮтП^г^,е М10тПк(гь ).

Приложение С1Т(1о) и его |С1Т(1о)|-1 сдвинутых версий

Обеспечивает проверку и в каждой ячейке ИЛМ. Аналогичная процедура справедлива для всех переходов в Р. В работе предложен метод синтеза М10тПк для условий МКН.

Дальнейшее развитие методов ТД ориентировано на разработку средств встроенного ТД. К таким методам относится Р1-тестирование. При Р1-тестировании ИЛМ разбивается на несколько логических блоков с одинаковым числом ячеек в каждом. Блоки ячеек порождают одинаковые между собой отклики на Р1 тестовые векторы, хотя отклики ячеек внутри определенного блока необязательно одинаковы между собой. Количество тестовых векторов не зависит от числа ячеек в ИЛМ Срис, 2.). Действительно, если РКиЭ - Р1-тестовое множество для проверки перехода С1о): Р1(1о)=<Р1рС1о), у т0 Р1 рС^о3-последовательность, про-

веряющая переход йСга,ха)=г^, представляется.в виде

Р1рС1о)=Сха,0тПСг|э,гр) ,ХПП1 )*,

где (5)*= 5,8,5,...; ХПГЬ- переводящая последовательность Спереводит ячейку в начальное состояние 2а после приложения последовательности ОтПСг^,2р) 3.

блок 1 блок 2

0т1Кгь,гр)+ХПт' ОтПСгь.грЗ+ХПш

Рис 2. Р1-тестируемые ИЛМ со встроенной схемой диагностирования

Длина переводящей последовательности ХПШ выбирается так, чтобы длина проверяющей последовательности Р1р(и)для всех состояний автоматной модели ячейки была равна числу ячеек в блоке ИЛМ. Переход 1о проверяется во всех ячейках ИЛМ, если приложить

PIpCto) и все его версии С |PIp(to)-l |) ко входам ИЛМ. Как видно из рис. 2. достоинство предложенного метода заключается в простоте генерации тестовых векторов и проверки откликов.

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

В третьей главе предлагаются методы синтеза тестов для двумерных ИЛМ C2D ИЛМ) для МКН. В работе предложены достаточные условия тестирования ИЛМ тестами постоянной длины, не зависящей от числа ячеек в 2D ИЛМ, т. е. предложены достаточные условия С-тестируемости 2D ИЛМ для обнаружения кратных неисправностей сети.

В общем случае 2D ИЛМ могут иметь ортогональную или гексагональную структуру и, соответственно, два или три направления распространения сигналов: СХД,2). В работе предложены процедуры синтеза тестов для следующих трех случаев.

Случай С1: ортогональные ИЛМ. Показано, что верхняя граница числа тестовых векторов составляет (m+l)Cn+l)(4mn), где |Xl=m;|Y|=n - число состояний в направлениях X и Т, соответственно. Предложений метод отличается от известных способностью обнаружения кратных неисправностей, при этом получаемая верхняя граница длины проверяющей последовательности меньше аналогичных границ, полученных ранее.

Случай С2: гексагональные ИЛМ. Метод основан на использовании свойств гамильтоновых циклов в графе переходов автоматной модели ячейки 2D ИЛМ. Предложено ввести два дополнительных состояния в направлениях X и Y. Верхняя граница числа тестовых векторов для МКН в этом случае составляет

2LCш+2)С п+2)С тахС2т,En)+1)С га+п+2) ;

где |Z|=L - число состояний в направлении Z.

Случай СЗ: Метод может использоваться для диагностирования гексагональных ИЛМ, в которых составляющие ее ячейки выполняют функции перестановок типа совершенной тасовки CPS) и стандартной транспозиции CTR).

В работе доказано, что минимальная верхняя граница пере-

водящей последовательности для автоматной модели ячейки обладающей свойствами РБ и Тй составляет 21д2|X(-1, где |Х|-число состояний автомата.

верхняя граница длины проверяющей последовательности для МКН составляет

2ЬС т+2) С п+2)С тахС 41 д2п-2,41д2т-2) +Ю С т+п+2).

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

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

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

В работе рассмотрены требования к алгоритмам,' реализуемым в С-СП. Требования обусловлены следующими факторами:

-обеспечение требуемого уровня распараллеливания вычислений, а следовательно, производительности С-СП;

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

Центральным в предложенной процедуре синтеза С-СП является понятие индексного пространства СИП). ИП является 5 мерным гиперкубом с длиной, составляющей N. если для любого вектора 1= [ 11"д . ; I е ИП; 1< 1 <Н ; j= 1,... Тогда можно представить регулярный итеративный алгоритм, реализуемый 'в С-СП, в виде множества переменных \/={Х1 .ХдДд... Ху>, которые принимают определенные значения во всех координатах ИП. Значение перемен-, ной X; может быть наперед заданным или результатом некоторой

функции вида

Х^1) = Г1^СХ1(1-Р11),Х1(1-П12),...,ХуС1-Оу1)1ХуС1-Оу2)-_) С1)

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

Вектор индексного смещения Р^ позволяет определить координату индексного пространства (1-б^р, в которой определена Х^, относительно координаты СI), в которой вычисляется Х^ Процесс синтеза логической структуры С-СП заключается в отображении регулярного итеративного алгортитма на однородный п- мерный массив ПЭ,соединенных между собой локальными связями. Каждому ПЭ соответствует координата в п-мерном процессорном пространстве СПП).'

Пространством итерации <Ш назовем подпространство индексного пространства, которое является дополнением ПП и определяет однозначное соответствие координат индексного и процессорного пространств.

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

Индексное пространство, на котором определен Ь-тый дублирующий алгоритм определяется множеством координат 1ехь:

1нхи_ Кзс I + Уехь, у I е ИП; С2)

где Кэс- линейный оператор преобразования векторных пространств; Кэ=[кзС| ,кгса,... .квсэ]; кгс,)- целое положительное число;

Уехь - вектор индексного смещения Ь-того дублирующего алгоритма от основного алгоритма;

1бс= Кбс I - координаты масштабированного индексного пространства СМИП), где определен основной алгоритм.

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

выработать признак корректности вычислений СПкор):

ПК0РПЕХ)= Г0;СХ,С1*а)= Х^1ЕХ)) ^

(Д^СТгс^СГЕх:)) .

Нижеследующее утверждение используется для определения условий синтеза структуры С-СП.

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

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

ит15С; ит1ЕХ1^ит( 1ЕС+УЕХО ; .

Тт15С; Тт1ехь=ТтС1зс+УЕХ1Л. С4)

Поскольку вектор индексного смещения указывает на

передачу значения переменной в ИП, то в координатах МИП вектор индексного смещения В-1 к&с определяется в виде В ^ Кзс 0 к

В этом случае компоненты вектора индексного • смещения на процессорном пространстве Ссг,кзс) и на пространстве итерации (р1*^) определяются в виде

Л к Т Л): Зк Т л к

« 5С=Т С 5С Р 5С=и С „(Г

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

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

динаты ССКэс I) для основного алгоритма и СКэс 1+Уех) для дублирующего алгоритма), в которых определены эти алгоритмы, т.е.

иХ^С1зс))= Сч^Юзс 1)+Г^ ; 1С^С1ех))= Сят,СКзс1+УЕХ))+^; ' КПкорСIех)) =С, Iех) +Псор; у ^еУ; . С5)

где t(XjCIsc)), КХ^1ех))- моменты времени, в которых значение переменной Xj определено в основном и дублирующем алгоритмах соответственно;

транспонирований вектор постоянных коеффициентов;

Г^,Гкор- произвольные функции координат МИЛ, представленные полиномиальной аппроксимацией.

Обозначим, через Ь^ промежуток времени, необходимый для вычисления значений Х^ если известен момент времени, в котором определено Х^. Тогда для основного и дублирующего алгоритма справедливо, что

иХ^ЬгОЫСХ^азстЬ^

КХ^ГехЗЭЧСХ^СТЕХЗЭЭД^ . . С6)

где 1СХ^С1зс)3, КХ^СГех))- моменты времени, в которых значение переменной Х^ определено в основном и дублирующем алгоритмах соответственно.

В работе показано, что всегда можно определить из

характеристик элементов используемой элементной базы..

Решение системы неравенств (6) для всех переменных Xj и признаков корректности определяет моменты времени, в которых определены значения всех переменных и признаков корректности основного и дублирующих алгоритмов согласно уравнениям С 5), то есть определяется временное расписание С-СП.

Любое иэ уравнений (5) можно записать в виде

^С1)) = [№-' №~г... 1] ^ . (7)

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

С1^1)т), т.е.

гапкС1^)=гапкС1^ ит). (8)

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

1.Пусть зад<ж регулярный итеративный алгоритм. Определить размерность 5 индексного пространства, на котором он определен, а также порядок (с) длины критического пути алгоритма 0(№).

2. Выбрать размерность (I) процессорного пространства и размерность пространства итераций Си) так, чтобы и и>с.

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

4. Определить коеффициент масштабирования К„с. Его компоненты определяются исходя из того, сколько дублирующих алгоритмов будут выполняться на С-СП . Если п.- количество совмещаемых алгоритмов С включая основной), то хотя бы один из компонентов Кзс должен быть больше, чем па. Если осуществляется синтез структуры С-СП только со связями между ближайшими процессорными модулями, то необходимо масштабировать все размерности индексного пространства одинаковыми' коеффициентами к5С1.

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

6. Исходя из условий совместимости пространства итераций I) и временного расписания, определить и, а зат^м процессорное пространство Т, ортогональное и.

7.Отобразить координаты основного алгоритма на и и Т .

8. Определить компоненты каждого из ' векторов смещения дублирующих алгоритмов на процессорном пространстве (ТтЕХ1) и на пространстве итераций (итЕХ1). Эти компоненты соответствуют пространственно-временным характеристикам сигналов, используемых при вычислении признаков корректности'. Затем определяется каждый из векторов смещения дублирующих алгоритмов путем

решения системы уравнений :

ит V = ит

ЕХ1 ЕХ1

Тт V = Тт ЕХ1 ЕХ1

9.Определить временное расписание основного и дублирующих алгоритмов .

10.Отобразить координаты дублирующих алгоритмов на Т и U.

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

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

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

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

Таблица 1

Состояние ' П „„„ кир Неисправный ПЭ

Сравнение 1. ПЭ Сравнение 2.ПЭ4 +

1. Совпадение 2. Несовпадение 3. Несовпадение Совпадение Совпадение -Несовпадение Нет неисправностей ПЭ. ю' х 1 +i

В приложениях предложена логическая структура и порядок

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

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

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

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

1) Предложено три метода синтеза тестов для обнаружения кратных функциональных неисправностей в одномерных ИЛМ:

а) I-тестирование: правильность откликов ИЛМ на тестовые векторы можно проверить простой схемой равнозначности, поскольку отклики ячеек идентичны между собой;

.6) С1-тестирование: позволяет синтезировать тестовые множества, размер которых, не зависит от числа ячеек в проверяемой одномерной ИЛМ и при зтом сохраняет простоту проверки откликов ИЛМ на тестовые векторы;

в) Р1-тестирование: позволяет упростить процесс генерации тестовых векторов (благодоря свойству С-тестируемости ИЛМ), и простоту проверки откликов, хотя размер сгенерированного тестового множества, как правило, больше, чем при С-тестируемости.

2)Разработан инженерный подход к синтезу встроенных средств автономного тестового диагностирования, основанный на методах С1 и Р1-тестирования, для обнаружения кратных неисправностей.

ЗШоказано, что новые методы синтеза I, С1, Р1 тестовых множеств для диагностирования одномерных однонаправленных ИЛМ также можно применить для одномерных двунаправленных ИЛМ.

4)Предложен метод синтеза ортогональных С-тестируемых ИЛМ и процедура синтеза тестов для них. Получена оценка верхней границы длины С-тестового множества и доказано, что она выгодно отличается от ранее известных результатов.

5) Предложен метод синтеза С- тестируемых гексагональных ИЛМ и процедура синтеза тестов для таких ИЛМ.

6) Предложен метод синтеза С-тестируеыых двумерных ИЛМ, основанный на свойствах подстановок типа совершенной тасовки и стандартной транспозиции. Показанно, что верхняя граница числа тестовых векторов, полученных этими методами, существенно меньше, чем оценки полученные для других типов С-тестируемых двумерных ИЛМ.

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

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

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

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

11. Предложены стуктуры и расчитан порядок вычислений трех С-СП, предназначенных для решения следующих задач:

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

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

1. Дербунович Л.В. Нуньес С., Метод синтеза проверяющих тестов для однородных перепрограмнруемых логических схем/ Тезисы докл. республ. н. т. конф. "Микропроцессорные системы связи нд железнодорожном транспорте", киев, 1990 г. с. 6-7.

2. Нуньес С. Обнаружение кратных неисправностей в итеративных логических матрицах / Тезисы докл. республ. н. т. конф. "Функционально ориентированные вычислительные системы ", г. Алушта, Окт. 1990г. с. 169.