Развитие спецификаций JTAG для отладки аппаратного и программного обеспечения

УДК 004.416.2

РАЗВИТИЕ СПЕЦИФИКАЦИЙ JTAG ДЛЯ ОТЛАДКИ АППАРАТНОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

В.А. Галатенко, д.ф.-м.н.; К.А. Костюхин, к.ф.-м.н.; Н.В. Шмырев, к..ф.-м.н.

В работе дается краткий обзор базовых спецификаций JTAG, новых спецификаций cJTAG и некоторых корпоративных расширений, помогающих использовать JTAG в качестве отладочного интерфейса. Ключевые слова: JTAG, cJTAG, EJTAG, отладка.

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

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

В 1985 году для разработки стандартов тестирования интегральных схем и печатных плат была образована Объединенная группа тестового доступа (Joint Test Access Group (,JTAG)). Спустя почти 15 лет предложения этой группы оформились в виде стандарта IEEE STD. 1149.1-2001 (IEEE Standard Test Access Port and Boundary Scan Architecture [1]). Параллельно ряд других групп и корпораций, например MIPS, развивали свои стандарты и спецификации, такие как Enhanced JTAG (EJTAG [2]). Развитие спецификаций JTAG продолжалось и в рамках IEEE: в феврале 2010 года была опубликована новая, значительно расширенная версия стандарта IEEE Std. 1149-7.2009 (IEEE Standard for Reduced-Pin and Enhanced-Functionality Test Access Port and Boundary-Scan Architecture [3]).

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

Стандарт IEEE 1149.1 - базовые спецификации JTAG

Стандарт IEEE 1149.1 создан для поддержки тестирования функциональности аппаратных компонентов, их взаимосвязей и взаимодействий в составных аппаратных продуктах. Объектом стандартизации является тестирующее устройство.

Тестирующее устройство, соответствующее стандарту IEEE 1149.1, содержит один регистр инструкций, несколько регистров тестовых данных, а также контроллер порта тестового доступа (Test Access Port (TAP)), управляющий всеми операциями по тестированию.

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

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

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

Стандартом предусмотрены следующие интерфейсные сигналы на шине TAP (направление указывается с точки зрения управляющего устройства шины TAP):

1) тестовый тактирующий сигнал (Test Clock (TCK), последовательные тактирующие сигналы, выходной);

2) выбор тестового режима (Test Mode Select (TMS), переходы в конечном автомате JTAG, выходной);

3) исходные тестовые данные (Test Data Input (TDI), доставляются к тестируемым компонентам, выходной);

4) выходные тестовые данные (Test Data Output (TDO), извлекаются из тестируемых компонентов, входной);

5) перезагрузка тестов (Test Reset (nTRST), необязательный сигнал для асинхронной инициализации тестов, выходной).

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

Функционирование JTAG определяется конечным автоматом, реализованным в контроллере TAP. Сигнал TMS служит для выбора маршрута в конечном автомате JTAG [1].

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

• BYPASS. При выборе для устройства данной инструкции однобитный регистр обхода подключается в качестве регистра тестовых данных. Это позволяет укоротить цепочку сканирования, состоящую из нескольких последовательных устройств, тем самым ускоряя тестовый доступ. Устройство в режиме обхода не должно выполнять никаких тестовых операций. Кодом операции для инструкции обхода могут служить все единицы (для 4-битного регистра инструкций - 0xF), но и другие коды могут отображаться на эту инструкцию.

• EXTEST. Обязательная инструкция EXTEST выбирает регистр граничного сканирования в качестве текущего регистра тестовых данных.

• IDCODE. Дополнительная инструкция IDCODE выбирает регистр идентификации устройства в качестве текущего регистра тестовых данных.

В связи с развитием технологий проектирования, разработки и производства микросхем возникла ситуация, требующая дополнения и расширения стандарта IEEE 1149.1. Кроме того, появился ряд корпоративных расширений, позволяющих использовать механизм JTAG не только для тестирования, но и для отладки аппаратных компонентов. Рассмотрим эти расширения более подробно.

Новое в стандарте IEEE 1149.7

Стандарт IEEE 1149.7, называемый также cJTAG (compact JTAG), не является революционным обновлением стандарта IEEE 1149.1. Он полностью совместим со своим предшественником и представляет новые расширения JTAG, призванные улучшить характеристики JTAG и расширить область его применения.

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

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

галась. Вторая группа характеристик определяет двухконтактный протокол функционирования таких усовершенствованных J7AG-структур. Стандарт 1149.7 подразделяется на шесть операционных классов, каждый из которых строится на базе функций, задаваемых предыдущим классом. Классы Т0-Т3 относятся к первой группе характеристик, а классы Т4 и Т5 - ко второй.

