Parallel I/O scheduling using randomized, distributed edge coloring algorithms

Dannie Durand

doi:10.1016/S0743-7315(03)00015-7

2003-06-01

PRE

Dannie Durand *

Ravi Jain

David Tseytlin

DOI：10.1016/S0743-7315(03)00015-7

原文链接

原文求助

摘要

En 中文

A growing imbalance in CPU and I/O speeds has led to a communications bottleneck in distributed architectures, especially for data-intensive applications such as multimedia information systems, databases, and Grand Challenge problems. Our solution is to schedule parallel I/O operations explicitly. We present a class of decentralized scheduling algorithms that eliminate contention for I/O ports while maintaining an efficient use of bandwidth. These algorithms, based on edge-coloring and matching of bipartite graphs, rely upon simple heuristics to obtain shorter schedules. We use simulation to evaluate the ability of our algorithms to obtain near optimal solutions in a distributed context, and compare our work with that of other researchers. Our results show that our algorithms produce schedules within 5% of the optimal schedule, a substantial improvement over existing algorithms. (C) 2003 Published by Elsevier Science (USA).

Keyword:

OPERATIONS