一种面向多核平台的多线程划分及静态均衡调度策略

摘要

本发明涉及一种面向多核平台的多线程划分及静态均衡调度策略，提出用于评估分解出任务大小的粒度值参数概念，首先根据一定判断条件，判断一个任务是否真正适合多线程并行；其次采用静态调度策略，相比动态调度来说，没有在运行阶段的调度开销；最后，不同于一般的静态调度策略，本发明提出一种启发式静态调度策略，考虑了静态调度时当分解的任务大小差异很大时，会造成各个线程之间负载极不平衡的问题，通过获取的任务块的粒度值，可以将差异很大的任务块合理分配到不同线程上，达到负载均衡。

说明书

技术领域

本发明涉及一种面向多核平台的多线程划分及静态均衡调度策略，属于并行计算领 域。

背景技术

提高处理器性能一般取决于两个方面：一方面是处理器的体系结构的发展；另一个方 面是半导体工艺的不断进步。美国斯坦福大学提出片上多核处理器，为了提高处理器计算 能力，将多个内核集成到一个处理器芯片上，而最容易、最简单、最基本的一种实现方法 就是多核。早在上世纪末，IBM和惠普就已经提出双核处理器的可行性设计。2005年4月， intel全球同步首发基于多核技术桌面产品IntelPentiumD处理器，正式宣告x86处理 器多核心时代来临。

多核技术是在一个处理芯片上包含多个“执行内核”，使处理器能完全并行的执行程 序的多线程。如果从操作系统层面来看，多核就是指多个处理器，而每个处理器都独立拥 有全部的计算资源。

处理器架构从单核发展到多核架构的过程中，极大地提高了处理器的性能，同时也带 来了一些问题。如任务调度和负载均衡问题、节点间的通信、Cache一致性问题以及系统 异构性问题等。

其中解决负载均衡问题通常有两种方案，一种是静态调度，另外一种是动态调度。静 态调度是指程序在编译阶段，就将循环迭代任务近乎平均分配到各个线程上。而动态调度 则要到运行阶段才动态地将任务分配给空闲的线程，动态调度无需过多的关心循环体大小 以及循环迭代任务规模，就能获得好的负载均衡性能，同时，也会带来一定的调度开销。 而且现有的并行计算过程中,由于每次线程创建撤销以及调度均有一定开销,有些计算任 务采用多线程并行后，程序性能会大幅度下降；另外针对适合多线程并行的计算任务，在 进行任务调度时，需要为多线程分配任务，静态调度在程序运行前，就将任务分解并近乎 平均得分配给各个线程，当分解的任务大小差异很大时，会造成各个线程之间负载极不平 衡，影响程序运行性能。

发明内容

本发明所要解决的技术问题是提供一种面向多核平台的多线程划分及静态均衡调度 策略，采用全新设计思路，能够主动判断待处理任务是否适合多线程并行处理，并针对多 线程并行处理，实现任务调度时多线程之间任务分配的负载均衡，能够有效提高程序运行 的性能。

本发明为了解决上述技术问题采用以下技术方案：本发明设计了一种面向多核平台的 多线程划分及静态均衡调度策略，包括如下步骤：

步骤001.初始化系统各线程上所对应的负载G_load_m＝0，G_load_m表示系统第m个 线程上所对应的负载，m＝{1,…,M}，M表示系统线程的数量；然后针对待处理任务进行 划分，获得计算逻辑相互独立的各个任务块，构成任务块集合，并且各个任务块不可进一 步划分，并进入步骤002；

步骤002.针对任务块集合，获取各个任务块的计算时间，分别作为对应任务块的粒 度值，并进入步骤003；

步骤003.获得任务块集合中所有任务块粒度值所对应的粒度平均值，并判断粒度平 均值是否小于等于预设粒度平均值，是则将任务块集合中所有任务块所对应的待处理任 务，任意分配至其中一个线程上，由该线程针对该待处理任务进行串行处理，针对该待处 理任务的调度策略结束；否则进入步骤004；

步骤004.根据任务块集合中所有任务块粒度值所对应的粒度平均值，获得任务块集 合中所有任务块粒度值所对应的粒度值方差，并判断粒度值方差是否小于预设方差阈值， 是则进入步骤005；否则进入步骤006；

