Закон Амдала. Ускорение. Эффективность

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

С помощью информационного графа можно оценить максимальное ускорение, которого можно достичь при распараллеливании алгоритма там, где это возможно. Предположим, что программа выполняется на машине, архитектура которой идеально соответствует структуре информационного графа программы. Пусть время выполнения алгоритма на последовательной машине Т1, причем Тs — время выполнения последовательной части алгоритма, а Тр — параллельной. Очевидно:T1 = TS + Тр.

При выполнении той же программы на идеальной параллельной машине, N независимых ветвей параллельной части распределяются по одной на V процессоров, поэтому время выполнения этой части уменьшается до величины Тр / N, а полное время выполнения программы составит:T2=TS+ Tp/N.

Коэффициент ускорения, показывающий, во сколько раз быстрее программа выполняется на параллельной машине, чем на последовательной, определяется формулой:Х= Т}/Т2 = (Ts + Tp) / (Ts + Tp/N) = 1/(S + P/N),

где S= Ts / (Ts + Tp) и P= Tp / (Ts + Tp) — относительные доли последовательной и параллельной частей (S+ Р= 1). График зависимости коэффициента ускорения от числа процессоров и степени параллелизма алгоритма (относительной доли параллельной части) приведен на рис. 2.5. Эта зависимость носит название закона Амдала.

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

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

Префикс B (buffered) -означает буферизованный режим передачи данных. В адресном пространстве передающего процесса с помощью специальной функции создается буфер обмена, который используется в операциях обмена. Операция посылки заканчивается, когда данные помещены в этот буфер. Функция имеет локальный характер.
MPI_Bsend — передача сообщения с буферизацией. Если прием посылаемого сообщения еще не был инициализирован процессом-получателем, то сообщение будет записано в буфер, и произойдет немедленный возврат из функции. Выполнение данной функции никак не зависит от соответствующего вызова функции приема сообщения. Тем не менее, функция может вернуть код ошибки, если места под буфер недостаточно. О выделении массива для буферизации должен заботиться пользователь.

int MPI_Bsend(void *buf, int count, MPI_Datatype datatype,int dest, int tag, MPI_Comm comm)

buf-адрес начала расположения пересылаемых данных; count– число пересылаемых элементов; datatype – тип посылаемых элементов; dest–номер процесса-получателя в группе, связанной с коммуникатором comm; tag–идентификатор сообщения (аналог типа сообщения функций nread и nwrite PSE nCUBE2); comm – коммуникатор области связи.

MPI_Bsend(&buffer, buffsize, MPI_INT, 1, TAG, MPI_COMM_WORLD);