Metode și algoritmi de aspect, de plasare și a PCB urmă

Moscova, Institutul de Stat de Electronică și Matematică

Adu metode și algoritmi pentru rezolvarea problemelor de aspect, plasare și rutare, care rezultă în procesul de proiectare. Evaluează complexitatea metodelor și a calității soluțiilor cu ei, considerând problema ca o problemă de programare matematică menționate mai sus.

2. aspect Algoritmi

cazare 3. Algoritmi

4. Algoritmi urmă

La proiectarea CEA de proiectare (echipament electronic) a rezolvat problema de a găsi cel mai bun mod de proiectare satisface cerințele caietului de sarcini ia în considerare capacitățile de producție de baze de date tehnologice și maxime. Interconectarea strânsă a problemelor și dimensiuni mari pentru fiecare dintre acestea, de obicei, nu oferă metoda de căutare permite soluției de proiectare optimă într-un singur ciclu, din cauza dificultăților de creare a unui model matematic comun, care ia în considerare proiectarea complexă și caracteristicile tehnologice ale bazei de producție. Prin urmare, dezvoltarea și implementarea de algoritmi și metode de rezolvare a problemelor individuale stadiu de inginerie de construcții: aspect, plasare și rutare - sunt încă probleme urgente, din care soluția este strâns legată de dezvoltarea de sisteme de proiectare asistată de calculator.

2. LAYOUT ALGORITMI

La etapa de inginerie de construcții pentru problemele de manipulare legate de dispunerea elementelor logicii în modulul, celulele, celulele din panou, și așa mai departe .. Aceste sarcini, în general, sunt strâns legate, iar soluția lor reduce semnificativ costul și complexitatea acestei etape în CAD. De obicei aranjament sunt considerate ca un proces de luare a deciziilor în anumite sau incerte condiții, în urma căruia o parte a circuitului logic sunt aranjate în elemente structurale ale nivelului i-lea, iar aceste elemente sunt dispuse în elemente structurale (i + 1) strat -lea și t. D. în care locația este realizată cu criteriul de optimizare selectat.

aspect Circuitry pe CEA structural parte finit este procesul de distribuire a elementelor constructive ale nivelului inferior la cel mai înalt, în conformitate cu criteriul selectat. Aranjamentul de bază este criteriul de compatibilitate elektromagnitoteplovoy elementelor de nivel inferior. Acest criteriu determină intervalul de schema de partiții admisibilă, care formulează alte criterii. Aceste criterii pot fi: minimul constructiv tipuri de piese finite, densitatea aranjament, un minim de conexiuni între dispozitive, ușurința de diagnostic, etc. Este evident că legătura dintre circuitele externe este adesea unul dintre cei mai importanți factori care determină fiabilitatea CEA .. Prin urmare, cel mai frecvent criteriu este criteriul unui număr minim de link-uri externe. Făcând acest criteriu minimizează interferența reciprocă, simplificarea proiectarea, îmbunătățirea fiabilității, și așa mai departe. D.

Pentru a construi un formale probleme matematice modelul de aspect este convenabil de a folosi teoria graficelor. În această diagramă interpreta multigraf neorientat, în care fiecare element structural (modulul) stabilește în conformitate multigraf vertex și circuite de comunicație electrice - marginile sale. Apoi, problema aspect este formulată după cum urmează, cere un multigraf G (X, U). Este necesară "tăiat" în bucăți G1 separat (X1, U1), G2 (X2, U2), ..., Gk (Xk, Marea Britanie), astfel încât numărul de muchii care leagă aceste piese la un nivel minim, de exemplu,

Cu alte cuvinte, părți ale pereților despărțitori pe set de grafice G luate în considerare, în cazul în care orice parte a acestui set nu este gol; pentru oricare două părți de intersecție ale setului de nervuri poate fi non-gol; unirea tuturor pieselor este exact egală cu graficul G.

algoritmi de aspect cunoscute pot fi împărțite în cinci grupe:

1. algoritmi folosind tehnici de programare întreg.

2. algoritmi secvențiale

3. algoritmi iterative

4. Algoritmi mixte

