page 1  (30 pages)
2to next section

Uniprocessor Performance of a Reference-Counting

Hardware Heap?

Technical Report 401

David S. Wisey, Brian Hecky, Caleb Hessy, Willie Hunty, and Eric Ostyz

c 1994: Indiana University (all rights reserved)
Bloomington, Indiana 47405-4101 USA
[email protected]

May 1994


A hardware implementation of a self-managing heap has been designed, built, and tested. It's uniprocessor performance demonstrates real-time storage management for general-purpose heap-based programs, and the availability of that performance on multiprocessors.

On every pointer write, remote reference-counting transactions occur in real-time memory; available space is maintained there without processor cycles. A processor obtains a new node simply by reading its address from a distinguished location there. Hardware support for off-line, multiprocessing mark/sweep collection is also provided.

Performance statistics are presented from an implementation of SCHEME, but this hardware is immediately useful also for languages like Lisp, Smalltalk, and C++. Although this prototype was fitted to a NeXT uniprocessor, the design is motivated by shared-heap multiprocessing, the target of a revised design.
CR categories and Subject Descriptors:
E.2 [Data Storage Representations]: Linked representations; D.4.2 [StorageManagement]: Allocation/Deallocation strategies; B.3.2 [Memory Structures]: Primary memory, Shared memory; C.1.2 [Multiple Data Stream

?Research reported herein was sponsored, in part, by the National Science Foundation under grants numbered DCR 85-21497 and DCR 90-027092.
yComputer Science Department
zCenter for Innovative Computer Applications