lOMoARcPSD|46958826 lOMoARcPSD|46958826
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA ĐIỆN - ĐIỆN TỬ BỘ MỘN ĐIỆN TỬ BÁO CÁO ĐỒ ÁN 1
THIẾT KẾ BỘ NHỚ ĐỊA CHỈ NỘI DUNG (TCAM)
THỰC HIỆN TRÊN FPGA
Giảng viên hướng dẫn: Trịnh Vũ Đăng Nguyên
Sinh viên thực hiện MSSV Nguyễn Long Vũ 1915979 Lê Quang Vinh 1915932
TP.HCM, tháng 6 năm 2022 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1 MỤC LỤC Trang
DANH MỤC HÌNH ẢNH..................................................................................................4
DANH MỤC BẢNG..........................................................................................................5
LỜI MỞ ĐẦU....................................................................................................................6
CHƯƠNG 1. GIỚI THIỆU VỀ ĐỀ TÀI............................................................................7
1.1. Lí do thực hiện đề tài................................................................................................7
1.2. Mục đích nghiên cứu................................................................................................7
1.3. Nội dung thực hiện...................................................................................................7
1.4. Đối tượng và phạm vi nghiên cứu............................................................................7
CHƯƠNG 2. CƠ SỞ LÝ THUYẾT BỘ NHỚ ĐỊA CHỈ NỘI DUNG...............................8
2.1. Giới thiệu chung về bộ nhớ địa chỉ nội dung............................................................8
2.1.1. Bộ nhớ tìm kiếm theo nội dung CAM................................................................8
2.1.2. Bộ nhớ có thể định địa chỉ nội dung TCAM......................................................9
2.2. Ứng dụng của CAM và TCAM..............................................................................10
2.3. Cách tổ chức bộ nhớ TCAM..................................................................................11
2.3.1. Cách cập nhật bộ nhớ TCAM...........................................................................13
2.3.2. Cách tìm kiếm bộ nhớ TCAM..........................................................................14
2.3.3. Cách mở rộng bộ nhớ TCAM..........................................................................15
2.3.4. Giới thiệu về các thuật toán sử dụng TCAM dựa trên RAM............................16
CHƯƠNG 3: ĐẶC TẢ THIẾT KẾ LÕI IP BỘ NHỚ ĐỊNH ĐỊA CHỈ NỘI DUNG 3
BIẾN (TCAM)..................................................................................................................19
3.1. Kiến trúc hệ thống..................................................................................................19
3.1.1. Sơ đồ khối top level.........................................................................................19
3.1.2. Mô tả tín hiệu vào ra........................................................................................20
3.1.3. Nguyên tắc hoạt dộng khối top level................................................................21
3.2. Các khối trong hệ thống.........................................................................................21
3.2.1. Counter Engine................................................................................................21
3.2.1.1. Nguyên tắc hoạt động....................................................................................21
3.2.1.2. Sơ đồ khối.....................................................................................................22 Trang 1 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
3.2.1.3. Giải thuật.......................................................................................................22
3.2.1.4. Mô tả tín hiệu vào ra.....................................................................................22
3.2.2. Khối xử lý trung tâm........................................................................................23
3.2.2.1. Nguyên tắc hoạt động....................................................................................23
3.2.2.2. Sơ đồ khối.....................................................................................................23
3.2.2.3. Sơ đồ khối chi tiết.........................................................................................24
3.2.2.4. Giải thuật.......................................................................................................24
3.2.2.5. Mô tả tín hiệu vào ra.....................................................................................25
3.2.3. Khối Compare Engine......................................................................................26
3.2.3.1. Nguyên tắc hoạt động....................................................................................26
3.2.3.2. Sơ đồ khối.....................................................................................................26
3.2.3.3. Giải thuật.......................................................................................................26
3.2.3.4. Mô tả tín hiệu vào ra.....................................................................................26
3.2.4. Khối Change Engine........................................................................................27
3.2.4.1. Nguyên tắc hoạt động....................................................................................27
3.2.4.2. Sơ đồ khối.....................................................................................................28
3.2.4.3. Giải thuật.......................................................................................................28
3.2.4.4. Mô tả tín hiệu vào ra.....................................................................................28
3.2.5. Khối Search Engine.........................................................................................29
3.2.5.1. Nguyên tắc hoạt động....................................................................................29
3.2.5.2. Sơ đồ khối.....................................................................................................29
3.2.5.3. Mô tả tín hiệu vào ra.....................................................................................30
3.2.6. Khối Confirm Engine.......................................................................................30
3.2.6.1. Nguyên tắc hoạt động....................................................................................30
3.2.6.2. Sơ đồ khối.....................................................................................................31
3.2.6.3. Mô tả tín hiệu vào ra.....................................................................................31
3.2.7. Khối Priority Encoder......................................................................................31
3.2.7.1. Nguyên tắc hoạt động....................................................................................31
3.2.7.2. Sơ đồ khối.....................................................................................................32
3.2.7.3. Mô tả tín hiệu vào ra.....................................................................................32
CHƯƠNG 4: KIỂM TRA THỰC NGHIỆM TRÊN FPGA..............................................33 Trang 2 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
4.1. Kiểm tra và đánh giá thiết kế trên Quartus.............................................................33
4.1.1. Kết quả synthesis.............................................................................................33
4.1.2. Kết quả timing..................................................................................................33
4.1.3. Kết quả Memory Usage...................................................................................34
4.2. Xây dựng mô phỏng bằng ModelSim.....................................................................35
4.2.1. Chuẩn bị bảng TCAM......................................................................................35
4.2.2. Xây dựng các testcase và kết quả mô phỏng....................................................36
CHƯƠNG 5: TỔNG KẾT................................................................................................38
5.1. Hạn chế..................................................................................................................38
5.2. Kết luận..................................................................................................................38
DANH MỤC TÀI LIỆU THAM KHẢO..........................................................................39 Trang 3 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1 DANH MỤC HÌNH ẢNH Trang
Hình 2.1. Minh hoạ một khối CAM....................................................................................9
Hình 2.2. Minh hoạ một khối TCAM...............................................................................10
Hình 2.3. Tổ chức bộ nhớ TCAM theo RAM...................................................................12
Hình 2.4. Minh họa cách ghi vào TCAM.........................................................................13
Hình 2.6. Cấu trúc của một khối TCAM mở rộng theo độ rộng.......................................15
Hình 2.5. Cấu trúc của một khối TCAM mở rộng độ sâu.................................................16
Hình 3.1: Sơ đồ khối top level..........................................................................................19
Hình 3.2: Sơ đồ chi tiết khối top level..............................................................................19
Hình 3.3: Sơ đồ khối bộ đếm............................................................................................22
Hình 3.4: Sơ đồ khối xử lý trung tâm...............................................................................24
Hình 3.5: Sơ đồ chi tiết khối bộ xử lý trung tâm...............................................................24
Hình 3.6: Sơ đồ khối Compare Engine.............................................................................26
Hình 3.7: Sơ đồ khối Change Engine...............................................................................28
Hình 3.8: Sơ đồ khối Search Engine.................................................................................29
Hình 3.9: Sơ đồ khối Confirm Engine..............................................................................31
Hình 3.10: Sơ đồ khối Priority Encoder............................................................................32
Hình 4.1. Mô tả kết quả phần cứng tài nguyên sử dụng trên kit FPGA............................33
Hình 4.2. Kết quả Timing.................................................................................................33
Hình 4.3. Kết quả Analysis & Synthesis lấy từ RAM summary.......................................34
Hình 4.4. Xuất bảng data của TCAM...............................................................................35
Hình 4.6. Mô phỏng dạng sóng.........................................................................................37 Trang 4 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1 DANH MỤC BẢNG Trang
Bảng 2.1. Bảng kí hiệu được sử dụng................................................................................12
Bảng 2.2. Bảng lưu các giá trị trùng khớp của các từ TCAM............................................14
Bảng 3.1. Mô tả tín hiệu vào ra khối top level...................................................................20
Bảng 3.2. Mô tả tín hiệu vào ra khối Counter Engine.......................................................22
Bảng 3.3. Mô tả tín hiệu vào ra khối xử lý trung tâm........................................................25
Bảng 3.4. Mô tả tín hiệu vào ra Compare Engine..............................................................26
Bảng 3.5. Mô tả tín hiệu vào ra Change Engine................................................................28
Bảng 3.8: Mô tả tín hiệu vào ra Change Engine................................................................30
Bảng 3.7. Mô tả tín hiệu vào ra khối Confirm Engine.......................................................31
Bảng 3.8. Mô tả tín hiệu vào ra Priority Encoder..............................................................32
Bảng 4.1. Các trường hợp mô phỏng testcase...................................................................36 Trang 5 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1 LỜI MỞ ĐẦU
Ngày nay cùng với sự phát triển của khoa học kĩ thuật nói chung và ngành công
nghệ thông tin nói riêng, máy tính đang trở nên rất phổ biến trong cuộc sống của con
người. Nó hiện diện ở rất nhiều lĩnh vực, xuất hiện ở rất nhiều nơi từ gia đình đến các xí
nghiệp, các công ty lớn nhỏ, … nhằm phục vụ nhu cầu công việc và giải trí.
Trong lĩnh vực công nghệ nói chung và trong môi trường mạng nói riêng thì việc
tra cứu và tìm kiếm địa chỉ Ethernet, lọc địa chỉ trong firemalls, bridges, switches và
routers là rất quan trọng. Việc tìm kiếm phải được thực hiện chính xác và nhanh chóng.
Các TCAM (bộ nhớ nội dung định địa chỉ bậc ba) rất phù hợp cho hoạt động này.
Cùng với đó, ngày càng có nhiều sự quan tâm đến việc triển khai TCAM bằng
cách sử dụng phần cứng có thể cấu hình lại như FPGA. Hầu hết các thiết kế TCAM dựa
trên FPGA hiện tại đều dựa trên việc triển khai brute-force, dẫn đến việc sử dụng tài
nguyên trên chip không hiệu quả. Do đó, các thiết kế hiện tại chỉ hỗ trợ kích thước TCAM
nhỏ ngay cả với các thiết bị FPGA lớn. Chúng cũng bị suy giảm thông lượng đáng kể khi
triển khai TCAM lớn, nguyên nhân chủ yếu là do mã hóa ưu tiên sâu.
Trong bài báo cáo này, chúng em đã trình bày một số khái niệm liên quan đến
TCAM, cấu trúc và hoạt động cơ bản của một TCAM, các phương cấu thành TCAM dựa
trên bộ nhớ truy cập ngẫu nhiên có thể mở rộng (RAM) nhằm mục đích triển khai hiệu
quả trên các FPGA hiện đại.
Trong quá trình thực hiện đề tài, do khả năng đọc dịch tài liệu tiếng anh còn hạn
chế và nhiều thiếu sót, chúng em rất mong đợi có những góp ý từ thầy cô để chúng em có thể hoàn thiện hơn.
Chúng em chân thành cảm ơn thầy Trịnh Vũ Đăng Nguyên đã dành nhiều thời
gian hướng dẫn và chỉ bảo tận tình trong suốt quá trình chúng em thực hiện đề tài để có
được một kết quả tốt nhất. Trang 6 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
CHƯƠNG 1. GIỚI THIỆU VỀ ĐỀ TÀI
1.1. Lí do thực hiện đề tài
Ngày càng có nhiều sự quan tâm đến việc triển khai TCAM bằng cách sử dụng
phần cứng có thể cấu hình lại như FPGA (Field Programmable Gate Array). Hầu hết các
thiết kế TCAM dựa trên FPGA hiện tại đều dựa trên việc triển khai brute force (Brute
force hoạt động bằng cách thử tất cả các chuỗi mật khẩu có thể để tìm ra mật khẩu), dẫn
đến việc sử dụng tài nguyên trên chip không hiệu quả. Do đó, các thiết kế hiện tại chỉ hỗ
trợ kích thước TCAM nhỏ ngay cả với các thiết bị FPGA lớn. Chúng cũng bị suy giảm
thông lượng đáng kể khi triển khai TCAM lớn, nguyên nhân chủ yếu là do mã hóa ưu tiên sâu.
Biết được một số hạn chế đó, chúng em muốn nghiên cứu thực hiện thiết kế lại 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 để
có thể 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. Cùng với đó là cấu trúc một TCAM dựa trên bộ nhớ truy cập ngẫu nhiên có thể mở
rộng (RAM) nhằm mục đích triển khai hiệu quả trên các FPGA hiện đại.
1.2. Mục đích nghiên cứu
Tìm hiểu được cách thức hoạt động của một bộ nhớ định địa chỉ nội dung và cách mở rộng chúng.
Thiết kế lại 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.
1.3. Nội dung thực hiện Gồm 2 phần:
Phần 1: Phân tích lý thuyết bộ nhớ định địa chỉ TCAM và đề ra những phương
pháp chính trong việc triển khai TCAM dựa trên RAM.
Phần 2: Thực hiện thiết kế và mô phỏng các giải thuật trên nền tảng FPGA Trang 7 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
1.4. Đối tượng và phạm vi nghiên cứu
Thiết kế ra được một bộ nhớ truy xuất dữ liệu có kích thước 256 x 104-bit trên nền
tảng FPGA (cụ thể là FPGA Cyclone V), từ đó đánh giá khả năng ứng dụng trong thực tế.
CHƯƠNG 2. CƠ SỞ LÝ THUYẾT BỘ NHỚ ĐỊA CHỈ NỘI DUNG
2.1. Giới thiệu chung về bộ nhớ địa chỉ nội dung
2.1.1. Bộ nhớ tìm kiếm theo nội dung CAM
Bộ nhớ tìm kiếm theo nội dung CAM (Content Addressable Memory) là sự phát
triển vượt bậc của bộ nhớ truy cập ngẫu nhiên (RAM). Ngoài các thao tác đọc và viết
thông thường, CAM cũng hỗ trợ các thao tác tìm kiếm. CAM lưu trữ một số từ dữ liệu và
so sánh một từ khóa tìm kiếm với tất cả mục nhập được lưu trữ song song. Nếu tìm thấy
giá trị trùng khớp, vị trí bộ nhớ ương ứng sẽ được truy xuất. Khi có nhiều kết quả trùng
khớp, bộ mã hóa ưu tiên sẽ xử lí kết quả phù hợp có mức độ ưu tiên cao nhất.
Cách thức hoạt động của CAM gần như ngược lại với bộ nhớ truy cập ngẫu nhiên
(RAM). Để truy xuất dữ liệu nằm trên RAM, H
ệ điều hành cung cấp địa chỉ bộ nhớ nơi
dữ liệu được lưu trữ. Mặt khác, dữ liệu được lưu trữ trên CAM có thể được truy cập bằng
cách tự tìm kiếm nội dung và bộ nhớ truy xuất các địa chỉ mà nội dung đó có thể được tìm
thấy. Vì tính chất s ong song của nó, CAM nhanh hơn nhiều so với RAM để tìm kiếm.
Một từ tìm kiếm trong bộ nhớ CAM sẽ cho ra kết quả là trùng khớp (MATCH)
hoặc không trùng khớp, có thể đưa ra cả địa chỉ trùng khớp nếu cần thiết. Bộ nhớ CAM
có khả năng tìm kiếm song song cho một số lượng rất lớn các nội dung và có cơ chế tổ
chức rất khác so với các phương pháp tìm kiếm theo dạng duyệt tuần tự. Trên thực tế, thời
gian trễ của thuật toán tìm kiếm tuần tự trên bộ nhớ RAM tỷ lệ thuận với số lượng từ khóa
và thường không cố định nên không thể áp dụng cho các thiết bị chuyển mạch thời gian
thực. Bộ nhớ này là một phần rất quan trọng trong thiết kế của các thiết bị mạng nói
chung và Switch lớp 2 nói riêng. Trang 8 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
Hình 2.1. Minh hoạ một khối CAM
Như mô hình trên, một từ khóa sẽ được tìm kiếm song song ở bốn vị trí đã lưu từ
CAM. Tại các địa chỉ 00, 01, 10 sẽ cho ra kết quả MATCH = 0 do từ đã lưu khác với từ
khóa tìm kiếm. Tại địa chỉ 11 sẽ cho ra kết quả MATCH = 1, tùy theo cấu hình của CAM
có thể đưa ra cả địa chỉ của từ MATCH.
2.1.2. Bộ nhớ có thể định địa chỉ nội dung TCAM
Bộ nhớ có thể định địa chỉ nội dung TCAM (Ternary Content Addressable
Memory) là CAM bậc ba. Điều này cho phép hệ điều hành khớp với trạng thái thứ ba,
"X". Trạng thái X là một “mặt nạ”, nghĩa là giá trị của nó có thể là bất kỳ thứ gì. Từ
"ternary" đề cập đến số lượng đầu vào mà bộ nhớ có thể lưu trữ và truy vấn: 0, 1 và X
hoặc thẻ đại diện. Mặt khác, CAM nhị phân chỉ có thể truy vấn bằng cách sử dụng 1 và 0.
Giao diện tra cứu của TCAM nhận từ khóa tra cứu và đưa ra kết quả có chứa một
tín hiệu cho biết từ khóa đó có khớp (MATCH) với bất kì một từ TCAM nào đã được lưu
trong bộ nhớ hay không. Nếu có bất kì một vị trí khớp, bộ nhớ TCAM sẽ đưa ra địa chỉ
của từ khóa đó, một từ khóa có thể được khớp với nhiều vị trí được lưu. Do có nhiều vị trí
khớp nên bộ nhớ TCAM sẽ có thêm bộ mã hóa ưu tiên để lựa chọn ví trí cần tìm. Trang 9 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
Hình 2.2. Minh hoạ một khối TCAM
Như mô hình trên, một từ khóa được đưa vào bộ nhớ TCAM để tìm kiếm, ở hai địa
chỉ 00 và 01 khác với từ khóa nên sẽ cho kết quả MATCH = 0. Tại địa chỉ 10 và 11 do từ
TCAM đã lưu có dạng 10011xx và 100110x nên từ khóa tìm kiếm chỉ cần trùng khớp với
năm bit đầu và sáu bit đầu, các còn lại có thể nhận bất kì giá trị nào sẽ cho kết quả
MATCH = 1. Kết quả của tìm kiếm sẽ được OR với nhau, nếu một vị trí MATCH = 1 thì
từ khóa tìm kiếm sẽ cho kết quả MATCH. Quá trình tìm kiếm có thể cho ra kết quả là địa
chỉ của từ được tìm kiếm, tuy nhiên để đưa ra vị trí, các kết quả MATCH sẽ được đưa vào
bộ mã hóa ưu tiên, thường sẽ chọn vị trí đầu tiên xuất hiện bit 1.
2.2. Ứng dụng của CAM và TCAM
CAM và TCAM được ứng dụng rộng rãi cho hạ tầng mạng và các chức năng tìm
kiếm khác nhau. Trên thực tế, có những cơ sở như Google, Bing, Yahoo!... với lượng dữ
liệu vô cùng lớn không thể dùng công cụ tìm kiếm thông thường bằng cách duyệt tuần tự
để đưa ra kết quả trùng khớp được vì sẽ tốn rất nhiều thời gian. Tuy nhiên, những hệ
thống tìm kiếm này đều dùng một công cụ tìm kiếm gọi là Search Engine (SE), là một
loại hệ điều hành được thiết kế với chức năng tìm kiếm các thông tin trên mạng World
Wide Web. Khi người dùng sử dụng công cụ tìm kiếm, họ sẽ cần phải nhập một từ khóa
của chủ đề mình cần tìm hiểu để có thể nhận về một bảng kết quả có chứa các trang web,
hình ảnh, video, tài liệu,…có liên quan đến chủ đề tìm kiếm đó. Các kết quả trả về này sẽ Trang 10 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
được sắp xếp theo một thứ tự nhất định bằng các thuật toán tìm kiếm của SE, và mỗi SE
sẽ có một thuật toán tìm kiếm khác nhau. Tương tự như với đối với hạ tầng mạng nói
chung và với thiết bị chuyển mạch hai lớp nói riêng, CAM và TCAM sẽ có nhiệm vụ tìm
kiếm các thông tin cần thiết để thiết bị chuyển mạch có thể làm việc với tốc độ cao.
2.3. Cách tổ chức bộ nhớ TCAM
Để hiểu rõ về cách tổ chức TCAM, chúng ta cần hiểu rõ các định nghĩa sau :
- Độ sâu của TCAM (hoặc RAM) là số từ trong TCAM (hoặc RAM). Ký hiệu là N.
- Chiều rộng của TCAM (hoặc RAM) là chiều rộng (tức là số bit) của mỗi từ
TCAM (hoặc RAM). Ký hiệu là W.
- Kích thước của TCAM (hoặc RAM) là tổng số bit của TCAM (hoặc RAM). Nó bằng N × W.
- Độ rộng địa chỉ của RAM là số bit của địa chỉ RAM. Ký hiệu là d. Lưu ý rằng N = 2d đối với RAM.
Một từ TCAM có dạng N × W sẽ được biểu diễn bởi một bộ nhớ RAM 2W × N,
việc quy đổi độ rộng bit của TCAM sang bộ nhớ RAM tính theo hàm mũ, khi đó W bit
TCAM sẽ cần có 2W bit địa chỉ của RAM tương ứng. Trên thực tế tỷ lệ RAM trên TCAM
được dùng như một chỉ số để đo đạc mức độ tối ưu tài nguyên của thiết kế.
Ví dụ: RAM 2 × 1 bao gồm 2 từ trong đó mỗi từ là 1 bit. Trang 11 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
Hình 2.3. Tổ chức bộ nhớ TCAM theo RAM
(a) là tổ chức bộ nhớ TCAM 1 x 2 dựa trên RAM 4 x 1
(b) là tổ chức bộ nhớ TCAM 1 x 3 dựa trên RAM 8 x 1
(c) là tổ chức bộ nhớ của TCAM 2 x 2 dựa trên RAM 4 x 2
(d) tổ chức bộ nhớ của TCAM 2 x 3 dựa trên RAM 8 x 2
Chúng ta còn có các kí hiệu khác được liệt kê trong bảng sau :
Bảng 2.1. Bảng kí hiệu được sử dụng Kí hiệu Mô tả k
Dữ liệu đầu vào hoặc số nhị phân t Một từ Ternary A
Bảng chữ cái cho các kí tự 1 bit An
Tập hợp tất cả các chuỗi n-bit trên A |s|
Chiều dài của 1 chuỗi s ∈ An Trang 12 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
2.3.1. Cách cập nhật bộ nhớ TCAM
Quy tắc cập nhật TCAM: Một từ TCAM khi được ghi vào RAM sẽ được ghi lần
lượt tất cả các địa chỉ của RAM đó, tức là sẽ ghi từ địa chỉ 0 cho đến địa chỉ 2W – 1 của
RAM. Tại những địa chỉ có vị trí bit tương ứng trùng với bit không chứa X của từ TCAM
thì dữ liệu sẽ được ghi là 1.
Tổng quát: RAM [k][i] = 1 nếu k match t và ngược lại RAM [k][i] = 0 Với
k: là từ TCAM biểu diễn bởi k-bit trong TCAM
t: là từ TCAM đầu vào để ghi vào RAM[i]
i: là từ TCAM thứ i được ghi vào TCAM
Ví dụ: Minh họa Cách ghi vào TCAM
Hình 2.4. Minh họa cách ghi vào TCAM
Ở hình trên, 2 từ TCAM 2 bit có giá trị 1X và 01 khi được ghi vào RAM, đầu tiên
từ 1X được ghi vào RAM[k][0], tại các giá trị k = 10 hoặc k = 11 thì sẽ được ghi 1 và các
giá trị còn lại ghi 0. Đối với từ 01 sẽ được ghi vào RAM[k][1], duy nhất chỉ tại vị trí k =
01 được ghi bit 1 còn lại sẽ ghi bit 0, ở trường hợp này từ TCAM sẽ được ghi tương tự như một khối CAM Trang 13 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
2.3.2. Cách tìm kiếm bộ nhớ TCAM
Tìm kiếm bộ nhớ TCAM là quá trình đọc dữ liệu trong RAM, dữ liệu được lưu
trong RAM được gọi là giá trị trùng khớp.
Ví dụ: 4 từ TCAM (N = 4 và W = 4) : 0110 , 110X , 01XX , XXXX được ghi vào RAM như bảng sau :
Bảng 2.2. Bảng lưu các giá trị trùng khớp của các từ TCAM Địa chỉ 0110 011X 0XXX XXXX 0000 0 0 1 1 0001 0 0 1 1 0010 0 0 1 1 0011 0 0 1 1 0100 0 0 1 1 0101 0 0 1 1 0110 1 1 1 1 0111 0 1 1 1 1000 0 0 0 1 1001 0 0 0 1 1010 0 0 0 1 1011 0 0 0 1 1100 0 0 0 1 1101 0 0 0 1 1110 0 0 0 1 1111 0 0 0 1
Giả sử một từ khóa 0110 được tra cứu thì chuỗi bit đầu ra của từ khóa đó sẽ nhận
được là 1111, tức là từ khóa này trùng khớp với cả 4 từ TCAM được lưu. Nếu chỉ yêu cầu
tìm kiếm từ khóa ra kết quả là trùng khớp hay không thì đầu ra sẽ được OR lại với nhau
và cho ra kết quả là trùng khớp. Nếu yêu cầu cả địa chỉ của từ khóa thì bộ mã hóa ưu tiên
sẽ có nhiệm vụ chọn ra từ TCAM có độ ưu tiên cao hơn và cho ra vị trí của từ đó. Thông
thường bộ mã hóa ưu tiên sẽ chọn ra vị trí đầu tiên xuất hiện giá trị trùng khớp, tức là kết
quả của quá trình tìm kiếm sẽ là trùng khớp tại vị trí 0 (từ đầu tiên). Trang 14 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
2.3.3. Cách mở rộng bộ nhớ TCAM
Để tăng kích thước của bộ nhớ TCAM, có hai cách để mở rộng bộ nhớ TCAM là
mở rộng theo độ sâu (số từ) hay mở rộng theo độ rộng (độ dài bit của mỗi từ)
Phần mở rộng về độ rộng
Với cách mở rộng theo độ rộng, một giá trị hay một dữ liệu trước khi được lưu vào
khối TCAM sẽ được tách ra thành các giá trị hay dữ liệu con tương ứng với các khối bộ
nhớ con. Thông thường việc ghi một từ TCAM sẽ là tuần tự từ khối con này đến khối con
tiếp theo, tín hiệu hoàn thành ghi của khối trước sẽ là tín hiệu ghi của khối sau, tuy nhiên
để tiết kiệm thời gian có thể ghi các khối con song song, cách ghi này sẽ phức tạp hơn
trong việc điều khiển. Đầu ra của khối TCAM mở rộng là trùng khớp khi tất cả đầu ra của
các khối con là trùng khớp tức là các đầu ra của mỗi khối sẽ được AND lại với nhau sau
đó sẽ vào khối mã hóa ưu tiên ra được kết quả ID của dữ liệu khóa.
Hình 2.6. Cấu trúc của một khối TCAM mở rộng theo độ rộng
Phần mở rộng về độ sâu
Mở rộng theo độ sâu là các từ TCAM sẽ được ghi lần lượt vào các khối TCAM
đơn vị, khi ghi hết một khối TCAM đơn vị sẽ nhảy sang khối TCAM đơn vị tiếp theo.
Đầu ra của các khối được vào cổng OR để lấy kết quả trùng khớp, điều này có nghĩa là
chỉ cần một khối cho giá trị trùng khớp thì quá trình tìm kiếm sẽ cho kết quả trùng khớp.
Ngoài ra, kết quả ID trùng khớp của cả mỗi khối TCAM nhỏ hơn sẽ đi vào bộ mã hoá ưu
tiên để lấy ra địa chỉ ID trùng khớp cuối cùng của dữ liệu khóa. Trang 15 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
Hình 2.5. Cấu trúc của một khối TCAM mở rộng độ sâu
2.3.4. Giới thiệu về các thuật toán sử dụng TCAM dựa trên RAM
Như đã thảo luận trước đó, một TCAM N × W có thể được xây dựng bằng cách sử
dụng P TCAM hẹp (P = 1, 2, …W). Kích thước của TCAM thứ i là N × Wi (i = 1, 2, …
P) và W = . Gọi RAMi biểu thị RAM tương ứng với TCAM hẹp thứ i (i = 1, 2, … P) .
Kích thước của RAMi là 2Wi × N, i = 1, 2, …P. Do đó N × W TCAM có thể được thực
hiện bằng cách sử dụng P RAM này.
Thuật toán tra cứu ( Lookup )
Dưới đây là thuật toán tìm kiếm dữ liệu trên TCAM dựa trên RAM Trang 16 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
Input: 1 dãy W-bit key k
Input: {RAMi}, i = 1,2, … P.
Output: 1 vector phù hợp N-bit m
1: Chia k thành các đoạn P: k→{k1 ,k2 ,…kp }
|ki| = Wi, i = 1,2, … P
2: Khởi tạo m để tất cả là 1: m ←11…1
3: for i← 1 to P do {bitwise AND} 4: m ← m &
RAMi[ki] 5:end for
Thuật toán cập nhật ( Update )
Cập nhật TCAM có thể là thêm hoặc xóa một từ TCAM cụ thể. Thuật toán dưới
đây cho thấy thuật toán để thêm hoặc xóa từ thứ n của TCAM trong phần tử dựa trên
RAM, trong đó n = 1, 2,…, N.
Input : 1 kí tự ternary W-bit t
Input : Chỉ số của t : n
Input : Thao tác cập nhật : op ∈ { add , delete }
Output : cập nhật { RAMi } , i + 1,2 ,…P.
1: Chia t thành các đoạn P : t→{t1 ,t2 ,…
tp } |ti| = Wi , i = 1,2,…P
2: for i← 1 to P do { update each RAM }
3: for k ← 0 to 2Wi – 1 do 4:
if k match ti and op == add then 5: RAMi[k][n] = 1 6: else 7: RAMi[k][n] = 0 8: end if 9: end for Trang 17 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1 10: end for Trang 18 lOMoARcPSD|46958826
GVHD: Trịnh Vũ Đăng Nguyên Đồ án 1
CHƯƠNG 3: ĐẶC TẢ THIẾT KẾ LÕI IP BỘ NHỚ ĐỊNH ĐỊA CHỈ NỘI DUNG 3 BIẾN (TCAM)
3.1. Kiến trúc hệ thống
3.1.1. Sơ đồ khối top level
Hình 3.1. Sơ đồ khối top level
Hình 3.2: Sơ đồ chi tiết khối top level Trang 19