多核处理器大规模并行系统中的任务分配问题及算法  

Allocating Tasks for Multi-core Processor-based Parallel System

作　　者：刘轶[1] 张昕[2] 李鹤[2] 钱德沛[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100083 [2]西安交通大学计算机系,陕西西安710049

出　　处：《小型微型计算机系统》2008年第5期972-975,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673180)资助

摘　　要：对基于多核处理器的大规模并行系统中的任务分配问题进行了分析讨论,在此基础上建立了任务分配模型,并提出一种基于迭代的任务分配算法,该算法分为两轮操作,分别完成进程到处理节点和进程内线程到处理器核的分配,每轮操作经过带回溯的多次迭代处理,最终得到任务关系图的划分.实验数据表明该算法能在较短时间内求得近优解,并且当线程个数增大时,算法的求解时间远小于遗传算法.After a discussion of the task allocation problem in multi-core processor-based parallel system, this paper gives the task allocation model,and proposes an iteration-based heuristic algorithm, which is composed of two round of operations,in which the processes are assigned to processing nodes in the first round and the threads within a process are assigned to processor cores in the second round respectively. Each round of operation partitions the Task Interaction Graph by iterations with backtracking. Evaluation result shows that the algorithm can find near-optimal solutions in reasonable time,and behaves better than genetic algorithm when the number of threads increases,since it can find solutions in much less time than genetic algorithm.

关 键 词：任务分配 多核处理器 并行计算 启发式算法 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]