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

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

У

ООьиэА»

Алымова Елена Владимировна

ГЕНЕРАЦИЯ НАБОРОВ ТЕСТОВ ДЛЯ РАСПАРАЛЛЕЛИВАЮЩИХ И ОПТИМИЗИРУЮЩИХ ПРЕОБРАЗОВАНИЙ В КОМПИЛЯТОРЕ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

ОЧОКТ 2012

Санкт-Петербург - 2012

005052788

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» на кафедре алгебры и дискретной математики.

доктор технических наук Штейнберг Борис Яковлевич

Терехов Андрей Николаевич, доктор физико-математических наук, профессор Санкт-Петербургский государственный университет, зав. каф. «Системное программирование»

Бухановский Александр Валерьевич, доктор технических наук Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (НИУ ИТМО), директор НИИ наукоемких компьютерных технологий

Учреждение Российской академии наук Институт систем информатики им. А.П.Ершова Сибирского отделения РАН

Защита состоится 16 октября 2012 г. в 17:00 на заседании диссертационного совета Д212.227.06 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д. 49, конференц-зал, ЦИО.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан 15 сентября 2012 г. Ученый секретарь диссертационного совета

доктор технических наук, профессор __— Лисицына Л.С.

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

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

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

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

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

Эффективное исполнение программ без параллелизма на современном аппаратном обеспечении становится все более затруднительным. Наличие готовых отлаженных библиотек последовательных программ, а так же высокая стоимость ручной оптимизации программного кода за счет повышенных требований к квалификации специалистов повышают интерес к разработке инструментов автоматизации распараллеливания программ. Одним из инструментов автоматизации распараллеливания являются оптимизирующие и распараллеливающие компиляторы. Среди зарубежных оптимизирующих и распараллеливающих компиляторов можно выделить GNU Compiler Collection (GCC), Microsoft Visual С++, ROSE, Oracle Solaris Studio (OSS), Intel С++ Compiler и Glasgow Haskell Compiler (GHC). Разрабатываются системы автоматического распараллеливания: SUIF Compiler, PLUTO, Par4All. Примерами отечественных разработок в области оптимизации и распараллеливания программ являются система ПРОГРЕСС, DVM-система, системы ОРС и ДВОР.

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

трудоемким процессом, при этом есть вероятность пропуска некоторых тестовых случаев. Тестированию программного обеспечения посвящены работы следующих авторов: В.В. Липаев, Г. Майерс, П. Можаев, J. Rashka, J. Paul. Разработкой методов генерации тестов для различных частей компилятора занимались многие авторы. В 1972 году П. Пар дом описал алгоритм вывода минимального набора коротких предложений по контекстно-свободным грамматикам, который мог использоваться в качестве тестов синтаксического анализатора. Заметный вклад в теорию тестирования оптимизирующих компиляторов внесли: C.B. Зеленов, С.А. Зеленова, М.В. Архипова, А.П. Стасенко, R. Lâmmel, J. Harm.

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

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

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

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

1. Формулирование требований к наборам тестов на основе данных о допустимых информационных зависимостях в программе;

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

3. Формулирование критерия полноты набора тестов для преобразования;

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

5. Разработка метода задания информационных зависимостей в генерируемой программе;

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

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

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

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

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

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

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

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

• Сгенерированные наборы тестов для преобразования «Разрезание циклов» и синтаксического анализатора конвертера С2НОЬ, удовлетворяющие критерию полноты.

• Методика построения наборов тестов для графического интерфейса, удовлетворяющих критерию полноты.

На защиту выносятся:

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

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

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

Внедренне результатов работы. Результаты работы используются в проекте «Диалоговый высокоуровневый оптимизирующий распаралле-ливатель программ и его приложения» в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, государственный контракт № 02.740.11.0208 от 7 июля 2009 г. В процессе работы получено Свидетельство о государственной регистрации программ для ЭВМ: «Диалоговый высокоуровневый оптимизирующий рас-параллеливатель программ» (свидетельство №2011617205). Часть данной работы используется в проекте «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК» в рамках ФЦП «Научные и научно-педагогические кадры инновационной России», государственный контракт № 14.740.11.0006 от 1 сентября 2010 г. Работа поддержана проектом «Создание высокотехнологичного производства комплексных решений в области предметно-ориентированных облачных вычислений для нужд науки, промышленности, бизнеса и социальной сферы» (шифр 2010-218-01-209) в рамках реализации постановления №218 Правительства РФ (по заказу НИУ ИТМО). Результаты работы использованы при выполнении ОКР «Разработка системной поддержки высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов» по заказу НИУ ИТМО в рамках

темы «Разработка высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов», государственный контракт № 133с/380066/4005 от 19 ноября 2008 г. Полученные в данной работе результаты могут также использоваться в учебном процессе для изучения свойств формальных языков, описываемых контекстно-свободными грамматиками.

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

• автоматический распараллеливатель программ, реализованный по технологии «клиент-сервер» (созданный в составе группы программистов);

• выполнено тестирование сложного интерфейса высокопроизводительного программного комплекса HPC-NASIS;

• разработана система поддержки пользователя при редактировании скриптов на языке EasyFlow для среды облачных вычислений CLAVIRE.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на международных и всероссийских научно-технических конференциях: Всероссийская суперкомпьютерная конференция «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность», Новороссийск, 21-26 сентября 2009 г; IV сессия научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» в рамках VIII Всероссийской межвузовской конференции молодых ученых, СПбГУ ИТМО, Санкт-Петербург, 12-15 апреля 2011 г.; THE 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009), Moscow, Russia, September 18-21, 2009; Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи», Новороссийск, 20-25 сентября 2010 г; V Me-

ждународная конференция «Параллельные вычисления и задачи управления» (РАСО'2010), ИПУ РАН, Москва, 26-28 октября 2010 г.

Публикации. По результатам выполненных исследований опубликовано 9 печатных работ (из них 2 - в изданиях из перечня ведущих рецензируемых научных журналов и изданий Высшей аттестационной комиссии Министерства образования и науки РФ).

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы (110 наименований) и одного приложения. Содержит 129 страниц текста, включая 41 рисунок и 5 таблиц. Результаты диссертации иллюстрируются 23 примерами.

СОДЕРЖАНИЕ РАБОТЫ

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

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

На основе анализа описания тестируемого преобразования определяются условия применимости этого преобразования. Условия применимости преобразования являются совокупностью описания контекстных условий (условий на допустимые информационные зависимости преобразуемого фрагмента кода с остальной программой) и заменяемого фрагмента.

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

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

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

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

Конфигурация записывается в конфигурационный файл, представляющий собой правильный ХМЬ-документ. Упрощенная грамматика языка описания конфигураций представлена на рис. 1.

statement := block | statAssign | statlf |statlfThenElse | statswitch j statFor | statwhile | statBreak | statcontinue | statGoTo

block := It, "block", attrQuantifier?, attrcounter?, gt, dependency?, statement*, clt, "block", gt

dependency := It, "dependency", gt, set*, clt, "dependency", gt set It, "set", attrType?, attrDirecti on?, attrCyclic?, attrMode?, cgt

attrType := "type", "=", quot, typeset, quot

typeset := "in-in" | "out-out" 1 "in-out" | "out-in"

attrDirecti on := "direction", "=", quot, directi onset, quot

directionset := "asc" | "desc" | "any"

attrCyclic := "cyclic", "=", quot, cyclicSet, quot

cyclicset := "true" | "false" | "any"

attrMode := "mode", "=", quot, modeSet, quot

modeSet := "regular" | "any"

Рис. 1. Упрощенная грамматика языка описания конфигураций

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

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

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

ние КС-грамматики позволяет находить конечные пути вывода терминальных цепочек по заданной грамматике.

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

к, <:

о

\

Г

Правила КС - грамматики; 5 Л, В, С

Л Л, "а" I "а" В В, "Ь" | "Ь" СС, "с" 1 "с"

Рис. 2. Проанализированное графовое представление КС-грамматики

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

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

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

Третья глава посвящена примерам использования генератора тестов, построенного на основе методов, описанных выше.

В главе рассматриваются примеры построения критерия полноты набора тестов для синтаксического анализатора конвертера C2HDL и преобразования «Разрезание циклов», входящего в состав преобразований Открытой распараллеливающей системы.

Конвертер C2HDL на вход принимает программы на языке С, на выходе генерируется VHDL описание. На данном этапе развития конвертер принимает программы, состоящие из n-го количества одномерных циклов с параметром (оператор for языка С). В циклах могут содержаться только операторы присваивания, все циклы должны быть конвейеризуе-

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

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

Конфигурация генератора (см. рис. 3) содержит информацию, позволяющую генерировать 5 подряд идущих операторов циклов с параметром. Каждый цикл конвейеризуемый и содержит от 10 до 50 операторов присваивания.

<?хт1 уег51оп="1.0" епсосМ пд="1ЛТ-8"?> <ргодгаш с1а55="с2Н01_">

<рагаш5 1пгАггау="10" т тиг^ех^'Б" /> <Ьос1у>

«эгагрог п="5">

<Ыоск п="10..50"> <с!ерепс)епсу>

гуре="1п-1п" сН гесТюп="апу" сус"Нс="апу" тгх)е="геди1аг" /> <set type="out-in" ^геЛ1'оп="апу" сус1тс="апу" гг*х)е="геди!аг" /> </dependency> <51аГАБ51дп т="3">

сорэх! [С0АТА[* / % || && л « »]]></орз> </5Га1А551дп> </Ыоск> </5ГаГГог> </body> </ргодгат>

Рис. 3. Запись конфигурации генератора для получения набора тестов конвертера С2НПЬ

Критерий полноты набора тестов для преобразования «Разрезание циклов» формулируется следующим образом. Выделено 6 видов операторов из множества операторов языка С. Набор тестов полон, если для каждой четверки операторов из выделенного множества в наборе тестов найдется программа, содержащая эту четверку.

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

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

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

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

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

На рис. 4 приведен пример построенного дерева состояний графического интерфейса, состоящего из одной экранной формы.

Вершинами дерева состояний экранной формы являются состояния элементов этой формы. Две вершины А и В соединены дугой, если последовательность действий, приведшая к состоянию А, может быть продолжена одним действием для достижения состояния В.

Вершины, помеченные буквами А, В, С, соответствуют состояниям выпадающего списка, флажка и кнопки. Вершина, помеченная только буквой, соответствует состоянию «элемент выбран». Возможные состояния элементов экранной формы: метка «А_» - «не выбран пункт списка», метка «А1» - «выбран Пункт1», метка «А2» — «выбран Пункт2», метка «В1» — «флажок возведен», метка «В2» — «флажок сброшен», метка «С1» — «кнопка нажата», метка «С2» — «кнопка не нажата». Троеточиями помечены места, в которых на рисунке не отображены части дерева.

Рис. 4. Дерево состояний упрощенного графического интерфейса, состоящего из одной экранной формы

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

Предложенный метод построения дерева состояний используется для автоматизации построения тестов графического интерфейса высокопроизводительного программного комплекса НРС-ЫАБ^1.

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

1 Высокопроизводительный программный комплекс для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов «НРС-ЫА818» (свидетельство о государственной регистрации программ для ЭВМ № 2010610161).

нальных тестов мастера, являющегося частью \уеЬ-интерфейса автоматического распараллеливателя.

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

Задачей инструмента валидации пользовательских скриптов на предметно-ориентированном языке ЕазуР1о\у является проверка корректности скрипта до его отправки на обработку, что позволяет сократить количество ошибок и сбоев в работе вычислительной среды. Язык ЕазуР1о\у задает инструкции для выполнения композитных приложений в распределённой вычислительной среде на базе многопрофильной инструментально-технологической платформы СЬАУШЕ2. В качестве инструмента валидации разработана система поддержки пользователя при редактировании скриптов на языке Еа5уР1о\у. В системе реализованы следующие возможности: проверка синтаксиса и семантики скрипта на языке ЕазуР1о\у, проверка отсутствия дублирования в именах шагов и циклов в графе потока работ, предоставление контекстно-зависимых подсказок в текстовом редакторе.

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

Заключение. В ходе диссертационной работы получены следующие результаты:

• Разработан язык описания условий применимости преобразования программ в компиляторе;

2 Бухановскин A.B., Васильев В Н., Виноградов В Н., Смирнов Д.Ю., Сухоруков С.А., Яп-паров Т.Г. CLAVIRE: перспективная технология облачных вычислений второго поколения. //Известия вузов. Приборостроение. №10, 2011.

• Предложен новый метод построения критериев полноты набора тестов для преобразования программ в компиляторе;

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

• Разработан метод задания информационных зависимостей в генерируемой программе;

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

• С помощью разработанного генератора получены набор тестов для преобразования «Разрезание циклов», реализованного в распараллеливающей системе, и получен набор тестов для конвертера C2HDL.

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

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

1. Алымова Е. В. Критерий полноты тестовых наборов, ориентированных на проверку распараллеливающих преобразований программ // Информационные технологии. -2011. -№9. -С. 19-22. (по перечню ВАК)

2. Алымова Е.В. Автоматическая генерация тестов на основе конфигурационных файлов для оптимизирующих преобразований компилятора // Известия вузов. Северо-Кавказский регион. Естеств. науки. — № 3.-2010.-С. 5-8. (по перечню ВАК)

3. Алымова Е.В. Конфигурируемая генерация тестов для оптимизирующих и распаралелливающих преобразований // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды Международной суперкомпьютерной конференции, г. Новороссийск, 2025 сентября 2010 г., -М.: Изд-во МГУ, 2010. - С. 71-75.

4. Штейнберг Б.Я., Абрамов А.А., Алымова Е.В., Баглий А.П., Гуда С.А., Дубров Д.В., Кравченко Е.Н., Морылев Р.И., Нис З.Я., Петренко В.В., Полуян С.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б., Юрушкнн М.В. Диалоговый высокоуровневый оптимизирующий распараллеливатель (ДВОР) // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды Международной суперкомпьютерной конференции, г. Новороссийск, 2025 сентября 2010 г., - М.: Изд-во МГУ, 2010. - С. 71-75.

5. Штейнберг Б.Я., Алымова Е.В., Баглий А.П., Гуда С.А., Кравченко Е.Н., Морылев Р.И., Нис З.Я., Петренко В.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б. Особенности реализации распараллеливающих преобразований программ в ДВОР // Параллельные вычисления и задачи управления (РАСО'2010): Труды V Международной конференции, ИПУ РАН, г. Москва, 26-28 октября 2010 г. - С. 787854.

6. Штейнберг Б.Я., Алымова Е.В., Баглий Е.В., Морылев Р.И., Нис З.Я., Петренко В.В., Штейнберг Р.Б. Автоматизация тестирования элементов высокопроизводительного программного комплекса // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г. Новороссийск). М.: Изд-во МГУ, 2009.-С. 287-291.

7. Штейнберг Б.Я., Штейнберг Р.Б., Морылев Р.И., Петренко В.В., Полуян С. В., Штейнберг О.Б., Баглий А.П., Нис З.Я., Скиба И.С., Юрушкин М.В., Шаповалов В.Н., Алымова Е.В., Кравченко Е.Н., Гуда С.А. Диалоговый высокоуровневый оптимизирующий распараллеливатель программ // Свидетельство о государственной регистрации программы для ЭВМ № 2011617205 —2011.

8. Steinberg В., Abramov A., Alymova Е., Baglij A., Guda S., Demin S., Dubrov D., Ivchenko A., Kravchenko E., Makoshenko D., Molotni-kovZ., Morilev R., Nis Z. , Petrenko V., Povazhnij A., Poluyan S., Skiba I., Suhoverkhov S., Shapovalov V., Steinberg O., Steinberg R. Dialogue-based optimizing parallelizing tool and C2HDL converter // Proceedings of 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009). Moscow, Russia, September 18-21, 2009. P. 216-218.

9. Steinberg B., Alimova E., Bagliy A., Morilev R., Nis Z., Petrenko V., Steinberg R. The System for Automated Program Testing // Proceedings of 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009). Moscow, Russia, September 18-21, 2009. P. 218-221.

Подписано в печать 14.09.2012. Формат 60*84'/,6. Бумага офсетная. Печать офсетная. Физ. псч. л. 1.0. Тираж 100 экз. Заказ № 145.

НПО ПИ ЮФУ 344082, г. Ростов-на-Дону, ул. Большая Садовая, 33.

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДИКА РАЗРАБОТКИ ТЕСТОВЫХ НАБОРОВ ДЛЯ ОПТИМИЗИРУЮЩИХ И РАСПАРАЛЛЕЛИВАЮЩИХ ПРЕОБРАЗОВАНИЙ ПРОГРАММ В КОМПИЛЯТОРЕ.

