2013-04-09 15 views
1

Предположим, что у вас есть 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 adder.

+0

Awesome, спасибо! – Shmoopy

+0

Добро пожаловать! Спасибо за репутацию :) – Marcellus

Смежные вопросы