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

• Автор: Сотов, Леонид Сергеевич
• Шифр специальности: 05.13.05
• Научная степень: Докторская
• Год защиты: 2011
• Место защиты: Саратов
• Количество страниц: 374 с. : ил.

ОГЛАВЛЕНИЕ
Введение
Глава 1. Бит-ориентированные операции преобразования форматов данных в вычислительной технике
1.1. Производительность средств вычислительной техники в задачах, связанных с преобразованиями форматов данных
1.2. Использование преобразований форматов данных в системах защиты информации
1.3. Инструкции обработки битов и под с лов данных
1.4. Проблемы использования аппаратурных средств преобразования форматов данных
1.5. Основные результаты главы
Глава 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. Инволютивный матричный преобразователь ВСТА
3.11. Сравнительная оценка аппаратурной сложности преобразователей форматов данных
3.12. Основные результаты главы
Глава 4. Методы построения и модели устройств перечисления множеств дескрипторов формата
4.1. Модели и методы устройств комбинаторного формирования дескрипторов формата
4.2. Комбинаторный генератор сочетаний элементов бинарных множеств
4.3. Матричный комбинаторный генератор перестановок и упорядоченных разбиений числовых множеств PG
4.4. Исследование псевдослучайных генераторов перестановок и упорядоченных разбиений бинарных множеств, модели PRPG
4.5. Основные результаты главы
Глава 5. Модели и методы структурного синтеза устройств стохастической генерации дескрипторов формата
5.1. Вероятностные комбинаторные генераторы
5.2. Устройство последовательного стохастического
формирования дескрипторов формата SPRG
5.3. Синхронный стохастический формирователь перестановок, модель SSPRG
5.4. Вероятностные генераторы неупорядоченных г-выборок с быстрым ростом энтропии и равномерным распределением

требованием 16 килобайтов памяти для размещения таблиц. Инструкция общего назначения PERMUT в МАХ-2 может сделать любую перестановку, с повторениями или без повторений для подслов, упакованных в 64-битовый регистр [38]. Однако это возможно только для 16-битовых подслов. Инструкции MIX и MUX осуществимые с использованием архитектуры IA-64 являются расширениями инструкций MIX и PERMUTE, используемых в МАХ-2 [39]. В IA-64 используется инструкция MUX, которая является инструкцией, осуществляющей перестановку 16-битовых подслов, с пятью новыми перестанавливаемыми разновидностями байта. Инструкция VPERM, используемая в AltiVec в Power PC фирмы IBM [32], расширяет возможности инструкции PERMUT, используемой в МАХ-2. Она применяется к 8-битовым подсловам выбираемым из двух 128-битовых исходных регистров и помещаемым в единственный 128-битовый регистр назначения. Таким образом, существует 32 таких подслова, из которых выбираются 16. Это требует 16xlog232=80 бит для того, чтобы определить требуемую перестановку. Поэтому инструкция VPERM должна использовать другой 128-битовый регистр, чтобы хранить биты управления перестановкой, что делает её очень затратной инструкцией с тремя исходными регистрами и одним регистром назначения. Причём все регистры имеют разрядность 128 битов.
Наиболее перспективными являются универсальные инструкции преобразования форматов данных. В работах [35, 36] была предложена инструкция grp Г=Г2, г3, где где гг - регистр входных данных, г - регистр выходных данных, г3— регистр битов управления перестановкой. Эта инструкция иллюстрируется на рис. 11. Было доказано, что произвольное преобразование формата данных можно осуществить с использованием log2« инструкций grp, где п - длина регистров ги г2, г3. Как видно из рис. 11, данные, соответствующие единичным битам в регистре г3, группируются в начале машинного слова, а данные, соответствующие нулевым битам в регистре г3, группируются в конце машинного слова. Причем относительный порядок сгруппированных битов данных не меняется.