在Haskell中并行构造树的策略

Question

我有一个项目,我在Haskell中构建一个决策树.生成的树将具有多个彼此独立的分支,因此我认为它们可以并行构建.

该DecisionTree数据类型被限定如下所示:

data DecisionTree =
    Question Filter DecisionTree DecisionTree |    
    Answer DecisionTreeResult

instance NFData DecisionTree where
    rnf (Answer dtr)            = rnf dtr
    rnf (Question fil dt1 dt2)  = rnf fil `seq` rnf dt1 `seq` rnf dt2

这是构造树的算法的一部分

constructTree :: TrainingParameters -> [Map String Value] -> Filter -> Either String DecisionTree    
constructTree trainingParameters trainingData fil =    
    if informationGain trainingData (parseFilter fil) < entropyLimit trainingParameters    
    then constructAnswer (targetVariable trainingParameters) trainingData    
    else
        Question fil <$> affirmativeTree <*> negativeTree `using` evalTraversable parEvalTree    
        where   affirmativeTree   = trainModel trainingParameters passedTData    
                negativeTree      = trainModel trainingParameters failedTData    
                passedTData       = filter (parseFilter fil) trainingData    
                failedTData       = filter (not . parseFilter fil) trainingData

parEvalTree :: Strategy DecisionTree    
parEvalTree (Question f dt1 dt2) = do    
    dt1' <- rparWith rdeepseq dt1    
    dt2' <- rparWith rdeepseq dt2    
    return $ Question f dt1' dt2'
parEvalTree ans = return ans

trainModel递归调用constructTree.并行的相关路线是

Question fil <$> affirmativeTree <*> negativeTree `using` evalTraversable parEvalTree 

我正在使用GHC标志构建-threaded -O2 -rtsopts -eventlog它并运行它 stack exec -- performance-test +RTS -A200M -N -s -l (我在2核机器上).

但它似乎并没有并行运行

SPARKS: 164 (60 converted, 0 overflowed, 0 dud, 0 GC'd, 104 fizzled)

INIT    time    0.000s  (  0.009s elapsed)
MUT     time   29.041s  ( 29.249s elapsed)
GC      time    0.048s  (  0.015s elapsed)
EXIT    time    0.001s  (  0.006s elapsed)
Total   time   29.091s  ( 29.279s elapsed)

我怀疑使用rdeepseq和并行策略的递归调用可能存在一些问题.如果一些经验丰富的Haskeller会发出声响,那真的会让我的一天成真:)

Answer 1

我不是 Haskell 性能/并行性方面的专家，但我认为这里发生了一些事情。

首先，确实有这一行：

Question fil <$> affirmativeTree <*> negativeTree `using` evalTraversable parEvalTree 

据推测，人们可能期望该行的第一部分构建一个看起来像这样的数据结构

                      +-------+
                      | Right |
                      +-------+
                          |
                    +----------+
                    | Question |
                    +----------+
                     |   |    |
   +-----------------+   |    +-----------+
   |                +----+                |
   |                |                     |
+-----+   +-------------------+   +----------------+
| fil |   |       THUNK       |   |     THUNK      |
+-----+   | (affirmativeTree) |   | (negativeTree) |
          +-------------------+   +----------------+

然后，evalTraversable将看到并在 上Right运行，从而引发两个 thunk 并行进行深度评估。parEvalTreeQuestion

不幸的是，事实并非如此，我认为问题是由于额外的Either String. 为了评估这Question条线（即使只是评估 WHNF），evalTraversable我们必须弄清楚结果是 aRight decisonTree还是 a Left _。这意味着affirmativeTree和negativeTree必须先评估为 WHNF，然后parEvalTree才能发挥作用。不幸的是，由于代码的结构，以这种方式将任一树评估为 WHNF 几乎会强制执行所有操作 — 必须强制选择过滤器才能查看递归调用constructTree采用哪个分支，然后对其自己的递归调用trainModel被迫以同样的方式 WHNF。

可以通过首先单独触发affirmativeTree和来避免这种情况negativeTree，然后在有时间完全计算后才查看 WHNF 形式的结果，方法如下：

uncurry (Question fil) <$> bisequence ((affirmativeTree, negativeTree) `using` parTuple2 rdeepseq rdeepseq)

如果您使用此行替换原始代码来运行代码并将其加载到 ThreadScope 中，您将看到并行性明显有所增加：活动图在一些地方短暂地超过 1，并且执行在几个地方的 HEC 之间跳转。不幸的是，程序的绝大多数时间仍然花在顺序执行上。

我尝试对此进行一些研究，并且我认为您的树构建代码中的某些内容可能有点右偏。我添加了一些traceMarkers 和traceEvents，看起来过滤器的正侧和负侧之间经常存在相当大的不平衡，这使得并行执行不能很好地工作：正子树往往会很快完成，而负子树往往会非常快地完成子树需要很长时间，创建看起来基本上是顺序执行的。在某些情况下，正子树非常小，以至于引发计算的核心完成计算，然后在另一个核心醒来窃取工作之前开始负子树。这就是 ThreadScope 中单核上长时间运行的来源。您可以在图表开头看到的具有相当多并行性的短时间段是执行第一个过滤器的负子树的时间，因为这是主过滤器，其负子树足够大以真正做出贡献到并行性。在跟踪的后面还有一些类似的（但小得多）事件，其中创建了合理大小的负树。

我希望如果您进行上述更改并尝试找到更均匀地划分数据集的过滤器，您应该会看到此代码的并行性有相当大的增加。