Tài liệu Thiết kế bộ nhớ địa chỉ nội dung (tcam) thực hiện trên fpga

ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ------------------------ TRỊNH VŨ ĐĂNG NGUYÊN THIẾT KẾ BỘ NHỚ ĐỊA CHỈ NỘI DUNG (TCAM) THỰC HIỆN TRÊN FPGA Chuyên Ngành: Kỹ Thuật Điện Tử Mã số: 8520203 LUẬN VĂN THẠC SỸ TP. Hồ Chí Minh, tháng 08 năm 2021 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG – HCM Cán bộ hướng dẫn khoa học: TS. Trần Hoàng Linh Cán bộ chấm nhận xét 1: TS. Bùi Trọng Tú Cán bộ chấm nhận xét 2: TS. Trương Quang Vinh Luận văn thạc sỹ được bảo vệ tại Trường Đại Học Bách Khoa, ĐHQG Tp. HCM ngày 22 tháng 08 năm 2021 (trực tuyến). Thành phần Hộ đồng đánh giá luận văn thạc sĩ gồm: 1. Chủ tịch hội đồng:TS. Huỳnh Phú Minh Cường 2. Phản biện 1: TS. Bùi Trọng Tú 3. Phản biện 2: TS. Trương Quang Vinh .... 4. Thư ký: TS. Nguyễn Lý Thiên Trường ... 5. Ủy viên: TS. Nguyễn Minh Sơn ............. Xác nhận của chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sữa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TS. Huỳnh Phú Minh Cường TRƯỞNG KHOA ĐIỆN - ĐIỆN TỬ PGS.TS. Đỗ Hồng Tuấn Nhiệm vụ luận văn thạc sỹ GVHD: TS. Trần Hoàng Linh ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ------------------------------ CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc ----------------------------------------------- NHIỆM VỤ LUẬN VĂN THẠC SỸ Họ và tên học viên: Trịnh Vũ Đăng Nguyên MSHV: 1970428 Ngày, tháng, năm sinh: 18/12/1997 Nơi sinh: Ninh Thuận Chuyên ngành : Kỹ Thuật Điện Tử Mã Số: 1970428 I. II. III. IV. V. TÊN ĐỀ TÀI: THIẾT KẾ BỘ NHỚ ĐỊA CHỈ NỘI DUNG (TCAM) THỰC HIỆN TRÊN FPGA NHIỆM VỤ VÀ NỘI DUNG: Nghiên cứu đề ra là một bộ nhớ địa chỉ nội dung hỗ trợ các giá trị nhị phân và tùy định của hệ thống máy tính, cho phép truy xuất từ một giá trị dữ liệu kỹ thuật số và cho ra kết quả về hành động cần thực hiện hoặc giá trị ưu tiên của dữ liệu đó trong cơ sở dữ liệu. Bộ nhớ truy xuất dữ liệu này sẽ được tích hợp trên FPGA, sử dụng các khối bộ nhớ trong để lưu trữ cơ sở dữ liệu. NGÀY GIAO NHIỆM VỤ (Ghi theo QĐ giao đề tài): 22/02/2021 NGÀY HOÀN THÀNH NHIỆM VỤ (Ghi theo QĐ giao đề tài): 13/06/2021 CÁN BỘ HƯỚNG DẪN : TS. Trần Hoàng Linh CÁN BỘ HƯỚNG DẪN ( Họ tên và chữ ký) TS. Trần Hoàng Linh Tp. HCM, ngày ……. tháng ……. năm 2021 CHỦ NHIỆM BỘ MÔN ĐÀO TẠO ( Họ tên và chữ ký ) TS. Trần Hoàng Linh TRƯỞNG KHOA ĐIỆN - ĐIỆN TỬ ( Họ tên và chữ ký ) PGS.TS. Đỗ Hồng Tuấn Lời cảm ơn GVHD: TS. Trần Hoàng Linh LỜI CẢM ƠN Trong suốt quá trình học tập, thực hiện và hoàn thành luận văn này, em đã nhận được sự hướng dẫn, giúp đỡ quý báu của các thầy cô, các anh chị, các em và các bạn. Với lòng kính trọng và biết ơn sâu sắc em xin được bày tỏ lời cảm ơn chân thành tới: TS. Trần Hoàng Linh, người thầy kính mến đã hết lòng giúp đỡ, dạy bảo, động viên và tạo mọi điều kiện thuận lợi cho em trong suốt quá trình thực hiện luận văn tốt nghiệp. Thầy là người định hướng, góp ý cũng như chỉ dạy phương pháp làm việc, giúp em có thể hoàn thành luận văn một cách tốt nhất. Các quý thầy cô trong khoa Điện – Điện tử, trường Đại Học Bách Khoa thành phố Hồ Chí Minh đã tận tình chỉ dạy và truyền đạt kiến thức giúp em có thể đạt được kết quả như ngày hôm nay. Bên cạnh đó, em xin chân thành cảm ơn bố mẹ và gia đình đã luôn hỗ trợ, động viên về mặt vật chất và tinh thần, giúp em hoàn thành tốt được luận văn này. Tóm Tắt Luận Văn GVHD: TS. Trần Hoàng Linh TÓM TẮT LUẬN VĂN Bộ nhớ địa chỉ nội dung là một loại bộ nhớ đặc biệt, được sử dụng rộng rãi trong các thiết bị hạ tầng mạng để điều hướng và định địa chỉ các gói dữ liệu. Ngoài ra, bộ nhớ địa chỉ nội dung còn được sử dụng trong các ứng dụng cần tìm kiếm dữ liệu nhanh chóng. Tuy nhiên, bộ nhớ địa chỉ nội dung vẫn còn các nhược điểm như mức tiêu thụ năng lượng cao và kích thước lớn cũng như cấu trúc riêng biệt, khó tích hợp vào các FPGA đang được dùng trong nhiều ứng dụng cải thiện tốc độ mạng Internet. Nghiên cứu này đề ra một cấu trúc bộ nhớ địa chỉ nội dung xây dựng từ các phần tử RAM trên FPGA, hỗ trợ đầy đủ các giá trị nhị phân và tuỳ định. Sử dụng phương pháp xếp chồng các dữ liệu lên nhau để giảm kích thước và tài nguyên tiêu thụ. Bên cạnh đó, nghiên cứu đưa ra một thiết kế mẫu bộ nhớ địa chỉ nội dung 256 x 104-bit trên FPGA Cyclone V và đánh giá khả năng ứng dụng của thiết kế trên quy mô lớn cũng như các hướng phát triển trong tương lai. Abstract GVHD: TS. Trần Hoàng Linh ABSTRACT Content addressable memory (CAM) and ternary content addressable memory (TCAM) are specialized high-speed memories for data searching. CAM and TCAM have many applications in network routing, packet forwarding and Internet data centers. These types of memories have drawbacks on power dissipation and area. As fieldprogrammable gate array (FPGA) is recently being used for network acceleration applications, the demand to integrate TCAM and CAM on FPGA is increasing. Because most FPGAs do not support native TCAM and CAM hardware, methods of implementing algorithmic TCAM using FPGA resources have been proposed through recent years. Algorithmic TCAM on FPGA have the advantages of FPGAs low power consumption and high intergration scalability. This paper proposes a scaleable algorithmic TCAM design on FPGA. The design uses memory blocks to negate power dissipation issue and data collision to save area. The paper also presents a design of a 256 x 104-bit algorithmic TCAM on Intel FPGA Cyclone V, evaluates the performance and application ability of the design on large scale and in future developments. Lời cam đoan GVHD: TS. Trần Hoàng Linh LỜI CAM ĐOAN Học viên cam đoan rằng, ngoài trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong báo cáo đề tài, các công việc trình bày trong báo cáo này là do chính học viên thực hiện. Học viên Trịnh Vũ Đăng Nguyên Mục Lục GVHD: TS. Trần Hoàng Linh MỤC LỤC NHIỆM VỤ LUẬN VĂN THẠC SỸ ........................................................................................ i LỜI CẢM ƠN ........................................................................................................................... ii TÓM TẮT LUẬN VĂN........................................................................................................... iii ABSTRACT.............................................................................................................................. iv LỜI CAM ĐOAN ...................................................................................................................... v MỤC LỤC BẢNG .................................................................................................................. viii MỤC LỤC HÌNH ..................................................................................................................... ix CHƯƠNG 1. TỔNG QUAN ĐỀ TÀI ...................................................................................... 1 1.1 Vấn đề tổng quan bao phủ nghiên cứu: ............................................................................... 1 1.2 Mục đích nghiên cứu ............................................................................................................. 1 1.3 Những kết quả công bố trước đây ........................................................................................ 1 1.4 Mục tiêu, đối tượng và phạm vi nghiên cứu ........................................................................ 2 CHƯƠNG 2. CƠ SỞ LÝ THUYẾT BỘ NHỚ ĐỊA CHỈ NỘI DUNG ................................. 3 2.1 Sơ lược về bộ nhớ địa chỉ nội dung ...................................................................................... 3 2.1.1 Giới thiệu về bộ nhớ khả lập địa chỉ nội dung (CAM) ..................................................................... 3 2.1.2 Giới thiệu về bộ nhớ khả lập địa chỉ nội dung 3 biến (TCAM) ....................................................... 3 2.2 Sơ lược về một số nghiên cứu bộ nhớ khả lập địa chỉ nội dung ........................................ 3 2.3 Phương pháp xếp chồng dữ liệu (Data Collision) ............................................................... 5 2.3.1 Tổng Quan ............................................................................................................................................ 5 2.3.2 Giới thiệu thuật toán chồng chập dữ liệu (Data Collision)............................................................... 5 CHƯƠNG 3. ĐẶC TẢ THIẾT KẾ LÕI IP BỘ NHỚ KHẢ LẬP ĐỊA CHỈ NỘI DUNG 3 BIẾN (TCAM) ......................................................................................................................... 10 3.1 Kiến trúc hệ thống ............................................................................................................... 10 3.1.1 Sơ đồ khối Top level ........................................................................................................................... 10 3.1.2 Mô tả tín hiệu vào ra .......................................................................................................................... 12 3.1.3 Nguyên tắc hoạt động của khối top level.......................................................................................... 13 3.2 3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 Các khối trong hệ thống ...................................................................................................... 14 Khối segment Engine ......................................................................................................................... 14 Khối Status Engine............................................................................................................................. 16 Khối Mask Engine .............................................................................................................................. 19 Khối Confirm Engine......................................................................................................................... 23 Khối Priority Engine .......................................................................................................................... 30 CHƯƠNG 4. ĐẶC TẢ THIẾT KẾ LÕI IP BỘ NHỚ KHẢ LẬP ĐỊA CHỈ NỘI DUNG 3 BIẾN (TCAM) _ CẢI TIẾN................................................................................................... 34 4.1 Kiến trúc hệ thống ............................................................................................................... 34 Page : vi Mục Lục GVHD: TS. Trần Hoàng Linh 4.1.1 Sơ đồ khối Top level ........................................................................................................................... 34 4.1.3 Nguyên tắc hoạt động của khối top level.......................................................................................... 37 4.2 4.2.1 4.2.2 4.2.3 4.2.4 Các khối trong hệ thống ...................................................................................................... 38 Khối segment Engine ......................................................................................................................... 38 Khối Status Engine............................................................................................................................. 44 Khối Mask Engine .............................................................................................................................. 47 Khối Confirm Engine và Priority Engine ........................................................................................ 54 CHƯƠNG 5. HỆ THỐNG KIỂM TRA THỰC NGHIỆM LÕI IP BỘ NHỚ ĐỊA CHỈ NỘI DUNG TRÊN FPGA ...................................................................................................... 55 5.1 Sơ đồ hệ thống kiểm tra thiết kế trên Quartus và modelsim ........................................... 55 5.1.1 Kiểm tra và đánh giá thiết kế trên quartus....................................................................................... 55 5.1.1.1 Kết quả synthesis .................................................................................................................... 55 5.1.1.2 Kết quả Timing....................................................................................................................... 57 5.1.1.3 Kết quả Memory Usage ......................................................................................................... 59 5.1.2 Xây dựng môi trường kiểm tra Mô phỏng bằng ModelSim ............................................................ 62 5.2 Sơ đồ hệ thống kiểm tra thiết kế trên FPGA........................................................................... 65 5.2.1 5.2.2 5.2.3 5.2.4 Nguyên tắc hoạt động ........................................................................................................................ 65 Hành vi của TCAM Adapter: ........................................................................................................... 66 Nội dung BGP dataset........................................................................................................................ 66 Kết quả ................................................................................................................................................ 68 CHƯƠNG 6. KẾT LUẬN ...................................................................................................... 69 6.1 So sánh kết quả của thiết kế so với yêu cầu đề tài ............................................................ 69 6.2 Các bài báo liên quan .......................................................................................................... 69 TÀI LIỆU THAM KHẢO ...................................................................................................... 70 Page : vii Mục Lục Bảng GVHD: TS. Trần Hoàng Linh MỤC LỤC BẢNG Bảng 1: Ví dụ về cơ sở dữ liệu cơ bản của TCAM ................................................................. 4 Bảng 2: Mô tả tín hiệu vào ra khối top level ........................................................................ 12 Bảng 3: Mô tả tín hiệu vào ra của khối Segment engine ..................................................... 16 Bảng 4: Mô tả tín hiệu khối Status Engine ........................................................................... 18 Bảng 5: Mô tả tín hiệu vào ra của khối Mask engine .......................................................... 23 Bảng 6: Mô tả tín hiệu vào ra của khối Confirm engine ..................................................... 29 Bảng 7: Mô tả tín hiệu vào ra của khối Priority engine ...................................................... 33 Bảng 8: Mô tả tín hiệu vào ra khối top level ........................................................................ 36 Bảng 9: Mô tả tín hiệu vào ra của khối Segment engine ..................................................... 43 Bảng 10: Mô ta tín hiệu vào ra khối Status Engine ............................................................. 46 Bảng 11: Mô tả tín hiệu vào ra của khối Mask engine ........................................................ 53 Bảng 12: Nội dung TCAM Adapter ...................................................................................... 66 Bảng 13: Mẫu nội dung BGP dataset .................................................................................... 67 Bảng 14: Bảng mô tả kết quả đạt được của thiết kế so với yêu cầu ................................... 69 Bảng 15: Bảng tần số hoạt động tối đa cho phép của hai version ...................................... 57 Bảng 16: Bảng tính số lượng M10 cho thiết kế Collision TCAM 256 x 104 ( ver 1) ......... 59 Bảng 17: Bảng tính số lượng M10 cho thiết kế Collision TCAM 512 x 104 ( ver 2) ......... 60 Bảng 18: Bảng tính số lượng M10 cho thiết kế Collision TCAM 256 x 104 ( ver 2) ......... 60 Bảng 19: Các bài báo liên quan ............................................................................................. 69 Page : viii Mục Lục Hình GVHD: TS. Trần Hoàng Linh MỤC LỤC HÌNH Hình 1: Khôí RAM điển hình .................................................................................................. 5 Hình 2: Hoạt động cơ bản của bộ nhớ khả lập địa chỉ nội dung .......................................... 5 Hình 3: Data của CAM được cắt thành nhiều mảnh và được sử dụng để tạo một vecto đối sánh ở cuối ........................................................................................................................... 6 Hình 4: Luồng dữ liệu cơ bản của cấu trúc ............................................................................ 6 Hình 5: Đặt các quy tắc vào cơ sở dữ liệu của TCAM .......................................................... 7 Hình 6: Tìm kiếm vectơ đối sánh từ cơ sở dữ liệu ................................................................. 7 Hình 7: Vectơ mặt nạ từ vectơ ID quy tắc .............................................................................. 8 Hình 8: Xác nhận lại vectơ để có kết quả chính xác .............................................................. 8 Hình 9: Sơ đồ khối top level ................................................................................................... 10 Hình 10: Sơ đồ chi tiết khối Top-level .................................................................................. 11 Hình 11: Sơ đồ khối Segment engine .................................................................................... 14 Hình 12: Sơ khối chi tiết khối Segment Engine ................................................................... 14 Hình 13: Cấu trúc bit của Segment Vector .......................................................................... 15 Hình 14: Sơ đồ khối Status Engine ....................................................................................... 16 Hình 15: State machine khối Status Engine ......................................................................... 17 Hình 16: Cấu trúc bit của Set ID Mod .................................................................................. 17 Hình 17: Sơ đồ khối Mask engine ......................................................................................... 19 Hình 18: Sơ đồ khối chi tiết khối Mask Engine ................................................................... 20 Hình 19: Cấu trúc bit của Masked Vector ID ...................................................................... 21 Hình 20: Sơ đồ khối Confirm engine .................................................................................... 23 Hình 21: Sơ đồ khối Mask engine ......................................................................................... 24 Hình 22: Sơ đồ khối chi tiết khối Confirm Engine .............................................................. 24 Hình 23: Cấu trúc bit của Set Confirm String ..................................................................... 24 Hình 24: Cấu trúc bit của Confirm Result ........................................................................... 25 Hình 25: So sánh ID trong 1 Mask Vector ........................................................................... 25 Hình 26: So sánh từng cặp segment trong segmetn vector ................................................. 26 Hình 27: Sơ đồ khối Priority engine ..................................................................................... 30 Hình 28: Giải thuật so sánh Priority .................................................................................... 31 Hình 29: So sánh Priority từng cặp ....................................................................................... 31 Hình 30: Sơ đồ khối top level ................................................................................................. 34 Hình 31: Sơ đồ khối chi tiết Top-level .................................................................................. 35 Hình 32: Sơ đồ khối Segment Engine ................................................................................... 38 Hình 33: Sơ đồ khối chi tiết khối Segment Engine .............................................................. 39 Hình 34: Cấu trúc bit data của RAM 256 x 23 bit .............................................................. 40 Hình 35: Cấu trúc bit của Segment Vector .......................................................................... 40 Hình 36: Sơ đồ khối Status Engine ....................................................................................... 44 Hình 37: State machine khối Status Engine ......................................................................... 44 Hình 38: Cấu trúc bit của Set ID Mod .................................................................................. 45 Hình 39: Sơ đồ khối Mask Engine......................................................................................... 47 Hình 40: Sơ đồ khối chi tiết khối Mask Engine ................................................................... 48 Page : ix Mục Lục Hình GVHD: TS. Trần Hoàng Linh Hình 41: Cấu trúc bit của Masked Vector ID ...................................................................... 49 Hình 42: Kết quả synthesis version 1 .................................................................................... 55 Hình 43: Kết quả synthesis version 2 .................................................................................... 56 Hình 44: Kết quả tần số hoạt động tối đa cho phép của hai version .................................. 57 Hình 45: Tần số hoạt động tối đa cho phép của giải thuật so với những nghiên cứu....... 58 Hình 46: Tài nguyên bộ nhớ tiêu thụ của thiết kế so với những nghiên cứu kkhác ......... 61 Hình 47: Cấu trúc file test bench........................................................................................... 62 Hình 48: Kết quả mô phỏng modelsim ................................................................................. 63 Hình 49: Kết quả mô tả dạng sóng trên modelsim .............................................................. 64 Hình 50: Môi trường kiểm tra thực nghiệm lõi IP trên FPGA .......................................... 65 Hình 51: Kết quả kiểm tra thực nghiệm lõi IP trên FPGA................................................. 68 Page : x Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh CHƯƠNG 1. TỔNG QUAN ĐỀ TÀI 1.1 Vấn đề tổng quan bao phủ nghiên cứu: Bộ nhớ địa chỉ nội dung đã được nghiên cứu từ năm 1955 [1], là một dạng hình thức bộ nhớ cho phép chỉ chính xác địa chỉ của dữ liệu được truy xuất. Từ đó đến nay, bộ nhớ địa chỉ nội dung đã được phát triển dưới nhiều hình thức và cho nhiều ứng dụng khác nhau. Có thể kể đến dạng phổ biến là được chế tạo dưới dạng một IC bộ nhớ ngoài hoặc một phần của một vi xử lý, thường được sử dụng trong các bộ định tuyến Internet [2]. Hơn nữa, nhu cầu sử dụng bộ nhớ truy xuất dữ liệu đa dạng, xuất hiện trong các bộ xử lý và điều hướng hạ tầng mạng Internet, các hệ thống cơ sở dữ liệu lớn, bộ nhớ đệm cho CPU, các hệ thống xử lý mạng lưới trí tuệ nhân tạo,... Trong đó, việc sử dụng các thiết bị gia tốc tính toán trên FPGA cho các ứng dụng trên cũng trở nên phổ biến [9], gia tăng nhu cầu tích hợp bộ nhớ truy xuất dữ liệu trên FPGA. 1.2 Mục đích nghiên cứu Nghiên cứu đề ra là một bộ nhớ truy xuất dữ liệu hỗ trợ các giá trị nhị phân và tùy định của hệ thống máy tính, cho phép truy xuất từ một giá trị dữ liệu kỹ thuật số và cho ra kết quả về hành động cần thực hiện hoặc giá trị ưu tiên của dữ liệu đó trong cơ sở dữ liệu. Bộ nhớ truy xuất dữ liệu này sẽ được tích hợp trên FPGA, sử dụng các khối bộ nhớ trong để lưu trữ cơ sở dữ liệu. 1.3 Những kết quả công bố trước đây Gần đây, nhiều nghiên cứu và giải thuật đã được đề xuất để thực hiện nhằm mục đích đưa cấu trúc của bộ nhớ truy xuất dữ liệu lên FPGA. Trong số đó, có thể kể đến các xu hướng sử dụng các khối RAM nội của FPGA để thay thế cho CAM và TCAM, tuy vậy vì lý do này chúng ta phải đánh đổi bằng một số lượng lớn tài nguyên [11] [6]. Các giải thuật và các cách sắp xếp hợp lý để tối ưu hóa lượng tài nguyên và năng lượng tiêu thụ cũng được đề xuất. [13] [14] [8] Trong đó, [13] tăng tần số hoạt động của khối RAM nội cho phép truy xuất nhiều lần nhiều khối RAM trong cùng một tần số hoạt động của toàn hệ thống. Tuy vậy với những thiết kế có tần số hoạt động cao thì việc thiết kế cho khả năng sử dụng RAM nội nhanh gấp 5 lần tần số hệ thống rất khó khăn [13]. Nghiên cứu [8] đề ra cách sắp xếp dữ liệu chồng chất lên nhau rất đặc biệt và có thể ứng dụng rất tốt, tuy vậy chỉ đề cập tới thay thế cho bộ nhớ truy xuất dữ liệu (CAM) mà không nhắc tới cách hỗ trợ các giá trị tùy định của một cơ sở dữ liệu thường thấy trong bộ nhớ truy xuất dữ liệu khi sử dụng cho các ứng dụng đã nêu trên. Nghiên cứu này đề xuất một cấu trúc bộ nhớ truy xuất dữ liệu sử dụng các khối RAM trên FPGA, cũng dùng phương pháp chồng chất dữ liệu [8] để tối ưu hóa không gian lưu trữ cơ sở dữ liệu, giảm lượng tài nguyên tiêu thụ cho thiết kế. Thêm vào đó, đề ra thêm cấu trúc giải thuật bổ sung để hỗ trợ các giá trị tùy định để thiết kế có thể hoạt động như một TCAM. Page : 1 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh 1.4 Mục tiêu, đối tượng và phạm vi nghiên cứu Mục tiêu: Bộ nhớ địa chỉ nội dung là một loại bộ nhớ đặc biệt, được sử dụng rộng rãi trong các thiết bị hạ tầng mạng để điều hướng và định địa chỉ các gói dữ liệu. Ngoài ra, bộ nhớ địa chỉ nội dung còn được sử dụng trong các ứng dụng cần tìm kiếm dữ liệu nhanh chóng, chỉ trong một chu kỳ máy. Tuy nhiên, bộ nhớ địa chỉ nội dung vẫn còn các nhược điểm như mức tiêu thụ năng lượng cao và kích thước lớn cũng như cấu trúc riêng biệt, khó tích hợp vào các FPGA đang được dùng trong nhiều ứng dụng cải thiện tốc độ mạng Internet. Đề tài này đề ra một cấu trúc bộ nhớ địa chỉ nội dung xây dựng từ các phần tử RAM trên FPGA, hỗ trợ đầy đủ các giá trị nhị phân và tuỳ định. Bên cạnh đó đề tài cũng sử dụng giải thuật xếp chồng các dữ liệu lên nhau để giảm kích thước và tài nguyên tiêu thụ. Đề tài cũng đưa ra một thiết kế mẫu bộ nhớ địa chỉ nội dung 256 x 104-bit trên FPGA Cyclone V và đánh giá khả năng ứng dụng của thiết kế trên quy mô lớn cũng như các hướng phát triển trong tương lai. Đối tượng và phạm vi nghiên cứu: Thiết kế mẫu bộ nhớ địa chỉ nội dung 256 x 104-bit trên FPGA Cyclone V và đánh giá khả năng ứng dụng của thiết kế trên quy mô lớn cũng như các hướng phát triển trong tương lai. Page : 2 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh CHƯƠNG 2. CƠ SỞ LÝ THUYẾT BỘ NHỚ ĐỊA CHỈ NỘI DUNG 2.1 Sơ lược về bộ nhớ địa chỉ nội dung 2.1.1 Giới thiệu về bộ nhớ khả lập địa chỉ nội dung (CAM) Bộ nhớ địa chỉ nội dung (CAM) là một loại bộ nhớ đặc biệt, có thể tìm kiếm toàn bộ cơ sở dữ liệu trong một chu kỳ CPU và trả về thông tin địa chỉ tương ứng [1][2][3]. Những ứng dụng của CAM có thể kể đến như: định tuyến gói Internet, bộ nhớ đệm cho vi xử lý, hoặc ứng dụng trong AI. Ngoài ra, CAM còn ứng dụng trong lĩnh vực nghiên cứu các chuỗi DNA [4]. Mặc dù CAM có nhiều ưu thế như cải thiện tốc độ tìm kiếm dữ liệu trên vi xử lý, nhưng nó tiêu thụ nhiều điện năng và gần như không có khả năng nâng cấp. 2.1.2 Giới thiệu về bộ nhớ khả lập địa chỉ nội dung 3 biến (TCAM) Bộ nhớ địa chỉ nội dung 3 biến (TCAM) là phần mở rộng của CAM, hỗ trợ thêm việc xử lý giá trị tuỳ định ‘x’. TCAM dùng tài nguyên bộ nhớ nhiều gấp 30 lần so với DDR SRAM và tiêu thụ điện năng trên mỗi bit nhớ gấp 150 lần so với SRAM [5]. Cho đến nay, TCAM là một thiết bị quan trọng trong việc cải tiến hệ thống kỹ thuật số. Việc phát triển TCAM và CAM vật lý trong vài năm trở lại đây đã trở nên chậm lại, tuy nhiên, TCAM và CAM trên FPGA thì lại phát triển nhanh chóng. Các ứng dụng tìm kiếm dữ liệu tốc độ cao ngày càng yêu cầu khắt khe hơn về TCAM trong nhiều lĩnh vực. 2.2 Sơ lược về một số nghiên cứu bộ nhớ khả lập địa chỉ nội dung Trong các giải pháp tăng tốc phần cứng gần đây, Mảng phần tử logic có thể tái lập trình (FPGA) thường được sử dụng vì sự nhanh chóng trong thiết kế mạch số và khả năng nâng cấp trực tiếp trên hệ thống. Ứng dụng của FPGA có thể kể đến như cải thiện tốc độ các gói Internet định tuyến, trí tuệ nhân tạo (AI) và nghiên cứu sinh học, chuỗi DNA, v.v [6][7]. Những ứng dụng được nêu trên thường yêu cầu các phần cứng hỗ trợ tìm kiếm dữ liệu tốc độ cao như TCAM và CAM. Bởi FPGA không hỗ trợ sẵn CAM và TCAM, do đó phương pháp đề xuất sử dụng các tài nguyên sẵn có trên mạch, như các khối bộ nhớ ( Blocks RAM) và bảng tra cứu (LUT). Nhiều nghiên cứu trước đây đề xuất sử dụng các khối RAM sẵn có bên trong FPGA để thay thế CAM và TCAM tuy nhiên cách làm này đi cũng với sự đánh đổi lượng lớn tài nguyên trong mạch theo nghiên cứu [5][8]. Nghiên cứu [9] cung cấp TCAM thuật thoán có thể mở rộng sử dụng các mảnh cấu thành FPGA (slices) làm tài nguyên chính. Xilinx đã giới thiệu một lõi IP (IP core) dùng để ứng dụng TCAM trên mạch FPGA của họ [10]. Bên cạnh đó, các phương pháp dùng để tối ưu hoá lượng tài nguyên và điện năng tiêu thụ cũng đã được thể hiện trong các nghiên cứu [11-17]. Green TCAM, dưa theo nghiên cứu [18], chứng minh rằng TCAM thuật toán cải thiện hiệu xuất đáng kể dựa trên việc cài đặt các quy tắc. Pseudo-TCAM [19] sắp xếp các tài nguyên bộ nhớ một Page : 3 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh cách đơn giản và thống nhất với nhau áp dụng cho tất cả các quy tắc và thông lượng cao. Thuật toán hỗ trợ cập nhật nhanh chóng được đề cập trong nghiên cứu [20] nhưng phải đánh đổi bằng hiệu suất. Multi-pumping SRAMs, theo nghiên cứu [15], tăng tần số hoạt động của các khối RAM nội và cho phép nhiều truy cập cùng lúc trong cùng một xung nhịp hệ thống. Với những thiết kế tần số cao, rất khó để thiết kế các RAM nội có thể đạt tốc độ nhanh hơn gấp 5 lần thiết kế của nghiên cứu [15]. Nghiên cứu [17] đề xuất một cách đặc biệt để định vị dữ liệu, nhưng nghiên cứu này chỉ đề cập đế CAM mà không nói đến việc hỗ trợ giá trị tuỳ định thường thấy trong bộ nhớ địa chỉ nội dung khi được sử dụng trong các ứng dụng được nêu ở phần trên. Nhiều đơn vị so khớp băm (hash matching unit) [21] cũng là một tuỳ chọn để triển khai TCAM thuật toán, nhưng nó gặp phải xung đột băm (hash collision). Bảng 1 cho thấy dữ liệu cơ bản thường thấy của một CAM, bao gồm hàng dữ liệu được sắp xếp theo thứ tự ưu tiên. Rule 0 là quy tắc mặc định khi dữ liệu trả về không phù hợp với bất kỳ quy tắc nào khác trong bộ nhớ. Cơ sở dữ liệu này có thể được cài đặt vào một Bộ nhớ khả lập địa chỉ nội dung hỗ trợ giá trị tùy định (TCAM) hoặc một Bộ nhớ khả lập địa chỉ nội dung không hỗ trợ giá trị tùy định (CAM) cùng với Bộ mở rộng tiền tố có kiểm soát (CPE), đơn giản là tách các giá trị tùy định và biến đổi chúng thành giá trị Nhị Phân. Như vậy, với một bộ nhớ khả lập địa chỉ nội dung mà không không hỗ trợ giá trị tùy định (CAM), nhu cầu sử dụng tài nguyên bộ nhớ là vô cùng lớn Bảng 1: Ví dụ về cơ sở dữ liệu cơ bản của TCAM Ví dụ về Bộ mở rộng tiền tố có kiểm soát (CPE) được nêu trong nghiên cứu [22]. Với số lượng lớn các quy tắc và nhiều giá trị ngẫu nhiên như trong một bộ định tuyến FIB, việc sử dụng CPE tiêu tốn một lượng lớn tài nguyên bộ nhớ. Để xây dựng bộ nhớ khả lập định địa chỉ nội dung trên FPGA, tài nguyên được sử dụng trong nghiên cứu này là các khối RAM nội được hỗ trợ trong FPGA. Bộ nhớ bên trong FPGA được cung cấp dưới dạng các ô nhớ như trong Hình 1. Mỗi ô nhớ hỗ trợ lưu trữ một số lượng kilobit dữ liệu nhất định. Ô nhớ M20K của Intel hỗ trợ 20k-bit và tương tự đối với các ô nhớ: Xilinx M9K, M10K hoặc B36K. Các ô nhớ này hỗ trợ một số lượng địa chỉ và độ dài dữ liệu nhất định tùy thuộc vào công nghệ được sử dụng. Tuy nhiên, khi sử dụng để xây dựng bộ nhớ khả lập địa chỉ nội dung, cần lưu ý rằng các ô nhớ này không hỗ trợ giá trị tùy định mà chỉ hỗ trợ giá trị nhị phân. Page : 4 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh Hình 1: Khôí RAM điển hình 2.3 Phương pháp xếp chồng dữ liệu (Data Collision) 2.3.1 Tổng Quan Để hiểu được thuật toán, trước tiên chúng ta cần hiểu cách hoạt động của bộ nhớ khả lập địa chỉ nội dung – CAM. Hoạt động cơ bản của CAM được mô tả trong Hình 2. Dữ liệu cần tìm địa chỉ, được hiểu là dữ liệu khóa, được đưa vào CAM và kết quả được trả về. Kết quả là địa chỉ tương ứng của dữ liệu đầu vào đã được cài đặt từ trước trong bộ nhớ khả lập địa chỉ nội dung. Một cách tổng quát, kết quả có thể là địa chỉ đúng của dữ liệu mà ta cần tìm địa chỉ hoặc không, và dữ liệu ngõ vào sẽ được xử lý một cách phù hợp. Khi thiết kế bộ nhớ TCAM trên FPGA, như đã đề cập trong [7] [16], cách tốt nhất để giảm số RAM và tối ưu hóa tốc độ hệ thống là cắt dữ liệu khóa thành nhiều mảnh dữ liệu với độ dài bit nhất định (độ dài của các mảnh có thể bằng nhau hoặc không). Phương pháp tối ưu nhất [7] [16] khi độ dài của các mảnh dữ liệu đúng bằng độ dài của địa chỉ ô nhớ trên FPGA. Ví dụ, đối với ô nhớ M20K của Intel, độ dài này là 9 bit. Trong phương pháp được thực hiện của nghiên cứu này, chúng ta cũng sẽ cắt dữ liệu khóa thành nhiều mảnh dữ liệu để tối ưu hóa tốc độ và giảm bộ nhớ tiêu thụ. Hình 2: Hoạt động cơ bản của bộ nhớ khả lập địa chỉ nội dung 2.3.2 Giới thiệu thuật toán chồng chập dữ liệu (Data Collision) Hình 3 cho thấy dữ liệu khóa được cắt thành các mảnh dữ liệu có độ dài nhất định. Những mảnh dữ liệu này truy cập mỗi ô nhớ tương ứng, những ô nhớ này đã được cài đặt dữ liệu trước đó, và tạo thành một Vector kết quả, được nêu trong nghiên cứu [17]. Tuy nhiên, nghiên cứu [17] không hỗ trợ các quy tắc chứa giá trị tùy định. Khi đã có được Vector kết quả, CAM sẽ phân tích và xác minh những kết quả đó để đưa ra kết quả cuối cùng của dữ liệu khóa tương ứng. Nghiên cứu được trình bày trong tài liệu này thay đổi và tổ chức lại cấu trúc xung đột dữ liệu được trình bày trong nghiên cứu Page : 5 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh [17]. Những sửa đổi và việc bổ sung một số mô-đun cần thiết cho phép các quy tắc hỗ trợ giá trị tùy định và làm giảm vấn đề tiêu thụ bộ nhớ của CPE Hình 3: Data của CAM được cắt thành nhiều mảnh và được sử dụng để tạo một vecto đối sánh ở cuối Hình 4 cho thấy giải thuật cơ bản của cấu trúc TCAM này. Dữ liệu tuân theo 3 bước chính để xử lý tạo ra kết quả. Hình 4: Luồng dữ liệu cơ bản của cấu trúc Hình 5 mô tả chi tiết quá trình thiết lập các quy tắc vào bộ nhớ. Ở đây chúng tôi lấy ví dụ về quy tắc 10-bit, được chia thành 5 mảnh dữ liệu có độ dài 2-bit. Một bảng của bộ nhớ khả lập địa chỉ nội dung này bao gồm các ô nhớ, mỗi ô chứa hai thành phần – trạng thái của ô nhớ và dữ liệu nhận dạng (ID) cho quy tắc. Cách ghi các quy tắc vào bảng như sau. Đầu tiên, các quy tắc phải ở dạng thích hợp để được điền vào bảng, nghĩa là, quy tắc phải có các mảnh dữ liệu chứa 2-bit tùy định giống nhau dưới dạng "**" hoặc không có giá trị tùy định nào. Nếu quy tắc có các phân mảnh ở dạng chỉ có một giá trị tùy định, thì quy tắc đó phải được tách thành hai quy tắc. Để cài đặt một quy tắc vào bảng, viết ID của quy tắc đó vào ô tại địa chỉ tương ứng giá trị trong các mảnh dữ liệu của quy tắc đó trong bảng và chuyển trạng thái của ô sang đã ghi (Written). Nếu ô đã có quy tắc được viết trước đó, ô đó sẽ ở trạng thái xung đột (Collision). Sau khi viết xong các quy tắc, các ô trong bảng có một trong ba trạng thái: trống, đã ghi hoặc xung đột. Khi viết quy tắc, cần đảm bảo có ít nhất n ô không xung đột nhau, thông thường, n chỉ cần bằng 1. Để xóa quy tắc khỏi bảng, xóa quy tắc đó khỏi ô đã điền, ô ở trạng thái xung đột sẽ trở thành đã ghi nếu chỉ còn lại một quy tắc được điền trong ô đó; ô ở trạng thái đã ghi sẽ trở thành ô trống. Page : 6 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh Hình 5: Đặt các quy tắc vào cơ sở dữ liệu của TCAM Để có thể tìm địa chỉ cho một khóa, một số thành phần cần được bổ sung. Tuy nhiên, ở bước này, một vectơ dữ liệu đã có thể được tìm thấy để tiếp tục quy trình xử lý. Hình 6 minh họa cách tìm khóa từ bảng dữ liệu quy tắc đã được thiết lập và trong một số trường hợp không hợp lệ, kết quả được kết luận một cách nhanh chóng. Các trường hợp xấu có thể dự đoán được trong quá trình thiết lập bảng và có thể được ngăn chặn bằng cách tối ưu hóa phần mềm. Theo nghiên cứu [16], đối với một TCAM có n rules và chứa m data ngẫu nhiên, tỷ lệ xung đột cho một cột là 26%. Đối với z cột, tỷ lệ để có toàn bộ z cột đều ở trạng thái xung đột là 26%z , tỷ lệ này là rất nhỏ với một dữ liệu khóa dài. Hình 6: Tìm kiếm vectơ đối sánh từ cơ sở dữ liệu Ở bước tiếp theo, các quy tắc đã được thiết lập hoàn tất trong bảng. Đối với mỗi quy tắc, chúng ta có một Vector dữ liệu đánh dấu các giá trị tùy định tương ứng – gọi là Vector mặt nạ. Mỗi bit trong vectơ này đánh dấu một đoạn giá trị tùy định “**” (trong Page : 7 Luận Văn Thạc Sỹ GVHD: TS. Trần Hoàng Linh ví dụ này, mỗi bit trong Vector mặt nạ đánh dấu 2-bit giá trị). Với mỗi đoạn có chứa ID (không ở trạng thái xung đột), ta cần tìm một Vector mặt nạ tương ứng với ID đó để thực hiện việc so sánh. Có rất nhiều cách có thể được áp dụng để tìm kiếm vectơ mặt nạ trong trường hợp này, mỗi cách khác nhau sẽ có những ưu nhược điểm khác nhau khi áp dụng trên phần cứng. Vectơ mặt nạ và quá trình đánh dấu được mô tả trong Hình 7. Các vectơ mặt nạ được trình bày trong hình dưới dạng một chuỗi 5-bit với mỗi bit tương ứng với một đoạn dữ liệu được che. Hình 7: Vectơ mặt nạ từ vectơ ID quy tắc Bước tiếp theo, TCAM thực hiện so sánh các đoạn ID trong Vector ID đã được đánh dấu và đưa ra kết quả cuối cùng bao gồm tín hiệu cho biết liệu khóa có khớp với dữ liệu quy tắc hay không và, nếu có, thì kết quả sẽ là ID cần tìm của quy tắc. Trong trường hợp có hơn 1 kết quả trùng khớp, các đoạn khóa vẫn phải qua một bộ nhớ khác để xác nhận lại , để đề phòng xác suất xảy ra lỗi trùng khớp. Việc xác nhận lại được thực hiện trước khi so sánh thứ tự ưu tiên vì nếu so sánh ưu tiên trước sẽ có khả năng xảy ra trường hợp lỗi trùng khớp. Bước này được thể hiện trong Hình 8. Hình 8: Xác nhận lại vectơ để có kết quả chính xác Mức độ ưu tiên được thiết lập vào bảng xác nhận và với các bộ quy tắc trong bộ nhớ khả lập địa chỉ nội dung lớn có thể được ưu tiên phân cấp trước giữa các vùng để giảm độ phức tạp khi thực hiện so sánh các thứ tự ưu tiên. Sau khi so sánh thứ tự ưu tiên Page : 8