high performance computing on graphics processing units: hgpu.org

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 patterns, e.g., data flow and pipeline. Since characteristics of the patterns and the features of the CPU-GPGPUs environment are both considered in making scheduling decisions, the proposed strategies are found to deliver better performances as compared to other contemporary strategies. A scheduling framework has been designed and implemented based on these strategies for the classified farm patterns. The framework not only intends to hide the complexity of parallel programming but also can automatically schedule tasks and balance loads among processors, relieving these burdens from the programmer. In addition, the framework serves as a test bed for newer scheduling heuristics on the target heterogeneous system, and also as an experimental verifier of the proposed hypothesis that use of patterns can facilitate in making better scheduling decisions.