автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Методы синтеза устройств вычислительной техники на основе нелинейных полиномиальных функций над конечным полем

На правах рукописи

Шалагин Сергей Викторович

МЕТОДЫ СИНТЕЗА УСТРОЙСТВ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ НА ОСНОВЕ НЕЛИНЕЙНЫХ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ НАД КОНЕЧНЫМ ПОЛЕМ

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

Автореферат

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

005534289

Казань-2013

з ОКТ 2013

005534289

Работа выполнена в ФГБОУ ВПО «Казанский национальный исследовательский технический университет им. А.Н. Туполева — КАИ».

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

Захаров Вячеслав Михайлович

Официальные оппоненты: Нсмагилов Ильяс Идрнсович

доктор технических наук, профессор, ФГАОУ ВПО «Казанский (Приволжский) федеральный университет», заведующий кафедрой

Кирьянов Борис Федорович

доктор технических наук, профессор, ФГБОУ ВПО «Новгородский государственный университет имени Ярослава мудрого», профессор

Крашенинников Виктор Ростиславович

доктор технических наук, профессор ФГБОУ ВПО «Ульяновский государственный технический университет», заведующий кафедрой

Ведущая организация - ФГБОУ ВПО «МАТИ - Российский

государственный технологический университет им. К.Э.Цнолковского», г. Москва

Защита состоится « 2.Т » аг.уд^д 20 ¡3 г. в 15" часов на заседании диссертационного совета Д 212.277.01 при Ульяновском государственном техническом университете (УлГТУ) по адресу: 432027, г. Ульяновск, ул. Северный Венец, 32 (ауд. 211, Главный корпус).

Автореферат разослан « £ I » 20[^г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор —

Смирнов Виталий Иванович

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

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

Известны результаты по представлению генераторов массивов равномерно распределенных случайных и псевдослучайных чисел большой размерности на основе полиномиальных функций над конечным полем (Алферов А.П., Винокуров В.И., Ганнтмахер В.Е., Гилл А., Кирьянов Б.Ф. Иванов М.А., Кузнецов В.М., Песошин В.А., Шнайер Б. и др.). Существует подход к представлению генераторов дискретных стохастических процессов (ДСП) из классов однородных и неоднородных цепей Маркова (ЦМ) и их функций, на основе вероятностных автоматов (ВА), в общем случае - нелинейных систем. Такие генераторы находят применение в таких областях как построение вероятностных моделей алгоритмов для решения задач защиты информации, статистическое моделирование, распознавание образов, кодирование и декодирование информации, техническая диагностика цифровых устройств, обработки сигналов в системах связи и управления. Поэтому исследование вопросов синтеза генераторов ДСП данного класса имеет важное теоретическое и прикладное значение. Указанный подход, определенный как автоматный, отражен в многочисленных публикациях (Аблаев Ф.М., Альпин Ю.А., Баканович Э.А., Бусленко Н.П., Бухара-ев Р.Г., Гилл А., Гиоргадзэ А.Х., Гладкий B.C., Глова В.И., Захаров В.М., Кемени Дж., Левин Б.Р., Кирьянов Б.Ф., Лоренц A.A., Нурмеев H.H., Нурутдинов Ш.Р., Песошин В.А., Полляк Ю.Г., Поспелов Д.А., Салимов Ф.И., Столов Е.Л., Хамитов Г.П., Ченцов В.М., Чирков М.К., Шварц В., Яковлев В.В., Paz А. и др.). Вместе с тем, реализация автоматных функций на ПЛИС/FPGA без адаптации под архитектуру ПЛИС/FPGA сопряжена с большими дополнительными затратами аппаратных ресурсов из-за неполного задействования однотипных конфигурируемых элементов ПЛИС/FPGA, реализующих любую булеву функцию (БФ) от R< 5, переменных. Решение задачи адаптации более эффективно для системы БФ, пересечение по аргументам между которыми будет минимальным. Известные подходы, основанные на использовании аппарата алгебры логики, не ориентированы на базис ПЛИС/FPGA, где R< 5, а декомпозиция Шеннона является нерациональной по оценкам временной и аппаратной сложности, т.к. схема имеет древовидную структуру (Баркалов A.A. и др.).

Представление генераторов ДСП класса марковских и их функций на основе однотипных операций над конечным полем позволяет производить распределенные, непересекающиеся по аргументам вычисления, что повышает эффективность реализации потоковых преобразований над «-разрядными двоичными векторами. Задача определения генераторов простых однородных ЦМ в базисе нелинейных полиномиальных функций (НПФ) над полем Галуа вида GF(2"), впервые решена в 1999-2001 гг. (Захаров В.М., Нурутдинов Ш.Р., Шалагин C.B.). Затем данный подход был распространен (2002-2005) на генераторы однородных а-сложных ЦМ и их детерминированных и стохастических функций, а также на генераторы неоднородных ЦМ (Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B., Эминов Б.Ф.). В диссертации докт. физ.-мат. наук Нурутдинова Ш.Р. (2005) дано развитие конечно-автоматных преобразований на базе нелинейных полиномиальных функций от двух переменных в рамках исследования проблемы моделирования автоматов различ-

ных видов (комбинационных схем, детерминированных и вероятностных автоматов, цепей Маркова) полиномами над полем Галуа вида GF(2"). Решена задача уменьшения количества ненулевых коэффициентов НПФ путем доопределения неопределенных значений функции на заданных наборах (Нурутдинов Ш.Р., Николаев А.Г., 2005).

Развитие теоретических основ представления ВА на основе операций в конечных полях над потоками дискретных случайных величин открывает возможность для разработки эффективных методов синтеза на ПЛИС/FPGA генераторов ДСП класса марковских и их функций на основе распределенного, непересекающегося по аргументам и адаптированного под архитектуру ПЛИС/FPGA вычисления значений НПФ, определенных над конечным полем.

Известен аппарат теоретико-полиномиальных преобразований (ТПП) - дискретных преобразований, определенных на основе теории полиномиальных вычетов, ориентированный на задачи анализа и синтеза динамических систем, описываемых вещественными числами (Крот A.M., Минервина Е.Б. и др.). Частные случаи ТПП - широко применяемые на практике дискретные преобразования Фурье (ДПФ) и Хартли (ДПХ), а также алгоритмы цифровой фильтрации сигналов. В частности, получил развитие подход к синтезу устройств вычислительной техники (ВТ) для определенных алгоритмов цифровой обработки сигналов (ЦОС) - ДПФ и цифровых фильтров, на основе системы остаточных классов, обеспечивающий повышение скорости выполнения отдельных операций на уровне реализации на ПЛИС класса FPGA (Акушский И.Я., Галанина H.A., Лебедев Е.К., Юдицкий Д.М. и др.). Дискретные функции Уолша как подкласс ТПП применимы в автоматизированных системах управления, в частности, для сжатия цифровых изображений (Исмагилов И.И. и др.) Однако, вопросы адаптации широкого класса устройств ЦОС, описываемых на основе нелинейных полиномиальных преобразований над конечным полем, под распределенную архитектуру ПЛИС/FPGA, исследованы не достаточно.

Данные обстоятельства определяют предпосылки к созданию общего метода синтеза при использовании однотипных специализированных цифровых вычислительных устройств, ориентированных на архитектуру ПЛИС/FPGA и описываемых НПФ над конечным полем, для: 1) генераторов дискретных стохастических процессов класса марковских и их функций; 2) устройств ВТ, выполняющих ЦОС. Для решения задачи синтеза (или создания прототипов) таких классов устройств ВТ как «система на кристалле», встраиваемые и портативные системы, широкое распространение получили IP-ядра (англ. Intellectual Property) - готовые блоки, применяемые для проектирования микросхем и представленные на уровне абстрактного описания, на функциональном и на физическом уровнях. При ограничениях на быстродействие и размер занимаемой площади микросхемы, IP-ядра позволяют существенно ускорить процесс синтеза устройств ВТ на микросхемах, в том числе, на ПЛИС/FPGA. При решении задач синтеза устройств ЦОС, использование подходов на базе IP-ядер позволяет синтезировать на ПЛИС цифровые сигнальные процессоры (англ. DSP, digital signal processor) как на алгоритмическом и программном уровнях, при использовании языка VHDL, так и на физическом уровне, на базе спец. DSP, встроенных в кристалл ПЛИС - XtremeDSP, PicoBlaze, MicroBlaze и т.п. (Зотов В.Ю., Шагурин И.И., B.Afra, S.Y.Kulkarni, P.Moakes, D.Pellerin, E.Young и др.). Вместе с тем, вопросы синтеза цифровых устройств, выполняющих нелинейные полиномиальные преобразования, в конечных полях на ПЛИС/FPGA при использовании IP-ядер, изучены не достаточно.

Для решения вычислительно трудоемких задач генерирования и обработки массивов данных большой размерности применимы РВС ПА. В настоящее время созданы РВС ПА различного назначения, выполненные при использовании унифицированных базовых модулей - многопроцессорных реконфигурируемых вычислителей на основе ПЛИС/FPGA (Каляев И.А., Левин И.И., Макаревич О.Б., Семерников Е.А., Шмойлов В.И. и др.). РВС ПА позволяют реализовать различные устройства ВТ, реконфигурируемые в реальном времени, что находит применение для таких областей, как символьная обработка информации,

защита компьютерных сетей, управление в реальном масштабе времени объектами энергетики, летательными и космическими аппаратами и т. п. В данной связи перспективной является задача синтеза устройств как для генерирования дискретных стохастических процессов класса марковских и их функций, так и для ЦОС, на РВС ПА при использовании однотипных IP-ядер, описываемых на основе нелинейных полиномиальных преобразований над конечным полем. В соответствии с требованиями, предъявляемыми к синтезируемым на РВС ПА устройствам по быстродействию и количеству задействованных процессорных элементов, актуальна задача адаптации указанных IP-ядер под архитектуру ПЛИС/FPGA.

Известно представление дискретных детерминированных нелинейных функций (ДДНФ) вида y/(xt,...,хт) = у, где x¡,...,xm,y - «-разрядные двоичные числа, на основе НПФ над GF(2") на абстрактном уровне (Лидл Р., Нидеррайтер Г. 1988). В ряде работ (Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин С.В. и др.) исследовано применение частных случаев НПФ, /и = 1,2, для решения задач синтеза генераторов дискретных стохастических процессов (ДСП) класса марковских и их функций. Теоретически обоснован алгоритм синтеза произвольной булевой функции (БФ) на основе НПФ над GF(2) - полиномов Жегалкина И.И. (Чебурахин И.Ф.). В настоящее время существуют микросхемы ПЛИС/FPGA, количество реконфигурируемых элементов внутри которых позволяет реализовать цифровые устройства для вычисления произвольной БФ от 20-ти переменных как IP-ядро. Вместе с тем, вопросы синтеза устройств для вычисления значения y/(x¡,...,xm), где т - произвольное, на основе системы НПФ над полем Галуа изучены не достаточно. Данное обстоятельство актуализирует исследование задач синтеза устройств ВТ для ДДНФ на основе однотипных IP-ядер, вычисляющих заданную НПФ и ориентированных на архитектуру ПЛИС/FPGA.

Для решения задачи синтеза устройств ВТ на ПЛИС/FPGA применимы однотипные функциональные модули (ФМ), описываемые нелинейными полиномиальныеми преобразованиями над конечным полем. Известно, что отдельные операции, в частности, операции умножения элементов поля вида GF( 2") и GF((2k)'), п = к-г, (обозначим их О У/ GF(2") и Oy/GF((2*)'), соответственно) допускают организацию распараллеливания вычислений и потоковой обработки данных (Алексеев В.Б., Лидр Р., Ниддеррайтер Г., Нурутдинов Ш.Р., Сюрин В.Н. и др.). Решены частные задачи синтеза ФМ, выполняющих ОУ I GF(2") и Oy/GF((2f)4) на ПЛИС/FPGA (Захаров В.М., Нурутдинов Ш.Р., Столов Е.Л., Шалагин С.В., Fleischemann Р., Orlando G., Рааг С., Р.Soria-Rodrigues и др.). Однако, в общем случае, вопросы, связанные с синтезом спец. ФМ, выполняющих О У/ GF(2") и п = к ■ г, на основе распределенных вычислений, исследованы не достаточно. При аппаратной реализации вычислений в конечных полях, важной задачей является синтез функциональных модулей операции вычисления остатка по заданному модулю, отличного от степени числа два, над конечным полем (далее - ОВО). Однако, вопросы, связанные с синтезом функциональных модулей ОВО на основе конвейерных вычислений в конечном поле, изучены не достаточно. В данной связи, актуальна задача исследования методов синтеза модулей, определяемых как IP-ядра, ориентированных на архитектуру ПЛИС/FPGA, и реализующих как ОУ/ GF(2"), ОУ/ GF((2l)'), п = к ■ г , так и ОВО.

В результате, актуально создание и исследование общего метода синтеза устройств ВТ, ориентированных на архитектуру ПЛИС/FPGA, в трех направлениях: 1) разработка новых эффективных методов синтеза широкого класса устройств ВТ на основе нелинейных полиномиальных преобразований над конечным полем; 2) расширение класса процессов, представляемых нелинейными полиномиальными преобразованиями; 3) повышение эффективности методов синтеза устройств ВТ для генерирования дискретных стохастических

процессов и цифровой обработки сигналов на ПЛИС/FPGA при использовании однотипных устройств и модулей, представляемых как IP-ядра.

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

Предмет исследования - методы синтеза генераторов дискретных стохастических процессов класса марковских и их функций и устройств ВТ для выполнения теоретико-полиномиальных преобразований на ПЛИС/FPGA и распределенных вычислительных системах с программируемой архитектурой, повышающие эффективность генерирования и обработки массивов цифровых данных на основе нелинейных полиномиальных функций, определенных над конечным полем.

Цель диссертационной работы - разработка общего метода для структурного, алгоритмического и функционального синтеза генераторов дискретных стохастических процессов класса марковских и их функций и устройств ВТ для выполнения теоретико-полиномиальных преобразований, повышающего эффективность реализации данных генераторов и устройств на ПЛИС/FPGA за счет применения нелинейных полиномиальных параллельных преобразований над потоками чисел в конечных полях.

Научная проблема сформулирована как разработка методов синтеза на абстрактном, структурном и функциональном уровнях устройств ВТ для обработки потоков чисел, описываемых нелинейными полиномиальными функциями над конечным полем и реализуемых в однородных вычислительных структурах по технологии ПЛИС/FPGA.

Для достижения поставленной цели диссертационной работы и разрешения научной проблемы сформулированы следующие основные задачи:

• разработка теоретических основ для общего метода структурного и функционального синтеза генераторов дискретных стохастических процессов класса марковских и их функций в базисе НПФ над конечным полем;

• разработка теоретических основ для метода синтеза цифровых вычислительных устройств, структурно ориентированных на архитектуру ПЛИС/FPGA и реализующих дискретную детерминированную нелинейную функцию общего вида на основе нелинейной полиномиальной функции или системы НПФ от многих переменных, определенных над полем Галуа;

