On-line algorithm for scheduling parallel tasks on related computational clusters with processors of different capacities and its average-case analysis

Abstract

In this article the on-line problem of scheduling parallel tasks on related computational clusters with processors of different capacities was studied in average case. In the problem the objective is to make a schedule on k clusters with w processors each of N tasks, where the task i,i≤N requires time hi on cluster with nominal capacity of processors and wi≤w processors. We presume for all 1≤i≤N that wi has uniform distribution on (0,w] and that hi has uniform distribution on (0,1]. The processors on different clusters have different capacities v1,…,vk. The task with nominal time hi will require wi processors be computed in time hi/vj on cluster number j. Let sum volume of computations W be the sum of volumes of computations for each task. Let L be the minimal time at which all clusters will compute all the tasks, assigned to them, where each task is assigned to one cluster. The expected value of free volume of computations E(Vsp) is used to analyze the quality of an algorithm, where Vsp=∑1≤i≤kviL-W. It was shown that for every algorithm for scheduling parallel tasks on related clusters E(Vsp)=Ω(w√N). An online scheduling algorithm Limited Hash Scheduling was proposed that distribute tasks to limited areas. This algorithm works in a closed-end mode and has a mathematical expectation of a free calculation volume equal to O(w√(N ln N)). The idea of the algorithm is to schedule tasks of close required number of required processors into different limited in time and the number of allowed to use processors areas on clusters.

Keywords

• построение расписаний
• онлайновый алгоритм
• режим closed-end
• вероятностный анализ
• процессоры различной производительности
• алгоритм размещения задач в ограниченные области