Gang Scheduling Performance Benefits for Fine-Grain Synchronization

Gang Scheduling Performance Benefits for Fine-Grain Synchronization

题目

• 什么是 gang secheduling ？ 组调度，要么一组全部执行，要么都不执行
• 什么是 fine-grain 同步 ？细粒度同步 CSDN 博客

摘要

• gang scheduling, where a set of threads are scheduled to execute simultaneously on a set of processors. gang scheduling 一组线程同时在一组处理器上执行的调度
• It allows the threads to interact efficiently by using busy waiting, without the risk of waiting for a thread that currently is not running 使用忙等来高效地互动。
• 否则使用 block 来达到同步地目的会造成上下文切换，造成很大的开销。
• have developed a model to evaluate the performance of different combi
  nations of synchronization mechanisms and scheduling policies 建立模型来评估同步机制和调度策略的组合
• gang schedule 在细粒度同步地要求下更高效

INTRODUCTION

• 随着“虚拟处理器”，多程序多处理器的发展， 程序执行过程中不可见，只能由系统软件管理 mapping 和 scheduling
• 并行应用的线程互动，体现在线程的同步上。
• explicit synchronization 显示同步 barrier 同步 互斥同步
• implicit synchronization 隐式同步，数据存在生产者和消费者关系等。
• In the case of fine-grain interactions it is shown that it is best for the threads to execute simultaneously on distinct processors，and to coordinate their activities with busy waiting.
  在细粒度的互动中，线程最好在不同的处理器上同时执行，通过忙等来进行协调
• 在粗粒度的同步中，如果执行时间的方差很大，最好是通过阻塞的方式进行同步。这样就可以将处理器让出来，将给其他线程执行。

Related work

这篇文章是第一个分析 gang scheduling 的性能，以及同步和调度之间相互作用的。

• This allows us to identify the situations in which gang scheduling
  should be used, namely when the application is based on fine-grain synchronization. 这也使我们能去确定，使用gang scheduling 的情况。

• It is also the first to report
  experiments based on a real implementation of gang scheduling on a multiprocessor. 他也是第一个真正基于多处理器上的组调度的实际实现的实验。

• Gang scheduling may cause an effect reminiscent of fragmentation, if the gang sizes do not fit the number of available processors. 如果组的大小和处理器数量不匹配，gang scheduling 将会产生 碎片效果

• In this paper we
  show that for fine-grain computations gang scheduling
  can more than double the processing capability. 在细粒度计算中，gang scheduling 可以将处理器的能力提高一倍以上。

• gang scheduling 指的就是将一组线程采用一对一的映射同时调度到一组处理器上。

Question: 关于同步过程的细节问题，解决了这个问题，后面很多问题估计也就解决了。
假设 1: 在进行同步的时候，必须要所有参与同步的线程同时在执行吗？也就是说，所有的线程都同时在处理器上执行，这样他们之间才能完成交互。
假设 2: 在进行同步的时候，不需要所有的线程都同时在处理器上执行。当执行同步的操作的时候，线程只需要将消息传输到一个消息队列、或者类似于公共内存的地方。基于这样的假设，考虑当使用blocking 和 uncoordinated scheduling 当最后一个线程完成计算部分，可以执行同步任务。然后同步结束，可以直接执行下一轮。对于其他线程，当重新唤醒时，完成未完成的同步任务，继续向下执行下一轮任务。

2 Synchronization And Scheduling

• busy waiting ：忙等的性能非常依赖于系统的调度策略

• blocking

• Two-phase ：两阶段阻塞，第一阶段使用一段时间的忙等，然后使用阻塞。当和gang scheduling在细粒度的情况下使用，基本上只用到了第一阶段的 忙等。使用其他调度，基本上是blocking，并且还比blocking的开销更大。

• gang scheduling： 所用互动的线程同时运行，但是一组的线程数存在限制。

• uncoordinated scheduling：各个处理器上的线程单独调度。

gang scheduling 和 blocking 结合是没有意义的，因为blocking的线程就算切换上下文，让出了处理器，处理器还是不能切换给别的gang的线程。
所以有三种组合：

• busy waitng with gang scheduling
• busy waiting with uncoordinated scheduling
• blocking with uncoordinated scheduling

2.1 Model and Assumptions

• 线程执行迭代计算
• 每个迭代中执行 $t_p^{ij} $ 时间的计算，然后执行同步操作
• 在执行同步的时候，他也会xiao’hao’yi，由于每个线程都需要执行，直接将这一部分的开销计入 $t_p^{ij} $
• 每个线程，在执行一次迭代的时候，会有一个处理时间，和一个等待时间

平均等待时间
$$t_p=\frac{1}{nk}\sum _{i=1}^n\sum _{j=1}^k{t}_p^{ij}$$