1.1. Необходимые сведения из теории преобразования программ.

1.2. Условия применимости оптимизирующих и распараллеливающих преобразований программ.

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

1.4. Язык описания конфигурации.

1.5. Критерий полноты тестового набора.

1.6. Запись конфигурационного файла.

1.7. Класс программ, задаваемый конфигурацией.

1.8. Организация тестирования преобразований в оптимизирующем компиляторе.

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

ГЛАВА 2. ГЕНЕРАТОР ТЕСТОВ ПРЕОБРАЗОВАНИЙ В КОМПИЛЯТОРЕ.

2.1. Входная КС-грамматика и принцип генерации цепочек.

2.2. Древовидное представление КС-грамматики.

2.3. Графовое представление грамматики и автоматический вывод цепочек

2.4. Хранение данных об информационных зависимостях.

2.5. Моделирование информационных зависимостей в генераторе тестов

2.6. Режимы генерации тестовых наборов.

2.6.1. Режим нормального распределения.

2.6.2. Режим универсального распределения.

2.6.3. Режим перебора.

2.7. Выводы ко второй главе.

ГЛАВА 3. ПРИМЕНЕНИЕ ГЕНЕРАТОРА ТЕСТОВ.

3.1. Набор тестов для синтаксического анализатора конвертера С2ЬГОЬ.

3.2. Набор тестов для преобразования «Разрезание циклов».

3.3. Выводы к третьей главе.

ГЛАВА 4. СМЕЖНЫЕ ЗАДАЧИ.

4.1. Автоматизация тестирования графического интерфейса.

4.1.1. Дерево состояний графического интерфейса.

4.1.2. Тестирование графического интерфейса НРС-1ЧА818.

4.1.3. Генерация тестов для мастера Экспертной системы.

4.2. Автоматизация тестирования \уеЬ-приложений.

4.2.1. \¥еЬ-интерфейс автоматического распараллеливателя.

4.2.2. Тестовые сценарии для \¥еЬ-интерфейса автоматического распараллеливателя.

4.3. Система поддержки пользователя при редактировании скриптов на языке ЕаБуИош.

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

4.3.2. Основные функции системы поддержки пользователя.

4.4. Выводы к четвертой главе.

Актуальность темы. В настоящее время наблюдается стремительное развитие параллельных вычислительных архитектур. Мощность параллельных компьютеров требуется для решения задач криптографии, радиолокации в оборонной промышленности, а так же при математическом моделировании сложных систем. В 2011 году введен альтернативный рейтингу Тор500 [105] мощнейших компьютеров рейтинг Graph500 [39] эффективности вычислительных комплексов, которые обрабатывают большие массивы разреженных данных, представленных в виде графа или базы данных.

Параллельные вычисления становятся все доступнее для персональных компьютеров, в основном, в форме многоядерных процессоров [85]. В настоящее время персональные компьютеры могут быть оборудованы четырехъядер-ными процессорами Intel Core 2 Quad [37], AMD Phenom II [57]. Ведущие производители процессоров продолжают увеличивать количество ядер. В августе 2007 года на конференции Hot Chips компания Tilera Corporation представила многоядерный процессор для встраиваемых систем TILE64, архитектура iMesh которого позволяет использовать одновременно в одном процессоре сотни и тысячи ядер [104]. В октябре 2009 года компания NVIDIA представила суперкомпьютерную архитектуру Fermi, обеспечивающую более широкое применение гетерогенным вычислениям на GPU и CPU. Графические процессоры NVIDIA Tesla на базе архитектуры Fermi разработаны для высокопроизводительных вычислений при решении задач обработки сейсмических данных, моделирования погоды и климата, вычислений в области финансов [73]. В марте 2010 года компания AMD объявила о выходе новой серверной платформы AMD Opteron 6000 Series на базе 8-ядерных и 12-ядерных х86-совместимых процессоров AMD Opteron 6100 [55]. В ноябре 2011 года компания выпустила 16-ядерные процессоры AMD Opteron 6200 [56].

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

Эффективное исполнение программ без параллелизма на современном аппаратном обеспечении становится все более затруднительным [93]. Наличие готовых отлаженных библиотек последовательных программ, а так же высокая стоимость ручной оптимизации программного кода за счет повышенных требований к квалификации специалистов повышают интерес к разработке инструментов автоматизации распараллеливания программ. Одним из инструментов автоматизации распараллеливания являются оптимизирующие и распараллеливающие компиляторы [54]. Среди зарубежных оптимизирующих и распараллеливающих компиляторов можно выделить GNU Compiler Collection (GCC) [70], Microsoft Visual С++ [91], ROSE [103], Oracle Solaris Studio (OSS) [75], Intel С++ Compiler [77] и Glasgow Haskell Compiler (GHC) [69]. Разрабатываются системы автоматического распараллеливания: SUIF Compiler [71], PLUTO [61], Par4All [94]. Примерами отечественных разработок в области оптимизации и распараллеливания программ являются система ПРОГРЕСС [81, 82], DVM-система [7, 26], системы ОРС [35] и ДВОР [48].

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

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

Позитивным тестом для синтаксического анализатора является цепочка, принадлежащая целевому языку программирования. Формальное описание синтаксиса целевого языка может быть представлено в форме BNF [67]. Формальное описание позволяет автоматизировать процесс построения тестов, поэтому часто генерация тестов основывается на анализе формальных грамматик целевого языка программирования.

