Asynchronous circuits promise a number of important advantages over its synchronous counterparts for the design of digital circuits. These advantages, including elimination of clock skew problem, potential low-power consumption, average-case performance, modularity, and automatic adaptation to physical changes, have also encouraged an extensive research in recent years. Asynchronous circuits must be not only functionally equivalent to the specification but also free from hazards. Speed-independent (SI) circuits, relying on the unbounded gate delay model, are a broadly adopted design style for asynchronous applications. Our implementation structure for SI circuits is based on the standard C-implementation, which uses Muller C-elements as its asynchronous latches. After an SI circuit is synthesized from its specification, logic decomposition is then performed for technology mapping. The decomposition of a gate into smaller gates must again preserve not only the functional correctness but also speed independence, i.e., hazard freedom.

　　In this thesis, the modeling of an SI circuit is based on a class of interpreted free-choice Petri nets (PNs) named signals transition graphs (STGs). PNs are a powerful model to describe the behavior of a concurrent system that gracefully captures the behavior of causality, concurrency, and conflict between events. The proposed synthesis and decomposition techniques are based on the analysis of the concurrent and interleave relations between signal transitions in an STG, and the generation of covering cubes that cover the reachable markings. This STG-based approach can eliminate the state explosion problem by avoiding the explicit generation of all the markings.

　　The work in this thesis starts by synthesizing a hazard-free implementation from the STG specification of an SI circuit. Then a hazard-free combinational decomposition is performed to decompose each high-fanin gate into lower-fanin ones, carried down to two-input gates, on which technology mapping techniques operate. For those gates that cannot be hazard-freely decomposed, two signal-adding methods constructed at the STG level are developed for resynthesis. This decomposition and resynthesis process is iterated until all high-fanin gates are successfully decomposed or no solution can be found. The time efficiency of our method has been demonstrated in the experimental results conducted on the asynchronous benchmarks.

[1] P. A. Beerel and T. H.-Y. Meng, “Automatic gate-level synthesis of speed-independent circuits,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 581-587, Nov. 1992.

[2] E. Brunvand, Translating Concurrent Communicating Programs into Asynchronous Circuits. PhD thesis, Carnegie Mellon University, 1991.

[3] J. A. Brzozowski and K. Raahemifar, “Testing C-elements is not elementary,” in Proc. Second Working Conference on Asynchronous Design Methodologies, pp. 150-159, May 1995.

[4] S. M. Burns, “General condition for the decomposition of state holding elements,” in Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, pp. 48-57, Mar. 1996.

[5] J. Carmona, J. Cortadella and E. Pastor, “A structural encoding technique for the synthesis of asynchronous circuit,” in Proc. Second International Conference on Application of Concurrency to System Design (ICACSD), pp. 157-166, June 2001.

[6] R.-D. Chen and J.-M. Jou, “On synthesizing and decomposing asynchronous circuits from STG specification,” in Proc. International Conference on Next Decades of High Technologies, pp. 109-113, Nov. 1998.

[7] R.-D. Chen, J.-M. Jou, and Y.-H. Shiau, “An efficient method for the decomposition and resynthesis of speed-independent circuits,” in Proc. the Sixth International Conference on Electronics, Circuits and Systems, pp. 339-342, Sept. 1999.

[8] R.-D. Chen and J.-M. Jou, “STG-level decomposition and resynthesis of speed-independent circuits,” IEEE Transactions on Circuits & Systems, Part I, vol. 49, pp. 1751-1763, Dec. 2002.

[9] T.-A. Chu, Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications. PhD thesis, MIT Laboratory for Computer Science, June 1987.

[10] J. Cortadella, A. Yakovlev, L. Lavagano, and P. Vanbekbergen, “Designing asynchronous circuits from behavioral specifications with internal conflicts,” in Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, pp. 106-115, Nov. 1994.

[11] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, E. Pastor, and A. Yakovlev, “Decomposition and technology mapping of speed-independent circuits using Boolean relations,” in Proc. International Conference on Computer-Aided Design (ICCAD), Nov. 1997.

