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

Размещено на http://www.Allbest.Ru/

Выпускная квалификационная работа

Тема:

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



Реферат

Выпускная квалификационная работа содержит (без учета разделов в приложениях) 110 с., 39 рис., 50 табл., 4 прил. Использовано 46 источников.

Ключевые слова: дискретное преобразование Фурье, быстрое преобразование Фурье, БПФ, ДПФ, параллельное программирование, корреляционный анализ, спектральный анализ, частотно-временной корреляционный анализ, цифровая обработка сигналов, оптимизации, ЦП, многоядерные процессоры.

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

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

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

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

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

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

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

Экономическая эффективность/значимость работы: данная работа является необходимым этапом разработки корреляционного течеискателя нового типа.



Обозначения и сокращения

БПФ - быстрое преобразование Фурье; ВКФ - взаимно-корреляционная функция;

ГП - графический процессор;

ДПФ - дискретное преобразование Фурье; НИР - научно-исследовательская работа; НР - научный руководитель;

ОБПФ - обратное быстрое преобразование Фурье; ОС - операционная система;

ПО - программное обеспечение; ПФ - полосовой фильтр;

ЦОС - цифровая обработка сигналов; ЦП - центральный процессор;

ЧВ ВКФ - частотно-временная взаимно-корреляционная функция.



Оглавление

• Введение
• 1. Алгоритмы спектрального и частотно-временного корреляционного анализа
• 1.1 Спектральный анализ
• 1.1.1 Ряды Фурье
• 1.1.2 Дискретное преобразование Фурье
• 1.1.3 Быстрое преобразование Фурье
• 1.1.4 Алгоритм Кули-Тьюки
• 1.1.5 Алгоритмическая реализация обработки сигналов при решении задачи обнаружения утечек
• 1.1.6 Функции когерентности
• 1.2 Частотно-временной корреляционный анализ
• 2. Исследование и оптимизация алгоритмов спектрального и частотно-временного корреляционного анализа
• 2.1 Исследование быстрое преобразование Фурье
• 2.1.1 Последовательная реализация быстрого преобразования Фурье
• 2.1.2 Реализация быстрого преобразования Фурье на параллельной архитектуре путём распараллеливания обхода рекурсии в ширину
• 2.1.3 Анализ эффективности распараллеливания быстрого преобразования Фурье
• 2.1.4 Вычисление обратного преобразования Фурье через прямое быстрое преобразование Фурье
• 2.2 Исследование взаимнокорреляционной функции
• 2.2.1 Последовательная и параллельная реализация расчёта взаимнокорреляционной функции
• 2.2.2 Анализ эффективности распараллеливания взаимнокорреляционной
• функции
• 2.3 Исследование функций когерентности
• 2.3.1 Последовательная и параллельная реализация расчёта функций когерентности
• 2.3.2 Анализ эффективности распараллеливания функций когерентности
• 2.3.3 Оптимизация работы с памятью при расчёте функций когерентности
• 2.4 Исследование частотно-временных корреляционных функций
• 2.4.1 Последовательная и параллельная реализация расчёта частотно- временных корреляционных функций
• 2.4.2 Применение архитектурных и компиляторных оптимизаций к вычислению частотно-временных корреляционных функций
• 3. Финансовый менеджмент, ресурсоэффективность и ресурсосбережение
• 3.1 Оценка коммерческого потенциала и перспективности с позиции ресурсоэффективности и ресурсосбережения
• 3.1.1 Потенциальные потребители результатов исследования
• 3.1.2 Анализ конкурентных технических решений
• 3.1.3 SWOT-анализ
• 3.2 Определение возможных альтернатив проведения научных исследований
• 3.3 Планирование научно-исследовательских работ
• 3.3.1 Структура работ в рамках планируемого исследования
• 3.3.2 График проведения научного исследования
• 3.3.3 Бюджет научно-технического исследования
• 3.4 Определение ресурсной (ресурсосберегающей), финансовой, бюджетной, социальной и экономической эффективности исследования
• 3.4.1 Расчёт интегральных показателей финансовой эффективности
• 3.4.2 Расчёт интегральных показателей ресурсоэффективности
• 3.4.3 Расчёт интегральных показателей эффективности вариантов исполнения разработки
• 3.5 Оценка научно-технического уровня научно-исследовательской работы
• 3.6 Оценка экономического эффекта
• 4. Социальная ответственность
• 4.1 Производственная безопасность
• 4.1.1 Анализ вредных производственных факторов и санитарных норм
• 4.1.2 Анализ опасных производственных факторов
• 4.2 Экологическая безопасность
• 4.3 Безопасность в чрезвычайных ситуациях (техногенного, природного, социального характера)
• Заключение
• Conclusion
• Список публикаций студента
• Список использованных источников
• Приложение А (Обязательное). Некоторые оконные функции
• Приложение Б (Обязательное). Архитектурные и компиляторные оптимизации
• Б.1 Архитектурные оптимизации
• Б.1.1 Векторизация
• Б.1.2 Упреждающее помещение данных в кэш первого уровня
• Б.1.3 Уменьшение числа ветвлений
• Б.2 Компиляторные оптимизации
• Приложение В (Обязательное). Анализ эффективности распараллеливания вычисления частотно-временной корреляционной функции
• Приложение Г (Обязательное). Application of time-frequency correlation analysis for leak detection
• G.1 Time-frequency correlation analysis
• G.2 Algorithm of the time-frequency correlation function acquisition
• G.3 Informative assessment of time-frequency correlation function
• G.4 The study of signals received during the leakage survey



