CHƯƠNG 1 CƠ SỞ LÝ THUYẾT Trong chương này, chúng tôi sẽ trình bày ngắn gọn các kiến thức liên quan đến nội dung nghiên cứu của đề tài để làm cơ sở cho những đề xuất trong các chương tiếp theo. Lý thuyết về NoC gồm kiến trúc của bộ định tuyến, cấu hình mạng, thuật toán định tuyến, cơ chế điều khiển luồng và chuyển mạch; công nghệ FPGA hiện tại và tương lai, các điểm mạnh và khả năng cấu hình lại từng phần động của các FPGA hiện đại; các kỹ thuật ánh xạ như phương pháp ánh xạ tại thời gian thiết kế và tại thời gian chạy sẽ được giới thiệu và phân tích. Lý thuyết về mạng trên chip 1. Nguồn gốc và thuật ngữ 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. 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 [7][8]. 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.1 mô tả một NoC điển hình dạng lưới hai chiều 3x3. IP core core core (0,0) (0,1) (0,2) Router Router Router links core core core (1,0) (1,1) (1,2) Router Router Router core core core (2,0) (2,1) (2,2) Router Router Router Hình 1. Cấu trúc của một NoC dạng lưới 3x3 Các thuật ngữ thường được sử dụng trong NoC: 6 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.
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. 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. 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.
Cấu hình mạng Topologies Irregular Regular Trees Meshes Cubes Others n-dimensional Cube-connected Fat tree k-ary n-cubes meshes cycles 2D meshes Torus (n=2) Hình 1. Phân loại cấu hình mạng NoC Một cấu hình mạng được định nghĩa là cách kết nối các bộ định tuyến trong mạng với nhau thông qua các kênh liên kết. Cấu hình mạng thường được biểu diễn dưới dạng đồ thị. Cấu hình mạng có thể chia thành hai nhóm chính: Bất quy tắc (Irregular) và quy tắc (Regular) [14].
Các cấu hình mạng quy tắc đơn giản hơn so với các cấu hình bất quy tắc. Do vậy, định tuyến trong cấu hình mạng quy tắc dễ dàng hơn, kích thước của chuyển mạch 7 có khả năng nhỏ hơn, hiệu quả hơn, băng thông cao, chu kỳ đồng hồ nhanh hơn và khả năng mở rộng hệ thống cũng dễ hơn [15].2 chỉ ra cách phân loại cấu hình mạng. Mạng lưới n-chiều (n-Dimensional Mesh) Trong cấu hình mạng lưới n-chiều, các nút mạng được sắp thành một mảng n chiều. Dọc theo mỗi chiều có ki nút (ki ≥ 2, i là số thứ tự của chiều, 0 ≤ i ≤ n-1).
Mạng sẽ có tổng số nút là k0,k1,…,kn-1. Mỗi nút có từ n đến 2n nút lân cận tùy vào vị trí của nó trong mạng như Hình 1. Nếu lưu lượng dữ liệu trong mạng là đều giữa các nút thì các kênh truyền dẫn gần trung tâm sẽ mang nhiều lưu lượng hơn do chúng có nhiều liên kết giữa các nút nhất [16]. Mạng lưới n-chiều 1.
Mạng K-ary n-cube Trong cấu hình mạng này, các nút được sắp xếp thành một mảng n chiều và số nút trên mỗi chiều bằng nhau và bằng k như Hình 1. Do đó tổng số nút có trong mạng là kn nút. Với cấu hình này, các nút tại vị trí giao nhau giữa các cạnh của mạng sẽ có thêm liên kết với nhau [17]. Mạng k-ary n-cube 1.
Mạng có số chiều thấp 8 Khi cấu hình mạng lưới n-chiều và k-ary n-cube ở trên có n = 2, mạng lưới n-chiều trở thành mạng lưới hai chiều (2D-mesh) và mạng k-ary n-cube trở thành mạng torus hai chiều (2D-torus). Đây là các cấu hình mạng thông dụng được sử dụng trong thiết kế NoC dành cho các hệ thống SoC. Trong mạng lưới hai chiều, liên kết giữa các nút là liên kết hai chiều và trong cấu hình mạng torus hai chiều liên kết giữa các nút là liên kết một chiều [18].5 trình bày cấu hình mạng lưới hai chiều và torus. a) Mesh b) Torus Hình 1.
Mạng hai chiều mesh và torus 1. Cơ chế điều khiển luồng 1. Bản tin Trong NoC, nút nguồn và nút đích trao đổi thông tin với nhau thông qua các bản tin (Message), mỗi bản tin được chia thành nhiều gói tin và mỗi gói tin được chia thành nhiều phần nhỏ gọi là flit (Flow control unit). Mỗi flit mang theo các Phit (Physical Transfer unit).
Các liên kết trong mạng sẽ truyền từng flit của gói tin đi từ nguồn đến đích. Để đảm bảo toàn bộ bản tin truyền đến được đích và tiết kiệm được lưu lượng cho mạng đồng thời nâng cao hiệu năng mạng, người thiết kế cần lựa chọn cơ chế điều khiển luồng thích hợp theo cấu hình mạng của NoC [19]. Gói tin: Là đơn vị cơ bản để thực hiện định tuyến và sắp xếp thứ tự cũng như trạng thái điều khiển cho gói tin. Phần Header của gói tin chứa thông tin định tuyến và có thể chứa số thứ tự gói tin.
Trong đó, thông tin định tuyến dùng để xác định đường di chuyển của gói tin từ nút nguồn đến nút đích. Mỗi gói tin thường có kích thước từ 128 bit đến 512 Kbit. Flit: Là đơn vị cơ bản để thực hiện cấp phát băng thông và tài nguyên kênh truyền, bộ đệm trong các cơ chế điều khiển luồng. Có ba loại flit được sử dụng: Header flit, body flit và tail flit.
Trong đó, header flit là flit đầu tiên của gói tin và được gọi là flit tiêu đề, flit này mang theo thông tin định tuyến như địa chỉ nút đích của gói tin. Body flit và tail flit không mang theo thông tin định tuyến mà mang theo thông tin về loại flit và dữ liệu của gói tin, do đó body flit và tail flit được truyền cùng đường đi với flit tiêu đề. Mỗi flit có kích thước từ 16 bit đến 512 bit và mỗi Phit có kích thước từ 1 bit đến 64 bit. Cơ chế điều khiển luồng Store-and-Forward (SAF) Cơ chế điều khiển luồng này thực hiện như sau: Một flit đơn được gửi đến một cổng ra của một bộ định tuyến tại mỗi đơn vị thời gian.
Bộ định tuyến sẽ gửi flit tiêu đề đến bộ định tuyến kế tiếp khi đã nhận được tail flit của gói tin như Hình 1. Để chống tràn bộ đệm kênh truyền ngõ vào, bộ đệm ngõ vào cần phải lớn hơn dung lượng của gói tin [19]. Cơ chế điều khiển luồng Wormhole (WH) Buffer Router a) Store-and-Forward packet data flit header flit Buffer Router b) Wormhole Hình 1. Cơ chế điều khiển luồng SAF và WH Trong cơ chế điều khiển luồng này, một flit được định tuyến và truyền đi đến bộ định tuyến kế tiếp trước khi flit tiếp theo được truyền đến.
Các bộ định tuyến sẽ lưu một phần các flit của một gói tin đơn. Điều này yêu cầu bộ đệm trong bộ định tuyến có kích thước nhỏ. Theo lý thuyết, kích thước của bộ đệm kênh truyền trong bộ định tuyến chỉ cần bằng một flit đơn (Hình 1. Vì mỗi bộ định tuyến có thể chuyển tiếp các flit của một gói tin trước khi nhận đầy đủ cả gói tin, các flit được lưu trên nhiều bộ định tuyến dọc theo đường đi của gói tin [19].
Cơ chế điều khiển luồng WH tốt hơn cơ chế điều khiển SAF cả về kích thước bộ đệm yêu cầu và độ trễ. Tuy nhiên, cơ chế này cũng có nhược điểm riêng là hiệu năng của mạng bị giảm khi một gói tin bị nghẽn. Các phần của một gói tin có thể được lưu trong các bộ định tuyến dọc theo đường đi của gói tin, vì thế một gói tin đơn sẽ chiếm dụng các bộ đệm trên nhiều bộ định tuyến khi nó di chuyển. Khi phần đầu của gói tin không thể tiếp tục di chuyển do có xung đột.
Trường hợp này gọi là nghẽn HoL (Head-of-Line). Các bộ đệm bị chiếm bởi HoL sẽ ngăn các gói tin khác đang muốn đi qua đường đi của gói tin bị nghẽn và dẫn đến giảm hiệu năng của mạng. Cơ chế điều khiển luồng kênh ảo (Virtual Channel) 10 Trong các cơ chế điều khiển luồng trên đây, mỗi kênh liên kết vật lý cần một bộ đệm kết hợp với một FIFO để lưu trữ các flit đi vào bộ định tuyến. Bộ đệm này chứa các flit của một gói tin đơn và nếu như gói tin bị chặn thì liên kết vật lý sẽ ở trạng thái rỗi do không có gói tin nào khác có thể yêu cầu tài nguyên bộ đệm để truy cập kênh truyền.
Cơ chế điều khiển luồng kênh ảo được đưa ra để khắc phục nhược điểm này. Cơ chế này tạo ra nhiều bộ đệm cho mỗi kênh trong mạng. Mỗi bộ đệm có thể chứa một hay nhiều flit của một gói tin kết hợp với thông tin trạng thái gói tin. Nếu gói tin hiện đang sử dụng kênh liên kết vật lý bị chặn thì các gói tin khác có thể yêu cầu các bộ đệm ngõ vào khác để sử dụng kênh liên kết vật lý.