Browse Prior Art Database

Read Only Concurrent Traversal Technique for Cyclic Graphs

IP.com Disclosure Number: IPCOM000109596D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 2 page(s) / 98K

Publishing Venue

IBM

Related People

Revesz, GE: AUTHOR

Abstract

Described is a read-only concurrent traversal technique for cyclic graphs stored in shared memory. The concept provides a means whereby an arbitrary number of parallel processes can independently traverse the same graph.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Read Only Concurrent Traversal Technique for Cyclic Graphs

       Described is a read-only concurrent traversal technique
for cyclic graphs stored in shared memory.  The concept provides a
means whereby an arbitrary number of parallel processes can
independently traverse the same graph.

      Typically, in a shared memory multi-processor system, several
processors may concurrently access any data stored in the shared
memory of a computer system.  For parallel list processing and
similar applications, the most important shared data structures are
usually represented by direct graphs.  If several processors are
independently traversing the same graph stored in shared memory, then
a means must be implemented to keep track of the current state of the
traversal without processor interference.

      In direct acyclic graph technology, the current state of
traversal may be stored in a private control stack.  However, for
direct cyclic graphs, in order to avoid extraneous accesses, steps
were required such as marking all visited nodes or the reversal of
their pointers.  This approach however required significant overhead
when the number of independent processes concurrently traversed the
same graph.

      The concept described herein reduces the overhead by accessing
the graph in a strictly read-only manner without marking the visited
nodes or leaving any other traces of the current state in the shared
memory.  A distinguished node type is used to recognize cycles,
assuming that every cycle contains at least one of the distinguished
nodes.  Since this would be guaranteed by the construction of the
graph, any number of concurrent processes may traverse the graph
independently using its own control stack while storing all
distinguished nodes encountered by it in a separate private list....