Разработка и исследование высокопроизводительных методов и алгоритмов итерационного решения систем линейных алгебраических уравнений на основе дельта-преобразований в специализированных вычислительных устройствах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Пирская, Любовь Владимировна

• Пирская, Любовь Владимировна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Пирская, Любовь Владимировна

СОДЕРЖАНИЕ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ВВЕДЕНИЕ

1. ОБЗОР АЛГОРИТМИЧЕСКИХ МЕТОДОВ И ТЕХНИЧЕСКИХ СРЕДСТВ ОРГАНИЗАЦИИ РЕШЕНИЯ СЛАУ НА ОСНОВЕ ИТЕРАЦИОННЫХ

МЕТОДОВ

1.1. Итерационные методы решения СЛАУ

1.1.1 Общий подход к построению итерационных методов

1.1.2 Условия сходимости итерационных методов

1.2. Решение СЛАУ с использованием дельта-преобразований первого порядка

1.3. Решение СЛАУ с использованием дельта-преобразований второго порядка

1.3.1. Постановка задачи дельта-преобразования второго порядка

1.3.2. Двоичный алгоритм оптимального по быстродействию и точности дельта-преобразования на основе вторых разностей

1.3.3. Алгоритмизация параллельного решения СЛАУ с использованием дельта-преобразований второго порядка

1.4. Программируемые логические интегральные схемы и специализированные вычислительные устройства

1.5. Основные выводы. Частные исследовательские задачи

2. РАЗРАБОТКА ОПТИМИЗИРОВАННОГО АЛГОРИТМА ПАРАЛЛЕЛЬНОГО РЕШЕНИЯ СЛАУ С ИСПОЛЬЗОВАНИЕМ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ПЕРВОГО ПОРЯДКА И ПЕРЕМЕННОГО КВАНТА

2.1. Алгоритм параллельного решения СЛАУ с использованием дельта-преобразований первого порядка и переменного кванта

2.2. Исходные положения в решении задачи оптимизации алгоритма

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

при отсутствии возмущений

2.4. Формирование квазиоптимальных значений параметров для реального вычислительного процесса

2.5. Исследование работоспособности решения СЛАУ на основе дельта-преобразований первого порядка и переменного кванта на основе компьютерного моделирования

2.6. Основные выводы и результаты

3. РАЗРАБОТКА ОПТИМИЗИРОВАННОГО АЛГОРИТМА ПАРАЛЛЕЛЬНОГО РЕШЕНИЯ СЛАУ С ИСПОЛЬЗОВАНИЕМ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ВТОРОГО ПОРЯДКА И ПЕРЕМЕННОГО КВАНТА

3.1. Алгоритм параллельного решения СЛАУ с использованием дельта-преобразований второго порядка и переменного кванта

3.2. Исследование вопросов минимизации по количеству итераций решения СЛАУ с постоянными свободными членами на основе дельта-преобразований второго порядка и переменного кванта

3.2.1. Разработка оценок минимальной длительности идеализированных итерационных процессов с переменным квантом при отсутствии возмущений

3.2.2. Формирование условий и параметров для реализации реального вычислительного процесса

3.2.2.1. Разработка целочисленных параметров итерационных процессов с

переменным квантом

3.2.2.2 Формирование условий завершения итерационных процессов в циклах

3.3. Исследование быстродействия решения СЛАУ с использованием дельта-преобразований первого и второго порядков с постоянным и переменным квантом

3.4. Исследование работоспособности решения СЛАУ с постоянными свободными членами на основе дельта-преобразований второго порядка с использованием компьютерного моделирования

3.5. Исследование решения СЛАУ с переменными свободными членами на

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

3.6. Исследование работоспособности решения СЛАУ с переменными свободными членами на основе дельта-преобразований первого и второго порядков с переменным квантом с использованием компьютерного моделирования

3.7. Основные выводы и результаты

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

4.1. Алгоритмы параллельного решения СЛАУ на основе дельта-преобразований первого и второго порядков, ориентированные для специализированного вычислителя

4.1.1. Алгоритм на основе дельта-преобразований первого порядка

