Đặt Vấn Đề & Hướng Giải Quyết 16 Phạm Đăng Lâm CHƢƠNG 1.1 Mạng trên chip. với kiến trúc bus thông thường trước đây, các nghiên cứu đã cho thấy sự giới hạn về hiệu quả cũng như tính phức tạp trong thiết kế của nó [1] khi mà mật độ tích hợp các đơn vị xử lý tăng lên. Một hướng nghiên cứu khác được xem là rất có tiềm năng trong tương lai để giải quyết vần đề đặt ra là “mạng trên chip – Network on Chip (NoC)”. Trong một kiến trúc NoC, các lõi xử lý hay các IP giao tiếp không thông qua các bus thông dụng mà thông qua các router.
Các hướng nghiên cứu về vấn đề này được giới thiệu ở mục 1.2 tiếp sau đây.2 Các hƣớng nghiên cứu và các khái niệm liên quan đến NoC Dựa trên ý tưởng giao tiếp giữa các IP thông qua các router được kết nối với nhau. Các hướng nghiên cứu sau được đưa ra và gặt hái nhiều thành quả. Kiến trúc NoC (mô hình, giải thuật định tuyến và phân xử…). Các phương pháp kết nối chuyển mạch bên trong router và giữa các router.
Những vấn đề về năng lượng. Những vấn đề về đảm bảo chất lượng (lỗi và khả năng sửa lỗi, băng thông giới hạn …). Các phương pháp thiết kế (trình tự các bước thiết kế), đánh giá (mô phỏng, kiểm tra), phần mềm hỗ trợ… cho thiết kế NoC. Hệ điều hành và khả năng lập trình trên NoC.
Vấn đề về tích hợp các kỹ thuật bên trong NoC (mạng noron, logic mờ …). Vấn đề về đánh giá hiệu suất NoC trên FPGA và ASIC. Vấn đề về diện tích. Tổng Quan 17 Phạm Đăng Lâm Do NoC là một thuật ngữ mang tính khái quát nên các lĩnh vực nghiên cứu về NoC nêu trên mang ý nghĩa bao hàm nhiều mảng kiến thức rộng lớn khác nhau.
Bởi thế, luận văn chỉ đề cập sâu vào những hướng nghiên cứu mà đề tài luận văn sẽ tiếp cận. Đầu tiên những khái niệm cơ bản nhất của một kiến trúc NoC được mô tả.1 Mô hình kiến trúc mạng NoC (topology) Xuất phát từ các quan điểm khác nhau, các nghiên cứu đã đưa ra các mô hình mạng thông dụng NoC khác nhau như dạng điểm điểm (point-to-point), dạng bus, dạng xuyến (Torus), dạng lưới (Mesh), dạng vòng (Ring), dạng hình cánh bướm (Butterfly), dạng không theo quy luật (Irregular) … Cấu hình mạng là sự sắp xếp các router chuyển mạch và các kênh liên kết giữa các router đó. Lựa chọn mô hình mạng là công việc đầu tiên cần làm khi thiết kế một hệ thống mạng, cho dù là mạng máy tính hay mạng trên chip. Việc chọn lựa mô hình mạng có ảnh hưởng rất lớn đến với các kỹ thuật định tuyến (routing) và điều khiển luồng (flow control) sẽ được nhắc đến ở các phần sau.
Mô hình mạng thường được mô tả ở dưới dạng sơ đồ hay đồ hình.1 [2] mô tả một số mô hình mạng cơ bản đã được phát triển và đưa vào ứng dụng trong thực tế.2 [2] mô tả các mô hình mạng NoC phổ biến. Trong đó mạng dạng lưới (MESH) và dạng xuyến (TORUS) được sử dụng phổ biến nhất. a/ Dạng điểm-điểm b/Dạng bus c/ Dạng nhiều bus C1. Tổng Quan 18 Phạm Đăng Lâm d/ Dạng lưới e/Dạng xuyến f/ Dạng cách bướm g/Dạng lưới 3D h/Dạng xoắn 3D Hình 1.1 Các mô hình kết nối trong NoC [2] Hình 1.2 Phân nhánh mô hình NoC theo cấu trúc mạng [2] C1.
Tổng Quan 19 Phạm Đăng Lâm Sau đây là những phân tích về mô hình mạng MESH và TORUS hai chiều. Sự khác biệt giữa hai mô hình mạng này được mô tả bởi hình 1. Mô hình mạng dạng MESH và TORUS [2] Dựa trên hình 1.3, mô hình dạng lưới mang tính đối xứng cao rất phù hợp và tiện lợi trong quá trính sản xuất. Chính điều này đã làm cho mô hình dạng lưới trở thành mô hình được lựa chọn nhiều nhất trong các hướng nghiên cứu.
Sau đây là những biến điệu của mô hình dạng lưới được phân tích chi tiết. a/ Mesh 2D b/Concentrate Mesh c/CMesh-X2v d/Flattened Butterfly C1. Tổng Quan 20 Phạm Đăng Lâm e/Multipdrop express channel (MESC) Hình 1.4 Các mô hình dạng lưới hai chiều [3] Theo như hình 1.4 [3], các ưu và khuyết điểm của mỗi mô hình được trình bày.a) Thuận lợi: Cấu tạo các router đơn giản tốc độ cao. Thuận lợi trong quá trình sắp đặt cấu trúc lên chip (place& route).
Không thuận lợi: Chiếm diện tích lớn. Tiêu hao nhiều năng lượng. b/ Concentrate Mesh (hình 1.b) Là sự cải thiện của Mesh-2D bằng cách nhóm 4 router thành 1 router. Với sự kết hợp này đã cho thấy các đặc điểm cải thiện sau.
Thuận lợi: Chia sẻ các ngõ vào/ra dùng chung trong một nhóm 4 router. Tổng Quan 21 Phạm Đăng Lâm Giảm độ trễ hơn so với Mesh-2D do có thể rút ngắn số router trung gian phải đi qua. Tốc độ tăng khi giao tiếp giữa các router trong cùng một nhóm. Không thuận lợi: Độ phức tạp trong thiết kế các kiến trúc bên trong router.
Tiêu hao nhiều năng lượng.c) Mô hình CMesh-X2 được xem như một phiên bản cải thiện của Concentrate Mesh với sự tăng cường các port giao tiếp nhằm tăng thông lượng truyền dẫn và giảm độ phức tạp trong việc thiết kế kiến trúc bên trong của router. d/ Flattened Butterfly (hình 1.d) Dựa trên nền tảng Concentra Mesh, mỗi router có tất cả các đường bus truyền đi đến các router khác trên phương x và y. Trong khi đó, bản thân mỗi router cũng nhận các đường bus từ tất cả các router khác trên phương x và y. Chính cải thiện này đã mang đến những thuận lợi và bất lợi sau.
Thuận lợi: Tiện lợi giao tiếp giữa các router trên các phương x và y mà không thông qua router trung gian. Giảm độ trễ hơn so với Mesh-2D, Concentrate Mesh do có thể rút ngắn tổng số router phải đi qua nhiều nhất là 2. Tổng Quan 22 Phạm Đăng Lâm Không thuận lợi: Độ phức tạp trong thiết kế thành phần điều khiển bên trong router. Khi lưu lượng dữ liệu ít, tài nguyên trên mạng dư thừa lãng phí.
Tiêu hao nhiều năng lượng và các vấn đề về số lượng kênh truyền trở nên khó khăn khi mạng mở rộng với nhiều IP. e/ Multipdrop express channel-MESC (hình 1.e) Dựa trên nền tảng Flattend Butterfly, sự cải thiện trong vấn đề kênh truyền được chú ý. Số lượng kênh truyền sẽ bằng chính số router trên một phương x hoặc y. Ngoài ra, đặc tính kênh truyền trong mô hình này còn cho phép một router truyền dữ liệu đồng thời cho nhiều router khác nhờ cơ chế multidrop [3].
Chính cải thiện này đã mang đến những thuận lợi và bất lợi sau. Thuận lợi: Tiện lợi giao tiếp giữa các router trên các phương x và y mà không thông qua router trung gian đồng thời hỗ trợ cơ chế multidrop trên một đường truyền. Giảm độ trễ so với Mesh-2D, Concentrate Mesh do có thể rút ngắn số router trung gian phải đi qua nhiều nhất là 2. Thích hợp cho các mô hình thời gian thực.
Không thuận lợi: Độ phức tạp trong thiết kế thành phần điều khiển bên trong router. Khi lưu lượng dữ liệu ít, tài nguyên trên mạng dư thừa lãng phí. Tổng Quan 23 Phạm Đăng Lâm Tính không đối xứng trong thiết kế. Để so sánh chi tiết về những khác biệt của các mô hình NoC dạng lưới và những biến điệu của nó, kết quả so sánh tài nguyên giữa các mô hình được giới thiệu trong bảng 1.
Dựa vào sự khác biệt giữa các thông số của hình 1.5, các điểm thuận lợi và bất lợi của các mô hình được chọn được thể hiện. Ví dụ tiêu biểu như số router tối đa mà gói dữ liệu phải đi qua chỉ là 2 router so với mô hình MECS và FBfly. Nhưng đối với CMESH, số router sẽ tăng theo quy mô của mạng. Ngoài ra khi gia tăng tài nguyên trong mạng NoC, một số chỉ số về tài nguyên sẽ thay đổi, một số khác được giữ cố định tùy theo đặc tính cấu hình mạng.
Việc phân tích các thông số khác không được đề cập chi tiết ở đây. Phần phụ lục tham khảo có đưa ra các nghiên cứu thể hiện các đánh giá chi tiết các mô hình cần quan tâm [3], [5], [6]. Phần kế tiếp luận văn giới thiệu chi tiết về các kỹ thuật được sử dụng trong mạng NoC như : kỹ thuật chuyển mạch, kỹ thuật định tuyến, kỹ thuật điều khiển luồng và cấu trúc tổng quan router … Trước hết, kỹ thuật định tuyến được giới thiệu trước. CMesh FBfly MECS Tổng số router 64 256 64 256 64 256 Số router/ phương 4 8 4 8 4 8 Số router tối đa gói dữ liệu đi qua 6 14 2 2 2 2 Số kênh truyền/phương 2 2 8 32 4 8 Độ rộng kênh 576 1152 144 72 288 288 Số ngõ vào router 4 4 6 14 6 14 Số ngõ ra router 4 4 6 14 4 4 1.1 Bảng so sánh các đặc tả của các mô hình lưới khác nhau [3] C1.
Tổng Quan 24 Phạm Đăng Lâm 1.2 Thủ tục định tuyến (rounting protocol) Dựa trên mô hình mạng tương ứng sẽ có những thủ tục định tuyến phù hợp. Ở đây luận văn chỉ đưa ra các định tuyến thông dụng. Việc sử dụng giải thuật định tuyến tương ứng với mô hình mạng cụ thể không được đề xuất. Bạn đọc cần tham khảo các đề tài chi tiết để biết thêm.
Bản thân các giải thuật định tuyến cũng thay đổi theo từng mô hình mạng khác nhau. Mô hình ở hình 1.5 [1] mô tả cách phân loại các giải thuật định tuyến đã và đang nghiên cứu. Dựa trên các mô hình mạng và mục đích khác nhau mà đưa ra các giải thuật định tuyến thích hợp. Đầu tiên căn cứ vào số lượng đích đến (destinations) mà các giải thuật được phân chia thành đơn mục tiêu (unicast rounting) và đa mục tiêu (multicast rounting).
Trong đó, giải thuật định tuyến đơn mục tiêu được ứng dụng rộng rãi hơn nhờ tính phù hợp với đặc tính kết hợp điểm điểm trong mô hình nhiều IP. Trong mô hình đơn mục tiêu, người ta chia nhỏ thành bốn loại khác bao gồm: Định tuyến nguồn (source rounting), định tuyến phân tán (distribute rounting), định tuyến trung tâm (centralized rounting) và định tuyến dựa trên từng pha khác nhau (multiphase rounting). Trong định tuyến trung tâm, một bộ phận điều khiển trung tâm sẽ thực hiện nhiệm vụ này để điều khiển dữ liệu trong hệ thống. Trong định tuyến nguồn, quyết định giải thuật định tuyến được thực hiện tại nơi (router) mà dữ liệu bắt đầu được truyền đi.
Trong khi đó định tuyến phân tán quyết định đường truyền (các đường đi của các gói/khung-packet/split dữ liệu) dựa trên các router trung gian. Sự kết hợp của định tuyến nguồn và định tuyến phân tán chính là định tuyến theo từng pha khác nhau.