БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Херрис Дж. Использование окон при гармоническом анализе методом дискретного преобразования Фурье // ТИИЭИР. 1978. Т. 66. С. 60–67.
Кузнецов С. П., Сотов Л. С. К оценке спектральной плотности мощности сигналов, генерируемых динамическими системами // Радиотехника и электроника. 1990. Т. 35, № 11. C. 2307–2312.
Заславский Г. М. Стохастичность динамических систем. М. : Наука, 1984. 10 с.
Сотов Л. С., Харин В. Н., Хвалин А. Л. Детекторы режимов функционирования генераторов случайных сигналов // Автоматика и телемеханика. 2010. № 5. С. 166–170.
Сотов Л. С., Харин В. Н., Хвалин А. Л. Встроенные средства контроля генераторов случайных сигналов // Приборы и системы. Управление, контроль, диагностика. 2010. № 7. С. 30–33.
Коваленко М. Л., Сотов Л. С. Исследование двухдоменной модели сферического микрорезонатора на основе железоиттриевого граната в ненасыщенном режиме // Гетеромагнитная микроэлектроника : сб. докл. и ст. II и III науч.-техн. совещ. Саратов : Изд-во Сарат. ун-та, 2005. Вып. 2 : Методы проектирования магнитоэлектронных устройств. С. 30–53.
Сотов Л. С., Харин В. Н. Цифровой генератор подкачки энтропии на базе отображения Арнольда // Изв. вузов. Прикладная нелинейная динамика. 2009. Т. 17, № 6. С. 57–66.
Хвалин А. Л., Сотов Л. С., Россошанский А. В. Цифровой формирователь случайных сигналов на базе сдвиговых регистров // Радиотехника. 2014. № 10. С. 68–73.
Ляшенко А. В., Сотов Л. С. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 :. Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 57–72.
Соболев С. С., Сотов Л. С., Харин В. Н. Устройство функционального генератора перестановок // Моделирование систем и процессов. 2011. № 1–2. С. 59–64.
Соболев С. С., Сотов Л. С., Харин В. Н. Алгоритм работы и модель функционального генератора перестановок // Информационные технологии. 2010. № 4. С. 41–46.
Хвалин А. Л., Сотов Л. С., Овчинников С. В., Кобякин В. П. Экспериментальные исследования гибридного интегрального магнитоуправляемого генератора // Приборы и системы. Управление, контроль, диагностика. 2009. № 11. С. 42–44.
Хвалин А. Л., Сотов Л. С., Васильев А. В. Расчет характеристик интегрального магнитоуправляемого генератора в диапазоне частот 26,0 … 37,5 ГГЦ // Приборы и системы. Управление, контроль, диагностика. 2010. № 11. С. 47–49.
Сотов Л. С., Хвалин А. Л. Средства разработки и исследования архитектурных моделей в САПР SYSTEM STUDIO : в 2 ч. Ч. 1. Использование инструментов SYSTEM STUDIO при моделировании матричного генератора перестановок // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 5 : Прикладные аспекты микро- и наноэлектроники. С. 121–145.
Сотов Л. С., Хвалин А. Л. Средства разработки и исследования архитектурных моделей в САПР System Studio : в 2 ч. Ч. 2. Основные объекты SYSTEMC и их использование // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 5 : Прикладные аспекты микро- и наноэлектроники. С. 146–176.
УДК 50.41.00
СРАВНИТЕЛЬНАЯ ОЦЕНКА АППАРАТУРНОЙ СЛОЖНОСТИ
ПРЕОБРАЗОВАТЕЛЕЙ ФОРМАТОВ ДАННЫХ
В. А. Малярчук
Саратовский национальный исследовательский
государственный университет имени Н. Г. Чернышевского
Россия, 410012, Саратов, Астраханская, 83
E-mail: kof@info.sgu.ru
Проведен сравнительный анализ аппаратурной сложности устройств преобразования форматов представления данных. Результаты исследований позволяют выбрать наиболее эффективные решения данной задачи.
Ключевые слова: многоуровневые коммутационные схемы, разбиение множества, перестановка, кластер, криптографический шифр, псевдослучайная перестановка.
Comparativ Assessment of Data Formats
Converters Hardware Complexity
V. A. Malyarchuk
The comparative analysis of hardware complexity of devices of transformation of formats of data is carried out. Results of researches allow to choose the most effective devices for the solution of this problem.
Key words: multistage interconnection networks, partition of a set, permutation, cluster, cryptography cipher, pseudo-random shuffling.
Преобразования форматов представления данных и связанные с ними перестановки бинарных множеств часто встречаются в прикладных задачах [1, 2]. В системах защиты информации преобразования форматов данных используются при управлении хранилищами [3, 4] и базами данных [5, 6], в качетстве примитивов крипторгафических шифров [7, 8] для генерации случайных чисел с равномерным распределением вероятностей [9, 10]. В телекоммуникационных системах бинарные перестановки используются для обеспечения быстрого кодирования информации [11, 12] и расширения спектра при кодовом разделении каналов [13, 14].
Аппаратурные средства для ускорения перестановок бинарных множеств позволяют от двух до десяти раз увеличить производительность микропроцессоров при решении широкого круга задач [15, 16]. Современные микропроцессоры осуществляют перестановку битов машинного слова за две операции [17, 18].
Для ускорения проектных процедур аппаратурные формирователи перестановок используются в системах автоматизированного проектирования [19, 20].
В данной статье проведен краткий обзор существующих подходов к построению аппаратурных преобразователей форматов представления данных, а также расчет и сравнительный анализ аппаратурной сложности этих преобразователей.
С технической точки зрения транспозиционные преобразователи – достаточно сложные устройства. При этом следует различать однотактные преобразователи, которые формируют перестановку за один такт внешнего генератора тактовых импульсов и устройства, осуществляющие перестановку за много раундов преобразований. Для однотактных устройств время, необходимое для выполнения преобразования, практически не зависит от длины перестановки n. Для остальных преобразователей это время увеличивается с ростом n. Скорость роста определяется комбинаторной моделью, положенной в основу формирователя перестановки, при этом с уменьшением времени преобразования увеличивается аппаратурная сложность преобразователя [21].
При разработке средств динамического форматирования данных в вычислительной технике необходимо учитывать два обстоятельства, обусловливающих необходимость минимизации аппаратной сложности преобразователей формата:
при большой длине преобразуемых строк реализация устройств, осуществляющих данные преобразования, может оказаться технически невозможной. Аппаратурная сложность известных однотактных функциональных формирователей перестановок элементов строк длиной n растет не медленнее n2, что делает технически невозможным использование таких устройств при больших значениях n;
дескрипторы формата, образующие среду форматирования, необходимо представлять в компактном виде с минимизацией операций их преобразования в управляющие коды транспозиционного преобразователя. Действительно, аппаратурная сложность устройств преобразования форматов определяется количеством управляемых переключающих элементов, следовательно, длина управляющего кода находится в прямой зависимости от аппаратной сложности преобразователя.
Вто же время упрощение конструкции преобразователя формата приводит к необходимости многоуровневой обработки и сокращает скорость выполнения операции конверсии форматов данных [22].
Число переключателей T(n) коммутационной матрицы nn, обеспечивающей максимальную скорость преобразования, определяется выражением
Наиболее простую аппаратную реализацию имеют формирователи упорядоченных разбиений бинарных множеств с последовательной загрузкой, описанные в [23], число логических элементов TB(n, u) матрицы дешифратора таких преобразователей составляет
где 2u – число элементов множеств разбиения.
Но данные формирователи осуществляют преобразование форматов за n тактов, и длина кода управления преобразованием в битах RB(n, u) составляет
Функциональные формирователи перестановок можно строить на основе многоуровневых коммутационных сетей. Оценка сложности оптимальной неблокирующей коммутационной схемы без перестроения дана в [24], минимальное число ребер в коммутационном графе которой составляет
R(n) ≥ n·log2n + 0(n)
и не превосходит значения
R(n) ≤ 67,65 n log2n + 0(n) при n = 17·4k,
где  – любое целое положительное число.
В работе [24] проводится сравнение известных коммутационных схем. Наиболее эффективными оказываются коммутационные схемы с перестроением. Для них число переключателей Tb(n) с двумя входами и двумя выходами определяется выражением
Tb(n) = n(log2(n) – 1).
При минимизации числа переключателей в сетях Бенеша на первом уровне можно исключить один переключатель, на втором – два и т. д. [25, 26]. Таким образом, число переключателей входной части коммутационной матрицы определяется рядом
 .
