Алгоритм ВЕНТИЛЯТОРА
Алгоритм FAN — это алгоритм автоматической генерации тестовых шаблонов (ATPG) . Его изобрели в 1983 году Хидео Фудзивара и Такеши Симоно на факультете электронной инженерии Университета Осаки , Япония. [1] На тот момент это был самый быстрый алгоритм ATPG, который впоследствии был принят промышленностью. Алгоритму FAN удалось сократить количество возвратов за счет применения новых эвристик, таких как уникальная чувствительность и множественная обратная трассировка. [1] Уникальная чувствительность заключается в определении как можно большего числа значений сигнала, которые могут быть однозначно подразумеваемы. Множественная обратная трассировка — это параллельная обратная трассировка более чем одного пути, которая более эффективна, чем обратная трассировка по одному пути. Чтобы уменьшить количество возвратов, важно как можно скорее обнаружить отсутствие решения. Когда мы обнаруживаем, что решения не существует, нам следует немедленно вернуться назад, чтобы избежать последующего ненужного поиска. Эти эвристики могут привести к раннему обнаружению несоответствий и уменьшению количества возвратов. Алгоритм FAN был представлен в нескольких книгах. [2] [3] [4] и многие документы конференций, такие как конференция по автоматизации проектирования ACM/IEEE и др. [5]
Реализации
[ редактировать ]- Аталанта : автоматический генератор тестовых шаблонов, реализующий алгоритм FAN.
- FanWorks : визуальный симулятор схемы, включающий режим ATPG с использованием алгоритма FAN.
Ссылки
[ редактировать ]- ^ Jump up to: а б Фудзивара, Хидео; Симоно, Такеши (декабрь 1983 г.). «Об ускорении алгоритма генерации тестов». Транзакции IEEE на компьютерах . С-32 (12): 1137–1144. дои : 10.1109/TC.1983.1676174 . S2CID 9547677 .
- ^ Фудзивара, Хидео (сентябрь 1985 г.). Логическое тестирование и проектирование для тестируемости . МТИ Пресс. ISBN 9780262561990 .
- ^ Абрамович, Мирон; Брейер, Мелвин А.; Фридман, Артур Д. (1990). Тестирование цифровых систем и тестируемое проектирование . IEEE Пресс. ISBN 9780780310629 .
- ^ Нирадж, Джа; Гупта, Сандип (2003). Тестирование цифровых систем . Издательство Кембриджского университета. ISBN 0521773563 .
- ^ Киркланд, Том; Мерсер, М. Рэй (1987). «Алгоритм топологического поиска для ATPG». Материалы 24-й конференции ACM/IEEE, посвященной конференции по автоматизации проектирования - DAC '87 . стр. 502–508. дои : 10.1145/37888.37963 . ISBN 0818607815 .