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

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

АРАПБАЕВ Русланбек Нурмаматович

АНАЛИЗ ЗАВИСИМОСТЕЙ ПО ДАННЫМ: ТЕСТЫ НА ЗАВИСИМОСТЬ И СТРАТЕГИИ ТЕСТИРОВАНИЯ

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск -2008

0034540 17

003454017

Работа выполнена в Институте систем информатики имени А. П. Ершова СО РАН

Научные руководители:

Официальные оппоненты:

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

Евстигнеев Владимир Анатольевич, доктор физико-математических наук, профессор

Касьянов Виктор Николаевич, доктор физико-математических наук, профессор.

Малышкин Виктор Эммануилович доктор технических наук, профессор.

Акжолов Маматжан Жолчуевич кандидат физико-математических наук, доцент.

Южный Федеральный Университет (г. Ростов-на-Дону).

Защита состоится 12 декабря 2008 г. в15 ч 30 мин на заседании диссертационного совета К003.032.01 в Институте систем информатики им А.П. Ершова Сибирского отделения РАН по адресу 630090, г. Новосибирск, пр. Лаврентьева, 6.

С диссертацией можно ознакомится в читальном зале ИСИ СО РАН (пр. Лаврентьева, 6)

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

Ученый секретарь диссертационного совета К003.032.01

Мурзин Ф.А.

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

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

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

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

В последние годы интерес к этой тематике снова возрос, и были предложены более эффективные методы, которые получили название тестов на зависимость (data dependence test). Среди них на практике наибольшее распространение получили НОД-тест и тест на основе неравенства Банержи, специально разработанные Утополом Банержи (Banerjee).

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

большей точностью, но обычно требуют для этого много времени. Поэтому на практике используется алгоритм зависимости по данным, который состоит из серии тестов, исполняемых в определенном иерархическом порядке. Например, в проекте SUIF1 алгоритм состоит из серии точных тестов, где последним тестом служит метод исключения Фурье-Моцкина. В распараллеливающем компиляторе Parafrase-22 используется стратегия применения НОД-теста и теста Банержи, а в системе ОРС3 применяется тест Банержи-Вольфа, а также поддерживается идея полуавтоматического распараллеливания. Однако до сих пор остается открытым вопрос, какая последовательность или стратегия лучшая.

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

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

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

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

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

• Исследование существующих тестов на зависимость и сопоставление их сильных и слабых сторон;

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

• Реализация библиотеки тестов на зависимость по данным;

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

• Проведение экспериментов, подтверждающих корректность и эффективность предложенных методов.

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

1 Система разработана в Стэидфордском университете под руководством M Lam

2 Проект разработан в Иллинойском университете под руководством С Polychronopoulos

3 Открытая распараллеливающая система разрабатывается в Ростовском государственном университете под руководством Б Я Штейнберга

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

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

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

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

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

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

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

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах.

1. Международная научная конференция "Параллельные вычислительные технологии" (ПаВГ2007), Челябинск, Россия, 2007 г.

2. VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Кемерово, 2005.

3. IV Российско-Германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах, Новосибирск, ИВТ СО РАН, 2007.

4 Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2006 г.

5. VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Красноярск, 2006.

6. Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2008 г.

7. XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 г.

8. Семинары «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2003-2008 гг.

Публикации. Основные' результаты диссертационной работы опубликованы в 12 работах, среди которых 4 статьи, 1 препринт и 7 тезисов докладов.

Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН по проекту 3.15 «Методы и средства трансляции и конструирования программ» программы 3.1 СО РАН «Информационное и математическое моделирование в различных областях знаний, задачи поддержки принятия решений, экспертные системы, системное и теоретическое программирование» и частично поддерживались грантом РФФИ (№07-07-12050).

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

Диссертационная работа состоит из введения, трех глав и списка литературы. Объем диссертации - 116 стр. Список литературы содержит 109 • наименований.

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

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

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

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

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

Традиционно под зависимостью по данным понимается зависимость, связанная с совпадением с сыпок на элементы массивов. Пусть в гнезде г вложенных ОО-циклов, операторы 8[ и Бг обращаются к а( - мерному массиву А индексные выражения которого представлены линейными функциями 1Ъ . . . , /' г)и ¿^ц, ¡2, .... I г), где ? = 1, . . , , Л Зависимость по данным между операторами в! и 52 имеется тогда и только тогда, когда существуют целые /|, 1Ъ .. , /г и/1, ]!,..., ]'г, такие что

Й1(/1, (2. • ■ • . 1г) = ^(/ь )ъ ■ ■ ■. У г),

Ый, '2.....I.) = йОьН-----УД (1)

hA.ii, (2, .... <г) = /2, • •.,]',) и

г'/»Ур е [1р.ир1 (2)

где р = 1,..., г.

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

Если имеется «-мерный массив А и индексные выражения массива линейны, то тогда система (1) может быть записана в следующем виде:

ОцХ 1 + 0112^2+-•■+в1пДГп+С)=0 Я21 •*! + апх2+- + а2„хп+с2 =0

............................(3)

ат 1*1 + атгхг+ .. + атхп+ст =0 и

Ь,<,х,< и, где ¡'=1,...,п. (4)

В разделах 1.2. и 1.3. приводится сравнительный анализ тестов на зависимость. Также приведена обширная классификация тестов на зависимость по использованию различных математических инструментов и по сложности применения их на практике. В частности сначала описываются три основных метода нахождения зависимости по данным: НОД-тест, тест Банержи и метод исключения переменных Фурье-Моцкина. Далее рассматриваются расширенные варианты предыдущих методов, которые делятся на два вида: приближенные тесты и точные тесты. К приближенным тестам относятся обобщенный НОД-тест, Х-тест, 1-тест и их различные модификации. Точные тесты используют более сложные методы: Ро\уег-тест, Омега-тест и Ж-тест. В разделе 1.4. отмечены другие тесты на зависимость, которые в рамках

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

Раздел 1.5. представляет новый модифицированный Х.-тест для анализа ссылок в многомерных массивах. Сравнительный анализ показал, что при анализе зависимостей в цикле ключевой проблемой является работа с многомерными массивами. Общий подход состоит в индивидуальном тестировании уравнений (тестирование "индекс-за-индексом") из (3) вместо проверки существования решения системы в целом. Однако система уравнений зависимости может не иметь решения даже в том случае, когда имеются решения в каждом из отдельных уравнений.

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

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

