informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2021-18-3-18-35inform-1137Research ArticleАВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯCOMPUTER AIDED DESIGNНеразрушающие тесты с четным повторением адресов для запоминающих устройствTransparent memory tests with even repeating addresses for storage devicesЯрмоликВ. Н.YarmolikV. N.

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

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

Vyacheslav N.   Yarmolik - Dr. Sci. (Eng.), Professor.

St. P. Brovki, 6, 220013, Minsk

yarmolik10ru@yahoo.comМрозекИ.MrozekI. M.

Мрозек Иренеуш - доктор, адъюнкт.

ул. Вейска, 45A, 15-351, Белосток

Ireneusz Mrozek - Dr. Sci., Lecture.

St. Wiejska, 45A, 15-351, Biafystok

i.mrozek@pb.edu.plЛеванцевичВ. А.LevantsevichV. A.

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

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

Vladimer A. Levantsevich - M. Sci. (Eng.), Senior Lecture.

St. P. Brovki, 6, 220013, Minsk

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

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

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

Denis V. Demenkovets - M. Sci. (Eng.), Senior Lecture.

St. P. Brovki, 6, 220013, Minsk

demenkovets@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsБелостокский технический университетBialystok University of Technology2021300920211831835Copyright © Ярмолик В.Н., Мрозек И.M., Леванцевич В.А., Деменковец Д.В., 20212021Ярмолик В.Н., Мрозек И., Леванцевич В.А., Деменковец Д.В.Yarmolik V.N., Mrozek I.M., Levantsevich V.A., 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/1137

Показывается актуальность задачи тестирования запоминающих устройств современных вычислительных систем. Исследуются математические модели неисправностей этих устройств и используемые методы тестирования наиболее сложных из них на базе классических неразрушающих маршевых тестов. Вводится понятие адресных последовательностей (pA) с четным повторением адресов, которые являются основой базового элемента, входящего в структуру новых неразрушающих маршевых тестов March_pA_1 и March_pA_2. Приводятся алгоритмы формирования подобных последовательностей и примеры их реализации. Показывается максимальная диагностическая способность новых тестов для случая простейших неисправностей, таких как константные (SAF) и переходные (TF), а также сложных кодочувствительных неисправностей (PNPSFk). Отмечается существенно меньшая временная сложность тестов March_pA_1 и March_pA_2 по сравнению с классическими неразрушающими тестами, которая достигается за счет меньших временных затрат на получение эталонной сигнатуры. Вводятся новые метрики расстояния для количественного сравнения эффективности применяемых pA при однократной реализации тестов March_pA_1 и March_pA_2. В основе новых метрик лежит расстояние D(A(j), pA), определяемое разностью индексов повторяющихся адресов A(j) в последовательности pA. Исследуются свойства новых характеристик последовательностей pA и оценивается их применимость для выбора оптимальных тестовых последовательностей pA, обеспечивающих высокую эффективность новых неразрушающих тестов. Приводятся примеры вычисления метрик расстояний и показывается зависимость эффективности новых тестов от численных значений метрик расстояния. Как и в случае классических неразрушающих тестов, рассматривается многократное применение тестов March_pA_1 и March_pA_2. Вводится характеристика V(pA), которая численно равняется количеству отличающихся значений расстояния D(A(j), pA) адресов A(j) последовательности pA. Экспериментально показывается справедливость аналитических оценок и подтверждается высокая эффективность обнаружения неисправностей однократными и многократными тестами типа March_pA_1 и March_pA_2 на примере неисправностей взаимного влияния для p = 2.

