Dynamic Adaptation for Independent Task Scheduling Using Dynamic Programming in Multiprocessor Systems

Abstract

Performance in IT systems is critical to ensuring that systems meet user needs and expectations. In heterogeneous computing systems (HCS), which consist of processors with varying capabilities, dynamic adaptation plays a vital role in maintaining high performance. Dynamic adaptation enables systems to adjust task allocation and resource usage in real-time to respond to changes in workloads, resource availability, and system conditions. Task scheduling is a key aspect of achieving dynamic adaptation and remains a challenging NP-hard problem in HCS. Efficient scheduling requires optimizing competing objectives, such as minimizing makespan and maximizing processor utilization, to ensure that resources are used effectively. In this work, we propose DYnamic Task Allocation using dynamic programminG (DyTAg), a task scheduling algorithm based on dynamic programming, designed to support dynamic adaptation in HCS. Dynamic programming is particularly suited to this context as it breaks the scheduling problem into smaller, manageable subproblems and solves them incrementally, enabling efficient real-time adjustments. DyTAg leverages dynamic programming to minimize makespan while maximizing resource utilization, ensuring that tasks are allocated optimally even in complex, heterogeneous environments. To evaluate its performance, DyTAg is compared against established algorithms, including Min-Min, Max-Min, and Quality of Service Guided Min-Min, using various task sets and processor configurations. The results demonstrate that DyTAg achieves superior performance, particularly in scenarios involving independent tasks and small task sets, showcasing its potential to enhance dynamic adaptation and optimize performance in heterogeneous computing systems.