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

а

005042394

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

Выборной Пётр Владимирович

ДИАГНОСТИКА ПАРАЛЛЕЛЬНЫХ МАГИСТРАЛЕЙ И ПАМЯТИ

БОРТОВЫХ ЦВМ

Специальность 05.13.15 -«Вычислительные машины, комплексы и компьютерные сети»

АВТОРЕФЕРАТ

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

1 п-ПК

Москва —

2012

005042394

Работа выполнена на кафедре «Вычислительные машины, системы и сети» Московского авиационного института (национального исследовательского университета).

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

д.т.н., проф. Гаврилин Б.Н.

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

Аксёнова Г.П., к.т.н., с.н.с. лаборатории технической диагностики ИПУ им. В.А. Трапезникова РАН

Александров А.Е., д.т.н., проф. кафедры «Персональные компьютеры и сети» МГУПИ

Ведущая организация: ФГУП «Научно-исследовательский институт авиационных систем» (НИИАС)

Защита состоится ¿¿¿¿г^е? 2012 г. в мин, на заседании

диссертационного совета Д212.125.01 Московского Авиационного института (национального исследовательского университета) по адресу: 125993, г.Москва, А-80, ГСП-3, Волоколамское ш., д.4, зал заседаний Ученого совета.

С диссертацией можно ознакомиться в библиотеке МАИ. Автореферат разослан «2012 г.

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

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

к.т.н.

Корнеенкова А.В.

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

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

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

Проверки, которые производятся после изготовления вычислительных модулей БЦВМ и в ходе их испытаний, показали, что от 70 до 90% (в зависимости от типа модуля) всех неисправностей относятся к вычислительному ядру (ВЯ). Подавляющее большинство дефектов В Я, порядка 85-90%, приходится на связи микропроцессора (МП) с микросхемами внешней памяти - структуры демультиплексированных параллельных магистралей (ДПМ). Второе по численности место занимают дефекты кристаллов оперативной памяти, составляя в среднем чуть более 10%; небольшой остаток в 1-2% приходится на постоянную память.

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

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

Вопросы тестирования кристаллов памяти в целом разработаны достаточно глубоко и всесторонне, обеспечивая эффективное обнаружение т.н. классических дефектов. Однако существующие методы обнаружения кодочувствительных дефектов (PSF - pattern sensitive fault) не обеспечивают приемлемой для этапов наладки и испытаний полноты покрытия. Данный факт обусловлен критериями построения этих тестов, которые ориентированы на применение в аппаратуре самотестирования и должны удовлетворять довольно жёстким временным ограничениям, а также объективной сложностью обнаружения этих дефектов. Очевидно, что недостаточная степень выявления кодочувствительных дефектов на этапе испытаний существенно снижает вероятность безотказной работы БЦВМ в условиях эксплуатации.

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

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

Основные результаты работы, выносимые на защиту:

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

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

3) Разработан метод генерации шаблонов активации для нередуцированных моделей активных и пассивных кодочувствительных неисправностей PSF3 и PSF4, обеспечивающий их 100%-ное покрытие. Дополнение классических маршевых тестов памяти тестами, составленными по этому методу, позволило существенно увеличить полноту проверки кристаллов SRAM.

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

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

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

Научная новизна работы. Новыми результатами работы являются алгоритм диагностики ДПМ с максимальной глубиной разбиения неисправных состояний и метод обнаружения кодочувствительных дефектов, обладающий 100%-ным покрытием для дефектов третьего и четвёртого порядков (PSF3 и PSF4). Более детально они представляются следующим образом:

1) при построении алгоритма диагностики ДПМ применён сигнально-ориентированный подход, подразумевающий нацеленность элементарных проверок на определение состояния магистрального сигнала или группы сигналов;

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

3) введены логически неустойчивые типы поведения в модели неисправной системы для повышения достоверности диагноза;

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

5) разработаны методы комбинирования неисправных разрядов, на основе которых осуществляется локализация обрывов и замыканий на шинах адреса и данных;

6) предложены шаблоны тестового заполнения для ROM, как в варианте полного объёма, так и в свободных областях, позволяющие выполнять исчерпывающую диагностику связей с МП без необходимости перезаписи;

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

8) на основе принципа чётности позиции, использования регулярных преобразовании и теоремы разработан и обоснован метод прямой генерации активирующих шаблонов для нередуцированных моделей PSF3 и PSF4.

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

Алгоритмическая основа магистральных тестов допускает их применение для любой элементной базы, гарантирует нечувствительность к разбросу характеристик драйверов и приёмников сигналов и обеспечивает получение достоверных результатов при произвольных сочетаниях дефектов и наличии логической неустойчивости. Применение бит-ориентированных маршевых тестов, разработанных в работе тестов для PSF3/PSF4, а также тестов переключения адреса и насыщения позволило существенно увеличить полноту проверки кристаллов SRAM. Разработанный комплекс диагностики, наряду со стандартной наладкой, позволяет проводить тестирование памяти при испытаниях модулей в специальных условиях, во время которых проявляется значительная часть дефектов. Комплекс обеспечивает простоту организации, управляемость и наблюдаемость процесса диагностирования. Схемотехнические решения ЦВМ комплекса и её программное обеспечение являются перспективными для использования в задачах диагностики интерфейсных узлов БЦВМ, полунатурного моделирования и отладки рабочих программ, а также в качестве монитора мультиплексированной магистрали.

Апробация работы. Результаты работы представлялись на конференциях молодых учёных и специалистов ГосНИИП (2006 г., 2008 г.), конференциях Московского отделения МОО «Академия навигации и управления движением» (г.Москва, ЦНИИАГ, 2009 г., 2011 г.), конференции «Люльевские чтения» (г. Свердловск, ОКБ «Новатор», 2010 г.).

Публикации. По теме диссертации опубликовано 2 научные работы в журналах, рекомендованных ВАК РФ; результаты работы также нашли отражение в пояснительных записках к двум техническим проектам (ГосНИИП).

Структура и объём работы. Диссертация состоит из введения, трёх глав, заключения, списка литературы и трёх приложений, оформленных в виде отдельной книги. Основной текст изложен на 185-и страницах и содержит 33 рисунка и 26 таблиц. Список источников включает 63 наименования.

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

Рис.1. Обобщённая функциональная схема вычислительного модуля БЦВМ Детально рассматриваются магистральные циклы обмена процессора с памятью, приводятся временные диаграммы сигналов ДПМ (рис.2).

О.Огге

ЭОО.Опв

БОО.Опг

