Problem-centric scheduling for heterogeneous computing systems

Abstract

This project addresses key scheduling problems in heterogeneous computing environments. Heterogeneous computing systems (HCSs) have received increased attention since the 1990s, particularly over the past 10 years with the popularity of grid computing systems. These computing environments consist of a variety of resources interconnected by a high-speed network. Many parallel and distributed applications can take advantage of this computing platform; however, resource heterogeneity and dynamism impose scheduling restrictions. It is extremely difficult for a single scheduling scheme to efficiently and effectively handle the application scenarios that are required in grid computing environments. What further complicates the issue is that computing environments are controlled by different administrative authorities. Thus, application diversity, and resource heterogeneity and dynamism, point to the need to develop a set of scheduling algorithms to manage these scenarios. The thesis describes a number of key application and system models, and extensively discusses the characteristics of traditional multiprocessor scheduling and grid scheduling. The application models can be broadly classified as independent and precedence-constrained. The coupling of resources in our HCS model can be tight or loose; while static scheduling is applied to tightly coupled platforms, dynamic scheduling is adopted on loosely coupled platforms. The thesis presents the scheduling schemes that we have developed to address various challenging scheduling issues, and sets out and interprets the experimental results from our performance evaluation study. The data indicate that our novel scheduling algorithms—which appropriately incorporate application and system characteristics into their scheduling—demonstrate significantly superior performance than previous approaches.