Авторефераты по всем темам  >>  Авторефераты по техническим наукам

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

Автореферат докторской диссертации по техническим наукам

СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА

Страницы: | 1 | 2 | 3 |

 

Сотов Леонид Сергеевич

КОМБИНАТОРНЫЕ УСТРОЙСТВА ФОРМИРОВАНИЯ ИЗОМОРФНЫХ ПРЕДСТАВЛЕНИЙ ДАННЫХ, ПОВЫШАЮЩИЕ ПРОИЗВОДИТЕЛЬНОСТЬ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Специальность:а 05.13.05 - Элементы и устройства вычислительной техники и систем управления

Автореферат

диссертации на соискание ученой степени

доктора технических наук

Саратов-2011

Работа выполнена в НИУ ВПО Саратовский государственный университет им. Н.Г. Чернышевского и в ГОУ ВПО Воронежский государственный технический университет.

Научный консультант:аа доктор технических наук, профессор

Антимиров Владимир Михайлович

Официальные оппоненты:аа доктор технических наук, профессор

Хетагуров Ярослав Афанасьевич

доктор технических наук, профессор Зольников Владимир Константинович

доктор физико-математических наук, профессор Безручко Борис Петрович

Ведущая организация:аа ОАО Институт электронных управляющих машин

им. И.С. Брука, г. Москва

Защита состоится 21 декабря 2011 года в 14.00 часов на заседании диссертанционного совета Д. 212.242.08 при ГОУ ВПО Саратовский государственный техннический университет по адресу: 410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319.

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО Саратовский государственный технический университет.

Автореферат размещён на сайте ВАК РФ л______ аа 2011 г.

Автореферат разослан л______ а 2011 г.

Ученый секретарь

диссертационного советаа А. А. Терентьев

2

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

С расширением области применения средств вычислительной техники все чаще возникают задачи, связанные с формированием изоморфных представлений или битовых перестановок машинного слова. В число таких задач входят обработнка морфологии изображений, сортировка, моделирование и тестирование цифронвых устройств, задачи биоинформатики, расчет контрольных сумм и коррекция ошибок, стеганография, сжатие и развертывание информации, выполнение крипнтографических примитивов, обработка сигналов в системах RPMA {randompermuнtation-basedmultipleaccess) для передачи данных с использованием технологий расширения спектра, преобразование данных для передачи в текстовом формате и т.п. При этом затраты машинного времени на битовые преобразования данных сонставляют от 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 (InverseButterfly), grp (Grop), разработаны устройстнва для их реализации. Последовательное использование инструкций bflyи ibflyданёт возможность осуществить любую перестановку, но её выполнение может занинмать значительное время. Инструкция grpявляется альтернативным подходом, но существующие аппаратурные решения не обладают необходимым быстродействинем и сложны.

Для увеличения производительности в платформах: IA-32 (IntelArchitecture, 32-bit), AMD64 , Itanium ISA, POWER (PerformanceOptimizationWithEnhancedRISC), кроме указанных базовых инструкций, вводится поддержка специализиронванных команд для манипуляций с битами данных. Однако при этом теряется унинверсальность.

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

3

последовательные,аа достаточноаа медленныеаа алгоритмыаа Фишера-Йетсаа (FisherЧ Yates), Саттоло (Sattolo).

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

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

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

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

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

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

1. Анализ областей использования, проблем, особенностей и методов осунществления преобразований форматов данных в вычислительной технинке.
2. Выбор и обоснование универсальных базовых преобразований форматов данных, обеспечивающих повышение производительности вычислительнной техники за счет параллелизма при обработке битов данных.
3. Разработка принципов структурного синтеза и моделей аппаратурных средств, осуществляющих базовые преобразования, создание на их оснонве универсальных устройств, повышающих скорость манипуляций с бинтами данных.
4. Обоснование принципов построения и разработка с использованием банзовых преобразований универсальных детерминированных и вероятнонстных устройств, увеличивающих производительность вычислительной техники при решении задач перечисления и формирования в случайном порядке представлений данных.
5. Исследование повышения производительности вычислительной техники при использовании разработанных устройств на примерах различных зандач, разработка рекомендаций к применению данных устройств.

4

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

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

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

Научная новизна работы:

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

1. параллельного формирования упорядоченных и неупорядоченных разбиенний блоков данных длиной п=2 на т кластеров по 2й элементов с q= 2 log2 (п) Ч и Ч \ уровнями преобразования и аппаратурной сложнонстью не более чем п ж (log2 (п) Ч и/2 Ч 1) +1 логических элементов матрицы формирователя, где ^-положительное целое число, а и=0,.. .,к-1;
2. параллельного формирования упорядоченных разбиений блоков данных длиной п на т кластеров с использованием топологий сортирующих сентей, что обеспечивает уменьшение времени установления готовности устнройства к реализации заданного преобразования при смене дескриптора формата;
3. параллельного формирования перестановок с заданной структурой цикнлов, аппаратурной сложностью О ( log2 (п) J и числом уровней преобразонвания q= 41og2(л);
4. параллельного формирования прямых и обратных преобразований упоряндоченных разбиений блоков данных длиной п=2 на т кластеров по 2й элементов в классе матричных устройств с аппаратурной сложностью

0(2);

5

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

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

5.аа Разработан способ построения формирователя импульсов случайной длин

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

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

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

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

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

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

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

собы построения и модели детекторов режимов функционирования генераторов

случайных сигналов, основанные на анализе периодов возвратов изображающей

точки в фазовом пространстве контролируемых генераторов и проверке непрен

рывности распределения спектральной плотности мощности.

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

6

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

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

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

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

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

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

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

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

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

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

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

7

числения упорядоченных разбиений строки чисел (0,l,2,...,w-l) на блоки по 2й элементов.

1. Универсальное устройство преобразования форматов данных на базе многонуровневой коммутационной сети baselineобеспечивает произвольное преобразонвание форматов данных с использованием двух инструкций bsnи выполнение специализированных инструкций манипуляций с битами данных grpm, grp, pex.v, pdep.v, рех, pdep, инструкций логического и циклического сдвига данных.
2. Перестановки данных с произвольной или заданной структурой циклов, формируемые разработанными вероятностными формирователями, имеют равнномерное распределение вероятностей и обеспечивают значение информационнной энтропии вероятностного распределения выходных данных более 50% от максимального за время, определяемое задержкой используемого формироватенля.
3. Формирователь импульсов случайной длительности и случайных бинарных кодов состоит только из цифровых элементов и при соотношениях частот зандающих генераторов /и/п/п/и^, удовлетворяющих выражениям

g"---- Ч >2;--------------- = Ч ж> имеет равномерную функцию распределения

J\\J22J\\J22а J\2J2\Jg

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

1. Детекторы режимов функционирования позволяют регистрировать измененние режима колебаний, обеспечивая, таким образом, контроль режима функционнирования генератора динамического хаоса.
2. Разработанные 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 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

9

распознавания геометрических образов и символов на бинарных изображениях, обработки морфологии изображений, медианной фильтрации для устранения шунмов на изображениях, операций преобразования представлений генетических понследовательностей в биоинформатике, расчета контрольных сумм и коррекции ошибок, стеганографии, сжатия и развертывания информации, выполнения крипнтографических примитивов, преобразования данных для передачи в текстовом формате, обработки сигналов в системах RPMAдля передачи с использованием технологий расширения спектра и т.п. На основе проведенных исследований понказано, что затраты машинного времени на преобразования форматов данных в исследованных задачах составляют от 30 до 90%. Наиболее критичной к скорости выполнения битовых манипуляций является обработка данных в системах RPMA. В этих системах передаваемые и принимаемые данные подвергаются обработке, связанной со случайными перестановками. Каждый элемент Xвходного набора данных XЧ {X1, ...,Хп) разделяется на Р блоков Хк Ч (Х%, ...,Хр). Формируется случайная перестановка ?, которая используется для преобразования набора входных данных X. Принимаемые данные подвергаются обратному преобразованнию 7Г-1.

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

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

СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА

Страницы: | 1 | 2 | 3 |

     Авторефераты по всем темам  >>  Авторефераты по техническим наукам