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

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

Ускорением параллельного алгоритма называют отношение времени выполнения лучшего последовательного алгоритмам к времени выполнения параллельного алгоритма: S= (2)

Параллельный алгоритм может давать большое ускорение, но использовать для этого множество процессов неэффективно. Для оценки масштабируемости параллельного алгоритма используется понятие ффективности: E= (3)

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

S= = (4)

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

2.Коммуникации точка/точка. Примеры использования фукнции MPI_Isend(), MPI_Irecv.

intMPI_Isend (void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm,MPI_Request*request)- функциянеблокирующейпосылки

bufначальныйадресбуферапосылки (альтернатива); countчислоэлементоввбуферепосылки (целое); datatypeтипкаждогоэлементавбуферепосылки (дескриптор); destномерпроцесса-получателя (целое); tagтэгсообщения (целое); commкоммуникатор (дескриптор); requestзапрособмена (дескриптор);

intMPI_Irecv (void*buf,intcount,MPI_Datatypedatatype,intsource,inttag,MPI_Commcomm,MPI_Request*request)- функциянеблокирующегоприема

IN bufначальныйадресбуферапосылки (альтернатива); IN countчислоэлементоввбуферепосылки (целое); IN datatypeтипкаждогоэлементавбуферепосылки (дескриптор); IN sourceномерпроцесса-получателя (целое); IN tagтэгсообщения (целое); IN commкоммуникатор (дескриптор); OUT requestзапрособмена (дескриптор)

Пример 3: Обмен по кольцу без блокировки

#include "mpi.h"

#include <stdio.h>

main(int argc, char **argv) {

int numtasks, rank, next, prev, buf[2], tag1=1, tag2=2;

MPI_Request reqs[4];

MPI_Status stats[4];

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

prev = rank - 1;

next = rank + 1;

if (rank == 0) prev = numtasks - 1;

if (rank == (numtasks - 1)) next = 0;

MPI_Irecv(&buf[0], 1, MPI_INT, prev, tag1, MPI_COMM_WORLD, &reqs[0]);

MPI_Irecv(&buf[1], 1, MPI_INT, next, tag2, MPI_COMM_WORLD, &reqs[1]);

MPI_Isend(&rank, 1, MPI_INT, prev, tag2, MPI_COMM_WORLD, &reqs[2]);

MPI_Isend(&rank, 1, MPI_INT, next, tag1, MPI_COMM_WORLD, &reqs[3]);

MPI_Waitall(4, reqs, stats);

printf("me %d recv %d %d\n",rank,buf[0],buf[1]);

MPI_Finalize();

}