Tài liệu Nghiên cứu NoC cấu hình lại được trên FPGA và phát triển thuật toán ánh xạ động ứng dụng trên nền tảng NoC

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN VĂN CƢỜNG NGHIÊN CỨU NoC CẤU HÌNH LẠI ĐƢỢC TRÊN FPGA VÀ PHÁT TRIỂN THUẬT TOÁN ÁNH XẠ ĐỘNG ỨNG DỤNG TRÊN NỀN TẢNG NoC LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐIỆN TỬ Hà Nội – 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN VĂN CƢỜNG NGHIÊN CỨU NoC CẤU HÌNH LẠI ĐƢỢC TRÊN FPGA VÀ PHÁT TRIỂN THUẬT TOÁN ÁNH XẠ ĐỘNG ỨNG DỤNG TRÊN NỀN TẢNG NoC Chuyên ngành: Kỹ thuật điện tử Mã số: 62520203 LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐIỆN TỬ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. PHẠM NGỌC NAM Hà Nội – 2017 i LỜI CAM ĐOAN Tôi xin cam đoan rằng các kết quả khoa học được trình bày trong quyển luận án này là kết quả nghiên cứu của bản thân tôi trong suốt thời gian làm nghiên cứu sinh và chưa từng xuất hiện trong công bố của các tác giả khác. Các kết quả nghiên cứu là chính xác và trung thực. Giáo viên hướng dẫn Hà Nội, ngày 08 tháng 05 năm 2017 Tác giả PGS. TS. Phạm Ngọc Nam Nguyễn Văn Cường ii LỜI CẢM ƠN Đầu tiên, tôi xin bày tỏ lời cảm ơn sâu sắc và kính trọng đến thầy giáo PGS. TS. Phạm Ngọc Nam, người đã hướng dẫn và định hướng khoa học cho tôi trong suốt khóa học. Cảm ơn các thành viên nhóm NoC của Lab ESRC đã hỗ trợ và cùng tôi thực hiện một số thí nghiệm trong luận án này. Tôi xin trân trọng cảm ơn Ban Lãnh đạo, quý thầy cô và cán bộ, chuyên viên trong Viện Điện tử Viễn thông, Bộ môn Điện tử và Kỹ thuật máy tính và Viện Đào tạo Sau Đại học đã tạo các điều kiện thuận lợi về nơi học tập, nghiên cứu, các thủ tục hành chính và góp ý chuyên môn cho tôi trong suốt quá trình học tập và nghiên cứu tại trường Đại học Bách khoa Hà Nội. Tôi cũng xin trân trọng cảm ơn Ban Giám hiệu trường Đại học Công nghiệp Tp.HCM, Ban Lãnh đạo và đồng nghiệp của tôi tại Phân hiệu Quảng Ngãi đã tạo các điều kiện thuận lợi về thời gian để tôi học tập và nghiên cứu tại trường Đại học Bách khoa Hà Nội. Xin cảm ơn các nghiên cứu sinh đã quan tâm và động viên tôi trong suốt khóa học. Cuối cùng, tôi xin bày tỏ lòng biết ơn đến gia đình, đặc biệt là vợ và các con của tôi. Những người đã luôn động viên và giúp đỡ tôi trong suốt thời gian vừa qua. Đây cũng là động lực lớn nhất để tôi vượt qua các khó khăn và hoàn thành luận án này. Tác giả iii MỤC LỤC LỜI CAM ĐOAN ............................................................................................................................. i LỜI CẢM ƠN ................................................................................................................................. ii MỤC LỤC ............................................................................................................................... iii DANH MỤC CÁC TỪ VIẾT TẮT ..............................................................................................vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ......................................................................................... x DANH MỤC CÁC BẢNG BIỂU ..................................................................................................xii MỞ ĐẦU ................................................................................................................................. 1 1. Đặt vấn đề .................................................................................................................... 1 2. Mục tiêu, đối tượng, phương pháp và phạm vi nghiên cứu ....................... 3 3. Các kết quả đạt được của luận án ....................................................................... 5 4. Cấu trúc của luận án................................................................................................. 6 CHƯƠNG 1 CƠ SỞ LÝ THUYẾT ............................................................................................. 7 1.1. Lý thuyết về mạng trên chip.................................................................................. 7 1.1.1. Nguồn gốc và thuật ngữ .....................................................................................................7 1.1.2. Cấu hình mạng ........................................................................................................................8 1.1.2.1. Mạng lưới n-chiều (n-Dimensional Mesh)................................................9 1.1.2.2. Mạng K-ary n-cube ..............................................................................................9 1.1.2.3. Mạng có số chiều thấp ..................................................................................... 10 1.1.3. Cơ chế điều khiển luồng .................................................................................................. 10 1.1.3.1. Bản tin .................................................................................................................... 10 1.1.3.2. Cơ chế điều khiển luồng Store-and-Forward (SAF) .......................... 11 1.1.3.3. Cơ chế điều khiển luồng Wormhole (WH)............................................. 11 1.1.3.4. Cơ chế điều khiển luồng Virtual cut-through (VCT) ......................... 12 1.1.3.5. Cơ chế điều khiển luồng kênh ảo (Virtual Channel) ......................... 12 1.1.4. Thuật toán định tuyến ..................................................................................................... 13 1.1.4.1. Phân loại định tuyến ........................................................................................ 13 1.1.4.2. Các vấn đề trong định tuyến......................................................................... 14 1.1.5. Tổng quan kiến trúc bộ định tuyến............................................................................ 14 1.2. Công nghệ FPGA...................................................................................................... 16 iv 1.2.1. Kiến trúc FPGA .................................................................................................................... 17 1.2.1.1. Tổng quan kiến trúc FPGA ............................................................................ 17 1.2.1.2. Kiến trúc FPGA của Xilinx .............................................................................. 18 1.2.2. Cấu hình lại từng phần ..................................................................................................... 19 1.2.2.1. Cấu hình lại từng phần động ........................................................................ 21 1.2.2.2. Các ưu điểm của cấu hình lại từng phần ................................................. 22 1.2.2.3. Hỗ trợ cấu hình lại trong FPGA của Xilinx ............................................. 23 1.3. Kỹ thuật ánh xạ ứng dụng lên nền tảng mạng trên chip .......................... 24 1.3.1. Bài toán ánh xạ .................................................................................................................... 24 1.3.2. Ánh xạ tại thời gian thiết kế .......................................................................................... 25 1.3.3. Ánh xạ tại thời gian chạy ................................................................................................ 26 1.4. Kết luận chương..................................................................................................... 26 CHƯƠNG 2 PHÁT TRIỂN NỀN TẢNG PHẦN CỨNG CẤU HÌNH LẠI ĐƯỢC CHO NoC 2.1. .............................................................................................................................. 28 Thiết kế bộ định tuyến cho NoC ........................................................................ 28 2.1.1. Giới thiệu................................................................................................................................ 28 2.1.2. Đề xuất kiến trúc bộ định tuyến .................................................................................. 29 2.1.2.1. Lựa chọn các thông số thiết kế .................................................................... 29 2.1.2.2. Bộ đệm ngõ vào .................................................................................................. 32 2.1.2.3. Bộ giải mã flit....................................................................................................... 32 2.1.2.4. Chuyển mạch và kênh ảo ............................................................................... 33 2.1.2.5. Bộ phân xử............................................................................................................ 34 2.1.3. Kết quả và đánh giá ........................................................................................................... 34 2.1.3.1. Kết quả tổng hợp ............................................................................................... 35 2.1.3.2. Kết quả mô phỏng ............................................................................................. 36 2.2. Thiết kế bộ giao tiếp mạng cho NoC ................................................................ 40 2.2.1. Giới thiệu................................................................................................................................ 40 2.2.2. Phương pháp tiếp cận ...................................................................................................... 40 2.2.3. Đề xuất kiến trúc bộ giao tiếp mạng .......................................................................... 42 2.2.4. Kết quả và đánh giá ........................................................................................................... 44 2.3. Phát triển nền tảng phần cứng cấu hình lại từng phần động ................. 45 2.3.1. Giới thiệu................................................................................................................................ 45 v 2.3.2. Xây dựng hệ thống (nền tảng phần cứng) cấu hình ........................................... 47 2.3.2.1. Luồng thiết kế ..................................................................................................... 47 2.3.2.2. Thiết lập hệ thống ............................................................................................. 48 2.3.3. Các trường hợp nghiên cứu........................................................................................... 50 2.3.3.1. Cấu hình lại cơ sở hạ tầng truyền thông ................................................. 50 2.3.3.2. Cấu hình lại các PE ............................................................................................ 53 2.3.4. Kết quả thực nghiệm ........................................................................................................ 54 2.4. Kết luận chương..................................................................................................... 56 CHƯƠNG 3 TRIỂN KHAI CÁC ỨNG DỤNG CÓ THỂ ĐIỀU CHỈNH MỨC CHẤT LƯỢNG VÀO NỀN TẢNG CẤU HÌNH LẠI ĐƯỢC DỰA TRÊN NoC TẠI THỜI GIAN CHẠY .............................................................................................................................. 57 3.1. Giới thiệu .................................................................................................................. 57 3.2. Mô tả bài toán ánh xạ............................................................................................ 59 3.3. Các định nghĩa và xây dựng bài toán ánh xạ ................................................ 60 3.3.1. Mô hình ứng dụng .............................................................................................................. 60 3.3.1.1. Đồ thị tác vụ ứng dụng .................................................................................... 61 3.3.1.2. Mô hình chất lượng .......................................................................................... 61 3.3.2. Mô hình phần cứng ............................................................................................................ 62 3.3.3. Xây dựng bài toán ánh xạ ............................................................................................... 63 3.4. Các giải pháp cho bài toán ánh xạ các ứng dụng lên NoC tại thời gian chạy ................................................................................................................................ 65 3.4.1. Giải pháp tối ưu sử dụng thuật toán tìm kiếm đầy đủ ...................................... 66 3.4.1.1. Thuật toán ............................................................................................................ 66 3.4.1.2. Kết quả mô phỏng và đánh giá .................................................................... 67 3.4.2. Giải pháp heuristic cho bài toán ánh xạ tại thời gian chạy ............................. 70 3.4.2.1. Chiến lược chọn vùng gần lồi....................................................................... 70 3.4.2.2. Thuật toán ánh xạ heuristic .......................................................................... 73 3.4.2.3. Kết quả mô phỏng và đánh giá .................................................................... 75 3.5. Kết luận chương..................................................................................................... 82 KẾT LUẬN .............................................................................................................................. 83 Nội dung và các kết quả đạt được của luận án.......................................................... 83 Đóng góp khoa học của luận án...................................................................................... 84 vi Hướng phát triển của luận án ........................................................................................ 85 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN ........................................ 86 TÀI LIỆU THAM KHẢO ........................................................................................................... 87 vii DANH MỤC CÁC TỪ VIẾT TẮT Ký hiệu ABP ACMD Nghĩa tiếng Anh của từ viết tắt Adaptive BackPressure Average Communication Manhattan Distance AMD Average Manhattan Distance ARM ATG AXI C2R CAGR CF CLB CMPS CPU DDR Advanced RISC Machine Application-Specific Integrated Circuit Application Task Graph Advanced eXtensible Interface Core to Router Compound Annual Growth Rate CompactFlash Configurable Logic Block Chip Multi-Processors Central Processing Unit Double Data Rate DDRAM Double Data Rate RAM DMA DP DPR DSP DT EDK FF FFT FIFO Direct Memory Access Dynamic Part Dynamic Partial Reconfigurable Digital Signal Processor Design-time Embedded Development KIT First Fit Fast Fourier Transform First In First Out FPGA Field Programmable Gate Array FT Flit Type GPIO General Purpose Input Output HDL Hardware Description Language ASIC HTTP-VS HTTP video streaming HW/SW Hardware/Software Nghĩa tiếng Việt Khoảng cách Manhattan truyền thông trung bình Khoảng cách Manhattan trung bình Vi xử lý ARM Vi mạch tích hợp chuyên dụng Đồ thị tác vụ ứng dụng Giao diện mở rộng tiên tiến Từ lõi IP đến bộ định tuyến Tốc độ tăng trưởng kép hàng năm Bộ nhớ flash Khối Logic cấu hình Chip đa xử lý Đơn vị xử lý trung tâm Tốc độ dữ liệu kép Bộ nhớ truy cập ngẫu nhiên tốc độ dữ liệu kép Truy nhập bộ nhớ trực tiếp Phần động Cấu hình lại từng phần động Xử lý tín hiệu số Thời gian thiết kế Bộ công cụ phát triển nhúng Thuật toán ánh xạ first fit Biến đổi Fourier nhanh Vào trước ra trước Mảng các cổng có thể lập trình tại chỗ Loại flit Các giao tiếp vào ra mục đích chung Ngôn ngữ mô tả phần cứng Truyền tải video qua giao thức http Phần cứng/Phần mềm viii Ký hiệu IC Nghĩa tiếng Anh của từ viết tắt Integrated Circuit ICAP Internal Configuration Access Port InP IP ISE ISP JTAG LCD LE LUT MD MPEG-4 MPSoC MWD NI Indefinite Postponement Intellectual Property (IP Core) Integrated Software Environment Instruction Set Processor Joint Test Action Group Cable Liquid Crystal Display Logic Element Logic Look-up Table Manhattan Moving Picture Experts Group Multiprocessor System on Chip Multi-Window Display Network Interface NN Nearest Neighbor NoC OB PC PCB PE PIP PL PLB PLD PR QoS R2C RAM RI RPA RR RT RTL SAF Network-on-Chip Overall Benefit Personal Computer Printed circuit board Processing Element Picture In Picture Programmable Logic Processor Local Bus Programmable Logic Device Partial Reconfiguration Quality of service Router to Core Random Access Memory Routing Information Reprogrammability Reconfigurable Region Run-time Register Transfer Level Store-And-Forward SDK Software Development KIT SN Sequence Number Nghĩa tiếng Việt Mạch tích hợp Cổng truy nhập cấu hình bên trong Trì hoãn không xác định Lõi sở hữu trí tuệ Môi trường phần mềm tích hợp Vi xử lý tập lệnh Cáp JTAG Màn hình tinh thể lỏng Phần tử logic Bảng tra logic Khoảng cách Manhattan Hệ thống đa xử lý trên chip Bộ giao tiếp mạng Thuật toán ánh xạ nearest neighbor Mạng trên chip Giá trị lợi ích tổng thể Máy tính cá nhân Bảng mạch in Phần tử xử lý (tính toán) Logic lập trình Thiết bị logic khả trình Cấu hình lại được từng phần Chất lượng dịch vụ Từ bộ định tuyến đến lõi IP Bộ nhớ truy cập ngẫu nhiên Thông tin định tuyến Khả năng lập trình lại Vùng cấu hình lại được Thời gian chạy Mức truyền thanh ghi Bộ công cụ phát triển phần mềm của Xilinx Số thứ tự ix Ký hiệu SoC SOF SP SRAM Nghĩa tiếng Anh của từ viết tắt System-on-Chip System-on-an-FPGA Static Part Static Random Access Memory TGFF Task Graphs For Free VLSI WH Universal Asynchronous Receiver/Transmitter Virtual Channel Virtual Cut-Through VHSIC Hardware Description Language Very High Speed Integrated Circuit Very-large-scale integration Wormhole XPS Xilinx Platform Studio UART VC VCT VHDL VHSIC Nghĩa tiếng Việt Hệ thống trên chip Hệ thống trên một FPGA Phần tĩnh Bộ nhớ truy cập ngẫu nhiên tĩnh Công cụ tạo đồ thị tác vụ miễn phí Bộ truyền nhận nối tiếp không đồng bộ Kênh ảo Ngôn ngữ mô tả phần cứng VHSIC Mạch tích hợp tốc độ rất cao Mạch tích hợp rất cao Chuyển mạch lỗ sâu Bộ công cụ xây dựng phần cứng hệ thống nhúng của Xilinx x DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Trang Hình 1. Các ưu điểm của FPGA hiện đại [89] ........................................................................... 3 Hình 1.1. Cấu trúc của một NoC dạng lưới 3x3........................................................................... 8 Hình 1.2. Phân loại cấu hình mạng NoC ......................................................................................... 9 Hình 1.3. Mạng lưới n-chiều ................................................................................................................ 9 Hình 1.4. Mạng k-ary n-cube .............................................................................................................10 Hình 1.5. Mạng hai chiều mesh và torus ......................................................................................10 Hình 1.6. Cơ chế điều khiển luồng SAF và WH .........................................................................11 Hình 1.7. Phân loại các thuật toán định tuyến trong NoC ...................................................13 Hình 1.8. Kiến trúc tổng quát của một bộ định tuyến [7] ....................................................15 Hình 1.9. Thị trường cung cấp FPGA bởi các nhà sản xuất [78] .......................................16 Hình 1.10. Quy mô thị trường ứng dụng của FPGA khu vực Châu Á Thái Bình Dương [42] ............................................................................................................................17 Hình 1.11. Kiến trúc chung của FPGA ..............................................................................................17 Hình 1.12. Một Slice của FPGA Xilinx Virtex-6 [95] ..................................................................19 Hình 1.13. Minh họa thiết kế cấu hình lại từng phần ...............................................................20 Hình 1.14. Quy trình thực hiện cấu hình từng phần cho FPGA [97] ..................................21 Hình 1.15. Tổng quan cấu hình lại từng phần động và bộ nhớ cấu hình [77] ...............23 Hình 2.1. Bộ định tuyến .......................................................................................................................30 Hình 2.2. Cấu trúc của các flit ...........................................................................................................30 Hình 2.3. Kiến trúc bộ định tuyến đề xuất ..................................................................................30 Hình 2.4. Sơ đồ khối của bộ đệm ngõ vào ...................................................................................32 Hình 2.5. Sơ đồ khối bộ giải mã flit ................................................................................................32 Hình 2.6. Thuật toán XY.......................................................................................................................33 Hình 2.7. Cấu trúc của chuyển mạch .............................................................................................33 Hình 2.8. Bộ phân xử 2:1.....................................................................................................................34 Hình 2.9. Bộ phân xử 4:1.....................................................................................................................34 Hình 2.10. Kết quả mô phỏng RTL cho các kịch bản.................................................................37 Hình 2.11. Trễ trung bình toàn mạng ..............................................................................................38 Hình 2.12. Thông lượng trung bình toàn mạng ..........................................................................38 Hình 2.13. Quá trình ghi/đọc dữ liệu vào/ra bộ đệm đơn .....................................................41 Hình 2.14. Quá trình ghi/đọc dữ liệu vào/ra bộ đệm kép .....................................................41 Hình 2.15. Kiến trúc tổng quát của bộ giao tiếp mạng .............................................................42 xi Hình 2.16. Biểu đồ thời gian truyền các gói tin từ tài nguyên đến bộ định tuyến ......45 Hình 2.17. Mô hình kiến trúc cấu hình trên FPGA .....................................................................46 Hình 2.18. Sơ đồ luồng thiết lập hệ thống .....................................................................................47 Hình 2.19. Sơ đồ khối tổng quát của hệ thống .............................................................................48 Hình 2.20. Thiết lập phần cứng trên công cụ XPS ......................................................................49 Hình 2.21. Phân chia khu vực cấu hình các bộ đệm ngõ vào trong bộ định tuyến của NoC ...................................................................................................................................50 Hình 2.22. Lưu đồ thuật toán điều khiển quá trình cấu hình ...............................................52 Hình 2.23. Phân chia khu vực cấu hình lại bộ định tuyến hoặc topo mạng 2x2 của NoC ...................................................................................................................................53 Hình 2.24. Mô hình cấu hình lại các PE trong mạng 2x2 ........................................................54 Hình 2.25. Vị trí vật lý của các thành phần trong hệ thống theo các kịch bản khác nhau ...............................................................................................................................55 Hình 3.1. Ví dụ mô tả bài toán ánh xạ ...........................................................................................59 Hình 3.2. Ảnh hưởng của dữ liệu đến chất lượng video [33, 91] .....................................60 Hình 3.3. Mô hình hệ thống ...............................................................................................................63 Hình 3.4. Đồ thị tác vụ của ứng dụng A6 và ứng dụng MPEG-4 .........................................66 Hình 3.5. Vị trí đặt các tác vụ vào nền tảng phần cứng sau khi ánh xạ ..........................68 Hình 3.6. Minh họa quá trình ánh xạ của thuật toán heuristic đã đề xuất ...................74 Hình 3.7. So sánh lợi ích chi phí theo các thuật toán ánh xạ ..............................................74 Hình 3.8. Giá trị lợi ích tổng thể của các ứng dụng đã được ánh xạ lên kích thước mạng 5x5 ..................................................................................................................76 Hình 3.9. Giá trị lợi ích tổng thể của các ứng dụng đã được ánh xạ lên kích thước mạng 6x6 ..................................................................................................................77 Hình 3.10. Giá trị lợi ích tổng thể của các ứng dụng đã được ánh xạ lên kích thước mạng 7x7 ..................................................................................................................77 Hình 3.11. Giá trị AMD của các ứng dụng đã được ánh xạ theo các thuật toán khác nhau ...............................................................................................................................79 Hình 3.12. Giá trị ACMD của các ứng dụng đã được ánh xạ theo các thuật toán .........80 Hình 3.13. Các cải thiện trong chiến lược chọn vùng của tác giả ........................................82 xii DANH MỤC CÁC BẢNG BIỂU Trang Bảng 2.1. Các thông số mô phỏng....................................................................................................35 Bảng 2.2. Tài nguyên sử dụng của các bộ định tuyến trên FPGA .....................................35 Bảng 2.3. Một vài so sánh tham khảo với kiến trúc bộ định tuyến đã đề xuất ...........39 Bảng 2.4. Kết quả tổng hợp trên FPGA .........................................................................................44 Bảng 2.5. Tốc độ hoạt động của các bộ giao tiếp mạng .........................................................44 Bảng 2.6. Tài nguyên sử dụng của các hệ thống cấu hình ....................................................55 Bảng 2.7. Thời gian và tốc độ cấu hình của các kịch bản ......................................................56 Bảng 3.1. Các ứng dụng tổng hợp được tạo ra từ TGFF và các ứng dụng thực ..........65 Bảng 3.2. Giá trị lợi ích tại mỗi mức chất lượng .......................................................................67 Bảng 3.3. Kết quả mô phỏng của các kịch bản ánh xạ ............................................................69 Bảng 3.4. Chất lượng và giá trị lợi ích của các ứng dụng ......................................................78 Bảng 3.5. Giá trị AMD khi ánh xạ các ứng dụng lên nền tảng 5x5, 6x6 và 7x7 ...........78 Bảng 3.6. Giá trị ACMD khi ánh xạ các ứng dụng lên nền tảng 5x5, 6x6 và 7x7 ........79 Bảng 3.7. Thời gian chạy trung bình của các chiến lược chọn vùng ...............................81 1 MỞ ĐẦU 1. Đặt vấn đề Ngày nay, các thiết bị nhúng đang trở nên quan trọng trong cuộc sống của chúng ta (ví dụ: điện thoại thông minh, các thiết bị di động). Khi thiết kế hệ thống nhúng, người thiết kế cần xem xét kỹ lưỡng các tiêu chí ràng buộc như hiệu năng, thời gian đưa sản phẩm ra thị trường, tiêu thụ năng lượng, kích thước thực hiện, khả năng nâng cấp, cập nhật các ứng dụng và các tính năng mới trong tương lai, v.v. Bên cạnh đó, các ứng dụng đa phương tiện tiên tiến như HD-video, xử lý ảnh, các trò chơi 3D, v.v. luôn yêu cầu một sức mạnh tính toán lớn và chuyển tải dữ liệu nhanh. Các ứng dụng này được thiết kế theo cách mà mức chất lượng của chúng có thể được điều chỉnh phù hợp với khả năng xử lý của nền tảng phần cứng [52, 70]. Ví dụ khi xem video trên Internet, tùy thuộc vào băng thông của mạng cũng như khả năng xử lý của thiết bị mà người dùng có thể xem được video ở mức chất lượng HD hoặc SD, v.v. Thêm vào đó, các ứng dụng được mô hình hóa dưới dạng đồ thị tác vụ với số lượng lớn các tác vụ truyền thông và các đặc tính khác nhau do vậy yêu cầu xử lý song song các tác vụ này là rất cao. Một yếu tố khác đó là hành vi của người sử dụng thiết bị luôn thay đổi theo thời gian như nghe nhạc, xem phim hoặc chơi trò chơi, v.v. Theo các yêu cầu này, chúng ta dễ thấy rằng các ứng dụng được đưa vào và rời khỏi hệ thống tại bất kỳ thời điểm nào. Thứ tự các ứng dụng được đưa vào và rời hệ thống cũng không thể biết trước. Ngoài ra, mức chất lượng của các ứng dụng cũng có thể bị thay đổi theo hành vi của người dùng hoặc theo tình trạng tài nguyên sẵn có của thiết bị (ví dụ: yêu cầu mức chất lượng, hiệu năng cho từng ứng dụng). Do vậy, việc phát triển các nền tảng phần cứng có nhiều khả năng linh hoạt và khả năng thích nghi với các yêu cầu như trên là hết sức cần thiết. Một xu hướng mới trong thiết kế các nền tảng tiên tiến đó là tạo ra một nền tảng có thể tái cấu hình các mô đun vật lý sau khi chế tạo, kết hợp giữa bộ vi xử lý và các thiết bị cấu hình lại [90], chẳng hạn như FPGA (Field Programmable Gate Array), để tăng thêm tính linh hoạt cho hệ thống trong các môi trường khác nhau [63]. Tuy nhiên, khả năng của các phần tử cấu hình lại trong thiết bị luôn có giới hạn. Do vậy, cần lựa chọn thêm một giải pháp quản lý động cho hệ thống. Một trong những giải pháp quan trọng và rất linh hoạt đó là kỹ thuật ánh xạ ứng dụng động. Kỹ thuật này kết hợp với khả năng cấu hình lại từng phần động của thiết bị phần cứng như FPGA sẽ tạo ra một giải pháp hứa hẹn để giải quyết yêu cầu triển khai nhiều ứng dụng có thể điều chỉnh được mức chất lượng lên nền tảng có tài nguyên tái cấu hình hạn chế [8, 86]. Hơn nữa, do độ phức tạp của các thiết bị nhúng hiện đại ngày càng tăng, một số lượng ngày càng nhiều ứng dụng với chất lượng dịch vụ (QoS: Quality of Service) khác nhau có 2 thể được triển khai lên thiết bị, thường là trong một môi trường các nền tảng cấu hình lại không đồng nhất. Bởi vì một nền tảng cấu hình lại không đồng nhất với sự linh hoạt của các bộ xử lý nhúng và hiệu quả tính toán của một số vùng cấu hình lại đã được chứng minh là có nhiều ưu điểm hơn so với nền tảng đồng nhất [1, 49]. Trong một nền tảng như vậy, các bộ xử lý nhúng thường được sử dụng để quản lý và thực hiện một số tác vụ phức tạp thấp trong khi các vùng cấu hình lại được sử dụng để tăng tốc độ tính toán cho các tác vụ phức tạp. Khả năng cấu hình động cho phép nền tảng thích nghi với các yêu cầu xử lý thay đổi của các ứng dụng. Mặt khác, các yêu cầu truyền thông ngày càng gia tăng trong một hệ thống trên chip (SoC: System on Chip) phức tạp như nền tảng đa lõi không đồng nhất cấu hình lại được. Do vậy việc lựa chọn một cơ sở hạ tầng truyền thông phù hợp là cần thiết. Điều này phải đảm bảo các kết nối cần thiết với một QoS được xác định trước, chẳng hạn như thông lượng hoặc trễ tối đa. Tuy nhiên, trong nhiều trường hợp mức ưu tiên của các ứng dụng chưa được biết trước tại lúc thiết kế mà chỉ biết được khi chúng được triển khai vào hệ thống tại thời gian chạy. Trong trường hợp này, các yêu cầu truyền thông hiệu quả không được biết đến tại thời gian tổng hợp, do đó một cơ sở hạ tầng truyền thông linh hoạt sẽ được lựa chọn. Hơn nữa, một SoC phức tạp còn yêu cầu tích hợp một số lượng lớn các lõi IP (Intellectual Property) lên nó, vì vậy, một cơ sở hạ tầng truyền thông hiệu năng cao, khả năng xử lý song song để kết nối các IP khác nhau cần được sử dụng. Với yêu cầu này, các kiến trúc truyền thống như Bus chia sẻ hay kết nối trực tiếp điểm-điểm không thể áp dụng được. Kiến trúc mạng trên chip (NoC: Network on Chip) ra đời và xem như một giải pháp thay thế cho kiến trúc Bus và kết nối điểm-điểm theo hướng công nghệ này. Kiến trúc NoC cung cấp một cơ sở hạ tầng truyền thông có hiệu năng cao, có khả năng mở rộng và khả năng xử lý song song cao, thích hợp cho việc tích hợp một số lượng lớn các lõi IP lên một SoC [9,50]. Do vậy, NoC được đề xuất như là một giải pháp cho truyền thông giữa các IP trong thiết kế các SoC phức tạp. Ngoài ra, hầu hết các nền tảng phần cứng SoC hiện nay được chế tạo trên công nghệ ASIC (Application-Specific Integrated Circuit) đó là một dạng thiết kế tĩnh, có nghĩa là các IP, hạ tầng truyền thông và các thiết bị ngoại vi không thể thay đổi sau khi sản phẩm được chế tạo. Do vậy chúng khó có thể đáp ứng được các yêu cầu cho khả năng thích nghi, thay đổi một số mô đun hay sửa lỗi sau khi chế tạo. Để phát triển một nền tảng SoC dạng ASIC cần phải có quỹ thời gian dài và chi phí khá cao khi yêu cầu thiết kế với số lượng sản phẩm không lớn. Điều này rõ ràng bất lợi và không phù hợp với các yêu cầu như: Thời gian thiết kế sản phẩm mẫu ngắn, số lượng sản phẩm nhỏ, sản phẩm có độ linh hoạt và thích nghi cao. Các hạn chế này có thể được khắc phục bằng công nghệ FPGA. Một trong những tính năng đặc biệt của một FPGA hiện đại là khả năng cấu hình lại và 3 cấu hình lại từng phần động. Với khả năng này, FPGA có thể thay đổi nhiều lần và thay đổi động các chức năng đã thực hiện trên các thiết bị vật lý của nó ngay khi đang còn hoạt động. Do đó, FPGA được lựa chọn như một nền tảng hứa hẹn để tạo mẫu nhanh cho một hệ thống trên chip so với ASIC [84]. Điều này cũng thích hợp để xây dựng một hệ thống thích nghi. Một hệ thống thích nghi [2, 87] là mô hình trong đó tác vụ tính toán có thể thay đổi và thích nghi với tình trạng tài nguyên của hệ thống hoặc các yêu cầu của ứng dụng hay hành vi của người dùng tại thời gian chạy. Hơn nữa, nhờ vào sự phát triển không ngừng của công nghệ bán dẫn và công nghệ nano mà số lượng tài nguyên và tốc độ xử lý trên FPGA đang dần tăng; giá thành và tiêu thụ năng lượng tiếp tục giảm (Hình 1). Thêm vào đó xu hướng thiết kế kết hợp giữa bộ vi xử lý và FPGA [28, 43] làm cho nó có thể phù hợp với các thiết kế hệ thống phức tạp linh hoạt trên một FPGA [6, 41]. Hình 1. Các ưu điểm của FPGA hiện đại [89] Với những yêu cầu như vậy, việc phát triển một nền tảng nhúng đa lõi cấu hình lại được động trên FPGA dựa theo mô hình NoC có hiệu năng cao và triển khai các ứng dụng có thể điều chỉnh mức chất lượng lên nền tảng này tại thời gian chạy là các vấn đề mới cần được nghiên cứu. Đó cũng chính là động lực mạnh mẽ thôi thúc nghiên cứu sinh chọn và thực hiện các nội dung nghiên cứu này trong luận án. 2. Mục tiêu, đối tƣợng, phƣơng pháp và phạm vi nghiên cứu Mục tiêu nghiên cứu: Xuất phát từ những vấn đề đặt ra như trên, mục tiêu chính của luận án tập trung vào phát triển một nền tảng phần cứng nhúng đa lõi cấu hình lại được kiến trúc NoC trên FPGA theo các yêu cầu thay đổi của các ứng dụng và triển khai các ứng dụng có thể điều chỉnh mức chất lượng lên nền tảng hệ thống này tại thời gian chạy. Để đạt được các mục tiêu chính này luận án cần thực hiện các mục tiêu cụ thể sau đây: 4 (i) Đề xuất kiến trúc NoC hiệu năng cao bao gồm kiến trúc bộ định tuyến và bộ (ii) giao tiếp mạng. Xây dựng nền tảng phần cứng đa lõi linh hoạt có khả năng cấu hình lại được từng phần trên FPGA dựa trên kiến trúc NoC. Nền tảng này cho phép thay đổi tự động một số mô đun trong lớp truyền thông hoặc lớp tính toán của NoC tại (iii) thời gian chạy để thích nghi với các yêu cầu thay đổi của các ứng dụng. Xây dựng và đề xuất các thuật toán cho bài toán ánh xạ các ứng dụng có thể điều chỉnh mức chất lượng vào nền tảng phần cứng cấu hình lại được dựa trên NoC. Các vấn đề này giúp hệ thống có các khả năng: Điều chỉnh mức chất lượng của ứng dụng theo tài nguyên sẵn có của nền tảng phần cứng; có thể triển khai được nhiều ứng dụng hơn lên nền tảng trong điều kiện giới hạn tài nguyên phần cứng; và cho phép thêm vào hệ thống các ứng dụng mới trong tương lai. Đối tượng nghiên cứu: Các đối tượng được nghiên cứu chính trong luận án bao gồm: (i) Mô hình kiến trúc mạng trên chip. (ii) (iii) (iv) Công nghệ FPGA và khả năng cấu hình lại từng phần động trên FPGA. Thiết kế hệ thống nhúng trên FPGA. Các kỹ thuật ánh xạ các ứng dụng vào kiến trúc đa lõi. Phương pháp nghiên cứu: Đầu tiên, phương pháp điều tra và phân tích dựa trên sách, tạp chí và các nguồn tài liệu khác từ Internet sẽ được sử dụng. Các ưu điểm và hạn chế của các vấn đề nghiên cứu liên quan đến luận án sẽ được chỉ ra. Từ đó, tác giả sẽ đề xuất một số mô hình và thuật toán cho vấn đề nghiên cứu. Cuối cùng, tính chính xác và đúng đắn của các mô hình và thuật toán đã đề xuất sẽ được kiểm chứng và phân tích bằng mô phỏng phần mềm và thực nghiệm trên các thiết bị thực tế. Phạm vi nghiên cứu: Để thực hiện được các mục tiêu đặt ra, luận án tập trung vào nghiên cứu các vấn đề cụ thể dưới đây: (i) Nghiên cứu mô hình kiến trúc NoC sử dụng cấu hình lưới hai chiều, kỹ thuật điều khiển luồng wormhole, kênh ảo và giải thuật định tuyến XY để xây dựng mô hình truyền thông NoC có hiệu năng cao. 5 (ii) Nghiên cứu công nghệ FPGA của Xilinx, công nghệ cấu hình lại từng phần động của FPGA để phát triển nền tảng phần cứng có khả năng cấu hình lại được lớp truyền thông hoặc lớp tính toán. (iii) Nghiên cứu bài toán ánh xạ các ứng dụng động có thể điều chỉnh mức chất lượng vào nền tảng phần cứng đa lõi cấu hình lại được dựa trên NoC với giả thiết kiến trúc lớp truyền thông là cố định và chỉ cấu hình lại lớp tính toán (các PE) của NoC để thích nghi với sự chuyển đổi từ ứng dụng này đến ứng dụng khác lên nền tảng phần cứng hoặc sự thay đổi mức chất lượng của các ứng dụng. Ngoài ra, luận án cũng chỉ tập trung vào nghiên cứu mô hình ứng dụng dưới dạng đồ thị tác vụ. 3. Các kết quả đạt đƣợc của luận án Luận án đã tập trung vào phát triển nền tảng phần cứng có khả năng cấu hình lại từng phần trên FPGA dựa theo kiến trúc NoC tại thời gian chạy. Nền tảng này cho phép tự động cấu hình lại các mô đun của lớp truyền thông (bộ định tuyến hoặc các mô đun trong bộ định tuyến) hoặc lớp tính toán để tối ưu hóa kiến trúc truyền thông hoặc các phần tử tính toán nhằm nâng cao hiệu năng cho hệ thống và đáp ứng với các yêu cầu thay đổi của ứng dụng. Ngoài ra, một kiến trúc truyền thông NoC cũng được phát triển. Trong đó, một bộ định tuyến và một bộ giao tiếp mạng mới có hiệu năng cao cũng được đề xuất. Bộ định tuyến và bộ giao tiếp mạng là các thành phần quan trọng để phát triển nền tảng phần cứng linh hoạt có khả năng cấu hình lại được nói trên. Dựa trên nền tảng đã được phát triển, một mô hình mới được xây dựng để 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ượng lên nền tảng này. Mô hình này đã được mô hình hóa bằng mô hình toán học và được mô phỏng trên máy tính cá nhân (PC: Personal Computer) với xem xét ánh xạ nhiều ứng dụng vào nền tảng phần cứng tại thời gian chạy. Tùy theo tình trạng tài nguyên sẵn có của nền tảng mà mô hình cho phép ánh xạ ứng dụng với một mức chất lượng phù hợp. Giải pháp này tạo ra một sự linh hoạt và thích nghi khi triển khai các ứng dụng lên nền tảng trong môi trường động, tức là tải làm việc của các ứng dụng thay đổi động và các yêu cầu chất lượng của các ứng dụng thay đổi theo hành vi của người dùng. Giải pháp cũng cho phép khai thác hiệu quả và cân bằng giữa sức mạnh tính toán của các phần tử phần cứng cấu hình và sự linh hoạt của các vi xử lý nhúng nhằm đáp ứng cho các ứng dụng yêu cầu sức mạnh tính toán lớn và có nhiều mức chất lượng. Thêm vào đó, một thuật toán phân vùng và hai thuật toán ánh xạ cũng được phát triển để giải quyết bài toán ánh xạ nói trên với mục tiêu chung đó là triển khai linh hoạt các ứng dụng lên nền tảng phần cứng cấu hình lại được sao cho chất lượng dịch vụ tổng thể của các ứng dụng sau khi triển khai đạt được cực đại. Ngoài ra, giải pháp này cũng cho phép thêm vào hệ thống các ứng dụng mới trong tương lai một cách dễ dàng. 6 Các kết quả đạt được của luận án đã được công bố trên các tạp chí khoa học chuyên ngành uy tín trong nước và các hội nghị quốc tế có phản biện độc lập khác nhau. Một kiến trúc NoC hiệu năng cao bao gồm một bộ định tuyến và bộ giao tiếp mạng đã được đề xuất và đăng tải trong [TC1] và [HN1]. Một nền tảng phần cứng linh hoạt hỗ trợ cấu hình lại cho các mô đun truyền thông tại thời gian chạy được xuất bản trong [TC2]. Một mô hình mới được xây dựng để 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ượng lên nền tảng phần cứng cấu hình lại được và các thuật toán ánh xạ động có chất lượng giải pháp tốt hơn một vài thuật toán liên quan cũng được đăng tải trên [HN2] và [TC3]. 4. Cấu trúc của luận án Cấu trúc của luận án bao gồm ba chương: Trong Chương 1, tác giả trình bày ngắn gọn các nội dung kiến thức liên quan đến luận án để làm cơ sở cho những đề xuất trong các chương tiếp theo như kiến trúc NoC, công nghệ FPGA, khả năng cấu hình lại từng phần động của FPGA và bài toán ánh xạ các ứng dụng lên NoC. Các kiến thức về NoC như: Kiến trúc của bộ định tuyến, cấu hình mạng, thuật toán định tuyến, cơ chế điều khiển luồng, chuyển mạch, v.v. Công nghệ FPGA hiện tại và tương lai, các điểm mạnh của các FPGA hiện đại. Các khái niệm và các kỹ thuật ánh xạ các ứng dụng lên kiến trúc NoC cũng được trình bày trong phần cuối của chương này. Chương 2 tóm tắt các nghiên cứu trong nước và quốc tế; nêu ra các hạn chế của các nghiên cứu này, từ đó đề xuất và phát triển các mô hình kiến trúc; các kết quả thí nghiệm và đánh giá cũng được trình bày trong chương này. Các kiến trúc được đề xuất bao gồm: kiến trúc bộ định tuyến, bộ giao tiếp mạng và phát triển một nền tảng phần cứng đầy hứa hẹn trên FPGA cho NoC bằng cách sử dụng khả năng cấu hình lại từng phần động của FPGA. Phần cuối sẽ tổng kết các nội dung, các đề xuất nổi bật của chương. Trong Chương 3, tác giả trình bày một mô hình mới cho bài toán ánh xạ các ứng dụng có thể điều chỉnh mức chất lượng lên nền tảng phần cứng đã được phát triển trong Chương 2 bằng cách mô hình hóa nền tảng này bằng mô hình toán học và mô phỏng trên PC. Trong chương này, các mô tả, các định nghĩa, mô hình ứng dụng, mô hình chất lượng và mô hình phần cứng sẽ được trình bày. Ngoài ra, một thuật toán phân vùng và một vài thuật toán ánh xạ cũng sẽ được giới thiệu. Các nội dung quan trọng và các đóng góp chính sẽ được tóm lược trong phần cuối của chương. Cuối cùng là kết luận về những nội dung chính, các đóng góp khoa học quan trọng của luận án cũng như hướng nghiên cứu và phát triển trong tương lai.