List Access Procedures for the Ultracomputer

Authors:Williams, Craig, Department of Computer ScienceUniversity of Virginia Reynolds, Paul, Department of Computer ScienceUniversity of Virginia

We describe a set of asynchronous procedures for accessing an unsorted linear linked list in shared memory. The procedures are designed for highly parallel computation on the ultracomputer and support search, insertion at the tail of the list, and deletion from anywhere within the list. The procedures maintain the consistency of the list without using high-level locks or any other kind of high - level critical section. No type of access locks out any other type of access, and any number of searches, insertions, and deletions can occur concurrently. Our simulation of the access procedures indicates that the time required for a list access can remain almost constant as the level of concurrency increases. We show that the procedures can be used to implement the wound-wait and wait-die protocols for accessing a database and as the basis for a space-efficient implementation of P and V operations that maintains FIFO order among waiting processes. Neither the database protocol nor the semaphore implementation itself introduces serialization. We also describe a parallel garbage collection algorithm based on reference counts which should collect garbage more promptly than marker-based algorithms and which can be used even when processes hold pointers into the shared structure exclusively in local memory.
Note: Abstract extracted from PDF file via OCR

All rights reserved (no additional license for public reuse)
Source Citation:

Williams, Craig, and Paul Reynolds. "List Access Procedures for the Ultracomputer." University of Virginia Dept. of Computer Science Tech Report (1987).

University of Virginia, Department of Computer Science
Published Date: