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

• Полуян, Степан Вячеславович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Полуян, Степан Вячеславович

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПСЕВДОНИМОВ.

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

1.2. Алгоритм анализа псевдонимов системы ДВОР и его реализация.

1.2.1. Описание программной реализации анализатора псевдонимов в ДВОР.

1.2.2. Алгоритм анализа целей указателей при анализе псевдонимов в ДВОР.

1.2.2.1. Представление значений указателей.

1.2.2.2. Внутрипроцедурная часть анализа целей указателей.

1.2.2.3. Межпроцедурная часть анализа целей указателей.

1.2.2.4. Анализатор выражений для анализа целей указателей.

1.2.2.5. Учет состояний программы.

1.2.2.6. Результат анализа целей указателей.

1.2.3. Алгоритм анализа типов переменных при анализе псевдонимов в ДВОР.

1.2.3.1. Представление типов данных.

1.2.3.2. Определение псевдонимов на основе информации о типе.

1.3. Применение анализа псевдонимов в ДВОР.

1.3.1. Уточнение информационных зависимостей.

1.3.2. Уточнение потока данных.

1.4. Оценка точности и эффективности анализатора псевдонимов.

1.5. Выводы к первой главе.

ГЛАВА 2. СТАТИЧЕСКОЕ ПРОФИЛИРОВАНИЕ.

2.1. Обзор методов профилирования.

2.2. Алгоритм статического профилирования системы ДВОР и его реализация.

2.2.1. Описание программной реализации профилировщика в ДВОР.

2.2.2. Задание весов операций в ДВОР.

2.2.3. Внутрипроцедурная часть алгоритма профилирования в ДВОР.

2.2.3.1. Вычисление времени выполнения оператора-выражения.

2.2.3.2. Вычисление времени выполнения блока операторов.

2.2.3.3. Вычисление времени выполнения операторов ветвления.

2.2.3.4. Вычисление времени выполнения операторов циклов.

2.2.3.5. Алгоритм выделения горячих точек.

2.2.3.6. Типизация операций.

2.2.4. Межпроцедурная часть алгоритма профилирования в ДВОР.

2.2.4.1. Типы времени выполнения подпрограмм.

2.2.4.2. Алгоритм обхода графа вызовов.

2.2.4.3. Вычисление времени выполнения подпрограмм.

2.2.5. Метод получения горячих точек в ДВОР.

2.2.6. Диалоговый режим профилирования в ДВОР.

2.3. Сравнение результатов профилирования .'.

2.4. Выводы ко второй главе.

ГЛАВА 3. АНАЛИЗ РАЗМЕЩЕНИЯ ДАННЫХ НА ЭТАПЕ КОМПИЛЯЦИИ.

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

3.2. Исследование целесообразности анализа размещения данных.

3.3. Модель рассматриваемых программ.

3.4. Алгоритм анализа обращений программы к памяти в ДВОР и его реализация.

3.5. Алгоритм анализа размещения данных в общей памяти с минимизацией кэш-промахов системы ДВОР и его реализация.

3.5.1. Об особенностях работы кэш-памяти.

3.5.2. Условие оптимального размещения массивов с учетом особенностей кэша.

3.5.3. Алгоритм вычисления количества заполнений кэш-линеек в ДВОР.

3.5.4. Описание программной реализации в системе ДВОР анализатора размещения данных в общей памяти.

3.6. Алгоритм анализа размещения данных в распределенной памяти с минимизацией количества межпроцессорных пересылок системы ДВОР и его реализация.

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

3.6.2. Условие оптимального размещения массивов в распределенной памяти.

3.6.3. Алгоритм подсчета количества межпроцессорных пересылок в ДВОР.

3.6.4. Описание программной реализации в системе ДВОР анализатора размещения данных в распределенной памяти.

3.7. Алгоритм уменьшения количества переборов вариантов размещений массивов в системе ДВОР.

3.8. Оценка корректности и эффективности анализа размещения данных в ДВОР.

3.9. Выводы к третьей главе.

Введение диссертации (часть автореферата) на тему «Анализ обращений программы к памяти в оптимизирующей распараллеливающей системе»

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

