автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Автоматизация проектирования симуляторов микропроцессоров и микроконтроллеров

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

НЕГОДА ДМИТРИЙ ВИКТОРОВИЧ

Автоматизация проектирования симуляторов микропроцессоров и микроконтроллеров

Специальность 05.13.12 -«Системы автоматизации проектирования (промышленность)»

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

Ульяновск — 2005

Работа выполнена на кафедре «Вычислительная техника» Ульяновского государственного технического университета.

Научный руководитель: доктор технических наук, профессор

СОСНИН Петр Иванович

Официальные оппоненты: доктор технических наук, профессор

СЕМУ1ИИН Иннокентий Васильевич

кандидат технических наук, доцент ИВАНОВ Владимир Михайлович

Ведущая организация:

Ульяновское отделение Института радиотехники и электроники РАН

Защита состоится 7 декабря 2005 г. в 15.00 на заседании диссертационного совета Д212.277.01 при Ульяновском государственном техническом университете, ауд. 211.

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 432027, г. Ульяновск, ул. Северный Венец, д. 32. УлГТУ, ученому секретарю совета Д212.277.01.

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

Автореферат разослан 3 ноября 2005 г.

Ученый секретарь Диссертационного совета д.т.н., профессор

М. К. Казаков

гоов-^

12/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Программные модели микропроцессоров (МП) и микроконтроллеров (МК), называемые чаще всего симуляторами, являются важными подсистемами САПР микропроцессорных систем (МПС). Среди множества требований, предъявляемых к симулятору, выделяются два основных, обеспечение которых занимает большую часть времени его разработки. Это производительность и адекватность модели. При создании интерактивных си-муляторов-отладчиков довольно трудоемким является также разработка средств интеграции компонентов САПР и программных моделей различных микропроцессорных устройств.

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

Адекватность симуляторов обеспечивается процессом тестирования исходной спецификации или исходного симулятора. По мнению В.В. Липаева процесс тестирования программ занимает до 30-40% суммарных трудозатрат на их разработку. В этой связи особо актуальной является автоматизация тестирования программных моделей.

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

Все вышесказанное обуславливает актуальность задачи исследования принципов и методов построения средств автоматизации проектирования симуляторов МП и МК.

Исследования должны охватывать достаточно представительный круг вопросов.

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

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

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

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

Область исследования - автоматизация проектирования микропроцессорных систем.

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

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

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

Задачи диссертационной работы. Для достижения этой цели необходимо решить следующие основные задачи:

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

2. Разработка и исследование методов оптимизирующих преобразований, нацеленных на повышение быстродействия симуляторов.

3. Разработка и исследование методов автоматической генерации тестов машинных команд.

4. Проведение объектно-ориентированного анализа задачи интеграции симуляторов МП и МК в САПР МПС, разработка архитектурного каркаса САПР МПС, центральным компонентами которого являются программные модели средств микропроцессорной техники.

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

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

1. Предложенные в работе расширения языка While позволяют моделиро-вагь свойства таких широко распространенных языков как С и Java. Тем самым, создается более конструктивная основа для осуществления оптимизирующих преобразований программных моделей МП и МК.

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

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

4. Разработанный метод таблично-алгоритмической оптимизации позволяет повышать производительность симулятора практически без затрат времени разработчика (на 40% в проведенных экспериментах).

5. Разработанный метод оптимизации «отложенное вычисление флагов» позволяет повышать производительность симулятора практически без затрат времени разработчика (на 4-18%).

6. Метод тестирования симуляторов, разработанный в диссертации, отличается от известных тем, что использует исходный код симулятора для генерации тестов машинных команд, которые затем выполняются на существующих интерпретаторах машинных команд - либо реальных микропроцессорах, либо заведомо правильных симуляторах. Благодаря этому трудозатраты на тестирование симуляторов сокращаются в 3-4 раза.

Практическая ценность. Практическую ценность представляют следующие результаты осуществления разрабатываемых и развиваемых в диссертации методов и средств: а) симулятор микропроцессора 18086, б) архитектурный каркас САПР МПС, в) экспериментальная программа выполнения оптимизирующих преобразований, г) программа анализа потока данных.

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

Внедрение результатов. Результаты внедрены в учебный процесс УлГТУ и в ООО «Креативная разработка».

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

1 Разработан абстрактный язык программирования While++, включающий операции общеизвестного языка While, операции с побочным эффектом (такие как ++, += и т.п.), вызовы функций и процедур, неструктурные операторы (return и многоуровневый break), адресную арифметику и массивы. Разработана формальная спецификация синтаксиса и денотационной семантики этого языка. Предложенный язык обладает достаточной строгостью для того, чтобы использоваться в формальных методах анализа и преобразования программ, с одной стороны, и достаточной полнотой для моделирования реальных языков программирования, с другой.

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

3. Разработана поразрядная двоичная арифметика, позволяющая анализировать поток данных в логике принятия решений в разборе машинных инструкций и получать оценки вида xand где and - поразрядное И, а и Ъ -константы. Логика позволяет получать: а) оценки результата выполнения операций из оценок операндов (прямой DFA); б) уточненные оценки операндов на основе исходных оценок операндов и оценки результата операции (обратный DFA). Тем самым обеспечивается получение локальных решений систем уравнений и неравенств, используемых при анализе алгоритмов декодирования машинной инструкции.

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

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

СТРУКТУРА ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

В САПР МПС часто оперируют не реальным микропроцессорным устройством, а некоторой математической моделью, которая абстрагирует реальную МПС, моделируя лишь некоторые интересующие разработчика ее свойства. В данной диссертации интерес представляют функционально-логические модели микропроцессоров МП. В зависимости от цели исследования, применяются различные функционально-логические модели. На самом абстрактном уровне мы имеем дело с автоматными моделями, такими как абстрактная машина Тьюринга, модель дискретных процессов Капитоновой-Летичевского, итеративные функции (iterated maps) Хармана и Такера, автоматы Мура и другие.

В модели, предложенной Харманом и Такером, вычислительный процесс разбивается на последовательные дискретные моменты времени. В каждый момент времени состояние вычислителя определяет значение состояния в следующем моменте времени: / :А —> А. Пусть Т - дискретное время Т — {0.1,..}. Функционирование системы описывается функцией

F'.TxA^A,

F(f,e) = /(e).

где teT,aeA. Таким образом, F(t,a) обозначает состояние, которое примет система через t шагов времени (итеративная функция). Абстрактная машина описывается алгеброй

(A,T\F).

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

Потоком s€[T—+А] называют функцию от времени, порождающую бесконечную последовательность состояний.

Рассмотрим две модели:

F:TxA->A и G:SxB-^B,

где F(t,a) = ft(a) и G(s,b) = gs(b). Говорят, что G симулирует F, если существуют такие отображения a:TxA->SxB и /3:ЯЛ, при которых коммутирует следующая диаграмма:

ТхА —А

SxB —В

