A Scheduling Framework for a Heterogeneous Parallel Architecture
Wei Zhang · Spectrum Research Repository (Concordia University) · 2011
Scheduling on heterogeneous parallel and distributed computing environment has been studied for decades.Based on different assumptions, researchers have proposed several algorithms and heuristics aiming to improve the performance of parallel applications.Most of these works focus on clusters of CPUs or grid-based environments where heterogeneity is created by processors and networks of varying speeds.However, in recent years, there has been wide spread use of another type of heterogeneous parallel computing environment, even on regular PCs and workstations, which comprise of multi-core CPUs and many-core GPGPUs (General Purpose Graphic Processor Units).Heterogeneity in this new generation of computers is even more pronounced due to the significant differences in architectures and programming models between CPUs and GPGPUs.The scheduling problem on a heterogeneous environment is known to be NP-Complete.Consequently, this research proposes several approximate strategies to solve this problem on a heterogeneous CPU-GPGPU environment.As a focus of this research, the strategies utilize the structural and behavioral characteristics of patterns in parallel programming to facilitate scheduling decisions.The parallel pattern extensively studied in this research is the farm pattern, which is used in a wide range of parallel applications.For the purposes of scheduling, the farm pattern is further classified into several categories and subsequently scheduling strategies for each of these categories are proposed.The similar strategies can be employed for the scheduling of some other