Последовательно-параллельный алгоритм MPI: как добиться такого поведения с помощью MPI?

Question

У меня следующая проблема, и я не понимаю, как этого добиться в MPI-Fortran.

Предположим, что у меня есть N0 узлов в моем кластере, учитывая интервал (1, N), я делю его на N0 сегментов обозначается (i1, i2), и предположим, что время вычисления для каждого (i1, i2) - некоторое T, выполняемое параллельно. Теперь, если я сделаю дополнительное разделение каждого подинтервала (i1, i2) на N0 меньших, позвольте вызвать (a1, a2), в данный момент, я хочу работать с каждым (i1, i2) последовательно, но с каждым (a1, a2) параллельно, будет ли время вычисления для (i1, i2) T / N0, т. е. значительно уменьшится по сравнению с первым разделом? и если это так, как мне реализовать эту идею в MPI?

Спасибо за ваши предложения и помощь.

Чтобы обновить сообщение, я придумал следующие схематические строки. Надеюсь, это достаточно для понимания, где

• i: индекс подинтервала (i1, i2)
• rank: это ранг текущего узла
• sub_sub_interval (rank, i): переменная, содержащая все подинтервалы (a1, a2) интервала (i1, i2).

.

do i = 0, number_machine-1

   call MPI_BARRIER(MPI_COMM_WORLD, ierr)

   start = MPI_Wtime()

   call compute_my_quantity(A, sub_interval(i),
        sub_sub_interval(rank,i))

   end = MPI_Wtime()

   if (rank /= 0) then 
      call SEND_my_quantity(rank, A)
   else 
      do i_prime = 1, number_machine-1
         call RECEV_my_quantity(i_prime, A_sub(i_prime))
      end do
   end if
end do

Что Я понимаю, что: время, измеренное для каждого (a1, a2), все еще такое же, как

   start = MPI_Wtime()

   call compute_my_quantity(A, sub_interval(rank))

   end = MPI_Wtime()

   if (rank /= 0) then 
      call SEND_my_quantity(rank, A)
   else 
      do i_prime = 1, number_machine-1
         call RECEV_my_quantity(i_prime, A_sub(i_prime))
      end do
   end if

Может быть, вы можете сказать мне, что концептуально неверно в этом алгоритме, например, что время, необходимое для (a1, a2 ) то же, что и для (i1, i2)?

Answer 1

Как я понял из вопроса,

У вас есть несколько задач (скажем, N), которые разделены на N0 сегментов, каждый из которых принимает несколько N / N0 задач.

В стратегии 1 , вы распределяете это между N0 (или более) рангами и работаете параллельно. В стратегии 2 вы берете задачу из N задач и распределяете ее по рангам MPI. Точно так же каждая задача выполняется последовательно.

Теоретически стратегия 1 всегда будет быстрее, чем стратегия 2, из-за накладных расходов, накладываемых коммуникацией. В стратегии 2 будет много (в N0 раз больше, чем в стратегии 1) общения. Таким образом, производительность вашего приложения будет снижена.

Идеальным подходом будет использование модели гибридного программирования , где вы распределяете задачи между узлами с помощью MPI, а на каждом узле вы используете некоторую парадигму общей памяти (openMP ), чтобы ускорить выполнение. По сути, это комбинация вашей стратегии 1 и стратегии 2.