Это означает, что для t £ Т,а € А выполняется следующее равенство: F(/,e) = j9(G(Qi(/>a)>aJ(/,e)))

Вторая группа моделей специфицирует операционную семантику МП. К этой группе относятся следующие модели: абстрактные машины состояний Юрия Гуревича (Abstract State Machines), системы перезаписи термов, алгоритмические модели. Симулятор МП включает его алгоритмическую модель и решает над ней некоторую задачу симуляции - например, задачи оценочного моделирования, отладки, виртуализации и т.п.

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

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

По точности симуляции можно выделить симуляторы системы команд (СК, или ISA) и более низкоуровневые симуляторы, начиная с уровня регистровых передач и ниже. Внутри уровня СК существует несколько подуровней. Прежде всего, различают функциональные (functional) и поцикловые (cycle-accurate) модели. Известно, что функциональные симуляторы примерно на 2 порядка быстрее своих поцикловых аналогов. Кроме того, следует различать функциональные симуляторы СК, моделирующие интерфейс МП на сигнальном уровне, а внутренние состояния и переходы - на поведенческом; таковы, например, поведенческие модели на языках описания аппаратуры (HDL), поддерживающих многоуровневое проектирование (VHDL, Verilog, Handel-C, Sys-temC, др.). Еще одним основанием деления функциональных симуляторов СК по точности является степень реализации функций МП: интеграция модели МП с моделями периферийных устройств, набор симулируемых команд, режимы работы МП. Наконец, симуляция может производиться с точностью до базовых блоков программы целевой машины или быть высокоуровневой симуляцией.

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

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

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

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

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

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

Предположим, что имеется программа эмуляции МП с множеством состояний S. Программа имеет командный цикл, который считывает байты очередной команды и интерпретирует ее. Командный цикл можно представить функцией от байтов кода команды: Е = Äbj ... b2-f, где/' S ~>S- функция эмуляции, содержащая операции обращения к отдельным байтам инструкции. Заменим операцию чтения отдельных байтов на операцию чтения слова: B = \w.Elo{w)hi(w), где lo(w) и hi(w), соответственно, младший (старший) и старший(младший) байты слова w для архитектуры типа big endian (little endian). Далее заменим тело командного цикла Е ветвлением по первому слову кода машинной инструкции, а операции чтения слова в каждой ветви заменим константой: Е' = switch 216 В, где оператор switch определим следующим образом:

switch = Xngw.

g 0, если w — 0

g n — 1, если w = и — I.

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

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

Исходный код (симулятор)

/ л

Ручная маркировка

(выделение командного цикла)

V__

Маркированная программа

Программа на «чистом» языке программирования

'■"««чи,;.

Компилятор

Задачно-ориентированный I

оптимизатор Г V (ТАО) J

Препроцессор (дсс -Е)

Рис. 1. Процедура предметно-ориентированной автоматической оптимизации программ

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

Далее предлагается процедура ТАО в общем случае на основе анализа семантики программ. Достоверность предложенной процедуры подтверждается вычислительными экспериментами и доказательствами с позиций реляционной хоаровской логики (РХЛ). В отличие от классической логики Флойда-Хоара, в которой суждения присутствуют в форме Ь {'■{>)р{Ф), где <р и ф - пред- и постпредикаты соответственно, р - программа, в РХЛ суждения имеют следующий вид:

где Ф - выражение, задающее пред-отношение S х S, и Ф' - выражение, задающее пост -отношение. Выражение, стоящее после двоеточия, описывает «контекст», в котором понимается эквивалентность операторов с и с', и может иметь почти произвольный синтаксис и семантику типа (SxS)—>(Sx S) для операторов и (S xS) >(Zy,Z) для выражений без побочного эффекта, где S -множество состояний, Z- множество значений.

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

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

2. Выражения в While++ могут иметь побочный эффект, т.е. изменять состояние.,

3. Добавляются вызовы функций.

4. Добавляется оператор switch.

5. Добавляются неструктурные операторы return и многоуровневый break (выход на несколько уровней вверх, аналогичный оператор присутствует в Java).

Для While++ сформулированы синтаксис, денотационная семантика и правила РХЛ для верификации анализа и преобразования программ. Утверждения РХЛ в случае While++ принимают вид he, ~е2 :Ф=>Ф',ф для выражений и 1= с, ~ с2: Ф Ф',тг,ф для операторов, где

1Ф Ф',тг,0]|: (S х S)(S х Z, х Zx х S х i х Zx), [ф ф',ф]; (S х S) -»(S х Zx х S х Zx).

Здесь S - множество состояний, I - множество меток перехода (continuations), включая специальное значение х, означающее отсутствие перехода (последовательное исполнение), ZL - множество значений плюс специальное значение _l , означающее отсутствие оператора return или вызов функции типа void. Утверждения имеют следующую семантику:

~с2 :Ф=>Ф',ф = (felfe])€[*=►$',¿J,

