Существует ли какое-либо алгебраическое представление натуральных чисел, допускающее параллельное сложение?

Натуральные числа могут быть представлены в логарифмическом пространстве с помощью двоичного представления (в данном случае с прямым порядком байтов):

-- The type of binary numbers; little-endian; O = Zero, I = One
data Bin = O Bin | I Bin | End

Затем можно реализовать добавление a и b, например, вызвав функцию successor (O(log(N))) a раз на b. Проблема с этой реализацией заключается в том, что она по своей сути является последовательной. Чтобы добавить 2 номера, suc вызовов последовательно объединяются в цепочку. Другие реализации add (например, использование переноса) страдают от той же проблемы. Легко видеть, что сложение не может быть реализовано параллельно с этим представлением. Существует ли какое-либо представление натуральных чисел с использованием алгебраических типов данных, которое занимает логарифмическое пространство и сложение которого можно выполнять параллельно?

Код для иллюстрации:

-- The usual fold  
fold :: Bin -> (t -> t) -> (t -> t) -> t -> t
fold (O bin) zero one end = zero (fold bin zero one end)
fold (I bin) zero one end = one (fold bin zero one end)
fold E zero one end       = end

-- Successor of `Bin` - `O(log(N))`
suc :: Bin -> Bin
suc (O bin) = I bin
suc (I bin) = O (suc bin)
suc E       = E

-- Calls a function `a` times
times :: Bin -> (t -> t) -> t -> t
times a f x     = fold a zero one end f where 
    one bin fs  = fs (bin (fs . fs))
    zero bin fs = bin (fs . fs)
    end fs      = x

-- Adds 2 binary numbers
add :: Bin -> Bin -> Bin
add a b = (a `times` suc) b

-- 1001 + 1000 = 0101
main = print $ add (I (O (O (I E)))) (I (O (O (O E))))

parallel-processing algorithm data-structures haskell addition
person MaiaVictor    schedule 15.11.2015    source источник
comment
двоичный код — это представление, и у него есть упомянутая вами проблема — перенос каждого бита зависит от всех младших битов. Поэтому сложно понять, чего ты хочешь. Способ сложения двоичных чисел с большим параллелизмом (например, сумматор с опережением переноса) или недвоичное представление (например, представление CRT), которое позволяет выполнять сложение (и умножение) параллельно.   -  person Matt Timmermans    schedule 15.11.2015
comment
@MattTimmermans, это действительное возражение, я отредактировал вопрос. Надеюсь, теперь это имеет больше смысла.   -  person MaiaVictor    schedule 15.11.2015
comment
Я использую сумматоры с опережением переноса как способ улучшить параллелизм. Существует также родственный вероятностный подход: если вы суммируете две битовые строки с начальным переносом a+b+carry1 = result + carry2, вы можете вычислить carry2, не глядя на carry1 в подавляющем большинстве случаев, то есть во всех случаях, когда map not a /= b. Таким образом, вы можете произвести выходной перенос заранее и начать добавлять следующий битовый блок, не дожидаясь предыдущего переноса (в большинстве случаев).   -  person chi    schedule 15.11.2015
comment
может быть сделано параллельно, довольно расплывчато, вы имеете в виду конкретное понятие?   -  person Reid Barton    schedule 15.11.2015
comment
Я думаю о каком-то древовидном представлении, таком как data Nat = Bin Nat Nat | Zero | One, с сопоставлением с натуральными числами, и на котором add : Nat → Nat → Nat можно реализовать параллельно, потому что две ветви можно добавить независимо. add (Bin l r) = _ l _ r _; add Zero = _; add One = _;... что-то в этом роде я имею в виду.   -  person MaiaVictor    schedule 15.11.2015

Ответы (3)


arrow_upward
4
arrow_downward

Существует множество архитектур параллельных сумматоров. Отличный обзор дан в магистерской диссертации Томаса Уокера Линча в Техасском университете в Остине, 1996 г.< /а>. См. раздел 9.1, где он резюмирует длину пути для наихудшего случая.

Сумматор Линча и Шварцлендера (L&S) имеет наихудшую длину пути 2*ceil(log4(N))+2, где N – это количество битов. Архитектура представлена ​​в их документе A Spanning Tree Carry Lookahead Adder.

Вы можете найти отличные объяснения многих простых архитектур, погуглив «быстрый сумматор».

person Lior Kogan    schedule 15.11.2015
comment
Отличный ответ. Это показывает, что это возможно. Теперь осталось перевести технику на ADT. Мое наивное определение Bin не может быть распараллелено с этой стратегией, поскольку вы не можете читать nth бит Bin параллельно (как вы можете с машинным битовым вектором). Я считаю, что какое-то умное представление двоичного дерева может заставить его работать. - person MaiaVictor; 15.11.2015
comment
(Почему вы удалили эту ссылку? ) - person MaiaVictor; 15.11.2015
comment
@Viclib: Просто потому, что есть так много отличных ссылок, и это только одна из них. - person Lior Kogan; 15.11.2015

