Комбинаторные устройства формирования изоморфных представлений данных, повышающие производительность вычислительной техники тема диссертации и автореферата по ВАК РФ 05.13.05, доктор технических наук Сотов, Леонид Сергеевич

• Сотов, Леонид Сергеевич
• доктор технических наук
• 2011

Оглавление диссертации доктор технических наук Сотов, Леонид Сергеевич

Введение.

Глава 1. Бит-ориентированные операции преобразования форматов данных в вычислительной технике.

1.1. Производительность средств вычислительной техники в задачах, связанных с преобразованиями форматов данных.

1.2. Использование преобразований форматов данных в системах защиты информации.

1.3. Инструкции обработки битов и подслов данных.

1.4. Проблемы использования аппаратурных средств преобразования форматов данных.

1.5. Основные результаты главы 1.

Глава 2. Концепция разработки и внедрения семейства устройств форматирования данных.

2.1. Принципы построения семейства комбинаторных устройств формирования изоморфных представлений данных.

2.2. Формализация задачи формирования изоморфных представлений данных.

2.3. Представление форматирующих преобразований, дескрипторы формата и методы их формирования.

2.4. Декомпозиция процедуры формирования упорядоченного разбиения.

2.5. Классификация базовых форматирующих преобразований бинарных векторов данных.

2.6. Основные результаты главы 2.

Глава 3. Структурный синтез и модели устройств базовых форматирующих преобразований.

3.1. Функциональный формирователь упорядоченных разбиений бинарных множеств с последовательной загрузкой ВСТА.

3.2. Организация обратных перестановок бинарных множеств с использованием сортирующих сетей.

3.3. Параллельный формирователь упорядоченных разбиений ВСТАР.

3.4. О композиции переключателей преобразователя упорядоченных разбиений п элементного множества входных данных.

3.5. Структурный синтез матричных преобразователей неупорядоченных разбиений п элементного множества входных данных.

3.6. Универсальное устройство преобразования форматов данных.

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

3.8. Формирователи перестановок и упорядоченных разбиений на базе топологий сортирующих сетей.

3.9. Синтез формирователей перестановок с заданной структурой циклов.

3.10. Инволютивный матричный преобразователь ВСТА1.

3.11. Сравнительная оценка аппаратурной сложности преобразователей форматов данных.

3.12. Основные результаты главы 3.

Глава 4. Методы построения и модели устройств перечисления множеств дескрипторов формата.

4.1. Модели и методы устройств комбинаторного формирования дескрипторов формата.

4.2. Комбинаторный генератор сочетаний элементов бинарных множеств.

4.3. Матричный комбинаторный генератор перестановок и упорядоченных разбиений числовых множеств PG.

4.4. Исследование псевдослучайных генераторов перестановок и упорядоченных разбиений бинарных множеств, модели PRPG.

4.5. Основные результаты главы 4.

Глава 5. Модели и методы структурного синтеза устройств стохастической генерации дескрипторов формата.

5.1. Вероятностные комбинаторные генераторы.

5.2. Устройство последовательного стохастического формирования дескрипторов формата SPRG.

5.3. Синхронный стохастический формирователь перестановок, модель SSPRG.

5.4. Вероятностные генераторы неупорядоченных г-выборок с быстрым ростом энтропии и равномерным распределением.

5.5. Стохастический формирователь упорядоченных разбиений конечных множеств MRPG.

5.6. Структурный синтез вероятностных формирователей классов сопряженных перестановок.

5.7. Использование генераторов динамического хаоса в подсистеме стохастического формирования дескрипторов формата.

5.8. Цифровой формирователь случайных чисел и временных интервалов.

5.9. Цифровой формирователь случайных чисел на базе сдвиговых регистров.

5.10. Квазишумовые режимы задающего генератора формирователя случайных чисел на базе отображения Аносова.

5.11. Встроенные средства контроля режимов функционирования генераторов случайных сигналов.

5.12. Сравнительный анализ устройств формирования и способов представления дескрипторов формата.

5.13. Основные результаты главы 5.

Глава 6. Структура и функциональность компонентов комплекса средств, реализующих динамическое форматирование данных в вычислительной технике.

6.1. Инфраструктура средств осуществления динамического форматирования данных в вычислительной технике.

6.2. Универсальный модуль манипуляции битами данных в микропроцессорах.

6.3. Модуль защиты файлов изображений от несанкционированного копирования.

6.4. Исследование производительности модели формирователя перестановок ОКРМ64.

6.5. Оценка эффективности использования специальных команд преобразования форматов данных в вычислительной технике.

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

Введение диссертации (часть автореферата) на тему «Комбинаторные устройства формирования изоморфных представлений данных, повышающие производительность вычислительной техники»

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

С расширением области применения средств вычислительной техники все чаще возникают задачи, связанные с формированием изоморфных представлений или битовых перестановок машинного слова. В число таких задач входят обработка морфологии изображений, сортировка, моделирование и тестирование цифровых устройств, задачи биоинформатики, расчет контрольных сумм и коррекция ошибок, стеганография, сжатие и развертывание информации, выполнение криптографических примитивов, обработка сигналов в системах RPMA {random permutation-based multiple access) для передачи данных с использованием технологий расширения спектра, преобразование данных для передачи в текстовом формате и т.п. При этом затраты машинного времени на битовые преобразования данных составляют от 30 до 90% времени выполнения задач.

Битовые перестановки сложны для программной реализации. Каждый бит должен быть извлечен из исходного регистра, перемещен на новое место в регистре назначения и объединен с ранее перестановленными битами. Это требует 4 инструкций на бит (генерация маски, И, Сдвиг, ИЛИ), и 4п инструкций для выполнения произвольной перестановки п битов. В связи с этим в последние годы проводятся интенсивные исследования в области разработки устройств, ускоряющих обработку битов данных.

В работах R.B. Lee, Y. Hilewitz, Z. Shi, H. Liao, Z. Wu, Y. Xiao, G. Dimitrakopoulos, C. Mavrokefalidis и др. для ускорения осуществления битовых перестановок предлагается расширение архитектуры процессоров. В основе ряда предлагаемых решений лежат многоуровневые коммутационные сети, теория которых была заложена в работах Клоза, Бенеша и развита в работах ряда авторов: М. Н. Ackroyd, D. P. Agrawal, D. G. Cantor, F. К. Hwang, С. P. Kruskal и др. Для ускорения битовых перестановок R.B. 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).

В работах В. М. Курейчика, В. М. Глушань, JI. И. Щербакова, Г.С. Цирамуа, В.А. Богатырева, В.М. Полищука, В.И. Чабана, Р.В. Дмитришина и др. исследуются детерминированные и вероятностные формирователи перестановок, сочетаний и размещений. Однако предлагаемые устройства являются специализированными, их аппаратурная сложность составляет 0(п2) и быстро растет с увеличением п, где п - длина формируемого блока данных.

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

В связи с вышеизложенным в вычислительной технике является актуальной научно-техническая проблема разработки универсальных устройств для ускорения выполнения процедур преобразования форматов представления данных.

Тематика диссертационной работы соответствует научной программе кафедры общей физики Саратовского государственного университета им. Н.Г. Чернышевского и кафедры систем автоматизированного проектирования и информационных систем Воронежского государственного технического университета.

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

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

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

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

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

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

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

Объект исследования: устройства вычислительной техники для преобразования форматов представления и манипуляций с битами данных.

Предмет исследования: структурный синтез, модели детерминированных и вероятностных устройств формирования и преобразования форматов данных.

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

Научная новизна работы: 1. На основе предложенных базовых преобразований, включающих упорядоченные и неупорядоченные разбиения блока данных длиной п, обоснованы принципы создания и разработаны алгоритмы структурного и синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных. Показано, что при использовании разработанных устройств вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

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

