На правах рукописи
АРАПБАЕВ Русланбек Нурмаматович
АНАЛИЗ ЗАВИСИМОСТЕЙ ПО ДАННЫМ:
ТЕСТЫ НА ЗАВИСИМОСТЬ И СТРАТЕГИИ ТЕСТИРОВАНИЯ
05.13.11 – математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
Новосибирск – 2008
Работа выполнена в Институте систем информатики имени А. П. Ершова СО РАН Научные руководители: Евстигнеев Владимир Анатольевич, доктор физико-математических наук, профессор.
Касьянов Виктор Николаевич, доктор физико-математических наук, профессор.
Официальные оппоненты: Малышкин Виктор Эммануилович доктор технических наук, профессор.
Акжолов Маматжан Жолдошевич кандидат физико-математических наук, доцент.
Ведущая организация: Южный Федеральный Университет (г. Ростов-на-Дону).
Защита состоится 12 декабря 2008 г. в15 ч 30 мин на заседании диссертационного совета К003.032.01 в Институте систем информатики им А.П. Ершова Сибирского отделения РАН по адресу:
630090, г. Новосибирск, пр. Лаврентьева, 6.
С диссертацией можно ознакомится в читальном зале ИСИ СО РАН (пр.
Лаврентьева, 6) Автореферат разослан 8 ноября 2008 г.
Ученый секретарь диссертационного совета К003.032. к.ф.-м.н. Мурзин Ф.А.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Развитие ЭВМ с параллельными архитектурами и высокопроизводительных вычислительных систем ставит перед программистами задачи по созданию новых технологических подходов и их эффективному использованию. В настоящее время успешно развиваются следующие основные направления для решения этой задачи: использование параллельных языков, использование библиотек и автоматическое распараллеливание программ. Первые два пути, несмотря на все их достоинства, оставляют в стороне возможность использования накопленного запаса пакетов прикладных программ, написанных на последовательных языках типа Фортран, а также не облегчают процесс написания параллельных программ. Остается третий путь – создание автоматических распараллеливающих компиляторов, обладающих способностью автоматически преобразовывать последовательную программу в параллельную, функционально эквивалентную, соответствующую заданному типу архитектуры программу.
Однако, разработка эффективных автоматических распараллеливающих компиляторов – это трудоемкий и достаточно длительный процесс. Основная их задача – извлечь как можно больше скрытого параллелизма из последовательной программы. Главным источником такого потенциального параллелизма, как правило, служит гнездо циклов. Извлечение скрытого параллелизма в первую очередь связано с анализом циклов и заключается в нахождении зависимости по данным между итерациями цикла. Таким образом, мощность автоматических распараллеливающих компиляторов весьма зависит от эффективности блока анализа зависимостей по данным.
Тем не менее, прямой подход к решению задачи выявления зависимостей в общем случае невозможен, так как даже для линейных индексных выражений массивов это приводит к NP-полной проблеме отыскания целочисленного решения системы диофантовых уравнений (уравнение зависимости). Один из способов строгого решения этой проблемы был предложен в 1976 г. Тоулем (Towel). Однако метод был слишком трудоемким, чтобы его можно было использовать на практике в распараллеливающих компиляторах. Позднее были разработаны быстрые приближенные методы, которые «ошибочно»
предполагают существование решения уравнения зависимости. Конечно, использование таких некорректных предположений никогда не приводит к ошибочному объектному коду, но может мешать некоторым оптимизациям.
В последние годы интерес к этой тематике снова возрос, и были предложены более эффективные методы, которые получили название тестов на зависимость (data dependence test). Среди них на практике наибольшее распространение получили НОД-тест и тест на основе неравенства Банержи, специально разработанные Утополом Банержи (Banerjee).
Тесты на зависимость используют различные математические инструменты, и каждый из них имеет различную сложность и разрешающую способность. Мощные алгоритмы могут выявлять зависимости по данным с большей точностью, но обычно требуют для этого много времени. Поэтому на практике используется алгоритм зависимости по данным, который состоит из серии тестов, исполняемых в определенном иерархическом порядке. Например, в проекте SUIF1 алгоритм состоит из серии точных тестов, где последним тестом служит метод исключения Фурье-Моцкина. В распараллеливающем компиляторе Parafrase-22 используется стратегия применения НОД-теста и теста Банержи, а в системе ОРС3 применяется тест Банержи-Вольфа, а также поддерживается идея полуавтоматического распараллеливания. Однако до сих пор остается открытым вопрос, какая последовательность или стратегия лучшая.
К настоящему времени разработано множество тестов на зависимость, дающих приближенные и точные решения задачи анализа зависимости по данным, что открывает новые возможности. В связи с этим особую актуальность приобретает выработка новых стратегий тестирования для выявления зависимостей по данным, в которых алгоритм стратегии должен быть эффективным при применении на практике, т.е. выбрать “золотую середину” между точностью и использованием ресурсов.
Поэтому в рамках диссертационной работы была предпринята попытка расширить, обобщить и развить существующие подходы с целью преодоления упомянутых выше ограничений.
Все вышесказанное говорит об актуальности проводимых исследований.
Цель работы. Целью диссертационной работы является разработка новых и улучшение имеющихся алгоритмов для анализа зависимостей по данным при распараллеливании и оптимизации последовательных программ.
Достижение цели связано с решением следующих задач:
Исследование существующих тестов на зависимость и сопоставление их сильных и слабых сторон;
Разработка новых эффективных тестов для анализа зависимостей по данным, в том числе для анализа ссылок многомерных массивов;
Реализация библиотеки тестов на зависимость по данным;
Выработка новой стратегии тестирования для анализа зависимостей по Проведение экспериментов, подтверждающих корректность и эффективность предложенных методов.
Методы исследования. В диссертационной работе использовались различные методы и математические инструменты такие, как: теория графов, теория алгоритмов, элементы теории множеств, теории чисел, методы интервального анализа, методы линейного и целочисленного программирования, теория преобразования и оптимизация программ и др.
Система разработана в Стэндфордском университете под руководством M. Lam Проект разработан в Иллинойском университете под руководством C. Polychronopoulos Открытая распараллеливающая система разрабатывается в Ростовском государственном университете под руководством Б. Я. Штейнберга.
Научная новизна. Проведены исследования, направленные на изучение применимости различных тестов для выявления зависимостей по данным. Даны сопоставления сильных и слабых сторон тестов, как на примерах, так и по оцениваемым характеристикам отдельных критериев.
Предложен модифицированный эффективный тест для решения проблемы зависимости по данным при анализе ссылок многомерных массивов. Новый модифицированный метод, в отличие от известных способов, позволяет получить ответ о существовании целочисленных решений уравнений зависимости при выявлении зависимости по данным в многомерных массивах, содержащих сцепленные индексы.
Реализована библиотека из новых и модифицированных тестов на зависимость по данным, в состав которой вошли приближенные и точные тесты, рассматривающие одномерные и многомерные случаи.
Выработана новая стратегия тестирования, основанная на новых тестах анализа зависимостей по данным. При построении стратегии использованы факты и результаты некоторых эмпирических и теоретических исследований анализа зависимостей по данным, позволившие оптимизировать общее время выполнения алгоритма новой стратегии. На основе новой стратегии и библиотеки тестов на зависимость создан программный комплекс анализа зависимостей по данным, а также построен алгоритм для индексного анализа зависимости по данным в Sisal-программах в рамках системы функционального программирования (SFP).
Проведены экспериментальные работы для сравнения эффективности предложенных подходов с аналогичными методами анализа зависимостей по данным.
Практическая ценность.
неотъемлемой частью системы быстрого прототипирования распараллеливающего компилятора и системы функционального программирования (SFP), разрабатываемых в рамках проекта ПРОГРЕСС.
Результаты могут быть использованы при решении практических задач, а именно при разработке распараллеливающих компиляторов. В частности, разработанные автором диссертации методы могут стать основой для построения алгоритмов выявления зависимости по данным между итерациями DO-циклов в блоке зависимостей в системе быстрого прототипирования распараллеливающего компилятора.
Программно реализованные разработки могут использоваться в качестве инструмента для изучения свойств последовательных программ в процессе написания параллельных программ, а также при проведении обучения студентов методам программирования и оптимизации для параллельных архитектур.
Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах.
1. Международная научная конференция "Параллельные вычислительные технологии" (ПаВТ'2007), Челябинск, Россия, 2007 г.
2. VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Кемерово, 2005.
3. IV Российско-Германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах, Новосибирск, 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 стр. Список литературы содержит наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность проводимых исследований, сформулирована цель диссертационной работы, показана новизна и практическая значимость результатов, указаны положения, выносимые на защиту, и кратко аннотировано содержание глав.
В главе 1 содержится сравнительный обзор существующих тестов на зависимость по данным, применяемых в распараллеливающих компиляторах.
Даны сопоставления сильных и слабых сторон тестов, как на примерах, так и по оцениваемым характеристикам отдельных критериев. Также рассматривается некоторые проблемы анализа зависимостей по данным для многомерных массивов.
В разделе 1.1. описан ряд определений анализа зависимостей по данным, которые требуются в дальнейшем.
Традиционно под зависимостью по данным понимается зависимость, связанная с совпадением ссылок на элементы массивов. Пусть в гнезде r вложенных DO-циклов, операторы S1 и S2 обращаются к d - мерному массиву A индексные выражения которого представлены линейными функциями hq(i1, i2,.
.., i r)и gq(i1, i2,..., i r), где q = 1,..., d. Зависимость по данным между операторами S1 и S2 имеется тогда и только тогда, когда существуют целые i1, i2, Следовательно, проблема зависимости данным представляет собой задачу целочисленного программирования.
Если имеется m-мерный массив А и индексные выражения массива линейны, то тогда система (1) может быть записана в следующем виде:
a11 х1 + a12 х2+…+ a1n хn+c1 = a21 х1 + a22х2+…+ a2n хn+c2 = am1 х1 + am2 х2+…+ amn хn+cm = В разделах 1.2. и 1.3. приводится сравнительный анализ тестов на зависимость. Также приведена обширная классификация тестов на зависимость по использованию различных математических инструментов и по сложности применения их на практике. В частности сначала описываются три основных метода нахождения зависимости по данным: НОД-тест, тест Банержи и метод исключения переменных Фурье-Моцкина. Далее рассматриваются расширенные варианты предыдущих методов, которые делятся на два вида:
приближенные тесты и точные тесты. К приближенным тестам относятся обобщенный НОД-тест, -тест, I-тест и их различные модификации. Точные тесты используют более сложные методы: Power-тест, Омега-тест и IR-тест.
В разделе 1.4. отмечены другие тесты на зависимость, которые в рамках данной диссертационной работе не исследованы. К ним относится CM-тест, использующий симплекс-метод, модифицированный для решения задач целочисленного программирования, алгоритм Шостака, основанный на использовании теоретико-графового метода для решения систем линейных неравенств, и др.
Раздел 1.5. представляет новый модифицированный -тест для анализа ссылок в многомерных массивах. Сравнительный анализ показал, что при анализе зависимостей в цикле ключевой проблемой является работа с многомерными массивами. Общий подход состоит в индивидуальном тестировании уравнений (тестирование “индекс-за-индексом”) из (3) вместо проверки существования решения системы в целом. Однако система уравнений зависимости может не иметь решения даже в том случае, когда имеются решения в каждом из отдельных уравнений.
При анализе многомерных массивов основную трудность вызывают часто встречающиеся в реальных программах сцепленные индексы. Если потенциальная зависимость включает сцепленные индексы, то для её разрушения необходимо одновременное рассмотрение индексов многомерного массива. Один из таких эффективных тестов анализа зависимости в многомерных массивах, включающих сцепленные индексы, является -тест.
Однако -тест определяет, имеет ли система действительные решения, но не может дать точного ответа о существовании целочисленных решений системы.
В предложенном новом модифицированном варианте -теста -тест интегрирован с точным IR-тестом, благодаря чему при анализе зависимостей многомерных массивов были получены более точные результаты. IR-тест находит целочисленные решения уравнения зависимости путем сокращения интервала решений переменных с многократным проецированием. Как только эффективный интервал решений какой-нибудь переменной сжимается к пустому, то делается вывод, что линейное уравнение не имеет целочисленного решения.
Геометрически каждое линейное уравнение системы (3) представляет собой гиперплоскость в пространстве Rn. Пересечение гиперплоскостей S соответствует общим решениям системы уравнений. Границы циклов (4) соответствуют ограниченному выпуклому множеству V в Rn. Если можно найти новую гиперплоскость, которая содержит S, и не имеет целочисленных точек пересечения с V, то это доказывает, что S не имеет целочисленных значений в V, следовательно, зависимости по данным не существует. Данная гиперплоскость является линейной комбинацией уравнений системы.
Теорема 1. SV не имеет целочисленных точек тогда и только тогда, когда существует гиперплоскость, соответствующая линейной комбинации целочисленных точек, где < a i, x > – скалярное произведение a i ( ai1 ai2,…, ain) и x (х1, х2,…хn).
Предложенный алгоритм с помощью -теста генерирует множество линейных комбинаций гиперплоскостей. Затем применяется IR–тест для нахождения гиперплоскости из данного множества, которая не имеет целочисленных точек пересечения с V. Экспериментальные сравнения результатов показали, что модифицированный алгоритм более точен по сравнению с НОД-, Банержи- и -тестами на зависимость. Таким образом, модифицированный -тест является точным тестом для выявления зависимости по данным в многомерных массивах, содержащих сцепленные индексы.
Вторая глава диссертации посвящена подробному описанию новой выработанной стратегии применения тестов для выявления зависимости по данным, в которой алгоритм состоит из серии эффективных и недорогостоящих тестов на зависимость, имеющих линейную и полиномиальную сложность. При выработке стратегии учтены результаты некоторых эмпирических исследований, а также некоторые ограничения аналогичных работ.
В разделе 2.1. рассматриваются существующие стратегии тестирования анализа зависимостей по данным. Приведется теоретическое и практическое описание Дельта-теста, Эпсилон-теста, алгоритма Майдана и К-теста.
Изучаются основные ограничения перечисленных алгоритмов, а также статистические данные существующих эмпирических исследований.
Исследование алгоритмов на зависимость выявило ряд работ в некотором отношении аналогичных представленной диссертационной работе. Во всех исследованиях были представлены наборы тестов на зависимость (библиотека тестов на зависимость), с целью их использования для точного и эффективного решения проблемы в практических ситуациях. Однако наша работа по существу отличается отних.
Дельта–тест разработан для определенных классов ссылок массива, которые часто встречаются в научных программных кодах. Тест сначала классифицирует индексные выражения массивов на следующие категории: ZIV (нулевая индексная переменная), SIV (единственная индексная переменная) и MIV (составная индексная переменная) формы. Соответственно к каждой форме применяются одноименные тесты.
В. Пью (W. Pugh) и Т. Шпейзман (T. Shpeisman) предложили более упрощенный и быстрый вариант Дельта-теста, называемый Эпсилон – тестом.
В этом тесте рассмотрены только самые простые случаи индексных выражений SIV, не используются сцепленные MIV формы и НОД–тест, а также не рассматриваются треугольные границы цикла при использовании теста Банержи. Хотя эти алгоритмы являются самыми быстрыми, но они уступают по точности предложенному в данной диссертационной работе алгоритму.
Алгоритм Майдана который использован в системе SUIF Стенфордского университета, состоит из серии точных тестов, каждый из которых применим в ограниченной области. Последний тест в алгоритме – метод исключения Фурье–Моцкина, расширенный для решения целочисленных задач. Авторы показали, что практически зависимость по данным может быть вычислена точно и эффективно. Главное различие между алгоритмом Майдана и предложенным подходом – в том, что в первом случае добивались требуемого результата с использованием дорогих методов. В противоположность этому, наш подход пытается получить те же результаты с использованием более дешевых тестов на зависимость.
K-тест также состоит из библиотеки тестов на зависимость, но, в отличие от других подходов, вместо конкретной стратеги применения тестов, используются методы искусственного интеллекта. Хотя в самой работе также упоминается о NP-полноте методов искусственного интеллекта.
Раздел 2.2. начинается кратким обзором тестов на зависимость, используемых в предложенной новой стратегии тестирования. Тесты можно классифицировать на одномерные и многомерные. Одномерные тесты: SIVтест, НОД-тест, тест Банержи, I-тест и IR-тест. Многомерные тесты:
-тест, многомерный I-тест,и модифицированный -тест. Идея нашей стратегии опирается на следующие научные факты и результаты.
Основные результаты существующих эмпирических исследований.
Объектом автоматического распараллеливания служат большие пакеты научных прикладных программ, написанных на последовательных языках типа Фортран. Согласно эмпирическому изучению Шена (Shen) и др., в реальных программах индексные выражения не очень сложны. Из всех исследованных массивов примерно 56% составляют ссылки одномерных массивов и 36% – ссылки двухмерных массивов. Доля ссылок трехмерных (и выше) массивов составляет около 8 %. Что касается индексных выражений массивов, то 53 % являются линейными, 13 % – частично линейными и 34 % – нелинейными.
Поэтому обычно для анализа зависимостей по данным на практике применяются только одномерные тесты, использующие подход тестирования “индекс-за-индексом”.
При анализе многомерных массивов основную трудность вызывают часто встречающиеся в реальных программах сцепленные индексы. Как показано в эмпирических исследованиях, более чем в девяти тысячах пар двухмерных ссылок массивов приблизительно 46% являются сцепленными индексными выражениями. Что касается ссылок массивов большей размерности, то только 2% являются сцепленными индексными выражениями. Поэтому на практике важно иметь эффективный тест для обработки сцепленных индексов, особенно для анализа ссылок двухмерных массивов.
«