Введение к работе
Актуальность проблемы. Обеспечение параллелизма манипуляций с данными является одним из методов повышения производительности средств вычислительной техники. В настоящее время большинство процессоров общего назначения параллельно обрабатывают данные, имеющие 32 или 64 разряда, что позволяет с высокой скоростью осуществлять операции над числами с одинарной и двойной точностью.
С расширением области применения средств вычислительной техники все чаще возникают задачи, связанные с формированием изоморфных представлений или битовых перестановок машинного слова. В число таких задач входят обработка морфологии изображений, сортировка, моделирование и тестирование цифровых устройств, задачи биоинформатики, расчет контрольных сумм и коррекция ошибок, стеганография, сжатие и развертывание информации, выполнение криптографических примитивов, обработка сигналов в системах RPMA {random permutation-based multiple access) для передачи данных с использованием технологий расширения спектра, преобразование данных для передачи в текстовом формате и т.п. При этом затраты машинного времени на битовые преобразования данных составляют от 30 до 90% времени выполнения задач.
Битовые перестановки сложны для программной реализации. Каждый бит должен быть извлечен из исходного регистра, перемещен на новое место в регистре назначения и объединен с ранее перестановленными битами. Это требует 4 инструкций на бит (генерация маски, И, Сдвиг, ИЛИ), и An инструкций для выполнения произвольной перестановки п битов. В связи с этим в последние годы проводятся интенсивные исследования в области разработки устройств, ускоряющих обработку битов данных.
В работах 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).
В работах В. М. Курейчика, В. М. Глушань, Л. И. Щербакова, Г.С. Цирамуа, В. А. Богатырева, В.М. Полищука, В.И. Чабана, Р.В. Дмитришина и др. исследуются детерминированные и вероятностные формирователи перестановок, сочетаний и размещений. Однако предлагаемые устройства являются специализированными, их аппаратурная сложность составляет 0(п2) и быстро растет с увеличением п, где п - длина формируемого блока данных.
Таким образом, традиционные методы и аппаратурные средства для выполнения операций формирования изоморфных представлений или преобразования форматов данных в вычислительной технике существенно снижают её производительность. Существующие специальные устройства для преобразования форматов данных или не обладают необходимой универсальностью и гибкостью, или создают существенные задержки при обработке данных и сложны в аппаратурном исполнении.
В связи с вышеизложенным в вычислительной технике является актуальной научно-техническая проблема разработки универсальных устройств для ускорения выполнения процедур преобразования форматов представления данных.
Тематика диссертационной работы соответствует научной программе кафедры общей физики Саратовского государственного университета им. Н. Г. Чернышевского и кафедры систем автоматизированного проектирования и информационных систем Воронежского государственного технического университета.
Цель диссертационной работы. Создание и исследование универсальных устройств формирования изоморфных представлений данных на основе предлагаемых принципов построения и алгоритмов структурного синтеза, обеспечивающих повышение производительности средств вычислительной техники.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
Анализ областей использования, проблем, особенностей и методов осуществления преобразований форматов данных в вычислительной технике.
Выбор и обоснование универсальных базовых преобразований форматов данных, обеспечивающих повышение производительности вычислительной техники за счет параллелизма при обработке битов данных.
Разработка принципов структурного синтеза и моделей аппаратурных средств, осуществляющих базовые преобразования, создание на их основе универсальных устройств, повышающих скорость манипуляций с битами данных.
Обоснование принципов построения и разработка с использованием базовых преобразований универсальных детерминированных и вероятностных устройств, увеличивающих производительность вычислительной техники при решении задач перечисления и формирования в случайном порядке представлений данных.
Исследование повышения производительности вычислительной техники при использовании разработанных устройств на примерах различных задач, разработка рекомендаций к применению данных устройств.
Объект исследования: устройства вычислительной техники для преобразования форматов представления и манипуляций с битами данных.
Предмет исследования: структурный синтез, модели детерминированных и вероятностных устройств формирования и преобразования форматов данных.
Методы исследования. В качестве теоретической и методологической основы диссертационных исследований использованы элементы теории множеств, групп, комбинаторики, теории конечных однородных цепей Маркова и аппарата стохастических матриц, теории вероятностей, теории динамических систем с хаотической динамикой, аппарата и методов имитационного системного моделирования.
Научная новизна работы:
На основе предложенных базовых преобразований, включающих упорядоченные и неупорядоченные разбиения блока данных длиной п, обоснованы принципы создания и разработаны алгоритмы структурного синтеза детерминированных и вероятностных устройств формирования изоморфных представлений данных. Показано, что при использовании разработанных устройств вклад в увеличение производительности вычислительной системы на базе 64-разрядного процессора составляет от 2 до 10 раз для задач обработки морфологии изображений, сортировки, обработки сигналов в системах RPMA, биоинформатики, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения криптографических примитивов, алгоритма UUE преобразования данных для передачи в текстовом формате.
Доказаны теоремы о композиции переключателей для осуществления упорядоченных и неупорядоченных разбиений данных, об использовании сортирующих сетей для осуществления прямых и обратных перестановок и разбиений, о композиции формирователей разбиений слов длиной п, п/2, w/4, ..., которые обеспечили структурный синтез, и разработку моделей устройств:
параллельного формирования упорядоченных и неупорядоченных разбиений блоков данных длиной п=2 на т кластеров по 2й элементов с q = 2 log2 (п) — и — \ уровнями преобразования и аппаратурной сложностью не более чем п (log 2 (и) - и/2 — 1) +1 логических элементов матрицы формирователя, где ^-положительное целое число, а и=0,.. .,к-1;
параллельного формирования упорядоченных разбиений блоков данных длиной п на т кластеров с использованием топологий сортирующих сетей, что обеспечивает уменьшение времени установления готовности устройства к реализации заданного преобразования при смене дескриптора формата;
параллельного формирования перестановок с заданной структурой циклов, аппаратурной сложностью О ( log2 (ті) J и числом уровней преобразования q = 41og2(«);
параллельного формирования прямых и обратных преобразований упорядоченных разбиений блоков данных длиной п=2 на m кластеров по 2й элементов в классе матричных устройств с аппаратурной сложностью
0(п2);
— перечисления упорядоченных разбиений множества чисел (0,1,2,... ,п-1) на блоки по 2й элементов, выполненных на базе матриц, формирующих упорядоченные разбиения входных данных длиной п, nl2, пі А, ...,2й на два подмножества.
Обоснованы теоретические положения, включающие теоремы о композиции формирователей упорядоченных разбиений, о формировании сигналов управления переключателями, о декодировании битов управления, обеспечивающие создание универсального устройства преобразования форматов данных, выполняющего две новые инструкции bsn и grpm. Доказано, что разработанное устройство характеризуется более высокой скоростью выполнения и простотой аппаратурной реализации по сравнению с существующими решениями. На основании проведенных исследований разработаны варианты структурно-функциональной организации модулей, осуществляющих инструкции bsn, grpm, grp, pex.v, pdep.v, pex, pdep, rotate, shift.
Разработаны и обоснованы принципы построения высокопроизводительных вероятностных формирователей упорядоченных разбиений блоков данных длиной п с произвольной и заданной структурой циклов, характеризующиеся равномерным распределением вероятностей формируемых последовательностей. Разработанные вероятностные формирователи выполнены на базе предложенных устройств, осуществляющих упорядоченные и неупорядоченные разбиения. Доказано, что информационная энтропия вероятностного распределения выходных данных достигает значения более 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,l,2,...,w-l) на блоки по 2й элементов.
Универсальное устройство преобразования форматов данных на базе многоуровневой коммутационной сети baseline обеспечивает произвольное преобразование форматов данных с использованием двух инструкций bsn и выполнение специализированных инструкций манипуляций с битами данных grpm, grp, pex.v, pdep.v, рех, pdep, инструкций логического и циклического сдвига данных.
Перестановки данных с произвольной или заданной структурой циклов, формируемые разработанными вероятностными формирователями, имеют равномерное распределение вероятностей и обеспечивают значение информационной энтропии вероятностного распределения выходных данных более 50% от максимального за время, определяемое задержкой используемого формирователя.
Формирователь импульсов случайной длительности и случайных бинарных кодов состоит только из цифровых элементов и при соотношениях частот задающих генераторов fu/njixjiiifg, удовлетворяющих выражениям
g " — > 2; = —, имеет равномерную функцию распределения
-/11./22 ./1I./22 У12У2І Jg
вероятностей формируемых бинарных последовательностей и описывается двухмерным дискретным отображением с хаотической динамикой в прямом и обратном времени.
Детекторы режимов функционирования позволяют регистрировать изменение режима колебаний, обеспечивая, таким образом, контроль режима функционирования генератора динамического хаоса.
Разработанные 64-разрядные устройства преобразования форматов данных имеют время преобразования от \2t3 до 30?3, где t3 — максимальная задержка сигнала на одном инверторе, нагруженном на четыре входа, что обеспечивает увеличение производительности вычислительной системы от 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 таблиц.