В работе П. Пардома [95] описан алгоритм вывода предложений языка по контекстно-свободным грамматикам. Набор предложений считается полным, если для каждого правила данной грамматики во множестве тестов присутствует предложение языка, в выводе которого используется это правило. Алгоритм позволяет генерировать минимальный набор коротких предложений, принадлежащих целевому языку. Данная работа стала основополагающей в дальнейших исследованиях [59], [100], [74]. Работа [15] посвящена способу генерации тестов на основе формального описания поведения тестируемого синтаксического анализатора. Работа [83] является продолжением предыдущего исследования. В ней рассматривается способ генерации тестов на основе абстрактной модели поведения тестируемой программы, критерии тестового покрытия формулируются в терминах построенной модели.

Тесты для семантического анализатора компилятора должны быть не только синтаксически корректны, но и соблюдать правила семантики целевого языка программирования. В работе [63] описана система генерации тестов, использующая алгоритм Пардома для генерации синтаксически корректных программ. Проверка контекстных условий и преобразование синтаксически корректных программ в семантически корректные происходит за счет вставки дополнительного кода в грамматику входного языка. Методы генерации тестов на основе атрибутных грамматик рассматриваются в работах [86] и [72]. В этих работах атрибутные грамматики используются в качестве описания спецификации семантики целевого языка. В работе [5] предлагается метод генерации позитивных и негативных тестов для семантических анализаторов, основанный на конструктивном описании статической семантики. Это описание заменяет и дополняет традиционные контекстные условия. Для конструктивного описания правил статической семантики используется специально разработанный язык SRL (Semantic Relation Language).

В работе [19] представлен подход к динамической верификации компиляторов, основанный на декомпозиции общей задачи компилятора. Авторы предложили разбить общую задачу компилятора на подзадачи: синтаксический анализ, семантический анализ, оптимизация и генерация кода, а также предложено верифицировать библиотеки поддержки времени исполнения. Метод верификации состоит из нескольких этапов. На первом этапе происходит извлечение требований из нормативных документов, на втором этапе извлеченные требования формализуются и используются как формальная модель на следующих этапах. На основе построенной формальной модели автоматически строятся тесты. В результате исполнения тестов делается вывод о том, насколько поведение компилятора соответствует формальной модели. Работа [43] посвящена вопросу генерации исполняемых тестов для компилятора. Для генерации тестов выбран подход, основанный на использовании параметрической контекстно-свободной грамматики. Эти грамматики пишутся специально для выбранного языка программирования. Метод позволяет генерировать синтаксически и семантически корректные программы, которые могут быть скомпилированы в исполняемую программу.

В работе [36] изложены принципы автоматной парадигмы программирования, и описан подход к динамической проверке корректности автоматных программ. Подход основывается на возможности инструментальных средств, поддерживающих автоматное программирование, вести протокол выполнения программы в терминах автоматов. В протоколе содержится необходимая для проверки программы информация: последовательность состояний, в которых пребывал автомат, обработанные события, значения входных и выходных переменных. В качестве примера инструментального средства, которое позволяет осуществлять пошаговую отладку программы в терминах автоматов, можно привести расширение UniMod [38] интегрированной среды разработки Eclipse [20].

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

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

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

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

1. Формулирование требований к наборам тестов на основе данных о допустимых информационных зависимостях в программе (разделы 1.1 и 1.2);

2. Разработка языка описания условий применимости преобразования, связанных с информационными зависимостями в программе (раздел 1.4);

3. Формулирование критерия полноты набора тестов для преобразования (раздел 1.5);

4. Разработка алгоритма генерации синтаксически и семантически корректных программ на языке, заданном контекстно-свободной грамматикой (разделы 2.1, 2.2 и 2.3);

5. Разработка алгоритма моделирования информационных зависимостей в генерируемой программе (разделы 2.4 и 2.5);

6. Проектирование, программная реализация и отладка генератора тестовых программ на основе контекстно-свободной грамматики и конфигурационных файлов (разделы 2.6.1, 2.6.2 и 2.6.3);

7. Внедрение разработанной в диссертации технологии генерации наборов тестов посредством тестирования преобразований распараллеливающей системы (раздел 3.2);

8. Внедрение предложенной в диссертации технологии тестирования в разработанный интерфейс автоматического распараллеливателя программ, реализованного по технологии «клиент-сервер» (разделы 4.2.1 и 4.2.2).

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

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

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

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

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

• Сгенерированные наборы тестов для преобразования «Разрезание циклов» и синтаксического анализатора конвертера С2НОЬ, удовлетворяющие критерию полноты.

• Методика построения наборов тестов для графического интерфейса, удовлетворяющих критерию полноты.

На защиту выносятся:

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

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

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

Внедрение результатов работы.

Результаты работы используются в проекте «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения» [17] в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, государственный контракт № 02.740.11.0208 от 7 июля 2009 г. В процессе работы получено Свидетельство о государственной регистрации программ для ЭВМ: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ» (свидетельство №2011617205). Часть данной работы используется в проекте «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК» в рамках ФЦП «Научные и научно-педагогические кадры инновационной России», государственный контракт № 14.740.11.0006 от 1 сентября 2010 г. Работа поддержана проектом «Создание высокотехнологичного производства комплексных решений в области предметно-ориентированных облачных вычислений для нужд науки, промышленности, бизнеса и социальной сферы» (шифр 2010-218-01-209) в рамках реализации постановления №218 Правительства РФ (по заказу НИУ ИТМО). Результаты работы использованы при выполнении ОКР «Разработка системной поддержки высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов» по заказу НИУ ИТМО в рамках темы «Разработка высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов», государственный контракт № 133с/380066/4005 от 19 ноября 2008 г. Полученные в данной работе результаты могут также использоваться в учебном процессе для изучения свойств формальных языков, описываемых контекстно-свободными грамматиками.

