minimizarea starilor

8/18/2019 Minimizarea starilor

1/47

UNIVERSITATEA TEHNIC! din CLUJ-NAPOCAFACULTATEA de AUTOMATIC! "i CALCULATOARECATEDRA de CALCULATOARE

Sistem CAD pentrusinteza sistemelor numerice

Referat de doctorat

Conduc#tor "tiin$ific, Doctorand,

Prof. Dr. Ing. PUSZTAI Kalman ".l. ing. BARUCH Zoltan-Francisc


2/47

Sistem CAD pentru sinteza sistemelor numerice %

Cuprins

%. Metodologii de proiectare........................................................................................... 2

2. Sisteme de sintez!........................................................................................................ 8

2.%. Sistem generic de sintez# ....................................................................................... 8

2.2. Sinteza la nivel de sistem..................................................................................... %0

2.3. Sinteza la nivel de cip .......................................................................................... %2

2.4. Sinteza logic# "i secven$ial#................................................................................. %5

2.5. Proiectarea fizic#.................................................................................................. %8

2.6. Baza de date a sistemului..................................................................................... %9

2.7. Baza de date a componentelor ............................................................................. 22

2.8. Mediul de conceptualizare ................................................................................... 24

3. Rafinarea specifica"iilor ........................................................................................... 29

3.%. Introducere ........................................................................................................... 29

3.2. Rafinarea grup#rii variabilelor............................................................................. 29

3.2.%. Amplasarea variabilelor în memorie............................................................. 30

3.2.2. Translatarea adreselor de memorie ............................................................... 3%

3.3. Rafinarea canalelor "i a magistralelor.................................................................. 33

3.3.%. Parametrii canalelor "i magistralelor............................................................. 33

3.3.2. Definirea problemei ...................................................................................... 343.3.3. Generarea magistralei ................................................................................... 34

3.3.4. Generarea protocolului.................................................................................. 40

4. Concluzii .................................................................................................................... 43

Bibliografie .................................................................................................................... 46


3/47


4/47

Sistem CAD pentru sinteza sistemelor numerice 3

lea"i prelucr #ri. Se va presupune c# descrierea de intrare const# numai din asign#ri alevariabilelor utilizând operatori aritmetici. Aceast# descriere este compilat# într-un graf al fluxului de date (GFD) care identific# în mod explicit dependen$ele de date (Figura#(a)). Se presupune c# apar noi date în fiecare ciclu de ceas, "i fiecare itera$ie a buclei se

execut# în dou# cicluri de ceas. Se presupune de asemenea c# fiecare opera$ie este exe-cutat# într-un ciclu de ceas de o unitate func$ional# cu o singur # func$ie, toate unit#$ilefunc$ionale "i registrele au acela"i num#r de bi$i, iar num#rul de unit#$i func$ionale nueste limitat.

Resursele hardware "i restric$iile de proiectare fiind specificate, se pot aplica al-goritmii de planificare "i alocare. Ace"ti algoritmi adnoteaz# graful fluxului de date cuatribute suplimentare pentru a indica asignarea la st#ri "i componente. Fiecare operator este asignat la o stare de control "i la o unitate func$ional# pentru a executa opera$ia înciclul de ceas dat. Fiec#rei muchii din graful fluxului de date îi este asignat un latch, un

registru sau o conexiune. Graful adnotat, indicat în Figura #(b), este utilizat pentru ge-

Figura #. Sistem simplu de sintez#: (a) GFD; (b) GFD adnotat; (c) structurac#ii de date; (d) sistemul de sintez#.


5/47


nerarea c#ii de date, prezentat# în Figura #(c). De notat c# graful adnotat "i calea dedate ob$inut# au aceea"i topologie, ceea ce indic# simplitatea arhitecturii destina$ie "i aalgoritmilor de asignare.

Sistemul de sintez# pentru acest exemplu simplu (Figura #(d)) va constadintr-un compilator pentru conversia descrierii func$ionale de intrare în reprezentareaGFD, un planificator pentru asignarea st#rilor de control, un alocator pentru selec$ia "iasignarea unit#$ilor func$ionale la opera$ii "i a unit#$ilor de memorie la valori ale datelor,"i un generator al listelor de conexiuni pentru generarea listei de conexiuni a c#ii de da-te, care pot fi utilizate de alte sisteme. Lista de conexiuni a c#ii de date con$ine compo-nente RT interconectate, "i anume un sumator, un sc#z#tor, un circuit de înmul$ire "iregistre. Deoarece s-a presupus c# fiecare unitate execut# o singur # func$ie "i are acela"inum#r de bi$i, se poate presupune de asemenea c# un singur proiectant va proiecta în

prealabil toate unit#$ile func$ionale "i de memorie pentru diferite tehnologii, acestea fi-ind memorate într-un set de fi"iere accesibile de ceilal$i proiectan$i. Fiecare fi"ier va

con$ine dimensiunile fizice ale unit#$ilor pentru amplasare "i pozi$ia porturilor de I/E pentru rutare. Astfel, etapa de proiectare fizic# va consta din executarea amplas#rii "irut#rii pentru lista de conexiuni a c#ii de date, utilizând dimensiuni ale unit#$ilor "i lo-ca$ii ale porturilor predefinite.

Sistemul de sintez# prezentat în Figura #(d) are numeroase limit#ri care îi res-trâng utilitatea în situa$iile practice. În primul rând, presupunerea c# toate unit#$ile auacela"i num#r de bi$i "i aceea"i întârziere de propagare este prea restrictiv#. Un proiec-tant are de obicei posibilitatea de a alege între unit#$i cu mod de func$ionare, întârzieride propagare "i num#r de bi$i diferi$i. În al doilea rând, stilul de proiectare de tipul flu-xului de date, în care num#rul unit#$ilor func$ionale este egal cu num#rul operatorilor

din descrierea func$ional#, este costisitor pentru proiectele obi"nuite, cu excep$ia celor foarte simple. Pe de alt# parte, o arhitectur # destina$ie cu un num#r foarte redus de uni-t#$i func$ionale necesit# o unitate de control pentru a asigura secven$ierea corect# a exe-cu$iei opera$iilor "i partajarea corespunz#toare a unit#$ilor func$ionale. Pentru oasemenea arhitectur #, trebuie s# se utilizeze o metodologie de proiectare diferit#. În altreilea rând, presupunerea c# rata datelor de intrare "i de ie"ire este aceea"i cu rata deintrare "i de ie"ire a c#ii de date, este de asemenea prea restrictiv#. Datele pot proveni dela diferite surse, într-o ordine diferit# "i momente de timp diferite, "i nu sunt sincroni-zate întotdeauna cu ceasul c#ii de date. Din acest motiv, sunt necesare cozi de intrare "ide ie"ire sau memorii, pentru a sincroniza "irurile de date cu rate "i protocoale diferite.

În scopul prezent#rii unui sistem de sintez# pentru o clas# mai larg# de arhitec-turi, se va considera acela"i exemplu, dar cu restric$ii de proiectare diferite. Se va impu-ne ca opera$ia y = (a + b) * (c - d) s# fie executat# într-un timp de 300 ns, utilizândnumai dou# unit#$i func$ionale, un circuit de înmul$ire "i un sumator/sc#z#tor, cu întâr-zieri de propagare mai mici de %00 ns fiecare.

Graful fluxului de date pentru calculul valorii y este indicat în Figura 2(a). Gra-ful poate fi planificat în trei st#ri de control, utilizând circuitele date. Deoarece se potreutiliza registrele r 2 "i r 4, vor fi necesare în final numai cinci registre, în compara$ie cu"apte registre utilizate în Figura #(b) "i (c). Vor fi necesare în schimb patru multiple-xoare 2:%. Graful adnotat este prezentat în Figura 2(b), iar structura circuitului este pre-zentat# în Figura 2(c).


6/47


Pe lâng# calea de date, circuitul final necesit# o unitate de control pentru selec$ia"i înc#rcarea valorilor în registre "i pentru selec$ia opera$iilor executate de unit#$ile fun-c$ionale. Unitatea de control are de asemenea rolul de a înc#rca datele din unitatea Me-morie1 "i de a memora datele în unitatea Memorie2, "i necesit# o alt# cale de date pentrugenerarea adreselor de înc#rcare "i memorare. Utilizarea resurselor este indicat# în Fi-gura 2(d). Fiecare opera$ie necesit# pentru execu$ie un ciclu de ceas, inclusiv pentruînc#rcarea "i memorarea datelor, iar fiecare itera$ie necesit# cinci cicluri de ceas. O nou#itera$ie este lansat# la fiecare dou# cicluri de ceas. Astfel, sunt necesare 2(n-%)+5 cicluride ceas pentru a termina n itera$ii.

Figura 2. Un exemplu cu 3 opera$ii: (a) GFD; (b) GFD adnotat; (c)implementarea ASFD; (d) utilizarea resurselor; (e) îmbun#t#$irea utiliz#rii

resurselor.


7/47


Se observ# c# unitatea aritmetic# "i logic# este o resurs# critic#, fiind utilizat# înfiecare ciclu de ceas, în timp ce circuitul de înmul$ire "i fiecare din cele dou# memoriisunt utilizate numai într-unul din dou# cicluri de ceas. Se poate realiza un compromisîntre gradul de utilizare al unor componente "i spa$iul de pe cip. De exemplu, se poate

înlocui circuitul de înmul$ire cu unul mai lent, care necesit# dou# cicluri de ceas, dar unspa$iu mai redus. Similar, se pot utiliza memorii mai lente, sau acestea se pot înlocui cumemorii având un num#r mai mic de porturi sau un num#r mai mic de bi$i pe cuvânt. Deexemplu, unitatea Memorie1, cu patru porturi de câte %6 bi$i, poate fi înlocuit# cu omemorie cu dou# porturi de câte %6 bi$i. Deci, vor fi necesare dou# cicluri de ceas pen-tru a furniza patru operanzi de câte %6 bi$i. Se poate utiliza un singur port de %6 bi$i

pentru unitatea Memorie2, fiind necesare dou# cicluri de ceas pentru memorarea rezul-tatului de 32 bi$i. Astfel, dac# se înlocuie"te circuitul de înmul$ire "i ambele memorii cucomponente care necesit# dou# cicluri de ceas în loc de un ciclu, toate componentele vor fi utilizate complet (Figura 2(e)). Timpul total de execu$ie a buclei va cre"te numai cu

trei cicluri de ceas, fiind de 2(n-%)+8 cicluri de ceas pentru n itera$ii.Exemplul precedent demonstreaz# faptul c# sinteza de nivel înalt genereaz# odescriere structural# care con$ine componente ca unit#$i aritmetice "i logice, circuite deînmul$ire, multiplexoare, registre, memorii "i controlere. Pentru fiecare din aceste com-

ponente, trebuie s# se realizeze sinteza utilizând tehnici de sintez# logic# sau secven$ial# pe baza descrierii componentelor memorate într-o baz# de date a componentelor (BDC).Aceast# baz# de date poate con$ine de asemenea dimensiunea fiec#rei componente nece-sar # pentru opera$ia de amplasare, "i pozi$ia fiec#rui pin al componentelor necesar #

