Алгоритм измерения времени расчета (с использованием MPI, параллельные вычисления) - PullRequest
Новая
       13

Алгоритм измерения времени расчета (с использованием MPI, параллельные вычисления)

1 голос
/ 15 июня 2011

http://pastebin.com/Xb6GLv8Y

Мой код выполняет следующие действия:

Он будет выполняться параллельно в кластере.Мастерский ранг создаст упорядоченный по потомкам массив с большим количеством элементов (максимум 1.6M элементов), разделит этот массив на меньшие массивы, отправит каждую из этих частей на каждый из компьютеров в кластере.Каждый компьютер в кластере будет выполнять алгоритм быстрой сортировки в своей части массива и отправлять этот (упорядоченный по возрастанию) массив в ранг мастера.Затем мастер-ранг будет использовать модифицированный алгоритм пузырьковой сортировки для сортировки каждой части, полученной из дочерних рангов, и построения нового упорядоченного массива.(Цель состоит в том, чтобы выполнить алгоритм быстрой сортировки в параллельных вычислениях.)

Все работает отлично, единственная проблема заключается в том, что мне нужно измерить время вычисления алгоритма.Это работа университета, поэтому в PDF-документе говорится «рассчитывать время ТОЛЬКО для алгоритма заказа».Поэтому я считаю, что не следует рассматривать передачу массива между сетью и т. Д.

То, что я сделал в коде, - это измерение истекшего времени быстрой сортировки для каждого ранга ребенка.Самое большое время будет временем вычислений.Я прав?Но есть проблема.Посмотрите вывод: 

Array final, first 1, last 800000
Vetor de 800000 elementos ordenado com quicksort em paralelo (99 threads).
Dentre o tempo de processamento de cada node, o maior foi 140000, 0.14 seconds.

Array final, first 1, last 1600000
Vetor de 1600000 elementos ordenado com quicksort em paralelo (99 threads).
Dentre o tempo de processamento de cada node, o maior foi 560000, 0.56 seconds.

В нем указано, что максимальное время выполнения ребенком быстрой сортировки составляет 0,56 секунды.Но я ждал около 30 секунд, прежде чем был напечатан последний результат.Это абсурдная разница нормально?Я правильно измеряю время?

Спасибо за помощь

Ответы [ 2 ]

0 голосов
/ 15 июня 2011

Если вы хотите измерить время для всей сортировки, то вы должны измерить время, затраченное на завершение работы последнего процессора. Вы можете сделать это, приняв время окончания после MPI_Barrier.

Разница в скорости между узлами в 60 раз означает, что у вас плохая балансировка нагрузки. Некоторые узлы выполняют намного больше работы, чем другие, и если вы хотите добиться хорошей производительности, вам нужно найти способ выровнять нагрузки немного больше.

Если вы заинтересованы в параллельной сортировке, то я рекомендую вам ознакомиться с алгоритмом PSort и исходным кодом . Он выполняет локальную сортировку, а затем некоторое минимальное взаимодействие, чтобы выяснить, какие процессоры должны получить какую часть, а затем массовую передачу данных на их целевые процессоры. У него минимальное количество служебных данных.

0 голосов
/ 15 июня 2011

Может произойти пара вещей.

  1. Вы не рассчитываете время для sort и joinArrays в rank0 после завершения дочерних процессов.

  2. Каждому ребенку потребовалось 0,56 секунды, но время начала каждого ребенка не обязательно должно быть одинаковым. Я не знаю, какую коммуникационную структуру имеет ваш кластер, но, учитывая небольшое количество данных, которые вы перемещаете, я сомневаюсь, что это будет проблемой.

...