Алгоритми за проследяване
Има доста различни алгоритми за проследяване, които имат различна ефективност. Някои алгоритми са по-приемливи в началните етапи на маршрутизиране с превключващо поле без следи. Други алгоритми са по-ефективни, когато превключващото поле вече е запълнено със следи. Изясняването на същността на алгоритмите за проследяване ще бъде разгледано на примера на основния вълнов алгоритъм.
Вълнов алгоритъм
Ориз. 5.10. Илюстрация на вълнов алгоритъм
Алгоритъмът съдържа следните основни стъпки.
Формираме условна цифрова вълнаот източника до приемника (от началото на следата до нейния край). Клетката с точкатаAобозначаваме като клетка #0, съседните клетки - #1, съседните на тези - #2 и т.н. до достигане на крайната точка (в случаяB). Съседни клетки са тези, които са оградени с ръбове.
Изграждане на писта. Следата се изгражда от приемника до източника по фронтовете на цифровата вълна, в ред на намаляване на предната стойност. Посоката на маршрута се променя само при необходимост.
Алгоритъмът изисква огромни изчислителни разходи и затова има различни модификации на ускореното проследяване. Например конструирането на ортогонални лъчи на първите етапи на проследяване (алгоритъм за лъчи - фиг. 5.11).
Ориз. 5.11. Рей алгоритъм
Този алгоритъм работи добре само когато има няколко зони, забранени за маршрутизиране на платката. Следователно в реални системи се използва сложен алгоритъм. На първите стъпки се използват бързи методи за проследяване (лъч, канал и т.н.), а на следващите стъпки по-фини, но по-бавни алгоритми (като алгоритъма на Лий).
Контролни въпроси
Каква е отправната точка за решаване на топологични проблеми?
Избройте начините за задаване на графики и ги опишете?
Кои са най-често срещаните видове графики?
Какво определя структурните свойства на свързаните графи?
Какъв е принципът на попълване на матрицата на връзката?
Каква е разликата между матрица на инциденти и матрица на връзка?
Кои са трите основни задачи на топологичния дизайн?
Как се формулира задачата за разделяне, поставяне и проследяване?
Как се изпълнява алгоритъмът за последователно разделяне?
Какво е превключващо поле и позиция? Дайте им примери?
Какви са основните стъпки на алгоритъма на Лий и неговото приложение?
Лекция 6
Елементна база
Основните параметри на цифровите интегрални схеми:
електрически (номинални токове и напрежения за вход, изход и захранване.)
характеристики на тока и напрежението (VAC) за входа и изхода на микросхемите.
параметри на мощността (P 1, P 0)
Параметрите на производителност се определят от формата на стандартен цифров сигнал (фиг. 6.1). Тези параметри определят минималната продължителност на цикъла (фиг. 6.2) и следователно възможностите на системата при обработка на информация.
Ориз. 6.1. Стандартна цифрова форма на вълната
Ориз. 6.2. Определяне на времето на часовника на цифровия сигнал
Основните времеви параметри, характеризиращи изпълнението:
twширочина на импулса на ниво 0,5,
tpпродължителност на импулса при 0,9 щети,
Минималното време на цикъла е свързано с минималния ръб:tc10tr, т.е. максималната тактова честота ще бъдеT= 1/tc.
Пример. Некаtr= 1 ns, тогаваtc=10 ns и максималната тактова честота ще бъде