On the Design of a Time, Resource and Energy Efficient Multi-Installment Large-Scale Workload Scheduling Strategy for Network-Based Compute Platforms

Multi-installment scheduling (MIS) has been deemed as a promising paradigm that can sharply reduce the processing time of large-scale divisible workloads on various network-based compute platforms. Unfortunately, the practicality of MIS was crippled due to its overwhelming complexity for deriving optimal values for $(n\times m)+2$(n×m)+2 related variables, i.e., we have to obtain an optimal number $n$n of required computing resources, optimal number $m$m of installments, and optimal load partition matrix $A=(\alpha _{ij})_{n\times m}$A=(αij)n×m which determines the sizes of load fractions assigned to each computing unit in every installment. To circumvent this complexity, in this paper, we first derive explicit analytical expressions for optimal load partition matrix $A$A of size $n\times m$n×m based on a given number of $n$n and $m$m. Then we propose a heuristic algorithm referred to as Time, Resource, and Energy Efficient MIS (TREE-MIS) to determine optimal values of $n$n and $m$m. The efficiency of our approach is shown to significantly improve since it can produce globally optimal solutions directly for $(n\times m)$(n×m) variables among $(n\times m)+2$(n×m)+2 in total for MIS problems based on the derived analytical expressions within a short runtime. We conduct extensive simulations to demonstrate the effectiveness of the proposed algorithm. Simulation results show that our TREE-MIS can not only minimize the processing time of workloads as well as improve resource utilization of the compute platform but also drastically reduce the runtime compared to other state-of-art MIS strategies. Furthermore, while handling large-scale workloads in any large network infrastructures would inexorably result in significant amounts of energy wastage if the strategy is not prudently designed. As an offshoot of our analysis and design, we clearly demonstrate that the energy wastage in adopting our TREE-MIS is kept minimum when compared to other currently available strategies in practice.