= ([С,],[С21)€[Ф^Ф',7г,4

Выражения, которыми описываются отношения Ф, 7г и ф, являются предикатами над переменными, проиндексированными знаками (1) и (2); например, ф = (у0 — v,2,) означает, что возвращаемое значение в выражении исходной

программы должно совпадать со значением в преобразованной программе; <j)-=true означает, что возвращаемое значение не имеет значения (например, далее нигде не используется).

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

х and а = Ь,

где and - поразрядная операция И, а маска, Ъ - значение, х - оцениваемое значение. Уравнение х and а = b задает значение отдельных бит (определяемых маской а) переменной х. Для операций языка While++ сформулированы правила распространения оценки, которые позволяют по оценкам операндов получить консервативную оценку результата операции. Эти правила составляют поразрядную двоичную арифметику. Например, для операции поразрядного И правило имеет следующий вид:

I- х and а = b Ь у and а — /? ,,

------- [Band]

Ь (х and у) and (a and a or a and not b or a and not 0) = b and (3

Теперь рассмотрим следующий пример декодирования машинной инструкции:

1. switch(*(short*)рс & OxFFF) (

2. . . .

3. case ОхАВС:

4. i£(*pc >= OxCO) { . . . }

5. break;

6. . . .

Для roro чтобы упростить программу, необходимо оценить значение *рс в строке 4. В архитектуре Intel оно будет равно ОхВС Современные компиляторы не могут вывести это значение. Вывод в данном случае возможен только путем решения уравнения

(Крс) +„ (Крс +„, 1) «16 8)) and16 OxFFF=с.

В общем случае данную задачу можно сформулировать так: пусть имеется множество переменных х, и некоторые начальные оценки этих переменных Требуется найти как можно более конкретные уточненные оценки этих переменных, включающие все решения некоторого ограничения P(xi, ..., х^, заданного произвольным предикатом. Предикат может включать любые операции языка программирования. Данная задача решается путем распространения оценки вида дг and a-b от результата каждой операции обратно к ее операндам.

Для операций While++ сформулированы правила вывода таких оценок. Например, для поразрядного И соответствующее правило имеет вид:

Ь х and а = Ъ Ь у and а = ß Ь (х and у) and А = В гг. „

--[CandJ

Ь х and (а ох В от A and not В and ß) = b or В

hyand (а от В от A and not В and b) — ß от В

Анализ потока данных, проводимый при преобразовании программ, заключается в отслеживании зависимостей значений в разных точках программы. Данные из одной точки программы в другую передаются через ячейки памяти. Для того, чтобы быть уверенным, что в какой-либо точке программы используется ячейка, измененная ранее в другой точке, необходим механизм вывода, способный установить эквивалентность двух адресов (или индексов массива), заданных выражениями. Эта задача решается с использованием расширенной системы перезаписи S\R, состоящей из множества правил перезаписи R, описывающих правила упрощения алгебраических выражений, и уравнений S, состоящих из утверждений коммутативности и ассоциативности арифметических операций. Выражения равны, если их S\R-нормальны формы равны с точностью до эквациональной теории S.

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

для операторов и

для выражений While++, где П - множество определений (или окружение), являющееся конъюнкцией предикатов, с',е' - преобразованные оператор и выражение, у - возвращаемое значение, или, если точнее, его оценка (а,Ь), / - множество меток, на которые происходит переход в данном операторе. Пример правила, описывающее усечение известного ветвления в условии:

Sa I- -i Va

[ÍT|ife then с, else c2 -> (Va;Vß,Sß,Cß,Vß)

, где a = [íl]e, ß - [<Sa A Va]c2.

Еще одним исследуемым оптимизирующим преобразованием является отложенное вычисление флагов, которое исходит из того факта, что результат вычисления флагов МП зачастую не используются. Очевидно, что здесь можно сэкономить на вычислительных операциях, если вместо значений флагов сохранять некоторые значения, на основе которых эти флаги можно вычислить «по запросу». В диссертации предлагается метод автоматизации этого оптимизирующего преобразования, основанный на методике программных срезов (program slicing).

Для спецификации рассматриваемого преобразования симулятор представляется дискретной системой (S,F), где S - множество состояний, a F -

множество процессов. СостояниеS = PC* MemxRgx Fl состоит из счетчика команд PC, ячеек памяти Мет, регистров Rg и флагов Fl. Эта система заменяется изоморфной моделью (S',F'), где S' = PC х. Mem xRgx Subst, Subst некоторая информация, замещающая Fl. Пусть функция r:Subst—>Fl задает гомоморфизм системы S в Л". Пусть также множества процессов F и F' и соответствующие функции перехода t:S->S и i':S'S" изоморфны. Алгоритм, реализующий функцию t, является телом командного цикла симулятора. Задача организации отложенного вычисления флагов сводится к преобразованию алгоритма командного цикла из t в эквивалентную ему форму г".

Пусть t(s 6 S) и t'(s е 5") представлены в виде разложений

t(pc, mem, rg, fl) =< ^ _ rg (pc, mem, rg, fl), tfl (pc, mem, rg, fl) >,

t'{pc,mem,rg,subst) =

(t 'Рс,ш„,гг (Pc> mem, rg, subst), t ',,,„„ (pc, mem, rg, subst))

тогда изоморфизм между l и V задается соотношениями

tpcmg (Рс>тет' r(subst)) = t \c^rg (pc, mem, rg, subst), t fl (pc, mem, rg, r (subst)) = r(t \ubsl (pc, mem, rg, subst));

Положительный эффект рассматриваемого преобразования имеет место в случае, когда время вычислений t'subll(pc,mem,rg, subst) меньше, чем время вычислений tfl(pc,mem,rg,fl). В качестве subst предлагается выбирать следующие переменные:

1. Целочисленная переменная Variant, определяющая, в какой точке программы происходило вычисление флагов. При реальном (отложенном) вычислении флагов происходит ветвление по этой переменной.

2. Набор входных значений для t.fl (pc, mem, rg, fl), которые используются и для вычисления tpc mem ri, при данном значении Variant. Входным значением может быть исходная переменная из набора {pc} U {mem,} U {rgj} U {flk} или результат промежуточного вычисления.

Вычислительные эксперименты, проведенные с данным преобразованием, показали увеличение скорости симуляции на 4,5-18,3%. Нижняя граница соответствует традиционным алгоритмам обработки данных, а верхняя - алгоритмам, в которых для уменьшения времени реакции встроенной системы циклические программы приводятся к линейным.

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

процессорах, либо заведомо правильных симуляторах (рис.2) Благодаря этому существенно сокращаются трудозатраты на тестирование симуляторов.

Метод тестирования симуляторов базируется на следующих основных положениях:

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

Исходный код

л г

i симулятора

Генератор тестов

разработчик

Протокол ') тестирвоания J

Тесты (СТП)

МП

Рис. 2. Метод тестирования симулятора, основанный на генерации тестов и использовании прототипа

• тест представляет собой самотестирующуюся программу (СТП, self-test program), корректное выполнение которой на симуляторе подтверждает или опровергает корректность симулятора;

• тест разбивается на множество тестовых проверок согласно некоторой метрике покрытия исходного кода симулятора; каждая проверка соответствует инициализации операндов, выполнению одной инструкции МП и проверке результата;

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

Основной проблемой в предложенном методе является анализ программы симулятора и автоматическая генерация тестов. Обобщенная процедура генерации тестов показана на рис. 3: исходный код симулятора, помеченный специальными комментариями или директивами #pragma, подвергается синтаксическому и семантическому анализу, результатом которого является дерево разбора (или терм). Дерево разбора, которое преобразуется во внутреннее представление \УЫ1е++-ггрограммы, служит входом для генератора кода инструкции.

Маркировка исходного кода симулятора включает указание на командный цикл симуляции, имена переменных или выражения (lvalue) состояния микропроцессора, включающие имена регистров и флагов, массива, который моделирует память, счетчика команд. Генератор кода инструкции ищет все маршруты выполнения командного цикла, согласно заданному критерию покрытия Потом он использует символьное решение систем уравнений и неравенств для вывода масок кодов команд (это также является задачей обратного DFA). Среди уравнений имеются, в частности, уравнения вида х and а = Ь, где and — поразрядная операция И. В известных системах решения уравнений и неравенств такого рода уравнения решаются неэффективным способом или вообще не решаются. Упомянутая ранее двоичная арифметика позволяет решать такие уравнения более эффективно

Рис. 3. Процесс генерации тестов для симулятора

В работе проводится вычислительный эксперимент, в котором из фрагмента симулятора МП 18086, используя предложенные правила вывода и решение систем уравнений и неравенств, выводятся код машинной команды и зна-

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

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

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

В предложенном архитектурном каркасе взаимодействие компонентов осуществляется посредством посылки сообщений, в противоположность подходу, основанному на сигналах, принятом в моделировании цифровых устройств. Посылка сообщения является наиболее простым в реализации и быстродействующим способом взаимодействия моделей устройств на поведенческом уровне. Так, если нужно прочитать байт памяти, вызывается метод read-Memory (addr, 8) у объекта, ответственного за моделирование памяти. Выделен наиболее типичный для МПС набор сообщений, имена которых примерно соответствует сигналам шины управления, а операнды - сигналам шин адреса и/или данных. Все такие сообщения сгруппированы в т.н. динамические интерфейсы, согласно следующей таблице:

Интерфейс Сообщение Описание

Memory readMemory(address: i, length:i):i Чтение length-разрядного слова памяти по адресу address

writeMemory(address: i, word:i, length:i) Запись length-разрядного слова word по адресу address памяти

10 readPort(address:i, length:i):i Чтение length-разрядного слова памяти по адресу address

writePort(address:i, Запись length-разрядного

word:i, length) слова word по адресу address памяти

CallHandler call(address:i, Cpu:CPUComponent) Виртуальное сообщение, предназначенное для перехвата вызов подпрограмм и прерываний при высокоуровневой симуляции

CPU interrupt(vector:i) Вызвать аппаратное прерывание с заданным вектором

canlnterrupt():b Вывод «разрешение аппаратных прерываний» микропроцессора

canDMAO :b Вывод «разрешение прямого доступа к памяти» микропроцессора

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

Используется известный алгоритм симуляции, основанный на планировании и дельта-задержках. Симуляция каждого компонента выполняется методом step. Очередной step вызывается симулятором в соответствии с некоторым графиком Г • Гх С, где Т- запланированное время моделирования, а.С - множество компонентов в модели. После возврата из step соответствующая позиция удаляется из графика. В начале моделирования в график заносятся все компоненты со временем моделирования равным нулю.

В графике одному моменту времени может соответствовать множество Г(г) заданий, порядок выполнения которых зависит от алгоритма планирования. Недетерминизм, как и в других симуляторах, решается в пользу первого запланированного задания1. Таким образом, автоматная модель симулятора оп-

1 Выполнением задания является вызов метода step компонента.

ределяется состоянием ,s, € S компонентов и текущим графиком Г, «Текущее» время можно определить как время самого раннего задания: /т,„(Г) = min t То-

(М-)еГ

гда функция симуляции f:Sx(TxC)-+Sx(TxC) является композицией всех функций, реализуемых методами step компонентов, соответствующих текущему времени:

/(5„Г,) = {Step{c,)o... °Step{ck))(s„T,), где с е ГДпт(Г,)),\<)<к

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

Поддерживается такой режим моделирования, при котором в некоторой точке алгоритма можно запланировать его продолжение. Имеются ввиду операторы ожидания, аналогичные wait в VHDL. Для этого предлагается использовать неконкурирующую многопоточность для сохранения контекста алгоритма (процесса в терминах VHDL) между вызовами step (). Суть подхода заключается в выполнении симуляции каждого компонента МПС в отдельном потоке, который активизируется методом step () .

Архитектурный каркас содержит следующие законченные компоненты

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

2. Компонент, предназначенный для имитации алфавитно-цифрового дисплея XT с видеобуфером, отображаемым на ОЗУ.

3. Шестнадцатеричный редактор памяти.

4. Интерактивный компонент, моделирующий поведение портов ввода-вывода. При попытке ввода из порта командой in предлагается ввести входное значение, которое потом отображается в первой строке панели. Во второй строке отображаются значения, выведенные в порты командой out.

5. Компоненты, отображающие содержимое стека и состояние регистров МП.

Архитектурный каркас использовался для создания обучающего симулято-ра МП i8086, который является законченным графическим приложением. В си-мулятор интегрирована модель алфавитно-цифрового монитора с видеобуфером по адресу Ь8000, совместимым с XT. Симулятор содержит дизассемблер, функции загрузки и выполнения СОМ-приложений, пошаговую трассировку программ, точки останова. Эта разработка может играть роль прототипа для создания новых симуляторов.

Архитектурный каркас позволяет перехватить как вектора программных прерываний, так и вызовы подпрограмм по определенным адресам. Например, симулято^может перехватить вызовы обращения к файловой системе (int 21h в MS-DOS ) и перенаправить эти вызовы хост-системе. Таким образом, можно добиться интеграции системных служб целевой системы со службами хост-системы.

Архитектурный каркас представлен в диссертации в виде десяти UML-диаграмм, при его разработке использовались такие шаблоны проектирования как Flyweight, Visitor, Adapter, Decorator, MVC. Оценка степени повторности использования кода архитектурного каркаса в экспериментальной разработке САПР МПС на базе 18086 показывает, что примерно 39% кода САПР составляет код архитектурного каркаса. Общий объем исходного кода на языке Java составляет около 10 тыс. строк.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Построенный в работе язык While++ позволяет моделировать свойства таких широко распространенных языков как С и Java. В отличие от базового языка While расширенный язык становится средством практического осуществления оптимизирующих преобразований программных моделей МП и МК, созданных на указанных языках программирования.

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

3. Разработан метод таблично-алгоритмической оптимизации симулятора по быстродействию, который в ходе проведенных экспериментов позволил уменьшать время симуляции примерно на 40% практически без затрат времени разработчика.

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

5. Разработан метод тестирования симуляторов, отличающийся от известных тем, что использует исходный код симулятора для генерации тестов машинных команд, которые затем выполняются на существующих интерпретаторах машинных команд - либо реальных микропроцессорах, либо заведомо правильных симуляторах. Благодаря этому трудозатраты на тестирование симуляторов сокращаются примерно в 3-4 раза.

Полученные результаты могут стать хорошей основой для широкого спектра дальнейших исследований, связанных с построением САПР МПС К основным из направлений таких исследований следует отнести:

1. Исследование методов автоматизации проектирования симуляторов, базирующихся на полном спектре средств технологии объектно-ориентированного программирования.

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

3. Исследование применения предложенных методов автоматизации проектирования к симуляторам с динамической компиляцией.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Negoda D. Fully Automated Test Generation for a Processor Simulator // Interactive Systems and Technologies: The Problems of Human-Computer Interaction: Collection of scientific papers. - Ulyanovsk State Technical University, 2005, p. 196-201.

2. Негода Д. В. Таблично-алгоритмическая оптимизация симулятора микропроцессора // Известия Белорусской Инженерной Академии. - Минск, 2004. -№1(17)/2.-С. 109-111.

3. Негода Д. В. Реинжениринг программной модели микропроцессора с целью повышения быстродействия // Труды международной научно-технической конференции «Современные информационные технологии». - Пенза: Пенз технологич. ин-т., 2004. - С. 120-122.

4. Негода Д. В. Использование подстановки термов в оптимизации эмуляторов микропроцессоров // Пятая Международная научно-практическая конференция «Компьютерные технологии в науке, производстве, социальных и экономических процессах». - Новочеркасск, 2004. - С. 21-26.

5. Негода Д. В. Анализ потока данных в объектной надстройке над РСУБД // ► Информатика, системы искусственного интеллекта и моделирование технических систем: труды международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике». -УлГТУ, 2005. -том 2. - С. 116-118.

6. Негода Д. В. Отложенное вычисление флагов в симуляторах микропроцессоров // Информатика, системы искусственного интеллекта и моделирование технических систем: труды международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике» - УлГТУ, 2005. - том 2. - С. 119-120.

7. Negoda D. Ontology Representation Languages // Interactive Systems: The Problems of Human-Computer Interaction: Collection of scientific papers. - Ulyanovsk State Technical University, 2003. - p. 174-177.

8. Negoda V.N., Negoda D.V. Foundation of Model Interaction in Microprocessor System Simulation System // Interactive Systems: The Problems of HumanComputer Interaction. - Ulyanovsk State Technical University, 2001. - p. 70-72.

9. Negoda D. Interactive Telecommunication Simulator of 18О86 Microprocessor. Ulyanovsk State Technical University, Interactive Systems: The Problems of Human-Computer Interaction, 1999, p. 160.

Ю.Соснин ПИ., Негода Д.В. Автоматическая классификация в базах данных опыта. // Информационные технологии в учебном процессе кафедр физики и математики (ИТФМ-2002): Труды VI международного совещания-семинара (24-26 сентября 2002 г.), под ред. Климовского А.Б. - Ульяновск: УлГТУ, 2002. - С. 104-106.

11.Негода В.Н., Негода Д.В. Репозитарий программно-информационных ресурсов учебной системы моделирования. // Информационные технологии, системы и приборы: Сборник научных трудов/УлГТУ. - Ульяновск, 2000. - с. 51-56.

12.Негода В.Н., Негода Д.В. Программа подготовки описаний информационных ресурсов. // Материалы выставки 2-й международной научно-технической конференции "Интерактивные системы проблемы человеко-компьютерного взаимодействия", - Ульяновск, 1997, с. 18-19.

А

Список сокращений, принятых в автореферате

мк - микроконтроллер

МП - микропроцессор

МПС - микропроцессорная система

ОЗУ - оперативное запоминающее устройство

РХЛ - реляционная хоаровская логика

САПР - система автоматизированного проектирования

ск - система команд

СТП - самотестирующаяся программа

ASM - Abstract State Machine

АВТОРЕФЕРАТ

НЕГОДА Дмитрий Викторович

Автоматизация проектирования симуляторов микропроцессоров и микроконтроллеров

Подписано в печать 01.11.2005. Формат 60x84/16 Бумага писчая. Усл. п. л. 1,17 Уч.-изд.л. 1,00. Тираж 100 экз. Заказ № ШЧ

Типография УлГТУ. 432027. Ульяновск, Сев. Венец, 32.

»20622

РНБ Русский фонд

2006-4 22537

Введение.

1. Анализ технологий проектирования симуляторов.

1.1. Модели микропроцессоров.

1.2. Классификация симуляторов.

1.3. Базовые технологии проектирования симуляторов.

1.4. Оптимизация симуляторов по быстродействию.

1.5. Выводы по первой главе.

2. Исследование методов оптимизации симуляторов по быстродействию

2.1. Методы анализа и трансформаций программ.

2.1.1. Алгебра языков программирования.

2.1.2. Синтаксис и семантика языка While++.

2.1.3. Реляционная хоаровская логика.

2.2. Таблично-алгоритмическая оптимизация.

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

2.2.2. Эксперимент.

2.2.3.Решение в общем случае.

2.2.4. Частичная реализация ветвей симулятора.

2.2.5. Поразрядная двоичная арифметика.

2.2.6. Решение систем уравнений и неравенств в поразрядной двоичной арифметике.

2.2.7. Эквивалентность выражений.

2.2.8. Процедура таблично-алгоритмической оптимизации.

2.3. Отложенное вычисление флагов.

2.3.1. Функциональная модель.

2.3.2. Эксперимент.

2.3.3. Автоматизация оптимизирующего преобразования.

2.4. Выводы по второй главе.

3. Автоматизация тестирования симуляторов.

3.1. Автоматизация тестирования программ.

3.2. Существующие методы тестирования симуляторов.

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

3.4. Выводы по третьей главе.

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

4.1. Структура МПС.

4.2. Взаимодействие компонентов МПС.

4.3. Маршрутизатор сообщений.

4.4. Планирование и дельта-задержка.

4.5. Дизассемблер.

4.6. Визуальная среда симуляции МПС.

4.7. Симулятор микропроцессора 18086. Создание новых симуляторов и моделей.

4.8. Выводы по четвертой главе.

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

Адекватность симуляторов обеспечивается процессом тестирования исходной спецификации или исходного симулятора. По мнению В.В.Липаева процесс тестирования программ занимает до 30-40% суммарных трудозатрат на их разработку. В этой связи особо актуальной является автоматизация верификации спецификаций.

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

Исследования должны охватывать достаточно представительный круг вопросов.

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

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

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

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

Область исследования - автоматизация проектирования микропроцессорных систем.

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

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

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

Задачи диссертационной работы. Для достижения этой цели необходимо решить следующие основные задачи:

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

2. Разработка и исследование методов оптимизирующих преобразований, нацеленных на повышение быстродействие симуляторов.

3. Разработка и исследование методов автоматической генерации тестов машинных команд.

4. Проведение объектно-ориентированного анализа задачи интеграции симуляторов МП и МК в САПР МПС, разработка архитектурного каркаса САПР МПС, центральным компонентами которого являются программные модели средств микропроцессорной техники.

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

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

1. Предложенные в работе расширения языка While позволяют моделировать свойства таких широко распространенных языков как Си и Java. Тем самым создается более конструктивная основа для осуществления оптимизирующих преобразований программных моделей МП и МК.

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

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

4. Разработанный метод таблично-алгоритмической оптимизации позволяет повышать производительность симулятора практически без затрат времени разработчика (на 40% в проведенных экспериментах).

5. Разработанный метод оптимизации «отложенное вычисление флагов» позволяет повышать производительность симулятора практически без затрат времени разработчика (на 4-18% в проведенных экспериментах).

6. Метод тестирования симуляторов, разработанный в диссертации, отличается от известных тем, что использует исходный код симулятора для генерации тестов машинных команд, которые затем выполняются на существующих интерпретаторах машинных команд - либо реальных микропроцессорах, либо заведомо правильных симуляторах. Благодаря этому трудозатраты на тестирование симуляторов сокращаются примерно в 3-4 раза.

Практическая ценность. Практическую ценность представляют следующие результаты осуществления разрабатываемых и развиваемых в диссертации методов и средств: а) симулятор микропроцессора 18086, б) архитектурный каркас САПР МПС, в) экспериментальная программа выполнения оптимизирующих преобразований г) программа анализа потока данных в программе.

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