步骤005.判断系统线程的数量M是否大于等于任务块集合中任务块的数量N，是则 将任务块集合中各个任务块一一对应任意分配至各线程当中，由该各线程分别针对所分配 的任务块进行处理，针对任务块集合中所有任务块所对应的待处理任务的调度策略结束； 否则将第i个任务块分配至第m个线程上，i＝{m,m+M,…,m+KM}，K为大于等于1的 整数，m+KM≤N，实现针对任务块集合中各个任务块的分配，由系统各个线程分别针对 所分配的任务块进行处理，针对任务块集合中所有任务块所对应的待处理任务的调度策略 结束；

步骤006.获得任务块集合中所有任务块粒度值的总和平均分配至系统M个线程的平 均值，作为系统单线程负载范围标准值G_thread_avg，同时判断任务块集合中各任务块所对 应的最大粒度值是否大于G_thread_avg，是则获取任务块集合中各任务块所对应的最大粒度 值与G_thread_avg之间的差值，作为系统单线程负载波动范围值ΔG_thread，然后进入步 骤007；否则预设系统单线程负载波动范围值ΔG_thread，然后进入步骤007；

步骤007.提取任务块集合中所有大于系统单线程负载范围标准值G_thread_avg的粒 度值所对应的各个任务块，将该各个任务块一一对应任意分配至各线程当中，用该各个任 务块的粒度值分别更新对应各线程上所对应的负载，并在任务块集合中删除该各个任务 块，将任务块集合中剩余各个任务块按其所对应的粒度值由大至小的顺序进行排序，更新 任务块集合，获得任务块集合中任务块的数量N'，然后进入步骤008；

步骤008.初始化m＝1，n'＝1，进入步骤009；

步骤009.判断G_load_m+G_C_n'是否小于等于G_thread_avg+ΔG_thread，是则将任务 块集合中第n'个任务块分配至第m个线程当中，用G_load_m+G_C_n'的值更新第m个线程 上所对应的负载G_load_m，并在任务块集合中删除该任务块，更新任务块集合，然后进入 步骤011；否则进入步骤010；其中，G_C_n'表示任务块集合中粒度值按由小至大顺序第n' 个任务块所对应的粒度值；

步骤010.判断n'是否等于N'，是则进入步骤013；否则用n'+1的值更新n'，返回步 骤009；

步骤011.判断第m个线程上所对应的负载G_load_m是否大于等于 G_thread_avg-ΔG_thread，是则进入步骤012；否则令n'＝1，并返回步骤009；

步骤012.判断m是否等于M，是则针对任务块集合中所有任务块所对应的待处理任 务的调度策略结束；否则用m+1的值更新m，并令n'＝1，然后返回步骤009；

步骤013.判断第m个线程上所对应任务块的数量是否大于1，是则将第m个线程上最 后所分配的任务块退回至任务块集合当中，并更新任务块集合，然后进入步骤014；否则 进入步骤015；

步骤014.判断任务块集合中是否存在位于步骤013中所退回任务块下一个位置的任 务块，是则将任务块集合中步骤013中所退回任务块的下一个任务块分配至第m个线程当 中，用G_load_m加该任务块粒度值的和更新第m个线程上所对应的负载G_load_m，并在任 务块集合中删除该任务块，更新任务块集合，然后进入步骤011；否则返回步骤013；

步骤015.判断第m个线程上所对应任务块的数量是否等于1，是则进入步骤016；否 则进入步骤017；

步骤016.判断第m个线程上是否存在大于系统单线程负载范围标准值G_thread_avg的粒度值所对应的任务块，是则进入步骤017；否则将第m个线程上最后所分配的任务块 退回至任务块集合当中，并更新任务块集合，然后进入步骤014；

步骤017.判断m是否大于1，是则用m-1的值更新m，并返回步骤013，否则在预 设系统单线程负载波动范围值ΔG_thread基础上，按预设波动范围扩大并更新 ΔG_thread，然后返回步骤009。

