Багатоаспектний метод та алгоритми генерації тестів комбінованого діагностування мікропроцесорних пристроїв

Размещено на http://www.allbest.ru/

ДЕРЖКОМІТЕТ ПРОМИСЛОВОЇ ПОЛІТИКИ УКРАЇНИ

НАУКОВО-ВИРОБНИЧА КОРПОРAЦIЯ

"КИЇВСЬКИЙ IНСТИТУТ АВТОМАТИКИ"

УДК 004.2:004.3

Багатоаспектний метод та алгоритми генерації тестів комбінованого діагностування мікропроцесорних пристроїв

Спеціальність 05.13.05 - Елементи та пристрої обчислюваної техніки та систем керування

АВТОРЕФЕРАТ

дисертацiї на здобуття наукового ступеня кандидата

технiчних наук

Бойчук Вадим Олександрович

Київ 2000

Дисертацiєю є рукопис.

Робота виконана на кафедрі комп'ютерних систем Технологiчного університету Подiлля (м.Хмельницький) Міністерства освіти і науки України.

Захист вiдбудеться 11 жовтня 2000 р. о 13 год. на
засiданнi спецiалiзованої вченої ради К.26.818.01 НВК "Київський iнститут автоматики" за адресою: 04107 Київ, вул.Нагiрна, 22.

З дисертацiєю можна ознайомитись у бiблiотецi НВК "Київський iнститут автоматики" за адресою: 04107 Київ, вул.Нагiрна, 22.

Автореферат розiсланий " 10" вересня 2000 р.

Вчений секретар спецiалiзованої вченої ради кандидат технiчних наук Тронько Л.П.

Анотації

Бойчук В.О. Багатоаспектний метод та алгоритми генерації тестів комбінованого діагностування мікропроцессорних пристроїв.- Рукопис.

Дисертація на здобуття вченого ступеня кандидата технічних наук по спеціальності 05.13.05 - елементи та пристрої обчислювальної техніки та систем керування. - НПК "Київський інститут автоматики", Київ, 2000.

Дисертація присвячена питанням розвитку тестового комбінованого діагностування сучасних мікропроцесорних пристроїв.

В роботі запропонована нова структурно-поведінкова модель МПП як об'єктів діагностування, котра є комбінацією поведінкових та структурних складових, які пов'язані нечіткими відношеннями.

На основі запропонованої моделі розроблено новий багатоаспектний метод генерації тестів комбінованого діагностування МПП, який характеризується паралельним хвильовим алгоритмом розповсюдження проявів несправностей. Для їх розповсюдження через вузли моделі або сукупність вузлів використовуються розв'язки невизначених (діофантових) рівнянь або їх систем, які одержуються в процесі аналізу програмних модулів вузлів.

Запропоновані способи запобігання конфліктів, що виникають при побудові тестів, згідно з багатоаспектним методом.

На основі нечітких відношень складових моделі розроблено метод мінімізації кількості тестової інформації.

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

Ключові слова: комбіноване діагностування, генерація тестів, діофантові рівняння, хвильовий алгоритм, процес, мікропроцесорні пристрої, мікропроцесори .

Бойчук В.А. Многоаспектный метод и алгоритмы генерации тестов комбинированного диагностирования микропроцессорных устройств. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - элементы и устройства вычислительной техники и систем управления. - НПК "Киевский институт автоматики", Киев, 2000.

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

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

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

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

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

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

Cпособы базируются на:

1) управлении распространением волны;

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

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

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

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

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

Boychuk V. O. Multidimensional method and algorithms of test generation for combined diagnosing of microprocessor devices. - Manuscript.

Thesis for candidate degree on a speciality 05.13.05. - Elements and devices of computing engineering and control systems. - SPC "Kiev institute of an automation", Kiev, 2000.

The dissertation is devoted to development of test combined diagnosing of modern microprocessor devices. A new structrural-behavioural model of modern microprocessor devices is combination of structural and behavioral submodels, which connected by fuzzy relation. A new approach to test generation, based on parallel propagation algorithm and decision of undeterminаted (diophantine) equations, is propoused.

Ways of conflicts prevention, which arise in test generation process, were developed.

Technique of test quantity minimization is elaborated, which is based on fuzzy relation.

Main rezults of this work were used in the subsystem of test generation. Creation of this subsystem has allowed to simplyfy structure and expand functional opportunities of test combined diagnosing systems software. This increases reliability of fault search and efficiency of test combined diagnosing process.

Key words: kombined diagnosing, test generation, wavefront algorithm, diophantine equations, proccess, microprocessor devices, microprocessors.

1. Загальна характеристика роботи

мікропроцесорний діагностування генерація текст

Актуальність теми. Основою обчислювальної техніки, сучасних пристроїв автоматики, засобів керування і зв'язку є мікропроцесорні пристрої (МПП). Значно розширилося застосування МПП за останні роки, що обумовлює зростаючий інтерес до забезпечення високих показників якості і надійності МПП. Для контролю і діагностування мікропроцесорних пристроїв були розроблені різні методи і засоби.

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

Але існуючі методи й алгоритми генерації тестів не розраховані на одержання ефективних тестових наборів для комбінованого діагностування сучасних МПП. Це знижує ефективність процесу діагностування і його достовірність. Тому одним із питань, що вимагає вирішення, є розробка моделі МПП як об'єкта діагностування, уточнення моделей несправностей і на їх основі розробка методу й алгоритмів генерації тестів комбінованого діагностування мікропроцесорних пристроїв.

Зв'язок роботи з науковими програмами, планами, темами. Подані в дисертації дослідження проводилися в рамках держбюджетних НДР Технологічного університету Поділля: №9Б-92 (ТА-ХМТИ-ОУ) "Розвиток теорії і розробка методу комбінованого діагностування цифрових, цифро-аналогових і аналого-цифрових пристроїв із компонентами підвищеного ступеня інтеграції бортових і наземних установок нової техніки" (1992-1995 рр.); №6Б-98 "Теорія тестового комбінованого діагностування структур із компонентами підвищеного ступеня інтеграції" (1996-1997 рр.).

Автор є співвиконавцем розроблених систем діагностування МПП "Пальма-Ц-1460" і "ТЕКОД-2М".

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

Об'єктом досліджень в дисертаційній роботі є мікропроцесорні пристрої, які являють собою схемно-конструктивне з'єднання декількох мікросхем на друкованій платі, включаючи один чи декілька мікропроцесорів.

Предметом дослідження є багатоаспектний метод генерації тестів комбінованого діагностування мікропроцесорних пристроїв.

Методи досліджень базуються на основних положеннях технічної діагностики, які є основними в досягненні мети дисертації. Визначення структурно-поведінкової моделі грунтується на теоріях графів, множин, нечітких множин та елементах теорії алгоритмів. Багатоаспектний метод генерації тестів побудований на базі теорії множин та елементах теорії алгоритмів. Вибір значень тестових дій і відповідних реакцій при їх поширенні здійснюється на основі теорії нечітких множин. Розповсюдження тестових дій та відповідних реакцій через вузли поведінкової складової здійснюється на основі елементів теорії алгоритмів.

Задачі досліджень у роботі формулюються у такий спосіб:

1. Провести аналіз сучасних МПП і їх особливостей як об'єктів діагностування.

2. Проаналізувати відомі методи генерації тестів мікропроцесорних пристроїв і дослідити області їх застосування.

3. Розробити структурно-поведінкову модель МПП як об'єкту діагностування.

4. Уточнити відомі моделі проявів несправностей МПП для використання в генерації тестів.

5. На підставі запропонованої моделі і уточнених несправностей МПП розробити багатоаспектний метод генерації тестів мікропроцесорних пристроїв.

6. Використовуючи запропонований метод, розробити алгоритми побудови тестів МПП.

7. Запропонувати способи запобігання конфліктів, що виникають у процесі побудови тестів.

8. На основі розробленої структурно-поведінкової моделі МПП запропонувати новий метод мінімізації кількості тестів.

9. Впровадити в промисловість комплекс програмного забезпечення систем тестового комбінованого діагностування з підсистемою генерації тестів.

Наукова новизна одержаних результатів роботи полягає в розробці нового багатоаспектного методу автоматичної генерації тестів, який відрізняється від існуючих методів використанням паралельного хвильового алгоритму поширення проявів несправностей. При описанні поширення проявів несправностей через вузли або сукупність вузлів використовується розв'язок невизначених (діофантових) рівнянь. Багатоаспектний метод побудований на основі нової структурно-поведінкової моделі МПП як об'єкту діагностування. Модель є комбінацією поведінкових і структурних складових, зв'язаних нечіткими відношеннями. Структурно-поведінкова модель, в порівнянні з відомими моделями, дозволяє більш вірогідно і гнучко описувати сучасні мікропроцесорні пристрої з урахуванням наявних знань. Для скорочення кількості тестів на основі нечітких відносин між складовими структурно-поведінкової моделі розроблено новий метод мінімізації кількості тестової інформації, суть якого полягає у використанні правил виводу.

Практичне значення одержаних результатів. Результати досліджень складають основу програмного забезпечення підсистеми генерації тестів систем тестового комбінованого діагностування. Розроблені програмні засоби дають можливість забезпечити: автоматизацію побудови тестових наборів діагностування мікропроцесорних пристроїв; максимальну гнучкість при побудові тестів з урахуванням знань користувача; підвищення достовірності і глибини тестування. Основні результати дисертації знайшли застосування при створенні систем тестового комбінованого діагностування "ТЕКОД-2М", "Пальма-Ц-1460" і використовуються на ВО "Новатор" (м.Хмельницький) для тестування цифрових та мікропроцесорних пристроїв, а також в навчальному процесі Технологічного університету Поділля при вивченні курсів "Технічна діагностика обчислювальних пристроїв" і "Паралельне програмування". Практичні результати рекомендується використовувати в системах тестового діагностування цифрових та мікропроцесорних пристроїв.

Особистий внесок здобувача. Основні наукові результати, положення і висновки отримані особисто автором і полягають в розробці:

- структурно-поведінкової моделі МПП як об'єкту діагностування;

- багатоаспектного методу генерації тестів комбінованого діагностування МПП;

- алгоритмів побудови тестів МПП на основі багатоаспектного методу генерації тестів;

- методу мінімізації кількості тестів комбінованого діагностування;

- способів запобігання конфліктів, що виникають при генерації тестів;

- структури підсистеми генерації тестів.

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

Апробація роботи. Наукові і практичні результати роботи доповідалися й обговорювалися на науково-технічній конференції "Вимірювальна та обчислювальна техніка в технологічних процесах та конверсії виробництва" (м. Хмельницький, 1993р., 1995р., 1997р., 2000р.); міжвузівскій науковій конференції молодих вчених і студентів (м. Київ, 1996р., 2000р.); науково-технічних конференціях професорсько-викладацького персоналу, співробітників і студентів Технологічного університету Поділля (м. Хмельницький, 1993-1999 рр.).

Публікації. Основні результати дисертації повністю викладені в 14 друкованих працях, у т.ч. в 6 статтях у фахових виданнях, 1 статті в збірнику наукових праць, 7 тезах доповідей.

Структура й об'єм дисертації. Дисертація складається з вступу, чотирьох розділів, висновків. Загальний обсяг дисертації 138 сторінок, з яких основний текст складає 125 сторінок. Дисертація містить 31 рисунок, 4 таблиці, включає 128 найменувань вітчизняної і закордонної літератури, 2 додатки. Додатки містять акти впровадження результатів роботи та тексти програм розроблених програмних продуктів.

2. Короткий зміст роботи

У вступі обгрунтована актуальність тематики досліджень, сформульована мета роботи та задачі досліджень, наведені характеристики наукової новизни та практичної цінності отриманих результатів, показано зв'язок роботи з науковими програмами та темами.

У першому розділі проведено аналіз сучасних МПП як об'єктів діагностування та особливостей основних методів генерації тестів цифрових пристроїв. На основі аналізу визначено, що існуючі моделі цифрових пристроїв та методи генерації тестів не дозволяють одержувати ефективні тести комбінованого діагностування сучасних МПП, а саме:

1. Методи, які використовують моделі з домінуванням структурної інформації про пристрій, неможливо використати через недостатність інформації про МПП та труднощі розповсюдження проявів несправностей.

2. Методи з використанням моделей, які відображають функціонування МПП, дають контролюючі тести порівняно великого об'єму з невизначеним відсотком покриття несправностей.

Тому однією з задач, яка потребує вирішення, є розробка нового, більш ефективного методу та алгоритмів генерації тестів МПП.

У другому розділі, враховуючи недоліки існуючих моделей та представлення МПП в процесі тестового комбінованого діагностування, була запропонована структурно-поведінкова модель МПП як об'єкта діагностування. Ця модель являє собою комбінацію з наступних складових:

- поведінкової;

- структурної.

Поведінкова складова (ПС) структурно-поведінкової моделі відбиває перетворення інформації при функціонуванні МПП і може бути записана в такому загальному вигляді:

B=< X , L , GX,L >,

де X- множина вузлів; L -множина ліній зв'язку між вузлами; GX,L - граф, вершини якого зіставлені з операційними, запам'ятовуючими, керуючими вузлами і вузлами зовнішніх виводів, а дуги відповідають лініям зв'язку між вузлами для передачі даних і керуючих сигналів.

Кожний вузол ПС xi задається як:

xi=< ki , ni , ti >,