Класс ТО определяет совместимость интегральных схем (ИС), поддерживающих стандарт 1149.1 (ИС.1), и ИС, поддерживающих стандарт 1149.7 (ИС.7), в рамках одной и той же схемы.

Характеристики класса Т1 определяют так называемые уровни управления (УУ) ИС.7, которых нет для ИС.1. Эти уровни управления являются основой построения всех функций, определяемых классами Т1-Т5, и базируются на диаграмме состояний контроллера ТАР, описанной в стандарте 1149.1.

Введение УУ ИС.7 является ключевым новшеством стандарта 1149.7, которое заключается в использовании последовательностей состояний диаграммы ТАР в сочетании с подсчетом количества обходов состояния Shift-DR, то есть числа невхождений в это состояние диаграммы ТАР. УУ ИС.7 приведены в таблице.

УУ ИС.7 Функция перегрузки БК-сканирование

0-1 Нет Системное

2 Команды управления Бит обхода на уровне чипа

3 Нет (резерв) Резерв

4-5 Добавочные пути сканирования Определяется пользователем

6-7 Используется системой отладки Определяется пользователем

Иерархия управления структурой 1149.7 образует основу, на которой базируется двухконтактный протокол, определяемый классами Т4 и Т5. Поскольку команды управления представляют собой некоторую функцию последовательности переходов между состояниями диаграммы ТАР, для управления протоколом требуются лишь два контакта - TCK и TMS.

Кроме определения УУ, класс Т1 определяет несколько режимов выключения питания ИС.7, что может быть критичным при тестировании самих ИС и ПП, а также при отладке тестов.

Класс Т2 определяет механизм обхода ИС.7 на уровне чипа, который предназначен для укорачивания цепочек сканирования при разработке тестов сложных схем. Этот же класс обусловливает механизм так называемого горячего включения ИС.7. Для реализации этих новых возможностей класс Т2 определяет три формата JTAG-сканиро-вания.

1. JSCAN0 - операции, совместимые с традиционным JTA G-стандартом 1149.1.

2. JSCAN1 - обеспечивает защиту при горячем включении и отключении ИС.7, обусловливая обход всех подключенных ИС.7 при включении питания по умолчанию. Этот формат предназначен для защиты отдельных портов ТАР от непреднамеренных подключений и предотвращения повреждения функциональных ядер при горячем включении.

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

Характеристики класса Т3 определяют возможность соединения ИС.7 звездой, что является определенным упущением стандарта 1149.1, предполагающего соединение ИС только в цепочку. Соединение звездой обеспечивает новый формат JSCAN3, для определения которого в классе Т3 используется специальный регистр «Только для записи». Стандарт 1149.7 предусматривает также возможность адресации каждой из ИС.7 при соединении их звездой.

Класс Т4 вводит ряд дополнительных форматов сканирования для поддержки протокола передачи тестовых данных при помощи только двух контактов порта ТАР вместо четырех. Контакты передачи данных TDI и TDO не используются, а тестовые данные передаются по теперь уже двунаправленной цепи TMSC. Кроме того, класс Т4 определяет ряд оптимизированных режимов ввода тестовых данных, позволяющих вводить только необходимые данные, без повторов и избыточности.

Функции класса Т5 ориентированы в основном на разработчиков ПО, использующих протокол JTAG в целях отладки. Основное преимущество этих функций заключается в сокращении числа контактов, предназначенных только для отладки, а также в использовании контактов TM.SC и ТСКС для реализации разнообразных пользовательских протоколов.

Следует отметить, что наряду с полной совместимостью с традиционным стандартом 1149.1 новый стандарт 1149.7 обеспечивает сокращение числа контактов сложных ИС типа System-on-Chip (SoC), выключение питания ИС в схемах с пониженным потреблением, упрощает производство и тестирование многоядерных модулей и ИС с многоэтажными чипами, а также существенно повышает эффективность процедур отладки.

Корпоративные расширения спецификаций JTAG

Значительную роль в распространении стандарта JTAG сыграло применение этого интерфейса

для отладки приложений на микропроцессорах встраиваемых систем, в частности, спецификации EJTAG для семейства процессоров MIPS и спецификации для семейства процессоров ARM.

Расширения MIPS: спецификации EJTAG

EJTAG - спецификация программно-аппаратной подсистемы для семейства процессоров с ядрами MIPS. В качестве интерфейса доступа к данным и командам EJTAG использует инфраструктуру IEEE 1149.1 JTAG и расширяет семейство инструкций ядра MIPS, а также набор компонент ядра. Таким образом создается унифицированная архитектура для отладки встраиваемых систем. Спецификации EJTAG постоянно обновляются. На данный момент последней является спецификация EJTAG версии 5.00 [2], вышедшая в июне 2009 г.

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

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

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

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

