ПРОГРАММИРОВАНИЕ, 2010, No 1, с. 40-49
ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 004.92+004.94
ГЕНЕРАЦИЯ ТЕСТОВЫХ ДАННЫХ ДЛЯ ТЕСТИРОВАНИЯ МЕХАНИЗМОВ КЭШИРОВАНИЯ И ТРАНСЛЯЦИИ АДРЕСОВ МИКРОПРОЦЕССОРОВ
© 2010 г. Е. В. Корныхин
Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: kornevgen@ispras.ru Поступила в редакцию 10.04.2009 г.
В статье рассматривается задача генерации тестовых данных для системного функционального тестирования микропроцессоров (core-level verification), а именно, задача построения тестовой программы по заданной ее абстрактной форме (тестовому шаблону). Для решения этой задачи в работе предложен алгоритм, сводящий ее к задаче разрешения ограничений. В данной статье рассматриваются вопросы тестирования инструкций работы с памятью (при этом учитываются такие особенности микропроцессора, как кэширование и трансляция адресов).
1. ВВЕДЕНИЕ
Базовым компонентом многих вычислительных систем являются микропроцессоры, выполняющие управляющие функции. Тестирование микропроцессоров является важной задачей, которой и посвящена данная работа.
Как и для программных систем, для микропроцессоров может быть проведено функциональное тестирование, а именно, тестирование, целью которого является проверка выполнения микропроцессором функциональных требований. Под функциональными требованиями на системном уровне (в противовес модульному уровню) понимается выполнение инструкциями микропроцессора семантики, заявленной в архитектуре микропроцессора [1]. При этом проверяемая семантика не должна содержать особенностей конкретной реализации в конкретном микропроцессоре, она не должна быть избыточной.
В рамках системного тестирования микропроцессор рассматривается как единая система, входными данными для которой являются машинные программы, загруженные в память (далее такие программы будут называться тестовыми программами). В рамках функционального тестирования эти программы исполняют-
ся, процесс исполнения протоколируется и затем анализируется. При этом проверяется выполнение функциональных требований при исполнении тестовой программы.
Тестовые программы могут быть построены на основе модели микропроцессора: она включает в себя модель инструкций микропроцессора -их сигнатуру (имя и параметры), ветви функциональности - и состояние микропроцессора. Сначала тестовые программы систематически строятся в абстрактном виде (в виде тестового шаблона) - с заданной последовательностью инструкций, но без без конкретных параметров и без необходимой инициализации состояния микропроцессора перед исполнением этих инструкций. Затем тестовые шаблоны уточняются до тестовых программ, при этом происходит выбор параметров инструкций и построение инструкций инициализации состояния микропроцессора. Решение этой задачи для инструкций, затрагивающих лишь регистры, хорошо известно [2-4]. Однако модель состояния микропроцессора сильно усложняется, если тестовый шаблон включает инструкции, работающие с кэшпамятью [5], что усложняет и построение тестовых программ. Этой проблеме посвящена данная статья.
тестовые шаблоны
описание архитектуры микропроцессора
этап 1: подготовка тестовых шаблонов
тестовые программы
генератор тестовых анных
начальное состояние микропроцессора
этап 2: генерация тестовых программ
генерация
тестовых
данных
Рис. 1. Генерация тестовых программ на основе тестовых шаблонов.
2. ОБЗОР РАБОТ ПО СИСТЕМНОМУ ФУНКЦИОНАЛЬНОМУ
ТЕСТИРОВАНИЮ МИКРОПРОЦЕССОРОВ
В настоящее время в практике системного функционального тестирования микропроцессоров можно выделить следующие подходы к построению тестовых программ:
• Ручная разработка тестовых программ, хоть и практически неприменима для полного тестирования микропроцессора, все же может применяться для тестирования особых, крайних случаев.
• Тестирование с использованием кросс-компиляции применяется часто из-за невысокой сложности его проведения: после согласования спецификации микропроцессора можно начинать делать кросскомпилятор, а код, предназначенный для кросс-компиляции, уже готов. Однако гарантировать полноту такое тестирование не может.
• Случайная генерация тестовых программ применяется также часто в силу простоты автоматизации. Сгенерированные таким образом тестовые программы позволяют быстро обнаружить простые ошибки, однако не гарантируют полноты тестирова-
ния. Разрабатываются и более сложные варианты случайной генерации [6].
• Генерация тестовых программ на основе тестовых шаблонов предполагает разделение процесса генерации тестовой программы на два этапа (см. рис. 1): на первом подготавливаются тестовые шаблоны -абстрактные представления тестовых программ (в тестовых шаблонах для параметров инструкций вместо значений указываются ограничения на значения) - а на втором этапе по тестовым шаблонам генерируются тестовые программы. Второй этап включает в себя генерацию тестовых данных, т.е. генерацию параметров инструкций (параметров-констант) и начальных значений регистров, ячеек кэш-памяти, строк TLB и т.д. Конкретные регистры-параметры инструкций либо заданы в тестовом шаблоне (и они же должны быть в тестовой программе) [13], либо не заданы в тестовом шаблоне (в этом случае выбор регистров делает генератор тестовых данных) [2].
Тестовые шаблоны описывают последовательность инструкций, параметры инструкций с указанием происходящих событий (например, переполнение, промахи или попадания в кэшпамяти). В качестве параметров инструкции мо-
гут быть явно указаны регистры и константы, а может быть предоставлена возможность инструменту самому подобрать регистры. Последовательность инструкций чаще всего задана явно. Необходимость в тестовом шаблоне обычно возникает тогда, когда тестирование проводится нацеленным образом и эта цель выражена последовательностью инструкций, каждая из которых должна быть исполнена заданным образом. Пример тестового шаблона:
REGISTER ax:32; REGISTER bx:32; REGISTER cx:32; LW cx, ax, 0 @ l1Hit SD ax, bx, 2 @ l1Miss
В этом тестовом шаблоне 2 инструкции - LW и SD. У каждой инструкции указаны параметры - 2 регистра и константа - и после знака '@' информация о том, как должна быть исполнена инструкция (ограничение на значения параметров инструкции и состояние микропроцессора): l1Hit - c кэш-попаданием (при загрузке из памяти данные по требуемому физическому адресу в момент исполнения инструкции должны присутствовать в кэш-памяти) и l1Miss -c кэш-промахом (при загрузке из памяти данные по требуемому физическому адресу в момент исполнения инструкции не должны присутствовать в кэш-памяти). Чтобы получить тестовую программу по этому шаблону, достаточно задать начальные значения регистров ax, bx и cx и той части кэш-памяти, с которой работают инструкции - это и будут тестовые данные для данного шаблона. Это можно сделать, добавив перед тестовым шаблоном инструкции инициализации состояния микропроцессора (загрузка данных в регистры, последовательность инструкций загрузки данных в память, которые обратятся в кэш-память, TLB и т.п.).
Полученную тестовую программу можно исполнить и проверить, совпадает ли поведение каждой инструкции с тем, что было заявлено в тестовом шаблоне.
Обратимся к задаче генерации тестовых данных. Среди известных работ можно выделить следующие методы ее решения:
• комбинаторные техники;
• решение задачи ATPG;
• разрешение ограничений.
Комбинаторные техники применимы в случае простых тестовых шаблонов. Такие тестовые шаблоны включают лишь простые ограничения, а именно, указание области значений переменной. Причем все значения этой области в тестовой программе равноправны. Техника хоть и простая, но довольно ограниченная в применении, поскольку не всегда получается привести ограничения на переменные к такому простому виду. В работе исследователей из Fujitsu Lab [7] предлагается описать тестовые программы в виде выражений (Test Specification Expressions, TSE), а инструкции микропроцессора - на языке ISDL. Специальный генератор строит тестовые программы, удовлетворяющие TSE. Kohno и Matsumoto [8] рассматривают задачу верификации конвейерных микропроцессоров, используя для этого генерацию тестовых программ с помощью тестовых шаблонов. Области значений переменных в таких шаблонах складываются из регистров и числовых констант.
Исследователи из Politecnico di Milano [9] предложили генеровать тестовые данные с использованием техник решения задачи ATPG (Automatic Test Pattern Generation). ATPG - задача поиска значений входных сигналов ("векторов") схемы с целью поиска ее некорректного поведения. ATPG чаще применяется для модульного тестирования, если известна RTL-модель микропроцессора. Задача ATPG известна давно, и для ее решения существуют (в том числе коммерческие) инструменты. Для применения ATPG при генерации тестовых программ необходимо, чтобы RTL-модель микропроцессора была готова к моменту генерации тестовых данных. Кроме того, использование такой методики именно для функционального тестирования ограничено, поскольку нарушено требование неизбыточности задания семантики инструкций -наличие RTL-модели является лишним, дополнительным требованием к семантике и требует
дополнительных трудозатрат на свою подготовку.
Наиболее впечатляющих результатов достигают инструменты, использующие для генерации тестовых данных разрешение ограничений. Ограничение, с логической точки зрения, - это то же, что и предикат, а задача разрешения ограничений - то же, что и задача выполнимос-
ти системы предикатов, но для решения этой задачи применяются специальные алгоритмы [10]. В работе [2] исследователей из Китайского Национального Университета технологий безопасности описывается инструмент MAATG. Тестовый шаблон для него может содержать лишь ограничения равенства или неравенства значений и указание области значений переменной. Для задания архитектуры микропроцессора используется описание на языке EXPRESSION. Другой инструмент - Genesys-Pro [11] - позиционируется компанией IBM как разработка, впитавшая лучшее из разработок последних 20 лет. Тестовые шаблоны позволяют задавать тестовые программы пе
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.