Повышение производительности может достигаться двумя путями. Во-первых, за счет усложнения вычислительных архитектур [32]. Во-вторых, за счет оптимизации программного обеспечения [29]. Ручная оптимизация программ является достаточно дорогостоящим процессом, так как она обуславливает повышенные требования к квалификации программистов. Ввиду этого, особый интерес представляют оптимизирующие и распараллеливающие компиляторы [74], позволяющие автоматизировать этот процесс [24].

Среди наиболее известных оптимизирующих и распараллеливающих компиляторов можно назвать GNU Compiler Collection (GCC) [92], SUIF Compiler [75] и Intel С++ Compiler [99]. В отечественной науке наиболее заметными в этой области являются система V-Ray [133], система ПРОГРЕСС [103], DVM-система [10], Т-система [1], среда Par Java [17], языки mpC [101] и НОРМА [6], системы ОРС [41] и ДВОР [66].

По мере увеличения производительности вычислительных систем все острее проявляет себя проблема под названием "стена памяти" (memory wall) [20], которая заключается в отставании скорости подготовки данных от скорости их обработки. Причем это отставание имеет тенденцию к постоянному увеличению. Так, по данным, приведенным в работе [33] В.В. Корнеева «тактовая частота процессоров растёт с темпом 40%, а быстродействие схем динамической памяти только 9% в год». В итоге, для ряда программ, активно обращающихся к памяти, увеличение быстродействия процессора практически не приводит к уменьшению времени работы этих программ.

Описанная выше проблема несколько меняет акценты в оптимизации программ, что можно видеть на примере оценки целесообразности использования алгоритма Штрассена [64]. По этой же причине сейчас происходит пересмотр критериев оценки производительности вычислительных систем и ведется создание новых тестов, таких как тест нерегулярного доступа к памяти (random access) [16], на основе которого строится новый альтернативный Тор500 [131] рейтинг производительности вычислительных систем Graph500 [93].

Описанные выше причины вынуждают развивать методы [8, §11], улучшающие размещение данных в программе, в системах оптимизации и распараллеливания программ. На сегодняшний день разработано достаточно много теоретических методов размещения данных в общей [107] и распределенной [38] памяти, однако они не имеют связи с исполняемым кодом. Таким образом, для того чтобы использовать существующие теоретические достижения в распараллеливающих и оптимизирующих компиляторах требуется создание специальных анализаторов, позволяющих корректно и эффективно вычислять наилучшее размещение данных на этапе компиляции, что и определяет актуальность темы диссертации.

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

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

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

• Разработка и реализация анализа псевдонимов для корректного определения обращений программы к памяти (раздел 1.2);

• Разработка и реализация статического профилирования для ускорения выбора наилучшего размещения данных (раздел 2.2);

• Разработка и реализация анализа размещения данных в общей памяти с минимизацией кэш-промахов (раздел 3.5);

• Разработка и реализация анализа размещения данных в распределенной памяти с минимизацией количества пересылок данных (раздел 3.6).

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

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

• Новый алгоритм анализа псевдонимов, который в отличие от известных позволяет провести его на высокоуровневом внутреннем представлении и получить результат в виде, пригодном для уточнения информационных зависимостей;

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

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

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

• Анализатор псевдонимов, который позволяет получить информацию о псевдонимах переменных для высокоуровневого внутреннего представления и использовать его результаты как в анализе потоков данных [8, §9.2], так и в анализе информационных зависимостей [137];

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

• Анализатор размещения данных в системах с общей памятью, который позволяет вычислить такое размещение данных, при котором количество кэш-промахов будет минимальным;

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

Основные положения, выносимые на защиту:

1. Алгоритмы и программная реализация анализа псевдонимов для высокоуровневого внутреннего представления;

2. Алгоритмы и программная реализация статического профилирования с диалоговым режимом работы;

3. Алгоритм и программная реализация анализа размещения данных в общей памяти с минимизацией кэш-промахов;

4. Алгоритм и программная реализация анализа размещения данных в распределенной памяти с минимизацией количества межпроцессорных пересылок в многопроцессорных вычислительных системах.

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