Введение

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

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

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

Несмотря на принципиальную применимость метода для решения различных задач обнаружения утечек, качество их решения определяется эффективностью цифровой обработки сигналов. Данная работа посвящена исследованию, оптимизации и программной реализации алгоритмов спектрального анализа и вычисления частотно-временной корреляционной функции, обладающей рядом преимуществ, по сравнению с традиционными подходами, для корреляционной обработки акустических сигналов в рамках проекта РФФИ (№16-37-00049).



1. Алгоритмы спектрального и частотно-временного корреляционного анализа

1.1 Спектральный анализ

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

1.1.1 Ряды Фурье

Любой ?? - периодический сигнал ??(??), изменяющийся во времени, может быть представлен в виде суммы постоянного члена и некоторого числа синусоидальных и косинусоидальных членов, имеющих частоты кратные ?? = 2 ??/??. Такое представление называется рядом Фурье и определяется следующим выражением [2]:

(1)

где коэффициенты ????, ?? = 0,1, …, ? и ????, ?? = 1,2, …, ? получаются из соображений попарной ортогональности функций sin(??????) и ??????(??????) на отрезке [0, ??] [2]:

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

(2)

(3)

В полученном представлении частоты ???? принято называть ?? ? ыми гармониками частоты ??. Следовательно, ряд (1) содержит зависящие от частоты синусоидальные и косинусоидальные члены с различными амплитудами ???? и ???? на положительных частотах гармоник ???? [2].

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

(4, 5)



После подстановки (4) и (5) в исходное выражение (1) и приведения подобных получено следующее выражение [1]

??(??) = ?^???????^????????. (6)

Комплексные коэффициенты ???? могут быть определены из выражения (6) способом, использованным ранее:

(7)

В выражении (7) интегрирование осуществляется в диапазоне [???/2, ??/2], однако из свойств интегралов периодических функциях следует, что интегрирование может осуществляется на любом интервале длительностью в период, то есть [??₀, ??₀ + ??] при любом значении времени начала отсчета ??₀ [12].

Следует обратить внимание, что в выражении (6) коэффициент ?? при члене ???? принимает как положительные, так и отрицательные значения, следовательно, половину ряда составляют отрицательные частоты ?????. Они в полной мере не имеют физического смысла и являются скорее математическим понятием, однако отрицательные частоты все же может быть интерпретированы как вращение с угловой скоростью ???? в направлении противоположном принятому за положительное [2]. Тем не менее, вследствие того, что амплитуды |????| равномерно распределяются между соответствующими положительными и отрицательными частотами, для определения реального значения амплитуды на частоте ???? необходимо удвоить рассчитанную величину [2]. Для того, чтобы перейти от формы (6) к сумме тригонометрических функций можно воспользоваться следующим выражением:



(8)

На практике, использование выражения (8) предпочтительнее, чем выражения (1). Это связано с тем, что последнее не обладает свойством инвариантности, то есть изменение начала отчета времени приводит к нетривиальному преобразованию коэффициентов ????, ????. Напротив, коэффициенты ???? в выражении (8) инварианты к выбору начала отсчета, следовательно, при наблюдении одного и того же сигнала будут получаться одинаковые значения коэффициентов [2].

1.1.2 Дискретное преобразование Фурье

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

Пусть сигнал ??(??) наблюдается на ограниченном отрезке [? ??/2; ??/2]. В таком случае, формулы преобразования Фурье совпадают с формулами для коэффициентов ???? ряда Фурье периодической функции, полученной продолжением на всю вещественную ось функции ??(??). Таким образом, формула прямого дискретного преобразования Фурье может быть получена из (7), путем замены интеграла суммой в соответствии с методом прямоугольников [2]

(9)

где ?? - количество временных отсчетов; ??/?? = ??₀ - интервал дискретизации. С учетом того, что ?? = 2??/??, выражение может быть переписано следующим образом

(10)

Если ???? = 0 при |??| > ??/2, обратная формула имеет вид

(11)

Таким образом, (10) и (11) - прямое и обратное преобразования Фурье соответственно. Последовательность |????| называют амплитудным дискретным спектром временного ряда ???? [2].

Другой распространенной формой записи формул ДПФ является запись через поворачивающий множитель

(12)

Используя (12), можно переписать (10) и (11) как

(13)

(14)

Несмотря на то, что ДПФ связано с приближенным вычислением коэффициентов ряда Фурье, оно обладает свойством взаимной однозначности образа и оригинала. Среди других свойств ДПФ - ??-периодичность последовательностей ???? и ????, что позволяет производить в (9) и (10) суммирование по любым последовательным ?? отсчетам [2].

При неправильном выборе частоты дискретизации сложного сигнала наблюдается явление растекания спектра [1]. Взвешивание окном уменьшает утечку ДПФ за счёт уменьшения уровня боковых лепестков [3]. Различные взвешенные оконные функции приведены в приложении A.

1.1.3 Быстрое преобразование Фурье

В связи с тем, что вычисление ДПФ по формулам (10) и (11) требует большого количества операций, широко используется более эффективный с данной точки зрения подход, получивший название быстрого преобразования Фурье (БПФ). В его основу положен эффективный алгоритм расчета последовательности [2]

(15)

К вычислению последовательности с помощью (15) может быть сведено как прямое, так и обратное ДПФ. Из (13) и (15) видно, что если ???? = ????, то ????/?? = ????. Аналогично, из (14) и (15) следует, что если ???? = ??????? при ?? > 0 и ???? = ???? при ?? = 0, то ???? = ????.

Эффективная схема вычисления (15) реализуется через формулу, получившую название формулы Ланцоша - Даниэльсона [2]

, (16)



где ?? = 2??, ??^' = ?? ? ??, а последовательности ??⁰, ??¹ могут быть вычислены по следующей формуле [2]

(17)

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

Таким образом, прежде всего вычисление ДПФ по методу БПФ требует разбиения последовательности ????, имеющей ?? = 2^?? членов, на ?? одноточечных последовательностей. Для этого, требуется ?? последовательных делений ???? по (16). В таблице 1 смоделирована данная процедура для ?? = 3 [2]. Связь индексов всех элементов в исходном и конечном массивах показана в таблице 2. Из таблицы 2 видно, что разбиение исходной последовательности на одноточечные сводится к перестановке элементов (операция «бит-реверсирование»), причем индекс элемента в выходном массиве получается путем «переворачивания» индекса данного элемента в исходном массиве. Далее происходят последовательные расчеты по (16) [2].

Таблица 1

Разбиение исходной последовательности для N = 8

Исходная последовательность	Этап разбиения
	Первый	Второй	Третий
??0	??0	??0	??0
??1	??2	??4	??4
??2	??4	??2	??2
??3	??6	??6	??6
??4	??1	??1	??1
??5	??3	??5	??5
??6	??5	??3	??3
??7	??7	??7	??7

Таблица 2

Связь между индексами элементов (бит-реверсирование)

Элемент	Индекс в исходном массиве	Индекс в выходном массиве
??0	000 (0)	000 (0)
??1	001 (1)	100 (4)
??2	010 (2)	010 (2)
??3	011 (3)	110 (6)
??4	100 (4)	001 (1)
??5	101 (5)	101 (5)
??6	110 (6)	011 (3)
??7	111 (7)	111 (7)

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

1.1.4 Алгоритм Кули-Тьюки

Данный алгоритм отличают наглядность (схема производимых вычислений, может быть легко изображена графически), относительная простота и достаточно высокое быстродействие. Количественно быстродействие оценивается следующим образом - количество необходимых операций умножения для БПФ имеет порядок ?? log₂ ??, в то время как для ДПФ - ??². При ?? = 1024, алгоритм БПФ выполняется примерно в 208 раз быстрее, чем ДПФ [2].

Дополнительная минимизация вычислительных операций в алгоритме Кули-Тьюки при вычислении быстрого преобразования Фурье достигнута за счёт использования разбиения исходной анализируемой последовательности на две, более коротких (рисунок 1). При этом количество операций сокращается в два раза [4].

Рисунок 1 - Замена N-точного БПФ двумя N/2-точными БПФ

Необходимо отметить, что последующее разбиение полученных последовательностей возможно проводить до тех пор, пока число отсчетов в анализируемой выборке кратно 2. При N = 8 возможное разбиение представлено на рисунке 2 [4].

Операции объединения и разбиения проводятся в соответствии с сигнальными графами [3].

В связи с тем, что сигнальный граф «бабочка» с прореживанием по времени и бит-реверсным порядком входной последовательности (рисунок 3) обладает понятной структурой и легко подаётся распараллеливанию в контексте «вычислительных задач» будем использовать его в дальнейшей работе.

Рисунок 2 - Разбиение и объединение последовательности при N = 8

Рисунок 3. Сигнальный граф «бабочка» для 8-точечного БПФ с прореживанием по времени, входные отсчёты которого подвергнуты бит-реверсивной перестановке

На рисунке 3 цифрами в прямоугольниках показаны поворотные коэффициенты. Например, 0 в прямоугольнике значит W₈⁰.

Отметим, что в этом сигнальном графе на каждом вычислительном этапе повторяется одна и та же операция, которая в литературе носит название операция «бабочка» [5].

Обозначим верхний вход через x, нижний - через y, тогда верхний выход будет определяться выражением (18), а нижний - выражением (19).

*(18, 19)

Рисунок 4 - Операция «бабочка»

1.1.5 Алгоритмическая реализация обработки сигналов при решении задачи обнаружения утечек

Обнаружение утечки корреляционно-акустическим методом сводится к вычислению взаимной корреляционной функции сигналов, поступающих с датчиков. Блок обработки сигналов, на основании полученных данных осуществляется вычисление взаимной корреляционной функции (ВКФ) [6]

(20)

где ?? = ???/2, ?1,0,1 …, ??/2 - 1

Оценка запаздывания ?? определяется по максимуму взаимной корреляционной функции ??₀ с использованием очевидного соотношения [6]

???₀ = ??₀ • ???. (21)

Размещено на http://www.Allbest.Ru/

Рисунок 5 - Схема обнаружения утечки корреляционно-акустическим методом

В соответствии с рисунком 9 расстояние от любого из датчиков до утечки (???? и ????) [1] определяется по формуле (22):

(22)

где ?? - скорость распространения сигнала по линейному участку трубопровода;

???? и ???? - расстояния от утечки до датчиков А и В соответственно; ?? - расстояние между датчиками.

Однако на практике, так как размер исследуемых выборок достаточно велик, использование (20) для вычисления корреляционной функции не является целесообразным. Очевидно, что реализация (20) требует умножения каждого отсчета последовательности ????, на каждый из отсчетов последовательности ????, то есть ??² операций умножения [1]. Так как величина ?? оказывает влияние на точность обнаружения утечки, она является достаточно большой (имеет порядок десятков тысяч), что затрудняет расчет корреляции непосредственно.

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

(23)

где ???? - прямое дискретное преобразование Фурье (ДПФ); ?????1 - обратное ДПФ; ????? - комплексно-сопряженное представление результатов прямого ДПФ.

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

Рисунок 6 - Схема вычисления взаимной корреляции через БПФ

Основным преимуществом корреляционной функции ?????? (??) является удобство последующего анализа.

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

Описанный алгоритм схематически изображен на рисунке 6.

1.1.6 Функции когерентности

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

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

(24)

где ??(•) - оператор усреднения; ????(??), ???? (??) - собственные спектры сигналов ????(??) и ????(??) соответственно. Собственные спектры сигналов могут быть вычислены по следующей формуле:

(25)

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

(26)

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

