Performance analysis of parallel database sort operations in a heterogenous Grid Environment

In this paper an analytical comparison of the performance behavior of parallel flavors of the well-known Binary Merge Sort and Bitonic Sort algorithm in a grid environment is presented. To keep the analysis clear and focused we concentrate on a limited number of characteristic parameters and develop a concise but comprehensive analytical model both for a generalized multiprocessor framework and a simplified heterogeneous grid environment. We justify that a meaningful model can be built upon only three characteristic parameter sets, describing node processing performance, the I/O and the disk bandwidth, which are the parameters for the optimization the Grid workflow by a smart brokerage mechanism. Based on these results the paper proves that by a smart enhancement of the algorithms exploiting the specifics of the grid the well-known results of Bitton et al. for a homogenous multi-processor architecture are invalidated and reversed for a heterogenous Grid environment.