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


Чтобы посмотреть этот 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

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