Рис.2. Временные диаграммы магистральных сигналов (геаё-геас1-\¥п1е) Функциональная классификация сигналов. Все сигналы диагностируемого модуля разбиваются на пять функциональных групп: 1) Св - линии питания микросхем подсистемы и образующие по форме временной диаграммы шесть подгрупп сигналы управления памятью, к которым относятся процессорные стробы, тактовая частота магистрали, управляющие адресные разряды, биты регистров 1/0 доступа к памяти МАСВ и производные перечисленных сигналов; 2) А - адресные разряды магистральной шины, участвующие в физической адресации ячеек памяти; 3) О - линии данных; 4) Р — внешние сигналы постоянного уровня; 5) Р - периодические не синхронизированные с СЬКОШ" внешние сигналы, производные непроцессорных генераторов, если они есть в устройстве (Ай на рис.1.). Группы 1, 2 и 3 образуют магистральные сигналы (I), группы 4 и 5 - внешние (Е).

Физическими дефектами исследуемого объекта являются: замыкания магистральных сигналов между собой (8Н-11-12-...) или со сторонними сигналами (8Н-1-Е), обрывы сигнальных линий и отсутствие питания микросхем памяти и управляющей логики (ВК-1), общие для подсистемы дефекты логических элементов МСЬС и сигнальных трактов (ЗРИ-Св), дефекты переключения сигналов (5№Т-1), вызванные высоким сопротивлением

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

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

Описывается типовая схема вычислительного ядра модуля (рис.1).

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

Класс образуется одним или несколькими видами неисправностей. Вид есть типовое искажение формы и уровней определённых сигналов, в ряде случаев сопровождающееся и нарушением работы электронных схем, для которых эти сигналы являются входными. Например, виды SH-WE-A[x], SH-RD-A[x], SH-CE-Afx], SH-DS-A[x] и SH-CLKOUT-A[x] составляют класс SH-CS-A. Искажение уровней вызывается либо дефектами сигнальных линий, либо дефектами элементов магистральной логики. Созданная функциональная классификация в основном совпадает с разбиением видов дефектов на ранжированные группы и характеризует влияние дефектов на обмены с памятью с точки зрения процессора и, следовательно, способ их обнаружения.

Логически неустойчивое поведение. В работах по диагностике межкомпонентных связей в качестве описания одиночных дефектов используются детерминированные логические модели замыканий для двух сигналов. Известно несколько таких моделей, а в качестве рабочих, как правило, применяются монтажное И (WAND) или монтажное ИЛИ (WOR); обрывы считаются константной лог.1 либо лог.О. Не ставя под сомнение следующего из этих моделей общего принципа обнаружения замыканий посредством подачи парафазных наборов, в диссертационной работе было показано, что совокупность этих моделей не является достаточной для отражения поведения замкнутых сигналов.

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

HMNV

ai! Too-в......... кг ¡.....СТО.......Irj 20ónci a; ki \ i.

Рис.3. Замыкание адресных линий с неопределённым уровнем (канал К1 -тёмный), приводящее к попеременной коммутации разных ячеек SRAM на разряд D[n] шины данных (канал К2 - светлый)

Техника проверок объектов с детерминированным поведением заключается в установлении правильности выполнения единичной операции. На основе рассмотрения и анализа реальных замыканий был определён принцип построения проверок для объектов с логической неустойчивостью: критерием исправности сигнала должно быть отсутствие неправильных результатов при многократном повторении операции с инверсными входными

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

50 (suppressing 0) - на сигнальных линиях устанавливается потенциал, всегда воспринимающийся приёмником при данной логической конфигурации сигналов как устойчивый лог.О (может быть и выше стандартного порогового уровня UвхОтах).

51 (supressing 1) - устанавливается потенциал \]зам, всегда воспринимаемый приёмником как устойчивая лог.1 (может быть и ниже стандартного Uexlmiri).

INDTL (indetermined level) - результирующий потенциал приёмником воспринимается неустойчиво, то как лог.1, то как лог.О в течение одного цикла или в разных циклах.

Аналогичные логические типы были введены и для описания обрывов.

Модели неисправностей. Пусть Е - множество технических состояний подсистемы «магистраль-память», которое включает исправное состояние Ео и подмножество из всех остальных, неисправных состояний Ef (i=],2,...,|C|), где С - множество всех одиночных неисправностей (простых дефектов) S и их возможных сочетаний. Тогда Z=4'(X,Yn.i,n) -некоторая форма представления передаточной функции исправного дискретного последовательностного объекта диагностики (Е0), где X - набор входных переменных в цикле n, Y„.i - значение внутренних переменных после записи в элементы памяти в цикле п-1, Z - выходные функции в цикле п после определённого времени установки выходов. Объект, находящийся в ¡-неисправном состоянии (Ej), реализует передаточную функцию Zp'PiiX.Yn-i.n). Функция Zi с входным набором X, и значением внутренних переменных Yn-i описывает элементарную проверку яь а используемые выходные переменные, или результат проверки, принято обозначать R,,.

При проверке магистрали подсистема в большинстве случаев может быть представлена как квазикомбинационное устройство. Для этого передаточная функция (модель объекта) должна представлять не единичное обращение, а пару совмещённых операций записи и чтения. Наличие инициализирующих записей выражает Yn.| (содержимое ячеек SRAM) через входные переменные X=(A,Dp), и каждая элементарная проверка описывается функцией без участия членов Yn.i и п.

Очевидно, что передаточной функцией исправной подсистемы будут тождества:

Dr[A](n)=Dp[A](i=max(0, п-1)) при обращении к SRAM,

Dr[A](n)=Dm[A] при обращении к ROM,

где Dr[A](n) - данные, читаемые процессором в n-цикле из адреса A; Dp[A](i=max(0, п-1)) - данные, выставляемые процессором на магистраль в i-цикле записи в память по адресу А, ¡-цикл является последней записью по адресу A; Dm[A] - данные в ячейке ROM с адресом А.

При наличии неисправности связей Sj подсистема функционирует в соответствии с одной из передаточных функций 4V Соответствующие ей функции элементарных проверок Dr=0,(A,Dp) с необходимыми значениями А и Dp (об их выборе см. далее) составляются в виде синтаксических диаграмм записи-чтения. Для каждого вида магистральных дефектов составляется несколько таких диаграмм, для каждого логического типа замыкания и набора (A,Dp). Синтаксические диаграммы являются текстовым представлением поведения объекта, которое получается, если вместо временных диаграмм исправных сигналов (рис. 2) подставить диаграмму при их замыкании, и проследить работу памяти в этих условиях; постановка физических экспериментов позволила проверить, уточнить и в ряде случаев дополнить модели дефектов. Выглядит этот способ представления следующим образом (для примера взят вид замыкания SH-WE-A[x], логического типа S1, из класса SH-A-CS):

A(0000)Dp[0000] WR + Aw[x]=0 mem(0000).-[0000] RD + Ar[x]=l mem(0]00)— [PPPP] RES=CNE, где

A(0000)Dp[0000] - входные наборы адреса А(в круглых скобках) и данных Dp[ß квадратных скобках], условные позиции неисправных разрядов А и/или D выделены подчёркиванием

WR(RD) - маркеры начала описания записи(чтения), атрибуты { + | - | wda | wdd | ose | asw | atd} - обращение происходит нормально | стробирование подавлено | запись по фронту установки данных | запись по фронту снятия данных | отключающееся чтение | самопереключение адреса | изменение логического состояния разряда адреса при выставлении данных памятью