pentru rutarea în cadrul proiect#rii fizice. Figura 3 prezint# o schem#-bloc a sistemuluide sintez# care con$ine o baz# de date a componentelor.

Figura 3. Sistem de sintez# cu o baz# de date a componentelor.


8/47


Un proiect poate fi îmbun#t#$it în mod iterativ prin alegerea unei alte arhitecturidestina$ie, a unei alte topologii sau a unor caracteristici diferite ale componentelor. Înultimul exemplu, îmbun#t#$irea s-a realizat prin cre"terea gradului de utilizare a unor componente. Proiectantul estimeaz# de obicei calitatea proiectului "i efectueaz# modifi-

c#ri ale stilului de proiectare "i ale restric$iilor de proiectare pentru a îmbun#t#$i proiec-tul în mod iterativ. Aceast# opera$ie poate fi automatizat#, prin definirea unor indicatoride calitate "i dezvoltarea unei proceduri pentru estimarea calit#$ii, care realizeaz# selec-$ia caracteristicilor proiectului (Figura 4).

Figura 4. Sistem de sintez# utilizând îmbun#t#$irea iterativ#.


9/47


2. Sisteme de sintez!

22..##.. SSiisstteemm ggeenneerriicc ddee ssiinntteezz!!

În aceast# sec$iune se vor formula cerin$ele pentru procesul de proiectare "i se va

descrie un sistem generic de sintez# ipotetic. Acest sistem este generic, deoarece reu-ne"te toate conceptele principale ale sintezei de nivel înalt. Sistemul este ipotetic, deoa-rece niciunul din sistemele de sintez# comerciale sau de cercetare nu satisfac toatecriteriile prezentate în continuare:

(a) Completitudine. Sistemul trebuie s# pun# la dispozi$ie utilitare de sintez# pentrutoate nivelele procesului de proiectare, de la specifica$ie "i pân# la documenta$iade fabrica$ie. Utilitarele de sintez# trebuie s# se poat# adapta la diferitele arhi-tecturi destina$ie.

(b) Extensibilitate. Sistemul trebuie s# fie suficient de flexibil pentru a permite ad#-

ugarea unor noi algoritmi "i utilitare. Similar, sistemul trebuie s# permit# ad#u-garea unor noi stiluri arhitecturale, dac# este posibil, numai prin rescriereastrategiilor procesului de proiectare ( a scenariilor). Sistemul trebuie s# permit#de asemenea ad#ugarea unor noi componente "i a unor algoritmi pentru adapta-rea acestor componente la diferite tehnologii.

(c) Controlabilitate. Un proiectant trebuie s# aib# posibilitatea de a controla tipulutilitarelor care se vor utiliza pentru o anumit# descriere "i ordinea în care aces-tea vor fi executate. Acela"i proiectant trebuie s# aib# posibilitatea de a controlaexplorarea spa$iului de proiectare, prin selec$ia diferitelor stiluri arhitecturale "i adiferitelor componente. În scopul asist#rii proiectantului în cadrul procesului deselec$ie, sistemul trebuie s# pun# la dispozi$ie diferi$i indicatori de estimare aicalit#$ii.

(d) Interactivitate. Proiectantul trebuie s# aib# posibilitatea de a interac$iona cu uti-litarele de sintez#, prin specificarea par $ial# a structurii proiectului, sau prin mo-dificarea proiectului dup# sintez#. De asemenea, proiectantul trebuie s# poat#modifica fiecare asignare a obiectelor func$ionale la obiectele structurale.

(e) Îmbun!t !" irea metodologiei de proiectare. Sistemul de sintez# trebuie s# permit#îmbun#t#$irea calit#$ii prin trecerea de la metodologia de proiectare bazat# pescheme electice "i simulare la metodologia bazat# pe descriere "i sintez#, "i s#

permit# posibilitatea utiliz#rii ambelor strategii la fiecare nivel de abstractizare.


10/47


Schema-bloc a unui sistem de sintez# generic este prezentat# în Figura 5. Siste-mul dispune de un Mediu de conceptualizare pentru a permite interactivitatea "i contro-labilitatea. Completitudinea sistemului este dat# de faptul c# acesta permite sinteza lanivel de sistem, de circuit, la nivel logic "i fizic. Extensibilitatea este asigurat# prinexisten$a a dou# baze de date. Baza de date a componentelor ( BDC ) permite ad#ugarea aunor noi componente pentru sintez#, în timp ce Baza de date a sistemului ( BDS ) permitead#ugarea unor noi stiluri de proiectare, prin faptul c# utilizeaz# o reprezentare cuprin-z#toare a proiectului "i faciliteaz# ad#ugarea unor noi algoritmi, punând la dispozi$iediferite tipuri de informa$ii pentru diferite nivele de abstractizare.

Sistemul permite utilizarea atât a metodologiei de proiectare bazate pe schemeelectrice "i simulare, cât "i a metodologiei bazate pe descriere "i sintez#. Prima meto-

dologie poate fi utilizat# prin realizarea schemelor cu ajutorul Mediului de conceptualizare "i simularea acesteia printr-una din simulatoarele Setului de simulare. A doua me-todologie poate fi utilizat# prin reprezentarea descrierii proiectului într-una sau maimulte forme intermediare "i sinteza cu utilitarele corespunz#toare de sintez#.

Se utilizeaz# diferite Forme intermediare pentru diferite aspecte de proiectare laacela"i nivel sau pentru acela"i aspect de proiectare la diferite nivele ale proiect#rii. Înlocul mai multor forme intermediare, s-ar putea defini un limbaj universal pentru toatenivelele "i stilurile de proiectare, dar un asemenea limbaj ar fi greoi "i ineficient. Ar finecesar un timp considerabil pentru a se ajunge la un standard pentru un asemenea lim-

baj. Se poate utiliza în schimb un limbaj standard de simulare, cum este limbajul VHDL.

Totu"i, un asemenea limbaj dispune mai ales de construc$ii necesare pentru simulare "i

Figura 5. Un sistem de sintez# generic.


11/47

Sistem CAD pentru sinteza sistemelor numerice %0

nu pentru sintez#. Mai mult, construc$iile acestui limbaj nu sunt adecvate pentru mode-larea diferitelor stiluri de proiectare, "i proiectan$ii nu sunt interesa$i de obicei în descri-erea proiectelor în acest limbaj, ci în determinarea valorilor de ie"ire pentru un set devectori de test "i în observarea rela$iilor în timp între semnalele selectate. Deci, un raport

de ie"ire generat de un simulator va fi satisf #c#tor indiferent de sursa intr #rii pentru si-mulator, fie un alt limbaj, fie o alt# form# de specificare a proiectului. De aceea, se

poate utiliza orice form# intermediar # pentru reprezentarea proiectului, cât timp exist#un generator al codului de simulare pentru translatarea formei intermediare într-o des-criere care se poate utiliza pentru simulare. Generatoarele codului de simulare din Fi-gura 5 sunt utilizate în acest scop.

Generatoarele de cod se pot utiliza de asemenea în cadrul metodologiei bazate pescheme "i simulare. De exemplu, o schem# poate fi considerat# ca o form# intermediar #care este translatat# de c#tre un generator al listelor de conexiuni într-o descriere utili-zabil# pentru simulare. Similar, formele intermediare de la nivelul logic, secven$ial, RT

"i sistem pot fi translatate în limbajul VHDL sau într-un alt limbaj de simulare. Formeleintermediare pot fi utilizate pentru sinteza interactiv#, pentru a realiza parti$ionarea, pla-nificarea "i asignarea manual#, ca "i transformarea "i verificarea proiectelor "i a descrie-rilor. Ele se pot utiliza de asemenea pentru estimarea calit#$ii proiectelor "i pentruestimarea efectelor modific#rii proiectelor asupra calit#$ii acestora.

22..22.. SSiinntteezzaa llaa nniivveell ddee ssiisstteemm

Un sistem poate fi descris printr-un set de procese comunicante controlate de

evenimente externe sau interne. Scopul sintezei la nivel de sistem este de a reprezenta oasemenea descriere a sistemului, de a evalua anumite caracteristici de baz# ale acesteia,"i de a parti$iona descrierea într-o ierarhie de descrieri care reflect# entit#$i fizice ca

pl#ci, module multi-cip, cipuri sau macrocelule utilizate pentru fabrica$ia sistemului.

Parti$ionarea descrierii unui sistem în entit#$i pentru care se poate realiza fabri-ca$ia sau sinteza este o sarcin# dificil#, în special dac# anumite entit#$i pot fi asignateunor componente standard (ca procesoare "i memorii), în timp ce altele nu sunt definitecomplet sau sunt definite la un nivel de abstractizare diferit. Limbajul de descriere alsistemului trebuie s# aib# posibilitatea specific#rii ierarhiei func$ionale "i structurale, s#dispun# de construc$ii abstracte de comunica$ie "i de un stil de descriere care este p#strat

pe parcursul mai multor nivele de parti$ionare. Limbajul trebuie s# permit# reprezenta-rea informa$iilor structurale par $iale, ca cipuri, porturi "i conexiuni. Trebuie s# permit#de asemenea specificarea par $ial# a sistemului, astfel încât sinteza s# poat# fi realizat#f #r # cunoa"terea detaliat# a unor por $iuni ale sistemului. Descrierea trebuie s# fie exe-cutabil# pentru a permite verificarea înainte "i dup# parti$ionare.

O metodologie tipic# pentru sinteza la nivel de sistem este prezentat# în Figura6. Descrierea de intrare este compilat# într-o Reprezentare a sistemului ( RS ), utilizat# detoate celelalte utilitare. Codul pentru simulare este generat de asemenea din aceast# re-

prezentare. Descrierea sistemului este parti$ionat# în subdescrieri care se vor executasecven$ial pe anumite circuite sau vor exista concurent în acela"i pachet. Dou# tipuri deobiecte sunt supuse parti$ion#rii: structurile de date "i descrierile func$ionale.


12/47

Sistem CAD pentru sinteza sistemelor numerice %%

Structurile de date cuprind variabile globale "i locale, tablouri, liste, cozi "i înre-gistr #ri. Acestea sunt implementate de obici prin componente de memorie. De aceea,trebuie grupate structurile de date care pot fi implementate printr-o singur # memorie, iar apoi trebuie parti$ionate acele memorii între cipuri sau alte pachete fizice.

Similar, descrierile func$ionale pot fi parti$ionate între diferite unit#$i de execu$iesau procesoare. Se poate presupune c# descrierea de intrare este bazat# pe st#ri, tranzi$ii-le între st#ri fiind determinate de evenimente, în fiecare stare fiind executate anumite

prelucr #ri, cuprinzând instruc$iuni de asignare, func$ii, proceduri sau procese. Parti$io-narea descrierilor func$ionale poate fi considerat# ca parti$ionare a st#rilor. Dac# descrie-

