1100
1111
1001
Рис. . Диаграмма преобразований, осуществляемых с использованием инструкций bsn, grpm, grp
Инструкции grp и grpm используются при осуществлении инструкций pdep параллельного размещения и pext параллельного извлечения, которые согласно [20] включены в микроархитектуру процессоров фирмы Intel в 2015 г.
В работе [19] были описаны инструкции bfly r1 = r2, ar.b1, ar.b2, ar.b3 и ibfly r1 = r2, ar.b1, ar.b2, ar.b3, где ar.b1, ar.b2, ar.b3 – регистры, хранящие биты управления перестановкой. При соединении коммутационных схем butterfy и inverse butterfy образуется коммутационная схема, для которой доказана возможность осуществления любой перестановки.
Таким образом, любое преобразование формата представления данных в регистре r2 осуществляется путем выполнения двух инструкций bfly и ibfly.
Управление переключателями, расположенными в узлах коммутационной схемы, выполняется с использованием битов, находящихся в регистрах ar.b1, ar.b2, ar.b3.
В работе [23] была описана инструкция bsn r1=r2, ar.b1, ar.b2, ar.b3 для выполнения статических перестановок битов машинного слова, в работе [24] авторами предложено устройство для выполнения инструкции bsn. Произвольная перестановка выполняется путем использования двух инструкций bsn. Преимуществом применения инструкции bsn является упрощение аппаратурной части для ее реализации [21]. Инструкции bsn, bfly и ibfly удобны для осуществления статических преобразований форматов данных, когда биты управления в регистрах ar.b1, ar.b2, ar.b3 известны до выполнения программы и могут быть вычислены при ее компиляции. Динамические перестановки с использованием инструкций bsn, bfly и ibfly не эффективны, поскольку определение битов управления в регистрах ar.b1, ar.b2, ar.b3 представляет собой последовательный алгоритм, выполнение которого занимает значительное время. Попытки разработки аппаратуры для определения битов управления коммутационной схемой приводят к неоправданно сложным решениям.
Проблемы разработки аппаратурных средств
преобразования форматов данных
Для быстрого выполнения операций манипуляции битами данных был разработан процессор [21, 25], упрощенная блок-схема схема центрального процессорного устройства (CPU) которого изображена на Рис. . Кроме блока регистров, арифметико-логического устройства и устройства логического сдвига данных, процессор включает модуль выполнения перестановок или преобразования форматов представления данных. Данные из входного регистра поступают на модуль перестановок. Результат записывается в выходной регистр.
Регистры
АЛУ
Сдвиг
Модуль
перестановок
Данные
Результат
Биты
управления
n
n
n
Рис. . Блок-схема процессора с модулем выполнения перестановок
В работе [26] показано, что модули, осуществляющие перестановки последовательно, не обладают достаточным быстродействием, поэтому далее анализируются только устройства, выполняющие преобразование форматов представления данных параллельно.
В работе [1] в качестве основного компонента модуля перестановок было предложено использовать так называемую многоуровневую коммутационную схему с топологией butterfly. Схема состоит из двух частей: прямого butterfly (bfly) и обратного inverse butterfly (ibfly) преобразования. Она содержит 2log2(n) уровней преобразования. В узлах схемы расположены переключатели, имеющие два входа и два выхода, которые в зависимости от значения бита управления осуществляют транспозицию битов входных данных на своих выходах либо передают данные без изменения. Для управления одним уровнем переключателей требуется n/2 бит, поэтому битами одного регистра процессора можно управлять двумя уровнями сети.
Схема модуля, выполняющего инструкцию grp (см. рис. 1), представлена на рис. 4.
64-разрядное слово
бит данных и бит управления
GRP1Z
GRP2ZD/S
GRP4ZD/S
GRP32ZD/S
GRP64ZD
64-разрядный элемент ИЛИ
Выход
64-разрядное слово инвертированных бит данных и бит управления
в обратном порядке
Рис. . Структура модуля выполнения инструкции grp
Операция grp состоит из трех шагов. На первом шаге группируются z-биты, соответствующие нулевым битам управления в регистре r3. На втором – w-биты, соответствующие единичным битам управления в регистре r3. На третьем осуществляется операция слияния результатов двух предшествующих шагов.
Схема группировки z-битов расположена слева, а w-битов – справа (см. Рис. ). Для группировки w-битов на схему подаются инвертированные биты управления. Процедуры, выполняемые блоками GRPZD, иллюстрируются на рис. 5.
Каждый блок GRPnZD осуществляет группировку z-битов в строке длиной n бит, состоящей из двух строк длиной по n/2, содержащих сгруппированные биты. Эта операция осуществляется с использованием схемы, представленной на Рис. , где изображен блок GRP8ZD.
n/2 битов
n битов
z биты
остальные биты
n/2 битов
Рис. . Рекурсивная группировка z-битов
S0
S1
S2
S3
S4
I0
I1
I2
I3
I4
I5
I6
I7
0
O0
O1
O2
O3
O4
O5
O6
O7
Рис. . Структурная схема блока GRP8ZD
Базовый элемент блока GRP8ZD изображен на Рис.7. Он имеет входы данных I0–I7, выходы данных O0–O7, и управляющие входы S0–S7. Выходы O0-O7 соединяются с входами I0–I7 только при высоком уровне сигнала на входах S0–S7.
S
I
O
Рис. 7. Базовый элемент
блока GRP8ZD
В блоке GRP8ZD входы (I0, I1, I2, I3) и (I4, I5, I6, I7) соединены с выходами двух блоков GRP4ZD, каждый из которых имеет z-биты слева, а заполняющие нули справа. В зависимости от количества нулей на входах (I0, I1, I2, I3) один из сигналов (S4, S3, S2, S1, S0) устанавливается в 1. Этот бинарный сигнал обозначает номер строки с базовыми элементами, выходы которых соединены с входами. Нули на входах (I0, I1, I2, I3) замещаются сдвинутыми битами на входах (I4, I5, I6, I7). Например, когда логические значения на входах (I0, I1, I2) являются z-битами, а на вход I3 подается заполняющий ноль, только сигнал S1 устанавливается в 1. Входы и выходы соединены во втором ряду, т. е. (O0,…,O7) = (I0, I1, I2, I4, I5, I6, I7).
Недостатком данного решения являются большая сложность устройства, реализующего инструкции grp, и его низкое быстродействие. Площадь, занимаемая данным модулем на кристалле, в несколько раз превышает площадь арифметико-логического устройства (АЛУ), а задержка превосходит задержку АЛУ.
Попыткой улучшить ситуацию является использование для выполнения операции grp топологии сортирующей сети bitonic [27]. Структурная схема предложенного в [27] устройства изображена на рис. 8. Схема представляет собой иерархию блоков EBS (enhanced bitonic sorters).
Двухбитный EBS
НВ
LВ
Четырёхбитный EBS
Пары маркированных битов данных
и битов управления
EBS
2
EBS
EBS
EBS
2
4
2
4
EBS
EBS
8
EBS
A0,C0
0
2
3
4
5
6
7
1
Восьмибитный EBS
НВ
LВ
НВ
LВ
НВ
НВ
LВ
LВ
НВ
НВ
НВ
НВ
НВ
НВ
НВ
LВ
LВ
LВ
LВ
LВ
LВ
LВ
LВ
НВ
A7,C7
A6,C6
A5,C5
A4,C4
A3,C3
A2,C2
A1,C1
A0,C0
НВ
LВ
НВ
LВ
НВ
LВ
НВ
LВ
2
A7,C7
Рис. 8. Восьмибитный grp-модуль на базе структуры сортирующей сети bitonic
Схема выполнения инструкции grp представлена на рис. 9. Как можно заключить из рис. 8, подход, используемый в работе [27], аналогичен ранее рассмотренному подходу, предложенному в [28]. Недостатками данного решения также являются большая сложность аппаратурного устройства и его низкое быстродействие. При этом рассмотренные устройства имеют близкие параметры.
a7
a6
a5
a4
a3
a2
a1
a0
Биты управления
Биты данных
1
0
1
0
0
0
1
0
a7
a6
a5
a4
a3
a2
a1
a0
a7
a6
a5
a4
a3
a2
a1
a0
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
1
Маска «И»
Маска «И»
а7
0
а5
0
0
0
а1
0
Модуль извлечения
0
а6
0
а4
а3
а2
0
а0
а7
0
а5
0
0
0
а1
0
Модуль извлечения
0
Путь данных слева
Путь данных справа
а6
а4
а3
а0
а7
а5
а1
а2
0
0
а6
а4
а3
а2
а0
Рис. 9. Cхема выполнения инструкции grp
Наиболее продвинутым решением является универсальный модуль выполнения инструкций pdep и pext, базирующихся на grp, предложенный в [2]. В данном решении также используется схема раздельной группировки битов, соответствующих нулевым и единичным битам управления в регистре r3. Сгруппированные биты подвергаются операции слияния на третьем шаге. Предложенное решение основано на многоуровневой коммутационной схеме с топологией butterfly и inverse butterfly. Структурная схема устройства, осуществляющего группировку w-бит, представлена на рис. 10.
Модуль parallel prefix population count осуществляет расчет числа единиц в подсловах длиной 64, 32, 16, 8, 4 и 2 бита. Для выполнения данного расчета в работе [3] предложена структура сети, состоящая из сумматоров.
Модули LROTC осуществляют циклический сдвиг строк длиной 32, 16, 8, 4 и 2 бита. Схема восьмибитного LROTC представлена на рис. 11.
Модуль подсчёта битов данных
32
32×1
16×2
8×3
4×4
2×5
1×6
2×16-bit LROTC
1×32-bit LROTC
16×2-bit LROTC
8×4-bit LROTC
4×8-bit LROTC
64: 192 дешифратор
32
32
32
32
32
32
64
Битовая маска
Ibfly
Ibfly
Уровень 1
Ibfly
Уровень 2
Ibfly
Уровень 3
Ibfly
Уровень 4
Ibfly
Уровень 5
Ibfly
Уровень 6
Рис. 10. Структурная схема устройства, группирующего w-биты
Восьмибитный LROTC
Count0
Count1
Count2
Count3
Out7
Out6
Out5
Out4
Out3
Out2
Out1
Out0
Рис. 11. Схема восьмибитного LROTC
Недостатком данного решения является увеличение времени задержки и усложнение устройства за счет необходимости использования модулей LROTC.
В работах [29, 30] были предложены способы построения универсальных устройств, выполняющих упорядоченные разбиения входных данных. В частном случае разбиения перестановки битов машинного слова выполнялись с использованием многоуровневой коммутационной схемы baseline. На базе данных устройств был разработан модуль, реализующий инструкции pdep и pext и новые инструкции bsn и grpm [23, 21]. В связи с отсутствием модулей LROTC формирование битов управления многоуровневой коммутационной схемой baseline происходит быстрее, чем схемой с топологией butterfly или inverse butterfly. Тем не менее задержки преобразования слишком велики для выполнения инструкций pdep, pext, grpm за один такт микропроцессора [22]. Выполнение инструкций bsn требует наличия дополнительных регистров, отсутствующих в CPU RISC микропроцессоров.
Таким образом, существующие специальные устройства для преобразования форматов данных не обладают необходимой универсальностью и гибкостью или создают существенные задержки при обработке данных и сложны в аппаратурном исполнении.
В статье проведен аналитический обзор задач, решаемых средствами вычислительной техники, в которых преобразование форматов данных занимает значительную часть общего объема вычислений. На основе проведенных авторами исследований показано, что затраты машинного времени на преобразования форматов данных в исследованных задачах составляют от 30 до 90% в широком классе задач.
На основе анализа новых инструкций манипуляции битами данных показано, что большинство из них специализированные и имеют ограниченную функциональность. Наиболее универсальными являются инструкции параллельной выборки pext, размещения pdep, введенные в 2015 г. в микроархитектуру Intel 64 and IA-32. Аппаратурная часть, осуществляющая данные инструкции, по-видимому, основана на многоуровневых коммутационных схемах butterfy и inverse butterfy. Устройство, формирующее биты управления этими коммутационными схемами, достаточно сложно в аппаратурном исполнении, так как содержит модули parallel prefix population count, осуществляющие расчет числа единиц в подсловах длиной 64, 32, 16, 8, 4 и 2 бита, и модули LROTC, осуществляющие циклический сдвиг строк длиной 32, 16, 8, 4 и 2 бита.
Более перспективным с точки зрения задержек преобразования и аппаратурной сложности являются многоуровневые коммутационные схемы baseline. Тем не менее задержки преобразования слишком велики для выполнения инструкций pdep, pext, grpm за один такт микропроцессора. Выполнение инструкций bsn требует наличия дополнительных регистров, отсутствующих в CPU RISC микропроцессоров. Инструкции bsn, bfly, ibfly произвольных перестановок и группировок битов данных grp, grpm в настоящее время в системах команд микропроцессоров не используются.
Показано также, что существующие специальные устройства для преобразования форматов данных не обладают необходимой универсальностью и гибкостью или создают существенные задержки при обработке данных, сложны в аппаратурном исполнении и требуют для осуществления дополнительных регистров CPU, отсутствующих в микроархитектуре современных RISC микропроцессоров.
Таким образом, представляет интерес дальнейшее развитие микропрограммных и аппаратурных средств, направленное на увеличение производительности процессоров при выполнении преобразований форматов представления данных.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Hilewitz Y., Lee R. B. Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors // J. of Signal Processing Systems. 2008. Vol. 53. № 1–2. Р. 145–169.
Pat. 9134953 B2 USА, МПК G06F 5/01 (20060101), G06F 7/76. Microprocessor Shifter Circuits Utilizing Butterfly and Inverse Butterfly Routing Circuits, and Control Circuits Therefor / applicant Lee R. B., Hilewitz. Y. ; аssignee Teleputers, LLC. – № 13/647861 ; filed 9.10.2012 ; publication date 15.09.2015. URL : http://patft.uspto.gov/netahtml/ PTO/search-bool.html (дата обращения : 24.11.2015).
Пат. 2488161 Российская Федерация, МПК G0 6F 11/00. Устройство перестановок и сдвигов битов данных в микропроцессорах / заявитель Сотов Л. С. ; патентообладатель Сарат. гос. ун-т им. Н. Г. Чернышевского. – № 2011145864/08 ; заявл. 14.11.2011 ; опубл. 20.07.2013, Бюл. № 20. 27 с.
Молодченко Ж. А., Харин В. Н., Сотов Л. С. Алгоритм создания диверсификационного метода битовых преобразований // Естественные и технические науки. 2007. № 6. С. 222–225.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Математические модели транспозиционных преобразований // Информационно-измерительные и управляющие системы. 2007. Т. 5, № 12. С. 58–60.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Модели аппаратных функциональных формирователей перестановок // Информационно-измерительные и управляющие системы. 2009. Т. 7, № 10. С. 78–84.
Сотов Л. С. Об эффективности использования специальных команд преобразования форматов данных в вычислительной технике // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 61–80.
Ляшенко А. В., Сотов Л. С. Простой матричный формирователь r-выборок // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 47–56.
Ляшенко А. В., Сотов Л. С., Хвалин А. Л., Чесаков В. С. Микропроцессор с ускоренной манипуляцией битами данных для обработки сигналов в системах связи // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2015. Вып. 18 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 72–81.
Молдовян Н. А., Молдовян А. А., Алексеев Л. Е. Молдовян Н. А., Молдовян А. А., Алексеев Л. Е. Перспективы разработки скоростных шифров на основе управляемых перестановок // Вопр. защиты информации. 1999. № 1. C. 41–47.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Математические модели стохастического формирования изоморфных представлений структурных элементов данных в ЭВМ // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Устройства различного назначени. С. 29–41.
Сотов Л. С., Харин В. Н. Концепция ТСВ-платформы для распределенных информационно-вычислительных систем специального назначения // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 3 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. С. 66–72.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Аппаратный акселератор сервера форматирования данных // Надежность и качество : тр. междунар. симпозиума : в 2 т. Пенза : Изд-во Пензенск. ун-та, 2007. Т. 1. С. 134–136.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. О формировании доверенной среды серверных систем у правления базами данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 3. С. 23–27.
Ляшенко А. В., Сотов Л. С. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 57–72.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Cтруктура подсистемы стохастической генерации дескрипторов форматов // Аспирант и соискатель. 2009. № 4. С. 86–88.
Соболев С. С., Сотов Л. С., Харин В. Н. Алгоритм работы и модель функционального генератора перестановок // Информационные технологии. 2010. № 4. С. 41–46.
Сотов Л. С. Комбинаторная модель функционального формирователя разбиений бинарного множества // Информационные технологии. 2010. № 10. С. 46–52.
Hilewitz Y. Advanced bit manipulation instructions : architecture, implementation and applications. 2008. 161 p. URL : http://www.cse.uconn.edu/~zshi/course/cse5302/ref/ yhilewitz_thesis.pdf (дата обращения : 24.11.2015).
Intel 64 and IA-32 Architectures Software Developer’s Manual Volume 2B : Instruction Set Reference, N-Z. URL : http://www.intel.com/content/dam/www/public/us/en/ documents/manuals/64-ia-32-architectures-software-developer-vol-2b-manual.pdf (дата обращения : 24.11.2015).
Назаров С. И., Сотов Л. С., Ляшенко А. В. Процессор с улучшенной манипуляцией битами данных для средств навигации, обработки сигналов и изображений, криптографии, мобильных диагностических устройств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 16 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 51–63.
Сотов Л. С., Ачкасов В. Н. Универсальный модуль манипуляции битами данных в микропроцессорах // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 11 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 57–73.
Сотов Л. С. Методы синтеза устройств, выполняющих инструкции перестановки битов данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 25–50.
Молодченко Ж. А., Харин В. Н., Овчинников С. В., Сотов Л. С. Модели аппаратных акселераторов перестановок бинарных множеств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Устройства различного назначения. С. 11–23.
Назаров С. И., Ляшенко А. В., Сотов Л. С., Хвалин А. Л. Проектирование микропроцессора c расширенным набором команд манипуляции битами данных на базе архитектуры OPENRISC1200 // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 17 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 50–65.
Пат. 2320000 Российская Федерация, МПК G0 6F 7/76, G0 6F 12/14. Дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ / заявители Молодченко Ж. А., Сотов Л. С., Харин В. Н. ; патентообладатель Сарат. гос. ун-т им. Н. Г. Чернышевского. – № 2007105175/09 ; заявл. 13.02.2007 ; опубл. 20.03.2008, Бюл. № 8. 6 с.
Giorgos D., Christos M., Sorter Based Permutation Units for Media-Enhanced Microprocessors // IEEE transactions on very large scale integration (VLSI) systems. 2007. Vol. 15, №. 6. P. 711–715.
Сотов Л. С. Аппаратные устройства формирования прямых и обратных перестановок данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 9 : Магнитоэлектроника. Микро- и наноструктуры. Прикладные аспекты. Проблемы физического образования. С. 61–77.
Соболев С. С., Харин В. Н., Сотов Л. С. Модели устройств кластерных перестановок данных в ЭВМ // Вестн. компьютерных и информационных технологий. 2009. № 12. С. 51–55.
Сотов Л. С., Соболев С. С., Харин В. Н. Кластерная коммутационная матрица для аппаратной поддержки управляемой перестановки данных в криптографических системах // Проблемы информационной безопасности. Компьютерные системы. 2009. № 4. С. 56–63.
УДК 50.41.00 |