作为本发明的一种优选技术方案：所述步骤007中，提取任务块集合中所有大于系统 单线程负载范围标准值G_thread_avg的粒度值所对应的各个任务块，将该各个任务块按其粒 度值由大致小的顺序进行排序，将系统各线程按其顺序与该各个任务块依序进行一一对 应，将该各个任务块分别分配至对应线程上，用该各个任务块的粒度值分别更新对应各线 程上所对应的负载。

本发明所述一种基于面向多核平台的多线程划分及静态均衡调度策略采用以上技术 方案与现有技术相比，具有以下技术效果：本专利所设计基于面向多核平台的多线程划分 及静态均衡调度策略，提出用于评估分解出任务大小的粒度值参数概念，首先根据一定判 断条件，判断一个任务是否真正适合多线程并行；其次采用静态调度策略，相比动态调度 来说，没有在运行阶段的调度开销；最后，不同于一般的静态调度策略，本发明提出一种 启发式静态调度策略，考虑了静态调度时当分解的任务大小差异很大时，会造成各个线程 之间负载极不平衡的问题，通过获取的任务块的粒度值，可以将差异很大的任务块合理分 配到不同线程上，达到负载均衡。

附图说明

图1是本发明设计的面向多核平台的多线程划分及静态均衡调度策略的流程图。

具体实施方式

下面结合说明书附图对本发明的具体实施方式作进一步详细的说明。

如图1所示，本发明所设计的一种面向多核平台的多线程划分及静态均衡调度策略， 其特征在于,包括如下步骤：

步骤001.初始化系统各线程上所对应的负载G_load_m＝0，G_load_m表示系统第m个 线程上所对应的负载，m＝{1,…,M}，M表示系统线程的数量；然后针对待处理任务进行 划分，获得计算逻辑相互独立的各个任务块，构成任务块集合，并且各个任务块不可进一 步划分，并进入步骤002。

步骤002.针对任务块集合，以各任务块单元为分析对象，将进入和退出各个任务块 的源代码位置作为插桩点分别进行插桩，由此可以获取各任务块的计算时间，分别作为对 应任务块的粒度值G_n，并进入步骤003；其中，G_n表示任务块集合中第n个任务块的粒度 值，n＝{1,…,N}，N表示任务块集合中任务块的数量。

步骤003.根据如下公式：

${\mathrm{Granul}}_{avg}=\frac{G_1+...+G_n+...+G_N}{N}$

获得任务块集合中所有任务块粒度值所对应的粒度平均值Granul_avg，并判断粒度平均 值Granul_avg是否小于等于预设粒度平均值，是则表明任务块粒度值过小，由于每次线程创 建撤销以及调度均有一定开销，所以该任务块集合中所有任务块所对应的待处理任务不适 合多线程并行，则将任务块集合中所有任务块所对应的待处理任务，任意分配至其中一个 线程上，由该线程针对该待处理任务进行串行处理，针对该待处理任务的调度策略结束； 否则进入步骤004。

步骤004.根据任务块集合中所有任务块粒度值所对应的粒度平均值Granul_avg，按如 下公式：

$S_G=\sqrt{\frac{{(G_1-{\mathrm{Granul}}_{avg})}^2+\mathrm{...}+{(G_n-{\mathrm{Granul}}_{avg})}^2+\mathrm{...}+{(G_N-{\mathrm{Granul}}_{avg})}^2}{N}}$

获得任务块集合中所有任务块粒度值所对应的粒度值方差S_G，并判断粒度值方差S_G是否小于预设方差阈值S，是则表明任务块粒度值相差不大，并行切分的任务块比较均匀， 则进入步骤005；否则进入步骤006。

步骤005.判断系统线程的数量M是否大于等于任务块集合中任务块的数量N，是则 将任务块集合中各个任务块一一对应任意分配至各线程当中，由该各线程分别针对所分配 的任务块进行处理，针对任务块集合中所有任务块所对应的待处理任务的调度策略结束； 否则将第i个任务块分配至第m个线程上，i＝{m,m+M,…,m+KM}，K为大于等于1的 整数，m+KM≤N，实现针对任务块集合中各个任务块的分配，由系统各个线程分别针对 所分配的任务块进行处理，针对任务块集合中所有任务块所对应的待处理任务的调度策略 结束。

步骤006.按如下公式：

$G\_{\mathrm{thread}}_{avg}=\frac{G_1+...+G_n+...+G_N}{M}$

