Page 109 - 《软件学报》2021年第12期

王静莲 等:软硬件节能原理深度融合之绿色异构调度算法 3773

2.2 异构调度候选解的三维编/解码设计
仿照生物遗传或人工免疫理论,一个智能调度(候选)方案看作是基因组合的进化个体;本算法中,候选解(仿
r
+
+
+
r
r
,
生个体)Ch r (i∈{r∈R )的基因特征 G (i∈{r∈R )拟表示为三维编码 (X i r ,YZ i r ) ,代表随机任务 X (i∈{r∈R )被分
i
i
i
r
+
r
+
配到计算节点 Z (i∈{r∈R )的虚拟机 Y (i∈{r∈R )上.
i
i
如图 2 所示,每个立方体代表候选解不同维度的取值范围,而其中彩色填充部分则表示一个候选解(仿生个
+
体),即所有任务与计算节点及虚拟机编号的某种配置映射.因而,候选解个体 Ch r (i∈{r∈R )可编码为三维矩阵
(如公式(8)):
⎡ r Y r Z r ⎤ X
⎢ 1 r 1 r 1 r ⎥
⎢ X 2 Y 2 Z 2 ⎥
⎢ # # # ⎥
Ch r = ⎢ ⎥ (8)
⎢ i r Y i r Z i r ⎥ X
⎢ ⎥
⎢ # # # ⎥
⎢ ⎣ m r Y m r Z m r ⎥X ⎦
Cluster 2
…
… … … Cluster Cluster
1
k
作业解析产生的DAG集合 云异构众核超系统
类似染色体或抗体的仿生个体
m-基因组合
X i Y i Z i
G i
G 1 G 2 G m
(X i , Y i , Z i )
Z
‹ G i 对应于作业解析产生的“任务”α i ,
X 基因值为任务 α i 被分配到的虚拟机编码
Y ‹
O
映射
……
任务队列1 虚拟机φ 1 任务队列2 虚拟机φ 2 任务队列 n 虚拟机φ n
Fig.2 Three-dimensional coding of the candidate solution (bionic individual)
图 2 候选解(仿生个体)的三维编码表示
T
T
r
鉴于编码的有效合理性,所有仿生个体第一维列向量 [XX 2 r ,..., X i r ,..., X m r ] 对应随机任务[1,2,…,i,…,m] ,
,
1
是确定的值;第二维列向量元素(虚拟机编号)的上限取决于单节点虚拟机配置的最大值;第三维列向量元素(节
点编号)的最大值则由计算节点总数确定.这里,m 表示随机任务个数.
本算法解码细则考虑不同任务分配到同一虚拟机两种情形.
(1) 逻辑深度不同:遵循深度值排序原则,以避免任务之间长时间等待甚至发生死锁;
(2) 逻辑深度相同:遵循关联耦合强度排序原则,以缩短关键路径长度达到最优效果.
2.3 基于三维编码的协同进化算子定义
基于三维编码的基因组进化模拟包括个体选择、交叉、变异以及克隆等智能算子定义.
克隆算子在 GHSA_di/II 算法中对绿色异构调度候选解之多样性和逼近性起着重要作用,通常,其对仿生种
群 Ch = {Ch 1 ,Ch 2 ,...,Ch ε ,...,Ch 的克隆操作Γ C 可以定义为公式(9):
}
θ