автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:К построению нейрофункциональной коммуникационной среды систем обработки знаний

САИКТ-ПЕТЕРБУРГСЕГТЗ тСУКАРСТБЕЩДП ТЕШЩЧЕСИ1Я УНЖКРС15ТЕТ

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

АРЗУМАНЯН Рачья Вагерша&ович

УДК 681.3.01(02)

X ПОСТРОЕНИЮ НЕЙРОФУНКЩОНАЛЫЮП КОММУНИКАЦИОННОЙ СРЕДЫ СИСТЕМ ОБРАБОТКИ ЗНАНИЯ

Специальность: 05.13.13 - вычислительные машины,

комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1994

Работа выполнена на кафедре вычислительной техники и в НИИ многопроцессорных вычислительных систеи при Таганрогском государственном радиотехническом университете

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

член-корреспондент РАН, доктор технических наук, профессор КАЛЯЕВ A.B.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук, профессор ИГНАТЬЕВ М.Б.,

кандидат технических наук, доцент РЕШЕТНЯК В.Н.

Ведущее предприятие: Институт оптико-нейронных технологий РАН, г. Москва

[> ^диссертации состоится 1994г.

часов на засздании диссертационного совета Д 663.38.64

в Санкт-Петербургском государственном техническом университете по ацресу: 195251, С- Петербург, ул. Политехническая 21, ауд. 34.

Автореферат разослан "(У/U/ ' ' /1**-- 19Э4г-.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

К.П. Лурандии

ВВЕДЕНИЕ

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

Осознание Сложности процессов мышления, представления и обработки знаний происходило и в рамках эволюции средств вычислительной техники. Исследования в области создания интеллектуальных систем привели к необходимости пересмотра базисных постулатов теории вычислений, с переходом от понятий 'обработка данных", "коммутация" к новым -"обработки знаний", "коммуникация". В диссертационной работа рассматриваются модели, опиравшиеся ках на принципы, разработанные г рамках исследований мозга, так и на исследования в области искусственного интеллекта (ИИ). Результатом такого синтеза могло бы быть создание нового поколения нейрокомпыоггерных систем, позволяющих проектировать системы обработки зшший (003), отражающие существующий уровень понимания працее ч представления и манипулирования знаниями в живых системах.

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

л

¡Ьункциопиро оании которой отображаются на процессы структурной ..амоорганиэации. Это позволяет говорить о самоорганизующейся • ^нефункциональной коммуникационной среде (СНКМС) СОЛ. Таким образом, СНКМК макет быть представлена в виде структурированной системы, с несколькими уровнями иерархии, обмены к которой обеспечивают мощные коммутационные сети.

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

Для достижения поставленной цели в диссертации решены следующие оснониые

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

- исследованы нейрофизиологические модели коммуникационных отношений в центральной нервной системе;

- разработана модель коммуникационной системы обработки знаний с элементами структурной самоорганизации;

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

Предметом__иг еле попами я являются методы представления и

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

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

В процессе исследований получены следующие 'Т?тр научные результаты, выносимые на залиту:

1) кзтохга синтеза ¡»эраргич-зслих кдошэттавацнонныг. сред систем обработки сиг.яка, в багисв кгобдогсаятеэтерс^х систем с гапергубнческой архктоЕ'зтфой;

2) автоматика и логичоогяэ кодедя ьогагукикационлых процессов в системах обработки зтаявй с злемеззтеьи отруотуряой' с вмо о рга! мзшии;

3) гкпе рхуСнче сгие интерфейса агйрофушцдаоиальной комйуникацион-иой срака система обработки Влзкий;

4) алгоритмы обмена яалныкл в етшутаинетяюй сети "двоичная гипвюмиа";

й) ьсвтоды папаиекия .еСФвктивкости обменов данными в ксгвпггационной сети "двоичная гипергаина" чере-э организацию расгфед&п^дисй обработки Ешформшоси или введение дополнительных гиперхубическкх каналов связи; .

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

Пваугтяпмя аккнпгггк вяватм ггнуганг-.

- в разработке модели интеллектуальной систем*, обработки знаний с элементами структурной самоорганизации;

- в разработке _ методов ■ синтеза нейрофунхциональной самоорганизующейся коммуникационной среды систем обработки знаний;

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

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

Это позволило создать имитационную модель нейроФункциональной ■шкмуникадаскной ' среды системы обработки знаний с элементами структурной самоорганизации. Отработанные на имитационной модели подкопы используются при создании конхретнмх образцов интеллектуальных систем в рамках проводимых в НИИ МВС научно-исследовательских работ.

РбН.'ЯГЯЯНИя ргэулг,тутпт^ рдбсяы. Работа является результатом исследований, проводимых автором под руководством члена-корреспондента РАН Д.В.Каляева в рамках меявуэозской научно-технической программы "Принципы создания универсального сверхпроизводительного

супярмакронейроюмпыотера • с программируемой самоорганизующейся архитектурой и элементами искусственного интеллекта" (Распоряжение 57 от 19.05.8С г. Министерства науки, высшей школы и технической политики Российской Федерации), а также при выполнении научно-исследовательских и хоздоговорных тем, проводимых в НИИ МВС.

Результаты диссертационной работа использовались о учебкжд процессе ТРТУ при выполнении.дипломных работ.

Anpaßaima лдбоуы. Основные результаты диссертацншшой работы докладывались ч обсуждались на: XII Всесоганом овюшара по одкородкьш вычислительным средам и сиетоличассим структурам (Лыьап, 19Э1 р.), XIV, XV Семинарах по однородный вычиопитолыпла срадаи и систолическим структурам <Львов, 1992 г.), Секции "Кнфодааткз&ция , систем безопасности" III конгресса "К^Ъоркационш^о коашушвгаге&з. озти, системы, технологии" Ма&дународаого форуиа юсЬорматкп&ци::. (г.Иоисва 1992 г.). Научном сеамкаро НИЦ ИВС, Научно-техшзчэсЕйг cetsatapax t: научно-методических котРэ рокциях npcxteccopcco-преподавательского состава, аспирантов и сотрудников ТРТУ (1090-1993 гг.).

