Exploiting Hierarchy In Heterogeneous Environments

Heterogeneous cluster environments are becoming an increasingly popular platform for executing parallel applications. Efficient heterogeneous parallel applications must account for the differences inherent in such an environment. Specifically, faster machines should possess more data items than their slower counterparts and communication should be minimized over slow network links. We propose the k-Heterogeneous Bulk Synchronous Parallel (HBSPk) model, which is based on the BSP model of computation, as a framework for developing applications for heterogeneous systems. The BSP model is appropriate for 1-level (one communication network) heterogeneous systems. HBSPk extends BSP hierarchically to address k-level heterogeneous machines. The utility of the model is demonstrated through the design and analysis of the gather and one-to-all broadcast operations. Experimental results demonstrate the improved performance that results from effectively exploiting the heterogeneity of the underlying system. By hiding the non-uniformity of the underlying system from the application developer, the HBSPk model offers a framework that encourages the design of heterogeneous parallel software