Asociativní počítačová paměť. asociativní paměť. Rozvoj asociativní paměti. Obecné informace a klasifikace paměťových zařízení

Způsoby, jak organizovat paměť

Funkčně se paměť jakéhokoli typu vždy skládá z úložného pole, které uchovává informace, a pomocných, velmi složitých bloků, které slouží k vyhledávání v poli, zápisu a čtení (a v případě potřeby regeneraci).

Úložné pole (MS) sestává z množství identických úložných prvků (SE). Všechny SE jsou organizovány do buněk, z nichž každá je navržena pro uložení jednotky informace ve formě binárního kódu, jehož počet bitů je určen šířkou vzorku. Způsob organizace paměti závisí na metodách umístění a vyhledávání informací v SM. Na tomto základě se rozlišuje adresní, asociativní a zásobníková paměť.

PAMĚŤ ADRES

V paměti s adresním uspořádáním je umístění a vyhledávání informací v SM založeno na použití adresy úložiště informační jednotky, kterou budeme pro stručnost dále nazývat slovo. Adresa je číslo buňky SM, ve které se toto slovo nachází. Při zápisu (čtení) slova v SM musí příkaz spouštějící tuto operaci udávat adresu (číslo) buňky, do které je potřeba zapisovat (číst).

Na Obr. 5.2 ukazuje zobecněnou strukturu adresové paměti.

Cyklus přístupu do paměti je inicializován signálem "Přístup" přicházejícím do TCU. Obecná část přístupového cyklu zahrnuje příjem v RgA z adresové sběrnice (SHA) adresy adresy a příjem v TCU řídicího signálu "Operation" udávající typ požadované operace (čtení nebo zápis).

Čtení. BAW dešifruje adresu a vyšle signál, který zvýrazní buňku 3M určenou adresou. V obecném případě může BAW také odesílat signály do přidělené paměťové buňky, která nastavuje buňky GE pro zápis nebo čtení. Poté je slovo zapsané v buňce přečteno zesilovači BUS a přeneseno do RGI. Dále se v paměti s destruktivním čtením informace regenerují zápisem slova z RgI přes BUZ do stejné SM buňky. Operace čtení je dokončena vydáním slova z RGI do výstupní informační sběrnice SHI out.

Záznam. Kromě výše uvedené obecné části přístupového cyklu je psané slovo přijímáno ze vstupní sběrnice SHI do RGI. Samotný záznam se obecně skládá ze dvou operací – vymazání buňky a samotného záznamu. K tomu BAS nejprve vybere a vymaže buňku určenou adresou v PrA. Vymazání SM buňky (resetování) lze provést různými způsoby. Zejména v paměti s destruktivním čtením může být vymazání provedeno signálem pro přečtení slova v buňce, když je BUS blokována (takže informace nevstoupí do RGI). Dále se do vybrané buňky zapíše nové slovo.

Potřeba operace čištění buňky před zápisem, stejně jako operace regenerace informace při čtení, je dána typem použitých SG, metodami řízení, vlastnostmi elektronické struktury paměti LSI, a proto mohou tyto operace chybí v polovodičových pamětech.

TCU generuje potřebné sekvence řídicích signálů, které iniciují činnost jednotlivých paměťových uzlů. Je třeba mít na paměti, že TCU musí být velmi složité zařízení (jakýsi řídicí řadič s vlastní cache pamětí), které dává paměti LSI jako celku speciální spotřebitelské vlastnosti, jako je multiport, zřetězený výstup informací atd. .

ASOCIATIVNÍ PAMĚŤ

V tomto typu paměti se informace nehledají podle adresy, ale podle jejího obsahu. Obsahem informace se v tomto případě obvykle rozumí nikoli sémantická zátěž slova uloženého v paměťové buňce, ale jako obsah GE paměťové buňky, ᴛ.ᴇ. bitové složení zaznamenaného binárního slova. V tomto případě je asociativní dotaz (vlastnost) také binární kód s určitým bitovým složením. Vyhledávání pomocí asociativního znaku probíhá paralelně v čase pro všechny SM buňky a je to operace porovnávání obsahu bitů atributového registru s obsahem odpovídajících bitů paměťových buněk. Pro organizaci takového vyhledávání jsou všechny EP SM vybaveny jednobitovými procesory, proto je v některých případech tento typ paměti považován za víceprocesorový systém.

Velká plně asociativní paměť je velmi drahé zařízení, proto, aby se snížila její cena, je počet jednobitových procesorů snížen na jeden na paměťovou buňku. V tomto případě se porovnání asociativního dotazu s obsahem paměťových buněk provádí postupně pro jednotlivé číslice, paralelně v čase pro všechny buňky SM.

Při velmi velkém množství paměti na určité třídy problémů asociativní vyhledávání výrazně urychluje zpracování dat a snižuje pravděpodobnost selhání v počítači. Asociativní paměti s bloky odpovídajících kombinačních obvodů zároveň umožňují provádět v paměti poměrně složité logické operace: hledání maximálního nebo minimálního čísla v poli, hledání slov uzavřených v určitých hranicích, třídění pole atd.

Je třeba poznamenat, že asociativní vyhledávání může být také implementováno v počítači s konvenční adresovou pamětí, sekvenčním voláním slov zapsaných v paměťových buňkách do procesoru a jejich porovnáním s nějakou asociativní funkcí (šablonou). Zároveň s velkým množstvím paměti na to strávíme spoustu času. Při použití asociativní paměti je možné bez čtení slov z RAM do procesoru určit počet slov odpovídajících tomu či onomu asociativnímu dotazu v jednom volání. To umožňuje ve velkých databázích velmi rychle implementovat dotaz typu: kolik obyvatel kraje nepodalo přiznání k příjmu atd.

V některých specializovaných počítačích je OP nebo jeho část postavena tak, že umožňuje realizovat jak asociativní, tak cílené vyhledávání informací.