获得任务块集合中所有任务块粒度值的总和平均分配至系统M个线程的平均值，作为 系统单线程负载范围标准值G_thread_avg，同时判断任务块集合中各任务块所对应的最大粒 度值是否大于G_thread_avg，是则获取任务块集合中各任务块所对应的最大粒度值与 G_thread_avg之间的差值，作为系统单线程负载波动范围值ΔG_thread，然后进入步骤007； 否则预设系统单线程负载波动范围值ΔG_thread，然后进入步骤007。

步骤007.提取任务块集合中所有大于系统单线程负载范围标准值G_thread_avg的粒 度值所对应的各个任务块，将该各个任务块按其粒度值由大致小的顺序进行排序，将系统 各线程按其顺序与该各个任务块依序进行一一对应，将该各个任务块分别分配至对应线程 上，用该各个任务块的粒度值分别更新对应各线程上所对应的负载，并在任务块集合中删 除该各个任务块，将任务块集合中剩余各个任务块按其所对应的粒度值由大至小的顺序进 行排序，更新任务块集合，获得任务块集合中任务块的数量N'，然后进入步骤008。

步骤008.初始化m＝1，n'＝1，进入步骤009。

步骤009.判断G_load_m+G_C_n'是否小于等于G_thread_avg+ΔG_thread，是则将任务 块集合中第n'个任务块分配至第m个线程当中，用G_load_m+G_C_n'的值更新第m个线程 上所对应的负载G_load_m，并在任务块集合中删除该任务块，更新任务块集合，然后进入 步骤011；否则进入步骤010；其中，G_C_n'表示任务块集合中粒度值按由小至大顺序第n' 个任务块所对应的粒度值。

步骤010.判断n'是否等于N'，是则进入步骤013；否则用n'+1的值更新n'，返回步 骤009。

步骤011.判断第m个线程上所对应的负载G_load_m是否大于等于 G_thread_avg-ΔG_thread，是则进入步骤012；否则令n'＝1，并返回步骤009。

步骤012.判断m是否等于M，是则针对任务块集合中所有任务块所对应的待处理任 务的调度策略结束；否则用m+1的值更新m，并令n'＝1，然后返回步骤009。

步骤013.判断第m个线程上所对应任务块的数量是否大于1，是则将第m个线程上最 后所分配的任务块退回至任务块集合当中，并更新任务块集合，然后进入步骤014；否则 进入步骤015。

步骤014.判断任务块集合中是否存在位于步骤013中所退回任务块下一个位置的任 务块，是则将任务块集合中步骤013中所退回任务块的下一个任务块分配至第m个线程当 中，用G_load_m加该任务块粒度值的和更新第m个线程上所对应的负载G_load_m，并在任 务块集合中删除该任务块，更新任务块集合，然后进入步骤011；否则返回步骤013。

步骤015.判断第m个线程上所对应任务块的数量是否等于1，是则进入步骤016；否 则进入步骤017。

步骤016.判断第m个线程上是否存在大于系统单线程负载范围标准值G_thread_avg的粒度值所对应的任务块，是则进入步骤017；否则将第m个线程上最后所分配的任务块 退回至任务块集合当中，并更新任务块集合，然后进入步骤014。

步骤017.判断m是否大于1，是则用m-1的值更新m，并返回步骤013，否则在预 设系统单线程负载波动范围值ΔG_thread基础上，按预设波动范围扩大并更新 ΔG_thread，然后返回步骤009。

本专利所设计基于面向多核平台的多线程划分及静态均衡调度策略，提出用于评估分 解出任务大小的粒度值参数概念，首先根据一定判断条件，判断一个任务是否真正适合多 线程并行；其次采用静态调度策略，相比动态调度来说，没有在运行阶段的调度开销；最 后，不同于一般的静态调度策略，本发明提出一种启发式静态调度策略，考虑了静态调度 时当分解的任务大小差异很大时，会造成各个线程之间负载极不平衡的问题，通过获取的 任务块的粒度值，可以将差异很大的任务块合理分配到不同线程上，达到负载均衡。

上面结合附图对本发明的实施方式作了详细说明，但是本发明并不限于上述实施方 式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做 出各种变化。