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

Вид материала

Реферат

Содержание 2.Метод оценки времени выполнения программетод оценки времени выполнения программ. 3.Особенности архитектуры процессоров цифровой обработки сигналов. архитектуры 5.Апробация модели.

Подобный материал:

• Методика оценки времени выполнения программ, оптимизированных под конкретную архитектуру, 245.73kb.
• Р. Е. Алексеева кафедра ису программирование на языке высокого уровня методические, 57.65kb.
• Отчёт по курсовой работе по дисциплине программирование на языке высокого уровня Выполнил, 129.75kb.
• Рабочая программа по дисциплине Программирование на языке высокого уровня для специальности, 182.97kb.
• Отчёт по курсовой работе по дисциплине программирование на языке высокого уровня Выполнил, 210.25kb.
• Программирование на языке высокого уровня, 59.92kb.
• Программа курса «Программирование на языке высокого уровня», 126.66kb.
• Г. Екатеринбург, 2010 > I. Письменно ответить на вопросы: Какое устройство компьютера, 89.19kb.
• Пояснительная записка к курсовой работе по предмету «Языки и технологии программирования», 353.31kb.
• Рабочая учебная программа по дисциплине «Программирование на языке высокого уровня», 119.59kb.

ПОСТРОЕНИЕ МОДЕЛЕЙ ПРОЦЕССОРОВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ НА ОСНОВЕ СТАТИКО -ДИНАМИЧЕСКОГО ПОДХОДА.


Балашов В.В., Капитонова А.П., Костенко В.А., Смелянский Р.Л., Ющенко Н.В.

119899, Москва, ГСП-3, Воробьевы горы, МГУ, 2-й учебный корпус, ф-т ВМиК,

тел.: (095) 939-46-71, факс: (095) 939-25-96, е-mail: kost@cs.msu.su


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


1.Введение.

В работе [ 1] был рассмотрен опыт применения метода прогнозирования времени выполнения программ, применительно к программам цифровой обработки сигналов (ЦОС), на процессоре DSP 96002 фирмы Motorola. В этой статье мы рассмотрим задачу построения модели процессора для прогнозирования времени выполнения программы. Другими словами здесь рассматривается следующая задача, дано:

• описание архитектуры процессора DSP96002 (система команд, функциональная схема, временные характеристики работы функциональных блоков) и; имеется кросс-компилятор с этой архитектуры.
  
• тексты программ ЦОС на языке программирования высокого уровня.
  

Требуется:

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

Таким образом в этой статье мы сфокусируем внимание на проблеме построения модели процессора и рассмотрим ее применительно к процессору DSP96002.


2.Метод оценки времени выполнения программетод оценки времени выполнения программ.


Основная идея метода [Инвариант, Формальная модель2,3] прогнозирования времени выполнения программ на параллельной вычислительной системе состоит в следующем:

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

Здесь мы ограничим наше внимание на прогнозированиии времени выполнениядля последовательных участков программы [42]. Суть используемого метода состоит в следующем.

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


Использование ого авработе

работы [1].

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

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

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


3.Особенности архитектуры процессоров цифровой обработки сигналов. архитектуры

Описание архитектуры процессора DSP96002, его системы команд и особенностей их выполнения можно найти в [5]. Архитектура этого микропроцессора относится к классу RISC архитектур и ориентирована на решение задач цифровой обработки сигналов. Эта ориентация выражется, например, в том, что операционный блок процессора (АЛУ) оптимизирован для выполнения комплексного преобразования фурье. Все команды АЛУ регистровые. В слове памяти может кодироваться до четырех команд: две команды АЛУ и две команды пересылки данных. Такой набор из четырех команд называется инструкцией. Есть конвейер выполнения инструкций. Память команд и память данных разделены. Память данных разделена на две области: X-память и Y-память, к которым возможен независимый доступ. Адресное пространство для накристальной и внекристальной X, Y памяти едино. Обращение к внекристальной памяти осуществляется через порты A и B.


При решении рассматриваемой задачи На точность оценки времени выполнения программ учитывалисьсущественно влияют следующие основные собенности архитектуры процессора23]]:

1. Все команды АЛУ регистровые;
   
2. Время выполнения инструкции определяется только самой инструкцией и не зависит от контекста, в котором стоит инструкция. Это обусловлено:
   

• отсутствием кэш-памяти;
  
• достаточо простым поведением конвейера инструкций.
  

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

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


4.

Модель процессора DSP96002.

Модель процессора функционирует в ОС Solaris и состоит из следующих программных компонентов:

• программы dspmodel, анализирующей командную строку и передающей управление той или иной компоненте модели в зависимости от ключей, заданных при запуске;
  

• программы mark, которая выделяетение линейныех участкиов в исходной программе на Си и вставляетку контрольныех точкиек -, представляющих собой вызовы служебных функций системы моделирования. Для корректной работы программы mark необходимо соответствие исходного текста на Cи определенным требованиям, описанным ниже;
  
• статического анализатора dsps, осуществляющего разбор текста на ассемблере DSP96002 и оценку времени выполнения каждого линейного участка в отдельности;
  
