Avoiding Irreducible CSC Conflicts by Internal Communication

• Autorzy: Wist D. , Wollowski R. , Schaefer M. , Vogler W.
• Języki publikacji: EN

Abstrakty

EN

Resynthesis of handshake specifications obtained e.g. from BALSA or TANGRAM with speed-independent logic synthesis from STGs is a promising approach. To deal with state-space explosion,we suggested STG decomposition; a problemis that decomposition can lead to irreducible CSC conflicts. Here, we present a new approach to solve such conflicts by introducing internal communication between the components. We give some first, very encouraging results for very large STGs concerning synthesis time and circuit area.

Słowa kluczowe

EN

STG; decomposition; state-space explosion; CSC; resynthesis; handshake

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 95, nr 1
• Strony: 1--29
• Opis fizyczny: Bibliogr. 28 poz., wykr.

Twórcy

autor

Wist D.

autor

Wollowski R.

autor

Schaefer M.

autor

Vogler W.

• Hasso-Plattner-Institut, P.O. Box 90 04 60, 14440 Potsdam, Germany,

Bibliografia

• [1] André, C.: Structural transformations giving B-equivalent PT-nets, Applications and Theory of Petri Nets (Pagnoni, Rozenberg, Eds.), Informatik-Fachber. 66, 14-28. Springer, 1983.
• [2] Bardsley, A., Edwards, D. A.: The BALSA asynchronous circuit synthesis system, FDL2000: Forum on Design Languages. European Electronic Chips and Systems Design Initiative (ECSI), 2000.
• [3] van Berkel, C. H. K., Josephs,M. B., Nowick, S.M.: Scanning the technology: Applications of asynchronous circuits, Proceedings of the IEEE, 87, 1999.
• [4] van Berkel, K.: Handshake circuits: an asynchronous architecture for VLSI programming, Cambridge University Press, New York, NY, USA, 1993, ISBN 0-521-45254-6.
• [5] Berthelot, G.: Transformations and decompositions of nets, Petri Nets: Central Models and Their Properties (W. Brauer, et al., Eds.), Lect. Notes Comp. Sci. 254, 359-376. Springer, 1987.
• [6] Carmona, J., Colom, J.-M., Cortadella, J., Garcia-Valles, F.: Synthesis of Asynchronous Controllers using Integer Linear Programming, IEEE Trans. on CAD of Integrated Circuits and Systems, 25(9), 2006, 1637-1651.
• [7] Carmona, J., Cortadella, J.: Encoding Large Asynchronous Controllers With ILP Techniques, IEEE Trans. on CAD of Integrated Circuits and Systems, 27(1), 2008, 20-33.
• [8] Chu, T.-A.: Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications, Ph.D. Thesis, MIT, 1987.
• [9] Cortadella, J., Kishinevsky,M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic Synthesis of Asynchronous Controllers and Interfaces, Springer, 2002.
• [10] Ebergen, J.: Arbiters: an exercise in specifying and decomposing asynchronously communicating components, Sci. of Computer Programming, 18, 1992, 223-245.
• [11] Edwards, D., Bardsley, A.: BALSA: an AsynchronousHardware Synthesis Language, The Computer Journal, 45(1), 2002, 12-18.
• [12] van Gageldonk, H., van Berkel, K., Peeters, A., Baumann, D., Gloor, D., Stegmann, G.: An Asynchronous Low-Power 80C51 Microcontroller, ASYNC '98, IEEE, 1998, ISBN 0-8186-8392-9.
• [13] Kapoor, H. K., Josephs, M. B.: Decomposing specifications with concurrent outputs to resolve state coding conflicts in asynchronous logic synthesis, DAC '04: Proceedings of the 41st annual conference on Design automation, ACM, New York, USA, 2004.
• [14] Karaki, N., Nanmoto, T., Ebihara, H., Utsunomiya, S., Inoue, S., Shimoda, T.: A flexible 8b asynchronous microprocessor based on low-temperature poly-silicon TFT technology, ISSCC '05: Proceedings of the Solid-State Circuits Conference, 2005, Seiko Epson Corp., Nagano, Japan, 2005.
• [15] Khomenko, V., Koutny, M., Yakovlev, A.: Logic Synthesis for Asynchronous Circuits Based on Petri Net Unfoldings and Incremental SAT, ACSD 2004 (K. M., P. Darondeau, Eds.), IEEE, 2004.
• [16] Khomenko, V., Schaefer, M.: Combining Decomposition and Unfolding for STG Synthesis, ATPN '07: Applications and Theory of Petri Nets and Other Models of Concurrency, Lect. Notes Comp. Sci. 4024, 2007.
• [17] Reisig, W.: Petri Nets, EATCS Monographs on Theoretical Computer Science 4, Springer, 1985.
• [18] Schaefer, M.: DESIJ - A tool for decomposition, Technical Report 2007-11, University of Augsburg, http://www.informatik.uni-augsburg.de/de/forschung/reports/, 2007.
• [19] Schaefer, M., Vogler, W.: Component Refinement and CSC Solving for STG Decomposition, Theoret. Comput. Sci., 388(1-3), 2007, 243-266.
• [20] Schaefer, M., Vogler,W., Jančar, P.: Determinate STG Decomposition of Marked Graphs, ATPN 05 (G. Ciardo, P. Darondeau, Eds.), Lect. Notes Comp. Sci. 3536, 365-384. Springer, 2005.
• [21] Sokolov, D., Yakovlev, A.: Clockless Circuits and System Synthesis, IEE Proceedings - Computers Digital Techniques, 152, 2005.
• [22] Vanbekbergen, P., Goossens, G., Catthoor, F., Man, H. J. D.: Optimized synthesis of asynchronous control circuits fromgraph-theoretic specifications, Proceedings of IEEE Transactions on CAD of Integrated Circuits and Systems, 1992.
• [23] Vogler, W., Kangsah, B.: Improved Decomposition of Signal Transition Graphs, Fundamenta Informaticae, 76, 2006, 161-197.
• [24] Vogler, W., Wollowski, R.: Decomposition in Asynchronous Circuit Design, Concurrency and Hardware Design (J. Cortadella, et al., Eds.), Lect. Notes Comp. Sci. 2549, 152 - 190. Springer, 2002.
• [25] Wist, D., Wollowski, R.: STG Decomposition: Avoiding Irreducible CSC Conflicts by Internal Communication, Technical Report 20, HPI, University of Potsdam, http://www.hpi.unipotsdam. de/forschung/publikationen/technische berichte.html, 2007.
• [26] Wollowski, R., Beister, J.: Comprehensive Causal Specification of Asynchronous Controller and Arbiter Behaviour, Hardware Design and Petri Nets (A. Yakovlev, L. Gomes, L. Lavagno, Eds.), Kluwer Academic Publishers, 2000.
• [27] Yakovlev, A., Petrov, A.: Petri Nets and Asynchronous Bus Controller Design, ICATPN'90: International Conference on Application and Theory of Petri Nets, Paris, 1990.
• [28] Yoneda, T., Onda, H.,Myers, C.: Synthesis of Speed Independent Circuits Based on Decomposition, ASYNC 2004, IEEE, 2004.