arrow_upward
1
arrow_downward

Вы не сказали, что каждое натуральное число должно иметь уникальное представление. Итак, вот еще один вариант. (Я не изобрел его, но я не могу вспомнить, как он называется, поэтому мне пришлось реконструировать, как он работает.)

Представлять числа в виде строк цифр с основанием 2, как в двоичном формате, за исключением того, что вместо того, чтобы ограничиваться цифрами 0 и 1, нам дополнительно разрешено использовать цифру 2. Так, например, число 2 имеет два представления: 10 и 2. .

Чтобы сложить два числа, представленные таким образом, просто сложите их по цифрам без переноса. Ясно, что мы можем сделать это эффективно параллельно (с линейным размером, постоянной глубиной схемы). Что ж, теперь у нас есть проблема: полученное число имеет правильное значение по основанию 2, но его цифры не обязательно будут 0, 1 или 2, но могут достигать 4.

Итак, давайте исправим это с помощью следующего прохода распространения переноса: запишите каждую цифру результата в виде двузначного двоичного числа, где вторая цифра равна 0 или 1, а первая цифра может быть 0, 1 или 2. (Так что 0 -> 00, 1 -> 01, 2 -> 10, 3 -> 11, 4 -> 20.) Теперь «переносим» первую цифру каждого из этих двузначных чисел влево, оставляя за собой вторую цифру, но не выполняя любое другое продолжение результата. Например, если мы начали с числа

 314102    (perhaps from the original problem of computing 212001 + 102101)

мы выполняем сумму

11       = 3
 01      = 1
  20     = 4
   01    = 1
    00   = 0
     10  = 2
-------
1130110

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

Этого недостаточно, поэтому давайте проделаем тот же проход распространения переноса еще раз. Теперь 4 больше не является возможной входной цифрой, поэтому цифра, которую мы переносим, ​​никогда не может быть 2, только 0 или 1. Таким образом, на этот раз процедура приведет к представлению по основанию 2, в котором используются только цифры 0, 1 и 2, чего мы и хотели. В приведенном выше примере результатом будет 1210110. (Конечно, любое другое представление с тем же значением базы 2 также будет правильным.)

(Для других комбинаций базовой и максимальной цифр вам может понадобиться только один проход распространения переноса. Например, если вы представляете числа в базе 3, используя цифры 0, 1, 2, 3 и 4, самая большая цифра, появляющаяся в сумме, равна 8. , так что обе цифры, участвующие в проходе распространения переноса, будут в диапазоне 0, 1, 2, а их сумма уже будет не более 4.)

Теперь, если вы хотите выполнить другие операции с этим представлением, например, сравнить два числа на равенство, один из вариантов — преобразовать в двоичный код либо последовательно за линейное время, либо параллельно с помощью быстрого сумматора, как описано в ответе Лиора Когана. На самом деле преобразование этого представления в двоичное по существу эквивалентно проблеме сложения чисел в двоичном виде, поскольку мы можем рассматривать представление, подобное 212001, как «формальное сложение» 101000 + 111001. Однако вы, вероятно, не можете проверить равенство в этом представлении с постоянной глубиной, как вы можете для двоичного. Я полагаю, что «сложность» в этом смысле либо сложения, либо проверки на равенство важна, учитывая ваши другие ограничения, хотя я не знаю наверняка.

person Reid Barton    schedule 15.11.2015
comment
Их можно просто назвать избыточными двоичными числами. Я не уверен. - person dfeuer; 16.11.2015
comment
Да это оно! Спасибо. - person Reid Barton; 16.11.2015

arrow_upward
0
arrow_downward

Вот один из простых способов описания параллельного сложения натуральных чисел: если вы посмотрите на схема сумматора, она имеет 3 входных бита и выводит 2-битное число, указывающее, сколько входных битов было 1. Именно поэтому ее иногда называют компрессор 3:2. Из них мы можем создать схему, которая параллельно складывает 3 двоичных числа, чтобы получить 2 двоичных числа. Это также называется схемой сумматора переноса-сохранения, потому что вместо распространения битов переноса мы сохраняем их как другой, отдельный номер. Затем каждое число (избыточно) представляется как пара двоичных чисел. А при добавлении k натуральных чисел на каждом шаге мы можем сводить тройки к кортежам, требуя всего O(log k) временных шагов.

Но проблема в том, что если мы ограничены только АТД, у нас будет фиксированный набор конструкторов, каждый из которых имеет конечное число записей. Так что несмотря ни на что, глубина такой структуры будет O(log n). И нам нужно выполнить O(log n) шагов только для обхода структуры.

person Petr    schedule 22.11.2015