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

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

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

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

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

S= = (4)

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

 

 

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

int MPI_Isend ( void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request) - функциянеблокирующейпосылки

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

int MPI_Irecv ( void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, 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();

}