.. i do tego programowanie wielowątkowe. Ja tu czegoś nie rozumiem. Weźmy na przykład program do obliczenia sumy liczb od 1 do N. Ot, zwykły ciąg arytmetyczny S(N)=N*(N+1)/2. Zakładając, że wzoru nie znamy, zlecamy to kompowi. Soft jest banalny:
s:=0; for i:=0 to N do begin s:=s+1; end;
Powyższe jest nasmarowane w Pascalu, którego składnia jest podobna do C, ino jest to bardziej czytelne. Nie w tym rzecz.. Rozbijmy to na 2 wątki:
1) s1:=0; for i:=0 to k do ........... ..........
2) s2:=0; for i:=k+1 do ............. ..............
Wiasomo o co biega,no i na koniec s:=s1+s2. Czyli wykonujemy jak gdyby 2 programy na 2-ch różnych kompach, kompilator ładnie nam to rozdzielił i klawo jak cholera. No to teraz skomplikujmy zagadnienie ciuta bardziej.. Chcemy policzyć sumę wyrazów jakiegoś ciągu, którego wyrazy są zapisane w wektorze A[i] (i=0..N). Robimy zaś 2 wątki:
1) s1:=0; for i:=0 to k do begin s1:=s1+A[i]; end;
2) s2:=0; for i:=k+1 to N do begin s2:=s2+A[i]; end;
s:=s1+s2. A co jeżeli elementy ciągu A[m] i A[n] są zapisane fizycznie w tej samej kostce pamięci? Co w takiej sytuacji dają mi 2 rdzenie?
Jak już wspomniał Andrzej, w takim przypadku strona pamięci z danymi zostanie przepisana do pamięci cache i problem jednoczesnego dostępu do zewnętrznej kostki przestanie istnieć.
Ale załóżmy że tech cache nie ma i przy każdym odczycie procesor będzie musiał sięgnąć do pamięci zewnętrznej. Jeśli cały program by się składał wyłącznie z odczytów z pamięci, wtedy byłby problem, bo rdzenie by sobie przeszkadzały nawzajem. Ale nawet przy tak prostym programie jak przytoczyłeś, odczyt z pamięci jest jedną z kilku- kilkunastu instrukcji które muszą zostać wykonane podczas jednego obiegu pętli. Podczas kiedy jeden rdzeń zajmuje się wykonaniem dodawania, przepisywaniem pomiędzy rejestrami sprawdzaniem warunku końca czy czy skokiem do początku pętli, szyna pamięci danych leży odłogiem i może być wykorzystana przez drugi rdzeń do pobrania danych.
Nawet jeśli założymy najbardziej niekorzystny przypadek, że podczas każdego obiegu pętli obydwa rdzenie będą chciały czytać w tym samym momencie, i tak spowolnienie będzie ledwie zauważalne. W większości przypadków każdy rdzeni nawet nie zauważy że dostęp do pamięci jest dzielony z kimś innym.
W dniu niedziela, 5 października 2014 00:41:48 UTC+2 użytkownik A. L. napisał:
Pamięć cache to też taka "kostka" tyle że zaszyta w kostce procka. No i co w sytuacji, gdy 2 procesory odwołują się jednocześnie do dwóch różnych adresów w obrębie tej pamięci?
W dniu niedziela, 5 października 2014 01:47:28 UTC+2 użytkownik Jacek Radzikowski napisał:
Dlaczego?! Cóż tam za magia jest zaszyta w tym cache'u, że pozwala na jednoczesny dostęp do dwóch albo i więcej(ilość rdzeni/wątków) adresów jednocześnie?
L1 jest najczęściej do wyłącznego użytku rdzenia. A jeśli nie - to działa mechanizm identyczny do opisanego. Z tą drobną różnicą że pamięć cache jest o wiele szybsza i przestoje są krótsze.
OK, czas dostępu do cache jest argumentem przekonywującym. Zapomnijmy na chwilę o wielowątkowości/wielordzeniowości. A co w przypadku jeżeli mamy program, którego kod znacznie objętościowo przekracza pojemność cache'a? A z reguły tak jest. No i teraz w wyniku działania programu przy spełnieniu jakiś tam warunków mamy dłuuuugie skoki do innej części kodu? Nie mam zamiaru się tutaj wymądrzać i deprecjonować sensu pakowania cache'a do procka, ale czy zawsze ten mechanizm jest porządany? No bo w przypadku dłuuugich skoków o ile dobrze rozumiem pamięć cache powinna być przeładowana na nowy obszar kodu. No a to przeładowanie, to jakby na to nie patrzeć zaś komunikacja z pamięcią zewnętrzną, a co za tym idzie zaś trzeba na to trochę czasu... Bilans zysków i strat wydaje mi się może być przy spełnieniu pewnych warunków wręcz niekorzystny. Tak se gdybam...
Zarządzanie zawartością pamięci cache to bardzo skomplikowany temat, na którym zrobiono wiele doktoratów i sporo zostanie zrobionych w przyszłości. W skrócie wygląda to tak, że zawartość cache nie odwzorowuje liniowo jednego wielkiego obszaru pamięci, a wiele stosunkowo niedużych stron. Strony sąsiadujące ze sobą w cache mogą w pamięci głównej być położone daleko od siebie. Tym żeby wiedzieć jaki adres w cache odpowiada adresowi w pamięci zajmuje się tablica translacji. Jeśli strona do której procesor chce się odwołać nie znajduje się w cache - wykonanie programu jest wstrzymywane i strona jest ładowana. To, którą stronę w cache zastąpić nową zawartością - to jeden z tematów na doktorat.
Oddzielnym zagadnieniem jest synchronizacja zapisywanych danych. Nie może dojść do sytuacji że jeden procesor zapisze coś do do pamięci, ale to utknie w jego lokalnym cache i inny procesor będzie dalej czytać starą wartość. Na to poświęca się sporą część z tych milionów tranzystorów jakie są pakowane w krzem.
Że to wszystko wymaga czasu - no cóż, "taką mamy pamięć". Dlatego szybkie procesory mają po kilka poziomów pamięci cache o różnych szybkościach, dlatego rozdziela się cache programu i danych. Temu też służą algorytmy przewidywania skoków i cała masa innej magii zaimplementowanej w nowoczesnym procesorze.
Na szybkość działania programu bardzo duży wpływ ma też to jak zaplanujesz dostępy do pamięci. Numerycy bardzo nie lubią operować na tablicach wielowymiarowych, bo to potrafi dodać sporo niepotrzebnych przeładowań stron. Zamiast tego indeksy są mapowane do liniowego obszaru pamięci i jak trzeba obliczyć stan w następnym kroku symulacji - solwer jedzie po kolejnych komórkach nie troszcząc się o indeksy (oczywiście wszystkie dane wejściowe są odpowiednio przygotowane). Zrób kiedyś eksperyment: zaalokuj wielką tablicę dwu-wymiarową i przeskanuj ją iterując najpierw po wierszach później po kolumnach, a później odwróć kolejność iteracji: najpierw po kolumnach później po wierszach. Przekonasz się o ile szybciej program będzie działać kiedy będziesz odwoływać się do pamięci bez skakania po stronach.
W dniu niedziela, 5 października 2014 12:01:53 UTC+2 użytkownik Jacek Radzikowski napisał:
Fakt, że nie jest to odwzorowanie "wielkiego" obszaru pamiąci jest oczywisty. Natomiast mechanizm kojarzenia stron jest dla mnie niezrozumiały. Od strony HW, mamy jakiś tam adres zapisany na n-bitach. Jasne, że możemy ten adres w przypadku "dużych" pamięci podzielić na strony, bądź innymi słowy na kostki pamięci. OK, no ale wtedy cykl dostępu do pamięci to 2 kliknięcia zegarka na licznik adresowy, bądź 2 rozkazy zapisu od strony procka do jakiegoś tam rejestru adresowego. O co mi chodzi? Nosz kurdelebelans, nie da się z jednej kostki odczytać w tym samym czasie danych z 2-ch różnych adresów!! No bo niby jak ? Zakładam że kostka ma liniową przestrzeń adresową A(N downto 0). Szerokość słowa danych nie ma znaczenia.
A skąd owa tablica ma wiedzieć o wynikach działania programu/obliczeń i jak przypisać skoki tam gdie trzeba? Czyżby kompilator najpierw wykonywał wszelakia możliwe obliczenia, a następnie odpowiednio to kompilował? David Copperfield?
Bez jaj. Tego się nie da zrobić w sposób predykcyjny z poziomu kompilatora. Jeżeli ktoś podejmie się takiego doktoratu, to równie dobrze może się chwycić za doktorat z wróżenia z fusów.
To jest oczywiste. Implikacja tego co napisałem wcześniej.
Ano właśnie ta magia.. Na czym owa predykcja polega? Może się mylę, ale coś mi tu pachnie marketingowym bełkotem.
Hah!! Właśnie ja tak robię. Dzięki paru GB pamięci, DSP mogę robić na najpodlejszym laptopie w czasie rzeczywistym.
Upsss.. Nie za bardzo kojarzę.
Bez jaj !! Poważnie? Kurde, zrobię taki eksperyment, ale aż wierzyć mi się nie chce. Załóżmy że masz rację. No ale wróćmy do realu. Załóżmy że potrzebuję w koło macieju w jakiejś tam pętli odczytywać dane pomiarowe, z tych danych jest tworzona macierz (NxN), robimy z niej macierz odwrotną, następnie wykonujemy jakieś tam czary mary na elementach a(i,j), potem liczymy z tego wyznacznik i cholera wie co jeszcze. No i jak w takim burdelu mam zapanować nad stronicowaniem? Kompilator to zrobi za mnie? Nie wierzę !!
==============
Cholera, na grupie elektronicznej w zasadzie zjechaliśmy na matematykę. Ale cóż, nowoczesna elektronika bez matematyki/algorytmiki nie może funkcjonować.
Odpowiedź napiszę po po łacinie, jest częściowo podobna do polskiego, ale bardziej zwięzłą ;-)
Nie jest to do końca równoznaczne z dwoma różnymi kompami. Pewne rzeczy nadal są wspólne, jak L2 i L3 czy rurka łącząca cache z RAM.
Nie wiem, co to jest kostka pamięci. To naprawdę zależy od tego, na czym piszesz. Niby grupa elektronika, ale zakładam, że to x86/x64, arm będzie miał podobnie, 8051 miał tylko jeden rdzeń ;-)
Tak więc dane siedzą w RAM. Jeśli operacja jest szybka, jak dodawanie, najbardziej kosztowną operacją będzie sprowadzenie danych da cache. I tutaj wiele rdzeni praktycznie nic nie pomaga, bo rurka RAM-cache jest jedna, i ma ograniczoną przepustowość *)
Jeśli operacja jest bardziej skomplikowana i zajmuje dużo czasu, możesz mieć przyspieszenie nawet do x(ilość rdzeni).
*) A przynajmniej tak mi się wydaje, chyba jednak czegoś nie wiem;-)
Jednak każdy rdzeń ma własną rurkę, czy automatyczny prefetching daje ciała?
Gdzie > W dniu niedziela, 5 października 2014 00:41:48 UTC+2 użytkownik A. L. > napisał:
I właśnie na to pytanie odpowiedź znajdziesz, czytając o cache.
L1 każdy procek ma własne. Te same dane mogą być w cache każdego rdzenia i być swobodnie czytane, nie przeszkadza to nikomu. Jeśli ktoś jednak zmodyfikuje coś, informacja o tym wędruje po procesorze i jeśli inny rdzeń będzie chciał odczytać tę informację, zobaczy, że jest ona oznaczona jako 'nieaktualna' i ściągnie ją raz jeszcze z wyższego poziomu.
Oczywiście, nie zabezpiecza to przed race condition, stąd potrzeba użycia przy zapisywaniu i odczytywaniu tych samych danych poprzez różne wątki tej całej zoologii narzędzi rozproszonych;)
W dniu niedziela, 5 października 2014 14:30:25 UTC+2 użytkownik bartekltg napisał: [ciach]
Wyciachałem, coby poprzez zmniejszoną ilość tekstu dalsza dyskusja była bardziej czytelna. Zarówno dla mnie, dla Ciebie i Zainteresowanych wątkiem. Szczególy są do odczytania w poprzednich wpisach.
1) Dzięki za podany przykład w języku krzaczastym (C, znasz moje zdanie w tym temacie, ale proszę nie "uruchamiajmy" się w dyskusję Pascal/C, bo będzie awantura/pyskówa).
2) Napisałeś jak to napisać, aby działało zgodnie z oczekiwaniem programisty. Chyba mnie nie zrozumiałeś. To nie chodzi o to że a^2+b^2=c^2, tylko DLACZEGO a^2+b^2=c^2 !! Chodzi o to magiczne słowo "dlaczego?".
Wiem, że nie wiem jak w szczegółach działa mechanizm multicore/multithreade.
Odnoszę wrażenie, że umiesz ten mechanizm wykorzystywać, ale jak to funguje to chyba podobnie jak i ja za bardzo nie wiesz. Ot jak moja Kobita. Autem jeździ, ale zasady działania silnika nie zna.
Zapominasz o jednym. Odczyt jednego bajtu z ramu zajmuje niemal tyle samo czasu co odczyt 128 bajtów. Sczytuje się wiec na raz całą linię cache albo i więcej (nie wiem, co w tej dyskusji robi słowo "strona").
Wyobraź sobie, że składasz wibratory na atmega.
Bez cache zamawiasz w TME jedeną sztukę. Przychodzi za tydzień. lutujesz w kilka godzin, zamawiasz kolejną, przychodzi za tydzień.
Z cache zamawiasz na raz 200 procków. czekasz tydzeiń, Lutujesz
100 ... sztuk produktu w trzy tygodnie (bo po zlutowaniu sięgnięcie na półkę po następny procek zajmuje 30s, a nie tydzień) i zamawiasz kolejne 200, czekasz tydzień na dostawę.
Dodatkowo dla dostępu sekwencyjnego mamy coś takiego jak prefetching, albo Ty mozesz przewidzieć, żę potrzebujesz jeszcze wiećej niż standardowa paczka i zamawiać na przyszłość, albo i sam dostawca zauważa schemat i podsyła Ci pod dzwi kolejną paczkę.
Bez cache zawsze byłoby wolniej. Sprowadzenie bajtu czy całej linii to tyle samo roboty, a jeśli linię zapamiętamy sobie w podręcznym schowku, to być mozę się te dane za moment przydadzą. Jeśli tak, mamy je natychmiast, jeśli nie, strata jest pomijalna.
Musisz pozbyć się wyobrażenia z 8051, gdzie zapytanie XRAM o komórkę pamięci to dwa (nie pamietam dokłądnie) cykle procesora. W ciagu Zapytanie współczesnego szybkiego procesora (x86, ARM) o pamieć z ram to wysłanie listu z zapotrzebowaniem do magazynu na drugim końcu kraju. Aby działać sprawnie, trzeba trochę energii poświęcić na logistykę.
Pleciesz. Tablica translacji nie ma nic wspolnego z przewidywaniem skoków.
O przywidywaniu skoków, nie tablicy translacji.
Nie. Procek zgaduje. Jeśli ostatnio 10 razy test na mniejszość wypadł pozytywnie, to zakłada, ze tak dalej będzie. Pod koniec pętli for oczywisćie to zgadniecie jest niepoprwne. I co z tego, sprowadziliśmy pamięć, która była niepotrzebna. Jakbyśmy tego nie zrobili, zużylibyśmy mniej prądu, ale nic dla samych obliczeń się nie zmieni, i tak musimy sprowadzić jakieś inne dane.
A moze byś jednak wziął internet i go poczytał;-)
Nikt nie mówił o kompilatorze. On to tez robi, ale niezależnie. Ustawia tam skoki, aby skok wymagany był w mniej prawdopodobnym przypadku.
Co jest prawdopodobne? Możesz kompilatorowi powiedzieć, a możesz postestować. poczytaj o :
-fprofile-generate
-fprofile-use
Ale to zupełnie inny mechanizm niż przewidywanie skoku przez procek.
Mylisz się. Niech by ta predyckja działałą 50/50, już byłaby korzyść. Jeśli jakieś cześci procesora nic nie robią w jakejś chwili, niech robią choćby coś, co się przyda na 50%. A w takiej pętli po 1010 elementów predykcja trafi ~1000 razy.
Zobacz, jak BLAS(i praktycznie wszystko) trzyma macierz.
Jeszce lepiej. Napisz mnożenie macierzy. C=A*B. będziesz miał tam trzy pętle for i for j for k
Poprzestawiaj kolejność pętli (zachowując sens matematyczny), przyszpieszenie potrafi być 10 krotne*). Jeszcze bardziej dopieszczając traktowanie cache można zbić prędkość
3 razy*) prostą pętlą i kolejne 4 razy*) jak naprawdę wiesz, co robisz (czytaj, biblioteka).
formatting link
*) konkretne wartosći przyszpieszń mocno zależą od procesora. Jak testowałem cuit inne wyniki były.
Jakim znowu stronnicowaniem? Sprawdź, co znaczy to pojęcie, a o czym tu rozmawiacie.
Nie wierzę w to kierowanie przez GPS. Skąd mechanik auta ma wiedzieć, gdzie będę jechać!!
Procesror i kontroler pamięci to za Ciebie robi, nie kompilator.
Dnia Sun, 5 Oct 2014 04:16:25 -0700 (PDT), snipped-for-privacy@gmail.com
To robi sprzet a nie program. Ale owszem, trwa.
No, pamieci dwuportowe sa, moga byc i wiecej portowe, ale glowny RAM taki nie jest. Natomiast cache ... kto wie.
Nie, to sie dzieje automatycznie.
Masz pamiec cache C, moze i 32-bit, ale podzielona na ramki po np 16 bajtow. Adres w niej dzielimy bitowo na f:w, gdzie f to nr ramki, a w
- slowa/bajtu w ramce. Podobnie pamiec glowna R, gdzie adres dzielimy na p:f:w. f i w w obu pamieciach sa takie same, wiec kazda ramka f:* w C jest przypisana do jednej z mozliwych lokalizacji *:f:* w pamieci R. Do ktorej aktualnie - to jest zapisane w osobnej pamieci S, ktora przechowuje starsza czesc adresu p.
No i teraz - jak procesor ma potrzebuje siegnac do jakiegos adresu pamieci, to dzieli go na p:f:w, odczytuje S(f), i jesli tam jest akurat p, to wie ze moze odczytac z pamieci C(f:w). A jesli nie ma, to przepisujemy cala ramke R(p:f:*) do cache C(f:*), a do S(f) zapisujemy p. I nastepnym razem juz jest. Sam odczyt calej ramki z SDRAM idzie w miare szybko, bo sa do tego stosowne funkcje.
Tak wyglada pierwsza wersja, ktora ma te wade, ze procesor moze sie odwolywac do roznych obszarow pamieci o przypadkowo zgodnym f. Wiec powiekszamy pamiec C np 4 razy, adresujac ja s:f:w, dajemy 4 pamieci S - nazwijmy je S0 do S3, i teraz jesli procesor potrzebuje adresu p:f:w, odczytujemy wszystkie Sn(f), sprawdzamy czy jest w ktorejs p, i jesli jest, do odczytujemy dane z C(n:f:w). A jak nie ma, to dobrze by bylo znalezc najdawniej uzywane n, po czym ponownie przepisujemy ramke do C(n:f), i w odpowiednia Sn(f) wpisujemy p.
To wszystko robi sprzet wbudowany w procesor, a moze wrecz zewnetrzny kontroler, tylko w procesorze szybciej.
No, to sie raczej nowym procesorom przypisuje. Predykcja adresow itp.
No, potrafi byc np taka ze jak jest skok warunkowy w tyl, to zaklada sie ze on bedzie, i wstepnie odczytuje rozkaz spod adresu skoku. Bo to jakas petla w programie jest, a petla jest po to aby sie petlic :-)
Jak trzeba to trzeba i tego nie unikniesz. Zlosliwe jest tu raczej mnozenie, potrzebne do obliczenia adresu, plus np to ze robisz funkcje biblioteczna, ktora nie zna rozmiaru, wiec kompilator nie moze zoptymalizowac, a czesto nawet nie umozliwia .
Patrzac na opis powyzej, to cache nie lubi: a) obszarow polozonych pod "okraglymi" adresami, bo jak sie okaze ze np jedna tablica jest pod 1A0000, druga pod 1B0000 a trzecia pod 1D000 i chcemy dodac z pierwszej i drugiej i zapisac w trzeciej, to za wszystkie maja te sama czesc adresu f i koliduja w cache. Lepiej zdac sie na dynamiczny przydzial pamieci, moze lepiej rozrzuci.
b) skakania po adresach co kilkanascie bajtow - my tu cachujemy cala ramke, a program uzywa z niej 1 bajt i przeskakuje do nastepnej.
W dniu niedziela, 5 października 2014 15:21:41 UTC+2 użytkownik bartekltg napisał:
W zapędach wycinania wyciąłem chyba pytanie "jak to działa?" , a nie "dlaczego?". Być może, ale nie chce mi się przeglądać dyskusji od początku.W ogóle chyba (?) stricte takiego pytania nie zadałem. Nie neguję sensu implementowania w prockach pamięci cache, nie neguję sensu produkowania procków wielordzeniowych/programowania wielowątkowego, ale po prostu pytam jak jest to zrealizowane. W notach aplikacyjnych HW/SW jest napisane jak to obsługiwać, ale jak jest to zrobione to ni cholery. Pytanie ot, z czystej ciekawości. Ale są pewne wątpliwości o których wcześniej napisałem. Czy aby w pewnych szczególnych przypadkach częstych i dłuuugich skoków ten mechanizm jest porządany? Sądzę, że w takich przypadkach może być wręcz szkodliwy.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.