Tóm tắt 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 ứng dụng trên nền tảng noc

in được truyền xong. Điểm đặc biệt trong thiết kế này đó là việc bố trí các kênh ảo khác nhau tại các cổng nhằm tiết kiệm tài nguyên phần cứng nhưng vẫn tránh được tắc nghẽn và đảm bảo được hiệu năng mạng bằng cách kết hợp linh hoạt giữa việc sử dụng thuật toán định tuyến XY với việc bố trí số kênh ảo phù hợp tại các cổng ngõ ra. Điều này có thể được giải thích như sau: Theo nguyên tắc hoạt động của thuật toán định tuyến XY, khi chuyển các flit từ nguồn đến đích, đầu tiên các flit sẽ được truyền theo phương X sau đó đến phương Y đến khi tìm đúng địa chỉ đích sẽ dừng. Do vậy, cổng ngõ ra E sẽ nhận được dữ liệu từ các cổng ngõ vào W và L; cổng ngõ ra W sẽ nhận được dữ liệu từ cổng ngõ vào E và L; cổng ngõ ra S sẽ nhận được dữ liệu từ các cổng vào N, E, W và L; cổng ngõ ra N sẽ nhận được dữ liệu từ cổng ngõ vào S, E, W và L; cổng ngõ ra L sẽ nhận được dữ liệu từ các cổng ngõ vào N, S, E và W. Dựa trên phân tích này, tác giả bố trí 4 kênh ảo tại các cổng ngõ ra N và S và 2 kênh ảo cho các cổng ngõ ra còn lại E và W. 2.1.2. Kết quả và đánh giá 2.1.2.1. Kết quả tổng hợp Kiến trúc bộ định tuyến được mô hình hóa bằng ngôn ngữ phần cứng Verilog HDL và được tổng hợp trên KIT FPGA Virtex-6 chip 6VLX240TFF156 bởi công cụ ISE (Integrated Software 8 Environment )14.1. Bảng 2.2 chỉ ra tài nguyên FPGA đã sử dụng khi tổng hợp. Kết quả tổng hợp cho thấy bộ định tuyến đã đề xuất chiếm khoảng 0,48% Register và 0,88% LUT so với tổng tài nguyên FPGA. Nếu so sánh với trường hợp bộ định tuyến sử dụng 2 kênh ảo thì số Register tăng 26,6% và số LUT tăng 19,5%. Tuy nhiên, khi so sánh với trường hợp 4 kênh ảo thì thiết kế đã đề xuất giảm 17,2% tài nguyên Register và 29,7% tài ngyên LUT. Vấn đề tăng và giảm tài nguyên trong các thiết kế là do số lượng kênh ảo tăng; các mạch điều khiển kênh ảo và bộ phân xử có độ phức tạp lớn hơn. Kết quả tổng hợp cũng chỉ ra rằng tần số làm việc cực đại của bộ định tuyến đã đề xuất có thể đạt đến 426,6 MHz. Bảng 2.2. Tài nguyên sử dụng của các bộ định tuyến trên FPGA Tổng hợp sử dụng tài nguyên Logic Utilization Sẵn có 2 kênh ảo Tác giả 4 kênh ảo Sử dụng % Sử dụng % Sử dụng % Slice Registers 301440 1027 0,34 1399 0,46 1692 0,56 Slice LUTs 150720 1026 0,68 1274 0,85 1814 1,20 2.1.2.2. Kết quả mô phỏng Độ trễ và thông lượng trung bình của mạng với kích thước 3x3 sử dụng bộ định tuyến chứa 1, 2, 4 kênh ảo và bộ định tuyến đã đề xuất sẽ được đánh giá và so sánh. Các thông số mô phỏng được thiết lập như Bảng 2.1 và sử dụng công cụ Noxim trong [27]. Kết quả mô phỏng về độ trễ và thông lượng trung bình như Hình 2.11 và Hình 2.12. Hình 2.11. Trễ trung bình toàn mạng Hình 2.12. Thông lượng trung bình toàn mạng 2.2. Thiết kế bộ giao tiếp mạng Bộ giao tiếp mạng là khối logic rất quan trọng trong cấu trúc của NoC. Chức năng của nó tương tự như chức năng của card mạng kết nối giữa máy tính và mạng Internet [36, 45] tức là thực hiện kết nối tài nguyên vào mạng tại các vị trí giao diện dữ liệu vào ra của bộ định tuyến [64]. Do sự khác biệt về kích thước dữ liệu, giao diện tín hiệu điều khiển của các tài nguyên với mạng nên bộ giao tiếp mạng có thể thay đổi tùy theo tài nguyên được kết nối với mạng. Bộ giao tiếp mạng có thể chia ra làm hai phần như sau: Phần thứ nhất là phần giao tiếp với bộ định tuyến được xem như phần không phụ thuộc vì dữ liệu vào bộ định tuyến là các flit có kích thước dữ liệu cố định theo thiết kế. Phần thứ hai là phần giao tiếp với tài nguyên, tùy thuộc vào loại tài nguyên mà kích thước dữ liệu có thể thay đổi. Vì vậy phần này được gọi là phần phụ thuộc. 9 2.2.1. Đề xuất kiến trúc 34 bits Kiến trúc NI FIFO A full_FFA empty_FFA rd_en_FFA release_FFA release_FFB A/B_select Flit_type C2R_READ_CTRL state_FFA state_FFB req_router router_ack full_FFB empty_FFB rd_en_FFB wr_en_FFA empty_FFA full_FFA release_FFA release_FFB pkt_size C2R_WRITE_CTRL state_FFA core_req state_FFB ack_core wr_en_FFB empty_FFB full_FFB FIFO B 32 bits F li ti li z e r router_ack req_router ack_core core_req Data_routerCore_data 34 bits FIFO A full_FFA empty_FFA wr_en_FFA release_FFA pkt_size release_FFB flit_en R2C_WRITE_CTRL state_FFA state_FFB ack_router router_req full_FFB empty_FFB wr_en_FFB rd_en_FFA empty_FFA full_FFA release_FFA release_FFB A/B_select R2C_READ_CTRL state_FFA Core_ack state_FFB req_core rd_en_FFB empty_FFB full_FFB FIFO B D e -f li ti li z e r router_req Router_DataData_core req_core core_ack 32 bits 32 bits M u x ack_router 32 bits 32 bits 32 bits 32 bits 32 bits 32 bits 32 bits Hình 2.15. Kiến trúc tổng quát của bộ giao tiếp mạng Kiến trúc của bộ giao tiếp mạng được đề xuất như Hình 2.15 gồm các khối chính sau: Các bộ đệm FIFO A và B; các bộ điều khiển ghi/đọc dữ liệu vào/ra WRITE_CTRL và READ_CTRL; các bộ ghép Flitilizer và tách flit De-Flitilizer mỗi khối sẽ thực hiện một chức năng riêng. 2.2.2. Kết quả và đánh giá Bảng 2.4. Kết quả tổng hợp trên FPGA Tổng hợp sử dụng tài nguyên Logic Utilization Sẵn có NI - 1 FIFO Tác giả Đã sử dụng % Đã sử dụng % Slice Registers 301440 202 0,07 227 0,08 Slice LUTs 150720 186 0,12 361 0,24 IOBs 600 147 24,5 147 24,5 Bộ giao tiếp mạng đã đề xuất được mô hình hóa bằng ngôn ngữ Verilog, tổng hợp và mô phỏng bằng ISE 14.1 và Isim trên FPGA Virtex-6 chip 6VLX240TFF156. Các thông số như tài nguyên sử dụng, độ trễ, tốc độ hoạt động của NI đã đề xuất sẽ được phân tích và đánh giá. Bảng 2.4 thống kê tài nguyên sử dụng của NI với trường hợp sử dụng bộ đệm đơn và sử dụng bộ đệm kép. NI sử dụng bộ đệm đơn mất khoảng 0,07% tài nguyên Register và 0,12% tài nguyên LUT so với tổng tài nguyên sẵn có của FPGA, trong khi với phiên bản NI sử dụng bộ đệm kép mất khoảng 0,08% tài nguyên Register và 0,24% tài nguyên LUT. Dễ thấy tài nguyên sử dụng của phiên bản bộ đệm kép tăng so với phiên bản sử dụng bộ đệm đơn, điều này có thể lý giải như sau: Xét về kích thước bộ đệm, gần như không thay đổi vì bộ đệm kép được tách đôi từ bộ đệm đơn như đã trình bày trong Mục 2.2.1 của luận án. Tuy nhiên, xét về mặt phức tạp của bộ điều khiển quá trình ghi/đọc trong phiên bản dùng bộ đệm đơn và bộ đệm kép thì phiên bản sử dụng bộ đệm kép có độ phức tạp lớn hơn. Đó cũng là nguyên nhân làm tăng tài nguyên sử dụng của NI sử dụng bộ đệm kép. 10 Kết quả tổng hợp cho thấy rằng tốc độ hoạt động của NI do tác giả đề xuất lớn hơn so với tốc độ hoạt động của NI sử dụng một bộ đệm và nghiên cứu trong [4]. Nó được thể trong Bảng 2.5. Trễ của bộ giao tiếp mạng sử dụng bộ đệm kép thấp hơn trễ trong NI sử dụng bộ đệm đơn. Bảng 2.5. Tốc độ hoạt động của các bộ giao tiếp mạng Các nghiên cứu NI-1 FIFO [4] Tác giả MNI SNI Tốc độ (Mhz) 302 310 252 397 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 Trong giới hạn của nghiên cứu này, tác giả sẽ tập trung vào phát triển một nền tảng mẫu có thể thực hiện theo hai giải pháp. Giải pháp đầu tiên, nền tảng có thể cấu hình lại cơ sở hạ tầng truyền thông mạng, có thể cấu hình bộ định tuyến hoặc các thành phần trong bộ định tuyến như bộ đệm, chuyển mạch, bộ phân xử, v.v. hoặc cấu hình cả cấu hình mạng để tối ưu kiến trúc truyền thông, trong khi duy trì cố định vị trí của các PE (lõi tính toán). Giải pháp này hoàn toàn phù hợp với kịch bản các ứng dụng chạy trên hệ thống có tải làm việc thay đổi động (ví dụ: thay đổi hiệu năng, thay đổi mức chất lượng). Giải pháp thứ hai, nền tảng có thể thay đổi tự động các PE tại thời gian chạy, trong khi cơ sở hạ tầng truyền thông mạng được giữ cố định. Giải pháp này rất phù hợp cho bài toán ánh xạ các ứng dụng khác nhau lên hệ thống hoặc hệ thống có tài nguyên hạn chế nhưng yêu cầu triển khai nhiều ứng dụng lên nó tại các thời điểm khác nhau. 2.3.1. Xây dựng mô hình hệ thống Hệ thống cấu hình lại từng phần động được xây dựng gồm hai khu vực chính: Khu vực tĩnh và khu vực cấu hình như được trình bày trong Hình 2.19. Khu vực tĩnh được đặt trong vùng tĩnh của FPGA. Nó chịu trách nhiệm điều khiển quá trình hoạt động của toàn hệ thống trong suốt thời gian chạy ứng dụng và điều khiển quá trình cấu hình lại các mô đun của NoC tương ứng với các giải pháp đã được trình bày ở trên. Các thành phần chính được đặt trong khu vực tĩnh gồm vi xử lý nhúng đóng vai trò xử lý trung tâm và điều khiển các hoạt động cấu hình của hệ thống qua hệ thống Bus AXI (Advanced eXtensible Interface ) hoặc PLB (Processor Local Bus). Khối UART (Universal Asynchronous Receiver/Transmitter) có chức năng giao tiếp với máy tính thông qua cổng truyền thông nối tiếp chuẩn RS-232 để hiển thị các thông báo và kết quả trên máy tính. Khối sysAce_Compact Flash thực hiện giao tiếp với bộ nhớ ngoài CF (Compact Flash), nơi lưu trữ các file cấu hình như kích thước bộ đệm, bộ định tuyến hay các PE được tổng hợp theo các ứng dụng. Bộ định thời (Timer) sử dụng để đo thời gian cấu hình của hệ thống. HWICAP là một lõi cứng được cung cấp bởi Xilinx [98-99] (XPS_ICAP dùng cho Bus PLB hoặc AXI_ICAP sử dụng cho Bus AXI), nó có vai trò rất quan trọng trong hệ thống cấu hình lại động đó là nhận các file cấu hình từ bộ nhớ ngoài CF hoặc từ bộ nhớ SDRAM DDR3 để nạp vào khu vực cấu hình động của FPGA. Ngoài ra, khu vực tĩnh còn chức một số mô đun không cần cấu hình lại của NoC. Khu vực động chứa các mô đun chức năng còn lại của NoC mà có thể thay đổi, sửa lỗi hoặc gỡ bỏ tại thời gian chạy để thích nghi với yêu cầu thay đổi của ứng dụng. Hoạt động cấu hình lại được thực hiện nhờ vào bộ điều khiển cấu hình và vi xử lý nhúng được đặt trong phần tĩnh. Bộ điều khiển cấu hình kết nối bộ nhớ ngoài CF hoặc bộ nhớ SDRAM DDR3 với ICAP thông qua Bus AXI/PLB. Bộ nhớ ngoài CF được sử dụng để lưu trữ các file cấu hình từng phần đã được tổng hợp trước dựa trên phân tích các đặc tính của ứng dụng. Để thực hiện một quá trình cấu hình, bộ điều khiển sẽ đọc file cấu hình mong muốn từ bộ nhớ ngoài CF hoặc bộ nhớ 11 SDRAM DDR3 để ghi vào ICAP, tiếp theo dữ liệu sẽ được đọc từ ICAP để ghi vào bộ nhớ cấu hình của FPGA. Khu vực độngKhu vực tĩnh Microblaze Processor Uart SysACE CompactFlash HWICAP AXI/PLB BUS Timer Flash Memory Host NoC DDR3 Phần không cần cấu hình Phần cấu hình Hình 2.19. Sơ đồ khối tổng quát của hệ thống Trong nghiên cứu này, tác giả sử dụng hai phương pháp cấu hình. Phương pháp thứ nhất, thực hiện cấu hình từ bộ nhớ ngoài CF. Ưu điểm của phương pháp này là tài nguyên mà hệ thống sử dụng nhỏ. Tuy nhiên, tốc độ thực hiện cấu hình chậm vì độ rộng bus dữ liệu của bộ nhớ CF bé (8 bit). Phương pháp thứ hai, thực hiện cấu hình từ bộ nhớ SDRAM DDR3. Phương pháp này có tốc độ cấu hình cao hơn phương pháp cấu hình từ CF vì bộ nhớ SDRAM DDR3 có tốc độ hoạt động và độ rộng Bus dữ liệu lớn hơn bộ nhớ CF. Tuy nhiên, hệ thống phải sử dụng tài nguyên nhiều hơn. 2.3.2. Kết quả thực nghiệm Thiết kế của tác giả được thực hiện và thử nghiệm trên Kit FPGA Virtex-6 dòng chip XC6VLX240T với hai loại Bus PLB/AXI cho các giải pháp nghiên cứu đã được trình bày ở trên. Tần số hoạt động của hệ thống tại 100 MHz, tốc độ truyền nối tiếp giữa máy tính và FPGA là 115.200 baud thông qua cổng UART. Các công cụ hỗ trợ thiết kế gồm ISE, XPS, SDK và PlanAhead phiên bản 14.1 của Xilinx. Tài nguyên phần cứng của các hệ thống tương ứng với bus PLB, AXI và AXI + DDR3 được chỉ ra như Bảng 2.6. Bảng 2.6. Tài nguyên sử dụng của hệ thống Tài nguyên Sẵn có PLB AXI AXI + DDR3 Sử dụng % Sử dụng % Sử dụng % Register 301440 4249 1,41 4257 1,41 15347 5,10 LUT 150720 4243 2,82 4948 3,28 14763 9,79 Slice 37680 1904 5,05 1915 5,08 6949 18,44 Các file cấu hình của bộ đệm ngõ vào, bộ định tuyến, mạng NoC 2x2 và các PE trong NoC được tổng hợp và tạo ra bởi công cụ PlanAhead. Thời gian và tốc độ cấu hình cho từng kịch bản cụ thể được hệ thống đo đạt như trong Bảng 2.7. Dễ thấy rằng hệ thống sử dụng Bus AXI có thời gian cấu hình nhỏ hơn, tốc độ cấu hình nhanh hơn so với Bus PLB. Đối với hệ thống cải tiến AXI + DDR3, các file cấu hình được đọc trực tiếp từ bộ nhớ RAM DDR3 nên tốc độ cấu hình được cải thiện hơn 5 lần so với trường hợp các file cấu hình được đọc từ bộ nhớ ngoài CF vì độ rộng bus dữ liệu của bộ nhớ RAM DDR3 lớn hơn. Tuy nhiên, hệ thống này tiêu tốn khá nhiều tài nguyên. Do vậy, tùy theo yêu cầu về QoS của từng miền ứng dụng mà chúng ta có thể lựa chọn loại hệ thống cấu hình phù hợp để thực hiện. 12 Bảng 2.7. Thời gian và tốc độ cấu hình của hệ thống Thông số cấu hình Cấu hình buffer 1 Router mạng 2x2 Cả mạng 2x2 1 PE của mạng 2x2 PLB AXI AXI+DDR3 AXI+DDR3 Bitstream size (Kb) 36 36 36 209 450 108 Thời gian cấu hình (s) 0,074 0,071 0,012 0,068 0,147 0,035 Tốc độ cấu hình (Mb/s) 0,498 0,519 3,070 3,070 3,070 3,070 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 3.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. Xu hướng triển khai nhiều ứng dụng và tích hợp nhiều tính năng lên chúng ngày càng gia tăng trong khi tài nguyên của chúng luôn bị giới hạn. Điều này đòi hỏi người thiết kế phải có những giải pháp linh hoạt và hiệu quả. Các FPGA hiện đại không ngừng tăng số lượng tài nguyên trên nó, giá thành tiếp tục giảm, các tính năng mới được tích hợp đặc biệt là khả năng cấu hình lại từng phần động. Do vậy, FPGA là một lựa chọn thích hợp để phát triển nhanh một nền tảng nhúng đa lõi linh hoạt và có hiệu năng cao. Theo hướng này, một số hệ thống nhúng dựa trên FPGA đã được phát triển để hỗ trợ cho các ứng dụng đa phương tiện và các ứng dụng xử lý tín hiệu [30, 38, 48, 54, 58]. Các ứng dụng này thường yêu cầu cơ sở hạ tầng truyền thông hiệu năng cao và có khả năng xử lý dữ liệu nhanh. Nhằm cung cấp một cơ sở hạ tầng truyền thông hiệu năng cao để kết nối các phần tử xử lý (PE) khác nhau của một SoC phức tạp, mạng trên chip đã được đề xuất như là một thay thế cho các kiến trúc truyền thống như Bus và kết nối điểm-điểm [9, 75]. Ngoài ra, 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 dựa trên NoC đã chứng minh là có nhiều ưu điểm hơn so với các 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 trên FPGA đượ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 FPGA 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, nhiều ứng dụng đượ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 các nền tảng phần cứng. Do vậy, trong phần này, tác giả xem xé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 tự cấu hình lại động dựa trên NoC không đồng nhất với ràng buộc tài nguyên trong khi vẫn đảm bảo QoS tổng thể tối đa cho các ứng dụng. 3.2. Các định nghĩa và xây dựng bài toán ánh xạ 3.2.1. Mô hình ứng dụng Một vấn đề lớn trong mô phỏng mạng đó là khó có thể chạy chính xác các ứng dụng thực tế trong mô phỏng vì mô phỏng mạng không có khả năng thực thi các mã nhị phân. Do đó, trực tiếp chạy các ứng dụng thực tế trên mô hình kiến trúc NoC không phải là điều dễ dàng thực hiện. Thay vì mô phỏng các ứng dụng thực tế. Một mô hình lưu lượng cung cấp một phân bố thống kê của truyền thông là một giải pháp đơn giản để mô hình và thực hiện nhanh các mô phỏng. Điều này có thể cung cấp các kết quả hữu ích trong giai đoạn đầu của sự phát triển một dự án NoC. Do vậy, trong nghiên cứu này tác giả sử dụng đồ thị tác vụ như trong [25, 66] để mô hình một ứng dụng. 13 Mỗi ứng dụng có một đồ thị tác vụ cố định và chất lượng của mỗi ứng dụng có thể được điều chỉnh bằng cách thay đổi số lượng dữ liệu được xử lý bằng đồ thị tác vụ ngõ vào. Ví dụ, trong một ứng dụng đồ họa 3D các công cụ hiển thị hình ảnh 3D là cố định và phụ thuộc vào số lượng tam giác sử dụng để biểu diễn cho một đối tượng 3D, ta có thể có các chất lượng khác nhau cho các đối tượng đó [70]. Một ví dụ điển hình khác là một ứng dụng truyền tải video qua giao thức http trong [52], trong đó các bộ giải mã video là cố định và số lượng các bit dữ liệu được sử dụng để biểu diễn nội dung video sẽ xác định chất lượng của video được giải mã. 3.2.1.1. Đồ thị tác vụ ứng dụng Định nghĩa 1: Một đồ thị tác vụ ứng dụng được biểu diễn như một đồ thị vô hướng  ,ATG V E , trong đó V là tập các tác vụ ứng dụng và E là tập tất cả các cạnh, mỗi cạnh trong đồ thị được kết nối giữa 2 tác vụ như Hình 3.3. Mỗi đỉnh kv V là một tác vụ với bộ thông số  id type comp reqcomp, , ,t t t t . Trong đó, idt là thông số nhận dạng; typet là kiểu tác vụ (tác vụ phần cứng HWt hoặc tác vụ phần mềm SWt ), các tác vụ phần cứng được tạo ra từ ngôn ngữ phần cứng HDL và các tác vụ phần mềm được tạo ra từ ngôn ngữ lập trình bậc cao như C/C++; compt là thời gian tính toán của tác vụ khi nó thực hiện trên tài nguyên phần cứng hoặc phần mềm. Một tác vụ được thực hiện trên tài nguyên phần cứng sẽ có thời gian tính toán nhỏ hơn khi nó thực hiện trên tài nguyên phần mềm [24, 69]; reqcompt là thời gian yêu cầu tối thiểu để thực hiện hoàn thành một tác vụ trên tài nguyên phần cứng hoặc phần mềm. Mỗi cạnh rse biểu diễn mối quan hệ giữa tác vụ rv và sv . Nó có các thông số như   comm reqcomm, , rst t e . Trong đó, commt là trễ truyền thông khi truyền các gói tin từ tác vụ rv đến sv ; reqcommt là yêu cầu trễ truyền thông tối thiểu khi truyền các gói tin từ tác vụ rv đến sv ; và  rse là một hàm trọng lượng đại diện cho tốc độ truyền thông giữa các tác vụ. 3.2.1.2. Mô hình chất lượng Giả sử có M ứng dụng 1 2 3, , ,..., MA A A A cùng chạy trên một thiết bị, mỗi ứng dụng iA có iN mức chất lượng 1 2 3, , ,..., ii i i iNQ Q Q Q . Mỗi mức chất lượng yêu cầu một tập các tài nguyên bao gồm thời gian tính toán, thời gian truyền thông, diện tích phần cứng và năng lượng. Mức chất lượng cao hơn sẽ yêu cầu tài nguyên nhiều hơn [67, 69]. Ví dụ, giả sử ứng dụng 1A có các mức chất lượng 111 12 13 1N Q Q Q Q   thì thời gian cần thực hiện ứng dụng tại mỗi mức chất lượng tương ứng sẽ là 111 12 13 1N t t t t   . Mỗi mức chất lượng ijQ cung cấp cho người xem một cảm giác chất lượng, cảm giác chất lượng này có thể biểu diễn bởi một giá trị lợi ích ijB . Tác giả sử dụng mô hình biểu diễn mối quan hệ giữa giá trị lợi ích và mức chất lượng của ứng dụng như đã trình bày trong [67]. Ứng dụng đạt mức chất lượng cao hơn thì sẽ có giá trị lợi ích lớn hơn. Ngược lại, mức chất lượng thấp hơn thì giá trị lợi ích sẽ thấp hơn. Tổng quát, ứng dụng iA có các mức chất lượng 1 2 3 ii i i iN Q Q Q Q   thì giá trị lợi ích tương ứng sẽ là  1 2 3 0 1ii i i iNB B B B B     . 14 Reconfigurable platform R V11 R R ISP R R R R R R V12 V13 V14 RR RRRR RR (PE) App1 úúú App2 App3 AppM Q11, Q12, ,Q1Ni Quality levels Application task graph V11 V12 V14V13 7 5 6 [10,15] [4,6] [6,9] [8,12] Mapping p h y si ca l co n n ec ti o n Hình 3.3. Mô hình hệ thống 3.2.2. Mô hình phần cứng Nền tảng phần cứng được xem xét là một nền tảng cấu hình lại được không đồng nhất được thực hiện trên FPGA Virtex-6 dựa trên mô hình NoC đã được phát triển trong Chương 2 (này tảng này cũng có thể phát triển trên một KIT khác có tốc độ làm việc cao hơn như Zynq-7000). Nền tảng bao gồm một vi xử lý nhúng ISP (Microblaze) và các PE phần cứng cấu hình lại được, chúng được kết nối với nhau qua mạng truyền thông NoC. Trong chương này, tác giả chỉ xem xét tái cấu hình cho các PE phần cứng, kiến trúc truyền thông của NoC được giữ cố định trong phần tĩnh của FPGA (Hình 3.3). Mỗi PE có thể hỗ trợ tác vụ phần cứng hoặc phần mềm. Tác vụ phần mềm được thực hiện trên ISP, trong khi tác vụ phần cứng được thực hiện trên các PE cấu hình lại được. Tác giả giả định rằng mỗi PE phần cứng có khả năng hỗ trợ chỉ một tác vụ. Trong khi đó, vi xử lý nhúng ISP có thể hỗ trợ một hoặc nhiều hơn một tác vụ và chịu trách nhiệm quản lý hệ thống bao gồm ánh xạ tác vụ, lập lịch tác vụ, kiểm soát tài nguyên và điều khiển cấu hình lại. Định nghĩa 2: Một nền tảng cấu hình lại dựa trên NoC được biểu diễn bởi một đồ thị  , NoC N P L trong đó, P là tập các phần tử xử lý PE, và L là tập các kết nối vật lý giữa 2 bộ định tuyến. Mỗi PE xyp P được biểu diễn bởi các thông số  id add type use, , ,p p p p , trong đó idp là PE nhận dạng, addp là địa chỉ PE, typep là kiểu PE gồm có PE cứng HWp và PE mềm SWp , và usep là trạng thái của PE (rỗi và bận). 3.2.3. Xây dựng bài toán ánh xạ Tác giả xem xét bài toán ánh xạ với M ứng dụng được triển khai đồng thời hoặc tuần tự lên nền tảng phần cứng. Các ứng dụng này có thể biết trước, tuy nhiên, thứ tự xuất hiện của chúng là không biết trước và không phụ thuộc nhau. Mục tiêu của ánh xạ là đạt được chất lượng dịch vụ tổng thể cực đại của M ứng dụng khi triển khai chúng lên nền tảng với các ràng buộc tài nguyên. Giả sử compijkt là thời gian tính toán của tác vụ ikv của ứng dụng iA trên PE xyp tại mức chất lượng ijQ . Khi đó tổng thời gian tính toán cho ứng dụng iA tại mức chất lượng ijQ trên các PE là: 15 comp comp 1 i ij ijk L k t t   Trong đó, iL là số tác vụ của ứng dụng iA . Giả sử commijrst là trễ truyền thông từ tác vụ irv đến tác vụ isv trong ứng dụng iA tại mức chất lượng ijQ . Khi đó tổng trễ truyền thông trong ứng dụng iA tại mức chất lượng ijQ sau khi ánh xạ sẽ là: comm comm (( , ), (x', y')) i i ij ijrs L L rs r s t t dist x y  Trong đó, 1rs  nếu có một kết nối giữa tác vụ irv và isv , 0rs  cho các trường hợp còn lại.     , , '’, ’ 'dist x y x y x x y y    là khoảng cách Manhattan (MD) từ PE xyp đến ' 'x yp . Tổng thời gian thực hiện của ứng dụng iA tại mức chất lượng ijQ được tính bởi công thức: comp commij ijij t t t  Giả sử i đại diện cho mức độ ưu tiên của ứng dụng. Lúc đó, bài toán ánh xạ có thể được xây dựng như sau: Giả sử có M ATG ứng dụng đưa vào hệ thống đồng thời hoặc tuần tự và trạng thái của nền tảng phần cứng. Tìm một hàm ánh xạ:    , ,A V E N P L ,   , ,ik xy ik xyMap v p v V p P   với các mục tiêu 1 max 1 i NM i ij ij i j B B M             1 1 min iNM ij ij i j T t           Thỏa mãn các điều kiện: 1 1 iN ij j    , 1ij  nếu ijQ được lựa chọn, 0 cho các trường hợp khác. HW HW comp reqcomp comm reqcomm ij ij ij ij t p t t t t         Cần lưu ý rằng, biểu thức (3.4) là mục tiêu chính của bài toán ánh xạ. Khi Bmax được tìm thấy, biểu thức (3.5) sẽ được sử dụng để tìm một giải pháp vị trí đặt các tác vụ tối ưu. 3.3. 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 3.3.1. Giải pháp tối ưu sử dụng thuật toán tìm kiếm đầy đủ 3.3.1.1. Thuật toán Trong phần này, tác giả đề xuất giải pháp tối ưu đơn giản cho bài toán ánh xạ với việc xem xét nền tảng phần cứng có kích thước nhỏ, số lượng ứng dụng triển khai lên nền tảng không lớn, số mức chất lượng của mỗi ứng dụng nhỏ. Trong trường hợp như vậy, thuật toán tìm kiếm đầy đủ có thể sử dụng để tìm ra giải pháp tối ưu cho bài toán ánh xạ đã được xây dựng như Mục 3.2.3 là hoàn toàn khả thi. Mã của thuật toán tìm kiếm đầy đủ được trình bày như Thuật toán 1. (3.1) (3.2) (3.3) (3.4) (3.5) (3.6) 16 Thuật toán 1: Giải pháp tối ưu sử dụng thuật toán tìm kiếm đầy đủ Input: A(V,E), N(P,L) // task ; PE Output: tmpg (mapping A(V,E)  N(P,L)) 1: BEGIN 2: Set benefit_max  0; time_min  ∞; tmpg  NULL; 3: Generate all possible mapping A(V,E)  N(P,L); // number of hard task <= number of hard PE; 4: for all mapping tmpgj in step 3 do 5: for all application Ai do 6: Set benefit_Ai  highest_benefit; 7: Call verification_Ai (benefit_Ai); 8: while constraint is not verified do 9: if benefit_Ai == lowest_benefit then 10: break; 11: end if 12: benefit_Ai = benefit_Ai - 1; 13: verification_Ai (benefit_Ai); 14: end while 15: end for 16: if ((benefit_Ai > benefit_max) and (time_Ai < time_min)) then 17: benefit_max  benefit_Ai; 18: time_min  time_Ai; 19: tmpg = tmpgj; 20: end if 21: end for 22: return tmpg has the highest benefit and the sum of time of all application is the lowest; 23: END 3.3.1.2. Kết quả mô phỏng và đánh giá Để đánh giá giải pháp đề xuất, một vài kịch bản mô phỏng sẽ được thực hiện. Trong giải pháp này, một nền tảng NoC cấu hình lại được đã được trình bày ở Mục 3.2.2 với kích thước 3x3, bao gồm 1 ISP và 8 vùng cấu hình lại sẽ được sử dụng. Có 3 ứng dụ