Memoria asociativă este o memorie distribuită care învață pe baza asocierilor, similară creierului ființelor vii. În tehnologia informației, memoria este accesată nu prin adresă, ci prin conținut. Modelul care implementează memoria asociativă trebuie să recunoască modelul necesar și să-l recupereze.
Spre deosebire de memoria convențională a mașinii, în care utilizatorul specifică o adresă de memorie și RAM returnează cuvântul de date stocat la acea adresă, UA este proiectat astfel încât utilizatorul specifică cuvântul de date și UA caută în toată memoria pentru a vedea dacă este stocat unde. orice în ea. Dacă se găsește un cuvânt de date, UA returnează o listă cu una sau mai multe adrese de stocare la care a fost găsit cuvântul (și, pe unele arhitecturi, returnează, de asemenea, cuvântul de date în sine sau alte date asociate). Astfel, AP-ul este o implementare hardware a ceea ce în termeni de programare s-ar numi o matrice asociativă.
Memoria autoasociativă
memorie heteroasociativă
Descrieți două faze în funcționarea memoriei asociative
- imagine cheie 
-vector de model memorat, 
-numar de imagini (capacitate). Imaginea cheie acționează nu numai ca un stimul care determină locația imaginii amintite, dar conține și cheia pentru a o recupera. faza de recuperare. Corespunde procesului de preluare a unei imagini stocate ca răspuns la prezentarea unei versiuni zgomotoase sau corupte a unei chei în rețea.
Definiți un proces de recunoaștere a modelelor
Descrieți două tipuri de mașini de recunoaștere a modelelor.
Sistemul constă din două părți: o rețea de extracție a caracteristicilor (nesupravegheată) și o rețea de clasificare (supravegheată). Imagine - un set de 
observații, fiecare observație poate fi considerată ca un punct 
în spaţiul -dimensional al observaţiilor (datelor). Extragerea caracteristicilor este descrisă folosind o transformare care se traduce într-un punct intermediar 
spațiu caracteristic în -dimensional 
. Această transformare poate fi privită ca o operație de reducere a dimensionalității (comprimarea datelor), care simplifică sarcina de clasificare. Clasificare - o transformare care mapează un punct intermediar la una dintre clase 
-spațiul dimensional al soluțiilor ( - numărul claselor selectate).
Al 2-lea tip de mașină.
Sistemul este proiectat ca o singură rețea feedforward multistrat, folosind unul dintre algoritmii de învățare supravegheată. Cu această abordare, sarcina de extragere a caracteristicilor este îndeplinită de nodurile de calcul ale stratului ascuns al rețelei.
Descrieți o metodă de rezolvare a problemei de identificare a sistemului.
Descrie relația dintre intrare și ieșire într-un sistem necunoscut cu intrări multiple și ieșiri fără memorie (invarianța în timp a sistemului). Apoi setul de exemple etichetate poate fi folosit pentru a antrena o rețea neuronală reprezentând un model al acestui sistem. Lasa 
- ieșirea rețelei neuronale corespunzătoare vectorului de intrare 
. Semnal de eroare ( 
=
(răspunsul dorit) - (ieșire de rețea)) este utilizat pentru a ajusta parametrii liberi ai rețelei pentru a minimiza eroarea pătratică medie 
Descrieți o metodă de construire a unui sistem invers
generează un răspuns, specificat ca un vector. Sistemul invers poate fi descris după cum urmează: 
funcție vectorială 
-invers. Pe baza multor exemple etichetate ( 
) puteți construi o rețea neuronală care aproximează funcția inversă folosind schema: 
() - răspunsul dorit, () - semnalul de intrare (vectori , - și-au schimbat locurile). Vector semnal de eroare 
este egală cu diferența dintre vectorul dorit și ieșirea reală a rețelei neuronale, obținută ca răspuns la perturbație. Aici, vectorul semnalului de eroare este utilizat pentru a minimiza suma diferențelor pătrate dintre ieșirile sistemului invers necunoscut și rețeaua neuronală într-un sens static (adică, calculat pe întregul set de exemple de antrenament).
Dați o diagramă bloc a unui sistem de control cu feedback
Acest sistem folosește un singur feedback care acoperă întregul obiect de control. Astfel, ieșirea obiectului de control este scăzută din semnalul de referință () primit de la o sursă externă. Semnalul de eroare (e) obținut în acest fel este transmis neurocontrolerului pentru a regla parametrii liberi. Sarcina principală a controlerului este să mențină un astfel de vector obiect de intrare pentru care semnalul de ieșire (y) să corespundă valorii de referință (d). Cu alte cuvinte, sarcina controlerului este de a inversa maparea intrare-ieșire a obiectului de control.
Descrieți operațiile de sumă logică și produs logic pe mulțimi fuzzy
, care este egal cu 1 dacă elementul aparține mulțimii A, sau egal cu 0 în caz contrar. În sistemele fuzzy, un element poate aparține parțial oricărei mulțimi. Gradul de apartenență în mulțimea A, care este o generalizare a funcției caracteristice, se numește funcție de apartenență și 
, Și 
înseamnă că x nu aparține mulțimii A și 
- proprietate deplină. Valoarea specifică a funcției de apartenență se numește grad sau coeficient de apartenență. Operație de sumă booleană:
Lasa 
este cel mai mic submult fuzzy care le include pe ambele 
asa de 
cu functie de membru:
Funcționarea logică a produsului pe seturi fuzzy:
Lasa 
- cea mai mare submulțime fuzzy care este conținută simultan în și în , atunci funcția de membru are forma:
Descrieți operațiunile de negație și normalizare a seturilor pentru mulțimi fuzzy
Lasa 
- tot acel set care nu este 
, atunci elementul aparținând mulțimii se determină în funcție de funcția:
Normalizarea seturilor fuzzy:
SUPERMUM: Sup - limita superioară exactă (valoarea maximă de membru prezentă în set).
NORMALIZARE: O mulțime neclară este normală dacă supremamul setului este egal cu unu. Pentru a normaliza, recitiți apartenența elementelor:
M "a (x) \u003d Ma (x) / (Sup Ma (x))
Descrieți operația de concentrare și întindere pentru seturi fuzzy
Operațiune de estompare: 
Definiți o variabilă lingvistică
Definiția matematică a unei variabile lingvistice: 
, unde este numele variabilei; 
-set de nume de valori lingvistice ale variabilei, fiecare dintre acestea fiind o variabilă fuzzy pe set 
; 
- regula sintactica pentru formarea numelor de valori; 
o regulă semantică pentru asocierea fiecărei mărimi de valoare cu conceptul său.
Descrieți operația de produs algebric pentru mulțimi fuzzy
(agregarea premiselor).
Descrieți măsura Jaeger care caracterizează gradul de neclaritate al mulțimilor
,
numărul de elemente în , 
distanta dintre multimi si in metrica 
(care este egal cu 1 sau 2). Valoarea corespunde valorii Hamming 
Descrieți metrica euclidiană care caracterizează măsura neclarității unei mulțimi
se numește metrica euclidiană: 
.
Descrieți măsura entropiei de neclaritate a mulțimii Kosko
Setați numărul cardinal 
suma coeficienților de apartenență a tuturor elementelor acestei mulțimi, i.e. 
.
Descrieți sistemul de inferență fuzzy al lui Mamdani-Zade
set de reguli fuzzy utilizate;
o bază de date care conține descrieri ale funcțiilor de membru;
mecanism de inferență și agregare, care este format din regulile de implicare aplicate.
Pentru a asigura interacțiunea acestor două tipuri, se introduce un sistem fuzzy cu așa-numitul fuzzifier (un convertor de seturi de date de intrare într-un set fuzzy) la intrare și un defazator (un convertor de seturi fuzzy într-o valoare specifică a variabilă de ieşire) la ieşire.
Semnalul de ieșire al modulului de ieșire poate fi sub formă de seturi fuzzy care determină intervalul de modificare a variabilei de ieșire. Defuzzifier-ul convertește acest interval într-o valoare specifică care este luată ca rezultat al întregului sistem.
Modelul de inferență al lui Mamdani-Zadeh conține următorii operatori: 
Fig 1. Exemplu de sistem de inferență Mamdani-Zadeh
Pe fig. 1 prezintă metoda de agregare pentru două variabile de intrare.
Caracterizați fuzzifier-ul
Descrieți conceptul de funcție de membru
Coeficientul de apartenență este o valoare din intervalul care caracterizează gradul de apartenență a unui element într-o mulțime fuzzy.
Un număr real care ia o valoare în intervalul (0,1), în timp ce 1 înseamnă apartenența 100% (necondiționată) a lui a în set și 0 - absența absolută în . Valorile între 0 și 1 caracterizează elementele incluse neclare.
Maparea unui set de elemente la un set de valori formează o funcție de apartenență.
Funcția poate fi definită explicit sub forma, de exemplu, a unei expresii algebrice sau într-o formă tabelară (discretă) ca o matrice de perechi
Descrieți funcția de membru Gaussian generalizat
și parametrul lățime 
se pare ca: 
Există, de asemenea, o funcție Gaussiană generalizată: 
parametrul de formular. 
Orez 3. Graficul funcției gaussiene generalizate pentruc=1,
Funcția Gaussiană generalizată poate fi și în formă rațională: 
.
Descrieți conceptul de defuzzificare a mulțimii fuzzy
Descrieți defuzificarea în raport cu centrul mediu
Unde 
Centru 
-a-a funcție de membru unic care participă la funcția finală agregată.
Descrieți defuzificarea față de centrul regiunii
sau sub formă discretă 
.
Dați o diagramă bloc a funcționării algoritmului genetic.
Descrieți conceptele de codificare întreg și real.
De regulă, parametrii numerici ai soluției sunt codificați în cromozom. Pentru aceasta, este posibil să se utilizeze codare întreagă și reală.
codificare cu numere întregi.
Într-un algoritm genetic clasic, un cromozom este un șir de biți care codifică parametrii pentru rezolvarea unei anumite probleme.
Codare reală.
Este adesea mai convenabil să codificați într-o genă nu un număr întreg, ci un număr real. Acest lucru vă permite să scăpați de operațiunile de codificare și decodare utilizate în codificarea întregului și să creșteți acuratețea soluției.
Descrieți metodele de selecție.
Alegerea ruletei.În această variantă de selecție, probabilitatea celui de-al i-lea individ de a lua parte la traversarea pi este proporțională cu valoarea fitness-ului său fi și este egală cu .
Procesul de selectare a indivizilor pentru încrucișare seamănă cu un joc de ruletă.
Cercul ruletei este împărțit în sectoare, iar aria sectorului i-lea este proporțională cu valoarea lui pi. După aceea, ruleta „se învârte” de n ori, unde n este mărimea populației, iar individul selectat pentru traversare este determinat de sectorul pe care se oprește ruleta.
Selectare prin trunchiere. La selectarea prin trunchiere, după calcularea valorilor de fitness pentru trecere, sunt selectați Ln cei mai buni indivizi, unde L este „pragul de limită”, 0
De regulă, alegeți L în intervalul de la 0,3 la 0,7.
Selecția turneului.În cazul utilizării selecției turneului pentru încrucișare, ca în selecția la ruletă, sunt selectați n persoane.
Pentru a face acest lucru, t indivizi sunt selectați aleatoriu din populație, iar celui mai potrivit dintre ei i se permite să se încrucișeze. Se spune că un turneu este format din t indivizi, t este mărimea turneului. Această operație se repetă de n ori.
Cu cât valoarea lui t este mai mare, cu atât presiunea de selecție este mai mare. Varianta de selecție a turneului, când t = 2, se numește turneu binar. Valorile tipice ale mărimii turneului sunt t = 2, 3, 4, 5.
28. Descrieți principiul de funcționare a operatorilor de încrucișare omogene într-un punct, în două puncte și pentru codificarea întregilor.
Pentru codificarea întregului, sunt adesea utilizați operatori de încrucișare cu 1 punct, 2 puncte și uniform.
Încrucișarea în 1 punct funcționează similar cu operația de încrucișare a cromozomilor atunci când încrucișează organisme biologice. Pentru a face acest lucru, este selectat un punct de întrerupere arbitrar și părți ale cromozomilor parentali sunt schimbate pentru a crea descendenți.
Pentru operatorul de încrucișare în 2 puncte, sunt selectate 2 puncte de rupere aleatoare, după care, pentru a crea descendenți, cromozomii parentali schimbă regiunile situate între punctele de rupere. Rețineți că pentru operatorul de încrucișare în 2 puncte, începutul și sfârșitul cromozomului sunt considerate a fi „lipite”, drept urmare unul dintre punctele de rupere poate cădea la începutul/sfârșitul cromozomilor, iar în în acest caz rezultatul încrucișării în 2 puncte va coincide cu rezultatul încrucișării în 1 punct.
Când se utilizează operatorul de încrucișare omogenă, biții cromozomilor parentali sunt moșteniți independent unul de celălalt. Pentru a face acest lucru, determinați probabilitatea p0 ca a i-a cifră a cromozomului primului părinte să ajungă la primul copil, iar al doilea părinte - la al doilea copil. Probabilitatea evenimentului opus este (1 – p0). Fiecare bit de cromozomi parentali este „reprodus” în conformitate cu valoarea p0 între cromozomii descendenților. În cele mai multe cazuri, probabilitatea ambelor evenimente este aceeași, adică p0 = 0,5.
29. Descrieți principiul de funcționare a unui crossover în două puncte pentru codare reală.
Încrucișarea în 2 puncte pentru codificare reală este practic aceeași cu crossover-ul în 2 puncte pentru codificarea întregului. Diferența este că punctul de rupere nu poate fi ales „în interiorul” genei, ci trebuie să se încadreze între gene.
30. Descrie conceptul de abilitate distructivă a unui crossover.
Operatorii crossover se caracterizează prin capacitatea de a distruge cromozomii parentali.
Încrucișarea pentru codificarea întregului este considerată mai distructivă dacă, ca urmare a aplicării sale, distanța Hamming dintre cromozomii descendenți rezultați și cromozomii părinților este mare.
Cu alte cuvinte, capacitatea unui număr întreg de trecere de a distruge depinde de cât de mult „amestecă” (recombină) conținutul cromozomilor parentali. Astfel, încrucișarea în 1 punct este considerată a fi slab distructivă, în timp ce încrucișarea omogenă este, în majoritatea cazurilor, un operator puternic distructiv. În mod corespunzător, trecerea în 2 puncte ocupă o poziție intermediară în ceea ce privește puterea distructivă în raport cu operatorii de trecere în 1 punct și omogene.
În cazul încrucișării pentru codificare reală, capacitatea de distrugere este determinată de cât de mare este distanța în spațiul de căutare dintre punctele corespunzătoare cromozomilor părinților și descendenților. Astfel, efectul distructiv al încrucișării în 2 puncte depinde de conținutul cromozomilor parentali. Capacitatea distructivă a încrucișării aritmetice depinde de valoarea parametrului l, de exemplu, pentru l >> 1 și l >> 0, capacitatea distructivă va fi scăzută. Pentru trecerea BLX-a, capacitatea distructivă depinde atât de valoarea lui a, cât și de diferența dintre valorile genelor corespunzătoare ale indivizilor parentali.
Rețineți că, alături de capacitatea de a distruge, se vorbește și de capacitatea de a crea (creație, construcție) prin trecerea peste noi indivizi. Astfel, se subliniază că, prin distrugerea cromozomilor indivizilor parentali, încrucișarea poate crea cromozomi complet noi care nu au fost întâlniți anterior în procesul de căutare evolutivă.
31. Descrieți algoritmul genetic canonic.
Algoritmul genetic canonic a fost dezvoltat de John Holland și descris în cartea sa Adaptation in Natural and Artificial Systems, 1975. Reprezintă unul dintre modelele de bază ale căutării evolutive, studiat în detaliu în anii 70-80 ai secolului XX.
GA canonic are următoarele caracteristici:
Codificare întregi;
Toți cromozomii dintr-o populație au aceeași lungime;
Dimensiunea constantă a populației;
Alegerea ruletei;
Operator de încrucișare cu un singur punct;
Mutație de biți;
O nouă generație se formează numai din indivizi descendenți (decalajul generațiilor T = 1).
32. Ce modele de reprezentare a cunoștințelor cunoașteți?
Cele mai comune modele de reprezentare a cunoștințelor în sistemele expert sunt:
model de reprezentare a cunoștințelor prin logica predicatelor de ordinul întâi;
model de producție;
model de cadru;
model de reprezentare a cunoștințelor sub forma unei rețele semantice;
model de reprezentare a cunoștințelor sub formă de buletin;
model de reprezentare a cunoștințelor sub formă de scenariu;
model de reprezentare a cunoștințelor bazat pe logica fuzzy;
modelul rețelei neuronale de reprezentare a cunoștințelor.
Modelul logic al reprezentării cunoștințelor se bazează pe logica predicatelor. Un predicat, sau o funcție logică, este o funcție a oricărui număr de argumente care ia o valoare adevărată sau falsă. Argumente ale funcției - valori dintr-un set arbitrar, finit sau infinit 
numită aria subiectului. Predica de la 
-argumentele se numește -predicat local. Modelul de reprezentare a cunoștințelor folosește logica predicatelor de ordinul întâi pe care se bazează Prolog.
34. În ce constă un sistem de producție?
Un sistem de producție este un sistem de procesare a cunoștințelor care utilizează reprezentări ale cunoștințelor prin reguli de producție. Regulile de producție sunt expresii precum „Dacă (condiție) atunci (acțiune)”. „Condiție” – un exemplu de propoziție prin care se efectuează căutarea în baza de cunoștințe; „acțiune” este acțiunea care trebuie întreprinsă atunci când căutarea are succes. Concluzia asupra unei astfel de baze de cunoștințe poate fi directă (de la date la căutarea unui scop) și inversă (de la un scop pentru a-l confirma - la date). Datele sunt faptele inițiale stocate în baza de fapte, pe baza cărora este lansat motorul de inferență sau interpretul de reguli, sortând regulile din baza de cunoștințe de producție.
Sistemul de producție include o bază de reguli, o bază de date și un interpret de reguli. Baza de reguli este o zonă de memorie care conține o bază de cunoștințe - un set de cunoștințe prezentate sub forma unor reguli de forma DACĂ ... ATUNCI; o bază de date este o zonă de memorie care conține date reale (fapte). Un interpret este un mecanism de inferență, acesta este componenta sistemului care formează concluzia folosind baza de reguli și baza de date.
35. Descrieți modelul de reprezentare a cunoștințelor sub formă de cadre
Într-un sistem de cadru, unitatea de reprezentare a cunoștințelor este un obiect numit cadru. Un cadru este o formă de reprezentare a unei anumite situații care poate fi descrisă de un anumit set de concepte și entități. Cadrul primește un nume ca identificator. Acest nume trebuie să fie unic în întregul sistem de cadre. Un cadru are o structură internă specifică, constând din multe elemente numite sloturi, cărora li se dau și nume. Fiecare slot, la rândul său, este reprezentat de o structură de date specifică. Uneori, un slot include o componentă numită fațetă care specifică un interval sau o listă de valori posibile. Fațeta specifică, de asemenea, valorile limită ale umplerii slotului (de exemplu, numărul maxim permis de frați
36. Cum este reprezentată cunoștințele în rețeaua semantică?
Rețeaua semantică reprezintă cunoașterea sub forma unui graf, ale căror noduri corespund unor fapte sau concepte, iar arcele corespund relațiilor dintre concepte. Un grafic este un set de vârfuri și un set de arce care leagă unele perechi de vârfuri. Graficul etichetat pentru fiecare vârf conține descriptori (etichete) datorită cărora vârfurile graficului diferă unele de altele. Pentru un grafic stat-spațiu, descriptorii identifică stări în procesul de rezolvare a unei probleme. Etichetele de arc în rețelele semantice sunt folosite pentru a defini relațiile numite.
37. Descrieți arhitectura sistemelor expert
Un grup de experți sau o altă sursă de expertiză asigură că faptele, observațiile și metodele de analiză a situațiilor sunt încărcate în baza de cunoștințe. Utilizatorul interoghează sistemul despre probleme specifice printr-o interfață care permite comunicarea folosind expresii normale.
Informațiile conținute în baza de cunoștințe sunt procesate de un motor de inferență care utilizează asocieri empirice sau reguli „IF...THEN” pentru a forma și testa posibile soluții. Interfața cu utilizatorul într-o formă accesibilă transmite rezultatele operatorului.
În sistemele inteligente puternice, există o interfață în limbaj natural care vă permite să puneți întrebări și să primiți răspunsuri în engleză simplă sau rusă. În cazul sistemelor inteligente convenționale, utilizatorului i se oferă o interfață mai puțin rafinată, dar totuși „prietenoasă”.
38. Descrieți funcțiile mașinii de ieșire (mecanism)
Principalul lucru în ES este mecanismul care caută baza de cunoștințe conform regulilor logicii raționale pentru a obține soluții. Acest mecanism, numit motor de inferență, este activat atunci când este primită o cerere de utilizator și efectuează următoarele sarcini:
compară informațiile conținute în cererea utilizatorului cu informațiile din baza de cunoștințe;
caută scopuri specifice sau relații cauzale;
evaluează certitudinea relativă a faptelor pe baza factorilor de încredere respectivi asociați fiecărui fapt.
39. Dați o diagramă bloc care descrie etapele tehnologiei pentru crearea sistemelor expert
La etapa de identificare se determină sarcinile de rezolvat, se identifică obiectivele de dezvoltare, resursele, experții și categoriile de utilizatori.
La etapa de achizitie a cunostintelor se disting trei strategii: dobandirea cunostintelor, extragerea cunostintelor si descoperirea cunostintelor. Dobândirea de cunoștințe este înțeleasă ca o metodă de completare automată a bazei de cunoștințe prin dialogul unui expert și a unui program special. Extragerea cunoștințelor este procedura de interacțiune între un inginer de cunoștințe și o sursă de cunoștințe (un expert, literatură de specialitate etc.) fără utilizarea tehnologiei informatice. Termenul de descoperire a cunoștințelor este asociat cu crearea de sisteme informatice care implementează metode de achiziție automată a cunoștințelor. Acum această direcție este cea mai promițătoare. În același timp, se presupune că sistemul însuși va fi capabil să dezvăluie tiparele domeniului subiectului și să formuleze cunoștințele necesare pe baza materialului empiric disponibil.
În etapa de conceptualizare se realizează o analiză a zonei problemei, se identifică conceptele utilizate și relațiile dintre acestea și se determină metode de rezolvare a problemelor.
Etapa de formalizare determină modalitățile de reprezentare a tuturor tipurilor de cunoștințe, formalizează conceptele de bază, determină modalitățile de interpretare a cunoștințelor și modelează funcționarea sistemului. În această etapă se evaluează adecvarea scopurilor sistemului de concepte fixe, metode de rezolvare, mijloace de reprezentare și manipulare a cunoștințelor.
În etapa de execuție, baza de cunoștințe a sistemului este completată. În etapa de testare, expertul (și inginerul de cunoștințe), în mod interactiv, folosind instrumente interactive și explicative, verifică competența SE. Procesul de testare continuă până când examinatorul decide că sistemul a atins nivelul de competență necesar.
În etapa de operare de probă, se verifică adecvarea ES pentru utilizatorii finali. Pe baza rezultatelor acestei etape, precum și a etapei de testare, poate fi necesară o modificare semnificativă a ES.
Procesul de creare a unui ES nu se limitează la a urma o secvență strictă a pașilor enumerați mai sus. În timpul dezvoltării, trebuie să reveniți în mod repetat la etapele anterioare și să revizuiți deciziile luate acolo.
Pagina 1 tabel de pagini pe mai multe niveluri necesită mai multe accesări la memoria principală, deci durează mult timp. În unele cazuri, o astfel de întârziere este inacceptabilă. Problema accelerarii cautarii este rezolvata la nivelul arhitecturii computerului.
Datorită proprietății localității, majoritatea programelor accesează un număr mic de pagini pentru o anumită perioadă de timp, astfel încât doar o mică parte din tabelul de pagini este utilizată în mod activ.
Soluția firească a problemei de accelerare este de a furniza un computer cu un dispozitiv hardware pentru maparea paginilor virtuale cu cele fizice fără a se face referire la tabelul de pagini, adică să aibă o memorie cache mică, rapidă, care stochează partea din tabelul de pagini care este necesar în prezent. Acest dispozitiv este numit memorie asociativă, uneori folosiți și termenul de translație de tip tampon (TLB).
O intrare în masă memorie asociativă(o intrare) conține informații despre o pagină virtuală: atributele acesteia și cadrul în care se află. Aceste câmpuri corespund exact câmpurilor din tabelul de pagini.
pentru că memorie asociativă conține doar câteva dintre intrările din tabelul de pagini, fiecare intrare din TLB trebuie să includă un câmp cu un număr pagina virtuala. Memoria se numește asociativă, deoarece compară simultan numărul celor afișate pagina virtuala cu câmpul corespunzător în toate rândurile acestui mic tabel. Prin urmare, acest tip de memorie este destul de scump. În linie, câmp pagina virtuala care a coincis cu valoarea dorită, se găsește numărul cadrului paginii. Numărul obișnuit de intrări în TLB este de la 8 la 4096. Creșterea numărului de intrări în memorie asociativă trebuie să țină cont de factori precum dimensiunea memoriei cache-ului principal și numărul de accesări la memorie per instrucțiune.
Luați în considerare funcționarea managerului de memorie în prezență memorie asociativă.
La începutul afișării informațiilor pagina virtuala in fizic se gaseste in memorie asociativă. Dacă se găsește intrarea necesară, totul este în regulă, cu excepția încălcărilor de privilegii, când cererea de acces la memorie este respinsă.
Dacă intrarea dorită în memorie asociativă absent, afișarea se face prin tabelul de pagini. Una dintre intrările din memorie asociativă a găsit intrarea din tabelul de pagini. Aici ne confruntăm cu problema tradițională de înlocuire pentru orice cache (și anume, care dintre intrările din cache trebuie schimbată). Proiecta memorie asociativă ar trebui să organizeze înregistrările în așa fel încât să se poată lua o decizie cu privire la care dintre înregistrările vechi ar trebui să fie șterse atunci când sunt adăugate altele noi.
Numărul de căutări reușite ale numerelor de pagină în memorie asociativă in raport cu numarul total de cautari se numeste rata de hit (coincidenta) (proportie, raport). Uneori este folosit și termenul de procentaj de accesări în cache. Deci, rata de accesare este partea de link-uri care poate fi făcută folosind memorie asociativă. Referirea la aceleași pagini crește rata de accesare. Cu cât este mai mare rata de accesare, cu atât timpul mediu de acces la datele din RAM este mai mic.
Să presupunem, de exemplu, că este nevoie de 100 ns pentru a determina adresa în cazul pierderii cache-ului prin tabelul de pagini și pentru a determina adresa în cazul unei accesări în cache. memorie asociativă– 20 ns. Cu un raport de accesare de 90%, timpul mediu de rezoluție a adresei este de 0,9x20+0,1x100 = 28ns.
Performanța destul de acceptabilă a sistemelor de operare moderne demonstrează eficiența utilizării memorie asociativă. Probabilitate mare de a găsi date în memorie asociativă asociate cu prezența proprietăților obiective ale datelor: localitatea spațială și temporală.
Este necesar să acordați atenție următorului fapt. Când schimbați contextul proceselor, trebuie să vă asigurați că noul proces „nu vede” în memorie asociativă informații legate de procesul anterior, cum ar fi ștergerea acestuia. Deci utilizarea memorie asociativă crește timpul de schimbare a contextului.
Considerat pe două niveluri ( memorie asociativă+ tabel de pagină ) schema de traducere a adreselor este un exemplu excelent de ierarhie a memoriei bazată pe utilizarea principiului localității, așa cum sa discutat în introducerea prelegerii anterioare.
Tabel cu pagini inversate
În ciuda organizării pe niveluri, stocarea mai multor tabele mari de pagini este încă o provocare. Valoarea sa este relevantă în special pentru arhitecturile pe 64 de biți, unde numărul de pagini virtuale este foarte mare. Soluția este folosirea tabel cu pagini inversate(tabel cu pagini inversate). Această abordare este utilizată pe mașinile PowerPC, unele stații de lucru Hewlett-Packard, IBM RT, IBM AS/400 și câteva altele.
Acest tabel conține o intrare pentru fiecare cadru de pagină din memoria fizică. Este esențial ca un singur tabel să fie suficient pentru toate procesele. Astfel, o parte fixă a memoriei principale este necesară pentru a stoca funcția de mapare, indiferent de bitness al arhitecturii, de dimensiunea și numărul de procese.
În ciuda economisirii memoriei RAM, utilizarea masa inversată are un dezavantaj semnificativ - intrările din el (ca în memorie asociativă) nu sunt sortate în ordine crescătoare a numerelor paginilor virtuale, ceea ce complică traducerea adreselor. O modalitate de a rezolva această problemă este utilizarea unui tabel hash. adrese virtuale. În același timp, parte adresa virtuală, care este numărul paginii, este mapat la un tabel hash folosind o funcție hash. Fiecare pagină de memorie fizică aici corespunde unei intrări din tabelul hash și tabel cu pagini inversate. Adrese virtuale, care au aceeași valoare hash, se concatenează între ele. De obicei, lungimea lanțului nu depășește două intrări.
Mărimea paginii
Dezvoltatorii de sisteme de operare pentru mașinile existente au rareori capacitatea de a influența dimensiunea paginii. Totuși, pentru computerele nou create, decizia privind dimensiunea optimă a paginii este relevantă. După cum v-ați aștepta, nu există cea mai bună dimensiune. Mai degrabă, există un set de factori care afectează dimensiunea. De obicei, dimensiunea paginii este o putere de doi de la 29 la 214 octeți.
Cu toate acestea, umbrela rămâne, desigur, pe raft, deoarece conștiința unei persoane care stă în pragul apartamentului său este plină de probleme complet diferite ...
În încercarea de a explica cumva acest fenomen descurajator, neurologii de la Institutul Salk pentru Studii Biologice din suburbiile San Diego (SUA, California) au efectuat o serie de experimente interesante. Institutul Salk este o organizație independentă non-profit angajată în cercetarea de bază, tratarea oamenilor și educarea viitorilor specialiști, iar acest institut poartă numele fondatorului său (1965) - imunologul Jonas Edwards Salk (1914-1995), care a câștigat cândva poliomielita. . Descoperirile sunt raportate în numărul din 20 octombrie al revistei Neuron. În linii mari, a fost posibil să arătăm pentru prima dată că creierul își amintește amenințarea cu furtuna, chiar dacă o ignorăm și lăsăm umbrela acasă.
„Pentru prima dată, când ne uităm la activitatea cerebrală a unei maimuțe rhesus, putem ghici ce știe cu adevărat animalul”, spune Thomas D. Albright, care conduce Vision Center Laboratory. Iar autorul principal al studiului, Adam Messinger, un fost student absolvent al Albright, care acum lucrează la Institutul Național de Sănătate Mintală din SUA (NIMH), compară subiectul studiului său cu cunoștințele subconștiente. Această cunoaștere rămâne cu noi chiar dacă nu este direct accesibilă conștiinței. El dă acest exemplu: „Știi că ai cunoscut-o pe soția colegului tău de muncă, deși nu-ți poți aminti chipul ei”.
Memoria umană se bazează în principal pe asocieri; când încercăm să recuperăm o informație, un obiect ne amintește de altul, care la rândul său ne amintește de un al treilea și așa mai departe... Tocmai pe această împrejurare se bazează succesele fenomenale ale deținătorilor de recorduri în memorare, de exemplu serii digitale, legând cu fiecare număr câteva obiecte mai familiare din lumea exterioară - acestea sunt așa-numitele tehnici mnemonice. Desigur, oamenii de știință în neuroștiință au încercat de mult și foarte activ să demonteze structura tuturor acestor „roți dinte” de memorie asociativă. Unii experți susțin în general că cel puțin două tipuri de memorie sunt ascunse în interiorul nostru (și cineva are până la zece varietăți, dar aceasta este mai mult o curiozitate). Prima - memoria principală - este conectată funcțional cu activitatea cortexului frontal al creierului, iar a doua, mult mai încăpătoare - se înghesuie într-o zonă specifică a creierului, numită cortexul temporal inferior (ITC). ). Acolo sunt stocate informații despre aproape toate evenimentele din viața noastră. Adevărat, urmele de memorie din cortexul temporal sunt înconjurate de zone nefuncționale ale creierului, ele sunt, parcă, înfundate. Și puteți activa, trezi această memorie, de exemplu, într-o stare de transă hipnotică cu ajutorul unor întrebări speciale de conducere.
O altă modalitate de a studia memoria asociativă (implementată de cercetătorii de la Institutul Salk) este de a antrena maimuțele rhesus conectate la dispozitive (maimuțe din genul macaci) pentru a-și aminti perechile unor simboluri. Când se afișează primul dintre simbolurile pereche amintite (de exemplu, o imagine cu nori posomorâți), maimuțelor li se oferă o alegere dintre două opțiuni, dintre care doar una este considerată corectă - cea asociată cu stimulul inițial (în acest caz, este va fi o umbrelă). Recompensa pentru alegerea corectă este o înghițitură de suc de fructe adorată de maimuțe.
„Am încercat să ne asigurăm că maimuțele nu au făcut greșeli în timpul acestor teste, dar au existat și o serie de greșeli”, explică Albright. „Și am devenit interesați de ce se întâmplă în creierul lor când maimuțele fac în mod clar o alegere greșită. în ciuda ar trebui să-și amintească relația corectă a unei perechi de simboluri.” Și astfel, în timp ce maimuțele încercau să-și amintească - adică să restabilească conexiunile asociative corecte - și făceau propria lor alegere eronată, oamenii de știință au început să observe semnale de la neurocite (celule nervoase, neuroni) în acest cortex temporal cel mai de jos al creierului. Și acum se știe deja cu siguranță că această zonă este extrem de importantă pentru procesele de recunoaștere vizuală a diferitelor structuri și, în plus, este responsabilă pentru funcționarea acestui tip particular de memorie.
După ce Albright și echipa sa au analizat tiparele activității celulelor creierului în cortexul temporal inferior, ei au ajuns la concluzia că peste 50% din neurocite active de acolo pot fi atribuite în siguranță unei noi clase speciale de neuroni, în care, conform cercetătorilor, memoria este codificat.despre conexiunile corecte ale „stimulului” si simbolul asociat acestuia.
Iar cel mai surprinzător lucru despre toată această poveste pare să fie că aceste celule cerebrale specializate au continuat să-și trimită impulsurile „corecte” chiar și atunci când maimuțele au ales simbolurile greșite. „În acest sens, celulele creierului „știu” mai multe decât dezvăluie maimuțele prin comportamentul lor”, spune Albright. Într-adevăr, în lumea reală a maimuțelor (precum și a oamenilor), ceva distrage atenția tot timpul, adică nu vă permite să vă concentrați corespunzător și vă scoate din gândurile corecte, nu vă permite să apelați la memoria adevărată. ...
Modalități de organizare a memoriei
| Nume parametru | Sens |
| Subiect articol: | Modalități de organizare a memoriei |
| Rubrica (categoria tematica) | Calculatoare |
Din punct de vedere funcțional, o memorie de orice tip constă întotdeauna dintr-o matrice de stocare care stochează informații, și blocuri auxiliare, foarte complexe, care servesc la căutare în matrice, la scriere și citire (și, dacă este necesar, la regenerare).
Matricea de stocare (MS) constă dintr-o multitudine de elemente de stocare identice (SE). Toate SE-urile sunt organizate în celule, fiecare dintre acestea fiind concepută pentru a stoca o unitate de informație sub forma unui cod binar, al cărui număr de biți este determinat de lățimea eșantionului. Modul în care este organizată memoria depinde de metodele de plasare și căutare a informațiilor în SM. Pe această bază se disting memoria de adrese, asociativă și stiva.
MEMORIA ADRESĂ
În memoria cu organizarea adresei, plasarea și căutarea informațiilor în SM se bazează pe utilizarea adresei de stocare a unității de informații, pe care o vom numi în continuare pentru concizie. cuvânt. Adresa este numărul celulei SM în care este plasat acest cuvânt. La scrierea (citirea) unui cuvânt pe SM, comanda care inițiază această operațiune trebuie să indice adresa (numărul) celulei prin care este necesar să scrieți (citiți).
Pe fig. 5.2 prezintă o structură generalizată a memoriei de adrese.
Ciclul de acces la memorie este inițializat de semnalul „Acces” care ajunge la TCU. Partea generală a ciclului de acces include recepția în RgA de pe magistrala de adrese (SHA) a adresei adresei și recepția în TCU a semnalului de control „Funcționare” indicând tipul operației solicitate (citire sau scriere) .
Citind. BAW decriptează adresa și trimite un semnal care evidențiază celula 3M specificată de adresă. În cazul general, BAS-ul poate trimite semnale și către o celulă de memorie dedicată care configurează celulele GE pentru scriere sau citire. După aceea, cuvântul scris în celulă este citit de amplificatoarele BUS și transmis către RGI. Mai mult, în memoria cu citire distructivă, informația este regenerată prin scrierea unui cuvânt din RgI prin BUZ către aceeași celulă SM. Operația de citire este finalizată prin emiterea unui cuvânt de la RGI către magistrala de informații de ieșire SHI out.
Record.În plus față de partea generală de mai sus a ciclului de acces, cuvântul scris este primit de la magistrala de intrare SHI în către RGI. Înregistrarea în sine constă în general din două operații - ștergerea celulei și înregistrarea în sine. Pentru a face acest lucru, BAS selectează și șterge mai întâi celula specificată de adresa din PrA. Ștergerea celulei SM (resetarea) se poate face în diferite moduri. În special, într-o memorie cu citire distructivă, ștergerea se poate face printr-un semnal pentru a citi un cuvânt într-o celulă atunci când BUS-ul este blocat (pentru ca informațiile să nu intre în RGI). Apoi, un cuvânt nou este scris în celula selectată.
Necesitatea operațiunii de curățare a celulei înainte de scriere, precum și operațiunea de regenerare a informațiilor în timpul citirii, este determinată de tipul de SG utilizate, metodele de control și caracteristicile structurii electronice a memoriei LSI; prin urmare, aceste operațiuni poate fi absent în memoriile semiconductoare.
TCU generează secvențele necesare de semnale de control care inițiază funcționarea nodurilor de memorie individuale. Trebuie avut în vedere faptul că TCU trebuie să fie un dispozitiv foarte complex (un fel de controler de control cu propria sa memorie cache), care oferă memoriei LSI în ansamblu proprietăți speciale de consum, cum ar fi multiport, ieșire pipeline de informații etc. .
MEMORIA ASOCIATIVA
În acest tip de memorie, căutarea informațiilor nu are loc după adresă, ci după conținutul acesteia. În acest caz, conținutul informației este de obicei înțeles nu ca încărcare semantică a cuvântului stocat în celula de memorie, ci ca conținut al GE al celulei de memorie, ᴛ.ᴇ. compoziția pe biți a cuvântului binar înregistrat. În acest caz, interogarea asociativă (funcția) este, de asemenea, un cod binar cu o anumită compoziție pe biți. Căutarea după un atribut asociativ are loc în paralel în timp pentru toate celulele SM și este o operație de comparare a conținutului biților registrului de atribut cu conținutul biților corespunzători celulelor de memorie. Pentru a organiza o astfel de căutare, toate SM-urile EP sunt echipate cu procesoare pe un singur bit, în legătură cu aceasta, în unele cazuri, acest tip de memorie este considerat un sistem multiprocesor.
Memoria de mare capacitate complet asociativă este un dispozitiv foarte scump, prin urmare, pentru a-și reduce costul, numărul procesoarelor pe un singur bit este redus la unul pe celulă de memorie. În acest caz, compararea interogării asociative cu conținutul celulelor de memorie se face secvenţial pentru cifre individuale, paralel în timp pentru toate celulele SM.
Cu cantități foarte mari de memorie pentru anumite clase de sarcini, căutarea asociativă accelerează semnificativ procesarea datelor și reduce probabilitatea unei defecțiuni a computerului. În același timp, memoriile asociative cu blocuri de circuite combinaționale corespunzătoare fac posibilă efectuarea unor operații logice destul de complexe în memorie: căutarea numărului maxim sau minim într-o matrice, căutarea cuvintelor cuprinse în anumite limite, sortarea unui tablou etc.
Trebuie remarcat faptul că o căutare asociativă poate fi implementată și într-un computer cu o memorie de adrese convențională, apelând secvențial cuvintele scrise în celulele de memorie la procesor și comparându-le cu o caracteristică asociativă (șablon). În același timp, cu cantități mari de memorie, se va petrece mult timp pentru asta. Când se utilizează memoria asociativă, este posibil, fără a citi cuvinte din RAM către procesor, să se determine numărul de cuvinte corespunzător uneia sau alteia interogări asociative într-un apel. Acest lucru permite în bazele de date mari să se implementeze foarte rapid o interogare de genul: câți rezidenți ai regiunii nu au depus o declarație de venit etc.
În unele calculatoare specializate, OP-ul sau partea sa este construită în așa fel încât să permită implementarea atât a căutării de informații asociative, cât și direcționate.
În Fig. 5.3.
Să luăm mai întâi în considerare operația numită controlul asocierii. Această operație este comună operațiunilor de citire și scriere și are, de asemenea, o valoare independentă.
O solicitare asociativă de n biți, ᴛ.ᴇ, intră în RGAP prin magistrala de informații de intrare. cifrele de la 0 la n-1 sunt completate. În același timp, codul de mască de căutare intră RgM, în timp ce al n-lea bit al RgM este setat la 0. Căutarea asociativă se efectuează numai pentru setul de biți RgAP, care corespund la 1 în RgM (biți RgAP nemascați). Este important de reținut că pentru cuvintele în care cifrele din cifre coincid cu cifrele nemascate ale PrAP, CS setează 1 în cifrele corespunzătoare ale PrCv și 0 în cifrele rămase.
Schema combinațională pentru generarea rezultatului inversării asociative a FS formează cel puțin trei semnale din cuvântul format în RgSv:
A 0 - absenta in SM a cuvintelor care satisfac atributul asociativ;
A 1 - prezența unui astfel de cuvânt;
A 2 - prezența a mai mult de un cuvânt.
Sunt posibile și alte operațiuni asupra conținutului PgSv, de exemplu, numărarea numărului de unități, ᴛ.ᴇ. numărarea cuvintelor în memorie care satisfac o interogare asociativă etc.
Formarea conținutului de RgSv și a 0 , a 1 , a 2 în funcție de conținutul RgAP, RgM, ZM se numește de obicei operația de control a asocierii.
Citind.În primul rând, asocierea este controlată pe baza RgAP.
A 0 = 1 - citirea este anulată din lipsa informațiilor solicitate;
A 1 \u003d 1 - cuvântul găsit este citit în RGI, după care este emis la ieșirea SHI;
A 2 \u003d 1 - se citește un cuvânt care are, de exemplu, cel mai mic număr dintre celulele marcate cu 1 în RgSv, după care este emis la ieșirea SHI.
Record.În primul rând, este găsită o celulă liberă (presupunem că 0 este scris în bitul ocupat al unei celule libere). Pentru a face acest lucru, controlul de asociere este efectuat la PgAP=111...10 și PgM=000...01, ᴛ.ᴇ. A n-a cifră a lui RgAP este setată la 0, iar a n-a cifră a lui RgM este setată la 1. În acest caz, celula liberă este marcată cu 1 în RgSv. Pentru înregistrare, este selectată o celulă liberă, de exemplu, cu cel mai mic număr. Conține cuvântul primit de la SHI în RGI.
Trebuie remarcat faptul că această diagramă nu prezintă blocurile BUP, BUS, BUS, care se află în dispozitive reale. În același timp, pentru a construi o memorie asociativă sunt necesare elemente de stocare care pot fi citite fără distrugere.
STACK MEMORY (MAGAZIN)
Memoria stivă, ca și memoria asociativă, nu este abordată. Memoria stivă trebuie organizată atât în hardware, cât și pe o matrice obișnuită de memorie de adrese.
În cazul unei implementări hardware, celulele de memorie stiva formează o matrice unidimensională în care celulele învecinate sunt conectate între ele prin lanțuri de biți de transmisie a cuvintelor (Fig. 5.4). În acest caz, sunt posibile două tipuri de dispozitive (a, b), ale căror principii de funcționare sunt diferite. Să luăm mai întâi în considerare structura din fig. 5.4, a.
Introducerea unui cuvânt nou primit de la SHI în se face în celula superioară (zero), în timp ce toate cuvintele înregistrate anterior (inclusiv cuvântul din celula 0) sunt mutate în jos în celulele învecinate, ale căror numere sunt încă unul. Citirea este posibilă numai din celula de memorie superioară (zero). Modul principal este citirea ϶ᴛᴏ cu ștergere. În acest caz, toate cuvintele rămase în memorie sunt mutate în celulele învecinate cu numere mai mici. Într-o astfel de memorie, se implementează următoarea regulă: ultimul intrat, primul iesit. Stivele de acest tip se numesc stive LIFO (Last In - First Out).
În unele cazuri, dispozitivele de memorie stivă oferă și operațiunea de citire simplă a unui cuvânt din celula 0 fără a-l șterge și a muta restul cuvintelor. Când folosiți stiva pentru a stoca parametrii de inițializare ai controlerelor oricăror dispozitive computerizate, de obicei este posibil să citiți conținutul oricărei celule stivei fără a o șterge, ᴛ.ᴇ. citirea conținutului nu doar celula 0.
Se spune că primul cuvânt împins pe stivă se află pe partea de jos a stivei. Se spune că ultimul cuvânt trimis (în timp) la stivă este în partea de sus a stivei. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, celula N-1 este partea de jos a stivei, iar celula 0 este partea de sus.
De obicei, stiva hardware este prevăzută cu un contor de stivă, ChSt, care arată numărul total de cuvinte stocate în memorie (CHSt = 0 - stiva este goală). Când stiva este plină, dezactivează operațiunile de scriere ulterioare.
Principiul stivei de organizare a memoriei poate fi implementat nu numai în dispozitivele special concepute în acest scop. Organizarea stivei de date este posibilă și pe memoria de adrese convențională cu acces aleatoriu (stivă de software). Pentru a organiza stiva LIFO, în acest caz, este nevoie de încă o celulă de memorie (registru), în care este întotdeauna stocată adresa vârfului stivei și care se numește în mod obișnuit indicator de stivă. De obicei, unul dintre registrele interne ale procesorului este folosit ca indicator de stivă. În plus, este necesar un software adecvat. Principiile organizării stivei de date pe memoria convențională de adrese sunt ilustrate prin diagrama din fig. 5.5.
Spre deosebire de o stivă hardware, datele plasate pe o stivă de software nu sunt mutate atunci când un număr nou este scris sau citit. Fiecare cuvânt nou este scris în celula de memorie care urmează în ordinea celui a cărui adresă este conținută în pointerul stivei. După ce este scris un cuvânt nou, indicatorul stivei este incrementat cu unu (vezi Figura 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, nu datele se deplasează pe stiva de software, ci partea de sus a stivei. Când un cuvânt este citit din stivă, procesul este invers. Cuvântul este citit din celula a cărei adresă se află în pointerul stivei, după care conținutul indicatorului stivei este decrementat cu unu.
Dacă cuvintele nou încărcate pe stivă sunt plasate în celule de memorie cu adrese crescătoare secvenţial, stiva se numeşte direct. Dacă adresele sunt în scădere consecutivă, atunci - Cu susul în jos.În cele mai multe cazuri, se utilizează o stivă inversată, ceea ce se datorează particularităților implementării hardware a contoarelor în interiorul procesorului.
Cât de convenabilă este această formă de organizare a memoriei? Privind în perspectivă, se poate observa că orice instrucțiune executată în procesor, în cazul general, trebuie să conțină un cod de operație (COP), adresa primului și celui de-al doilea operand și adresa rezultatului. Pentru a economisi memorie și a reduce timpul de execuție a unei instrucțiuni de mașină de către procesor, este de dorit să se reducă lungimea instrucțiunii. Limita pentru această reducere este lungimea comenzii neadresate, ᴛ.ᴇ. doar COP. Aceste instrucțiuni sunt posibile cu organizarea stivei de memorie, deoarece, cu aranjarea corectă a operanzilor pe stivă, este suficient să le regăsiți secvențial și să efectuați operațiunile corespunzătoare asupra lor.
Pe lângă memoria stivă de tip LIFO discutată mai sus, computerele folosesc memorii stive de alt tip care implementează regula: primul intrat - primul iesit. Stivele de acest tip sunt numite stive FIFO (First In - First Out). O astfel de memorie stivă este utilizată pe scară largă pentru organizarea diferitelor tipuri de cozi (comenzi, date, solicitări etc.). Structura generalizată a stivei hardware de tip FIFO este prezentată în fig. 5.4b.
Ca și în cazul precedent, celulele de memorie stiva formează o matrice unidimensională în care celulele învecinate sunt conectate între ele prin lanțuri de biți de transmisie de cuvinte. Introducerea unui cuvânt nou primit de la SHI în se efectuează în celula superioară (zero), după care se deplasează imediat în jos și este scris în ultima celulă goală. Dacă teancul înainte de scriere era gol, cuvântul merge imediat la celula cu numărul N-1, ᴛ.ᴇ. spre partea de jos a stivei. Citirea este posibilă numai din celula de jos numerotată N-1 (partea de jos a stivei). Modul principal este citirea ϶ᴛᴏ cu ștergere. În acest caz, toate cuvintele ulterioare (înregistrate) sunt mutate în jos în celulele învecinate, ale căror numere sunt încă unul. Când stiva este plină, contorul (CHST) interzice scrierile ulterioare în stivă.
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, spre deosebire de stiva LIFO, stiva FIFO nu mișcă partea de jos, ci cea de sus. Cuvintele scrise în stiva FIFO se deplasează treptat de sus în jos, de unde sunt citite, deoarece sunt extrem de importante, iar rata de scriere și citire este determinată de semnale de control extern și nu are legătură între ele.
Implementarea software a stivei FIFO nu este luată în considerare în această secțiune, deoarece este rar folosită în practică.
Modalități de organizare a memoriei - concept și tipuri. Clasificarea și caracteristicile categoriei „Metode de organizare a memoriei” 2017, 2018.
ÎN memorie asociativă elementele sunt selectate nu după adresă, ci după conținut. Să explicăm ultimul concept mai detaliat. Pentru memoria cu organizarea adresei a fost introdus conceptul unitate minimă adresabilă(MAE) ca o bucată de date care are o adresă individuală. Să introducem un concept similar pentru memorie asociativă, iar noi vom fi această unitate minimă de stocare în memorie asociativă apel șir de memorie asociativă(Curea). Fiecare StrAP conține două câmpuri: un câmp de etichetă și un câmp de date. O cerere de citire către memoria asociativă poate fi exprimată în cuvinte după cum urmează: selectați o linie (linii) a căror etichetă este (sunt) egală cu valoarea dată.
În special, unul dintre cele trei rezultate este posibil cu o astfel de interogare:
- există exact o linie cu eticheta dată;
- există mai multe linii cu eticheta dată;
- nu există niciun rând cu eticheta dată.
Căutarea unei înregistrări după atribut este o activitate tipică pentru accesarea bazelor de date, iar căutarea în baza de date este adesea o căutare asociativă. Pentru a efectua o astfel de căutare, trebuie să căutați prin toate intrările și să comparați eticheta dată cu eticheta fiecărei intrări. Acest lucru se poate face și atunci când se utilizează memorie adresabilă obișnuită pentru stocarea înregistrărilor (și este clar că acest lucru va necesita mult timp - proporțional cu numărul de înregistrări stocate!). Despre memorie asociativă să spunem când preluarea asociativă a datelor din memorie este suportată de hardware. Când scrieți în memoria asociativă, elementul de date este plasat în StrAP împreună cu eticheta inerentă acestui element. Pentru a face acest lucru, puteți folosi orice CUREA gratuită. Luați în considerare varietățile de organizare structurală a memoriei cache sau modalitățile de mapare a memoriei RAM la cache.
Cache complet asociativ
Schema unui cache complet asociativ este prezentată în figură (vezi figura de mai jos).
Să descriem algoritmul de funcționare a sistemului cu memorie cache. La începutul operațiunii, memoria cache este goală. Când prima comandă este executată în timpul preluării, codul acesteia, precum și câțiva octeți învecinați ai codului programului, vor fi transferați (încet) într-una dintre liniile de cache și, în același timp, în partea superioară a adresei. va fi scris pe eticheta corespunzătoare. Așa se umple linia cache.
Dacă următoarele extrageri sunt posibile din această secțiune, acestea vor fi făcute din CASH (rapid) - „CASH hit”. Dacă se dovedește că elementul necesar nu se află în cache, - „CASH miss”. În acest caz, memoria RAM este accesată (încet), iar următoarea linie de cache este umplută simultan.
Diagrama cache complet asociativă
Accesarea memoriei cache se face după cum urmează. După ce adresa de execuție este formată, biții ei înalți, care formează eticheta, sunt comparați în hardware (rapid) și simultan cu etichetele tuturor liniilor de cache. În acest caz, sunt posibile doar două situații din cele trei enumerate mai sus: fie toate comparațiile vor da un rezultat negativ (CASH miss), fie un rezultat pozitiv al comparației va fi înregistrat pentru exact un rând (CASH hit).
La citire, dacă o atingere CACHE este fixă, biții inferiori ai adresei determină poziția în linia cache din care să se selecteze octeții, iar tipul de operație determină numărul de octeți. Evident, dacă lungimea unui element de date depășește un octet, atunci sunt posibile situații când acest element (în părți) este situat în două (sau mai multe) linii de cache diferite, atunci timpul de preluare a unui astfel de element va crește. Acest lucru poate fi contracarat prin alinierea operanzilor și instrucțiunilor de-a lungul limitelor liniei cache, care este luată în considerare la dezvoltarea traducătorilor de optimizare sau la optimizarea manuală a codului.
Dacă apare o pierdere a memoriei cache și nu există linii libere în cache, trebuie să înlocuiți o linie a cache-ului cu o altă linie.
Scopul principal al strategiei de înlocuire este de a păstra în cache liniile care sunt cel mai probabil să fie accesate în viitorul apropiat și de a înlocui liniile care vor fi accesate într-un timp mai îndepărtat sau deloc. Evident, algoritmul optim va fi unul care înlocuiește linia care va fi accesată mai târziu în viitor decât orice altă linie de cache.
Din păcate, o astfel de predicție este practic irealizabilă și trebuie să apelăm la algoritmi inferiori celui optim. Indiferent de algoritmul de înlocuire utilizat, acesta trebuie implementat în hardware pentru a obține viteză mare.
Dintre numeroșii algoritmi de substituție posibili, patru sunt cei mai uzuali, considerați în ordinea descrescătoare a eficienței lor relative. Oricare dintre acestea poate fi folosit într-un cache complet asociativ.
Cel mai eficient este algoritmul de înlocuire bazat pe cea mai veche utilizare ( LRU - Cel mai puțin recent folosit ), care înlocuiește linia cache care nu a fost accesată de cel mai mult timp. Studiile au arătat că algoritmul LRU care „se uită” înapoi funcționează destul de bine în comparație cu algoritmul optim care „se uită” înainte.
Cele mai cunoscute sunt două metode de implementare hardware a acestui algoritm. În primul, un numărător este asociat cu fiecare linie de cache. Unul este adăugat la conținutul tuturor contoarelor la anumite intervale. Când se accesează un șir, contorul acestuia este resetat la zero. Astfel, cel mai mare număr va fi în contorul rândului care nu a fost accesat de cel mai mult timp, iar acest rând este primul candidat pentru înlocuire.
A doua metodă este implementată folosind o coadă, în care referințele la aceste linii sunt introduse în ordinea în care sunt completate liniile cache. De fiecare dată când un șir este accesat, referința acestuia este mutată la sfârșitul cozii. Ca urmare, primul din coadă de fiecare dată este o referință la șirul, care nu a fost accesat de cel mai mult timp. Această linie este înlocuită în primul rând.
Un alt algoritm de înlocuire posibil este algoritmul primul intrat, primul ieșit ( FIFO-First In First Out ). Aceasta înlocuiește linia care a fost cea mai lungă în cache. Algoritmul se implementează cu ușurință folosind coada discutată mai devreme, cu singura diferență că după accesarea șirului, poziția link-ului corespunzător în coadă nu se modifică.
Un alt algoritm este înlocuirea șirului cel mai puțin utilizat (LFU - Least Frequently Used). Linia din cache care a fost cel mai puțin accesată este înlocuită. Principiul poate fi pus în practică prin asocierea fiecărui rând cu un contor de lovituri, al cărui conținut se adaugă unul după fiecare lovitură. Principalul candidat pentru înlocuire este șirul al cărui numărător conține cel mai mic număr.
Cel mai simplu algoritm este o alegere arbitrară a unui șir de înlocuit. Șirul de înlocuire este ales la întâmplare. Acest lucru poate fi implementat, de exemplu, prin utilizarea unui contor al cărui conținut este incrementat cu unul cu fiecare puls de ceas, indiferent dacă a fost o lovitură sau o ratare. Valoarea din contor determină șirul care trebuie înlocuit.
Pe lângă eticheta și octeții de date, linia cache poate conține câmpuri de serviciu suplimentare, printre care, în primul rând, bitul de valabilitate V (din valid - valid) și bitul de modificare M (din modificare - modificare, modificare) ar trebui să fie remarcat. Când următoarea linie de cache este completată, V este setat la starea „validă”, iar M este setat la starea „nemodificat”. Dacă conținutul acestei linii a fost modificat în timpul execuției programului, bitul M este comutat, semnalând că la înlocuirea acestei linii, conținutul acesteia trebuie rescris în RAM. Dacă dintr-un anumit motiv s-a schimbat o copie a unui element al acestui șir stocat în altă parte (de exemplu, în RAM), bitul V este comutat. La accesarea unui astfel de șir, va fi înregistrată o pierdere de cache (în ciuda faptului că eticheta se potrivește ), iar apelul va avea loc către RAM principală. În plus, câmpul de serviciu poate conține biți care acceptă algoritmul LRU.
Estimarea volumului echipamentului
Cantitatea tipică de memorie cache într-un sistem modern este de 8 ... 1024 kb, iar lungimea liniei de cache este de 4 ... 32 de octeți. Se face o evaluare suplimentară pentru dimensiunea memoriei cache de 256 KB și lungimea liniei de 32 de octeți, ceea ce este tipic pentru sistemele cu procesoare Pentium și PentiumPro. Lungimea etichetei este de 27 de biți, iar numărul de linii din cache va fi 256K/ 32=8192. Acesta este cât de multe comparatoare digitale de coduri de 27 de biți vor fi necesare pentru a implementa structura de mai sus.
O estimare aproximativă a costului echipamentului pentru construirea unui comparator digital oferă o valoare de 10 tranzistori/bit, iar numărul total de tranzistori din blocul comparator va fi egal cu:
10*27*8192 = 2 211 840,
care este de aproximativ o ori și jumătate mai mic decât numărul total de tranzistori de pe un cip Pentium. Astfel, este clar că structura descrisă a unei memorii cache complet asociative () este realizabilă numai cu un număr mic de linii în cache, i.e. cu o cantitate mică de cache (practic nu mai mult de 32 ... 64 de linii). Un cache mai mare este construit conform unei structuri diferite.