??_??(??) = ??_??(??_??(??)) = ??_??(??) + ?? • ??_??(??),

??_??(??) = ??_??(??_??(??)) = ??_??(??) + ?? • ??_??(??),

где ????(??), ????(??) - вещественные составляющие спектров сигналов ????(??), ????(??);

????(??), ????(??) - мнимые составляющие спектров сигналов ????(??), ????(??). Далее произведем расчет знаменателя (26):

????(??) = ????(??) • ?????(??) = ????2(??) + ????2(??),

????(??) = ????(??) • ?????(??) = ????2(??) + ???? 2(??),

????(??)????(??) = ????2(??)????2(??) + ????2(??)????2(??) + ????2(??)????2(??) +

+ ????2(??)????2(??).

Аналогично, производится вычисление числителя (26):

?????? (??) = ????(??) • ?????(??) = (??_??(??)??_??(??) + ??_??(??)??_??(??)) + ?? • (??_??(??)??_??(??) ? ??_??(??)??_??(??)),

?????? 2(??) = ????2(??)????2(??) + ????2(??)????2(??) + ????2(??)????2(??) +

+ ????2(??)????2(??).

Несложно убедиться в тождественном равенстве единице отношения

?????? 2(??)

????(??)????(??) ? 1.

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

В литературе [1, 9] встречаются различные подходы к вычислению функции когерентности, отличающиеся способом усреднения значения в знаменателе. Наиболее распространенным в настоящее время является метод усреднения по Бартлетту [10], который описывается (26). С учетом введенных обозначений (26) можно привести к виду

. (27)

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

(28)

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



1.2 Частотно-временной корреляционный анализ

Как отмечалось выше, в основе корреляционно-акустического метода лежит оценка времени запаздывания, которая производится, как правило, путём анализа графика ВКФ. При этом традиционно используемые ВКФ, которые могут быть получены с помощью (23), не содержат в явном виде информации о частотных свойствах исследуемых сигналов. Последнее существенно затрудняет интерпретацию графиков ВКФ в случаях, когда сигнал утечки маскируется интенсивными шумами [11]. С другой стороны существование нескольких мод сигнала утечки ведёт к ложному определению местоположения утечки, используя когерентный анализ.

Для разрешения данной проблемы, в рамках научного коллектива автора, был разработан и зарегистрирован в качестве изобретения метод частотно-временного корреляционного анализа сигналов [12]. Особенностью метода является получение частотно-временных взаимнокорреляционных функций (ЧВ ВКФ), в явном виде содержащих информацию о степени коррелированности сигналов в различных частотных областях. Алгоритм получения ЧВ ВКФ приводится далее.

Пусть сигналы x(t) и y(t) представлены дискретными последовательностями x(t_i) и y(t_i) соответственно. На начальном этапе, в соответствии с Теоремой о корреляции [1], путём поэлементного перемножения отсчетов дискретного спектра сигнала y(t_i) и результата комплексного сопряжения дискретного спектра сигнала x(t_i) вычисляется кросс-спектр сигналов Sxy (k).

(29)

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

(30)

(31)

На заключительном этапе полученные векторы обратному дискретному преобразованию Фурье:

(32)

Полученный в результате (32) сложный вектор m состоит из M векторов, каждый из которых в свою очередь содержит все отсчеты ВКФ исходных сигналов x(t_i) и y(t_i) на m-ом частотном интервале. Путём простых преобразований из векторов m могут быть восстановлены значения ЧВ ВКФ:

(33)



Поскольку ЧВ ВКФ имеет два независимых аргумента, наиболее наглядным способом ее представления является поверхность, построенная в трехмерном пространстве.

В таком случае, признаком наличия утечки является присутствие выраженных пиков на поверхности



2. Исследование и оптимизация алгоритмов спектрального и частотно-временного корреляционного анализа

2.1 Исследование быстрое преобразование Фурье

2.1.1 Последовательная реализация быстрого преобразования Фурье

По алгоритму, описанному в пункте 1.1.4, разработана функция для вычисления прямого БПФ. Экспериментальные исследования проводились на трёх процессорах Intel: Core 2 Q6700, Xeon 5160, Core i5-750. В экспериментальных вычислениях размер выборки последовательности варьировался от 4 до 131072 отсчётов. Было произведено 1000 временных замеров 1000 преобразований БПФ. Поскольку существует множество факторов, в том числе псевдопараллельная работа планировщика процессов ядра ОС, обработка прерываний устройств, способных замедлить, но не ускорить проведение вычислительной операции [12, 13], для повышения достоверности за время выполнения принималось наименьшее время по выборке. Результаты приведены таблице 3.

