Mänskligt associativt minne. Associativt minne

V associativt minne element väljs inte efter adress, utan efter innehåll. Låt oss förklara det sista konceptet mer i detalj. För minne med adressorganisation introducerades konceptet lägsta adresserbar enhet(MAE) som en bit data med en individuell adress. Låt oss introducera ett liknande koncept för associativt minne, och denna minimala lagringsenhet kommer att vara associativt minne ring upp associativ minnessträng(Rem). Varje strAP innehåller två fält: ett taggfält (engelsk tagg - tagg, etikett, attribut) och ett datafält. Begäran om att läsa till det associativa minnet i ord kan uttryckas på följande sätt: välj raden (s), där (vilken) taggen är lika med det angivna värdet.

Vi noterar särskilt att med en sådan fråga är ett av tre resultat möjligt:

1. det finns exakt en rad med den givna taggen;
2. det finns flera rader med den angivna taggen;
3. det finns inga rader med den givna taggen.

Att söka efter en post efter attribut är en typisk aktivitet vid databasåtkomst, och sökning i en databas kallas ofta för en associativ sökning. För att utföra en sådan sökning måste du visa alla poster och jämföra den angivna taggen med taggen för varje post. Detta kan göras när man använder vanligt adresserbart minne för att lagra poster (och det är klart att detta kommer att ta mycket tid - i proportion till antalet lagrade poster!). Handla om associativt minne de säger när associativ datahämtning från minnet stöds av hårdvara. När man skriver till det associativa minnet placeras dataelementet i StrAP tillsammans med taggen som är inneboende i detta element. För detta kan du använda vilken gratis StraP som helst. Tänk på varianterna av den strukturella organisationen av cacheminnet eller visningsmetoder random access minne på cachen.

Helt associativ cache

Ett diagram över en helt associativ cache visas i figuren (se figur nedan).

Låt oss beskriva algoritmen för driften av systemet med cacheminne. I början av arbetet är cacheminnet tomt. När det första kommandot exekveras under samplingen, dess kod, såväl som ytterligare några intilliggande byte programkod, - kommer att överföras (långsamt) till en av cache-raderna, och samtidigt kommer den övre delen av adressen att skrivas till motsvarande tagg. Så här fylls cacheraden.

Om nästa val är möjliga från detta område kommer de att göras redan från CACHE (snabb) - "CACHE-hit". Om det visar sig så önskat föremål det finns ingen cache i cachen, - "CASH-miss". I detta fall sker åtkomst till RAM (långsamt), och samtidigt fylls nästa cache-rad.

Helt associativ cachekrets

Cachen nås på följande sätt. Efter bildandet av den verkställande adressen är dess högordningsbitar, som bildar en tagg, hårdvara (snabba) och jämförs samtidigt med taggarna för alla cache-rader. I det här fallet är endast två situationer av de tre listade tidigare möjliga: antingen kommer alla jämförelser att ge ett negativt resultat (cachemiss), eller så kommer ett positivt jämförelseresultat att registreras exakt för en rad (cacheträff).

Vid läsning, om en cacheträff registreras, bestämmer de lägre bitarna av adressen positionen i cacheraden från vilken bytes ska väljas, och typen av operation bestämmer antalet byte. Uppenbarligen, om längden på ett dataelement överstiger en byte, då situationer är möjliga när detta element (i delar) är placerat i två (eller flera) olika cache-linjer, då kommer tiden för att hämta ett sådant element att öka. Detta kan motverkas genom att justera operanderna och instruktionerna längs cachelinjernas gränser, vilket beaktas vid utveckling av optimeringsöversättare eller vid manuell optimering av koden.

Om det finns en cachemiss och det inte finns några lediga rader i CACHEN, måste du ersätta en rad i CACHEN med en annan rad.

Huvudmålet med ersättningsstrategin är att behålla de linjer i cacheminnet som mest sannolikt kommer att nås inom en snar framtid, och att ersätta de linjer som kommer att nås vid ett senare tillfälle eller inte alls. Uppenbarligen kommer den optimala algoritmen att vara den som ersätter raden som kommer att nås senare i framtiden än någon annan CACHE-rad.

Tyvärr är en sådan förutsägelse praktiskt taget orealiserbar, och man måste använda algoritmer som är sämre än den optimala. Oavsett vilken ersättningsalgoritm som används måste den implementeras i hårdvara för att uppnå hög hastighet.

Bland de många möjliga ersättningsalgoritmerna är de vanligaste fyra, betraktade i ordning efter minskande relativ effektivitet. Alla dessa kan appliceras i en helt associativ cache.

Den mest effektiva är ersättningsalgoritmen baserad på den äldsta användningen ( LRU - Minst nyligen använd ), som ersätter CACHE-raden som inte har nåtts under längst tid. Forskning har visat att algoritmen för LRU-blickande bakåt fungerar ganska bra jämfört med den optimala framåtblickande algoritmen.

