Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Прелести вентилей Фредкина

Вентиль Фредкина, также известный как Controlled Swap и симметрический переключатель — замена транзистора в цифровой технике будущего. Переключатели обратимые и консервативные (выходит столько же единиц и нулей, сколько входило), а значит спинтронные переключатели такого типа скорее всего удастся сделать очень маленькими, очень быстрыми и очень эффективными. А переключатели это очень практичные. Клонирование сигнала, not, and, or, and not и implicates можно реализовать одним переключателем. nand, nor, xor и xnor всего двумя.


Однобитный сумматор требует четырёх вентилей и срабатывает за 2·τ, где τ — время прохождения сигналом от входа одного вентиля до входа другого, см. изображение справа. Сумматоры большей разрядности можно делать из одного однобитного сумматора и (n - 1) трёхбитных суммирующих блоков. Минимальные по размеру трёхбитные суммирующие блоки состоят из четырёх вентилей:


Однако, такие блоки работают довольно медленно: сложение n-битных чисел занимает (2n + 1)·τ, при том что используются (4n - 2) блоков. Существуют оптимизированные по скорости (неминимальные по размеру) трёхбитные сумматоры. Лучший известный автору вариант выглядит следующим обазом:


Эти блоки можно соединять как последовательно, реализуя сложение в столбик, так и деревом, реализуя сложение Когге-Стоуна.
Сложение в столбик занимает (n + 2)·τ и требует (7·n - 3) вентилей.
Сложение Когге-Стоуна занимает ⌈3 + log₂(n)⌉·τ и использует дополнительных вентилей ⌈n·log₂(n)⌉.

В случае 64-битных чисел, сложение в столбик потребует 66τ и 445 вентилей, а сложение Когге-Стоуна потребует 9τ и 957 вентилей. Компромиссные варианты, работающие за 10-12τ могут обходиться ≈500 вентилями. В предположении, что удастся реализовать баллистические (т.е. не привносящие задержки в передачу сигнала) переключатели Фредкина размеров порядка применяемых в сегодняшних процессорах транзисторов, сложение двух 64-битных можно будет производить (в совершенно реалистичных предположениях) с частотой порядка по меньшей мере миллионов ГГц.

* В тексте использованы материалы и изображения из cтатьи Bruce, Thornton et al., “Efficient Adder Circuits Based on a Conservative Reversible Logic”, Mississippi State University, IEEE 0-7695-1486-3/02, 2002.
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments