Википедија

Konteksno-adresibilna memorija

Memorija kojom se može pristupiti pomoću podatka, dobila je naziv od eng. skraćenice Content-addressable memory (skraćeno CAM), je posebna vrsta računarske memorije koja se koristi u određenim aplikacijama za pretraživanje veoma visokim brzinama. Takođe je poznat kao asocijativna memorija i upoređuje ulazne podatke pretrage sa tabelom sačuvanih podataka i vraća adresu odgovarajućih podataka. [1]

Memorija kojom se pristupa pomoću podatka

Memorija kojom se pristupa pomoću podatka se često koristi u mrežnim uređajima gde ubrzava rad osnovnih informacija za prosleđivanje i tabele rutiranja . Ova vrsta asocijativne memorije se takođe koristi u keš memoriji. U asocijativnoj keš memoriji, adresa i podatak se čuvaju jedan pored drugog. Kada se adresa podudara, odgovarajući podatak se preuzima iz keš memorije.

Istorija uredi

Dadli Alen Bak (eng. Dudley Allen Buck) je 1955. godine izmislio koncept memorije koja se može adresirati na podatak. Bak je zaslužan za ideju o jedinici za prepoznavanje . [2]

Hardverski asocijativni niz uredi

Za razliku od standardne računarske memorije, memorije sa slučajnim pristupom (eng. random-access memory, skraćno RAM), u kojoj korisnik daje memorijsku adresu, a RAM vraća podatak uskladišten na toj adresi, CAM je dizajniran tako da korisnik daje podatak, a CAM pretražuje njenu celu memoriju da vidite da li je taj podatak uskladišten negde u memoriji. Ako je zadati podatak pronađen, CAM vraća listu jedne ili više memorijskih adresa na kojima je podatak pronađen. Dakle, CAM je hardverska ideja onoga što bi se u softverskom smislu nazvalo asocijativnim nizom .

Sličan koncept se može naći u jedinici za prepoznavanje podataka, koju je predložio Dadli Alen Bak (eng. Dudley Allen Buck) 1955. [3]

Standardi uredi

Glavna definicija interfejsa za CAM i druge mrežne pretraživače navedena je u sporazumu o kompatiblinosti pod nazivom Look-Aside Interface (LA-1 i LA-1B) koji je razvio Network Processing Forum . [4] Brojne uređaje koji su u skladu sa sporazumom o kompatiblinosti proizvedeni su Integrated Device Technology, Cypress Semiconductor, IBM, Broadcom i drugih kompanija. OIF je 11. decembra 2007. objavio ugovor o interfejsu za serijski pogled sa strane (eng. serial lookaside - SLA).[traži se izvor]

Poluprovodničke implementacije uredi

 
CMOS binarna CAM ćelija koja se sastoji od 6T SRAM ćelije plus 4 uporedna tranzistora. Kada se podaci na linijama za pretragu (eng. search lines - SL) razlikuju od podataka uskladištenih u ćeliji kroz bitne linije (eng. bit lines - BL), linija podudaranja (eng. match line - ML) će biti povučena na masu da bi ukazala na neusklađenost. Ako nijedna ćelija na liniji podudaranja ne ukazuje na neusklađeni bit, linija podudaranja će ostati visoko na nivou napona napajanja da bi označila podudaranje reči. Obe linije za pretragu mogu da se drže na logičkoj '0' kao uslov pretraživanja koji nije bitan. Linije za pretragu i bitne linije mogu se spojiti u jedan par linija podataka.

