A Balanced Allocation Strategy for File Assignment in Parallel I/O Systems

In parallel I/O systems, fast response to disk access and load balancing are two important performance objectives pursued by end users and applications. These performances are largely determined by the data allocation strategies, or file assignment algorithms. However, most existing algorithms can only obtain one of the performance objectives, including the well-known algorithms like Greedy, Sort Partition (SP) and Hybrid Partition (HP). New algorithms that can achieve both objectives are very necessary for parallel I/O systems. In this paper, we have proposed two new allocation algorithms for file assignment in parallel I/O systems: an offline Balanced Allocation with Sort (BAS) algorithm and an online Balanced Allocation with Sort for Batch (BASB) algorithm. Both algorithms aim to achieve the optimal mean response time and load balancing at the same time. The experiment results have shown that the BAS algorithm can get the optimal performance on response time among all compared algorithms and better performance on load balancing than SP. For online BASB algorithm, it can achieve the optimal performances on both response time and load balancing among all algorithms for comparison.