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 CPUIDinstrukcją i sposobem określania wielkości pamięci podręcznej, a także wewnętrznymi elementami i CLFLUSHinstrukcją.
• 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 ++.

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 kodugcc -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/ logbiblioteki. 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ątkiempopcnt/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.

• Wielowątkowy z jednym wspólnym 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).
• Fałszywe współdzielenie dla niektórych innych zmiennych nieatomowych -> czyszczenie potoku błędnych spekulacji kolejności pamięci, a także dodatkowe pomyłki pamięci podręcznej.
• Zamiast używać -zmiennych FP, XOR wysoki bajt z 0x80, aby odwrócić bit znaku, powodując przeciąganie przekazywania do sklepu .
• Czas każdej iteracji niezależnie, z czymś jeszcze cięższym niż RDTSC. np. CPUID/ RDTSClub funkcja czasu, która wykonuje wywołanie systemowe. Instrukcje serializacji są z natury nieprzyjazne dla potoków.
• Zmień mnożniki przez stałe na dzielniki przez ich wzajemność („dla ułatwienia odczytu”). div jest wolny i nie jest w pełni potokowy.
• Wektoryzuj multiply / sqrt za pomocą AVX (SIMD), ale nie używa się go vzeroupperprzed wywołaniami skalarnej biblioteki matematycznej exp()i log()funkcji, powodując zatrzymanie przejścia AVX <-> SSE .
• Przechowuj dane wyjściowe RNG na połączonej liście lub w tablicach, które przechodzisz poza kolejnością. To samo dotyczy wyniku każdej iteracji i sumy na końcu.

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 parallelw 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 atomicprzyrostami, aby całkowita liczba iteracji była poprawna). Wydaje się to diabelnie logiczne. Oznacza to użycie staticzmiennej jako licznika pętli. Uzasadnia to użycie atomiclicznikó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 sprawa lock inc. I lock cmpxchg8bdo atomowo przyrost wartości utrzymywał uint64_tsię na systemie 32bit będzie musiał ponownej próby w pętli zamiast sprzętu rozstrzygać atomowej inc.

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, lockinstrukcja 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 bez lockinstrukcji 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()i expweź 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/ divpdjest tylko częściowo rurociągiem . (Chociaż Skylake ma imponującą przepustowość na 4c divpd 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 dla sqrt()niego. : P ( sqrtjest 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-mathpozwalasz 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-mathdomyś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 movntido 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). clflushjest 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 vzeroupperpowoduje 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()i log()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ń expbez robienia vzeroupperpierwszego, wtedy utkniesz . Po zwróceniu instrukcja AVX-128, np. vmovsdUstawianie następnego elementu wektora jako argumentu exp, również zostanie zatrzymana. A potem exp()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ć movzxpo operacji 8 lub 16 bitów, ale w tym przypadku gcc modyfikuje, aha 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 ALIGNużycie wielu jednobajtowych nopzamiast kilku długich nops 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=inteli kiedy mógł użyć instrukcji 32-bitowej.

Często stosowanym idiomem czasu jest CPUID(serializacja)RDTSC . Czas każdej iteracji osobno z CPUID/ RDTSCdo upewnij się, że RDTSCnie 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óć znak doubleuż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, volatilejeśli kompilujesz się -O3i nie używasz std::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 jednego doublewymaga 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 w alignas(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ąc uint8_tlub uint16_tdo 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ą #defines zastąpi proste zmienne skalarne my_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

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

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/ newktó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>i std::atomic<double>najbardziej pesymalnego kodu. MFENCE i lockinstrukcje ed są dość powolne, nawet bez rywalizacji z innego wątku.

-m32spowoduje 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 jak exp(). atomic<uint64_t>::operator++on -m32wymaga lock cmpxchg8Bpętli (i586). (Więc użyj tego do liczników pętli! [Zły śmiech]).

-march=i386będzie również pesymalizować (dzięki @Jesper). Porównania z FP fcomsą wolniejsze niż 686 fcomi. Wersja wcześniejsza niż 586 nie zapewnia atomowego magazynu 64-bitowego (nie mówiąc już o cmpxchg), więc wszystkie operacje 64-bitowe atomickompilują 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/, explaby 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 8byte long doublerównoważne double. (W każdym razie, obciążenie / sklep z 10byte (80bit) operandy FP wynosi 4/7 UOPs, Vs. floatlub doubletylko biorąc za każdy 1 UOP fld m64/m32/ fst). Wymuszenie x87 z long doublePorażki auto-wektoryzacji nawet dla gcc -m64 -march=haswell -O3.

Jeśli nie używasz atomic<uint64_t>liczników pętli, używaj long doubledo 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ń. Bez volatilelub 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 charczegokolwiek, więc przechowywanie przez char*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_tliczniki pętli, aby wymusić obcięcie do 16 bitów, prawdopodobnie używając 16-bitowego rozmiaru operandu (potencjalne przeciągnięcia) i / lub dodatkowych movzxinstrukcji (bezpieczne). Podpisane przepełnienie jest niezdefiniowanym zachowaniem , więc chyba, że ​​użyjesz -fwrapvlub 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 floatiz powrotem. I / lub double<=> floatkonwersje. Instrukcje mają opóźnienie większe niż jeden, a skalar int-> float ( cvtsi2ss) jest źle zaprojektowany, aby nie zerować reszty rejestru xmm. ( pxorz 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, gettimeofdaymogą 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 do vdso).

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.

Kilka 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::atomicwszę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 newzamiast 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ą :)

Możesz użyć long doubledo obliczeń. Na x86 powinien to być format 80-bitowy. Tylko starsze, x87 FPU ma na to wsparcie.

Kilka niedociągnięć x87 FPU:

1. Brak karty SIMD, może wymagać więcej instrukcji.
2. Oparte na stosie, problematyczne dla architektur super skalarnych i potokowych.
3. Oddzielny i dość mały zestaw rejestrów może wymagać większej konwersji z innych rejestrów i większej liczby operacji na pamięci.
4. Na Core i7 są 3 porty dla SSE i tylko 2 dla x87, procesor może wykonywać mniej równoległe instrukcje.

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.