- параллельного формирования упорядоченных и неупорядоченных разбиений блоков данных длиной п=2к на т кластеров по 2" элементов с q = 2 log2 (п)-и-1 уровнями преобразования и аппаратурной сложностью не более чем п • (log2(п) -и/2-1) +1 логических элементов матрицы формирователя, где ^-положительное целое число, а

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

- параллельного формирования перестановок с заданной структурой циклов, аппаратурной сложностью О (log2 (ft)) и числом уровней преобразования q = 41о^(я);

- параллельного формирования прямых и обратных преобразований упорядоченных разбиений блоков данных длиной п=2к на т кластеров по 2" элементов в классе матричных устройств с аппаратурной сложностью О(п2);

- перечисления упорядоченных разбиений множества чисел (0,1,2,1) на блоки по 2й элементов, выполненных на базе матриц, формирующих упорядоченные разбиения входных данных длиной п, п!2, «/4, ., 2"+1 на два подмножества.

3. Обоснованы теоретические положения, включающие теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями, о декодировании битов управления, обеспечивающие создание универсального устройства преобразования форматов данных, выполняющего две новые инструкции bsn и grpm. Доказано, что разработанное устройство характеризуется более высокой скоростью выполнения и простотой аппаратурной реализации по сравнению с существующими решениями. На основании проведенных исследований разработаны варианты структурно-функциональной организации модулей, осуществляющих инструкции bsn, grpm, grp,pex.v,pdep.v,pex,pdep, rotate, shift.

4. Разработаны и обоснованы принципы построения высокопроизводительных вероятностных формирователей упорядоченных разбиений блоков данных длиной п с произвольной и заданной структурой циклов, характеризующиеся равномерным распределением вероятностей формируемых последовательностей. Разработанные вероятностные формирователи выполнены на базе предложенных устройств, осуществляющих упорядоченные и неупорядоченные разбиения. Доказано, что информационная энтропия вероятностного распределения выходных данных достигает значения более 50% от максимального за время, определяемое задержкой используемого формирователя, что обеспечивает увеличение производительности вычислительного устройства в п раз по сравнению с его производительностью при реализации алгоритмов Фишера-Иетса {Fisher-Yates) или Саттоло (Sattolo).

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

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

Практическая значимость работы заключается в повышении производительности технической базы средств вычислительной техники за счет использования разработанных устройств при решении задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики; расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате и других задач, связанных с манипуляцией битами данных.

В диссертации показано, что общий вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз. Использование разработанных детерминированных и вероятностных формирователей упорядоченных разбиений блоков данных длиной п обеспечивает увеличение производительности вычислительного устройства примерно в п раз по сравнению с его производительностью при реализации алгоритмов Фишера-Йетса (.Fisher-Yates), Саттоло (Sattolo).

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

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

Реализация и внедрение результатов работы.

Результаты работы внедрены в ОАО «Тантал», г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от нелицензионного копирования.

Материалы диссертации были использованы при разработке устройств высокоскоростного преобразования форматов данных, разработанных в НИР «Исследование нелинейных физических процессов в сложных системах, включая наноструктуры», шифр «Синдикат - 3», проводимой в ОМФ НИИЕН по заданию Федерального агентства по образованию.

Научно-методические результаты, полученные в диссертационной работе, внедрены в учебный процесс кафедры «Общая физика» Саратовского государственного университета и использованы при проведении занятий по дисциплинам «Моделирование полупроводниковых приборов и устройств на их основе» и «Технические средства защиты информации», в дипломном проектировании, при подготовке магистерских и двух кандидатских диссертаций. Материалы диссертации были использованы в учебно-методическом пособии «Имитационные модели физических систем с дискретным временем» (Изд-во Сарат. ун-та, 2009. ISBN 978-5-292-03916-7, 56 е.), в котором рассматриваются вопросы имитационного моделирования матричных преобразователей форматов данных.

Внедрения подтверждены соответствующими актами.

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

По результатам работы в ФГУ ФИПС зарегистрированы 3 программы, получены 12 патентов РФ на изобретения.

Основные положения и результаты, выносимые на защиту:

1. Теоретические положения, обеспечивающие структурный синтез устройств параллельного формирования разбиений входных данных и устройства для перечисления упорядоченных разбиений строки чисел (0,1,2,.,п-1) на блоки по 2й элементов.

2. Универсальное устройство преобразования форматов данных на базе многоуровневой коммутационной сети baseline обеспечивает произвольное преобразование форматов данных с использованием двух инструкций Ьбп и выполнение специализированных инструкций манипуляций с битами данных рт, ^р, рех. v, рйер.у, рех, рс1ер, инструкций логического и циклического сдвига данных.

3. Перестановки данных с произвольной или заданной структурой циклов, формируемые разработанными вероятностными формирователями, имеют равномерное распределение вероятностей и обеспечивают значение информационной энтропии вероятностного распределения выходных данных более 50% от максимального за время, определяемое задержкой используемого формирователя.

4. Формирователь импульсов случайной длительности и случайных бинарных кодов состоит только из цифровых элементов и при соотношениях частот задающих генераторов /п/п/гх/и^, удовлетворяющих выражениям

8(/п + /22) > 2-—\---3:— = ~ 5 имеет равномерную функцию распределения

У11/22 /и/22 /2/21 • вероятностей формируемых бинарных последовательностей и описывается двухмерным дискретным отображением с хаотической динамикой в прямом и обратном времени.

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

6. Разработанные 64-разрядные устройства преобразования форматов данных имеют время преобразования от 12?3 до З0г3, где ^ - максимальная задержка сигнала на одном инверторе, нагруженном на четыре входа, что обеспечивает увеличение производительности вычислительной системы от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах КРМА, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50), Саратов, 2009, Международных симпозиумах «Надежность и качество», Пенза 2006, 2007, Всероссийской научно-практической конференции «Проблемы защиты информации ограниченного доступа от утечки по техническим каналам» Саратов, РАЦ «Тантал», 2003 г., Международной технической конференции «Перспективы развития электроники и вакуумной техники на период 1001-2006 гг.» ГШ ill «Контакт», Саратов, 2001, научно-технической конференции «Электронные приборы и устройства СВЧ», Саратов, 2001, Международной научно-технической конференции «Физика и технические приложения волновых процессов», Самара, 2001.

Основное содержание работы изложено в 22 публикациях в изданиях, рекомендованных ВАК РФ, а также в трудах международных конференций, симпозиумов, регистрации 3 программ для ЭВМ в реестре ФИПС. Оригинальность технических решений защищена 12 патентами РФ на изобретения. Всего по материалам диссертации опубликовано 57 работ.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Сотов, Леонид Сергеевич

5.13. Основные результаты главы 5

В данной главе предложены эффективные стохастические формирователи упорядоченных разбиений и сочетаний исходных множеств. Высокая производительность достигается благодаря использованию специальных топологий многоуровневых коммутационных сетей (ШЫ).

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

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

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

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

Глава 6. Структура и функциональность компонентов комплекса средств, реализующих динамическое форматирование данных в вычислительной технике

6.1. Инфраструктура средств осуществления динамического форматирования данных в вычислительной технике

При проведении исследований были разработано семейство высокопроизводительных компонентов устройств преобразования форматов данных, инфраструктура которых представлена на рис. 100.

Устройства осуществления базовых преобразований

Формирователи дескрипторов формата

Последовательн ого действия

Матричные параллельного действия

Модель ВСТА

Вероятностные (стохастические)

Комбинаторные (детерминирован ные)

На базе различных топологий М1И Модели семейства ВСТАМ.

На базе сортирующих сетей Модель ВСТАБ

Модель ВСТАК с конвейерной обработкой

Последовате льного действия Модель

БЯРв

Матричные параллельного действия

Безопасные генераторы случайных сигналов Модели ОйА, СО

Перечисл

Матричные Псевдосл ение и параллельного учайные стох действия Модель рассеяние

Модель МКРв РЯРв Модель

