Prva karakteristika iz spiska elektricnih je najznacajnija i na nju se u postupku projektovanja layout-a moze uticati na vise nacina. Pre svega, elementi kola moraju biti ispravno povezani, a poboljsanje povezivosti se ostvaruje minimizacijom ukupne duzine veza i gustine veza u kanalima. Takodje, optimizacijom ostalih elektricnih osobina moze da se utice na ispravan rad kola.

Na gornju granicnu frekvenciju rada kola moze se uticati, pre svega, izborom odgovarajuce tehnologije u kojoj ce aktivni elementi biti proizvedeni, ali i minimizacijom ukupne duzine veza, rasterecenjem kanala, smanjenjem preslusavanja, minimizacijom duzina kriticnih veza i sl. Na slican nacin se smanjuje i kasnjenje signala duz veza.

Preslusavanje je posledica postojanja parazitnih elemenata (R,L,C) izmedju dve razlicite veze i njihov uticaj se smanjuje udaljavanjem veza jedne od druge. Ovome treba posvetiti vecu paznju pri povezivanju nego pri razmestaju elemenata.

Vek kola moze biti drasticno smanjen ako su na ploci skoncentrisani elementi koji se vise greju. Zato treba kod razmestanja te elemente ravnomerno rasporediti na ploci .

Vek kola se povecava i ako se gustina struje kroz veze smanji, a to se postize odgovarajucim izborom minimalne debljine (sirine) veza.

Za povrsinu ploce je bitno da se nadje kompromis izmedju dva kontradiktorna zahteva - njenim smanjivanjem se pojeftinjuje proizvod ali sa druge strane moze se narusiti optimalnost nekog od topoloskih parametara (na primer minimalno rastojanje izmedju veza).

Potrebno je istaci i da resenje razmestaja mora da zadovolji izvesne uslove koji su diktirani stilom realizacije. Prvo, dva elementa ili modula ne smeju se preklapati. Zatim kod projektovanja stampanih kola ili gejtovskih matrica moze se zahtevati da moduli budu smesteni u ranije definisane lokacije ploce. Kod gejtovskih matrica ili stila standardnih celija, moduli moraju biti smesteni u predefinisanim nizovima. Najvise fleksibilnosti u ovom pogledu dopusta realizacija kola u stilu makro celija - sto se danas dosta koristi kod "full custom" projektovanja. Ovde nema nikakvih ogranicenja u pogledu polozaja modula.

Na osnovu svega napred iznetog moze se govoriti o kvalitetnom ili manje kvalitetnom razmestaju imajuci u vidu topoloske parametre razmestaja diktirane elektricnim karakteristikama, ili o legalnom i ilegalnom razmestaju uzimajuci u obzir ispunjenost uslova koji su definisani stilom projektovanja.

  2. DEFINICIJA TOPOLOŠKIH PARAMETARA

Evo pregleda oznaka za neke velicine koje su od znacaja za projektovanje layout-a jednog kola.

M={m₁,m₂,...,m_n} skup pokretnih modula

S ={s₁,s₂,...,s_ns} skup fiksiranih modula

V={v₁,v₂,...,v_nc} skup veza kojim su moduli povezani

M⁽ⁱ⁾={m₁⁽ⁱ⁾,m₂⁽ⁱ⁾,...,m_n(i)⁽ⁱ⁾} skup pokretnih modula povezanih vezom v_i

S⁽ⁱ⁾ ={s₁⁽ⁱ⁾,s₂⁽ⁱ⁾,...,s_ns(i)⁽ⁱ⁾} skup fiksiranih modula povezanih vezom v_i

B ={B₁,B₂,...,B_nB}skup nizova u gejtovskoj matrici

U ={u₁,u₂,...,u_nu} skup centralnih kanala kod gejtovske matrice

Kako svakom paru susednih nizova matrice, B_i i B_i+1, odgovara centralni kanal u_i, to je broj kanala za jedan manji od broja nizova, odnosno n_u=n_B-1.

Kod projektovanja layout-a kola u stilu gejtovskih matrica ili standardnih celija skoro uvek se celije tretiraju kao pokretni, a stopice kao fiksirani moduli.

Slika 1. Primer simbolickog layout-a

Povezanost kola se moze predstaviti incidentnim matricama: a={a_ij} - incidentna matrica izmedju veza i pokretnih modula; b={b_ij} - incidentna matrica izmedju veza i fiksiranih modula. Njihovi elementi su dati sa:

Da bismo definisali neke najznacajnije topoloske parametre koristicemo Sliku 1. koja predstavlja tipican primer simbolickog layout-a kola koje se moze realizovati u stilu gejtovskih matrica ili standardnih celija sa mogucnoscu postavljanja veza u dva sloja.

  2.1. UKUPNA DUZINA VEZA

Duzina jedne veze predstavlja zbir duzina svih njenih segmenata. Zbog lakseg racunanja, najcesce se kao mera duzine uzima jedinica rastera. Duzinu jedne veze L_i mozemo posmatrati i kao zbir njenih x i y komponenata:

Pa ce onda ukupna duzina veza koja se dobija kao zbir duzina svih veza u kolu biti:

,

gde je n_c broj veza u kolu.  

2.2. GUSTINA VEZA U KANALU

Slika 2. Horizontalni i vertikalni segmenti kanala

Gustina veza g(vs_i^(k)) vertikalnog segmenta vs_i^(k) moze se definisati kao broj horizontalnih segmenata veza koji presecaju ovaj segment. Isto, gustina veza g(hs_i^(k)) horizontalnog segmenta hs_i^(k) jednaka je broju vertikalnih segmenata veza koji presecaju ovaj segment.

Na osnovu gustina veza segmenata kanala, moguce je suditi o njegovom zauzecu, ali se zakljucak puno brze moze izvesti na osnovu histograma gustina veza. Na sledecoj slici je za kanal sa Slike 1. dat histogram veza.

Slika 3. Histogram gustine veza  

2.3. POVRSINA PLOCE

Povrsina ploce layout-a jednaka je povrsini pravougaonika minimalnih dimenzija, koji obuhvata sve module i sve veze kola. Moze se uociti da je povrsina ploce funkcija broja traka kanala potrebnih da se sve veze trasiraju. Sto je ovaj broj manji, manja je i povrsina layout-a. Na osnovu gustina veza u kanalu moze se priblizno odrediti broj potrebnih traka. Ako sa n_t^(k) oznacimo broj horizontalnih traka kanala u^(k) potrebnih za povezivanje, onda je njegova minimalna vrednost definisana sa:

Iz ovoga sledi, da se minimizacijom gustine veza u kanalu, posredno vrsi i minimizacija povrsine ploce. Kod stila gejtovskih matrica povrsina layout-a je fiksna, tako da minimizacija gustine veza jeste znacajna jedino zbog poboljsanja povezivosti.

  3. MODELI OBLIKA VEZA

Algoritmi za razmestaj obicno optimiziraju neki parametar layout-a tako da se on izracunava vise puta, da bi se dobijena resenja mogla uporedjivati. Ali definitivno, nijedan parametar se ne moze sa sigurnoscu tacno odrediti pre faze trasiranja. Kako je potrebno dosta vremena da se u toku procedure razmestaja vrsi povezivanje trenutnih resenja, stvarno povezivanje se zamenjuje procedurom koja krace traje i koja priblizno ocenjuje oblik i polozaje veza u kolu - to je simulator trasiranja, a veze koje on generise predstavljaju modele oblika stvarnih veza.

Na Slici 4. su dati pinovi koje treba povezati jednom vezom i moze se reci da oni cine cvorove neusmerenog grafa, a njihovo povezivanje se svodi na problem formiranja stabla grafa, odnosno stabla veza. Pravila formiranja stabla dovode do razlicitih modela oblika veza.

Slika 4. Pinovi koje treba povezati

REKTILINEARNO STEINER-OVO STABLO povezuje sve pinove, sastavljeno je samo od horizontalnih i vertikalnih segmenata i ima minimalnu duzinu. Steiner-ove tacke su tacke spajanja segmenata veze (kao sto se vidi na Slici 5.)

Slika 5. Rektilinearno Steiner-ovo stablo veze

EUKLIDSKO STEINER-OVO STABLO je ono stablo kod koga se grane iz svih pinova sticu u jednu tacku koja se naziva gravitacioni centar veze. Kao sto se moze uociti sa Slike 6., ovo stablo se odlikuje svojom jednostavnoscu pa zahteva puno manje racunarskog vremena za formiranje.

Slika 6. Euklidsko Steiner-ovo stablo veze

MINIMALNO POVEZANO STABLO je stablo veze minimalne duzine kod koga je skup cvorova grafa veze sveden samo na skup pinova. Slika 7. prikazuje rektilinearnu i Euklidsku verziju ovog stabla.

Slika 7. Rektilinearno i Euklidsko minimalno povezano stablo

MINIMALNO LANAC STABLO se dobija ispunjenjem pravila koja vaze za minimalno povezano stablo i zahteva da se formirano stablo ne sme granati. To znaci da iz svakog pina mogu da polaze najvise dve grane stabla. Na Slici 8. je prikazano rektilinearno i Euklidsko lanac stablo.

