Áp dụng chiến lược chọn vùng và thuật toán NSGA2 cho ánh xạ các ứng dụng có thể điều chỉnh chất lượng lên nền tảng tái cấu hình NoC

70 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN NSGA2 CHO ÁNH XẠ CÁC 
 ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH CHẤT LƯỢNG LÊN NỀN TẢNG TÁI CẤU HÌNH NoC 
© 2019 Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
4. KẾT QUẢ MÔ PHỎNG VÀ THẢO LUẬN 
4.1. Thiết lập mô phỏng 
Chương trình mô phỏng được viết bằng ngôn ngữ C++ chạy trên hệ điều hành Ubuntu 14.04 64bit, Intel 
Core i5-2520M 2.5 GHz, RAM 4GB. Các nền tảng phần cứng không đồng nhất có thể cấu hình lại được 
dựa trên NoC có kích thước khác nhau lần lượt là 6x6, 7x7, 8x8, và 9x9. Mỗi nền tảng gồm một ISP và 
một số vùng cấu hình lại được. ISP có thể thực hiện được tối đa đến 6 tác vụ, trong khi vùng cấu hình lại 
được chỉ thực hiện duy nhất 1 tác vụ. Bộ dữ liệu thực hiện mô phỏng gồm 20 ứng dụng có kích thước 
khác nhau thay đổi từ 7 đến 26 tác vụ được tạo ra từ công cụ TGFF trong [22]. Để đơn giản, chúng tôi 
xem xét mỗi ứng dụng với bốn mức chất lượng (ví dụ, Qi1, Qi2, Qi3 and Qi4). Thời gian tính toán của các 
tác vụ, thời gian truyền thông giữa các cặp tác vụ được tạo ra một cách ngẫu nhiên cho mức chất lượng 
cao nhất. Đối với mức chất lượng thấp hơn, các thông số này được tạo ra từ các giá trị cao nhất theo mô 
hình chất lượng đã trình bày trong [17]. Giá trị lợi ích tại các mức chất lượng khác nhau của các ứng dụng 
cũng được tạo ta theo mô hình này. 
Kịch bản mô phỏng trên 4 nền tảng với tổng số tác vụ của các ứng dụng được ánh xạ lên nền tảng thay 
đổi từ (x*y) đến (x*y+5). Trong đó, x, y lần lượt là số hàng và số cột của nền tảng phần cứng. Mỗi kịch 
bản sẽ thực hiện thay đổi thứ tự ánh xạ các ứng dụng đi vào theo hoán vị của tổng số ứng dụng. Ví dụ, 
ánh xạ bốn ứng dụng lên nền tảng có kích thước 8x8 thì sẽ có 24 trường hợp. 
Các thông số được sử dụng trong thuật toán NSGA2 được mô tả trong Bảng 1 bao gồm kích thước quần 
thể, số thế hệ, xác suất chéo hóa, xác suất đột biến. 
Bảng 1: Thông số mô phỏng thuật toán NSGA2 
Thông số Giá trị 
Kích thước quần thể 600 
Số thế hệ 1000 
Xác suất chéo hóa 0,9 
Xác suất đột biến 0,2 
Để đánh giá tính hiệu quả của NSGA2, chúng tôi chọn hai thuật toán có liên quan đến ánh xạ đó là thuật 
toán Nearest Neighbor (NN) trong [23] và thuật toán của Chou Chen-Ling (CL) trong [19] để so sánh. 
Các thuật toán này cũng thực hiện ánh xạ các tác vụ của ứng dụng lên vùng gần lồi được tạo ra từ chiến 
lược chọn vùng NF (CVNF) trong [20] và chiến lược chọn vùng theo góc quét (SA) của chúng tôi 
(CVSA) trong [21]. Các thông số được thu thập và thống kê theo giá trị trung bình, bao gồm giá trị lợi ích 
tổng thể của các ứng dụng (OB: Overall Benefit), khoảng cách MD trung bình (AMD: Average 
Manhattan Distance), khoảng cách MD truyền thông trung bình (ACMD: Average Communication 
Manhattan Distance). 
4.2. Kết quả và đánh giá 
4.2.1. Đánh giá giá trị lợi ích tổng thể 
Giá trị lợi ích đại diện cho mức độ hài lòng của người dùng khi nhận được một mức chất lượng nhất định. 
Khi người dùng nhận được chất lượng cao nhất của một ứng dụng, giá trị lợi ích bằng 1. Chất lượng thấp 
hơn sẽ có giá trị lợi ích nhỏ hơn [18]. Do vậy, chúng tôi sử dụng thông số này để đánh giá chất lượng đạt 
được cho các ứng dụng sau khi ánh xạ. Hình 9 chỉ ra giá trị OB của các ứng dụng đạt được khi triển khai 
các ứng dụng vào nền tảng phần cứng với các kích thước lần lượt là 6x6, 7x7, 8x8, và 9x9 theo các thuật 
toán khác nhau. Trong các trường hợp, thuật toán NSGA2 cho kết quả tốt hơn so với thuật toán NN và 
CL. Cụ thể, đối với chiến lược chọn vùng SA và nền tảng có kích thước 6x6, thuật toán NSGA2 cải thiện 
giá trị lợi ích tổng thể so với thuật toán NN và CL lần lượt 34,30%, và 2,57%. Đối với chiến lược chọn 
vùng NF, thuật toán NSGA2 cải thiện giá trị lợi ích tổng thể lần lượt là 35,78%, và 29,49%, so với thuật 
toán NN, CL. 
 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN NSGA2 CHO ÁNH XẠ CÁC 71 
 ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH CHẤT LƯỢNG LÊN NỀN TẢNG TÁI CẤU HÌNH NoC 