De mest kända är två metoder för hårdvaruimplementering av denna algoritm. I den första är en räknare associerad med varje cache-rad. En enhet läggs till innehållet i alla räknare med jämna mellanrum. När en rad öppnas nollställs dess räknare till noll. Det största numret kommer alltså att finnas i räknaren på raden som inte har nåtts under längst tid, och denna rad är den första kandidaten för ersättning.

Den andra metoden implementeras med hjälp av en kö, där referenser till dessa rader matas in i den ordning de fyller cacheraderna. Varje gång en rad öppnas flyttas länken till den till slutet av kön. Som ett resultat är den första i kön varje gång länken till raden som inte har nåtts under längst tid. Det är denna linje som byts ut först och främst.

En annan möjlig ersättningsalgoritm är en först in, först ut ( FIFO - Först in först ut ). Här ersätts den sträng som har legat längst i cacheminnet. Algoritmen implementeras enkelt med den tidigare övervägda kön, med den enda skillnaden att efter att ha kommit åt strängen ändras inte positionen för motsvarande länk i kön.

En annan algoritm är att ersätta den minst ofta använda strängen (LFU - Least Frequently Used). Raden i CACHE-minnet ersätts med det minsta antalet åtkomster. Principen kan omsättas i praktiken genom att associera varje rad med en träffräknare, vars innehåll en etta läggs till efter varje träff. Den främsta utmanaren för ersättning är den sträng vars räknare innehåller det minsta antalet.

Den enklaste algoritmen är godtyckligt val av en sträng för ersättning. Strängen som ska ersättas väljs slumpmässigt. Detta kan implementeras till exempel med hjälp av en räknare vars innehåll ökar med en för varje klockpuls, oavsett om det var en träff eller en miss. Värdet i räknaren identifierar strängen som ska ersättas.

Förutom tagg- och databyte kan cache-raden innehålla ytterligare servicefält, bland vilka först och främst giltighetsbiten V (från giltig - giltig) och ändringsbiten M (från modifiera - ändra, modifiera) bör vara noterade. När nästa cache-rad är fylld sätts V till det "giltiga" tillståndet och M - till det "ej modifierade" tillståndet. Om innehållet i denna rad har ändrats under programmets exekvering, växlas M-biten, vilket signalerar att när denna rad byts ut, bör dess innehåll skrivas om till RAM. Om, av någon anledning, en kopia av ett element i denna sträng, lagrad på en annan plats (till exempel i RAM), har ändrats, bit V. till huvud-RAM. Dessutom kan tjänstefältet innehålla bitar som stöder LRU-algoritmen.

Utrustningsvolymuppskattning

Typisk cachestorlek in modernt system- 8 ... 1024 kbyte, och längden på cache-raden är 4 ... 32 byte. Ytterligare utvärdering görs för 256KB Cache och 32B linjelängd, vilket är typiskt för system med Pentium- och PentiumPro-processorer. I det här fallet är tagglängden 27 bitar, och antalet rader i cachen kommer att vara 256K / 32 = 8192. Detta är exakt antalet digitala komparatorer med 27 bitars koder som krävs för att implementera ovanstående struktur.

En ungefärlig uppskattning av utrustningskostnaderna för att bygga en digital komparator ger ett värde på 10 trans/bit, och det totala antalet transistorer endast i komparatorenheten kommer att vara lika med:

10*27*8192 = 2 211 840,

vilket är ungefär en och en halv gånger mindre än det totala antalet transistorer på en Pentium-kristall. Således är det tydligt att den beskrivna strukturen för ett fullt associativt CACHE-minne () är realiserbart endast med ett litet antal rader i CACHE, dvs. med en liten cachestorlek (praktiskt taget inte mer än 32 ... 64 rader). En större cache är byggd enligt en annan struktur.

sidtabell i nivå kräver flera åtkomster till huvudminnet, därför tar det mycket tid. I vissa fall är denna fördröjning oacceptabel. Problemet med att påskynda sökningen löses på datorarkitekturens nivå.

På grund av lokalitetsegenskapen kommer de flesta program åt ett litet antal sidor under en tid, så endast en liten del av sidtabellen används aktivt.

En naturlig lösning på accelerationsproblemet är att utrusta datorn med en hårdvaruenhet för att mappa virtuella sidor till fysiska utan att komma åt sidtabellen, det vill säga att ha ett litet, snabbt cacheminne som lagrar nödvändiga det här ögonblicket del av sidtabellen. Denna enhet kallas associativt minne, termen translation lookaside buffer (TLB) används också ibland.

En bordsingång in associativt minne(en ingång) innehåller information om en virtuell sida: dess attribut och ramen i vilken den finns. Dessa fält motsvarar exakt fälten i sidtabellen.

Eftersom associativt minne innehåller endast några av sidtabellsposterna, varje TLB-post måste innehålla ett fält numrerat virtuell sida... Minnet kallas associativt eftersom det samtidigt jämför numret på de visade virtuell sida med ett matchande fält på alla rader i detta lilla bord. Det är därför given syn minne är ganska dyrt. I linje, fält virtuell sida som sammanfaller med det önskade värdet, hittas sidramsnumret. Typiska TLB-poster från 8 till 4096. Ökning av antalet poster i associativt minne bör göras med hänsyn till faktorer som storleken på huvudminnescachen och antalet minnesåtkomster per instruktion.

Tänk på hur minneshanteraren fungerar i närvaro associativt minne.

Första visningsinformation virtuell sida i det fysiska söks in associativt minne... Om den nödvändiga posten hittas är allt bra, utom i fall av privilegieöverträdelse, när begäran om åtkomst till minne nekas.

Om önskad post i associativt minne saknas, visas visningen genom sidtabellen. En av inläggen i associativt minne hittade posten från sidtabellen. Här står vi inför ett ersättningsproblem, som är traditionellt för vilken cache som helst (nämligen vilken av posterna i cachen som behöver ändras). Design associativt minne bör organisera journalerna på ett sådant sätt att beslut kan fattas om vilken av de gamla journalerna som ska tas bort när nya görs.

Antal lyckade sökningar efter sidnummer i associativt minne i förhållande till det totala antalet sökningar kallas hit (match) ratio (proportion, ratio). Termen "cacheträffprocent" används också ibland. Således är träffförhållandet den del av länkarna som kan göras med hjälp av associativt minne... Att komma åt samma sidor ökar träffförhållandet. Ju högre träffförhållande, desto kortare är den genomsnittliga åtkomsttiden till data i RAM.

Anta till exempel att det tar 100 ns att bestämma adressen i händelse av en cachemiss genom sidtabellen, och för att bestämma adressen i fallet med en cache-träff associativt minne- 20 ns. Med 90 % träffförhållande är den genomsnittliga adressbestämningstiden 0,9x20 + 0,1x100 = 28 ns.

Den ganska acceptabla prestandan hos moderna operativsystem bevisar effektiviteten i användningen associativt minne... Hög sannolikhet att hitta data i associativt minne associerad med närvaron av dessa objektiva egenskaper: rumslig och tidsmässig lokalitet.

Det är nödvändigt att uppmärksamma följande faktum. När du byter kontext för processer är det nödvändigt att se till att den nya processen inte "ser" in associativt minne information relaterad till den tidigare processen, som att rensa den. Så använder associativt minneökar kontextbytetiden.

Den övervägda tvånivån ( associativt minne+ sidtabell) är adressöversättningsschemat ett lysande exempel en minneshierarki baserad på lokalitetsprincipen, som diskuterades i inledningen till föregående föreläsning.

Inverterad sidtabell

Trots den stegvisa organisationen är det fortfarande ett problem att lagra flera stora sidtabeller. Dess betydelse är särskilt relevant för 64-bitars arkitekturer, där antalet virtuella sidor är mycket stort. En lösning är att använda inverterad sidtabell(omvänd sidtabell). Detta tillvägagångssätt används på PowerPC-maskiner, vissa Hewlett-Packard-arbetsstationer, IBM RT, IBM AS / 400 och flera andra.

Den här tabellen innehåller en post för varje sidram. fysiskt minne... Det är viktigt att ett bord räcker för alla processer. Således krävs en fast del av huvudminnet för att lagra visningsfunktionen, oavsett bitarkitektur, storlek och antal processer.

Trots besparingarna i RAM, användningen av inverterad tabell har en betydande nackdel - posterna i den (som i associativt minne) sorteras inte i stigande ordning av virtuella sidnummer, vilket komplicerar översättningen av adressen. Ett sätt att lösa detta problem är att använda en hashtabell. virtuella adresser... Dessutom del virtuell adress som representerar sidnumret mappas till en hashtabell med hjälp av en hashfunktion. Varje sida med fysiskt minne här motsvarar en post i hashtabellen och inverterad sidtabell. Virtuella adresser som har samma hashvärde sammanlänkas med varandra. Vanligtvis överstiger inte kedjelängden två rekord.

Sidstorlek

OS-designers för befintliga maskiner har sällan möjlighet att påverka sidstorleken. Men för re datorer som skapas beslutet om den optimala sidstorleken är relevant. Som du kanske förväntar dig finns det ingen enskild bästa storlek. Snarare finns det en uppsättning faktorer som påverkar storleken. Normalt är sidstorleken en potens av två från 2 9 till 2 14 byte.

Associativt minne

Parameternamn	Menande
Ämnet för artikeln:	Associativt minne
Kategori (tematisk kategori)	Datorer

Sidtabell

Organisering av sidtabeller är ett av nyckelelementen i omvandlingsmekanismer från sida och segment till sida. Låt oss överväga strukturen för sidtabellen mer i detalj.

Så, en virtuell adress består av ett virtuellt sidnummer (bitar av hög ordning) och en offset (bitar av låg ordning). Det virtuella sidnumret används som ett index i sidtabellen för att hitta posten för den virtuella sidan. Från denna post i sidtabellen hittas sidramsnumret, sedan läggs offset till och den fysiska adressen bildas. Dessutom innehåller en post i sidtabellen information om sidans attribut, i synnerhet säkerhetsbitarna.