4.1.2. Алгоритм на основе дельта-преобразований второго порядка

4.2. Архитектура специализированных вычислителей для решения СЛАУ на основе дельта-преобразований первого и второго порядков

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

4.2.2. Архитектура специализированного вычислителя алгоритма для решения СЛАУ на основе дельта-преобразований второго порядка

4.3. Оценки эффективности использования алгоритмов на основе дельта-преобразований первого и второго порядков для специализированного вычислителя

4.4. Исследование возможности решения навигационной задачи

4.4.1. Постановка навигационной задачи

4.4.2. Особенности алгоритмизации решения навигационной задачи

4.4.3. Исследование возможностей использования дельта-преобразований первого и второго порядков для решения СЛАУ в навигационной задаче

4.5. Основные выводы и результаты

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЕ

ОБ ОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ASIC - application specific integrated circuit

FPGA - field-programmable gate array (программируемая пользователем

вентильная матрица)

SoC - system on chip

БИС - большая интегральная схема

JIA - летательный аппарат

ЛЭ - логический элемент

ПЗУ — постоянное запоминающее устройство

ПЛИС - программируемая логическая интегральная схема

СБИС - сверхбольшая интегральная схема

СЛАУ - система линейных алгебраических уравнений

СнК - система на кристалле

ЦОС - цифровая обработка сигналов

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

ВВЕДЕНИЕ

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

В качестве отдельных компонент задач, решаемых в рамках создания специализированных вычислительных средств, часто выступают задачи вычислительной математики, в частности, представляемые в виде систем линейных алгебраических уравнений (СЛАУ). Однако известные, в частности, итерационные методы решения СЛАУ [4-5, 57, 63] при реализации на основе специализированных вычислителей характеризуются значительными затратами аппаратных ресурсов, что связано, в первую очередь, с необходимостью реализации устройств умножения многоразрядных кодов переменных и коэффициентов, пересылками многоразрядных кодов между уравнениями системы при параллельной реализации.

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

Известны итерационные методы решения СЛАУ, исключающие операцию многоразрядного умножения, базирующиеся на основе дельта-преобразований первого порядка с постоянным и переменным квантом и дельта-преобразований второго порядка с постоянным квантом [6-7, 13, 15, 22, 26, 45-47, 59-60]. Известным недостатком методов с постоянным квантом является очень большое

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

Практически во всех работах, посвященных алгоритмической организации итерационного процесса решения СЛАУ с использованием дельта-преобразований первого порядка с переменным квантом отсутствует освещение теоретического обоснования выбора наилучшего соотношения между квантами соседних циклов; способы задания этих соотношений с одной стороны вводятся эвристически, а с другой полно не охватывают представляющих теоретический и практический интерес соотношений [6-7, 13, 15, 26, 45-47, 60].

Кроме того, необходимо отметить также следующие замечания. В работах [6-7, 26, 45-47] предлагаемые алгоритмы характеризуются большой вычислительной трудоемкостью при реализации завершения итерационного процесса, что связано с необходимостью выполнения на каждой итерации возведения в квадрат невязок по всем уравнениям, их суммирования и выделения наименьших из текущих по итерациям значений суммы. Возведение в квадрат невязок связано с необходимостью использования многоразрядных устройств умножения, что противоречит исходной цели - реализации специализированных вычислительных устройств решения СЛАУ с возможным исключением устройств такого рода. Момент завершения итераций фиксируется с использованием некоторой константы, значения которой неопределенно, или по количеству итераций, что также представляет собой проблему предварительной оценки или является исходно избыточным по затрачиваемым временным ресурсам.

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

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

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

Известные методы оптимизированных дельта-преобразований второго порядка, представленные в работах [22, 59], при использовании постоянного кванта характеризуются по сравнению с дельта-преобразованиями первого порядка возможностью обеспечения более высоких динамических (сокращение количества шагов переходного процесса) и точностных характеристик. Однако в известных публикациях отсутствует рассмотрение вопроса использования переменного кванта для оптимизированных дельта-преобразований второго порядка, а также решения СЛАУ с переменным свободными членами и переменным квантом.

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

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