Лх&цжашии Основные результаты диссертационной работы отрагены в восьми печатных работах.

Структура и оЯ-ы>м рябетл. Диссертационная работа состоит из сведения, четырех разделов и зоклячегаш, изложенных на 228 стргнапик, содерзит 133 рисунка, 1 таблицу, 00 наименований библиографией, 129 страниц приложения, всего 357 страниц.

СОДЕРЖАНИЕ РАШШ

L.

во—введении обосновывается актуальность теш, формулируется цель и задачи исследования.

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

В системах 1Ш большую роль приобретают проблемы, связанные с понятием "знания" - катодами их представления, обработки. При обработке знаний наиболее фундаментальной и важной проблемой становится, преада всего, описаниа смыслового содергимого проблем самого широкого даапазока. а таске наличие такой формы описания знаний (языка представления званий), которая гарантирует, что обработка их содержимого форг&алъньаз* правилами преобразования будет осуществляться правильно.

Существующие на сегодняшний день CQ3 являются прсграюссгз продуктом, однако фукзЭД'Окирование в репные реального времен;!,

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

Проектирование параллельных систем обработки знаний, содержшм<к принципиально большое число обрабатывающих элементов (ОЭ), переродит проблему проектирования коммутационном сети (КС) таких систем п новую плоскость. Кроме того, к ХС предъявляются дополнительные требования, не характерные для мультипроцессорных систем. Необходимость обеспечит* п^райоиглие новых зависимостей между • -¿»'ементаки 003 в процессе функционирсванич приводит к расширению функций каналов связи, которые становится активными элементами. Это приводит г. тому, что в системах ИИ становится неиозможнкм проложить четкую грань между" "обработкой" и "конкутациеи", что позволяет говорить не просто о коммутации. а о "коммуникации" и коммуникационных средах (KMC) СОЗ.

Требования к KMC СОЗ должны быть формализованы о применением никоторого аппарата, позволяющего . перейти к анализу и синтезу-г.оммуникациоцных сред. С данной точки зрения интерес представляет аппарат автоматов о .программируемыми процессом, структурой и коммутацией. СОЗ можно описать в виде некоторой алгебраической структура (ОЛ) > где Q - 0ц) O^J — множество объекте: ,

определенны*, в данной системе, V - ^ V/,> Vz-, • V- множество коммуникационных отношений, определенных на множестве 0 .

Ka«Lдый и^ элементов множества 0 представляется в виде неко"орог-о нжаипа С i , оодпржшцего описание объекта, множества входов X г j^-Xj • <■ \ ,VIJ" , нл котором когут бить задакы

коммуникационные ц,"нотеиич, описываемые множеством алгебраических структур Н г h > , . , и множества выходов У1 ^^f у уг ^

Анализ показывает ч . о кыяди-н из uj ^ментов множества 0 может бить реализован в виле иоьокупносгти подавтоматов с прог-раюдаруеиой структурой и коммутацией, объединенных коммутационной сетью. Множести«, коммутацио1>ных отношений V также реализуется о виде совокупное ги подавтоматов с программируемой структурой ■ и коммутацией, объединенных никоторой коммутационной оугьо.

В целом СОЗ представляется в вяде структурированной систем, элементы которой реализуют множества концептов С ', коммуникационных отнесений на входах концептов Х/п^, йсымукиЕпциогаес!

отношений \ = •} VV ^ I % j ... ^ , а также коггегх коммута'!иокггдх сетой,

сС.сспсчииающих связь между подсистемами различного уровня иерархии или различного Фхгнкционально{х> назначения.

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

Ко rm^psftf толкла, iia oüHoiie предлагаемого в пврцои разделе подхода к анализу СОЗ, разрабатывается модель когшуникашюкмой системы с элементами структурной самоорганизации.

Естественнонаучный ' подход ' к ' рвссмотрслзсо проблем опирается иа методологию, в' основе Которой лекнт , стремлешги „ расчленить сложную проблему на ряд независимых задач, то есть рассиатрЯвагвдая проблема представляется в виде некоторой ¿истекал, попе Деки s и' фуигздш которой определяются че[>еэ поведение и функции еа подсистем. При изучении мозга. такой подход пригюди'г к- появлении иогих проблем, сложность которых оказывается, соизмеримой с сложностью основной. ЦязяНае своИство является одним Из основных характеристик слоеных ' систем -- трудность представления ее а ' виде s структурированной системы с обозримым числом иерархий и подсистем, Таким образом, современный уровень представлений о мозге ' требует целостного подхода к рассматриваемой проблеме, .. когда •одной из важнейших' характеристик системы признается ее целйстность. Большое . ' место ' проблема целостности 'занимала в -гворчестве A.A. Ухтомского, который. -впервые -экспериментально и теоретически обосновал основной принцип деятельности ЦНС; - принцип домшщят. С то.чки зрения принципа доминанты важнейшей характеристикой интеграционных процессов - ЦНС является способность осуе;ествлять в дашшй момент врбмецм одну определенную Форшу адаптивного поведения.

Принцип доминанта относится к области меясистемных отношений. Он описывает, мелашзм , активизации наиболее ваыюй системы и подавления конкурирующих, обеспечивая саму возмоаность реализации реакции. Однако он .fie может определить характер реакции, семант*ическую нагрузку, которую несет данная доминанта. Характер , реакции должен определять д[jytxjü принцип, определяющий уже характер внутрисистемных отношений. Таким принципом может служить - принцип детерминанты- Коадая Физиологическая реакция осуществляется по определенному алгоритму, который специфичен и' присущ только данной реакции. Для актипизоции алгоритма требуется появление соответствующих раздражителей в среде или определенная степень возбуждения мотивационных центров, то есть такой "алгоритм тахяе является продуктом интегратчвней деятельности ЦНС

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

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

- установление канала связи. СНКМС должна обеспечивать установление коммуникационного канала связи. Условия, при которых пргисхогит установление какала описываются алгоритмами Функционирования СНККС;

- активизация канала связи. При выполнении ряда условий, описываемых алгоритмами функционирования, должна происходить активизация определенных коммуникационных каналов связи СНКМС;

- разрушение каналов связи. Если Ьекоторые из коммуникационных каналов связи не активизируются в течение определенного промежутка времени, СНКМС должна обеспечить их разрушение;

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

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

в трвта-оу р'чтг*""', на основе предлагаемой во втором разделе модели ко*шунмкациожой системы, разрабатываются структура СНКМС, автоматные и логические модели коммуникационных процесоов в СНКМС. На верхнем уровне иерархии СНКМС представляется в виде коммуникационной системы, с многослойной структурой - Рис.1а. Здесь подсистема L1 служит для образования и функционирования коммуникационных каналов саязи первого типа, отражающих активность моделей входных воздействий (КВВ). Возбуждение какой-либо из МВВ означаот, что ситуация, отражаемая моделью представляет интерес для системы, и- она должна предпринять че которые действия в ответ на ее возникновение, что . осуществляется через возбуждение некоторых из моделей выходных воздействий (МВЫВ). В функции подсистемы L2 входит сохранение в

а)

5)

