Hardware và software
Phương pháp tổng hợp hardware và software tạo ra mô tả tổng hợp của 2 thành phần thông qua việc sử dụng các công cụ có sẵn như là PTOLEMY và HYPER tổng hợp tạo thành hardware và software.
http:// www.diachiweb.com
Trang Chuû Muïc Luïc
1. GIÔÙI THIEÄU CHUNG:
Trong phaïm vi cuûa baûng baùo caùo naøy chuùng toâi seõ trình baøy vieäc thieát keá möùc heä thoáng gaén
vôùi vieäc troän laãn thaønh phaàn hardware vaø software .Troïng taâm laø boán vaán ñeà chính :vieäc phaân
chia ,toång hôïp ,moâ phoûng vaø phöông phaùp thieát keá .trong thieát keá möùc heä thoáng nhöõng öùng duïng
ñöôïc ñaïi dieän nhö moâït ñoà thò coâng vieäc ,maø nhöõng coâng vieäc goïi laø nhöõng node ,vaø moåi node
thì coù vaøi caùch ñeå löïa choïn hieän thöïc khaùc nhau tuøy thuoäc vaøo khoâng gian noù chieám vaø thôøi gian
thöïc thi .Vaán ñeà phaân chia laø vieäc xaùc ñònh moät node ñöôïc aùnh xaï sang hardware hay software .
Phöông phaùp toång hôïp taïo ra moâ taû toång hôïp cuûa thaønh phaàn hardware vaø software thoâng
qua vieäc söû duïng caùc coâng cuï coù saún nhö laø :PTOLEMY vaø HYPER toång hôïp taïo thaønh
hardware vaø software .
Moâ phoûng giöû vai troø quan troïng trong thieát keá möùc heä thoáng .ÔÛ caáp ñoä ñaëc taû ,noù cho
pheùp moâ phoûng caùc moâ hình .Caùc coâng cuï cho pheùp moâ phoûng caùc ñaëc taû toång hôïp ñaõ yeâu caàu
.ÔÛ caáp hieän thöïc nhöõng coâng cuï moâ phoûng hoå trôï cho vieäc troän laãn heä thoáng hardware vaø
software .
Thieát keá heä thoáng bao goàm caû hai thaønh phaàn hardware vaø software khoâng phaûi laø vaán
ñeà môùi .Trong höôùng thieát keá truyeàn thoáng thì phaàn cöùng ñöôïc thieát keá vaø taïo maãu tröôùc caùc
thaønh phaàn software ñöôïc thieát keá sau ñoù .Vieäc thieát keá hardware vaø software rieâng reõ gaëp phaûi
khoù khaên trong vieäc toái öu thieát keá heä thoáng .Höôùng thieát keá nhö vaäy khoâng töông xöùng khi thieát
keá nhöõng heä thoáng coù yeâu caàu hieäu quaû moät caùch khaét khe vaø thôøi gian thieát keá nhoû ,höôùng
thieát keá chung (codesign) cho pheùp thieát keá nhöõng heä thoáng coù yeâu caàu nhö vaäy .Nguyeân lyù chuû
yeáu trong thieát keá chung laø traùnh söï coâ laäp giöûa hardware vaø software ,chieán löôïc thieát keá
chung cho pheùp thieát keá hardware ,software moät caùch song song vôùi söï aûnh höôûng qua laïi thoâng
tin phaûn hoài cuûa tieán trình thieát keá hardware vaø software .Ñieàu naøy ñöôïc hoaøn thaønh nhôø nhöõng
coâng cuï vaø nhöõng phöông phaùp hoå trôï chaët cheõ trong vieäc thieát keá caû hai software vaø hardware
thoâng qua khung laøm vieäc thoáng nhaát (unified framework) .Keát quaû cuûa vieäc thieát keá chung
hardware vaø software laø ñaït ñöôïc nhöõng thieát keá chaát löôïng cao vaø giaûm ñöôïc thôøi gian thieát
keá.
http:// www.diachiweb.com
Moät sô ñoà khoái cho thieát keá chung (hình 1)
Ñaëc taû (design specification)
Nhöõng raøng buoäc Nhaäp döõ lieäu
(design constraints) (user input)
Ñaùnh giaù khoâng gian thôøi gian
(area time estimation)
Manual
Phaân chia hardware ,software CPLEX (ILP)
(hw/sw partitioning) MIBS
Toång hôïp hardware Toång hôïp giao Toång hôïp software
(hardware synthesis dieän(interface (software synthesis)
synthesis)
Sô ñoà noái daây
(netlist generation)
Moâ phoûng
(simulation)
PTOLEMY
Heä thoáng toång hôïp (synthesized system)
(layout +software )
(hình 1) Löu ñoà thieát keá chung
· Ñaùnh giaù:(estimation)
Coâng cuï ñaùnh giaù (estimation tool) taïo ra öôùc löôïng cho vieäc hieän thöïc (khoâng gian vaø thôøi gian
yeâu caàu )cho moãi node trong ñoà thò khi hieän thöïc trong hardware vaø software .Nhöõng vieäc ñaùnh
giaù naày seõ laø input cho coâng cuï phaân chia (partitioning tool).
http:// www.diachiweb.com
· Phaân chia (partitioning) :
Sau khi thu ñöôïc caùc ñaùnh giaù veà khoâng gian vaø thôøi gian ,böôùc keá tieáp trong löu ñoà thieát keá
chung laø phaân chia .keát quaû cuûa vieäa phaân chia laø daãn ñeán vieäc xaùc ñònh coâng vieäc goàm 3 thoâng
soá
· Aùnh xaï coâng vieäc (task) ñoù thöïc hieän baèng hardware hay software
· Quan heä giöûa caùc task khi noù thöïc thi
· Hieän thöïc (choïn löïa caùch hieän thöïc chuù yù ñeán giaûi thuaät ,söï bieán ñoåi
(transformation),giaù trò khoâng gian ,thôøi gian ) .
Khung laøm vieäc trôï giuùp thieát keá (design assistant framework) cho pheùp user thöïc nghieäm vôùi
nhöõng coâng cuï phaân chia khaùc nhau :baèng tay , giaûi phaùp ILP (CPLEX) , hay kinh nghieäm
(heuristic MIBS) .
Vieäc phaân chia laø vaán ñeà khoâng phaûi deã daøng .Xem xeùt ñeán ñaëc taû möùc coâng vieäc ñieån hình coù
töø 50 ñeán 100 node . Moãi task coù theå aùnh xaï hoaëc hardware ,software ,hôn theá nöõa trong moãi
coâng vieäc coù vaøi caùch löïa choïn ñeå hieän thöïc .
· Toång hôïp chung (cosynthesis)
Moät öùng duïng ñöôïc phaân chia vaøo hardware vaø software ,nhöõng thaønh phaàn rieâng reõ
software ,hardware ,giao dieän phaûi ñöôïc toång hôïp laïi .Coâng cuï toång hôïp ñaëc thuø phuï thuoäc
vaøo coâng ngheä mong muoán.Coâng cuï toång hôïp hardware goàm SILAGE, VHDL, coâng cuï toång
hôïp software thöôøng duøng C , Assembly . Vieäc phaùt sinh giao dieän phuï thuoäc vaøo moâ hình
kieán truùc mong muoán
· Moâ phoûng chung (cosimulation):
Caùc thaønh phaàn software ,hardware ,giao dieän ñaõ toång hôïp ,böôùc tieáp theo laø moâ phoûng heä
thoáng nhôø moâi tröôøng moâ phoûng PLOTEMY
· Kieán truùc ñích (target architecture) :
Address bus
Controller
Hardware
modul
Hardware
Processor core modul
Data bus Control bus
Hardware
modul
(hình 2) KIEÁN TRUÙC ÑÍCH
The hardware bao goàm nhöõng thaønh phaàn coù saün hoaëc phaûi cheá taïo theâm, vaø software laø nhöõng
chöông trình chaïy treân nhöõng thaønh phaàn laäp trình ñöôïc .Giao dieän hardware ,software bao goàm
noái keát logic vaø ñieàu khieån phuï thuoäc vaøo cô cheá truyeàn nhaän döõ lieäu ñöôïc chon .
2.PARTITIONING :
Trong phaàn naày chuùng ta taäp trung nghieân cöùu vaán ñeà phaân chia hardware hay software
cho caùc öùng duïng veà heä thoáng thôøi gian thöïc .Giaû söû ta coù moät ñaëc taû öùng duïng ñöôïc bieåu dieån
baèng ñoà thò SDF (synchronous data flow) ,SDF naày chuyeån thaønh DAG (directed acycle graph)
,DAG naày laø input cho coâng cuï phaân chia (partitioning tool).
http:// www.diachiweb.com
Coù hai giai ñoaïn ñeå phaân chia :Phaân chia nhò phaân (binary partitioning ) ,phaân chia môû
roäng (extended partitioning)
Phaân chia nhò phaân:laø aùnh xaï moãi node cuûa DAG sang hardware hay software vaø xaùc
ñònh thöù töï cho moãi node .
Phaân chia môû roäng :Vaán ñeà phaân chia software ,hardware khoâng chæ laø vieäc aùnh xaï sang
software hay hardware maø trong moãi node coøn coù vaán ñeà söû duïng nhöõng giaæ thuaät vaø caùc boä
phaän toång hôïp khaùc nhau .Nhöõng hieän thöïc naày khaùc nhau veà ñaëc tröng trong khoâng gian vaø
thôøi gian treå rieâng ,nhöõng tính chaát naày cuûa node ñöôïc goïi laø “implementation bins”.Vieäc phaân
chia môû roäng laø keát noái vaán ñeà aùnh xaï moät node sang hardware hay software trong DAG vôùi
vieäc löïa choïn moät implementation bins thích hôïp .
Vieäc phaân chia noùi chung laø vaán ñeà khoù .Nhöõng thoâng soá thieát keá coù theå thöôøng ñöôïc söû
duïng laøm thaønh coâng thöùc döôùi daïng vaán ñeà toái öu soá nguyeân .Vieäc laäp thaønh coâng thöùc chính
xaùc laø khoù do vaäy phaûi duøng moät soá keát quaû heuristic ñeå laøm giaûm thôøi gian.
Toùm laïi vaán ñeà phaân chia môû roäng vaø phaân chia nhò phaân ñöôïc xaùc ñòng nhö sau
Binary Hardware /Software mapping and scheduling
partitioning
Extended
partitioning Hardware /Software mapping and scheduling + implementtation bin selection
3 .Toång hôïp chung :
Trong chöông tröôùc giaûi thuaät phaân chia caùc node cuûa öùng duïng sang hardware ,software ñaõ
ñöôïc moâ taû .Vieäc phaân chia taïo thaønh 3 thuoäc tính cho moät node :aùnh xaï sang hardware hay
software ,kieåu hieän thöïc cho aùnh xaï naày vaø thöù töï .
Böôùc tieáp theo trong quaù trình thieát keá laø toång hôïp heä thoáng troän laãn hardware ,software
.Vaán ñeà toång hôïp laø toång hôïp hardware ,software vaø caùc thaønh phaàn giao dieän trong hieän thöïc
cuoái cuøng .
Moâ phoûng hardware ,software ,laø quaù trình moâ phoûng nhöõng thaønh phaàn hardware
,software cuûa heä thoáng ,troän hardware ,software beân trong moät moâi tröôøng thoáng nhaát .Ñieàu naày
bao goàm moâ phoûng cuûa nhöõng modun hardware ,boä xöû lyù ,vaø software ñöôïc boä xöû lyù thöïc thi
.Nhöõng yeâu caàu cuûa moät moâi tröôøng moâ phoûng laø taïo ra phaùc thaûo .PTOLEMY coù ñaày ñuû coâng
cuï noù hoå trôï haàu heát nhöõng yeâu caàu naày .
4.Moâ phoûng chung :
Moâ phoûng hardware ,software laø quaù trình cuûa thöïc hieän moâ phoûng caùc thaønh phaàn
hardware ,software cuûa moät heä thoáng ñaõ ñöôïc troän laãn (toång hôïp ) hardware ,software beân trong
moät moâi tröôøng ñoàng nhaát . Ñieàu naày bao goàm söï moâ phoûng caùc moñun hardware ,boä xöû lyù vaø
software maø boä xöû lyù seõ thöïc thi .
Caùc höôùng coù theå bao goàm
4.1.Moâ hình chi tieát cuûa boä xöû lyù :
http:// www.diachiweb.com
Nguyeân taéc chung laø nhöõng thaønh phaàn cuûa boä xöû lyù coù theå söû duïng moâ hình nhöõng söï kieän
rôøi raïc cuûa kieán truùc hardware beân trong nhö (ñöôøng döõ lieäu ,giaûi maõ leänh ,bus,…) maø software
seõ keát noái vaø thöïc thi treân noù . Thöôøng duøng VHDL hay VERYLOG ñeå moâ phoûng
4.2. Moâ hình bus:
Ñaây laø nhöõng söï kieän hoaït ñoäng treân ngoaïi vi cuûa boä xöû lyù khoâng keát hôïp thöïc thi software
vôùi boä xöû lyù . Ñieàu naày coù ích cho vieäc kieåm tra aûnh höôûng qua laïi ôû möùc thaáp nhö bus vaø boä
nhôù nhöng khoù khaên cho baûo ñaûm chính xaùc moâ hình hoaït ñoäng treân ngoaïi vi ,cuõng khoù khaên
cho moâ phoûng aûnh höôûng qua laïi hardware ,software .
4.3.Moâ hình kieán truùc taäp leänh :
Kieán truùc taäp leänh coù theå moâ phoûng hieäu quaû baèng chöông trình C .Chöông trình C laø moät boä
phaän thoâng dòch cho software . Noù caäp nhaät traïng thaùi cuûa boä xöû lyù vaø phaùt sinh söï kieän ñeán moâ
hình hoaït ñoäng ngoaïi vi cuûa boä xöû lyù .
4.4.Moâ phoûng dòch :
Nguyeân taéc chung laø chuyeån ñaëc taû software gaén vôùi söï thöïc thi sang code töï nhieân ñeå
processor laøm vieäc moâ phoûng
4.5. Moâ hình hardware :
Neáu boä xöû lyù toàn taïi trong hình thöùc hardware thì hardware vaät lyù coù theå duøng ñeå moâ hình
hoaù procesor trong moâ phoûng . Coù theå duøng FPGA prototype ñeå moâ hình hoaù processor .
Moâi tröôøng PTOLEMY laø moät moâi tröôøng moâ phoûng kieåu maãu ñöôïc phaùt trieån bôûi nhoùm
DSP ôû ñaïi hoïc BERKELEY California . PTOLEMY laø moâi tröôøng duy nhaát coù khaû naêng trôï
giuùp trong vieäc moâ phoûng chung heä thoáng troän laãn hardware ,software .Moâi tröôøng naày khoâng
nhöõng coù khaû naêng moâ phoûng maø coøn toång hôïp heä thoáng .
4.6 Moät tröôøng hôïp nghieân cöùu thieát keá trong moâi tröôøng Ptolemy:
Phaàn naày moâ phoûng thieát keá moät keânh ñieän thoaïi choïn cho tröôøng hôïp nghieân cöùu naày söû
duïng moâi tröôøng Ptolemy cho thieát keá chung troän laãn phaàn cöùng ,phaàn meàm .
4.6.1 Moâ phoûng keânh ñieän thoaïi :
Ñoà thò doøng chaûy tín hieäu cuûa keânh ñieän thoaïi ñöôïc trình baøy ôû hình 20 , vieäc moâ phoûng
ñöôïc thieát keá duøng Motorola DSP 56000s cho haàu heát xöû lyù tín hieäu . Moâ hình phaàn cöùng cuûa heä
thoáng yeâu caàu theo maãu beân caïnh DSPs , cuõng nhö thaønh phaàn caùc keát noái logic .
4.6.2 Löïa choïn test case :
ÔÛ ñaây ta moâ phoûng keânh ñieän thoaïi ñöôïc trình baøy ôû hình 20 ,noù ñaïi dieän cho moät heä
thoáng thöïc vaø thöïc hieän baèng thieát keá chung ,ñaàu tö vaø giaù saûn phaåm thaáp , thôøi gian ñöa ra thò
tröôøng cuõng giaûm xuoáng vieäc thieát keá vaø moâ phoûng beân trong moâi tröôøng Ptolemy .
4.6.3 Giôùi thieäu beân trong moâi tröôøng Ptolemy :
Hình 21 trình baøy nhöõng thaønh phaàn caáu truùc cuûa Plotemy . Ñôn vò cô sôû cuûa Plotemy laø
block nhöõng portholes cung caáp giao tieáp chuaån ñeå thoâng tin giöõa caùc block . Moät block goàm
moät moñun cuûa code (“go()” method) noù göûi döõ lieäu khi chaïy , döõ lieäu ñöôïc göûi ñeán ñaàu vaøo
cuûa caùc portholes vaø phaùt sinh döõ lieäu göûi ra ôû ñaàu ra cuûa portholes . Phöông phaùp “go() “ ñöôïc
ñieàu khieån bôûi lieät keâ caùc ñònh nghóa ngöõ nghæa caùc maïng cuûa block , truyeàn daãn caùc block
duøng nhöõng doøng goïi laø particle . Lôùp ño löôøng Geodesic ñöôïc thieát laäp ñeå lieân keát giöõa caùc
portholes . lôùp plasma quaûn trò caùc particles .
Caáp thaáp nhaát trong Plotemy laø kieåu star trong block . Moät nhoùm (galaxy) cuõng tìm ñöôïc
töø moät block , moät galaxy coù theå chöùa beân trong nhöõng galaxy vaø star. Moät ñích (target) cuõng
tìm ñöôïc töø block ñieàu khieån thöïc thi moät öùng duïng . Trong moät öùng duïng toång hôïp noù coù theå
toång hôïp assembly code cho DSP laäp trình ñöôïc .
http:// www.diachiweb.com
Hình 21 Nhöõng khoái beân trong moâi tröôøng Ptolemy
4.6.4 Phöông phaùp thieát keá :
Moät höôùng toång quaùt ñeå thieát keá chung ñöôïc ñeà nghò ôû hình 22 . Treân cô sôû caùc böôùc
thieát keá chung naày thieát keá moâ phoûng keânh ñieän thoaïi seõ ñöôïc ñeà caäp
Hình 22 Phöông phaùp thieát keá chung duøng Ptolemy
Böôùc 1 : Ñaëc taû öùng duïng , ôû böôùc naày ñöôïc ñaëc taû baèng giaûi thuaät caáp cao vaø moâ phoûng
ñaëc tröng .
Böôùc 2 : Söû duïng mieàn SDF cuûa moâi tröôøng Ptolemy.
Böôùc 3 : Phaân chia ra phaàn cöùng hoaëc phaàn meàm .
Böôùc 5 , 6 , 7 : Moâ phoûng phaàn cöùng , caáu hình phaàn cöùng ñöôïc phaùt trieån leân möùc cao
hôn vaø moâ phoûng caùc ñaëc tröng .
http:// www.diachiweb.com
Böôùc 4 : Toång hôïp phaàn meàm .
Toång hôïp phaàn cöùng , phaàn meàm sau ñoù ñöôïc moâ phoûng ôû böôùc 8 .
Moâi tröôøng Ptolemy cho pheùp moâ phoûng theo möùc ñoä phaùt trieån naâng cao cuûa phaàn cöùng
, phaàn meàm treân cô sôû raøng buoäc thôøi gian vaø caùc ñaëc ñieåm hôïp lyù .
A. Thieát keá duøng Shared memory :
Höôùng naày duøng 2 DSPs cho moâ phoûng keânh full duplex cuûa ñieän thoaïi . ÔÛ ñaây DSPs
ñöôïc caáu hình ñeå truyeàn nhaän thoâng tin ôû boä nhôù duøng chung (Shared memory) . Hình 23 trình
baøy nhöõng thaønh phaàn trong moâi tröôøng Ptolemy duøng cho heä thoáng naøy . Caáp ñoä tröøu töôïng chæ
laø giaûi thuaät moâ taû trình baøy ôû hình 23(a) . Giaûi thuaät phöùc taïp naày bao goàm tuyeán tính vaø khoâng
tuyeán tính , ñoä dôøi taàn soá , pha vaø nhieãu . Thieát keá ñöôïc xaây döïng trong mieàn phaùt sinh code ,
töông thích ñeán moâ hình SDF cho tính toaùn . Giaûi thuaät cung caáp cho boä phaùt sinh code , boä phaùt
sinh code hình 23(b) cuõng caàn moâ taû kieán truùc ñích . Töø ñaây böôùc tieáp laø phaùt trieån phaàn cöùng
cho heä thoáng ( böôùc 5 , 6 , vaø 7 ôû hình 22) . Hình 23(c) trình baøy moâ hình phaàn cöùng cuûa heä
thoáng bao goàm 2 DSP laäp trình ñöôïc tính toaùn qua moät boä nhôù Shared memory .
Moâ hình full duplex caáu taïo bôûi tín hieäu töø moät ñaàu cuoái cuûa keânh ñeán boä loïc ñöôïc löôïng töû
hoaù vaø göûi ñeán DSP ñaàu tieân , DSP thöù hai ñoïc döõ lieäu töø shared memory xöû lyù vaø göûi ñeán
ñaàu cuoái khaùc cuûa keânh . Töông töï quaù trình xöû lyù ngöôïc ñöôïc laøm ngöôïc laïi . Chuyeån ñoåi
A/D ñöôïc löôïng töû hoaù ôû hình 23(e) . Hình 23(f) trình baøy moâ hình chuyeån ñoåi D/A , giaûi
thuaät ñöôïc chuyeån ñeán boä phaùt sinh code . Böôùc 4 vaø 5 cuûa hình 22 phaân chia vaø lieät keâ caùc
khoái vaø phaùt sinh assembly code cho processor trong heä thoáng . Ñaàu ra cuûa boä sinh code laø
assembly code ñaùp öùng giaûi thuaät chaïy treân 2 processor . Phaàn cöùng sau ñoù ñöôïc moâ phoûng
ôû böôùc 8 cuûa hình 22 chaïy code ñöôïc phaùt sinh bôûi boä phaùt sinh code .
Chuùng ta coù theå thaáy taùc ñoäng laãn nhau giöõa giaûi thuaät moâ taû , moâ phoûng , phaùt sinh code ,
phaùt trieån phaàn cöùng vaø moâ phoûng , phaàn cöùng ñöôïc moâ hình taïi nhöõng möùc ñoä khaùc nhau
cuûa giaûi thuaät moâ taû duøng nhöõng mieàn khaùc nhau cuûa moâi tröôøng Ptolemy .
B.Thieát keá duøng Serial port :Moät kieåu thieát keá khaùc ñöôïc löïa choïn nhö hình 24 ñöôïc phaùt
trieån baèng taùc ñoäng qua laïi qua böôùc 4 ñeán böôùc 8 ôû hình 22 . ÔÛ ñaây DSPs ñöôïc truyeàn thoâng
tin baèng daõy coång thay theá cho shared memory . Nhö ñaõ thaáy trong hình , tín hieäu töø ñaàu
cuoái cuûa keânh ñöôïc nhaän baèng DSP ñaàu tieân (DSP1) ôû ñaây tín hieäu ñöôïc xöû lyù vaø göûi qua
moät daõy coång ñeán DSP thöù 2 (DSP2) sau ñoù göûi ra moät ñaàu cuoái khaùc cuûa keânh . Nhöõng khoái
khaùc nhö A/D , D/A ñöôïc thieát keá gioáng nhö thieát keá shared memory
Caáu hình phaàn cöùng thay ñoåi ( nhö IPC delay) ñöôïc cung caáp ñeán boä sinh code , boä sinh code
seõ phaân chia vaø lieät keâ laïi code ôû böôùc 4 hình 22 .
Thieát keá naày minh hoïa cho tröôøng hôïp vôùi chieán löôïc IPC khaùc nhau coù theå ñieàu khieån
baèng tay trong Ptolemy . Hai heä thoáng naày (shared memory va serial port) ñöôïc ñaùnh giaù chuù yù
ñeán hieäu suaát nhö IPC overhead , giaù cuûa heä thoáng .
5.TOÅNG KEÁT:
Trong ñoà aùn naày ñeà caäp ñeán phaùt trieån kyõ thuaät cho thieát keá heä thoáng xöû lyù tín hieäu .
Thieát keá heä thoáng ñoøi hoûi giaù chính xaùc , hieäu suaát vaø raøng buoäc veà thôøi gian . Nhöõng hieän thöïc
hardware ,software thuaàn tuùy thöôøng khoâng gaëp raøng buoäc naày beân caïnh ñoù moät vaøi boä phaän
cuûa öùng duïng thì gaén vôùi hoaëc hardware , hoaëc software . Töø ñaây nhöõng öùng duïng höôùng tôùi
http:// www.diachiweb.com
nhöõng hieän thöïc troän laãn hardware , software . Nhöõng öùng duïng naày ñöôïc ñaëc taû toát nhaát ôû möùc
ñoä Task nguyeân thuûy .
Höôùng ñi ñeán thieát keá laø thieát keá chung caùc thaønh phaàn hardware , software . Ñieàu naày
cho pheùp nhöõng thieát keá hardware ,software laø tieán trình song song , vôùi söï hoài tieáp vaø aûnh
höôûng laãn nhau giöõa 2 quaù trình khi phaùt trieån . Thieát keá chung cho pheùp khaûo saùt roäng lôùn
nhöõng traïng thaùi löïa choïn hieän thöïc , do ñoù heä thoáng ñöôïc toái öu hoùa vaø troïn veïn cuûa noù .
Boán vaán ñeà chính ñöôïc ñaët ra trong thieát keá chung möùc heä thoáng laø : phaân chia , toång hôïp ,
moâ phoûng vaø quaûn lyù phöông phaùp thieát keá , chuùng ta coá gaéng cung caáp nhöõng caùch giaûi
quyeát cho vaán ñeà naày nhö giaûi quyeát heä thoáng xöû lyù tín hieäu ñaëc taû töø SDF .
5.1 Phaân chia :
Phaân chia nhò phaân laø vaán ñeà xaùc ñònh cho moãi node trong moät öùng duïng ñoù laø : aùnh xaï
moät node sang hardware hay software , trình töï cuûa söï thöïc thi .
Phaân chia môû roäng laø vaán ñeà gaén vôùi aùnh xaï node trong ñoà thò möùc cao ñeán hardware
hay software thöù töï vaø löïa choïn hieän thöïc ñaëc bieät cho moãi node , muïc tieâu cuoái cuøng cuûa caû hai
laø laøm nhoû nhaát toång khoâng gian hardware , tính ñeán raøng buoäc taøi nguyeân .
Giaûi thuaät GCLP giaûi quyeát vaán ñeà phaân chia nhò phaân ,moät vaøi ñaëc ñieåm cuûa giaûi thuaät :
1 . Coâng nhaän raèng phaân chia nhò phaân laø toái öu raøng buoäc . GCLP duøng moät ño löôøng
giôùi haïn thôøi gian chung GC ñeå löïa choïn thích öùng muïc tieâu aùnh xaï ôû moãi böôùc . Neáu thôøi gian
laø tranh chaáp noù löïa choïn aùnh xaï maø thôøi gian thöïc thi cuûa node seõ nhoû nhaát , nhöng noù tieâu thuï
taøi nguyeân nhoû nhaát .
2 . Theâm vaøo xem xeùt naày coù caùc pha cuïc boä nhö extremity measure ,repeller measure
vaø normal ñeå xeùt moät node aùnh xaï sang hardware hay software thích hôïp hôn . GCLP coù ñoä
phöùc taïp O(|N|2).
Phaân chia môû roäng ñöôïc giaûi quyeát baèng giaûi thuaät MIBS ,yù nghóa cuûa MIBS laø môû roäng
GCLP cho phaân chia môû roäng maø khoâng xaây döïng nhöõng phöùc taïp keát hôïp khaùc . Chieán löôïc
phaân loaïi nhöõng node trong ñoà thò laø : free node , tagged node , fixed node . Ñaàu tieân khôûi taïo
taát caû nhöõng node trong ñoà thò laø free , aùnh xaï vaø hieän thöïc bin chöa bieát , GCLP aùp duïng cho
taát caû caùc node trong taäp free ,sau ñoù moät node tagged seõ ñöôïc choïn töø taäp naày vaø aùnh xaï cuûa
noù ñöôïc quyeát ñònh baèng GCLP . Moät thuû tuïc löïa choïn bin ñöôïc duøng ñeå tính toaùn vaø hieän thöïc
thích hôïp bin cho tagged node , noù söû duïng ño löôøng tröôùc goïi laø bin fraction ,noù löôïng giaù moãi
bin cuûa node . Bin fraction ñöôïc söû duïng tính toaùn ño löôøng ñoä nhaïy bin töông quan ñeán hieän
thöïc bin vôùi thu giaûm toång khoâng gian hardware . Thuû tuïc löïa choïn bin ñöôïc choïn vôùi ñoä nhaïy
cao nhaát . Tính toaùn ñoä nhaïy bin ñöôïc ñôn giaûn hoùa baèng caùch coâng nhaän nhöõng node töï do coøn
laïi hoaëc chaäm nhaát . Tagged node trôû thaønh fixed node vaø löïa choïn ñöôïc moät hieän thöïc bin .
GCLP sau ñoù aùp duïng leân taát caû caùc node free coøn laïi vaø trình töï ñöôïc laëp cho ñeán khi taát caû
node trong ñoà thò thaønh coá ñònh
5.2 Toång hôïp vaø moâ phoûng :
Toång hôïp chung laø vaán ñeà cuûa toång hôïp hardware ,software vaø thaønh phaàn giao dieän cuûa
heä thoáng , baét ñaàu töø moät DAG ñaõ ñöôïc phaân chia kyõ thuaät toång hôïp ñaït ñöôïc kieán truùc ñích bao
goàm : moät processor ñôn laäp trình ñöôïc vaø nhieàu moñun hardware . Node ñöôïc aùnh xaï sang
hardware ,software ñöôïc truyeàn nhaän duøng moät aùnh xaï boä nhôù .
Toång hôïp chung laø phaân raõ DAG ñöôïc phaân chia thaønh ñoà thò hardware ,ñoà thò software
,vaø giao dieän .Moãi node trong ñoà thò hardware ,software ñeàu coù kyõ thuaät ñaïi dieän . Coâng cuï toång
http:// www.diachiweb.com
hôïp ñöôïc söû duïng ñeå phaùt sinh hieän thöïc cuoái cuøng töø nhöõng ñoà thò naày . Nhöõng coâng cuï coù saün
nhö ( HYPER vaø PTOLEMY ) ñöôïc duøng ñeå phaùt sinh hieän thöïc cuoái cuøng .
Moâ phoûng hardware , software laø quaù trình moâ phoûng caùc thaønh phaàn hardware vaø
software cuûa heä thoáng troän laãn beân trong moâi tröôøng ñoàng nhaát ,ñieàu naày coù nghóa laø moâ phoûng
moñun hardware , boä xöû lyù ,software maø boä xöû lyù thöïc thi
5.3 Quaûn lyù phöông phaùp thieát keá :
Chuùng ta ñöa ra moät cô sôû haï taàng hoå trôï quaûn lyù hieäu quaû quaù trình thieát keá vôùi taàm
quan troïng laø quaûn trò doøng thieát keá . Cô sôû haï taàng ñöôïc phaùt trieån nhö DMM domain beân trong
moâi tröôøng PTOLEMY coù moät coâng cuï laø Designmaker ñaùp öùng töï ñoäng quaûn lyù doøng chaûy .
6. PHUÏ LUÏC
1.Moâi tröôøng PTOLEMY
Ptolemy laø moâi tröôøng ñoàng nhaát trôï giuùp cho söï toång hôïp vaø moâ phoûng.Noù söû duïng kyõ thuaät
laäp trình höôùng ñoái töôïng ñeå moâ hình nhöõng heä thoáng con trong söï töï nhieân vaø hieäu quaû nhaát vôùi
moät söï hôïp nhaát troïn veïn.
Neàn taûng cuûa noù laø BLOCK, moät heä thoáng ñöôïc moâ phoûng nhö moät Network cuûa Block, thöù
töï ñöôïc quyeát ñònh bôûi ngöõ nghóa trong network nghóa laø noù quyeát thöù töï maø block ñöôïc thöï thi
Ñoái töôïng thaáp nhaát trong Ptolemy laø loaïi STAR.A STAR ñöôïc ñaëc taû bôæ C++ ,ñaëc taû naøy
bao goàm nhöõng haøm :setup(),go(),wrapup().A GALAXY cuõng baét nguoàn töø BLOCK chöùa nhöõng
BLOCK khaùc beân trong.A GALAXY Ùcoù theå chöùa caû hai loaïi laø Galaxy vaø Star.
Ptolemy trôï giuùp nhieàu maåu moâ phoûng ,nhöõng loaïi thieát keá khaùc nhau goïi laø DOMAIN .Moät
Domain moâ taû ñuùng moâ hình tính toaùn thích hôïp cho moät loaïi heä thoáng con ñaëc thuø.Moät soá
Domain moâ phoûng hieän thôøi ñöôïc trôï giuùp bao goàm:Synchronous Data Flow(SDF) ,Dynamic
Data Flow(DDF),Discrete Event (DE) vaø Digital Hardware Modeling Environment(Thor).
A Domain trong Ptolemy bao goàm taäp cuûa Block vaø thöù töï phuø hôïp vôùi moâ hình söï tính
toaùn chung ,noù cuõng trôïï giuùp söïï troän laån giöûa caùc moâ hình naøy ôû möùc heä thoáng ñeå phaùt trieån heä
thoáng hoån taïp vôùi söï khaùc nhau ôû möùc tröuø töôïng. Söï troän coù thöù baäc baát cöù moâ hình tính toaùn
coù theå söû duïng ôû möùc cao cuûa heä thoáng ,beân trong moãi möùc cuûa heä thoáng coù thöù baäc noù coù theå
coù nhöõng Block ñang chöaù caùc Domain beân ngoaøi.Heä thoáng hoån taïp coù thöù baäc thì haàu heát khaùc
nhau töø nhöõng khaùi nieäm cuûa simulation backplane.
2.Ñoä phöùc taïp cuûa giaûi thuaät GCLP
Ñoä phöùc taïp cuaû giaûi thuaät GCLP ñöôïc tính nhö sau:
S1.Tính toaùn GC:O(A+N)
S1.1.Löôïng giaù taäp cuûa nhöõng node di chuyeån ñeán phaàn cöùng:O(1)
S1.2.Tính toaùn thôøi gian hoaøn thaønh thöïc teá:O(A+N).
S2.Xaùc ñònh taäp nhöõng node saún saøng:O(N)
S3.Tính toaùn thôøi gian thöïc thi hieäu quaû:O(N)
S4.Tinh toaùn ñöôøng ñi daøi nhaát:O(A).
S5.Choïn moät node saün saøng vôùi ñöôøng ñi daøi nhaát lôùn nhaát:O(N)
S6.Xaùc ñònh aùnh xaï vaø thöù töï:O(1)
Trong böôùc S1.2 tính toaùn thôøi gian hoaøn thaønh duøng giaûi thuaät
COMPUTE_ACTUAL_FINISH_TIME sau:
Procedure COMPUTE_ACTUAL_FINISH_TIME
http:// www.diachiweb.com
Input:DAG vôùi söï xaùc ñònh laïi aùnh xaï vaø töoâng öùng vôùi thôøi gian thöïc
thi(texec(I)) cho moãi node i
Output:Tfinish=thôøi gian hoaøn thaønh cuûa DAG
Khôûi taïo:dsp_finish_time=0,Tfinish=0:
S1.Gaùn nhaõn cho taát caû caùc node vôùi caáp cuûa noù
S2.Gaùn maët naï cho taát caû caùc node caáp 0 nhö laø node saún saøng
S3.while (ready nodes exist){
S3.1.Choïn node saún saøng i:O(i)
S3.2.Tìm Tstart(i):O(1)
S3.3.if (i in software)
Tstart(i)=max(maxj(tavail(j)),dsp_finish_time)
/*j:inputs cuûa node i*/
if (i in hardware)
Tstart(i)=maxj(tavail(j))
S3.4 Caäp nhaät tfinish(i)=tstart(i)+texec(i):O(1)
S3.5.if i laø trong software:
Dsp_finish_time=(dsp_finish_time>tfinish(i))?
Dsp_finish_time:tfinish(i)
S3.6.Cho moãi output k cuûa node i set tavail(k)=tfinish(i)
S3.7.Cho moãi output k cuûa node i ,truy caäp node p noái ñeán noù
S3.7.1.Giaûm baäc cuûa node p
S3.7.2.Neáu baäc cuûa p laø 0 :coäng p vaøo list cuûa nhöõng node saún saøng
S3.8.Tfinish=(Tfinish>tfinish(i))? Tfinish:tfinish(i)
}:O(A+N)
Procedure COMPUTE_LONGEST_PATH
input: G=(N,A),teff(i) cho i,i thuoäc N
output: ñöôøng ñi daøi nhaár d(i) cho i thuoäc N
khôûi taïo: bieán ñeám c=0,ñ(i)=0 cho i thuoäc N
S1.traû laïi taát caû caùc cung cuûa GRAPD
S2.thöù töï hình hoïc cuûa grapd (moät thöù töï maø cung (i,j) coù nghæa node i laø
tieàn boái cuûa node j)
S2.1 Gaùn nhaûn cho taát caû caù node vôùi thöù baäc cuûa noù:O(N)
S2.2 while (chttp:// 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;ihttp:// www.diachiweb.com
S3 phaùt sinh caïng A töø (perm[i],perm[j]),ihttp:// 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(zhttp:// 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 :
http:// www.diachiweb.com
NU =N , NM =Þ
Compute GC
Select 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 =Þ?
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
3
s
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
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= 0http:// 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= 0H
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
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 http:// www.diachiweb.com
If iÎ EXs then
xI-xsmin
EI= -0.5 * ,-0.5
