<
I.~
f)
,
',j:
,. r
""
,
!
TECHNISCHE HOGESCHOOL EI1IDHOVEN AFDELING DER ELEKTROTECHNIEK Vakgroep Automatisch Systeemontwerpen (ES)
Het ontwerpen van een multiprocessor ~ysteem voar de oplossing van grate stelsels vergelijkingen uit de: netwerkanalyse. J ;P'.R. Peters
vakgroep ES
Verslag van een afstudeeronderzoek, verricht in de vakgroep ES, o.l.v. Prof.Dr.ing. J. Jess, 12/79 - 12/80.
- 1 -
Samenvatting Dit verslag van een afstudeero~derzoek beschrljft achtereenvolgens de theorie voor het oplossen van grote stelsels vergelljkingen door een multiprocessor systeem, uitgaande van het concept van~de elimination-tree, de software voor data- en taaktoewljzing, het ontwerp van een processor uit het systeem en enkele methoden voor de evaluatie van voorkomende niet lineaire functies.
- 2 Inhoudsopgave pagina
o.
In1eiding
1. Theorie voor de para11e1organisatie van de L/U decompositie 1.1. Netwerkana1yse, Ax = b 1.2. L/U decompositie a. Gausse1iminatie b. Crout decompositie c. berekening van x d. ij1e matrices 1.3. E-tree 1.4. Systeemopzet 1.5. Para11e11e processoren' 2. Software 2.1. Data en communicatievoorbereiding a. e-tree b. critpath c. vectors d. address e. codes f. aanroep 2.2. Besturing van de processoren a. niet 1ineaire functies b. L/U decompositie c. berekening van x 2.3. Voorbee1den 3. Hardware 3.1. PDP-II a1s Host computer 3.2. Processor ontwerp a. a1gemeen
b. ALU c. geheugens d. registers en buffers e. bussen
4
5 5 7 7 8 10 12 14 18 21 23 23 23 25 27
29 30 32 32 32 32 34 34
37 37 39 39 41 45 46
47
- 3 3.3. Besturing a. niet lineaire functies b. L/u decompositie c. berekening van ~
4. Niet lineaire functies
49 50 50 52
4.1. Wortelfunctie 4.2. E-macht 5. 3lotopmerkingen 6. Literatuur
47 47 48
55
.
Bijlagen: 13M3 201 multiprocessor systeem II Voorbeeld e-tree III Software IV Processor ontwerp
56
- 4 -
o. Inleiding De oplossing door een computer van grote stelsels vergelijkingen kan men sneller laten verlopen door de berekeningen, die hieraan verbonden zijn, te laten uitvoeren door meerdere processoren, die min of meer onafhankelijk en gelijktijdig kunnen werken. In het algemeen is er dan datatransport nodig tussen de processoren onderling. Dit kan aanleiding geven tot wachttijden als meerdere processoren via een kanaal willen communiceren. Een theorie die het stelsel vergelijkingen opdeelt en de rekenlast toewijst aan een aan}al processoren is gebaseerd op het principe van de "elimination-tree". Deze theorie wordt in hoofdstuk 1 van dit verslag behandeld. Aan de hand van deze theorie werd een systeem met parallelle processoren ontworpen. Voor de datatoewijzing aan de processoren werd een aantal procedures geschreven uitgaande van de elimination-tree. Ook kunnen hiermee de instructiecodes voor de processoren gegenereerd worden. In hoofdstuk 2 komt deze software aan de orde en worden enkele voorbeelden gegeven. Hoofdstuk 3 beschrijft een processor, zoals die tijdens dit afstudeeronderzoek ontworpen is. Van de bijbehorende besturing zijn nog niet aIle onderdelen in detail (poortnivo) uitgewerkt. Tijdens de oplossing van stelsels vergelijkingen uit de netwerkanalyse moeten ook een aantal niet-lineaire functies geevalueerd worden. Hoofdstuk 4.- geeft een paar voorbeelden van gebruikelijke methoden hiervoor. Dit verslag wordt besloten met enige slotopmerkingen en een overzicht van de geraadpleegde literatuur.
- 5 1. Theorie voor de parallel organisatie van de L/u decompositie 1.1. Netwerkanalyse,
~
=b
Tengevolge van de groeiende complexiteit van geIntegreerde circuits -het aantal elementen per chip verdubbelt iedere twee jaar- is er een toenemende vraag ontstaan naar snelle netwerkanalyseprogramma's. Behalve door gebruik te maken van bijvoorbeeld macromodellering en ijle matrixtechnieken kan ook tijdwinst behaald worden door de rekenlast te verdelen over meerdere processoren • Deze laatste methode is uitgangspunt geweest voor het afstudeerwerk, waarvan dit het verslag is.
.
Alvorens te komen tot een ontwerp van een parallel processing computer met bijbehorende software is een beschouwing van de struktuur en werking van een netwerkanalyseprogramma op zijn plaats. Bij een klassiek analyseprogramma, als bijvoorbeeld SPICE rl1,[21,(31, dat gebruik maakt van "modified nodal analasys" is het uitgangspunt een groot stelsel impliciete gewone differentiaalvergelijkingen (fig. 1.). Na discretisatie op de tijdas ontstaat een stelsel niet-lineaire algebraische vergelijkingen. De oplossing van dit stelsel wordt door itereren verkregen. Vaak wordt hiervoor de Newton-Raphson iteratiemethode gebruikt. Per iteratieslag moet nu een stelsel lineaire vergelijkingen opgelost worden: I /
-
Ax = b'
(1)
Hierin is A een meestal ijle matrix en ~ een bekende vektor. A en ~ bevatten echter aanvankelijk coefficienten, die nietlineaire functies zijn van de onbekende circuitvariabelen, gerepresenteerd door de vektor ~. Iedere iteratieslag begint met het berekenen van deze functies met behulp van de vektor x, die in de voorgaande iteratieslag bepaald werd. In de eerste slag worden geschikte beginwaarden voor 2f gekozen.
- 6 -
stelsel
differentiaalvergel~kingen
discretiseren stelsel niet-lineaire algebraische vergel~kingen itereren niet-lineaire functies,
L/u
fig. 1.
decompo~itie
Netwerkanalyse.
Daarna volgt een L/u decompositie van de matrix A (par. 1.2.) en de bepaling van een nieuwe vektor ~ (par. 1.1.). In de prakt~k bl~kt de meeste rekent~d, 80%, te gaan zitten in het berekenen van de niet-lineaire functies. Het ligt dan ook voor de hand om deze berekeningen te verdelen over meerdere processoren. De verdeling van de rekenlast is niet moeil~k en er is ook geen communicatie tussen de processoren onderling nodig. Het parallel uitvoeren van de L/u decompositie levert slechts een beperkte t~dwinst Ope Toch dient de L/u decompositie ook in de parallelle computer te geschieden, omdat er anders een communicatie-bottleneck ontstaat tussen de parallelle processoren en de Host-computer, die de rest van het rekenwerk verzorgt. Een parallelle uitvoering van de L/u decompositie is echter geen eenvoudige zaak, er zal ook een busstruktuur nodig z~n voor de communicatie tussen de processoren. In dit verslag is dan ook vooral de aandacht gericht op de L/u decompositie en de problemen daarb~. In de volgende paragrafen zal nader op de theorie hiervan worden ingegaan.
- 7 -
1.2. L/u decompositie 1.2.a. Gauss-eliminatie Voor het oplossen van het stelsel algebraische vergelijkingen A~ = ~ zal men, na de berekening van de niet-lineaire coefficienten, de matrix A ontbinden in een linksondermatrix L en een rechtsbovenmatrix TI, zo dat (2)
LU = A en
LUx = Ax = b
(3)
...
Zij nu Ux
=c
(4)
Dan volgt uit (3) en (4) Lc
=b
(5)
Uit (5) is door voorwaartse substitutie de vektor £ te bepalen. In de praktijk gebeurt dit gelijktijdig met de L/U decompositie. Daarna levert achte~~aartse substitutie in (4) de vektor ~ op. Een van de methoden om de L/u decompositie van de matrix A te bewerkstelligen is de eliminatiemethode van Gauss, ook wel vegen genoemd (41. Het principe is als volgt: Beschouw een stelsel vergelijkingen Ax = b , of Allxl +
•••
Anlx l +
•••
- - - -
Stel dat All
F O.
+ Alnxn = b l
- - - - - - - -
(6)
+ Ann~ = b n
Neem de eerste rij van A als eerste rij van U,
Ulj := Alj cl := b l
j=l, ••• ,n
- 8 -
Definieer voor i=2, ••• ,n : Lil := Ail/Ull en vermenigvuldig de eerste vergel~king van (6) met Lil en trek dit van de i-de vergel~king af. Nu ontstaat het volgende stelsel: UllXl + U12 x 2 + • • • + Ulnxn = c l ... e,) (I) b(l) L21 , A22 x 2 + • • • + A2nx n = 2 I
----- , I
Lnl waarin
_1_ 1 1 I I
(.)
An2 x 2 +
(., .- A..
Aij b~') 1.
----
---~J,
.-
o- bi
-
Lil Lil
••• +
* *
Ulj cl
(7)
AC') X
nn n =
b (I)
i, j >,2 i~,
n (8)
2
Op deze w1Jze is een rij van U en een koloID van L verkregen. De b~behorende ondermatrix wordt ook gew~zigd. De laatste n-l vergelijkingen van (7) worden op dezelfde manier behandeld. Er ontstaat dan een triangulair stelsel Ux = £ waaruit ~ eenvoudig bepaald kan worden. 1.2.b. Crout decompositie Een andere methode ter verkr~ging van de L/U decompositie is de methode van Crout. Ret aantal numerieke bewerkingen is even groot als b~ Gauss-eliminatie, alleen de volgorde is anders. Terw~l bij Gauss-eliminatie telkens het produkt van twee getallen van een ander getal afgetrokken wordt, wordt bij de Crout decompositie eerst een aantal produkten bij elkaar opgeteld, waarna het resultaat wordt afgetrokken van een bepaald getal. Ret zal blijken dat de getallen waarmee de produkten gevormd worden in (r~- en kolom-) vektorvorm in de matrix aanwezig z~n: telkens wordt het inprodukt van twee vektoren van een bepaald getal afgetrokkeno Ret grote voordeel van deze methode boven Gauss-eliminatie is dat de partiele sommen van produkten in het optelregister van de computer kunnen bl~ven staan tot het inprodukt voltooid is; er is minder datatransport van en naar het geheugen nodig. Omdat b~ parallelle processoren de" onderlinge communicatie het grootste probleem vormt, en omdat het waarsch~nlijk geacht
- 9 -
werd dat vektormatige bewerkingen efficienter zouden z~n dan bewerkingen met slechts een operatie, werd besloten een parallel computersysteem te ontwerpen, waarin de L/U decompositie plaats vindt volgens de methode van Crout. B~ de decompositie volgens Crout wordt in iedere slag een r~ van U en een koloID van L bepaald volgens: Uij := Aij - ~(Lik * Uki ) l~k
19
procedure Crout; begin !££ p:=l step 1 until n do begin sp:=O;sb:=O; for k:=l step 1 until p-l £2. begin sp:=sp+a(p,k)*a(k,p); sb:=sb+a(p,k)*b(k) end· --' a(p,p):=a(p,p)-sp;b(p):=b(p)-sb; for j:=p+l step 1 until n do begin su:=O;s!:=O; for k:=l step 1 until p-l do begin su:=su+a(p,k)*a(k,j); sl:=sf+a(j,k)*a(k,p) end' a(p,j):=a(p,j)-su; a(j,p):=Ca(j,p)-sf)/a(p,p)
20 21 22
end end-'
1
2
3 4
5 6 7 8
9 10
11 12
13 14 15 16
17 18
~
-
fig. 2.
Algoritme Crout decompositie
De inprodukten worden berekend in de regels 7 (pivot), 8 (b), 15 (r~elementen van U) en 16 (kolomelementen van L).
(9)
- 10 -
In figuur 3. wordt de methode nog eens aan de hand van enige plaatjes weergegeven om de plaats van de vektoren in de matrix te laten zien. • J
....
.. "
'-
I
.,
.O
\ I
I, I
_ •
l
f
• r
..
. i:
c::-S~
" "-
"-
~
"- \..
.
rij:
,
J
"D
::·....:G "I
kolom:
"-
• I
c::::J. I I
"
\.. \..
r=:_iO
"
o •
"- "-
i Irt--l'-
fig. 3.
-
L/U decompositie volgens Crout.
1.2.c. berekening van x Na de bepaling van c en de rechtsbovenmatrix U kan de onbekende vektor x berekend worden uit Ux=c door middel van achterwaartse substitutie (backsubstitution);
--
xn := cn/U nn xi := (c i -Lt Uik
*
xk»/U ii
i
(~O)
- 11 In figuur 4. is dit
aanschouwel~k
gemaakt.
o
"" X1..
:= (c.1. - 'l.(Uo1. k *- x k ) )/U1.1. ..
fig. 4. Berekening van x Bij de L/U decompositie volgens Crout worden de elementen van U kolomsgewijS aangesproken (fig. 3.). Vooruitlopend op het volgende kan reeds gesteld worden dat bij gebruik van een parallel computersysteem aan iedere processor een of meer pivots (diagonaalelementen van de matrix) gekoppeld worden met de bijbehorende kolommen van U en rijen van L. De berekening van ~ heeft echter r~en van ~ nodig en de elementen hiervan zijn dan in het algemeen verspreid over verschillende processoren. Een vektormatige berekening van ~ is nu niet mogelijk. Het is daarom beter om de berekening van x op een iets andere manier te schrijven: X
j
,.-
j=n, (-1),1
cj/U j,j
,- c - U c k ,k kj
3£
xj
l-'k(j
}
In pseudo algol:
f2£ j:=n step -1 until 1 do begin x(j):=c(j)/U(j,j); for k:=l steE 1 until j-l do c(k):=c(k)-U(k,j)*x(j) end' -", fig. 5.
Algoritme berekening van
~
(11)
- 12 1.2.d. ijle matrices Als men de Gausseliminatiemethode (7) bekijkt komt men al gauw in de verleiding om de volgende parallelle computer te ontwerpen: Gegeven een n * n matrix A, neem n processoren en koppel de elementen van A kolomsgewijs aan deze processoren. Aan (7) en (8) kan men zien dat de instructies voor iedere processor (vanaf een bepaald nummer) op elk tijdstip gelijk zijn, wat de bepaling van een rij van U en de bijbehorende ondermatrix betreft. Er hoeft telkens slechts een element van L naar deze p~ocessoren gezonden te worden. De Siemens SMS201 met 128 microprocessoren (bijlage I) werkt volgens dit principe. Tijdens het verloop van de decompositie zullen steeds meer processoren op non-actief gesteld worden, doordat de rijen van U korter worden. De tijdwinst die met een dergelijk systeem te behalen is daalt ook als het aantal beschikbare processoren kleiner is dan het aantal pivots van A, hetgeen in de praktijk meestal het geval zal zijn. Iedere eliminatieslag moet dan in meerdere stappen uitgevoerd worden, hetgeen een complexere besturing noodzakelijk maakt. Veel belangrijker echter is het feit dat de matrices uit de netwerkanalyse ijl (sparse) zijn. Ze bevatten zeer veel elementen die nul zijn. Gebruik van bovengenoemd systeem zou inhouden dat slechts enkele processoren daadwerkelijk bijdragen tot de L/U decompositie en dat het meerendeel van de processoren met nullen werkt. De beschikbare hardware wordt zeer inefficient benut. De elementen van een grote ijle matrix worden trouwens ook niet in een groot tweedimensionaal a~ay opgeslagen, daar dit enorm veel geheugenruimte zou vergen. Meestal kiest men een geindiceerde struktuur voor de opslag. Een geschikte ijle matrixstruktuur is een "row-pointer-columnindex" struktuur (fig. 6.), waarbij er hier vanuit gegaan wordt dat de matrix struktuursymmetrisch is, d.w.z. AijfO~AjifO. Men moet hierbij wel van te voren plaatsen reserveren voor de tijdens de decompositie optrdende "fill-in". Elementen van
- 13 A, die aanvankelijk nul waren, kunnen gevuld worden doordat er een inprodukt vanaf getrokken wordt dat niet nul is.
1 2 3 4 5
x 0 x x 0 0 x x 0 x x x x 0 x x o 0 x 0 ox x 0 x 1 2 3 4 5
- diag. cf. row p. a(l,l) a(2,2) ~ a(3,3) a(4,4) a(5,5)
col. indo off. diag. cf. 3 So a(1,3) a(1,4) 4 a. a(2,3) 3 1 5 If a(2,5) 1 C' a(3,1) 2 a(3,2) a(3,5) 5 f 1 a a(4,1) 2 a(5,2) a(5,3) 3 ••
,
,
fig.• 6. Opslag jjle matrix. Door herordening van de matrix A kan men de fill-in minimaliseren. Een ordening met minimale fill-in is bijvoorbeeld een bandmatrix of een "bordered block diagonal form" (fig. 7.). Een ijle matrix impliceert dat de berekeningen, die met bepaalde pivots geassocieerd zijn gelijktjjdig uitgevoerd kunnen worden «(5],[6]). Een hulpmiddel om van dit gegeven gebruik te maken is de e-tree (elimination-tree), gebaseerd op een graafmodel van de matrix. An de hand van de e-tree kan de matrix verdeeld worden in blokken van de "bordered block diagonal form", die onderling deels onafhankelijk en gelijktijdig bewerkt kunnen worden.
bandmatrix fig. 7.
bordered block diagonal form Hatrices met minimale "fill-in"
- 14 1.3. E-tree De e-tree (elimin~tion-tree~[71,t81) is afgeleid van een graafmodel van een ijle matrix. Verondersteld is dat er enig voorbereidend rekenwerk heeft plaatsgevonden, zodat de matrix struktuursymmetrisch is en dat er geheugenplaatsen gereserveerd zljn voor de optredende fill-in. De L/U decompositie mag nu geen extra fill-in meer genererenl Het is noodzakelijk eerst enkele begrippen rond het graafmodel te definieren; hierbij zullen in hoofdzaak de engelse benamingen gehanteerd worden. Een graaf wordt gesymboliseerd door (V,E), waarin V de set knooppunten (vertices) is en E de set takken (edges), die de knooppunten verbinden. Met (u,v)€.E terwijl uEV en vG:.V wordt bedoeld een tak tussen de knooppunten u en v. Er wordt geen onderscheid gemaakt tussen (u,v) en (v,u). In matrixtermen stellen de knooppunten van de graaf de diagonaalelementen voor, terwijl de tak (u,v) de elementen a(u,v) en a(v,u) representeert. Verdere definities zijn (fig. 8.): - inc (v ,E) : = { (v, u) EEl v c V, u E V~ aIle takken die lIincident ll zijn aan v, of aIle takken die van v uitgaan. - ad j ( v , E) : = {u E V , ~ v , u) l: E ~ : aIle knopen die "adjacent ll zijn aan v, of aIle knopen die door een tak met v verbonden zijn, aIle buren van v. - def(v,E) := {(u,w)l u,w€adj(v,E)/\ (u,w)¥EI : "deficiency",het ontbreken van een tak tussen twee buren van v. inc(p,E) = {(p,u), (p,v), (p,w)i adj(p,E) = [u, v, w} def(p,E) = {(u,w)! fig. 8.
Definities graafmodel.
- 15 Het verband tussen de graaf en de matrix is als voIgt (fig. 9.):
v
~
(v,u) inc(v,E)
~
adj (v ,E)
~
def(v,E)
~
~
diagonaalelementen a(u,v) en a(v,u) non-zero off diagonal elementen van de rij en kolom met a(v,v) als pivot een bepaalde set diagonaalelementen met bijbehorende submatrix de zero off diagonal elementen in deze sUbmatrix, en symboliseert de fill-in die hier gaat optreden.
Ync(:e~ a(p,p)
a(p,u)
a(p,v)
a(p,w)
a(u,p)
a(u,u)
a(u,v)
-...... ~u,w]}
\~ a(v,p)
a(v,u)
a(v,vJ
a{v,w)
a(w,v)
a(w,w)
J'
inc(p,E
(
a(w,p)
-
~(w,~
.0:
fill-in ~ def(p,E) {a(u,u),a(v,v),a(w,w)} ~ adj(p.E) fig. 9. Verband graaf-matrix
Voor de L/u decompositie wordt in iedere stap een bepaalde pivot gekozen, waarna de bijbehorende rij en kolom worden omgevormd tot een rij en kolom van U en L. Deze rij en kolom worden nu uit de matrix "verwijderd" en uit de overblijvende 6ubmatrix wordt een nieuwe pivot gekozen, etcetera. In termen van grafen betekent dit: definieer twee subgrafen (V,E) C(V,E) en (V,E)~(V,E) en begin met (V,E) = (¢,~) en = (V,E). De volgende procedure, UPDATE, beschrijft dan het verwijderen van een rij en koloID tijdens een stap van de L/u decompositie.
(V,E)
- 16 procedure UPDATE(p); _ __ It. _ _ A begin V : = V U l pJ U ad j (p, E); E : = E lJ inc (p , E) ; V := v'-{pl; E := EU def(p,E)'\J.nc(p,E) ~;
fig. 10.
Procedure UPDATE.
" = ~ voor aIle p Een keuzeset voor p (l~p~n) zodat def(p,E) tijdens de L/U decompositie wOJrdt "perfect ordering" genoemd. Een graaf waarbij een dergelijke ordening mogelijk is heet "perfect elimination" graaf of "triangulated" graaf. Een dergelijke graaf heeft de eigenschap dat indien (v,u) en (v,w) bestaan en er is een pad tussen u en w dat niet door v gaat, dat dan (u,w) bestaat.
.
Het principe van de a-tree is nu als-volgt: Uitgaande van een "triangulated" graaf worden aIle knooppunten v € V toegekend aan "label-classes" V( i). Dit gebeurt in stappen • .... In de i-de stap worden de knooppunten met def(v,E) = ~ toegekend aan label-class 'V( i), met label i. .... Echter niet aIle knooppunten met def(v,E) = ~ kunnen aan V(i) toegekend worden. Als bijvoorbeeld v en u beide in aanmerking " dan mogen v en u niet in dezelfde labelkomen, maar v € adj (u,E) class geplaatst worden. De bedoeling is namelijk dat knopen, die tot dezelfde label-class behoren onafhankelijk van elkaar zijn en dus gelijktijdig bewerkt kunnen worden. " dan betekent di t dat bijvoorbeeld u pas als Als nu v 6 adj (u,E) pivot gekozen kan worden na de berekening a(u,u):=a(u,u)-a(u,v)*a(v,u) Na vol tooiing van label-class V( i) worden aIle v c V( i) en "" J'\, aIle incidente takken uit (V,E) verwijderd. De procedure wordt .... herhaald om de volgende label-class te verkrijgen, totdat V = ¢. Tenslotte wordt de e-tree gevormd door knooppunten uit verschillende label-classes met elkaar te verbinden met takken uit E, zodat het verschil tussen de labels zo klein mogelijk is. De algoritme voor de e-tree wordt gegeven in figuur 11. In bijlage II is een voorbeeld opgenomen.
-
- 17 procedure ETREE(V,E); begin comment (V,E) is een triangulated graaf; ,.. A (V,E) := (V,E); i:=l; "" 1= f/J do while V begin A _ U := V; V(i) := f/J; for ~ vEU do begin U := U\
tvJ; A
if def(v,E) = f/J then begin V(i) := V(i) U lv"J; .I3(v) := i; comment V(i) is label-class i, J3(v) is de label van v; A . U : = U \ ad j ( v , E) ; ;\ A .... ""\ A V := v\tvl; E := E inc(v,E) end end· -' i := i+l; end" -' comment constructie van de e-tree (V,B);
B
:=
Y';
for each v 6 V do B := BU{(v,W)~E \ end; fig. 11.
~w)
is de kleinste label'>'&v)\
Algoritme voor de e-tree.
Enkele belangrijke eigenschappen van de e-tree zijn: - Ret rekenwerk dat geassocieerd is met knooppunten uit dezelfde label-class kan gelijkt~dig (parallel) plaatsvinden in een bepaald "time slot lt • - Ret kritieke pad door de e-tree is het langste pad van een blad van de boom naar de wortel; de lengte van dit pad is gel~k aan de label, J3(r), van de wortel. 'Ret geeft tevens het aantal time slots dat nodig is voor de L/U decompositie. - De e-tree is niet uniek, maar aIle e-trees voor een bepaalde graaf (V,E) hebben kritieke paden van dezelfde lengte.
- 18 -
- Ieder knooppunt heeft slechts een opvolger in een hogere label-class. De hoogst genummerde label-class bevat slechts een knooppunt, de wortel, die geen opvolger heeft. - AIle bladen van d~ e-tree bevinden zich in V(l). - AIle "connecties" tussen een bepaalde knoop, v, en knopen in een hogere label-class kunnen gerepresenteerd worden door backedges naar deze knopen, die liggen op het pad van v naar de wortel van de e-tree. Behalve het kritieke pad z~n er nog meer paden aan te w~zen in de e-tree. Van elke knoop in Vel) gaat een pad uit • Ieder pad eindigt b~ de aansluiting op een ander pad. De paden kunnen als voIgt bepaald worden: l.zoek het langste pad in de e-tree. 2.verwijder dit pad uit de e-tree. 3.herhaal 1. en 2. tot de e-tree geen knooppunten meer bevat.
..
Men kan twee soorten backedges onderscheiden (fig. 12.), - van een knoop v naar een knoop w op hetzelfde pad als waar v: op ligt, - van een knoop v naar een knoop w, die op een ander pad ligt. In principe kan elk pad in de e-tree gekoppeld worden aan een eigen processor. De laatstgenoemde backedges komen dan overeen met updates van elementen, die tot andere paden behoren. Dit geeft aanleiding tot datatransport tussen de processoren. 1.4. Systeemopzet Toepassing van de procedure e-tree levert een herordening van de matrix Ope De L/u decompositie -volgens Crout- kan nu deels parallel uitgevoerd worden, doordat r~em en kolommen, die tot dezelfde label-class behoren gelijktijdig berekend kunnen worden. Nadat de r~en en kolommen, die bij een bepaald pad uit de e-tree behoren, berekend zijn -in de e-tree zijn dit de backedges naar knopen op hetzelfde pad-, kunnen partiele inprodukten
- 19 gevormd worden, die afgetrokken worden van elementen op andere paden -dit z~n de backedges naar die andere paden-. Voor de matrix en e~tree uit figuur 12. betekent dit hetvolgende: In time slot 1 wordt berekend: processor 1 r~ en kolom 9, updates voor de elementen a(lO,lO), a(lO,5)·,a(5,lO) en a(5,5). processor 2 r~ en kolom 7, updates voor de elementen a(8,8), a(8,4) en a(4,8). processor 3 : r~ en koloID 1, updates voor de elementen a(2,2), a(2,3) en a(3,2), en a(3,3). Ook zou al een update voor aC4,4) berekend kunnen worden in processor 2, maar dit wordt uitgesteld tot aIle elementen van pad 2 bepaald z~n. Dan kan namel~k een inprodukt gevormd worden ( a(7,4)*a(4,7)+a(8,4)*a(4,8) ) en aIleen het resultaat hoeft ~ls update voor a(4,4) naar processor 1 gezonden te worden. De andere updates die dan berekend worden voor elementen op een ander pad z~n a(8,6)*a(6,8) voor aC6,6), a(8,6)*a(4,8) voor a(4,6) en a(8,4)*a(6,8) voor a(6,4). Als men b~voorbeeld a(7,4),a(8,4) als vektor, met lengte 2, beschouwt en a(6,8) als vektor met lengte 1, wordt als update voor a(6,4) dus een korte vektor (a(6,5)) met een deel van een langere vektor (a(8,4)) vermenigvuldigd.
pA.cU.
9, I I
I
{ 3
10
,/
I II '" I \I I
If
\\('f
~,
o 0-
OltQ,.1(
--0
:
\'o..c.IC~J~e
fig. 12.
E-tree en matrix uit bijlage II.
- 20 -
De vektoren in dit voorbee1d z~n slechts kort, maar het principe van het werken met vektoren 'b1~ft ge1den. Om dit rekenwerk moge1~k te maken zu11en de processoren uit het parallel computersysteem moeten bestaan uit de vo1gende onderde1en: Een sne1 geheugen, dat de matrixe1ementen bevat, in vektorvorm, behorend b~ een bepaa1d pad uit de e-tree. - Een rekeneenheid, ALU, waarvan de sne1heid verge1~kbaar is met die van de Host computer. Deze ALU moet dan 32 bit floating point berekeningen a1s vermenigvu1digen, de1en, opte11en en aftrekken kunnen uitvoe~en. Bovendien zou het prettig zijn a1s tevens de niet-1ineaire functies door deze ALU geeva1ueerd zouden kunnen worden. - Een bus waar1angs de Host computer toegang heeft tot de geheugens van de processoren. Een bus, bestuurd via de Host computer, voor de paar\~ze communicatie tussen de processoren onder1ing. - Een instructiegeheugen, waarin het programma voor de processor opges1agen wordt. In figuur 13. is een b10kschema van dit ontwerp getekend.
riO b 11£
H O~T
I ..
" ,it
"
Mo
Ml)
'"
II
M%
l'
-----
.....
Hs
~ AlU
J, l'
' ~
ALl,) ~~
~ ,~
bus C'o.,froller
Mn MI
,if bits) co __ u,,~c:.Q,!ie. ~"SU ..
., d.c
geheugen voor de matrixe1ementen instructiegeheugen fig. 13.
B10kschema computer.
fro CeiIlO'f'e",
- 21 -
In de Host computer gebeurt het voorbereidende werk. Nadat de e-tree gevormd is worden data en instructiecodes gereed gemaakt en naar de parallelle processoren gezonden. Tijdens het berek~nen van de niet-lineaire functies, de L/U decompositie en ~ is er geen interactie tussen de Host computer en de parallelle processoren. Tenslotte wordt de vektor ~ uit de geheugens van de processoren gelezen door de Host computer. 1.5. Parallelle processoren In principe kan ieder pad in de e-tree aan een bepaalde processor toegewezen worden. Het heeft geen zin om lange paden te verdelen over meerdere processoren om ·zodoende de totale verwerkingstijd te bekorten. Ieder pad dient immers sequentieel doorlopen te worden van blad naar wortel. De minimale verwerkingstijd van de L/U decompositie is te berekenen uit de werklast, die verbonden is aan het kritieke pad in de e-tree. De te behalen tijdwinst ten opzichte van een sequentiele machine blijkt een faktor 4 a 5 te zijn. Hieruit volgt dat het aantal benodigde processoren ook beperkt zal zijn. Als de maximaal te behalen tijdwinst een faktor 5 is kan dit in principe bereikt worden met 5 processoren. Dit minimale aantal processoren is te bepalen door de totale werklast van de l/U decompositie te delen door de werklast, die verbonden is aan het langste pad (het kritieke pad) in de e-tree. Voor de berekening van de niet-lineaire functies is het natuurlijk weI voordelig om een groot aantal processoren tar beschikking te hebben. Als het aantal beschikbare processoren kleiner is dan het aantal paden in de e-tree zullen meerdere paden aan een processor gekoppeld moeten worden. Door dit op een slimme manier te doen, n.l. die paden bij elkaar te nemen, die veel onderlinge interactie hebben, wordt het datatransport tussen de processoren beperkt. Veel paden zijn slechts kort en toewijzing van een processor per pad zou inhouden dat aIleen in de beginfase aIle processoren actief zijn.
- 22 -
Clustering van paden heeft dus ook het voordeel da~ de hardware eefectiever benut wordt. Voor iedere knoop (pivot+rij+kolom) geldt dat er een vroegste tijdstip en een laatste tijdstip is waarop hij behandeld kan worden. Meestal zit hier weI enige ruimte tussen, die men kan gebruiken voor de scheduling van het rekenwerk.(fig. 14.). Het totale rekenproces wordt hierdoor niet verlengdl 1
3
fig. 14.
Clustering van paden.
Deze clustering van paden wordt in dit verslag verder niet behandeld, een aanzet ertoe is (9J. In het vervolg zal er van worden uitgegaan dat ieder pad aan een eigen processor gekoppeld wordt. Ook de taak van de bus controller, nodig voor de scheduling van de communicatie tussen de processoren, wordt in dit verslag niet uitgewerkt.
- 23 2. Software 2.1. Data en communicatievoorbereiding 2.1.a. e-tree In dit hoofdstuk worden een aantal procedures besproken, die nodig zijn voor de voorbereiding van de parallelverwerking van de L/U decompositie. De procedures zijn geschreven in BEA (Burroughs extended algol), voor gebruik op de B7700 machine van de Technische Hogeschool Eindhoven. Omdat ze bij feite~ijk gebruik waarschijnlijk in een andere programmeertaal en voor een andere computer herschreven dienen te worden, is niet al te veel aandacht besteed aan optimalisatie van de programmering. De tekst van de procedures, alsmede de computeruitvoer van enkele voorbeelden, is verzameld in bijlage III. Zoals reeds vermeld in het vorige hoofdstuk vindt de opslag van de te ve~qerken matrices niet plaats in grote tweedimensionale arrays. Hier is gekozen voor de volgende geindiceerde opslag: een array INDEX(1:N,1:7], waarin N de rang van de matrix is en INDEX[i,11 = nummer van het diagonaalelement, INDEX(i,21 = aantal niet diagonaalelementen a(i,*) F 0, I~~EXti,31 = aantaJ records waarin de nummers van deze niet diagonaalelementen staan, INDEx[i,41 - INDEXli,71 = nummers van de records waarin de niet diagonaalelementen staan. - een array ROW[N+l:N+NN,1:18] , met NN is het aantal records nodig voor de opslag van de matrixelementen, terwijl in ieder record 18 plaatsen zijn gereserveerd voor de opslag van de nummers van de niet diagonaalelementen. - een array met grenzen [N+l:N+NN,O:lS] dat de feitelijke matrixelementen bevat, de diagonaalelementen op de plaatsen met tweede index = 0, maar dat voor de datavoorbereiding niet van belang is.
- 24 Voorbeeld: INDEX[5,*1 = 5, 2,1,199,0,0,0 ROWt199,*) = 2, 115, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 geeft aan dat a(5,2) F 0 en a(5,115) F O. Bij de datavoorbereiding wordt allereerst de procedure ETREE aangeroepen. De procedure veronderstelt dat de matrix struktuursymmetrisch is en "triangulated ll • De heading luidt: procedure ETREE(N,INDEX;ROW,BETA,BADJ); integer N; array INDEX *,* ,ROW *,* ,BETA * ,BADJ *,* N
INDEX, ROW BETA(l:N] BADJ [1 : N, 1: 10J
rang van de matrix (invoer) opslag van de matrix (invoer) bevat na afloop de label-classes van iedere pivot bevat na afloop de takken van de e~tree
In de procedure kan men twee delen onderscheiden. In het eerste deel (regels 2040-2370) wordt iedere pivot geplaatst in een bepaalde label-class. Diagonaalelementen, die nog niet gelabeld zijn en die potentiele kandidaat zijn (2060-2070) worden onderzocht op "deficiency" (2080-2290); er wordt gekeken of keuze als pivot geen fill in veroorzaakt in de onderliggende submatrix. Indien dit inderdaad niet het geval is wordt een label aan het element toegekend (2300-2310), en worden aIle elementen die "adjacent ll zijn uitgesloten van kandidatuur voor deze label-class (2320-2330). In het tweede deel van de procedure (2380-2520) wordt de e-tree gevormd. Dit gebeurt door de takken van de e-tree te bepalen en op te slaan in array BADJ. Van iedere knoop worden de voorgangers bepaald, die in een lagere label-class zitten, zo dat het verschil in labels zo klein mogelijk is. Indien het verschil precies 1 is Vlordt het nUTIliner van deze voorganger veer in het array BADJ toegevoegd, anders achteraan (fig.l
- 25 -
3
w
bad j ( w) = { v 3 ' v 2 ' V1 ' v 4} badj(v1 ) = ¢ fig. 15.
,
Badj(w) en badj(v1 ).
Door de arrays BETA en BADJ is de e-tree vo11edig bepaa1d. 2.1.b. critpath Deze procedure nummert de paden in de e-tree. Ret 1angste pad dat het eerste gevonden wordt is het kritieke pad en krijgt vo1gnummer 1. De nummers van de knopen van ieder pad worden geindiceerd opges1agen in een array pl1:N+~, zoa1s aan~egeven in figuur 16. De 1aatste p1aats in array P dient a11een voor de vereenvoudiging van de programmering. In een array CPI1IDEX[1:CPMAXl wordt de p1aats van het begin van ieder pad, zoa1s dat in P is opges1agen, aangegeven. CPMAX is het hoogste padnummer uit de e-tree. \-
--,
f4".&. f , I
.t
,,-
_... -.
cpindex pad 1 = l2,4} ~ 1 pad 2 = eli ~ 3 pad 3 = [3 J ~ 4
:-- 'f- - - .:
fig. 16. Ops1ag paden van de e-tree.
- 26 -
In het array PATH[l:N] wordt bewaard op we1k pad iedere knoop 1igt (PATH(4] = 1 in fig. 16.). De procedure CRITPATH is recursief en gebruikt "depth first search". De a1goritme is a1s voIgt (fig. 17.): procedure CRITPATH(x,i); begin P ( i ) : = P ( i ) U {x
t;
comment P(i)CV is pad nummer i; y := first entry of badj(x); if y ~ 0 then begin CRITPATH(y,i) ; f£E all other entries y of badj(x) do begin i := i + 1; CRITPATH(y,i) end end end; fig. 17. A1goritme critpath. De procedure heading 1uidt: procedure CRITPATH(X,BADJ,CP,P,CPI~IDEX,PATH); integer X,CP; array BADJ(*,*] ,f[*J,CPINDEX[*,*1,PATH[*);
x BADJ OF
F
OPINDEX PATH
de aktue1e knoop; bij eerste aanroep dient dit de worte1 van de e-tree te zijn (invoer) de takken van de e-tree (invoer) nummer van het aktue1e pad; bij eerste aanroep dient OF de waarde 1 te hebbenj CP bevat na af100p het hoogste padnummer (invoer en uitvoer) bevat na af100p de paden, achter e1kaar hu1parray om de p1aats van het begin van de paden in P aan te geven bevat na af100p op we1k pad iedere knoop 1igt.
- 27 2.1.c. vectors Om de berekening van de inprodukten zo te laten verlopen dat hiervoor elementen gebruikt worden, die in opeenvolgende geheugenplaatsen van een processor opgeslagen zijn, zijn twee procedures geschreven. De eerste procedure, VECTORS, zet matrixelementen in vektorvorm bijeen, de tweede procedure, ADDRESS (2.1.d.), verzorgt de toewijzing van deze element en aan de geheugens van de processoren. Indien men een stuk van een e-tree bekijkt, met daarin getekend alle backedges (fig. 18.-) kUlmen enige begrippen gedefinieerd worden: V~
".
'''If' \IJ • "1. • \I, \ = r""If • \01, • W2 ....., 1
wit
rAJ j
Wl
p ... .l
Wt
0- --0
W,
0-
:;
. I
0
[ v 5'
b... elC:ecldes
'.
~Q.lCl<e .. vA" Je e -l: 1'ee
V,
fig. 18. - root(p) - highpoint(v,p)
- bottom(v,p)
Stuk e-tree.
de wortel van een pad, in figuur 18 is root(i) = wI en root(j) = v l • een knoop op pad p in een lagere label-class dan waar v inzi t" zodat er een backedge of tak van de e~tree bestaat tussen v en deze knoop, terwijl de label van deze knoop minimaal is; in figuur 18 is highpoint(vl,j) = v ' 3 highpoint(vl,i) = w3 • NB: highpoint(wl,j) = ¢. als highpoint(v,p) ! ¢ dan: als v op pad p ligt de voorganger van v, anders de wortel van pad p; in figuur 18 is bottom(vl,j) = v 2 ' bottom(v1 ,i) = wl en bottom(wl,j) = ¢.
- 28 -
Highpoint en bottom geven het begin en einde aan van een vektor van matrixelementen. In de door de e-tree herordende matrix is iedere vektor een stukje rij van de toekomstige linksondermatrix L en een stukje kolom van de toekomstige rechtsbovenmatrix U.(fig. 19). De vektoren zDn vol, d.w.z. ze bevatten geen elementen die nul zijn. In de graaf (V,E) van de matrix is zo'n vektor equivalent met een "maximal fundamental loop".
/,- - - - ,
-
-1-1- - - -
"l~l,fOiwU",.i~
["
I" "
I
w~
11''''s.'''
l,.O.uO... {lIh iJ-..
/1.
'
i' - - .-.......--, I,,,.
L"
'\.r. '\
t~"r···~l.v,'~J
:....1
-. ~
'.~~
I
I_\'~l~~~v"j}~ ~ \_ ._..~...L.. _~~ '4 ~.".
I. •.• I
VI ,",_
v,."'J
'"'t
V..
""s
II
~/IWt"l
'"
I"
I
.
v,."',
fig. 19.
V'f
~ 'It
~'''I 1I,.\'t ",.11,' ...
Vektoren in de matrix.
De procedure VECTORS bepaalt nu highpoint(v,p) en bottom(v,p). Aan de e-tree kan men zien dat bottom(v,p) = BADJ[v,l] als v op pad p ligt en dat anders bottom(v,p) = root(p). De procedure heading luidt: procedure VECTORS(N,INDEX,ROW,BETA,CPMAX,P,CPINDEX,PATH, BADJ , VT , VB) ; integer N,CPMAX; array IN])EX[*,*] ,R0\1[*,*) ,BETA[*J ,P (*], CPINDEX [*) ,PATH [*1 ,BADJ (*,*1, VT [*,*) ,VB (*,*1; Nieuw zijn: VT 1: N, 1: CPf\1AX VB l:N,l:CPHAX
bevat na afloop highpoint(v,p) bevat na afloop bottom(v,p).
- 29 2.I.d. address Nadat highpoint en bottom voor iedere knoop en met betrekking tot elk pad bepaald zijn kunnen de vektoren samengesteld worden. Daarna kunnen de elementen die tot zoln vektor behoren aan de geheugens van de processoren worden toegewezen. Bij iedere "maximal fundamental loop" horen nu twee vektoren van gelijke lengte en met elementen a(u,v) en a(v,u). Besloten werd om daarom de geheugens van de processoren in twee delen te splitsen, NL en MR. Het geheugen ML bevat dan de rijvektoren uit de linksondermatrix en MR bevat de kolomvektoren ~it de rechtsbovenmatrix. De diagonaalelementen worden aan ML toegewezen en de elementen van b aan MR. In het voorbeeld uit paragraaf 2.I.c. zou dit resulteren in een toewijzing zoals in figuur 20. a(v l ,w ) 3 a(vl ,w 2 ) a(vl,wl ) a(w ,w ) 4 4 a(w ,w ) 3 3 a(w 2 ,w 2 ) a(wl,wl )
a(w ,vl ) 3 a(w 2 ,vl ) a(wl,vl ) b(w ) 4 b(w ) 3 b(w 2 ) b(wl )
ML MR processor i fig. 20.
I 2 3 4 S 6
7 adres
a(vl ,v ) 3 a(v l ,v 2 ) a(vS'v S ) a(v ,v ) 4 4 a(v ,v ) 3 3 a(v 2 ,v 2 ) a(vl,v l )
a(v ,v l ) 3 a(v 2 ,vl ) b(V S ) b(V ) 4 b(v ) 3 b(v 2 ) b(v l )
ML MR processor j
Toewijzing matrixelementen.
De procedure ADDRESS verzorgt deze toewijzing. In het arra~ PLACE(N+I:N+NN,O:IS] wordt onthouden welke plaats in welk geheugen voor een bepaald matrixelement bestemd is. Dit array heeft dezelfde struktuur als het array ROW, zij het dat er extra plaatsen gereserveerd zijn voor de adressen van de diagonaalelementen (PLACE[*,O]).
- 30 -
De procedure heading luidt: procedure ADDRESS(VT,VB,CPMAX,N,P,CPINDEX,INDEX, ROW ,PLACE); integer CPMAX,N; array VT[*,*J,VB~,*),P[*], CPIlIDEX[*J, INDEX [*1 ,ROW [*,*1 ,PLACE [*,*] ; 2.1.e. codes Tenslotte wordt de procedure CODES aangeroepen, die de instructiecodes voor de verschillende processoren genereert. Voor ieder pad in de e-tree wprden achtereenvolgens bepaald: - codes voor de berekening van inprodukten ten behoeve van updates van elementen die in het geheugen van dezelfde ~ processor zitten ~ codes voor de berekening van inprodukten ten behoeve van updates van elementen die in het geheugen van een andere processor zitten - codes voor de berekening van ~. Voor de berekening van de niet lineaire functies worden nog geen codes gegenereerd. Deze berekeningen worden geacht plaats te vinden v66r de L/U decompositie, in time slot O. De overige time slots zullen niet aIle evenlang zijn, afhankelijk van het grootste aantal bewerkingen in ieder time slot. Deze time slots komen overeen met de label-classes van de e-tree. Voor de L/U decompositie moeten voor de update van een bepaald matrixelement, waarbij het niet uitmaakt in welk" processorgeheugen dit element zich bevindt, telkens twee vektoren bepaald worden, waarmee het inprodukt gevormd gaat worden. Voor een update voor a(u,v) op pad j, die gevormd wordt met vektoren die tot pad L behoren, met ~ al dan niet gelijk aan j, wordt eerst gekeken of highpoint(u,i) en highpoint(v,i) niet 0 zijn. Indien ze beide niet 0 zijn wordt een TOP vastgesteld, dit is die highpoint, die in de hoogste label-class zit. De benedengrens van de vektoren is gelijk aan bottom(u,i) = bottom(v,i (zie ook fig. 3., fig. 12., fig. 19.). Zoals gezegd kunnen updates voor elementen van de vektor b
- 31 met de L/u decompositie bepaald worden. Uit figuur 3. blijkt dat het benodigde rekenwerk hetzelfde is als voor een rijelement van U. Het berekenen van de vektor £ uit £ gaat automatisch als b beschouwd wordt als een extra kolom van de matrix. tegel~k
Voor de berekening van ~ uit £ en U werd bepaald dat de paden van de e-tree na elkaar in opklimmende volgorde van nwmnering, en van wortel naar blad doorlopen zullen worden. In de herordende matrix komt dit overeen met de normale achterwaartse substitutie volgens de tweede methode uit 1.2.c. Hierbij gaat £ geleidelijk over in x.:
I
(1)
:= c i
l
~
i
~
n-l
I un-l,n-l
:= cl ) - x n _l
*
ui,n-l
I
~
i
~
n-2
enzovoorts. Zodra een element van ~ berekend is (de deling) wordt het naar aIle andere processoren gezonden (broadcasting), waarna~ met behulp van dit element en een element van U een update voor een element van £ berekend wordt. Het berekenen van een element van x en het maken van updates dient in versc~illende time slots te geschieden, omdat zoln element van x eerst naar elke processor gezonden moet zijn voor er mee gewerkt kan worden. In paragraaf 2.2. zullen de gegenereerde codes behandeld worden. De uitvoer van CODES is nu nog gericht op visuele interpretatie (decimale getallen met tekst), maar is eenvoudig te herschr~ven voor binaire uitvoer. De heading van de procedure luidt: procedure CODES(VT,VB,CPMAX,N,P,CPINDEX,INDEX, ROW,PLACE,BETA,BETAMAX); integer CPMAX,N ,BETMIAX; array VT t*,*1, VB [*,*1 , 1'[;iJ ,CPINDEX L*] ,INDEX [*,*) ,ROW [*,*) ,PLACE [*,*] , BETA [:£];
- 32 -
2.l.f. aanroep In een kort pro8ramma wordt eerst de matrixstruktuur ingelezen in de arrays INDEX en ROW, uit de file IN. Indien de file IN niet op de magnetische sch~f aanwezig is geeft het systeem CANDE de melding: :t*NO FILE IN Men kan dan een andere file laten lezen door in te typen: ?FA TITLE =
~filenaam>
Vervolgens worden de procedures ... ETREE, CRITPATH, VECTORS, ADDRESS en CODES aangeroepen. Tussendoor worden de e-tree (BETA, BADJ) en de paden (P, PATH) afgedrukt. Door de procedure ADDRESS wordt de adrestoew~zing van de matrix~lementen gedrukt en door de procedure CODES de instructiecodes. 2.2. Besturing van de processoren 2.2.a. niet lineaire functies Codes voor de berekening van de niet lineaire functies worden nog niet gegenereerd. Hiervoor is het nodig te weten welke functies en op welke plaatsen ze geevalueerd moeten worden. WeI kunnen enige aanw~zingen gegeven worden. Deze berekeningen dienen plaats te vinden in time slot 0, veer de aanvang van de L/U decompositie. De soort functie kan door een code worden aangegeven. Indien a(u,v) := f(X j ) dan kan in de matrix op de plaats van a(u,v) een schatting voor x j ' of de in de vorige iteratieslag berekende x j gezet worden. De processor gebruikt dit getal dan als argument voor de door de oode aangegeven functie. Het resultaat kan dan naar hetzelfde adres in het geheugen teruggestuurd worden. 2.2.b. L/U decompositie Voor het berekenen van de inprodukten moeten de vektoren doer de processoren uit de geheugens gehaald kunnen worden. Gekozen werd voor het aangeven van de beginadressen van de "linker" en
- 33 "rechter" vektor, en de lengte van zoln vektor. Ook de plaats waar het resultaat naar toe moet, en naar welke processor, dient in de instructiecode opgegeven te worden. Het kan ook voorkomen dat er een deling door een diagonaalelement moet plaatsvinden, het adres van dit diagonaalelement wordt dan ook in de instructiecode gegeven. Tenslotte dient nog vermeld te worden in welk time slot de instructie uitgevoerd moet worden. De instructiecode ziet er dan schematisch als voIgt uit (fig. 21.) .t
[T
I
1-
VL.
vR.
1O
ID
fig. 21.
~I 't
DIAg
p
10
"I
I
R. £'s
"
0 If
Instructiecode.
Uit de gegevens van enige tests (2.3.) volgde het aantal bits dat voor ieder stuk uit de instructiecode nodig is, dit is eveneens in figuur 21. vermeld. In totaal bleken minimaal 60 bits nodig. Omdat de busverbinding tussen het instructiegeheugen en de Host computer in de prakt~k 16 o~ 32 bit breed zal zijn, werden nog 4 extra bits aan de instructiecode toegevoegd (Cl, C2, C3 en C4), zodat het totale aantal bits op 64 komt. Hieronder voIgt een opsomming van de betekenis van de verschillende blokken:
...
m
7 bit
10 VR 10 L 4 1 D DIAG 10 VL
P
bit bit bit bit bit 7 bit
RES
11 bit
Cl C2
1 bit 1 bit
C3 C4
1 bit 1 bit
timeslot waarin de bewerking moet plaatsvinden startadres linkervektor (1 - 1024) startadres rechtervektor (1 - 1024) lengte van de vektoren (maximaal 16) geeft aan of er een deling moet plaatsvinden adres van het element waardoor gedeeld moet worden nummer van de processor waar het resultaat naar toe moet (rnaximaal 128) adres voor het resultaat, de eerste bit geeft aan of dit in ML of in MR is er moet een element van x berekend worden (deling) er moet een update voor een element van £ berekend \V'orden (fase: berekening van ,2S) het inprodukt is bestemd voor een andere processor niet gebruikt
- 34 -
2.2.c. berekening van
~
Tijdens deze laatste fase van het parallelle rekenwerk kan men twee gevallen onderscheiden, de berekening van x j en het vormen van updates voor c i • Voor de berekening van x. is de deling c. / a .. nodig. Het J J JJ resultaat wordt via een aparte bus, de XBUS, naar aIle andere processoren gestuurd, en daar bewward in een speciaal register, XREG.
Om dit aan de processor kenbaar te maken krijgt Cl in de instructiecode voor de processor waar de deling uitgevoerd moet worden de waarde 1. De overige processoren zijn nu niet aktief, ze moeten wachten tot het element van ~ verstuurd is. Het adres van het diagonaalelement a j j waardoor gedeeld moet worden komt in VL, het adres van c. komt in VR. J (k+l) (k) Voor updates van c i geldt c i := c i - a ij * x j • Dit is vrijwel identiek aan de berekening van een update uit de decompositiefase, met vektoren van lengte 1. Er is een klein verschil, inplaats van een element uit M wordt nu het element x j L gebruikt dat zich in XREG bevindt. Voor dit geval wordt C2 gel~k aan 1 gemaakt. Het adres van a ij komt in VR, L wordt 1 en het adres van c i komt in RES. 2.3. Voorbeelden Met het ontwikkelde programma zijn vier matrices "verwerkt", de matrix uit bijlage II (testmatrixl), een iets gewijzigde testmatrix2, de matrix geassocieerd met de graaf uit (71 en de matrix behorende bij het IC fA 758, met resp. 10, 10, 46 en 192 knooppunten. Van de eerste matrix is de computeruitvoer volledig opgenomen in b~lage III, van de overige matrices aIleen de e-tree, z9als de computer die a f l e v e r t . - . . .
Voor de graaf uit [7] en voor de matrix van de fA 758 zijn in onderstaande tabel (fig. 22.) de executietijden (PT) van de verschillende procedures gegeven, ernaast zijn de t~den nodig voor transport van en naar magnetische schijven (10) vermeld.
- 35 Graaf [7]
46
rang ~
ETREE CRITPATH VECTORS ADDRESS CODES
fA 758 192 PT
PT
10
0.2 0.2 0.4 0.6 3.9
0.0 1.7 2.6 9.1 51.2
10
0.0 2.9 0.6 8.9 7.0 10.3 4.6 50.7 42.9 310.5
fig. 22. Executietijden in seconden. 4
De executietijden voor de procedures ETREE, VECTORS en CODES hangen kwadratisch af van het aantal diagonaalelementen van de matrix, voor de procedures CRITPATH en ADDRESS is deze afhankelijkheid lineair. De programma's werden verwerkt op de Burroughs B7700 computer van de THE, via het interaktieve systeem CANDE. Om inzicht te krijgen in het benodigde aantal processoren en het optredende datatransport tussen de processoren werd een aparte procedure geschreven. Deze lijkt veel op de procedure CODES, maar in plaats van instructiecodes te genereren wordt de werklast en het datatransport berekend, dat bij iedere instructie hoort. De werklast van een vermenigvuldiging en deling wordt hierbij gesteld op twee eenheden, de werklast van optellen, aftrekken en datatransport op een eenheid. In figuur 23. zijn de resultaten van de berekende werklast verzameld. Ook enige gegevens van het systeem USNET, verkregen uit [9J~ zijn hierin opgenomen. Er wordt een minimum en een maximum aantal processoren aangegeven. Het maximum aantal is gelijk aan het aantal paden in de e-tree. Ret minimum kan men natuurlijk stellen op een, maar dan kan geen gebruik gemaakt worden van het aanwezige parallellisme. Bet mini!nale aantal processoren wordt hier berekend door de totale werklast te del en door de werklast die verbonden is aan het kritieke pad uit de e-tree. Voor de L/u decompositie zou in principe dit minimale aantal voldoende zijn als het mogelijkzou zijn om een optimale clustering van paden in weinig processoren te verkrijgen.
- 36 -
aantal pivots testmatrix graaf [7] p.A 758 USNET
10 46 192 1637 betamax e-tree
testmatrix graaf [7] pA 758 USNET
5 11 22 48 fig. 23.
aantal niet diag. elem. 36 202 1338 8948
totaal
vul% matrix
46 248 1530 10585
totale werklast
werklast pad 1
259... 1562 13386 48938
91 367 2735 15311
46 12 4 0.4 aantal proc min 3 5 5 4
aantal proc max -
3 18 81 11~
Werklast.
Tabellen met het datatransport van en naar elke processor op elk tijdstip (time slot) zijn te vinden in bijlage III; voor de pA 758 is echter alleen het totale datatransport in elk time slot gegeven. Het blijkt dat vooral in de beginfase veel datatransport optreedt. Deze situatie is te verbeteren door datatransport, dat uitstelbaar is, te verschuiven naar een later tijdstip.
- 37 3. Hardware 3.1. PDP-ll als Host computer De vakgroep Automatisch Systeemontwerpen beschikt over een PDP-ll/60 minicomputer. Aangezien het de bedoeling is om het systeem met de parallelle processoren aan deze computer te koppelen zullen enige eigenschappen van de PDP-ll bekeken worden[lO). Het systeem beschikt over een 16 bit databus (UNIBUS), waartoe alle onderdelen van de computer toegang hebben. Ook kan men externe apparatuur hierop aansluiten, zoals bijvoorbeeld het systeem met de parallelle processoren. Er kan gerekend worden met verschillende dataformaten (fig. 24.), zoals Integer (15 bit plus teken bit), Long (31 bit integer plus teken bit), Floating Point en Double. Een Floating Point woord bestaat uit een tekenbit, 8 bits voor de exponent (-127.$ p ~ 128) en 23 bits voor. de mantisse. Bij een Double woord bestaat de mantisse uit 55 bits. In beide gevallen wordt nog een truc gebruikt, waardoor het aantal bits van de mantisse met een verhoogd wordt. Bij een genoDmaliseerd Floating Point woord is de eerste bit van de mantisse n.l. altijd gelijk aan 1. Deze bit bevat dus geen informatie en kan weggelaten worden. Bij het rekenwerk wordt dan automatisch een 1 gegenereerd (hidden bit) ter completering van de mantisse. Bet geheugen van de PDP-ll is bipolair, met een toegangstijd van 300 nsec. De PDP-ll beschikt over een Fixed Point ALU, met daaraan parallel een Floating Point Processor (FPP). Alle Floating Point instructies worden door de ALU naar de FPP gestuurd. Bet resultaat wordt uiteindelijk weer door de ALU opgehaald. Ondertussen kan de ALU doorgaan met de uitvoering van andere instructies, mits ze het resultaat van de Floating Point berekening niet nodig hebben. Een single precision (32 bit) Floating Point woord komt overeen met ongeveer 8 decimale cijfers, een double precision woord (64 bit) met ongeveer 17 cijfers.
- 38 -
R._~H--A--C.-_T--'__
[_S.L..I_ _E_-_X_p _ _---=-'l"--;--_ _F __ IS' J'f t ,
Is .!. I~
EX
P
. ~
''1
L
-
-
,
-
fl..
F
O_ _N
lIS,
_~ ,II '"
A __ C._T_'_ _ O_ _ N __
I
o
-
-
-o
,~
H
[--.!..-~:i_ _ IV _~: '"
13
----'I
_ E_ _
If'
'"
fig. 24. Dataformaten. Besloten werd om de paral1elle processoren te ontwerpen voor 32 bit Floating Point woorden. De rekensnelheden moeten vergelijkbaar zijn met die van de PDP-ll. In figuur 25. zijn enkele tijden gegeven voor verschillende Floating Point Processoren. De tijden gelden voor 32 bit woorden en in "mode 0" (register to register) en zijn gegeven in microseconden. PDP
11/34
11/70
FPP
ll-A
ll-C
.AJJD/SUB HUL DIV
8.91 16.2 16.2 fig. 25.
1.65 3.27 4.29
h
0
-
1'1 1'(
0
IS"
-
,~
_
!O
11/60 ll-C' 1.02 1.53 7.00
Rekentijden in fsec.
11/44 Il-F 8.91 16.2 16.2
- 39 3.2. Processor ontwerp 3.2.a. algemeen De hardware voor een processor uit het parallelle systeem werd in wisselwerking met het schrijven en testen van de software ontworpen. Figuur 26. geeft een overzicht van de opzet. De twee geheugens M en MR bevatten de matrixelementen. L Processor PI vormt (tijdens de L/U decompositie) de inprodukten ( * , + ). Het resultaat wordt of naar FI of naar F2 gestuurd. Fl en F2 zijn first in first out registers en ze dienen als buffers, zodat PI niet hoeft te wachteh op data transport. De getallen uit FI worden via de BUS naar een andere processor gestuurd en komen daar terecht in F2. Dit zijn ~e updates voor element en op andere paden uit de e-tree. De getallen uit F2 worden in rekeneenheid P2 afgetrokken van een element uit ML of MR ' en eventueel gedeeld door een diagonaalelement ( - , / ). De resultaten uit P2 worden weer naar de geheugens gestuurd. Op deze manier ontstaat er een pipeline processor. PI kan nu ononderbroken inprodukten blijven vormen, zolang FI of F2 niet vol zijn. P2 verwerkt de resultaten van Pl. De vertragingstijd die ontstaat doordat de getallen eerst de registers Fl, F2 moeten doorlopen is niet belangrijk, omdat deze praktisch geen invloed heeft op de totale verwerkingstijd. In de volgende paragraaf zal blijken dat zowel PI als P2 onafhankelijk van elkaar gebruikt kunnen worden voor de evaluatie van niet lineaire functies. Per processor zijn hier dus twee rekeneenheden voor beschikbaar, hetgeen een gunstige uitwerking heeft op de totale rekentijd. Tenslotte is er nog een XBUS waarlangs elementen van ~ naar alle andere processoren gezonden kunnen worden naar een speciaal register, RI. Het doel hiervan is in 2.2.c. uitgelegd. In de rest van dit hoofdstuk zullen de onderdelen van de processor besproken worden, alsmede de besturing. De getekende datapaden in figuur 26. worden geacht 32 bit breed te zijn.
- 40 -
--
I ....._-t-
I
, ,
,.
----
-..._~x~.~~~u.::::s:.._
-
--1'
~.
•,. &2.-
• &l ~,;;~
M""t\",
HeMOll.'fS
I
" ,u.
PltOC If H IN'S VW'T"S
I
FI
I ~I
'.
ML
~"SI~T.IL"
'T"\-
~"T"""T1!i
I
Mit
8v',.~
, •
I
!
ttrC;I\T5ll, W.TH
r
I
.. r ....
.
~
I
-
-"-
,
---
(1,.1...
--
'II
--,
-
I ...
~1
I I
I
I
Ir ~~
I
I
I
I
I
I
I I I
I
I r
~,.
I
I
,.I
L_
•
,
,.
I
I I
I I
I
pz. A
--- _. _ -
"'l"ltZ-S 'rATIi
CV.,. .. \J'"T"
I
I
r-
flf.ST IAI F/I. 17'
.F~
I
I~
r
I
-.~---.---
..
I
t
"," ..1. -- _ -~ __ --~____
1
I
&1
-
J
~
- 41 3.2.b. ALU Om een keuze te kunnen maken voor de ALUls, PI en P2 uit figuur 26., werden enkele eisen geformuleerd: - 32 bit floating point berekeningen ( *, I, +, -), - snelheid vergelijkbaar met de PDP-II, - mogelijkheid tot evaluatie van niet lineaire functies, - nu of in de nabije toekomst op de markt. De tweede eis, snelheid, sluit het gebruik van een gangbare microprocessor, zoals bijvoorbeeld een 8080, uit. De rekentijden zouden een faktor 100 a 1000 langer zijn als vereist • Zelfontwerp van de ALU behoort tot de mogelijkheden, indien men gebruik maakt van discrete snelle EeL componenten, maar vergt tijd en ervaring. De keuze is ten slotte gevallen op de Am 2903 (Superslice~), een 4 bit slice microprocessor van Advanced Micro Devices [111. Een aantal van deze bipolaire microprocessoren kan aan elkaar gekoppeld worden om 32 bit berekeningen mogelijk te maken. De Am 2903 is een 48 pins microprogra~neerbare ALU met een aantal extra faciliteiten (fig. 27.), speciaal geschikt voor aritmetisch georienteerde processoren. Zo bevat de chip zelf logika voor vermenigvuldigen, delen en normalisatie van floating point getallen. Verder een aantal nuttige registers en 16 interne werkregisters, die willekeurig adresseerbaar zijn (RAr:;). Momenteel (1980) is de Am 2903 verkrijgbaar. Pin compatibele opvolgers worden de Am 2903A, Am 2903B etc. Deze opvolgers zullen steeds sneller zijn dan hun voorgangers, bijvoorbeeld de Am 2903A zal 30% sneller zijn dan de Am 2903. Deze Am 2903 kan bedreven worden met een klok van ongeveer 10 !11Hz. Voor de totstandkoming van een deling of vermenigvuldiging is een klok cyclus per bit nodig. Handig is ook dat data wia twee inganespoorten, DAO_ en DB _ ' O 3 3 is aan te bieden aan de ALU (gelijktijdig). Informatie ui t de eerder genoemde geheugens M en M kan dus gelijktijdig aangeboden L R worden. Ook is het mogelijk de ALU te laten werken met twee willekeurige
..
- 42 -
--,
--_.--.---- --------- ------ _. -- ----
I
'. I"'JA IN AQ
4
:..
_A
C>-----,.L--
ADnftt
~u
3
I - - - - - - ".... <--<J
S~
nOM
.. A"ll!t?lJ] ONI Y
OE8
0---------<::1
000 _ J
fA [::>>--------·+--1
GIN
C > - - - - - - - t - - -.....
aP/OVfi
Cn
/'--------t--c:l SlUg
,.-------..,-&:1 $1°3
~I-----+--01°3
~f----
6fY
• D--..--,--IINSHHJC:TUJN OECHJf
~ ;,iss
•
•
CP ~---a
Vee ~---o
l
r- --, ~~703
'_-r---------'
GND
----0
Noles' 1. DI\o.J's Inp"~ only on 11"'2903. but is Ita pori on Am29203 2. 0 ... Am2903, 2010 logic IS c.('nneeled to Y, ane, Ille OEy buHBr wpn-030
fig. 27.
Blokschema Am 2903.
interne registers of een intern register en een van de datapoorten. De instructies voor de Am 2903 bestaan uit 9 bits, 1 -1 • 0 8 Behalve zeven aritmetische en negen logische operaties op twee 4-bit operanden, z~n nef,en speciale functies mogel~k, die de vermenigvuldiging, deling en normalisering ,uitvoeren.
':
.
- 43 -
Zoals vermeld is de Am 2903 microprogrammeerbaar. De instructies en eventuele routines voor niet lineaire functies worden opgeslagen in een microprogra~nageheugen. Door dit geheugen direct of indirect te adresseren kan men Am 2903 dwingen om bepaalde instructies uit te voeren. Meestal zal de adressering indirect z~n en gebruikt men een microprogram controller, b~voorbeeld de Am 2910, om een aantal instructies aan de microprocessor aan te bieden (fig. 28.). De voordelen hiervan zijn: - met een opdracht aan de microprogram controller kan men meerdere instructies laten uitvoeren • - conditionele sprongen, bijvoorbeeld afhankelijk van bepaalde controlesignalen, naar elke gewenste plaats in het microprogramma geheugen worden automatisch verzorgd. - In de opzet volgens figuur 28. wordt t~dwinst behaald doordat instructies zoveel mogelijk veer de executie in een speciaal register (pipeline register) gezet worden (instruction look ahead). De microprocessor hoeft dan niet te wachten tot er een instructie uit het geheugen geselecteerd is, maar kan deze meteen uit het register betrekken.
.
3 c:c
r?
MU)(.
'1\
.,
A~
.....
2.t,)IO
K(OK
:r
A+I
lATI W\i c.,... p
1'0'
rOo."""
cLt.. vo~e ... ek \\.,~,
,t:CA) : cL... o..tc~",e l.
~
.....
S (A)
l:I I
,,,,~h,,,c.4,~
J:(A1") :
~~"'Of'y
PIPEL",' E
~ ~¥'e~ "~Io\ cle. v,~e",a'.t
~
:
(A+')
IlE)
I
...,
~' rCA)
'\
....,
A"",1,03 ALl.ol
1
SCA)
Y
STATV~ RliS .It S (A-I)
fig. 28. Microprogram controller.
h.,\
S'+o.~"sl.o)oo .. d
c..he c.~'.e
44 -
Tot slot wordt als voorbeeld gegeven de algoritme en microcode voor een 2's complement 16 * 16 vermenigvuldiging (fig. 29.). Een volledige beschr~ving van de mogel~kheden van de Am 2903 is hier niet mogel~k, hiertoe z~ verwezen naar (111.
STAltT :
o ~.. to M"l-t'tl;co.... c! i
R,
I1 ..U'flier
Jl t
i
I 5,. ~ cTR.
2.' S
Coif PL af1,/IIT MUL'TIPl.Y
2' S
COI1PlGMI5NT MV1.T,PLY
LA C;T C '( c. L E
ellO:
memory address n
n+l n+2
Am 2910
instr.
data pipeline
OOE 16
LDCT RPCT
n+l
X
X
Pr..t"c* (MS)
i... (0
P... oI"c-+-
(l.S) t1 .. t4"hc ..."J
~... i ...
H"l"it'''c"
h .. R~
<J' It,
comment load counter & R 4Q 2 2's complement mUltiply 2's complement mUltiply (last cycle)
fig. 29. 2'8 complemeut 16
*
16 vermenigvuldiging.
- 45 3.2.c. geheugens In feite hebben we te maken met twee verschillende geheugens, de datageheugens M en MR ' en het instructiegeheugen 1M, dat L de instructies voor de processorencbevat. Dit laatste geheugen dat bestaat uit 64 bit woorden moet niet verward worden met het microprogrammageheugen van de Am 2903. Bedoeld is het geheugen dat de instructies voor de L/u decompositie etc. bevat. In tegenstelling tot de datageheugens hoeft dit geheugen niet bijzonder snel te zijn. Omdat er oak geen sprongopdrachten in deze instructies voorkomen kan hier een instruction look ahead systeem gebruikt worden om de volgen&e instructie alvast uit het geheugen te selecteren, terwijl de voorgaande in uitvoering is. Gangbare geheugens, zoals die bij normale microFrocessorsystemen gebruikt worden, met een toegangstijd rond de 1 microseconde, zijn hiervoor goed te gebruiken. De datageheugens N en MR ' elk 32 bit breed, dienen weI snel L te zijn. Ze kunnen aangeroepen worden door zowel PI als P2 uit figuur 26. Om conflicten uit te sluiten werd bepaald dat PI de geheugens kan gebruiken als de klok hoog is en P2 als de klok laag is. Bij een klokfrekwentie voor de Am 2903 van 10 MHz moet een cyclus van 100 nsec dus twee geheugencycli van elk maximaal 50 nsec bevatten. Op deze wijze hoeven PI en P2 nooit te wachten op toegang tot het geheugen. Snelle geheugens zijn meestal EeL (emitter coupled logic) geheugens. Bij gebruik van dergelijke geheugens, die ook veel energie verbruiken, zou een tijd kostende conversie naar de TTL nivo's van PI, P2, de registers en de besturing nodig zijn. Momenteel zijn ook TTL geheugens beschikbaar, die snel genoeg zijn. De keuze viel daarom op de 93F425 van Fairchild. Dit TTL geheugen bevat 1024 * 1 bit en is voorzien van TRI-STATE uitgangen. Belangrijke signalen voor een geheugencyclus zijn getekend in figuur 30. Het aantal benodigde geheugenplaatsen hangt af van het aantal matrixelementen en het aantal parallelle processoren. Zou bijvoorbeeld de matrix voor de )l.A 758 verdeeld worden over
- 46 I
I
-rT7'YI!~~710~~~-~--"~$~ I
address valid
I J
tll.-_--..:..._~Y---l' I
Z!!II//!//*,ff~ (;
)
'5" "" S e"
fig. 30.
chip select, CE
I
: (
data valid
• )
.to .... sec Gehe~gencyclus
93F425
acht of meer processoren dan zouden 2 * 132 plaatsen per processor voldoende zijn. yoor het USNET systeem zouden ongeveer vijf maal zoveel plaatsen nodig zijn. De 1024 plaatsen van de 93F425 zijn dus zelfs voor dit grote systeem ruim voldoende. Het aantal plaatsen in het instructiegeheugen moet ongeveer drie maal zo groot zijn als dat van het datageheugen, hetgeen bleek uit tellingen aan de matrices. 3.2.d. registers en buffers De registers Fl en F2 (fig. 26.) zijn van het type first in first out. Ze dienen als databuffer tussen de rekeneenheid Pl en de BUS of P2. Een TTL IC dat hiervoor in aanmerking komt is de SN74LS227, een 16 * 4 bit FIFO regis~er. Het IC kan met een klok van maximaal 10 MHz bedreven worden. Er is nog niet bepaald hoeveel plaatsen er in totaal nodig zijn in Fl en F2 om te voorkomen dat de registers geheel vollopen. Registers met een plaats zijn Rl ••• R5. Ze dienen om tijdelijk getallen op te slaan nadat deze uit het geheugen geselecteerd zijn. De rekeneenheden Pl en P2 kunnen deze getallen dan snel ophalen uit de registers op het moment dat ze nodig zijn. Gedacht wordt aan D-flipflops voor deze registers met TRI STATE uitgangen, zoals de Am 2954, die acht D-flipflops bevat. De maximum klokfrekwentie voor dit IC is 100 l'1Hz. In het schema van figuur 26. zijn tenslotte nog een aantal TRI STATE buffers, Bl ••• B7, opgenomen. Zij dienen als schakelaars,
- 47 die verschi11ende datapaden in de processor met e1kaar kuIh~en verbinden. De buffers B3 en B4 zijn bidirectionee1, de overige buffers 1aten de data maar in een richting door. Een bruikbaar Ie is bijvoorbee1d de 74125.
3.2.e. bussen Beha1ve de bus waar1angs de Host computer toegang he eft tot de geheugens van de processoren (niet getekend in fig. 26.) zijn er twee bussen die de prucessoren onder1ing verbinden. be eenvoudigste bus is de XBUS, waarlangs te1kens een geta1 uit een van de geheugens naar de registers R1 van al1e processoren gezonden kan worden. De BUS waar1angs partie1e inprodukten naar een andere processor gestuurd worden, vereist een besturing die in dit afstudeeronderzoek niet uitgewerkt is. 3.3. Besturing '.3.a. niet 1ineaire functies Afhanke1ijk van de 64 bit instructiecodes zu11en de processoren bepaalde taken moeten kunnen uitvoeren. De hiervoor benodigde besturing zal in de rest van dit hoofdstuk behande1d worden. Voor de L/U decompositie is deze besturing vrij gedetai1leerd uitgewerkt, echter a1leen om te beoorde1en of een degge1ijke besturing rea1iseerbaar is. Schema's met betrekking tot de datapaden in en de besturing van de processoren, voor achtereenvo1gens niet 1ineaire functies, L/U decompositie en berekening van~, zijn a1le verzame1d in bij1age IV. Voor de berekening van niet lineaire functies zijn per processor twee rekeneenheden, P1 en P2 in figuur 26., beschikbaar. Deze berekeningen dienen p1aats te vinden vear de L/U decompositie. Hiervoor werd een apart time slot 0 ingevoerd. B10k T in de instructiecode (2.2.b.) is dan dus nul.
- 48 Verondersteld wordt dat het argument voor de functie staat op de geheugenplaats waar het resultaat van de berekening terecht moet'ikomen. Dit adres alsmede de code voor de soort functie dient dus ook in de instructiecode opgenomen te worden. Zogauw een van de rekeneenheden klaar is met een functieevaluatie kan de volgende instructie verwerkt worden. Op een gegeven moment is deze volgende instructie de aerste instructie voor de L/U decompositie. Deze dient uitgevoerd te worden in time slot 1, de inhoud van blok T is nu 1. De processor vergel~kt dit met de stand van een centrale teller) TIME, die het aktuele time slot aangeeft. B~ verschil wordt de instructie niet uitgevoerd, maar treedt een wachttoestand op. Alsalle instructies voor een bepaald time~slot door aIle processoren voltooid z~n, wordt de stand van TIME met een verhoogd. Een processor die zich in timeslot 0 in de wachttoestand bevindt, kan in principe gebruikt worden voor de evaluatie van functies ten behoeve van andere processoren. Het argument en de instructiecode kan dan via een verbrede XBUS van de ene naar de andere processor gezonden worden. Het resultaat wordt dan via Fl weer naar het geheugen van de oorspronkel~ke processor gestuurd. Een gedetailleerde besturing hiervan is nog niet ontworpen. Met behulp van de zelfde besturing zouden ook een aantal losse functiegeneratoren gebruikt kunnen worden om de totale t~d voor functieevaluatie te bekorten. Schema's met de datapaden : IV-I .•• IV-5. 4
3.3.b. L/U decompositie De schema's op pagina's IV-6 ••• IV-IO geven een overzicht van de datapaden t~dens de L/U decompositie. PI vormt inprodukten van r~tjes getallen uit ML en MR. Ret resultaat komt of in Fl of in F2 voor verdere bewerking in P2 in een andere processor of in dezelfde processor. In F2 kunnen ook getallen komen die van een andere processor afkomstig z~n. De getallen uit F2 worden door P2 afgetrokken van een getal uit ML of MR. In sommige gevallen voIgt dan nog een deling door een getal uit ML • Het resultaat wordt weer naar de geheugens teruggestuurd.
- 49 -
Ook is het mogel~k dat er;als enige bewerking een deling nodig is, bijvoorbeeld om getallen uit de eerste kolom van L te bepalen. Om de .~·besturing niet nodeloos ingewikkeld te maken wordt dan toch de volgorde inprodukt in PI, F2, aftrekken inP2 en delen in P2 aangehouden. Het inprodukt wordt dan gevormd met vektoren met lengte nul (blok L in de instructiecode is dan nul). Het resultaat, nul, wordt via F2 naar P2 gestuurd en daar afgetrokken van een element dat daarna gedeeld wordt door een diagonaalelement uit de matrix. Deze methode kost weinig extra tijd, omdat PI aIleen maar een nul naar F2 hoeft te zenden en daarna aan de volgende instructie kan beginnen. • Het schema op pagina IV-II geeft een overzicht van de b~ de L/U decompositie horende besturing. Verschillende blokken zijn nader uitgerwerkt op de daarop volgende paginats. Parallel aan FI en F2, dataregisters, staan identieke registers die de adressen bevatten, waar de verschillende getallen naar toe moeten, d.w.z. van welk getal ze afgetrmkken moeten worden. De adressen in de blokken VL en VR adresseren rechtstreeks de geheugens ML en MR. Hetvsignaal Cl bepaalt of er een getal uit ML of uit Rl gebruikt wordt als invoer voor Pl. 3.3.c. berekening van
~
De berekening van x valt uiteen in twee delen, die:in verschillende time slots (om en om) plaats vinden. Eerst wordt een getal uit MR gedeeld door een getal uit M • L Dit kan gebeuren in PI, die het resultaat rechtstreeks naar M R stuurt. Tevens wordt dit resultaat naar de registers Rl in aIle processoren gestuurd. Daarna worden op dezelfde w~ze als b~ de L/U decompositie inprodukten gevormd, nu met vektoren ter lengte 1 en met een getal uit MR en een getal uit Rl. Via F2 wordt het resultaat in P2 van een getal uit MR afgetrokken en het resultaat weer naar MR gestuurd.(IV-17). Literatuur met betrekking tot het ontwerp van aritmetische processoren, rekenalgoritmen en het ontwerp van microprocessorsystemen is onder meer [121, [13J, [14] en [15].
- 50 -
4. Niet lineaire functies 4.1. Wortelfunctie
Vi
Voor de berekening van b~voorbeeld en eX zullen routines geschreven moeten worden. Er z~n verschillende methoden waarop deze routines gebaseerd kunnen worden.(l61. In di t hoofdstuk zullen twee methoden behandeld worden, de iteratieve methode en de methode van rationale benadering door polynomen. Tevens wordt enige aandacht besteed aan range reduction. De evaluatie van ~, x)00geschiedt meestal met de methode van Newton. Men kiest een geschikte startwaarde YO en berekent dan de getallen Yl'Y2'Y3' ••• ' die gedefinieerd worden door de recursieve relatie k=0,1,2, ••• Dit is een speciaal geval van de Newton-Raphson iteratieformule F(Yk) Yk+l := Yk - F'(Yk} die wordt gebruikt om de vergel~king F(y) = 0 op te lossen, met in dit geval F(y) = y 2 - x. De methode convergeert kwadratisch naar de oplossing Y =~. Dit betekent dat als Yk dicht genoeg b~ de oplossing x ligt, dat dan het aantal correcte c~fers in Yk+l ongeveer tweemaal zo groot is als dat in Yk. Omdat de methode convergeert voor elke positieve startwaarde YO kan men een routine schr~ven, die gebruik maakt van een vaste startwaarde, b~voorbeeld YO = 1. Na iedere iteratie kan dan getest worden of de gewenste nauwkeurigheid bereikt is. In de prakt~k bl~kt de convergentie zo snel, dat het beter is om de convergentietest achterwege te laten en een vast aantal iteratieslagen uit te voeren. In de subroutine kunnen dan aIle statements achter elkaar gezet worden indien er voldoende geheugenruimte beschikbaar is. Er zijn dan geen conditionele sprongopdrachten nodig.
- 51 -
De convergentie is het snelst als YO reeds een goede benadering is voor de oplossing. Door x in een beperk~ interval te nemen (range reduction) kan dit makkelijker bereikt worden. Waarden van x buiten het interval kunnen dan berekend worden met behulp van radix tables. Voorbeeld: Neem x in het volgende interval: 0.5.$xS2
Kies voor YO l. ,
'I<
, c = (8 "- 1)
yO: = x/2 + c
2
4
De waarde c is bepaald met een minimaxmethode en zorgt dat de maximale fout in de eerste slag minimaal is, hier < 0.36 • Na 3 iteraties is de absolute fout kleiner dan 0.2 * 10-13 , na 4 iteraties is de fout kleiner dan 0.2 * 10- 27 • Ret rekenwerk dat hiermee gepaard gaat is vermeld in onderstaande tabel (fig. 31.), waarin SHIFT delen door twee voorstelt, dat gedaan wordt door het binaire getal een plaats naar rechts te schuiven. rIT 3 4
DIV
ADD
SHIFT
3 4
4 5
4 5
fig. 31.
Bewerkingen voor
Indien x bui ten het interval reduction te worden toegepast:
'R =
bk
x.
o. 5 ~ x ~ 2 ligt dient range
VXb- 2k = bk • Vb. VXb- 2 (k+l)' 2
met 0.5 ~ xb- (k+l) ~ 2 ...., 2 De functieV xb- (k+l) kan nu in enkele slagen berekend worden en moet dan vermenigvuldigd worden met bk.'Vb om ~ te verkrijgen. Bij floating point representatie is x = m * 2P , met o. 5 ~ m < 1, en dus ook o. 5 ~ m ~ 2. De mantisse m kan dus zonder rneer gebruikt worden voor de bepaling van de wortel. Deze wordt daarna verrnenigvuldigd met ~.
- 52 -
'fiP
\'laarden voor kunnen in een tabel worden opgeslagen. Aangezien peen geheel getal is, met voor de PDP-ll -128 ~ P ~ 127, kan p gebruikt worden als wijzer voor de tabel p~~. De tabel dient dan 256 plaatsen te hebben. Dus :
2£. = V;; * ~
~ tabel, 256 plaatsen
\
\-.---..-,,') berekenen.
4.2. E-macht
Vi
Uitgezonderd worden de ~eeste andere functies, zoals eX, op een niet iteratieve manier geevalueerd. de functie wordt dan benaderd door een polynoom of door een rationale functie van polynomen. De benadering is echter in het algemeen slechts geldig in een klein interval voor X. Door op een slimme manier range reduction toe te passen kan de functie geevalueerd worden voor elSe gewenste waarde van x. Indien x in een beperkt interval ligt hoeft de benadering van de functie maar uit een beperkt aantal termen te bestaan om de gewenste nauwkeurigheid te bereiken. Voorbeeld: Benader eX door een polynoom van graad x2 xn +
2l + ••• +
n~
stel dat x ligt in het interval [a,b) en dat geeist wordt dat
I
.....;.;Pn_(x_)_-_eX \ -7 X < 10 e De kleinste waarde van n waarvoor hieraan voldaan kan worden is voor verschillende intervallen in onderstaande tabel aangegeven.
[a, b]
n
to, 1/ 4J
4 5
[0,1/21 [0,11 [0,21 [0,3] [0,4J
6 8 9 11
fig. 32. Verband interval en graad polynoom eX.
- 53 2
n
Polynomen van de vorm Pn(x) = a O + a 1 x + a 2x + ••• + anx kunnen voordelig berekend worden met de regel yam Horner:
Pn(x) := « ••• ~anx+an_l)x + ••• + a 2 )x +a1 )x + a O • Het aantal bewerkingen is n vermenigvuldigingen en n optellingen Een andere methode is om de functie in het beperkte interval te benaderen door een breuk van de vorm Pm(x) / Qn(x), met Pm(x) en Qn(x) polynomen van de graad m en n. Door de breuk te schalen, zodat de eerste coefficient in een van de p&lynomen 1 is kan een vermenigvuldiging uitgespaard worden. In [17] worden vele tabellen gegeven voor dergelijke benaderingen, voor verschillende functies, intervallen en nauwkeurigheden. 'Een benadering ui t [17] voor eX lui'dt: eX
=1
2xP(x 2 ) Q(x 2 ) _ xP(x 2 )
+
Precision 12.49 17.49 22.69
N
M Index
1 1 2
1 2 2
1800 1801 1802
, range [0,1/101
MUL
DIV
ADD
SHIFT
4 5 6
1 1 1
3 4 5
1 1 1
Met Precision = 12.49 wordt bedoeld dat de absolute fout kleiner is dan 10 12 • 49 • De getallen onder Index verwijzen naar een tabel met waarden voor de coefficienten voor P en Q. Bijvoorbeeld Index = 1800: P POO + POlx 2 , Q = QOO + QOlx 2 + Q02x 4
=
POO POl QOO QOl Q02
(+3) (+2) (+4) (+3) (+1)
EXPEC 1801 +.84006 68525 +.20001 11415 +.16801 33705 +.18001 33704 +.1
36483 89964 07296 07390
23940 56893 64841 02280
67033 54 44681 7 539
De getallen tussen haakjes geven de roacht van tienwaarmee het erachterstaande getal moet worden vermenigvuldigd.
- 54 Een techniek voor range reduction voor eX is de volgende. Er wordt uitgegaan van een base 16 floatin~ point rekenmachine en er is een benadering beschikbaar voor 16- z , 0 ~ z ~ 1. De functie eX, voor aIle x, wordt dan verkregen met: bereken y = -x log16(e) en n = (yJ (n is het grootste gehele getal dat kleiner is dan y). bereken z = y - n = y - [y], dan is 0 ~ z .! 1. bereken 16- z • Dan is eX = 16- n • = 16- n .16- z immers eX = 16- y = ~ berekenen ---~'> tabel z Aangezien ~16-z< 1 is 16- (bij benadering) de mantisse in de floating point representatie van eX, en -n de exponent. Een benadering voor 16- z voor een base 16 machine is
l
n
l",..
P9(z) = 1 - 2.77258729 z + 3.84357669 z2 - 3.55169683 z3 + 2.45881065 z4 - 1.35322234 z5 +.60413322 z6 - .21187238 z7 + .05181070 z8 -.00645242 z9 met
Ip 9(z) - z16l 16-
Z \
< 2-25
voor 0
~
z
~
1.
In dit hoofdstuk werden slechts enkele mogelijkheden aangegeven voor de berekening van niet lineaire functies. Ret is dan ook verre van volledig. De bedoeling was uitsluitend om enig inzicht te verkrijgen in de beschikbare rekenmethoden en de daaraan verbonden rekenlast.
- 55 5. Slotopmerkingen De in hoofdstuk 2 beschreven programma's z~n zonder meer bruikbaar voor de data toew~zing aan en het genereren van instructiecodes voor de parallelle processoren. De programma's w~zen echter aan ieder pad uit de e-tree een eigen processor toe. Voor een efficient gebruik van de hardware dient een clusterfung van een aantal paden in een processor te worden verwezenlijkt. Verder onderzoek op dit gebied is dan ook gewenst. Een buscontroller voor de regeling van de communi~atie tussen de processoren onderling dient ook nog ontworpen te worden. De besturingslogika van de processoren is nog niet volle dig in detail uitgewerkt. Verdere detaillering zal naar verwachting geen grote :problemen met zich mee brengen. Het onderzoek naar de mogel~kheid om niet lineaire functies te evalueren leverde een aantal methoden Ope Twee voorbeelden van veel voorkomende functies werden in dit verslag opgenomen.
- 56 6. Literatuur 1. Nagel, L., "SPICE2, A computer program to simulate semiconductor circuits". 2. "Contents of SPICE:S/tJIAHUAL", Rdok 5186, THE-RC 29627. 3. Jess, J.A.G., IINetwerksimulatie", collegediktaat THE. 4. Veltkamp, G.W., Geurts, A.J., "Numerieke methoden I en II", collegediktaat THE. 5. Wing, 0., Huang, J.W., "A parallel triangulation process of sparse matrices", Proc. 1977 Intern. Conf. on Parallel Processing, pp 207-214, Aug. 1977 • 6. Wing, 0., Huang, J.W., "A computation model of parallel solution of linear equations", IEEE Proc. of the Intern. Symp. on Circuits and Systems, pp271-274, 1979. 7. Jess, J.A.G., "Some new results on decomposition and pivoting of large sparse systems of linear equations", IEEE Trans. Circuits and Systems, Vol. CAS-23, pp 729-738, Dec. 1976 8. Jess, J.A.G., Kees, H.G.M., IIA data structure for the parallel organisation of L/U decomposition", IEEE Proc. of the Intern. Symp. on Circuits and Systems, pp 776-779, April 1980. 9. Kees, H.G.H., Jess, J .A.G., "A study on the parallel organisatiol of the solution of a 1600-node network ll , Proc. of the 1980 IEEE Intern. Conf. on Circuits and Computers. 10. PDP-ll Processor Handbook. 11. "Am 2900 Family Data :Sook ll , Advanced Nicro Devices, 1979, importeur Arcobel Oss. 12. Hwang, K., "Computer arithmetic ll • 13. Stein, M.L., JVIunro, W.D., "Introduction to machine arithmatic". 14. Hill, F.J., Peterson, G.R., "Digital Systems ll • 15. Electrical Research Ass., "The engineering of microprocessor systems". 16. Fike, C.T., IIComputerevaluation of mathematical functions". 17. Hart, J.F., "Computer approximations ll •
.
BIJLAGEN
ISMS 201 multiprocessor systeem II III IV
Voorbeeld e-tree Software Processor ontwerp
Bijlage I Siemens 3M3 201 multiprocessor systeem
EUROMICRO JOURNAL 5 (1979) 48·52
to EU ROM lCRO and Norlh·Hollilnd Publi,hing Company
SMS 201- A Powerfull Parallel Processor with 128 Microprocessors R. Kober and C. Kuznia Siemens AG. 0110 Hahnring 6. 0·8000 Munich 83. Fed. Rep. Germany
The architecture, organization and application of the SMS multiprocessor system. an MIl~struc ture for high-speed numerical computations, are outZined. The now operational SMS 201 with 128 combined microcomputers. each containing an additional arithmetic processing unit. is capable of e;cecuting 550000 floating point operations per second (FWPS). A similar system. named SMS 80. with a variable number of modules, will be available soon for interested usars. A future El-!S system using high SPlied LSI circuits, tits newly d.esignl1d SMS 3, will have a speed of 18 million FWPS.
1. INTRODUCTION Many motivations lead to investigations of multiprocessor systems, for instance: to build a cheap computer system, to increase reliability or to achieve high processing power [1 - 9] . The Structured Multiprocessor System (SMS) is a parallel arChitecture, which (besides beeing useful for nonnumerical applications) mainly pursues the high speed computer idea for the solution of large numerical problems aD - 13] Typical applications are picture processing, solving of partial differential equations for weather prediction or aerodynamic problems etc, circuit simulation, and control or supervision of comple~ processes [5 - 14 - 18] .
leN
... Fig. 1. SMS-Architecture. The communication memories are one main characteristic of the SMS concept. They accomplish a soft coupling of the modules. Each module has only access to its own CH. All cOlT1llunications between the modules, and between modules and main processor are controlled and carried out by the main processor via these eMs. The second main characteristic is a self synchronized computing scheme in a repetitive sequence of three phases: - the control phase, in which the main processor selects and starts the module programs, - the computation phase, in Which the modules carry out their tasks, and - after all modules have" completed their tasks -, - the communication phase, in which the results of e~ch module are broadcast to the other modules. This clear and straightforward organization avoids problems 1ike access conflicts, synchronization problems and deadlocks [7,10J. Nevertheless a high computing power can be achieved. For homogeneous problems, that is for equal module tasks (in co~tent and execution time), the computing powe~ can be characterized by: - the instruction stream of all module processors (~!PS, MFLOPS) (a), - the data exchange stream (MBPS) (b). In the next section, we will give an account of these characteristics for a realized and for a future SMS >ystem.
2. ARCHITECTURE AND ORGANIZATION OF THE SMS The SMS concept combines the advantages of array processors of the ILLIAC IV-type [2] on one side and of "decentralize~' multiprocessor systems 1ike the C.mmp or the Cm [7, 8J on the other side. If features a central control of the processor modules as known from the array processors. It allows a clear organization of software. Bu the level of paralleliSM is high, namely at the program level, as used in decentralized multiprocessor systems. This fact has two important advantages. Firstly, it is possible, to translate a rea1 prOblem, consisting of a number of coupled sub-problems, i~ a natural way into sub-programs for the prOCF.ssor modules. (!n section 4, we descr~be th~ task allocation scheme for the example of t~~ global weather forecast). Secondly the amount of data exchanges oetween the modules, repres~nting the real interactions between the su~-problems, is small compared to the amount of ca'culatio~ done by eacn module task. Figure 1 shows the architecture of the SMS. A number of identical modules, each co~sisting of a processor PR with program and oi'ta memory, and of a communication memory cr~, a'·~ connected via an interconnection network ICN "0 a main processor MPR. 48
I
...
49
R. Kober
3. PRESENr AND fUTURE SMS SYSTEMS In order to study the architectural aspects of large multiprocessor systems, the SMS 201 with 128 8080-based microcomputer modules and a total memory capacity of 2.5 Mbyte has been implemented (see fig. 2). (a) MIPS Million Instructions Per Second HFLOPS Million Floating Point Operations Per Second (b) M8PS Million Bytes Per Second Fig. 3 shows its block diagram: 8 groups of 16 modules each are connected to a minicomputer representing the main processor [12J. The system, up and running since autumn 1977 provides a perfonnance comparable to large main frame systems, except for the limited floating-point-arithmetic capabilities of the 8 bit-microprocessors. But it is now improved by a factor of about 20 by addi ng a dedicated I-chip Arithmetic Processing Unit (APU) to each module. Recently, a concept for a new, very powerful system has been designed. The SMS 3 will provide a performace enhancement of about 20x - 30x compared to the SMS 201 with APUs. This is achieved by: extending the module number, - using more powerful modules: • faster components (bi-tslicemicroprocessors). • greater word length. speeding up data exchanges: double-word bus, communication memory with double-word interface, faster bus cycle, special communications processor [12]. The performance characteristics of the SMS 201 with and without APUs, and of the SMS 3 are summarized in Table 1. An average module processor utilization of 80 1 is assumed.
.
[f·~~'~~"'t~;\.~·~ .I_~. ~ ~.c
•
r
t. .~ :.'
I:~'
f-
"t,. ,
'0
t.' .' '~::"
;..;
.-
-
11------5¥S 201
"
..
. "~
'. .-------11
,
'..
C- '.
c;;:.
'.
"
Fig. 2. SMS 201 multiprocessor System with 128 modules.
mi~rocomputer
",owt. array
00 .................. 1--' ...... 0 OUl-JWL..JWL...JwwwOD
32 48
JO 0[5[5[5 0CHS [5 [5 eH56 64
'd L..J"'''' L..l L..J 'w 0
L..J L...J '-,J L..I UW L_JL_J
~ 80
lIJ[5[5[5[5 [5 [5[5[56
, 0 ~
~
-~[5(566[5[50[5[5[5[5[5[5(5[56 n m
_,'5iJiY' Jo[5(5[5[5[5(5[50m
m -------------_.--..:..-Fig. 3. B1?ck
diagra~
of
S~5
201.
-----------
50
SMS 201
Table 1 Performance characteristics of SMS Systems (The SUbscripts denote the number of bits).
I
SMS 201
32 MIPS,
so
SMS 3 250 MIPS"
0.03 MFLOPS" o.SS MFlOPS"
Snl.... Data u£hM1Q' SlRalll
40
10
32 MIPS,
IaIIIUClIOII
SMS 2011 AI'U
30
20
10
18
MFlO~z
20 0.\ MBPS
r-
30
Fig. 4 shows a comparison of the instruction stream of sequential, general purpose computers with SMS-tyPe parallel computers. In order to obtain equivalent values for different word lengths, the following conversion has been applied (Again, the subscripts denote the number of bits): 1 MIPS = 1 MIPS6~ = 7 MIPS 16 = 24 MIPS a The SMS 101, an 8 module system {10] reaches the minicOmputer class; the SMS 201 has an instruction stream comparable to present mainframe computers. The SNS 3 wi 11 surpass them for many application problems. Further improvements on the parallel processor side will be possible soon by progress in LSI-technology, whereas further speed-up in sequential processors will be slow due to phys i ca1 limits [61. 4. IJSING THE SI·1S - EXAl1PLE WEATHER FORECAST The problem structure of the applications ment i one din i t i ally, is the f 011 owi ng (11]. Many elements. parts of the whole system, interact with each other in a fairly simple way. The translation to a parallel processor leads to subprograms for the modules '''elementary tasks");
.l. MIPS ~ \0'
SMS 3
I largl SCill. CampUII,.
I
10'
SMS 201 I
Mldium Scali Campuills
10'
MlnltllmpUll1S
10"
MicracampulllS
10"
j
SMS \0\ i
;:,.~~..,.....--,
--r!':;+,:;;:
3.5 MaPS
0.1 MBPS
~:"""'J.,-.-"
I
i---.
FIg. 4. Comparison of instruction stream; MIPS Mio Instructions Per Second.
xt
_-
,_~.' ~~
-
-,.....,...,-_ ._
j·"!-r~~~ 't"~',
40
50
Fig. 5_'. Horizontal structure of the prognosis model. the real interactions are reproduced by data exchanges between the modules. We want to describe that translation, which means the programming of the SMS, fo~ a weather forecast model. This has been the first application of the SMS 201. The numerical model of the atmosphere, which is a finite difference approximation to partial differential equations {IB], subdivides the northern hemisphere by a 3-1ayer grid of 2.000 mesh points each. Fig. 5 shows the horizontal structure of the prognosis model, which has been adapted from a model used by the u~rman Weather Service (17]. The weather forecasting model is implemented on the SMS in the following manner. Each module represents a local prognosis block ~f 3x16 adjacent mesh points. Starting with the initial values th~ system calculates the further development in time steps of 5 minutes real time. After each time step the results of all local areas are d'~tributed to the other local areas, thus reproducing the real world physical interactions by data exchanges between the modules. The data exchange program for the main processor (or the data exchange processor) might be generated automatically by a planned generator. When this tool is available, the user will only have to supply the irteraction grid of each elementary task to Its neighbours and the boundary conditions of the problem. If the problem is homogeneous, then the connection characteristic is identical fc- all tasks, and it is sufficient to sped fy en 1)' the connect; on cha racteri s ti c for one tas k. Fig. 6 shows :he flowchart of the SMS-prognosisprogram. The :orrespond;ng program for a sequential processC''" is o'.Jt1ined in fig. 7. In this ca-se the part' Ie 1 tasks are sequenti a11y computed in a time cor,uming loop. The frame of the program, the re~~titive sequence of discrete timesteps, is id!."tia1 for parallel and sequential processors.
•
R. Kober
51 Tab 1e 2 Computation
times for a 24 hours prognosis. SMS 201
A._s
I
SMS 201 APIJ
SMS J
73.2 ...
42 """
8.4
SIC
34 ...
34 ....
58
SIC
C""'pu1ll1OOS
Conlrol PIIf.. • Olla EUbl1lfll
flUl :
4
Fig.' 6. Prognosis program for the SMS 201. The computation times for a real time interval of 24 hours (288 time steps), measured with the S~lS 201, and extrapolated for the SriS 201 with APU and the SMS 3, are summarized in Table Z. The improvement in processing speed is remar. kable. The computation time of the SMS 201 can be speeded up by a factor of 300 with SMS 3, although the share of time needed for control and data exchanges raises from 4.5 % to 41 :. It is possible to reduce substantially the amount of communication time by more sophisti-
Fig. 7. Prognosis prog;am for a sequential comput~r.
77 OI.
I
7.6_
142,""
cated interconnection networks, introducing parallelism into the exchange. At the moment, however, we do not see the necessity to implement more complicated bus-structures. The reason is that with faster modulecomputers the length of the elementary task will tend to increase too. In this way the user can achieve a higher sophistication of his physical model and better accuracy. So the relation of time needed for data exchanges to the time needed for the autonomous computations will become less critical. 5. EXPERIMENTAL SYSTEM SMS 80 For users who want to work with the SMS an experimental system will be available soon. This system is ca11ed SMS 80; a version with 64 module computers is shown in fig. 8. Any number of modules is possible. depending on the special intention and need of the user. The SMS 80 consists of an 8080 based main processor with extended I/O-capabilities and a powerful floppy-disk-operating system. The module computers are also 80BO-based; they are essentiall~ equivalent to the proven design implemented for the SMS 201. Their floating-point performance has been enhar.ced by adding the arithmetic processing unit AM9511 directly on the module board. The speedup gained by the APU for a typical application is shown in Table 2. The software Which has been developed for the SMS 201 will also support the operation of the SMS BO. The package consists mainly of: pro-
Fig. 8. Exoel'imer.tal system SHS 80 with 64 module '.omput':!'"s.
SMS 201
52 gramming aids to parallelize the_code for special applications, Assembler, fORTRAN-compiler, BCPl, PASCAL (later), and run-time support for the SMS-operation. A number of sample programs for the solution of numerical problems is available. 6. CoNClUS1ON The SMS concept is well suited for a large class of applications with extensive numerical calculations. Taking full advantage of the trend of lSI-technology it will provide a considerable improvement in performance. That will allows us to solve problems, which cannot yet be treated fast enough by present computer systems. The utilization, task allocation and programming of the system is possible in a transparent manner. 4
o.2l
o.3J
Q4]
[15]
(16]
[l7J REFERENCES (lJ M.J. Flynn : Some computer organizations and their effectiveness IEEE Trans. on Computers, Vol. C-21, No. 9, Sept. 1972, p. %3-'360 (2J
OJ
(~
[5J
(6J
(7J
(8)
(9]
DO]
n1]
G.H. Barnes, R.M. Brown, M. Kato, o.J. Kuck D.l. Slotnick, R.A. Stokes ; The IlLIAC IV computer IEEE Trans. on computers, Yolo C-17, No. 3, Aug. 68, p. 746-757 C.H. Radoy, G.J. lipovski ; Switched multiple instruction, multiple data processing. Proc. 2nd symposium on compo architecture, jan. 197~. p. 183-137 G.J. llpovski : On a varistructured array of microprocessors, IEEE Trans. on com¥uters, Vol. C-26, No. 2, Febr. 1977, p. 25-138 G.A. Korn : Back t~ parallel computation; Proposal for a comoletely on-line simulation system using standard minicomputers for low-cost multiprocessing, Simulation, Aug. 1972, p. 37-45 J.W. Wirsching : Computer of the 1980 s It is a network of microcomputers, oiqest of ~apers, Compcon Fall 75. 1975, ~ p. 3-26 S.H. Fuller, D.P. Siewiorek, R.J. Swan: Computer modules; an architecture for large digital modules. ACM SIGARCH, Compo Arch. News, Vol. 2, No. 4, Dec. 1973, p. 231-236 R.J. Swan, S.H. Fuller, D.P. Siewiorek em - A modular muitiprocessor, AFIPS ConL Proc .• Vol. 46, 1977 ~latio~ Co~puter Confe~ence, p. 537-744 J.L. Baer: Nulti~rocessing systems, IEEE Trans. on c~rn~uters, Vol. C-25. No. 12. Dec. 1976, D. 1271-1277 R. Kober, H. Kopo. Ch. Kuznia: SMS 101 A structured multimicroprocessor system with deadlock free operation scheme. Euromicro newslet:er, 2 (1976). p. 56-64 Ch. KUZlll a. H. Kopp : A mode 1 for process communication in parallel processor systems, Proc. !MACS-G!-Symposium on par)llel computers and panllel mathematlcs, ','unlch March 14-15-\1977) p. 339-34Z-------
U8)
R. Kober : A fast communication processor for the SMS multimicroprocessor system Proc. Euromicro symposium on microprocesand mlcroprogrammlng, Oct. 1976, Venlce, p. 183-189 R. Kober: The multiprocessor system SMS 201 - Combining 128 microprocessors to a powerful computer, Digest of papers, Compcon fall 1977, p. 22~-229 M. Tasto : Parallel array processor for digital image processing Optica acta, Vol. 24, 1977, No.4, p. 391-406 M. Inouye: The computer as a wind tunnel, Proc. 2nd USA-Japan Comp Conf., 1975 p. 405-409 F.R. Bailey: Computational aerodynamics IlllAC IV and beyond Digest of papers. Compeon spring 1977, p. 3-11 H. Ropp : Numerical weather forecast with the multimicroprocessor system SMS 201, Proc. IMACS-GI-~ymposium on parallel comeuters and parallel mathematlcs, Munlch Mareh 14-16 (1977), p. 265-268 H.O. Welch: Numerical weather prediction in the PEPE parallel processor, Proc. into conf. on parallel processing, 1977, p. 180192
- 11-1 Op onderstaande matrix (fig. 1.) zal de procedure e-tree worden toegepast. De gegenereerde e-tree met b~behorende label-classes wordt ,gegeven in figuur 2. In figuur 3. z~n bovendien de resterellde takken uit (V,E) gestippeld getekend in de e-tree. Figuur 4. geeft de herordende matrix en de paden in de e-tree na verwisselen van r~en en kolommen. De c~fers in de cirkeltjes z~n de labels van de betreffende diagonaalelementen. Bet rekenwerk dat gepaard gaat met de L/u decompositie van deze matrix is in figuur 5. gegeven.
1
2.
8
3
10
3
ID
fig. 1.
Testmatrixl.
t;J
\j
/0
V (9.)
,
(!.)
V
(1)
If
V
(If )
!>
\j ( ~}
fig. 2.
= [~'1.1J = [10. ! . t = { 6, 3} :
:
~ ~
!
~
J
S"
E-tree en label-classes.
I
- 1I-2 , ...J
I
,,,,,,J t
I I
,1 '0, ,/ I / ' 6,
I
I
I
\IJ., d,
'"s fig. 3. E-tree met alle takken uit (V.E).
f'Q. d 3
Z. 3 =1
po. J. 2-
~
S
,
10
pe.. cl i
~
5"
fig. 4.
Hero~dende
matrix.
, .$'h" .. loS "0 ..
oS,"'<J"* S'.s"
. . "'l:I
If
'Sl:)) - .sS-V
('st,,* ("£" *
* a)b) ':
.
..sS, _ . .U "
t'b'" Io Z"., U,,) :: ~
1.."S'1:
.....
,
..,.s'1 -
....,. ....
So"', _ So"''o'':
U . " / (UV ~ 'Z,S''O - ES"rJ) ::
St,,"*
£I:'Q
I
~t lQ -
(£1." -ff 'U,~ ),1"
(n."" Zt",+
~
.U"
2l" - Itt'Q .. :
"'l7 iI'tl))
-
,
H H
u" /
"'0/
I.t,>
tt '0 ::: tt-o
1
l ! l " .. :
(&1'0'" It'o -
,----.
'lS ~
H .. 'O},,:
u."
::0:
~l.'()
\'lQ
*
1&-0 _
=~
n",
II}:)/
*
a,'I::J:: ~
'8"
off
8,'0 :::
h lQ /
-,
Eo
P
38 b II b
/
tJS "0 .lirli'O
""'",,:0"" """0
1 (atoo"* 1.1,,,,, - '''"0) -=: 8" '" hl" * lab _ ~8'o =~ "8'0
13 '0 ~ ~
I ~ '0
U"o/ 1&'0::
8/:.'O
"t
p-.od
lB'O
£:
9'''0 ::: ""
""')I -
"h~:: l-.""o
"" 1
.' -4'
'"
1/
a.-
..
'It
41 :)
9"'10
' " '0 :::
"'" - "'4 . :
01 '0' lQ /
99\::)
01', '0 : "" 0/'9"
~
"lit
{;
o"o'b / (0/"\0 Jt' (,'~'O _ O/'st.)):: 0/'~'O
s't"Q 01'
*
r. * lQ
"o''I::J -
"0' ~ _ H",=, / (,{,'O
I
S'O' , , : :
So'OllQ
0"01,,: ",
Q,'", '::)
{,.s "0 : : t'O/"G =;
,r
-0
d
"
~
ltl O"V
~
\..5 '0
t.' 01 b
o
41
CJ ""0
'* 0","0 -
"'"-11 -.J
"'>I - ",,, .: "1"
"
It "0
~d
"s." =~
9\", :::
'''" -
:-4'
=~
"'0
'0
h, '" :- ..... ~".?,_ia, 8,'()
hi"
'* J.~"O - 12'0 :: lab H"I h'O =: h"
't~"'Q
'1 '0'
(h''O .. 8''t.)+''t'O*h'O):~ ,"\\}. i- ~ y'''O * b"O :I: 1""')1 ~~ ,
11'0/ I.h'O:: 1"''0
I''';) if" 11'1Q_ to&'()
oJJ "0
" " I p'or" * 0"5"0 - ,robJ: : 9~ '0 .s 'e"" '* 01"" _ $1:1 '0 : : .A, 'lQ
EIob) -: thb
-
h .... ~ _
1
I:
h
.." "0
ts"
S'""O.:
~
u" /
.,~'O ~:
-,
r
~
1
Pi~ ~
* £).,\::)+ "1'011' Z"',,} =~ \,_""'"' I - -I
"5" )''I::J
1
1
.n'O
tS17+
(oS,:,,*, t),~+ .sl,,~ 1".,,)~: 'j,\~
("£b
* ,It,, - oS"" .
)"" *' ''''0 -
.sS..,
:1
""'-01 (It,,,,.. '~b-),ro"O): $,"0
S
+ ~'O'""" ~I'.s"
T TOP •.... ~t
Bijlage III Software
- procedures - voorbeelden
1 2000 ~.~O:l. 0
;.:::0;::'0 ;:.::0:':'·0 ?040
:,:::0::;0 ;:,::c)/o :.;: ():: 0 2()')O ~?:l ()O
PROC~DURE
ETRE~(N,INDEX,RUW,BETA,BADJ);
INTEGER N;INTEGER ARRAY INDEXE*,*J,RDWl*,*J,BETA[*J,BADJ[*,*J; BEGIN INTEG~R V,W,I,K,R,L,T,RC;BOOLEAN ARRAY CANDC1:NJ; INTEGER ARRAY ADJ[0~N+1J;DDOLEAN DLF,DF; I:: :::J'(: :::::1. ; I,JH I LE K 1...1:::n N
DO BEGIN FOR V:=l STEP :I. UNTIL N DO IF BLTA[V]=O THEN CANDLVJ:=TRUE ELSE CANDLVJ~=FALSE; F UI:;: I,):: ::: :I. !3 T E F' :I. UN r I I.. N no IF C t~1 NII I:: V J THE N BEGIN ADJ[O]:=V;FOR R:=l STEP :I. UNTIl.. N DO ADJERJ:=O;R:=l; FOR RC~=l STEP 1 UNTIl.. INDEXeV,3] DO ~OR T~=:I. SlEP :I. UNTIL MIN(18,N-(RC-l)*18) DO ADJC18*(RC-1)+TJ:=ROWlINDExeV,RC+3J,TJ;
21 (;,0 21}O :21HO 1 ':.;;'0 :..'>:00 ~,:.~
~::::.':I 0
2:..:':::.:::0
/::'::UO
::.::::o?O 2::;:1 0 ;:;:.3:.'0 ?:.':30
OO()02()OO 00002010 O()0020::!.O O()002030 O()002040 000020:::jO OO()()20(:.O O()0020}O 00 00 ~.' () DO OOOO;..i 070 ()OOO~:::' 00 OO()C~~l :1.0 0000:::1;.'0
Ii I::. F' :: :::: F (11... ::> I:: ;
OOOO;:~l:\O
WHILE ADJ[R] NEQ 0 DO HE[JI ~J IF BETALADJERJJ=O lHEN BEGIN L::::::1;; WHILE ADJELJ NEQ 0 DO FiLG 1N IF r:L.T p, I. r,DJLI... J ]=0 AND ~~D, ..I e I... J >(,D,..1 e RJ THEN B;:::G J N DF:: ::::TF~UE ii FOR RC:=:I. STEP :I. UNTIL INDEXeADJLRJ,3J DO FUR 1:=:1. SfEP 1 UNTIl... 18 DO IF F(UW I. TNDeXL PILiJ el:(::l , 1:(C+3::1 r T:1 ::::(0DJ e1... J THEN BEGIN DF~=FAI...SE;;RC:=N+l;T:=19 END; IF D~ THEN BLGIN D~F:=TRUE;I...:=N;R:=N END; CND; l..:: ::::1...+:1.;: END; END;: ~~: ::::F(+l;: END; IF NUT D!:::F THEN BEGIN BETALVJ:=I;K:=K+l; WHILE ADJ:RJ=O DO R~=R-l; FOR R:=R STEP -:I. U~TIL 1 DO CANDLADJeRJJ:=FALSE; FNU,
O()002140 000021~:jO
OOOO:!.l hI,) OO()o::.) 1 /0 OOO()~::lHO
0000::: :\. ~!O OOOO:?20() 000022::.0 () Co 0 ()~!.2? 0 0 (O:~ ::.:: 30
o()
()O()O:?~.)4()
o0 0 0 ~.~ ~:: ~.:; 0 O()002260 000022/0 000022UO
00002270 OOOO::!.::~OO
0()()023:LO
OO()023::::0 OOOO~!.330
O()()O:?2i40
2::,:'.'.;0
1:::NDi:
o0 0 () 2 ::~ ~:.; ()
;::::\(:',0 :: . ··~/O
1:: ::1+1;
O()002360
0
END::
000 O::'~j'70
FOR
STEP 1 UNTIL N DO R~=O SlEP 1 UNTIL N DO ADJCRJ:=O;R:=R+l;L:=O; FUR RC~=l STEP 1 UNTIL INDEXeV,3J DO FOR T~=l SlEP 1 UN1IL MIN(18,N-CRC-l)*18) DO BEGIN W~=ROW[INDEX[V,RC+3J,TJ; IF W NLQ 0 THEN IF BLTALWJ>BETALVJ THEN V~=l
B~GIN 4.'~ /~
() ()
:'.)<\10 :.: lj ,:: () ::~ 4 ;".0 ::.'l;·/{O
)4';:.0
FOR
~:
F BLT tiL: WJ
THEN BEGIN FOR ::.:~ it
;.:: 0
I~=10
S'lEP -1 UNTIL 2 DO
BADJ[L,IJ~=BADJ[l,I-1J;BAD~[L,lJ:=V;
END ELSE FOR 1==1 SfEP 1 UNTIL 10 DO IF BADJeL,IJ=O THEN BlGIN BADJeL,IJ:=V;I:=11 END; END END FTF(FI::: r
OO()()2:~UO
0(: () 0 ::~:sr;o
O()()02400 00()024:1.0
00002420 00002430
00002440
o()OO::'4~:;O 00002460 OO()024/0 ,() Co 0 C< ::.' II a ()
O()()02490
o0 ()()::?~~iO 0 00002:'510 000 0 2~:~;:::: () 00002::530
,': () (;1 ()
/. 0 ~.::: ()
PROCEDURE CRITPATN(X,BADJ,CP~P,CPINDEX,PATH); INTEGER X,CP;ARRAY BADJL*,*JvPC*J,CPINDEXC*JvPATHL*J; B~GIN INTEGER J,Y; J:=l;WHILE PLCPINDEXrCP]+J-1J NEQ 0 DO J~=J+l; P[CPINDEX[CPJ+J-IJ==X;CPINDEX[CP+IJ:=CPINDEXlCPJ+J;PATHlXJ==CP; Y:=BADJ[XvlJ;IF Y NED 0 THEN BEGIN CRITPATH(Y~BADJ,CP,P~CPINDEX,PATH);J:=2; WN II... F Bi:,D,.JCX I' ,j J NI::.U 0 DO B(GIN CP==CP+l;Y:=BADJEX,JJ; CRITPATH(Y,BADJvCPvP~CPINDEXvPATH);J:~J+l;
30~?O
.3::'00 3 ::. !. 0
;; ::. ::.' 0
E:.:ND END
END
CF~ITPtlfH;;
O()()03000
0000301() OOOO/.Q20
000030:?;O OOOO;!;040 000030::=;0 () 0 () 0 :50 60 000030}O 000030EO OO()O:'~090
{)OOO::; J 00
0000.5110 OO()031 ~.'O \
\N
... 00':> '1')'!O 'i :!:~ 0 '1 ,:):50 401.1,0 40~,;O
l;O;::'i 0 .I~O'/O
40;':::0 .;'~O,)O
:I () () 1.,;:1 0 ':.~
41:"::;0
4140 4:1./.,0 4:;70
',)E:CTClI'U:; ( N, :r. NDEX, I:WW , BET ~I, CPMAX , F' , CP I NDE:X, PATH, Bt,D,j 1,1,)T 1 VB) ; J N rC[),::I:< N, CPt1,!:)X; INTEGER AkRAY INDEXL*,*J,ROWL*,*J,BETAL*J,P[MJ,CPINDEXL*J, PATHC*J,BADJC*,*J,VTC*,*J,VBC*,*J, BLGIN INTEGER CP,V,WvI,J,RC,T; F 1m C F:' ~ "" 1. !:) T E,I::' 1 UN T.:: L C F' r'1 t'l x Ii () FOR V:=l SlEP 1 UNTIL N DO B£G:N J:=BEfALVJ;W:=O; FOR I:=CPINDEXLCPJ STEP 1 UNTIL CPINDEXlCP+1J-l DCl BfGJN IF BETAlPlIJJ<J THEN FOR RC:=l S,'EP 1 UNTIL INDEXeV,JJ DO FOR T:=l SlEP 1 UNTIL 18 DU !F RDWLINDEXCV,RC+3J,TJ=PCIJ THEN BEGIN RC:=N;T~=19;J:=BETALPLIJJ;W~=P[IJ END; END; VT LVv CP::I :: ::::W;:
1:·r;:l.JCL:DU::~E
.:: F W t-k:CJ () T 1..1t:: N t~·190
420()
IF PATHLVJ=CP THEN VBLV,CPJ:=BADJeV,lJ ELSE VBLV,CPJ:=PlCPINDEXCCPJ]; END Et'lIr
t.)!~:CTUF~;:;;
00004000 00004010 O()()04()~!.O
OO()040~:SO
0000 40/~() 000040~:;O
0000 l+O l~lO
000040/0 000040UO
P00040?O OOOO'~i::' 00
OOOO.l\:I.:1.() 00004:1.:!O
00004:1.30 OOOO!~l/;·()
\
OOOOI..i:l.~:,;O
~
000041f:>O 00004:1.70 000041UO OO()041(?0 O()004200
000042:1.0 00004220
:.' () () 0
PR8ClDURE
:,0:1.0
A "" I'·,~ AY ..., ..
:,<::<'0
F(UI,,1 L)~,'~
~.::.;o:·::.o
BlGIN INTEGER CP,J,S,V,K,L,PP; FOR CP:=l STEP 1 UNT[L CPMAX DO BlGIN WkITE(DEX,,CP); S:=1000*CP;PP:=CPINDEXCCPJ; FOR V:=l SlEP 1 UNTIL N DO IF VTCV,CPJ NEQ 0 THEN BEGIN J:=l;WHILE V1CV,CPJ NEQ PCPP+J-1J DO J:=J+l; WH I 1.,1::: J>O DO BEGIN WRITE(DEX,
~:;o
~'.:j
/) 0
0 (. 0
~:;O)'O
:::; 0:::0 ~:;
:L () 0
::j:l. )0
~:i::'
~:.; :~. ~:j"j,
(.0 '.1'0
ADD~ESS(VT,VB,CPMAX,N,P,CPINDEX,INDEX,ROW,PLACE);
"I V 1'1'" I v ,)~""I , I"-' \".. *..'" ,)(, ~ ~('''' :" ,(, J :; ::: NTi~::G:J::: CPt1(1X, N;;
t) 'T""..
n".. X I".. 'If""\ , 1-,,' I'" A(" I'" [,.~' , L'" \..,,'..'[ N ..,::. J
::,
,
"I
,)~"
'" N r1.1F.",:, X ['.. ,~.
,..
,
*J ,
::;: =::!:;+:I. ;
IF PlPP+J-1J=VBLV,CPJ THEN J:=O ELSE J:=J-l END;
no
OOOO;'jOOO O()OO~:jO:l () O()OO~:j()20
()OOO~:j030
oO() O~j () 4 () () 0 0 0 ~:j () ~:,:j 0
000 ()~:;()illj
o 0 () () ~::j () "7 ()
000 () ~:j Of:) 0 () 00 O~:,;jO (/ 0
0000'5100 O()()O~:;;:j,10
O()OO~51
:,'0
130 OO()()~;:j 140 ()()()O~::j
OOOO~::;
1 ~::jO
o() 00 ~;:j 11:,0 OOOO:"j:l. "70 ()O()O~;j lBO
~:.:j:L ~?O
END;:
OOOO~;jl ')()
:j:~OO
J:=CPINDEXCCP+1J; FOR J:=CPINDEXCCP+1J-l STEP -1 UNTIL PP DU BLGiN WRlfE(DEX,
000 O';:i2 00 o() 0 0 ~:j::' :~, ()
~,);,:,)
:!, 0
:',:: ~~ :,,' () ~,:.:::::)o
\.::; :':' ..:~. ()
!:) ::
"::~:;+:t.
END; END; ~:,i::,)/O
END
t-,IJDF~E::3!:; ~
;
OOOO~5220
00005230 OO()(),,:j240 Co 00 O~j::~ :'.'jO ()()OO~::i260 OOOO~:j27()
\
'"
/, ',) (J ()
(,0(;::, (,0 J 0 hOI:','"
/) () :~O (;030 i.>O:·~~:.;j
60<()
hO,SO
(,O'i' () l) ~':.~
P')
(,100
61 O~::..
6110 {,1 )0 6 1 :~~ ~;.:l (;.130
6140
PROCEDURE CODES(VT 1 VB,CPMAX,N,P,CPINDEX,INDEX,ROW 1 PLACE,BETA,BETAMAX)~ AkRAY VTC*,*J,VBC*,*],PC*J,CPINDEXC*J,INDEXC*,*J,PLACE[*,*J,ECTAl-],
0000600()
O()006005
ROW[*?*J;INTEG~R CPMAX~N,BETAMAX;
O()()Of.:,010
BEGIN INTEGER I~J~V,W~TDP1BOTTOM1T?CPfS,Z,VL,K1L,PVV,PUT,PWT; ;NTCGER ARRAY PI?PZ~PCP(1:N+1J?TTC1:NJ; INTEGER PROCEDURE LOC(VvW)~INTEGER V1W; BEGIN INTEG~R K,L~ IF V=W THEN LDC:=PLACECN+V 10J ELSE FUR K:=4 SfEP 1 UN'fIL 3+INDEXCV r 3J DO FOR L:=1 STEP 1 UN1'IL 18 DO IF RUWCINDEXeV,KJ?LJ=W "HEN BLGIN LUC:=PLACElINDEXCV,KJ,LJ;K:=8;L:=19 END;
OOO()601~:;
[,'it)
L,oe;
OOOO")02~':j
() COO 060 ::;0
oO() () 6 0 ::;~::j 00006040
1000 0 ,~)O l~. ~:.:j
o() 0 0 (; 0 ~:,; 0 000 () (:) O~:; ~:j
OOOOc)OhO
FOR 1:=1 SlEP 1 UNTIL N DO TTCPEIl]:=I; FUR I:=CPMAX ST~P -1 UNTIL 1 DO BEGIN FOR L:=CPINDEXCIJ STEP 1 UNTIL CPINUEXCI+1]-1 DO PICL-CPINDEXCIJ+1J:=PCLJ;PICl-CPINDEXCIJ+IJ:=0; J:=L-CPINDEXCIJ+l; WRlfE(DEX,{II"ELEMENfS & B & X FOR CRITICAL PATH",I4>,I); WRITE(DEX~{34("="»);
WRlfE(DEX,
, BETALVJ,V,PVT,PVT,VL,PVV); END;:
°
OO()Ob06~':;
() 0 () () 60'/ () Co 00 0 (~i O)'::j OOOOl)OBO 0000 () Co H~;.i
O()OOf.:,O')O () 000 () O(l :',:j OOOO() 1. O() OOOObJ ()~:j O()()O<Sl:LO OOOO() 11::j
O()OOf:.120 OOOO.i) 12~:i OOOOc) 130 00006:l.:?-;:'5 O()006:l.'I() 000061·~,~5
O()OOt:>:I. ::jO 000061 ~5::;j
/:'·1 l)~'''' /):L /0
61 ;;0 /) 1 ~)~::.I 4
(,:':>00
FOR W~~l STEP 1 UNTIL N DO IF BETALW] > BETALVJ AND VTCW,I] NEU THEN IF BETAeVTCW,IJJ < BETAlVJ AND VTeV,IJ NEQ 0 THEN BEGiN IF BETACVTeV,IJ] > BETAeVTCW,IJJ THEN TOP~=VTeV,IJ ELSE TOP:=VTlW,IJ;
0000':,160 000061 c,~5
°
OO()06170 OO()06175 000061E;O OOOOf.>:l.B:·;j
BOTTOM:=VB[V,IJ~PVT~=LOCCV,TOP);PWT~=LOC(W,TOP); VL:=S~=l;WHILE PIeS] NLU BOTTOM DO S:=S+1; WHILE PIeS] NEU TOP DO BEGIN VL:=V!...+l;S:=S+l END; WRITECDEX,<17,X2," AL",13,",",I3,"J ",I8,2Il0,Xl0,I9, "R 0 0 *"),BETAlVJ,V,W,PVT,PWT,VL,LOCCW,V»; WRI1'ECDEX,,BETALVJ,W,V,PWT,PVT,VL,PVV,LOCCW,V»; END
°
°
EI...~:)E
/:. :~ ~ .,:+ ~.)
l) ::.~ ~:.;.; 0
(,::::/0 /) : .:.: '7~::1 () ~.? (:~ 0
IF BLTAlVTeWvIJJ=BETAlVJ THEN BCGIN WRITECDEX v ~.' BET rd: IJ J , Wr V, PVV , UJC ( W, I,,' ) END v
000061 (i'O O()00619~:j
00006200 OOO()()20::;j
0000/)210 OOOO(,21~)
00006:~::::O
() () () 0 f.> 2 :::~ :::j oO() () f., 23 0 OO()Ob23~:j
0000(,240 OUOO('24~:i
) ;
OOOOf.,2:'jO
000 Of., :.~ :5:i
TOP~=VT[V,IJ;BOTTOM==VBeV,IJ;PVT:=LDC(VrTOP);
00006260
IF TUP NEQ 0 THEN B::: l:! I N VL. : ":: ~:; =:::: 1. ii !,) HI I... E P I LS J NE [~ II iJ TTl] M Ii 0 S:":: ~;; +:1. ;
00006?/O
WHILE PICS] NEQ TOP DU BLGIN VL:=VL+l~S~=S+l END; WRITE(DCX,,BETALVJ,V,PVT,LOC(TOP,TOP),VL,PVV); -'---ENO; LND:;
0000626:i 0000627::i O()0062HO 000062n~:j
000062 1}'O OOOOf.12()5
\
~
/
.. : .., :~.'"
:').',O:J
.:,.; '" 0 h::) 1::.. (, ~~; ~,' 0
(.,;;'lO (; :..~, 4
:~J
(~)3~.;.;;O
,S:":':,n~::J
,I):::; ',.::00 (·400 {:.410 6J~·1 ~:j 6l;.::.:~ 0
WRI'I'E(DEX,
°
()
(,f.:,:,:) ()
I
')('">r
BETA[VJ,PCPLZJ,PCPLWJrLOCCPCPLZJ,TOP)r LOC(PCPLWJ,TOP),VL, IF BETALPCP[ZJJ
(.!~ I} ()
()4/:,O (,/f)' ()
(,4')0
()
II
END;; END;; END;
END ,:
O(}OO{,300 00 DO () 30~'~ OO()06::'~:LO
OOOOf.d 1 ~S
O()()Ob320 OOO()f.>32~S
000 O{, ~~ ~::O OO()06:3:3~:;
O()()OS340 OOOO()34::) 00006 3 ~.'; () 000 0 6';~ ~:j~::j '00006':560
OOOO,:~)3/~5
OO() 0 6':;tlO 00 () 0 ,S :::~. B~:j OOOO!:,:3<)() OOOO·S3?~5
00006400 o() 0 06i~ 0 ~5 00006410 000 (1(> 41'5 00 () 0 6A ::.>() 0000642~S
000064:':;0 000 0 1~>4 ~S~::j O() 0 0641~ () o() 0 () 6 44 ::.i
o() 0 06'+::;;0 0000(>460
OOO()()., 6~;5 OO()O () 4 '/ 0 OOOO(,4l~;j
000064HO OOO()t:>4U~,:5
O()()064()O 0000 (; oil') ::,'; "
() 00 0 (; :::J() () o OOO(,~,:;O:':i
WRITECDEX,
FOR
Z~=l STEP BEGIN K~=l;FOR
X
DIVIDE
RE~;U\...T
STAI:;:T VF;:", C1 C2 C3 C4"»;
1 UNTIL I DO L~=CPINDEX[ZJ
STEP 1 UNTIL CPINDEXCZ+l]-l DO
PZ[l-CPINDEXCZ]+lJ~=PCLJ;PZ[L-CPINDEXCZ]+lJ~=O;
\.; H11.. E I::' Z. C,'\ J N I;:: U 0 Ii 0
. ~~ ::..i l~. 0
000065:l.0 () 000 6~:i 1 ~:j ()O!)06~:j20
o() () () 6 ~:; 2 ~:j 00006~::j30
()O()06~33::i
OO()06':540
BEGIN IF Z::::1 THE:N
() () () 0 (, ~:i~:, 0
BEGIN T~=BlTAMAX+2*TT[PZCKJJ-l; WRITECDEX,<17,X2," XC·,I3,"]
() 0 () () 6 ~:j ~:i ::5
• R
1
0
• ,X30,I:I.(),I9,
o0 0 ()
«()
~:i
(; 0
*">,
0
T,PICKJ,lOC(PILKJ,PICKJ),LOCCPICKJ,PICKJ»; END~
IF VBCPZCK],IJ NEU 0 THEN BEGIN T~=BETAMAX+2*TTCPZ[KJJ; 3~=1;WHILE PICS] N~Q VBCPZLKJ,I] DO 5:=S+1; DO
b~·:.lH~:. 6~.:.:.;')O
BEGIN WRITECDEX,
R
0
1
0
*">,
",3110,Xl0,I9,
T,PICSJ,LOCCPZlKJ,PZCKJ),LOCCPZCKJ,PIlS]),l, LOC(PIlSJ,PICS]»; !;) ::
::::~:;
+:!. ;
END UNTIL PICS-1J=VTCPZCKJ,IJ; ENfI; 1"\:::::1<+:1.;
(, /, ~.:; 0 /) () ~:.;.i ~:.;j
END; FND v END; END
C[)DE~:;
V
o() () 0 (!, ~.:j n 0 O()006~3B~:';
000 () 6~::j? () OOO()6~)?~.:j
00006600 o() () O<~) () 0 ~:;
O()OO/)61 () O()O()(~)6:l.~5
00001>620 OOOOI>62~:j
COO () 0 (;; 6'2-; () 00 () () () (;)3::j 0000664() () () 00 () 6 4::j OOOOI:)t:)~.iO
o()() 0 I> \~ :'.'j :'5
',,0;'0
FILE INyDEX(KIND=PRINTER)~ INTEGER IyNyNN,VyW,CP,CPMAXyBETAMAX; ;: NfC[;:,,:I:;; tIF~F~.':, Y Mr.: 1 : 1. B:1 , !:) C:I. : .'1,()::1 ;:
:1.030
R~AD(IN,<40A:I.>,S);WRITE(DlX,<"INPUT
:I. Oll,O :l. O~~.;O
READ(IN y<214>,N,NN); BEGIN INTEGER ARRAY INDEXC1:N,l:7J,ROWCN+l:N+NN,1:18J,
1000
QO()() 1 000 00001()::.0
B~G~N
10::.0
O()()01020 FILE WAS: ·,40Al/>,S);
:1. {) 6 ()
BADJ~1:N,1=10J,BETAC1:NJ,PATHC1:NJ,PLACE[N+l=N+NN,O=18J,
10/0
PL1:N+1J yCPINDEXC1:NJ; INCLUDE ·P/ETREE" S INCLUDE "P/CRITPATH" $ INCLUDE °P/VECTORS· $ INCLUDE "P/ADDRESS· $ INCLUDE uP/CODES"
:LOHO
$
lO?O 1100 1:1.10 l:i.>:O 11 :':\() 1 :i, 40 1. ::. ';,0 1.1 (~:,O
,,,'Y
:r.
i:;:E:r,D(lt~y<:I.BI4>,FUF~
STEP 1 UNTIL N DO INDEXCI,*J); • I:==N+l ~3TE:F' 1 UNTIL N+NN 00 i::':CJW[I,')~]);, ,__
I~=l
1 ::.~::. 0 :! ;:~:.::O
:L :) ~::; 0 1300
0000:1.0';0 ()0001100 O()()O:1.1:l.0 O()()O:L120 OOO()::.l~jO
000011 f:.O
000011DO
C(.:-,1... CUl.. ('\ T I UNO F C r~: I TIC ,~ L F' (':1 TH1::: ~:)
0000l:':'::f.lO 000012'7()
O()OO:1.170 OO()01200 000012:l.0 00001220 OO()()1230 OOOO:l.:?40 OOOOl:~~~50
'I'
1;?'70
000010HO
DII,):r S I I)N I N L.tIBELCL..A:3~3ES ETREE(N,INDEX,ROWyBETAyBADJ); WRITECDEX,{//" V LABELCLASS(V) BADJ(V)"/»~ FOR V:=l STEP 1 UNTIL N DO WRITE(DCX y{I4 p I12,X5,10;4>,V,BETACVJ, FOR 1:=1 STEP 1 UNTIL 10 DO IF BADJLVyI] NEQ 0 THEN BADJ[V,IJ)~
iI.
;l:
00001 o(~:,() O()0010,/()
0000:1.:1.70
'1'
.:r.
OO()010~50
00001140
t'1 iYl' RI X
READ(IN y<7I4>,FOR
:1.1 ()O :i.?OO
00001.040
0000::.130 I:~ E:J\ D
iI.
:I.:LHO
O()O():L030
BETAMAX:=O;CP:=l;CPINDEXCCPJ:=l; FOR W:=l S'!'EP 1 UNTIL N DO IF B~TA[Wj>BETAMAX THEN BEGIN BETAMAX:=BETACWJ;V:=W END; CRITPATH(V,BADJ,CP,P,CPINDEX,PATH);CPMAX:=CP;
000012no 0000:1.2<1'0 0000:1.300
WRITE(DEX,
1 :.'~lO :I ;;~?O
1 :'5 ~:,:" () 13(,0
1::::·/0
::.4:1.0 :;.4?O
0000134() OO()O:l.3~50
00001360 O()OO 1~5'7()
000013UO
00001390 00001400
OOOOl41.0 C'()001420 OOOO:l.430
00001440
END;;
BEGIN ARRAY
OOOOl:UO O()001320 , OO()O:!.330
VT[l~N,l:CPMAXJ,VB[l:N,l~CPMAX];
OOO()14~:!O
000014c,O ::,~)'O
CALCULATION OF HIGHPOINT(VvCP) & LOWPOINTCV,CP)
%
•
VECTORSCN,INDEX,ROW,BETA,CPMAX,P,CPINDEX,PATH,BADJ,VT,VB)~
14UO
000014}O 000014EO OOOO:l.4(,~·O
::. ~:.:.;OO ~ ~:.;:1. 0 :L ~.:) 2 ()
OF VECTORsrO MEMORIES ADDkESSCVT,VB,CPMAX,N,P,CPINDEX,INDEX,ROW,PLACE);
Z
ASSIGNME~T
,..., %
ESTABLISHMENT OF PROGRAM CODES CODES(VT,VB,CPMAX,N,P,CPINDEX,INDEX,ROW,PLACE,BETA,BETAMAX); END END:j LOCI" CDEX) ;
E~H)
•
00001500
000015::.0 OOOOl'::i20 o() 0 0 :I. ~:! :::~ () OOOO:l.~::j40
o0 0;;) 1
~,:.:j ~:.:; 0
00001 ~:jbO
OO()015/0
:LOO 2~)O
0
~
tI>
~
cJ)
J-.. ~
~
S
~ ""I
-~
r:..
J X1
10
1
")
10:,.
:1.
00 ::,:,~ GO
"J
4
"J
bOO
4
4 6
1 1
!'()() H()O
~:;
6
(;,
4
/
A_
900
If)
:to
300 ,~
r--
Ti:::~:;TM(.:ITF~
A ••
,.J
Ci
.-.
:!.OOO 1 :1.00 ::. :.'(;, ()
10
"1
~,
::::.0 ()
") to:••
-1'
:1.
,.'.~
1
.. :)
"
")
() ()
:L ~:';OO :L (.()O ::,"/00 :LHOO :1.(;'00
::: () () () 2 :~. 00 ::.200
<,J
(~
,I.
.
..:> ,., ....:. ,.)
,.J
..
,,:
7.
"i,
"J
")
··z
A:.
"J
0 0
()
()
()
0
0
:I. 1 1
16
.I.
lB
0 0 0 0
0 0 0 0 0 0
.
'1J.
"l ,
()
1-
., {J
,',
~,~ ()
()
(' ,)
0
0
()
4 4
l;:'
0 0
0 0 0
.,
.1. "
d
I::"
0 0 0 0 0 () ()
7
:!.O ()
0 0
0 0 0
0
()
()
()
()
()
()
'-;>
0
0
0
0 0 0
....1
,J
6
it
b
:to
B
I}
(;,
0 .. " i
1.::'
:1.0 6
1.1
'J
/ ("
r'
:)
\=:\
()
0 0 0 0
l~:'
~:j
'"
0 0
:1.3
.0.
4 4
l~'
0 0
14 l:':j
.,
,'j
,.J
11 ::'2
0 0
0 0
0 0 0
0 0 0 0 0 0 0
()
()
()
()
0
0 0
0 0
()
() ()
()
()
0 ()
0 0
0 ()
0 0 0 0 ()
0
0 0 ()
0 0 0 0 0 0 0
0 0 0 0 0 0
0 0
0 0
0 0
()
0 0 0 0 0
()
0 0 0 0 0 0 0
()
()
()
()
0 0 0 0 0 0
()
0 0
()
0
0
()
()
0
()
0 0 0 0
0 0 0 0 0 0 0 0 0 0
~
INPUT fILE WAS
It> I
.
l
1
Z
(1
,.
Z
3
,.
et--
5 I)
'"
7 8 9
5 3 1 Z
+-
!
P ~
., 10
BAOJ( V)
V LlBELCLASS( 'I)
c'-< ~
TESTHATRIXl
,
1 Z 6 r,
3
'f
1
10
•e
7 9
2
~
~
to'"
VERTICES ON CRITICAL PATHS. CP=
1
5
CP=
,.
6
10
Z
8
cp=
• 3
3
Z
7
1
ftATHS·. ASSI GNEO TO VERTICES 1 3
Z 3
3 3
4 1
_.('f'ee
w
1
10
~
5
8
5 1
6
7
1
2
8 2
9 1
10 1
,.
,.
ADDRESS " NO tECTORS rOR PROCESSOR 1000 1001 1002 1003 1004 1005
5 5 5 5 6
1006
10
6
9
9
10
10
(,
£» 4
to
10
6
9
llJ
lOOT
9
1005
10
10
-<
1D09
$
1010 1011
6 4 5
0 It 5
a(ll (II
9 10
1
5 5 5 5
It 9 9
~
6
9
0
10 6
4 5
4 5
~ \
:;
~ 19
-
~
J ~ '1 ~
r
.
t-
-t:
ADDRESS AND tEeTORS fOR PROCESSOR 2000 2001 2002 2003 200 " 2005
7 8
1
4
4
4
6 8 1 8
a
B 8
7 7 8
1 7 8
4
6 8 7
8
ADDRESS AND VECTORS rOR PROCESSOR 3000 3001 3002 3003 300ft 3005 3006 3001 3008 3009
2 3 3 4
"
1 1 Z 2 3
5 5
2
1
1 2
2 3
.1
3
1 1 2 2
3 2 3 1 Z 3
Z
2
3
,. 3
4
5
5 1 2
3
3
ELEMENTS I. B t X FOR CRITICAL PATH
================================== -'
5
V)
fI HESLOT 1 1 2
-r., c
Z 2
z
(l -to-
2 2 3 3 3 3 3 3
(Q (' 0
0It
'"
0+-
fr\---: S f'
UPDATE
ELEMENT A[ 2. 1] A[ 3. 1] PllfOT Z A{ 2, 3] A[ 2] 3. A[ 2] 4. A{ 2] 5. 81 2]
PIVOT A[ 3. A(
4,
Al Al Bl
3, 5. 3]
~!lEMEHT
3 It]
3] 51 31
START VL 3000 3000 3001 3000 3001 3002 3003 3002 3005 3001
SON OTHER CRITICAL
3
START VR 3000 3001 3000 3007 3001 3003 3002 3005 3002 3007
LENGTH 1 1 1
DIYIDE 3001 3001 3008 3008 3008
1 2 1
1 1 1 2
3009 3009
~
~
HHESLOT 3 3 3 3 1 3
ELEMENT 4, A( B[ It] A[ 4. At 5. A[ 5. 8l 5]
4]
5] 4]
5]
START Vl 300l 3003 3003 3005 3005 3005
30(5 1 30C8 30C9 '30C4 3001, 30C6 30C6 30(9
R L R t
R 1 R
ct C2 C3 C4 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0
0
0
0
..•
0
0
*
0 0 0
0 0 0
0 0 0
()
0
0 0 0 Q 0 0 Q 0 ~p
..
* It
..
*
START VR 3003 3008 3005 3003 3005 3008
LENGTH 2 Z 2 2 2 2
DIYIDE
RESULT 1010 1 letO R 1004 R 1 CC4 L 1011 1 1 C J1 R
~\
*It
.. .. ..* It
PAn\~S
~
-...
RESULT 3000 1 3 CelL 3008 t JCe2 R 1002 L 3003 L
Cl C2 C3 C4 0 0 * 0 0 I' 0 I' * 0 0 I ' It 0 t, 0 0 *It 0 0 I·
• ..
\J1
CALCULAfION or x rr HESlDT 1 9
B[ X[
9 ZO 21
s
B[
D[ Xl
Z1
\II
.+~
t ('
ELEMENT 3] fI[ 21 B[ 3]
X
1011 1011 1010 1010
S(
7
22 23 24
2]
3] 21
START VR 3006 3005 3004
3003
3009 3009
11
300Z 3001
LENGTH
11
X[
1]
3008
3000
r
ELEMENTS & B & X FOR CRITICAL PATH
0
==================================
p....
~ c+11
VI
""-
~
~
.
'"i
~
1"
t'
flHE5LOT 1 1
2 2 2 2 2
START Vl
ELEMENT Itp
1]
A[ 6" PIVilT
1)
A[
A[ A[
A[ S[
8" 4"
6"
6 4] 8) 6]
6)
C1 C2 C3 0 1 0
3008 3001
0 0 0
3009 1 1
-+-. ~
RE SUL T 3009 R 3008 R 3 Ce9 R 3008 R 30 (9 R 3~C8 R 3e07 R
1
Z]
t}t
DIVIDE
1 1 1 1
a
1
()
0 0
1 1 0
0
1
0
1
30(8 R 3007 R
0 1
a
1 0 1
30e7 R
1
0
0
0 0 {I
C~ fr
• •" fr
• * *
"*
I:
2 ,-_.
START VR
LENGTH
o I VIDE Zn04
2004 2003 2003 2000
2003 2000 2003
1
2003
Z004
1
1
1 Z005
2005
R E~UL T C1 C2 C3 C4 2
ELEMENTS ON OTHER CRITICAL PATH:S
U~DATE
TIHESLOT 2
ELEHENf A[
6"
61
6]
2
B(
2
A[
f)p
4)
Z Z
A[ A[
4"
6]
Itp
2
O[
4]
41
START VL 2002 2002 2002 2001 2000 2000
~
START VR 2002 2005 2001 2002 2000 200r.
LENGTH 1 1
1 1 Z
z
01 VID E
RESUL T 10(9 l 1009 R l(H 0 R lceo L 1elO l 1010 R
C1 C2 C3 C4 fr 0 I' 0 0 0 r "* I: 0 0 c· 0 0 I * I: 0 0 0 0 *
,
.,
""
CALCULATION Dr x Tl HESLOT 9 9
-. .s
""...
A--
11 16 11 18
X
ELEMENT a( 81 IH 11 Br 81
X( B1
1]
X(
1l
1010 1010 1009
START VR 2001 2000 2002
LENGTH 1 1 1
B1
DIVIDE
2005 2005
2003
1 200ft
RESULT 2005 R 2 OC4 R 20CS R 2005 R 2 (j (4 R 20C4 R
C1 C2 C3 Cit 0 1 :0 * 0 1 "0 A
RE~ULT
Cl C2 C3 C4 0 0 1> * 0 () * 0 0 0 «) • 0 0 -0 * 0 0 0 0 0 0 0 0 ¢ *
a
1
'0
1 0 1
0 1 0
~o ~o ~,o
*
• • *
C.
n
"...
-' ~
r0
CL-. (1) V"
rlt'l
.1'1
.r~ 9
...-.., X t-
ELEMENTS I B 1 X FOR CRITICAL PATH
========'========================== TlHESLOT
4
ELEMENT A£ 5. 9] A( 10. 91 PI"OT 10 A( lOp 5] 5p 101 A{ bp 10] A[ B( lO] PIVOT 6 A{ 4. 6] A£ fu 51 5p 6] A[ o£ 61 PIVDT 4 A[ It. 5] A[ 5. 41
4
or
4)
5
PIIfDr Br 5)
l
1 2 2 2 2 2 1 1 3 3
3 4 4
s
5
START VL 1006 1006 1001
1
START VR
1006 1001 1006
LENGTH
DIVIDE 1001 1001
1 1 1
1006 1005
1001 1005
1 I"
1005 1002 1005 1000 1000 1003 1000 1001 1001
1002 1005 100B 1000 1003 1000 1009 1001 1001
1 1 1 1 1
1008 1006 1009
1
1 It
"
1009
1010
lCOI 10(6 1 OC8 10e2 1 C(2 1 CC5 1 ee8 10(9 lOCO 1 CC] 10 (3 1009 1010 10C4 1 I) (4 1 C10 1011 1011
L l
L R t
L R L L R t
R L R t
R L R
~
-
~
•
•
0
0
0 0 0 0
0 0 0
0 0
0 0
0 0 0 0 0
0 0 0 0
()
*
Q C:.>
*.
0 t)
•
()
0
0 ()
0
e
I
*
•
*
*
•
* *
CALCULATION OF X
-"
s
VI ~
(.
(' c1"-
\0
()
0
t1-. f:J Vl
e+-
ro
'"
k-
!
~ .... ~
r-
fIHESLOT
ELEHENT
6
Xl
1 1 1 1 8
Bt It] 81 6] B[ 10] B( 9] )(( 4] BI 61 X( 6] Bt 10] x{ 101 B( 91 X( 9]
9 10 II
1l 13 14
X
START YR
LENGTH
5]
1011 1011 1011 1011
1004 1003 100l 1001
1 1 1
1010
1000
1
1009
1005
1
DIVIOE
RE~ULT
1011
1011 ~ 1 C10 R 10(9 R 1008 R 1eel R "1010 R 1009 R
1
1010 1009 1008 1008
1006
1
1007
lOC9 R 10(8 1008 1 C C7 1007
R R R R
C1 Cl C3 C" ' 0 5 1 0 1 0 * 111' 0 1 0 111' 0 1 '0 II 0 1 0 1 0 0 * 1 0 0 111' 1 0 0 * 1 0 .0 • 0 .i;l * 1 0 1 .:P tr 1 '0 * 0
.,
~
\
OJ
8200 8300
8400 8500 8600 8700
8800 8900 9000 9100 9200 9300
9400 9500 9600 9700
9800 9900
BUSTRANSPORT PER TIMESLOT: 0 6 6 0 0
"~
t ,
.~
i I
1
I
,
100 ::::00
300
c;)
:1.
1 :I. :I. 1
3
4
4
'./00
r.:' ••J
6 7
COO
t.>
lfOO l()OO :1 :~. 00
f':) ("I
P
c.D
1 :?OO ::.~r,oo
1':':·00
.:..
?
,")
:I.
4·"
:I. :l.
'3
r if=>
:1./;00 :1.)'00 :l.F:OO
")
:1.(/00
4 4
::.~
1
3 3
s.::.
:t. ~:.:)OO
::>000
3 2 :5
:!.o,.,
-t-
-<
.:..
4
600
r--
-r~ P
")
400 :::!OO
1/1
\/I
..•1.
")
-.:)
rt~
TI:::STMAfl=i:J:X2 :to 10
4 .. r)
")
,;..
··x " ••1
...'
:I. 1 'I
0 4 4 .:':.
,..I
...: ..
"1
4
4
.::.
10 0 '7 0
::. 00
5
:.' ::~ () 0
,::. •.J
•.1
,.,
<:>
~:j
:1.0 6
.,
n
20
0 0 0 0 0 0 0 0 0 0
0
0
I.:' •.1
0
0 0 0 0 0 0 0 0 0 0 0 0
~5
0
()
7
B
P
.J
']
0 0 0 0 0
0
J.l 3. ':) :1.3 J..4 :I. ~:j :Lt.> 1'7 113 1 ("I ~.
t' 6 0 0
0 0 0
,., ()
0 0 0
0 0 () () ()
0 0 0 0
~
()
0 ()
0 0 :l.O 0 0 ()
0 0
0 0 0 0 0 0 0 0 0 0
0 ()
0 0 0 0 0
~
0
0
0
0 0
()
0 0
0
0 0 0
()
0 0 0
0 0 0
0
0
0 0
O· 0
0 0
()
()
()
0 0 0 0 0 0 0
()
0 0 0 0
0 0
0
0
()
0 0 0 0 0
0 0
t.)
0 0 0 0 0 0 0
0 0 0 0 0 0 0 ()
0 0
0
0 0
0
()
0
0 0 0 0 0 0
()
0
()
0 ()
0 0 0
~
C>
UPUT FI LE WAS
V
.
TESTHATRIX2
LABELCLlSS(V)
~
BAOJ
10
(t> I
(f-<,
~ ~
rt--
-
C ~
1
1
2
2
r,
,.
1
3
Z 6
5
5
4
6
3
10
1
1 Z
1
3
8 9
1 2
10
f:. 8
3
'i
e _ i't'ec.
•
9
P
.-'-
-~ . ~
~
VERTICES ON CRITICAL PATHS CP= 5 CIt= 3 l: P= 8
1 It
6
Z
1
·2 .
10
9
1 7
PATH S ASSIGNED TO VERTICES 1
2
3
,.
5
Z
2
2
1
1
6 . 1
~
SO
1 1
8 1
9 1
10 1
~ t--
ADDRESS AND fEeT ORS fOR PROCESSOR
9 Cl~
~
VI
v(tI ~
1000 1001 1002 lOOl 1004 1005 1006
4 5 5 5 5
6
6 9
"
9 10
10
6
6
10
10
4 10 9
lOOT
'}
'J
'J
9
1008 1009 1010 1011
10
10 6
10
10
6
6
4 5
,.
5
" 9
1
5 5 5 5 6 10
6
6
4 5
4 5
\=::\
,l~ III
..r ~
i _.~
~
~
ADDRESS AND VECTORS fOR PROCESSOR 2000 2001 2002 2003 2004 2005 2006 2001 2008 2009
2
1
1
1 3
1 2 2
1 2 2
4 5 5
1 2 1
3 Z
1
1 2
3 1 Z
1
3
" 2 3
1 8
3002
5
8
3003
""
8 1 8
1 7 6
3001
3004 3005
1 6 8 1 7
1 2
3
8
,.
4 5 8 7
8
~
f'l
3 4 4 5 5
ADDRESS AND VECTORS fOR PROCESSOR 3000
2
2 1
3
8200 Fl300 B40() n::iO() f:l6()() B'700 BHO()
BUSTRANSPORT PER TIMESLOT:
o
6
TI~1FS1...0T
P
3
Of
S-
0
()
()
()
0
0 6
6 0
0
()
()
(;
... ''1
0
3
()
(1200 9;';")00 ?400 9~:j() 0
('".,
9/)()()
(U I TU(.,AND)
J..
B?OO ?OOO
:J.
600
T IMF::;I...OT I
'L.
(INKOMEND)
3
'1
S-
(?)'OO 9UOO
1.
0
6
(;,
0
0
2
()
()
()
()
()
("')'JOO
:5
0
()
0
()
0
~ I
~
OJ
r'-~-"-----'"''
-.. -..
736 ~>
,.' .'
'", ?
1. Fig. 6.
Graph representing structure of nodal admittance malri", of some amplifier.
[1-"J
:LOO
200
ur;:(.) r.) F PUEIL 46
~;;:() 0
:I.
..
400
")
~.,OO
,
4b 1
'•..",
M.:::".
:1.::;::00 :i.I.!·OO
c
10 1:1. :1.2
? 3
r--,
1600
:1.4
., "7 (', () " ... ,
1 ~:J
I
:!.UOO
:I. (~)
:!.
:1./
"!
n
...
n D
~~OOO
.•. '1
2100
1?
")
~~ ::~ () ()
:!-O 2:1.
I:>
22
~::j
::,' :,; 0 () ~?/~·OO '0, L. (\. {'t ......... J ", ...,
,J (;') () ()
"
'0)",:
"'... f::"J
()
0
0 0 0
()
....,
:I. 1. :I. 1 :!. .,
6(:)
6/ f)\:"j
,J .:,
1..::'1;;"
,.J ,.J
:';j '7 \;:'1",
"J C)
~;.;9
60 b:!, t, ") t ....:..
t)/i
.;,
b4
:l. 1 1 :I.
6~·.;;
........
1
:!.
(,.,9
::>'4
")
.....
:I.
/0
10
1 1 1 1
'""!'f
"\1••
:iHOO
:'~
::.~? 00 :;;000
:',~/
4
r:,u
.......
::,) :I
.;~)OO
29 30
"J
3/,00
;.~
:!.
4
0 ()
~.
~:
:,~iOO
:'S~,
()
~;:j6
3 4
:i. (;)00
()
:I. :I. 1
~::;OO
1-.1
0 0 0 0 0 0 0 0 0 0 0 0 0
4 '/
")
:i.
J. ,
0
·1
~:j
..
rr~
0
1
") ,,;
1 "1 .1..... J
()
12
(;l
,.
~.i3
...
:LOOO :! ';00
';-
0
:?
6 I' n
()
~::j
BOO 900
:, ~;: () ()
()
.".. 1
III
P
()
0 0 0
0
I:':'
~
0 0
.
')'00
cJ)
0 0
.::"
~
r..C
,..::..... J
~:
c)
()
()
8 5
~
4/ 48 4(1
4
-.:.
...
1
1 :I. 1
)
~jO
j
bOO
,..'
/ '
0 0
"1
'"'
..
"'J ~
..
") ,
&::'
:I. 1 1
I
.1.
'72
() ()
0 0 0
~,
()
()
~
()
0
"l
()
()
()
0 0
0 0 0 0
()
()
()
0 0
()
()
0 0 0
0
0 0 0 0
()
()
()
()
0 0 0
'73 /4
()
()
()
7~:j
0
0
()
7f)
()
T?
0
0 0
0
0
()
32 33
:1.2 6
34 :3 ~.:5 36
"Yo
,.>
1
B
...1
1
1
J\/OO
"Y "~
"I
4000
3B 30:;
;5400 00 ~:~~~) 0 0
~:'; ~;:.;
..,": .... ,.f I '., ,) (~d'"
;:~BOO
4:LOO
0
~
'"p
r-C-O ~
.... p p
~
e--, ~
L..J
...
,C
... ,.,
:) ~
.:,.',
'1
.,.1.
0.1.
0",
'I..J"..
f"r .> ...,
r.:' ,.J
:I.
B~':j
4
1
G6
:I. .,
..
B] un
:I. J.
U9 I/O
9:!
4
4400
4~,~
1
4~':JOO
4
Af.!OO
4?:; 44
b
·-t/OO
0/1"'., hJ
8
l·~·BOO
4<:')
"7.
11::.
0
:I.
"1
,.>
1 1 0 0
..::. '"
4
44
,)
~")
•'OJ
I
0 0 0 0 0 0 0
('\.,
B4
4",.
"3 4
()
:I.
'to
,-,
0
7<'/ f30
:I.
4:::00 4;;;00
4
lB
()
0 0 0 0 0 0 0 0
I
A"
0 0 0 of
,' ..
.1••:.
44 '1 .,
P.1
1 ~>.
44 0 0
.....,
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
()
()
0 0 0
() ()
()
()
0
0
(0
0
0
()
()
0 0
()
0 0
0
0
()
~:)9
U.
B
0
()
()
0 0 0
()
0 0 0 0 0
0 0 0
0 0 0
0 0 0 0 0
")') "'~~
2~:.:;
44
4
()
0 0
0 0
0 f' ,)
0 0 0 0 0 0
0 0
0
0
0
()
0 0
()
0
()
0 0 0 0 0
0 0
0
0 0 0
()
()
()
0 0 0
0 0 ()
0
~:j40()
"7.<:,) J
44
()
~:j:,}OO
4
3(/
~:i('()O
~5
;~"I
~J/OO
n '"
'"'7 :1.0
0 11
If>
:l.tl
0 :to 0
~:jHO()
9
:L :5
:1.4
n
:l.H
0 0 1::;) 0 20
~.;j900
B
..
21
'0)")
,,;..,....
2]
4
L';'
()
()
0 20
0 0 0
0 0 0
21
lH
0
0 0
:I. '.J
f'
0 0 :I. :::i
:1.0 0 0 20
...J
",
.j...::.
{IOOO (,:!.OO
4 :1.0
{<>.oo
14
10
:1.3
{)300
14
1]
llAOO I.)~.:~ 00
')
lH
l)bOO
1 ~:.;) 1 {.
.:;'
~!
.t
oj
{'~
C)
.\
...
.J. /
,
'1 .I. "' .t.
20 1 ~:j 20 0
7
()
0 0
1 ::j 0 1 ~:j
0
0 21 0 0
0
~.:5
3~:j
0 0
B
0 0 0 0
0
()
,,)
()
()
()
n
0 0 0
10
()
()
0
(;0
0
0
0
0 0
0
0
()
0
0
()
0
()
0
0
()
0
0
()
0 0 0 0
0
0
()
0
0 0 0 0 0 0 0 0 0
0
0 0 0 0
()
()
0
0 0
°a0 0 0 0 0
()
0
()
0 0 0 0 0
0
0 0 0 0
()
()
()
()
0 0
0 0 0
()
0 0
0 0
0
()
0 0 ()
0
0 0 0 ()
0 ()
()
0 0 0
0 0
~ I
~
0"..
.l
:.,1 1
<
1
,
.I
lEI
20
6::::()O
1 ::>
{,!lOO
.1•. 1.
15 1 ~:j
4f.>
11 4b
2~'~j
4f:i
()
0
/~?()()
::.~ ~:j
/';:;00
".;..~
31 ... : .....\(
r\,,;'
~')
••OJ
()
()
6700 7000 ?:l.OO
..,
0
()
lEI
10
0 14
()
0 0
/')")
f:l
0
0
0
n
0
()
0
0
0
()
()
()
()
()
2f.>
4'"' ,.J
27
0 11
0
0
0 :J. II
.,.).,...
.:..
,,:...i.
Q
7~:jO()
E
2f.>
3~:J
2~5
'" r-
/600 7/00 /1300
4()
4~:j
0
0
40
0
()
33
0 40
0 3:1. 0 0 0 0
3::?-
()
}(?()O
:.~4
-J! r) ..... ,;..
41. 4::':;
4~::j 2~.;j
31
:':-;4
:5 f)
0
~3000
37
0 ~:) fl
~:~:L
..30,.,
34 33
43
4::)
".~
,.)
...1
~ •.
B~·:·~OO
2'7
HL.:·OO
"1'") ,~.-
34 0
H~':jOO
32
41
:·:::(.()O
~52
4
n700
6
UHOO U?OO
,.) Ci
/ 1~ () () ~
cJ oJ)
..,
? ?
~ t'--o ~
L...J
00
H~,:.)O
()
',/000
7 ::" 00
,.),,)
,::. ~.,
."
,:) ....
.
\
•.• I
3~·.)
,.'
~J
9:':\00 ?400
2~.~j
2B
2:1.
22
~
I~"
6 31 23
()
0
0
0
0 0
0 0
()
0
()
0
0 0 0 0
0
()
0 0 0 0
0 0
0
0
0
()
()
0
0
0 0 0 0
0
()
0
()
()
0
0
0 0 0 0 0 0
30
33
4~::j
2~5
35
0
()
0 0
()
0 0 0 0 0 0 0 0 0
0
0
0
0 0
~)
0 0
0
~,
')
0
0
()
()
0
()
()
0 0 0
0 0 0
0
0 0
0
()
0 0 0
0 0 0 0 0 0
()
0
()
0 0 0 0
0 0 0 0
0 0
()
()
0
0 0
()
()
0
(I
0 0
0
0 0 3~~:"
0
:~; ()
3~5
0 ~:~ ::.!
0
()
0
0 0 0
0 0
()
()
()
0 0 0 0 0 0 0
()
0
()
()
0 0
0 0 0 0
0
0
()
0 0
0
0 0 0 0 0 0 0
,.)
0 0 0 0
0
0 0 0
0
()
0 0
0
()
0 4';(
0
0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0
()
4 40 0
0 0
0 0
0
0 B
()
0
0 G
,
()
0 0
0 0 4 0 0 0 0 ~")
()
0 0
0
""1:)
()
0 0 0
()
0
32
0
0
0
()
0
0
0 0 0
0
4~.'J
32
0
()
:;~2
33
0 3H
0
0
0
()
3'7 0 2") ~7j
..
:5 ~::j
0 0
0 ()
3~:i
32
30 41 '''x ....' "X...-'
'?~'::()O
41
0
0 0
()
0
4~')
4::.:
0 0
0 ()
B 0 0 0 0
,'\ 1;;"
30
1
~.I
0
0
0 0 0
.:: ...J
':•• \.1
•
0
()
0
-; 29
..'
0
()
" " .1.• i.
0 4.01-
\
0
()
0 0
0
0 0 0 0
0 0
4' x 0 0 0 B ,,)
()
()
0
()
0 0 0 ()
()
0 0 0 0'
0 0 0 0
0
0 () ()
0 0 0 0 0 0 0 '0
0 0 0 0 0 0 0 0 0
0
Co
()
(" ,)
0
0 0 0 0 0 0
0
0 ()
0 0
~\ N ~
1If-2.8 100
1 NPUT F 1I.. E WAS
.
7E
GRAAF PUBL
200
30a
4eo
503
V
-
600 700 800
. ".-
._--- -_._-
9D3
1 2 3
.- - -
_._- --,--
1000 llOO
5
...... -._.-.
~
~
12QO 1. 30 :> 1400 .,------ - -_.. - _.
"~~~--~~--
-
-
.~_.-
.
-
------_ ..
150() 1600 170)
5 6 1· 1 8 2
4 6 7 8 9
4
1800
1l 12
9
L900
13
1 Z
2000
14
2100
15
2200
16
23a:>
17 18 19 20 21 22 23 24 25 26
24CO 250:> 2600 2TD:> 2800
BADJeV)
1
2 3
10
290) 30GO 5i0C) 3200 .3 30 3
---_. ----.
LA3£LCLASSeV}
1 2 44 4
12
21 16 2) 8
5 9
35
1 6 1
1 5 1 3 ..-
13
18 1)
17
14
19 46
7
- 15
10
11
1
1 22
3400
27 28
11 1 2 1
5503
29
1
36CO
30
31
3 2
41 24
4)
.37D) 3600
32
5
390C)
33
4 1
33 30
31 34
45
27
7
6 26 37
40110 410,) 42CO 430\) 4400 450G 4600
470a 48eQ ,.90) 50eD
51DO 52CO 5303
34
35 36 37 38 39
40 41 42 43 1t4
7 1
1 1 2 2 2 1 2 4 6
45 46
2
€.-.f. yo ee
~1'C\"'~ [1]
25
29 42 38
3 32 ~3
39
36 43
]1[-2'1 54CO 550)
-.
._.•
"."
_---~~
-_ .. --~.
.,.- -'.. _. ~
..
56':0 5700 5800 5900 &00) 6100 &200
,.~,
- -.
-
.
-- -
1
22 2
::P=
9 :p=
17 :; jl=
45
CRITICAL ;J A TH S
11
8
2l
15
44
3
2
1
32
33
30
41
18
10
20
14
3
16 4
5
23
:: p=
6
5 C po: 39
1
:: P=
8
7200
5
7300
:: jl=
7400 7500 7600 7700 7BOG
12 :: P=
35 C p=
4
'7
9
10 45
42
11
37
1900
:: p=
6[}1)~
40
8100 820a 8300 840)
C F=
12
29 13
28 :: P=
14
34
oseo
: P=
6&00
43
BlCO
:: p=
16
8800 6900 9000 9100 920)
31 C p=
24 17
9700 , 98DO
ON
19 C F=
63uO
93eo
- .-....
CP=
- 25
&40) 6500 &&O() 67110 &800 6900 7000 7100
9400 9500 960) ...
VERTICES
15 38
3& :: p=
27
18 26
rc
PATH S ; ASSIGN::D
1 5
2
3
r
6
I)
VE FT ICES
4 6
5
& 8
7 7
8 1
9
6
3
10 1
9900 11 1
12
L3
16
17
le
1
14 1
15
9
1
3
4
1
1$ 2
2:> 1
10300 1(40) 105eo
21 1
22
23 5
24 16
25 1
2&
27 18
28 13
29 12
31)
li>50)
31
34
!7
10
14
35 D
36
16
32 10
33
1()700
17
11
38 15
39 7
40 12
l()()Q)
10100 HI200
1
1~800
18
10900
41
42
43
44
45
45
11 00)
10
10
15
6
1-~
5
e-~'/'~~
d .".eu>.-~ [7]
10
13
II[ - 30
32100 32200
HUH TI:;:~I N~:;r,' Dr, T 4B flO 0
F'FF~
0
T J t"\E~:IL()T: 6 0
0
0
0
0
f
8
9
'0
., I
0
0
0
0 0
0
0
0 0 ()
()
0
0
0
0
0 0 0
0
0 0
6
2)2300 ,~::!400
3:l.:;,;iOO 32600 32/00 ::;:;!BOO ~~21'1O()
33000
3
'i
5"
0 0 0 0
0 0 0 0
0 0 0 0 0 0 0 0 0 0
0
0
I.;
0 12 0
3 4
33200 3~BOO
6
33400 33500 :5 :'5(;' 0 0 33/00 33BOO
7
0
6
8 9 :LO
0 0 0 4 El 0
.,1
I.;
0
0
0 0
0 0 0 0
11
6
0 B 0 0 0 0
12 13
0
6
0
4
()
14
12 0 0
0 0 12 l":) 0
of
1::"
J, -.J
16 17
..,.:..
:1.8
0
n
<:)
·0 0 0 ()
0 0 0 ()
0
,
(l.JIT(3r~'lr;ND)
'L
1
0;:'
340()O 34100 34200 34300 34400 34500 34600
ivjl:;:~:;I...()T
,')
.....
3~HOO
339()O
TI
F'
0 0 0 0 0 0 0 0 0
0
0 0
0 0 0 0
()
0
0
6 0
0 0 0 0
0 0 0
6 0
0 0
0 0 0 0 0 0 0 0 0
To
r
'1-,
0
0 0 0 0 0 0
0
0
0 0
()
()
0 0 0 0 0
0
0 0
0 0 0 0 0 0
0 0 0 0
0
0
0 0 0
0 0 0 0 0
0
0
0 0 0 0 0 0 0
0 0 0 0
0 0 0
()
0 0
0 0 0 0 0 0 0 0
0 0
~14/00
34800 34S.'OO 3:'50()O 35100 3:=:;200 3~~:500 3~:;400
3::;500 3:':;600 35/'00 ~~5BOO
35900 36000 36100 36200 3<:)300 36400 36:7iOO 3b600 3(l/OO 36800
r;' 1
.
") ,
3 4
5 6 7 l3 9
TJME-:SUn 14 0 0 0 0
8 ")
.:..
0
0
to
:
2a 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
10
") ' j
26
11
0
1':> 13 14
2
0 0
...
.:0.";"
... -.J
0 0 0
16
()
1'7
0 0
'" 1.::"
lB
0 0 0 0 0 0
()
0 0 0
(INI
()
0 ()
0 0 0 0 0 ()
0 0 0 0
0 0 0 0 0
0 0
0 0 0 0 0 0 0 0 0
0 0 0 0
0 0 0
6 0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0
6 0 0
0 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0
0
('I
0
0 0 0 0 0 0
0 0 0
0 0
0 0
0 0
0
0
0 0 0 0 0 0 0 0 0 0 0 0
0
0
,....
0
0 0 0 0 0
0
"
0
0
0 0 0 0
0 0 0 0
0 0 0 0
0
0
0 0 0
0 0 0
..
..'
•
'f·
."
:;.".~~-. .,. ...
-
••
...
,
.. '.'
......
£OUfVAL-eNT CIRCUIt'·
-
.
.. 1••• '
..
"'-:. :.
'-
:~:
INPUT FILE liftS
V
UA75e
LABELCU SSt V)
1
13
HI
2
3
11~
3
4 6
2 113
4
5 6 7
1 14
9 10 11 12
13 11, 15 16
17 18
lCl
~
-
.---
_.~-.
'._-. ----
..~
<-
124 122 123 Q
2. 5 2 12 1 16 1 1
12Ll
Iv 1
1 !.3
2
]9
1 ~ lv'
e
22
31
1 4 1 E 1 1 4 2 1
119
,e
. 12 J 120 !b
37
11
40 41
1
1
42
19
43
1 19
49
2
':;f)
·1
e--tY(te
; 2. 1!2
!3
39 (,2 ';:1 1
e
s
21
u 131
17
5 1
25
lIe
39
45 4G 41 48
l3
24 1 ! 5
6 1
1 ?
4"
1,6
23 1 ~ 7
S 10
B
c::
J
11
4 7
35 36 37
~
,
ll~
21
34 ...
1 4
20
23 24 25 U, 27 28 29 30 31 . 32 33
77 114
4
15
22 --
15
1 1 (j ! 11 11 S 129 1~ 7 ~IJ
~
a
.-
EflCJ{Vl
~ (!
:() 41 144 1 4 3 [I OJ 49
f A 15'&
It.5
1~4
I! S
]I - 33 51 52 53 54
~
._~
........
~-.~
1
1 3 1
, • • _ _ _ _•
__
2 7
59
4
60 61 62 63 64
2 4
2 5
1
-
~--
43 H6 146
Su 53 141 Uti 171. 17 'J 153 1Elf 111 E5 E1
2
lEu
7
HI H! 4 I, 110 74 7 ()
~
67
20
68 69 10 . 71 72
4 5
3 1 2
HZ 173
73 7 It -. 75 76
2
176 175 17/ 7 3
1
71
7
17 t.
18
3 1 1 2
180
3 1
.
6f)
7'1
es
€Z
94 85
4 2 2
86
21
El
2 2 5 P.
]54 15')
e7 - 6£\ 139
90
3 '+ 2
51 92 93 94
( .j
1C4
f{l
9'7
9G
~
jQ
4
So
2
V~'(VOLd
e-
1E u
15'i 94
f ')
S 'J 1U
1~4_JE?
-trQ.e. / A 1'S8
4
_ _ _ ._. _ _ _ _ _ •
9:; 1 C3 1E 1
El 156 15 7 91 156
H~ '}f
Ilj (I
eI
Lt
n
97
~6
f
153 1:2 149 151 150
5 2 0 2
S5
75
E3 17J 72 1 7 j
3
E2 83
16S
1 ~ ")- 165
65 66
et ~
l~S
1
In
79 Bt)
--------_.
141 140
.....
55 56 57 58
o.
142
1
~
C ..,
- c.
1£1
]]I - '3 i.t
101 lCZ 1 C3 104 105
.-
-
.
.,
90
lEb H5 1 :l J., ~
% c; •
leG 107 103 109 110
12 2? 1 1
111 112
1 1 5 7
4
?
~
115 116 -.--.,'
2
leO
11 2
113 ... 114
.-_ ... --..
3 ~
117
1
5 3
139 140 141 142 143 144 145 146
lG~
1C9
8G
.5
3
5 2
29
_u. 3:> 34 9 ~
1 3 2 3 3
12 193 16 14 1
1 1 3
20
1 1 11 I
1 2 2 2 2 2 2 2
2S
13
40 H
£3 46 52
54 :~
1 1 2 1
':1
1 l ,7
3
57
148 149 150
1 1
ve..rvoL~
lC2
191 1<;;0
1
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
~IJ
lEd leJ
1
e.--t'(-a~
/A :;s-e
]]I - '35'
,b;-e. slo~
.1 Jj
\:
~
U ::i r H MJ 5P C\{ 1 94 276 222
cr <.
::t::>;;'-
~
2-
... 5'
U\ :>
C";).." ~ \)
""-T~ .., rt-
~
l'3
..., Q
-r-
It
~
,
1-
PER TitJ£SLCf: 22 9'3 42 56
e
,
C
72
t~
C
f(
(
,t.
,1
'If
]c
(
C
If;
"
'1
II
"
"lb
tl
C
c
a
(
(
c
c
'l.'L
(
~ ~
0--.....
Bijlage IV Processor ontwerp -
datapaden datapaden besturing datapaden
niet lineaire functies L/U decompositie L/U decompositie berekening ~
.
,
-
•
1 ru.
4P.
41'- 8 J
..
--1'
81.
I I
MeMO"IIS
'I.'t.
'ltOC'U'N'~
I
I
I
I 1
F I ~ S1" /t.1 Flit \'7" o..rr -'''S,'TBlL'i
•
Tr.\-\"TA'TS
=
" 1r«;''''T6«'
r:
I
v""T"S
.F~
FI
I
,----'---,
f'
GvP,.\t
WIT Ii TltZ- STAT Ii
t
I
4!)
I
I
...
---
-
r..
".
r-
R3 ~Ir
--t.
I I
1
f
I
I
I [
r .~
Fi.
L - - ..
_
..
- ...
~
I
I I
- I ,
I
Pi
I r
I
IJ'T' "'.,.
-I ,
.
r
I
...
133
~
I I
-- 6'i
.
85" \
1
...
I ..
".
I
Ft
I
I
1
I ~o...,e: "";~ll;,,,~.... e.uo.l VQA; ... door
I 1 1
M... t\R.
--
I ;n.
P.1
P.t
t
I
I I I
_J
~
N
- - --- - -
-r
~ ·1Q\AS
I
II'
~
-r-
81
I
---" Bt.
I
11.. , t1 '"
l4el1oll'5
\ I
PI, Pt
, ..OC.", .... c;
FI • FiE.
fiIUT' ,,,, "C\'TOV'J lI.IES 11T .r-\
I
, •. $li
I
I
I
ML
Ma
!
¥D 'T"\·~"fA"T. au,....
I
--
r
I
I
I
r
I
!L•
.
L
I r-~
I --
P..t..
R'5 ,Ir
-1
-------
1
I I I
I ~~
r Fi
I I 85" (
T
I
Ft
I I I
to..sc.: ..... -e~ (:",,,, ..:,,.. e.lIo..l..,Do.~l'to Joo't' 1~
~".. c.~:~
I
I
1
I
1
"fa,r- ST"ATf
v.,. ""'T
I
1_ _
1
o
I
Pi
I
I
\AI I,.ti
I
I
I
tt Ie;' ,-rs«'
I I
...
L
I
I
uNITS
....
------
-
--, I
PI • Pt
Bt.l
8/
-_ , •. g~
I ~~iiiII
1
,
Fa •F1..
I
-M
I ,
I
I
_.
-'''SI'T.''~
Arc;'~"'l"ti«' W,Tti '1'IU-,-rAT 6
OU,.''''''
f
I
FI c. $1" I It! ,,~ t'T CVT
I
r. ...
I
I
I ~--
--
-
--
.....
--I
I I
I
I
~iiiiII
tu..
R'! "lIP
I
r
I
I
I
I
I
I
Pi
I I
I r J
r
4~
.. Ir
I I
I
-
...
6"1
I
1
I
Ft
1 J
.t'~e.: ..,
I ....... 1
I
"I
e.(
(i"'~Q,,"n. ~ ""e~~~
e\l"'/",,,"~,<, d .... ~
1'1
.h
~1M~loI4!.
~- J~ •• t·~"···
t
85" \
- -
-
--------1'
~l'
... 8/
~ I~
I
41
81.
-_
~
I
'
~
~
M"
I ~
Mil
r~-
-FI.F:z.
I I
I
I
I
I
I
_ _ _ _
r. .
0..-_
L
~
I
rl,
HeM 0 . , rs
PI ,I':"
\
I I I
, " R~ I
11.. , t1...
.---
'kt;.~~---T-....;:.X=-.-~=-IA....:.=..S -r-~'-
",«'$1" IN ',UT -'CSI'T."~
-, I I
to.
~-----J1'_--__i•. . _ - - - . . . ,
-
-~.
-
11..2..,
IC:;;;-"'R'3 "III1r
i,
f
I
I
I
I
I I
1
I
I
/
Pi
VI
;r ~~
I • I ,.
I
I
r
I
I
I
l_.
...--
,..--
.lIIl
'"
I ..
~3
"l
T
I
Ft
I
I
~
I
:e.... ~c·.
"'-'e.lr l~",,~ ...... 'f'lt. pu... c.~~ ~v .. lv.... ~:t. Joo~ P2.. k.... "ch«>~lI<. \0lOI""
~ .... ~"" J.evlt.
fW'OC
I
e.sso.,. -
_. _._-
_.-.
--_.
-_ _..
-
_..
...
--
1u --~-_."'L,
cq.
I I I
. _ - -J Ha
NS
_._--------,.
.-.r_..-
-._..:;')(;.......:~;;:;..lA_~.;.._.
---l- . 82- I
I
j~
It- 8'
HeMell'"
_
......
PI.,t
I
1
I
, .. it
M..
,
MA
I
I
tt.iiiiiiJ'.
I
,
----_.r .. .
...
I
.
_ ..... "ll
-."--
t
-
--
R '3 ~ ..
...
--,
I
I
I
I I I I
I
Pi
I I
1
r
~.
Fi
I 1 _.
I I
-
~
.-
~
...... ~
I
I
I
I
Ft
I.
I
1
I
-
--~
I
"l'llr.ST'AT i
",.,.,,\JT
I I
[
I
'i ' " T \i «-
WIT'"
I ....
I
I
I f
o
I
r-
"Its' 'Ta ....
I
I
}
'I«'$T ,1.1 It',UT
FI • f1..
lo.$«' . ""',c~
I -..
{j"'oe.... :.,.e.
~~c.~~u
o...("""'1s~
v......
~.
\~~_,l~J ....~l...(.;..
I.e.~ Y'c.sv l ~J..
r
I
I I I
_J
~ 0
~ (:;;
1>u. 'S
Nt>
r --- -
X---~-lA.S
. . . . - - - . ---
-'--...-----.-...;.:..-=-~-
I
~,
,
,
--"
PI,'%, FI,H.
F,c"T ,AI F'llT I(.ESI~"'."~
1•. it
I
tr;;iiiiiiiil.. • r c:; , , T Wi «-
loY'''''' -r1U'- STAT'
I
Cl
I
-,
I
I
r-
•
•
J
I
1
I I I
I
Pi
I I
r Fi
.....
--==i'"
I
-
I I
,·.,
bQ'f~Il..Il ...:W'\.~ i""f,..oclul<~ cLe..tc.l-t-~
'ff'Oc~rof'
01001'
•
I
I
\
I
I f
I
I I _.-
I
-- -_ .. ----- -
---
t>u. ~
I
I
1
.. ~
F.t
.ta.se : L ItA. d-eco_pOSj~'t.
!l'
.....
,
1
·1 I
r: ,,
1
I I
U///'///'////7~1
I ~ l
I I I
I
I
I
u'T "UT
_J
-
-
r
-
---....
~
~
..
-
-
-
- ----.' I
r.
8'
B 2..
.
I
,
-
"-
-
'1. n. f,«' ST "" '/UT 1l"'i'~T."\
I , .. Ri
I
,
I
M ..
I
I Ilrti"TS"
I
I
w I T~ -rllr- ST"ATf ClV'TPvT'
I
I
r
I
r
...
.
I
r--
......._-
-_
z
-
--,
-
tl..
,
I I
I ..
--
I
r
I
I
I
,
I
I
I I i
F~
•ro I 'lao
I
I 1_. _
I
Pi
. ...
r
I ~I --4
....
I•
I Ft
I
I j.lo..,e. :
l.1tA..
clec.c
fo.;.l;e.
b~T-e. ~ ..:... e;, i .. fT." ~4- UOO~
I"'~ hJ~ ...
I
r
o<
,.
f
I
I I I
~
r- I
--------,.
1
-- ,
81
n
B 2.
1
PI.
\
FI.H.
I
". I Ri
I
I
I
,
tl:.iiiI".
I
r.
...
.
I
r-
--
-
IU..
'-
.. -
--
11r
--
- - -- --
-1 . RI:'S-i;1.~ I I
I
I
j
I
I
Pi
I I
1
r 4~
Fi
''IF
l_ _
.
.
_._. _.- -=----1"
~
., ~"'.r:I
....
~l I
I
I
~iI I I
I
I :
1 L.lu.. ~c:.C"..,,,os;kc.. 0 .... .1 "'"'1,4- UQ."" u.... ""fl'O d."'K.J.
.:e",'!oc,
&>I~
I 1
I I
r
I I
I
f
.....
I ,
WI"" 1'IU-S"-ATS
I I
-
1
~I~'~TS"
Cl V'" ,,,,T
I
I
flllST IAI FlUor IlESIIT.'"
•
I
I
J
n.
:
..-.... a.",
d~ .. c. r"Oc.c.'fO~
Pt
.Ll
I.
I
-
-
--.-.
. -. . - - - - - - , '
.r_~'--_-- -x;.;.--..;:~;..I..t.-:s;..-.. .......- - - , - •
I
_
PI • ,t
r- B 2.. I -_ I
81
I
flt.sT 11.1
I
,,' it
I
I
I
tt.iiiI".' , r ti \ ~,-Ii ..
I Cl.~.
I
WIT"
-,
I r----~
.. I~
.
I
.
I
I I
r--
I
I
1---
--,,
I
Pi
,
I
I
I I
1
1 I
!
I
r
I 01 ..
Fi
I
\
~~I
I
It
I
l_ _
\
-- -
I
.
...
I
I
4~
I
, ~-----
~o.s .. \ L 1t.J.. ~.'"i""s ..ji",-
II
v\
+ Mit) ~~4",~c.
t!oot' ~...
d.a.l'.... ~
Q.:i:: o...ij - i ... i'" ... J
?-voc.~ J
-VI
+
--- . . ---1M
•
I
r~
I
-a.ti'y~--lilIr---,
P z..
I
.~
:
I
-==1'"-
~
I I
I I
~4~ u('dCt..~~" V~"" u.... ft.4...... ~ ..
6't
_0..
~~~~
83
I
I
-rltl-S TATi
CI "',. p",,-
I
I
FI~t'"
,,"CS·'T.'"
I I
I
I I I
~=:, L..
.......It,"
VlEEt/Nil
I"
MI. F,
1----.-;:- ~_ I
PooIT C,.
1JL -1i stuurblok
1
Dit blok geeft een instructie voor het vormen van een inprodukt al dan niet door (via blok 2) aan ALU Pl. Input
: T.
TINE CLOCK RESET CI
ElVlPTYFl EMPTYF2 READYPI READYP2
- blok T uit de instructiecode, 7 bit, geeft aan in welk time slot de instructie verwerkt moet worden. - stand van een centrale teller, 1 bit, geeft het aktuele time slot aan. - de 10 MHz klok v.an de processor. - algemene reset van de flip flops. - een bit uit de instructiecode, geeft aan dat er geen inprodukt gevormd moet worden, maar een element van ~ (deling in ALU PI). Er is dan een ander besturingsblok aktief (nog niet ontworpen) - first in first out register Fl is leeg. - idem voor F2. ALU PI is klaar. ALU P2 is klaar.
output
CONTlNUE- de instructie kan verwerkt worden. WAIT - T # TIME, er treedt een wachttoestand Ope NONLINF - T = 0, er moeten niet lineaire functies geevalueerd worden. HALT - De processor is klaar.
Timing
T T T T
=0 = TIME # TIME
=* 7F
-
NONLINF = 1, evaluatie niet lineaire functies. CONTINUE, voer de instructie uit. WAIT, wacht tot T = Tlrili. blok T bevat ui tslui tend enen, di t betekent dat de laatste instructie verwerkt is en dat de HALT toestand optreedt zodra de registers Fl en F2 leeg zijn en de ALUls PI en P2 klaar Zijl
Wanneer processor i zich in de wachttoestand bevindt wordt als aIle rekenwerk waarmee de processor bezig was eerst afgewerkt en dan wordt het signaal NEXTTIMESLOT(i) gegenereerd. Zodra aIle processoren een dergelijk signaal gegenereerd hebben wordt de stand van TIME met een verhoogd. De instructies uit het volgende time slot kunnen dan uitgevoerd worden. De stand van TIME wordt met T vergeleken door middel van EXCLUSIVE ORs, niet getekend in het schema.
N
-It
,-
-I
,
~ CI -,
--
1
I
, T ... TIHE
~
,
I r
D
CJ
..
-
S11S"
CJ
Co
~
~
D
·LJ
-#'
-'-
( I
-'c
t..SliT
R
c.
0
If
$'i5'
;
c.
R.
r I
_ I!I'I fT't -0'• • _
~I
D
•
I
U
~,t~AP"f'.z.
I 1-
I
wAIT
"'()I'I~,#I=
D
I I
"
LJ
I
f:) LJ
I I
I
--.,-
--
I
I r
-l
,.... J
11/ EtTri I1ESL0r...CJ "?
I
I
IJH,TYF2
... CEAPVPI
(......". bto:i )
I
if ~U
I I
l c. ~OC.IC
Cf
$11S" ~
T=#'jF
\
, P
I
;
co,," ,NC) ~
I
I
T-O
I
7
I L
I
HAL-r -;7
:nr - t3 Stuurblok 2 I
Door dit blok wordt het inlezen v~n de vektoren ten behoeve van ALU Pl verzorgd. De adressen van het -begin van de vektoren z~n de blokken VL en VR van de instructiecode. Deze staan nu in binaire tellers. Ook de lengte van de vektoren (blok L) staat ih een binaire teller. Via TRI STATE buffers worden de geheugens geadresseerd. Nadat fl het produkt v.an de twee getallen, die geselecteerd zijn, gevormd he eft (READYP1) worden de standen van de adrestellers met I verhoogd en de stand van de teller met L met 1 verlaagd. Als de stand van deze laatst~ teller nul geworden is wordt er een sinaal FIFOREQ gegeven om aan te geven dat het gevormde inprodukt naar FIFO register 1 of 2 gestuurd moet worden (stuurblok Input
VL, VR, L CONTINUE READYPl CLOCK
Output
DATAIN
blokken uit de instructiecode, aanwezig in drie binaire tellers. - er kunnen getallen uit de geheugens geselecteerd worden. - ALU PI is klaar. 10 MHz klok van de processor. de geselecteerde getallen worden in de registers R4 en R5 gekloktj tevens worden de standen van de tellers met VL, VR en L gew~zigd; start~naal voor Pl. - "chip enable" voor de geheugens. - het gevormde inprodukt moet door een van de FIFOregisters opgenomen worden.
CE FIFOREQ
Timing CLOC.K
,~
\
C6 =
, ~
I (
,"
i
)
...Jc!vcss ",... l~ cL
I
•I
!e:
J A.~tx
.-• --I
CI.OC'"
"CI'ol~ .l.
®
oIcl... y
DATAIN
soo '" Sec.
'(
lS'o",~ec.
>
-,
-- - - ----- - - -
r--
I
I I
11.'
VL
",
L
+
r
/')3
t.... l.ElLO
-n-I I
I I
I
CONTI N()E
PATA/III
(~I(.U)~
c,"-t.,.c+ p,)
(EAOY PI
I I I
I I r
.r
I
-'--
-- - - - -
.nz Stuurblok
J
5'* 3
Een inprodukt dat klaar is wordt naar FIFO register FI of F2 gestuurd. Naar Fl als het bestemd is voor een andere processor, C3 uit de instructiecode is dan 1; naar F2 als het een update is voor een element in het geheugen van dezelfde processor, C3 is dan nul. Ook kan er een updauvia de BUS arriveren voor F2. Hiertoe zendt de BUS eerst een BUSREQ signaal, dat door de processor al dan niet beantwoord wordt met een READYTORECEIVE signaal. Parallel aan de dataregister~ Fl en F2 staan enkele FIFOregisters, die de noodzakelijke bestemmingsadressen opnemen voor deze data. De stuursignalen hiervoor zijn dezelfde als voor de dataregisters. Input
- als C3 = 1 komt het getal in Fl, als C3- = 0 komt het getal in F2, tevens wordt buffer B4 opengezet. FIFOREQ - er moet een inprodukt naar Fl of F2 gestuurd worden. FREEl - er is nog een vrije plaats in register Fl. FREE2 - idem voor F2. BUSREQ - de buscontroller wil een getal naar deze processor zenden. TAKE het getal wordt nu overgezonden via de bus.
output
READYTO RECEIVE - de buscontroller krijgt toestemming om een getal over te zenden. LOADI - klok het getal in register Fl. LOAD2 - idem voor F2. - IIchip enable" voor buffer B4. B4 B5 - idem voor B5. RESET - resetsignaal voor stuurblok 1, de volgende instructie wordt in het instructieregister geklokt.
C3
-l I r
..c 3
I
..
I I
~
®--
C3
~
~ r-:.J -u
V
F,~olC.e~
I
......
~
;~Cll''''
..o.o ~
J
i
ltAPY1
'".
~
~lflfl
o
'TAlC E
,!l6E1
,
I I
,
~r\
.r
LJ
c,
.n.
, .. ls
f"l5
Jl..
fl-
I
,
I
R LJA.. ..... ;
lPAD
I
\.-.~
sl't
,
c
R~
I)
Cf
U
-,
,
~
"
\.~AOl -I
1
I
I r
.r c
c±>-
I fJ/
s~'1
~
Cf
" ..... , ..l -I.••:. "
f"£E1.! ,
U
p
-,
--,
C"3
~
~
c3
.-~ -lUVY'\ lOK S~V't:~8
)
\/a.",
J....
'3
FI~O -(,~iSlf"
FI ~... F2...
LJ
I -J
L~
...., AOI
-
TST- J 7 Stuurblok
4
Dit blok bestuurt de tweede ALU, P2, die getallen van elkaar af moet trekken en eventueel del en. Als P2 klaar is (READYP2) en er bevinden zich nog getallen in register F2 (EMPTYF2) dan wordt op de eerstvolgende klokpuls een getal uit het geheugen gelezen (ML of MR, afhankel~k van de ll-de bit uit RES van de instructiecode). Het adres is tevens het adres waar het resultaat later naar toe moet. Indien er ook een deling moet plaatsvinden wordt tijdens de volgende klokpuls een getal uit M in register R2 gezet. L Input
Output
bit 11 RES - geeft aan voor welk geheugen de update bestemd is. READYP2 - ALU P2 is klaar. register F2 is leeg. EMPTYF2 - geeft aan of er ook een deling moet D plaatsvinden. CLOCK - 10 MHz klok van de processor.
. R2,
R3
B8, B9 B10 STARTSUB CE
- "chip enable" signalen voor de bufferregisters R2 en R3. - buffer B8 of B9 wordt opengezet om het geheugen ML of MR te adresseren. - via deze buffer wordt het element geadresseerd waardoor gedeeld moet worden. - ALU P2 kan beginnen met aftrekken. - IIchip enable ll van de geheugens.
Het gearceerde blokje in het schema maakt een paar pulsen voor het aansturen van het geheugen op dezelfde w~ze als in stuurblok 2.
l'1L. A.
D
J'"
c.
~
,
D
rt
t-
er
I I
!
R
E'lt ... b~
Af'tS
"It.
'8~
~'1"htn()8
D
I I
I
~
4 u:s ri""\' \... til.
0.
I (C'i)
I I I L
00 610
cl.t It....
J-"'l-
'"jijSii •.• +--_. I I
-
~.Sl'
--",Itt.
R.'3 • _.
~_ _--,
~
JJL - )5 Stuurblok
5
Dit blok geeft het startsignaal voor een deling door P2, en signalen voor he~ in het geheugen schr~ven van hat resultaat van de bewerking van P2. Het resetsignaal dient voor de reset van P2 en het lezen van de data voor de volgende instructie uit F2. Het gearceerde blokje in het schema maakt een puIs voor het schrijven in het geheugen, zoals de pulsen voor lezen in blok 2. Input
: READY D CLOCK STARTSUBRESll
ALU P2 is klaar. er moet oak een deling plaats vinden. 10 MHz klok van de processor. P2 kan beginnen met aftrekken, READYP2 wordt gereset. - bit 11 van RES uit de instructiecode, kiest uit ML of MR.
Output : STARTDIV- P2 kan beginnen met delen. B8, B9 - het buffer B8 of B9 wordt opengezet voor de adressermng van ML of MR. B6, B7 - een van deze databuffers wordt opengezet voor het schrijven. DATAOUT - het getal wordt in het geheugen gezet. CE - "chip enable" voor het geheugen. READYP2 - ALU P2 was al klaar, nu is ook het wegschrijven van het getal voltooid. RESET - P2 wordt gereset en kan daarna verder gaan met het volgende getal uit F2.
-
jl,£11
,
-r~ ... d.
~l!1DY D
,
c
It.
-
s..'o
STAR-ro,,'
gB 6c:J
.,
I \
17
\ )'.:> ()
[ 1>
..r-t-
u ... .l'f div
lJ --M-
~
r C LO't(
~
to
l.
r ? vl.s
I
,
j)
I
I
q t
c.
STAtTSl1Q
f
L
-S t . " J ... blo J(
5"
~ ~ V('~"'~
Y'l..
-It...
-
--[
~ St. ",., ve..
.\... W'\.e",
~•
]Jl:-
~t·;
I~+-
'71,
Ii &. • t11\
HeM t)."5
PI • Pt
,a.cc,u'N'S
FI .F~
f" ~ $ "f I #II F1~ \'1' .,." -.lES I'"T."~
~;a:.i
1 f "Ri
, l
'1'«,,- ~"fA'T.
•
.'t;"TS«'
-,
I I
1
[--
-
I I
L
-" -1
--
--:--
I~.
I
II
u "LP
I
I
Pi
I
I
I
I
, ".
J
I I
Fi
I L_
I I 1
1
I
I r
I I
a
_
--.
....
--- --Bif
6S"
I "(f
I
....
I
Ft
I,
I
1
I
""."T'" "flU- STATi ~u"'IJ~
f
I
."',... "
I
I
r
vN'TS
~Q. se: b.-.y ~ ... e '" :""~ '%'J :': CJ /
I:t.jl
\0,,4 ,..h.lt
~
It!. ')'sl
'C'
ct
~Of
l,l.
",""
~
OOIC.. l1o.A.r
I
I
I I I
_J
:rrr- 2.2. -----------,-
1
I
+
8/
B~
J"I
1 I._
Ri
....
\
MeMOlI"
-""t
I
flf.ST /AI ~/tl'T
I
1l"'iI'T.a.~
I
I
I
I
I
";;;;iiiiiiil". ~ I ~ , ,
Q.(j
WIT ..
I
-,
I
I
I
r. .
I
I ...
--
i--
~
Cl "',." U.,.
- -
I
,
- -t ~. II R'5 .., --
---
I
.
I
I
I'
I
I
:~~~-
I
I I
r
I
Pi
Fi
I
I I
..
I"
I
I I
1
I
1 J
I
L
I
«-
T .. "1'1U'-ST"ATi
~ sc ~ l-, t.1CAt.1'\;"" "f d""~~
VOO'l'
I XJ *" G\.ij
I/O"...
I
Ci )
I
"'..
·1
I ---
I
l'!:
_.--..
----
-_ _-..
--
t
I I
_J