Таблица 3

Результаты вычисления 1000 преобразований Фурье

Размер выборки	Intel Core 2 Q6700, c. (4 ядра)	Intel Xeon 5160, c. (2 ядра)	Intel Core i5 -750, c. (4 ядра)
4	0,00024075	0,00021465	0,00015828
8	0,00075717	0,00067474	0,00044916
16	0,00211405	0,0018886	0,00128905
32	0,00541865	0,00486566	0,00333004
64	0,01335926	0,01185663	0,00821746
128	0,03145305	0,02798085	0,01862822
256	0,07274957	0,06557836	0,04182029
512	0,16645052	0,15079034	0,09292365
1024	0,37508703	0,34058475	0,20636104
2048	0,83740993	0,76407335	0,448927
4096	1,84897964	1,6919186	0,97540429
8192	4,04408304	3,72334611	2,12225743
16384	8,79226033	8,13358534	4,60217241
32768	19,0863284	17,86104067	9,90601857
65536	41,35974078	39,62870942	21,21087834
131072	89,84323728	87,70679429	45,51673787

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

В качестве инструмента параллельных вычислений в данной работе использована кроссплатформенная библиотека Intel® TBB, на основе которой в среде разработки Visual C++ 2015 создано программное обеспечение. Выбор этой библиотеки объясняется использованием вычислительных систем на базе ЦП Intel и AMD.

Для реализации параллельного вычисления БПФ использовался подход, заключающийся в распараллеливании метода обхода рекурсии в ширину при расчёте поворотных коэффициентов графа «бабочка». Основное преимущество такого подхода перед другими реализациями БПФ [14,15] очевидно и заключается в отсутствии необходимости проводить предварительный тест с целью определения оптимальных значений степеней детализации (grainsize) для различных выборок перед массивными математическими вычислениями.

Вычисление БПФ представлено в шаблоне библиотеки Intel TBB как логическая задача класса tbb::task, которая в свою очередь порождает другие вычислительные логические задачи в момент разбиения исходной анализируемой последовательности. После объединения последовательностей, соответственно созданные задачи уничтожаются.

Экспериментальные исследования были проведены на модельных примерах с размером выборки 4-131072 отсчётов. Массив входных данных состоял преимущественно из действительных чисел. Экспериментальные исследования проведены на трех процессорах фирмы Intel: Xeon® 5160, Core 2 Quad 6700, Core i5-750. В таблице 4 приведены временные результаты вычисления быстрого преобразования Фурье на многоядерных процессорах.

Таблица 4

Результаты параллельных вычислений 1000 преобразований Фурье

Размер выборки	Intel Core 2 Q6700, c. (4 ядра)	Intel Xeon 5160, c. (2 ядра)	Intel Core i5 -750, c. (4 ядра)
4	0,00056012	0,00029708	0,00017144
8	0,00084838	0,00075982	0,00043799
16	0,00225578	0,00194729	0,0010752
32	0,00570983	0,00492981	0,0028454
64	0,01372574	0,01199732	0,00738605
128	0,03214769	0,02807533	0,01685715
256	0,07459504	0,06530345	0,04056767
512	0,16966321	0,14892508	0,08994134
1024	0,23420794	0,19616322	0,13117278
2048	0,32721335	0,43127884	0,1904456
4096	0,71485054	0,93534788	0,42766034
8192	1,51241585	1,97059527	0,92581837
16384	3,18103463	4,27614957	1,87070088
32768	6,75964589	9,24869119	4,05282814
65536	14,34330215	20,55700017	8,36174447
131072	31,39113339	44,21680053	17,18434964

2.1.3 Анализ эффективности распараллеливания быстрого преобразования Фурье

В параллельном программировании для анализа эффективности распараллеливания существуют специальные показатели, такие как ускорение (8), эффективность использования (9) вычислительных ресурсов и накладным расходам (10) [17].

(35, 36, 37)

где p - количество вычислительных ядер;

T₁ - время выполнения последовательного кода;

T_p - время выполнения параллельного кода.

Произведём расчёт показателей эффективности распараллеливания для реализации БПФ (пункт 2.1.2). Результаты вычислений приведены в таблицах 5-7.

