RUS | UKR | ENG || ДонНТУ || Портал магистров ДонНТУ
Автобиография | Библиотека | Ссылки | Отчет о поиске | | Индивидуальный раздел
Магистр ДонНТУ Блинов Юрий Валерьевич

Блинов Юрий Валерьевич

Факультет компьютерных наук и технологий

Специальность: Компьютерные системы и сети

«Разработка и исследование методов и структур аппаратной генерации тестов и анализа тестовых реакций на базе FPGA»


Разработка и исследование методов и структур аппаратной генерации тестов и анализа тестовых реакций на базе FPGA


Оглавление

  1. Введение и актуальность
  2. Цель и задачи магистерской работы
  3. Предполагаемая научная новизна
  4. Принципы цифрового тестирования
  5. Методы генерации тестовых воздействий
  6. Анализ тестовых реакций
  7. Разработанная структура логического анализатора
  8. Результаты работы (на момент написания реферата)
  9. Выводы
  10. Список литературы

Введение и актуальность

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

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

Существенным параметром при тестировании устройств является скорость тестирования. Существуют автоматизированные системы тестирования (ATE) позволяющие работать на частотах равных десяткам гигагерц[2]. Данные устройства дорогостоящие, массивные и стационарные, что ограничивает их применение. В свою очередь, ставшая популярной технология FPGA позволяет создавать быстрые компактные и не дорогие устройства. Поэтому тема данной магистерской работы, направленная на разработку и исследование методов и структур аппаратной генерации и анализа дискретных тестовых реакций, с использованием всех достоинств технологии FPGA является актуальной.


Цель и задачи магистерской работы

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

  • исследование существующих методов и систем диагностирования;
  • разработка методов и FPGA‐структур генерации дискретных тестовых реакций;
  • разработка методов и FPGA‐структур анализа дискретных тестовых реакций;
  • разработка и исследование экспериментальной подсистем генерации тестовых воздействий и анализа тестовых реакций на базе FPGA.

Предполагаемая научная новизна

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


Принципы цифрового тестирования

На рисунке 1 продемонстрирован способ взаимодействия диагностирующего оборудования с ОД.


Принцип тестирования

Рисунок 1 — Подача тестирующих векторов на ОД[2]

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


Методы генерации тестовых воздействий

Процесс генерации тестовых воздействий состоит в последовательной выдаче на входы ОД тестовых векторов ti, i=1..n, из некоторого множества T={ti}, называемого тестом. Порядок следования тестовых воздействий может быть не важным или строго оговоренным. В зависимости от указанных признаков различают следующие методы генерации тестовых воздействий[1]:

  • исчерпывающие;
  • псевдослучайные;
  • детерминированные;
  • комбинированные.

Исчерпывающее тестирование

При исчерпывающем тестировании тест Т образует 2n всевозможных входных значений, где n — количество входов, которые подаются на объект диагностики, причем порядок их следования безразличен. Данный способ весьма прост в реализации, т.к. может быть реализован с использованием двоичного счётчика нужной разрядности. Однако, он неприменим для последовательностных схем, что объясняется плохими корреляционными свойствами векторов исчерпывающего теста.

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

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


Псевдослучайное тестирование

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

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

Для генерации псевдослучайных последовательностей применяют две схожие структуры. На рисунке 2 показан РСЛОС с внешними сумматорами обратной связи, а рисунок 3 показан РСЛОС с внутренними сумматорами обратной связи[3].


РСЛОС с внешними сумматорами обратной связи

Рисунок 2 — РСЛОС с внешними сумматорами обратной связи[3]


РСЛОС с внутренними сумматорами обратной связи

Рисунок 3 — РСЛОС с внутренними сумматорами обратной связи[3]

Важной характеристикой РСЛОС является период повторения генерируемой им последовательности, который зависит от вида обратной связи описываемой многочленом обратной связи G(x). Доказано, что если в качестве G(X) выступает примитивный, а значит и неприводимый, многочлен, то на выходах РСЛОС генерируется периодическая последовательность с максимальным для разрядности n периодом следования сигналов, равным L = 2n - 1. Такие последовательности называются последовательностями максимальной длины или М‐последовательностями[3].


Генетические алгоритмы

Достаточно новым методом генерации псевдослучайных тестов является метод с применением генетических алгоритмов[4]. Использование генетических алгоритмов при генерации проверяющих тестов является естественным развитием псевдослучайных методов генерации тестов. Одним из первых применений генетических алгоритмов в технической диагностике цифровых схем является построение на их основе генераторов тестовых последовательностей. Суть задачи заключается в поиске двоичной входной последовательности, которая для каждой неисправности из заданного множества дает различные выходные значения сигналов в исправной и неисправной схемах. Генетические алгоритмы, являясь одной из парадигм эволюционных вычислений, представляют собой алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора. Эти принципы основаны на следующих механизмах эволюции:

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

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

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


