Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования

Диссертация: Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Тем не менее, прямой подход к решению задачи выявления зависимостей в общем случае невозможен, так как даже для линейных индексных выражений массивов это приводит к МР-полной проблеме отыскания целочисленного решения системы диофантовых уравнений (уравнение зависимости). Один из способов строгого решения этой проблемы был предложен в 1976 г. Тоулем (Towel). Однако метод был слишком трудоемким… Читать ещё >

Содержание

  • 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. Промежуточное представление IR
    • 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−12 050).

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

Диссертационная работа состоит из введения, трех глав и списка литературы. Объем диссертации — 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. В. А., Арапбаев Р. Н., Осмонов Р. А. Анализ зависимостей: основные тесты на зависимость по данным // Сиб. журн. вычисл. математики / РАН, Сиб. отд-е. — Новосибирск, 2007. — Т. 10, № 3. — С. 247−265.
  20. В. А., Касьянов В, Н. Оптимизирующие преобразования в распараллеливающих компиляторах // Программирование, 1996. — № 6.1. С. 12−26.
  21. В. А., Мирзуитова И. А. Анализ циклов: выбор кандидатов на распараллеливание. — Новосибирск, 1999. — 41 с. — (Препр. / РАН, Сиб. отд-е, Ин-т систем информатики. № 58).
  22. В. А., Серебряков В. А. Методы межпроцедурного анализа (обзор) // Программирование. — 1992. — N 3. — С. 4−15.
  23. В. А., Спрогис С. В. Векторизация программ: анализ зависимостей. Б.м., — 1989. — (Препр. / АН СССР, НФ ИТМ и ВТ № 23).
  24. В. Н. Оптимизирующие преобразования программ. — М.: Наука, 1988 г. — 336 с.
  25. В. Н., Евстигнеев В- А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003 г.— 1104 с.
  26. В. Н., Стасенко А. П. Язык программирования Sisal: 3−2-. // Методы и инструменты конструирования* программ / РАН, Сиб. отд-е. Ин-т систем, информатики-—• Новосибирск, 2007. — С. 56−1-34.
  27. С. А. Анализ зависимостей' по данным на базе алгоритма Шостака // Поддержка- супервычислений и Интернет — ориентированные технологии. / РАН, Сиб. отд-е. Ин-т систем информатики. —
  28. Новосибирск, 2001. —С. 31−43.
  29. Малышкин В. Э-. Введение в «параллельное программирование: мультикомпьютеров. Новосибирск, 2003, ИВМ и МГ СО РАН. -—268 с.
  30. К.А. Блок редукции в компиляторе Sisal 3.0. // Методы и инструменты конструирования и оптимизации программ / РАН, Сиб. отд-е. Ин-т систем информатики.— Новосибирск, 2005. — С. 185−196.
  31. А. П- Внутреннее представление системы функционального программирования Sisal 3.0.— Новосибирск, 2004.—54 с. — (Препр. / РАН. Сиб. отд-е. Ин-т систем информатики- № 110).
  32. Шульженко А- М. Преимущества: определения информационных зависимостей в программе с помощью решетчатых графов // XIII Международная конференция „Математика. Экономика. Образование.“. Тезисы докладов. — Ростов н/Д, 2005.—.С. 195.
  33. Allen J. R. Dependence analysis for subscripted variables and its application to program transformations: PhD Thes. (computer sci.) — Rice Univ., 1983.
  34. Allen J. R., Kennedy K. Automatic translation of Fortran programs to vector form // ACM Trans. Program Lang. Syst. — 1987. — Vol. 9, N 4. — P. 491 542.
  35. Banerjee U. An introduction to a formal theory of dependence analysis // The J. of Supercomputing. — 1988. — Vol.2. — P. 133−149.
  36. Banerjee U. Data dependence in ordinary programs. — Urbana, 1976. — (Tech. Rep. / Univ. III- 76−837).
  37. Banerjee U. Dependence Analysis. Boston, Mass.: Kluwer Academic Publishers. — 1997. — P. 106.
  38. Banerjee U. Speedup of ordinary programs. PhD diss. Univ. 111., Rpt N UIUCDCS-R-79−989, 1979.
  39. Bernstein A. J. Analysis of Programs for Parallel Processing // IEEE Trans. Electronic Computers. — 1966. — Vol. 15, N 5. — P. 757−763. .
  40. Berry M. et al. The PERFECT Club benchmarks: effective performance evaluation of supercomputers. —1989. — 48 p. — (Tech. Rep. / UIUCSRD- N 827).
  41. 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.
  42. 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.
  43. Burke M., Cytron R. Interprocedural dependence analysis and parallelization. — 1986 (Res. Rep / IBM- RC-11 794).
  44. Chang W.-L., Chu C.-P. The 1+ test // LNCS — 1999. — vol. 1656.— P. 367 381.
  45. 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.
  46. 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.
  47. Chang W.-L., Chu, C.-P., Wu, J. A multi-dimensional version of the I test // Parallel Computing. — 2001. — Vol. 27. — P. 1783−1799.
  48. 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.
  49. Cooper K., Hall M., Hood R. et al. The Parascope parallel programming environment // Proc. IEEE. —1993. — Vol. 81, N 2. — P. 224−263.
  50. Dantzig G., Eaves B. Fourier-Motzkin Elimination and its Dual // Journal of Combinatorial Theory. A. — 1973. — Vol. 14. — P. 288- 297.
  51. 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.
  52. 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).
  53. 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
  54. Feautrier P. Dataflow analysis of array and scalar references // Int. J. Parallel Program. — 1991. — V. 20, N 1. — P. 23 52.
  55. Fenlason and Stallman, GNU gprof, The GNU Profiler. — Available at: http://www.gnu.org/manual/gprof-2.9. l/htmlchapter/gproftoc.html
  56. 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.
  57. Gupta R., Pande S., Psarrisc K., Sarkar V. Compilation techniques for parallel systems // Parallel Computing.— 1999. —Vol. 25. —P. 1741−1783.
  58. Huang T.-C., Yang C.-M. Data dependence analysis for array references // J. Systems and Software. — 2000. — Vol. 52. — P. 55−65.
  59. 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.
  60. Huang T.-C., Yang C.-M. Non-linear array data dependence test. // J. Systems and Software. — 2001, — Vol. 57. —P. 145−154.
  61. 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.
  62. 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.
  63. Kuck D. The structure of computers and computations.,—Vol. 1. — New York-John Wiley and Sons, 1978.
  64. 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.
  65. Lamport L. The parallel execution of DO loops // Com. ACM. — 1974. — Vol. 17, N2. —P. 83−92.
  66. Li Z. Array privatization for parallel execution of loops // Proc. of the 1992 Int. Conf. on Supercomputing, July 1992. — P. 313−322.
  67. 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.
  68. Lu L., Chen M. Subdomain dependence test for massive parallelism // Proc. of Supercomputing '90, New York, NY. —1990.
  69. Maydan D. E. Accurate4 analysis of array references: Thes. PhD (computer sci.). — Computer Systems Lab., Stanford Univ., — 1992.
  70. Maydan D. E., Hennessy J. L., Lam M. S. Effectivness of data dependenceanalysis // Proc. of the NSF-NCRD Workshop on Advanced Compilation
  71. Techniques for Novel Arch. —1991.
  72. 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.
  73. McGraw J. R. Parallel functional programming in Sisal: fictions, facts, and future. — Livermore, CA, June 1993. — (Tech. Rep. / Lawrence Livermore National Laboratory- UCRL-JC-114 360)
  74. 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.
  75. Petersen P. M., Padua D. A. Static and dynamic evaluation of data dependence analysis // Proceedings of the ACM International Conference on
  76. Supercomputing. ACM Press, New York, 1993. — P. 107 — 116.
  77. Petersen P., Padua D. Experimental*evaluation of some data dependence tests.1991. —(Rep/CSRD- 1080).
  78. Pratt V. R. Two easy theories whose combination is hard. —1977. — (Tech. rep./MIT).
  79. Psarris K. On exact data dependence analysis // Proc of the Sixth ACM International Conference on Supercomputing, Washington, DC, July 1992. — P. 303−312.
  80. Psarris-K. Program analysis techniques for transforming programs for parallel execution // Parallel Computing. — 2002. — Vol. 28. —P. 455−469.
  81. 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.
  82. 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.
  83. Pugh W. The definition of dependence distance. — 1992. — (Tech. Rep. / Univ. Maryland: CS-TR-2992).
  84. 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.
  85. Pugh W., Shpeisman T. On Fast Array Data Dependence Tests. — Univ. of Maryland, College Park. — 1999. — Available at: http://citeseer.ist.psu.edu/43 683.htm
  86. Pugh W., Wonnacott D. An Exact Method for Analysis of Value-based Array Data Dependences // LNCS 768, 1993. — P. 546 566.
  87. Pugh W., Wonnacott D. Nonlinear array dependence analysis. — 1994 — (Tech. Rep / Univ. Maryland- CS-TR-3372).
  88. Qiao L., Huang W., Tang Z. Coping with data dependencies of Multidimensional Array References. // NPC 2005, LNCS — 2005. —Vol. 3779. — P. 278−284.
  89. 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.
  90. Shostak R. Deciding linear inequalities by computing loop residues // ACM Journal. — 1981. — Vol. 28, N 4. — P. 769−779.
  91. Towle R.A. Control and data dependence for Program Transformation. Thes. PhD, —1976. — University of Illinois at urbana-Champaign.
  92. Triolet R. Interprocedural analysis for program restructuring with PARAFRASE. — 1985. — (Tech. Rep. / CSRD- N538).
  93. Wallace D. Dependence of multidimensional array references // Proc. of the Second Intern. Conf. on Supercomputing. St. Malo, France, July — 1988. — P. 418−428
  94. Wolfe M. The Tiny Loop Restructuring Research Tool. // Proceedings of the 1991 International Conference on Parallel Processing, St Charles, IL. — August 1991.
  95. Wolfe M., Banerjee U. Data dependence and its application to parallel processing // Intern. J. Par. Progr. — 1987. — Vol. 16, N 2. — P. 137−178.
  96. Wolfe M., Tseng C. The power test for data dependence // IEEE Trans. Parallel Distrib. Syst. —1992. — V. 3, № 5. — P. 591−601.
  97. Wolfe M.J. Optimizing supercompilers for supercomputers: Thes. PhD, —1982. — (Rep. / Univ. 111., — N UIUCDCS-R-82−1105).
  98. 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.
Заполнить форму текущей работой

На отлично!