The urgency of the problem of memory testing of modern computing systems is shown. Mathematical models describing the faulty states of storage devices and the methods used for their detection are investigated. The concept of address sequences (pA) with an even repetition of addresses is introduced, which are the basis of the basic element included in the structure of the new transparent march tests March _pA_1 and March _pA_2. Algorithms for the formation of such sequences and examples of their implementations are given. The maximum diagnostic ability of new tests is shown for the case of the simplest faults, such as constant (SAF) and transition faults (TF), as well as for complex pattern sensitive faults (PNPSFk). There is a significantly lower time complexity of the March_pA_1 and March_pA_2 tests compared to classical transparent tests, which is achieved at the expense of less time spent on obtaining a reference signature. New distance metrics are introduced to quantitatively compare the effectiveness of the applied pA address sequences in a single implementation of the March_pA_1 and March_pA_2 tests. The basis of new metrics is the distance D(A(j), pA) determined by the difference between the indices of repeated addresses A(j) in the sequence pA. The properties of new characteristics of the pA sequences are investigated and their applicability is evaluated for choosing the optimal test pA sequences that ensure the high efficiency of new transparent tests. Examples of calculating distance metrics are given and the dependence of the effectiveness of new tests on the numerical values of the distance metrics is shown. As well as in the case of classical transparent tests, multiple applications of new March_pA_1 and March_pA_2 tests are considered. The characteristic V(pA) is introduced, which is numerically equal to the number of different values of the distance D(A(j), pA) of addresses A(j) of the sequence pA. The validity of analytical estimates is experimentally shown and high efficiency of fault detection by the tests March_pA_1 and March_pA_2 is confirmed by the example of coupling faults for p = 2.

