e-mail: kstevens@ece.utah.edu
This is part of a tool set that was developed at Hewlett-Packard Labs to help with the development of a large (in 1988) 300,000 transistor asynchronous communication chip called the post office. During the initial design phase of the Post Office, Ken Stevens developed the burst-mode hazard model designed for high performance multiple-input-change and multiple-output-change asynchronous finite state machine implementation. The synthesis of these state machines was taking an inordinately large amount of time. The synthesis based on burst-mode was was done in a very "Unger-esque" style, and Ken figured the algorithms could be implemented in software. Grinding all the minimizations through by hand was also very error prone, and a tool would reduce these faults.
Al Davis took the challenge and made Ken a bet that within 3 weeks given a sum of products specification as input he could output correct asynchronous covering using a Quine-McCluskey like algorithm. Well, he got it working, but tuning the performance to make it efficient took several months!
Bill Coates hacked up some code that takes a state machine specification and generates the maximal compatibles. The user then selects the compatibles and his code will do the state assignment and output the unreduced logic equations. This is an Unger like reduction and uses the Tracey algorithm, and is a front end to the asynchronous logic minimizer.
Ken hacked up a back-end to the Logic Minimization that does CMOS transistor minimization, and generates a schematic for the circuit. This was interfaced to the design tool we've been using called Electric(tm), and so it hasn't been included. If you are interested, we can send you the code that does the transistor minimization.
Steve Nowick then came on as a summer student and interfaced the MEAT tool to Dave Dill's asynchronous verification tool called AVER. He also integrated the burst-mode hazard model into the version of AVER used at Hewlett-Packard for the implementation of the Post Office. (This version of AVER is not included with this software. Ask Ken if you want more details.)
This work has spawned interesting follow on projects at Stanford University and other sites. In particular, Ken Yun formalized the informal long arcs concept used in MEAT and the Post Office synthesis, integrated Steve Nowick's Exact combinational logic synthesis work, can utilize outputs as context signals to reduce state variables, and has added set/reset coverings in addition to the on-set coverings of MEAT. This work is available as the 3D synthesis system.
Although the MEAT code here is still perfectly functional, it has in my opinion been superseded by Ken Yun's 3D tool. This MEAT code is still offered here. The suite of examples that have been distributed with MEAT over the years may be of more interest than the MEAT code. These examples have been widely used in the literature as benchmarks for asynchronous Finite State Machine synthesis.
Common Lisp source for the Most Excellent Asynchronous
Tool,
MEAT -- burst-mode synthesis of asynchronous finite state
machines.
Documentation for compiling and using MEAT.
MEAT examples from the Post
Office chip and other sources.
Stevens, Kenneth S. "Automatic synthesis of Fast, Compact Self-Timed State Machines", University of Calgary Research Report No. 92/495/33, December, 1992.
W. S. Coates, A. L. Davis, and K. S. Stevens. "Automatic Synthesis of Fast Compact Asynchronous Control Circuits", IFIP Working Conference on Asynchronous Design Methodologies, March 1993.
Unger, Steven H. "Asynchronous Sequential Switching Circuits", 1983 Reprint by Robert E. Krieger Publishing Company, Inc., Krieger Drive, Malabar, Florida 32950 (originally published by Wiley, 1969)
Tracey, James H. "Internal State Assignments for Asynchronous Sequential Machines", IEEE Transactions on Electronic Computers, Vol. EC-15, No. 4, pages 551-560, August 1966.
K. S. Stevens, S. V Robison, and A. L. Davis. "The Post Office - Communication Support for Distributed Ensemble Architectures", Proceedings of 6th International Conference on Distributed Computing Systems, pages 160-166, May 1986. (Awarded best paper)
| Ken Stevens | kstevens@ece.utah.edu |
| Al Davis | ald@cs.utah.edu |
| Bill Coates | coates@eng.sun.com |
This software was developed at Hewlett-Packard Laboratories under the
Mayfly project.