A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; s...A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.展开更多
Task scheduling in Grid has been proved to be NP-complete problem. In this paper, to solve this problem, a Hybrid Task Scheduling Algorithm in Grid (HTS) has been presented, which joint the advantages of Ant Colony an...Task scheduling in Grid has been proved to be NP-complete problem. In this paper, to solve this problem, a Hybrid Task Scheduling Algorithm in Grid (HTS) has been presented, which joint the advantages of Ant Colony and Genetic Algorithm. Compared with the related work, the result shows that the HTS algorithm significantly surpasses the previous approaches in schedule length ratio and speedup.展开更多
为了提高异构多核处理器平台的计算性能,从任务调度的角度出发,提出了一种使用黄金正弦和莱维飞行机制改进的麻雀搜索算法(Fusion of Golden Sinusoidal and Levy Flight in Sparrow Search Algorithm,GSLF-SSA)来优化异构多核处理器的...为了提高异构多核处理器平台的计算性能,从任务调度的角度出发,提出了一种使用黄金正弦和莱维飞行机制改进的麻雀搜索算法(Fusion of Golden Sinusoidal and Levy Flight in Sparrow Search Algorithm,GSLF-SSA)来优化异构多核处理器的任务调度。通过对异构任务调度的分析,将异构任务建模为DAG(Directed Acyclic Graph)任务模型,通过对其优先级进行随机编码分配,实现了GSLF-SSA算法求解域从连续到离散的映射,使该算法更能适用于异构多核任务调度之中。将DAG任务的最优调度长度作为算法的适应度值进行迭代寻优,通过与目前应用广泛的麻雀搜索算法(SSA)、混合式任务调度算法(IHSSA)、人工蜂群算法(ABC)等多种启发式算法在异构任务调度环境下的实验对比表明,GSLF-SSA能获得更优的调度长度与更短的调度执行时间。展开更多
文摘A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.
基金Supported by the Specialized Research Fund for the Doctoral Program of Higher Education(No.20030290003)
文摘Task scheduling in Grid has been proved to be NP-complete problem. In this paper, to solve this problem, a Hybrid Task Scheduling Algorithm in Grid (HTS) has been presented, which joint the advantages of Ant Colony and Genetic Algorithm. Compared with the related work, the result shows that the HTS algorithm significantly surpasses the previous approaches in schedule length ratio and speedup.
文摘为了提高异构多核处理器平台的计算性能,从任务调度的角度出发,提出了一种使用黄金正弦和莱维飞行机制改进的麻雀搜索算法(Fusion of Golden Sinusoidal and Levy Flight in Sparrow Search Algorithm,GSLF-SSA)来优化异构多核处理器的任务调度。通过对异构任务调度的分析,将异构任务建模为DAG(Directed Acyclic Graph)任务模型,通过对其优先级进行随机编码分配,实现了GSLF-SSA算法求解域从连续到离散的映射,使该算法更能适用于异构多核任务调度之中。将DAG任务的最优调度长度作为算法的适应度值进行迭代寻优,通过与目前应用广泛的麻雀搜索算法(SSA)、混合式任务调度算法(IHSSA)、人工蜂群算法(ABC)等多种启发式算法在异构任务调度环境下的实验对比表明,GSLF-SSA能获得更优的调度长度与更短的调度执行时间。