Algoritmii din primul grup, deși și permite o soluție exactă a problemei, dar complexitatea reală pentru dispozitivul nu este, de fapt realizat pe computere. Recent, algoritmi de dispunere aproximative cele mai utilizate pe scară largă (secvențială, iterativ, mixt). Atunci când se utilizează algoritmi secvențiale mai întâi pe un nod anumita regula selectată a graficului, se efectuează apoi selectând secvențial noduri (între nealocată) și atașându-le la care formate dintr-o bucată de grafic. După formarea primei piese în mișcare la al doilea, și așa mai departe. E. Pentru a produce tăierea dorită a graficului original. Algoritmii iterative graficul inițial de tăiere în bucăți funcționează în mod arbitrar; Optimizarea Layout se realizează prin permutări pereche sau grup de noduri de diverse piese. Procesul de redistribuire a nodurilor terminate atunci când a primit o extremelor locale a funcției obiective care satisface cerințele de dezvoltator. In algoritmi de layout mixte pentru versiunea inițială „de tăiere“ algoritm este folosit secvențial formarea de bucăți; Alte soluții de optimizare a face transferuri între piesele individuale ale varfului graficului.

Succesive algoritmi de dispunere "așchiere" Graficul inițial G (X, U) în bucăți G1 (X1, U1), G2 (X2, U2), ..., Gk (Xk, Marea Britanie), este după cum urmează. In graficul G (X, U) sunt primele xi

grad minim local Xc

Dacă mai multe astfel de noduri, atunci se acordă preferință în partea de sus cu numărul maxim de muchii multiple. Din multitudinea de vârfuri adiacente nodurilor formate graficului piesa G1 (X1, U1), este ales cel care asigură legăturile minime cu bucata increment nodurile încă neatribuite. Având în vedere xi nod

X \ X1 includ G1 (X1, U1), în cazul în care nu există nici o încălcare a limitărilor privind numărul de bucăți de relații externe, și anume,

unde # 945; j # 949; - matricea elementului adiacență graficului inițial G (X, U); # 948; (xg) - relativa greutate nodurile xg ,. incrementa număr egal de nervuri externe piesă G1 (X1, U1) când nodurile într-o pluralitate X1 xg; E - set de indici vertex incluse în piesa formată din graficul privind etapele anterioare ale algoritmului; m - numărul maxim permis de contacte externe ale unei singure piese cu tot restul.

Acest proces continuă atâta timp cât o pluralitate de X1 nu va conține nici o aderare nelementov păstrate nodurile regulate xj la o G1 piesă (X1, U1) nu va conduce la o încălcare a limitărilor asupra numărului de conexiuni externe piesă la egal la egal

Trebuie remarcat faptul că valoarea

nu este o funcție monotonă a | X1 |, prin urmare, să fie convinși de imposibilitatea formării ulterioare a piesei din cauza încălcării din urmă restricție este necesară verificarea impracticabilitate în următorii pași pentru a crește pluralitatea X1 până la n. Ca opțiune finală este selectată felie 0 G1 (X1 0, U1 0) conținând numărul maxim posibil de noduri ale G (X, U), pentru care următoarele restricții privind numărul de conexiuni externe, și ale vârfurilor sale constitutive (nmin -nmax).

După piesa de conversie 0 G1 (X1 0, U1 0), procesul se repetă pentru a forma un al doilea, al treilea etc. piese originale grafic, cu singura diferență că se ia în considerare partea de sus, care nu sunt incluse în bucăți anterioare.

Formulăm un algoritm de componente de aspect coerente.

În care t, # 920; - numerele de serie ale piesei formate și nodurile de legătură; # 945; - o limită a numărului de noduri pe bucata.

3) La matricea inițială graficul adiacență | # 945; CP | NxN. în care N- număr de vârfuri de pornire (cu o valoare mare de N pentru a reduce cantitatea de memorie din calculator în sine nu utilizează matricea adiacenta și punerea sa în aplicare cod), definește gradul de vârfuri locale

4) din multitudinea de noduri nealocată Xvybiraem vertex xj cu # 961; (xj) =

. Ne întoarcem la revendicarea 6. Dacă mai multe astfel de noduri, apoi trece la revendicarea 5

5) Din Xl Subset de noduri cu același grad xj vertex local ales cu numărul maxim de nervuri multiple (numărul minim de noduri adiacente), adică | Gxj | =

6) de stocare a nodurilor de pornire graficului format piesă

. Mai departe revendicării 10

7) Prin matricea de adiacență