在HLSL DirectCompute着色器中实现SpinLock

Question

我试图在计算着色器中实现自旋锁。但是我的实现似乎并没有锁住任何东西。

这是我实现自旋锁的方式：

void LockAcquire()
{
    uint Value = 1;

    [allow_uav_condition]
    while (Value) {
        InterlockedCompareExchange(DataOutBuffer[0].Lock, 0, 1, Value);
    };
}

void LockRelease()
{
    uint Value;
    InterlockedExchange(DataOutBuffer[0].Lock, 0, Value);
}

背景：我需要使用自旋锁，因为我必须在一个大的二维数组中计算数据总和。这个总和是一个双精度浮点数。使用单个线程和双重循环计算总和可以产生正确的结果。然而，使用多线程计算总和会产生错误的结果，即使引入了自旋锁以避免计算总和时发生冲突。

我不能使用InterLockedAdd，因为总和不适合32位整数，并且我正在使用着色器模型5（编译器47）。

这里是单线程版本，产生正确的结果：

[numthreads(1, 1, 1)]
void CSGrayAutoComputeSumSqr(
    uint3 Gid  : SV_GroupID,
    uint3 DTid : SV_DispatchThreadID, // Coordinates in RawImage window
    uint3 GTid : SV_GroupThreadID,
    uint  GI   : SV_GroupIndex)
{
    if ((DTid.x == 0) && (DTid.y == 0)) {
        uint2 XY;
        int   Mean = (int)round(DataOutBuffer[0].GrayAutoResultMean);
        for (XY.x = 0; XY.x < (uint)RawImageSize.x; XY.x++) {
            for (XY.y = 0; XY.y < (uint)RawImageSize.y; XY.y++) {
                int  Value  = GetPixel16BitGrayFromRawImage(RawImage, rawImageSize, XY);
                uint UValue = (Mean - Value) * (Mean - Value);
                DataOutBuffer[0].GrayAutoResultSumSqr += UValue;
            }
        }
    }
}

以下是多线程版本。每次执行此版本会产生类似但不同的结果，我认为这是由于锁未正常工作引起的。

[numthreads(1, 1, 1)]
void CSGrayAutoComputeSumSqr(
    uint3 Gid  : SV_GroupID,
    uint3 DTid : SV_DispatchThreadID, // Coordinates in RawImage window
    uint3 GTid : SV_GroupThreadID,
    uint  GI   : SV_GroupIndex)
{
    int  Value  = GetPixel16BitGrayFromRawImage(RawImage, RawImageSize, DTid.xy);
    int  Mean   = (int)round(DataOutBuffer[0].GrayAutoResultMean);
    uint UValue = (Mean - Value) * (Mean - Value);
    LockAcquire();
    DataOutBuffer[0].GrayAutoResultSumSqr += UValue;
    LockRelease();
}

使用的数据：

cbuffer TImageParams : register(b0)
{
    int2   RawImageSize;       // Actual image size in RawImage
}

struct TDataOutBuffer
{
    uint   Lock;                             // Use for SpinLock
    double GrayAutoResultMean;
    double GrayAutoResultSumSqr;
};

ByteAddressBuffer                  RawImage       : register(t0);
RWStructuredBuffer<TDataOutBuffer> DataOutBuffer  : register(u4);

调度代码：

FImmediateContext->CSSetShader(FComputeShaderGrayAutoComputeSumSqr, NULL, 0);
FImmediateContext->Dispatch(FImageParams.RawImageSize.X, FImageParams.RawImageSize.Y, 1);

GetPixel16BitGrayFromRawImage函数访问RawImage字节地址缓冲区，从灰度图像中获取16位像素值。它会产生预期的结果。

非常感谢任何帮助。

- fpiette

---

你尝试过在这行代码上方加锁吗：int Mean = (int)round(DataOutBuffer[0].GrayAutoResultMean); 或者是在 int Value = GetPixel16BitGrayFromRawImage(RawImage, RawImageSize, DTid.xy); 上方加锁呢？ - VuVirt

不，我没有尝试过，因为这是无意义的。无论如何，我现在刚刚尝试了一下，但这并没有改变。另外，GetPixel16BitGrayFromRawImage是线程安全的，因为它只访问只读数据，并且已经被证明在许多其他多线程地方中我都大量使用它。 - fpiette

Answer 1

你遇到了XY问题。

让我们从Y问题开始。 你的自旋锁无法锁定。为了理解为什么你的自旋锁无法工作，你需要检查GPU如何处理你正在创建的情况。你发出一个由一个或多个线程组成的warp，每个线程又由许多线程组成。只要执行是并行的，warp的执行就很快，这意味着所有形成warp（如果您愿意，也可以称为wavefront）的线程必须同时执行相同的指令。每次插入条件（例如while循环），一些线程必须采取一条路线，其他线程必须采取另一条路线，这就是线程的分歧。问题在于您不能并行地执行不同的指令。

在这种情况下，GPU可以采取以下两种路线之一：

1. 动态分支，这意味着wavefront（即warp）采取2条路线之一，并停用应该采取另一条路线的线程。然后，它回滚以在它们离开时拾取睡眠的线程。
2. 平面分支，这意味着所有线程都执行两个分支，然后每个线程丢弃不需要的结果并保留正确的结果。

现在有趣的部分：

没有转换规则说明GPU应该如何处理分支。

