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

Цели. Решается задача разработки методологии генерирования адресных последовательностей с заданной переключательной активностью и повторяемостью адресов, широко используемых при тестировании современных вычислительных систем. Актуальность данной задачи заключается в том, что основной характеристикой различия для адресных последовательностей является переключательная активность как отдельных битов адресов, так и их последовательностей.
Методы. Представленные результаты основаны на универсальном методе генерирования квазислучайных последовательностей Соболя, эффективно используемых для формирования адресных тестовых последовательностей. В качестве исходной математической модели используется модификация указанного метода генерирования, предложенная Антоновым и Салеевым. Главная идея подхода, предлагаемого в настоящей работе, основана на применении для генерирования адресных последовательностей прямоугольных (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.