автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Разработка и исследование функциональных диагностических тестов конвейеризованных RISC процессоров

□□3447829

На правах рукописи

Белкин Виктор Викторович

разработка и исследование функциональных диагностических тестов конвейеризованных risc процессоров

Специальность 05 13 15 — Вычислительные машины и системы

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2008

О 2 ОПТ 2003

003447829

Работа выполнена на кафедре электронной и компьютерной техники ГОУ ВПО «Дальневосточный государственный технический университет»

НАУЧНЫЙ РУКОВОДИТЕЛЬ ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ

ВЕДУЩАЯ ОРГАНИЗАЦИЯ

доктор технических наук, профессор Шаршунов Сергей Георгиевич

доктор технических наук Родионов Алексей Сергеевич

кандидат технических наук Майданов Юрий Сергеевич

ГОУ ВПО «Морской государственный университет им. адмирала Г И Невельского»

Защита состоится 28 октября 2008 г в 14 часов на заседании диссертационного совета Д 219 005 02 при ГОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики» (СибГУТИ) по адресу 630102, г. Новосибирск, ул Кирова, 86

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

Автореферат разослан «2Л» сентября 2008 г

Ученый секретарь диссертационного совета канд технических наук

—

Иван Иванович Резван

Общая характеристика работы

Актуальность темы. Публикация первых работ (S Thatte, J Abraham, С Robach, G Saucier), в которых представлен функциональный, основанный на выполнении тестовых программ подход к тестовому диагностированию процессоров, относится к началу 80-х годов 20-го века В 90-е годы развитие этого подхода привело к разработке методик (С Шаршунов, J Lee, J. Patel и др ), основанных на функциональных моделях и использующих особенности архитектуры процессоров, а так же к появлению автоматизированных методик разработки тестов (J Shen, J Abraham, К Batcher, С Papachristou), в которых наряду с использованием функциональных моделей применяется рандомизация В последние годы разработаны автоматизированные методики (V Vedula, J Abraham, F Corno, M Sonza Reorda, L Chen, S Dey и др ), характеризующиеся отказом от функциональных моделей и использующие точные регистровые и вентильные модели

Универсальные процессоры широко применяются в современной электронной аппаратуре Процессорные модули обычно интегрированы в состав систем на кристалле (СНК) Как правило, архитектуры современных универсальных процессоров наследуют архитектуру RISC (Reduced Instruction Set Computer) и конвейеризованы

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

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

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

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

Объект исследования диссертационной работы - универсальный процессор, принципы его разработки и методы его технической диагностики с использованием методов моделирования цифровых систем

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

Основные задачи работы:

- анализ существующих методик функционального диагностирования,

- разработка математических моделей и процедур функционального диагностирования конвейеризованных RISC процессоров;

- разработка процесса генерирования диагностических тестов,

- оценка качества разработанных тестов как покрытия одиночных константных неисправностей (ОКН) вентильных моделей процессоров средствами имитационного моделирования,

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

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

- Предложены функциональные модели и процедуры генерирования тестов механизмов хранения и передачи данных конвейеризованных RISC процессоров,

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

Практическая ценность работы заключается в разработке моделей, алгоритмов и процедур для генерирования функциональных диагностических тестов конвейеризованных RISC процессоров и разработке программного испытательного стенда для оценки качества этих тестов

Результаты работы внедрены на следующих предприятиях и организациях

1 в ГОУ ВПО «Дальневосточный государственный технический университет»

2 в ООО «СпецСвязьСервис» (г Артем, Приморский край)

Основные положения, выносимые на защиту:

- Методика функциональной декомпозиции процессоров с параллелизмом уровня системы команд для их тестового диагностирования,

- Функциональные модели и процедуры генерирования тестов механизмов хранения и передачи данных конвейеризованных RISC процессоров,

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

- Результаты оценки качества разработанных функциональных тестов,

Достоверность научных положений подтверждена теоретическим обоснованием разработанных моделей и методов и данными экспериментов

Апробация результатов работы. Основные положения и результаты работы представлялись и обсуждались на конференции ДВГТУ (г. Владивосток, 2004 г ), на российской конференции МСИТ (г Томск, 2005 г), на международных семинарах - EWDTW, DDECS (г. Алушта, 2004 г, г Одесса, 2005 г, г Прага, 2006 г , г Сочи, 2006 г), и симпозиуме - EWDTS (г Ереван, 2007 г)

Публикации по теме диссертации. Основные результаты и положения диссертации изложены в 2 статьях в научных изданиях, в том числе в 1 статье в

журнале из списка, рекомендованного ВАК, в 6 сборниках трудов конференций, в 1 тезисах конференции Всего опубликовано 9 печатных работ

Структура и объем работы. Основное содержание диссертации изложено на 104 страницах, состоит из введения, пяти глав и заключения и включает 25 рисунков и 9 таблиц 11 приложений на 24 страницах включают 3 рисунка и 13 таблиц Список литературы включает 44 наименования

Содержание работы

Во введении обоснованы актуальность работы, ее цель, решаемые задачи, отражены научная новизна и значимость результатов исследований

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

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

