Добавление двух целых чисел параллельно
Предположим, у вас есть 2 беззнаковых целых числа n цифр, заданных в двух массивах a, b, и у вас есть p процессоров, каждый из которых может добавить 2 цифры и вычислить перенос, если он существует. Можно ли вычислить a+b за время O(p+n/p)? Я пытался разделить входные данные на p интервалов (n/p) каждый, но я не знаю, как обрабатывать перенос.
1 ответ
Я верю, что это возможно. Я собираюсь предположить n >= p и что ваши p-процессоры организованы в архитектуре без разделения ресурсов, в которой процессоры обмениваются сообщениями.
Если ваши цифры еще не распределены между p процессорами, а собраны на одном главном процессоре, не участвующем в вычислениях, вы просто разделяете a и b, чтобы создать p блоков непрерывных цифр, каждая, и отправлять их на каждый из процессоров., Это требует сложности сообщения O(p),
Затем каждый процессор вычисляет две суммы для своего блока цифр, одна сумма при условии, что он получит перенос 1 от своего предшественника, то есть процессора, который имеет следующий блок менее значащих цифр, а другой, предполагая, что перенос будет равен 0. Он также рассчитает исходящий перенос для каждого из двух сценариев. Вычисление имеет временную сложность O(ceil(n/p)), поскольку каждый процессор должен содержать целое число цифр.
Конечно, процессор, имеющий блок младших разрядов, должен будет вычислить только одну сумму. Как только он выполнил свои вычисления, он отправляет свою долю результирующих цифр обратно в мастер, а свой исходящий перенос в процессор, содержащий следующий блок более значимых цифр. Следующий процессор решает, какой из двух сценариев результатов стал истинным, отправляет соответствующие цифры результата главному устройству и его исходящему переносу на следующий процессор. И так далее.
Это займет дополнительные p сообщений для результатов и p-1 сообщений для переносов. Таким образом, сложность сообщения по-прежнему O(p), Время сложность будет O(p + ceil(n/p)) так как последний процессор придется ждать до p-2 его предшественники решили, какой из двух результатов переслать. Если вы предполагаете, что n цифр могут быть равномерно распределены между процессорами p (т. Е. N кратно p), то вы согласны с предложенной сложностью времени. O(p + n/p),
Этот метод сложения с умозрительным подсчетом двух возможных результатов очень похож на работу сумматора Carry-select.