Cyclic Allocation of Two-Dimensional Data

Various proposals have been made for declustering two-dimensionally tiled dataon multiple I/O devices. Recently, it was shown that strictly optimalsolutions only exist under very restrictive conditions on the tiling of thetwo-dimensional space or for very few I/O devices. In this paper we exploreallocation methods where no strictly optimal solution exists. We propose ageneral class of allocation methods, referred to as cyclic declusteringmethods, and show that many existing methods are instances of this class. As aresult, various seemingly ad hoc and unrelated methods are presented in asingle framework. Furthermore, the framework is used to develop new allocationmethods that give better performance than any previous method and that approachthe best feasible performance.