A Scheduling Method of Moldable Parallel Tasks Considering Speedup and System Load on the Cloud

Jianmin Li, Ying Zhong, Xinming ZhangIEEE Access 2019 · DOI

Introduction

Cloud computing environments increasingly rely on Moldable Parallel Tasks (MPTs)—applications that can execute on a variable number of processors. However, optimizing the scheduling of these tasks remains a significant challenge due to nonlinear speedup effects and fluctuating system loads. This paper introduces MC, a heuristic scheduling method designed specifically for MPTs that support a time-slice model. By decomposing tasks into granular units and dynamically adjusting parallelism, MC improves resource efficiency and task success rates even under uncertain load conditions.

The Challenge of Moldable Task Scheduling

Scheduling MPTs is complicated by two primary factors:

  1. Nonlinear Speedup: Increasing the number of processors for a task does not always yield a proportional decrease in execution time. Communication overhead eventually limits the benefits of parallelism.
  2. Dynamic System Load: Cloud environments experience constant shifts in demand. A static schedule often fails to account for resource availability changes that occur after a task has begun.

Traditional scheduling methods often treat tasks as "rigid" once they start. The authors address this by utilizing a "time-slice" approach, where sub-tasks hold resources exclusively for a set duration, after which they can be reconfigured or suspended.

Hierarchical model of cloud resources and parallel tasks

The MC Scheduling Method

The proposed MC (Moldable Cloud) method manages tasks through a multi-step heuristic process:

1. Reference Parallelism Calculation

Rather than assigning a fixed number of CPUs, the system determines a "reference parallelism" based on the current total system load. This prevents individual tasks from monopolizing resources during periods of high demand.

2. Time-Slice and Resource Allocation

The core of the MC method is the time-slice model. Large parallel tasks are treated as a matrix of synchronized "cloudlets." This granularity allows the scheduler to re-evaluate and adjust the resource allocation at regular intervals.

The time-slice model for scheduling moldable parallel tasks

3. Deadline-Aware Optimization

The algorithm continuously monitors task progress against deadlines. If a task is ahead of schedule, the system may reduce its allocated resources to minimize fragmentation. Conversely, if a task is lagging, additional resources are strategically assigned to ensure completion.

4. Dynamic Priority and Placement

Each cloudlet is assigned a dynamic priority score that increases as the deadline approaches. For final task placement, the authors employ a 0-1 integer programming model to optimize resource utilization, priority fulfillment, and total instruction throughput simultaneously.

Experimental Evaluation

The researchers evaluated the MC method using the CloudSim toolkit, simulating a large-scale environment with four datacenters and 2,000 Virtual Machines (VMs). The simulation used speedup characteristics modeled after the Weather Research and Forecasting (WRF) model.

Key Results

The MC method was compared against industry standards including FFDH, HEFTP, and AFCFSP:

  • Execution Efficiency: MC reduced average execution time (AET) by 37.5% to 81.3% compared to baseline methods.
  • Reduced Latency: Even with 90% load forecast accuracy (MC90), the method significantly lowered average waiting times (AWT).
  • Higher Reliability: MC achieved the lowest percentage of unfinished tasks (PFT). Specifically, MC with perfect load information (MC100) reduced task failure rates by 87.6% compared to the HEFTP method.

Conclusion

The MC scheduling method demonstrates that incorporating time-slicing and load-awareness into MPT management can drastically improve cloud performance. Its robustness to imperfect load forecasts makes it a practical solution for real-world cloud infrastructures where perfect information is rarely available. Future work will focus on integrating energy-saving techniques like Dynamic Voltage and Frequency Scaling (DVFS) to balance performance with power consumption.

Summary updated

Abstract

The moldable parallel task (MPT) is a kind of parallel task that their sub-tasks hold the resources exclusively, which has been widely used in different areas. Our paper focuses on the scheduling of moldable tasks when every sub-task supports time-slice. The time-slice is a consecutive time that the sub-task holds the resources exclusively. After every time-slice, the sub-task can be canceled, suspended, or continued. We give the model of MPTs and propose a scheduling method for MPTs: MC (a heuristic scheduling method supporting time-slice model on the cloud). The simulation results show that, even under a forecast accuracy of system load under 90% and 95%, MC reduces average waiting time and average execution time; at the same time, MC has a lower value in the percentages of unfinished tasks.
BibTeX
@inproceedings{li2019scheduling,
  author = {Jianmin Li and Ying Zhong and Xinming Zhang},
  title = {{A Scheduling Method of Moldable Parallel Tasks Considering Speedup and System Load on the Cloud}},
  booktitle = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2925429},
}
Figure