informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2022-19-3-7-24inform-1177Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNГенерирование адресных последовательностей с заданной переключательной активностью и повторяемостью адресовGeneration of address sequences with specified switching activity and address repeatabilityЯрмоликВ. Н.YarmolikV. N.

Ярмолик Вячеслав Николаевич, доктор технических наук, профессор

ул. П. Бровки, 6, Минск, 220013

Vyacheslav N. Yarmolik, D. Sc. (Eng.), Professor

st. P. Brovki, 6, Minsk, 220013

yarmolik10ru@yahoo.comШевченкоН. А.ShevchenkoN. A.

Шевченко Николай Алексеевич, студент

Каролиненплац, 5, Дармштадт, 64289

Nikolai А. Shevchenko, Student

Karolinenplatz, 5, Darmstadt, 64289

nik.sh.de@gmail.comЛеванцевичВ. А.LevantsevichV. А.

Леванцевич Владимир Александрович, магистр технических наук, старший преподаватель

ул. П. Бровки, 6, Минск, 220013

Vladimer A. Levantsevich, M. Sc. (Eng.), Senior Lecture

st. P. Brovki, 6, Minsk, 220013

lvn@bsuir.byДеменковецД. В.DemenkovetsD. V.

Деменковец Денис Викторович, магистр технических наук, старший преподаватель

ул. П. Бровки, 6, Минск, 220013

Denis V. Demenkovets, M. Sc. (Eng.), Senior Lecture

st. P. Brovki, 6, Minsk, 220013

demenkovets@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsДармштадтский технический университетDarmstadt Technical University202202032022193724Copyright © Ярмолик В.Н., Шевченко Н.А., Леванцевич В.А., Деменковец Д.В., 20222022Ярмолик В.Н., Шевченко Н.А., Леванцевич В.А., Деменковец Д.В.Yarmolik V.N., Shevchenko N.A., Levantsevich V.А., Demenkovets D.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1177

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

Objectives. The problem of developing a methodology for generating address sequences with a given switching activity and repeatability of addresses widely used in testing modern computing systems is being solved. The relevance of this problem lies in the fact that the main characteristic of the difference and their effectiveness for address sequences is the switching activity of both individual address bits and their sequences.Methods. Presented results are based on a universal method for generating quasi-random Sobol sequences, which are effectively used to generate targeted test sequences. As an initial mathematical model, a modification of the indicated generation method proposed by Antonov and Saleev is used. The main idea of proposed approach is based on the use of rectangular (m + k) × m generating matrices V of arbitrary rank r to generate address sequences.Results. The main properties of sequences generated in accordance with the new mathematical model are determined. A number of statements are given that substantiate the requirements for generator matrices to ensure the maximum period of generated sequences and the multiplicity of repetition of used addresses. The problem of synthesizing the sequences with given values of switching activity F(A) and F(ai) is solved. It is shown that in order to find a generating matrix for generating such sequences, it is necessary to solve the problem of decomposing an integer into terms. This decomposition represents the value of switching activity in the (m + k)-ary mixed number system, in which the weights of the digits are represented as powers of two from 20 to 2m+k-1, and the values of the digits w(vi) lie in the range from 0 to m+k-1. On the basis of proposed restrictions, the notion of an integer decomposition diagram similar to the Young diagram is introduced, and the operation of its modification is defined.Conclusion. The proposed mathematical model expands the possibilities of generating test address sequences with the required values of switching activity of both test sets and their individual bits. The use of generating matrices of non-maximal rank makes it possible to formalize the method of generating address sequences with even repetition of addresses.

