Barrel shifter

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

Принцип действия устройства быстрого сдвига

Принцип построения схемы быстрого сдвига

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

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

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

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

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

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

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

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

• 128-бит — ${\displaystyle \scriptstyle 128\times \log _{2}(128)=128\times 7=896}$
• 64-бит — ${\displaystyle \scriptstyle 64\times \log _{2}(64)=64\times 6=384}$
• 32-бит — ${\displaystyle \scriptstyle 32\times \log _{2}(32)=32\times 5=160}$
• 16-бит — ${\displaystyle \scriptstyle 16\times \log _{2}(16)=16\times 4=64}$ ^[3]
• 8-бит — ${\displaystyle \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

Примечания

1. An Interconnect-Centric Approach to Cyclic Shifter Design: slide 6
2. Архивная копия от 10 августа 2019 на Wayback Machine: "У 386-го процессора ... заменили последовательный регистр сдвига параллельным (barrel shifter, производит любой вид сдвига на любое число бит за фиксированное время)."
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

Литература

• 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