July 20th, 2009

with Cat The Cat

SPJ.

Который Саймон Пейтон-Джонс.

Крут.

PS
Сейчас накидаю кое-что.
with Cat The Cat

par и pseq.

Я имел смелость заявить, что Parallel Haskell можно практически ничем не отличается от nested data parallelism (про который и был доклад).

Сейчас я изложу мысли по этому поводу.

Итак, чуть изменённые числа Фибоначчи из презентации выше:
f :: Int -> Int
f x
    | x <= 1 = 1
    | otherwise = a `par` b `seq` a + b
    where
        a = f (x-1)
        b = f (x-2)
Если я правильно всё понимаю, то (практически) на каждый вызов f будет порождено две искры (spark) - вычисление a = f (x-1) и b = f (x-2). Эти искры будут помещены в очередь, откуда их будут вытаскивать нити-работники (нити операционной системы) и выполнять.

Очередь защищена семафорами, поэтому работа с ней накладна. Если размер вычислений в искрах меньше определённого размера (в тактах процессора), то расходы на работу с очередью будут превышать полезную работу. Поэтому параллельное выполнение как-то ограничивают: f x ...| x <= 35 = f (x-1) + f (x-2)....

А что, если создавать специальные массивы для искр?

Для нашей искры a мы создадим массив a_sparks, для b - b_sparks. В них будут укладываться параметры замыкания для вычисления f (x-1) и f (x-2) соответственно. Этот код изменяться не будет. Если у нас есть массив искр для a, то все искры могут быть обработаны параллельно в стиле SIMD (одна программа, много данных), поскольку программа у них одна: \x -> f (x-1).

Если мысленно выполнять программу, то получится вот, что:
- f 10 выполнит `par` и положит 10 в массив a_sparks и b_sparks по индексу 0. Перейдя к вычислению a+b, она форсирует a_sparks@0: (\x -> f (x-1) 10.
- f 9 выполнит `par` и положит 9 в массив a_sparks по индексу 0 и в массив b_sparks по индексу 1. a+b начнёт форсирование a_sparks@0.
- f 8 выполнит `par` и положит 8 в массив a_sparks по индексу 0 и в массив b_sparks по индексу 2. a+b начнёт форсирование a_sparks@0.
- ...
- к моменту начала форсирования любого значения из b_sparks их окажется 10 штук - можно попробовать выполнить код для них параллельно. Это параллельное выполнение создаст несколько (9, как я полагаю на данный момент) штук a_sparks. И их можно попробовать выполнить параллельно.

Получается весьма интересно. По крайней мере, умозрительно. По крайней мере, для меня.

На выходных надо будет попробовать промоделировать.