Обложка Хачумов В.М., Хачумов М.В. Конвейерные и разрядно-параллельные вычисления в бортовых системах навигации и управления
Id: 256908
823 руб.

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

URSS. 2019. 208 с. ISBN 978-5-396-00980-6.
  • Твердый переплет

Аннотация

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

Основные результаты получены в процессе выполнения ряда научных проектов в Институте программных систем им. А.К.Айламазяна Российской академии наук (ИПС им. А.К.Айламазяна РАН) и Федеральном исследовательском центре «Информатика и управление» Российской академии наук (ФИЦ ИУ РАН). Материалы монографии вошли в содержание отдельных разделов учебных дисциплин «Моделирование вычислительных систем», «Компьютерная графика», «Математические основы распознавания образов», читаемых в Российском университете дружбы народов (РУДН) и МИРЭА — Российском технологическом университете.

Исследование выполнено при финансовой поддержке проектов РФФИ № 16-07-00096_а, № 15-07-00925_а, № 17-29-07003 офи_м и № 16-29-12839 офи_м.

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

Khachumov Vyacheslav Mikhailovich, Khachumov Mikhail Vyacheslavovich

Pipeline and bit-parallel computing models in onboard navigation and control systems

The monograph discusses methods to organize pipeline and bit-parallel computing, gives solutions to the problems of optimizing calculations with controlled speed and required accuracy for onboard navigation and control systems. Some of the proposed algorithms are used to find the optimal combination of cycles for periodic information processing and synthesize specialized navigation and control devices. Other methods are based on the technique of converting CORDIC algorithms into bit computing schemes. The proposed approaches are designed to develop mathematical, software and hardware support for onboard computer systems of autonomous aircraft under conditions of resource constraints.

The main results were obtained in the Program Systems Institute of RAS and Federal Research Center "Computer Science and Control" of RAS through a number of research projects. The monograph materials were included in the individual sections of courses “Computer Modeling”, “Computer Graphics” and “Mathematical Foundations of Pattern Recognition”, read at the RUDN University and MIREA — Russian Technological University.

The study was financially supported by RFBR projects No. 16–07–00096_a, No. 15–07–00925_a, No. 17–29–07003 ofi_m and No. 16–29–12839 ofi_m.

The monograph is intended for researchers, engineers, postgraduates and students involved in high-performance computing for onboard navigation and control systems.


