A fully parallel algorithm for implementing path expressions

Anne Dinning, B. Mishra

Research output: Contribution to journalArticlepeer-review


Current research efforts in parallel architecture usually evolve from designs of a processor-memory-connection architecture with rudimentary facilities for synchronization and communication, which are often found to be inadequate to support the more sophisticated usages. In order to remedy this problem, we favor a top-down design, where the primitive operations are selected via a careful and thorough analysis of the high-level general purpose applications to be supported by the architecture. In this paper, we study how a high-level process-synchronization specification, presented in the path expression language, can be translated into a fully parallel implementation on an MIMD shared memory architecture and what primitive support facilities are necessary to achieve this. Primary emphasis is obviously on the simplicity of the system, the low synchronization overhead of the algorithm, the efficiency of the primitives, and the relative ease of system implementation.

Original languageEnglish (US)
Pages (from-to)205-221
Number of pages17
JournalJournal of Parallel and Distributed Computing
Issue number3
StatePublished - Nov 1990

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'A fully parallel algorithm for implementing path expressions'. Together they form a unique fingerprint.

Cite this