virtuální paměť. Architektonická podpora pro virtuální paměť. Asociativní organizace paměti Lidská asociativní paměť

Na rozdíl od konvenční strojové paměti, 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 prohledává celou paměť, aby zjistil, zda je kde uloženo. cokoliv v něm. 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 hardwarovou implementací toho, co by se z hlediska programování nazývalo asociativní pole.

1. 
   Autoasociativní paměť

1. 
   heteroasociativní paměť

1. 
   Popište dvě fáze fungování asociativní paměti

fáze obnovy. Odpovídá procesu načítání uloženého obrazu v reakci na předložení hlučné nebo poškozené verze klíče do sítě.

1. 
   Definujte proces rozpoznávání vzorů

1. 
   Popište dva typy strojů pro rozpoznávání vzorů.

Systém se skládá ze dvou částí: sítě pro extrakci příznaků (bez dohledu) a sítě klasifikace (s dohledem). Obrázek - soubor
pozorování, každé pozorování lze považovat za bod v -rozměrném prostoru pozorování (dat). Extrakce rysů je popsána pomocí transformace, která se převádí na mezilehlý bod v -rozměrném prostoru rysů
. Na tuto transformaci lze nahlížet jako na operaci redukce rozměrů (komprese dat), která zjednodušuje klasifikaci. Klasifikace - transformace, která mapuje mezilehlý bod do jedné z tříd -dimenzionální prostor řešení ( - počet vybraných tříd).

2. typ stroje.

Systém je navržen jako jednovrstvá dopředná síť využívající jeden z dohlížených výukových algoritmů. S tímto přístupem je úloha extrahování funkcí prováděna výpočetními uzly skryté vrstvy sítě.

1. 
   Popište způsob řešení problému identifikace systému.

Popisuje vztah mezi vstupem a výstupem v neznámém systému s více vstupy a výstupy bez paměti (časová invariance systému). Pak lze sadu označených příkladů použít k trénování neuronové sítě představující model tohoto systému. Nechat - výstup neuronové sítě odpovídající vstupnímu vektoru . Signál chyby ( =(požadovaná odezva) - (síťový výstup)) se používá k úpravě volných parametrů sítě, aby se minimalizovala střední kvadratická chyba

1. 
   Popište metodu konstrukce inverzního systému

() - požadovaná odezva, () - vstupní signál (vektory , - se změnily). Vektor chybového signálu se rovná rozdílu mezi požadovaným vektorem a skutečným výstupem neuronové sítě, získaným v odezvě na poruchu. Zde je vektor chybového signálu použit k minimalizaci součtu čtvercových rozdílů mezi výstupy neznámého inverzního systému a neuronové sítě ve statickém smyslu (tj. počítáno přes celou sadu trénovacích příkladů).

1. 
   Uveďte blokové schéma zpětnovazebního řídicího systému

Tento systém využívá jedinou zpětnou vazbu pokrývající celý řídicí objekt. Výstup řídicího objektu je tedy odečten od referenčního signálu () přijatého z externího zdroje. Takto získaný chybový signál (e) je přiveden do neurokontroléru k úpravě volných parametrů. Hlavním úkolem regulátoru je udržovat takový vstupní objektový vektor, pro který by výstupní signál (y) odpovídal referenční hodnotě (d). Jinými slovy, úkolem regulátoru je invertovat vstupně-výstupní mapování řídicího objektu.

1. 
   Popište operace logického součtu a logického součinu na fuzzy množinách

Operace logického součtu:

Nechat
je nejmenší fuzzy podmnožina, která zahrnuje obojí tak s členskou funkcí:

Logická operace součinu na fuzzy množinách:

Nechat
- největší fuzzy podmnožina, která je obsažena současně v a v , pak má funkce členství tvar:

1. 
   Popište operace negace množin a normalizace množin pro fuzzy množiny

Nechat - vše, co není , pak je prvek patřící do množiny určen podle funkce:

Normalizace fuzzy množin:

SUPERMUM: Sup - přesná horní hranice (maximální hodnota členství v sadě).

NORMALIZACE: Fuzzy množina je normální, pokud je supremum množiny roven jedné. Pro normalizaci si znovu přečtěte příslušnost prvků:

M "a (x) \u003d Ma (x) / (Sup Ma (x))

1. 
   Popište operaci koncentrace a protahování pro fuzzy množiny

Operace rozmazání:

1. 
   Definujte lingvistickou proměnnou

Matematická definice lingvistické proměnné:
, kde je název proměnné;
-sada názvů jazykových hodnot proměnné, z nichž každá je fuzzy proměnná v sadě
; - syntaktické pravidlo pro tvoření jmen hodnot;
sémantické pravidlo pro přiřazování každé velikosti hodnoty k jejímu pojmu.

1. 
   Popište algebraické operace součinu pro fuzzy množiny

1. 
   Popište Jaegerovu míru charakterizující stupeň fuzzy množin

,

počet prvků v ,
vzdálenost mezi sadami a v metrice (což se rovná 1 nebo 2). Hammingova metrika odpovídá hodnotě

1. 
   Popište euklidovskou metriku charakterizující míru fuzzy množiny

1. 
   Popište míru entropie fuzziness Kosko množiny

1. 
   Popište Mamdani-Zadeův fuzzy inferenční systém

• 
  soubor použitých fuzzy pravidel;
• 
  databáze obsahující popisy funkcí členství;
• 
  mechanismus inference a agregace, který je tvořen aplikovanými pravidly implikace.

Pro zajištění interakce těchto dvou typů se zavádí fuzzy systém s tzv. fuzzifierem (převaděč vstupních datových souborů na fuzzy množinu) na vstupu a dephasifier (převodník fuzzy množin na konkrétní hodnotu výstupní proměnná) na výstupu.

Výstupní signál výstupního modulu může být ve formě fuzzy množin, které určují rozsah změny výstupní proměnné. Defuzzifier převádí tento rozsah na jednu konkrétní hodnotu, která je brána jako výstup celého systému.

Mamdani-Zadehův inferenční model obsahuje následující operátory:

Obr 1. Příklad inferenčního systému Mamdani-Zadeh

Na Obr. 1 ukazuje metodu agregace pro dvě vstupní proměnné.

1. 
   Charakterizujte fuzzifikátor

1. 
   Popište pojem funkce členství

Koeficient příslušnosti je hodnota z rozsahu, který charakterizuje stupeň příslušnosti prvku ve fuzzy množině.

Reálné číslo, které nabývá hodnoty v rozsahu (0,1), přičemž 1 znamená 100% (nepodmíněné) členství a v množině a 0 - absolutní nepřítomnost v . Hodnoty mezi 0 a 1 charakterizují fuzzy zahrnuté prvky.

Mapování sady prvků na sadu hodnot tvoří funkci členství.

Funkce může být definována explicitně ve formě například algebraického výrazu nebo v tabulkové (diskrétní) formě jako pole dvojic

1. 
   Popište zobecněnou Gaussovu funkci členství

Existuje také zobecněná Gaussova funkce:
parametr formuláře.

Rýže 3. Graf zobecněné Gaussovy funkce proc=1,

Zobecněná Gaussova funkce může být také v racionální formě:
.

1. 
   Popište pojem defuzzifikace fuzzy množiny

1. 
   Popište defuzzifikaci vzhledem ke střednímu středu

1. 
   Popište defuzzifikaci vzhledem ke středu regionu

1. 
   Uveďte blokové schéma fungování genetického algoritmu.

1. 
   Popište pojmy celočíselné a reálné kódování.

Číselné parametry řešení jsou zpravidla zakódovány v chromozomu. K tomu je možné použít celočíselné a reálné kódování.

celočíselné kódování.

V klasickém genetickém algoritmu je chromozom bitový řetězec, který kóduje parametry pro řešení daného problému.

Skutečné kódování.

Často je výhodnější zakódovat do genu ne celé číslo, ale reálné číslo. To vám umožní zbavit se operací kódování a dekódování používaných při kódování celých čísel a zvýšit přesnost řešení.

1. 
   Popište způsoby výběru.

Výběr rulety. V této variantě výběru je pravděpodobnost, že se i-tý jedinec zúčastní křížení pí, úměrná hodnotě jeho zdatnosti fi a rovná se .

Proces výběru jedinců pro křížení připomíná hru rulety.

Kruh rulety je rozdělen na sektory a plocha i-tého sektoru je úměrná hodnotě pí. Poté se ruleta „otočí“ n-krát, kde n je velikost populace, a jednotlivec vybraný ke křížení je určen sektorem, na kterém se ruleta zastaví.

Výběr zkrácením. Při výběru zkrácením se po výpočtu hodnot fitness pro křížení vybere Ln nejlepších jedinců, kde L je „mezní práh“, 0
Zpravidla volte L v rozsahu od 0,3 do 0,7.

Výběr turnaje. V případě použití turnajového výběru pro křížení je stejně jako u ruletového výběru vybráno n jednotlivců.

Za tímto účelem je z populace náhodně vybráno t jedinců a nejzdatnějšímu z nich je umožněno přejít. Říká se, že turnaj se tvoří z t jednotlivců, t je velikost turnaje. Tato operace se opakuje nkrát.

Čím větší je hodnota t, tím větší je selekční tlak. Varianta turnajového výběru, kdy t = 2, se nazývá binární turnaj. Typické hodnoty velikosti turnaje jsou t = 2, 3, 4, 5.
28. Popište princip fungování jednobodových, dvoubodových a homogenních crossover operátorů pro celočíselné kódování.

