Luận án 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 - Trường Đại học Bách khoa Hà Nội

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. Hà Nội, ngày 08 tháng 05 năm 2017 Giáo viên hướng dẫn Tác giả PGS. 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.

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. 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.

Mục tiêu, đối tượng, phương pháp và phạm vi nghiên cứu. Các kết quả đạt được của luận án. Cấu trúc của luận án. 6 CHƯƠNG 1 CƠ SỞ LÝ THUYẾT.

Lý thuyết về mạng trên chip. Nguồn gốc và thuật ngữ. Cấu hình mạng. Mạng lưới n-chiều (n-Dimensional Mesh).

Mạng K-ary n-cube. Mạng có số chiều thấp. Cơ chế điều khiển luồng. Cơ chế điều khiển luồng Store-and-Forward (SAF).

Cơ chế điều khiển luồng Wormhole (WH). Cơ chế điều khiển luồng Virtual cut-through (VCT). Cơ chế điều khiển luồng kênh ảo (Virtual Channel). Thuật toán định tuyến.

Phân loại định tuyến. Các vấn đề trong định tuyến. Tổng quan kiến trúc bộ định tuyến. Công nghệ FPGA.

Kiến trúc FPGA. Tổng quan kiến trúc FPGA. Kiến trúc FPGA của Xilinx. Cấu hình lại từng phần.

Cấu hình lại từng phần động. Các ưu điểm của cấu hình lại từng phần. Hỗ trợ cấu hình lại trong FPGA của Xilinx. Kỹ thuật ánh xạ ứng dụng lên nền tảng mạng trên chip.

Bài toán ánh xạ. Ánh xạ tại thời gian thiết kế. Ánh xạ tại thời gian chạy. 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. Thiết kế bộ định tuyến cho NoC. Đề xuất kiến trúc bộ định tuyến. Lựa chọn các thông số thiết kế.

Bộ đệm ngõ vào. Bộ giải mã flit. Chuyển mạch và kênh ảo. Bộ phân xử.

Kết quả và đánh giá. Kết quả tổng hợp. Kết quả mô phỏng. Thiết kế bộ giao tiếp mạng cho NoC.

Phương pháp tiếp cận. Đề xuất kiến trúc bộ giao tiếp mạng. Kết quả và đánh giá. Phát triển nền tảng phần cứng cấu hình lại từng phần động.

Xây dựng hệ thống (nền tảng phần cứng) cấu hình. Luồng thiết kế. Thiết lập hệ thống. Các trường hợp nghiên cứu.

Cấu hình lại cơ sở hạ tầng truyền thông. Cấu hình lại các PE. Kết quả thực nghiệm. 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. Mô tả bài toán ánh xạ. Các định nghĩa và xây dựng bài toán ánh xạ. Mô hình ứng dụng.

Đồ thị tác vụ ứng dụng. Mô hình chất lượng. Mô hình phần cứng. Xây dựng bài toán ánh xạ.

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. Giải pháp tối ưu sử dụng thuật toán tìm kiếm đầy đủ. Kết quả mô phỏng và đánh giá. Giải pháp heuristic cho bài toán ánh xạ tại thời gian chạy.