© 2019 Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
Hình 9: Giá trị OB của các ứng dụng khi ánh xạ lên các nền tảng 
Tương tự, đối với nền tảng phần cứng có kích thước 7x7, 8x8, và 9x9, thuật toán NSGA2 tăng giá trị lợi 
ích tổng thể so với các thuật toán NN và CL trong chiến lược chọn vùng SA lần lượt là [58,92%, 
15,86%], [59,70%, 49,34%], và [66,20%, 69,25%]. Trong chiến lược chọn vùng NF, tăng lần lượt là 
[23,01%, 62,14%], [19,14%, 34,15%], và [7,60%, 10,30%]. 
Từ kết quả này, chúng ta cũng dễ thấy rằng, tùy theo chiến lược chọn vùng mà tính hiệu quả của các thuật 
toán triển khai đạt được cũng khác nhau. Cụ thể, theo chiến lược chọn vùng SA thì tính hiệu quả của thuật 
toán NSGA2 đạt được tăng dần theo kích thước nền tảng phần cứng so với các thuật toán khác. Cụ thể, 
đối với nền tảng phần cứng có kích thước 9x9, giá trị lợi ích tổng thể thuật toán NSGA2 đạt được tăng lần 
lượt 66,20% và 69,25% so với thuật toán NN và CL trong khi kích thước nền tảng phần cứng 8x8 chỉ tăng 
lần lượt 59,70% và 49,34%. Ngược lại đối với chiến lược chọn vùng NF, tính hiệu quả của thuật toán 
NSGA2 giảm dần theo chiều tăng của kích thước nền tảng phần cứng. Cụ thể, đối với nền tảng phần cứng 
có kích thước 8x8, giá trị lợi ích tổng thể thuật toán NSGA2 đạt được lần lượt 19,14% và 34,15% so với 
thuật toán NN và CL nhưng khi kích thước nền tảng phần cứng tăng lên 9x9 thì kết quả giảm xuống còn 
chỉ 7,60% và 10,31%. Điều này cũng khẳng định được rằng, ngoài thuật toán ánh xạ thì chiến lược chọn 
vùng cũng ảnh hưởng đáng kể đến kết quả ánh xạ. 
4.2.2. Đánh giá hiệu năng truyền thông 
Tiếp theo, chúng tôi đánh giá hiệu năng truyền thông cho các thuật toán qua hai thông số AMD và 
ACMD. AMD là tỉ số giữa tổng số Hop của một ứng dụng đã được ánh xạ trên tổng các cạnh trong đồ thị 
tác vụ ứng dụng. Một thuật toán ánh xạ ứng dụng có AMD nhỏ hơn thì độ trễ và tiêu thụ năng lượng sẽ 
nhỏ hơn bởi vì các gói dữ liệu đi qua số lượng Hop nhỏ hơn. ACMD đại diện cho trễ truyền thông của các 
gói tin đi qua mỗi Hop. Tương tự, ACMD nhỏ thì trễ và tiêu thụ năng lượng của mạng cũng giảm. 
Giá trị AMD và ACMD của các ứng dụng khi triển khai lên các nền tảng với kích thước khác nhau (6x6, 
7x7, 8x8 và 9x9) theo các thuật toán ánh xạ khác nhau được chỉ ra như Hình 10 và Hình 11. Các giá trị 
AMD và ACMD được cắt giảm lần lượt theo thuật toán NSGA2 và chiến lược chọn vùng SA so với thuật 
toán NN, CL cũng như chiến lược chọn vùng NF. Điều này có nghĩa rằng, thuật toán NSGA2 cho kết quả 
tốt hơn, tối ưu hơn về khoảng cách MD và giảm trễ truyền thông giữa các cặp tác vụ của ứng dụng sau 
khi ánh xạ so với các thuật toán khác. Chiến lược chọn vùng SA tạo ra các vùng có tổng khoảng cách MD 
72 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN NSGA2 CHO ÁNH XẠ CÁC 
 ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH CHẤT LƯỢNG LÊN NỀN TẢNG TÁI CẤU HÌNH NoC 
