Trộn lẫn thành phần Hardware và Software (Phần 2)

Nội dung text: Trộn lẫn thành phần Hardware và Software (Phần 2)

1. http:// www.diachiweb.com Ta thaáy ñoái vôùi aùnh xaï vaø thöù töï thì thôøi gian tính toaùn laø haèng .Do vaäy toång doä phöùc taïp cuûa giaûi thuaät GCLP ôû moåi böôùc laø O(N+A).giaæ thuaät chaïy N laàn vaäy toång thôøi gian laø O(N.(N+A)).kieåu maåu cho öùng duïng DSP thì A»N nhö vaäy ñoä phöùc taïp xaáu nhaát cuûa giaûi thuaät GCLP laø O(N2) 3.Phaân tích ñoä phöùc taïp cuaû giaûi thuaät Bin selection procedure Ñoä phöùc taïp cuûa giaûi thuaät ñöôïc tính toaùn nhö sau: COMPLEXITY(BIN SELECTION) S1.Tính toaùn BFC(Bin Selection Curve):O(B*(N+A)) S1.1.Cho moãi BIN tính toaùn BIN FRACTION:O(N+A) S1.1.1.Löôïng giaù nhöõng node di chuyeån ñeán L bin S1.1.2.Tính toaùn thôøi gian hoaøn thaønh chính xaùc coâng nhaän aùnh xaï naøy vaø löïa choïn bin S2.Tính toaùn ñoä nhaïy bin:O(B) S3.Tính troïng cuaû ñoä nhaïy bin:O(B) S4.Löïa choïn bin Söï tính toaùn BIN FRACTION trong böôùc S1.1 thì töông töï nhö söï tính toaùn trong GC.ÔÛ ñaây ñoä phöùc taïp cuûa giaû thuaät BIN FRACTION cho moät BIN ñaët bieät laø O(N+A).Ñoä phöùc taïp cuûa böôùc S1 ôû ñaây laø O(B*(N+A)) cho B implementation bin.Ñoä phöùc taïp cuûa nhöõng böôùc khaùc thì ñôn giaûn laø thöù töï cuûa soá bin.Vaäy ñoä phöùc taïp cuûa giaûi thuaät ôû ñaây laø:O(B.(N+A)). 4.Phaân tích ñoä phöùc taïp cuûa giaûi thuaät MIBS(Mapping and Bin Seclection) Giaûi thuaät MIBS aùp duïng GCLP löïa choïn bin N laàn cho taát caû nhöõng node treân graph.Ñoä phöùc taïp cuûa nhöõng böôùc nhoû ñöôïc tính toaùn nhö sau: COMPLEXITY(MIBS) S1.Xaùc ñònh aùnh xaï cho taát caû caùc caùc node free baèng caùch chaïy GCLP:O(N2). S2.Xaùc ñònh nhöõng node saún saøng:O(N) S3.Choïn node tagged :O(N). S4.Tính toaùn hieän thöïc BIN cho node tagged söû duïng giaûi thuaät BIN SELECTION :O(B*(N+A)) Ñoä phöùc taïp cuûa moåi böôùc cuaû giaûi thuaät laø:O(N2+B.N).Moãi böôùc laäp laïi N laàn cho N node .Vaäy ñoä phöùc taïp cuûa giaûi thuaät laø:O(N3+B*N2) 5. Giaûi thuaät phaùt sinh DAG ngaãu nhieân : Procedure Generate_random_Graph /* phaùt sinh thoâng soá cho DAG */ Input : kích thöôùc cuûa ñoà thò N Output : Ñoà thò laëp voøng tröïc tieáp , caùc caïnh khoâng song song S1 . a= random_int(N,N2) (soá cung ) S2 . phaùt sinh hoaùn vò ngaãu nhieân 1 N trong daõy “perm” S21 .for(i=0;i<N;i++) {perm[i]=i} S22. For(i=0;i<N;i++){ S221.j=random_int(0,N-1); S222.tmp=perm[i] S223.perm[i]=perm[j]; S224. Perm[j]=tmp; }
2. http:// www.diachiweb.com S3 phaùt sinh caïng A töø (perm[i],perm[j]),i =0)&&(y =0.33)&&(y =0.66)&&(y<1)) i:normal node S42. Thieát laäp khoâng gian vaø thôøi gian cho node i ; S5.phaùt sinh nhöõng raøng buoäc :T,AH,AS S51.T=random_int(sum_th,sum_ts); S52.AH=random_int(ah_low,ah_high); S53.AS=random_int(as_low,as_high); Procedure Generate_extremity_node Input :tsmin ,asmin ,thmin ,ahmin , tsmax ,asmax, thmax, ahmax,cutoff threshold Output : ts, th ,ah, as S1.tính toaùn giaù trò threshold tsth ,asth ,thth ,ahth (ví duï :tsth =tsmin + cutoff* (tsmax –tsmin )) S2 tính toaùn giaù trò extremity max ,min S21. xsmax =tsmax/ahmin S22. xsmin =tsth/ahth S23.xhmax= ahmax/tsmin S24.xhmin =ahth/tsth S25.deltah =xhmax –xhmin S26.deltas =xsmax –xsmin S3 xaùc ñònh neáu node laø hardware extremity hay software extremity S31.z=ran1(); S32.if(z,0.5) hardware_extremity ;else software_extremity ; S4.phaùt sinh ño löôøng extremity trong khoaûng (0,0.5); S5.if hardware extremity S51.ah=random_int(ahth,ahmax); S52.ts=ah/((2*deltah *ex) +xhmin); S53.as=random_int(asmin,asth); S54.th=random_int(thmin,thth); S6.if software extremity : S61.ts=random_int(tsth,tsmax); S62.ah=ts/((2*deltas *ex) +xsmin); S63.as=random_int(asmin,asth); S64.th=random_int(thmin,thth); Procedure Generate_repeller_node Output: ts,th, as,ah;
3. http:// www.diachiweb.com S1.phaùt sinh daõy giaù trò TS,TH S2.xaùc ñònh neáu node laø software repeller hay hardware repeller S21.z=ran1(); S22if(z<0.5) hardware repeller ;else software repeller ; S3.phaùt sinh ño löôøng repeller trong khoaûng (0,0.5)(r=ran(0,0.5)) S4.if software repeller : S41.ts=TS[random_int(0,5)]; S42.as=ts/2; S43.ah=(1-r)*as; S44.th=(1+ran1())*ah; S5. If hardware repeller : S51.th=TH[random_int(0,5)]; S52.ah=ah/2; S53.as=(1-r)*ah; S54.ts=(1+ran1())*th; Procedure Generate_normal_node Output ts,th , ah , as S1.ts= random_int(tsmin, tsth) S2.as= ts/2 S3.th=ts/random_int(1,4) S4.ah=th/2; 2.1 Moät soá thoâng soá ban ñaàu : • Moät DAG goàm : N : taäp node A :taäp cung • D :thôøi gian giôùi haïn khi thöïc thi • AS :Dung löôïng boä nhôù,kích thöôùc software khoâng ñöôïc vöôït quaù AS • AH :Khoâng gian cho pheùp cuûa hardware ,toång khoâng gian cuûa caùc node hardware khoâng vöôït quaù AH . • ahcomm :Khoâng gian hardware yeâu caàu truyeàn nhaän döõ lieäu . • ascomm :Khoâng gian software yeâu caàu ñeå truyeàn nhaän döõ lieäu . • tcomm :Soá chu kyø yeâu caàu cho truyeàn döõ lieäu . Trôû veà trang chuû 2.2 Phaân chia nhò phaân (binary partitioning) : Vaán ñeà phaân chia nhò phaân (P1) :Cho tröôùc moät DAG ,löôïng giaù khoâng gian ,thôøi gian caùc node aùnh xaï sang hardware ,software ,giaù thoâng tin truyeàn nhaän ,thôøi gian giôùi haïn thöïc thi D. Mi laø aùnh xaï node i sang hardware hay software ,tI laø thôøi gian baét ñaàu cuûa moät node ,keát |N| quaû cho ñöôïc toång khoâng gian hardware laø nhoû nhaát. Soá traïng thaùi lôùn nhaát laø O(2 ) Vaán ñeà aùnh xaï sang hardware ,software vaø saép xeáp thöù töï coù theå thaønh coâng thöùc nhö moät chöông trình tuyeán tính (ILP :integer linear program) vaø ñöôïc giaûi quyeàt moät caùch chính xaùc ,nhöng nhöõng coâng thöùc naày khoù ñuùng cho nhöõng öùng duïng coù kích thöôùc vöøa phaûi .Moät soá heuristic cho pheùp giaæ quyeát nhöõng khaùc nhau cuaû vaán ñeà naày • Giaûi thuaät phaân chia nhò phaân :GCLP Algorithm
4. http:// www.diachiweb.com 2.2.1 Cô sôû giaûi thuaät : Cô sôû thöù töï khung coâng vieäc trong giaûi thuaät GCLP döïa vaøo thöù töï duyeät qua moät löôït caùc node töø node nguoàn ,vôùi moãi node choïn aùnh xaï maø noù laøm nhoû nhaát muïc tieâu . P1 coù caùc muïc tieâu :thôøi gian hoaøn thaønh cuûa node laø nhoû nhaát (toång thôøi gian baét ñaàu vaø thôøi gian thöïc thi ) hay laø khoâng gian nhoû nhaát cuûa moãi node (khoâng gian hardware hay kích thöôùc cuûa software ).Vaán ñeà ñaït ñöôïc caùc muïc tieâu naày coù tính töông ñoái . Giaûi thuaät GCLP noù löïa choïn vaø chuyeån ñoåi muïc tieâu ôû moåi böôùc ñeå xaùc ñònh aùnh xaï vaø trình töï Obj1 y Min(finish time) GC >? n Glocal (time) Obj2 Min(% resource consumed ) Criticality threshole measure + 0.5 D Local phase delta 1.GC (Global criticality) :laø söï ño löôøng tröôùc maø noù löôïng giaù thôøi gian giôùi haïn ôû moãi böôùc cuûa giaûi thuaät .GC sosaùnh vôùi ngöôõng ñeå xaùc ñònh neáu thôøi gian laø tôùi haïn .Neáu thôøi gian laø tôùi haïn , muïc tieâu nhieäm vuï laø thôøi gian hoaøn thaønh nhoû nhaát ñöôïc choïn ,neáu khoâng thì khoâng gian nhoû nhaát ñöôïc choïn .GC coù theå thay ñoåi ôû moãi böôùc cuûa giaûi thuaät . 2.Pha cuïc boä (local phase):LP laø moät söï phaân loaïi cuûa nhöõng node treân cô sôû tính ñoàng nhaát vaø thuoäc tính beân trong cuûa chuùng .Moãi node ñöôïc phaân loaïi nhö extremity (pha 1),hay repeller (pha 2), hay normal (pha 3).Moät söï ño löôøng goïi laø delta pha cuïc boä xaùc ñònh soá löôïng aùnh xaï cuïc boä thích hôïp cuûa node ñeå yù ñeán söï thay ñoåi ngöôõng ñöôïc duøng trong so saùnh GC .Löu ñoà giaûi thuaät nhö sau :
5. http:// www.diachiweb.com NU =N , NM =Þ Compute GC Se l ect node among i Identify local phase Select objective ready nodes And compute delta Select mapping Mi find Start time Ti NM {I}, NU =NU\ {I} Update (Tremaining ) |N| times no NU =Þ?
6. http:// www.diachiweb.com {Mi,ti} (hình 3) Giaûi thuaät GCLP N laø taäp nodes cuûa DAG . NU laø taäp nodes chöa ñöôïc aùnh xaï ñöôïc tính laïi taïi moãi voøng laëp . NM laø taäp nodes ñöôïc aùnh xaï . NU ban ñaàu ñöôïc gaùn laø N. NM ban ñaàu ñöôïc gaùn laø roång . Moãi voøng laëp seõ aùnh xaï moät node ,böôùc ñaàu tieân cuûa moãi voøng laëp thôøi gian giôùi haïn chung GC ñöôïc tính toaùn laïi treân cô sôû yeâu caàu giôùi haïn cuûa nhöõng node ñaõ ñöôïc aùnh xaï vaø chöa ñöôïc aùnh xaï .Quaù trình ñöôïc laëp N laàn cho ñeán khi khoâng coøn node naøo chöa ñöôïc aùnh xaï . 2.2.2 :Giôùi haïn chung GC : GC laø söï ño löôøng tröôùc maø noù löôïng giaù thôøi gian giôùi haïn ôû moãi böôùc cuûa giaûi thuaät . Ñeå hieåu vaán ñeà naày ta xeùt ví duï sau : D H u 2 4 (a1) 1 u 5 s 3 s NM :nhöõng nodes ñöôïc aùnh xaï {1,2,3}. NU :nhöõng nodes chöa ñöôïc aùnh xaï {4,5} S:software ,h:hardware .D thôøi gian giôùi haïn chung . (a2) 2 Hardware 1 3 times
7. http:// www.diachiweb.com Software T rem D • T rem :thôøi gian coøn laïi (remaining time) N SàH b) Hardware 2 1 3 4 5 times Software T rem D Ts • Ts thôøi gian chaïy cuûa node ñöôïc aùnh xaï sang software N S->H laø taäp cuûa nhöõng node ñöôïc aùnh xaï chuyeån töø software sang hardware do vöôït quaù thôøi gian giôùi haïn D . (c) Hardware 2 1 3 4 5 times Software Th T rem D Hình 4 • T h :thôøi gian hoaøn thaønh neáu node chuyeån töø software sang hardware vaø ñöôïc aùnh xaï sang hardware ∑ sizeI i∈Ns->H GC= 0<= GC <=1 ∑ sizeI i∈Nu ÔÛ moãi böôùc caùc node ñang chuaån bò ñöôïc aùnh xaï sang hardware hay software .Söû duïng trình töï naày vaøø thôøi gian giôùi haïn D ,ñeå ñaàu tieân xaùc ñònh Trem.Böôùc tieáp theo taát caû caùc node chöa
8. http:// www.diachiweb.com ñöôïc aùnh xaï (node 4 vaø node 5 trong ví duï ) seõ ñöôïc aùnh xaï sang software ,luùc naày thôøi gian Ts seõ ñöôïc tính toaùn .Giaû söû raèng Ts vöôït qua giôùi haïn D.Moät soá node trong taäp node chöa ñöôïc aùnh xaï phaûi di chuyeån töø software sang hardware ñeå thoûa maõn nhoû hôn giôùi haïn D .Nhöõng node naày taïo thaønh taäp N S->H (trong ví duï taäp naày laø {5} ).Luùc naày thôøi gian hoaøn thaønh Th ñöôïc tính toaùn laïi .Trong giaûi thuaät GC taïi moät böôùc naøo ñoù coù theå coù nhieàu node chöa ñöôïc aùnh xaï vaø caàn phaûi aùnh xaï sang hardware vì vaäy phaûi tìm keát quaû khaû thi ,(thôøi gian nhö laø taøi nguyeân ñang bò tranh chaáp ). Giaûi thuaät tính toaùn GC : Procedure Compute_GC ; Input :NM,NU,D ,tsi,thi.sizeI ,vôùi moïi I thuoäc N; Output GC S1 :tìm taäp N S->H cuûa nhöõng node chöa ñöôïc aùnh xaï maø coù theå chuyeån tö software sang hardware ñeå thoûa maõn giôùi haïn D; S11 Löaï choïn nhöõng node trong NU ,duøng öu tieân Pf di chuyeån töø software sang hardware . S12 Tính toaùn thôøi gian Thieát keá treân cô sôû node trong taäp N S->H ñöôïc aùnh xaï sang hardware S13 Neáu Th > D quay laïi S11 å sizeI iÎNs->H S2 GC= 0 h ñeán hardware ñeå thoûa maõn T .thôøi gian hoaøn thaønh laø O(|A| + |N|) GC ñöôïc tính toaùn trong S2 laø tæ soá cuûa toång kích thöôùc cuûa nhöõng node trong taäp Ns->H vaø toång kích thöôùc trong taäp Nu .kích thöôùc cuûa node ñöôïc xem nhö soá caùc pheùp toaùn nguyeân toá (coäng ,nhaân, ) trong node .Moãi node ñöôïc ñaïi dieän bôûi kích thöôùc cuûa noù töø nhöõng node coù theå khoâng ñoàng nhaát trong toång theå . GC ño löôøng thôøi gian giôùi haïn chung .GC coù theå giaûi thích baèng moät caùch khaùc : noù ño löôøng khaû naêng (noùi ñôn giaûn) laø baát cöù node khoâng aùnh xaï thì aùnh xaï sang hardware .khaû naêng naày coù theå thay ñoåi ôû moãi böôùc cuûa giaûi thuaät . 2.2.3 Pha cuïc boä (Local phase) : GC laø moät ño löôøng trung bình treân taát caû nhöõng node chöa aùnh xaï ôû moãi böôùc .Ñieàu naày laøm giaûm tính chính xaùc ñeán thuoäc tính cuïc boä cuûa node ñang ñöôïc aùnh xaï .Ñeå nhaán maïnh ñaëc
9. http:// www.diachiweb.com tröng cuïc boä cuûa nhöõng node , ngöôøi ta chia laøm 3 loaïi : extremities (goïi laø local phase 1) , repellers (goïi laø local phase 2) , normal (goïi laø local phase 3). 2.2.3.1 Local phase 1 (extremity nodes ) Nhöõng node söû duïng nhieàu taøi nguyeân khoâng caân ñoái khi aùnh xaï so vôùi aùnh xaï khaùc ñöôïc goïi laø extremities .Chaúng haïn nhö moät hardware extremity yeâu caàu khoâng gian roäng lôùn khi aùnh xaï sang hardware nhöng coù theå hieän thöïc baèng software vôùi giaù khoâng ñaét .Vieäc aùnh xaï thích hôïp cuûa nhöõng node nhö vaäy ñöôïc xaùc ñònh bôûi extremity measure , laøm thay ñoåi ngöôûng duøng trong sosaùnh GC . Moät hardware extremity node laø node söû duïng khoâng gian lôùn trong hardware , nhöng thôøi gian trong software töông ñoái nhoû . Moät software extremity node laø node söû duïng nhieàu thôøi gian trong software nhöng söû duïng khoâng gian nhoû khi aùnh xaï sang hardware . Vieäc di chuyeån hardware extremity node sang software extremity node hay ngöôïc laïi laø roõ raøng caàn thieát . Söï cheânh leäch trong söû duïng taøi nguyeân cuûa extremity node I ñöôïc xaùc ñònh bôûi extremity measure EI .extremity measure ñöôïc söû duïng ñeå thay ñoåi ngöôõng ñöa vaøo so saùnh vôùi GC khi löïa choïn muïc tieâu aùnh xaï .EI laø local phase delta trong hình phaàn tröôùc . EXTREMITY MEASURE : Procedure Compute_Extremity_measure Input tsI ,ahI ,"iÎ N ,tæ leä a,b, Output EI , ,"iÎ N ,-0.5 =ts(a) and ahI = ah(b) and tsI <ts(a) ,iÎEXh S4 xaùc ñònh giaù trò extremity xI cho node I : If iÎ EXs then Tsi/tsmax ,xI = ahi/ahmax else ahi/ahmax xI= Tsi/tsmax Trong ñoù :tsmax =maxi{tsi} vaø ahmax =maxi{ahi} S5 thöù töï nhöõng node trong EXs(EHh) cho bôûi x .Trong ñoù giaù tri extremity lôùn nhaát vaø giaù trò extremity nhoû nhaát laø xsmax (xhmax) vaø xsmin (xhmin) S6 tính toaùn extremity measure EI cho node I :
10. http:// www.diachiweb.com If iÎ EXs then xI-xsmin EI= -0.5 * ,-0.5 ts(a)) vaø döôùi tæ leä b trong bieåu ñoà ah (ahI ah(b)) vaø döôùi tæ leä a trong bieåu ñoà ts (tsI <ts (a)). hình 5 sau trình baøy caùc loaïi bieåu ñoà vaø nhaän ra caùc extremities .Ví duï ta xem xeùt giaù trò a vaø b naèm trong khoaûng (0.5 ,0.75) ñöôïc söû duïng . Soá node treân ts a Caän treân a ts(a ) ts EXh EXs Soá node treân ah b Caän treân b ah(b) ah