Slika 8. Rektilinearno i Euklidsko lanac stablo

STABLO KOMPLETNOG GRAFA je stablo kod koga su prisutne sve moguce grane, odnosno graf je kompletan. Ovo stablo je vrlo jednostavno za odredjivanje ali zato predstavlja vrlo losu aproksimaciju oblika veze.

Slika 9. Rektilinearno i Euklidsko stablo kompletnog grafa

METOD POLUOBIMA sluzi uglavnom za definisanje duzina veze. Dodatna definicija oblika veze cini ga vrlo pogodnim za primene kod stilova gde su jasno izdvojeni kanali za povezivanje. Pretpostavlja se da ce se stablo veze formirati unutar pravougaonika minimalnih dimenzija koji obuhvata sve pinove p_i, a da je duzina veze priblizno jednaka poluobimu tog pravougaonika. Slika 10. ilustruje odredjivanje duzine veze po ovoj metodi.

Slika 10. Odredjivanje duzine veze po metodu poluobima

Za oblik veze se uzima da je ekvivalentan obliku veze koja povezuje dva naspramna temena minimalnog pravougaonika, s tim da ne sme biti lomljena vise od dva puta i mora biti sacinjena samo od horizontalnih i vertikalnih segmenata. Na Slici 11. prikazana su, primera radi, samo dva stabla veze.

Slika 11. Modeli oblika veze po metodu poluobima

Treba jos reci da je duzina veza odredjena ovim metodom jednaka duzini Steiner-ovog stabla za veze koje povezuju dva ili tri pina. Kako su 70% veza u elektronskim kolima upravo takve veze, to je slaganje ukupne duzine veza odredjene metodom poluobima sa stvarnom duzinom izuzetno velika. Ovo je potkrepljeno i eksperimentalnim rezultatima.

Skoro uvek se javlja problem izbora prioriteta parametara layout-a koji ce biti kompetentni pri odlucivanju koje resenje razmestaja prihvatiti. Zato se uvodi funkcija cene. Razmestaj sa manjom vrednoscu funkcije cene, odnosno sa manjom cenom, bice prihvacen kao bolji.

Kao funkcije cene obicno se koriste funkcije duzine veza, gustine veza u kanalu, povrsine ploce ili cak kombinacije ovih funkcija.

Odredjivanje funkcija duzine veza uglavnom zavisi od izbora modela oblika veza. Ukupna duzina veza se dobija kao suma duzina stabala svih veza, dok se duzina jedne veze dobija kao zbir segmenata stabla veze. U nekim primenama izraz za ukupnu duzinu veze se generalizuje i ima sledeci oblik:

Za svaku vezu su uvedena dva tezinska faktora, t_j⁽¹⁾ i t_j⁽²⁾. Odgovarajucim izborom faktora t_j⁽¹⁾ moguce je pojedinim vezama dati prioritet pri optimizaciji, sto je pogodno za minimizaciju duzine kriticnih veza. Faktorom t_j⁽²⁾ odredjuje se razlika u doprinosu ukupnoj duzini veza izmedju x i y komponenti duzine jedne veze. Ovo se dosta primenjuje kod stilova projektovanja kod kojih je ploca diskretnog tipa, kakvi su u sustini stilovi gejtovskih matrica i standardnih celija.

Klasu takozvanih konveksnih funkcija cine funkcije duzine veza koje nastaju upotrebom Euklidskog Steiner-ovog stabla i Euklidskog stabla kompletnog grafa kao modela oblika veza. Ove konveksne funkcije se izvode uz zanemarivanje dimenzija modula i koriscenjem kvadratne Euklidske metrike kao mere rastojanja.

EUKLIDSKO STEINER-OVO STABLO Na Slici 12. prikazan je skup pokretnih modula M^(k) i fiksiranih modula S^(k) koji trebaju biti povezani vezom v_k, kao i Euklidsko Steiner-ovo stablo ove veze. Za funkciju ukupne duzine veza se dobija sledeci izraz:

gde su a_ki i b_ki incidentne matrice, a x_gk i y_gk koordinate gravitacionog centra veze v_k.

Slika 12. Euklidsko Steiner-ovo stablo veze

STABLO KOMPLETNOG GRAFA Slika 13. prikazuje module koje treba povezati vezom v_k i Euklidsko stablo kompletnog grafa.

Slika 13. Stablo kompletnog grafa veze

da bi se i ovde doslo do funkcije slicne prethodnoj treba naci velicinu koja ce pokazivati kada su dva modula vezana istom vezom, odnosno kada duz koja spaja njihove centre pripada stablu veze. U tu svrhu treba razmotriti proizvod dva elementa matrice incidencije, na primer izmedju pokretnih modula i veza. Na kraju se za ukupnu duzinu veza dobija:

TEZINSKI KOMPLETAN GRAF Poznato nam je da stablo veze kompletnog grafa predstavlja losu aproksimaciju i oblika veze i njene duzine, jer sigurno nece sve grane grafa da ucestvuju u formiranju stvarnog stabla veze. Zato se ide na jednu bolju aproksimaciju duzine veza koja se dobija mnozenjem duzine svake grane u prethodnoj sumi verovatnocom da ona ucestvuje u formiranju lanac stabla, pod uslovom da su sva lanac stabla veze jednako verovatna. Ta verovatnoca je p=2/e_k gde je e_k broj tacaka nad kojima se formiraju e_k!/2 lanaca stabla, pa se na osnovu toga dobija ukupna duzina veza kao:

Prethodne dve funkcije duzine veza cine tzv. klasu konveksnih funkcija koje se odlikuju time da se sve mogu svesti na oblik:

,

gde je C={c_ij} matrica mecusobnih veza celija, a F={f_ij} matrica veza izmedju celija i stopica.

Takodje se moze pokazati da postoji prosta veza: L_u^(tkg)=2 L_u^(ss), odnosno, duzine veza odredjene preko Euklidskog Steiner-ovog stabla i pomocu tezinskog kompletnog grafa su u sustini iste funkcije.

Sve velicine su nam poznate sem c_vk i c_hk koje predstavljaju vertikalni i horizontalni kapacitet kanala u_k. Vertikalni kapacitet kanala je maksimalan broj horizontalnih traka veza koje mogu da prolaze vertikalni segment kanala, a da ne dodje do njihovog medjusobnog preklapanja. Parametar r treba da ima dovoljno veliku vrednost, tako da sabirci u prethodnom izrazu postanu znacajno veliki tek kada gustina veza u segmentu prekoraci kapacitet kanala.

Kod stilova standardnih celija i gejtovskih matrica, funkcija gustine veza cesto ima oblik:

No, najcesce je u upotrebi ova funkcija za r® µ , kada je ona jednaka:

.

Minimizacija ove funkcije ekvivalentna je minimizaciji broja traka kanala potrebnih za postavljanje veza.

Ona je po prirodi vrlo slicna funkciji gustine veza u kanalima. Definise se za svaku liniju preseka, gde linija preseka predstavlja liniju koja sece povrsinu ploce i deli je na dva dela. Broj veza koje presecaju liniju preseka predstavlja brojnu vrednost funkcije preseka za tu liniju.

Tako recimo za primer prikazan na Slici 14. vrednost funkcije preseka za liniju preseka je 3 jer tri veze presecaju liniju preseka.

Slika 14. Odredjivanje funkcije preseka veza  

Ova funkcija treba da oceni velicinu ploce koja je potrebna za realizaciju kola, ali na nivou razmestaja, pre trasiranja veza. Tako da se povrsina ploce najcesce odredjuje kao povrsina pravougaonika minimalnih dimenzija koji obuhvata sve module, smatrajuci da je taj prostor dovoljan i za postavljanje veza.

  5. PODELA TEHNIKA ZA AUTOMATSKI RAZMESTAJ

Podela prema stilu za koji su algoritmi za razmestaj namenjeni:

• razmestaj za stampana kola
• razmestaj za stil gejtovskih matrica
• razmestaj za stil standardnih celija
• razmestaj za stil makro-celija.

Podela prema parametrima layout-a koje ovi algoritmi optimiziraju daje nam algoritme koji minimiziraju :

• duzinu veza
• gustinu veza
• funkciju preseka veza
• vise parametara layout-a.

Po strukturi algoritma, tehnike razmestaja mogu biti konstruktivne i iterativne. Konstruktivne metode generisu kompletan razmestaj na bazi parcijalnih, dok iterativne metode pokusavaju da poboljsaju kompletan razmestaj generisuci bolji iz iteracije u iteraciju. Uglavnom konstruktivne metode daju resenja razmestaja slabijeg kvaliteta tako da iza njih uvek sledi neka procedura iterativnog poboljsanja. Tako da se kaze da konstruktivne metode sluze za generisanje inicijalnog razmestaja.

Po nacinu tretmana problema razmestaja, algoritmi se dele na:

• deterministicke
• Stohasticke

