小编Chr*_*ert的帖子

在Repa中,我想d在我的数组的最内层维度上并行应用一定的线性变换,即在所有"列"向量上.

通常,这样的变换可以表示为一个矩阵M,并且各条目M*v只是适当的行的点积M用v.所以我可以使用traverse一个计算相应点积的函数.这需要付出代价d^2.

但是,我M很特别:它承认了线性工作顺序算法.例如,M可能是1整个下三角形中具有s的下三角矩阵.然后M*v只是部分和的向量v(又名"扫描").这些总和可以以显而易见的方式顺序计算,但是需要结果的(i-1)st条目来i有效地计算该条目.(我有几个这样的M,所有这些都可以在线性顺序时间内以一种方式计算.)

我没有看到任何明显的使用方法traverse(或任何其他的维修功能)来利用这个属性M.可以吗？d^2当有如此快速的线性工作算法时,使用工作算法(即使具有丰富的并行性)将是非常浪费的.

(我看过一些旧的SO帖子(例如,这里)提出类似的问题,但没有什么能与我的情况相符.)

UPDATE

根据请求,这里是一些说明性代码,用于M计算部分和(如上所述).正如我所料,运行时(work)以超线性方式增长d,即array(ext)范围的第二个参数.这来自于这样的事实:mulM'仅指定如何计算i输出的条目,而与所有其他条目无关.即使在阵列的总大小中存在线性时间算法,我也不知道如何在Repa中表达它.

有趣的是,如果删除定义该清单中的线array'从main,则运行时仅线性比例在所述阵列的总大小!因此,当数组被"一直向下"延迟时,融合/优化必须以某种方式提取线性工作算法,但没有任何明确的帮助.这太棒了,但对我来说也不是很有用,因为实际上我需要调用mulM清单数组.

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

module Main where

import Data.Array.Repa as R

-- multiplication by M across …

我关心的是,何时以及何时共享/记忆多态"全局" 类值,特别是跨模块边界.我已经读过这个和这个,但它们似乎并不能反映我的情况,而且我看到了一些与人们对答案的期望不同的行为.

考虑一个暴露一个计算成本高昂的值的类:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}

module A

import Debug.Trace

class Costly a where
  costly :: a

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = trace "costly!" $ (repeat 1) !! 10000000

foo :: Int
foo = costly + 1

costlyInt :: Int
costlyInt = costly

还有一个单独的模块:

module B
import A

bar :: Int
bar = costly + 2

main = do
  print foo
  print bar …