Dlaczego nie ma ukrytego paralelizmu w Haskell?

Question

Haskell jest funkcjonalny i czysty, więc zasadniczo ma wszystkie właściwości potrzebne kompilatorowi do pokonania implicit parallelism.

Rozważmy ten trywialny przykład:

f = do 
    a <- Just 1 
    b <- Just $ Just 2 
    --^The above line does not utilize an `a` variable, so it can be safely 
    -- executed in parallel with the preceding line 
    c <- b 
    --^The above line references a `b` variable, so it can only be executed 
    -- sequentially after it 
    return (a, c) 
    -- On the exit from a monad scope we wait for all computations to finish and 
    -- gather the results 

schematyczny plan wykonania można opisać jako:

   do 
       | 
     +---------+---------+ 
     |     | 
    a <- Just 1  b <- Just $ Just 2 
     |     | 
     |     c <- b 
     |     | 
     +---------+---------+ 
       | 
      return (a, c) 

Dlaczego nie ma takich funkcjonalności zaimplementowane w kompilatora z flagą lub jeszcze pragma? Jakie są praktyczne powody?

Answer 1

To jest długo studiowany temat.Chociaż można niejawnie wyprowadzić paralelizm w kodzie Haskella, problemem jest to, że istnieje zbyt dużo równoległości, przy zbyt drobnym ziarnie, dla obecnego sprzętu.

Koniec końców wysiłek włożono w księgowość, a nie w szybsze działanie.

Ponieważ nie mamy nieskończoną sprzętu równoległego, to wszystko o wybranie właściwej ziarnistości - zbyt gruba i nie będzie bezczynne procesory, zbyt fi ne i koszty ogólne będzie nie do przyjęcia.

To, co mamy, to bardziej gruboziarniste równoległości (iskry) odpowiednie do generowania tysięcy lub milionów równoległych zadań (a więc nie na poziomie instrukcji), które są mapowane na zaledwie garść rdzeni, które zwykle mamy do dzisiaj.

Należy zauważyć, że w przypadku niektórych podzbiorów (na przykład przetwarzania tablic) istnieją w pełni automatyczne biblioteki równoległe z ciasnymi modelami kosztów.

Dla tła na tym patrz, http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf, gdzie wprowadzają zautomatyzowane podejście do wstawiania par w dowolnych programach Haskell.

Answer 2

Podczas gdy blok kodu nie może być najlepszym przykładem z powodu ukrytych danych zależność pomiędzy a i b, warto zauważyć, że te dwa Wiązania dojeżdżać w tym

f = do 
    a <- Just 1 
    b <- Just $ Just 2 
    ... 

dadzą takie same wyniki

f = do 
    b <- Just $ Just 2 
    a <- Just 1 
    ... 

, więc można to nadal zrównoleglać w sposób spekulacyjny. Warto zauważyć, że to nie musi mieć nic wspólnego z monadami. Możemy na przykład ocenić wszystkie niezależne wyrażenia w jednostce let -block lub możemy wprowadzić wersję , która by to zrobiła. W tym celu użyto narzędzia lparallel library dla Common Lisp.

Nie jestem żadnym ekspertem w tej dziedzinie, ale to jest moje zrozumienie problemu: . Głównym utrudnieniem jest ustalenie, kiedy jest korzystne zrównoleglanie oceny wielokrotnych wyrażeń z . Istnieje obciążenie związane z uruchamianiem oddzielnych wątków do oceny i, jak pokazuje twój przykład, może to spowodować w marnowaniu pracy. Niektóre wyrażenia mogą być zbyt małe, aby ocena równoległa była warta narzutu. Jak rozumiem, nadchodząc, w pełni dokładna metryka kosztu wyrażenia będzie równała się rozwiązaniu problemu zatrzymania, a więc jesteś spadkobiercą do korzystania z heurystycznego podejścia do ustalania, co do oceniać równolegle.

Wówczas nie zawsze szybciej rzuca się więcej rdzeni na problem. Nawet jeśli jawnie paralelnie problem z wieloma dostępnymi bibliotekami Haskella, , często nie zauważysz zbyt dużej prędkości tylko przez ocenianie wyrażeń równolegle z powodu dużej alokacji i wykorzystania pamięci oraz obciążenia, które to nakłada na pamięć podręczną kolektora i procesora pamięci podręcznej. Koniec z potrzebą ładnego kompaktowego układu pamięci i do inteligentnego przemierzania danych. Mając 16 wątków powiązanych z listami, po prostu wązi cię na magistrali pamięci i może faktycznie spowolnić działanie.

Przynajmniej, co wyrażenia można skutecznie parallelized jest czymś nieoczywisty dla wielu programistów (przynajmniej nie do tego), więc coraz kompilator zrobić to skutecznie to nietrywialne .

Answer 3

Krótka odpowiedź: Czasami równoległe uruchamianie sprzętu okazuje się wolniejsze, a nie szybsze. I ustalenie, kiedy jest, a kiedy nie jest dobrym pomysłem, jest nierozwiązanym problemem badawczym.

Jednak nadal "można nagle wykorzystać wszystkie te rdzenie, nie zawracając sobie głowy wątkami, zakleszczeniami i warunkami wyścigu". To nie jest automatyczne; wystarczy podać kompilatorowi wskazówki, gdzie to zrobić! :-D

Answer 4

Jednym z powodów jest to, że Haskell nie jest restrykcyjny i domyślnie nic nie ocenia. W ogólności kompilator nie wie, że wyliczenie a i b kończy stąd próbuje obliczyć byłoby marnotrawstwo zasobów:

x :: Maybe ([Int], [Int]) 
x = Just undefined 
y :: Maybe ([Int], [Int]) 
y = Just (undefined, undefined) 
z :: Maybe ([Int], [Int]) 
z = Just ([0], [1..]) 
a :: Maybe ([Int], [Int]) 
a = undefined 
b :: Maybe ([Int], [Int]) 
b = Just ([0], map fib [0..]) 
    where fib 0 = 1 
      fib 1 = 1 
      fib n = fib (n - 1) + fib (n - 2) 

Rozważmy to dla następujących funkcji

main1 x = case x of 
       Just _ -> putStrLn "Just" 
       Nothing -> putStrLn "Nothing" 

(a, b) część nie potrzebują do oceny. Jak najszybciej dostać się, że x = Tylko _ można przystąpić do gałęzi - stąd to będzie działać dla wszystkich wartości, ale a

main2 x = case x of 
       Just (_, _) -> putStrLn "Just" 
       Nothing -> putStrLn "Nothing" 

Funkcja ta wymusza ocenę krotki. Stąd x zakończy się z błędem, podczas gdy reszta będzie działać.

main3 x = case x of 
       Just (a, b) -> print a >> print b 
       Nothing -> putStrLn "Nothing" 

Ta funkcja najpierw wydrukuje pierwszą listę, a następnie drugą. Będzie działać dla z (w wyniku drukowania nieskończony strumień liczb, ale Haskell może sobie z tym poradzić). b w końcu zabraknie pamięci.

Generalnie nie wiadomo, czy kończy się obliczenia i ile zasobów zużyje. Nieskończone listy są perfekcyjnie w Haskell:

main = maybe (return()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers 

Stąd tarła wątki do oceny ekspresji w Haskell może próbować oceniać coś, co nie ma być w pełni ocenione - wykaz wszystkich liczb pierwszych powiedzieć - jeszcze programiści używać jako część struktury .Powyższe przykłady są bardzo proste i możesz argumentować, że kompilator je zauważył - jednak generalnie nie jest to możliwe z powodu problemu z zatrzymaniem (nie możesz napisać programu, który bierze dowolny program i jego wejście i sprawdzić, czy się kończy) - dlatego nie jest to możliwe bezpieczna optymalizacja.

Ponadto - o czym wspominają inne odpowiedzi - trudno jest przewidzieć, czy dodatkowe nakłady wątku są warte zaangażowania. Mimo że GHC nie odradza nowych wątków iskier za pomocą zielonego wątku (z ustaloną liczbą wątków jądra - odkładając na bok kilka wyjątków) nadal musisz przenieść dane z jednego rdzenia do drugiego i zsynchronizować między nimi, co może być dość kosztowne.

Jednak Haskell ma kierowaną równoległość bez łamania czystości języka przez par i podobne funkcje.

Answer 5

W rzeczywistości była taka próba, ale nie na zwykłym sprzęcie ze względu na niską dostępną ilość rdzeni. Projekt nosi nazwę . Działa z kodem Haskella z wysokim poziomem paralelizmu. W przypadku, gdyby kiedykolwiek został wydany jako proper 2 GHz ASIC core, mielibyśmy poważny przełom w szybkości wykonywania Haskell.