Large-scale sorting in uniform memory hierarchies (Q1803300)

The traditional model of large-scale memory, in which input/output (I/O) takes place between internal memory and an external device, such as a disk or tape, focuses on only one small portion of the I/O problem. In most large-scale computer systems, memory progresses from very small but very fast registers to successively larger but slower components, such as several layers of cache, primary memory, disks, and archival storage. In order to achieve optimal performance on such a computer system, it is often necessary for the algorithm designer to take into account the physical characteristics of the entire memory hierarchy. Unfortunately, there are too many possible variables to consider (e.g., the block size of each level, the number of blocks at each level, and the communication bandwidth between one level and the next) to allow design of general algorithms; hence some degree of abstraction of the memory hierarchy is required. A relatively new model of blocked multilevel memories introduced by \textit{B. Alpern}, \textit{L. Carter} and \textit{E. Feig} [Uniform memory hierarchies. Proceeding of the 31st Annual IEEE Symposium on Foundations of Computer Science. St. Louis, MO, 600-608 (1990)] called the Uniform Memory Hierarchy (UMH), is studied. In Section 2, optimal and near- optimal sorting algorithms are given for UMH and its parallel variant for a wide range of bandwidth rates, and a parsimonious (optimal) schedule for merge sort is given for the case when the bandwidth is equal to 1. In Section 3, a natural and easy-to-program restriction of UMH is introduced, called random-access UMH (or RUMH), for which optimal upper and lower bounds for all bandwidths and amounts of parallelism are presented. A sequential model of UMH, called SUMH, is also discussed, and similar types of results are presented.