Huvudproblemet för en effektiv implementering av sidtabellen är den stora storleken på de virtuella adressutrymmena. moderna datorer, som vanligtvis bestäms av bitheten hos processorarkitekturen. De vanligaste idag är 32-bitars processorer, som gör det möjligt att skapa virtuella adressutrymmen av denna storlek på 4 GB (för 64-bitars datorer är detta värde 2 ** 64b).

Låt oss beräkna den ungefärliga storleken på sidtabellen. I ett 32-bitars adressutrymme med en sidstorlek på 4K (Intel) får vi 1M sidor, och ännu mer i 64-bitars. Den där. tabellen måste ha 1M rader (entry), och posten i raden består av flera byte. Observera att varje process behöver sin egen sidtabell (och i fallet med ett segment-sideschema, en för varje segment). Så i det här fallet måste sidtabellen vara för stor.

Visningen ska dock vara snabb. Mappningen bör vara snabb, eftersom den görs vid varje minnesåtkomst, ĸᴏᴛᴏᴩᴏᴇ händer i nästan varje maskininstruktion. Detta problem löses huvudsakligen genom implementering av associativt minne.

För att undvika den avgörande betydelsen av att ha en enorm tabell i minnet hela tiden, och bara behålla några fragment av den (detta är möjligt igen baserat på locality-egenskapen), använder många datorer en sidtabell på flera nivåer.

Betrakta ett modellexempel (Figur 10.4). Antag att en 32-bitars adress är uppdelad i ett 10-bitars Ptr1-fält, ett 10-bitars Ptr2-fält och en 12-bitars Offset. 12-bitars offset låter dig lokalisera en byte inom en 4K-sida (2 ** 12), för totalt 2 ** 20 sidor. Som framgår av fig. 9.4 1024 rader i en tabell högsta nivån med Ptr1-fältet hänvisar de till 1024 tabeller på den andra nivån, som var och en innehåller 1024 rader. Med hjälp av Ptr2-fältet pekar varje rad i tabellen på andra nivån till en specifik sida. Poängen med en sådan organisation är att undvika att behålla alla tabeller på andra nivån (och det finns 1024 av dem) i minnet hela tiden. Låt oss titta på ett exempel med runda tal. Låt oss säga att en process behöver 12M minne: 4M längst ner i minnet för kod, 4M längst ner för data och 4M längst upp i minnet för stacken. Det finns ett enormt 4Gb-12Mb utrymme mellan botten av stacken och toppen av data, ĸᴏᴛᴏᴩᴏᴇ oanvänd. För det här fallet behövs endast 1 toppnivåbord och 3 andranivåbord. Detta tillvägagångssätt generaliserar naturligtvis till tre eller flera tabellnivåer.

Överväg en av posterna i sidtabellen. Dess storlek varierar från system till system, men 32 bitar är det vanligaste fallet. Det viktigaste fältet är ramnumret. Syftet med personsökning är att lokalisera detta värde. Vidare närvarobiten, skyddsbitar (till exempel 0 - läs/skriv, 1 - skrivskyddad ...), modifieringsbitar (om de är skrivna till den) och länkbitar som hjälper till att markera lite använda sidor, bitar som möjliggör cachelagring. Observera att sidadresserna på disken inte är en del av sidtabellen.

Figur 10.4 - Ett exempel på en sidtabell på två nivåer.

Hur påverkar det minneshanterarens prestanda att ha flera nivåer? Om man antar att varje nivå är en separat tabell i minnet, kan adressöversättning kräva flera minnesåtkomster.

Antalet nivåer i sidtabellen beror på den specifika arkitekturen. Du kan ge exempel på implementering av en-nivå (DEC PDP-11), två-nivå (Intel, DEC VAX), tre-nivå (Sun SPARC, DEC Alpha) personsökning "a, såväl som personsökning" och med en ställ in antal nivåer (Motorola). MIPS R2000 RISC-processorn fungerar utan sidtabell alls. Här bör sökningen efter den önskade sidan, om denna sida inte finns i det associativa minnet, tas över av OS (den så kallade nollnivåsökningen).

Att hitta den önskade sidan i en sidtabell på flera nivåer som kräver flera åtkomster till huvudminnet på vägen att översätta en virtuell adress till en fysisk adress tar lång tid. Under ett antal omständigheter är en sådan försening oacceptabel. Detta problem hittar också sin lösning på datorarkitekturens nivå.

På grund av lokalitet länkar de flesta program till ett litet antal sidor under en tidsperiod, så bara en liten del av sidtabellen är stressad.

En naturlig lösning är att utrusta datorn med en hårdvaruenhet för att mappa virtuella sidor till fysiska utan att komma åt sidtabellen, det vill säga att ha ett litet snabbt cacheminne som lagrar den del av sidtabellen som för närvarande behövs. Denna enhet kallas vanligtvis associativt minne, ibland använder de också termen associativa register (ibland translation lookaside buffer (TLB)).

En post i tabellen i associativt minne innehåller information om en virtuell sida, dess attribut och den ram i vilken den finns. Dessa fält motsvarar exakt fälten i sidtabellen.