Объектом исследований являются итерационные методы решения СЛАУ и вычислительные структуры, ориентированные для построения

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

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

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

1) проведен анализ существующих методов и алгоритмов итерационного решения СЛАУ в рамках построения специализированных вычислительных средств;

2) разработаны теоретические положения, обосновывающие оптимизированную по быстродействию организацию итерационного процесса решения СЛАУ на базе дельта-преобразований первого и второго порядков и переменного кванта;

3) разработан метод и алгоритм итерационного решения СЛАУ с постоянными и переменными свободными членами на базе оптимизированных дельта-преобразований второго порядка и переменного кванта;

4) на основе разработанных теоретических положений усовершенствован метод и алгоритм итерационного решения СЛАУ на базе дельта-преобразований первого порядка и переменного кванта;

5) сформулированы оценки, характеризующие оптимизированную длительность идеализированных итерационных циклов;

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

7) предложены способы эффективного завершения итерационных процессов в циклах;

8) выполнены экспериментальные исследования с использованием

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

9) разработаны структурные схемы специализированных устройств, реализующие имеющие специфические особенности алгоритмы решения СЛАУ на базе дельта-преобразований первого и второго порядков;

10) с ориентацией на ПЛИС получены оценки по аппаратным затратам, быстродействию и комплексные сравнительные оценки эффективности реализации разработанных алгоритмов на специализированном вычислителе;

11) определены условия, регламентирующие эффективное использование по быстродействию при решении СЛАУ дельта-преобразований первого порядка с одной стороны и дельта-преобразований второго порядка с другой;

12) проведено исследование возможности использования дельта-преобразований первого и второго порядков для решения СЛАУ в бортовой задаче локальной навигации.

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

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

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

1) впервые разработанные теоретические положения, обосновывающие

приближенное решение вопроса минимизации количества итераций при использовании переменного кванта для дельта-преобразований первого и второго порядков;

2) разработанный метод итерационного решения СЛАУ с постоянными и переменными свободными членами на базе оптимизированных дельта-преобразований второго порядка с переменным квантом преобразования, базирующийся на разработанных теоретических положениях и отличающийся от известных введением переменного кванта в организацию параллельного итерационного процесса без использования устройств умножения многоразрядных кодов в специализированном вычислительном устройстве;

3) впервые теоретически обоснованные целочисленные оценки параметров, определяющие способ задания последовательности значений переменных квантов в циклах итерационного решения СЛАУ и базирующиеся на использовании двух или четырех итераций в каждом цикле для дельта-преобразований первого порядка и четырех или восьми - для дельта-преобразований второго порядка;

4) предложенный способ завершения итераций в циклах при решении СЛАУ на основе дельта-преобразований в специализированном вычислительном устройстве, отличающийся от известных использованием признаков выявления моментов пересечения нулевого уровня функцией невязки и возможностью уменьшения количества выполняемых итераций в циклах и системы в целом;

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

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

использованием метода простой итерации длительности выполнения одной итерации и итерационного процесса в целом в -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.

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

возможности решения СЛАУ с непрерывными переменными свободными членами в режиме реального времени при использовании оптимизированных дельта-преобразований второго порядка в установившемся процессе за одну итерацию. Результаты, выносимые на защиту:

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

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях, школах, семинарах: Всероссийской научной школе - семинаре молодых ученых, аспирантов и студентов «Семантические технологии - 2013. Семантическая интерпретация и интеллектуальная обработка данных и ее приложение в информационном поиске», Таганрог, 2013 г.; Конгрессе по интеллектуальным системам и информационным технологиям "18&1Т'13", п. Дивноморское, 2013 г.; Ежегодной научной конференции студентов и аспирантов

базовых кафедр Южного научного центра РАН, Таганрог, 2014 г.; Научной конференции «Современные информационные технологии: тенденции и перспективы развития», Южный федеральный университет, г. Ростов-на-Дону, 2014, 2015 гг.; конференции IEEE International Conference on Engineering and Telecommunication (EnT 2014), Долгопрудный, Москва, 2014 г.; Международной научно-практической конференции «Фундаментальные и прикладные исследования в современном мире», Санкт-Петербург, 2014 г.; Всероссийской научно-технической конференции "Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности", Таганрог, 2015 г..