CAM je mnogo brži od RAM-a u aplikacijama za pretraživanje podataka. Međutim, CAM ima nedostataka u pogledu troškova. Troškovi su određeni brojem tranzistora koji su potrebni da bi se napravilo integrisano kolo. Za razliku od RAM čipa, koji ima jednostavne ćelije za skladištenje, svaki pojedinačni memorijski bit u potpuno paralelnom CAM-u mora imati sopstveno povezano kolo za poređenje da bi se otkrilo podudaranje između uskladištenog i ulaznog bita. Pored toga, rezultati podudaranja iz svake ćelije u reči podataka moraju da se kombinuju da bi se dobio potpun signal podudaranja podataka. Dodatna kola povećavaju fizičku veličinu i troškove proizvodnje CAM čipa. Dodatna kola takođe povećavaju potrošnju električne energije pošto je svako kolo za poređenje aktivno u svakom ciklusu takta. Shodno tome, CAM se koristi samo u specijalizovanim aplikacijama gde se brzina pretraživanja ne može postići korišćenjem jeftinijih čipova. Jedna uspešna rana implementacija bila je General Purpose Associative Processor IC and System. [5]

Početkom 2000-ih nekoliko poluprovodničkih kompanija, uključujući Cypress, IDT, Netlogic, Sibercore, [6] i MOSAID, predstavilo je CAM proizvode namenjene mrežnim aplikacijama. Ovi proizvodi su bili označeni kao mrežni pretraživači (eng. Network Search Engines - NSE), akceleratori mrežnog pretraživanja (eng. Network Search Accelerators - NSA) i procesori zasnovani na znanju (eng. Knowledge-based Processors - KBP), ali su u suštini bili CAM sa specijalizovanim interfejsima i funkcijama optimizovanim za umrežavanje. Trenutno Broadcom nudi nekoliko KBP proizvoda. [7]

Alternativne implementacije uredi

Da bi se postigla drugačija ravnoteža između brzine, veličine memorije i cene, neke implementacije oponašaju funkciju CAM-a koristeći standardnu pretragu stabla ili heširanje dizajna u hardveru, koristeći hardverske trikove kao što su kopiranje podataka ili cevovod (eng. pipelining) da bi se ubrzale efektivne performanse. Ovi dizajni se često koriste u ruterima .[traži se izvor] Lulea-ov algoritam (eng. The Lulea algorithm) je efikasna implementacija za najduže pretrage, gde je potrebno podutaranje prefiksa, kao što se zahteva u tabelama rutiranja na internetu.

Ternarni CAM uredi

 
CMOS ternarna CAM ćelija koja se sastoji od dva 6T SRAM ćelije plus 4 uporedna tranzistora. Normalno suprotni logički nivoi, '0' i '1' ili '1' i '0' biće uskladišteni u dve ćelije. Za „nebriga“ uslov „0“ će biti sačuvan u obe ćelije tako da linija podudaranja (eng. match line - ML) neće biti povučena nisko za bilo koju kombinaciju podataka linije za pretragu (eng. search line - SL).

Binarni CAM je najjednostavniji tip CAM-a i koristi reči za pretragu podataka koje se u potpunosti sastoje od 1 i 0 . Ternarni CAM (skraćeno TCAM) [8] dozvoljava nepožnato stanje podudaranja X ili ne vodi računa o jednom ili više bitova u sačuvanom podatku, dodajući tako fleksibilnost pretrazi. Na primer, sačuvana reč „10XX0“ u ternarnom CAM-u će odgovarati bilo kojoj od četiri reči za pretragu „10000“, „10010“, „10100“ ili „10110“. Dodatna fleksibilnost pretraživanja dolazi uz dodatnu cenu u odnosu na binarni CAM, jer interna memorijska ćelija sada treba da kodira tri moguća stanja umesto dva za binarni CAM. Ovo dodatno stanje se obično implementira dodavanjem bita maske (bit „briga“ ili „nebriga“) svakoj memorijskoj ćeliji.

Primeri aplikacija uredi

Memorija koja se može adresirati na sadržaj se često koristi u mrežnim uređajima . Na primer, kada mrežni prekidač primi podatak sa jednog od svojih portova, on ažurira internu tabelu sa izvornom MAC adresom okvira (eng. frame) i portom na koji je primljen. Zatim traži odredišnu MAC adresu u tabeli da odredi na koji port okvir (eng. frame) treba da bude prosleđen i šalje ga na taj port. Tabela MAC adresa se obično implementira sa binarnim CAM-om tako da se odredišni port može pronaći veoma brzo, smanjujući kašnjenje koje ima sam prekidač (eng. switch).