[12] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, “A region-based theory for state assignment in speed-independent circuits,” IEEE Transactions on Computer-Aided Design, vol. 16, pp. 793-812, Aug. 1997.

[13] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, “Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers,” IEICE Transactions on Information and Systems, vol. E80-D(3), pp. 315-325, Mar. 1997.

[14] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, E. Pastor, and A. Yakovlev, “Decomposition and technology mapping of speed-independent circuits using Boolean relations,” IEEE Transactions on Computer-Aided Design, vol. 18, pp. 1221-1236, Sept. 1999.

[15] A. Davis and K. Stevens, “The post office experience: design a large asynchronous chip,” in Proc. Twenty-Sixth International Conference on System Sciences, pp. 409-418, Jan. 1993.

[16] A. Davis, B. Coates, and K. Stevens, “Automatic synthesis of fast compact asynchronous control circuits,” in Asynchronous Design Methodologies (S. Furber and M. Edwards, editors), vol. A-28 of IFIP Transactions, pp. 193-207. Elsevier Science Publishers, 1993.

[17] J. C. Ebergen, “A formal approach to designing delay-insensitive circuits,” Distributed Computing, vol. 5, no. 3, pp. 107-119, 1991.

[18] M. Hack, “Analysis of production schemata by Petri nets,” Master’s thesis, Massachusetts Institute of Technology, Cambridge, Feb. 1972.

[19] C. A. R. Hoare, “Communicating sequential processes,” Communications of the ACM, vol. 21, pp. 666-677, Aug. 1978.

[20] D. A. Huffman, “The synthesis of sequential switching circuits,“ in Sequential Machines: Selected Papers (E. F. Moore, editor), Addison-Wesley, 1964.

[21] M. B. Josephs and J. T. Udding, “An overview of DI algebra,” in Proc. Hawaii International Conference on System Sciences (T. N. Mudge, V. Milutinovic, and L. Hunter, editors), vol. I, pp. 329-338, Jan. 1993.

[22] J.-M. Jou, R.-D. Chen, and K.-M. Lin, “Integrated synthesis of speed-independent asynchronous circuits,” in Proc. International Symposium on Circuits and Systems, pp. 1600-1603, June 1997.

[23] S. T. Jung and C. J. Myers, “Direct synthesis of timed asynchronous circuits,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 332-337, Nov. 1999.

[24] V. Khomenko, M. Koutny, and A. Yakovlev, “Detecting state coding conflicts in STGs using integer programming,” in Proc. 2002 Design, Automation and Test in Europe Conference and Exhibition (DATE’02), pp. 338-345, 2002.

[25] M. A. Kishinevsky, A. Y. Kondratyev, and A. R. Taubin, “Formal method for self-timed design,” in Proc. European Design Automation Conference, pp. 197-201, Feb. 1991.

[26] M. Kishinevsky, A. Kondratyev, A. Taubin, and V. Varshavsky, Concurrent Hardware: The Theory and Practice of Self-Timed Design. John Wiley and Sons, London, 1994.

[27] A. Kondratyev, M. Kishinevsky, J. Cortadella, L. Lavagno, and A. Yakovlev, “Technology mapping for speed-independent circuits: decomposition and resynthesis,” in Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, pp. 240-253, Apr. 1997.

[28] A. Kondratyev, J. Cortadella, M. Kishinevsky, L. Lavagno, A. Taubin, and A. Yakovlev, “Identifying state coding conflicts in asynchronous system specifications using Petri net unfoldings,” in Proc. International Conference on Application of Concurrency to System Design, Mar. 1998.

[29] A. Kondratyev, M. Kishinevsky, and A. Yakovlev, “Hazard-free implementation of speed-independent circuits,” IEEE Transactions on Computer-Aided Design, vol. 17, pp. 749-771, Sept. 1998.

[30] L. Lavagno, K. Keutzer, and A. Sangiovanni-Vincentelli, “Algorithms for synthesis of hazard-free asynchronous circuits,” in Proc. ACM/IEEE Design Automation Conference, pp. 302-308, 1991.