Aw[x]=0 - фактическое значение неисправных разрядов в цикле записи, символ "/", когда присутствует, разделяет альтернативные варианты

mem(0000)<— [0000] - изменение содержимого ячеек памяти в цикле записи Аг[х]=1- фактическое значение неисправных разрядов в цикле чтения в момент фиксации процессором состояния магистральной шины данных

mem(0100)—»[РРРР] - ячейки, из которых фактически производится чтение, и данные получаемые процессором Dr [в квадратных скобках], являющиеся результатом Ru элементарной проверки. Значением данных, кроме определённого числа, может быть: ХХХХ - неопределённый результат чтения; РРРР (previous value) - предыдущее значение в ячейке, не изменяемое данной элементарной проверкой

RES=CNE - атрибуты выходных данных, могут быть следующими: {EQ|NE|CNE|LP} -Dn=Dp I Dr*Dp безусловно ] Dr*Dp условно | значение низкой вероятности.

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

Методика разбиений. Если множество допустимых одиночных неисправностей объекта S, а множество их сочетаний - С (ScC), то фактическая j-неисправность подсистемы в общем случае представляется Cj=Sk+S|+...Sp, причём на дефекты Sk...Sp не налагается ограничений по числу и видовой принадлежности. Особенностью систем с неоднородными сигналами является то, что детектирующие проверки для некоторого подмножества неисправностей могут быть осуществлены только при отсутствии некоторых других их подмножеств. Для выбора последовательности обнаружения неисправностей при наличии произвольных их сочетаний в работе предложен принцип разбиения на ранжированные подмножества и маскирования дефектов подчинённых рангов.

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

Самым старшим рангом является первый, для него все остальные подмножества, имеющие ранг t>l, являются подчинёнными. Критерием включения простого дефекта Si в подмножество старшего ранга Ft из исходного F', ранг которого принимается равным t+1, является возможность физически осуществить и однозначно интерпретировать такую элементарную проверку, которая при наличии любых дефектов ранга t+1 даст результат Rt (ответ исправного объекта) при отсутствии Si и Ru*Rt - при его наличии. Сначала берется исходное множество F-S, t=l и выделяется Fi, затем t=2, F-S-Fj, и уже из нового F' выделяется группа дефектов F2 и так далее вплоть до последнего класса или вида дефектов. В результате применения этой процедуры исходное множество было разделено на 13 подмножеств F, (t=l,2,...13), так, что S=F,UF2U... UF,3. Каждому подмножеству F, соответствует свой этап теста, предназначенный для обнаружения и определения дефектов только из этого подмножества, называемых целевыми дефектами. Этапы теста выполняются поочерёдно в ранговом порядке соответствующих подмножеств, начиная с самого старшего и кончая младшим.

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

алгоритма магистрального теста для систем, содержащих SRAM и ROM. Тест состоит из основной (детектирующей) последовательности и локализующих процедур. Основная тестовая последовательность состоит из детектирующих проверок для каждого подмножества Ft, это путь по графу алгоритма диагноза от состояния «полностью неопределённо» до «исправно». Локализующие процедуры выполняют окончательное разделение и определение неисправностей внутри целевого подмножества, обнаруженного проверками основной последовательности, и являются составными частями соответствующих этапов теста. Алгоритмы проверок представлены в виде Фортран-подобного псевдокода.

Выбор входных векторов А и Dp как для детектирования Ft, так и для определения всех простых дефектов S,eF, является основной задачей, решаемой при построении каждого этапа, или фазы теста. Рассмотрение каждого из 13-ти этапов теста начинается с анализа моделей целевых дефектов, на основе которого определяются алгоритм и тестовые вектора детектирующей проверки. В соответствии с принципом ранжированных разбиений выбираются такие вектора, которые при наличии любых неисправностей F' из возможных на данной фазе теста позволят выделить дефекты, относящиеся к подмножеству Ft, или сделать заключение об отсутствии таких дефектов.

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

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

На основе метода комбинирования было составлено три разных алгоритма локализации для следующих групп дефектов: 1) SH-A-D, 2) SH-A-A, BR-A, SH-A-F, 3) SH-D-D.

Задача этапов проверки связей с постоянной памятью заключается главным образом в установлении целостности сигнальных линий, поскольку большинство замыканий элиминируется предыдущими этапами теста. Была разработана схема области тестового заполнения ROM. Первые две четверти области заполняются инверсными шаблонами и предназначены для проверок сигналов D и CS. Верхняя её половина содержит адресный код для обнаружения неисправностей линий А.

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

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

Рассматриваются электрическая схема SRAM и модели классических функциональных дефектов, статических - залипания SAF, обрыва линии SOF, перехода TF, взаимовлияния CF, дешифратора адреса ADF и динамических - удержания данных DRF, восстановления усилителей записи/чтения и переключения адреса. Описание сопровождается указанием возможных физических причин дефекта, а также операций, необходимых для его детектирования.

Наиболее эффективным средством тестирования памяти являются маршевые тесты, сочетающие высокую покрывающую способность в отношении дефектов классических типов и низкую сложность порядка N (N - количество ячеек массива). Маршевый тест состоит из последовательности маршевых элементов. Маршевый элемент есть некоторая последовательность операций чтения и/или записи, применяемая к каждой ячейке массива перед тем, как будет осуществлён переход к следующей ячейке. Перебор ячеек может производиться в одном из двух порядков следования адресов: прямом или обратном. Прямая последовательность перебора адресов обозначается значком обратный - 1. Чаще всего применяются наиболее простые в реализации счётчиковые последовательности, прямая (от О до N-1) и реверсивная (от N-1 до 0). Когда порядок перебора ячеек значения не имеет, перед маршевым элементом ставится значок Операции чтения ожидаемого значения е принято обозначать те, записи - we, е е {0,1}.

Для обнаружения тех или иных дефектов, в том числе и в случаях, когда проявление одного дефекта может маскироваться наличием другого, маршевый тест должен содержать элементы с определённой последовательностью операций. Эти вопросы изложены по основополагающим в данной теме работам. Так, например, тест обнаруживает все ADF при наличии двух маршевых элементов: |(re,...,we) и 4(re,...,we). Первый элемент читает значение е из ячейки 0, затем записывает инверсное значение ё в ячейку 0, читает значение е из ячейки 1, затем записывает ё в ячейку 1, ... , читает е из ячейки N-1, записывает ё в ячейку N-1. Второй элемент выполняет аналогичные операции с инверсными значениями, но в обратном порядке.

Были проанализированы наиболее известные маршевые тесты и показано, что среди них существуют такие, которые обеспечивают полное покрытие для всех типов статических дефектов, включая и случаи связанных. В качестве примера можно привести тест March В длиной 17N:

March В: {J(vvO); T(r0,wl,rl,w0,r0,wl); t(rl,vv0,wl); I(rl,w0,wl,w0); |(rO,wl,wO)}.

