Генерирование адресных последовательностей с заданной переключательной активностью и повторяемостью адресов

Цели. Решается задача разработки методологии генерирования адресных последовательностей с заданной переключательной активностью и повторяемостью адресов, широко используемых при тестировании современных вычислительных систем. Актуальность данной задачи заключается в том, что основной характеристикой различия для адресных последовательностей является переключательная активность как отдельных битов адресов, так и их последовательностей.
Методы. Представленные результаты основаны на универсальном методе генерирования квазислучайных последовательностей Соболя, эффективно используемых для формирования адресных тестовых последовательностей. В качестве исходной математической модели используется модификация указанного метода генерирования, предложенная Антоновым и Салеевым. Главная идея подхода, предлагаемого в настоящей работе, основана на применении для генерирования адресных последовательностей прямоугольных (m + k) × m порождающих матриц V произвольного ранга r.
Результаты. Определены основные свойства последовательностей, генерируемых в соответствии с новой математической моделью. Приведен ряд утверждений, обосновывающих требования к порождающим матрицам для обеспечения максимального периода формируемых последовательностей и кратности повторяемости используемых в них адресов. Решена задача синтеза последовательностей с заданными величинами переключательной активности F(A) и F(a_i). Показано, что для нахождения порождающей матрицы для генерирования таких последовательностей необходимо решить задачу разложения целого числа на слагаемые. Такое разложение представляет собой величину переключательной активности в (m+k)-ичной смешанной системе счисления, в которой веса разрядов представлены в виде степеней двойки от 2⁰ до 2^m+k-1, а значения цифр w(vi) лежат в диапазоне от 0 до m+k-1. На основе предлагаемых ограничений введено понятие диаграммы разложения целого числа, аналогичное диаграмме Юнга, и определена операция ее модификации.
Заключение. Предложенная математическая модель расширяет возможности генерирования тестовых адресных последовательностей с требуемыми значениями переключательной активности как тестовых наборов, так и их отдельных разрядов. Применение порождающих матриц не максимального ранга дает возможность формализации метода генерирования адресных последовательностей с четным повторением адресов.

1. Marwedel, P. Embedded System Design. Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things / P. Marwedel. – 4th ed. – Dortmund, Germany : Springer Nature, 2021. – 433 p.

2. Challenges in embedded memory design and test / E. J. Marinissen [et al.] // Proc. of Design, Automation and Test in Europe Conf. and Exhibition. DATE’05, Munich, Germany, 7–11 Mar. 2005. – Munich, 2005. – P. 722–727.

3. Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бестпринт, 2019. – 387 с.

4. Goor, A. J. Optimizing memory BIST Address Generator implementations / A. J. Goor, H. Kukner, S. Hamdioui // Proc. of the 2011 6th Intern. Conf. on Design & Technology of Integrated Systems in Nanoscale Era (DTIS), Athens, Greece, 6–8 Apr. 2011. – Athens, 2011. – P. 572–576.

5. Pomeranz, I. An adjacent switching activity metric under functional broadside tests / I. Pomeranz // IEEE Transaction on Computers. – 2013. – Vol. 62, no. 4. – P. 404–410.

6. Ярмолик, В. Н. Формирование адресных последовательностей с заданной переключательной активностью / В. Н. Ярмолик, Н. А. Шевченко // Информатика. – 2020. – № 1(17). – С. 47–62.

7. A test vector ordering technique for switching activity reduction during test operation / P. Girard [et al.] // Proc. Ninth Great Lakes Symp. on VLSI, Ypsilanti, MI, USA, 4–6 Mar. 1999. – Ypsilanti, 1999. – P. 24–27.

8. Wang, S. An automatic test pattern generator for minimizing switching activity during scan testing activity / S. Wang, S. K. Gupta // IEEE Transaction Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 8. – P. 954–968.

9. Design and analysis of low-transition address generator / S. Saravanan [et al.] // Proc. of 6th EAI Intern. Conf. ICAST 2018, Bahir Dar, Ethiopia, 5–7 Oct. 2018. – Bahir Dar, 2018. – P. 239–247.

