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


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.

1

РАЗРАБОТКА И ПРИМЕНЕНИЕ ПРОГРАММНЫХ СРЕДСТВ
ДЛЯ ОБУЧЕНИЯ СТУДЕНТОВ СПЕЦИАЛИЗАЦИИ
«МАТЕМАТИЧЕСКАЯ ЭЛЕКТРОНИКА»



А. Е. Люлькин

Белорусский государственный университет

Минск, Беларусь

E
-
mail:

lulkin
@
bsu
.
by


Рассматриваются оригинальные программные
средства, которые испол
ь-
зуются
при подготовке студентов специализации «Математическая электрон
и-
ка» Белгосуниверситета в области моделирования и тестирования логических
схем. Приводится описание генетического алгоритма для построения теста, ре
а-
лизованного
и включенного в состав программных средств.


Ключевые слова
:
логическое
моделирование
,
тесты логического контроля
,
генетические алгоритмы
.



С целью повышения качества подготовки студентов специализации «Матем
а-
тическая электроника» механико
-
математического
факультета Белгосуниверситета в
рамках международной программы
REASON

разработан спецкурс «Тестирование и
тестопригодное проектирование БИС
/
СБИС
»
. Спецкурс включает как лекционный
материал, так
и лабораторные занятия, направленные на получение практически
х н
а-
выков логического анализа цифровых схем с применением программных средств.

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

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

практических навыков проектирования тестов были разработаны две подсистемы для
автоматизированного построения тестов:


подсистема анализа и построения тестов для тестопригодных схем;


2


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

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

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

Вероятностный метод состоит в
следующем:

1) генерируется очередной псевдослучайный входной набор;

2) вычисляется множество неисправностей, проверяемых набором;

3) набор включается в тест, если он проверяет некоторые неисправности, кот
о-
рые не проверяются предшествующими наборами.

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

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

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

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

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

3

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

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

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

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

Рассмотрим особенности разработанного и реализованного генетического алг
о-
ритма
(ГА)
для построения тестов.

Пусть
С
{
C
1
,
C
2
,.
..,
С
r
}

разбиение множества входов схемы {1,2,...,
n
} на по
д-
множества
С
j
{
j
1
,
j
2
,...,
j
u
i
}, где
j
1
,
j
2
,...,
j
u
i

{1,2,...,
n
}. Подмножества
C
1
,
C
2
,...,
С
r
могут
пересекаться и

r
i
i
C
1

{1,...,
n
}.
Здесь
n


число входов в схеме. Пусть также
N
1


ма
к-
симальное число псевдослучайных наборов, которые используются для формиров
а-
ния начального отрезка теста
T
;
N
2


максимальное число входных наборов, генер
и-
руемых в процессе одной итерации на основе генетич
еского алгоритма;
N
3


макс
и-
мальное число итераций.

Алгоритм

1. Последовательно генерируются
N
1
псевдослучайных входных наборов. Для
каждого входного набора
t
i
находится множество ранее необнаруженных неиспра
в-
ностей, которые проверяются данным набором, и о
пределяется их число
k
i
(данная
задача решается с помощью моделирования неисправностей). Если
k
i
>0, то набор
t
i

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

I
:1.

2. Наборы из теста
Т
упорядочиваются в порядке убывания числа обнаружива
е-
мых ими неисправностей. Формируется множество наборов
Т
1
. При этом в
Т
1
вкл
ю-
чаются наборы с лучшим качеством (качество набора определяется ч
ислом пров
е-
ряемых им неисправностей; чем больше это число, тем выше качество набора). При
этом |
T
1
|[|
T
|/3].

K
:1.

3. Генерируется случайное число
p

[0,1]. Если p

0,5, то наборы
t
1
и
t
2
, которые
будут использоваться для построения очеред
ного тестового набора
t
на основе ГА,
выбираются из
T
1
, иначе

из
Т
.

Если наборы выбираются из
T
1
, то генерируются два случайных числа
p
1
,
p
2

[0,1],
p
1

p
2
. Если (
i
-
1)

(1/|
Т
1
|)

p
k
<(1/|
T
1
|)
i
, то
i
-
й набор из
Т
1
выбирается в кач
е-

4

стве
t
k
. Зд
есь
k


{0,1}. Если
p
2
приводит к выбору того же входного набора, что и
p
1
,
то генерируется другое псевдослучайное число из отрезка [0,1], чтобы исключить т
а-
кой случай.

Аналогичным образом выбираются наборы и из
Т
(если
p
>0.5).

4. Случайн
ым образом упорядочиваются подмножества
С
1
,
С
2
,...,
С
r
из
С
. Это
можно сделать следующим образом. Генерируется случайное число
p

[0,1]. Если (
i
-
1)

(1/
r
)


p
<(1/
r
)
i
, то
С
i
помещается в конец формируемой последовательности и
С
i

удаляется из
С

(вначале последовательность не содержит подмножеств из
С
). Далее
указанная операция повторяется для нового
С
с учетом того, что |
С
|
r
-
1. Процесс
продолжается до тех пор, пока
С


.

В результате получим последовательность
С
u
(
С
i
1
,
С
i
2
,...,
С
i
r
);
i
1
,
i
2
,...,
i
r

{1,2,...,
r
}.

5. Строим входной набор
t
на основе выполнения операции смешивания наб
о-
ров
t
1
и
t
2
и операции мутации.

v
:1.

6. Генерируется случайное число
p

[0,1].
Если
p

0.5, то в набор
t
включаем
значения входов
С
i
v
, взятые из набора
t
1
, иначе

из набора
t
2
.

Если
v

r
, то переход к п.7, иначе
v
:
v
+1 и переход к началу п.6.

7. Выполняется операция мутации для полученного набора
t
. Генерируются
слу
чайные числа
p
1
,
p
2
,...,
p
n

[0,1]. Если
p
j

1/
n
, то
j
-
й разряд в
t

инвертируется.

8. Для набора
t
находится множество проверяемых им неисправностей и по
д-
считывается их число
k
t
. Если
k
t
>0, то набор
t
включается в множество наборов
Т
I
,
генер
ируемых на итерации
I
для включения в тест (перед началом итерации
Т
I


).
Если список непроверенных неисправностей является пустым, то
Т
:
Т

Т
I
и выпо
л-
нение алгоритма завершается.

Иначе, если
K

N
2
, то
Т
:
Т

Т
I
и переход
к п.9; иначе
K
:
K
+1 и переход к п.3.

9. Если
I

N
3
, то тест
T
построен и выполнение алгоритма завершается; иначе
I
:
I
+1 и переход к п.2.

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

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


ЛИТЕРАТУРА


1.
Люлькин, А. Е.
Состав и организация учебно
-
исследовательской системы автоматизированн
о-
го построения тестов для дискретных устройств на ПЭВМ
/
А. Е. Люлькин
//
Упра
вляющие системы и
машины. 1996. № 1

2. С. 48

55.

2.
Люлькин, А. Е.
Моделирование неисправностей в функционально
-
переключательныхКМОП
-
структурах
/
А. Е. Люлькин
//
Электронное моделирование. 1998. № 5. С. 49

59.


Приложенные файлы

  • pdf 39378433
    Размер файла: 267 kB Загрузок: 0

Добавить комментарий