Генерация наборов тестов для распараллеливающих и оптимизирующих преобразований в компиляторе Алымова, Елена Владимировна

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 7^th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009), Moscow, Russia, September 18-21, 2009; Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи», Новороссийск, 20-25 сентября 2010 г; V Международная конференция «Параллельные вычисления и задачи управления» (PACO’2010), ИПУ РАН, Москва, 26-28 октября 2010 г.

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

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

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