BWoS Work-Stealing Queue简介

华为研究院在OSDI23会议上发表了一篇名为BWoS: Formally Verified Block-based Work Stealing for Parallel Processing的论文，介绍了一种叫做BWoS的Work-Stealing Queue，能够极大地减小Work-Stealing带来的额外开销，本文会简要介绍BWoS的设计思想。

本文大部分都翻译自BWoS论文原文。如果对细节感兴趣，可以前往OSDI Open Access阅读原论文。

影响Work-Stealing Queue性能的主要因素

#

并行处理在计算机的各种领域都有十分广泛的应用。比如在Web开发中，Golang goroutine和Rust coroutine都是十分轻量的对象，现有的Work-Stealing Queue对于轻量级对象会有很大的额外开销。除此之外，像Java G1GC算法的并行化也十分依赖Work-Stealing Queue，Work-Stealing Queue在其并行化中也占有很大一部分额外开销。

现有的Work-Stealing Queue的性能问题主要由四个方面导致：

同步开销

#

由于Thief的存在，队列必须使用强同步原语（内存屏障）。FIFO Queue通常会实现为单生产者多消费者（Single-Producer Multiple-Consumer，SPMC）队列，此时Thief的行为与Owner的行为是类似的，因此Thief的操作与Owner的操作开销大致是相同的，这会带来大量不必要的额外性能开销。对于LIFO Queue来说，内存屏障通常也会占用很大的开销，比如ABP Queue。

由Thief导致的Cache Miss

#

Stealing会更新队列的Metadata，而队列的Metadata由Owner和Thief共享，这会导致Owner接下来访问队列发生Cache Miss。对于任务分配尤其不均衡的情况，这种Cache Miss发生得尤其频繁。Batching（批量处理）能够一定程度上减轻这种问题，但会导致偷取过多的任务，从而导致额外性能开销。

Victim选择算法

#

为了改善工作负载的分配，一些Victim选择策略需要扫描所有的队列，这会导致Thief与Owner发生访问冲突。

弱内存模型下的正确性

#

目前来看，在弱内存模型的CPU上要正确实现Work-Stealing Queue是很困难的，比如ARM处理器就需要额外的内存屏障来阻止一些乱序执行，这会严重影响性能。而如果不使用内存屏障，则会直接产生错误的结果。

BWoS Work-Stealing Queue的设计

#

BWoS将队列拆分成多个Block，每个Block针对Owner和Thief都存储不同的Metadata，因此即使Owner和Thief在同一个Block中工作，也能尽可能避免同步。

由于每个Block存储有自己的Metadata，因此只要令Owner和Thief在不同的Block上工作即可有效避免同步开销。FIFO BWoS Queue允许Thief从Block的中间开始Stealing操作，而不像单生产者多消费者队列那样必须Steal最老的任务。

BWoS精心设计了算法以使Thief无法影响Owner的get操作，但Owner的get操作可以安全地Takeover Thief的Block，从而使Owner无需等待Thief操作结束，实现了一定程度上的Wait-Free。

接下来，让我们考虑BWoS Queue的get、put和steal方法的实现，下面是三个方法的伪代码：

template <typename Element>
std::optional<Element> BWoS<Element>::get() {
    Element e;
    Block *block = this->blockToGet();
    while (true) {
        // Try to get from owner get block.
        Block::Status result = block->get(&e);
        // Get successfully.
        if (result == Block::Status::Success)
            return e;
        // The whole queue is empty.
        if (result == Block::Status::Empty)
            return std::nullopt;
        // Current block is empty. Find next block to get.
        if (result == Block::Status::Done) {
            auto rnd = someRandomNumber();
            if (!this->advanceGetBlock(&block, rnd)) // Update block.
                return std::nullopt;
        }
    }
}

template <typename Element>
bool BWoS<Element>::put(Element e) {
    Block *block = this->blockToPut();
    while (true) {
        // Try to put into current owner put block.
        Block::Status result = block->put(e);
        // Put successfully.
        if (result == Block::Status::Success)
            return true;
        // This block is full. Find next block to put.
        auto rnd = someRandomNumber();
        if (!this->advancePutBlock(&block, rnd)) // Update block.
            return false;
    }
}

template <typename Element>
std::optional<Element> BWoS<Element>::steal() {
    Element e;
    Block *block = this->blockToSteal();
    while (true) {
        Block::Status result = block->steal(&e);
        // Steal successfully.
        if (result == Block::Status::Success)
            return e;
        // The whole queue is empty.
        if (result == Block::Status::Empty)
            return std::nullopt;
        // Conflict stealing element with other thieves.
        if (result == Block::Status::Conflict)
            continue;
        // This block is empty. Find next block to steal.
        if (result == Block::Status::Done) {
            auto rnd = someRandomNumber();
            if (!this->advanceStealBlock(&block, rnd)) // Update block.
                return std::nullopt;
        }
    }
}

至于get、put和steal的伪代码，原论文给出的伪代码偏向于一种融合语言风格，此处我改成了C++风格，相信具有一定C++或其他面向对象语言基础的读者配合注释应当不难看懂上面的伪代码，此处不再赘述。

在介绍三种advanceBlock算法之前，我们需要先介绍两个概念：Block-level同步、Round Control。