Внедрение результатов. Результаты внедрены в учебный процесс Ул-ГТУ и в ООО «Креативная разработка».

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

1. Абстрактный язык программирования While++, включающий операции общеизвестного языка While, операции с побочным эффектом (такие как ++, += и т.п.), вызовы функций и процедур, неструктурные операторы (return и многоуровневый break), адресную арифметику и массивы; формальная спецификация синтаксиса и денотационной семантики этого языка. Предложенный язык обладает достаточной строгостью для того, чтобы использоваться в формальных методах анализа и преобразования программ, с одной стороны, и достаточной полнотой для моделирования реальных языков программирования, с другой.

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

3. Поразрядная двоичная арифметика, позволяющая анализировать поток данных в логике принятия решений в разборе машинных инструкций и получать оценки вида х and a = b, где and - поразрядное И, а и b -константы. Логика позволяет получать: а) оценки результата выполнения операций из оценок операндов (прямой DFA); б) уточненные оценки операндов на основе исходных оценок операндов и оценки результата операции (обратный DFA). Правила этой логики позволяют получать локальные решения систем уравнений и неравенств, используемых при анализе алгоритмов декодирования машинной инструкции.

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

5. Оптимизирующее преобразование, основанное на отложенном вычислении флагов целевой архитектуры.

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