Kartläggning av virtuella sidor lagrade i associativt minne går snabbt, men cachen är dyr och begränsad i storlek.
Upplagt på ref.rf
Antal TLB-poster från 8 till 2048

Det är vanligt att kalla minnesassociativt, eftersom till skillnad från sidtabellen, som indexeras av virtuella sidnummer, här jämförs det virtuella sidnumret samtidigt med motsvarande fält i alla rader i denna lilla tabell. Av denna anledning är detta minne dyrt. Linjen, vars fält för den virtuella sidan sammanföll med det önskade värdet, innehåller sidramens nummer.

Låt oss överväga hur minneshanteraren fungerar i närvaro av associativt minne. Först letar den efter en virtuell sida i associativt minne. Om sidan hittas är allt bra, utom i fall av privilegieöverträdelse när begäran om åtkomst till minne avvisas.

Om sidan inte finns i associativt minne, söks den genom sidtabellen. En av sidorna i associativt minne ersätts med den hittade sidan. I tabellen är en sådan laddad sida markerad med en modifieringsbit, som kommer att tas med i beräkningen när nästa associativa minne laddas från sidtabellen.

Procentandelen gånger sidnumret finns i associativt minne kallas vanligtvis för träffförhållande. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, träffförhållande - en del av länkarna som ska göras med associativt minne. Att komma åt samma sidor ökar träffförhållandet.

Anta till exempel att 100 ns är avgörande för att komma åt sidtabellen och 20 ns för att komma åt det associativa minnet. Med 90 % träffförhållande är den genomsnittliga åtkomsttiden 0,9 * 20 + 0,1 * 100 = 28 ns.

Den ganska acceptabla prestandan hos moderna operativsystem bevisar effektiviteten av att använda associativt minne. Det höga värdet av sannolikheten för att hitta data i associativt minne är associerat med närvaron av dessa objektiva egenskaper: rumslig och tidsmässig lokalitet.

Det är nödvändigt att uppmärksamma följande faktum. När du byter processer är det nödvändigt att säkerställa att den nya processen inte ser information relaterad till den tidigare processen i det associativa minnet, till exempel för att rensa den. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, användningen av associativt minne ökar tiden för att byta sammanhang.

Associativt minne - koncept och typer. Klassificering och funktioner i kategorin "Associativt minne" 2017, 2018.

I associativa experiment bör en punkt särskilt betonas, nämligen att en nödvändig förutsättning för att identifiera en tillförlitlig associativ process är subjektets fullständiga passivitet, den maximala frånkopplingen av hans vilja och tänkande från det spontana flödet av idéer. Annars får vi istället för en associativ process en aktivt deterministisk process. Denna omständighet bör särskilt betonas av det skälet att den verkliga associativa processen i själva verket är en spontan process som äger rum utanför en persons aktivitet; det är i denna egenskap som det representerar ett av utvecklingsstadierna för minnet och en av formerna för dess manifestation. När det gäller associativt minne har vi att göra med spontant minne, en spontan mnemonisk process som inte har något att göra med godtyckligt minne. I denna mening är det associativa minnet naturligtvis närmare de ovan beskrivna primitiva formerna av minnesmanifestation än dess specifikt mänskliga former.

Spontanitet kännetecknar lika mycket det associativa minnet som nu memorering, det är fixering eller bibehållande, och minnen, alltså reproduktioner.

Ämnet är alltid under inflytande av olika intryck, och ofta uppstår eller försvinner dessa intryck oavsett hans avsikt. De försvinner dock oftast inte spårlöst. Visserligen finns dessa intryck inte kvar länge i psyket som medvetna upplevelser, men i själva ämnet orsakar de vissa personliga förändringar. Och så, på grundval av dessa förändringar, när lämpliga förhållanden uppstår, när till exempel ett av dessa intryck igen börjar agera på ämnet, reagerar den senare i enlighet med de förändringar som har inträffat i honom, det vill säga erfarenheter motsvarande denna förändring uppstår i hans medvetande. ... Det är så reproduktionen av idéer uppstår, upplevd av subjektet som en produkt av effekten av spontana intryck. Som du kan se sker reproduktionen av dessa senare också utanför subjektets aktiva, avsiktliga ingripande.

Till förmån för det faktum att det associativa minnet tydligt bör skiljas från det godtyckliga minnet bevisas också av det faktum att reproduktionen av associativa representationer alltid uppstår endast under påverkan av någon andra erfarenhet - perceptuell representation. En irriterande representation eller uppfattning är nödvändig för att en associativ representation ska uppstå. Denna omständighet karakteriserar associativt minne tillräckligt bra som en fortfarande låg, beroende form av minneshandling. V denna känsla hon är ganska nära att bli igenkänd.

