Параллельные вычисления Haskell с использованием STArray

Я пытаюсь выполнять вычисления параллельно и записывать результаты в STArray. Я думаю, что этот код показывает, что я пытаюсь сделать. Однако я получаю ошибки компиляции.

import Control.Monad
import Control.Monad.ST
import Control.Parallel
import Data.Array.ST

main = do
    arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
    runSTArray $ do
        par (writeArray arr (1,1) 17) (writeArray arr (2,2) 23)
        return arr
    print arr

Как мне это сделать?


arrays parallel-processing haskell monads state-monad
person Kevin    schedule 09.04.2012    source источник
comment
Я думаю, вам следует использовать Repa для параллельных операций с массивами.   -  person leftaroundabout    schedule 10.04.2012

Ответы (2)


arrow_upward
10
arrow_downward

Вы используете newArray, который имеет тип ST s (STArray s (Int, Int) Int). Однако вы используете его в теле функции main, а это значит, что все, что вы do, должно иметь тип IO. ST не IO, поэтому типы не могут совпадать.

Сначала вы должны переместить newArray в контекст, где у вас есть доступ к монаде ST. Этот контекст, конечно же, доступен в теле runSTArray, поэтому измените тело на:

    runSTArray $ do
        arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
        par (writeArray arr (1,1) 17) (writeArray arr (2,2) 23)
        return arr

Затем вам нужно переосмыслить поведение par. par предназначен для создания параллельных чистых вычислений и не может использоваться для монадических действий; монады вообще не могут быть распараллелены. В частности, монада ST даже не предлагает никаких альтернатив для параллельных вычислений; поскольку параллельная запись в массив может привести к гонкам (что произойдет, если вы перезапишете одну и ту же ячейку? Какая запись будет учитываться, а какая нет?), здесь небезопасно допускать параллелизм. Вы должны изменить массив последовательно:

    runSTArray $ do
        arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
        writeArray arr (1,1) 17
        writeArray arr (2,2) 23
        return arr

Однако запись не дорогая; это расчеты значений, которые могут быть дорогими. Предположим, вы хотите вычислить 17 и 23 на лету; затем вы можете сделать следующее:

let a = someLongCalculation 12534
    b = a `par` (someLongCalculation 24889)
writeArray arr (1, 1) a
writeArray arr (2, 2) b

Наконец, вы должны понимать, что runSTArray возвращает массив результатов, поэтому вы должны хранить его следующим образом:

import Control.Monad
import Control.Monad.ST
import Control.Parallel
import Data.Array.ST

main =
  let pureArr =
        runSTArray $ do
          arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
          writeArray arr (1,1) 17
          writeArray arr (2,2) 23
          return arr
  in print pureArr

Я не думаю, что STArrays здесь правильное решение. Вам следует использовать более мощную библиотеку массивов, такую ​​как repa, в ситуациях, когда вам нужны параллельные вычисления симметричных массивов.

person dflemstr    schedule 09.04.2012
comment
Спасибо, я понял, как выполнять последовательное чтение и запись. Похоже, я застрял, потому что, как вы указываете, монада par не позволяет мне распараллелить эти действия. Мне нужно будет изучить, как добиться параллельной записи в массив с помощью Repa. - person Kevin; 10.04.2012
comment
Это монада ST, которая не позволяет вам выполнять параллелизм. Вы могли бы сделать это в IO с forkIO и компанией, если хотите. - person Louis Wasserman; 10.04.2012
comment
@LouisWasserman Не могли бы вы уточнить? Позволит ли это мне писать в один и тот же массив из всех разветвленных потоков? - person Kevin; 10.04.2012
comment
Изменяемые массивы существуют как для ST, так и для IO, поэтому вы можете использовать их из IO, если вам не нужны гарантии типа, которые предлагает ST. Кроме того, будьте осторожны с гонками, когда дело доходит до параллельных модификаций изменяемых массивов. - person dflemstr; 10.04.2012
comment
Ага. Вы можете писать параллельно в массив IO, хотя, если несколько потоков попытаются записать или прочитать из одних и тех же элементов массива, безопасность потоков будет нарушена. - person Louis Wasserman; 10.04.2012
comment
Познавательный ответ, спасибо. Я даже не искал это, я просто оказался здесь и мне понравилось. - person paulotorrens; 22.01.2017

arrow_upward
1
arrow_downward

par предназначен для параллельного составления чистых операций. вы составляете эффективные операции. вы не можете использовать пар. Более того, параллелизм является эффектом (по крайней мере, когда он состоит из мутаций) и недоступен вам в монаде ST. Я не могу дать вам совет о том, как правильно структурировать ваш код, потому что все слишком урезано, чтобы понять, в чем ваша настоящая проблемная область. Мой общий совет, однако, состоит в том, чтобы использовать явные конструкции параллелизма, такие как fork (в монаде IO) или, чтобы использовать чистые операции, а не изменяемые массивы.

person sclv    schedule 09.04.2012