Сравнительный анализ эффективности инструментария MPI и NET для задачи суммирования

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

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

"Тверской государственный технический университет"

Курсовая работа

по дисциплине "Параллельные вычисления и многопоточное программирование"

на тему: "Сравнительный анализ эффективности инструментария mpi и net для задачи суммирования"

Выполнил:

Студент 5-го курса

Группы ПОВТ 0906

Белков Е.И.

Принял:

Биллиг В. А.

Тверь 2013

Содержание

Введение

1. Проблема распараллеливания в Инструментарии.NET

2. Суммирование в инструментарии .net

3. Средство анализа эффективности MPI программ

3.1 Постановка задачи

3.2 Этапы работы анализатора

3.3 Устройство анализатора

3.3.1 Сбор трассы

3.3.2 Анализ

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

4.Задача суммирования на MPI

Заключение



Введение

параллельный компьютер анализатор программа

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

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

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

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

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

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

Эффективность выполнения параллельных программ на многопроцессорных ЭВМ с распределенной памятью определяется следующими основными факторами:

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

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

· временем, необходимым для выполнения межпроцессорных обменов;

· степенью совмещения межпроцессорных обменов с вычислениями;

· эффективностью выполнения вычислений на каждом процессоре (а она может варьироваться значительно в зависимости от степени использования кэша).

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



1. Проблема распараллеливания в Инструментарии.net

Исторически сложилось так, что для создания «отзывчивых» клиентских приложений, масштабируемых серверов и для распараллеливания алгоритмов разработчики напрямую манипулировали потоками. Но это же вело к взаимоблокировкам (deadlocks), активным блокировкам (livelocks), очередям на блокировках (lock convoys), «топтанию потоков на месте» (two-step dances), конкуренции за блокировки (race conditions), превышению лимита (oversubscription) и уйме других нежелательных проблем в приложениях. С самого начала Microsoft .NET Framework предоставляла мириады низкоуровневых средств для создания параллельных приложений, в том числе целое пространство имен, специально выделенное для этой области: System.Threading. При наличии примерно 50 типов в этом пространстве имен в базовых сборках .NET Framework 3.5 (включая такие типы, как Thread, ThreadPool, Timer, Monitor, ManualResetEvent, ReaderWriterLock и Interlocked) никто не должен был бы винить .NET Framework в легковесном отношении к поддержке потоков. И тем не менее я обвиняю предыдущие версии .NET Framework в таком отношении к реальной поддержке разработчиков, которым нужно было создавать масштабируемые приложения с высокой степенью распараллеливания. С радостью констатирую, что эта проблема устранена в .NET Framework 4 и что в будущих версиях .NET Framework будет внесено много усовершенствований в этой области.

Некоторые могут усомниться в ценности богатой подсистемы в управляемом языке для написания параллельного кода. В конце концов, параллелизм и параллельная обработка сводятся к вопросам производительности, а разработчики, заинтересованные в максимальном быстродействии, должны искать его в неуправляемых языках, которые обеспечивают полный доступ к «железу» и контроль над каждым битом, позволяют манипулировать кеш-линиями и выполнять interlocked-операции…, правильно? Если бы дело и впрямь обстояло таким образом, я бы испугался за состояние нашей индустрии. Существуют управляемые языки вроде C#, Visual Basic и F#, которые предоставляют всем разработчикам -- и простым смертным, и супергероям -- безопасную, производительную среду для быстрого написания эффективного кода. Разработчикам даются тысячи и тысячи заранее скомпилированных библиотечных классов наряду с языками, напичканными всеми современными сервисами и позволяющими достигать впечатляющих показателей производительности. Все это я говорю, чтобы подчеркнуть, что управляемые языки и связанные с ними инфраструктуры имеют глубокую поддержку для создания высокопроизводительных параллельных приложений, благодаря которой и волки сыты, и овцы целы -- даже на современном аппаратном обеспечении.

Я всегда считал, что шаблоны -- хороший способ чему-то научиться, поэтому для данной тематики будет тем более правильно, если мы начнем наше исследование с рассмотрения какого-то шаблона. И для «сбивающего с толку», и для «восхитительно» параллельного шаблона одна из наиболее востребованных конструкций разветвления-соединения (fork-join) -- параллельный цикл, который предназначен для обработки каждой независимой итерации в цикле параллельно. Очень поучительно посмотреть, как такая обработка могла бы выполняться с использованием ранее упомянутых низкоуровневых примитивов, и для этого мы подробно обсудим базовую реализацию наивного параллельного цикла, реализованного на C#. Возьмем типичный цикл for:

1. for (int i=0; i<N; i++) {

2.   ... // здесь обрабатывается i

3. }

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

1. int lowerBound = 0, upperBound = N;

2. int numThreads = Environment.ProcessorCount;

3. int chunkSize = (upperBound - lowerBound) / numThreads;

4.  

5. var threads = new Thread[numThreads];

6. for (int t = 0; t < threads.Length; t++) {

7.   int start = (chunkSize * t) + lowerBound;

8.   int end = t < threads.Length - 1 ? start +

9.     chunkSize : upperBound;

10.   threads[t] = new Thread(delegate() {

11.     for (int i = start; i < end; i++) {

12.       ... // здесь обрабатываем i

13.     }

14.   });

15. }

16.  

17. foreach (Thread t in threads) t.Start(); // fork

18. foreach (Thread t in threads) t.Join();  // join

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

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



2. Суммирование в Инструментарии.net

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

Основные классы для реализации многопоточных приложений определены в пространстве имен System.Threading. Для описания собственных потоков предназначен класс Thread. При создании потока ему необходимо указать делегата, реализующего процедуру потока. К сожалению, в .NET, во-первых, не предусмотрено передачи аргументов в эту процедуру, во-вторых, процедура должна быть статическим методом, и в-третьих, класс Thread является опечатанным. В результате передача каких-либо данных в процедуру потока вызывает определенные трудности и требует явного или косвенного использования статических полей, что не слишком удобно, зачастую нуждается в дополнительной синхронизации и плохо соответствует парадигме ООП.

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

using System;

using System.Threading;

namespace TestNamespace {

class TestApp {

const int m_size = 600;

const int m_stripsize = 50;

const int m_stripmax = 12;

private static int m_stripused = 0;

private static double[,] m_A = new double[m_size,m_size],

m_B = new double[m_size,m_size],

m_C = new double[m_size,m_size];

public static void ThreadProc()

{

int i,j,k, from, to;

from = ( m_stripused++ ) * m_stripsize;

to = from + m_stripsize;

if ( to > m_size ) to = m_size;

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

for ( j = 0; j < m_size; j++ ) {

for ( k = from; k < to; k++ )

m_C[i,j] += m_A[i,k] * m_B[k,j];

}

}

}

public static void Main()

{

Thread[] T = new Thread[ m_stripmax ];

int i,j,errs;

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

for ( j = 0; j < m_size; j++ ) {

m_A[i,j] = m_B[i,j] = 1.0;

m_C[i,j] = 0.0;

}

}

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

T[i] = new Thread(new ThreadStart(ThreadProc));

T[i].Start();

}

// дожидаемся завершения всех потоков

for ( i = 0; i < m_stripmax; i++ ) T[i].Join();

// проверяем результат

errs = 0;

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

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

if ( m_C[i,j] != m_size ) errs++;

Console.WriteLine("Error count = {0}", errs );

}

}

}

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



Рис. 1. Состояния потока

Сразу после создания и до начала выполнения потока он находится в незапущенном состоянии ( Unstarted ). Текущее состояние можно определить с помощью свойства Thread.ThreadState. После запуска поток можно перевести в состояние исполнения ( Running ) вызовом метода Thread.Start. Работающий поток может быть переведен в состояние ожидания (WaitSleepJoin ) явным или неявным вызовом соответствующих методов ( Thread.Sleep, Thread.Join и др.) или приостановлен ( Suspended ) с помощью метода Thread.Suspend(). Исполнение приостановленного потока можно возобновить вызовом метода Thread.Resume. Также можно досрочно вывести поток из состояния ожидания вызовом метода Thread.Interrupt.

Завершение функции потока нормальным образом переводит поток в состояние "завершен" ( Stopped ), а досрочное прекращение работы вызовом метода Thread.Abort переведет его в состояние "прерван" ( Aborted ). Кроме того, .NET поддерживает несколько переходных состояний ( AbortRequested, StopRequested и SuspendRequested ). Состояния потока в общем случае могут комбинироваться, например, вполне корректно сочетание состояния ожидания ( WaitSleepJoin ) и какого-либо переходного, скажем, AbortRequested.

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

Для получения и задания приоритета потока используется свойство Thread.Priority. Приоритеты потока в .NET базируются на подмножестве относительных приоритетов Win32 API так, что при переносе на другие платформы существует возможность предоставить их корректные аналоги. В .NET используются приоритеты Highest, AboveNormal, Normal, BelowNormal и Lowest.

Когда .NET приложение начинает исполняться в среде Windows, CLR создает внутренний пул потоков, используемый средой для реализации асинхронных операций ввода-вывода, вызова асинхронных процедур, обработки таймеров и других целей. Потоки могут добавляться в пул по мере надобности. Этот пул реализуется на основе пула потоков, управляемого операционной системой (построенного на основе порта завершения ввода-вывода). Для взаимодействия с пулом потоков предусмотрен класс ThreadPool, и единственный объект, принадлежащий этому классу, создается CLR при запуске приложения. Все домены приложений в рамках одного процесса используют общий пул потоков.

Разработчики могут использовать несколько статических методов класса ThreadPool. Так, например, существует возможность связать внутренний порт завершения ввода-вывода с файловым объектом, созданным неуправляемым кодом, для обработки событий, связанных с завершением ввода-вывода этим объектом (см. методы ThreadPool.BindHandle и описание порта завершения ввода-вывода ранее). Можно управлять числом потоков в пуле (методы GetAvailableThreads, GetMaxThreads, GetMinThreads и SetMinThreads), можно ставить в очередь асинхронных вызовов собственные процедуры (методQueueUserWorkItem) и назначать процедуры, которые будут вызываться при освобождении какого-либо объекта (методRegisterWaitForSingleObject ). Эти два метода имеют "безопасные" и "небезопасные" ( Unsafe...) версии; последние отличаются тем, что в стеке вызовов асинхронных методов не будут присутствовать данные о реальном контексте безопасностипотока, поставившего в очередь этот вызов, - в подобном случае будет использоваться контекст безопасности самого пула потоков.

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

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

первая считает общее количество бит в большом массиве данных в памяти

вторая читает данные из сетевого протокола, и пишет на диск

третья шифрует небольшое значение с помощью AES-256

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

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

Пакетная обработка.

У вас есть N элементов, с которыми необходимо выполнить некую операцию, причём все элементы не хранятся в памяти - у вас есть некий поставщик элементов. Элементов много, поэтому лучше было бы сделать это параллельно. Одна операция над элементом занимает F секунд, а синхронизация потоков для добавления элемента в очередь обработки занимает S секунд. Представьте, что F соизмеримо с S, или хуже того S больше F. В итоге, тот поток, который добавляет элементы в очередь обработки других потоков, тратит столько же времени (или больше) на синхронизацию потоков, сколько и само время обработки элементов (N x F <= N x S). Оптимизацией это не назовёшь, поэтому вы можете на этом остановиться и решить, что в распараллеливании нет никакого смысла.

Если объединить K элементов в «пакет», и ставить в очередь обработки не элементы, а пакеты, то вам не нужно будет так часто синхронизировать потоки, и общее время синхронизации уменьшится в K раз. Сделайте пакет в 1000 элементов, и оно пропорционально уменьшится в 1000 раз. Неплохо, да? Скажем, у вашего процессора 16 ядер, и в идеальном случае вы хотите снизить время обработки всех элементов до N x F / 16. А если F соизмеримо с S, то вы получите неравенство N x F / 16 > N x S / 1000. Т.е. теперь общее время синхронизации намного меньше, чем обработка элементов одним из 16 потоков. Для примера реализации приведу псевдокод:

Пример кода

void DoWork(ItemProvider provider)

{

Batch batch = NextFreeBatch();

while (true)

{

Item item = provider.GetNextItem();

batch.AddItem(item);

if (batch.IsFull)

{

EnqueueBatchForAsyncProcessing(batch);

batch = NextFreeBatch();

}

}

}

void EnqueueBatchForAsyncProcessing(Batch batch)

{

lock (this.batchQueue)

this.batchQueue.Enqueue(batch);

}

void ThreadRoutine()

{

while (true)

{

Batch batch = DequeueBatchForAsyncProcessing();

foreach (Item item in batch)

ProcessItem(item);

RecycleBatch(batch);

}

}

Batch DequeueBatchForAsyncProcessing()

{

lock (this.batchQueue)

return this.batchQueue.Dequeue();

}

Предупреждаю, код - нерабочий и содержит массу недочётов. Я специально сделал его максимально простым, чтобы просто пояснить суть принципа.

Переключение контекста.

Вы знаете, почему потоки могут работать «параллельно» даже, если у процессора всего одно ядро? Каждая программа имеет изолированную от других память (виртуальная память), но все они используют одни и те же регистры процессора для выполнения инструкций. Чтобы дать возможность использования регистров процессора «параллельно», придумали технику переключения контекста - сохранение состояния регистров в оперативную память при остановке выполнения программы, чтобы можно было их позже восстановить для продолжения выполнения. Т.е. система выполняет часть инструкций одной программы, сохраняет её состояние, потом загружает состояние другой программы, выполняет немного её инструкций, потом опять сохраняет состояние, и так далее. Таким образом, система много раз в секунду переключается с программы на программу, что даёт эффект «параллельности выполнения».

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

Во избежание переключения контекста, можно привязать потоки к конкретным физическим ядрам/процессорам. Для процессов есть свойство Process.ProcessorAffinity (общая маска для всех потоков процесса), а для потоков можно использовать ProcessThread.ProcessorAffinity.

Для контроля выделения времени выполнения потоков есть приоритет - свойство Thread.Priority. Чем больше приоритет, тем больше выделяется процессорного времени на выполнение инструкций. Также есть приоритет у процессов в системе -Process.PriorityClass.



3. Средство анализа эффективности MPI программ

3.1 Постановка задачи

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

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

Целью данной дипломной работы является создание экспериментальной системы отладки эффективности MPI-программ.

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

3.2 Этапы работы анализатора

В работе анализатора можно выделить следующие этапы.

Этап 1

Обработка трасс со всех процессоров и вычисление для каждого интервала и каждого процессора следующих характеристик:

Основные характеристики и их компоненты

Коэффициент эффективности (Parallelization efficiency) равен отношению полезного времени к общему времени использования процессоров.

Время выполнения (Execution time).

Число используемых процессоров (Processors).

Общее время использования процессоров (Total time) - произведение времени выполнения (Execution time) на число используемых процессоров (Processors).

Полезное время (Productive time) - прогнозируемое время выполнения на одном процессоре

Потерянное время (Lost time).

Коммуникации (Communication) и все компоненты.

Простои (Idle time).

Разбалансировка (Load_Imbalance).

Потенциальные потери из-за синхронизации (Synchronization) и все компоненты.

Потенциальные потери из-за разброса времен (Time_variation) и все компоненты.

Характеристики выполнения программы на каждом процессоре

Потерянное время (Lost time) - сумма его составляющих - потерь из-за недостаточного параллелизма (User insufficient_par), системных потерь из-за недостаточного параллелизма (Sys insufficient_par), коммуникаций (Communication) и простоев (Idle time).

Простои на данном процессоре (Idle time) - разность между максимальным временем выполнения интервала (на каком-то процессоре) и временем его выполнения на данном процессоре.

Общее время коммуникаций (Communication).

Реальные потери из-за рассинхронизации (Real synchronization).

Потенциальные потери из-за разброса времен (Variation).

Разбалансировка (Load_imbalance) вычисляется как разность между максимальным процессорным временем (CPU+MPI) и соответствующим временем на данном процессоре.

Время выполнения интервала (Execution_time).

Полезное процессорное время (User CPU_time).

Полезное системное время (MPI time).

Число используемых процессоров для данного интервала (Processors).

Времена коммуникаций для всех типов коллективных операций

Реальные потери из-за рассинхронизации для всех типов коллективных операций.

Потенциальные потери из-за рассинхронизации для всех типов коллективных операций.

Потенциальные потери из-за разброса времен для всех типов коллективных операций.

Этап 2

Подготовка текстового представления вычисленных характеристик. Такое представление упрощает первоначальный анализ характеристик при запуске параллельной программы на удаленной ЭВМ.

Этап 3

Визуализация результатов анализа эффективности.

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

3.3 Устройство анализатора

Итак, анализатор состоит из трех основных компонент.

Первая - сбор информации по трассе. Вторая - анализ собранных данных. Третья - визуализация.

3.3.1 Сбор трассы

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

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

3.3.2 Анализ

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

Корнем дерева будет вся программа, она считается интервалом нулевого уровня.

Далее в соответствии с вложенностью интервалы первого уровня и т.д.

Как указать границы интервалов?

Для этого используются пара функций MPI_Send() и MPI_Recv() для указания начала интервала, и такая же пара для указания его окончания.

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