© 2019 Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
nhỏ hơn so với chiến lược chọn vùng NF. Kết quả này cho thấy, khi kết hợp giữa thuật toán NSGA2 với 
chọn vùng gần lồi sẽ giảm thiểu trễ truyền thông và tiết kiệm năng lượng cho hệ thống, cụ thể. 
Hình 10: Giá trị AMD của các ứng dụng 
Khi triển khai thuật toán NSGA2 với chiến lượt chọn vùng SA lên nền tảng có kích thước 6x6, thông số 
AMD được cắt giảm lần lượt 8,96% và 4,51% so với thuật toán NN và CL. Đối với các nền tảng 7x7, 8x8 
và 9x9 thông số này được cải thiện [13,91%, 9,26%], [17,96%, 11,59%], và [17,42%, 11,51%]. Tương tự, 
đối với chiến lược chọn vùng NF, khi thực hiện ánh xạ thuật toán NSGA2 lên các nền tảng 6x6, 7x7, 8x8 
và 9x9 thông số AMD được cắt giảm so với thuật toán NN và CL lần lượt là [16,51%, 7,56%], [11,24%, 
12,82%], [4,71%, 16,75%], và [0,63%, 12,32%]. 
Hình 11: Giá trị ACMD khi triển khai các thuật toán 
 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN NSGA2 CHO ÁNH XẠ CÁC 73 
 ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH CHẤT LƯỢNG LÊN NỀN TẢNG TÁI CẤU HÌNH NoC 