rea nu este bazat# pe st#ri, aceasta se poate diviza în por $iuni mai mici prin parti$ionareaîntre limitele blocurilor, proceselor "i a procedurilor. St#rile ale c#ror descrieri func$io-nale sunt executate secven$ial pot fi grupate pentru execu$ie pe o singur # arhitectur # detip ASFD, care poate fi apoi parti$ionat# între pachetele fizice.

Pentru a evalua calitatea fiec#rei parti$ii trebuie s# se estimeze perioada ceasului, performan$ele, spa$iul ocupat, puterea consumat#, costurile de testare "i încapsulare.Deoarece timpul total de execu$ie depinde de datele de intrare, estimarea perioadei cea-sului "i a performan$elor pe baza descrierii func$ionale este dificil#, deoarece datele nusunt disponibile înaintea execu$iei. Algoritmii de estimare trebuie s# utilizeze tehnici

probabilistice pentru a defini num#rul de parcurgeri ale fiec#rei c#i din descriere.

Figura 6. Metodologia de sintez# la nivel de sis-tem.


13/47


Dac# pentru implementare se vor utiliza componente standard, ca procesoare saucontrolere, opera$ia de parti$ionare devine foarte dificil#. Algoritmii de parti$ionare tre-

buie s# fie capabili s# recunoasc# p#r $i ale descrierii care pot fi implementate prin componente standard. Astfel, parti$ionarea trebuie s# fie precedat# de o preparti$ionare a

descrierii în p#r $i care sunt executabile sau neexecutabile pe anumite componente stan-dard date.

Orice parti$ionare poate modifica unele caracteristici ale sistemului, în particular performan$ele. De exemplu, mutarea loca$iilor alocate pentru o structur # de date de la uncip care utilizeaz# acea structur # de date într-un alt cip poate satisface cerin$ele de în-capsulare, dar poate determina cre"terea timpului de acces la acea structur # de date. Deasemenea, unirea mai multor structuri de date poate necesita modificarea protocolului deacces la acestea. Similar, unirea structurilor de date accesate de mai multe st#ri concu-rente necesit# introducerea unor mecanisme de arbitraj. De aceea, sinteza interfe$elor "ia logicii de arbitraj trebuie s# fie realizat# dup# fiecare itera$ie a parti$ion#rii.

Dup# ce descrierea sistemului este parti$ionat# în entit#$i care satisfac restric$iilefizice, canalele de comunica$ie "i protocoalele lor pot fi unite pentru a minimiza num#-rul de porturi din fiecare parti$ie. Unirea canalelor poate fi considerat# ca o multiplexarea mesajelor prin aceea"i magistral#. Evident, aceast# multiplexare este posibil# numaidac# dou# mesaje nu trebuie transmise concurent.

Sinteza la nivel de sistem are ca rezultat o structur # de subdescrieri func$ionale,fiecare din acestea definind un pachet sau modul a c#rui sintez# trebuie realizat# ulteri-or. Aceast# descriere func$ional# a fiec#rui modul poate fi utilizat# ca intrare pentru unutilitar de sintez# la nivel de cip, sau poate fi descompus# în continuare în cicluri deceas prin planificarea opera$iilor "i transmis# direct utilitarelor de sintez# la nivel RT.

22..33.. SSiinntteezzaa llaa nniivveell ddee cciipp

Sinteza la nivel de sistem produce o descriere la nivel de cip sub forma unor subdescrieri func$ionale care pot fi implementate prin arhitecturi ASFD care comunic#între ele. Aceste automate pot fi utilizate pentru a descrie procesoare, memorii cache,cozi, memorii, circuite de arbitraj a magistralelor "i interfe$e. Sinteza la nivel de cip areca scop transformarea unei descrieri func$ionale ASFD într-o descriere structural# careutilizeaz# componente RT. Un sistem generic de sintez# la nivel de cip este prezentat înFigura 7.

Sistemul de sintez# const# dintr-un compilator care genereaz# o reprezentare in-tern#, un set de utilitare pentru sinteza de nivel înalt, o baz# de date a componentelor RT, un utilitar pentru adaptarea tehnologic# "i un utilitar pentru optimizareamicroarhitecturii. Descrierea func$ional# de intrare este compilat# într-o reprezentareintern# (de exemplu, un graf al fluxului de control "i de date), care pune în eviden$# de-

penden$ele de control "i de date necesare pentru planificare "i alocare. Mai multe utilita-re ale sintezei de nivel înalt adnoteaz# aceast# reprezentare cu informa$ii necesare pentrusinteza logic# "i secven$ial#.

Utilitarul de Planificare asigneaz# opera$ii st#rilor de control. Utilitarele de Alo-care a unit !" ilor func " ionale, de memorie "i de interconectare aloc# operatori unit#$ilor func$ionale, variabile scalare "i tablouri registrelor "i memoriilor, "i conexiuni magis-


14/47


tralelor. Utilitarul de Grupare a memoriilor une"te registrele în tablouri de registre, "itablourile de registre în memorii. Acest utilitar determin# de asemenea loca$ia fiec#reivariabile în cadrul memoriei grupate. Selectorul de module selecteaz# componentele RTcare vor fi utilizate pentru implementare. Acest utilitar poate parti$iona graful fluxului

de control "i de date "i poate executa o amplasare preliminar # pentru a determina combina$ia de componente RT care vor satisface restric$iile date.

Baza de date a componentelor ( BDC ) memoreaz# componentele RT care vor fiutilizate pentru sintez# "i furnizeaz# informa$ii despre caracteristicile acestora. Utilitarulde Adaptare tehnologic! mapeaz# componentele generice din descrierea pentru care serealizeaz# sinteza la instan$ieri ale componentelor memorate în BDC . C#ile critice esti-mate "i întârzierile acestor c#i se pot modifica dup# mapare. Utilitarul de Optimizaremicroarhitectural ! elimin# unele c#i critice "i reduce întârzierile prin redistribuirea

Figura 7. Sinteza la nivel de cip.


15/47


16/47


22..44.. SSiinntteezzaa llooggiicc!! $$ii sseeccvveenn""iiaall!!

Ie"irea sintezei de nivel înalt este o descriere structural# în care fiecare compo-nent# este un automat ASFD descris printr-o tabel# de st#ri, o component# a c#ii de datedescris# prin ecua$ii booleene, o component# de interfa$# descris# prin diagrame de timpsau forme de und#, sau o memorie specificat# prin dimensiune, num#rul "i tipul portu-rilor, "i protocolul de acces. Fiecare din aceste componente necesit# tehnici diferite desintez#, dup# cum se indic# în Figura 8 pentru un sistem ipotetic de sintez# logic#.

O arhitectur # ASFD const# dintr-o cale de date "i o unitate de control a c#reifunc$ionare poate fi modelat# ca un automat determinist cu st#ri finite. Un asemeneaautomat con$ine un registru de stare pentru memorarea st#rii prezente "i un circuit

combina$ional pentru evaluarea st#rii urm#toare "i a func$iilor de ie"ire. Un utilitar desintez# a unit#$ii de control trebuie s# translateze o asemenea descriere într-o structur #hardware, executând minimizarea st#rilor, codificarea st#rilor, minimizarea logic# "iadaptarea tehnologic#.

Minimizarea st#rilor reduce num#rul st#rilor unui automat cu st#ri finite prineliminarea st#rilor redundante, ale c#ror func$ii pot fi executate de alte st#ri. Procedurilede minimizare a st#rilor parti$ioneaz# st#rile în clase de st#ri echivalente. Dou# st#ri si "i

s j sunt echivalente dac# nu exist# secven$# de intrare care genereaz# dou# secven$e dife-rite de ie"ire, atunci când aceasta este aplicat# automatului în st#rile si "i s j. Deoarecetoate st#rile echivalente genereaz# acelea"i ie"iri, fiecare clas# echivalent# poate fi înlo-

cuit# printr-o singur # stare. Minimizarea st#rilor este important# deoarece num#rul st#-

Figura 8. Sistem de sintez# logic#.


17/47


rilor determin# dimensiunea registrului de stare "i a logicii de control. Minimizarea st#-rilor îmbun#t#$e"te de asemenea testabilitatea automatelor cu st#ri finite, deoarece au-tomatele f #r # st#ri redundante sunt mai u"or de testat.

Codificarea st#rilor asigneaz# coduri binare st#rilor simbolice. Scopul codific#riist#rilor este de a minimiza logica necesar # pentru implementarea automatului cu st#rifinite. Pentru satisfacerea acestui scop, se poate aplica implementarea prin dou# nivelelogice sau implementarea printr-o logic# multi-nivel.

În cazul implement#rii prin dou# nivele logice, se execut# o minimizare logic#cu valori multiple (simbolic#) a logicii necodificate, prin gruparea setului de intr #ri carecorespunde fiec#rui simbol de ie"ire. Aceast# grupare stabile"te de asemenea un set derestric$ii pentru codificarea fiec#rui simbol. Simbolurile sunt codificare secven$ial utili-zând codul cu lungimea minim# care satisface toate restric$iile.

În cazul implement#rii printr-o logic# multi-nivel, procedura de codificare în-cearc# s# minimizeze costul implement#rii prin minimizarea num#rului de literale dinexpresiile booleene ale logicii st#rii urm#toare. Minimizarea num#rului de literale esterealizat# prin maximizarea num#rului "i dimensiunii subexpresiilor comune, ceea ce serealizeaz# prin asignarea codurilor similare st#rilor care genereaz# ie"iri similare.

Dup# codificarea tuturor intr #rilor, ie"irilor "i st#rilor simbolice, prin minimiza-rea logic# se reduce costul implement#rii logicii st#rii urm#toare "i a logicii de control.Diferite implement#ri necesit# concentrarea asupra unor obiective diferite. Pentru logicacu dou# nivele, obiectivul este de a se minimiza num#rul termenilor produs ale ecua$ii-lor booleene scrise sub forma sumelor de produse. Pentru logica multi-nivel, obiectivuleste de a se minimiza num#rul de literale din ecua$iile booleene prin aplicarea mai mul-tor tehnici.

Opera$ia de extragere identific# divizorii comuni din expresiile booleene care se pot utiliza pentru a reduce num#rul total de literale. Opera$ia de resubstituire testeaz#dac# o func$ie existent# este un divizor al altor func$ii. Opera$ia de asignare a fazei rea-lizeaz# alegerea între implementarea func$iei sau a complementului acesteia, în scopulminimiz#rii num#rului total de inversoare necesare pentru implementare. Opera$ia de

factorizare a por " ilor factorizeaz# ecua$ia logic# pentru fiecare poart# complex# pentrua produce o re$ea optim# pentru poarta respectiv#. Descompunerea por " ilor împarte fun-c$iile complexe în p#r $i mai simple. Prin simplificare se aplic# minimizarea cu dou# ni-vele fiec#rui nod din re$ea.

Opera$iile logice men$ionate sunt executate în ordinea specificat# într-un scena-

riu, eficien$a acestora depinzând în mare m#sur # de caracteristicile logicii de intrare. In-terac$iunea utilizatorului "i un scenariu cu autoadaptare pot fi utilizate pentru a cre"tecalitatea minimiz#rii.