Рис. 100. Компоненты устройств преобразования форматов данных в вычислительной технике

Далее будут рассмотрены устройства преобразования форматов представления данных, выполненные на базе компонентов, представленных на рис. 100.

6.2. Универсальный модуль манипуляции битами данных в микропроцессорах

Существует много важных приложений, таких как криптография, обработка изображений, кодирование, распознавание образов, проектирование аппаратуры, моделирование и др., где манипуляции с битами данных занимают значительную часть общего объёма вычислений. При этом можно выделить несколько команд, выполнение которых требуется особенно часто: это команда извлечения группы бит данных pex{parallel extract), команда размещения битов в заданных позициях машинного слова pdep {parallel deposit), команда осуществления произвольной перестановки битов машинного слова и команды логического и циклического сдвигов битов машинного слова. Логический и циклический сдвиги могут осуществлять большинство микропроцессоров. Но этого не достаточно для обеспечения высокопроизводительной обработки на битовом уровне.

В работе [225] был предложен способ структурного синтеза устройств разбиения строки входных данных для реализации инструкций группировки grp (group), выборки рех (parallel extract), размещения pdep (parallel deposit).

Показано, что используя предложенный подход построения универсального устройства для манипуляций с битами данных, можно осуществить инструкции логического и циклического сдвига данных. Проблемой, возникающей при разработке устройства, выполняющего команду grp, является достаточно высокая аппаратурная сложность блока декодирования битов управления переключателями. Аналогичная проблема возникает и при других подходах к разработке устройства, основанных, например, на использовании многоуровневой коммутационной сети butterfly [46]. В работе [226] показано, что при осуществлении логических и циклических сдвигов битов данных на базе обратной топологии сети butterfly удается существенно упростить декодер бит управления и увеличить его быстродействие. При этом для построения универсального модуля манипуляции битами требуется две сети butterfly и /butterfly, реализующие прямые и обратные преобразования.

В данном разделе описывается разработанный универсальный модуль выполнения манипуляций с битами данных в микропроцессорах на базе только одной структуры baseline.

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

С\,\-Сп!2,к

Рис. 101. Структурно-функциональная схема модуля осуществления инструкций манипуляции битами данных

ЗАКЛЮЧЕНИЕ

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

При проведении исследований получены следующие научные и практические результаты:

1. На основе сформулированных в диссертации положений использования упорядоченных разбиений в качестве базовых преобразований входных данных разработана и обоснована структура комплекса новых детерминированных и вероятностных устройств формирования изоморфных представлений данных. Доказано, что использование разработанных устройств приводит к увеличению производительности вычислительной системы на базе 64 разрядного процессора от 2 до 10 раз для задач сортировки, распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шумов на изображениях, операций преобразования представлений генетических последовательностей в биоинформатике, обработки данных в системах КРМА, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.

2. Разработаны теоретические положения, обеспечивающие структурный синтез и принципы функционирования устройств, формирующих упорядоченные разбиения входных слов данных длиной п на подмножества с произвольной и заданной структурой циклов. На базе многоуровневых коммутационных и сортирующих сетей и матричных коммутаторов предложены устройства, имеющие аппаратурную сложность О(п), 0(nlog2n), 0(«(log2«)2), О(п2). Проведена сравнительная оценка их производительности и разработаны рекомендации к применению.

3. Разработанные положения структурного синтеза формирователей упорядоченных разбиений и блоков управления ими обеспечили создание универсального устройства для поддержки новых инструкций bsn и grpm, осуществляющих динамическое и статическое преобразования форматов данных. Показана эффективность предложенного решения для осуществления манипуляций с битами и подсловами данных, реализуемых с использованием специализированных инструкций, таких как рех.v, pdep.v, рех, pdep, shift, rotate. Проведенный сравнительный анализ свидетельствует о том, что предложенное устройство в настоящее время является наиболее эффективным с точки зрения производительности и простоты аппаратурной реализации.

4. Разработаны и обоснованы принципы построения и модели детерминированных и вероятностных устройств, формирующих упорядоченные разбиения данных длиной п с произвольной и заданной цикловой структурой. Проведенные оценки показали, что предложенные устройства увеличивают производительность формирования перестановок с произвольной и заданной цикловой структурой примерно в п раз по сравнению с производительностью системы при реализации алгоритмов Фишера-Иетса (Fisher-Yates) и Саттоло (Sattolo).

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

6. Для контроля режимов функционирования формирователей случайных сигналов на базе систем с хаотической динамикой впервые предложено использовать анализ периодов возвратов Пуанкаре. Разработаны и исследованы устройства встроенного контроля генераторов с хаотической динамикой.

7. Разработанные IP блоки, методики расчета и синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных в ЭВМ внедрены в ОАО «Тантал», г. Саратов, при разработке процессора с ускоренной обработкой бит данных, вероятностных матричных комбинаторных формирователей для автоматизированной системы дистанционного опроса датчиков и системы защиты файлов изображений и видео от не лицензионного копирования. Научные основы создания, принципы функционирования, математические и имитационные модели комбинаторных устройств формирования изоморфных представлений данных в ЭВМ внедрены при организации обучения специалистов студентов ГОУ ВПО «Саратовский государственный университет им. Н.Г. Чернышевского». По результатам работы в ФГУ ФИПС зарегистрированы 3 программы и получены 12 патентов РФ на изобретения.

Список литературы диссертационного исследования доктор технических наук Сотов, Леонид Сергеевич, 2011 год

1. Шапиро Л., Стокман Дж. Компьютерное зрение, изд. М.: БИНОМ. Лаборатория знаний, 2006. 752 с.

2. Shi Z., Lee R.B.Subword Sorting with Versatile Permutation Instructions // Proceedings of the International Conference on Computer Design, 2002. P. 234-241.

3. Hilewitz Y., Lee R.B. Fast Bit Gather, Bit Scatter and Bit Permutation Instructions for Commodity Microprocessors // Journal of Signal Processing Systems, 2008. Vol. 53, № 1-2. P. 145-169.

4. The Mathworks, Inc., Image processing toolbox user's guide. URL: http://www.mathworks.com/help/pdfdoc/images/imagestb.pdf (дата последнего обращения 24.01.2011).

5. Hilewitz Y. Advanced bit manipulation instructions: architecture, implementation and applications // A dissertation presented to the faculty of princeton university in candidacy for the degree of doctor of philosophy. 2008. 161 p.

6. Lee R. Accelerating Multimedia with Enhanced Micro-processors // IEEE Micro, 1995. Vol. 15, № 2. P. 22-32.

7. Paver N., Aldrich B, Khan M. ITT-L4.3: INTEL® WIRELESS MMX(TM) TECHNOLOGY: A 64-BIT SIMD. II 305. Architecture for Mobile Multimedia // IEEE International Conference on Acoustics, Speech, and Signal Processing -ICASSP, 2003. Vol. II. P. 305-308.

8. Материал из Википедии: UUE http://ru.wikipedia.org/wiki/UUE (дата последнего обращения 24.01.2011).

9. UUE кодирование, http://algolist.manual.ru/compress/standard/uue.php (дата последнего обращения 21.01.2011).

10. Rivest R.L. The RC5 encryption algorithm // Fast Software Encryption: Second International Workshop, Lecture Notes in Computer Science, 1994. Vol. 1008. P. 86-96.

11. Lacaze В., Roviras D. Effect of random permutations applied to random sequences and related applications // Signal Processing Journal, 2002. Vol. 82. P. 821-831.

12. Coulon M., Roviras D. Adaptive Joint Detection for a Random Permutation-Based Multiple-Access System on Unknown Time-Varying Frequency-Selective Channels // 14th European Signal Processing Conference (EUSIPCO 2006), Florence, Italy. 2006.

13. Pat. 7281188 US, H03M 13/00 (20060101). Method and system for detecting and correcting data errors using data permutations.