Во время работы над диссертацией при изучении теории тестирования программ рассматривались задачи, близкие к теме диссертации: участие в разработке шеЬ-интерфейса распараллеливающего конвертора (на оптимизирующие преобразования которого ориентирован разработанный в диссертации генератор тестов) и тестирование программных интерфейсов. При этом получены практически значимые результаты: автоматический распараллеливатель программ, реализованный по технологии «клиент-сервер» (созданный в составе группы программистов);

• выполнено тестирование сложного интерфейса высокопроизводительного программного комплекса НРС-МАБК;

• разработана система поддержки пользователя при редактировании скриптов на языке ЕазуР1о\у для среды облачных вычислений СЬАУЖЕ.

Часть исследований диссертации поддерживалась грантами:

• ОКР «Разработка системной поддержки высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов» в рамках темы: ГК № 133с/380066/4005 «19» ноября 2008 г.

• ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по теме: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения» ГК № 02.740.11.0208 от 7 июля 2009 г.

• ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по теме «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК» ГК № 14.740.11.0006 от 1 сентября 2010.

• ФЦП «Кадры инновационной России на 2009-2013 гг.» по программе «Мобильность молодых учёных» 2009 г.

• Российский государственный проект «Создание высокотехнологичного производства комплексных решений в области предметно-ориентированных облачных вычислений для нужд науки, промышленности, бизнеса и социальной сферы», Шифр № 2010-218-01-209.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на научно-технических конференциях. Всероссийские конференции:

• Всероссийская суперкомпьютерная конференция «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность», Новороссийск, 21-26 сентября 2009 г;

• IV сессия научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» в рамках VIII Всероссийской межвузовской конференции молодых ученых, СПбГУ ИТМО, Санкт-Петербург, 12-15 апреля 2011 г.

Международные конференции:

• THE 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009), Moscow, Russia, September 18-21, 2009;

• Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи», Новороссийск, 20-25 сентября 2010 г;

• V Международная конференция «Параллельные вычисления и задачи управления» (РАСО'2010), ИПУ РАН, Москва, 26-28 октября 2010 г.

В 2008 году сделан доклад по теме диссертации в ОАО «Научно-конструкторское бюро вычислительных систем» города Таганрога. Кроме того, результаты работы многократно докладывались на семинаре «Автоматическое распараллеливание программ» мехмата Южного федерального университета.

Публикации. По результатам выполненных исследований опубликовано 9 печатных работ. Из них 2 статьи в журналах перечня ВАК: «Информационные технологии» [2] и «Известия высших учебных заведений. СевероКавказский регион. Естественные науки» [3], 4 статьи в сборниках трудов конференций [48], [49], [101] и [102], 2 тезисов докладов [4], [49] и 1 свидетельство о государственной регистрации программы [51].

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

Структура диссертации.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы (110 наименований) и одного приложения. Содержит 129 страниц текста, включая 41 рисунок и 5 таблиц. Результаты диссертации иллюстрируются 23 примерами.

Основные результаты, полученные в ходе диссертационной работы:

• Разработан язык описания условий применимости преобразования программ в компиляторе;

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

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

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

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

• С помощью разработанного генератора получены набор тестов для преобразования «Разрезание циклов», реализованного в распараллеливающей системе, и получен набор тестов для конвертера С2НТ)Ь.

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

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

ЗАКЛЮЧЕНИЕ

1. Автоматический web-распараллеливатель программ. URL: http://ops.opsgroup.ru

2. Алымова Е. В. Критерий полноты тестовых наборов, ориентированных на проверку распараллеливающих преобразований программ. Информационные технологии. М.: «Новые технологии», 2011, №9, сс. 19 22.

3. Алымова Е.В. Автоматическая генерация тестов на основе конфигурационных файлов для оптимизирующих преобразований компилятора // Известия вузов. Северо-Кавказский регион. Естеств. науки. № 3, 2010.

4. Архипова М.В. Генерация тестов для семантических анализаторов, б.м. : Вычислительные методы и программирование, 2006.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. М.: Мир, 1978.

6. Белоусов А. И., Ткачев С. Б. Дискретная математика. Серия: Математика в техническом университете. М.: МГТУ им. Н. Э. Баумана, 2004.

7. Бухановский А. В., Васильев В. Н., Виноградов В. Н., Смирнов Д. Ю., Су-хоруков С. А., Яппаров Т. Г. CLAVIRE: перспективная технология облачных вычислений второго поколения. // Известия вузов. Приборостроение. №10, 2011.

8. Бухановский A.B., Ковальчук C.B., Марьин C.B. Интеллектуальные высокопроизводительные программные комплексы моделирования сложных систем: концепция, архитектура и примеры реализации. // Известия вузов. Приборостроение. т. 52, №10, 2009.

9. Векторизация программ. // Векторизация программ: теория, методы, реализация. / Сборник переводов статей М.: Мир, 1991. С. 246 267.

10. Воеводин В.В. Воеводин Вл.В. Параллельные вычисления, С-Петербург «БХВ-Петербург», 2002.

11. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.:МИР, 1975.

12. Демаков A.B., Зеленова С.А., Зеленов C.B. Тестирование парсеров текстов на формальных языках. Программные системы и инструменты (тематический сборник факультета ВМиК МГУ), 2001. стр. 150-156.

13. Деундяк В. М., Элементы теории формальных грамматик. Ростов-на-Дону, 1997.

14. Диалоговый высокоуровневый оптимизирующий распараллеливатель программ (ДВОР). URL: http://www.ops.rsu.ru.

15. Зандстра. М., PHP: объекты, шаблоны и методики программирования, 3-е издание = PHP Objects, Patterns and Practice, Third Edition. — M.: «Вильяме», 2010.