În timp ce logica cu dou# nivele este implementat# de obicei printr-un circuitPLA, logica multi-nivel poate fi implementat# prin biblioteci de celule standard. Adap-tarea tehnologic# transform# o re$ea logic# independent# de tehnologie generat# prinminimizarea logic# într-o list# de conexiuni a unor celule standard aflate într-o anumit#

bibliotec#. Dintre numeroasele metode care pot fi aplicate pentru adaptarea tehnologic#se aminte"te parti$ionarea re$elei logice într-o p#dure de arbori, "i determinarea pentrufiecare arbore a unei acoperiri prin celule de bibliotec#, cu un cost minim.


18/47


Deoarece se presupune c# fiecare proiect poate fi descris printr-un set de procesecomunicante "i poate fi implementat printr-un set de automate ASFD care comunic# în-tre ele, proiectarea logicii de comunica$ie este o parte necesar # a sintezei. Circuitul deinterfa$# poate fi implementat ca o parte integrant# a fiec#rui automat ASFD, sau ca un

automat independent. Dac# un protocol de comunica$ie este o parte a descrierii ASFD,fiecare r #spuns la un semnal de protocol necesit# un num#r întreg de st#ri. De exemplu,

protocolul de cerere-confirmare se poate implementa utilizând o stare de a"teptare "i ostare de confirmare. Activarea semnalului de cerere determin# ie"irea automatului dinstarea de a"teptare "i trecerea acestuia în starea de confirmare, în care este activat sem-nalul de confirmare. La dezactivarea cererii, automatul va ie"i din starea de confirmare.Pe de alt# parte, dac# trebuie s# se realizeze interfa$area între dou# automate ASFDstandard cu protocoale diferite, trebuie s# se realizeze sinteza unui al treilea automat

pentru conversia între cele dou# protocoale.

Sinteza interfe$elor este dificil# din cauza lipsei limbajelor de descriere a in-

terfe$elor "i a metodelor de sintez# pentru logica combinat# secven$ial# sincron# "i asin-cron#. Protocoalele de comunica$ie sunt descrise de obicei prin diagrame de timp curestric$ii impuse de temporizare. Exist# trei tipuri de restric$ii de temporizare: de ordo-nare, de simultaneitate "i de sincronizare. O restric$ie de ordonare define"te ordinea încare apar evenimentele într-un anumit interval de timp. O restric$ie de simultaneitatedefine"te toate evenimentele care apar împreun#, iar o restric$ie de sincronizare defi-ne"te timpul de setare "i men$inere pentru logica sincron#.

O asemenea descriere trebuie convertit# într-un graf de temporizare, în care fie-care nod reprezint# un eveniment, deci o tranzi$ie logic# a unui semnal. Arcele grafuluicorespund restric$iilor de temporizare care exist# între dou# evenimente. Aceste grafuri

pot fi construite în mod direct pe baza diagramelor de timp. Sinteza interfe$elor const#în implementarea grafului de temporizare cu un num#r minim de latch-uri "i bistabile "iminimizarea logicii pentru setarea "i resetarea acestora. Logica de interfa$# poate fi sin-cron# sau asincron#.

Sinteza memoriei genereaz# o descriere a memoriei pentru anumite cerin$e date,ca num#rul de cuvinte, num#rul de bi$i pe cuvânt, num#rul de porturi, tipul porturilor (citire, scriere, sau citire/scriere), rata de transfer, protocolul de acces, "i restric$iile detemporizare. Sinteza memoriilor poate fi complex# pentru anumite cerin$e. De exemplu,

proiectarea unei memorii cu 4 porturi utilizând numai circuite de memorie cu un singur port poate fi simpl# dac# datele pot fi parti$ionate în patru grupuri, fiecare grup fiind ac-cesat numai printr-un port (de exemplu, Memorie1 din Figura 2(c)). Dac# îns# acelea"idate sunt accesate prin dou# porturi diferite, sau dac# dou# porturi acceseaz# datele dinacela"i circuit de memorie cu un singur port, trebuie s# se adauge o logic# de rezolvare aconflictelor. Aceast# logic# are ca rezultat cre"terea timpului de acces al memoriei.Deci, scopul utilitarului de grupare a memoriilor este de a parti$iona datele "i de a asignafiecare parti$ie unei memorii astfel încât num#rul de conflicte "i costul logicii de genera-re a adreselor s# fie minimizat.


19/47


22..55.. PPrrooiieeccttaarreeaa f f iizziicc!!

Metodologia de proiectare fizic# prezentat# în Figura 9 porne"te de la o list# deconexiuni RT care con$ine trei tipuri de componente, acestea fiind caracterizate prinnum#rul dimensiunilor în care ele prezint# o regularitate. Componentele cu dimensiunilecele mai mari sunt tablourile bidimensionale, ca memoriile, circuitele de înmul$ire "igrupurile de registre. Componentele cu dimensiuni medii sunt tablourile unidimensio-nale ca registrele, num#r #toarele, unit#$ile aritmetice "i logice, driverele de magistral# "iunit#$ile logice. Por $ile logice, latch-urile "i bistabilele sunt componente de dimensiunimici, f #r # o regularitate.

Fiecare grup de componente are un stil de amplasare diferit. Componentele bi-dimensionale au de obicei dimensiuni mari "i constituie module separate. Componentele

unidimensionale pot fi grupate împreun# sub forma unei stive (Figura #0(a)), datelefiind rutate într-o direc$ie "i semnalele de control în cealalt# direc$ie, pe straturi metalicediferite. Ca un stil arhitectural eficient de amplasare, arhitectura de tip stiv# reduce sem-nificativ spa$iul necesar "i lungimea conexiunilor. Totu"i, aceast# amplasare poate aveaca rezultat o pierdere semnificativ# de spa$iu datorit# componentelor cu dimensiuni ine-gale. De exemplu, poate exista o unitate aritmetic# "i logic# de %6 bi$i "i un num#r #tor de 4 bi$i, amplasate al#turat în stiv#. În asemenea cazuri, spa$iul liber trebuie umplut

prin amplasarea por $ilor "i a bistabilelor, utilizând stilul de amplasare standard al celu-lelor, în care celulele sunt amplasate pe linii "i sunt conectate prin canale de rutare întrelinii. De exemplu, spa$iul liber de lâng# stiva din Figura #0(a) este divizat în trei zone

Figura 9. Metodologie de proiectare fizic#.


20/47


dreptunghiulare. Dou# dintre aceste sunt umplute cu logica de control necesar # compo-nentelor din stiv#, dar a treia este umplut# cu componente care nu au leg#tur # cu stiva.

Dup# parti$ionarea componentelor în trei grupuri pe baza dimensiunii acestora,ele sunt parti$ionate în continuare pentru a satisface restric$iile spa$iale impuse de planulde amplasare selectat (Figura #0(b)). Por $ile "i bistabilele sunt parti$ionate pentru a um-

ple spa$iile dintre modulele de dimensiuni mari. Spa$iul disponibil poate avea formaunui poligon arbitrar, "i astfel trebuie parti$ionat la rândul s#u în zone dreptunghiulare,cu capacit#$i estimate ale tranzistoarelor. Por $ile "i bistabilele sunt parti$ionate apoi îngrupuri pentru care nu se dep#"esc capacit#$ile tranzistoarelor zonelor care le sunt asig-nate. Similar, componentele unidimensionale pot fi parti$ionate în mai multe stive.

Parti$ionarea "i amplasarea trebuie executate în mod iterativ, deoarece fiecare parti$ionare influen$eaz# amplasarea, "i invers, fiecare plan de amplasare influen$eaz# parti$ionarea. Dup# terminarea amplas#rii, trebuie s# se realizeze sinteza descrierii am-

plas#rii pentru fiecare component#, utilizând una din cele trei arhitecturi de amplasare:tablou, stiv#, sau celule standard. Opera$ia final# din cadrul proiect#rii fizice este rutareacomponentelor instan$iate.

22..66.. BBaazzaa ddee ddaattee aa ssiisstteemmuulluuii

În mod tradi$ional, sistemele de sintez# sunt elaborate ca o colec$ie de utilitare de proiectare de sine st#t#toare. În cazul acestor sisteme, exist# diferen$e în ceea ce prive"tereprezentarea datelor, "i formatele de intrare "i de ie"ire. A doua genera$ie a unui aseme-

nea sistem de sintez# poate fi dezvoltat# fie ca un sistem puternic integrat, fie ca un sis-

Figura #0. Planuri de amplasare generice.


21/47


tem integrat într-o m#sur # mai mic#. Un sistem puternic integrat utilizeaz# o repre-zentare comun# a datelor, fiecare utilitar utilizând acelea"i proceduri pentru accesul ladate. Un asemenea sistem este foarte eficient, dar extrem de rigid, deoarece o modificarea formatului influen$eaz# toate utilitarele componente. Un sistem integrat într-o m#sur #

mai mic# separ # datele de utilitare. Datele sunt memorate într-o baz# de date "i fiecareutilitar face acces numai la informa$iile de care are nevoie, utilizând o reprezentare pro-

prie pentru prelucrarea informa$iilor respective.

O alt# motiva$ie pentru bazele de date este existen$a unor versiuni diferite aleaceluia"i proiect în timpul explor #rii spa$iului de proiectare. În multe sisteme, proiec-tan$ii sunt cei care gestioneaz# ierarhia de proiectare, reviziile "i configura$iile acesteia,

de"i aceste sarcini pot fi asignate bazei de date. O baz# de date poate memora "i gestiona

Figura ##. Model al datelor de proiectare.


22/47


23/47


Verificarea consisten$ei este executat# la dou# nivele diferite. În primul rând,utilitarul de Verificare a consisten " ei testeaz# dac# utilitarele sunt apelate în ordinea co-respunz#toare "i dac# datele solicitate de fiecare utilitar sunt disponibile în baza de date.În al doilea rând, verific# dac# datele noi ad#ugate sunt consistente cu datele originale.

De exemplu, asignarea operatorilor la unit#$ile func$ionale nu trebuie s# modifice num#-rul pa"ilor de control, "i o modificare a num#rului pa"ilor de control nu trebuie s# modi-fice func$ionarea ini$ial# specificat#. Utilitarul de Evaluare a calit !" ii proiectului punela dispozi$ie indicatori de calitate sub forma unor atribute în graful entit#$ilor de proiec-tare dup# fiecare actualizare, astfel încât diferite versiuni ale proiectului pot fi reg#site

pe baza unui indicator de calitate sau a unei combina$ii a unor asemenea indicatori.

22..77.. BBaazzaa ddee ddaattee aa ccoommppoonneenntteelloorr

Utilitarele de sintez# func$ional# genereaz# un proiect microarhitectural din des-crieri func$ionale sau descrieri la nivelul transferurilor între registre. Microarhitecturagenerat# const# din componente RT ca unit#$i aritmetice "i logice, circuite de înmul$ire,num#r #toare, decodificatoare "i registre. Spre deosebire de componentele logice de baz#,componentele RT au diferite op$iuni care pot fi parametrizate. Unul din parametri estedimensiunea componentei, ceea ce indic# num#rul de bi$i. Al$i parametri sunt lega$i deaspectele func$ionale sau propriet#$ile electrice "i geometrice ale componentei. Deexemplu, num#r #toarele pot avea op$iuni pentru incrementare sau decrementare, "i fun-c$ii de înc#rcare, setare "i resetare. De asemenea, fiecare component# poate avea întârzi-eri diferite "i fiecare pin de ie"ire poate fi înc#rcat în mod diferit. În plus, fiecarecomponent# poate avea mai multe op$iuni diferite pentru amplasare, ca "i pentru pozi$i-