14. Henry S.,Warren Jr. Hacker's Delight // Addison-Wesley Professional, 2002. 320 c.

15. Moldovyan A.N., Moldovyan A.A., Eremeev M.A., Sklavos N. New Class of Cryptographic Primitives and Cipher Design for Networks Security // International Journal of Network Security, 2006. Mar. Vol. 2. № 2. P. 114-125.

16. Sklavos N. et al. Encryption and data dependent permutations: implementation cost and performance evaluation // Proceedings of the International Workshop. Springer-Verlag. 2003. LCNS 2776. P. 337-348.

17. Goots N.D., Izotov B.V., Moldovyan A.A., Moldovyan A.N. Fast Ciphers for Cheap Hardware: Differential Analysis of SPECTR-H64, Springer-Verlag LNCS 2776 (2003) P. 449-452.

18. Гуц Н.Д., Молдовян A.A., Молдовян H.A. Построение управляемых блоков перестановок с заданными свойствами // Вопросы защиты информации. 1999. N.4. С.39-49.

19. Молдовян H.A., Молдовян A.A., Алексеев JI.E., Молдовян H.A., Молдовян A.A., Алексеев JI.E. Перспективы разработки скоростных шифров на основе управляемых перестановок // Вопросы защиты информации, 1999, № 1, С. 41-47.

20. Chen H.C., Guo J.I., Huang L.C., Yen J.C. Design and realization of a new signal security system for multimedia data transmission//Applied Signal Processing. 2003. №13. P.1291-1305.

21. Uehara Т., Safavi-Naini R., Ogunbona P. Securing wavelet compression with random permutations // IEEE Pacific-Rim Conference on Multimedia (IEEE-PCM'2000). 2000. P. 332-335.

22. Zeng W., Lei S. Efficient frequency domain selective scrambling of digital video // IEEE Trans. Multimedia 2003. 5(1). P. 118-129.

23. Mao Y., Wu M. A joint signal processing and cryptographic approach to multimedia encryption // IEEE Trans. Image Processing 2006. 15(7). P. 2061-2075.

24. Socek D. Permutation-based transformations for digital multimedia encryption and steganography / Ph.D. dissertation, Department of Computer Science and Engineering, Florida Atlantic University, 2006. 148 p.

25. Brown L. Comparing the security of pay-TV systems for use in Australia // Australian Telecommunication Research. 1990. Vol. 24. № 2 P. 1-8.

26. Сотов JI.C. Концепция ГС2?-платформы для распределенных информационно вычислительных систем специального назначения / JI.C. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 3. С.66-72.

27. Сотов JI.C. О формировании доверенной среды серверных систем управления базами данных / Ж.А. Молодченко, JI.C. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. 2008. .№3. С.23-27.

28. Сотов JI.C. Модуль генерации форматирующих сред в распределенных реляционных СУБД/ Ж.А. Молодченко, JI.C. Сотов, В. Н.

29. Харин // Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО Том 1/Под ред.Н.К.Юркова Пенза: Изд-во Пенз.гос.ун-та, 2006. С. 179-182.

30. Armonk N.Y. AltiVec Extensions to PowerPC" Instruction Set Architecture Specification// Motorola Corporation, May 1998. 114 p.

31. Intel Corporation, Intel 64 and IA-32 Architectures Software Developer's Manual, 2008. Vol. 1-2. 143 p.

32. Intel Corporation, Intel Itanium Architecture Software Developer's Manual, 2006. Vol. 1-3, Rev. 2.2. 210 p.

33. Lee R.B., Shi Z., Yang X. Efficient Permutation Instructions for Fast Software Cryptography//IEEE Micro, 2001. Vol. 21, № 6. P. 56-69.

34. Shi Z., Lee R.B. Bit Permutation Instructions for Accelerating Software Cryptography // Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP 2000), 2000. P. 138-148.

35. Lee R. Precision Architecture // IEEE Computer. 1989. Vol. 22, № 1, P. 78-91.

36. Lee R. Subword Parallelism in MAX-2// IEEE Micro, 1996. Vol. 16. № 4, P. 51-59.

37. IA-64 Application Developer's Architecture Guide // Intel Corporation, May 1999. 130 p.

38. Shi Z., Yang X., Lee R.B. Arbitrary bit permutations in one or two cycles. Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP), 2003. P. 237-247.

39. Lee R.B., Yang X., Shi Z.J. Single-cycle bit permutations with MOMR execution. Journal of Computer Science and Technology, 2005. 20(5). P. 577-585.

40. Benes V.E. Mathematical Theory of Connecting Networks and Telephone Trafic. N.Y. Academic Press, 1965. 333 p.

41. Lee C.Y., Oruc A.Y. Fast Parallel Algorithm for Routing Unicast Assignments in Benes Networks // IEEE Transactions On Parallel And Distributed Systems. March 1995. Vol. 6., № 3. P. 329-334.

42. Pat. 6.922.472 US, МПК 380/37 Method and system for performing permutations using permutation instructions based on butterfly networks.

43. Giorgos Dimitrakopoulos, Christos Mavrokefalidis, Sorter Based Permutation Units for Media-Enhanced Microprocessors//IEEE transactions on very large scale integration (VLSI) systems, 2007. Vol. 15, № 6. P. 711-715.

44. Hilewitz Y., Shi Z.J., Lee R.B. Comparing Fast Implementations of Bit Permutation Instruction // Proceedings of the 38th Annual Asilomar Conference on Signals, Systems, and Computers, 2004. P. 1856-1863.

45. Советов Б. Я., В. В. Цехановский, Чертовский В. Д. Базы данных. Теория и практика. М : Высшая школа, 2005. 464 с.

46. Васюкевич В. О. Элементы асинхронной логики. Венъюнкция и секвенция / 2009. 123с. URL: http://asynlog.balticom.lv/Content/Files/ru.pdf. (дата последнего обращения 24.01.2011)

47. Молодченко Ж. А., Сотов Л.С., Харин В. Н. Стохастическое кластерное моделирование картезиана двудольного графа в рамках наложенных ограничений Воронеж, гос. лесотехн. акад. Воронеж, 2006. 10 с: 3 ил., Библиог. 5 назв. Рус- Деп. в ВИНИТИ.

48. Abramowitz М., Stegun I.A. Handbook of Mathematical Functions. US Department of Commerce, National Bureau of Stanards. 1970. 430 p.

49. Носов В.А. Комбинаторика и теория графов. М.:МГУ. 1999.112 С.

50. Czumaj A., Kanarek P., Kutylowski М., Lorys К. Fast Generation of Random Permutations Via Networks Simulation // Algorithmica. 1998. V.21. № 1. P.2-20.

51. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т.7. №10. С.78-85.

52. Сотов Л.С. Математические модели транспозиционных преобразований / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2007. Т5. №12. С. 58-60.

53. Риордан Дж. Введение в комбинаторный анализ. М.: Изд-во иностранной литературы, 1963. 289 с.

54. Стенли Р. Перечислительная комбинаторика: Пер. с англ. М. Мир. 1990. 440 с.

55. IEEE Standard SystemC® Language Reference Manual Version 2.2 ISBN 0-7381-4871-7 SH95505.

56. Hawang F.K., Hwang F. The Mathematical Theory of Nonblocking Switching Networks. NJ.: World Scientific Publishing Company, 2004. 200 p.

57. Сотов JI. С. Комбинаторная модель функционального формирователя разбиений бинарного множества // Информационные технологии. 2010. №10. С. 46-52.

58. US № 6,952,478, МПК 380/37 Method and system for performing permutations using permutation instructions based on modified omega and flip stages/ Lee; Ruby B. (Princeton, NJ), Yang; Xiao (Princeton, NJ). October 4, 2005 Appl.No.: 09/850,238.

