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

Полуян Степан Вячеславович

АНАЛИЗ ОБРАЩЕНИЙ ПРОГРАММЫ К ПАМЯТИ В ОПТИМИЗИРУЮЩЕЙ РАСПАРАЛЛЕЛИВАЮЩЕЙ СИСТЕМЕ

Специальность 05.13Л1 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

~ 1 ДЕК 2011

Санкт-Петербург 2011

005003087

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» на кафедре алгебры и дискретной математики.

Научный руководитель: доктор технических наук, с.н.с.

Штейнберг Борис Яковлевич

Официальные оппоненты: доктор физико-математических наук,

профессор Терехов Андрей Николаевич

доктор технических наук, профессор Бухановский Александр Валерьевич

Ведущая организация: Учреждение Российской академии наук Институт

систем информатики им. А.П. Ершова Сибирского отделения РАН

Защита состоится 22 декабря 2011 г. в 11 часов на заседании диссертационного совета Д 212.227.06 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д. 49, центр интернет образования.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

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

Ученый секретарь диссертационного совета __ Лисицына Л.С.

доктор технических наук, профессор

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

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

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

Среди наиболее известных оптимизирующих и распараллеливающих компиляторов можно назвать GNU Compiler Collection (GCC), SUIF Compiler и Intel С++ Compiler. В отечественной науке наиболее заметными в этой области являются система V-Ray, система ПРОГРЕСС, DVM-система, Т-система, среда ParJava, языки трС и НОРМА, системы ОРС и ДВОР.

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

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

строится новый альтернативный Тор500 рейтинг производительности вычислительных систем ОгарЬЗОО1.

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

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

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

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

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

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

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

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

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

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

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

' ОгарЬбОО. ИНЬ: Ь11р://ж\то.вгарЬ500.ог£

лизации программного обеспечения использовались принципы объектно-ориентированного программирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение результатов работы. Результаты работы используются в проекте «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения» (ДВОР) ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, государственный контракт № 02.740.11.0208 от 7 июля 2009 г. В процессе работы получено свидетельство о государственной регистрации программ для ЭВМ: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ» (свидетельство №2011617205). Кроме того, части данной работы используются в проектах «Тренажер параллельного программиста», «Анализатор распараллеливаемое™ циклов» и «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК» ФЦП «Научные и научно-педагогические кадры инновационной России», государственный кон-факт № 14.740.11.0006 от 1 сентября 2010.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на международных и российских научно-технических конференциях: THE 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (2009, Moscow), Всероссийская суперкомпыотерная конференция «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность» (2009 г., Новороссийск), Всероссийская конференция молодых ученых «Теория и практика параллельного программирования» (2010 г., Новороссийск), 5-ая Международная конференция «Параллельные вычисления и задачи управления» (2010 г., Москва), Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: су-перкомпыотерние центры и задачи» (2010 г., Новороссийск), XVIII Всероссийская научно-методическая конференция Телематика'2011 (2011 г., Санкт-Петербург).

Публикации. По теме диссертации опубликовано 12 печатных работ (из них 2 - в изданиях из перечня ведущих рецензируемых научных журналов и изданий Высшей аттестационной комиссии Министерства образования и науки РФ).

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

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

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

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

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

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

Во втором разделе первой главы описаны алгоритмы анализа псевдонимов, разработанные и реализованные автором данной работы в системе ДВОР. Предложенный анализ псевдонимов основывается как на анализе целей указателей (points-to analysis), так и на анализе типов переменных (type-based alias analysis), что позволяет, не снижая точности анализа псевдонимов, обойтись более простыми вычислениями там, где это возможно.

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

Отличительными особенностями предложенного автором алгоритма анализа псевдонимов являются:

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

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

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

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

В третьем разделе описано применение анализа псевдопимов в ДВОР для уточнения потока данных и уточнения информационных зависимостей.

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

Тестирование анализа псевдонимов в компиляторе Intel С++ Compiler ХЕ 12.0.3.175 показано, что компилятор проводит распараллеливание с ошибкой, если программа содержит информационную зависимость, образованную путем создания псевдонимов через присвоение адреса целочисленной переменной. Напри-