TCAM se često koriste u mrežnim ruterima, gde svaka adresa ima dva dela: mrežni prefiks, koji može da varira u veličini u zavisnosti od konfiguracije podmreže, i adresu domaćina (eng. Host), koja zauzima preostale bitove. Svaka podmreža ima mrežnu masku koja određuje koji bitovi adrese su mrežni prefiks, a koji bitovi adrese domaćina. Rutiranje se izvršava pomoću tabele rutiranja koju održava ruter i koja sadrži svaki poznati mrežni prefiks odredišta, pridruženu mrežnu masku i informacije potrebne za usmeravanje paketa do tog odredišta. U jednostavnoj softverskoj implementaciji, ruter upoređuje odredišnu adresu paketa koji treba da se rutira sa svakim unosom u tabeli rutiranja, izvodeći konjunkcijau sa mrežnom maskom i upoređujući ga sa mrežnim prefiksom. Ako su jednaki, odgovarajuće informacije o rutiranju se koriste za prosleđivanje paketa. Korišćenje ternarnog CAM-a za tabelu rutiranja čini proces traženja veoma efikasnim. Adrese se čuvaju pomoću nebriga za host deo adrese, tako da traženje odredišne adrese u CAM-u odmah preuzima ispravan unos za rutiranje; i maskiranje i poređenje vrši CAM hardver. Ovo funkcioniše ako:

  • unosi se čuvaju po redukciji dužine mrežne maske
  • hardver vraća samo prvi odgovarajući unos; stoga se koristi podudaranje sa najdužom mrežnom maskom ( podudaranje najdužeg prefiksa ). [9]

Ostale CAM aplikacije uključuju:

Reference uredi

  1. ^ „K. Pagiamtzis* and A. Sheikholeslami, Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, pp. 712-727, March 2006.” (PDF). Arhivirano (PDF) iz originala 2007-03-15. g. 
  2. ^ TRW Computer Division. (1963). First interim report on optimum utilization of computers and computing techniques in shipboard weapons control systems. (BuWeps-Project RM1004 M88-3U1). Alexandria, Virginia:Defence Documentation Center for Scientific and Technical Information.
  3. ^ TRW Computer Division Arhivirano avgust 5, 2011 na sajtu Wayback Machine, 1963, p. 17.
  4. ^ Look-Aside (LA-1B) Interface Implementation Agreement (PDF), 2004-08-04 
  5. ^ Stormon, C. D.; Troullinos, N. B.; Saleh, E. M.; Chavan, A. V.; Brule, M. R.; Oldfield, J. V. (decembar 1992). „C. Stormon, N. Troullinos, E. Saleh, A. Chavan, M. Brule and J. Oldfield, "A general-purpose CMOS associative processor IC and system", IEEE Micro, vol. 12, no. 6, pp. 68-78, December 1992.”. IEEE Micro. 12 (6): 68—78. doi:10.1109/40.180249. 
  6. ^ „Sibercore Technologies - Silicon Solutions for Cyberspace”. Arhivirano iz originala 2003-04-19. g. 
  7. ^ „16nm Heterogeneous Knowledge-Based Processors (KBPs)”. Arhivirano iz originala 2017-05-19. g. 
  8. ^ Hucaby, David (2004). CCNP BCMSN Exam Certification Guide: CCNP Self-study. ISBN 9781587200779. 
  9. ^ Varghese, George, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, 2005
  10. ^ Smith, Alan Jay (septembar 1982). „Cache Memories” (PDF). Computing Surveys. 14 (3): 473—530. doi:10.1145/356887.356892. Arhivirano iz originala (PDF) 03. 04. 2022. g. Pristupljeno 3. 4. 2022. „The TLB is a small associative memory which maps virtual to real addresses.” 
  11. ^ Hinton, Geoffrey E. (1984). „Distributed representations”. Arhivirano iz originala 02. 05. 2016. g. Pristupljeno 08. 02. 2023. 

Bibliografija uredi

Spoljašnje veze uredi

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Контексно-адресибилна_меморија&oldid=26903387”