Deterministicki metodi se odlikuju time sto je svaki korak algoritma jasno odredjen, dok su Stohasticki metodi bazirani na algoritmima slucajnog karaktera. Klasu deterministickih metoda cine heuristicki i analiticki algoritmi. Stohasticke metode su poznate jos i pod imenom Monte Karlo metode.

Mnoge metode za razmestaj pokusavaju da razmestaj rese svodeci ga na problem iz drugih grana nauke, tako da se mogu sresti algoritmi bazirani na analogiji sa:

• uravnotezavanjem sila
• resavanjem otporne elektricne mreze
• simuliranjem ocvrscavanja materijala
• genetikom
• evolucijom.

  6. METOD RASTA GRUPE

Ovaj algoritam se sastoji u sukcesivnom selektovanju nerasporedjenog modula i njegovom dodavanju trenutnom resenju razmestaja. Metod opisuje sledeci algoritam a njegov rad je ilustrovan na Slici 15.

gde je A skup nerasporedjenih modula, P trenutno resenje razmestaja, a m trenutno selektovan modul.

Slika 15. Ilustracija rada metoda rasta grupe

U pocetku je skup rasporedjenih modula P prazan skup, a skup nerasporedjenih A je jednak skupu modula koje treba rasporediti. Iz skupa nerasporedjenih modula selektuje se modul m funkcijom select(A), a funkcijom place(m,P) vrsi se njegovo dodavanje skupu rasporedjenih modula, odnosno njegovo rasporedjivanje na ploci. Proces se zaustavlja kada svi moduli budu rasporedjeni.

Najbitnije su funkcija selektovanja modula i funkcija rasporedjivanja. Prva odredjuje redosled kojim ce se moduli rasporedjivati, dok od druge zavisi na koju poziciju ce modul biti smesten. Konacno resenje razmestaja zavisi od obe ove funkcije. Najpoznatiji metodi ovog tipa su Cluster Development, Random Placement, Pair Linking, a medjusobno se razlikuju bas u ovim funkcijama.

Kao modul koji ce biti razmesten, najcesce se iz skupa nerazmestenih bira modul koji ima najjace veze sa skupom vec rasporedjenih modula, a za lokaciju na kojoj ce selektovani model biti smesten se uzima ona sa minimalnom vrednoscu funkcije cene.

Kvalitet ovako dobijenog resenja razmestaja umanjuje cinjenica da se optimalna pozicija modula odredjuje samo na osnovu povezanosti tog modula sa skupom vec rasporedjenih modula. Takodje, kada vise modula zadovoljava selekciono pravilo ili pak vise lokacija ima istu funkciju cene, onda se kandidati moduli i kandidati lokacije biraju slucajno, sto naravno umnogome pogorsava kvalitet resenja razmestaja. No, prednost ovih u odnosu na druge algoritme su jednostavnost i brzina rada.

  7. ALGORITAM MINIMALNOG PRESEKA

Ovim algoritmom se minimizira funkcija preseka veza. Naime, neka je C={c₁,c₂,..., c_k} skup horizontalnih i vertikalnih linija koje presecaju plocu, i neka je v(c_i) vrednost funkcije preseka veza za liniju preseka c_i. Cilj ovog algoritma je da se odredi razmestaj modula koji ce minimizirati neku funkciju F srazmernu vrednostima funkcija preseka veza za sve linije c_i. Kao funkcija cilja se koristi funkcija sledeceg oblika:

F₂=min v(c_k) | min v(c_k-1) | ... | min v(c₁)

gde se simbol " | " cita kao "pod uslovom da je" . Algoritam vrsi sukcesivnu minimizaciju funkcija preseka veza za svaku liniju preseka posebno i to u odredjenom redosledu c₁,c₂,..., c_k.

Osnovu algoritma minimalnog preseka cini deoba skupa modula koje treba razmestiti M={m₁,m₂,..., m_n}, na grupe modula G={g₁,g₂,...,g_t} tako da je broj veza izmedju modula iz razlicitih grupa minimalan. Rad algoritma se najbolje moze opisati preko Slike 16.

.

Slika 16. Tok algoritma

Opsti algoritam minimalnog preseka bi mogao da izgleda ovako:

g₁=M;

G={g₁};

line_sequence_gen(C);

while( (sve linije preseka nisu procesirane) and

bar jedna grupa sadrzi vise od jednog modula) ) {

cut(G, c_i);

}

Ovde line_sequence_gen(C) generise sekvencu linija preseka C, a cut(G, c_i) deli grupe modula iz G imajuci u vidu liniju c_i tako da je v(c_i)=min. Ovde su znaci bitne dve funkcije: 1.izbor sekvence linija preseka i redosleda njihovog procesiranja i 2.deoba jednog skupa modula na dva tako da je broj njihovih medjusobnih veza minimalan. Izbor sekvence linija preseka je u tesnoj vezi sa geometrijom cipa, odnosno konacnim izgledom layout-a. U literaturi se najcesce srecu dva nacina resavanja ovog problema poznati kao Slice/Bisection i Quadrature koji su ilustrovani na Slici 17.

Slika 17. Najcesce koriscene sekvence linija preseka

Prvi nacin je pogodan za stilove koji poseduju nizove modula (gejtovske matrice i standardne celije). Linije preseka su tako izabrane da se prvo moduli razmeste po nizovima procesiranjem horizontalnih linija preseka. Razmestaj modula unutar niza odredjuje se procesiranjem vertikalnih linija. Kod drugog nacina, vrsi se naizmenicno procesiranje horizontalnih i vertikalnih linija preseka.

7.1 ALGORITAM KERNIGHAN - LIN-A

Koristi se za resavanje problema deobe skupa modula. Ova procedura se moze opisati na sledeci nacin:

1. Konstruisati pocetno resenje deobe. To se moze uraditi slucajnom deobom skupa M na A i B.
2. Odrediti par modula a_1Î A i b_1Î B koji daje maksimalno g₁ (g je mera promene broja medjusobnih veza izmedju skupova A i B). Zameniti module a₁ i b₁. Ponoviti prethodni proces pri cemu a₁ i b₁ iskljuciti kao kandidate za zamenu. Prethodni proces se nastavlja dok se ne iscrpe mogucnosti za zamenu (n puta). Tako je generisana sekvenca modula iz A i B kao i promena u medjusobnim vezama: a₁, a₂, ..., a_n; b₁, b₂, ..., b_n i g₁, g₂, ..., g_n.
3. Odrediti vrednost k tako da ima minimalnu vrednost.
4. Novo kvalitetnije resenje deobe dobice se ako se izmedju skupova A i B izvrsi razmena prvih k modula iz dobijene sekvence.
5. Prethodni postupak ponoviti od koraka 2, sve dok je G>0 i k>0.

Prethodni algoritam ne daje bas globalno optimalno resenje, ali ipak zadovoljava u pogledu kvaliteta. Po potrebi, do kvalitetnijeg resenja se moze doci ponavljanjem postupka deobe sa razlicitim pocetnim resenjima. Da bi se ovaj metod deobe mogao koristiti u algoritmima minimalnog preseka, mora da pretrpi male izmene.

Do skora, klasa algoritama minimalnog preseka je bila najcesce koriscena za razmestaj u komercijalnim softverima za projektovanje layout-a. Medjutim, cinjenica je da kvalitet njihovih resenja u mnogome zavisi od izbora sekvence linija preseka, tako da je primeceno da ovi algoritmi daju resenja manjeg kvaliteta kada prirodna deljivost kola ne odgovara sekvenci linija preseka.

  8. METODI BAZIRANI NA OPTIMIZACIJI KONVEKSNIH FUNKCIJA

Ovi metodi bazirani su na optimizaciji funkcije oblika:

Kod klase konveksnih funkcija do njihovog globalnog optimuma se dolazi na relativno lak nacin, resavanjem dva sistema linearnih jednacina po koordinatama centara modula. Tako da na osnovu oznaka u prethodnoj formuli, ovi sistemi se dobijaju kao:

U opstem slucaju, resenje koje pri tome nastaje predstavlja ilegalan razmestaj s obzirom da su moduli tretirani kao materijalne tacke, bez dimenzija, pa je preklapanje modula u resenju prisutno. Takodje, nisu ispunjeni ni ostali uslovi diktirani stilom projektovanja. Ovo resenje daje samo dobar relativan razmestaj modula, pa je i poznato kao relativan razmestaj. Iza njega sledi jos jedna (ili vise) faza koje ce ilegalan razmestaj prevesti u legalan. Ova procedura je poznata pod nazivom geometrijski razmestaj.

  8.1 RELATIVNI RAZMESTAJ

Kao sto je vec receno, kod relativnog razmestaja resenje koje se dobija dato je u obliku spiska koordinata centara pokretnih modula (x_i, y_i). Pogledajmo konkretan primer odredjivanja relativnog razmestaja kola cija je logicka sema data na Slici 18. sa rasporedom stopica datim na Slici 19.

Slike 18. i 19. Logicka sema primera i raspored stopica