Pro celočíselné kódování se často používají operátory 1-tečka, 2-tečka a jednotné křížení.

Jednobodové křížení funguje podobně jako operace křížení chromozomů při křížení biologických organismů. K tomu je vybrán libovolný bod zlomu a části rodičovských chromozomů jsou vyměněny, aby se vytvořilo potomstvo.

Pro operátor 2-bodového křížení jsou vybrány 2 náhodné body zlomu, po kterých si rodičovské chromozomy vymění oblasti ležící mezi body zlomu, aby se vytvořilo potomstvo. Všimněte si, že pro operátor 2-bodového křížení je začátek a konec chromozomu považován za „slepený“, v důsledku čehož může jeden z bodů zlomu spadat na začátek/konec chromozomů, a v tomto případě výsledek 2-bodového přejezdu se bude shodovat s výsledkem 1-bodového přejezdu.

Při použití operátoru homogenního křížení se bity rodičovských chromozomů dědí nezávisle na sobě. K tomu určete pravděpodobnost p0, že i-tá číslice chromozomu 1. rodiče se dostane k prvnímu dítěti a 2. rodič - k druhému dítěti. Pravděpodobnost opačného jevu je (1 – p0). Každý bit rodičovských chromozomů je „přehrán“ v souladu s hodnotou p0 mezi chromozomy potomků. Ve většině případů je pravděpodobnost obou událostí stejná, tzn. p0 = 0,5.
29. Popište princip fungování dvoubodového křížení pro reálné kódování.

2-bodové křížení pro reálné kódování je v podstatě stejné jako 2-bodové křížení pro celočíselné kódování. Rozdíl je v tom, že bod zlomu nelze zvolit „uvnitř“ genu, ale musí spadat mezi geny.
30. Popište pojem destruktivní schopnosti crossoveru.

Crossover operátory se vyznačují schopností ničit rodičovské chromozomy.

Crossover pro celočíselné kódování je považován za destruktivnější, pokud je v důsledku jeho aplikace Hammingova vzdálenost mezi výslednými chromozomy potomka a chromozomy rodičů velká.

Jinými slovy, schopnost celočíselného křížení ničit závisí na tom, jak moc „smíchá“ (rekombinuje) obsah rodičovských chromozomů. 1-bodový crossover je tedy považován za slabě destruktivní, zatímco homogenní crossover je ve většině případů silně destruktivní operátor. Odpovídajícím způsobem zaujímá 2-bodový přejezd mezilehlou pozici z hlediska destruktivní síly ve vztahu k 1-bodovému a homogennímu přejezdu.

V případě křížení pro skutečné kódování je schopnost ničit určena tím, jak velká je vzdálenost ve vyhledávacím prostoru mezi body odpovídajícími chromozomům rodičů a potomků. Destruktivní účinek 2 bodového křížení tedy závisí na obsahu rodičovských chromozomů. Destruktivní schopnost aritmetického křížení závisí na hodnotě parametru l, např. pro l >> 1 a l >> 0 bude destruktivní schopnost nízká. U přechodu BLX-a závisí destruktivní schopnost jak na hodnotě a, tak na rozdílu hodnot odpovídajících genů rodičovských jedinců.

Všimněte si, že spolu se schopností ničit se mluví i o schopnosti tvořit (tvorba, stavba) křížením nových jedinců. Je tedy zdůrazněno, že zničením chromozomů rodičovských jedinců může crossover vytvořit zcela nové chromozomy, se kterými se v procesu evolučního hledání dříve nesetkali.
31. Popište kanonický genetický algoritmus.

Kanonický genetický algoritmus byl vyvinut Johnem Hollandem a popsán ve své knize Adaptation in Natural and Artificial Systems, 1975. Představuje jeden ze základních modelů evolučního hledání, podrobně studovaný v 70.-80. letech 20. století.

Kanonický GA má následující vlastnosti:

celočíselné kódování;

Všechny chromozomy v populaci jsou stejně dlouhé;

Konstantní velikost populace;

Výběr rulety;

Jednobodový křížový operátor;

Bitová mutace;

Nová generace se tvoří pouze z potomků (generační mezera T = 1).
32. Jaké znáte modely reprezentace znalostí?

Nejběžnější modely reprezentace znalostí v expertních systémech jsou:

• 
  model reprezentace znalostí pomocí logiky predikátů 1. řádu;

• 
  výrobní model;

• 
  model rámu;

• 
  model reprezentace znalostí ve formě sémantické sítě;

• 
  model reprezentace znalostí ve formě nástěnky;

• 
  model reprezentace znalostí ve formě scénáře;

• 
  model reprezentace znalostí založený na fuzzy logice;

• 
  model reprezentace znalostí neuronové sítě.

Logický model reprezentace znalostí je založen na logice predikátů. Predikát neboli logická funkce je funkcí libovolného počtu argumentů, které nabývají pravdivé nebo nepravdivé hodnoty. Argumenty funkce - hodnoty z libovolné, konečné nebo nekonečné množiny
s názvem předmětná oblast. Predikát od -argumenty se nazývá -místní predikát. Model reprezentace znalostí používá predikátovou logiku prvního řádu, na které je založen Prolog.
34. Z čeho se skládá výrobní systém?

Produkční systém je systém zpracování znalostí, který využívá reprezentace znalostí podle produkčních pravidel. Produkční pravidla jsou výrazy jako „Pokud (podmínka) pak (akce)“. „Podmínka“ – vzorová věta, pomocí které se provádí vyhledávání ve znalostní bázi; „akce“ je akce, která má být provedena, když je vyhledávání úspěšné. Závěr na takovéto znalostní bázi může být přímý (od dat k hledání cíle) a zpětný (od cíle k jeho potvrzení - k datům). Data jsou počáteční fakta uložená v databázi faktů, na jejichž základě je spuštěn inferenční engine nebo interpret pravidel, který třídí pravidla z produkční znalostní báze.

Produkční systém zahrnuje bázi pravidel, databázi a interpret pravidel. Báze pravidel je paměťová oblast, která obsahuje znalostní bázi - soubor znalostí prezentovaných ve formě pravidel ve tvaru POKUD ... POTOM; databáze je oblast paměti, která obsahuje aktuální data (fakta). Interpret je inferenční mechanismus, je to součást systému, která tvoří závěr pomocí báze pravidel a databáze.
35. Popište model reprezentace znalostí ve formě rámců

