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 heterogenous 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.