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

На правах рукописи

Андреев Никита Евгеньевич

ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ ЭФФЕКТИВНЫХ МЕТОДОВ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

9 ИЮН 2011

Томск-2011

4849606

Работа выполнена в Кемеровском государственном университете на кафедре ЮНЕСКО по Новьм Информационным Технологиям

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

профессор Афанасьев Константин Евгеньевич

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

профессор Старченко Александр Васильевич

кандидат технических наук . Романенко Алексей Анатольевич

Ведущая организация: Институт вычислительных технологий,

г. Новосибирск

Защита состоится 23 июня 2011 г. в 10.30 на заседании диссертационного совета Д 212.267.08 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 102.

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 34а.

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

Учёный секретарь

диссертационного совета Д 212.267.08 доктор технических наук, профессор

А. В. Скворцов

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

Актуальность работы

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

В условиях постоянного увеличения количества ядер в вычислительных системах старые подходы к анализу производительности становятся непродуктивными. Такие методы, как профилировка и анализ временных шкал, требуют ручного поиска узких мест параллельной программы, что снижает их эффективность и увеличивает трудоемкость поиска с ростом объема поступающих данных. Для оптимизации современных приложений необходимы методы автоматизированного анализа. Среди работ в данном направлении можно выделить B.R. Helm, В.P. Miller, H.L. Truong, J. Vetter, F. Wolf. В России направление анализа производительности развивается в научных коллективах под руководством С.М. Абрамова, A.B. Бухановского, Вл.В. Воеводина, В.П. Гергеля, Б.М. Глинского, В.П. Иванникова, В.А. Крюкова, В.Э. Малышкина, С.А. Немнюгина, Л.Б. Соколинского, A.B. Старченко, Ю.И. Шокина.

Стандартом де-факто для разработки параллельных программ на сегодня является Message Passing Interface (MPI). Несмотря на сравнительно высокую производительность, процесс разработки MPI-программ сложен и подвержен ошибкам, а саму библиотеку иногда называют «ассемблером параллельного программирования». Альтернативой MPI является набирающая популярность модель программирования с разделенным глобальным адресным пространством (Partitioned Global Address Space - PGAS), использующая логически общую память и односторонние коммуникации. Самым «взрослым» представителем модели является язык Unified Parallel С (UPC). Программы, написанные в этой модели, проще для понимания и имеют сравнимую с MPI производительность, а сама модель поддержана со стороны производителей аппаратного обеспечения.

В настоящее время ощущается нехватка инструментальных средств для новой модели, которые бы позволили вывести ее на уровень, сравнимый с MPI по распространенности среди разработчиков. Существующие инструменты, такие как Parallel Performance Wizard (PPW) и upc_trace, предоставляют только статистическую информацию о работе программы. Это требует от программиста последовательного просмотра всех диаграмм и графиков и ручного поиска проблем производительности. Кроме того, для параллельных приложений, генерирующих большой объем трассировочной информации, средства PPW и upc_trace вносят высокий процент накладных расходов на ввод/вывод данных, что снижает точность последующего анализа. К недос-

з

таткам РР\У также можно отнести необоснованно большой размер файлов трасс.

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

Цель работы

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

Задачи исследования

1. Исследовать методы и алгоритмы анализа производительности параллельных программ, а также модели и методы создания программных систем для высокопроизводительных вычислительных комплексов. Выявить принципы построения инструментальных средств, а также требования, предъявляемые к их реализации.

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

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

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

5. Реализовать инструментальное средство с учетом разработанных подходов, моделей и алгоритмов. Провести его тестирование на параллельных приложениях.

Методика исследований

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

Научная новизна

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

2. Предложен алгоритм трассировки, минимизирующий накладные расходы на анализ и сокращающий объем выходных данных.

3. Предложена модель программного средства, позволяющая создавать на ее основе инструменты для программной модели РОАБ, реализующие

подход автоматизированного анализа и оказывающие низкое влияние на работу программ.

4. Реализовано инструментальное средство анализа производительности UPC-программ, отличающееся от других существующих средств поддержкой автоматизированного анализа.

Практическая ценность

1. Разработанные в работе модели, подходы и алгоритмы могут быть использованы при реализации программных средств для других языков программной модели PGAS, таких как: Co-Array Fortran, Titanium, Fortress, Chapel, X10.

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

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

Внедрение результатов работы

1. Программное средство было использовано для анализа производительности и последующей оптимизации следующих приложений: реализации итерационного метода Лкоби для решения СЛАУ, полученной при дискретизации уравнения Пуассона для трехмерной структурированной сетки, реализации алгоритма блочной сортировки и реализации алгоритма быстрого преобразования Фурье. Оптимизированные версии последних двух алгоритмов вошли в зарубежный пакет NAS Parallel Benchmarks.

2. Реализованный программный комплекс используется в рамках программы «Университетский кластер» представителями научного общества Кемеровского государственного университета, занимающимися численным моделированием.

3. Теоретические и практические результаты работы используются в учебном процессе при преподавании дисциплины «Параллельное программирование» на кафедре ЮНЕСКО по НИТ Кемеровского государственного университета.

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

1. Набор шаблонов неэффективного поведения, позволяющий автоматизировать поиск проблем производительности в UPC-программах.

2. Алгоритм трассировки UPC-программ, позволяющий снизить накладные расходы на трассировку и сократить объем выходных данных.

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

4. Реализация инструментального средства для вычислительных машин с общей и с распределенной памятью.

s

5. Результаты анализа и оптимизации параллельных приложений при помощи разработанного программного средства.

Апробация работы

Основные результаты диссертации докладывались на следующих научных конференциях и семинарах: VII Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2008); Девятой международной конференции-семинаре «Высокопроизводительные Параллельные Вычисления на Кластерных Системах» (Владимир, 2009); Пятой Сибирской конференции по параллельным и высокопроизводительным вычислениям (Томск, 2009); XVII Всероссийской научно-методической конференции «Телематика'2010» (Санкт-Петербург, 2010); IX Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование (ИТММ-2010)» (Анжеро-Судженск, 2010); Выставке-конференции «Supercomputing 2010» (New Orleans, 2010); семинаре ИВМиМГ СО РАН под руководством профессора Глинского Б.М. (Новосибирск, 2010); семинаре ИСИ СО РАН «Потоковая обработка данных и программирование» под руководством Непомнящих В.А. и Шилова Н.В. (Новосибирск, 2010); научных семинарах «Информационные технологии и математическое моделирование» кафедры ЮНЕСКО по НИТ КемГУ под руководством профессора Афанасьева К.Е. (Кемерово, 20072011).

Личный вклад

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

Структура и содержание диссертационной работы

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

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

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

мые к реализации инструментальных средств. Проведен обзор языков программирования класса PGAS. В качестве наиболее «взрослого» представителя модели выделен язык Unified Parallel С (UPC).

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