Внедрение результатов работы. Данная работа проводится в рамках проекта «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения» (ДВОР) [21], который предназначен для оптимизации и распараллеливания программ, написанных на процедурных языках программирования. Кроме того, части данной работы используются в проектах «Тренажер параллельного программиста» [71] и «Анализатор распараллели-ваемости циклов» [4]. В процессе работы получено свидетельство о государственной регистрации программ для ЭВМ: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ» (свидетельство №2011617205). Также полученные в данной работе результаты могут использоваться в учебном процессе для изучения свойств программ, связанных с размещением данных в общей и распределенной памяти.

Часть исследований диссертации поддерживалась грантами:

• Внутренний грант Южного федерального университета «Учебно-научная лаборатория оптимизации и распараллеливания программ», 2007 г;

• ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по теме: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения». Государственный контракт № 02.740.11.0208 от 7 июля 2009 г;

• Грант РФФИ на участие во Всероссийской конференции молодых ученых "Теория и практика параллельного программирования" от 16 июня 2010 г;

• ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по теме: «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК». Государственный контракт № 14.740.11.0006 от 1 сентября 2010 г.

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

• Всероссийская суперкомпьютерная конференция «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность», Новороссийск, 21-26 сентября 2009 г;

• Всероссийская конференция молодых ученых «Теория и практика параллельного программирования», Новороссийск, 20-25 сентября 2010 г;

• XVIII Всероссийская научно-методическая конференция Телематика'2011, Санкт-Петербург, 20-23 июня 2011 г.

Международные конференции:

• THE 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2009), Moscow, Russia, September 18-21, 2009;

• Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи», Новороссийск, 20-25 сентября 2010 г;

