Plagiatteza Cap2 [631162]

2. ANALIZA SITUA ȚIEI ACTUALE ÎN DOMENIUL
CIRCUITELOR VLSI ȘI FPGA
2.1 Introducere
În acest capitol se prezintã în mod sintetic situaøia actualã în domeniul cir-
cuitelor VLSI ši FPGA ši al proiectãrii acestor circuite. În secøiunea 2.2 se descriuetapele de proiectare ale circuitelor VLSI în general, pentru a scoate în evidenøã loculetapei de proiectare fizicã în cadrul procesului de proiectare, etapele proiectãrii fizicereprezentând subiectul principal al tezei. Deoarece metodele de proiectare sunt elabo-rate în general pentru un anumit tip de circuit VLSI, în secøiunea 2.3 se prezintã prin-cipalele tipuri de circuite VLSI: reøele de porøi, celule standard, macro-celule, circuiteFPGA. Implementãrile ši experimentãrile au fost efectuate pentru circuite FPGA, ši dinacest motiv în secøiunea 2.4 se trec în revistã unele circuite FPGA comerciale, cuscopul de a dispune de un punct de referinøã pentru modelul de circuit utilizat în cad-rul tezei, în special pentru arhitectura de rutare a acestui circuit. În secøiunea 2.5 sepun în evidenøã dificultãøile care apar în cadrul etapelor de proiectare fizicã. Concluzii-le sunt prezentate în secøiunea 2.6.
2.2 Procesul de proiectare al circuitelor VLSI
Deoarece complexitatea circuitelor VLSI este de ordinul milioanelor de tran-
zistoare, proiectarea unui circuit VLSI este o sarcinã complexã. Pentru a reduce com-plexitatea procesului de proiectare, se introduc mai multe nivele de abstractizare. Pemãsurã ce procesul avanseazã de la nivelele superioare la cele inferioare de abstracti-zare, se introduc din ce în ce mai multe detalii despre noul proiect. Nivelele tipice deabstractizare ši etapele de proiectare corespunzãtoare sunt ilustrate în Figura 2.1. Dupãcum se indicã în aceastã figurã, proiectul trece de la etapa de specificaøie la cea defabricaøie cu ajutorul diferitelor utilitare CAD.
2.2.1 Proiectarea arhitectural ă
Iniøial, proiectantul utilizeazã module de circuit ca unitãøi aritmetice, unitãøi de
memorie, reøele de interconectare, controlere. Proiectarea unui circuit la acest nivel deabstractizare este numitã proiectare arhitecturalã . Deciziile luate în aceastã etapã
afecteazã în mod semnificativ costul ši performanøele proiectului. De exemplu, uneledecizii care trebuie luate în timpul proiectãrii arhitecturale a unui microprocesor sereferã la: setul de instrucøiuni al procesorului, modul de adresare, utilizarea supra-punerii execuøiei instrucøiunilor, utilizarea unei memorii cache interne ši dimensiuneaacesteia, utilizarea unei unitãøi aritmetice seriale sau paralele, interfaøarea procesoruluicu exteriorul.

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 8
Deši proiectarea arhitecturalã nu poate fi realizatã în întregime prin programe,
aceste programe pot ajuta proiectantul pentru a lua unele decizii importante. De ex-emplu, proiectantul poate determina un parametru (ca dimensiunea memoriei cache)prin simulare.
Dupã definirea arhitecturii sistemului, este necesarã execuøia urmãtoarelor
etape:
1. Proiectarea logicã detaliatã a modulelor de circuit;
2. Determinarea semnalelor de control necesare pentru activarea ši dezactivarea
modulelor de circuit.
Prima etapã este numitã proiectarea cãii de date , iar etapa a doua proiectarea
cãii de control . Calea de date a unui circuit cuprinde diferite blocuri funcøionale, ele-
mente de memorare ši componente hardware care permit transferul datelor între blo-curile funcøionale ši elementele de memorare. Transferul datelor se realizeazã prinintermediul magistralelor sau a unei combinaøii de multiplexoare ši demultiplexoare.
Calea de control a unui circuit genereazã diferitele semnale de control necesare
pentru funcøionarea circuitului. Aceste semnale de control iniøializeazã elementele dememorare ale circuitului, iniøiazã transferurile de date între blocurile funcøionale šielementele de memorare, etc. Calea de control poate fi implementatã utilizând controlcablat sau control microprogramat.
În cazul implementãrii unui circuit, diferitele variante posibile constituie spaøiul
de proiectare (la nivelul respectiv de abstractizare). Fiecare metodã de implementare
constituie un punct în spaøiul de proiectare. Existã avantaje ši dezavantaje asociate cufiecare din aceste puncte. Atunci când se încearcã optimizarea costului componentelorhardware, de obicei se reduc performanøele, ši invers. Existã diferite consideraøii deproiectare de care trebuie sã se øinã cont, ca de exemplu: costul, performanøele, testa-bilitatea, puterea disipatã, toleranøa la erori, simplitatea proiectãrii, simplitatea modifi-cãrii proiectului. O specificaøie a unui circuit poate conøine anumite constrângeri
asupra unor aspecte ale proiectului.
Fiind datã o specificaøie, obiectivul este de a se ajunge la un proiect care satis-
face toate constrângerile impuse de specificaøie, ši optimizeazã unul sau mai multe as-pecte ale proiectului. Aceastã problemã este numitã ši sintezã hardware . Pentru sin-
teza cãii de date ši a cãii de control au fost elaborate diferite programe de proiectareasistatã de calculator. Generarea automatã a cãii de date ši a cãii de control este nu-mitã sintezã de nivel înalt [79] [80] [121] [122].
Figura 2.1. Nivele de abstractizare ši etapele corespunzãtoare de proiectare.

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 9
2.2.2 Proiectarea logic ă
Cãile de date ši de control vor avea componente ca unitãøi aritmetice ši logice,
registre de deplasare, multiplexoare, buffere etc. Etapele ulterioare de proiectare de-pind de modul de implementare, sub forma unui circuit VLSI de tip ASIC sau prin cir-cuite FPGA.
Dacã implementarea trebuie realizatã sub forma unui circuit VLSI utilizând
componente aflate într-o bibliotecã de module (aceste module fiind numite ši macro-
celule ), urmãtoarea etapã de proiectare este selectarea componentelor astfel încât sã se
minimizeze costul total ši în acelaši timp sã se maximizeze performanøele. Dupã pro-cedura de selecøie, componentele (celulele) sunt amplasate pe suprafaøa de rutare šisunt interconectate utilizând conexiuni de metal ši polisiliciu.
Dacã implementarea trebuie realizatã utilizând unul sau mai multe circuite
FPGA, operaøiile efectuate în cadrul proiectãrii logice constau în principal din par-
tiøionare ši mapare tehnologicã . În cadrul partiøionãrii, proiectul este divizat în mai
multe pãrøi astfel încât sã fie posibilã implementarea fiecãreia într-un circuit FPGA. Încadrul mapãrii tehnologice, pentru fiecare parte care va fi implementatã într-un singurcircuit FPGA, logica este divizatã în mai multe fragmente suficient de mici pentru a fiimplementate într-un singur bloc logic al circuitului.
2.2.3 Proiectarea fizic ă
Proiectarea fizicã a unui circuit este etapa care precede fabricaøia acestuia. În
modul cel mai general, proiectarea fizicã se referã la toate etapele de proiectare careurmeazã dupã proiectarea logicã ši care preced fabricaøia. Acestea cuprind toate sau oparte din urmãtoarele etape: partiøionare logicã, plasare ši rutare. Performanøele cir-cuitului, din punct de vedere al spaøiului ocupat, al vitezei ši al fiabilitãøii, depind înmod critic de modul în care se realizeazã proiectarea fizicã. Ca exemplu, se considerãmai întâi efectul plasãrii ši rutãrii asupra performanøelor de vitezã ale circuitului.Într-un circuit integrat, interconexiunile de metal ši polisiliciu introduc impedanøe,ceea ce poate afecta viteza circuitului. În cazul în care se utilizeazã mai multe straturimetalice, existã o altã sursã de impedanøã. Dacã o conexiune este implementatãutilizând douã straturi metalice, se utilizeazã un orificiu de trecere în punctul de tre-cere între cele douã straturi. În mod similar, dacã o conexiune este implementatã pa-røial prin metal ši parøial prin polisiliciu, este necesar un contact pentru realizareatrecerii între straturi. Contactele ši orificiile de trecere introduc o impedanøã de o va-loare semnificativã, contribuind în plus la reducerea vitezei circuitului.
Plasarea ši rutarea afecteazã în mod semnificativ suprafaøa ocupatã de circuit.
Existã douã componente ale suprafeøei circuitului: suprafaøa funcøionalã ši cea de in-terconectare. Suprafaøa ocupatã de elementele active reprezintã suprafaøa funcøionalã.Interconexiunile utilizate pentru conectarea acestor elemente funcøionale contribuie lasuprafaøa de interconectare. Interconexiunile lungi ši orificiile de trecere afecteazã nunumai performanøele, ci ši suprafaøa circuitului.
Suprafaøa unui circuit influenøeazã în mod direct randamentul procesului de
fabricaøie. Acest randament este definit prin numãrul de circuite fãrã defecte dintr-unlot de circuite fabricate. Cu cât suprafaøa circuitului este mai mare, cu atât randamentulva fi mai redus. Un randament redus va determina un cost de producøie ridicat.
Fiabilitatea circuitului este de asemenea influenøatã de operaøiile efectuate în
cadrul proiectãrii fizice. De exemplu, orificiile de trecere reprezintã surse de reducerea fiabilitãøii. Lãøimea unei conexiuni metalice trebuie aleasã în mod corespunzãtorpentru a se evita migrarea metalului din cauza densitãøii excesive a curentului.

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 10
2.3 Tipuri de circuite VLSI
În aceastã secøiune se descriu principalele tipuri de circuite VLSI, în funcøie de
metodele utilizate pentru generarea reprezentãrilor fizice ale circuitelor. Aceste metodediferã în principal prin restricøiile structurale pe care le impun asupra elementelor decircuit ši asupra suprafeøei de plasare.
2.3.1 Rețele de por ți
O reøea de porøi constã dintr-un numãr mare de tranzistoare care sunt prefabri-
cate sub forma unui tablou bidimensional. Iniøial tranzistoarele dintr-o reøea nu suntconectate între ele. Pentru implementarea unui circuit printr-o reøea de porøi, trebuieplasate conexiuni metalice între tranzistoare utilizând procesul obišnuit de mascare.Acest proces de adãugare a conexiunilor metalice la o reøea de porøi este numit par-ticularizare a reøelei. Dupã acest proces, reøelele individuale de porøi pot fi separate,împachetate ši testate.
Deoarece toate etapele cu excepøia particularizãrii sunt identice pentru toate
reøelele de porøi, indiferent de circuitul care va fi implementat, se poate stoca un nu-mãr mare de circuite care au fost prefabricate pânã la procesul de metalizare. Astfel, vafi necesar un timp foarte redus pânã la fabricarea circuitului final. Reøelele de porøisunt numite ši reøele de porøi programabile prin mãšti ( Mask Programmable
Gate-Array – MPGA ). Costul producerii unui circuit cu o reøea de porøi este redus dato-
ritã randamentului ridicat. Aceasta deoarece existã un numãr redus de etape de prelu-crare implicate într-o particularizare, fiind necesare numai patru etape de mascare, câteuna pentru cele douã straturi metalice ši cele douã straturi de contact.
Particularizarea implicã douã tipuri de interconexiuni, în interiorul celulelor ši
între celule. O celulã este un modul de circuit, de exemplu o poartã ŠI-NU cu douãintrãri, care poate fi implementatã prin conectarea unui grup de tranzistoare dintr-ovecinãtate localã a reøelei de porøi. Pentru implementare se poate pãstra o bibliotecãde celule, în care este memorat modelul de interconectare pentru fiecare celulã. Astfel,interconexiunile din interiorul celulelor sunt de asemenea independente de circuitulcare va fi implementat prin reøeaua de porøi. Interconexiunile între celule sunt speci-fice circuitului ši sunt gestionate de programul de rutare. O reøea de porøi tipicã par-ticularizatã ca o poartã ŠI-NU cu douã intrãri este indicatã în Figura 2.2.
Pentru ca interconexiunile între celule sã poatã fi realizate într-un mod siste-
matic, reøeaua de porøi este structuratã ca o reøea regulatã de celule de bazã (Figura2.3). Fiecare dreptunghi din figurã reprezintã o celulã ši cuprinde un grup de tranzis-toare. Interconexiunile între celule sunt realizate în regiunile numite canale . Zona în
care un canal orizontal intersecteazã un canal vertical reprezintã un bloc de comutare .
În fiecare canal orizontal (vertical) poate fi plasat un numãr fix de interconexiuni ori-
Figura 2.2. (a) Exemplu de celulã de bazã într-o reøea de porøi.
(b) Celulã particularizatã ca o poartã ŠI-NU cu douã intrãri.

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 11
zontale (verticale). Acest numãr reprezintã densitatea pistelor orizontale (verticale) ale
canalului.
Datoritã spaøiului limitat rezervat pentru interconexiuni, proiectarea fizicã a
reøelelor de porøi este dificilã. Dacã programul de plasare încearcã sã evite intercone-xiunile lungi prin plasarea apropiatã a celulelor puternic conectate, congestia localãpoate determina ca circuitul sã nu poatã fi rutat. Deoarece toate celulele au aceleašidimensiuni (lãøime ši înãløime), celulele din bibliotecã trebuie proiectate în mod spe-cial pentru a satisface aceastã cerinøã.
Un caz special al arhitecturii cu reøele de porøi este cel în care canalele de ru-
tare sunt foarte înguste, sau virtual absente. Circuitul constã deci dintr-o reøea de tran-zistoare foarte apropiate. Deoarece canalele sunt foarte înguste, ele nu pot fi utilizatepentru rutare. Conexiunile trebuie rutate de aceea peste tranzistoare. Aceastã rutareeste numitã uneori rutare peste celule . Arhitectura este numitã reøea de porøi fãrã ca-
nale.
2.3.2 Celule standard
O celulã standard, numitã ši policelulã, este un bloc logic care executã o fun-
cøie standard. Exemple de celule standard sunt poarta ŠI-NU cu douã intrãri, poartaSAU cu douã intrãri, bistabilul D, multiplexorul cu douã intrãri etc. O bibliotecã decelule este o colecøie de informaøii legate de celulele standard. Informaøiile relevantedespre o celulã constau din numele celulei, funcøionalitatea acestuia, aranjarea pinilor,
ši amplasarea celulei pentru o anumitã tehnologie, de exemplu CMOS de 2 µm. Ce-
lulele dintr-o anumitã bibliotecã au aceeaši înãløime.
Proiectarea cu celule standard este similarã celei cu componente SSI ši MSI, cu
excepøia detaliilor de implementare. Componentele sunt selectate din biblioteca decomponente. Avantajul utilizãrii unei biblioteci de componente constã în faptul cãproiectele pot fi terminate într-un timp redus. Programele de proiectare fizicã trebuiesã realizeze doar plasarea fiecãrei celule ši interconectarea acestora. Plasarea ši rutareasunt simplificate prin utilizarea unui plan de amplasare simplificat (Figura 2.4).
Suprafaøa de amplasare este împãrøitã în mai multe rânduri. Un rând constã din
celule plasate aproape unele de altele. Rândurile sunt separate prin canale de rutareorizontale. Celulele din acelaši rând, sau cele din douã rânduri alãturate pot fi inter-conectate prin intermediul canalului adiacent. Dacã trebuie conectate douã celuleaflate în rânduri non-adiacente, se utilizeazã celule de tip special, numite celule de tre-
cere. În Figura 2.4, celula A din rândul 1 este conectatã cu celula B din rândul 3. Se
utilizeazã o celulã de trecere plasatã în rândul 2. O celulã de trecere constã doar dinuna sau mai multe conexiuni verticale.
Figura 2.3. Organizarea unei reøele de porøi.

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 12
Faøã de reøelele de porøi, celulele standard oferã o flexibilitate mai mare. În ca-
zul unui circuit cu celule standard, spaøiul de interconectare nu este fixat dinainte. Maimult, celulele pot avea lãøimi diferite. Dezavantajul celulelor standard faøã de reøelelede porøi constã în faptul cã pentru fabricaøia circuitului sunt necesare toate etapele defabricaøie.
2.3.3 Macro-celule
Atât proiectarea cu reøele de porøi cât ši cea cu celule standard impun restricøii
asupra celulelor care sunt utilizate. De exemplu, celulele standard trebuie sã aibãaceeaši înãløime. Dacã aceastã restricøie este eliminatã, celulele nu mai pot fi plasate perânduri. Chiar în cazul în care se forøeazã un amplasament pe rânduri, ca în Figura2.5(a), acesta ar fi ineficient din punct de vedere al suprafeøei ocupate. În Figura2.5(b), acelaši set de celule este aranjat mult mai compact. Circuitele la care pot variaambele dimensiuni ale celulelor sunt numite circuite cu macro-celule sau blocuri con-
structive . Avantajul principal al acestora este cã biblioteca poate conøine celule de o
complexitate mult mai mare, de exemplu registre, unitãøi aritmetice ši logice, memoriiši alte blocuri arhitecturale.
Existã un avantaj important al memorãrii unor blocuri ca unitãøi aritmetice ši
logice într-o bibliotecã de celule. Asemenea blocuri pot fi proiectate astfel încât sã aibãcaracteristici de amplasare eficiente. De exemplu, un circuit de înmuløire de 8 biøi areo structurã regulatã, ceea ce permite o amplasare eficientã. Dacã acelaši circuit trebuieproiectat utilizând celule simple ca de exemplu porøile logice, nu se cunoašte modulîn care vor fi aranjate celulele în final. Dacã se dorešte menøinerea topologiei circuitu-
Figura 2.4. Planul de amplasare al unui circuit cu celule
standard.
Figura 2.5. (a) Celule cu înãløime ši lãøime variatã într-o
amplasare bazatã pe linii. (b) O amplasare mai compactã
pentru acelaši circuit.

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 13
lui de înmuløire, singura soluøie este pãstrarea acesteia sub forma unui bloc construc-
tiv.
Amplasarea automatã pentru circuitele cu macro-celule este mult mai dificilã
decât pentru tipurile de circuite amintite anterior. Aceasta deoarece nu existã un plande amplasare standard, ši ca urmare nici canalele de rutare nu sunt predefinite. Am-plasarea ši definirea canalelor sunt etape suplimentare necesare pentru aceste circuite.
Conceptul de memorare a celulelor într-o bibliotecã poate reduce în mod sem-
nificativ efortul de proiectare. Existã însã un dezavantaj al acestei metode. O bibliotecãde celule este dependentã de tehnologia de fabricaøie, deci sunt necesare bibliotecidiferite pentru diferitele tehnologii. În cazul trecerii la o nouã tehnologie, de exemplu
de la CMOS de 2 µm la CMOS de 1.5 µm, este necesar un efort considerabil pentru
reproiectarea celulelor.
O altã metodã este utilizarea unui generator de module care poate compila
specificaøia unei celule într-o realizare a acesteia. Specificaøia poate fi o descriere fun-
cøionalã , ca de exemplu un tabel de adevãr sau un limbaj de descriere hardware, sau
o descriere structuralã , ca de exemplu o listã de conexiuni. Caracteristicile cerute ale
implementãrii, ca de exemplu înãløimea celulei, pot fi specificate pentru generatorul demodule.
2.3.4 Circuite FPGA
Similar unui circuit MPGA, un circuit FPGA ( Field Programmable Gate Array )
constã dintr-o reøea bidimensionalã de blocuri logice. De obicei, fiecare bloc logic po-ate fi programat pentru a implementa orice funcøie logicã a intrãrilor sale. De aceea,aceste blocuri sunt numite de obicei blocuri logice configurabile ( Configurable Logic
Block – CLB). Canalele ši blocurile de comutare dintre aceste blocuri conøin resurse de
interconectare, dupã cum se ilustreazã în Figura 2.6. Aceste resurse conøin de obiceisegmente de interconectare de diferite lungimi. Interconexiunile conøin comutatoareprogramabile cu rolul de a conecta blocurile logice la segmentele de interconectare,sau un segment de interconectare la altul. În plus, existã celule de I/E la periferiareøelei, care pot fi programate ca intrãri sau ieširi.
Principalele etape de proiectare atunci când se utilizeazã circuite FPGA pentru
implementarea circuitelor digitale sunt:
Figura 2.6. Structura unui circuit FPGA tipic.

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 14
1) Maparea descrierii logice iniøiale a circuitului într-o listã de conexiuni între blo-
curile CLB (mapare tehnologicã);
2) Asignarea fiecãrui bloc CLB din lista de conexiuni a unui bloc CLB din reøea
(plasare);
3) Interconectarea blocurilor CLB din reøea (rutare);
4) Generarea širului de biøi pentru configurarea blocurilor CLB conform funcøiei
asignate ši a interconexiunilor conform rutãrii.
Circuitele FPGA au fost introduse în anul 1985 de compania Xilinx. De atunci
au fost elaborate diferite tipuri de circuite FPGA de un numãr de alte companii ca Ac-tel, Altera, Atmel, Texas Instruments etc. Existã diferite aspecte de proiectare a cir-cuitelor FPGA. Aceste aspecte includ granularitatea ši flexibilitatea blocurilor logice šia resurselor de interconectare.
Blocurile logice pot fi module cu granularitate finã ca de exemplu porøi ŠI-NU
cu douã intrãri, sau structuri complexe ca multiplexoare, reøele programabile de porøi(PAL) etc. Cele mai multe blocuri logice FPGA conøin unul sau douã bistabile carepermit implementarea circuitelor secvenøiale.
Structura ši conøinutul resurselor de interconectare a unui circuit FPGA reprez-
intã arhitectura de rutare a circuitului. Aceastã arhitecturã constã din segmente de in-
terconectare ši comutatoare programabile. Aceste comutatoare sunt realizate utilizândtranzistoare de trecere (controlate prin celule RAM statice), anti-fuzibile, sau tranzisto-are EPROM/EEPROM. Similar cu blocurile logice, complexitatea arhitecturii de rutarepoate varia de la conexiuni simple între blocuri pânã la structuri de interconectare maicomplexe.
Avantajele circuitelor FPGA faøã de circuitele MPGA sunt costurile de prototipi-
zare mai reduse ši durata mai scurtã de producøie. Principalele dezavantaje sunt vitezade operare mai redusã ši densitatea mai redusã a porøilor. Comutatoarele programabileši circuitele de programare asociate necesitã un spaøiu mai mare în cadrul circuituluicomparativ cu conexiunile metalice din reøelele de porøi. Aceste comutatoare au deasemenea o rezistenøã ši capacitate semnificativã care determinã o vitezã redusã deoperare.
2.4 Tipuri de circuite FPGA
Existã douã categorii principale de circuite FPGA: circuite cu memorii SRAM ši
circuite cu antifuzibile.
Circuite cu memorii SRAM. Programarea acestor circuite se realizeazã prin
celule de memorie staticã. Logica este implementatã cu ajutorul unor tabele (lookuptable) realizate din celulele de memorie, intrãrile funcøiilor controlând liniile de adresã.Fiecare tabelã de 2
n celule de memorie implementeazã orice funcøie cu n intrãri. Una
sau mai multe tabele, combinate cu bistabile, formeazã un bloc logic configurabil. Ac-este blocuri sunt aranjate într-un tablou bidimensional, segmentele de interconectareformând canale, similar cu reøelele de porøi. Segmentele se conecteazã la pinii blocu-rile logice din canale ši la alte segmente din blocurile de comutare prin intermediultranzistoarelor de trecere controlate de celule ale memoriei de configurare.
Un program de configurare pentru circuitele cu memorii SRAM constã dintr-un
singur cuvânt lung de programare. Logica din circuit încarcã cuvântul de programare,pe care îl citešte serial dintr-o memorie externã de fiecare datã când circuitul este ali-mentat. Biøii acestui cuvânt seteazã valorile tuturor celulelor memoriei de configuraredin circuit, setând astfel valorile tabelelor ši selectând segmentele care se vor conecta

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 15
între ele. Circuitele cu memorii SRAM sunt reprogramabile. Ele pot fi actualizate în
sistem, punând la dispoziøia proiectanøilor noi opøiuni ši posibilitãøi de proiectare.
Din aceastã categorie de circuite FPGA fac parte cele ale firmelor Xilinx, Altera,
AT&T.
Circuite cu antifuzibile. Un antifuzibil este un dispozitiv cu douã terminale
care în mod normal se aflã în starea de înaltã impedanøã, iar atunci când este expus la
o tensiune ridicatã, trece în starea cu rezistenøã redusã (300-500 Ω). Antifuzibilele au
dimensiuni reduse, astfel încât o arhitecturã bazatã pe antifuzibile poate conøine sutede mii sau milioane de antifuzibile. Pentru simplificarea arhitecturii ši a programãrii,circuitele FPGA bazate pe antifuzibile constau de obicei din rânduri de elementelogice configurabile cu canale de interconectare între ele, ca ši reøelele de porøitradiøionale. Un bloc logic poate fi programat prin conectarea pinilor sãi de intrare lavalori fixe sau la reøele de interconectare. Existã antifuzibile la fiecare punct deintersecøie între interconexiuni ši pini din canal ši la toate punctele de intersecøie întreinterconexiuni în locurile în care canalele se intersecteazã.
Din categoria circuitelor FPGA cu antifuzibile fac parte circuitele firmelor Actel,
Quicklogic, Cypress.
În continuarea acestei secøiuni se descriu unele familii de circuite FPGA comer-
ciale. Tipurile prezentate au fost alese deoarece ele sunt exemple reprezentative dedispozitive ši deoarece sunt larg rãspândite. Pentru fiecare dispozitiv se descrie arhi-tectura generalã ši arhitectura de rutare, indicându-se pentru unele cazuri modul încare arhitectura de rutare a circuitului este legatã de conøinutul acestei teze.
2.4.1 Circuitele FPGA Xilinx
Circuitele FPGA Xilinx [177] conøin un tablou bidimensional de celule pro-
gramabile, numite blocuri logice configurabile ( Configurable Logic Block – CLB), inter-
conectate prin canale de rutare orizontale ši verticale (Figura 2.7). Resurseleprogramabile sunt configurate prin celule RAM statice, ši fiecare comutator de rutareeste implementat ca un tranzistor special controlat de un bit SRAM.
Prima serie a fost introdusã de firma Xilinx în 1985, actualmente existând alte
trei generaøii: XC3000 , XC4000 ši XC5000 . Deši circuitele XC3000 sunt utilizate încã
pe scarã largã, se va descrie familia XC4000 , care este mai recentã. Capacitatea acestor
circuite variazã de la aproximativ 2.000 la peste 15.000 de porøi echivalente. Aceastãmãsurã are semnificaøia de "echivalent cu un circuit MPGA de aceeaši dimensiune".Producãtorii circuitelor FPGA utilizeazã aceastã mãsurã pentru capacitatea logicã, dešieste discutabil dacã valorile indicate sunt realiste. Familia XC5000 are caracteristici
Figura 2.7. Arhitectura generalã a circuitelor FPGA Xilinx.

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 16
similare la un preø mai atractiv, având însã o vitezã mai redusã. Xilinx a dezvoltat ši o
familie de circuite FPGA bazate pe antifuzibile, XC8100 .
Blocul CLB este bazat pe tabele de memorie. O asemenea tabelã este un
tablou de memorie cu lãøimea de 1 bit; liniile de adresã ale memoriei sunt intrãri aleblocului logic, iar ieširea de 1 bit a memoriei este ieširea tabelei. O tabelã cu K intrãri
corespunde unei memorii de 2
K × 1 bit, iar utilizatorul poate realiza orice funcøie
logicã cu K intrãri prin programarea tabelei de adevãr a funcøiei logice direct în memo-
rie. Faøã de seria XC3000 , blocurile CLB ale circuitelor XC4000 utilizeazã o aranjare
ierarhicã a tabelelor care permite o capacitate logicã mai mare pentru un bloc. Existãdouã tabele cu patru intrãri, ši o a treia tabelã ale cãrei intrãri sunt ieširile celorlaltedouã. Aceastã configuraøie permite implementarea unei largi varietãøi de funcøii logice:douã funcøii independente de patru variabile, o singurã funcøie de cinci variabile, oricefuncøie de patru variabile împreunã cu anumite funcøii de cinci variabile, sau anumitefuncøii de pânã la nouã variabile. Fiecare bloc CLB conøine de asemenea douã bista-bile.
Circuitele XC4000 au caracteristici care permit integrarea unor sisteme com-
plete. De exemplu, fiecare bloc CLB conøine circuite care permit execuøia eficientã aoperaøiilor aritmetice. Acestea implementeazã operaøii cu transport rapid pentru cir-cuite de tip sumator. De asemenea, tabelele pot fi configurate ca celule RAM de tipR/W. Circuitele din seria XC4000E permit configurarea tabelelor ca memorii RAM cu
porturi duale, cu un singur port de scriere ši douã porturi de citire, existând posibili-tatea ca blocurile RAM sã fie sincrone. Fiecare circuit XC4000 conøine planuri ŠI largi
în jurul periferiei reøelei de blocuri logice pentru a facilita implementarea blocurilor decircuit cum sunt decodificatoarele de dimensiuni mari.
Structura de interconectare a circuitelor XC4000 este caracterizatã prin canale
orizontale ši verticale. Arhitectura de rutare este diferitã în mod semnificativ de seriileprecedente. Diferenøa cea mai importantã este înlocuirea interconexiunilor directe ši ainterconexiunilor cu scop general cu douã noi resurse, numite linii de lungime simplãši linii de lungime dublã. Liniile de lungime simplã, care sunt prevãzute pentru con-exiuni relativ scurte sau cele care nu sunt critice din punct de vedere al vitezei, sunt
ilustrate în Figura 2.8, unde fiecare × indicã un comutator de rutare.
Figura indicã trei îmbunãtãøiri arhitecturale ale seriei XC4000 :
1. Existã un numãr mai mare de segmente de interconectare. Deši numãrul indi-
cat în figurã este doar ilustrativ, XC4000 conøine un numãr dublu de segmente
faøã de seria XC3000 .
Figura 2.8. Linii de lungime simplã ale circuitelor XC4000 .

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 17
2. Cei mai muløi pini CLB se pot conecta la o mare parte a segmentelor de inter-
conectare. Aceasta reprezintã o creštere a conectivitãøii faøã de XC3000 .
3. Fiecare segment de interconectare de la intrarea unei matrici de comutatoare
se poate conecta numai la trei alte segmente, ceea ce reprezintã doar jumãtatefaøã de circuitele XC3000 .
Celelalte resurse de rutare ale circuitului XC4000 , care cuprind linii de lungime
dublã ši linii lungi, sunt ilustrate în Figura 2.9. Liniile de lungime dublã sunt similarecu cele de lungime simplã, cu excepøia faptului cã fiecare trece numai prin jumãtatedin matricile de comutare. Prin aceasta rezultã întârzieri de rutare mai mici pentruconexiuni de lungime moderatã care nu sunt potrivite pentru liniile lungi. Pentruclaritate, liniile de lungime simplã ši comutatoarele de rutare pentru conectarea la piniiblocurilor CLB nu sunt indicate în Figura 2.9. Liniile lungi se întind pe toatã dimensi-unea circuitului.
O caracteristicã importantã a structurii de interconectare Xilinx este cã semna-
lele trebuie sã treacã prin comutatoare pentru a ajunge de la un bloc CLB la altul, šinumãrul total de comutatoare parcurse depinde de setul particular de segmente utili-zate. De aceea, performanøa de vitezã a unui circuit implementat depinde în parte demodul în care utilitarele CAD alocã segmentele de interconectare pentru semnaleleindividuale.
2.4.2 Circuitele FPGA Altera
Circuitele FPGA Altera [6] sunt diferite de celelalte circuite FPGA deoarece ele
combinã tehnologiile FPGA ši CPLD ( Complex Programmable Logic Device ). Cu toate
acestea, ele sunt echivalente funcøional cu circuitele FPGA, deoarece utilizeazã untablou bidimensional de celule programabile ši o structurã de rutare programabilã, potimplementa o logicã multi-nivel, ši sunt programabile de cãtre utilizator. Arhitecturageneralã a circuitelor Altera , care se bazeazã pe tehnologia de programare EPROM,
este ilustratã în Figura 2.10. Aceasta constã dintr-o reøea de celule programabile, nu-mite blocuri ale reøelei logice ( Logic Array Block – LAB), interconectate printr-o resursã
de rutare numitã reøea de interconectare programabilã ( Programmable Interconnect
Array – PIA). Capacitatea circuitelor variazã între 2.000 ši 20.000 de porøi logice
echivalente.
Figura 2.9. Linii de lungime dublã ši linii lungi ale circuitului XC4000 .

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 18
Blocurile LAB sunt celule logice complexe, putând fi considerate ca circuite
PLD ( Programmable Logic Device ). Fiecare bloc LAB constã din douã blocuri princi-
pale, reøeaua de macrocelule ši blocul de expandare a termenilor produs.
Elementele din reøeaua de macrocelule conøin trei porøi ŠI ale cãror ieširi se
conecteazã la o poartã SAU, ieširea acesteia fiind conectatã la o poartã SAU EXCLUSIV;macrocelula mai conøine un bistabil. Fiecare intrare a unei macrocelule este generatãca o funcøie ŠI cablat (numitã termen p) a unor semnale. Un termen p poate conøine
orice semnal din reøeaua PIA, oricare din termenii produs ai blocului LAB, sau iešireaoricãrei alte macrocelule. Cu aceastã configuraøie, reøeaua de macrocelule funcøioneazãca un circuit PLD, dar cu un numãr mai redus de termeni produs pe registru (existã deobicei cel puøin opt termeni produs pe registru într-un circuit PLD). Conform firmeiAltera [6], prin aceasta blocul LAB este mai eficient, deoarece majoritatea funcøiilor
logice nu necesitã numãrul mare de termeni p întâlniøi la circuitele PLD, iar blocul LAB
permite generarea unor funcøii variate.
Fiecare bloc de expandare a termenilor produs constã dintr-un numãr de ter-
meni p, care sunt inversaøi ši aplicaøi la intrarea reøelei de macrocelule, ca ši la intrarea
blocului însuši. Aceastã configuraøie permite implementarea unor funcøii complexe,deoarece fiecare macrocelulã are acces la acešti termeni p suplimentari.
Structura de rutare, PIA, constã dintr-un numãr de segmente lungi de inter-
conectare care trec pe lângã fiecare bloc LAB. Structura PIA asigurã o conectivitatecompletã, deoarece fiecare intrare a unui bloc LAB poate fi conectatã la ieširea oricãruibloc LAB, fãrã restricøii. De aceea, rutarea unui circuit FPGA Altera este simplã. Însã,acest nivel de conectivitate este excesiv ši poate fi redus, dacã se utilizeazã un algo-ritm de rutare corespunzãtor.
Circuitele din seria Altera Flex 8000 constau dintr-o ierarhie cu trei nivele,
asemãnãtoare celei a circuitelor CPLD. Nivelul cel mai inferior al ierarhiei este un setde tabele de memorie, ši nu un bloc de tip PAL sau PLA, motiv pentru care Flex 8000
poate fi considerat un circuit FPGA. Capacitatea seriei 8000 este între 4.000 ši 15.000de porøi echivalente.
Figura 2.11 prezintã arhitectura generalã a circuitului Flex 8000 . Blocul logic de
bazã al circuitului, numit element logic, conøine o tabelã cu patru intrãri, un bistabil, šiun circuit special de transport pentru circuite aritmetice (similar cu XC4000 ). Elemen-
tul logic conøine de asemenea circuite de cascadare care permit implementarea efi-cientã a funcøiilor ŠI de dimensiuni mari.
Figura 2.10. Arhitectura generalã a circuitelor FPGA Altera.

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 19
Elementele logice sunt grupate în seturi de câte opt, numite blocuri de reøele
logice. Fiecare din aceste blocuri conøin interconexiuni locale, prin care un elementlogic poate fi conectat cu oricare alt element logic din cadrul aceluiaši bloc. Intercon-exiunile locale sunt legate la interconexiunile globale FastTrack ale circuitului. Ca ši
liniile lungi ale circuitului XC4000 , fiecare conexiune FastTrack se extinde pe toatã
înãløimea sau lãøimea circuitului. O diferenøã majorã între circuitele Flex 8000 ši Xilinx
este însã cã FastTrack consøine numai linii lungi, ceea ce permite configurarea simplã
a circuitului. Toate liniile orizontale FastTrack sunt identice. De aceea, întârzierile de
interconectare ale circuitului Flex 8000 sunt mai predictibile decât cele ale altor cir-
cuite FPGA care utilizeazã segmente mai scurte, deoarece cãile mai lungi conøin maipuøine comutatoare programabile. Mai mult, conexiunile între liniile orizontale ši verti-cale trec prin buffere active, îmbunãtãøind în plus predictibilitatea.
Familia de circuite Flex 10K are toate caracteristicile familiei Flex 8000 , ši dis-
pune în plus de blocuri SRAM de dimensiune variabilã. Fiecare rând de blocuri dereøele logice are un asemenea bloc SRAM la un capãt. Blocurile SRAM pot fi configu-
rate pentru diferite aranjamente: 256 ×8, 512×4, 1K×2, sau 2K ×1. Aceste blocuri pot fi
configurate ši pentru implementarea unui circuit logic complex, ca de exemplu un cir-cuit de înmuløire. Considerând ši blocurile SRAM ca porøi logice, Flex 10K oferã cea
mai mare capacitate dintre circuitele FPGA, deši obøinerea unui numãr exact este difi-cilã.
2.4.3 Circuitele FPGA Actel
Arhitectura de bazã a circuitelor FPGA Actel, prezentatã în Figura 2.12, este
similarã cu cea a circuitelor MPGA, constând din rânduri de celule programabile, nu-mite module logice ( Logic Module – LM), între rânduri existând canale de rutare ori-
zontale. Fiecare comutator de rutare este implementat printr-un antifuzibil. Actel
dispune de trei generaøii de circuite FPGA, Act-1, Act-2, ši Act-3.
Figura 2.11. Arhitectura generalã a circuitului Altera Flex 8000 .

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 20
Modulul logic al circuitelor Actel ilustreazã o abordare diferitã faøã de cea întâl-
nitã la circuitele FPGA Xilinx . În timp ce Xilinx utilizeazã un bloc CLB complex, blo-
cul logic al circuitelor Actel este foarte simplu. Cercetãrile au arãtat cã ambele variante
au avantaje, ši alegerea cea mai bunã pentru o celulã programabilã depinde de per-formanøele de vitezã ale arhitecturii de rutare [27]. Modulul LM al circuitului Act-1 se
bazeazã pe o configuraøie de multiplexoare, prin care se poate implementa orice fun-cøie de douã variabile, cele mai multe funcøii de trei variabile, ši unele funcøii de patruvariabile, cu un total de pânã la 702 funcøii logice.
Arhitectura de rutare a circuitelor Actel este ilustratã în Figura 2.13, în care se
indicã pentru claritate numai resursele de rutare conectate la modulul LM din centrulfigurii. Existã patru tipuri distincte de resurse de rutare: segmente de rutare, segmentede iešire, piste de ceas ši segmente de interconectare. Segmentele de intrare conec-teazã patru din intrãrile LM la segmentele de interconectare aflate deasupra modululuilogic ši patru intrãri la segmentele de interconectare de sub modulul logic. Un seg-ment de iešire conecteazã ieširea LM la mai multe canale. Segmentele de interconec-tare constau din linii metalice de diferite lungimi care pot fi conectate împreunã prinantifuzibile pentru a forma linii mai lungi. Circuitul Act-1 dispune de 22 piste de seg-
mente de interconectare în fiecare canal, ši de 13 piste verticale (acestea nu sunt ilus-trate în figurã). Pistele de ceas reprezintã linii speciale cu întârziere redusã care sunt
Figura 2.12. Arhitectura generalã a circuitelor FPGA Actel.
Figura 2.13. Arhitectura de rutare a circuitului Act-1.

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 21
utilizate pentru semnale care trebuie conectate la mai multe module LM cu o nesime-
trie minimã.
Performanøele de vitezã ale circuitelor Actel nu sunt complet predictibile, deo-
arece numãrul de antifuzibile traversate de un semnal depinde de modul de alocare asegmentelor de interconectare de cãtre utilitarele CAD. Performanøele de vitezã suntîmbunãtãøite însã în mod semnificativ prin posibilitãøile multiple de selecøie a lungimiisegmentelor din fiecare canal ši prin algoritmi care garanteazã limite stricte a numãru-lui de antifuzibile traversate de oricare conexiune.
Circuitul Act-2 reprezintã o versiune îmbunãtãøitã a circuitului Act-1, conøinând
douã celule programabile diferite, numite module C (combinaøionale) ši module S(secvenøiale). Modulul C este similar cu modulul LM al circuitului Act-1, deši este mai
complex, în timp ce modulul S este optimizat pentru implementarea elementelorsecvenøiale. Arhitectura de rutare a circuitului Act-2 este de asemenea similarã cu cea a
circuitului Act-1, dar numãrul de piste este de 36 în fiecare canal de rutare ši de 15 în
fiecare coloanã.
2.4.4 Circuitele FPGA Quicklogic
Circuitele FPGA pASIC ale firmei Quicklogic se bazeazã de asemenea pe anti-
fuzibile, ca ši circuitele Actel. Existã douã familii de circuite FPGA Quicklogic, pASIC ši
pASIC2 . Circuitul pASIC are similaritãøi cu mai multe tipuri de circuite FPGA: ca ši cir-
cuitele Xilinx , are o structurã de tip tablou; ca ši circuitele Actel, blocurile sale logice
utilizeazã multiplexoare, ši ca ši circuitul Altera Flex 8000 , interconexiunile acestuia
constau numai din linii lungi. Circuitul pASIC2 este o versiune îmbunãtãøitã a circuitu-
lui pASIC . Firma Cypress oferã de asemenea circuite utilizând arhitectura pASIC .
Structura antifuzibilului Quicklogic , numitã ViaLink , constã dintr-un strat supe-
rior de metal, un strat izolator amorf de siliciu, ši un strat inferior de metal. Comparativcu antifuzibilul Actel, numit PLICE , ViaLink oferã o rezistenøã foarte redusã în starea
conductoare, de aproximativ 50 Ω (rezistenøa PLICE este în jur de 300 Ω), ši o capaci-
tate parazitã redusã. Antifuzibilele ViaLink sunt prezente la fiecare intersecøie a pinilor
blocurilor logice ši a liniilor de interconectare, asigurând o conectivitate ridicatã.
Blocul logic al circuitului pASIC este mai complex decât modulul logic al cir-
cuitului Actel, cu un numãr mai mare de intrãri, având porøi ŠI cu šase intrãri pe liniile
de selecøie ale multiplexoarelor. Fiecare bloc logic conøine de asemenea un bistabil.
2.5 Dificult ățile proiect ării fizice
Proiectarea fizicã este o problemã complexã de optimizare, care implicã mai
multe funcøii obiectiv, de exemplu suprafaøa ocupatã de circuit, lungimea interconexi-unilor, numãrul orificiilor de trecere. Circuitul trebuie sã satisfacã toate constrângerileimpuse de specificaøie. De exemplu, dacã tehnologia utilizatã este cea a reøelelor deporøi, existã o constrângere asupra spaøiului disponibil pentru interconexiuni. Numãrulstraturilor de rutare este o altã constrângere. Similar, pot fi constrângeri asupra mode-lului de rutare, de exemplu pot fi permise numai trasee orizontale ši verticale, liniilede alimentare trebuie sã fie metalice ši sã aibã o lãøime suficientã pentru a permitedensitatea maximã de curent etc.
Existã dificultãøi practice atunci când se încearcã satisfacerea tuturor cerinøelor
specificate. În primul rând, este dificilã modelarea problemei de proiectare fizicã dacãexistã un numãr mare de constângeri ši se dorešte optimizarea unui numãr mare defuncøii obiectiv. Problema este dificilã ši pentru cã unele din aceste funcøii obiectiv seaflã în conflict cu altele. De exemplu, considerãm cazul circuitelor cu reøele de porøi.Dacã se încearcã minimizarea lungimii totale a interconexiunilor prin plasarea apro-

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 22
piatã a componentelor puternic conectate, va crešte congestia interconexiunilor în
anumite regiuni ale circuitului. Aceasta poate determina ca circuitul sã fie nerutabil,deoarece existã un numãr fix de piste disponibile în fiecare canal al reøelei de porøi.
Din cauza dificultãøilor amintite, nu se poate concepe un singur program pen-
tru problema de proiectare fizicã. Existenøa mai multor tipuri de circuite face ca prob-lema sã fie ši mai dificilã. Astfel, sunt necesare abordãri diferite pentru plasareareøelelor de porøi, a celulelor standard, a macro-celulelor, sau a circuitelor FPGA. Încazul reøelelor de porøi, existã constrângeri privind suprafaøa ocupatã de interconexi-uni, numãrul de canale, ši numãrul de piste pe canal. De aceea, rutabilitatea este deimportanøã majorã pentru reøelele de porøi. În cazul celulelor standard, existã o maimare flexibilitate în privinøa suprafeøei interconexiunilor, de aceea accentul se pune peoptimizarea acestei suprafeøe. În plus, se poate minimiza numãrul celulelor de trecereastfel încât sã se reducã suprafaøa totalã ocupatã de circuit. În cazul circuitelor cumacro-celule, celulele care trebuie plasate au dimensiuni ši forme diferite. De aceea,este necesarã conceperea unui plan de amplasare al circuitului ši definirea canalelor.Ordinea în care trebuie rutate aceste canale este de asemenea importantã.
Problema de proiectare fizicã este divizatã de obicei în mai multe subprobleme
mai simple. O subdiviziune posibilã este urmãtoarea:
1. Partiøionarea circuitului;
2. Planul de amplasare ši definirea canalelor;
3. Plasarea celulelor;
4. Rutarea globalã;
5. Ordonarea canalelor;
6. Rutarea detaliatã a liniilor de alimentare ši masã;
7. Rutarea detaliatã a celorlalte conexiuni.
Partiøionarea unui circuit este necesarã în cazul în care acesta nu poate fi im-
plementat într-o singurã capsulã. Planul de amplasare ši definirea canalelor sunt ne-
cesare pentru circuitele cu macro-celule. Planul de amplasare cuprinde gãsirea alinieriiši a orientãrii relative a modulelor astfel încât suprafaøa totalã a circuitului sã fie mini-mizatã. Dupã aceastã etapã, regiunea de rutare trebuie divizatã în canale ši blocuri decomutare. În timpul plasãrii , se determinã poziøiile exacte ale componentelor de cir-
cuit, astfel încât sã se reducã lungimea estimatã a conexiunilor. Rutarea urmeazã dupã
etapa de plasare, ši se executã de obicei în douã faze: rutarea globalã ši rutarea de-taliatã. Rutarea globalã decide pentru fiecare conexiune un plan de rutare sub forma
canalelor prin care va fi rutatã conexiunea. Este necesarã apoi selectarea unei ordinipentru rutarea canalelor ši a blocurilor de comutare, deoarece descrierea unui canalpoate depinde de rutarea altor canale. Prin descrierea unui canal se înøelege ordonareaexactã a pinilor pe marginile de sus ši de jos ale canalului. Dupã aceasta se poate ex-ecuta rutarea detaliatã , care implicã asignarea efectivã a interconexiunilor la pistele
canalului. Conexiunile de alimentare ši masã sunt rutate de obicei separat, datoritãconstrângerilor speciale asupra stilului de rutare a acestora.
Toate subproblemele menøionate sunt probleme de optimizare cu constrângeri.
O asemenea problemã constã din gãsirea unei soluøii fezabile care satisface un setspecificat de constrângeri de proiectare ši optimizeazã o funcøie obiectiv datã. Exemplede constrângeri de proiectare sunt: un numãr restrâns de straturi de rutare, dimensiuniši forme de celule, resurse de rutare, constrângeri geometrice etc. Exemple de funcøiiobiectiv sunt: lungimea totalã a interconexiunilor, densitatea canalelor, întârzierile deinterconectare, sau o combinaøie a acestora.
Aceste subprobleme sunt de obicei NP-complete. De aceea, nu se cunosc algo-
ritmi eficienøi care pot gãsi soluøii optime ale acestor probleme. De exemplu, o sub-problemã care apare în cazul unui circuit cu n celule este aranjarea acestor celule într-
o secvenøã liniarã astfel încât sã se minimizeze lungimea totalã a interconexiunilor.Spaøiul de cãutare conøine n! aranjamente posibile. Pentru examinarea tuturor aran-
jamentelor ši selectarea celei optime este necesarã metoda forøei brute. Aceastãabordare este însã impracticã, deoarece timpul de calcul este prohibitiv. Pot exista însã

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 23
metode prin care se eliminã cãutarea într-o mare parte a spaøiului de cãutare, rezultând
un numãr de aranjamente dat de f (n), unde f (n) este o funcøie polinomialã de n. O
asemenea funcøie, de exemplu n2 + 2n, nu crešte prea rapid pentru valori mari ale lui
n.
Pentru soluøionarea problemelor complexe de optimizare de dimensiuni mari
se utilizeazã tehnici euristice . O euristicã este un algoritm care va efectua cãutarea
numai într-un subspaøiu al spaøiului total de cãutare pentru a gãsi o soluøie acceptabilã,care satisface toate constrângerile de proiectare. De aceea, cerinøele de timp ale unuialgoritm euristic sunt reduse.
Pentru a evalua calitatea soluøiei generate de un algoritm euristic, se presupune
cã s-a elaborat un asemenea algoritm A pentru o problemã de minimizare. Dacã S
A
este soluøia generatã de acest algoritm ši S* este soluøia optimã, o mãsurã a erorii ( ε)
introduse de algoritmul euristic este datã de deviaøia soluøiei euristice de la soluøia op-timã, deci
ε=−∗
∗SS
SA(2.1)
Aceastã eroare nu poate fi mãsuratã în mod simplu, deoarece S* nu este cunoscut. De
aceea, trebuie utilizate alte tehnici pentru evaluarea calitãøii soluøiilor generate de algo-ritmii euristici.
O posibilitate pentru rezolvarea acestei probleme constã în generarea artificialã
a unor intrãri de test pentru care soluøia optimã este cunoscutã dinainte. De exemplu,în scopul testãrii unui algoritm euristic pentru amplasare, intrãrile de test pot fi gener-ate dupã cum urmeazã. Se începe cu un dreptunghi D care se divizeazã în drep-
tunghiuri mai mici. Dacã aceste dreptunghiuri se constituie ca intrãri pentru programulde amplasare, soluøia optimã este cunoscutã – un plan de asamblare asemãnãtor cudreptunghiul D. Aceastã metodã de testare nu este însã fezabilã întotdeauna. Este difi-
cilã generarea unor asemenea intrãri de test pentru programele de rutare globalã, ru-tare prin canale etc.
Pentru compararea performanøelor algoritmilor euristici se utilizeazã circuite
reale de test ( benchmark ). Aceste circuite sunt create de experøi în domeniu. Pentru
problemele de proiectare fizicã, existã douã seturi de circuite de test utilizate pe scarãlargã: circuitele de test MCNC ( Microelectronics Center of North Carolina ) ši cele ISCAS
(International Symposium on Circuits and Systems ).
2.6 Concluzii
În acest capitol s-a prezentat în mod sintetic situaøia actualã în domeniul cir-
cuitelor VLSI ši FPGA, ši a fost descris procesul de proiectare al acestor circuite. Acestproces este complex, ši pentru reducerea complexitãøii se introduc mai multe nivele deabstractizare. Au fost prezentate nivelele tipice de abstractizare ši etapele de proiectarecorespunzãtoare: proiectarea arhitecturalã , proiectarea logicã ši proiectarea fizicã .
Proiectarea arhitecturalã cuprinde douã etape principale: proiectarea cãii de
date ši proiectarea cãii de control. Generarea automatã a cãii de date ši a cãii de con-trol este numitã sintezã de nivel înalt .
Pentru circuitele VLSI, proiectarea logicã constã în selectarea componentelor
dintr-o bibliotecã de module astfel încât sã se minimizeze costul total ši sã se maxi-mizeze performanøele. Pentru circuitele FPGA, în cadrul proiectãrii logice se efectueazãoperaøiile de partiøionare ši mapare tehnologicã . În cadrul partiøionãrii, proiectul este
divizat în mai multe pãrøi astfel încât sã fie posibilã implementarea fiecãreia într-uncircuit FPGA. În cadrul mapãrii tehnologice, pentru fiecare parte care va fi implemen-

