Memorie Adresabilă prin Conținut

1. Introducere

Memoria adresabilă prin conţinut ( CAM – content addresable memory ) reprezintă o memorie în care căutarea se face după o cheie de intrare, informaţia stocată pentru acea cheie fiind întoarsă la ieşirea memoriei. Memoriile CAM pot fi implementate la nivel de circuit, având un timp de răspuns de un singur ceas, sau la nivel de logică de căutare hardware sau software într-o memorie RAM.

Memoriile CAM sunt folosite în aplicaţii care necesită viteze de căutare ridicate. Exemple de astfel de aplicaţii pot fi codarea / decodarea Huffman, compresia Lempel-Ziv, codarea imaginii, dar în special în aplicaţii de networking pentru clasificarea şi routarea pachetelor de IP.

2. Tema proiectului

Tema acestui proiect constă în conceperea unei arhitecturi pentru o logică de căutare hardware, implementarea arhitecturii într-un limbaj de descriere hardware ( Verilog/VHDL ) şi verificarea acesteia..

3. Arhitectura propusă

Figura 1.

Modulul cam_engine conţine logica de căutare hardware a datelor în interiorul memoriei adresabile prin conţinut SPRAM. Din punct de vedere al implementării este organizat sub forma unui automat cu trei stări:

- INIT_STATE: starea de stand-by

- READ: starea în care se caută şi se citesc date din memorie

- WRITE: starea în care se înlocuiesc date sau se scriu date noi în memorie

Semnalele de intrare şi ieşire în/din modul precum şi dimensiunile acestora sunt cele indicate în figura 1. Ele reprezintă principalele atribute ale arhitecturii (utilizatorul are control asupra lor) şi au următoarele semnificaţii:

- reset: semnal de reset

- clk: semnal de ceas

- key: cheia după care se face căutarea

- data: data ce trebuie scrisă (la citire nu are importanţă)

- read: semnal ce comandă începutul operaţiei de citire

- write: semnal ce comandă începutul operaţiei de scriere

- ram_address: adresa din memorie la care se va „uita”modulul la un moment dat

- ram_data_in: data ce este trimisă către memorie; se obşine prin concatenarea semnalelor key şi data (în această ordine)

- ram_data_out: data returnată de memorie

- info: returnează data citită din memorie

- found: semnalizează terminarea cu succes a operaţiei de scriere/citire

- done: indică terminarea operaţiei de scriere/citire

Pentru prelucrarea semnalelor modulul mai conţine o serie se „semnale”/„registre” interne, transparente la o privire din exterior (din punctul de vedere al utilizatorului; nu fac obiectul arhitecturii). Acestea sunt:

- state : registru în care se ţine minte starea curentă a automatului

- inc: registru increment folosit la calcularea de adrese succesive în memorie

- valid: registru ce semnalează găsirea primei locaţii goale din memorie (unde se va face scrierea)

- last_empty: registru ce reţine adresa relativă a primei locaţii goale din memorie

- finished_read: semnal ce indică terminarea operaţiei de citire

- finished_write: semnal ce indică terminarea operaţiei de scriere

- hash: conţine rezultatul restrângerii cheii de căutare

- found_it: indică găsirea cheii căutate

- no_space: indică terminarea spaţiului de căutare

- test: reţine cheia citită de la o locaţie din memorie pe toată durata operaţiilor în care acesta este implicată (comparare)

Memoria SPRAM are o organizare a datelor tipică memoriilor cu adresare prin conţinut: la fiecare adresă se reţine atât informaţia utilă cât şi cheia după care acesta va fi identificată ( ram_data_in <= {key,data} ). Dimensiunea aceteia este impusă de algoritmul de căutare, după cum se va arăta în cele ce urmează.