Разработка средств анализа информационных обменов в параллельных программах на языке IBM X10

Федеральное агентство связи Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«Сибирский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО «СибГУТИ»)

Кафедра вычислительных систем

ДИПЛОМНЫЙ ПРОЕКТ

Разработка средств анализа информационных обменов в параллельных программах на языке IBM X10

Студента Сашенина П.С.

Группа ВМ-87

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

1.

ЗАДАНИЕ

1. Тема проекта: «Разработка средств анализа информационных обменов в параллельных программах на языке IBM X10» утверждена указом по университету от «9» января 2013 г. № 4/2−13

2. Срок сдачи студентом законченного проекта: 8 июня 2013 г.

3. Исходные данные по проекту (эксплуатационно-технические данные):

3.1 Техническое описание кластерной ВС

3.2 Документация языка.

4. Содержание расчетно-пояснительной записки (перечень подлежащих разработке вопросов) и сроки выполнения по разделам:

5. Консультанты по проекту (с указанием относящихся к ним разделов проекта).

Безопасность жизнедеятельности (Курносов М.Г.)

Расчет экономических показателей (Курносов М.Г.)

Дата выдачи задания:

«_____» _________________ ___________ Курносов М.Г.

Задание принял к исполнению

«_____» _________________ ___________ Сашенин П. С

.

ОТЗЫВ

на дипломный проект студента группы ВМ-87 Сашенина П.С.

Увеличение количества процессорных ядер в распределенных вычислительных системах (ВС) и усложнения их конфигураций (вычислительные узлы с ускорителями, иерархическая коммуникационная система) требует создания адекватных средств создания параллельных программ. Компанией IBM разработан язык IBM X10 реализующий модель параллельных вычислений APGAS — Asynchronous Partitioned Global Address Space. В рамках этой модели параллельным потокам (activities) доступна вся память вычислительных узлов. При попытке потока получить доступ к области памяти, находящейся на другом узле, runtime-система языка выполняет удаленное копирование или запись информации.

В рамках дипломного проекта Сашенин П. С. разработал профилировщик (profiler) для анализа фоновых информационных обменов между ветвями программ на IBM X10. Пакет осуществляет формирование протокола выполнения программ для его последующего анализа. Собранная информация может быть использована для оптимизации обменов в параллельной программе.

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

Несмотря на указанное замечание, считаю, что дипломный проект заслуживает оценки «ОТЛИЧНО», а Сашенин П. С. — присвоения квалификации инженер по специальности 230 101.65 «Вычислительные машины, комплексы, системы и сети».

РЕЦЕНЗИЯ

на дипломный проект Студента Сашенин П.С.,

По специальности (группа, шифр) ВМ-87, 230 101.65

Тема дипломного проекта: «Разработка средств анализа информационных обменов в параллельных программах на языке IBM X10».

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

Созданный пакет предназначен для анализа информационных обменов в параллельных программах на языке IBM X10.

Выполнена серия экспериментов на вычислительном кластере Центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ».

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

Замечания: в работе рассматривается только общее количество принятой информации вычислительным узлом.

Несмотря на указанное замечание, считаю, что дипломный проект заслуживает оценки ««, а Сашенин П. С. — присвоения квалификации инженер по специальности 230 101.65 «Вычислительные машины, комплексы, системы и сети».

• Введение
• 1. Понятия О ВС
• 1.1 Классификация ВС
• 1.2 Распределенные ВС
• 1.3 Параллельные алгоритмы и программы
• 1.4 Модели параллельных вычислений PGAS и APGAS
• 1.5 Язык IBM X10
• 1.6 Профилирование
• 2. Пакет для профилирования программ на языке IBM X10
• 2.1 Функциональная структура пакета
• 2.2 Описание модулей пакета
• 2.3 Организация экспериментов
• 2.4 Результаты экспериментов
• 3. Расчёт экономических показателей программного продукта
• 3.1 Расчёт себестоимости и цены программного
• 3.2 Оценка экономического эффекта от использования программного продукта
• 4. Безопастность жизнедеятельности
• 4.1 Характеристика вредных факторов при работе с ПК
• 4.2 Профилактика зрительного и статического утомления
• 4.3 Пожарная безопасность офисных помещений
• Заключение
• Библиография

