Содержание к диссертации
Введение
1. Обзор алгоритмических методов и технических средств организации решения слау на основе итерационных методов 20
1.1. Итерационные методы решения СЛАУ 20
1.1.1 Общий подход к построению итерационных методов 21
1.1.2 Условия сходимости итерационных методов
1.2. Решение СЛАУ с использованием дельта-преобразований первого порядка.. 23
1.3. Решение СЛАУ с использованием дельта-преобразований второго порядка... 1.3.1. Постановка задачи дельта-преобразования второго порядка 26
1.3.2. Двоичный алгоритм оптимального по быстродействию и точности дельта-преобразования на основе вторых разностей 28
1.3.3. Алгоритмизация параллельного решения СЛАУ с использованием дельта-преобразований второго порядка
1.4. Программируемые логические интегральные схемы и специализированные вычислительные устройства 34
1.5. Основные выводы. Частные исследовательские задачи 40
2. Разработка оптимизированного алгоритма параллельного решения слау с использованием дельта-преобразований первого порядка и переменного кванта 42
2.1. Алгоритм параллельного решения СЛАУ с использованием дельта-преобразований первого порядка и переменного кванта 42
2.2. Исходные положения в решении задачи оптимизации алгоритма 43
2.3. Формирование оптимальных оценок, обеспечивающие минимальную длительность идеализированных итерационных процессов с переменным квантом при отсутствии возмущений 45
2.4. Формирование квазиоптимальных значений параметров для реального вычислительного процесса 47
2.5. Исследование работоспособности решения СЛАУ на основе дельта-преобразований первого порядка и переменного кванта на основе компьютерного моделирования 50
2.6. Основные выводы и результаты 53
3. Разработка оптимизированного алгоритма параллельного решения слау с использованием дельта-преобразований второго порядка и переменного кванта 55
3.1. Алгоритм параллельного решения СЛАУ с использованием дельта-преобразований второго порядка и переменного кванта 55
3.2. Исследование вопросов минимизации по количеству итераций решения СЛАУ с постоянными свободными членами на основе дельта-преобразований второго порядка и переменного кванта
3.2.1. Разработка оценок минимальной длительности идеализированных итерационных процессов с переменным квантом при отсутствии возмущений 57
3.2.2. Формирование условий и параметров для реализации реального вычислительного процесса 59
3.2.2.1. Разработка целочисленных параметров итерационных процессов с переменным квантом 60
3.2.2.2 Формирование условий завершения итерационных процессов в циклах
3.3. Исследование быстродействия решения СЛАУ с использованием дельта преобразований первого и второго порядков с постоянным и переменным квантом
3.4. Исследование работоспособности решения СЛАУ с постоянными свободными членами на основе дельта-преобразований второго порядка с использованием компьютерного моделирования 67
3.5. Исследование решения СЛАУ с переменными свободными членами на основе дельта-преобразований второго порядка и переменного кванта 69
3.6. Исследование работоспособности решения СЛАУ с переменными свободными членами на основе дельта-преобразований первого и второго порядков с переменным квантом с использованием компьютерного моделирования 73
3.7. Основные выводы и результаты 76
4. Исследование возможностей использования алгоритмов параллельного решения слау на основе дельта преобразований первого и второго порядков для специализированного вычислителя 79
4.1. Алгоритмы параллельного решения СЛАУ на основе дельта-преобразований первого и второго порядков, ориентированные для специализированного вычислителя 79
4.1.1. Алгоритм на основе дельта-преобразований первого порядка 79
4.1.2. Алгоритм на основе дельта-преобразований второго порядка 81
4.2. Архитектура специализированных вычислителей для решения СЛАУ на
основе дельта-преобразований первого и второго порядков 83
4.2.1. Архитектура специализированного вычислителя для алгоритма на основе дельта-преобразований первого порядка 84
4.2.2. Архитектура специализированного вычислителя алгоритма для решения СЛАУ на основе дельта-преобразований второго порядка 4.3. Оценки эффективности использования алгоритмов на основе дельта-преобразований первого и второго порядков для специализированного вычислителя 92
4.4. Исследование возможности решения навигационной задачи 4.4.1. Постановка навигационной задачи 97
4.4.2. Особенности алгоритмизации решения навигационной задачи 100
4.4.3. Исследование возможностей использования дельта-преобразований первого и второго порядков для решения СЛАУ в навигационной задаче 102
4.5. Основные выводы и результаты 108
Заключение
Библиографический список 113
- Условия сходимости итерационных методов
- Формирование оптимальных оценок, обеспечивающие минимальную длительность идеализированных итерационных процессов с переменным квантом при отсутствии возмущений
- Разработка оценок минимальной длительности идеализированных итерационных процессов с переменным квантом при отсутствии возмущений
- Архитектура специализированного вычислителя для алгоритма на основе дельта-преобразований первого порядка
Введение к работе
Актуальность темы исследования. На всех этапах развития вычислительной техники уделялось и уделяется в настоящее время большое внимание вопросам проектирования функционирующих в реальном масштабе времени специализированных высокопроизводительных вычислительных систем, позволяющих обеспечивать необходимые показатели по быстродействию в сочетании с минимизированными затратами аппаратных ресурсов и потребляемой энергии.
В качестве отдельных компонент задач, решаемых в рамках создания специализированных вычислительных средств, часто выступают задачи вычислительной математики, в частности, представляемые в виде систем линейных алгебраических уравнений (СЛАУ). Однако известные, в частности, итерационные методы решения СЛАУ при реализации на основе специализированных вычислителей характеризуются значительными затратами аппаратных ресурсов, что связано, в первую очередь, с необходимостью реализации устройств умножения многоразрядных кодов переменных и коэффициентов, пересылками многоразрядных кодов между уравнениями системы при параллельной реализации.
Известны итерационные методы решения СЛАУ, исключающие операцию многоразрядного умножения, базирующиеся на основе дельта-преобразований первого порядка с постоянным и переменным квантом и дельта-преобразований второго порядка с постоянным квантом. Известным недостатком методов с постоянным квантом является очень большое количество итераций. Использование переменного кванта позволяет сократить количество итераций.
Практически во всех работах, посвященных алгоритмической организации итерационного процесса решения СЛАУ с использованием дельта-преобразований первого порядка с переменным квантом отсутствует освещение теоретического обоснования выбора наилучшего соотношения между квантами соседних циклов. Кроме того, предлагаемые алгоритмы характеризуются большой вычислительной трудоемкостью при реализации завершения итерационного процесса, либо момент завершения итераций фиксируется с использованием некоторой константы, значения которой неопределенно, или по количеству итераций, что также представляет собой проблему предварительной оценки или является исходно избыточным по затрачиваемым временным ресурсам.
Известные методы оптимизированных дельта-преобразований второго порядка при использовании постоянного кванта характеризуются по сравнению с дельта-преобразованиями первого порядка возможностью обеспечения более высоких динамических (сокращение количества шагов переходного процесса) и точностных характеристик. Однако в известных публикациях отсутствует рассмотрение вопроса использования переменного кванта для оптимизированных дельта-преобразований второго порядка, а также решения СЛАУ с переменным свободными членами и переменным квантом.
В связи с отмеченным актуальным является рассмотрение вопросов разработки и исследования методов решения СЛАУ на базе дельта-преобразований первого и второго порядков с переменным квантом и реализации этих методов в специализированных вычислительных устройствах.
Цель работы состоит в повышении производительности, уменьшении аппаратных ресурсов и разработке теоретических основ специализированных вычислительных устройств на основе методов и алгоритмов итерационного решения систем линейных алгебраических уравнений с использованием дельта-преобразований.
Объектом исследований являются итерационные методы решения СЛАУ и вычислительные структуры, ориентированные для построения специализированных вычислителей на основе использования теории и алгоритмов дельта-преобразований первого порядка и оптимизированных дельта-преобразований второго порядка.
Научная задача, решаемая в диссертационной работе, - разработка и исследование методов и алгоритмов функционирования специализированных вычислительных устройств на основе итерационного решения СЛАУ с использованием дельта-преобразований первого и второго порядков, исключающих операцию многоразрядного умножения.
Для достижения указанной цели необходимо решить следующие задачи:
-
провести анализ существующих методов и алгоритмов итерационного решения СЛАУ в рамках построения специализированных вычислительных средств;
-
разработать теоретические положения, обосновывающие оптимизированную по быстродействию организацию итерационного процесса решения СЛАУ на базе дельта-преобразований первого и второго порядков и переменного кванта;
-
разработать метод и алгоритм итерационного решения СЛАУ с постоянными и переменными свободными членами на базе оптимизированных дельта-преобразований второго порядка и переменного кванта;
-
на основе разработанных теоретических положений усовершенствовать метод и алгоритм итерационного решения СЛАУ на базе дельта-преобразований первого порядка и переменного кванта;
-
разработать оценки, характеризующие оптимизированную длительность идеализированных итерационных циклов;
-
разработать целочисленные оценки параметров, определяющие способ задания последовательности значений переменных квантов в циклах при реализации реальных вычислительных процессов;
-
разработать способы эффективного завершения итерационных процессов в циклах;
-
выполнить экспериментальные исследования с использованием компьютерного моделирования, подтверждающие достоверность полученных результатов;
-
разработать структурные схемы специализированных устройств, реализующие имеющие специфические особенности алгоритмы решения СЛАУ на базе дельта-преобразований первого и второго порядков;
-
с ориентацией на ПЛИС получить оценки по аппаратным затратам, быстродействию и комплексные сравнительные оценки эффективности реализации разработанных алгоритмов на специализированном вычислителе;
-
определить условия, регламентирующие эффективное использование по быстродействию при решении СЛАУ дельта-преобразований первого порядка с одной стороны и дельта-преобразований второго порядка с другой;
-
провести исследование возможности использования дельта-преобразований первого и второго порядков для решения СЛАУ в бортовой задаче локальной навигации.
Методы исследований. При проведении исследования были использованы: математический аппарат теории оптимизированных дельта-преобразований второго порядка, численные методы решения систем алгебраических уравнений, теория дифференциального исчисления, машинное моделирование на ЭВМ.
Достоверность и обоснованность научных положений, выводов и результатов, сформулированных в диссертационной работе, подтверждается результатами математического анализа на основе теоретических исследований и логическими выводами,
компьютерным моделированием, публикациями, свидетельством о регистрации программы, апробацией работы на международных, всероссийских научно-технических конференциях, школах и семинарах, актами о внедрении.
Научной новизной обладают следующие результаты диссертационной работы:
-
впервые разработанные теоретические положения, обосновывающие приближенное решение вопроса минимизации количества итераций при использовании переменного кванта для дельта-преобразований первого и второго порядков;
-
разработанный метод итерационного решения СЛАУ с постоянными и переменными свободными членами на базе оптимизированных дельта-преобразований второго порядка с переменным квантом преобразования, базирующийся на разработанных теоретических положениях и отличающийся от известных введением переменного кванта в организацию параллельного итерационного процесса без использования устройств умножения многоразрядных кодов в специализированном вычислительном устройстве;
-
впервые теоретически обоснованные целочисленные оценки параметров, определяющие способ задания последовательности значений переменных квантов в циклах итерационного решения СЛАУ и базирующиеся на использовании двух или четырех итераций в каждом цикле для дельта-преобразований первого порядка и четырех или восьми - для дельта-преобразований второго порядка;
-
предложенный способ завершения итераций в циклах при решении СЛАУ на основе дельта-преобразований в специализированном вычислительном устройстве, отличающийся от известных использованием признаков выявления моментов пересечения нулевого уровня функцией невязки и возможностью уменьшения количества выполняемых итераций в циклах и системы в целом;
-
впервые теоретически обоснованные и экспериментально подтвержденные возможности решения СЛАУ с непрерывными переменными свободными членами при использовании оптимизированных дельта-преобразований второго порядка в установившемся процессе за одну итерацию
Положения, выдвигаемые на защиту:
1) возможности решения СЛАУ с непрерывными переменными свободными членами в режиме реального времени при использовании оптимизированных дельта-преобразований второго порядка в установившемся процессе за одну итерацию.
Результаты, выносимые на защиту:
-
итерационный метод решения СЛАУ с постоянными и переменными свободными членами на основе использования оптимизированных дельта-преобразований второго порядка с переменным квантом, базирующийся на разработанных теоретических положениях и отличающийся от известных введением переменного кванта в организацию параллельного итерационного процесса без использования устройств умножения многоразрядных кодов в специализированном вычислительном устройстве, сокращением количества итераций по сравнению с использованием дельта-преобразований второго порядка и постоянного кванта - в десятки раз, сокращением длительности выполнения одной итерации и итерационного процесса в целом по сравнению с реализацией метода простой итерации в ~1,7 раз, сокращением затрат аппаратных ресурсов в ~1,7 раз и благодаря этому в целом повышающий эффективность в ~2,9 раз;
-
впервые разработанные и теоретически обоснованные оптимальные оценки, характеризующие длительность идеализированных итерационных циклов с постоянным квантом определенного значения для дельта-преобразований первого и второго порядков;
-
впервые теоретически обоснованные целочисленные оценки параметров, на основе которых формируются последовательности значений переменных квантов в циклах для дельта-преобразований первого и второго порядков;
-
способ завершения итераций в циклах при решении СЛАУ на основе дельта-преобразований в специализированном вычислительном устройстве, отличающийся от известных использованием признаков выявления моментов пересечения нулевого уровня функцией невязки и возможностью уменьшения количества выполняемых итераций в циклах и системы в целом.
Практическая ценность работы. Решение СЛАУ с постоянными свободными членами на базе дельта-преобразований первого порядка и переменного кванта обеспечивает возможность сокращения по сравнению с использованием метода простой итерации длительности выполнения одной итерации и итерационного процесса в целом в ~2,5 раз, затрат аппаратных ресурсов в ~2,7 раз и благодаря этому в целом повышения эффективности в ~6,7 раз при реализации в специализированном вычислительном устройстве.
Представляются возможности решения СЛАУ с переменными свободными членами при переменном кванте с использованием дельта-преобразований второго порядка в установившемся процессе на основе одной итерации с временным шагом в десятки раз большим по сравнению с использованием дельта-преобразований первого порядка.
Решение СЛАУ с переменными свободными членами на базе оптимизированных дельта-преобразований второго порядка и переменного кванта обеспечивает возможность сокращения по сравнению с использованием метода простой итерации длительности выполнения одной итерации и итерационного процесса в целом в ~1,7 раз, затрат аппаратных ресурсов в ~1,7 раз и благодаря этому в целом повышения эффективности в ~2,9 раз при реализации в специализированном вычислительном устройстве.
В решении задачи локальной навигации: определения координат летательного аппарата (ЛА) использование оптимизированных дельта-преобразований второго порядка и переменного кванта обеспечивает возможность решения СЛАУ с переменными свободными членами на каждом временном шаге установившегося процесса за одну итерацию. Полученные результаты экспериментов с использованием компьютерного моделирования подтверждают при достаточно большой удаленности начала установившегося процесса от начала координат возможности оперирования с практически значимыми временными шагами работы системы.
Реализация результатов работы. Результаты диссертации использованы при выполнении следующих научно-исследовательских работ:
проект № 213.01-24/2013-102 «Разработка теоретических и методологических основ создания и применения информационно-алгоритмического и программного обеспечения интегрированных систем цифрового управления и автономной высокоточной навигации по искусственным навигационным полям для перспективных гиперзвуковых летательных аппаратов». Финансирование - за счет федерального бюджета в рамках базовой части Государственного задания Минобрнауки РФ, 2013 г., № ГР 01201368261;
проект №213.01-11/2014-86 «Информационно-алгоритмическое обеспечение систем цифрового управления, автономной высокоточной навигации и технического зрения для перспективных летательных аппаратов: разработка теоретических основ проектирования, алгоритмов, способов эффективной и надежной программной реализации, использование высокопроизводительной вычислительной инфраструктуры для
экспериментального моделирования». Финансирование - за счет федерального бюджета в рамках базовой части Государственного задания Минобрнауки РФ, 2014 - 2015 гг.,№ГР 114110640027.
Результаты диссертации использованы на предприятии АО «Центральный научно-исследовательский институт автоматики и гидравлики» в решении навигационной задачи; в учебном процессе на кафедре математического обеспечения и применения ЭВМ Института компьютерных технологий и информационной безопасности Южного федерального университета.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях, школах, семинарах: Всероссийской научной школе - семинаре молодых ученых, аспирантов и студентов «Семантические технологии - 2013. Семантическая интерпретация и интеллектуальная обработка данных и ее приложение в информационном поиске», Таганрог, 2013 г.; Конгрессе по интеллектуальным системам и информационным технологиям "IS&IT'13", п. Дивноморское, 2013 г.; Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, Таганрог, 2014 г.; Научной конференции «Современные информационные технологии: тенденции и перспективы развития», Южный федеральный университет, г. Ростов-на-Дону, 2014, 2015 гг.; конференции IEEE International Conference on Engineering and Telecommunication (EnT 2014), Долгопрудный, Москва, 2014 г.; Международной научно-практической конференции «Фундаментальные и прикладные исследования в современном мире», Санкт-Петербург, 2014 г.; Всероссийской научно-технической конференции "Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности", Таганрог, 2015 г..
Публикации. Результаты диссертации отражены в 15 печатных работах: из них 5 статей, среди которых 3 в изданиях, входящих в перечень ВАК РФ и 2 в изданиях, входящих в реферативную базу SCOPUS, 1 свидетельство об официальной регистрации программы для ЭВМ, а также тезисы и материалы 9 докладов на всероссийских и международных научно-технических конференциях, школах, семинарах. Общий объем публикаций составляет 83 печатных страницы (личный вклад автора 55 п. с). Результаты работы отражены в 2 отчетах о НИР.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка, включающего 65 наименований и приложения. Основной текст работы изложен на 120 страницах машинописного текста, поясняется 11 рисунками и 7 таблицами.
Диссертация соответствует п. 1 и п. 3 («Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления», «Разработка принципиально новых методов анализа и синтеза элементов и устройств вычислительной техники и систем управления с целью улучшения их технических характеристик») паспорта специальности 05.13.05 «Элементы и устройства систем управления и вычислительной техники», технические науки.
Условия сходимости итерационных методов
В современной литературе описано большое количество итерационных методов, основанных на различных принципах. Однако каждый итерационный процесс имеет свою ограниченную область применимости, так как, во-первых, процесс итераций может оказаться расходящимся для данной системы и, во вторых, сходимость процесса может быть настолько медленной, что практически оказывается невозможным достигнуть удовлетворительной близости к решению [48].
Если итерационный процесс метода простой итерации сходится, то он сходится к решению системы.
Для сходимости итерационного процесса метода простой итерации при любом начальном векторе Y0 необходимо и достаточно, чтобы все собственные значения матрицы А были бы по модулю меньше единицы [35, 48]. Однако условия теоремы 1 трудно проверяемы, в связи с этим судить о сходимости процесса последовательных приближений лучше при помощи достаточных признаков, связанных непосредственно с элементами матрицы А. Теорема 2. Для того, чтобы итерационный процесе метода простой итерации сходился, достаточно, чтобы какая-либо норма матрицы А была меньше 1 [1,5, 48].
Метод простой итерации может быть применен к матрицам специального вида [9, 50]. Так если матрица В является симметричной и положительно определенной, тогда итерационный процесс метода простой итерации будет сходиться для системы (1.1). В силу положительной определенности собственные значения матрицы В положительны.
Итерационные методы решения СЛАУ, удовлетворяющие рассмотренным в разделе 1.1.2 условиям сходимости, при реализации на основе специализированных вычислителей характеризуются значительными затратами аппаратных ресурсов, что связано, в первую очередь, с необходимостью реализации устройств умножения многоразрядных кодов переменных и коэффициентов.
Известны итерационные методы решения СЛАУ, исключающие операцию умножения, базирующиеся на основе дельта-преобразований первого порядка.
Сущность методов решения СЛАУ на основе дельта-преобразований первого порядка с постоянным квантом заключается в представлении решаемой задачи в виде системы разностных уравнений первого порядка; формирование переменных осуществляется на основе постоянных по модулю (2 % s є N) и отличающихся по знаку значений первых разностей (квантов преобразования), а операция умножения заменяется на операцию, основными компонентами которой является умножение на ±1.
Впервые данные методы были представлены в работах [13, 45-46]. Их применение позволяло создавать сравнительно простые и высокопроизводительные проблемно-ориентированные устройства за счет избавления от операции многоразрядного умножения. Однако известным недостатком методов с постоянным квантом являлось очень большое количество итераций.
В то же время появляется в работах [26, 47] использование дельта-преобразований первого порядка и переменного кванта для решения СЛАУ. Предлагаемые методы в [26, 47] организации вычислительного процесса с переменным квантом носят эвристический переборный характер и отсутствуют теоретические обоснования, что приводит к сужению возможности реализации этого метода. В работе [26] практически отсутствует анализ, характеризирующий точность решения и длительность итерационного процесса. В работе [47] предлагаемый алгоритм характеризуется большой вычислительной трудоемкостью при реализации завершения итерационного процесса, что связано с необходимостью выполнения на каждой итерации возведения в квадрат невязок по всем уравнениям, их суммирования и выделения наименьшего из текущих по итерациям значений суммы. Возведение в квадрат невязок связано с необходимостью использования многоразрядных устройств умножения, что противоречит исходной цели - реализация специализированных вычислительных устройств решения СЛАУ с возможным исключением устройств такого рода.
В работе [15] предложен метод решении СЛАУ на базе дельта-преобразований первого порядка с переменным квантом, в котором для определения текущего значения веса кванта при организации вычислений с переменным квантом получены оптимизированные соотношения. Однако освещение эффективной возможности алгоритмической организации вычислительного процесса является неполным, предложен только один вариант из нескольких возможных. В работе [15] отсутствует теоретическое обоснование наилучшего соотношения между квантами соседних циклов. В данной работе не решена проблема эффективного завершения итерационного процесса, однако представлены предельные оценки длительности итерационного процесса.
В работах [6-7] проведено экспериментальное исследование методов, рассмотренных в работах [26, 47] и рассмотрены вопросы их практического применения. В работах [6-7] присутствуют недостатки, отмеченные в работах [26, 47]. Кроме того, в качестве основной рекомендации по вопросу выбора наилучшего соотношения между квантами соседних циклов в работах [6-7] 2009-2010 г. предлагается вариант, представленный в работе [15] 1983 г., однако в то же время отсутствует ссылка на данную работу.
В представленных выше работах не рассматривается вопрос использования дельта-преобразований второго порядка, которые имеют существенно другой характер переходных (итерационных) процессов, и при постоянном кванте преобразования позволяют в сотни раз сократить количество итераций решения СЛАУ по сравнению с использованием дельта-преобразований первого порядка [22]. 1.3.Решение СЛАУ с использованием дельта-преобразований второго порядка
Впервые в работах [22, 59] был представлен разработанный высокопроизводительный оптимизированный по скорости протекания переходного процесса и точности алгоритм разностных преобразований второго порядка. Особенностью данного алгоритма является то, что формирование переменных осуществляется на основе постоянных по модулю квантов вторых разностей, принимающих положительные или отрицательные значения [59].
Как и при использовании дельта-преобразований первого порядка, обеспечивается возможность исключения операций многоразрядного умножения и упрощения обмена информацией в параллельных системах. В то же время существенно возрастает скорость протекания вычислительных процессов при той же погрешности (или повышается точность при одинаковой скорости решения) [59].
Формирование оптимальных оценок, обеспечивающие минимальную длительность идеализированных итерационных процессов с переменным квантом при отсутствии возмущений
Известные итерационные методы решения СЛАУ на базе дельта-преобразований первого порядка и переменного кванта позволяют сократить количество итераций по отношению к использованию постоянного кванта. Однако известные методы с переменным квантом требуют теоретически обоснованного охватывающего приближенное решение вопросов минимизации количества итераций и получения оптимизированных оценок, характеризующих длительности итерационных циклов с постоянным квантом определенного значения. Для реализации реальных процессов необходимо разработать теоретические оценки параметров, определяющих способ задания последовательности значений переменных квантов преобразования в циклах.
Итерационное решение СЛАУ на базе дельта-преобразований второго порядка представляет возможности сокращения количества итераций по отношению к использованию дельта-преобразований первого порядка при постоянном кванте. Интерес представляет исследование возможности использования оптимизированных дельта-преобразований второго порядка в сочетании с переменным квантом и постоянными свободными членами: решение вопросов минимизации по количеству итераций, длительности выполнения итераций и необходимых аппаратных ресурсов. Рассмотрение возможности эффективного решения (по быстродействию и аппаратным ресурсам) СЛАУ с переменными свободными членами на основе использования дельта-преобразований второго порядка с переменными квантом в установившемся итерационном процессе требует теоретического исследования.
Для формирования момента завершения реальных итерационных процессов на основе дельта-преобразований в циклах требуется разработка эффективных по обеспечению своевременного завершения итераций, простых в реализации и не требующих численной оценки с использованием специальных исходных данных алгоритмов.
Обоснование эффективности практического использования алгоритмов параллельного решения СЛАУ на основе дельта-преобразований первого и второго порядков с переменным квантом для реализации специализированного вычислителя требуется выполнение комплексных исследований, охватывающих разработку оценок по быстродействию и аппаратным ресурсами.
Алгоритм параллельного решения СЛАУ с использованием дельта-преобразований первого порядка и переменного кванта
Алгоритм параллельного решения системы (1.12) с постоянными свободными членами с использованием дельта-преобразования первого порядка и переменного кванта представим в следующей разностной форме для / - го шага при начальных условиях Г01 =0, zr01 = -Д., г = 1,п, [18, 29, 34, 58, 61]:
В алгоритме (2.1) с, - вес модуля кванта преобразования на /- ом цикле (сг 0), Р - количество итерационных циклов, выполняемых при постоянных по модулю значениях квантов, Rt - количество итераций в цикле. Кроме того, для стыков участков соседних циклов справедливы соотношения: Yr0l = YrR(l ;
Требуется найти условия оптимизированного выбора количества циклов и значений квантов в циклах, позволяющие оптимизировать по количеству итерации характеризующийся сходимостью итерационный процесс решения СЛАУ. уравнения модуль zr(il)l будет уменьшаться, т.е. становится \znl\ величину cl . Невязка zr(il)l, / = 1,2,...,i уменьшается, причем её уменьшающееся значение с ростом / обязательно проходит через уровень значения нуль, в частности, меняя знак. При этом количество шагов (итераций) в данных условиях до вхождения в нуль для /=1 будет составлять (предполагаем пока - не целое
Момент прохождения значения невязки через нуль будем рассматривать как переход на следующий итерационный цикл. Для данных условий можно записать причем sign(zr02) = -sign(zr01) или zr02 = 0. Далее соотношение zr02 = 0 будем учитывать только в условиях завершения итерации. Соответственно для /-го, 1 = \,2,...,Р значения Rt можно записать:
При выполнении реального сходящегося итерационного процесса вероятность значения Vyn7 = О мала и в данном рассмотрении необходимо учитывать Vy„7 Ф О. Если sign(Vynl) = sign(zr(._1);), т. е. zm = Zr(,-,)! - CiSigliz - y sigriz И zm = zrwi (ci + Yyrt;).«gy (,-i)/), то скорость уменьшения невязки увеличивается (уменьшается количество итераций в цикле) благодаря соответствующему уменьшению невязки на каждом шаге на величину, превышающую квант в выражении (с + Vyn7). Если sign(Vynl) = -sigriz ), т. е. zm = z«i-m - ( c i - 1 7 (,-1)/) то скорость уменьшения невязки уменьшается (увеличивается количество итераций в цикле) благодаря соответствующему уменьшению невязки на каждом шаге на величину меньшую, чем квант в выражении (с -Vyn7); при этом условием уменьшения невязки является с] Уул7. В связи с этим можно сделать следующие заключения:
При реализации сходящегося вычислительного процесса значение невязки в конце цикла меняет знак (или равно нулю) [18, 28-29, 34, 57, 60-61], т.е. si&izm) = -si& zHR-lv), (2.4) / = 1,2,.. .,Р,г = й. Обобщая изложенное выше, для СЛАУ (значение нормы удовлетворяет условиям сходимости, представленным в главе 1.1.2) проведение обоснования условий завершений итерационного вычислительного процесса с переменным квантом дельта-преобразования первого порядка основывается:
В качестве основного расчетного соотношения количества итераций в идеализированном цикле принимаем (2.2).
В рамках формирования момента завершения итерационного процесса в / -ом цикле принимаем условие (2.4), соответствующее моменту (номеру шага), к которому по всем уравнениям СЛАУ сформированы в этом цикле признаки изменения знака невязки, то есть завершения итерационного процесса[18, 28-29, 34, 58, 60-61].
Формирование оптимальных оценок, обеспечивающие минимальную длительность идеализированных итерационных процессов с переменным квантом при отсутствии возмущений
Будем искать оценку теоретического минимального количества итераций идеализированного процесса (количество шагов дельта-преобразования отработки начальных невязок при Vyn7 = 0). Количество итераций (длительность переходного процесса) Мидеализированного решения СЛАУ представим в виде:
Разработка оценок минимальной длительности идеализированных итерационных процессов с переменным квантом при отсутствии возмущений
Из равенства правых частей (3.11), (3.12) следует равенство левых частей: е2р =(0.5-R)2p, откуда для оптимального значения R получаем: R = 2e = 5,44-Таким образом, при У2уп1 = 0 минимальное количество итераций идеализированного процесса в цикле, в котором остается неизменным значение кванта преобразования, по существу не зависит от начального значения невязки \zm и веса минимального кванта ср, а является константой, равной удвоенному числу Эйлера.
Полученное соотношение (3.10), характеризующее длительность М идеализированного переходного процесса для дельта-преобразований второго порядка при постоянных свободных членах СЛАУ и переменном кванте, оказывается идентичным соотношению для оценки количества итераций при использовании дельта-преобразований первого порядка, полученных в разделе 2.3 и работах [18, 29, 58, 61]. Возможности эффективного использования дельта-преобразований второго порядка при постоянных квантах и постоянных свободных членах СЛАУ, а также при переменных квантах и переменных свободных членах рассмотрены в работе [22] и разделе 1.3.
Формирование условий и параметров для реализации реального вычислительного процесса В реальном вычислительном процессе при выполнении условий сходимости по значению нормы и использовании дельта-преобразований второго порядка процесс уменьшения невязки сохраняется, так как в ходе выполнения переходного процесса постоянно действуют ограниченные по модулю допустимые возмущающие воздействия -— LL _z_ 5 Где - для дельта-преобразований второго порядка характеризует максимальный уровень действующих допустимых возмущающих воздействий [22]. При этом для соответствующей ограниченной нормы СЛАУ можно записать [19, 22]: /
В зависимости от знака величины V2_yn/ реальная скорость уменьшения невязки увеличивается или уменьшается. Количество итераций при этом может увеличиться или уменьшиться относительно приближенной оценки (3.2). В рамках решения данной задачи, связанной с организацией решения СЛАУ при V уп1 Ф О, необходимо определить целочисленное количество циклов и связанные с этим количеством параметры, устанавливающие связь значений квантов преобразования между соседними циклами. Кроме того, необходимо сформулировать условия завершения итераций в циклах.
Сущность реализации итерационного процесса решения СЛАУ без использования операции умножения при использовании дельта-преобразований первого порядка рассмотрена в разделе 2.4. Использование дельта-преобразований второго порядка основывается на таких же принципах работы. Также в качестве целых значений Rmt целесообразно принять числа, наиболее близкие к оптимальной оценке R = 2е, то есть ЯЫ1 = 4 и ЯЫ2 = 8.
С целью упрощения и универсализации алгоритма (3.1) представляется целесообразным создание универсальных шаблонов, задающих количество циклов и итераций в циклах. В качестве одного из вариантов такого шаблона примем расчет для ) =1, и, например, с =214 Небольшие отклонения значений zm Ф1 по уравнениям СЛАУ могут приводить к изменению количества итераций в первом цикле, что в целом может не оказывать существенное влияние на общее количество итераций. Кроме того, при необходимости в процессе реализации последнего цикла возможно варьирование в небольших пределах значением ср, что также в целом может не оказывать существенное влияние на общее количество итераций.
Признаком окончания итерационного процесса в текущем цикле и перехода на следующий цикл по всей СЛАУ является выполнение (не обязательно одновременное) условия (3.22) по всем уравнениям. Вычислительные процессы в цикле должны продолжаться до тех пор, пока не сформируется указанный выше признак по всем уравнениям.
Учитывая приведенные в разделе 1.3 рекомендации по оптимизации процессов на основе дельта-преобразований второго порядка, целесообразно использовать [19]: с, = 0.75с и (lV ;"7l») 0.25. (3.23) Следует отметить, что разработанные методология и алгоритмы успешно функционировали и при решении СЛАУ, имеющих норму большую, чем принято выше, но при обязательном выполнении условий сходимости, описанных в разделе 1.1.2. С целью расширения указанных возможностей введены и экспериментально подтверждены дополнительные условия завершения итерационного процесса в цикле [19]: sign( ) = -sign( ). (3.24)
Сущность данного эвристического условия (3.24) состоит в выявлении момента пересечения невязкой оси ординат и предлагается для одновременной реализации с условием (3.22). При этом представляются возможности выявления пересечения оси ординат и в случае, когда пересечение имеет место, но при повышенной норме не соответствует условию (3.22).
На основании полученных теоретических оценок и представленных графиков на рисунках 3.2, 3.3, 3.4 показано сокращение общей длительности итерационного процесса решения СЛАУ приблизительно в сотни раз при использовании дельта-преобразований второго порядка и постоянного кванта по отношению к использованию дельта-преобразований первого порядка и постоянного кванта; сокращение в тысячи раз - при использовании дельта-преобразований первого порядка и постоянного кванта по отношению к использованию дельта-преобразований первого и второго порядков и переменного кванта; сокращение в десятки раз - при использовании дельта преобразований второго порядка и постоянного кванта по отношению к использованию дельта-преобразований первого и второго порядков и переменного кванта. Причем данные сравнительные оценки с уменьшением веса минимального кванта преобразования с резко увеличиваются.
Архитектура специализированного вычислителя для алгоритма на основе дельта-преобразований первого порядка
Комплексную эффективность реализации алгоритмов дельта-преобразования первого и второго порядков с переменным квантом по сравнению с использованием метода простой итерации на специализированном вычислителе можно рассматривать в виде взаимосвязанной совокупности сравнительных оценок по быстродействию и аппаратным затратам. Учитывая, как показано в разделах 2.5 и 3.3, что количество итераций при использовании дельта-преобразований первого и второго порядка и переменного кванта, может быть большим или меньшим по сравнению с простой итерацией, при исследовании это количество принято одинаковым для исследуемых методов.
Можно рассматривать реализацию структурных схем устройств, представленных на рисунках 4.1 и 4.2, с использованием ПЛИС, в частности, типа FPGA. Ресурсные характеристики реализации основных арифметических операций при их аппаратном исполнении существенно неравнозначны. Особенно высокие аппаратные затраты, выражаемые в логических ячейках, требуются для множительных устройств. Операцию умножения будем рассматривать как выполнение умножения с использованием однотактных аппаратных схем параллельной реализации, а также при расширении разрядной сетки сомножителей - экономичные параллельно-последовательные реализации путем выполнения умножения за несколько тактов по алгоритму «сдвиг с накоплением». Наиболее просто реализуется структура простого матричного суммирования, которая формирует параллельный умножитель как массив одноразрядных соединенных локальными меж соединениями сумматоров [38]. Данная схема наиболее эффективна на операндах небольшой разрядности (4 и менее), где параллельный умножитель 4x4 требует для своей реализации 12 сумматоров. При дальнейшем наращивании разрядности матрица одноразрядных сумматоров значительно разрастается, одновременно увеличивается критический путь распространения сигнала переноса, соответственно ограничивается быстродействие, и реализация умножителя становится малорациональной. Таким образом, в данной работе умножители большей разрядности рассматривались как комбинация умножителей 4x4 [38].
Формирование относительных оценок по аппаратным затратам базировалось на учете количества задействованных логических вентилей [24], [39]. В соответствии с алгоритмами (4.1), (4.2) и структурными схемами на рисунках 4.1, 4.2, решение уравнений выполняется параллельно. Также параллельно реализуются решения уравнений и по методу простой итерации.
Пусть Q - оценка, характеризующая аппаратные затраты алгоритма, Qd_pX оценка для алгоритма (4.1), основанного на дельта-преобразованиях первого порядка и переменного кванта, Qdp2- оценка для алгоритма (4.2), основанного на дельта-преобразованиях второго порядка и переменного кванта, Qpr - оценка для метода простой итерации. Для сравнительной аппаратной оценки вводим
Анализ полученных оценок показал, что использование алгоритма, основанного на дельта-преобразованиях первого порядка и переменного кванта, при решении СЛАУ порядка п=Ъ имеет преимущество по аппаратным затратам в -2,7 раз, основанного на дельта-преобразованиях второго порядка и переменного кванта —1,7 раз при оперировании с 32-разрядными данными по сравнению с методом простой итерации, а с увеличением порядка системы п эффективность увеличивается. дельта-преобразование второго порядка
Анализ полученных оценок показал, что использование алгоритма, основанного на дельта-преобразованиях первого порядка и переменного кванта, при решении СЛАУ порядка п=Ъ имеет преимущество по быстродействию в -2,5 раза, основанного на дельта-преобразованиях второго порядка и переменного кванта —1,7 раз при оперировании с 32-разрядными данными по сравнению с использованием метода простой итерации, причем с увеличением порядка системы п имеет место увеличение данной эффективности.
Сравнительная комплексная оценка эффективности реализации алгоритмов на основе дельта-преобразований первого и второго порядков и переменного кванта была сформирована как произведение полученных выше относительных оценок по аппаратным затратам и быстродействию системы:
В соответствии с (4.4) были получены сравнительные комплексные оценки эффективности. На основании данных результатов был построен график зависимости относительных комплексных оценок эффективности El 2 от порядка СЛАУ п и представлен на рисунке 4.5.
В соответствии с данной оценкой Е12 алгоритм, основанный на дельта-преобразованиях первого порядка и переменного кванта, при решении СЛАУ порядка п=Ъ имеет преимущество при оперировании с 32-разрядными данными в 6,7 раз, основанный на дельта-преобразованиях второго порядка и переменного кванта - -2,9 раз по сравнению с использованием метода простой итерации, причем эта оценка с увеличением порядка системы п резко увеличивается.
В главах 3.4, 3.5 показана целесообразность использования дельта-преобразований второго порядка и переменного кванта при решении СЛАУ с непрерывными переменными свободными членами с получением результата за одну итерацию. На основании представленной на рисунке 4.2 структурной схемы устройства и полученных оценок по быстродействию решение СЛАУ на базе дельта-преобразований второго порядка и переменного кванта в установившемся процессе за одну итерацию осуществляется примерно за 5 тактов при параллельной реализации алгоритмической последовательности действий для всех уравнений системы.
Одна из задач определения местоположения летательного аппарата (ЛА) базируется на использовании нескольких разнесенных в пространстве маяков, расположенных на относительно близком расстоянии от начала локальной системы координат. Бортовой вычислитель получает значения дальностей от ЛА до маяков. На основании имеющихся координат маяков и полученных дальностей можно сформировать навигационные определения в стандартном для дальномерных навигационных систем виде [54]: (х-х +іу-у,)2+(2-2 = , (4.5) где x,y,z- координаты ЛА; хи уи zt - координаты /-го маяка в выбранной системе координат; Д - дальность до /-го маяка. Решение системы уравнений для всех маяков позволяет определить местоположения ЛА (х, у, z) в пространстве.