Asociativní paměť

Asociativní paměť (AP) neboli asociativní paměťové zařízení (AMU) je speciální typ počítačové paměti používané ve velmi rychlých vyhledávacích aplikacích. Také známý jako obsahově adresovatelná paměť, asociativní úložiště, obsahově adresovatelná paměť nebo asociativní pole , ačkoli druhý termín se v programování běžně používá k označení datové struktury (Hannum et al., 2004).

Hardwarové asociativní pole

Na rozdíl od konvenční paměti stroje (paměť s náhodným přístupem nebo RAM), ve které uživatel specifikuje adresu paměti a RAM vrací datové slovo uložené na této adrese, je UA navržen tak, že uživatel specifikuje datové slovo a UA jej hledá. abyste zjistili, zda je někde uložen v paměti. Pokud je nalezeno datové slovo, UA vrátí seznam jedné nebo více adres úložiště, kde bylo slovo nalezeno (a na některých architekturách také vrátí samotné datové slovo nebo další související části dat). AP je tedy hardwarová implementace toho, co by se z hlediska programování nazývalo asociativní pole.

Průmyslové standardy adresovatelný obsah paměti

Definice základního rozhraní pro UA a další Network Search Elements (NSE) byla specifikována v dohodě o interoperabilitě nazvané Look-Aside Interface ( LA-1 a LA-1B ), kterou vyvinulo Network Processing Forum, které bylo později sloučeny do Optical Internetworking Forum (OIF). Řada zařízení byla vyrobena společnostmi Integrated Device Technology, Cypress Semiconductor, IBM, Netlogic Micro Systems a dalšími v rámci těchto dohod LA. Dne 11. prosince 2007 zveřejnil OIF smlouvu o rozhraní Serial Lookaside ( SLA ).

Implementace na polovodičích

Protože je AP navržen tak, aby prohledával celou paměť v jedné operaci, je to mnohem rychlejší než prohledávání RAM prakticky ve všech vyhledávacích aplikacích. Nevýhodou jsou však vyšší náklady na AP. Na rozdíl od čipu RAM, který má jednoduché úložiště, musí mít každý jednotlivý bit paměti v plně paralelním AP připojen svůj vlastní porovnávací obvod, aby se zjistila shoda mezi uloženým bitem a vstupním bitem. Kromě toho musí být výstupy porovnání z každé buňky v datovém slově kombinovány, aby se získal úplný výsledek porovnání datového slova. Další obvody zvětšují fyzickou velikost AP čipu, což zvyšuje výrobní náklady. Další obvody také zvyšují ztrátový výkon, protože všechny srovnávací obvody jsou aktivní v každém hodinovém cyklu. V důsledku toho se AM používá pouze ve specializovaných aplikacích, kde nelze dosáhnout rychlosti vyhledávání jinými, méně nákladnými metodami.

Alternativní implementace

Aby se dosáhlo různé rovnováhy mezi rychlostí, velikostí paměti a cenou, některé implementace emulují funkce AP pomocí standardního stromového vyhledávání nebo hardwarově implementovaných hašovacích algoritmů, a také pomocí hardwarových triků, jako je replikace a zřetězení, pro urychlení efektivního provozu. Tyto konstrukce se často používají ve směrovačích.

Ternární asociativní paměť

Binární AA je nejjednodušším typem asociativní paměti, která používá slova pro vyhledávání dat složená výhradně z 1s a 0s. V ternární paměti s adresovatelným obsahem (TCAM [1] ) je přidána třetí hodnota pro porovnání "X" nebo "don't care" pro jeden nebo více bitů v uloženém datovém slově, což přidává další flexibilitu vyhledávání.

Například ternární UA může uložit slovo „10XX0“, které by odpovídalo kterémukoli ze čtyř hledaných slov „10000“, „10010“, „10100“ nebo „10110“. Přidání flexibility do vyhledávání je za cenu zvýšené složitosti paměti, protože vnitřní buňky nyní musí kódovat tři možné stavy namísto dvou. Tento dodatečný stav je obvykle implementován přidáním "důležitého" ("důležitého"/"nedůležitého") bitu masky do každého paměťového místa.

Příklady aplikací

Obsahově adresovatelná paměť se často používá v zařízeních počítačových sítí. Když například síťový přepínač přijme datový rámec na jednom ze svých portů, aktualizuje interní tabulku s původem MAC adresy rámce a portem, na kterém byl přijat. Poté vyhledá cílovou MAC adresu v tabulce, aby určil, na který port má být rámec odeslán, a odešle jej na tento port. Tabulka MAC adres je obvykle implementována na binárním AP, takže cílový port lze najít velmi rychle, což snižuje latenci přepínače.

Ternární AP se často používají v těch síťových směrovačích, kde má každá adresa dvě části: (1) síťovou adresu, jejíž velikost se může měnit v závislosti na konfiguraci podsítě, a (2) adresu hostitele, která zabírá zbývající bity. Každá podsíť má masku sítě, která určuje, které bity jsou síťovou adresou a které bity jsou adresou hostitele. Směrování se provádí kontrolou podle směrovací tabulky spravované směrovačem. Obsahuje všechny známé cílové síťové adresy, jejich přidruženou masku sítě a informace potřebné pro pakety směrované do tohoto cíle. Směrovač implementovaný bez UA porovnává cílovou adresu paketu, který má být rozdělen, s každým záznamem ve směrovací tabulce, dělá logické AND se síťovou maskou a porovnává výsledky se síťovou adresou. Pokud jsou stejné, použije se k odeslání paketu odpovídající informace o směru. Použití ternárního UA pro směrovací tabulku činí proces vyhledávání velmi efektivním. Adresy jsou uloženy pomocí bitu don't care v části adresy hostitele, takže vyhledání cílové adresy v UA okamžitě získá správný záznam ve směrovací tabulce; obě operace - nanesení masky a porovnání - provádí hardware AP.

Mezi další aplikace AP patří

Viz také

Poznámky

  1. ↑ Průvodce certifikací zkoušky CCNP BCMSN: Samostudium CCNP - David Hucaby - Knihy Google . Získáno 7. dubna 2015. Archivováno z originálu 4. března 2016.

Literatura

V angličtině

Odkazy

V angličtině:

  Přejděte na položku Wikidata  Slovníky a encyklopedie
V bibliografických katalozích