Computer Science ›› 2014, Vol. 41 ›› Issue (6): 18-21.doi: 10.11896/j.issn.1002-137X.2014.06.004

Previous Articles     Next Articles

Adaptive Simulated Annealing Algorithm for Task Assignment on Homogeneous Multi/Many-core Processors

YAN Qiao,QIN Zhi-dong,WANG Shao-yu and YAN Hong-man   

  • Online:2018-11-14 Published:2018-11-14

Abstract: With rapid increasing of the number of cores in multi/many-core processors,the task assignment solution space increases sharply so that reducing the relative deviation of the approximate solution becomes more and more difficult.An adaptive simulated annealing algorithm was put forward by establishing the relationship of the algorithm parameters and the number of optimized environment tasks and cores.The increasing of core number can not only effectively reduce the relative deviation of the approximate solution,but also shows high adaptability for the environment.Experiments reveal that on the 16cores platform,the adaptive simulated annealing algorithm iterations are increased by 41%,but the relative deviation is decreased by 86% versus the recent research results.

Key words: Many-core processor,Simulated annealing algorithm,Task assignment

[1] Partitioning S V.scheduling parallel programs for execution on multiprocessors[M].MIT Press,1989
[2] Huang L,Yuan F,Xu Q.On task allocation and scheduling forlifetime extension of platform based mpsoc designs[J].IEEE Transactions on Parallel and Distributed Systems,2011,2(12):2088-2099
[3] Kim J-K,Shivle S,Siegel H J,et al.Dynamically mapping tasks with priorities and multiple dead-lines in a heterogeneous environment[J].ParallelDistrib.Comp.,2007,7(2):154-169
[4] Koch P.Strategies for realistic and efficient static scheduling of data Independent algorithms onto multiple digital signal processors[R].Technical report.The DSP Research Group,Institute for Electronic Systems,Aalborg University,Aalborg,Denmark,December 1995
[5] Ferrandi F,Pilato C,Sciuto D,et al.Mapping andscheduling of parallel C applications with ant colony optimization onto heterogeneous reconfigurable MPSoCs[C]∥Design Automation Conference(ASP-DAC),201015th Asia and South Pacific.2010:799-804
[6] Coroyer C,Liu Z.Effectiveness of heuristics andsimulated an-nealing for the scheduling of concu-rrent tasks an empirical comparison[M]∥Rapport derecherche de l’INRIA Sophia Antipolis.1991:452-463
[7] Heikki O.Optimizing algorithms for task graph mapping onmultiprocessor system on chip SoCs[D].Tampereen teknillinen yliopisto,Julkaisu Tampere University of Technology,Publication,2011
[8] 温平川,徐晓东.并行遗传/模拟退火混合算法及其应用[J].计算机科学,2003,0(3):86-89
[9] 彭晓明,郭浩然,庞建民.多核处理器——技术、趋势和挑战[J].计算机科学,2012,9(Z11):320-326
[10] Wentzlaff D,Griffin P,Hoffmann H,et al.On chip interconnection architecture of the tile processor[J].IEEE MICRO,2007,7(5):15-31
[11] Zhang Y P,Jeong T,Chen F,et al.A study of the on chip interconnection network for the ibm cyclops64multicore architecture[C]∥Proceedings of the 20th international conference on Parallel and distributed processing,ser.IPDPS’06.Washington,DC,USA:IEEE Computer Society,2006:64-74
[12] Fan Dong-rui,Yuan Nan,Zhang Jun-chao,et al.Godson-t:Anefficient many-core architecture for parallel program executions[J].Journal of ComputerScience and Technology,2009,4(6):1061-1073
[13] Standard Task Graph Set.http://www.kasahara.elec.waseda.ac.jp/schedule/,2005-12-20
[14] Hashemi M.Automated Software synthesis for streaming applications on embedded manycore processors[D].University of California,Davis,2011
[15] Kw Y K,Ahmad I.Static scheduling algorithms forallocating directed task graphs to multiprocessors[J].ACM Comput.Surv.,1999,1(4):406-471
[16] 王颖锋,刘志镜.面向同构多核处理器的节能任务调度方法[J].计算机科学,2011,8(9):294-297

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!