V systému rámců je jednotkou reprezentace znalostí objekt zvaný rámec. Rámec je forma znázornění určité situace, kterou lze popsat určitým souborem pojmů a entit. Rám je pojmenován jako identifikátor. Tento název musí být jedinečný v celém systému rámů. Rám má specifickou vnitřní strukturu, která se skládá z mnoha prvků nazývaných sloty, které jsou také pojmenovány. Každý slot je reprezentován specifickou datovou strukturou. Někdy slot obsahuje komponent zvaný faseta, který určuje rozsah nebo seznam jeho možných hodnot. Fazeta také určuje mezní hodnoty výplně slotu (například maximální povolený počet bratrů

36. Jak jsou znalosti reprezentovány v sémantickém webu?

Sémantická síť představuje znalosti ve formě grafu, jehož uzly odpovídají faktům nebo pojmům a oblouky vztahům mezi pojmy. Graf je množina vrcholů a množina oblouků spojujících některé dvojice vrcholů. Označený graf pro každý vrchol obsahuje deskriptory (návěsky), díky kterým se vrcholy grafu od sebe liší. Pro stavový graf identifikují deskriptory stavy v procesu řešení problému. Obloukové štítky v sémantických sítích se používají k definování pojmenovaných vztahů.
37. Popište architekturu expertních systémů

Skupina odborníků nebo jiný zdroj odborných znalostí zajišťuje, že fakta, pozorování a metody analýzy situací jsou načteny do znalostní báze. Uživatel se dotáže systému na konkrétní problémy prostřednictvím rozhraní, které umožňuje komunikaci pomocí normálních výrazů.

Informace obsažené ve znalostní bázi jsou zpracovávány inferenčním strojem, který používá empirické asociace nebo pravidla „Jestli... POTOM“ k vytvoření a testování možných řešení. Uživatelské rozhraní v přístupné podobě předává výsledky obsluze.

Ve výkonných inteligentních systémech existuje přirozené jazykové rozhraní, které vám umožňuje klást otázky a přijímat odpovědi v jednoduché angličtině nebo ruštině. V případě běžných inteligentních systémů je uživateli poskytnuto méně propracované, ale přesto „přátelské“ rozhraní.

38. Popište funkce výstupního stroje (mechanismu)

Hlavní věcí v ES je mechanismus, který prohledává znalostní bázi podle pravidel racionální logiky za účelem získání řešení. Tento mechanismus, nazývaný inferenční stroj, se aktivuje při přijetí požadavku uživatele a provádí následující úkoly:

• 
  porovnává informace obsažené v požadavku uživatele s informacemi ze znalostní báze;

• 
  hledá konkrétní cíle nebo kauzální vztahy;

• 
  vyhodnocuje relativní jistotu faktů na základě příslušných faktorů spolehlivosti spojených s každým faktem.

Ve fázi identifikace jsou určeny úkoly, které mají být řešeny, jsou identifikovány rozvojové cíle, zdroje, odborníci a kategorie uživatelů.

Ve fázi získávání znalostí se rozlišují tři strategie: získávání znalostí, extrakce znalostí a objevování znalostí. Získávání znalostí je chápáno jako metoda automatizovaného naplňování znalostní báze prostřednictvím dialogu odborníka a speciálního programu. Extrakce znalostí je postup interakce mezi znalostním inženýrem a zdrojem znalostí (odborníkem, odbornou literaturou atd.) bez použití výpočetní techniky. Pojem objevování znalostí je spojen s tvorbou počítačových systémů, které implementují metody automatického získávání znalostí. Nyní je tento směr nejslibnější. Zároveň se předpokládá, že systém sám bude schopen odhalit zákonitosti předmětné oblasti a na základě dostupného empirického materiálu formulovat potřebné poznatky.

Ve fázi konceptualizace je provedena analýza problémové oblasti, identifikovány použité pojmy a jejich vztahy a stanoveny metody řešení problémů.

Fáze formalizace určuje způsoby reprezentace všech typů znalostí, formalizuje základní pojmy, určuje způsoby interpretace znalostí a modeluje fungování systému. V této fázi se posuzuje přiměřenost cílů systému pevných pojmů, metod řešení, prostředků reprezentace a manipulace se znalostmi.

Ve fázi provádění je znalostní báze systému naplněna. Ve fázi testování odborník (a znalostní inženýr) interaktivně pomocí interaktivních a vysvětlujících nástrojů kontroluje způsobilost ES. Proces testování pokračuje, dokud zkoušející nerozhodne, že systém dosáhl požadované úrovně způsobilosti.

Ve fázi zkušebního provozu je prověřena vhodnost ES pro koncové uživatele. Na základě výsledků této fáze, jakož i fáze testování, může být vyžadována významná úprava SE.

Proces vytváření ES není omezen na striktní sled kroků uvedených výše. Během vývoje se musíte opakovaně vracet do dřívějších fází a revidovat tam učiněná rozhodnutí.

Nalezení čísla rámce odpovídající požadované stránce ve víceúrovňové tabulce stránek vyžaduje několik přístupů do hlavní paměti, a proto zabere spoustu času. V některých případech je takové zpoždění nepřijatelné. Problém akcelerace vyhledávání je řešen na úrovni počítačové architektury.

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 zrychlení je poskytnout počítači hardwarové zařízení pro mapování virtuálních stránek na fyzické stránky bez přístupu k tabulce stránek, to znamená mít malou rychlou mezipaměť, která ukládá část tabulky stránek, která je aktuálně potřebná. Toto zařízení se nazývá asociativní paměť, někdy se také používá termín překladová vyrovnávací paměť (TLB).

Jeden záznam tabulky v asociativní paměti (jeden záznam) 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é záznamy tabulky stránek, musí každý záznam v TLB obsahovat pole s číslem virtuální stránky. Paměť se nazývá asociativní, protože současně porovnává číslo zobrazené virtuální stránky s odpovídajícím polem ve všech řádcích této malé tabulky. Proto je tento typ paměti poměrně drahý. Řádek, jehož pole virtuální stránky odpovídá hledané hodnotě, obsahuje číslo rámce stránky. Typický počet záznamů v TLB je od 8 do 4096. Růst počtu záznamů v asociativní paměti musí být proveden s ohledem na 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ěti.

Za prvé, informace o mapování virtuální stránky na fyzickou se nachází v asociativní paměti. Pokud je nalezen požadovaný záznam, je vše v pořádku, kromě porušení oprávnění, kdy je požadavek na přístup do paměti zamítnut.

Pokud požadovaný záznam v asociativní paměti neexistuje, mapování se provede přes tabulku stránek. Jeden ze záznamů v asociativní paměti je nahrazen nalezeným záznamem 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). Návrh asociativní paměti musí organizovat záznamy takovým způsobem, aby bylo možné rozhodnout, který ze starých záznamů by měl být vymazán, když jsou zavedeny nové.

Počet úspěšných vyhledávání čísel stránek v asociativní paměti vzhledem k celkovému počtu vyhledávání se nazývá poměr shody (proporce, poměr). Někdy se také používá termín „procento zásahu do mezipaměti“. Poměr přístupů je tedy zlomkem odkazů, které lze vytvořit pomocí asociativní paměti. 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 trvá 100 ns v případě, že mezipaměť neprojde tabulkou stránek, a 20 ns, aby se určila adresa v případě zásahu do mezipaměti přes asociativní paměť. Při 90% poměru zásahů je průměrná doba rozlišení adresy 0,9x20 + 0,1x100 = 28 ns.

Vcelku přijatelný výkon moderních operačních systémů dokazuje efektivitu využití asociativní paměti. Vysoká hodnota pravděpodobnosti nalezení dat v asociativní paměti je spojena 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ů je nutné zajistit, aby nový proces „neviděl“ v asociativní paměti informace související s předchozím procesem, např. je vyčistil. Použití asociativní paměti tedy prodlužuje dobu přepínání kontextu.

Uvažované dvouúrovňové schéma převodu adres (asociativní paměť + tabulka stránek) je názorným příkladem paměťové hierarchie založené na využití principu lokality, o kterém byla řeč v úvodu předchozí přednášky.