Наиболее употребляемые текстовые сокращения

• Приложения
• Введение
• В настоящее время широкое распространение получили распределенные вычислительные системы (ВС). В архитектурном плане распределенная ВС представляется множеством взаимодействующих элементарных машин, оснащенных средствами коммуникаций и внешними устройствами.
• Также создаются средства, облегчающие процесс создания параллельных программ, в частности компания IBM разработала для этих целей язык X10.
• Существует такая статистика: 20% кода выполняется 80% времени. Точность ее вряд ли полностью соответствует реальному положению вещей, а вот общий смысл довольно интересен: получается, что оптимизация всего приложения — занятие неблагодарное и глупое, а реальные результаты может дать только оптимизация тех 20% приложения, которые выполняются дольше всего. Необходимо только найти эти 20%. Профилирование позволяет выявлять подобные «узкие» места программы.
• Задачи профилирования актуальны для языков программирования, в частности и для языка IBM X10.
• В данной работе разработана библиотека, позволяющая перехватывать информационные обмены между узлами в программах, написанных на языке IBM X10 и анализировать эти данные.

1. ПОНЯТИЯ О ВС

1.1 Классификация ВС

программный параллельный вычислительная система

ВС классифицируют по различным признакам. Наиболее общей является классификация, предложенная в 1966 М. Дж. Флинном. В зависимости от числа обрабатываемых вычислительным средством потоков команд и данных, выделено четыре класса архитектур: SISD (Single Instruction stream / Single Data stream), SIMD (Single Instruction stream / Multiple Data stream), MISD (Multiple Instruction stream / Single Data stream), MIMD (Multiple Instruction stream / Multiple Data stream). Первый класс — SISD — относится к ЭВМ. Архитектуры MISD, SIMD, MIMD относятся к ВС. В соответствии с этими архитектурами допустимо построение нескольких типов ВС: 1) конвейерные ВС, 2) матричные ВС, 3) мультипроцессорные ВС, 4) распределенные ВС, 5) кластерные ВС, 6) пространственно-распределенные мультикластерные ВС.

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

Матричные ВС основываются на принципе массового параллелизма, в них обеспечивается возможность одновременной реализации большого числа операций на элементарных процессорах (ЭП), «объединенных» в матрицу. Каждый ЭП — композиция из арифметико-логического устройства (АЛУ) и локальной памяти (ЛП); последняя предназначается для хранения части данных. Поток команд на матрицу ЭП формируется устройством управления (следовательно, оно имеет в своём составе память для хранения программ обработки данных). Такие ВС имеют SIMD-архитектуру в классическом виде.

Мультипроцессорные ВС — обширная группа систем, в которую, в частности, могут быть включены конвейерные и матричные ВС. Однако принято к мультипроцессорным ВС относить системы с MIMD-архитектурой, которые состоят из множества (не связанных друг с другом) процессоров и общей (возможно и секционированной, модульной) памяти; взаимодействие между процессорами и памятью осуществляется через коммутатор (общую шину и т. п.), а между процессорами — через память.

Распределенные ВС — мультипроцессорные ВС с MIMD-архитектурой, в которых нет единого ресурса (общей памяти). Основные компоненты распределенной ВС (такие, как коммутатор, устройство управления, арифметико-логическое устройство или процессор, память) допускают представление в виде композиции из одинаковых элементов (локальных коммутаторов и устройств управления, локальных процессоров и модулей памяти).

Вычислительные системы с программируемой структурой полностью основываются на модели коллектива вычислителей и являются композицией взаимосвязанных элементарных машин. Каждая ЭМ в своем составе обязательно имеет локальный коммутатор (ЛК), процессор и память; может иметь также внешние устройства. Локальная память ЭМ предназначается для хранения части данных и ветви параллельной программы. Архитектура ВС с программируемой структурой относится к типу MIMD. Такие ВС по своим потенциальным архитектурным возможностям не уступают ни одному из перечисленных выше классов систем.

