题目 冒险模拟退火算法及其在任务映射上的应用
A SPECULATIVE SIMULATED ANNEALING ALGORITHM AND ITS APPLICATION IN TASK MAPPING
作者 倪南、王晨*、张德富*
NI NAN,WANG CHEN*,ANDZHANG DEFU*
单位 中国科学院计算技术研究所 北京 100080
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080*State Key Laboratory for Novel Software Technology at Nanjing University, Nanjing 210093*Department of Computer Science & Technology, Nanjing University, Nanjing 210093
关键词 模拟退火,冒险计算,任务映射。
simulated annealing, speculative computing, task mapping.
摘要 本文提出了一种冒险模拟退火算法。该算法将冒险计算引进模拟退火算法来处理任务映射问题。它引入任务图与费用函数的概念,不仅考虑到任务的计算时间,还考虑到任务间的通信时间。既确保了模拟退火的串行顺序,使解趋于最优,又缩短了达到最优所需时间,提高了并行计算效率。
In this paper, we present a speculative simulated annealing algorithm for task mapping. Speculative computing is introduced into simulated annealing to solve the task mapping problem. The concept of task graph and cost function are introduced. The algorithm not only takes computing time of a task into account, but also deals with communicating time. It maintains the serial sequence that the simulated annealing requires, and converges to a global optimum solution. And at the same time, it speeds up the solution and improves parallel computing efficiency.