Przez tydzień pracowałem nad mózgiem, próbując wykonać to zadanie i mam nadzieję, że ktoś tutaj poprowadzi mnie na właściwą ścieżkę. Zacznę od instrukcji instruktora:
Twoje zadanie jest przeciwieństwem naszego pierwszego zadania laboratoryjnego, które polegało na optymalizacji programu liczb pierwszych. Twoim zadaniem w tym zadaniu jest pesymalizacja programu, tzn. Spowolnienie jego działania. Oba są programami intensywnie wykorzystującymi procesor. Uruchomienie ich na komputerach laboratoryjnych zajmuje kilka sekund. Nie możesz zmienić algorytmu.
Aby zoptymalizować program, wykorzystaj swoją wiedzę na temat działania potoku Intel i7. Wyobraź sobie sposoby zmiany kolejności ścieżek instrukcji, aby wprowadzić WAR, RAW i inne zagrożenia. Pomyśl o sposobach zminimalizowania skuteczności pamięci podręcznej. Bądź diabelnie niekompetentny.
Zadanie dało wybór programów Whetstone lub Monte-Carlo. Komentarze dotyczące skuteczności pamięci podręcznej dotyczą głównie Whetstone, ale wybrałem program symulacyjny Monte-Carlo:
// 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 zablokować potok bez dodawania kodu. Wskazanie właściwego kierunku byłoby niesamowite, doceniam wszelkie odpowiedzi.
Aktualizacja: profesor, który zlecił to zadanie, opublikował kilka szczegółów
Najważniejsze to:
- Jest to drugi semestralny kurs architektury na uniwersytecie (z podręcznika Hennessy i Pattersona).
- komputery laboratoryjne mają procesory Haswell
- Uczniowie zostali zapoznani z
CPUID
instrukcją i sposobem określania wielkości pamięci podręcznej, a także wewnętrznymi elementami iCLFLUSH
instrukcją. - wszelkie opcje kompilatora są dozwolone, podobnie jak wbudowany asm.
- Napisanie własnego algorytmu pierwiastka kwadratowego ogłoszono jako spoza zakresu
Komentarze Cowmoogun dotyczące meta wątku wskazują, że nie było jasne, że optymalizacje kompilatora mogą być częścią tego i zakładano-O0
, i że wzrost czasu działania o 17% był rozsądny.
Brzmi więc to tak, jakby celem zadania było nakłonienie uczniów do zmiany kolejności istniejącej pracy w celu zmniejszenia paralelizmu na poziomie instrukcji itp., Ale nie jest to złe, że ludzie sięgnęli głębiej i nauczyli się więcej.
Pamiętaj, że jest to pytanie dotyczące architektury komputera, a nie pytanie, jak ogólnie spowolnić C ++.
źródło
while(true){}
Odpowiedzi:
Ważna podstawowa lektura: mikroarcha pdf Agner Fog i prawdopodobnie także to, co każdy programista powinien wiedzieć o pamięci Ulricha Dreppera . Zobacz także inne linki wx86otaguj wiki, zwłaszcza podręczniki optymalizacji Intela oraz analizę mikroarchitektury Haswella z diagramami .
Bardzo fajne zadanie; znacznie lepiej niż te, które widziałem, gdzie studenci zostali poproszeni o zoptymalizowanie kodu
gcc -O0
, ucząc 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 poprowadzenia wysiłków związanych z de-optymalizacją, a nie tylko zgadywania. Najbardziej zabawną częścią tego jest usprawiedliwienie każdej pesymizacji „diabelską niekompetencją”, a nie umyślną złośliwością.Problemy z brzmieniem i kodem przypisania :
Opcje specyficzne dla uarch dla tego kodu są ograniczone. Nie używa żadnych tablic, a duża część kosztów to wywołania funkcji
exp
/log
biblioteki. Nie ma oczywistego sposobu na uzyskanie mniej więcej równoległości na poziomie instrukcji, a łańcuch zależności przenoszony przez pętlę jest bardzo krótki.Chciałbym zobaczyć odpowiedź, która próbowała spowolnić od zmiany aranżacji wyrażeń w celu zmiany zależności, aby zmniejszyć ILP tylko z zależności (zagrożeń). Nie próbowałem tego.
Procesory z rodziny Intel Sandybridge to agresywne, niesprawne konstrukcje, 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 zakłócić działanie klasycznego potoku RISC . Zwykle jedynymi tradycyjnymi zagrożeniami, które go spowalniają, są „prawdziwe” zależności RAW, które powodują, że przepustowość jest ograniczana przez opóźnienia.
Zagrożenia związane z WAR i WAW dla rejestrów praktycznie nie stanowią problemu dzięki zmianie nazwy rejestru . (z wyjątkiem
popcnt
/lzcnt
/tzcnt
, które mają fałszywą zależność między miejscem docelowym a procesorami Intela , nawet jeśli jest to tylko do zapisu, tj. WAW jest traktowany jako zagrożenie RAW + zapis). W celu uporządkowania pamięci nowoczesne procesory używają kolejek sklepowych do opóźniania zatwierdzania do pamięci podręcznej aż do wycofania, unikając również zagrożeń związanych z WAR i WAW .Dlaczego Mulsy mają tylko 3 cykle na Haswell, w przeciwieństwie do tabel instrukcji Agnera? ma więcej informacji na temat zmiany nazwy rejestru i ukrywania opóźnienia FMA w pętli produktu kropki FP.
Marka „i7” została wprowadzona wraz z Nehalem (następcą Core2) , a niektóre instrukcje Intela mówią nawet „Core i7”, kiedy wydają się oznaczać Nehalem, ale zachowały markę „i7” dla Sandybridge i późniejszych mikroarchitektur. SnB ma miejsce, gdy rodzina P6 przekształciła się w nowy gatunek, rodzinę SnB . Pod wieloma względami Nehalem ma więcej wspólnego z Pentium III niż z Sandybridge (np. Przeciągnięcia odczytu rejestru i przeciągnięcia odczytu ROB nie zdarzają się w SnB, ponieważ zmieniły się na użycie fizycznego pliku rejestru. Również pamięć podręczna uop i inne wewnętrzne format uop). Termin „architektura i7” nie jest użyteczny, ponieważ nie ma sensu grupowanie rodziny SnB z Nehalem, ale nie z Core2. (Nehalem wprowadził jednak współdzieloną, współdzieloną architekturę pamięci podręcznej L3 do łączenia wielu rdzeni razem. A także zintegrowane układy GPU. Więc na poziomie układu, nazewnictwo ma sens)
Podsumowanie dobrych pomysłów, które diaboliczna niekompetencja może uzasadnić
Nawet diabelnie niekompetentni raczej nie dodadzą oczywiście bezużytecznej pracy lub nieskończonej pętli, a zrobienie bałaganu klasami C ++ / Boost jest poza zakresem przypisania.
std::atomic<uint64_t>
licznikiem pętli, więc ma miejsce odpowiednia całkowita liczba iteracji. Atomowy uint64_t jest szczególnie zły z-m32 -march=i586
. W przypadku punktów bonusowych należy ustawić, aby był wyrównany i przekraczał granicę strony z nierównomiernym podziałem (nie 4: 4).-
zmiennych FP, XOR wysoki bajt z 0x80, aby odwrócić bit znaku, powodując przeciąganie przekazywania do sklepu .RDTSC
. np.CPUID
/RDTSC
lub funkcja czasu, która wykonuje wywołanie systemowe. Instrukcje serializacji są z natury nieprzyjazne dla potoków.vzeroupper
przed wywołaniami skalarnej biblioteki matematycznejexp()
ilog()
funkcji, powodując zatrzymanie przejścia AVX <-> SSE .Również ujęte w tej odpowiedzi, ale wyłączone ze streszczenia: sugestie, które byłyby tak samo powolne na niepotokowym procesorze, lub które nie wydają się uzasadnione, nawet przy diabelskiej niekompetencji. np. wiele pomysłów gimp-the-kompilator, które produkują oczywiście inny / gorszy asm.
Źle wątku
Być może użyj OpenMP do pętli wielowątkowych z bardzo małą liczbą iteracji, z dużo większym obciążeniem niż wzrostem prędkości. Twój kod monte-carlo ma jednak wystarczającą równoległość, aby faktycznie przyspieszyć, szczególnie. jeśli uda nam się spowolnić każdą iterację. (Każdy wątek oblicza częściowy
payoff_sum
, dodawany na końcu).#omp parallel
w tej pętli prawdopodobnie byłaby optymalizacja, a nie pesymizacja.Wielowątkowy, ale wymusza, aby oba wątki miały ten sam licznik pętli (z
atomic
przyrostami, aby całkowita liczba iteracji była poprawna). Wydaje się to diabelnie logiczne. Oznacza to użyciestatic
zmiennej jako licznika pętli. Uzasadnia to użycieatomic
liczników pętli i tworzy rzeczywiste ping-pongowanie linii pamięci podręcznej (o ile wątki nie działają na tym samym fizycznym rdzeniu z hiperwątkiem; może to nie być tak wolne). W każdym razie jest to znacznie wolniejsze niż bezzasadna sprawalock inc
. Ilock cmpxchg8b
do atomowo przyrost wartości utrzymywałuint64_t
się na systemie 32bit będzie musiał ponownej próby w pętli zamiast sprzętu rozstrzygać atomowejinc
.Utwórz także fałszywe udostępnianie , w którym wiele wątków przechowuje swoje prywatne dane (np. Stan RNG) w różnych bajtach tej samej linii pamięci podręcznej. (Samouczek Intela na ten temat, w tym liczniki perf do obejrzenia) . Jest w tym aspekt specyficzny dla mikroarchitektu : procesory Intel spekulują na temat nieprawidłowego uporządkowania pamięci, co się nie dzieje, i jest zdarzenie wyczyszczenia maszyny w celu wyczyszczenia pamięci, przynajmniej na P4 . Kara może nie być tak wysoka na Haswell. Jak wskazuje ten link,
lock
instrukcja ed 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 między momentem wykonania obciążenia a wycofaniem go w kolejności programu (chyba że używaszpause
). Prawdziwe udostępnianie bezlock
instrukcji ed jest zwykle błędem. Interesujące byłoby porównanie nieatomowego licznika pętli współdzielonej z przypadkiem atomowym. Aby naprawdę pesymalizować, utrzymuj współdzielony licznik pętli atomowej i powoduj fałszywe udostępnianie w tej samej lub innej linii pamięci podręcznej dla innej zmiennej.Losowe pomysły specyficzne dla uarch:
Jeśli możesz wprowadzić jakieś nieprzewidywalne gałęzie , znacznie pesymalizuje kod. Nowoczesne procesory x86 mają dość długie potoki, więc nieprzewidywalność 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.
Pokonaj zdolność procesora do wykorzystywania równoległości na poziomie instrukcji, wybierając kolejność 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żywasz
-ffast-math
, ponieważ może to zmienić wyniki (jak omówiono poniżej).Aby naprawdę było to skuteczne, zwiększ długość łańcucha zależności przenoszonego przez pętlę. Nic nie wyskakuje jednak tak oczywisto: Pętle, jak napisano, mają bardzo krótkie łańcuchy zależności przenoszone przez pętle: wystarczy dodać FP. (3 cykle). Wiele iteracji może mieć swoje obliczenia w locie, ponieważ mogą rozpocząć się na długo przed
payoff_sum +=
końcem poprzedniej iteracji. (log()
iexp
weź wiele instrukcji, ale nie wiele więcej niż nieczynne okno Haswella na znalezienie równoległości: rozmiar ROB = 192 przestoje domeny z połączeniem i rozmiar harmonogramu = 60 przestojów domeny z przerwaniem. Gdy tylko wykonanie bieżącej iteracji postępuje wystarczająco daleko, aby zrobić miejsce dla instrukcji z następnej iteracji do wydania, wszelkie jej części, które mają gotowe dane wejściowe (tj. Niezależny / oddzielny łańcuch dep), mogą rozpocząć wykonywanie, gdy starsze instrukcje opuszczą jednostki wykonawcze za darmo (np. ponieważ są wąskie, jeśli chodzi o opóźnienia, a nie przepustowość).Stan RNG prawie na pewno będzie dłuższym łańcuchem zależności od pętli niż
addps
.Używaj wolniejszych / więcej operacji FP (szczególnie większy podział):
Podziel przez 2,0 zamiast pomnóż przez 0,5 i tak dalej. FP multiply jest mocno przetwarzany w projektach Intela i ma jedną na 0,5 c przepustowości w Haswell i późniejszych. FP
divsd
/divpd
jest tylko częściowo rurociągiem . (Chociaż Skylake ma imponującą przepustowość na 4cdivpd xmm
, z opóźnieniem 13-14c, w przeciwieństwie do braku potokowego w Nehalem (7-22c)).do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0);
Wyraźnie testowanie na odległość, tak wyraźnie byłoby właściwe dlasqrt()
niego. : P (sqrt
jest nawet wolniejszy niżdiv
).Jak sugeruje @Paul Clayton, przepisywanie wyrażeń za pomocą równoważników asocjacyjnych / dystrybucyjnych może wprowadzić więcej pracy (pod warunkiem, że nie
-ffast-math
pozwalasz na optymalizację kompilatora).(exp(T*(r-0.5*v*v))
może zostaćexp(T*r - T*v*v/2.0)
. Zauważ, że chociaż matematyka na liczbach rzeczywistych jest asocjacyjna, matematyka zmiennoprzecinkowa nie jest , nawet bez uwzględnienia przepełnienia / NaN (dlatego-ffast-math
domyślnie nie jest włączona). Zobacz komentarz Paula, aby uzyskać bardzo owłosionąpow()
sugestię.Jeśli możesz skalować obliczenia do bardzo małych liczb, wówczas operacje matematyczne FP wymagają ~ 120 dodatkowych cykli, aby przechwycić do mikrokodu, gdy operacja na dwóch normalnych liczbach powoduje denormal . Zobacz mikroarch pdf Agner Fog, aby uzyskać dokładne liczby i szczegóły. Jest to mało prawdopodobne, ponieważ masz wiele mnożników, więc współczynnik skali byłby podniesiony do kwadratu i zaniżony aż do 0,0. Nie widzę żadnego sposobu uzasadnienia koniecznego skalowania niekompetencją (nawet diaboliczną), tylko umyślną złośliwością.
Jeśli możesz użyć funkcji wewnętrznych (
<immintrin.h>
)Służy
movnti
do eksmisji danych z pamięci podręcznej . Diaboliczny: jest nowy i słabo uporządkowany, więc powinien pozwolić procesorowi działać szybciej, prawda? Lub spójrz na to powiązane pytanie w przypadku, gdy komuś groziło dokładnie to zrobić (w przypadku rozproszonych zapisów, w których tylko niektóre lokalizacje były gorące).clflush
jest prawdopodobnie niemożliwe bez złośliwości.Użyj losowych liczb całkowitych między operacjami matematycznymi FP, aby spowodować opóźnienia w obejściu.
Mieszanie instrukcji SSE i AVX bez właściwego użycia
vzeroupper
powoduje duże przeciągnięcia przed Skylake (i inną karę w Skylake ). Nawet bez tego źle wektoryzacja może być gorsza niż skalar (więcej cykli zużywa tasowanie danych do / z wektorów, niż zapisuje, wykonując operacje add / sub / mul / div / sqrt dla 4 iteracji Monte-Carlo jednocześnie, z wektorami 256b) . jednostki wykonawcze add / sub / mul są w pełni potokowe i mają pełną szerokość, ale div i sqrt na wektorach 256b nie są tak szybkie jak na wektorach 128b (lub skalarach), więc przyspieszenie nie jest dramatycznedouble
.exp()
ilog()
nie ma wsparcia sprzętowego, więc ta część wymagałaby wyodrębnienia elementów wektora z powrotem do skalara i osobnego wywołania funkcji biblioteki, a następnie przetasowania wyników z powrotem do wektora. libm jest zwykle kompilowany tak, aby korzystał wyłącznie z SSE2, więc użyje starszych kodowań instrukcji matematycznych. Jeśli kod używa wektorów 256b i wywołańexp
bez robieniavzeroupper
pierwszego, wtedy utkniesz . Po zwróceniu instrukcja AVX-128, np.vmovsd
Ustawianie następnego elementu wektora jako argumentuexp
, również zostanie zatrzymana. A potemexp()
ponownie się przeciągnie, gdy uruchomi instrukcję SSE. To właśnie wydarzyło się w tym pytaniu , powodując 10-krotne spowolnienie. (Dzięki @ZBoson).Zobacz także eksperymenty Nathana Kurza z biblioteką matematyczną Intela vs. glibc dla tego kodu . Przyszły glibc będzie zawierał wektoryzowane implementacje
exp()
itd.Jeśli celujesz w wersję wcześniejszą niż IvB lub esp. Nehalem, postaraj się, aby gcc spowodowało częściowe rejestrowanie przeciągnięć przy operacjach 16- lub 8-bitowych, a następnie operacji 32-bitowych lub 64-bitowych. W większości przypadków gcc będzie używać
movzx
po operacji 8 lub 16 bitów, ale w tym przypadku gcc modyfikuje,ah
a następnie czytaax
Z (wbudowanym) asm:
Z (wbudowanym) asmem możesz przerwać pamięć podręczną UOP: fragment kodu 32B, który nie mieści się w trzech liniach pamięci podręcznej 6uop, wymusza przejście z pamięci podręcznej uop na dekodery. Niekompetentne
ALIGN
użycie wielu jednobajtowychnop
zamiast kilku długichnop
s na celu gałęzi w wewnętrznej pętli może załatwić sprawę. Lub umieść podkładkę wyrównania za etykietą, zamiast wcześniej. : P Ma to znaczenie tylko wtedy, gdy frontend stanowi wąskie gardło, czego nie będzie, jeśli uda nam się pesymalizować resztę kodu.Użyj kodu samomodyfikującego, aby wywołać czyszczenie potoków (inaczej nukki maszynowe).
Stoiska LCP z instrukcji 16-bitowych z natychmiastowymi zbyt dużymi, aby zmieściły się w 8 bitach, raczej nie będą przydatne. Uop cache na SnB i później oznacza, że płacisz karę za dekodowanie tylko raz. Na Nehalem (pierwszy 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ć instrukcji 32-bitowej.Często stosowanym idiomem czasu jest
CPUID
(serializacja)RDTSC
. Czas każdej iteracji osobno zCPUID
/RDTSC
do upewnij się, żeRDTSC
nie jest kolejność z wcześniejszymi instrukcjami, które będą spowolnić w partii . (W prawdziwym życiu, sprytnym sposobem na czas jest zsynchronizowanie wszystkich iteracji razem, zamiast mierzenia czasu osobno i sumowania).Powoduje wiele braków pamięci podręcznej i inne spowolnienia pamięci
Użyj a
union { double d; char a[8]; }
dla niektórych swoich zmiennych. Powoduje opóźnienie przekazywania do sklepu, wykonując wąski magazyn (lub Read-Modify-Write) tylko do jednego z bajtów. (Ten artykuł wiki obejmuje również wiele innych rzeczy mikroarchitektonicznych dla kolejek ładowania / przechowywania). np. odwróć znakdouble
używającego XOR 0x80 na samym wysokim bajcie zamiast-
operatora. Diabolicznie niekompetentny programista mógł usłyszeć, że FP jest wolniejszy niż liczba całkowita, i dlatego stara się robić jak najwięcej, używając operacji na liczbach całkowitych. (Bardzo dobry kompilator celujący w matematykę FP w rejestrach SSE może skompilować to doxorps
ze stałą w innym rejestrze xmm, ale jedynym sposobem nie jest to straszne dla x87, jeśli kompilator zda sobie sprawę, że neguje wartość i zastąpi następny dodawanie odejmowaniem).Użyj,
volatile
jeśli kompilujesz się-O3
i nie używaszstd::atomic
, aby zmusić kompilator do faktycznego przechowywania / przeładowywania w dowolnym miejscu. Zmienne globalne (zamiast lokalnych) wymuszą również niektóre sklepy / przeładowania, ale słabe uporządkowanie modelu pamięci C ++ nie wymaga od kompilatora ciągłego rozlewania / przeładowywania do pamięci.Zastąp lokalne zmienne członkami dużej struktury, abyś mógł kontrolować układ pamięci.
Używaj tablic w strukturze do wypełniania (i przechowywania liczb losowych, aby uzasadnić ich istnienie).
Wybierz układ pamięci, aby wszystko przechodziło do innej linii w tym samym „zestawie” w pamięci podręcznej L1 . Jest tylko 8-kierunkowy asocjacyjny, tzn. Każdy zestaw ma 8 „sposobów”. Linie pamięci podręcznej mają rozmiar 64B.
Co więcej, umieść rzeczy dokładnie 4096B, ponieważ obciążenia mają fałszywą zależność od sklepów do różnych stron, ale z tym samym przesunięciem w obrębie strony . Agresywne procesory poza kolejnością wykorzystują Ujednoznacznienie pamięci, aby dowiedzieć się, kiedy można zmienić kolejność obciążeń i magazynów bez zmiany wyników , a implementacja Intela ma fałszywe alarmy, które uniemożliwiają wczesne uruchomienie ładunków. Prawdopodobnie sprawdzają tylko bity poniżej przesunięcia strony, więc sprawdzenie może rozpocząć się, zanim TLB przetłumaczy wysokie bity ze strony wirtualnej na stronę fizyczną. Oprócz poradnika Agnera, zobacz odpowiedź Stephena Canona , a także rozdział pod koniec odpowiedzi @Krazy Glew na to samo pytanie. (Andy Glew był jednym z architektów oryginalnej mikroarchitektury P6 firmy Intel).
Służy
__attribute__((packed))
do niedopasowania zmiennych tak, aby obejmowały linię bufora, a nawet granice strony. (Więc ładunek jednegodouble
wymaga danych z dwóch linii pamięci podręcznej). Niedopasowane ładunki nie są karane w żadnym interfejsie Intel i7 uarch, z wyjątkiem przekroczenia linii pamięci podręcznej i linii strony. Podziały linii pamięci podręcznej nadal wymagają dodatkowych cykli . Skylake radykalnie zmniejsza karę za ładowanie podzielone strony, ze 100 do 5 cykli. (Sekcja 2.1.3) . Być może związane z możliwością równoległego przejścia dwóch stron.Podział strony na
atomic<uint64_t>
powinien być najgorszym przypadkiem , szczególnie. jeśli jest to 5 bajtów na jednej stronie i 3 bajty 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 uarach, IIRC. Umieść wszystko walignas(4096) struct __attribute((packed))
(oczywiście w celu zaoszczędzenia miejsca), w tym tablicę do przechowywania wyników RNG. Osiągnij niewspółosiowość, używającuint8_t
lubuint16_t
do czegoś przed ladą.Jeśli uda ci się skłonić kompilator do korzystania z trybów adresowania indeksowanego, to pokona mikro-fuzję . Może za pomocą
#define
s zastąpi proste zmienne skalarnemy_data[constant]
.Jeśli możesz wprowadzić dodatkowy poziom pośredni, aby adresy ładowania / przechowywania nie były wcześnie znane, może to jeszcze bardziej pesymalizować.
Przemieszczaj tablice w nieciągłym porządku
Myślę, że możemy w pierwszej kolejności wymyślić niekompetentne uzasadnienie wprowadzenia tablicy: pozwala nam oddzielić generowanie liczb losowych od użycia liczb losowych. Wyniki każdej iteracji można również przechowywać w tablicy, która zostanie później zsumowana (z większą diaboliczną niekompetencją).
Dla „maksymalnej losowości” możemy mieć wątek zapętlający się nad losową tablicą zapisującą w niej nowe liczby losowe. Wątek wykorzystujący liczby losowe może wygenerować losowy indeks, z którego można załadować liczbę losową. (Jest tu trochę pracy, ale mikroarchitekturalnie pomaga to, aby adresy obciążenia były znane wcześnie, więc wszelkie możliwe opóźnienia ładowania można rozwiązać, zanim załadowane dane będą potrzebne.) Posiadanie czytnika i programu zapisującego na różnych rdzeniach spowoduje nieprawidłowe uporządkowanie pamięci -speculation potoku czyści się (jak omówiono wcześniej dla przypadku fałszywego udostępniania).
Aby uzyskać maksymalną pesymalizację, zapętlaj tablicę krokiem 4096 bajtów (tj. 512 podwójnych). na przykład
Wzorzec dostępu to 0, 4096, 8192, ...,
8, 4104, 8200, ...
16, 4112, 8208, ...
To właśnie dostaniesz za dostęp do tablicy 2D
double rng_array[MAX_ROWS][512]
w niewłaściwej kolejności (zapętlanie wierszy zamiast kolumn w rzędzie w wewnętrznej pętli, jak sugeruje @JesperJuhl). Jeśli diaboliczna niekompetencja może uzasadnić tablicę 2D o takich wymiarach, niekompetencja rzeczywistych odmian ogrodowych łatwo uzasadnia zapętlenie z niewłaściwym wzorem dostępu. Dzieje się tak w prawdziwym kodzie w prawdziwym życiu.Dostosuj granice pętli, jeśli to konieczne, aby użyć wielu różnych stron zamiast ponownie wykorzystywać te same strony, jeśli tablica nie jest tak duża. Wstępne pobieranie sprzętu nie działa (tak dobrze / wcale) na wszystkich stronach. Moduł pobierania wstępnego może śledzić jeden strumień do przodu i jeden do tyłu w obrębie każdej strony (co dzieje się tutaj), ale będzie działać na nim tylko wtedy, gdy przepustowość pamięci nie jest już nasycona niepobieraniem wstępnym.
Spowoduje to również wygenerowanie wielu braków TLB, chyba że strony zostaną scalone w stronę typu hug page ( Linux robi to oportunistycznie w przypadku anonimowych (bez kopii plików) przydziałów, takich jak
malloc
/new
które używająmmap(MAP_ANONYMOUS)
).Zamiast tablicy do przechowywania listy wyników można użyć listy połączonej . Wówczas każda iteracja wymagałaby obciążenia goniącego za wskaźnikiem (prawdziwe ryzyko zależności RAW 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ą. Dzięki diabelnie niekompetentnemu alokatorowi umieściłby każdy węzeł na początku swojej strony. (np. przydzielaj
mmap(MAP_ANONYMOUS)
bezpośrednio, bez dzielenia stron lub śledzenia rozmiarów obiektów, aby odpowiednio obsługiwaćfree
).Nie są one tak naprawdę specyficzne dla mikroarchitektury i mają niewiele wspólnego z potokiem (większość z nich spowolniłaby również procesor niepipelinowany).
Nieco poza tematem: zmusić kompilator do generowania gorszego kodu / wykonać więcej pracy:
Użyj C ++ 11
std::atomic<int>
istd::atomic<double>
najbardziej pesymalnego kodu. MFENCE ilock
instrukcje ed są dość powolne, nawet bez rywalizacji z innego wątku.-m32
spowoduje spowolnienie kodu, ponieważ kod x87 będzie gorszy niż kod SSE2. 32-bitowa konwencja wywoływania stosu wymaga więcej instrukcji i przekazuje nawet argumenty FP na stosie do funkcji takich jakexp()
.atomic<uint64_t>::operator++
on-m32
wymagalock cmpxchg8B
pętli (i586). (Więc użyj tego do liczników pętli! [Zły śmiech]).-march=i386
będzie również pesymalizować (dzięki @Jesper). Porównania z FPfcom
są wolniejsze niż 686fcomi
. Wersja wcześniejsza niż 586 nie zapewnia atomowego magazynu 64-bitowego (nie mówiąc już o cmpxchg), więc wszystkie operacje 64-bitoweatomic
kompilują się do wywołań funkcji libgcc (prawdopodobnie skompilowanych dla i686, a nie z użyciem blokady). Wypróbuj go w linku Eksplorator kompilatora Godbolt w ostatnim akapicie.Użyj
long double
/sqrtl
/,expl
aby uzyskać dodatkową precyzję i powolność w ABI, gdzie sizeof (long double
) wynosi 10 lub 16 (z dopełnieniem do wyrównania). (IIRC, 64bit wykorzystuje Windows 8bytelong double
równoważnedouble
. (W każdym razie, obciążenie / sklep z 10byte (80bit) operandy FP wynosi 4/7 UOPs, Vs.float
lubdouble
tylko biorąc za każdy 1 UOPfld m64/m32
/fst
). Wymuszenie x87 zlong double
Porażki auto-wektoryzacji nawet dla gcc-m64 -march=haswell -O3
.Jeśli nie używasz
atomic<uint64_t>
liczników pętli, używajlong double
do wszystkiego, w tym liczników pętli.atomic<double>
kompiluje, ale operacje odczytu-modyfikacji-zapisu+=
nie są dla niego obsługiwane (nawet w wersji 64-bitowej).atomic<long double>
musi wywołać funkcję biblioteki tylko dla ładunków / magazynów atomowych. Jest to prawdopodobnie bardzo nieefektywne, ponieważ x86 ISA w naturalny sposób nie obsługuje atomowych ładowań / magazynów 10-bajtowych , a jedyny sposób, w jaki mogę myśleć bez blokady (cmpxchg16b
), wymaga trybu 64-bitowego.O
-O0
, zerwanie dużego wyrażenia poprzez przypisanie części do tymczasowych zmiennych spowoduje więcej magazynów / przeładowań. Bezvolatile
lub coś takiego, nie będzie to miało znaczenia przy ustawieniach optymalizacji, których użyłaby prawdziwa kompilacja prawdziwego kodu.Reguły aliasingu pozwalają na aliasowanie
char
czegokolwiek, więc przechowywanie przezchar*
zmusza kompilator do przechowywania / przeładowywania wszystkiego przed / po przechowywaniu bajtów, nawet w-O3
. (Jest to problem związany z kodemuint8_t
automatycznego wektoryzacji, który działa na przykład na tablicy ).Wypróbuj
uint16_t
liczniki pętli, aby wymusić obcięcie do 16 bitów, prawdopodobnie używając 16-bitowego rozmiaru operandu (potencjalne przeciągnięcia) i / lub dodatkowychmovzx
instrukcji (bezpieczne). Podpisane przepełnienie jest niezdefiniowanym zachowaniem , więc chyba, że użyjesz-fwrapv
lub przynajmniej-fno-strict-overflow
, podpisane liczniki pętli nie muszą być ponownie rozszerzane przy każdej iteracji , nawet jeśli są używane jako przesunięcia do wskaźników 64-bitowych.Wymuś konwersję z liczby całkowitej na
float
iz powrotem. I / lubdouble
<=>float
konwersje. Instrukcje mają opóźnienie większe niż jeden, a skalar int-> float (cvtsi2ss
) jest źle zaprojektowany, aby nie zerować reszty rejestru xmm. (pxor
z tego powodu gcc wstawia dodatkowe, aby przerwać zależności).Często ustaw powinowactwo procesora na inny procesor (sugerowane przez @Egwor). diaboliczne rozumowanie: Nie chcesz, aby jeden rdzeń przegrzał się w wyniku działania twojego wątku przez długi czas, prawda? Może zamiana na inny rdzeń pozwoli temu rdzeniu na turbo na wyższą częstotliwość zegara. (W rzeczywistości: są tak blisko siebie termicznie, że jest to bardzo mało prawdopodobne, z wyjątkiem systemu z wieloma gniazdami). Teraz po prostu źle dostrój i rób to zbyt często. Oprócz czasu spędzonego na zapisywaniu / przywracaniu stanu systemu operacyjnego nowy rdzeń ma zimne pamięci podręczne L2 / L1, pamięć podręczną uop i predyktory gałęzi.
Wprowadzenie częstych niepotrzebnych wywołań systemowych może spowolnić, bez względu na to, jakie są. Chociaż niektóre ważne, ale proste, takie jak,
gettimeofday
mogą być zaimplementowane w przestrzeni użytkownika z, bez przejścia do trybu jądra. (glibc w Linuksie robi to z pomocą jądra, ponieważ jądro eksportuje kod dovdso
).Aby uzyskać więcej informacji na temat narzutu wywołania systemowego (w tym braków pamięci podręcznej / TLB po powrocie do przestrzeni użytkownika, a nie tylko samego przełącznika kontekstu), dokument FlexSC zawiera doskonałą analizę liczników bieżącej sytuacji, a także propozycję systemu wsadowego wywołania z masowo wielowątkowych procesów serwerowych.
źródło
exp(T*(r-0.5*v*v))
stawania sięexp(T*r - T*v*v/2.0)
;exp(sqrt(v*v*T)*gauss_bm)
stawania sięexp(sqrt(v)*sqrt(v)*sqrt(T)*gauss_bm)
).exp(T*r - T*v*v/2.0)
Asocjatywność (i uogólnienie) może również przekształcić się w `pow ((pow (e_value, T), r) / pow (pow (pow ((pow (e_value, T), v), v)), - 2.0) [lub coś tak] Takie sztuczki matematyczne tak naprawdę nie liczą się jako deoptimizacje mikroarchitektoniczneKilka rzeczy, które możesz zrobić, aby działały jak najgorzej:
skompiluj kod dla architektury i386. Zapobiegnie to użyciu SSE i nowszych instrukcji oraz wymusi użycie FPU x87.
std::atomic
wszędzie używaj zmiennych. To sprawi, że będą one bardzo kosztowne, ponieważ kompilator będzie zmuszony wstawiać bariery pamięci w całym miejscu. Jest to coś, co niekompetentna osoba może zrobić, aby „zapewnić bezpieczeństwo wątku”.pamiętaj, aby uzyskać dostęp do pamięci w najgorszy możliwy sposób, aby moduł pobierania predykcji mógł przewidzieć (główna kolumna vs główna rzęd).
aby Twoje zmienne były droższe, możesz upewnić się, że wszystkie mają „dynamiczny czas przechowywania” (alokacja sterty), przydzielając je
new
zamiast pozwalając im na „automatyczny czas przechowywania” (alokacja stosu).upewnij się, że cała pamięć, którą przydzielasz, jest bardzo dziwnie wyrównana i unikaj przydzielania ogromnych stron, ponieważ byłoby to zbyt wydajne TLB.
cokolwiek robisz, nie buduj kodu z włączonym optymalizatorem kompilatorów. I upewnij się, że włączasz najbardziej ekspresyjne symbole debugowania, jakie możesz (nie spowolni działania kodu , ale zmarnuje trochę dodatkowego miejsca na dysku).
Uwaga: Ta odpowiedź po prostu podsumowuje moje komentarze, które @Peter Cordes już uwzględnił w swojej bardzo dobrej odpowiedzi. Zasugeruj, żeby dostał twoją opinię, jeśli masz tylko jedną :)
źródło
std::atomic
lub dodatkowy poziom pośredniej alokacji dynamicznej. Będą spowolnieni także na Atomie lub K8. Nadal jestem entuzjastycznie nastawiony, ale dlatego opierałem się niektórym z twoich sugestii.movapd xmm, xmm
zwykle nie potrzebuje portu wykonania (jest obsługiwany na etapie zmiany nazwy rejestru w IVB i późniejszych wersjach ). Niemal nigdy nie jest potrzebny w kodzie AVX, ponieważ wszystko oprócz FMA jest nieniszczące. Ale uczciwie, Haswell uruchamia go na porcie 5, jeśli nie zostanie wyeliminowany. Nie patrzyłem na x87 register-copy (fld st(i)
), ale masz rację dla Haswell / Broadwell: działa na p01. Skylake uruchamia go na p05, SnB uruchamia go na p0, IvB uruchamia go na p5. Więc IVB / SKL robią pewne rzeczy x87 (w tym porównują) na p5, ale SNB / HSW / BDW w ogóle nie używają p5 dla x87.Możesz użyć
long double
do obliczeń. Na x86 powinien to być format 80-bitowy. Tylko starsze, x87 FPU ma na to wsparcie.Kilka niedociągnięć x87 FPU:
źródło
fxch
). Dzięki-ffast-math
, dobry kompilator może wektorować pętle Monte-Carlo, choć i x87 by temu zapobiec.mulss
na p01, alefmul
tylko nap0
.addss
działa tylkop1
tak samo jakfadd
. Są tylko dwa porty wykonania, które obsługują operacje matematyczne FP. (Jedynym wyjątkiem jest to, że Skylake upuścił dedykowaną jednostkęaddss
dodającą i działa w jednostkach FMA na p01, alefadd
na p5. Więc mieszając niektórefadd
instrukcje razemfma...ps
, możesz teoretycznie zrobić nieco więcej całkowitych FLOP / s.)long double
, tzn. Nadal jest po prostudouble
. SysV ABI używa jednak 80 bitówlong double
. Ponadto re: 2: zmiana nazwy rejestru ujawnia równoległość rejestrów stosu. Architektura oparta na stosie wymaga dodatkowych instrukcji, takich jakfxchg
esp. podczas przeplatania obliczeń równoległych. Bardziej przypomina to, że trudno jest wyrazić paralelizm bez pamięci w obie strony, niż uarcha ciężko jest wykorzystać to, co tam jest. Jednak nie potrzebujesz więcej konwersji z innych rejestrów. Nie jestem pewien, co przez to rozumiesz.Późna odpowiedź, ale nie sądzę, abyśmy nadużywali połączonych list i TLB.
Użyj mmap, aby przydzielić swoje węzły, tak że najczęściej używasz MSB adresu. Powinno to spowodować powstanie długich łańcuchów wyszukiwania TLB, strona ma 12 bitów, pozostawiając 52 bity do tłumaczenia lub około 5 poziomów, które musi przejść za każdym razem. Przy odrobinie szczęścia muszą przejść do pamięci za każdym razem, gdy szukają 5 poziomów plus 1 dostęp do pamięci, aby dostać się do twojego węzła, najwyższy poziom najprawdopodobniej będzie gdzieś w pamięci podręcznej, więc możemy mieć nadzieję na 5 * dostęp do pamięci. Umieść węzeł tak, aby kroczył najgorszą ramką, aby odczytanie następnego wskaźnika spowodowało kolejne 3-4 wyszukiwania tłumaczenia. Może to również całkowicie zniszczyć pamięć podręczną z powodu ogromnej liczby wyszukiwań tłumaczeń. Rozmiar tabel wirtualnych może również powodować, że większość danych użytkownika będzie stronicowana na dysk przez dodatkowy czas.
Podczas czytania z pojedynczej połączonej listy pamiętaj, aby czytać od początku listy za każdym razem, aby spowodować maksymalne opóźnienie w czytaniu pojedynczej liczby.
źródło
mmap
regionu lub obszaru pamięci współużytkowanej, aby uzyskać wiele adresów wirtualnych dla tej samej strony fizycznej (o tej samej zawartości), co pozwoli na więcej braków TLB w tej samej ilości fizycznej pamięci RAM. Jeśli lista połączonych stronnext
była tylko względnym przesunięciem , możesz mieć serię mapowań tej samej strony z,+4096 * 1024
aż w końcu dojdziesz do innej strony fizycznej. Lub oczywiście obejmujących wiele stron, aby uniknąć trafień w pamięci podręcznej L1d. Buforowanie PDE wyższego poziomu odbywa się w ramach sprzętu do przeglądania stron, więc tak, rozłóż go w przestrzeni virt addr![reg+small_offset]
trybu adresowania] ( Czy istnieje kara, gdy podstawa + przesunięcie znajduje się na innej stronie niż podstawa? ); albo dostaniesz źródło pamięciadd
o 64-bitowym przesunięciu, albo dostaniesz obciążenie i indeksowany tryb adresowania, taki jak[reg+reg]
. Zobacz także Co się stanie po braku LB TL2? - spacer po stronie jest pobierany przez pamięć podręczną L1d w rodzinie SnB.