许多并行应用程序的顺序转换在维修
在Repa中，我想要在我的数组的最内维上并行应用某个d维线性变换，即在所有“列”向量上。
通常，这样的变换可以表示为矩阵M ，并且M*v每个条目只是M的适当行与v的点积。 所以，我可以只使用traverse与计算相应的点积的功能。 这花费d^2工作。
但是，我的M是特殊的：它承认线性工作顺序算法。 例如， M可能是整个下三角形中1 s的下三角矩阵。 那么M*v只是v （即“扫描”）的部分和的向量。 这些总和可以以明显的方式顺序计算，但需要结果的(i-1) st条目有效地计算第i个条目。 （我有几个这样的M ，所有这些都可以按照线性顺序时间以某种方式计算）。
我没有看到任何明显的方式来使用traverse （或任何其他的Repa函数）来利用M的这个属性。 可以做到吗？ 当存在如此快速的线性工作算法时，使用d^2工作算法（即使具有丰富的并行性）将是相当浪费的。
（我看过一些旧的SO帖子（例如，在这里）提出了类似的问题，但没有什么与我的情况完全匹配。）
UPDATE
这里请求的是一些说明性代码，用于计算部分和的M （如上所述）。 正如我所料，运行时（工作）在d中超线性增长， d是数组范围的第二个参数（ ext ）。 这是由于mulM'只指定如何计算输出的第i个条目，而与所有其他条目无关。 即使在数组的总大小中有一个线性时间算法，我也不知道如何在Repa中表达它。
有趣的是，如果我从main删除定义清单array'的行，那么运行时只会在数组的总大小中线性缩放！ 所以当数组“延迟”延迟时，融合/优化必须以某种方式提取线性工作算法，但没有任何明确的帮助。 这很神奇，但对我来说也不是很有用，因为实际上我需要在清单数组上调用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"
上一篇: many parallel applications of a sequential transform in repa