Genetic algorithm for constructing functional tests of arithmetic logic units

Authors

DOI:

https://doi.org/10.15587/1729-4061.2014.22407

Keywords:

digital device, system-on-chip, built-in self-test, functional test, genetic algorithm

Abstract

A genetic algorithm for constructing functional-level test sequences for built-in self-test schemes of arithmetic logic units of modern systems-on-chip is proposed in the paper. The idea of the method lies in the automated construction of functional tests, which are arithmetic operands, allowing maximum coverage of the selected type of damages of the structural level, at which test is considered as a binary set. In fact, providing input sets and checking reactions are performed directly by the arithmetic logic unit. Since the task concerns two-level representation of the digital device with an appropriate representation of input tests, two types of genetic operations, namely binary and arithmetic are used in the method. Inversion of input/output lines of arithmetic logic unit is selected as a functional level coverage metrics.Approbation of the proposed algorithm is performed for arithmetical division. It is experimentally shown that the functional test with the length of seven sets allows covering about 90% of constant structural-level damages. The test compression level with respect to the structural level is more than 100 times.ф

Author Biographies

Юрий Александрович Скобцов, Donetsk National Technical University Artema str., 58, Donetsk, Ukraine, 83001

Dr. of Sc., Professor

Head of Department of Automatic Control Systems

Дмитрий Евгеньевич Иванов, Institute of Applied Mathematics and Mechanics NAS of Ukraine R. Luxemburg str., 74, Donetsk, Ukraine, 83114

Dr. of Sc., Associative Professor

Senior scientific researcher in Theory Control System Department

Вадим Юрьевич Скобцов, Institute of Applied Mathematics and Mechanics NAS of Ukraine R. Luxemburg str., 74, Donetsk, Ukraine, 83114

PhD, Associative Professor

Head of Department of Discrete Mathematics and Applied Algebra

References

  1. ITRS 2010 technology roadmap [Electronic resource]. – available at: –http://www.itrs.net/Links/2010ITRS/Home2010.htm/. – Загл. с экрана. – (1.06.2013).
  2. Rajski, J. Arithmetic Built-in Self-test for Embedded Systems [Text] / J. Rajski, J. Tyszer. – Prentice Hall:Pearson Professional Education, 1997. – 256 p.
  3. Иванов, Д. Е. Генетические алгоритмы построения входных идентифицирующих последовательностей цифровых устройств [Text] / Д. Е. Иванов. − Донецк, 2012. − 240 с.
  4. Hamzaoglu, I. Test Set Compaction Algorithms for Combinational Circuits [Текст] / I. Hamzaoglu, H. Patel // Proceedings of the International Conference on CAD (ICCAD), 1998. – P. 283–289.
  5. Kruus, H. Defect-oriented BIST quality analysis [Text] / H. Kruus, R. Ubar, J. Raik // 12th Biennial Baltic Electronics Conference (BEC), 2010. – P. 153–156.
  6. Dorsch, R. Reusing scan chains for test pattern decompression [Text] / R. Dorsch, H.-J. Wunderlich // Proc. of Int. Test Conf., May 29 - Jun. 1, 2001. – P. 124–132.
  7. Novak, O. Test pattern decompression using a scan chain [Text] / O. Novak, J. Nosek // Proc. IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, 24-26 Oct. 2001. – P. 110–115.
  8. Goldberg, D. E. Genetic Algorithm in Search, Optimization, and Machine Learning [Text] / D. E. Goldberg. − Boston, MA:Addison-Wesley Longman Publishing Co. – 1989. – 412 p.
  9. Logofătu, D. Efficient Evolutionary Approach for the Test Compaction Problem [Text] / D. Logofătu // 9th International Conference on development and application systems, 2008. – P. 144–148.
  10. Ubar, R. HyFBIST: Hybrid Functional Built-In Self-Test in Microprogrammed Data-Paths of Digital Systems [Text] / R. Ubar, N. Mazurova, J. Smahtina, E. Orasson, J. Raik // Int. Conference MIXDES. – 2004. – P. 497–502.
  11. Skobtsov, Y. A. Evolutionary approach to the functional test generation for digital circuits [Text] / Y. A. Skobtsov, D. E. Ivanov, V. Y. Skobtsov, R. Ubar // In Proc. of 9th Biennial Baltic Electronics Conf., BEC 2004 (Tallinn, Oct. 2004).- Tallinn Univ. of Techn., 2004. – P. 229–232.
  12. Whitley, D. A Genetic Algorithm Tutorial [Text] / Darrell Whitley // Statistics and Computting. – 1994. – №4. – P. 65–85.
  13. Touba, N. A. Test point insertion based on path tracing [Text] / N. A. Touba, E. J. McCluskey // In Proc. of IEEE VLSI Test Symposium, 1996. – P. 2–8.
  14. ITRS 2010 technology roadmap (2010). Available at:http://www.itrs.net/Links/2010ITRS/Home2010.htm.
  15. Rajski, J., Tyszer, J. (1997). Arithmetic Built-in Self-test for Embedded Systems. Prentice Hall:Pearson Professional Education, 256.
  16. Ivanov, D. E. (2012). Geneticheskie algoritmy postroeniya vxodnyx identificiruyushhix posledovatel’nostej cifrovyx ustrojstv. Doneck, 240.
  17. Hamzaoglu, I., Patel, H. (1998). Test Set Compaction Algorithms for Combinational Circuits. Proceedings of the International Conference on CAD (ICCAD), 283–289.
  18. Kruus, H., Ubar, R., Raik, J. (2010). Defect-oriented BIST quality analysis.12th Biennial Baltic Electronics Conference (BEC), 153–156.
  19. Dorsch, R., Wunderlich, H.-J. (2001). Reusing scan chains for test pattern decompression, 124–132.
  20. Novak, O., Nosek, O. (2001). Test pattern decompression using a scan chain Proc. IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, 110–115.
  21. Goldberg, D. E. (1989). Genetic Algorithm in Search, Optimization, and Machine Learning. Boston, MA:Addison-Wesley Longman Publishing Co, 412.
  22. Logofătu, D. (2008) Efficient Evolutionary Approach for the Test Compaction Problem. 9th International Conference on development and application systems, 144–148.
  23. Ubar, R., Mazurova, N., Smahtina, J., Orasson, E., Raik, J. (2004). HyFBIST: Hybrid Functional Built-In Self-Test in Microprogrammed Data-Paths of Digital Systems. Int. Conference MIXDES, 497–502.
  24. Skobtsov, Y. A., Ivanov, D. E., Skobtsov, V. Y., Ubar, R. (2004). Evolutionary approach to the functional test generation for digital circuits. Tallinn Univ. of Techn., 229–232.
  25. Whitley, D. A. (1994). Genetic Algorithm Tutorial. Statistics and Computting, 4, 65–85.
  26. Touba, N. A., McCluskey, E. J. (1996). Test point insertion based on path tracing. In Proc. of IEEE VLSI Test Symposium, 2–8.

Downloads

Published

2014-04-18

How to Cite

Скобцов, Ю. А., Иванов, Д. Е., & Скобцов, В. Ю. (2014). Genetic algorithm for constructing functional tests of arithmetic logic units. Eastern-European Journal of Enterprise Technologies, 2(9(68), 9–13. https://doi.org/10.15587/1729-4061.2014.22407

Issue

Vol. 2 No. 9(68) (2014): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2014 Юрий Александрович Скобцов, Дмитрий Евгеньевич Иванов, Вадим Юрьевич Скобцов

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.