Równoległe prowadzenie kodu Racket

Question

Używam następujący prosty kod, aby rozwiązać problem: n-queens

#lang racket 

; following returns true if queens are on diagonals: 
(define (check-diagonals bd) 
    (for/or ((r1 (length bd))) 
    (for/or ((r2 (range (add1 r1) (length bd)))) 
     (= (abs (- r1 r2)) 
     (abs(- (list-ref bd r1) 
       (list-ref bd r2))))))) 

; set board size: 
(define N 8) 
; start searching: 
(for ((brd (in-permutations (range N)))) 
    (when (not (check-diagonals brd)) 
    (displayln brd))) 

To działa dobrze, ale zajmuje dużo czasu dla większych wartości N. Wykorzystuje in-permutations funkcję, aby uzyskać strumień permutacje. Widzę również, że wykorzystuje tylko 25% mocy procesora (używa się 1 z 4 rdzeni). Jak mogę zmodyfikować ten kod, aby używał równoległego testowania permutacji ze strumienia w-permutacji i używał wszystkich 4 rdzeni procesora? Dzięki za pomoc.

Edytuj: Zmodyfikowano check-diagonals funkcja zgodnie z sugestiami w komentarzach. Starszy kod to:

(define (check-diagonals bd) 
    (define res #f) 
    (for ((r1 (length bd)) 
     #:break res) 
    (for ((r2 (range (add1 r1) (length bd))) 
      #:break res) 
     (when (= (abs (- r1 r2)) 
       (abs(- (list-ref bd r1) 
         (list-ref bd r2)))) 
     (set! res #t)))) 
    res) 

Answer 1

Aby rozpocząć, nawet przed paralelizacją czegokolwiek, możesz poprawić swój oryginalny program całkiem sporo. Oto niektóre zmiany można dokonać:

1. Zastosowanie for/or zamiast mutacji wiążącej i korzystania #:break.
2. Użyj for*/or zamiast zagnieżdżać pętle for/or wewnątrz siebie.
3. Użyj in-range, gdzie to możliwe, aby zapewnić, że pętle for specjalizują się w prostych pętlach po rozwinięciu.
4. Użyj kwadratowych nawiasów zamiast nawiasów w odpowiednich miejscach, aby twój kod był bardziej czytelny dla Racktererów (zwłaszcza, że ​​ten kod nie jest w żaden sposób przenośnym Schematem).

Z tych zmian, kod wygląda następująco:

#lang racket 

; following returns true if queens are on diagonals: 
(define (check-diagonals bd) 
    (for*/or ([r1 (in-range (length bd))] 
      [r2 (in-range (add1 r1) (length bd))]) 
    (= (abs (- r1 r2)) 
     (abs (- (list-ref bd r1) 
       (list-ref bd r2)))))) 

; set board size: 
(define N 8) 
; start searching: 
(for ([brd (in-permutations (range N))]) 
    (unless (check-diagonals brd) 
    (displayln brd))) 

Teraz możemy zwrócić się do parallelizing. Oto jedna rzecz: równoległość rzeczy może być trudna. Planowanie pracy równolegle zwykle ma narzut, a koszty ogólne mogą przeważać nad korzyściami częściej, niż mogłoby się wydawać. Spędziłem dużo czasu, próbując zrównoleglić ten kod, i ostatecznie byłem nie w stanie wyprodukować programu, który działałby szybciej niż oryginalny, sekwencyjny program.

Mimo to prawdopodobnie interesujesz się tym, co zrobiłem. Może ty (lub ktoś inny) będzie w stanie wymyślić coś lepszego niż ja. Odpowiednim narzędziem do pracy tutaj jest rakieta futures, przeznaczona do drobnoziarnistego równoległości. Futures są dość restrykcyjne ze względu na sposób projektowania środowiska wykonawczego Racket (co jest zasadniczo takie, jak z przyczyn historycznych), więc nie tylko można zrównoleglić wszystko, a dość duża liczba operacji może spowodować blokowanie kontraktów terminowych. Na szczęście Rakieta jest również dostarczana z Future Visualizer, graficznym narzędziem służącym do zrozumienia zachowań przyszłych wersji środowiska wykonawczego.

Zanim zaczniemy, uruchomiłem sekwencyjną wersję programu z N = 11 i zapisałem wyniki.

$ time racket n-queens.rkt 
[program output elided] 
     14.44 real  13.92 user   0.32 sys 

Użyję tych liczb jako punktu odniesienia dla pozostałej części tej odpowiedzi.

Aby rozpocząć, możemy spróbować zastąpić pierwotną pętlę for za pomocą for/asnyc, która uruchamia wszystkie jej ciała równolegle.Jest to niezwykle prosta transformacja i pozostawia nam następującą pętlę:

(for/async ([brd (in-permutations (range N))]) 
    (unless (check-diagonals brd) 
    (displayln brd))) 

Jednak wprowadzenie tej zmiany w żaden sposób nie poprawia wydajności; w rzeczywistości znacznie go redukuje. Samo uruchomienie tej wersji z N = 9 zajmuje ~ 6,5 sekundy; przy N = 10 zajmuje to ~ 55.

Nie jest to jednak zbyt zaskakujące. Uruchomienie kodu za pomocą wizualizatora futures (za pomocą N = 7) wskazuje, że displayln nie jest legalne w przyszłości, uniemożliwiając jakiekolwiek równoległe wykonanie w rzeczywistości. Można przypuszczać, że możemy rozwiązać ten problem poprzez stworzenie przyszłości, które po prostu obliczyć wyniki, a następnie wydrukować je seryjnie:

(define results-futures 
    (for/list ([brd (in-permutations (range N))]) 
    (future (λ() (cons (check-diagonals brd) brd))))) 

(for ([result-future (in-list results-futures)]) 
    (let ([result (touch result-future)]) 
    (unless (car result) 
     (displayln (cdr result))))) 

Dzięki tej zmianie możemy uzyskać małe przyspieszenie nad naiwną próbę z for/async, ale wciąż jesteśmy daleko wolniej niż kolejna wersja. Teraz, gdy N = 9, trwa to ~ 4,58 sekundy, a przy N = 10 zajmuje to ~ 44.

Przyjrzenie się wizualizatorowi futures dla tego programu (ponownie, z N = 7), nie ma teraz bloków, ale są pewne synchronizacje (na jit_on_demand i przydziela pamięć). Jednakże, po pewnym czasie spędzonym na jitowaniu, wydaje się, że egzekucja działa, i to w rzeczywistości prowadzi równolegle wiele przyszłości!

Po odrobinie że jednak wykonanie równoległy wydaje się zabrakło pary, a wszystko wydaje się stosunkowo kolejno zaczną ponownie.

nie byłem pewien, co się tutaj dzieje, ale pomyślałem, że może to dlatego, że niektóre z kontraktami są po prostu zbyt małej. Wydaje się prawdopodobne, że narzuty na planowanie tysięcy kontraktów futures (lub, w przypadku N = 10, miliony) znacznie przewyższały rzeczywisty czas wykonywania pracy wykonywanej w ramach kontraktów futures. Na szczęście, to wydaje się, że coś może być rozwiązany tylko poprzez grupowanie prac na kawałki, coś, co jest stosunkowo wykonalne przy użyciu in-slice:

(define results-futures 
    (for/list ([brds (in-slice 10000 (in-permutations (range N)))]) 
    (future 
    (λ() 
     (for/list ([brd (in-list brds)]) 
     (cons (check-diagonals brd) brd)))))) 

(for* ([results-future (in-list results-futures)] 
     [result (in-list (touch results-future))]) 
    (unless (car result) 
    (displayln (cdr result)))) 

Wydaje się, że moje podejrzenia były słuszne, ponieważ zmiana pomaga dużo. Teraz uruchomienie równoległej wersji programu zajmuje tylko 3,9 sekundy dla N = 10, co oznacza przyspieszenie o ponad 10 razy w stosunku do poprzedniej wersji z wykorzystaniem kontraktów futures. Niestety, nadal jest to wolniejsza niż wersja całkowicie sekwencyjna, która trwa tylko ~ 1,4 sekundy. Zwiększenie N do 11 powoduje, że wersja równoległa trwa ~ 44 sekundy, a jeśli wielkość porcji dostarczona do in-slice zostanie zwiększona do 100 000, to zajmie to nawet dłużej, ~ 55 sekund.

Przyjrzenie się przyszłemu wizualizatorowi dla tej wersji programu, z N = 11 i rozmiarem 1 000 000, wydaje mi się, że istnieją pewne okresy przedłużonej równoległości, ale przyszłość jest często blokowana alokacji pamięci:

ma to sens, ponieważ teraz każdy przyszły jest obsługa znacznie więcej pracy, ale to oznacza, kontrakty synchronizacji stale, prawdopodobnie prowadząc do znacznego narzutu wydajności widzę.

W tym momencie nie jestem pewien, czy jest coś więcej, co mogę zmienić, aby poprawić wydajność w przyszłości.Próbowałem ograniczyć alokację przy użyciu wektorów zamiast list i specjalistycznych operacji fixnum, ale z jakiegokolwiek powodu wydawało się to całkowicie zniszczyć paralelizm. Sądziłem, że być może dlatego, że przyszłość nie zaczęła się równolegle, więc zastąpiłem przyszłość przyszłością, ale wyniki były dla mnie mylące, a ja tak naprawdę nie rozumiałem, co mają na myśli.

Mój wniosek jest taki, że przyszłość Racket jest po prostu zbyt delikatna, aby pracować z tym problemem, choć może być prosta. Poddaję się.

---

Teraz, jako mały bonus, postanowiłem spróbować i naśladować to samo w Haskell, ponieważ Haskell ma szczególnie solidną historię dla drobnoziarnistej oceny równoległego. Gdybym nie mógł zwiększyć wydajności w Haskell, nie spodziewałbym się, że uda mi się go zdobyć w Racket.

Pominę wszystkie szczegóły na temat różnych rzeczy próbowałem, ale ostatecznie skończyło się według następującego programu:

import Data.List (permutations) 
import Data.Maybe (catMaybes) 

checkDiagonals :: [Int] -> Bool 
checkDiagonals bd = 
    or $ flip map [0 .. length bd - 1] $ \r1 -> 
    or $ flip map [r1 + 1 .. length bd - 1] $ \r2 -> 
     abs (r1 - r2) == abs ((bd !! r1) - (bd !! r2)) 

n :: Int 
n = 11 

main :: IO() 
main = 
    let results = flip map (permutations [0 .. n-1]) $ \brd -> 
     if checkDiagonals brd then Nothing else Just brd 
    in mapM_ print (catMaybes results) 

byłem w stanie łatwo dodać pewien paralelizm z wykorzystaniem biblioteki Control.Parallel.Strategies. I dodaje linię do głównej funkcji, która wprowadzona jakiś równoległy ocena:

import Control.Parallel.Strategies 
import Data.List.Split (chunksOf) 

main :: IO() 
main = 
    let results = 
     concat . withStrategy (parBuffer 10 rdeepseq) . chunksOf 100 $ 
     flip map (permutations [0 .. n-1]) $ \brd -> 
      if checkDiagonals brd then Nothing else Just brd 
    in mapM_ print (catMaybes results) 

zajęło trochę czasu, aby dowiedzieć się odpowiednią klocek i walcowanie wielkości buforów, ale wartości te dał mi spójnego 30-40% przyspieszenie nad oryginalny, sekwencyjny program.

Oczywiście, czas działania Haskella jest znacznie bardziej odpowiedni do programowania równoległego niż Racket, więc porównanie to nie jest sprawiedliwe. Pomogło mi jednak przekonać się, że pomimo posiadania 4 rdzeni (8 z hiperwątkowością) do mojej dyspozycji, nie byłem w stanie uzyskać nawet 50% przyspieszenia. Miej to w pamięci.

Jak Matthias noted in a mailing list thread I wrote on this subject:

Jedna uwaga na równoległości w ogóle. Nie tak dawno temu ktoś z CS w szkole Ivy League badał wykorzystanie równoległości w różnych zastosowaniach i aplikacjach. Celem było sprawdzenie, jak bardzo "szum" na temat równoległości wpłynął na ludzi. Przypominam sobie, że znaleźli blisko 20 projektów, w których profesorowie (w CE, EE, CS, Bio, Econ itd.) Powiedzieli swoim studentom/doktorantom, aby używali równoległości do szybszego uruchamiania programów. Sprawdzili je wszystkie, a dla N - 1 lub 2 projekty zaczęły działać szybciej po usunięciu paralelizmu. Znacznie szybciej.

Ludzie rutynowo nie doceniają kosztów komunikacji wprowadzanych przez równoległość.

Uważaj, aby nie popełnić tego samego błędu.