В вычислительных системах с программируемой структурой выделяют пространственно сосредоточенные и распределенные ВС. Характерной особенностью сосредоточенных ВС является компактное пространственное размещение средств обработки и хранения информации, при котором среднее время передачи слова между функциональными модулями (процессорами, модулями памяти, ЭВМ и др.) соизмеримо со средним временем выполнения одной операции в процессоре.

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

Концепция вычислительных систем с программируемой структурой была сформулирована в Сибирском отделении АН СССР, первая такая система («Минск-222») была построена в 1965 — 1966 гг.

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

Начало XXI в. ознаменовалось созданием пространственно-распределенных мультикластерных ВС как макроколлективов рассредоточенных кластеров, взаимодействующих между собой через локальные и глобальные сети (включая всемирную сеть Internet).

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

1.2 Распределенные ВС

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

1) параллельности функционирования сосредоточенных ВС (ЭМ в простейшем случае);

2) программируемости структуры (возможности автоматической настройки сети связи);

3) гомогенности состава (программной совместимости).

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

К структурам современных ВС предъявляется ряд требований.

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

2) Удобство адресации элементарных машин и «переноса» подсистем в пределах вычислительной системы. Вычислительная система должна предоставлять возможность пользователям создавать параллельные программы с виртуальными адресами ЭМ. Следовательно, структура ВС должна позволять реализовать простейший «механизм» преобразования виртуальных адресов ЭМ в реальные (физические) адреса машин системы. Необходимость организации одновременного решения нескольких задач на ВС (т.е необходимость разделения пространства элементарных машин между задачами) обосновывает требование простоты перемещения подсистем в пределах системы (при сохранении их топологических свойств).

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

4) Масштабируемость и большемасштабность структуры ВС. Для формирования конфигураций ВС с заданной эффективностью требуется, чтобы структура обладала способностью к наращиванию и сокращению числа вершин (машин). Изменение числа ЭМ в ВС не должно приводить к коренным перекоммутациям между машинами и (или) к необходимости изменения числа связей для любых ЭМ.

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

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

6) Живучесть структуры ВС. Важным требованием к ВС в целом является обеспечение работоспособности при отказе её компонентов или даже подсистем. Основой функциональной целостности ВС как коллектива элементарных машин является живучесть структуры. Под последним понимается способность структуры ВС обеспечить связность требуемого числа работоспособных ЭМ в системе при ненадёжных линиях межмашинных связей.

7) Технологичность структур ВС. Структура сети межмашинных связей ВС не должна предъявлять особых требований к элементной базе, к технологии изготовления микропроцессорных БИС. Системы должны быть восприимчивы к массовой технологии, их «вычислительное ядро» должно формироваться из массовых микропроцессорных БИС. Последнее позволит достичь приемлемых значений технико-экономических показателей ВС.

Структурные задержки при передачах информации между машинами ВС определяются расстоянием (в смысле теории графов) между вершинами структуры, сопоставленными взаимодействующим машинам [1, 3]. Для оценки структурных задержек в вычислительных системах используются диаметр и средний диаметр структуры. Диаметр есть максимальное расстояние, определённое на множестве кратчайших путей между парами вершин структуры ВС:

(2.1)

а средний диаметр ;

(2.2)

где — расстояние, т. е. минимальное число рёбер, образующих путь из вершины в вершину;; - число вершин, находящихся на расстоянии от любой выделенной вершины (однородного) графа .

Показателем оценивающим структурную коммутируемость ВС, является вектор-функция

, (2.3)

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

Структурная живучесть ВС оценивается вектор-функцией

, (2.4)

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

Наиболее полно перечисленным выше требованиям удовлетворяют однородные структуры (т.е. описываемые однородными графами) [1, 3]. Такие структуры являются перспективными для формирования масштабируемых и большемасштабных вычислительных систем (в частности, ВС с программируемой структурой).

В компьютерной индустрии получили распространение n-мерные структуры вычислительных систем, известные сейчас как циркулянтные (Circulant Sructures). Впервые они были определены и исследованы в Отделе вычислительных систем Института математики СО АН СССР в начале 70-х годов и первоначально назывались _графами. По определению —граф или циркулянтная структура есть граф вида:, в котором:

— число вершин или порядок графа;

вершины помечены целыми числами по модулю, следовательно,

вершина соединена ребром (или является смежной) с вершинами

— множество целых чисел, называемых образующими, таких, что, а для чисел наибольшим общим делителем является 1;

— размерность графа;

2n — степень вершины в графе.

В качестве примера рассмотримграф или двумерный циркулянт вида:, который изображен на рисунке 2.1.

Рисунок 2.1 —граф:

Графы вида, т. е. -графы или циркулянты с единичной образующей (Loop Networks — петлевые структуры) интенсивно изучаются в последнее время. Циркулянтные структуры широко внедрены в практику вычислительных систем.

Целые числа отмечающие вершиныграфа, называют адресами. Адресация вершин в таких структурах называется диофантовой (в честь древнегреческого математика из Александрии Диофанта, Diophantos, 3 век). В циркулянтных структурах при полном переносе какой-либо подструктуры (всех вершин подструктуры на одно и то же расстояние в одном из направлений) сохраняются все её свойства и адресация вершин. Следовательно, при диофантовой адресации элементарных машин ВС можно простыми средствами реконфигурации осуществить виртуальную адресацию вершин-машин и, следовательно, создавать отказоустойчивые параллельные программы, реализовывать мультипрограммные режимы обработки информации, исключать отказавшие вершины-машины из подсистем, а значит обеспечить живучесть ВС.

При этом алгоритм работы реконфигуратора структуры ВС сводится к изменению адресов у всех машин подсистемы по формуле:

, (2.5)

где i — номер ЭМ, исключаемой из подсистемы, а j — номер машины, включаемый в подсистему,

В качестве структур ВС, допускающих масштабирование (изменение числа машин) без коренной перекоммутации уже имеющихся межмашинных связей, используютсяграфы (введённые также в Отделе вычислительных систем ИМ СО АН СССР). В такие графы вкладываютсяграфы; -граф — это неориентированный однородный граф с числом и степенями вершин, соответственно, и v и значением обхвата g. Примеры изображены на рисунке 2.2.

Вграфах каждая вершина при входит в не менее v кратчайших простых циклов длиной (длина кратчайшего цикл в графе называется обхватом). Приграф является простым циклом с вершинами.

а б

а — б ;

Рисунок 2.2 — Фрагментыграфов В зависимости от сложности задач и характера их поступления в теории вычислительных систем выделяют два основные режима функционирования ВС с программируемой структурой [1, 3]: монои мультипрограммный режимы.

В монопрограммном режиме для решения задачи используются все ресурсы ВС. Задача представляется в виде параллельной программы, число ветвей в которой либо фиксировано, либо допускает варьирование в заданном диапазоне. В качестве единицы ресурса выступает элементарная машина ВС. Все машины используются для решения задачи. Если максимальное число ветвей в параллельной программе менее общего числа ЭМ в системе, то «избыточные» машины используются для повышения надёжности функционирования ВС.

К мультипрограммным относят режимы [1, 3]:

1) обработки наборов задач;

2) обслуживания потоков задач.

При работе ВС в этих режимах одновременно решается несколько задач, следовательно, ресурсы системы делятся между ним.

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

Обслуживание потока задач на ВС — принципиально отличается от обработки наборов: задачи поступают в случайные моменты времени, их параметры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключён. Для режима потока задач применяются методы и алгоритмы [3], обеспечивающие стохастически оптимальное функционирование вычислительных систем.

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

1.3 Параллельные алгоритмы и программы

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

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

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

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

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

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

Пусть — количество операций, которые необходимо выполнить при решении задачи на ВС; n — число параллельных ветвей или число вычислителей, на которых решается задача,; Тогда задачу, для которой выполняется условие

(2.6)

будем называть сложной, или системной, или трудоемкой, или с большим объемом вычислений.

В соотношении (2.6) — эмпирический коэффициент,. Очевидно, что имеет место зависимость от быстродействия каналов связей между вычислителями: при, где — время обращения к локальной памяти в вычислителе.

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

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

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

Параллельная программа решения сложной задачи допускает представление в виде композиции: в которой естья ветвь программы, -допустимое число ветвей.

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