[31] L. Lavagno, C. W. Moon, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Solving the state assignment problem for signal transition graphs,” in Proc. ACM/IEEE Design Automation Conference, pp. 568-572, June 1992.

[32] L. Lavagno and A. Sangiovanni-Vincentelli, Algorithms for synthesis and testing of asynchronous circuits. Norwell, MA: Kluwer Academic Publishers, 1993.

[33] K.-J. Lin and C.-S. Lin, “On the verification of state-coding in STGs,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 118-122, Nov. 1992.

[34] K.-J. Lin, J.-W. Kuo, and C.-S. Lin, “Direct synthesis of hazard-free asynchronous circuits from STGs based on lock relation and MG-decomposition approach,” in Proc. European Design and Test Conference, pp. 178-183, Feb. 1994.

[35] A. J. Martin, “Compiling communicating processes into delay-insensitive VLSI circuits,” Distributed Computing, vol. 1, no. 4, pp. 226-234, 1986.

[36] T. H.-Y. Meng, R. W. Brodersen, and D. G. Messerschmitt, “Automatic synthesis of asynchronous circuits from high-level specifications,” IEEE Transactions on Computer-Aided Design, vol. 8, pp. 1185-1205, Nov. 1989.

[37] R. E. Miller, Switching Theory. Vol. II: Sequential Circuits and Machines. John Wiley and Sons, New York, 1965.

[38] C. W. Moon, P. R. Stephan, and R. K. Brayton, “Synthesis of hazard-free asynchronous circuits from graphical specifications,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 322-325, Nov. 1991.

[39] T. Murata, “Petri nets: properties, analysis, and applications,” Proceedings of the IEEE, vol. 77, pp. 541-580, Apr. 1989.

[40] C. Myers and T. H.-Y. Meng, “Synthesis of timed asynchronous circuits,” in Proc. International Conference on Computer Design (ICCD), pp. 279-282, Oct. 1992.

[41] S. M. Nowick and D. L. Dill, “Synthesis of asynchronous state machines using a local clock,” in Proc. International Conference on Computer Design (ICCD), pp. 192-197, Oct. 1991.

[42] S. M. Nowick, K. Y. Yun, and D. L. Dill, “Practical asynchronous controller design,“ in Proc. International Conference on Computer Design (ICCD), pp. 341-345, Oct. 1992.

[43] S. M. Nowick, Automatic Synthesis of Burst-Mode Asynchronous Controllers. PhD thesis, Stanford University, Department of Computer Science, Mar. 1993.

[44] S. M. Nowick, M. E. Dean, D. L. Dill, and M. Horowitz, “The design of a high-performance cache controller: a case study in asynchronous synthesis,” Integration, the VLSI journal, vol. 15, no. 3, pp. 241-262, Oct. 1993.

[45] S. M. Nowick and B. Coates, “UCLOCK: automated design of high-performance unclocked state machines,” in Proc. International Conference on Computer Design (ICCD), pp. 434-441, Oct. 1994.

[46] S.-B. Park and T. Nanya, “Synthesis of asynchronous circuits from signal transition graph specifications,“ IEICE Transactions on Information and Systems, vol. E80-D(3), pp. 326-335, Mar. 1997.

[47] E. Pastor and J. Cortadella, “An efficient unique state coding algorithm for signals transition graphs,” in Proc. International Conference on Computer Design (ICCD), pp. 174-177, Oct. 1993.

[48] E. Pastor, J. Cortadella, A. Kondratyev, and O. Roig, “Structural methods for the synthesis of speed-independent circuits,” IEEE Transactions on Computer-Aided Design, vol. 17, pp. 1108-1129, Nov. 1998.

[49] J. L. Peterson, Petri Net Theory and the Modeling of Systems. Prentice Hall, Englewood Cliffs, NJ, 1981.

[50] R. Puri and J. Gu, “A divide-and-conquer approach for asynchronous interface synthesis,” in Proc. Seventh International Symposium on High-Level Synthesis, pp. 118-125, 1994.