onarea porturilor de I/E în cadrul modulului.

Figura #2. Arhitectura bazei de date a sistemului.


24/47


Baza de date a componentelor ( BDC ) genereaz# componente care satisfac cerin-$ele specifice de proiectare "i furnizeaz# informa$ii despre caracteristicile electrice "i deamplasare ale componentelor.

Deci, BDC trebuie s# pun# la dispozi$ie dou# tipuri de informa$ii: o estimare acaracteristicilor componentelor pentru fiecare tip de component# disponibil#, "i o des-criere a instan$ierii componentelor pentru a fi inclus# în descrierile la nivel RT, logic "ila nivel de cip. Estim#rile caracteristicilor componentelor sunt utilizate de utilitarelesintezei de nivel înalt pentru planificare "i alocare, "i de utilitarele proiect#rii fizice pen-tru planul de amplasare. Descrierile componentelor sunt utilizate la trei nivele diferite.În primul rând, numele componentelor "i numele pinilor acestora sunt utilizate în des-crierile RT generate de utilitarele sintezei de nivel înalt. În al doilea rând, descrierile dela nivelul logic sunt utilizate în timpul sintezei logice "i a optimiz#rii. În al treilea rând,descrierile la nivel de cip sunt utilizate în timpul asambl#rii planurilor de amplasare. În

plus fa$# de descrierile componentelor, BDC trebuie s# furnizeze trei modele diferite

pentru simulare la nivel RT, la nivel logic "i la nivel de cip.

Exist# pu$ine lucr #ri legate de generarea componentelor "i bazele de date alecomponentelor pentru sinteza de nivel înalt. Baza de date generic# prezentat# în Figura#3 const# din dou# p#r $i: Serverul de componente "i Serverul de cuno #tin " e. Serverul decomponente furnizeaz# estim#ri "i descrieri la nivel RT, la nivel logic "i la nivel de cip,atunci când indic# r #spunsuri la întreb#ri legate de instan$ierile componentelor. Serverul de cuno #tin " e permite ad#ugarea unor noi instan$ieri de componente, a generatoarelor de

Figura #3. Baza de date a componentelor.


25/47


componente sau a utilitarelor de optimizare a componentelor. Acest server este utilizat pentru extinderea bibliotecilor de componente disponibile.

O component# poate fi memorat# ca o instan$iere atunci când este proiectat# ma-nual pentru o anumit# implementare particular #, sau ca o descriere parametrizat# pentruo clas# de instan$ieri ale componentelor. Generatoarele de componente sunt seturi deutilitare care genereaz# instan$ieri de componente din descrieri parametrizate. Utilitarelede optimizare la nivel logic sau la nivel de cip pot fi utilizate ca o parte a procesului degenerare a componentelor. Toate instan$ierile proiectate manual sau generate sunt p#s-trate în Memoria de componente pentru a fi utilizate de un anumit proiectant sau unanumit utilitar de sintez#.

BDC este o component# critic# a metodologiei sintezei de nivel înalt, deoareceasigur # o separare clar # a sintezei la nivel de sistem "i la nivel de cip de sinteza logic# "ifizic#. Existen$a unei BDC permite ca proiectan$ii s# se concentreze asupra proiect#riisistemului, f #r # implicarea în proiectarea logic# sau fizic#. Permite de asemenea dez-

voltarea rapid# a utilitarelor sintezei de nivel înalt, punând la dispozi$ie interfe$e stan-dard pentru sinteza componentelor "i izolarea fa$# de modific#rile tehnologiilor defabrica$ie.

22..88.. MMeeddiiuull ddee ccoonncceeppttuuaalliizzaarree

Automatizarea complet# a procesului de proiectare pornind de la nivele maiînalte de descriere este un scop important, de"i nu este posibil# imediat. Chiar dac# toateutilitarele sintezei de nivel înalt ar fi disponibile în momentul de fa$#, ar fi necesar ca

proiectan$ii s# devin# familiariza$i cu utilizarea lor. De asemenea, este necesar un timp pentru ca algoritmii de sintez# s# asigure o calitate uniform# pentru diferite stiluri de proiectare. Astfel, este necesar s# se asigure un mediu în care proiectan$ii pot verificadeciziile de proiectare "i pot modifica manual algoritmii de sintez#. Chiar dac#algoritmii sunt performan$i, proiectan$ii trebuie s# aib# posibilitatea de a lua decizii denivel înalt, ca de exemplu selec$ia stilului de proiectare, a arhitecturii, a topologiei, acerin$elor "i a restric$iilor pentru componente. Deci, un mediu de conceptualizare trebuies# permit# controlul deciziilor de proiectare "i a strategiei de proiectare în toate etapele

procesului de proiectare, ceea ce necesit# ca mediul s# pun# la dispozi$ie indicatoriutilizabili de calitate la fiecare nivel de abstractizare.

Mediul de conceptualizare este strâns legat de baza de date a sistemului "i bazade date a componentelor. Aceste baze de date memoreaz# toate versiunile datelor de proiectare pentru perioade lungi de timp, în timp ce mediul de conceptualizare face ac-ces numai la por $iuni reduse ale datelor pentru modificare în timpul unor perioade scurtede timp.

Mediul de conceptualizare const# din cinci p#r $i: gestiunea datelor "i a proiectu-lui, vizualizarea "i editarea datelor, estimarea indicatorilor de calitate, algoritmii de sin-tez# "i verificarea consisten$ei proiect#rii. Calitatea proiectului este estimat# pe bazadatelor proiectului par $ial sau complet. Indicatorii de calitate pot fi calcula$i relativ sim-

plu pe baza proiectului final, dar trebuie s# se utilizeze tehnici diferite de estimare la di-ferite nivele de abstractizare. Algoritmii de sintez# pot fi aplica$i întregului proiect saunumai unor p#r $i ale proiectului. Proiectantul trebuie s# poat# împ#r $i sinteza în etape "i


26/47


s# aplice algoritmii fiec#rei etape separat. Prin verificarea consisten$ei proiect#rii se asi-gur # faptul c# modific#rile manuale ale proiectului nu produc nici o modificare în des-crierea func$ional#. De exemplu, dac# un transfer între registre de forma y ← a+b+c,care necesit# dou# sumatoare, este împ#r $it de proiectant în dou# transferuri între regis-

tre, y ← a+b, y ← y+c, care necesit# un singur sumator, dar dou# st#ri, prin verificareaconsisten$ei trebuie s# se asigure c# cele dou# transferuri între registre genereaz# acela"irezultat ca "i transferul original.

Proiectul complet al unui cip poate fi reprezentat sub dou# forme: o tabel# func-$ional# de st#ri "i un plan de amplasare. Fiecare descriere func$ional# exprimat# subforma instruc$iunilor "if", "case" "i "loop" poate fi parti$ionat# dup# aceste instruc$iuni.De exemplu, testul condi$ional dintr-o instruc$iune "if" poate fi asignat unei st#ri, coduldin fiecare ramur # fiind asignat câte unei st#ri. Dac# exist# mai multe instruc$iuni deasignare a unor variabile în fiecare ramur #, ele pot fi divizate în continuare manual sauautomat în mai multe st#ri. De exemplu, o descriere func$ional# sub forma unei organi-

grame este prezentat# în Figura #4(a). Tabela func$ional# de st#ri care corespunde

Figura #4. Descriere func$ional#: (a) organigram#; (b) tabel# func$ional# dest#ri.


27/47


acestei organigrame este prezentat# în Figura #4(b). De notat c# nodul de unire din Fi-gura #4(a) nu trebuie s# ocupe neap#rat o stare complet#, dar astfel descrierea este mailizibil# "i se permite verificarea modific#rilor. În proiectul final, o asemenea descriereeste compactat# în tabela de st#ri alocat#. În$elegerea proiectului dintr-o tabel# de st#ri

compactat# "i nestructurat# este îns# dificil#.

A doua reprezentare este planul de amplasare al proiectului, care indic# pozi$ia "iconexiunile fiec#rei componente (Figura #5). Aceast# reprezentare este ierarhic#, deoa-rece poate fi de asemenea reprezentat planul de amplasare al fiec#rei componente, ca deexemplu calea de date. Pentru fiecare component# se reprezint# porturile acestuia. Co-

nexiunile dintre porturi pot fi reprezentate fie ca linii drepte între porturi, fie ca "i co-nexiuni rutate între porturi.

Alte reprezent#ri faciliteaz# selec$ia modulelor, amplasarea, alocarea "i planifi-carea. Selec " ia modulelor este realizat# prin parcurgerea componentelor disponibile în

