Lower bounding techniques for the multiprocessor scheduling problem with communication delay
Lower bounding techniques for the multiprocessor scheduling problem with communication delay
复制标题
具有通信延迟的多处理器调度问题的下界技术
DOI：
10.1109/pact.1999.807534
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Tadanori Nakagawa
中科院分区：
文献类型：
--
作者：
S. Fujita;Tadanori Nakagawa
本文提出了两种方法来获得具有不可忽略通信延迟的多处理机调度问题(MSP)的精确下界。在所提出的技术中，我们应用不可避免的通信时延的概念来获得调度长度的一个非平凡下界。通过在几个随机生成的实例上进行实验，评估了导出界的有效性。实验结果表明，当处理器数目不是很少(例如，至少10个)并且最大通信代价不是很大(例如，小于或等于最小执行代价)时，所提出的技术产生了一个非常尖锐的下界，其至少是上界的97.5%。
This paper proposes two techniques for obtaining a sharp lower bound for the multiprocessor scheduling problem (MSP) with nonnegligible communication delay. In the proposed techniques, we apply the notion of inevitable communication delay to obtain a nontrivial lower bound on the scheduling length. The effectiveness of the derived bound is evaluated by conducting experiments on several randomly generated instances. By the results of the experiments, it is shown that the proposed techniques generate a very sharp lower bound that is at least 97.5% of an upper bound, when the number of processors is not very small (e.g., at least 10) and the maximum communication cost is not very large (e.g., less than or equal to the minimum execution cost).