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

Актуальность темы

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

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

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

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

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

Исследования в области нейросетевых технологий поддерживаются Российским фондом фундаментальных исследований. С 1992 г. в России издается научно-технический журнал «Нейрокомпьютер». По данной тематике ежегодно проводится большое число конференций и симпозиумов. Работа выполнена в рамках исследований Государственной целевой комплексной программы (Постановление правительства РФ № 945−95 от 28.08.96 г.).

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

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

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

Как в отечественных, так и в зарубежных работах, посвященных вопросу построения естественно-надежных распределенных систем, все чаще ставится задача использования разнотипных специализированных микропроцессоров. Функциональная специализация — это один из наиболее интересных способов комплексирования цифровых вычислительных машин, который может быть организован на основе разнотипных машин. Известно, что процессоры, функционирующие в непозиционной системе счисления СОК, обладают высоким быстродействием выполнения арифметических операций. В то же время позиционные микропроцессоры более эффективно выполняют логические операции и операции вводавывода. При организации распределенной системы «ЭВМ-сопроцессор» образовывается распределенная вычислительная система с множественным представлением информации, которая позволяет реализовать достоинства разнотипных микропроцессоров. При создании подобной вычислительной системы одной из определяющих специфических задач является задача взаимодействия между элементами системы. При этом целесообразно обеспечить максимальную пропускную способность и производительность системы.

Цель диссертационных исследований состоит в повышении скорости обработки информации в распределённой вычислительной системе «ЭВМ-сопроцессор», базирующейся на множественном представлении информации.

Научная задача исследований состоит в разработке новых численных методов и алгоритмов для эффективной реализации вычислительных операций модулярного нейроподобного анализатора спектра (МНАС) и алгоритмов сопряжения МНАС с центральным процессором ЭВМ.

Для решения поставленной общей научной задачи разобьем её на ряд частных задач:

1. Обоснование адекватности математических моделей при переходе от выполнения действий с многоразрядными числами к вычислениям с малоразрядными числами и выбор типа (модификации) СОК и набора ее оснований, обеспечивающих высокую скорость вычислений БПФ.

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

3. Разработка и математическое моделирование высокоскоростного вычисления базовых модулярных операций БПФ (сложение, умножение, вычисление тригонометрических функций) и реализация их табличными схемами.

4. Реализация эффективных численных методов модулярного вычисления на многослойных структурах нейронных сетей, если в операциях «бабочка» БПФ коэффициенты преобразования отождествить с перестраиваемыми весами синапсов, и тогда нейроны являются арифметическими элементами, которые имеют характеристики оператора по модулю, а не обычные нелинейные функции активации, применяемые при обучении нейронной сети.

5. Разработка вычислительного алгоритма для организации информационного обмена между ЭВМ и сопроцессором и обработки в них данных, базирующихся на множественном представлении информации.

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

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

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

2. Разработаны математические модели быстрых процедур БПФ (алгоритма Ъпреобразования с ЛЧМ) в полной мере согласующиеся с модулярными принципами высокоскоростной параллельной обработки цифровой информации.

3. Предложены новые численные методы высокопараллельных процедур преобразования из системы остаточных классов (СОК) в позиционную систему счисления (ПСС) через промежуточную обобщенную полиадическую систему счисления (ОПСС).

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

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

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

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

Каждое вычислительное устройство функционирует по какому-либо алгоритму, который, в конечном итоге, и определяет его структуру. Самый перспективный способ обработки данных — параллельно-конвейерный. Класс алгоритмов, который можно реализовать на параллельно-конвейерных структурах имеет свои особенности: алгоритмы должны быть вычислительноограниченными и локально рекурсивными. Кроме того, для вычисления БПФ, должна быть эффективно реализована возможность обработки комплексных данных. На основе анализа вычислительной сложности известных быстрых алгоритмов ДПФ, а также с учетом перечисленных требований в работе осуществлен выбор рационального алгоритма — Ъ ~ преобразования с ЛЧМ и ставится задача поиска путей повышения его эффективности.

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

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

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

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

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

В третьем разделе исследуются вопросы информационной совместимости модулярного нейроподобного сопроцессора с центральным процессором ЭВМ. Для решения задачи сопряжения микропроцессоров с различными диапазонами представимых чисел, с различной формой представления чисел, с различными системами счисления разработан алгоритм, позволяющий сохранить заданную точность и однозначность представления при обработке и передаче информации. Функция сопряжения возложена на интерфейсный микропроцессор, также выполняющий функции перераспределения информации в случае выхода из строя какой-либо из компонент распределенной вычислительной системы «ЭВМ-сопроцессор».

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

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

В заключении обобщены итоги и результаты исследований. В приложении 1 оценены затраты современных процессоров ЦОС на выполнение ДПФ различной длительности. В приложении 2 приведены расчеты логарифмических дефектов оснований системы остаточных классов. В приложении 3 приведены результаты исследования совместимости различных модификаций СОК с систолической архитектурой. В приложении 4 проведен расчет производительности многоканальной систолической матрицы при вычислении ДПФ в ПСС и СОК, в приложениях 5,6 — временных и аппаратурных затрат на выполнение свертки и ДПФ в ПСС и СОК. На защиту выносятся следующие основные положения:

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

2. Математические методы для исследования вычислительных структур при выполнении основных операций БПФ.