BDC , pe categorii specifice ca de exemplu clasa (combina$ionale, secven$iale), func$io-narea (UAL, comparatoare, num#r #toare), num#rul maxim de bi$i "i stilul (de exemplu,cu transport succesiv sau anticipat). Informa$iile fizice despre fiecare component# suntafi"ate dup# ce au fost specificate categoriile precedente.

Amplasarea este realizat# pe baza planului de amplasare "i cu ajutorul unui edi-tor. Proiectan$ii pot ad#uga, "terge, roti "i repozi$iona diferite module. De asemenea, se

pot pozi$iona porturile modulelor. Similar, proiectan$ii pot ad#uga sau "terge conexiuni,

Figura #5. Plan de amplasare.


28/47


sau le pot pozi$iona în cadrul canalelor din jurul modulelor. Calitatea amplas#rii, subforma unor indicatori ca în#l$imea, l#$imea, spa$iul de rutare, densitatea tranzistoarelor,lungimea conexiunilor "i frecven$a ceasului, este afi"at# pentru fiecare amplasare.

Alocarea este executat# prin selec$ia unit#$ilor "i asignarea obiectelor func$ionale(de exemplu, variabile "i opera$ii) la componentele RT, "i a conexiunilor la multiplexoa-re "i magistrale. Aceast# asignare poate fi realizat# utilizând o matrice, în care apar pede o parte obiectele func$ionale, iar pe de alt# parte componentele. Calitatea unei asig-n#ri este estimat# prin indicatori ca gradul de utilizare al componentelor, întârzierile dela registru la registru "i spa$iul de rutare.

Planificarea este realizat# prin reparti$ionarea descrierii func$ionale ini$iale întabela func$ional# de st#ri. Proiectantul poate ad#uga sau "terge st#ri, poate diviza sauconcatena expresii, condi$ii "i bucle, sau poate realoca asign#rile de la o stare la alta.Calitatea planific#rii este estimat# prin indicatori ca num#rul de componente necesare,suma spa$iului necesar pentru toate componentele, întârzierile de la registru la registru,

num#rul de st#ri, "i timpul total de execu$ie.Pentru a se permite o estimare rapid# a calit#$ii, descrierea func$ional# "i planu-

rile de amplasare sunt legate printr-o structur # de date comun#, astfel încât modific#riledin cadrul unei reprezent#ri sunt propagate în cealalt# reprezentare. Uneori propagareaunei modific#ri nu este posibil# în totalitate, "i ambele structuri trebuie actualizate. Deexemplu, dac# dou# opera$ii de adunare sunt planificate în acela"i pas de control "iexist# un singur sumator, aceast# modificare va genera un nou proiect, cu un sumator suplimentar, neconectat la nici o alt# component#. Acest sumator trebuie conectat ma-nual pentru ca descrierea func$ional# s# fie corect#.

Mediul de conceptualizare permite utilizarea mai multor metodologii diferite.

Proiectantul trebuie s# aib# posibilitatea iter #rii unei anumite opera$ii ori de câte ori estenecesar pentru a satisface cerin$ele. Figura #6 prezint# câteva scenarii posibile. Proiec-tantul poate porni de la o reprezentare a unei descrieri, care va fi parti$ionat# în por $iunimai mici. Deoarece func$ionarea este specificat# printr-o tabel# de st#ri, descrierea areîntotdeauna o planificare ini$ial#. Dup# selec$ia componentelor "i asignare, dac# deexemplu planificarea violeaz# anumite restric$ii de proiectare, proiectantul poate efectuao replanificare. Dup# ce planificarea ini$ial# devine satisf #c#toare, proiectantul poatevizualiza BDC pentru a identifica componentele de baz# pentru proiectul final. Celelaltecomponente pot fi asignate ulterior, fie manual, fie automat. Proiectantul poate efectua oasignare prealabil# a unor obiecte func$ionale importante la componentele selectate,

înaintea execut#rii aloc#rii complete.Dup# selec$ia componentelor, proiectantul poate efectua amplasarea. Deoarece

componentele de baz# ocup# de obicei cea mai mare parte a spa$iului, un plan de ampla-sare disponibil din fazele ini$iale poate cre"te viteza de explorare a spa$iului de proiecta-re. Proiectantul poate specifica interconexiuni de baz#, ca magistralele de date "i deadrese.

Dup# amplasare, proiectantul poate reveni la planificare, deoarece restric$iile deresurse "i de temporizare sunt cunoscute mai exact. De obicei, se încearc# îmbun#t#$ireaindicatorilor de calitate prin mai multe itera$ii, pân# la atingerea unei calit#$i satisf #c#-toare. Este de a"teptat ca proiectantul s# ia cele mai multe din deciziile de nivel înalt, dar

s# efectueze sinteza manual# doar a unei por $iuni reduse a proiectului. Restul proiectului


29/47


va fi generat de c#tre utilitarele de sintez#, care nu vor afecta de obicei în mod drasticdeciziile luate de proiectant.

În concluzie, un mediu de conceptualizare permite proiectan$ilor s# execute ma-nual acelea"i opera$ii pe care le execut# proiectan$ii care lucreaz# la nivele mai înalte deabstractizare. Îns#, un asemenea mediu permite de asemenea ca proiectan$ii s# executeaceste opera$ii par $ial prin utilitarele de sintez# automat#. Pe m#sura îmbun#t#$irii algo-ritmilor pentru sinteza de nivel înalt, un num#r mai mare de opera$ii vor fi executate cuajutorul utilitarelor de sintez# automat#.

Figura #6. Scenarii posibile pentru sinteza de nivel înaltinteractiv#.


30/47


3. Rafinarea specifica"iilor

33..##.. IInnttrroodduucceerree

O specifica$ie a unui sistem const# din obiecte func " ionale ca variabile "i canale

de comunica$ie. În timpul proiect#rii sistemului, aceste obiecte func$ionale din cadrulspecifica$iilor sunt grupate într-un set de componente de sistem, ca circuite ASIC, me-morii "i magistrale. În timp ce obiectele func$ionale sunt lipsite de structur #, compo-nentele de sistem au o structur # bine definit#, ca num#rul pinilor unui cip, num#rul "idimensiunea cuvintelor unei memorii, sau num#rul liniilor unei magistrale. Actualizareaspecifica$iilor pentru reflectarea transform#rii obiectelor func$ionale în componente desistem reprezint# rafinarea specifica " iilor .

Rafinarea specifica$iilor este important# în cadrul proiect#rii din mai multe mo-tive. În primul rând, rafinarea determin# ca specifica$ia s# devin# consistent# din toate

punctele de vedere, prin actualizarea acesteia pentru a reflecta deciziile de grupare luateîn timpul parti$ion#rii sistemului. De exemplu, dac# variabilele sunt grupate pentru a fiasignate unei singure memorii, declara$iile "i referin$ele la aceste variabile trebuie actu-alizate. Rafinarea specifica$iilor va înlocui declara$iile variabilelor cu o declara$ie a unuitablou de memorie, iar referin$ele la variabilele originale vor fi actualizate pentru a seaccesa elemente de tablou. În al doilea rând, rafinarea permite ca specifica$ia s# poat# fisimulat#, permi$ând ca proiectantul s# verifice corectitudinea func$ional# a sistemuluidup# o etap# de proiectare. În fine, specifica$ia rafinat# care este generat# poate fi utili-zat# ca intrare pentru utilitarele de verificare, sintez# "i compilare care pot urma proiec-t#rii sistemului.

În continuare se va prezenta un set de opera$ii de rafinare a specifica$iilor. Întâise vor descrie opera$iile de rafinare asociate cu implementarea grupurilor de variabile "i

canale. Se vor introduce apoi mecanisme pentru rezolvarea conflictelor de acces care potapare atunci când se efectueaz# accesul concurent la variabile "i canale care au fost gru-

pate împreun# într-o memorie sau o magistral#.

33..22.. R R aaf f iinnaarreeaa ggrruupp!!rriiii vvaarriiaabbiilleelloorr

Memoria c#reia i s-a asignat un grup de variabile este modelat# în specifica$iarafinat# ca un tablou cu un num#r fix de cuvinte "i bi$i pe cuvânt. Pentru gruparea varia-

bilelor trebuie efectuate dou# opera$ii: amplasarea variabilelor în memorie "i translatarea

adreselor de memorie.


31/47


33..22..##.. AAmmppllaassaarreeaa vvaarriiaabbiilleelloorr î î nn mmeemmoorriiee

Parti$ionarea sistemului asigneaz# un grup de variabile la o memorie cu un nu-m#r fix de cuvinte "i o dimensiune a cuvântului fix#. Diferite variabile pot avea dimen-siuni diferite. Amplasarea variabilelor în memorie se refer # la asignarea bi$ilor uneivariabile la bi$ii fiec#rui cuvânt din memorie.

Amplasarea variabilelor este simpl# dac# dimensiunea variabilelor este mai mic#decât dimensiunea cuvântului de memorie sau dac# este un multiplu exact al acestei di-mensiuni. Consider #m declara$iile variabilelor din Figura #7(a), care trebuie amplasateîntr-o memorie de 8 bi$i, dup# cum se indic# în Figura #7(b). Variabilelor a "i b li seasigneaz# un cuvânt, respectiv dou# cuvinte de memorie.

Dac# dimensiunea variabilelor nu este un multiplu întreg al dimensiunii cuvân-tului, variabilele pot fi amplasate într-unul din dou# moduri. Pentru variabila de %2 bi$ic, cei 8 bi$i mai pu$in semnificativi sunt asigna$i unei adrese, iar cei 4 bi$i r #ma"i suntasigna$i urm#toarei adrese (Figura #7(b)). Variabila d este o alt# variabil# de %2 bi$i,

pentru care cei 6 bi$i mai pu$in semnificativi sunt asigna$i unei adrese, iar ceilal$i 6 suntasigna$i urm#toarei adrese. Prima variant# necesit# un multiplexor 4:% pentru scriereavariabilei c în memorie, dar necesit# conectarea a 8 drivere la magistrala de date a me-moriei, dup# cum se indic# în Figura #7(c). A doua variant# necesit# un multiplexor de6:%, dar sunt necesare numai 6 drivere de magistral# (Figura #7(d)).

Figura #7. Amplasarea variabilelor în memorie: (a) declara$ii de variabile;(b) amplasarea într-o memorie de 8 bi$i; (c) înscrierea variabilei c cu o va-

loare de %2 bi$i; (d) înscrierea variabilei d cu o valoarea de %2 bi$i.


32/47

Sistem CAD pentru sinteza sistemelor numerice 3%

33..22..22.. TTrraannssllaattaarreeaa aaddrreesseelloorr ddee mmeemmoorriiee

Asignarea adreselor la variabilele asignate la o memorie "i modificarea tuturor referin$elor la aceste variabile în cadrul specifica$iei este cunoscut# ca translatareaadreselor de memorie.

Pentru asignarea adreselor de memorie, variabilele se pot considera în orice or-dine. Num#rul cuvintelor de memorie necesare pentru fiecare variabil# se poate deter-mina prin amplasarea variabilelor în memorie. Elementelor unei variabile de tip tabloutrebuie s# li se asigneze adrese contigue în memorie.

Pentru variabile scalare, translatarea adreselor de memorie este relativ direct#.Presupunem c# o variabil# scalar # v apar $ine unui grup de variabile reprezentate de ta-

bloul Mem, iar adresa variabilei v în memoria Mem este 30. Toate referin$ele la variabila

v în cadrul specifica$iei sunt înlocuite simplu prin referin$e la Mem(30).Pentru o variabil# de tip tablou care a fost grupat# cu alte variabile, adresele care

indexeaz# variabila trebuie actualizate la rafinarea referin$elor la aceste variabile. Deexemplu, pentru o variabil# de tip tablou v(63 DOWNTO 0) asignat# adreselor de la %00la %63 în memoria Mem, trebuie considerate mai multe aspecte pentru actualizareareferin$elor la variabila v.

În primul rând, dac# variabila de tip tablou v este indexat# în totalitate prin adre-se numerice, referin$ele la aceasta sunt înlocuite în mod simplu prin referin$ele cores-

punz#toare la memoria Mem. Astfel, referin$a v(0) va fi înlocuit# prin Mem(100), iar v(36) prin Mem(136).

În al doilea rând, dac# tabloul este indexat printr-o expresie care implic# variabile, la expresia respectiv# trebuie s# se adune un offset corespunz#tor adresei de memo-rie a primului element al variabilei. De exemplu, consider #m variabila de tip tablou v,care este indexat# prin j sau k în cadrul codului din Figura #8(a). Deoarece variabilei v is-au asignat adrese începând cu %00 în memoria Mem, o referin$# v(j) va fi înlocuit# prin

Mem(j+100), iar o referin$# v(k) va fi înlocuit# prin Mem(k+100), ca în Figura #8(b).

În al treilea rând, dac# o variabil# este utilizat# pentru a indexa un singur tablou,adunarea offsetului poate fi evitat# prin ini$ializarea corespunz#toare a variabilei deadres#. De exemplu, în Figura #8(a), variabila j indexeaz# numai variabila de tip tablouv. Figura #8(c) indic# modul în care actualizarea tuturor ini$ializ#rilor variabilei j (in-clusiv a limitelor buclei for) elimin# necesitatea adun#rii offseturilor. Totu"i, aceasta nueste posibil# întotdeauna dac# variabila j indexeaz# mai multe tablouri. În acest caz, se

poate evita adunarea offsetului pentru cel pu$in o variabil# de tip tablou prin asignareaacesteia a adreselor de memorie începând cu 0.


33/47


VARIABILE j,k: INTEGER := 0;

VARIABILE v: IntArray(63 DOWNTO 0);

...

v(k) := 3;x := v(36);

v(j) := x;

...

FOR j IN 0 TO 63 LOOP

sum := sum + v(j);

END LOOP;

...

(a)

VARIABILE j,k: INTEGER := 0;

VARIABILE Mem: IntArray(255 DOWNTO 0);...

Mem(k+100) := 3;

x := Mem(136);

Mem(j+100) := x;

...


sum := sum + Mem(j+100);

END LOOP;

...

(b)

VARIABILE j: INTEGER := 100;

VARIABILE k: INTEGER := 0;

VARIABILE Mem: IntArray(255 DOWNTO 0);

...

Mem(k+100) := 3;

x := Mem(136);

Mem(j) := x;

...


sum := sum + Mem(j);

END LOOP;

...

(c)

Figura #8. Translatarea adreselor de memorie: (a) specifica$ieini$ial#; (b) specifica$ie ob$inut# prin înlocuirea expresiilor deindex din referin$ele la variabila v cu un offset; (c) specifica$ie

cu actualizarea variabilei de index j.


34/47


33..33.. R R aaf f iinnaarreeaa ccaannaalleelloorr $$ii aa mmaaggiissttrraalleelloorr

Obiectele func$ionale concurente dintr-o specifica$ie, numite de obicei procese,comunic# între ele prin mesaje transmise prin canale de comunica$ie abstracte. Pentruminimizarea costului de interconectare, canalele din sistem sunt grupate astfel încât fie-care grup de canale este implementat printr-un mediu fizic comun numit magistral#. Omagistral# const# dintr-un set de linii prin care are loc transferul datelor conform unui

protocol de magistral#. Opera$ia de generare a magistralelor "i a protocoalelor acestora pentru fiecare grup de canale este numit# rafinarea interfe " elor . Se vor descrie în conti-nuare metode pentru rafinarea interfe$elor.

33..33..##.. PPaarraammeettrriiii ccaannaalleelloorr $$ii mmaaggiissttrraalleelloorr

Pentru fiecare canal, un singur proces master ini$iaz# "i controleaz# transferuldatelor, "i unul sau mai multe procese slave r #spund la comunica$ia ini$iat# de procesulmaster. Dac# procesul master transmite (sau recep$ioneaz#) date prin canal, direc " ia aso-ciat# cu canalul este cea de scriere (sau citire). Canalele sunt de obicei unidirec$ionale,ceea ce implic# faptul c# dac# un proces cite"te "i scrie o variabil# a unui alt proces, suntnecesare canale distincte pentru fiecare direc$ie a transferului datelor.

Canalele sunt caracterizate prin patru parametri. Dimensiunea în bi"i a datelor transmise prin canal, dim(C), reprezint# num#rul de bi$i dintr-un singur mesaj transferat

prin canalul C . Dimensiunea datelor include bi$ii de adres# care pot fi necesari pentruaccesarea variabilelor de tip tablou prin canal. Num!rul de accesuri, acces(P, C), re-

prezint# num#rul de transferuri efectuate de procesul P prin canalul C , pe durata de via$#a procesului. Rata medie a canalului, rata_med(C), este rata la care datele sunttransmise prin canalul C pe durata de via$# a proceselor care comunic# prin canal. Ratala vârf a canalului, rata_vârf(C), este rata la care este transferat un singur mesaj princanalul C .

Orice implementare printr-o magistral# a unui canal sau grup de canale poate ficaracterizat# prin patru parametri. Dimensiunea magistralei, dim_bus(B), este num#rulliniilor de date ale magistralei B prin care mesajele pot fi transferate între procese. Fie-c#rei magistrale i se asociaz# un protocol care define"te secven$a exact# de opera$ii careimplementeaz# transferul mesajelor prin setul liniilor de date. Întârzierea protocolului,

prot_delay(B), este întârzierea total# a protocolului utilizat pentru un singur transfer prinmagistral#. Rata medie a magistralei, rata_med(B), este rata la care datele sunt transfe-rate prin magistral# pe întreaga durat# de via$# a sistemului. Rata la vârf a magistralei,rata_vârf(B), este rata maxim# la care datele pot fi transferate prin magistral#. Între ratala vârf a magistralei "i dimensiunea magistralei exist# urm#toarea rela$ie:

rata vârf Bbus B

prot delay B _ ( )

dim_ ( )

_ ( )= (3.%)


35/47


33..33..22.. DDeef f iinniirreeaa pprroobblleemmeeii

Fiind dat un grup de canale abstracte de comunica$ie, rafinarea interfe$elor de-termin# dimensiunea magistralei "i protocolul pentru magistrala care va implementa ca-nalele. În cadrul acestei opera$ii, exist# dou# cerin$e contradictorii. Prima este cea deminimizare a costului de interconectare între componentele de sistem care utilizeaz# omagistral# prin reducerea dimensiunii magistralei, dim_bus(B). A doua cerin$# este de ase maximiza performan$ele de comunica$ie prin magistral#, prin cre"terea ratei la vârf amagistralei, rata_vârf(B), "i în consecin$# prin cre"terea dim_bus(B).

Rafinarea interfe$elor const# din dou# opera$ii: generarea magistralei "i genera-rea protocolului. Fiind dat un set de restric$ii, generarea magistralei determin# dimen-siunea magistralei care va implementa grupul de canale. Dup# ce a fost selectat# dimen-siunea dorit# a magistralei, generarea protocolului selecteaz# "i genereaz# protocolulde comunica$ie care va implementa transferul datelor prin magistral#.

33..33..33.. GGeenneerraarreeaa mmaaggiissttrraalleeii

Un caz simplu de determinare a dimensiunii magistralei este cel în care toate ca-nalele unui grup au dimensiuni identice ale mesajelor. În acest caz, canalele sunt uniteastfel încât toate canalele din fiecare grup sunt utilizate exclusiv pentru a comunica întreacelea"i dou# procese. În consecin$#, fiecare grup de canale este implementat cu o di-mensiune a magistralei identic# cu dimensiunea fiec#rui canal.

Într-un caz mai general, procesele comunicând între ele prin canale care au fostgrupate împreun# transfer # date simultan prin mediul fizic partajat. În plus, diferite ca-nale transfer # mesaje cu dimensiuni diferite între procese. Un asemenea exemplu este

prezentat în Figura #9. Procesele P , Q, R "i S comunic# prin canalele X , Y "i Z , care aufost grupate prin parti$ionarea sistemului pentru a fi implementate printr-o singur # ma-gistral#, B. Cele trei canale transfer # date de dimensiuni diferite, de 8, %6, respectiv %2

bi$i. În plus, este necesar ca procesul P s# transfere date la procesul R în acela"i timp în

Figura #9. O magistral# tipic# format# prin unireacanalelor care transfer # date de diferite dimensiuni

între diferite procese.


36/47


care procesul Q trebuie s# transmit# date la procesul S . Se va descrie o metod# de gene-rare a magistralei pentru un asemenea caz general.

3.3.3.#. Determinarea ratei magistraleiSe consider # dou# canale, X "i Y , care transfer # mesaje de 8 bi$i, respectiv %6

bi$i, dup# cum se prezint# în Figura 20. Num#rul de bi$i asociat cu fiecare transfer demesaj este indicat deasupra mesajului. Pentru simplitate, se presupune c# cele patru in-tervale de timp indicate în figur # reprezint# transferurile de date pe duratele de via$# ale

proceselor care comunic# prin canalele X "i Y . Canalele X "i Y au ratele medii de 4 "i %2 bi$i/s, respectiv. Dac# aceste canale sunt reunite într-o singur # magistral# B, magistralatrebuie s# transmit# datele cu o rat# de cel pu$in %6 bi$i/s pentru a putea satisface ce-rin$ele pentru transferul datelor ale celor dou# canale originale.

Mesajele individuale transferate prin canale au fost etichetate în figur # pentru a putea fi asociate mai u"or cu datele transferate prin magistrala partajat#. Consider #mmesajul etichetat cu Y2 transferat la t = % s prin canalul original Y , care este transferat

prin magistrala B la t = %.5 s. În timp ce transferurile individuale de mesaje pot fi întâr-ziate datorit# conflictelor de acces la magistral#, num#rul total de bi$i transfera$i princanalele individuale înaintea unirii canalelor este transmis prin magistrala partajat# înacela"i interval de timp.

Pentru sinteza magistralei B din Figura 20, se $ine cont de faptul c# cele dou#canale individuale nu vor transfera date în permanen$#. Intervalele de timp în care uncanal este inactiv sunt utilizate pentru transferul datelor celuilalt canal, realizându-sesinteza unei magistrale prin care datele sunt transferate întotdeauna cu o rat# constant#.

Înainte de a fi unit într-o magistral#, dac# un canal transfer # datele la o anumit#rat# medie, trebuie s# fie capabil s# transfere datele prin magistral# la aceea"i rat# medie.Aceasta se poate realiza dac# rata medie, rata_med(B), a magistralei B este mai maredecât suma ratelor medii ale canalelor individuale. Deci

Figura 20. Unirea canalelor X "i Y sub forma magistralei B.


37/47


rata med B rata med C _ ( ) _ ( ) C B

≥∈∑ (3.2)

Scopul gener #rii magistralei este sinteza unei magistrale cu un num#r minim delinii "i o rat# medie dat# de ecua$ia (3.2). Implementarea cea mai eficient# a magistralei

va fi ob$inut# dac# magistrala nu este niciodat# inactiv#, "i dac# ea transfer # în mod con-stant date cu o rat# fix#. În asemenea condi$ii ideale, rata la vârf "i cea medie a magis-tralei vor fi identice:

rata_vârf(B) = rata_med(B) (3.3)

3.3.3.2. Restric"ii pentru generarea magistralei

Pentru un set dat de canale care au fost grupate împreun# pentru a fi implemen-tate printr-o singur # magistral#, pot fi specificate restric$ii pentru mai mul$i parametri aimagistralei "i ai canalelor.

O restric$ie a dimensiunii minime/maxime a magistralei poate fi dedus# dinrestric$iile num#rului de pini specificate pentru modulele sau cipurile c#rora li s-au asig-nat procesele care comunic# prin intermediul magistralei.

Rata medie a canalului poate fi restric$ionat# astfel încât s# se asigure ca proce-sele s# nu fie încetinite datorit# întârzierilor de comunica$ie pe magistral#. Fiind daterestric$ii asupra timpului de execu$ie al unui proces care comunic# prin mai multe cana-le, proiectantul poate aloca sau calcula timpul necesar comunica$iei prin diferite canale,din care se poate deduce o restric$ie asupra ratei medii minime a canalului. O rat# mediemaxim# a canalului poate fi specificat# în cazurile în care unul din procesele care comu-nic# prin canal reprezint# un dispozitiv lent care nu poate transmite sau recep$iona da-tele mai rapid decât o anumit# rat#.

Figura 2#. Restric$ii asupra ratei la vârf a canalelor: (a) trasarea execu$iei pentru canalul X ; (b) magistrala B implementat# f #r # restric$ii asupra ratei lavârf a canalelor; (c) magistrala B implementat# cu o restric$ie a ratei la vârf de

minim %6 bi$i/s.


38/47


În anumite cazuri, poate fi specificat# o rat! la vârf minim#, pentru a se asiguraca transferul unui singur mesaj prin canal s# nu necesite un interval de timp excesiv. Deexemplu, consider #m canalul X din Figura 2#(a), care transfer # un mesaj de %6 bi$i înfiecare din primele dou# intervale de timp, t = 0 "i t = %. Celelalte dou# intervale de timp

sunt utilizate pentru a efectua calcule interne de c#tre procesul care comunic# prin ca-nalul X . Dac# s-ar implementa canalul ca o magistral#, din ecua$ia (3.2), rata medie amagistralei ar fi de 8 bi$i/s, trasarea execu$iei fiind cea din Figura 2#(b). Îns#, procesular necesita atunci patru intervale de timp numai pentru comunica$ia prin magistral#.Aceasta nu se poate accepta, deoarece vor fi necesare înc# dou# intervale suplimentarede timp pentru execu$ia calculelor interne ale procesului (executate ini$ial în intervalelede timp t = 2 "i t = 3 în Figura 2#(a)).

Dac# se specific# pentru canalul X o rat# la vârf minim# de %6 bi$i/s, se va ob$ineimplementarea dorit# a magistralei din Figura 2#(c), care nu necesit# intervale de timpsuplimentare. Deci, pentru toate canalele C c#rora li se asociaz# o restric$ie minim# a

ratei la vârf, exist# rela$ia:rata_vârf(B) > rata_vârf(C) (3.4)

În cazul în care se specific# o rat# la vârf minim# a canalului, magistrala rezul-tat# poate fi inactiv# în anumite intervale de timp.

3.3.3.3. Algoritm pentru determinarea dimensiunii magistralei

Dup# ce s-au introdus restric$iile care pot fi specificate pentru generarea magis-tralei, se prezint# un algoritm pentru determinarea dimensiunii unei implement#ri a ma-

gistralei. Algoritmul presupune c# liniile de control "i de date sunt disjuncte. În oricemoment de timp, un singur canal poate transfera date prin magistral#. Dac# dimensiuneamagistralei este mai mare decât num#rul de bi$i de adrese "i de date, bi$ii de adrese "i dedate sunt transfera$i simultan prin magistral#, în caz contrar ace"tia sunt transfera$i sepa-rat, în dou# transferuri distincte. În ultimul caz, bi$ii de adres# trebuie memora$i de pro-cesul receptor. Dac# dimensiunea magistralei este mai mic# decât dimensiuneamesajului care trebuie transmis prin magistral#, mesajul este transmis prin transferurimultiple.

Se presupune c# toate procesele care comunic# printr-una din canalele magistra-lei au o implementare sincron#. Transferul unui mesaj prin magistral# necesit# deci unnum#r întreg de cicluri de ceas. O variabil# care se acceseaz# prin magistral# este mo-delat# printr-un proces separat care transmite "i recep$ioneaz# valoarea acesteia prinmagistral# ca r #spuns la cererile de la alte procese. Deci, pentru calculul timpului deexecu$ie al unui proces master care acceseaz# o variabil# prin magistral#, se presupunec# procesul slave care modeleaz# acea variabil# este întotdeauna gata pentru transfer,adic# nu apar întârzieri de sincronizare pentru accesul la variabile prin magistral#.

Intrarea pentru algoritmul de generare a dimensiunii magistralei const# dintr-unset de canale care trebuie implementate printr-o singur # magistral# "i din restric$ii asu-

pra ratelor de transfer prin canale "i asupra dimensiunii magistralei. Ie"irea algoritmuluieste dimensiunea în bi$i a magistralei care va implementa setul de canale.


39/47


Algoritmul examineaz# un domeniu al dimensiunilor posibile. Pentru fiecaredimensiune, se calculeaz# rata la vârf a magistralei "i ratele medii individuale ale cana-lelor. Pentru sinteza unei magistrale care transfer # date în mod constant, conform ecua-$iilor (3.2) "i (3.3) rata la vârf a magistralei trebuie s# fie mai mare decât suma ratelor

medii ale canalelor. Fiecare dimensiune a magistralei pentru care aceast# condi$ie esterespectat# reprezint# o implementare fezabil# a magistralei. Din setul de implement#rifezabile ale magistralei, fiecare corespunzând unei dimensiuni diferite a magistralei, seselecteaz# cea cu costul cel mai redus. În cazul în care nu sunt specificate restric$ii, seselecteaz# o dimensiune unitar # care corespunde unui transfer serial de date.

Algoritmul pentru determinarea dimensiunii magistralei este prezentat în Figura

22. Întâi se determin# domeniul dimensiunilor examinate de algoritm. Dimensiunea ma-

if nu exist# restric$ii thenreturn (%)

end if

/* calculeaz# domeniul dimensiunilor */

dim_min = %dim_max = Max (bi " i(C ))

mincost = ∞dim_mincost = ∞for dim_curent ! in dim_min to dim_max loop

/* calculeaz# rata la vârf a magistralei */rata_vârf ( B) = dim_curent ! / prot_delay ( B)

/* calculeaz# suma ratelor medii ale canalelor pentru dim_curent ! */ suma_rata_med = 0;for toate canalele C ∈ B loop

rata med C acces P C biþi C timp calcul P timp comunic P

_ ( ) ( , ) ( ) _ ( ) _ ( )

= ×+

suma_rata_med = suma_rata_med + rata_med (C)end loop

if (rata_vârf ( B) > suma_rata_med ) then/* solu$ie fezabil#, determin# costul minim */cost_curent = CalculCost (dim_curent !)if (cost_curent < mincost ) then

mincost = cost_curent dim_mincost = dim_curent !

end if end if end loop

if (mincost = ∞)then return (e #ec)else return (dim_mincost )

end if

Figura 22. Algoritm pentru determinarea dimensiunii magistralei.


40/47


xim# a magistralei, dim_max, este dimensiunea maxim# a mesajelor transmise prin ori-care canal. Dimensiunea minim#, dim_min, este %.

Variabila dim_curent ! reprezint# dimensiunea curent# care este evaluat# de al-goritm. Pentru fiecare valoare din domeniul (dim_min, dim_max), se calculeaz# rata lavârf a magistralei cu ecua$ia (3.%).

Se noteaz# cu acces(P,C) num#rul mediu de accesuri efectuate de c#tre procesul P la canalul C . Num#rul de bi$i transmi"i sau recep$iona$i prin canalul C într-un singur mesaj se noteaz# cu bi " i(C). Dac# un proces face acces la o variabil# de tip tablou princanal, dimensiunea adresei este de asemenea inclus# în bi " i(C). De exemplu, dac# un

proces face acces la o variabil# scalar # de %6 bi$i x "i la o variabil# de tip tablou y de 32cuvinte × %6 bi$i prin canalele Cx, respectiv Cy, atunci bi " i(Cx) este %6, iar bi " i(Cy) este2% (5 bi$i de adres# "i %6 bi$i de date).

Pentru simplitate, se presupune c# un proces P are un singur canal C prin caresunt transferate mesajele. În cazul în care dimensiunea curent# este mai mic# decât nu-m#rul de bi$i ai mesajului, pot fi necesare mai multe transferuri (în num#r de

biþi C curentã( ) / dim_ ) pentru implementarea transferului unui singur mesaj. Timpulnecesar comunica$iei pentru procesul P este calculat astfel:

)( _ dim_

)(),(=)( _

×

× Bdelay prot

curenta

C bi " iC P acces P comunictimp (3.5)

Utilizând valoarea calculat# mai sus pentru timp_comunic(P), se poate calcularata medie pentru fiecare canal asignat magistralei. Suma ratelor medii a canalului pen-tru o valoare specific# a variabilei dim_curent ! este memorat# în suma_rata_med .

Dac# rata la vârf a magistralei, rata_vârf(B), este mai mic# decât suma ratelor medii a tuturor canalelor, atunci dim_curent ! reprezint# o implementare a magistraleicare nu este fezabil#. Se repet# calcularea ratei la vârf a magistralei "i a sumei ratelor canalelor pentru urm#toarea dimensiune în cadrul domeniului (dim_min, dim_max).

Dac# rata la vârf a magistralei este mai mare decât suma ratelor medii ale cana-lelor, atunci dim_curent ! reprezint# o implementare fezabil# a magistralei. Pentru fieca-re restric$ie asupra dimensiunii magistralei, a ratelor medii "i la vârf specificate pentrumagistral#, procedura CalculCost calculeaz# costul unei implement#ri fezabile ca suma

p#tratelor pentru toate viol#rile restric$iilor, înmul$ite cu ponderile relative specificate pentru restric$iile respective. De exemplu, presupunem c# singura restric$ie specificat#

este cea a dimensiunii maxime a magistralei, reprezentat# de max_linii. Fie k ponderearelativ# specificat# pentru aceast# restric$ie. Pentru fiecare valoare a dimensiunii magis-tralei, dim_curent !, func$ia de cost pentru magistral# va fi definit# astfel:

>−

= altfel 0

max_ dim_ daca))max_ (dim_ (cos

2 liniicurentaliniicurentak t (3.6)

Pot fi specificate "i alte func$ii de cost pentru evaluarea costului asociat cu o di-mensiune specific# a magistralei. De exemplu, dac# se dore"te o implementare a magis-tralei cu un num#r minim de linii, costul poate fi calculat simplu, ca fiind valoareadim_curent !.


41/47


Dac# exist# mai multe solu$ii fezabile pentru grupul de canale, pentru imple-mentare se selecteaz# dimensiunea care conduce la costul minim. Variabila mincost dincadrul algoritmului reprezint# costul minim calculat pentru toate implement#rile fe-zabile, iar variabila dim_mincost reprezint# dimensiunea care corespunde costului mi-

nim.Dac# nu exist# solu$ii fezabile pentru niciuna din dimensiunile examinate, atunci

o implementare pentru grupul respectiv de canale nu este posibil#. Orice implementare aunui asemenea grup de canale va întârzia procesele care comunic# prin magistral#. Oasemenea situa$ie poate apare dac# mai multe canale cu rate medii foarte ridicate suntgrupate pentru a fi implementate printr-o singur # magistral#. O solu$ie poate fi divizareagrupului de canale pentru a fi implementate ulterior prin mai multe magistrale. O alt#

posibilitate este selec$ia dimensiunii nefezabile cu costul minim.

33..33..44.. GGeenneerraarreeaa pprroottooccoolluulluuiiD

minimizarea starilor

Documents