Гетеромагнитная микроэлектроника (стр. 10 )

Для оценки производительности применялась инструкция rdtsc, возвращающая число циклов процессора с момента последней команды сброса. Фрагмент кода-вставки для занесения числа циклов в переменную res приведен ниже:

__asm { rdtsc mov dword ptr res, eax mov dword ptr res+4, edx };

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

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

При проведении исследований брались стандартные программы, описанные в литературе. Проверялось изменение времени выполнения алгоритмов из-за введенных программных вставок анализа производительности. Во всех экспериментах это время не превышало 1%.

Данные, характеризующие объем вычислений, приходящихся на преобразование форматов данных при решении приведенных задач, отображены в табл. 1 и 2.

Таблица 1

Результаты расчета (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

Таблица 2

Результаты расчета 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. Аппаратурной основой для выполнения данных инструкций являются специальные многоуровневые коммутационные схемы [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. Как видно из рис. 2, данные, соответствующие единичным битам в регистре r3, группируются в начале машинного слова, а данные, соответствующие нулевым битам в регистре r3, –в конце машинного слова. Причем относительный порядок сгруппированных битов данных не меняется.

Рис. 2. Диаграмма преобразований, осуществляемых с использованием инструкций 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 образуется коммутационная схема, для которой доказана возможность осуществления любой перестановки.