MO Ml M2 M3 M4

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

Наиболее труднообнаруживаемым типом дефектов SRAM являются кодочувствительные неисправности {pattern sensitive faults - PSF), вовлекающие более двух ячеек массива (т.н. неклассические дефекты). Для подобных дефектов поведение одной ячейки зависит от содержимого или логических переходов соседних ячеек. Выделяют базовую ячейку (base cell), которая является аналогом жертвы в классических дефектах взаимовлияния CF, и соседние ячейки (neighborhood cells), выступающие в роли агрессоров. Если принимается, что их местоположение может быть произвольными, то говорят о нередуцированной модели PSF. Если допускается, что массив представляет собой одну прямоугольную матрицу, последовательность расположения ячеек в которой соответствует их адресам, и в дефекте могут участвовать только физически смежные ячейки, то говорят о редуцированной модели.

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

В зависимости от эффекта влияния на базовую ячейку большинство исследователей выделяет два класса кодочувствительных дефектов: пассивные (passive PSF - PPSF), когда состояние базовой ячейки не может быть изменено для определённого кода в соседних ячейках, и активные (active PSF - APSF), когда базовая ячейка изменяет своё состояние при наличии определённого кода в соседних ячейках и изменении состояния на противоположное в одной из них. В качестве объекта исследования обычно рассматриваются дефекты PPSFk, где к обозначает количество произвольных ячеек массива емкостью N бит, участвующих в неисправности, причём одна из них является базовой. Основной проблемой обнаружения кодочувствительных дефектов является генерация наборов активации дефекта для всех возможных конфигураций и значений соседних ячеек, и предельное покрытие любого метода определяется отношением количества наборов активации дефекта, генерируемых тестом, к общему числу возможных наборов. В работе были рассмотрены четыре существующих метода обнаружения этих дефектов, три из них используют нередуцированные модели, а один - редуцированные. Все они используют многократные проходы маршевых тестов.

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

Однократный прохода теста March С- даёт следующие покрытия для PPSFk: для к=3 -50,0%, для к=4 - 25,0% и для к=5 - 12,5%. Для к=5 двухкратный проход даёт 24,5%, трёхкратный - 32,9%, N-кратный - 50,0%. Существует методический предел, достигаемый при N-кратном использовании теста: нельзя достигнуть 100%-ого покрытия для кодочувствительных дефектов с к>3. Следует отметить, что это предельное покрытие на практике не может быть реализовано, так как длина теста приобретает порядок N .

Альтернативным подходом является многократное тестирование с различными адресными последовательностями. Под адресной последовательностью понимается упорядоченная последовательность максимальной длины из m-разрядных двоичных векторов Aü^bm-ibm. гЬт-з-.ЬгЬ^о, где bie{0,l}, ie{0,l,2,...,m-l), a je{0,1,2,...,2го"1}, однократно принимающих всевозможные значения {0,1,2,..„2т_1}. В качестве меры отличия последовательностей используется метрика среднего Хэммингова расстояния AHD между соседними элементами. Так, для случая счётчиковой последовательности AHD[AC]=2, а для последовательности кода Грея AHD[Ao]=l, что свидетельствуют об их незначительном отличии и невысокой полноте покрытия кодочувствительных неисправностей при реализации двукратного тестирования памяти. С целью достижения максимального отличия адресных последовательностей рассматриваются последовательности, для которых данная характеристика близка к величине разрядности m адресов памяти - анти-Грея (Ас») и MHD (Ан).

По результатам моделирования двукратного применения теста March С- наибольшее покрытие было получено для сочетания Ас-Ас: для PPSF3 - 71,7%, для PPSF5 - 22,0%. Отметим, что предыдущий метод при двукратном тестировании обеспечивает несколько более высокое покрытие. Насколько можно судить по вышедшим в печать работам,

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

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

В случае m проходов теста, который генерирует только одно состояние в соседних ячейках, оптимальным набором заполнений В0, Bi, ..., Bm.i будет такое, в котором минимальное значение из Хэмминговых расстояний между каждой парой векторов HD(Bj, Bj), где i, js{0,l,2,...,m-l}, будет наибольшим. Эффективные алгоритмы существуют для генерирования наборов, состоящих не более чем из четырёх таких шаблонов, чем и ограничивается покрывающая способность данного метода. По результатам моделирования для тестов типа MATS+ покрытие дефектов PPSF3 составило 47,23%, PPSF4 - 24,54%.

В методах для редуцированных моделей используется прямая генерация заполнений, поэтому подобные тесты отличаются высоким покрытием при небольшой длине. В работе был рассмотрен маршевый тест MT-R3CF длиной ЗОп для обнаружения активных APSF3 и пассивных PPSF3 кодочувствительных дефектов с покрытием 100%. Самый главный недостаток подобных методов является обратной стороной их преимущества: в большинстве практических случаев гарантировать достоверность редуцированных моделей, а значит и покрывающую способность таких тестов не представляется возможным.

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

В работе был развит новый метод обнаружения PSF3 и PSF4 для нередуцированных моделей - метод чётности позиции, - обеспечивающий 100%-ное покрытие для этих неисправностей. Он использует прямую генерацию активирующих наборов посредством начальных заполнений массива, и многократные проходы неразрушающего маршевого теста {f(re,\ve,re,we,re); Т(ге))- Ниже излагается предложенный принцип чётности позиции, вводится ряд понятий, формулируется теорема и показывается основанный на ней способ генерации заполнений.

Под чётностью позиции или расположения ячейки одноразрядной памяти понимается чётность адреса этой ячейки. Любой чётный адрес одноразрядной памяти размером N представляется выражением А=2п, а нечётный - А=2п+1, где ne(0,l,...N/2). Чётность позиции вводится лишь для того, чтобы разделить и упорядочить обращения к ячейкам двух подмножеств, никакого смысла касательно геометрического расположения ячеек на кристалле она не несёт.

Подобно ячейке одноразрядной памяти, чётность расположения слова в многоразрядной памяти будем определять чётностью его адреса, а чётность позиции ячейки внутри слова многоразрядной памяти - чётностью номера бита (биты 0,2,4,6,... являются чётными, а 1,3,5,7,... - нечётными). Характеристика чётности может быть приложена к блокам ячеек или слов любого размера, при этом вместо чётности физических адресов необходимо оперировать чётностью порядковых номеров блоков. Ячейки одноразрядной памяти и слова многоразрядной памяти, адреса которых различаются на 1, будем называются смежными.

Шаблоном называется минимальная по размеру последовательность бит, повторение которой даёт требуемое регулярное заполнение ячеек массива. В общем случае шаблон обозначается (P,Q,R,...), где P,Q,R,... - n-разрядные числа, размещаемые в памяти непосредственно друг за другом в порядке возрастания адресов. Подразделение последовательности бит шаблона на n-разрядные числа обусловлено в основном

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

Определение 1. Элементарной инверсной парой (1,0):(0,1) называется пара двухбитных шаблонов (1,0) и (0,1), применяемых к двум смежным ячейкам одноразрядной памяти. Напомним, что такие ячейки всегда имеют различную чётность расположения.

Определение 2. Инверсной парой масштаба х, обозначаемой М[х](1,0):(0,1), называются два шаблона (Р,<2) и (<3,Р), состоящие из полностью единичного Р= 11... 1 и полностью нулевого <3=00...0 чисел, разрядность которых одинакова и равна х. Инверсная пара масштаба х=1 есть элементарная инверсная пара. Инверсная пара масштаба х=2 есть шаблоны (11,00):(00,11), а парой масштаба х=3 являются значения (111,000):(000,111). Будем заполнение шаблоном (Р,С>) называть прямым, а (С2,Р) - инверсным.

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

Теорема покрытия парных комбинаг/ий. Дан массив одноразрядной памяти размером И, где Ы=2Р, ре(1,2,3,..). Адреса ячеек массива пробегают все значения от 0 до N-1. Заполнения массива инверсными парами М[х](0,1):(1,0), где х=2у, а у пробегает все значения от 0 до р-1, создают в двух любых произвольно взятых ячейках массива Са и Ср комбинации (0,1) и (1,0).

Пусть массив одноразрядной памяти содержит N=32 ячейки (рис.4). Тогда р=^232=5, и у принимает значения 0,1,2,3,4, а соответствующие им значения х - 1,2,4,8,16. Тогда 5 инверсных пар заполнений массива в байтовом представлении будут выглядеть так:

1) 55Ь 5511 55Ь 55И : ААЬ ААЬ ААЬ ААЬ (у=0, х=1)

2) 331г ЗЗЬ ЗЗЬ ЗЗЬ : ССЬ ССЬ ССЬ ССЬ (у=1, х=2)

3) 0Н1 ОРИ ОРЬ ОРЬ: РОИ Р0Н РОЬ РОЬ (у=2, х=4)

4) РРЬ 0011 РРЬ 00Ь: 00Ь РРЬ 00Ь РР11 (у=3, х=8)

5) РИ1 БРЬ 001т 00Ь: 001т 0011 РРЬ РРЬ (у=4, х=1б)

012345678 9 10 11 12 13 14 15 16 17 18 192021 22232425262728293031

Рис.4. Заполнения массива N=32 инверсными парами масштабов 1, 2, 4, 8, 16

Адреса ячеек массива проставлены в верхней части рисунка. Каждый ряд прямоугольников представляет собой заполнение массива определённым шаблоном; ячейки, принимающие единичное значение, окрашены чёрным. В паре рядов с одинаковым масштабом верхний ряд показывает прямое заполнение, а нижний - инверсное. Масштаб х увеличивается сверху вниз. В самом низу показано разделение массива на 4 блока (байта) \V0-W3 по 8 ячеек.

Теорема непосредственно даёт метод генерации наборов активации дефектов РРЭРЗ и АРЭРЗ, вовлекающих три ячейки Са, Ср и Сг с произвольным расположением в адресном пространстве, из которых любая может быть базовой. Для определённости будем считать базовой, например, ячейку Су, а Ср - агрессором (для АРЭРЗ). Две соседние ячейки Са и Ср в ходе заполнений массива инверсными парами примут комбинации (1,0) и (0,1), а комбинации (0,0) и (1,1) будут получены при сплошных нулевых и единичных заполнениях. Проверка переключения каждой ячейки Сг после заполнения массива обнаруживает РРБРЗ. Первое чтение Ст, которая в паре с С„ должна содержать требуемый набор активации, после запускающего перехода в Ср обнаруживает АРБРЗ. Для обнаружения таких конфигураций

APSF3, в которых адрес базовой ячейки меньше адреса агрессора, тестом должна быть выполнена проверка сохранности шаблона после прохода элемента t(re,we,re,we,re), выполняющего запускающие переходы: для этого добавлен элемент |(ге). С учётом сплошных количество заполнений составит 21og2N+2 (множитель 2 перед логарифмом отражает то, что заполнение для каждого масштаба х производится двумя шаблонами - (P,Q) и (Q,P))- Каждое заполнение требует N/W записей в память, где W есть разрядность памяти. Так как после заполнения к каждой из N ячеек маршевыми элементами {t(re,we,re,we,re); Т(ге)} будет произведено 6 обращений, то сложность теста будет вычисляться как 6N(21og2N+2)+N/W(21og2N+2)=2N(6+l/W)(log2N+l).

Определение 3. Перестановочной парой шаблонов называются двухсловные шаблоны (P,Q) и (Q,P), в которых числа Р и Q меняются местами; оба числа записываются в смежные слова или блоки ячеек (слов). Условимся, что младшее число всегда пишется в блок с чётным порядковым номером, старшее - в блок с нечётным номером. На рис. 5 заполнение ряда 1 (сверху) выполнено шаблоном (05h,AAh), а заполнение ряда 4 - шаблоном (AAh,05h); эти шаблоны образуют перестановочную пару. Отметим, что инверсная пара масштаба х есть частный случай перестановочной пары из х-разрядных чисел вида Р=00...0 и Q= 11.... 1

Определение 4. Масштабированной перестановочной парой шаблонов масштаба х, обозначаемой M[x](P,Q):(P,Q), называются два шаблона (xP,xQ) и (xQ,xP), в которых хР и xQ получаются соответственно из чисел Р и Q расширением каждого их бита начиная с младшего на х разрядов. На рис. 5 масштабированный шаблон M[2](05h,AAh)=(0033h,CCCCh) находится в ряду 3, а M[2](AAh,05h)=(CCCCh,0033h) - в ряду б.

Определение 5. Повторной (реплицированной) парой перестановки R[x](P,Q):(Q,P) для исходной пары (P,Q):(Q,P) является пара шаблонов (РР...Р, QQ...Q):(QQ...Q, РР...Р), в которой числа Р и Q повторяются как целое х раз. На рис. 5 повторный шаблон R[2](05h,AAh)=(0505h,AAAAh) находится в ряду 2, а R[2](AAh,05h)=(AAAAh,0505h) - в ряду 5. Заметим, что для инверсных пар процедуры повтора и масштабирования дают один и тот же результат.

0 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 1В 19 20 21 22 23 24 25 26 27 28 29 30 31

МВД чщ

Рис.5. Масштабирование и повторение пары шаблонов (05h,AAh):(AAh,05h)

