Page 282 - 《软件学报》2021年第8期

2564 Journal of Software 软件学报 Vol.32, No.8, August 2021

开销这 3 部分组成.
定义 5(最优线程重分配). 现对非关键线程进行重分配,首先需要考虑集群内工作节点的资源占用率,在满
足资源约束的条件下,为减少节点间的通信开销,需要将非关键线程重新分配到运行其父线程的关键节点上.此
外,在进行非关键线程重新分配时,除了需要满足资源约束模型,还需要防止非关键线程分配出现扎堆现象.其
原因为线程在进行重分配时,一般倾向于往通信开销较小的节点分配.由于上游非关键线程已经进行重分配,则
下游非关键线程优先考虑分配到上游非关键线程所在的关键节点上.为避免上述情况,故非关键线程重分配需
要加入 RR 与 CPU 优先级(工作节点中 CPU 的利用率最低)两个限制条件.
如果一个非关键子线程仅存在一个关键父线程,则将非关键子线程重新分配到运行其关键父线程的关键
节点上;如果一个非关键子线程存在两个或多个关键父线程,则为防止扎堆现象的出现,首先需要考虑 RR,在满
足 RR 的条件下,优先将非关键子线程重新分配到 CPU 利用率最低的关键父线程所在的关键节点上;如果运行
父线程的关键节点的资源利用率达到极限,则同样为防止扎堆现象的出现,在满足 RR 的条件下,优先将非关键
子线程重新分配到 CPU 利用率最低的关键节点上.

以图 4 为例,n 1 与 n 2 为关键节点,n 3 为非关键节点,且 n 1 存在 3 个线程,n 2 存在 4 个线程,则非关键子线程 e c
被分配到 n 1 ,而非关键子线程 e i 被分配到 n 1 ,即
s
communication cost between node
e ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→ n 1 (13)
c
communication cost between nodes
e ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→ n 1 (14)
i
RR
如果 n 1 与 n 2 内的线程数量相等,且 n 1 的 CPU 占用率高于 n 2 ,则非关键子线程 e i 被分配到 n 2 ,即
RR
e ⎯⎯⎯⎯⎯→ n (15)
i CPU priority 2
如果 n 1 的资源占用率已达到极限,则非关键子线程 e c 在满足 RR 与 CPU 优先级的前提下分配到关键节点
n i ,即
RR
e ⎯⎯⎯⎯⎯→ n i (16)
c
CPU priority
此外,选择 CPU 优先级为评判指标,是由于 CPU 的利用率对集群的性能影响最大.
2.4 数据迁移模型
根据第 2.3 节可知,集群已生成新的拓扑路径.现通过最优线程重分配模型建立数据迁移模型,将原非关键
线程上的数据迁移到对应的关键线程中.
若父线程 e ab 传输给非关键子线程 e ji 数据的大小为 d ji ,在完成非关键子线程重分配后,父线程对子线程的数
据分配发生改变,类似数据流 d ji 从 e ji 迁移到 e′ ,即
ji
da
e ⎯⎯⎯→ ∑ e′ ji (17)
ji
ji
fn )→ fn i
( )
( j
根据定义 4 可知,数据迁入存在资源约束的问题,需要满足数据迁入原则 tr,即
r + o ≤ r (18)
i n input i n i n
其中, r i n input 表示数据迁入后工作节点增加的资源占用率, o 表示原工作节点的资源占用率, r 表示工作节点资
i n
i n
源占用率的极限,则式(17)符合数据迁入原则 tr.此外,具体结果在第 4.2 节体现.
定理 2. 根据定义 3 可知,原集群的路径成本为 W cost ,数据迁移完成后集群的路径成本为W ′ ,则
cost
W′ cost < W cost (19)
证明:根据定义 3 可知,集群的路径成本由节点间通信开销、节点内部进程间通信开销、节点内部线程间
edge
的通信开销与线程的计算开销这 4 部分组成.其中,节点间通信开销为 W node cost ;节点内部线程间的通信开销为
edge
executor
W executor cost ;线程的计算开销为 W computation cost ;由于每个节点仅分配一个进程,则节点内部进程间的通信开销为 0.
令节点间存在 n 条路径,节点内部线程间存在 m 条路径.集群拓扑数据迁移完成后,共有 s 条节点间路径发生改
变,其中有 d 条节点间路径变为节点内部线程间路径,有 c 条节点间路径变为新的节点间路径.则当前节点间的