zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Phần cứng

Trộn lẫn thành phần Hardware và Software part 2

Chia sẻ: AJFGASKJHF SJHDB | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

79
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ta thấy đối với ánh xạ và thứ tự thì thời gian tính toán là hằng .Do vậy tổng dộ phức tạp của giải thuật GCLP ở mổi bước là O(N+A).giaỉ thuật chạy N lần vậy tổng thời gian là O(N.(N+A)).kiểu mẩu cho ứng dụng DSP thì A»N như vậy độ phức tạp xấu nhất của giải thuật GCLP là O(N2) 3.Phân tích độ phức tạp cuả giải thuật Bin selection procedure Độ phức tạp của giải thuật được tính toán như sau: COMPLEXITY(BIN SELECTION)...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Trộn lẫn thành phần Hardware và Software part 2

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
http:// www.diachiweb.com S3 phaùt sinh caïng A töø (perm[i],perm[j]),i
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
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 :
http:// www.diachiweb.com NU =N , NM =Þ Compute GC i Select node among 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) u 1 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 . 2 (a2) 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) 2 Hardware 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) 2 Hardware 4 5 1 3 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
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= 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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.