• разработка методов алгоритмического синтеза функциональных модулей, реализующих операции умножения над элементами полей вида GF(2") и GF((2k)'), п = к г, и операцию вычисления остатка от деления по заданному модулю в конечном поле, на основе параллельных и конвейерных вычислений, выполняемых на архитектуре ПЛИС/FPGA;

• получение оценок временной и аппаратной сложности для цифровых вычислительных устройств и для функциональных модулей в базисе ПЛИС/FPGA путем проведения компьютерного моделирования разработанных устройств и модулей при использовании спец. САПР ISE 13.4 - Foundation (Xilinx Corp.) и Quartus II v. 9.0 (Altera Corp.);

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

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

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

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

Научная новизна полученных результатов. Работа является завершенным исследованием проблемы по разработке методов синтеза на уровне абстрактного описания, на структурном и на функциональном (в архитектуре ПЛИС/РРОЛ) уровнях генераторов дискретных стохастических процессов класса марковских и их функций, на основе предложенного принципа суперпозиции НПФ над полем Галуа, и устройств вычислительной техники для выполнения теоретико-полиномиальных преобразований.

1. Доказаны теоремы, обосновывающие предложенный в работе общий метод синтеза генераторов ДСП класса марковских и их функций: однородных цепей Маркова, их детерминированных и стохастических функций и а-сложных ЦМ, на основе введенного понятия «полиномиальная модель цепи Маркова» и реализации нелинейных полиномиальных преобразований над полями Галуа на основе предложенного принципа суперпозиции НПФ, а также систем НПФ от многих переменных. Определены структурные схемы генераторов неоднородных ЦМ и их функций, детерминированных и стохастических, на основе систем НПФ от многих переменных, определенных над полем Галуа, а также генераторов дискретных случайных величин (ДСВ) с заданным законом распределения на основе НПФ от т переменных над полем Галуа, и т генераторов равномерно распределенных ДСВ, что позволяет синтезировать указанные генераторы на распределенной вычислительной системе с программируемой архитектурой, элементами которой являются ПЛИС/БРСА.

2. Доказаны теоремы, обосновывающие предложенный метод структурного синтеза цифровых устройств для вычисления значения дискретной детерминированной нелинейной функции общего вида от т /7-разрядных переменных над полями Галуа на основе представления указанной ДДНФ при использовании системы из / НПФ от т -1 переменных над элементами полей Галуа вида С1'(2к), п = 1-к. Определены структурные схемы вычисления значения указанной ДДНФ - параллельная, систолическая, последовательностная и па-раллельно-последовательностная, представленные на структурном уровне при использовании НПФ над СР(2") и альтернативные по оценкам сложности.

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

• выполнения ТПП над потоками чисел (на примере ДПФ, ДПХ и цифровых фильтров с импульсной характеристикой конечной длительности (КИХ-фильтров)) при использовании системы НПФ от многих переменных согласно предложенному методу алгоритмического синтеза, причем каждая НПФ определена над полем Галуа и значения каждой НПФ системы вычисляются параллельно;

• расчета дискретной модели отображения и варьирования состояния квантово-механической системы, включающей N базисных состояний - КМС(Л'), а также ее частных случаев: для N=2 и Л—4 на основе параллельного выполнения операций умножения элементов СР(2") или С^((2*)г), п = г-к,

что позволяет синтезировать указанные устройства на распределенной вычислительной системе с программируемой архитектурой, элементами которой являются ПЛИС/ТРОА.

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

немного поля за счет применения принципов распределенных вычислений. При этом операция умножения - О У/ GF(2"), производится на основе операций над GF(2), О У/ GF((2ky) - на основе операций над полем вида GF(2l), n = rk, а операция вычисления остатка по заданному простому модулю - на основе однотипных операций над целыми числами, выполняемых параллельно внутри каждой из ступеней конвейера. Доказаны утверждения, обосновывающие оценки сложности разработанных алгоритмов.

5. Предложена методика оценки степени соответствия ФМ, описываемых как IP-ядра и выполняющих операции над конечным полем, архитектуре ПЛИС/FPGA, которая позволяет выбрать одну из функциональных схем, описывающую данный модуль и наиболее приближенную к оптимальной по предложенным критериям. Результаты поддержаны грантами РФФИ - № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей», 03-01-00769 «Сложностные свойства классических и квантовых вычислений», 09-01-97004-Р-Поволжье 01 «Вычислительные возможности классических и квантовых моделей вычислений с ограничениями», ^ по проекту № 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», Практическая значимость работы в том, что предложенные теоретические основы и общий метод являются базовыми для решения задач

• анализа и синтеза генераторов ДСП класса марковских и их функций в базисе НПФ над полем GF(2"),

• синтеза устройств для вычисления теоретико-полиномиальных преобразований (на примере ДПФ, ДПХ и КИХ-фильтров).

Указанные генераторы и устройства, реализуемые на РВС ПА при использовании однотипных IP-ядер, позволяют с высокой скоростью производить и обрабатывать массивы цифровых данных большой размерности. Общий метод синтеза на ПЛИС/FPGA устройств, реализующих генераторы ДСП указанного класса и заданные алгоритмы ЦОС на основе однотипных IP-ядер, позволяет варьировать характеристики генерируемых и/или обрабатываемых последовательностей чисел за время, сопоставимое со временем вычисления значений этих чисел, путем изменения коэффициентов указанных НПФ, а также позволяет увеличивать их быстродействие за счет того, что указанные устройства адаптированы под архитектуру ПЛИС/FPGA.

Предложенные теоретические основы и общий метод синтеза обеспечивают: повышение скорости выполнения операции вычисления остатка по заданному модулю для потока чисел (получен патент [19]); повышение эффективности процесса разработки схемотехнических решений, позволяющих осуществлять распараллеливание процесса вычисления широкого класса дискретных преобразований цифровой информации, поддерживаемых специализированной прикладной программой (Свид. о гос. регистрации программы для ЭВМ № 2011610812 РФ. Вычисление коэффициентов многочлена над полем Галуа вида GF(2)/ Шалагин C.B.; опубл. 20.06.2011), а также решение задач:

1) синтеза генераторов дискретных стохастических процессов класса марковских и их функций на основе однотипных IP-ядер, реализуемых на ПЛИС/FPGA;

2) анализа семейства генераторов ЦМ на ПЛИС/FPGA путем отбора типичных представителей и идентификации заданных подклассов объектов данного семейства;

3) синтеза устройств анализа и фильтрации цифровых сигналов на РВС ПА.

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

моделирования, при использовании специализированных САПР ПЛИС класса FPGA и результатами исследований других авторов.

Результаты использованы в НИР за 2001 - 2011гг. по трем грантам РФФИ - № 99-0100163, № 03-01-00769 и № 09-01-97004-Р-Поволжье 01, по проекту № 015-04-01-52 программы «Университеты России», в ОАО «Научно-производственное объединение «Радиоэлектроника» имени В.И. Шимко», г. Казань (далее - НПО «Радиоэлектроника»), в ОАО «Научно-производственное предприятие «Межотраслевой центр эргономических исследований и разработок», г. Тверь (далее — НПП МЦЭИР), в ООО «НПП «Измерительные технологии», г. Саров (далее - НПП «Измерительные технологии») и в учебном процессе Военной академии воздушно-космической обороны им. Маршала Советского Союза Г.К.Жукова, г. Тверь (далее - ВА ВКО) и Института технической кибернетики и информатики ФГБОУ ВПО «Казанский национальный исследовательский технический университет им. А.Н. Туполсва-КАИ» (далее - КНИТУ-КАИ). По тематике, представленной в диссертации, опубликовано четыре учебно-методических пособия, два из которых - с грифом УМО.

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

1. Теоретические основы общего метода синтеза генераторов дискретных стохастических процессов класса марковских и их функций, и устройств вычислительной техники, выполняющих теоретико-полиномиальные преобразования, (на примере дискретных преобразований Фурье, Хартли и КИХ-фильтров) при использовании однотипных 1Р-ядер, позволяющих выполнять распределенные вычисления над конечным полем.

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

3. Метод синтеза на алгоритмическом уровне функциональных модулей в базисе ПЛИС/FPGA, позволяющих выполнить в конечных полях при использовании распределенных вычислений операции: умножения элементов поля Галуа, его расширений и вычисления остатка по заданному модулю, отличного от степени числа два.

4. Методики, позволяющие при использовании методов многопараметрического анализа определять подмножество типичных представителей семейства генераторов ДСП класса однородных цепей Маркова, синтезируемых на РВС ПА, и идентифицировать (с определенной доверительной вероятностью) принадлежность генератора ДСП класса однородных ЦМ к одному из априори заданных подклассов путем анализа производимой им последовательности состояний конечной длины.

5. Методика оценки степени соответствия ЦВУ и ФМ архитектуре ПЛИС/FPGA на основе разработанных критериев.

Апробация работы. Основные результаты работы были доложены и обсуждались на конференциях и семинарах международного уровня: «Дискретная математика и её приложения» (Москва, 2001, 2007), «Проблемы теоретической кибернетики» (Москва, 2002, Пенза, 2005), «Новые информационные технологии и системы» (Пенза, 2002), «Дискретные модели в теории управляющих систем» (Дубна, 2003), «Новая геометрия природы» (Казань, 2003), «Инфокоммуникационные технологии глобального информационного общества» (Казань, 2003, 2006-2009), «Инновационное образование в техническом университете» (Казань, 2004), «Высокопроизводительные параллельные вычисления на кластерных системах» (Казань, 2008), «Проблемы техники и технологий телекоммуникации» (Казань, 2008, 2011), «Дискретные модели в теории управляющих систем» (Москва, 2009), всероссийского уровня: «Теория сеточных методов для нелинейных краевых задач» (Казань, 2000, 2002 и 2004), «Методы и средства обработки информации» (Москва, 2003, 2005, 2009), «Наука и профессиональная деятельность» (Казань, 2008), «Инновации РАН 2010» (Казань, 2010), «Информационные технологии в системе экономической безопасности России и ее

регионов» (Казань, 2010), «Проблемы и перспективы развития информационных технологий» (Казань, 2012), регионального уровня: «Методы моделирования» при Академии наук РТ (Казань, 2001-2009), а также Итоговой науч. конф. КФУ (КГУ) (Казань, 2001); ряде семинаров каф. Теоретической кибернетики КФУ (Казань, 2001-2007), каф. Компьютерных систем КНИТУ-КАИ (Казань, 2001 - 2013), Института информатики Академии наук РТ (Казань, 2008-2010) и др.

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

Личный вклад автора. Выносимые на защиту результаты получены автором лично. Вклад автора в ряд совместных работ: в [2,4, 23, 24, 28, 29, 45] - методы синтеза устройств на структурном уровне, в [1, 28, 34, 35] - методы синтеза устройств на функциональном уровне, в [3, 22, 30] - получение и анализ результатов экспериментальных данных на уровне методов, в [17] - идея создания методики анализа множества объектов на основе характеризующих их признаков, в [25, 31] - метод синтеза представленных устройств, в [10, 12, 13, 40] - основная идея, в [39] - синтез предложенных устройств на структурном уровне, в [14, 15, 18, 19] - определение предложенных устройств на функциональном уровне, а в [18, 44] - разработка метода синтеза различных устройств ВТ на РВС ПА при использовании однотипных цифровых вычислительных устройств, выполняющих вычисления в конечных полях.

Структура и объем работы: введение, шесть глав, заключение и список используемых источников, включающий 366 наименований. Объем работы - 295 стр., в т.ч., 267 стр. основного текста. Работа включает 64 рисунка и 21-ну таблицу.

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

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

Первая глава содержит обзор методов синтеза устройств ВТ, основанных на применении полиномиальных преобразований, а также основные понятия и определения, обеспечивающие разработку теоретических основ и общего метода синтеза устройств ВТ, выполняющих нелинейные полиномиальные преобразования над потоками чисел в конечных полях, путем организации распределенных вычислений при использовании однотипных цифровых устройств, адаптированных под архитектуру ПЛИС/РРСА. Пусть вм = 0^(2")- поле Галуа. Введём в рассмотрение отображение элементов данного поля вида:

(1)

Любое отображение конечного поля в себя вида (1) можно задать полиномиальной функцией/над этим полем (Лидл Р., Нидеррайтер Г., 1988):

/(<?,.->О = Х^-о-Е-Л' = .....ю

получение матрицы коэффициентов НПФ (2) /1 = {а,,1т\., у1. производится путем последовательного решения системы уравнений:

Ут{\ ¡2..... 0=сМ\ к, а ^Чч. *,0=*,....

.... /„.,, *) = ...../„.,, *), А = V™, /, = О, Н-,..., «„ = О, V/,

где С"1 - матрица, определенная над полем , размерности 2" х2". Существенно уменьшить количество операций, требуемых для вычисления НПФ вида (2), позволяет наличие нулевых коэффициентов, получаемых путем решения системы (3) при наличии неопреде-

ленных значений в отображении вида (1) (Нурутдинов Ш.Р., Николаев А.Г., 2005). Для решения задачи синтеза генераторов конечных простых однородных ЦМ [2, 23] и их функций [4, 24, 31,34] применимы частные случаи НПФ вида (2) от одной и от двух переменных:

= Е,1оа^ > Ч е - (4)

/(?! > ) = Х1-0 Х"=0 ^ ' ' Я > 6 ■ * = Т -1 ■ (5)

На основе концептуальной модели [43] предложен общий метод синтеза, позволяющий синтезировать генераторы дискретных стохастических процессов класса марковских и их функций при использовании однотипных цифровых устройств, выполняющих вычисление дискретных детерминированных нелинейных функций, заданных произвольным отображением вида (1), на основе НПФ и/или их систем, а также функциональных модулей, выполняющих операции умножения элементов GF(2"), GF((2*)'), где п = к г, и операции вычисления остатка в кольце и в конечном поле. Данный подход на основе общего метода синтеза распространяем на устройства вычисления теоретико-полиномиальных преобразований и дискретной модели отображения/варьирования состояния квантово-механической системы, включающей N базисных состояний, и ее частных случаев.

Предложеный общий метод синтеза (ОМС) генераторов ДСП класса марковских и их функций представлен следующими этапами. 1) определение и заданиие требуемого закона ДСП на основе одной или системы эргодических стохастических матриц (ЭСМ). 2) построение полиномиальной модели генератора (ПМГ) ДСП класса марковских и их функций на основе принципа суперпозиции полиномиальных функций — представление каждой ЭСМ (в общем случае - каждого элемента системы ЭСМ) суперпозицией НПФ над полем Галуа, включающей полиномиальную модель генератора дискретной случайной величины (ДСВ) и НПФ вида (2) от т переменных, т= 1, 2, ... , над конечным полем, представляющую произвольное отображение вида (1). 3) структурный синтез ПМГ в заданном базисе однотипных цифровых устройств, анализ сложности с целью построения структурных схем ПМГ, приближенных к оптимальным по заданным критериям. 4) алгоритмический и функциональный синтез цифровых вычислительных устройств и функциональных модулей для выполнения операций в конечном поле, в базисе ПЛИС/ГРвА, анализ сложности с целью синтеза устройств и модулей, приближенных к оптимальным по предложенным в работе критериям. 5) отображение схем, полученных на этапах 3) и 4), в архитектуру ПЛИС/ТРОА.

В последующих главах приведены результаты по детализации этапов схемы ОМС и по распространению данной схемы на задачи синтеза устройств ЦОС.

Во второй главе представлены результаты по разработке и выполнению этапов 1) и 2) общего метода синтеза генераторов ДСП в виде разработанных методов синтеза генераторов дискретных стохастических процессов класса марковских и их функций над полем GF(2"). Показана возможность представления генераторов цепей Маркова [2, 23] и их функций [4, 24, 31, 34, 45] при использовании предложенного принципа суперпозиции НПФ, включающей полиномиальную модель генератора ДСВ, определенного на основе системы некоррелированных генераторов равномерно распределенных псевдослучайных чисел [38], и (в общем случае) суперпозицию НПФ вида (4) и/или (5) над элементами поля Галуа, каждая из которых реализует заданное отображение вида (1) [42]. Предложенный принцип суперпозиции НПФ, как совокупность сформулированных теорем, обосновывает возможность синтеза высокоскоростных генераторов ДСП указанных классов, в архитектуре ПЛИС/ГРвА, с применением распределенных вычислений в конечном поле [16].

В п. 2.1 представлены результаты по разработке и выполнению этапов 1) и 2) ОМС для решения задач синтеза и анализа генераторов однородных ЦМ вида

,„*„). (6)

где 5 = } - конечное множество ее состояний, Р{т) - эргодическая стохастическая

матрица размера тхт, л0 = {л"(}, / = 1, т - «-разрядный стохастический вектор, задающий начальное распределение вероятностей состояний.

Однородная ЦМ представима на основе автономного вероятностного автомата (ВА), определяемого системой:

Л(1) = (Д5,<У(*,*)), (7)

где $ - тот же объект, что и в (6), р - ДСВ, принимающая конечное число значений

/¿,,//2,...,//, на входе А(1) с вероятностями р,, р2,...,р,, = (р,, р2,..., р;) - стохастический вектор, 0 < р< 1, У' ; р, =1. - функция переходов, однозначно ставящая в соответ-

ствие паре (*,$) новое состояние 5'е5 и для которой множество значений {х,}=Х = 1 = 1,1, / <(т2 -т +1) (Поспелов Д.А., 1970). Рассмотрим предлагаемый метод реализации этапа 2) ОМС - метод полиномиального представления генератора однородной ЦМ на базе автономного ВА, определенного согласно (7), над С(11). Имеет место

Теорема 2.1.1 (синтеза) [2]. Для системы вида (6) можно вычислить дискретную случайную величину ¡X и полином /(х, ц) вида (5), 2"), минимальная степень которого определена из условия 2" —1 = г>тах(/и,/), /<(тг -т + \), с коэффициентами еСг/7^"), г,у = 0, г, и случайным начальным значением такие, что /{х,д) преобразует р в последовательность состояний заданной цепи Маркова.

ДСВ ¡л, в свою очередь, реализуема на основе НПФ g{z) вида (4) над , задаваемой отображением элементов множества значений «-разрядной дискретной случайной величины г, т. б7., распределенной по равновероятному закону, Щ = 2", во множество /<2", согласно (1) для /я = 1. Теорема 2.1.1 устанавливает возможность представления стохастической матрицы Р(т) суперпозицией двух НПФ вида (4) и (5). Согласно теореме 2.1.1, задание ЦМ в виде системы

(Я Дх, д), /(х, ;г0), (8)

эквивалентно заданию системы (6).

Определение 2.1 [2]. Систему (8) будем называть полиномиальной моделью конечной однородной цепи Маркова над полем Галуа - полиномиальной марковской моделью (ПММ).

Теорема 2.1.1 обосновывает метод синтеза генераторов однородных ЦМ вида (6) на базе ПММ вида (8), заданной путем представления ЭСМ вида РЫ) при использовании суперпозиции НПФ вида (4) и (5) над С(п), в соответствии с этапом 2) ОМС [2]: 1) представление ЭСМ линейной стохастической комбинацией простых матриц - Р(т) = У' . р,М, , где

