Jak działa pamięć o dostępie losowym? Dlaczego jest to stały dostęp losowy?

Obliczenie, aby uzyskać od początku tablicy do dowolnego elementu wymaga tylko dwóch operacji, mnożenie (times sizeof (element)) i dodawanie. Obie te operacje są w stałym czasie. Często w przypadku dzisiejszych procesorów można to zrobić w zasadzie w mgnieniu oka, ponieważ procesor jest zoptymalizowany pod kątem tego rodzaju dostępu.

Kiedy mówię array [4] = 12 w programie, tak naprawdę zapisuję bit reprezentacja adresu pamięci w rejestrze. Ten fizyczny Zarejestruj się w sprzęcie włączy odpowiednią elektrykę sygnały zgodnie z reprezentacją bitową, którą podałem. Te elektryczne sygnały będą wtedy jakoś magicznie (mam nadzieję, że ktoś wyjaśni Magia) dostęp do właściwego adresu pamięci w pamięci fizycznej/głównej.

array[4] = 12;

Więc z komentarzy wynika, że trzeba uzyskać adres bazowy tablicy, a następnie pomnożyć przez Rozmiar elementu tablicy (lub przesunięcie, jeśli taka optymalizacja jest możliwa), aby uzyskać adres (z perspektywy programów) lokalizacji pamięci. Prawo bat, mamy problem. Czy te rzeczy są już w rejestrach, czy musimy po nie iść? Adres bazowy tablicy może, ale nie musi, znajdować się w rejestrze w zależności od kodu otaczającego tę linię kodu, w szczególności kodu, który ją poprzedza. Ten adres może znajdować się na stosie lub w innej lokalizacji, w zależności od tego, gdzie go zadeklarowałeś i jak. I to może, ale nie musi mieć znaczenia, jak długo to zajmie. Kompilator optymalizujący może (często) posunąć się tak daleko, aby wstępnie obliczyć adres tablicy [4] i umieść to gdzieś, aby mogło wejść do rejestru, a mnożenie nigdy nie dzieje się w czasie działania, więc absolutnie nie jest prawdą, że obliczanie tablicy [4] dla dostępu losowego jest ustaloną ilością czasu w porównaniu do innych dostępów losowych. W zależności od procesora, niektóre bezpośrednie wzorce są jedną instrukcją, inne biorą więcej, co ma również wpływ na to, czy ten adres jest odczytywany .tekst lub stos lub itp, etc...To nie Kura i jajko, że problem na śmierć, Załóżmy, że mamy adres tablica [4] obliczona.

Jest to operacja zapisu, z punktu widzenia programistów. Zaczynając od prostego procesora, bez pamięci podręcznej, bez bufora zapisu, bez mmu itp. Ostatecznie prosty procesor umieści adres na krawędzi rdzenia procesora, z stroboskopem zapisu i danymi, każda szyna procesora różni się od innych rodzin procesorów, ale jest mniej więcej taka sama adres i dane mogą wyjść w tym samym cyklu lub w oddzielnych cyklach. Typ polecenia (odczyt, zapis) może się zdarzyć w w tym samym czasie lub inaczej. ale rozkaz wychodzi. Krawędź rdzenia procesora jest podłączona do kontrolera pamięci, który dekoduje ten adres. Rezultatem jest przeznaczenie, czy jest to Peryferia, jeśli tak, Który i na jakiej szynie, czy ta pamięć, jeśli tak, na jakiej szynie pamięci i tak dalej. Załóżmy, że ram, Załóżmy, że ten prosty procesor ma sram, a nie dram. Sram jest droższy i szybszy w porównaniu jabłek do jabłek. SRAM ma adres i Stroby zapisu/odczytu i inne kontrolki. Ostatecznie będziesz miał typ transakcji, Odczyt/Zapis, adres i dane. SRAM jednak jego geometria będzie trasować i przechowywać poszczególne bity w ich pojedynczych parach / grupach tranzystorów.