Публикации. Результаты диссертации отражены в 15 печатных работах: из них 5 статей, среди которых 3 в изданиях, входящих в перечень ВАК РФ и 2 в журналах, входящих в реферативную базу SCOPUS, 1 свидетельство об официальной регистрации программы для ЭВМ, а также тезисы и материалы 9 докладов на всероссийских и международных научно-технических конференциях, школах, семинарах. Результаты работы отражены в 2 отчетах о НИР.

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

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

2) разработаны целочисленные параметры, определяющие способ задания последовательности значений переменных квантов в циклах при реализации реальных вычислительных процессов для дельта-преобразований первого и второго порядков;

3) выполнены исследования с использованием компьютерного моделирования,

подтверждающие достоверность полученных результатов;

4) разработаны структурные схемы специализированных устройств, реализующие имеющие специфические особенности алгоритмы решения СЛАУ на базе дельта-преобразований первого и второго порядков;

5) с ориентацией на ПЛИС получены оценки по аппаратным затратам, быстродействию и комплексные сравнительные оценки эффективности реализации разработанных алгоритмов на специализированном вычислителе;

6) проведено исследование возможностей использования дельта-преобразований первого и второго порядков для решения СЛАУ в бортовой задаче локальной навигации, практическая значимость которого подтверждается актом реализации научных результатов в АО «ЦНИИАГ». Структура диссертации. Диссертация состоит из введения, четырех глав,

заключения, библиографического списка и приложения.

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

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

идеализированных итерационных циклов с постоянным квантом определенного значения. Для реализации реальных процессов разработаны квазиоптимальные условия, определяющие способ задания последовательности значений переменных квантов в циклах и базирующиеся на использовании двух или четырех идеализированных итераций в каждом цикле. При этом значения квантов представляются в виде 2~*, 5 е N, что позволяет на каждой итерации представить умножение коэффициента матрицы на квант в виде операции сдвига на 8 двоичных разрядов. Введение данного способа представления кванта позволяет реализовать выполнение итерационного процесса без использования операции умножения многоразрядных кодов. Предлагаются эффективные способы завершения итераций в каждом цикле. В данной главе приводятся результаты исследования итерационного решения различных СЛАУ, отличающихся скоростью сходимости. Показана возможность сокращения количества итераций по сравнению с использованием дельта преобразований с постоянным квантом в сотни - тысячи раз при обеспечении одинаковой точности. Количество итераций при переменном кванте оказывается в значительной мере приближенным по количеству итераций к методу простой итерации.

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

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

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

1. ОБЗОР АЛГОРИТМИЧЕСКИХ МЕТОДОВ И ТЕХНИЧЕСКИХ СРЕДСТВ ОРГАНИЗАЦИИ РЕШЕНИЯ СЛАУ НА ОСНОВЕ ИТЕРАЦИОННЫХ

МЕТОДОВ

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

Список литературы диссертационного исследования кандидат наук Пирская, Любовь Владимировна, 2015 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Амосов, A.A. Вычислительные методы для инженеров [Текст] / A.A. Амосов, Ю.А. Дубинский, Н.В. Копченова. -М.: Изд-во МЭИ, 2003. - 595 с.

2. Балу, К. ПЛИС объединяются с ЦПУ - наступает эра СнК ПЛИС [Текст] / К. Балу // Электронные компоненты. - 2012. - №7. - С.93-94

3. Барабанов, О.О. Математические задачи дальномерной навигации [Текст] / О.О. Барабанов, Л.П. Барабанова. - М.: ФИЗМАТЛИТ, 2007. - 272 с.

4. Бахвалов, Н.С. Численные методы [Текст] / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. - М.: БИНОМ. Лаборатория знаний, 2006. - 632 с.

5. Березин, И.С. Методы вычислений, том 2 [Текст] / И.С. Березин, Н.П. Жидков. - М.: Наука, 1966. - 632 с.