© 2019 Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
Thông số ACMD cũng được cắt giảm đáng kể khi thực hiện ánh xạ bởi thuật toán NSGA2 so với thuật 
toán NN và CL lên các chiến lược chọn vùng với các nền tảng 6x6, 7x7, 8x8 và 9x9. Cụ thể, đối với chọn 
vùng SA, thông số này lần lượt được cắt giảm [14,59%, 9,91%], [17,25%, 12,72%], [20,58%, 13,87%], 
và [19,44%, 13,30%]. Đối với chọn vùng NF, tỉ lệ phần trăm nhỏ hơn các thuật toán NN, CL là [21,47%, 
13,10%], [16,56%, 15,49%], [7,44%, 18,91%], và [2,23%, 14,18%]. 
5. KẾT LUẬN 
Trong bài báo này, chúng tôi đã đề xuất một cách tiếp cận mới để giải quyết bài toán ánh xạ các ứng dụng 
có thể điều chỉnh mức chất lên nền tảng NoC có khả năng cấu hình lại được với ràng buộc tài nguyên mà 
vẫn đảm bảo chất lượng dịch vụ tổng thể tối đa cho các ứng dụng, đó là kết hợp giữa chiến lược chọn 
vùng gần lồi và thuật toán tiến hóa đa mục tiêu NSGA2. Kết quả đạt được cho thấy giải pháp đã đề xuất 
hoàn toàn cho phép triển khai nhiều ứng dụng, các ứng dụng có kích thước lớn lên nền tảng phần cứng 
cấu hình lại được một cách linh hoạt, cải thiện chất lượng dịch vụ tổng thể của các ứng dụng sau khi triển 
khai chúng lên nền tảng phần cứng. 
LỜI CẢM ƠN 
Chúng tôi xin chân thành cảm ơn Trường Đại học Công nghiệp TP. Hồ Chí Minh vì đã hỗ trợ kinh phí để 
chúng tôi hoàn thành đề tài với mã số 182.QN01. 
TÀI LIỆU THAM KHẢO 
[1] Flasskamp Martin, Gregor Sievers, Johannes Ax, Christian Klarhorst, Thorsten Jungeblut, Wayne Kelly, Michael 
Thies, and Mario Porrmann, "Performance estimation of streaming applications for hierarchical MPSoCs", in 
Proceedings of the 2016 Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools, p. 
3,2016. 
[2] Hsiao Pei-Yung, Shih-Yu Lin, and Shih-Shinh Huang, "An FPGA based human detection system with 
embedded platform". Microelectron. Eng., vol. 138, pp. 42–46, 2015. 
[3] Kim Dong-Jin, Yeon-Jeong Ju, and Young-Seak Park, "An Implementation of SoC FPGA-based Real-time 
Object Recognition and Tracking System". IEMEK J. Embed. Syst. Appl., vol. 10, no. 6, pp. 363–372, 2015. 
[4] Leibo L I U, WANG Dong, CHEN Yingjie, Z H U Min, Y I N Shouyi, and W E I Shaojun, "An Implementation 
of Multiple-Standard Video Decoder on a Mixed-Grained Reconfigurable Computing Platform". IEICE Trans. Inf. 
Syst., vol. 99, no. 5, pp. 1285–1295, 2016. 
[5] Luo Junwen, Graeme Coapes, Terrence Mak, Tadashi Yamazaki, Chung Tin, and Patrick Degenaar, "Real-Time 
Simulation of Passage-of-Time Encoding in Cerebellum Using a Scalable FPGA-Based System". IEEE Trans. 
Biomed. Circuits Syst., vol. 10, no. 3, pp. 742–753, 2016. 
[6] Benini Luca and Giovanni De Micheli, "Networks on chips: a new SoC paradigm". Computer (Long. Beach. 
Calif), vol. 35, no. 1, pp. 70–78, 2002. 
[7] Pang Ke, Virginie Fresse, Suying Yao, and Otavio Alcantara De Lima, "Task mapping and mesh topology 
exploration for an FPGA-based network on chip". Microprocess. Microsyst., vol. 39, no. 3, pp. 189–199, 2015. 
[8] Abdelfattah Mohamed S, Andrew Bitar, and Vaughn Betz, "Take the highway: Design for embedded NoCs on 
FPGAs", in Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 
pp. 98–107, 2015. 
74 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN NSGA2 CHO ÁNH XẠ CÁC 
 ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH CHẤT LƯỢNG LÊN NỀN TẢNG TÁI CẤU HÌNH NoC 
