Memorie adresabilă conținutului - Content-addressable memory

Memorie adresabilă pentru conținut

Memoria adresabilă conținutului ( CAM ) este un tip special de memorie de calculator utilizată în anumite aplicații de căutare de mare viteză. Este, de asemenea, cunoscut sub numele de memorie asociativă sau stocare asociativă și compară datele de căutare de intrare cu un tabel de date stocate și returnează adresa datelor potrivite.

Unitatea de recunoaștere a cuvintelor de date a fost propusă de Dudley Allen Buck în 1955.

CAM este frecvent utilizat în dispozitivele de rețea în care accelerează operațiunile de transmitere a bazei de informații și a tabelelor de rutare . Acest tip de memorie asociativă este, de asemenea, utilizat în memoria cache. În memoria cache asociativă, atât adresa, cât și conținutul sunt stocate unul lângă altul. Când adresa se potrivește, conținutul corespunzător este preluat din memoria cache.

Matrice asociativă hardware

Spre deosebire de memoria standard a computerului, memoria cu acces aleatoriu (RAM), în care utilizatorul furnizează o adresă de memorie și RAM returnează cuvântul de date stocat la acea adresă, o CAM este concepută astfel încât utilizatorul să furnizeze un cuvânt de date și CAM să caute întreaga memorie pentru a vedea dacă cuvântul de date este stocat oriunde în el. Dacă este găsit cuvântul de date, CAM returnează o listă cu una sau mai multe adrese de stocare unde a fost găsit cuvântul. Astfel, o CAM este întruchiparea hardware a ceea ce în termeni software ar fi numit o matrice asociativă .

Standarde

O definiție majoră a interfeței pentru CAM-uri și alte motoare de căutare a rețelei a fost specificată într-un acord de interoperabilitate numit Interfață Look-Aside (LA-1 și LA-1B) dezvoltat de Forumul de procesare a rețelei . Numeroase dispozitive conforme cu acordul de interoperabilitate au fost produse de Integrated Device Technology , Cypress Semiconductor , IBM , Broadcom și altele. La 11 decembrie 2007, OIF a publicat acordul de interfață serial lookaside (SLA).

Implementări semiconductoare

Celulă CAM binară CMOS formată dintr-o celulă SRAM 6T plus 4 tranzistori de comparație. Când datele de pe liniile de căutare (SL) diferă de datele stocate în celulă prin liniile de biți (BL), linia de potrivire (ML) va fi trasă jos pentru a indica o nepotrivire. Dacă niciuna dintre celulele de pe o linie de potrivire nu indică un bit nepotrivit, linia de potrivire va rămâne ridicată la nivelul de preîncărcare pentru a indica o potrivire de cuvânt. Ambele linii de căutare pot fi ținute la logica „0” ca o condiție de căutare indiferentă. Liniile de căutare și liniile de biți pot fi îmbinate într-o singură pereche de linii de date.

CAM este mult mai rapid decât memoria RAM în aplicațiile de căutare a datelor. Cu toate acestea, CAM prezintă dezavantaje de cost. Spre deosebire de un cip RAM , care are celule de stocare simple, fiecare bit de memorie individual într-un CAM complet paralel trebuie să aibă propriul său circuit de comparație asociat pentru a detecta o potrivire între bitul stocat și bitul de intrare. În plus, ieșirile de potrivire din fiecare celulă din cuvântul de date trebuie combinate pentru a produce un semnal complet de potrivire a cuvântului de date. Circuitul suplimentar crește dimensiunea fizică și costul de fabricație al cipului CAM. Circuitul suplimentar crește, de asemenea, disiparea puterii, deoarece fiecare circuit de comparație este activ la fiecare ciclu de ceas. În consecință, CAM este utilizat numai în aplicații specializate în care viteza de căutare nu poate fi realizată folosind o metodă mai puțin costisitoare. O implementare timpurie de succes a fost un IC și un sistem de procesare asociativă cu scop general.

La începutul anilor 2000, mai multe companii de semiconductori, inclusiv Cypress , IDT , Netlogic , Sibercore și MOSAID, au introdus produse CAM care vizează aplicații de rețea. Aceste produse au fost etichetate motoare de căutare în rețea (NSE), acceleratoare de căutare în rețea (NSA) și procesoare bazate pe cunoștințe (KBP), dar erau în esență CAM cu interfețe specializate și caracteristici optimizate pentru rețea. În prezent, Broadcom oferă mai multe familii de KBP.