6. Гомозов, О.В. Инкрементные алгоритмы решения систем линейных алгебраических уравнений и архитектура мультипроцессоров на программируемой логике [Текст] / О.В. Гомозов, Ю.В. Ладыженский // Научные труды ДонНТУ. Серия «Информатика, кибернетика и вычислительная техника». - 2010. - Вып. 12 (165). - С.34-40.

7. Гомозов, О.В. Структура инкрементных алгоритмов решения систем линейных алгебраических уравнений [Текст] / О.В. Гомозов // Материалы 3-й международной научно технической конференции «Моделирование и компьютерная графика - 2009». - Донецк, 2009. - С.255-259.

8. Золотухо, Р. Stratix III - новое семейство FPGA фирмы Altera [Текст] / Р. Золотухо, Д. Комолов // Компоненты и технологии. - 2006. - №1. - С. 30-33

9. Икрамов, Х.Д. Численные методы для симметричных линейных систем [Текст] / Х.Д. Икрамов. - М.: Наука, 1988. - 158 с.

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

вычислительной инфраструктуры для экспериментального моделирования [Текст] : отчет о НИР (промежуточный) : 213.01 -11/2014-86 / Южный федеральный университет ; рук. Хусаинов Н.Ш.; исполн.:, Кравченко П. П., Пирская Л.В. [и др.] - Ростов-на-Дону, 2014. - 118 с. -№ ГР 114110640027.

11. Иоффе, Д. 8таг1Ри8Юп2 и ЮЬ002 - надежные, экономичные, компактные. Обзор новых семейств ПЛИС корпорации МюгоБегш [Текст] / Д. Иоффе, А. Казаков // Компоненты и технологии. - 2014. - №8. - С. 87-90.

12. Калачев, А. Многоядерная конфигурируемая вычислительная платформа 2упя-7000 [Текст] / А. Калачев // Современная электроника. - 2013. - №1. -С.22-31.

13. Клочков, Г.Д. Некоторые методы моделирования систем линейных алгебраических уравнений с произвольной матрицей на математических машинах непрерывного действия [Текст] / Т.Д. Клочков, И.А. Николаев // Электромеханика. - 1962. -№11. - С. 1296-1300.

14. Корчинский, А.П. Применение программируемых логических интегральных схем в электронной аппаратуре [Текст] / А.П. Корчинский, Н.В. Бурцева // Електрошка та системи управлшня. - 2009. - № 4(22). - С. 513. [42]

15. Кравченко, П.П. Инкрементные методы решения систем линейных алгебраических уравнений [Текст] / П.П. Кравченко // Многопроцессорные вычислительные структуры. - 1983. - Вып.5(Х1У). - С.30-32.

16. Кравченко, П.П. Исследование алгоритма параллельного решения систем линейных алгебраических уравнений с использованием дельта-преобразований [Текст] / П.П. Кравченко, Л.В. Пирская // Труды Конгресса по интеллектуальным системам и информационным технологиям 'ЧБ&ГПЗ". Научное издание в 4-х томах. - М.: Физматлит, 2013. - Т.З. - С. 202-206.

17. Кравченко, П.П. Исследование возможностей параллельного решения систем линейных алгебраических уравнений с использованием дельта-преобразований [Текст] / П.П. Кравченко, Л.В. Пирская // Сборник трудов

VII Всероссийской научной школы - семинара молодых ученых, аспирантов и студентов «Семантические технологии - 2013. Семантическая интерпретация и интеллектуальная обработка данных и ее приложение в информационном поиске». - Таганрог: Изд-во ЮФУ, 2013. - С.36-38.

18. Кравченко, П.П. Итерационный метод решения систем линейных алгебраических уравнений, исключающий операцию многоразрядного умножения [Текст] / П.П. Кравченко, Л.В. Пирская // Известия ЮФУ. Технические науки. - 2014. -№ 7 (156). - С. 214-224.

