Tóm tắt Luận án tiến sĩ Kỹ thuật: 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

Chia sẻ: Trần Văn Nan | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

32
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề 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ộ 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 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Kỹ thuật: 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 Chuyên ngành: Kỹ thuật điện tử Mã số: 62520203 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐIỆN TỬ Hà Nội – 2017
Công trình này được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: PGS.TS. PHẠM NGỌC NAM Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Trường họp tại Trường Đại học Bách khoa Hà Nội Vào hồi … giờ … , ngày … tháng … năm 2017 Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam
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ó 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
2 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à 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. 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]. 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, phạm vi và phƣơng pháp nghiên cứu Mục tiêu nghiên cứu: (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ộ giao tiếp mạng. (ii) 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 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. (iii) 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. Phạm vi nghiên cứu:
3 (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. (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ụ. 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ế. 3. Cấu trúc của luận án Cấu trúc của luận án bao gồm ba chương: Chương 1 trình bày lý thuyết liên quan đến các nội dung nghiên cứu của luận án. Chương 2 phát triển nền tảng phần cứng cấu hình lại được cho NoC. 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. CHƢƠNG 1 CƠ SỞ LÝ THUYẾT 1.1. Lý thuyết về mạng trên chip Với sự phát triển không ngừng của công nghệ bán dẫn và công nghệ nano, số lượng các ứng dụng được tích hợp lên chip ngày càng tăng. Kiến trúc Bus và kết nối điểm-điểm truyền thống không còn đáp ứng được yêu cầu này vì chúng có một số hạn chế trong khả năng mở rộng, khả năng sử dụng lại các IP, đồng bộ, v.v. [35, 55]. Kiến trúc NoC đã được đề xuất 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. 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, 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. Ý tưởng xây dựng NoC bắt nguồn từ mô hình mạng máy tính đã được phát triển trong lịch sử của hệ thống máy tính. Hình 1.1 mô tả một NoC điển hình dạng lưới hai chiều 3x3. Tiếp theo, các thuật ngữ thường được sử dụng trong NoC sẽ được trình bày. Tài nguyên (Resource) hay lõi IP (IP core) hoặc PE (Processing Element): Là các khối logic thực hiện xử lý dữ liệu trong mạng. Khối logic này có thể là một lõi vi xử lý, một bộ biến đổi FFT (Fast Fourier Transform), một lõi xử lý DSP (Digital Signal Processor), v.v. Bộ giao tiếp mạng (NI: Network Interface): Là khối logic làm nhiệm vụ 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. 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, 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ộ định tuyến (Router): Là khối logic thực hiện chức năng định tuyến, điều khiển luồng cho dòng dữ liệu trong mạng. Đóng vai trò là hạt nhân trong NoC với mỗi mô hình NoC khác nhau, bộ
4 định tuyến được thiết kế riêng để thực hiện thuật toán định tuyến, cơ chế điều khiển luồng riêng biệt. Liên kết vật lý (Physical link): Là các kết nối vật lý giữa các bộ định tuyến trong mạng NoC. Liên kết bao gồm các đường truyền dữ liệu và các tín hiệu điều khiển/báo hiệu. Cấu hình mạng (Topology): Là cấu trúc hình học của NoC, cấu trúc hình học này sẽ quyết định cách liên kết giữa các bộ định tuyến với nhau, giải thuật định tuyến và thậm chí cả cơ chế điều khiển luồng. Định tuyến (Routing): Là cơ chế tìm đường đi cho gói tin (Packet) từ tài nguyên nguồn đến tài nguyên đích thông qua các kết nối trong mạng. Điều khiển luồng (Flow control): Là cơ chế cấp phát tài nguyên bộ đệm, liên kết cho gói tin khi gói tin đang truyền trong mạng. Độ trễ (Latency): Là thời gian cần thiết để truyền một gói tin đi từ nguồn đến đích. Trong NoC, có nhiều yếu tố ảnh hưởng tới độ trễ bao gồm trễ do định tuyến, độ chiếm dụng kênh, trễ do tranh chấp tài nguyên, thời gian ghép và tách gói tin (packetization and depacketization), thời gian ghép và tách flit (flitization and deflitization), sự đồng bộ giữa các bộ định tuyến. Băng thông (Bandwidth): Là tốc độ cao nhất của luồng thông tin trong mạng được đo bằng số bit/giây. Thông lượng (Throughput): Là tổng số gói tin đến được đích của chúng trên mỗi đơn vị thời gian. IP core IP core IP core (0,0) (0,1) (0,2) I I I N N N Router Router Router Physical links IP core IP core IP core (1,0) (1,1) (1,2) I I I N N N Router Router Router IP core IP core IP core (2,0) (2,1) (2,2) I I I N N N Router Router Router Hình 1.1. Cấu trúc của một NoC dạng lưới 3x3 1.2. Công nghệ FPGA FPGA là một mạch tích hợp đặc biệt (IC: Integrated Circuit) được thiết kế để cấu hình bởi các nhà thiết kế sau khi nó được chế tạo để đạt được các tùy chọn về chức năng logic hoặc số học. FPGA được giới thiệu lần đầu tiên vào thị trường IC thương mại năm 1985 bởi Xilinx. Ngày nay, FPGA đang được sử dụng rộng rãi trong các lĩnh vực và đóng vai trò quan trọng trong các thiết kế nhúng hiện đại. Các sản phẩm FPGA hiện đại [26] tận dụng các tiến bộ công nghệ bán dẫn, kết hợp cả hai phần tử Logic lập trình (LE: Logic Element) và các lõi IP cứng trên cùng một đế bán dẫn, đặc biệt với khả năng cấu hình lại động từng phần giúp FPGA có thể thay đổi các chức năng đã được thực hiện trên thiết bị vật lý tại thời gian chạy mà không cần phải dừng hệ thống. Chúng cung cấp đầy đủ các khả năng của chip và thiết kế thuận tiện. Do vậy, FPGA là một nền tảng hứa hẹn để tạo mẫu nhanh chóng cho một hệ thống trên một FPGA (System-on-an-FPGA)[6], trong đó có bộ vi xử lý, bộ điều khiển bộ nhớ, các bộ tăng tốc phần cứng cũng như các bộ điều khiển thiết bị ngoại vi, v.v. 1.3. Kỹ thuật ánh xạ ứng dụng lên nền tảng mạng trên chip 1.3.1. Bài toán ánh xạ
5 Bài toán ánh xạ ứng dụng lên nền tảng NoC đã được xây dựng trong [39] đó là quá trình gán các tác vụ của ứng dụng vào các PE của Noc. Nó là một trường hợp của phép gán bậc hai (quadratic assignment) đã được chứng minh là một vấn đề NP-hard [31]. Không gian tìm kiếm tăng giai thừa lần theo kích thước hệ thống. Ví dụ, một NoC có kích thước 8x8, theo lý thuyết có thể có 64! trường hợp ánh xạ. M! Tổng quát, nếu ánh xạ N tác vụ vào M nút mạng (NM) thì có thể có trường hợp  M  N ! ánh xạ các tác vụ vào các nút của NoC. Trong trường hợp số tác vụ bằng số nút mạng (M=N) thì số trường hợp ánh xạ trở thành M!. Ánh xạ có ảnh hưởng trực tiếp đến hiệu năng của NoC như độ trễ, thông lượng, tiêu thụ điện năng, năng lượng, v.v. Vì vậy cần phải có các kỹ thuật ánh xạ hiệu quả để tối ưu các thông số này. Kỹ thuật ánh xạ phụ thuộc vào các yếu tố sau đây: (i) Mô hình ứng dụng (ví dụ: Task Graph [25], Data Flow Graph [88], v.v.) (ii) Mô hình kiến trúc nền tảng phần cứng (ví dụ: Nền tảng đồng nhất, không đồng nhất, số lượng PE và loại PE, v.v.) (iii) Các tham số ràng buộc của ứng dụng (ví dụ: Hiệu năng tính toán, trễ truyền thông, mức chất lượng, v.v.) (iv) Mô hình thực hiện truyền thông giữa các PE (ví dụ: Thời gian thực hiện, năng lượng tiêu thụ, v.v.) (v) Ước lượng thời gian thực hiện trên các PE khác nhau. Bài toán ánh xạ các tác vụ của ứng dụng lên nền tảng NoC có thể được thực hiện tại thời gian thiết kế (design-time) hoặc sau khi thiết kế tức là khi hệ thống đang hoạt động (run-time). Đối với kỹ thuật ánh xạ tại thời gian thiết kế hay gọi là ánh xạ tĩnh thì kiến trúc nền tảng và ứng dụng đã được biết trước, vì vậy chúng không phù hợp cho việc thêm các ứng dụng mới vào hệ thống tại thời gian chạy. Đối với kỹ thuật ánh xạ tại thời gian chạy hay gọi là ánh xạ động thì gần như các ứng dụng đều có thể chạy trên hệ thống khi hệ thống đang hoạt động, kỹ thuật này là một giải pháp phù hợp cho việc triển khai nhiều ứng dụng lên hệ thống có tài nguyên giới hạn. Sau khi ánh xạ các tác vụ lên hệ thống thì một số tác vụ đã được ánh xạ có thể được điều chỉnh vị trí, nếu yêu cầu người dùng thay đổi hoặc có ứng dụng mới đưa vào hệ thống. Trong phần tiếp theo, các kỹ thuật ánh xạ tĩnh và ánh xạ động sẽ thảo luận chi tiết hơn. Tuy nhiên, luận án này sẽ tập trung vào kỹ thuật ánh xạ động, do đó chúng ta nghiên cứu sâu hơn về kỹ thuật này. 1.3.2. Ánh xạ tại thời gian chạy Ngược lại với ánh xạ tại thời gian thiết kế là kỹ thuật ánh xạ tại thời gian chạy. Kỹ thuật này yêu cầu xem xét về thời gian để ánh xạ các tác vụ bởi vì nó làm tăng tổng thời gian thực hiện của ứng dụng. Do đó, thuật toán tham lam thường được sử dụng để ánh xạ hiệu quả nhằm tối ưu các thông số như năng lượng tiêu thụ, độ trễ truyền thông, thời gian thực hiện, v.v. Một vài ưu điểm của ánh xạ động so với ánh xạ tĩnh được tóm tắt như sau: (i) Khả năng thích nghi với nguồn tài nguyên sẵn có: Các nguồn tài nguyên sẵn có sẽ thay đổi khi các ứng dụng được đưa vào hệ thống lúc đang hoạt động.
6 (ii) Khả năng cho phép nâng cấp hệ thống: Nó có thể nâng cấp hệ thống để cho phép ứng dụng mới có thể hoạt động được hoặc thay đổi các tiêu chuẩn mà không được biết đến tại lúc thiết kế, thậm chí sau khi đã đưa tới tay người dùng. (iii) Khả năng để tránh các phần bị hỏng trong một nền tảng: Nếu một hoặc nhiều PE hoạt động không đúng chức năng sau khi sản xuất, hoặc theo thời gian làm cho một số phần tử xử lý bị hỏng mà chúng ta không thể biết trước tại lúc thiết kế thì các bộ phận lỗi đó có thể bị vô hiệu hóa trước khi thực hiện quá trình ánh xạ [61]. Khi các ứng dụng đã được ánh xạ bắt đầu thực thi, quá trình ánh xạ một hoặc nhiều ứng dụng đang chạy cần phải được xem xét các vấn đề sau: (i) Một ứng dụng mới được đưa vào hệ thống và nó cần tài nguyên từ các ứng dụng vừa mới thực hiện. (ii) Các thông số của một ứng dụng đang chạy được sửa đổi. (iii) Một ứng dụng đang chạy cần phải kết thúc để giải phóng tài nguyên chiếm giữ. (iv) Yêu cầu hiệu năng của một ứng dụng đang chạy bị thay đổi. Điều này có thể cần thêm tài nguyên để thực hiện các chức năng bổ sung. (v) Quá trình ánh xạ hiện tại là không đủ tối ưu, nó yêu cầu ánh xạ lại. Những vấn đề nêu trên chỉ có thể được giải quyết bằng các kỹ thuật ánh xạ tại thời gian chạy. 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. Thiết kế bộ định tuyến cho NoC Mạng trên chip được đề xuất như một giải pháp cho truyền thông giữa các IP trong thiết kế các hệ thống trên chip phức tạp. Tránh bế tắc, cắt giảm tắc nghẽn để tăng hiệu năng cho mạng là những thử thách lớn khi thiết kế NoC bởi vì chúng ảnh hưởng trực tiếp đến hiệu năng toàn mạng. Để giải quyết các vấn đề này, các bộ định tuyến thường sử dụng kiến trúc kênh ảo đều tại mỗi cổng. Trong mục này, tác giả đề xuất một kiến trúc cho bộ định tuyến sử dụng điều khiển luồng wormhole kết hợp với số lượng kênh ảo không đều trên cổng tại ngõ ra để cắt giảm chi phí nhưng vẫn đảm bảo “deadlock free” và hiệu năng trong trường hợp lưu lượng dữ liệu đi qua mạng là cao nhất. Chi phí và hiệu năng của bộ định tuyến đã đề xuất sẽ được phân tích, đánh giá và so sánh với các bộ định tuyến sử dụng 2 và 4 kênh ảo. 2.1.1. Đề xuất kiến trúc bộ định tuyến Kiến trúc bộ định tuyến sử dụng cấu hình mạng hai chiều dạng lưới (2D-Mesh), chuyển mạch gói, điều khiển luồng wormhole kết hợp với kênh ảo không đều trên cổng và thuật toán định tuyến XY. Bộ định tuyến có 5 cổng gồm cổng Bắc (N), Nam (S), Đông (E), Tây (W) và cổng nội bộ L. Tại mỗi cổng, dữ liệu có thể truyền theo hai hướng và có độ rộng là 34 bit. Kích thước của mỗi flit là 34 bit gồm 32 bit dữ liệu và 2 bit còn lại sử dụng cho nhận dạng loại flit. Có 3 loại flit: Flit tiêu đề (header flit), flit thân (body flit) và flit đuôi (end flit). Kiến trúc đề xuất của bộ định tuyến như Hình 2.3, bao gồm 5 khối chính: Bộ đệm ngõ vào (FIFO), bộ giải mã flit (Flit decoder), chuyển mạch (Switch), kênh ảo và bộ phân xử (Arbiter). Bộ đệm ngõ vào dùng để lưu trữ tạm thời các flit. Bộ giải mã flit thực hiện chức năng nhận, phân tích thông tin định tuyến trong flit tiêu đề và đưa ra thông tin định tuyến đến các ngõ ra cho gói tin. Chuyển mạch thực hiện chức năng kết nối đường chuyển dữ liệu đến đúng ngõ ra tương ứng theo tín hiệu điều khiển từ khối giải mã flit. Kênh ảo được thiết kế giống như các FIFO dùng để lưu trữ tạm thời các flit khi các flit chưa được cấp phát kênh vật lý.
7 Switch VC 0 34 N N 34 d_in N Flit VC 1 Arbiter d_out FIFO 4 to1 ack_out decoder VC 2 ack_in req_in VC 3 req_out VC 0 S 34 34 S d_in S Flit VC 1 Arbiter d_out FIFO 4 to1 ack_out decoder VC 2 ack_in req_in VC 3 req_out E 34 34 E d_in E Flit VC 0 Arbiter FIFO d_out ack_out decoder VC 1 2 to1 ack_in req_in req_out W 34 34 W d_in W Flit VC 0 Arbiter d_out FIFO VC 1 2 to1 ack_in ack_out decoder req_out req_in VC 0 34 L L 34 d_in L Flit VC 1 Arbiter d_out FIFO 4 to1 ack_out decoder VC 2 ack_in req_in VC 3 req_out Hình 2.3. Kiến trúc bộ định tuyến đề xuất Bộ phân xử thực hiện nhiệm vụ điều tiết các kênh ảo khi có yêu cầu truyền flit để cấp phát kênh vật lý, tương ứng. Quá trình vận chuyển các flit từ ngõ vào đến ngõ ra của bộ định tuyến được diễn ra như sau: Các flit đi vào bộ đệm FIFO và được lưu trữ tạm thời tại đây. Các tín hiệu bắt tay req_in và ack_out sẽ thông báo đến bên gửi tình trạng sẵn sàng ghi và ghi dữ liệu thành công vào FIFO. Tiếp theo các flit sẽ được đưa vào bộ giải mã flit. Tại đây địa chỉ nguồn và địa chỉ đích chứa trong flit tiêu đề được phân tích để đưa ra tín hiệu điều khiển hướng đi cho các flit. Tiếp theo bộ chuyển mạch sẽ dựa vào các tín hiệu điều khiển được tạo ra từ bộ giải mã flit để tiếp tục chuyển dữ liệu đến các ngõ ra và đưa vào các kênh ảo tương ứng. Cuối cùng, bộ phân xử sẽ lựa chọn và cấp phát kênh vật lý cho flit để truyền các flit đến các bộ định tuyến đích đến khi toàn bộ gói tin đượ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 2 kênh ảo Tác giả 4 kênh ảo Logic Utilization Sẵn có 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 Kiến trúc NI 32 bits 32 bits FIFO A wr_en_FFA empty_FFA full_FFA full_FFA empty_FFA rd_en_FFA release_FFA release_FFA Core_data release_FFB release_FFB A/B_select Data_router Flitilizer pkt_size Flit_type 32 bits C2R_WRITE_CTRL C2R_READ_CTRL 34 bits core_req state_FFA state_FFA req_router core_req state_FFB state_FFB req_router ack_core router_ack ack_core wr_en_FFB empty_FFB full_FFB full_FFB empty_FFB rd_en_FFB router_ack 32 bits 32 bits FIFO B 32 bits 32 bits FIFO A rd_en_FFA empty_FFA full_FFA full_FFA empty_FFA wr_en_FFA release_FFA release_FFA pkt_size De-flitilizer Data_core release_FFB release_FFB Router_Data A/B_select flit_en Mux 32 bits 34 bits R2C_READ_CTRL R2C_WRITE_CTRL core_ack state_FFA state_FFA ack_router Core_ack state_FFB state_FFB ack_router req_core router_req req_core rd_en_FFB empty_FFB full_FFB full_FFB empty_FFB wr_en_FFB router_req 32 bits 32 bits FIFO B 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ộ 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. 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 NI - 1 FIFO Tác giả Logic Sẵn có Đã sử Đã sử Utilization % % dụng 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
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 NI-1 [4] Các nghiên cứu Tác giả FIFO 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. Flash Memory SysACE Timer CompactFlash Phần không Microblaze Phần cấu Processor AXI/PLB BUS cần cấu hình hình Uart HWICAP DDR3 NoC Khu vực tĩnh Khu vực động Host 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 PLB AXI AXI + DDR3 Tài nguyên Sẵn có Sử Sử Sử % % % dụng dụng 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 Cấu hình buffer 1 Router Cả mạng 1 PE của Thông số cấu hình mạng 2x2 2x2 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 vk V là một tác vụ với bộ thông số tid , ttype , tcomp , treqcomp . Trong đó, tid là thông số nhận dạng; ttype là kiểu tác vụ (tác vụ phần cứng tHW hoặc tác vụ phần mềm tSW ), 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++; tcomp 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]; treqcomp 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 ers biểu diễn mối quan hệ giữa tác vụ vr và vs . Nó có các thông số như t comm , treqcomm ,   ers   . Trong đó, tcomm là trễ truyền thông khi truyền các gói tin từ tác vụ vr đến vs ; treqcomm 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ụ vr đến vs ; và   ers  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 A1 , A2 , A3 ,..., AM cùng chạy trên một thiết bị, mỗi ứng dụng Ai có N i mức chất lượng Qi1 , Qi 2 , Qi 3 ,..., QiNi . 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 A1 có các mức chất lượng Q11  Q12  Q13    Q1N1 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à t11  t12  t13    t1N1 . Mỗi mức chất lượng Qij 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 Bij . 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 Ai có các mức chất lượng Qi1  Qi 2  Qi 3    QiNi thì giá trị lợi ích tương ứng sẽ là Bi1  Bi 2  Bi 3    BiNi  0  B  1 .
14 App1 App2 App3 úúú AppM Q11, Q12, …,Q1Ni Quality levels [10,15] V11 7 5 6 V12 V13 V14 [4,6] [6,9] [8,12] Application task graph Mapping V12 V11 V13 R R R physical connection RR V14 RR (PE) R R R ISP RR RR R R R Reconfigurable platform 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 pxy  P được biểu diễn bởi các thông số pid , padd , ptype , puse  , trong đó pid là PE nhận dạng, padd là địa chỉ PE, ptype là kiểu PE gồm có PE cứng pHW và PE mềm pSW , và puse 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ử tcompijk là thời gian tính toán của tác vụ vik của ứng dụng Ai trên PE pxy tại mức chất lượng Qij . Khi đó tổng thời gian tính toán cho ứng dụng Ai tại mức chất lượng Qij trên các PE là:
15 Li tcompij   tcompijk (3.1) k 1 Trong đó, Li là số tác vụ của ứng dụng Ai . Giả sử tcommijrs là trễ truyền thông từ tác vụ vir đến tác vụ vis trong ứng dụng Ai tại mức chất lượng Qij . Khi đó tổng trễ truyền thông trong ứng dụng Ai tại mức chất lượng Qij sau khi ánh xạ sẽ là: Li Li tcommij    rstcommijrs  dist (( x, y ), (x', y')) (3.2) r s Trong đó,  rs  1 nếu có một kết nối giữa tác vụ vir và vis ,  rs  0 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 pxy đến px ' y ' . Tổng thời gian thực hiện của ứng dụng Ai tại mức chất lượng Qij được tính bởi công thức: tij  tcompij  tcommij (3.3) 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  , Map  vik   pxy , vik V , pxy  P với các mục tiêu 1 M Ni  B  i   ij Bij  (3.4) M  i 1 j max  M Ni  T    ij tij  (3.5)  i 1 j 1 min Ni Thỏa mãn các điều kiện:  j 1 ij  1 ,  ij  1 nếu Qij được lựa chọn, 0 cho các trường hợp khác.  t   HW  HW p  tcompij  treqcompij (3.6)   tcommij  treqcommij 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.
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 vik V ; PE pxy  P 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 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ụng tổng hợp được sử dụng trong mô phỏng, đồ thị tác vụ của chúng được tạo ra bởi công cụ TGFF [25]. Trong đó, ứng dụng A1 có 4 tác vụ và 3 mức chất lượng (Q11, Q12 và Q13). Ứng dụng A2 có 5 tác vụ và 4 mức chất lượng (Q21, Q22, Q23 và Q24). Ứng dụng A3 có 3 tác vụ và 4 mức chất lượng (Q31, Q32, Q33 và Q34). Với mỗi ứng dụng, thời gian tính toán của các tác vụ và trễ truyền thông giữa các cặp tác vụ được tạo ra 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 đã được trình bày trong [69]. Bốn kịch bản khác nhau được sử dụng để mô phỏng cho giải pháp đề xuất này như sau: (i) Mức độ ưu tiên giữa các ứng dụng là bằng nhau; (ii) Ứng dụng A1 có mức ưu tiên cao nhất tiếp theo là ứng dụng A2 và cuối cùng là ứng dụng A3; (iii) Ứng dụng A2 có mức ưu tiên cao nhất tiếp theo là ứng dụng A3 và cuối cùng là ứng dụng A1; (iv) Mức độ ưu tiên của các ứng dụng lần lượt là A3 > A2 > A1. Tất cả các kịch bản mô phỏng được thực hiện trên PC với các thông số: CPU core i3 – 2,6 Ghz , Bộ nhớ RAM - 4 GB, HDD – 720 GB. Các kết quả mô phỏng như vị trí đặt các tác vụ trên nền tảng phần cứng, chất lượng đạt được của các ứng dụng và giá trị lợi ích tổng thể của các ứng dụng theo các kịch bản được chỉ ra như Hình 3.5 và Bảng 3.3.
17 V32 V33 V13 V24 V25 V13 V31 V14 V11 V22 V14 V11 V24 V22 V21 V31 V21 V12 V33 V12 V25 V23 V23 V32 a) Kịch bản 1 b) Kịch bản 2 V24 V22 V21 V24 V33 V32 V25 V23 V12 V23 V21 V31 V11 V31 V22 V12 V32 V13 V11 V14 V14 V33 V25 V13 c) Kịch bản 3 d) Kịch bản 4 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ạ Trong kịch bản đầu tiên, kết quả ánh xạ (Hình 3.5a) cho thấy rằng tất cả các tác vụ của ứng dụng A1 và A3 chạy trên tài nguyên phần cứng. Vì vậy, cả hai ứng dụng này đều chạy ở mức chất lượng cao nhất. Trong khi đó, chỉ có một tác vụ của ứng dụng A2 chạy trên tài nguyên phần cứng và các tác vụ còn lại của nó chạy trên ISP. Do vậy, ứng dụng A2 chạy ở mức chất lượng thấp nhất. Giá trị lợi ích tổng thể của các ứng dụng trong trường hợp này là 0,25. Bảng 3.3. Kết quả mô phỏng của các kịch bản ánh xạ Ƣu tiên Kết quả Kịch bản Mức chất Giá trị lợi Ứng dụng Ai Hệ số i lƣợng ích tổng thể A1 0,33 Q11 i A3 0,33 Q31 0,25 A2 0,33 Q24 A1 0,50 Q11 ii A2 0,30 Q23 0,23 A3 0,20 Q34 A2 0,50 Q21 iii A1 0,30 Q13 0,23 A3 0,20 Q34 A3 0,50 Q31 iv A2 0,30 Q23 0,24 A1 0,20 Q13 Trong kịch bản thứ hai, các ứng dụng được ánh xạ lên nền tảng phần cứng như Hình 3.5b. Do ứng dụng A1 có mức ưu tiên cao nhất nên tất cả các tác vụ của nó được ánh xạ lên các vùng tái cấu hình của FPGA để đảm bảo đạt mức chất lượng tốt nhất. Một số tác vụ của ứng dụng A2 và A3 chạy
18 trên phần cứng và một số tác vụ còn lại của chúng chạy trên ISP. Với giải pháp ánh xạ này, úng dụng A1 có thể chạy ở chất lượng cao nhất, ứng dụng A2 đạt mức chất lượng trung bình và ứng dụng A3 có mức ưu tiên thấp nhất nên nó chạy ở chất lượng thấp nhất. Giá trị lợi ích tổng thể của các ứng dụng trong trường hợp này là 0,23. Tương tự như vậy, các giải pháp ánh xạ của các kịch bản thứ ba và thứ tư lần lượt được thể hiện trong Hình 3.5c và Hình 3.5d. Từ kết quả mô phỏng này, chúng ta có thể kết luận rằng cách tiếp cận đã đề xuất có thể tìm thấy một giải pháp ánh xạ nhắm đến tối đa chất lượng tổng thể của các ứng dụng và có thể đảm bảo truyền thông tối thiểu giữa các tác vụ. Trong tất cả các tình huống, các tác vụ của cùng một ứng dụng được ánh xạ vào vùng RR lân cận để giảm thiểu trễ truyền thông giữa các tác vụ. 3.3.2. Giải pháp heuristic cho bài toán ánh xạ tại thời gian chạy Một thuật toán tìm kiếm đầy đủ đã được đề xuất để tối ưu cho bài toán ánh xạ trong Mục 3.3.1. Tuy nhiên, giải pháp này chỉ thực hiện hiệu quả trong trường hợp 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ó không lớn và số mức chất lượng trong mỗi ứng dụng hạn chế. Khi kích thước mạng tăng, kích thước của các ứng dụng lớn thì giải pháp này không còn hiệu quả vì thời gian thực hiện thuật toán ánh xạ lớn. Để khắc phục nhược điểm này, tác giả đề xuất một giải pháp mới hiệu quả dựa trên chiến lược chọn vùng gần lồi kết hợp với thuật toán ánh xạ heuristic. Đầu tiên, một vùng gần lồi sẽ được lựa chọn khi có ứng dụng đưa vào hệ thống, tiếp theo một thuật toán ánh xạ sẽ ánh xạ các tác vụ của ứng dụng này vào vùng gần lồi đã chọn. Giải pháp cho phép triển khai nhanh và linh hoạt các ứng dụng lên nền tảng. Ngoài ra, nó cũng có thể dễ dàng thêm vào hệ thống các ứng dụng mới trong tương lai. 3.3.2.1. Chiến lược chọn vùng gần lồi Chọn các vùng gần lồi liền kề trên nền tảng để ánh xạ các tác vụ của các ứng dụng vào chúng là một giải pháp hiệu quả cho bài toán ánh xạ, nó đã được chứng minh trong các nghiên cứu [13-14]. Với một nền tảng phần cứng thực hiện trên FPGA có số lượng PE không lớn, tác giả đề xuất một chiến lược chọn vùng gần lồi mới nhắm đến các mục tiêu như cấp phát tài nguyên linh hoạt, thời gian thực hiện chọn vùng nhanh, giảm thiểu khoảng cách MD trung bình trong vùng đã chọn, tạo ra các vùng lồi liền kề. Chiến lược này được chia thành 2 bước: Bước 1, tính toán cấp phát số lượng PE cứng/mềm tương ứng với mức chất lượng của ứng dụng yêu cầu. Bước 2, tìm một vùng gần lồi dựa trên phương pháp góc quét hình học và sử dụng thêm ràng buộc khoảng cách MD tối thiểu để chọn một vùng gần lồi tối ưu cho ứng dụng.  Cấp phát PE cứng/mềm cho ứng dụng theo yêu cầu chất lượng Bước đầu tiên của chiến lược chọn vùng sẽ cấp phát số lượng PE cứng/ mềm tương ứng với mức chất lượng mà ứng dụng yêu cầu. Nếu các ứng dụng đưa vào hệ thống một cách tự nhiên khi đó số PE cứng/mềm sẽ được cấp phát theo một tỉ lệ công bằng sao cho tổng mức chất lượng đạt được của các ứng dụng sau khi ánh xạ là cực đại. Ví dụ, số PE cứng/mềm được cấp phát dựa theo độ phức tạp của ứng dụng. Nếu các ứng dụng vào được ưu tiên hoặc người dùng yêu cầu một mức chất lượng nào đó, lúc đó số PE cứng sẽ được ưu tiên cấp phát nhiều hơn cho các ứng dụng có độ ưu tiên hoặc yêu cầu chạy ở mức chất lượng cao hơn. Ví dụ, một ứng dụng yêu cầu chạy ở mức chất lượng cao nhất, khi đó các PE cứng sẽ được cấp phát cho tất cả tác vụ của ứng dụng.  Chọn vùng gần lồi Tiếp theo, một chiến lược chọn vùng mới dựa trên góc quét hình học kết hợp với khoảng cách MD tối thiểu được sử dụng để chọn ra một vùng gần lồi cho ứng dụng vào. Chiến lược này được mô tả như sau: Đầu tiên, tìm một PE trung tâm hoặc cận (gần) trung tâm làm tâm quét trên nền tảng. Các góc quét khác nhau thay đổi từ 0->3600 có thể được sử dụng. Hướng quét có thể