同步屏障

在并行计算中，屏障是一种同步方法。 源代码中一组线程或进程的屏障意味着任何线程/进程都必须在此时停止，并且在所有其他线程/进程到达此屏障之前无法继续。

许多集体例程和基于指令的并行语言强加了隐含的障碍。 例如，在最后一次迭代完成之前，不允许在任何线程上继续使用带有 OpenMP 的 Fortran 中的并行 do 循环。 这是为了防止程序在完成后立即依赖循环的结果。 在消息传递中，任何全局通信（例如减少或分散）都可能意味着障碍。

在并发计算中，屏障可能处于升高或降低的状态。 术语闩锁有时用于指代从升起状态开始并且一旦处于降低状态就无法重新升起的屏障。 术语倒计时锁存器有时用于指代一旦预定数量的线程/进程到达后自动降低的锁存器。

基本barrier主要有两个变量，一个记录barrier的pass/stop状态，另一个保存进入barrier的线程总数。 屏障状态被初始化为由xxx个进入屏障的线程停止。 每当有线程进入时，根据已经进入屏障的线程数，只有是最后一个线程，线程才将屏障状态设置为pass，这样所有的线程才能脱离屏障。 另一方面，当传入的线程不是最后一个时，它会被困在屏障中，并不断测试屏障状态是否从停止变为通过，直到屏障状态变为通过时才退出。 以下 C++ 代码演示了此过程。

struct barrier_type{ // 有多少处理器进入屏障 // 初始化为 0 int arrive_counter; // 有多少处理器已经退出屏障 // 初始化为 p int leave_counter; 内部标志； std::mutex lock;};// p 处理器的屏障void barrier(barrier_type* b, int p){ b->lock.lock(); if (b->arrive_counter == 0) { b->lock.unlock(); while (b->leave_counter != p); // 在清除之前等待所有人离开 b->lock.lock(); b->标志=0； // 先到者清除标志 } b->arrive_counter++; if (b->arrive_counter == p) // 最后到达者设置标志 { b->arrive_counter = 0; b->leave_counter = 0; b->标志=1； } b->lock.unlock(); while (b->flag == 0); // 等待标志 b->lock.lock(); b->离开计数器++； b->lock.unlock();}

潜在的问题是：

• 由于所有线程重复访问全局变量pass/stop，通信量较大，降低了可扩展性。

这个问题可以通过重新组合线程和使用多级屏障来解决，例如 结合树屏障。 硬件实现也可能具有更高可扩展性的优势。

顺序障碍不是使用相同的值来表示通过/停止，而是使用相反的值来表示通过/停止状态。 例如，如果屏障 1 使用 0 停止线程，屏障 2 将使用 1 停止线程，屏障 3 将再次使用 0 停止线程，依此类推。 下面的 C 代码演示了这一点。

struct barrier_type{ int counter; // 初始化为 0 int flag; // 初始化为 0 std::mutex lock;};int local_sense = 0; // 每个处理器私有 // p 个处理器的屏障void barrier(barrier_type* b, int p){ local_sense = 1 – local_sense; b->lock.lock(); b->计数器++； int 到达 = b-> 计数器； if (arrived == p) // 最后到达者设置标志 { b->lock.unlock(); b->计数器=0； // 内存栅栏以确保在更改标志 b->flag = local_sense 之前看到对计数器的更改 // } else { b->lock.unlock(); while (b->flag != local_sense); // 等待标志 }}

组合树屏障是一种实现屏障的分层方法，通过避免所有线程都在同一位置旋转的情况来解决可伸缩性问题。

在 k-Tree Barrier 中，所有线程均等分为 k 个线程的子组，并且在这些子组内完成xxx轮同步。 一旦所有子组都完成了同步，每个子组中的xxx个线程进入第二级进一步同步。 在第二层，与xxx层一样，线程形成新的 k 线程子组并在组内同步，将每个子组中的一个线程发送到下一层，依此类推。 最终，在最后一层只有一个子组需要同步。 末级同步后，释放信号向上层传递，所有线程通过屏障。

硬件屏障使用硬件来实现上述基本屏障模型。