informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2021-18-1-25-42inform-1117Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNПостроение и применение маршевых тестов для обнаружения кодочувствительных неисправностей запоминающих устройствConstruction and application of march tests for pattern sensitive memory faults detectionЯрмоликВ. Н.YarmolikV. N.

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

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

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

st. P. Brovki, 6, 220013, Minsk

yarmolik10ru@yahoo.comЛеванцевичВ. А.LevantsevichV. A.

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

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

Vladimer A. Levantsevich, M. Sci. (Eng.), SeniorLecture

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МрозекИ.MrozekI.

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

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

Ireneusz Mrozek, Dr. Sci., Lecture

st. Wiejska, 45A, 15-351, Białystok

i.mrozek@pb.edu.plБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsБелостоцкий технический университетBialystok University of Technology2021290320211812542Copyright © Ярмолик В.Н., Леванцевич В.А., Деменковец Д.В., Мрозек И., 20212021Ярмолик В.Н., Леванцевич В.А., Деменковец Д.В., Мрозек И.Yarmolik V.N., Levantsevich V.A., Demenkovets D.V., Mrozek I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1117

Показывается актуальность задачи тестирования запоминающих устройств современных вычислительных систем. Исследуются математические модели неисправностей запоминающих устройств и используемые методы тестирования наиболее сложных из них на базе классических маршевых тестов. Выделяются пассивные кодочувствительные неисправности (PNPSFk), в которых участвуют произвольные k из N ячеек памяти, где k << N, а N представляет собой емкость памяти в битах. Для этих неисправностей приводятся аналитические выражения минимальной и максимальной полноты покрытия, которые достижимы в рамках маршевых тестов. Определяется понятие примитива, описывающего в терминах элементов маршевого теста условия активизации и обнаружения неисправностей PNPSFk запоминающих устройств. Приводятся примеры построения маршевых тестов, имеющих максимальную полноту покрытия, а также маршевых тестов с минимальной временной сложностью, равной 18N. Исследуется эффективность однократного применения тестов типа MATS++, March C− и March PS для различного количества k ≤ 9 ячеек памяти, участвующих в неисправности PNPSFk. Обосновывается применимость многократного тестирования с изменяемыми адресными последовательностями, в качестве которых предлагается применять случайные последовательности адресов. Приводятся аналитические выражения для полноты покрытия сложных неисправностей PNPSFk в зависимости от кратности теста. Кроме того, даются оценки среднего значения кратности тестов MATS++, March C− и March PS, полученные на основании математической модели, которая описывает задачу собирателя купонов, и обеспечивающие обнаружение всех k2k неисправностей PNPSFk. Экспериментально показывается справедливость аналитических оценок и подтверждается высокая эффективность обнаружения неисправностей PNPSFk тестами типа March PS.

The urgency of the problem of testing storage devices of modern computer systems is shown. The mathematical models of their faults and the methods used for testing the most complex cases by classical march tests are investigated. Passive pattern sensitive faults (PNPSFk) are allocated, in which arbitrary k from N memory cells participate, where k << N, and N is the memory capacity in bits. For these faults, analytical expressions are given for the minimum and maximum fault coverage that is achievable within the march tests. The concept of a primitive is defined, which describes in terms of march test elements the conditions for activation and fault detection of PNPSFk of storage devices. Examples of march tests with maximum fault coverage, as well as march tests with a minimum time complexity equal to 18N are given. The efficiency of a single application of tests such as MATS ++, March C− and March PS is investigated for different number of k ≤ 9 memory cells involved in PNPSFk fault. The applicability of multiple testing with variable address sequences is substantiated, when the use of random sequences of addresses is proposed. Analytical expressions are given for the fault coverage of complex PNPSFk faults depending on the multiplicity of the test. In addition, the estimates of the mean value of the multiplicity of the MATS++, March C− and March PS tests, obtained on the basis of a mathematical model describing the problem of the coupon collector, and ensuring the detection of all k2k PNPSFk faults are given. The validity of analytical estimates is experimentally shown and the high efficiency of PNPSFk fault detection is confirmed by tests of the March PS type.

