РОЗДІЛ 2
РОЗРОБЛЕННЯ ТА АНАЛІЗ МОДЕЛЕЙ ДЕКОМПОЗИЦІЙНОГО
ПРЕДСТАВЛЕННЯ ЦИФРОВИХ ПРИСТРОЇВ
2.1. Аналіз властивостей і елементів компонентних l-структур
цифрових пристроїв
Швидкість і точність пошуку несправностей є інтегральними критеріями оцінювання
ефективності апаратно-програмних засобів діагностування, а допоміжні показники
тестових випробувань цифрових схем, як правило, відображають результат
взаємодії структур ЦП і відповідних програм їх тестування з можливостями СПД.
Трудомісткість вибору оптимальних стратегій діагностування у більшості випадків
значна і визначається як функціональною, так і структурною складністю самих
об’єктів. Враховуючи тенденцію розвитку сучасних інтегральних технологій, яка
зв'язана з постійним ростом щільності розміщення елементів на платах (а також у
базових кристалах), можна зробити висновок, що розраховувати на одержання
точного рішення за який-небудь прийнятний час машинного моделювання не
приходиться [29, 128].
Сформульована ситуація не може не позначитися на перегляді існуючих методів і
засобів технічної діагностики, пошуку нових рішень, в той час, як відомі
підходи, що вже стали класичними, мають нерідко лише часткове застосування, а
реалізуючі їх технічні засоби малоефективні. Причина такого стану криється в
самій природі задач тестового діагностування (ТД), що (як відзначено в ряді
робіт [128, 129]) дуже близькі за своєю складністю до проблем комбінаторного
аналізу. У теорії обчислювальної складності на основі техніки поліноміальної
збіжності було показано, що задачі ТД, які навіть достатньо просто
сформульовані, відносяться до класу універсальних переборних: наприклад,
виділення несправності в складній схемі; визначення несправностей у пристрої
під час моделювання на графах; пошук несправностей у схемах за допомогою
контрольних точок (КТ), які відповідним чином розміщені, і таке інше [129].
Єдиним універсальним підходом до вирішення подібних задач є зниження їх
розмірності шляхом розбивання структур складних ЦП на фрагменти (компоненти) з
метою наступному тестування. При цьому пошук, принаймні задовільних варіантів
розбиття, привів до їх формальної класифікації і виділення різних підкласів
цифрових схем з подальшим тестовим аналізом на різних рівнях їх представлення
(формального опису) як об'єктів досліджень.
Так, на структурному рівні опису вивчалися характеристики програм контролю
підкласів пристроїв з різними топологічними особливостями, зокрема,
деревоподібних схем, схем з вузлами розгалуження (збіжними, розбіжними),
локальних або глобальних контурів зворотних зв'язків, шинних з'єднань
компонентів і таке інше [128].
На функційному рівні досліджувався підклас схем, що реалізують як булєві
функції (наприклад, лінійні, симетричні), так і більш складні у функційному
відношенні утворення (механізми): вузол обробки даних, вузол збереження
інформації, канал передачі даних і таке інше [154]. Однак, як показала практика
тестові програми більшості реальних схем у багатьох випадках виявлялися більш
складними, а запропоновані числові характеристики їх тестів не завжди
відповідають дійсності. Спроби отримати більш загальні результати на основі
статистичного аналізу функціонування багатьох програм генерації тестів (q =
=1), а також аналізу витрат машинного моделювання несправностей (q = 2) для
різних класів схем дали усереднену оцінку їх трудомісткості в часі
tq = t ЧLq+1, (2.1)
де (t - коефіцієнт, що має розмірність часу, L - вентильний еквівалент
досліджуваного пристрою (або фрагмента схеми), який тестується) [29].
Подібні результати не є математично строго обґрунтованими, однак у багатьох
випадках можуть служити добрим орієнтиром [129]. При цьому, характер
пофрагментних розбиттів структур ЦП багато в чому визначає не тільки точність
пошуку несправностей, але впливає і на загальний час тестування об'єктів. З
метою оптимізації алгоритмів діагностування проведемо узагальнений аналіз
особливостей представлення компонентних структур цифрових схем, а також їх
впливу на часові показники декомпозиційного пошуку несправностей.
Структуру будь-яких пристроїв зручно розглядати на модельному рівні,
представивши сам об'єкт, наприклад, у вигляді орієнтованого графу G*(V*, E*),
де V* = {vi | } – множина вершин, що відповідають елементам пристрою на
принциповій схемі, а Е* = { | j О } - множина дуг, що відображають зв'язки між
елементами. Формування будь-якої фрагментованої структури пристрою, як правило,
виконується за умов певних фізичних обмежень, формальних критеріїв і
закінчується, фактично, перетворенням вихідного графа G*G, де G(V, E) -
гіперграф, для кожного ребра якого ei E можна поставити у відповідність один із
сформованих компонентів G = {G1, G2, ..., Gp}, | E | = р, при наступній умові
їх об’єднання = V. При цьому доцільно, щоб структура кінцевого графа G розбиття
відповідала ряду певних вимог і обмежень відповідно до конструктивних
особливостей досліджуваних об'єктів.
В л а с т и в і с т ь 2.1. Характер декомпозиції вершин графа G* G повинен мати
нетривіальний вигляд, для елементів якого виконується наступна умова (Gi G)(Vi
{}), де , де р - число сформованих підграфів (або компонентів) розбиття
структури вихідного графа G*.
Величина р, фактично, відповідає ступеню фрагментації ЦП, де кожному фрагменту
Gi G можна поставити у відповідність числове значення коефіцієнта qi =
(1/n)Ч|V* | 1, що характеризує складність компонентів розбиття, для яких
справедлива рівність = 1.
В и з н а ч е н н я 2.1. Під ступенем декомпозиції цифр
- Киев+380960830922