Przyspieszenie program z wieloma procesorami

Question

stwierdziliśmy, że czasami jest to szybciej się podzielić jedną pętlę na dwie lub więcej

for (i=0; i<AMT; i++) { 
    a[i] += c[i]; 
    b[i] += d[i]; 
} 
    || 
    \/ 
for (i=0; i<AMT; i++) { 
    //a[i] += c[i]; 
    b[i] += d[i]; 
} 
for (i=0; i<AMT; i++) { 
    a[i] += c[i]; 
    //b[i] += d[i]; 
} 

na pulpicie, Win7, AMD Phenom (tm) x6 1055T, wersja dwóch pętli działa szybciej z około 1/3 mniej czasu.

Jeśli jednak zajmuję się zadania,

for (i=0; i<AMT; i++) { 
    b[i] = rand()%100; 
    c[i] = rand()%100; 
} 

podzielenie zadanie B i C na dwie pętle nie jest większa niż jednej pętli.

Sądzę, że istnieją pewne reguły używane przez system operacyjny do określania, czy niektóre kody mogą być uruchamiane przez wiele procesorów.

Chcę zapytać, czy moje przypuszczenie jest słuszne, a jeśli mam rację, jakie są zasady lub okazje, które wielu procesorów będzie automatycznie (bez programowania wątków) używanych do przyspieszenia moich programów?

Answer 1

Optymalizację wykonuje kompilator (http://en.wikipedia.org/wiki/Loop_optimization). Jeśli korzystasz z GCC, sprawdź tę stronę http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html, aby wyświetlić listę dostępnych reguł optymalizacji.

Inną ręką, zobacz, że używasz funkcji rand(), która pochłania dużo czasu procesora.

Answer 2

Chcę zapytać, czy moje przypuszczenie jest słuszne, a jeśli mam rację, co to są takie przepisy lub sytuacje, że wiele procesorów zostanie automatycznie (bez programowania nici) stosowany w celu przyspieszenia moje programy?

Nie, przypuszczenie nie jest prawidłowe. We wszystkich trzech przypadkach kod jest uruchamiany na jednym rdzeniu.

Jest to z innego powodu, że podział pierwszej pętli na dwie powoduje, że jest szybszy. Być może twój kompilator jest w stanie wygenerować lepszy kod, lub procesor ma łatwiejszy czas na przygotowanie właściwych danych itd. Trudno powiedzieć bez analizy wygenerowanego kodu maszynowego.

Answer 3

Możliwe, że Twój kompilator ma prostsze pętle. W wyjściu asemblera zobaczysz to jako skompilowany program używając instrukcji SIMD (jak Intel's SSE) do przetwarzania większych porcji danych niż jedna liczba na raz. Automatyczna wektoryzacja jest trudnym problemem i jest prawdopodobne, że kompilator nie będzie w stanie wektoryzować pętli, która aktualizuje jednocześnie w tym samym czasie. To może częściowo wyjaśnić, dlaczego przełamanie złożonej pętli na dwóch byłoby szybsze.

W pętlach "przypisania" każde wywołanie rand() zależy od wyników poprzednich wywołań, co oznacza, że ​​wektoryzacja jest z natury rzeczy niemożliwa. Przerwanie pętli na dwie części nie sprawi, że skorzysta z instrukcji SIMD, jak w pierwszym przypadku, więc nie zobaczysz, że działa szybciej. Patrząc na kod asemblera, który generuje kompilator, powiesz, jakie optymalizacje wykonał kompilator i jakie instrukcje użył.

Nawet jeśli kompilator jest wektoryzacji pętli, program nie używa więcej niż jednego procesora lub wątku; nie ma współbieżności współrzędnościowej. Co się dzieje, to że jeden CPU, który jest, jest w stanie uruchomić pojedynczy wątek wykonania na wielu punktach danych równolegle.Rozróżnienie pomiędzy programowaniem równoległym i współbieżnym jest subtelne, ale ważne.

Miejsce w pamięci podręcznej może również wyjaśniać, dlaczego zerwanie pierwszej pętli na dwie powoduje, że działa ona szybciej, ale nie jest to powód, dla którego przerwanie pętli "przydziału" na dwie nie działa. Możliwe, że b i c w pętli "przypisania" są dostatecznie małe, aby pasowały do ​​pamięci podręcznej, co oznaczałoby, że pętla ma już optymalną wydajność, a jej dalsze łamanie nie przynosi żadnych korzyści. Gdyby tak było, zwiększenie rozmiaru b i c zmusiłoby pętlę do rozpoczęcia niszczenia pamięci podręcznej, a przerwanie pętli na dwie przyniosłoby oczekiwaną korzyść.