16. Зеленов C.B., Пакулин H.B. Верификация компиляторов систематический подход. Труды Института системного программирования РАН, 2007.

17. Интегрированная среда разработки Eclipse. URL: http://www.eclipse.org/

18. Калинов А .Я., Косачёв A.C., Посыпкин М.А., Соколов A.A. Автоматическая генерация тестов для графического пользовательского интерфейса по UMLдиаграммам действий. Труды института Системного Программирования РАН, 2005.

19. Касперский К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ-Петербург, 2003. - 456 с.

20. Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988.

21. Касьянов В.Н., Мирзуитова H.J1. Реструктурирующие преобразования: Алгоритмы распараллеливания циклов. В кн.: Программные средства и математические основы информатики.,- Новосибирск: ПСИ СО РАН, 2004.

22. Керниган Б., Ритчи Д. Язык программирования Си.\Пер. с англ., 3-е изд., испр. — СПб.: "Невский Диалект", 2001.

23. Клинов М.С., Крюков В.А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер. Вестник Нижегородского университета им. Н.И. Лобачевского, 2009, № 2, с. 128-134.

24. Князьков К. В., Ларченко А. В. Предметно-ориентированные технологии разработки приложений в распределенных средах. // Известия вузов. Приборостроение. №10, 2011.

25. Котляров В.П., Основы тестирования программного обеспечения: Уч. Пособие / В.П. Котляров, Т.В. Коликова М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знания, 2006.

26. Криспин Л., Грегори Д., Гибкое тестирование: практическое руководство для тестировщиков ПО и гибких команд = Agile Testing: A Practical Guide for Testers and Agile Teams. — M.: «Вильяме», 2010.

27. Можаев П. Средства автоматизированного тестирования // Открытые системы. №3, 2009.

28. Набор тестов для конвертера C2HDL. URL: http://ops.rsu.ru/tests/C2HDL-tests.zip.

29. Набор тестов для преобразования «Разрезание циклов». URL: http://ops.rsu.ru/tests/testsBv4LoopDistr tests.zip.

30. Нис 3. Я. Автоматизация проверок семантической корректности распараллеливающих преобразований. / Труды III международной конференции «Параллельные вычисления и задачи управления» (РАСО'2006).

31. Открытая распараллеливающая система (ОРС). URL: http://www.ops.rsu.ru.

32. Поликарпова H.H., Шалыто А. А. Автоматное программирование. — СПб.: Питер, 2009.

33. Процессоры Intel® Core™2 Quad. Обзор. URL: http://www.intel.com/cd/products/services/emea/rus/processors/core2quad/33391 7.htm.

34. Расширение UniMod для IDE Eclipse. URL: http://unimod.sourceforge.net/intro.html

35. Рейтинг Graph500. URL: http://www.graph500.org.

36. Серебряков B.A., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования //М.: МЗ-Пресс, 2006 г., 2-е изд.

37. Силаков Д.В., Автоматизация тестирования web-приложений, основанных на скриптовых языках // Труды Института системного программирования РАН. Подход UniTESK: итоги и перспективы. Т. 14, Ч. 2, 2008.

38. Спельников Д. М., Гуськов А. А., Маслов В. Г., Бухановский А. В. Учебно-научный комплекс „Компьютерное моделирование в нанотехнологиях" на основе Грид-среды. // Известия вузов. Приборостроение. №10, 2011.

39. Стасенко А.П. Генерация исполняемых тестов для компилятора. Новосибирск : Конструирование и оптимизация параллельных программ, 2008.

40. Фаулер М. Предметно-ориентированные языки программирования. М.: Вильяме, 2011.

41. Холзнер С. XML. Энциклопедия, 2-е изд. СПб.: Питер, 2004.

42. Штейнберг Б.Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью. Ростов н/Д: Изд-во Рост, ун-та, 2004.

43. Штейнберг Б.Я. Распараллеливание программ для суперкомпьютеров с параллельной памятью и Открытая распараллеливающая система. Диссертация на соискание ученой степени доктора технических наук. РГУ, 2004.

44. Электронное обучающее средство «Тренажер параллельного программиста» (ТПП) 2007 г. URL: http://www.ops.rsu.ru.

45. Эндрюс Грегори Р. Основы многопоточного, параллельного и распределенного программирования. М: Вильяме, 2003.

46. Allen R., Kennedy К. Optimizing compilers for Mordern Architetures. Morgan Kaufmann Publisher, Academic Press, USA, 2002.

47. AMD Opteron™ 6100 Series Processors. URL: http://www.amd.com/us/products/server/processors/600Q-series-platform/6100/Pages/6100-series-processors.aspx#5.

48. AMD Opteron™ 6200 Series Processors. URL: http://www.amd.com/us/products/server/processors/600Q-series-platform/6200/Pages/6200-series-processors.aspx.

49. AMD Phenom™ II Key Architectural Features. URL: http://www.amd.com/us/products/desktop/processors/phenom-ii/Pages/phenom-ii-key-architectural-features.aspx.

50. Apache JMeter. URL: http://jmeter.apache.org/

51. Bazzichi F., Spadafora I. An automatic generator for compiler testing. IEEE Transactions on Software Engineering, стр. 343-353, 1982.

52. Bennett J. Autolt Documentation // Autolt Online Documentation. URL: http://www.autoitscript.com/autoit3/docs (дата обращения: 24.05.2011)

53. Bondhugula Uday, Hartono A., Ramanujan J., Sadayappan P. A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. ACM SIGPLAN Programming Languages Design and Implementation (PLDI), Jun 2008.

54. Bray T., Paoli J., Sperberg-McQueen C. M., Maler E., Yergeau F. Extensible Markup Language (XML) 1.0 (Fifth Edition). W3C Recommendation. URL: http://www.w3.org/TR/2008/REC-xml-20081126/. 2008.

55. Celentano A., Reghizzi S., Delia Vigna P., Ghezzi C. Compiler testing using a sentence generator, б.м. : Software Practice and Experience, стр. 897-913, 1980.

56. CMMI for Development, v. 1.3, November 2010, p. 466.

57. CSE HTML Validator. URL: http://www.htmlvalidator.com/

58. Dustin, Rashka, Paul. "Automated Software Testing -Introduction, Management, and Performance". Addison-Wesley 1999, p. 43-44.

59. Garshol L.M. BNF and EBNF: What are they and how do they work? URL: http://www.garshol.priv.no/download/text/bnf.html

60. Geb. URL: http://www.gebish.org/

61. Glasgow Haskell Compiler (GHC). URL: www.haskell.org/ghc.

62. GNU Compiler Collection (GCC). URL: http://gcc.gnu.org.

63. Hall M. W., Anderson J. M., Amarasinghe S. P., Murphy B. R., Liao S. W., Bug-nion E., Lam M. S. Maximizing Multiprocessor Performance with the SUIF Compiler. IEEE Computer, Dec 1996.

64. Harm J., Lammel R. Two-dimensional Approximation Coverage // Informatica Journal. 24. 2000. № 3.

65. High Performance Computing Supercomputing with Tesla GPUs. URL: http://www.nvidia.com/obiect/teslacomputingsolutions.html.

66. Homer W., Schooler R. Independent testing of compiler phases using a test case generator. Software Practice and Experience, стр. 53-62, 1989.

67. How Oracle Solaris Studio Optimizes Application Performance. An Oracle Technical White Paper. Dec. 2011. 10 p.

68. HPC-NASIS, http://hpc-nasis.ifmo.ru/

69. Intel С++ Compiler. URL: http://software.intel.com/ru-ru/intel-compilers/.

70. ISO (1994). International Standard ISO/IEC 8402. Quality Management and Quality Assurance Vocabulary, International Organization for Standardization, Geneva.

71. Kanglin Li, Mengqi Wu. Effective GUI Test Automation: Developing an Automated GUI Testing Tool. Sybex Inc, 2004.

72. Kasyanov V.N., Evstigneev V.A. The PROGRESS program manipulation system // Parallel Computer Technologies/ Proc. Intern. Conf., Obninsk, 1993. — Vol. 3. — P. 651-656.

73. Kasyanov V.N., Evstigneev V.A., Gorodniaia L. The system PROGRESS is a tool for parallelizing compiler prototyping // Proc. of Eighth SIAM Conf. on Parallel Processing for Scientific Computing (PPSC-97), Minneapolis, 1997. — P. 301-306.

74. Kragen Sitaker. С BNF Grammar, 30 Oct 1999. URL: http://lists.can0nical.0rg/pipermail/kragen-hacks/l999-October/000201 .html.

75. Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley. University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. Dec. 18,2006.

76. Lammel R, J. Harm. Testing attribute grammars. Proceedings of the Third Workshop on Attribute Grammars and their Applications (WAGA'2000), 2000. стр. 79-98.

77. Lamport L. The parallel execution of DO loops // Comm. Acm, 1974.

78. LoadZen. URL: http://loadzen.com/

79. Maydanchik A., "Data Quality Assessment", Technics Publications, LLC, 2007.

80. Microsoft Domain-Specific Language (DSL) Tools. Overview. URL: http://msdn.microsoft.com/ru-ru/library/bbl26327.aspx (дата обращения: 19.12.2011)

81. MSDN Library. Visual C++. URL: http://msdn.microsoft.com/en-en/librarv/60kl 461 a.aspx.

82. Muchnick S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.

83. Mycroft, A. Programming Language Design and Analysis motivated by Hardware Evolution (Invited Presentation) Proc. SAS'07, Springer-Verlag LNCS vol. 3634: 18-33, August 2007.

84. Par4All. URL: http://www.par4all.org/features/.

85. Purdom P. A sentence generator for testing parsers. 2, BIT, pp. 336-375, 1972.

86. Richard Gronback (Borland), Ed Merks (IBM). Eclipse Modeling Project as a DSL Toolkit. Eclipse Foundation Webinar, 2008

87. Robinson R. Automation test tools. URL: http://www.vcaa.com/tools/Rav%20Robinson.pdf, 2001.

88. SandStorm. URL: http://sandstorm.impetus.com/

89. Selenium WebDriver. URL: http://seleniumhq.org/proiects/webdriver/

90. Shyamasundar, V. Murali and R. K. A sentence generator for a compiler for PT, a pascal subset. Software Practice and Experience, CTp. 857-869, 1983.

91. Steinberg B., Alimova E., Bagliy A., Morilev R., Nis Z., Petrenko V., Steinberg R. The System for Automated Program Testing // Proceedings of 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009). Moscow, Russia, September 18-21, 2009. P. 218-221.

92. The ROSE Source-to-Source Compiler Infrastructure. URL: http://rosecompiler.org/.

93. TILE64 Processor. URL: http://www.tilera.com/products/processors/TILE64.

94. Top500. URL: http://www.top500.org.

95. W3C Markup Validation Service. URL: http://validator.w3.org

96. W3C standards. URL: http://www.w3.org/standards/

97. Websecurify. URL: http://www.websecurifV.com/

98. XHTML 1.0. The Extensible HyperText Markup Language (Second Edition), http://www.w3 .org/TR/xhtml 1/

99. Zhu H., Hall P. A. V., May J. H. R. Software Unit Test Coverage and Adequacy. ACM Computing Surveys, pp. 366-427, Dec. 1997.