Существующие в настоящий момент инструменты для языка UPC, такие как Parallel Performance Wizard (PPW), upc_trace, upc_dump, предоставляют пользователю статистическую информацию о работе программ в виде диаграмм, графиков и таблиц. Это затрудняет анализ, так как требует от пользователя визуального поиска проблем производительности. Ни один из рассмотренных инструментов не имеет средств автоматизированного анализа. Кроме того, представленные программные средства используют алгоритмы трассировки программ, которые приводят к сравнительно высоким накладным расходам и генерируют большие объемы выходных данных, что снижает точность анализа.

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

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

- иметь средства для ручной корректировки и управления процессами инструментовки и сбора данных;

- иметь сравнительно низкие требования к объему дискового пространства для хранения файлов трасс и результатов анализа;

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

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

- по возможности автоматизировать процесс анализа для снижения нагрузки на пользователя;

- позволять сравнивать данные нескольких экспериментов для оценки результатов оптимизации;

- указывать пользователю на конкретную строку кода, в которой возникла проблема производительности.

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

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

Существующие подходы к автоматизированному анализу производительности используют приемы и методы из области искусственного интеллекта, такие как экспертные системы на основе баз знаний и методы автоматической классификации. Наиболее развитым из таких методов является разработанный F. Wolf и В. Mohr метод поиска шаблонов неэффективного поведения, реализованный для библиотеки MPI и набора директив ОрепМР. Метод используется в активно развивающемся наборе инструментов Scalasca. Суть метода заключается в следующем. Различным моделям параллельного программирования присущ ряд типовых проблем производительности или, другими словами, шаблонов неэффективного поведения. Разработчик как эксперт в определенной модели может разработать набор таких шаблонов и в процессе анализа программы выполнять поиск этих шаблонов, последовательно проверяя все записи файла трассы на соответствие каждому из них. По сути, шаблон - это набор найденных в трассировочном файле событий, которые удовлетворяют условиям возникновения некоторой ситуации, которую он описывает. Такой способ представления шаблона позволяет фиксировать сложные ситуации, не охватываемые профилировочными инструментами и визуализаторами трасс.

F. Wolf и В. Mohr предложили набор шаблонов неэффективного поведения для моделей передачи сообщений и общей памяти. Автором был предложен набор из 12 шаблонов неэффективного поведения для модели разделенного глобального адресного пространства. Семь шаблонов из ОрепМР и MPI были адаптированы для языка UPC, среди них: конкуренция за блокировку, ожидание в барьере, завершение барьера, поздняя рассылка, ранняя сборка, синхронизация на входе в коллективную операцию многие ко многим, синхронизация на выходе из коллективной операции многие ко многим. Также были разработаны 5 новых шаблонов, характерных только для языка UPC, среди них: синхронизация на входе в коллективную операцию, синхронизация на выходе из коллективной операции, ранняя префиксная редукция, ожидание внутри коллективной операции, ожидание в операции динамического выделения памяти. Приведем для примера один из шаблонов.

Шаблон «Синхронизация на входе в коллективную операцию» справедлив для всех операций релокализации, в которых используется тип синхронизации UPC _IN _ALLSYNC (рис. 1). Данный тип синхронизации обязывает каждую нить дождаться на входе всех остальных. Когда нити входят в операцию релокализации в разные моменты времени - это вносит нежелательные накладные расходы на синхронизацию. Шаблон не встречается в программной модели передачи сообщений и характерен только для языка UPC. Это объясняется тем, что стандарт MPI не накладывает строгих ограничений на порядок входа нитей в коллективную операцию. Будут ли нити ожидать друг друга, как при использовании барьерной синхронизации, или же будет

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

Ь i а

потери

иотсри

иреми

Рисунок 1. Шаблон «Синхронизация на входе в коллективную операцию»

Шаблон имеет следующий алгоритм поиска. Предположим, что в данном примере используется операция релокализации upe_all_broadcastQ, которая выполняет рассылку значения переменной всем нитям. На первом этапе для всех событий трассы проверяется следующее условие: type{last) = CExit л

coll (last) ф 0 л

last.reg = upc_all_ broadcast.

Если встретилось событие выхода из коллективной операции, это событие выхода последней нитью и функцией, из которой был выполнен выход, является upe_all_broadcast(), то выполняется переход к анализу. Здесь функция type() возвращает тип события, collQ возвращает непустое множество, если все нити завершили выполнение коллективной операции и пустое множество в обратном случае. Атрибут reg для каждого события содержит название функции, с которой связано событие.

Далее проверяется условие срабатывания шаблона: := coll(last),

^ [Eventerptr, если 3e¡,e} е Eventerptr: ertime Ф ej.time, 2 [неудача, иначе. Множество E¡ содержит события выхода из функции ирс_ all __ broadcast() каждой из нитей. Далее выполняется проверка, если нити вошли в операцию не одновременно, то есть существуют события с разным временем входа в операцию, то Ег присваиваются все события входа. В данном случае enterptr - это атрибут события выхода из операции, который указывает на соответствующее событие входа.

Если шаблон сработал, то на последнем этапе рассчитывается время, потерянное на синхронизацию:

wasted = ^ ma x(E2.time) - eXime.

ееЕг

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

| ;Т. ингер."| | :Т. библ. ] | :Прсф. буф- | | :Ж. диск

bopj [О,*]

aij

[Суф| р

не заполнен] I f Уместить запись

полон]

1: Въпэшитъ уыгрузк* на дискТ I

~Т

ь буфер

Z5

Т

Рисунок 2. Алгоритм трассировки инструмента PPW

Одним из основных показателей качества инструмента анализа производительности является объем вносимых в работу исходной программы накладных расходов во время трассировки. Сильное влияние на приложение в процессе его выполнения может исказить результаты последующего анализа. В PPW, наиболее развитом инструменте для языка UPC - используется следующий алгоритм (рис. 2). Информация о возникающих в программе событиях поступает от трассировочного интерфейса в трассировочную библиотеку. Библиотека содержит промежуточный программный буфер, в котором накапливаются записи. После того как буфер заполняется, данные выгружаются на жесткий диск и буфер очищается. Достоинство такого алгоритма в использовании буферизации, что сокращает количество обращений к медленному внешнему накопителю. Однако запись на диск выполняется синхронно, что требует приостановки параллельного приложения на время записи.

ю

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

Рисунок 3. Расширенный алгоритм трассировки

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

Ввод и вывод данных во всех современных внешних накопителях осуществляются при помощи технологии Direct Memory Access (DMA), разгружающей центральный процессор. Таким образом, предложенный подход снижает накладные расходы, не оказывая в то же время дополнительного влияния на программу пользователя при создании вспомогательной нити.

Инструментовка Измерение

т Интерфейс Л"13 GASP .. : Трассировочная йиблиотежа

