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:
- 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.
- 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.
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.
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