Igenkännandet går, som vi redan vet, till på följande sätt: N:s uppfattning är alltid åtföljd av en känsla av förtrogenhet. Jag kände igen N., jag såg honom. Men om någon form av representation läggs till detta, till exempel såg jag N. där och där (bild av en plats) eller han var i en sådan och en hatt (bild av en hatt), då har vi redan att göra med associativt minne , det vill säga N:s uppfattning orsakar reproduktion av representationer. I denna mening består skillnaden mellan igenkänning och associativt minne endast i det faktum att i fallet med igenkänning, kommer det förflutna till liv i själva uppfattningen, utan att gå över dess gränser, medan i det associativa minnet detta förflutna inte ges i formen. av någon tidigare uppfattning, men det framstår som en bild som ges upprepade gånger, men redan i form av en representation. Nedan kommer vi att vara övertygade om att på ett högre utvecklingsstadium, för reproduktion av minnesrepresentationer, behövs inte alltid en stimulans. Det finns inte bara ofrivillig memorering, utan också frivillig återkallelse.

Sätt att organisera minnet

Parameternamn	Menande
Ämnet för artikeln:	Sätt att organisera minnet
Kategori (tematisk kategori)	Datorer

Funktionellt sett består minnet av vilken typ som helst av en lagringsmatris som lagrar information och extra, ganska komplexa block som tjänar till att söka i matrisen, skriva och läsa (och, om så krävs, för regenerering).

En lagringsuppsättning (ZM) består av många identiska lagringselement (ZE). Alla GE är organiserade i celler, som var och en är utformad för att lagra en informationsenhet i form av en binär kod, vars antal bitar bestäms av sampelbredden. Sättet att organisera minnet beror på metoderna för att placera och hämta information i ZM. På denna basis särskiljs adress, associativt och stackminne.

ADRESSMINNE

I minnet med en adressorganisation baseras placeringen och hämtningen av information i ZM på användningen av lagringsadressen för en informationsenhet, som i det följande, för korthets skull, kommer att kallas ord... Adressen är numret på 3M-cellen där detta ord finns. När du skriver (läser) ett ord till ZM, måste kommandot som initierar denna operation ange adressen (numret) för cellen där du vill skriva (läsa).

I fig. 5.2 visar den generaliserade strukturen för adressminnet.

Minnesåtkomstcykeln initieras av "åtkomst"-signalen som anländer till PCU:n. Den allmänna delen av accesscykeln inkluderar mottagning av en accessadress från adressbussen (ША) från adressbussen (ША) och mottagning av en styrsignal "Operation" i PCU:n, som indikerar typen av begärd operation (läsning eller skrivning).

Läsning. BAV:n dekrypterar adressen och skickar en signal som väljer 3M-cellen som anges av adressen. I det allmänna fallet kan BAS också skicka signaler till den dedikerade minnescellen som ställer in ZE-cellerna för att skriva eller läsa. Därefter läses ordet inskrivet i cellen av ACC-förstärkarna och sänds till RgI. Vidare, i minnet med destruktiv läsning, återskapas information genom att skriva ett ord från RgI genom BUZ i samma ZM-cell. Läsoperationen fullbordas genom att ett ord avges från RgI till utgångsinformationsbussen SHI ut.

Inspelning. Förutom ovanstående allmänna del av åtkomstcykeln mottas det skrivna ordet från ingångsbussen Shi in till Rgl. Själva posten består i allmänhet av två operationer - cellrensning och själva posten. För att göra detta väljer och rensar BAS först den cell som anges av adressen i РгА. Rengöring av ZM-cellen (inför initialtillståndet) kan göras på olika sätt. Speciellt i minnet med destruktiv läsning kan rensningen göras genom signalen att läsa ordet i cellen när BUS är blockerad (så att information inte kommer till RgI). Därefter skrivs ett nytt ord in i den valda cellen.

Behovet av operationen att rensa cellen före skrivning, såväl som i driften av att regenerera information under läsning, bestäms av typen av GE som används, kontrollmetoder, egenskaper hos den elektroniska strukturen i LSI-minnet; därför är dessa operationer kan vara frånvarande i halvledarminnen.

PCU genererar de nödvändiga sekvenserna av styrsignaler som initierar driften av individuella minnesnoder. Man bör komma ihåg att PCU:n bör vara en mycket komplex enhet (en sorts kontrollkontroller med eget cacheminne) som ger minnet LSI som helhet speciella konsumentegenskaper, såsom multiport-kapacitet, pipelined informationsleverans, etc.

ASSOCIATIVT MINNE

I denna typ av minne sker sökningen efter information inte genom adress, utan genom dess innehåll. I det här fallet är det vanligt att förstå innehållet i information inte som den semantiska belastningen av ordet som är lagrat i minnescellen, utan innehållet i ZE-minnescellen, ᴛ.ᴇ. bitvis sammansättning av inspelad binärt ord... I det här fallet är en associativ begäran (funktion) också binär kod med en viss bitvis sammansättning. Sökning med en associativ egenskap sker parallellt i tid för alla 3M-celler och är en operation för att jämföra innehållet i bitarna i funktionsregistret med innehållet i motsvarande bitar i minnesceller. För att organisera en sådan sökning är alla ZE i SM utrustade med enbitsprocessorer; därför betraktas minne av denna typ i ett antal fall som ett multiprocessorsystem.