59. Сотов Л.С., Соболев C.C., Харин B.H. Кросс кластерная коммутационная матрица для аппаратной поддержки управляемойперестановки данных в криптографических системах // Проблемы информационной безопасности. Компьютерные системы. 2009. №4. С. 56-63.

60. Сотов Л.С., Солопов А.А., Фарафонова А. Модель инволютивного транспозиционного преобразователя // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.38-48.

61. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т.7. №10. С.78-85.

62. Сотов Л.С. Модели устройств кросс-кластерных перестановок данных в ЭВМ / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Вестник компьютерных и информационных технологий. 2009. №12. С.51-55.

63. Pat. 5175539 US, 340/2.21 Interconnecting network. / Richter; Harald.-December 29, 1992.

64. Сотов Л.С. Простой матричный формирователь г-выборок / А.В. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.47-56.

65. Pat. US 6381690 G06F 7/76 (20060101); 712/223 ; Processor for performing subword permutations and combinations/Lee; Ruby B. April 30, 2002 . T. Appl. No.: 08/509,867 Filed: August 1, 1995.

66. Hilewitz Y., Lee R. A. New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations // IEEE Transactions on Computing. 2009. Vol. 58, № 8. P. 1035-1048.

67. Shi Z.J., Lee R.B. Implementation Complexity of Bit Permutation Instructions/Proceedings of the 37th Annual Asilomar Conference on Signals, Systems, and Computers, 2003. P.879-886.

68. Hilewitz Y., Shi Z. J., Lee R. B. Comparing Fast Implementations of Bit Permutation Instruction // Proceedings of the 38th Annual Asilomar Conference on Signals, Systems,and Computers. Pacific Grove, California, USA, Nov. 7-10, 2004. P.1856-1863.

69. Batcher К. E. Sorting Networks and Their Applications.// Proceedings of 1968 Spring Joint Computer Conference, pp. 307-314, 1968.

70. Pat/ US 5319788 G06F 7/22 (20060101); 712/300 ; Modified batcher network for sorting N unsorted input signals in log.sub.2 N sequential passes/Canfield; Earl R., Williamson; Stanley G. June 7, 1994 . T. Appl. No.:07/677,222 Filed:March 29, 1991.

71. Алексеев JI. Е., Белкин Т. Г., Гуц Н. Д., Изотов Б. В. Управляемые операции: повышение стойкости к дифференциальному криптоанализу// Безопасность информационных технологий. 2000. № 2. С. 81-82.

72. Белкин Т.Г., Гуц Н.Д., Молдовян А.А. Молдовян Н.А. Способ скоростного шифрования на базе управляемых операций. Управляющие системы и машины. 1999. №б. С. 78-87.

73. Молдовян А. А., Молдовян Н. А. Скоростные шифры на базе нового криптографического примитива // Безопасность информационных технологий. 1999. № 1. С. 82-88.

74. Монахов, В. С. Введение в теорию конечных групп и их классов : учеб. пособие для физико-математических спец. вузов / В. С. Монахов. Мн. : Вышэйшая школа, 2006. - 207 с.

75. Naor M.,Reingold О. Constructing Pseudo-Random Permutations with a Prescribed Structure//Journal of Cryptology. 2002. №15. P.97-102.

76. Tsaban В. Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation.//Journal of Algorithms,V.47. Issue 2. July 2003. P.104-121.

77. Clos C. A study of nonblocking switching networks // Bell System Technical Journal, Vol 32, 1953, S.406-424.

78. Сотов JI.С., Хвалин A.JI. Средства разработки и исследования архитектурных моделей в САПР System Studio. Часть 2. Основные объекты SystemC и их использование // Гетеромагнитная микроэлектроника, 2008. Вып. 5. С.121-146.

79. Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. 5-е изд. СПб.: Питер; Киев: Изд. группа BHV, 2003. С. 668-675.

80. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М., 1990. 216 с.

81. Бассалыго Л. А., Пинскер М. С. О сложности оптимальной неблокирующей коммутационной схемы без перестроения.//Пробл. передачи информ., 1973, 9:1, 84-87.

82. Enrique С.А., Gregory W. D. A Comparison of Circuits for On-Chip Programmable Crossbar Switches//10th NASA Symposium on VLSI Design, Albuquerque, NM, March 20-21, 2002. .

83. Martel C. , Nguyen V. Designing networks for low weight, small routing diameter and low congestion// in: 25th Conference of the IEEE Communications Society, INFOCOM, 2006.

84. Hamza, Haitham S. Optimizing complexity in Benes-type WDM switching networks.//Photonic Network Communication vol.17 no.3.-2009.-Page 277 291.

85. A. c. 643883 СССР, G06F 15/20. Устройство для перебора сочетаний, размещений и перестановок/Г. Я Левин. — Опубл. 1979, Бюл. № 10.

86. А. с. 957215 СССР, МКИЗ G06F 15/20. Устройство для перебора перестановок/Г А. Ерошко, Н. Н. Шубина. —Опубл. 1982, Бюл. № 33.

87. А. с. 1383381 СССР, МКИЗ G06F 15/20. Устройство для перебора перест новок/В. М. Глушань, И. Г. Ефремов, М. И. Пупков. — Опубл. \1989.-Бюл. №11.

88. А. с. 1124319 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний и перестановок/В. М. Глушань и др. — Опубл. 1984, Бюл № 42.

89. А. с. 1190388 СССР, МКИЗ G06F 15/20. Устройство для перебора пер становок/В. М. Глушань и др.— Опубл. 1985, Бюл. № 41.

90. А. с. 1397933 СССР, МКИЗ G06F 15/20. Устройство для перебора перест новок/В. М. Глушань и др.—Опубл. 1988, Бюл. № 19.

91. А. с. 1397933 СССР, МКИЗ G06F 15/20. Устройство для перебора перест новок/В. М. Глушань и др.—Опубл. 1988, Бюл. № 19.

92. А. с. 995093 СССР, МКИЗ GOGF 15/20. Устройство для перебора перест новок/Н И. Крылов — Опубл. 1983, Бюл. № 5.

93. А. с. 1513467 СССР, МКИЗ G06F15/20. Функциональный генератор п рестановок/В. М. Глушань, И. Г. Ефремов, С. Ю. Ермаков. — Опубл. 1987 Бюл. №37.

94. Рейнгольд. Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ./Под ред. В.Б. Алексеева.-М.: Мир, 1980.-476 С.

95. Глушань В. М., Пупков М. И., Щербаков Л. И. Алгоритмы формирования упорядоченных г-выборок//Кибернетика. 1988. № 1. С. 129—131.

96. Тимошевская Н.Е. О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования управляющих систем // Известия Томского политехнического университета, 2004. Т.307. №6. С. 18-20.

97. Portz М., Aachen R. On the Use of Interconnection Networks in Cryptography ./Springer, D.W. Davies (Ed.): Advances in Cryptology EUROCRYPT '91, LNCS 547, pp. 302-315, 1991.

98. William J.D., Brian T. Principles and practices of interconnection networks/Morgan Kaufmann Publishers Inc. San Francisco, CA, USA- 2003.- 550 p.

99. CEES J.A. JANSEN . On the Construction of Run Permuted Sequences/Springer, Damgard I.B. (Ed.): Advances in Cryptology EUROCRYPT '90, LNCS 473, pp. 196-203, 1991.

100. Reif J. H. An optimal parallel algorithm for integer sorting./ In 26th Symposium on Foundations of Computer Science, 1985.-P. 496-503.

101. Alonso L., Schott R. A parallel algorithm for the generation of permutation and applications// Theoretical Computer Science. 1996. 159(1). P.15-28.

102. Anderson R. Parallel algorithms for generating random permutations on a shared memory machine./ In Proc. SPAA'90. 1990. P. 95-102.

103. Lassous I.Guerin, Thierry E. Generating Random Permutations in the Framework of Parallel Coarse Grained Models./Rapport de recherche, N 3896.- Mars 2000.-P.1-14.

