ПХБ алгоритми за маршрутизация на ВЕИ
следа проблем е да се изгради връзката между елементите на ПИН подредени в предварително определено място инсталация, в съответствие с електрическа схема на устройството съгласно дизайн ограничения предвид. Обикновено писта е оформен като множество от свързани сегменти, свързващи точките електрическата верига. Следните критерии са взети под внимание при решаването на проблема със следа:
1) Минималното общата дължина на съединения;
2) минималният брой връзки, дължината на която надвишава предварително определена стойност;
3) минималният брой на прехода между слоевете;
4) минималния брой слоеве;
5) минимум паразитни смущения;
6) съединения с максимално разстояние маршрути;
7) броят на слоевете не трябва да надвишава предварително определената стойност;
8) дължина връзка не трябва да надвишава предварително определена стойност;
9) ниво на намеса, предизвикана от всяка песен не трябва да надвишава допустимата стойност;
10) брой връзки (дажба) до единия край не надвишава предварително определена стойност.
При проектирането на многослойни структури, като правило, отделно реши проблема на оптимални връзки, което свежда до минимум индекс
където R - слой номер; Z - брой слоеве; М - броят на вериги във веригата; - естеството на пръчка градуса пресечната точка на к-ти и S-те пътища на;
ако маршрут к и и не принадлежат към слой R;
ако маршрут к и и принадлежат слой г.
Характеристики дадени различни стойности, например, ASW schadyu-припокриващи се зони Ар схеми и прилагане като; пресичане брой пълни подграфи като Аг и вериги; минимален брой преминавания свързващи Аг и като мрежи; ПИН брой вериги и Ar като принадлежащи към пресечните зони при изпълнение на тези схеми.
Като цяло проблемът за автоматизация на инженерно-строителни проследяване връзки - това е най-трудната задача, която е особено тясна връзка с проектиране и технологично изпълнение. Първоначална информация за проследяване на задачи обикновено са:
1) проектираната верига Netlist;
2) параметри на структурните елементи (форма и размери);
3) параметрите на монтаж пространство (допустимо разстояние, под формата на съединения, броят на кръстовища и други подобни);
4) данни за елементи разположение (следи се извършва между точките, чиито координати са посочени в абсолютни или относителни стойности).
проследяване проблем има метрични и топологични аспекти. Метрични аспект свързани със структурните размерите на елементи и съединения на монтаж пространство (мястото). Топологична аспект е обект на ограничения за броя на преминавания право, броят на верига слоеве и т.н. т.е. свързани с пространственото подреждане на отделните части и верига връзки. Алгоритмичните маршрутизация методи, въпреки тяхното разнообразие, не осигуряват 100% от съединенията. По метод за конструиране методи следи проследяване са разделени в структурна и итеративен.
В следващите конструктивни алгоритми релсови вериги се извършва в определен ред, една след друга. Обикновено маршрута започва с или най-дългите съединения са напълнени в много пространство за инсталиране са по-трудно да се образува, или с по-късите съединения, които са по-гъсто напълнени с пространство за монтаж. С настилка опит и по-нататъшно проследяване се разглежда като пречка, това е, като пространство за инсталация заета от клетката. По този начин, в последователните алгоритми местен се извършва оптимизация, когато се определя всеки път, но в крайна сметка, след поредица от пътеки, някои части от монтажната пространство могат да бъдат блокирани, което не позволява да се проследи автоматично.
Повтарящата алгоритъм след полагане на всички песни, което е оса fected без да се отчита взаимното влияние на песни се определя от качеството на функцията за проследяване като претеглена сума от параметрите на трасето (дължина, брой PE-кръстовища, броят на завои). След оценка на най-лошия проследяване маршрут изпълнение се отстранява и процеса на проследяване се повтаря с най набор от съединения като препятствия.
и алгоритми, разработени за решаване на проблемите за маршрутизация, които съчетават последователни и повтарящи се процедури - "смущаващи" песни са деформирани или премахнати, т.е. промени в конфигурацията вече посочени съединения или уплътнения последователност изтече.
Фигура 1 показва последователността на проследяване методи за прилагане на различни видове схеми и алгоритми, използвани.
Примери проследяване алгоритми
Повечето от известните универсален проследяване алгоритми Ba-вълнова екстрахиране алгоритъм за определяне на пътя (микроелемент съединения полицаи) намалява някои многомерен функция че качеството път. Идеята на алгоритъма на вълната е илюстрирано на фиг. 2, където свързаните елементи А и В, намиращи се в (1, 4) и (4, 7) на редовен пространство инсталация.
Фиг. 2. проследяване Алгоритъм вълна съединения в присъствието на препятствия
Номерата 0, 1, 2. Фигура 14 показва "фронт" на разпространение на вълната от точката (1,4) - състояние 0, докато достигне точката (4, 7) - състоянието на пистата 14. оптимално точки Полученото съединение в обратен ред 14-13-. -1-0 като следа с минимална дължина и минимален брой извивки за максимална плътност опаковка. Пунктираната линия показва маршрута със същата дължина, но най-лошото от другите критерии. вълна алгоритъм промени, насочени към подобряване на ефективността и намаляване на размера на паметта се изисква.
Проследяване с помощта на различни евристичен алгоритъм - лъч - показано на фиг. 3. Между съединителните точки А (6, 3) и В (5, 8) се провежда лъч. При преминаване към следващата точка на монтиране пространство определена от посоката на пистата, минимално различава от посоката на лъча въз основа на приоритета на споменатите структура (номерирани линии) и необходимостта да се избегнат пречките, образувани заети позиции.
Фиг. 3. проследяване съединения алгоритъм лъч в присъствието на препятствия
Прекъснатата линия показва оптимален път (дължина в първата половина), посочена по време на лъч от В в А, т.е. в обратна посока.
Трябва да се отбележи, че по-горе форма, когато се обмисля маршрутизиране критерии за оптимизиране на проблеми, които не са въведени, за да се контролира процеса на проследяване, но само за да се оцени качеството на решенията.
В някои случаи се прави опит да се помисли за следващите стъпки се проследи и да организират паралелни следи всички връзки. Един пример е алгоритъм, използвайки канал представяне на магистрали свързване.
Фиг. 4 показва мрежа от вертикално В1, В2, В3 и хоризонтална G1, G2, G3 канали, която показва свързване на два елемента. Монтаж пространство с два слоя от хоризонтални и вертикални превключване и да се вмъкват контакт кръстовища в точките на хоризонтално и вертикално свързване на слоевете е типично за устройства, реализирани на двустранен печатни платки, както и за големи и неразделна хибрид и монолитни интегрални схеми. Алгоритмите, които използват понятието канали, маршрутизация се извършва на два етапа: предварителен, за да се разпределят каналите работи по един и същи ги разтоварване и на финала, процесът, който определя местоположението на връзките по магистралите канали.
Фиг. 4. Трейс съединения, използвайки канал
Специален вид алгоритми за проследяване на връзки в една равнина, без да преминават. Те се използват при проектиране на монтаж устройство еднослоен в присъствието на различни форми и размери на елемента.
Поради факта, че нито един от известните алгоритми не гарантират пълно проследяване на компютърен дизайн, той се счита за подходящо разработени автоматизирани системи за инженерно проектиране имаше няколко различни програми за проследяване и имаха възможност за споделяне в решаването на даден проблем. Neprolozhennymi оставаща след проследяване на връзката финализирана дизайнери ръчно или интерактивно взаимодействие с компютрите.
Трябва да се отбележи, че при използването на CAD дизайн време топология на устройства, съдържащи 20. 30 ЕО се намали с приблизително заповед, а за степен на интеграция, е почти няма друг начин да се постигне високо качество на проекта и неговата документация. Въпреки това, най-големият недостатък на съвременния компютърен дизайн инженеринг е необходимостта от по-голямо количество допълнителна информация, която може да се подготви от порядъка на няколко седмици с LSI е разработила логика. За да се преодолее този недостатък, създаването на CAD изисква свързване на всички фази на проектиране и електроника с интегриран инвариант база данни, съдържаща информация, която може да бъде завършена в рамките на развитие, както и стандартизация на най-ефективните верига дизайн и дизайнерски решения.