Resolution of Encoding Conflicts by Signal Insertion and Concurrency Reduction Based on STG Unfoldings

• Autorzy: Khomenko V. , Madalinski A. , Yakovlev A.
• Języki publikacji: EN

Abstrakty

EN

A combined framework for the resolution of encoding conflicts in STG unfoldings is presented, which extends previouswork by incorporating concurrency reduction in addition to signal insertion. Furthermore, a novel validity condition is proposed to justify these transformations. The method has been implemented in the CONFRES tool and applied to a number of case studies. The experimental results show that the combined framework enlarges the design space and allows for better exploration of the speed/area tradeoff.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 3
• Strony: 299--323
• Opis fizyczny: bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Khomenko V.

autor

Madalinski A.

autor

Yakovlev A.

• Newcastle University, Newcastle upon Tyne, NE1 7RU, United Kingdom,

Bibliografia

• [1] Bryant, R.: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35-8, 1986, 677-691.
• [2] Carmona, J., Cortadella, J.: State Encoding of Large Asynchronous Controllers, Proc. DAC'06, IEEE Computer Society Press, 2006.
• [3] Carmona, J., Cortadella, J., Pastor, E.: A Structural Encoding Technique for the Synthesis of Asynchronous Circuits, Fundamenta Informaticae, 50(2), 2002, 135-154.
• [4] Chu, T.-A.: Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications, Ph.D. Thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, 1987.
• [5] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: PETRIFY: a Tool for Manipulating Concurrent Specifications and Synthesis of Asynchronous Controllers, IEICE Transactions on Information and Systems, E80-D(3), 1997, 315-325.
• [6] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Automatic Handshake Expansion and Reshuffling Using Concurrency Reduction, Proc. HWPN'98, 1998.
• [7] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic Synthesis of Asynchronous Controllers and Interfaces, Springer-Verlag, 2002.
• [8] Dill, D.: Trace Theory for Automatic Heirarchical Verification of Speed-IndependentCircuits, Ph.D. Thesis, Carnegie Mellon University, 1987.
• [9] Esparza, J., RÖmer, S., Vogler,W.: An Improvement of McMillan's Unfolding Algorithm, Formal Methods in System Design, 20(3), 2002, 285-310.
• [10] Josephs, M.: An Analysis of Determinacy Using a Trace-TheoreticModel of Asynchronous Circuits, Proc. ASYNC'03, IEEE Computer Society Press, 2003.
• [11] Khomenko, V.: Model Checking Based on Prefixes of Petri Net Unfoldings, Ph.D. Thesis, School of Computing Science, University of Newcastle upon Tyne, 2003.
• [12] Khomenko, V.: Behaviour-Preserving Transition Insertions in Unfolding Prefixes, Proc. ATPN'07, Lecture Notes in Computer Science, Springer-Verlag, 2007.
• [13] Khomenko, V., Koutny,M., Yakovlev, A.: Detecting State Coding Conflicts in STG Unfoldings Using SAT, Fundamenta Informaticae, 62(2), 2004, 1-21.
• [14] Khomenko, V., Koutny, M., Yakovlev, A.: Logic Synthesis for Asynchronous Circuits Based on Petri Net Unfoldings and Incremental SAT, Fundamenta Informaticae, 70(1-2), 2006, 49-73.
• [15] Khomenko, V., Madalinski, A., Yakovlev, A.: Resolution of Encoding Conflicts by Signal Insertion and Concurrency Reduction Based on STG Unfoldings, Proc. ACSD'2006, IEEE Computer Society Press, 2006.
• [16] Kinniment, D., Gao, B., Yakovlev, A., Xia, F.: Towards asynchronous A-D conversion, Proc. ASYNC'00, IEEE Computer Society Press, 2000.
• [17] Lin, B., Ykman-Couvreur, C., Vanbekbergen, P.: A General State Graph Transformation Framework for Asynchronous Synthesis, Proc. EURO-DAC'94, IEEE Computer Society Press, 1994.
• [18] Madalinski, A., Bystrov, A., Khomenko, V., Yakovlev, A.: Visualization and Resolution of Coding Conflicts in Asynchronous Circuit Design, IEE Proceedings: Computers & Digital Techniques, 150(5), 2003, 285-293.
• [19] Pratt, V.: Modelling Concurrency with Partial Orders, International Journal of Parallel Programming, 15(1), 1986, 33-71.
• [20] Saito, H., Kondratyev, A., Cortadella, J., Lavagno, L., Yakovlev, A.: What is the Cost of Delay Insensitivity?, Proc. CAD'99, IEEE Computer Society Press, 1999.
• [21] Sch¨afer, M., Vogler, W.: Component Refinement and CSC Solving for STG Decomposition, Technical Report 2004-13, Institut f¨ur Informatik, Universit¨at Augsburg, 2004.
• [22] Verhoeff, T.: Analyzing Specifications for Delay-Insensitive Circuits, Proc. ASYNC'98, IEEE Computer Society Press, 1998.