Fullständigt associativt minne för en stor volym är en mycket dyr enhet; därför reduceras antalet enbitsprocessorer till en per minnescell för att minska kostnaderna. I detta fall utförs jämförelsen av den associativa frågan med innehållet i minnescellerna sekventiellt för individuella bitar, parallellt i tiden för alla minnesceller.

Med mycket stora mängder minne för vissa klasser av problem, snabbar associativ sökning avsevärt upp databehandlingen och minskar sannolikheten för ett datorfel. Samtidigt tillåter associativt minne med block av motsvarande kombinationskretsar att utföra ganska komplexa logiska operationer i minnet: sökning efter det maximala eller minsta antalet i en array, sökning efter ord inneslutna i vissa gränser, sortering av en array, etc.

Det bör noteras att associativ sökning också kan implementeras i en dator med vanligt adressminne genom att sekventiellt anropa ord skrivna i minnesceller till processorn och jämföra dem med någon associativ egenskap (mönster). Samtidigt, med stora mängder minne, kommer detta att ta mycket tid. När man använder associativt minne är det möjligt, utan att läsa ord från OP till processorn, i ett anrop att bestämma antalet ord som motsvarar en viss associativ fråga. Detta gör det möjligt i stora databaser att mycket snabbt implementera en fråga av typen: hur många invånare i regionen som inte har lämnat in sin inkomstdeklaration etc.

I vissa specialiserade datorer är OP eller en del av den byggd på ett sådant sätt att den låter dig implementera både associativ information och adressinformation.

Förenklat strukturplan Det associativa minnet, i vilket alla ZE i ZM är utrustade med enbitsprocessorer, visas i fig. 5.3.

Överväg först en operation som kallas föreningskontroll... Denna operation är vanlig för läs- och skrivoperationer och har också en oberoende betydelse.

En n-bit associativ begäran, ᴛ.ᴇ, skickas till RgAP via ingångsinformationsbussen. bitar från 0 till n-1 fylls. Samtidigt anländer sökmaskkoden till RgM, medan den n:te biten i RgM sätts till 0. Den associativa sökningen utförs endast för uppsättningen av bitar i RgAP, som motsvarar 1 i RgM (omaskerade delar av RgAP). Det är viktigt att notera att för ord där siffrorna i siffrorna sammanföll med de omaskerade siffrorna i PrAP, sätter KS 1 till motsvarande siffror i PrSv och 0 till de återstående siffrorna.

Kombinationsschemat för bildandet av resultatet av den associativa inversionen av FS bildar minst tre signaler från ordet som bildas i РгСв:

A 0 - frånvaron av ord i ZM som uppfyller den associativa egenskapen;

A 1 - närvaron av ett sådant ord;

A 2 - närvaro av mer än ett ord.

Andra operationer på innehållet i РгСв är också möjliga, till exempel att räkna antalet enheter, ᴛ.ᴇ. räkna ord i minnet som uppfyller en associativ fråga och liknande.

Bildning av innehållet i PrCv och a 0, a 1, a 2 av innehållet i PrAP, RgM, 3M kallas vanligtvis driften av associationskontroll.

Läsning. Först övervakas associationen av attribut i RgAP.

A 0 = 1 - avläsning avbryts på grund av bristen på nödvändig information;

A 1 = 1 - det hittade ordet läses in i RgI, varefter det skickas till SHI-outen;

A 2 = 1 - ordet läses, som har till exempel det minsta numret bland cellerna markerade med 1 i PgSv, varefter det utfärdas till SHI out.

Inspelning. Först hittas en fri cell (vi antar att 0 skrivs i den upptagna biten i en ledig cell). För detta övervakas föreningen vid РгАП = 111 ... 10 och РгМ = 000 ... 01, ᴛ.ᴇ. Den n:te biten av РгАП är satt till 0, och den n:te biten av РгМ - till 1. I detta fall markeras den fria cellen med 1 i РгСв. För inspelning, välj en tom cell, till exempel med det lägsta numret. Den registrerar ordet mottaget från SHI i RgI.

Det bör noteras att detta diagram inte visar BUP, BUS, BUZ-blocken som finns i verkliga enheter. Samtidigt, för att bygga ett associativt minne, krävs lagringselement som kan läsas utan att förstöras.

STACK MINNE (BUTIK)

Stackminne, liksom associativt minne, är adresslöst. Stackminnet måste organiseras både i hårdvara och på en vanlig array av adresserbart minne.

I fallet med en hårdvaruimplementering bildar stackminnescellerna en endimensionell array i vilken angränsande celler är anslutna till varandra genom bitkedjor för ordöverföring (fig. 5.4). I det här fallet är två typer av enheter (a, b) möjliga, vars principer är olika. Betrakta först strukturen i fig. 5.4, ​​a.

Att skriva ett nytt ord mottaget från SHI i görs till den övre (noll) cellen, medan alla tidigare skrivna ord (inklusive ordet i cell 0) flyttas ner till angränsande celler, vars nummer är en till. Läsning är endast möjlig från den övre (noll) minnescellen. Huvudläget är ϶ᴛᴏ läsning med radering. I detta fall flyttas alla andra ord i minnet uppåt, till närliggande celler med lägre siffror. I sådant minne implementeras regeln: den sista kom - den första gick... Stackar av denna typ kallas vanligtvis LIFO (Last In - First Out) stackar.