р1 - элементы стохастического вектора Р, А/ - простые матрицы. 2) определение функции переходов конечного детерминированного автомата (КДА) - <5(х,5), и закона распределения ДСВ р, на основе полученной линейной комбинации. 3) представление р и 3{х,я) НПФ 5(г) и /(х, д) над С(л) вида (4) и (5), соответственно, где задание коэффициентов указанных НПФ производится согласно (3) на основе отображений вида (1) для от = 1, 2, соответственно. Схема генератора однородной ЦМ представлена на рис. 2.1.1, где модуль «£>» есть набор О-триггеров, составляющих регистр памяти.

/(■Г, <l)

D

ÍT

Для системы (8) справедлива теорема 2.1.2, обратная теореме 2.1.1, позволяющая решать задачу анализа ПММ - определение ЭСМ по заданной суперпозиции НПФ вида (4) и (5) [2].

Теорема 2.1.2 (анализа). Для заданного полинома f(x,q) вида (5), х, q, /(х, q) е GF(2"), с коэффициентами a:J е GF(2"), i,j = 0,r, r = 2"-1, с множеством {jca }, к = 1,1 значений переменной х и множеством {(/,}, t = \,m значений переменной q, для дискретной случайной величины р. с множеством значений {fik ¡ = {хк}, заданной вектором Р и для вектора я"0 последовательность вычисленных значений /(х, q) является реализацией простой однородной цепи Маркова вида (6), для которой S = {qt}, а элементы Pím), т =[{?,}|, однозначно определены Р и f(x,q).

Теорема 2.1.2 обосновывает метод определения ЭСМ Р(т) по заданным НПФ над G(„, - f(x, q) вида (5) и g(z) вида (4) [2]. 1) определение g(¡) — функции переходов КДА - S(x,s), на основе НПФ f(x,q) и |

закона распределения ДСВ fi на основе НПФ g(z), путем Рпс. 2.1.1. Схема генератора вычисления отображений вида (1) - <р2: G(n¡ xG„, —pea- однородной ЦМ

лизуемого f(x,q) и tp,:G(n) —»G(n), реализуемого g(z). 2) на основе ё(х,s) и ¡i определение множества простых матриц - {Д-/:}, / = 1, /, и стохастического вектора Р . 3) на основе {М,}, i = 1,1, н Р вычисление ЭСМ, определяющей (6), на основе линейной стохастической комбинации простых матриц - Р(т) = У' /> Л/ .

Генератор a-связной (а-сложной, а > 1) ЦМ, схема которого приведена на рис. 2.1.2, определяем на основе ЭСМ Ра размера d" x.d", где d" - число состояний данной цепи. На множестве состояний а-связной ЦМ Z" в соответствии с различающимися распределениями, представленными в матрице Ра, зададим разбиение вида

/,( -. Ч)

D

Г

8(4) D

g(5) D

Г)

А(х.у)

Рис. 2.1.2 Схема генератора «-сложной ЦМ у„у2,-,ук, У, =0, yi^jyJ=z при i,j = \,k, k<d". (9) Тогда ЭСМ Ра представима как разложение вида У..^ дМ(х,), где /, <(k-d — k +1) (Буха-

раев Р.Г., Захаров В.М., 1978). Справедлива

Теорема 2.1.3 [4]. Для а-связной цепи Маркова, а > 1, заданной стохастической матрицей Ра размера d" у-d" и разбиением над Z" вида (9), последовательность ее состояний представима последовательностью значений функции =ё(й)* fi{x>y) - суперпозицией трех полиномиальных функций над полем GF(2"), где 2" > тах(/г, /,,£/),

k<h<d°, а начальное состояние данной цепи определяется начальным значением переменной полинома q.

В п. 2.2 приведены результаты по разработке и выполнению этапов 1) и 2) ОМС для решения задач синтеза генераторов детерминированных и стохастических функций однородных ЦМ - {У,} и {Z,}, которые применимы на практике при решении широкого круга задач [4, 24, 34, 39, 41]. Схема генератора ДСП {У,} представлена на рис. 2.2. Метод синтеза указанных генераторов, представленных на основе НПФ вида (4) и (5), обоснован

рядом теорем [4, 39]. Разобьем множество 5 в системе (6) на непересекающиеся подмножества А1, Аг,..., Ак:

и?=, 4 = А, пА/ = О, при / . (10)

Теорема 2.2.1 [4]. Для цепи Маркова, заданной согласно (6), последовательность состояний процесса {У,}, заданного разбиением (9) на множестве 5, представима последовательностью значений функции (С2= £(<?)• /(*,#) - суперпозицией двух полиномиальных функций над полем ), минимальная степень которого удовлетворяет условию 2" >1,

где 1<{тг —т + \), ш = [51, а начальное значение д в /(х,ц) определяется распределением я0.

Пусть задано множество X, = (1, и /1(2/ я) - стохастическая функция, определяемая ЭСМ Р(2/1) размера тхс!, и имеющая вид: Рии) ={рв)т1^ = (Мг,/'5, ))„„,,> гдс Р,/> ; = 1,т, у' = 1 ,с1 определяет вероятность появления буквы гу при условии, что автономный ВА вида (7) находится в состоянии . Схема генератора ДСП {2представлена на рис. 2.2, ¡л' есть ДСВ, принимающая /, всевозможных значений переменной х', /, <(тс!-т +1). Имеет место

Теорема 2.2.2 [2]. Последовательность состояний процесса {2,}, заданного системой (10) и функцией //(г/.у), представима последовательностью значений функции у/г = /(х, у) - суперпозицией двух полиномиальных функций над полем С/7^"),

минимальная степень которого удовлетворяет условию 2" >тах(/,/,), где I <(тг —т +1),

Разложение ЭСМ Р(г/у)ы, участвующей в определении ДСП {21}, имеет вид Х'^Р.М«), где 1г<к-с1-к +1, а {Л/^,")},.^ определяет НПФ /2(х*,>') (рис. 2.2) [4]. Схема генератора ДСП {г,'} представлена на рис. 2.2, //" есть ДСВ, принимающая /2 всевозможных значений х". Справедливо

Следствие теоремы 2.2.2 [4]. Последовательность состояний процесса {!,}, заданного системой (10), разбиением (9) на множестве ¿'и функцией /¿(г/у), представима последовательностью значений функции =/1(х', д)* g(,q)^ /2{х", у)- суперпозицией трех полиномиальных функций над (7^(2"), где 2" > тах(/,/2).

На основе теорем, представленных в п. 2.2, и в соответсвии с этапом 2) общего метода синтеза предложен метод синтеза генераторов ДСП из классов {У,} и {2,} на основе суперпозиции НПФ вида (4) и (.5). [4, 24, 34, 41], включающий три этапа. 1) определение каждой из стохастических функций, представленных при использовании ЭСМ, на основе генератора дискретных случайных величин и КДА. 2) кодирование множеств входных и выходных переменных каждой из детерминированных функций, определяющих заданный ДСП, элементами С(п) с целью представления данных детерминированных функций на основе отображений вида (1). 3) определение многочленов вида (4) и/или (5) над С(п) на ос-

Генератор ЦМ

I)

т

о

/,(-*'. я)

в

О

МЛ у)

о

(7'\ і^гі

{г,}

Рис. 2.2. Схемы генераторов ДСП {Г; }. {2,} и

нове дискретных детерминированных нелинейных функций, заданных отображениями ви-да(1).

Представление генераторов ДСП из классов {У,} и {2,} на основе нелинейных полиномиальных преобразований над полем Галуа (рис. 2.2) позволяет получать элементы указанных последовательностей путем организации конвейерной обработки данных с сохранением промежуточных результатов, полученных при вычислении значений НПФ вида (4) и/или (5) [39]. При этом законы распределения ДСВ $ и р." заданы на основе НПФ и g"(z), каждая из которых определена над С(п) путем отображения элементов множества

2 во множества всевозможных значений переменных х' и х", соответственно.

В п. 2.3 приведены результаты по разработке и выполнению этапа 2) ОМС как метода синтеза генератора дискретных случайных величии с заданным законом распределения на основе системы, включающей генератор равномерно распределенных дискретных случайных величин (ГРДСВ) на п разрядов, и НПФ (от одной или от множества из т переменных) над полем Галуа. Метод синтеза генераторов ДСП, определенных в пп. 2.1 и 2.2, основан на описании их вероятностной и детерминированной частей на основе нелинейных полиномиальных преобразований над полем Галуа. Основу вероятностной части указанных генераторов составляет генератор дискретных случайных величин, метод синтеза которого описан в данном разделе [38].

С целью увеличения точности представления вероятности формирования значений ДСВ, требуется увеличивать количество разрядов чисел, снимаемых с выхода ГРДСВ - п. Следствие этого - увеличение сложности как ГРДСВ, так и НПФ вида (4) за счет увеличения размерности С(п) [33]. Предложенный в [38] метод, основан на распределенном представлении генератора ДСВ // как композиции т некоррелированных у-разрядных ГРДСВ Д, ..., Д, и НПФ от т переменных над Ом вида (2). При этом 2" > 2"'т и 2" > I, где / -количество значений /}. Схема данного генератора ДСВ приведена на рис. 2.3. [20].

Согласно [38], в качестве меры оценок временной и аппаратной сложности для т некоррелированных ГРДСВ на у разрядов, определены операции над полем Галуа вида С/<"(2), позволяющие вычислить произвольную булеву функцию от двух переменных (Ахо А. и др., 1979). Данные оценки ограничены сверху величинами ] 1о§2 v [ и - Схема генератора

шу(у- 1). Предложенный метод позволяет представить ДСВ

вероятности формирования значений ¡л с дискретностью, равной 2~™, что обеспечивает абсолютную погрешность представления указанных вероятностей е < 2"™"1, без увеличения разрядности чисел - v, формируемых ГРДСВ, п = т-v, (по сравнению с представлением генератора ДСВ ¡л системой из НПФ вида (4) над и ГРДСВ на п разрядов) [38].

В третьей главе приведены результаты по разработке и детализации этапа 3) ОМС в виде предложенных теоретических основ синтеза на структурном уровне устройств для вычисления значений дискретных детерминированных нелинейных функций (ДДНФ) на основе нелинейных полиномиальных преобразований над полем Галуа. Актуальность полученных результатов обоснована тем, что генераторы дискретных стохастических процессов класса марковских и их функций (пп. 2.1 - 2.3) в общем случае реализуемы в архитектуре ПЛИС/ТРОА на основе системы НПФ, определенных над полем Галуа [41, 43]. Снижение оценок временной сложности для схем устройств вычисления значений ДДНФ, реализованных на ПЛИСЛ'РОА как 1Р-ядер, влечет за собой повышение быстродествия устройств ВТ - как генерирующих элементы последовательностей из класса марковских и их функций, так и выполняющих ЦОС. В данной связи, определены как перспективные

следующие подходы к синтезу цифровых устройств вычисления ДЦНФ от т «-разрядных переменных:

• подход на основе системы из / многочленов от т ■ I переменных над полем Галуа вида GF(2*), п = к-1 [11,41];

• подход с использованием схем, позволяющих вычислить НПФ от многих переменных над С^(2"), альтернативных по оценкам временной и аппаратной сложности - параллельной, систолической и последовательностной [38].

В п. 3.1 дано представление структурных схем устройств для вычисления значений ДДНФ на основе операций над элементами поля Галуа вида С1у), в виде определений.

Устройства, позволяющие вычислить НПФ вида (2), представляющую заданную ДЦНФ от т переменных, реализуемы на основе схем, альтернативных по оценкам временной и аппаратной сложности, которые получены на основе количества операций над 0(„>: параллельной, систолической, последовательностной [38] и параллельно-последовательностной [46].

Определение 3.1.1. Параллельная схема есть схема вычисления значения НПФ вида (2) от т переменных над GF(2") путем параллельного вычисления значений слагаемых а, 1 <7,'1 и их поразрядного сложения по модулю два.

Определение 3.1.2. Систолическая схема есть схема вычисления значения НПФ вида (2) от т переменных над ОР(2" ) на базе выражения вида

, " = -1, (11)

согласно схеме Горнера: /(<71>-.<?„) =

значения которых вычисляются по схеме Горнера.

Определение 3.1.3. Последовательностная схема есть схема вычисления значения НПФ вида (2) от т переменных над 0^2"), путем последовательного выполнения операций вида а1+1</ + а1, / = 0,(^-1), над 6^(2") в выражении (11), вычисляемого по схеме Горнера с сохранением результатов выполнения данной операции.

На основе анализа достоинств и недостатков параллельной, систолической и последовательностной схем цифровых вычислительных устройств значений ДДНФ предложена параллельно-последователъностная схема (ППС) [46].

Определение 3.1.4. Параллельно-последовательная схема есть схема вычисления значения НПФ вида (2) от т переменных над путем последовательного выполнения групп из <1 операций над 2"), выполняемых параллельно, вида: а) в (2) для

¿е [2,м72], либо б) амд + а,, / = 0,(^-1), в (11) для <1> 1, НОД(и>,(^ + 1)) = 1.

Оценки временной и аппаратной сложности для ППС занимают промежуточное положение между соответствующими оценками для параллельной (вариант а)) и систолической (вариант б)) схем с одной стороны и последовательностной схемой с др. стороны [46]. Примем в качестве меры сложности операции над элементами С7*Х2). Тогда, согласно [38], для параллельной, систолической и последовательностной схем порядки оценок временной и аппаратной сложности равны, соответсвенно,

О+ + для л>1 и О\Р"г){тг -п ■2""), (12)