3. Математические методы моделирования модулярных процессоров, выполняющих основные операции над данными, представленными в СОК.

4. Математическая модель модулярного нейроподобного анализатора спектра.

5. Алгоритм сопряжения модулярного нейроподобного сопроцессора с центральным процессором ЭВМ.

Апробация работы. На всероссийской конференции «Математическое моделирование в научных исследованиях» (СГУ, Ставрополь, 2000 г.), на.

13 межрегиональной конференции «Вузовская наука — Северо-Кавказскому региону» (Сев-Кав ГТУ, Ставрополь, 1999 г.), на научно-технических конференциях Ставропольского Государственного Университета, СевероКавказского Государственного Университета, ставропольского филиала РВИ РВ в период с 1994 по 2001 г. Полученные результаты достаточно полно изложены в 8 статьях, 23 тезисах докладов.

Реализация результатов исследования. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР «Новый класс нейронных цифровых фильтров параллельной обработки данных» номер Государственной регистрации № 01.02.105 057 по гранту Министерства образования РФ ТОО-3.3−292, реализованы в ВНИИС (г. Воронеж) в ходе проведения ОКР «Бланк», при разработке блока ЦОС в рамках НИР ХД 401−98 и в учебном процессе СевКавГТУ.

Автор выражает искреннюю благодарность научным руководителямзаслуженному деятелю науки и техники РФ, доктору технических наук, профессору, академику МАИ Н. И. Червякову и кандидату физико-математических наук, доценту Галкиной В. А., а также коллективу кафедры «Информационных систем и технологий» за помощь, оказанную при написании диссертации, и критические замечания, высказанные при её обсуждении.

Основные результаты, полученные в ходе исследований можно свети к следующим:

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

О 1Л производительность 10 -10 операций в секунду и обработку сигналов разрядностью 8−16 бит. При этом накладываются ограничения на аппаратурные затраты.

2. Сравнение требований к производительности и точности современных вычислительных структур ЦОС с предложениями отечественной и зарубежной промышленности показало, что существующие процессоры ДПФ способны обеспечить максимальную производительность П=3,3'10. Сделан вывод о том. что проблема повышения производительности требует качественного решения на уровнях совершенствования функционирования вычислительных структур.

3. Определено, что для использования в параллельно-конвейерных структурах, обрабатывающих комплексные данные более рациональным является алгоритм ДПФ на основе /-преобразования с ЛЧМ. Выявлена актуальность задачи повышения эффективности данного алгоритма.

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

5. Произведен анализ и исследование влияния различных модификаций СОК на производительность вычислительных структур ЦОС при выполнении ДПФ. Показано, что КвСОК требует наименьшего количества вещественных операций. Для выполнения комплексного умножения потребуется две вещественные операции, сложение производится независимо (параллельно). Проанализирована возможность совмещения модификаций с систолической архитектурой и определено, что для высокоскоростных специализированных процессоров, обрабатывающих комплексные данные могут быть использованы следующие модификации СОК: КвСОКМКвСОККСОК. Наименьшей сложностью при выполнении обобщенную позиционную систему счисления и предложен вариант преобразования комплексных чисел. При этом временные затраты на обратный перевод составляют 5−6 модульный тактов.

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

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

14. Рассмотрены особенности выполнения арифметических операций с непозиционными числами, представленными в полулогарифмической форме. Показано, что быстродействие микропроцессора, в котором мантисса и порядок представлены в СОК, в «1,5 раза выше, чем в микропроцессоре, работающем при комбинированном представлении информации ив «10 раз выше по сравнению с микропроцессором, работающем в позиционной системе счисления.

15. Проведена оценка влияния квадратичной системы остаточных классов на производительность разработанных вычислительных структур спектрального анализа. Проведен сравнительный анализ производительности многоканальных систолических матриц, функционирующих в квадратичной системе остаточных классов и в обычной системе счисления. Показано, что использование КвСОК позволяет повысить производительность МСМ в числе базовых операций до значений 10 ю-1012 оп/сек.

16. Проведена оценка скоростных характеристик разработанных вычислительных структур. При этом выполнена сравнительная оценка скорости выполнения как всего алгоритма 2-преобразования с ЛЧМ, так и операции свертки при использовании ПСС и КвСОК. Показано, что при использовании квадратичной системы остаточных классов временные затраты разработанных структур на вычисление ДПФ и свертки на порядок ниже аналогичных структур в ПСС.

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

18. Получена оценка эффективности использования разработанных вычислительных структур. Проведена сравнительная оценка с аналогичными структурами, функционирующими в ПСС. Показано, что эффективность использования разработанного специализированного процессора КвСОК в 1,5 раза выше, чем у аналогичного процессора ПСС серии ТМ8320С30.

19. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР «Новый класс нейронных цифровых фильтров параллельной обработки данных» номер Государственной регистрации № 01.02.105 057 по гранту Министерства образования РФ ТОО-3.3−292, реализованы в ВНИИС (г. Воронеж) в ходе проведения ОКР «Бланк», при разработке блока ЦОС в рамках НИР ХД 401−98 и в учебном процессе СевКавГТУ.

Продолжение научных исследований в данной области целесообразно проводить в следующих направлениях:

Исследование вопросов обеспечения необходимого уровня производительности при выполнении алгоритма Ъ — преобразования с ЛЧМ с последовательностями намного большей длины.

ЗАКЛЮЧЕНИЕ

.

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

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