Введение к работе
Актуальность темы. Важнейшими областями применения цифровой обработки сигналов (ЦОС) является биомедицина, акустика, звуковая локация, радиолокация, сейсмология, ядерная техника, обработка изображений и др. К числу основных направлений ЦОС относятся цифровая фильтрация и спектральный анализ. Исследование повышения быстродействия и вычислительной точности алгоритмов ЦОС актуально, несмотря на наличие процессоров ЦОС с производительностью нескольких миллиардов комплексных умножений/сек. При реализации основных алгоритмов ЦОС таких, как свертка, корреляция, ковариация, необходимо вычислять элементарные функции (базисные функции ортогональных разложений). Объем и точность их вычисления в значительной мере влияют на быстродействие и точность ЦОС. Помимо актуальности быстрого вычисления функций базиса ортогональных разложений, существует широкий круг задач с большим объемом вычисления функций, где требуется высокая скорость и точность аппроксимации. К категории таких задач относятся задачи гидро- и аэродинамики, задачи по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных физических и химических процессов. Задачи управления движением летательных аппаратов, включая гидросамолеты, требуют эффективных способов улучшения аэродинамических характеристик, при этом в описании законов векторного управления пространственным движением используются тригонометрические функции на каждом шаге управляющих воздействий. В практических приложениях часто необходимо вычислять значения рациональных, степенных, тригонометрических, обратных тригонометрических, показательных, логарифмических, гиперболических и обратных гиперболических функций. При этом к методам их вычисления предъявляются требования одновременно высокого быстродействия, вычислительной устойчивости, высокой точности аппроксимации и универсальности схем вычислений. Значительные объемы вычисления элементарных функций и функций специального вида могут включать задачи моделирования управлением различными техническими и технологическими процессами, задачи моделирования физических процессов различной природы. Такие задачи необходимо решать в строго ограниченное время или в режиме реального времени, поэтому схемы вычисления функций должны быть оптимизированы по временной сложности. Применение быстродействующих алгоритмов вычисления функций в задачах ЦОС позволяет сократить аппаратурные и вычислительные затраты, снизить стоимость устройств или систем, уменьшить габариты, массу и энергопотребление, что особенно важно для бортовых систем и систем с автономным питанием.
Цель диссертационной работы состоит в разработке и исследовании компьютерных схем минимизации временной сложности вычисления функций с обеспечением инвариантности алгоритмов относительно вида функций, точности их вычисления, промежутка изменения аргумента. Оптимизированные алгоритмы должны применяться в качестве основы для параллельного вычисления одновременно всех элементов базиса ортогональных разложений, используемых в ЦОС, и при этом отличаться инвариантностью относительно вида разложений, быть совместимыми с параллельным выполнением базового набора операций ЦОС в целом.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
1. Средствами информатики построить устойчивую распараллеливаемую схему минимизации временной сложности таблично-алгоритмического вычисления функций на основе интерполяции по Ньютону, которая была бы инвариантна относительно вида функции, промежутка изменения аргумента и априори заданной границы погрешности.
2. Распространить исследуемую схему на компьютерное вычисление производных и определенных интегралов с сохранением инвариантности относительно вида функции, устойчивости, параллелизма и минимальности временной сложности для произвольно заданной границы погрешности.
3. Осуществить программную реализацию синтезированной таблично-алгоритмической схемы, выполнить численный эксперимент по практической проверке инвариантности, устойчивости и точности вычисления функций при условии минимальной временной сложности схемы.
4. Разработать метод параллельного вычисления всех последовательных элементов тригонометрического базиса дискретного преобразования Фурье (ДПФ) с временной сложностью , который отличался бы инвариантностью относительно количества отсчетов и сохранял данный порядок оценки при параллельном выполнении ДПФ и обратного дискретного преобразования Фурье (ОДПФ) в целом.
5. Синтезировать алгоритм параллельного выполнения ДПФ и ОДПФ на основе таблично-алгоритмической аппроксимации всех элементов базиса с временной сложностью , который отличался бы минимизированным до значения числом последовательных умножений, а также инвариантностью относительно количества отсчетов в условиях произвольно заданной границы погрешности вычислений.
6. Распространить синтезированные параллельные алгоритмы на выполнение совокупности схем ЦОС, включая операции корреляции, свертки, ковариации, быстрого преобразования Фурье (БПФ), двумерные ДПФ и ОДПФ с логарифмическими оценками временной сложности в условиях инвариантности относительно количества отсчетов.
Методы исследования опираются на теоретические основы информатики и информационные технологии, на методы прикладной информатики, численного анализа, теории сложности, теоретические и прикладные методы ЦОС.
Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, представленными в форме доказательных утверждений и теорем, детально иллюстрируется результатами программного моделирования и численного эксперимента.
Научная новизна заключается в следующем:
1. Синтезирована динамически распараллеливаемая компьютерная схема минимизации временной сложности таблично-алгоритмической аппроксимации функций на основе интерполяции по Ньютону, которая отличается от известных аналогов построением с помощью матричного параллельного видоизменения формул Виета, инвариантностью относительно вида функции, промежутка изменения аргумента и априори заданной границы погрешности.
2. На основе использования средств информатики выполнено распространение таблично-алгоритмической аппроксимации функций для случая вычисления производных и определенных интегралов с сохранением свойств инвариантности относительно вида функции, устойчивости, параллелизма и минимальности временной сложности в условиях произвольно заданной границы погрешности. Показано, что динамически распараллеливаемая схема таблично-алгоритмического вычисления функций, производных и определенных интегралов применима для синхронизации параллельных процессов вычисления данных функциональных зависимостей в параллельных вычислительных системах с перестраиваемой архитектурой.
3. Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма, – предложенные схемы ускоряют известные методы в , где – степень аппроксимирующего полинома, и позволяют достигать времени параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций.
4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью , который отличается инвариантностью относительно количества отсчетов и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в целом. В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов заключается в сокращении до количества последовательных умножений в условиях произвольно заданной границы погрешности вычислений.
5. Предложены модификации параллельных схем выполнения ДПФ для параллельного выполнения БПФ и вычисления частичной суммы ряда Фурье. Разработанные схемы распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей операции корреляции, свертки, ковариации и ОДПФ, при этом сохраняется логарифмический порядок оценок временной сложности. Видоизменения данных схем с сохранением порядка оценок распространяются на случай двумерных ДПФ и ОДПФ. Предложенные схемы отличаются от известных аналогов построением, сокращением числа последовательных умножений и, в частности, тем, что число процессоров модифицированного БПФ сокращается в раз при сохранении логарифмической оценки временной сложности вычисления.
6. Выполнено сравнение предложенных схем параллельной ЦОС с известными параллельными методами, при этом показано, что предложенные схемы, в целом, отличаются инвариантностью относительно числа отсчетов, быстродействием в условиях повышенной точности вычисления и общностью для комплекса алгоритмов цифровой обработки. Синтезированная динамически распараллеливаемая схема таблично-алгоритмического вычисления элементов базиса преобразований Фурье позволяет сохранить быстродействие в условиях произвольно заданной границы погрешности вычислений, распараллеливаемая настройка схемы на динамически изменяющиеся параметры может осуществляться в режиме реального времени.
Основные положения, выносимые на защиту:
1. С помощью средств информатики построена динамически распараллеливаемая схема минимизации временной сложности таблично-алгоритмической аппроксимации функций на основе интерполяции по Ньютону, схема опирается на параллельное видоизменение формул Виета, инвариантна относительно вида функции, промежутка изменения аргумента и априори заданной границы погрешности.
2. На основе средств информатики таблично-алгоритмическая аппроксимация функций распространяется на случаи вычисления производных и определенных интегралов с сохранением инвариантности относительно вида функции, качества устойчивости, параллелизма и минимальности временной сложности в условиях произвольно заданной границы погрешности.
3. Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма. Предложенные схемы ускоряют известные методы в , где – степень аппроксимирующего функцию полинома, и позволяют достигать времени параллельного выполнения комплекса данных вычислительных схем для априори заданных функций.
4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью , инвариантный относительно количества отсчетов , который сохраняет порядок данной оценки при параллельном выполнении ДПФ и ОДПФ в целом. При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до в условиях произвольно заданной границы погрешности вычислений.
5. Разработаны модификации предложенных схем ДПФ для параллельного вычисления БПФ и частичной суммы ряда Фурье, которые распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей операции корреляции, свертки, ковариации и ОДПФ, при этом сохраняется логарифмический порядок оценок временной сложности. Данные схемы с сохранением порядка оценок распространяются на двумерные ДПФ и ОДПФ.
6. Схема таблично-алгоритмического вычисления элементов базиса преобразований Фурье позволяет сохранить быстродействие в условиях произвольно заданной границы погрешности вычислений, распараллеливаемая настройка схемы на динамически изменяющиеся параметры может осуществляться в режиме реального времени.
Практическая ценность диссертационного исследования заключается в прикладном характере разработанных схем последовательного и параллельного вычисления функций, производных и определенных интегралов при условии минимизации временной сложности. Предложенные методы доведены до практической программной реализации, применимы для решения актуальных задач ЦОС. На основе предложенных схем минимизации временной сложности вычисления функций могут создаваться новые библиотеки стандартных подпрограмм, ориентированные на практическое применение в быстродействующих вычислительных системах, а также новые системы параллельной ЦОС.
Внедрение и использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» в качестве единой распараллеливаемой схемы минимизации кусочно-полиномиальной аппроксимации функций применительно к основным алгоритмам ЦОС; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО «ТГПИ»; в учебном процессе кафедры информатики Таганрогского государственного педагогического института в курсах «Математика и информатика», «Численные методы», «Компьютерное моделирование», курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 3 к диссертационной работе.
Апробация работы. Основные результаты работы докладывались на: международной научно-технической конференции «Математические модели и алгоритмы для имитации физических процессов» (Таганрог, ТГПИ, 2006 г.); the Fourth International Conference «Theoretical and Applied Aspects of Program Systems Development» (Ukraine, Berdyansk, 2007); XII международной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2007 г.); VII международной научно-технической конференции «Математическое моделирование, обратные задачи, информационно-вычислительные технологии» (Пенза, ПГУ, 2007); всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008).
Публикации. По материалам диссертационной работы опубликовано 11 печатных работ с общим объёмом 10,3 печатных листов, в том числе, статья в журнале из списка допущенных ВАК РФ.
Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и 3 приложений. Основное содержание работы изложено на 154 страницах, включая 33 таблицы, 4 рисунка и список литературы из 113 наименований.