• библиотеки поддержки прогона libdspd.a, содержащей объектный код служебных функций, вызываемых в контрольных точках;
  
• вспомогательной программы addnops, учитывающей некоторые специфические особенности генерируемого кросс-компилятором ассемблерного текста;
  
• программ estdump и estconcat, предназначенных для работы с библиотеками результатов статического анализа.
  

Модель также использует следующие части компилятора g96k:

• g96k, g96k-cc1, mcpp - для генерации текста программы на ассемблере DSP96002;
  
• annotate, asm96000 - для обработки ассемблерного текста.
  

Для получения объектного кода и исполняемых модулей программ для инструментальной машины применяется компилятор gcc версии 2.7.2.


Этапы работы модели и компоненты, используемые на каждом из них, показаны на рис.1.

При разработке модели были сделаны следующие допущения:

• зЗадержки при обращении к внешней памяти равны задержкам при обращении к накристальной памяти (и равны нулю);
  
• вВ арифметических операциях не встречается денормализованных операндов;
  
• на вход статического анализатора модели должно поступать лишь подмножество ассемблера DSP96002, выдаваемое компилятором Motorola g96k. Это связано с использованием особенностей ассемблерных файлов, генерируемых g96k;
  
• иИсходный текст программы на Cи удовлетворяет определенным требованиям.
  

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

и






























исполняемого кода размеченнойпрограммы данных


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


((включить в описание рисунка, описание первого блока))

Текущая версия модели может обрабатывать тексты на языке Cи, удовлетворяющие следующему требованию: в операторе return запрещено использование выражений, содержащих условную конструкцию “? : “, операции “&&” и “||” или вызовы функций.

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

При их несоблюдении модель выдаст сообщение об ошибке.

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




Исходный текст Разметка (вставка вызовов

программы на C служебных функций)

mark







Кросс-компиляция Текст на ассемблере Разбор ассемблерного текста

mcpp, g96k, g96k-cc1, mcpp DSP96002 текста и статический анализ

addnops, annotate, dsps, estconcat

asm9600 анализ

addnops, annotate, dsps, estconcat




Компиляция Объектный код для Результаты

gcc инструментальной статического

машины прогнозирования



Библиотекаlibspd.a Компоновка

libspd.a gcc Библиотека

результатов

Исполняемый код статического

инструментальной прогнозирования

машины







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

результат программы на конкретных исходных

прогнозирования данных и динамический анализ


Рис. 1. Основные этапы работы модели.

((Сделать расшифровку (по всем программам и частям компилятора) и привести в соответствии с рисунком))


5.Апробация модели.

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

[31]:

• Скалярное произведение векторов для действительных и комплексных операндов.
  
• Умножение вектора на скаляр для действительных и комплексных операндов.
  
• Поэлементное сложение/умножение векторов для действительных и комплексных операндов.
  
• Внешнее произведение векторов для действительных и комплексных операндов.
  
• Перемножение матриц для действительных и комплексных операндов.
  
• Транспонирование матриц для действительных и комплексных операндов.
  
• Сравнение элементов массива с заданной константой для действительных операндов.
  

При тестировании получены следующие результаты:

• На всех программах из тестового набора модель дает оценку времени выполнения, с точностью 100% совпадающую с результатом выполнением программ на эмуляторе процессора DSP96002.
  
• Время работы динамического этапа модели в среднем на три порядка меньше времени работы эмулятора.
  

При тестировании производительности в качестве инструментальной машины использовалась рабочая станция SPARC Classic с процессором MicroSPARC и 16 MB RAM под управлением ОС Solaris. Эмулятор процессора DSP96002 работал на машине 486DX2-66 с 8 МB RAM под управлением MS-DOS.


л.

(Attention! Может быть, эти цифры лучше убрать?).,


6.Заключение.

Тестирование модели процессора Motorola DSP96002 на наборе задач из класса цифровой обработки сигналов показало высокую эффективность работы модели, значительно превышающую эффективность применения эмулятора (по скорости работы на три порядка). На рассмотренном классе задач цифровой обработки сигналов точность оценки времени выполнения программ составила 100%.


Библиография.

1. Капитонова А.П.,Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Методика оценки времени выполнения программ, оптимизированных под конкретную архитектуру процессора, по тексту программ на языке высокого уровня. //В данном сборнике.

2. Смелянский Р.Л. Модель функционирования распределенных вычислительных систем//Вестник Моск. Ун-та. сер 15, Вычисл. Матем. и Кибернетика. 1990., N3.,С.3-21.

3. Смелянский Р.Л. Об инварианте поведения программ//Вестник МГУ, сер.15, Вычисл. матем. и киберн., 1990., N 4, С.54-60.

42. Д.В.Калиниченко, А.П.Капитонова, Н.В.Ющенко. Методы и средства прогнозирования времени выполнения последовательных программ. //Методы математического моделирования. МГУ, 1997., N 2.

53. Процессор обработки сигналов Motorola DSP96002. Руководство пользователя.

1. Капитонова А.П.,Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Методика оценки времени выполнения программ, оптимизированных под конкретную архитектуру процессора, по тексту программ на языке высокого уровня//В данном сборнике.