Ú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 registru asociativního atributu 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, ukazuje 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.

Paměť s asociativním přístupem popř asociativní paměť se od ostatních typů paměti liší tím, že k jejím buňkám se nepřistupuje na konkrétní adrese, ale na obsah paměťové buňky. Ve skutečnosti asociativní paměť funguje jako vyhledávač, který dokáže najít informace o daném vzoru. Asociativní paměť je založena na asociativní úložná zařízení(AZU), které jsou stejně jako většina operačních pamětí volatilní a jsou implementovány ve formě polovodičových mikroobvodů (čipových sad).

Princip činnosti AZU je vysvětlen na schématu na Obr. 3.8 Paměťové pole se stejně jako u adresových pamětí dělí na m- bitové buňky, jejichž počet n. Složení AZU zpravidla zahrnuje:

úložné pole (SM);

Registr asociativních znaků (RgAP);

registr masky (RgM);

· Registr indikátoru adresy se srovnávacími obvody na vstupu.

V CAM mohou být další prvky, jejichž přítomnost a funkce jsou určeny způsobem použití CAM.

Rýže. 3.8. Asociativní úložné zařízení

Vzorkování informací z AZU probíhá následovně. Vzorek vyhledávání je přenesen z řídicího zařízení do registru asociativních znaků - kód atributu požadovaných informací(někdy nazývané srovnání). Kód může mít libovolný počet číslic - od 1 před m. Pokud je kód funkce použit celý, pak vstupuje do porovnávacího obvodu beze změny, ale pokud je nutné použít pouze část kódu, pak jsou zbytečné bity maskovány pomocí registru masky. Před zahájením vyhledávání informací v modulu CAM jsou všechny bity registru indikátoru adresy nastaveny do stavu 1 .Poté je dotazována první číslice všech buněk pole úložiště a obsah je porovnáván s první číslicí registru asociativních prvků. Pokud je obsah první číslice i-tá buňka neodpovídá obsahu první číslice RgAP, pak číslice registru indikátoru adresy odpovídající této buňce T i resetovat do stavu 0 , pokud se shoduje - vybití T i Zůstává 1 . Poté se tato operace opakuje s druhou, třetí a následující číslicí, dokud není provedeno srovnání se všemi úrovněmi RgAP. Po bitovém výslechu a srovnání ve státě 1 zůstanou ty bity registru indikátoru adresy, které odpovídají buňkám obsahujícím informace, které se shodují s informacemi zaznamenanými v registru asociativních znaků. Tyto informace lze číst v pořadí určeném řídicím zařízením.

Všimněte si, že doba vyhledávání informací v SM pomocí asociativního prvku závisí pouze na počtu číslic prvku a na rychlosti dotazování číslic, ale vůbec nezávisí na počtu buněk SM. To určuje hlavní výhodu AMS oproti adresovým pamětem: v adresových pamětech vyžaduje operace vyhledávání výčet všech buněk úložného pole. Kromě toho existují implementace CAM, které současně prohledávají všechny bity všech slov uložených v paměti, tzn. doba vyhledávání v takových zařízeních nepřekračuje dobu cyklu paměti.

Záznam nové informace do ZM se provádí bez uvedení čísla buňky. Obvykle se jedna z číslic každé buňky používá k označení jejího použití, tzn. pokud je buňka volná pro zápis, zapíše se tento bit 0 a pokud je zaneprázdněn, - 1 . Poté, když jsou do modulu CAM zapsány nové informace, je nastaveno znaménko 0 v odpovídající číslici registru asociativních znaků a jsou určeny všechny buňky SM, které jsou volné pro zápis. Do jednoho z nich umístí řídicí zařízení nové informace.

Často jsou CAM stavěny tak, že je kromě asociativního umožněno i přímé adresování dat, což představuje určité vymoženosti při práci.

Je třeba poznamenat, že paměťové prvky CAM, na rozdíl od prvků adresovatelné paměti, musí nejen ukládat informace, ale také vykonávat určité logické funkce, takže vám umožňují vyhledávat nejen podle rovnosti buňky obsah k danému atributu, ale také jinými podmínkami: obsah buňky je větší než (menší než) porovnávaný a větší než nebo roven (menší než nebo rovný).

Výše uvedené vlastnosti CAM charakterizují výhody CAM pro zpracování informací. Vytvoření několika proudů identických informací pomocí CAM je rychlé a jednoduché a s velkým množstvím provozních prvků lze vytvářet vysoce výkonné systémy. Musíme také vzít v úvahu skutečnost, že na základě asociativní paměti je snadné realizovat změnu místa a pořadí informací. Z tohoto důvodu je CAM účinným prostředkem pro generování datových sad.

