利索能及
我要发布
收藏
专利号: 2016100224660
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-04-10
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种面向多核平台的多线程划分及静态均衡调度方法,其特征在于,包括如下步骤:

步骤001.初始化系统各线程上所对应的负载G_loadm=0,G_loadm表示系统第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_threadavg,同时判断任务块集合中各任务块所对应的最大粒度值是否大于G_threadavg,是则获取任务块集合中各任务块所对应的最大粒度值与G_threadavg之间的差值,作为系统单线程负载波动范围值ΔG_thread,然后进入步骤

007;否则预设系统单线程负载波动范围值ΔG_thread,然后进入步骤007;

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

步骤008.初始化m=1,n'=1,进入步骤009;

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

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

009;

步骤011.判断第m个线程上所对应的负载G_loadm是否大于等于G_threadavg-Δ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_loadm加该任务块粒度值的和更新第m个线程上所对应的负载G_loadm,并在任务块集合中删除该任务块,更新任务块集合,然后进入步骤011;否则返回步骤013;

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

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

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

2.根据权利要求1所述一种面向多核平台的多线程划分及静态均衡调度方法,其特征在于:所述步骤007中,提取任务块集合中所有大于系统单线程负载范围标准值G_threadavg的粒度值所对应的各个任务块,将该各个任务块按其粒度值由大至小的顺序进行排序,将系统各线程按其顺序与该各个任务块依序进行一一对应,将该各个任务块分别分配至对应线程上,用该各个任务块的粒度值分别更新对应各线程上所对应的负载。