The University of Western Australia

Technical Report 93/3

April 1993

A Scalable Implementation of

Globally-shared Queues*

R. Lyndon While

Abstract
This paper describes the use of combining networks to implement globally-shared first-in-first-out queues in scalable fashion. Up to N processors can access a queue in one time cycle, N being the maximum length of the queue. No critical code sections are required, no waiting is necessary and no bottleneck is created.

Keywords
Combining networks, process synchronisation, communications architecture

CR categories
C.1.2, D.4

Communicated by
Robyn Owens

* Part of this work was done whilst the author was an employee of INMOS Ltd.

Department of Computer Science