Модели и алгоритмы параллельной обработки гидроакустической информации линейных антенных решёток

Во Введении обоснована актуальность темы исследования, сформулированы цели и
задачи диссертационной работы, приведён обзор литературы по теме исследования, пред­
ставлены положения, выносимые на защиту, показана научная новизна и практическая зна­
чимость полученных результатов.
В первой главе приводятся необходимые сведения из рассматриваемой предметной
области — обработки гидроакустической информации. Рассмотрен предмет первичной об­
работки сигналов, состоящий в извлечении информации о наблюдаемом объекте непосред­
ственно из «сырых» данных, принятых элементами антенной решётки. Описаны модельные
представления первичной обработки в общем виде, которые позволяют работать не только
с традиционным плосковолновым приближением в дальней зоне, но и учитывать кривизну
волнового фронта при работе в зоне Френеля.
Выделены основные этапы пространственно-частотно-временной обработки информа­
ции -элементной линейной антенной решётки. Одним из наиболее ресурсоёмких является
этап формирования статического веера пространственных каналов в широком секторе обзо­
ра по пространству с фокусировкой по дальности (далее будем сокращённо называть этот
этап «формированием пространственных каналов» — ФПК).
Каждому углу в секторе обзора ставится в соответствие номер (который будем
называть пространственным каналом), дискретизация сектора обзора по пространству про­
изводится следующим образом:
⌊︂ ⌋︂⌊︂ ⌋︂
2
sin =, =−,…,,
( − 1)22
где — количество пространственных каналов (для удобства будем полагать, что — нечет­
ное число).
Расстояние до источника излучения априори не известно. Дискретизация по рассто­
яниям до источника производится следующим образом:
2 ( − 1)2
=, = 1, . . . , ,
2
где — количество каналов по дальности, — длина волны, — расстояние между приём­
ными элементами ЛАР. При = 0 считаем, что источник находится в дальней зоне (в этом
случае индекс в обозначениях будем опускать).
ФПК на дискретной частоте , = н , . . . , в , представляется в виде

( ) = ( ) ¯ ( ),(1)

где ( ) — -компонентный вектор спектров входных сигналов на элементах ЛАР; ( ) =
{exp{2 ( , )}} −1
=0 — -компонентный вектор, отвечающий задержкам сигнала на эле­

ментах ЛАР в частотной области для пространственного канала и канала по дальности
; ( , ) — временная задержка сигнала, пришедшего на -й элемент ЛАР; = 0, . . . , ;
= − ⌊ /2⌋ , . . . , ⌊ /2⌋.
При работе в зоне Френеля в задержках ( , ) заключается информация не только о
направлении прихода сигнала, но и о расстоянии до источника. Выражение для задержек
сигнала на элементах ЛАР в общем случае имеет вид
⌊︂ ⌋︂⌊︂ ⌋︂
( ( , ) − 1)
( , ) =, =−,…,,
22

где√︃(︂)︂2
− /24( − /2)
( , ) =1+−,(2)
( − 1)
= 1, . . . , , = 0, . . . , − 1, = ( − 1) — апертура ЛАР.
В случае, когда для поля приходящего на элементы ЛАР принята плосковолновая мо­
дель (при = 0) в выражении для задержки сигнала на -м приемном элементе содержится
информация только о направлении прихода и не содержится информации о расстоянии до
источника. При работе в дальней зоне для выражения (2) используется линейное прибли­
жение, где информация о дистанции не используется и задержки на элементах ЛАР имеют
вид⌊︂ ⌋︂⌊︂ ⌋︂
2
( ) =, =−,…,.
( − 1)22
Также в главе рассмотрена модель адаптивной обработки по выходу сформированных
пространственных каналов. Сформулирован перечень задач, которые выполняются в реаль­
ном времени программным обеспечением многопроцессорной системы. Приведены упрощён­
ные модели имитации типовых сигналов на приёмных элементах ЛАР и уплотнённых сигна­
лов, предназначенные для проверки функционирования основных задач первичной обработ­
ки.
Также в этой главе приведены основные сведения о вычислительных средствах на базе
цифровых сигнальных процессоров (ЦСП), которые применяются для обработки гидроаку­
стической информации в реальном времени. Отмечены общие для ряда специализированных
вычислительных средств современные архитектурные решения.
Приведён краткий обзор видов и способов представления параллелизма алгоритмов и
программ. Рассмотрено, введённое М. Коулом (M. Cole), понятие параллельных каркасов —
некоторых шаблонов, отражающих закономерности в организации вычислений и межпроцес­
сорных коммуникаций. Описаны известные каркасы с параллелизмом данных и с паралле­
лизмом задач.
Рассмотрено, введённое Л. Вэлиантом (L. Valiant), понятие «связующей модели» парал­
лельных вычислений. Даётся классификация таких моделей.
Обоснована актуальность построения связующей модели для встроенных многопроцес­
сорных вычислительных систем и алгоритмов обработки гидроакустической информации в
реальном времени. Формулируются требования к такой модели. Основным из которых яв­
ляется обобщение характеристик ряда существующих и перспективных технических систем
обработки гидроакустической информации, значительно влияющих на реализацию алгорит­
мов обработки.
Во второй главе предложены «быстрые» вычислительные алгоритмы для основных
ресурсоёмких задач первичной обработки информации ЛАР, т. е. такие, в которых для сокра­
щения количества арифметических операций применяются алгоритмы «быстрой свёртки».
Известно, что вычисление свёртки с помощью алгоритмов быстрого преобразования Фурье
(БПФ) имеет квазилинейную временную сложность вместо квадратичной.
В основу «быстрого» ФПК ЛАР положен известный алгоритм Блюстейна. Выполнены
преобразования выражений для ФПК ЛАР к виду, удобному для применения этого алгорит­
ма.
Пусть — наименьшее целое число, являющееся степенью 2, такое, что > + ; в
каждом частотном канале = н , . . . , в входной вектор ( ) длины дополнен нулями до
длины . Тогда ФПК ЛАР в каждом частотном канале сводится к выполнению двух БПФ
длины и трёх поэлементных комплексных умножений векторов длины . В случае работы
в дальней зоне «быстрый» алгоритм ФПК ЛАР применяется для вычисления исходного
выражения без приближения.
Для ФПК в зоне Френеля предложено приблизить выражение (2) полиномами вида