19. Кравченко, П.П. Метод организации итерационного решения систем линейных алгебраических уравнений с использованием дельта-преобразований второго порядка [Текст] / П.П. Кравченко, Л.В. Пирская // Известия ЮФУ. Технические науки. - 2015. - № 6 (167). - С. 57-71.

20. Кравченко, П.П. Об исследовании возможностей решения систем линейных алгебраических уравнений с использованием дельта-преобразований второго порядка [Текст] / П.П. Кравченко, Л.В. Пирская // Современные информационные технологии тенденции и перспективы развития: материалы конференции. - Южный федеральный университет. - Ростов-на-Дону: Издательство Южного федерального университета, 2015. - С.306 -308.

21. Кравченко, П.П. Об оценке сокращенного количества итераций при параллельном решении систем линейных алгебраических уравнений с использованием дельта-преобразования первого порядка [Текст] / П.П. Кравченко, Л.В. Пирская // Материалы XXI научной конференции «Современные информационные технологии: тенденции и перспективы развития». - Ростов н/Д: ЮГИНФО ЮФУ, 2014. - С. 220-222.

22. Кравченко, П.П. Оптимизированные дельта-преобразования второго порядка. Теория и применение. Монография [Текст] / П.П. Кравченко. - М: Радиотехника, 2010. - 288 с.

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

первого порядка с переменным квантом / П.П. Кравченко, J1.B. Пирская // Свидетельство о государственной регистрации программы для ЭВМ №2015610364. Зарегистрировано в Реестре программ для ЭВМ 12.01.2015. Заявка №2014661167 от 05.11.2014.

24. Максимов, Н.В. Архитеркута ЭВМ и вычислительных систем: учебник. - 3-е изд. [Текст] / Н.В. Максимов, Т.Д. Партыка, И.И. Попов. - М.: ФОРУМ, 2010.-512 с.

25. Максфилд, К. Проектирование на ПЛИС [Текст] / К. Максфилд. - М.: Додека-ХХ1, 2007. - 408 с.

26. Малиновский, Б.Н. Алгоритмы решения систем линейных алгебраических уравнений, ориентированные на структурную реализацию [Текст] / Б.Н. Малиновский, В.П. Боюн, Л.Г. Козлов // Упр. Системы и машины. - 1977. -Вып.5. - С.79-84.

27. Пирская Л.В. О подходе к сокращению количества итераций при параллельном решении систем линейных алгебраических уравнений с использованием дельта-преобразований первого порядка [Текст] / Л.В. Пирская // Сборник трудов X Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН: тезисы докладов. - Ростов н/Д: Изд-во ЮНЦ РАН, 2014. - С. 80-81.

28. Пирская, Л.В. Алгоритм итерационного решения систем линейных алгебраических уравнений без использования операции многоразрядного умножения [Текст] // Сборник тезисов докладов Международной конференции "Инжиниринг & Телекоммуникации - Еп&Т 2014" (26-28 ноября 2014, Москва, Долгопрудный). Москва. - Долгопрудный: МФТИ, -С.207-209.

29. Пирская, Л.В. Итерационный метод параллельного решения систем линейных алгебраических уравнений с использованием дельта-преобразования первого порядка [Текст] / Л.В. Пирская, П.П. Кравченко // Материалы VIII Международной научно-практической конференции «Фундаментальные и прикладные исследования в современном мире».

Издание в 4 томах. - Санкт-Петербург: Информационный издательский учебно-научный центр «Стратегия будущего», 2014 - Т.1. - С. 4-10.

30. Пирская, JI.B. О возможности использования дельта-преобразований первого порядка для построения специализированного вычислителя [Текст] / J1.B. Пирская // Известия ЮФУ. Технические науки. - 2015. - № 2 (163). -С. 83-92.

31. Пирская, Л.В. Об оценках эффективности использования дельта-преобразований первого порядка для построения специализированного вычислителя [Текст] / Л.В. Пирская // Сборник статей I Всероссийской научно - технической конференции молодых ученых, аспирантов и студентов «Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности». - Ростов-на-Дону: Издательство Южного федерального университета, 2015. - С.294-297.