$$t_p^{maxj}=ma{x}_{1\le i\le n}{t}_p^{ij}$$

迭代 j 的线程 i 的等待时间为

$$t_w^{ij}=t_p^{max,j}-t_p^{ij}$$

平均等待时间
$$t_w=\frac{1}{nk}\sum _{i=1}^n\sum _{j=1}^k{t}_w^{ij}$$

note:$t_p+t_w=(\frac{1}{k}){\sum }_{j=1}^k{t}_p^{maxj}$

由于同步的开销可能和处理器的数量相关，因此$t_p$ 的值还需要调整。

System Characterization

在多道程序多处理器的情况下，每个处理都映射了多个线程。并且，采用时分策略，为所有的线程提供相同的服务时间。
Assumptiong：

• the number of threads on each processor is denoted by l
• 我们只关注 a single gang of n threads ,mapped to n different processors,剩余的 n(l-1)个线程运行好坏不是我们关心的

对于blocking 策略，性能好坏，和其他gang 的线程行为有很大关系。因为blocking 策略有利他性：

1. 所有的线程的行为都相同，都执行迭代操作
2. 剩余的 l-1 组线程是独立调度的，纯计算的线程

调度时间片记为 ${\tau }_q$
上下文切换的开销记为 ${\tau }_{c}s$
blocking 的开销记为 $\alpha$ 倍的上下文开销， $\alpha$ 一定是大于1的

在粗粒度的情况下：
$t_p$ 相对于 ${\tau }_q$可能会大的多，在执行同步步骤之前可能会执行许多个时间片

在细粒度的条件下：
$t_p$ 相对于 ${\tau }_q$可能小的多，假设${\tau }_q$的可能会执行 $10^4-10^5$ 个指令，每10-100个个指令执行一次交互。

$$k(t_p+t_w)\gg {\tau }_q$$
在细粒度情况下，k 要足够大

2.2 Performance Dervition

Busy Waiting with Gang Scheduling

执行k次迭代的时间为：

$$T=(k(t_p+t_w)+\frac{k(t_p+t_w)}{{\tau }_q}{\tau }_{cs})l$$
乘 l 是因为，要考虑到每个processor 映射了 l个线程，并且采用了时分策略，需要为其他线程提供相同时长的服务。

平均每次迭代所需要的时间为：
$$t=(1+\frac{{\tau }_{cs}}{{\tau }_q})(t_q+t_w)l$$

因为 $t_p+t_w=(\frac{1}{k}){\sum }_{j=1}^k{t}_p^{maxj}$ ，所以执行速率取决于执行最慢的线程。

Busy Waiting with Uncoordinated Scheduling

使用忙等和非协调调度的行为表现和粒度是相关的。

粗粒度的情况下：
在粗粒度的情况下，Busy Waiting with Uncoordinated Scheduling与 gang scheduling 的行为几乎一样。
由于同一组的线程不必同时执行，会导致 $t_p+t_w$ 远远大于 ${\tau }_q$ ，每次迭代都会需要若干个调度。
计算 t 和之前的情况是一样的：
$$t=(1+\frac{{\tau }_{cs}}{{\tau }_q})(t_q+t_w)l$$

Question：也是要等到所有线程同时调度时，才能完成同步操作的吧？ 所以 $t_w$ 的计算方式和之前不同？

在细粒度的情况下：
首先明确，在不加干预的情况下，也有一定概率，使得 n 个线程同时调度。当这种情况发生的时候，会完成很多轮的迭代。

当循环周期为 $\Lambda$时， n 段 长度为 $\lambda$ 的重叠为 $\frac{{\lambda }^n}{{\Lambda }^{n-1}}$

在细粒度的情况下 ：

• $\lambda {\tau }_q$
• $\Lambda =l({\tau }_q+{\tau }_{cs})$ 是一个调度周期
• 每个调度周期线程重叠时间为 $\frac{{\tau }_q^n}{l^{n-1}({\tau }_q+{\tau }_{cs}{)}^{n-1}}$
• 每个调度周期完成的迭代数为：$\frac{{\tau }_q^n}{l^{n-1}({\tau }_q+{\tau }_{cs}{)}^{n-1}(t_q+t_w)}$

执行 k 次迭代所需要的调度轮数 $m =\frac{kl^{n-1}(\tau_q + \tau_{cs})^{n-1}(t_q + t_w)}{\tau_q^n} $

总的执行时间为：

平均每一次迭代的时间为：

如果假设 ${\tau }_q\gg {\tau }_{cs}$,那么使用 uncoordinated 调度比 gang 调度慢 $l^{n-1}$倍

事实上，应满足每个调度周期至少完成一轮迭代。
$t=min(Eq.(8),({\tau }_q+{\tau }_{cs})l)$

Question: 为什么每个调度周期至少完成一轮迭代？他说这是个假设？没解释

Blocking Mechanism

Blocking 可以将CPU空出来，所以存在一种利他性。
考虑两种情况：

1. 所有的线程的行为相同，都会进行迭代的计算和同步，并且在wait时block
2. 竞争的线程是独立调度的，纯计算的，所以从来不会阻塞

所有线程行为相同、粗粒度
由于是独立调度的，在任何时刻只有 $\frac{t_p}{t_p+t_w}$ 个线程是活跃的。
由于粗粒度的情况下，大部分的上下文切换都是因为时间片到期，而不是因为blocking。所以 blocking 带来的额外开销可以忽略不计。

所以运行的总时间是：

其实相当于是，省掉了等待的时间
每个迭代所需要的时间为：

其他线程行为不同、粗粒度

在任何时刻，活跃的进程数基本上还是l个

所有线程行为相同、细粒度

线程会频繁地被阻塞，实际上的调度时间片会减少。
如果是最后一个线程，不需要阻塞就可以直接进入下一轮迭代。所n个线程中，只有 n-1 个线程会被阻塞。
blocking 的开销是 $\alpha$倍的线程上下文切换。

所以运行k个迭代的时间是

每轮迭代需要的时间为

相比于busy wait：

• 粗粒度情况下，每轮迭代时间减少
• 细粒度条件下，每轮迭代时间增加

其他线程行为不同、细粒度

在每个调度周期，只能迭代一轮，就结束了，其他的进程依旧能执行 ${\tau }_q$的时间片，这里就充分体现了利他性的特点

这时候，RR的轮转对于被阻塞的进程来说就不是公平的了。

3 Implementation And Experiments

Experimental Results

程序生乘若干组，每一组在每个处理器器上，只有一个线程。

• LOAD :参与竞争的组数
• GRAIN: 粒度，每个迭代中除同步过程外的，其他的指令数。如果有多种粒度，取最小。
• VAR ：各个迭代中不同活动的最大和最小指令数之差。实验中的活动的指令数，服从 GRAIN 到 GRAIN+VAR的均匀分布：最长活动为 GRAIN+(n/(n+1))VAR ,最短活动为GRAIN+(1/(n+1))VAR

在实验中，GRAIN每个unit耗时 0.00141ms， 互动时间为 0.137ms

t_w 是根据

迭代数量在多数实验中为 30000 或 50000

为了保证在不协调的情况下启动，还在开始时加入了启动辅助线程。

实验1

该实验显示了阻塞引起的附加开销，
并且当负载为1时，阻塞不能实现任何增益

实验2

LOAD =3
显示了 busy waiting with gang scheduling 和 blocking with
uncoordinated scheduling 的性能。

在最小粒度的时候，gang scheduling 可以达到阻塞性能得到两倍。

实验3

实验三显示了blocking 机制的利他性

一组实验是所有线程的行为相同。
另一组实验是只有一组线程会进行阻塞。

实验4

这个实验表明，没有gang调度的忙碌等待确实不是可行的选择

4 总结与讨论

1. busy waiting with gang scheduling 对于细粒度的job，效果最好
2. blocking 会释放系统资源，对于粗粒度的job 会减少运行时间。但是对于细粒度的job，会怎个加运行hi见。 如果 竞争的先尝不阻塞，会将低阻塞线程的执行效率（利他性）
3. busy waiting with uncoordinated 调度是比较浪费资源的，尤其是在细粒度的job上。在粗粒度的job上，忙等的小号是非常大的。
4. 两阶段阻塞，会限制浪费，但是不会提升性能，除非与 gang scheduling结合使用。

什么时候使用 busy waiting with gang scheduling

busy waiting with gang scheduling 每次迭代的执行时间记为 $t_{BW}$

使用bloking 每次迭代的执行时间记为 $t_{BLK}$

当然这里假设所有线程都有相同的behavior

当在什么条件下 $\frac{t_{WB}}{t_{BLK}}\le \sigma <1$

带入上面的式子

在灰色的区域，可以说 BW 比BLK 块了至少 $\frac{1}{\sigma }$ 倍

同样如果满足 $\frac{t_{BLK}}{t_{BW}}\le \sigma <1$ ，blocking 是占优的。

当所有的线程行为不相同的时候，应该采取 Eq(13) 作为 $t_{BLK}$

因此，带入可以的得到

此外，busy waiting更好的有利于使用chache，因为blocking 造成的频繁的上下文切换降低了cache的有效性。

不仅如此，也需要硬件支持，如锅交互时间太长，也会很容易使得其超出细粒度的时间边界。