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

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

Аксайская Любовь Николаевна

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

Специальность- 003 170906

05.13.17- Теоретические основы информатики

05 13 18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

2 9 ®

Таганрог 2008

003170906

Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт»

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

профессор Ромм Яков Евсеевич

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

профессор Финаев Валерий Иванович

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

Ведущая организация Ростовский государственный университет путей сообщения (РГУПС)

Защита состоится << в 14 20 на заседании диссертационного совета

Д 212 208 21 Южного федерального университета по адресу ауд Д-406, пер Некрасовский, 44, г Таганрог, Ростовская область, ГСП-17 А, 347928

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу 344000, Ростов-на-Дону, ул Пушкинская, 148.

Автореферат разослан <^>>>^^1^-2008 г

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

диссертационного совета Д 212 208 21 доктор технических наук, профессор

Чернов Н И

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

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

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

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

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

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

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

4 Разработать метод параллельного вычисления всех последовательных элементов тригонометрического базиса дискретного преобразования Фурье (ДПФ) с временной сложностью Т=0{\о%ги), который отличался бы инвариантностью относительно количества отсчетов и со-

хранял данный порядок оценки при параллельном выполнении ДПФ и обратного дискретного преобразования Фурье (ОДПФ) в целом

5 Синтезировать алгоритм параллельного выполнения ДПФ и ОДПФ на основе таблично-алгоритмической аппроксимации всех элементов базиса с временной сложностью Т~ O(log2 N), который отличался бы минимизированным до значения o(l) числом последовательных умножений, а также инвариантностью относительно количества отсчетов в условиях произвольно заданной границы погрешности вычислений

6 Распространить синтезированные параллельные алгоритмы на выполнение совокупности схем ЦОС, включая операции корреляции, свертки, ковариации, быстрого преобразования Фурье (БПФ), двумерные ДПФ и ОДПФ с логарифмическими оценками временной сложности в условиях инвариантности относительно количества отсчетов

Методы исследования опираются на теоретические основы информатики и информационные технологии, на методы прикладной информатики, численного анализа, теории сложности, теоретические и прикладные методы ЦОС

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

Научная новизна заключается в следующем

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

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

3 Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма, - предложенные схемы ускоряют известные методы в O(log2 m), где m - степень аппроксимирующего полинома, и позволяют достигать времени 0( 1) параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций

4 Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью 7'=0(log2 jV), который отличается инвариантностью относительно количества отсчетов N и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в целом В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов заключается в сокращении до o(l) количества последовательных умножений в условиях произвольно заданной границы погрешности вычислений

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

вестных аналогов построением, со!фащением числа последовательных умножений и, в частности, тем, что число процессоров модифицированного БПФ сокращается в log2 N раз при сохранении логарифмической оценки временной сложности вычисления

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

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

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

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

3 Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма. Предложенные схемы ускоряют известные методы в O(log2m), где т - степень аппроксимирующего функцию полинома, и позволяют достигать времени O(l) параллельного выполнения комплекса данных вычислительных схем для априори заданных функций

4 Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью 7"=0(log2jV), инвариантный относительно количества отсчетов N, который сохраняет порядок данной оценки при параллельном выполнении ДПФ и О ДПФ в целом При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до O(l) в условиях произвольно заданной границы погрешности вычислений

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 наименований

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы, формулируется цель исследования, основные положения, выносимые на защиту, ставятся основные задачи исследования

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

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

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

Рассматривается функция одной действительной переменной вида

y = f(x), х4а,b), (1)

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

M]=0WO. x,tl-x,=(b-a)/P, / = 0,1, ,Р-1 (2)

г /»о

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

зуется по дистрибутивности с приведением подобных так, что в результате преобразования на / - м подынтервале принимает канонический вид полинома от одной переменной

Р.(*)=<*„„ +аигх+<ьих1 + +ая1/зГ, хе[х„хм),п = сао!А, 1 = 0,1,. ,Р-1 (3) В (3) индекс коэффициента / совпадает с номером подынтервала, индекс / соответствует аппроксимируемой функции Построение (3) выполняется для всех Р подынтервалов, чтобы на каждом из них не превышалась заданная граница погрешности

|/(*)-/>„(*)' = 0Л ,Р-1 (4)

В (3), (4) значение п выбирается минимальным при условии, что оно одинаково для всех подынтервалов Если такое п найдено, то для функции (1) и для каждого подынтервала из (2) набор коэффициентов в (3) можно записать в память машины и сделать хранимым В дальнейшем, когда потребуется вычислить функцию данного вида, вначале дешифруется значение номера / подынтервала, которое служит математическим адресом выборки коэффициентов (3), взаимно однозначно соответствующим данному номеру подынтервала. Если х е[лг,, то

/ = где ш[ - целая часть числа, а - из (1), Н = х11гХ-х1 Порядок времени этой де-

шифрации оценивается как единичный г = 0(1) Если для рассматриваемой функции вычислить и хранить коэффициенты для всех подынтервалов, то в дальнейшем время вычисления функции зависит только от степени полинома (3) По схеме Горнера значение этого полинома вычисляется с временной сложностью /(1)=п(/^,+/е), где /с, / - время бинарного сложения и умножения соответственно За счет уменьшения длины подынтервала степень п в (3) можно сделать «сколь угодно» малой (но целой) при соответственном возрастании Р в (2) После выборки /-го набора коэффициентов, время вычисления функции оказывается минимальным С целью осуществления описываемого построения вычисление коэффициентов начинается для значения п=1 при минимальном значении Р В случае невозможности достижения заданной точности (4) значение Р удваивается, это продолжается до нарушения допустимых границ значений Р, при их нарушении снова делается переход к минимальному значению Р, но уже при п=2, итд

В рамках интерполяции по Ньютону схема минимизации степени полинома детализируется следующим образом. Если границы /-го подынтервала из (2) обозначить как а,0, ¿>,0, шаг ин-

Ь,о - аю

терполяции - и>, =—-, то равностоящие узлы интерполяции на текущем шаге можно запи-

п

сать в виде хи = а,0 +у и>, , } = 0,1, , п-1 Полином Ньютона степени п на 1-м подынтервале для функции (1) и данных узлов интерполяции записывается в виде

У»,(*)=/(х,о)+Ё А"И'» ("К*-*, Л . где Д'ую - конечная разность ] -го порядка в точке х,0, или,

у-1 к,о

в обозначении / = ,

(5)

у.1 у *-о

Процесс приведения (5) к виду, аналогичному (3), влечет значения коэффициентов

" ^ У о

Цц/=/(*>о)' аи/ = £ ^ч^ч' где Ьц =——, с1и - коэффициенты полиномов вида

н ^

+ + /" с натуральными корнями, входящими в состав полинома Ньютона. Эти коэффициенты не зависят от вида аппроксимируемой функции, после вычисления их можно сделать хранимыми для всех использований интерполяции

Процесс построения полинома на каждом подынтервале из (2) начинается с п = 1, Р = 1 Проверка на заданную соотношением (4) точность аппроксимации (где Р„,(х) = ¥,,,(*)) выпол-

няется на каждом подынтервале в проверочных точках, взятых для независимой переменной / Если во всех проверочных точках каждого из подынтервалов соотношение (4) не нарушено, то аппроксимация на всех подынтервалах при данном значении Р осуществима полиномом Р„,(х) = ¥„,(<) при выбранном п Нарушение (4) в какой-либо точке при сохранении того же значения Р требует увеличить степень полинома на 1, после чего весь процесс построения Ч*. и проверки его на точность аппроксимации заново повторяется на всех подынтервалах В проверочных точках преобразованный полином Ньютона вычисляется по схеме Горнера

Ч'Л'М +а(„-211/)'+ +о01/ (6)

Значение (6) сравнивается непосредственно со значением исходно заданной функции /(*) Результатом работы алгоритма окажется минимальное п для каждого Р-1,2,4,

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

Таблица 1

Степени интерполяционного полинома Ньютона, аппроксимирующего функцию у = 1 / х, л;е[1/2,1] по таблично-алгоритмической схеме

Е \к 0 1 2 3 4 5 6 7 К 9 10 11 12 13 14 15 16 17

10м 7 3 4 2 2 2 1 1 1 1 1 1 1 1 1 1 1

10" я 6 4 4 3 2 2 Ч 1 1 1 1 1 1 1 1 1 1

10 7 Ь 4 3 3 г г 1 2 1 1 1 1 1 1 1 1

10т 12 « 6 5 4 3 3 2 2 2 2 2 1 1 1 1 1 1

104 10 7 6 4 4 3 3 3 2 2 2 2 2 1 1 1 1

10" И 6 4 4 4 i 3 2 2 2 2 2 2 1 1 1

10"° 12 У 7 6 4 4 3 3 2 2 2 2 2 2 2 1

10" К 6 5 4 4 4 3 3 3 2 2 2 2 2 2

10 ' 11 а 7 6 5 4 4 4 3 3 3 2 2 2 2 2

10"» 12 9 7 ь 6 4 4 3 3 3 3 2 2 2 2

12 10 И 7 6 Ь 4 4 4 3 3 3 3 2 2 2

у 10 У 7 6 6 5 4 4 4 3 3 3 3 2 2

к 12 10 7 ь 5 4 4 3 3 3 3 3 2

10" 12 10 й 7 ь $ 5 4 4 4 4 3 3 3 3 1

Ю'" 12 У К 6 5 5 4 4 4 4 3 3 3

В частности, для границы погрешности 10"" достигается третья степень интерполяционного полинома функцию у = Мх можно вычислить с точностью до 10"18 за время трех операций сложения и умножения Помимо точности аппроксимации, при сохранении минимизированной временной сложности таблично-алгоритмической схемы, достигается общность условий аппроксимации функций, отличающая методы интерполяции

Формула (5) для каждого ] - 1,2, , п включает разложение полинома по целым корням

КОР™ и> соответственно, коэффициенты которого не зависят от вида интерпо-

*-0

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

¿¿yt,=ytl-jy,0 „ + -- ^y,u n - ——^p—~y,t, и + + У»' ПРИ этом все биномиальные коэффициенты С/ имеют априори известные значения Достаточно параллельно умножить эти значения на узловые значения функции у, (/_0, затем выполнить алгебраическое сложение по схеме сдваивания Временная сложность этой операции составит /(г) = ty + |log2 j \ t,, где ty, tc - время, соответственно, одного бинарного умножения и сложения, а количество процессоров г - j Факториалы в знаменателях слагаемых выражения полинома fri(t) можно считать априори присоединенными к биномиальным коэффициентам Остается вычисленные значения коэффициентов параллельно умножить на хранимые коэффициенты лолиномов Plt(t) и привести подобные при равных степенях. Временная сложность описанного параллельного алгоритма составит T(R ) = + |log2n |/сна одном подынтервале, R здесь и ниже - количество процессоров, в данном случае R = л(п-1)/2 При параллельном вычислении одновременно по всем Р подынтервалам

т(Рпг 1Т)= ty + |log2 л |/е (7)

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

Таким образом, предложенная схема минимизации временной сложности обладает максимальным параллелизмом, временная сложность которого оценивается на базе (7) с учетом последних замечаний Аналогичная оценка не достигается для полинома Лагранжа, где разложение по корням зависит от выбора узлов интерполяции, при этом на практике не достигается точность аппроксимации полинома Ньютона. Данная оценка не достигается для полинома Тейлора, поскольку его коэффициенты должны быть аналитически определяемыми производными в различных точках, причем на практике при равной точности аппроксимации полином Ньютона обладает преимуществом универсальности (полиномы Лагранжа и Тейлора рассматриваются в контексте использования в (3) взамен полинома Ньютона)

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

При интерполяции по Ньютону /(х)"Ч',10), где Т„,(/) из (б) Отсюда /'(*)«4^,(0, При