TAG = 0x(aa)(id)(aa/bb).

Тэг является четырехбайтным целым числом. Первый байт у «нашего» тэга - это 0xaa. Это позволяет отличить его от обычных посылок/приемов сообщений. Последний байт может быть 0xaa - символизирует начало интервала, 0xbb - конец интервала. Внутри специальный идентификатор интервала (2 байта), его можно использовать, например, для того, чтобы отдельно выделить итерации цикла.

Такой способ выделения был выбран потому, что:

· он всегда попадает в трассировку (некоторые специальные функции вроде MPI_Pcontrol() в текущей версии трассировщика не попадают).

· занимает относительно немного времени (порядка 100 тиков процессора).

· прост в использовании и не требует дополнительных средств, помимо стандартных MPI-функций.

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

Далее по этим тэгам среди всех событий будут найдены те, которые являются границами интервалов и будут определены их идентификаторы.

Для этого вводится специальный класс:

class Margin

{

public:

Margin(bool ,unsigned long ,int ,unsigned int ,int);

friend bool operator <( const Margin& s1, const Margin& s2)

bool enter_leave;

unsigned long time;

int identity;

unsigned int proc;

unsigned int scl;

};

И функция:

vector<Margin>* createMargins(void);

которая и вычисляет=> определяет необходимые границы вместе со всеми параметрами. После определения границ, создается структура дерево, в которой хранятся все данные обо всех интервалах.

Кратко об используемых структурах данных.

Создан специальный класс tree:

class tree

{

public:

static int Intervallevel; // current interval level

static int IntervalID; // current interval ID

long index;

int level; // Interval level

int EXE_count;

int source_line;

string source_file;

int ID;

//Characteristics for every interval

unsigned long Exec_time;

unsigned long Productive_time;

double Efficiency;

unsigned long CPU_time;

unsigned long MPI_time;

unsigned long Lost_time;

unsigned long Comm_time;

unsigned long SendRecv_time;

unsigned long CollectiveAll_time;

unsigned long Idle_time;

unsigned long AllToAll_time;

unsigned long Time_variation;

unsigned long Potent_sync;

unsigned long T_start;

vector < pair<unsigned long,unsigned int> >* cmp_pairs;

//for intelval's tree

tree* parent_interval;

int count;

vector<tree *> nested_intervals;

vector<Processors> Procs;

};

Этот класс содержит информацию обо всех характеристиках данного интервала, описанных в 5.2. Кроме того, в нем есть информация о родительском узле дерева, а также обо всех «листьях-потомках».

В этом классе в качестве вспомогательного используется класс Processors.

class Processors

{

public:

unsigned long enter_time;

unsigned long leave_time;

unsigned int number;

unsigned long MPI_time;

unsigned long SendRecv_time;

unsigned long CollectiveAll_time;

unsigned long Idle_time;

unsigned long AllToAll_time;

unsigned long CPU_time;

unsigned long Comm_time;

unsigned long Time_variation;

unsigned long Potent_sync;

unsigned long T_start;

};

В этом классе содержатся элементарные составляющие всех компонентов, собранные на каждом интервале каждого процессора.

Далее, после определения границ интервалов, происходит создание дерева интервалов.

В этом дереве и будет храниться информация обо всех интервалах.

Класс tree включает методы, которые и собирают информацию из структур, собранных на трассе.

Первая группа характеристик собирается в функции

Leave(int line, char* file, long index,unsigned int proc,unsigned long time).

· MPI_time Используем - getMPITimebyProc();

· SendRecv_time - getSendRecvCommunicationTimebyProc();

· CollectiveAll_time - getCollectiveAllByProc();

· AllToAll_time - getAllToAllByProc();

· Potent_sync - getPotentSyncByProc();

· Time_variation - getTimeVariationByProc();

· T_start - getNonBlockedTimebyProc();

Вычисление характеристик.

getMPITimebyProc() - Происходит суммирование интервалов времени, занятых под MPI-функции (интервалы получаются как разность между временем выхода и входа в MPI-функцию).

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

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

getTimeVariationByProc() - Вычисляется время, рассинхронизации окончания коллективной операции.

getNonBlockedTimebyProc() - Вычисляется аналогично getMPITimebyProc(), только суммируются времена работы только не блокирующих операций.

Все эти характеристики собираются на каждом процессоре для данного интервала. Прототип всех функций одинаков:

getFunction(unsigned long enter_time, unsigned long leave_time, unsigned int proc).

Собранные «элементарные» характеристики, затем собираются в более общие по всему интервалу.

Первая используемая для этого функция - это функция Integrate().

В этой функции собираются следующие характеристики:

· CPU_time

· MPI_time

· SendRecv_time

· CollectiveAll_time

· AllToAll_time

· Comm_time(Общее время коммуникаций)

· Idle_time(время бездействия)

· Potent_sync

· Time_variation

· T_start

Все они уже являются характеристиками всего интервала.

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

После функции Integrate() вычисляется полезное время calculateProductive(), потом время запуска - calculateExecution(),

эффективность распараллеливания - efficiency(), и, наконец, потерянное время - calculateLost().

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

Пример. Текстовый файл с итоговыми характеристиками.

Interval (LineNumber = 153 SourceFile = exch.c) Level=0 EXE_Count=1

---Main Characteristics---

Parallelization Efficiency 0.978833

Execution Time 2.079975

Processors 4

Total Time 8.319900

Productive Time 8.143794 (CPU MPI)

MPI время на одном процессоре считается полезным, а на остальных - потерянным

Lost Time 0.176106

---MPI Time 0.173490

---Idle Time 0.002616

Communication Time 0.076563

*****SendRecv Time 0.013295

*****CollectiveAll Time 0.063268

*****AllToAll Time 0.000000

Potential Sync. 0.068763

Time Variation 0.001790

Time of Start 0.000000

---Comparative Characteristics---

Tmin Nproc Tmax Nproc Tmid

Lost Time 0.033087 3 0.060057 0 0.044026

Idle Time 0.000000 1 0.000898 0 0.000654

Comm. Time 0.006597 3 0.034854 0 0.019140

MPI Time 0.032259 3 0.059159 0 0.043372

Potential Sync. 0.001800 0 0.029369 3 0.017190

Time variation 0.000161 1 0.000607 3 0.000447

Time of Start 0.000000 0 0.000000 0 0.000000

Для каждого интервала выдается следующая информация:

· имя файла с исходным текстом MPI-программы и номер первого оператора интервала в нем (SourceFile, LineNumber);

· номер уровня вложенности (Level);

· количество входов (и выходов) в интервал (EXE_Count);

· основные характеристики выполнения и их компоненты (Main characteristics);

· минимальные, максимальные и средние значения характеристик выполнения программы на каждом процессоре (Comparative characteristics);

При выдаче характеристик их компоненты располагаются в той же строке (справа в скобках), либо в следующей строке (справа от символов “*” или “-“).

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

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

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

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

Это значительно облегчает поиск необходимой для анализа области.

Рис.2. Окно программы анализа.

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

Используя механизм Tooltip'ов, пользователь получает возможность узнать тип события (пользовательский (UserCode) или MPI) и название функции (для MPI - функций).

Рис.3. TimeLine



4. Задача суммирования на MPI

Функции MPI_Send и MPI_Recv, рассмотренные в п. 5.2.1, обеспечивают возможность выполнения парных операций передачи данных между двумя процессами параллельной программы. Для выполнения коммуникационных коллективных операций, в которых принимают участие все процессы коммуникатора, в MPI предусмотрен специальный набор функций. В данном подразделе будут рассмотрены три такие функции, широко применяемые даже при разработке сравнительно простых параллельных программ; полное же представление коллективных операций будет дано в подразделе 5.4.

Для демонстрации применения рассматриваемых функций MPI будет использоваться учебная задача суммирования элементов вектора x (см. подраздел 2.5):

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

Передача данных от одного процесса всем процессам программы

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

MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);

for (int i = 1; i < ProcNum; i++)

MPI_Send(&x, n, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);

Однако такое решение будет крайне неэффективным, поскольку повторение операций передачи приводит к суммированию затрат (латентностей) на подготовку передаваемых сообщений. Кроме того, как показано в "Оценка коммуникационной трудоемкости параллельных алгоритмов" , данная операция может быть выполнена за log₂p итераций передачи данных.

Достижение эффективного выполнения операции передачи данных от одного процесса всем процессам программы (широковещательная рассылка данных ) может быть обеспечено при помощи функции MPI:

int MPI_Bcast(void *buf, int count, MPI_Datatype type, int root,

MPI_Comm comm),

где

· buf, count, type -- буфер памяти с отправляемым сообщением (для процесса с рангом 0 ) и для приема сообщений (для всех остальных процессов );

