Layout visszafejtő program cellás tervezésű integrált áramkörökhöz D R . S Z É K E L Y V L A D I M Í R - B A J I P Á L - D R . MASSZI F E R E N C K E R E C S E N N É D R . RENCZ M Á R T A B M E Elektronikus Eszközök Tanszék KÓNYA ILONA B M E Villamoskari Matematika Tanszék DR. K O L T A I MIHÁLY B M E Elméleti Villamosságtan Tanszék ÖSSZEFOGLALÁS A cikkben bemutatott program — a C E L L I N E X — cellás terve zésű integrált áramkörök layout-jából megállapítja a cellák között megvalósított összeköttetéseket. Ennek alapján generálja az áram kör logikai leírását és ellenőrzi, hogy a megvalósított összekötteté sek megengedettek-e, illetve nincsenek-e triviális hiányok stb. A cikk ismerteti a program jellemzőit és a visszaíejtés legfontosabb algoritmusait. Bemutat néhány eredményközlési formát és útmuta tást ad a program használatára vonatkozóan.
1. Bevezetés Az integrált á r a m k ö r i maszkok előállítása — tudjuk — igen költséges és időigényes feladat. E z é r t elsőrendű fontosságú kérdés, hogy a maszkok lehetőség szerint m á r első v á l t o z a t u k b a n jók legyenek — hiszen az esetleg szükséges megismétlés mind költségkihatásai miatt, mind az átfutási idő növekedése folytán kelle metlenül rontja a tervezés h a t é k o n y s á g á t . Különö-? sen áll ez a berendezésorientált á r a m k ö r ö k r e , ame lyek életképességének alapfeltétele a r e d u k á l t ter vezési, gyártáselőkészítési költség és a vonzóan kis átfutási idő. E z é r t minden lehetőséget meg kell ra gadni a maszktervek menet közbeni ellenőrzésére, hogy tényleges előállításra csak a m á r nagy valószí nűséggel jó maszkok kerüljenek. Mit jelent közelebbről a maszktervek (layouttervek) ellenőrzése? — A tervezés általában számí tógéppel segített m ó d o n t ö r t é n i k (grafikus editorral, digitalizálóval stb.), az e r e d m é n y k é n t előálló maszk tervek tulajdonképpen számítógépi adatfile-ok, ame lyek a maszkok geometriáját, a rajtuk levő geomet riai objektumok, alakzatok összességét definiálják. Ebből az adathalmazból teljesen a u t o m a t i z á l t m ó d o n áll elő a g y á r t á s t szolgáló maszk. A lépések: — az adatokból a mestermaszk előállítása szá mítógép-vezérelt ábragenerátorral, — a mestermaszk végleges méretre kicsinyítése és léptetése, — a gyártási maszkok másolása. Idő és költség szempontjából e g y a r á n t szűk kereszt metszet az ábragenerálás. (Jelenleg k é t ábragenerátor dolgozik az országban; a művelet sebességére az jel lemző, hogy h e t e n k é n t 1—2 LSI IC maszkjai állít h a t ó elő velük.) Ez m i n d e n k é p p e n azt jelenti, hogy még az ábragenerálás előtt, t e h á t a maszkokat leíró számítógépi adatfile-okon kell annyi ellenőrzést el végezni, amennyit csak tudunk. Ez még e x t r é m nagy gépidő felhasználás (akár néhányszor 10 órás CPU idő) mellett is gazdaságos megoldás. Beérkezett: 1984. I . 26. ( A ) Híradástechnika
XXXV.
évfolyam
1984. 8.
szám
DR. SZÉKELY VLADIMÍR A BME Villamosmér nöki Karán kitüntetéssel szerzett oklevelet 1964ben. Egyetemi doktori disszertációját 1970-ben védte meg. Kandidátusi fokozatot 1978-ban szer zett, az integrált áram körök elektro-termikus je
lenségei modellezésének témakörében. 1964 óta a BME Elektronikus Eszközök Tanszék ok tatója; jelenleg docens, tanszékvezető-helyettes, Fő szakterületei: félvezelőeszközök működésé nek fizikája, számítógé pes szimuláció, integrált áramkörök számítógép pel segített tervezése. 1
Ha osztályozni próbáljuk a maszkadatok ellen őrzésének lehetőségeit, azokat k é t nagy csoportba sorolhatjuk. — Szabályellenőrzés
jellegű
műveletek.
Nevezhet
nénk ezeket szintaktikus ellenőrzésnek is. Létez nek ugyanis a maszkalakzatokra olyan alap vető, a technológia által m e g h a t á r o z o t t szabá lyok, amelyeket s e m m i k é p p e n nem szabad á t hágni, amelyek szinte a maszkok „geometriai helyesírását", szintaxisát adják. Ilyenek pél dául egy vezetőcsík minimális szélességére, k é t alakzat minimális távolságára vonatkozó meg kötések. E szabályok összességét nevezzük ter vezési szabályoknak, a rájuk vonatkozó ellen őrzést végzik a tervezési szabály ellenőrző (design-rule check, DRC) programok. ' :?
— Visszafejtés
jellegű
művelétek.
Most azt
ellen
őrizzük, hogy a s z i n t a k t i k u s á n h i b á t l a n layout azt ábrázolja-e, amit kell — szemantikusan he lyes-e t e h á t . „Visszafejtjük" a maszkrajzolatok alapján, hogy hol milyen alkatrész jön majd létre, és azok hogyan kapcsolódnak egymás hoz — vagyis visszafejtjük a layout által k é p viselt á r a m k ö r t . A visszafejtés mélysége különböző lehet aszerint, hogy m i az á r a m k ö r felismert legkisebb alkateleme. Ha ez a legkisebb elem az alkatrész (ellenállás, tran zisztor stb.), akkor beszélünk alkatrészszintű vissza fejtésről. Ha nem alkatrészmélységig, hanem csak egyes részegységekig (tipikusan a cellás tervezésű á r a m k ö r celláiig) fejtünk vissza, akkor ez a cellaszintü visszafejtés. U t ó b b i esetben a cellákon t ú l csak azok összekötő vezetékeit kell felismerni — ezért sok eset ben konnexió-feltárás néven is említik a műveletet. C i k k ü n k b e n a cellaszintű visszafejtés egy lehetséges megvalósításával, az általunk 1983 t a v a s z á n kidol gozott CELLINEX ( C E L L INterconnection EXtraction) programmal foglalkozunk.
341
BAJI
PÁL
A BME Villamosmér nöki Karán 1970-ben szerzett diplomát. A BME Elektronikus Esz közök Tanszékén 1971 — 1973 között ösztöndíjas ként, Schottky dióda tech nológiával foglalkozóit. 1973-tól tanársegédként, 1984-től adjunktusként dolgozik a BME Elektro nikus Eszközök Tanszé ken. Érdeklődési terüle te : félvezető eszközök szá mítógépes modellezése, in tegrált áramkörök számí tógépes tervezése.
KERECSENNÉ DR. RENCZ MÁRTA 1973-ban végzett a BME Villamosmérnöki Kará nak Műszer és Irányítás technika Szakán. Azóta a BME Elektronikus Eszközök Tanszékén dol gozik, jelenleg adjunk tusként. Egyetemi dok tori disszertációját 1979ben védte meg. Szakterü lete : félvezető eszközök számítógépes modellezése, integrált áramkörök szá mítógéppel segített terve zése.
KÓNYA
ILONA
DR. MASSZI
1970-ben szerzett okle velet a Budapesti Műsza ki Egyetem Villamosmér nöki Karának Híradás technikai szakán, majd 1973-ban kitüntetéses vil lamosmérnök-matema tikus szakmérnöki okleve let. 1970-től a Villamos kari Matematika Tanszé ken dolgozik, ahol első sorban numerikus mód szerekkel és számítás technikával foglalkozik.
342
1976-ban szerzett kitün tetéses oklevelet a BME Villamosmérnöki Karán. 1978-ban megvédett mű szaki egyetemi doktori disszertációjának témá ja a vélvezető memória elemek számítógépes mo dellezése volt. Oklevelének megszerzése óta a BME Elektronikus Eszközök Tanszékén dolgozik, je lenleg adjunktusként. Kutatási területe: félve zető struktúrák modelle zése, számítógépes terve zés. 1973-ban szerzett diplo mát a BME Villamos mérnöki Karán. 1976ban megvédett műszaki egyetemi doktori érteke zésének témája az általa kifejlesztett elektromágne ses térszámító program rendszer volt. Oklevelé nek megszerzése óta a BME Elméleti Villa mosságtan Tanszékén dol gozik, jelenleg adjunktus ként. Kutatási területe: elektromágneses tér számí tás, félvezető eszközök és technológia számítógépes modellezése, számítógépes grafika.
2. A CELLINEX-program jellemzői A C E L L I N E X program cellás tervezésű digitális L S I á r a m k ö r ö k layout-ellenőrzésére szolgál [5]. K i dolgozása része annak a fejlesztő m u n k á n a k , amely a Mikroelektronikai Vállalatnál a berendezésorien t á l t integrált á r a m k ö r ö k tervezése software eszköz t á r á n a k létrehozását célozza. Szorosan kapcsolódik a t a n s z é k ü n k által k o r á b b a n kidolgozott C E L L I B cellakönyvtár-kezelő programhoz, amiről a közel m ú l t b a n adtunk ismertetést ugyanezen folvóiratban[4]. A program k ö n y v t á r i cellákból és összeköttetéseik ből álló layout visszafejtésére alkalmas. A layout adatait a Mikroelektronikai Vállalatnál általánosan használt grafikus leíró nyelven olvassa be. A kezel hető layout-méret megfelel a berendezésorientált tervezés által néjiány év t á v l a t á b a n igényeltnek: 400 cella, 2000 jelvezeték, 5000 összeköttetés funkciójú alakzat, mint maximum. Az összeköttetés rétegek száma a kezelhető 20 maszksíkon belül tet szőleges : egyrétegű és többrétegű fémezéssel készülő á r a m k ö r ö k e g y a r á n t visszafejthetők. A program igen h a t é k o n y particionálási t e c h n i k á v a l és gondosan ter vezett algoritmusokkal biztosítja a layout-feldolgozási feladatoknál szokatlanul kis számítási időt (4—5 perc a legnagyobb feldolgozható hálózatra). A program eredményközlése az ellenőrzés változatos formáit szolgálhatja; úgy a l a k í t o t t u k k i azokat, hogy lehetőleg minden tervezői igényt kielégítsenek. A visszafejtett á r a m k ö r például automatikusan továb b í t h a t ó logikai szimulációra, vagy grafikus képernyőn t a n u l m á n y o z h a t j u k a layout-rajzon a logikai jelek terjedési útjait — hogy csak a lehetőségek szélsősé geit említsük.
FERENC
DR. KOLTAI MIHÁLY
3. Algoritmus-kérdések Első ránézésre úgy t ű n h e t , hogy az összeköttetés felderítés nem vet fel komolyabb algoritmus-prob lémákat. Poligonok érintkezését-átfedését, poligonoknak ablakokkal való találkozását kell feltárni és n y i l v á n t a r t a n i . Első b e n y o m á s u n k az lehet, hogy eléggé triviális analitikus geometriai problémák prog r a m o z á s á b a n merül k i a feladat megoldása. A k i m á r találkozott az L S I integrált áramkörök maszkinformációinak gépi feldolgozási problémáival, az tudja, hogy ez nincs egészen így. A maszkok nagy összetettsége miatt a feldolgozandó információ mennyiség m á r olyan hatalmas, hogy a „straightforward" programozási mód m á r nem hozhat meg oldást. Egyrészt a tárolóhelyigény nő meg alapo san. Nem j á r h a t ó az az út, hogy a számítás során Híradástechnika
XXXV.
évfolyam
1984. 8. szám
minden adatot mindig a központi m e m ó r i á b a n tart sunk. Ehelyett a h á t t é r t á r o l ó n őrzött nagy adatfileokon kell a programnak dolgoznia (egyiket a m á s i k b a transzformálni stb.). A C E L L I N E X program által kezelt maximális layout-bonyolultságnál ezek a fileok egyenként 0,5 —1 megabyte-ig is elmehetnek. Másrészt (és ez a tárolóhelygondoknál is súlyosabb) az úgynevezett k é t p a r a m é t e r e s geometriai műveletek időigénye nő meg tűrhetetlenül. Ilyen művelet például az alakzatok érintkezéseinek, átfedéseinek megkere sése. Ezekhez minden alakzatot minden másikkal össze kell vetni. Ha a vizsgált maszksíkon n alakzat van, n
Parücionálási technika. Az alakzatok nagy szá mából eredő p r o b l é m á k a t nagyságrendekkel enyhít heti a layout-terv részekre szabdalása, particionálása, és a műveletek partíciónkénti külön elvégzése [1]. Tegyük fel például, hogy a layout-ot az 1. ábra szerint m i n d k é t i r á n y b a n felosztva, k db partícióra vágjuk. Legyen az alakzatok eloszlása a maszkon egyenletes és egyelőre t e k i n t s ü n k el a partícióhatárok által el v á g o t t alakzatok problémájától. Ekkor egy partícióba n/k alakzat esik és a végzendő műveletek s z á m á öszszesen
" ~2k'
1
'W
z
(i)
2
összevetést kell t e n n ü n k — a műveletszám t e h á t n -nel arányos. 2000 alakzattal számolva és egy össze vetést 200 [xs-mal véve számításba, egyetlen ilyen m ű velet 6-7 perc C P U időt igényelne, ami a teljes program futását órás nagyságrendbe emelné. A vázolt nehézségek indokolttá teszik, hogy az algo ritmus kérdésekről részletesen szóljunk. Ezt tesszük az alábbiakban, m o n d a n i v a l ó n k a t n é h á n y lényeges t é m a köré csoportosítva. 2
vagyis fc-szor kisebb, mint a particionálás nélküli esetben. A nyereség n y i l v á n v a l ó ; 100 partícióval dolgozva például, az előbbi, 6-7 perces műveletidő n é h á n y másodpercre csökken. Elhamarkodott volna természetesen az a k ö v e t k e z tetés, hogy a partíciók s z á m á t h a t á r t a l a n u l növelni volna célszerű. Ha egy-egy partíció mérete az átlagos a l a k z a t m é r e t alá csökken, egyre t ö b b alakzatot vág nak k é t vagy t ö b b részre a partícióhatárok, és ezzel az alakzatok teljes száma növekedni kezd. A sok par tíció maga is jelentős többletadminisztrációt, t e h á t időt igényel. E z é r t egy h a t á r o n t ú l m á r nem érdemes folytatni a layout felosztását; van egy optimális mértéke a particionálásnak [2]. (Erre vonatkozó kísér leti t a p a s z t a l a t o k r ó l a következő szakaszban szá molunk be.) A particionálás
partíció
H958-1
gyakorlati
kérdései.
A CELLINEX-
programban egy- vagy kétdimenziós, rögzített h a t á r ú , elvágó particionálási t e c h n i k á t alkalmazunk. A par tíciók s z á m á t a felhasználó adhatja meg. Ez mind x, mind y i r á n y b a n maximálisan 16, t e h á t össze sen maximálisan 256 partíció lehet. R ö g z í t e t t ha t á r o n azt értjük, hogy a partícióhatárok helye állandó és független a maszk alakzatainak elhelyezkedésétől. Az „elvágó" particionálás annyit jelent, hogy a par tícióhatárok részekre választják szét azokat az alak zatokat, amelyeket átmetszenek. A particionálás algoritmusát a 2. á b r a segítségével mutatjuk be. A műveletet először a függőleges par tícióhatárokra végezzük el. A lépések a k ö v e t k e z ő k : — mindazon pontokban, ahol poligonél partíció-
1. ábra. A layout particionálása
partició határok
a.,
többlet csúcspontok
b. ,
c,
1H958-2I 2. ábra. A particionálási algoritmus magyarázatához. A többlet csúcspontok párosával azonos helyre esnek, csak a szemléltetés kedvéért ábrázoltuk páronként külön azokat Híradástechnika
XXXV.
évfolyam
1984. 8.
szám
343
1,
i 1
1
1
1>
II
,1
1i
—
•
—
—
—
M —
1 i
a poligon
i
i i
1H958-A partició-határ
1H958-3 3. ábra. H a p a r t í c i ó n b e l ü l v i z s g á l j u k csak az alakzatok é r i n t k e z é s é t , az A-v&\ jelölt kontaktus f e l t á r a t l a n marad
h a t á r t metsz, k é t - k é t t ö b b l e t poligon csúcs pontot veszünk fel (ugyanazon k o o r d i n á t a adatokkal, de egyiket az egyik, m á s i k a t a másik határos partícióhoz t a r t o z ó a n ; 2b ábra), — valamely körüljárási irány szerint pointer láncra fűzzük a poligon csúcspontjait, — megállapítjuk minden egyes partícióhatárra a felvett t ö b b l e t csúcspontok y irányú sorrend jét, — az e sorrendben szomszédos többlet csúcspon tok közül a körüljárás szerint „ h á t s ó k " t o v á b b m u t a t ó pointereit felcseréljük (2c ábra). A vízszintes partícióhatárokra a művelet hasonló m ó d o n végezhető el. A particionálásnál külön gondot okoznak azok az alakzatok, amelyek csúcspontjai, élei éppen partíció h a t á r r a esnek. Ezek kezelése, ha megoldhatatlan prob l é m á t nem is jelent, de a particionáló algoritmust meglehetősen bonyolítja. E n n é l is súlyosabb nehéz ség viszont (ami miatt végül is m á s megoldást kellett v á l a s z t a n u n k ) , hogy ha megengedünk partícióhatárra eső alakzatéleket, akkor az érintkező alakzatok fel t á r á s a nem lesz partíciónként függetlenül kezelhető probléma (lásd a 3. ábra ellenpéldáját). A vázolt gondok elkerülésére a következő megol dást v á l a s z t o t t u k . Az alakzat-koordináták minden esetben eleve egész értékűek (a maszk-leíró nyelvek ugyanis egy k ö t ö t t rácson, „ g r i d - é r t é k e k b e n " teszik lehetővé a k o o r d i n á t á k m e g a d á s á t ) . A C E L L I N E X program belső a d a t á b r á z o l á s á b a n kétszer ilyen sűrű rácsot használ, a maszk minden k o o r d i n á t á j á t t e h á t kettővel szorozzuk. Így az alakzatok csúcspont k o o r d i n á t á i feltétlenül páros számok. Ez u t á n ele gendő a p a r t í c i ó h a t á r o k a t p á r a t l a n koordináta-ér té* E z és minden t o v á b b i f u t á s i d ő adat a M E V F ó t i ú t i t e l e p h e l y é n , a g é p i t e r v e z é s i o s z t á l y o n v é g z e t t futta t á s o k b ó l származik és CPU i d ő b e n é r t e n d ő .
344
4. ábra. A „ p o n t a poligonban van-e" algoritmus ma gyarázatához
kűre venni, s elkerüljük a partícióhatárra eső csúcs pontokkal, élekkel együttjáró gondokat. Rendezési műveletek. Célszerű elvégezni — és a prog ramban meg is tesszük — a particionált alakzatok megfelelő rendezését. A rendezés partíciók szerint tör ténik. Végeredménye a „rendezett, particionált alakzat-file", amelynek minden egyes rekordja egyegy partíció alakzatait, kontaktusablakait tartalmaz za. A partíciónkénti feldolgozás során e file rekordjait olvassuk egy nagy méretű (80 kbyte) bufferbe. Az egy partíciónyi adathalmazon a t o v á b b i műveletek előtt az egyes maszksíkokat összejelölő pointérláncokat hozunk létre. A „pont
a poligonban van-e" algoritmus. Ez az egyik
legfontosabb algoritmusa a programnak. Feladata: megállapítani, hogy egy pont a poligonon belülre (határára) esik-e vagy azon kívül. Az algoritmus je lentősége k e t t ő s . Egyfelől az ablakok közvetítésével létrejövő kontaktusok feltárásának kulcsa. Az ab lakokat a program középpontjukkal veszi számításba: az a k é t poligon érintkezhet egy ablakon át, melyek mindegyikébe beleesik az ablak középpontja. Más felől a poligonok azonosítóval (címkével) való ellá t á s á b a n van szerepe: egy címkeszöveg azon poligonhoz tartozik, ameryre a kezdőpontja esik. Az algoritmus lényegét a 4. á b r á n szemléltetjük. Lépései : — a kérdéses ponton á t képzeletben egy (pl. y irányú) egyenest h ú z u n k , — m e g h a t á r o z z u k ezen egyenes metszéspontjait az alakzat k o n t ú r j á v a l , — ha (y i r á n y b a n értve) p á r a t l a n számú ilyen metszéspont van a kérdéses pont „ a l a t t " , akkor a pont benne van az alakzatban, egyéb k é n t rajta kívül. (Az a l a k z a t h a t á r r a eső pont esetét kezelő külön lé péseket i t t nem részletezzük.) Az 5. á b r á n futásidő s t a t i s z t i k á t mutatunk be a fenti algoritmust realizáló szubrutinról.* A statiszti kából elhagytuk a triviálisan számolható eseteket; ezeknél a gépidő % 50 J J I S . A műveletek
egyszerűsítési
lehetőségei.
A gyorsabb
működés érdekében a program m i n d e n ü t t kihasználja Híradástechnika
XXXV.
évfolyam
1984. 8. szám
A következő lépés: a p á r o n k é n t felfedett érintke zések alapján megkeresni az alakzatok ekvipotenciális csoportjait. Ennek algoritmusa:
CPU idő
1000
— minden alakzathoz egy pointert rendelünk, ami az ekvipotenciális csoport egy k ö v e t k e z ő alak z a t á r a mutat, — e pointerek kezdeti beállítása olyan, hogy mind egyik alakzat ö n m a g á r a mutat ( t e h á t minden csoport egyetlen alakzatból áll), — sorra vesszük az érintkezés-file-on bejegyzett a l a k z a t p á r o s o k a t és minden egyes ilyen páros pointereit felcseréljük. (A többszörös össze köttetéseket, hurkokat t a r t a l m a z ó ekvipoten ciális csoportok miatt i t t még n é h á n y t ö b b l e t lépésre is szükség van; ezeket nem részletezzük.)
-
^
^
• 500
•
A
/
d
< >
*
csucspont-szám —r~ 10
i
15
i
20
25
IH958-5 5. ábra. A „pont a poligonban van-e" algoritmus futás idői azokat a lehetőségeket, amelyek speciális esetekben a számítás egyszerűsítésére adnak m ó d o t vagy t r i v i ális esetekben a számítás teljes mellőzését teszik le hetővé. Ennek érdekében a poligonok belső tárolásá nak része — a poligont befoglaló téglalap négy k o o r d i n á t a adata, — kód, amely azt jelzi, hogy a poligon általános-e vagy valamely speciális, k ö n n y e b b e n kezelhető kategóriához tartozik (téglalap, ortogonális poligon). Megéri, hogy tároljunk-e néhány r e d u n d á n s adatot, mert segítségükkel a számítás sok esetben egyszerű síthető. Például a „ p o n t a poligonban van-e" vagy „ k é t poligon érintkezik-e" típusú döntéseknél elő ször a befoglaló téglalap adatait veszi tekintetbe a program. A negatív döntés (a pont nincs a poligon ban, a k é t poligon nincs érintkezésben) sok esetben m á r ennek alapján meghozható. A poligon kategóriája alapján háromfelé ágazik a t o v á b b i számítás. Tégla lap esetén nincs is szükség t o v á b b i vizsgálatra (hiszen ilyenkor az alakzat azonos a m á r megvizsgált befog laló téglalappal). Ortogonális poligon esetén egysze r ű b b ú t o n folytatódhat a számítás, és csak az álta lános poligon esetén „ v e t i be" a program a ferde oldaléleket is kezelő, s így leghosszadalmasabb al goritmust. Az összeköttetés-felderítés folyamata. A program elő ször partíciónként végigtekinti, hogy mely poligonok k ö z ö t t áll fenn vezető összeköttetés. Ez az ablak közvetítésével létrejövő összeköttetéseknél a „ p o n t a poligonban van-e" algoritmus segítségével t ö r t é n i k , azonos maszk-sík érintkező alakzatainál a „ k é t poli gon érintkezik-e" algoritmussal. Valamennyi felfe dett érintkezést az ú n . érintkezés-file-on jegyzi be a program; e file-on minden ilyen érintkezést k é t - k é t adat, a k é t érintkező poligon sorszáma reprezentálja. Híradástechnika
XXXV.
évfolyam
Mire a fenti eljárást végigvittük, a pointerek az ek vipotenciális alakzatok csoportjait láncolják össze. Az összeköttetés-feltárás t e h á t m e g t ö r t é n t ; ami h á t r a van, az az eredményközlés.
1984. 8.
szám
4. Particionálás és futásidö A program próbaüzeme során kísérleti vizsgálato k a t végeztünk arra v o n a t k o z ó a n , hogy milyen össze függés van hálózatméret és futásidő k ö z ö t t , valamint hogy a particionálás m é r t é k e hogyan befolyásolja a program egyes rész-algoritmusainak időigényét.
CPU idő O] 200
150
100
50
cellaszám 100
1
200
300
1H958-6I 6. ábra. A számítás CPU ideje a cellaszám függvényé ben (a „mérge" művelet nélkül)
345
i 1
I
i
i
t
i
i
i
|
i
i
i
i
T
1°
i
i
r-j
100
t
|
partíció-szám
7. ábra. Az egyes rész-algoritmusok futásideje a partíciószám függvényében
A vizsgált mintahálózat alapeleme egy h á r o m cellából álló áramkörrészlet volt, 24 összeköttetés alakzattal, 7 kontaktusablakkal, 20 alakzatazono sítóval. Ezt sokszoroztuk meg mátrixszerűen, a k ü lönböző méretű layoutok vizsgálatához. Először a teljes CPU időt m é r t ü k különböző nagy ságú hálózatokra, a partíciószámot vagy állandó ér t é k e n tartva vagy a hálózatmérettel a r á n y o s a n nö velve. Az eredményeket a 6. á b r á n mutatjuk be. Rögzített számú partíciónál a v á r a k o z á s n a k meg felelően, nagyjából négyzetesen emelkedik a futás idő a layout mérettel, növekvő számú partíciónál cca lineárisan. A következő vizsgálatunk egy nagyméretű, 300 cellából álló hálózatra vonatkozik. A partíciószámot egyre növelve vizsgáltuk az egyes rész-algoritmusok futásidejét. Az eredményeket a 7. á b r á n közöljük. L á t h a t ó , hogy a címke-hozzárendelés és az érintke zések feltárása a partíciószám növelésével monoton csökkenő időt igényel. E z t részben lerontja m a g á n a k a particionálásnak a növekvő időfelhasználása. Az összidőnek l á t h a t ó a n minimuma, optimuma van a 100 körüli partíciószámnál. Megjegyzendő, hogy az sem lényegtelen, hogy egy adott partíciószám hogyan oszlik meg az x és az y irányú particionálás között. A legjobb e r e d m é n y t akkor é r t ü k el, ha a k é t i r á n y b a n cca egyforma szá m ú partíciót alkalmaztunk (egybehangzóan a kér désre vonatkozó elméleti vizsgálatokkal [3]).
346
5. Az eredmények dokumentálása A visszafejtés eredményei igen változatos formában használhatók fel a layout ellenőrzésére. A C E L L I N E X program eredményközlési lehetőségeivel igyekszik t á m o g a t n i minden szóba jövő ellenőrzési módszert. Hibajelzések,
figyelmeztető
üzenetek.
A visszafejtés
során feltárásra kerülhetnek a layout olyan vonásai, amelyek feltétlenül tervezési hibára utalnak. Ezekről a program hibajelzést nyomtat. Más esetben csak valószínűsíthető a hiba jelenléte — ezekből képződ nek a figyelmeztető üzenetek. Tipikus, a program által jelzett rendellenességek az alábbiak: — — — — —
kihasználatlan ablak, bekötetlen cellakivezetés, hurkot t a r t a l m a z ó ekvipotenciális vezeték, zárlatok (tápfeszültség, cellakimenet stb.), funkcionális rendellenesség a cellák összeköté sében (nem csatlakozik cellabemenet egy jel vezetékhez, t ö b b , nem háromállapotú kimenet össze van kötve stb.), — rendeltetés nélküli részletek a layout-on (ve zeték, amely csak egy cellához csatlakozik vagy egyhez sem). Listázás
a cellák szerint. A n y o m t a t á s i k é p e t a 8. á b
ra mutatja, egyetlen cellára vonatkozóan. A program kilistázza a cella kivezetéseit, címkéjükkel és a funkciójukra utaló k a r a k t e r k ó d d a l (INP, OUT stb.) Híradástechnika
XXXV.
évfolyam
1984. 8. szám
CELL
DESIGN
CELL
«0.-
FILE
NAME=klANÍ2
\ ,
KO. "
1. 2. 3. 4. 5. 6.
N»*E=
,
CELL TYPE
— a kiinduló cellát, — a felderítés mélységét (hogy t e h á t az cellán á t történjen meg).
LISTING
CELL1
RELATEO
INTERCONNECTIONS™
NODES IDENTIFIER
I I
A d o k u m e n t á l ó szegmens megkeresi a kiinduló cella kimeneteit, az azokhoz b e m e n e t ü k k e l csatlakozó t o v á b b i cellákat, ez u t ó b b i a k kimeneteit . . . stb., a k í v á n t mélységig. A jelfolyam felderítés e r e d m é n y é t a program a 10. á b r á n l á h a t ó , szemléletes formában közli. A műveletet nem csak a jelterjedés i r á n y á b a n , hanem azzal ellentétesen, visszafelé is kérhetjük.
INTERCONNECTION IOENTIFIER NO.
INP*
BEI
I
1.
IhP* OUT* UGGUDDGI1D7
SE2 OUTP TAPF TAPF FOLD
I I I I I
2. 3. 15. 16. 17.
LAAB MÁSODIK ELSŐ B E K
-
—
-
-
Grafikus-interaktív
8. ábra. A cellák szerinti eredményközlés részlete
INTERCONNECTIC;
FILE
NO.»
1
NAflE-
CELL1
IDENTIfIES^LAAB
»
ALIAS*HASODIK C E L L NO. NAPÉ 1. 2.
hAND2 WN0S2
«»«»
ERROR
*»«»
***•
WARNING
****
I I
NO.
I I
1. 2.
.
CONNECTED N C D E TYPE
CELLS-
IDENTIFIER
INP* INP*
BE1 BE2
NO O U T P U T S OR F I X E D L E V E L S A RE C O N N E C T E D TO T H I S T R E E HJLTIPLE IDENTIFIER
jelfolyam-felderítés.
(SUFPLY*GND)
Logikai hálózatleírás
9. ábra. Az összeköttetések eredményközlés részlete
az összeköttetések
(jelvezetékek) szerinti
szerint. A 9. á b r á n l á t j u k
ennek egy összeköttetésre vonatkozó részét. Tulaj donképpen az előbbi lista megfordításáról van s z ó : most azt listázzuk, hogy az egyes összeköttetések hez mely cellák, mely kivezetésükkel csatlakoznak. Jelfolyam-felderítés. A felhasználónak lehetősége van arra, hogy egy logikai jel ú t j á t nyomon kövesse az egymáshoz kapcsolódó cellákon át. Ehhez meg kell adnia , C E L L
1 - J J L - 8 3
INTERCOHNECT10N
S1GNAL-FL0W
PRINTCUT
COCE-
DESI6N
F I L E =
L I R " C K
0N -
-(
EXTRACTION
fATH
1 ÓT
A program jelenleg
— összevethető a felhasználó által megadottal, — ellenőrző logikai szimulációnak v e t h e t ő alá. Layout-statisztikák
készítése.
Nem
közvetlenül
a
visszafejtéshez t a r t o z ó , de hasznos szolgáltatása a programnak, hogy a layout lényeges statisztikai jel lemzőit közli. Ilyenek: 5
PROGRAM
CELL SEPTH=
F C R * A R C>
5
STAGc
1111=
CELL
IMPUT
(OCÖŰ)
0C0C-
CELL
OUTPUT
(
AAAAAA=
MHtP.Í
I I I 1)2JZ/AAAAAA
C t L l
generálása.
DlSCOVERING
222=
( O C C O ) — I N I T I A L
előbbi
a L O B S T E R logikai szimulációs program [6] beme neti nyelvén állítja elő a layout által képviselt hálózat logikai leírását, a cellák belső logikai leírását a CELLIB-program [4] által szervezett cellakönyvtár ból emelve k i . (A későbbiekben valószínűleg a M E V most kialakítás alatt álló integrált tervezőrendsze rének E T A L O N egységes topológiai leírónyelvére t é r ü n k i t t át.) A logikai leírás
ellátva kiírja, hogy az illető cellakivezetés h á n y a s sorszámú és milyen azonosítójú összeköttetéshez csat lakozik. Listázás
Az
m ű v e l e t grafikus display képernyőn is végezhető. Az ernyőn megjelenik a layout vagy annak kiválasz t o t t részlete, de kizárólag a cellák körvonalainak á b rázolásával. Ha kijelölünk egy cellát és kérjük a jel folyam-felderítést, kirajzolódnak mindazon összeköt tetés-alakzatok, amelyek az illető cella kimeneteihez kapcsolódnak és vonalkázás emeli k i a bemenetekkel csatlakozó t o v á b b i cellákat (11. ábra). A művelet ismétlésével tetszőleges jel-út nyomon k ö v e t h e t ő . M i n t az előbb, i t t is haladhatunk a jelterjedéssel ellen tétes i r á n y b a n is.
I N T E R C O N N E C T I O N L I S T ING
DESIGN
hány
0 - f T H
2!v0
CFLL CELL
NCOE
LA3EL LA8EL
NO. 3RD
Dé'TH
NOD E
NAKE
DEPTh
4TH
DEPTH
STH
DEPTH
1/WAND2 COUTP)
(BE2
)
3 / W « R 2 (OUTF)
C?E1
>
I
20/WNOF2 COUTP)
(9E1
)
21/1.10R2 (OL'TP)
I I
I
4.
I
I
)
33/WN0R2
)
37/WAND2
COUTP)
COUTP)
I
(3E1
)
39/WN0R2
(BE2
)
39/WNOR2
C3E1
)
39/WNCR2
)
39/UN0R2
I Í6E2
)
19/UA.ND2 COUTP)
CíU2
)
21/WN0S2 (OLTP)
ÍBE1
)
3S/WN0R2
CBE2
)
37/JAND2
1
COUTP)
I'
10. ábra. A jelfolyam-felderítés eredményközlése sor nyomtatón Híradástechnika
XXXV.
évfolyam
1984. 8.
szám
(CUTP)
C3É2
fH95tPÍÖl
347
11. ábra. Jelfolyam-felderítés a grafikus k é p e r n y ő n — alakzatok, ablakok, a z o n o s í t ó k , j e l v e z e t é k e k száma, — cellák és cellafajták száma, — alakzatok á t l a g o s és m a x i m á l i s c s ú c s p o n t s z á m a , x és y i r á n y ú á t l a g o s és m a x i m á l i s m é r e t e , — alakzatok m e g o s z l á s a a p a r t í c i ó k k ö z ö t t stb.
6. Felhasználás, továbbfejlesztés A CELLINEX-program 1983 j ú l i u s á b a n k e r ü l t hasz n á l a t b a a Mikroelektronikai Vállalatnál. Rendelte tése a cellás tervezésű berendezésorientált á r a m k ö r ö k l a y o u t j á n a k ellenőrzése. A h a s z n á l a t i tapasztalatok ról korai ma m é g szólni; ezekre 1-2 év u t á n érde mes majd visszatérni. A továbbfejlesztés lehetőségei közül k e t t ő t l á t u n k m á r ma meglehetősen világosan. Ezek: — A program „feldeklarálása" nagyobb h á l ó z a t m é r e t r e . A programkészítés és az eddig v é g z e t t f u t t a t á s o k tapasztalatai a l a p j á n n y i l v á n v a l ó , hogy a program nagyobb nehézségek nélkül alkalmassá t e h e t ő a 400-nál t ö b b cellát t a r t a l m a z ó layout-ok vizsgálatára — előre l á t h a t ó a n k b . 1000 celláig.
348
— A parazita k a p a c i t á s o k s z á m í t á s a . A program c s e k é l y k i e g é s z í t é s s e l alkalmas lesz arra, hogy az ö s s z e k ö t t e t é s e k á l t a l k é p v i s e l t s z ó r t kapa c i t á s t s z á m o l n i t u d j a . E z igen l é n y e g e s lehet a pontosabb logikai s z i m u l á c i ó , az i d ő z í t é s e k pontos e l l e n ő r z é s e s z e m p o n t j á b ó l . V á r h a t ó t e r m é s z e t e s e n , hogy a h a s z n á l a t i tapaszta latok m é g e g y é b t o v á b b f e j l e s z t é s i i g é n y e k e t is fel vetnek m a j d . I R O D A L O M [1] Dr. Székely V., Baji P., dr. Rencz M., dr. Koltai M.: I C maszkok gépi t e r v e z é s e , t a n u l m á n y , B M E Elektronikus E s z k ö z ö k T a n s z é k e , 1981. [2] Baird: F a s t algorithms f or L S I artwork analysis, I E E E D A T C 1977, pp. 3 0 3 - 3 1 1 . [3] Farkas G.: I n t e g r á l t áramkörök h e l y e t t e s í t ő k é p é nek m e g h a t á r o z á s a a t o p o l ó g i a i elrendezés alapján, s z a k m é r n ö k i diplomaterv, B M E 1980. [4] Dr. Székely V., Baji P., Kerecsenné dr. Rencz M., Kónya I., dr. Masszi F.: CELLIB — cellakönyvtár kezelő program a mikroelektronikai tervezés céljá ra, H í r a d á s t e c h n i k a , 1983. nov. [5] C E L L I N E X cellaszintű l a y o u t - v i s s z a f e j t ő prog ram, h a s z n á l a t i u t a s í t á s , Budapest, 1983. [6] Jávor A., Benkő T-né: L O B S T E R programrendszer felhasználói leírás, K F K I k i a d v á n y .
Híradástechnika
XXXV.
évfolyam
1984. 8. szám