Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Сотов Леонид Сергеевич
КОМБИНАТОРНЫЕ УСТРОЙСТВА ФОРМИРОВАНИЯ ИЗОМОРФНЫХ ПРЕДСТАВЛЕНИЙ ДАННЫХ, ПОВЫШАЮЩИЕ ПРОИЗВОДИТЕЛЬНОСТЬ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
Специальность: 05.13.05 - Элементы и устройства вычислительной техники и систем управления
Автореферат диссертации на соискание ученой степени доктора технических наук
Саратов-2011
Работа выполнена в НИУ ВПО Саратовский государственный университет им.
Н.Г. Чернышевского и в ГОУ ВПО Воронежский государственный технический университет.
Научный консультант: доктор технических наук, профессор Антимиров Владимир Михайлович
Официальные оппоненты: доктор технических наук, профессор Хетагуров Ярослав Афанасьевич доктор технических наук, профессор Зольников Владимир Константинович доктор физико-математических наук, профессор Безручко Борис Петрович
Ведущая организация: ОАО Институт электронных управляющих машин им. И.С. Брука, г. Москва
Защита состоится 21 декабря 2011 года в 14.00 часов на заседании диссертационного совета Д. 212.242.08 при ГОУ ВПО Саратовский государственный технический университет по адресу: 410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319.
С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО Саратовский государственный технический университет.
Автореферат размещён на сайте ВАК РФ л_____ 2011 г.
Автореферат разослан л_____ 2011 г.
Ученый секретарь диссертационного совета А.А. Терентьев
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. Обеспечение параллелизма манипуляций с данными является одним из методов повышения производительности средств вычислительной техники. В настоящее время большинство процессоров общего назначения параллельно обрабатывают данные, имеющие 32 или 64 разряда, что позволяет с высокой скоростью осуществлять операции над числами с одинарной и двойной точностью.
С расширением области применения средств вычислительной техники все чаще возникают задачи, связанные с формированием изоморфных представлений или битовых перестановок машинного слова. В число таких задач входят обработка морфологии изображений, сортировка, моделирование и тестирование цифровых устройств, задачи биоинформатики, расчет контрольных сумм и коррекция ошибок, стеганография, сжатие и развертывание информации, выполнение криптографических примитивов, обработка сигналов в системах RPMA (random permutation-based multiple access) для передачи данных с использованием технологий расширения спектра, преобразование данных для передачи в текстовом формате и т.п. При этом затраты машинного времени на битовые преобразования данных составляют от 30 до 90% времени выполнения задач.
Битовые перестановки сложны для программной реализации. Каждый бит должен быть извлечен из исходного регистра, перемещен на новое место в регистре назначения и объединен с ранее перестановленными битами. Это требует 4 инструкций на бит (генерация маски, И, Сдвиг, ИЛИ), и 4n инструкций для выполнения произвольной перестановки n битов. В связи с этим в последние годы проводятся интенсивные исследования в области разработки устройств, ускоряющих обработку битов данных.
В работах R.В. Lee, Y. Hilewitz, Z. Shi, H. Liao, Z. Wu, Y. Xiao, G. Dimitrakopoulos, C. Mavrokefalidis и др. для ускорения осуществления битовых перестановок предлагается расширение архитектуры процессоров. В основе ряда предлагаемых решений лежат многоуровневые коммутационные сети, теория которых была заложена в работах Клоза, Бенеша и развита в работах ряда авторов:
M. H. Ackroyd, D. P. Agrawal, D. G. Cantor, F. K. Hwang, C. P. Kruskal и др. Для ускорения битовых перестановок R.В. Lee с соавторами были предложены новые инструкции bfly (Butterfly), ibfly (Inverse Butterfly), grp (Grop), разработаны устройства для их реализации. Последовательное использование инструкций bfly и ibfly даёт возможность осуществить любую перестановку, но её выполнение может занимать значительное время. Инструкция grp является альтернативным подходом, но существующие аппаратурные решения не обладают необходимым быстродействием и сложны.
Для увеличения производительности в платформах: IA-32 (Intel Architecture, 32-bit), AMD64, Itanium ISA, POWER (Performance Optimization With Enhanced RISC), кроме указанных базовых инструкций, вводится поддержка специализированных команд для манипуляций с битами данных. Однако при этом теряется универсальность.
В ряде отмеченных ранее задач требуется перечисление и формирование перестановок битов данных в случайном порядке. Для этого обычно используются последовательные, достаточно медленные алгоритмы Фишера-Йетса (FisherЦ Yates), Саттоло (Sattolo).
В работах В. М. Курейчика, В. М. Глушань, Л. И. Щербакова, Г.С. Цирамуа, В.А. Богатырева, В.М. Полищука, В.И. Чабана, Р.В. Дмитришина и др. исследуются детерминированные и вероятностные формирователи перестановок, сочетаний и размещений. Однако предлагаемые устройства являются специализированными, их аппаратурная сложность составляет O(n2 ) и быстро растет с увеличением n, где n - длина формируемого блока данных.
Таким образом, традиционные методы и аппаратурные средства для выполнения операций формирования изоморфных представлений или преобразования форматов данных в вычислительной технике существенно снижают её производительность. Существующие специальные устройства для преобразования форматов данных или не обладают необходимой универсальностью и гибкостью, или создают существенные задержки при обработке данных и сложны в аппаратурном исполнении.
В связи с вышеизложенным в вычислительной технике является актуальной научно-техническая проблема разработки универсальных устройств для ускорения выполнения процедур преобразования форматов представления данных.
Тематика диссертационной работы соответствует научной программе кафедры общей физики Саратовского государственного университета им. Н. Г. Чернышевского и кафедры систем автоматизированного проектирования и информационных систем Воронежского государственного технического университета.
Цель диссертационной работы. Создание и исследование универсальных устройств формирования изоморфных представлений данных на основе предлагаемых принципов построения и алгоритмов структурного синтеза, обеспечивающих повышение производительности средств вычислительной техники.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
1. Анализ областей использования, проблем, особенностей и методов осуществления преобразований форматов данных в вычислительной технике.
2. Выбор и обоснование универсальных базовых преобразований форматов данных, обеспечивающих повышение производительности вычислительной техники за счет параллелизма при обработке битов данных.
3. Разработка принципов структурного синтеза и моделей аппаратурных средств, осуществляющих базовые преобразования, создание на их основе универсальных устройств, повышающих скорость манипуляций с битами данных.
4. Обоснование принципов построения и разработка с использованием базовых преобразований универсальных детерминированных и вероятностных устройств, увеличивающих производительность вычислительной техники при решении задач перечисления и формирования в случайном порядке представлений данных.
5. Исследование повышения производительности вычислительной техники при использовании разработанных устройств на примерах различных задач, разработка рекомендаций к применению данных устройств.
Объект исследования: устройства вычислительной техники для преобразования форматов представления и манипуляций с битами данных.
Предмет исследования: структурный синтез, модели детерминированных и вероятностных устройств формирования и преобразования форматов данных.
Методы исследования. В качестве теоретической и методологической основы диссертационных исследований использованы элементы теории множеств, групп, комбинаторики, теории конечных однородных цепей Маркова и аппарата стохастических матриц, теории вероятностей, теории динамических систем с хаотической динамикой, аппарата и методов имитационного системного моделирования.
Научная новизна работы:
1. На основе предложенных базовых преобразований, включающих упорядоченные и неупорядоченные разбиения блока данных длиной n, обоснованы принципы создания и разработаны алгоритмы структурного синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных. Показано, что при использовании разработанных устройств вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.
2. Доказаны теоремы о композиции переключателей для осуществления упорядоченных и неупорядоченных разбиений данных, об использовании сортирующих сетей для осуществления прямых и обратных перестановок и разбиений, о композиции формирователей разбиений слов длиной n, n/2, n/4, Е, которые обеспечили структурный синтез, и разработку моделей устройств:
параллельного формирования упорядоченных и неупорядоченных разбиений блоков данных длиной n=2k на m кластеров по 2u элементов с q 2log2 (n) u 1 уровнями преобразования и аппаратурной сложностью не более чем n (log (n) u/ 2 1) 1логических элементов матрицы формирователя, где kЦположительное целое число, а u=0,Е,k-1;
параллельного формирования упорядоченных разбиений блоков данных длиной n на m кластеров c использованием топологий сортирующих сетей, что обеспечивает уменьшение времени установления готовности устройства к реализации заданного преобразования при смене дескриптора формата;
параллельного формирования перестановок с заданной структурой цик( ) лов, аппаратурной сложностью O и числом уровней преобразования q 4log2(n) ;
параллельного формирования прямых и обратных преобразований упорядоченных разбиений блоков данных длиной n=2k на m кластеров по 2u элементов в классе матричных устройств с аппаратурной сложностью O(n2) ;
перечисления упорядоченных разбиений множества чисел (0,1,2,Е,n-1) на блоки по 2u элементов, выполненных на базе матриц, формирующих упорядоченные разбиения входных данных длиной n, n/2, n/4, Е, 2u+1 на два подмножества.
3. Обоснованы теоретические положения, включающие теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями, о декодировании битов управления, обеспечивающие создание универсального устройства преобразования форматов данных, выполняющего две новые инструкции bsn и grpm. Доказано, что разработанное устройство характеризуется более высокой скоростью выполнения и простотой аппаратурной реализации по сравнению с существующими решениями. На основании проведенных исследований разработаны варианты структурно-функциональной организации модулей, осуществляющих инструкции bsn, grpm, grp, pex.v, pdep.v, pex, pdep, rotate, shift.
4. Разработаны и обоснованы принципы построения высокопроизводительных вероятностных формирователей упорядоченных разбиений блоков данных длиной n с произвольной и заданной структурой циклов, характеризующиеся равномерным распределением вероятностей формируемых последовательностей. Разработанные вероятностные формирователи выполнены на базе предложенных устройств, осуществляющих упорядоченные и неупорядоченные разбиения. Доказано, что информационная энтропия вероятностного распределения выходных данных достигает значения более 50% от максимального за время, определяемое задержкой используемого формирователя, что обеспечивает увеличение производительности вычислительного устройства в n раз по сравнению с его производительностью при реализации алгоритмов Фишера-Йетса (FisherЦYates) или Саттоло (Sattolo).
5. Разработан способ построения формирователя импульсов случайной длительности и случайных бинарных кодов, имеющего равномерную функцию распределения вероятностей формируемых бинарных последовательностей и отличающегося использованием только цифровых логических элементов. Обоснована модель формирователя, являющаяся двухмерным отображением с хаотической динамикой, параметрами которого являются частоты задающих генераторов.
6. Обоснована необходимость использования встроенных систем диагностики режимов функционирования генераторов случайных сигналов. Разработаны способы построения и модели детекторов режимов функционирования генераторов случайных сигналов, основанные на анализе периодов возвратов изображающей точки в фазовом пространстве контролируемых генераторов и проверке непрерывности распределения спектральной плотности мощности.
Практическая значимость работы заключается в повышении производительности технической базы средств вычислительной техники за счет использования разработанных устройств при решении задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики; расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате и других задач, связанных с манипуляцией битами данных.
В диссертации показано, что общий вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до раз. Использование разработанных детерминированных и вероятностных формирователей упорядоченных разбиений блоков данных длиной n обеспечивает увеличение производительности вычислительного устройства примерно в n раз по сравнению с его производительностью при реализации алгоритмов Фишера-Йетса (FisherЦYates), Саттоло (Sattolo).
Предложенные в диссертации формирователи импульсов случайной длительности и случайных бинарных кодов имеют равномерную функцию распределения, устойчивы к внешним воздействиям и разработаны на стандартных цифровых элементах, что обеспечивает надежность их использования.
Разработанные в диссертации детекторы режимов функционирования генераторов случайных сигналов способны регистрировать их возможные отказы, которые могут быть обусловлены неисправностями и внешними воздействиями.
Реализация и внедрение результатов работы.
Результаты работы внедрены в ОАО Тантал, г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от нелицензионного копирования.
Материалы диссертации были использованы при разработке устройств высокоскоростного преобразования форматов данных, разработанных в НИР Исследование нелинейных физических процессов в сложных системах, включая наноструктуры, шифр Синдикат - 3, проводимой в ОМФ НИИЕН по заданию Федерального агентства по образованию.
Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс кафедры Общая физика Саратовского государственного университета и использованы при проведении занятий по дисциплинам Моделирование полупроводниковых приборов и устройств на их основе и Технические средства защиты информации, в дипломном проектировании, при подготовке магистерских и двух кандидатских диссертаций. Материалы диссертации были использованы в учебно-методическом пособии Имитационные модели физических систем с дискретным временем (Изд-во Сарат. ун-та, 2009. ISBN 978-5292-03916-7, 56 с.), в котором рассматриваются вопросы имитационного моделирования матричных преобразователей форматов данных.
Внедрения подтверждены соответствующими актами.
При реализации алгоритмов и методов разработаны, зарегистрированы и внедрены программные комплексы, включающие программы моделирования комбинаторных преобразователей форматов представления данных и программы определения эквивалентных параметров биполярных и полевых транзисторов с целью адекватного представления их в используемых моделях.
По результатам работы в ФГУ ФИПС зарегистрированы 3 программы, получены 12 патентов РФ на изобретения.
Основные положения и результаты, выносимые на защиту:
1. Теоретические положения, обеспечивающие структурный синтез устройств параллельного формирования разбиений входных данных и устройства для перечисления упорядоченных разбиений строки чисел (0,1,2,Е,n-1) на блоки по 2u элементов.
2. Универсальное устройство преобразования форматов данных на базе многоуровневой коммутационной сети baseline обеспечивает произвольное преобразование форматов данных с использованием двух инструкций bsn и выполнение специализированных инструкций манипуляций с битами данных grpm, grp, pex.v, pdep.v, pex, pdep, инструкций логического и циклического сдвига данных.
3. Перестановки данных с произвольной или заданной структурой циклов, формируемые разработанными вероятностными формирователями, имеют равномерное распределение вероятностей и обеспечивают значение информационной энтропии вероятностного распределения выходных данных более 50% от максимального за время, определяемое задержкой используемого формирователя.
4. Формирователь импульсов случайной длительности и случайных бинарных кодов состоит только из цифровых элементов и при соотношениях частот задающих генераторов f11,f12,f21,f22,fg, удовлетворяющих выражениям fg f11 f22 1 1 2; , имеет равномерную функцию распределения f11 f22 f11 f22 f12 f21 fgвероятностей формируемых бинарных последовательностей и описывается двухмерным дискретным отображением с хаотической динамикой в прямом и обратном времени.
5. Детекторы режимов функционирования позволяют регистрировать изменение режима колебаний, обеспечивая, таким образом, контроль режима функционирования генератора динамического хаоса.
6. Разработанные 64-разрядные устройства преобразования форматов данных имеют время преобразования от 12tз до 30tз, где tз - максимальная задержка сигнала на одном инверторе, нагруженном на четыре входа, что обеспечивает увеличение производительности вычислительной системы от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.
Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции Проблемы управления, передачи и обработки информации (АТМ-ТКИ-50), Саратов, 2009, Международных симпозиумах Надежность и качество, Пенза 2006, 2007, Всероссийской научно-практической конференции Проблемы защиты информации ограниченного доступа от утечки по техническим каналам Саратов, РАЦ Тантал, 2003 г., Международной технической конференции Перспективы развития электроники и вакуумной техники на период 1001-2006 гг. ГНПП Контакт, Саратов, 2001, научно-технической конференции Электронные приборы и устройства СВЧ, Саратов, 2001, Международной научно-технической конференции Физика и технические приложения волновых процессов, Самара, 2001.
Основное содержание работы
изложено в 22 публикациях в изданиях, рекомендованных ВАК РФ, а также в трудах международных конференций, симпозиумов, регистрации 3 программ для ЭВМ в реестре ФИПС. Оригинальность технических решений защищена 12 патентами РФ на изобретения. Всего по материалам диссертации опубликовано 57 работ.
ичный вклад автора. Основные результаты, представленные в диссертации, получены лично соискателем. Вклад автора был определяющим при выборе направлений, объектов и методов исследования, а также при написании статей, докладов и одиннадцати изобретений. Большинство работ написаны в соавторстве с моим первым научным консультантом Валерием Николаевичем Хариным, который принимал активное участие в обсуждении содержания статей и заявок на изобретения.
В работах, опубликованных в изданиях, рекомендованных ВАК РФ, в соавторстве и приведенных в конце автореферата, лично соискателем разработаны: в [1-3,6,7,11-13,15,22] - структура и принципы функционирования детерминированных и вероятностных устройств формирования изоморфных представлений данных; в [6,11,12] - методы структурного синтеза и модели устройств базовых преобразований форматов данных; в [7,15,21] - принципы построения и функционирования устройства преобразования форматов данных на основе параллельного формирователя упорядоченных разбиений блоков данных на два подмножества; в [17] - принципы построения и модели высокопроизводительных вероятностных формирователей разбиений с произвольной и заданной структурой циклов; в [5,9,10] - принципы построения, условия вычислительной непредсказуемости и модель формирователя импульсов случайной длительности и случайных бинарных кодов; в [14,16] - принципы построения, функционирования и модели встраиваемых в устройство детекторов режимов функционирования генераторов случайных сигналов.
Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, изложенных на 350 страницах, списка литературы из 255 наименований; содержит 117 рисунков, 38 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы исследования, определены цели и задачи работы, методы решения поставленных задач, отмечены основные результаты исследований, выносимые на защиту, определена их научная новизна и практическая значимость, приведены сведения об апробации и внедрении результатов работы. Обоснована выбранная методология проведенного исследования.
В главе 1 проведен аналитический обзор задач вычислительной техники, в которых преобразование форматов данных занимает значительную часть общего объема вычислений. Проведены исследования существующих подходов к решению данных задач и принципов построения комбинаторных устройств, осуществляющих детерминированные и стохастические процедуры формирования изоморфных представлений данных. На основе проведенного анализа определены требования к устройствам поддержки преобразования форматов данных в вычислительной технике.
Исследованы проблемы и возможности использования устройств, осуществляющих преобразования форматов данных для ускорения процедур сортировки, распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шумов на изображениях, операций преобразования представлений генетических последовательностей в биоинформатике, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, преобразования данных для передачи в текстовом формате, обработки сигналов в системах RPMA для передачи с использованием технологий расширения спектра и т.п. На основе проведенных исследований показано, что затраты машинного времени на преобразования форматов данных в исследованных задачах составляют от 30 до 90%. Наиболее критичной к скорости выполнения битовых манипуляций является обработка данных в системах RPMA.
В этих системах передаваемые и принимаемые данные подвергаются обработке, связанной со случайными перестановками. Каждый элемент входного набора ( ) ( ) данных =, Е, разделяется на P блоков =, Е,. Формируется случайная перестановка, которая используется для преобразования набора входных данных. Принимаемые данные подвергаются обратному преобразованию.
На рис. 1 представлена структура устройств преобразования форматов данных и их использования в различных задачах, решаемых средствами вычислительной техники.
В диссертации показано, что устройства преобразования форматов данных существенно увеличивают производительность вычислительной техники, используемой для решения задач защиты информации.
Рис. 1. Структура устройств преобразования форматов данных В таблица 1-2 приведены данные, характеризующие объем вычислений, приходящихся на преобразование форматов данных при решении приведенных задач.
В этих таблицах в процентах приведены результаты расчета отношения затрат машинного времени Tf, приходящихся на преобразование форматов данных, к общим затратам машинного времени T на выполнение задач c использованием разрядного процессора.
Таблица Результаты расчета Tf /T*100% в задаче сортировки N m-разрядных подслов данных N 128 256 512 1024 2048 4096 8192 16384 32768 41943m=86 76 67 61 55 50 48 42 42 m=88 77 69 62 56 52 46 42 42 m=92 80 71 64 60 55 48 45 41 Таблица Результаты расчета Tf /T Виды обработки информации Tf / T *100% Медианная фильтрация изображений Распознавание геометрических образов и символов на бинарных изображениях Коррекция морфологии изображений Упаковка и распаковка данных LSB стеганография Прямое преобразование Обратное преобразование UUE (Uuencode) Прямое преобразование Обратное преобразование Биоинформатика (операция трансляции) Формирование последовательностей перестановок в системах RPMA Обработка данных в системах RPMA Криптографический алгоритм DES Криптографический алгоритм RC5 Защита файлов мультимедиа от нелицензионного копирования На основе анализа алгоритмов различных задач показано, что можно выделить два типа преобразований формата - статическое и динамическое. В первом случае задача сводится к выполнению фиксированных перестановок на уровне бит данных, во втором случае дескриптор формата данных меняется в процессе вычислений и зависит от данных.
В главе 2 проведена формализация постановки задач и разработаны теоретико-множественные модели форматирующих преобразований. На основе требований к их реализации вводятся базовые форматирующие преобразования.
Структурные элементы обрабатываемых данных можно рассматривать как естественные кластеры данных в основной памяти компьютера. При представлении данных в ячейках основной (оперативной) памяти компьютера производится их упаковка в машинные слова определенной длины, в пределах которых они рас сматриваются как бинарные векторы А (b1,b2,..., bn). Блок ячеек памяти компьютера можно рассматривать как набор переменных. Отношение бинарного набора данных и набора переменных определяет формат представления данных.
В настоящем изложении принят ряд терминов, смысл которых интерпретируется следующим образом:
под транспозицией понимается отображение элемента bi вектора А, определенного в i-й позиции исходной бинарной строки S, в j-ю позицию результирующей строки D, или обратное представление;
под дескриптором формата понимается совокупное описание транспозиций всех элементов исходной бинарной строки при их представлениях в результирующей строке, или при обратном представлении.
Будем обозначать AS - представление компонент бинарного вектора А в исходной строке и AD - их образ в результирующей строке.
Конкретный вид отображения ( Rb : AS AD ) определяется в декартовом произведении множеств AS и AD : ( ).
Теоретико-множественная модель представлений структурных элементов данных, определяющая прямое преобразование исходного формата, имеет вид:
= {,, }. (1) Для обратного преобразования формата (2) = {,, }.
При исследовании способов построения и принципов функционирования преобразователей форматов данных основное внимание уделялось следующим положениям:
Ц скорость преобразования;
Ц размер дескрипторов формата;
Ц число логических вентилей преобразователя.
На основе анализа практических задач, исследованных в первой главе, в качестве базовых преобразований форматов данных в диссертации предложено использовать упорядоченные и неупорядоченные разбиения входных данных. Такой выбор определялся следующими положениями:
1. В общем случае мощность множества форматов представлений вектора А (b1,b2,..., bn ) определяется числом возможных перестановок его компонент и составляет n!. С увеличением n быстро возрастает размер дескрипторов формата, поэтому для сокращения ресурсов, отводимых под описание операции, необходимо использовать более простые форматирующие преобразования.
2. В большинстве рассмотренных в первой главе приложений не требуется выполнения произвольных преобразований форматов данных. Обычно используются операции выделения определенных бит данных и их группировка или обратные операции установки группы бит данных в заданные позиции.
3. Произвольная перестановка компонент вектора А является частным случаем упорядоченного разбиения, когда множество {b1,b2,..., bn} разбивается на n непустых подмножеств.
Глава 3 посвящена разработке и обоснованию теоретических положений, обеспечивающих структурный синтез устройств базовых форматирующих преобразований. В главе исследованы способы построения ряда устройств последовательного и параллельного преобразования формата данных, имеющих аппаратурную сложность O(n), O(nlog2n), O(n(log2n)2), O(n2). Проведена сравнительная оценка их производительности. Точные данные, характеризующие производительность предлагаемых устройств, получены на основе анализа имитационных моделей устройств и приведены в шестой главе.
Предложена и обоснована модель BCTA1 устройства последовательного формирования упорядоченных разбиений. Устройство осуществляет упорядочен ные разбиения компонент вектора данных А (b1,b2,..., bn) на 2 подмножеств мощности 2, где n=2k, u=0,1,2,Е,k-1, k - положительное целое число. Аппаратурная сложность устройств последовательного действия составляет = /2 1. Для параллельной обработки в модели BCTAP используется n устройств последовательного действия. Задержка выполнения преобразования определяется числом последовательно соединенных уровней дешифратора устройства и имеет значение 2(log2n-u)tз, где tз - задержка на одном логическом инверторе, нагруженном на четыре входа. Аппаратурная сложность при этом составляет = ( ) /2 - 1 и быстро возрастает с увеличением n.
Для упрощения формирователя упорядоченных и неупорядоченных разбиений в диссертации предложены и обоснованы теоретические положения, обеспечивающие структурный синтез коммутационной матрицы, формирующей упоря доченные и неупорядоченные разбиения компонент вектора данных А (b1,b2,..., bn) на 2 подмножеств мощности 2, где n=2k, u=0,1,2,Е,k-1. На базе данной матрицы разработана имитационная модель устройства BCTAM.
Соединения переключателей коммутационной матрицы устройства ВСТАМ u можно представить в виде орграфа Gn (S,Т,V, D, A), где S (s1,s2,...,sn) - множество входных вершин, Т - множество промежуточных вершин входной части орграфа, V - множество промежуточных вершин выходной части орграфа, D (d1,d2,...,dn)Ц множество выходных вершин, а A - множество дуг орграфа. Согласно теореме о композиции переключателей для осуществления упорядоченных и неупорядоченных разбиений данных промежуточные вершины графа можно представить в виде матрицы с n/2 линиями (строками) и 2log2n-u-1 уровнями (столбцами), причем log2n-1 уровень образован вершинами множества Т, а log2nu уровень образован вершинами множества V. Каждая вершина Тim Т уровня m (1,k 2) входной части является смежной вершинам Th,m+1, Tp,m+1 уровня m+1.
Каждая вершина Vim V уровня m (1,k u-1) выходной части является смежной вершинам Vh,m+1, Vp,m+1 уровня m+1. Причем на отношение смежности накладываются ограничения Bit Cluster Transposition Accelerator i 1 i 2k m1int 1 h 2k m1int 1, 2k m1 2k m (3) m 1)mod n 2k m1 1)mod n (i 2k 2k m1 int 1 p 2k m1int(i 1 , 2k m1 2k m где int - функция выделения целой части, (j 2k m1 1)mod n - операция вычисi 2k m1 ления остатка от частного.
n Промежуточные вершины интерпретируются как переключатели коммутационной матрицы. Каждый переключатель имеет два входа, два выхода данных и бинарный вход управляющего кода c {0,1}. Данные на входах переставляются местами (при значении управляющего кода с=1), либо не переставляются (при с=0). Множество ребер графа описывает соединения между переключателями. Коды управления переключателями являются битовыми атрибутами промежуточных вершин орграфа. В зависимости от их значений формируются разрешенные пути прохождения вершин графа.
В диссертации развита методика управления переключателями для осуществления заданного разбиения.
На рис. 2 приведена диаграмма орграфа одного из вариантов коммутационной матрицы устройства ВСТАМ для случая n=16, u=1. Вершины входной части орграфа образуют уровни F1, F2, F3, вершины выходной части орграфа образуют уровни G1, G2, G3.
Рис. 2. Диаграмма орграфа одного из вариантов матрицы формирователя разбиений для случая n=16, u= Число переключателей коммутационной матрицы устройства BCTAM составляет n(log2(n) u/ 2 1) 1 и растет практически линейно с ростом n, что делает технически возможной реализацию функционального формирователя разбиений при больших значениях n. Быстродействие устройства определяется числом последовательно соединенных уровней коммутационной матрицы устройства и составляет не более 2(2log2n-u-1)tз, так как задержка на уровне составляет 2tз. Таким образом, разработанные устройства BCTAM обладают достаточно высоким быстродействием при выполнении фиксированных преобразований. Проблемой является то, что время настройки переключателей коммутационной матрицы устройства возрастает с ростом n как nlog2n, что приводит к существенному снижению производительности при решении задач с динамическим преобразованием форматов данных. Попытки организовать процесс настройки параллельно приводят к необоснованно сложным техническим решениям.
Для ускорения настройки устройства формирования упорядоченных разбиений при смене дескрипторов формата в диссертации предложен способ структурного синтеза формирователей перестановок и упорядоченных разбиений на основе топологии сортирующей сети. Если дескриптор формата задан в виде перестановки (1,2,...,n), а P - преобразование, осуществляемое сортирующей сетью, при подаче на ее входы перестановки (1,2,...,n), то справедливо выражение:
(1,2,...,n) P1(1,2,3,...,n), где P-1 - преобразование, обратное P. Для выполнения обратного преобразования у преобразователя, реализующего перестановку P достаточно поменять выходы и входы. Поэтому, если на сортирующую сеть P наложить сеть P1с аналогичной топологией, у которой входы заменены на выходы, получим устройство, реализующее заданную перестановку (0,1,2,...,n). Имитационная модель разработанного устройства получила название BCTAS. В диссертации показано, что с использованием топологии сортирующей среды нетрудно построить преобразователь, осуществляющий обратное преобразование (0,1,2,...,n). Аппаратурная сложность предложенного устройства составляет On log2 n , что хуже, чем у модели BCTAM. При этом скорость настройки переключателей коммутационной матрицы значительно выше и определяется числом последовательно соединенных компараторов используемой сортирующей сети.
Число двоичных разрядов чисел, сравниваемых компараторами, составляет log2n.
При использовании компараторов с пирамидальной структурой оценка задержки выполнения преобразований составляет 4(log2n)2tз, где tз - задержка на одном логическом инверторе, нагруженном на четыре входа. Недостатком устройства BCTAS является низкая производительность осуществления фиксированных преобразований форматов данных, время выполнения которых в устройствах BCTAM составляет не более (4log2n) tз.
В связи с этим на базе устройства BCTAM, формирующего упорядоченные разбиения входных данных на два подмножества, были разработаны принципы построения и функционирования универсального устройства, осуществляющего статические и динамические преобразования форматов данных. Разработанные принципы включают теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями формирователей, о декодировании битов управления. Теоремы о композиции формирователей упорядоченных разбиений обеспечивает ряд способов структурного синтеза матрицы устройства. На основе теорем о формировании сигналов управления переключателями матрицы и о декодировании битов управления показано, что наиболее перспективным решением является коммутационная матрица на базе сети baseline, которая удовлетворяет уравнению (3). В результате было разработано устройство, осуществляющее две новые инструкции: bsn r1=r2, ar.b1, ar.b2, ar.b3 и grpm r1=r2, r3, где r2 - регистр входных данных, r1 - регистр выходных данных, ar.b1, ar.b2, ar.b3, r3Ц регистры, хранящие код управления перестановкой.
На рис. 3 приведена диаграмма, иллюстрирующая преобразования, осуществляемые с использованием инструкций bsn, grp, grpm для случая n=8, где в верхней части рисунков расположены регистр управляющих кодов r3 и регистр входных данных r2, а в нижней части рисунков изображен регистр выходных данных r1. Отличие инструкции grpm от grp заключается в том, что при использовании инструкции grp сгруппированные данные сохраняют свой первичный порядок, а при использовании инструкции grpm порядок данных, выбранных с использованием битов управления с низким логическим уровнем, меняется на обратный. Инструкция bsn предназначена для статического преобразования форматов данных, a инструкция grpm - для динамического, так как настройка коммутационной матрицы при использовании этой инструкции выполняется значительно быстрее с использованием разработанных средств аппаратурной поддержки. В диссертации показано, что произвольное преобразование форматов данных формируется с использованием последовательно log2n инструкций grpm или двух инструкций bsn, которые осуществляют преобразование входной и выходной частей коммутационной матрицы модели BCTAM.
Рис. 3. Диаграмма преобразований, осуществляемых с использованием инструкций bsn, grpm, grp На рис. 4 представлена структурно-функциональная схема разработанного устройства GRPM-64, выполняющего преобразования данных длиной n=64 бит с использованием инструкций grpm и bsn. Коммутационная матрица устройства включает 6 уровней преобразования bsn1-bsn6. В зависимости выполняемой инструкции bsn или grpm блок FP осуществляет одну из двух фиксированных перестановок.
Рис. 4. Структурно-функциональная организация устройства формирования преобразований форматов данных, осуществляющего инструкции bsn и grpm Декодер бит управления, помещаемых в регистр r3 процессора, включает сумматоры, осуществляющие вычисление порядковых номеров следования бит с высоким и низким логическим уровнем, и формирующие биты управления переключателями коммутационной матрицы устройства.
Предложены и обоснованы способы синтеза сумматоров декодера. Согласно одному способу сумматоры образуют пирамидальную структуру. Число сумматоров в декодере определяется выражением 3/2n. Задержка преобразования составляет 2tslog2n, где ts - задержка, создаваемая сумматором. Исследована возможность использования в декодере структур параллельных префиксных сумматоров Ладнера-Фишера (Ladner-Fischer), Кога-Стоуна (Kogge-Stone), Брента-Кунга (Brent-Kung), Хана-Карлсона (Han-Carlson). С их использованием удалось сократить общую задержку выполнения инструкции grpm до 28 задержек на инверторе, нагруженном на четыре входа.
Устройство GRPM-64 позволило объединить преимущества быстрого выполнения статических преобразований форматов данных с использованием модели BCTAM и обеспечения динамического преобразования форматов данных в модели BCTAS. При этом аппаратурная сложность устройства составляет O(nlog2n).
Доказаны следующие утверждения:
любые параллельные инструкции pex выделения и группировки с сохранением начального порядка бит данных могут быть осуществлены с использованием наложения битовой маски на входные данные и однократного преобразования упорядоченного разбиения входных данных на два подмножества с использованием устройства BCTAM;
любые параллельные инструкции deposit размещения бит данных в заданных позициях машинного слова могут быть осуществлены с использованием однократного преобразования, обратного упорядоченному разбиению входных данных, на два подмножества с использованием устройства BCTAM и наложения битовой маски на выходные данные;
инструкции grp могут быть осуществлены путем однократного параллельного использования двух устройств BCTAM, обеспечивающих упорядоченные разбиения входных данных на два подмножества;
инструкции логического сдвига могут быть осуществлены путем однократного преобразования упорядоченного разбиения входных данных на два подмножества с использованием устройства BCTAM.
На основании проведенных исследований разработаны варианты структурно-функциональной организации и модели устройств, осуществляющих инструкции bsn, grpm, grp, pex.v, pdep.v, pex, pdep, rotate, shift. Показано, что для реализации перечисленных инструкций устройство BCTAM следует выполнять на базе многоуровневой коммутационной сети baseline. Возможно также использование любых коммутационных сетей, изоморфных baseline.
В главе 4 описаны принципы построения и модели устройств, формирующих перестановки с заданной структурой циклов и устройств для перечисления упорядоченных разбиений входных данных.
В основу работы устройств, формирующих перестановки и упорядоченные разбиения с заданной структурой циклов, положен метод формирования сопряженных перестановок. Перестановки A, B, являются сопряженными, если существует перестановка такая, что =, где - перестановка, обратная.
Из теории групп известно, что перестановки являются сопряженными в том и только том случае, если их цикловые структуры одинаковы. Таким образом, если - фиксированная перестановка с заданной цикловой структурой, то для любой перестановки с аналогичной цикловой структурой существует перестановка, такая что =. Используя различные перестановки, можно перечислить весь класс сопряженных элементов с заданной цикловой структурой. Цикловая структура записывается в виде Е, где - количество различных длин циклов в циклической записи перестановки, длина -го цикла, а - количество циклов длины, входящих в перестановку. В диссертации показано, что для формирования перестановки с заданной цикловой структурой перестановки, можно представить в виде произведения двух перестановок =, =, где, - прямая и обратная перестановки, формирующие неупоря доченные разбиения входных данных на подмножества c1,..,cs,, - перестановки с фиксированной неподвижной точкой, которые осуществляют полноцикловые преобразования подмножеств с, с, Е, с.
На основе проведенных исследований в данной главе представлены результаты разработки аппаратурных формирователей перестановок с заданной цикло вой структурой. Синтез матриц формирователей перестановок,,, осуществлен с использованием переключателей, осуществляющих прямое и обратное преобразования одновременно. Показано, что аппаратурная сложность разработанных устройств составляет O(nlog2n), а задержка формирования перестановки с заданной цикловой структурой не превосходит (8log2n)tз, что вдвое больше, чем в моделях BCTAM, так как в данных устройствах последовательно выполняются прямая и обратная перестановки. Для увеличения производительности формирования перестановок с заданной цикловой структурой предложено использовать устройства BCTAP, имеющие аппаратурную сложность O(n2). Разработаны и обоснованы модели устройств, осуществляющих прямые и обратные перестановки под управлением одинаковых кодов. Показано, что в этом случае время формирования перестановки составляет не более (2log2n)tз, так как задержка определяется временем работы дешифраторов, одновременно используемых для формирования прямой и обратной перестановок.
Комбинаторные процедуры перебора перестановок, сочетаний и разбиений различных элементов представляют собой трудоемкие процессы, значительно снижающие производительность вычислительной техники. Предложен метод построения комбинаторных формирователей упорядоченных разбиений чисел (0,1,2,Е,n) с использованием преобразований, обратных упорядоченным разбиениям входных данных на два подмножества и формирующих сочетания бинарных наборов. Формирование упорядоченных разбиений осуществляется поразрядно, с использованием формирователей сочетаний бинарных наборов.
Различные устройства для перечисления перестановок и сочетаний предлагались в работах Курейчика, Щербакова и др., однако предложенное в диссертации решение позволило упростить конструкцию формирователя, аппаратурная ( ) сложность которого составляет, в отличие от.
Глава 5 посвящена исследованию принципов построения и разработке универсальных вероятностных формирователей упорядоченных разбиений и перестановок с произвольной и заданной структурой циклов, увеличивающих производительность вычислительной техники при решении задач, связанных с обработкой данных в системах RPMA, тестированием, защитой данных от нелицензионного копирования, обеспечением защиты информации. Проведены исследования научно-технических принципов построения цифровых генераторов случайных сигналов (ГСС) на базе систем с хаотической динамикой.
Разработке алгоритмов формирования случайных перестановок с произвольной и заданной структурой циклов посвящено большое количество работ разных авторов. В диссертации были разработаны модель и устройство синхронного формирователя перестановок последовательного действия, работа которого основана на аппаратурной реализации модифицированного алгоритма Фишера-Йетса.
Исследования данного устройства показали, что аппаратурная поддержка последовательных алгоритмов не приводит к существенному увеличению производительности системы.
На основе разработанных формирователей базовых преобразований форматов данных в диссертации были разработаны принципы построения и функционирования высокопроизводительных вероятностных устройств параллельного действия для формирования упорядоченных разбиений и перестановок с произвольной и заданной структурой циклов.
На рис. 5 приведена структурная схема вероятностного формирователя упорядоченных разбиений, для случая n=16, u=0. Устройство состоит из блока регистров данных и многоуровневой коммутационной сети baseline. Где D1 - Dn - параллельные q разрядные входы блока регистра данных и выходы коммутационной матрицы; Q1 - Qn - параллельные q разрядные выходы блока регистров данных и выходы формирователя; S1 - Sn - q разрядные входы коммутационной матрицы; С1 - Сm - бинарные входы формирователя для подачи управляющих сигналов от внешних источников случайных сигналов; А1 - Аn - начальная строка q разрядных данных, загружаемая в блок регистров данных; Vi, j - переключатели коммутационной матрицы; PE - бинарный вход управления последовательной и параллельной записью данных; S - последовательный q разрядный вход блока регистров данных для записи элементов начальной строки данных А1 - Аn; clk - вход тактовых импульсов.
Преимуществом данного формирователя является быстрый рост энтропии Hm распределения вероятностей генерируемых последовательностей, где m - число импульсов на входе clk. В диссертации показано, что для рассматриваемых устройств энтропия Hm достигает значения более 50% от максимальной величины за один тактовый импульс.
Приведенный пример иллюстрирует метод построения высокопроизводительных вероятностных формирователей упорядоченных разбиений и перестановок с произвольной и заданной структурой циклов, и равномерным распределением вероятностей. Согласно разработанной методике вероятностные формирователи строятся на основе описанных в третьей главе диссертации преобразователей форматов данных, выходы которых соединены с входами через буферный регистр.
В диссертации показано, что процессы, протекающие в разрабатываемых устройствах, описываются однородными цепями Маркова с конечным числом состояний.
Поэтому последовательность вероятностных распределений (1,2...,r )i формиr руемых разбиений определяется выражением (1,2...,r )i 1 (1,2...,r )i pij 1, где r матрица pij 1 оказывается дважды стохастической с отсутствием нулевых элементов, что приводит к быстрой экспоненциальной сходимости последовательности (1,2...,r )i к равновероятному распределению 1 2 ... r.
Рис. 5. Структурная схема стохастического формирователя дескрипторов формата упорядоченных разбиений для случая n=16, u=Основными компонентами разработанных вероятностных устройств являются физические генераторы случайных сигналов (ГСС). В качестве источников случайных сигналов предложено использовать генераторы динамического хаоса. В диссертации сформулированы и обоснованы условия непредсказуемости используемых генераторов. Предложена модель хаотического формирователя случайных чисел и временных интервалов, удовлетворяющего сформулированным условиям.
Предложенный в диссертации метод построения ГСС обеспечивает построение формирователей импульсов случайной длительности и случайных бинарных кодов с равномерной функцией распределения вероятностей, устойчивых к внешним воздействиям. Возможность исполнения разработанных ГСС в виде интегральной микросхемы с использованием только стандартных цифровых элементов позволяет без дополнительных исследований использовать при их производстве различные технологические процессы, а также реализовать ГСС на ПЛИС. Перечисленные свойства являются очень важными для практических применений.
Согласно модели функционирования ГСС по запросу системы в некоторые моменты времени Ti на основе внутреннего состояния X (Ti ) генератора формиру ется цифровой сигнал {DS}T. Система определяет состояние X (Ti ) с погрешноi стью , таким образом, {DS}T генерируется на основе любого значения X из i окрестности X (Ti ) в фазовом пространстве системы {X} {X : X, X X (Ti ) }.
Ti Цифровой сигнал {DS}T генерируется системой по известному наблюдателю алгоi ритму S для X (Ti) {X}, S(X (Ti )) {DS}T. ГСС будет непредсказуемым, если наTi i блюдатель не сможет определить его состояние с погрешностью, не превышающей в требуемые моменты времени Ti даже в том случае, если некоторые значе ния из последовательности X (Ti ) ему известны.
Утверждение. Генератор динамического хаоса вычислительно непредсказу ем, если погрешность n определения его состояния Xn экспоненциально возрастает при моделировании в прямом и обратном времени.
В диссертации рассмотрены два типа систем с дискретным и непрерывным временем, для которых доказываются следующие утверждения.
Генератор динамического хаоса на базе отображения X F(X ) вычисn1 n лительно непредсказуем, если в спектре собственных значений матрицы T 1s 2s присутствуют два собственных значения,, одно из коA ( X ) A ( X ) n n торых 1s 1, а другое 1, где A(X ) - матрица Якоби для F (X ).
2 s n n dX Генератор динамического хаоса на базе потоковой системы F(X ) выdt числительно непредсказуем, если в каждой точке фазовой траектории ГСС в спекT тре собственных значений матрицы A A присутствуют положительs ные и отрицательные значения, где AЦ матрица Якоби F (X ).
Приведенным условиям вычислительной непредсказуемости удовлетворяет предложенный и исследованный в диссертации формирователь случайных бинарных последовательностей, моделируемый системой с хаотической динамикой.
Структурно-функциональная схема разработанного формирователя представлена на рис. 6. Его работа описывается двухмерным отображением fg fg ; kn1 f11 f12 kn N ), (4) m fg fg mn mod( n1 ;
f21 f22 где, - частоты задающих генераторов G, G11, G12, G21, G22. Таким образом, частоты задающих генераторов являются параметрами управления в модели предложенного формирователя.
Рис. 6. Структурно-функциональная схема генератора случайных временных интервалов Для обеспечения вычислительной непредсказуемости необходимо, чтобы отображение (4) было гиперболического типа, что выполняется при fg f11 f22 1 1 2; .
f11 f22 f11 f22 f12 f21 fgФормирователь состоит из шести N-разрядных двоичных счетчиков: А11, А12, А21, А22, X, Y и пяти задающих генераторов. В состав формирователя входит также логический блок ВС, пропускающий импульсы от соответствующих генераторов G11, G21 при обнулении счетчиков А12 и А22 соответственно. Данную схему можно реализовать только на цифровых элементах, используя в качестве G, G11, G12, G21, G22 быстродействующие автогенераторы, частота колебаний которых определяется инерционными свойствами используемых логических элементов.
В начальный момент времени счетчики X, Y обнуляются, в А11, А21 заносится начальное значение k0, а в счетчики А12, А22 заносится значение m0. После этого тактовые импульсы от генераторов G, G12, G22 подаются на соответствующие счетчики X, Y,А12, А22, причем А12, А22 осуществляют реверсивный счет, а Xn+1, Yn+1 - прямой. После обнуления счетчиков А12, А22, тактовые импульсы от генераторов G11, G21 через логические схемы Б1 поступают на счетчики А11, А21, осуществляющие реверсивный счет. Цикл завершается в момент обнуления этих счетчиков. Для осуществления следующего цикла содержимое счетчиков X, Y записывается в А11, А21 и А12, А22 соответственно.
Учитывая флуктуации частоты колебаний генераторов G, G11, G12, G21, G22, числа kn,mn являются случайными величинами.
В качестве задающих генераторов G, G11, G12, G21, G22 предложено использовать разработанные в пятой главе магнитоэлектронные генераторы, достоинствами которых являются широкая спектральная полоса генерируемых колебаний, возможность исполнения в интегральном виде, широкий диапазон рабочих частот. На рис. 7 приведена микрофотография разработанного магнитоэлектронного генератора, а на рис. 8 - спектр генерируемых им колебаний. Ширина спектральной линии по уровню -3дБ составляет около 5 кГц.
Рис. 7. Микрофотография магнитоэлектрон- Рис. 8. Спектр сигнала магнитоэлектронного ного генератора в квазимонолитном испол- генератора нении На рис.9 представлена микрофотография кристалла гибридной микросхемы формирователя импульсов случайной длительности. Кристалл изготовлен на фабрике SilTerra (Малайзия) с использованием технологического процесса КМОП 0,18 мкм. Размеры кристалла: 3,021 х 1,809 мм.
Рис.9. Микрофотография кристалла ГСС Учитывая возможность внешнего воздействия на ГСС с целью изменения режима работы, необходимо, чтобы условие непредсказуемости ГСС сохранялось при любом возможном внешнем воздействии. Для обеспечения безопасности в аппаратуру с генераторами случайных сигналов в диссертации предложено встраивать средства контроля характера колебаний. Рассмотрены два подхода к решению этой задачи: детекторы режимов функционирования генераторов на основе спектрального анализа и анализа статистики возвратов изображающей точки в фазовом пространстве системы.
Структурно-функциональная схема спектрального детектора режимов приведена на рис. 10, где ГСС - контролируемый генератор случайных сигналов, ГКЧ - генератор качающейся частоты, СМ - смеситель, ФПЧ - фильтр промежуточной частоты, УО - усилитель-ограничитель, Д - амплитудный детектор, ИУ - интегрирующий усилитель, ИНД - устройство индикации и сигнализации.
Рис. 10. Структурно-функциональная схема спектрального детектора хаотических колебаний На выходе интегрирующего усилителя будет сигнал:
T UИУ СМ wK KФПЧKУОKДU0 H(w1p (t)modwp) dt, 2T где w w2 p w1p - полоса пропускания ФПЧ, wp w2 p w1p - полоса контролируемых детектором частот, KСМ - коэффициент преобразования смесителя, KФПЧ - модуль коэффициента передачи ФПЧ, K - коэффициент передачи детекД тора, KУО коэффициент передачи усилителя-ограничителя, H(w)Ц Фурье образ сигнала ГСС U (t), U0 - амплитуда сигнала гетеродина.
Блок УО ограничивает амплитуду сигналов и wK KФПЧ KУОKДU0 H (w1 p (t)mod wp ) Amax, и в случае случайных коСМ УО C лебаний на выходе интегрирующего усилителя будет сигнал U Amax. В случае ИУ УО периодических колебаний с числом гармоник N, попадающих в диапазон max АУО Nw w П UИУ (w2 p,w1p ) :. Так как 1, при смене режима колебаний конwр wр тролируемого генератора сигнал на выходе ИУ уменьшается практически до нуля.
Предложенный спектральный детектор прост, не требует настройки и особенно эффективен при анализе быстродействующих ГСС, когда исследования во временной области затруднительны.
Второй предложенный в диссертации метод опирается на теорему Пуанкаре о возвратах. Для реализации метода осуществляется временная обработка сигнала, поэтому данный метод применим для контроля относительно низкочастотных ГСС.
Если случайный сигнал формируется динамической системой, то фазовая траектория X (t) будет устойчивой по Пуассону в том случае, если обладает свойством возвращаться в сколь угодно малую окрестность каждой своей точки бесконечное число раз. Возврат Пуанкаре - это возврат траектории в -окрестность произвольно выбранной на ней начальной точки. Пусть T1,T2...Tn последовательность периодов возврата. Если колебания периодические, то T1 T2 ... Tn T.
Если колебания квазипериодические, то T1 T2 ... Tn T ( ) - результат, аналогичный случаю периодических колебаний, но время возврата будет возрастать с уменьшением : lim T ( ) . В случае хаотических колебаний T1,T2...Tn - слу чайные величины с некоторым распределением. В диссертации разработаны методика построения и модель устройства, контролирующего значения T1,T2...T.
n Глава 6 посвящена экспериментальной проверке разработанных устройств.
В данной главе на примерах различных задач проведена оценка повышения производительности вычислительной техники при использовании преобразователей форматов данных, разработаны рекомендации к использованию и приведены примеры внедрения разработанных устройств.
На базе предложенных в диссертации методов построения генераторов случайных сигналов и стохастических комбинаторных формирователей в ОАО Тантал была разработан многофункциональный программируемый формирователь случайных последовательностей и сигналов с контролем режима функционирования. Устройство предназначено для использования в системах защиты информации, вычислительных методах Монте-Карло, процедурах тестирования аппаратуры и т.п. Отличительными особенностями разработанных формирователей являются обеспечение вычислительной непредсказуемости, определяемой согласно методике, разработанной в диссертации, исполнение в виде интегральной микросхемы, контроль роста энтропии в системе.
В классе 16-разрядных архитектур был разработан модуль формирования упорядоченных разбиений, обеспечивающий приемлемое сочетание функциональности и сложности реализации. Модуль был реализован на базе FPGA (fieldprogrammable gate array) серии APEX 20K фирмы Altera с использованием платы APEX PCI Development board. На рис. 11 представлена фотография модуля BCTAM16X256, предназначенного для формирования упорядоченных разбиений блоков данных длиной 256 бит. Задержка преобразования данных составляет около 10 нс, что обеспечивает пиковую скорость преобразования до 25,6 Гб/с. При этом производительность устройства определяется пропускной способностью используемой шины PCI-X. Данный формирователь использовался для защиты файлов изображений от несанкционированного копирования.
Рис. 11 Внешний вид модуля BCTAM16X2Результаты исследований, полученные в диссертации, позволили создать новый высокоскоростной и эффективный в аппаратурном исполнении модуль GRPM-64B для манипуляций с битами данных, осуществляющий инструкций grp, pex.v, pdep.v, pex, pdep, shift, rotate и новые инструкции bsn и grpm. Используя две инструкции bsn, можно выполнить произвольную перестановку входных данных.
Время выполнения инструкций составляло от 12 до 22tз без организации конвейерной обработки.
В шестой главе рассмотрен ряд часто решаемых средствами вычислительной техники задач, на которых показана эффективность использования разработанного модуля. Ускорение выполнения алгоритмов обусловлено параллельной обработкой нескольких групп бит данных, находящихся в регистре процессора.
Кроме этого, инструкции grp и grpm оказываются очень эффективными в случаях, когда результат перестановки зависит от входных данных. При проведении исследований использовалась система моделирования SimpleScalar. Задержка выполнения инструкций grpm, pex.v, pdep.v составляла два цикла процессора. Остальные параметры Simplescalar были аналогичны параметрам, используемым Y. Hilewitz и R. Lee.
В таблица 3 представлены результаты ускорения сортировки 64 элементов данных различного размера c использованием модели GRPM-64B. При этом сортируемые элементы представлялись четырехразрядными, восьмиразрядными и шестнадцатиразрядными подсловами. Минимальное ускорение по сравнению с алгоритмом сортировки слиянием составляет более 12 раз.
Таблица Ускорение сортировки 64 подслов данных c использованием модели GRPM-64B Размер подслов, бит 4 8 Пузырьковая сортировка 408.3 128.9 43.Сортировка выбором 272.7 86.1 29.Сортировка слиянием 104.4 32.8 12.При сортировке большого числа элементов использование инструкций grpm также приводит к существенному ускорению. При этом для сортировки больших фрагментов могут использоваться стандартные алгоритмы сортировки слиянием, а небольшие фрагменты сортируются с использованием инструкций grpm. В таблица 4 представлены результаты увеличения скорости сортировки слиянием строки данных длиной N подслов данных размером m бит c использованием модели GRPM-64B.
Таблица Ускорение сортировки N m-разрядных подслов данных c использованием модели GRPM-64B N 128 256 512 1024 2048 4096 8192 16384 32768 41943m=6,9 4,0 3,0 2,5 2,2 2,0 1,9 1,7 1,7 1,m=6,8 3,9 3,0 2,5 2,2 2,0 1,8 1,7 1,7 1,m=6,4 3,8 2,9 2,4 2,2 2,0 1,8 1,7 1,6 1,С увеличением N эффективность использования инструкций grpm уменьшается, так как все большая часть программы выполняется с использованием стандартной процедуры сортировки слиянием. Тем не менее, при длине сортируемой последовательности более четырех миллионов увеличение производительности за счет использования инструкции grpm составляет 1,4 раза.
В таблица 5 приведены результаты проведенных оценок ускорения выполнения различных алгоритмов.
Таблица Ускорение выполнения алгоритмов c использованием модели GRPM-64B Виды обработки информации Ускорение работы алгоритма, разы Медианная фильтрация изображений 4,Распознавание геометрических образов и символов на бинарных 2,изображениях Коррекция морфологии изображений 1,Упаковка и распаковка данных 2,LSB стеганография Прямое преобразование 1,Обратное преобразование 2,UUE (Uuencode) Прямое преобразование 2,Обратное преобразование 2,Биоинформатика (операция трансляции) 2,Формирование последовательностей перестановок в системах 10,RPMA Обработка данных в системах RPMA 9,Криптографический алгоритм DES 2,Алгоритм DES, генерация ключей 15,Криптографический алгоритм RC5 2,Защита файлов мультимедиа от нелицензионного копирования 10,Результаты проведенных исследований находятся в соответствии с данными, полученными Y. Hilewitz и R. Lee, и свидетельствуют в среднем о более чем двукратном увеличении скорости выполнения программ.
Для использования в системах управления передатчиками помех КВ, УКВ и ДЦВ диапазонов серии Кентавр и аналогичных, с использованием разработанной в диссертации методики были разработаны устройства для контроля режимов функционирования генераторов случайных сигналов. Использование данного устройства в составе контроллеров генераторов помех является крайне важным, т.к.
позволяет исключить возможность возникновения последствий, связанных с поломкой и изменением режимов функционирования используемых генераторов.
Результаты, полученные в диссертации, обеспечили возможность реализации в ОАО Тантал проекта расширения архитектуры RISC процессора для ускорения выполнения преобразований на уровне битов и подслов данных. Данный процессор используется, в частности, для обработки данных в системе RPMA. Разработанная теория структурного синтеза формирователей упорядоченных разбиений и устройств управления ими обеспечила возможность построения универсального модуля для реализации инструкций grp и инструкций, аналогичных bfly, ibfly. Причем две инструкции bfly и ibfly заменены одной bsn. Предложенное решение апробировалось на базе процессора OpenRISC 1000 и в настоящее время является наиболее эффективным с точки зрения быстродействия и простоты аппаратурного исполнения.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ Основным результатом диссертационной работы является решение крупной научной проблемы, имеющей важное народно-хозяйственное значение, заключающейся в разработке основ функционирования и методов построения детерминированных и вероятностных устройств формирования изоморфных представлений данных, увеличивающих производительность вычислительной техники.
При проведении исследований получены следующие научные и практические результаты:
1. На основе сформулированных в диссертации положений использования упорядоченных разбиений в качестве базовых преобразований входных данных разработана и обоснована структура комплекса новых детерминированных и вероятностных устройств формирования изоморфных представлений данных. Доказано, что использование разработанных устройств приводит к увеличению производительности вычислительной системы на базе разрядного процессора от 2 до 10 раз для задач сортировки, распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шумов на изображениях, операций преобразования представлений генетических последовательностей в биоинформатике, обработки данных в системах RPMA, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.
2. Разработаны теоретические положения, обеспечивающие структурный синтез и принципы функционирования устройств, формирующих упорядоченные разбиения входных слов данных длиной n на подмножества с произвольной и заданной структурой циклов. На базе многоуровневых коммутационных и сортирующих сетей и матричных коммутаторов предложены устройства, имеющие аппаратурную сложность O(n), O(nlog2n), O(n(log2n)2), O(n2). Проведена сравнительная оценка их производительности и разработаны рекомендации к применению.
3. Разработанные положения структурного синтеза формирователей упорядоченных разбиений и блоков управления ими обеспечили создание универсального устройства для поддержки новых инструкций bsn и grpm, осуществляющих динамическое и статическое преобразования форматов данных.
Показана эффективность предложенного решения для осуществления манипуляций с битами и подсловами данных, реализуемых с использованием специализированных инструкций, таких как pex.v, pdep.v, pex, pdep, shift, rotate. Проведенный сравнительный анализ свидетельствует о том, что предложенное устройство в настоящее время является наиболее эффективным с точки зрения производительности и простоты аппаратурной реализации.
4. Разработаны и обоснованы принципы построения и модели детерминированных и вероятностных устройств, формирующих упорядоченные разбиения данных длиной n с произвольной и заданной цикловой структурой. Проведенные оценки показали, что предложенные устройства увеличивают производительность формирования перестановок с произвольной и заданной цикловой структурой примерно в n раз по сравнению с производительностью системы при реализации алгоритмов Фишера-Йетса (FisherЦYates) и Саттоло (Sattolo).
5. На стандартных цифровых элементах разработан формирователь случайных сигналов с равномерной функцией распределения вероятностей, моделируемый дискретным отображением с хаотической динамикой.
6. Для контроля режимов функционирования формирователей случайных сигналов на базе систем с хаотической динамикой впервые предложено использовать анализ периодов возвратов Пуанкаре. Разработаны и исследованы устройства встроенного контроля генераторов с хаотической динамикой.
7. Разработанные IP блоки, методики расчета и синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных в ЭВМ внедрены в ОАО Тантал, г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от нелицензионного копирования. Научные основы создания, принципы функционирования, математические и имитационные модели комбинаторных устройств формирования изоморфных представлений данных в ЭВМ внедрены при организации обучения специалистов студентов ГОУ ВПО Саратовский государственный университет им. Н.Г. Чернышевского. По результатам работы в ФГУ ФИПС зарегистрированы 3 программы и получены 12 патентов РФ на изобретения.
Основные результаты диссертации опубликованы в следующих работах:
Публикации в изданиях, рекомендованных ВАК РФ 1. Сотов Л.С. Математические модели транспозиционных преобразований / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин// Информационноизмерительные и управляющие системы. 2007. Т5. №12. С. 58-60.
2. Сотов Л.С. О формировании доверенной среды серверных систем управления базами данных / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2008. №3. C.2327.
3. Сотов Л.С. Динамическое форматирование структурных объектов хранилищ данных / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2008. №4. С. 28-33.
4. Сотов Л.С. Экспериментальные исследования гибридного интегрального магнитоуправляемого генератора / А.Л. Хвалин, Л.С. Сотов, С.В. Овчинников, В.П. Кобякин // Приборы и системы. Управление, контроль, диагностика. 2009. №11. С.42-44.
5. Сотов Л.С. Использование генераторов динамического хаоса в системах информационной безопасности / Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2009. №2. С. 32-6. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок/ Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационноизмерительные и управляющие системы. 2009. Т.7. №10. С.78-85.
7. Сотов Л.С. Модели устройств кросс-кластерных перестановок данных в ЭВМ / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Вестник компьютерных и информационных технологий. 2009. №12. С.51-55.
8. Сотов Л.С. Сложная динамика генераторов на диоде Ганна с низкочастотным контуром / Г.Н. Коростелев, Л.С. Сотов // Изв. вузов. Радиотехника и электроника. 1989. Т.34. N9. С.1925-1929.
9. Сотов Л.С. Цифровой генератор подкачки энтропии на базе отображения Арнольда / Л.С. Сотов, В.Н. Харин // Известия вузов. Прикладная нелинейная динамика. 2009. Т.17. № 6. С.57-66.
10. Сотов Л.С. Квазишумовые режимы магнитоэлектронных генераторов/ А.Л.
Хвалин, Л.С. Сотов // Вопросы электромеханики. 2009. Т. 113. №6. С.55-59.
11. Сотов Л.С. Кросс - кластерная коммутационная матрица для аппаратурной поддержки управляемой перестановки данных в криптографических системах / Л.С. Сотов, C.C. Соболев, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2009. №4. С. 56-63.
12. Сотов Л.С. Модель инволютивного транспозиционного преобразователя/ Л.С. Сотов, А.А. Солопов, А.В. Фарафонова // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.34-46.
13. Сотов Л.С. Алгоритм работы и модель функционального генератора перестановок / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Информационные технологии. 2010. №4. С.41-46.
14. Сотов Л.С. Детекторы режимов функционирования генераторов случайных сигналов / Л.С. Сотов, В.Н. Харин, А.Л. Хвалин //Автоматика и телемеханика. 2010. №5. С.166-170.
15. Сотов Л.С. Простой матричный формирователь r-выборок / А.В. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.47-56.
16. Сотов Л.С. Встроенные средства контроля генераторов случайных сигналов / Л.С. Сотов, В.Н. Харин, А.Л. Хвалин // Приборы и системы. Управление, контроль, диагностика. 2010. №7. С.30-33.
17. Сотов Л.С. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии / А.В. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.57-71.
18. Сотов Л. С. Комбинаторная модель функционального формирователя разбиений бинарного множества / Л. С. Сотов // Информационные технологии. 2010. №10. С. 46-52.
19. Сотов Л.С. Формирователи перестановок с управляемой цикловой структурой / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011. Вып. 9. С.4355.
20. Сотов Л.С. Аппаратные устройства формирования прямых и обратных перестановок данных / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011.
Вып. 9. С.61-77.
21. Сотов Л.С. Методы синтеза устройств, выполняющих инструкции перестановки битов данных / Л. С. Сотов // Гетеромагнитная микроэлектроника.
2011. Вып. 10. С.25-50.
22. Сотов Л.С. Об эффективности использования специальных команд преобразования форматов данных в вычислительной технике / Л. С. Сотов // Гетеромагнитная микроэлектроника. 2011. Вып. 10. С.61-80.
Публикации в других изданиях 23. Сотов Л.С. Динамическое форматирование представлений объектов реляционных СУБД на основе кластерных транспозиций/ Ж. А. Молодченко, Л.С.
Сотов, В. Н. Харин //Естественные и технические науки. 2007. № 6 (32).
С.224-226.
24. Сотов Л.С. Алгоритм создания диверсификационного метода битовых преобразований/ Ж.А. Молодченко, Л.С. Сотов, В. Н. Харин // Естественные и технические науки. 2007. № 6 (32). С.220-223.
25. Сотов Л.С. Модуль генерации форматирующих сред в распределенных реляционных СУБД/ Ж.А. Молодченко, Л.С. Сотов, В. Н. Харин // Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО Том 1/Под ред.Н.К.Юркова - Пенза:Изд-во Пенз.гос.ун-та, 2006. - С. 179-182.
26. Сотов Л.С. Расчёт характеристик интегрального магнитоуправляемого генератора в диапазоне частот 26,0 Е 37,5 ГГЦ/ А.Л. Хвалин, Л.С. Сотов, А.В.
Васильев //Приборы и системы. Управление, контроль, диагностика. 2010.
№ 11. С. 47-49.
27. Сотов Л.С. Модуль сервера форматирования в распределенных реляционных СУБД с повышенным уровнем ИБ/ Ж.А. Молодченко, Л.С. Сотов, В. Н.
Харин // НАДЕЖНОСТЬ И КАЧЕСТВО: труды международного симпозиума Т. 1 / Под ред.Н.К. Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2006.
С. 182-184.
28. Сотов Л.С. К вопросу об архитектуре аналого-цифровых систем генерации случайных сигналов / Ж.А. Молодченко, Л.С. Сотов, В. Н. Харин // НАДЕЖНОСТЬ И КАЧЕСТВО: труды международного симпозиума / Под ред.
Н.К. Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2007. С. 85-87.
29. Сотов Л.С. Аппаратный акселератор сервера форматирования данных / Ж.
А. Молодченко, Л.С. Сотов, В. Н. Харин // НАДЕЖНОСТЬ И КАЧЕСТВО:
труды международного симпозиума / Под ред. Н.К.Юркова. Пенза: Изд-во Пенз. гос. ун-та, 2007. С. 134-136.
30. Сотов Л.С. Эффективный прямошумовой генератор / Л.С. Сотов, Д.В. Тугушов, А.А. Игнатьев, А.Г. Передумов, А.В. Безруков // Тезисы докладов и сообщений 1 Международной научно-технической конференции Физика и технические приложения волновых процессов. Т.1. 10-16 сентября 2001.
С. 148.
31. Сотов Л.С. Динамическое форматирование данных в распределенных информационно-управляющих системах / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Материалы Международной научной конференции Проблемы управления, передачи и обработки информации (АТМ-ТКИ-50) СГТУ 16 - 18 сентября 2009 г. 2 с.
32. Сотов Л.С. Концепция TCB-платформы для распределенных информационно вычислительных систем специального назначения / Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 3. C.66-72.
33. Сотов Л.С. Моделирование архитектуры акселератора битовых перестановок с использованием САПР SYSTEM STUDIO фирмы SYNOPSYS / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та. 2008. Вып. 3. С. 60 - 66.
34. Сотов Л.С. Модели аппаратурных акселераторов перестановок бинарных множеств / Ж.А. Молодченко, С.В. Овчинников, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008.
Вып. 4. С.11-22.
35. Сотов Л.С. Математические модели стохастического формирования изоморфных представлений структурных элементов данных в ЭВМ/ Ж.А. Молодченко, Л.С. Сотов, В.Н Харин // Гетеромагнитная микроэлектроника.
2008. Вып.4. С. 29 - 41.
36. Сотов Л.С. Средства разработки и исследования архитектурных моделей в САПР System Studio. Использование инструментов System Studio при моделировании матричного генератора перестановок / Л.С. Сотов, А.Л. Хвалин // Гетеромагнитная микроэлектроника. 2008. Вып. 5. С.112-121.
37. Сотов Л.С. Средства разработки и исследования архитектурных моделей в САПР System Studio. Основные объекты SystemC и их использование / Л.С.
Сотов, А.Л. Хвалин // Гетеромагнитная микроэлектроника. Вып. 5. С.121146.
38. Сотов Л.С. Матричные акселераторы транспозиционных преобразований форматов данных в ЭВМ / Ж.А. Молодченко, Л.С. Сотов, А.А. Солопов, В.Н. Харин // Гетеромагнитная микроэлектроника. Вып. 6. С.91-107.
39. Сотов Л.С. Архитектура генераторов комбинаторных дескрипторов формата/ Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин //Гетеромагнитная микроэлектроника. 2009. Вып. 6. С. 108-119.
40. Сотов Л.С. Первичный преобразователь на основе ЖИГ - генератора для измерения сильных магнитных полей/ А.Л. Хвалин, С.В. Овчинников, Л.С.
Сотов, В.Н. Самолданов //Датчики и системы. 2009. №10. C. 57-58.
41. Сотов Л.С. Генераторы случайных импульсов на базе модельного отображения сдвиг Бернулли / А.Л. Блинов, Ж.А. Молодченко, Л.С. Сотов, В.Н.
Харин // Гетеромагнитная микроэлектроника. 2009. Вып. 6. С.120-130.
42. Сотов Л.С. Cтруктура подсистемы стохастической генерации дескрипторов форматов / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин //Аспирант и соискатель. 2009. № 4. С. 86-88.
Патенты и зарегистрированные программы 43. Пат. на изобретение RU № 2320000 C1, МПК G06F 7/76 (2006.01), G06F 12/14 (2006.01). Дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2007105175/09; заявл. 13.02.2007; опубл.
20.03.2008, Бюл. №8, 6 с.
44. Пат. на изобретение RU № 2334272 C1, МПК G06F 21/22 (2006.01), G06F 12/14 (2006.01). Устройство защиты от несанкционированного доступа к информации / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия).
№ 2007105177/09; заявл. 13.02.2007; опубл. 20.09.2008, Бюл. № 26, 8 с.
45. Пат. на изобретение RU № 2340931 C1, МПК G06F 7/58 (2006.01) H03K 3/84 (2006.01). Генератор случайных чисел / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2007111405/09; заявл. 28.03.2007; опубл.
10.12.2008, Бюл. № 34, 5 с.
46. Пат. на изобретение RU № 2390049 C1, МПК G06F 7/00 (2006.01). Параллельный дешифратор управляемой транспозиции информации, хранимой в персональной ЭВМ / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия).
№ 2008139529/09; заявл. 07.10.2008; опубл. 20.05.2010, Бюл. № 14, 8 с.
47. Пат. на изобретение RU № 2390052 C2, МПК G06F 7/76 (2006.01). Дешифратор управляемой перестановки информации, хранимой в персональной ЭВМ / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2008132009/09; заявл. 06.08.2008; опубл. 20.05.2010, Бюл. № 14, 8 с.
48. Пат. на изобретение RU № 2393594 C1, МПК H01P1/20 (2006.01). Полосовой ферритовый фильтр сверхвысоких частот / Хвалин А. Л., Сотов Л.С.
(Россия). № 2009117566/09; заявл. 12.05.2009; опубл. 27.06.2010, Бюл. № 18, 6 с.
49. Пат. на изобретение RU № 2395834 C1, МПК G06F 7/58 (2006.01). Генератор случайных перестановок / Сотов Л.С., Харин В. Н., Хвалин А.Л. (Россия). № 2009104555/09; заявл. 12.02.2009; опубл. 27.07.2010, Бюл. № 21, 8 с.
50. Пат. на изобретение RU № 2405187 С1 МПК G06F7/24(2006.01). Устройство управляемой перестановки информации, хранимой в ЭВМ / Сотов Л.С., Харин В. Н. (Россия). № 2009111245/08; заявл. 30.03.2009; опубл.
27.11.2010. Бюл. № 33. 8 с.
51. Пат. на изобретение RU № 2408059 С2 МПК G06F 7/58 (2006.01) Генератор импульсов случайной длительности / Сотов Л.С., Харин В. Н., Хвалин А.Л.
(Россия). № 2009104553/08; заявл. 12.02.2009; опубл. 27.12.2010. Бюл. № 36.
7 с.
52. Пат. на изобретение RU 2409842 C1 МПК G06F 12/14 (2006.01) G06F 17/(2006.01). Устройство кросс-кластерной управляемой перестановки информации, хранимой в персональной ЭВМ / Сотов Л.С., Харин В. Н., Соболев С.С. (Россия). № 2009115317/08; заявл. 23.04.2009; опубл. 20.01.2011.
Бюл.№2. 8 с.
53. Пат. на изобретение RU 2417402 G06F7/00 (2006.01). Кросс-кластерная коммутационная матрица / Сотов Л.С. (Россия). № 2009133507; заявл.
07.09.2009; опубл. 27.04.2011. Бюл. №12. 13 с.
54. Пат. на изобретение RU 2419174 G11C 19/00 (2006.01) Устройство управляемого циклического сдвига / Сотов Л.С., Харин В. Н., Соболев С.С. (Россия). № 2009134344/08; заявл. 14.09.2009; опубл. 20.05.2011. Бюл. №14. 10 с.
55. Свидетельство об официальной регистрации программы для ЭВМ № 2004610988 (РФ). Программа расчета параметров модели Матерка полевого транзистора / Сотов Л.С. и др. Заявка № 2004610416. Зарегистрировано 21.04.2004.
56. Свидетельство об официальной регистрации программы для ЭВМ № 2004610989 (РФ). Программа расчета параметров модели Гумеля-Пуна биполярного транзистора / Сотов Л.С. и др. Заявка № 2004610417, зарегистрировано 21.04.2004.
57. Свидетельство о государственной регистрации программы для ЭВМ № 2010612449 (РФ). Программа моделирования комбинаторных преобразователей форматов представления данных в ЭВМ (DMATRIX) / Сотов Л.С. и др. Заявка № 2010610690, зарегистрировано 7.04.2010 г.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям