user avatar
Update scheduler
Nemo authored
da24df27

哈尔滨工业大学 (深圳) Proj-317 高效用户态线程调度 项目文档

hitsz

队伍: 叉子联合平行线 (Fork, Join, Parallel)

队员: 黄俊杰 羊柯伍 陈希峻

校内导师: 夏文, 李诗逸

校外导师: 任玉鑫, 吴一凡

详细文档: IOPM System 开发设计文档
本文件仅简单介绍本项目内容

项目内容

根据大赛赛题仓库中的指导, 本赛题由三个子赛题组成:

  • 基本的环境搭建和熟悉

    • 熟悉现有工具的使用
    • 理解parallel loop、simd等数据并行,以及调度相关的背景知识
  • 高效调度策略

    • 洞察前沿论文,分析其冷热识别的核心算法
    • 支持混合应用,支持多种策略,实现不同场景的需求
  • 内核与用户态协同调度

    • 分析由于不感知用户态的调度策略,内核的调度如何影响应用性能
    • 改进内核里的调度策略,与用户态的调度协同感知,提升性能

初赛完成的内容有:

向 LLVM OpenMP 中添加了5种调度策略,丰富了 OpenMP 对各种负载的适应程度
初步优化了 LLVM OpenMP 中的工作窃取(Work Stealing)策略
初步实现了 CRSS 调度器
完成了内核相关的调研\

本项目从赛题以及实际项目分析出发, 从以下角度完成了赛题的任务

  • 通过丰富OpenMP的调度分发算法以对于不同的负载提供更多的调度策略,以实现更优的性能
  • 通过实现更优的工作窃取(Work Stealing)算法,提高了负载均衡表现,实现了更优的性能
  • 通过实现一个OpenMP的调度分发器,通过合理分配系统计算资源,提高计算资源利用率,实现更优的性能

项目完成情况

分发策略

项目参考论文,实现了Factoring以及Adaptive Weighted Factoring的4种变体的分发策略,使得OpenMP能更好的适应多种工作负载。

Factoring (FAC) 分发策略简介

Factoring分发策略尝试一种介于静态均衡分配和动态分配 (Chunksize=1) 之间的策略,先以较大的chunk进行分发,随着分发的进行,逐渐缩小chunk的大小,从而实现较低的分发开销的同时尽量实现负载均衡,其详细策略描述算法如下:

\begin{align}
R_0&=N\\
R_{j+1}&=R_j-PF_j \\
F_j&=\frac{R_j}{x_jP} \\
b_j&=\frac{P}{2\sqrt{R_j}}\frac{\sigma}{\mu} \\
x_0&=1+{b_0}^2+b_0\sqrt{{b_0}^2+2} \\
x_j&=2+{b_j}^2+b_j\sqrt{{b_j}^2+4} \\
\end{align}

其中, P 为处理器核心数量, R_i 为第 i 此分配时循环体中所剩余的循环数, F_i 为第 i 此分配时的 Chunksize

Adaptive Weighted Factoring (AWF) 分发策略简介

Adaptive Weighted Factoring算法的设计思路是解决在异构环境下科学应用程序性能问题入手的。其从加权分块算法演化而来的,在每次迭代后动态调整处理器的权重,不仅基于上一次迭代的性能,还考虑了之前所有迭代的累积性能。 以下为其详细策略描述算法:

\begin{align}
&R_0=N  \\
&R_{j+1}=R_i-\sum_{j=1}^{P}K_{ij}  \\
&K_{i+1}=\frac{R_{i+1}}{2}\frac{WP_i}{P}  \\
&WP_j=\frac{RPW_jP}{TRW}  \\
&RWP_j=\frac{AWAP}{WAP_j}  \\
&AWAP=\frac{\sum_{j=1}^{P}{WAP_j}}{P}  \\
&WAP_j=\frac{\sum_{i=1}^{m}T_{ij}i}{\sum_{i=1}^{m}K_{ij}i}
\end{align}

其中, P 为处理器核心数目, R_i 为第 i 此分配时剩余的循环数, K_i 为第 i 此分配时的 Chunksize T_{ij} 是处理器核心 j 完成工作负载 i 的时间,不计分发开销。

工作窃取 (Work Stealing)

通过对LLVM OpenMP源码的仔细阅读,修改了LLVM OpenMP中的工作窃取策略,希望实现更优的负载均衡效果。

LLVM OpenMP实现中, 每个线程具有UNUSED, CLAIMED, READY以及THIEF 4种标记,每个线程通过维护自身的标记来向其他线程表示自身工作负载的状态。当一个线程的工作负载被完全处理完成时,其将成为THIEF状态并尝试窃取其他线程的工作负载。其Victim选择逻辑是:从线程ID为自身线程ID+1的线程开始尝试窃取,如果窃取失败,则继续尝试窃取线程ID+1的线程的工作负载,最多尝试nproc次。如果其中尝试窃取成功,则将被窃取线程的工作负载的剩余部分的1/4窃取至本线程中,并进行处理。同时取消THIEF标记并且允许其他线程窃取本线程的工作负载。

以上窃取逻辑几乎完全不感知其他线程的所剩余的工作负载的强度,仅仅通过逐个尝试的方式,可能会导致某个剩余负载较多的线程没有及时的被窃取足量的负载,同时也可能造成部分线程过度窃取的问题,不能非常完善的均衡负载。

为了尝试解决上述问题,我们提出了一种 Best Victim Work Stealing 的算法,在测试负载上实现了相比 LLVM OpenMP 约 9.55\% 的提升

img img

计算资源调度系统 调度分发器 (CRSS, Computation Resource Schedule System)

初赛工作

通过对OpenMP应用性能的测试,本项目初步实现了一个系统CPU计算资源监视脚本CRSS (Computation Resource Scheduling System, for now only a script),并取得了一定性能上的优化。

img

决赛工作

我们通过构建一个调度分发器,在64核心模拟测试平台上对测试负载进行测试,获得极大的性能提升。

img

由上图可见,经过调度分发器调度后 OpenMP 应用性能相比 LLVM OpenMP 有成倍增加,这主要由以下两个原因构成:

  1. 测试用例对于负载均衡的要求较高,对负载不均衡较为敏感
  2. CRSS 调度分发器避免将高负载核心分配至 OpenMP 应用,极大的避免了负载不均衡的发生

详细的介绍将位于 IOMP System 开发设计文档

决赛第二阶段预期目标

  1. 在现有的基础上,进一步提高工作窃取(Work Stealing)算法的性能,进一步提高负载均衡表现

  2. 在现有的调度分发器上,添加更多的功能,使其能够作为系统常驻服务,为多个 OpenMP 应用提供计算资源调度服务,加入更多的参数,使其能够更好的适应不同的部署需求

构建项目

详细构建方式请见LLVM 文档

总结

对于以上任意一点的详细介绍将位于 IOMP System 开发设计文档 中.