Рис. 1

течение определенного промежутка времени следов ахтиинооти данных моделей. Кроме сохранетая следов шгнвшхян МВВ и МВШЗ, в функции подсистем Ы и Ь2 входит и организация каналов связи между ними. Это приводит к необходимое™ проектировать КС, . которая позволила бм осуществлять передачу возбуждения между элементами.СНЕМС-

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

я Ч^ГЧгРт* Р«им» разрабатывается коммутационная сеть гиперкубической топологтта типа "двоичная тапершина" (ГИ-п). Каждой вершине гиперкубического графа ГК—п в Пй-п ставится в соответствие шина, каждому ребру - обрабатывающий элемент (ОЭ). На Рис.16 приведена структура ГШ-3, построенная на основе ГК-3 с Н=23 узлами. Каждому ОЭ ГШ-п ставится в соответствие номер (хл-х. .. ШхУх] ..-Хи), который означает, что ОЭ присоединен к двум шинам (хг.-х- . .их.. .же) и (Хп-1.. .VI...ха).

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

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

Первый заключается в организации распределенной обработки информации, при котором Функции ОЭ ГШ-п оказываются распределенными

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

Ьторсй подход заключается в введении дополнительных каналов связи. Он позволяет, оставаясь в рамках гиперкубической топологии, значительно увеличить коммутационный ресурс сети. При этом удается 4cn0flb30j3aTb сильные стороны сетей ГШ-n и ГК-n. Колииеспю порт-о в ввода/вывода в норой сети но зависит от дипмечра сети. Cfcra сохраняет все топологические характеристики, присущие семейству гиперкубииоскюс сотой. Базисные алгоритмы обмена донными строягся комбинированием соответствующих алгоритмов маршрутизации ь ГШ-n и ГК-n, каждый из которых работает на своем уровне иерархии. Коммутационная сеть кокет быть использована в качестве компромисса мекду требованиями, предъявляемыми к быстродействию проектируемой сети и технологическими ограничениям: СБИС-реализации.

В приложении на основе синтезированных в четвертом разделе автоматов с программируемыми структурой, процессом и коммутацией строится имитационная модель и проводится экспериментальная проверка предлагаемого подхода к проектирования» СНКМС СОЗ.

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

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

В результате накопления опыта функционирования в внешней среде и появления в СНКМС новых коммуникационных каналов, телехка оказывается в состоянии выработать стратегию преодоления "препятствий".

ЗАКЛЮЧЕНИЕ

На основе анализа задачи предстааясния и манипулирования знанияии в диссертационной работе предлагается модель нейрофункциональной коежзукикациокной с ролл скстеиы eSpaSui'Ei загний. Исследование

коммуникациоига£х отношений з системах ИИ проводится на осног«> atmspca ii автоматов с npcrpat^avpyetaü^-i структурой, коммутацией и процессом, гибкость которого позволяет получить форгшлизоишшео поз дставгентз проблемы создания Еокмуникацкокной среды CU3.

На основе анализа Е.оьагукнкацнонньгх отнойю1шй в центральной нервной система человека и езктеих гмиоткых разрабатывается г^одель коммуникационной среди СОЗ, в готсрой процессы образования .таекх сэяззй í-'езяу объектами происходит на основе процессов структурной самоорганизации. Это позволяет говорить о самооргониэуъзщихсл иейрофункцнсиальиых коммукнпацно;яс£х ерэдах (СНККС).

Обеспечение необходимых функций СНКМС требует создания мощной КГ., обвепечгезеигззй обкзгс/ данными нелду подсистемами CHHíC. Принципиально большое число объектов, обмен кзгду которыми долгзга обеспечить КС делает невогноиккк проепирогяч1т полнодоступной сети. В качестве: компромисса предлагается КС тспологки "двоичная щпернптна", позволяющая отображать на себя обмены по полному графу. Для предлагаемой сети разработали соответствующие алгоритмы обмена даншдаи и предложена пути ' повышения, эффективности КС за счст организации распределенной обработки информации или введения дополнитзльн^гх каналов связи, не разкыгызfiaix топологию сети.

1. Каляев A.B., Бозич В.П., Арэуманян Р.В. Коммутационная сеть топологии двоичная гипершина//Нногопроцессорнь!е вычислительные структуры. Вып. 14(XIII). Таганрог: ТРТИ, 1992, - С.1В-23

2. Бокич В.И., Арзуманян Р.В. К построению коммуникационных систем с элементами структурной самоорганиззщад.//II Всероссийский научно—тезсагческил семинар "Кенрокомпькггерные технологии и пути их использования при создании специальных технических комплексов, г.Курок, 1993, - с.12-20.

3. Боасич В.И. , Арзуманян Коммуникационная сеть с топологией "двоичная гипершина"//Х11 ' Всесоюзный семинар по однородным вычислительным среден и систоличаским структур®^*- - Препринт ИГ1ГО5М АН УкССР, Нв 3-91, Львов, 1991, - с.12-16.

4. Аргумшшн Р.З. , Анализ коммутационных возможностей сети тополог.™ "д.личная шина" //XIV Семинар по однородным вычислительном средам и снстоготесгим структурам- - Препринт 1иТШ-"1 АН УкССР, Н° 6-92, Львов, 1992, - с. 15-20.