( )( )( )( )( )( )
˜ ( , ) = 0 + 1 + 2 + 3 2 + 4 2 + 5 ( − )2 .(3)

Тогда ФПК при работе в зоне Френеля легко сводится к вычислительным алгоритмам на базе
«быстрой свёртки». Таким образом, предложенный «быстрый» алгоритм ФПК ЛАР является
универсальным для случаев дальней зоны и зоны Френеля. Его вычислительная сложность в
каждом канале по частоте и по дальности составляет ( log ) арифметических операций
вместо ( 2 ).
Задача поиска набора векторов коэффициентов ( ) ∈ R6 , = 1, . . . , , полиномов (3)
состоит в решении переопределённых систем линейных уравнений (в каждом канале по ди­
станции). Для их решения применён метод наименьших квадратов.
Проведено исследование точности работы приближённого «быстрого» алгоритма ФПК
в зоне Френеля для решения задачи фокусировки. Описаны численные эксперименты на про­
граммных моделях. Их результаты показали, что для достижения точности приближения,
позволяющей решать задачи обработки сигналов в зоне Френеля, диапазон пространствен­
ных каналов необходимо разбить на поддиапазоны и для каждого сформировать свой набор
коэффициентов полиномов (3). При этом точность приближённого алгоритма ФПК позволя­
ет решать задачу фокусировки.
Выполнена оценка ожидаемого выигрыша в производительности предложенного алго­
ритма ФПК ЛАР в зависимости от количества приёмных элементов и количества простран­
ственных каналов. Показано, что для типовых параметров обработки он выигрывает в про­
изводительности в десятки раз по отношению к вычислениям по определению. Помимо этого
«быстрый» алгоритм ФПК ЛАР выигрывает и по необходимому для хранения фазовых ко­
эффициентов объёму памяти.
Далее рассматриваются вопросы применения алгоритмов «быстрой свёртки» при реше­
нии ряда других задач пространственно-частотно-временной обработки информации ЛАР.
Результаты второй главы опубликованы в работах [1—4].
В третьей главе построена связующая модель блочно-синхронно-конвейерного парал­
лелизма (БСКП) для обработки потока данных в реальном времени. Рассмотрено приме­
нение модели БСКП для проектирования пространственно-частотно-временной обработки
информации ЛАР (БСКП-обработка) и БСКП-алгоритмы восстановления данных по извест­
ным значениям в узлах равномерной сетки.
Вычислительная система в модели БСКП (далее БСКП-компьютер) включает в себя
ЭЦСП эквивалентов цифровых сигнальных процессоров (ЭЦСП), соединённых между со­
бой эквивалентом коммуникационной среды (ЭКС) с пропускной способностью машин­
ных слов в единицу времени. ЭКС является полносвязной и однородной. В составе каждого
ЭЦСП есть глобальная память объёмом машинных слов и эквиваленты вычислитель­
ных ядер (ЭВЯ) в количестве ЭВЯ , обладающие собственной локальной памятью объёмом
. Пропускная способность передачи данных между глобальной памятью ЭЦСП и ло­
кальной памятью ЭВЯ составляет машинных слов в единицу времени. Множество всех
ЭЦСП разбивается на ВВЭ непересекающися подмножеств, называемых виртуальными вы­
числительными элементами (ВВЭ). Функционирование БСКП-компьютера рассмотрено на
двух уровнях, на каждом уровне введены стоимостные компоненты вычислительного про­
цесса.
Вычисления в модели БСКП представляются в виде конвейера, состоящего из стадий,
соединённых между собой потоками по которым передаются данные. Работа конвейера рас­
сматривается как итерационный процесс, разворачивающийся во времени. На каждой ите­
рации стадия обрабатывает входную порцию данных (ВПД), полученную из входного пото­
ка. Период поступления очередной ВПД для каждой стадии задан априори и фиксирован.
Обработка ВПД в стадии представляется набором вычислительных процедур. Каждая вы­
числительная процедура завершается барьерной синхронизацией. Это гарантирует, что ре­
зультаты её вычислений находятся в глобальной памяти ЭЦСП. После завершения любой
из вычислительных процедур данные могут быть выданы в другие стадии конвейера. ВПД
разделяется на элементы порции данных (ЭПД) и распределяется между вычислительными
элементами на которых выполняется стадия, таким образом, что размер ЭПД не превыша­
ет размера локальной памяти. Операции, которые выполняются над ЭПД, будем называть
вычислительным ядром.
Далее рассматривается применение модели БСКП при проектировании программного
обеспечения пространственно-частотно-временной обработки, выполняющего функциональ­
ные задачи описанные в первой главе. При этом применяются «быстрые» вычислительные
алгоритмы, предложенные в главе 3. Приводятся вычислительные процедуры и атрибуты
каждой стадии БСКП-обработки. Для ресурсоёмких задач приводится количество арифме­
тических операций.
Предложены эффективные параллельные БСКП-алгоритмы восстановления данных по
известным значениям в узлах равномерной сетки, применяемых при имитации уплотнённых
входных сигналов и обработке сигналов прослушивания. Произведена теоретическая оценка
вычислительной и коммуникационной сложности предложенных БСКП-алгоритмов.
Результаты третьей главы опубликованы в статьях [5—7].
В четвёртой главе рассматриваются вопросы практического применения результатов
диссертационной работы в технических системах. Описана, разработанная для многопроцес­
сорных систем на базе ЦСП семейства «Комдив» (целевой многопроцессорной системы), биб­
лиотека «быстрой» обработки гидроакустической информации ЛАР, которая предназначена
для решения основных функциональных задач обработки гидроакустической информации
ЛАР. Библиотека включает в себя функции, реализующие следующие алгоритмы обработки
сигналов ЛАР: «быстрого» ФПК, вычисления фазовых коэффициентов для ФПК в дальней
зоне и в зоне Френеля, последетекторной обработки, автоматического сопровождения целей,
формирования и обработки сигналов прослушивания, адаптации, экспоненциального накоп­
ления и формирования сплошной части спектра. Приведён файловый состав этой библиотеки
и интерфейсы основных её функций.
Для анализа производительности программной реализации предложенного алгоритма
ФПК ЛАР проведён ряд вычислительных экспериментов на ЦСП «Комдив-128». Результа­
ты этих экспериментов показали, что выигрыш в производительности для «быстрого» ФПК
ЛАР сопоставим с теоретическим (полученным в главе 3). Применение «быстрых» алгорит­
мов позволяет ускорить решение задачи ФПК ЛАР в зоне Френеля на порядок по сравнению
с точным решением.
Разработана программа, предназначеная для построения по заданным параметрам обра­
ботки приближённых фазовых коэффициентов, позволяющих реализовать «быстрый» алго­
ритм ФПК ЛАР в зоне Френеля, а также выполняющая априорную оценку точности «быстро­
го» вычислительного алгоритма ФПК ЛАР. Данная программа применяется на этапе проек­
тирования программного обеспечения систем реального времени пространственно-частотно
временной обработки в зоне Френеля.
Далее рассматривается программная реализации «быстрой» БСКП-обработки инфор­
мации ЛАР для целевой многопроцессорной системы с использованием имеющихся в рас­
поряжении технологических средств разработки. Описана логика организации вычислений
в соответствии с предложенной моделью, приводятся блок-схемы вызовов функций библио­
теки «быстрой» обработки гидроакустической информации ЛАР в стадиях, обсуждаются
вопросы распределения по процессорам в многопроцессорной системе.
Разработана библиотека, реализующая предложенные в четвёртой главе БСКП-алгорит­
мы восстановления данных по известным значениям в узлах равномерной сетки. Функции
этой библиотеки применяются для повышения частоты дискретизации сигналов при про­
граммной имитации гидроакустической информации ЛАР.
Для проверки программного обеспечения пространственно-частотно-временной обработ­
ки гидроакустической информации ЛАР разработан программный имитатор входных сигна­
лов ЛАР. Имитатор имеет модульную структуру, благодаря которой, является легко расши­
ряемым и модифицируемым.
Разработанное программное обеспечение имеет свидетельства о государственной реги­
страции [20—23].
В Заключении сформулированы основные научные и практические результаты рабо­
ты.
1. Разработан «быстрый» вычислительный алгоритм формирования статического веера
пространственных каналов в широком секторе обзора с фокусировкой по дальности.

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

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

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

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

6. Разработан комплекс программ обработки гидроакустической информации линейной
антенной решётки для вычислительных средств на базе отечественного ЦСП «Ком­
див-128».

7. Проведены вычислительные эксперименты, подтверждающие правильность работы пред­
ложенных алгоритмов.

8. Разработанное программное обеспечение внедрено и функционирует в изделиях АО
«Концерн «Океанприбор».