5

给定一个（双重）对象链接列表（C++），我有一个我想要多线程的操作来对每个对象执行。每个对象的操作成本并不统一。出于各种原因，链表是这组对象的首选存储。每个对象中的第一个元素是指向下一个对象的指针；第二个元素是列表中的前一个对象。

我通过构建节点数组并应用 OpenMP 解决了这个问题。这给出了不错的表现。然后我切换到我自己的线程例程（基于 Windows 原语）并通过使用 InterlockedIncrement()（作用于数组的索引），我可以获得更高的整体 CPU 利用率和更快的吞吐量。本质上，线程通过沿元素“跨越式”工作。

我的下一个优化方法是尝试消除在我的链表中创建/重用元素数组。但是，我想继续使用这种“跳跃式”方法，并以某种方式使用一些不存在的例程，可以称为“InterlockedCompareDereference” - 以原子方式与 NULL（列表末尾）进行比较并有条件地取消引用并存储，返回取消引用的值.

我不认为 InterlockedCompareExchangePointer() 会起作用，因为我不能原子地取消引用指针并调用这个 Interlocked() 方法。我已经阅读了一些内容，而其他人则建议使用关键部分或自旋锁。关键部分在这里似乎很重要。我很想尝试自旋锁，但我想我首先在这里提出问题并询问其他人在做什么。我不相信 InterlockedCompareExchangePointer() 方法本身可以像自旋锁一样使用。然后还必须考虑获取/释放/栅栏语义......

想法？谢谢！

4

4 回答 4

1

我认为 Casta 有一些优点，我会自己弄一个。这个问题的解决方案将非常重视在每个节点上完成的理念转换，它们是否相互依赖，以及完成的任务是否可以在列表的单一扫描中完成。

如果操作不是相互依赖的，并且扫描方法是有意义的，我建议使用代理获取系统。它实际上与工作组方法相同。每个线程都有一个对管理列表的代理的引用，因为每个线程都需要处理内容，所以它从代理请求它，代理锁定，获取下一个节点，推进内部扫描迭代器，并释放锁定，返回请求线程的节点。这一直持续到列表枚举完成。对于每个节点可能被不同线程多次访问的累加器问题，您可以使用循环列表或其他一些此类容器。有才华的经纪人可以管理列表，包括新的插入、删除等，其方式与分派相同：锁定、操作、解锁。显然有许多活动可以根据您在经纪人方面的特定需求进行定制。这些需求可以构建一个精细的池管理系统，同时在锁定争用方面仍然非常有效（即几乎没有）。

然而，底线是显而易见的。了解您的问题集以及您希望每个线程使用其当前节点完成的具体内容。

于 2012-09-25T21:36:37.367 回答
1

关键部分并不是真正的重量级。假设他们可以快速获得锁，他们的行为就像一个自旋锁。

您的问题的解决方案将取决于您是否正在修改列表。如果您不修改列表，您需要做的就是对初始化为 0 的对象中的值进行 InterlockedCompareExchange 之类的操作。交换值为 1，如果您返回 0，则执行您的操作，如果返回 1，你跳过。下次您在列表上执行操作时，您交换 2 并检查 1/2 而不是 0/1。

如果您要更改列表，那么这一切都取决于。如果您只想向前移动，并且只删除当前节点，那么您最好的选择是在执行比较交换位、跳跃（获取它的下一个节点）和删除时锁定您锁定的项目中的下一个锁定节点。

于 2012-09-25T21:19:39.927 回答
0

由于对齐，列表指针的低位包含零。您可以通过使用比较和交换指令将对象标记为正在处理，以原子方式在其中一个指针中设置这些位之一来利用这一点。

每个线程都会做：

  1. 从头开始遍历列表。
  2. 对于每个列表节点，检查其下一个指针是否设置了低位。
  3. 如果该位设置转到 7。
  4. 比较并交换列表节点的下一个指针(next | 1)。
  5. 如果比较和交换失败转到 7。
  6. 处理对象。
  7. 移动到下一个节点并转到 2。

另一种选择是将此位标记放入对象本身具有未使用位的整数中，除非列表节点是基类或对象的成员。

这样，线程将从列表中获取对象，而不会阻塞或忙于以无等待方式旋转。

于 2012-09-26T16:37:06.713 回答
0

基本上，要尽可能快地浏览列表，您需要避免一些事情；

  • 锁定冲突。即使使用自旋锁，每次循环迭代都是错失完成工作的机会。
  • 记忆障碍。每次执行原子操作时，内存屏障都会停止执行。
  • 不必要的工作，例如扫描列表以查找要做的工作。

我必须同意你的阅读并支持自旋锁。

您将指向列表头部的指针放在易失性指针中。

然后每个线程依次进行；

  • 获取自旋锁
  • 将指针的值保存在临时文件中
  • 更新指向下一个列表条目的指针
  • 释放自旋锁。

然后它可以开始在临时指向的条目上工作。

这对于使用 per-entry lock 来搜索列表有一些好处；

  • 如果每个项目的工作需要很长时间才能完成，那么在更新指针的短时间内您将很少有冲突。
  • 除非发生冲突，否则每个列表项只有 2 个内存屏障，一个用于锁定，一个用于解锁。
  • 无需扫描列表即可获取新的工作项，只需从“队列”中获取工作即可。
于 2012-09-26T15:50:42.637 回答