Deoptymizacja programu dla rurociągu w procesorach z rodziny Intel Sandybridge
Od tygodnia męczę się nad tym zadaniem i mam nadzieję, że ktoś poprowadzi mnie na właściwą drogę. Zacznę od instrukcji instruktora:
Zadanie dawało wybór programów Whetstone ' a lub Monte-Carlo. Komentarze cache-effectiveness dotyczą głównie Whetstone ' a, ale wybrałem Monte-Carlo program symulacyjny:Twoje zadanie jest przeciwieństwem naszego pierwszego zadania laboratoryjnego, które polegało na optymalizacji programu liczb pierwszych. Twoim celem w tym zadaniu jest pesymizacja programu, czyli spowolnienie jego działania. Oba te programy są obciążające procesor. Uruchomienie naszych komputerów zajmuje kilka sekund. Ty nie może zmienić algorytmu.
Aby dezoptymizować program, wykorzystaj swoją wiedzę na temat działania potoku Intel i7. Wyobraź sobie sposoby zmiany kolejności ścieżek instrukcji, aby wprowadzić zagrożenia wojenne, surowe i inne. Pomyśl o sposobach zminimalizowania skuteczności pamięci podręcznej. Bądź diabolicznie niekompetentny.
// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm> // Needed for the "max" function
#include <cmath>
#include <iostream>
// A simple implementation of the Box-Muller algorithm, used to generate
// gaussian random numbers - necessary for the Monte Carlo method below
// Note that C++11 actually provides std::normal_distribution<> in
// the <random> library, which can be used instead of this function
double gaussian_box_muller() {
double x = 0.0;
double y = 0.0;
double euclid_sq = 0.0;
// Continue generating two uniform random variables
// until the square of their "euclidean distance"
// is less than unity
do {
x = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
y = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
euclid_sq = x*x + y*y;
} while (euclid_sq >= 1.0);
return x*sqrt(-2*log(euclid_sq)/euclid_sq);
}
// Pricing a European vanilla call option with a Monte Carlo method
double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
double S_adjust = S * exp(T*(r-0.5*v*v));
double S_cur = 0.0;
double payoff_sum = 0.0;
for (int i=0; i<num_sims; i++) {
double gauss_bm = gaussian_box_muller();
S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
payoff_sum += std::max(S_cur - K, 0.0);
}
return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}
// Pricing a European vanilla put option with a Monte Carlo method
double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
double S_adjust = S * exp(T*(r-0.5*v*v));
double S_cur = 0.0;
double payoff_sum = 0.0;
for (int i=0; i<num_sims; i++) {
double gauss_bm = gaussian_box_muller();
S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
payoff_sum += std::max(K - S_cur, 0.0);
}
return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}
int main(int argc, char **argv) {
// First we create the parameter list
int num_sims = 10000000; // Number of simulated asset paths
double S = 100.0; // Option price
double K = 100.0; // Strike price
double r = 0.05; // Risk-free rate (5%)
double v = 0.2; // Volatility of the underlying (20%)
double T = 1.0; // One year until expiry
// Then we calculate the call/put values via Monte Carlo
double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
double put = monte_carlo_put_price(num_sims, S, K, r, v, T);
// Finally we output the parameters and prices
std::cout << "Number of Paths: " << num_sims << std::endl;
std::cout << "Underlying: " << S << std::endl;
std::cout << "Strike: " << K << std::endl;
std::cout << "Risk-Free Rate: " << r << std::endl;
std::cout << "Volatility: " << v << std::endl;
std::cout << "Maturity: " << T << std::endl;
std::cout << "Call Price: " << call << std::endl;
std::cout << "Put Price: " << put << std::endl;
return 0;
}
Wprowadzone przeze mnie zmiany wydłużyły czas działania kodu o sekundę, ale nie jestem do końca pewien, co mogę zmienić, aby zatrzymać potoki bez dodawania kodu. Punkt w dobrym kierunku byłby super, doceniam wszelkie odpowiedzi.
Update: profesor, który dał to zadanie zamieścił kilka szczegółów
Najważniejsze są:
- to drugi semestr zajęć z architektury w szkole (z wykorzystaniem podręcznika Hennessy ' ego i Pattersona).
- Komputery laboratoryjne mają procesory Haswell
- uczniowie zapoznali się z instrukcją
CPUIDi sposobem określania wielkości pamięci podręcznej, a także z instrukcjąCLFLUSH. - wszelkie opcje kompilatora są dozwolone, podobnie jak inline asm.
- pisanie własnego algorytmu pierwiastka kwadratowego zostało ogłoszone jako poza bladą
Komentarze Cowmoogun w Meta wątku wskazują, że nie było jasne częścią tego mogą być optymalizacje kompilatorów i zakłada się -O0, i że 17% wzrost czasu pracy był rozsądny.
Wygląda na to, że celem zadania było nakłonienie uczniów do ponownego uporządkowania istniejącej pracy, aby zmniejszyć równoległość na poziomie nauczania lub tego typu rzeczy, ale to nie jest zła rzecz, że ludzie zagłębiali się głębiej i uczyli się więcej.
Należy pamiętać, że jest to pytanie o architekturę komputera, a nie o to, jak zwolnić C++ w Generale.
1 answers
Ważne lektury: mikroarchitektura Agner Fog, i prawdopodobnie również Ulricha Dreppera , co każdy programista powinien wiedzieć o pamięci . Zobacz także inne linki w x86 tag wiki, zwłaszcza podręczniki optymalizacji Intela, i David Kanter analiza mikroarchitektury Haswella, ze schematami.
Bardzo fajne zadanie; dużo lepsze niż te, które widziałem gdzie uczniowie zostali poproszeni o optymalizację niektórych kod dla gcc -O0, nauczenie się kilku sztuczek, które nie mają znaczenia w prawdziwym kodzie. W takim przypadku zostaniesz poproszony o zapoznanie się z potokiem procesora i wykorzystanie go do kierowania wysiłkami de-optymalizacji, a nie tylko ślepym zgadywaniem. najbardziej zabawną częścią tego jest usprawiedliwianie każdego pesymizmu "diaboliczną niekompetencją", a nie celową złośliwością.
Problemy z przypisaniem i kodem :
Opcje specyficzne dla uarch dla tego kodu to ograniczona. Nie używa żadnych tablic, a duża część kosztów To połączenia z exp/log funkcje biblioteczne. Nie ma oczywistego sposobu, aby mieć mniej lub bardziej równoległy poziom instrukcji, a łańcuch zależności przenoszony w pętli jest bardzo krótki.
Chciałbym zobaczyć odpowiedź, która próbowała uzyskać spowolnienie od zmiany aranżacji wyrażeń w celu zmiany zależności, aby zmniejszyć ILP tylko z zależności (zagrożenia).Nie próbowałem.
Intel Procesory z rodziny Sandybridge są agresywnymi, niekonwencjonalnymi konstrukcjami, które zużywają dużo tranzystorów i mocy, aby znaleźć równoległość i uniknąć zagrożeń (zależności), które mogłyby utrudnić klasyczny rurociąg w kolejności RISC[99]. Zwykle jedynymi tradycyjnymi zagrożeniami, które go spowalniają, są surowe" prawdziwe " zależności, które powodują, że przepustowość jest ograniczona opóźnieniami.
WAR I WAW hazards dla rejestrów nie stanowią problemu, dzięki zmianie nazwy rejestru. (z wyjątkiem popcnt/lzcnt/tzcnt, które mają fałszywą zależność ich przeznaczenia od procesorów Intela , mimo że są tylko do zapisu. czyli WAW jest traktowany jako Zagrożenie surowe + zapis). W przypadku pamięci podręcznej, procesory używane są do przechowywania kolejek, aby opóźnić przejście do pamięci podręcznej aż do przejścia na emeryturę, a także uniknąć zagrożeń wojennych i WAW .
Podsumowanie dobrych pomysłów, które diaboliczna niekompetencja może uzasadnić
Nawet diabolicznie niekompetentni są mało prawdopodobne, aby dodać oczywiście bezużyteczną pracę lub nieskończoną pętlę, a Robienie bałaganu z klasami C++ / Boost jest poza zakres zadania.
- multi-thread with a single shared
std::atomic<uint64_t>Licznik pętli, więc następuje właściwa całkowita liczba iteracji. Atomic uint64_t jest szczególnie zły z-m32 -march=i586. Aby uzyskać punkty bonusowe, ułóż układ, aby był on wyrównany i przekroczył granicę strony z nierównym podziałem (nie 4: 4). - False sharing dla innej nieatomowej zmiennej - > memory-order mis-Specification pipeline clears, a także extra cache pudło.
- zamiast używać
-na zmiennych FP, XOR wysoki bajt z 0x80, aby odwrócić bit znaku, powodując Store-forwarding strachy . - czas każdej iteracji niezależnie, z czymś nawet cięższym niż
RDTSC. np.CPUID/RDTSClub funkcja czasu, która wykonuje wywołanie systemowe. Instrukcje serializujące są z natury nieprzyjazne dla potoków. - Zmiana mnoży się przez stałe do dzielenia przez ich wzajemność ("dla ułatwienia czytania"). div jest powolny i nie do końca.
- Wektoryzować mnożenie/sqrt za pomocą AVX (SIMD), ale nie używać
vzeroupperprzed wywołaniem skalarnej biblioteki math-libraryexp()ilog()funkcji, powodując AVXSSE transition strachy. - przechowuj wyjście RNG w połączonej liście lub w tablicach, które przesuwasz niezgodnie z kolejnością. To samo dla wyniku każdej iteracji i sumy na końcu.
Również zawarte w tej odpowiedzi, ale wyłączone z podsumowania: sugestie, które byłyby tak samo powolne na procesorze nie-pipelinowanym, lub to nie wydaje się być uzasadnione nawet przy diabolicznej niekompetencji. np. wiele pomysłów gimp-the-compiler, które produkują oczywiście inny / gorszy asm.
Wielowątkowość
Może używać OpenMP do pętli wielowątkowych z bardzo małą liczbą iteracji, ze znacznie większym obciążeniem niż przyrost prędkości. Twój kod monte-carlo ma wystarczająco podobieństwa, aby przyspieszyć, esp. jeśli uda nam się spowolnić każdą iterację. (Każdy wątek oblicza część payoff_sum, dodaną na końcu). #omp parallel w tej pętli byłaby prawdopodobnie optymalizacja, a nie pesymizacja.
Wiele wątków, ale zmuszają oba wątki do współdzielenia tego samego licznika pętli (przy przyrostach atomic, więc całkowita liczba iteracji jest poprawna).To wydaje się diabolicznie logiczne. Oznacza to użycie zmiennej static jako licznika pętli. To uzasadnia użycie atomic dla liczników pętli i tworzy rzeczywiste ping-ponging linii pamięci podręcznej (o ile wątki nie działają na tym samym fizycznym rdzeniu z hyperthreading; może to nie być jako powolne). W każdym razie, to jest znacznie wolniejsze niż sprawa bez zarzutu dla lock inc. I lock cmpxchg8b aby atomicznie zwiększyć argument uint64_t na 32-bitowym systemie będzie musiał ponowić próbę w pętli, zamiast mieć sprzęt rozstrzygać atomowe inc.
Tworzy również false sharing, gdzie wiele wątków przechowuje swoje prywatne dane (np. stan RNG) w różnych bajtach tego samego linia pamięci podręcznej. [[199]}(samouczek Intela o tym, w tym liczniki perf do obejrzenia) . Procesory Intela spekulują na temat błędnego porządkowania pamięci , a nie, i istnieje , aby wykryć to zdarzenie, przynajmniej na P4. Kara może nie być tak duża dla Haswella. Jak wskazuje ten link, Instrukcja locked zakłada, że tak się stanie, unikając błędnych spekulacji. Normalne obciążenie spekuluje, że inne rdzenie nie unieważnią linii pamięci podręcznej pomiędzy momentem wykonania obciążenia a momentem jego wycofania w kolejności programowania (, chyba że użyjesz pause). Prawdziwe udostępnianie bez lockinstrukcji ed jest zwykle błędem. Interesujące byłoby porównanie nieatomowego licznika współdzielonej pętli z atomowym przypadkiem. Aby naprawdę pesymizować, zachowaj współdzielony licznik pętli atomowej i spowoduj fałszywe udostępnianie w tej samej lub innej linii pamięci podręcznej dla innej zmiennej.
Random uarch-konkretne pomysły:
Jeśli możesz wprowadzić dowolne nieprzewidywalne gałęzie , to znacznie poprawi kod. Nowoczesne procesory x86 mają dość długie potoki, więc błędny odczyt kosztuje ~15 cykli (podczas uruchamiania z pamięci podręcznej uop).
Łańcuchy zależności:
Myślę, że to była jedna z zamierzonych części zadania.Pokonanie zdolności procesora do wykorzystania równoległości na poziomie instrukcji poprzez wybór kolejności operacji, która ma jeden długi łańcuch zależności zamiast wielu krótkich łańcuchów zależności. Kompilatory nie mogą zmieniać kolejności operacji dla obliczeń FP, chyba że użyjesz -ffast-math, ponieważ może to zmienić wyniki (jak opisano poniżej).
Aby było to naprawdę skuteczne, zwiększ długość łańcucha zależności przenoszonego w pętli. Nic jednak nie jest tak oczywiste: zapisane pętle mają bardzo krótkie łańcuchy zależności: wystarczy dodać FP. (3 cykle). Wiele iteracji może mają swoje obliczenia w locie na raz, ponieważ mogą rozpocząć się na długo przed payoff_sum += pod koniec poprzedniej iteracji. (log() i exp pobierają wiele instrukcji, ale niewiele więcej niż okno out-of-order Haswella do znalezienia równoległości: ROB size=192 fused-domain UOPs, and scheduler size=60 unfused-domain UOPs . Gdy tylko wykonanie obecnej iteracji postępuje wystarczająco daleko, aby zrobić miejsce na instrukcje z następnej iteracji do wydania, wszelkie jej części, które mają ich wejścia gotowe (tj. niezależny / oddzielny łańcuch dep) mogą rozpocząć wykonywanie, gdy starsze instrukcje pozostawią jednostki wykonawcze wolne (np. ponieważ są wąskie pod względem opóźnień, a nie przepustowości.).
Stan RNG będzie prawie na pewno dłuższym łańcuchem zależności z pętlą niż addps.
Użyj wolniejszych / więcej operacji FP (esp. podział większy):
Dziel przez 2.0 zamiast mnożyć przez 0.5, i tak dalej. FP multiply jest mocno w Intelu projektuje i ma jedną przepustowość na 0,5 c w Haswell i Później. FP divsd/divpd jest tylko częściowo rurociągiem . (Chociaż Skylake ma imponującą przepustowość 4c dla divpd xmm, z opóźnieniem 13-14c, a nie w ogóle na Nehalem (7-22C))).
do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); jest wyraźnie testowany na odległość, więc wyraźnie byłoby właściwe sqrt() to. :P (sqrt jest nawet wolniejszy niż div).
Jak sugeruje @ Paul Clayton, przepisywanie wyrażeń za pomocą asocjacyjnych / dystrybucyjnych odpowiedniki mogą wprowadzić więcej pracy(o ile nie używasz -ffast-math, aby umożliwić kompilatorowi ponowną optymalizację). (exp(T*(r-0.5*v*v)) może stać się exp(T*r - T*v*v/2.0). Zauważ, że podczas gdy matematyka na liczbach rzeczywistych jest asocjacyjna, matematyka zmiennoprzecinkowa jest Nie, nawet bez uwzględnienia przepełnienia/NaN (dlatego -ffast-math nie jest domyślnie włączony). Zobacz komentarz Pawła {[99] } dla bardzo włochatego zagnieżdżonego pow() sugestii.
Jeśli możesz skalować obliczenia do bardzo małych liczb, to FP math ops weź ~120 dodatkowych cykli, aby złapać mikrokod, gdy operacja na dwóch normalnych liczbach wytwarza denormalną . Zobacz mikroarchitekturę Agner Fog pdf, aby uzyskać dokładne liczby i szczegóły. Jest to mało prawdopodobne, ponieważ masz wiele mnożenia, więc współczynnik skali byłby kwadratowy i zaniżony aż do 0,0. Nie widzę sposobu, aby uzasadnić konieczne skalowanie niekompetencją( nawet diaboliczną), tylko celową złośliwością.
Jeśli możesz użyć wewnętrznych (<immintrin.h>)
Użyj movnti, aby usunąć dane z pamięci podręcznej. Diabolical: jest nowy i słabo uporządkowany, więc powinno pozwolić procesorowi działać szybciej, prawda? Lub zobacz to powiązane pytanie w przypadku, gdy ktoś był w niebezpieczeństwie zrobienia dokładnie tego (dla rozproszonych pisze, gdzie tylko niektóre miejsca były gorące). To prawdopodobnie niemożliwe bez złośliwości.
Użyj tasowania liczb całkowitych między operacjami matematycznymi FP, aby spowodować opóźnienia obejścia.
Miksowanie SSE i AVX instrukcje bez właściwego użycia vzeroupper powoduje duże stragany w przed-Skylake (W Skylake ' U pojawia się również postać z gry. Nawet bez tego wektoryzacja może być gorsza niż Skalar (więcej cykli spędzonych na tasowaniu danych do / Z wektorów niż zapisanych przez wykonywanie operacji add/sub/mul/div / sqrt dla 4 iteracji Monte-Carlo na raz, z 256b wektorami). jednostki wykonawcze add / sub / mul są w pełni pipelinowe i o pełnej szerokości, ale div I sqrt na wektorach 256b nie są tak szybkie jak na 128B wektory (lub Skalary), więc przyspieszenie nie jest dramatyczne dla double.
exp() i log() nie mają wsparcia sprzętowego, więc ta część wymagałaby wyodrębnienia elementów wektorowych z powrotem do skalara i oddzielnego wywołania funkcji biblioteki, a następnie przetasowania wyników z powrotem do wektora. libm jest zazwyczaj kompilowany tylko w celu użycia SSE2, więc będzie używał kodu legacy-SSE skalarnych instrukcji matematycznych. Jeśli twój kod używa wektorów 256b i wywołuje exp bez wykonywania vzeroupper najpierw, to przeciągasz. Po zwracając, Instrukcja AVX-128, taka jak vmovsd, aby ustawić następny element wektora jako arg dla exp, również zostanie wstrzymana. I wtedy exp() znów się zatrzyma, gdy uruchomi instrukcję SSE. To właśnie stało się w tym pytaniu , powodując 10-krotne spowolnienie.[[100]} (Dzięki @ZBoson).
Zobacz także eksperymenty Nathana Kurza z lib matematyki Intela vs. glibc dla tego kodu . W przyszłości glibc pojawią się z wektoryzowanymi implementacjami exp() i tak on
Jeśli celują w pre-IvB, lub esp. Nehalem, Postaraj się aby gcc powodowało partial-register z operacjami 16-bitowymi lub 8-bitowymi, a następnie z operacjami 32-bitowymi lub 64-bitowymi. W większości przypadków gcc użyje movzx po operacji 8 lub 16-bitowej, ale oto przypadek, w którym GCC modyfikuje ah, a następnie odczytuje ax
Z (inline) asm:
Z (inline) asm, można złamać UOP cache: 32B kawałek kodu, który nie mieści się w trzech 6uop cache lines wymusza przełączenie z pamięci podręcznej uop na Dekodery. Niekompetentny ALIGN używanie wielu jednobajtowych nopS zamiast kilku długich nopS na gałęzi docelowej wewnątrz wewnętrznej pętli może załatwić sprawę. Lub umieść wyściełanie wyrównania za etykietą, zamiast przed. : P to ma znaczenie tylko wtedy, gdy frontend jest wąskim gardłem, czego nie będzie, jeśli uda nam się pesymizować resztę kodu.
Użyj samoodtwarzającego się kodu, aby wyzwalać czyszczenie potoków (aka maszyny-Atomówki).
LCP z 16-bitowych instrukcji o zbyt dużych rozmiarach, aby zmieścić się w 8 bitach jest mało prawdopodobne, aby były użyteczne. Pamięć podręczna uop na SnB i Później oznacza, że kara za dekodowanie jest płacona tylko raz. Na Nehalem (pierwszym i7) może działać dla pętli, która nie mieści się w buforze pętli 28 uop. gcc czasami generuje takie instrukcje, nawet z -mtune=intel i kiedy mógł użyć 32-bitowej instrukcji.
Częstym idiomem na czas jest CPUID(do serializacji) wtedy RDTSC. Czas każda iteracja osobno z CPUID/RDTSC aby upewnić się, że {[10] }nie jest ponownie uporządkowany z wcześniejszymi instrukcjami, co spowolni sprawę lot. (W prawdziwym życiu inteligentnym sposobem na czas jest zmierzenie wszystkich iteracji razem, zamiast mierzyć każdą osobno i dodawać je do siebie).
Powoduje wiele braków pamięci podręcznej i innych spowolnień pamięci
Użyj union { double d; char a[8]; } dla niektórych zmiennych. przyczyna a stoisko sklepowo-spedycyjne wykonując wąski zapis (lub Read-Modify-Write) tylko do jednego z bajtów. (Ten artykuł wiki obejmuje również wiele innych mikroarchitekturowych rzeczy do kolejek ładowania/przechowywania). na przykład Odwróć znak double używając XOR 0x80 tylko na wysokim bajcie , zamiast operatora -. Diabolicznie niekompetentny programista mógł słyszeć, że FP jest wolniejszy niż integer, a więc próbować zrobić jak najwięcej używając integer ops. (Bardzo dobry kompilator celujący w FP math w rejestrach SSE może skompilować to do xorps ze stałą w innym rejestrze xmm, ale jedynym sposobem, aby nie było to straszne dla x87 jest, jeśli kompilator zda sobie sprawę, że neguje wartość i zastępuje następny add odejmowaniem.)
Użyj volatile jeśli kompilujesz z -O3, a nie używasz std::atomic, aby zmusić kompilator do rzeczywistego przechowywania / przeładowania w całym miejscu. Zmienne globalne (zamiast lokalnych) wymusi również niektóre magazyny/przeładowania, ale C++ słaba kolejność modelu pamięci nie wymaga od kompilatora rozlewania / przeładowywania pamięci przez cały czas.
Zastąp lokalne var-y składnikami dużej struktury, aby móc kontrolować układ pamięci.
Użyj tablic w strukturze do wypełnienia (i przechowywania liczb losowych, aby uzasadnić ich istnienie).
Wybierz układ pamięci, aby wszystko trafiło do innej linii w tym samym "zestawie" w pamięci podręcznej L1. Jest tylko 8-kierunkowy asocjacyjny, tzn. każdy zestaw posiada 8 "sposobów". Linie pamięci podręcznej to 64B.
Jeszcze lepiej, rozłożyć rzeczy dokładnie na 4096B, ponieważ ładunki mają fałszywą zależność od sklepów na różnych stronach, ale z tym samym przesunięciem w obrębie strony. Procesory Intela wykorzystują Dysk pamięci , aby dowiedzieć się, kiedy ładowanie i magazynowanie można zmienić bez zmiany wyników, a implementacja Intela ma fałszywe alarmy, które uniemożliwiają wczesne Ładowanie. Prawdopodobnie sprawdzają tylko bity poniżej przesunięcie strony, więc sprawdzenie może rozpocząć się przed tłumaczeniem wysokich bitów przez TLB ze strony wirtualnej na stronę fizyczną. Jak również przewodnik Agnera, zobacz odpowiedź Stephena Canona, a także sekcję pod koniec odpowiedzi @Krazy Glew na to samo pytanie. (Andy Glew był jednym z architektów oryginalnej mikroarchitektury Intela P6.)
Użyj __attribute__((packed)), aby pozwolić ci źle wyrównać zmienne, aby rozciągały się na linie bufora lub nawet granice strony. (Więc obciążenie jednego double potrzebuje danych z dwóch linii pamięci podręcznej). Niewspółosiowe ładunki nie mają kary w żadnym Intel i7 uarch, z wyjątkiem przekroczenia linii pamięci podręcznej i linii stron. podziały linii pamięci podręcznej nadal wymagają dodatkowych cykli. Skylake drastycznie zmniejsza karę za ładowanie podzielonych stron, ze 100 do 5 cykli. (Sekcja 2.1.3) . Być może związane z możliwością wykonywania dwóch stron równolegle.
Podział strony na atomic<uint64_t> powinien być w najgorszym przypadku, esp. jeśli jest 5 bajtów na jednej stronie i 3 bajtów na drugiej stronie, lub cokolwiek innego niż 4: 4. Nawet podziały w środku są bardziej wydajne dla podziałów linii cache z wektorami 16B na niektórych uarchach, IIRC. Umieść wszystko w alignas(4096) struct __attribute((packed)) (aby zaoszczędzić miejsce, oczywiście), w tym tablicę do przechowywania wyników RNG. Aby osiągnąć niewspółosiowość, użyj uint8_t lub uint16_t dla czegoś przed licznikiem.
Jeśli możesz zmusić kompilator do używania trybów adresowania indeksowanego, to pokonasz mikro-fuzję uop. Może za pomocą #defineS, aby zastąpić proste zmienne skalarne my_data[constant].
Jeśli możesz wprowadzić dodatkowy poziom indrection, więc adresy load/store nie są znane wcześniej, to może się to zmienić.
Tablice Trawersowe w nieciągłym porządku
Myślę, że możemy wymyślić niekompetentne uzasadnienie wprowadzenia tablicy w pierwszej kolejności: pozwala nam to oddzielić generowanie liczb losowych od użycia liczb losowych. Wyniki każdej iteracji można również zapisać w tablica, do podsumowania później (z bardziej diaboliczną niekompetencją).
Dla "maksymalnej losowości", możemy mieć wątek zapętlający tablicę losową, zapisujący do niej nowe liczby losowe. Wątek zużywający liczby losowe może wygenerować indeks losowy, z którego można załadować liczbę losową. (Jest tu trochę make-work, ale mikroarchitektonicznie pomaga to, aby adresy ładowania były znane wcześnie, więc wszelkie możliwe opóźnienia ładowania mogą być rozwiązane, zanim załadowane dane są potrzebne.) Posiadające czytelnika i writer na różnych rdzeniach spowoduje czyszczenie potokăłw ze Ĺ "rodkĂłw pamiÄ ™ ci (jak wspomniano wczeĹ" niej w przypadku false-sharing).
Dla maksymalnej pesymizacji, pętla nad tablicą z krokiem 4096 bajtów(tj. 512 podwaja). np.
for (int i=0 ; i<512; i++)
for (int j=i ; j<UPPER_BOUND ; j+=512)
monte_carlo_step(rng_array[j]);
Więc wzorzec dostępu To 0, 4096, 8192, ...,
8, 4104, 8200, ...
16, 4112, 8208, ...
To jest to, co dostajesz za dostęp do tablicy 2D, takiej jak double rng_array[MAX_ROWS][512] w złej kolejności (zapętlanie wierszy, zamiast kolumny w wierszu w wewnętrznej pętli, zgodnie z sugestią @JesperJuhl). Jeśli diaboliczna niekompetencja może uzasadnić tablicę 2D o takich wymiarach, to prawdziwa niekompetencja garden variety łatwo usprawiedliwia zapętlenie błędnym wzorem dostępu. Dzieje się to w prawdziwym kodzie w prawdziwym życiu.
Dostosuj granice pętli, jeśli jest to konieczne, aby używać wielu różnych stron zamiast ponownie używać tych samych stron, jeśli tablica nie jest taka duża. Wstępne ustawianie sprzętowe nie działa (jak również/w ogóle) na stronach. Prefetcher może śledzić jeden strumień do przodu i jeden do tyłu w obrębie każdej strony( co się dzieje tutaj), ale będzie działać tylko wtedy, gdy przepustowość pamięci nie jest już nasycona przez non-prefetch.
To również wygeneruje wiele błędów TLB, chyba że strony zostaną połączone w hugepage (Linux robi to oportunistycznie dla anonimowych (nie wspieranych plikami) alokacji, takich jak malloc/new to użycie mmap(MAP_ANONYMOUS)).
Zamiast tablicy do przechowywania listy wyników, można użyć linked list . Wtedy każda iteracja wymagałaby obciążenia ścigającego wskaźnik (zagrożenie prawdziwymi zależnościami dla adresu obciążenia następnego obciążenia). Przy złym alokatorze możesz rozproszyć węzły listy w pamięci, pokonując pamięć podręczną. Z diabolicznie niekompetentnym alokatorem, może umieścić każdy węzeł na początku własnej strony. (np. przydzielaj za pomocą mmap(MAP_ANONYMOUS) bezpośrednio, bez rozbijania stron lub śledzenia rozmiarów obiektów, aby prawidłowo obsługiwać free).
Te nie są tak naprawdę specyficzne dla mikroarchitektury i mają niewiele wspólnego z potokiem (większość z nich byłaby również spowolnieniem dla procesora bez pipelina).
Nieco off-topic: make the compiler generate worse code / do more work:
Użyj C++11 std::atomic<int> i std::atomic<double> dla najbardziej pesymistycznego kodu. Instrukcje MFENCEs i locked są dość powolne, nawet bez kontrowersji z innego wątku.
-m32 zrobi wolniejszy kod, bo x87 kod będzie gorszy niż kod SSE2. 32-bitowa konwencja wywołująca oparta na stosie pobiera więcej instrukcji i przekazuje nawet args FP na stosie do funkcji takich jak exp().