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 NoC cấu hình lại được :Báo cáo tổng kết đề tài khoa học cấp Trường

BỘ CÔNG THƯƠNG

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HCM

BÁO CÁO CHI TIẾT

ĐỀ TÀI:

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 NoC CẤU HÌNH LẠI ĐƯỢC

Mã số: 182.QN01

Đơn vị chủ trì: Phân hiệu Quảng Ngãi

Chủ nhiệm đề tài: Nguyễn Văn Cường

Hồ Chí Minh – 2019

MỤC LỤC

DANH MỤC CÁC TỪ VIẾT TẮT ....................................................................................i

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ...........................................................................iii

DANH MỤC CÁC BẢNG BIỂU....................................................................................... v

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ấu trúc của đề tài.............................................................................................. 4

CHƯƠNG 1 CƠ SỞ LÝ THUYẾT................................................................................... 5

1.1. Lý thuyết về mạng trên chip.............................................................................. 5

1.1.1. Nguồn gốc và thuật ngữ ................................................................................... 5

1.1.2. Cấu hình mạng ................................................................................................. 6

1.1.2.1. Mạng lưới n-chiều (n-Dimensional Mesh)......................................... 7

1.1.2.2. Mạng K-ary n-cube............................................................................. 7

1.1.2.3. Mạng có số chiều thấp........................................................................ 7

1.1.3. Cơ chế điều khiển luồng................................................................................... 8

1.1.3.1. Bản tin ................................................................................................ 8

1.1.3.2. Cơ chế điều khiển luồng Store-and-Forward (SAF) .......................... 9

1.1.3.3. Cơ chế điều khiển luồng Wormhole (WH) ........................................ 9

1.1.3.4. Cơ chế điều khiển luồng kênh ảo (Virtual Channel).......................... 9

1.1.4. Thuật toán định tuyến..................................................................................... 10

1.1.4.1. Phân loại định tuyến ......................................................................... 10

1.1.5. Tổng quan kiến trúc bộ định tuyến ................................................................ 11

1.2. Công nghệ FPGA.............................................................................................. 12

1.2.1. Kiến trúc FPGA.............................................................................................. 13

1.2.1.1. Tổng quan kiến trúc FPGA............................................................... 13

1.2.1.2. Kiến trúc FPGA của Xilinx .............................................................. 14

1.2.2. Cấu hình lại từng phần ................................................................................... 16

1.2.2.1. Cấu hình lại từng phần động............................................................. 17

1.2.2.2. Các ưu điểm của cấu hình lại từng phần .......................................... 18

1.3. Kỹ thuật ánh xạ ứng dụng lên nền tảng mạng trên chip .............................. 19

1.3.1. Bài toán ánh xạ............................................................................................... 19

1.3.2. Ánh xạ tại thời gian thiết kế........................................................................... 20

1.3.3. Ánh xạ tại thời gian chạy ............................................................................... 20

1.4. Kết luận chương................................................................................................ 21

CHƯƠNG 2 PHÁT TRIỂN NỀN TẢNG PHẦN CỨNG CẤU HÌNH LẠI ĐƯỢC

CHO NoC ...................................................................................................................... 22

2.1. Giới thiệu........................................................................................................... 22

2.2. Xây dựng hệ thống (nền tảng phần cứng) cấu hình ...................................... 24

2.2.1. Luồng thiết kế................................................................................... 24

2.2.2. Thiết lập hệ thống............................................................................. 25

2.3. Các trường hợp nghiên cứu............................................................................. 26

2.3.1. Cấu hình lại cơ sở hạ tầng truyền thông........................................... 26

2.3.2. Cấu hình lại các PE........................................................................... 29

2.4. Kết quả thực nghiệm ........................................................................................ 30

2.5. Kết luận chương................................................................................................ 32

CHƯƠNG 3 ÁP DỤNG CHIẾN LƯỢC CHỌN VÙNG VÀ THUẬT TOÁN

NSGA2 CHO BÀI TOÁN ÁNH XẠ CÁC ỨNG DỤNG LÊN NoC............................. 33

3.1. Giới thiệu........................................................................................................... 33

3.2. Các định nghĩa và bài toán ánh xạ.................................................................. 34

3.2.1. Mô hình ứng dụng.......................................................................................... 34

3.2.1.1. Đồ thị tác vụ ứng dụng ..................................................................... 35

3.2.1.2. Mô hình chất lượng .......................................................................... 35

3.2.2. Mô hình phần cứng ........................................................................................ 36

3.2.3. Bài toán ánh xạ............................................................................................... 37

3.3. Vùng gần lồi và thuật toán NSGA2................................................................. 38

3.3.1. Chiến lược chọn vùng gần lồi ........................................................................ 39

3.3.2. Thuật toán NSGA2......................................................................................... 39

3.3.2.1. Khởi tạo quần thể cha....................................................................... 39

3.3.2.2. Đánh giá quần thể............................................................................. 39

3.3.2.3. Sắp xếp thứ hạng và tính khoảng cách hội tụ cho quần thể cha....... 40

3.3.2.4. Lựa chọn cá thể bố mẹ trong quần thể cha ....................................... 41

3.3.2.5. Chéo hóa và đột biến ........................................................................ 42

3.3.2.6. Sắp xếp thứ hạng, tính khoảng cách hội thụ cho quần thể cha,

con và tạo quần thể cha mới ............................................................. 42

3.3.3. Kết quả mô phỏng và thảo luận ..................................................................... 43

3.3.3.1. Thiết lập mô phỏng........................................................................... 43

3.3.3.2. Kết quả và đánh giá .......................................................................... 44

3.4. Kết luận chương................................................................................................ 47