Cykl zapisu można odpalić i zapomnieć. Wszystkie informacje, które są potrzebne do zakończenia transakcji, to jest zapis, to jest adres, to są dane, są znane od razu i tam. Kontroler pamięci może, jeśli wybierze, powiedzieć procesorowi, że transakcja zapisu została zakończona, nawet jeśli dane nie znajdują się w pobliżu pamięci. Ta para adres / dane zajmie trochę czasu dotarciu do pamięci i procesor może nadal działać. Niektóre systemy, choć konstrukcja jest taka, że procesory zapis transakcji czeka, aż sygnał wraca do wskazania, że zapis dotarł aż do pamięci ram. W Ustawieniach typu fire and forget, adres/Dane będą gdzieś w kolejce i będą działać w drodze do pamięci ram. Kolejka nie może być nieskończenie głęboka inaczej byłoby ram sam, więc jest skończony, i jest możliwe i prawdopodobne, że wiele zapisów w wierszu może wypełnić tę kolejkę szybciej niż drugi koniec może zapisać do pamięci ram. W tym momencie bieżący i lub następny zapis musi czekać na kolejkę, aby wskazać, że jest miejsce na jeszcze jeden. Tak więc w takich sytuacjach, jak szybko odbywa się zapis, czy twój prosty procesor jest związany z I / O, czy nie, ma to związek z wcześniejszymi transakcjami, które mogą lub nie muszą być instrukcjami zapisu poprzedzającymi tę instrukcję w pytanie.

Teraz dodaj trochę złożoności. ECC lub jakakolwiek nazwa chcesz go nazwać (EDAC, jest inny). Sposób, w jaki działa pamięć ECC, polega na tym, że wszystkie zapisy mają stały rozmiar, nawet jeśli twoja implementacja to cztery 8-bitowe części pamięci dające 32 bity danych na zapis, musisz mieć stałą z tym, że ECC obejmuje i musisz zapisać bity danych plus bity ecc wszystkie w tym samym czasie (musisz obliczyć ecc na całej szerokości). Więc jeśli był to 8 bitowy zapis np. do 32-bitowa pamięć chroniona ECC wtedy ten cykl zapisu wymaga cyklu odczytu. Odczytaj 32 bity (sprawdź ecc na tym odczycie) zmodyfikuj nowe 8 bitów w tym 32 bitowym wzorze, Oblicz nowy wzorzec ecc, napisz 32 bity plus bity ecc. Oczywiście, że część odczytu cyklu zapisu może skończyć się błędem ecc, co po prostu sprawia, że życie jest jeszcze bardziej zabawne. Błędy pojedynczych bitów mogą być poprawiane zwykle (co dobre jest ECC / EDAC, jeśli nie można), błędy wielobitowe nie. Jak sprzęt jest zaprojektowany do obsługi tych błędy wpływają na to, co dzieje się dalej, błąd odczytu może po prostu wrócić do procesora, który uszkadza transakcję zapisu, lub może wrócić jako przerwanie itp. Ale tutaj jest inne miejsce, gdzie jeden losowy dostęp nie jest taki sam jak inny, w zależności od dostępnej pamięci, a rozmiar dostępu Odczyt-modyfikacja-zapis zdecydowanie trwa dłużej niż zwykły zapis.

Pamięć Dram może również należeć do tej kategorii o stałej szerokości, nawet bez ECC. Właściwie wszystkie wspomnienia należą do tej kategorii w pewnym momencie. Tablica pamięci jest zoptymalizowana na krzemie dla określonej wysokości i szerokości w jednostkach bitów. Nie można naruszać tej pamięci, można ją tylko odczytywać i zapisywać w jednostkach tej szerokości na tym poziomie. Biblioteki krzemowe będą zawierać wiele geometrii pamięci ram, a projektanci będą wybierać te geometrie dla swoich części, a części będą miały ustalone limity i często można użyć wielu części, aby uzyskać pewną liczbę całkowitą wielokrotności szerokości tego rozmiaru, a czasami projekt pozwoli Ci aby napisać tylko do jednej z tych części, jeśli tylko niektóre bity się zmieniają, lub niektóre projekty zmuszą wszystkie części do świecenia. Zauważ, jak kolejna rodzina modułów ddr, które podłączasz do komputera domowego lub laptopa, pierwsza wave to wiele części po obu stronach płyty. Następnie, jak ta technologia staje się starsza i bardziej nudne, może zmienić się na mniej części po obu stronach płyty, w końcu staje się mniej części po jednej stronie płyty, zanim ta technologia jest przestarzałe i już jesteśmy do następnego.

