Efficient Distributed Algorithms for Parallel I/O Scheduling

In distributed systems, the lack of global information about data transfer between clients and servers makes im-plementation of parallel I/O a challenging task. In this paper, we propose two distributed algorithms for schedul-ing data transfer in parallel I/O with non-uniform data sizes, the Maximum-Size/Maximum-Load (MS/ML) algo-rithm and the Minimum-Size/Earliest-Completion-First (MS/ECF) algorithm. Experimental results indicate that both algorithms achieve good performance, com-pared with the results achieved by their centralized coun-terparts. Both algorithms yielded parallel performances within 6 % of the centralized solutions. We also compare the performance of our algorithms with a distributed Highest Degree First (HDF) method, which handles non-uniform data transfers by dividing them into units of fixed-sized blocks which are then scheduled and transferred one at a time. Experimental results show that our algorithms require less scheduling and data transfer time, resulting in better overall parallel I/O performance. Our simulations also show that MS/ML is more suitable for parallel I/O with lighter data transfer traffic, while MS/ECF is more suitable for parallel I/O with heavy data transfer traffic. 1