Специфика разработки и применения процессоров позволила выделить их в отдельный подкласс цифровых объектов диагностирования, для которых учитывается тот факт, что процессор предназначен для выполнения программы и управляется программой Это привело к разработке методов, основанных на выполнении процессором тестовых программ Выполнение тестовых программ проводится на рабочей частоте, поэтому занимает мало времени Для разработки тестовой программы может быть необязательным знание точной логической

схемы всего процессора, поэтому тест может разрабатываться параллельно с самим процессором

В работах по программному диагностированию процессоров можно выделить два основных подхода к разработке тестов Первый основан на использовании функциональных моделей (S Thatte, J Abraham и др.) Процессор рассматривается как система функций (передача, хранение, обработка данных и управление), связанная с архитектурой системы команд Тесты разрабатываются для каждой функции отдельно, в соответствии с ее математической моделью Тест процессора включает тесты всех его функций Этот подход позволяет разработать компактные тесты и не требует знания вентильной схемы. К его недостаткам относят значительные затраты усилий человека на разработку тестов и то, что при неизвестном алгоритме работы функции, тест для нее разработать нельзя В основе второго подхода (К Batcher, С Papachristou и др ) лежит идея, предполагающая, что с каждым структурным модулем процессора связана команда, группа команд или их последовательность, выполняя которые, можно проверить модуль Для разработки тестов проводится подробная классификация команд При необходимости большого перебора значений в полях команд применяется их рандомизация Подход универсален, разработка тестов может быть автоматизирована Знание вентильной структуры не требуется Недостатком является длительное время тестирования, связанное с рандомизацией тестовых последовательностей В последние годы разработано множество методик, комбинирующих различные подходы к диагностированию, в том числе использующие точные регистровые и вентильные модели процессора или его структурных модулей (V Vedula, J Abraham, L Chen, S Dey и др )

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

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

В работе эффективность рассматривается как совокупность двух показателей - длины тестовой программы (число ее команд) и качества теста Качество теста рассчитывается средствами имитационного моделирования как покрытие ОКН вентильной модели процессора

Во второй главе представлен подход к тестовому диагностированию процессоров RISC архитектуры с использованием функциональных моделей В качестве такого подхода использована методика, предложенная С Г Шаршу-новым и представленная в его работах (АиТ №11,2004 г и др)

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

Механизм хранения и передачи данных представляет функцию хранения и обмена данными между регистрами процессора Модель механизма включает все регистры, определенные его архитектурой, и передачи данных между ними под управлением программы Используется графическое представление модели механизма - граф регистровых передач (ГРП), строящийся на основе графа-модели архитектуры системы команд процессора путем исключения узлов, соответствующих обработке данных Регистрам соответствуют узлы ГРП, а передачам данных - направленные дуги, помеченные списками команд, активизирующими передачи Внешним устройствам и памяти соответствуют обобщенные вершины IN (вход) и OUT (выход) Последовательности команд в процессе выполнения активизируют определенные пути в ГРП. Механизм неисправен, если в результате активизации последовательностями команд (с тестовыми

операндами и адресами) подмножества путей ГРП, покрывающего все его дуги, хотя бы один операнд или адрес будет изменен Тестовые операнды и адреса -наборы «теста переноса», обнаруживающего произвольные сочетания констант О и 1 на разрядных линиях шин и на перемычках между этими линиями

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

Функциональная декомпозиция механизма управления производится до механизмов, соответствующих классам команд выборки регистров (класс обмена с внешней памятью, Load & Store, LS), межрегистрового обмена, управления обработкой данных (класс передачи и обработки данных, Transition & Manipulation, ТМ), управления выполнением команд (класс ветвлений, передачи управления, Control Transfer, СТ) Механизмы выборки регистров и межрегистрового обмена и отвечают за корректный выбор регистра-источника и регистра-приемника данных Модель неисправности этих механизмов предполагает, что вместо заданного полем команды регистра выбирается произвольное подмножество регистров из множества возможных Механизм управления обработкой данных отвечает за корректный выбор операций обработки пользовательских данных Модель неисправности механизма предполагает, что вместо заданной полем команды операции обработки данных выполняется произвольное подмножество операций из множества возможных Механизм управления выполнением команд включает механизм выполнения команд ветвлений и механизм

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

В третьей главе рассматривается процесс разработки функциональных тестов процессоров с использованием методики, представленной во второй главе Функциональные тесты были разработаны для двух MIPS подобных гипотетических архитектур RISC микропроцессоров Это 16 разрядная модификация процессора DP32 и 32 разрядный процессор DLX с сокращенной системой команд Целью разработки тестов является оценка эффективности методики и оценка возможности ее автоматизации Возможность автоматизации означает, что для всех включенных в процесс процедур, их содержательное описание должно быть достаточно определенным и полным, чтобы избежать двусмысленности в понимании, хорошо структурированным, чтобы его можно было легко формализовать, и не содержать противоречий

На рис 1 представлена общая схема процесса разработки тестов механизма хранения и передачи данных.

Построение графа-модели

Исключение функциональ ных углов

