Скобцовы Моделирование и тестирование

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

а) б) в) Рис.8.13 Различные реализации параллельных ГА.

На рис.8.13 б) представлена также чрезвычайно популярная "модель островов" (coarse grain), где множество подалгоритмов совместно работают параллельно, обмениваясь в процессе поиска некоторыми особями. Эта модель допускает прямую реализацию на компьютерных системах с MIMD-архитектурой (multiple-instruction, multiple-data). При этом каждый "остров" соответствует своему процессору.

В клеточных ГА (fine grain), показанных на рис.8.13 в),

параллелизация обычно реализуется на компьютерных системах с SIMD-

архитектурой (single-instruction, multiple-data), где каждый процессор представляет подпопуляцию (из одной особи). Хотя известны работы, в которых используются однопроцессорные компьютеры и системы с MIMD-архитектурой.

Для параллелизации ГА мы, в первую очередь, используем модель «рабочий - хозяин», поскольку она требует наименьших изменений в существующей версии программного обеспечения, реализующего ГА генерации тестов и дает неплохие результаты [120].

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

381

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

Итак, процессор – хозяин выполняет центральную часть (ядро) алгоритма генерации тестов, в то время как логическое моделирование (исправных и неисправных) цифровых схем реализуется на процессорах – рабочих. Наиболее критичным по затратам вычислительных ресурсов является моделирование неисправных схем. Известны различные методы организации распределенного моделирования неисправностей, которые, в основном основаны на разбиении: 1) схем на подсхемы; 2) тестовой последовательности на подпоследовательности. Мы используем комбинированный подход, сочетающий эти два метода.

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

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

При этом работа между процессором-хозяином и рабочими распределяется следующим образом.

Процессор-хозяин:

− выполняет все вход-выходные операции с пользователем и файловой

382

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

−первоначально запускает «рабочие» процессы на доступных ресурсах;

−распределяет копии (внутреннего представления) схем и списков неисправностей каждому рабочему процессору;

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

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

Поскольку размер популяции много больше числа процессоров

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

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

383

большинстве случаев улучшается, а время генерации тестов существенно сокращается.

8.8 Иерархические ГА построения тестов для сильно последовательностных схем

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

8.8.1 Функциональный подход

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

Проверяющие эксперименты для конечного автомата (КА) имеют следующую структуру

… XiTijYj … X kTklYl ,

где X i – вход/выходная последовательность, переводящая КА в состояние

Si ; Y j - вход/выходная последовательность, идентифицирующая

384

состояние S j ; Tij переводит КА из состояния Si в состояние S j [121].

При построении проверяющего эксперимента в качестве X i и Y j мы

можем использовать специальные характеристические последовательности: 1) синхронизирующая; 2) установочная; 3) диагностическая; 4) уникальная, которые рассмотрены в разделе 7. Для построения этих характеристических последовательностей также используются различные методы и модели:

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

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

3)методы, основанные на символьном моделировании в терминах характеристических переменных.

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

Таким образом, для сильно последовательностных схем целесообразно применять 2-уровневый ГА (Рис.8.14). При этом ГА первого нижнего уровня строит характеристические последовательности. Генерация этих последовательностей может быть выполнена:1) на структурном уровне представления ДУ с использованием модели в виде логической схемы; 2) на основании автоматной модели, заданной таблицей переходов и выходов. В обоих случаях для их построения можно

385

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

ГА – уровень II (верхний)

Рис. 8.14 Схема 2-уровневого генетического алгоритма для сильно последовательностных схем

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

8.8.2 Структурный подход

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

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

386

(hard) неисправностей [118]. Построение тестовой последовательности для такой неисправности выполняется в два этапа: 1) активизация неисправности, 2) распространение влияния неисправности, как это показано на рис.8.15. При этом используется структурная модель в виде итеративной комбинационной схемы, рассмотренная в 7.1.

ПЕРВИЧНЫЕ ВХОДЫ

ПЕРВИЧНЫЕ ВЫХОДЫ

Рис.8.15 2 этапа генерации тестовой последовательности

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

387

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

КЭ 0

а) Активизация неисправности в КЭ, б) Релаксация состояний Рис.8.16 Построение тестовой последовательности схемах для “тяжело тестируемых” (hard) неисправностей

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

388

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

Для построения транслирующих входных последовательностей используется таблица посещенных состояний схемы, в которой посещенные состояния отображаются во входные вектора, как это показано на рис.8.17. [118].

Рис.8.17. Структура данных посещенных состояний

Здесь слева представлены посещенные состояния и справа входные вектора на текущий момент. Состояния связаны указателями со “своими” входными векторами. То есть указатель состояния показывает входные вектора, после подачи которых, схема находится в данном состоянии. В процессе генерации тестовой последовательности эти структуры данных постоянно пополняются.

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

389

k и m, а требуемое состояние (отмеченное на рис.8.17 как конечное) достигается после векторов j и l. Таким образом, для установки схемы в требуемое состояние E из текущего состояния S можно использовать последовательности T1=(i…j) или T2=(k…l), которые находятся из представленных структур. Поэтому, если состояние схемы Sr, полученное после релаксации, отображается в ранее посещенное состояние Sp, и

существует транслирующая входная последовательность TSSз из текущего

с

состояния Sc в состояние Sp, то может быть построена транслирующая

входная последовательность T Sr .

sc

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

популяцию включаются случайные входные последовательности заданной длины. Кроме этого в нее могут быть включены входные последовательности, которые частично решают поставленную задачу. Например, это могут быть входные последовательности, устанавливающие лишь некоторые триггера в необходимые состояния. При чем различные входные последовательности могут устанавливать различные триггера в необходимые состояния. Назовем последовательность Si, устанавливающей i-й триггер, входную последовательность, которая устанавливает i-й триггер в единичное состояние. Аналогично назовем последовательность Ri, сбрасывающей (очищающей) i-й триггер, входную последовательность, которая сбрасывает i-й триггер в нулевое состояние. Очевидно, эти входные последовательности могут быть полезны при построении входных последовательностей, устанавливающих схему в заданное состояние и поэтому их следует включить в начальную популяцию. Будем называть последовательность Si (Ri) типа А, если она позволяет установить

390