Структура диссертационной работы.

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

4.8. Выводы по четвертой главе

1. Модель МПС в контексте задачи создания средств интеграции симуляторов в САПР МПС и построения архитектурного каркаса целесообразно рассматривать в аспектах конструирования, симуляции и визуализации.

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

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

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

5. Оценка степени повторности использования кода архитектурного каркаса в экспериментальной разработке САПР МПС на базе i8086 показывает, что примерно 25% кода САПР составляет код архитектурного каркаса.

Заключение

В ходе исследований по теме диссертации получены следующие основные результаты:

1. Построенный в работе язык While++ позволяет моделировать свойства таких широко распространенных языков как Си и Java. В отличие от базового языка While, расширенный язык становится средством практического осуществления оптимизирующих преобразований программных моделей МП и МК, созданных на указанных языках программирования.

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

3. Разработан метод таблично-алгоритмической оптимизации симулятора по быстродействию, который позволяет повышать производительность симулятора на 43% практически без затрат времени разработчика.

4. Разработан метод оптимизации на основе отложенного вычисления флагов позволяет повышать производительность симулятора на 4-18%.

5. Разработан метод тестирования симуляторов, отличающийся от известных тем, что использует исходный код симулятора для генерации тестов машинных команд, которые затем выполняются на существующих интерпретаторах машинных команд - либо реальных микропроцессорах, либо заведомо правильных симуляторах. Благодаря этому трудозатраты на тестирование симуляторов сокращаются примерно в 3-4 раза.

