Compiling path expressions into VLSI circuits

ABSTRACT

Path expressions were originally proposed by Campbell and Habermann [1] as a mechanism for process synchronization at the monitor level in software. Not unexpectedly, they also provide a useful notation for specifying the behavior of asynchronous circuits. Motivated by this potential application 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 area 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.

REFERENCES

• 1: Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
• 2: Michael John Foster, Specialized silicon compilers for language recognition, Carnegie Mellon University, Pittsburgh, PA, 1984
• 3: 3. Foster. M. J. and Kung, H. T. "Recognize Regular Languages with Programmable Building-Blocks." Journal of Digital Systems VI, 4 (Winter 1982). 323-332.
• 4: Robert W. Floyd , Jeffrey D. Ullman, The Compilation of Regular Expressions into Integrated Circuits, Journal of the ACM (JACM), v.29 n.3, p.603-622, July 1982 [doi>10.1145/322326.322327]
• 5: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 6: 6. Lauer, P. E. and Campbell. R. H. "Formal Semantics of a Class of High-Level Primitives for Coordinating Concurrent Processes." Acta Informatica 5 (June 5 1974). 297-332.
• 7: Charles Eric Leiserson, Area-efficient vlsi computation, Carnegie Mellon University, Pittsburgh, PA, 1981
• 8: 8. Li, W. and P. E. Lauer. A VLSI Implementation of Cosy. Tech. Rept. ASM/121, Computing Laboratory, The University of Newcastle Upon Tyne. January, 1984.
• 9: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 10: 10. Mukhopadhyay, A. "Hardware Algorithms for Nonnumeric Computation." IEEE Transactions on Computers C-28, 6 (June 1979), 384-394.
• 11: 11. Patil, Suhas S. An Asynchronous Logic Array. MAC TECHNlCAL MEMORANDUM 62, Massachusetts Institute of Technology. May, 1975.
• 12: V. R. Pratt, On the composition of processes, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-223, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582177]
• 13: 13. Rem. Martin. Partially ordered computations, with aplications to VLSl design. Eindhoven University of Technology, 1983.
• 14: 14. Seitz. C. L. "Ideas About Arbiters." LAMBDA First Quarter (1980). 10-14.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Design, Languages, Performance, Theory, Verification