Геометрически каждое линейное уравнение системы (3) представляет собой гиперплоскость я. в пространстве К". Пересечение гиперплоскостей 5 соответствует общим решениям системы уравнений. Границы циклов (4) соответствуют ограниченному выпуклому множеству V в К". Если можно найти новую гиперплоскость, которая содержит 5, и не имеет целочисленных •точек пересечения с V, то это доказывает, что Б не имеет целочисленных значений в V, следовательно, зависимости по данным не существует. Данная гиперплоскость является линейной комбинацией уравнений системы.

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

=0 системы уравнений (3), такая, что лпУ не имеет целочисленных точек, где < а,,х> — скалярное произведение а,=( йц аЛ.....а1Г)

И д: ..*„)•

Предложенный алгоритм с помощью Я-теста генерирует множество линейных комбинаций гиперплоскостей. Затем применяется IR-тсст для нахождения гиперплоскости из данного множества, которая не имеет целочисленных точек пересечения с V. Экспериментальные сравнения результатов показали, что модифицированный алгоритм более точен по сравнению с НОД-, Банержи- и ^-тестами на зависимость. Таким образом, модифицированный ).-тест является точным тестом для выявления зависимости по данным в многомерных массивах, содержащих сцепленные индексы.

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

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

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

Дельта-тест разработан для определенных классов ссылок массива, которые часто встречаются в научных программных кодах. Тест сначала классифицирует индексные выражения массивов на следующие категории: ZIV (нулевая индексная переменная), SIV (единственная индексная переменная) и MIV (составная индексная переменная) формы. Соответственно к каждой форме применяются одноименные тесты.

В. Пью (W. Pugh) и Т. Шпейзман (T. Shpeisman) предложили более упрощенный и быстрый вариант Дельта-теста, называемый Эпсилон - тестом. В этом тесте рассмотрены только самые простые случаи индексных выражений SIV, не используются сцепленные MIV формы и НОД-тест, а также не рассматриваются треугольные границы цикла при использовании теста Банержи. Хотя эти алгоритмы являются самыми быстрыми, но они уступают по точности предложенному в данной диссертационной работе алгоритму.

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

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

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

Раздел 2.2. начинается кратким обзором тестов на зависимость, используемых в предложенной новой стратегии тестирования. Тесты можно классифицировать на одномерные и многомерные. Одномерные тесты: SIV-тест, НОД-тест, тест Банержи, I-тест и IR-тест. Многомерные тесты: к-тест, многомерный 1-тест,и модифицированный л-тест. Идея нашей стратегии опирается на следующие научные факты и результаты.

Основные результаты существующих эмпирических исследований. Объектом автоматического распараллеливания служат большие пакеты научных прикладных программ, написанных на последовательных языках типа Фортран. Согласно эмпирическому изучению Шена (Shen) и др., в реальных программах индексные выражения не очень сложны. Из всех исследованных массивов примерно 56% составляют ссылки одномерных массивов и 36% -ссылки двухмерных массивов. Доля ссылок трехмерных (и выше) массивов составляет около 8 %. Что касается индексных выражений массивов, то 53 % являются линейными, 13 % - частично линейными и 34 % - нелинейными. Поэтому обычно для анализа зависимостей по данным на практике применяются только одномерные тесты, использующие подход тестирования "индекс-за-индексом".

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

Случаи повышающие точность тестов на зависимость. Точно определяющие методы: Омега-тест, Power-тест, алгоритм Майдана и др. используют линейные и целочисленные методы для решения диофантовых уравнений, например, метод Фурье-Моцкина, Симплекс метод и др., которые не эффективны на практике. В экспериментальных результатах Р. Триоле (Triolet R.) показано, что по сравнению с более простыми методами, метод исключения переменных Фурье-Моцкина выполняется в 22-28 раз дольше.

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

внимание границы циклов. Эффективность и полноценность теста Банержи при опровержении зависимостей, делают его одним из самых используемых тестов в распараллеливающих компиляторах. В исследованиях Банержи, 3 Ли (2.1л) и Д. Клапхольц (О. ЮаррИоЬ) показано, что если коэффициенты линейного уравнения удовлетворяют некоторым условиям, то тест Банержи становится точным. Банержи показал, что его неравенства точны, если все коэффициенты индексных переменных равны 1, 0, или -1. Ли и др. показали, что неравенства Банержи точны, если коэффициент одной индексной переменной (я*1=1 и (а,|<(Ц, - Ь,), где /=1,...,к-1,к+1,...,п.

Клапхольц и др. доказали, что неравенства Банержи точны, если после упорядочения коэффициентов индексных переменных ]<зг)| < \а2\ <, ... < \а„\, коэффициент индексной переменной |<21|=1 и для каждого } выполняется .м