й. Арзуманял Р.Б. Распределенная обработка информации в коммутационной сети типа "двоичная гипьрсина"//ХУ Семинар по однородным вычислительным средам и систоличоскии структурам. — Препринт ИППММ АН УкССР, N0 8-92, Львов, 1992, - с. 10-14.

П. Лохич fJ-И. , Арзуманип Р.В. Г.оммутационная сеть топологии двоичная 'гигюршина с дополнительными гиперкубическими каналами свя:>и. //Многопроцессорные ва^чиолительвые структуры. Таганрог: ТРТИ, ШУЗ.

7. Еохич П.И., Арзуманян Р.В. , Ереыенно tä.A. Гиперкубичаская архитектура нейрокомпьютера с распределенной обработкой информаиии//1I всероссийский научно-технический семинар "Цо.йрокомпыатерные технологии и пути их использования при создании специальных технических комплексов х*. Курск. 1093, - c.S-i.Z.

8. Божич В.И., Арзуманян Р. В. Использование нейрокомпьютеров в пнтоматизирос«анных противопожарных и аварийно-спасательных сис:темах//Секцин "Информатизация систем бэзопасности" III конгресса "Информационные коммуникации, сети, системы и технологии" Международного Форума информатизации, . Москва, 1992, - с.115-117.

Личный 1<кл<1д__шпард £>,саше.ехные лабахы:

в l1, 3] разработаны алгоритмы обмена данными "один-к-одному" и "один ко всем" в коммутационной сети топологии "двоичная гилершина", в [2] - разработана модель коммуникационной системы и алгоритмы, обеспечивающие процессы структурной самоорганизации в предлагаемой модели, в Е03 — разработана коммутационная сеть "двоичная гипершина с дополнительными гиперкубчческими каналами связи" и алгоритма обмена дшшимм в ней, в [7] - предложен гиперкубический интерфейс "двоичная гипер>аина с распределенной обработкой информации".

ОП ТРТИ. Зак.43? Тир. 100 ,

'Ш

с"

РГб од

] ' л I! г

НАУЧНО - ИССЛЕДОВАТЕЛЬСКИЙ ЦЕНТР

ЭЛЕКТРОННОЙ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

НА правах рукописи УДК 681,323

ФРЕНКЕЛЬ СЕРГЕИ ЛАЗАРЕВИЧ

ВЕРОЯТНОСТНЫЙ МЕТОД ОЦЕНКИ ПОЛНОТЫ ТЕСТОВ КОНТРОЛЯ ЦИФРОВЫХ УСТРОЙСТВ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 1994

Работа выполнена в ГНПП "Импульс" (г. Москва),

Консультант:

- кандидат технических наук,

ст. научный сотрудник Святский Б.А.

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

- доктор технических наук, профессор Татарников в.ю.

- кандидат„технических наук, доцент Кривошапко в.М.

Ведущее предприятие: ИНЭУМ, Г, Москва

Защита состоится "-"-—1994г. в •—г- часов

на заседании специализированного совета Д115.01.01. НИЦЭВТ Москва, 113403

С диссертацией можно ознакомится в библиотеке НИЦЭВТ

Автореферат разослан "----:-1994г.

Ученый секретарь специализированного совета Д115.01.01. доктор:технических наук, профессор

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

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

Цель работы. Основной целью выполненной работы является:

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

-Теоретический анализ вероятностных методов оценки полноты тестов, основанных на результатах моделирования исправных схем; ; , 1 ' ,.■•/.'

-исследование сходимости вычислительных процедур, лежащих в основе вычисления вероятностей обнаружения неисправностей по результатам моделирования исправных схем,-

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

повысить эффективность использования вероятностных методов оценки полноты, базирующихся на результатах моделирования исправных схем, а именно:

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

-повысить скорость вычисления для схем с памятью;'

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

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

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

-предложена классификация вероятностных методов оценки обнаруживаемое"™ неисправностей ;

-Исследованы математические модели, используемые для вычисления вероятности очувствления пути для неисправности на линии вентильной сети, на заданной входной двоичной последовательности;

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

- предложен новый подход к анализу качества вероятностных оценок наблюдаемости линий цифровых схем;

- выявлены и описаны различные Факторы { в терминах структурно-Функциональных свойств вентильных сетей), влияющие на точность вероятностной оценки полноты, и на точность построения списка необнаруженных неисправностей;.

точность построения списка необнаруженных неисправностей;

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

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

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

существенно повышающей его эффективность, а также в реализации на основе полученных результатов программных средств, использованных • при построении тестов контроля ряда изДелий. разрабатываемых и выпускаемых в ГНПП " Импульс" в 1985г1991гг., а также на ряде других предприятий.

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

Республиканская научно-техническая конференция "Автоматизация проектирования средств вычислительной техники и радиоэлектроники". Каунас, июнь, 1985,'

- Отраслевой семинар , "Автоматизация средств контроля и диагностики РЭА". Москва, декабрь. 1987г.,

- Всесоюзный семинар "бпыт и практическое использование систем автоматизированного проектирования (САПР)", Москва, 2426 сентября, 1987г.,

-Зональная конференция "Математические и программные методы проектирования информационных и управляющих систем", Пенза, 26-29 мая, 1990г..

- Конференция по автоматизации проектирования "АРК91". Каунас 3-6 июня, 1991г,

2nd International Design Automation Workshop ("Russian Workshop92"). Moscow. June 29-30, 1992.

("Russian Workshop93")., Moscow, July 19-20, 1993, а также на семинарах в ГНПП "Импульс", ИЛИ РАН.

Публикации. По теме диссертации опубликовано 9 печатных работ.

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

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

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

- вычислительная сложность метода относительно методов оценки полноты, основанных на моделировании неисправностей:

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

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

Для строгого изложения и, анализа методов. Фиксируется смысл используемых при описании анализируемых методов понятий, а также вводятся ряд дополнительных понятий.

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

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

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

Функцию. и при этом учитываются некоторые топологические особенности вентильной сети;