• V Международная конференция «Параллельные вычисления и задачи управления» (РАСО'2010), ИЛУ РАН, Москва, 26-28 октября 2010 г.

Кроме того, результаты работы многократно докладывались на семинаре «Автоматическое распараллеливание программ» мехмата Южного федерального университета.

Публикации. По результатам выполненных исследований опубликовано 12 печатных работ. Из них 2 статьи в журналах перечня ВАК: «Информационные технологии» [52] и «Известия высших учебных заведений. СевероКавказский регион. Естественные науки» [48], 1 монография [51], 1 статья в научном сборнике [45], 6 статей в сборниках трудов конференций [47], [49], [50], [66], [68] и [126], 1 тезисы доклада [46] и 1 свидетельство [69].

Личный вклад. Постановка задачи о выборе оптимального размещения данных принадлежит научному руководителю. Все результаты диссертации получены автором лично. Большинство научных публикаций по теме диссертации выполнены без соавторов. Программная реализация анализатора псевдонимов, профилировщика, анализатора размещения данных в общей памяти с минимизацией кэш-промахов, анализатора размещения данных в распределенной памяти с минимизацией межпроцессорных пересылок выполнены автором лично в рамках проекта ДВОР [21] с использованием подпроектов "внутреннее представление", "граф потока управления", "граф вызовов" и "графический интерфейс" других разработчиков.

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

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы (139 наименований) и одного приложения. Содержит 147. страниц текста, включая 50 рисунков и 13 таблиц.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Полуян, Степан Вячеславович

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

• Разработан и реализован в ДВОР алгоритм анализа псевдонимов, необходимый для корректного проведения размещения данных и позволяющий использовать его результаты как для уточнения потока данных, так и для уточнения информационных зависимостей;

• Разработан и реализован в ДВОР алгоритм статического профилирования, необходимый для ускорения выбора наилучшего размещения данных и позволяющий расширить возможности статического анализа посредством диалогового режима;

• Разработан и реализован в ДВОР алгоритм выбора способа размещения данных в общей памяти с минимизацией кэш-промахов, который позволяет сократить количество вариантов размещений при выборе наилучшего размещения данных;

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Полуян, Степан Вячеславович, 2011 год

1. Абрамов С., Адамович А., Коваленко М. Т-система: среда программирования с поддержкой автоматического динамического распараллеливания на платформе «IP-сеть UNIX-компьютеров». URL: www.botik.ru/abram/ts-pabs.html.

2. Александреску A. Современное проектирование на С++. Серия С++ In-Depth, т. 3. M.: Издательский дом "Вильяме", 2002. - 336 с.

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

4. Анализатор распараллеливаемое™ циклов (OPS Web Tool). URL: http://195.208.237.175/opsweb.php.

5. Антонов A.C. Параллельное программирование с использованием технологии MPI. M.: Изд-во МГУ, 2004 г., 71 с.

6. Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н. НОРМА специализированная система параллельного программирования. В сб. Сибирская школа-семинар по параллельному программированию, Томск: Изд-во Томского университета, 2002. С.33-45.

7. Арапбаев Р.Н. Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования: дис. . кандидата физико-математических наук, Новосибирск, ИСИ СО РАН, 2008. 116 с.

8. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструментарий, 2-е изд.: Пер. с англ. М.: ООО «И.Д. Вильяме», 2008. - 1184 с.

9. Бабичев A.B., Лебедев В.Г. Распараллеливание программных циклов // Программирование. 1983, № 5, С. 52-63.

10. Векторизация программ. // Векторизация программ: теория, методы, реализация. Сборник переводов статей М.: Мир, 1991. С. 246 267.

11. Воеводин В.В. Математические основы параллельных вычислений, М., МГУ, 1991.-345 с.

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

13. Воеводин Вл. В. Статистические оценки возможности выявления параллельной структуры последовательных программ // Программирование, № 4, 1990. С. 44-54.

14. Воеводин В л. В. Теория и практика исследования параллелизма последовательных программ. // Программирование, № 3, 1992. С. 38-54.

15. Волков Д., Фролов А. Оценка быстродействия нерегулярного доступа к памяти // Открытые системы. СУБД, 2008, №01. С. 15-19.

16. Гайсарян С.С., Аветисян А.И., Падарян В.А., Леонтьев Г. Применение среды ParJava для разработки параллельных программ. // Труды международной научной конференции «Суперкомпьютерные системы и их применение» (SSA,2004). Минск, 2004. С. 99-104.

17. Гайсарян С.С., Чернов A.B., Белеванцев A.A., Маликов О.Р., Мельник Д.М., Меньшикова A.B. О некоторых задачах анализа и трансформации программ. Труды Института системного программирования РАН. Том 5, 2004. С. 7-40.

18. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. - 184 с.

19. Горбунов В., Эйсымонт Л. Экзафлопсный барьер: проблемы и решения // Открытые системы. Платформы, 2010, №05. С. 10-13.

20. Диалоговый высокоуровневый оптимизирующий распараллеливатель программ (ДВОР). URL: http://www.ops.rsu.ru.

21. Дроздов А.Ю, Владиславлев В.Е. Межпроцедурный анализ указателей // Информационные технологии. Приложение № 2. 2005.

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

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

24. Евстигнеев В.А., Мирзуитова И.А. Анализ циклов: выбор кандидатов на распараллеливание. Препринт № 58, ИСИ РАН, Новосибирск, 1999. 41 с.

25. Идрисов Р.И. Межпроцедурный анализ и распараллеливание потоковых программ на базе графа исполнений вызовов: дис . кандидата физико-математических наук, Новосибирск, ИСИ СО РАН, 2010.- 148 с.

26. Ильин В.А., Позняк Э.Г. Линейная алгебра. М.: Наука, 1974. - 331с.

27. Ицыксон В.М., Моисеев М.Ю., Ахин М.Х., Захаров A.B., Цесько В.А. Алгоритмы анализа указателей для обнаружения дефектов в исходном коде программ // Системное программирование. № 4. 2009. С. 5-30.

28. Касперский К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ-Петербург, 2003. - 456 с.

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

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

31. Корнеев В.В. Параллельные вычислительные системы. М., «Нолидж», 1999.-311 с.

32. Полуян C.B. Автоматическое размещение массивов в распределенной памяти с минимизацией количества пересылок // Труды научной школы И.Б. Симоненко, отв. ред.: Я.М. Ерусалимский, Б.Я. Штейнберг. Ростов н/Д: Изд-во ЮФУ, 2010 г. С. 214-219.

33. Полуян С.В. Анализ обращений программы к памяти в оптимизирующей распараллеливающей системе // Труды XVIII Всероссийской научно-методической конференции Телематика'2011. Том 2 СПб.: СПбГУ ИТ-МО, 2011.-С. 328-329.

34. Полуян С.В. Анализ указателей для распараллеливания // Параллельные вычисления и задачи управления (РАСО'2010): Труды V Международной конференции, ИПУ РАН, г. Москва, 26-28 октября 2010 г. С. 1065-1069.

35. Полуян С.В. Выбор оптимального размещения многомерных массивов в памяти компьютера // Известия вузов. Северо-Кавказский регион. Серия: Естественные науки, 2010, №3. С. 15-18.

36. Полуян С.В. Статический анализ высокоуровневых программ. -Saarbrücken: Lambert Academic Publishing, 2011. 154 е.: ил. - ISBN 978-38454-4150-4.

37. Полуян С.В. Уточнение графа информационных связей с помощью анализа псевдонимов // Информационные технологии, 2011, №4. С. 36-40.

38. Прангишвили И.В., Виленкин С .Я., Медведев И.Л., Параллельные вычислительные системы с общим управлением // М.: Энергоатомиздат, 1983. -312 с.

39. Свами М., Тхуласираман К. Графы, сети, алгоритмы. М.: Мир, 1984. -454 с.

40. Себеста Р. Основные концепции языков программирования, 5-е изд.: Пер. с англ. — М.: Вильяме, 2001. — 672 с.

41. Семенов А., Фролов А., Эйсымонт Л. Graph500: адекватный рейтинг // Открытые системы. СУБД, 2011, №01. С. 14-17.

42. Система документирования исходных кодов Doxygen (www.doxygen.org).

43. Фельдман Л.П. Параллельные алгоритмы численного решения систем линейных обыкновенных дифференциальных уравнений // Математическое моделирование. 2000, Т. 12, № 6. С. 15-20.

44. Фролов А. В. Оптимизация размещения массивов в ФОРТРАН-программах на многопроцессорных вычислительных системах // Программирование, 1998, № 3,-С. 70-80.

45. Хандхаузен Р. Знакомство с Microsoft Visual Studio 2005 Team System. Пер. с англ. -М.: Издательство «Русская редакция»; СПб.: Питер, 2006. 416 с.

46. Чернов А.В. Анализ запутывающих преобразований программ. Сб. Труды Института системного программирования, под. ред. В. П. Иванникова. М.: ИСП РАН, 2002.

47. Штейнберг Б.Я. Бесконфликтные размещения массивов при параллельных вычислениях // Кибернетика и системный анализ, 1999, № 1. С. 166-178.

48. Штейнберг Б.Я. Оптимизация размещения данных в параллельной памяти, Изд-во Южного федерального ун-та, 2010. 256 с.

49. Штейнберг Б.Я. Распараллеливание программ для суперкомпьютеров с параллельной памятью и открытая распараллеливающая система: дис. . д-ра техн. наук. Ростов н/Д, 2004. 343 с.

50. Шульженко A.M. Исследование информационных зависимостей программ для распараллеливающих преобразований: дис. . канд. техн. наук. Ростов н/Д, 2006. 202 с.

51. Электронное обучающее средство «Тренажер параллельного программиста» (ТПП) 2007 г. URL: http://www.ops.rsu.ru.

52. Этов В.И. Быстрый онлайновый анализ указателей // Автоматика и вычислительная техника. №3. 2008. С 219-219.

53. Якобовский М.В. Распределенные вычисления. М.: Наука, 2003. - 340 с.

54. Allen R., Kennedy К. Optimizing compilers for Mordern Architetures. Morgan Kaufmann Publisher, Academic Press, USA, 2002. 790 p.

55. Amarasinghe S.P., Anderson J.M., Lam M.S., Tseng C.W. The SUIF Compiler for Scalable Parallel Machines // In Proceedings of the seventh SIAM Conference on Parallel Processing for Scientific Computing, Feb. 1995.

56. AMD CodeAnalyst Performance Analyzer. URL: http://developer.amd.com/.

57. Andersen L.O. Program Analysis and Specialization for the С Programming Language. Ph.D thesis. DIKU, University of Copenhagen. 1994. 311 p.

58. Appel A., Ginsburg M. Modern Compiler Implementation in C. Cambridge University Press. 1998. 544 p.

59. AQtime Pro. URL: http://www.automatedqa.ru/products/aqtime/.

60. Berndl M., Lhotak O. Points-to analysis using BDDs // Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003. P. 103-114.

61. Beyls K., D'Hollander E.H. Refactoring for Data Locality // IEEE Computer, vol. 42, №2, 2009. P. 62-71.

62. Bodin F., Beckman P., Gannon D., Yang S., Kesavan S., Malony A., Mohr В. Implementing a Parallel С++ Runtime System for Scalable Parallel Systems // In Proceedings of Supercomputing '93, November 1993. P. 588-597.

63. Chapman B.M., Mehrotra P., Zima H.P. User Defined Mappings in Vienna Fortran // In SIGPLAN'92 Workshop on Languages, Compilers, and Run-Time Environments for Distributed Memory Multiprocessors, Boulder, Colorado, 1992. P. 72-75.

64. Cooper K. D., Hall M. W., Kennedy K., Torczon L. Interprocedural Analysis and Optimization // Communications in Pure and Applied Mathematics, 1995. P. 947-1003.

65. Cooper K.D., Torcson L. Engineering a Compiler. 2nd ed. Morgan Kaufmann Publishers, Elsevier Inc. 2011. - 824 p.

66. DevPartner Studio. URL: http://www.microfocus.com.

67. Diwan A., McKinley K., Moss E. Type-based alias analysis // Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, Montreal, Quebec, Canada, June 17-19, 1998. P.106-117.

68. Embarcadero RAD Studio. URL: http://www.embarcadero.com.

69. Emami M., Ghiya R., Hendren L. J. Context-sensitive interprocedural points-to analysis in the presence of function pointers // In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, June 1994. P. 242-256.

70. Feautrier P. Data Flow Analysis for Array and Scalar References // International Journal of Parallel Programming. V. 20, № 1, Feb. 1991. P. 23-53.

71. Frumkin M.A., Shabanov L.V. Benchmarking Memory Performance with the Data Cube Operator // Proceedings of ISCA 17th International Conference Parallel and Distributed Computing Systems, September 2004. P 165-171.

72. GNU Compiler Collection (GCC). URL: http://gcc.gnu.org.

73. Graph500. URL: http://www.graph500.org.

74. Gross A. Evaluation of dynamic points-to analysis, 2004. URL: http://www.complang.tuwien.ac.at/franz/sem-arbeiten/04w/semWS04gross 0026934.pdf.

75. Hamel L., Hatcher P., Quinn M. An Optimizing C* Compiler for a Hypercube Multicomputer. In Languages, Compilers, and Run-Time Environments for Distributed Memory Machines, Elsevier Science Publishers, 1992. P. 285-298.

76. Handy J. The Cache Memory Book. 2nd ed. Academic Press, 1998. - 229 p.

77. Hecht M. Flow Analysis of Computer Programs. Elsevier North-Holland, New York, 1 edition, 1977. 246 p.

78. IBM Rational Software Analyzer. URL: www.ibm.com/software/rational.

79. Intel C++ Compiler. URL: http://software.intel.com/ru-ru/intel-compilers/.

80. Intel VTune Amplifier XE. URL: http://software.intel.com/en-us/articles/intel-vtune-amplifier-xe/.

81. Kalinov A., and Klimov S. Optimal mapping of a parallel application processes onto heterogeneous platform // Proceedings of 19th International Parallel and Distributed Processing Symposium, Denver, USA, April 2005, IEEE CS.

82. Kant K. Introduction to Computer System Performance Evaluation. Mc Graw-Hill Inc. 1992.-640 p.

83. Kasyanov V. N., Evstigneev V. A. 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.

84. Kuck D.J., Kuhn R.H., Leasure B., Wolfe M. Depedance graph and compiler optimizations // Proc. 8-th ACM Symp. On Principles of Progr. Lang. Williamsburg, 26-28 Jan. 1981. P. 207-218.

85. Kulkurni D., Stumm M. Loop and Data Transformations: A Tutorial. Technical Report CSRI 337, Computer Systems Research Institute, June 1993. 53 p.

86. Lam M. S., Whaley J. Context-sensitive program analysis as database queries // Proc. ACM Symposium on Principles of Database Systems, 2005. P. 1-12.

87. Lim A.W., Lam M.S. Cache Optimizations With Affine Partitioning // In Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, Virginia. 14 p.

88. Lim A.W., Lam M.S. Maximizing Parallelism and Minimizing Synchronization with Affine Partitions // Parallel Computing, 24, 1998. P. 445-475.

89. McAffer J., Lemieux J., Aniszczyk C. Eclipse Rich Client Platform. 2nd ed. Addison-Wesley Professional. 2010. - 552 p.

90. Metz E., Lencevicius R. Efficient Instrumentation for Performance Profiling // Proceedings of the ICSE Workshop on Dynamic Analysis, 2003. P. 143-148.

91. Mitchell M. Type-based alias analysis // Dr. Dobb's Journal: Software Tools for the Professional Programmer, 2000, №10. P. 54-58.

92. Muchnick S. Advanced compiler design and implementation. Morgan Kaufmann, 3rd ed., 1997.-887 p.

93. Murphy B.R., Lam M.S. Program analysis with partial transfer functions // In: Proc. of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New York, NY, USA, 2000. P. 94-103.

94. Pugh W. The Omega Test: a fast and practical integer programming algorithm for dependence analysis // Comm. Of the ACM, August, 1992. P. 102-114.

95. Paek Y. Compiling for Distributed Memory Multiprocessors Based on Access Region Analysis. Thesis Ph/D in Computer Science, University of Illinois at Ur-bana-Champaign, 1997. http://polaris.cs.uiuc.edu.

96. Randolph N. Professional Visual Studio 2010. Wrox. 2010. 1224 p.

97. Richardson H. High Performance Fortran: history, overview and current developments. Tech. Rep. TMC-261, Thinking Machines Corporation, 1996.

98. Richter J. Applied Microsoft .NET Framework Programming. Microsoft Press. 2002. 640 p.

99. Rinetzky N., Ramalingam G., Sagiv S., Yahav E. On the complexity of partially-flow-sensitive alias analysis. ACM Transactions on Programming Languages and Systems, 2008. 28 p.

100. Ruf Erik. Context-insensitive alias analysis reconsidered // In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, June 1995. P. 13-31.

101. Sade Y., Sagiv M., Shaham R. Optimizing C multithreaded memory management using thread-local storage // In Compiler Construction. 2005. P. 137-155.

102. SHMEM Programming Manual: staff.psc.edu/oneal/compaq/ShmemMan.pdf

103. Standard Performance ^ Evaluation Corporation (SPEC). URL: h ttp:// ww w. spec. org/ben chm arks. html.

104. Steensgaard B. Points-to analysis in almost linear time // Proc. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1996. P. 32-41.

105. Sunderam V.S. PVM: A Framework for Parallel Distributed Computing, Concurrency: Practice and Experience, 1990. P. 315-339.

106. Thinking Machines Corporation, Cambridge, Massachusetts. CM Fortran Reference Manual, Version 1.0, February 1991.

107. Treleaven P.C. Parallel architecture overview // Parallel Computing, North-Holland, 1988. P. 59-70.

108. Tok T. B., Guyer S. Z., Lin C. Efficient flow-sensitive interprocedural data-flow analysis in the presence of pointers // In 15th International Conference on Compiler Construction (CC), 2006. P. 17-31.

109. Top500. URL: http://www.top500.org.

110. Triolet R., Irigoin F., Feautrier P. Direct Parallelization of CALL Statements // In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, Palo Alto, California, June 1986". P. 176-185.

111. Voevodin V.V., Voevodin VI.V. The V-Ray Technology of Optimizing Programs to Parallel Computers // Proc. of the 1st workshop on numerical analysis and applications, Russe, Bulgary, 24-27 June, 1996.

112. Whaley J. A portable sampling-based profiler for java virtual machines // In Proceedings of the ACM 2000 Conference on Java Grande, ACM Press, June 2000. P. 78-87.

113. Whaley J., Lam M. S. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams // In SIGPLAN Conference on Programming Language Design and Implementation, 2004. P. 131-144.

114. Wilson R, Lam M.S. Efficient context-sensitive pointer analysis for C programs // In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, June 1995. P. 1-12.

115. Wolf M., Banerjee U. Data Dependence and its Application to Parallel Processing // International Journal of Parallel Programming. 1987. Vol.16, № 2. P. 137-178.

116. Wolf M.E., Lam M.S. A data locality optimizing algorithm // Proc. ACM Sig-plan Notices 1991. vol. 26. P. 30-44.

117. Zhu J., Caiman S. Symbolic pointer analysis revisited // Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation, 2004, P. 145-157.147