网格结点选择中基于时间模型的多起点最陡爬山算法

Multi-Start Most Steep Hill-Climbing Algorithm for Grid Node Selection Based on Execution Cost Model

为任务计算时间和任务间通信时间构建一个运行时间模型,根据资源性能相对差异,模型可从一种结点选择下的任务计算和任务间通信时间,计算出其他结点选择下的任务计算时间和任务间通信时间.基于运行时间模型实现的多起点最陡爬山算法,分别在多个潜在收敛域选择搜索起点,使搜索结果更优.该模型预测任务计算时间、结点内任务通信时间、结点间任务通信时间和应用总运行时间的平均误差分别为17%、19%、15%和11%,实验表明,该算法可有效提高应用性能.

To estimate task computation cost and task communication cost of an application, an execution cost model is constructed. According to the relative differences of resource performance, as well as computation costs and communication costs on a certain node selection, the costs on other node selections may be evaluated. Based on the model, a multi-start most steep hill-climbing algorithm is presented for searching suboptimal node selection. The starts of searching are respectively situated at different potential convergence fields, so the result of searching is more preferable. Experiments show that, the mean error of the model is 17% in forecasting computation cost, 19% in forecasting intra-node communication cost, 15% in forecasting inter-node communication cost, and 11% in forecasting application runtime, thus the algorithm is effective in promoting application performance.