- конечно-автоматные методы, вычисляющие

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

На основании выполненного анализа рассмотренных методов делается вывод, что указанным выше критериям выбора метода оценки полноты в наибольшей степени удовлетворяют методы, основанные на оценке полноты тестов по результатам моделирования исправной схемы. В данных методах вычисление полноты контроля заданным тестон выполняется по значениям оценок вероятностей обнаружения неисправностей, впервые предложенных авторами статистического метода оценки полноты STAFAN (Statistical Fault Analysis). ВГдиссертации эти оценки названы STAFAN-оценками соответствующих вероятностей. Используются следующие STAFAN-оценки:

- Cz(m) - оценка вероятности установки линии m вентильной сети в логическое значение z-0 или 1 соответственно. Эта величина называется 0 или 1- управляемостью линии т.

Bz(m)- оценка условной вероятности создания существенного пути для логического значения z на линии m на случайно выбранном наборе тестовой последовательности. Bz(m) называется 0 или 1-наблюдаемостью линии т.- Dz(mj»Cz(n>)Bz(to) - оценка вероятности обнаружения неисправности m/г на случайно выбранном в исследуемой тестовой последовательности входном наборе, где га-линия вентильной сети, z ' - логическое значение, соответствующее данной константной неисправности("Константа О"

или "константа X"), г- инверсное логическое значение;

- Xz(m)- вероятность обнаружения ОКН m/z хотя бы на одном наборе тестовой' последовательности

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

. 1

fc- -Е Xz(m) (1).

NF (m,z)

где <m,z> - множество неисправностей из - рассматриваемого списка одиночных константных неисправностей в схеме, NF-число данных неисправностей в схеме.

Величина Cz(m) вычисляется непосредственно по результатам моделирования схемы. Bz(m) - череэ величины Cz(m) и S(m)-оценку вероятности активизации пути со входа m вентиля на его выход. При этом алгоритм вычисления Ez(m) представляет собой обратный проход с выходов сети ко всем линиям схемы, с вычислением на каждом шаге значений наблюдаемости входа m вентиля по известно* значениям наблюдаемости выхода вентиля и значениям Cz(m),,S(m). Наблюдаемость Bz(f) любого выхода f сети считается равной 1..при Cz(f)>0 , и равной о при Cz(f)=o.

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

следующие группы вопросов:

- Формализация оценки точности методов. основанных на STAFAN-оценках вероятностей;

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

-Формализация процедуры построения списка необнаруженных неисправностей.

В главе 2 изучаются математические свойства STAFAN-оценок. и их связь с различными характеристиками• схем и

тестовых последовательностей.

Основные результаты данной главы относятся к исследованию адекватности бТАРАН-оценок для одиночных константных неисправностей в схемах с различными структурно-функциональными свойствами и излагается в следуюяих пунктах. 1. Исследована адекватность ЗТАГАН- оценки вероятности обнаружения неисправности линии. связанной с выходом сети простым путем. Необходимость такого исследования обусловлена тем. что указанная £5ТАРАИ-оценка вырааается через вероятности очувствления соответствующих простых путей.

Показано, что используемая в ЭТАГАИ методика, вычисления Вг(га) не приводит к вычислению условной вероятности наблюдаемости линии т. т.е. условной вероятности того, что для асех вентилей пути выполняются условия очувствления на входном наборе, на котором литая т установлена в проявляющее для неисправности т/г значение. Из этого результата следует вывод, что погрешность вычисления г-наблюдаемости Вг(т) имеет модельный характер.

В связи с полученным результатом. ставится вопрос о критериях оценки точности БТАГАМ-оцекок и рассматриваются возможные подходы гс выбору критерия качества. Показывается нецелесообразность использования принятых в математической статистике характеристик достоверности для исследования эффективности ЗТАГАК - оценок. Показано, что применимость ЭТАГАН-оценки для конкретной неисправности удобно охарактеризовать с помощью следующего понятия!

ЗТАГАИ- оценка адекватна для неисправности т/г, если:

а) 02(тп)>О н т/г обнаруживается на исследуемом тесте.■

или

б) П2(т)-0 и т/г не обнаруаивается на исследуемом тесте. Свойства БТАКАМ-оценок для неисправностей участков схем с различными Функциональными я структурными характеристиками изучаются с ~ точки зрения их влияния на адекватность« в указанном смысле). Показывается, что если на исследуемом тесте для неисправности т/г на линии т древовидной сети вычислено значение 0г(ш)-0, .то данная неисправность непроверяема на тесте, т.е. нулевая ЭТАГАН-оценка йг(т) ■ адекватна для данного класса непроверяемых неисправностей. При этом ненулевые значения ЭТАГАН-

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

2.Показано, что для неисправностей в узлах сходящихся разветвлений адекватность " STAFAN-оценок в общем случае определяется распределением логических значений в их ветвях на входных наборах исследуемой тестовой последовательности. что связано с хорошо известными явлениями "самокаскирования неисправностей" (self-marking" (SM)). и многомерного, пути распространения ("multiple path propagation" (МРР)). При этом явление самомаскирования приводит к неадекватности STAFAN-оценок для необнаруагиваемых неисправностей в узле сходящегося разветвления, а ММР - к их неадекватности для обнаруживаемых на исследуемом тесте неисправностей.

3. Рассматривалась применимость STAFAN-оценок для неисправностей на линиях участков вентильных сетей с обратными связями. ( максимальных сильносвязных подсетей -JICCП ). В этом случае проблема применимости возникает уже на уровне структуры _ события, соответствующего проверяемости неисправности. Дело в том. что в общем случ'ае данное событие в последовательностной схема может быть представлено только на некоторой последовательности наборов теста, в то время как Dz(m) вычисляется как вероятность создания существенного пути для неисправности на случайно выбранном ■из входная последовательности) наборе. Тем, не менее. как

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

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

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