104. Dehne F., Fabri A., and Rau-Chaplin A. Scalable parallel computational geometry for coarse grained multicomputers.// International Journal on Computational Geometry, Vol. 6(No. 3):pp. 379-400, 1996.

105. Valiant L. A bridging model for parallel computation. Communications of the ACM, Vol.33(8):103-lll, 1990.

106. Молодченко Ж.А., Сотов JI.C., Харин B.H. Архитектура генераторов комбинаторных дескрипторов формата // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2009. Вып. 6. С. 108-119.

107. Молодченко Ж.А., Сотов Л.С., Харин В.Н. Моделирование архитектуры акселератора битовых перестановок с использованием САПР SYSTEM STUDIO фирмы SYNOPSYS.// «Гетеромагнитная микроэлектроника». Саратов: Изд-во Сарат. ун-та. 2008. - Вып.З. С. 60 - 66.

108. А. с. 525948 СССР, МКИЗ G06F7/00. Устройство для перебора сочетаний/ В. В. Епихин, Опубл. 1976, Бюл. № 31.

109. А. с. 512472 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний/В. В. Епихин. — Опубл. 1976, Бюл. № 16.

110. А. с. 514295 СССР, МКИЗ G06F15/20. Устройство для перебора сочет ний /В. В. Енихин. — Опубл. 1976, Бюл. № 18.

111. А. с. 634285 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний/ Г. С. Цирамуа, В. А. Богатырев. — Опубл. 1978, Бюл. № 43.

112. А. с. 1370655 СССР, МКИЗ G06F 15/31. Устройство для перебора сочет ний/В. М. Глушань, А. В. Пришибской.— Опубл. 1988, Бюл. № 4.

113. А. с. 1397934 СССР, МКИЗ G06F 15/31. Устройство для перебора сочет ний/В. М. Глушань, А. В. Пришибской.—Опубл. 1988, Бюл. № 19.

114. А. с. 1008750 СССР, МКИЗ G06F 15/31. Устройство для перебора сочетаний/С. П. Присяжнюк и др.— Опубл. 1983, Бюл. № 12.

115. А. с. 1264195 СССР, МКИЗ G06F 15/20. Устройство для перебора сочетаний/В. М. Глушань и др. — Опубл. 1986, Бюл. № 38.

116. А. с. 1305702 СССР, МКИ2 G06F 15/20. Устройство для перебора сочетаний/В. М. Глушань, М. В. Рыбальченко. — Опубл. 1987, Бюл. № 15.

117. Майоров С. А., Новиков Г. И.@ Структура ЭВМ. 2-е изд., перераб. и д полн. —JL: Машиностроение, 1979. — 384 с.

118. Борисенко A.A., Протасова Е. А. Цифровой автомат для перебора композиций//Вюник СумДУ. Техшчш науки",№2.-2007.-С.123-126.

119. Борисенко A.A. Биномиальные автоматы./Сумы: СумГУ, 2005.-120 с.

120. А. с. 1077054 МПК Н03К23/00. Счетчик импульсов / А. А. Борисенко. И. Д. Пузько. JI. А. Стеценко. Заявка: 3479062, 27.07.1982. Опубликовано: 28.02.1984.

121. Alan Tucker. Applied Conbinatorics.NEW YORK:John Wiley & Sons, INC, Third Edition. 1995. 462 p.

122. Молодченко Ж.А., Сотов JI.C., Солопов A.A., Харин B.H. Матричные акселераторы транспозиционных преобразований форматов данных в ЭВМ //Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2009. Вып. 6. С.91-107.

123. Сотов JI.С. Алгоритм работы и модель функционального генератора перестановок / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Информационные технологии. 2010. №4. С.41-46.

124. Сотов Л.С. Модели аппаратных функциональных формирователей перестановок / Ж.А. Молодченко, Л.С. Сотов, В.Н. Харин // Информационно-измерительные и управляющие системы. 2009. Т.7. №10. С.78-85.

125. Сотов Л.С. Модели аппаратурных акселераторов перестановок бинарных множеств / Ж.А. Молодченко , C.B. Овчинников, Л.С. Сотов, В.Н. Харин // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 4. С. 11-22.

126. Amirfathi M., Holtmann U., Ramachandran L. et al. CoCentric System Studio Synthesizable SystemC RTL Code Generation. Synopsys, July. 2001. 210 p.

127. А. с. 903891 СССР, МКИЗ G06F 15/31. Устройство для перебора сочетанш /В. М. Полищук. — Опубл. 1982, Бюл. № 5.

128. А. с. 1262520 СССР, МКИЗ G06F 15/20. Устройство для перебора сочет ний/В. М. Глушань и др.— Опубл. 1986, Бюл. № 37.

129. Сотов Л.С., Хвалин А.Л. Средства разработки и исследования архитектурных моделей в САПР System Studio. Часть 2. Основные объекты SystemC и их использование // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 5. С.121-146.

130. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М., 2003. 240 с.

131. Байбурин В.А., Мантуров А.О. Перспективные методы защиты информации при её передаче по открытому каналу связи // Информационная безопасность регионов. 1(2). 2008. С.33-37.

132. Andrew С. Yao. Theory and application of trapdoor functions// In Proceedings of the 23rd IEEE Symposium on Fundation of Computer Science New York, IEEE. 1982. P. 80-91.

133. Blum M., Micali S. How to generate cryptographically strong sequences of pseudo-random bits // SIAM Journal on Computing, 1984. №13. P. 850-864.

134. Levin L. A. One-way function and pseudorandom generators // In Proceedings of the 17th ACM Symposium on Theory of Computing, New York, 1985. ACM. p. 363-365

135. Шнайер Б. Прикладная криптография // Протоколы, алгоритмы, исходные тексты на языке Си. М., 2002. 610 с.

136. Goldreich О., Goldwasser S., Micali S. How to construct random functions.// Journal of the ACM, Vol. 33, No. 4, Oct. 1986, P. 792-807.

137. Luby M., Rackoff C. "Pseudo-random permutation generators and cryptographic composition // Proceedings of the 18th ACM Symposium on the Theory of Computing, ACM, 1986, P. 356-363.

138. Luby VI. and Rackoff C. How to construct pseudorandom permutations and pseudorandom functions// SIAM J. Compute vol. 17, 1988, pp. 373-386.

139. Mauier U. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators // Abstracts of Eurocrypt '92, Balatonfiired, Hungary, 1992. P. 614-621.

140. Zheng Y., Matsumoto T. and Imai H. Impossiblility and optimally results on con-strucbng pseudorandom permutations// Abstract of EUROCRYPT'89, Houthalen, Belgium, April 1989, P. 412-421.

141. Patarin J. How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function. Springer-Verlag GmbH. Lecture Notes in Computer Science. 1993. V.658 P.256-267.

142. Patarin J. New results on pseudorandom permutation generators based on the DES Scheme// Abstracts of Crypto'91. P. 72 -77.

143. Sadeghiyan В. and Pieprzyk J. On necessary and sufficient conditions for the construction of super pseudorandom permutations // Abstracts of Asiacrypt'91, November 1991. P. 117-123.

144. Pieprzyk J. How to Construct Pseudorandom Permutations from Single Pseudorandom Functions // Abstracts of Asiacrypt'91, November 1991. P. 219-223.

145. Schnorr C.P. On the construction of random number generators and random function generators // In Proc. of Eurocrypt SSt Lecture Notes in Computer Science, Springer Verlag, New York, 1988. P. 372 -377.

146. Rueppel R.A. On the security of Schnorr's pseudo random generator // Astracts of EUROCBYPT'89, Houtkalen, Belgium, April 1989.

147. Zheng Y., Matsumoto Т., Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses //Astracts of CRYPTO'89, Santa Barbara, CA, July 1989.

148. Portz M.A. Generalised Description of DES-based and Benes-based Permutation Generators // Springer-Verlag London Lecture Notes In Computer Science. 1992. Vol. 718. P. 397-409.