I vissa fall tillhandahåller stackminnesanordningar också operationen att helt enkelt läsa ett ord från cell 0 utan att radera det och flytta resten av orden. När du använder en stack för att memorera initialiseringsparametrarna för styrenheter för alla datorenheter, är det vanligtvis möjligt att läsa innehållet i vilken cell som helst i stacken utan att radera den, ᴛ.ᴇ. läsa innehållet i inte bara cell 0.

Det första ordet som trycks på stapeln sägs vara placerat på botten av högen... Det sista ordet som skickades (i tid) på stacken sägs vara in toppen av högen... Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, cell N-1 är botten av stacken och cell 0 är toppen.

Vanligtvis är hårdvarustacken försedd med en stackräknare, som visar det totala antalet ord lagrade i minnet (Count = 0 - stacken är tom). När stacken är full tillåter den inte ytterligare skrivningar.

Staplingsprincipen för minnesorganisation kan implementeras inte bara i specialdesignade enheter. Stackorganisation av data är också möjlig på vanligt adressminne med direktåtkomst (programstack). För att organisera LIFO-stacken behövs i detta fall ytterligare en minnescell (register), där adressen till toppen av stacken alltid lagras och som vanligtvis kallas stackpekare... Vanligtvis används ett av processorns interna register som en stackpekare. Dessutom krävs lämplig programvara. Principerna för att stapla data i vanligt adressminne illustreras av diagrammet i fig. 5.5.

Till skillnad från hårdvarustacken, flyttas inte data som finns på mjukvarustacken när ett nytt nummer skrivs eller läses. Varje nytt ord skrivs till nästa minnesplats i ordning efter det som finns i stackpekaren. Efter att ha skrivit ett nytt ord, ökas innehållet i stackpekaren med ett (se figur 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, det är inte data som flyttas i programstacken, utan toppen av stacken. När ett ord läses från stapeln sker den omvända processen. Ordet läses från cellen vars adress finns i stackpekaren, varefter stackpekarens innehåll minskas med ett.

Om de nyladdade orden i stacken finns i minnesceller med sekventiellt ökande adresser, anropas stacken direkt. Om adresserna minskar sekventiellt, då - omvänd. I de flesta fall används en inverterad stack, som är förknippad med särdragen i hårdvaruimplementeringen av räknare inuti processorn.

Varför är denna form av minnesorganisation bekväm? När man ser framåt kan det noteras att varje instruktion som exekveras i processorn, i det allmänna fallet, måste innehålla en operationskod (CPC), adressen för den första och andra operanden och adressen för inmatning av resultatet. För att spara minne och minska exekveringstiden för en maskininstruktion av processorn är det önskvärt att minska instruktionslängden. Gränsen för denna minskning är längden på det oadresserade kommandot, ᴛ.ᴇ. bara en COP. Det är just sådana instruktioner som är möjliga med stackorganisationen av minnet, eftersom med korrekt arrangemang av operanderna i stacken räcker det att sekventiellt hämta dem och utföra motsvarande operationer på dem.

Förutom LIFO-stackminnet som diskuterats ovan använder datorer stackminnen av en annan typ som implementerar regeln: först kom - först kvar... Stackar av denna typ kallas vanligtvis för FIFO-stackar (First In - First Out). Ett sådant stackminne används i stor utsträckning för att organisera olika typer av köer (kommandon, data, förfrågningar, etc.). Den generaliserade strukturen för en hårdvarustapel av FIFO-typ visas i fig. 5.4, ​​b.

Liksom i det föregående fallet bildar stackminnesceller en endimensionell array i vilken angränsande celler är anslutna till varandra genom bitordsöverföringskedjor. Inspelning av ett nytt ord mottaget från SHI i utförs i den övre (noll) cellen, varefter det omedelbart flyttas ner och registreras i den sista ofyllda cellen. Om stapeln innan skrivning var tom, går ordet omedelbart till cellen med siffran N-1, ᴛ.ᴇ. till botten av högen. Avläsning är endast möjlig från den nedre cellen numrerad N-1 (nederst i stapeln). Huvudläget är ϶ᴛᴏ läsning med radering. I det här fallet flyttas alla efterföljande (skrivna) ord ner till intilliggande celler, vars nummer är ett till. När stacken är full, förbjuder räknaren (Count) ytterligare skrivoperationer på stacken.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, till skillnad från en LIFO-stack flyttar en FIFO-stack inte botten, utan toppen. Orden som skrivs till FIFO-stacken rör sig gradvis uppifrån och ner, varifrån de läses som extremt viktiga, och skriv- och läsningshastigheten bestäms av externa styrsignaler och är inte relaterade till varandra.

Mjukvaruimplementeringen av FIFO-stacken beaktas inte i detta avsnitt, eftersom den sällan används i praktiken.

Sätt att organisera minnet - koncept och typer. Klassificering och funktioner i kategorin "Sätt att organisera minnet" 2017, 2018.