6. Разработан объектно-ориентированный архитектурный каркас симуляции МПС, включающий базовую реализацию функций симулятора и интерфейсы для его настройки на конкретную систему команд МП и архитектуру МПС.

Полученные результаты могут явиться хорошей основой для широкого спектра дальнейших исследований, связанных с построением САПР МПС. К основным из направлений таких исследований следует отнести:

1. Исследование методов автоматизации проектирования симуляторов, базирующихся на полном спектре средств технологии объектно-ориентированного программирования.

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

3. Исследование возможностей использования предложенных методов автоматизации проектирования симуляторов в симуляторах с динамической компиляцией.

Список используемых сокращений

ББ - базовый блок, максимальная последовательная цепочка операторов (или инструкций) без операций перехода. Иногда накладывается еще одно требование: в программе не должно быть переходов внутрь ББ, а только на его начало.

СК - система команд (instruction set).

СТП - самотестирующаяся программа (self-testing program)

МП - микропроцессор.

МПС - микропроцессорная система, включающая МП, память, порты ввода/вывода, контроллеры шины, периферийные устройства и пр.

МК - микроконтроллер, частный случай МПС.

ПДА - поразрядная двоичная арифметика.

ТАО - таблично-алгоритмическая оптимизация, при которой получается таблица частичных процедур.

ASM - Abstract State Machine. Абстрактная машина состояний (автомат).

CFG - Control Flow Graph, граф потока управления.

CFA - Control Flow Analysis, анализ потока управления.

DFA - Data Flow Analysis, анализ потока данных.

RHL - Relation Hoare Logic, расширение классической Хоаровской логики для анализа преобразований программ.

RTL - 1) Register Transfer Level, уровень межрегистровых передач, 2) Register Transfers List, внутренняя структура в виде трехадресного кода, используемая для внутреннего представления программ в компиляторах.

SoC - System on Chip, система на кристалле - (полу)заказная МПС, технологически выполненная на одном кристалле.

Публикации по теме диссертации

1. Negoda D. Fully Automated Test Generation for a Processor Simulator. Ulyanovsk State Technical University, Interactive Systems: The Problems of Human-Computer Interaction. - Collection of scientific papers, 2005.

2. Негода Д.В. Таблично-алгоритмическая оптимизация симулятора микропроцессора // Труды Белорусской Инженерной Академии, 2004.

3. Негода Д.В. Реинжениринг программной модели микропроцессора с целью повышения быстродействия. // Труды международной научно-технической конференции «Современные информационные технологии». Пенза. Пенз. технологич. ин-т., 2004.

4. Негода Д.В. Использование подстановки термов в оптимизации эмуляторов микропроцессоров // Пятая Международная научно-практическая конференция «Компьютерные технологии в науке, производстве, социальных и экономических процессах», Новочеркасск, 2004

5. НЕГОДА Д.В. Анализ потока данных в объектной надстройке над РСУБД // КЛИН, УлГТУ, 2005.

6. НЕГОДА Д.В. Отложенное вычисление флагов в симуляторах микропроцессоров // КЛИН, УлГТУ, 2005.

7. Negoda D. Ontology Representation Languages. Ulyanovsk State Technical University, Interactive Systems: The Problems of Human-Computer Interaction. - Collection of scientific papers, 2003, pp. 174-177

8. Negoda V.N., Negoda D.V. Foundation of Model Interaction in Microprocessor System Simulation System. Ulyanovsk State Technical University, Interactive Systems: The Problems of Human-Computer Interaction, 2001, pp. 70-72.

9. Negoda D. Interactive Telecommunication Simulator of i8086 Microprocessor. Ulyanovsk State Technical University, Interactive Systems: The Problems of Human-Computer Interaction, 1999, pp. 160.

Ю.Соснин П.И., Негода Д.В. Автоматическая классификация в базах данных опыта. // Информационные технологии в учебном процессе кафедр физики и математики (ИТФМ-2002): Труды VI международного совещания-семинара (24-26 сентября 2002 г.), под ред. Климовского А.Б. -Ульяновск: УлГТУ, 2002. - с. 104-106.