你无法预测GPU是否会使用一种方法或另一种方法，在动态分支的情况下，你无法事先知道GPU是否会将直线路由、其他路由、具有较少线程的分支或具有更多线程的分支置于睡眠状态。你没有办法事先知道，并且不同的GPU可能以不同的方式执行代码（并且会）。甚至同一GPU在不同的驱动程序版本下甚至可能改变其执行。

在自旋锁的情况下，你的GPU（及其驱动程序和当前使用的编译器版本）最可能采用平面分支策略。这意味着所有warp的所有线程都执行两个分支，因此基本上根本没有锁。

如果您更改代码（或在循环之前添加[branch]属性），则可以强制进行动态分支流，但这并不能解决您的问题。对于自旋锁的特殊情况，您要求GPU关闭除一个线程外的所有线程。这不是GPU想做的事情。GPU将尝试相反地关闭唯一评估条件不同的线程。这确实会导致更少的分歧并增加性能...但在您的情况下，它将关闭唯一一个不在无限循环中的线程。因此，您可能会得到一个完整的波前线程被锁定在无限循环中，因为唯一一个可能解锁循环的线程正在休眠。您的自旋锁已经变成了死锁。

现在，在您的特定计算机上，程序甚至可能运行良好。但您没有任何保证该程序将在其他计算机上运行，甚至使用不同的驱动程序版本也是如此。您更新驱动程序，程序突然遇到GPU超时并崩溃。

关于GPU中的自旋锁的最佳建议是...永远不要使用它们。

现在让我们回到您的Y问题。

您真正需要的是一种计算大型二维数组中数据总和的方法。因此，您真正寻找的是一个好的约减算法。有一些可以在互联网上找到，或者根据您的需要编写自己的算法。

如果需要，我将添加一些链接以供参考。 关于分歧的离题讨论 NVIDIA - GPU技术大会2010演示文稿 Goddeke - 入门教程 Donovan - GPU并行扫描 Barlas - 多核和GPU编程

- kefren

---

哇哦！我觉得在继续之前还需要学习很多。感谢你的帮助。感谢提供参考资料。 - fpiette

如果我可以给你一个未被询问的建议 ;) 我看到你总是使用单个线程[numthreads(1, 1, 1)]来分派线程组。这非常低效。一个好的起点可能是使用64、128或256个线程的线程组。然后你可以进一步优化。 - kefren

谢谢你的建议。我会提出一个新问题，以便我们可以适当地讨论这个话题。 - fpiette

我采纳了你的建议：现在我每个组使用大量线程，性能提高了一个数量级。感谢你的提示。 - fpiette

我会尽快回答，但这不是一个简单的问题，所以我需要一些时间来给出一个好的答案。顺便说一下，如果这些答案对您有帮助，请考虑接受它们，如果您认为它们令人满意的话。 - kefren

Answer 2

如 kefren 所述，您的自旋锁由于warp分歧而无法工作。但是有一种设计GPU自旋锁的方法可以避免死锁。我在像素着色器中使用了这个自旋锁，但它也应该适用于计算着色器。

RWTexture2D<uint> mutex; // all values are 0 in the beginning

void doCriticalPart(int2 coord) {
   bool keepWaiting = true;
   while(keepWaiting) {
      uint originalValue;
      // try to set the mutex to 1
      InterlockedCompareExchange(mutex[coord], 0, 1, originalValue);
      if(originalValue == 0) { // nothing was locked (previous entry was 0)
         // do your stuff
         // unlock mutex again
         InterlockedExchange(mutex[coord], 0, originalValue);
         // exit loop
         keepWaiting = false;
      }
   }
}

在我的学士论文第30页上有关于为何此方法有效的详细解释。还有一个GLSL示例。

注意：如果您想在像素着色器中使用此自旋锁，请在调用此函数之前检查SV_SampleIndex == 0。像素着色器可能会生成一些辅助调用以确定纹理提取mipmap级别，这会导致原子操作出现未定义行为。对于那些辅助调用，这可能会导致循环的无限执行，从而导致死锁。

- Felix Brüll

---

你的实现和我的并没有真正的不同，除了你将代码写成了内联形式，而我使用了函数。由于HLSL编译器会将所有函数都转换为内联形式，所以这两种方式几乎是相同的。 - fpiette

区别在于我的实现中while循环围绕着LockAcquire和LockRelease。而你的while循环只围绕LockAcquire，这可能会导致死锁，因为所有线程组中的线程都只作为一组（锁步进），如果你的实现中有一个线程没有获取到锁，那么所有其他线程都不会前进，也就无法释放它们的锁。 - Felix Brüll

fpiette的实现在他的硬件上没有导致死锁。但在某些硬件上可能会出现这种情况。在他的硬件上，问题是所有线程都执行了两个分支，这导致根本没有锁定。在您的实现中也可能发生同样的情况，而且它能够在您特定的硬件/驱动程序对上工作，不能保证在其他硬件或不同驱动程序版本上工作。您可以获得在PC上工作的自旋锁。但您无法在GPU上获得可靠地在每个硬件修订版或所有驱动程序版本上工作的自旋锁。 - kefren

如果我在if语句之前添加[branch]标签会发生什么？那么内部只有在实际获取锁时才会执行。或者我漏掉了什么吗？ - Felix Brüll

你的互斥锁出现问题了，因为无法保证以下情况不会发生：

1. 线程A获取锁
2. Warp一直执行“无法获取锁”分支，计划在此之后执行A（但这永远不会发生）
3. 线程A永远不会恢复执行，因此也永远不会释放互斥锁。

- Matias N Goldberg