Причины неадекватности STAFAN-оценок для неисправностей на линиях последовательностных схем ножно условно разделить на два класса. Один из классов соответствует Факторам, которые приводят к неадекватности оценок для неисправностей комбинационных схем. а именно, явлению несинхронности очувствления различных участков путей, и наличию SM и МРР-эФФектов. Наличие второго класса причин связано с тем. что существуют неисправности, которые могут быть проверены на последовательности двух' наборов, являющихся для данного контура установочными, и при этом алгоритм STAFAN приводит к вычислению нулевых значений Dz(m), т.к. ни на одном из наборов через контур не активизируются простые существенные пути.

4.Рассмотрен вопрос о точности вычисления Xz<m)- вероятности проверяемости неисправности хотя бы на одном наборе теста. Исследуется правомерность предложенной в STAFAN модели представления погрешности, как смещения оценки вероятности хотя бы одного успеха в последовательности независимых испытания.'

Показывается возможность интерпретации вероятности D2(m). как вероятности успеха в указанной последовательности-испытания. и правомерность используемой авторами STAFAN аппроксимации выражения для ошибки смещения. Ввиду того, что вероятность Dzim) вычисляется в STAFAN в рамках соответствующей вероятностной модели, а не ' оценивается по результатам

статистического эксперимента делается вывод о правомерности определения STAFAN. как вероятностного метода. 5.Рассмотрены возможные подходи к Формализации оадачи принятия решения об обнаруживаемое™ одиночной константной

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

Задача Формулируется следующим образом: выбрать пороговое ¡значение q вероятности Xz(mj таким образом, чтобы обеспеченить минимальные вероятности следующих ошибок:

а) "ud->d" - ошибки отнесения необнаруясиваекой на тестовой последовательности OICH к проверяемой, при применении порогового правила:

ОКН m/z обнаруживается на данном тесте, если Xz(m)>q,

(2)

ОКН m/z не обнаруживается на данном тесте, в противном случае;

б1 "d->ud"- ошибки отнесения обнаруживаемой ОКН к необнарушшаемой, при применении указанного порогового правила. Делается вывод, что . для решения данной задачи необходима модификация метода STAFAN.

Выполненный в главе 2 анализ адекватности STAFAN-

оценок является основой для оценки точности решения задачи

интерактивного построения тестов с использованием

вероятностного метода оценки полноты.

В главе 3 исследуются вопросы сходимости процесса

вычисления STAFAN - оценок для сетей с обратными связями.

Показывается, что задача вычисления z-наблюдаемостей линий ИССП

по алгоритму STAFAN эквивалентна решению системы нелинейных

уравнений с L-I уравнениями, где L- число элементарных контуров

в МССП, I- число элементов в пересечении многеств линий ИССП.

являющихся выходами элементарных контуров. Исследуются свойства

правых частей уравнений. определяющих сходимость итераций.

Доказано следующее свойство решений:

При любых начальных условиях иэ {0,11, итерации сходятся к

вектору решения х-(х(1),х(2).....хОО). где k-число строк в

системе уравнений, такому, что для всех координат вектора

справедливо;. п 1

х (i) < x(i) i Xlli).

где х°(а)- 1-я координата вектора, к которому сходится решение при нулевом начальном приближении (т.е.нулевых

начальных значениях всех переменных), х1 (1) -соответственно, при единичном начальном приблиаеиии. Доказана сходимость итерационного процесса с вероятность» 1 к единственному решению при любых начальных приближениях из [0,11, при единичном значении эмпирического коэффициента а . учитывающего в ЗТАГАН степень зависимости событий, связанных с активизацией простых путей, образующих узлы разветвлений а рассматриваемой сети (значение а=1 соответствует предположению об их независимости ). Полученные результаты показывают принципиальную возможность использования ЭТАГДЫ-оценок для произвольных схем с памятью. При этом отмечается, что скорость сходимости итераций для сложных контуров может быть довольно медленной, и зависит от организации итерационного процесса. Это обстоятельство указывает на актуальность задачи повышения быстродействия вычислений БТАГАМ-оценои.. решение которой излагается в главе 5.

В Главе 4 - исследуется влияние .различных Факторов на точность _оценки полноты контроля по результатам моделирования исправной схемы с использованием ЭТАКАЯ -оценок. Погрешность БТАГАМ- оценки полноты представляется следующим образом: =1/НР( £ а (ш\2) +Е а (т/2) ) » Ес1+Еи (3)

гп/гсГа. т/геГи

где-.

е(т\2)- погрешность', вносимая в суммарную

погрешность оценки полноты (относительно точного значения, которое могло бы быть вычислено по результатам моделирования схемы с неисправностями) значением вероятности Хг(т) каждой из неисправностей щ\2 в Формуле оценки полноты (1). Гй-мнонество обнаруживаемых на тесте неисправностей, Ги- множество необнаруаиваемых неисправностей. Ей- суммарная погрешность, вносимая оценками Хг(т), вычисленными для обнаруживаемых неисправностей. Ей- суммарная погрешность, вносимая в оценку полноты значениями Хг(т), вычисленными для необнаруживаемых неисправностей.

Слагаемые в (3) могут вносить как положительный, так

Слагаемые в ГЭ) могут вносить как положительный, так и отрицательный вклады в оценку погрешности. Соответственно,. структурно-Функциональные свойства участков сети, определяющие адекватность STAFAN- оценок для неисправностей на принадлежащих им линиях, и математические свойства STAFAN-оценок могут характеризоваться согласно знаку погрешности, вносимому в (3) соответствующим слагаемым :

причина неадекватности знак, вносимый в погрешность

"несинхронность" (в комбинацион-. ных и последова-тельностных схемах) . . +

"Самомаскирование" в узле схрд.разт ветвления +

"множественный путь распространения" -

неисправности в контурах,проверяемые на установочных наборах -

смещенность оценки Хг(т).

Взаимная компенсация вкладов в погрешность в выражении (3) является одной из причин, обеспечивающей высокую точность БТАГАН-оценки полноты, несмотря на то, что используемая вероятностная модель во многих случаях противоречит логическим условиям очувствления комбинационных и последовательностних путей. Другая причина состоит в , том. ■что ряд Факторов, определяющих данное ■• противоречие, проявляется крайне редко в реальных схемах на реальных тестах. Прежде всего. это относится к явлениям "самомаскирования" и "многомерного пути распространения" в узлах сходящихся разветвлений. Делается вывод. что отмеченный компенсационный характер точности оценки полноты может приводить к ошибкам при решении второй подзадачи общей задачи построения тестов -

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

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

