杨际祥 凌 玲

(重庆交通大学数学与统计学院 重庆 400074)



多核集群任务分配问题的0-1整数规划求解模型①

杨际祥②凌 玲

(重庆交通大学数学与统计学院 重庆 400074)

研究了典型多核集群任务分配中的节点内通讯特性。基于0-1整数非线性规划模型和线性松弛技术，给出了一种0-1整数线性规划任务分配问题求解优化模型。由于节点内的通讯量与通讯延迟较大，以最小化计算代价和节点间通讯代价为研究目标的传统求解模型具有严重的局限性，而该求解模型考虑了节点内通讯代价，并采用了线性规划松弛技术，其目标是最小化计算代价、节点间通讯代价和节点内通讯代价。计算结果验证了提出的模型的有效性。

多核集群， 任务分配问题(TAP)， 0-1整数规划， 线性规划松弛

0 引 言

任务分配问题(task allocation problem, TAP)是并行计算领域的一个经典问题，任务分配旨在将一组任务分配到一组计算节点上，以最小化总成本。总成本通常包括执行成本和节点间(或处理器间)通讯成本。然而，随着基于多核节点的以层次方式构成的集群成为并行计算的一种发展趋势，通讯成本不但包括节点间通讯成本，还应包括节点内通讯成本，而节点内通讯成本又与节点内的通讯量和通讯延迟两个因素密切相关。文献[1,2]通过通讯量和通讯延迟展示了节点内通讯的重要性。文献[1]指出，网络附属存储(NAS)基准测试中超过50%的通讯量是通过节点内通讯完成的。文献[2]研究表明，在典型的多核集群系统中，在节点内的通讯延迟与节点间的通讯延迟之比随消息的增大而增大。……