Проблема динамического распараллеливания цикла в MPI?

Question

[ptizza]

Имеем цикл следующего вида:

for (int i = 0; i <= n ; ++i )
 sum += calc(i);

Время выполнения функции calc() всегда разное и его не возможно определить заранее.

Каким образом можно распараллелить цикл, чтобы в среднем все машины были одинакого загружены?


Прошу помочь с решением проблемы.

Answer 1

[1nd1go]

Похоже на work stealing

Answer 2

[m08pvv]

Производитель-потребитель, причём если время выполнения calc небольшое, то можно выдавать задания небольшими пачками (по несколько i).

Answer 3

[petch]

Рутовый (нулевой) процесс раздает значения i, все остальные вычисляют sum по полученным i. Ускорение получается не в P (количество задействованных процессов) раз, а P-1 поскольку один процесс не участвует в вычислениях.

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <unistd.h>
#include <time.h>

int calc(int i) {
	int time = rand() % 1000;
	printf("calc(%d) takes %d ms\n", i, time);
	usleep(time * 1000);
	return time;
}

int main() {
	MPI_Init(0, 0);

	int rank, size;
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	std::cout << "Hello from " << rank << std::endl;

	int sum = 0, n = 100;
	MPI_Status status;
	srand(time(NULL) + rank);

	clock_t begin = clock();
	if (rank == 0) {
		int dest, finish = -1;
		for (int i = 0; i < n; i++) {
			MPI_Recv(&dest, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
			MPI_Send(&i, 1, MPI_INT, status.MPI_SOURCE, 1, MPI_COMM_WORLD);
		}
		for (int p = 0; p < size - 1; p++) {
			MPI_Recv(&dest, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
			MPI_Send(&finish, 1, MPI_INT, status.MPI_SOURCE, 1, MPI_COMM_WORLD);
		}
	} else {
		int i = 0;
		while (i >= 0) {
			MPI_Send(&rank, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
			MPI_Recv(&i, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
			if (i >= 0) {
				printf("process %d ", rank);
				sum += calc(i);
			}
		}
	}
	clock_t end = clock();
	double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

	MPI_Allreduce(&sum, &sum, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);

	if (rank == 0) {
		printf("Program execution time is  %f s\n", time_spent);
		printf("Processes calc(i) takes    %f s\n", sum / 1000.0);
		printf("CPU time (without root) is %f s\n", (size - 1) * time_spent);
	}

	MPI_Finalize();
	return 0;
}