© 2019 Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
[9] Kumar Rakesh, Dean M Tullsen, Parthasarathy Ranganathan, Norman P Jouppi, and Keith I Farkas, "Single-
ISA heterogeneous multi-core architectures for multithreaded workload performance". ACM SIGARCH Comput. 
Archit. News, vol. 32, no. 2, p. 64, 2004. 
[10] Nguyen Van Cuong, Nguyen Trong Bang, Le Dinh Tuyen, Pham Ngoc Nam, “Dynamic Mapping of Quality 
Adjustable Applications on NoC-based Reconfigurable Platforms”, in The 2016 International Conference on 
Advanced Technologies for Communications (ATC), Hanoi, Vietnam, pp. 321–326, 2016. 
[11] Vinícius, M., da Silva, C., Nedjah, N., & de Macedo Mourelle, L., “Optimal ip assignment for efficient noc-
based system implementation using nsga-ii and microga”. International Journal of Computational Intelligence 
Systems, 2(2), pp. 115-123, 2009. 
[12] Ngoc N Pham, W van Raemdonck, Gauthier Lafruit, Geert Deconinck, and Rudy Lauwereins, "A qos 
framework for interactive 3d applications", in 10th Int. Conf. in Central Europe on Computer Graphics, 
Visualization and Computer Vision (WSCG-2002), pp. 317–325, 2002. 
[13] Le Hung T, Hai N Nguyen, Nam Pham Ngoc, Anh T Pham, Hoa Le Minh, and Truong Cong Thang, "Quality-
driven bitrate adaptation method for HTTP live-streaming", in 2015 IEEE International Conference on 
Communication Workshop (ICCW), pp. 1771–1776, 2015. 
[14] Ghanbari M, D Crawford, M Fleury, E Khan, J Woods, H Lu, and R Razavi, "Future performance of video 
codecs". Video Netw. Lab. (November 2006), 2006. 
[15] Wiegand Thomas, Heiko Schwarz, Anthony Joch, Faouzi Kossentini, and Gary J Sullivan, "Rate-constrained 
coder control and comparison of video coding standards". IEEE Trans. circuits Syst. video Technol., vol. 13, no. 7, 
pp. 688–703, 2003. 
[16] Davis Don, Srinivas Beeravolu, and Ranjesh Jaganathan, "Hardware/Software Codesign for platforms FPGA". 
Xilinx Inc, 2005. 
[17] Ngoc N Pham, G Lafruit, S Vernalde, and R Lauwereins, "Real-Time 3D Applications on Mobile Platforms 
With Run-Time Reconfigurable Hardware Accelerator", pp. 25–29, 2002. 
[18] Ngoc Nam Pham, Gauthier Lafruit, Geert Deconinck, and Rudy Lauwereins, "A fast QoS adaptation algorithm 
for MPEG-4 multimedia applications", in International Workshop on Interactive Distributed Multimedia Systems 
and Telecommunication Services, pp. 92–105, 2002. 
[19] Chou Chen-Ling and Radu Marculescu, "User-aware dynamic task allocation in networks-on-chip", in 2008 
Design, Automation and Test in Europe, pp. 1232–1237, 2008. 
[20] Chou Chen Ling, Umit Y. Ogras, and Radu Marculescu, "Energy- and performance-aware incremental 
mapping for networks on chip with multiple voltage levels". IEEE Trans. Comput. Des. Integr. Circuits Syst., vol. 
27, no. 10, pp. 1866–1879, 2008. 
[21] Nguyen Van Cuong, Le Dinh Tuyen, Dao Vu Tuan, Tran Thanh Hai, Pham Ngoc Nam, “Heuristics for 
Dynamic Mapping of Quality Adjustable Applications on NoC-based Reconfigurable Platforms”, The Journal of 
Science & Technology of Technical Universities, 2017. 
[22] Dick Robert P, David L Rhodes, and Wayne Wolf, "TGFF: task graphs for free", in Proceedings of the 6th 
international workshop on Hardware/software codesign, pp. 97–101, 1998. 
 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN NSGA2 CHO ÁNH XẠ CÁC 75 
 ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH CHẤT LƯỢNG LÊN NỀN TẢNG TÁI CẤU HÌNH NoC 
© 2019 Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
[23] Carvalho Ewerson, Ney Calazans, and Fernando Moraes, "Heuristics for dynamic task mapping in NoC-based 
heterogeneous MPSoCs", in 18th IEEE/IFIP International Workshop on Rapid System Prototyping (RSP’07), pp. 
34–40, 2007. 
Ngày nhận bài:24/10/2018 
Ngày chấp nhận đăng:10/02/2019