Как определить наиболее эффективный алгоритм параллельного добавления?

Question

Задав еще один вопрос о алгоритме MapReduce, я подумал о том, как определить наиболее эффективный способ достижения общей суммы n значений с помощью параллельной обработки. Проблема может быть упрощена следующим образом:

Предположим, что у меня есть n процессоров, каждая из которых имеет целое число. Я хочу как можно быстрее определить сумму целых чисел.

Теперь я мог бы получить каждый процессор 2, .., n, чтобы передать его целое число в процессор 1. Затем процессор 1 затем добавляет каждое из чисел, чтобы получить результат. Это означает, что n - 1 проход данных, но все это может происходить параллельно. За этим следуют n-1 операции сложения, происходящие последовательно.

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

Конечно, есть много других способов сделать это. Как определить, какая из них наиболее эффективна? Я подозреваю, что это зависит от относительной стоимости операции добавления и передачи целого числа (в реальной жизни, думаю, CPU против скорости сети) и, вероятно, также от размера n. В конце концов, если n очень велико, то добавление дополнительного сетевого хопа для сокращения вдвое n может стоить того, даже если каждое добавление относительно дешево.

Answer 1

Это больше комментариев, чем ответ, но коробочка так ограничившись ...

Определения наиболее эффективным. Вы занимаетесь теоретической эффективностью или скоростью на практике?

Я думаю, вы задаете себе правильные вопросы, и, похоже, вы поняли, что если у вас есть 100 000 процессоров с 1 целым числом, тогда критический ресурс - это скорость связи, а не скорость вычислений. Для любой схемы, которую вы создаете для сумм N целых чисел, начиная с N, процессоры учитывают, что время связи будет преобладать не по полосе пропускания (время отправки 1 целого), а по латентности (время отправки сообщения размера 0). Для большинства практических целей я ожидаю, что этот вопрос уничтожит ваши фантазии.

И еще один вопрос: откуда взялись целые числа? Если они возникли на одном процессе (или) и были распределены другим N-1, вы почти наверняка потратили больше времени на их рассылку, чем на первый процесс (или), чтобы вычислить сумму. Если целые числа возникли, по-видимому, в результате процесса, выполняемого на каждом процессоре, независимо от эффективности (в), вам все равно придется сделать какое-то сокращение и оплатить стоимость связи.

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