тестирование вычислительных системзапоминающие устройствамаршевые тесты памятимногократное тестированиезадача собирателя купоновtesting of computer systemsstorage devicesmarch tests of memorymultiple testingcoupon collector problemReferencesThe International Technology Roadmap for Semiconductors: 2003 Edition. – San Jose, CA, USA, Semiconductor Industry Association, 2003. – 65 p.The International Technology Roadmap for Semiconductors: 2003 Edition. San Jose, CA, USA, Semiconductor Industry Association, 2003, 65 p.Sharma, 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 р.Wang, L.-T. VLSI Test Principles and Architectures: Design for Testability / L.-T. Wang, C.-W. Wu, X. Wen. – Amsterdam : Elsevier, 2006. – 808 p.Wang L.-T., Wu C.-W., Wen X. VLSI Test Principles and Architectures: Design for Testability. Amsterdam, Elsevier, 2006, 808 p.Bushnell, M. L. Essentials of Electronic Testing for Digital, Memory & Mixed-Signal VLSI Circuits / M. L. Bushnell, V. D. Agrawal. – N. Y., USA : Kluwer Academic Publishers, 2000. – 690 p.Bushnell M. L., Agrawal V. D. Essentials of Electronic Testing for Digital, Memory & Mixed-Signal VLSI Circuits. New York, USA, Kluwer Academic Publishers, 2000, 690 p.Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бест-принт, 2019. – 387 с.Yarmolik V. N. Kontrol’ i diagnostika vuchislitel’nuh system. Monitoring and Diagnostics of Computer Systems. Minsk, Bestprint, 2019, 387 р. (in Russian).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.Hayes, J. P. Detection of pattern-sensitive faults in random access memories / J. P. Hayes // IEEE Transactions on Computer. − 1975. − Vol. 24, no. 2. − P. 150−157.Hayes J. P. Detection of pattern-sensitive faults in random access memories. IEEE Transactions on Computer, 1975, vol. 24, no. 2, pp. 150−157.Anderson, K. Device manufacturers test problems / K. Anderson // Proc. of IEEE Semiconductor Test Symp. − Cherry Hill, NJ, USA, 1972. – P. 17–26.Anderson K. Device manufacturers test problems. Proceedings of IEEE Semiconductor Test Symposium. Cherry Hill, NJ, USA, 1972, pp. 17–26.Suk, D. S. Test procedures for a class of pattern-sensitive faults in semiconductor random-access memories / D. S. Suk, S. M. Reddy // IEEE Transactions on Computer. − 1980. − Vol. 29, no. 6. − P. 419−429.Suk D. S., Reddy S. M. Test procedures for a class of pattern-sensitive faults in semiconductor random-access memories. IEEE Transactions on Computer, 1980, vol. 29, no. 6, pp. 419−429.Hayes, J. P. Testing memories for single-cell pattern-sensitive fault / J. P. Hayes // IEEE Transactions on Computer. − 1980. − Vol. 29, no. 3. − P. 249−254.Hayes J. P. Testing memories for single-cell pattern-sensitive fault. IEEE Transactions on Computer, 1980, vol. 29, no. 3, pp. 249−254.Cheng, K.-L. Efficient neighborhood pattern-sensitive fault test algorithms for semiconductor memories / K.-L. Cheng, M.-F. Tsai, C. T. Wu // Proc. of 19th IEEE VLSI Test Symp. − Marina Del Rey, CA, USA, 2001. − P. 225−237.Cheng K.-L., Tsai M.-F., Wu C. T. Efficient neighborhood pattern-sensitive fault test algorithms for semiconductor memories. Proceedings of 19th IEEE VLSI Test Symposium. Marina Del Rey, CA, USA, 2001, pp. 225−237.Cheng, K.-L. Neighborhood pattern-sensitive fault testing and diagnostics for random-access memories / K.-L. Cheng, M.-F. Tsai, C. T. Wu // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. − 2002. − Vol. 21, no. 11. − P. 284−267.Cheng K.-L., Tsai M.-F., Wu C. T. Neighborhood pattern-sensitive fault testing and diagnostics for random-access memories. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 11, pp. 284−267.Cascaval, P. Efficient march test for 3-coupling faults in random access memories / P. Cascaval, S. Bennett // Microprocessors and Microsystems. − 2001. − Vol. 24, no. 10. − P. 501−509.Cascaval P., Bennett S. Efficient march test for 3-coupling faults in random access memories. Microprocessors and Microsystems, 2001, vol. 24, no. 10, pp. 501−509.Kang, D.-C. An efficient built-in self-test algorithm for neighborhood pattern sensitive faults in high-density memories / D.-C. Kang, S.-B. Cho // Proc. of 4th Korea-Russia Intern. Symp. (KORUS 2000). − Ulsan, South Korea, 2000. – Vol. 2. – P. 218–223.Kang D.-C., Cho S.-B. An efficient built-in self-test algorithm for neighborhood pattern sensitive faults in high-density memories. Proceedings of 4th Korea-Russia International Symposium (KORUS 2000). Ulsan, South Korea, 2000, vol. 2, pp. 218–223.Cockburn, B. F. Deterministic tests for detecting scrambled pattern-sensitive faults in RAMs / B. F. Cockburn // Proc. IEEE Intern. Workshop Memory Technology Design and Testing (MTDT). − San Jose, CA, USA, 1995. – P. 117–122.Cockburn B. F. Deterministic tests for detecting scrambled pattern-sensitive faults in RAMs. Proceedings IEEE International Workshop Memory Technology Design and Testing (MTDT). San Jose, CA, USA, 1995, pp. 117–122.Ярмолик, В. Н. Псевдоисчерпывающее тестирование запоминающих устройств на базе маршевых тестов типа March A / B. Н. Ярмолик, И. Мрозек, С. В. Ярмолик // Информатика. – 2020. − № 2(17). − С. 54−70.Yarmolik V. N., Mrozek I., Yarmolik S. V. Pseudoischerpuvayuchie testirovanie zapominayuschih ustroistv na baze marchevuh testov tipa March A [Pseudo-exhaustive memory testing based on March A tests]. Informatika [Informatics], 2020, no. 2(17), рр. 54–70 (in Russian).Ярмолик, С. В. Маршевые тесты для самотестирования ОЗУ / С. В. Ярмолик, А. П. Занкович, А. А. Иванюк. – Минск : Бестпринт, 2009. – 270 с.Yarmolik V. N., Zankovich A. P., Ivanuok A. A. Marshevue testu dlya samotestirovaniya OZU. RAM Self-Test March Tests. Minsk, Bestprint, 2009, 270 р. (in Russian).Franklin, M. A built in self-test algorithm for row/column pattern sensitive faults in RAMs / M. Franklin, K. Saluja, K. Kinoshita // IEEE J. of Solid-State Circuits. – 1990. − Vol. 25, no. 2. − P. 514−524.Franklin M., Saluja K., Kinoshita K. A built in self-test algorithm for row/column pattern sensitive faults in RAMs. IEEE Journal of Solid-State Circuits, 1990, vol. 25, no. 2, pp. 514−524.Sfikas, Y. Physical design oriented DRAM neighborhood pattern sensitive fault testing / Y. Sfikas, Y. Tsiatouhas // Proc. of 12th Intern. Symp. on Design and Diagnostics of Electronic Circuits & Systems (DDECS). − Liberec, Czech Republic, 2009. − P. 108−113.Sfikas Y., Tsiatouhas Y. Physical design oriented DRAM neighborhood pattern sensitive fault testing. Proceedings of 12th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Liberec, Czech Republic, 2009, pp. 108−113.Parallel testing of multi-port static random access memories / F. Karimi [et al.] // Microelectronics J. – 2003. − Vol. 34, no. 1. − P. 3−21.Karimi F., Irrinki S., Crosbuy T., Lombardi F. Parallel testing of multi-port static random access memories. Microelectronics Journal, 2003, vol. 34, no. 1, pp. 3−21.Min, D.-S. Multiple twisted data line techniques for coupling noise reduction in embedded DRAMS / D-S. Min, D. Langer // IEEE Custom Integrated Circuits Conf. – San Diego, CA, USA, 1999. − P. 231−234.Min D.-S., Langer D. Multiple twisted data line techniques for coupling noise reduction in embedded DRAMS. IEEE Custom Integrated Circuits Conference. San Diego, CA, USA, 1999, pp. 231−234.Kang, D.-C. An efficient built-in self-test algorithm for neighborhood pattern and bit-line-sensitive faults in high density memories / D.-C. Kang, S. M. Park, S.-B. Cho // ETRI J. – 2004. − Vol. 26, no. 6. − P. 520−534.Kang D.-C., Park S. M., Cho S.-B. An efficient built-in self-test algorithm for neighborhood pattern and bit-line-sensitive faults in high density memories. ETRI Journal, 2004, vol. 26, no. 6, pp. 520−534.Goor, A. J. van de. Disturb neighborhood pattern sensitive fault / A. J. van de Goor, I. B. S. Tlili // IEEE Intern. VLSI Test Symp. – San Diego, CA, USA, 1997. − P. 37−45.Goor A. J. van de, Tlili I. B. S. Disturb neighborhood pattern sensitive fault. IEEE International VLSI Test Symposium. San Diego, CA, USA, 1997, pp. 37−45.Yarmolik, V. N. Transparent memory testing for pattern-sensitive faults / V. N. Yarmolik, M. G. Karpovsky // Proc. of Intern. Test Conf. – Washington DC, USA, 1994. – P. 860–869.Yarmolik V. N., Karpovsky M. G. Transparent memory testing for pattern-sensitive faults. Proceedings of International Test Conference. Washington DC, USA, 1994, pp. 860–869.Cockburn, B. E. Synthesized transparent BIST for detecting scrambled pattern-sensitive faults in RAMs / B. E. Cockburn, Y. F. Sat // Proc. of the IEEE Intern. Test Conf. – Washington DC, USA, 1995. – P. 23–32.Cockburn B. E., Sat Y. F. Synthesized transparent BIST for detecting scrambled pattern-sensitive faults in RAMs. Proceedings of the IEEE International Test Conference. Washington DC, USA, 1995, pp. 23–32.Yarmolik, V. March PS(23N) test for DRAM pattern-sensitive faults / V. Yarmolik, Y. Klimets, S. Demidenko // Proc. Seventh IEEE Asian Test Symp. (ATS). – Singapore, 1998. – P. 354–357.Yarmolik V., Klimets Y., Demidenko S. March PS(23N) test for DRAM pattern-sensitive faults. Proceedings Seventh IEEE Asian Test Symposium (ATS). Singapore, 1998, pp. 354–357.Mrozek, I. Multi-run Memory Tests for Pattern Sensitive Faults / I. Mrozek. – Cham : Springer International Publishing AG, 2019. – 135 p.Mrozek I. Multi-run Memory Tests for Pattern Sensitive Faults. Cham, Springer International Publishing AG, 2019, 135 p.Nicolaidis, M. Transparent BIST for RAMs / M. Nicolaidis // Proc. IEEE Intern. Test Conf. – Washington DC, USA, 1992. – P. 598–607.Nicolaidis M. Transparent BIST for RAMs. Proceedings IEEE International Test Conference. Washington DC, USA, 1992, pp. 598–607.Неразрушающее тестирование запоминающих устройств / В. Н. Ярмолик [и др.]. – Минск : Бест-принт, 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 Russian).Ярмолик, В. Н. Псевдоисчерпывающее тестирование запоминающих устройств на базе многократных маршевых тестов / В. Н. Ярмолик, И. Мрозек, В. А. Леванцевич // Информатика. – 2018. – № 1(15). – C. 110–121.Yarmolik V. N., Mrozek I., Levantsevich V. A. Pseudoischerpuvayuchie testirovanie zapominayuschih ustroistv na baze mnogokratnuch marchevuh testov [Pseudo-exhaustive memory testing based on multiple march tests]. Informatika [Informatics], 2018, no. 1(15), рр. 110–121 (in Russian).Das, D. Exhaustive and near-exhaustive memory testing techniques and their BIST implementations / D. Das, M. G. Karpovsky // J. of Electronic Testing. – 1997. – Vol. 10. – P. 215–229.Das D., Karpovsky M. G. Exhaustive and near-exhaustive memory testing techniques and their BIST implementations. Journal of Electronic Testing, 1997, vol. 10, pp. 215–229.Ярмолик, С. В. Итеративные почти псевдоисчерпывающие вероятностные тесты / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2010. − № 2(26). − С. 66−75.Yarmolik S. V., Yarmolik V. N. Iterativnue pochti pseudoischerpuvayuchie veroyatnostnue testu [Iterative near pseudo-exhaustive tests]. Informatika [Informatics], 2010, no. 2(26), рр. 66–75 (in Russian).Niggemeyer, D. Integration of non-classical faults in standard march tests / D. Niggemeyer, M. Redeker, J. Otterstedt // Proc. IEEE Intern. Workshop on Memory Technology, Design and Testing. – San Jose, USA, 1998. – P. 91–96.Niggemeyer D., Redeker M., Otterstedt J. Integration of non-classical faults in standard march tests. Proceedings IEEE International Workshop on Memory Technology, Design and Testing. San Jose, USA, 1998, pp. 91–96.Ярмолик, В. Н. Адресные последовательности для многократного тестирования ОЗУ / В. Н. Ярмолик, С. В. Ярмолик // Информатика. – 2014. – № 2(42). – C. 124–136.Yarmolik V. N., Yarmolik S. V. Adresnue posledovatel’nosti dlya mnogokratnogo testirovaniya OZU [Address sequences for multi run RAM testing]. Informatika [Informatics], 2014, no. 2(42), рр. 124–136 (in Russian).Ярмолик, С. В. Многократные неразрушающие маршевые тесты с изменяемыми адресными последовательностями / С. В. Ярмолик, В. Н. Ярмолик // Автоматика и телемеханика. – 2007. – № 2. – С. 21–30.Yarmolik S. V., Yarmolik V. N. Mnogokratnue nerazrushayuschie marshevue testu s izmenyaemumi adresnumi posledovatel’nostymi [Multiple non-destructive marching tests with variable address sequences]. Avtomatika i telemehanika [Automation and Remote], 2007, no. 2, рр. 21–30 (in Russian).Flajolet, P. Birthday paradox, coupon collectors, caching algorithms and self-organizing search / P. Flajolet, D. Gardy, L. Thimonier // Discrete Applied Mathematics. – Vol. 39, no. 3 − P. 207−229.Flajolet P., Gardy D., Thimonier L. Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Applied Mathematics, vol. 39, no. 3, рр. 207−229.

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