Построение тестовой последователь-

Построение тестовой программы

Спецификация архитектуры процессора Граф-модель архитектуры процессора Граф регистровых передач 1. Тестовая последовательность команд Тестовая программа

Рис 1 Разработка тестов механизма хранения и передачи данных

В ходе практической разработки тестов этих механизмов выявлена неполнота описания процедуры исключения функциональных узлов из графа-модели архитектуры при генерировании ГРП Неполнота описания связана с наличием контуров в графе-модели и произвольной последовательностью исключения узлов Полученный ГРП зависит от этой последовательности, не все регистры в нем могут оказаться соединенными путями с вершинами IN или OUT Чтобы исключить это противоречие, в работе предложены два способа генерирования ГРП на основе графа-модели Первый способ основан на введении порядка исключения узлов

- Все выходы на контуры с исключаемых узлов соединяются со входами путей от вершины IN

- Все входы в исключаемые узлы с контуров соединяются с произвольными выходами, кроме выходов на контуры

- Узлы исключаются в порядке, определяемом расстоянием от вершины IN

Входы с контуров и выходы на контуры определяются процедурой, основанной на построении кратчайшего остова графа-модели и последующего построения на его основе подграфа, сохраняющего частичную упорядоченность к вершинам IN и OUT

Второй способ основан на использовании свойств RISC архитектуры Множество регистров архитектуры таких процессоров ограничено большим числом однотипных регистров, управляемых и наблюдаемых с использованием команд класса LS Контуры в графе-модели обусловлены обработкой данных в этих регистрах с использованием команд класса ТМ В ходе генерирования ГРП все регистры соединяются с вершинами IN и OUT с учетом выполнения соответствующих команд класса LS

Первый способ предполагает выполнение более сложной процедуры генерирования теста Второй способ приводит к более длинному тесту

Процесс разработки тестов механизмов обработки данных учитывает обособленность этой группы механизмов в системах команд класса RISC Он предусматривает отдельный структурный синтез функций или наборов функций обработки и использование доступных средств автоматического генерирования тестов, основанных на модели ОКН Используются так же готовые тесты логического уровня для функций, реализованных модулями сторонних разработчиков Процедура перевода полученного теста логического уровня на уровень системы команд основана на свойствах систем команд класса RISC Тесту каждой из функций обработки однозначно соответствует подмножество команд класса ТМ Дополнив их командами обмена данными регистров с внешней памятью, получим тест механизма обработки данных процессора, соответствующий набору функций обработки

Разработка тестов механизмов управления заключается в генерировании всех тестов-индикаторов для диагностируемого процессора

В четвертой главе представлена оценка эффективности функциональных диагностических тестов, разработанных в соответствии с рассматриваемым подходом По данным исследований (J Abraham, L Chen, S Dey и др ), объем встроенного теста для несложных процессоров находится в пределах от 1 до 10 тыс команд Что касается качества, то оно считается приемлемым, когда тест покрывает более 90% ОКН вентильной модели процессора

В ходе экспериментов тестовые программы, полученные с использованием исследуемой методики разработки, применяются для проверки технического состояния моделей микропроцессоров Техническое состояние определяется с помощью модели системы диагностирования

В связи с отсутствием доступной по условиям лицензирования и типу используемой ЭВМ программы имитационного моделирования, способной моделировать систему и одновременно ОКН ее структурных элементов, испытательный стенд основан на логически обоснованной схеме совместной работы двух программ Это программа моделирования цифровых систем (ModelSim, QuartusII) и программа моделирования ОКН структурных моделей цифровых устройств Modus Используемый в экспериментах принцип взаимодействия программ состоит (см. рис 2)

- в фиксации последовательности битовых слов S(t) на контролируемых системой диагностики входах и выходах процессора в ходе моРис 2 Принцип взаимодействия программ

имитаторов делирования системы,

- в последующем использовании этой последовательности как входной для моделирования ОКН вентильной модели процессора

Для моделирования ОКН программой Modus необходима трансляция вентильной модели процессора с языка Verilog на язык Modus Корректность

трансляции модели доказывается выполнением двух процедур Первая состоит в подаче на входы обеих моделей одной и той же тестовой последовательности и сравнении последовательностей на выходах моделей Вторая - в определении качества теста При совпадении выходных последовательностей и качестве теста более 90% покрытия ОКН полагаем, что модели эквивалентны

Использование покрытия ОКН как показателя качества теста для верификации вентильных моделей обосновано способностью этого показателя характеризовать способность теста обнаруживать ошибки в структуре модели и ошибки в функциях базисных логических элементов модели

Общая схема испытательного стенда представлена на рис 3

вход

Объем функциональных тестов процессоров, разработанных по представленной в главах 2, 3 методике, ЭР32 - 1116 команд, БЬХ - 1269 команд Качество теста для модели последовательного процессора БР32 достаточно высоко и составляет 96,6% покрытия ОКН его вентильной модели Качество теста для модели конвейеризованного процессора ЭЬХ значительно ниже и составляет 71,87% покрытия ОКН Предполагаем, что снижение качества теста обусловле-

