Accession Number : ADA195167

Title :   Space-Efficient Queue Management Using Fixed-Connection Networks,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE MICROSYSTEMS RESEARCH CENTER

Personal Author(s) : Leighton, Tom ; Schwabe, Eric

PDF Url : ADA195167

Report Date : Nov 1987

Pagination or Media Count : 12

Abstract : 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. Keywords: Routing; Queueing networks; Lower bounds.

Descriptors :   *NETWORKS, *QUEUEING THEORY, ALGORITHMS, GLOBAL, GUARANTEES, LOGARITHM FUNCTIONS, MACHINES, MEMORY DEVICES, PARALLEL ORIENTATION, RANDOM VARIABLES

Subject Categories : Operations Research
      Command, Control and Communications Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE