thesis_main3.dvi

Size: px

Start display at page:

Download "thesis_main3.dvi"

かずまさののした
4 years ago
Views:

1 FPGA Udorn Lerdtanaseangtham

2 Ullmann Refinement procedure G α G β G α G β Ullmann G α G β G α G β FPGA i

3 A 73 A A.2 I/O A A A A ii

4 [] NP [2] Ullmann[] refinement procedure ( Ullmann ) [6] FPGA (Field Programmable Gate Array) Ullmann Ullmann [6]. [6] FPGA 33 MHz Ullmann ( ) 333 MHz PentiumII 5 33 MHz [6] () (2) OPERL [4] FPGA 5 2 Ullmann 2. [6] G p V q E G =(V, E) V v i ( i p) E e k ( k q) {v i,v j } (i j). {v i,v i } {v i,v j } {v j,v i } E G A A =[a ij ] p p a ij {, {i, j} Eor{j, i} E a ij =, {i, j} E and {j, i} E ( i, j p) 2 G α =(V α,e α ) G β =(V β,e β ) (p α p β ). G β G α V α V β, E α E β 2 G α G β G α 2 G β 2 G α G β (isomorphic) V V β,e E β f G α

5 G β i, j({v αi,v αj } E α {f(v αi ), f(v αj )} E) f : V α V () f f V α v α,v α2,,v αpα v α,v α2,,v αpα, 2,,p α p α d v αd f ( d p α ). p K p G ed K p q ed = q p(p ) 2 (2) G (p ) q p G (3) ed 2 p (3) (p ) (tree) p (p ) ( ) (3) 2.2 Ullmann Ullmann [] 2 refinement procedure refinement procedure 2.2. Refinement procedure 2. () f f pβ P pα p α p β refinement procedure Refinement procedure G α,g β A =[a ij ],B =[b ij ] M =[m ij ] p α p β m ij = v αi v βj M deg(v) v m ij = {, deg(v βj ) deg(v αi ), Refinement procedure i, j (4) m ij = M x ((a ix =) ( y) (m xy b yj = ) ) (4) x p α y p β Refinement procedure B j B j M i M i elim refinement procedure 2

6 deg i v αi sc p β := & NOT do-while,while,if,break,return C Refinement procedure M(M i ) v αi v βj FAIL do { elim := ; i := ; while(i p α) { j := ; sc := 2 p β ; while(j p β ) { if((m i &sc ){ h :=; while(h deg i ) { x := lst h ; if((m i &B j ){ M i := M i &NOTsc; elim := elim +; h := h +; break; } h := h +; } } sc := sc/2; j := j +; } if(m i = ) return(fail); i := i +; } } while(elim ); return(succeed); : Refinement procedure [] (depth-first search) 2 M M M := M M M M d := M M M d M H i = k i v αi v βk ( i p α ).F i = v βi ( i p α ) make lst i and deg i G α refine M refinement procedure Ullmann refinement procedure refinement procedure O(p α p 2 β ) [7] p α =5,p β =5 OR2CxxA FPGA [6] refinement procedure [6] 3

7 Step. M := M ; d := ; H := ; for all i :=,..., p α set F i := ; make lst i and deg i for all i :=,..., p α; refine M; if exit FAIL then go to step 7; Step 2. If there is no value of j such that m dj = and f j = then go to step 7; M d := M; k := ; Step 3. k := k +; if m dk =orf k = then go to step 3; for all j k set m dj := ; refine M; if exit FAIL then go to step 5; Step 4. if d<p α then go to step 6 else give output to indicate that an isomorphism has been found; Step 5. If there is no j>ksuch that M d (d, j) = and f j = then go to step 7; M := M d ; go to step 3; Step 6. H d := k; F k := ; d := d +; go to step 2; Step 7. If d = then terminate algorithm; F j :=, if j H i for all i<d; d := d ; M := M d ; k := H d ; go to step 5; 2: [] 2.3. [6] d G α G β ( ) ( ) 3 etsa edge list table starting address eta, etb edge list table B G β while,if,return C n := etsa(d); i := ; a := eta(n); b := etb(n); while (a orb ){ if (B(p(a) p(b)) = ) return(ng); i := i +; a := eta(n + i); b := etb(n + i); } return (OK); 3: [6] f e αi e βj ( ) e βj G β E β ( ) 4 ( STV algorithm ) depth vb(i)( i p α ) ( edge existence check module ) exist result a b depth d( d p α ) vb(i) G α v αi ( i p α ) G β v βj j Edge list table p α + q α p α 2 (,) eta, etb Edge list table etsa(edge list table starting address) p α, d edge list table 4

8 Mux a vb vb2 vb3... vb(pa) Mux b STV algorithm depth edge list table starting address address data n edge list table address data,2, 2,2 3, 4,3 5 2,3 6, edge existence check module data data2 start address address result control unit exist edge existence check algorithm 4: [6] edge check module a B Pb Ba exist b edge existence check module 5: [6] 5 {v βa v βb } B G β B SRAM p β p β [6] Ullmann 6 M 2.2. d M d M d p β used used(i) := v βi p p α p(i) v αi 7 priority encoder 2 DEC control [6]. 5

9 M := M ; IM := M ; d := ; used := ; while () { current := M d & used; while (current ){ current(i) = i ; p(d) := i; current(i) := ;flag := ; ; if ( = OK) { if (d = p α ) ; else {used(i) :=; M d := current; d := d +; flag := ; break;} } } if (flag) continue; if (d = ) terminate algorithm; M d := IM d ; d := d ; used(p(d)) := ; } 6: [6] control priority encoder IM M and current DEC P edge check module used DEC DEC =? d +/- = pa? 7: [6] 3 Ullmann ( Ullmann ) 3. [6] 6

10 3.. [6] (3) refinement procedure M refinement procedure FAIL exit M G α G α refinement procedure deg(v αi ) > deg(v βj ) ( ) (3) [6] ed α =.2 (A) (B) (A),(B) (A),(B) (A) G β G α G α G β (B) G β G α G α G β 3.2 G α G β G α G β 7

11 3.2. G α G β G α,g β ed α,ed β G α,g β p α,p β G α,g β q α,q β p α,p β,q α,q β p α p β q α q β p α p β p β p α (5) G α G β q β q α q β q α (6) (3) p α,p β p α p β 2 ed α (7) 2 ed β (8) (2) q α = p α(p α ) 2 q β = p β(p β ) 2 ed α (9) ed β () q α,q β (9),() q α,q β ( 6 ) q α,q β q α,q β round() ( ) pα (p α ) q α = round ed α () 2 ( ) pβ (p β ) q β = round ed β (2) a p, q G (i) p (ii) q (p ) q G p q (5),(6),(7) (2) C G [c ij ] if,while,for,break,return C G α G β G α G β 9 A G α [a ij ]( i, j p α ) B G β [b kl ] ( k, l p β ) G α G β G α [a ij ] G β [b ij ] G β = G α (p β p α ) (q β q α ) G β 8

12 gen graph(c, p, q) { while(){ for all i, j :=,...,p, set c ij := ; for(k := ; k (p ); k ++){ i, j (i j, i, j p); C[i][j] :=; } if(c = ) break; } for(k := ; k q (p ); k++) { while() { m, n (m n, m, n p); if(c mn ){ c mn := ; break; } } } return C; } 8: gen graph p - p A q q - q B p p 9: G α G β (p β p α ) G β (p β p α ) (3) q β q α p β p α (3) G α G β p α,p β,q α,q β (5),(6),(7) (3) if,while,do-while,for,break C return X, Y X Y G α p α, q α G β p β, q β G α A G β B =[b ij ] G α G β (q β q α ) G β G β G α G β G α G β G α G β G α G β G α G β G α G β Ga into Gb() 9

13 Ga into Gb(p α,q α,p β,q β ) { gen graph(a, p α,q α ); while() { for all i, j :=,...,p β, set b ij := ; A B for(k := q α ; k q β ; k ++){ while() { i, j (i j, i, j p β ); if(b ij ){ b ij := ; break; } } } if ( B = ) break; } return A, B; } : G α G β Ga into Gb G α p α, q α G β p β, q β G α G β A, B G β G α G α G β G α G β G α G β Ga notin Gb(p α,q α,p β,q β ) { while() { gen graph(a, p α,q α ); gen graph(b, p β,q β ); if( A B ) break; } return A, B; } : G α G β Ga notin Gb 3.3 [6] 33MHz OPERL Ullmann FreeBSD-3. C 999

14 C Intel Pentium-II 4MHz Intel 44BX AGPset 52KB(Pentium-II ) SDRAM 256MB(6ns) FreeBSD-3. gcc ver : Ullmann 3.4 Ullmann G α,g β ed α,ed β G α,g β p α,p β G α G β G α G β ed α p α ed β p β (I) G α G β p α ed α p β ed β (5),(6),(7) (3) ed α,ed β p α,p β (5),(6),(7) (3) : (ed α,ed β )=(.2,.2) (5),(6) p α 2.2 =, p β 2.2 = p α = () p β (7) q α = round ( ) =9 (8) q β 9 ( (2) ) p α = (3) p β p β =,, 2,... p α = () p β (7) q α = round ( 2.2 ) = (8) q β ( (2) ) p α = (3) p β p β =, 2, 3,... 2: (ed α,ed β )=(.4,.2) (5),(6) p α 2.4 =5,p β 2.2 = p α =9

15 () p β (7) q α = round ( ) =4 (8) q β 9 (2) q β 4 p α,q α (3) p β 9 q β 4 q β p β +5 p β q β 5 p β = q β = round ( ) =9 p β = q β = round ( 2.2 ) = p β =2 q β = round ( ) =4 p β =3 q β = round ( ) =6 p β =4 q β = round ( ) =8 p β =5 q β = round ( ) =2 p β =6 q β = round ( ) =24. p α =9 (3) p β p β =5, 6, 7,... (5),(6),(7) (3) p α ed α p β ed β p α,p β 5 ed α,ed β p α,p β ed α,ed β ed (dense ) ed α ed β 4 (a) ed α,ed β : (ed α,ed β )=(.2,.2) (b) ed α,ed β : (ed α,ed β )=(.2,.4) (c) ed α,ed β : (ed α,ed β )=(.4,.2) (d) ed α,ed β : (ed α,ed β )=(.4,.4) 4 p α p β 2,3,4,5 2: G α G β (ed α,ed β )=(.2,.2) p α p β p β p α ed α ed β q α q β (a) (d) ed α,ed β ed α,ed β ed α ed β 2,3,4,5 ed α ed β 2

16 3: G α G β (ed α,ed β )=(.2,.4) p α p β p β p α : G α G β (ed α,ed β )=(.4,.2) p α p β p β p α ed α,ed β ed α,ed β G α,g β 5 (II) G α G β G α G β p α p β (I) G α G β (3) G α G β (5),(6),(7) (2) p α,q α G α G β G α G α G β 7,8,9, p α,p β G α G β 7,8,9, ed α ed β q α q β G α G β G α G β 3

17 5: G α G β (ed α,ed β )=(.4,.4) p α p β p β p α : G α G β ed α,ed β Given Average s.d. ed α ed β ed av. α ed av. β ed s.d. α ed s.d. β Ullmann Ullmann FreeBSD getrusage() [] step step7 getrusage() G α,g β Ullmann C OPERL 6.5MHz OPERL 2,3 [ ] G α,g β 4

18 7: G α G β (ed α,ed β )=(.2,.2) p α p β p β p α : G α G β (ed α,ed β )=(.2,.4) p α p β p β p α : G α G β (ed α,ed β )=(.4,.2) p α p β p β p α

19 : G α G β (ed α,ed β )=(.4,.4) p α p β p β p α : G α G β ed α,ed β Given Average s.d. ed α ed β ed av. α ed av. β ed s.d. α ed s.d. β G α G β (ed α,ed β )=(.2,.2), (.2,.4), (.4,.2), (.4,.4) 4,5,6,7 (a) (b) Ullmann (c) Ullmann (a),(b),(c) p α x (a),(b) y ( : ) (c) y ( : ) (c) Ullmann (ed α,ed β )=(.2,.4) Ullmann (ed α,ed β )=(.4,.4) Ullmann Ullmann (ed α,ed β )=(.2,.2) Ullmann G α G β (ed α,ed β )=(.2,.2), (.2,.4), (.4,.2), (.4,.4) 8,9,2,2 (ed α,ed β )= (.2,.2), (.4,.2), (.4,.4) Ullmann refinement procedure (Step ) Ullmann 6

20 M := M ; IM := M ; d := ; used := ; [ ] while () { current := M d & used; [] while (current ){ current(i) = i ; [ ] p(d) :=i; current(i) :=;flag := ; [ ] ; if ( =OK [ ]) { if (d = p α []) ; [] else {used(i) :=; M d := current; d := d +; flag := ; break; [ ] } } } if (flag) continue; if (d = []) terminate algorithm; [] M d := IM d ; d := d ; [] used(p(d)) := ; [] } 2: n := etsa(d); i := ; a := eta(n); b := etb(n); while (a orb ){ [] if (B(p(a) p(b)) = []) return(ng); [] i := i +; a := eta(n + i); b := etb(n + i); [ ] } return (OK); [] 3: (ed α,ed β )=(.2,.4) Ullmann 7

21 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (a) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (c) Ullmann 4: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) (G α G β ) 8

22 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (a) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (c) Ullmann 5: (ed α,ed β )=(.98,.3976),(s.d. α, s.d. β )=(.267,.23) (G α G β ) 9

23 . p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (a). p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (c) Ullmann 6: (ed α,ed β )=(.39436,.9772),(s.d. α, s.d. β )=(.783,.27) (G α G β ) 2

24 run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. e (a). p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 ratio(times) (c) Ullmann 7: (ed α,ed β )=(.39466,.396),(s.d. α, s.d. β )=(.665,.47) (G α G β ) 2

25 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (a) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. ratio(times) (c) Ullmann 8: (ed α,ed β )=(.98,.9758),(s.d. α, s.d. β )=(.267,.28) (G α G β ) 22

26 p(beta)=2 p(beta)= p(beta)= run time(sec.). 2 (a) p(beta)=2 p(beta)= p(beta)= run time(sec.). 2 (b) Ullmann p(beta)=2 p(beta)= p(beta)= ratio(times) 2 (c) Ullmann 9: (ed α,ed β )=(.9899,.39798),(s.d. α, s.d. β )=(.43,.286) (G α G β ) 23

27 . p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.). e (a).. p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.). e-5 e (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. ratio(times) (c) Ullmann 2: (ed α,ed β )=(.39236,.9788),(s.d. α, s.d. β )=(.764,.274) (G α G β ) 24

28 run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. e (a) run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. e (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 ratio(times) (c) Ullmann 2: (ed α,ed β )=(.39436,.39624),(s.d. α, s.d. β )=(.66,.468) (G α G β ) 25

29 4 FPGA Lucent ORCxxA FPGA[5] OPERL [4] OPERL 2 FPGA PCI FPGA, USER FPGA ( 22) PCI FPGA PCI USER FPGA SROM USER FPGA (bit stream) USER FPGA FPGA Lucent OR2C5A FPGA USER FPGA OR2C5A 9,2 44,2 [5] OR2C FPGA PFU(Programable Function Unit) OR2C5A 4PFU OR2C5A OPERL PCI 2 PCI OPERL ( A ) 22: OPERL [4] 2: C AMD K6-III 4 MHz Intel 43HX 256KB(K6-III ) DRAM 64MB FreeBSD-2.2. gcc ver

30 USER FPGA (Unit) PCI (Unit) 23: 2 Unit, Unit 2 2 G α G β G α ( ) G β G β 2 PCI A 4..3 G α A G α p α 27

31 G β B M,IM Edge list table (eta,etb) Edge list table starting address (etsa) 4..4 G α,g β 5 (p α,p β ) = (5, 5) 2 (,) IM,M,B VHDL Lucent OR2CxxA FPGA RAM 4 FPGA 4 RAM p α G α q α G α p β G β ETS(A),ETS(B) 4 Edge list Table (data) 2 (data2) ETS(A),ETS(B) log(p α + q α ) log(p β ) 6x4 RAM RAM ETS(A),ETS(B) MUX ETS(A) 25 ETS(B) ETS(A) 28

32 From Main Control Unit From Priority Encoder From External Circuit From Main Control Unit To Main Control Unit PWrite PSel d memsel reset sub start sub log( p ) ETSAWrite MBWrite ETS_AWrite ETS_BWrite log( p ) External Input Adr 4 log( p ) External Input4 a p(a ) adr in data in P adr in2 adr in data in data out data out2 ETSA p(b) result end sub log( p ) log( p ) data out log( p ) start address External Input Adr 3 log( p ) log(p + q ) log(p + q ) External Input Adr 5 log(p + q ) adr Sub Control Unit External Input3 log( p ) External Input5A External Input5B adr in data in adr in data in adr in data in B ETS(A) ETS(B) data out data out data out a b p Edge Check exist 24: 29

33 address Psel 3 E WPE ETS(A) # RCF6X4Z TRI data out Psel WPE ETS(A) #7 RCF6X4Z TRI data out 4 a d 4 25: ETS(A) ETSA 4 Edge list table starting address ETSA log(p β ) log(p α + q α ) 6x4 RAM P P( 7) 4 vb(i)( i p α ) (MUX) P log(p β ) log(p β ) log pα [6] 4 p α log(p α ) log 4 p α p α 4 i 2 2 log(p log pα log pα α) ( 2 2 ) i= Lucent OR2CxxA [8] 4 (RD4P3D).5 4 (MUX4).25 2 (MUX2).25 p α =5 8 PFU 6x2 (DCE6X2) p α =5 2 PFU B Edge Check 5 B log(p β ) log(p β ) p β Edge Check p β, log(p β ) B 6x4 RAM Edge Check G β 2 ( ) B Edge Check 26 B B 5 2 B 4, 5 B B Sub Control Unit 3

34 MBwrite B # RCF6X4Z data out B_DO[3:] P_B_out[3:2] 2 WPE TRI 4 exist WPE B #3 RCF6X4Z TRI data out B_DO[5:2] P_B_out[:] 26: B Edge Check 27 reset sub sub control unit (4.2.2 ) reset sub ( ) sub control unit start sub (4.2.2 ) start sub start address Edge list table ETSA log(p α + q α ) exist {v βa,v βb } Edge Check adr Edge list table start address adr log(p α + q α ) result result result OK( ) d v αd e α G β e β result NG( ) G β e β end sub end sub end sub 3

35 reset sub= start sub= INIT i= adr=start address i=i+ adr=start address + i INCREMENT start sub= reset sub= CHECK ETS (a = ) and (b=)? True False exist= CHECK B s EDGE RESULT OK B(p(a),p(b)) result= end sub= reset sub= RESULT NG result= end sub= exist= reset sub= 27: INIT i adr start address start sub CHECK ETS Edge list table (data) 2 (data2) RESULT OK CHECK B s EDGE CHECK B s EDGE CHECK EDGE exist exist INCREMENT RESULT NG INCREMENT data data2 i adr start address + i CHECK ETS RESULT OK result end sub reset sub RESULT NG result end sub reset sub

36 Reset main From External From External Circuit From External Circuit To External Circuit MBWrite memsel External Input Adr 2 p log( ) External Input2 p Reset main PaWrite External Input p adr in data in IM =? =? p data out d found end main check EqOne check EqPa dwrite dout log( ) Main Control Unit Next d p adr in data in reset sub start sub PSel check current zero currentwrite usedsel currentsel usedwrite M data out p p p p used p Priority Encoder p current Start main Decode& Set Decode& Set Decode& Set Circuit MSel MWrite p PWrite PrioWrite =? log( p ) log( p ) log( p ) i a p(a ) adr in data in log( p ) P adr in2 To Sub Control Unit data out data out2 p(b) b a d 28: 33

37 Start main= reset main= d =? CHECK COMPLETE dwrite= Next d= usedwrite= usedsel= currentwrite= currentsel= PSel= PrioWrite= reset sub= start sub= found= end main= check EqOne= True False end main= INIT MAIN reset main= Start main= END MAIN check EqOne= CHECK CURRENT False currentsel= currentwrite= MWrite= MSel= dwrite= usedwrite= current? reset sub= found= SET CURRENT MWrite= Msel= PSel= PWrite= dwrite= Next d = dout - True SET REST PART found= NEXT DEPTH MWrite= MSel= dwrite= usedwrite= Next d = dout + MWrite= Msel= PSel= PWrite= dwrite= usedwrite= usedsel= FOUND result= end sub= check EqPa= False check EqPa= LOAD P NG True reset sub= currentsel= currentwrite= PSel= PWrite= PrioWrite= d = p? SET P AND CURRENT start sub= CHECHK DEPTH EDGE CHECK ALGORITHM currentsel= currentwrite= PSel= PWrite= PrioWrite= Call EDGE EXISTENCE CHECK ALGORITHM OK result= end sub= 29: M IM 7 M IM M IM log(p β ) log(p β ) 6x4 RAM current 7 current current p β current 4 used 7 used used p β used 4 d 7 d d log(p α ) d 4 p α p α p α log(p α ) p α 4 34

38 Priority Encoder current G α G β 7 Priority encoder Priority encoder p β log(p β ) i Priority Encoder Priority Encoder current i log(p β ) i 4 Decode & Set p β n 2 2 input input2 input p β input2 log(p β ) input p β input2 n p β input ( ) 2, input2 () 2 ( ) 2 Decode & Set p β n 2 2 input input2 input p β input2 log(p β ) input p β input2 n p β input ( ) 2, input2 () 2 ( ) 2 =? d( d) log(p α ) d 4 =p α? d( d) p α log(p α ) d p α 4 Main Control Unit 29 Reset main ( A ) Reset main Reset main Main Control Unit (d, current, used,i) 35

39 Start main ( A ) Reset main Start main check EqOne d =? check EqPa d p α =p α? check current zero d v βj =? dout d dout log(p α ) reset sub start sub PSel P PSel d Edge list table PWrite P PWrite P PrioWrite i PrioWrite i Priority Encoder currentsel current currentsel AND (M d & used ) Decode & Set (current(i):= ) ( 6 ) currentwrite current currentwrite usedsel used usedsel Decode & Set (used(p(d)):= ) Decode & Set (used(i):= ) ( 6 ) usedwrite used usedwrite 36

40 Msel M Msel IM (M d :=IM d ) current (M d :=current ) ( 6 ) MWrite M MWrite Next d d Next d dout dwrite d dwrite Next d found found end main end main INIT MAIN Start main= Start main= Reset main= SET CURRENT d (dwrite=, Next d= x). Decode & Set (used(i):= ) used (usedsel=) used (usedwrite=) Decode & Set (current(i):= ) current (currentsel=) current (currentwrite=) d P (PSel=) i (PrioWrite=). (reset sub=) (start sub=) (found=) (end main=) SET CURRENT current AND (M d & used ) AND currentsel currentwrite M MSel M d dwrite used SET CURRENT CHECK CURRENT current (reset sub=) found (found = ) =? check current zero CHECK COMPPLETE SET P AND CURRENT 37

41 SET P AND CURRENT d v αd i P current i i P Psel Pwrite current i Decode & Set current i i (PrioWrite=) EDGE CHECK ALGORITHM EDGE CHECK ALGORITHM P ETS(A) Psel Start sub end sub result end sub result= end sub= CHECK DEPTH result= end sub= CHECK CURRENT CHECK DEPTH d p α =p α? check EqPa FOUND NEXT DEPT FOUND found CHECK CURRENT NEXT DEPTH d+ v βi (=) used i current M d d used i usedsel usedwrite current M d M MSel Mwrite d next d d dwrite SET CURRENT CHECK COMPLETE d =? check EqOne END MAIN SET REST PART SET REST PART d d-, IM d M d d IM d M MSel Mwrite d Next d d dwrite LOAD P LOAD P v αd v βi P d used i P d Psel PWrite used i decode & set decode & set used usedsel CHECK CURRENT END MAIN end main reset main INIT MAIN 38

42 4.3 OPERL 4.3. VHDL Lucent OR2CxxA ( RAM ) VHDL (VHDL ) Synopsys Design Compiler VHDL OR2C FPGA 3 EDIF 3: Ultra SPARC 67MHz 28MB Solaris 2.5. ORCA FPGA ( ) EDIF ncd ORCA FPGA Lucent ORCA Foundry (bit stream) USER FPGA 4: Intel Pentium II 45 MHz Intel 44BX 52KB(CPU ) SDRAM 256MB MS-Windows NT Workstation OR2C FPGA 5 PFU 6 4FPU OR2C5A 2 39

43 PCI FPGA PCI 5: PFU (MHz) Unit Unit PFU 6 PFU RAM OR2C FPGA SRAM FPGA FPGA 5 PFU 6 PFU PFU PFU 6 6 PFU 6: PFU PFU RAM( ) ( A ) 4 PFU 7 n (n n 4) 2,, 3,,,2, 4,,,2,3 3 PFU 2 PFU 6 6 OR2C FPGA 5 OR2C5A 2 Ullmann, 2 2 4

44 7: PFU 2C5A 2C26A 2C4A PFU PFU (%) (PFU :83) 2 PFU (%) (PFU :343) 3 PFU (%) (PFU :499) 4 PFU (%) (PFU :664) Ullmann ( ) ( ) 3 j j T2 T 5..2 G α G β (ed α,ed β )=(.2,.2), (.2,.4), (.4,.2), (.4,.4) Ullmann 3, 32, 33, 34 ( ) 5% G α G β (ed α,ed β )=(.2,.2), (.2,.4), (.4,.2), (.4,.4) Ullmann 35, 36, 37, 38 ( ) 5% G α,g β 2 Ullmann 5.2. G α,g β p α,p β,ed α,ed β 2 p α,p β 5, (ed α,ed β )=(.2,.2), (.2,.4), (.4,.2), (.4,.4) 4

45 #define LOOP for (p α p β ) { for(j=;j<2;j++) { T: getrusage() for( LOOP) { if(j) { ; ; } } T2: getrusage() temptime[j]= j ; } used time = (temptime[]-temptime[])/loop; used time ; } 3: Ullmann 39 (ed α,ed β )=(.2,.2) 4 (ed α,ed β )=(.2,.4) 4 (ed α,ed β )=(.4,.2) 42 (ed α,ed β )=(.4,.4) ( 39 42) (b) (c) PCI OPERL Unit Unit inl() [4] 43 (ed α,ed β )=(.2,.2) 44 (ed α,ed β )=(.2,.4) 45 (ed α,ed β )=(.4,.2) 46 (ed α,ed β )=(.4,.4) 2 (ed α,ed β )=(.2,.4), (.4,.4) 4 (ed α,ed β )=(.2,.2), (.4,.2) Ullmann 42

46 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (a) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (c) Ullmann 3: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) (G α G β ) 43

47 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (a) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (c) Ullmann 32: (ed α,ed β )=(.98,.3976),(s.d. α, s.d. β )=(.267,.23) (G α G β ) 44

48 . p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (a). p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (c) Ullmann 33: (ed α,ed β )=(.39436,.9772),(s.d. α, s.d. β )=(.783,.27) (G α G β ) 45

49 run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. e (a). p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 ratio(times) (c) Ullmann 34: (ed α,ed β )=(.39466,.396),(s.d. α, s.d. β )=(.665,.47) (G α G β ) 46

50 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (a) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. run time(sec.) (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. ratio(times) (c) Ullmann 35: (ed α,ed β )=(.98,.9758),(s.d. α, s.d. β )=(.267,.28) (G α G β ) 47

51 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.). (a) p(beta)=2 p(beta)= p(beta)= run time(sec.). 2 (b) Ullmann p(beta)=2 p(beta)= p(beta)= ratio(times) 2 (c) Ullmann 36: (ed α,ed β )=(.98,.3976),(s.d. α, s.d. β )=(.267,.23) (G α G β ) 48

52 . p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.) (a).. p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= run time(sec.). e-5 e (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)=. ratio(times) (c) Ullmann 37: (ed α,ed β )=(.39436,.9772),(s.d. α, s.d. β )=(.783,.27) (G α G β ) 49

53 run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. e (a) run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. e (b) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 ratio(times) (c) Ullmann 38: (ed α,ed β )=(.39466,.396),(s.d. α, s.d. β )=(.665,.47) (G α G β ) 5

54 run time(sec.).. p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (a) Ullmann number of patterns (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 39: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) (G α,g β ) 5

55 run time(sec.) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (a) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (b) number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 4: (ed α,ed β )=(.98,.3976), (s.d. α, s.d. β )=(.267,.23) (G α,g β ) 52

56 run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns e (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 4: (ed α,ed β )=(.39345,.9772), (s.d. α, s.d. β )=(.756,.278) (G α,g β ) 53

57 run time(sec.)... p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5. number of patterns e (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 (c) 42: (ed α,ed β )=(.39474,.396), (s.d. α, s.d. β )=(.665,.47) (G α,g β ) 54

58 ratio(times). p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (a) 2 Ullmann number of patterns (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 43: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) (G α,g β ) 55

59 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) 2 Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (b) number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 44: (ed α,ed β )=(.98,.3976), (s.d. α, s.d. β )=(.267,.23) (G α,g β ) 56

60 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) 2 Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 45: (ed α,ed β )=(.39345,.9772), (s.d. α, s.d. β )=(.756,.278) (G α,g β ) 57

61 ratio(times) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (a) 2 Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 (c) 46: (ed α,ed β )=(.39474,.396), (s.d. α, s.d. β )=(.665,.47) (G α,g β ) 58

62 p α,p β,ed α,ed β p α,p β,ed α,ed β Ullmann.3 ( ).3 47 (ed α,ed β )=(.2,.2) 48 (ed α,ed β )=(.2,.4) 49 (ed α,ed β )=(.4,.2) 5 (ed α,ed β )=(.4,.4) Ullmann ( ) 5 (ed α,ed β )=(.2,.2) 52 (ed α,ed β )= (.2,.4) 53 (ed α,ed β )=(.4,.2) 54 (ed α,ed β )=(.4,.4) 2 ( 52,54 ) p α,p β,ed α,ed β K K K K K=2 55 (ed α,ed β )=(.2,.2) 56 (ed α,ed β )=(.2,.4) 57 (ed α,ed β )=(.4,.2) 58 (ed α,ed β )=(.4,.4) 55,57,

63 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (a) Ullmann number of patterns (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= 47: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) 6

64 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (b) number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 48: (ed α,ed β )=(.98,.3976), (s.d. α, s.d. β )=(.267,.23) 6

65 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= 49: (ed α,ed β )=(.39345,.9772), (s.d. α, s.d. β )=(.756,.278) 62

66 ratio(times) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 5: (ed α,ed β )=(.39474,.396), (s.d. α, s.d. β )=(.665,.47) 63

67 ratio(times). p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (a) Ullmann number of patterns (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= 5: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) 64

68 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns ratio(times) (a) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (b) number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 52: (ed α,ed β )=(.98,.3976), (s.d. α, s.d. β )=(.267,.23) 65

69 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= 53: (ed α,ed β )=(.39345,.9772), (s.d. α, s.d. β )=(.756,.278) 66

70 ratio(times) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 54: (ed α,ed β )=(.39474,.396), (s.d. α, s.d. β )=(.665,.47) 67

71 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) (a) Ullmann number of patterns (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= 55: (ed α,ed β )=(.98,.9758), (s.d. α, s.d. β )=(.267,.28) 68

72 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) Ullmann p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (b) number of patterns p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= (c) 56: (ed α,ed β )=(.98,.3976), (s.d. α, s.d. β )=(.267,.23) 69

