IN associatief geheugen elementen worden niet op adres geselecteerd, maar op inhoud. Laten we het laatste concept nader toelichten. Voor geheugen met adresorganisatie werd het concept geïntroduceerd minimaal adresseerbare eenheid(MAE) als een gegevensbestand met een individueel adres. Laten we een soortgelijk concept introduceren voor associatief geheugen, en we hebben deze minimale opslagruimte binnen associatief geheugen telefoongesprek associatieve geheugenreeks(Riem). Elke StrAP bevat twee velden: een tagveld (Engelse tag - label, label, attribuut) en een gegevensveld. Een leesverzoek aan het associatieve geheugen kan als volgt in woorden worden uitgedrukt: selecteer de regel(s) waarvan de tag(s) gelijk is aan de opgegeven waarde.
We merken vooral op dat bij een dergelijk verzoek een van de volgende drie resultaten mogelijk is:
- er is precies één regel met de gegeven tag;
- er zijn verschillende regels met een bepaalde tag;
- er zijn geen regels met de opgegeven tag.
Zoeken naar een record op attribuut is een handeling die typisch is voor het benaderen van databases, en het doorzoeken van een database wordt vaak associatief zoeken genoemd. Om een dergelijke zoekopdracht uit te voeren, moet u alle vermeldingen bekijken en de gegeven tag vergelijken met de tag van elke vermelding. Dit kan ook worden gedaan als u gewoon adresseerbaar geheugen gebruikt om records op te slaan (en het is duidelijk dat dit behoorlijk wat tijd zal vergen - evenredig aan het aantal opgeslagen records!). Over associatief geheugen ze zeggen dat het associatief ophalen van gegevens uit het geheugen wordt ondersteund door hardware. Bij het schrijven naar het associatieve geheugen wordt een data-element in de StrAP geplaatst, samen met de tag die inherent is aan dit element. Om dit te doen, kunt u elke gratis StrAP gebruiken. Laten we naar de variëteiten kijken structurele organisatie Cachegeheugen of methoden om RAM aan cache toe te wijzen.
Volledig associatieve cache
Het diagram van een volledig associatieve cache wordt weergegeven in de figuur (zie onderstaande figuur).
Laten we het algoritme beschrijven voor het besturen van een systeem met cachegeheugen. Aan het begin van de werking is het cachegeheugen leeg. Wanneer de eerste instructie wordt uitgevoerd tijdens het ophalen, wordt de code ervan, evenals nog een aantal aangrenzende bytes van programmacode, (langzaam) overgedragen naar een van de cacheregels, en tegelijkertijd wordt het hoge deel van het adres geschreven. naar het bijbehorende label. Zo wordt de cacheregel gevuld.
Als er vanuit dit gebied verdere selecties mogelijk zijn, worden deze gemaakt vanuit de cache (snel) - "CACHE hit". Als blijkt dat het vereiste element niet in de cache staat, is er sprake van een “CACHE miss”. In dit geval vindt toegang tot RAM (langzaam) plaats en wordt tegelijkertijd de volgende cacheregel gevuld.
Volledig associatief cachegeheugencircuit
De cache is als volgt toegankelijk. Nadat het uitvoeringsadres is gevormd, worden de belangrijkste bits, die de tag vormen, hardwarematig (snel) en gelijktijdig met de tags van alle cachelijnen vergeleken. In dit geval zijn slechts twee van de drie eerder genoemde situaties mogelijk: óf alle vergelijkingen zullen een negatief resultaat opleveren (CACH-misser), óf er wordt een positief vergelijkingsresultaat geregistreerd voor precies één rij (CACH-treffer).
Als bij het lezen een cachetreffer wordt gedetecteerd, bepalen de bits van lage orde van het adres de positie in de cacheregel waaruit bytes moeten worden opgehaald, en bepaalt het type bewerking het aantal bytes. Als de lengte van een data-element groter is dan één byte, zijn er uiteraard situaties mogelijk waarin dit element (in delen) zich in twee (of meer) verschillende cacheregels bevindt, en dan zal de tijd om een dergelijk element op te halen toenemen. Dit kan worden tegengegaan door operanden en instructies uit te lijnen langs de grenzen van cacheregels, waarmee rekening wordt gehouden bij het ontwikkelen van optimaliserende vertalers of bij het handmatig optimaliseren van code.
Als er een cachemisser optreedt en er geen vrije regels in de cache zijn, moet u de ene cacheregel vervangen door een andere.
Het belangrijkste doel van de vervangingsstrategie is het behouden van cacheregels waarvan de kans het grootst is dat ze in de nabije toekomst zullen worden gebruikt, en het vervangen van regels die later of helemaal niet toegankelijk zullen zijn. Het is duidelijk dat het optimale algoritme er een is die de regel vervangt die later in de toekomst toegankelijk zal zijn dan welke andere cacheregel dan ook.
Helaas is een dergelijke voorspelling praktisch onmogelijk en is het noodzakelijk om algoritmen te gebruiken die inferieur zijn aan de optimale. Ongeacht het gebruikte vervangingsalgoritme moet het in hardware worden geïmplementeerd om hoge snelheid te bereiken.
Van de vele mogelijke vervangingsalgoritmen zijn er vier de meest voorkomende, gerangschikt in volgorde van afnemende relatieve effectiviteit. Elk van deze kan worden gebruikt in een volledig associatieve cache.
Het meest efficiënte vervangingsalgoritme is gebaseerd op het oudste gebruik ( LRU - Minst recent gebruikt ), waarin de cacheregel die het langst niet is gebruikt, wordt vervangen. Studies hebben aangetoond dat het achterwaarts gerichte LRU-algoritme vrij goed presteert in vergelijking met het optimale toekomstgerichte algoritme.
De meest bekende zijn twee methoden voor hardware-implementatie van dit algoritme. In de eerste is aan elke cacheregel een teller gekoppeld. Op bepaalde tijdstippen wordt aan de inhoud van alle tellers een eenheid toegevoegd. Wanneer een rij wordt benaderd, wordt de teller ervan op nul gezet. Dus, grootste aantal komt in de teller te staan van de lijn die het langst niet is gebruikt en deze lijn is de eerste kandidaat voor vervanging.
De tweede methode wordt geïmplementeerd met behulp van een wachtrij, waarbij verwijzingen naar deze regels worden ingevoerd in de volgorde waarin cachegeheugenregels worden gevuld. Elke keer dat een rij wordt geopend, wordt de verwijzing ernaar naar het einde van de wachtrij verplaatst. Hierdoor is de eerste in de wachtrij telkens een link naar de lijn die het langst niet is bezocht. Het is deze lijn die als eerste wordt vervangen.
Een ander mogelijk vervangingsalgoritme is een first-in, first-out-algoritme ( FIFO - Eerst in, eerst uit ). Hier wordt de regel vervangen die het langst in het cachegeheugen heeft gestaan. Het algoritme kan eenvoudig worden geïmplementeerd met behulp van de eerder besproken wachtrij, met als enige verschil dat na toegang tot een string de positie van de corresponderende link in de wachtrij niet verandert.
Een ander algoritme vervangt de minst vaak gebruikte string (LFU - Least Frequently Used). De regel in het cachegeheugen die de minste toegang heeft gehad, wordt vervangen. Het principe kan in de praktijk worden gebracht door elke regel te associëren met een trefferteller, aan de inhoud waarvan er na elke treffer één wordt toegevoegd. De belangrijkste kandidaat voor vervanging is de string waarvan de teller het kleinste getal bevat.
Het eenvoudigste algoritme is om willekeurig een string te selecteren om te vervangen. De te vervangen string wordt willekeurig gekozen. Dit kan bijvoorbeeld worden gerealiseerd met behulp van een teller, waarvan de inhoud bij elke klokpuls met één toeneemt, ongeacht of er sprake is van een treffer of een misser. De waarde in de teller bepaalt welke string moet worden vervangen.
Naast de tag- en databytes kan de cacheregel aanvullende servicevelden bevatten, waaronder allereerst het geldigheidsbit V (van geldig) en het wijzigingsbit M (van wijzigen - wijzigen, wijzigen) moeten worden genoteerd. Wanneer de volgende cacheregel gevuld is, wordt V ingesteld op de status "geldig" en wordt M ingesteld op de status "niet gewijzigd". Als de inhoud van deze regel tijdens de uitvoering van het programma wordt gewijzigd, schakelt de M-bit om, wat aangeeft dat bij het vervangen van deze regel de inhoud ervan in het RAM moet worden herschreven. Als er om de een of andere reden een wijziging optreedt in een kopie van een element van deze regel die op een andere locatie is opgeslagen (bijvoorbeeld in RAM), wordt bit V omgeschakeld. Bij toegang tot een dergelijke regel wordt een cachemisser geregistreerd (ondanks het feit dat de tag komt overeen) en de toegang zal plaatsvinden tot het hoofd-RAM. Bovendien kan het serviceveld bits bevatten die het LRU-algoritme ondersteunen.
Schatting van het apparatuurvolume
Typische cachegeheugengrootte in modern systeem- 8...1024 kbytes, en de lengte van de cacheregel is 4...32 bytes. Verdere evaluatie is gemaakt voor een cachegrootte van 256 KB en een lijnlengte van 32 bytes, wat typisch is voor systemen met Pentium- en PentiumPro-processors. De taglengte is 27 bits en het aantal regels in de cache is 256K/32=8192. Dit is precies hoeveel digitale vergelijkers van 27-bits codes nodig zullen zijn om de hierboven beschreven structuur te implementeren.
Een geschatte schatting van de apparatuurkosten voor het bouwen van een digitale comparator geeft een waarde van 10 trans/bit, en het totale aantal transistors in het comparatorblok alleen zal gelijk zijn aan:
10*27*8192 = 2 211 840,
dat is ongeveer anderhalf keer minder dan het totale aantal transistors op een Pentium-chip. Het is dus duidelijk dat de beschreven structuur van een volledig associatief cachegeheugen () alleen implementeerbaar is met een klein aantal regels in de cache, d.w.z. met een kleine cachegrootte (praktisch niet meer dan 32...64 regels). Grotere caches worden gebouwd met een andere structuur.
Waarom zien we een constante toename in de prestaties van single-threaded programma's? Op dit moment bevinden we ons in het ontwikkelingsstadium van microprocessortechnologieën waarin de toename van de snelheid van single-threaded applicaties alleen afhankelijk is van het geheugen. Het aantal cores groeit, maar de frequentie ligt vast op 4 GHz en zorgt niet voor prestatieverbetering.
De snelheid en frequentie van de geheugenwerking is het belangrijkste waardoor we “ons stukje gratis taart” krijgen (link). Daarom is het belangrijk om het geheugen zo efficiënt mogelijk te gebruiken, en vooral zo snel als een cache. Om een programma voor een specifieke computer te optimaliseren, is het handig om de kenmerken van de processorcache te kennen: aantal niveaus, grootte, regellengte. Dit is vooral belangrijk bij krachtige code: systeemkernels, wiskundige bibliotheken.
Hoe bepaal ik de kenmerken van een automatische cache? (uiteraard wordt cpuinfo niet als geparseerd beschouwd, al was het maar omdat we uiteindelijk graag een algoritme zouden willen hebben dat gemakkelijk in andere besturingssystemen kan worden geïmplementeerd. Handig, nietwaar?) Dit is precies wat we nu gaan doen.
Een beetje theorie
Momenteel zijn er drie typen cachegeheugen die veel worden gebruikt: direct-mapped cache, associatieve cache en multi-associatieve cache.Directe mapping-cache
- een bepaalde RAM-regel kan worden toegewezen aan een enkele cacheregel, maar er kunnen veel mogelijke RAM-lijnen worden toegewezen aan elke cacheregel.Volledig associatieve cache
- elke RAM-lijn kan worden toegewezen aan elke cachelijn.Multi-associatieve cache
- Het cachegeheugen is verdeeld in verschillende "banken", die elk functioneren als een direct-mapped cache, zodat een RAM-regel kan worden toegewezen aan geen enkele mogelijke cache-ingang (zoals het geval zou zijn in een direct-mapped geval ), maar aan een van de vele banken; Bankselectie wordt uitgevoerd op basis van LRU of een ander mechanisme voor elke regel die in de cache wordt geplaatst.LRU - uitzetting van de "langst ongebruikte" regel, geheugencache.
Idee
Om het aantal cacheniveaus te bepalen, moet u rekening houden met de volgorde van geheugentoegang waarin de overgang duidelijk zichtbaar zal zijn. Verschillende cacheniveaus verschillen voornamelijk in de reactiesnelheid van het geheugen. In het geval van een cachemisser zoekt de L1-cache naar gegevens in de volgende geheugenniveaus, en als de gegevensgrootte groter is dan L1 en kleiner dan L2, dan is de geheugenreactiesnelheid de L2-reactiesnelheid. De voorgaande bewering geldt ook in algemene gevallen.Het is duidelijk dat we een test moeten selecteren waarbij we duidelijk cache-missers zullen zien en deze zullen testen verschillende maten gegevens.
Als je de logica kent van set-associatieve caches die werken met behulp van het LRU-algoritme, is het niet moeilijk om een algoritme te bedenken waarin de cache "valt", niets lastigs - door de lijn gaat. We zullen het efficiëntiecriterium beschouwen als de tijd van één geheugentoegang. Uiteraard moet u achtereenvolgens toegang krijgen tot alle elementen van de lijn, en dit vele malen herhalen om het resultaat te middelen. Er kunnen bijvoorbeeld gevallen zijn waarin een regel in de cache past, maar voor de eerste keer laden we de regel vanuit het RAM en krijgen daarom een volkomen ontoereikende tijd.
Ik zou graag iets zien dat lijkt op stappen, waarbij je langs lijnen van verschillende lengte loopt. Om de aard van de stappen te bepalen, beschouwen we een voorbeeld van een regeldoorgang voor een directe en associatieve cache; het geval met een set-associatieve cache zal een gemiddelde zijn tussen een direct toegewezen cache en een associatieve cache.
Associatieve cache
Zodra de gegevensgrootte de cachegrootte overschrijdt,
Een volledig associatieve cache mist elke geheugentoegang.
Directe cache
Laten we eens overwegen verschillende maten lijnen. - toont maximale hoeveelheid mist, waardoor de CPU wordt verspild om toegang te krijgen tot de array-elementen de volgende keer dat deze de lijn passeert.
Zoals u kunt zien, neemt de toegangstijd tot het geheugen niet sterk toe, maar naarmate het gegevensvolume toeneemt. Zodra de gegevensgrootte de cachegrootte overschrijdt, zullen er fouten optreden bij elke geheugentoegang.
Daarom zal de stap voor een associatieve cache verticaal zijn, terwijl deze voor een directe cache geleidelijk zal toenemen tot het dubbele van de cachegrootte. Een multi-associatieve cache zal een gemiddeld geval zijn, een “bump”, al was het maar omdat de toegangstijd niet beter kan zijn dan een directe.
Als we het over geheugen hebben, dan is de cache de snelste, gevolgd door het operationele geheugen, de langzaamste is de swap, we zullen er in de toekomst niet over praten. Op zijn beurt, verschillende niveaus cache (meestal hebben processors tegenwoordig 2-3 cacheniveaus) verschillende snelheid geheugenreactie: hoe hoger het niveau, hoe langzamer de reactiesnelheid. En daarom, als een regel in de cache van het eerste niveau wordt geplaatst (die overigens volledig associatief is), zal de responstijd korter zijn dan voor een regel die aanzienlijk groter is dan de grootte van de cache van het eerste niveau. Daarom zullen er in de grafiek van de geheugenresponstijd versus de lijngrootte verschillende plateaus zijn: een plateau* van de geheugenrespons, en plateaus veroorzaakt door verschillende cacheniveaus.
*Functieplateau - ( i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Laten we beginnen met de implementatie
Voor implementatie zullen we C (ANSI C99) gebruiken.De code werd snel geschreven, waarbij de gebruikelijke passage door regels van verschillende lengte, minder dan 10 MB, vele malen werd uitgevoerd. (We zullen kleine stukjes van het programma presenteren die een semantische lading hebben).
Voor (i = 0; ik< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
We kijken naar de grafiek en zien één grote stap. Maar in theorie komt alles prima uit. Daarom moet je begrijpen: waarom gebeurt dit? En hoe dit te verhelpen?
Dit kan uiteraard om twee redenen gebeuren: ofwel heeft de processor geen geheugencache, ofwel is de processor zo goed in het raden van geheugentoegang. Omdat de eerste optie dichter bij sciencefiction ligt, is de reden voor alles een goede voorspelling van oproepen.
Het feit is dat zij tegenwoordig verre van topverwerkers zijn, maar naast het principe van ruimtelijke lokaliteit ook voorspellen rekenkundige progressie in volgorde van geheugentoegang. Daarom is het noodzakelijk om geheugentoegang willekeurig te maken.
De lengte van de gerandomiseerde array moet vergelijkbaar zijn met de lengte van de hoofdreeks om de grote granulariteit van oproepen weg te nemen, en de lengte van de array mag geen macht van twee zijn, hierdoor zijn er "overlappingen" opgetreden - wat tot uitschieters zou kunnen leiden. Het is het beste om de granulariteit constant in te stellen, ook als de granulariteit een priemgetal is, kunt u de effecten van overlays vermijden. En de lengte van een gerandomiseerde array is een functie van de lengte van de string.
voor (i = 0; ik< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Waarna we de langverwachte ‘foto’ verrasten waar we het in het begin over hadden.
Het programma is verdeeld in 2 delen: testen en gegevensverwerking. Het is aan jou om te beslissen of je een script in 3 regels schrijft om het uit te voeren of het 2 keer handmatig uit te voeren.
Het size.file weergeven op Linux
#erbij betrekken
Lijst met bestandsgrootte.van Windows
#erbij betrekken
anders k += 4*1024;
) retourneer 0; )
Over het algemeen denk ik dat alles duidelijk is, maar ik zou graag een paar punten willen verduidelijken.
Array A wordt als vluchtig verklaard - deze richtlijn garandeert ons dat er altijd toegang zal worden verkregen tot array A, dat wil zeggen dat ze niet zullen worden "uitgesneden" door de optimalisatie of de compiler. Het is ook vermeldenswaard dat de volledige rekenlast wordt uitgevoerd voordat de tijd wordt gemeten, waardoor we de achtergrondinvloed kunnen verminderen.
Het bestand wordt vertaald naar assembler op Ubuntu 12.04 en de gcc 4.6-compiler - de cycli worden opgeslagen.Gegevensverwerking
Het is logisch om derivaten te gebruiken om gegevens te verwerken. En ondanks het feit dat ruis toeneemt met toenemende differentiatievolgorde, zullen de tweede afgeleide en zijn eigenschappen worden gebruikt. Hoe luidruchtig de tweede afgeleide ook is, we zijn alleen geïnteresseerd in het teken van de tweede afgeleide.
We vinden alle punten waarop de tweede afgeleide groter is dan nul (met enige fout omdat de tweede afgeleide niet alleen numeriek wordt berekend, maar ook erg luidruchtig is). We stellen de functie in afhankelijk van het teken van de tweede afgeleide van de functie op de cachegrootte. De functie neemt de waarde 1 aan op punten waar het teken van de tweede afgeleide groter is dan nul, en nul als het teken van de tweede afgeleide kleiner dan of gelijk aan nul is.
#erbij betrekken
dubbele ronde (dubbele x) ( int mul = 100; if (x > 0) return floor(x * mul + .5) / mul; else return ceil(x * mul - .5) / mul; ) float size, tijd , der_1, der_2; int main())( grootte = 0; tijd = 0; der_1 = 0; der_2 = 0; int i, z = 110; for (i = 1; ik
2) der_2[i] = 1;
anders der_2[i] = 0;// kam voor (i = 0; i
Testen
Voor elke test worden CPU/OS/kernelversie/compiler/compilatiesleutels aangegeven.- Intel Pentium CPU P6100 @2,00GHz / Ubuntu 12.04 / 3.2.0-27-generiek / gcc -Wall -O3 size.c -lrt L1 = 0,05 MB L2 = 0,2 MB
L3 = 2,7 MB
Ik zal niet alles opsommenHet probleem ligt in het kleine aantal punten dat binnen het interval valt om het plateau te bereiken; de sprong in de tweede afgeleide is dan ook onmerkbaar en wordt als ruis beschouwd.
U kunt dit probleem oplossen met behulp van de methode kleinste kwadraten of voer tests uit terwijl u plateauzones identificeert.
Ik zou graag uw suggesties willen horen om dit probleem op te lossen.
Referenties
- Makarov AV Computerarchitectuur en programmeren op laag niveau.
- Ulrich Drepper Wat elke programmeur moet weten over geheugen
CACHE-niveaus.
Meestal heeft de microprocessor dat wel verschillende cacheniveaus-A(processor cachegeheugen, cache). Eerst ( L1 & L1i(cache voor instructies)), seconde ( L2) en derde ( L3) (er zijn er meer over serveroplossingen).
Hoe lager op cacherang, hoe langzamer de snelheid zijn werk.
Eerste niveau werkt meestal op processorfrequentie en heeft de breedste band, maar ook het kleinste volume. Serveert voor het adresseren van commando's En instructies, maar niet hun tijdelijke opslag.
Tweede en derde niveaus CACHE-en dienen voor waarden registreren berekeningen en voor officiële informatie, gebruikt vaker op dit moment. Heeft meerdere keren B O groter volume dan de cache van het eerste niveau, maar ook in n meerdere malen kleinere band, Wat negatief beïnvloedt bandbreedte.
Cache gebeurt gedeeld(per kern) en algemeen(gecombineerd).
Ongetwijfeld gedeelde cache werken sneller. Sinds verdeeld cache, als één kern informatie nodig heeft die voorheen aanwezig was berekend door een andere kernel en zit in de zijne CACHE, dan zal het door veel langzamer RAM moeten gaan. Soms is het sneller om opnieuw te tellen, wat de processor doet. En in het geval van algemeen cache, kon gewoon gegevens nemen van gedeelde cache.
Een verwerker bijvoorbeeld Intel C2Dq9550 bestaat uit twee Intel C2D E8400.
Vier cores zullen niet alleen langzamer zijn vanwege het gebruik van gedeelde busbronnen. L2-cache is nu niet gebruikelijk en hij moet bijvoorbeeld op zoek gaan naar oplossingen kern 1 benodigde verwerkte informatie kern 3. Dit verhoogt de tijd informatieverwerking, waardoor de prestaties afnemen.
Cache-geheugen genaamd volledig associatief, als elke regel RAM kan overal worden geplaatst cache-geheugen.
In een volledig associatief cache-geheugen gebruikt het volledige volume maximaal: repressie informatie die in de CP is opgeslagen, wordt pas uitgevoerd nadat deze volledig is ingevuld. Echter zoekopdracht V cache-Op deze manier georganiseerd geheugen is een moeilijke taak.
Een compromis tussen deze twee manieren van organiseren cache-dient het geheugen meervoudig associatief CP, waarin elke regel RAM kan op een beperkt aantal plaatsen worden gevestigd cache-geheugen.
Vervang indien nodig de informatie in cache-een nieuw geheugen wordt meerdere keren gebruikt vervangingsstrategieën. De bekendste onder hen zijn:
1. LRU- de lijn die het langst niet is gebruikt, wordt vervangen;
2. FIFO - de oudste regel in het cachegeheugen wordt vervangen;
3. Willekeurig - vervanging vindt willekeurig plaats.
De laatste optie, aanzienlijk besparend hardware vergeleken met andere benaderingen biedt het in sommige gevallen meer efficiënt gebruik cache-geheugen. Stel bijvoorbeeld dat de CP een lengte heeft van 4 regels, en dat een cyclisch gedeelte van het programma een lengte heeft van 5 regels. In dit geval met strategieën LRU en FIFO cache-geheugen zal door het gebrek vrijwel nutteloos zijn cache-hits. Tegelijkertijd zullen bij het gebruik van de strategie van willekeurige informatievervanging enkele oproepen naar de CP leiden cache- treffers.
Correspondentie tussen gegevens in RAM en in cache-geheugen wordt geleverd door wijzigingen in die gebieden aan te brengen RAM, waarvoor de gegevens in cache-herinneringen hebben veranderingen ondergaan. Er zijn twee manieren om deze acties te implementeren: writethrough en write-back.
Bij het lezen werken beide methoden identiek. Bij het opnemen doorschrijfcache updates hoofdgeheugen parallel met het bijwerken van informatie in de CP. Dit vermindert enigszins prestatie systemen, sinds microprocessor Vervolgens kunt u opnieuw contact opnemen met hetzelfde adres om informatie op te nemen, en de vorige doorschakeling van de lijn cache-geheugen erin RAM zal nutteloos blijken te zijn. Bij deze aanpak blijft echter de inhoud van de overeenkomstige rijen behouden RAM en de CP is altijd identiek. Dit speelt een grote rol bij multiprocessors systemen met gemeenschappelijke RAM.
Caching voor terugschrijven wijzigt een string RAM alleen wanneer repressie lijnen cache-geheugen, bijvoorbeeld als het nodig is om ruimte vrij te maken om een nieuwe regel te schrijven RAM naar de reeds gevulde CP. Operaties terugschrijvingen worden ook geïnitieerd door het consistentiemechanisme cache-geheugen bij gebruik van een multiprocessorsysteem met gedeeld RAM.
Een tussenpositie tussen deze benaderingen wordt ingenomen door een methode waarbij alle strings die bedoeld zijn voor verzending van de CP naar RAM, worden vooraf geaccumuleerd in een bepaalde buffer. De overdracht wordt op elk gewenst moment uitgevoerd repressie lijnen, zoals in terugschrijfcache, of indien nodig goedkeuring cache-geheugen van meerdere microprocessors in een multiprocessorsysteem, of wanneer de buffer vol is. Deze overdracht wordt in batchmodus uitgevoerd, wat efficiënter is dan het overbrengen van een enkele lijn.
11. Microprocessor (MP). Definitie. Functies uitgevoerd. Basisparameters. Typen MP afhankelijk van de set commandosystemen (CISC, RISC, VLIW).
Microprocessor is een softwaregestuurd universeel apparaat voor digitale verwerking van discrete en (of) analoge informatie en controle van het proces van deze verwerking, gebouwd op een of meer. grote geïntegreerde schakelingen (LSI)
MP-functies.
Na het inschakelen van de stroom gaat de processor naar het eerste adres van het opstartprogramma en voert dit programma uit. Dit programma vooraf opgenomen in permanent (niet-vluchtig) geheugen. Na voltooiing van het initiële opstartprogramma begint de processor het hoofdprogramma uit te voeren dat zich in het permanente of RAM-geheugen bevindt, waarvoor hij op zijn beurt alle commando's selecteert. De processor kan van dit programma worden afgeleid door externe interrupts of DMA-verzoeken. De processor selecteert instructies uit het geheugen met behulp van leescycli via de bus. Indien nodig schrijft de processor gegevens naar het geheugen of I/O-apparaten met behulp van schrijfcycli, of leest hij gegevens uit het geheugen of I/O-apparaten met behulp van leescycli.
De belangrijkste functies van elke processor zijn dus als volgt:
1) bemonstering (lezen) van uitgevoerde opdrachten;
2) invoer (lezen) van gegevens uit het geheugen of invoer-/uitvoerapparaat;
3) gegevens uitvoeren (schrijven) naar geheugen of invoer-/uitvoerapparaten;
4) verwerking van gegevens (operanden), inclusief rekenkundige bewerkingen daarop;
5) geheugenadressering, dat wil zeggen het instellen van het geheugenadres waarmee de uitwisseling zal worden uitgevoerd;
6) interruptverwerking en directe toegangsmodus.
Opties
Belangrijkste kenmerken van de microprocessor
Microprocessors verschillen van elkaar in twee hoofdkenmerken: type (model) en klokfrequentie. Identieke modellen microprocessors kunnen verschillende klokfrequenties hebben: hoe hoger de klokfrequentie, hoe hoger de prestaties en prijs van de microprocessor. De klokfrequentie geeft aan hoeveel elementaire bewerkingen (cycli) de microprocessor in één seconde uitvoert. De kloksnelheid wordt gemeten in megahertz (MHz). Opgemerkt moet worden dat verschillende modellen microprocessors voeren dezelfde bewerkingen uit ander nummer klopt Hoe hoger het microprocessormodel, hoe minder klokcycli nodig zijn om dezelfde bewerkingen uit te voeren.
Laten we de kenmerken van processors in meer detail bekijken.
1. Type microprocessor.
Het type microprocessor dat in de computer is geïnstalleerd, is de belangrijkste factor die het uiterlijk van de pc bepaalt. De rekenmogelijkheden van een computer zijn ervan afhankelijk. Afhankelijk van het type microprocessor dat wordt gebruikt en de architectonische kenmerken van de computer die daardoor worden bepaald, worden vijf klassen pc's onderscheiden:
XT-klasse computers;
AT-klasse computers;
Klasse 386-computers;
Computerklasse 486;
Computers uit de Pentium-klasse.
2. Klokfrequentie van de microprocessor - geeft aan hoeveel elementaire bewerkingen (cycli) de microprocessor in één seconde uitvoert.
De klokgenerator genereert een reeks elektrische pulsen. De frequentie van de gegenereerde pulsen bepaalt de klokfrequentie van de machine. Het tijdsinterval tussen aangrenzende pulsen bepaalt de tijd van één werkingscyclus van de machine, of eenvoudigweg de werkingscyclus van de machine.
De frequentie van de klokgenerator is een van de belangrijkste kenmerken persoonlijke computer en bepaalt grotendeels de snelheid van de werking ervan, omdat elke handeling in de machine in een bepaald aantal cycli wordt uitgevoerd.
3. De microprocessorsnelheid is het aantal elementaire bewerkingen dat door de microprocessor per tijdseenheid wordt uitgevoerd (bewerkingen/seconde).
4. Bitcapaciteit van processor - het maximale aantal bits binaire code dat tegelijkertijd kan worden verwerkt of verzonden.
De bitcapaciteit van de MP wordt aangeduid als m/n/k/ en omvat: m - de bitcapaciteit van interne registers, bepaalt het lidmaatschap van een bepaalde klasse processors; n - databusbreedte, bepaalt de snelheid van informatieoverdracht; k - adresbusbreedte, bepaalt de grootte van de adresruimte. Zo wordt de i8088 MP gekenmerkt door de waarden m/n/k=16/8/20.
5. Microprocessorarchitectuur. (Soorten microprocessors)
Het concept van microprocessorarchitectuur omvat een systeem van commando's en adresseringsmethoden, de mogelijkheid om de uitvoering van commando's in de tijd te combineren, de aanwezigheid van extra apparaten in de microprocessor, principes en werkingsmodi.
In overeenstemming met de architectonische kenmerken die de eigenschappen van het commandosysteem bepalen, zijn er:
Microprocessors van het CISC-type met een volledige set instructiesystemen (de grootste set instructies, universele MP's, vervangen hele systemen);
Microprocessors van het type RISC met een ingekorte instructieset (moeten snel een aantal bewerkingen uitvoeren (120 commando's in totaal) Bijvoorbeeld: aansturen van randapparatuur);
Microprocessors van het VLIW-type met een zeer lang instructiewoord ((zeer lange instructie) - architecturen voor het berekenen van statistische parameters. Hun taak is enorme berekeningen);
Microprocessors van het MISC-type met een minimale instructieset en zeer hoge snelheid, enz.
12. Servermicroprocessors. Prestatie-eisen. Onderscheidende kenmerken.
Server MP – snelle uitvoering van bewerkingen. Taken snel voltooien. Adresseer een groot aantal OP's, moet alle taken uitvoeren.
XEON, AMD Optiron, deze processors besparen bijvoorbeeld geen energie. Ze hebben geen goede grafische kern.
Specificaties:
-frequentie
-chipset
-multiprocessorsysteem
Cache-architectuur.
Afhankelijk van de methode voor het bepalen van de onderlinge correspondentie van een cacheregel en een hoofdgeheugengebied, worden drie cachegeheugenarchitecturen onderscheiden: direct-mapped cache, volledig associatieve cache, gedeeltelijk of set-associatieve cache.
Direct toegewezen cache.
Bij direct-mapped cache bepaalt het geheugenadres waartoe toegang wordt verkregen op unieke wijze de cacheregel waarin het vereiste blok kan worden gelokaliseerd. We zullen het werkingsprincipe van een dergelijke cache uitleggen aan de hand van het voorbeeld van een niet-gesectoreerde cache van 256 KB met een lijngrootte van 32 bytes en een in de cache opgeslagen hoofdgeheugencapaciteit van 64 MB - een typische cache van een Pentium-moederbord. De structuur van het cachegeheugen in een dergelijk systeem wordt geïllustreerd in Fig. 1. Het in de cache opgeslagen hoofdgeheugen is voorwaardelijk verdeeld in pagina's (in dit geval elk 256 KB), waarvan de grootte samenvalt met de grootte van het cachegeheugen (256 KB). Cachegeheugen (en voorwaardelijk hoofdgeheugenpagina's) is verdeeld in lijnen (256 KB / 32 bytes - 8 K lijnen). Direct mapping-architectuur betekent dat elke cacheregel alleen de bijbehorende regel kan toewijzen vanaf elke pagina met cachegeheugen. Omdat de hoeveelheid hoofdgeheugen veel groter is dan de grootte van de cache, kan elke cacheregel worden geclaimd door veel geheugenblokken met hetzelfde lage-orde deel van het adres, dat de offset binnen de pagina wordt genoemd (0 - set, 1-set, 2-set ... N-set van 32 byteblokken). Eén regel kan tegelijkertijd slechts een kopie van één van deze blokken bevatten. Het regelnummer is het adres van de regel in het cachegeheugen en de tag bevat informatie over welk blok zich in beslag neemt deze lijn(een tag is het hoge deel van het adres dat door de processor wordt ingesteld bij toegang tot het geheugen of, met andere woorden, het paginanummer). Het taggeheugen moet een aantal cellen hebben dat gelijk is aan het aantal cacheregels, en de breedte ervan moet voldoende zijn om de meest significante bits van het cachegeheugenadres te huisvesten die niet op de cacheadresbus vallen. Naast het adresgedeelte van de tag wordt elke cacheregel geassocieerd met bits met tekenen van gegevensvaliditeit en -wijziging. Aan het begin van elke toegang tot RAM leest de cachegeheugencontroller allereerst een taggeheugencel met een lijnadres bepaald door bits A17-A5, vergelijkt de inhoud van deze taggeheugenregel met bits A25-A18 van het geheugen adres ingesteld door de processor, en analyseert een teken van de werkelijkheid.
Rijst. 1. Direct toegewezen cache.
Deze analyse wordt uitgevoerd in een speciale tracking-lus, ook wel een query-lus genoemd. Als uit de analyse blijkt dat het vereiste blok zich niet in de cache bevindt, wordt een hoofdgeheugentoegangscyclus (cachemisser) gegenereerd (of voortgezet). Als dit gebeurt, wordt het verzoek afgehandeld door het cachegeheugen. In geval van een misser worden de nieuwe gegevens, nadat de informatie door de ontvanger uit het hoofdgeheugen is gelezen, in de cacheregel geplaatst (als deze schoon is) , en de meest significante bits van het adres worden in de tag geplaatst en de geldigheid van de gegevens wordt ingesteld. Ongeacht de hoeveelheid gegevens die vanuit het hoofdgeheugen in de cache wordt opgevraagd, wordt de hele regel herschreven (aangezien de geldigheidsindicator van toepassing is op alle bytes). Als de cachecontroller vooruitlezen implementeert, wordt in daaropvolgende vrije buscycli de volgende regel (als deze schoon was) ook bijgewerkt ). Door het "in reserve" te lezen, kan, indien nodig, een batchcyclus van het lezen uit de cache over een lijngrens worden uitgevoerd. Deze cache heeft de eenvoudigste hardware-implementatie en wordt gebruikt in de secundaire cache van de meeste moederborden. Het heeft echter een ernstig nadeel. Als de processor tijdens de uitvoering van het programma afwisselend hetzelfde rijadres benadert, maar met verschillende of cyclisch veranderende tagnummers, zullen cache-missers voortdurend worden geregistreerd en zal het cachegeheugen, in plaats van te versnellen, de uitwisseling met het geheugen vertragen. Het wisselen van pagina's in multitasking-besturingssystemen (OS) vermindert ook het aantal cachehits, wat de systeemprestaties beïnvloedt. Het vergroten van de cachegrootte met behoud van de directe mapping-architectuur zal geen erg significant effect hebben, aangezien verschillende taken dezelfde cacheregels zullen claimen. Zonder de cachegrootte te vergroten, kunt u de efficiëntie van caching vergroten door de structuur ervan te wijzigen, wat hieronder zal worden besproken.
Soms bevat de beschrijving van een directe kaartcache de term set, die wordt gebruikt in plaats van de term rij in een sectorgerichte directe kaartcache, en de sector wordt dan een rij genoemd. Aan een set (evenals aan een cacheregel zonder sectoren) is tag-informatie gekoppeld die van toepassing is op alle elementen van de set (rijen of sectoren). Bovendien heeft elk element van de set (rij of sector) zijn eigen geldigheidsbit (Fig. 2).
Rijst. 2. Sectorale directe mapping-cache
Set-associatieve (gedeeltelijk associatieve) cache.
De set-associatieve cache-architectuur (Afbeelding 3) maakt het mogelijk dat elk in de cache opgeslagen geheugenblok een van de verschillende cacheregels claimt die in een set zijn gecombineerd. In deze architectuur zijn er als het ware meerdere parallelle en gecoördineerde directe mapping-kanalen, waarbij de cachecontroller een beslissing moet nemen over welke van de rijen van de set het volgende datablok moet plaatsen. In het eenvoudigste geval kan elk geheugenblok bijvoorbeeld in een van de vier set-lijnen passen (een vierweg set-associatieve cache). Het ingestelde nummer waarin het opgevraagde datablok kan worden weergegeven, wordt uniek bepaald door het middelste deel van het adres (zoals het regelnummer in de direct mapping cache). De setlijn die het vereiste blok representeert, wordt bepaald door een tagvergelijking (zoals in een associatieve cache) die parallel wordt uitgevoerd voor alle taggeheugenlijnen van een gegeven set (cachekanalen). Bovendien moet elke set worden gekoppeld aan een bord dat de setregel definieert die moet worden vervangen door een nieuw datablok in het geval van een cachemisser (een pijl wijst in de richting in de figuur).
Rijst. 3. Set-associatieve cache met vier kanalen
De kandidaat voor vervanging is meestal de rij die het langst niet is geopend (LRU - Least Recent Used-algoritme). Bij een relatief groot aantal kanalen (lijnen in een set) wordt enige vereenvoudiging toegepast: het Pseudo-LRU-algoritme voor vier lijnen maakt het mogelijk beslissingen te nemen met behulp van slechts 3 bits.
Het is ook mogelijk om een FIFO-vervangingsalgoritme (first in, first out) of zelfs willekeurige vervanging te gebruiken, wat eenvoudiger maar minder efficiënt is. Set-associatieve architectuur wordt veel gebruikt voor de primaire cache van moderne processors.
Associatieve cache.
In tegenstelling tot de vorige heeft een volledig associatieve cache elke regel kan elk geheugenblok in kaart brengen, wat de efficiëntie van het gebruik van beperkte cacheruimte aanzienlijk verhoogt. In dit geval alle bits
Rijst. 4. Volledig associatief cachegeheugen.
De adressen van het in de cache opgeslagen blok, minus de bits die de positie (offset) van de gegevens in de lijn bepalen, worden opgeslagen in het taggeheugen. In een dergelijke architectuur (Fig. 4) wordt, om de aanwezigheid van de gevraagde gegevens in het cachegeheugen te bepalen, een vergelijking gemaakt met het hoge deel van het tagadres van alle taggeheugenlijnen, en niet met één of meerdere, zoals bij directe mapping of set-associatieve architectuur is vereist. Sequentiële opsomming van taggeheugencellen wordt geëlimineerd. (dit kost te veel tijd), dus er blijft een parallelle vergelijking van de tags van alle cellen bestaan, en dit is een complexe hardwaretaak die alleen op acceptabele wijze kan worden opgelost voor kleine volumes van de primaire cache (M2 Cyrix-processor).
Dit type geheugen ligt tussen de twee hierboven besproken. Het combineert de eenvoud van een direct toegewezen cache met de snelheid van associatief zoeken.
Het cachegeheugen is verdeeld in onsamenhangende subsets (blokken) van lijnen. Elke hoofdgeheugenlijn kan slechts in één cachesubset terechtkomen. Directe mapping wordt gebruikt om naar blokken te zoeken, en volledig associatief zoeken wordt gebruikt om binnen een subset te zoeken. Het aantal regels in een cache-subset bepaalt het aantal ingangen (poorten) van de cache zelf.
Als 2 n cachelijnen zijn verdeeld in disjuncte subsets van 2 s, geven de trage-orde bits van RAM aan in welke subset (index) de associatieve zoekactie moet worden uitgevoerd. Senior n-s De hoofdgeheugenadresbits zijn tags.
Als S=0, krijgen we één subset, die overeenkomt met een volledig associatief cachegeheugen. Als S=n, dan krijgen we 2 n subsets (dat wil zeggen één lijn - één subset). Dit is een direct toegewezen cachegeheugen. Als 1 £ S £ n-1, dan hebben we een set-associatief cachegeheugen.
Figuur 6.5 toont een voorbeeld van een cache waarbij S=1, dat wil zeggen dat er twee subsets zijn cachegeheugen. Fysiek adres 0111, gegenereerd door de processor, is verdeeld in index 1, gelijk aan het minst significante cijfer, en tag 011. De tweede subset van regels in het cachegeheugen wordt geselecteerd met behulp van de index, en vervolgens wordt een associatieve zoekopdracht uitgevoerd tussen de lijntags van de geselecteerde subset. De gevonden regel 7 met tag 011 wordt naar de databus (SD) verzonden. Er wordt associatief zoeken uitgevoerd
tijdelijk voor alle tags die combinatievergelijkingsschema's CC1 en CC2 gebruiken.
Rijst. 6.5. Multi-associatieve cache
Moderne processors gebruiken cachegeheugen met 4 en 8 ingangen. Een toename van het aantal inputs leidt tot snelle stijging de complexiteit van de hardware-implementatie van dat deel van de cache dat associatief zoeken naar tags mogelijk maakt.
Kenmerken van het opnemen en vervangen van informatie in het cachegeheugen.
Cache-coherentie
Leestoegang tot zowel de cache als het RAM-geheugen kan onmiddellijk beginnen. Als de informatie vervolgens in de cache ontbreekt, zal tegen de tijd dat dit feit wordt vastgesteld, een deel van de RAM-toegangscyclus al zijn voltooid, wat de prestaties kan verbeteren. Als de informatie zich in de cache bevindt, kan de toegang tot RAM worden gestopt.
Bij toegang via schrijven worden twee methoden gebruikt: schrijven gebeurt alleen in de cache of in zowel de cache als het RAM tegelijk. Deze methoden worden algoritmen genoemd achteruit WB (Terugschrijven) en door records WT (doorschrijven) respectievelijk. De tweede is eenvoudiger, maar ook langzamer, hoewel deze garandeert dat kopieën van dezelfde informatie in de cache en het RAM altijd overeenkomen. De meeste vroege Intel-processors gebruiken dit algoritme.
Het WB-terugschrijfalgoritme is sneller. Informatie wordt alleen naar RAM overgedragen wanneer een regel van een andere OP-pagina wordt overgebracht naar de plaats van een bepaalde cacheregel of wanneer een opdracht wordt uitgevoerd om de inhoud van de cache bij te werken. Dit algoritme vereist zorgvuldiger beheer, omdat er momenten zijn waarop kopieën van dezelfde informatie verschillend zijn in de cache en OP. Bovendien verandert niet elke regel terwijl deze zich in de cache bevindt. Als er geen verandering is opgetreden, is het niet nodig om de string terug naar het RAM-geheugen te herschrijven. Meestal gebruiken ze de M-vlag (gemodificeerd) in het taggeheugen. Het wordt opnieuw ingesteld op “0” wanneer de regel voor het eerst in de cache wordt geladen en ingesteld op “1” wanneer er informatie naartoe wordt geschreven. Wanneer een regel uit de cache wordt verwijderd, wordt er alleen naar de OP geschreven als de M-vlag op één is ingesteld.
Wanneer er een misser optreedt, moet de cachecontroller een regel selecteren om te vervangen. Voor directe weergave zijn hardwareoplossingen het eenvoudigst. Er wordt slechts één regel getest op een treffer, en alleen die regel kan worden vervangen. Bij een volledig associatieve of multi-associatieve cache-organisatie zijn er verschillende lijnen waaruit een kandidaat moet worden geselecteerd in geval van een misser. Om dit probleem op te lossen, gebruikt u de volgende speciale regels, genaamd vervangingsalgoritmen .
1) FIFO (First In First Out - wie het eerst komt - het eerst weggaat);
2) LRU (minst recent gebruikt - langer ongebruikt dan andere);
3) LFU (minst frequent gebruikt – minder vaak gebruikt);
4) Willekeurig.
De eerste en laatste methoden zijn het eenvoudigst te implementeren, maar houden geen rekening met hoe vaak een bepaalde cacheregel wordt gebruikt. In dit geval kan een rij die in de zeer nabije toekomst wordt geopend, worden verwijderd. De foutkans voor deze methoden is veel groter dan voor de tweede en derde.
In het FIFO-algoritme wordt de regel die als eerste in de cache terechtkomt, geselecteerd voor vervanging. Elke nieuw in de cache geplaatste regel wordt aan de staart van deze wachtrij toegevoegd. Het algoritme houdt geen rekening met het daadwerkelijke gebruik ervan. De eerste geladen rijen kunnen bijvoorbeeld gegevens bevatten die gedurende de gehele bewerking nodig zijn. Dit zorgt voor een onmiddellijke terugkeer naar de lijn die zojuist is vervangen.
Het LRU-algoritme bepaalt dat de rij die het langst ongebruikt is, moet worden geselecteerd voor verwijdering. Elke keer dat een rij wordt geopend, wordt de tijdstempel ervan bijgewerkt. Dit kan aanzienlijke kosten met zich meebrengen. In de praktijk wordt echter het LRU-algoritme het meest gebruikt. Het nadeel is dat als een programma een grote lus doorloopt die veel regels beslaat, het kan gebeuren dat de lijn die het langst niet is gebruikt, daadwerkelijk de volgende is die wordt gebruikt.
Een van de algoritmen die dicht bij LRU liggen, is het LFU-algoritme, waarbij de minst gebruikte rij wordt verwijderd. In dit geval is het noodzakelijk om het aantal toegangen tot elke lijn te tellen en te controleren. Het kan blijken dat de minst intensief gebruikte regel de regel is die zojuist naar het cachegeheugen is geschreven en die slechts één keer is benaderd (terwijl andere regels meer werden gebruikt). Het kan worden verwijderd, wat een nadeel is van het LFU-algoritme.
De inhoud van het cachegeheugen verandert onder controle van de processor. In dit geval kan het hoofdgeheugen ongewijzigd blijven. Aan de andere kant kunnen externe apparaten gegevens in het OP wijzigen in de directe toegangsmodus. In dit geval verandert het cachegeheugen zijn gegevens niet. Meer de situatie is ingewikkelder in systemen met meerdere processors, wanneer meerdere processors toegang hebben tot gedeeld geheugen. Er ontstaat een probleem samenhang cachegeheugen.
Het computersysteem heeft samenhangend geheugen als elke leesbewerking op een adres uitgevoerd door een apparaat de waarde retourneert van de laatste kopie op dat adres, ongeacht welk apparaat de laatste kopie heeft geschreven. Het coherentieprobleem is het belangrijkst bij kopieersystemen. Ze gebruiken speciale protocollen en aan elke tag worden vlaggen van wijziging en betrouwbaarheid van informatie toegevoegd. Deze vlaggen staan toegang tot gegevens toe of weigeren deze.
Laden...