U ovom primeru broj pokretnih modula n=3; broj fiksiranih modula (stopica) n_s=6; broj veza je n_c=8. Neophodno je odrediti matrice incidencije izmedju veza i pokretnih modula, a i izmedju veza i fiksiranih modula, b. Sledeci korak u formulisanju sistema jednacina jeste odredjivanje matrice veza izmedju pokretnih modula, C,i matrice veza izmedju pokretnih i fiksiranih modula, F. Zatim treba sa Slike 19. ocitati koordinate polozaja fiksiranih modula, i onda pristupiti formiranju matrica i vektora sistema jednacina za dobijanje relativnog razmestaja. Resavanje tako dobijenog sistema jednacina daje koordinate centara pokretnih modula (x_i, y_i) i=1,2,3. Slika 20. prikazuje resenje relativnog razmestaja razmatranog primera gde su skicirana i Euklidska stabla veza u kolu.

Slika 20. Relativni razmestaj razmatranog primera

Opisani nacin formulacije sistema jednacina relativnog razmestaja vazi za nepraktican kako pri rucnom formiranju, tako i uz pomoc racunara. Tako da se u praksi najcesce koristi pristup slican formulaciji jednacina kod elektricne simulacije, tj. pristup nalepnica.

Osim cinjenice da je relativni razmestaj ilegalan, on u sebi sadrzi jos dva problema koji nisu eksplicitno iskazani. Naime, kada u kolu ne postoje fiksirani moduli, sistemi jednacina postaju homogeni pa resenje relativnog razmestaja postaje trivijalno tj. svi moduli leze u istoj tacki. Zato se ovakvi slucajevi ne mogu resavati na opisani nacin. No, cak i kada u kolu postoje fiksirani moduli, primeceno je da se u resenju relativnog razmestaja pokretni moduli grupisu oko centra ploce, sto potvrdjuje primer sa Slike 21.

To znatno otezava drugu fazu ovih metoda, fazu geometrijskog razmestaja jer se ona svodi na to da se svaki modul smesti u legalnu lokaciju na ploci koja je najbliza njegovom trenutnom polozaju. I tada mogu da se pojave slucajevi da dva ili vise modula treba smestiti u istu lokaciju, sto je nedopustivo. A resavanja ovakvih konflikata dovodi do drasticnog narusavanja relativnog razmestaja, tj. do resenja smanjenog kvaliteta.

Slika 21. Primer relativnog razmestaja

Slede najzanimljiviji i najcesce korisceni nacini za poboljsanje osobina relativnog razmestaja.

  8.2 RELATIVNI RAZMESTAJ BEZ FIKSIRANIH MODULA

Ovde je potrebno pronaci netrivijalni minimum funkcije L_u. Postupak je opisan u radu. Ali treba primetiti da i ovaj nacin nije pogodan tj. prilicno je zamoran kada razmestamo veliki broj modula. Tada se pristupa rucnom rasporedjivanju i fiksiranju izvesnog broja modula, uglavnom onih na periferiji, odnosno stopica kod integrisanih kola.

  8.3 SMANJENJE GRUPISANJA MODULA

Prvi nacin, koji je predlozio Blanks, nalazenje relativnog razmestaja svodi na uslovnu minimizaciju konveksne funkcije L_u. Ovde je pretpostavljeno da je koordinatni sistem postavljen tako da se koordinatni pocetak poklapa sa centrom ploce. Uslov  onda obezbedjuje da relativni razmestaj bude centriran, odnosno simetrican u odnosu na X i Y ose. Ako se pretpostavke radi zeli razmestaj sa r kolona i s vrsta (pri cemu mora da vazi r´ s=n), ploca se izdeli sa r vertikalnih i s horizontalnih linija definisuci na taj nacin mrezu za razmestaj. U cvorovima mreze se nalaze potencijalne lokacije gde ce moduli biti smesteni.

Drugi nacin ublazavanja grupisanja modula predlozili su Quinn i Breuer u svom radu. Ovde se vrsi direktna intervencija u polazni sistem jednacina, dodajuci clanove koji ce teziti da module medjusobno udalje, s tim sto pri tome sistem jednacina postaje nelinearan. Da bi dosli do pogodnog sistema jednacina, Quinn i Breuer su koristili analogiju problema razmestaja sa uravnotezavanjem sila. Naime, polazna osnova pri tome bio je Hook-ov zakon. Tako da je ovde kvalitet relativnog razmestaja obezbedjen cinjenicom da je sila izmedju dva modula proporcionalna broju veza izmedju njih i da ta sila deluje tako da tezi da ta dva modula priblizi. Zato ce jako povezani moduli u resenju relativnog razmestaja biti medjusobno blizu, za razliku od slabije povezanih, odnosno ne povezanih modula. No, pravo poboljsanje relativnog razmestaja se postize tek uvodjenjem tzv. odbojnih sila izmedju nepovezanih modula, cime se oni medjusobno udaljavaju.

  8.4 GEOMETRIJSKI RAZMESTAJ

To je druga faza metoda baziranih na optimizaciji konveksnih funkcija, koja sledi iza faze relativnog razmestaja. Zadatak geometrijskog razmestaja je da na osnovu relativnog razmestaja generise resenje u kome nece biti preklopljrnih modula i da takvo resenje ispunjava uslove stila projektovanja, a da pri tome ono ostane sto je moguce slicnije resenju relativnog razmestaja. Najprirodniji nacin da se generise legalno resenje jeste da se svaki modul pomeri u najblizu legalnu lokaciju. To nam je ilustrovano na sledecoj slici gde je dat najpre relativan razmestaj, a iza toga konacno resenje.

Slika 22. Relativni razmestaj i konacno resenje

Problem koji se gotovo uvek javlja je da vise modula konkurise da bude smesteno u istu lokaciju. Ovaj problem je u literaturi poznat kao linearni problem dodeljivanja. za njegovo resavanje se uvde posebni algoritmi. Medjutim, oni bas ne predstavljaju najefikasnije resenje jer ne garantuju optimalnost resenja u smislu minimuma polazne konveksne funkcije, a i zbog slozenosti algoritma i velikog utroska racunarskog vremena.

Geometrijski razmestaj se najcesce resava prostijim, brzim ali manje efikasnim procedurama koje se zasnivaju na heuristici, s tim sto iza ove uvek sledi i faza iterativnog poboljsanja.

Prvi nacin se ukratko sastoji u sledecem:

1. Na osnovu relativnog razmestaja sortirati module saglasno rastojanju od centra ploce u opadajucem redosledu
2. Smestati module po tom redosledu. Svaki modul smestiti u najblizu slobodnu lokaciju na ploci.

Pri ovome ce dosta informacija iz relativnog razmestaja biti izgubljeno ali je kvalitet resenja ipak zadovoljavajuci.

Drugi nacin za generisanje legalnog resenja na osnovu relativnog razmestaja zasnovan je na kombinaciji metoda baziranih na optimizaciji konveksnih funkcija i algoritma minimalnog preseka. Procedura se moze ukratko opisati na sledeci nacin:

1. Sortirati module na osnovu njihovih y koordinata u opadajucem redosledu
2. Odrediti prvih k modula iz spiska cija je suma sirina priblizno jednaka srednjoj sirini niza W_B. Ispod k-tog modula postaviti liniju preseka.
3. Iz spiska izbaciti prvih k modula i ponoviti postupak sve dok se iz spiska ne iscrpe svi moduli.
4. Od modula iz istih pojasa formirati nizove gejtovske matrice.
5. Unutar svakog niza, na osnovu x koordinata, urediti module s leva na desno u rastucem redosledu.

Sve ovo je ilustrovano na Slici 23.

Slika 23. Primer geometrijskog razmestaja

  9. METODI ITERATIVNOG POBOLJSANJA

Ovim metodom se pokusava da se startujuci od nekog inicijalnog generise bolje resenje. Unutar jedne iteracije vrsi se selektovanje izvesnog broja modula i njihovo smestanje na alternativnim lokacijama. Ako rezultujuca konfiguracija ima manju cenu od prethodne, ona se prihvata, u suprotnom vrsi se vracanje pomerenih modula na njihove prethodne lokacije. Na Slici 24.a) prikazan je opsti algoritam ove klase metoda. Koriscene su sledece oznake: R_o, R i R_new predstavljaju inicijalno, trenutno i novogenerisano resenje razmestaja, a F i F_new su funkcije cene trenutnog i novogenerisanog resenja.

Slika 24. Opsti algoritam metoda iterativnog poboljsanja

U algoritmu se uocavaju tri funkcije od znacaja: score(R), generate(R), accept(F,F). Funkcija score(R) ima za zadatak da sracuna funkciju cene resenja R. Funkcija generate(R) generise novo na osnovu trenutnog resenja R. Generisanje se najcesce obavlja zamenom dva ili vise modula. Funkcijom accept sprovodi se odluka o prihvatanju ili odbacivanju novonastalog resenja razmestaja. Funkciju realizuje modul cija je struktura data na Slici 24.b). Novo resenje se prihvata ako je njegova cena manja od cene prethodnog resenja.

Algoritmi iz ove klase uglavnom se razlikuju po funkcijama score i generate dok je accept kod svih ista.

Odlika ovih metoda je da novo resenje razmestaja prihvataju samo ako ono izaziva negativan prirastaj u funkciji cene. Zbog toga postoji velika opasnost od konvergiranja iterativnog procesa ka lokalnom optimumu, sto je i najveci nedostatak ovih algoritama. I pored toga, ovo je klasa metoda koja se odlikuje i svojom brzinom i kvalitetom resenja koja daju. Najpoznatiji metodi iz ove klase su metod zamene parova, metod zamene suseda, metod zamene upravljan silom, relaksacija u parovima upravljana silom i generalizovana relaksacija upravljana silom.

  9.1 METOD ZAMENE UPRAVLJAN SILOM

Ovaj metod je baziran na analogiji sa uravnotezavanjem sila. Neka nam je poznato neko trenutno resenje razmestaja i neka je ono legalno tj. moduli su vec smesteni u legalnim lokacijama ploce. Da bi to resenje bilo optimalno sa stanovista minimuma konveksne funkcije, potrebno je da su sile koje deluju na module jednake nuli. Ispunjavajuci taj novi uslov dobijamo nove koordinate polozaja centra modula m_i. Ta nova tacka sa koordinatama (x_i,y_i) naziva se tackom nulte sile modula m_i i oznacava se t(m_i). Skoro uvek se desava da da se tacka nulte sile ne poklapa ni sa jednom legalnom lokacijom ploce. Zbog toga je neophodno da se, umesto u tacku nulte sile, modul smesti na najblizu lokaciju koju nazivamo lokacijom minimalne sile modula m_i i oznacavamo sa l(m_i). Ovo je ilustrovano na Slici 25.

Slika 25. Tacka nulte sile i lokacija minimalne sile modula

Na osnovu prethodnog izlaganja, moze se zakljuciti da se odredjivanje optimalnog razmestaja moze obaviti sledecom iterativnom procedurom:

1. Generisati pocetno resenje
2. Iz skupa modula selektovati jedan
3. Selektovani modul smestiti u njegovu lokaciju minimalne sile.

Korake 2. i 3. ponavljati dok se ne postigne konvergencija.

Da bi ova procedura mogla i prakticno da se upotrebljava, mora da pretrpi izvesne izmene. Cest je slucaj da je lokacija minimalne sile zauzeta. Pretpostavimo da se to desilo i da je trenutno resenje prikazano na Slici 26.

Slika 26. zamena u konfliktnim situacijama

Jedno od najprostijih resenja ovog konflikta je sledece. Odredi se lokacija minimalne sile modula koji je vec smesten na lokaciji koja nas interesuje, na nasoj slici to je modul m_j. Ako se dobije da je l(m_j)^nş l(m_i)^n-1, onda se jednostavno zamene moduli m_i i m_j. U suprotnom, modul m_i treba zameniti sa jednim od tri suseda u pravcu sile koja deluje na njega. Ako se pri tome postigne smanjenje konveksne funkcije, promenu treba prihvatiti i preci na korak 2. U suprotnom, pokusati zamenu sa jednim od preostala dva suseda. Ako nijedna zamena nije bila uspesna, prelazi se na korak 2, odnosno, selektuje se naredni modul kao kandidat za pomeranje, a iterativni postupak se nastavlja.

Koji je nacin selektovanja modula? Najpre se za svaki modul sracuna broj njegovih veza sa ostalim modulima. Zatim se formira lista modula gde su oni poredjani po opadajucim vrednostima prethodno izracunate velicine. U toku iterativnog procesa, moduli se sukcesivno obradjuju u redosledu koji je definisan ovom listom.

Sto se tice kriterijuma za zaustavljanje petlje, on se recimo moze definisati tako da se proces zaustavlja kada vise nema znacajnijih poboljsanja u resenju razmestaja.

Algoritam ocvrscavanja je iterativna procedura bazirana na analogiji uredjivanja atoma u kristalima sa jedne strane i razmestanja modula pri projektovanju layout-a, sa druge. Naime, kod fizickog sistema koji je na visokoj temperaturi, atomi ce biti pokretni i nalazice se daleko od svog polozaja minimalne energije. Kada se temperatura smanjuje atomi ce biti sve blize svojim lokacijama minimalne energije. Na temperaturi smrzavanja, atomi vise nece biti pokretni i zauzece takav polozaj da sistem ima minimalnu energiju. Ako sada skup modula koje treba razmestiti posmatramo kao atome fizickog sistema, a funkciju kojom ocenjujemo kvalitet resenja razmestaja (funkciju cene) kao energiju tog sistema, izlozeni proces moze biti iskoriscen za odredjivanje optimalnih polozaja modula tako da vrednost funkcije cene konacnog resenja bude minimalna.

U Tabeli 1. prikazana je analogija izmedju velicina iz domena fizike i problema razmestaja.  

Tabela 1.

Prethodno razmatran proces ocvrscavanja moze biti simuliran procedurom koja je prikazana na Slici 27. Ovde su koriscene sledece oznake: T je temperatura, R_o pocetno resenje razmestaja, TĄ pocetna vrednost temperature, R je trenutno a R_new novogenerisano resenje, F i F_new su funkcije cene trenutnog i novogenerisanog resenja.

Kako je i algoritam ocvrscavanja iterativnog karaktera, struktura mu je slicna algoritmima iz prethodnog izlaganja. Zadatak funkcija score, generate i accept je isti, dok u njihovoj realizaciji postoje manje ili vece razlike. Ovde su prisutne jos dve funkcije: update i random. Prvom se kontrolise temperatura, odnosno proces hladjenja, a druga generise slucajne brojeve sa uniformnom raspodelom u intervalu koji je zadat parametrima funkcije.

Slika 27. Algoritam ocvrscavanja

Dakle, algoritam pocinje odredjivanjem pocetnog resenja (R=R₀), a kontrolnom parametru T se dodeljuje dovoljno velika vrednost (T=Tµ ). Ova dva koraka cine inicijalizaciju iterativnog postupka. Zatim pocinje sam iterativni preces koji u sebi sadrzi dve petlje: spoljasnju i unutrasnju. Unutar unutrasnje petlje, ciklus se odvija na sledeci nacin: generise se novo resenje funkcijom generate izmenom trenutnog resenja. Nakon toga odredi se njegova funkcija cene F_new. Funkcijom accept, na osnovu funkcija cene trenutnog i novogenerisanog resenja, kao i temperature, sprovodi se odluka o prihvatanju novogenerisanog resenja kao trenutnog za naredni ciklus, ili njegovom odbacivanju. Iterativni proces unutrasnje petlje odvija se sve dok sistem resenja ne udje u stabilno stanje odnosno, receno jezikom termodinamike dok sistem ne dostigne ekvilibrijum. Zbog toga je i kriterijum zaustavljanja unutrasnje petlje poznat kao detektovanje ekvilibrijuma. Zatim se funkcijom update racuna temperatura za naredni ciklus spoljasnje petlje, pri cemu je naredna temperatura manja od prethodne (da bi se sistem hladio). Ceo proces se nastavlja sve dok temperatura ne bude dovoljno mala da se sistem moze smatrati smrznutim. S tim u vezi, kriterijum zaustavljanja spoljasnje petlje, a samim tim i celog iterativnog procesa, poznat je kao detektovanje tacke smrzavanja.

Receno je vec da kod ovog algoritma postoje neke razlike u realizaciji funkcija generate, score i accept. Najveca i najbitnija razlika jeste u funkciji accept. Na Slici 28. prikazan je izgled ove funkcije u algoritmu ocvrscavanja. Glavna odlika algoritma je upravo ta da se u toku iterativnog procesa vrse prihvatanja i novih resenja koja izazivaju pozitivan prirastaj u funkciji cene, odnosno resenja koja su losija od vec postojeceg. Ova osobina je najveca prednost algoritma, a ne mana sto se da i pokazati analizom Slike 3. Recimo da iterativnim postupkom treba da se odredi minimum funkcije sa slike i da proces startuje od tacke M₀. Klasicnim iterativnim postupcima, koji prihvataju resenje samo ako je funkcija u narednoj tacki manja no u prethodnoj, doslo bi se do tacke M₁ kao resenja problema. Ali postoji bolje resenje od ovog, pa M₁ ocigledno predstavlja lokalni minimum. Osobina algoritma ocvrscavanja da prihvata resenja koja izazivaju pozitivan prirastaj funkcije omogucice da se iz tacke M₁ dodje do M₂, a kasnije i do globalnog optimuma funkcije, odnosno tacke M₃. Drugim recima, realizacijom funkcije accept kao na Slici 1.b) eliminisana je opasnost konvergiranja iterativnog procesa algoritma ka lokalnom minimumu. Zato algoritam ocvrscavanja daje izvrsna resenja, a njegova sposobnost da pobegne iz lokalnog minimuma svrstava ga u klasu tzv. Hill-Climbing algoritama. S druge strane, baziran je na procesu slucajnog karaktera (funkcija random) pa algoritam pripada i klasi Monte-Carlo metoda, odnosno klasi Stohastickih metoda.

Slika 28. Lokalni i globalni minimum

Iako izgleda jednostavan, pri njegovoj realizaciji treba dati odgovore na sledeca pitanja:

• Kako odrediti pocetnu temperaturu?
• Kako generisati pocetno resenje?
• Kako generisati novo resenje?
• Kako smanjivati temperaturu?
• Kako detektovati ekvilibrijum i tacku smrzavanja?

GENERISANJE POCETNOG RESENJA Skoro u svim realizacijama ovog algoritma, pocetno resenje razmestaja se generise slucajno.

GENERISANJE NOVOG RESENJA Ovo obavlja funkcija generate i bazira se na lokalnim transformacijama vec postojeceg tj. trenutnog resenja. Te lokalne transformacije u literaturi se nazivaju perturbacije ili pomeranja. U upotrebi su razliciti tipovi perturbacija. Najznacajnije i najcesce su: pomeranje jednog modula, zamena dva ili vise modula, rotiranje modula i mirorovanje modula. Svi ovi tipovi perturbacija ilustrovani su na Slici 29.

Slika 29. Tipovi perturbacija

Definisanjem skupa perturbacija definise se u stvari strategija generisanja novog resenja. U literaturi se najcesce kao skup perturbacija dovoljnih da obezbede kvalitet strategije generisanja resenja koriste perturbacije pomeranja jednog modula, zamena dva modula, i ako to tehnologija u kojoj ce layout biti realizovan dozvoljava, uvode se i perturbacije rotiranja i mirorovanja.

REALIZACIJA FUNKCIJE SCORE Zadatak ove funkcije je da sracuna funkciju cene resenja razmestaja. Najopstiji oblik funkcije cene koji moze biti primenjen u algoritmu ocvrscavanja bi bio: F=l _LL+l _DD+l _AA , gde je L funkcija duzine veza, D je funkcija gustine veza, a A je funkcija povrsine ploce.

Za razliku od relativnog razmestaja gde je funkcija cene morala biti diferencijabilna, ovde takvo ogranicenje ne postoji. Jedino ogranicenje je da ova funkcija mora da preslikava skup resenja razmestaja u skup realnih brojeva. I ukupna duzina veza L se najcesce racuna po metodu poluobima.

Kada se razmatra opstiji problem razmestaja gde moduli imaju razlicite dimenzije pa je moguce njihovo preklapanje u medjuresenjima, funkcija cene trpi izvesne izmene. Naime, postoje dva nacina da se dodje do konacnog resenja bez preklopljenih modula. Kod prvog se modifikuje funkcija cene tako da dobija sledeci oblik: F=l _LL+l _DD+l _AA +l _OO , gde je O funkcija koja odslikava preklapanje modula u trenutnom resenju.

Kod drugog nacina modifikuje se strategija generisanja novih resenja, tako da se u toku iterativnog procesa algoritma ocvrscavanja vrsi pretrazivanje samo na skupu legalnih resenja. Kod projektovanja layout-a u stilu gejtovskih matrica ili standardnih celija, uslov da se moduli nalaze u nizovima se uglavnom resava modifikacijom strategije generisanja novih resenja.

ODREDJIVANJE INICIJALNE I TEMPERATURE SMRZAVANJA

D F_max i D F_min su maksimalni odnosno minimalni pozitivni prirastaj funkcije cene

p_max i p_min su verovatnoce sa kojima ce resenja koja izaziva D F_max odnosno D F_min biti prihvacena

KRITERIJUM ZAUSTAVLJANJA UNUTRASNJE I SPOLJASNJE PETLJE U najprostijim realizacijama algoritma, unutrasnja petlja je konstantne duzine, znaci da se za svaku temperaturu obavi isti broj iteracija, recimo K. To K se dobija kao: K=An

gde je A eksperimentalno odredjena konstanta, a n broj modula koji se razmestaju.

Spoljasnja petlja se zaustavlja jednostavno kada temperatura padne ispod temperature smrzavanja.

SMANJENJE TEMPERATURE Najjednostavniji nacin upravljanja temperaturom svodi se na sledeci izraz: T_nenj=a T_old

Koeficijent a je pozitivan parametar manji od jedinice da bi se temperatura smanjivala. Najcesce se uzima da je a =0.9. Funkcija update upravo realizuje prethodni izraz.

Na osnovu prethodno recenog, najprostija realizacija algoritma ocvrscavanja je prikazana na Slici 30.

Slika 30. Najprostija realizacija algoritma ocvrscavanja

UTICAJ KONTROLNIH PARAMETARA NA OSOBINE ALGORITMA

Sa povecanjem pocetne temperature povecava se kvalitet konacnog resenja, odnosno smanjuje njegova funkcija cene. S druge strane, da bi se algoritam izvrsavao za sto krace vreme, pocetna temperatura treba da je sto niza. Zbog toga je najbolje da se pocetna temperatura postavi u oblasti visokih temperatura blizu granice ove oblasti i oblasti srednjih temperatura.

Sto se tice uticaja temperature smrzavanja na kvalitet konacnog resenja, ocigledno je da sto je T₀ manje bice manja i energija konacnog resenja. Dok s druge strane, smanjenje temperature smrzavanja izaziva povecanje vremena izvrsavanja algoritma ocvrscavanja.

Za parametar A rekli smo da predstavlja broj iteracija unutrasnje petlje po jednom modulu. On mora imati vrednost koja ce obezbediti dovoljno veliki broj iteracija da sistem na svakoj temperaturi dostigne ekvilibrijum. U suprotnom proces ce konvergirati ka losijim resenjima.

Ali zato povecanje parametra A povecava vreme izvrsavanja algoritma, te je potrebno pronaci kompromis izmedju ova dva zahteva.

Parametar a posredno odredjuje broj iteracija spoljasnje petlje algoritma ocvrscavanja. Za manje a manji je broj iteracija, odnosno algoritam se izvrsava za krace vreme. S druge strane, manje a izaziva brze smanjivanje temperature, sto dovodi do konvergiranja algoritma ka losijim resenjima. I ovde se mora ici na kompromis.

Zakljucak je, da kontrolni parametri deluju na algoritam tako da ako se zeli kvalitetnije konacno resenje, cena je veci utrosak vremena.

U radu Srdjana Milenkovica na par strana su obradjeni rezultati iz teorijske analize algoritma ocvrscavanja. Osnovu teorije cine teorije slucajnih, Stohastickih procesa i Markovljevih lanaca. Zainteresovane upucujem na Srdjanov magistarski rad odnosno knjigu CADEC 2 gde mogu da pronadju i reference za detaljnije upoznavanje sa ovom problematikom.

Iako algoritam ocvrscavanja daje resenja odlicnog kvaliteta, on se odlikuje sporom konvergencijom, odnosno velikim utroskom racunarskog vremena. U prevazilazenju ovog nedostatka tj. ubrzanju algoritma uocavaju se dva pravca. Jedan nacin je softversko ubrzanje algoritma, a drugi ubrzanje algoritma uz pomoc hardvera.

Cilj je da se razvije procedura koja ce biti nezavisna od problema i koja ce se izvrsavati brze no originalni algoritam. Jedini nacin da se to ostvari je da se problemi odredjivanja pocetne temperature, smanjivanje temperature, detektovanje ekvilibrijuma i tacke smrzavanja, rese na nacin koji nece zavisiti od problema koji se algoritmom ocvrscavanja resava. Resenja pomenutih problema koja na ovaj nacin nastaju poznata su kao metodi za adaptivno upravljanje procesom hladjenja i predstavljaju podskup metoda softverskog ubrzanja algoritma ocvrscavanja.

ODREDJIVANJE POCETNE TEMPERATURE Zasniva se na zakljuccima izvedenim ranije da pocetna temperatura treba da bude u oblasti visokih temperatura a blizu granice ove oblasti i oblasti srednjih temperatura. Postupak bi se sastojao u sledecem: Posle formiranja pocetnog resenja izvrsiti dovoljno veliki broj iteracija algoritma ocvrscavanja prihvatajuci svako novogenerisano resenje sto je ekvivalentno slucaju kada temperatura ima beskonacno veliku vrednost. Onda se racuna kvadrat standardne devijacije pri beskonacnoj temperaturi, a pocetna temperatura se odredjuje iz izraza:

Tµ =ks (T)

Tipicno je k=20.

SMANJENJE TEMPERATURE Osnovna ideja za adaptivno upravljanje temperaturom svodi se na to da se temperatura moze brze smanjivati u oblastima gde energija sistema ne zavisi od temperature, a da to nema velikog uticaja na konacno resenje. Ovo se moze ostvariti ako se temperatura smanjuje tako da razlika energija u ekvilibrijumu na dvema susednim temperaturama ostaje konstantna. Vrlo cesto koriscen izraz za smanjenje temperature je:

gde je m broj iteracija spoljasnje petlje algoritma ocvrscavanja, l je tipicno 0.7.