KẾT LUẬN ...................................................................................................................... 49

Các kết quả đạt được của đề tài .................................................................................. 49

Hướng phát triển của đề tài......................................................................................... 50

DANH MỤC CÁC CÔNG TRÌNH ĐÃ CHẤP NHẬN ĐĂNG CỦA ĐỀ TÀI............ 51

TÀI LIỆU THAM KHẢO................................................................................................ 52

i

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

ACMD Average Communication

Manhattan Distance

Khoảng cách Manhattan truyền

thông trung bình

AMD Average Manhattan Distance Khoảng cách Manhattan trung

bình

ARM Advanced RISC Machine Vi xử lý ARM

ASIC Application-Specific Integrated

Circuit Vi mạch tích hợp chuyên dụng

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

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

DDRAM Double Data Rate RAM Bộ nhớ truy cập ngẫu nhiên tốc

độ 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

FPGA Field Programmable Gate Array Mảng các cổng có thể lập trình tại

chỗ

FT Flit Type Loại flit

GPIO General Purpose Input Output Các giao tiếp vào ra mục đích

chung

HDL Hardware Description Language Ngôn ngữ mô tả phần cứng

HTTP-VS HTTP video streaming Truyền tải video qua giao thức

http

HW/SW Hardware/Software Phần cứng/Phần mềm

IC Integrated Circuit Mạch tích hợp

ICAP Internal Configuration Access Port Cổng truy nhập cấu hình bên

trong

ii

Ký hiệu Nghĩa tiếng Anh của từ viết tắt Nghĩa tiếng Việt

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

LE Logic Element Phần tử logic

LUT Logic Look-up Table Bảng tra logic

MD Manhattan Khoảng cách Manhattan

MPEG Moving Picture Experts Group MPEG

MPSoC Multiprocessor System on Chip Hệ thống đa xử lý trên chip

MWD Multi-Window Display Hiển thị đa cửa sổ

NI Network Interface Bộ giao tiếp mạng

NN Nearest Neighbor Thuật toán ánh xạ nearest

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 Ảnh trong ảnh

PL Programmable Logic Logic lập trình

PLB Processor Local Bus Bus PLB

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ụ

RAM Random Access Memory Bộ nhớ truy cập ngẫu nhiên

SDK Software Development KIT Bộ công cụ phát triển phần mềm

của Xilinx

SoC System-on-Chip Hệ thống trên chip

SRAM Static Random Access Memory Bộ nhớ truy cập ngẫu nhiên tĩnh

TGFF Task Graphs For Free Công cụ tạo đồ thị tác vụ miễn

phí

UART Universal Asynchronous

Receiver/Transmitter

Bộ truyền nhận nối tiếp không

đồng bộ

VC Virtual Channel Kênh ảo

VHDL VHSIC Hardware Description

Language

Ngôn ngữ mô tả phần cứng

VHSIC

VHSIC Very High Speed Integrated

Circuit Mạch tích hợp tốc độ rất cao

WH Wormhole Chuyển mạch lỗ sâu

XPS Xilinx Platform Studio Bộ công cụ xây dựng phần cứng

hệ thống nhúng của Xilinx

iii

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Trang

Hình 1.1. Cấu trúc của một NoC dạng lưới 3x3.................................................................5

Hình 1.2. Phân loại cấu hình mạng NoC............................................................................ 6

Hình 1.3. Mạng lưới n-chiều .............................................................................................. 7

Hình 1.4. Mạng k-ary n-cube ............................................................................................. 7

Hình 1.5. Mạng hai chiều mesh và torus............................................................................ 8

Hình 1.6. Cơ chế điều khiển luồng SAF và WH................................................................ 9

Hình 1.7. Phân loại các thuật toán định tuyến trong NoC................................................ 11

Hình 1.8. Kiến trúc tổng quát của một bộ định tuyến [20]............................................... 11

Hình 1.9. Thị trường cung cấp FPGA bởi các nhà sản xuất [23].....................................13

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

[24] ................................................................................................................... 13

Hình 1.11.Kiến trúc chung của FPGA [25].......................................................................14

Hình 1.12.Một Slice của FPGA Xilinx Virtex-6 [30]....................................................... 15

Hình 1.13.Minh họa thiết kế cấu hình lại từng phần [33] ................................................. 16

Hình 1.14.Quy trình thực hiện cấu hình từng phần cho FPGA [34] .................................17

Hình 2.13.Mô hình kiến trúc cấu hình trên FPGA ............................................................ 23

Hình 2.14.Sơ đồ luồng thiết lập hệ thống..........................................................................24

Hình 2.15.Sơ đồ khối tổng quát của hệ thống ...................................................................25

Hình 2.16.Thiết lập phần cứng trên công cụ XPS............................................................. 26

Hình 2.17.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................................................................................................................... 27

Hình 2.18.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

.......................................................................................................................... 29

Hình 2.19.Mô hình cấu hình lại các PE trong mạng 2x2 .................................................. 30

Hình 2.20.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

.......................................................................................................................... 31

Hình 3.1. Ảnh hưởng của dữ liệu đến chất lượng video [67][68]....................................34

Hình 3.2. Mô hình hệ thống ............................................................................................. 37

Hình 3.3. Đồ thị tác vụ của ứng dụng được tạo ra từ TGFF và ứng dụng MPEG-4........38

Hình 3.4. Thuật toán tìm nhóm cá thể cùng thứ hạng ...................................................... 40

Hình 3.5. Thuật toán tính khoảng cách hội tụ ..................................................................41

Hình 3.6. Thuật toán sắp xếp thứ hạng và tính khoảng cách hội tụ .................................41

Hình 3.7. Thuật toán lựa chọn.......................................................................................... 42