Zjednodušené blokové schéma asociativní paměti, ve které jsou všechny GE SM vybaveny jednobitovými procesory, je na Obr. 5.3.

Podívejme se nejprve na operaci s názvem kontrola asociace. Tato operace je společná pro operace čtení a zápisu a má také nezávislou hodnotu.

N-bitový asociativní požadavek, ᴛ.ᴇ, vstupuje do RGAP prostřednictvím vstupní informační sběrnice. číslice od 0 do n-1 jsou vyplněny. Současně kód vyhledávací masky zadá RgM, zatímco n-tý bit RgM je nastaven na 0. Asociativní vyhledávání se provádí pouze pro sadu bitů RgAP, které odpovídají 1 v RgM (nemaskované bity RgAP). Je důležité poznamenat, že pro slova, ve kterých se číslice v číslicích shodovaly s nezamaskovanými číslicemi PrAP, CS nastaví 1 na odpovídající číslice PrCv a 0 na zbývající číslice.

Kombinační schéma pro generování výsledku asociativní inverze FS tvoří alespoň tři signály ze slova vytvořeného v RgSv:

A 0 - nepřítomnost slov v SM, která splňují asociativní atribut;

A 1 - přítomnost jednoho takového slova;

A 2 - přítomnost více než jednoho slova.

Jsou možné i další operace s obsahem PgSv, například počítání jednotek, ᴛ.ᴇ. počítání slov v paměti, která splňují asociativní dotaz atd.

Tvorba obsahů RgSv a a 0, a 1, a 2 podle obsahů RgAP, RgM, ZM se obvykle nazývá operace řízení asociace.

Čtení. Nejprve je sdružení řízeno na základě RgAP.

A 0 = 1 - čtení je zrušeno z důvodu nedostatku požadovaných informací;

A 1 \u003d 1 - nalezené slovo je načteno do RGI, poté je vydáno na výstup SHI;

A 2 \u003d 1 - je přečteno slovo, které má například nejmenší číslo mezi buňkami označenými 1 v RgSv, po kterém je vydáno na výstup SHI.

Záznam. Nejprve je nalezena volná buňka (předpokládáme, že do obsazeného bitu volné buňky je zapsána 0). K tomu se provádí řízení asociace při PgAP=111...10 a PgM=000...01, ᴛ.ᴇ. N-tá číslice RgAP je nastavena na 0 a n-tá číslice RgM je nastavena na 1. V tomto případě je volná buňka označena 1 v RgSv. Pro záznam se vybere volná buňka, např. s nejmenším číslem. Obsahuje slovo přijaté od SHI v RGI.

Je třeba poznamenat, že toto schéma neukazuje bloky BUP, BUS, BUS, které jsou ve skutečných zařízeních. K vybudování asociativní paměti jsou zároveň zapotřebí úložné prvky, které lze číst bez zničení.

ZÁSOBNÍK PAMĚTI (OBCHOD)

Zásobníková paměť je stejně jako asociativní paměť neadresná. Zásobníková paměť musí být organizována jak v hardwaru, tak v běžném poli adresové paměti.

V případě hardwarové implementace tvoří zásobníkové paměťové buňky jednorozměrné pole, ve kterém jsou sousední buňky vzájemně spojeny bitovými řetězci přenosu slov (obr. 5.4). V tomto případě jsou možné dva typy zařízení (a, b), jejichž principy fungování jsou odlišné. Nejprve se podívejme na strukturu na obr. 5.4, ​​a.

Zápis nového slova přijatého z SHI in se provede do horní (nulové) buňky, zatímco všechna dříve zaznamenaná slova (včetně slova v buňce 0) se posunou dolů do sousedních buněk, jejichž čísla jsou o jednu větší. Čtení je možné pouze z horní (nulové) paměťové buňky. Hlavním režimem je ϶ᴛᴏ čtení s mazáním. Současně jsou všechna ostatní slova v paměti posunuta nahoru do sousedních buněk s nižšími čísly. V takové paměti je implementováno následující pravidlo: poslední dovnitř, první ven. Zásobníky tohoto typu se nazývají zásobníky LIFO (Last In - First Out).

V některých případech zásobníková paměťová zařízení také umožňují operaci prostého čtení slova z buňky 0 bez jeho vymazání a posunutí zbývajících slov. Při použití zásobníku k uložení inicializačních parametrů řadičů jakýchkoli počítačových zařízení je obvykle možné číst obsah libovolné buňky zásobníku, aniž by bylo nutné ji smazat, ᴛ.ᴇ. čtení obsahu nejen buňky 0.

Říká se, že první slovo vložené do zásobníku je umístěno na spodní část zásobníku. Říká se, že poslední slovo odeslané (v čase) do zásobníku je in horní část zásobníku. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, buňka N-1 je spodní část zásobníku a buňka 0 je horní část.

Hardwarový zásobník je obvykle opatřen čítačem zásobníku ChSt, který ukazuje celkový počet slov uložených v paměti (CHSt = 0 - zásobník je prázdný). Když je zásobník plný, zakáže další operace zápisu.

Zásobníkový princip organizace paměti lze implementovat nejen do zařízení speciálně určených k tomuto účelu. Zásobníkové uspořádání dat je také možné na konvenční adresové paměti s náhodným přístupem (softwarový zásobník). K uspořádání LIFO zásobníku je v tomto případě potřeba ještě jedna paměťová buňka (registr), ve které je vždy uložena adresa vrcholu zásobníku a která se běžně nazývá ukazatel zásobníku. Obvykle se jako ukazatel zásobníku používá jeden z interních registrů procesoru. Kromě toho je vyžadován vhodný software. Principy zásobníkové organizace dat na konvenční adresové paměti ilustruje schéma na Obr. 5.5.

