0

我正在阅读这篇论文中关于屏障同步算法的伪代码，但我无法完全理解它。

代码的目标是使用称为“软件组合树”的东西为多个线程创建一个屏障（除非所有线程都完成，否则线程不能通过屏障）（不确定它的含义）

这是伪代码（尽管我鼓励你也看看这篇文章）

type node = record
      k : integer             // fan-in of this node
      count : integer         // initialized to k
      locksense : Boolean     // initially false
      parent : ^node          // pointer to parent node; nil if root

  shared nodes : array [0..P-1] of node
      // each element of nodes allocated in a different memory module or cache line
  processor private sense : Boolean  := true
  processor private mynode : ^node    // my group's leaf in the combining tree

  procedure combining_barrier 
      combining_barrier_aux (mynode)      // join the barrier
      sense := not sense                  // for next barrier

  procedure combining_barrier_aux (nodepointer : ^node)
      with nodepointer^ do
          if fetch_and_decrement (&count) = 1     // last one to reach this node
              if parent != nil
                  combining_barrier_aux (parent)
              count := k                          // prepare for next barrier
              locksense := not locksense          // release waiting processors
          repeat until locksense = sense

我知道这意味着构建二叉树，但我不明白一些事情。

  1. P是线程数吗？
  2. 什么是k？什么是“该节点的扇入”
  3. 文章提到线程在树的叶子上被组织成组，什么组？
  4. 每个线程是否只有一个节点？
  5. 如何获得“组合树中我组的叶子”？
4

2 回答 2

1
  1. P是线程数吗？

是的

  1. 什么是k？什么是“该节点的扇入”。

这称为正在构建的树的 ary-ness。这是一棵二叉树，因此 k = 2。这个想法是，对于较少数量的处理器，二叉树就足够了。但是随着处理器数量的增加，树中的层级会增长很多。这可以通过增加 k 的值来增加 ary-ness 来平衡。这实质上将使两个以上的处理器成为叶或组的一部分。随着系统扩展到数千个具有互连功能的处理器，这可能很重要。不利的一面是竞争加剧。随着更多处理器成为同一棵树的一部分，它们将在同一个变量上旋转。

  1. 文章提到线程在树的叶子上被组织成组，什么组？

线程被组织成等于叶子数量的组。叶数本质上是线程数除以ary-ness或 k。因此，对于一组 8 个线程，k=2，叶子的数量将为 4。这允许组中的线程在单个变量上旋转，并且还可以将旋转分布到多个变量，而不是单个共享变量就像在基本的集中障碍算法中一样。

  1. 每个线程是否只有一个节点？

    答案是否定的。当然，至少有与叶子一样多的节点。对于 8 线程问题，4 个叶子将有 4 个节点。现在，在这个平坦级别之后，“赢家”（最后出现的线程）将以递归方式爬上它的父级。级别数将为log P to base k。对于每个父节点，都会有一个节点，最终爬到真正的根或父节点。例如对于 8 线程问题，将有 4 + 2 + 1 = 7 个节点。

  2. 如何获得“组合树中我组的叶子”？

这是一个有点棘手的部分。有一个基于模数和一些整数除法的公式。但是，我还没有看到公开可用的实现。抱歉，我不能透露我只在课堂上看到的内容，因为这可能不合适。可能是谷歌搜索或其他人可以填写。

于 2017-10-14T16:39:48.713 回答
0

只是猜测，不是真实答案

这些节点可能构成一棵具有 P/2 叶的完整二叉树，其中 P 是线程数。每个叶子都分配了两个线程。

每片叶子上的线程相遇，并决定哪些将是“主动的”，哪些将是“被动的”。被动线程等待，而主动线程将它们的输入结合起来并向上移动到父节点以与来自兄弟叶的主动线程会面。然后这两个选择一个活动成员，并且该过程重复，向上移动树，直到一个线程在根处被选为“活动”。

根处的活动线程进行最后的计算，产生一个结果，然后整个事情展开，所有的被动线程都收到结果通知，并被释放以执行它们将要执行的任何操作。

于 2014-02-13T18:44:39.387 回答