30

dRepa では、配列の最も内側の次元、つまりすべての「列」ベクトルに対して、特定の次元の線形変換を並列に適用したいと考えています。

一般に、このような変換は行列として表すことができM、 の各エントリはwithM*vの適切な行の内積です。したがって、適切な内積を計算する関数を使用できます。これには手間がかかります。Mvtraversed^2

ただし、 myMは特別です。線形作業の順次アルゴリズムを受け入れます。たとえば、は、下三角全体に s がMある下三角行列である可能性があります。1次に、 （別名「スキャン」）M*vの部分和のベクトルです。vこれらの合計は、明らかな方法で順次計算できますが、効率的に th エントリ(i-1)を計算するには、結果の st エントリが必要です。i（私はそのような をいくつか持っていMますが、それらはすべて線形順次時間で何らかの方法で計算できます。）

traverseのこのプロパティを利用するために (または他の Repa 関数を)使用する明確な方法がわかりませんM。それはできますか？d^2このような高速な線形作業アルゴリズムが利用可能な場合、(豊富な並列処理を使用しても) 作業アルゴリズムを使用するのは非常に無駄です。

(古い SO の投稿 (例: here ) で同様の質問をしているのを見たことがありますが、私の状況と完全に一致するものはありません。)

アップデート

M要求に応じて、 (上記のように) 部分和を計算するの例示的なコードを次に示します。d予想通り、ランタイム (作業)は、配列 ( ) のエクステントの 2 番目の引数 で超線形に増加しextます。これは、他のすべてのエントリとは関係なく、出力の th エントリmulM'を計算する方法のみを指定するという事実に由来します。i配列の合計サイズに線形時間アルゴリズムがあるのに、それを Repa で表現する方法がわかりません。

array'興味深いことに、マニフェストを定義する行をから削除するとmain、ランタイムは配列の合計サイズに対して線形にしかスケーリングしません! そのため、配列が「完全に」遅延している場合、融合/最適化は何らかの方法で線形作業アルゴリズムを抽出している必要がありますが、明示的な助けはありません。これは驚くべきことですが、私にとってはあまり役に立ちません。実際にはmulM、マニフェスト配列を呼び出す必要があるからです。

{-# LANGUAGE TypeOperators, ScopedTypeVariables, FlexibleContexts #-}

module Main where

import Data.Array.Repa as R

-- multiplication by M across innermost dimension
mulM arr = traverse arr id mulM'
    where mulM' _ idx@(i' :. i) =
              sumAllS $ extract (Z:.0) (Z:.(i+1)) $ slice arr (i' :. All)

ext = Z :. (1000000::Int) :. (10::Int) -- super-linear runtime in 2nd arg
--ext = Z :. (10::Int) :. (1000000::Int) -- takes forever

array = fromFunction ext (\(Z:.j:.i) -> j+i)

main :: IO ()
main = do
  -- apply mulM to a manifest array
  array' :: Array U DIM2 Int <- computeP $ array
  ans :: Array U DIM2 Int <- computeP $ mulM array'
  print "done"
4

0 に答える 0