Efficient Distributed Algorithms for Parallel I/O Scheduling
Jan‐Jan Wu, Yih-Fang Lin, Pangfeng Liu · 2005
In distributed systems, the lack of global information about data transfer between clients and servers makes implementation of parallel I/O a challenging task. In this paper, we propose two distributed algorithms for scheduling data transfer in parallel I/O with non-uniform data sizes, the maximum-size/maximum-load (MS/ML) algorithm and the minimum-size/earliest-completion-first (MS/ECF) algorithm. Experimental results indicate that both algorithms achieve good performance, compared with the results achieved by their centralized counterparts. 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.