Ta kategoria stałej szerokości niesie ze sobą również kary wyrównania. Niestety większość ludzi uczy się na maszynach x86, które nie ograniczają dostępu do wyrównanych jak wiele innych platform. Na x86 lub innych urządzeniach obowiązuje określona kara za niezaliczone dostępy, jeśli jest to dozwolone. Jest to zwykle, gdy ludzie idą do mips lub Zwykle ramię na jakimś urządzeniu zasilanym bateryjnie, kiedy po raz pierwszy uczą się jako programiści o wyrównanych dostępach. I niestety uważają je za bolesne zamiast błogosławieństwa (ze względu na prostotę zarówno w programowaniu, jak i korzyści sprzętowe, które z niego wynikają). W skrócie, jeśli pamięć ma szerokość 32 bitów i może być dostępna tylko, odczyt lub zapis, 32 bity na raz, co oznacza, że jest ograniczona tylko do wyrównanych dostępu. Szyna pamięci o szerokości 32 bitów zwykle nie ma dolnych bitów adresu a [1: 0], ponieważ nie ma dla nich zastosowania. te dolne bity z punktu widzenia programistów są zerami. gdyby nasz zapis wynosił 32 bity przeciwko jednej z tych 32-bitowych pamięci i adres był 0x1002. Następnie ktoś po linii musi odczytać pamięć pod adresem 0x1000 i wziąć dwa z naszych bajtów i zmodyfikować tę 32-bitową wartość, a następnie zapisać ją z powrotem. Następnie weź 32 bity pod adres 0x1004 i zmodyfikuj dwa bajty i zapisz je z powrotem. cztery cykle magistrali dla jednego zapisu. Gdybyśmy pisali 32 bity na adres 0x1008, chociaż byłby to prosty 32 bitowy zapis, bez odczytów.

Następna przeszkoda, cache. Pamięć podręczna jest dobra i zła. Pamięć podręczna jest zazwyczaj wykonana z pamięci sram. Mam nadzieję, że masz zrozumienie pamięci podręcznej. Jeśli procesor lub ktoś z dostawców oznaczył transakcję jako nie-buforowalną, przechodzi ona przez niebuforowaną do magistrali pamięci po drugiej stronie. Jeśli cacheable to część adresu a jest sprawdzana w tabeli i spowoduje trafienie lub chybienie. jest to zapis, w zależności od pamięci podręcznej i / lub ustawień transakcji, jeśli jest to miss może przejść do drugiej strony. Jeśli dojdzie do trafienia, dane zostaną zapisane w pamięci podręcznej, w zależności od typu pamięci podręcznej może również przejść na drugą stronę lub dane mogą siedzieć w pamięci podręcznej czekając na jakiś inny fragment danych, aby go eksmitować, a następnie zostaje zapisany na drugą stronę. Cache zdecydowanie czyta, a czasami pisze niedeterministycznie. Dostęp sekwencyjny ma najwięcej korzyści, ponieważ wskaźnik eksmisji jest niższy, pierwszy dostęp w linii pamięci podręcznej jest powolny w stosunku do innych, a reszta jest szybka. stąd i tak otrzymujemy ten termin przypadkowego dostępu. Losowe dostępy idą na przeciw schematy, które mają na celu szybszy dostęp sekwencyjny.

Czasami po drugiej stronie pamięci podręcznej znajduje się bufor zapisu. Stosunkowo mała kolejka / pipe / buffer / fifo, która przechowuje pewną liczbę transakcji zapisu. Kolejny pożar i zapomnij o umowie, z tymi korzyściami.

Wiele warstw pamięci podręcznej. l1, l2, l3...L1 jest zwykle najszybszy ze względu na swoją technologię lub bliskość, i zwykle najmniejszy, a stamtąd wzrasta szybkość i rozmiar, a niektóre z tego mają związek z kosztami pamięć. Robimy zapis, ale kiedy robisz Cache włączone czytać zrozumieć, że jeśli L1 ma miss idzie do l2 który jeśli ma miss idzie do l3 który jeśli ma miss idzie do pamięci głównej, następnie L3, l2 i L1 wszystkie będą przechowywać kopię. Więc miss na wszystkich 3 jest oczywiście najbardziej bolesne i jest wolniejsze niż Jeśli nie miał cache w ogóle, ale sekwencyjne odczyty daje buforowane elementy, które są teraz w l1 i super szybkie, dla pamięci podręcznej, aby być przydatne sekwencyjne odczyty nad linią pamięci podręcznej powinny zajmuje to mniej czasu niż czytanie takiej ilości pamięci bezpośrednio z wolnej pamięci dram. System nie musi mieć 3 warstw pamięci podręcznej, może się różnić. Podobnie niektóre systemy mogą oddzielić pobieranie instrukcji od odczytu danych i mogą mieć oddzielne pamięci podręczne, które nie eksmitują się nawzajem, a niektóre pamięci podręczne nie są oddzielne, A pobieranie instrukcji może eksmitować dane z odczytu danych.