условие [а(<1 + -4), 2 </<п.

Л=1

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

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

На вход алгоритма подается гнездо цикла, в котором г - количество вложенных циклов, и операторы цикла обращаются к элементам й-мерного массива. Кроме того, считаются постоянными и известными значения коэффициентов индексных переменных ац, «п атп и значения границ циклов ¿1, ¿2,..., ,иь Щ,.... и„, где п=2*г и т=<1. Задача нашего алгоритма -выявить зависимости по данным между операторами в итерациях гнезда циклов, те. алгоритм должен возвращать ответ «да/нет» о существовании целочисленных решений г'ь /п системы линейных диофантовых уравнений (3), удовлетворяющих ограничениям (4).

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

1. г=1, (1=1, т.е. внутри единственного цикла операторы обращаются к элементам одномерного массива В этом случае уравнение зависимости (3) выглядит так: йг( Х{ + а2 хг= ао и Ь< хи хгШ. Для уравнения целесообразно применить самый быстрый и точный 51\/-тест.

2. г> 1, А= 1, уравнение зависимости имеет вид а[ х^ + а2хг+.. + ап хп= аа, где Ь,<х,<и„ 1=1,...,п. Этот случай несколько усложняет решение, поэтому применяется серия одномерных тестов на зависимость: тест Банержи, 1-тест и Ж-тест. Каждый следующий тест выполняется только

в том случае, если предыдущим тестом был получен неточный ответ (maybe), кроме того, после применения теста Банержи выполняется проверка коэффициентов индексных переменных для уточнения ответов теста.

3. d=2 и имеются сцепленные индексы. Система уравнений зависимости имеет вид

«1,1 + 01,2*2+- ••+ = «1.0 «2,1*1 + «2.2*2+- •+ «2,11*11= «2,0 и L,<x,<U, где (=1,...,я.

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

4. В оставшихся случаях уравнение зависимости имеет вид (3) с ограничениями (4). Каждое уравнение рассматривается в отдельности, и для него последовательно применяется серия одномерных тестов: тест Банержи, I-тест и IR-тест. Этот подход дает более точный ответ, если индексные переменные не сцеплены. На практике доля сцепленных индексных переменных в ссылках трехмерных массивов и выше незначительна.

Учитывая все случаи, была собрана и реализована библиотека тестов на зависимость. Библиотека состоит из следующих тестов: ZIV-тест, SIV-тест, НОД-тест, Банержи-тест, 1-тест, IR-тест, А,-тест, многомерный I-тест и модифицированный Х-тест. Кроме тестов на зависимость в библиотеке имеются алгоритмы для уточнения ответов теста Банержи. Все алгоритмы имеют линейную временную сложность. Из-за высокой стоимости в библиотеку не вошли точные тесты. На рис. 1 приведена общая схема новой стратегии применения тестов на зависимость.

Временная сложность. Новый алгоритм имеет наихудшую временную сложность в двух случаях:

1) при применении серии одномерных тестов на зависимость;

2) при применении серии двухмерных тестов на зависимость.

Рассмотрим отдельно каждый случай. В первом случае тест Банержи имеет

временную сложность О (и), I-тест - 0(п2*с+п*с) и IR-тест - О(кя), где A=min{ u,-l,+1: п - количество переменных в уравнении зависимости, с -

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

наихудшая временная сложность - 0(<1*( п2*с+п*с + п + к*п + с)), где й — размерность массива.

Во втором случае используются более сложные механизмы, но в нашем алгоритме они применяются только для двухмерных массивов, где индексы являются сцепленными. Следовательно, трудоемкость методов несколько уменьшается. Например, Х-тест имеет временную сложность 0(п*(г+с)), многомерный 1-тест - ()(п*(х2*с+7*с+с)) и модифицированный Х-тест -0(и*(к*2+с)), где г - число переменных в сгенерированной Х-плоскости. В общем случае временная сложность - 0(п*( г2*с+г*с+ г+к*г+с)).

неизвестны грашцы цикла

-*|0-

имеется ZIV индекс te»-

■d=l Иг=1 а 1 = аа

|0-

НОД -тест

-из—

ZIV-тест

-СП-сильный S ГУ-тест

—т

—

уа и* 0ИЛИш *= 0_слабо-нулевой S ГУ-тест

о-К=3-

шдр счуч Бакержи, 1-тест. IR-тесг

тО-кЗ-i-[=3-

Выход

^CJwÎo-пересекаюпдай SW-тест

-—-КЗ

Выход

Выход

»а

Выход

rd=l Иг>1

О-

^ Г^2И индексы сцеп цены

дрспуч.

Банержк. 1-тест. lR-тест

-HZ1»

Х-тест, мног 1-тести

-инь®-о

тестер индекс за-индексом _ Банержи, 1-тест, ÎR-тест

Выход

-KD

Выход

-O-KZ)

_____ Выход

чин>о

X -тест Выход

-ою

Выход

Рис 1 Общая схема новой стратегии тестирования для выявления зависимости по данным • - алгоритм проверки коэффициентов, □ - тесты на зависимость

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

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

Глава начинается (раздел 3.1.) с описания некоторых деталей алгоритма новой стратегии и программной реализации библиотеки тестов на зависимость.

Далее рассматривается характеристика системной среды и структура инструментов для проведения эксперимента. Также описывается конструкция прототипа распараллеливающего компилятора на основе новой стратегии тестирования и библиотек системы SUIF.

В разделе 3.2. проводится экспериментальное сравнение результатов предложенного метода с наиболее известными стратегиями тестирования анализа зависимостей по данным, такими как Эпсилон-тест и алгоритм Майдана. Эксперимент проведен с использованием инструмента Petit VI.2, разработанного в Мэрилендском университете как расширенный вариант инструмента tiny, и с использованием системы SUIF, разработанной в Стенфордском университете. Обе программы были установлены на персональном компьютере с процессором AMD Athlon ХР 1700+ с операционной системой Debian GNU/Linux. Для эксперимента использованы два вида данных. Первый - набор тестовых научных программ NASA и PERFECT Club benchmarks (PERFormance Evaluation for Cost-efiective Transformations), где каждая программа состоит от 500 до 18000 строк (см. табл. 1). Второй вид - набор из 16 циклов собранный из работ аналогичных нашей. Все циклы являются специальными примерами и созданы для демонстрации мощности некоторых тестов на зависимость по данным.

Таблица 1

Статистические характеристики эталонных тестовых программ

№ Эталонные тестовые программы Количество строк программ Количество подпрограмм Количество СЮ-цикпоа Количество ссылок на массивы

1 LGSI 2815 36 161 6389

2 LWSI 1430 17 56 906

3 SDSI 8446 80 259 658

4 TISI 579 В 78 84

5 btrix 159 1 14 488

6 cholsky 53 1 18 70

7 smtry 117 1 14 369

в gosser 19 2 5 7

Всего 13618 146 605 8971

Сравнение результатов. С помощью пакетов basesuif 1.3.0.1, suifbuilder 1.3.0.1, baseparsuif 1.3.0.1 и suifcookbook 1.3.0.1 системы SUIF собраны два анализатора зависимостей по данным. Первый основан на алгоритме Майдана, а во втором внедрена новая стратегия. Каждый анализатор принимает на входе преобразованный в SUIF формат (с помощью see драйвера) *.spd файл последовательной программы, а на выходе дает информацию о всех зависимостях по данным в данной программе. При экспериментальном сравнении результатов рассматривались только истинные (потоковые) циклически порожденные зависимости по данным.

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

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

Таблица 2

Сравнение результатов

.V» Эталонные тестовые программы Всего обрщ. на ИСТИН. завис. Кол-во разрушенных зависимостей

Алгоритм Мьйдана Новая стратегия

] LGSI 6168 5546 89,92% 5546 89,92%

2 LWSI 795 102 12,83% 102 12,83%

3 SDSI 417 154 36,93«/. 149 35,73%

4 TBI 52 0 0,00% 0 0,00%

5 btrir 450 208 46,22% 208 46,22%

6 cholsky 61 3 4,92% 0 0,00%

7 emtry 258 125 48,45% 119 46,12%

S goner 5 0 0,00% 0 0,00%

Всего 8206 6138 74,80% 6124 74,63%

Сравнение результатов на экспериментальных примерах.

Статистические характеристики экспериментальных примеров: количество строк - 66, количество DO-циклов - 26, количество ссылок на массивы - 40. Эти примеры взяты из аналогичных работ описывающих тесты на зависимость такие как Power-тест (авторы M Вольф и др.), Омега-тест (автор В.Пью) и др. В данных примерах индексные выражения более сложны, чем реальные программы. В этом случае мы сравнивали результаты следующих алгоритмов: Эпсилон-тест, алгоритм Майдана и новая стратегия тестирования. С помощью инструмента Petit к экспериментальным примерам применялся Эпсилон-тест. Для 40 пар ссылок массивов Эпсилон-тест 44% случаев показал независимость по данным, алгоритм Майдана - 63%, а новая стратегия тестирования для выявления зависимости по данным - 56%.

Время выполнения. Для определения того, какой метод требует больше времени исполнения, использован GNU профилировщик 'gprof операционной системы Linux. Чтобы снизить статистические неточности, каждый алгоритм зависимости по данным выполнен 100 раз для различных эталонных тестов и взято их усредненное значение. В общем случае алгоритм Майдана требовал времени па 25% больше, чем алгоритм новой стратегии (см. Рис. 2).

Алгоритм MañqaHa

Новая стратегия

Рис. 2. Время выполнения

Статистические данные Новой стратегии. По итогам эксперимента были анализированы статистические данные новой стратегии. Результаты еще раз показывают целесообразность и эффективностью методов, предложенных в предыдущей главе. В большинстве случаев зависимости по данным выявляются с помощью простых тестов (ZIV-тест, SIV-тест, Банержи тест и Х-тест). Помощь более сложных тестов (1-тест, IR-гест, Многомерный I-тест и Модифицированный Х-тест) требовалась в незначительных случаях. Это достигается с помощью алгоритмов, уточняющих ответы теста Банержи. Так в 361 случае с помощью теста Банержи в 54 случаях опровергнуты зависимости по данным, а 301 случае алгоритм проверки коэффициентов доказывает существование зависимости. Это позволяет сократить общее время выполнения новой стратегии, так как после положительного ответа алгоритма проверки исключается выполнение последовательности более сложных тестов. В 71 случае с помощью А.-тесга опровергнуты зависимости по данным в 2 случаях, а 67 случае алгоритм проверки коэффициентов доказывает существование зависимости.

Раздел 3.3 посвящен к построению алгоритма для индексного анализа зависимостей по данным в Sisal-программах для SFP системы. Отметим, что она является системой функционального программирования и разрабатывается в Лаборатории конструирования и оптимизации программ ИСИ СО РАН в рамках проекта ПРОГРЕСС, где в качестве начальной версии входного языка выбран Sisal.

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

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

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

2. Разработан новый эффективный тест (модифицированный Х.-Тест) для решения проблемы зависимости по данным при анализе сцепленных ссылок многомерных массивов.

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

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

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

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

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

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

1. Евстигнеев В. А., Арапбаев Р. Н., Осмонов Р. А. Анализ зависимостей: основные тесты на зависимость по данным II Сиб. журн. вычисл. математики / РАН, Сиб. отд-е. — Новосибирск, 2007. — Т. 10, № 3. — С 247-265.

2. Арапбаев Р. Н. Анализ зависимостей по данным: стратегии тестирования и экспериментальное сравнение результатов // Аннотации докл. научной сессии IV Российско-Германской школы по параллельным вычислениям на высокопроизводительных вычислительных системах. — Новосибирск, Академгородок, 9-20 июля 2007г. / Вычислительные технологии — 2007. — Т. 12, №6,—С. 138-142.

3. Арапбаев Р. Н., Осмонов Р. А. Анализ зависимостей по данным для многомерных массивов на базе модифицированного Х-теста // Проблемы интеллектуализации качества систем информатики / РАН, Сиб. отд-е, Ин-т систем информатики. — Новосибирск, 2006. — С. 7-23.

4. Арапбаев Р. Н. Экспериментальное исследование новой стратегии // Методы и инструменты конструирования программ. / РАН, Сиб. отд-е, Ин~т систем информатики. — Новосибирск, 2007. — С. 7-23.

5. Арапбаев Р. Н., Осмонов Р. А. Анализ зависимостей: новая стратегия тестирования // Труды Международной конференции «Параллельные вычислительные технологии (ПаВТ'2007)». — Челябинск: изд-во ЮУрГУ, 2007, —Т.2. —С. 16-27.

6. Арапбаев Р. Н., Евстигнеев В. А., Осмонов Р. А. Сравнительный анализ тестов на зависимость по данным. — Новосибирск, 2006. — 36 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 141).

7. Арапбаев Р. Н. Анализ зависимостей по данным: стратегии тестирования и экспериментальное сравнение результатов // Научная сессия IV Российско-Германской школы по параллельным вычислениям на высокопроизводительных вычислительных системах / РАН, Сиб. отд-е, Ин-т выч. техн. —Новосибирск, 2007. — С. 11-14.

8. Арапбаев Р. Н. Новая стратегия применений тестов для выявления зависимостей по данным // VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. — Красноярск, 2006. — С. 78.

9. Арапбаев Р. Н., Осмонов Р. А. Новый алгоритм анализа зависимостей по данным в многомерных массивах // VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. — Кемерово* изд-во КемГУ, 2005. —■ С. 57.

10.Арапбаев Р. Н., Осмонов Р. А., Фомин А. С. Программный комплекс для анализа зависимостей по данным // Конференция-конкурс «Технологии Microsoft в теории и практике программирования». — Новосибирск, 2008. — С. 99-101.

11.Арапбаев Р.Н., Осмонов Р.А. Анализ зависимостей по данным для многомерных массивах с учетом векторов направлений // Конференция-конкурс «Технологии Microsoft в теории и практике программирования». —• Новосибирск, 2006. — С. 153-155.

12. Арапбаев Р.Н., Осмонов Р. А. Сравнительный обзор тестов на зависимость по данным // XLIV Междунар. науч. студенческая конф. «Студент и научно-технический прогресс»: Информационные технологии / НГУ — Новосибирск, 2006. — С. 4-5.

Л РАН БАЕВ Русланбек Нурмаматович

АНАЛИЗ ЗАВИСИМОСТЕЙ ПО ДАННЫМ: ТЕСТЫ НА ЗАВИСИМОСТЬ И СТРАТЕГИ» ТЕСТИРОВАНИЯ

Авгореф. дисс. на соискание учёной степени кандидата физико-математических наук. Подписано в печать 06.11.2008. Заказ № 99. Формат 60x90/16. Усл. печ. л. 1. Тираж 100 экз. Отпечатано в издательском отделе Института катализа им. Г.К. Борескова СО РАН 630090 Новосибирск, пр. Академика Лаврентьева, 5

ВВЕДЕНИЕ.

1. АНАЛИЗ ЗАВИСИМОСТЕЙ: ТЕСТЫ НА ЗАВИСИМОСТЬ ПО ДАННЫМ.

1.1. Основные понятия и определения.

1.1.1. Модель программы.

1.1.2. Определение зависимостей по данным.

1.1.3. Граф зависимостей по данным.

1.1.4. Анализ зависимостей по данным.

1.2. Основные методы.

1.2.1. НОД-тест.

1.2.2. Тест Банержи.

1.2.3. Метод исключения переменных Фурье-Моцкина.

1.3. Расширенные методы.

1.3.1 Приближенные тесты.

Обобщенный НО Д-тест.

1-тест.

1-тест (Интервальный тест).

1.3.2. Точные тесты.

Роу/ег-тест.

Омега-тест.

Ж-тест.

1.4. Другие тесты на зависимость по данным.

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

1.5.1. Постановка проблемы.

1.5.2. Модифицированный Я-тест.

1.5.3. Алгоритм.

1.5.4. Сравнение результатов.

1.5.5. Временная сложность.

Выводы по главе 1.

2. АНАЛИЗ ЗАВИСИМОСТЕЙ ПО ДАННЫМ: СТРАТЕГИИ

ТЕСТИРОВАНИЯ.

2.1. Существующие алгоритмы анализа зависимостей по данным

2.1.1. Дельта-тест.

ZIV-тест.

SIV-тест.

MIV-тест.

2.1.2. Эпсилон-тест.

Эпсилон-Омега тест.

2.1.3. Алгоритм Майдана.

SVPC-тест ("single variable per constraint").

АсусПс-тест.

LR-тест (" loop residue").

2.1.4. К-тест.

Организация интеллектуального подхода.

2.2. Новая стратегия применений тестов на зависимость.

2.2.1. Библиотека тестов на зависимость по данным.

Одномерные тесты.

Многомерные тесты.

2.2.2 Основные результаты существующих исследований.

2.2.3. Случаи, повышающие точность тестов на зависимость.

2.2.4. Алгоритм стратегии.

2.2.5. Временная сложность.

Выводы по главе 2.

3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ.

3.1. Программный комплекс для анализа зависимостей по данным.

3.1.1. Реализация библиотеки тестов на зависимость и алгоритма новой стратегии.

3.1.2. Система SUIF.

3.1.3. Прототип распараллеливающего компилятора на основе новой стратегии тестирования на зависимость и библиотек системы SUIF

3.2. Экспериментальное сравнение результатов.•.

3.2.1. Системная среда.

3.2.2. Сравнение результатов.

3.2.3. Сравнение результатов на экспериментальных примерах.

3.2.4. Время выполнения.

3.2.5. Статистические данные Новой стратегии.

3.3. Индексный анализ зависимостей по данным в Sisal -программах

3.3.1. Язык функционального программирования SISAL.

3.3.2. Промежуточное представление IR1.

3.3.3. Построение алгоритма индексного анализа зависимостей по данным.

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

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

Особенности используемого алгоритма анализа зависимостей.99 Интерпретация и использование результатов анализа в целях оптимизации.

Выводы по главе 3.

Актуальность темы.

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

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

Тем не менее, прямой подход к решению задачи выявления зависимостей в общем случае невозможен, так как даже для линейных индексных выражений массивов это приводит к МР-полной проблеме отыскания целочисленного решения системы диофантовых уравнений (уравнение зависимости). Один из способов строгого решения этой проблемы был предложен в 1976 г. Тоулем (Towel) [101]. Однако метод был слишком трудоемким, чтобы его можно было использовать на практике в распараллеливающих компиляторах. Позднее были разработаны быстрые приближенные методы, которые «ошибочно» предполагают существование решения уравнения зависимости. Конечно, использование таких некорректных предположений никогда не приводит к ошибочному объектному коду, но может мешать некоторым оптимизациям.

В последние годы интерес к этой тематике снова возрос, и были предложены более эффективные методы, которые получили название тестов на зависимость (data dependence test). Среди них на практике наибольшее распространение получили НОД-тест и тест на основе неравенства Банержи, специально разработанные Утополом Банержи (Banerjee) [44; 46].

Тесты на зависимость используют различные математические инструменты, и каждый из них имеет различную сложность и разрешающую способность. Мощные алгоритмы могут выявлять зависимости по данным с большей точностью, но обычно требуют для этого много времени. Поэтому на практике используется алгоритм зависимости по данным, который состоит из серии тестов, исполняемых в определенном иерархическом порядке. Например, в проекте SUIF1 алгоритм состоит из серии точных тестов, где последним тестом служит метод исключения Фурье-Моцкина. В распараллеливающем компиляторе Parafrase-22 используется стратегия применения НОД-теста и теста Банержи, а в системе ОРС3 применяется тест Банержи-Вольфа, а также поддерживается идея полуавтоматического распараллеливания. Однако до сих пор остается открытым вопрос, какая последовательность или стратегия лучшая.

1 Система разработана в Стэндфордском университете под руководством М. Lam

2 Проект разработан в Иллинойском университете под руководством С. Polychronopoulos

3 Открытая распараллеливающая система разрабатывается в Ростовском государственном университете под руководством Б. Я. Штейнберга.

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

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

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

Цель работы

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

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

• Исследование существующих тестов на зависимость и сопоставление их сильных и слабых сторон;

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

• Реализация библиотеки тестов на зависимость по данным;

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

• Проведение экспериментов, подтверждающих корректность и эффективность предложенных методов.

Методы исследования

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

Научная новизна

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

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

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

Выработана новая стратегия тестирования, основанная на новых тестах анализа зависимостей по данным. При построении стратегии использованы факты и результаты некоторых эмпирических и теоретических исследований анализа зависимостей по данным, позволившие оптимизировать общее время выполнения алгоритма новой стратегии. На основе новой стратегии и библиотеки тестов на зависимость создан программный комплекс анализа зависимостей по данным, а также построен алгоритм для индексного анализа зависимости по данным в 81за1-программах в рамках системы функционального программирования (БГР).

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

Практическая ценность

Полученные результаты являются неотъемлемой частью системы быстрого прототипирования распараллеливающего компилятора и системы функционального программирования (SFP), разрабатываемых в рамках проекта ПРОГРЕСС [71]. Результаты могут быть использованы при решении практических задач, а именно при разработке распараллеливающих компиляторов. В частности, разработанные автором диссертации методы могут стать основой для построения алгоритмов выявления зависимости по данным между итерациями DO-циклов в блоке зависимостей в системе быстрого прототипирования распараллеливающего компилятора.

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

Апробация работы

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

1. Международная научная конференция "Параллельные вычислительные технологий" (ПаВТ'2007), Челябинск, Россия, 2007 г.

2. VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых),'Кемерово, 2005.

3. IV Российско-Германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах, Новосибирск, ИВТ СО РАН, 2007.

4. Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2006 г.

5. VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Красноярск, 2006.

6. Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2008 г.

7. XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 г.

8. Семинары «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2003-2008 гг.

Публикации

Основные результаты диссертационной работы опубликованы в 12 работах, среди которых 4 статьи [8; 10; 11; 25], 1 препринт [9] и 7 тезисов докладов [5; 6; 7; 15; 12; 14; 13].

Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН по проекту 3.15 «Методы и средства трансляции и конструирования программ» программы 3.1 СО РАН «Информационное и математическое моделирование в различных областях знаний, задачи поддержки принятия решений, экспертные системы, системное и теоретическое программирование» и частично поддерживались грантом РФФИ (№07-07-12050).

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

Диссертационная работа состоит из введения, трех глав и списка литературы. Объем диссертации - 116 стр. Список литературы содержит 109 наименований.

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

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

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

4. Выработана новая стратегия тестирования, основанная на новых тестах анализа зависимостей по данным. На базе новой стратегии и библиотеки тестов на зависимость создан программный комплекс анализа зависимостей по данным, а также реализован анализатор зависимости по данным в 81за1-программах в рамках системы ЗБР.

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

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

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

ЗАКЛЮЧЕНИЕ

1. Аллен Р., Кеннеди К. Автоматическая трансляция Фортран-программ в векторную форму .//Векторизация программ: теория, методы, реализация. — М.:Мир, 1991. —С. 77-140.

2. Антонов А. С. Современные методы межпроцедурного анализа программ // Программирование. — 1998. — № 5. — С. 3-14.

3. Академгородок, 9-20 июля-2007г. / Вычислительные технологии -—2007. —Т. 12, №6. —С. 138-142.

4. Арапбаев Р. Н. Новая стратегия применений тестов для выявления зависимостей по данным // Тез. докл. У1Г Всероссийской конференции молодых .ученых по; математическому моделированию и информационным технологиям; — Красноярск, 2006. — С. 78.

5. Арапбаев P. II. Экспериментальное исследование новой стратегии // , Методы и инструменты конструирования программ. / РАН, Сиб. отд-е,

6. Ин-т систем информатики. — Новосибирск, 2007. — С. 7-23.9: Арапбаев Р. Н., Евстигнеев В; А., Осмонов Р. А. Сравнительный анализ тестов на зависимость по данным. — Новосибирск, 2006. — 36 с. — (Препр. / РАН. Сиб. огд-е. ЙСИ; № 141).

7. Арапбаев Р. Н., Осмонов Р. А. Анализ зависимостей: новая стратегия тестирования // Труды Международной конференции «Параллельные вычислительные технологии (ПаВТ'2007)». :— Челябинск: изд-во ЮУрГУ, 2007. — Т.2. — С. 16-27. . ,,

8. Арапбаев Р. Н., Осмонов Pi А., Фомин-А. С. Программный комплекс для анализа зависимостей по данным // Тез. докл. конференции-конкурса «Технологии Microsoft в теории и практике программирования». — Новосибирск, 2008. — С. 99-101.

9. Арапбаев Р.Н., Осмонов Р. А. Сравнительный обзор тестов на зависимость по данным // Тр. XLIV Между нар. науч. студенческойконф. «Студент и научно-технический прогресс»: Информационные технологии / НГУ — Новосибирск, 2006. -- С. 4-5.

10. Арапбаев P.M., Осмонов P.A. Анализ зависимостей по; данным для? многомерных массивах с учетом векторов направлений // Тез; докл. конференции-конкурса «Технологии Microsoft в теории и. практике программирования».—Новосибирск, 2006. — С. 153-155.

11. Ахо А., Хопкрофт Дж., • Ульман Дж. Построение и анализ вычислительных алгоритмов. — М., «Мир», 1979.—536 с.

12. Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. — М.: Радио и связь. — 1989. — 176 с.

13. Вальковский В. А., Малышкин В; Э. Синтез параллельных программ и систем на вычислительных моделях:/РАН; Сиб.отд-е. —Новосибирск: «Наука», 1988. — 129 с.

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

15. Воеводин В. В. Информационная структура алгоритмов. — М.: изд-во МТУ, 1997. .

16. Густокашина Ю. В., Евстигнеев В. A. IF1 — промежуточное представление Sisal-программ // Проблемы конструирования? эффективных и надежных программ. — Новосибирск, 1995. — С. 70-78.

17. Дроздов А. Ю., Корнев Р. М., Боханко А. С. Индексный: анализ; зависимостей по данным // Информационные технологии и вычислительные системы. — 2004. — Т. 3. — С. 27-37.

18. Евстигнеев В. А. Анализ зависимостей: состояние проблемы // Системная информатика: Сб. науч. тр. /РАН, Сиб. отд-е, Ин-т систем информатики. — Новосибирск: Наука, 2000-Вып. 7. — С. 112-173.

19. Евстигнеев В. А. Применение теории графов в программировании// М.: «Наука», Главная редакция физико-математической литературы, — 1985 г. — 352 с.

20. Евстигнеев В. А., Арапбаев Р. Н., Осмонов Р. А. Анализ зависимостей: основные тесты на зависимость по данным // Сиб. журн. вычисл. математики / РАН, Сиб. отд-е. — Новосибирск, 2007. — Т. 10, № 3. — С. 247-265.

21. Евстигнеев В. А., Касьянов В ,Н. Оптимизирующие преобразования в распараллеливающих компиляторах // Программирование, 1996. — № 6.1. С. 12-26.

22. Евстигнеев В. А., Мирзуитова И. А. Анализ циклов: выбор кандидатов на распараллеливание. — Новосибирск, 1999. — 41 с. — (Препр. / РАН, Сиб. отд-е, Ин-т систем информатики. №58).

23. Евстигнеев В. А., Серебряков В. А. Методы межпроцедурного анализа (обзор) // Программирование. — 1992. — N 3. — С. 4-15.

24. Евстигнеев В. А., Спрогис С. В. Векторизация программ: анализ зависимостей. Б.м., — 1989. — (Препр. / АН СССР, НФ ИТМ и ВТ №23).

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

26. Касьянов В. Н., Евстигнеев В; А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003 г.— 1104 с.

27. Касьянов В. Н., Стасенко А. П. Язык программирования Sisal: 3;2;. // Методы и инструменты конструирования* программ / РАН, Сиб. отд-е. Ин-т систем,информатики;—• Новосибирск, 2007. — С. 56-1-34.

28. Логачева С. А. Анализ зависимостей' по данным на базе алгоритма Шостака // Поддержка- супервычислений и Интернет — ориентированные технологии. / РАН, Сиб. отд-е. Ин-т систем информатики. —

29. Новосибирск, 2001. —С. 31-43.

30. Малышкин В.Э;. Введение в "параллельное программирование: мультикомпьютеров. Новосибирск, 2003, ИВМ и МГ СО РАН. -—268 с.

31. Пыжов К.А. Блок редукции в компиляторе Sisal 3.0. // Методы и инструменты конструирования и оптимизации программ / РАН, Сиб. отд-е. Ин-т систем информатики.— Новосибирск, 2005. — С. 185-196.

32. Стасенко А. П; Внутреннее представление системы функционального программирования Sisal 3.0.— Новосибирск, 2004.—54 с. — (Препр. / РАН. Сиб. отд-е. Ин-т систем информатики; № 110).

33. Шульженко А; М. Преимущества: определения информационных зависимостей в программе с помощью решетчатых графов // XIII Международная конференция «Математика. Экономика. Образование.». Тезисы докладов. — Ростов н/Д, 2005.—.С. 195.

34. Allen J. R. Dependence analysis for subscripted variables and its application to program transformations: PhD Thes. (computer sci.) — Rice Univ., 1983.

35. Allen J. R., Kennedy K. Automatic translation of Fortran programs to vector form // ACM Trans. Program Lang. Syst. — 1987. — Vol. 9, N 4. — P. 491542.

36. Banerjee U. An introduction to a formal theory of dependence analysis // The J.of Supercomputing. — 1988. — Vol.2. — P. 133-149.

37. Banerjee U. Data dependence in ordinary programs. — Urbana, 1976. — (Tech. Rep. / Univ.III; 76-837).

38. Banerjee U. Dependence Analysis. Boston, Mass.: Kluwer Academic Publishers. — 1997. — P. 106.

39. Banerjee U. Speedup of ordinary programs. PhD diss. Univ. 111., Rpt N UIUCDCS-R-79-989, 1979.

40. Bernstein A. J. Analysis of Programs for Parallel Processing // IEEE Trans. Electronic Computers. — 1966. — Vol. 15, N 5. — P. 757-763. .

41. Berry M. et al. The PERFECT Club benchmarks: effective performance evaluation of supercomputers. —1989. — 48 p. — (Tech. Rep. / UIUCSRD; N 827).

42. Blume W., Eigenmann R. Nonlinear and Symbolic data dependence testing // IEEE Trans, on Parallel and Distrib. Systems. — 1998. — Vol. 9, N 12. — P. 1180-1194.

43. Blume W., Eigenmann R. The Range Test: A dependence test for symbolic, non-linear expressions // Proc. Supercomputing '94. Washington D.C., Nov., 1994. —P. 528-537.

44. Burke M., Cytron R. Interprocedural dependence analysis and parallelization. — 1986 (Res. Rep / IBM; RC-11794).

45. Chang W.-L., Chu C.-P. The 1+ test // LNCS — 1999. — vol. 1656.— P. 367381.

46. Chang W.-L., Chu C.-P. The infinity Lambda test: A multi-dimensional version of Banerjee infinity test // Parallel Computing. — 2000. — Vol. 26. — P. 1275-1295.

47. Chang W.-L., Chu C.-P., Wu J. The generalized Lambda test // Proc. of the First Merged Symposium on IPPS/SPDP, Orlando, FL, March 1998. — 1998.1. P. 181-186.

48. Chang W.-L., Chu, C.-P., Wu, J. A multi-dimensional version of the I test // Parallel Computing. — 2001. — Vol. 27. — P. 1783-1799.

49. Chang, W.-L., Chu, C.-P., Wu, J. A precise dependence analysis for multidimensional arrays under specific dependence direction // The Journal of Systems and Software. — 2002. — Vol. 63. — P. 99-112.

50. Cooper K., Hall M., Hood R. et al. The Parascope parallel programming environment // Proc. IEEE. —1993. — Vol. 81, N 2. — P. 224-263.

51. Dantzig G., Eaves B. Fourier-Motzkin Elimination and its Dual // Journal of Combinatorial Theory. A. — 1973. — Vol. 14. — P. 288- 297.

52. Eisenbeis C., Sogno J.-C. A general algorithm for data dependence analysis // Proc. of the Sixth ACM International Conference on Supercomputing, Washington, DC. — 1992. — P. 292-302.

53. Eisenbeis C., Temam O., Wijshoff H. On efficiently characterizing solutions of linear Diophantine equations and its application to data dependennce analysis.1992.— (Rep / Utrecht Univ.; RUU-CS-92-01).

54. Faigin K. A., Hoeflinger J. P., Padua D.A., Petersen P. M., Weatherford S. A. The Polaris Internel Representation // February 18, 1994. — P. 1-32. — Available at: http://polaris.cs.uiuc.edu

55. Feautrier P. Dataflow analysis of array and scalar references // Int. J. Parallel Program. — 1991. — V. 20, N 1. — P. 23 52.

56. Fenlason and Stallman, GNU gprof, The GNU Profiler. — Available at: http://www.gnu.org/manual/gprof-2.9. l/htmlchapter/gproftoc.html

57. Goff G., Kennedy K., Tseng C. Practical Dependence Testing // Proc. of the ACM SIGPLAN 91 Conference on Programming Language Design and Implementation, June 1991. — 1991. — P. 15-29.

58. Gupta R., Pande S., Psarrisc K., Sarkar V. Compilation techniques for parallel systems // Parallel Computing.— 1999. —Vol. 25. —P. 1741-1783.

59. Huang T.-C., Yang C.-M. Data dependence analysis for array references // J. Systems and Software. — 2000. — Vol. 52. — P. 55-65.

60. Huang T.-C., Yang C.-M. Data dependence analysis with direction vector for array references // Computers and.Electrical Engineering. — 2001. — Vol. 27.1. P. 375-393.

61. Huang T.-C., Yang C.-M. Non-linear array data dependence test. // J. Systems and Software. — 2001, — Vol. 57. —P. 145-154.

62. Kasyanov V. N., Evstigneev V. A. et al. The system PROGRESS as a tool for paralleling compiler prototyping // proc. Of Eighth SIAM Conf. On Parallel Processing for scientific Computing (PPSC-97) — Minneapolis, 1997.— P. 301-306.

63. Kong X., Klappholz D., Pssaris K. The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization // IEEE Trans, on Parallel and Distributed Systems. — 1991. — Vol. 2(3). — P. 342-349.

64. Kuck D. The structure of computers and computations.,—Vol. 1. — New York-John Wiley and Sons, 1978.

65. Kuck D., Kuhn R., Padua D., Leasure B., Wolfe M. Dependence graphs and compiler optimizations // Proc. 8th ACM Symp. on Princ. Progr. Lang., Williamsburgh, VA„ Jan. 1981. —P. 207-218.

66. Lamport L. The parallel execution of DO loops // Com. ACM. — 1974. — Vol. 17, N2. —P. 83-92.

67. Li Z. Array privatization for parallel execution of loops // Proc. of the 1992 Int. Conf. on Supercomputing, July 1992. — P. 313-322.

68. Li, Z., Yew, P.-C., Zhu, C.-Q. An efficient data dependence analysis for paralleling compilers // IEEE Trans, on Parallel and Distributed Systems. — 1990. — Vol. 1, N 1. — P. 26-34.

69. Lu L., Chen M. Subdomain dependence test for massive parallelism // Proc. of Supercomputing '90, New York, NY. —1990.

70. Maydan D. E. Accurate4 analysis of array references: Thes. PhD (computer sci.). — Computer Systems Lab., Stanford Univ., — 1992.

71. Maydan D. E., Hennessy J. L., Lam M. S. Effectivness of data dependenceanalysis // Proc. of the NSF-NCRD Workshop on Advanced Compilation

72. Techniques for Novel Arch. —1991.

73. Maydan D. E., Hennessy J. L., Lam M. S. Efficient and exact data dependence analysis // ACM SGPLAN'91 Conf. on Progr. Lang. Design and Imp. June 1991. —P. 1-14.

74. McGraw J. R. Parallel functional programming in Sisal: fictions, facts, and future. — Livermore, CA, June 1993. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-JC-114360)

75. Niedzielski D., Psarris K. An Analytical Comparison of the I-Test and Omega Test //Proceedings of the Twelfth International Workshop on Languages and Compilers for Parallel Computing / LNCS 1863. —San Diego, CA: Springer.2000: —P. 251-270.

76. Petersen P. M., Padua D. A. Static and dynamic evaluation of data dependence analysis // Proceedings of the ACM International Conference on

77. Supercomputing. ACM Press, New York, 1993. — P. 107 - 116.

78. Petersen P., Padua D. Experimental*evaluation of some data dependence tests.1991. —(Rep/CSRD; 1080).

79. Pratt V. R. Two easy theories whose combination is hard. —1977. — (Tech. rep./MIT).

80. Psarris K. On exact data dependence analysis // Proc of the Sixth ACM International Conference on Supercomputing, Washington, DC, July 1992. — P. 303-312.

81. Psarris-K. Program analysis techniques for transforming programs for parallel execution // Parallel Computing. — 2002. — Vol. 28. —P. 455-469.

82. Psarris K., Klappholz D., Kong X. On the accuracy of the Banerjee test, shared memory multiprocessors // J. Parallel Distrib. Comput. — 1991. — Vol.12 , N2.—P. 152- 157.

83. Psarris K., Kong X., Klappholz D. The direction vector I test // IEEE Trans, on Parallel and Distributed Systems. — 1993. — Vol. 4, N 11. — P. 1280-1290.

84. Pugh W. The definition of dependence distance. — 1992. — (Tech. Rep. / Univ. Maryland: CS-TR-2992).

85. Pugh W. The Omega test: a fast and practical integer programming algorithm for dependence analysis // Comm. of the ACM. — 1992. — Vol. 35, N 8 . — P. 102-114.

86. Pugh W., Shpeisman T. On Fast Array Data Dependence Tests. — Univ. of Maryland, College Park. — 1999. — Available at: http://citeseer.ist.psu.edu/43683.htm

87. Pugh W., Wonnacott D. An Exact Method for Analysis of Value-based Array Data Dependences // LNCS 768, 1993. — P. 546 566.

88. Pugh W., Wonnacott D. Nonlinear array dependence analysis. — 1994 — ( Tech. Rep / Univ. Maryland; CS-TR-3372).

89. Qiao L., Huang W., Tang Z. Coping with data dependencies of Multidimensional Array References. // NPC 2005, LNCS — 2005. —Vol. 3779. — P. 278-284.

90. Shen Z., Li Z., Yew P.-C. An empirical study of Fortran programs for parallelizing compilers // IEEE Trans, on Parallel and Distributed Systems. — 1992. —Vol. 1,N3. —P. 356-364.

91. Shostak R. Deciding linear inequalities by computing loop residues // ACM Journal. — 1981. — Vol. 28, N 4. — P. 769-779.

92. Towle R.A. Control and data dependence for Program Transformation. Thes. PhD, —1976. — University of Illinois at urbana-Champaign.

93. Triolet R. Interprocedural analysis for program restructuring with PARAFRASE. — 1985. — (Tech. Rep. / CSRD; N538).

94. Wallace D. Dependence of multidimensional array references // Proc. of the Second Intern. Conf. on Supercomputing. St. Malo, France, July — 1988. — P. 418-428

95. Wolfe M. The Tiny Loop Restructuring Research Tool. // Proceedings of the 1991 International Conference on Parallel Processing, St Charles, IL. — August 1991.

96. Wolfe M., Banerjee U. Data dependence and its application to parallel processing // Intern. J. Par. Progr. — 1987. — Vol. 16, N 2. — P. 137-178.

97. Wolfe M., Tseng C. The power test for data dependence // IEEE Trans. Parallel Distrib. Syst. —1992. — V. 3, № 5. — P. 591-601.

98. Wolfe M.J. Optimizing supercompilers for supercomputers: Thes. PhD, —1982. — (Rep. / Univ. 111.,; N UIUCDCS-R-82-1105).

99. Yang C.-T., Tseng S.-S., Shih W.-C. The K Test: an Exact and Efficient Knowledge-based Data Dependence Testing Method for Parallelizing Compilers // Proc. Natl. Sci. Counc. ROC(A). — 2000. — Vol. 24, №. 5. p. 362-372.