Для активации дефектов PSF4 в каждом произвольном триплете ячеек массива Са, Ср и Сг, должны быть созданы все восемь возможных комбинаций. Проверка состояний и обоих переключений каждой ячейки массива СЕ, которая, как и в предыдущем случае, производится элементами {t(re,we,re,we,re); t(re)J после каждого начального заполнения, обнаруживает дефект.

Когда соседние ячейки, или ячейки-агрессоры имеют одинаковые значения активации СаСрСу=000 или СаСрСг=111, дефект обнаруживается первыми проходами маршевого теста со сплошными заполнениями 00h и FFh. Очевидно, что при остальных шести наборах {100,010,110,001,101,011} две из трёх соседних ячеек всегда имеют одинаковое значение, которое будем обозначать е, а одна - ё. Далее, значком * перед значением будем обозначать чётность позиции бита (ячейки), отличную от чётности двух других. Распределение ячеек по словам (байтам) может быть следующим: все три ячейки Са,Ср и CY могут быть в одном слове Wv, две любые могут быть в одном слове W|i, третья - в другом Wv, все ячейки могут быть в разных словах WX, W|i и Wv.

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

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

Таблица 1. Позиции ячеек-агрессоров и шаблоны активации РР8И4 и ЛР8Е4

Расположение соседних ячеек Шаблоны активации Р8Б4

(е,е,е)еУ, (е,е,*е)б\/ ООИ^ТИ

(е,е,*ё)е\/ 5511,ААЬ

(е,*е,е)е\\Ч> 22И, 8811, ОАИ, АОЬ, 77Ь, ОИЬ, 5№, Р5Ь, 1111, 44Ь, 05Ь, 50И, ВВИ, ЕЕЬ, АБЪ, БаЬ

(е e,ë)eWv 22Ь. 88Ь. ОАЬ, АОЬ, 28Ь, 82Ь, 11Ь, 44Ь. 05Ь; 50Ь, 14Ь, 41Ь

(е,ё)е\Уц, *ее\Уу ¿[х](Р <3):(С>,Р) для пар чисел (Р,<3): четная позиция *е -(2211,0011), (2211,5511), (8811,0011), (88Ь,55Ь), (ОАМОЬ), (ОЛИ,55Ь),(А011,0011), (АОЬ,5511); нечётная позиция *е -(1111,0011), (11Ь,ААЬ), (44Ь,ООЬ), (44Ь,ААЬ), (05Ь,00Ь),(0511.ААЬ), (50Ь,00Ь), (50Ь,ААЬ)

(е,ё)еШц, ее\Уу Щх](Р,(3):(С>,Р) для пар чисел (Р,0): чётная позиция ячеек • (1111,0011). (1111,5511). (4411,0011). (44Ь,551г), Ю5Ь,00Ь). (0511.5511). (50Ь,001г), (50Ь,55Ь); нечётная позиция ячеек - (2211,001)), (22ЬДАЬ), (881г,00Ь), (88Ь,АА11). (ОАЬ.ОО'гЛ (ОАЬ.ААЬ), {АОМШ, (АОЬ,ААЬ)

(е,*е)е\Уц, ëeWv КГх1(ООЬ,РКЬ):(РИ1,0011)

(е,е)еУ/ц, ёе\\Ч> ЕЧч.КРиЪ^1Ъ>-(11 Ь ООЬ^

(*е,ё)е\\'|1, ее\Уу КГхК55Ь,АА11):(АА11,5511)

СаеШ, С[,е\»/ц, М[х](Р) и М[х](Р,0):(0,Р) всех предыдущих вариантов, кроме (е,е,е)б V, (е,е,*е)е\/

Сложность полученного теста Ы(6+1ЛУ)(1001о82>1-398), формула верна для N>128. Обратим внимание, что данные заполнения обнаруживают и все РБРЗ. Если принять разрядность микросхем равной 8, приближённо длина теста составит 612М(1о&!М-4).

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

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

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

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

Рис. 6. Система диагностивования

Применение микропроцессора ЦВМ в качестве задатчика системной магистрали модуля вместо адаптеров, устанавливаемых в разъёмы периферийных шин ISA, EISA или PCI компьютеров, даёт два существенных преимущества:

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

• тестируемый модуль вместе с диагностической ЦВМ может быть расположен на удалении от компьютера-монитора, что необходимо при проверках в специальных условиях (например, в температурных камерах).

Вычислительное ядро ЦВМ включает микропроцессор MP со встроенными Flash-модулями программной памяти и дополнительную внешнюю память программ SRAM (рис. 7). Блок соединения магистралей ВСС (Bus Connection Circuitry) в режиме тестирования (TEST=1) предоставляет процессору ЦВМ доступ к пространству данных и кода системной магистрали модуля через адресное окно DS:2000h-3FFFh, а к пространству ввода-вывода -через окно IS:8000h-9FFFh. Узловыми частями блока являются управляемые магистральные передатчики адреса и сигналов управления, двунаправленный приёмопередатчик данных и схема расширения/перестановки адреса.

Блок DPRAM/MPXBI (Dual port RAM/Multiplexed bus interface) служит для связи с мультиплексированной параллельной магистралью модуля. Он состоит из двухпортовой памяти данных DPRAM, регистра и внутренней шины адреса правого порта, схемы управления доступом к памяти со стороны МПМ, схем генерации прерывания и установки разовых команд, а также двунаправленного параллельного порта для связи ЦВМ с устройством индикации. Введение памяти с управляемым доступом позволяет использовать ЦВМ не только в целях двустороннего тестирования МПМ, но и в составе комплексов полунатурного моделирования, для чего предусмотрена также обработка прерывания LINT

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

Два участка ПК связаны через конвертор USB-UART. Он поддерживает полноскоростной режим стандарта USB 2.0 и позволяет задавать скорость передачи по UART от 300 бит/с до 3 Мбит/с, различные форматы слова и режимы контроля чётности. Наличие приёмного и отправочного FIFO-буферов обеспечивает высокую пропускную способность ПК за счёт того, что минимизируется число кадров, требующихся для передачи массивов по USB, и время, которое затрачивается операционной системой ЦВМ на передачу данных.

Рис. 7. Структурная схема диагностической ЦВМ.

В разделе описания аппаратной части ЦВМ приводится обоснование применяемых схемотехнических решений, а также детально рассматривается работа спроектированных узлов. Логические схемы блоков ВСС и DPRAM/MPXBI реализованы на ПЛИС EPM7160S. Исходные файлы для компилятора MAX+PLUS П создавались на языке описания цифровых устройств AHDL. Средствами из этого же программного пакета было проведено моделирование работы схем и их элементов, проверка на непревышение ограничивающих временных параметров, а также осуществлена разводка и программирование ПЛИС.

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

Как показывает опыт, наиболее эффективно процесс поиска неисправностей реализуется при выполнении диагностических тестов в режиме отладки. Существенным моментом здесь является не только получение итоговых результатов проверок, но и достаточно полная визуализация контекста и возможность оперативного вмешательства специалиста. Типичными случаями такого вмешательства являются переход на операции зацикливания (при необходимости произвести электроизмерительный эксперимент), выбор из нескольких возможных операций, изменение тестовых значений, создание точек останова. Одновременно с этим потребность реализации стандартных действий, в частности, проверок теста, в виде низкоуровневых процедур послужила причиной разработки интерпретируемого языка, получившего рабочее название CDS (Communication Device Sequence).

В работе рассматриваются те компоненты системного программного обеспечения комплекса, которые непосредственно обеспечивают выполнение тестовых программ.

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

последовательному интерфейсу, а для интерпретируемых CDS-программ - также и режим отладки. ОС включает восемь функциональных единиц:

■ блок инициализации

■ приёмопередатчик сообщений последовательного канала

■ исполнительный блок системных команд

■ интерпретатор CDS

■ отладчик CDS

■ обработчики прерываний таймера и двухпортовой памяти DPRAM

■ набор процедур для вызова загружаемым кодом

■ блок перепрограммирования Flash-памяти ЦВМ

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

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

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

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

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

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

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

2) На основе полученных моделей, принципов и методов разработаны алгоритмы проверок детектирующей тестовой последовательности и процедур локализации неисправностей ДПМ в системах, содержащих статическую оперативную (SRAM) и постоянную (ROM) память. Испытания полностью подтвердили детектирующую и

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

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

4) Разработан новый метод обнаружения активных и пассивных кодочувствительных неисправностей PSF3 и PSF4, имеющий 100%-ное покрытие. Для этого был предложен принцип чётности позиции ячеек и их блоков в адресном пространстве памяти, введены понятия инверсной пары, шаблона, перестановочной пары шаблонов, операции их регулярного преобразования и сформулирована теорема покрытия парных комбинаций.

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

6) Подготовлено системное программное обеспечение комплекса - операционная система ЦВМ и программа-монитор, разработаны интерпретируемый язык CDS и средства создания и отладки CDS-программ, обеспечивающие эффективную организацию процесса диагностирования.