Implementări alternative

Pentru a obține un echilibru diferit între viteză, dimensiunea memoriei și cost, unele implementări imită funcția CAM utilizând căutarea standard în arbore sau modele de hash în hardware, folosind trucuri hardware cum ar fi replicarea sau canalizarea pentru a accelera performanța eficientă. Aceste modele sunt adesea folosite în routere . Algoritmul Lulea este o implementare eficientă pentru cea mai lungă corespondență între căutări prefix este necesar în tabelele de rutare pe internet.

CAM ternare

Celulă CAM ternară CMOS formată din două celule SRAM 6T plus 4 tranzistori de comparație. În mod normal, nivelurile logice opuse, fie '0' și '1' sau '1' și '0' vor fi stocate în cele două celule. Pentru o condiție de nepăsare, „0” va fi stocat în ambele celule, astfel încât linia de potrivire ML să nu fie trasă la o combinație de date despre linia de căutare (SL).

CAM-ul binar este cel mai simplu tip de CAM și folosește cuvinte de căutare a datelor constând în întregime din 1s și 0s . CAM ternar ( TCAM ) permite o a treia stare de potrivire a lui X sau nu le pasă de unul sau mai mulți biți în cuvântul stocat, adăugând astfel flexibilitate căutării. De exemplu, un cuvânt stocat de „10XX0” într-o CAM ternară se va potrivi cu oricare dintre cele patru cuvinte de căutare „10000”, „10010”, „10100” sau „10110”. Flexibilitatea de căutare adăugată are un cost suplimentar față de CAM-ul binar, deoarece celula de memorie internă trebuie să codeze acum trei stări posibile în loc de cele două pentru CAM-ul binar. Această stare suplimentară este de obicei implementată prin adăugarea unui bit de mască (bitul „care” sau „nu îmi pasă”) la fiecare celulă de memorie.

Exemple de aplicații

Memoria adresabilă conținutului este adesea utilizată în dispozitivele de rețea de computer . De exemplu, atunci când un comutator de rețea primește un cadru de date de la unul dintre porturile sale, acesta actualizează un tabel intern cu adresa MAC sursă a cadrului și portul pe care a fost primit. Apoi caută adresa MAC de destinație în tabel pentru a determina la ce port trebuie să fie redirecționat cadrul și îl trimite pe acel port. Tabelul de adrese MAC este de obicei implementat cu o CAM binară, astfel încât portul de destinație poate fi găsit foarte repede, reducând latența comutatorului.

CAM-urile ternare sunt adesea folosite în routerele de rețea , unde fiecare adresă are două părți: prefixul rețelei , care poate varia ca dimensiune în funcție de configurația subrețelei și adresa gazdă, care ocupă biții rămași. Fiecare subrețea are o mască de rețea care specifică ce biți ai adresei sunt prefixul rețelei și care biți sunt adresa gazdă. Rutarea se face consultând un tabel de rutare menținut de router care conține fiecare prefix de rețea de destinație cunoscut, masca de rețea asociată și informațiile necesare pentru a direcționa pachetele către destinația respectivă. În implementările software, routerul compară adresa de destinație a pachetului care urmează să fie rutat cu fiecare intrare din tabelul de rutare, efectuând un bit și cu masca de rețea și comparând-o cu prefixul de rețea. Dacă sunt egale, informațiile de rutare corespunzătoare sunt utilizate pentru a redirecționa pachetul. Utilizarea unei CAM ternare pentru tabelul de rutare face procesul de căutare foarte eficient. Adresele sunt stocate folosind nu le pasă de partea gazdă a adresei, astfel căutarea adresei de destinație în CAM recuperează imediat intrarea corectă de rutare; atât mascarea, cât și comparația sunt realizate de hardware-ul CAM. Acest lucru funcționează dacă (a) intrările sunt stocate în ordinea descrescătoare a lungimii măștii de rețea și (b) hardware-ul returnează doar prima intrare potrivită; astfel, se utilizează potrivirea cu cea mai lungă mască de rețea ( cea mai lungă potrivire de prefix ).

Alte aplicații CAM includ:

Vezi si

Referințe

Bibliografie

linkuri externe