Contribuøii la proiectarea asistatã de calculator a sistemelor numerice 24
tatã într-un singur circuit FPGA, logica este divizatã în fragmente care pot fi imple-
mentate într-un singur bloc logic al circuitului.
Proiectarea fizicã este etapa finalã a procesului de proiectare pentru circuitele
VLSI ši FPGA, ši aceastã etapã reprezentã subiectul principal al tezei. Proiectarea fizicãimplicã în principal operaøiile de plasare a modulelor ši de rutare a conexiunilor.
În cazul circuitelor VLSI, metodele de proiectare sunt elaborate în general
pentru un anumit tip de circuit. Au fost prezentate principalele tipuri de circuite VLSIutilizate: reøele de porøi , celule standard , macro-celule , circuite FPGA . O reøea de porøi
constã dintr-un numãr mare de tranzistoare care sunt prefabricate sub forma unuitablou bidimensional. Iniøial tranzistoarele nu sunt conectate între ele. O celulã, deexemplu o poartã logicã, poate fi creatã prin gruparea tranzistoarelor dintr-o zonã areøelei ši interconectarea lor utilizând procesul obišnuit de mascare. Modelele de inter-conectare pentru diferite celule sunt memorate într-o bibliotecã. Deoarece toateetapele cu excepøia celei de interconectare sunt identice pentru toate reøelele de porøi,va fi necesar un timp foarte redus pânã la fabricarea circuitului final.
O celulã standard este un bloc logic care executã o funcøie standard. Infor-
maøiile legate de celulele standard sunt pãstrate de asemenea într-o bibliotecã, dar înacest caz sunt necesare toate etapele de fabricaøie pentru crearea unui circuit. Arhi-tectura acestor circuite este diferitã de cea a reøelelor de porøi, constând din rânduri decelule de aceeaši înãløime. Rândurile sunt separate prin canale de rutare orizontale.Pentru conectarea celulelor aflate în rânduri non-adiacente, se pot utiliza conexiuniverticale scurte care trec prin celule de tip special, numite celule de trecere.
În cazul macro-celulelor sunt eliminate restricøiile de dimensiune existente la
reøelele de porøi ši la celulele standard. În acest caz pot varia ambele dimensiuni alecelulelor. Avantajul principal al macro-celulelor este cã biblioteca poate conøine celulede o complexitate mult mai mare. Deoarece nu existã un plan de amplasare standard,ši canalele de rutare nu sunt predefinite, proiectarea acestor circuite este mai dificilã,fiind necesare etapele suplimentare de amplasare ši definire a canalelor.
Circuitele FPGA sunt formate dintr-o reøea bidimensionalã de blocuri logice,
care pot fi programate pentru a implementa diferite funcøii logice. Între aceste blocuriexistã resurse de interconectare, formate din canale ši blocuri de interconectare. Inter-conexiunile conøin comutatoare programabile cu rolul de a conecta blocurile logice lasegmentele de interconectare, sau segmentele de interconectare între ele. De aseme-nea, existã celule de I/E la periferia reøelei. Avantajele circuitelor FPGA faøã de reøelelede porøi sunt costurile de prototipizare mai reduse ši durata mai scurtã de producøie,avantaje care au determinat utilizarea pe scarã largã a acestor circuite. Dezavantajelecircuitelor FPGA sunt viteza de operare mai redusã ši densitatea mai redusã a porøilor.
Deoarece implementãrile ši experimentãrile din cadrul tezei au fost efectuate
pentru circuite FPGA, au fost descrise exemple reprezentative de arhitecturi ale unorcircuite FPGA comerciale, cu scopul de a dispune de un punct de referinøã pentrumodelul de circuit utilizat în cadrul tezei. Au fost descrise circuitele Xilinx ( XC4000 ,
XC5000 ), Altera ( Flex 8000 ), Actel ( Act-1, Act-2) ši Quicklogic ( pASIC , pASIC2 ). Cir-
cuitele Xilinx ši Altera utilizeazã memorii SRAM, iar cele Actel ši Quicklogic utilizeazãantifuzibile. Pentru fiecare circuit s-a descris arhitectura generalã ši arhitectura de ru-tare.
Existã numeroase dificultãøi legate de proiectarea fizicã. Aceasta este o prob-
lemã complexã de optimizare, care implicã mai multe funcøii obiectiv. Circuitul trebuiesã satisfacã de asemenea toate constrângerile impuse de specificaøie. Existã dificultãøipractice atunci când se încearcã satisfacerea tuturor cerinøelor specificate. Este dificilãmodelarea problemei de proiectare fizicã dacã existã un numãr mare de constângeri šise dorešte optimizarea unui numãr mare de funcøii obiectiv. Unele din aceste funcøiiobiectiv se aflã în conflict cu altele.
Din cauza acestor dificultãøi, problema de proiectare fizicã este divizatã de obi-
cei în mai multe subprobleme mai simple. Principalele subprobleme sunt: par-

Analiza situaøiei actuale în domeniul circuitelor VLSI ši FPGA 25
tiøionarea, planul de amplasare ši definirea canalelor, plasarea, rutarea globalã ši ru-
tarea detaliatã. Toate aceste subprobleme sunt probleme de optimizare complexe, caretrebuie sã gãseascã o soluøie fezabilã care satisface un set specificat de constrângeri deproiectare ši optimizeazã o anumitã funcøie obiectiv.
Aceste subprobleme sunt de obicei NP-complete. De aceea, nu se cunosc algo-
ritmi eficienøi care pot gãsi soluøii optime ale acestor probleme. Pentru soluøionareaacestora se utilizeazã tehnici euristice. O asemenea tehnicã efectueazã cãutarea numaiîntr-un subspaøiu al spaøiului total de cãutare pentru a gãsi o soluøie apropiatã de ceaoptimã, care satisface toate constrângerile de proiectare.