Routing and scheduling I/O transfers on wormhole-routed mesh networks

This paper studies the problem of routing and scheduling parallel I/O opera tions to minimize the time required to transfer data between processors and I/O devices. In particular, a 2-dimensional mesh architecture is considere d in which routing is performed using wormhole switching and I/O nodes are placed on the periphery of the mesh. Two broad classes of data transfer mec hanisms are examined: schedules with blocking (SB), in which packets may be temporarily blocked during transit, and schedules with no blocking (SNB), in which packets are never blocked in the network. For both classes, optima l scheduling is shown to be NP-complete and heuristics are presented and ex perimentally evaluated via a detailed simulation, (C) 1999 Academic Press, Inc.