يک مدل سطح بالا برای وارسی خواص CTL در طرح توصيف شده توسط VHDL
محورهای موضوعی : مهندسی برق و کامپیوتربيژن عليزاده 1 * , زین العابدین نوابی 2
1 - دانشگاه تهران
2 - دانشگاه تهران
کلید واژه: توابع انتقال حالتحلکننده معادلات صحيحمعادلات چندجملهای با متغيرهای صحيحBDD و Boolean Satisfiability ,
چکیده مقاله :
در اين مقاله قصد داريم مدل سطح بالايي بر پاية معادلات چندجملهاي با متغيرهاي صحيح ارائه دهيم كه مناسب براي وارسي خواص بر پاية CTL (Computational Temporal Logic) ميباشد. اكثر ابزارهاي وارسي از ساختمان دادههاي سطح پاييني مانند BDD استفاده ميكنند و اين ساختمان دادهها به علت نياز به حافظه زياد، قابل اعمال به بخش مسير داده از يك طرح نميباشند، در حالي كه مدل سطح بالاي پيشنهادی در اين مقاله قادر است بخشهاي مسير داده و كنترلر را با هم مورد ارزيابي قرار دهد. ضمن اينكه روش پيشنهادي به گونهاي است كه نياز به حل صريح معادلات نميباشد و اين كار توسط عمليات جايگزيني و سادهسازي انجام ميگيرد. در انتها نتايج كارمان با ابزار VIS، بعنوان يك ابزار وارسي بر پاية BDD، مقايسه ميگردند.
This paper describes the use of polynomial integer equations for high level model of digital circuits for property checking formal verification at this level. Most formal verification methods use low-level representations of a design like BDDs. BDD operations are not applicable to a large datapath because of large CPU time and memory usage. In our method, a behavioral state machine is represented by a list of integer equations, and RT level properties are directly applied to this representation. Furthermore, this method is applied to circuits without having to separate their data and control sections. For this implementation, we use a canonical form of integer equations, which simplifies equations instead of solving them. This paper compares our results with those of the VIS verification tool that is a BDD based program
[1] R. P. Kurshan, "Formal verification in a commercial setting," in Proc. Design Automation Conf., pp. 258-262, Jun. 1997.
[2] S. Devadas, H. T. Ma, and A. R. Newton, "On the verification of sequential machines at differing levels of abstraction," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 6, pp. 713-722, Jun. 1988.
[3] M. Yoeli, Formal Verification of Hardware Design, IEEE Computer Society Press, Los Alamos, NM, 1990.
[4] P. Camurati and P. Prinetto, "Formal verification of hardware correctness," IEEE Computer, vol. 21, no. 7, pp. 8-19, Jul. 1988.
[5] A. Gupta, S. Malik, and P. Ashar, "Toward formalizing a validation methodology using simulation coverage," in Proc. IEEE Design Automation Conf., pp. 740-745, Jun. 1997.
[6] R. Eastham and K. Thirunarayan, "Proof strategies for hardware verification," in Proc. of National Aerospace and Electronics Conf. (NAECON), vol. 2, pp. 451-458, May 1996.
[7] G. Cabodi, P. Camurati, and F. Corno, "Sequential circuit diagnosis based on formal verification techniques," in Proc. IEEE Int. Test Conf., pp. 187-196, Sep. 1992.
[8] K. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, Boston, 1993.
[9] J. Burch, E. Clarke, K. McMillan, and D. Dill, "Symbolic model checking: 1020 states and beyond," in Proc. of the Fifth Annual IEEE Symp. on Logic in Computer Science, pp. 428-439, Jun. 1990.
[10] M. C. McFarland, "Formal verification of sequential hardware," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 5, pp. 633-645, May 1993.
[11] C. Kern and M. R. Greenstreet, "Formal verification in hardware design," ACM Trans. on Design Automation of Electronic Systems, vol. 4, no. 2, pp. 123-193, Apr. 1999.1. Register transfer level 2. Symbolic simulation
. [12] J. Burch, E. Clarke, D. Long, K. McMillan, and D. Dill, "Symbolic model checking for sequential circuit verification," IEEE Trans. Computer Aided Design, vol. 13, no. 4, pp. 401-424, Apr. 1994.
[13] J. R. Burch, E. M. Clarke, and K. L. McMillan, "Sequential circuit verification using symbolic model checking," in Proc. 27th ACM/IEEE Design Automation Conf., pp. 46-51, 1990.
[14] H. Touati, H. Savoj, and B. Lin, "Implicit state enumeration of finite state machines using BDD’s," in Proc. of the 2th Int. Conf. on Computer Aided Design, pp. 130-133, Nov. 1990.
[15] A. Biere, A. Cimatti, E. M. Clarke, M. Fujita, and Y. Zhu, "Symbolic model checking using SAT procedures instead of BDDs," in Proc. of Design Automation Conf., pp. 317-320, Jun. 1999.
[16] R. Drechsler, Formal Verification of Circuits, Kluwer Academic Publishers, 2000.
[17] C. Y. Huang and K. T. Cheng, "Assertion checking by combined word-level ATPG and modular arithmetic constraint-solving techniques," in Proc. of Design Automation Conf., pp. 118-123,Jun. 2000.
[18] F. Fallah, S. Devadas, and K. Keutzer, "Functional vector generation for HDL models using linear programming and 3-satisfiability," in Proc. of 35th DAC, pp. 528-533, Jun. 1998.
[19] F. Fallah, Coverage Directed Validation of Hardware Models, Ph.D.Thesis, MIT, 1999.
[20] R. Brinkmann and R. Drechsler, "RTL-datapath verification using integer linear programming, " in Proc. of IEEE VLSI Design’01 & Asia and South Pacific Design Automation Conf., pp. 741-746, Bangalore, Jan. 2002.
[21] E. Clarke and E. Emerson, "Design and synthesis of synchronization skeletons using branching time temporal logic," in Logic of Programs Workshop, pp. 52-71, 1981.
[22] E. Clarke, R. Enders, and T. Filkorn, "Exploiting symmetry in temporal logic model checking," Formal Methods in System Design, vol. 9, no. 2, pp. 77-104, 1996.
[23] I. Beer, S. Ben-David, C. Eisner, and A. Landver, "RuleBase: an industry-oriented formal verification tool," in Proc. of the 33rd Design Automation Conf., pp. 655-660, Las Vegas, 1996.
[24] R. K. Brayton, A. Sangiovanni, A. Aziz, et al., "VIS: A system for verification and synthesis," in Proc. of the 8th Int. Conf. on Computer Aided Verification, pp. 428-432, 1996.
[25] J. C. Corbett and George S. Avrunin, "Using integer programming to verify general safety and liveness properties," in Journal of Formal Methods in System Design, vol. 6, no. 1, pp. 97-123, Jan. 1995.