Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

MEMORY DEVICE AUTOMATED DISCRETE DIAGNOSTIC TEST DESIGN

Ryabtsev V.G. 1 Shubovich A.A. 1 Evseev K.V. 1
1 Volgograd State Agrarian University
The methods and tools of high-performance memory device automated diagnostic test are suggested. The device program model is required for designing the algorithms and test program to reduce work. The scientific foundation of mathematical tools for designing high-performance memory device diagnostic tools are presented as well. The set of code address microoperations is defined for multiprocessor testing tools. Oriented graphs’ incidence matrix transformation, executed by program Transfor.exe, is used to parallelize the code address microoperations for reducing work of designing tests and error frequency. The new symbol notation of algorithm operations is suggested to eliminate verbal description of operations. Code address microoperations paralleling for four address drivers testing tool is done. The example of using the suggested method for designing testing algorithm march_Y is presented.
automated design
memory device
operation processors
diagnostic tests

Для повышения быстродействия всей вычислительной системы усложняются структура и архитектура современных микросхем полупроводниковой памяти. Микросхемы памяти DDR и QDR типов обеспечивают считывание или запись по одной команде пакетов данных длиной до 8 слов. Для выполнения тестового диагностирования быстродействующих микросхем памяти на этапе изготовления целесообразно применять устройства тестового диагностирования (УТД), имеющие мультипроцессорную структуру, содержащую несколько групп формирователей кода адреса, данных и компараторов.

Значительный вклад в формирование теоретических и практических основ диагностики полупроводниковых элементов памяти с привлечением тестовых методов внесли ученые А.А. Иванюк, В.И. Хаханов, В.Н. Ярмолик, D.S. Suk, S.M. Reddy, A.J. Van de Goor, Y.Y. Zorian и другие [8, 12, 13]. Однако в большинстве литературных источников приведены описания алгоритмов и свойства тестов, а принципы проектирования тестов и применяемые при этом средства излагаются недостаточно подробно [5]. Разработка программ тестов диагностирования быстродействующей оперативной памяти сопряжена с высокой трудоемкостью и связана со значительными затратами времени и материальных средств, поэтому требуется создание новых методов и средств, уменьшающих продолжительность проектирования тестов [1–3].

Целью данной статьи является разработка методов и средств автоматизированного проектирования тестов диагностирования быстродействующих запоминающих устройств.

Теоретические основы построения модели диагностируемой памяти и устройства диагностирования

Для проектирования алгоритмов и программ тестов быстродействующих запоминающих устройств предлагается программная модель объекта и устройства диагностирования, которая позволит сократить трудоемкость проектных операций [4]. Структурная схема взаимодействующих объекта и устройства диагностирования (рис. 1) содержит устройство управления (УУ), матрицу запоминающих ячеек и операционные процессоры (ОП).

В качестве объекта диагностирования в модели используется квадратная матрица запоминающих ячеек размером 16×16, при этом обеспечивается удобный вывод их состояния на экран монитора. Все запоминающие ячейки нумеруются цифрами, начиная от 0 до 255. Запись и считывание данных в ячейки обеспечивают операционные процессоры, число которых обычно кратно 2.

Последовательность формируемых тестов определяется УУ, которое может находиться в одном из конечного числа состояний, которое определяется номером текущей команды в программе. В соответствии с текущим состоянием УУ каждый ОП может записывать новые данные в выбранную ячейку и перемещаться независимо друг от друга влево или вправо либо остаться на месте. Для сканирования ячеек памяти при помощи нескольких ОП нужно определить их начальное состояние и набор микроопераций для изменения шага приращения их кода адреса.

pic_34.tif

Рис. 1. Структура модели объекта и устройства диагностирования

Предлагаемая математическая модель задается пятеркой компонентов:

M = <Q, q0, S, рr, d>,

где Q – множество состояний УУ; q0 – начальное состояние УУ; S – множество символов алфавита; рr – величина приращения координаты r-го ОП; d – функция переходов, которая отображает некоторое подмножество множества Q×(Sr×pr), то есть для заданного состояния УУ и символов, обозреваемых ОП, выдает новое состояние, новые символы и приращения координат ОП.

Пусть

ryabtsev01.wmf

и УУ находится в состоянии q1, а i-й ОП обозревает символ si, тогда УУ перейдет в состояние q2, заменит символы si на ryabtsev02.wmf и все ОП изменят свои позиции на pi.

Сформулированные ниже теоремы доказывают необходимость и достаточность набора микроопераций для разработки программ наиболее распространенных тестов диагностирования полупроводниковой памяти.

