In order to reduce the scheduling makespan of a workflow,three list scheduling algorithms,namely,level and out-degree earliest-finish-time(LOEFT),level heterogeneous selection value(LHSV),and heterogeneous priority ea...In order to reduce the scheduling makespan of a workflow,three list scheduling algorithms,namely,level and out-degree earliest-finish-time(LOEFT),level heterogeneous selection value(LHSV),and heterogeneous priority earliest-finish-time(HPEFT)are proposed.The main idea hidden behind these algorithms is to adopt task depth,combined with task out-degree for the accurate analysis of task prioritization and precise processor allocation to achieve time optimization.Each algorithm is divided into three stages:task levelization,task prioritization,and processor allocation.In task levelization,the workflow is divided into several independent task sets on the basis of task depth.In task prioritization,the heterogeneous priority ranking value(HPRV)of the task is calculated using task out-degree,and a non-increasing ranking queue is generated on the basis of HPRV.In processor allocation,the sorted tasks are assigned one by one to the processor to minimize makespan and complete the task-processor mapping.Simulation experiments through practical applications and stochastic workflows confirm that the three algorithms can effectively shorten the workflow makespan,and the LOEFT algorithm performs the best,and it can be concluded that task depth combined with out-degree is an effective means of reducing completion time.展开更多
With the increasing energy consumption of computing systems and the growing advocacy for green computing, energy efficiency has become one of the critical challenges in high-performance heterogeneous computing systems...With the increasing energy consumption of computing systems and the growing advocacy for green computing, energy efficiency has become one of the critical challenges in high-performance heterogeneous computing systems. Energy consumption can be reduced by not only hardware design but also software design. In this paper, we propose an energy-aware scheduling algorithm with equalized frequency, called EASEF, for parallel applications on heterogeneous computing systems. The EASEF approach aims to minimize the finish time and overall energy consumption. First, EASEF extracts the set of paths from an application. Then, it reconstructs the application based on the extracted set of paths to achieve a reasonable schedule. Finally, it adopts a progressive way to equalize the frequency of tasks to reduce the total energy consumption of systems. Randomly generated applications and two real-world applications are examined in our experiments. Experimental results show that the EASEF algorithm outperforms two existing algorithms in terms of makespan and energy consumption.展开更多
基金The Natural Science Foundation of Hunan Province(No.2018JJ2153)the Scientific Research Fund of Hunan Provincial Education Department(No.18B356)+1 种基金the Foundation of the Research Center of Hunan Emergency Communication Engineering Technology(No.2018TP2022)the Innovation Foundation for Postgraduate of the Hunan Institute of Science and Technology(No.YCX2018A06).
文摘In order to reduce the scheduling makespan of a workflow,three list scheduling algorithms,namely,level and out-degree earliest-finish-time(LOEFT),level heterogeneous selection value(LHSV),and heterogeneous priority earliest-finish-time(HPEFT)are proposed.The main idea hidden behind these algorithms is to adopt task depth,combined with task out-degree for the accurate analysis of task prioritization and precise processor allocation to achieve time optimization.Each algorithm is divided into three stages:task levelization,task prioritization,and processor allocation.In task levelization,the workflow is divided into several independent task sets on the basis of task depth.In task prioritization,the heterogeneous priority ranking value(HPRV)of the task is calculated using task out-degree,and a non-increasing ranking queue is generated on the basis of HPRV.In processor allocation,the sorted tasks are assigned one by one to the processor to minimize makespan and complete the task-processor mapping.Simulation experiments through practical applications and stochastic workflows confirm that the three algorithms can effectively shorten the workflow makespan,and the LOEFT algorithm performs the best,and it can be concluded that task depth combined with out-degree is an effective means of reducing completion time.
基金Project supported by the National Natural Science Foundation of China （Nos. 61133005, 61432005, 61370095, 61472124, and 61402400）
文摘With the increasing energy consumption of computing systems and the growing advocacy for green computing, energy efficiency has become one of the critical challenges in high-performance heterogeneous computing systems. Energy consumption can be reduced by not only hardware design but also software design. In this paper, we propose an energy-aware scheduling algorithm with equalized frequency, called EASEF, for parallel applications on heterogeneous computing systems. The EASEF approach aims to minimize the finish time and overall energy consumption. First, EASEF extracts the set of paths from an application. Then, it reconstructs the application based on the extracted set of paths to achieve a reasonable schedule. Finally, it adopts a progressive way to equalize the frequency of tasks to reduce the total energy consumption of systems. Randomly generated applications and two real-world applications are examined in our experiments. Experimental results show that the EASEF algorithm outperforms two existing algorithms in terms of makespan and energy consumption.