t = X Х'° получится /'(*)«(¥„,(/))'/' Очевидно, (У„,(())', = а,,, + 2a2i,г + 3<,/г + +„а,,/""», w,

где /' = — Значение Ч" . (/) вычисляется по схеме Горнера, на основании которой w,

/'(*)«(( ^а„(/< +(л-1)а <„_,,,,)/ + +2а(„„2),,)/ + £>,,,)■!.

wi

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

Погрешность вычисления производной функции f (х) = sin(x),

Таблица 2

[а. Ь}-

1.1 2

на основе полинома Ньютона степени п

п к 11огрешностъ вычисления Функции Погрешность вычисления производной

11 0 5.421*10 9.048» 10"'

4 и 5,421*10'м -2,92740"

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

Вычисление интеграла от функции (1) на промежутке [а,Ь] по аддитивности влечет

ь ?-1 «II

J/(■*)*/•* = Х ¡f(x)dx, где [л,,*,.,,) из (2) Для »-го подынтервала справедливо f(x)**P„,(x),

где Р„,(х) из (4) Отсюда \f{x)dx « [pM(x)dx В свою очередь, [/ (j: « £ \Pm(x)dx Для

<-i

интерполяции по Ньютону используется замена переменной = ——— При ее выполнении

п

значениям х=х, и х = хм соответствуют / = 0 и 1 = п С учетом Р„,(х) = Ч,„,(')> Ч'.ЛО из

+ 1 я

(6), получится Рп1{х)еЫ = щШп1(()Л. В результате /Рп1(х)с1х = у^Ч'^О) <й. Интеграл в правой

щ О

я

части вычисляется непосредственно = где

о

¥<„,,,(0 = с+^-1 +—+ +—Для минимальной степени п интерполирующего функцию полинома и соответствующего числа подынтервалов строится приближение определенного интеграла функции После элементарных преобразований

= и*, Ч*^ ((/т) Значения Ч^^Дл) вычисляются по схеме Горнера

"oif

° р-1

В результате Jf (x)dx*> Х^/^сшоД")- Даннос соотношение строится для минимизи-

О ¡-I

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

Пусть 8 -\Ь\Ъ)~ F(a) - £ и>/?(л+|),(и)|, где F(x) - первообразная функции f(x) Результаты

М)

сравнения с известными методами типичны для представленных в табл 3

Погрешности интегрирования для функции /(х) = 51п(лг), [а, 6 ] =

1,2 2

Таблица 3 : = Ю-10

п к 5 Формула трапеций Метод Симпсона

7 й 7,24» 10"' «ШМО" 1,03'Ю-1

4 2,2640" 3.82*10" 1.55*10'"

2 14 6,51*10'" 3.64*10"" 6,23« Ю-"

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

г е'

приближенного вычисления специальных функций, включая Е1(х)= \—с1х, (х < 0),

X

-СО

/((*)= [-"""> (* > 0)! С(х) = (соб—х^Лх При помощи таблично-алгоритмической схемы можно ¿1шс >0 2

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

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

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

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

Временная сложность максимально параллельного вычисления конечного множества функций по схеме с динамическим распараллеливанием сохраняет оценку Т(К) = 0(1), где Я зависит от максимального количества одновременно готовых аргументов По величине порядка оценка не изменится, если в схему максимально параллельного вычисления функций дополнительно включить ярус аналогичного вычисления производных и определенных интегралов

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

В третьей главе рассматриваются алгоритмические схемы цифровой обработки сигналов, применяемые для распознавания образов и идентификации объектов В частности, рассматриваются схемы, основанные на ортогональных разложениях сигналов Исследуется возможность построения схем максимально параллельной ЦОС для произвольного количества членов ряда в ортогональном базисе Целью построения схем является максимальное быстродействие (минимальная временная сложность) параллельных алгоритмов при условии произвольно заданной границы погрешности цифровой обработки Основные алгоритмы синтезируются для ортого-

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

Х(к) = ^х(пТ)е',1''ш, ¿=0,1,- ,М-\, (8)

N „о

а также О ДПФ

М.яТ) = ^Х{к)е,и"К, и = 0,1, ,N-1. (9)

4-0

Известны рекуррентные зависимости между тригонометрическими функциями (формулы Виета) cos((m + l)j[) = 2cos(;c)cos(OT.r)-cos((m-l).x)> m = 1,2, 1 sin((m + l)x) = 2cos(x)sm(mдг)-sin((m- l)x), m = 1,2, j'

которые в обозначениях Ft(x) = cos(Cx), G,(x)= srn(fjc) можно переписать в виде

^iW-^W^M-'F-iMl Gmtl(x) - 2Gt(x)Gm(x)-Gm_l(x) Fa{x)=h Ft(x) = oos(x) /' G0(x) = 0,G,(x) = sm(x)

Отсюда [FM}-{ , 0JU-,WJ'U.WJ = 1 1 ojU-,Wj'm = 1'2' В силу рекуррентности

r^itoWZcosW -iTf^Wl (G„,(*)W2cos(j0 -l)"(G,{x))

UWA 1 oJUwJ'U-WA 1 oJUwJ

По схеме Стоуна первоначально находятся все степени Аг'=^А2 j ,/=1,2, , flog2m], где

(2cos(x) -Г| Tr „ Г О

А - I Каждому (= ¿j ai 2 > а,=< ,, £ =1,2, ,m, сопоставляется процессор с но-

I. 1 0) ,.о [1

мером I При синхронной работе процессоров С -й из них перемножает те и только те двоичные степени матрицы, перед показателем 2' которой а, = 1. Отсюда временная сложность схемы составит r(m)=0(log2m) Вычисление по ней всех элементов базиса ДПФ (аналогично, ОДПФ), затем параллельное вычисление ДПФ (ОДПФ) с использованием схемы сдваивания (рис 1), с учетом m = N, выполняется с окончательной оценкой r(Ar)=flog2A''](8/(l +5/c)=£?(logJAf) при каждом k = const из (8)

Рис 1 Схема сдваивания N слагаемых

Оценка улучшается путем вычисления ДПФ (ОДПФ) с помощью таблично-алгоритмической аппроксимации элементов базиса на основе полинома Ньютона Для вычисления функций, задающих действительную и мнимую части элемента базиса в (8) или (9), их аппроксимирующие выражения можно представить в виде полинома с заданными коэффициентами eos (л) м a0l+aux+allx2+ +a„xr, sin(x) и b0l+bilx+bllx1+ +brlxr, где х-^ЕЬ.^ , - номер

N

подынтервала Для всех таких х, при всех Р для произвольного N и одновременно для всех

номеров подынтервала i - параллельно и синхронно - вычисляются сразу все элементы базиса ДПФ Для заданной точности аппроксимации степень г каждого интерполирующего полинома может быть априори выбрана «сколь угодно малым» натуральным числом Поэтому временная сложность такого параллельного вычисления всего множества элементов базиса оценивается из соотношения T(R) = r{ty + t(}= 0(1), где число процессоров R совпадает с количеством одновременно вычисляемых элементов ty, tc - время бинарного умножения и сложения Далее элементы базиса на тех же N процессорах одновременно умножаются на соответствующие коэффициенты х(пТ) ДПФ, после чего ДПФ принимает вид суммы N слагаемых Полученную сумму можно определить параллельно по схеме сдваивания

Имеет место

Теорема 1. ДПФ (8) с переменным числом членов N при каждом к = const можно вычислить параллельно на N процессорах с помощью таблично-алгоритмической схемы на основе кусочно-полиномиальной интерполяции и схемы сдваивания с временной сложностью Г(2^) = г(/ +/,) + flogjA']íe = 0(IogjjV), где логарифмическое число шагов алгоритма состоит только из операций сложения, а количество умножений произвольно мало и фиксировано г = 0(1)

Аналогично реализуется ОДПФ (9) при той оговорке, что коэффициенты ОДПФ предварительно найдены

Пусть функция одной действительной переменной представлена рядом Фурье

_ ав 00 J

/(í)=^ + £(a,c»s(6:) + 6,sm(&0) 3 Ic,e"\ где а0, a,, b¡, ct=~(a,-ib,), (¿ = 1,2, )-априори

2 í-i (=-«, 2

известные числовые коэффициенты Функция в левой части ряда Фурье приближается частичной суммой /(*)» — + (a, cos(íjc) + b, sin(£*)) По схеме Стоуна могут быть параллельно вы-2 (.i

числены значения одновременно m элементов базиса sin(¿x) и cos(£x), I=1,2, ,m Найденные значения sin(£x) и cos ((х) параллельно умножаются на соответствующие а, и bt В результате частичная сумма ряда Фурье принимает вид суммы парных произведений Для вычисления частичной суммы остается воспользоваться схемой сдваивания В результате функция может быть вычислена с точностью до е на m процессорах с временной сложностью Г (и ) =("logjm"l(8^ + 5/J= О (log, т)

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

В главе формулируется следующая теорема

Теорема 2. Суммарный набор алгоритмов ЦОС, включающий алгоритмы ДПФ (8), ОДПФ (9), круговой свертки, линейной свертки, корреляции с использованием схемы Стоуна реализуется параллельно с оценкой временной сложности T(r)=o(log2 N) Тот же набор алгоритмов с использованием таблично-алгоритмической схемы реализуется параллельно с временной сложностью T(R) s с |~Iog2 //"J lc , где с = const, tc - время бинарного сложения В этих оценках Д = Л'5 с учетом одновременно требуемых значений (8) и (9) для каждого £=0,1, ,N-\ и каждого п = 0,1, ,N-1

Исследуется применимость данного подхода для параллельного вычисления БПФ В случае вычисления всех элементов базиса по схеме Стоуна имеет место следующее утверждение

Предложение 1. В предположении, что коэффициенты при элементах базиса БПФ

--i

+ К £*(2' + lKl2 априори заданы и что эти коэффициенты являются

г'о г* О

комплексными, N -точечное БПФ с прореживанием по времени можно выполнить параллельно на n процессорах с временной сложностью t(n) = 0(log2 n) при произвольном динамическом изменении количества отсчетов N для каждого к = const из (8)

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

Предложение 2. В условиях предложения 1 N -точечное БПФ с прореживанием по времени можно выполнить параллельно на N процессорах с временной сложностью

I N

•ogiy

tc+ 4 (2ly + lc) slogj^-/,. =0(k>g2iV) при произвольном динамическом

изменении количества отсчетов N для каждого к = const из (8)

Предложенная модификация параллельного выполнения БПФ не только сокращает число процессоров пропорционально log 2 N, но и улучшает известные оценки времени за счет кусочно-полиномиального вычисления базиса. Утверждения теорем 1, 2 и предложений 1, 2 инвариантны относительно динамически меняющегося количества точек отсчета Данное качество, равно как и рассматриваемые оценки распространяются на совокупность алгоритмов ЦОС в целом, где подразумеваются алгоритмы, относительно которых сформулирована теорема 2

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

Предложение 3. В условиях предложения 1 N -точечное БПФ с прореживанием по време-

bi

ни ХК(к)= 2^л(2г+ + l)W*/2 можно выполнить параллельно на — процессорах с

ГШ о г-0 2

временной сложностью уj = log 2 N х ((г+8)ty + (г+4)tc) или 7^-yj=o(logj N) для каждого

к = const из (8) При этом выполнение операций БПФ совмещается во времени с вычислением элементов тригонометрического базиса в условиях произвольного динамического изменения количества отсчетов N

Предложение 3 инвариантно относительно динамически меняющегося количества отсчетов и показывает целесообразность перехода от ДПФ к БПФ в рамках предложенного метода с целью сокращения числа процессоров

Представленные выше оценки временной сложности объединены в таблицу (табл 4) для сравнения с оценками известных методов параллельных и последовательных вычислений ортогональных преобразований В табл 4 IIM - обозначение предложенных методов, ИМ - обозначение известных методов

Таблица 4

Сравнение временной сложности параллельных схем выполнения ДПФ и БПФ

ПМ ИМ

Временная сложность Число процессоров, к - const Число тригонометрических полиномов (элементов базиса) Временная сложность Число процессоров Число тригонометрических полиномов (этементов базиса)

Отрезок ряда Фурье (коэффициенты ткет ни) O(log2/j) п = const 0(п) И» const ТУ 0(log2,V) оИ N

ДПФ Ts}°hN{c = ф gjtf) 0(N) N при совмещении с вычислением базиса O(log2 ЛГ) ф2) N без совмещения с вычислением базиса

БПФ 0(logjAO 0(N) N при совмещении с вычислением базиса O(\0SlN) Ф) N без совмещения с вычислением базиса

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

At,i1("i."2)=sm—r^-sm—-г-S ^(«,,«2)=cos—rf-^cos—-t-i, где NtxN2 - размер исходам "j i ного сигнала, размер спектра, к{= 0, ,Nx-l и к2= О, ,N2-1 - номера базисных функций (номера коэффициентов двумерного ДПФ, при которых эти функции находятся), и,= О, ,N¡-1 и п2= О, ,N2-1 - переменные-аргументы базисных функций Двумерное ДПФ определяется следующими соотношениями

■4MJ-1? *£x[nl,n2]e4"'t'il"/x^'">k>(2"'N>\ (10)

П[сО /»2-0

Предложение 4. В предположении, что коэффициенты в (10) априори известны, двумерное ДПФ (10) можно выполнить параллельно с использованием схемы Стоуна для вычисления элементов базиса с временной сложностью Г = O(log2 max(;V,, N2)) При этом требуемое количество процессоров R = N, xN2 для каждого к, = const и каждого к2 = const В том же предположении относительно коэффициентов (11) данное утверждение и оценки распространяются на двумерное ОДПФ (11)

Если поиск элементов базиса выполнять не по схеме Стоуна, а по таблично-алгоритмической схеме на основе кусочно-полиномиальной интерполяции по Ньютону, то при том же количестве процессоров, что и в случае схемы Стоуна, достигается временная сложность параллельного вычисления всех элементов базиса, равная T(N, +N2 )= O(l)

Предложение 5 В условиях предыдущего предложения двумерное преобразование Фурье (10) можно выполнить параллельно с использованием таблично-алгоритмической схемы на основе кусочно-полиномиальной интерполяции по Ньютону для вычисления элементов базиса. Без изменения остальной части схемы, описанной для предложения 3, полное вычисление ДПФ (10) будет выполнено с временной сложностью T(R) = r(iy + tc) + c0(log2 maxiA', , N2))tc, где c0 = const При этом требуемое количество процессоров R- Nx *N2 для к, = const, к2 = const, а логарифмическое число шагов алгоритма состоит только из операций сложения, количество ум-

ножений постоянно, - г = O(l). В тех же предположениях относительно коэффициентов (11) данное утверждение и оценки распространяются на двумерное ОДПФ (11)

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

Максимально параллельная схема минимизации временной сложности таблично-алгоритмического вычисления функций позволяет с оценкой т(Рп2/2)=ty + [log 2n\tc выполнить настройку параллельного вычисления всех элементов тригонометрического базиса ДПФ и БПФ для произвольно заданной границы погрешности е Если условия задачи ЦОС допускают такую настройку на этапе компиляции, то настройка на этом этапе может выполняться максимально параллельно с использованием ярусно-параллельной формы Если условия задачи цифровой обработки требуют динамической адаптации алгоритма минимизации временной сложности вычисления базиса, то параллелизм алгоритма с временной оценкой Т {Рп1 / 2) = ty +1 log j п | tc, где n - степень аппроксимирующего полинома, позволяет (при наличии соответственной архитектуры параллельной вычислительной системы) организовать настройку схемы минимизации для данной границы погрешности в режиме реального времени

В случае выбора такого режима теоремы 1 - 3, а также предложения 1-5 корректируются с добавлением времени из правой части данной оценки в виде tf -+- [ log 2 п0 где п„ - допустимая степень кусочно-полиномиальной аппроксимации при заданной границе погрешности аппроксимации 6 При этом существенно возрастает количество процессоров, требуемое данным режимом реального времени, - это количество, согласно т[Рпг 12)- ty +[log2n]ic в используемых обозначениях, возрастет на величину R„ = Рп\! 2, где Р-количество подынтервалов оптимизированной кусочно-полиномиальной схемы

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

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

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

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

Работа включает следующие научные результаты.

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

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

3 Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма. Предложенные схемы ускоряют известные методы в O(log2m), где т - степень аппроксимирующего функцию полинома, и позволяют достигать времени 0( l) параллельного выполнения комплекса данных вычислительных схем для априори заданных функций

4 Разработана динамически распараллеливаемая схема вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью T=0(\og2N), инвариантная относительно количества отсчетов N, которая сохраняет порядок данной оценки при параллельном выполнении ДПФ и ОДПФ в целом При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до O(l) в условиях произвольно заданной границы погрешности вычислений

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

1. Ромм Я.Е, Аксайская Л Н Программный метод приближенного вычисления определенных интегралов на основе интерполяционного полинома Лагранжа произвольной степени / ТГПИ - Таганрог, 2006 - 16 с Деп в ВИНИТИ от 17 02 2006, № 170 - В2006 (лично автора -0,4 п.л ) v

2 Ромм Я Е, Аксайская Л Н Программный метод временной оптимизации приближенного вычисления производных на основе интерполяционного полинома Лагранжа - В кн Материалы Международной научно-технической конференции «ММА-2006» - «Математические модели и алгоритмы для имитации физических процессов» Т 1 Физико-математические и физико-технические модели и алгоритмы для имитации физических процессов - Таганрог - 2006

С 313 - 356 (лично автора - 0,2 п л )

3 Ромм Я Е, Аксайская Л Н Временная оптимизация вычисления производных и опре-еленных интегралов на основе интерполяции по Лагранжу / ТГПИ - Таганрог, 2006 - 44 с еп в ВИНИТИ от 30 10 2006, № 1281 - В2006 (лично автора -1 п л)

4 Ромм Я Е , Аксайская Л Н Схема кусочно-полиномиальной аппроксимации с мини-альной временной сложностью на основе интерполяционного полинома Ньютона / ТГПИ - Та-анрог, 2007 - 17 с Деп в ВИНИТИ от 12 02 2007, № 121 - В2007 (лично автора - 0,5 пл)

5 Ромм Я Е, Аксайская Л Н Кусочно-полиномиальное вычислении функций, производ-ых и определенных интегралов на основе интерполяции по Ньютону / ТГПИ - Таганрог, 2007 36 с Деп в ВИНИТИ от 02 05 2007, № 487 - В2007 (лично автора - 0,75 п л )

6 Ромм Я Е, Аксайская Л Н Кусочно-починомиальная аппроксимация функций на ос-ове интерполяции по Ньютону в приложении к рядам и преобразованиям Фурье - В кн The ourth International Conference Theoretical and Applied Aspects of Program Systems Development TAAPSD'2007) «ABSTRACTS» - Ukraine, Berdyansk - 2007 - P 93 - 98 (лично автора -,2пл)

7 Ромм Я Е, Аксайская Л Н Кусочно-полиномиальная аппроксимация функций на ос-ове интерполяции по Ньютону в приложении к цифровой обработке сигналов / ТГПИ - Таган-ог, 2007 - 47 с Деп в ВИНИТИ от 02 11 2007, № 1021 - В2007 (лично автора - 1 п л )

8 Ромм Я Е, Аксайская Л Н Кусочно-полиномиальная аппроксимация функций в приложении к дискретному преобразованию Фурье - В кн «Математические модели физических процессов» Т 1 Физико-математические и физико-технические модели, проблемы технологии - Таганрог - 2007. - С 158-161 (лично автора - 0,2 п л).

9 Ромм Я Е, Аксайская Л Н Кусочно-полиномиальная аппроксимация функций на основе интерполяции по Ньютону в приложении к параллельному вычислению ДПФ и ОДПФ - В кн Математическое моделирование, обратные задачи, информационно-вычислительные технологии Сб статей VII Международной научно-технической конференции - Пенза - 2007 -С 81-84 (лично автора - 0,2 п л)

10 Ромм Я Е, Аксайская Л Н Кусочно-полиномиальная аппроксимация функций на основе интерполяции по Ньютону в приложении к параллельной цифровой обработке сигналов // Вопросы современной науки и практики Университет им В И Вернадского Т 2 Серия «Технические науки», 2007 - С 107 - 118 (лично автора - 0,4 пл)

11 Ромм Я Е, Аксайская Л Н Кусочно-полиномиальная аппроксимация функций, производных и определенных интегралов на основе интерполяции по Ньютону // Известия ЮФУ Технические науки - 2008 -№ 2 -С. 14-21 (лично автора - 0,3 п л)

Соискатель

Аксайская Л Н

Тип ТТИ ЮФУ

Подписано к печати Объем 1,1 У4 -изд л

Заказ л № Тираж 100 экз

ВВЕДЕНИЕ.

ГЛАВА 1. СИНТЕЗ КОМПЬЮТЕРНЫХ СХЕМ МИНИМИЗАЦИИ ВРЕМЕННОЙ СЛОЖНОСТИ ТАБЛИЧНО-АЛГОРИТМИЧЕСКОГО ВЫЧИСЛЕНИЯ ФУНКЦИЙ НА ОСНОВЕ ИНТЕРПОЛЯЦИОННОГО ПОЛИНОМА НЬЮТОНА.

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

1.2. Сравнение погрешности таблично-алгоритмического вычисления функций на основе интерполяционных полиномов Ньютона и Лагранжа

1.3. Сравнение погрешности таблично-алгоритмической схемы вычисления функции на основе интерполяционного полинома Ньютона и ряда Тейлора

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

1.5. Выводы.

ГЛАВА 2. ОПТИМИЗИРОВАННАЯ СХЕМА ТАБЛИЧНО-АЛГОРИТМИЧЕСКОГО ВЫЧИСЛЕНИЯ ПРОИЗВОДНЫХ И ОПРЕДЕЛЕННЫХ ИНТЕГРАЛОВ НА ОСНОВЕ ИНТЕРПОЛЯЦИИ ПО НЬЮТОНУ.

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

2.2. Метод приближенного вычисления определенных интегралов на основе таблично-алгоритмической схемы с помощью интерполяционного полинома Ньютона.

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

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

2.5. Выводы.

ГЛАВА 3. ПАРАЛЛЕЛЬНАЯ ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ С ПРИМЕНЕНИЕМ ТАБЛИЧНО-АЛГОРИТМИЧЕСКОЙ АППРОКСИМАЦИИ БАЗИСНЫХ ФУНКЦИЙ.

3.1. Параллельное вычисление прямого и обратного ДПФ с использованием схемы Стоуна.

3.2. Параллельная таблично-алгоритмическая аппроксимация базиса ДПФ и

ОДПФ на основе интерполяционного полинома Ньютона.

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

3.4. Параллельные схемы для совокупности алгоритмов ЦОС.

3.5. Применение схем параллельного вычисления тригонометрического базиса для выполнения БПФ.

3.6. Сравнение временной сложности алгоритмов ЦОС.

3.7. Параллельные схемы многомерной ЦОС.

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

3.9. Выводы.

Актуальность проблемы. Решение задач в вычислительных системах с использованием аппроксимации функций требует значительных затрат времени, объема оперативной памяти и вычислительных ресурсов [1, 2]. В практических приложениях часто необходимо вычислять значения t элементарных функций: рациональных, степенных, тригонометрических, обратных тригонометрическим, показательных и логарифмических, гиперболических и обратных гиперболическим. При этом к методам их вычисления предъявляются требования одновременно высокого быстродействия, вычислительной устойчивости, высокой точности аппроксимации и универсальности схем вычислений. К категории задач, требующих большого объема вычислений, относятся задачи гидро- и аэродинамики, задачи по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных т физических и химических процессов. Задачи управления движением летательных аппаратов, включая гидросамолеты, требуют эффективных способов улучшения аэродинамических характеристик, при этом в описании законов векторного управления пространственным движением используются тригонометрические функции для определения углов тангажа, крена, рыскания. Базовая нелинейная математическая модель пространственного движения твердого тела, записанная через углы Эйлера, имеет вид [3]: xi (t)=—хъ х5 + х2 х6 — g sin X|q + (l/m)ux;

X2{t)=—x6 +x3 x4 — gcosxn cosx10 + (l/m)u2; хз (t)=—x2 x4 + x, + g sin xx j eos x,o + (l/m)u2;

X5 (t)=a4x4x6 + a3u5;

4 л4 ти3 и5 ,

Xl (t)= x¡ cosx12 cosx10 +x2 (sinxn sinx12 -cosxn cosx12 sinx10)+ +x3 (cosxn sinx]2 +sinxu cosx12 sinx10) ;

X8(t)= X¡ sinx10 +x2 COSXjj COSX]0 -x3 sinxncosx10;

X9 (t)= - Xj sinX12 COSXl0 + x2 ( sinXj t COS X12 + COS xn sin Xj2 sin X,Q)+ +x3 (cosxncosx12-sinxnsinx12sinx]0) ; x\o(t)= x5sinxH +x6cosxH ; xn(/)= x4-tgx10 (x5cosxn -x6sinxn );

• / \ cosxn sinx,,

X\2\t J= Xj-— ~X6- ? cosx10 cosx10 где xx - Vx, x2=Vy, x3=V, - проекции вектора линейной скорости на оси связанной системы координат; х4=сох, х5=соу, х6=со:. - проекции вектора угловой скорости на оси той же системы; х7-Х, х8=7, x9=Z - координаты центра масс летательного аппарата в земной системе координат; х|0=&, хи=у, х12=х ~ углы тангажа, крена и рыскания, соответственно; u{=Fx, u2=Fy, u3=F, - результирующие силы по осям координат; иА=Мх, и5 = Му, и6 -Mz - суммарные моменты сил; g - ускорение свободного падения; т -масса аппарата; ax-\jlx, a2={ly-Iz)/Ix, a3=l/Iy, a4=(l:~Ix)/Iy, a5=l/L, ae={lx-Iy)jI,; Ix, Iy, I: - моменты инерции самолета.

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

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

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

Г(г)= интеграл вероятностей е^(г)=~1=§ехр\^-Г)с11; у

I' о

71 0 интеграл Досона F(y)=exp(—y2'j |ехр(^2) Ж; интегралы Френеля

С(г)= $соб^^2 ск, 5^)= интегральная показательная функция

Ех[—Ж; интегральный логарифм Ы{х)- Г—, х>0, хФ\\ х * о интегральный синус и косинус С1(х)=- дилогарифм о

00 х" ; функция распределения Пирсона %2 (хи-квадрат) я=1« распределение случайной величины Х=Х2+Х% +.+ Хгп, случайные величины Хх, Х2, .,Хп независимы и имеют одно и тоже распределение ч щ 2 2

N(0,1); распределение Фишера ^ где %п, хт - независимые 1т П случайные величины, подчиненные распределению хи-квадрат с п, т степенями свободы, £ -распределение Стьюдента , и,Х независимые случайные величины).

Приближенные методы вычисления функции /(х) на интервале (а, Ь) сводятся к вычислению аппроксимирующей функции ф(х). Для оценки ошибки г(х)=/(х)-ф(х) вводятся некоторые числовые характеристики, называемые «нормами» функции. Наибольшее значение имеют [1]:

1) «равномерная норма» ошибки:

II г 1с= т,ахЛИ*)| = тах1/(*)- ф(*)| ; ха{а,Ь) 1С (а,Ь)

2) «квадратическая норма» ошибки:

1 г ||2 = рг(х)]2Лх = , или более общая квадратическая норма с весом р(х)>0 :

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

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

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

00 источников является разложение функции в степенной ряд (х-х0)к , где к=О х 0 - фиксированное число, центр сходимости ряда. Если функция п +1 раз дифференцируема при хе(л:0-г,х0+г), г>0, то для всех хе(х0-г,х0+г) имеет место формула Тейлора

С1) с остаточным членом П

XQ

Необходимым и достаточным условием сходимости правой части (1) к функции /(х), xe(x0-r,x0+r) является выполнение равенства lim Rn (х) =0. n—> 00

Если функция /(х) непрерывна на \а, х] и обладает на этом отрезке производными до порядка т+п+1 включительно, то справедлива обобщенная формула Тейлора [4, 5] к=1 [т + п)\ где я = (-1)п т-п^х а>--/("+и+1)(0); а<е<х; рСк- биномиальный т + п)! (т + п +1)! коэффициент, причем рСк=0 при к> р.

Элементарные и аналитические функции принадлежат к числу представимых степенными рядами. Если функция /(х) представима п АкЦ0\ формулой /(х)= ——хк + Яп (х), то, обрывая ее на п -ом члене, получим о к! многочлен Рп(х) п-ой степени, который обладает следующим свойством: на интервале (0, К) система многочленов степени п наилучшего приближения при к—>0 стремится к многочлену Рп(х). Поэтому многочлен Рп{х) дает наилучшее приближение к функции /(х) вблизи нуля.

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

Для вычисления многочленов наиболее часто используется схема Горнера, но для ускорения процесса применяются схемы Винограда, Мотцкина - Белаги - Пана [1,5-11].

Схема Горнера может быть записана в виде: р„{х)={(Лапх+ап-\)х+ .-)х+ах)х+а0 .

Ее вычисление сводится к рекуррентному алгоритму

К=ап'> Ук=ак+хУк+Х9 к = п-1,0; Ра(х)=Г0.

Схема Горнера требует п операций алгебраического сложения и п операций умножения. В случае, когда требуется вычислять один и тот же полином многократно и время выполнения операции умножения значительно больше времени выполнения операции сложения, более экономно применять методы Мотцкина - Белаги - Пана. Например, многочлен четвертой степени 4

РА (х)= ак хк, О представляется по схеме Мотцкина [12] в виде к-0 х)=((м+д:+а2)м+аз )а4, где и=(л;+а0 )л:+а1, ак — соответственно-подобранные коэффициенты. Эта схема содержит три умножения, пять сложений, т.е. меньше операций умножения, чем схема Горнера. Минимальное количество операций1 умножения (деления) и сложения при построении схем, подобных схеме Мотцкина, определяется теоремой Белаги [7], утверждающей, что для любого п всякая схема вычисления многочлена Рп{х) содержит не менее [(и+1)/2] операций умножения (деления) и не менее п операций сложения (вычитания).

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

Ускорение в этом случае достигается не за счет сокращения общего количества операций, а за счет параллельного выполнения взаимно независимых частей аппроксимирующего функцию алгоритма при условии готовности значений данных. Многочисленные примеры параллельных алгоритмов вычисления полиномов представлены в [10, 11, 13 — 16].

Все параллельные алгоритмы здесь и в дальнейшем описываются на модели неветвящейся параллельной программы. Понятие неветвящейся параллельной программы как последовательности параллельных арифметических команд заимствуется из [17]. При этом арифметические команды отождествляются с конкретными арифметическими операциями. Временная сложность алгоритма понимается как длительность выполнения представляющей его неветвящейся параллельной программы. Ускорение — как отношение временной сложности последовательного алгоритма к временной сложности его параллельного варианта, эффективность — как отношение ускорения к количеству процессоров, требуемому для реализации параллельного варианта алгоритма с максимальным параллелизмом каждого-последовательного шага. Более точно в дальнейшем временная сложность алгоритма измеряется количеством последовательных шагов его выполнения, при этом будет учитываться вид операции на каждом последовательном шаге. Временная сложность будет обозначаться Т(я), где R - количество процессоров. Каждое из данных понятий аналогично интерпретируется в [18-24]. Конкретная программная.реализация неветвящихся параллельных программ в данной модели не учитывается, не учитывается отображение на архитектуру параллельной вычислительной системы. Данная модель абстрагируется от способов обмена: в рамках модели * предполагается [17], что параллельная вычислительная система работает как идеальный параллельный процессор [20].

Пусть до начала вычислений известна вещественно-значная функция f(x), допускающая полиномиальную аппроксимацию f{x)K±aixl. (2)

1=0

Пусть /(х) задана на фиксированном отрезке [а, б], допустимая погрешность аппроксимации (2) s также фиксирована, т.е. а = const, b =const , е = const, х е \а, b\. В этих условиях степень п и коэффициенты at априори могут быть найдены. Поэтому можно считать, что при каждом значении 1=0,1,., п at = const , п = const. (3)

Полином (2) разлагается на квадратичные множители: где а=1 при п нечетном и а=0, если п четно; ап, г, вещественны,

1=1, 2,.,[п/2]. (Разложение (4) получается из известного п разложения Рп{х)=ап\\{^~У,-)> гДе У/ ~~ вещественные или комплексно1 сопряженные корни). В условиях (3) ап, г, р{, д1, /=1, 2,., [и/2] можно также считать вычисленными и априори известными. Поэтому для (3) можно построить неветвящуюся параллельную программу [17—19]: Шаг1: х+г, х+р¡, /=1, 2,., [и/2].

Шаг2: ап(х+г), {х+р)2, 1=1, 2,., [п/2]. (5)

Шаг 3: (х+р{)2+д{, 1=1, 2,., [и/2].

Шаги 4, 5, ., ["к^2([и/2]+1)1 состоят в умножении" по схеме сдваивания [18, 19] [и/2]+1 сомножителей и ап(х+г), вычисленных на шаге 3. Здесь и ниже |~а~| - ближайшее целое, не меньшее самого числа; [а] -целая часть числа (наименьшая часть числа, не превосходящая а). Имеет место

Теорема 1. В рассматриваемых условиях функция /(х) может быть вычислена с точностью до в посредством параллельного алгоритма (5) с временной сложностью Т(я), определяемой равенством

Г([и/2]+1)=(Т1оё2([и/2]+1)1+1) 1у п)гу =0(1о§2 п). (6)

Здесь и ниже, при оценках временной сложности, 1у — длительность одного бинарного арифметического умножения, /с - длительность бинарного алгебраического сложения.

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

В [6, 25] используется схема распараллеливания вида т-1 г=О являющаяся сравнительно универсальной и имеющая временную сложность рп(х)= 11хг{.(апгхт +аптг) хт+ап2тг)хт+. + а,г, п — г т.

Т(т) = — О(и) + 0( 1оё2т) > 0(^2 п)\ 1г=п-гт [ т

Известна следующая неветвящаяся параллельная программа вычисления значения полинома [26, 27]: Шаг 1: х • х.

Шаг 2: х2 -х; х2 -х2. ттт 4 • 4 2.4 3.4 4

1-1.1. цГ ^ • X * X 2 X * X ^ X ' X у X * X ■ ттт 29"1 29-1 2 2<?1 29-1 ^ П 1

Шаг д: х -х; х -х ; .; х -х ; д <| (7)

Шаг [~1оё2 п |+1: щ х1, / = 1, 2,., п.

Шаги [~1о§2и]+2, 2(~1о§2и~]+1 состоят в сложении по схеме сдваивания. Очевидно, временная сложность алгоритма (7) есть

Т(п)=(Г1оё2 п\ +1)^ + Г1оё2 п\ Гс ~ 2 \о%2 п та , /с) = 0(1о§2 и)

Данная неветвящаяся параллельная программа применима для параллельной полиномиальной аппроксимации функций в условиях сходимости. Схему Горнера [28] параллельный алгоритм (5) ускоряет в ~ п [{ + ¿с): n)ty) ~ 2 л 1п2 раз при ? « ценой затраты п/2 процессоров. Отсюда ее эффективность ~41п2 Неветвящаяся параллельная программа (7) универсальна, но обладает вдвое меньшим ускорением и вчетверо меньшей эффективностью.

Для деления применяется следующая неветвящаяся параллельная программа [29]. Пусть в результате редукции вещественного аргумента функции х 1 выполнено соотношение хе к Пусть выбрана двоичная система счисления. Тогда для редукции достаточно выделить порядок и мантиссу: х 1 =2 р-т\ \^<т< 1 [29] Пусть аппроксимация т 1 выполняется по методу Эмбла [30] у0=2-т. (8) т 1 ~

Стандартным приемом [30 - 32] (8) разворачивается в полином

1=0 1=0 1=0 2=1 -т. Аналогично разложению для треугольных матриц, использованному в [33 -35], получается

9)

1 + 2 ъ

1=0 1 где г требуется выбрать так, чтобы 2 -1=/+2, что всегда можно сделать, не увеличив погрешности метода. Тогда к=log2 (z+З) - 1.

Неветвящаяся параллельная программа для (9) примет вид: Шаг 1: z2.

Шаг 2: (z2f.

Шаг к: (z2*-' J. (10)

Шаг k+1: 1+z2', / = 0,1, .Д.

Шаги к+2, к+3, ., &+[~log2(A;+l)~|+l состоят в умножении по схеме сдваивания сомножителей (10), вычисленных на шаге к+1. В описанных условиях имеет место

Теорема 2. Функция х~1 может быть вычислена посредством неветвящейся параллельной программы (10) со сложностью

Г(1оё2 (i+3))=(log2 (i'+3)+j"log2 log2 (/+3)] + 1)^+3^, (11) где i+3 - наименьшая целая степень двойки, такая, что число итераций i+\ в (8) достаточно для достижения требуемой точности вычисления.

Сложность ' неветвящейся параллельной программы (10) ~ (1о§2 = 0(\о^2 /); ускорение метода Эмбла ~2/1п2; эффективность 2/1п2/к^2/ ~ 2/1п22. Вычисление (9) на одном процессоре возможно со сложностью ~ / ({у +tc) = /). Данные оценки можно считать оценками сложности деления, ввиду того, что у/х=у-х~х.

Схемы кусочно-полиномиальных аппроксимаций. Схемы кусочно-полиномиальной аппроксимации часто рассматривали в качестве V оптимальных машинных алгоритмов вычисления функций [36,37]. Такое представление об .оптимальности обусловлено следующими качествами данных схем. Аппроксимирующий полином строится на каждом подынтервале, объединение подынтервалов покрывает основной интервал. Длину подынтервала можно выбрать такой малой, чтобы приближение на нем достигало априори* заданной границы погрешности. На этой основе возможно достигать высокой точности приближения полиномом малой степени. Именно это качество определяет преимущество таких схем и .сравнительную оптимальность их временной сложности.

При построении таких схем, однако, в окончательной форме нет общего подхода: в зависимости от разновидности приближения на подынтервале, схемы отличаются количеством операции, временем и точностью вычисления. Например, для аппроксимации на подынтервале в [38] предлагается1 использовать интерполяционный полином Ньютона, в котором не приводятся подобные, вследствие чего аппроксимация обладает существенно избыточным числом операций. В [39] ту же аппроксимацию предлагается выполнять с помощью интерполяционного полинома Лагранжа. В общем виде приведение подобных не осуществляется, и эта схема обладает тем же недостатком избыточности. Существуют разновидности [1] аппроксимации на подынтервале с помощью метода «цифра за цифрой», в которых, как и в отмеченных схемах, не сохраняется инвариантность относительно произвольной точности приближения, не достигается оптимизация временной сложности на подынтервале. Аналогичный недостаток сохраняется при аппроксимации на подынтервалах с помощью ортогональных полиномов Чебышева [36, 37].

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

Некоторые разновидности приближений функций. Разложение функции /(х) по невязкам строится следующим образом. Пусть функция У - /(х) задана уравнением

12) I

Невязка уравнения (12) [2] определяется соотношением получающимся при замене точного значения у на у0, которое является приближением функции у=/(х) на заданном отрезке \а, Ь]. При этом необходимо выполнение условия Нш г0=0. Один из способов получения

У~*Уо разложения функций по невязкам состоит в том, что из уравнения невязки (13) определяется х0=ф(у0,г0), а из этого уравнения находится искомая функция /(х)=/(ф(у0,г0))- Для наиболее часто употребляемых элементарных функций допускается представление суперпозиции функций /{ф(у0,г0)) в явном виде. При соответствующем выборе структуры невязки

13) уравнения (12) для хе[а, Ь\ элементарные функции (1 + х)", ах, 1пх, агсэтл:, агссозх, ак^х, АгбЬл;, АгсЬх, АлЬх удовлетворят функциональному уравнению: /(*) = /(*0)®Ф (*о)> гДе хо=/~1(уо\/~1(у)~ взаимно обратная функция по отношению к у = /(х), у0 - приближенное значение к функции /(х), х&\а,Ь\, ® - знак некоторой операции (для функций (1 + х)", ха, ах знак ® означает операцию умножения, а для остальных функций - операцию сложения (вычитания)). Для рассматриваемых функций ер (г0) определяется на основе тождества ф (г0) = /(г0), а для остальных функций - на основе тождеств

Ф (^оЬДС1*^)*1) Для ха, ф (20)з/(г0/1па) для а\

Лы±11

А ^—I дЛЯ 1пд;

1 1 + гг 1 о.

В зависимости от выбранного вида невязки (знак «+» либо «-» зависит от порядка вычитания членов в невязке).

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

Для приближения табличных и аналитически заданных функций наряду с многочленами широко используются дробно-рациональные приближения вида [2]:

14)

1=0 1=0

Выражения, по которым вычисляются специальные функции- в вычислительных системах, в основном, — рациональные приближения. Это объясняется тем, что общее количество операций для достижения заданной точности при рациональном приближении обычно меньше, чем при многочленном. Однако при использовании дробно-рациональных приближений появляется операция деления, что не для всех вычислительных систем является удобным. Во многих вычислительных системах само деление организуется как приближенное вычисление функции /(х)=х-1, для которой требуется алгоритм, сопоставимый по числу операций с вычислением Як1 (х). В тех случаях, когда скорость деления близка к скорости умножения, эффективность использования рациональной аппроксимации возрастает. Общее количество операций при. вычислении цепной дроби меньше, чем при вычислении рациональной дроби, образуемой по схеме подходящей дроби [40]. Для цепной дроби с единичными частными числителями и положительными частными знаменателями относительная погрешность ее значения асимптотически (с точностью до бесконечно малых первого порядка) не превышает максимальной из относительных погрешностей ее компонентов независимо от числа звеньев дроби [41,42]. Вместе с тем на практике, при вычислении цепных дробей в режиме с плавающей точкой, погрешности округления могут накапливаться быстрее, чем при счете дробно-рациональной функции [9]. Цепную или непрерывную дробь определяют как выражение а.

Ь0 +

7 а ъх+-

Ы-К.,' в* ьк+~ где — — к-е звено цепной дроби; Ь0 - нулевое звено; а 1 - частные делители; К

Ь1 - частные знаменатели (/=1,2,.). Помимо отмеченных, имеется еще одно затруднение: цепная дробь, непосредственно по построению; не допускает эквивалентной записи в параллельной форме. Отсюда вытекает существенное несоответствие тенденции распараллеливания вычислений и несоответствие архитектуре программного обеспечения параллельных вычислительных систем.

Иногда с помощью сжатия цепных дробей удается преобразовать равноценную цепную дробь в соответствующую. Для построения равноценных цепных дробей на практике чаще всего используют тождество« Эйлера [40] к ахх а2х ахаъх яг2 а1 х

2-1акх =ао + —--—---;-------;-

Л=о 1 а1+а2х а2+а3х + а1 х

С целью уменьшения количества операций умножения при вычислении рациональных функций вида (14) для числителя и знаменателя можно использовать схему Горнера либо методы Мотцкина - Белаги - Пана.

Одним из методов получения дробно-рационального приближения является аппроксимация Паде. Под обычной аппроксимацией Паде понимают получение дробно-рационального приближения Як1{х), для которого при х —> 0 точность приближения составляет при условии, что на заданном интервале знаменатель ни в одной точке не обращается в нуль. При таком определении аппроксимации Паде она является естественным обобщением разложения функции в ряд Тейлора. Метод Паде позволяет получить рациональные приближения из степенного ряда.

Примером итеративного процесса является модификация метода Чебышева. Метод Чебышева построения итераций высших порядков [43] основан на отыскании корней уравнения /(х)=0. По модифицированному методу Чебышева [44] рассматривается уравнение х,у)=0, (15) где х<=\а, Ь ], у - искомая функция или г0=Г(х, у0), где у0 - приближенное значение искомой функции на заданном промежутке а, б]. Пусть функция г=Е{х,у) непрерывно дифференцируема достаточное число раз по у в окрестности точки у0. Формула для построения итераций высших порядков по модифицированному методу Чебышева [44, 45] имеет вид

3 12?К*,у,У-4>М2?Ы ,, ч

---77YT-ч s -z \Х,у.)----.

Zy (х, У,)]

Если в выражении (16) оставить два члена, получится итерационная формула второго порядка (метод Ньютона) [1]. Если оставить три члена, получится итерационная формула третьего порядка, и т.д.

Модифицированный метод Доморяда получается при задании уравнения (15) [2,44]. Итерационный метод Доморяда второго порядка сходимости совпадает с итерационным методом Ньютона. Итерационные формулы третьего и четвертого порядка сходимости соответственно имеют вид

F(x> У,Ж(Х>У^ где

A=[F'y{x,yi)]2-F(x, yi)F;(x,yi)/2,

B=[Fy{x,yi)f - F{x, у;Уу(х,У;)Р;(х,У;)+[Р{х, yi)]2F;(x,yi)/6.

Еще одним примером итеративного процесса является метод «цифра за цифрой». Для нахождения x=log2у (l<.y<2) ищется значение л: в двоичной системе:x=a0,aja2 . аи . (аг=0,1 ). Последовательно определяются хп> Уп> ап (л =0,1,-•■)*<)=*> Уи=У\ а{ = 0, если у\<2, оц = 1, если У2 >2. Пусть уже определены al5 a2, ., аг-! и найдено уг Если yi <2, то a• = 0, yi+l=yf. Если у] > 2, то а,- = 1, yi+l=2~lyf. После п шагов найдутся п цифр двоичного разложения x=log2 у « 0, at a2. .an .

В' алгоритмах вычисления функций, основанных на методах «цифра за цифрой», используются итеративные процессы, позволяющие последовательно определять цифровое значение /-го разряда аг искомого значения функции f{x), заданной в позиционной системе счисления. Большинство алгоритмов рассматриваемого вида разработано для двоичной системы счисления, хотя имеются алгоритмы для десятичной и произвольной систем счисления [2]. Длительность работы алгоритма пропорциональна числу разрядов с достаточно большим значением коэффициента пропорции. Схема «цифра за цифрой» по этим причинам не соответствует архитектуре суперкомпьютеров, число разрядов мантиссы в которых достигает 256 и более цифр [46 - 52]. Трудности усугубляются тем, что в описаниях метода, как правило, не указывается зависимость точности аппроксимации функции от диапазона изменения независимой переменной'. С другой стороны, методы типа «цифра за цифрой» успешно применяются в специализированных устройствах, где упрощается обработка текущего разряда [53, 54]. Очевидна возможность конвейеризации метода в общем случае.

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

Методы кусочной аппроксимации можно условно разделить на три группы: простая сегментная аппроксимация, телескопическая сегментная аппроксимация и нониусная сегментная- аппроксимация: При простой сегментной аппроксимации исходный промежуток \а, b\ разбивается на ряд непересекающихся подынтервалов. На каждом подынтервале искомая функция f{x) приближается многочленом, дробно-рациональной или нелинейной функцией, содержащей малое количество параметров и операций. Простую сегментную аппроксимацию наиболее удобно реализовать в вычислительной системе, если на всех подынтервалах функция1 /(х) приближается выражением одного вида. Частным случаем такого приближения является сплайн. Пусть отрезок \а, б] разбит на N равных частичных отрезков *,•+)]> где Х;=а+1Ъ, 1=0,1,.,N -1, хы=Ь, к={Ь-а)!N. Функцию &т (х) называют сплайном степени т дефекта к, если Зт(х) - полином степени? т на частичном отрезке [д:,-, х(+, ] и £т(х) е С тк \а, Ь]. На практике наиболее широкое распространение получили^ сплайны третьей' степени, имеющие на [а, Ъ\ непрерывную, но крайней мере, первую производную [55, 56]. При условии высокой точности резко* возрастает количество частичных отрезков и; как следствие, время г вычисления. С возрастанием степени сплайна возрастает число уравнений-системы, по которым: согласуются: значения производных, поэтому на; практике: ограничиваютсясплайнами невысокой степени.

При нониусной кусочной аппроксимации сначала аргумент приводится к нониусу (относительно небольшому промежутку), в котором вычисляется; нониусное значение функции. Затем с использованием опорных; значений, получают искомое: значение функции. Опорные значения могут находиться в: памяти вычислительной системы или вычисляться каким-либо быстрым» способом. В основу нониусной кусочной аппроксимации могут быть положены разложения функций по невязкам [36, 57 - 59]: К ним примыкают методы;. называемые табличными или. таблично-алгоритмическими- [6, 60 -63].

При' телескопической сегментной аппроксимации система вложенных подынтервалов; строится; так, что они- имеют вид +/г(х)), где ¡г{х) зависит от свойств функции /(х)1 и количества.точек разбиения. В некоторых случаях систему подынтервалов выбирают таким способом, чтобы> на больших подынтервалах многочлен, аппроксимирующий функцию, имел на одно слагаемое больше, чем на меньших подынтервалах. При этом-каждому подынтервалу соответствует многочлен с разными коэффициентами [36, 64, 65].

Для приближения функций в вычислительной системе часто используется интерполирование функций. Пусть на отрезке \а, b] задано п+1 значение функции y=f(x): y0=f(xQ), y.x=f(X]), ., yn=f(xn) в точках а<х0 < x1 <х2 <. < хп < b, которые называются узлами интерполяции. Требуется построить интерполирующую функцию F{x), принадлежащую определенному классу и принимающую в узлах интерполяции те же значения, что и fix). Если интерполирующую функцию F(x) задать в виде многочлена Рп{х) степени не выше п, то всегда существует только один интерполяционный многочлен, который может быть представлен в различных формах. Таблично заданную функцию {хг}, /(х;), /=0,п, можно приблизить с помощью многочлена Лагранжа

Р М- ги \ )(х~хг) (*~*н) , \ (х-х0){х-х2) ■■• (х-х„) хо-^ххо-хз) ••• (х0-х„) (л^ - х0 ДЛ^ ~ Х2) ••• - X „) /(* )- (Х-Хо)(Х~Х\) ••• (Х~Хп-\)

Хп~ХоХХп~Х\) {Хп~Хп-1)

Интерполирование с использованием многочлена Чебышева функции п х)ща, Ь] базируется на минимизации выражения тах ^(х-х^). Узлы к=О интерполяции выбираются в нулях многочлена Чебышева: х1 =(а + б)/2+((б-а)/2)-со8 [(2/+1)я/(2и+2)], /=07п. Интерполяционный многочлен имеет вид / 1 л л г (2х-Ъ-а\

2 к=1 V. Ь~а ) где Ак=——^/(^соб^*"1"^71, к=0,п; Тк(х) - многочлен Чебышева. п+1 2 п +2

Если функция /(х) для хе[0, 2тг] является периодической с периодом Т=Ь-а и задана в 2п+1 узлах интерполяции /(.хк), А:=0, 2и, и у(а)=у(Ь), то ее можно интерполировать тригонометрическим многочленом о. п х) =~ + ХКя* со8 кг + Ьк бш кг), 2 к=1 где хе[0, 2%).

Ъ—а

Для приближения функций, кроме многочленов и рациональных дробей, используются и более сложные выражения [66 - 74]. Рассмотрим две ограниченные функции /{х) и тз(х): М, < /(*)< М2, 0 < А^, < ш(*)< заданные на множестве

Х={хеХ:а<х<$}, (17) содержащем не менее тп + 2 точек, и приближающую функцию

Г(А,х)=Е(а0,а1,.,ат;х), А&Р, (18) где Р — открытое множество (т+1)'-мерного пространства.

В качестве меры близости функций /(х) и ^(А, х) принимаем норму ||/ - = шах|г{А, х)|, где г(Л, х)=[/(х)-Г(А, х)]/т(х). хеХ

Необходимо найти такую функцию В вида (18), чтобы

Х&Л.

Таким образом, ищется наилучшее приближение с весом ш(х) выражением вида (18) функции /(х) на множестве чисел (17).

Приближения тригонометрическими полиномами используются, как правило, для характеристики качеств аппроксимируемой функции, выражаемых периодическими свойствами [75 - 77]. Это делается для того, чтобы получить по возможности адекватное представление о физическом процессе, который выражается посредством аппроксимируемой функции. В качестве одного из источников приближения функций тригонометрическими полиномами используется интерполяция на основе полиномов Чебышева. Полиномы Чебышева I и II рода традиционно [30, 78] обозначаются Тп (х) и

Un(x). Для цели аппроксимации функций используются соотношения: r„(x) = cos(«6), X = COS0, r2w(sin0)= (-1)" cos(2«0), (19)

T2n+l (sin 0) = (-1)" sin((2« + 1)0), (20)

Un (x) = cosec (0) sin((n +1)9), x = cos 0,

COS0

22)

COS0

На этой основе конструируется полином, интерполирующий функцию /(х), в виде m

23) z = 0

Чаще встречаются разложения по ортогональным полиномам [43] вида - Рп (4

Рп СХ)=С0 + ClTl iX)+c2T2 (*)+- + с„ Тп М>

С0=— J/(cos в) d0, ск=- J/(cos cos кв dO, (k>l),

7Г Q 7Г q

24) где Тк (х) - алгебраические полиномы. Такие приближения используются в качестве наилучших среднеквадратичных приближений. С другой стороны, приближения (19) - (23) используются как среднеквадратичные приближения функций непосредственно тригонометрическими полиномами, в частности, для приближения функций, заданных таблицей, по методу наименьших квадратов. В последнем случае тригонометрические полиномы образуют ряд Фурье [43]. Обе формы интерполяционных полиномов связаны между собой, допуская преобразование одной формы в другую. Эти преобразования основаны на известных рекуррентных зависимостях [30, 78]

ТтЛХ)=2хТт(Х)-Тт-х{Х) 1

Г0(х) = 1, 7;(л;)=л; У

0(х)=1, и1(х)= 2х ]'

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

РА{х)=а$ хА + ах хъ + . + а4 используется преобразование:

Ф) = «оЫ*) + ЬМ+* +я4},

27) где

A-j ——-——, А/2 ——~— —— + (Aj + l)A, j ,

2 а0 а() а0 — + l) + A,j, —-— %2 А<з ■ aQ aQ

В качестве сложного для компьютерной реализации примера ортогональных многочленных разложений можно привести разложение [1]

1 1 a-bx Ja2—b2

Г1+2±ркТк(х) к=1 |б|<Я, I JCI <1, а-4а2~Ъ2 2 рп ь ' -р) оо l + 2Z(-lfqkTk(2x-l)

-, 0<jc<1, q = 2a+\-2^a2+a a+x Jâ* a +a

Формула справедлива и для комплексных а при ] , аФ0.

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

Для показательной функции используется разложение по многочленам Чебышева [1]:

2х-22 о

Гл \ оо (л Л

1п2 ч2 у к=1

2ЕА -1п2 Тк{2х-\) У 0 <х< 1, при к>4 к з2 -ю-* к\

Для вычисления гамма - функции и ее преобразований [79]:

00

Г(г)=рг \е~рЧ2-хЖ, Я{р)>О, Я(г)>0; о если 0<7фг)<1;

Г(г+п)= п-1 к=О г(г)г(1 - г)=71 созес 7Г г; Г(тг)={24Х~т)12ттг-1121[Т{г+г/т)включая логарифмическую производную а х¥(г)=—либо \nT(z) = ZЫt)dt; с12 1 ш-1 иг)=/и 1 ^^{г+к/гг^+Хпт; к=о п-1 о

1)=-у, у=0,57721566490153286061; используются следующие разложения [79]:

1пг(2+1)=£(-1)Ч^Л> М<1, к=\ г = 1

1/Г(г + 1)=2>*г\ До=1, Н<оо, к=0 г гаг = Ц{-1) к+^кагк, г> 0, ¿=1 а также разложение в ряд Тейлора [79]: оо оо и =0 л=О

Помимо того, применяются ортогональные разложения по полиномам Чебышева:

00 00 п=0 п=О ии ии

Г(1+3)=2>Х(*Х Г(1+х)=^7Г(х), 0 <х< 1 п=О

1пГ(х)= и=0 П 1

1пх -х +—1п27г+5,(х), х-

2, ф)=(12*Г'2;(-1)чг2„ п=О

Г-1

Vх/ х>1

Т(т)(х+3)=|;С^)Г;(х), т=0,1,.,6, ^(0)(х+3)=^(х+3), 0<х<1. п= О

Примером рационального приближения функции ^(г), представимой в виде гипергеометрического ряда ^(г) +у служить приближение вида [79]:

2И

3^2

1,1,2-г 2,1+г

-1 может

ЛЛ >-( >"к [(2)4]2(3-г)4 4 \ 1+*. 2+4, 3

4(г)=(г3+387г2 + 2906 г+192о)/12,

4(г)=(зг4 + 3643 г3 + 86068г2 + 293508г+ 149760)/б0, 1

Я3(г)=14г2+204г+ЗЮ, Я4(г)=22г3+864г2 + 4958г+4956 . Для вычисления кубического корня предлагается [79] аппроксимация Паде:

- 1 у/з 1+V (4/3) Вп (г,1/3) , , il.il V ^

-1/3(2/3)„^(г,-1/3) 1/3), ф)пВп(гМъ) агё(1+ 1/г)| < 71,

2?и (г, 1/3) =«0-1 ±ак гк , Вп (г, -1/3) '' ** • к=0 £=0

Для интегралов Френеля используются разложения вида [79]: )г1/2 соз/^=х,/2Г2п(х/8), |Г1/2 *ШЖ=хх1г Т2п+1(ф), 0 <х< 8, л=0 и=0 п=О

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

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

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

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

К цифровым .фильтрам относятся- фильтры с конечной импульсной характеристикой (КИХ-фильтры) и фильтры с бесконечной импульсной характеристикой (БИХ-фильтры). КИХ-фильтром - называют фильтр, у которого импульсная характеристика представляет собой конечный дискретный сигнал (Л^-точечный дискретный сигнал), который может принимать от нуля; значения: лишь при п=0,1, .,N-1БИХ-фильтром называют фильтр, у, которого импульсная характеристика может принимать отличные от нуля значения на-бесконечном множестве значений; п=0,1,. В случае, когда представляемая последовательность имеет конечную длительность, т.е. имеет только конечное число ненулевых значений,. используется1 вид преобразования Фурье, называемый ДПФ. ДГГФ есть преобразование Фурье4 последовательности конечной длины, являющееся? само по себе также последовательностью; а не непрерывной функцией, которое соответствует равноудаленным по частоте выборкам преобразования Фурье-сигнала.

Спектральный анализ; можно проводить > путем? вычисления спектров; с помощью ДПФ или с применением статистических методов: На- практике при спектральном-анализе,, как правило, используются БПФ и основанная на нем методика вычисления'быстрой свертки.

Несмотря? на наличие процессоров- ЦОС с быстродействием: порядка нескольких миллиардов комплексных умножений в< секунду, проблема; повышения' быстродействия? алгоритмов ЦОС остается? актуальной [82, 83]. Это связано с тем, что ряд задач, например цифровая обработка движущихся изображений; в; реальном масштабе; времени, требует больших вычислительных затрат. К числу таких задач относятся также различные видеосистемы слежения; и телеметрии. Значительные вычислительные, а следовательно; и аппаратурные затраты, необходимы при реализации нерекурсивных фильтров- нижних частот высокого порядка. Такие фильтры применяются в качестве ограничителей спектра; перед вторичной-дискретизацией сигнал а. в высокоточных скоростных интегральных аналогов цифровых преобразователях на основе дельта-модулятора.и; сумматора (ДЕ ,-АЦП). Применение быстродействующих алгоритмов- цифровой фильтрации позволяет сократить аппаратурные и вычислительные затраты, снизить стоимость устройств или систем. Кроме этого, появляется возможность уменьшить габариты, массу и энергопотребление [82], что особенно важно для бортовых систем и систем с автономным питанием. В системах ЦОС, работающих под управлением вычислительных систем, применение быстродействующих алгоритмов фильтрации дает возможность реализовать часть подсистем программно и, таким образом, отказаться от ряда средств аппаратной поддержки.

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

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

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

Для двух заданных последовательностей конечной длины х(к) и к{к) с длиной Ы^ и Ы2 соответственно линейная свертка равна оо оо у(п)=к(п) <8> х(п к=-<я к-О где М = Их+И2- 1. Для двух заданных последовательностей х(к) и у(к) длины N с нулевыми средними значениями оценка их взаимной корреляции равна г. где гху{п) - оценка взаимной ковариантности, определяемая как Xх(к)у(к+п,), п= 0,1,2,. гху{п) =

N ь=о

ЛГ+л-1

1 ^+/7-1

- "=0,-1,-2,. ги(о)=± ТШ]1» «-„(о)=1 2 •

М к=0 ¿=0

Оценка автокорреляции рд:х(и) последовательности х(к) длины N с нулевым средним значением задается как ч гх(п) где гхх(п) - оценка автоковариантности, определяемая как Ы-п-1

М = — Xх{к)х{к+п), п= 0,1,2,.

Уравнение для фильтрации с конечной импульсной характеристикой имеет вид:

N-п-\ у(п)= /г (к)х(п-к), к=0 где х(^) и у{к) — соответственно вход и выход фильтра, а к(к), к = 0, 1,., 7У-1 - коэффициенты фильтра.

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

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

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

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

Анализ непрерывных (аналоговых) линейных стационарных систем в случае нулевых начальных условий при частотном подходе выполняется в последовательности [84]:

- с помощью прямого преобразования Фурье определяют спектр Х(у со) входного сигнал *(/);

- умножением спектра ^Т(у'со) на комплексный коэффициент передачи системы //(у ю) находят спектр выходного сигнала у(7):

- с помощью обратного преобразования Фурье функции Дую) вычисляют реакцию у{Г) системы на воздействие х{{).

Сравнение спектров непрерывных х(/) и дискретных сигналов позволяет выявить их общие свойства и различия. Общим является то, что периодические сигналы описываются рядами Фурье, а непериодические -преобразованиями Фурье. Спектры периодических сигналов — дискретные линейчатые, расстояние между спектральными линиями определяется частотой повторения сигнала. Спектральная плотность непериодического аналогового сигнала представляет собой непрерывную функцию частоты со, а спектр дискретного сигнала х\п\ - периодическую функцию частоты со с периодом, равным частоте дискретизации юд = - 2%/Т.

Анализ дискретных линейных стационарных систем в случае нулевых начальных условий при частотном подходе выполняется в последовательности [84]:

- с помощью прямого ДПФ определяют спектрХ(к~) входногосигнала х[и], {п = О, N -1);

- умножением всех компонент спектра Х{к) на комплексный коэффициент передачи системы для соответствующих частот находят спектр выходного сигнала у\п\:

Y(k) = Х(к)Н f .271 ^

J-* ч NT (к = 0,N

- с помощью обратного ДПФ функции У(к) вычисляют реакцию у\п\ системы на воздействие х[п]. I

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

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

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

Существует множество применяемых для данных целей преобразований. Преобразование Винограда-Фурье [85 - 87] и алгоритм первоначального множителя [85, 87] представляют собой оригинальные, но сложные методы повышения скорости вычисления БПФ. Дискретное косинус-преобразование особенно целесообразно для сжатия данных. В рамках преобразования Уолша сигнал раскладывается на прямоугольные импульсы; а не на синусоиды, и преобразование вычисляется быстрее, чем БПФ. Преобразование Адамара, построенное с помощью перестановки последовательности Уолша, вычисляется еще более быстро. Преобразование Хаара полезно для определения краевых элементов при Обработке изображений [88].

1. Дискретное косинус-преобразование по сути представляет собой действительную часть ДПФ п=О v N

2. Дискретное преобразование Уолша [89] основано на наборе гармонических прямоугольных импульсов, которые называются функциями Уолша WAL (n,t) (t — время, п - порядок). Четные функции WAL(2£, t) записываются как CAL (A:, t), а нечетные функции WAL(2¿+1, t) записываются как SAL(2á:+1, t), где к=\, 2,., N/2—1. Любую функцию f{t) можно разложить по набору функций Уолша (аналог разложения в ряд Фурье) как

N/2-XN/2-1 tf0WAL(0, t)+ £ Xk SAL(i, t) + b, CAL (y, t)],

1=1 j=i где а,- и b — коэффициенты ряда.

3. Преобразование Адамара (Уолша-Адамара) - это, по сути, то же преобразование Уолша, но с другим порядком функции Уолша и, следовательно, строк матрицы преобразования. Получающаяся при такой перестановке матрица Адамара содержит подмассивы матриц второго порядка. Например, матрицу Адамара порядка 8x8 можно записать через матрицы

2Н=

Любую матрицу Адамара порядка 2И можно рекурсивно получить из 2Н как

1 1" и — 2Н= "-1 -1~

1 -1 -1 1

Н= N н N н н -"н

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

Фурье-образ которой

Н( со)=л/2^е(с0~Юо)2/2-Остальные (дочерние) функции получаются путем такого изменения масштаба материнской, чтобы образовалось семейство функций. Каждую дочернюю функцию можно записать как

-^{(г-т )/*},

Ыа где а - переменный коэффициент масштабирования, т - константа переноса.

В большинстве (фактически во всех случаях) рассмотренных преобразований необходимо вычислять базисные, функции. Так, в двух последних случаях это* е,ю°' , е~' e"(U)wo) jj преобразованиях Фурье к2%п\ . (к2пп\ гг такими функциями являются cos - и sin -— . При вычислении

N* V Nкорреляции присутствуют операции- деления и вычисления; квадратного? корня: рху{п)= у / \ 1/2 • В ряде ортогональных разложений! ^хх У^туу \Р/] базисными функциями; являются алгебраические: и тригонометрические: полиномы. Рассмотренные базисные функции необходимо вычислять для каждого элемента прямого и, обратного ортогональных разложений; г поскольку аргументы базисных- функций меняются в зависимости от порядкового номера элемента базиса.

Первый важный аспект этого обстоятельства - это то, что-большой объем? вычисления: базисных функций принципиально влияет на быстродействие ЦОС в целом.

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

Если алгоритм; вычисления базисных функций не инвариантен относительно вида: рассматриваемых математических^ преобразований,, то этим ограничивается возможность одновременного* использования различных ортогональных преобразований для обработки сигналов.

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

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

На основании изложенного целью диссертационной: работы является разработка и исследование: компьютерных алгоритмов- минимизации' временной сложности вычисления функций с обеспечением инвариантности! алгоритмов относительно вида функций,, точности их вычисления; промежутка изменения аргумента. Оптимизированные алгоритмы должны, применяться для параллельного вычисления одновременно всех, элементов; базиса ортогональных разложений, используемых в ЦОС, и при этом отличаться: инвариантностью относительно вида разложений; быть совместимыми с параллельным выполнением базового набора операций ЦОС в целом. I

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

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

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

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

4. Разработать метод параллельного вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью Т- ЛО, который отличался бы инвариантностью относительно количества отсчетов и сохранял данный порядок оценки при параллельном выполнении ДПФ и обратного дискретного преобразования Фурье (ОДПФ) в целом.

5. Синтезировать алгоритм параллельного выполнения ДПФ и О ДПФ на основе таблично-алгоритмической аппроксимации всех элементов базиса с временной сложностью Т = 0 (1оё2 А^), который отличался бы минимизированнымь до значения 0(1) числом последовательных умножений, а также инвариантностью относительно количества отсчетов в условиях произвольно заданной границы погрешности вычислений.

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

Методы исследования опираются на теоретические основы информатики и информационные технологии, на методы прикладной информатики, численного анализа, теории сложности, теоретические и прикладные методы ЦОС.

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

Научная новизна диссертационной работы заключается в следующем:

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

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

3. Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма, - предложенные схемы ускоряют известные методы в 0(\og2m), где т — степень аппроксимирующего полинома, и позволяют достигать времени O(l) параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций.

4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью Т = 0(log2 N), который отличается инвариантностью относительно количества отсчетов N и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в делом. В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов заключается в сокращении до 0(1) количества последовательных умножений в условиях произвольно заданной границы погрешности вычислений.

5. Предложены модификации параллельных схем выполнения ДПФ для параллельного выполнения БПФ и вычисления частичной суммы ряда Фурье. Разработанные схемы распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей операции корреляции, свертки, ковариации и ОДПФ, при- этом сохраняется- логарифмический порядок оценок временной сложности. Видоизменения данных схем с сохранением порядка оценок распространяются на случай двумерных ДПФ и ОДПФ: Предложенные схемы отличаются от известных аналогов построением, сокращением числа последовательных умножений и, в частности, тем, что число процессоров модифицированного БПФ сокращается в \og2 N раз при сохранении логарифмической оценки временной сложности вычисления.

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

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

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

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

3. Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной-временной .сложности алгоритма. Предложенные схемы ускоряют известные методы в 0{\о£2т), где т - степень аппроксимирующего функцию полинома, и позволяют достигать времени 0(\) параллельного выполнения1 комплекса данных вычислительных схем для априори-заданных функций.

4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ' с временной сложностью \0g2N), инвариантный относительно количества отсчетов N, который сохраняет порядок данной оценки при параллельном выполнении ДПФ и- ОДПФ в целом. При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до 0(1) в условиях произвольно заданной границы погрешности вычислений.

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

Данные схемы с сохранением порядка оценок распространяются на двумерные ДПФ и ОДПФ.

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

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

Внедрение и использование результатов работы. Результаты диссертации приняты к использованию в ОАО «Таганрогский завод «Прибой» в качестве единой распараллеливаемой схемы минимизации временной сложности кусочно-полиномиальной аппроксимации функций применительно к основным алгоритмам ЦОС; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО «ТГПИ»; в учебном процессе факультета информатики Таганрогского государственного педагогического института в курсах «Математика и информатика», «Численные методы», «Компьютерное моделирование», курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 3 к диссертационной работе.

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

-Международная научно-техническая конференция «Математические модели и алгоритмы для имитации физических процессов» (Таганрог, ТГ1Ш, 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 наименований.

3.9. Выводы

1. Предложен метод параллельного вычисления всех последовательных элементов тригонометрического базиса ДПФ на основе схемы Стоуна с временной сложностью Т= 0{[og1N\, который отличается от известных аналогов по построению, инвариантностью относительно количества отсчетов, при этом позволяет сохранять- данный порядок временной сложности при* параллельном- выполнении ДПФ и О ДПФ с применением схемы сдваивания.

2. Синтезирован алгоритм параллельного выполнения ДПФ и ОДПФ на основе таблично-алгоритмической аппроксимации всех последовательных элементов базиса с помощью интерполяционного полинома Ньютона с временной сложностью Т= 0(к^2 ТУ"), который отличается от известных аналогов по построению, сокращенным-до О(ь) числом последовательных умножений и инвариантностью относительно количества отсчетов.

3. Алгоритмы параллельного выполнения, ДПФ и, ОДПФ; на основе схемы Стоуна и таблично-алгоритмической аппроксимации-распространяются на параллельное вычисление частичной суммы ряда Фурье с сохранением логарифмических оценок временной' сложности.

4. Предложенные параллельные схемы, выполнения ДПФ и ОДПФ модифицируются для параллельного выполнения БПФ, распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей-операции корреляции, свертки, ковариации, сохраняя при этом логарифмический порядок оценок временной сложности. Данные* схемы с сохранением порядка оценок распространяются на случай, двумерных ДПФ и ОДПФ. Схемы отличаются от известных аналогов по построению и, в частности, тем, что число процессоров модифицированного БПФ сокращается в N раз при сохранении временной сложности вычисления.

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

ЗАКЛЮЧЕНИЕ

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

Работа включает следующие научные результаты.

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

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

3. Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма. Предложенные схемы ускоряют известные методы в где т - степень аппроксимирующего функцию полинома, и позволяют достигать времени <9(1) параллельного выполнения комплекса данных вычислительных схем для априори заданных функций.

4. Разработана динамически распараллеливаемая схема вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью Т = 0 ЛГ) инвариантная относительно количества отсчетов А/", которая сохраняет порядок данной оценки при параллельном выполнении ДПФ и ОДПФ в целом. При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до 0{\) в условиях произвольно заданной границы погрешности вычислений.

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

Научная новизна'результатов диссертационной работы заключается в следующем.

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

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

3. Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, ' показывающие отличительно высокую точность вычисления функций, производных и интегралов, при минимальной временной сложности алгоритма,. — предложенные схемы ускоряют известные методы в 0{\о%2т\, где т - степень аппроксимирующего полинома, и позволяют достигать времени 0( 1) параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций.

4. Разработан метод динамически распараллеливаемого вычисления всех последовательных, элементовтригонометрического базиса ДПФ с временной сложностью Т = 0(Лг), который отличается инвариантностью относительно количества отсчетов. N и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в целом: В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов, заключается в сокращении до 0( 1) количества последовательных умножений в,условиях произвольно заданной границы.погрешности вычислений.

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

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

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

Практическое использование результатов работы.

Полученные в» работе результаты использованы в ОАО «Таганрогский завод «Прибой»; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.00106436; в учебном процессе кафедры информатики Таганрогского государственного педагогического института в курсах «Математика и информатика», «Численные методы», «Компьютерное

1. Люстерник Л.А., Червоненкис О.А., Янпольский А.Р. Математический анализ: Вычисление элементарных функций. - М.: Физматгиз, 1963. — 248 с.

2. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ: Справочник. -Киев: Наукова думка, 1985. 600 с.

3. Кобзев В.А. Синергетический метод аналитического конструирования систем взаимосвязанного управления движением гидросамолетов / Автореферат диссертации на соискание ученой степени кандидата технических наук. Таганрог: ТРТУ, 2006. - 17 с.

4. Ланцош К. Практические методы прикладного анализа. М.: Физматгиз, 1961.-524 с.

5. Литвин О.М., Рвачев В.Л. Класична формула Тейлора, й узагальнення та застосування. Киев: Наукова думка, 1973. — 122 с.

6. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977. - 726 с.

7. Белага Э.Г. О вычислении значений многочленов от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики, 1961. Вып. 5. - С. 7-15.

8. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Проблемы кибернетики, 1961. -Вып. 5.-С. 17-29.

9. Fike С.Т. Computer evaluation of mathematical function. New Jersey: Prentice-Hall, 1968. - 228 p.

10. Winograd S. On the Parallel Evaluation of Certain Arithmetic Expressions. "Journal ACM", 1975. v. 22, № 4. - P. 477-492.

11. Winograd S. On the Speed Gained in parallel methods. "New Concepts andi

12. Technologies in Parallel Information Processing, Ed. Coianielle, Leiden, Nordhoft, 1975", 1975.-P. 155-165.

13. Motzkin T.S. Evaluation of polinomials. Bull. Amer. Math. Soc, 1956. — 61, №2.-P. 163.

14. РоммЯ.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. Таганрог: ТРТУ, 1998. - 546 с.; ВНТИ Центр. - № 05.990.001006.

15. Maruyama К. On the Parallel Evaluation of Polynomials // IEEE Trans, on Computers, 1973. v. c, 22, № 1. - P. 2-5.

16. Miranker W.L. A Survey of Parallelism in Numerical Analysys // SIAM Review, 1971. v. № 7. - P. 524-547.

17. Stone H.S. Problems of parallel computation. In: Complexity of Sequent. Paral Numer. Algor. // Ed. T.F. Traub. N.Y.: Acad. Press, 1973. - P. 1-16.

18. Солодовников В. И. Верхние оценки сложности, решения систем линейных уравнений. В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. - Л. - 1982. Т. 118. - С. 159-187.

19. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре // Кибернетика, 1977. № 6. - С. 28-40.

20. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. II // Кибернетика, 1982. № 3. - С. 18-31.

21. Котов В.Е. О связи алгебраических и архитектурных аспектов параллельных вычислений. В кн.: Вычислительные процессы и системы. Под ред. Г.И. Марчука. - М.: Наука, 1983. - С. 54-80.

22. Миклошко И. Связь между алгоритмами, программами и структурой параллельных ЭВМ. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. - М.: Наука, 1982. - С. 6-36.

23. Миклошко И. Синтез параллельных алгоритмов. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. - М.: Наука, 1982. -С. 220-240.

24. Миклошко И. Сложность параллельных алгоритмов. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. — М.: Наука, 1982. - С. 241-253.

25. Пьявченко О.Н., Сурженко И.Ф., РоммЯ.Е. Метод распараллеливания схемы Горнера и его приложение к цифровым вычислительным устройствам // Автоматика и вычислительная техника, 1978. № 5. -С. 73-78.

26. CsankyL. Fast parallel matrix inversion algorithms // "SIAM Journal on Computers". 1976. - 5, № 4. - P. 618-623.

27. РоммЯ.Е., ШаповалВ.Г. Некоторые алгоритмы организации параллельных вычислений / ТРТН Таганрог, 1982. - 80 с. Деп. в ВИНИТИ 23.02.83, № 970-83.

28. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975. - 431 с.

29. Hart I.E., Cheney E.W., е.а. Computer Approximation, New York, John Willey, 1968.-P. 420.

30. Kogg P., Ston H.S. A parallel algorithm for the efficient solution of a general class of recurrence equation // IEEE Trans. Comput, 1973. v. c., 22. - № 8. -P. 786-790.

31. Heller D:E. On the efficient computation of recurrence relations I I ICASE Rep. NASA Langley Res. Confer. Hampton, Va, Dept. Comput. Sci, Carnegie. Mellon Univ, 1974.

32. Orcutt S.E. Compyter organization and parallel computing. Diss., Dept. Comput. Sci., Stanford Univ, 1974.

33. Orcutt S.E. Parallel Solution methods for triangular linear systems of equations. Stanford Electronics Labs., Stanford, Calif, Tech, Rep, 1974. -№77.

34. Голубков Ю.А.' К правильному выбору алгоритмов, аппроксимации функций для ЭВМ, работающих в реальном масштабе* времени // Электронные вычислительные машины. М.: ИТМ и ВТ АН СССР, 1965. - Вып. 3.-С. 115-154.

35. Лебедев В.Н. Введение в системы программирования. М.: Статистика, 1975.-312 с.

36. Смолов В.Б., БайковВ.Д. Анализ табличных и таблично-алгоритмических методов воспроизведения элементарных функций // Электронное моделирование, 1980. № 1. - С. 22-27.

37. ПалагинЛВ., Иванов В.А., КурчаевА.Ф., Денисенко В.П. Мини-ЭВМ. Принципы построения и проектирования. — Киев: Наукова думка, 1975. -352 с.

38. Хованский А.Н. Приложения цепных дробей и их обобщений к вопросам приближенного анализа. -М.: Гостехиздат, 1956. 203 с.

39. Боднарчук П.И., Скоробогатько В.Я. Успехи и задачи теории цепных и ветвящихся цепных дробей. В кн.: Цепные дроби и их применения. -Киев: ИМ АН УССР, 1976. - С. 5-8.

40. Скоробогатько В.Я. Теория ветвящихся цепных дробей и ее применение в вычислительной математике. М.: Наука, 1983. - 312 с.

41. Березин И.С., Жвдков НГ. Методы вычислений. Т. 1. -М.: Наука, 1970. -464 с.

42. Теслер Г.С. Модификация методов Чебышева и Доморяда построения итераций высших порядков. В кн.: Алгоритмы и программы для

43. Теслер Г.С. Вычисление некоторых элементарных функций на ЦВМ. — В кн.: Математическое обеспечение ЭВМ и эффективная организация вычислительного, процесса. — Киев: ИК АН УССР, 1976. Вып. 2. -С. 91-110.

44. Головкин Б.А. Параллельные вычислительные системы. — М.: Наука, 1980.-520 с.

45. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995. - 318 с.

46. Воеводин В.В. Некоторые машинные аспекты распараллеливания вычислений. М.: «Проблемы вычислительной математики» под руководством Г.И. Марчука. Препринт № 22, 1981. - 10 с.

47. Воеводин В.В. Математические проблемы освоения супер-ЭВМ // Вычислительные процессы и системы / Под ред. Г.И. Марчука. М.: Наука, 1985.-С. 3-12.

48. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

49. Воеводин В.В. Просто ли получить обещанный гигафлоп? // Программирование, 1995. № 4. - С. 13-23.

50. Воеводин В.В. Массовый параллелизм и декомпозиция алгоритмов // Вычисл. мат. и мат. физ., 1995. 35, № 6. - С. 988-996.

51. Meggit Т. Psevdo Division and psevdo Multiplication Process. IBM J. Res. and Dev, 1962. - v. 6, № 2. - P. 210-226.

52. Voider Т.Е. The CORDIC Trigonometric Computing Technique. IRE on* el. Comput, 1959. - v.e.c. 8, № 3. - P. 330-334.

53. Писарский A.B., Кургаев А.Ф. Нониусная аппроксимация функций. В кн.: Моделирующие гибридные системы. - Киев: Наукова.думка, 1978. -С. 117-127.

54. Попов Б.А., ТеслерГ.С. Приближение функций для технических приложений. Киев: Наукова думка, 1980. - 352 с.

55. Теслер Г.С. Сегментная аппроксимация функций, основанная на: рекуррентных формулах и разложениях в ряды невязок. — В кн.: Алгоритмы и программы для вычисления функций на ЭЦВМ. — Киев: ИК АН УССР, 1976. Вып. 3. - С. 117-125.

56. БайковВ.Д., СмоловВ.Б., Аппаратная реализация элементарных функций в ЦВМ. JL: Изд-во Ленингр. ун-та, 1975. - 96 с.

57. Оранский A.M. Аппаратные методы в цифровой вычислительной технике. Минск: Изд-во Белорус. Ун-та, 1977. - 208 с.

58. Сергиенко И.В., Теслер Г.С. Методы быстрого деления, основанные на итеративных процессах // Кибернетика, 1974. № 6. - С. 21-25.

59. СмоловВ.Б. Функциональные преобразователи, информации. JL: Энергоиздат, 1981. - 248 с.

60. Голубков Ю.А., Лебедев A.B. Некоторые пути повышения скорости вычисления элементарных функций. В кн.: Электронные вычислительные машины. - М.: ИТМ и ВТ АН СССР, 1962. - Вып. 1. -С. 20-43.

61. Писарский A.B., Кургаев А.Ф. Телескопическая аппроксимация функций // Автоматика, 1978. № 2. - С. 80-84.

62. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М.: Наука, 1981. — 720 с.

63. Коллатц JL, Крабе В. Теория приближений: Чебышевские приближения и их приложения. М.: Наука, 1978. - 272 с.

64. Barrodate I., Roberts F.D.K., Hunt C.R. Computing best Lp approximation by function non-linear in one parameter. Comput. J., 1970. - 14, № 4. - P. 382386.

65. Dunham C.B. Chebyshev approximation by A +B ln(l+Cx). II. Inst. Math. Appl:, 1972. - 10, № 3. - P. 369-372.

66. Dunham C.B. Chebyshev approximation by A{Bx). ZAMM, 1973. - 53, №6.-P. 353-354.

67. Dunham C.B. Chebyshev approximation by exponential-polynomial product. J. Approxim. Theory, 1975. - 14, № 1. - P. 77-78.

68. Dunham C.B. Approximation by ф(дх) L(Ax) on finite point sets. Ibid., 1977. - 20, №3,-P. 296-301.

69. Meinardus G. Approximation on Functions. Theorie and numerical methods. -Berlin: Springer, 1967. 198 p.

70. Meinardus G., Schwedt D. Nicht-lineare approximation. Arch. Ration. Mech. Und Anal., 1964. 17, № 2. - P. 297-326.

71. Nosenko Yuri L. Approximation of functions by some means of their Fourier series. Facta Univ. Ser. Math. AndTnf. Univ. Nis., 1998. № 13. - P. 73-77.

72. Сердук A.C. Приближение периодических аналитических функций интерполяционными тригонометрическими полиномами в метрическом пространстве L II Укр. мат. ж., 2002. 54, № 5. - С. 692-699.исслед.: 011-8612.

73. Люк Ю. Специальные математические функции и их аппроксимации. — М.: Мир, 1980. -608 с.

74. Оппенгейм А.В., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. / Под ред. С.Я. Шаца. М.: Связь, 1979. - 416 с.

75. Применение цифровой обработки сигналов // Под ред. Э. Оппенгейма. -М.: Мир, 1980.-398 с.

76. Турулин И.И. Основы теории рекурсивных фильтров с конечной импульсной характеристикой и реализующих их структур / Автореферат диссертации на соискание ученой степени доктора технических наук. -Таганрог: ТРТУ, 2000. 32 с.

77. Цифровая обработка сигналов: практический подход // Э. Айфичер, Б. Джервис. 2-е изд. - М.: Вильяме, 2004. - 989 с.

78. Рабинер Л., Гоулд М. Теоретические основы цифровой обработки сигналов. М.: Мир, 1978. - 848 с.

79. Barlow J.S. and RemondA. Eye movement artifact nulling in EEGs by multichannel on-line EOG subtrractio. // Electroencephalography and Clinical Neurophysiology, 1981. 52. - P. 418-423.

80. Bierman G.J. Measurement updating using the U-D factorization. Automatica, 1976.- 12.-P. 375-382.

81. Ifeachor E.C. A Practical Guide for MATLAB and С Language Implementations of DSP Algorithms. Harlow: Person Education, 2001.

82. Залманзон JI.A. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука. Гл. ред. физ.-мат. лит, 1989. - 496 с. - ISBN 5-02-014094-5.

83. Ромм Я.Б., Фирсова С.А. Устойчивое распараллеливаемое вычисление функций на основе таблично-алгоритмической аппроксимации с приложениями в численном анализе. Таганрог: Изд-во ТРТУ, 1999. — 86 с.

84. РоммЯ.Е., Аксайская JI.H Схема кусочно-полиномиальной аппроксимации с минимальной временной сложностью на основе интерполяционного полинома Ньютона / ТГПИ. Таганрог, 2007. - 17 с. Деп. в ВИНИТИ 12.02.2007, № 12Г-В2007.

85. Пулькин С.П., Никольская JI.H., Дъячков-А.С. Вычислительнаяматематика. -М.: Просвещение, 1980. 176 с.

86. Бахвалов Н.С. Численные методы. Т. 1. М.: Наука, 1973. - 632 с.

87. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987.-600 с.

88. Фаронов B.B. Delfi. Программирование на языке высокого уровня. -СПб.: Питер, 2004. 640 с.