де ki -тип вузла (операційний, запам'ятовуючий, керуючий, зовнішній вивід); ni - програмний модуль, що визначає алгоритм функціонування вузла;
ti - параметр, що показує інтервал синхронізації, в якому функціонує даний вузол .

Кожна лінія зв'язку lj задається як:

lj=< nbj , nej , qj , ?j >,

де nbj -номер початкового вузла та ідентифікатор вихідного порту у цьому вузлі; nej - номер кінцевого вузла та ідентифікатор вхідного порту у цьому вузлі; qj - тип дуги; j -часові параметри передачі даних або керуючих сигналів по лінії зв'язку.

Дуги можуть використовуватись для передачі даних, керуючих сигналів та передачі керування, що визначає тип дуги.

Зміст програмних модулів подається за допомогою абстрактної мови програмування. При моделюванні МПП зміст модулів перетворюється в моделюючий процес вузла, який є сукупністю послідовно виконуваних операторів і локально описаних даних. Процеси можуть виконуватися паралельно і незалежно один від одного. При моделюванні дуги являють собою канали з обмеженою ємністю і їм відповідає передача інформації між модулями. Оператори в модулі можуть бути операторами присвоювання, умовного переходу, ітераційного циклу, запису в порт або зчитування з порту. Оператори запису або зчитування з порту служать для обміну інформацією між програмними модулями.

Множина дуг, що входять у вузол і виходять із вузла, складається з двох типів підмножин, для яких:

1) передача або прийом інформації по дугах даної підмножини завжди ведеться у процесі виконання програмного модуля вузла;

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

В узагальненій формі для різних типів дуг ці підмножин можуть бути подані так :

,

де R - тип дуги; I/O - ідентифікатор, на місце якого ставиться: I- для вхідних дуг, O - для вихідних дуг; -підмножина дуг першого типу; - підмножина дуг другого типу.

Структурна складова (СС) структурно-поведінкової моделі дозволяє враховувати структуру МПП під час генерації тестів та представляється у такому вигляді:

С=< S , H , GS,H >,

де S - множина вершин; H - множина дуг; GS,H - граф, вершинам якого зіставлені вузли зовнішніх виводів і структурні вузли МПП, а дуги відповідають лініям зв'язку між вузлами.

МПП у процесі тестового комбінованого діагностування розглядається ієрархічно: рівень МПП; рівень фрагментів, що виконують окремі функції; рівень окремих компонентів. Ієрархічна структурна складова дозволяє урахувати це при описанні МПП. Вершини ієрархічної СС, які відповідають структурним вузлам МПП, мають вкладені поведінкову та структурну складові.

Встановлення взаємозв'язків ПС і СС дозволяє прив'язати поведінкову складову до фізичної реалізації МПП. Взаємозв'язки між складовими представляються у вигляді відношень.

Відношення приналежності елемента поведінкової складової до елемента структурної складової BxC={< b , c >, b B, c C}, де b і c елементи ПС і СС, показує, що перетворення в МПП, яке описується елементом ПС b, відбуваються в структурному вузлі МПП, який відповідає елементу c структурної складової. Відношення задається у вигляді матриці RB. У випадку, коли взаємозв'язки неможливо точно описати, використовується нечітке відношення складових B і C. Кожному кортежу < b, c > ставиться у відповідність функція приналежності , що показує ступінь впевненості в приналежності елемента b до c. Матриця нечіткого відношення складається з елементів ri,j, які дорівнюють значенню функції для елементів bi та cj. На рис. 1 показано приклад цього відношення у графічній формі. Відношення приналежності елементів ПС до елементів СС відображено штриховою лінією.

Відношення приналежності елемента СС до елемента ПС CxB={< c , b >,
b B, c C} показує, що структурний вузол МПП, який відповідає елементу структурної складової с, виконує перетворення інформації в МПП, яке описується елементом поведінкової складової b. Аналогічно для задання цього відношення використовуємо матрицю нечітких відношень складових С та B, .

Функціонування деякого структурного вузла МПП в різні періоди часу відбивають елементи ПС, пов'язані відношенням еквівалентності BxB={<b, b >, b B}. Це може бути припущення, що в МПП однакові дії виконуються тим самим фізичним пристроєм. Це нечітке відношення представляємо у вигляді матриці .

Комбінація поведінкових та структурних складових дозволяє врахувати багатоаспектність знань про МПП (поведінка, структура) та дає можливість проводити генерацію тестів з врахуванням неповної та нечіткої інформації про характеристики МПП.

Розглядаються такі види несправностей МПП, які відповідають вузлам ПС:

- несправності низького (вентильного) рівня;

