Petri nets and speed independent design

ABSTRACT

Petri nets are investigated as one method of modeling speed independent asynchronous circuits. A study of circuit realizations of Petri nets leads to a demonstration of their usefulness in modeling speed independent operation. This usefulness is emphasized by the design of a speed independent processor from modules developed in the investigation of Petri net implementation.

REFERENCES

• 1: Altman, Stanley, and Denning, Peter. Decompositions of control networks. Record of the Project MAC Conf. on Concurrent Systems and Parallel Computation. ACM, New York, 1970. pp. 81-92.
• 2: Bruno, J., and Altman, Stanley. Asynchronous control networks. Conf. Record 1969 Tenth Ann. Syrup. on Switching and Automata Theory. IEEE Computer Group, New York, 1969. pp. 61-73.
• 3: Clark, Wesley. A macromodular computer system. Proc. 1967 AFIPS SJCC, Vol. 30, AFIPS Press, Montvale, N.J., pp. 335-336.
• 4: Commoner, F., and Holt, A. Marked directed graphs. J. Computer and System Sciences 5 (Oct. 1971), 511-523.
• 5: Dennis, Jack. Private communication.
• 6: Dennis, Jack. Computation Structures. Course Notes, Dept. of Electrical Engineering, M.I.T., Cambridge, Mass., 1970.
• 7: Dennis, Jack, and Patil, Suhas. Speed independent asynchronous circuits. Proc. Fourth Hawaii Internat. Conf. on System Sciences. Western Periodical Co., North Hollywood, Calif., 1971. pp. 55-58.
• 8: Dennis, Jack. Modular asynchronous control structures for a high performance processor. Record of the Project MAC Conf. on Concurrent Systems and Parallel Computation. ACM, New York, pp. 55-80.
• 9: Furtek, Frederick. Modular implementation of Petri nets. MS Th., Dept. of Elec. Eng., M.I.T., Cambridge, Mass., Sept. 1971.
• 10: Gillies, D. B. A flow chart method for the description of a speed independent control. Proc. Sec. Ann. Syrup. and Papers from First Ann. Syrup. on Switching Theory and Logical Design. AIEE Subcommittee on Logic and Switching Circuit Theory, New York, pp. 109-110.
• 11: Grasselli, Antonio. Control units for sequencing complex asynchronous operations. IRE Trans. on Electronic Computers EC-11 (Aug. 1962), 483-493.
• 12: Hack, Michel. Analysis of production schemata by Petri nets. MS Th., Dept. of Elec. Eng., M.I.T., Cambridge, Mass., Feb. 1972.
• 13: Holt, Anatol and Commoner, Frederic. Events and Conditions. 3 Vols. Applied Data Research, Wakefield, Mass., 1968.
• 14: Holt, Anatol. Information system theory project, 1968. Dept. of Commerce, Clearinghouse, Springfield, VA 22151.
• 15: Kimura, Izumi. Some topics related to the logical circuits of the new Illinois computer. Electronics and Communications bt Japwl 46 (Nov. 1963), 92-99.
• 16: Luconi, Fred. Completely functional asynchronous computational structures. PhD Th., Dept. Elec. Eng., M,I.T., Cambridge, Mass. Jan. 1968.
• 17: Malhotra, Ashok. Asynchronous control of computer operations. MS Th. M.I.T., Sloan School of Management, Cambridge, Mass., Jan. 1967.
• 18: Meldman, Jeffrey and Holt, Anatol. Petri nets and legal systems. Jurimetrics Journal 12 (Dec. 1971), 65-75.
• 19: Miller, David. Switching Theory. Vol. 2. Wiley, New York, 1967.
• 20: Miller, R. E. An introduction to speed independent circuit theory. Proc. Sec. Ann. Syrup. and Papers from First Ann. Syrup. on Switching Theory and Logical Design, pp. 71-94.
• 21: Muller, David. Asynchronous logics and application to information processing. In Switching Theory attd Space Technology. Howard Aiken and William Mann (Eds.), Stanford U. Press, Stanford, Calif., 1963.
• 22: Muller, David. Flow chart methods for thelogical design of an asynchronous control. U. Illinois Digital Computer Labs, File 262, Jan. 1959.
• 23: Muller, David. The general synthesis problem for asynchronous digital networks. Conf. Record 1969 Tenth Ann. Syrup. on Switching and Automata Theory, pp. 71-94.
• 24: Muller, David, and Bartky, W. A theory of asynchronous circuits. In The Annals 2f the Computation Laboratory of Harvard University, Harvard U. Press, Cambridge, Mass., Vol. 29, pp. 204-243.
• 25: Patil, Suhas. Coordination of asynchronous events. ScD Th., Dept. of Elec. Eng., M.1.T., Cambridge, Mass., May 1970.
• 26: Patil, Suhas. Micro-modular implementation of the control modules of basic macro-modular circuits. M.I.T., MAC, Memo MAC-M-423. Oct. 1969.
• 27: Petri, Carl A. Communication with automata. Rome Air Develop. Cent., Suppl. I to Tech. Rep. No. RADC-TR-65-377. Reconnaissance-Intelligence Data Handling Branch, Rome Air Develop. Center, Griffin AFB, New York, Jan. 1966.
• 28: Robertson, James. Problems in the physical realization of speed independent circuits. Proc. Sec. Ann. Symp. and Papers from First Ann. Syrup. on Switching Theory and Logical Design pp. 106- 108.
• 29: Rodriguez, Jorge. A graph model for parallel computation. ScD Th., Dept. of Elec. Eng., M.I.T., Cambridge, Mass., Sept. 1967.
• 30: Stutz, Donald R. The flow graph schemata model of parallel computation. PhD Th., Dept. of Elec. Eng., M.I.T., Cambridge, Mass., Sept. 1968.
• 31: Swartwout, Robert. One method for designing speed independent logic for a control. Proc. Sec. Ann. Syrup. and Papers from First Ann. Syrup. on Switching Theory and Logical Design, pp. 94-105.

INDEX TERMS

Keywords:
Petri net, speed independent asynchronous