Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Арапбаев, Русланбек Нурмаматович

• Арапбаев, Русланбек Нурмаматович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Арапбаев, Русланбек Нурмаматович

ВВЕДЕНИЕ.

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. Проведены экспериментальные исследования для сравнения эффективности предложенных подходов с аналогичными методами анализа зависимостей по данным, выделены наиболее существенные ограничения этих методов.

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Арапбаев, Русланбек Нурмаматович, 2008 год

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.