- функціональні несправності;

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

На основі опису цих несправностей одержуються базові тестові дії (ТД) та відповідні реакції (ВР), які розповсюджуються до вузлів зовнішніх виводів.

У третьому розділі запропоновано метод генерації тестів МПП, що базується на таких принципах:

1. Побудова тестів здійснюється на основі структурно-поведінкової моделі.

2. При генерації тестів виконується почерговий вибір елементів ПС. У обраний елемент, який вважається несправним, вносяться базові ТД і ВР. Далі вони поширюються через інші елементи ПС до її зовнішніх вузлів.

3. Поширення ТД до входів і ВР до виходів виконується незалежно і паралельно по всіх шляхах.

Основними задачами при реалізації даних принципів є одержання шляхів поширення ТД і ВР та визначення їх значень при поширенні через справні елементи (вузли, дуги) поведінкової складової.

Визначення. Два вузли називаються зв'язаними, якщо існує дуга, що їх зв'язує. Для дуги зв'язаними є вузли, інцидентні цій дузі.

У розробленому багатоаспектному методі генерації тестів комбінованого діагностування використовуються деякі елементи хвильового алгоритму. При внесенні базових ТД і ВР в елемент поведінкової складової він стає початковим джерелом поширення "хвилі". Зв'язані вузли є приймачами хвилі. До фронту хвилі, яка поширюється до зв'язаних вузлів, прив'язуються значення тестових дій або відповідних реакцій. Після прийому хвилі й обчислення значень ТД і ВР вузли "збуджуються" і стають джерелами поширення хвилі для зв'язаних з ними вузлів. Обчислення їх значень при поширенні хвилі виконуються на підставі програмного змісту вузлів. Для того, щоб стежити за процесом поширення хвилі, початковій і кінцевій точкам дуг ставиться у відповідність множина атрибутів. Атрибути відбивають характеристики процесу поширення хвилі через дуги і вузли.

При поширенні хвилі через елементи ПС вирішуються наступні задачі:

1. Задача транспортування. На вході елемента ПС (на вхідній дузі вузла, на початку дуги) є визначені ТД. З огляду на умови й обмеження на поширення ТД через елемент поведінкової складової, визначити ВР на виходах елемента. Транспортування через вузол починається за умови наявності хоча б однієї визначеної ТД на вхідній дузі вузла.

2. Задача довизначення. На виході елемента ПС (на вихідній дузі вузла, на кінці дуги) є визначені ВР. Необхідно на підставі аналізу вмісту елемента визначити ТД на входах елемента. Довизначення через вузол починається при наявності хоча б одного визначеного значення ВР на вихідній дузі вузла.

Під час транспортування ТД та довизначення ВР (ТДВ) через вузол аналіз залежності даних у програмних модулях вузлів і визначення значень невідомих (вільних) змінних зводиться до одержання невизначених (діофантових) рівнянь. Як правило, для такого рівняння або системи рівнянь є декілька розв'язків, кожен з яких складається з декількох коренів. Окремі корені кожного з розв'язків є значеннями ТД або ВР для подальшого поширення.

Пошук шляхів ТДВ здійснюється паралельно деякою множиною програмних модулів. Після внесення базових ТД і ВР у деякий елемент поведінкової складової для кожного шляху поширення хвилі здійснюється "породження" програмного модуля транспортування і довизначення (МТД). Алгоритм роботи одного такого модуля відображено на рис. 2.

МТД читає зміст вузла (програмний модуль, атрибути, тип вузла), що знаходиться на шляху поширення хвилі. Якщо вузол є вузлом зовнішнього виводу, то тестові дії або відповідні реакції записуються в базу даних. Інакше, МТД на підставі аналізу змісту вузла одержує систему рівнянь і обмежень (нерівностей). Після їхнього розв'язку утворюється деяка множина розв'язків. Робиться вибір одного розв'язку, окремі корені якого є значеннями ТД і ВР для вхідних/вихідних дуг вузла. Після цього, відповідно до правил вибору дуг поширення хвилі виконується породження наступних МТД. Вони є "нащадками" для вузла, що породжує, і виконують аналогічні дії на наступних вузлах по шляхах поширення хвилі. Програмний модуль-предок очікує результати роботи модулів-нащадків. Якщо результати їхньої роботи незадовільні, функціонування програмного "модуля-предка" відновляється і вибирається інший розв'язок і т.д.