149. Clos C. A study of nonblocking switching networks.// Bell System Technical Journal, 1953. Vol 32. P.406-424.

150. A. c. 1101820 СССР, МКИЗ G06F7/58. Датчик случайных последовательностей.

151. А. с. 845154 СССР, МКИЗ G06F 1/02. Генератор равномерно распределенных случайных интервалов времени.

152. А. с. 1228103 СССР, МКИЗ G06F7/58. Генератор случайных сочетаний.

153. А. с. 879755 СССР, МКИЗ НОЗк 3/84. Датчик случайных равновероятных временных интервалов.

154. А. с. 1034034 СССР, МКИЗ G06F7/58. Датчик случайных равновероятных временных интервалов.

155. Глушань В. М., Прихоженко Б. Ю., Щербаков JI. И. Способ генерирования импульсов случайной двоичной последовательности сравновероятным законом распределения интервалов // Изв. СК НЦВШ Техн. науки. 1984. №2. С. 38-41.

156. А. с. 1319027 СССР, МКИЗ G06F7/58. Генератор случайных сочетаний.

157. Пат. на изобретение RU № 2395834 С1, МПК G06F 7/58 (2006.01). Генератор случайных перестановок/Сотов JI.C., Харин В. Н., Хвалин A.JI. (Россия). № 2009104555/09; заявл. 12.02.2009; опубл. 27.07.2010. Бюл. № 21. 8 с.

158. Пат. на изобретение RU № 2340931 С1, МПК G06F 7/58 (2006.01) Н03К 3/84 (2006.01). Генератор случайных чисел /Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия), заявл. 28.03.2007; опубл. 10.12.2008, Бюл. № 34, 5 с.

159. Fisher R.A., Yates F. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. 1948. P. 26-27.

160. Durstenfeld R. Algorithm 235: Random permutation//Communications of the ACM, 1964. V.7 № 7. P.420.

161. Кнут Д.Э. Искусство программирования. Сортировка и поиск. М.-.Вильяме. 2009. Т. 3. 824 с.

162. Коростелев Г.Н., Сотов Л.С. Сложная динамика генераторов на диоде Ганна с низкочастотным контуром // Изв. вузов. Радиотехника и электроника.-1989.-1Ч9.-Т.34.-С. 1925-1929.

163. Шеннон К. Теория связи в секретных системах. М.: Изд. иностр. лит.,Сб. Работы по теории информации и кибернетике. 1963. 830 с.

164. US 6934388 В1 380/47. Method and apparatus for generating random permutations.

165. Сотов Л.С., Харин В.Н. Использование генераторов динамического хаоса в системах информационной безопасности // Проблемы информационной безопасности. Компьютерные системы. 2009. №2. С. 32-37.

166. Осипенко Г.С. и др. Построение инвариантных мер динамических систем // Дифференциальные уравнения и процессы управления. 2007. № 4. с. 27-51.

167. А. с. 1269128 СССР, МКИЗ G06F7/58. Устройство для случайного перебора перестановок.

168. Кофман А. Введение в прикладную комбинаторику. М., 1975. 480 с.

169. Ritter Т. Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner// Cryptologia. 1991. Vol. 15(1). P. 1-17.

170. Сотов JI.C. Динамическое форматирование представлений объектов реляционных СУБД на основе кластерных транспозиций/ Ж. А. Молодченко, Л.С. Сотов, В. Н. Харин //Естественные и технические науки. 2007. № 6 (32). С.224-226.

171. Соболев С.С., Сотов Л.С., Харин В.Н. Динамическое форматирование структурных объектов хранилищ данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 4. С. 28-33.

172. Гантмахер Ф.Р. Теория матриц. М., 1966. 576 с.

173. Феллер В. Введение в теорию вероятностей и ее приложения. М., 1964. Т. 1.2-е изд. 499 с.

174. Thorsten G., Stan L., Grant M., Stuart S. System Design with SystemC. -Boston; Dordrech; London, 2002. 240 p.

175. US 7583155 МПК G06F7/58 Random sequence generator.

176. US №05871400, МПК A63F9/21. Random number generator for electronic applications.

177. Пат. на изобретение RU № 2340931 CI, МПК G06F 7/58 (2006.01) H03K 3/84 (2006.01). Генератор случайных чисел / Молодченко Ж. А., Сотов Л.С., Харин В. Н. (Россия). № 2007111405/09; заявл. 28.03.2007; опубл. 10.12.2008, Бюл. № 34, 5 с.

178. Портенко Н.И., Скороход А.В., Шуренков В.М. Марковские процессы. М., 1989. 248 с.

179. Шило В.Л. Популярные цифровые микросхемы. М., 1989. С. 107110.

180. Sattolo S. An algorithm to generate a random cyclic permutation // Information Processing Letters. 1986. V. 22. P. 315-317.

181. Prodinger H. On the analysis of an algorithm to generate a random cyclic permutation // Ars Combinatoria. 2002. V. 65. P. 75-78.

182. Mahmoud H.M. Mixed distributions in sattolo's algorithm for cyclic permutations via randomization and derandomization // Journal of Applied Probability. V. 40. 2003. P. 790-796.

183. Wilson M.C. Overview of Sattolo's Algorithm // Algorithms Seminar 2002-2004. INRIA Research Report. 2005. P. 105-108.

184. Сотов JI.C. Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии / А.В. Ляшенко, Л.С. Сотов // Гетеромагнитная микроэлектроника. 2010. Вып. 8. С.57-71.

185. Сотов Л.С., Харин В.Н. Цифровой генератор подкачки энтропии на базе отображения Арнольда // Известия вузов. Прикладная нелинейная динамика. 2009. Т. 17. № 6. С.57-66.

186. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography CRC, 1997. P.39-41.

187. Фергюсон H., Шнайер Б. Практическая криптография. Пер. с англ. М.: Издательский дом "Вильяме", 2005. С. 178-209.

188. Куприянов A.M. Основы зашиты информации : учеб. пособие для студ. высш. учеб. заведений / А.И.Куприянов, А.В.Сахаров, В. А. Шевцов. М.: Издательский центр «Академия», 2006. С.48.

189. Agnew G. В. Random Sources for Cryptographic Systems// Advances in Crvptology EUROCRYPT'8 7 Proceedings. Springer-Verlag. 1988. P 77-81.

190. Fairfield R. C., Moileiison R. I., Koullhan K.B. "An VSI Random Number Generator'VAdvances in Crypiology: Proceedings of CRYPTO 84, Springer Verlag, 1985. pp. 203-230.

191. T7001 Random Number Generator. AT&T, Dala Sheet, Aug. 1986.

192. Блинов А.Л., Молодченко Ж.А., Сотов Л.С., Харин В.Н. Генераторы случайных импульсов на базе модельного отображения «сдвиг Бернулли» // Гетеромагнитная микроэлектроника. Саратов: Изд-во Сарат. ун-та, 2009. -Вып. 6. С.120-130.

193. Каток А. Б. , Хасселблат Б. Введение в современную теорию динамических систем с обзором последних достижений / пер. с англ. под ред. А.С.Городецкого. М.: МЦНМО, 2005. 464 с.

194. Кузнецов С. П. Динамический хаос. М.: ФИЗМАТЛИТ, 2001. 296 с.

195. Евтушенко Н. Д., Немудров В. Г., Сырцов И. А. Методология проектирования систем на кристалле. Основные принципы, методы, программные средства // «Электроника». 2003. №3. С.35-42.

196. Опадчий Ю. Ф., Глудкин О. П., Гуров А. И. Аналоговая и цифровая электроника. М.:«Горячая Линия — Телеком». 2000. 768 с.

197. Шустер Г. Детерминированный хаос: Введение. М.: Мир, 1988. С.115.

