Data structures for parallel resource management

Abstract

The problem of resource management for many processor architectures can be viewed as the problem of simultaneously updating data structures that hold system state. Consistency requirements of strict data structures introduce serialization in the resource management functions thereby leading to performance bottlenecks in highly parallel systems. Our approach is to examine the possibility of using structures with weakened specifications. Specifically, this paper introduces data structures that weaken the specification of a priority queue permitting it to be updated simultaneously by multiple processes.