Block-level同步

#

Block-level同步保证了Thief永远不会从Owner正在执行get的Block上Steal。每个Block要么由Owner占用，要么被Thief占用。Owner可以将一个Block 赋予（grant） Thief（允许该Block上的Stealing操作），也可以从Thief处 收回（take over） 一个Block（在advanceGetBlock里）。

赋予和收回操作都基于Thief Index进行操作。Thief Index指的是在当前Block中Thief的偷取位置。收回操作会直接将Thief Index置为Block Size从而阻止Thief与Owner同时在当前Block中进行操作，同时也保证了Thief无法阻塞Owner的get操作，如下所示：

template <typename Element>
bool BWoS<Element>::Block::takeOver() {
    // Marks that thieves can no longer steal from this block.
    auto oldStealIndex = this->stealIndex.exchange(BLOCK_SIZE, std::memory_order_relaxed);
    // This block has already been taken over.
    if (oldStealIndex == BLOCK_SIZE)
        return false;
    // Update metadata for owner.
    ...
    return true;
}

赋予操作与收回操作类似，只需要更新Steal Index为队首即可表示本Block可被偷取，如下所示：

template <typename Element>
void BWoS<Element>::Block::grant() {
    // Update owner top (for LIFO BWoS queue) to BLOCK_SIZE so that owner no longer push objects into this block.
    auto newThiefIndex = this->ownerTop.exchange(BLOCK_SIZE, std::memory_order_relaxed);
    // Update steal index to tell thieves that this block is available for stealing.
    this->thiefIndex.store(newThiefIndex, std::memory_order_relaxed);
}

Round Control

#

每个Block均要记录最后一次访问的轮数（Round Numbers），当执行advanceBlock方法时，当前Block的轮数会被带到下一个Block。如果循环完了一轮，此时所有Block的轮数均相等，则给轮数加一（借助atomic_compare_exchange实现）。在更新轮数时，可能当前Block上一轮的数据还没有被读取完（不论是get还是steal），此时必须等待当前Block上一轮的数据全部读取完才能更新轮数。这保证了数据既不会被覆盖，也不会被重复读取。

Advance Block

#

三种advanceBlock算法本身只是根据各种情况调用上述方法好吧我承认是我懒得翻译了，所以请直接参考原论文4.2节吧。

基于概率的Steal策略

#

如上文所述，BWoS Queue的Metadata是分散存储的，这导致我们很难准确获取每个队列里具体存储着多少对象，不过BWoS给出了一种基于“队列有多满”的概率偷取策略。具体来说，Thief首先随机选择一个Victim Queue，假设Victim Queue中有$S$个对象，它的最大容量是$C$，那么Thief则以$\dfrac{S}{C}$的概率从该队列中偷取任务。如果决定不从该队列偷取任务，则重新选择Victim Queue进行上述过程。

不过正如上一段所述，我们很难准确获取每个队列里具体存储着多少对象，而且统计对象数量也会影响Owner的性能。因此，我们通过采样的方式直接估计$\dfrac{S}{C}$。具体来说，Thief会从所有的Block中随机选择一个Block，并检查该Block是否可被偷取。如果我们假设随机选择的Block可被偷取的概率等同于$\dfrac{S}{C}$，那么当随机选择的Block可被偷取时，则同样认为该Victim Queue可被偷取。

因为FIFO BWoS本来就不保证与SPMC队列行为相同，对于FIFO BWoS队列，通过上述采样方法选择Block后，如果可偷取，则可以直接从该Block开始偷取。如果当前Block已经为空，则结束本轮偷取，不进入下一个Block。

对于LIFO BWoS队列，我们需要从Bottom Block开始偷取。如果Bottom Block已经为空，则进入下一个Block偷取。

BWoS Work-Stealing Queue的实现

#

原论文的Chapter 4给出了十分详细的实现细节，所以就不再赘述了。如果想要找一份参考实现，NVIDIA stdexec实现了一个LIFO BWoS Queue，可以在GitHub找到这份代码。

需要注意的是，stdexec的实现没有直接通过轮数来防止重复写入（Block中是没有Round Number的），而是通过Owner和Thief的Block Index间接模拟了轮数。stdexec的实现假定put和get只能由Owner调用，因此重复写入只可能在put方法中发生。因此，当检测到重复写入时，Owner只需等待Thief线程将当前Block全部偷取完毕即可。由于LIFO Queue的get和put始终操作Top Block，只有Thief会操作Bottom Block，因此此实现能够防止重复写入。

stdexec在此处的实现十分巧妙。由于是LIFO Queue，因此当一个Block被偷取完毕时，它的Steal Index即为Block Size；而当Steal Index为Block Size时，也说明该Block已经由Owner收回。因此，只需要等待到Steal Index变为Block Size即相当于Owner完成了Block的收回，同时当前Block也可以由Owner写入了。

总结

#

BWoS Work-Stealing Queue提升性能的主要思路还是避免线程间的同步操作，主要思路是将队列切分为Block，并分散存储队列的Metadata以避免多个线程访问相同的Cache Line，其Victim选择算法也设计得十分巧妙。本文只是简单概括了BWoS的设计思想，想要具体了解BWoS设计与实现的具体细节，还请阅读BWoS论文原文。