ADDRESS - для доступа к шине адреса;

DATA - для доступа к шине данных;

CONTROL - для управления процессором;

ALL - для одновременного доступа к шинам адреса, данных и управления;

EJTAGBOOT - для установки режима отладки после перезагрузки;

NORMALBOOT - для обычной перезагрузки;

FASTDATA - для ускоренного доступа к данным;

TCBCONTROL[A-E] - для доступа к блоку трассировки;

TCBDATA - для доступа к данным трассировки;

PCSAMPLE - для профилирования;

FDC - для доступа к каналу быстрой отладки.

Спецификация EJTAG описывает возможности процессора.

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

Внешняя память EJTAG. EJTAG позволяет процессору MIPS в отладочном режиме выполнять инструкции, поступающие из TAP-интерфейса. Для этого память EJTAG в сегменте KSEG3 преобразуется в операции над интерфейсом TAP. И данные, и инструкции становятся доступными на инструментальной платформе, что позволяет отлаживать программы в постоянной памяти. Коммуникация с агентом отладки осуществляется посредством регистра CONTROL, бит которого говорит об ожидании процессора. После этого адрес транзакции выставляется в регистре ADDRESS, а данные - в регистре DATA. Бит в регистре управления обновляется, чтобы сигнализировать о совершении транзакции.

Эта последовательность требует примерно 200 периодов TCK при работе с 32-битными регистрами адреса и данных. С частотой 40 МГц это занимает порядка 5 мкс, а скорость передачи данных составляет 800 кБ/с. Оптимизация передачи может осуществляться с помощью программных методов, таких как предсказание следующего адреса,

или регистра FASTDATA.

Инструкции останова. Спецификации EJTAG определяют новую инструкцию SDBBP, отличающуюся от инструкции BREAK ядер MIPS32 и MIPS64 тем, что ее исключение переводит процессор в отладочный режим и позволяет выполнить обработчик из внешней памяти EJTAG.

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

EJTAG определяет два типа простых точек останова:

• останов по выполнению инструкции по заданному виртуальному адресу;

• останов по доступу к данным, причем срабатывающий при некотором значении записываемых/считываемых данных.

Возможна реализация до 15 точек останова различных типов.

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

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

Режимы трассировки и профилирования. Спецификации EJTAG содержат разделы, посвященные аппаратной трассировке PDTrace и аппаратному профилированию. Аппаратная трассировка позволяет передавать данные о выполнении приложения по специальному внешнему каналу на инструментальную машину. Аппаратная трассировка настраивается с помощью регистров TAP.

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

Аппаратные компоненты. Аппаратная инфраструктура EJTAG состоит из нескольких компонент: расширений ядра MIPS, порта TAP, реги-

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

Расширения для многоядерной отладки. Спецификации MIPS MT ASE определяют процессоры, состоящие из нескольких виртуальных модулей VPE (виртуальный процессорный элемент). С точки зрения аппаратуры и приложений такой процессор не отличается от набора нескольких процессоров. EJTAG может поддерживать все VPE по отдельности или модуль целиком. В первом случае каждое ядро должно иметь свой контроллер TAP и все они должны быть связаны в единую цепь, как определяет спецификация JTAG 1147.1. При этом значительная часть аппаратной составляющей не разделяется между модулями, каждый имеет свой отладочный регистр, регистр точек останова и т.д. Во втором случае ядра могут иметь один регистр отладки, поддерживать одновременное пошаговое выполнение и другие совместные отладочные действия. Версии спецификаций EJTAG определяют необходимые в этом случае изменения значений регистров.

Расширения семейства процессоров ARM

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

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

CoreSight определяет набор шин для многоядерных архитектур, таких как AMBA AXI (Advanced eXtensible Interface) / AHB (Advanced Highperformance Bus), управляющая шина APB и шина для сбора трассы A TB, единый порт доступа DAP, который реализует TAP-контроллер для доступа с инструментальной машины. Порт доступа мультиплексирует управляющие команды, позволяя отдельно работать с каждым ядром. Кроме интерфейса TAP, контроллер отладки может поддержи-

вать и более высокоскоростной последовательный интерфейс SWD.

Каждое ядро, поддерживающее JTAG, управляется посредством регистров TAP. Ядра могут поддерживать и более современную высокоскоростную шину APB. Высокоскоростная шина AHB может использоваться для прямого доступа к памяти и другим устройствам в обход процессора.

Как уже отмечалось, каждый ARM-процессор имеет свои особенности реализации отладочных функций через TAP-интерфейс. В качестве примера опишем отладку ядер ARM11 и ARM1136.