-1о§т) и ^(г"-п2), (13)

О(*о(2- .1оВи) и 0<5есУ). (14)

В п. 3.2 предложен метод синтеза устройств для вычисления ДДНФ от т переменных, представимой НПФ над Gtn) = GF(2"), на основе системы из I НПФ от т-l переменных каждая над полем G,t), п = к-1 [11, 42]. Определим частный случай НПФ вида (2), к = 2, отр=т-п!2 переменных над Gm В [43] показана возможность представления ДДНФ, заданной произвольным отображением вида (1), системой из п/2 полиномов вида:

выбранной из-за высокой степени соответствия ОУ/Gm базису ПЛИС/FPGA для большого

числа семейств: Virtex-4 (Xilinx, Inc), Stratix (Altera, Inc) и др.

С целью решения задачи синтеза устройств для вычисления значений дискретных детерминированных нелинейных функций от т переменных на основе системы НПФ вида

(15), обозначим: и(у(хх.....-О)" множество всевозможных значений ДДНФ у(хх,...,

l[xj) - множество всевозможных значений переменной Xj, У = 1, т, на входе ДДНФ і//(х,,...,хт). Сформулированы и доказаны теоремы [11], обосновывающие оценки сложности вычисления НПФ вида (2) от т переменных над элементами G(n), принадлежащего к классам А(к), к=\,п,

j = lm, (|/(х|)|є(2,',"1,2'',]> ..., I /(xm)| e(2<i-"',2I'-J) на основе системы НПФ вида (15). В качестве меры сложности принято количество операций над элементами GF{2). Определим НПФ вида (2) в виде:

y = y/(xt,...,xj, у,х„...хт є GF(2") (16)

Представив величины у и х1,...хт, определенные как л-разрядные векторы, на основе множества / ¿-разрядных векторов, п = к-1 - {У4,...,У"}, {дг(<'),...,t = 1,т, выражение

(16) определяется как система НПФ вида:

{у> ^¥р(4\...,хІ'\...,хі:\...,х^)}р, р = й, (17)

где У', х\р^ єGF(2k), t =1,т. Согласно (16) и (17), обоснована возможность представления НПФ вида (2) над GF(2") на основе системы полиномов над GF(2l). Справедлива

Теорема 3.2.1 [43]. Оценки временной и аппаратной сложности вычисления полиномиальной функции вида (2) от т переменных над GF{2"), на основе системы из I полиномиальных функций вида (2) над GF(2k) от m l переменных, принадлежащих к классам

Мр) и в№!>z = U, равны т, = max]log2X^f [ и q, — l).

соответственно.

Предлагаемый в данном пункте метод синтеза цифровых устройств для вычисления дискретной детерминированной нелинейной функции, принадлежащей классам А(п) и

В(с/,; ... ;dm), dj =п, j = \,т , на основе системы из I НПФ, включает три этапа [43]. 1) представление множества значений и т множеств значений переменных ДДНФ 1 к-разрядными векторами, п = к ■ 1. 2) определение I ДДНФ, принадлежащих классам А(к) и

B(dx\ ... ;dml), dj=k, j = 1, m l, на основе отображений (1) для т• I множеств элементов G(t) в одно множество элементов G(k). 3) вычисление коэффициентов для / НПФ от m l переменных каждая, определенных над G(l), которые соответствуют отображениям

вида (1), полученным на этапе 2).

Порядки оценок временной и аппаратной сложности цифровых устройств для вычисления ДДНФ, представленной системой НПФ вида (17) над G(2) на основе параллельной

реализации каждая, вычислены на основе операций над GF(2) и составляют О, (log2(m •«)) и Oq(m-n- /2), I — п!к, соответственно. Это определяет преимугцество данных устройств по порядкам оценок временной сложности в сравнении с оценками (12) - (14) для устройств, определенных на основе схем, представленных в п. 3.1: примерно в n-(m + log2n)/log2(m-n) раз для параллельной и примерно в (т■ 2" • log2m)/\og7(m■ п) раз -для систолической, соответственно [43].

В п. 3.3 предложены результаты по разработке и выполнению этапа 3) ОМС как метода синтеза генераторов неоднородных цепей Маркова (НЦМ) и их функций на основе цифровых устройств для вычисления ДДНФ [35, 41], определяемых на основе НПФ от многих переменных: как НПФ вида (2) над полем G(l0 [2, 4] (п. 3.1), так и системы многочленов вида (15) над G(1) (см. п. 3.2) [11, 43]. Метод является развитием подхода к представлению однородных ЦМ и их функций на основе принципа суперпозиции нелинейных полиномиальных преобразований в конечных полях [2, 4, 23, 31]. НЦМ задается как последовательность состояний ВА вида Анцм = (V, S, fj(s'/i, v)), где p(s'/s, v) - функция переходов, задаваемая системой стохастических матриц размерности тхт вида {p(j)(,/ = 1,л}, V = {v, v2 ... vA} - входной алфавит, 5 = {5, s2 ... im} - множество состояний. Функция НЦМ задана последовательностью букв выходного алфавита ВА общего вида Аснцм = S> Z, fi(s', z/s, v)), где Z = {z, z2 ... zd} - выходной алфавит, ju(s',z/s,v)

задается двумя системами ЭСМ: ,, г = 1,/)} - т х т -матрицы, определенные аналогично Анцм и i = 1, h\ тxd-матрицы, определяющие вероятностный закон последовательности выходных букв. На основе {р(ф,/ = 1,л} и (, г = 1, й} образуем ЭСМ P(lh) и Р(г Л) размерности /i-тхт и h-mxd соответственно. Определены разложения P(lh) = р1М1 и ^0=,*) = PiM" Где - простая матрица. Величины р\'\ р,,г) б [0,1], = ^ и

У.1'н pY* ~ 1 ■ ls<hnt -т +1, lz<hmd-d +1. На основе полученных систем простых матриц для каждого разложения строим конечный детерминированный автомат, основываясь на НПФ вида (4) и (5) [23, 31]. В [35] теоретически обоснована возможность представления генераторов, задаваемых Анци и Афпцм, на основе суперпозиции НПФ над GF(2").

Схема генератора, задаваемого Д^щ,, как общий случай рассматриваемых генераторов ДСП класса марковских и их функций на основе нелинейных полиномиальных преобразований [42] приведена на рис. 3.3, где |Z|=2" - разрядность равномерно распределенных случайных чисел, применяемых в генераторах дискретных случайных величин (ГДСВ1 и ГДСВ2), | X' |= Is, | X" |= 1г , | V |= h, | S |= т и | Z |= d. При задании ограничения на НПФ /2 (| X" |= 0) получаем последовательность элементов у как детерминированную функцию ЦМ (п. 2.2), однородных и неоднородных. При ограничении на НПФ /, (| К 1=0) получаемая последовательность элементов q есть однородная ЦМ (п. 2.1).

Предложен метод синтеза генератора неоднородных цепей Маркова и их функций, включающий два этапа: 1) синтез цифровых устройств для вычисления НПФ, заданных в блоках 1 и 2 на рис. 3.3, на основе их представления системами НПФ от многих переменных над G(2) вида (15) согласно методу, предложенному в п. 3.2 [42]; 2) синтез ГДСВ 1 и ГДСВ 2, определяющих ДСВ х' их", соответственно, с заданным законом распределения: ГДСВ/ реализуем системой из rji n-разрядных равномерно распределенных некоррелиро-

ванных дискретных случайных величин и НПФ от 77, переменных согласно методу, предложенному в п. 2.3 [38], / = 1, 2.

Представление генератора, задаваемого Афнцм и приведенного на рис. 3.3, на основе нелинейных полиномиальных преобразований над полем Галуа позволяет получать элементы указанных последовательностей путем организации конвейерной обработки данных с сохранением промежуточных результатов [43]; вычисление значений НПФ (у, х', д) = д и /2 (х", д) = 2 производится при использовании устройств, определенных как на основе предложенных У

структурных , ,

схем (п. 3.1), так |ГДСВ I

и систем НПФ над (п. 3.2)

г„ _ Рис. 3.3. Схема генератора стохастической функции НИМ

[43]. Данное обстоятельство создает предпосылки для представления генератора, задаваемого произвольным Афнцм, на основе однотипных 1Р-ядер, адаптированных под однородную архитектуру ПЛИС/ИРСА определенных семейств за счет организации распределенных вычислений в конечном поле [16, 18, 46].

В четвертой главе, как детализация результатов этапа 4) ОМС (см. главу 1), предложены схемы функциональных модулей (ФМ) операций умножения и вычисления остатка по заданному модулю в конечных полях, определенные на структурном и алгоритмическом уровнях. Данные ФМ являются базовыми для реализации цифровых устройств для генерирования дискретных стохастических процессов класса марковских и их функций (пп. 2.1 - 2.3, 3.3) и для вычисления дискретных детерминированных нелинейных функций, заданных произвольным отображением вида (1) (пп. 3.1 и 3.2), на основе НПФ вида (2) [43]. Проблемный вопрос - синтез ФМ операций над элементами конечных полей большой размерности при ограничениях на оценки временной сложности данных операций. Подходы к разрешению данной проблемы основаны на организации распределенных вычислений при обработке потоков однотипных данных. В частности, при выполнении операции умножения элементов поля Галуа вида 0(л) - ОУ/ С(п), распределенные вычисления организованы

на основе перехода к ОУ элементов расширения поля Галуа вида = 0/г((2*)г) -ОУ/С^{, к-г = п. ФМ, выполняющий О У/С(г1), определен как 1Р-ядро на структурном уровне на основе операций над элементами поля 0{к1, размерность которого - в 2"~к раз меньше, чем С(г1) [9, 26, 36]. Что касается операции вычисления остатка от деления по заданному модулю, то ФМ, ее реализующий, определен как 1Р-ядро на структурном уровне при использовании конвейерной схемы [12, 14, 40].

В п. 4.1 предложены функциональные модули ОУ/С{п) как 1Р-ядра, определение которых на структурном и алгоритмическом уровне допускает возможность распараллеливания вычислений отдельных двоичных разрядов произведения. Согласно [9, 26], оценки временной сложности данного ФМ при определенных образующих многочленах поля С1п)

меньше, чем для ФМ ОУ/С(л), определенной в [1, 29]. Пусть а,/? е0111}, а = (а0 ... а„_,)г и /? = (/?„ ... /?„_,/, где «, Д е СтГ{2). Возможность создания ФМ О У/ С(п) на основе распределенных вычислений обосновывает

Утверждение 4.1 [9, 26]. Вычисление разрядов произведения с элементов а и /?, а,ДсеС(п) производится параллельно согласно формуле:

с,=(«. - - л)г+х;:;((«, - о-(д.. - л^г-), (18)

где / = 0,л-1, = ($" — о,, Д, с,,е6^(2), - степени примитивного

элемента, корня образующего многочлена : Р(%) = 0, т = п, (2л - 2).

На основе операций над элементами GF(2), принятых в качестве меры сложности, для функционального модуля ОУ/0{п), определенного на основе выражения (18), вычислены оценки временной и аппаратной сложности: т(р(п))= 2«[ и <2(Сс)) = -1) = "(2п-1), соответственно [9, 26].

В п. 4.2 предложены функциональные модули ОУ/С'Ц на основе 1Р-ядер, определенные на структурном и алгоритмическом уровне согласно [9, 26, 36] (рис. 4.2). Элементы С((Ц представимы как п = к-г - разрядные векторы, то есть как г векторов размерности к:

а = (а0 ... аг_,У и /? = (Д, ... /?,_,/, еСГ(2'), Справедливо обоб-

щение утверждения 4.1 -

Утверзвдение 4.2 [9, 26]. Вычисление элементов произведения а и р, а, /? е С[р} -

с, производится согласно (18) для п = г, 1-0, г -1, где ¿¡т е С^], т = г, (2г - 2), - степени примитивного элемента, корня образующего многочлена : Р(£) = 0.

На основе утверждения 4.2 предложен алгоритм конвейерного вычисления О У/ :

сложения по модулю два над рнс 4 2 Сх£мз функционального модуля ОУ/(?м

элементами поля С(1). Для

определенных С{11) и С^ на структурном уровне представляется возможным уменьшить

оценки временной сложности функциональных модулей ОУ/О'^, по сравнению с ФМ ОУ/йм, п = к г, к> 1, примерно в 1+1оя2(я/£)/0о§22к) раз за счет организации распределенных вычислений [9, 26, 43]. В частности, для к- 2 (см. п. 3.2), - примерно в 1 + 0,5 ■ 1с^2(и/2) раза.

В п. 4.3 предложены две альтернативные схемы функциональных модулей операции вычисления остатка от деления по заданному модулю для потока чисел (ОВО), определенные как 1Р-ядра на структурном и алгоритмическом уровне. Особенность данных ФМ — уменьшение оценок временной сложности вычисления ОВО за счет сохранения промежуточных результатов, получаемых на каждой ступени конвейера (см. рис. 4.3). Пример эффективного использования указанных ФМ - синтез генератора Смита из класса конгруэнтных генераторов равномерно распределенных псевдослучайных чисел над конечным полем [12, 19, 40]. В зависимости от того, какие логические операции реализуют программируемые элементы заданной ПЛИС/ТРСА, производится выбор одного из двух предложенных 1Р-ядер ФМ для операции вычисления остатка от деления по заданному модулю, в наибольшей степени соответствующего предъявляемым требованиям к оценкам временной и/или аппаратной сложности. Обозначим как Тст(с), Т!Ь(с) и Тш - оценки временной сложности для операций сравнения и вычитания с константой с, а также для операции мультиплексирования «-разрядных чисел, а Тф(д) - оценку временной сложности операций умножения на константу с/ разрядности /. Оценки аппаратной сложности указанных элементов

обозначим как <2с„(с), <2,ь(с), (¿тх и (Э® (<7) > соответственно. Общая структурная схема ФМ ОБО приведена на рис. 4.3.

Для первого

л-<"

О

I)

о

I)

(х<'+,г) -(¡)тос! рэ

варианта 1Р-ядра х> ' ^ |

функционального _ . . ,

Рис. 4.3. Оощая схема функционального модуля операции вы-

модуля, определен- —11.

числения остатка по заданному' модулю

ной на основе операций вычисления частичных остатков от деления при заданных постоянных величинах и р, (/- и ¿-разрядных, соответственно) на каждом этапе конвейера [40], справедливы

Утверждение 4.3.1 [40]. Оценки временной сложности функционального модуля операции вычисления остатка по заданному модулю для потока чисел на основе вычисления частичных остатков, будут меньше, чем для функционального модуля, заданного на основе схемы операции вычисления остатка по заданному модулю без использования конвейера, в / + 1 + Ги(9)/Г раз, если 7" > , и в 1 + (/ + 1)(Г/Гв(?)) раз - если 7"<Гв(д), где Т' = тах(Тст(р1), 7;„(2Я), Тл(р,\ Т,„(2р,))+Тт.

Утверждение 4.3.2 [40]. Оценка аппаратной сложности функционального модуля операции вычисления остатка по заданному модулю на основе вычисления частичных остатков сотавляет - 6®(<7) +

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

Однако, для ФМ операции вычисления остатка по заданному модулю на основе вычисления частичных остатков требуется к(/ +1) ¿»-триггеров, применяемых для сохранения промежуточных сезультатов на каждой ступени конвейера [40].

Второй вариант 1Р-ядра ФМ операции вычисления остатка по заданному модулю определяет Г-кратное выполнение функции вида [14, 19]:

б(Л) = а„_16„_1 + - + +«»2' + •+а,2 + а0, (19)

где Л = (а„_,,..., аа) - и-разрядное двоичное число, 6, =2' для г' = 0,к и Ь) = 2' гпос! р1 для ]=к + \,п-\,к-разрядность р1. Значение Т устанавливается эмпирически для заданного р1 согласно методике, предложенной в [14]. Обозначим Т„Гт, Г, и Г£ ■ оценки временной сложности для параллельного регистра, буферного элемента и сумматора на п — к входов. Согласно [14] справедливо следующее

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

(/ + 1)-(тах(Г„(а),7*„(2Л),Т,ь(р,\Т,ь{2р,))+Т„)1Г раз, где Т" = Тю + тах(7^ + шах

При этом для ФМ ОВО, определенного на основе операций вида (19), требуется (г ■ (п(к + 2)-{к +1)2)+ 2к + з) ¿»-триггеров.

В пятой главе, как развитие п. 5) ОМС, предложена «Методология реализации устройств, описанных в главах 3 - 5 и позволящих выполнить операции над конечным полем, на основе однотипных 1Р-ядер, представленных на ПЛИС/КРСА». Методология включает ряд методик синтеза и анализа, основанных на предложенном ОМС. Методики представлены в пп. 5.1 - 5.3. Показано, что общий метод синтеза устройств ВТ для генерирования дискретных стохастических процессов класса марковских и их функций (пп. 2.12.3, 3.3) на РВС ПА сводится к методике синтеза однотипных 1Р-ядер, реализующих циф-

ровые устройства для вычисления ДДНФ от многих переменных (пп. 3.1, 3.2), а также ФМ для вычисления операций умножения элементов G(j0 или G(jj (пп. 4.1 и 4.2) и операции вычисления остатка по заданному модулю (п. 4.3), на ПЛИС/FPGA [16]. Указанный общий метод применим и к синтезу устройств для вычисления теоретико-полиномиальных преобразований [21, 27, 43] и отображения/варьирования состояния KMC(iV) [6 - 8, 21, 27, 32]. При синтезе однотипных IP-ядер использован подход, предполагающий предварительную структурную и функциональную проработку описывающих их схем на предмет возможности организации распределенных вычислений [1]. Подход, основанный на применении ОМС, включает в качестве важнейших задачи оценки: 1) количества и эффективности задействования конфигурируемых ресурсов ПЛИС/FPGA для синтеза IP-ядер [1, 5, 9, 10, 25, 26]; 2) количества корпусов ПЛИС/FPGA, требуемых для реализации устройства ВТ, и времени задержки его (устройства) работы [16].

Решена задача выбора реализации для заданного функционального модуля, представленного как IP-ядро, приближенное к оптимальному по предложенным критериям [1, 5, 9, 10, 25, 26]. Причем одной структурной схеме заданного ФМ, определяемой как IP-ядро на алгоритмическом уровне, может быть поставлено в соответствие множество FS - функциональных схем в базисе ПЛИС/FPGA, определяемых как IP-ядра на уровне физической реализации и удовлетворяющих ограничениям по указанным критериям. Синтез ФМ в базисе ПЛИС/FPGA выполнен путем создания принципиальной схемы IP-ядра, его описывающего, при использовании спец. САПР: ISE 13.4 - Foundation (Xilinx Corp.) и Quartus II v. 9.0 (Altera Corp.). Принципиальные схемы включают в себя элементы, определяющие арифметические и логические операции над двоичными числами заданной разрядности, а также связи между указанными элементами. Порядок ввода принципиальной схемы ФМ в САПР выполнен в зависимости от разрядности п обрабатываемых операндов - двоичных векторов. Если п относительно небольшое (например, не превышает 16-20 для операции умножения элементов G(„, или G^ (пп. 4.1 и 4.2) и 12 - для операции вычисления остатка по заданному модулю (п. 4.3)), ФМ представим в САПР при использовании схемотехнического редактора; иначе - использование схемотехнического редактора сопряжено с большими затратами труда и для описания модуля в САПР применен HDL-код.

Предложен двухэтапный метод синтеза [16] устройств ВТ на РВС ПА, элементами которой являются ПЛИС/FPGA, на основе IP-ядер, представленных пп. 3.1, 3.2, 4.1 - 4.3. При этом на одном корпусе ПЛИС/FPGA размещается как минимум одно IP-ядро, являющееся составной частью синтезируемого устройства.

Для обеспечения синтеза на ПЛИС/FPGA семейства генераторов, описываемых полиномиальной марковской моделью (определение 2.1), путем выделения из данного семейства к типичных представителей, и распознавания принадлежности данных генераторов к одному из заданных подклассов, решены задачи классификации [3, 17, 22, 30, 37] и идентификации [13, 15] при использовании методов многопараметрической статистики. Методика классификации позволяет в Q/k раз уменьшить суммарный объем файлов конфигурации ПЛИС/FPGA, реализующих семейство из Q генераторов конечных простых однородных цепей Маркова, k«Q. Методика идентификации генераторов ОЦМ, заданных стохастическими матрицами из определенных подклассов, позволяет существенно уменьшить длину ОЦМ, требуемую для идентификации данных генераторов с доверительной вероятностью 0,95: в 1,4-64 раза. Представленные методики внедрены в НПО «Радиоэлектроника» (г. Казань), в ВА ВКО (г. Тверь) и в НПП МЦЭИР (г. Тверь).

В п. 5.1 предложена методика оценки степени соответствия функционального модуля архитектуре ПЛИС/FPGA [10]. Методика позволяет оценить степень соответствия для ФМ, описываемых в пп. 4.1 - 4.3, при использовании критериев, характеризующих: 1) долю ресурсов взаимосвязи в общих затратах логических ресурсов ПЛИС - К„ [1, 5]; 2) вклад задержки межсоединений (МС) в общую оценку времени задержки функцио-

нирования - К, [1, 5, 9]; 3) оценку времени прохождения сигнала внутри логических элементов ПЛИС в пересчете на один уровень ЭС - tj3C [10]; 4) эффективность задействования ГФ внутри конфигурируемых логических элементов (ЛЭ) - Кt [25].

Замечание 5.1. Если для синтеза ФМ сконфигурировано не более 50% ЛЭ и не более 50% блоков ввода-вывода (БВВ), то, согласно опыту синтеза ФМ различного назначения на ПЛИС/FPGA (Норенков И.П., Пономарёв В.И., Шабалин Л.А. и др.), существуют реализации функциональных схем, в большой степени соответствующие архитектуре ПЛИС/FPGA по заданным критериям.

В п. 5.2 предложена, как составная часть п. 5) ОМС (глава 1), методика оценки сложности синтеза устройств ВТ на основе IP-ядер на распределенных вычислительных системах с программируемой архитектурой [16]. ПЛИС/FPGA включает такие виды программируемых ресурсов как MC, ЛЭ и БВВ. Количество ЛЭ и БВВ, в большей степени определяет возможности ПЛИС по реализации множества IP-ядер в одном её корпусе. Каждое из устройств ВТ описывается на основе графа алгоритма вычислений (Каляев И.А., Левин И.И. и др.). Вершинам данного графа соответствуют однотипные цифровые вычислительные устройства (или функциональные модули), описываемые как IP-ядра, общее количество которых равно , где п, - количество ядер 1-го типа, т - количество типов

IP-ядер. Для синтеза 1Р-ядер 1-го типа на ПЛИС/ FPGA требуется q\'l ЛЭ и q\','1H БВВ. При этом общее количество ЛЭ и БВВ, задействуемых под логические входы или выходы, внутри одного корпуса ПЛИС/FPGA определено как QlE и QIOB, соответственно. Задача оценки сложности синтеза определенного устройства (или модуля) по количеству корпусов ПЛИС определенного типа (WFPGA) и по времени задержки его функционирования (rFPGA ) сводится к решению двумерной задачи об упаковке в контейнеры. Первое измерение - количество ЛЭ, а второе - количество БВВ. IP-ядра (с параметрами и q^B ) выступают в качестве объектов упаковки, а корпусы ПЛИС (с параметрами у ■ QLE и Qlon ) - как контейнеры, где у - коэффициент задействования ЛЭ ПЛИС, 0 < у < 1, определяемый проектировщиком. Эмпирически установлено, что для приближенного к оптимальному (для обеспечения Ги>ОА —> min ) размещения ЛЭ, используемых для реализации на ПЛИС 1Р-ядер, значения у € [0,5, 0,7] (Норенков И.П., Пономарёв В.И., Шабалин Л. А.).

На ПЛИС семейства Virtex-4 - XC4VLX200 FF1513-11 реализованы IP-ядра, позволяющие вычислить элементы системы вида (15) - НПФ вида (2) от т переменных (НПФ(т)), определенных над полем G(2) = GF(22). Данные НПФ определены на основе следующих структурных схем (см. п. 3.1): параллельной (ПарС) и параллельно-последовательностной (ППС).

На одной ПЛИС заданного типа (при условии, что у < 0,5) на основе ПарС реализуемы IP-ядра для реализации НПФ(т), т < 7 : до двух IP-ядер для НПФ(7) (общее время задержки функционирования - Tt = 30,9 не., критерий 2) (см. п. 5.1) - К, = 76,4 %) и до 11-ти IP-ядер для НПФ(6) (Т3 = 26,4 не., К, = 74,5 %). Что касается реализации НПФ(т) на основе ППС, то на указанной ПЛИС синтезированы IP-ядра, реализующие вычисление значения У^а^ j q['...q'" еС(г), / = 16, - частичных сумм (ЧС(/ m)). Количество IP-ядер, реализуемых на одной ПЛИС XC4VLX200 FF1513-11 с применением ПСС, определено не по количеству задействованных ЛЭ, а по числу задействованных блоков ввода-вывода (БВВ) ПЛИС, т.к. доля задействованных БВВ для указанных устройств будет выше, чем доля задействованных ЛЭ. На одной ПЛИС реализуемы до десяти ЧС(16, 6) (7^ = 8,81 не., А', = 59,2 %) и до четырех ЧС(16, 34) (Т1 = 13,5 не., А', = 60,3 %).

Предложен метод оценки параметров М??0А и ТТраА для устройств ВТ на РВС ПА, реализующих как произвольную дискретную детерминированную нелинейную функцию (пп. 3.1 - 3.2), так и теоретико-полиномиальные преобразования (п. 5.1) и генераторы дискретных стохастических процессов класса марковских и их функций (пп. 2.1 -2.3, 3.3), при использовании ДЦНФ. Метод позволяет выполнить предварительный анализ характеристик реконфигурируемых ресурсов, требуемых для реализации широкого класса устройств ВТ, синтезируемых на основе однотипных цифровых устройств (функциональных модулей), на РВС ПА [16, 18, 44] и включает два этапа: 1) оценка количества ЛЭ и БВВ, требуемых для реализации одного 1Р-ядра 1-го типа, / = 1, т, - и , на одной ПЛИС/РРОА (с заданными параметрами к • (3ЬЕ и Qюъ) при использовании специализированной САПР; 2) на основе результатов решения двумерной задачи об упаковке в контейнеры вычисление значений параметров Т?ТОА и NFpaA.

Предложенный метод открывает возможности для предварительного анализа характеристик реконфигурируемых ресурсов, требуемых для реализации широкого класса устройств ВТ, синтезируемых на основе однотипных цифровых устройств (или функциональных модулей), на РВС ПА [16, 18, 55, 56,58].

В п. 5.3 предложены методики синтеза и идентификации семейства генераторов, описываемых полиномиальными марковскими моделями (ПММ). При реализации семейства генераторов дискретных стохастических процессов, задаваемых ПММ вида (8), на ПЛИС/РРОА, существует проблема хранения массивов исходных данных большей размерности. Указанная проблема разрешена путем многопараметрической классификации множества стохастических матриц класса эргодических Р, задающих указанные ПММ, мощности Q методами многомерной математической статистики, с последующим выделением представителей к получаемых групп (кластеров) - задачи типизации, k«Q. Задача решена при использовании метода кластерного анализа (КА) для ЭСМ из подклассов положительных, дважды стохастических и с локальными переходами [22, 30, 37]. Предложено множество признаков, |су, _/ = 1,10}, отражающее свойства ЭСМ Р, существенные для многопараметрической классификации [22, 30, 37]. Методика многопараметрической классификации ЭСМ включает два этапа [17, 22, 30]: 1) КА множества объектов - ЭСМ Р с применением разработанного множества признаков {су, у =1,10 }; 2) оценка качества результатов КА: оценки адекватности кластеризации и коррекция результатов КА при использовании метода дискриминантного анализа [3, 37], а также оценка корреляции между признаками {су, у = 1,10 } методом факторного анализа.

С целью распознавания принадлежности семейства генераторов, задаваемых ПММ вида (8), определенных на основе ЭСМ размерности тхт,к одному из конечного множества подклассов, предложена методика многопараметрической идентификации ЦМ, порождаемых указанными генераторами. Идентификация производится на основе предложенного множества признаков (МнП) Ае^ й^ к = \-т,т-\, ¿' = 1,4, вычисляемых непосредственно по ЦМ ограниченной дайны Ы, с заданной доверительной вероятностью р. Подклассы ЭСМ из множества - треугольные (верхние и нижние) и блочно-сообщающиеся (правые и левые), имеют различную степень сходства/различия структур [13, 15]. Показано, что для идентификации генератора ЦМ, заданного на основе ЭСМ размерности тхт (биграмм), элементы которой варьируются с дискретностью £> = 5-Ю-2, с вероятностью р = 0,95, требуется N — 386 элементов ЦМ, причем N практически не зависит от значения п. Тогда как для идентификации аналогичного объекта с р = 0,95 на основе предложенного МнП, требуется N = 284 элемента ЦМ для п = 6 а N = 6 для п = 256, то есть требуется элементов ЦМ в 1,4 - 64 раза меньше, соответственно [15]. Данное обстоятель-

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

В шестой главе. «Техническая реализация и применение устройств ВТ на основе нелинейных полиномиальных преобразований над конечным полем», представлены результаты по применению предложенных теоретических основ общего метода синтеза (гл. 1) как в задачах реализации генераторов ДСП класса марковских и их функций, так и в задачах создания специализированных устройств ВТ ЦОС, как существующих, так и перспективных. Во-первых, в направлении синтеза устройств ВТ для теоретико-полиномиальных преобразований на примере ДПФ, ДПХ и алгоритмов цифровой фильтрации с импульсной характеристикой конечной длительности (КИХ-ф.) на основе систем НПФ в поле Галуа (п. 3.2), причем каждая НПФ реализуема одним из однотипных функциональных модулей [43]. Во-вторых, на применение ФМ операции умножения элементов полей вида G(nl и G^j (пп. 4.1 и 4.2) для синтеза устройства ВТ, применяемого для отображения/варьирования состояния дискретной модели квантово-механической системы с N базисными состояниями - KMC(iV) [8] а также ее частных случаев: КМС(2) (кубит) [6, 32] и КМС(4) (простейший регистр с двумя взаимосвязанными кубитами) [7].

Для решения задачи синтеза устройств ВТ, применяемых для отображения/варьирования состояния KMC(JV), в соответствии с предложенной методикой (п. 5.1), синтезированы ФМ, реализующие операции умножения (ОУ) элементов G(n) и G^ (пп. 4.1 и 4.2). Функциональные схемы реализации ОУ в базисе ПЛИС/FPGA получены при использовании спец. САПР (см. введение к гл. 5).

Для уствойств ВТ, синтезируемых при использовании цифровых устройств для вычисления дискретных детерминированных нелинейных функций, за счет параллельного вычисления системы НПФ над полем GF(22) (п 3.2) на РВС ПА «Медведь» (НИИ многопроцессорных вычислительных систем им. A.B. Каляева Южного федерального университета (НИИ МВС ЮжнФУ), г. Таганрог), увеличена скорость выполнения алгоритмов ЦОС по сравнению с реализациями на ПЛИС ЕР2С5Т144С6 (семейство Cyclone II) в системе остаточных классов (СОК) (Галанина H.A., 2011) и на спец. процессорах ADSP-TS001 ( Analog Devices, Inc., 2010) и АМ1808 ARM Microprocessor ( Texas Instrument, Inc., 2011) в позиционной системе счисления (ПСС) в 1,2 - 2,6 раза. Достигнутое преимущество позволило внедрить устройства, реализующие ДПФ и КИХ-ф. на основе предложенной общей структурной схемы, ориентированной на архитектуру ПЛИС/FPGA, в НПП «Измерительные технологии» (г. Саров).

Реализуемые на РВС ПА «Медведь» генераторы ОЦМ (рис. 2.1.1, |ß|<2J-j-26, |ЛГ| < 28 -г- 29, \z\ < 2й) и стохастической функции НЦМ (рис. 3.3, |Z|,|Sj<26, \v\<2', I А"|,| Х"\ < 28 и |z| < 2'2), генерирующие элементы с частотой до 37,9 МГц, внедрены в НПО

«Радиоэлектроника» (г. Казань) и в НПП МЦЭИР (г. Тверь).

В п. 6.1 представлен подход к решению задач синтеза генераторов ДСП класса марковских и их функций на РВС ПА «Медведь» с применением предложенного ОМС (см. гл. 1). На основе IP-ядер, реализующих систему НПФ над G(2) вида (15) согласно методу, приведенному в п. 3.2, выполнен синтез генераторов как однородных цепей Маркова, заданных ПММ вида (8) (см. п. 2.1), так и стохастической функции неоднородных ЦМ, заданных ВА Ai>rfl{M = (V,S,Z,fi(s',z/s,v)) (п. 3.3). Генераторы ОЦМ общего вида, представленные НПФ g(z) и f{x,q) над GF( 22), реализуемы при использовании IP-ядер на основе ПарС и ППС (см. п. 5.2). В первом случае обеспечивается высокая частота генерирования элементов ОЦМ - 37,9 МГц для |ß|<23 +26, |Х|<28+29, |z|<212, примерно в 2

раза большая, чем на современных спец. процессорах, за счет распределенного вычисления НПФ в архитектуре ПЛИС/FPGA. Из-за характеристик современных ОЗУ (полное время цикла чтения - не менее 50 не.) вычисление функции перехода ОЦМ на спец. процессорах производится с частотой не более 20 МГц (В.П.Афанасьев, 2013).

Генераторы стохастической функции НЦМ общего вида, реализуемы на основе предложенной структурной схемы (рис. 3.3) при использовании IP-ядер, из которых ns /2 = ]log2 /s[ позволяют вычислить НПФ вида (15) от (77,-/7/2) переменных, nz /2 = ]log2/z[/2 -от (щ-п/2), «„ /2 = ]log2 т[/2 -от (Qlog,/г[+«, + «J/2), a ]log2 f/[/2 -от {(п2 + л„)/2) переменных, соответственно. Для |Z|<2'4, |z|<26, \v\<2\ |S|<26 и | A"|,| X"\ < 28 данный генератор реализуем на 30-ти ПЛИС 4VLX200FF1513-11 в составе

РВС ПА «Медведь» при использовании 59-ти IP-ядер, реализующих НПФ(7) либо на 32-х корпусах указанных ПЛИС при использовании 212-ти IP-ядер, реализующих НПФ(6). Оценки периода и частоты генерирования элементов СФ НЦМ равны: в первом случае -30,9 не. и 32,4 МГц, во втором случае - 26,4 не. и 37,9 МГц.

В п. 6.2 представлены результаты по применению метода синтеза цифровых устройств для вычисления дискретной детерминированной нелинейной функции общего вида (см. п. 3.2) для задачи реализации устройств ВТ определенных подклассов теоретико-полиномиальных преобразований, применяемых для анализа и фильтрации потоков «-разрядных двоичных чисел, на примерах ДПФ, ДПХ, а также КИХ-ф., описываемых на основе систем НПФ над полем Галуа [43].

Предложена общая структурная схема (ОбСС) для устройств ВТ, выполняющих заданные подклассы ТПП - ДПФ, ДПХ и КИХ-ф., на РВС ПА «Медведь», которая включает в себя однотипные элементы, например, ПЛИС XC4VLX200FF1513-11. ОбСС указанных устройств приведена на рис. 6.2. Определены оценки аппаратпой сложности предложенной ОбСС, как на основе ЛЭ ПЛИС/FPGA, так и по количеству ¿»-триггеров:

г*-2-')). (20)

где 2(<8>с) = /-е(БФ(и)), = (/ + /) (по количеству ЛЭ).

= + + (21)

Оценки аппаратной сложности вычислимы согласно (20) и (21) для устройств ВТ, обрабатывающих двоичные числа разрядности п и реализующих: 1) ДПФ для S = N и t = 2-N ; 2) ДПХ для S = Nut = iV;3) КИХ-ф. для S = M +1 и г = 1, где Л' - количество отсчетов дискретного сигнала, подвергаемого ДПФ или ДПХ, М-порядок КИХ-ф.

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

Тосс = max(7X<8>c), r(Z(/_2)), 7Й\ Т£?)+Т„ . (22)

где Г(®с ), 7Т£(/+„_2)), , и TD - оценки времени задержки схемы умножения на

константу, сумматора для двух (/ + и - 2) -разрядных двоичных чисел, блоков ввода-вывода, сконфигурированных на вход и выход, а также D-триггера, соответственно. Оценка частоты работы каждого из устройств указанного класса - F = , получена на основе (22).

Устройства ВТ для КИХ-ф. реализуемы на одной ПЛИС 4VLX200FF1513-11 при M < 255, п < 8, а для ДПФ и ДПХ - на одной РВС ПА «Медведь» при обработке чисел разрядности п < 8, при N < 128, а также когда п < 6, при N < 256.

Для предложеных устройств ВТ, реализующих заданные подклассы теоретико-полиномиальных преобразований -ДПФ, ДПХиКИХ-ф„ оценки времени задержки функционирования снижены в 2.4-2.6 раз, в 1.2 -1.3 раза и в 1.6 — 2.4 раза, соответственно, по сравнению с устройствами ВТ, реализующими указанные ТПП на основе операций над числами, представленными в СОК и в ПСС (см. табл. 6.2), за счет организации распределенных вычислений при использовании однотипных 1Р-ядер. В результате, увеличено быстродействие устройств ВТ указанного клас-

Рис. 6.2. Общая структурная схема устройств ВТ, реализующих ДПФ, ДПХ и КИХ-ф.

Тип устройства ВТ ПЛИС ЕР2С5Т144С6 (одни корпус), в СОК ft Спец. процессоры в ПСС РВС ПА «Медведь», система НПФ над GF(22) (п. 3.2)

TSOOl.ft (мкс.) AM 1808, ft (мкс.) ft (мкс.) / число корпусов Выигрыш по (з (раз)

ДПФ, N=128 ~ 19 мкс. - - -1,35/22 -14

ДПФ, N=256 - 43 мкс. -7,3 -6,8 -2,86/47 ~ 2,4 - 2,6

ДПХ, N=128 - - - -1,35/11 --

ДПХ, N=256 - -3,7 -3,4 -2,86/24 - 1,2- 1,3

КИХ-ф., М= 255 - -6,9 -4,5 -2,86/(1/11) ~ 1,6 - 2,4

В п. 6.3 решена задача анализа степени соответствия архитектуре ПЛИС/ FPGA схем функциональных модулей операции умножения элементов полей вида G(n) и G[£j -Oy/G(„, и Oy/G('jJ, определенных в пп. 4.1 и 4.2, соответственной качестве примера на рис. 6.3.1 приведены оценки общего и приведенного (критерий tl3C, п. 5.1) времени задержки функционирования для модулей, реализующих ОУ/G(n) на ПЛИС серии EP1S10B672C6 для двоичных векторов размерности 8, 16, 32 и 64. При отображении данных модулей в базис ПЛИС выполнено сопоставление их теоретических оценок сложности с оценками реальных затрат программируемых элементов ПЛИС: ЛЭ с программируемыми ГФ и D-триггерами, а также МС, согласно критериям, определенным в п. 5.1 (для указанных функциональных модулей (ФМ) значения критериев К,,Г, К, и К, (см. п. 5.1) приведены на рис. 6.3.2).

Критерий К, позволяет оценить возможность снижения Т для ФМ за счет реконфигу-рирования МС ПЛИС, а критерии Кп и Kt- оценить возможность более эффективного задействования ЛЭ и ГФ ПЛИС. Степень соответствия ФМ ОУ/G(n) и ОУ/ОЦ], архитектуре ПЛИС семейств ХС4000Е, Spartan и ХС5200 (Xilinx Corp.) и EP1S10B672C6 (Altera Corp.), в частности, при условии, что r-k = n, определена по методике и согласно критериям, описанным в п. 5.1 [1, 9, 10, 25, 35].

В п. 6.4. решена задача синтеза схем функциональных модулей операции вычисления остатка от деления по заданному модулю, определенной на основе конвейерных вычислений (п. 4.3), для потока чисел на ПЛИС/FPGA [14, 19]. Представлена реализация на ПЛИС/FPGA Stratix II GX (Altera Corp.) типа EP2SGX30CF780C3 и Virtex 4 (Xilinx Corp.) типа 4VLX160FF1148-11 генератора равномерно распределенной дискретной случайной величины Смита, заданного при использовании первого варианта схемы операции вычисления остатка по заданному простому модулю (рис. 4.3) [12, 40].

Рис. 6.3.1. Общее и приведенное время задержки функционирования ФМ ОУ/о(„, на ПЛИС ЕР1810В672С6, и = 8, 16, 32 и 64

ш

Рис. 6.3.2. Доля ресурсов взаимосвязи в ФМ О У/G(„} на ПЛИС EP1S10B672C6, л = 8, 16, 32 и 64

Данные семейства ПЛИС сопоставимы по таким характеристикам, как оценка временной сложности, количество конфигурируемых логических ресурсов и наличию специализированных вычислителей (ядер ХО-етеВЭР). Различие данных семейств - в структуре их логических ресурсов. Сопоставление оценок времени задержки функционирования (7) ФМ, реализующего операцию вычисления остатка от деления по заданному модулю, на ПЛИС 4УЬХ160РР1148-12 для потока чисел разрядности 8, 16 и 24, при ведено на рис. 6.4. За счет выбора оптимальной конфигурации программируемых элемен тов ПЛИС, параметр Т для ФМ, реализованных без использования ядер Хй-етеОЭР, определяется только задержкой блоков ввода-вывода, частота функционирования которых для ПЛИС данного типа -примерно 283 МГц). Если ФМ операции вычисления остатка от деления по заданному модулю реализуемы на ПЛИС без использования ядер

Х^етеОЭР, то ГФ и логические элементы задействованы не более чем на 50 и 75%, соответственно. Для ФМ операции вычисления остатка по заданному модулю характерна большая доля логических ресурсов, задействованных для пе-

□ Без ядер )^remeDSP

) С ядрами >lrerncDSP

ш

3,52

Рис. 6.4. Время задержки функционирования (не.) модуля, реализующего ОВО, на ПЛИС 4УЬХ160РР1148-12, п = 8, 16 и 24

редачи сигналов внутри ПЛИС, а не для синтеза логических функций. Что касается ФМ ОВО на ПЛИС УЫех 4 ЬХ с использованием ядер ХйетеОЗР, то ГФ задействованы на 80100%, а ЛЭ - на 50-56%, соответственно [14]. Степень соответствия ФМ ОВО (п. 4.3), архитектуре ПЛИСЛ-РОА определена по методике и согласно предложенным критериям (п. 5.1) [1,9, 10,25, 35].

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

В п. 6.5 предложены схемы устройств ВТ для отображения и варьирования состояния дискретной модели КМС(/У) для произвольного числа базисных состояний N [8], а также ее частных случаев: КМС(2) - квантового бита (кубита) [6, 32] и КМС(4) - простого квантового регистра [7]. Данное устройство представимо при использовании однотипных ФМ операции умножения (ОУ) элементов полей С/г(2") и СГ((2к)г), к-г = п, (см. пп. 4.1 и 4.2), функционирующих параллельно, что обосновано соответствующими теоремами [8]. Состояние КМС(;У) описывается как

И=(гов* ... 1. (23)

Дискретная модель (ДМ) КМСЗД описывается при использовании графовой модели - двоичного (бинарного) дерева Т. Число его вершин, являющихся листьями, равно числу базисных состояний КМС(Д0, а число вершин, которые не являются листьями, (Л? -1), определяет количество параметров, описывающих амплитудные и фазовые составляющие данной модели - 2(М -\) [8]. Варьирование состояния ДМ КМС(Л'), описываемое системой (23), задано квантовым вентилем, унитарной матрицей размерности Л' х N, вида С = ОфСЛ , где матрицы Сф и Ол размерности А,г х N определяют варьирование фазовой и амплитудной составляющей ДМ КМС(Л'), соответственно [8]. Верхняя оценка аппаратной сложности устройства ВТ для расчета предложенной ДМ отображения и варьирования КМС(Ы), а также ее частных случаев (Л' = 2, 4), определена как для 2(ЛГ -1) функциональных модулей ОУ/СР(2") или ОУ/ОР((2*)г), к-г =п (пп. 4.1 и 4.2); нижняя оценка временной сложности для указанного устройства ВТ определена как для одного функционального модуля ОУ/вР{2") или OУ/GF((2t)r) [6 - 8, 32].

В заключении сформулированы основные результаты работы.

ЗАКЛЮЧЕНИЕ

Главным результатом данной работы является достижение ее цели - разработка теоретических основ общего метода структурного, алгоритмического и функционального синтеза генераторов дискретных стохастических процессов класса марковских и их функций и устройств вычислительной техники для выполнения теоретико-полиномиальных преобразований, повышающего эффективность реализации данных генераторов и устройств на ПЛИС/ГРвА за счет применения нелинейных полиномиальных параллельных преобразований над потоками чисел в конечных полях. Достижению цели способствовало получение следующих основных научных результатов.

1. Предложен общий метод структурного синтеза классов устройств вычислительной техники и разработаны теоретические положения его реализации на основе предложенного принципа суперпозиции нелинейных полиномиальных функций (НПФ) над полем Га-луа; принцип суперпозиции определяется рядом теорем и позволяет отобразить на распределенных вычислительных системах с программируемой архитектурой, элементами которой являются ПЛИС/РРСЛ

• разработанные структурные схемы генераторов ДСП класса марковских и их функций - однородных ЦМ, определенных на основе введенного понятия «полиномиальная модель цепи Маркова», их детерминированных и стохастических функций, а-сложных ЦМ, неоднородных ЦМ и их функций, детерминированных и сто-

хаотических, дискретных случайных величин с заданным законом распределения; реализация применяемого принципа суперпозиции основана на предложенном методе представления стохастических матриц нелинейными полиномиальными функциями от многих переменных над полем Галуа, что позволяет уменьшить время генерирования элементов однородных ЦМ примерно в 2.0 раза, по сравнению с минимальным временем генерирования указанных процессов на основе известных методов (табличный, на основе функций алгебры логики) при использовании современных спец. процессоров;

• разработанную общую структурную схему устройств ВТ в архитектуре ПЛИС/ FPGA, выполняющих теоретико-полиномиальные преобразования на примере ДПФ, ДПХ и цифровых фильтров с импульсной характеристикой конечной длительности (КИХ-ф.), что позволяет получить выигрыш по быстродействию при реализации указанных устройств на распределенной вычислительной системе с программируемой архитектурой «Медведь»: для ДПФ и ДПХ (при п <8 и N < 256 ) - примерно в 1.2-2.6 раз, а для КИХ-ф. порядка 255 (при п < 8 ) - примерно в 1.6-2.4 раза, за счет организации распределенного вычисления дискретной детерминированной нелинейной функции на основе системы из / НПФ, определенных над GF(2k), п-к-1\

• разработанные структурные схемы устройств ВТ, позволяющих моделировать отображение и варьирование состояния квантово-механической системы общего вида с N базисными состояниями и ее частных случаев для N=2 и N = 4 при использовании предложенной дискретной модели, за счет параллельного выполнения 2(jV — 1) операций умножения над полем GF{2") или GF((2k)'), n = k-r.

2. Разработаны теоретические основы для предложенного метода синтеза ЦВУ ДДНФ от m /i-разрядных переменных на основе распределенных вычислений при использовании системы из / НПФ от / • m переменных, определенных над GF(2k), n-k-l, а также для схем вычисления НПФ от m переменных над GF{2"), альтернативных по оценкам сложности: параллельной, систолической, последовательностной и параллельно-последова-тельностной. Метод позволяет уменьшить оценки временной сложности для ЦВУ ДДНФ, синтезируемых на основе системы НПФ над GF{2*), к = 2, примерно в 1 + (и ■ log2 n + (log2 m)log2 n)/(m ■ n) раз по сравнению с ЦВУ указанной ДДНФ на основе параллельной схемы (п<6 ,т< 7) и примерно в (2"-log гт)! n раз - по сравнению с ЦВУ ДДНФ, определенным при использовании систолической схемы (n, m < 7).

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

• схем ОУ «-разрядных элементов расширений поля Галуа вида GF((2l)r), при использовании операций над элементами GF(2k), n = k-r, что позволяет уменьшить оценки временной сложности примерно в 1 + \og2(n/k)/(\og2 2к) раз, к < 4, n < 64, по сравнению со схемой ОУ элементов GF(2"), на основе операций над полем GF(2) ;

• двух альтернативных схем операции вычисления остатка по заданному простому п-разрядному модулю, n < 24, что позволяет уменьшить оценки временной сложности выполнения ОВО примерно в w раз по сравнению с существующими методами вычисления остатка по заданному простому модулю, где w - количество ступеней конвейера в предложенных схемах ОВО.

Работоспособность разработанных ФМ, определяемых как на основе схем операции умножения элементов GF(2") и GF((2k)'), так и схем ОВО, и синтезированных на ПЛИС/FPGA, подтверждена моделированием функциональных схем указанных модулей при использовании специализированных САПР ISE 13.4 (Xilinx Corp.) и Quartos II v. 9.0 (Altera Corp.).

4. Предложены методики многопараметрического анализа, позволяющие:

• определять подмножество из к типичных представителей семейства генераторов ДСП класса однородных ЦМ, заданных на основе Q эргодических стохастических матриц, описывающих указанные генераторы, с целью уменьшения в Qlk раз объема массивов исходных данных большой размерности, определяющих реализацию генераторов однородных ЦМ на ПЛИС/FPGA, на основе разработанного множества признаков, а также

• идентифицировать принадлежность дискретных простых конечных однородных ЦМ конечной длины N к одному из априори заданных подклассов с определенной доверительной вероятностью (0,95) на основе разработанного множества признаков, для N в 1,4 - 64 раза меньшей, чем на основе статистической обработки биграмм.

5. Разработана методика оценки степени соответствия цифровых вычислительных устройств и функциональных модулей архитектуре ПЛИС/FPGA, позволяющая выбрать из множества реализаций указанных устройств или модулей наиболее приближенную к оптимальной по предложенным критериям. Высокая степень соответствия данных устройств и модулей архитектуре ПЛИС/FPGA достигается путем организации распределенного вычисления как значений нелинейной полиномиальных функций от многих переменных, определенных над полем GF(2k), так и результатов операций, выполняемых в конечных полях: ОУ элементов GF(2"), ОУ элементов GF((2*)r), п = к-г, и вычисления остатка по заданному модулю.

6. Разработаны на основе САПР ISE 13.4 (Xilinx Corp.) и Quartus II v. 9.0 (Altera Corp.) и внедрены устройства ВТ для теоретико-полиномиальных преобразований и генераторы дискретных стохастических процессов из класса стохастических функций неоднородных ЦМ (СФ НЦМ), реализуемые на распределенной вычислительной системе с программируемой архитектурой (РВС ПА) «Медведь» (НИИ МВС ЮжнФУ, г.Таганрог) при использовании однотипных IP-ядер, синтезируемых на ПЛИС/FPGA. Основным объектом внедрения являются устройства ВТ ДПФ и КИХ-ф. (НПП «Измерительные технологии», г. Саров) и генератор СФ НЦМ, представленных двоичными числами (НПО «Радиоэлектроника», г. Казань и в НПП МЦЭИР, г. Тверь). За счет организации распараллеливания процесса вычислений и потоковой обработки данных в архитектуре ПЛИС/FPGA время вычисления на указанной РВС ПА: 1) Фурье-образа для устройства ВТ ДПФ уменьшено примерно в 2.4 раза по сравнению с устройсвами ВТ для быстрых ДПФ, реализованных на спец. процессорах AM 1808 (Texas Instrument, Inc.); 2) значений, снимаемых с выхода устройства ВТ КИХ-ф., уменьшено примерно в 1.6 раз по сравнению с аналогичными устройствами, реализованными на AM 1808. Показана принципиальная возможность синтеза высокопроизводительных генераторов (частота - до 37,9 МГц) однородных ЦМ и СФ НЦМ на основе однотипных IP-ядер, определенных на основе операций в конечном поле и синтезируемых на ПЛИС/FPGA, включенных в состав РВС ПА «Медведь». Теоретические основы и методы анализа и синтеза для генераторов ДСП класса марковских и их функций и для устройств ВТ ТПП на основе НПФ над конечным полем использованы при выполнении грантов РФФИ - №99-0100163, №03-01-00769 и № 09-01-97004-Р-Поволжье 01, в проекте №015-04-01-52 программы «Университеты России» и внедрены в учебный процесс КНИТУ-КАИ и в ВА ВКО. По результатам работы в ФГБУ ФИПС получены три патента РФ: два - на изобретение, один - на полезную модель, и зарегистрирована одна программа для ЭВМ.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых научных изданиях.

1. Захаров, В.М. Аппаратная реализация умножения элементов поля Галуа на программируемых микросхемах архитектуры FPGA/ В.М.Захаров, Ш.Р. Нурутдинов, С.В.Шалагин// Вестник КГТУ им.А.Н.Туполева. - 2001,- № 1,- С.36 - 47. (л. вк. 30%).

2. Захаров, В.М. Полиномиальное представление цепей Маркова над полем Галуа/ В.М.Захаров, Ш.Р.Нурутдинов, С.В.Шалагин// Вестник КГТУ им. А.Н.Туполева. -2001. - № 3. - С. 27-31. (л. вк. 30%).

3. Захаров, В.М. К задаче дискриминантного анализа автоматных марковских моделей/

B.М. Захаров, Н.Н. Нурмеев, Ф.И. Салимов и др. // Вестник КГТУ им.А.Н. Туполева. -2001. - № 3. - С. 37-39. (л. вк. 20%).

4. Захаров, В.М. Полиномиальное представление конечноавтоматных случайных последовательностей над полем Галуа/ В.М. Захаров, Ш.Р. Нурутдинов, С.Ю. Соколов и др.// Вестник КГТУ им. А.Н. Туполева. - 2003. - № 2. - С.24-28. (л. вк. 25%).

5. Шалагин, С.В. Экспериментальное исследование методики синтеза комбинационных схем на программируемых микросхемах класса FPGA / С.В. Шалагин // Микроэлектроника. - 2004. - Т. 33; № 1. - С. 56-67; Shalagin, S.V. Computer Evaluation of a Method for Combinational-Circuit Synthesis in FPGAs / S.V. Shalagin // Russian Microelectronics. -2004. - Vol. 33; № 1. - P. 46-54.

6. Шалагин, С.В. Дискретная модель квантового вычислителя/ С.В.Шалагин// Вестник КГТУ им. А.Н.Туполева. - 2005. - № 1. - С. 35 - 39.

7. Шалагин, С.В. Моделирование квантового регистра, включающего два квантовых бита/

C.В.Шалагин // Вестник КГТУ им. А.Н. Туполева. - 2006. - № 1. - С. 35 - 38.

8. Шалагин, С.В. Дискретная модель квантовой системы обработки информации/ С.В.Шалагин// Вестник КГТУ им. А.Н. Туполева. - 2007. - № 4. - С.22-27.

9. Шалагин, С.В. Умножение элементов расширений полей Галуа в базисе ПЛИС/FPGA/ С.В.Шалагин//Информационные технологии. - 2007. -№ 12.-С.22-27.

10. Кайбушев, Ф.Х. Реализация схем умножения элементов поля Галуа в базисе ПЛИС класса FPGA семейства Stratix/ Ф.Х.Кайбушев, С.В.Шалагин // Информационные технологии. - 2008. - № 11. - С. 51 - 55 (л. вк. 60%).

11. Шалагин, С.В. О представлении нелинейных полиномов над конечным полем распределенной вычислительной системой/ С.В.Шалагин// Нелинейный мир - 2009,- № 5. -С.З 76-379.

12. Зелинский, Р.В. Реализация на ПЛИС генераторов псевдослучайных последовательностей и средств их CRC-контроля/ Р.В.Зелинский, Ф.Х.Кайбушев, С.В.Шалагин// Вестник КГТУ им. А.Н.Туполева. - 2009. - № 2. - С. 57 - 61 (л. вк. 40%).

13. Нурутдинова, А.Р. Методика идентификации автоматных марковских моделей на основе порождаемых ими последовательностей/ А.Р.Нурутдинова, С.В.Шалагин// Вестник КГТУ им. А.Н.Туполева. - 2010. - № 1. - С. 94 - 99 (л. вк. 60%).

14. Захаров, В.М. Алгоритм вычисления остатка по модулю и оценки его сложности/

B.М.Захаров, Е.Л.Столов, С.В.Шалагин// Информационные технологии. - 2010. -№ 11. - С. 32 - 36. (л. вк. 30%).

15. Нурутдинова, А.Р. Многопараметрическая классификация автоматных марковских моделей на основе генерируемых ими последовательностей состояний/ А.Р. Нурутдинова,

C.В.Шалагин // Прикладная дискретная математика- 2010.- № 4. - С. 41-54 (л. вк. 60%).

16. Шалагин, С.В. Реализация устройств вычислительной техники на многопроцессорных системах с программируемой архитектурой/ С.В.Шалагин// Вестник МарГТУ. - 2011. -№ 1 (11).-С. 38-46.

17. Барковский, С.С. Многопараметрический анализ и ранжирование предложений НИОКР отраслевой программы/ С.С.Барковский, А.Р.Нурутдинова, С.В.Шалагин// Вестник КГТУ им. А.Н.Туполева. - 2011. - № 2. - С. 115 - 122 (л. вк. 40%).

18. Захаров, В.М. Вычисление нелинейных полиномиальных функций на многопроцессорной системе с программируемой архитектурой/В.М.Захаров, С.В.Шалагин// Информационные технологии. - 2012. - №5. - С. 6 - 11. (л. вк. 50%).

Патенты на изобретение.

19. Пат. 2421781 РФ МПК" G06F 7/72, НОЗМ 7/18. Устройство для формирования остатка по заданному модулю/ В.М.Захаров, Е.Л.Столов, С.В.Шалагин; заявитель и патентообладатель ГОУ ВПО Казан, гос. техн. ун-т. - № 2009138613/08; заявл. 19.10.2009; опубл. 20.06.2011, Бюл. № 17. -12 е.: ил. (л. вк. 30%).

20. Пат. 2446444 РФ МПК G06F 7/58 (2006.01). Генератор псевдослучайных последовательностей / В.М.Захаров, Р.В.Зелинский, С.В.Шалагин; заявитель и патентообладатель

ГОУ ВПО Казан, гос. техн. ун-т. - № 2010146202/08; заявл. 12.11.2010; опубл.

27.03.2012, Бюл. № 9. -14 е.: ил. (л. вк. 30%). Монография.

21. Шалагин, C.B. Представимость дискретных детерминированных нелинейных функций на основе многочленов над полем Галуа в базисе ПЛИС класса FPGA/ С.В.Шалагин. -Казань: изд-во КГТУ им. А.Н.Туполева, 2010. - 184 с.

Публикации в прочих научных изданиях.

22. Захаров, В.М. Классификация стохастических эргодических матриц методами кластерного и дискриминантного анализа / В.М. Захаров, H.H. Нурмеев, Ф.И. Салимов и др.// Исследования по информатике. - 2000. - Вып. 2. - С. 91-106. (л. вк. 25%).

23. Захаров, В.М. Синтез автономных вероятностных автоматов на основе полей Галуа/

B.М.Захаров, Ш.Р.Нурутдинов, С.В.Шалагин// Исследования по информатике. - 2000. -Вып. 2. - С. 107 - 116 (л. вк. 30%).

24. Захаров, В.М. Полиномиальное представление автоматных моделей марковских функций над полем Галуа / В.М. Захаров, Ш.Р. Нурутдинов, С.Ю. Соколов и др.// Исследования по информатике. - 2003. - Вып. 5. - С. 45-56. (л. вк. 25%).

25. Саси, С.А. Оценки сложности архитектур умножителей в базисе ПЛИС/FPGA/

C.А.Саси, С.В.Шалагин, Л.М.Шарнин // Исследования по информатике. - Казань, 2005. - Вып. 9. - С. 71 - 80 (л. вк. 40%).

26. Шалагин, C.B. Реализация умножения элементов расширений поля Галуа в базисе ПЛИС/ FPGA/ C.B. Шалагин// Методы моделирования: сб. тр. Казанского научного семинара. - Казань: Изд-во КГТУ им. А.Н. Туполева, 2007. - Вып. 3. - С. 297-314.

27. Шалагин, C.B. Представление нелинейных полиномиальных функций над полем Галуа в базисе ПЛИС/FPGA / C.B. Шалагин. - Saarbrücken Germany: LAP Lambert Academic Publishing GmbH & Co. KG, 2012. - 188 c.

28. Пат. на пол. модель 131886 РФ МПК G06F 17/14 (2006.01). Устройство для вычисления дискретных полиномиальных преобразований / В.М.Захаров, С.В.Шалагин; заявитель и патентообладатель КНИТУ-КАИ - № 2012148954/08 заявл. 16.11.2012; опубл.

27.08.2013, Бюл. № 24. - 3 е.: ил. (л. вк. 50%)

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

29. Захаров, В.М. Построение модели умножителя в полях Галуа/ В.М. Захаров, Ш.Р. Нурутдинов, C.B. Шалагин // Дискретная математика и ее приложения: материалы 7-го Междунар. семинара 29 янв.-2 февр. 2001. - В 3 ч. Ч. I. - М.: Изд-во центра прикладных исследований при механико-матем. факультете МГУ, 2001. - С. 62-65. (л. вк. 30%).

30. Захаров, В.М. Анализ стохастических матриц методами многомерной классификации /

B.М. Захаров, H.H. Нурмеев, Ф.И. Салимов и др. // Дискретная математика и ее приложения: материалы 7-го Междунар. семинара 29 янв.-2 февр. 2001. - В 3 ч. Ч. II. - М.: МГУ, 2001.-С. 156-159. (л. вк. 25%).

31. Нурутдинов, Ш.Р. Синтез автоматных моделей цепей Маркова и их функций в конечных полях / Ш.Р. Нурутдинов, С.Ю. Соколов, C.B. Шалагин // Новые информационные технологии и системы: сб. тр. 5-й Междунар. науч.-техн. конф. 14-15 нояб. 2002. - Пенза: Изд-во Пенз. гос. ун-та, 2002. -С. 211-213. (л. вк. 30%).

32. Шалагин, C.B. Дискретная модель квантового бита / C.B. Шалагин III Методы и средства обработки информации: тр. 1-й Всерос. науч. конф. 1-3 окт. 2003. - М.: МГУ, 2003. - С. 572- 577.

33. Шалагин, C.B. Синтез генераторов дискретной случайной величины над полем GF(2An)/ C.B. Шалагин // Сеточные методы для краевых задач и приложения: материалы 5-го Всерос. семинара 17-21 сент. 2004. - Казань: Изд-во КГУ, 2004. - С. 236-240.

34. Захаров, В.М. Метод моделирования и преобразования функций цепей Маркова в полях Галуа и его реализация в базисе ПЛИС/ В.М. Захаров, Ш.Р. Нурутдинов,

C.B. Шалагин // Методы и средства обработки информации: тез. докл. 2-й Всерос. науч. конф. 5-7 окт. 2005,- М.: МГУ, 2005. - С. 256-262. (л. вк. 30%).

35. Захаров, В.М. Реализация полиномиальных моделей над полем GF(2лп) неоднородных цепей Маркова и их функций в базисе ПЛИС/FPGA/ В.М. Захаров, Ш.Р. Нурутдинов, C.B. Шалагин // Инфокоммуникационные технологии глобального информационного

общества: тез. докл. 4-й ежегодной Междунар. науч.-практ. конф. 5-8 сент. 2006. — Казань: Центр инновационных технологий, 2006. - С. 62-66. (л. вк. 40%).

36. Шалагин, C.B. Операция умножения элементов полей Галуа вида GF((2*)')/ C.B. Шалагин // Дискретная математика и ее приложения: материалы 9-го Междунар. науч. семинара 18-22 июня 2007. - М.: Изд-во механико-матем. ф-та МГУ, 2007. -С. 136-139.

37. Шалагин, C.B. Многопараметрическая классификация устройств на базе марковских моделей / C.B. Шалагин // Инфокоммуникационные технологии глобального информационного общества: сб. тр. 5-й Междунар. науч.-практ. конф. 5-6 сент. 2007. - Казань: Изд-во «Фолианть», 2007. - С. 62-65.

38. Шалагин, C.B. Полиномиальные модели генераторов дискретных случайных величин / C.B. Шалагин // Инфокоммуникационные технологии Глобального информационного общества: сб. тр. 6-й ежегодной Междунар. науч.-практ. конф. 4-5 сент. 2008. - Казань: Центр Оперативной Печати, 2008. - С. 159-171.

39. Захаров,В.М. Параллельные марковские модели над полем GF(2")/ В.М.Захаров, C.B. Шалагин // Высокопроизводительные параллельные вычисления на кластерных системах: тез. докл. 8-й Междунар. конф. 17 - 21 нояб. 2008. - Казань: Изд-во КГТУ им. А.Н. Туполева, 2008. - С. 155-160. (л. вк. 40%).

40. Шалагин, C.B. Оценки сложности конгруэнтных псевдослучайных последовательностей по простому модулю на ПЛИС/FPGA/ C.B. Шалагин, Ф.Х. Кайбушев, Р.В. Зелинский // Методы и средства обработки информации (МСО-2009): тр. 3-й Все-рос. науч. конф. 6-8 окт. 2009. - М.: Издат. отд. ф-та ВМиК МГУ; МАКС Пресс, 2009. - С. 173-179. (л. вк. 40%).

41. Шалагин, C.B. Представимость марковских моделей системой полиномов над полем Галуа вида GF(2) / С.В.Шалагин // Методы и средства обработки информации: сб. тр. 3-й Всерос. науч. конф. 6-8 окт. 2009. -М.: МГУ, 2009. - С. 167-172.

42. Шалагин, C.B. Представимость неоднородных цепей Маркова и их стохастических функций полиномами от нескольких переменных над полем Галуа / C.B. Шалагин// Инфокоммуникационные технологии Глобального информационного общества: сб. тр. 7-й ежегодной Междунар. науч.-практ. конф. 10-11 сент. 2009. - Казань: Центр оперативной печати, 2009. - С. 134-139.

43. Шалагин, C.B. Обобщенная распределенная полиномиальная модель нелинейных преобразований над потоками чисел в конечных полях/ C.B. Шалагин// Информационные технологии в системе экономической безопасности России и ее регионов: сб. тр. III Всерос. науч. конф. 19-22 окт. 2010. - Казань: ИГМА-пресс, 2010. - С. 186-192.

44. Шалагин, C.B. Реализация многоканальных корреляционных измерителей на многопроцессорной вычислительной системе с программируемой архитектурой/ C.B. Шалагин, Ю.К. Евдокимов// Проблемы техники и технологий телекоммуникаций ПТиТТ-2011: материалы XII Междунар. науч.-техн. конф. Оптические технологии в телекоммуникациях ОТТ-2011: материалы IX Междунар. науч.-техн. конф. 21-24 ноября 2011. - Казань: Изд-во Казан, гос. техн. ун-та. 2011. - С. 163-164. (л. вк. 50%).

45. Песошин, В.А. Аппаратно-программные системы статистического моделирования и защиты информации / В.А. Песошин, В.М. Захаров, В.М. Кузнецов и др. // Проблемы и перспективы развития информационных технологий: материалы докл. Всерос. науч.-техн. конф. 10 февр. 2012. - Казань: Изд-во Казан, гос. техн. ун-та, 2012. - С. 8-21. (л. вк. 20%).

46. Шалагин, C.B. Цифровые вычислительные устройства полиномиальной функции на основе однотипных операций над полем Галуа/ C.B. Шалагин // Проблемы и перспективы развития информационных технологий: материалы Всерос. науч.-техн. конф. 10 февр. 2012. - Казань: Изд-во Казан, гос. техн. ун-та, 2012. - С. 63-73.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. А.Н.ТУПОЛЕВА - КАИ»

На правах рукописи

05201450353

Шалагин Сергей Викторович

МЕТОДЫ СИНТЕЗА УСТРОЙСТВ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ НА ОСНОВЕ НЕЛИНЕЙНЫХ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ НАД КОНЕЧНЫМ ПОЛЕМ

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

техники и систем управления

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

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

Захаров Вячеслав Михайлович

Казань - 2013

ОГЛАВЛЕНИЕ

Введение 5

Глава 1. Основные понятия и определения 23

1.1. Этапы и структурная схема общего метода синтеза 23

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

1.3. Определения теории полей Галуа и полиномиальной алгебры 34

1.4. Программируемые логические интегральные схемы класса БРвА. 38

1.5. Элементы теории цепей Маркова. 45

1.6. Методы многопараметрического анализа 48 Глава 2. Методы синтеза генераторов дискретных стохастических

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

2п) 60

2.1. Методы синтеза и анализа генераторов простых и сложных однородных цепей Маркова на основе полиномиальных марковских моделей 62

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

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

Глава 3. Устройства для вычисления значений дискретных детерминированных нелинейных функций на основе нелинейных полиномиальных преобразований над полем Галуа 89

3.1. Схемы устройств для вычисления значений ДДНФ, определенные при использовании операций над элементами поля Галуа 92

3.2. Метод синтеза устройств для вычисления ДДНФ от га переменных на основе системы из I нелинейных полиномиальных функций от т ■ I переменных 103

3.3. Метод синтеза генераторов неоднородных цепей Маркова и их функций на основе цифровых устройств для вычисления ДДНФ 109

Глава 4. Схемы функциональных модулей операций в конечных полях 115

4.1. Функциональные модули операции умножения элементов поля GF(2n) как 1Р-ядра. 118

4.2. Функциональные модули операции умножения элементов расширений поля GF((2k)f ) на основе 1Р-ядер 126

4.3. Схемы функциональных модулей операции вычисления остатка от деления по заданному простому модулю для потока чисел 136

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

IP-ядер, представленных на ПЛИС/FPGA 146

5.1. Методика оценки степени соответствия функционального модуля архитектуре ПЛИС/FPGA 149

5.2. Методика синтеза устройств ВТ на основе IP-ядер на распределенных вычислительных системах с программируемой архитектурой

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

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

6.1. Генераторы ДСП класса марковских и их функций на РВС ПА «Медведь» 185

6.2. Устройства ВТ определенных подклассов теоретико-полиномиальных преобразований на РВС ПА «Медведь» 187

6.3. Анализ степени соответствия архитектуре ПЛИС/FPGA функциональных модулей операции умножения элементов полей

вида GF(2") и Gf((2*)') 196

6.4. Синтез функциональных модулей операции вычисления остатка от деления по заданному модулю для потока чисел на ПЛИС/FPGA 214

6.5. Схема устройства ВТ для отображения и варьирования состояния дискретной модели KMC(N) и ее частных случаев 221

153 161

182

Заключение. 236

Список сокращений и условных обозначений. 242

Список литературы. 244

Приложение 1 268

Приложение 2 274

Приложение 3 288

Введение

В настоящее время особую актуальность приобрела проблема, связанная с генерированием и обработкой массивов данных, представленных в цифровой форме и имеющих большую размерность, за ограниченный период времени. Данная проблема актуальна при решении широкого круга задач, таких, как вычисление и/или анализ элементов дискретных стохастических процессов класса марковских и их функций, а также цифровая обработка сигналов (ЦОС). При решении указанных задач, связанных с обработкой большого количества оцифрованных данных в реальном масштабе времени, находят применение устройства вычислительной техники (ВТ), обеспечивающие высокое быстродействие, не достижимое на ЭВМ общего назначения. Один из подходов к разрешению указанной проблемы - организация распределенных вычислений (РасВ), под которыми будем понимать способы решения вычислительных задач с использованием двух и более вычислительных устройств с применением как распараллеливания вычислительного процесса [38 - 39, 69, 71, 150, 152, 181, 189, 258, 346, 367], так и потоковой обработки данных с сохранением промежуточных результатов [75 - 77, 153, 184, 316]. Потоковой названа обработка массивов данных при использовании однотипных операций [38 - 39, 69, 71, 152, 189, 258, 346, 357]. Для решения указанного класса задач эффективны распределенные вычислительные системы с программируемой архитектурой (РВС ПА) [68, 96, 139 - 140, 171 - 172, 245 - 246], элементами которых являются сконфигурированные программируемые логические интегральные схемы (ПЛИС) класса FPGA [128, 160, 265, 355 - 356, 361 - 363].

Известны результаты по представлению генераторов массивов равномерно распределенных случайных и псевдослучайных чисел большой размерности на основе полиномиальных функций над конечным полем (Алферов А.П., Винокуров В.И., Ганнтмахер В.Е., Гилл А., Кирьянов Б.Ф. Иванов М.А., Кузнецов В.М., Песошин В.А., Шнайер Б. и др.) [2, 4 - 8, 10 - 12, 29, 32, 67, 74, 83, 129 -130, 161, 219, 226, 300, 305, 329 - 330, 333, 364]. Существует подход к представлению генераторов дискретных стохастических процессов (ДСП) из классов однородных и неоднородных цепей Маркова (ЦМ) и их функций, на основе ве-

роятностных автоматов (ВА) [55 - 57, 59, 217], в общем случае - нелинейных систем. Такие генераторы находят применение в таких областях как построение вероятностных моделей алгоритмов для решения задач защиты информации, статистическое моделирование, распознавание образов, кодирование и декодирование информации, техническая диагностика цифровых устройств, обработки сигналов в системах связи и управления. Поэтому исследование вопросов синтеза генераторов ДСП данного класса имеет важное теоретическое и прикладное значение. Указанный подход, определенный как автоматный, отражен в многочисленных публикациях (Аблаев Ф.М., Альпин Ю.А., Баканович Э.А., Бусленко Н.П., Бухараев Р.Г., Гилл А., Гиоргадзэ А.Х., Гладкий B.C., Глова В.И., Захаров В.М., Кемени Дж., Левин Б.Р., Кирьянов Б.Ф., Лоренц A.A., Нур-меев H.H., Нурутдинов Ш.Р., Песошин В.А., Полляк Ю.Г., Поспелов Д.А., Салимое Ф.И., Столов ЕЛ., Хамитов Г.П., Ченцов В.М., Чирков М.К., Шварц В., Яковлев В.В., Paz А. и др.) [18 - 19, 30, 54 - 60, 72 - 73, 75 - 80, 86, 98 - 101, 145, 148, 154, 170, 177 - 178, 188, 193 - 194, 196,211 -213,215-219, 252 - 253,263, 306, 342 - 343, 357]. Вместе с тем, реализация автоматных функций на ПЛИС/FPGA без адаптации под архитектуру ПЛИС/FPGA сопряжена с большими дополнительными затратами аппаратных ресурсов из-за неполного задействования однотипных конфигурируемых элементов ПЛИС/FPGA, реализующих любую булеву функцию (БФ) от R< 5, переменных. Решение задачи адаптации более эффективно для системы БФ, пересечение по аргументам между которыми будет минимальным [41]. Известные подходы, основанные на использовании аппарата алгебры логики, не ориентированы на базис ПЛИС/FPGA, где R < 5, а декомпозиция Шеннона является нерациональной по оценкам временной и аппаратной сложности, т.к. схема имеет древовидную структуру (Баркалов A.A. и др.) [41]. Примем в качестве меры аппаратной сложности однотипный конфигурируемый элемент ПЛИС/FPGA, где R < 5, а в качестве меры временной сложности - время задержки функционирования указанного элемента (?е/). Тогда реализация БФ от D переменных на основе декомпозиции Шеннона предполагает мультиплексирование 2D~R БФ от R перемен-

ных [350], при этом нижняя оценка временной и оценка аппаратной сложности составляют (D-R) tel и ¡2D~R+l -1), соответственно, для R <5.

Представление генераторов ДСП класса марковских и их функций на основе однотипных операций над конечным полем позволяет производить распределенные, непересекающиеся по аргументам вычисления, что повышает эффективность реализации потоковых преобразований над «-разрядными двоичными векторами. Задача определения генераторов простых однородных ЦМ на основе нелинейных полиномиальных функций (НПФ), представленных на основе операций над полем GF(2"), впервые решена в 1999-2001 гг. (Захаров В.М., Нурутдинов Ш.Р., Шалагин C.B.) [107, 109]. Затем данный подход был распространен на генераторы однородных /-сложных ЦМ и их детерминированных и стохастических функций, а также на генераторы неоднородных ЦМ (Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B., Эминов Б.Ф.) [105 - 107, 113 - 115, 118 - 123, 194 - 195, 281, 284, 302]. В диссертации докт. физ.-мат. наук Нурутдинова Ш.Р. (2005 г.) дано развитие конечно-автоматных преобразований на базе нелинейных полиномиальных функций от двух переменных в рамках исследования проблемы моделирования автоматов различных видов (комбинационных схем, детерминированных и вероятностных автоматов, цепей Маркова) полиномами над полем Галуа вида GF{2") [192 - 194]. Решена задача уменьшения количества ненулевых коэффициентов НПФ путем доопределения неопределенных значений функции на заданных наборах [190, 194, 199].

Развитие теоретических основ представления ВА на основе операций в конечных полях над потоками дискретных случайных величин открывает возможность для разработки эффективных методов синтеза на ПЛИС/FPGA генераторов дискретных стохастических процессов класса марковских и их функций на основе распределенного, непересекающегося по аргументам и адаптированного под архитектуру ПЛИС/FPGA вычисления значений НПФ, определенных над конечным полем [26, 44-45, 174, 244, 261].

Известен аппарат теоретико-полиномиальных преобразований (ТИП) -дискретных преобразований, определенных на основе теории полиномиальных вычетов, ориентированный на задачи анализа и синтеза динамических систем, описываемых вещественными числами (Крот A.M., Минервина Е.Б. и др.) [155 - 157]. Частные случаи ТИП - широко применяемые на практике дискретные преобразования Фурье (ДПФ) и Хартли (ДПХ), а также алгоритмы цифровой фильтрации сигналов. Существует большое количество работ по синтезу цифровых устройств, реализующих данные подклассы дискретных преобразований (Аксенов И.Б., Гоулд Б., Оппенгейм A.B., Рабинер Д., Райхлин В.А., Уеркли Дж., Шафер Р.В. и др.) [23, 81, 163, 203 - 205, 207, 221 - 222, 234, 307, 335, 360], в частности, по представлению ДПФ (Гольденберг JI.M., Матюшкин Б.Д., Поляк М.Н., Cooley J.W., Tukey J.W. и др.) [81, 203 с.75-102, 320], в том числе - в полях Галуа (Афанасьев В.Б., Грушко И.И., Захарова Т.Г., Трифонов П.В., Федоренко C.B. и др.) [33, 124, 175, 247]. В частности, известен подход к синтезу устройств вычислительной техники (ВТ) для определенных алгоритмов цифровой обработки сигналов (ЦОС) - ДПФ и цифровых фильтров, на основе системы остаточных классов, обеспечивающий повышение скорости выполнения отдельных операций на уровне реализации на ПЛИС класса FPGA (Акуш-ский И.Я., Галанина H.A., Лебедев Е.К., Юдицкий Д.М. и др.) [24, 70, 163]. Дискретные функции Уолша как подкласс T111I находят применение в автоматизированных системах управления, в частности, для сжатия цифровых изображений (Исмагилов И.И. и др.) [65, 132]. Однако, вопросы адаптации широкого класса устройств ЦОС, описываемых на основе нелинейных полиномиальных преобразований над конечным полем, под распределенную архитектуру ПЛИС/FPGA, исследованы не достаточно.

Данные обстоятельства определяют предпосылки к созданию общего метода синтеза [289] при использовании однотипных специализированных цифровых вычислительных устройств, ориентированных на архитектуру ПЛИС/FPGA и описываемых НПФ над конечным полем, для: 1) генераторов дискретных стохастических процессов класса марковских и их функций [105 -106, 108, 110, 113 - 115, 118 - 120, 195, 284, 287, 289, 295]; 2) устройств ВТ, вы-

полняющих ЦОС [286]. Для решения задачи синтеза (или создания прототипов) таких классов устройств ВТ как «система на кристалле», встраиваемые и портативные системы, широкое распространение получили IP-ядра (англ. Intellectual Property - интеллектуальный продукт) - готовые блоки, применяемые для проектирования микросхем и представленные на уровне абстрактного описания, на функциональном и на физическом уровнях [128 - 129, 160, 249, 265]. При ограничениях на быстродействие и размер занимаемой площади микросхемы, IP-ядра позволяют существенно ускорить процесс синтеза устройств ВТ на микросхемах, в том числе, на ПЛИС/FPGA [160, 308, 355 - 356, 361 - 363], представляющих собой однородную вычислительную структуру (ОВС) [94, 159, 235]. При решении задач синтеза устройств ЦОС, использование подходов на базе IP-ядер позволяет синтезировать на ПЛИС/FPGA цифровые сигнальные процессоры (англ. DSP, digital signal processor) как на алгоритмическом и программном уровнях, при использовании языка VHDL, так и на физическом уровне, на базе спец. DSP, встроенных в кристалл ПЛИС - XtremeDSP, Pi-coBlaze, MicroBlaze и т.п. (Зотов В.Ю., Шагурин И.И., B.Afra, S.Y.Kulkarni, P.Moakes, D.Pellerin, E.Young и др.) [128, 160, 265, 315, 344, 347, 353, 368]. Вместе с тем, вопросы синтеза цифровых устройств, выполняющих нелинейные полиномиальные преобразования, в конечных полях на ПЛИС/FPGA при использовании IP-ядер, изучены не достаточно.

Для решения вычислительно трудоемких задач генерирования и обработки массивов данных большой размерности применимы РВС ПА. В настоящее время созданы РВС ПА различного назначения: «Скиф-Т» на 256 процессоров, 20 Гфлопс (2003 г.), «Рысь» на 512 процессоров, 50 Гфлопс (2004 г.), «Медведь» на 1280 процессоров, 200 Гфлопс (2006 г.) и др. Указанные системы выполнены при использовании унифицированных базовых модулей - многопроцессорных реконфигурируемых вычислителей на основе ПЛИС/FPGA. РВС ПА позволяют реализовать различные устройства ВТ, реконфигурируемые в реальном времени, что находит применение для таких областей, как символьная обработка информации, защита компьютерных сетей, управление в реальном масштабе времени объектами энергетики, летательными и космическими аппаратами и т. п.

(Каляев И.А., Левин И.И., Макаревич О.Б., Семерников Е.А., Шмойлов В.И. и др.) [68, 89, 139 - 142, 171 - 172, 245 - 246]. В данной связи перспективной является задача синтеза устройств как для генерирования дискретных стохастических процессов класса марковских и их функций, так и для ЦОС, на РВС ПА при использовании однотипных IP-ядер, описываемых на основе нелинейных полиномиальных преобразований над конечным полем. Анализ оценок временной и аппаратной сложности синтеза таких IP-ядер на ПЛИС/FPGA позволяет получить аналогичные оценки для данных устройств ВТ, синтезируемых на РВС ПА, элементами которой являются сконфигурированные ПЛИС/FPGA. В соответствии с требованиями, предъявляемыми к синтезируемым на РВС ПА устройствам по быстродействию и количеству задействованных процессорных элементов, актуальна задача адаптации указанных IP-ядер под архитектуру ПЛИС/FPGA.

Известно представление дискретных детерминированных нелинейных функций (ДДНФ) вида у/(хi,...,xm)=y, где лг,,..., хт, у - и-разрядные двоичные

числа, на основе НПФ над GF(2") на абстрактном уровне (Лидл Р., Нидеррай-тер Г. 1988) [174]. В ряде работ (Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. и др.) исследовано применение частных случаев НПФ, m = 1,2, для решения задач синтеза генераторов дискретных стохастических процессов (ДСП) класса марковских и их функций [105 - 106, 114 - 115, 123, 195, 302]. Теоретически обоснован алгоритм синтеза произвольной булевой функции (БФ) на основе НПФ над GF(2) - полиномов Жегалкина И.И. (Чебура-хин И.Ф.) [262]. В настоящее время существуют микросхемы ПЛИС/FPGA [128- 129, 355 - 357, 361 - 363], количество реконфигурируемых элементов внутри которых позволяет реализовать цифровые устройства для вычисления произвольной БФ от 20-ти переменных как 1Р-ядро [292]. Вместе с тем, вопросы синтеза устройств для вычисления значения у/{хх,..., хт), где m - произвольное, на основе системы НПФ над полем Галуа изучены не достаточно. Данное обстоятельство актуализирует исследование задач синтеза устройств ВТ для

ДДНФ на основе однотипных IP-ядер, вычисляющих заданную НПФ и ориентированных на архитектуру ПЛИС/FPGA.

Для решения задачи синтеза устройств ВТ на ПЛИС/FPGA применимы однотипные функциональные модули (ФМ), описываемые нелинейными полиномиальными преобразованиями над конечным полем [110, 118, 120, 194 - 195]. Известно, что отдельные операции, в частности, операции умножения элементов поля вида GF(2") и GF((2к)г), п = к-г, (обозначим их ОУ IGF(T) и О У/GF((2k)r), соответственно) допускают организацию распараллеливания вычислений и потоковой обработки данных (Алексеев В.Б., Лидр Р., Ниддер-райтер Г., Нурутдинов 1П.Р., Сюрин В.Н. и др.) [25 - 27, 44 - 45, 52, 244]. Решены частные задачи синтеза ФМ, выполн