Na rozdíl od hardwarového zásobníku se data umístěná na softwarovém zásobníku nepřesouvají, když se zapisuje nebo čte nové číslo. Každé nové slovo je zapsáno do paměti následující v pořadí, jehož adresa je obsažena v ukazateli zásobníku. Po napsání nového slova se ukazatel zásobníku zvýší o jedničku (viz obrázek 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, v softwarovém zásobníku se nepohybují data, ale horní část zásobníku. Když je slovo čteno ze zásobníku, proces se obrátí. Slovo je přečteno z umístění, jehož adresa je v ukazateli zásobníku, a poté se obsah ukazatele zásobníku sníží o jednu.

Pokud jsou slova nově načtená do zásobníku umístěna do paměťových buněk s postupně se zvyšujícími adresami, zásobník je volán Přímo. Pokud adresy postupně klesají, pak - vzhůru nohama. Ve většině případů se používá převrácený zásobník, což je způsobeno zvláštnostmi hardwarové implementace čítačů uvnitř procesoru.

Jak výhodná je tato forma organizace paměti? Při pohledu do budoucna lze poznamenat, že jakákoli instrukce prováděná v procesoru musí obecně obsahovat operační kód (COP), adresu prvního a druhého operandu a adresu výsledku. Pro úsporu paměti a snížení doby provádění strojové instrukce procesorem je žádoucí zkrátit délku instrukce. Limit pro toto snížení je délka neadresného příkazu ᴛ.ᴇ. jen COP. Právě tyto instrukce jsou možné se zásobníkovou organizací paměti, jelikož při správném uspořádání operandů na zásobníku je stačí postupně extrahovat a provádět s nimi příslušné operace.

Kromě výše popsané zásobníkové paměti typu LIFO používají počítače zásobníkové paměti jiného typu, které implementují pravidlo: první dovnitř - první ven. Stacky tohoto typu se nazývají FIFO (First In - First Out) stacky. Taková zásobníková paměť se široce používá pro organizování různých druhů front (příkazy, data, požadavky atd.). Zobecněná struktura hardwarového zásobníku typu FIFO je znázorněna na Obr. 5.4b.

Stejně jako v předchozím případě tvoří zásobníkové paměťové buňky jednorozměrné pole, ve kterém jsou sousední buňky vzájemně spojeny bitovými řetězci přenosu slov. Zadání nového slova přijatého od SHI in se provádí v horní (nulové) buňce, poté se okamžitě přesune dolů a zapíše se do poslední prázdné buňky. Pokud byl zásobník před zápisem prázdný, slovo okamžitě přejde do buňky s číslem N-1, ᴛ.ᴇ. na dno zásobníku. Čtení je možné pouze ze spodní buňky s číslem N-1 (spodní část zásobníku). Hlavním režimem je ϶ᴛᴏ čtení s mazáním. V tomto případě jsou všechna následující (zaznamenaná) slova posunuta dolů do sousedních buněk, jejichž čísla jsou o jedno více. Když je zásobník plný, čítač (CHST) zakáže další zápisy do zásobníku.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, na rozdíl od zásobníku LIFO se zásobník FIFO neposouvá spodní částí, ale horní částí. Slova zapsaná do zásobníku FIFO se postupně přesouvají shora dolů, odkud jsou čtena, protože jsou nesmírně důležitá, a rychlost zápisu a čtení je určována vnějšími řídicími signály a vzájemně nesouvisí.

Softwarová implementace zásobníku FIFO není v této části uvažována, protože se v praxi používá zřídka.

Způsoby organizace paměti - pojem a typy. Klasifikace a vlastnosti kategorie "Metody organizace paměti" 2017, 2018.

Úložné zařízení zpravidla obsahuje mnoho stejných úložných prvků, které tvoří úložné pole (SM). Pole je rozděleno na jednotlivé buňky; každý z nich je navržen pro uložení binárního kódu, jehož počet bitů je určen šířkou paměťového vzorku (zejména to může být jedno, polovina nebo několik strojových slov). Způsob, jakým je paměť organizována, závisí na metodách umístění a vyhledávání informací v poli úložiště. Na tomto základě se rozlišuje adresní, asociativní a zásobníková (store) paměť.

paměť adres. V paměti s organizací adres je umístění a vyhledávání informací v SM založeno na použití adresy úložiště slova (číslo, příkaz atd.), adresa je číslo buňky SM, ve které toto slovo je umístěn.

Při zápisu (nebo čtení) slova do SM musí příkaz spouštějící tuto operaci udávat adresu (číslo buňky), na které se záznam (čtení) provádí.

Typická struktura paměti adres zobrazená na Obr. 4.2 obsahuje pole úložiště N n-bitových buněk a jeho hardwarového rámce včetně registru adres RgA, mít k(k> log 2 N) bitů, registr informací RGI, blok načítání adresy BAS, jednotka čtecího zesilovače AUTOBUS, blok bitových zesilovačů-formátorů záznamových signálů BUZ a správu paměti BUP.

Obr.4.2.Struktura paměti adres.

Podle kódu adresy RgA BAV generuje signály v odpovídající paměťové buňce, které umožňují čtení nebo zápis slova v buňce.

Cyklus přístupu do paměti je zahájen příchodem BUP mimo signál Odvolání. Obecná část oběhového cyklu zahrnuje příjem v RgA s adresní sběrnice USA adresy odvolání a příjmu v BUP a dekódování řídícího signálu Úkon, indikující typ požadované operace (čtení nebo zápis).

Další při čtení BAS dešifruje adresu, odešle čtené signály do buňky určené adresou ZM, v tomto případě je kód slova zapsaný v buňce čten čtecími zesilovači AUTOBUS a převedeny do RGI. Poté v paměti s destruktivním čtením (při čtení jsou všechny úložné prvky buňky nastaveny do nulového stavu). informace se v buňce regenerují zápisem RGIčíst slovo. Operace čtení je dokončena vydáním slova z RGI na výstupní informační sběrnici SHIout.

Při zápisu je kromě provádění výše uvedené obecné části přístupového cyklu přijímáno zapisované slovo ze vstupní informační sběrnice SHIVx PROTI RGI. Samotný záznam se skládá ze dvou operací: vymazání buňky (resetování na 0) a samotného záznamu. Pro tohle BAS nejprve vybere a vymaže buňku určenou adresou v RgA. Zúčtování se provádí pomocí slov přečtených signálů v buňce, ale čtecích zesilovačů az AUTOBUS PROTI RGI informace nejsou přijímány. Pak k vyvoleným BAS z buňky je napsáno slovo RGI.

Ovládací blok BUP generuje potřebné sekvence řídicích signálů, které iniciují činnost jednotlivých paměťových uzlů. Řetězce přenosu řídicího signálu jsou na obr. 2 znázorněny tenkými čarami. 4.2.

asociativní paměť. V paměti tohoto typu se hledání potřebných informací neprovádí podle adresy, ale podle jejího obsahu (pomocí asociativní funkce). V tomto případě probíhá vyhledávání podle asociativního atributu (nebo postupně podle jednotlivých číslic tohoto atributu) paralelně v čase pro všechny buňky pole úložiště. Asociativní vyhledávání může v mnoha případech výrazně zjednodušit a zrychlit zpracování dat. Toho je dosaženo díky skutečnosti, že u tohoto typu paměti je operace čtení informací kombinována s prováděním řady logických operací.

Typická struktura asociativní paměti je znázorněna na Obr. 4.3. Úložné pole obsahuje N(P + 1) -bitové buňky. Obslužný n-tý bit slouží k indikaci obsazenosti buňky (0 - buňka je volná, 1 - slovo je zapsáno v buňce).

Na vstupní informační sběrnici SHIVx do rejstříku asociativního znaku RGAP v číslicích 0-a-1 vstoupí P- bitový asociativní dotaz a do registru masky RgM - kód vyhledávací masky s n-tou číslicí RgM nastavte na 0. Asociativní vyhledávání se provádí pouze pro sadu číslic RGAP, které „odpovídají 1 in RgM(odmaskované číslice RgAP). Pro slova, ve kterých se číslice v číslicích shodovaly s nezamaskovanými číslicemi RGAP, kombinační obvod KS nastaví 1 na odpovídající bity shodného registru RgSv a 0 pro zbytek bitů. Takže hodnota j-ro vypustit v RgSv je definován výrazem

RgSv(j) =

Kde RGAP[i], RgM[i] a ZM - hodnoty i-té číslice, resp RGAP, RGM a j-tá buňka ZM.

Kombinační schéma pro generování výsledku asociativního volání FS tvary ze slova utvořeného v RgSv, signály  0 ,  1 ,  2 odpovídající absenci slov v ZM, splňující asociativní rys, přítomnost jednoho nebo více takových slov. Pro tohle FS implementuje následující booleovské funkce:

 0 =

 1 = РгСв

 2 =  0  1

Tvarování obsahu RgSv a signály  0 ,  1 ,  2 podle obsahu RGAP, RGM A ZM se nazývá operace řízení asociace. Tato operace je nedílnou součástí operací čtení a zápisu, i když má také nezávislou hodnotu.

Při čtení je asociace nejprve řízena asociativním prvkem v RGAP. Poté při  0 = 1 čtení je zrušeno z důvodu nedostatku požadovaných informací, když  1 = 1 je načteno RGI nalezené slovo s  2 = 1 palec RGI slovo se přečte z buňky s nejmenším číslem mezi buňkami označenými 1 in RgSt. Z RGIčtené slovo se vydává na SHIout.

Rýže. 4.3. Struktura asociativní paměti

Při psaní se nejprve hledá volná buňka. K tomu se provede operace řízení přidružení, když RgAP= 111. ..10 a RgM== 00... 01. V tomto případě jsou volné buňky označeny 1 in RgSt. Pro záznam se vybere volná buňka s nejmenším číslem. Obsahuje slovo přijaté od SHIVx PROTI RGI.

Rýže. 4.4. zásobníková paměť

Pomocí operace řízení asociace je možné bez čtení slov z paměti určovat podle obsahu RgSv, kolik slov v paměti, která splňují asociativní atribut, například pro implementaci dotazů, jako je kolik studentů ve skupině má vynikající známku v dané disciplíně. Při použití vhodných kombinačních obvodů lze v asociativní paměti provádět poměrně složité logické operace, jako je hledání většího (menšího) čísla, hledání slov uzavřených v určitých hranicích, hledání maximálního (minimálního) počtu atd.

Všimněte si, že asociativní paměť vyžaduje úložné prvky, které lze číst, aniž by došlo ke zničení informací v nich zaznamenaných. Je to dáno tím, že při asociativním vyhledávání se provádí čtení přes celý SM pro všechny nemaskované bity a není kam uložit informace dočasně zničené čtením.

zásobníková paměť, stejně jako asociativní, je neadresný. V zásobníková paměť(obr. 4.4) buňky tvoří jednorozměrné pole, ve kterém jsou sousední buňky navzájem spojeny bitovými řetězci přenosu slova. Nové slovo se zapíše do horní buňky (buňka 0), zatímco všechna dříve zaznamenaná slova (včetně slova, které bylo v buňce 0) se posunou dolů do sousedních buněk s čísly většími o 1. Čtení je možné pouze z horní (nulové) paměťové buňky, přičemž pokud se provádí čtení s mazáním, všechna ostatní slova v paměti jsou posunuta směrem nahoru do sousedních buněk s vyššími čísly. V této paměti se pořadí, ve kterém se slova čtou, řídí pravidlem: naposledy vstoupil - sloužil jako první. V řadě zařízení uvažovaného typu je také zajištěna operace prostého čtení slova z nulové buňky (bez jeho mazání a přesouvání slova v paměti). Někdy je zásobníková paměť vybavena čítačem zásobníku chst, zobrazující počet zapamatovaných slov. Signál MFST = 0 zápalky prázdné, zásobník, MFST = N - 1 - plný zásobník.

Paměť zásobníku je často organizována pomocí paměti adres. Zásobníková paměť je široce používána při zpracování vnořených datových struktur.

Následující odstavce kapitoly popisují různé typy paměti s organizací adres. Asociativní paměť se v zařízení používá pro dynamickou alokaci paměti a také pro vytváření vyrovnávací paměti.

V asociativních paměťových zařízeních jsou informace vyhledávány pomocí asociativního prvku zaznamenaného v každé paměťové buňce.

V paměti tohoto typu se hledání potřebné informace neprovádí podle adresy, ale podle obsahu samotné informace (tj. podle asociativního atributu). V tomto případě probíhá vyhledávání podle asociativního prvku paralelně v čase pro všechny paměťové buňky. Asociativní vyhledávání umožňuje výrazně zjednodušit a zrychlit zpracování dat. Toho je dosaženo díky skutečnosti, že v takové paměti je operace čtení informací kombinována s prováděním řady logických operací. Můžete například provádět operace, jako jsou:

1) vyhledejte maximální nebo minimální číslo v paměti;