Обычно ядро ARM11 интегрировано с различными устройствами на одном чипе. Каждое из них может содержать свой контроллер TAP. Например, процессор OMAP2420 включает в себя TAP для граничного сканирования, ядро ARM1136 с отладочным контроллером TAP, буфер трассировки ETB11, DSP--модуль C55x и TAP для отладки графического чипа на основе ядра ARM7TDMI, при этом TAP граничного сканирования может быть исключен из JTAG-цепи [4]. Такая конфигурация позволяет отлаживать устройства в режиме малого потребления энергии, так как процессор OMAP2420 предназначен для мобильных устройств.

Регистры, поддерживаемые TAP, включают в себя:

• SCAN_N - инструкции для того, чтобы выбрать цепь для сканирования с помощью стандартных механизмов INTEST/EXTEST. Определены несколько цепей:

- 40-битный регистр-идентификатор;

- 32-битный регистр управления отладкой (DSCR);

- регистр для записи инструкций в режиме отладки (ITR), 33 бита (32 бита инструкции + 1 бит состояния);

- регистр для передачи данных (DCC), 34 бита (одно слово + 2 бита состояния); этот регистр может использоваться как во время отладки, так и при обычном выполнении;

- регистр управления трассой (ETM), 40 бит (7 бит адреса, 32 бита данных и один бит чтения-записи);

- отладочный модуль для доступа к точкам останова (7 бит адреса, 32 бита данных и один бит чтения-записи). Эта цепь может записываться даже в режиме выполнения процессором приложения;

• HALT, RESTART - инструкции для останова и перезапуска процессора;

• ITRSEL - инструкция, специфичная для ARM11 и предназначенная для ускорения работы с цепью ITR.

В отличие от ядра MIPS регистры управления здесь не являются регистрами TAP, а читаются и записываются с помощью INTEST/EXTEST. В других ядрах ARM используется похожая модель

управления, но другой аппаратный интерфейс. В более старых ядрах использовался модуль EmbeddedICE. В более новых, таких как Cortex-A8, предпочтение отдается высокоскоростному методу доступа к DAP с помощью последовательной шины SWD.

Процесс отладки приложений ARM достаточно стандартен. Контроллер TAP может прервать выполнение ядра, переведя его в отладочный режим с помощью HALT, затем считать регистры и данные, используя команды ITR и DCC. После выполнения отладочных действий инструментальное ПО восстанавливает регистры и продолжает выполнение с помощью инструкции RESTART.

Процессор может войти в отладочный режим по точке прерывания или по выполнению инструкции BKPT из программы. Когда цепь трассировки ETM не используется для трассировки инструкций, она тоже может вывести процессор в отладочный режим по наступлению определенного состояния, так как поддерживает триггеры, настраиваемые на заданные значения шины адреса и шины данных. Для определения момента останова процессора используется опрос регистра DSCR. Для пошагового режима необходимо прервать выполнение, установить точку прерывания и запустить процессор, затем удалить точку прерывания.

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

точки останова передают управление специальному обработчику, код которого включается в приложение. Этот обработчик может передать данные с использованием регистра DCC или инициировать пошаговую отладку одного из процессов, в то время как остальные процессы будут продолжать свою работу.

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

Литература

1. IEEE STD. 1149.1-2001. URL: http://standards.ieee.org/re-ading/ieee/std_public/description/testtech/1149.1-1990_desc.html (дата обращения: 7.06.2010).

2. MIPS EJTAG 5.00. 2009. URL: http://www.mips.com (дата обращения: 7.06.2010).

3. IEEE Standard for Reduced-Pin and Enhanced-Functionality Test Access Port and Boundary-Scan Architecture. 2009. URL: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnum-ber=5412866 (дата обращения: 7.06.2010).

4. Городецкий А. Новый JTAG-стандарт IEEE 1149.7. Компоненты и технологии. № 4. 2010.

5. DBJTAG User Guide. Texas Instruments. URL: http://wi-ki.davincidsp.com/images/9/90/Dbjtag_users_guide.pdf (дата обращения: 15.06.2010).

УДК 004.021

ПАРАЛЛЕЛЬНАЯ ГЕНЕРАЦИЯ ПРОСТРАНСТВА СОСТОЯНИЙ ДИСКРЕТНЫХ ДЕТЕРМИНИРОВАННЫХ МОДЕЛЕЙ

И.А. Короткое

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

Ключевые слова: формальная верификация, проверка моделей, генерация состояний, параллельные вычисления, язык Promela.

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

Для этого осуществляется проверка модели (model checking) - автоматический формальный

подход, при котором на основе дискретной детерминированной модели программы или комплекса программ строится полное пространство состояний и на нем проверяется набор интересующих утверждений - спецификация [1].

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