【作者】 黄亮；

【导师】 彭蔓蔓；

【作者基本信息】 湖南大学 ， 计算机科学与技术， 2011， 硕士

【摘要】 多年以来,处理器性能的提升主要依赖其工作频率的提高,然而受到芯片功耗及发热等因素的影响,这种做法已接近极限。在这种情况下多核处理器应运而生并得到了迅速发展,与此同时多核处理器系统也为任务调度与负载均衡研究提供了广阔的发展空间。目前,在多核处理器的任务调度和负载均衡中,首先将任务节点分配到处理器,其次在处理器中对任务节点进行调度,目标是使系统的整体执行时间最少,最大化发挥多核处理器的优势。本文对现有任务分配和任务调度算法进行改进,并在改进算法的同时考虑到任务处理器之间和处理核之间的负载均衡,主要工作包括以下两个方面：一方面,在现有DAG任务分配模型的基础上建立任务分组,并对任务分配算法进行改进,改进的重点是在进程任务进行复合时,不是单纯依据进程任务的通信时间来进行复合,而是综合考虑复合两个进程任务的通信时间和执行时间两个因素,依据设定的标准,选择最佳的两个进程任务进行复合,使分配到处理器上的进程任务更加均衡。模拟实验表明,改进的任务分配算法在处理器上的任务负载度和在处理器之间的任务执行时间差两方面比已有任务分配算法均有改进。另一方面,针对遗传算法在初始种群生成具有一定的盲目性问题,提出均衡种群遗传算法(Balanced Population Genetic Algorithm, BPGA),该算法对标准遗传算法初始种群生成算法进行改进,首先,在保证任务节点的高度约束的条件下,将任务节点依据高度值进行分组；然后,随机选择处理核和任务节点,并保证分配到每个处理核上的任务节点数基本均等,最后,在任务分配完成后,再根据任务分配到处理核上的执行时间大小实现任务节点的调整,使分配到每个处理核上任务节点的执行时间相对均衡,从而缩短整体任务执行时间,进一步提高处理核之间任务负载均衡。实验结果显示,BPGA算法在处理核间的任务负载均衡度和整体执行时间两个方面优于其他同类算法。更多还原

【Abstract】 Over the years, processor performance mainly depends on its frequency increased, however, this approach is close to the limit by the chip power consumption, heat and other factors. Under this condition, the multi-core processor came into being and has been developing rapidly, while multi-core processor system provides a broad space for the development of task scheduling and load balancing research. At present, when task scheduling and load balancing takes place on multi-core processors, first, the processes are assigned to the processors, then the nodes belonging to processes are scheduled on processing cores, the goal is to make the overall system execution time at least and maximize to play the multi-core processors advantage. In this paper, the existing task allocation and task scheduling algorithm is improved, furthermore, we take load balancing into account between processors and processing cores. The main work includes the following two aspects:On the one hand, we establish the task groups based on the existing DAG task allocation model and improve the task allocation algorithm, the improved algorithm compounding the processes not olny considers the communication time but foci on the two factors, which is the communication time and execution time. According to the setting standard, the algorithm will choose the best two processes to compound and make the task nodes will be more balanced on the processors. Simulation experiments show that the improved task allocation algorithm is superior to the existing task allocation algorithm in the level of workload and the execution time on the processor.On the other hand, taking the analysis based on the existing genetic algorithm, we propose a balanced population Genetic Algorithm algorithm named BPGA. The BPGA improves the standard genetic algorithm for its generating initial population, which has a certain blindness on the issue, frist, we take the task nodes category under the constraints of the height of task nodes; then, we select task nodes depending on the height of their value and processing cores randomly to make the nodes randomly assigned to processing cores,at the same time,we also making the number of nodes assigned to each processing core is load balancing; finally, we move the task nodes by their execution time on each processing core to make the processing cores relative balance after the nodes have been allocated, which can reduce the overall task execution time to make further balancing load between processing cores and also allow the system to maximize resource utilization. Experimental results show that the BPGA algorithm in the load balancing and the execution time has an advantage over other algorithms.更多还原