预览加载中,请您耐心等待几秒...
1/9
2/9
3/9
4/9
5/9
6/9
7/9
8/9
9/9

在线预览结束,喜欢就下载吧,查找使用更方便

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107704319A(43)申请公布日2018.02.16(21)申请号201710972593.1(22)申请日2017.10.18(71)申请人哈尔滨工程大学地址150001黑龙江省哈尔滨市南岗区南通大街145号哈尔滨工程大学科技处知识产权办公室(72)发明人李静梅李岚婷李赫(51)Int.Cl.G06F9/48(2006.01)G06N3/00(2006.01)权利要求书1页说明书5页附图2页(54)发明名称改进烟花算法的CMP任务调度方法(57)摘要本发明公开了改进烟花算法的CMP任务调度方法,属于计算机体系结构领域。具体步骤包括:设定初始参数;随机生成N个烟花的位置向量;计算烟花的爆炸火花数量、爆炸幅度和适应度值;进行爆炸操作和高斯变异操作;反复迭代后输出最优任务调度序列。本发明在烟花算法中引入排斥算子;同时,在排斥操作的维数上应用非线性惯性权重因子;采用的编码方案保留烟花位置是多维向量的特点,只重新定义每一维表示的含义和取值范围。本发明保证烟花产生的火花有效,有利于算法迭代后期在最优值附近进行细致性的寻优,编码方便、高效,能在更短时间内找到精度更高的解,有效提高了CMP架构下任务的执行效率。CN107704319ACN107704319A权利要求书1/1页1.改进烟花算法的CMP任务调度方法,其特征在于,包括以下步骤:(1)设定烟花个数N、基本爆炸火花数、基本爆炸半径、排斥操作界定距离、排斥操作作用维数的初始值、最大迭代次数、初始DAG图;(2)根据本发明所述的编码方式随机生成N个烟花的位置向量;(3)计算烟花的爆炸火花数量、爆炸幅度和适应度值;(4)进行爆炸操作和高斯变异操作,产生爆炸火花和高斯变异火花,并将超出可行域范围的火花映射回可行域内;(5)判断适应度值最优的烟花产生的火花是否需要进行排斥操作,若需要,转至步骤⑥,若不需要,转至步骤(7);(6)随机选择火花的维进行排斥操作,若排斥后有火花超出可行域范围则将其映射回可行域内;(7)计算爆炸火花和高斯变异火花的适应度值;(8)将适应度值最好的烟花或火花保留到下一代,根据基于欧式距离的轮盘赌规则选择其余N-1个烟花;(9)是否满足算法终止条件,达到最大迭代次数,若满足,输出最优任务调度序列,算法停止;若不满足,转至步骤(3)。2.根据权利要求1所述的改进烟花算法的CMP任务调度方法,其特征在于:步骤(2)所述的编码方式如下:编码保留每个烟花的位置是多维向量的特点,只对每一维表示的含义重新定义;用Xi表示烟花i的位置向量,即:Xi=[x1,x2,…,xj,…,xm]、xj=rand(1,n),其中n表示处理器核的数量,rand(1,n)表示在1到n之间随机取整数值;m表示任务的数量,xj表示第j个任务被分配到xj处理器核上执行。3.根据权利要求1所述的改进烟花算法的CMP任务调度方法,其特征在于:步骤(6)所述的排斥操作方法如下:当适应度值最好的烟花与其产生的火花之间距离小于可接受范围时进行排斥操作:其中,表示烟花i产生火花的位置向量第k维取值,是经过排斥作用后的火花位置向量第k维取值,Δs是排斥算子;考虑到CMP任务调度的特点,应用在CMP任务调度上的排斥算子取值为:Δs=rand(0,n-1),其中n表示处理器内核的数量,rand(0,n-1)是在0到n-1之间随机取整数的函数。4.根据权利要求1,3所述的改进烟花算法的CMP任务调度方法,其特征在于:步骤(6)所述的排斥操作作用维数z的迭代方法为:z(t)=w*z(t-1),其中z(t)表示第t次迭代排斥操作作用维数的取值,z(t-1)表示第t-1次迭代排斥操作作用维数的取值,w是一个随迭代次数t增加而递减的非线性惯性权重值,满足:w(t)=(1/2)t,其中w(t)是第t次迭代w的取值。2CN107704319A说明书1/5页改进烟花算法的CMP任务调度方法技术领域[0001]本发明属于计算机体系结构领域,具体涉及一种改进烟花算法的CMP任务调度方法。背景技术[0002]受内核间的硬件资源共享和任务间的依赖关系影响,有依赖的CMP任务调度容易产生资源争用,使得多核处理器吞吐率下降,并行性、高效性得不到有效发挥。[0003]CMP任务调度问题是一类NP完全的组合优化问题。目前,在任务调度问题上应用较多的组合优化算法是遗传算法(GeneticAlgorithm,GA),但遗传算法容易“早熟”,并且由于其复杂的交叉变异操作,算法的时间复杂度和执行效率容易受到任务数量影响,导致任务调度结果不能满足实际需求。[0004]烟花算法(FireworksAlgorithm,FWA)是在2010年由谭营提出的一种新型群体智能优化算法。烟花算法在求