2) hledat slova uzavřená v určitých hranicích;

3) hledejte slova nejbližší asociativnímu prvku, a to jak z větší, tak z menší strany atd.

Nejjednodušší asociativní paměť obvykle provádí jedinou operaci výběru slov, jejichž rys odpovídá asociativnímu rysu.

Paměťové pole (SM) obsahuje N buněk, každá buňka má n+1 bit. Pro indikaci využití buňky se použije n-tý bit služby. Pokud je v n-té číslici 0, pak je buňka volná, pokud 1, pak je obsazená.

N-bitové znaménko vstupuje do registru asociativních vlastností RGP na vstupu SD a kód vyhledávací masky vstupuje do registru masky RGM. V tomto případě je n-tý bit registru RGM nastaven na 0. Asociativní vyhledávání se provádí pouze na těch bitech atributu, které odpovídají "1" v registru masky, tedy na tzv. nemaskovaných bitech RGM. . Nastavením kódu masky M lze tedy libovolně zvolit ty číslice atributu, podle kterých se vyhledávání provádí.

Pro slova z 3M, ve kterých se všechny číslice shodují s nezamaskovanými bity RGP, kombinovaný obvod KS 1 nastaví "1" v odpovídajících bitech porovnávacího registru RGC. Pokud se tedy číslice j-tého slova shoduje s nemaskovatelnými bity znaménka, pak se do j-tého bitu registru RGC zapíše "1", jinak "0". Záznam "1" v j-té číslici RGC znamená, že j-té slovo odpovídá znaku, tj. je slovo, které se v ZM skutečně hledá.