тестирование вычислительных системадресные последовательностипереключательная активностьсимметричные последовательностипоследовательности с четным повторением адресовcomputer systems testingaddress sequencesswitching activitysymmetric sequencessequences with even repeating addressesReferencesMarwedel, 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.Marwedel, P. Embedded System Design. Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things. 4th edition. Dortmund, Springer Nature, 2021, 433 p.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.Marinissen E. J., Prince B., Keitel-Schulz D., Zorian Y. Challenges in embedded memory design and test. Proceedings of Design, Automation and Test in Europe Conference and Exhibition. DATE’05, Munich, Germany, 7– 11 March 2005. Munich, 2005, pp. 722–727.Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бестпринт, 2019. – 387 с.Yarmolik V. N. Control’ i diagnostika vuchislitel’nuch system. Computer Systems Testing and Diagnoses. Minsk, Bestprint, 2019, 387 p. (In Russ.).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.Goor A. J., Kukner H., Hamdioui S. Optimizing memory BIST Address Generator implementations. Proceedings of the 2011 6th International Conference on Design & Technology of Integrated Systems in Nanoscale Era (DTIS), Athens, Greece, 6–8 April 2011. Athens, 2011, pp. 572–576.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.Pomeranz I. An adjacent switching activity metric under functional broadside tests. IEEE Transaction on Computers, 2013, vol. 62, no. 4, pp. 404–410.Ярмолик, В. Н. Формирование адресных последовательностей с заданной переключательной активностью / В. Н. Ярмолик, Н. А. Шевченко // Информатика. – 2020. – № 1(17). – С. 47–62.Yarmolik V. N., Shevchenko N. A. Generation of address sequences with a given switching activity. Informatika [Informatics], 2020, no. 1(17), pp. 47–62 (In Russ.).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.Girard P., Guiller L., Landrault С., Pravossoudovitch S. A test vector ordering technique for switching activity reduction during test operation. Proceedings Ninth Great Lakes Symposium on VLSI, Ypsilanti, MI, USA, 4–6 March 1999. Ypsilanti, 1999, pp. 24–27.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.Wang S., Gupta S. K. An automatic test pattern generator for minimizing switching activity during scan testing activity. IEEE Transaction Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 8, pp. 954–968.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.Saravanan S., Hailu M., Gouse G. M., Lavanya M., Vijaysai R. Design and analysis of low-transition address generator. Proceedings of 6th EAI International Conference ICAST 2018, Bahir Dar, Ethiopia, 5–7 October 2018. Bahir Dar, 2018, pp. 239–247.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.Pavani P. A., Anitha G., Bhavana J., Raj J. P. Novel architecture design of address generators for BIST algorithms. International Journal of Science & Engineering Research, 2016, vol. 7, no. 2, pp. 1484–1488.Yarmolik, V. N. Address sequences / V. N. Yarmolik, S. V. Yarmolik // Automatic Control and Computer Sciences. – 2014. – Vol. 48, no. 4. – P. 207–213.Yarmolik V. N., Yarmolik S. V. Address sequences. Automatic Control and Computer Sciences, 2014, vol. 48, no. 4, pp. 207–213.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.Singh B., Narang S., Khosla A. Address counter/generators for low power memory BIST. International Journal of Computer Science (IJCSI), 2011, vol. 8, iss. 4, no. 1, pp. 561–567.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.Mrozek I., Yarmolik V. N. Iterative antirandom testing. Journal of Electronic Testing: Theory and Applications, 2012, vol. 9, no. 3, pp. 251–266.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.Yarmolik V. N., Yarmolik S. V. Generating modified Sobol sequences for multiple run march memory test. Automatic Control and Computer Sciences, 2013, vol. 47, no. 5, pp. 242–247.Robinson, J. Counting sequence / J. Robinson, M. Cohn // IEEE Transaction on Computers. – 1981. – Vol. C-30, no. 1. – P. 17–23.Robinson J., Cohn M. Counting sequence. IEEE Transaction on Computers, 1981, vol. C-30, no. 1, pp. 17–23.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.Hayes J. P. Generation of optimal transition count tests. IEEE Transaction on Computers, 1978, vol. C-27, no. 1, pp. 36–41.Ярмолик, С. В. Квазислучайное тестирование вычислительных систем / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2013. – № 3(39). – С. 92–103.Yarmolik V. N., Yarmolik S. V. Quasi-random testing of computer systems. Informatika [Informatics], 2013, no. 3(39), pp. 92–103 (In Russ.).Антонов, И. А. Экономичный способ вычисления ЛПτ последовательностей / И. А. Антонов, В. М. Салеев // Журнал вычислительной математики и математической физики. – 1979. – Т. 19, № 1. – С. 243–245.Antonov I. A., Saleev V. M. An economical way to compute LP sequences. Journal of Mathematics and Mathematical Physics, 1979, vol. 19, no. 1, pp. 243–245.Savage, C. A survey of combinatorial Gray code / C. Savage // SIAM Review. – 1997. – Vol. 39, no. 4. – P. 605–629.Savage C. A survey of combinatorial Gray code. SIAM Review, 1997, vol. 39, no 4, pp. 605–629.Boyd, S. Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares / S. Boyd. – Cambridge, United Kingdom : University Printing House, 2018. – 463 p.Boyd S. Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares. Cambridge, United Kingdom, University Printing House, 2018, 463 p.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.Shevchenko M. Generation of test sequences with a given switching activity. Proceedings of XIV Conference for Yong Researchers: Technical Science, Industrial Management, Borovets, Bulgaria, 10–13 March 2021. Borovets, 2021, pp. 14–17.Ярмолик, В. Н. Неразрушающие тесты с четным повторением адресов для тестирования запоминающих устройств / В. Н. Ярмолик, И. Мрозек, В. А. Леванцевич, Д. В. Деменковец // Информатика. – 2021. – № 3(18). – С. 18–35.Yarmolik V. N., Mrozek I., Levantsevich V. A., Demenkovets D. V. Transparent memory tests with even repeating addresses for storage devices. Informatika [Informatics], 2021, no. 3(18), pp. 18–35 (In Russ.).Кнут, Д. Искусство программирования. Т. 4А. Комбинаторные алгоритмы. Ч. 1 / Д. Кнут. – М. : Диалектика-Вильямс, 2013. – 960 c.Knuth D. Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1. 1st edition. Addison-Wesley Professional, 2011, 912 р.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.McKay J. K. S. Algorithm 371: Partitions in natural order [A1]. Communications of the ACM, 1970, vol. 13, no. 1, pp. 52.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.Stojmenović I., Zoghbi A. Fast algorithms for generating integer partitions. International Journal of Computer Mathematics, 1998, vol. 70, no. 2, pp. 319–332.Nicolaidis, M. Theory of transparent BIST for RAMs / M. Nicolaidis // IEEE Transactions on Computers. – 1996. – Vol. 45, no. 10. – P. 1141–1156.Nicolaidis M. Theory of transparent BIST for RAMs. IEEE Transactions on Computers, 1996, vol. 45, no. 10, pp. 1141–1156.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.Hellebrand S., Wunderlich H.-J., Yarmolik V. N. Symmetric Transparent BIST for RAMs. Proceedings of IEEE Design, Automation and Test in Europe Conference (DATA’99), Munich, Germany, 9–12 March 1999. Munich, 1999, pp. 702–707.

The authors declare that there are no conflicts of interest present.