Extension of Divisible-Load Theory from Scheduling Fine-Grained to Coarse-Grained Divisible Workloads on Networked Computing Systems

The big data explosion has sparked a strong demand for high-performance data processing. Meanwhile, the rapid development of networked computing systems, coupled with the growth of Divisible-Load Theory (DLT) as an innovative technology with competent scheduling strategies, provides a practical way of conducting parallel processing with big data. Existing studies in the area of DLT usually consider the scheduling problem with regard to fine-grained divisible workloads. However, numerous big data loads nowadays can only be abstracted as coarse-grained workloads, such as large-scale image classification, context-dependent emotional analysis and so on. In view of this, this paper extends DLT from fine-grained to coarse-grained divisible loads by establishing a new multi-installment scheduling model. With this model, a subtle heuristic algorithm was proposed to find a feasible load partitioning scheme that minimizes the makespan of the entire workload. Simulation results show that the proposed algorithm is superior to the up-to-date multi-installment scheduling strategy in terms of achieving a shorter makespan of workloads when dealing with coarse-grained divisible loads.