Многоядерное программирование в Haskell - Control.Parallel

Question

Я пытаюсь узнать, как использовать модуль Control.Parallel, но я думаю, что я не понял его.

Я пытаюсь запустить следующий код (fibs.hs).

import Control.Parallel 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = p `par` (q `pseq` (p + q)) 
    where 
     p = fib (n-1) 
     q = fib (n-2) 


main = print $ fib 30 

Я составил это с:

ghc -O2 --make -threaded fibs.hs 

И тогда я получаю следующие результаты, исполняющие эту программу (вывод скрипта Python, который работает каждую программу в 100 раз и возвращает среднее и стандартное отклонение время выполнения):

./fibs +RTS -N1 -> avg= 0.060203 s, deviation = 0.004112 s 
./fibs +RTS -N2 -> avg= 0.052335 s, deviation = 0.006713 s 
./fibs +RTS -N3 -> avg= 0.052935 s, deviation = 0.006183 s 
./fibs +RTS -N4 -> avg= 0.053976 s, deviation = 0.007106 s 
./fibs +RTS -N5 -> avg= 0.055227 s, deviation = 0.008598 s 
./fibs +RTS -N6 -> avg= 0.055703 s, deviation = 0.006537 s 
./fibs +RTS -N7 -> avg= 0.058327 s, deviation = 0.007526 s 

Мои вопросы:

1. Что именно происходит, когда я оцениваю:

   a `par` (b `pseq` (a + b)) ? 
   

   Я понимаю, что par б должен намекнуть компилятор о рассчет параллельно с Ъ и Ь вернуться. ОК. Но что делает pseq?

2. Почему я вижу такое небольшое увеличение производительности? Я запускаю это в четырехъядерном процессоре Intel Core 2. Я ожидаю, что работа с -N5 или -N6 не повлияет на производительность или что программа действительно начнет работать очень плохо. Но почему я не вижу улучшения от -N2 до -N3 и почему первоначальное улучшение настолько мало?

Answer 1

Как Дон explained, проблема в том, что вы создаете слишком много искр. Вот как вы можете переписать его, чтобы получить хорошее ускорение.

import Control.Parallel 

cutoff :: Int 
cutoff = 20 

parFib :: Int -> Int 
parFib n | n < cutoff = fib n 
parFib n = p `par` q `pseq` (p + q) 
    where 
     p = parFib $ n - 1 
     q = parFib $ n - 2 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = fib (n - 1) + fib (n - 2) 

main :: IO() 
main = print $ parFib 40 

демонстрация:

[computer ~]$ ghc --make -threaded -O2 Main.hs 
[1 of 1] Compiling Main    (Main.hs, Main.o) 
Linking Main ... 
[computer ~]$ time ./Main +RTS -N1 
102334155 

real 0m1.509s 
user 0m1.450s 
sys  0m0.003s 
[computer ~]$ time ./Main +RTS -N2 
102334155 

real 0m0.776s 
user 0m1.487s 
sys  0m0.023s 
[computer ~]$ time ./Main +RTS -N3 
102334155 

real 0m0.564s 
user 0m1.487s 
sys  0m0.030s 
[computer ~]$ time ./Main +RTS -N4 
102334155 

real 0m0.510s 
user 0m1.587s 
sys  0m0.047s 
[computer ~]$ 

Answer 2

Re (1): par позволяет a быть вычислены в другом потоке. Я предполагаю, что здесь, но я думаю, что pseq ведет себя как seq: он сначала вычисляет первый результат (ну, seq не гарантирует это, но на практике это делает GHC). Таким образом, в этом случае вычисление a разветвляется как один поток, а другой поток вычисляет b, а затем суммы a и b.

Re (2): Это довольно тривиальное вычисление, которое разветвляется на другие потоки; это, вероятно, так же быстро, как процессор вычислить его сам. Я делаю ставку на то, что накладные потоки повреждают почти столько же, сколько помогают в этом простом вычислении.

Answer 3

Вы создаете экспоненциальное количество искр (подумайте о том, сколько рекурсивных вызовов вы создаете здесь). Чтобы на самом деле получить хороший параллелизм, вам нужно создать less параллельной работы в этом случае, так как ваше оборудование не может обрабатывать столько потоков (и поэтому GHC их не делает).

Решение использовать стратегию отсечения, как описано в этом разговоре: http://donsbot.wordpress.com/2009/09/05/defun-2009-multicore-programming-in-haskell-now/

В основном, переключение на прямой линии версии, как только вы достигнете определенной глубины, и использование + RTS -sstderr, чтобы узнать, сколько искры преобразуются, поэтому вы можете определить, тратите ли вы свою работу или нет.

Answer 4

Поскольку никто не дал окончательного ответа о pseq, вот official description:

семантически идентичны SEQ, но с тонкой оперативной разницы: сл строго в обоих аргументах, , поэтому компилятор может, например, перегруппировка a seq b на b seq a seq b. Обычно это не проблема при использовании seq для выражения строгости, , но это может быть проблемой, когда аннотирующий код для параллелизма, , потому что нам нужно больше контроля над оценкой ; мы можем хотеть, чтобы оценил a до b, потому что мы знаем , что b уже был искривлен в , параллельном пар.

Вот почему у нас есть pseq. В отличие от в SEQ, pseq является строгим только в его первого аргумента (насколько компилятор обеспокоен), что ограничивает преобразования, которые компилятор может сделать, и гарантирует, что пользователь может сохранить контроль оценки заказ.