Алгоритми трасування
Існує чимало різних алгоритмів трасування, які мають різну ефективність. Одні алгоритми є більш прийнятними на початкових етапах трасування при вільному від трас комутаційному полі. Інші алгоритми ефективніші при вже заповненому трасами комутаційному полі. З'ясування сутності алгоритмів трасування буде розглянуто на прикладі базового хвильового алгоритму.
Хвильовий алгоритм
Мал. 5.10. Ілюстрація хвильового алгоритму
Алгоритм містить такі основні кроки.
Формуємо умовну числову хвилювід джерела до приймача (від початку траси до кінця). Позначаємо осередок з точкоюАяк осередок № 0, сусідні осередки? № 1, сусідні до цих? № 2 і т. д. до досягнення кінцевої точки (в даному випадку? . Сусідними осередками є ті, що межують ребрами.
Будуємо трасу. Траса будується від приймача до джерела по фронтах числової хвилі, як зменшення значення фронту. Напрямок траси змінюємо лише за необхідності.
Алгоритм вимагає величезних обчислювальних витрат і тому є різні модифікації прискореного трасування. Наприклад - побудова ортогональних променів на перших етапах трасування (променевий алгоритм - рис. 5.11).
Мал. 5.11. Променевий алгоритм
Цей алгоритм добре працює лише тоді, коли на платі є мало заборонених для трасування зон. Тож у реальних системах використовується комплексний алгоритм. На перших кроках застосовуються швидкі способи трасування (променевий, канальний тощо. буд.), але в наступних кроках - більш тонкі, але повільні алгоритми (типу алгоритму Лі).
Контрольні питання
Що є вихідним на вирішення топологічних завдань?
Перерахуйте способи завдання графів та опишіть їх?
Назвіть найпоширеніші різновиди графів?
Чим визначаються структурні властивості зв'язкових графів?
Яким є принцип заповнення матриці з'єднань?
У чому відмінність матриці інцидентів від матриці з'єднань?
Які три основні завдання топологічного проектування можна виділити?
Як формулюється завдання розбиття, розміщення та трасування?
Як здійснюється алгоритм послідовного розбиття?
Що таке комутаційне поле та позиція? Наведіть їхні приклади?
Які основні кроки містить алгоритм Лі та його застосування?
Лекція 6. Елементна база ес та конструкції плат
Елементна база
Основні параметри цифрових ІМС:
електричні (номінальні струми та напруги по входу, виходу та живленню.)
вольт-амперні характеристики (ВАХ) для входу та виходу мікросхем.
потужнісні параметри (P 1 ,P 0 )
Параметри швидкодії визначаються формою стандартного цифрового сигналу (рис. 6.1). Ці параметри визначають мінімальну тривалість такту (мал. 6.2), отже, можливості системи під час обробки інформації.
Мал. 6.1. Форма стандартного цифрового сигналу
Мал. 6.2. Визначення тривалості такту цифрового сигналу
Основні часові параметри, що характеризують швидкодію:
twширина імпульсу на рівні 0,5,
tpтривалість імпульсу на втраті 0,9,
Мінімальна тривалість циклу пов'язані з мінімальним фронтом:tc10tr, тобто. максимальна тактова частота дорівнюватимеT= 1/tc.
приклад. Нехайtr=1 нс, тодіtc=10 нс, а максимальна тактова частота буде