Теорема 1. Для обращения ко всем ячейкам памяти запоминающего устройства емкостью n = 2m бит, где m – целое положительное число больше 3, с увеличением кода адреса колонок устройством, имеющим h = 2k операционных процессоров и двухкоординатную систему адресации, где k ≤ m, достаточно следующего набора микроопераций формирования кода адреса:

m1 = {x := gx, y := gy, x := x + 1, ..., x := x + 2k, y := y + 1, y := y + 1*},

где gx – начальный адрес по координате Х; gy – начальный адрес по координате Y; символ * означает наличие переноса из координаты Х.

Доказательство. Рассмотрим случай, когда k = 2, m = 8, то есть память, имеющую 256 ячеек и h = 22 = 4 операционных процессора, формирующих коды адреса и обеспечивающих выбор ячеек памяти для записи или считывания. Для установки ОП в исходное состояние используем следующий набор микроопераций, представленный в виде матрицы, строки которой определяют положения ОП: первая для ОР0, вторая – ОП1, третья – ОП2, четвертая – ОП3:

ryabtsev03.wmf

Для выбора всех остальных смежных ячеек с увеличением кода адреса колонок применим следующий набор микроопераций:

ryabtsev04.wmf

Так как емкость микросхемы памяти в модели n = 256 бит и кратна числу ОП h = 4, поэтому, циклически повторяя набор микроопераций MO2, можно выбрать все ячейки памяти для данного направления сканирования. Матрицы MO1 и MO2 содержат только микрооперации, приведенные в теореме 1, что подтверждает ее справедливость. Если емкость памяти и число операционных процессоров удовлетворяет условиям теоремы 1, то для любой допустимой их комбинации можно составить наборы микроопераций, аналогичные наборам MO1 и MO2 для выбора всех ячеек с возрастанием кода адреса колонок.

Теорема 2. Для обращения ко всем ячейкам памяти емкостью n = 2m бит, где m – целое положительное число больше 3, с увеличением кода адреса рядов устройством, имеющим h = 2k операционных процессоров и двухкоординатную систему адресации, где k ≤ m, достаточно следующего набора микроопераций для формирования кода адреса:

m2 = {x := gx, y := gy, y := y + 1, y := y + 2, ..., y := y + 2k, x := x + 1}.

Теорема 3. Для обращения ко всем ячейкам памяти емкостью n = 2m бит, где m – целое положительное число больше 3, с уменьшением кода адреса колонок устройством, имеющим h = 2k операционных процессоров и двухкоординатную систему адресации, где k ≤ m, достаточно следующего набора микроопераций для формирования кода адреса:

m3 = {x := nx, y := ny, x := x – 1, x := x – 2, ..., x := x – 2k, y := y – 1*}.

Здесь символ * означает наличие займа из координаты Х.

Теорема 4. Для обращения ко всем ячейкам памяти емкостью n = 2m бит, где m – целое положительное число больше 3, с уменьшением кода адреса рядов устройством, имеющим h = 2k операционных процессоров и двухкоординатную систему адресации, где k ≤ m, достаточно следующего набора микроопераций для формирования кода адреса:

m4 = {x := nx, y := ny, y := y – 1, y := y – 2, ..., y := y – 2k, x := x – 1}.

Аналогично приведенному доказательству теоремы 1 можно доказать справедливость теорем 2, 3 и 4. Для разработки программ тестов необходимо учитывать следствия, которые вытекают из данных теорем.

Следствие 1. Для циклического выполнения фрагментов программ тестов, функционирующих согласно условиям и указаниям, приведенным в теоремах 1 и 2, необходимо использовать флаг условного перехода ryabtsev05.wmf, который формируется (h – 1)-м операционным процессором.

Следствие 2. Для циклического выполнения фрагментов программ тестов, функционирующих согласно условиям и указаниям, приведенным в теоремах 3 и 4, необходимо использовать флаг условного перехода ryabtsev06.wmf, который формируется (h – 1)-м операционным процессором.

Применение матриц инциденций графов адресных переходов для автоматизации распараллеливания микроопераций в алгоритмах тестов

Значительного повышения быстродействия диагностических устройств можно достичь за счет распараллеливания микроопераций формирования кодов адреса, данных и обработки считанных реакций устройством диагностирования, имеющим мультипроцессорную структуру [1, 3]. Однако применение мультипроцессорной структуры диагностических устройств увеличивает сложность проектирования алгоритмов и программ тестов, так как необходимо управлять одновременной работой нескольких ОП.

Для определения элементов матриц инциденций используются следующие обозначения: а i,j = 1, если ребро j уходит из вершины i; a i,j = –1, если ребро j подходит к вершине i или в вершине i имеется петля; ai,j = 0, если ребро j не имеет общей точки с вершиной i.

Наличие петель в преобразуемых графах соответствует операциям многократного обращения к одной и той же ячейке памяти, что характерно для большинства применяемых тестов семейства march.

Пусть задана матрица инциденций М размером n×m элементов:

ryabtsev07.wmf

Требуется разбить её на k матриц размером (n×m/k) каждая. Для решения данной задачи выполним следующие преобразования:

ryabtsev08.wmf (*)

где s = m/k – число столбцов в матрицах M0, M1, ..., Mk–1.

Таким образом, каждый j-й столбец матрицы М преобразуется в r-й столбец матрицы Мp. Дополним полученные матрицы единичными элементами:

ryabtsev09.wmf (2)

ryabtsev10.wmf

кроме ryabtsev11.wmf причем (r + 1) не больше, чем (s – 1).

Например, пусть задана матрица инциденций, которая имеет вид: A = (aij)mn, содержит ryabtsev12.wmf строк и ryabtsev13.wmf столбцов. После выполнения преобразований, приведенных выше, получаем матрицы инциденций, которые отображают работу отдельных ОП:

ryabtsev14.wmf

где aip, aiq, ..., aiw – элементы вновь сформированных матриц; h = n/l – число столбцов в данных матрицах.

Число сформированных матриц равно количеству ОП. На основании полученных матриц определяются микрооперации смены позиций для каждого ОП.

Рассмотренные выше матричные преобразования реализованы в программе Transfor.exe, осуществляющей разбиение и объединение матриц инциденций направленных графов [6, 7, 9]. Главное меню программы Transfor.exe приведено на рис. 2. Опция «Direct Transformation» обеспечивает объединение нескольких матриц в одну матрицу, а опция «Inverse Transformation» обеспечивает разбиение одной матрицы на несколько матриц.

Для отображения операций диагностирования запоминающих устройств используется операторная форма записи алгоритмов [3]. Операцию обращения для записи нуля в ячейку памяти с адресом (а) отображает оператор V(a), записи единицы – W(а), считывания данных – R(а). Операции записи единиц во все ячейки при возрастании кода адреса записываются в виде последовательности операторов ryabtsev15.wmf. Здесь символ Р определяет последовательность выполняемых операций, нижний индекс определяет начальный адрес ячейки памяти, а верхний индекс – конечный адрес запоминающих ячеек.

pic_35.tif

Рис. 2. Окно программы Transfor.exe при объединении матриц

Рассмотрим пример преобразования матрицы инциденций для теста march_Y, алгоритм которого в операторном виде имеет вид

ryabtsev16.wmf

Граф адресных переходов сканирования ячеек памяти данным тестом с увеличением кода адреса приведен на рис. 3.

pic_36.tif

Рис. 3. Граф теста march_Y при увеличении кода адреса

Матрица инциденций данного теста для 8 ячеек памяти приведена ниже.

ryabtsev17.wmf

Для распараллеливания операций данного теста при функционировании устройства, имеющего четыре ОП, выполним преобразования данной матрицы при помощи программы Transfor и получаем 4 матрицы, которые отображают адресные переходы четырех ОП:

ryabtsev18.wmf ryabtsev19.wmf

ryabtsev20.wmf ryabtsev21.wmf

На основании анализа полученных матриц можно определить микрооперации изменения кода адреса для выполнения теста march_Y устройством диагностирования, имеющим 4 ОП.

Для разработки алгоритмов и программ тестов быстродействующих запоминающих устройств, а также для анализа выполняемых операций разработана интерпретирующая система Prover, в которой предусмотрены три режима работы: автоматический, пошаговый и графический [10, 11]. При достижении команды останова на экран выводится сообщение о корректности или об ошибках в программе теста.

Выводы

Разработанную программную модель взаимодействующих микросхемы памяти и устройства диагностирования можно использовать в конструкторских, научно-производственных объединениях и высших учебных заведениях для разработки новых диагностических систем. Предложенный метод распараллеливания микроопераций тестов полупроводниковой памяти, основанный на преобразованиях матриц инциденций графов адресных переходов, повышает производительность труда программистов в 3,8 раза при применении двух операционных процессоров, и в 4,2 раза при четырех параллельно работающих операционных процессорах.

Работа выполнена при финансовой поддержке гранта РФФИ (проект 16-08-00393).