11.Негода В.Н., Негода Д.В. Репозитарий программно-информационных ресурсов учебной системы моделирования. // Информационные технологии, системы и приборы: Сборник научных трудов/УлГТУ. - Ульяновск, 2000. - с. 51-56.

12.Него да В.Н., Негода Д.В. Программа подготовки описаний информационных ресурсов. // Материалы выставки 2-й международной научно-технической конференции "Интерактивные системы проблемы челове-ко-компьютерного взаимодействия", - Ульяновск, 1997, с. 18-19.

1. Ахо, А, В., Сети, Р., Ульман, Дж., Компиляторы: принципы, технологии и инструменты.: Пер. с англ. - М.: Издательский дом «Вильяме», 2001. - 768 с.

2. Бердж В. Методы рекурсивного программирования/Пер. с англ. С.П. Забродина и др.; Под ред. Н.И. Иващенко. М.: Машиностроение, 1983.

3. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. -СПб.: Питер, 2001. 368 е.: ил.

4. Ицысков В. М. Исследование и проектирование моделей программных средств эмуляции вычислительных систем: Дис. канд. техн. наук: 05.13.13.-СПб, 1999.-249 е.: ил.

5. Негода В.Н. Средства автоматизации структурно-функционального проектирования микропроцессорных систем. Дисс. на соиск. уч. Степени д.т.н., Ульяновск: УлГТУ, 2001. - 156~с.

6. Негода Д.В. Таблично-алгоритмическая оптимизация симулятора микропроцессора микропроцессора // Труды Белорусской Инженерной Академии, 2004.

7. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. М.: Наука. Гл. ред. физ.-мат. лит., 1988.-296 с.

8. Липаев В. В. Тестирование программ. ■— М.: Радио и связь, 1986. — 296 с.

9. Соммервилл И. Инженерия программного обеспечения, 6-е издание.: Пер. с англ. — М.: Издательский дом «Вильяме», 2002. — 624

10. Ю.Суворова Е. А., Шейнин Ю. Е. Проектирование цифровых систем на VHDL. СПб.: БХВ-Петербург, 2003. - 576 е.: ил.

11. AVR® Instruction Set. Atmel Inc. http://www.atmel.com/dyn/resources/proddocuments/DOC0856.PDF

12. Bartak, R. Constraint Programming: In Pursuit of the Holy Grail, in: Proceedings of WDS99 (invited lecture), Charles University, Prague, June 1999.

13. Batcher K. et al. Instruction Randomization Self Test for Processor Cores, VTS, 1999.

14. BelIard, F., QEMU, a Fast and Portable Dynamic Translator, Proceedings of USENIX 2005 Annual Technical Conference, FREENIX Track, Anaheim, Canada, 2005, Pp. 41-46.

15. Benton, N. Semantics of Program Analyses and.Transformations. Lecture notes for the PAT Summer School. June 2005.

16. Benton, N. Simple Relational Correctness Proofs for Static Analyses and Program Transformations. Proceedings of the 31st ACM Symposium on Principles of Programming Languages (POPL). January 2004.

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

18. Chandra, S. Retargetable Functional Simultor. A Master Thesis, Department of Computer Science & Engineering, Indian Institute of Technology, Kanpur, 1999.

19. Chen L. et al. DEFUSE: A Deterministic Functional Self-Test Methodology for Processors, VTS, 2000.

20. Chernoff A., Hookway R., DIGITAL FX!32 Running 32-Bit x86 Applications on Alpha NT, in Proceedings of the USENIX Windows NT Workshop, USENIX Association, Berkeley CA, August 1997.

21. Cifuentes C, Lewis B.T, Ung D., "Walkabout-A Retargetable Dynamic Binary Translation Framework", Sun Labs Tech Report TR-2002-106, January 2002.

22. Cifuentes, C. and Sendall, S. Specifying the Semantics of Machine Instructions. In Proceedings of the 6th international Workshop on Program Comprehension (June 24 26, 1998). IWPC. IEEE Computer Society, Washington, 1998.

23. Cirstea, H. and Kirchner, C. An introduction to the rewriting calculus. Research Report RR-3818, INRIA, December 1999.

24. Corno F. et al. On the Test of Microprocessor IP Cores, DATE, 2001.

25. Das, M., Lerner, S., Seigle, M., ESP: Path-Sensitive Program Verification in Polynomial Time. In Proceedings of the 2002 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2002. pp. 57-68.

26. Dershowitz N., Jouannaud J.P. Rewrite Systems. Chapter 6 of Handbook of Theoretical Computer Science. Volume B: Formal Methods and Semantics, J. van Leeuwen ed. pp. 243-320, North Holland, Amsterdam, 1990.

27. Farfeleder S., Krall A., Horspool N. Ultra Fast Cycle-Accurate Compiled Emulation of Inorder Pipelined Architectures, To appear in Proceedings of SAMOS V: Embedded Computer Systems: Architectures, Modeling, and Simulation, 2005.

28. Fernandez, M. F., Ramsey, N., The New Jersey machine-code toolkit, Proceedings of the 1995 USENIX Technical Conference, 1995, pp. 289302.

29. Fox A.C.J., Harman N.A. Algebraic models of correctness for microprocessors. Technical Report CSR 8-98 (accepted for Formal Aspects of Computer Science). University of Wales Swansea, 1998. - 22 p.

30. Fox A.C.J., Harman N. A. Algebraic Models of Temporal Abstraction for Initialised Iterated State Systems: An Abstract Pipelined Case Study.Technical Report CSR 21-98 (submitted to Acta Informatica) -University of Wales Swansea, 1998. 32 p.

31. Fred kin E. Trie Memory. Communication of the ACM, 3: 490-500, 1960.

32. GENERATOR home page, http://www.squish.net/generator/

33. Gurevich Yu., Evolving Algebras 1993: Lipari Guide, Specification and Validation Methods, ed. E. Borger, Oxford University Press, 1995, 9—36.

34. Gurevich Yu., Huggins J. The Semantics of С Programming Language. Computer Science Logic, LNCS, vol. 702, 1993, pp. 274-309.

35. Hadjiyiannis, G., Hanono, S., Devadas, S., ISDL: An Instruction Set Description Language for Retargetability. DAC: Software Synthesis for Embedded Systems Anaheim, California, USA, 1997, pp. 299-302.

36. HaIambi, A., Grun, P., et al., EXPRESSION: A language for architecture exploration through compiler/simulator retargetability, in: Proceedings of the European Conference on Design, Automation and Test (DATE), Mar. 1999.

37. Harman N. A., Tucker J.V. Algebraic Models of Microprocessors: Architecture and Organisation. / Acta Informatica 33, 1996, pp. 421-456.

38. HedIey D. Final Year Project. An IBM PC Emulator For.Unix and Windows, 1994.

39. Hennessy J., Patterson D. Computer Organization and Design: The Hardware-Software Interface (Appendix A, by James R. Larus), Morgan Kaufman, 1993.