Детерминированное тестирование

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


Слабо детерминированные тесты

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

К генераторам слабо‐детерминированных тестов относят[1]:

  • генераторы на базе композиции ПЗУ и линейной последовательностной машины («ПЗУ + ЛПМ»);
  • ПЗУ, счетчика и формирователя («ПЗУ + СТ + Ф»);
  • генератор на базе регистра сдвига с нелинейной обратной связью (РСНОС)[10].

Сильно детерминированные тесты

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

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


Комбинированные тесты

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


Анализ тестовых реакций

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

  • логический анализ;
  • компактный анализ.
Среди методов последнего типа наибольшее распространение получили[1]:
  • сигнатурный анализ — основан на сжатии ТР с помощью регистра сдвига, охваченного цепями линейных обратных связей;
  • счет состояний — двоичный счётчик подсчитывающий количество единиц и нулей;
  • счет переходов — двоичный счётчик подсчитывающий количество переходов из 0 в 1 или из 1 в 0;

Разработанная структура логического анализатора

На момент написания реферата на базе отладочного комплекса Spartan‐3E разработан логический анализатор. Упрощённая структура разработанного логического анализатор приведена на рисунке 4.


Урощённая структура логического анализатора

Рисунок 4 — Структура разработанного логического анализатора
(GIF-анимация, размер: 113 KB, количество кадров: 11, количество повторений: 5)

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

Разработанное устройство имеет следующий принцип работы:

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

Результаты работы (на момент написания реферата)

На момент написания реферата были получены следующие результаты:

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

Выводы

На основе вышеизложенного материала можно сделать вывод, что:

  • разработка и исследование методов и структур аппаратной генерации тестов и анализа тестовых реакций остаётся актуальной;
  • на основе данных характеристик и описаний методов генерации тестовых векторов и анализа тестовых реакций сделаны выводы о целесообразности выбора методов при тестировании разных классов устройств;
  • в качестве платформы для реализации был выбран отладочный FPGA комплекс Spartan‐3E.


Список литературы

  1. Зинченко Ю.Е. Методы и средства встроенного тестового диагностирования специализированных устройств сетей передачи данных реального времени / Ю.Е Зинченко // Диссертация на соискание уч. степени канд. техн. наук.; специальности: 05.13.13 «Вычислительные машины, комплексы, системы и сети» и 05.13.05 «Элементы и устройства вычислительной техники», Институт проблем моделирования в энергетике (ИПМЭ) АН Украины. — Киев, 1989, 208c.
  2. Agrawal V.D. Essentials of electronic testing for digital, memory and mixed-signal VLSI circuits. /V.D. Agrawal //Kluwer Academic Publishers, 2000, — 690c.
  3. Зинченко Ю.Е. Разработка компьютерных систем на базе ACTIVE-HDL, методические указания [Электронный ресурс] Режим доступа: http://hardclub.donntu.ru/methods/nkd/nkd_mu/MAIN.HTM
  4. Скобцов Ю.А. Логическое моделирование и тестирование цифровых устройств/ Ю.А.Скобцов, В.Ю. Скобцов // Донецк: ИПММ НАН Украины, ДонНТУ,2005. — 436с.
  5. Ivask E., Raik J., Ubar R. Comparison of Genetic and Random Techniques for Test Pattern Generation [Электронный ресурс] Режим доступа: http://www.citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.8973
  6. Перцовский М., Воробьев Е., Трифонов А. Применение логических анализаторов в тестировании цифровой техники [Электронный ресурс] Режим доступа: http://www.cta.ru/cms/f/?/366656.pdf
  7. Уколов И.В. Cинтез псевдослучайных контролирующих тестов для дискретного устройства [Электронный ресурс] Режим доступа: http://www.sgu.ru/files/nodes/37509/Ukolov(64-70).pdf
  8. Zhang Y., Agrawal V.D. An Algorithm for Diagnostic Fault Simulation [Электронный ресурс] Режим доступа: http://www.eng.auburn.edu/~agrawvd/TALKS/LATW10/latw10_yu_new6.pdf
  9. Linear feedback shift register. Википедия свободная энциклопедия [Электронный ресурс] Режим доступа: http://en.wikipedia.org/wiki/Linear_feedback_shift_register
  10. Non-Linear Feedback Shift Register. Википедия свободная энциклопедия [Электронный ресурс] Режим доступа: http://en.wikipedia.org/wiki/NLFSR

Примечание

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