2

我有一堆线程和一堆计数器。线程递减计数器，如果计数器达到零，就会发生有趣的事情。使用原子操作实现这一点很简单。

但是，如果我们需要两个属性来保持而不考虑线程或计数器的数量，这将变得更加困难：

  1. 可扩展性：递减一个计数器是 O(polylog)。
  2. 紧凑性：每个计数器的内存为 O(1)。

我知道如何单独执行其中任何一项：简单的实现是紧凑的，分层计数网络 [4] 是可扩展的）。有可能两者都做吗？

注意：由于 O(n) 个线程不能在 O(n) 时间内做出 O(n) 个不同的更改 O(1) 个内存，因此解决此问题需要在不同计数器之间共享数据结构。

[4]：J. Aspnes、M. Herlily 和 N. Shavit。计数网络。ACM 杂志，41(5):1020-1048，1994 年 9 月。

更新：Jed Brown 指出了一个明显的事实，即 O(1) 时间是不可能的。更改为多对数。

4

2 回答 2

0

有一篇关于可扩展计数器的论文。您基本上有一棵树，其中每个线程都有一个节点，并且一个希望 inc/dec 发布该事实的线程，然后它开始爬树，直到顶部的计数器，累积 inc/dec 值在途中，然后将总数应用于顶部的柜台。（这就是它的要点——很多额外的细节）。

它将 inc/dec 分布在单个缓存行之外，这当然会妨碍可伸缩性。

在http://www.liblfds.org查看 wiki 中的白皮书- 你会在那里找到它。

于 2012-07-29T10:46:22.613 回答