Studie ukazují, že řadu úloh, jako je zpracování radarových informací, rozpoznávání snímků, zpracování různých snímků a další úlohy s maticovou datovou strukturou, jsou efektivně řešeny pomocí asociativních systémů. Navíc programování takových úloh pro asociativní systémy je mnohem jednodušší než pro tradiční.

Bohužel, zařízení s asociativní pamětí mají vysokou výrobní složitost a náklady, které převyšují dynamické i statické RAM. Asociativní paměť je základem pro budování paralelních asociativních systémů, stejně jako pro letadla řízená tokem dat. Asociativní přístup je nejrozšířenější v subsystémech cache paměti.

Mezipaměti

Poprvé byla dvouúrovňová struktura paměti navržena M. Wilksem v roce 1965 při stavbě počítače Atlas. Podstatou přístupu bylo umístění vysokorychlostní vyrovnávací paměti malé velikosti mezi CPU a RAM. Během provozu počítače se do vyrovnávací paměti zkopírují ty části OP, ke kterým se přistupuje. Díky dodržení zásady referenční lokality je dosaženo významného zvýšení výkonu.

Nazývá se nový typ paměti mezipaměť(z angličtiny. mezipaměti- "úkryt, úkryt"), protože taková paměť je skrytá, "neviditelná" pro CPU, které k ní nemůže přímo přistupovat. Programátor si zase nemusí být vůbec vědom existence mezipaměti. V sériových počítačích byla vyrovnávací paměť poprvé použita v systémech Model 85 rodiny IBMS/360. Mezipaměť je dnes přítomna v jakékoli třídě počítačů a často má víceúrovňovou strukturu.

Všechny termíny, které byly definovány dříve, lze použít pro vyrovnávací paměť, ačkoli slovo " čára» ( čára) se často používá místo slova " blok» ( blok).

Mezipaměť je zpravidla postavena na základě ultrarychlé a drahé paměti RAM statického typu, přičemž její rychlost je 5–10krát vyšší než rychlost paměti RAM a její objem je 500–1000krát menší. Všimněte si, že nejen a ani ne tak vysoké náklady na statickou RAM brání nárůstu množství mezipaměti v poměru ke kapacitě RAM. Faktem je, že se zvýšením kapacity mezipaměti se zvyšuje složitost řídicích schémat, což zase vede k poklesu výkonu. Četné studie prokázaly, že uvedený poměr mezipaměti a RAM je optimální a bude zachován v procesu vývoje počítače se zvýšením rychlosti obou typů pamětí.

Jak již bylo zmíněno, CPU nemá přímý přístup k cache paměti. Za organizaci interakce CPU, OP a mezipaměti je zodpovědný speciální řadič. Celý OP je rozdělen do bloků pevné velikosti, přičemž určuje horní část adresy OP blokovat adresu a spodní část je adresa slova v bloku. Výměna informací mezi OP a vyrovnávací pamětí probíhá v blocích. Vyrovnávací paměť má také své vlastní vnitřní adresování a každý blok načtený z RAM je umístěn do mezipaměti podle určitého blokovat adresu v mezipaměti. Často se nazývají bloky mezipaměti linky nebo řádky mezipaměti.

Pokud je blok požadovaný CPU již v mezipaměti, jeho čtení je dokončeno při přístupu do mezipaměti. Při přístupu k adrese tedy musí řadič nejprve určit, zda existuje kopie bloku obsahujícího tuto adresu v paměti cache, a pokud ano, určit, na jaké adrese cache tento blok začíná. Regulátor přijímá tyto informace pomocí mechanismus překladu adres. Složitost tohoto mechanismu závisí na strategie umístění, který určuje, kam v mezipaměti má být každý blok RAM umístěn.

Neméně důležitá je otázka, kdy umístit kopii bloku z OP do cache paměti. Tento problém je vyřešen pomocí vzorkovací strategie.

Při zápisu do mezipaměti existuje několik metod pro nahrazení starých informací, které jsou určeny strategie obnovy hlavní paměti.

Často nastává situace, kdy i přes výběr potřebného bloku z RAM není v mezipaměti místo, kam jej umístit. V tomto případě musíte vybrat jednu z řádků mezipaměti a nahradit ji novým blokem. Způsob, jak určit řádek mezipaměti, který se má odstranit, se nazývá substituční strategie.

Strategie umístění

Existují následující způsoby, jak umístit data do mezipaměti:

přímá distribuce;

plně asociativní distribuce;

· částečně (vícenásobná) asociativní distribuce.

Řekněme šířku adresové sběrnice n, dále kapacita OP V OP = 2n slova. Bez ztráty obecnosti definujeme velikost řádku cache jako 256 slov, takže celý OP bude rozdělen na 2n-8 bloky. Na adresu OP senior n-8 bity určí adresu bloku a dolní bajt určí adresu slova v bloku. Nechte kapacitu mezipaměti V cache 1024x menší než je kapacita OP, tzn. V cache = 2n-10 slova nebo 2n-18 bloky (řádky mezipaměti).