Содержание
Содержание 3
Введение 7
Глава 1. Алгоритмы CORDIC. Современное состояние и перспективы 11
1. Краткий обзор CORDIC-алгоритмов 13
1.1. Основные операции CORDIC 14
1.2. Обобщенная нотация Уолтера 17
2. Компенсация деформации вектора и ускорение вычислений 17
3. Реализация трехмерных CORDIC-алгоритмов 20
4. Выводы к главе 1 22
Литература к главе 1 22
Глава 2. Оптимизация периодической обработки информации в спе-циализированных устройствах 27
1. Подходы к планированию периодических расписаний 28
2. Построение периодических расписаний с совмещением циклов обработки 40
2.1. Системы с двухстадийным обслуживанием 40
2.2. Системы с трехстадийным обслуживанием 44
3. Многостадийные системы с периодическим расписанием работы 45
3.1. Основные понятия и определения 45
3.2. Планирование периодических расписаний для локальных алго-ритмов 48
4. Статистическое исследование расписаний для локальных алгоритмов обработки информации 53
5. Оптимизация закрепления процессорных элементов за операциями локального алгоритма 60
5.1. Алгоритм оптимизации закрепления процессорных элементов 61
5.2. Алгоритм оптимального закрепления процессорных элементов 64
6. Оценка сложности алгоритмов построения расписаний и сокраще-ние размерности 64
7. Построение периодических расписаний для систем локальных ал-горитмов 67
7.1. Расписания для систем локальных алгоритмов, ориентирован-ных на параллелизм множества объектов 70
7.2. Расписания для систем локальных алгоритмов, ориентирован-ных на параллелизм смежных операций 72
7.3. Расписания для систем локальных алгоритмов, ориентирован-ных на параллелизм независимых ветвей 75
7.4. Расписания для систем локальных алгоритмов, ориентирован-ных на смешанный параллелизм 78
8. Планирование периодических расписаний в сложных технических системах 78
9. Технология автоматического синтеза структур геометрических процессоров 82
9.1. Основные функции геометрического процессора 83
9.2. Архитектура геометрического процессора периодической обра-ботки 85
9.3. Минимизация числа процессорных элементов 87
9.4. Минимизация числа межпроцессорных связей. Синтез устрой-ства управления 90
9.5. Метод построения кортежа с минимальной суммарной длиной ребер 92
9.6. Оценка эффективности разрезания графов на подграфы 95
10. Выводы к главе 2 97
Литература к главе 2 99
Глава 3. Разрядно-параллельные вычислительные схемы 104
1. Вычисление математических функций на основе разрядно-параллельных схем 105
1.1. Вычисление обратной функции 106
1.2. Извлечение квадратного корня 110
1.3. Вычисление показательной функции 113
1.4. Логарифмирование 117
1.5. Вычисление тригонометрических функций sin(φ), cos(φ) 119
1.6. Разрядно-параллельные схемы операции «поворот» 124
1.7. Разрядно-параллельные схемы операции «вектор» 132
2. Оценка временной сложности разрядно-параллельных схем 133
3. Процессорные элементы с набором крупных операций 135
4. Решение задач в системе команд геометрического процессора 139
4.1. Алгоритмы отсечения для конвейерной графической системы 139
4.2. Отсечение графических объектов окном произвольной формы 148
5. Выводы к главе 3 149
Литература к главе 3 150
Глава 4. Построение специализированных устройств для бортовых систем навигации и управления 153
1. Алгоритмы навигации и управления в бортовых вычислительных комплексах беспилотных летательных аппаратов 153
1.1. Анализ особенностей бортовых вычислительных комплексов 153
1.2. Анализ математического обеспечения для траекторных измере-ний 156
1.3. Комплекс аффинных преобразований для БПЛА и поворотной камеры 160
1.4. Реализация дискретного преобразования Фурье 164
2. Алгоритмическое обеспечение для решения задач навигации и управления на базе алгоритмов CORDIC 165
2.1. Комплекс базовых алгоритмов CORDIC, рекомендуемый для БВК 165
2.2. Применение целочисленных алгоритмов генерации линий и по-воротов 168
3. Реализация алгоритмов CORDIC в специализированных и универ-сальных микропроцессорных устройствах 179
4. Аппаратные платформы и математическое обеспечение бортовых-вычислительных комплексов 185
4.1. Аппаратная платформа малого беспилотного летательного аппарата 186
4.2. Архитектура специализированных устройств в составе БВК 189
4.3. Разработка общей архитектуры программного обеспечения 191
4.4. Автоматизация синтеза структур геометрических процессоров 192
5. Выводы к главе 4 198
Литература к главе 4 199
Заключение 203
Содержание 3

Введение

Монография посвящена вопросам совершенствования математического и программного обеспечения бортовых систем интеллектуального анализа данных, навигации и управления. Актуальность темы определяется потребностью оснащения бортовых вычислительных комплексов (БВК) малоразмерных автономных беспилотных летательных аппаратов (БПЛА) программно-аппа¬ратными системами обработки телеметрии, потоков целевых данных от систем технического зрения и системами интеллектуального управления, способными решать задачи в условиях помех и ограниченных вычислительных ресурсов бортовых ЭВМ в реальном времени.

С учетом миссий малых аппаратов возрастает роль высокопроизводительной обработки данных на борту и выработки управления в условиях ограничений на вычислительные ресурсы. Большая роль отводится видеокамере как источнику важнейшей графической информации, которая помогает в решении задач мониторинга динамических объектов, навигации и траекторного движения, даже при отсутствии систем GPS/Glonass, но требует применения достаточно трудоемких вычислений. В комплекс задач, решаемых на борту с применением видеокамеры, входят распознавание и слежение за целевыми объектами; определение местоположения и ориентации; решение задач преследования и сопровождения целей. Реализовать весь объем алгоритмов в БВК в реальном масштабе времени с высокой точностью затруднительно из-за ограниченных бортовых ресурсов, поэтому возникает необходимость постановки оптимизационных задач по критериям времени и точности управления. Задачи реального времени решаются успешно на наземных высокопроизводительных системах, практически не имеющих ограничений. Поэтому, в ряде случаев целесообразно проводить распределение функций между землей и бортом, что препятствует построению полностью автономных аппаратов и требует надежных систем связи.

