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

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

1. 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á.
2. 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 hard ware ,s oftware CPLEX (ILP) ( h w / s w p a rtitioning) 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â p h oû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).
3. 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).
4. 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 /Sof t w a r e mapp i ng and scheduli n g + 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ù :
5. 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 .
6. 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 .
7. 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
8. 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
9. 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
10. 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 (c<N) { S2.2.1. ñònh danh moät node i vôùi thöù baäc =0 S2.2.2. gaùn nhaûn i vôùi c S2.2.3. giaûm baäc cuaû taát caû caùc node noái ñeán i S2.2.4. xoùa node i vaø taát caû caùc cung baét nguoàn töø i S2.2.5. c=c+1 }:O(A) S3.phuû nhaän thôøi gian thöïc thi hieäu quaû cuûa taát caû caùc node i thuoäc N.(teff(i)=(-1).teff(i)):O(N) S4.duyeät graph trong thöù töï hình hoïc:O(A) S4.1. d(i)=min(d(i))+teff(i) maø j thuoäc tieàn boái cuûa i S4.2. phuû ñònh d(i) cho ñöôøng ñi daøi nhaát cho moãi i,i thuoäc N:O(N)