Compiling path expressions into VLSI circuits

T. S. Anantharaman, E. M. Clarke, M. J. Foster, B. Mishra

Research output: Contribution to journalArticlepeer-review


Path expressions were originally proposed by Campbell and Habermann [2] as a mechanism for process synchronization at the monitor level in software. Not surprisingly, they also provide a useful notation for specifying the behavior of asynchronous circuits. Motivated by these potential applications we investigate how to directly translate path expressions into hardware. Our implementation is complicated in the case of multiple path expressions by the need for synchronization on event names that are common to more than one path. Moreover, since events are inherently asynchronous in our model, all of our circuits must be self-timed. Nevertheless, the circuits produced by our construction have are proportional to N · log(N) where N is the total length of the multiple path expression under consideration. This bound holds regardless of the number of individual paths or the degree of synchronization between paths. Furthermore, if the structure of the path expression allows partitioning, the circuit can be laid out in a distributed fashion without additional area overhead.

Original languageEnglish (US)
Pages (from-to)150-166
Number of pages17
JournalDistributed Computing
Issue number3
StatePublished - Sep 1986


  • Path expressions
  • Process synchronization
  • Silicon compilation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Compiling path expressions into VLSI circuits'. Together they form a unique fingerprint.

Cite this