Do registru masky je zapsáno slovo, které umožňuje dotaz na všechny nebo pouze některé číslice asociativní funkce, použití masky umožňuje zmenšit nebo rozšířit oblast hledání.

Informace jsou prohledávány paralelně pro všechny buňky porovnáním dotazu s asociativní funkcí každé buňky.

Výsledek vyhledávání je generován speciálním kombinačním obvodem, který generuje signály, které indikují nepřítomnost slov splňujících podmínky vyhledávání, přítomnost pouze jednoho slova, přítomnost několika slov s takovým asociativním prvkem.

Po vytvoření a zpracování výstražných signálů řídicí obvod přečte potřebné informace.

Při zápisu informací se nejprve najde volná buňka. K tomu se provede operace asociativního vyhledávání u prvku, který má „0“ ve všech číslicích a „0“ je zapsáno do registru masky všemi číslicemi, kromě nejméně významné n-té číslice.

Jsou tedy určeny ty buňky SM, ve kterých je na n-té číslici napsáno „0“, což znamená, že buňka není obsazena. Slovo z registru informací RGI se zapíše do volné buňky s nejmenším číslem.

Při použití dalších kombinačních obvodů v asociativní paměti můžete provádět různé logické operace, určovat maximální nebo minimální počet, počet slov, která mají stejnou asociativní vlastnost atd. Obrázek 1 ukazuje strukturu asociativní paměti. Paměťové buňky asociativního paměťového zařízení musí být prvky statické paměti, v asociativní paměti se ke všem buňkám přistupuje současně a nesmí být přerušovány obnovovacími cykly. Asociativní paměť je nejrychlejší, ale velmi drahá, protože vyžaduje zavedení dalšího porovnávacího obvodu, který umožňuje vyhledávat každou paměťovou buňku. Taková paměť se proto obvykle nepoužívá ve své čisté podobě a vysokorychlostní paměťová zařízení typu cache jsou obvykle implementována jako částečně asociativní.

V mikroprocesorech se jako součást vyrovnávací paměti používá asociativní paměť (paměť s výběrem obsahu) pro uložení adresové části instrukcí a operandů spustitelného programu. V tomto případě není potřeba přistupovat k RAM pro další instrukci nebo požadovaný operand, stačí umístit požadovanou adresu do asociativního znakového registru a pokud jsou požadované informace dostupné v paměti cache, bude okamžitě vydán. Přístup k paměti RAM bude nutný pouze v případě, že požadované informace nejsou v mezipaměti. Použitím mezipaměti tímto způsobem se sníží počet přístupů k paměti RAM, což šetří čas, protože přístup do mezipaměti trvá přibližně 10krát méně času než přístup k paměti RAM.

Zásobníková organizace paměti