32. Попович, А. Перспективная платформа для построения бортовых вычислительно управляющих систем [Текст] / А. Попович // Компоненты и технологии. - 2008. - №8. - С. 168-170.

33. Попович, А. Применение технологии разработки "систем на кристалле" на платформе ПЛИС [Текст] / А. Попович // Компоненты и технологии. - 2004. - №4. - С. 114-116.

34. Разработка теоретических и методологических основ создания и применения информационно-алгоритмического и программного обеспечения интегрированных систем цифрового управления и автономной высокоточной навигации по искусственным навигационным полям для перспективных гиперзвуковых летательных аппаратов [Текст] : отчет о НИР (заключительный) : 213.01 -24/2013-102 / Южный федеральный университет ; рук. Кравченко П. П.; исполн.: Хусаинов Н.Ш., Пирская Л.В. [и др.] - Таганрог, 2013. - 104 с. - № ГР 01201368261. - Инв. № 02201452714.

35. Самарский, A.A. Численные методы [Текст] / A.A. Самарский, A.B. Гулин-М.: Наука, 1989. -432 с.

36. Самкова, Е. Stratix IV против Virtex-5. Точка не поставлена [Текст] / Е. Самкова // Электронные компоненты. - 2009. - №8. - С.73-74.

37. Скрыпник, О.Н. Радионавигационные системы воздушных судов: Учебник [Текст] / О.Н. Скрыпник. -М.: ИНФРА-М, 2014. - 348 с.

38. Стешенко, В. Занятие 6. Реализация вычислительных устройств на ПЛИС [Текст] / В. Стешенко // Компоненты и технологии. - 2000. - №8 - С. 88-91.

39. Таненбаум, Э. Архитектура компьютера [Текст] / Э. Таненбаум, Т. Остин. -6-е изд. - СПб.: Питер, 2013. - 816 с.

40. Тарасов, И. Virtex 5 и другие современные ПЛИС фирмы ХШпх / И. Тарасов [Текст] // Современная электроника. - 2008. - №7. - С. 12-15.

41. Тарасов, И. Анализ характеристик FPGA ХШпх семейств Virtex-6 nSpartan-6 [Текст] / И. Тарасов // Компоненты и технологии. - 2009. - №12. - С. 10-16.

42. Тарасов, И. ПЛИС ХШпх и цифровая обработка сигналов. Особенности, преимущества, перспективы [Текст] / И. Тарасов // Электроника НТБ. -2011. - №3. - С. 70-74.

43. Тарасов, И. Расширяемая процессорная платформа семейства Zynq-7000 [Текст] / И. Тарасов // Компоненты и технологии. - 2011. - №4. - С. 88-92.

44. Тарасов, И. Системы на кристалле на базе ПЛИС FPGA ХШпх с встроенными процессорами PowerPC. Часть 1 [Текст] / И. Тарасов // Компоненты и технологии. - 2005. - №7. - С. 62-67.

45. Третьяков, С.И. Алгоритмы работы специализированных процессоров для решения систем уравнений [Текст] / С.И. Третьяков // Кибернетика. - 1978. - №5. - С.34-36.

46. Третьяков, С.И. Реализация метода блочной итерации на специализированных процессорах [Текст] / С.И. Третьяков. - В кн. Технические средства управляющих машин и систем. - Киев, 1978. - С.9.-13.

47. Устройство для решения систем линейных алгебраических уравнений [Текст]: A.c. 542943 СССР: MRK2 G06F 15/32 / В.П. Боюн, Л.Г. Козлов, Б.Н.

Малиновский, С.И. Третьяков. - № 2108752/24; заяв. 25.05.1975; опубл. 25.01.1977, Бюл. № 3.-4 с. : ил

48. Фаддеев, Д. К. Фаддеева. В.Н. Вычислительные методы линейной алгебры, 4-е изд., стереотип [Текст] / Д.К. Фаддеев, В.Н. Фаддеева. - СПб.: Лань, 2009.-734 с.

49. Фриш С.Э., Тиморева A.B. Курс общей физики. Том 1. Физические основы механики, молекулярная физика, колебания и волны [Текст] / С.Э. Фриш, A.B. Тиморева. -М.: ФИЗМАТГИЗ, 1962.-467 с.