Обоснована возможность использования единичного' значения коэффициента «, а также получено уравнение для. выбора величины эмпирического ■коэффициента, используемого для уменьшения ошибйи смещения при оценке вероятности Х2(т).

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

1. Возможность расширение базиса •сетей основана на

использовании общего выражения , для условной вероятности

создания сущертвенного пути со входа i на .выход модуля,

реализующего булеву Функцию п переменных F(х,...,х ), где i- вход, соответствующий переменкой Xj:

I D{x.-z) I . PCSXj/Xj-Z)- ---—--

i Fi<2»l

где Sxj- событие, состоящее в очувствлении пути со входа х4при наличии на нем логического сигнала z на выход модуля,

DiXj-z)- множество входных наборов, на которых.

Fix,---- (x.-z)» 1....x)-/=F(x.____lx.-z),. .х„) ,

1 . 1 П 1 1 n

F (z) - множество входных наборов, на которых х -z. i i

• -сложение по Mod 2.

Данный подход использован • для сетей, . ' содержащих помимо элементарных вентилей, также и 'элементы И-ИЛИ-НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ. При этом вычислительные затраты по сравнению со случаем преобразования данных компонентов в сеть элементарных вентилей не возрастают. Полезность такой доработки объясняется тем. что данные элементы, как правило, содержатся в доступных разработчику тестов Функциональных

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

2. Ускорение вычислений STAFAN-оценок для схем с памятью ноано обеспечить, отказавшись от использования итераций по значениям z-наблюдаеиоствй контурная линий.

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

Для реальных схем число простых путей мосет быть очень велико. Предложена и обоснована процедура сокращения числа простых путей, обрабатываемых при вычислении Вг(пО узлов разветвления я линий контуров. Возмогность такого сокращения основана на. свойствах z-наблюдаемостк узлов разветвлений; как Функции от z-наблюдаемостей образующих их ветвей, что позволяет отсекать простые пути. вычисленное значение наблюдаемости по которым на данном шаге реализации алгоритма STAFAN квге некоторого заданного значения.

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

В главе б. рассматривается возможность обоснованного

построения списка необнаруженных неисправностей по

информации, получаемой при моделировании исправной схемы.. При этом используется тот Факт, что практически вычисление ЗТАГАН-оценок выполняется по интервалам, на которые разбиваются тестовые последовательности, т.е. на каждом интервале с номером 1 длиной N1 входных наборов вычисляются свои величины Сг(тЛ), Вг(т,1), Ог(т,д), 1-1.к, где к- число интервалов, и вероятность Хг(т) вычисляется, как:

к (1-0г(тЛ))т Хг С1) - 1-П -:-:

где «(...)-•поправочный множитель, зависящий от значений N1 и Ог(ш.:) на ¿-я» интервале, а также от некоторого эмпирического коэффициента ь, выбор которого рассмотрен в. главе. 4. поправочный множитель . вводится с целью уменьшения ошибки смещения оценки данной вероятности. Заметим, что . длины интервалов разбиения берутся одинаковыми. Приведенная Формула определяет наличие следующего свойства у ЭТАРА№-оценки вероятности Хг(т):

значения Хг(т)>0 тогда и только тогда. когда хотя бы на одном из интервалов 1 разбиения тестовой последовательности Т)г(и,1)>0. Показывается, что для неисправности на" линии

древовидной сети, из данного свойства следует, что уменьшая вероятность события "0г(т.1}>0". уменьшается вероятность ненулевого значения Хи(т) для ' необнарукиваемой на данном тесте неисправности. При этом веротность ошибки й->ш! не возрастает. Показывается, что ввиду невозможности оценки с приемлемой точностью различных ' условных распредилений вероятностей для ошибок иа-М. а->ис1. необходимых для строгого ( с точки зрения математической статистики) решения задачи выбора порога в пороговом правиле (2), предпочтительный путь решения задачи построения, списка необнаруженных неисправностей состоит в следующем:

тиспользовать нулевой порог (д»0 в правиле 2). т.е. считать неисправность обнаруживаемой, если Хг(т)>0. и необНаруживаемой - в противном случае;

длину интервала N1 выбирать исходя из условия ограничения вероятности ошибки ий-М (при я=0К оценка сверху которой может быть выражена через значения V(э)— частоты активизаций путей

через каждый из вентилей j. входящих в состав простых путей, проходимых при реализации алгоритма STAFAN. При этом для неисправностей древовидных участков сети гарантировано отсутствие ошибки типа d->ud.

Снижение вероятности оикбки ud->d достигается уменьшением интервала N1. В этом случае, однако, для неисправностей на линиях, принадлежащих многотакткым последовательностныи подсхемам возможно появление ошибки типа d->ud, если Ni < td, где td -минимальное число тактов входной последовательности, которое необходимо для создания существенного пути для рассматриваемой неисправности.

В случае же комбинационных схем, время вычислений STAFAN-оценок увеличивается с , ростом числа сегментов ]T/Ni[ разбиения теста, что также может рассматриваться как условие ограничения снизу длины интервала. Предложена нетодика компромиссного выбора величины Ni.

Ошибка ud->d при использовании нулевого порога однозначно определяется долей необкаруживаемых на исследуемом теста неисправностей, для которых были вычислены ненулевые значения Xz(m). Таблица 1. показывает влияние длины интервала Ni на долю непроверяемых окн. с ненулевыми Xz(и):

Таблица 1.Зависимость числа ошибок ud->d и точности вычисления полноты от длины интервала разбиения теста.

схема ♦NF. #ud->d NÍ; |í| t/to % тип схемы

■ 1 642 146 28 28 50 80 20 1054 1 1.75 4.9. -4.1 -4.9 -5.3 последов,

2 1750 32 28. 28, .139 80 20 139. 1 1.4 - 0.9 -1.1 -1.1 комбинац

3 1307 132 46 34 294 80 20 294 -Д - ' >2.1 1.7 +2.1 +2.4 -3.1 последов.

Здесь:' ♦ud-M-число необнаруженных, неисправностей с Xz(rn) >0, при данном Ni,

| Т | -длина тестовой последовательности.

N1- длина интервала . разбиения тестовой

последовательности.

t/Ъ0 - относительное увеличение времени оценк» полноты относительно времени оценки при |Т|/Н1-1.

число неисправностей в схеме, АГс- относительная погрешность оценки полноты относительно метода параллельного компилятивного моделирования.

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

В главе 7 рассматривается программная реализация

предложенных подходов к вычислению ЭТАКАЯ-оценок и методология

1 ■

использования вероятностной оценки полноты при интерактивной разработке тестов. Программы реализованы на языне ПЛ/1. как составная часть программной системы синтеза тестов контроля цифровых устройств АССТ-ЕС. Данная система является реализацией в среде ОС-ЕС 6.1 на ЭВМ ЕС-1045 существенно модифицированной св части входных языков, средств ведения библиотек, а также возможности иерархического описания схем) широко известной Автоматизированой Системы Синтеза Тестов . ( АССТ ). Подсистема вероятностной оценки полноты