Pokud se zápis a čtení provádí přes stejný registr, pak se takové zařízení nazývá zásobníková paměť, fungující na principu "první dovnitř - poslední ven" (FILO-First Input, Last Output).

Paměť zásobníku, stejně jako asociativní, je neadresovatelná, je to soubor buněk, které tvoří jednorozměrné pole, ve kterém jsou sousední buňky navzájem spojeny bitovými řetězci přenosu slov. Slova se vždy zapisují do horní nulové buňky. V tomto případě jsou všechna dříve zaznamenaná slova posunuta o jednu buňku dolů. Čtení probíhá v obráceném pořadí zápisu.

Stack paměti se rozšířily. Pro jeho implementaci do RAM je pomocí programů operačního systému alokována část paměti pro zásobník. V praxi je zásobníková paměť často organizována pomocí konvenční adresové paměti.

Uvažujme organizaci zásobníku paměti jako paměť tvořenou propojenými paměťovými buňkami, ve kterých se informace posouvá dolů, když je do zásobníku zapsáno nové slovo (obr. 2). Výměna informací probíhá pouze přes horní paměťovou buňku. Při čtení slov ze zásobníku může být slovo odstraněno z paměti zásobníku nebo posunuto po kruhu, v závislosti na organizaci zásobníku. Režim čtení – poslední dovnitř, první ven – se nazývá LIFO (Last In First Out).

Obr.2.Organizace zásobníku paměti.

Hardwarová implementace takové paměti není vždy vhodná a často je zásobníková paměť organizována v hlavní paměti počítače pomocí softwaru, což umožňuje měnit velikost zásobníku v závislosti na potřebě. Při organizování zásobníku v hlavní paměti je přidělen speciální registr adres - „ukazatel zásobníku“. Ukazatel zásobníku obsahuje adresu posledního slova vloženého do zásobníku. Když je slovo zapsáno do zásobníku, adresa vrcholu zásobníku se automaticky sníží, když je slovo přečteno, automaticky se zvýší. Zásobníková paměť se obvykle používá k uložení stavu aktuálního programu při zpracování přerušení. Po provedení přerušujícího programu se obnoví stav všech registrů, které existovaly v době přerušení programu v obráceném pořadí záznamu. Na zásobník můžete ukládat i programová data, což je výhodné, protože při přístupu do zásobníku nemusíte zadávat adresu paměťové buňky v programu, k extrahování informací ze zásobníku dochází i bez zadání adresy.

V asociativní paměť prvky se nevybírají podle adresy, ale podle obsahu. Pojďme si poslední pojem vysvětlit podrobněji. Pro paměť s organizací adres byl představen koncept minimální adresovatelná jednotka(MAE) jako část dat, která má individuální adresu. Pojďme si představit podobný koncept pro asociativní paměť, a my budeme tuto minimální jednotku úložiště asociativní paměť volání řetězec asociativní paměti(Popruh). Každý StrAP obsahuje dvě pole: pole tagu a datové pole. Požadavek na čtení do asociativní paměti lze slovy vyjádřit následovně: vyberte řádek (řádky), jejichž tag je (jsou) roven zadané hodnotě.

S takovým dotazem je možný zejména jeden ze tří výsledků:

1. je tam právě jeden řádek s daným tagem;
2. existuje více řádků s danou značkou;
3. neexistuje žádný řádek s danou značkou.

Vyhledávání záznamu podle atributu je činnost typická pro přístupy k databázi a vyhledávání v databázi je často asociativní vyhledávání. Chcete-li provést takové vyhledávání, musíte si prohlédnout všechny záznamy a porovnat danou značku se značkou každé položky. To lze provést i při použití běžné adresovatelné paměti pro ukládání záznamů (a je jasné, že to bude vyžadovat spoustu času - úměrně počtu uložených záznamů!). O asociativní paměťřekněme, když je asociativní načítání dat z paměti podporováno hardwarem. Při zápisu do asociativní paměti je datový prvek umístěn do StrAP spolu s tagem, který je tomuto prvku vlastní. K tomu můžete použít jakýkoli bezplatný STRAP. Zvažte různé strukturální organizace mezipaměti nebo způsoby mapování RAM do mezipaměti.

Plně asociativní cache

Schéma plně asociativní cache je znázorněno na obrázku (viz obrázek níže).

Popišme algoritmus fungování systému s cache pamětí. Na začátku operace je vyrovnávací paměť prázdná. Když je během načítání vykonán první příkaz, jeho kód, stejně jako několik dalších sousedních bajtů programového kódu, se přenese (pomalu) do jednoho z řádků mezipaměti a současně se přenese horní část adresy se zapíše do odpovídajícího tagu. Takto se plní řádek mezipaměti.

Pokud jsou další aporty možné z této sekce, budou provedeny z CASH (rychle) - "CASH hit". Pokud se ukáže, že požadovaný prvek není v mezipaměti, - "CASH miss". V tomto případě se přistupuje k paměti RAM (pomalu) a současně se zaplňuje další řádek mezipaměti.

Plně asociativní schéma mezipaměti

Přístup ke keši je následující. Po vytvoření prováděcí adresy jsou její vysoké bity, které tvoří tag, hardwarově (rychle) porovnány s tagy všech linek cache. V tomto případě jsou možné pouze dvě situace ze tří výše uvedených: buď všechna srovnání poskytnou negativní výsledek (CASH miss), nebo pozitivní výsledek srovnání bude zaznamenán právě pro jeden řádek (CASH hit).

Pokud je při čtení pevný přístup do mezipaměti, nižší bity adresy určují pozici v řádku mezipaměti, ze které se mají vybrat bajty, a typ operace určuje počet bajtů. Je zřejmé, že pokud délka datového prvku přesahuje jeden bajt, pak jsou možné situace, kdy je tento prvek (po částech) umístěn ve dvou (nebo více) různých řádcích mezipaměti, pak se čas pro načtení takového prvku prodlouží. Tomu lze čelit zarovnáním operandů a instrukcí podél hranic mezipaměti, což se bere v úvahu při vývoji optimalizačních překladačů nebo při ruční optimalizaci kódu.

Pokud dojde k chybě mezipaměti a v mezipaměti nejsou žádné volné řádky, musíte jeden řádek keše nahradit řádkem jiným.

Hlavním účelem strategie náhrady je uchovat v mezipaměti linky, ke kterým se s největší pravděpodobností v blízké budoucnosti přistoupí, a nahradit linky, ke kterým bude přístup ve vzdálenější době nebo vůbec. Je zřejmé, že optimální algoritmus bude takový, který nahradí linku, ke které bude v budoucnu přistupováno později, než kterákoli jiná linka mezipaměti.

Bohužel taková předpověď je prakticky nerealizovatelná a člověk se musí uchýlit k algoritmům, které jsou horší než ten optimální. Bez ohledu na použitý náhradní algoritmus musí být pro dosažení vysoké rychlosti implementován v hardwaru.

Mezi mnoha možnými substitučními algoritmy jsou čtyři nejběžnější, uvažované v sestupném pořadí jejich relativní účinnosti. Kterýkoli z nich lze použít v plně asociativní mezipaměti.

Nejúčinnější je náhradní algoritmus založený na nejstarším použití ( LRU – Nejméně nedávno použité ), který nahrazuje řádek mezipaměti, který nebyl zpřístupněn nejdelší dobu. Studie ukázaly, že algoritmus LRU, který se „dívá“ dozadu, funguje docela dobře ve srovnání s optimálním algoritmem, který se „dívá“ dopředu.

Nejznámější jsou dva způsoby hardwarové implementace tohoto algoritmu. V prvním z nich je ke každému řádku mezipaměti přiřazen čítač. Jedna se v určitých intervalech přidává k obsahu všech počítadel. Při přístupu k řetězci se jeho čítač vynuluje. Největší číslo tedy bude v počítadle řádku, který nebyl zpřístupněn nejdelší dobu, a tento řádek je prvním kandidátem na nahrazení.

Druhý způsob je implementován pomocí fronty, kde jsou odkazy na tyto řádky zadávány v pořadí, v jakém jsou řádky cache naplněny. Při každém přístupu k řetězci se jeho odkaz přesune na konec fronty. Výsledkem je, že první ve frontě je pokaždé odkazem na řetězec, který nebyl zpřístupněn nejdelší dobu. Právě tato linka je nahrazena jako první.

Dalším možným náhradním algoritmem je algoritmus první dovnitř, první ven ( FIFO-první dovnitř, první ven ). Tím se nahradí řádek, který byl v mezipaměti nejdéle. Algoritmus je snadno implementován pomocí fronty diskutované výše, pouze s tím rozdílem, že po přístupu k řetězci se pozice odpovídající reference ve frontě nezmění.

Dalším algoritmem je nahrazení nejméně často používaného řetězce (LFU - Least Frequently Used). Řádek v mezipaměti, který byl nejméně přístupný, je nahrazen. Princip lze uvést do praxe přidružením každého řádku k počítadlu zásahů, k jehož obsahu se po každém zásahu přidá jedna. Hlavním uchazečem o výměnu je řetězec, jehož počítadlo obsahuje nejmenší číslo.

Nejjednodušší algoritmus je libovolná volba řetězce, který se má nahradit. Náhradní řetězec je vybrán náhodně. To lze realizovat např. pomocí čítače, jehož obsah se s každým hodinovým impulsem zvyšuje o jedničku, bez ohledu na to, zda došlo k zásahu nebo chybě. Hodnota v čítači určuje řetězec, který má být nahrazen.

Kromě tagu a datových bajtů může řádek mezipaměti obsahovat další servisní pole, mezi nimiž by měl být především bit platnosti V (z platný - platný) a modifikační bit M (z modifikace - změna, úprava) poznamenal. Když se zaplní další řádek mezipaměti, V se nastaví do stavu „platný“ a M se nastaví do stavu „nezměněno“. Pokud byl obsah tohoto řádku změněn během provádění programu, přepne se bit M, což signalizuje, že při nahrazení tohoto řádku by měl být jeho obsah přepsán do RAM. Pokud se z nějakého důvodu změnila kopie prvku tohoto řetězce uloženého jinde (například v RAM), přepne se bit V. Při přístupu k takovému řetězci se zaznamená chyba cache (nehledě na to, že tag odpovídá ) a volání bude do hlavní paměti RAM. Kromě toho může pole služby obsahovat bity, které podporují algoritmus LRU.

Odhad objemu zařízení

Typické množství vyrovnávací paměti v moderním systému je 8 ... 1024 kb a délka řádku mezipaměti je 4 ... 32 bajtů. Další hodnocení je provedeno pro velikost cache 256 KB a délku linky 32 bajtů, což je typické pro systémy s procesory Pentium a PentiumPro. Délka značky je 27 bitů a počet řádků v mezipaměti bude 256 kB/ 32=8192. Tolik digitálních komparátorů 27bitových kódů bude zapotřebí k implementaci výše uvedené struktury.

Hrubý odhad nákladů na vybavení pro stavbu digitálního komparátoru udává hodnotu 10 tranzistorů / bit a celkový počet tranzistorů v samotném komparátorovém bloku se bude rovnat:

10*27*8192 = 2 211 840,

což je přibližně jedenapůlkrát méně než celkový počet tranzistorů na čipu Pentium. Je tedy zřejmé, že popsaná struktura plně asociativní cache paměti () je realizovatelná pouze s malým počtem řádků v cache, tzn. s malým množstvím mezipaměti (prakticky ne více než 32 ... 64 řádků). Větší cache je postavena podle jiné struktury.

