Programing

Repa 배열의 병렬 mapM

lottogame 2020. 9. 12. 11:21
반응형

Repa 배열의 병렬 mapM


내 최근에 작업 과 함께 Gibbs sampling, 나는의 잘 사용하고 봤는데 RVar내 관점에서, 난수 생성에 가까운 이상적인 인터페이스를 제공합니다. 안타깝게도 맵에서 모나 딕 액션을 사용할 수 없어서 Repa를 사용할 수 없었습니다.

명확하게 모나 딕 맵은 일반적으로 병렬화 할 수 없지만 RVar효과를 안전하게 병렬화 할 수있는 모나드의 한 가지 예일 수 있습니다 (적어도 원칙적으로는의 내부 작업에별로 익숙하지 않습니다 RVar). . 즉, 다음과 같이 쓰고 싶습니다.

drawClass :: Sample -> RVar Class
drawClass = ...

drawClasses :: Array U DIM1 Sample -> RVar (Array U DIM1 Class)
drawClasses samples = A.mapM drawClass samples

어디 A.mapM같이 보일 것입니다,

mapM :: ParallelMonad m => (a -> m b) -> Array r sh a -> m (Array r sh b)

이것이 작동하는 방법은의 구현 RVar과 그 기반 에 결정적으로 달려 있지만 RandomSource원칙적으로 이것은 생성 된 각 스레드에 대해 새로운 임의의 시드를 그리고 평소와 같이 진행하는 것을 포함한다고 생각할 것입니다.

직관적으로, 이와 동일한 아이디어가 다른 모나드에도 일반화 될 수있는 것 같습니다.

그래서, 제 질문은 : ParallelMonad효과가 안전하게 병렬화 될 수있는 모나드 의 클래스 구성 할 수 RVar있습니까 (아마도 적어도에 의해 거주 )?

어떤 모습일까요? 이 클래스에 어떤 다른 모나드가있을 수 있습니까? 다른 사람들이 이것이 Repa에서 어떻게 작동 할 수 있는지에 대한 가능성을 고려 했습니까?

마지막으로, 병렬 모나 딕 동작의 개념을 일반화 할 수없는 경우, RVar(매우 유용한 경우) 특정 경우에이 작업을 수행 할 수있는 좋은 방법이 있습니까? RVar병렬 처리를 포기 하는 것은 매우 어려운 트레이드 오프입니다.


PRNG의 본질적으로 순차적 인 특성으로 인해 이렇게하는 것은 좋은 생각이 아닙니다. 대신 다음과 같이 코드를 전환 할 수 있습니다.

  1. IO 함수를 선언합니다 ( main또는 무엇을 가지고 있는지).
  2. 필요한만큼 난수를 읽으십시오.
  3. repa 함수에 (이제 순수한) 숫자를 전달하십시오.

이 질문을받은 지 7 년이 지났지 만 아직 아무도이 문제에 대한 좋은 해결책을 찾지 못한 것 같습니다. Repa에는 mapM/ traverselike 기능이 없으며 병렬화없이 실행할 수있는 기능도 없습니다. 더욱이 지난 몇 년 동안의 진전 정도를 고려할 때도 그렇게 될 것 같지 않습니다.

Haskell의 많은 어레이 라이브러리의 오래된 상태와 기능 세트에 대한 전반적인 불만족으로 인해 저는 massivRepa에서 몇 가지 개념을 차용했지만 완전히 다른 수준으로 가져가는 어레이 라이브러리에 몇 년 동안 작업 했습니다. 인트로로 충분합니다.

오늘 이전에는 함수와 같은 세 가지 모나드 맵이있었습니다 massiv(함수와 같은 동의어는 포함하지 않음 : imapM, forMet al.).

  • mapM-임의의 Monad. 명백한 이유로 병렬화 할 수 없으며 약간 느립니다 ( mapM목록에 비해 평소의 줄을 따라 느림)
  • traversePrim-여기서 우리는로 제한되어 있습니다 PrimMonad. 이는보다 훨씬 빠르지 만이 mapM논의에서는 그 이유가 중요하지 않습니다.
  • mapIO-이것은 이름에서 알 수 있듯이로 제한됩니다 IO(또는 오히려 MonadUnliftIO이지만 관련이 없음). 우리는 IO코어 수만큼 자동으로 배열을 분할하고 별도의 작업자 스레드를 사용 IO하여 해당 청크의 각 요소에 대한 작업 을 매핑 할 수 있습니다. fmap병렬화도 가능한 pure와는 달리 , IO매핑 작업의 부작용과 결합 된 스케줄링의 비결 정성 때문에 여기에 있어야합니다 .

그래서이 질문을 읽은 후 문제는에서 실질적으로 해결 massiv되지만 그렇게 빠르지 는 않다고 생각했습니다 . in mwc-randomin random-fu같은 난수 생성기는 여러 스레드에서 동일한 생성기를 사용할 수 없습니다. 즉, 내가 놓친 유일한 퍼즐 조각은 "생성 된 각 스레드에 대해 새로운 무작위 시드를 그리고 평소대로 진행하는 것"이었습니다. 즉, 두 가지가 필요했습니다.

  • 작업자 스레드가있을 수있는만큼의 생성기를 초기화하는 함수
  • 액션이 실행되는 스레드에 따라 매핑 함수에 올바른 생성기를 원활하게 제공하는 추상화.