7) На базе разработанных средств созданы автоматизированные рабочие места для контроля и наладки опытных образцов БЦВМ в ГосНИИП и серийных образцов на заводе-изготовителе БЦВМ. Разработаны диагностические тесты для системных и периферийных магистралей и памяти вычислительных модулей различных типов, построенных на основе микропроцессоров 1867ВЦ6, 1867ВЦ2Т, 1867ВЦ5Ти Л1867ВМ2.

Публикации по теме диссертации:

1. Выборное П.В., Гаврилин Б.Н. О подходах к составлению диагностических тестов вычислительного ядра БЦВМ. - Вопросы оборонной техники, серия 9, 2010, вып. 3-4, с. 140148.

2. Выборнов П.В., Гаврилин Б.Н. Детектирующая тестовая последовательность для магистральных структур в системах с оперативной памятью. - Вестник Южно-Уральского государственного университета, серия «Компьютерные технологии, управление, радиоэлектроника», 2011, вып. 14, №23[240], стр. 53-59.

3. Аносов Б.Н., Выборнов П.В., Гаврилин Б.Н., Ефремов Д.В., Зверобой Б.М., Каращук A.B. и др. Пояснительная записка СЧ технического проекта АБ-151. - ФГУП «ГосНИИП», 2009.

4. Арендарчук В.Б., Выборнов П.В., Данилушкин Ю.В., Каращук A.B. Средства диагностики БЦВУ Заря-74. Пояснительная записка к техническому проекту. - ФГУП «ГосНИИП», 2010.

Множительный центр МАИ (НИУ) Заказ от 19 О Ч 20l2Lr. Тираж ''

61 12-5/2513 <г /

'. / /

Министерство ооразования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального

образования Московский авиационный институт (национальный исследовательский университет)

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

Выборнов Пётр Владимирович

ДИАГНОСТИКА ПАРАЛЛЕЛЬНЫХ МАГИСТРАЛЕЙ И ПАМЯТИ

БОРТОВЫХ ЦВМ

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

компьютерные сети

Диссертация

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

Научный руководитель: проф., д. т. н. Гаврилин Б.Н.

Москва - 2012

Содержание

Введение и постановка задачи.....................................................3

1. Диагностика магистралей.......................................................13

1.1 Объект диагностики.........................................................14

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

1.3 Электрические и логические эффекты замыканий цифровых сигналов.......................................................................23

1.4 Модели неисправностей....................................................30

1.5 Методика разбиений и детектирующая последовательность.......34

1.6 Синтез проверок алгоритма диагноза....................................38

2. Обнаружение дефектов памяти.................................................88

2.1 Модели дефектов SRAM и маршевые тесты...........................88

2.2 Кодочувствительные неисправности и методы их обнаружения...................................................................99

2.3 Метод чётности позиций..................................................118

3. Комплекс диагностики магистралей и памяти вычислительных модулей......................................................134

3.1 Диагностическая ЦВМ....................................................136

3.2 Программное обеспечение................................................146

Заключение...........................................................................186

Список использованных источников............................................192

Книга приложений

Приложение 1. Магистральный тест...............................................3

Приложение 2. Тест оперативной памяти......................................34

Приложение 3. Применение тестов и комплекса диагностики.............59

Введение и постановка задачи

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

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

параллельных магистралей (ДПМ) с синхронным обменом данными [63]. Объектом исследования в данной работе является подсистема ядра, состоящая из ДПМ, асинхронной статической оперативной памяти произвольного доступа (SRAM) и какого-либо типа постоянной (энергонезависимой) памяти с параллельным доступом (ROM). Функциональное назначение устройства в рассматриваемом контексте значения не имеет.

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

ограниченным. Во-первых, на рубеже 80-ых и 90-ых гг. мейнстрим технической диагностики цифровых устройств разделяется два самостоятельных направления: тестовая и функциональная диагностика СБИС и проверка межкомпонентных соединений. В результате практически отсутствуют работы, где вычислительное ядро рассматривалось бы как целостный объект программной диагностики при детальной разработанности вопроса для его компонентов (микропроцессоров, памяти и логических схем) по отдельности. Во-вторых, ракетные и в значительной части авиационные БЦВМ характеризуются определённой спецификой применяемых электронных компонентов, которая исключает применение большого арсенала методов, разработанных для цифровых устройств на основе В SA- и BIST-компонентов. Вместе с тем технология мелкосерийного и опытного производства делает неизбежным появление значительного числа монтажных дефектов.

Проверки, которые производились после изготовления вычислительных модулей БЦВМ и в ходе их испытаний, показали, что 70-90% всех неисправностей приходится на вычислительное ядро. Эти неисправности подразделяются на три группы: 1) дефекты демультиплексированной параллельной магистрали (ДПМ), или, что то же самое, неисправности связей между процессором и внешней памятью; 2) дефекты кристаллов внешней памяти; 3) дефекты, относящиеся к работе микропроцессора (МП) (табл.1).

Таблица 1. Неисправности вычислительного ядра в выборке из 1380 модулей разных типов.

Группа Дефекты Кол-во в % от всех дефектов выч. ядра

1. Неисправности магистрали замыкания магистральных сигналов 229 42

обрывы магистральных сигналов 193 35

дефекты элементов управляющей логики 45 8

повышенное сопротивление сигнальных линий 12 2