Анализалгоритмов ипрограмм показал, что многообразие встречающихся в них схем обмена информацией между ветвями сводится к пяти типам: дифференцированному (ДО), трансляционному (ТО), трансляционно-циклическому (ТЦО), конвейерно-параллельному (КПО) и коллекторному обменам (КО).

При трансляционном обмене (one-to-all broadcast) (рисунок 1.4 слева) осуществляется передача одной и той же информации из одной (любой) ветви одновременно во все остальные ветви параллельного алгоритма.

Трансляционно-циклический обмен реализует трансляцию информации из каждой ветви во все остальные. Следовательно, если трансляционный обмен выполняется за 1 такт, то трансляционно-циклический — за тактов.

Конвейерно-параллельный обмен (all-to-all broadcast) обеспечивает передачу информации между соседними ветвями; он реализуется за два такта (рис. 1.5). Так, например, при четном в первом такте осуществляется передача информации из ветвей соответственно в ветви; во втором такте информация из последней последовательности ветвей поступает соответственно в ветви .

Коллекторный обмен — это по сути инвертированный трансляционный обмен (рис. 2.4. справа): т. е. вычислители, которые были приемниками, превращаются в передатчики и наоборот вычислитель-передатчик становится приемником. Вообще при коллекторном обмене в одну ветвь последовательно собирается информация из ветвей; такой обмен требует тактов и реализуется как последовательность из дифференцированных обменов.

Рисунок 2.4 — Трансляционный обмен (слева) и коллекторный обмен (справа) Рисунок 2.5 — Конвейерно-параллельный обмен

1.4 Модели параллельных вычислений PGAS и APGAS

Модель параллельных вычислений PGAS

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

Широкое применение в прикладном параллельном программировании получили две основные модели: MPI — стандарт программирования на ВС с архитектурой распределенной памяти и OpenMP — стандарт программирования на ВС с архитектурой общей памяти.

Однако «чистые» OpenMP-программы не могут крупно масштабироваться на современном поколении суперкомпьютеров, поскольку ни одна из крупномасштабных HPC-систем не имеет архитектуры исключительно с общей памятью. С повсеместным появлением и распространением многоядерных архитектур значительно возрастает актуальность программной модели MPI&OpenMP.

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

Новой концепцией параллельного программирования, вызвавшей широкий интерес, стала модель PGAS (Partitioned Global Address Space) — модель распределенного глобального адресного пространства, суть которой в дуальной концепции глобального адресного пространства и локального адресного пространства. В данной модели семантика распределенной памяти встроена в определение языка, что позволяет использовать систему языковых типов наряду со способностью компилятора оптимизировать передачу данных одновременно с последовательным кодом.

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

Графическое изображение модели PGAS представлено на рисунке 2.6.

Рисунок 2.6 Модель PGAS

Программная модель PGAS предоставляет две основных возможности, а именно разбиение данных на различие между локальными и удаленными данными, обе из которых используются для минимизации издержек на коммуникации извлечения наилучшей производительности. Производительность алгоритма, основанного на использовании PGAS, зависит от дисциплины доступа к глобальному адресному пространству. Несколько процессов могут работать независимо по образцу Single Program Multiple Data (SPMD) — «одна программа много данных». Процессы могут взаимодействовать через глобальную память и иметь доступ к общим данным, в то время как обращение к личным данным могут выполняться только их собственным потоком.

Языки модели PGAS спроектированы так, чтобы реализации могли генерировать односторонние обмены, в которых один процесс читает или пишет по адресу, связанному с удаленной единицей данных. Эта возможность обеспечивается за счет использования механизма GASNet (Global Address Space Networking), предоставляющего языково-независимый низкоуровневый интерфейс сетевого взаимодействия посредством высокопроизводительных коммуникационных примитивов.

Основные характеристики программной модели PGAS:

— выполняется в режиме SPMD;

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

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

— использует более быстрые односторонние коммуникации в противоположность двусторонним коммуникациям MPI;

— глобальное адресное пространство поддерживает построение сложных общих структур данных;

— высокоуровневые конструкции;

— переносимость.

PGAS-модель является основой для Unified Parallel C, Co-array Fortran, Titanium, Fortress, Chapel и X10.

Модель параллельных вычислений APGAS

Модель параллельного программирования APGAS (Asynchronous Partitioned Global Address Space) — является расширением модели PGAS, двумя простыми концепциями: places и asyncs. В этой модели реализовано динамическое управление параллельными задачами — процессы могут порождать дочерние процессы, задачи распределяются между процессами динамически (Work-stealing scheduler).

1.5 Язык IBM X10

X10 — новый язык программирования на основе Java, разработанный корпорацией IBM в исследовательском центре имени Томаса Уотсона как часть проекта PERCS, спонсируемого в рамках программы Высокопродуктивные компьютерные системы (High Productivity Computing Systems или сокр. HPCS) Агентства по перспективным оборонным научно-исследовательским разработкам США. Первыми авторами стали Кемаль Эбсиоглу, Вияй Сарасват и Вивек Саркар.

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

Основная цель разработки языка — обеспечение возможности разработки параллельных программ для вычислительных систем петафлопной производительности вплоть до с 10⁶ процессорами (ядрами).

Для языка IBM X10 применимы следующие понятия: place (область) и activity (активность).

Для представления отдельного вычислительного узла высокопроизводительной системы, используемой для выполнения Х10-программы, в IBM Х10 используется понятие place (область).

Область может рассматриваться как некоторая абстракция мультипроцессора с общей памятью (SMP-узла). Количество областей, как правило, соответствует числу имеющихся процессоров; в общем же случае, количество исполнителей может отличаться от числа процессоров. Количество созданных областей может быть определено при помощи значения place. MAX_PLACES. Каждая область характеризуется своим уникальным индексом от 0 до place. MAX_PLACES-1.

Выполняемая последовательность действий в X10-программе определяется как активность (activity).

Активность может рассматриваться как командный поток, выполняемый исполнителем. На одном исполнителе могут выполняться одновременно несколько активностей. Исполнитель, на котором выполняется активность, может быть определен при помощи переменной here. Активность может порождать другие — дочерние (child) — активности. Функция main является начальной — корневой (root) — активностью.

В листинге 2.1 показан пример того, как можно породить активность.

В результате в области создастся дочерняя активность, которая будет выполнять следующий описанный. Создание активности осуществляется асинхронно; базовая активность продолжает выполнение (не блокируется). Дочерняя активность может иметь доступ к локальной памяти области и к переменным, определенных как final.

Листинг 2.1 — Пример создания активностей при помощи async

// global dist. Array

final double a[D] = …;

final int k = …;

async (a.distribution[99]) {

// executed at A[99]'s place

atomic a[99] = k;

}

Директива finish ожидает завершение дочерних активностей, порожденных в блоке S. На листинге 2.2 продемонстрирован пример использования директивы finish

Листинг 2.2 — Пример использования директивы finish

def start (data) {

val a = new Calc ();

val b = new Calc ();

finish {

async a. run ();

async b. run ();

}

}

В языке IMB X10 можно создавать критические секции при помощи директива atomic. В листинге 2.3 показан пример использования директивы atomic.

Листинг 2.3 — Пример использования директивы atomic

def add (x: T) {

atomic {

this.list.add (x);

this.size++;

}

}

Директива at позволяет явно задать существующую область P, в которой будет выполняться блок S.

Новая активность в области P не создается, туда передается выполнение текущей активности. После завершения блока S выполнение потока переносится в начальную область.

Операция at требует копирования в область P данных используемых блоком S — в области P создаются их локальные копии.

В листинге 2.4 представлен пример использования директивы at.

Листинг 2.4 — Пример использования директивы at

public static def main (Array[String](1)) {

val a = [1, 2, 3];

at (here.next ()) {

a (1) = 4;

Console.OUT.println (here.id + «» + a);

}

Console.OUT.println (here.id + «» + a);

}

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

Листинг 2.5 — Пример создания таймера

clock c = Clock. make ();

IBM X10 сравнительно молодой язык программирования, многое не документировано, многое не работает, тем не менее язык развивается, регулярно выходят обновления. На текущий момент для скачивания доступна версия 2.3.1.

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

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