40. Herold, A., Siekmann, J., Unification in Abelian semigroups, J. of Automated reasoning 3 (3), 1987, pp. 215-221.

41. Hoare C.A.R. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576-585, October 1969.

42. Hoffmann A., et al., A novel methodology for the design of application-specific instruction-set processors using a machine description language, IEEE Trans, on CAD of Integrated Circuits and Systems, vol. 20, pp 13381354, Nov. 2001.

43. Huang C., Cheng K., Assertion checking by combined word-level ATPG and modular arithmetic constraint-solving techniques. In Proceedings of the 37th Conference on Design Automation. Los Angeles, California, June 05 -09, 2000, pp. 118-123.

44. Huggins J. K. and Wallace C, An Abstract State Machine Primer, Technical Report CS-TR-02-04, Computer Science Department, Michigan Technological University, 4 December 2002.

45. Jones, N.D., Gomard, C.K., Sestoft, P. Partial Evaluation and Automatic program generation, Prentice Hall International, 1993. http://www.dina.kvl.dk/~sestoft/pebook/pebook.html.

46. Khare, A., et al., V-SAT: A visual specification and analysis tool for system-on-chip exploration, in: Journal of Systems Architecture 47, 2001, pp. 263-275.

47. Lacey D., De Moor O. Imperative program transformation by rewriting. In Compiler Construction (CC'01), Lecture Notes in Computer Science. SpringerVerlag, April 2001.

48. Larsson F. Generating Efficient Simulators from Specification Language. SICS Technical Report T97:01, 1997. 25 p.

49. Larsson F., Magnusson P, Werner B. SimGen: Development of Efficient Instruction Set Simulators. SICS Technical Report T97:03, 1997. 17 p.

50. Leupers R., Elste J., Landwehr B. Generation of Interpretive and Compiled Instruction Set Simulators. ASP-DAC 1999, pp. 339-342.

51. Nakada Т., Nakashima H. Design and Implementation of a High Speed Microprocessor Simulator BurstScalar. MASCOTS 2004: 364-372.

52. Nanda A.K., Hu Y., Ohara M., Giampapa M., Benveniste C., Michael

53. M., The Design of COMPASS : An Execution Driven Simulator for Commercial 152 Applications Running on Shared Memory Multiprocessors. Proceedings of International Parallel Processing Symposium, Apr. 1998.

54. Negoda D. Interactive Telecommunication Simulator of i8086 Microprocessor. Ulyanovsk State Technical University, Interactive Systems: The Problems of Human-Computer Interaction, 1999, pp. 160.

55. Nilsson, N.J. Principles of Artificial Intelligence, Tioga, Palo Alto, 1980.

56. Nilsson S. Radix sorting & searching. PhD thesis, Department of Computer Science, Lund University, Lund, Sweden, 1996.

57. PearPC PowerPC Architecture Emulator, http://pearpc.sourceforge.net/

58. QEMU Internals, http://fabrice.bellard.free.fr/qemu/qemu-tech.html

59. Rajesh V., A Generic Approach to Performance Modeling and Its Application to Simulator Generator, available at http://www.cse.iitk.ac.in/research/mtechl996/9611123.html

60. Rapps S., Weyuker E.J. Data Flow Analysis Techniques for Test Data Selection, IEEE proc. of ICSE-6, 1982, pp.272—278.

61. Reshadi, M. Dutt, N. Reducing compilation time overhead in compiled simulators, In Computer Design, 2003. Proceedings., 2003, pp. 151 -153.

62. Sakharov A. Specialization of Imperative Programs Through Analysis of Relational Expressions. Dagstuhl Seminar on Partial Evaluation 1996: 430-445.

63. Sakharov, A. Propagation of constants and assertions. SIGPLAN Not. 29, 5, 1994, pp. 3-6.

64. Shaffer J. H. A Performance Evaluation of Operating System Emulators. Bachelor Thesis, Department of Computer Science of Bucknell University 2004.

65. Shen J. and Abraham J.A., Native Mode Functional Test Generation for Processors with Applications to Self Test and Design Validation, International Test Conference, 1998, pp. 990-999.

66. Skrien, D. CPU Sim 3.1: A tool for simulating computer architectures for computer organization classes. ACM Journal of Educational Resources in Computing (JERIC) 1 (4), 2001, pp. 46-59.

67. Stickel, M. E., A unification algorithm for associative-commutative functions, J. of the Association for Computing Machinery 28 (3), 1981, pp. 423-434.

68. The vmips Project Home Page, http://vmips.sourceforge.net/

69. Tijms A. Binary translation: Classification of emulators. Leiden Institute for Advanced Computer Science, atijms@liacs.nl. http ://www.liacs.nl/~atij ms/bintrans .pdf.

70. Tip F. A Survey of Program Slicing Techniques. Journal of Programming Languages, 1995, vol. 3, no. 3, pp. 121-189.

71. Titzer B. L., Lee D. K., Palsberg J. Avrora: Scalable sensor network simulation with precise timing. In Proceedings of IPSN'05, International Conference on Information Processing in Sensor Networks, 2005.

72. Troger J. Specification-driven Dynamic Binary Translation. PhD Thesis, Faculty of Information technology, Queensland University of Technology, Brisbane, Australia, 2004.

73. Tsang, E. Foundations of Constraint Satisfaction, Academic Press, London, 1995.

74. Turing A. On Computable Numbers, with an Application to the Ent-sheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Vol. 42:230-265, 1936.

75. Tupuri R. and Abraham J. A., A novel functional test generation method for processors using commercial ATPG, Proceedings of the International Test Conference 1997, Washington DC, Nov. 1997, pp. 743 752.

76. Ung, D. and Cifuentes, C. Machine-adaptable dynamic binary translation. In Proceedings of the ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization DYNAMO '00. ACM Press, New York, 2000. pp. 41-51.

77. Wallace C. The Semantics of the Java Programming Language: Preliminary Version. University, of Michigan EECS Department Technical Report CSE-TR-355-97.

78. Warren A. Hunt Jr. Microprocessor Design Verification. Journal of Automated Reasoning, Volume 5, Number 4, December 1989, pp. 429460.

79. Windley Ph.J. A Theory of Generic Interpreters. /In L.Pierre, G.Milne, editor, Correct Hardware Design and Verification Methods, p. 122—134. Lecture Notes in Computer Science 683, Springer-Verlag, 1993.

80. Zamulin A. V. A State-Based Semantics of a Pascal-Like Language. Siberian Devision of the Russian Academy of Sciences. A.P. Ershov Institute of Informatics Systems. Novosibirsk, 2003.

81. Zhang, Y. and Xu, B. A survey of semantic description frameworks for programming languages. SIGPLANNot. 39, 3, Mar. 2004, pp. 14-30.

82. Zhu, J., Gajski, D. D. A retargetable, ultra-fast instruction set simulator. In Proceedings of the Conference on Design, Automation and Test in Europe (Munich, Germany). ACM Press, New York, 1999.