Vzhledem k vlastnosti lokality přistupuje většina programů po určitou dobu k malému počtu stránek, takže je aktivně využívána pouze malá část tabulky stránek.

Přirozeným řešením problému s akcelerací je vybavit počítač hardwarovým zařízením pro mapování virtuálních stránek na fyzické bez odkazu na tabulku stránek, to znamená mít malou rychlou mezipaměť, do které je uložena ta část tabulky stránek, která je aktuálně potřeba. Toto zařízení se nazývá asociativní paměť, někdy také používat termín překladový vyhledávací buffer (TLB).

Jeden záznam v tabulce asociativní paměť(jeden vstup) obsahuje informace o jedné virtuální stránce: její atributy a rámec, ve kterém se nachází. Tato pole přesně odpovídají polím v tabulce stránek.

Protože asociativní paměť obsahuje pouze některé položky tabulky stránek, každý záznam v TLB musí obsahovat pole s číslem virtuální stránka. Paměť se nazývá asociativní, protože současně porovnává počet zobrazených virtuální stránka s odpovídajícím polem ve všech řádcích této malé tabulky. Proto je tento typ paměti poměrně drahý. V řadě, pole virtuální stránka která se shodovala s požadovanou hodnotou, je nalezeno číslo rámce stránky. Obvyklý počet záznamů v TLB je od 8 do 4096. Nárůst počtu záznamů v asociativní paměť musí brát v úvahu faktory, jako je velikost mezipaměti hlavní paměti a počet přístupů do paměti na instrukci.

Zvažte fungování správce paměti v přítomnosti asociativní paměť.

Na začátku zobrazení informací virtuální stránka ve fyzickém se nachází v asociativní paměť. Pokud je nalezen požadovaný záznam, je vše v pořádku, kromě porušení oprávnění, kdy je zamítnut požadavek na přístup do paměti.

Pokud je požadovaný vstup v asociativní paměť chybí, zobrazení je přes tabulku stránek. Jeden ze záznamů v asociativní paměť nalezen záznam z tabulky stránek. Zde se potýkáme s tradičním problémem výměny jakékoli mezipaměti (jmenovitě, který z položek v mezipaměti je třeba změnit). Design asociativní paměť by měl organizovat záznamy tak, aby bylo možné rozhodnout, které ze starých záznamů by měly být vymazány, když jsou přidány nové.

Počet úspěšných vyhledání čísla stránek v asociativní paměť ve vztahu k celkovému počtu vyhledávání se nazývá hit (coincidence) ratio (proporce, poměr). Někdy se také používá výraz procento zásahu do mezipaměti. Poměr zásahů je tedy část odkazů, kterou lze použít asociativní paměť. Odkazování na stejné stránky zvyšuje poměr návštěv. Čím vyšší je poměr přístupů, tím nižší je průměrná doba přístupu k datům v paměti RAM.

Předpokládejme například, že určení adresy v případě vynechání mezipaměti v tabulce stránek trvá 100 ns a určení adresy v případě nalezení mezipaměti v asociativní paměť– 20 ns. Při 90% poměru zásahů je průměrná doba rozlišení adresy 0,9x20+0,1x100 = 28ns.

Zcela přijatelný výkon moderních operačních systémů dokazuje efektivitu použití asociativní paměť. Vysoká pravděpodobnost nalezení dat v asociativní paměť spojené s přítomností objektivních vlastností dat: prostorové a časové lokality.

Je třeba věnovat pozornost následující skutečnosti. Při přepínání kontextu procesů se musíte ujistit, že nový proces „nevidí“ dovnitř asociativní paměť informace související s předchozím procesem, např. vymazat. Takže použití asociativní paměť zvyšuje čas přepnutí kontextu.

Považováno za dvouúrovňové ( asociativní paměť+ tabulka stránek ) schéma překladu adres je ukázkovým příkladem hierarchie paměti založené na využití principu lokality, jak bylo uvedeno v úvodu předchozí přednášky.

Tabulka obrácených stránek

Navzdory stupňovité organizaci je ukládání více velkých tabulek stránek stále výzvou. Jeho hodnota je relevantní zejména pro 64bitové architektury, kde je počet virtuálních stránek velmi velký. Řešením je použití tabulka obrácených stránek(tabulka obrácených stránek). Tento přístup se používá na strojích PowerPC, některých pracovních stanicích Hewlett-Packard, IBM RT, IBM AS/400 a několika dalších.

Tato tabulka obsahuje jednu položku pro každý rámec stránky fyzické paměti. Je nezbytné, aby pro všechny procesy stačila jedna tabulka. Pro uložení mapovací funkce je tedy nutná pevná část hlavní paměti, bez ohledu na bitovost architektury, velikost a počet procesů.

Navzdory úspoře RAM je použití o obrácená tabulka má významnou nevýhodu - záznamy v něm (jako v asociativní paměť) nejsou seřazeny vzestupně podle čísel virtuálních stránek, což komplikuje překlad adres. Jedním ze způsobů, jak tento problém vyřešit, je použití hashovací tabulky. virtuální adresy. Zároveň část virtuální adresa, což je číslo stránky, je mapováno na hašovací tabulku pomocí hašovací funkce. Každá stránka fyzické paměti zde odpovídá jednomu záznamu v hashovací tabulce a tabulka obrácených stránek. Virtuální adresy, které mají stejnou hodnotu hash, se navzájem zřetězí. Délka řetězce obvykle nepřesahuje dva vstupy.

Velikost stránky

Vývojáři OS pro stávající stroje mají zřídka možnost ovlivnit velikost stránky. U nově vytvořených počítačů je však důležité rozhodnutí o optimální velikosti stránky. Jak byste očekávali, neexistuje žádná nejlepší velikost. Spíše existuje soubor faktorů, které velikost ovlivňují. Velikost stránky je obvykle mocnina dvou od 29 do 214 bajtů.