198. Хвалин A.JI., Овчинников C.B., Сотов JI.C., Самолданов В.Н. Первичный преобразователь на основе ЖИГ генератора для измерения сильных магнитных полей//«Датчики и системы», 2009. №10. С. 57-58.

199. Хвалин А.Л., Сотов Л.С., Овчинников C.B., Кобякин В.П. Экспериментальные исследования гибридного интегрального магнитоуправляемого генератора // Приборы и системы. Управление, контроль, диагностика, 2009. №11.

200. Хвалин А.Л., Игнатьев A.A., Сотов Л.С. Квазишумовые режимы магнитоэлектронных генераторов//Вопросы электромеханики. Том 113. №6. 2009. С.55-59.

201. Молодченко Ж. А., Сотов Л.С., Харин В. Н. Модуль генерации форматирующих сред в распределенных реляционных СУБД. Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО. Пенза:Изд-во Пенз.гос.ун-та, 2006. Том 1. С. 179-182.

202. Свидетельство об официальной регистрации программы для ЭВМ № 2004610988 (РФ). Программа расчета параметров модели Матерка полевого транзистора / Сотов Л.С. и др. Заявка № 2004610416. Зарегистрировано 21.04.2004.

203. Гуревич А.Г., Мелхов Г.А. Магнитные колебания и волны. М.: Фирма «Физ.-мат. литературы», 1994 г. С.574.

204. Свидетельство об официальной регистрации программы для ЭВМ № 2004610989 (РФ). Программа расчета параметров модели Гумеля-Пуна биполярного транзистора / Сотов JI.C. и др. Заявка № 2004610417, зарегистрировано 21.04.2004.

205. Сотов JI.C., Харин В.Н., Хвалин A.JI. Детекторы режимов функционирования генераторов случайных сигналов // Автоматика и телемеханика. 2010. №5. С. 166-170.

206. Мирский Г. Я. Электронные измерения. 4-е изд., перераб. и доп. М.: Радио и связь, 1986. С. 225.

207. Packard N. Н., Crutchfield J. P., Farmer J. D., Shaw R. S. Geometry from a time series // Phys. Rev. Lett. 1980. V. 45. P. 712-716.

208. Takens F. Detecting strange attractors in turbulence. Dynamical Systems and Turbulence / Eds D. A. Rand, L.-S. Young. Berlin: Springer, 1981. P. 366-381.

209. Sotov L.S., Kharin V.N., Khvalin A.L. Operation Mode Detectors for Random Signal Generators // Automation and Remote Control, 2010. Vol. 71. No. 5. P.876-880.

210. Сотов JI.C. Методы синтеза устройств, выполняющих инструкции перестановки битов данных // Гетеромагнитная микроэлектроника. 2011. Вып. 10. С.25-50.

211. Hilewitz Y., Lee R. A. New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations // IEEE Transactions on Computing. 2009. Vol. 58, № 8. P. 1035-1048.

212. Lee R.B., Rivest R.L., Robshaw M.J., Shi Z.J., Yin Y.L. "On Permutation Operations in Cipher Design/Proceedings of the International Conference on Information Technology (ITCC), 2004. V.2. P.569-577.

213. Shi Z. J. Bit Permutation Instructions: Architecture, Implementation and Cryptographic Properties, Phd., Princeton University, 2004.

214. OpenRISC 1000 architecture, http://opencores.org/openrisc,architecture (дата последнего обращения 21.01.2011).

215. USB Function IP Core Rev. 1.5/ Rudolf Usselmann. January. 27. 2002.

216. DDR Memory Overview, Development Cycle, and Challenges // Agilent Technologies. № 5990-3180EN, Printed in USA, December 19, 2008.

217. Брассар Ж. Современная криптология: Пер. с англ. — М., Издательско-полиграфическая фирма ПОЛИМЕД, 1999. С. 32-34.

218. Молодченко Ж. А., Сотов Л.С., Харин В. Н. К вопросу об архитектуре аналого-цифровых систем генерации случайных сигналов // Труды международного симпозиума НАДЕЖНОСТЬ И КАЧЕСТВО Пенза:Изд-во Пенз. гос. ун-та, 2007. С. 85-87.

219. Виноградов, А. С. Диодный генератор шума для радиометрической системы/ А. С. Виноградов, А. Н. Сычев // Электронные средства и системы управления. Опыт инновационного развития / Томск: В-Спектр, 2007. С.171-173.

220. Кушнир Ф.В. Электрорадиоизмерения / Энергоатомиздат. 1983. 320с.

221. Анищенко B.C., Т.Е. Вадивасова, В.В. Астахов. Нелинейная динамика хаотических и стохастических систем. Фундаментальные основы и избранные проблемы. Саратов: Изд-во Сарат. Ун-та, 1990. 368с.

222. Шеннон К. Математическая теория связи. М.: Изд. иностр. лит., Сб. Работы по теории информации и кибернетике. 1963. 830 с.

223. Нему дров В., Мартин Г. Системы на кристалле. Проектирование и развитие. М.: Техносфера, 2004. 340 с.

224. Prasun Ghosal, Malabika Biswas, Manish Biswas Hardware Implementation of TDES Crypto System with On Chip Verification in FPGA // Journal Of Telecommunications, Volume 1, Issue 1, February 2010. P. 113-117.

225. Kaps, J., Paar, C.: Fast DES implementations for FPGAs and its application to a Universal key-search machine. In: Proc. 5th Annual Workshop on selected areas in cryptography Sac' 98, Ontario, Canada, Springer-Verlag, 1998. P. 234-247.

226. McLoone, M., McCanny, J.: High-performance FPGA implementation of DES using a novel method for implementing the key schedule. IEEE Proc.: Circuits, Devices & Systems 150, 2003 P.373-378.

227. Wilcox, D., Pierson, L., Robertson, P., Witzke, E.L., Gass, K.: A DES asic suitable for network encryption at 10 Gbs and beyond. In: CHESS 99, LNCS 1717, 1999. P. 37^18.

228. Patterson, C.: High Performance DES Encryption in Virtex FPGAs using Jbits. In: Field-programmable custom computing machines, FCCM' 00, Napa Valley, CA, USA, IEEE Computer. Soc., CA, USA, 2000, 2000. P. 113-120.

229. Vishwanath P., Joshi R. C., Saxena A. K. "Fpga Implementation Of Des Using Pipelining Concept With Skew Core Key-Scheduling"//Journal of Theoretical and Applied Information Technology,March 2009,Vol. 5. No.3 P. 113-117.

230. Vikram Pasham and Steve Trimberger, "High-Speed DES and Triple DES Encryptor/Decryptor", Xilinx Application Note: Virtex-E Family and Virtex-II Series, XAPP270 (vl.0) August 03, 2001.

231. Ravi Budruk, Don Anderson, Tom Shanley PCI Express System Architecture. Addison-Wesley Professional. 2004. 1120 p.

232. Архангельский C.B. Информационный анализ цифровых сигналов. Из-во Саратовского университета, 1991. С.22-32.

233. Грушо А.А. Тимонина Е.Е. Теоретические основы защиты информации. Издательство Агентства "Яхтсмен". 1996. 245 с.1. С.

234. Wong, К., Wark, М., Dawson, Е.: A SingleChip FPGA Implementation of the Data Encryption Standard (des) Algorithm. In: IEEE Globecom Communication Conf., Sydney, Australia, 1998. 827-832.

235. URL: http://www.okbsapr.ru/akk55.html (дата обращения 15.09.2010).

236. US №7519795, МПК G06F9/30 Method and system for performing permutations with bit permutation instructions.

237. Pat. US 6952478 G06F 7/76 (20060101); 380/37 ; Method and system for performing permutations using permutation instructions based on modified omega and flip stages.

238. Жан M. Рабаи, Ананта Чандракасан, Боривож Николич. Цифровые интегральные схемы. Методология проектирования. М.:Вильямс, 2007. 912 с.