Если обозначить k = log2n, число переключателей T1(n) входной части коммутационной матрицы составит
 ,
|
()
|
а всей матрицы –
ТВО(n) .
|
()
|
Для матричных преобразователей, осуществляющих упорядоченное разбиение исходного множества на 2k–u подмножеств мощности 2u [10], число переключателей TBМ коммутационной матрицы составляет
 .
|
()
|
Число переключателей ТМО транспозиционного преобразователя на базе односторонней коммутационной матрицы составляет
|
()
|
Оценку минимальной аппаратной сложности однотактных преобразователей можно провести исходя из информационной емкости управляющего кода преобразователя. Количество элементов множества упорядоченных разбиений строки длиной n на 2k–u подмножеств мощностью 2u составляет
Таким образом, управляющий код минимального размера имеет длину
|
()
|
При n>>1 для расчета Сn можно использовать формулу Стирлинга
 ,
|
()
|
где e = 2,71828. Применяя формулу Стирлинга дважды, для случая n>>1, u>>1 получим
|
()
|
Аппаратную сложность преобразователя Tn будем исчислять в условных логических вентилях. Пусть удалось создать устройство, формирующее перестановку на однотипных логических элементах. Каждый логический элемент имеет управляющий вход. Таким образом, минимальное число логических элементов преобразователя составляет Tn. Для любого однотактного преобразователя справедливо неравенство
 .
