Paměť adresovatelná obsahu - Content-addressable memory

Paměť adresovatelná obsahu (VAČKA) je speciální typ paměť počítače používá se v určitých aplikacích pro velmi rychlé vyhledávání. Je také známý jako asociativní paměť nebo asociativní úložiště a porovná vstupní vyhledávací data s tabulkou uložených dat a vrátí adresu odpovídajících dat.[1]

Jednotku pro rozpoznávání datových slov navrhl Dudley Allen Buck v roce 1955.[2]

CAM se často používá v síťová zařízení kde to zrychluje předávací informační základna a směrovací tabulka operace.

Hardwarové asociativní pole

Na rozdíl od standardní paměti počítače paměť s náhodným přístupem (RAM), ve kterém uživatel zadá adresu paměti a RAM vrátí datové slovo uložené na této adrese, CAM je navržen tak, že uživatel dodá datové slovo a CAM prohledá celou jeho paměť, aby zjistil, zda je toto datové slovo uloženo kdekoli v něm. Pokud je datové slovo nalezeno, modul CAM vrátí seznam jedné nebo více adres úložiště, kde bylo slovo nalezeno. CAM je tedy hardwarovým ztělesněním toho, co by se po softwarové stránce dalo nazvat asociativní pole.[3]

Standardy

Hlavní definice rozhraní pro CAM a další síťové vyhledávače byl specifikován v dohodě o interoperabilitě zvané Rozhraní Look-Aside (LA-1 a LA-1B) vyvinuté Fórum pro zpracování sítě. Mnoho zařízení vyhovujících dohodě o interoperabilitě bylo vyrobeno společností Technologie integrovaných zařízení, Cypress Semiconductor, IBM, Broadcom a další. Dne 11. prosince 2007 zveřejnil OIF dohodu o rozhraní Serial Lookaside (SLA).[Citace je zapotřebí ]

Polovodičové implementace

Protože CAM je navržen tak, aby prohledával celou svou paměť v jediné operaci, je mnohem rychlejší než RAM prakticky ve všech vyhledávacích aplikacích. CAM však má nákladové nevýhody. Na rozdíl od RAM čip, který má jednoduché paměťové buňky, každá jednotlivá paměť bit v plně paralelním CAM musí mít svůj vlastní přidružený srovnávací obvod, aby detekoval shodu mezi uloženým bitem a vstupním bitem. Navíc musí být kombinovány výstupy shody z každé buňky v datovém slově, aby se získal úplný signál shody datového slova. Dodatečné obvody zvyšují fyzickou velikost a výrobní náklady CAM čipu. Zvláštní obvody také zvyšují ztrátový výkon, protože každý srovnávací obvod je aktivní v každém taktu. CAM se proto používá pouze ve specializovaných aplikacích, kde nelze dosáhnout rychlosti vyhledávání pomocí méně nákladné metody. Jednou z úspěšných časných implementací byl IC a systém generálního sdruženého procesoru.[4]

Alternativní implementace

Aby se dosáhlo jiné rovnováhy mezi rychlostí, velikostí paměti a cenou, některé implementace emulují funkci CAM pomocí standardního vyhledávání stromů nebo hašovacích návrhů v hardwaru, pomocí hardwarových triků, jako je replikace nebo pipeline, k urychlení efektivního výkonu. Tyto vzory se často používají v směrovače.[Citace je zapotřebí ]

Alternativní přístup k implementaci je založen na překrývajících se kódových slovech nebo polních kódovaných slovech, která se používají pro efektivnější databázové operace, načítání informací a logické programování, s hardwarovými implementacemi založenými na technologii RAM i na discích s monitorováním hlavy.[5][6]

Ternární CAM

Binární CAM je nejjednodušší typ CAM, který používá slova pro vyhledávání dat skládající se výhradně z 1 s a 0 s. Ternární CAM (TCAM)[7] umožňuje a třetí shodný stav „X“ nebo „nestarám se“ o jeden nebo více bitů v uloženém datovém slově, což přidává flexibilitu vyhledávání. Například ternární modul CAM může mít uložené slovo „10XX0“, které bude odpovídat kterémukoli ze čtyř hledaných slov „10 000“, „10010“, „10100“ nebo „10110“. Přidaná flexibilita vyhledávání přináší za binární CAM dodatečné náklady, protože buňka vnitřní paměti musí nyní kódovat tři možné stavy místo dvou pro binární CAM. Tento dodatečný stav je obvykle implementován přidáním bitové masky (bit „péče“ nebo „nezajímá mě“) do každé paměťové buňky.

Ukázkové aplikace

Paměť adresovatelná obsahu se často používá v počítačová síťová zařízení. Například když a síťový přepínač přijímá a datový rámec z jednoho ze svých portů aktualizuje interní tabulku se zdrojem rámce MAC adresa a port, na kterém byl přijat. Poté vyhledá cílovou adresu MAC v tabulce, aby určil, na jaký port je třeba rámec předat, a odešle jej na tento port. Tabulka MAC adres je obvykle implementována s binárním CAM, takže cílový port lze najít velmi rychle, což snižuje latenci přepínače.

V síti se často používají ternární CAM směrovače, kde má každá adresa dvě části: předpona sítě, které se mohou lišit velikostí v závislosti na podsíť konfigurace a adresa hostitele, která zabírá zbývající bity. Každá podsíť má síťovou masku, která určuje, které bity adresy jsou předponou sítě a které bity jsou hostitelskou adresou. Směrování se provádí nahlédnutím do směrovací tabulky udržované routerem, která obsahuje každou známou předponu cílové sítě, přidruženou masku sítě a informace potřebné k směrování paketů do tohoto cíle. Bez CAM směrovač porovnává cílovou adresu paketu, který má být směrován, s každou položkou ve směrovací tabulce a provádí bitové AND s maskou sítě a její porovnání s předponou sítě. Pokud jsou stejné, použijí se odpovídající směrovací informace k předání paketu. Použití ternární CAM pro směrovací tabulku činí vyhledávací proces velmi efektivním. Adresy se ukládají pomocí „nestarám se“ o hostitelskou část adresy, takže vyhledáním cílové adresy v modulu CAM se okamžitě načte správný směrovací záznam; maskování i porovnání se provádí pomocí hardwaru CAM. To funguje, pokud (a) jsou položky uloženy v pořadí podle zmenšení délky masky sítě a (b) hardware vrací pouze první odpovídající položku; tedy shoda s nejdelší maskou sítě (nejdelší prefixová shoda ) se používá.[8]

Mezi další aplikace CAM patří:

Viz také

Reference

  1. ^ Pagiamtzis a Sheikholeslami (2006), str. 712–713
  2. ^ Počítačová divize TRW Archivováno 5. srpna 2011 v Wayback Machine, 1963, s. 17.
  3. ^ Hannum a kol. (2004)
  4. ^ Storman a kol. (1992)
  5. ^ Wise, Michael J; Powers, David M. W. (1984). "Indexování klauzulí prologu přes překrývající se kódová slova a pole kódovaná slova". Mezinárodní symposium o logickém programování: 203–210.
  6. ^ Colomb, Robert M (1991). "Vylepšení sjednocení v PROLOGU prostřednictvím indexování klauzule". Journal of Logic Programming. 1 (10): 23–44. doi:10.1016/0743-1066(91)90004-9.
  7. ^ Hucaby, David (2004). Průvodce certifikací CCNP BCMSN: Samostudium CCNP. ISBN  9781587200779.
  8. ^ Varghese, Georgi, Network Algorithmics: Interdisciplinary approach to designing Fast Networked Devices, Morgan Kaufmann, 2005
  9. ^ Hinton, Geoffrey E. (1984). „Distribuovaná zastoupení“.

Bibliografie

externí odkazy