Таблица 5

Показатели эффективности распараллеливания БПФ для ЦП Intel Core 2 Q6700

Размер выборки	Sp	Ep, %	T0, c.
4	0,42981861	10,74546526	0,00199973
8	0,892489215	22,31223037	0,00263635
16	0,937170291	23,42925729	0,00690907
32	0,949003736	23,72509339	0,01742067
64	0,9732998	24,33249501	0,0415437
128	0,978392227	24,45980567	0,09713771
256	0,975260151	24,38150378	0,22563059
512	0,98106431	24,52660774	0,51220232
1024	1,601512869	40,03782173	0,56174473
2048	2,559216884	63,9804221	0,47144347
4096	2,586526185	64,66315462	1,01042252
8192	2,673922678	66,84806695	2,00558036
16384	2,763962469	69,09906173	3,93187819
32768	2,823569268	70,58923171	7,95225516
65536	2,883557799	72,08894498	16,01346782
131072	2,862057772	71,55144429	35,72129628

Таблица 6

Показатели эффективности распараллеливания БПФ для ЦП Intel Xeon 5160

Размер выборки	Sp	Ep, %	T0, c.
4	0,722532651	36,12663256	0,00037951
8	0,888026111	44,40130557	0,0008449
16	0,969860678	48,49303391	0,00200598
32	0,986987328	49,34936641	0,00499396
64	0,988273214	49,41366072	0,01213801
128	0,996634768	49,8317384	0,02816981
256	1,004209732	50,21048658	0,06502854
512	1,012524821	50,62624106	0,14705982
1024	1,73623144	86,81157202	0,05174169
2048	1,77164581	88,58229052	0,09848433
4096	1,808865596	90,44327978	0,17877716
8192	1,889452475	94,47262375	0,21784443
16384	1,902081582	95,10407911	0,4187138
32768	1,931196566	96,55982832	0,63634171
65536	1,927747682	96,38738408	1,48529092
131072	1,983562656	99,17813279	0,72680677

Таблица 7

Показатели эффективности распараллеливания БПФ для ЦП Intel Core i5 - 750

Размер выборки	Sp	Ep, %	T0, c.

Подобные документы

• Параллельные алгоритмы двумерного быстрого преобразования Фурье

  Сигнал как некоторое средство для передачи информации. Знакомство с параллельными алгоритмами двумерного быстрого преобразования Фурье, анализ способов вычисления. Общая характеристика процессора Power5 64-bit RISC. Рассмотрение функций библиотеки MPI.
  
  дипломная работа [1,6 M], добавлен 09.10.2013
  

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

  Анализ проблем, возникающих при совмещении изображений в корреляционно-экстремальных навигационных системах. Использование двумерного дискретного преобразования Фурье. Нахождение корреляционной функции радиолокационного и моделируемого изображений.
  
  дипломная работа [3,6 M], добавлен 07.07.2012
  

• Дискретное преобразование Фурье

  Разработка функции вычисления дискретного преобразования Фурье от входного вектора. Исследование свойств симметрии ДПФ при мнимых, четных и нечетных входных сигналах. Применение обратного преобразования Фурье для генерации периодической функции косинуса.
  
  лабораторная работа [228,8 K], добавлен 13.11.2010
  

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

  Разработка и анализ алгоритмов с использованием электронных таблиц и прикладных программ Smath Studio, Microsoft Excel. Проверка алгоритма ветвления или выбора. Реализация циклов на примере вычисления определённого интеграла с заданной точностью.
  
  контрольная работа [1,0 M], добавлен 19.03.2016
  

• Программирование и исследование алгоритмов вычисления определенных интегралов

  Методы и алгоритмы вычисления определенных интегралов: метод трапеций и метод Симпсона (метод парабол). Оформление функции вычисления заданного определённого интеграла на Visual Basic 6.0. Программный код функции. Создание приложения для вычисления.
  
  курсовая работа [483,6 K], добавлен 25.06.2014
  

• Разработка и реализация вычислительного устройства в программе "Minecraft"

  Разработка вычислительного комплекса для преобразования параллельного десятичного кода в двоичный; вычисления суммы или разности; преобразования результата обратно в десятичный код и отображения на дисплее. Схемы логических элементов программы Minecraft.
  
  курсовая работа [2,5 M], добавлен 25.01.2013
  