Pamięci podręczne pomagają w problemach z wyrównaniem. Ale oczywiście jest jeszcze surowsza kara za niezalegany dostęp przez linie pamięci podręcznej. Pamięci podręczne zwykle działają przy użyciu fragmentów pamięci zwanych liniami pamięci podręcznej. Są to często liczby całkowite wielkości pamięci po drugiej stronie. na przykład pamięć 32 bitowa linia pamięci podręcznej może mieć na przykład 128 bitów lub 256 bitów. Więc jeśli i kiedy linia bufora jest w buforze, to odczyt-modyfikacja-zapis z powodu niezaliczonego zapisu jest przeciwko szybszej pamięci, nadal bardziej bolesne niż wyrównane, ale nie tak bolesne. Gdyby to był odczyt bez zmian i adres był taki, że część tego dane znajdują się po jednej stronie granicy linii bufora, a po drugiej dwie linie bufora muszą być odczytywane. Na przykład odczyt 16-bitowy może kosztować wiele bajtów odczytywanych z najwolniejszą pamięcią, oczywiście kilka razy wolniej niż w przypadku braku pamięci podręcznej. W zależności od tego, w jaki sposób pamięć podręczna i system pamięci w ogóle jest zaprojektowany, jeśli wykonasz zapis przez granicę linii bufora, może to być podobnie bolesne, lub być może nie tak bardzo, że może mieć ułamek zapis do bufora, a drugi ułamek wyjdź na drugą stronę jako mniejszy napis.

Następna warstwa złożoności to mmu. Pozwalając procesorowi i programiście na iluzję płaskich przestrzeni pamięci i / lub kontrolę nad tym, co jest buforowane lub nie, i / lub ochronę pamięci i / lub iluzję, że wszystkie programy są uruchomione w tej samej przestrzeni adresowej(więc twój toolchain zawsze może skompilować / link dla adresu 0x8000 na przykład). Mmu pobiera część wirtualnego adresu Po stronie rdzenia procesora. wygląda na to, że w tabeli, lub serie tabel, te Wyszukiwania często znajdują się w przestrzeni adresowej systemu, więc każde z tych wyszukiwań może być jednym lub więcej ze wszystkich wymienionych powyżej, ponieważ każdy z nich jest cyklem pamięci w pamięci systemowej. Te poszukiwania mogą spowodować błędy ecc, nawet jeśli próbujesz zrobić zapis. Ostatecznie po jednym, dwóch, trzech lub więcej odczytach, mmu ustalił, jaki jest adres po drugiej stronie MMU, a właściwości (buforowalne lub nie, itp.) i które są przekazywane do następnej rzeczy (L1, itp.) i wszystkie powyższe mają zastosowanie. Niektóre MMU mają w sobie trochę pamięci podręcznej pewnej liczby wcześniejszych transakcji, pamiętaj, ponieważ programy są sekwencyjne, sztuczki używane do zwiększenia iluzji wydajności pamięci opierają się na sekwencyjnych dostępach, a nie przypadkowych dostępach. Tak więc pewna liczba wyszukiwań może być przechowywana w mmu, więc nie musi od razu wychodzić do pamięci głównej...

Więc w nowoczesnym komputerze z MMU, pamięci podręczne, dram, sekwencyjne odczyty w szczególności, ale również zapisy są prawdopodobnie szybszy niż losowy dostęp. Różnica może być dramatyczna. Pierwsza transakcja w sekwencyjnym odczycie lub zapisie jest w tym momencie przypadkowym dostępem, ponieważ nie była widziana nigdy lub przez jakiś czas. Gdy sekwencja trwa, chociaż optymalizacje spadają w kolejności,a następne kilka / niektóre są zauważalnie szybsze. Rozmiar i dostosowanie transakcji odgrywa ważną rolę w wydajności, jak również. Podczas gdy dzieje się tak wiele niedeterministycznych rzeczy, jako programista z tą wiedzą ty zmodyfikuj swoje programy, aby działały znacznie szybciej lub jeśli masz pecha lub celowo, możesz zmodyfikować swoje programy, aby działały znacznie wolniej. Sequential będzie generalnie szybszy na jednym z tych systemów. losowy dostęp będzie bardzo niedeterministyczny. array[4]=12; nastÄ ™ pnie array[37]=12; te dwie operacje wysokiego poziomu mogÄ ... zajmowaÄ ‡ znacznie róşne iloĹ " ci czasu, zarĂłwno w obliczeniach adresu zapisu, jak i samych zapisăłw. Ale na przykład discarded_variable = array[3]; array[3]=11; array [4]=12; może dość często wykonywać znacznie szybciej niż array[3]=11; array[4]=12;