U stvarnim implementacijama algoritma ocvrscavanja, da bi se sprecilo prebrzo smanjenje temperature na osnovu prethodnog izraza, odnos T_m+1/T_m se ogranicava tako da ne bude manji od neke minimalne vrednosti (tipicno 0.5).

Postoje jos neki nacini upravljanja temperaturom. Metod zasnovan na pracenju entropije sistema, zatim metod zasnovan na pracenju brzine ulaska sistema u ekvilibrijum itd.

DETEKTOVANJE EKVILIBRIJUMA Ekvilibrijum ili stabilno stanje na nekoj temperaturi T, se odlikuje time da energija sistema konvergira ka nekoj srednjoj vrednosti. Zatim, vektor verovatnoce stanja p(m) konvergira ka stacionarnom vektoru. Adaptivni nacini detektovanja ulaska sistema u ekvilibrijum su bazirani na pracenju konvergencije pomenutih velicina, tj. njihovog ulaska u stabilno stanje.

Jedna od metoda je zasnovana na pracenju konvergencije vektora verovatnoce stanja. Sistem je dostigao ekvilibrijum ako vazi da je:

|D(T_m,k+1)-D(T_m,k)| <e ₁

gde je D(T_m,k) velicina koja se sracunava na sledeci nacin:

Postoji jos jedan nacin detekcije ekvilibrijuma zasnovan na pracenju ponasanja energije sistema. Autori su primetili da po ulasku sistema u ekvilibrijum, sledeca velicina postaje konstantna:

,

gde je n_a(T_m) broj prihvacenih resenja na temperaturi T_m, n(T_m) je broj resenja generisanih na temperaturi T_m, cija je vrednost funkcije cene u opsegu (F(T_m)-s ,F(T_m)+s ), pri cemu je F(T_m) srednja vrednost funkcije cene na temperaturi T_m, a s je parametar koji definise kvalitet aproksimacije ekvilibrijuma.

DETEKTOVANJE TACKE SMRZAVANJA Jedan od najcesce koriscenih nacina detektovanja tacke smrzavanja, odnosno kriterijuma za zaustavljanje procesa hladjenja, zasnovan je na pracenju energije sistema. Ako se energija nije promenila u toku tri ili cetiri iteracije spoljasnje petlje, moze se smatrati da je sistem smrznut.

Drugi nacin se sastoji u pracenju faktora prihvatanja gde se faktor prihvatanja definise na sledeci nacin:

Ovde je n_g(T_m) broj generisanih resenja na temperaturi T_m, a n_a(T_m) je broj prihvacenih resenja. Sa smanjivanjem temperature smanjuje se i faktor prihvatanja, zato se proces hladjenja moze zaustaviti kada faktor prihvatanja opadne ispod neke minimalne vrednosti, odnosno kada je:

a(T_m)<e ₂

Najkomleksniji nacin zaustavljanja procesa hladjenja je onaj gde se taj proces zaustavlja kada se detektuje da je funkcija zavisnosti energije sistema od temperature, postala konveksna.

STRATEGIJA GENERISANJA NOVIH RESENJA Njenim malim izmenama moze se postici znacajna usteda u vremenu izvrsavanja algoritma ocvrscavanja. Ovo se ostvaruje uvodjenjem ogranicavaca perturbacija koji ce unapred eliminisati neuspesne cikluse algoritma. On se definise kao pravougaonik a njegove dimenzije zavise od temperature. Na pocetnoj temperaturi dimenzije ogranicavaca moraju biti jednake dvostrukim dimenzijama ploce, da bi se omogucila zamena i modula iz igla ploce sa svim ostalima. Kada se temperatura smanjuje, dimenzije ogranicavaca treba takodje da se smanjuju, ali ne isuvise brzo jer bi to dovelo do drasticnog narusavanja kvaliteta konacnog resenja. Ovo je za stil standardnih celija ilustrovano na Slici 31.

Slika 31. Smanjivanje dimenzija ogranicavaca perturbacija

OSTALI NACINI SOFTVERSKOG UBRZANJA ALGORITMA OCVRSCAVANJA

Jedan od nacina se sastoji u konstruisanju algoritma kod koga nema odbacenih perturbacija. Drugo interesantno resenje ubrzanja algoritma ocvrscavanja se sastoji u izmeni nacina generisanja pocetnog resenja. Naime, za pocetno resenje se bira kvalitetno resenje generisano, recimo algoritmom minimalnog preseka. Da kvalitet tog resenja nadalje ne bi bio unisten, pocetna temperatura mora brizljivo da se odredi. To je ilustrovano na Slici 32. U ovom slucaju, pocetna temperatura T_in se odredjuje iz uslova da je funkcija cene pocetnog resenja F(R_in) jednaka energiji F(T_in) procesa koji je startovan na klasican nacin od Tµ . Postize se velika usteda u vremenu jer se opseg temperature smanjuje od (Tµ , T₀) na (T_in, T₀).

Slika 32. Odredjivanje pocetne temperature kada je pocetno resenje kvalitetno

Treba istaci da se primenom softverskih nacina postize ubrzanje algoritma ocvrscavanja od 2 do 10 puta.

To je u stvari njegova implementacija na paralelnim racunarima u cilju postizanja hardverskog nacina za ubrzanje algoritma. Ideja se sastoji u tome da se algoritam podeli na vise manjih poslova i da se svaki od njih dodeli posebnom procesoru na obavljanje. Ubrzanje se postize jer se sada ti poslovi obavljaju simultano, a ne sekvencijalno kao kod originalnog algoritma. Jedini problem ovde je kako algoritam podeliti na manje celine koje se mogu obavljati simultano.

Koraci unutar unutrasnje petlje se moraju obaviti sekvencijalno pa se tu ostvaruje mala usteda u vremenu. Najbolji rezultati u ubrzanju se postizu dekompozicijom algoritma ocvrscavanja na nivou Markovljevih lanaca. Mogu se pronaci razlicita resenja ovog problema. U knjizi je opisana paralelna implementacija koja se izmedju ostalog odlikuje i nezavisnoscu od problema koji se resava algoritmom ocvrscavanja. Ovde algoritam ima dva rezima rada, rezim visokih i rezim niskih temperatura. Znacajno je da su na kraju autori pokazali da je sekvenca resenja koja se generise na ovakav nacin ekvivalentna sekvenci resenja kod sekvencijalne implementacije algoritma ocvrscavanja. A postignuto ubrzanje je proporcionalno broju procesora koji rade u paraleli.

Na kraju izlaganja o algoritmu ocvrscavanja treba istaci da on predstavlja ne samo izuzetno efikasan metod za resavanje problema razmestaja, vec i za resavanje sire klase problema kombinatorne prirode. Spomenimo resenje problema projektovanja floorplaning-a integrisanih kola, resenje algoritma za povezivanje u kanalu i takodje, resenje problema logicke simulacije.

Kao sto je vec napomenuto, problem razmestaja se moze posmatrati i kao optimizacioni problem sa ogranicenjima, odnosno moze se definisati i na sledeci nacin:

gde su F_i(p) funkcije cene, a G_i(p) funkcije uslova koje razmestaj mora da zadovolji. Parametri n_F i n_G predstavljaju broj funkcija cene i broj funkcija uslova, respektivno. Argument ovih funkcija je vektor parametara p po kojima se vrsi optimizacija. Parametri koji su obicno smesteni u p su podaci o poziciji i orijentaciji modula, zatim podaci o dodeljivanju gejtova celijama, veza pinovima i slicno.

Analiticki algoritmi za resavanje problema razmestaja razlikuju se od prethodno opisanih metoda po tome sto su funkcije cene i funkcije uslova, analiticke funkcije svojih argumenata, a problem (*) resavaju klasicnim numerickim metodima za opimizaciju.

Prva ideja datira iz 1984. godine jer ranije nije bila u sirokoj upotrebi racunarska oprema potrebna za resavanje takvih problema uz prihvatljivu cenu. Ipak kao pretecu mozemo smatrati algoritme za relativan razmestaj, s obzirom da se oni svode na resavanje sistema linearnih ili nelinearnih analitickih jednacina po koordinatama centara modula, sto i jeste osnova analitickih algoritama.

Najveca razlika izmedju analitickih i algoritama za relativni razmestaj je sto resenje generisano analitickim algoritmom predstavlja legalan razmestaj, a to nije slucaj sa relativnim razmestajem.

U knjizi je prikazan analiticki algoritam za razmestaj celija u gejtovskim matricama. Problem razmestaja celija u gejtovskim matricama se sada definise na sledeci nacin:

minimizirati F(x, y),

pod uslovom da je:

G₁(X,Y)=min,G₂(X,Y)=0,G₃(X)=0, G₄(Y)=0 i G₅(Y)=0.

gde je F(X,Y) funkcija cene koja aproksimira ukupnu duzinu veza u kolu, a koja se u optimizacionim procesima cesce naziva funkcijom cilja, G₁(X,Y) je uslov refleksije modula, G₂(X,Y) je uslov nepreklapanja modula, G₃(X) i G₄(Y) su uslovi x i y sabijanja, respektivno, a G₅(Y) je uslov diskretizacije y koordinata centara celija. X i Y predstavljaju vektore koordinata centara celija. Zbog konvergencije, pozeljno je da sve funkcije u prethodnom izrazu budu diferencijabilne.

Uslov refleksije je dodat da bi poboljsao resenje relativnog razmestaja tezeci da poveca rastojanje izmedju modula. Uslov nepreklapanja sluzi za eliminisanje pojave preklapanja modula. Uslovi x i y sabijanja obezbedjuju da se sve celije nalaze u centru cipa, dok uslov diskretizacije y koordinata centara celija vrsi smestanje celija u nizove gejtovske matrice. Time je obezbedjeno dobijanje legalnog resenja razmestaja celija kod koga je minimizirana ukupna duzina veza.

EKSPERIMENTALNI REZULTATI Kod ovog analitickog algoritma (opisanog u radu S. Milenkovica) uocavaju se dva zanimljiva nacina resavanja problema grupisanja modula u relativnom razmestaju. Slika 33. pokazuje relativni razmestaj i to pod a) bez ikakve intervencije za smanjenje grupisanja i pod b) kada je primenjen metod Quinn-a i Breuer-a. Moduli su prikazani sa stvarnim dimenzijama, a prikazana su i EuklidskaSteiner-ova stabla veza. Sa slike se primecuje da se malo poboljsanje dobija uvodjenjem odbojnih sila.

Slika 33. Relativni razmestaj bez i sa odbojnim silama

U analitickom algoritmu smanjenje ovog problema je izvedeno uvodjenjem tezina stopica i uslova refleksije. Uvodjenjem tezina stopica u stvari je povecana sila kojom stopice kao moduli koji su rasporedjeni na periferiji, privlace celije ka periferiji cime se njihova skoncentrisanost oko centra ploce smanjuje. Ovo je ilustrovano na Slici 34. Prikazan je relativni razmestaj razmatranog primera za razlicite vrednosti parametra z. Sa povecanjem parametra z ocigledno je da se celije iz centra pomeraju ka periferiji. Za velike vrednosti tezine stopica efekat se zasicuje jer dolazi do uravnotezavanja sila koje teze da privuku celije ka stopicama sa suprotnih strana ploce. Zato se moze smatrati da je z=10 dovoljno da poboljsa resenje relativnog razmestaja.

Slika 34. Uticaj tezine stopica na relativni razmestaj

Dalje poboljsanje se moze postici uvodjenjem uslova refleksije u optimizacioni proces. Delovanje uslova refleksije ima slican efekat kao uvodjenje sila odbijanja kod metoda Quinn-a i Breuer-a. Medjutim, uslov refleksije se razlikuje od njih po tome sto deluje izmedju svake dve celije, a ne samo izmedju nepovezanih, sto takodje doprinosi smanjenju grupisanja. Osim ovoga, uslov refleksije zavisi od dimenzija celija tako da vece odbijanje postoji izmedju sirih celija, cime se jos na nivou relativnog razmestaja generise resenje sa manjim preklapanjem modula. Na Slici 35. prikazan je relativni razmestaj sa refleksijom celija.

Slika 35. razmestaj posle uvodjenja uslova refleksije

Na kraju ilustrujmo Slikom 36. optimizacioni proces prethodno razmatran. Na ovoj slici prikazana su najzanimljivija medjuresenja razmestaja primera koji je sastavljen od 130 celija, 16 stopica, 129 veza a popunjenost gejtovske matrice je 89,3%. Slika a) prikazuje resenje nakon nultog ciklusa, tj. relativni razmestaj. Uvodjenjem uslova x sabijanja a zatim uslova refleksije dobija se resenje prikazano pod b). Slika c) prikazuje resenje nakon eliminisanja preklapanja a d) posle uvodjenja uslova y sabijanja. Rezultat delovanja uslova diskretizacije y koordinata prikazan je pod e), dok je konacno resenje ovog primera dato pod f).

Slika 36. Najzanimljivija medjuresenja razmestaja  

12. GENETICKI RAZMESTAJ

To je jedna zanimljiva ideja za resavanje problema razmestaja. Naime, kod ovog algoritma neke aktivnosti unutar iterativnog procesa podsecaju na pojave u evoluciji jedne populacije, mada se njihova slicnost svodi samo na terminolosku. Ako odredjeni broj resenja oznacimo kao populaciju, onda se algoritam odvija na sledeci nacin:

Prvo se generise inicijalna populacija resenja i to se kako autori preporucuju vrsi slucajno. Na osnovu resenja iz populacije generisu se resenja potomci. To se vrsi tako sto se iz populacije izaberu dva resenja kao roditelji, i na osnovu njih generise se resenje potomak koji ce imati slicnosti sa oba roditelja. Kada je generisan odredjeni broj potomaka, iz skupa roditelja i skupa potomaka vrsi se selekcija resenja koja ce ciniti narednu generaciju, odnosno, izbor resenja koja ce preziveti. Ali se vodi racuna da u narednoj generaciji budu bolja resenja nego u prethodnoj. Logicno je znaci da iz skupa roditelja i skupa potomaka treba birati najbolja resenja. Medjutim, kao i u prirodnom procesu evolucije, pokazalo se da to bas i nije najbolji nacin selekcije. kada je nova generacija populacije formirana, vrsi se njena mutacija. To su u stvari slucajne zamene modula u resenjima razmestaja. To se cini da bi se sprecila prevremena konvergencija, odnosno konvergencija ka lokalnom optimumu. Opisani proces se nastavlja sve dok se ne postigne konvergencija. Kao konacno resenje bira se najbolje iz zadnje generacije.

Ovaj algoritam je sto se tice vremena izvrsavanja i kvaliteta resenja, vrlo blizak algoritmu ocvrscavanja. Autori jos kao prednost ovog algoritma navode njegovu izuzetnu pogodnost za realizaciju na paralelnim racunarima.

13. EVOLUCIONI RAZMESTAJ

Ovaj algoritam ima sasvim drugaciju ideju u odnosu na prethodni. Naime, prva i najveca razlika je da se ovde manipulise samo sa jednim resenjem razmestaja dok su jedinke koje evoluiraju u stvari moduli.

Pocinje se sa generisanjem inicijalnog razmestaja za sta se moze koristiti neki od konstruktivnih algoritama. Zatim se izvrsi procena kvaliteta polozaja svakog modula u resenju. Polozaj modula je kvalitetan ako se on nalazi u blizini modula sa kojim je povezan. U suprotnom, modul je lose rasporedjen. Svakom modulu se kao ocena kvaliteta njegovog polozaja dodeli broj iz intervala (0,100) tako da dobro rasporedjeni moduli imaju vecu ocenu. Zatim se iz istog intervala generise slucajni broj r. Svi moduli sa ocenom vecom od r su dobro locirani i prezivece na trenutnim lokacijama. Ostali, tzv. lose rasporedjeni moduli, se ponovo rasporede nekim konstruktivnim algoritmom. Opisani proces se nastavlja sve do konvergiranja. I ovde se uvode mutacije resenja koje se vrse na isti nacin i iz istog razloga kao kod genetickog razmestaja. Sem mutacija, zastita od konvergencije ka lokalnom optimumu, je izvedena i generisanjem slucajnog broja r kao praga koji razdvaja dobro od lose rasporedjenih modula.

14. ZAKLJUCAK

Problem automatskog razmestaja se proucava vec dve decenije, ali i danas je veoma atraktivan, prevashodno zbog teznje naucnika da pronadju metode koje ce dati resenja sto bliza optimalnom. Algoritam ocvrscavanja je tako i dalje predmet istrazivanja jer on daje resenja koja su veoma bliska optimalnom. Narocito su aktuelna istrazivanja na njegovom ubrzavanju, a najvise na paralelnoj implementaciji. Takodje se slicna traganja vrse i u oblasti genetickih i evolucionih algoritama.

Novi stil projektovanja vrlo slozenih kola poznat kao "more gejtova" (Sea-Of-Gates), ucinio je problem razmestaja vrlo kompleksnim jer ovde treba razmestiti vise desetina hiljada modula. Mnogi opisani algoritmi se ne mogu primeniti zbog velikog zauzeca memorije ili velikog utroska vremena. Zato se proucavaju metodi koji bi bili prilagodjeni ovakvim uslovima.

U toku je i razvoj algoritama za razmestaj modula sa sirokim spektrom dimenzija, ili sto je ekvivalentno, razlicitih stepena integracije. Tako se sada kao elementarni moduli pojavljuju recimo NI, NILI,.. kola, ali i RAM, ROM i slicno. Takodje, razvijaju se i algoritmi za hijerarhijsko projektovanje layout-a, a samim tim i algoritmi koji ce podrzavati hijerarhijsko resavanje problema razmestaja.

Takodje, radi se i na pronalazenju resenja za primenu vestackih neuronskih mreza u oblasti projektovanja layout-a.