50. Хейгеман, Л. Прикладные итерационные методы: Пер. с англ. [Текст] / Л. Хейгеман, Д. Янг. - М.: Мир, 1986. - 448 с.

51.Чудинов, С.М. Подходы по выбору ПЛИС при проектировании вычислительных устройств для обработки информации [Текст] / С.М. Чудинов, С.Н. Маликов, И.В. Зуев // Научные ведомости. Серия История. Политология. Экономика. Информатика. -2014. -№ 1 (172). - С. 161-167.

52. Шагурин, И. «Большие» FPGA как элементная база для реализации систем на кристалле [Текст] / И. Шагурин, В. Шалтырев, А. Волов // Электронные компоненты. - 2006. - №5. - С.83-88

53. Шалтырев, В. Структурная модификация процессорных СФ-блоков для систем на кристалле, реализуемых на базе FPGA [Текст] / В. Шалтырев, И. Шагурин // Электронные компоненты. - 2010. - №1. - С.20-24

54. Шебшаевич, B.C. Сетевые спутниковые радионавигационные системы [Текст] / B.C. Шебшаевич, П.П. Дмитриев. Н.В. Иванцевич и др. - М.: Радио и связь, 1993. -408с.

55. Altera: SoC FPGA — Система на кристалле: ПЛИС + двухъядерный процессор ARM Cortex-А9 [Электронный ресурс]. - Режим доступа: http://www.ebvnews.ru/technical/altera/4510.html, свободный.

56. Barrett, R. Templates for the Solution of Linear Systems: Building Blocks for Iterative Method [Text] / R. Barrett, M. Berry, T.F. Chan et al. - Philadelphia, PA: SI AM Press, 1994. - 124 p.

57. Greenbaum, A. Iterative Methods for Solving Linear Systems [Text] / A. Greenbaum. - Philadelphia, PA. SIAM, 1997. - 220 p.

58. Kravchenko P.P. The method of organizing the iterative process of the system of the linear algebraic equations solution excluding the multidigit multiplication operation [Text] / P.P. Kravchenko, L.V. Pirskaya // Biosciences Biotechnology Research Asia December. - 2014. - Vol. 11 (3). - P. 1831 -1839.

59. Kravchenko, P.P. (1989). Solving systems of algebraic and differential equations by second-order difference modulation [Text] / P.P. Kravchenko // Cybernetics. -1989.-Vol. 25(2).-P. 218-229.

60. Ledyankin, Yu. (1979). An increment method for the solution of the equation Ay=f / Yu. Ledyankin [Text] // USSR Computational Mathematics and Mathematical Physics. - 1979. - №19(4). - C.260-265.

61. Pirskaya, L.V. Iterative Algorithm for Solving of Linear Algebraic Equations Systems without Multi-bit Multiplication Operation [Text] / L.V. Pirskaya // Engineering and Telecommunication (EnT), 2014 International Conference on. -IEEE, 2014.-P. 87-91.

62. Pirskaya, L.V. The iterative algoriphm for solving systems of linear algebraic equations whithout the multibit multiplication operation [Text] / L.V. Pirskaya // International Conference «Engineering & Telecommunication En&T 2014». Book of Abstracts. - Moscow- Dolgoprudny: MIPT, 2014. - P.210 - 212.

63. Vuik, C. Iterative solution methods [Text] / C. Vuik. - The Netherlands. Delft Institute of Applied Mathematics, Delft, 2012. - 118 p.

64. Yang, H. FPGA-based vector processor for algebraic equation solvers [Text] / H. Yang, S.G. Ziavras // IEEE International SOC Conference. - IEEE, 2005. - P. 115-116.

65. Zhang, W. Portable and Scalable FPGA-Based Acceleration of a Direct Linear System Solver [Text] / W. Zhang, V. Betz, J. Rose // ACM Transactions on Reconfigurable Technology and Systems (TRETS). - 2012. - Vol. 5, №1. -Article 6.