73 p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= ratio(times) number of patterns (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= 57: (ed α,ed β )=(.39345,.9772), (s.d. α, s.d. β )=(.756,.278) 7

74 ratio(times) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (a) Ullmann (b) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 number of patterns (c) p(beta)=5 p(beta)=4 p(beta)=3 p(beta)=2 p(beta)= p(beta)= p(beta)=9 p(beta)=8 p(beta)=7 p(beta)=6 p(beta)=5 58: (ed α,ed β )=(.39474,.396), (s.d. α, s.d. β )=(.665,.47) 7

75 6 OPERL OR2C5 FPGA (p α,p β )= (5, 5) OR2C5A 2 6.5MHz 2 Ullmann (Pentium II 4MHz ) 4 FPGA OPERL [] J. R. Ullmann: An Algorithm for Subgraph Isomorphism, Journal of the Association for Computing Machinery, Vol. 23, No., pp. 3-42, 976. [2] Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP- Completeness, W. H. Freeman, San Francisco, 979. [3] Duncan A. Buell et al.: Splash 2: FPGAs in a Custom Computing Machine, IEEE Computer Society Press, Los Alamitos, 996. [4] : PCI CPSY96-97 pp [5] : ORCA TM OR2CxxA OR2TxxA 997,,, 997. [6], : FPGA, 999 ( A-3-2), [7] : Ullmann 2, 2. [8] Lucent Technologies Inc.: Lucent Techologies ORCA TM Foundry Library Manual Version 9.35, Lucent Technologies Inc., U.S.A., 999. [9] Lucent Technologies Inc.: ORCA TM FPGA PCI, Lucent Technologies Inc., U.S.A., 996. [] : C

76 A OPERL [4] OPERL A. 256 OPERL I/O IM,M,B,ETSA,ETS(A),ETS(B) OPERL (OPERL ) OPERL I/O M [4] [4] I/O IM,M,B,ETSA,ETS(A),ETS(B) 8 8: 2 p α,p β 5 ( ) ( ) 6 4 ( ) M/IM B ETSA ETS(A) ETS(B) p α,p β 5 28 Reset main, Start main p α (count unit) (carry) (found) (end unit)

77 A.2 I/O A I/O 59 I/O h RESERVED = s ETSA F h h M/IM B ETS(A) s address F h h ETS(A) #7 #6 #5 #4 #3 #2 # # ETS(B) s address ETS(A) s address 27 F h h ETS(B) #7 #6 #5 #4 #3 #2 # # ETS(B) s address 27 F h 59: I/O ( 6 ) ETSA (Reset unit, Start unit) p α (unit en) (reset system) Fh 7 ETSA h h ETSA Fh ETSA 5 h 8 Reset unit h 8 Start unit 2h 8 p α 3h 9 2 unit en unit en () 2 () 2 3h 8 reset system reset system Fh

78 Reset_unit Start_unit h h RESERVED=s RESERVED=s 2 h RESERVED=s P 3 h ETSA RESERVED=s F h use3_8 reset_system use7_ unit_en[3:] 6: Fh M/IM B 5 B h Fh B M IM h Fh M/IM ETS(A) ETS(A) x4 ETS(A) 8 6x x4 3 # # ETS(A) 5 # 6x4 4 7 # # ETS(A) 6 3 # 2 6x4 75

79 8 #2 #2 ETS(A) #2 3 6x4 2 5 #3 #3 ETS(A) #3 4 6x4 6 9 #4 #4 ETS(A) #4 5 6x #5 #5 ETS(A) 8 95 #5 6 6x #6 #6 ETS(A) 96 #6 7 6x #7 #7 ETS(A) 2 27 #7 8 6x4 4 4 ETS(B) ETS(B) ETS(A) ETS(B) ETS(A) A.2.2 OPERL I/O FFh 4 I/O I/O 6 6 I/O (addr) addr Fh 6 7 (grp) grp grp 2 grp 3 grp Eh BIOS ioctl 5 E grp addr Control or ETSA M/IM, B ETS(A) ETS(B) 6: I/O A I/O 62 2 h end unit h found 76

80 h 2 carry h 3 end unit h 4 found h 5 carry h 6 8 count unit h 9 3 count unit count_unit count_unit carry found end_unit h end_unit found carry RESERVED = s FF h 62: I/O ( 63 ) h end main h found h 2 over flow h 6 3 count found h 2 2h 3 3h A

81 found_count over_flow found end_unit RESERVED = s h RESERVED = s 4 h RESERVED = s 8 h RESERVED = s C h RESERVED = s FF h 63: I/O 4 65 datvldrr datvldrr clk d2 sel unit en ( ) PCI (33MHz) (6.5MHz). XXX c2 (XXX ) PCI ( ) ldirr c2 PCI FPGA 32 rdwrrr c2 H L ldarr c2 PCI FPGA datvldrrr c2 Pldio H Pldio memiorr c2 I/O H I/O unit enrr c2 H 78

82 2 to 4 DeMUX with Enable( ) ctrle ETSA P α, MBwe M,B ETS awe ETS(A) ETS bwe ETS(B) 2 to 4 DeMUX with Enable( ) P α Resete Starte Pawe P α memsel 79

83 IBT IBTS IBTS PrdwrN PdatavldN ldirwe D SP FDP3AX Pldio IBTS OBZ2 D SP FDP3AX ldoen IBTS PaddrvldN ldir ldorwe ldo ldarwe datavld Pclkout clk addrvldn rdwrn datavldn D FDS3AX D SP FDP3AX D SP FDP3AX ldar IBTS PmemioN memion memior E ldarr_c2[7:6] D FDS3AX ldarr_c2 32 ldor ldi rdwrr D SP FDP3AX Dece D FDS3AX datvldr datvldrrr_c2 rdwr D FDS3AX datvldrr memiorr_c2 rdwrrr_c2 D FDS3AX D FDS3AX 32 ldirr_c2 D FDS3AX clk_d2 D FDS3AX temp_resetn clk Konishi s Algorithm Circuits use3_8 line_three datvldr rdwrr memior sel_unit_en D FDS3AX unit_enrr_c2 unit_enr 4 D SP FDP3AX X4 use3_8 reset_system line_three datvldr rdwrr memior reset_alln 32 unit_out unit_out ldar[3:2] ldar[7:4] ldar[3] ldar[2] unit2_out unit3_out D FDS3AX found_subr Reset_unit end_unit over_flow count_found 4 4 X4 (unit_out[2]) (unit_out[3:6]) found (unit_out[]) (unit_out[]) end_all_algn clk D SP FDP3DX CD FADD4 CO CI A S B found_sub 64: I/O 8

84 P IBT IBTS IBTS PrdwrN PdatavldN ldirwe D SP FDP3AX Pldio IBTS OBZ2 D SP FDP3AX ldoen IBTS PaddrvldN ldir ldorwe ldo ldarwe datavld Pclkout clk addrvldn rdwrn datavldn D FDS3AX D SP FDP3AX D SP FDP3AX ldar IBTS PmemioN memion memior E 3 ldarr_c2[7:6] data out adr in data in M / IM data out adr in data in B data out adr in data in ETSA data out adr in data in ETS(A) data out adr in data in ETS(B) data out adr in data in ETS(B) data out adr in data in ETS(A) wren 2 E 3 wren wren wren wren wren wren wren ldarr_c2[5:2] Reset_mainN Start_main_e ldirr_c2r_c2[8] ldirr_c2[:8] # #7 # #7 ldirr_c2r_c2[8] ldirr_c2[5] ldirr_c2[3:] ldirr_c2[3:] ldirr_c2[3:28] ldirr_c2[3:28] ldirr_c2[3:6] ldirr_c2[7:] ldirr_c2[5:] ldirr_c2[4] D FDS3AX ldarr_c2 32 ldarr_c2[3:2] MBWrite ETSAWrite ETS_aWrite ETS_bWrite memsel ldor ldi rdwrr D SP FDP3AX Pawe Dec2e Dece Ctrle MBwe ETS_awe ETS_bwe Starte Resete D FDS3AX datvldr datvldrrr_c2 rdwr D FDS3AX datvldrr memiorr_c2 rdwrrr_c2 D FDS3AX D FDS3AX 32 ldirr_c2 D FDS3AX clk_d2 D FDS3AX D FDS3AX unit_enrr_c2 4 clk use3_8 line_three datvldr rdwrr memior sel_unit_en D SP FDP3AX Konishi s Algorithm Circuits 65: 8

コンピュータ概論

コンピュータ概論 4.1 For Check Point 1. For 2. 4.1.1 For (For) For = To Step (Next) 4.1.1 Next 4.1.1 4.1.2 1 i 10 For Next Cells(i,1) Cells(1, 1) Cells(2, 1) Cells(10, 1) 4.1.2 50 1. 2 1 10 3. 0 360 10 sin() 4.1.2 For