Поскольку аппаратурная сложность известных преобразователей составляет
Tn n2,
для больших значений n
Tn >> C(n,0).
Графики зависимости количества переключателей T от длины входной строки данных k = log2(n) для различных транспозиционных преобразователей представлены на рис. 1.
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
k
1
2
3
4
5
6
7
8
9
10
C(n,0)
T(n)
TBM(n,0)
TBM(n,4)
TB(n,0)
T
Рис. 1. Графики зависимости количества переключателей преобразователей от длины входных строк
Для сравнения также отображена кривая C(n,0), характеризующая минимальное число переключателей параллельного транспозиционного преобразователя, осуществляющего произвольные перестановки исходных данных.
Как отмечалось ранее, преобразователи с использованием матрицы переключателей n×n, имеющие число переключателей T(n), определяемое выражением (), не эффективны с аппаратной точки зрения. Использование этих преобразователей затруднено при k > 10.
Количество переключателей TBM(n,0), полученное в [10], и определяемое выражением (), незначительно превышает минимальное C(n,0) и уменьшается с увеличением параметра  .
Наиболее простой оказывается модель преобразователя, для которой число переключателей TB(n,0) определялось согласно ().
Для удобства сравнения результаты расчета числа переключателей в рассмотренных ранее моделях представлены на рис. 2 в логарифмическом масштабе и в расширенном диапазоне значений параметра k. Преобразователи TBМ(n,0), TBМ(n,4) С(n,0) и TМО имеют практически одинаковую аппаратурную сложность.
Преобразователь на базе односторонней коммутационной матрицы более эффективен, так как согласно () имеет меньшее количество переключателей. Но с его использованием можно реализовать только  различных перестановок.
C(n,0)
T(n)
TBM(n,0)
TBM(n,4)
TB(n,0)
5
10
15
20
5
7
9
11
13
15
17
19
21
23
25
log(T)
TMO
k
Рис. 2. Графики зависимости числа переключателей преобразователей от длины входных строк
Таким образом, проведенный в данной статье сравнительный анализ аппаратной сложности различных транспозиционных преобразователей показал, что модель с числом переключателей TBM(n,0) является близкой к оптимальной с минимальным числом переключателей. Это дает возможность реализовать преобразователи при больших длинах преобразуемых строк и хранить коды управления ими, не осуществляя преобразования с целью сокращения размера дескриптора формата.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Молодченко Ж. А., Харин В. Н., Овчинников С. В., Сотов Л. С. Модели аппаратных акселераторов перестановок бинарных множеств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Устройства различного назначения. Прикладные аспекты. С. 11–23.
Сотов Л. С. Аппаратные устройства формирования прямых и обратных перестановок данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 9 : Магнитоэлектроника. Микро- и наноструктуры. Прикладные аспекты. Проблемы физического образования. С. 61–77.
Соболев С. С., Сотов Л. С., Харин В. Н. Динамическое форматирование структурных объектов хранилищ данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 4. С. 28–33.
Сотов Л. С., Харин В. Н. Концепция ТСВ-платформы для распределенных информационно-вычислительных систем специального назначения // Гетеромагнитная микроэлектроника : сб. докл. и ст. II и III науч.-техн. совещ. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 3 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. С. 66–72.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. О формировании доверенной среды серверных систем управления базами данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 3. С. 23–27.
Анищенко А. Н., Ляшенко А. В., Солопов П. А., Сотов Л. С. Минимизация рисков утечки информации из-за побочных электромагнитных излучений персонального комьютера // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 17 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 66–77.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Cтруктура подсистемы стохастической генерации дескрипторов форматов //Аспирант и соискатель. 2009. № 4. С. 86–88.
Ляшенко А. В., Сотов Л. С. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 57–72.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Математические модели стохастического формирования изоморфных представлений структурных элементов данных в ЭВМ // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Устройства различного назначения. С. 29–41.
Сотов Л. С. Комбинаторная модель функционального формирователя разбиений бинарного множества // Информационные технологии. 2010. № 10. С. 46–52.
Соболев С. С., Сотов Л. С., Харин В. Н. Алгоритм работы и модель функционального генератора перестановок // Информационные технологии. 2010. № 4. С. 41–46.
Ляшенко А. В., Сотов Л. С. Простой матричный формирователь r-выборок // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 47–56.
Ляшенко А. В., Сотов Л. С., Хвалин А. Л., Чесаков В. С. Микропроцессор с ускоренной манипуляцией битами данных для обработки сигналов в системах связи // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2015. Вып. 18 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 72–81.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Математические модели транспозиционных преобразований // Информационно-измерительные и управляющие системы. 2007. Т. 5, № 12. С. 58–60.
Сотов Л. С. Об эффективности использования специальных команд преобразования форматов данных в вычислительной технике // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 61–80.
Сотов Л. С., Ачкасов В. Н. Универсальный модуль манипуляции битами данных в микропроцессорах // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 11 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 57–73.
Назаров С. И., Ляшенко А. В., Сотов Л. С., Хвалин А. Л. Проектирование микропроцессора c расширенным набором команд манипуляции битами данных на базе архитектуры OPENRISC1200 // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 17 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 50–65.
Назаров С. И., Сотов Л. С., Ляшенко А. В. Процессор с улучшенной манипуляцией битами данных для средств навигации, обработки сигналов и изображений, криптографии, мобильных диагностических устройств // Гетеромагнитная микроэлектроника: сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 16 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 51–63.
Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М. : Радио и связь, 1990. 216 с.
Сотов Л. С. Методы синтеза устройств, выполняющих инструкции перестановки битов данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования ы. С. 25–50.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Модели аппаратных функциональных формирователей перестановок // Информационно-измерительные и управляющие системы. 2009. Т. 7, № 10. С. 78–84.
Молодченко Ж. А., Харин В. Н., Сотов Л. С. Алгоритм создания диверсификационного метода битовых преобразований // Естественные и технические науки. 2007. № 6. С. 222–225.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Моделирование архитектуры акселератора битовых перестановок с использованием САПР SYSTEM STUDIO фирмы SYNOPSYS // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 3 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. С. 60–66.
Бассалыго Л. А., Пинскер М. С. О сложности оптимальной неблокирующей коммутационной схемы без перестроения // Проблемы передачи информации. 1973. Т. 9, № 1. С. 84–87.
Сотов Л. С., Соболев С. С., Харин В. Н. Кластерная коммутационная матрица для аппаратной поддержки управляемой перестановки данных в криптографических системах // Проблемы информационной безопасности. Компьютерные системы. 2009. № 4. С. 56–63.
Соболев C. C., Сотов Л. С., Харин В. Н. Модели устройств кросс-кластерных перестановок данных в ЭВМ // Вестн. компьютерных и информационных технологий. 2009. № 12. С. 51–55.
УДК 621.317.33; 53.082.722.55; 621.38.(075.8)
|