그게 바로 제가 한 일입니다.

먼저 질문과 더 관련이 있는 특수 제작 randomArrayWSinitWorkerStates기능을 사용하여 예제를 제공 하고 나중에보다 일반적인 모나드 맵으로 이동합니다. 유형 서명은 다음과 같습니다.

randomArrayWS ::
     (Mutable r ix e, MonadUnliftIO m, PrimMonad m)
  => WorkerStates g -- ^ Use `initWorkerStates` to initialize you per thread generators
  -> Sz ix -- ^ Resulting size of the array
  -> (g -> m e) -- ^ Generate the value using the per thread generator.
  -> m (Array r ix e)
initWorkerStates :: MonadIO m => Comp -> (WorkerId -> m s) -> m (WorkerStates s)

에 익숙하지 않은 사람들을 massiv위해 Comp인수는 사용할 계산 전략이며 주목할만한 생성자는 다음과 같습니다.

  • Seq -스레드를 분기하지 않고 순차적으로 계산 실행
  • Par -기능이있는만큼 스레드를 회전하고이를 사용하여 작업을 수행합니다.

mwc-random처음에는 패키지를 예제로 사용 하고 나중에 다음으로 이동합니다 RVarT.

λ> import Data.Massiv.Array
λ> import System.Random.MWC (createSystemRandom, uniformR)
λ> import System.Random.MWC.Distributions (standard)
λ> gens <- initWorkerStates Par (\_ -> createSystemRandom)

Above we initialized a separate generator per thread using system randomness, but we could have just as well used a unique per thread seed by deriving it from the WorkerId argument, which is a mere Int index of the worker. And now we can use those generators to create an array with random values:

λ> randomArrayWS gens (Sz2 2 3) standard :: IO (Array P Ix2 Double)
Array P Par (Sz (2 :. 3))
  [ [ -0.9066144845415213, 0.5264323240310042, -1.320943607597422 ]
  , [ -0.6837929005619592, -0.3041255565826211, 6.53353089112833e-2 ]
  ]

By using Par strategy the scheduler library will split evenly the work of generation among available workers and each worker will use it's own generator, thus making it thread safe. Nothing prevents us from reusing the same WorkerStates arbitrary number of times as long as it is not done concurrently, which otherwise would result in an exception:

λ> randomArrayWS gens (Sz1 10) (uniformR (0, 9)) :: IO (Array P Ix1 Int)
Array P Par (Sz1 10)
  [ 3, 6, 1, 2, 1, 7, 6, 0, 8, 8 ]

Now putting mwc-random to the side we can reuse the same concept for other possible uses cases by using functions like generateArrayWS:

generateArrayWS ::
     (Mutable r ix e, MonadUnliftIO m, PrimMonad m)
  => WorkerStates s
  -> Sz ix --  ^ size of new array
  -> (ix -> s -> m e) -- ^ element generating action
  -> m (Array r ix e)

and mapWS:

mapWS ::
     (Source r' ix a, Mutable r ix b, MonadUnliftIO m, PrimMonad m)
  => WorkerStates s
  -> (a -> s -> m b) -- ^ Mapping action
  -> Array r' ix a -- ^ Source array
  -> m (Array r ix b)

Here is the promised example on how to use this functionality with rvar, random-fu and mersenne-random-pure64 libraries. We could have used randomArrayWS here as well, but for the sake of example let's say we already have an array with different RVarTs, in which case we need a mapWS:

λ> import Data.Massiv.Array
λ> import Control.Scheduler (WorkerId(..), initWorkerStates)
λ> import Data.IORef
λ> import System.Random.Mersenne.Pure64 as MT
λ> import Data.RVar as RVar
λ> import Data.Random as Fu
λ> rvarArray = makeArrayR D Par (Sz2 3 9) (\ (i :. j) -> Fu.uniformT i j)
λ> mtState <- initWorkerStates Par (newIORef . MT.pureMT . fromIntegral . getWorkerId)
λ> mapWS mtState RVar.runRVarT rvarArray :: IO (Array P Ix2 Int)
Array P Par (Sz (3 :. 9))
  [ [ 0, 1, 2, 2, 2, 4, 5, 0, 3 ]
  , [ 1, 1, 1, 2, 3, 2, 6, 6, 2 ]
  , [ 0, 1, 2, 3, 4, 4, 6, 7, 7 ]
  ]

It is important to note, that despite the fact that pure implementation of Mersenne Twister is being used in the above example, we cannot escape the IO. This is because of the non-deterministic scheduling, which means that we never know which one of the workers will be handling which chunk of the array and consequently which generator will be used for which part of the array. On the up side, if the generator is pure and splittable, such as splitmix, then we can use the pure, deterministic and parallelizable generation function: randomArray, but that is already a separate story.

참고URL : https://stackoverflow.com/questions/11230895/parallel-mapm-on-repa-arrays

반응형