2. Дефекты кристаллов памяти статической оперативной (SRAM) 58 10-11

постоянной (Flash ROM, EEPROM) 8 1-2

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

дефекты микропроцессоров 1 «1

Как видно из табл.1, кристалльные дефекты запоминающих устройств (ЗУ) по числу намного уступают магистральным дефектам (10-15% против 85-90%), но на них приходятся практически 100% неисправностей СБИС: микропроцессоры оказываются едва ли не самым надёжным компонентом схемы. Высокая плотность расположения структурных элементов ЗУ на кристалле приводят к увеличенной (по сравнению с МП и ПЛИС) вероятности возникновения неисправностей. Встречаемость неисправностей оперативной

памяти в 7-10 раз выше, чем постоянной, если исходить из количества обнаруживаемых дефектов, приводимого к ёмкости запоминающего устройства. Отметим, что сходные оценки были даны в ряде других исследований [2,3]: отказы ОЗУ составляют до 70% от общего числа отказов электронных компонентов цифровых систем управления. Поэтому для обеспечения надёжного функционирования цифровых систем большое внимание должно быть уделено эффективному тестовому диагностированию памяти, особенно оперативной, как на этапе наладки, так и в ходе эксплуатации цифровых модулей.

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

В качестве тестов, с помощью которых осуществляется поиск дефектов в подсистеме «магистраль-память», на практике применяются тесты памяти, по существу являющиеся фрагментами TBK. Они обладают свойством обнаружения большинства неисправностей из групп 1 и 2 (в табл.1), однако, будучи нацелены преимущественно на проверку кристаллов ОЗУ и ПЗУ, не приводят к разделению неисправных состояний подсистемы. Поэтому для интерпретации результатов этих тестов и определения вызвавшего ошибку дефекта приходится ставить дополнительные программные и электроизмерительные эксперименты. Эти трудоёмкие операции, как правило,

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

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

Преимущества поверхностного монтажа и многослойной разводки в отношении автоматизации производства и компактности устройств сопряжены с усложнением печатных плат, и задача исчерпывающего тестирования межкомпонентных соединений приобрела повышенное значение. Уменьшение конструктивных размеров самих плат и компонентов при большом количестве выводов сделало привычные способы поиска дефектов с использованием визуальной информации и электроизмерительных приборов трудноосуществимыми. В 80-ых гг. организацией Joint Test Action Group (JTAG) была предложена схема тестирования цифровых устройств способом граничного сканирования, некоторое время спустя стандартизированная в виде спецификации IEEE Std. 1149.1. Разработанная BST-архитектура предоставляет возможности для программного тестирования межкомпонентных соединений и микросхем на печатной плате [4,5], причём его эффективность и простота достигается благодаря тому, что каждый из этих структурных элементов может

быть проверен по отдельности.

Узловым элементом BST-архитектуры является сдвиговый регистр BSR (boundary-scan register), охватывающий микросхему по периметру (рис.1). Вывод TDI микросхемы является входным для регистра, a TDO - выходным. Сдвиговые регистры нескольких микросхем объединяются последовательно [6]. Каждый сигнальный вывод микросхемы сопряжен с ячейкой регистра, которая может принудительно устанавливать вдвигаемое в неё значение на вывод микросхемы, захватывать входной сигнал с вывода или сигнал,

вырабатываемый функциональной частью микросхемы. Захватываемые данные выдвигаются на вывод ТБО и затем анализируются во внешнем приёмном устройстве. Ячейка представляет собой трёхбитную схему сдвига, состоящую из нескольких двухвходовых мультиплексоров и В-триггеров захвата и модификации сигналов. Входами выбора коммутируемой линии и стробированием записи в триггеры управляет ТАР-контроллер (на рисунке не показан). Когда микросхема находится в рабочем режиме, ячейки, будучи прозрачными для передачи сигналов, могут фиксировать состояние сигнальных линий в произвольный момент времени (по команде контроллера).

Рис.1. Схема тестирования межкомпонентных соединений для ВБТ-микросхем.

К настоящему моменту диагностика межкомпонентных соединений является достаточно подробно разработанным вопросом в отношении цифровых устройств, построенных на В8Т-интегральных схемах. Здесь как в рамках поведенческого, так и в рамках структурного подходов было разработано большое число диагностирующих алгоритмов, различающихся набором допустимых дефектов и полнотой проверок соединений [6-11], в том числе алгоритмы, минимизированные по размеру последовательности тест-векторов [12,13,14], что для сканирующего способа существенно сокращает время проверки. Для рассматриваемых в данной работе вычислительных устройств, которые построены с использованием обычных (не-В8Т) компонентов, поиск дефектов магистральных связей не может быть сведён к задаче получения матрицы соединений и её сравнения с эталонной. Объектом тестовых воздействий здесь является целостная подсистема, состоящая из магистральных структур и внешней памяти, а единственными выходными переменными, доступными для анализа алгоритмом диагноза, - значения разрядов магистральной шины данных, состояние которых фиксируется микропроцессором или другим задатчиком магистрали в определённый момент цикла чтения. В отличие от сканирующего тестирования, при котором состояние любых линий связи может быть зафиксировано и передано для

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

Полупроводниковые ОЗУ, как один из основных компонентов вычислительных машин, являются предметом едва ли не самой обширной области диагностики цифровых устройств. Повышение степени интеграции и плотности размещения структурных компонентов, уменьшение их размера, вызванные необходимостью увеличения ёмкости и сокращения времени доступа, как уже было сказано, приводят к повышенной вероятности возникновения дефектов ОЗУ (отнесённой к единице площади кристалла). Значительное количество структурных элементов памяти - ячеек массива -подразумевает астрономическое число сочетаний их состояний. Для массива из N ячеек таких состояний может быть 2N. Несмотря на то, что для обнаружения реально существующих дефектов достаточно генерировать только малую их часть, численно она всё же остаётся огромной. Это выдвигает на первый план задачу создания эффективных методик тестирования, обеспечивающих высокую покрывающую способность (покрытие) для дефектов тех или иных типов и при этом удовлетворяющих установленным временным ограничениям. Важность этой задачи возрастала по мере увеличения ёмкости памяти. Традиционные алгоритмы с относительно высокой покрывающей способностью - GALPAT, WALPAT и Sliding Diagonal, имеющие сложность порядка N2 и N3/2 (сложность теста есть количество обращений к памяти как функция числа ячеек N), - требуют для тестирования памяти сколько-нибудь значительной ёмкости слишком много времени. Так, для N=4M и времени доступа 100 не нижний предел времени, требующегося для выполнения этих тестов, составит 74 дня (4N2), 37 дней (2N2) и 53 мин (4N3/2). Другие ранние тесты, такие как MSCAN, Zero-One, шахматная доска, имеют сложность порядка N, но низкую покрывающую способность [15].

Проблема обнаружения т.н. классических типов неисправностей ОЗУ была решена после создания маршевых тестов. Доказано [16,17], что именно маршевые тесты являются непр