Tablice w C i C++ mają dostęp losowy, ponieważ są przechowywane w pamięci RAM - Random Access W skończonej, przewidywalnej kolejności. W rezultacie do określenia położenia danego rekordu wymagana jest prosta operacja liniowa (a[i] = a + sizeof (a[0]) * i). Obliczenia te mają stały czas. Z punktu widzenia procesora nie jest wymagana operacja "Szukaj" lub "przewijanie", po prostu mówi pamięci "załaduj wartość pod adresem X".

Jednak: na nowoczesnym CPU idea, że zajmuje to stały czas, aby pobieranie danych nie jest już prawdą. Zajmuje stały czas amortyzacji , w zależności od tego, czy dana część danych znajduje się w pamięci podręcznej, czy nie.

Mimo to-ogólna zasada jest taka, że czas na pobranie danego zbioru 4 lub 8 bajtów z pamięci RAM jest taki sam niezależnie od adresu. Na przykład, jeśli uzyskasz dostęp do pamięci RAM [0] i pamięci RAM [4294967292], procesor otrzyma odpowiedź w ciągu tej samej liczby cykli.

#include <iostream>
#include <cstring>
#include <chrono>

// 8Kb of space.
char smallSpace[8 * 1024];

// 64Mb of space (larger than cache)
char bigSpace[64 * 1024 * 1024];

void populateSpaces()
{
    memset(smallSpace, 0, sizeof(smallSpace));
    memset(bigSpace, 0, sizeof(bigSpace));
    std::cout << "Populated spaces" << std::endl;
}

unsigned int doWork(char* ptr, size_t size)
{
    unsigned int total = 0;
    const char* end = ptr + size;
    while (ptr < end) {
        total += *(ptr++);
    }
    return total;
}

using namespace std;
using namespace chrono;

void doTiming(const char* label, char* ptr, size_t size)
{
    cout << label << ": ";
    const high_resolution_clock::time_point start = high_resolution_clock::now();
    auto result = doWork(ptr, size);
    const high_resolution_clock::time_point stop = high_resolution_clock::now();
    auto delta = duration_cast<nanoseconds>(stop - start).count();
    cout << "took " << delta << "ns (result is " << result << ")" << endl;
}

int main()
{
    cout << "Timer resultion is " << 
        duration_cast<nanoseconds>(high_resolution_clock::duration(1)).count()
        << "ns" << endl;

    populateSpaces();

    doTiming("first small", smallSpace, sizeof(smallSpace));
    doTiming("second small", smallSpace, sizeof(smallSpace));
    doTiming("third small", smallSpace, sizeof(smallSpace));
    doTiming("bigSpace", bigSpace, sizeof(bigSpace));
    doTiming("bigSpace redo", bigSpace, sizeof(bigSpace));
    doTiming("smallSpace again", smallSpace, sizeof(smallSpace));
    doTiming("smallSpace once more", smallSpace, sizeof(smallSpace));
    doTiming("smallSpace last", smallSpace, sizeof(smallSpace));
}

Live demo: http://ideone.com/9zOW5q

Wyjście (od ideone, które może nie być ideałem)

Success  time: 0.33 memory: 68864 signal:0
Timer resultion is 1ns
Populated spaces
doWork/small: took 8384ns (result is 8192)
doWork/small: took 7702ns (result is 8192)
doWork/small: took 7686ns (result is 8192)
doWork/big: took 64921206ns (result is 67108864)
doWork/big: took 65120677ns (result is 67108864)
doWork/small: took 8237ns (result is 8192)
doWork/small: took 7678ns (result is 8192)
doWork/small: took 7677ns (result is 8192)
Populated spaces
strideWork/small: took 10112ns (result is 16384)
strideWork/small: took 9570ns (result is 16384)
strideWork/small: took 9559ns (result is 16384)
strideWork/big: took 65512138ns (result is 134217728)
strideWork/big: took 65005505ns (result is 134217728)

Widzimy tu wpływ pamięci podręcznej na wydajność dostępu do pamięci. Przy pierwszym trafieniu w smallSpace potrzeba ~8100ns, aby uzyskać dostęp do wszystkich 8kB małej przestrzeni. Ale kiedy zadzwonimy ponownie natychmiast po, dwa razy, zajmuje ~600ns mniej przy ~7400ns.

Teraz odchodzimy i robimy bigspace, który jest większy niż obecna pamięć podręczna procesora, więc wiemy, że zdmuchnęliśmy pamięć podręczną L1 i L2.

Powrót do małych, których na pewno nie buforowane teraz ponownie widzimy ~8100ns po raz pierwszy i ~7400 dla dwóch drugich.