использовалась, наряду с входящим в состав АССТ-ЕС модулем оценки полноты . на основе параллельного компилятивного моделирования (ПКМ) для построения качественных

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

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

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

Таблица 2 иллюстрирует снижение затрат машинного времени на оценку полноты, по сравнению с ПЕК, а также с ранее предложенным методом вычисления ЭТАГАЫ-оценок. достигаемое благодаря использованию предложенным модификациям.

таблица '2

N0 #<3 «иг »бР тъ сек ¡с, V,» Д^ с/с |Т|

а ь- с Ь с

п 201 6 2 43 29 23 84.3 -3.2 -2 9 69

б 249 28 8 604 216 165 63 +8.2 -2 1 370

6 374 0 0 184 161 147 97.7 +1.8 +1 б 139

здесь:

столбцы а, Ь, с-соответствуют ПКМ, ЭТАГАИ. и предложенной в диссертации модификации вТАГАИ, N0- условный номер схемы,

#в- число элементов в схеме(включая И-ИЛИ-НЕ,

ИСКЛЮЧАЮЩЕЕ ИЛИ).

♦КЗ- число Я-Б-триггеров,

число глобальных обратных связей. «Тт- общие затраты машинного времени. ¿а- полнота контроля построенным тестом, А ^-погрешность оценки полноты относительна ПКЫ. IX}— число наборов в тестовой последовательности.

Делается вывод, что накопленный опыт использования БТАГАН-оценок при интерактивном построении тестов на базе ЭВМ с небольшой (по современным понятиям) производительностью и оперативной памятью, показывает целесообразность реализации данных подходов на ПЭВМ.

В приложении дан 'акт о внедрении данной подсистемы.

. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

1. Исследована теоретико-вероятностная модель,

соответствующая эвристическим вычислениям вероятностного метода оценки полноты тестов БТАКАН. . Показано, что вычисляемые

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

2. Обоснованы критерии адекватности ЭТАКЛИ - оценок вероятностей обнаружения одиночных константных неисправностей в вентильных сетях.

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

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

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

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

7. Предложена Формализованная методика построения списка необнаруживаамых неисправностей.

8. Разработаны программы, реализующие вычислительную процедуру вероятностной оценки полноты тестов,на основе соответствующим образом модифицированной вычислительной процедуры СТАРА!*, для цифровых устройств, описанных в виде сетей элементарных вентилей и элементов И-ИЛИСНЕ,ДА), ИСКЛЮЧАЮЩЕЕ ИЛИ. Данное программное обеспечение включено в состав широко используемой Автоматизированной Системы Синтеза Тестов (АССТ).

9. Разработана и обоснована методика использования вероятностных методов оценки полноты на базе моделирования исправных схем в интерактивном синтезе тестов для цифровых устройств.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Френкель С.Л. Автоматизация поиска неисправностей в цифровых устройствах // Передовой производственный опыт, 1984. стр.9-12.

-2Ö-

2. Френкель С.Л. Подсистема САПР разработки тестов контроля и диагностики неисправностей в цифровых. устройствах на микропроцессорных ВИС. // Опыт и практическое использование систем автоматизированного проектирования. Материалы Всесоюзного научно-технического семинара, Москва, 24-26 сентября 1987г., стр.99-100.

3.Френкель с.Л., К вопросу об оценке контролепригодности цифровых схем, // Тезисы докладов к Всесоюзному семинару " Измерение я контроль в РЭА",М.:,1987, стр.101-103.

4.Френкель С.Л. Об одном вероятностном методе оценки

полноты тестов контроля цифровых устройств //Методы и средства автоматизации проектирования средств вычислительной техники, м.!. Тр.ИНЭУМ,1988, С.166-173.

5.Гробман Д.U..Френкель С.Л.. О сходимости итерационного процесса вычисления вероятности событий в логических сетях с обратными связями // Математические и програмные методы проектирования информационных и управляющих систем. Тезисы докладов к зональной конференции, 28-29 мая 1990г., стр.41-42.

6.Френкель С.Л. О возможности использования вероятностных методов оценки полноты в интерактивных системах синтеза ^тестов // Конференция по автоматизации проектирования "АРК91". Каунас. З-б июня, 1991г., стр. 132-136.

7.Френкель —С.Л«--.- О возможности использования ПЭВМ для решения задач синтеза тестов контроля цифровых устройств // Системы и средства информатики. М. •. Наука, вып. 4.1993. стр.283-290.

; 8.Frenke 1 S.L. Problem of- fault. classification by usage .Of statistical' method, of fault coverage for. sequential, circuits. // Proc. 2nd International Design Automation

Workshop ("Russian Workshop 92"). Moscow. Juno 29-30 1992. pp. 135-145.

9.Frankel S.L., Probabilistic Model for sequential circuits under functional testing, in Proc. 3rd International Design Automation Workshop ("Russian Workshop93"), Moscow, July 19-20, 1993. pp. 140-152.

Uh&, №32-266 2 /.03.94

Pa^HHO>Hetio 70^3. J/h №3/