но наличием в конвейеризованном процессоре аппаратуры, ответственной за параллельную обработку команд

В пятой главе представлена методика тестового диагностирования механизма хранения и передачи данных конвейеризованных RISC процессоров, разработанная в соответствии с подходом к диагностированию механизмов процессора с параллелизмом уровня системы команд (конвейеризованный или су-перскапярный процессор)

Отличие архитектуры процессора с параллелизмом уровня системы команд от последовательного определяется необходимостью одновременного выполнения нескольких команд Особенности архитектуры такого процессора существование регистров для временного хранения данных частично выполненных команд и передач данных между этими регистрами, существование передач данных между регистрами, управляемых зависимостями по данным и по именам,

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

С учетом критерия корректности процессора с параллелизмом уровня системы команд, подход к его тестовому диагностированию предполагает отдельное диагностирование множества механизмов, отвечающих за корректное выполнение программ, не содержащих конфликтов, и механизмов разрешения конфликтов Иными словами механизмы, аналогичные последовательным процессорам, и характерные для параллельных проверяются отдельно Это соот-

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

В качестве модели механизма хранения и передачи данных конвейеризованного RISC процессора для программ без конфликтов принят ГРП уровня архитектуры системы команд В граф добавлена информация, позволяющая сгенерировать тест без конфликтов по данным и полученная из спецификации ар-

Входы и выходы узлов ГРП помечены номерами тактов (ступеней конвейера), в которые выполняется запись или чтение соответствующих регистров при выполнении команд На рис 4 узлам RO, R1 соответствуют регистры общего назначения, узлу PC - регистр счетчика команд, вершинам IN, OUT -внешние порты, Add, Sub, Ld, St, В, Bi - команды процессора

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

В построенном ГРП множество R регистров, обращение к которым может привести к конфликтам по данным, включает все регистры Ri с номерами тактов записи m и чтения п, для которых n<m Конфликт по данным возникает, когда число к других команд, находящихся в программе между командами, зависимыми по данным, удовлетворяет неравенству 0<k<(m-n) Конфликт устраняется добавлением команд простоя между зависимыми командами Число команд простоя Idata, которое следует добавить Idata = m - n - к Таким образом,

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

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

В качестве модели механизма хранения и передачи данных, управляемого зависимостями по данным, принят граф-модель (ГМ) архитектуры конвейера (см рис 5)

Рис 5 Упрощенный граф-модель архитектуры конвейера RISC процессора Он получается из ГМ архитектуры системы команд процессора объединением находящихся на одной ступени конвейера групп узлов в общие функциональные узлы Условием объединения является обращение группы узлов к регистру конвейера в одном такте Модель включает конвейерные регистры и два типа функциональных узлов - узлы хранения данных и узлы обработки данных На рис 5 узел RegFile соответствует узлу хранения данных, ALU - узлу обработки данных, узлы RSI, RS2, RDI - RD4 — конвейерным регистрам, IN и OUT - внешним портам, Add, Sub, Ld, St - команды Входы и выходы узлов хранения данных помечены номерами ступеней конвейера, в которые происходит запись или чтение данных

Ld, Add, Sub