Существует эвристический закон «20/80», утверждающий, что приложение проводит 80% времени работы в 20% кода. Таким образом, за счет оптимизации именно этих 20% кода можно добиться значительного повышения производительности.

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

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

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

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

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

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

2. ПАКЕТ ДЛЯ ПРОФИЛИРОВАНИЯ ПРОГРАММ НА ЯЗЫКЕ IBM X10

2.1 Функциональная структура пакета

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

Структура пакета профилирования программм на языке IBM X10 представлена на рисунке 3.1.

Рисунок 3.1 — Структура пакета профилирования программм на языке IBM X10

2.2 Описание модулей пакета

В IBM X10 многоуровневая система передачи информационных обменов между узлами. Перехват обменов осуществляется на «верхнем» уровне — на уровне языка IBM X10.

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

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

По завершению работы программы и, как следствие, профилировщика, файлы будут закрыты. Пример содержимого файлов представлен в таблице 3.1

Таблица 3.1 — Пример содержимого файлов, с результатами перехваченных информационных обменов

В примере видно, что вычислительный узел 0 принял вначале 24, затем 14 байт, вычислительный узел 1 — 100 и 0 байт.

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

Листинг 3.1 — создание промежуточных файлов и их заполнение перехваченной информацией

FILE *stream[64];

int NEED_CREATE_FILES = 1;

void x10rt_lgl_send_msg (x10rt_msg_params *p)

{

int i;

char file_name[30];

…

if (NEED_CREATE_FILES == 1) {

for (i = 0; i < x10rt_lgl_nhosts (); i++) {

sprintf (file_name, «temp_rep_%d», i);

stream[i] = fopen (file_name, «a»);

}

NEED_CREATE_FILES = 0;

}

fprintf (stream[p->dest_place], «%dn», p->len);

…

}

Обработчик считывает содержимое файлов, сгенерированных модулем перехвата, содержащих результаты перехваченных информационных обменов и, складывая содержимое соответствующих файлов, формирует финальный выходной файл report, куда записывает общее количество принятой информации вычислительным узлом, в виде Place N received X bytes, где N — номер узла-получателя информации, Х — количество байт информации, которое принял вычислительный узел. Исходный код модуля обработки промежуточных результатов представлен в листинге 3.2.

Пример содержимого файла report:

Place 0 received 48 bytes

Place 1 received 100 bytes

Листинг 3.2 — модуль обработки промежуточных результатов

#include

#include

#include

#define NUM_POINT 16

int main (int argc, char *argv[])

{

FILE *stream;

char file_name[30];

int i, j, len;

int *point;

point = (int *) malloc (sizeof (int) * NUM_POINT);

i = 0;

while (1) {

sprintf (file_name, «temp_rep_%d», i);

stream = fopen (file_name, «r»);

if (stream == 0)

break;

point[i] = 0;

while (1) {

fscanf (stream," %d", &len);

if (feof (stream))

break;

point[i] += len;

}

i++;

fclose (stream);

}

stream = fopen («report», «a»);

for (j = 0; j < i; j++)

fprintf (stream, «Place %d received %d bytesn», j, point[j]);

fclose (stream);

return 0;

}

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

2.3 Организация экспериментов

Экспериментальные исследования проводились на вычислительном кластере (Jet) Центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ».

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

Узлы построены на базе серверной платформы Intel SR2520SAF. На каждом узле размещено два процессора Intel Quad Xeon E5420 с тактовой частотой 2.5 GHz. Пиковая производительность кластера — 1,44 TFLOP. В таблице 3.3 приведена конфигурация управляющего узла. В таблице 3.4 представлена конфигурация коммуникационной среды.

Таблица 3.2 — Конфигурация вычислительного узла

Таблица 3.3 — Конфигурация управляющего узла

Таблица 3.4 — Конфигурация коммуникационной среды

Кластер размещен в 19'' телекоммуникационном шкафу AESP Black Premium 48U. Система бесперебойного электропитания имеет мощность 12kVA и построена на базе источников бесперебойного питания APC Smart-UPS XL Modular 3000VA (SUM3000RMXLI2U).