Еволюційні методи побудови перевіряючих тестів цифрових систем - Автореферат

Важливу роль у питаннях підвищення надійності компютерних систем і елементної бази, грають системи автоматизованого проектування та діагностування, що включають у себе тестове діагностування. Ефективність автоматизованих систем тестового діагнозу, заснованих на подачі на випробуваний обєкт спеціально організованих (тестових) впливів, значною мірою залежить від застосовуваних методів і алгоритмів побудови тестів, що перевіряють. Однак дослідження в даному напрямку не припиняються, оскільки методи, що застосовуються, не завжди дозволяють будувати тести необхідної повноти через незадовільні показники швидкодії внаслідок високої розмірності завдання. Таким чином, побудова перевіряючих тестів для цифрових схем є актуальною науково-технічною проблемою, рішення якої істотно впливає на якість і надійність компютерних систем. Мета роботи і завдання дослідження: Метою є підвищення ефективності автоматизованого діагностування цифрових систем шляхом розробки еволюційних методів генерації перевірюючи тестів.У першому розділі “Аналіз моделей цифрових схем и методів побудови тестів” введені поняття, що визначають обєкт дослідження: математичні моделі цифрових пристроїв і несправностей, визначення тесту. Представлено сучасну класифікацію типових несправностей, які є моделями фізичних дефектів: одиночні та кратні константні несправності (stack-at faults s-a-0, s-a-1), місткові несправності (bridging faults), несправності “стійке замикання транзистора” ("stuck-on"-SON , "stuck-short" faults,), несправності типу “затримка”, несправності, що перемежовуються, нестійкі несправності, дефектно-орієнтовані несправності (defect oriented faults), функціональні несправності, несправності рівня мов регістрових передач (ЯРП), несправності, що не тестуються (untestable faults). Одиночна константна несправність f називається виявленою у послідовнісний схемі вхідною послідовністью X(1), X(2),..., X(p) щодо стратегії одиночного спостереження виходів, якщо , (2) де r - початковий стан справної схеми й q - початковий стан несправної схеми. Це визначення говорить, що при даній стратегії несправність вважається виявленою, якщо найдеться (принаймні один) момент часу (такт) t такий, що для будь-якої пари станів (r,q) справної й несправної схем деякий i-й вихід zi має різні значення в справній і несправній схемі. За даними логічного моделювання справної схеми обчислюється значення оцінної функції всієї послідовності: , (5) де s - послідовність яка аналізується; - вектор з розглянутої послідовності, i - позиція вектора в послідовності, f - задана несправність, LH - попередньо задана константа в діапазоні , завдяки якій перевага віддається найбільш коротким послідовностям.У дисертаційній роботі дано рішення актуальної наукової задачі, яка має велике значення при проектуванні, виробництві та експлуатації сучасної обчислювальної техніки. Розроблено нові еволюційні методи генерації тестів для цифрових логічних схем, що дозволяють підвищити повноту тестових впливів, що генеруються, і скоротити час їх побудови. Показано, що використання розроблених операторів кросінговера та мутації приводить до підвищення повноти на 5% і скороченню обчислювальних витрат на 10-20%.

Основний зміст

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

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

2. Розроблений і досліджений розподілений генетичний алгоритм побудови тестів на основі моделі “робітник-хазяїн”, експериментально показаний майже лінійне збільшення швидкодії для невеликого числа “процесорів-робітників” і логічних схем великої розмірності. При цьому загальний час рішення скоротився на величину від 80% до 50%, залежно від розмірності оброблюваних схем.

3. Розроблено та досліджено розподілений генетичний алгоритм побудови тестів на основі моделі островів, модифіковано генетичні оператори та визначено раціональні параметри ГА. Показано, що “модель островів” на відміну від моделі “робітник-хазяїн” дає відносно невелике збільшення швидкодії, але дозволяє істотно підвищити якість одержуваних рішень на 7%.

4. Проведено апробацію, тестування та перевірку ефективності розроблених програмних модулів на логічних схемах з міжнародних каталогів ISCAS-85 і ISCAS89, які підтвердили досягнуті високі експлуатаційні характеристики.

1. Ю.А.Скобцов, А.И.Эль-Хатиб. Параллельные генетические алгоритмы//Наукові праці Донецького национального технічного университету серія: “Обчислювальна техніка та автоматизація”, Випуск 90.-Донецьк : ДОННТУ. - 2005.-С.137-144

2. Д.Е.Иванов, Ю.А.Скобцов, А.И.Эль-Хатиб. Распределенные алгоритмы моделирования и генерации тестов // Радіоелектронні і компютерні системи.-ХАІ:2006.-№6.-С.97-102.

3. Скобцов Ю.А., Єль-Хатиб А.И, Іванов Д.Е. Распределенное параллельное моделирование цифровых схем с неисправностями//Наукові праці Донецького національного технічного університету.Серія:”Обчислювальна техніка та автоматизація”, Донецьк:2006.- Випуск 107.-С.128-134.

4. Ю.А.Скобцов, Д.Е.Иванов, А.И..Эль-Хатиб. Распределенные генетические алгоритмы генерации проверяющих тестов цифровых систем//Радіоелектронні і компютерні системи.-ХАІ:2007.-№7.-С.176-181.

5. Skobtsov Y.A., El-Khatib, Ivanov D.E. Parallel Genetic Algorithm of Test Generation for Digital Circuits // Proceedings of the IX International Conference “Modern problems of Radio Engineering, Telecommunications and Computer Science”.-Lviv-Slavsko:2006.- P.129-131.

6. Ю.А.Скобцов, А.И.Эль-Хатиб. Параллельные генетические алгоритмы построения тестов цифровых схем//Труды 7-й международной научно-практической конференции “Современные информационные и электронные технологии”.-Одесса: 2006.-С.204.

7. Skobtsov Y.A., El-Khatib, Ivanov D.E. Distributed Fault Simulation and Genetic Test Generation of Digital Circuits//Proceedings of IV IEEE East-West Design&Test Workshop(EWDT’06)/-2006: Sochi.- P.89-94.

8. Skobtsov Y.A., El-Khatib, Ivanov D.E. Distributed Genetic Algorithm of Test Generation For Digital Circuits// Proceedings of the 10th Biennial Baltic Electronics Conference.-Tallinn Technical University,2006.-p.123-128.

9. Скобцов Ю.А., Д.Е.Иванов, А.И.Эль-Хатиб.Распределенный генетический алгоритм генерации проверяющих тестов на основе модели островов//Тезисы II Всеукраинской конференции ”Сучасні тенденціїї розвитку інформаційних технологій в науці, освіті та економіці”.-2006:Луганск.-.С.211-213.

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