Бортовой комплекс, как правило, состоит из вычислите-лей, выполненных на базе однокристальной микро-ЭВМ, про-граммируемых логических интегральных схем ПЛИС (FPGA-Field-Pro¬gramm¬able Gate Array), сигнальных и графических процессоров с низким энергопотреблением, что важно для малых летательных аппаратов. Устройства служат вычислительной платформой, на которой можно решать сложные задачи, включая анализ и обработку навигационных данных; выработку управлений по показаниям бортовых датчиков, имеющимся топографическим данным и географическим ориентирам; мониторинг окружающей обста-новки и слежение за целями; картографирование и решение целевых задач следования по заданной траектории. Бортовая система должна обеспечивать режим реального времени, что в условиях постоянного увеличения объема решаемых задач и ограниченных ресурсов требует совершенствования и оптимизации программно-аппаратных вычислительных средств.

В монографии рассматриваются задачи оптимизации конвейерных и разрядно-параллельных вычислений для достижения компромисса между скоростью и качеством получаемых локально-оптимальных решений. Для решения задач используются алгоритмы семейства CORDIC («COordinate Rotation DIgital Com¬puter»), которые сводят вычисление сложных функций к набору простых операций сложения и сдвига. Базовые операции этого семейства, предложенные Дж. Волдером (J. E. Voider) и Дж. Мед¬житом (J.-E. Meggitt), были исследованы и развиты отечественными учеными В. Д. Байковым и В. Б. Смоловым. Выделим основные области современного применения CORDIC-алгоритмов, которые могут быть полезны на борту БПЛА: вычисление мате-матических функций, преобразования БПФ и ДПФ, дискретные синус- и косинус-преобразования; алгоритмы линейной алгебры; алгоритмы цифровой фильтрации и обработки изображений. Становится актуальной задача встраивания алгоритмов CORDIC в архитектуру перспективных вычислительных платформ. Для ускорения вычислений могут быть использованы методы конвейеризации и распараллеливания вычислений.

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

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

Монография состоит из четырех глав.

В главе 1 дается краткий анализ алгоритмов семейства CORDIC и их практических приложений. Алгоритмы, созданные Дж. Вол¬дером и называемые еще «метод „цифра за цифрой“» получили широкое распространение и еще не исчерпали своего потенциала, в связи с возможностями модификации и расширения функциональных возможностей.

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

В главе 3 рассмотрены методы построения разрядно-парал¬лель¬ных вычислительных схем на основе предложений Г. Е. Пухова и модификации алгоритмов семейства CORDIC. Приведена структура геометрического процессорного элемента, интегрирующего разработанные алгоритмы и предлагаемого для включения в состав бортового вычислительного комплекса БПЛА. Рассмотрено решение геометрических задач генерации отрезков пути, поворотов и выполнения видовых операций отсечения в системе команд БВК, опирающихся на алгоритмы CORDIC.

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


Об авторах
Хачумов Вячеслав Михайлович
Доктор технических наук, профессор, главный научный сотрудник Института проблем искусственного интеллекта ФИЦ ИУ РАН, заведующий лабораторией интеллектуального управления ИПС им. А. К. Айламазяна РАН. Действительный член (академик) Российской академии космонавтики имени К. Э. Циолковского. Профессор РУДН, МФТИ и МИРЭА — Российского технологического университета.
Хачумов Михаил Вячеславович
Кандидат физико-математических наук, старший научный сотрудник Института проблем искусственного интеллекта ФИЦ ИУ РАН, старший преподаватель кафедры информационных технологий РУДН.

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