ДЕКОМПОЗИЦИЯ ПРОЦЕДУРЫ ФОРМИРОВАНИЯ
УПОРЯДОЧЕННОГО РАЗБИЕНИЯ БИНАРНОГО МНОЖЕСТВА
В. А. Малярчук
Саратовский государственный университет
Россия, 410012, Саратов, Астраханская, 83
E-mail: kof@info.sgu.ru
Предложен способ реализации процедуры формирования упорядоченного разбиения входных данных, который используется для построения переключающей схемы, осуществляющей упорядоченные разбиения и манипуляции битами машинного слова в микропроцессорных устройствах.
Ключевые слова: упорядоченное разбиение множества, манипуляция битами данных, микропроцессор.
The Method for Organizing Ordered Partitions of a Binary Set
V. A. Malyarchuk
The method for organizing ordered partitions of a binary set is offered. The suggested method is useful to build multistage interconnection network that is released ordered partitions of input binary set in order to accelerate bit manipulations in microprocessors.
Key words: ordered partition of a set, bit manipulation, microprocessor.
Манипуляции битами данных и связанные с ними перестановки возникают в различных задачах, решаемых средствами вычислительной техники [1]. Манипуляции битами данных часто используются в криптографических преобразованиях [2, 3]. В работах [4, 5] предложены способы формирования ключей для систем защиты информации. Различными авторами предлагаются алгоритмы скоростного шифрования, в которых используются операции управляемой перестановки [6, 7].
Важной задачей является увеличение производительности устройств, осуществляющих перестановки и манипуляции битами данных. Поиску путей решения этой задачи посвящены недавние работы [8, 9]. При этом наибольшей производительностью обладают аппаратурные устройства [10, 11].
Известны последовательные [12] и параллельные [13] способы осуществления перестановок битов данных.
В работах [14, 15] было показано, что упорядоченные разбиения множества входных данных лежат в основе скоростных способов битовых и кластерных перестановок.
Представляет интерес разработка устройств, дающих возможность быстро выполнять перестановки бинарных кластеров множества из n битов. Обзор аппаратных формирователей перестановок (FP) дан в [16, 17].
Особый интерес представляют способы синтеза формирователей перестановок [18, 19].
В данной статье проведен краткий обзор существующих подходов и решений, а также предложен универсальный способ формирования упорядоченных разбиений множеств бинарных данных в ЭВМ.
Способ формирования упорядоченных разбиений
бинарного множества
Для устройств преобразования форматов данных важна возможность распараллеливания процесса формирования упорядоченных разбиений. Одним из перспективных подходов является метод последовательных упорядоченных разбиений множества мощностью n на К упорядоченных подмножеств. Орграф, иллюстрирующий данный метод, представляет собой дерево с К исходящими из каждого узла ветвями. В каждом узле орграфа соответствующее подмножество исходного множества разбивается на К подмножеств, каждое из которых позиционируется относительно других. В результате последовательного выполнения разбиений K раз образуется перестановка исходного упорядоченного множества, где K = log2(n).
Действительно, число разбиений Rn множества мощностью n на K подмножеств определяется уравнением
 .
Число упорядоченных разбиений упорядоченного множества мощностью n на K упорядоченных подмножеств составляет
где  , (log2(n) – u) – число последовательных разбиений исходного множества.
Доказательство (1) проведем по индукции. Докажем сначала, что 
Пусть n = K, тогда
Пусть верно
Докажем, что  Действительно,
 .
Введем новую переменную суммирования: m = i – 1, тогда
 ,
Каждое подмножество, содержащее 2u элементов на u уровнях преобразования, разбивается на (Кu)! одноэлементных множеств. При этом число подмножеств разбиения составляет n/Кu. Таким образом,
 .
С точки зрения аппаратурной реализации наиболее эффективным оказывается метод разбиения на два подмножества (K = 2). Аналогичный метод был использован в алгоритме формирования случайных перестановок.
Так как преобразования выполняются в различных узлах орграфа, процесс преобразования распараллеливается. Наиболее просто предложенный способ формирования упорядоченных разбиений бинарного множества реализуется при использовании последовательной загрузки данных. При этом последовательный код одновременно преобразуется в параллельный [12].
В статье предложен универсальный способ формирования упорядоченных разбиений множеств бинарных данных в ЭВМ, заключающийся в реализации последовательных разбиений исходной строки данных на K упорядоченных подмножеств. Этот способ является математической основой для разработки высокопроизводительных модулей манипуляции битами данных в микропроцессорах [20, 21] и формирователей кластерных перестановок для вычислительной техники и систем защиты информации [22, 23].
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Сотов Л. С. Об эффективности использования специальных команд преобразования форматов данных в вычислительной технике // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 61–80.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. О формировании доверенной среды серверных систем управления базами данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 3. С. 23–27.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Аппаратный акселератор сервера форматирования данных // Надежность и качество : тр. междунар. симпозиума : в 2 т. Пенза : Изд-во Пензенск. ун-та, 2007. Т. 1. С. 134–136.
Ляшенко А. В., Сотов Л. С. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 :. Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 57–72.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Cтруктура подсистемы стохастической генерации дескрипторов форматов //Аспирант и соискатель. 2009. № 4. С. 86–88.
Молдовян Н. А., Молдовян А. А., Алексеев Л. Е. Перспективы разработки скоростных шифров на основе управляемых перестановок // Вопр. защиты информации. 1999. № 1. C. 41–47.
Сотов Л. С., Харин В. Н. Концепция ТСВ-платформы для распределенных информационно-вычислительных систем специального назначения // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 3 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. С. 66–72.
Молодченко Ж. А., Харин В. Н., Сотов Л. С. Алгоритм создания диверсификационного метода битовых преобразований // Естественные и технические науки. 2007. № 6. С. 222–225.
Сотов Л. С. Методы синтеза устройств, выполняющих инструкции перестановки битов данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 25–50.
Молодченко Ж. А., Харин В. Н., Овчинников С. В., Сотов Л. С. Модели аппаратных акселераторов перестановок бинарных множеств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Устройства различного назначения. С. 11–23.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Модели аппаратных функциональных формирователей перестановок // Информационно-измерительные и управляющие системы. 2009. Т. 7, № 10. С. 78–84.
Пат. 2320000 Российская Федерация, МПК G0 6F 7/76, G0 6F 12/14. Дешифра-тор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ / заявители Молодченко Ж. А., Сотов Л. С., Харин В. Н. ; патентообладатель Сарат. гос. ун-т им. Н. Г. Чернышевского. – № 2007105175/09 ; заявл. 13.02.2007 ; опубл. 20.03.2008, Бюл. № 8. 6 с.
Ляшенко А. В., Сотов Л. С. Простой матричный формирователь r-выборок // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро- и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 47–56.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Математические модели стохастического формирования изоморфных представлений структурных элементов данных в ЭВМ // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Устройства различного назначения. Прикладные аспекты. С. 29–41.
Сотов Л. С. Комбинаторная модель функционального формирователя разбиений бинарного множества // Информационные технологии. 2010. № 10. С. 46–52.
Соболев С. С., Сотов Л. С., Харин В. Н. Алгоритм работы и модель функционального генератора перестановок // Информационные технологии. 2010. № 4. С. 41–46.
Сотов Л. С. Аппаратные устройства формирования прямых и обратных перестановок данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 9 : Магнитоэлектроника. Микро- и наноструктуры. Прикладные аспекты. Проблемы физического образования. С. 61–77.
Соболев С. С., Харин В. Н., Сотов Л. С. Модели устройств кластерных перестановок данных в ЭВМ // Вестн. компьютерных и информационных технологий. 2009. № 12. С. 51–55.
Молодченко Ж. А., Сотов Л. С., Харин В. Н. Математические модели транспозиционных преобразований // Информационно-измерительные и управляющие системы. 2007. Т. 5, № 12. С. 58–60.
Назаров С. И., Ляшенко А. В., Сотов Л. С., Хвалин А. Л. Проектирование микропроцессора c расширенным набором команд манипуляции битами данных на базе архитектуры OPENRISC1200 // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 17 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 50–65.
Назаров С. И., Сотов Л. С., Ляшенко А. В. Процессор с улучшенной манипуляцией битами данных для средств навигации, обработки сигналов и изображений, криптографии, мобильных диагностических устройств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 16 : Гетеромагнитная микро- и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 51–63.
Сотов Л. С., Соболев С. С., Харин В. Н. Кластерная коммутационная матрица для аппаратной поддержки управляемой перестановки данных в криптографических системах // Проблемы информационной безопасности. Компьютерные системы. 2009. № 4. С. 56–63.
Сотов Л. С., Ачкасов В. Н. Универсальный модуль манипуляции битами данных в микропроцессорах // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 11 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 57–73.
УДК 536.24, 621.382
ТЕПЛОФИЗИЧЕСКИЙ АНАЛИЗ РЕНТГЕНОВСКОГО МИКРОИЗЛУЧАТЕЛЯ
Н. Д. Жуков, С. В. Овчинников*
ООО «Реф-Свет»
Россия, 410033, Саратов, пр. 50 лет Октября, 101
E-mail: ndzhukov@rambler.ru
*Саратовский государственный университет
Россия, 410012, Саратов, Астраханская, 83
E-mail: kof@sgu.ru
Представлены результаты теплофизического анализа варианта конструкции рентгеновского микроизлучателя на основе микроканальной структуры. Определены предельные мощности тепловых нагрузок. Значения электрической мощности в статическом режиме могут достигать одного ватта. Использование импульсного режима с длительностью в доли секунды позволяет увеличить значения импульсной мощности в несколько раз.
Ключевые слова: рентгеновский микроизлучатель, дискообразный анод, микроканальная структура, тепловой режим, теплофизическая модель, конвективный и лучистый теплообмен.
X-Ray Micro-Emitter Thermo-Analysis
N. D. Zhukov, S. V. Ovchinnikov
Presents the results of thermo-analysis of X-ray micro-emitter on the basis of microcanal glass structure. Defined the limits of the heat power. The static electrical power can be up to 1 Wt. Use the pulse duration within a fraction of a second will increase the pulse power several times.
Key words: X-ray micro-emitter, disc-shaped anode, microcanal glass structure, heat transfer model, convective and radiant heat transfer.
Специфика работы миниатюрных рентгеновских излучателей заключается в том, что на их аноде в микрообъеме выделяется электрическая мощность большой величины и огромной плотности. Практически вся электрическая энергия в микрозоне анода превращается в тепло, которое через анод и присоединенные к нему элементы отводится в окружающую среду. Трубки излучателей большой мощности работают на отражательном принципе. Их конструкция позволяет создать эффективный радиатор для анода. Коэффициент полезного преобразования в таких трубках, однако, чрезвычайно мал отчасти из-за больших потерь рентгеновского излучения на пространственный лучевой переход от анода через окно. Этот недостаток устраняется в прострельных трубках, в которых анод и окно совмещены, но конвективная теплоотдача в этом случае практически мало эффективна, и тепло в основном отводится за счет излучения. Поиск оптимального варианта конструкции и структуры излучателя является актуальной задачей при его микроминиатюризации. К таким излучателям в последнее время отмечается повышенный интерес в связи с их применением в мобильной аппаратуре с учетом локального воздействия излучения на объект [1].
Изображения простых теплофизических моделей конструкции анода излучателя представлены на рисунке.
Анод излучателя представляет собой тонкий алюминиевый диск, закрывающий микроканальный элемент (см. рисунок, а). Радиус дискообразного анода обозначен через R, а толщина диска через δ. Рабочая зона анода, воспринимающая тепловую мощность РТ от электронного пучка, расположена в центральной области диска и имеет радиус rист. Эта тепловая мощность аккумулируется в диске и рассеивается в окружающую среду конвекцией и излучением. Анод излучателя может быть закрыт дополнительным алюминиевым корпусом (см. рисунок, б), выполняющим роль теплового радиатора.
а
б
δ
δ
R
Pr
rист
αэфф(TS – TСР)S
Теплофизическая модель излучателя: а – дискообразный анод; б – дискообразный анод с теплорассеивающей стаканообразной оболочкой
Вакуумным баллоном-носителем микроизлучателя является стеклянная микроканальная структура (микроканальный элемент) в виде цилиндра, содержащего множество каналов сотового профиля в его поперечном сечении, в центральной зоне которого сформирован возбуждающий электронный поток [2].
Теплофизический анализ проводился на основе решения уравнения теплопроводности с граничными условиями вида
|
(1)
|
где  – величина плотности теплового потока, подходящего к теплоотдающей поверхности S путем теплопроводности; λ – коэффициент теплопроводности материала тела; αК – коэффициент конвективной теплоотдачи с поверхности S; TS – температура теплоотдающей поверхностиS; ТСР – температура окружающей среды; ε – интегральная по спектру степень черноты поверхности S; φ – коэффициент взаимной облученности тел, участвующих в лучистом теплообмене;  =5,67∙10–8 Вт/(м2∙К4) – постоянная Стефана–Больцмана.
В инженерных задачах лучистый поток часто учитывается путем линеаризации закона лучистого теплообмена и заданием эффективного значения коэффициента конвективной теплоотдачи αЭФФ [3, 4], учитывающего как конвективную, так и лучистую составляющие теплового потока. Это позволяет формулировать задачу теплопроводности в линейном виде. Лучистую составляющую в выражении (1) можно преобразовать следующим образом:
|
(2)
|
где – эквивалентный коэффициент лучистой теплоотдачи:
= .
|
(3)
|
В этом случае граничное условие (1) можно переписать в виде
|
(4)
|
С катода излучателя через микроканальный элемент на сильно локализованный участок анода попадает электронный поток, выделяющий в этом элементе тепловую мощность РТ. Поскольку эквивалентные теплоемкость и теплопроводность вакуумированного микроканального элемента пренебрежимо малы по сравнению с материалом анода (алюминий), то в процессе рассеяния тепловой энергии микроканальный элемент практически не участвует. В связи с этим теплофизическая модель излучателя фактически является моделью анода с локальным тепловыделением.
При теплофизическом моделировании внешний радиус диска-анода задавался равным 1,5 мм и 3,0 мм при радиусе теплового источника 0,5 мм и толщине диска-анода 0,05 мм. Коэффициент теплопроводности алюминия принимался равным λ = 230 Вт/(м∙К), причем это значение практически не меняется в диапазоне 300–600 К [5].
Площадь поверхности анода достаточно мала, и эффективность теплоотдачи с нее низкая. Предлагается развивать эту поверхность с помощью внешней алюминиевой стаканообразной оболочки (см. рисунок, б), внешняя поверхность которой может быть дополнительно оребрена. Толщину оболочки для определенности выберем равной δ = 0,5 мм, поскольку делать ее тоньше с теплофизической точки зрения нецелесообразно. Между оболочкой и анодом может находиться тонкий изолирующий слой, выполненный, например, из бериллиевой керамики, теплопроводность которой практически равна теплопроводности алюминия, и всю конструкцию теплорассеивающей системы при оценочных расчетах можно считать однородной.
Как конвективная, так и лучистая теплоотдача зависят от температурного перепада между теплоотдающей поверхностью и окружающей средой – так называемый температурный напор (TS –ТСР). В нестационарных задачах и задачах с локальным тепловыделением температура теплоотдающей поверхности не является постоянной величиной. Поэтому в инженерной практике принято определять условия теплообмена по средней температуре теплоотдающих поверхностей. При расчетах средняя температура теплоотдающей поверхности задавалась равной 310, 330, 350 К и далее с шагом 50 К до значения 500 К. Температура внешней для прибора среды считалась неизменной и принималась равной 300 К.
Принимая степень черноты неполированного алюминия ε = 0,25 [3, 4] и считая, что самооблучение анода отсутствует, по формуле (3) вычисляются значения αЛ с поверхности анода, которые хорошо аппроксимируются формулой
αЛ (Т) = 1,614+Т∙(2,3585∙10–5∙Т – 0,0073).
|
(5)
|
Коэффициент конвективной теплоотдачи αК зависит от многих факторов, в том числе от температурного напора, размера теплоотдающей поверхности и ее ориентации в пространстве. При расчетах предполагалось, что излучатель находится в большом объеме спокойного воздуха при комнатной температуре. Ориентация основной теплорассеивающей поверхности принималась вертикальной. Значения αК определялись по общепринятой методике [3]. Дискообразный анод без теплорассеивающей оболочки конвективно рассеивает тепло только с одной своей стороны, а лучистым образом – с обеих сторон. Площадь поверхности анода (с одной стороны) принималась равной 7,1 мм2 и 28,3 мм2 для его радиусов 1,5 мм и 3,0 мм соответственно. Теплорассеивающая поверхность оболочки с учетом возможного оребрения задавалась равной 310, 700 и 1250 мм2. Теплообмен с окружающей средой осуществляется только с внешней поверхности оболочки.
Итоговые значения эффективного коэффициента конвективной теплоотдачи как функции температурного напора и размера теплоотдающей поверхности приведены табл.1, где  – средняя температура теплоотдающей поверхности модели; S – характерные размеры этой поверхности; αЭКВ = αК + αЛ – рассчитанные значения эквивалентного коэффициента теплоотдачи с учетом средней температуры теплоотдающей поверхности и ее размера; RTИСТ = (ТИСТ – ТСР)/РТ – тепловое сопротивление модели для температурных перепадов источник–окружающая среда; РТS – тепловая мощность, необходимая для достижения теплоотдающей поверхности модели того среднего значения температуры, которое указано в первом столбце табл. 1;  – средняя температура источника тепла.
Таблица 1 |