Диагностирование механизма заключается в активизации последовательностями команд (с тестовыми операндами и адресами) всех путей передачи данных между узлами графа-модели в случае конфликта (обозначены на рис 5 пунктиром). Идея создания конфликта состоит в построении последовательности команд, где первая записывает тестовые данные в узел хранения, а следующие за ней их читают для выполнения операции или вывода на внешние порты Между командами записи и чтения данных в тестовую процедуру вставляется последовательность команд простоя Наибольшее число I(,az команд простоя при проверке конфликтов типа RAW (Read After Write) для узла хранения Ihaz= ш - п - 1, где шип- номера такта записи и чтения этого узла, соответственно В тест включаются все последовательности команд с числом

КОМаНД ПрОСТОЯ ОТ НуЛЯ ДО Ihaz

Разработанные по этой методике функциональные модели интегрированы в общую методику диагностирования RISC процессоров, качество тестов проверено экспериментально Объем нового теста конвейеризованного процессора DLX - 2871 команда Качество теста достигает 95,5% покрытия ОКН его вентильной модели

В заключении приводится обсуждение полученных результатов и выводы по работе

Основные результаты и выводы диссертации:

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

2 Разработаны функциональные модели и процедуры тестового диагностирования механизмов хранения и передачи данных конвейеризованных RISC процессоров

3 Разработан общий процесс генерирования диагностических тестов

4 Разработана и обоснована схема испытательного стенда для определения качества функциональных диагностических тестов

5 С использованием экспериментального прототипа этого стенда оценена эффективность подхода к тестовому диагностированию

6 Представленная методика функционального тестового диагностирования позволяет разработать на ее основе автоматизированный процесс построения тестов, использующий спецификацию архитектуры системы команд как основные исходные данные

7 По результатам выполнения этих тестов можно с высокой степенью достоверности судить о техническом состоянии процессора

Основные публикации по теме диссертации

1 Белкин В В Использование средств автоматизации проектирования для разработки функциональных тестов микропроцессоров // Труды ДВГТУ — Владивосток, 2005 -Вып 140 - С 81-90

2 Белкин В В , Шаршунов С Г Разработка функциональных тестов конвейеризованных процессоров на основе высокоуровневых моделей // Приборы и системы Управление, контроль, диагностика -2007 -№4 - С 22-27

3 Белкин В В , Шаршунов С Г Функциональное тестирование микропроцессора пример // Сб трудов III всеросс конф Молодежь и совр информ тех-нол -Томск,2005.-С 264-265

4 Белкин В В , Шаршунов С Г Построение теста проверки работоспособности микропроцессора DP32 // Сб трудов научн конф ДВГТУ Вологдинские чтения - Владивосток, 2004 - С 17

5 Belkin V , Sharshunov S Functional Partition Based Testing of Current Microprocessors//Proc IEEE East-West Design & Test Symposium (EWDTS) -2007 -P 57-62

6 Belkin V , Sharshunov S High Level Models Based Functional Testing of Pipelined Processors // Proc IEEE East-West Design & Test Workshop (EWDTW) -2006 -P 76-81

7 Belkin V V , Sharshunov S G ISA Based Functional Test Generation with Application to Self-Test of RISC Processors // Proc IEEE Design Diagnostics of Electronic Circuits & Systems (DDECS) - 2006 - P 75-76

8 Sharshunov S G , Belkin V V Functional Testing of Microprocessors Case Study // Proc IEEE East-West Design & Test Workshop (EWDTW) - 2004 P - 135141

9 Sharshunov S G , Belkin V V , Rudnitskaya V P Detecting Malfunctions of Current Processor Control Hardware // Proc IEEE East-West Design & Test Workshop (EWDTW) -2005 -P 169-174

Белкин Виктор Викторович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ФУНКЦИОНАЛЬНЫХ ДИАГНОСТИЧЕСКИХ ТЕСТОВ КОНВЕЙЕРИЗОВАННЫХ RISC ПРОЦЕССОРОВ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 19 09 2008 Формат 60 х 84/к,

Уч изд л 1,0 Уел печ л 1,25 Тираж! 00 экз Заказ Ns 520

Отпечатано в типографии ИПК МГУ им адм Г И Невельского 690059 г Владивосток, ул Верхнепортовая, 50а

ОГЛАВЛЕНИЕ.

СПИСОК ТЕРМИНОВ И СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. ВЫБОР МЕТОДИКИ ТЕСТОВОГО

ДИАГНОСТИРОВАНИЯ ПРОЦЕССОРОВ.

1.1 Основные определения.

1.2 Тестовое диагностирование процессоров в системах на кристалле.

1.3 Архитектура и тестовое диагностирование реконфигурируемых систем.

1.4 Методы тестового диагностирования процессоров.

1.5 Оценка существующих методик программного тестового диагностирования.

ГЛАВА 2. МЕТОДИКА ФУНКЦИОНАЛЬНОГО ТЕСТОВОГО

ДИАГНОСТИРОВАНИЯ ПРОЦЕССОРОВ.

2.1 Архитектура системы команд процессоров.

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

2.2.1 Функциональная декомпозиция процессора.

2.2.2 Механизм хранения и передачи данных.

2.2.3 Механизмы обработки данных.

2.3 Методика функционального тестового диагностирования механизмов управления.

2.3.1 Функциональная декомпозиция механизмов управления.

2.3.2 Механизм управления передачей данных.

2.3.3 Механизм управления обработкой данных.

2.3.4 Механизм управления выполнением команд.

ГЛАВА 3. РАЗРАБОТКА ФУНКЦИОНАЛЬНЫХ ТЕСТОВ

МИКРОПРОЦЕССОРОВ.

3.1 Особенности архитектур диагностируемых процессоров

3.2 Разработка тестов механизмов хранения и передачи данных.

3.3 Разработка тестов механизмов обработки данных.

3.4 Разработка тестов механизмов управления.

ГЛАВА 4. ОЦЕНКА ЭФФЕКТИВНОСТИ ФУНКЦИОНАЛЬНЫХ

ТЕСТОВ СРЕДСТВАМИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.

4.1 Эффективность функциональных тестов.

4.2 Принципы работы программного испытательного стенда

4.3 Разработка испытательного стенда с использованием совместной работы двух программ-имитаторов.

4.3.1 Постановка задачи.

4.3.2 Обоснование схемы совместной работы программ-имитаторов

4.3.3 Оценка качества теста моделированием константных неисправностей.

4.3.4 Схема испытательного стенда.

4.4 Оценка эффективности функциональных диагностических тестов на моделях процессоров.

ГЛАВА 5. ФУНКЦИОНАЛЬНОЕ ТЕСТОВОЕ

ДИАГНОСТИРОВАНИЕ МЕХАНИЗМОВ ХРАНЕНИЯ И ПЕРЕДАЧИ ДАННЫХ КОНВЕЙЕРИЗОВАННЫХ RISC ПРОЦЕССОРОВ.

5.1 Функциональная декомпозиция архитектуры.

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

5.3 Особенности конвейерной архитектуры, существенные для разработки тестов.

5.4 Общая функциональная модель механизма и модель неисправности.

5.5 Тестовое диагностирование механизма, управляемого полями команд.

5.6 Тестовое диагностирование механизма управляемого зависимостями по данным.

5.7 Оценка эффективности функциональных тестов на модели

Актуальность темы. Публикация первых работ, [16, 20] и др., в которых представлен функциональный, основанный на выполнении тестовых программ подход к тестовому диагностированию процессоров, относится к началу 80-х годов 20-го века. В 90-е годы развитие этого подхода привело к разработке методик, [4, 32] и др., основанных на функциональных моделях и использующих особенности архитектуры процессоров, а так же к появлению автоматизированных методик разработки тестов [22, 37], в которых наряду с использованием функциональных моделей применяется рандомизация. В последние годы разработаны автоматизированные методики [27, 28, 38, 39], характеризующиеся отказом от функциональных моделей и использующие точные регистровые и вентильные модели.

Разнообразие прикладных вычислительных задач, растущий спрос на электронные вычислительные средства и прогресс в технологии производства полупроводников вызвали потребность в массовом производстве и гибком конфигурировании этих средств. Универсальные и специализированные процессоры являются неотъемлемой частью современной электронной аппаратуры. Сегодня процессорные модули обычно интегрированы в состав систем на кристалле, которые могут включать один или несколько модулей универсальных и специализированных процессоров. Как правило, архитектуры современных универсальных процессоров наследуют архитектуру RISC и конвейеризованы. Более того, развитие других архитектур часто идет по пути использования принципов RISC на уровне микроархитектуры. Проектирование современных процессоров и систем на кристалле требует значительных затрат времени и других ресурсов, поэтому в проектируемых системах часто используются готовые функциональные модули, разработанные ранее для других систем.

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

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

Актуальность настоящего исследования вызвана потребностью в разработке и внедрении методик функционального тестового диагностирования конвейеризованных RISC процессоров, использующих архитектуру системы команд как исходные данные. Исследование развивает методики разработки тестов последовательных процессоров, основанные на- функциональных моделях и использующие особенности их архитектуры, применяя их для тестового диагностирования конвейеризованных RISC процессоров.

Объект исследования диссертационной работы — универсальный процессор, принципы его разработки и методы его технической диагностики с использованием методов моделирования цифровых систем.

Цель работы. Целью диссертационной работы является разработка методики тестового диагностирования конвейеризованных универсальных RISC процессоров, основанной на функциональном подходе к разработке тестов. Требованиями к методике являются: возможность ее реализации как автоматизированного процесса разработки тестовых программ; использование архитектуры системы команд как основных исходных данных для разработки тестов.

Основные задачи работы:

- анализ существующих методик функционального диагностирования;

- разработка математических моделей и процедур функционального диагностирования конвейеризованных RISC процессоров;

- разработка процесса генерирования диагностических тестов;

- оценка качества разработанных тестов как покрытия одиночных константных неисправностей вентильных моделей процессоров средствами имитационного моделирования;

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

Научная новизна заключается в следующих результатах работы:

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

- Предложены функциональные модели и процедуры генерирования тестов механизмов хранения и передачи данных конвейеризованных RISC процессоров;

- Предложен принцип взаимодействия функционально дополняющих друг друга программ-имитаторов. По этому принципу разработан прототип испытательного стенда, на котором оценено качество тестов. Практическая ценность работы заключается в разработке моделей, алгоритмов и процедур, являющихся основой процесса генерирования функциональных диагностических тестов конвейеризованных RISC процессоров и разработке программного испытательного стенда для оценки качества этих тестов:

- Предложены функциональные модели и разработаны процедуры тестового диагностирования механизмов хранения и передачи данных конвейеризованных RISC процессоров;

- Предложена и экспериментально подтверждена методика разработки тестов механизма обработки данных;

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

Основные положения, выносимые на защиту:

- Методика функциональной декомпозиции процессоров с параллелизмом уровня системы команд для их тестового диагностирования;

- Функциональные модели и процедуры тестового диагностирования механизмов хранения и передачи данных конвейеризованных RISC процессоров;

- Принцип взаимодействия дополняющих друг друга функционально программ-имитаторов; схема испытательного стенда для определения качества функциональных диагностических тестов;

- Результаты оценки качества разработанных в соответствии с методикой функциональных тестов;

Достоверность научных положений подтверждена теоретическим обоснованием разработанных моделей и методов и данными экспериментов.

Апробация результатов работы. Основные положения и результаты работы представлялись и обсуждались на научной конференции ДВГТУ (г. Владивосток, 2004 г.), на III всероссийской научно-практической конференции студентов МСИТ (г. Томск, 2005 г.), на четырех международных семинарах под патронажем IEEE - EWDTW, DDECS (г. Алушта, 2004 г., г. Одесса, 2005 г., г. Прага, 2006 г., г. Сочи, 2006 г.), на международном симпозиуме под патронажем IEEE — EWDTS (г. Ереван, 2007 г.).

По результатам работы реализован экспериментальный прототип программного испытательного стенда и оценена эффективность разработанного подхода к тестовому диагностированию конвейеризованных RISC процессоров.

Публикации по теме диссертации. Основные результаты и положения диссертации изложены в 2 статьях в научных изданиях, в том числе в 1 статье в рецензируемом журнале из списка, рекомендованного ВАК, в 6 сборниках трудов конференций, в 1 тезисах конференции. Всего опубликовано 9 печатных работ [12, 13, 21, 23,24, 25, 35, 36].

Работа организована следующим образом:

- В первой главе по материалам журнала «Автоматика и телемеханика» и трудам конференций по технической диагностике (ITC, DAC, VTS и др.) проведена оценка требований к разрабатываемой методике тестового диагностирования процессоров и существующих методик диагностирования.

- Во второй главе представлен подход к тестовому диагностированию процессоров RISC архитектуры с использованием функциональных моделей.

- В третьей главе рассматривается процесс разработки функциональных тестов процессоров с использованием методики, представленной во второй главе, проводится анализ этой методики.

- В четвертой главе представлена экспериментальная оценка эффективности разработанных тестов на моделях процессоров, представлена и обоснована схема программного испытательного стенда. Эффективность рассматривается как совокупность двух показателей — длины тестовой программы (число ее команд) й качества теста.

- В пятой главе представлена методика тестового диагностирования механизма хранения и передачи данных конвейеризованных RISC процессоров. Методика разработана в соответствии с предложенным подходом к диагностированию механизмов процессора с параллелизмом уровня системы команд (конвейеризованный или суперскалярный процессор).

Основное содержание диссертации изложено на 105 страницах и включает 25 рисунков и 9 таблиц. 11 приложений на 24 страницах включают 3 рисунка и 13 таблиц. Список литературы включает 44 наименования.

Выводы по работе:

- Методика тестового диагностирования, основанная на функциональном подходе к разработке тестов, позволяет разрабатывать достаточно эффективные тесты конвейеризованных RISC процессоров, основываясь на системе команд как основных исходных данных для разработки тестов.

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

- Разработанные по методике функциональные тесты могут с успехом применяться для задач верификации уже на этапе проектирования процессоров, что показано в ходе разработки испытательного стенда.

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

ЗАКЛЮЧЕНИЕ

1. Нормативные документы

2. Техническая диагностика Термины и определения: ГОСТ 20911-89. Утв. и введ. Пост. гос. ком. по управл. кач. прод. и ст. от 26.12.89 № 4143.

3. AMBA Specification, Rev. 2.0. ARM Ltd., www.arm.com, 1999. - 230 p.

4. IEEE P1500. -http://grouper.ieee.org/groups/P1500/1. Книги

5. Чипулис В.П., Шаршунов С.Г. Анализ и построение тестов цифровых программно-управляемых устройств. — М.: Энергоатомиздат, 1992. — 224 с.

6. Яблонский С.В. Введение в дискретную математику: Учеб. Пособие для вузов. М.: Высш. Шк., 2002. - 384 с.

7. Abramovici М., Breuer М.А., Friedman A.D. Digital Systems Testing and Testable Design. New York: IEEE Press, 1995. - 652 p.

8. Ashenden P.J. The VHDL Cookbook (first edition). Adelaide: Dept. Computer Science, University of Adelaide, 1990. - 107 p.

9. Borger E., Stark R. Abstract State Machines: A Method for High-Level System Design and Analysis. Berlin: Springer-Verlag, 2003. - 438 p.

10. Hennessy J.L., Patterson D.A. Computer Architecture: A Quantitative Approach (second edition). — San Francisco: Morgan Kaufmann Publishers, 1996. 785 p.

11. Белкин В.В. Использование средств автоматизации проектирования для разработки функциональных тестов микропроцессоров // Труды ДВГТУ. — Владивосток, 2005. Вып. 140. - С. 81-90.

12. Белкин В.В., Шаршунов С.Г. Разработка функциональных тестов конвейеризованных процессоров на основе высокоуровневых моделей // Приборы и системы. Управление, контроль, диагностика. — 2007. — №4. — С 22-27.

13. Шаршунов С.Г. Разработка функциональных тестов RISC микропроцессоров // Автоматика и телемеханика. 2004. - № 11. - С. 174-183.

14. Berezin S. Verification of Out-Of-Order Processor Designs Using Model Checking and a Light-Weight Completion Function / Berezin S., Clarke E., Biere A., Zhu Y. // Formal Methods in System Design. 2002. - V. 20. - P. 159-186.

15. Brahme D., Abraham J.A. Functional Testing of Microprocessors // IEEE Trans, on Computers. 1984.-Vol. C-33(6).-P. 475-485.

16. Butel P. Managing Partial Dynamic Reconfiguration in Virtex-II Pro FPGAs // Xcell Journal. Xilinx, Inc., Fall 2004. - Issue 50. - P. 32-37.

17. S.Maxwell P.C., Aitken R.C. Test Sets and Reject Rates: All Fault Coverages Are Not Created Equal // IEEE Design & Test of Computers. March 1993. - V. 10. Issue l.-P. 42-51.

18. Roelandts W. Focusing on Programmable Technologies // Xcell Journal. Xilinx, Inc., Winter 2004. - Issue 51. - P. 6-16.

19. Thatte S.M., Abraham J.A. Test Generation for Microprocessors // IEEE Trans, on Computers. 1980. -V. C-29(6). - P. 429-441.1. Материалы конференций

20. Белкин B.B., Шаршунов С.Г. Функциональное тестирование микропроцессора: пример // Сб. трудов III всеросс. конф. Молодежь и совр. информ. технол. — Томск, 2005. С. 264-265.

21. Batcher К., Papachristou С. Instruction Randomization Self Test for Processor Cores //Proc. IEEE VLSI Test Symposium (VTS). 1999. - P. 34-40.

22. Belkin V., Sharshunov S. Functional Partition Based Testing of Current Microprocessors // Proc. IEEE East-West Design & Test Symposium (EWDTS). -2007.-P. 57-62.

23. Belkin V., Sharshunov S. High Level Models Based Functional Testing of Pipelined Processors // Proc. IEEE East-West Design & Test Workshop (EWDTW). 2006. - P. 76-81.

24. Belkin V.Y., Sharshunov S.G. ISA Based Functional Test Generation with Application to Self-Test of RISC Processors // Proc. IEEE Design Diagnostics of Electronic Circuits & Systems (DDECS). 2006. - P. 75-76.

25. Chen L., Dey S. DEFUSE: A Deterministic Functional Self-Test Methodology for Processors // Proc. IEEE VLSI Test Symposium. (VTS). 2000. - P. 255-262.

26. Chen L. A Scalable Software-Based Self-Test Methodology for Programmable Processors / Chen L., Ravi S., Ranghunathan A., Dey S. // Proc. ACM/IEEE Design Automation Conf. (DAC). 2003. - P. 548-553.

27. Corno F. Fully Automatic Test Program Generation for Microprocessor Cores / Corno F., Gumani G., Sonza Reorda M., Squillero G. // Proc. IEEE/ACM Design Automation & Test in Europe Conf. (DATE). 2003. - V. 1. - P. 11006-11011.

28. Kranitis N. Low-Cost Software-Based Self-Testing of RISC Processor Cores / Kranitis N., Xenoulis G., Gizopoulos D., Paschalis A., Zorian Y. // Proc. IEEE/ACM Design Automation & Test in Europe Conf. (DATE). 2003. - Vol. l.-P. 10714-10719.

29. Lee J., Patel J.H. An Instruction Sequence Assembling Methodology for Testing Microprocessors // Proc. IEEE Intl Test Conf (ITC). 1992. - P. 49-58.

30. Marinissen E.J., Zorian Y. System Chip Test: How Will It Impact Your Design? // Proc. ACM/IEEE Design Automation Conf. (DAC). 2000. - P. 136-141.

31. Mishra P., Dutt N. Graph-based Functional Test Program Generation for Pipelined Processors // Proc. ACM/IEEE Design Automation Conf. (DAC). 2004. - P. 182-187.

32. Sharshunov S.G., Belkin V.V. Functional Testing of Microprocessors: Case Study // Proc. IEEE East-West Design & Test Workshop (EWDTW). 2004. P. - 135141.

33. Sharshunov S.G., Belkin V.V., Rudnitskaya V.P. Detecting Malfunctions of Current Processor Control Hardware // Proc. IEEE East-West Design & Test Workshop (EWDTW). 2005. - P.169-174.

34. Shen J., Abraham J.A. Native Mode Functional Test Generation for Processors with Applications to Self Test and Design Validation // Proc. IEEE Intl Test Conf. (ITC). — 1998. — P. 990-999.

35. Tupuri R., Abraham J.A. A Novel Functional Test Generation Method for Processors using Commercial ATPG // Proc. IEEE Intl Test Conf. (ITC). 1997. -P. 743-752.

36. Vedula V.M., Abraham J.A. FACTOR: A Hierarchical Methodology for Functional Test Generation and Testability Analysis // Proc. IEEE/ACM Design Automation & Test in Europe Conf. (DATE). 2002. - P. 730-735.

37. Modelsim SE User's Manual, V5.7. / Model Technology. Wilsonville, OR, 2003.-621 p.1. Интернет ссылки43.www.altera.com44.www. xilinx.com

38. Формальная модель зависимости графа регистровых передач от порядка устранения узлов в графе-модели

39. Модель операции исключения в случае, например, когда d+(w) = d"(w) = n: Vuh v;er(w): (VjRw & wRuj) =5- (VjRuj), i = 1, . n, где T(w) множество смежности узла w. Рассмотрим пример:

40. При использовании дополненных правил исключения функциональных узлов (раздел 3.2) все регистры (не исключаемые узлы) ГРП, полученного в результате операции исключения узлов, останутся соединенными путями с вершинами IN и OUT.1. Доказательство:

41. Все правила действуют одновременно и для всех исключаемых узлов, следовательно свойство 4 для ГРП выполняется. Теорема доказана.