По этой причине появляется ряд команд и аппаратурных устройств, осуществляющих специальные перестановки или преобразования форматов. Целью данной статьи является анализ современных подходов к решению проблемы обеспечения высокой производительности вычислительных устройств при обработке битов данных. Проблема исследуется с общей точки зрения преобразования форматов представления данных в вычислительной технике.
Вычислительные затраты при решении задач,
связанных с манипуляциями битов данных
В работе [7] проведен обзор ряда задач, в которых время выполнения команд манипуляции битами данных значительно по сравнению с временем, необходимым для решения задачи. Структура задач, связанных с такими командами, и устройств, осуществляющих преобразования форматов представления данных, представлена на рис. 1.
Детерминированные и вероятностные устройства преобразования
форматов данных
Устройства, выполняющие инструкции манипуляций с битами
данных в процессорах
Устройства аппаратной поддержки формирования случайных разбиений, перестановок и сочетаний элементов данных
Генераторы шума и устройства контроля режимов их функционирования
Сортировка данных
Обработка морфологии изображения
Упаковка изображений и бинарных данных
Стеганография
Биоинформатика
Упаковка изображений и бинарных данных
Преобразование бинарных данных в текстовые строки для передачи
Контроль и коррекция ошибок
Распознание геометрических образов и символов
Медианная фильтрация изображений
Цифровое и аналоговое вещание
Генераторы помех
Обеспечение надёжности генераторов помех
Защита файлов мультимедиа от нелицензионного копирования
Формирование сетки частот в системах с ППРЧ
Ускорение выполнения проектных процедур САПР
Преобразование данных в системах с расширением спектра (RPMA и т.п.)
Организация тестирования
Методы Монте-Карло
Формирование ключей в ситемах защиты
информации
Рис. . Структура задач устройств преобразования форматов (ППРЧ – псевдослучайное переключение радиочастот, САПР – система автоматизированного проектирования)
Из анализа рис. 1 следует, что операции преобразования форматов представления данных используются в широком классе задач, таких как обработка морфологии изображений, сортировка, обработка сигналов в системах RPMA [9], обработка представлений ДНК в биоинформатике, расчет контрольных сумм, коррекция ошибок, стеганография, сжатие и развертывание информации, UUE (Unix-to-Unix encoding) преобразование данных для передачи в текстовом формате, распознавание геометрических символов [7], выполнение криптографических примитивов [10, 11], защита информации [12, 13], построение доверенных систем обработки информации [14], формирование ключей и случайных последовательностей [15, 16], перечисление комбинаторных множеств [17, 18] и т. п. Процедуры преобразования форматов представления данных используются достаточно часто в различных задачах, решаемых средствами вычислительной техники. Важное значение имеет задача оценки потери производительности при выполнении перестановок битов машинного слова традиционными методами.
Какую часть общего времени выполнения алгоритмов занимают преобразования форматов данных?
Исследования проводились с использованием процессора CPU Intel Core 2 Duo E7500 2,93 ГГц/ 3Мб/ 1066МГц.
Для оценки производительности применялась инструкция rdtsc, возвращающая число циклов процессора с момента последней команды сброса. Фрагмент кода-вставки для занесения числа циклов в переменную res приведен ниже:
__asm {
rdtsc
mov dword ptr res, eax
mov dword ptr res+4, edx
};
|
Использовалась следующая процедура оценки времени, затрачиваемого на преобразование формата данных. В исходном тексте исследуемых алгоритмов выделялись фрагменты, соответствующие преобразованиям форматов данных в пределах машинного слова.
В исходный текст программы вносились программные вставки, позволяющие определить число циклов процессора, требуемое на выполнение преобразований форматов данных.
При проведении исследований брались стандартные программы, описанные в литературе. Проверялось изменение времени выполнения алгоритмов из-за введенных программных вставок анализа производительности. Во всех экспериментах это время не превышало 1%.
Данные, характеризующие объем вычислений, приходящихся на преобразование форматов данных при решении приведенных задач, отображены в табл. 1 и 2.
Таблица
Результаты расчета (Tf / T)×100% в задаче сортировки
N подслов данных, имеющих m-разрядов
N
|
Tf / T, %
|
m = 4
|
m = 8
|
m = 16
|
128
|
86
|
88
|
92
|
256
|
76
|
77
|
80
|
512
|
67
|
69
|
71
|
1024
|
61
|
62
|
64
|
2048
|
55
|
56
|
60
|
4096
|
50
|
52
|
55
|
8192
|
48
|
46
|
48
|
16384
|
42
|
42
|
45
|
32768
|
42
|
42
|
41
|
4194304
|
29
|
29
|
31
|
Таблица
Результаты расчета Tf / T для различных задач обработки информации
Задачи обработки информации
|
(Tf /T)×100%
|
Медианная фильтрация изображений
|
78
|
Распознавание геометрических образов и символов на бинарных изображениях
|
50
|
Коррекция морфологии изображений
|
48
|
Упаковка и распаковка данных
|
60
|
LSB-стеганография:
|
|
прямое преобразование
|
45
|
обратное преобразование
|
53
|
UUE:
|
|
прямое преобразование
|
59
|
обратное преобразование
|
62
|
Формирование последовательностей перестановок в системах RPMA
|
91
|
Обработка данных в системах RPMA
|
90
|
Криптографический алгоритм DES
|
57
|
Криптографический алгоритм RC5
|
59
|
Защита файлов мультимедиа от нелицензионного копирования
|
91
|
В табл. 1, 2 представлены результаты расчета отношения затрат машинного времени Tf, приходящихся на преобразование форматов данных, к общим затратам машинного времени T на выполнение задач.
Результаты исследований свидетельствуют о значительных (от 30 до 90%) относительных затратах времени на преобразование форматов данных и необходимости совершенствования программных средств и аппаратурных устройств для решения этой проблемы.
Команды манипуляции битами данных
Инструкции манипуляций битами и подсловами данных согласно материалам из [19, 20], а также инструкции, предлагаемые в академических исследованиях [1], представлены в табл. 3.
Рассматривая инструкции манипуляций битами и подсловами данных, можно выделить логические операции между битами машинного слова и операции преобразования форматов данных, в которых биты машинного слова перемещаются на новые позиции. На практике побитовые операции и операции преобразования форматов представления данных часто объединяются.
Наиболее перспективными являются универсальные инструкции преобразования форматов данных. Различными авторами были предложены инструкции grp r1 = r2, r3 [1] и grpm r1 = r2, r3 [21, 22], где r1 – регистр выходных данных, r2 – регистр входных данных, r3 – регистр битов управления перестановкой. Эти инструкции иллюстрирует рис. . Аппаратурной основой для выполнения данных инструкций являются специальные многоуровневые коммутационные схемы [2].
Таблица 3
Инструкции манипуляций битами и подсловами данных
Типы инструкций
|
Процессор
|
POWER
|
IA-32/AMD64
|
Itanium
|
Другие
|
Инструкции, работающие со словами:
|
|
|
|
–
|
основные
|
Shift
|
Shift, rotate
|
Shift
|
составные
|
Rotate-and-clear, rotate-mask-and-insert, double shift
|
Subword extract, deposit,
pext, pdep,
subword insert, insert, double shift
|
Extract, deposit,
shift pair
|
аналитические
|
Count leading zeros
|
Population count, count leading zeros,
count trailing zeros
|
Population count
|
Инструкции, работающие с подсловами:
|
|
|
|
|
параллельные операции
|
Parallel shift and rotate,
parallel population count
|
Parallel shift and rotate
|
Parallel shift
|
Group-withdraw,
group-deposit
|
специализированные перестановки
|
Merge
|
Unpack
|
Unpack, mix
|
Mixpair
|
–
|
Select
|
-
|
Select
|
–
|
Reverse
|
Reverse
|
–
|
Splat
|
Duplicate, broadcast
|
Broadcast
|
–
|
–
|
–
|
Misc
|
Exchange, excheck,
group-shuffle,
group-swizzle
|
основные перестановки
|
Vperm
|
Pshufb, pshufw, pshufd, shuf, perm, pperm, vperm
|
Mux2
|
Select-bytes
|
Инструкции битового уровня:
|
|
|
|
|
битовые
|
Logical, select
|
Logical, select
|
Logical
|
–
|
специализированные перестановки
|
–
|
Mask extract
|
–
|
–
|
основные перестановки
|
–
|
–
|
–
|
Grp, bsn, grpm,
rearrangement cross, omflip, bfly, ibfly, bpi,
xbox, pperm, swperm, sieve, group-8-mux,
group-transpose-8-mux
|
Было доказано [22], что произвольную перестановку битов можно осуществить с использованием инструкций grp за log2(n) шагов, где n – длина регистров r1, r2, r3. Как видно из рис. , данные, соответствующие единичным битам в регистре r3, группируются в начале машинного слова, а данные, соответствующие нулевым битам в регистре r3, –в конце машинного слова. Причем относительный порядок сгруппированных битов данных не меняется.
r1
r1
r3
r2
r3
r2
grp r1 = r2, r3
grpm r1 = r2, r3
bsn r1 = r2, ar.b1, ar.b2, ar.b3
r2
r1
ar.b1
ar.b2
ar.b3
|
