Space-Efficient Queue Management Using Fixed-Connection Networks

摘要

On of the main difficulties in designing algorithms for large scale parallel machines is making sure that the capacities of the local memories are not exceeded. This paper presents a general scheme for dynamically reorganizing memory so that local memory constraints are never exceeded provided that global memory constraints are not exceeded. The scheme is simple, real-time, space-efficient, deterministic and transparent to the programmer. It requires only that the total hardware used (i.e., wires and total memory) exceed the number of local memories by a logarithmic factor. In return, the scheme guarantees an arbitrarily high percentage utilization of the total memory, independent of whatever local demands for memory arise. The authors analyze the behaviour of our scheme in worst-case and average-case settings, and show that it is optimal in many respects, even when compared to randomized algorithms.