Chiến lược chọn vùng gần lồi. Thuật toán ánh xạ heuristic. Kết quả mô phỏng và đánh giá. Kết luận chương.

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 Nghĩa tiếng Anh của từ viết tắt Nghĩa tiếng Việt ABP Adaptive BackPressure Average Communication Khoảng cách Manhattan truyền ACMD Manhattan Distance thông trung bình Khoảng cách Manhattan trung AMD Average Manhattan Distance bình ARM Advanced RISC Machine Vi xử lý ARM Application-Specific Integrated ASIC Vi mạch tích hợp chuyên dụng Circuit ATG Application Task Graph Đồ thị tác vụ ứng dụng AXI Advanced eXtensible Interface Giao diện mở rộng tiên tiến C2R Core to Router Từ lõi IP đến bộ định tuyến CAGR Compound Annual Growth Rate Tốc độ tăng trưởng kép hàng năm CF CompactFlash Bộ nhớ flash CLB Configurable Logic Block Khối Logic cấu hình CMPS Chip Multi-Processors Chip đa xử lý CPU Central Processing Unit Đơn vị xử lý trung tâm DDR Double Data Rate Tốc độ dữ liệu kép Bộ nhớ truy cập ngẫu nhiên tốc DDRAM Double Data Rate RAM độ dữ liệu kép DMA Direct Memory Access Truy nhập bộ nhớ trực tiếp DP Dynamic Part Phần động DPR Dynamic Partial Reconfigurable Cấu hình lại từng phần động DSP Digital Signal Processor Xử lý tín hiệu số DT Design-time Thời gian thiết kế EDK Embedded Development KIT Bộ công cụ phát triển nhúng FF First Fit Thuật toán ánh xạ first fit FFT Fast Fourier Transform Biến đổi Fourier nhanh FIFO First In First Out Vào trước ra trước Mảng các cổng có thể lập trình tại FPGA Field Programmable Gate Array chỗ FT Flit Type Loại flit Các giao tiếp vào ra mục đích GPIO General Purpose Input Output chung HDL Hardware Description Language Ngôn ngữ mô tả phần cứng Truyền tải video qua giao thức HTTP-VS HTTP video streaming http HW/SW Hardware/Software Phần cứng/Phần mềm viii Ký hiệu Nghĩa tiếng Anh của từ viết tắt Nghĩa tiếng Việt IC Integrated Circuit Mạch tích hợp Cổng truy nhập cấu hình bên ICAP Internal Configuration Access Port trong InP Indefinite Postponement Trì hoãn không xác định IP Intellectual Property (IP Core) Lõi sở hữu trí tuệ ISE Integrated Software Environment Môi trường phần mềm tích hợp ISP Instruction Set Processor Vi xử lý tập lệnh JTAG Joint Test Action Group Cable Cáp JTAG LCD Liquid Crystal Display Màn hình tinh thể lỏng LE Logic Element Phần tử logic LUT Logic Look-up Table Bảng tra logic MD Manhattan Khoảng cách Manhattan MPEG-4 Moving Picture Experts Group MPSoC Multiprocessor System on Chip Hệ thống đa xử lý trên chip MWD Multi-Window Display NI Network Interface Bộ giao tiếp mạng Thuật toán ánh xạ nearest NN Nearest Neighbor neighbor NoC Network-on-Chip Mạng trên chip OB Overall Benefit Giá trị lợi ích tổng thể PC Personal Computer Máy tính cá nhân PCB Printed circuit board Bảng mạch in PE Processing Element Phần tử xử lý (tính toán) PIP Picture In Picture PL Programmable Logic Logic lập trình PLB Processor Local Bus PLD Programmable Logic Device Thiết bị logic khả trình PR Partial Reconfiguration Cấu hình lại được từng phần QoS Quality of service Chất lượng dịch vụ R2C Router to Core Từ bộ định tuyến đến lõi IP RAM Random Access Memory Bộ nhớ truy cập ngẫu nhiên RI Routing Information Thông tin định tuyến RPA Reprogrammability Khả năng lập trình lại RR Reconfigurable Region Vùng cấu hình lại được RT Run-time Thời gian chạy RTL Register Transfer Level Mức truyền thanh ghi SAF Store-And-Forward Bộ công cụ phát triển phần mềm SDK Software Development KIT của Xilinx SN Sequence Number Số thứ tự ix Ký hiệu Nghĩa tiếng Anh của từ viết tắt Nghĩa tiếng Việt SoC System-on-Chip Hệ thống trên chip SOF System-on-an-FPGA Hệ thống trên một FPGA SP Static Part Phần tĩnh SRAM Static Random Access Memory Bộ nhớ truy cập ngẫu nhiên tĩnh Công cụ tạo đồ thị tác vụ miễn TGFF Task Graphs For Free phí Universal Asynchronous Bộ truyền nhận nối tiếp không UART Receiver/Transmitter đồng bộ VC Virtual Channel Kênh ảo VCT Virtual Cut-Through VHSIC Hardware Description Ngôn ngữ mô tả phần cứng VHDL Language VHSIC Very High Speed Integrated VHSIC Mạch tích hợp tốc độ rất cao Circuit VLSI Very-large-scale integration Mạch tích hợp rất cao WH Wormhole Chuyển mạch lỗ sâu Bộ công cụ xây dựng phần cứng XPS Xilinx Platform Studio 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]. Cấu trúc của một NoC dạng lưới 3x3.

Phân loại cấu hình mạng NoC. Mạng lưới n-chiều. Mạng k-ary n-cube. Mạng hai chiều mesh và torus.

Cơ chế điều khiển luồng SAF và WH. Phân loại các thuật toán định tuyến trong NoC. Kiến trúc tổng quát của một bộ định tuyến [7]. Thị trường cung cấp FPGA bởi các nhà sản xuất [78].

Quy mô thị trường ứng dụng của FPGA khu vực Châu Á Thái Bình Dương [42]. Kiến trúc chung của FPGA. Một Slice của FPGA Xilinx Virtex-6 [95]. Minh họa thiết kế cấu hình lại từng phần.

Quy trình thực hiện cấu hình từng phần cho FPGA [97]. Tổng quan cấu hình lại từng phần động và bộ nhớ cấu hình [77]. Bộ định tuyến. Cấu trúc của các flit.

Kiến trúc bộ định tuyến đề xuất. Sơ đồ khối của bộ đệm ngõ vào. Sơ đồ khối bộ giải mã flit. Thuật toán XY.

Cấu trúc của chuyển mạch. Bộ phân xử 2:1. Bộ phân xử 4:1. Kết quả mô phỏng RTL cho các kịch bản.

Trễ trung bình toàn mạng. Thông lượng trung bình toàn mạng. Quá trình ghi/đọc dữ liệu vào/ra bộ đệm đơn. Quá trình ghi/đọc dữ liệu vào/ra bộ đệm kép.

Kiến trúc tổng quát của bộ giao tiếp mạng. Biểu đồ thời gian truyền các gói tin từ tài nguyên đến bộ định tuyến. Mô hình kiến trúc cấu hình trên FPGA. Sơ đồ luồng thiết lập hệ thống .