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.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.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 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 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 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. 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.