In recent years,with the development of processor architecture,heterogeneous processors including Center processing unit(CPU)and Graphics processing unit(GPU)have become the mainstream.However,due to the differences o...In recent years,with the development of processor architecture,heterogeneous processors including Center processing unit(CPU)and Graphics processing unit(GPU)have become the mainstream.However,due to the differences of heterogeneous core,the heterogeneous system is now facing many problems that need to be solved.In order to solve these problems,this paper try to focus on the utilization and efficiency of heterogeneous core and design some reasonable resource scheduling strategies.To improve the performance of the system,this paper proposes a combination strategy for a single task and a multi-task scheduling strategy for multiple tasks.The combination strategy consists of two sub-strategies,the first strategy improves the execution efficiency of tasks on the GPU by changing the thread organization structure.The second focuses on the working state of the efficient core and develops more reasonable workload balancing schemes to improve resource utilization of heterogeneous systems.The multi-task scheduling strategy obtains the execution efficiency of heterogeneous cores and global task information through the processing of task samples.Based on this information,an improved ant colony algorithm is used to quickly obtain a reasonable task allocation scheme,which fully utilizes the characteristics of heterogeneous cores.The experimental results show that the combination strategy reduces task execution time by 29.13%on average.In the case of processing multiple tasks,the multi-task scheduling strategy reduces the execution time by up to 23.38%based on the combined strategy.Both strategies can make better use of the resources of heterogeneous systems and significantly reduce the execution time of tasks on heterogeneous systems.展开更多
最大最小蚂蚁系统(Max-min Ant System,MMAS)是一种性能优良的启发式算法,常用于解决组合优化问题.当解决的目标问题规模较大、迭代轮次较多时,最大最小蚁群算法存在运行时间长的缺点.试验以开源串行包ACOTSP为基准,利用GPU多线程并发...最大最小蚂蚁系统(Max-min Ant System,MMAS)是一种性能优良的启发式算法,常用于解决组合优化问题.当解决的目标问题规模较大、迭代轮次较多时,最大最小蚁群算法存在运行时间长的缺点.试验以开源串行包ACOTSP为基准,利用GPU多线程并发的优势,采用并行蚂蚁策略将MMAS在CPU-GPU协同异构计算平台上并发实现.算法在GPU上运行时的影响因素,如数据传输、内存层次、库函数调用等,也得到有效分析,并作出针对性优化.试验最终取得了高达13倍的加速,表明并行MMAS策略具有高效性和实用性.展开更多
基金This work is supported by Beijing Natural Science Foundation[4192007]the National Natural Science Foundation of China[61202076]Beijing University of Technology Project No.2021C02.
文摘In recent years,with the development of processor architecture,heterogeneous processors including Center processing unit(CPU)and Graphics processing unit(GPU)have become the mainstream.However,due to the differences of heterogeneous core,the heterogeneous system is now facing many problems that need to be solved.In order to solve these problems,this paper try to focus on the utilization and efficiency of heterogeneous core and design some reasonable resource scheduling strategies.To improve the performance of the system,this paper proposes a combination strategy for a single task and a multi-task scheduling strategy for multiple tasks.The combination strategy consists of two sub-strategies,the first strategy improves the execution efficiency of tasks on the GPU by changing the thread organization structure.The second focuses on the working state of the efficient core and develops more reasonable workload balancing schemes to improve resource utilization of heterogeneous systems.The multi-task scheduling strategy obtains the execution efficiency of heterogeneous cores and global task information through the processing of task samples.Based on this information,an improved ant colony algorithm is used to quickly obtain a reasonable task allocation scheme,which fully utilizes the characteristics of heterogeneous cores.The experimental results show that the combination strategy reduces task execution time by 29.13%on average.In the case of processing multiple tasks,the multi-task scheduling strategy reduces the execution time by up to 23.38%based on the combined strategy.Both strategies can make better use of the resources of heterogeneous systems and significantly reduce the execution time of tasks on heterogeneous systems.
文摘最大最小蚂蚁系统(Max-min Ant System,MMAS)是一种性能优良的启发式算法,常用于解决组合优化问题.当解决的目标问题规模较大、迭代轮次较多时,最大最小蚁群算法存在运行时间长的缺点.试验以开源串行包ACOTSP为基准,利用GPU多线程并发的优势,采用并行蚂蚁策略将MMAS在CPU-GPU协同异构计算平台上并发实现.算法在GPU上运行时的影响因素,如数据传输、内存层次、库函数调用等,也得到有效分析,并作出针对性优化.试验最终取得了高达13倍的加速,表明并行MMAS策略具有高效性和实用性.