мер, если сначала выполнить присваивание "int addrB = (int)(&B)", а затем создать указатель "double **pB=[double**)addrB", то компилятор не может определить к какой переменной указатель рВ является псевдонимом. В итоге, результат работы программы, собранной с помощью Intel С++ Compiler ХЕ в исполняемый файл с использованием ключа распараллеливания «Enable Parallelization

(/(¿parallel)», получается некорректным.

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

программные переменные, а не только переменные указательного типа (рис. 1).

ШШШШШ..... .....

3 trpvfengegton №ttfes • •

tor [long int i -О; 1 < IT: 1++) ( X[i] - 1+1: B[i] - i*3.7;>

:}jnt nddlfi; IX (л[0] > О)

üddrB • (int; i*ß): double ' *dE- (di)ablc' • 1 oddzB; 'рП-tArlJ; / ' creance. npu.:n.onav«s P - А ••

rot (long Int i - 1; 1 < 1000; i++) <

1[1J - ie-lO"i(l'ï) + ein{Btl)»AU3); return 0;

.-. Eip»es«*i ämptfior 5ii»täi*ionFcw<*d I Swq> StÄecients Switch To. if

B-V .

tf

a Crtraf «M »SpRtmg

P-ciânj $ L oops

' looo ÖihbUloo ■ Lrwp M ЦпгЛгч Looc Fasten LoocM«t»ig lowUniP^ «etuocncy EimtaJüan Strip Mrens

* i

-V

jVt^ütfas 1 ,' TrmsfeMfo-s I ftatfs Г"

ÎVJIISMг*___:

HÄreiesjire! - . г.- . " ■ : ■ * . ^

Lekfti-JuHi--■.Vi»''.".

U 19:03:38 OP5 0eiw>S:Wdco

■ Ь, " j "

Рис. 1. Анализ псевдонимов в системе ДВОР

Тестирование анализа псевдонимов в компиляторе Microsoft Visual С++ 2008 показало, что он не выполняет оптимизацию той части кода, которая содержит псевдонимы массивов. Так, при замене в программе обращения к массиву по индексу "А [ 1 ] =1 ; " на обращение к массиву через указатель "pAl = &А[1];

*рА1 = 1 ; " компилятор не может определить, к какому элементу массива происходит обращение и, следовательно, не проводит никакой оптимизации. Реализованный автором данной работы в системе ДВОР алгоритм анализа псевдонимов

позволяет выявить подобные псевдонимы.

Тестирование быстродействия анализатора псевдонимов проведено на известных тестах производительности NAS и SPEC. Результаты измерений приведены в таблице 1.

Таблица 1

Время проведения анализа псевдонимов

Тестируемая программа Решаемая задача Время анализа, реализованного в ДВОР, мин Время классического анализа, мин

NPB DC Программа реализует оператор «куб данных» для технологии OLAP (3154 строк кода). 10,37 274,19

SPEC 458.sjeng Программа реализует несколько вариантов игры в шахматы (13870 строк кода). 24,03 980,41

SPEC 470.1bm Программа реализует «метод решеток Больцмана» для симуляции поведения несжимаемых текучих сред (1161 строк кода). 3,51 23,03

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

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

В первом разделе данной главы сделан обзор существующих алгоритмов профилирования программ. Рассмотрены особенности таких профилировщиков, как Intel VTune Amplifier ХЕ, AMD CodeAnalyst, AQtime Pro, Visual Studio Team System Profiler и IBM Rational Software Analyzer.

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

как в современных профилировщиках. При этом сохраняется основное достоинство статического профилирования - анализ программы еще до ее запуска.

Схема взаимодействия пользователя с разработанным профилировщиком представлена на рисунке 2.

Информация пользователя

Профилировщик

Пользователь

.4 '

Слисок операторов

Рис. 2. Схема взаимодействия пользователя с профилировщиком в ДВОР

Отличительными особенностями предложенного автором данной работы алгоритма профилирования являются:

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

® способность учета пользовательской информации;

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

Таким образом, реализованный автором в рамках проекта ДВОР профилировщик позволяет определить на этапе компиляции время выполнения таких программных единиц, как операторы и подпрограммы, для произвольных программ.

В третьем разделе второй главы описано сравнение результатов статического профилирования, реализованного автором в системе ДВОР, с результатами работы коммерческих динамических профилировщиков. Результат профилирования программы SPEC 470.1bm в системе ДВОР изображен на рисунке 3.

L8M_performStreomCcIIide

LBMJoadOtstacleFile 3 5692

IBMJnitializeGrid J 4679

LBM_showGridStatistics j 3983

LBM handielnOutRow i 3150

LBMJmtializeSpecialCellsForChannel 1711

main 1190

MA)N_parseCommandLine 764

lBM_allocateGrid 679

MAINJnitialiie 656

MAIN_printlnfo ' 540

LBM_SW3pGrids 494

MAlN_flnalize 394

IBMJraeGrld 341

storeValue 276

toadvalue 246

MAINstopClock 0

MAIN startclock 0

100000 [ 50000 200000 250000

Рис. 3. Результат профилирования программы SPEC 470.lbm в ДВОР

Результат профилирования этой программы с помощью профилировщика Intel у Tune Amplifier ХЕ 201 i (build 119041) приведен на рисунке 4.

SHotepOtS'.i; К © . У,-: ; Ipteti/Tyffe Amplifierкегон

Штат/а» SkKk ,ll¡

• ISM jietf¿n«re«Aáíe

siiUWJOác^tadéFfe i"

aeHJnSisfeeüiJ ......................1

stHWjte^áaisSM 1 JtEW_íree4iW .......... I

BJTCjCI-íKttsp....... {.

• at)tm '

¡v:- :

1¿SS9

!.004f 0.7Щ: 0,744! •*>'/■>; e,CSÍs ' 0.СЙ55 0.0614

4c<fcte FuxtwíftlS)

... ,( -jm r « «■ ¡fcw' -""о*'' '

skc . i. * в/вв&ш <»![ 1

SPEC...

spec ... *

• «rail

S-'-iX... • «res>

5ñX... ......

'Ж,-. J«í.,'.Ji«'Ea<

лн

StítrtíCÍ Sli«(S)'

Рис. 4. Профилирование SPEC 470.!bm с помощью Intel VTune ХЕ 2011

Профилировщик Intel VTune ХЕ 2011 показывает, что самой горячей точкой программы является функция LBM_performStreamCollide, что подтверждает результаты, полученные с помощью статического профилировщика в системе ДВОР.

Профилирование той же программы с помощью профилировщика AQtime PRO (ver. 7.10.380.86) дало следующий результат (рис. 5):

Рис. 5. Профилирование SPEC 470.1bm с помощью AQtime PRO

Можно видеть, что результаты, полученные с помощью реализованного автором в ДВОР статического профилировщика (рис. 3), в целом аналогичны результатам, полученным с помощью динамических профилировщиков (рис. 4 и 5), однако есть несколько различий:

• Подпрограммы LBM_allocateGrid и LBM_freeGrid при статическом профилировании получаются менее горячими, чем при динамическом, что вызвано наличием в них функций malloc и free, время выполнения которых зависит от работы системы памяти.

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

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

ности NAS и SPEC (табл. 2).

Таблица 2

Время профилирования тестовых программ

Тестируемая программа '. Кол-во ! Время, Решаемая задача | строк ( №К

SPEC 410.bwaves Программа численного решения задачи распространения взрывной волны (язык Fortran]. 923 1,69

SPEC 458.sjeng Программа реализует несколько вариантов игры в шахматы (язык С). 13870 7,18

SPEC 470.1bm Программа реализует «метод решеток Больц-мана» для симуляции поведения несжимаемых текучих сред (язык С). 1161 2,43

NPB CG Программа решения СЛАУ (язык Fortran). 1177 2,07

NPBDC Программа реализует оператор «куб данных» для технологии обработки информации баз данных OLAP (язык С). 3154 5,01

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

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

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

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

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

График показывает во сколько раз доступ к матрице по строкам быстрее доступа по столбцам при пострчном размещении матрицы

£ « С 8

О 300 700 1100 1500 1900 2300 2700 3100 3500 3900 4300 4700 5000

параметр N

-Чтение ---- Запись

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

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

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

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

: Численные эксперимеоты проведены на кластере мехмата ЮФУ для задачи суммирования элементов матрицы.

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

Профилирование;

Цикл (пока существуют неразмещенные массивы) {

Выбирается самая горячая точка программы, содержащая хотя бы одно вхождение еще неразмещенного массива;

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

1 I

Конец алгоритма.

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

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

Таблица 3

Время проведения анализа размещения данных

Программа - Примечание Время без эвристики, мин Время с эвристикой, мин Ускорение ■■I

Перемножение матриц В программе используются квадратные матрицы размера 1000x1000 3,23 2,05 1,63

Сложение матриц В программе используются квадратные матрицы размера 10000x10000 1,42 1,14 1,38

LU разложение матриц В программе используются квадратные матрицы размера 1000x1000 3,51 2,33 1,51

SPEC 410.bwaves Программа численного решения задачи распространения взрывной волны (923 строк кода, 51 массив размерности от 3 до 5]. 33,23 17,51 1,87

Программа реализует не-

SPEC сколько вариантов игры в 13,04 8,23 1,56

458.sjeng шахматы (13870 строк кода.

11 двумерных массивов).

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

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

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

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

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

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

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

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

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

работы с памятью.

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

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

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

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

4. Полуян С.В. Автоматическое размещение массивов в распределенной памяти с минимизацией количества пересылок // Труды научной школы И.Б. Симо-пенко. - Ростов-на-Дону: Изд-во ЮФУ, 2010. - С. 214-219.

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

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

7. Полуян С.В. Профилирование и его применение в диалоговом высокоуровневом оптимизирующем распараллеливателе // Научный сервис в сети Интернет: суперкомпыотерные центры и задачи: Труды Международной суперкомпьютерной конференции (20-25 сентября 2010 г., г. Новороссийск). -М.: Изд-во МГУ, 2010. - С. 652-653.

8. Полуян С.В. Оптимальное размещение данных на этапе компиляции // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г. Новороссийск). - М.: Изд-во МГУ, 2009. - С. 283-286.

9. Steinberg В., Abramov A., Alymova Е„ Baglij A., Guda S., Demin S., Dubrov D., Ivchenko A., Kravchenko E., Makoshenko D„ Molotnikov Z, Morilev R., Nis Z , Petrenko V., Povazhnij A., Poluyan S., Skiba I., Suhoverkhov S„ Shapovalov V., Steinberg O., Steinberg R. Dialogue-based optimizing parallelizing tool and

C2HDL converter // Proceedings of 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (Moscow, Russia, September 18-21,2009). - 2009 -P. 216-218.

10. Штейнберг Б.Я., Абрамов A.A., Алымова Е.В., Баглий АЛ., Гуда С.А., Дубров Д.В., Кравченко E.H., Морылев Р.И., Hue З.Я., Петренко В.В., Полуян C.B., Скиба КС., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б., Юрушкин М.В. Диалоговый высокоуровневый оптимизирующий распараллеливатель (ДВОР) И Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды Международной суперкомпьютерной конференции (20-25 сентября 2010 г., г. Новороссийск). - М.: Изд-во МГУ, 2010. - С. 71-75.

11. Штейнберг Б.Я., Абрамов A.A., Баглий АЛ., Морылев Р.И., Петренко В.В., Полуян C.B., Штейнберг Р.Б. Уточнение зависимостей программы в ДВОР // Параллельные вычисления и задачи управления (PÀCO'2010): Труды V Международной конференции (26-28 октября 2010 г., г. Москва). - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2010. - С. 855-864.

12. Штейнберг Б.Я., Штейнберг Р.Б., Морылев Р.И., Петренко В.В., Полуян C.B., Штейнберг О.Б., Баглий А.П., Hue 3-Я., Скиба И.С., Юрушкин М.В., Шаповалов В.Н., Алымова Е.В., Кравченко E.H., Гуда С.А. Диалоговый высокоуровневый оптимизирующий распараллеливатель программ // Свидетельство о государственной регистрации программы для ЭВМ № 2011617205 -2011.

Тиражирование и брошюровка выполнены в учреждении

«Университетские телекоммуникации»

197101, Санкт-Петербург, Саблинская ул., 14

Тел. (812) 233 4669 объем 1 п.л.

Тираж 100 экз.

ВВЕДЕНИЕ.

ГЛАВА 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 таблиц.

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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