přímá distribuce

Pokud má každý blok hlavní paměti pouze jedno pevné místo, kde se může objevit v mezipaměti, pak se taková mezipaměť zavolá cache přímého přidělení(přímá mapovaná cache). Jedná se o nejjednodušší organizaci vyrovnávací paměti, ve které jsou nejméně významné bity adresy bloku jednoduše použity k mapování adres OP bloků na adresy vyrovnávací paměti. Tedy všechny OP bloky, které mají ve své adrese stejné nejméně významné číslice, spadají do jednoho cache řádku, tzn.

(adresa řádku mezipaměti) = (adresa bloku RT) mod (počet bloků v mezipaměti)

V našem příkladu adresa řádku cache C bude junior n-18 bit adresy OP bloku (viz obrázek 3.9). Převod adresy bloku OD na adresu řádku mezipaměti se provádí načtením těchto nižších n-18 bit. Na této adrese řádku cache má kterýkoli z 1024 OP bloků stejnou n-18 nižší bity. Tyto bloky se mezi sebou budou lišit o nejvýznamnějších 10 bitů t, volal štítek. Pro zjištění, který konkrétní blok RAM je aktuálně uložen v mezipaměti, se používá jiná paměť – tzv paměť štítků (paměť štítků). Paměť tagu je adresována slovo po slovu, přičemž každé slovo má velikost rovnou velikosti tagu. Kapacita paměti tagu je součinem velikosti tagu a celkového počtu řádků mezipaměti, pro náš příklad to je 10 2 n-18 bit. Adresa paměti tagu je adresa řádku mezipaměti S. Na rozdíl od paměti tagů se nazývá paměť, která ukládá bloky uložené v mezipaměti datová paměť. Datová paměť je adresována slovo po slově, její adresa je tvořena z adresy řádku cache a adresy slova v bloku (řádek cache).

Rýže. 3.9. Struktura adres paměti v přímé alokaci

Rýže. 3.10. Organizace mezipaměti s přímou alokací

Při přístupu A-tá adresa OP (obr. 3.10) ml n-18 bit adresy bloku (pole C) obsahující tuto adresu se použijí jako adresa řádku mezipaměti. Tag se načte z paměti tagu na adrese řádku cache (pole t). Paralelně s tím se přistupuje do datové paměti pomocí n-10 nejméně významné bity adresy A(pole C A w). Pokud je načten tag a horních 10 bitů adresy A shodu, to znamená, že blok obsahující adresu A, existuje v datové paměti a zpřístupněné slovo ukládá kopii A adresa OP.

Pokud se značka liší od horních 10 bitů adresy A, pak je z hlavní paměti načten blok obsahující adresu A a řádek mezipaměti je odstraněn z mezipaměti, jejíž adresa je určena polem C(mladší n-18 bitů) adresy čteného bloku. Blok načtený z RAM je umístěn na místo vymazaného řádku mezipaměti a odpovídající tag v paměti tagu je aktualizován.

Výhodou přímé alokace je snadná implementace, nicméně vzhledem k tomu, že adresa linky cache je jednoznačně určena adresou bloku OP, je vysoká pravděpodobnost koncentrace blokových oblastí v některé části cache. K výměně bloků v této části dochází poměrně často, zatímco ostatní oblasti mezipaměti mohou být nečinné. V takové situaci je účinnost vyrovnávací paměti znatelně snížena.

Paměť s náhodným přístupem zpravidla obsahuje množství identických paměťových prvků, které tvoří paměťové 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 uložení slova (čísla, příkazu atd.). Adresa je číslo buňky SM, ve které se toto slovo nachází.

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 adresové paměti obsahuje paměťové pole N-bitových buněk a jeho hardwarový rámec, včetně registru adres RgA mít k (k» log N) bitů, registr informací RGI, blok pro načtení adresy BAS, blok čtecích zesilovačů AUTOBUS, blok bitových zesilovačů-formátorů záznamových signálů BUZ a správu paměti BUP.

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 z adresní sběrnice USA adresy odvolání a příjmu v BUP a dekódování řídícího signálu Úkon A, které určuje typ požadované operace (čtení nebo zápis).

Další při čtení BAS dešifruje adresu, odešle čtecí signály do buňky SM určené adresou, zatímco kód slova zapsaného v buňce je načten čtecími zesilovači BUS a odeslán do RGI. Operace čtení je dokončena vydáním slova z RGI na výstupní informační sběrnici PWM.

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 A RGI. 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ů.

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. Pole úložiště obsahuje N (n+1)-bitových buněk. Obslužný n-tý bit slouží k indikaci obsazenosti buňky (0 - buňka je volná, 1 - slovo je zapsáno v buňce).