тестирование вычислительных системзапоминающие устройстванеразрушающие маршевые тестыадресные последовательности с четным повторением адресовмногократное неразрушающее тестированиеtesting of computer systemsmemorytransparent march testsaddress sequences with even repeating addressesmultiple transparent testingReferencesSharma, A. K. Advanced Semiconductor Memories: Architectures, Designs, and Applications / A. K. Sharma. - London : John Wiley & Sons, 2003. - 652 р.Sharma A. K. Advanced Semiconductor Memories: Architectures, Designs, and Applications. London, John Wiley & Sons, 2003, 652 р.The new hardware development trend and the challenges in data management and analysis / W. Pan [et al] // Data Science and Engineering. - 2018. - Vol. 6, no. 3. - P. 263-276.Pan W., Li Z., Zhang Y., Weng C. The new hardware development trend and the challenges in data management and analysis. Data Science and Engineering, 2018, vol. 6, no. 3, pp. 263-276.Prince, B. High-Performance Memories: New Architecture DRAM's and SRAM's, Evolution and Function / B. Prince. - London : John Wiley & Sons, 1999. - 354 p.Prince B. High-Performance Memories: New Architecture DRAM's and SRAM’s, Evolution and Function. London, John Wiley & Sons, 1999, 354 p.Goor, A. J. Testing Semiconductor Memories: Theory and Practice / A. J. Goor. - Chichester, UK : John Wiley & Sons, 1991. - 536 p.Goor A. J. Testing Semiconductor Memories: Theory and Practice. Chichester, UK, John Wiley & Sons, 1991, 536 p.Ярмолик, С. В. Маршевые тесты для самотестирования ОЗУ / С. В. Ярмолик, А. П. Занкович, А. А. Иванюк. - Минск : Бестпринт, 2009. - 270 с.Yarmolik S. V., Zankovich A. P., Ivaniuk A. A. Marshevue testu dlya samotestirovaniya OZU. RAM SelfTest March Tests. Minsk, Bestprint, 2009, 270 р. (In Russ.).Du, X. New Memory BIST and Repair Methods / X. Du. - Iowa : University of Iowa, 2004. - 276 р.Du X. New Memory BIST and Repair Methods. Iowa, University of Iowa, 2004, 276 р.Chakraborty, A. Fault-Tolerance and Reliability Techniques for High-Density Random-Access Memories / A. Chakraborty, P. Mazumder. - Prentice Hall, 2002. - 448 p.Chakraborty A. Fault-Tolerance and Reliability Techniques for High-Density Random-Access Memories. Prentice Hall, 2002, 448 p.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.Неразрушающее тестирование запоминающих устройств / В. Н. Ярмолик [и др.]. - Минск : Бестпринт, 2005. - 230 с.Yarmolik V. N., Murashko I. A., Kummert A., Ivaniuk A. A. Nerazrushayuschee testirovanie zapominayuschih ustroistv. Transparent Memory Testing. Minsk, Bestprint, 2005, 230 р. (In Russ.).Ярмолик, В. Н. Обзор методов неразрушающего тестирования ОЗУ / В. Н. Ярмолик, А. П. Занкович // Доклады БГУИР. - 2005. - № 4(12). - С. 62-72.Yarmolik V. N., Zankovich A. P. Overview of transparent testing methods for RAM. Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioelektroniki [Reports of the Belarusian State University of Informatics and Radioelectronics], 2005, no. 4(12), pp. 62-72 (In Russ.).Ярмолик, С. В. Многократные неразрушающие маршевые тесты с изменяемыми адресными последовательностями / С. В. Ярмолик, В. Н. Ярмолик // Автоматика и телемеханика. - 2007. - № 4. - C. 126-137.Yarmolik S. V., Yarmolik V. N. Multiple non-destructive marching tests with variable address sequences. Avtomatika i telemehanika [Automation and Remote], 2007, no. 4, рр. 126-137 (In Russ.).Ярмолик, В. Н. Адресные последовательности для многократного тестирования ОЗУ / В. Н. Ярмо-лик, С. В. Ярмолик // Информатика. - 2014. - № 2(39). - C. 124-136.Yarmolik V. N., Yarmolik S. V. Address sequences for repeated testing of RAM. Informatika [Informatics], 2014, no. 2(39), рр. 124-136 (In Russ.).Yarmolik, V. N. Modified gray and counter sequences for memory test address generation / V. N. Yarmolik, S. V. Yarmolik // Proc. of the 13th Intern. Conf. MIXDES Design of Integrated Circuits and Systems, Gdynia, Poland, 22-24 June 2006. - Gdynia, 2006. - P. 572-576.Yarmolik V. N., Yarmolik S. V. Modified gray and counter sequences for memory test address generation. Proceedings of the 13th International Conference MIXDES Design of Integrated Circuits and Systems, Gdynia, Poland, 22-24 June 2006. Gdynia, 2006, pp. 572-576.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.Ярмолик, С. В. Квазислучайное тестирование вычислительных систем / С. В. Ярмолик, В. Н. Ярмолик // Информатика. - 2013. - № 3(39). - С. 92-103.Yarmolik S. V., Yarmolik V. N. Quasi-random testing of computing systems. Informatika [Informatics], 2013, no. 3(39), рр. 92-103 (In Russ.).Savage, C. A survey of combinatorial Gray code / С. 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.Chi, H. Computational investigations of quasi-random sequences in generating test cases for specification-based tests / H. Chi, E. I. Jones // Proc. of the Winter Simulation Conf. WSC 2006, Monterey, CA, USA, 3-6 Dec. 2006. - Monterey, 2006. - P. 975-980.Chi H., Jones E. I. Computational investigations of quasi-random sequences in generating test cases for specification-based tests. Proceedings of the Winter Simulation Conference WSC 2006, Monterey, California, USA, 3-6 December 2006. Monterey, 2006, pp. 975-980.Chen, T. Y. Quasi-random testing / T. Y. Chen, R. Merkel // IEEE Transaction on Reliability. - 2007. -Vol. 56, no. 3. - P. 562-568.Chen T. Y., Merkel R. Quasi-random testing. IEEE Transaction on Reliability, 2007, vol. 56, no. 3, pp. 562-568.Yarmolik, S. V. Address sequences and backgrounds with different hamming distance for multiple run March tests / S. V. Yarmolik // IEEE Intern. J. of Applied Mathematics and Computer Science. - 2008. -Vol. 18, no. 3. - P. 329-339.Yarmolik S. V. Address sequences and backgrounds with different hamming distance for multiple run March tests. IEEE International Journal of Applied Mathematics and Computer Science, 2008, vol. 18, no. 3, pp. 329-339.Ярмолик, С. В. Анализ количественных характеристик различия при тестировании ОЗУ / С. В. Яр-молик, А. Н. Курбацкий, В. Н. Ярмолик // Информатика. - 2008. - № 3(19). - С. 90-98.Yarmolik S. V., Kurbatski A. N., Yarmolik V. N. Dissimilarity measure analysis for random access memory testing. Informatika [Informatics], 2008, no. 3(19), рр. 90-98 (In Russ.).Thompson, A. C. Minkowski Geometry / A. C. Thompson. - Cambridge, N. Y., 1996. - 364 p.Thompson A. C. Minkowski Geometry. Cambridge, New York, 1996, 364 p.Tubbs, J. D. Note on binary template matching / J. D. Tubbs // Pattern Recognition. - 1989. - Vol. 22, no. 4. - P. 359-365.Tubbs J. D. Note on binary template matching. Pattern Recognition, 1989, vol. 22, no 4, pp. 359-365.Sokol, B. Impact of the address changing on the detection of pattern sensitive faults / B. Sokol, I. Mrozek, V. N. Yarmolik // Information Processing and Security Systems. - London : Springer Science + Business Media, Inc., 2005. - P. 217-226.Sokol B., Mrozek I., Yarmolik V. N. Impact of the address changing on the detection of pattern sensitive faults. Information Processing and Security Systems, London, Springer Science + Business Media, Inc., 2005, pp. 217-226.Zhou, Z. Q. Using coverage information to guide test case selection in adaptive random testing / Z. Q. Zhou // Proc. 34th IEEE Computer Soft and Applications Conf., Seoul, Korea, 19-23 July 2010. - Seoul, 2010. - P. 208-213.Zhou Z. Q. Using coverage information to guide test case selection in adaptive random testing. Proceedings 34th IEEE Computer Soft and Applications Conference, Seoul, Korea, 19-23 July 2010. Seoul, 2010, pp. 208-213.Chan, K. P. Good random testing / K. P. Chan, T. Y. Chen, D. Towey // Proc. 9th Ada-Europe Intern. Conf. on Reliable Software Technologies (LNCS), Palma de Mallorca, Spain, 14-18 June 2004. Palma de Mallorca, 2004. - P. 200-212.Chan K. P., Chen T. Y., Towey D. Good random testing. Proceedings 9th Ada-Europe International Conference on Reliable Software Technologies (LNCS), Palma de Mallorca, Spain, 14-18 June 2004. Palma de Mallorca, 2004, pp. 200-212.Kuo, F. C. An in-depth study of mirror adaptive random testing / F. C. Kuo // Proc. 14th European Conf. on Soft Quality, Los Alamitos, CA, USA. - Los Alamitos, 2009. - P. 51-58.Kuo F. C. An in-depth study of mirror adaptive random testing. Proceedings 14th European Conference on Soft Quality, Los Alamitos, CA, USA. Los Alamitos, 2009, pp. 51-58.Shiyi, Xu. Orderly random testing for both hardware and software / Xu Shiyi // Proc. Pacific Rim Intern. Symp. on Dependable Computing, Taipei, Taiwan, 15-17 Dec. 2008. - Taipei, 2008. - P. 160-167.Shiyi Xu. Orderly random testing for both hardware and software. Proceedings Pacific Rim International Symposium on Dependable Computing, Taipei, Taiwan, 15-17 December 2008. Taipei, 2008, pp. 160-167.Ярмолик, С. В. Управляемое случайное тестирование / С. В. Ярмолик, В. Н. Ярмолик // Информатика. - 2011. - № 1(29). - С. 79-88.Yarmolik S. V., Yarmolik V. N. Controlled random testing. Informatika [Informatics], 2011, no. 1(29), рр. 79-88 (In Russ.).Ярмолик, В. Н. Многократные управляемые вероятностные тесты / B. Н. Ярмолик, В. А. Леванцевич, И. Мрозек // Информатика. - 2015. - № 2(12). - С. 63-76.Yarmolik V. N., Levantsevich V. A., Mrozek I. Multiple controlled probability tests. Informatika [Informatics], 2015, no. 2(12), рр. 63-76 (In Russ.).

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