10. Novel architecture design of address generators for BIST algorithms / P. A. Pavani [et al.] // Intern. J. of Science & Engineering Research. – 2016. – Vol. 7, no. 2. – P. 1484–1488.

11. Yarmolik, V. N. Address sequences / V. N. Yarmolik, S. V. Yarmolik // Automatic Control and Computer Sciences. – 2014. – Vol. 48, no. 4. – P. 207–213.

12. Singh, B. Address counter/generators for low power memory BIST / B. Singh, S. Narang, A. Khosla // Intern. J. of Computer Science (IJCSI). – 2011. – Vol. 8, iss. 4, no. 1. – P. 561–567.

13. Mrozek, I. Iterative antirandom testing / I. Mrozek, V. N. Yarmolik // J. of Electronic Testing: Theory and Applications. – 2012. – Vol. 9, no. 3. – P. 251–266.

14. Yarmolik, V. N. Generating modified Sobol sequences for multiple run march memory test / V. N. Yarmolik, S. V. Yarmolik // Automatic Control and Computer Sciences. – 2013. – Vol. 47, no. 5. – P. 242–247.

15. Robinson, J. Counting sequence / J. Robinson, M. Cohn // IEEE Transaction on Computers. – 1981. – Vol. C-30, no. 1. – P. 17–23.

16. Hayes, J. P. Generation of optimal transition count tests / J. P. Hayes // IEEE Transaction on Computers. – 1978. – Vol. C-27, no. 1. – P. 36–41.

17. Ярмолик, С. В. Квазислучайное тестирование вычислительных систем / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2013. – № 3(39). – С. 92–103.

18. Антонов, И. А. Экономичный способ вычисления ЛПτ последовательностей / И. А. Антонов, В. М. Салеев // Журнал вычислительной математики и математической физики. – 1979. – Т. 19, № 1. – С. 243–245.

19. Savage, C. A survey of combinatorial Gray code / C. Savage // SIAM Review. – 1997. – Vol. 39, no. 4. – P. 605–629.

20. Boyd, S. Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares / S. Boyd. – Cambridge, United Kingdom : University Printing House, 2018. – 463 p.

21. Shevchenko, M. Generation of test sequences with a given switching activity / M. Shevchenko // Proc. of XIV Conf. for Yong Researchers: Technical Science, Industrial Management, Borovets, Bulgaria, 10–13 Mar. 2021. – Borovets, 2021. – P. 14–17.

22. Ярмолик, В. Н. Неразрушающие тесты с четным повторением адресов для тестирования запоминающих устройств / В. Н. Ярмолик, И. Мрозек, В. А. Леванцевич, Д. В. Деменковец // Информатика. – 2021. – № 3(18). – С. 18–35.

23. Кнут, Д. Искусство программирования. Т. 4А. Комбинаторные алгоритмы. Ч. 1 / Д. Кнут. – М. : Диалектика-Вильямс, 2013. – 960 c.

24. McKay, J. K. S. Algorithm 371: Partitions in natural order [A1] / J. K. S. McKay // Communications of the ACM. – 1970. – Vol. 13, no. 1. – P. 52.

25. Stojmenović, I. Fast algorithms for generating integer partitions / I. Stojmenović, A. Zoghbi // Intern. J. of Computer Mathematics. – 1998. – Vol. 70, no. 2. – P. 319–332.

26. Nicolaidis, M. Theory of transparent BIST for RAMs / M. Nicolaidis // IEEE Transactions on Computers. – 1996. – Vol. 45, no. 10. – P. 1141–1156.

27. Hellebrand, S. Symmetric Transparent BIST for RAMs / S. Hellebrand, H.-J. Wunderlich, V. N. Yarmolik // Proc. of IEEE Design, Automation and Test in Europe Conf. (DATA’99), Munich, Germany, 9–12 Mar. 1999. – Munich, 1999. – P. 702–707.