Введение к работе
Актуальность. В последние годы широкое распространение во всех сферах жизнедеятельности получили компьютерные технологии. Благодаря им значительно повысилась эффективность современного производства, оперативность и качество обработки информации. При этом возрастают требования к надёжности компьютерных систем, что связано с ответственность возлагаемых на них функций. Повышение качества и надёжности вычислительной техники достигается в первую очередь применением современных автоматизированных систем проектирования, важнейшими компонентами которых являются средства логического моделирования и построения проверяющих тестов.
В настоящее время существует ряд эффективных алгоритмов моделирования и генерации тестов для комбинационных схем. Однако в связи с резким скачком сложности проектируемых цифровых устройств (ЦУ) применение уже существующих подходов существенно увеличивает стоимость процесса диагностирования, требуя чрезмерных затрат временных ресурсов и памяти. Задача разработки алгоритмов моделирования и построения тестов для последовательностных схем исследована значительно хуже вследствие неопределённости начального состояния и явления состязаний сигналов. В настоящее время не существует эффективных методов генерации тестов для сложных цифровых схем с памятью.
В связи с вышесказанным необходима дальнейшая разработка эффективных алгоритмов логического моделирования и автоматизированной генерации тестов, как для комбинационных, так и для последовательностных цифровых схем.
Связь работы с научными программами, планами, темами. Тема данной диссертационной работы, а также её результаты связаны с выполнением НИР №0194и022560 «Разработка основ теории и прикладного программного обеспечения идентификации дискретных систем», НИР №0199и001612 «Исследование актуальных проблем моделирования, управления и идентификации дискретных систем», а также комплексной программой НАН Украины "Техническая диагностика и неразрушающий контроль" пункт "Система автоматического моделирования и диагностирования (АСМИД) дискретных устройств".
Цель работы: повышение эффективности автоматизированного диагностирования цифровых схем путём разработки новых быстродействующих методов логического моделирования и генерации тестов, а также их реализации в виде программной системы.
Идея работы заключается в применении многозначных алфавитов при моделировании ЦУ с неисправностями, за счёт чего достигается повышение адекватности процесса моделирования; использовании методов сортировки неисправностей, позволяющих повысить быстродействие алгоритмов моделиро-
вания; применении генетических алгоритмов (ГА) совместно с многозначным моделированием для построения тестовых наборов больших схем.
Задачи работы. Для достижения указанной цели решаются следующие задачи:
-
разработка событийного алгоритма параллельного логического моделирования неисправных комбинационных и последовательностных ЦУ с высокой степенью адекватности;
-
разработка алгоритма событийного моделирования последовательностных ЦУ с функциональными неисправностями;
-
разработка методов повышения быстродействия алгоритмов моделирования ЦУ с неисправностями;
-
разработка алгоритма генерации тестов для сложных последовательностных ЦУ с высокой полнотой получаемых тестовых наборов.
Научная новизна полученных результатов состоит в разработке алгоритмов моделирования неисправных цифровых схем в многозначных алфавитах, методов уменьшения числа событий за счёт сортировки неисправностей, разработке генетического алгоритма генерации проверяющих тестов.
Практическое значение полученных в диссертационной работе результатов состоит в разработке и программной реализации новых алгоритмов моделирования исправных и неисправных ЦУ и генерации тестов ЦУ в виде автоматизированной системы моделирования и диагностики АСМИД-Е. Разработанная система позволяет повысить качество генерируемых тестовых наборов, адекватность процесса моделирования, уменьшить затраты памяти и времени. Апробация системы проводилась на схемах из каталогов ISCAS-85 и ISCAS-89, на которых по международным стандартам принято проверять эффективность новых программ моделирования и генерации тестов. По результатам машинных экспериментов на контрольных схемах временные характеристики в среднем улучшены на 45-50%.
Методы исследований. В работе использованы методы теории булевых функций, конечных автоматов, переключательных схем и методы технической диагностики цифровых схем.
На защиту выносятся;
-
Алгоритм событийного параллельного по неисправностям моделирования неисправных комбинационных и синхронных последовательностных схем, который для повышения адекватности процесса моделирования использует 16-значную логическую систему.
-
Алгоритм параллельного моделирования неисправных синхронных последовательностных ЦУ, использующий функциональную модель неисправности одиночного перехода конечных автоматов, что позволяет соединить преимущества структурных и функциональных подходов в моделировании ЦУ.
-
Методы повышения быстродействия за счёт статической и динамической сортировки списка неисправностей для стратегии параллельного моделирования, совмещённого с одиночным распространением неисправностей.
4) Алгоритм генерации тестовых наборов для синхронных последователь-носгаых устройств на основе генетических алгоритмов, который позволяет обрабатывать большие схемы.
Обоснованность и достоверность полученных в диссертационной работе результатов подтверждается корректным использованием математического аппарата теории булевых функций, конечных автоматов, переключательных схем; проведёнными машинными экспериментами, показывающими, что применение предложенных методов ускорения процесса моделирования существенно повышает его скорость; практическим использованием разработанной системы моделирования и генерации тестов АСМИД-Е на производстве в ОАО «Авто-матгормаш» при проектировании и диагностировании схем шахтной автоматики.
Апробация работы. Основные научные результаты работы докладывались и обсуждались на:
XIV Международной межвузовской школе-семинаре «Методы и средства технической диагностики», Ивано-Франковск, 1997;
Международной конференции «Математика в индустрии», Таганрог, 1998;
1-й Международной конференции «Современные технологии ресурсо-энергосбережения», Партенид, 1997;
областных семинарах «Актуальные проблемы компьютерных наук», Донецк;
семинарах отдела теории управляющих систем Института прикладной математики и механики НАН Украины.
Публикации. По теме диссертационной работы опубликовано 8 печатных работ: 5 статей в научных изданиях, 3 статьи в трудах международных конференций.
Реализация результатов работы. Разработанная система АСМИД-Е использовалась при проектировании и диагностировании цифровых схем шахтной автоматики в АО «Автоматгормаш» (г. Донецк), а также в учебном процессе при проведении лекций и лабораторных занятий в курсе «Основы автоматизации и проектирования средств вычислительной техники» кафедры автоматизированных систем управления Донецкого государственного технического университета.
Структура и объём работы. Диссертационная работа на 151 странице состоит из введения, 5 разделов, выводов и содержит 26 рисунков, 23 таблицы, список использованных источников из 127 наименований.