• Написание программ вычисления функций

  Принципы разработки математических моделей, алгоритмов и программ. Составление программы вычисления функции с использованием нестандартных функций. Нахождение значения корней нелинейного уравнения по методу касательных. Программа для вычисления интеграла.
  
  курсовая работа [568,3 K], добавлен 07.03.2015
  

• Составление алгоритмов и программ вычисления функций

  Использование нестандартных функций и подпрограмм (процедур) для составления алгоритмов вычислений. Программы для вычисления значение корней нелинейного уравнения по методу половинного деления. Составление алгоритма операций над матрицами и интегралами.
  
  курсовая работа [580,0 K], добавлен 23.08.2015
  

• Разработка алгоритмов и программ решения алгебраических задач численными методами

  Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
  
  контрольная работа [831,0 K], добавлен 24.11.2013
  

• Разработка алгоритма идентификации

  Состав и принцип работы аппаратуры. Выбор параметров корреляционного анализа и Фурье-анализа. Разработка и применение алгоритма корреляционного анализа. Реализация алгоритма Фурье-анализа на языке С++ и алгоритма корреляционного анализа на языке С#.
  
  дипломная работа [4,6 M], добавлен 30.11.2016
  

• Разработка специализированного процессора для исполнения элементарных функций

  Математический процессор для вычисления элементарных функций. Расчет разрядности представления данных и числа итераций. Разработка алгоритмов вычисления функции в математическом пакете. Обоснование достаточности аппаратных средств, программных ресурсов.
  
  курсовая работа [615,9 K], добавлен 19.12.2010
  

• Оптимизация структуры распределённого параллельного генетического алгоритма

  Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
  
  курсовая работа [1,3 M], добавлен 11.03.2014
  

• Вычисления по формулам. Разветвления. Циклы

  Особенности вычисления по формулам в Microsoft Visual Basic с использованием функции If. Применение циклов и разветвлений. Визуальные объекты, составление алгоритмов задачи, блок-схемы и программного кода. Введение переменных, определение типа данных.
  
  лабораторная работа [558,5 K], добавлен 23.05.2014
  

• Исследование алгоритмов принятия решений и обучение в программировании робототехнических устройств

  Анализ методов реализации интеллектуальных игр в системе человек-робот. Разработка архитектуры программного комплекса, выбор языка программирования. Алгоритм преобразования данных. Тестирование программного комплекса, редактирование и исправление ошибок.
  
  дипломная работа [2,6 M], добавлен 27.10.2017
  

• Оценка временной сложности некоторых классов алгоритмов

  Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.
  
  дипломная работа [1,6 M], добавлен 12.08.2017
  

• Программирование циклических алгоритмов на С/С++

  Описание особенностей программирования циклических алгоритмов на С/С++. Использование операторов цикла для организации повтора в программе определенных действий. Создание и реализация программы приближенного вычисления интеграла методом трапеций.
  
  лабораторная работа [86,3 K], добавлен 25.03.2019
  

• Обработка данных в автоматизированных системах

  Техническое обеспечение, расчет информационно-измерительного канала системы автоматического управления. Методическое обеспечение: описание модели АЦП, спектральный анализ на основе преобразования Фурье. Разработка прикладного программного обеспечения.
  
  курсовая работа [501,2 K], добавлен 21.05.2010
  

• Квантовые вычисления

  Основные понятия квантовой механики, понятия и принципы квантовых вычислений. Возможность построения квантового компьютера, и его преимущества перед "классическим". Алгоритм Гровера - квантовый алгоритм быстрого поиска в неупорядоченной базе данных.
  
  реферат [241,0 K], добавлен 07.05.2009
  

• Программное обеспечение вычислений

  Создание программ в Borland C++ Builder 6.0. Разработка программы для построения графика временной функции, работающей, как в машинном, так и в реальном времени. Использование алгоритма Горнера для вычисления корня квадратного и нелинейного уравнений.
  
  контрольная работа [925,2 K], добавлен 05.01.2016
  

• Разработка программы на языке Assembler с использованием процедур

  Создание программы для вычисления значения функции на основе определённой формулы. Уточнение структуры входных и выходных данных и определение ассемблерного формата их представления. Разработка алгоритмов для реализации работы программного обеспечения.
  
  курсовая работа [240,6 K], добавлен 17.06.2013
  

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