Л .....-*"""

^Компилятор •о ирс <•{ ЙИнструментоащйк | Библиотека ^Библиотека асинхронного В/В сжатия

л

Визуализация

Программное средство Cube

шИшерфейс и Cube

I Поиск ~ шаблонон

■ Представление шлПлонои

:Г) Анализатор

-г. Конверторе "-1 формат EPILOG

Ж.

Библиотека формата EPILOG

.^Библиотека языка EARL

. •■.V. ,. * К 1

=ОПрофилмров|«<ч

Анали) "" ра збалансь<ро«ки

Рисунок 4. Модель архитектуры программного средства

С учетом разработанного подхода к анализу и алгоритма трассировки была разработана модель архитектуры программного средства (рис. 4). Цикл работы с инструментом состоит из четырех этапов - инструментовки, измерения, анализа и визуализации. На первом этапе пользователь компилирует приложение при помощи инструментовщика. Инструментовщик добавляет в исходную программу измерительный код, который будет сообщать о событиях, возникающих в процессе работы программы, а также связывает (link) приложение с трассировочной библиотекой. На втором этапе программа запускается на вычислительной машине. В процессе работы приложения трассировочная библиотека выполняет сжатие информации о событиях и их запись при помощи технологии асинхронного ввода/вывода на диск. На третьем этапе выполняется анализ собранных данных. В качестве интерфейса доступа к файлам трасс предлагается использовать язык распознавания и анализа событий (Event Analysis and Recognition Language - EARL). EARL избавляет от необходимости ручного разбора (парсинга) трасс и представляет дан-

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

На рисунке 4 компоненты, разработанные автором, выделены темно-серым цветом. Для поддержки процесса работы с инструментом были разработаны ряд скриптов-оберток для компиляции, запуска, конвертации, анализа и визуализации, а также документация.

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

Для сравнения алгоритма трассировки, реализованного в инструменте PPW, и алгоритма, разработанного автором, были выбраны пять тестов из пакета NAS Parallel Benchmarks (NPB): метод сопряженных градиентов (Conjugate Gradient - CG), блочной сортировки (Integer Sort - IS), быстрого преобразования Фурье (FT), решение трехмерного уравнения Пуассона (MG -MultiGrid) и алгоритм генерации пар псевдослучайных чисел согласно гаус-совому распределению (ЕР - Embarrassing Parallel).

Таблица 1

Сравнение накладных расходов на трассировку _

Тест Ориг., с PPW, с ТМ, с PPW,% ТМ, % Разц.

CG 29,45 69,98 53,19 137,61 80,60 1,71

CG рирс 29,45 31,24 29,79 6,08 1,15 5,27

IS 4,17 72,93 39,54 1649,21 848,41 1,94

IS рирс 4,17 4,31 4,28 3,37 2,65 1,27

FT 51,39 55,31 52,98 7,63 3,08 2,47

MG 11,11 11,75 11,30 5,83 1,72 3,39

ЕР 16,39 16,85 16,62 2,78 141 1,97

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

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

13

эксперимента наглядно показывают преимущество улучшенного алгоритма, однако не позволяют сразу использовать эти данные для анализа.

Накладные расходы для тестов БТ, Мв, ЕР и скорректированных версий тестов Св, 18 также ниже, чем у РР\У. Для теста Св алгоритм асинхронного ввода/вывода показывает результат в 5 раз лучше, чем синхронный алгоритм. Для теста МО накладные расходы ниже в 3,5 раза. В среднем ТМ вносит в 23 раза меньший процент накладных расходов. Это объясняется неэффективностью алгоритма трассировки РР\У, который часто блокирует работу программы.

Также оценивался объем генерируемых трассировочных данных. В таблице 3 представлено сравнение размера файлов трасс для пяти тестов из пакета №В для 32 нитей.

Наилучшие результаты показывает профилировщик ирс_1тасе. Однако собираемых им данных недостаточно для полноценного анализа. РР\¥ и ТМ показывают результаты одного порядка. Использование улучшенного алгоритма (ТМ_г в таблице 2) позволяет снизить размер трасс в несколько раз. К примеру, для теста 18 сжатие «на лету» позволило сократить размер трассы в 6 раз - с 18ГБ до 3.1ГБ, тогда как размер трассы РР\У для теста 18 составляет 17ГБ.

Таблица 2

Сравнение объема трассировочных данных_

Тест upc_trace, МБ PPW, МБ TM, МБ TM_Z, МБ

CG 940 12695 13429 2583

ЕР 542 66 72 16

FT 479 775 820 192

IS 506 17401 18427 3167

MG 674 183 176 33

Тестирование модуля анализа проводилось на трех приложениях: алгоритмах параллельной блочной сортировки (Integer Sort - IS) и быстрого преобразования Фурье (Fast Fourier Transform - FFT) из пакета NAS Parallel Benchmarks (NPB) и метода Якоби.

Рисунок 5. Результаты оптимизации блочной сортировки

14

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

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

В результате оптимизации алгоритма удалось добиться сокращения времени выполнения до 30 % в случае 32 нитей. На рисунке 6 представлены графики времени расчета и масштабируемости для оригинальной и оптимизированной версий программы.

Рисунок 6. Результаты оптимизации преобразования Фурье

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

В данном примере использовались результаты срабатывания шаблона «Ожидание в барьере», анализа разбалансировки нагрузки и профилировки для крупных пересылок данных. Был сразу рассмотрен проблемный участок и выявлены причины неэффективного поведения. Последующая оптимизация программы позволила сократить время выполнения на 37 % для 256 нитей. На рисунке 6 представлены графики времени расчета и масштабируемости для оригинальной и оптимизированной версий программы. Первые две кривые с пометкой (С) соответствуют расчетам с размером матрицы 512x512x512

is

и 20 итерациями. Для кривых с пометкой (Б) использовалась матрица размером 2048x1024x1024 и 25 итераций.

В качестве главного средства для анализа метода Якоби были использованы профилировочные данные о распределении времени выполнения между функциями. Были выявлены основные «горячие точки» приложения, которые требуют оптимизации. Дальше более подробное изучение кода программы позволило определить конкретные функции программы и инструкции языка UPC, ответственные за снижение производительности. В результате оптимизации удалось ускорить алгоритм на 40 % для 256 нитей. Максимальное ускорение составило 58 % для 32 нитей. На рисунке 7 представлены графики времени расчета и масштабируемости для оригинальной и оптимизированной версий программы. Оптимизированная версия для 256 нитей показывает масштабируемость почти в два раза выше оригинальной.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

16

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

5. На основе предложенных подходов, моделей и алгоритмов реализовано инструментальное средство для языка UPC, отличающееся от других средств поддержкой автоматизированного анализа и обладающее лучшими характеристиками трассировки. При помощи инструмента были проанализированы и оптимизированы реализации алгоритмов блочной сортировки, быстрого преобразования Фурье и метода Якоби, которые могут быть положены в основу эффективных параллельных приложений. Оптимизированные версии первых двух алгоритмов вошли в пакет NAS Parallel Benchmarks.

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

Журналы, рекомендованные ВАК для представления основных научных результатов диссертации:

1. Андреев, Н.Е. Организация сбора и подготовки данных для анализа производительности UPC-программ / Н.Е. Андреев, К.Е. Афанасьев // Вестник Кемеровского государственного университета. - 2011. - Вып. 4 (44). -С. 4-10.

2. Андреев, Н.Е. Методы автоматизированного анализа производительности параллельных программ / Н.Е. Андреев // Вестник Новосибирского государственного университета. - 2009. - Т. 7, вып. 1. — С. 16-25.

3. Андреев, Н.Е. Реализация инструментального средства автоматизированного анализа производительности UPC-программ / Н.Е. Андреев, К.Е. Афанасьев // Вычислительные методы и программирование. - 2011. - Раздел 2. -С. 46-57 (http://num-meth.srcc.msu.ru/).

Публикации в других изданиях:

1. Андреев, Н.Е. Обзор методов автоматизированной оценки эффективности выполнения параллельных программ / Н.Е. Андреев. - Кемерово, 2009. -34 с. - Деп. в ВИНИТИ 22.06.09, № 390-В2009.

2. Андреев, Н.Е. Продуктивный анализ производительности параллельных приложений на мультиядерных и многоядерных архитектурах / Н.Е. Андреев, К.Е. Афанасьев // Многоядерные процессоры и параллельное программирование: материалы региональной научно-практической конференции. - Бийск, 2011. - С. 28-33.

3. Андреев, Н.Е. Система автоматизированного поиска шаблонов неэффективного поведения UPC-программ / Н.Е. Андреев // Тезисы докладов Пятой Сибирской конференции по параллельным и высокопроизводительным вычислениям. - Томск, 2009. - С. 81-82.

4. Андреев, Н.Е. Автоматизированный анализ производительности параллельных программ как способ повышения продуктивности разработчика / Н.Е. Андреев, К.Е. Афанасьев // Информационные технологии и математическое моделирование (ИТММ-2010): материалы IX Всероссийской научно-

практической конференции с международным участием. - Анжеро-Судженск, 2010. - С. 121-125.

5. Андреев, Н.Е. Архитектура системы автоматизированного анализа иРС-программ / Н.Е. Андреев // Телематика'2010: телекоммуникации, веб-технологии, суперкомпыотинг: сборник статей участников Всероссийского конкурса научных работ студентов и аспирантов. - СПб., 2010. - С. 164-166.

6. Андреев, Н.Е. Один из подходов к трассировке параллельных программ в модели разделенного глобального адресного пространства / Н.Е. Андреев // Высокопроизводительные Параллельные Вычисления на Кластерных Системах: материалы Девятой международной конференции-семинара. -Владимир, 2009. - С. 16-20.

7. Андреев, Н.Е. Инструментальное средство автоматизированного анализа производительности иРС-программ / Н.Е. Андреев, К.Е. Афанасьев // Студент и научно-технический прогресс: материалы Х1ЛХ Международной научной студенческой конференции. - Новосибирск, 2011. - С. 219-219.

8. Андреев, Н.Е. Использование пакета Бсаквса в качестве основы для анализа производительности иРС-программ / Н.Е. Андреев, К.Е. Афанасьев // Научное творчество молодежи: материалы XV Всероссийской научно-практической конференции. - Анжеро-Судженск, 2011. - С. 98-100.

Подписано к печати 17.05.2011. Формат 60х841/]б. Печать офсетная. Бумага офсетная № 1. Усл. печ. л. 1,2. Тираж 100 экз. Заказ № 181.

ООО «Издательство «Кузбассвузиздат». 650043, г. Кемерово, ул. Ермака, 7. Тел.: (3842) 58-29-34

Введение.

ГЛАВА 1. ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ

1.1. Цикл анализа производительности.

1.2. Программные модели параллельного программирования

1.2.1. Модель передачи сообщений.

1.2.2. Модель общей памяти.

1.2.3. Модель разделенного глобального адресного пространства

1.3. Языки PGAS.

1.3.1. Unified Parallel С.

1.3.2. Со-Array Fortran.

1.3.3. Titanium

1.4. Инструменты анализа производительности UPC.

1.4.1. upcdump

1.4.2. upctrace.

1.4.3. Parallel Performance Wizard.

1.5. Методы автоматизированного анализа.

1.5.1. IPS-2.

1.5.2. Подход Vetter'a.

1.5.3. SCALEA

1.5.4. Poirot.

1.5.5. EXPERT

ГЛАВА 2. НАБОР ШАБЛОНОВ НЕЭФФЕКТИВНОГО

ПОВЕДЕНИЯ

2.1. Основа метода.

2.1.1. Типы событий.

2.1.2. Состояния и атрибуты-указатели

2.2. Описание шаблонов.

2.2.1. Шаблон „Конкуренция за блокировку".

2.2.2. Шаблон „Синхронизация на входе в коллективную операцию"

2.2.3. Шаблон „Синхронизация на выходе из коллективной операции".

2.2.4. Шаблон „Ожидание в барьере"

2.2.5. Шаблон „Завершение барьера".

2.2.6. Шаблон „Поздняя рассылка".

2.2.7. Шаблон „Ранняя сборка".

2.2.8. Шаблон „Ранняя префиксная редукция".

2.2.9. Шаблон „Синхронизация на входе в коллективную операцию многие ко многим".

2.2.10. Шаблон „Синхронизация на выходе из коллективной операции многие ко многим".

2.2.11. Шаблон „Ожидание внутри коллективной операции"

2.2.12. Шаблон „Ожидание в операции динамического выделения памяти".

ГЛАВА 3. РЕАЛИЗАЦИЯ ИНСТРУМЕНТА

3.1. Инфраструктура пакета Scalasca.

3.2. Интерфейс GASP

3.3. Формирование трассы EPILOG.

3.4. Реализация.

3.4.1. Трассировка.

3.4.2. Выборочное измерение

3.4.3. Анализ фаз программы.

3.4.4. Слияние и конвертация трассы.

3.4.5. Синхронизация времени.

3.4.6. Анализ.

3.4.7. Визуализация.

ГЛАВА 4. ПРИМЕРЫ АНАЛИЗА И ОПТИМИЗАЦИИ

ПРОГРАММ

4.1. Сравнение эффективности UPC и MPI.

4.1.1. Результаты тестирования.

4.1.2. Обсуждение результатов.

4.2. Сравнение накладных расходов.

4.3. Сортировка целых чисел

4.3.1. Корректировка инструментовки.

4.3.2. Анализ полученных данных

4.3.3. Обсуждение результатов.

4.4. Быстрое преобразование Фурье.

4.4.1. Корректировка инструментовки.

4.4.2. Анализ полученных данных

4.4.3. Обсуждение результатов.

4.5. Итерационный метод Якоби.

4.5.1. Анализ полученных данных

4.5.2. Обсуждение результатов.

Современные высокопроизводительные кластеры преодолели рубеж в петафлопс, а количество ядер, которое насчитывают такие системы, десятков и сотен тысяч. Но если взглянуть на эффективность параллельных приложений на подобных системах, то оказывается, что по разным оценкам она не превышает 15% [68] или даже 3-5% [74] от пиковой производительности. Чтобы эффективно использовать потенциал дорогостоящих вычислительных установок, сообществу специалистов в области высокопроизводительных вычислений необходимы инструменты анализа производительности. С одной стороны, они помогают увеличить эффективность и масштабируемость параллельных программ, а с другой позволяют ученому сконцентрироваться на научной составляющей своего приложения, нежели на кропотливом процессе оптимизации.

Сегодня суперкомпыотериая индустрия ставит перед собой рубеж в экзафлопс. Разработка комплексов параллельных программ для таких систем является невероятно сложной задачей. Суперкомпьютеры могут иметь разную архитектуру и коммуникационную сеть [20], существует ряд алгоритмов распараллеливания , а также технологий и средств для написания параллельных программ [12]. Стандартом де-факто среди таких средств на сегодня является MPI [78]. Несмотря на сравнительно высокую производительность MPI-программ, процесс разработки приложений с использованием данной библиотеки трудоемок и подвержен ошибкам. Ограничения программной модели передачи сообщений широко признаны, а саму библиотеку MPI иногда называют "ассемблером параллельного программирования". Альтернативой MPI является набирающая популярность модель программирования PGAS - Partitioned Global Address Space (разделенное глобальное адресное пространство) [52]. В модели PGAS используются односторонние коммуникации, где при передаче данных нет необходимости в явном отображении на двухсторонние пары send и receive - трудоемкий, подверженный ошибкам процесс, серьезно влияющий на продуктивность программиста. Обычное присвоение значения переменной массива х[г] — а автоматически порождает необходимые коммуникации между узлами кластера. Программы, написанные в этой модели, проще для понимания, чем MPI версии, и имеют сравнительную или даже более высокую производительность [28]. К группе PGAS относятся такие языки как: Unified Parallel С (UPC) [43], Со-Array Fortran (CAF) [67], Titanium [109], Cray Chapel [37], IBM X10 [39], Sun Fortress [21]. Язык UPC является наиболее "взрослым" представителем модели. Компиляторы для языка UPC разработаны всеми основными вендорами суперкомпьютерного рынка. Существуют реализации от компаний IBM [26], HP [73], Cray [72], SGI [82]. Компания TotalView - ведущий разработчик в области отладки параллельных приложений поддерживает язык UPC [90]. Компания IBM включила поддержку языка UPC в интегрированную среду разработку Eclipse [42]. Но ввиду относительной молодости модели параллельного программирования PGAS, для нее существует не так много инструментальных средств. Такие известные инструменты, как Intel Trace Analyzer [76], TAU [84], Cray Apprentice [55] и другие, работают с ограниченным набором программных моделей, преимущественно моделью передачи сообщений. Те инструменты, которые на данный момент существуют, в частности для языка UPC, такие как upcdump, upctrace [77], обладают ограниченной функциональностью, a PPW [85] - Parallel Performance Wizard, позволяет получить лишь статистические данные о работе программы. В результате разработчики, использующие новые модели параллельного программирования, зачастую вынуждены вручную выполнять трудоемкий анализ в процессе оптимизации своей программы.

Также необходимо заметить, что большинство существующих инструментов используют ручной метод анализа, где пользователь должен самостоятельно выполнять поиск узких мест производительности приложения на основе представленных диаграмм, графиков, таблиц и методов манипулирования ими (масштабирование и поиск). Представление информации о производительности программы в графическом виде может быть мощным приемом, но без сложных методов фильтрации объем отображаемых данных может быть чрезвычайно большим, что сильно снижает полезность подобных инструментов. В условиях стремительного роста количества ядер в современных суперкомпьютерах особенно актуальным становится вопрос разработки средств автоматизированного анализа, которые способны в той или иной степени самостоятельно находить узкие места в приложении [1, 2]. Среди большого количества работ в данном направлении можно выделить В.P. Miller [64], J. Vetter [97], H.L. Truong [92], B.R. Helm [51], F. Wolf [104]. Наиболее перспективным, по мнению автора, можно назвать метод поиска шаблонов неэффективного поведения, предложенный F. Wolf и В. Mohr [104] для программных моделей передачи сообщений и общей памяти.

Можно отметить также ряд других работ, посвященных языку UP С. Кроме упомянутых выше компиляторов от производителей суперкомпьютеров, существует три бесплатных компилятора языка UPC: Berkeley UPC [77], GCC UPC [54], MuPC [95]. В рамках проекта RAMP Blue был разработан компилятор языка UPC для ПЛИС типа FPGA фирмы Xilinx [58]. В университете RWTH Aachen University ведется работа по разработке языка UPC для микропроцессорной архитектуры Cell Broadband Engine [66]. В рамках контракта с компанией HP в University of A Coruna и Galicia Supercomputing Center разрабатывается библиотека для параллельных численных расчетов BLAS для языка UPC [48]. В Michigan Technological University был разработан компилятор ScaleUPC, оптимизированный для систем с общей памятью [110]. В Iowa State University разрабатывается набор тестов для языка UPC, позволяющий проверить способность среды времени выполнения (runtime) фиксировать ошибки, возникающие во время работы программы [62]. Также в данном университете разрабатывается гибридная среда времени выполнения Integrated Native Communication Runtime (INCR), поддерживающая одновременно и UPC, и MPI [57]. В George Washington University разрабатывается компилятор RUPC для реконфигурируемых архитектур [46], а также компилятор для многоядерных (many core) процессоров Tile64 фирмы Tilera [15]. University of California, Berkeley разрабатывает компилятор UPC для графических процессоров [111]. Также можно отметить ряд разработанных для языка UPC расширений [22,30,32,33,35,36,45,70,71,81,88,98,108].

Среди приложений, разработанных на языке UPC, можно отметить следующие: конечно-элементный решатель задач вычислительной гидродинамики для статических неструктурированных сеток BenchC [56] и динамических неструктурированных сеток XFlow [27]; генератор сетки методом триангуляции Делоне [63]; решение задачи вычислительной гидродинамики при помощи метода Годунова второго порядка [93]; решение задачи о взаимодействии N тел методом Barnes-Hut, а также LU разложение [107]; реализация методов быстрого преобразования Фурье, приближенного решения трехмерного уравнения Пуассона, решения неупорядоченной, разряженной СЛАУ методом сопряженных градиентов [44]; обработчик данных с сенсора на основе радара с синтезированной апертурой [96]; метод Sobel для выделения границ изображения [50]; реализация метода дифференциального криптоанализа DES шифров [49] и другие.

В России направление анализа производительности параллельных программ развивается в научных коллективах под руководством академика С.М. Абрамова, A.B. Бухановского, Вл.В. Воеводина, В.П. Гергеля, Б.М. Глинского, В.П. Ивашшкова, В.А. Крюкова, В.Э. Малышкина, С.А. Немнюгина, Л.Б. Соколинского, A.B. Старченко, Ю.И. Шокина. Компания НИЦЭВТ выпускает вычислительные кластерные системы с предустановленным компилятором UPC [13]. Также компания НИЦЭВТ разрабатывает российский суперкомпьютер "Ангара" с аппаратной поддержкой PGAS [19]. В институте динамики систем и теории управления (ИДСТУ) СО РАН исследуются реализации алгоритма Survey Propagation для решения задачи выполнимости функций булевых переменных (SAT-задача) на языке UPC [16]. Сердюк Юрий Петрович, старший научный сотрудник Института программных систем РАН (Переславль-Залесский), разрабатывает учебный курс "Высокоуровневые языки программирования для параллельных архитектур" посвященный языкам PGAS, в том числе языку UPC [18].

О предмете и содержании диссертации.

Диссертация состоит из введения, четырех глав, заключения pi списка литературы. Главы диссертации разбиты на параграфы, нумерация которых внутри каждой главы своя. Общий объем диссертации составляет 136 страниц. Список литературы состоит из 111 наименований.

Основные результаты диссертации состоят в следующем:

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

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

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

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

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

Заключение

1. Андреев Н. Е. Методы автоматизированного анализа производительности параллельных программ / / Вестник Новосибирского государственного университета. 2009. Т. 7, № 1. С. 16-25.

2. Андреев Н. Е. Обзор методов автоматизированной оценки эффективности выполнения параллельных программ / / Деп. в ВИНИТИ 22.06.09, №390-В2009. 2009. С. 34.

3. Андреев Н. Е., Афанасьев К. Е. Организация сбора и подготовки данных для анализа производительности ИРС-программ // Вестник Кемеровского государственного университета. 2011. № 4 (44). С. 4-10.

4. Андреев Н. Е., Афанасьев К. Е. Реализация инструментального средства автоматизированного анализа производительности иРС-программ // Вычислительные методы и программирование. 2011. Раздел 2. С. 46-57. (http://num-meth.srcc.msu.ru/).

5. Андреев Н. Е., Афанасьев К. Е. Использование пакета 8са1азса в качестве основы для анализа производительности иРС-программ // Научное творчество молодежи: Материалы XV Всероссийской научно-практической конференции. Анжеро-Судженск, 2011. С. 98-100.

6. Андреев Н. Е. Инструментальное средство автоматизированного анализа производительности UPC-программ / / Материалы XLIX Международной научной студенческой конференции "Студент и научно-технический прогресс". Новосибирск, 2011. С. 219-219.

7. Андреев Н. Е. Архитектура системы автоматизированного анализа UPC-программ // Материалы XVII всероссийской научно-методической конференции "Телематика'2010". Санкт-Петербург, 2010. С. 164-166.

8. Андреев Н. Е. Система автоматизированного поиска шаблонов неэффективного поведения UPC-программ // Тезисы докладов Пятой Сибирской конференции по параллельным и высокопроизводительным вычислениям. Томск, 2009. С. 81-82.

9. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ, 2002. С. 608.

10. Вычислительные кластерные системы производства ОАО НИЦЭВТ Электронный ресурс. URL: http://www.nicevt.ru/techniques/81/86/ (дата обращения: 30.08.2010).

11. Межрегиональный супервычислительный центр ТГУ Электронный ресурс. URL: http://skif.tsu.ru/ (дата обращения: 30.08.2010).

12. Проекты университета George Washington University Электронный ресурс. URL: http://hpcl2.hpcl.gwu.edu/index.php/projects (дата обращения: 30.08.2010).

13. Сайт суперкомпыотерного центра коллективного пользования ИДСТУ СО РАН Электронный ресурс. URL: http://mvs.icc.ru/ (дата обращения: 30.08.2010).

14. Сапронов А. Обзор некоторых пакетов измерения производительности кластерных систем Электронный ресурс. URL: http: //www. ixbt. com/cpu/cluster-benchtheory. shtml (дата обращения: 30.08.2010).

15. Слуцкин А., Эйсымонт JI. Российский суперкомпьютер с глобально адресуемой памятью // Открытые системы. 2007. № 9. С. 42-51.

16. Сущенко С. Параллельные вычисления. Томск: ТГУ, 2003. С. 196.

17. Allen Е., Chase D., Flood С. et al. Project Fortress: A multicore language for multicore processors // Linux Magazine. 2007. Pp. 38-43.

18. Almasi G., Cascaval C. Proposal to extend UPC array types with multiple blocking factors Electronic resource., URL: http://www2.hpcl.gwu.edu/pgas09/upct iledproposal.pdf (дата обращения: 30.08.2010).

19. Amdahl G. M. Validity of the single processor approach to achieving large scale computing capabilities // AFIPS '67 (Spring): Proceedings of the April 18-20, 1967, spring joint computer conference. New York, NY, USA: ACM, 1967. Pp. 483-485.

20. Bailey D., Barszcz E., Barton J. et al. The NAS Parallel Benchmarks: Tech. Rep. RNR-94-007: NASA Ames Research Center, 1994.

21. Bailey D., Harris Т., Saphir W. et al. The NAS Parallel Benchmarks 2.0: Tech. Rep. NAS-95-020: NASA Ames Research Center, 1995.

22. Barton C., Casgaval C., Almäsi G. et al. Shared memory programming for large scale machines // PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation. New York, NY, USA: ACM, 2006. Pp. 108-117.

23. Beech-Brandt J. Applications of UPC Electronic resource. URL: http://www.nesc.ac.uk/talks/892/applicationsofupc.pdf (дата обращения: 30.08.2010).

24. Bell С., Bonachea D., Nishtala R., Yelick K. Optimizing bandwidth limited problems using one-sided communication and overlap //In 20th International Parallel and Distributed Processing Symposium (IPDPS). 2006.

25. Berkeley UPC Home Page Electronic resource., URL: http://upc.lbl.gov/ (дата обращения: 30.08.2010).

26. Bonachea D. Proposal for Extending the UPC Memory Copy Library Functions Electronic resource. URL: http: //upc. lbl. gov/publications/upcmemcpy. pdf (дата обращения: 30.08.2010).

27. Bonachea D. Proposal for Extending the UPC Memory Copy Library Functions, v2.0 Electronic resource. URL: http: //upc. lbl. gov/publications/upcmemcpy. pdf (дата обращения: 30.08.2010).

28. Bonachea D. Proposal for High-Performance Clock Timers in UPC Electronic resource., https://upc-wiki.lbl.gov/images/9/9b/Upctick0.2.pdf обращения: 30.08.2010).1. WallURL: (дата

29. Bonachea D. UPC Collectives Value Interface Electronic resource., URL: http://upc.lbl.gov/docs/user/README-collectivev.txt (дата обращения: 30.08.2010).

30. Bonachea D., Datta K., Gay D. et al. Titanium Language Reference Manual Electronic resource., URL: http ://titanium.es.berkeley.edu/doc/lang-ref.pdf (дата обращения: 30.08.2010).

31. Bonachea G. Proposal for Extending the UPC Libraries with Explicit Point-to-Point Synchronization Support Electronic resource. URL: http://www2.hpcl.gwu.edu/pgas09/upcsem.pdf (дата обращения: 30.08.2010).

32. Cascaval С., Almasi G., Saraswat V. Proposal to Extend UPC with Asynchronous Execution Electronic resource. URL: http : //www2. hpcl. gwu. edu/pgas09/upcAsync. pdf (дата обращения: 30.08.2010).

33. Chamberlain В. L., Callahan D., Zima H. P. Parallel programmability and the chapel language // International Journal of High Performance Computing Applications. 2007. Vol. 21. Pp. 291-312.

34. Chandy K. M., Misra J. Distributed computation on graphs: shortest path algorithms // Commun. ACM. 1982. Vol. 25, no. 11. Pp. 833-837.

35. Co-Array Fortran Home Page. URL: http://www.co-array.org/ (дата обращения: 30.08.2010).

36. DeRose L., Hoover T. The Dynamic Probe Class Library An Infrastructure for Developing Instrumentation for Performance Tools //In International Parallel and Distributed Processing Symposium. 2001.

37. Eclipse РТР Home Page Electronic resource., URL: http://www.eclipse.org/ptp/ (дата обращения: 30.08.2010).

38. El-Ghazawi Т. UPC Language Specifications Electronic resource. URL: http: //www. gwu. edu/~upc/documentation. html (дата обращения: 30.08.2010).

39. El-Ghazawi Т., Cantonnet F. UPC Performance and Potential: A NPB Experimental Study //In Sup er computing2002 (SC2002). IEEE Computer Society, 2002. Pp. 1-26.

40. El-Ghazawi Т., Cantonnet F., Saha P., Yao Y. UPC-IO: A Parallel I/O API for UPC Electronic resource. URL: http://upc.gwu.edu/docs/upciol. 0.2. pdf (дата обращения: 30.08.2010).

41. El-Ghazawi Т., Serres О., Bahra S. et al. Parallel Programming of HighPerformance Reconfigurable Computing Systems with Unified Parallel С // Proceedings of the Fourth Annual Reconfigurable Systems Summer Institute (RSSI'08). 2008.-July.

42. Flaviu C. Probabilistic Clock Synchronization // Distributed Computing. 1989. Vol. 3, no. 3. Pp. 146-158.

43. González-Domínguez J., J. Martín M., Taboada G. L. et al. A Parallel Numerical Library for UPC // Euro-Par '09: Proceedings of the 15th International Euro-Par Conference on Parallel Processing. Berlin, Heidelberg: Springer-Verlag, 2009. Pp. 630-641.

44. Gordon В., Nguyen N. Overview and Analysis of UPC as a Tool in Cryptanalysis Electronic resource. URL: http://www.hcs.uf1.edu/upc/archive/UPCCryptanalysisReport-310CT03.pdf (дата обращения: 30.08.2010).

45. GWU UPC Benchmark Electronic resource. URL: http: //www. gwu. edu/~upc/downloads/upcbench. tar. gz (дата обращения: 30.08.2010).

46. Helm В. R., Malony A. D., Fickas S. Capturing and automating performance diagnosis: the Poirot approach // Proceedings of the 9th International Parallel Processing Symposium (IPPS '95). IEEE Computer Society, 1995. Pp. 606-613.

47. High Productivity Computing Systems Program Electronic resource., URL: http://www.highproductivity.org/ (дата обращения: 30.08.2010).

48. Intrepid UPC Home Page Electronic resource., URL: http://www.gccupc.org/ (дата обращения: 30.08.2010).

49. CRAY Research. Introducing the MPP Apprentice Tool, 1994.

50. Johnson A. A. CFD on the Cray X1E using Unified Parallel С Electronic resource. URL: http://upc.gwu.edu/upcworkshop05/ahpcrc-UPCUserForum.pdf (дата обращения: 30.08.2010).

51. Jose J., Luo M., Sur S., Panda D. K. Unifying UPC and MPI Runtimes: Experience with MVAPICH // Proc. of Int'l Workshop on Partitioned Global Address Space (PGAS '10). 2010.

52. Krasnov A., Schultz A.; Wawrzynek J. et al. Ramp blue: a message-passing manycore system in FPGAs //In 2007 International Conference on Field Programmable Logic and Applications, FPL 2007. 2007. Pp. 27-29.

53. Leko A. Performance Analysis Strategies Electronic resource. URL: http://www.hcs.uf1.edu/prj/upcgroup/upcperf/documents/-20050302-AnalysisDraft.pdf (дата обращения: 30.08.2010).

54. Leko A., Bonachea D., Su H.-H., George A. GASP: A Performance Analysis Tool Interface for Global Address Space Programming Models: Tech. Rep. LBNL-61606: Lawrence Berkeley National Lab, 2006.

55. Leko А , Sherburne H., Su II. et al. Practical Experiences with Modern Parallel Performance Analysis Tools: An Evaluation Electronic resource. URL: http://www.hcs.ufl.edu/upc/archive/toolevals/WhitepaperEval-Summary.pdf (дата обращения: 30.08.2010).

56. Luecke G. R., Coyle J., Hoekstra J. et al. Evaluating error detection capabilities of UPC run-time systems // PGAS '09: Proceedings of the Third Conference on Partitioned Global Address Space Programing Models. New York, NY, USA: ACM, 2009. Pp. 1-4.

57. Mesh generation using Delaunay triangulation in UPC Electronic resource., URL: http://upc.lbl.gov/demos/delaunay.shtml (дата обращения: 30.08.2010).

58. Miller В. P., Clark M., Hollingsworth J. et al. IPS-2: The Second Generation of a Parallel Program Measurement System // IEEE Transactions on Parallel and Distributed Systems. 1990. Vol. 1. Pp. 206-217.

59. MPI NAS Parallel Benchmarks Project Page Electronic resource., URL: http://www.nas.nasa.gov/Resources/Software/npb.html (дата обращения: 30.08.2010).

60. Numrich R. W. Co-Array Fortran for parallel programming // ACM Fortran Forum. 1998. Vol. 17. Pp. 1-31.

61. Oliker L., Canning A., Carter J. et al. Scientific application performance on candidate petascale platforms //In Proc. of the International Parallel & Distributed Processing Symposium (IPDPS). 2007.

62. Rabenseifner R. The controlled logical clock a global time for trace based software monitoring of parallel applications in workstation clusters // In

63. Proc. of the 5th EUROMICRO Workshop on Parallel and Distributed Processing (PDP). 1997. Pp. 477-484.

64. Berkeley UPC Team. The 'bupcatomic*' function family Electronic resource., URL: http: //upc. lbl. gov/docs/user/index. shtml#atomics (дата обращения: 30.08.2010).

65. Berkeley UPC Team. Runtime thread layout query for hierarchical systems Electronic resource. URL: http://upc.lbl.g0v/d0cs/user/#threaddist (дата обращения: 30.08.2010).

66. Cray Inc. Cray С and С++ Reference Manual Electronic resource., URL: http://docs.cray.com/books/S-2179-72 (дата обращения: 30.08.2010).

67. Hewlett-Packard Company. HP UPC/HP SHMEM User's Guide Electronic resource., URL: http://www.hp.com/go/upc (дата обращения: 30.08.2010).

68. High-End Computing Revitalization Task Force. Federal Plan for High-End Computing Electronic resource. URL: http://www.nitrd.gov/pubs/2004hecrtf/20040702hecrtf.pdf (дата обращения: 30.08.2010).

69. High-End Computing Revitalization Task Force. Federal Plan for High-End Computing Electronic resource. URL: http://www.nitrd.gov/pubs/2004hecrtf/20040702hecrtf.pdf (дата обращения: 30.08.2010).

70. Intel Corporation. Intel Trace Analyzer Reference Guide Electronic resource., URL: http://software.intel.com/sites/products/documentation/-hpc/itac/itareferenceguide.pdf (дата обращения: 30.08.2010).

71. LBNL, UC Berkeley. Berkeley UPC User's Guide Electronic resource., URL: http://upc.lbl.gov/docs/user/index.shtml (дата обращения: 30.08.2010).

72. Message Passing Interface Forum. MPI: A Message-Passing Interface Standard Electronic resource., URL: http://www.mpi-forum.org (дата обращения: 30.08.2010).

73. The Scalasca Development Team. CUBE 3.3 User Guide: Generic Display for Application Performance Data Electronic resource. URL: http://www.fz-juelich.de/jsc/datapool/scalasca/cube3-wx.pdf (дата обращения: 30.08.2010).

74. RMIT HPC Resources Wiki Electronic resource., URL: http://its-ru-hpc-mgmt.cs.rmit.edu.au/doku.php (дата обращения: 30.08.2010).

75. Serres О., Kayi A., Anbar A., El-Ghazawi T. A UPC Specification Extension Proposal for Hierarchical Parallelism Electronic resource. URL: http://www2.hpcl.gwu.edu/pgas09/hierarchicalparallelism.pdf (дата обращения: 30.08.2010).

76. SGI Unified Parallel С (UPC) User's Guide Electronic resource., URL: http://techpubs.sgi.com/library/manuals/5000/007-5604-002/pdf/007-5604-002.pdf (дата обращения: 30.08.2010).

77. Shende S. S. The role of instrumentation and mapping in performance measurement: Ph.D. thesis / University of Oregon. 2001.

78. Shende S. S., Malony A. D. The Tau Parallel Performance System // The International Journal of High Performance Computing Applications. 2006. Vol. 20. Pp. 287-331.

79. Su H. H., Billingsley M., George A. D. Parallel Performance Wizard: A Performance Analysis Tool for Partitioned Global-Address-Space Programming Models //In Proceedings, ACM/IEEE Conference on Supercomputing (SC 2006) Poster Session. 2006.

80. Sunderam V. S. PVM: a framework for parallel distributed computing // Concurrency: Pract. Exper. 1990. Vol. 2, no. 4. Pp. 315-339.

81. Thorsen A. Atomic Memory Operations proposal Electronic resource. URL: http://www.cs.mtu.edu/ athorsen/research/atomic/-atomicproposal.pdf (дата обращения: 30.08.2010).

82. Titanium Home Page Electronic resource. URL: http://titanium.cs.berkeley.edu/ (дата обращения: 30.08.2010).

83. TotalView Technologies Home Page Electronic resource. URL: http://www.totalviewtech.com/ (дата обращения: 30.08.2010).

84. Truong H. L., Fahringer Т. Scalea a Performance Analysis System for Distributed and Parallel Programs //In 8th International Euro-Par Conference. Springer, 2002. Pp. 75-85.

85. UPC CFD Visualization Electronic resource., URL: http: //upc. lbl. gov/demos/UPC-CFD. shtml (дата обращения: 30.08.2010).

86. UPC NAS Parallel Benchmarks Project Page Electronic resource. URL: http://threads.hpcl.gwu.edu/sites/npb-upc (дата обращения: 30.08.2010).

87. UPC Projects at MTU Electronic resource., URL: http://www.upc.mtu.edu/ (дата обращения: 30.08.2010).

88. UUPC SSCA #3 Electronic resource., URL: http://threads.hpcl.gwu.edu/sites/ssca3 (дата обращения: 30.08.2010).

89. Vetter J. Performance analysis of distributed applications using automatic classification of communication inefficiencies // ICS '00: Proceedings of the 14th international conference on Supercomputing. New York, NY, USA: ACM, 2000. Pp. 245-254.

90. Wibecan B. F. UPC: Privatizing Functions Electronic resource. URL: http://www2.hpcl.gwu.edu/pgas09/HPUPCProposal.pdf (дата обращения: 30.08.2010).

91. Wijngaart R. The NAS Parallel Benchmarks 2.4: Tech. Rep. NAS-02-007: NASA Ames Research Center, 2002.

92. Wolf F. Automatic Performance Analysis on Parallel Computers with SMP Nodes: Ph. D. thesis / RWTH Aachen, Forschungszentrum Jülich. 2003.

93. Wolf F., Bhatia N. EARL API Documentation: High-Level Trace Access Library: Tech. Rep. ICL-UT-04-03: Forschungszentrum Jülich, University of Tennessee, 2004.

94. Wolf F., Mohr В. Automatic Performance Analysis of MPI Applications Based on Event Traces // Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing. London, UK: SpringerVerlag, 2000. Pp. 123-132.

95. Wolf F., Mohr В. Specifying performance properties of parallel applications using compound events // On-line monitoring systems and computer tool interoperability. Commack, NY, USA: Nova Science Publishers, Inc., 2003. Pp. 91-110. ISBN: 1-59033-888-X.

96. Wolf F., Mohr В., Bhatia N. et al. EPILOG Binary Trace-Data Format: Tech. Rep. FZJ-ZAM-IB-2004-06: Forschungszentrum Jülich, 2004.