haskell - Haskell 中并行构建树的策略

Question

我有一个项目正在构建 Decision Tree在 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 

我正在使用 GHcflags -threaded -O2 -rtsopts -eventlog 构建它并使用堆栈执行--性能测试+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)

我怀疑 rdepseq 的递归调用和并行策略可能存在一些问题。如果有经验丰富的 Haskeller 能插话，那真的会让我很开心:)

Answer 1

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

首先，确实有这一行:

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

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

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

然后，evalTraversable 将看到 Right 并在 Question 上运行 parEvalTree，从而产生两个 thunk并行进行深度评估。

不幸的是，事实并非如此，我认为问题是由于额外的 Either String 造成的。为了评估 Question 行(甚至只是 WHNF)，正如 evalTraversable 必须的那样，我们必须弄清楚结果是否是一个 Right decisonTree 或 Left _。这意味着在 parEvalTree 发挥作用之前，必须将 affirmativeTree 和 NegativeTree 评估为 WHNF。不幸的是，由于代码的结构，以这种方式将任一树评估为 WHNF 几乎会强制执行所有操作 — 必须强制选择过滤器才能查看递归 constructTree 调用采用哪个分支，然后它自己对 trainModel 的递归调用被强制以相同的方式进行 WHNF。

可以通过先分别触发 affirmativeTree 和 necessiveTree 来避免这种情况，然后在完全计算完之后才查看 WHNF 形式的结果，通过执行以下操作:

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

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

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

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