· root -- ранг процесса, выполняющего рассылку данных;

· comm -- коммуникатор, в рамках которого выполняется передача данных.

Функция MPI_Bcast осуществляет рассылку данных из буфера buf, содержащего count элементов типа type, с процесса, имеющего номер root, всем процессам, входящим в коммуникатор comm (см. рис. 5.1).

Следует отметить:

· функция MPI_Bcast определяет коллективную операцию, и, тем самым, при выполнении необходимых рассылок данных вызов функции MPI_Bcast должен быть осуществлен всеми процессами указываемого коммуникатора (см. далее пример программы);

· указываемый в функции MPI_Bcast буфер памяти имеет различное назначение у разных процессов: для процесса с рангомroot, которым осуществляется рассылка данных, в этом буфере должно находиться рассылаемое сообщение, а для всех остальных процессов указываемый буфер предназначен для приема передаваемых данных;

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

Общая схема операции передачи данных от одного процесса всем процессам

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

Параллельная программа суммирования числовых значений

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include "mpi.h"

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

double x[100], TotalSum, ProcSum = 0.0;

int ProcRank, ProcNum, N=100, k, i1, i2;

MPI_Status Status;

// Инициализация

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);

MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);

// Подготовка данных

if ( ProcRank == 0 ) DataInitialization(x,N);

// Рассылка данных на все процессы

MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

// Вычисление частичной суммы на каждом из процессов

// на каждом процессе суммируются элементы вектора x от i1 до i2

k = N / ProcNum;

i1 = k * ProcRank;

i2 = k * ( ProcRank + 1 );

if ( ProcRank == ProcNum-1 ) i2 = N;

for ( int i = i1; i < i2; i++ )

ProcSum = ProcSum + x[i];

// Сборка частичных сумм на процессе с рангом 0

if ( ProcRank == 0 ) {

TotalSum = ProcSum;

for ( int i=1; i < ProcNum; i++ ) {

MPI_Recv(&ProcSum,1,MPI_DOUBLE,MPI_ANY_SOURCE,0, MPI_COMM_WORLD, &Status);

TotalSum = TotalSum + ProcSum;

}

}

else // Все процессы отсылают свои частичные суммы

MPI_Send(&ProcSum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

// Вывод результата

if ( ProcRank == 0 )

printf("\nTotal Sum = %10.2f",TotalSum);

MPI_Finalize();

return 0;

}

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

Параллельная программа суммирования числовых значений

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

Передача данных от всех процессов одному процессу. Операции редукции

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

int MPI_Reduce(void *sendbuf, void *recvbuf,int count,MPI_Datatype type, MPI_Op op,int root,MPI_Comm comm),

где

- sendbuf - буфер памяти с отправляемым сообщением,

- recvbuf - буфер памяти для результирующего сообщения (только для сса с рангом root),

проце- count - количество элементов в сообщениях,

- type - тип элементов сообщений,

- op - операция, которая должна быть выполнена над данными,

- root - ранг процесса, на котором должен быть получен результат,

- comm - коммуникатор, в рамках которого выполняется операция.

В качестве операций редукции данных могут быть использованы предопределенные в MPI операции - см. табл. 4.2.

Таблица 4.2. Базовые (пpедопpеделенные) типы операций MPI для функций редукции данных

Операция	Описание
MPI_MAX	Определение максимального значения
MPI_MIN	Определение минимального значения
MPI_SUM	Определение суммы значений
MPI_PROD	Определение произведения значений
MPI_LAND	Выполнение логической операции "И" над значениями сообщений
MPI_BAND	Выполнение битовой операции "И" над значениями сообщений
MPI_LOR	Выполнение логической операции "ИЛИ" над значениями сообщений
MPI_BOR	Выполнение битовой операции "ИЛИ" над значениями сообщений
MPI_LXOR	Выполнение логической операции исключающего "ИЛИ" над значениями сообщений
MPI_BXOR	Выполнение битовой операции исключающего "ИЛИ" над значениями сообщений
MPI_MAXLOC	Определение максимальных значений и их индексов
MPI_MINLOC	Определение минимальных значений и их индексов

Помимо данного стандартного набора операций могут быть определены и новые дополнительные операции непосредственно самим пользователем библиотеки MPI - см., например, Немнюгин и Стесик (2002), Group, et al. (1994), Pacheco (1996).

...