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

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

1. http:// www.diachiweb.com Hình 5 Taäp Hardware (EXh) extremity vaø taäp software (EXs) extremity Söï thay ñoåi ngöôõng khi söû duïng ño löôøng extremity Gck bieåu thò giaù trò cuûa GC ôû böôùc thöù k khi moät extremity node I ñöôïc aùnh xaï .Neáu khoâng tính ñeán EI thì ngöôõng ñöôïc khôûi ñoäng giaù trò 0.5 vaø giaù trò naày bao truøm cho taát caû nhöõng node chöa ñöôïc aùnh xaï ,vieäc aùnh xaï cuûa node I trong tröøông hôïp naày chæ môùi laø cô sôû treân GCk .Moät soá chæ daãn sau : 1.aùnh xaï xaáu (poor mapping): Giaû söûï node i laø moät hardware extremity .Neáu GCk>=0.5 ,ñoái töôïng 1 (Obj1) ñöôïc choïn thôøi gian laø toái thieåu vaø i coù theå aùnh xaï sang hardware treân cô sôû giôùi haïn thôøi gian .Tuy nhieân i laø moät hardware extremity vaø aùnh xaï noù sang hardware hieån nhieân laø söï löïa choïn xaáu . 2.aùnh xaï khoâng theå thöïc hieän (infeasible mapping) :Giaû söûï node i laø moät software extremity .Neáu GCk < 0.5, ñoái töôïng 2 ñöôïc choïn (Obj2) khoâng gian laø toái thieåu vaø i coù theå ñöôïc aùnh xaï ñeán software .Node i laø moät software extremity ,vì vaäy aùnh xaï noù sang software coù theå vöôït quaù giôùi haïn cho pheùp . Bao truøm leân nhöõng vaán ñeà naày ,ño löôøng extremity Ei ñöôïc söû duïng ñeå thay ñoåi ngöôõng maët ñònh treân aùnh xaï thích hôïp . Ngöôõng môùi laø 0.5 + Ei .GCk ñöôïc so saùnh vôùi ngöôõng thay ñoåi naày . Trong tröôøng hôïp software extremities thì –0.5 <= Ei <=0 ; vì vaäy 0<=ngöôõng (threshold)<=0.5. Trong tröôøng hôïp hardware extremities thì 0<=Ei<=0.5, vì vaäy 0.5<=ngöôõng (threshold)<=1. 2.2.3.2 Local phase 2 or Repeller nodes : GCLP söû duïng khaùi nieäm repeller hay local phase 2 node ñeå thöïc hieän vieäc hoaùn ñoåi giöõa hardware vaø software cuûa nhöõng node töông töï .Ñeå laøm ñieàu naày phaûi ñoàng nhaát nhöõng thuoäc tính beân trong naøo ñoù cuûa node (ñöôïc goïi laø thuoäc tính repeller) noù phaûn aûnh söï thích hôïp coù saün cuûa node ñeå aùnh xaï sang hardware cuõng nhö software .Ví duï pheùp toaùn bit (bit operation) ñöôïc ñieàu khieån toát hôn trong hardware ,trong khi ñoù nhöõng pheùp toaùn veà memory (memory operation) thì phuø hôïp hôn cho software .Nhö vaäy moät node vôùi nhieàu bit ñieàu khieån baèng tay (bit manipulation) lieân heä ñeán nhöõng node khaùc laø software repeller , trong khi moät node vôùi nhieàu pheùp toaùn boä nhôù quan heä ñeán nhöõng node khaùc laø hardware repeller .Vieäc di chuyeån moät node vôùi nhieàu pheùp toaùn bit ñieàu khieån baèng tay ra khoûi software goïi laø repeller force .Töø ñoù tæ leä cuûa pheùp toaùn bit ñieàu khieån baèng tay trong moät node goïi laø thuoäc tính software repeller (software repeller property). Töông töï tæ leä cuûa pheùp toaùn boä nhôù trong moät node goïi laø thuoäc tính hardware repeller (hardware repeller property) .Moät thuoäc tính repeller ñöôïc xaùc ñònh baèng moät giaù trò repeller . Keát quaû keát hôïp cuûa taát caû thuoäc tính repeller trong moät node ñöôïc bieåu thò nhö laø söï ño löôøng repeller cuûa node .Taát caû nhöõng node ñöôïc xeáp haøng tuøy theo söï ño löôøng giaù trò repeller cuûa chuùng .Chaúng haïn nhö cho 2 node N1 vaø N2 vôùi ñaëc ñieåm software töông töï
2. http:// www.diachiweb.com ,neáu N1 coù giaù trò software repeller lôùn hôn N2 vaø 1 trong 2 ñöôïc löïa choïn aùnh xaï sang hardware thì öu tieân N1 . Moät vaøi thuoäc tính repeller coù theå ñöôïc nhaän daïng cho moãi node .Hoån hôïp leänh ôû möùc bit vaø möùc ñoä chính xaùc laø nhöõng ví duï cho thuoäc tính software repeller ,trong khi nhöõng hoån hôïp leänh taäp trung boä nhôù vaø hoån hôïp leänh tìm kieám trong baûng coù theå laø thuoäc tính hardware repeller .Moãi thuoäc tính ñöôïc xaùc ñònh bôûi giaù trò thuoäc tính . Keát quaû keát hôïp cuûa taát caû thuoäc tính repeller trong moät node ñöôïc bieåu thò nhö laø söï ño löôøng repeller cuûa node . Chuùng ta quan taâm ñeán hoãn hôïp leänh caáp ñoä bit (bit level instruction mix) laø moät thuoäc tính software repeller , thuoäc tính naày ñöôïc xaùc ñònh thoâng qua giaù trò thuoäc tính cuûa noù goïi laø BLIM.BLIMi ñöôïc ñònh nghóa laø tæ leä cuûa nhöõng leänh caáp ñoä bit treân toång caùc leänh trong moät node i (0 BLIM2 , neáu as1@ as2 thì ah1 <ah2 (bôûi vì pheùp toaùn bit laøm cho khoâng gian hardware nhoû hôn ). Thaät vaäy N1 laø software repeller so vôùi N2 treân cô sôû thuoäc tính hoãn hôïp leänh caáp bit . Khi löïa choïn aùnh xaï N1 hoaëc N2 sang hardware thì choïn N1 thích hôïp hôn (döïa vaøo thuoäc tính BLIM). Nhöõng thuoäc tính repeller khaùc ñöôïc ñeà caäp tröôùc ñaây thì xaùc ñònh töông töï döïa vaøo giaù trò thuoäc tính cuûa chuùng .Keát quaû tích luõy caùc thuoäc tính repeller cho moät node ñöôïc quan taâm khi aùnh xaï node ñoù . Söï ño löôøng repeller (repeller measure) Ri cuûa moät node laø keát quaû goäp laïi caùc giaù trò repeller cuûa node ñoù .Ño löôøng repeller ñöôïc söû duïng ñeå thay ñoåi laïi ngöôõng maø GC ñaõ so saùnh khi löïa choïn muïc tieâu aùnh xaï . REPELLER MEASURE : Procedure compute_repeller _measure Input vi,p = giaù trò cuûa thuoäc tính repeller p cuûa node i, iÎ N,pÎ P . Output ño löôøng repeller Ri ,"i Î N,0.5 <= Ri<=0.5. S1. tính toaùn cho moãi thuoäc tính p : 2 s (vi,p) = söï khaùc nhau cuûa vi,p cuûa taát caû node i . min (vi,p)= min cuûa vi,p cuûa taát caû node i .
3. http:// www.diachiweb.com max(vi,p) =max cuûa vi,p cuûa taát caû node i . ñeå RX = RH neáu pÎ RH hay RX = RS neáu p Î RS. 2 s (vi,p) 2 ap = = troïng cuûa thuoäc tính repeller p, å s (ap) =1 . 2 å s (vi,p) pÎRX pÎRX S2 . tính toaùn giaù trò thuoäc tính bình thöôønh nvi,p cho moãi thuoäc tính p cuûa node i vi,p -min(vi,p) nvi,p= .0<=nvi,p<=1. max(vi,p)-min(vi,p) S3.tính toaùn ño löôøng repeller Ri cho moãi node i Ri = 0.5(å ap.nvi,p - å ap.nvi,p ), -0.5 <=Ri<=0.5. pÎ RH p ÎRS Giaûi thuaät moâ taû tính toaùn ño löôøng repeller cho moãi node i (Ri) .Ñaët RH taäp thuoäc tính repeller hardware vaø RS laø taäp thuoäc tính repeller software ,P laø hoäi cuûa 2 thuoäc tính treân Giaù trò vi.p cuûa moãi thuoäc tính repeller p cuûa node i thu ñöôïc nhôø söï phaân tích node .Chaúng haïn nhö xem xeùt thuoäc tính troän leänh möùc bit (bit level instruction mix) .Caùc pheùp toaùn caáp bit nhö laø (or ,and ,exor) ñaàu tieân ñöôïc nhaän ra trong node .Giaù trò BLIM cuûa node i laø tæ leä cuûa soá pheùp toaùn ôû möùc bit treân toång soá pheùp toaùn trong node .Giaù trò thuoäc tính repeller khaùc ñöôïc tính toaùn töông töï . Trong S1 cuûa giaûi thuaät ,moãi giaù trò thuoäc tính repeller veà söï khaùc nhau ,giaù trò nhoû nhaát vaø giaù trò lôùn nhaát ñöôïc tính toaùn . Nhöõng giaù trò thuoäc tính ñöôïc bình thöôøng hoùa trong S2 . Trong S3 ño löôøng repeller cho moãi node ñöôïc tính toaùn nhö laø moät toå hôïp cuûa caùc giaù trò thuoäc tính bình thöôøng hoùa repeller .Troïng ap cuûa thuoäc tính p laø tæ leä töông öùng vôùi giaù trò khaùc nhau cuûa giaù trò node ñoù . Thay ñoåi ngöôõng khi söû duïng ño löôøng repeller : Nhö ñaõ trình baøy trong phaàn tröôùc repeller thieát laäp hoaùn ñoåi ñeå thu giaûm taát caû khoâng gian hardware .Coù theå noùi raèng ño löôøng repeller laø ño löôøng cuûa söï hoaùn ñoåi laïi cuûa 2 node cuûa phase 2 töông töï giöõa aùnh xaï hardware vaø software .Nhö ñaõ noùi cho moät löïa choïn aùnh xaï cuûa 2 node sang hardware ,thì node coù ño löôøng repeller software cao hôn seõ ñöôïc choïn . Cho moät phase 2 node i vôùi ño löôøng repeller software thích ñaùng , giaûi thuaät seõ coá gaéng hoaøn thaønh vieäc ñaåy node i ra khoûi software .Noù thay ñoåi ngöôõng maø muïc tieâu ñöôïc löïa choïn seõ thuaän lôïi hôn ñeå hoaøn thaønh vieäc aùnh xaï. Vieäc hoaùn ñoåi naày giaûi phoùng taøi nguyeân hieän thôøi cho node chöa ñöôïc saép thöù töï vôùi ño löôøng thuoäc tính repeller thaáp , nhôø vaäy cho pheùp thu giaûm toaøn boä khoâng gian hardware . D; repeller Ri ñöôïc söû duïng ñeå thay ñoåi ngöôõng ,ngöôõng môùi laø 0.5+Ri .Vôùi software repellers thì –0.5 <=Ri <=0 ,vì vaäy ngöôõng laø 0<=ngöôõng (threshold)<= 0 , vôùi hardware repellers thì 0<=Ri <=0.5 vì vaäy ngöôõng laø 0.5<=ngöôõng <=1. 2.2.3.3 Local phase 3 hay normal nodes : Moät node khoâng laø extremity node hay repeller node thì laø node bình thöôøng (normal node ) ñöôïc goïi laø lacal phase 3 .Ngöôõng ñöôïc thieát laäp maëc ñònh laø 0.5 khi aùnh xaï .Nhö vaäy muïc tieâu aùnh xaï ñöôïc quaûn lyù bôûi GC . Toùm laïi node ñöôïc phaân thaønh 3 loaïi :extremity node ,repeller node ,vaø normal node .Moãi phase thích hôïp cuûa moãi node ñöôïc xaùc ñònh bôûi söï ño löôøng cuûa noù , goïi chung laø local
4. http:// www.diachiweb.com phase delta (D) .Trong tröôøng hôïp node laø extremity node thì D=Ei ,trong tröôøng hôïp node laø repeller node thì D =Ri ,vaø tröôøng hôïp normal node thì D = 0 .Local phase delta ñöôïc duøng ñeå tính toaùn thay ñoåi ngöôõng : Ngöôõng =0.5+D . 2.2.4 .GIAÛI THUAÄT GCLP Algorithm : GCLP Input ahi ,asi , thi , tsi , Ei (extremity measure) ,vaø Ri (repeller measure) " i Î N Giaù truyeàn nhaän :ahcomm ,ascomm vaø tcomm vaø giôùi haïn AH , AS, vaø D. Output :aùnh xaï Mi (Mi Î { hardware,software } ,thôøi gian baét ñaàu ti ," i Î N Khôûi taïo :Nu ={ nodes chöa aùnh xaï } =N ,NM ={ nodes ñaõ aùnh xaï } =f Procedure While { |Nu|> 0 } { S1 Tính toaùn GC S2 Xaùc ñònh taäp node saün saøng NR S3 Tính toaùn thôøi gian thöïc thi keát quaû texec(i) cho moãi node i If i Î Nu texec(i) =GC .thi + ( 1-GC).tsi Else if i Î NM texec(i) = thi .I(Mi==hardware ) +tsi.I(Mi==software ) S4 Tính toaùn ñöôøng daøi nhaát longestpath(i),"i Î NR söû duïng texec(i) S5 Löïa choïn node i ,i Î NR baèng aùnh xaï :max(longestpath(i)) S6 Xaùc ñònh aùnh xaï Mi cho i : S61 if (Ei 0) D=n .Ri (local phase 2) n laø repeller measure weight 0 =ngöôõng m:minimize(obj1) else m:minimize(obj2) s64 Mi =m ; set(ti) ; Nu =Nu\{i} ; NMß {i} update (Tremaining ,AHremaining ,ASremaining); } Giaûi thuaät aùnh xaï moãi node ôû moät böôùc .Böôùc S1 Gc ñöôïc tính toaùn vaø .ÔÛ böôùc S2 xaùc ñònh taäp node saün saøng nghóa laø taäp nhöõng node chöa ñöôïc aùnh xaï maø tieàn boái cuûa noù ñaõ ñöôïc aùnh xaï ,moät trong nhöõng node saün saøng naày seõ ñöôïc choïn ñeå aùnh xaï trong böôùc 5 .Ñaëc bieät neân choïn node treân ñöôøng daøi nhaát cuûa graph ,ñöôøng tôùi haïn chung bao goàm nhöõng node chöa aùnh xaï tính toaùn noù .ÔÛ böôùc S3 tính toaùn thôøi gian thöïc thi ñeán keát quaû cuûa node i .ÔÛ böôùc 4 tính toaùn con ñöôøng daøi nhaát söû duïng thôøi gian thöïc thi ñeán keát quaû cuûa node i .ÔÛ böôùc 5 löïa choïn node i cho aùnh xaï .ÔÛ böôùc 6 xaùc ñònh aùnh xaï Mi cho moãi node i ,neáu node laø extremity node (hay repeller node ) thì duøng ñeå thay ñoåi ngöôõng .Söï goùp phaàn cuûa ño löôøng extremity vaø repeller coù theå thay ñoåi bôûi troïng g vaø v .Muïc tieâu aùnh xaï ñöôïc löïa choïn nhôø vaøo vieäc so saùnh laïi GC vôùi ngöôõng .Neáu thôøi gian laø tôùi haïn thì muïc tieâu thôøi gian hoaøn thaønh nhoû nhaát seõ ñöôïc choïn , khaùc ñi thì tieâu thuï taøi nguyeân nhoû nhaát ñöôïc choïn . Obj1 :tfin(i,m) ,trong ñoù mÎ {hardware ,software } Tfin(i,m) =max(maxp(i)(tfin(p) +tc(p,i)),tflast(m))+t(i,m) Trong ñoù :
5. http:// www.diachiweb.com P(i) : taäp tieàn boái cuûa node i ,p Î P(i) tfin(p) :thôøi gian hoaøn thaønh cuûa tieàn boái p tc(p,i) =thôøi gian truyeàn nhaän giöõa node tieàn boái p vaø node i tflast = thôøi gian hoaøn thaønh cuûa node cuoái ñöôïc gaùn bôûi aùnh xaï m =0 neáu m laø hardware . t(i,m) = thôøi gian thöïc thi cuûa node i treân aùnh xaï m tot tot (asi+ascomm ) (ahi+ahcomm ) Obj2 : .I(m=software ) + .I(m=hardware ) AS AHremaining Obj1 löïa choïn aùnh xaï maø thôøi gian hoaøn thaønh nhoû nhaát cuûa node .Moät node chæ baét ñaàu thöïc thi sau khi taát caû caùc tieàn boái cuûa noù hoaøn thaønh vieäc thöïc thi vaø döõ lieäu ñaõ ñöôïc truyeàn ñeán noù töø caùc tieàn boái cuõng vaäy moät node khoâng theå baét ñaàu thöïc thi treân moät taøi nguyeân software cho ñeán khi node cuoái cuøng ñöôïc aùnh xaï sang software hoaøn thaønh vieäc thöïc thi . Obj2 söû duïng ño löôøng soá phaàn traêm tieâu thuï (percentage resource consumption) .Vieäc ño löôøng naày laø phaàn nhoû cuûa khoâng gian taøi nguyeân cuûa moät node (vuøng khoâng gian truyeàn tot tot nhaän ) treân toång khoâng gian taøi nguyeân .khoâng gian ahcomm (ascomm ) ñöa vaøo tính toaùn giaù toång coäng cuûa söï truyeàn nhaän (keát noái trong hardware vaø code trong software ) giöõa node i trong hardware (software ) vaø taát caû tieàn boái cuûa noù .Taøi nguyeân hardware laø khoâng gian taøi nguyeân yeâu caàu bôûi node ñöôïc chia xeõ bôûi khoâng gian hardware coøn laïi (AHremaining). 2.2.5 Toùm taét giaûi thuaät GCLP : Cho ñeán ñaây chuùng ta ñaõ baøn luaän giaûi thuaät GCLP (global criticality /local phase ) ñeå giaûi quyeát vaán ñeà phaân chia nhò phaân (P1) ñieåm chính yeáu cuûa giaûi thuaät ñöôïc toùm taét nhö sau : Giôùi haïn chung laø moät ño löôøng nhìn tröôùc chung maø ñeå xaùc ñònh thôøi gian giôùi haïn ôû moät böôùc cuûa giaûi thuaät ñöa vaøo tính toaùn nhöõng node chöa aùnh xaï hieän thôøi .GC so saùnh vôùi ngöôõng ñeå löïa choïn muïc tieâu aùnh xaï ôû moãi böôùc cuûa giaûi thuaät .Nhöõng node söû duïng soá löôïng taøi nguyeân khoâng caân ñoái trong khi aùnh xaï sang hardware hay software thì ñöôïc phaân loaïi thaønh extremities .Ngöôõng söû duïng ñeå aùnh xaï nhöõng node naày ñöôïc thay ñoåi ñeå tính toaùn cho nhöõng aùnh xaï thích hôïp .Toång khoâng gian hardware ñöôïc thu giaûm toát hôn bôûi vieäc söû duïng khaùi nieäm hoaùn ñoåi nhöõng node repeller (on line swaps between repeller node ). Repeller node ñöôïc phaân loaïi vaø xaùc ñònh treân cô sôû nhöõng thuoäc tính beân trong cuûa node .Ngöôõng ñöôïc söû duïng cho aùnh xaï nhöõng node repeller ñöôïc thay ñoåi cho phuø hôïp vôùi quan heä aùnh xaï cuûa noù .Giaûi thuaät coù ñoä phöùc taïp (O(|N|2)) vôùi keát quaû so saùnh laø toái öu . Trôû veà trang chu 2.3 Phaân chia môû roäng (Extended partition ) 2.3.1 Giôùùi thieäu : Lyù do cho vieäc giaûi quyeát vaán ñeà phaân chia môû roäng laø do tính meàm deõo cuûa vieäc choïn löïa moät höôùng hieän thöïc cho node thay vì phaûi coá ñònh caùch hieän thöïc , nhôø vaäy maø noù coù theå thu giaûm ñöôïc khoâng gian hardware hay thôøi gian thöïc thi software . Töø thöïc tieån trong vieäc toång hôïp ngöôøi ta thaáy raèng keát quaû cuûa hieän thöïc heä thoáng toát hôn khi coù phaân chia môû roäng . 2.3.2 Giaûi thuaät phaân chia môû roäng :Muïc tieâu thieát keá . Giaûi thuaät GCLP giaûi quyeát vaán ñeà phaân chia nhò phaân P1 .Vaán ñeà phaân chia môû roäng P2 ñeà caäp ñeán toái öu hoaù vieäc aùnh xaï nhö ‘implementation bin ‘(taïm dòch laø ‘hieän thöïc bin’) cho moãi node .Quan taâm hieän thöïc bin ñöôïc trình baøy theo hình veõ 7
6. http:// www.diachiweb.com area j ahi j L bin thi H bin time Hình7 NH taäp cuûa hardware trong hieän thöïc bin i j j CHi ={ (ahi /thi ) jÎ NHi } Bieåu thò L laø nhanh nhaát (beân traùi nhaát cuûa hieän thöïc bin ) vaø H laø chaäm nhaát (beân phaûi nhaát cuûa hieän thöïc bin) .Nhö vaäy ñöôøng cong hieän thöïc bin ñi qua töø L ñeán H ,khoâng gian hardware yeâu caàu hieän thöïc node ñöôïc laøm giaûm .Töø quan ñieåm toái thieåu khoâng gian hardware moãi node ñöôïc aùnh xaï sang hardware coù theå ôû taäp H bin (khoâng gian nhoû nhaát).Tuy nhieân khoâng theå töø taäp H ñaùp öùng hieän thöïc chaäm nhaát .Vaán ñeà phaân chia môû roäng ñöôïc löïa choïn moät söï thích hôïp hieän thöïc bin vaø pheùp aùnh xaï cho moãi node nhö toång khoâng gian hardware nhoû nhaát coù tính ñeán giôùi haïn veà thôøi gian vaø taøi nguyeân .Vaán ñeà naày roõ raøng phöùc taïp hôn aùnh xaï phaân chia nhò phaân .Ñích cuûa chuùng ta laø thieát keá moät giaûi thuaät hieäu quaû giaûi quyeát vaán ñeà phaân chia môû roäng .Coù 2 muïc tieâu ñi ñeán vieäc thieát keá 1.Muïc tieâu thieát keá 1 :Hôïp lyù hoaù tæ leä phöùc taïp . Vaán ñeà phaân chia nhò phaân coù 2|N| khaû naêng aùnh xaï ,N laø soá node trong ñoà thò .Vôùi B hieän thöïc bin beân trong 1 aùnh xaï ,vaán ñeà phaân chia môû roäng coù (2B)|N| khaû naêng trong tröôøng hôïp toài nhaát .Ñoä phöùc taïp cuûa giaûi thuaät khoâng tæ leä vôùi kích thöôùc (soá löïa choïn thieát keá treân moät node )cuûa quaù trình phaân chia .Neáu giaûi thuaät phaân chia nhò phaân coù ñoä phöùc taïp O(|N|2) thì giaûi thuaät phaân chia môû roäng khoâng theå coù ñoä phöùc taïp O(|N|2B) ,B laø maãu trong taàm töø 5-> 10.Roõ raøng giaûi thuaät phaân chia nhò phaân khoâng theå môû roäng ñeå tröïc tieáp giaûi quyeát vaán ñeà phaân chia môû roäng vì buøng noå khaû naêng hieän thöïc . 2.Muïc tieâu thieát keá 2 :Duøng laïi GCLP. Chuùng ta ñaõ coù moät giaûi thuaät hieäu quaû cho phaân chia nhò phaân , giaûi thuaät phaân chia môû roäng duøng laïi noù . Ñieàu naày ñeà nghò phaân chia môû roäng ñöôïc taùch thaønh 2 khoái :aùnh xaï vaø löïa choïn hieän thöïc bin .GCLP coù theå söû duïng cho aùnh xaï . Muïc ñích treân vaãn khoâng ñaày ñuû tuy nhieân phaân tích vaán ñeà phaân chia môû roäng theo 2 böôùc ñoäc laäp :cuï theå laø vieäc aùnh xaï theo sau laø löïa choïn hieän thöïc bin .Duyeät qua caùc node trong ñoà thò coù nghóa hieän thöïc bin cuûa moät node rieâng bieät aûnh höôûng ñeán vieäc aùnh xaï cuûa nhöõng node chöa ñöôïc aùnh xaï .Töø ñaây coù söï töông quan giöõa vieäc aùnh xaï vaø löïa choïn hieän thöïc bin ,noù khoâng theå toái öu trong coâ laäp giöõa aùnh xaï vaø hieän thöïc .Ñieàu ñoøi hoûi naày phaûi ñöôïc giöõ trong giaûi thuaät .Höôùng ñi cuûa chuùng ta laø giaûi quyeát vaán ñeà phaân chia môû roäng ñöôïc toùm taét trong hình 8
7. http:// www.diachiweb.com Free nodes = N Tính toaùn aùnh xaï vaø thöù töï cho nhöõng node töï do - Thieát laäp giaù trò khoâng gian vaø thôøi gian trung bình - Aùp duïng GCLP Aùnh xaï cho taát caû node töï do Löïa choïn node danh hieäu T vôùi aùnh xaï MT Tìm hieän thöïc bin cho T beân trong aùnh xaï Mt Free = Free \ T Fixed ß T Update(schedule) |N|laàn n Free = roãng y aùnh xaï ,thöù töï vaø hieän thöïc bin cho taát caû caùc node hình 8 :höôùng ñi MIBS giaûi quyeát phaân chia môû roäng Heuristic ñöôïc goïi laø MIBS .Keát quaû cuoái cuøng moãi node trong doà thò coù ñaëc ñieåm bôûi 3 thuoäc tính :vieäc aùnh xaï ,hieän thöïc bin ,thöù töï node .Khi tieáp dieãn giaûi thuaät ñoøi hoûi môû roäng thoâng tin phaùt sinh ra ,moãi node trong DAG qua tuaàn töï 3 traïng thaùi :1-töï do (free node ) , 2-ñònh danh (tagged node ),3-coá ñònh (fixed node ) .Tröôùc khi giaûi thuaät baét ñaàu 3 thuoäc tính thì chöa bieát ,nhö vaäy nhöõng node ñöôïc goïi laø node töï do .Coâng nhaän raèng khoâng gian vaø thôøi gian trung bình GCLP ñöôïc aùp duïng ñaàu tieân ñeå aùnh xaï vaø tuaàn töï taát caû caùc node thay ñoåi trong ñoà thò .Moät node töï do rieâng bieät (goïi laø node ñònh danh tagged node ) seõ ñöôïc löïa choïn sau ñoù ,vaø moät hieän thöïc thích hôïp bin ñöôïc löïa choïn sau cho node ñònh danh .Trong phaàn sau moâ taû moät thuû tuïc löïa choïn moät bin , noù xaùc ñònh vieäc hieän thöïc bin cho node ñònh danh .Moät laàn aùnh xaï vaø hieän thöïc bin ñaõ bieát ,node ñònh danh trôû thaønh node coá ñònh .GCLP ñöôïc aùp duïng cho nhöõng node coøn laïi vaø quaù trình naày ñöôïc laëp cho ñeán khi taát caû node trong DAG trôû thaønh coá ñònh (fixed node ) . Giaûi thuaät MIBS coù |N| böôùc cho |N| node trong DAG . Höôùng ñi cuûa MIBS tích luõy chaët cheõ ,vaïch ra muïc tieâu thieát keá :GCLP vaø löïa choïn bin aùp duïng xen keõ beân trong moãi böôùc cuûa giaûi thuaät MIBS ,coù tieáp dieãn quay lui giöõa aùnh xaï vaø hieän thöïc bin .Giaûi thuaät MIBS coù ñoä phöùc taïp O(|N|3+B|N|2) ,trong ñoù B laø soá hieän thöïc bin treân aùnh xaï . 2.3.3 Löïa choïn hieän thöïc bin (implementation bin ) : 2.3.3.1 Toång quaùt :
8. http:// www.diachiweb.com Chæ giôùi haïn vaán ñeà löïa choïn hieän thöïc bin cho nhöõng node hardware . Nhöõng khaùi nieäm trình baøy ôû ñaây coù theå môû roäng löïa choïn hieän thöïc bin ôû software . Töø hình treân trong moãi böôùc cuûa giaûi thuaät MIBS thì GCLP aùp duïng tröôùc xaùc ñònh aùnh xaï laëp laïi cuûa nhöõng node töï do .Nhöõng node töï do ñöôïc aùnh xaï ñeán hardware taïi böôùc hieän thôøi goïi laø freeh node . Moät node ñònh danh ñöôïc löïa choïn töø taäp freeh node ,coâng nhaän raèng vieäc aùnh xaï ñöôïc xaùc ñònh bôûi GCLP ,coøn thuû tuïc löïa choïn bin ñöôïc aùp duïng ñeå löïa choïn moät hieän thöïc bin cho node ñònh danh . Hình 9 trình baøy doøng chaûy cuûa thuû tuïc löïa choïn bin .YÙ töôûng chính laø duøng ño löôøng tröôùc töông quan giöõa hieän thöïc bin cuûa node ñònh danh vôùi khoâng gian hardware yeâu caàu cho freeh node ,noù löïa choïn moät ñaùp öùng toát nhaát cho hieän thöïc bin . Tính toaùn ño löôøng tröôùc raát phöùc taïp ,ñeå ñôn giaûn ta coâng nhaän raèng freeh node coù theå hoaëc L hay H bin .Taát caû freeh node coâng nhaän khôûi taïo töø H bin cuûa chuùng .Nhöõng tính toaùn ño j löôøng tröôùc (ñöôïc goïi laø boä phaän bin BFT bin fraction) Cho moãi node bin j cuûa node ñònh danh T,phaàn nhoû cuûa freeh node caàn di chuyeån töø H bin ñeán L j bin theo thöù töï raøng buoäc thôøi gian .Moät giaù trò cao cuûa BFT chæ thò raèng neáu node ñònh danh T ñöôïc hieän thöïc trong bin j ,moät boä phaän lôùn cuûa freeh node tìm ñöôïc aùnh xaï hieän thöïc nhanh (L bin) töø ñoù laøm taêng khoâng gian toaøn boä . Ñöôøng cong boä phaän bin (BFCT) laø taäp hôïp taát caû giaù trò boä phaän bin cuûa node ñònh danh T . Ñoä nhaïy cuûa bin (Bin sensitivity) : Laø ñoä doác cuûa BFCT noù phaûn aùnh ñaùp öùng cuûa boä phaän bin trong di chuyeån cuûa node T ,giaû thieát raèng ñoä doác lôùn nhaát cuûa ñöôøng cong boä phaän bin laø trong khoaûng töø k-1 ñeán k . Vieäc di chuyeån cuûa node ñònh danh töø bin k-1 ñeán k laø söï thay ñoåi lôùn nhaát cuûa freeh node ñeán L bins cuûa chuùng töông öùng töø kàk-1 cuûa node ñònh danh ,keát quaû laø laøm giaûm lôùn nhaát cuûa khoâng h * gian free node . Töø ñoù bin thöù k-1 ñöôïc löïa choïn nhö laø hieän thöïc bin cho node ñònh danh (BT ) .Tính toaùn BFC vaø ñoä nhaïy bin ñöôïc moâ taû tieáp theo . Nhöõng ghi chuù duøng trong thuû tuïc löïa choïn bin toùm taét trong baûng 10 1 BFCT fixed node tagged node free node 0 Tính toaùn boä pha än bin (BFC T) LT K-1 K HT BS Tính toaùn ñoä nhaïy bin LT HT
9. http:// www.diachiweb.com * area Löïa choïn bin (BT ) * BT * BT time Hình 9(thuû tuïc löïa choïn bin) Kyù hieäu Giaûi thích T Node ñònh danh (tagged node ) Fixed nodes Node coá ñònh Free nodes Node töï do chöa ñöôïc aùnh xaï Freeh nodes Node töï do ñöôïc aùnh xaï ñeán hardware baèng GCLP taïi moãi böôùc cuûa giaûi thuaät MIBS CHT(CST) Ñöôøng cong hardware ,software cho node T NHT(NST) Taäp hieän thöïc bin software,hardware cuûa node T LT(HT) L (H) bin cuûa node T.L (H) laø nhanh nhaát (chaäm nhaát) cuûa bin * BT Löïa choïn hieän thöïc bin cuoái cuøng cho node T j BFT Boä phaän bin ñöôïc tính toaùn khi node T ñöôïc hieän thöïc trong bin j BFCT Ñöôøng cong boä phaän bin cuûa node T BSMAX Giaù trò lôùn nhaát cuûa ñoä nhaïy bin Hình 10 :toùm taét kyù hieäu söû duïng trong giaûi thuaät löïa choïn bin 2.3.3.2 Ñöôøng cong boä phaän bin (BFC): j Coâng nhaän raèng node T ñaõ ñöôïc hieän thöïc trong bin j ,BFT ñöôïc tính toaùn nhö boä phaän cuûa freeh node ,noù phaûi di chuyeån töø H bin ñeán L bin theo thöù töï thöïc hieän .Ñöôøng cong boä phaän j bin BFCT ñaùnh daáu cuûa boä phaän bin BFT cuûa moãi bin j cuûa node ñònh danh T. Thuû tuïc tính toaùn BFC ñöôïc moâ taû keá tieáp .Nhöõng khaùi nieäm cô sôû töông töï söû duïng trong tính toaùn GC ,ñeå ñôn giaûn ta aùp duïng thuû tuïc löïa choïn bin cho node ñònh danh ñöôïc aùnh xaï ñeán hardware bôûi GCLP . Moät hieän thöïc bin ñôn ñöôïc coâng nhaän khi node ñònh danh ñöôïc aùnh xaï sang software Procedure compute_BFC h h Input Nfixed ={ fixed nodes }.Nfree ={free nodes }. T = tagged node ,vôùi aùnh xaï MT (hardware coâng nhaän). Ñöôøng cong hieän thöïc hardware CHT. j Output BFCT = {(BFT ,j),"jÎ NHT} Khôûi taïo : NHàL= f , texec(p) bieát vôùi taát caû caùc node coá ñònh ,pÎNfixed. For (j=1;j<= |NHT| ; j++) { j S1 Thieát laäp , texec(T)=thïT h H h S2 for taát caû kÎ Nfree ,thieát laäp , texec(k) = thk (taát caû free nodes ôû H bins) S3 Tính toaùn Tfinish , cho aùnh xaï vaø , texec cho taát caû nodes h S4 Tìm trong taäp NHàL cuûa free nodes ñöôïc di chuyeån ñeán L bin trong thöù töï gaëp ñöôøng giôùi haïn
10. http:// www.diachiweb.com ß h S41 NHàL next(Nfree ) L S42 , texec(f) =thf , "fÎ NHàL S43 Caäp nhaät (Tfinish) S44 if Tfinish > D goto s41 å sizei i Î NHàL i j S5 BFT = , 0 ñieàu mong muoán laø bin BT ñöôïc löïa choïn nhö theá naøo * cho node naày .Moät caùch tröïc quan BT = HT ,töø ñoù ñieàu naày cho khoâng gian hardware laø nhoû H h nhaát cho node T ôû HT .Tuy nhieân BFT thì cao ,moät boä phaän lôùn cuûa node free thì trong L bin vì vaäy toång khoâng gian hardware coù theå khoâng caàn lôùn ,khi node ñònh danh dòch töø HT bin ñixuoáng ,keát quaû laøm giaûm trong BF nguï yù raèng boä phaän cuûa node freeh ôû L bin giaûm vaø tuaàn töï cho h pheùp khoâng gian hardware cuûa node free giaûm .Ñoä doác cuûa BFCT ñaïi dieän cho khoâng gian bin ñöôïc laøm giaûm nhanh nhö theá naøo cuûa node freeh trong node T.Ñoä doác naày goïi laø ñoä nhaïy bin BS ,noù phaûn aùnh moái töômg quan giöõa söï di chuyeån bin cuûa node ñònh danh vaø toång khoâng gian h j (j+1) j H ñöôïc laøm giaûm cuûa free node co nghóa BST =BFT –BFT ,L 0 .Neáu BFCT laø haèng soá (hình 11c) thì BSmax= 0 vaø node ñònh danh ñöôïc aùnh xaï sang H bin cuûa noù .Töø ñaây di chuyeån noù töø chaäm nhaát ñeán hieän thöïc nhanh nhaát khoâng aûnh höôûng ñeán nhöõng node freeh (a) (c) H BFCT BFT BFCT