[51] M. Rem, “Trace theory and systolic computations,” in PARLE: Parallel Architectures and Languages Europe, Vol. I (J. W. de Bakker, A. J. Nijman, and P. C. Treleaven, editors), vol. 258 of Lecture Notes in Computer Science, pp. 14-33, Springer-Verlag, 1987.

[52] O. Roig, J. Cortadella, and E. Pastor, “Hierarchical gate-level verification of speed-independent circuits,” in Proc. Second Working Conference on Asynchronous Design Methodologies, pp. 129-137, May 1995.

[53] L. Y. Rosenblum and A. V. Yakovlev, “Signal graphs: from self-timed to timed ones,” in Proc. International Workshop on Timed Petri Nets, pp. 199-207, July 1985.

[54] A. Semenov, A. Yakovlev, E. Pastor, M. Pena, and J. Cortadilla, “Synthesis of speed-independent circuits from STG-unfolding segment,” in Proc. ACM/IEEE Design Automation Conference, pp. 16-21, June 1997.

[55] E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli, “SIS: A system for sequential circuit synthesis,” Technical Report UCB/ERL M92/41, U.C. Berkeley, May 1992.

[56] P. Siegel and G. De Micheli, “Decomposition methods for library binding of speed-independent asynchronous designs,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 558-565, Nov. 1994.

[57] S. H. Unger, Asynchronous Sequential Switching Circuits. Wiley-Interscience, John Wiley & Sons, Inc., New York, 1969.

[58] P. Vanbekbergen, F. Catthoor, G. Goossens, and H. De Man, “Optimized synthesis of asynchronous control circuits form graph-theoretic specifications,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 184-187, Nov. 1990.

[59] P. Vanbekbergen, G. Goossens, and H. De Man, “Specification and analysis of timing constraints in signal transition graphs,” in Proc. European Conference on Design Automation (EDAC), pp. 302-306, Mar. 1992.

[60] P. Vanbekbergen, B. Lin, G. Goossens, and H. De Man, “A generalized state assignment theory for transformations on signal transition graphs,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 112-117, Nov. 1992.

[61] V. I. Varshavsky, editor, Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1990.

[62] A. V. Yakovlev, “On limitations and extensions of STG model for designing asynchronous control circuits,” in Proc. International Conference on Computer Design (ICCD), pp. 396-400, Oct. 1992.

[63] C. Ykman-Couvreur, B. Lin, G. Goossens, and H. De Man, “Synthesis and optimization of asynchronous controllers based on extended lock graph theory,” in Proc. European Conference on Design Automation (EDAC), pp. 512-517, Feb. 1993.

[64] C. Ykman-Couvreur, B. Lin, and H. DeMan, “ASSASSIN: A synthesis system for asynchronous control circuits,” Reference manual, IMEC, 1995.

[65] C. Ykman-Couvreur and B. Lin, “Optimised state assignment for asynchronous circuit synthesis,” in Proc. Second Working Conference on Asynchronous Design Methodologies, pp. 118-127, May 1995.

[66] K. Y. Yun and D. L. Dill, “Automatic synthesis of 3D asynchronous state machines,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 576-580, Nov. 1992.

[67] K. Y. Yun, D. L. Dill, and S. M. Nowick, “Practical generalizations of asynchronous state machines,” in Proc. European Conference on Design Automation (EDAC), pp. 525-530, Feb. 1993.

[68] K. Y. Yun and D. L. Dill, “Unifying synchronous/asynchronous state machine synthesis,” in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 255-260, Nov. 1993.

[69] K. Y. Yun, Bill Lin, D. L. Dill, and S. Devadas, “Performance-driven synthesis of asynchronous controllers,“ in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 550-557, Nov. 1994.

[70] K. Y. Yun and D. L. Dill, “A high-performance asynchronous SCSI controller,” in Proc. International Conference on Computer Design (ICCD), pp. 44-49, Oct. 1995.

[71] K. Y. Yun, “Automatic synthesis of extended burst-mode circuits using generalized C-elements,” in Proc. European Design Automation Conference (EURO-DAC), pp. 290-295, Sept. 1996.