ТДВ для поведінкової складової, як правило, неможливо провести незалежно і паралельно. Однією з причин виникнення конфліктів є збіжні розгалуження (ЗР). Класифікуємо елементи, що входять в ЗР, як: xF - вузол розгалуження; xR - вузол сходження; X1,X2 - множини вузлів, які входять у перший і другий шляхи ЗР (крім вузлів xF ,xR ), L1, L2 - множини дуг, які входять у перший і другий шляхи.

Визначено такі типи конфліктів, що виникають на ЗР:

1. Конфлікти різних значень. Виникають у випадку паралельного поширення по декількох шляхах різних значень ТД або ВР, що конфліктують у точці сходження.

2. Конфлікти переповнювання. Тестові дії в точці сходження викликають неприпустимі значення на виході вузла .

Перший тип розділяється на наступні підтипи:

1) конфлікти різних значень на шляхах поширення даних;

2) конфлікти різних значень на шляхах поширення об'єднаних типів .

Для запобігання конфліктів першого типу використовуються наступні способи:

1) керування поширенням хвилі через вузли поведінкової складової. Зокрема порушується умова збудження вузла, відповідно до якої ТДВ через вузол починається при наявності хоча б одного визначеного значення на вхідній/вихідній дузі вузла;

2) перетворення фрагмента ПС, що входить у ЗР, до системи невизначених (діофантових) рівнянь;

3) моделювання фрагмента ПС.

Для запобігання конфліктів першого підтипу використовується прийом на основі першого способу. Він застосовується, коли транспортування ТД або довизначення ВР через ЗР починається з вузлів, які входять у множини X1 або X2. Якщо МТД вибрав вузол, який xi ? X1 або xi ? X2 , то забороняється проведення транспортування через вузол xR без наявності визначених тестових дій на дугах l1h і l2h цього вузла. Відповідно до цього підходу, по шляху, на якому знаходиться обраний вузол xi , здійснюється транспортування ТДВ, по іншому шляху - тільки транспортування ТД. Щоб почати транспортування по іншому шляху необхідне проведення довизначення ВР через вузол xF.

З метою збереження паралельності проведення ТДВ для запобігання конфліктів на шляхах поширення об'єднаних типів використовується інший прийом на основі першого способу. ТДВ через керуючі вузли ПС може початися тільки після одержання визначених значень ВР на усіх вихідних дугах для передачі керуючих сигналів і на одній з альтернативних підмножин. Довизначення через керуючий вузол почнеться тільки у випадку, коли закінчилася ТДВ через операційні і запам'ятовуючі вузли, що знаходяться під керуванням цього вузла.

При ТДВ через вузли необхідно вибрати один з розв'язків рівняння або системи рівнянь. Випадковий вибір значень коренів може викликати конфлікти значень (переповнювання, ділення на нуль) на подальших етапах генерації тестів. Множини припустимих альтернатив, що можуть приймати значення розв'язків рівнянь (ТД та ВР), повинні задовольняти обмеженням. Звичайно обмеження мають форму 0 y 2n-1, де n - розрядність порту для передачі інформації.

Для вираження ступеня задоволення умові успішного ТДВ через вузол застосовується функція переваги. Як таку використовуємо значення функції приналежності нечіткої підмножини на множині припустимих альтернатив.

Розв'язки рівняння чи системи рівнянь можна представити у вигляді матриці Y, де стовпці (y11,y21,…,ym1), (y12,y22,…,ym2),…,(y1n,y2n,…,ymn) відповідають векторам варіантів розв'язків рівняння, а рядки Y1=(y11,y12,…,y1n), Y2=(y21,y22,…,y2n), …,Ym=(ym1,ym2,…,ymn) - векторам значень коренів для змінних y1,y2 ,…,ym .

Конфігурація нечітких множин призначена для вибору значень у векторах розв'язків для кожної змінної.

На рис.3 відображена ситуація транспортування тестових дій через вузол O1, де значення коренів у векторах можливих відповідних реакцій Y1,Y2 оцінюється за нечіткими множинами , що відносяться до вузлів O2,O3 .

Виконуємо перетинання нечітких множин і векторів Y1, Y2,...,Ym:

.

Для одержання результуючої функції переваги розв'язків використовується агрегація часткових критеріїв (функцій переваги) в узагальнену функцію переваги:

,

де ai - коефіцієнт, що дозволяє оцінити важливість шляхів ТДВ, ;
( yij ) - значення функції приналежності для елементів .

В результаті, кожному розв'язку присвоюється значення функції приналежності, на основі цієї функції вибирається єдиний розв'язок:

.

Виконується пошук розв'язку з локальним максимумом функції приналежності та проводиться транспортування або довизначення з вибраними значеннями ТД і ВР. Якщо виникає конфлікт, то відбувається повернення і здійснюється пошук чергового локального максимуму і т.д.

Розглянуті раніше нечіткі відношення є основою для застосування нечітких правил виводу. Правила використовуються з метою скорочення кількості тестів, обсяг яких при генерації тестів комбінованого діагностування на основі ПС може бути досить значним. Також вони дають можливість на основі використання існуючих тестів компонентів скоротити час генерації тестів МПП.

Для сукупності відношень між складовими використовуються декілька базових правил виводу:

1.ЯКЩО	існує тест для елемента поведінкової складової,
ТО	цей тест є тестом для всіх елементів, зв'язаних із даним вузлом відношенням еквівалентності RE.
2. ЯКЩО	існує тест для елемента поведінкової складової,
ТО	цей тест є тестом для всіх елементів структурної складової, зв'язаних із даним вузлом відношенням приналежності RC.
3. ЯКЩО	існує тест для елемента структурної складової,
ТО	цей тест є тестом для всіх елементів поведінкової складової, зв'язаних із даним вузлом відношенням приналежності RB.
4. ЯКЩО	існують тести для всіх елементів, зв'язаних з елементом поведінкової або cтруктурної складових відношеннями приналежності RC або RB,
ТО	ця сукупність тестів є тестом для даного елемента.

Ланцюжок міркувань будується з початкової гіпотези, що тестування деякого елемента поведінкової складової можна замінити тестуванням іншого елемента чи групи елементів поведінкової або структурної складових. При цьому по черзі вибираються елементи поведінкової складової і на підставі перебору даних правил робиться висновок про справедливість гіпотези. Після того як початкова гіпотеза підтверджується, всі елементи, зв'язані ланцюжком міркувань, запам'ятовуються для наступного використання в процесі генерації тестів або гіпотеза відхиляється.

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

У четвертому розділі розроблені багатоаспектний метод, способи, метод мінімізації і алгоритми генерації тестів комбінованого діагностування реалiзуються вiдповiдними засобами тестового комбiнованого дiагностування. Для цього з урахуванням розробленої підсистеми генерації тестів була модифікована структура програмного забезпечення систем комбінованого діагностування, що спростило та розширило його функціональні можливості. Представлено порівняння якісних характеристик підсистеми генерації тестів комбінованого діагностування з іншими високорівневими системами генерації тестів. Отримано залежності визначення часу генерації тестів та підвищення продуктивності генерації від кількості ЕОМ, котрі беруть участь в побудові тестів. Часова складність розроблених на основі багатоаспектного методу алгоритмів визначається як:

O(s Nвузл.( Nдуг.+Nвузл.) Nтес.),

де Nвузл.- кількість вершин в ПС; Nдуг. - кількість дуг в ПС; Nтес. - кількість тест-векторів або векторів відповідних реакцій в базових ТД або ВР;
s -кількість строк в програмних модулях вузлів.

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

Одержані тести дозволяють діагностувати МПП з більшою достовірністю і глибиною. Це є задовiльним для практичного використання в процесі тестового комбiнованого дiагностування МПП розробленої моделі, методів, способів і алгоритмів.

Висновки

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

Основні результати виконаної роботи полягають у наступному:

1. Запропоновано нову структурно-поведінкову модель МПП як об'єктів діагностування, що є комбінацією поведінкових і структурних складових, зв'язаних нечіткими відношеннями. Ця модель дозволяє вірогідно і гнучко описувати об'єкт діагностування з урахуванням знань, наявних у розробника.

2. Розроблено багатоаспектний метод автоматичної генерації тестів. Запропонований метод і алгоритми дозволяють в автоматичному режимі формувати набори тестових дій і відповідних реакцій, використовуючи паралельний хвильовий алгоритм поширення проявів несправностей. При описі поширення проявів несправностей через вузли або сукупність вузлів використовуються розв'язки невизначених (діофантових) рівнянь.

Запропонований метод підвищує достовірність тестування за рахунок збільшення глибини пошуку несправностей, підвищує продуктивність процесу тестового комбінованого діагностування за рахунок скорочення часу побудови тестів.

3. Досліджено типи конфліктів, які виникають у процесі побудови тестів. Розроблено способи й алгоритми, що дозволяють запобігти виникненню конфліктів шляхом керування процесом поширення хвилі, перетворення фрагмента моделі в систему діофантових рівнянь та вибору значень ТД або ВР з використанням функції переваги.

4. На основі нечітких відношень між складовими структурно-поведінкової моделі розроблено метод мінімізації кількості тестової інформації, суть якого полягає у використанні умовних базових і додаткових правил виводу.

5. Оптимізація процесу тестового комбінованого діагностування МПП дозволила приблизно на 23 % підвищити продуктивність побудови тестів у системах типу ТЕКОД у порівнянні з аналогічними системами.

6. Розроблені модель, методи, методика й алгоритми покладені в основу програмного забезпечення систем тестового комбінованого діагностування і реалізовані в промисловості.

Список опублікованих праць

1. Бойчук В.О., Джулiй В.М., Стецюк В.М. Система управління базою даних тестової інформації в системах тестового комбінованого діагностування //Вимірювальна та обчислювальна техніка в технологічних процесах. - 1997. - №1.- С. 140-143.

2. Бойчук В.О., Джулій В.М., Огнєвий О.В. Пiдсистема самонавчання при тестовому комбінованому діагностуванні цифрових структур з компонентами підвищеного ступеня інтеграції //Автоматизація виробничих процесів. - 1997-№2.- С. 31-33.

3. Бойчук В. О., Огнєвий О.В. Використання засобів штучного інтелекту в діагностиці цифрових пристроїв з компонентами підвищеного ступеня інтеграції // Вісник Технологічного університету Поділля. -1998. - №1. -С. 161-165.

4. Стецюк В.М., Джулiй В.М., Бойчук В.О. Концепцiя побудови сучасної системи дiагностування цифрових радiоелектронних вузлiв//Вимірювальна та обчислювальна техніка в технологічних процесах. - 1997. - №2. - С. 163-165.

5. Локазюк В.Н., Бойчук В.А. Использование нечетких и неполных знаний в процессе генерации тест-векторов комбинированного диагностирования
// Вимірювальна та обчислювальна техніка в технологічних процесах. - 1999.- №4. - С. 96-102.

6. Локазюк В.М., Бойчук В.О. Методи та алгоритми генерації тестів комбінованого діагностування мікропроцесорних пристроїв //Вісник Технологічного університету Поділля. -2000. - № 3. - С. 118-120.

7. Локазюк В. Н., Бойчук В.А. Графическая тестовая информация в системах комбинированного диагностирования устройств с компонентами повышенной степени интеграции //Вимiрювальна та обчислювальна технiка в технологiчних процесах i конверсiї виробництва: Тез. доп. II наук.-техн. конф.- Хмельницький:ТУП, 1993.- С. 187.

8. Бойчук В. А. Элементы искусственного интеллекта в системах комбинированного диагностирования цифровых устройств // Вимірювальна та обчислювальна техніка в технологічних процессах: Тез. доп. III наук.-техн. конференції, - Хмельницький:ТУП, 1995. - С. 171.

9. Бойчук В. О., Трапезніков В.М. Можливості використання теорії фреймів в програмному забезпеченні систем комбінованого діагностування // Тез. доп. наук. конф. молодих вчених та студентів. - К.: ДАЛПУ, 1996. - С. 51.

10. Бойчук В.А., Джулій В.Н. Применение технологии экспертных систем в программном обеспечении систем комбинированного диагностирования// Технологiчний унiверситет в системi реформування освiтньої та наукової дiяльностi Подiльського регiону: Тез. доп. наук.-практ. конф. - Хмельницький:ТУП, 1995. - C. 150.

11. Джулiй В.М., Стецюк В.М., Савенко О.С., Бойчук В.О. Інтерактивне середовище для систем комбінованого тестового діагностування //Актуальні проблеми техніки та суспільства: Зб. статей викл. і наук співробітників Технологічного університету Поділля. - Хмельницький: ТУП, 1996. Вип.2.- С.172-176.

12. Джулiй В.М., Стецюк В.М., Савенко О.С., Бойчук В.О. Система вiдновлення пошкодженних баз даних тестiв в системi комбiнованого дiагностування ВIС та НВIС//Вимірювальна та обчислювальна техніка в технологічних процесах: Зб. матер. конф. - Хмельницький:ТУП, 1997.

13. Бойчук В.О., Джулiй В.М., Стецюк В.М.Система керування базою даних тестової інформації в системах комбiнованого дiагностування ВIС та НВIС// Вимірювальна та обчислювальна техніка в технологічних процесах: Зб. матер. конф.- Хмельницький:ТУП, 1997. - С. 60.

14. Локазюк В.Н, Бойчук В.А. Многоаспектный метод генерации тестов комбинированного диагностирования микропроцессорных устройств //Вимірювальна та обчислювальна техніка в технологічних процесах: Тез. доп. IV наук.-техн. конф. - Хмельницький:ТУП, 2000. - C. 142-147.

Размещено на Allbest.ru

...