Масштабирование и распределение подзадач по процессорам. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Масштабирование и распределение подзадач по процессорам.



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

 

Анализ эффективности

Для анализа эффективности параллельных вычислений здесь и далее будут строиться два типа оценок. В первой из них трудоемкость алгоритмов оценивается в количестве вычислительных операций, необходимых для решения поставленной задачи, без учета затрат времени на передачу данных между процессорами, а длительность всех вычислительных операций считается одинаковой. Кроме того, константы в получаемых соотношениях, как правило, не указываются- для первого типа оценок важен прежде всего порядок сложности алгоритма, а не точное выражение времени выполнения вычислений. Как результат, в большинстве случаев подобные оценки получаются достаточно простыми и могут быть использованы для начального анализа эффективности разрабатываемых алгоритмов и методов. Второй тип оценок направлен на формирование как можно более точных соотношений для предсказания времени выполнения алгоритмов. Получение таких оценок проводится, как правило, при помощи уточнения выражений, полученных на первом этапе. Для этого в имеющиеся соотношения вводятся параметры, задающие длительность выполнения операций, строятся оценки трудоемкости коммуникационных операций, указываются все необходимые константы. Точность получаемых выражений проверяется при помощи проведения вычислительных экспериментов, по результатам которых времена выполненных расчетов сравниваются с теоретически предсказанными оценками длительностей вычислений. Как результат, оценки подобного типа имеют, как правило, более сложный вид, но позволяют более точно оценивать эффективность разрабатываемых методов параллельных вычислений. Рассмотрим трудоемкость алгоритма умножения матрицы на вектор. В случае, если матрица А квадратная(m=n), последовательный алгоритм умножения матрицы на вектор имеет сложность . В случае параллельных вычислений каждый процессор производит умножение только части(полосы) матрицы A на вектор b, размер этих полос равен n/p строк. При вычислении скалярного произведения одной строки матрицы и вектора необходимо произвести n операций умножения и (n-1) операций сложения. Следовательно, вычислительная трудоемкость параллельного алгоритма определяется выражением:

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

;

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

 

25. Обобщенная передача данных от всех процессов одному процессу. Операция обобщенной передачи данных от всех процессоров одному процессу (сбор данных) является обратной к процедуре распределения данных (см. рис. 5.5). Для выполнения этой операции в MPI предназначена функция: int MPI_Gather(void *sbuf,int scount,MPI_Datatype stype,void *rbuf,int rcount,MPI_Datatype rtype,int root, MPI_Comm comm), где sbuf, scount, stype - параметры передаваемого сообщения, rbuf, rcount, rtype - параметры принимаемого сообщения, root – ранг процесса, выполняющего сбор данных, comm - коммуникатор, в рамках которого выполняется передача данных.


Рис. 5.5. Общая схема операции обобщенной передачи данных от всех процессов одному процессу. При выполнении функции MPI_Gather каждый процесс в коммуникаторе передает данные из буфера sbuf на процесс с рангом root. Процесс с рангом root собирает все получаемые данные в буфере rbuf (размещение данных в буфере осуществляется в соответствии с рангами процессов-отправителей сообщений). Для того, чтобы разместить все поступающие данные, размер буфера rbuf должен быть равен scount * p элементов, где p есть количество процессов в коммуникаторе comm. Функция MPI_Gather также определяет коллективную операцию, и ее вызов при выполнении сбора данных должен быть обеспечен в каждом процессе коммуникатора. Следует отметить, что при использовании функции MPI_Gather сборка данных осуществляется только на одном процессе. Для получения всех собираемых данных на каждом из процессов коммуникатора необходимо использовать функцию сбора и рассылки:

int MPI_Allgather(void *sbuf, int scount, MPI_Datatype stype,

void *rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm).

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

 



Поделиться:


Последнее изменение этой страницы: 2016-04-08; просмотров: 503; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.238.161.165 (0.021 с.)