Barrel shifter (Barrel shifter)

Barrel shifter (устройство быстрого сдвига) — цифровая электронная схема, производящая сдвиг данных на указанное число позиций за один такт синхронизации. Устройство быстрого сдвига также может производить циклический сдвиг и расширение знакового бита.

На вход устройства подаётся две группы входных данных по N бит каждая и N управляющих сигналов, на выходе получается N бит данных. Количество разрядов, на которые производится сдвиг, определяется позицией управляющего сигнала высокого уровня (все остальные управляющие сигналы должны иметь низкий уровень), выполняемая операция определяется подачей входных данных. Например:

при подаче данных на «вход 1» и нулей на «вход 0» будет произведён правый сдвиг;
при подаче данных на оба входа будет произведён циклический сдвиг.

Устройство быстрого сдвига применяется в целочисленных арифметических операциях (где сдвиг на один разряд эквивалентен умножению или делению на два) и в операциях над числами с плавающей запятой для выравнивания операндов при выполнении сложения и вычитания. Мантисса числа, имеющего меньший порядок, сдвигается вправо, количество позиций, на которые производится сдвиг, равно разнице порядков чисел. После сдвига порядки чисел становятся равными.

Недостатки (для barrel shift, реализующего циклический сдвиг):^[1]

Входная ёмкость пропорциональна разрядности N.
Количество транзисторов пропорционально квадрату разрядности N²
Требуется декодер для формирования управляющих сигналов.

В процессорах x86 применяются, начиная с Intel 80386.^[2]

Ресурсоёмкость

Количество мультиплексоров, необходимое для реализации n-битового устройства сдвига, по схеме barrel составляет $\scriptstyle n\log _{2}n$ ^[3]. Для пяти часто используемых размеров количество мультиплексоров составляет:

128-бит — $\scriptstyle 128\times \log _{2}(128)=128\times 7=896$
64-бит — $\scriptstyle 64\times \log _{2}(64)=64\times 6=384$
32-бит — $\scriptstyle 32\times \log _{2}(32)=32\times 5=160$
16-бит — $\scriptstyle 16\times \log _{2}(16)=16\times 4=64$ ^[3]
8-бит — $\scriptstyle 8\times \log _{2}(8)=8\times 3=24$ ^[3]

Стоимость критического пути в единицах Fan-out-of-4 (FO4) оценивается (без учёта задержки в проводниках) как:

32-bit: от 18 FO4 до 14 FO4^[4]

См. также

Logarithmic Shifter

Примечания

↑ An Interconnect-Centric Approach to Cyclic Shifter Design: slide 6
↑ [1] Архивная копия от 10 августа 2019 на Wayback Machine: "У 386-го процессора ... заменили последовательный регистр сдвига параллельным (barrel shifter, производит любой вид сдвига на любое число бит за фиксированное время)."
↑ ¹ ² ³ * VLSI Implementation of a Barrel Shifter Архивировано 2 октября 2013 года. // Proceedings of SPIT-IEEE Colloquium and International Conference, Mumbai, India Vol2, 150
↑ David T. Wang, Revisiting the FO4 Metric. Estimating the FO4 depth of the critical path Архивная копия от 13 марта 2012 на Wayback Machine // RealWorldTech, August 15, 2002

Литература

Wayne Wolf. 6.2 Combinational Shifters // Modern VLSI Design: IP-Based Design. — 4th ed.. — Prentice Hall, 2009. — 627 p. — (Prentice Hall Modern Semiconductor Design Series). — ISBN 0137145004.

Ссылки

Design alternatives for barrel shifters, Matthew R. Pillmeier
VLSI Implementation of a Barrel Shifter // Proceedings of SPIT-IEEE Colloquium and International Conference, Mumbai, India Vol2, 150
Barrel Shifters // Bill Cowan, CS251 – Spring 2008
An Interconnect-Centric Approach to Cyclic Shifter Design
Shifters and Adders // Somayyeh Koohi

[1] An Interconnect-Centric Approach to Cyclic Shifter Design: slide 6

[2] [1] Архивная копия от 10 августа 2019 на Wayback Machine: "У 386-го процессора ... заменили последовательный регистр сдвига параллельным (barrel shifter, производит любой вид сдвига на любое число бит за фиксированное время)."

[spit-64-24-3] ¹ ² ³ * VLSI Implementation of a Barrel Shifter Архивировано 2 октября 2013 года. // Proceedings of SPIT-IEEE Colloquium and International Conference, Mumbai, India Vol2, 150

[4] David T. Wang, Revisiting the FO4 Metric. Estimating the FO4 depth of the critical path Архивная копия от 13 марта 2012 на Wayback Machine // RealWorldTech, August 15, 2002

[1]

[2]

[3]

[4]