Авторефераты по всем темам >>
Авторефераты по разным специальностям
На правах рукописи
СОБОЛЕВ Сергей Сергеевич АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ СПЕЦИАЛИЗИРОВАННЫХ УСТРОЙСТВ ГЕНЕРАЦИИ ПОЛНЫХ КОМБИНАТОРНЫХ ПЕРЕСТАНОВОК ЭЛЕМЕНТОВ СИМВОЛЬНОЙ СТРОКИ Специальность 05.13.12 - Системы автоматизации проектирования
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Воронеж 2012
Работа выполнена в ФГБОУ ВПО Воронежская государственная лесотехническая академия
Научный консультант: доктор технических наук, профессор, заведующий кафедрой вычислительной техники и информационных систем Воронежской государственной лесотехнической академии Зольников Владимир Константинович
Официальные оппоненты: доктор технических наук, профессор, заведующий кафедрой естественно-научных дисциплин Российского государственного социального университета (филиал в г. Воронеж) Стародубцев Виктор Сергеевич доктор технических наук, профессор кафедры систем автоматизированного проектирования и информационных систем, Баранников Николай Ильич
Ведущая организация: Федеральное государственное унитарное предприятие Научно-исследовательский институт электронной техники (г. Воронеж)
Защита состоится 11 мая 2012 г. в 10:00 на заседании диссертационного совета Д212.034.03 при ФГБОУ ВПО Воронежская государственная лесотехническая академия по адресу: 394087, г. Воронеж, ул. Тимирязева, 8, ауд. 242.
С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО Воронежская государственная лесотехническая академия
Автореферат разослан 10 апреля 2012 г.
Ученый секретарь диссертационного совета: В.И.Анциферова
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. Современное развитие полупроводниковых технологий, характеризующееся повышением сложности электронных устройств, изменением проектных норм, разделением труда проектировщиков и образованием кремниевых фабрик, предопределило изменения в методологии проектирования сверхбольших интегральных схем (СБИС). При наблюдаемом общем росте ресурсоемкости процесса разработки эффективным является применение методологии нисходящего проектирования на основе многоуровневого иерархического представления устройств и перехода в процессе проектирования от общего описания системы к детальному описанию составляющих ее компонентов - сложных функциональных блоков, или IP-блоков (от англ. Intellectual Property).
Наряду с изменениями стандартных методов разработки СБИС, необходимо отметить развитие методологии проектирования в соответствии с классом целевых интегральных схем. Учет специфики конкретного класса СБИС позволяет принять во внимание его особенности уже на ранних этапах проектирования и обеспечить более эффективную адаптацию архитектуры на конкретную задачу по сравнению со стандартными средствами, ориентированными на широкую область применения. Примерами таких классов микросхем являются схемы памяти, схемы программируемой логики (ПЛИС), характеризующиеся регулярной структурой. В настоящее время на мировом рынке существует множество фирм, специализирующихся на проектировании конкретного класса СБИС, например, крупнейшими производителями ПЛИС являются компании Altera и Xilinx.
Одним из специфических классов СБИС являются специализированные устройства генерации полных комбинаторных перестановок символьной строки, используемых главным образом в системах защиты информации ЭВМ. Основными особенностями таких устройств являются переменная разрядность символьной строки и наличие ограничений на требуемое множество генерируемых комбинаторных перестановок в некоторых приложениях. Например, в системах динамического преобразования форматов на основе транспозиционных преобразований, некоторые из перестановок являются недопустимыми и могут быть непригодными для формирования использующихся в этих системах дескрипторов формата, а значит, должны быть исключены из рассмотрения. В этом прослеживается аналогия со слабыми ключами в современных шифрах, например, DES. В рассматриваемом случае, перестановка является недопустимой, если она содержит одну или несколько неподвижных точек и/или инволюций.
Применение стандартных средств проектирования при разработке рассматриваемых специализированных СБИС связано с рядом проблем. Современная методология проектирования предполагает разбиение маршрута проектирования на несколько этапов проектных процедур. Первые два этапа составляют проектирование на системном уровне и на уровне регистровых передач (RTL-уровень). На верхнем структурном уровне, называемом также системным, разрабатывается и верифицируется обобщенная модель блока для проверки работоспособности взятого за основу математического алгоритма генерации перестановок. В качестве языка описания чаще всего используется язык SystemC.
На RTL-уровне разрабатывается функциональное описание блока на уровне регистровых передач с использованием одного из языков описания аппаратуры (HDL-языков).
Такое описание осуществляется чаще всего вручную, путем графического или текстового ввода, что, во-первых, увеличивает трудоемкость и требует недопустимо больших затрат времени, а во-вторых, влечет за собой разрыв между алгоритмическим описанием на SystemC и RTL-описанием. Аналогичный разрыв наблюдается и при разработке тестов для верификации блоков на системном и RTL-уровнях.
Обозначенные проблемы, а также многообразие входных параметров генерации комбинаторных перестановок и увеличение сложности схемы блока генерации с ростом длины символьной строки, повышают риск субъективных ошибок и, таким образом, увеличивают влияние человеческого фактора на качество всего проекта. В результате, использование традиционной методологии в процессе проектирования рассматриваемых устройств представляется затруднительным. В этой связи, актуальной задачей представляется разработка средств автоматизации проектирования специализированных устройств генерации комбинаторных перестановок элементов символьной строки, обеспечивающих высокое качество целевых устройств и позволяющих максимально автоматизировать процесс проектирования и верификации на системном и RTL-уровнях.
Диссертационная работа выполнена в рамках госбюджетной НИР кафедры вычислительной техники и информационных систем ВГЛТА Автоматизация проектных работ при создании изделий микроэлектроники и лесного комплекса, ГР №01.2.00609244, код ГРНТИ 68.47.01; 50.49.
Объектом исследования является средства автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, предназначенных для обеспечения конфиденциальности данных в рамках СУБД.
Предметом исследования являются модели, алгоритмы и методы проектирования и моделирования в САПР устройств генерации полных комбинаторных перестановок с отсевом недопустимых перестановок, содержащих неподвижные точки и обратимые пары.
Целью исследования является разработка средств проектирования: методики, моделей, методов и алгоритмов для специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки.
В соответствии с поставленной целью в диссертационной работе необходимо решить следующие задачи:
провести анализ современного состояния средств автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, выделить направления их текущего развития;
разработать методику проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки, позволяющую обеспечить наиболее эффективное проектирование устройств генерации полных комбинаторных перестановок;
разработать модели, алгоритмы и методы, позволяющие учесть особенности проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки переменной разрядности с возможностью отсеивания недопустимых перестановок, которые могут снизить качество проекта;
разработать алгоритмическую основу синтеза тестовой последовательности, учитывающей особенности проектирования устройств генерации полных комбинаторных перестановок на системном уровне и уровне регистровых передач (RTL);
разработать программное обеспечение подсистемы генерации функциональных блоков для формирования множества полных комбинаторных перестановок элементов символьных строк, верификации и синтеза тестовой последовательности, внедрить разработанные средства в единую среду сквозного проектирования дизайн-центра.
Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы элементы теории автоматизированного проектирования, множеств, дискретной математики, методы и средства структурнофункционального моделирования, технологии объектно-ориентированного и событийно-ориентированного программирования, а также мета-программирования.
Научная новизна результатов, полученных при решении вышеперечисленных задач исследования, состоит в следующем:
методика проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки, отличающаяся встроенными средства проектирования специальных микросхем, что позволяет обеспечить более высокое качество и сокращение цикла проектирования устройств генерации полных комбинаторных перестановок;
метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности, отличающийся наиболее полной автоматизацией процесса проектирования на системном уровне и уровне регистровых передач;
метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности, отличающийся возможностью отсеивания неподвижных точек и инволюций в процессе реализации, что позволяет исключать недопустимые перестановки на этапе комбинаторной генерации множества возможных перестановок;
алгоритм генерации функциональных блоков для формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности, отличающийся использованием в нем предложенных методов аппаратной генерации перестановок с отсеиванием неподвижных точек и инволюций и генерации соответствующих функциональных блоков;
алгоритм синтеза тестов для верификации функциональных блоков на системном уровне и уровне регистровых передач, отличающийся учетом особенностей проектирования устройств генерации полных комбинаторных перестановок.
Практическая значимость и результаты внедрения. Практическая значимость работы заключается в улучшении качества проектных работ и сокращении жизненного цикла проектирования специализированных устройств генерации полных комбинаторных перестановок за счет внедрения аппаратно-программных средств.
На основе предложенных методов, математических моделей и алгоритмов разработано программное обеспечение. Оно внедрено в ЗАО НПП Рэлекс (г. Воронеж) с экономическим эффектом 405 тыс. рублей и в учебный процесс ФГБОУ ВПО Воронежская государственная лесотехническая академия (в учебно-методические материалы дисциплин Системы автоматизации проектирования, Схемотехническое и функциональное проектирование электронной компонентной базы в САПР, Методы проектирования микроэлектронных устройств для подготовки студентов ВГЛТА по направлению Информационные системы и технологии, а также аспирантов и докторантов по специальности 05.13.12 - Системы автоматизации проектирования).
Полученные средства позволяют снизить трудоемкость, сократить время разработки и минимизировать риск субъективных ошибок при проектировании специализированных устройств генерации комбинаторных перестановок элементов символьной строки.
Выносятся на защиту:
методика проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки;
метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности;
метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности;
алгоритм генерации функциональных блоков для формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности;
алгоритм синтеза тестов для верификации функциональных блоков на системном уровне и уровне регистровых передач.
Соответствие паспорту специальности. Согласно паспорту специальности 05.13.12 - Системы автоматизации проектирования, задачи, рассмотренные в диссертации, соответствуют областям исследований:
1. методология автоматизированного проектирования в технике, включающая постановку, формализацию и типизацию проектных процедур и процессов проектирования, вопросы выбора методов и средств для применения в САПР;
3. разработка научных основ построения средств САПР, разработка и исследование моделей, алгоритмов и методов для синтеза и анализа проектных решений, включая конструкторские и технологические решения в САПР и АСТПП.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Международной научной конференции Проблемы управления, передачи и обработки информации (Саратов, 2009), Международной научнопрактической конференции Молодежь и наука: реальность и будущее (Невинномыск, 2010), Всероссийской конференции с элементами научной школы для молодежи Математическое моделирование в технике и технологии (Воронеж, 2011), Международной научно-практической конференции Современные проблемы гуманитарных и естественных наук (2011).
Публикации результатов работы. По теме диссертации опубликовано 20 работ, в том числе 6 статей в изданиях Перечня, определенного ВАК Минобрнауки России, монография, 1 свидетельство об официальной регистрации программ для ЭВМ, а также 1 патент на изобретение.
ичное участие заключается в определении цели и задач работы [1-3, 13-14], в выполнении научно-технических исследований [10-11], разработке и анализе моделей [4, 5, 15, 18, 19], разработке алгоритмов [10-12], разработке методики проектирования [6, 7, 16, 17, 20], программной реализации [9] и аппаратной реализации [8].
Структура и объм работы. Диссертация состоит из введения, четырех глав, заключения, изложенных на 129 страницах, включающих в себя список литературы из 104 наименований, 30 рисунков и 13 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы исследования, определены цели и задачи работы, методы решения поставленных задач, отмечены основные результаты исследования, выносимые на защиту; определена их научная новизна и практическая значимость; приведены сведения об апробации и внедрении результатов работы.
В первой главе проведен анализ современного состояния средств автоматизированного проектирования устройств генерации комбинаторных перестановок элементов символьной строки, выделены направления и проблемы их текущего развития, обозначены сферы практического применения и исследованы особенности этих устройств.
Проведен анализ устройств генерации полных комбинаторных перестановок элементов символьной строки. Исследована их область применения, которая показала достаточно широкий спектр использования в следующих приложениях: в устройствах аппаратной поддержки технологий систем автоматизированного проектирования радиоэлектронной аппаратуры; в системах защиты информации, где применяются различные шифры на основе перестановок; в системах аппаратного обеспечения динамического преобразования форматов данных в реляционных СУБД.
Определены особенности устройств генерации полных комбинаторных перестановок элементов символьной строки и методы проектирования. Показано, что за счет их особенностей средства проектирования могут быть дополнены специальными средствами, которые значительно сократят время проектирования. Кроме того за счет увеличения автоматизации процесса проектирования будет обеспечена бездефектность процесса проектирования.
На основании проведенного анализа и обозначенных проблем сформулированы цели и определены задачи диссертационного исследования.
Во второй главе предложена методика проектирования специализированных устройств генерации полных комбинаторных перестановок, метод генерации функциональных блоков для рассматриваемых устройств, а также приводятся алгоритмы генерации перестановок с отсевом перестановок, содержащих неподвижные точки и/или инволюции, и соответствующего набора верификационных тестов.
Специфика устройств генерации полных комбинаторных перестановок элементов символьной строки с отсевом недопустимых перестановок связана с их следующими особенностями:
1. Длина символьной строки, а также разрядность одного элемента символьной строки, для которой производится генерация комбинаторных перестановок, является переменной величиной.
2. Максимально допустимое количество неподвижных точек и/или инволюций является переменной величиной.
Учитывая данную специфику, в рамках проектирования на системном уровне предложено:
в качества языка описания поведенческой модели использовать SystemC - язык проектирования и верификации моделей системного уровня;
генерировать данную поведенческую модель с помощью программного модуля, реализованного на высокоуровневом языке C++, на основе следующих входных параметров:
а) - разрядность одного элемента символьной строки, для которой производится генерация комбинаторных перестановок;
б) - длина данной символьной строки, или мощность множества, для которого формируются перестановки;
в) - количество неподвижных точек в каждой из сгенерированных перестановок, достаточное для ее отсеивания;
г) - количество инволюций в каждой из сгенерированных перестановок, достаточное для ее отсеивания;
генерировать тесты для верификации поведенческой модели также с помощью с помощью программного модуля на С++ с тем же множеством входных параметров.
SystemC представляет собой надстройку стандартного языка программирования С++, реализованную в виде отдельных библиотек специальных классов. Данные библиотеки содержат в себе конструкции, позволяющие создавать эффективные и точные модели программных алгоритмов, аппаратных архитектур, интерфейсов и схем на системном уровне.
На этапе разработки функционального описания блока на уровне регистровых передач (RTL) создается синтезируемая RTL-модель блока на одном из языков описания аппаратуры. В рамках проектирования рассматриваемых устройств генерации перестановок в качестве такого языка предложен язык VHDL. Данный этап выполняется в автоматическом режиме, предполагающем генерацию VHDL-кода с помощью программного модуля на языке C++. Тесты для верификации на RTL-уровне генерируются также с помощью програсммного модуля на языке С++. Учитывая специфику блока генерации полных комбинаторных перестановок элементов символьной строки, оба модуля принимают на вход то же множество входных параметров, что и для автоматизированного формирования SystemC модели и тестов на системном уровне (,,, ). Общий маршрут проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки при использовании предложенной методики проектирования изображен на рис. 1 (элементы, отличающиеся новизной, отмечены серой заливкой).
Создание Генерация описания поведенческой SystemC C++ модели на SystemC модели Библиотека SystemC Генерация тестов для Системная поведенческой SystemC C++ верификация модели Генерация описания Создание RTL-модели на C++ VHDL RTL-модели VHDL Библиотеки RTL- Моделирование моделей Генерация тестов для и верификация C++ VHDL RTL-модели RTL-модели Логический синтез Статический Библиотеки Логическое моделирование временной анализ производии верификация телей СБИС Физический синтез и Генерация тестов верификация топологий Рис. 1. Маршрут проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки Преимущество предложенной методики состоит в автоматизации процесса аппаратного описания, создания тестов и верификации на системном и RTL уровнях. Это позволяет существенно сократить цикл проектирования рассматриваемых специалигенерации перестановок Множество входных параметров зированных устройств за счет исключения процесса ручного описания, традиционного для стандартных средств проектирования. Кроме того, данная методика позволяет минимизировать общее количество проектных ошибок и, как следствие, обеспечивает более высокое качество специализированных устройств генерации перестановок.
Предложенный метод генерации функциональных блоков для устройств формирования множества комбинаторных перестановок элементов символьной строки переменной разрядности заключается в следующем. Для обеспечения гибкости системной и RTL-моделей генератора перестановок используется множество входных параметров, позволяющих по требованию модифицировать основные характеристики устройства. На основе этих параметров генерируются программные IP-блоки на SystemC и VHDL, отвечающие всем входным аргументам. Генерация функциональных блоков может происходить в двух режимах (общая схема представлена на рис. 2).
Множество входных параметров системной модели d = 3; n = 8; Nmax = 1;Rmax = Режим I Режим II Набор процедур source_gen(d: 3; n: 8; sync: 1);
Е.
Чтение входных данных Генерация кода SystemC Лексический анализ Генерация кода VHDL Синтаксический анализ Генерация кода SystemC Генерация кода VHDL Функциональные блоки для устройств генерации перестановок Программные блоки на Программные блоки на VHDL SystemC (системная модель) (RTL-модель) Рис. 2. Схема генерации функциональных блоков для устройств формирования множества комбинаторных перестановок.
При использовании первого режима, блоки на SystemC и VHDL генерируются напрямую с использованием входных параметров блока генерации:.
Второй режим позволяет тонко конфигурировать модели и обеспечивает возможность трансформации системы с минимальной затратой ресурсов. Режим предусматривает процесс генерации блоков в несколько этапов. Первый этап - это формирование набора процедур, каждая из которых может принимать в качестве входных аргументов один или несколько вышеприведенных параметров, а также ряд других опциональных параметров (например, тактируемость блока, наличие порта асинхронного сброса RESET). Каждая процедура позволяет настраивать отдельные части моделей и регулировать взаимодействия между ними.
Второй этап заключается в синтаксическом разборе списка процедур и генерации кода конечных моделей на SystemC и VDHL. Эти действия осуществляет программный модуль на языке C++. Программный модуль включает в себя:
лексический и синтаксический анализатор;
шаблоны модулей, сигналов SystemC, необходимые для описания поведенческой модели генерации перестановок; шаблоны объектов, сигналов VHDL, необходимые для описания RTL-модели генерации перестановок;
генератор кода SystemC/VHDL с использованием этих шаблонов.
Общая схема предложенного алгоритма генерации комбинаторных перестановок с возможностью отсева недопустимых перестановок для длины символьной строки представлена на рис. 3.
А Полезная длина строки k = Циклических сдвигов: 1, Полезная длина строки k = перестановок: АB ВА Циклических сдвигов: 4, Полезная длина строки k = перестановок: АВC ВCА CАВ ВАС АСВ СВА Фильтрация перестановок, содержащих количество неподвижных точек, превышающих максимально допустимое ( ) Фильтрация перестановок, содержащих количество инволюций, превышающих максимально допустимое ( ) Результирующее множество перестановок Рис. 3. Схема алгоритма генерации перестановок для.
Заметим, что рассматриваемый алгоритм представляет собой комбинацию следующих последовательно применяемых элементарных операций: добавление нового символа в строку (увеличение полезной длины строки) и циклический сдвиг строки.
Подобная структура делает данный алгоритм очень удобным для аппаратной реализации на основе регистров циклического сдвига.
В качестве множества упорядоченных элементов, на основе которого осуществляется генерация, берется исходная строку длины, заполненная уникальными символами, т.е.
(1) где - символ, находящийся на i-ой позиции в строке, причем.
Множество всех перестановок обозначим (2) Неподвижной точкой перестановки является неподвижная точка отображения ( ) ( ), т.е. элемент множества { }.
Инволюцией перестановки является такая пара элементов ( ), что выполняются условия:
(3) ( ) ( ) ( ) Предложим следующее разбиение множества на подмножеств:
(4) * | ( )| + где.
Две перестановки входят в одно подмножество только в том случае, если количество неподвижных точек у них одинаково. Введем для фиксированного набор функций, возвращающих количество перестановок из множества с определенным числом неподвижных точек и с числом неподвижных точек, не меньшим определенного числа:
( ) | | (5) ( ) | | ( ) Общее количество перестановок с неподвижными точками на множестве мощности вычисляется по следующей формуле:
(6) ( ) ( ) Формула для общего количества перестановок с числом неподвижных точек, не меньшим, на множестве мощности выглядит следующим образом:
( ) (7) ( ) где - это субфакториал числа, или количество перестановок порядка без неподвижных точек.
( ) Значения функций возрастают экспоненциально с ростом. При больших процентная доля перестановок с числом неподвижных точек, не меньшим, становится постоянной величиной. При (в случае фильтрации перестановок, содержащих хотя бы одну неподвижную точку) относительное количество отсеиваемых перестановок (составляющих множество) представляется как: составляет:
| | (8) ( ) | | В третьей главе предложен метод аппаратной генерации полных комбинаторных перестановок в символьной строке переменной разрядности, описываются архитектурные модели (системная и RTL-модель) соответствующих устройств.
Общая структура подсистемы генерации полных комбинаторных перестановок представлена на рис. 4. Она включает в себя несколько блоков, каждый из которых имеет свою функциональность.
Блок подсчета количества неподвижных точек Формирователь Формирователь Блок Блок Блок подсчета исходной очередной фильтрации приема количества символьной уникальной недопустимых перестановок инволюций строки перестановки перестановок Блок проверки корректности перестановки Рис. 4. Общая структура блока генерации полных комбинаторных перестановок с отсевом недопустимых перестановок Задача формирователя исходной символьной строки - сформировать символьную строку фиксированной длины, множество элементов которой представляет собой упорядоченный набор целых чисел от 0 до. Таким образом, элементами исходной символьной строки являются элементы множества (9) { }, где - наперед заданное количество элементов.
Формирователь очередной уникальной перестановки принимает на вход сформированную предыдущим блоком символьную строку и на е основе формирует выходную символьную строку, элементы которой образуют уникальную перестановку.
Задачей следующих четырех блоков является подсчитать количество неподвижных точек и инволюций в очередной сформированной перестановке, проверить корректность текущей перестановки и отсеять недопустимые перестановки (которые либо сформированы некорректно, либо содержат количество неподвижных точек или инволюций, превышающее наперед заданное критическое значение или соответственно). В случае успешной проверки перестановки, она передается на вход блока приема перестановок, формирующего результирующее множество сгенерированных перестановок.
Для моделирования и верификации на системном уровне использовался язык SystemC. Каждому блоку на рис. 4 соответствует отдельный модуль (или класс, в терминах объектно-ориентированного программирования) в системной модели SystemC.
Модуль формирования очередной уникальной перестановки включает в себя модулей циклического сдвига и вспомогательных модулей управления. Модули циклического сдвига соединены последовательно и имеют уровень от 2 до в соответствии с увеличением полезной длины символьной строки согласно алгоритму на основе циклического сдвига.
Каждый модуль циклического сдвига обладает портами управления L и S. При высоком логическом уровне сигнала на входе L значения элементов символьной строки считываются с входных портов и тут же передаются на выходные порты (либо на следующий уровень, либо в качестве результирующей перестановки), без циклического сдвига. При высоком логическом уровне сигнала на входе S, происходит циклический сдвиг строки, хранящейся во внутреннем массиве модуля, и е передача на выходные порты. Значения сигналов на портах L и S вычисляются согласно значениям функций ( ) и ( ), где - уровень модуля, а - внутренний счетчик вспомогательного модуля управления, увеличивающийся с каждым тактовым импульсом.
( ) [ ( ) ] ( ) (10) ( ) ( ) *( ( )) ( ) + { Разработка RTL-описания блока генерации комбинаторных перестановок осуществлялась с применением языка описания аппаратуры VHDL. Базовым элементом любого проекта на VHDL является объект. Блок генерации перестановок представляет собой совокупность моделируемых объектов VHDL, каждый из которых соответствует отдельному блоку на общей схеме, изображенной на рис. 4.
Соединяющие объекты сигналы могут быть единичными или множественными (векторами). Каждый передаваемый элемент перестановки моделируется на RTL( )-разрядного уровне в виде n-разрядного вектора, а вся перестановка - в виде вектора.
( )Формирователь исходной символьной строки представляет собой разрядный регистр с параллельным вводом и выводом. Регистр хранит в себе элементы исходного упорядоченного множества X0, на основе которого осуществляется генерация перестановок. Каждый регистр представляет собой отдельный объект VHDL.
Формирователь очередной уникальной перестановки представляет собой набор регистров циклического сдвига с параллельным вводом и выводом, работа которых координируется вспомогательными объектами управления. Всего объект формирования уникальной перестановки содержит ( ) регистров ( групп по регистров) сдвига и вспомогательных объектов управления. Ширина регистров в каждой группе ступенчато увеличивается от до бит с шагом 1 в соответствии с увеличением полезной длины символьной строки согласно алгоритму на основе циклического сдвига. Каждый вспомогательный объект управления координирует работу своей группы из регистров с помощью сигналов управления, поступающих на входные управляющие порты регистров.
Для управления элементами перестановки, всякий регистр, помимо информационных портов, также обладает и двумя входными портами управления L и S. В соответствии со значениями сигналов на портах L и S, регистр либо зачитывает соответствующие биты элементов перестановки с входных информационных портов, либо осуществляет циклический сдвиг на 1 бит.
Вспомогательный объект управления включает в себя два счетчика: счетчик по модулю и счетчик по модулю. Счетчики устроены таким образом, что каждый из них по достижении своего максимального значения подает на выход высокий уровень сигнала, в противном случае - низкий уровень. Внутреннее состояние счетчика увеличивается при подаче очередного тактирующего импульса на входной порт тактирующего сигнала и сбрасывается по достижении максимального значения. Согласно значениям сигналов на выходе обоих счетчиков рассчитываются уровни управляющих сигналов L и S. Значения и вычисляются по формулам:
{ (11) где - разрядность соответствующего управляемого регистра.
В четвертой главе рассматриваются вопросы, связанные с практической реализацией предложенной подсистемы автоматизации проектирования устройств генерации полных комбинаторных перестановок.
Для автоматизации проектирования семейства генераторов полных комбинаторных перестановок разработан комплекс проблемно-ориентированного программного обеспечения, внедренный в общий маршрут проектирования данных устройств. Общая структура комплекса изображена на рис. 5.
Входные параметры генерации Модуль программного интерфейса Генерация системной модели Генерация RTL-модели Модуль Модуль Модуль Модуль генерации IP- генерации IPгенерации тестов генерации тестов блоков (SystemC) блоков (VHDL) Модуль подсистемы верификации IP-блоки Рис. 5. Структура программного комплекса автоматизации проектирования семейства генераторов полных комбинаторных перестановок.
В рамках данного программного комплекса реализованы модели, методы и алгоритмы для формирования множества комбинаторных перестановок элементов символьной строки с возможностью отсева недопустимых перестановок, содержащих неподвижные точки и/или инволюции. Программное обеспечение включает в себя набор инструментальных средств для решения задачи автоматизации проектирования целевых устройств генерации перестановок на системном (поведенческом) уровне и уровне регистровых передач (RTL-уровне). Для ввода требуемых параметров для блоков генерации комбинаторных перестановок, используется программный модуль интерфейса пользователя, пример которого изображен на рис. 6.
Модули генерации функциональных блоков и соответствующих тестов реализованы на языке высокого уровня C++. Результатом их работы являются программные IPблоки (soft IP cores) системного уровня моделирования в виде классов (модулей) SystemC, программные IP-блоки RTL-уровня моделирования в виде объектов VHDL, тесты окружения для обоих типов блоков, упаковщики IP-блоков для облегчения процесса их интеграции в проект. Программный модуль подсистемы верификации предоставляет возможность автоматической верификации IP-блоков посредством итерационного процесса прохождения тестов. Модуль реализован на языке программирования высокого уровня C++.
Рис. 6. Интерфейс пользователя для ввода параметров генерации IP-блоков Результирующие IP-блоки предназначены для использования в маршруте проектирования специализированных устройств генерации комбинаторных перестановок элементов символьной строки, применяемых в устройствах аппаратной поддержки технологий систем автоматизированного проектирования радиоэлектронной аппаратуры, в системах защиты информации, а также в системах аппаратного обеспечения динамического преобразования форматов данных в ЭВМ. Генерация полных комбинаторных перестановок производится в символьной строке переменной длины n, таким образом, целевые устройства образуют семейство аппаратных генераторов перестановок с дополнительной возможностью отсеивания неподвижных точек и инволюций.
Для оценки эффективности разработанных средств, определена сложность логической схемы каждого из семейства аппаратных генераторов перестановок путем подсчета общего количества логических вентилей и строк VHDL-кода для соответствующих устройств. В соответствии с полученными результатами произведена оценка временных затрат проектирования с учетом средней скорости разработки 100 вентилей в день (эта оценка является стандартной и неизменной на протяжении последних пяти лет). Результаты представлены в таблице 1.
Таблица 1. Сложность логических схем устройств генерации комбинаторных перестановок и оценка временных затрат проектирования.
Длина символьной строки n n = 16 n = 24 n = Количество логических вентилей 3200 7400 133Количество строк VHDL-кода 1120 2180 37Временные затраты, в человеко-днях 32 74 1(стандартная методика) Временные затраты, в человеко-днях 1 1 (предложенная методика) Автоматизация процессов аппаратного описания и верификации на системном и RTL-уровнях позволяет существенно сократить цикл проектирования за счет исключения процесса ручного описания на одном из HDL-языков. Как отражено в таблице 1, этот процесс обладает значительной трудоемкостью, возрастающей в квадратичной зависимости с увеличением длины строки n.
Кроме того, использование разработанных средств повышают эффективность проектирования за счет минимизации общего количества проектных ошибок и обеспечения бездефектности специализированных устройств генерации перестановок.
Разработка модулей программного обеспечения, реализующих предложенные модели, методы и алгоритмы для автоматизации проектирования семейства генераторов, осуществлена с использованием языка программирования C++ в среде Visual Studio 2010. Для симуляции моделей на SystemC использовались библиотеки SystemC версии 2.2.0. Разработка RTL-моделей на языке VHDL и их симуляция осуществлялась в среде ModelSimSE 6.5b, логический синтез проводился с помощью программного комплекса Synplicity Synplify Pro.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Проведен анализ современного состояния средств автоматизированного проектирования специализированных устройств генерации полных комбинаторных перестановок, определены направления их текущего развития.
2. Разработана методика проектирования специализированных устройств, решающих задачу генерации полных комбинаторных перестановок с функцией фильтрации недопустимых перестановок.
3. Разработаны и исследованы модели, алгоритмы и методы, позволяющие учесть особенности проектирования устройств генерации полных комбинаторных перестановок элементов символьной строки переменной разрядности с возможностью отсеивания недопустимых перестановок.
4. Разработаны алгоритмы синтеза тестовой последовательности, учитывающие особенности проектирования устройств генерации комбинаторных перестановок.
5. Разработаны программные средства, реализующие подсистему автоматической генерации функциональных блоков для формирования множества полных комбинаторных перестановок на системном и RTL-уровнях проектирования.
6. Разработаны программные средства, реализующие автоматическую генерацию тестов для функциональных блоков генерации комбинаторных перестановок.
7. Разработаны программные средства подсистемы верификации, предоставляющие возможность автоматизировать процесс верификации функциональных блоков генерации полных комбинаторных перестановок.
8. Подсчитаны трудоемкость и временные затраты проектирования каждого из семейства устройств генерации комбинаторных перестановок и произведена оценка эффективности разработанных средств автоматизации проектирования данных устройств.
9. Разработанные программные средства внедрены в единую среду сквозного проектирования специализированных устройств генерации перестановок в рамках дизайнцентра (ЗАО НПП Рэлекс, г. Воронеж) с полученным экономическим эффектом в размере 405 тыс. рублей и в учебный процесс Воронежской государственной лесотехнической академии.
Основные результаты диссертации опубликованы в следующих работах:
Публикации в изданиях Перечня, определенного ВАК Минобрнауки России 1. Соболев, C.C. Динамическое форматирование структурных объектов хранилищ данных [Текст] / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Проблемы информационной безопасности. Компьютерные системы. - 2008. - №4. - С. 28-33.
2. Сотов, Л.С. Кросс-кластерная коммутационная матрица для аппаратной поддержки управляемой перестановки данных в криптографических системах [Текст] / Л.С. Сотов, C.C. Соболев, В.Н. Харин // Проблемы информационной безопасности.
Компьютерные системы. - 2009. - №4. - С. 56-63.
3. Соболев, C.C. Модели устройств кросс-кластерных перестановок данных в ЭВМ [Текст] / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Вестник компьютерных и информационных технологий. - 2009. - №12. - С.51-55.
4. Соболев, С.С. Алгоритм работы и модель функционального генератора перестановок [Текст] / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Информационные технологии.
Ц 2010. - №4. - С. 41-46.
5. Соболев, С.С. Модель генератора перестановок на основе управляемого циклического сдвига [Текст] / C.C. Соболев, В.К. Зольников // Гетеромагнитная микроэлектроника : сб. науч. тр. / под ред. проф. А. В. Ляшенко. - Саратов : Изд-во Сарат. ун-та, 2011. - Вып. 11 : Гетеромагнитная микро- и наноэлектроника. Прикладные аспекты.
Экономика. Методические аспекты физического образования. - С. 44-57.
6. Зольников В.К. Автоматизация проектирования устройств генерации комбинаторных перестановок // В.К.Зольников, С.С.Соболев // Научный журнал КубГАУ [Электронный ресурс]. - Краснодар: КубГАУ, 2012. - №03(77). - Шифр Информрегистра: 0420700012\0043 - Режим доступа:
Монография 7. Соболев, С.С. Проектирование устройств генерации полных комбинаторных элементов символьной строки [Текст] / C.C.Соболев, В.К.Зольников. - Воронеж:
ВГЛТА, 2012. - 150 с.
Патенты и зарегистрированные программы 8. Пат. на изобретение RU №2419174 G11C 19/00 (2006.01) Устройство управляемого циклического сдвига [Текст] / Сотов Л.С., Харин В. Н., Соболев С.С. (Россия). - № 2009134344/08; заявл. 14.09.2009; опубл. 20.05.2011. - Бюл. №14. - 10 с.
9. Программа моделирования комбинаторных преобразований форматов представления данных в ЭВМ (D_MATRIX). Свидетельство об официальной регистрации программ для ЭВМ / Л.С. Сотов, С.С. Соболев, В.Н. Харин. - № 2010612449 от 07.04.2010.
Депонированные рукописи 10. Соболев, С. С. Локализация неподвижных точек при комбинаторной генерации перестановок с применением циклического сдвига [Текст] / С. С. Соболев, В. Н.
Харин, Л. С. Сотов; Федеральное агентство по образованию, ГОУ ВПО Воронежская государственная лесотехническая академия. - Воронеж, 2010. - 8 с. : ил. - Библиогр.:
с. 8. - Рус. - Деп. в ВИНИТИ РАН 02.08.2010 №479-В2010.
11. Соболев, С. С. Алгоритм генерации полных комбинаторных перестановок с применением циклического сдвига [Текст] / С. С. Соболев, В. Н. Харин, Л. С. Сотов;
Федеральное агентство по образованию, ГОУ ВПО Воронежская государственная лесотехническая академия. - Воронеж, 2010. - 6 с. : ил. - Библиогр.: с. 6. - Рус. - Деп. в ВИНИТИ РАН 02.08.2010 №480-В2010.
12. Соболев, С. С. Локализация обратимых пар при комбинаторной генерации перестановок с применением циклического сдвига [Текст] / С. С. Соболев, В. Н. Харин, Л. С. Сотов; Федеральное агентство по образованию, ГОУ ВПО Воронежская государственная лесотехническая академия. - Воронеж, 2010. - 9 с. : ил. - Библиогр.:
с. 9. - Рус. - Деп. в ВИНИТИ РАН 02.08.2010 №481-В2010.
Статьи и материалы конференций 13. Соболев, C.C. Динамическое форматирование данных в распределенных информационно-управляющих системах [Текст] / C.C. Соболев, Л.С. Сотов, В.Н. Харин // Материалы Международной научной конференции Проблемы управления, передачи и обработки информации (АТМ-ТКИ-50) СГТУ 16-18 сентября 2009 г. - 2 с.
14. Sobolew, S.S. Anwendung der Datenlagertechnologien fur die Sammlung and Analyse des Datenverkehrs von Korporationsnetzen [Текст] / S.S. Sobolew, N.W. Tatarintsewa // Молодежь и наука: реальность и будущее: Материалы III Международной научно-практической конференции: в 6 томах. - Невинномыск: НИУЭП, 2010. - Том V. Естественные и прикладные науки. - С. 413-414. - Яз. нем.
15. Соболев, С.С. Устройство функционального генератора перестановок [Текст] / С.С. Соболев, Л.С. Сотов, В.Н. Харин // Моделирование систем и процессов. - 2011.
Ц №1-2. - С. 59-64.
16. Соболев, С.С. Методика, модели и алгоритмы проектирования устройств генерации комбинаторных перестановок [Текст] / С.С. Соболев, В.К. Зольников // Моделирование систем и процессов. - 2011. - №4. - С. 23-29.
17. Соболев, С.С. Маршрут проектирования акселераторов генерации комбинаторных перестановок [Текст] / С.С. Соболев, В.К. Зольников // Математическое моделирование в технике и технологии: материалы Всероссийской конференции с элементами научной школы для молодежи. - Воронеж: ИПЦ Научная книга, 2011. - С. 286-291.
18. Соболев, С.С. RTL-модель генератора комбинаторного беспорядка [Текст] / С.С. Соболев // Современные проблемы гуманитарных и естественных наук: Материалы VIII Международной научно-практической конференции 26-27 сентября 2011 г.
Том 1. - Москва, 2011. - С. 62-67.
19. Соболев, С.С. Генератор перестановок на основе управляемого циклического сдвига / С.С. Соболев // Моделирование систем и процессов. - 2012. - №1. - С.70-75.
20. Соболев, С.С. Методика проектирования специализированных устройств генерации перестановок / С.С. Соболев // Моделирование систем и процессов. - 2012. - №1. - С.75-80.
Просим Ваши отзывы на автореферат в двух экземплярах с подписями, заверенными гербовой печатью, направлять по адресу: 394087, г. Воронеж, ул.Тимирязева, 8, ВГЛТА, ученому секретарю.
Тел / Факс (4732)-53-67-05.
Соболев Сергей Сергеевич Автоматизация проектирования специализированных устройств генерации полных комбинаторных перестановок элементов символьной строки Автореферат диссертации на соискание ученой степени кандидата технических наук Подп. в печать 26 марта 2012 г. Формат 6084 1/18. Обьем 1 п.л. Заказ № 3Тираж 100 экз. УОП ВГЛТА 394087, г. Воронеж, ул. Тимирязева, 8.
Авторефераты по всем темам >>
Авторефераты по разным специальностям