Скачать 143.55 Kb.
|
УДК 681.3И.А. НазароваДонецкий национальный технический университет, Донецк, Украина. nazarova@r5.dgtu.donetsk.ua Экспоненциальные методы решения линейной задачи Коши с альтернативными способами оценки локальной погрешности для массивно-параллельных компьютерных системПредложены специальные параллельные алгоритмы численного решения линейной задачи Коши на основе экспоненциального метода. Исследована эффективность применения альтернативных способов оценки локальной апостериорной погрешности. Разработаны вычислительные схемы отображения методов на параллельные структуры различной архитектуры и топологии процессорных элементов. Теоретические исследования и проведенные вычислительные эксперименты показывают, что наиболее используемым способом получения параллельных алгоритмов есть распараллеливание известных последовательных методов и математических описаний. Для разработки параллельных алгоритмов задач практического уровня сложности используется многоэтапный технологический процесс, названный иерархической декомпозиционной методикой [1-3]. Первоначально вычислительная задача разбивается на подзадачи, анализируются информационные взаимосвязи между подзадачами, биективно к множеству подзадач определяется множество макроопераций, оценивается эффективность потенциального крупно или среднеблочного параллелизма. Затем, методика применяется для распараллеливания каждой из макроопераций, то есть используется мелкозернистый параллелизм. Для разработки параллельного алгоритма и проверки корректности его построения на каждом из уровней используется математический аппарат графов влияния [1]. На основе применения декомпозиционной методики разработаны параллельные алгоритмы решения задачи Коши для систем линейных обыкновенных дифференциальных уравнений (СЛОДУ) со встроенными способами оценки локальной апостериорной погрешности: дублирование шага по правилу Рунге, вложенные методы, локальная экстраполяция Ричардсона. В частности, предложены специальные, экспоненциальные, методы решения однородных и неоднородных СЛОДУ с постоянными коэффициентами. Как показали исследования, учет специфики задачи позволяет строить более эффективные параллельные вычислительные алгоритмы, чем в случае применения стандартных численных схем. Экспоненциальный метод относится к частным методам численного интегрирования линейной задачи Коши для однородных СОДУ с постоянными коэффициентами, основан на точном представлении решения в аналитической форме и приближенном вычислении матричной экспоненты [4]. Общий вид задачи Коши для однородных СЛОДУ с постоянными коэффициентами: ![]() где ![]() ![]() ![]() Точным решением задачи Коши для СЛОДУ вида (1) является матричная экспонента: ![]() Приближенное решение можно построить, аппроксимировав матричную экспоненту отрезком её ряда Тейлора при малом ![]() ![]() а затем, используя некоторый алгоритм умножения матриц, вычислить численное решение (1). Полученная вычислительная схема (3) интегрирования однородных СЛОДУ с постоянными коэффициентами соответствует разностному методу решения порядка ![]() На основе экспоненциального метода построены три различных параллельных алгоритма с учетом альтернативных способов оценки локальной погрешности : 1) экспоненциальный и правило Рунге; 2) вложенный - экспоненциальный; 3) экспоненциальный с локальной экстраполяцией. Матричная экспонента ![]() ![]() Интегрирование однородных СЛОДУ с постоянными коэффициентами на основе экспоненциального метода и встроенного способа вычисления локальной погрешности на основе дублирования шага по правилу Рунге требует вычисления решения с удвоенным и дважды с половинным шагом. Используя аппроксимацию матричной формы ![]() ![]() ![]() ![]() где матричная форма (функция): ![]() Основными преимуществами предложенного метода являются: 1) фактическое отсутствие вычислений для промежуточной точки с половинным шагом; 2) возможность введения подготовительного этапа, который будет выполняться до начала интегрирования, и вынесение в него наиболее ресурсоемких операций нахождения матричных форм, а именно матричного умножения, не зависящего от шага интегрирования. Применение идеи вложенных форм в сочетании с экспоненциальным методом решения предполагает вычисление двух аппроксимаций решения смежных порядков точности в одной точке интегрирования: ![]() ![]() ![]() ![]() ![]() Как правило, формула более высокого, ![]() ![]() ![]() Вычислительная схема (8) позволяет уменьшить время каждого шага интегрирования за счет создания подготовительного этапа, который будет выполняться до начала основного счета и содержать операции, не связанные непосредственно с номером шага. Ускорение вычислений по технологии локальной экстраполяции при решении линейной однородной задачи Коши с постоянными коэффициентами также может быть получено на основе экспоненциального метода. Минимизировать вычислительные затраты можно реализацией ![]() ![]() ![]() ![]() ![]() Так, например, классический явный метод Рунге-Кутты четвертого порядка точности соответствует использованию матричной формы ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Затем, используя соотношение для полиномиальной экстраполяции Эйткена-Невилла, вычислить приближения: ![]() ![]() ![]() ![]() ![]() ![]() Для построения параллельных экспоненциальных алгоритмов решения линейной задачи Коши для однородных СОДУ с постоянными коэффициентами + способ оценки шаговой погрешности используется декомпозиционная иерархическая технология и аппарат графов влияния. Поскольку в линейной задаче Коши вид правой части СОДУ известен, то алгоритм решения может быть разбит на известные подзадачи линейной алгебры. Совокупность подзадач реализуется через следующее множество макроопераций:
Параллельная реализация двух основных наиболее ресурсоемких макроопераций требует распараллеливания операций умножения двух матриц и матрицы на вектор. Для рассматриваемых параллельных приложений топологическим решением, адекватно отображающим логическую связь между независимыми процессами, является квадратная сетка или ее замкнутый эквивалент – 2D-тор. На такой топологической схеме эффективно выполняются матричные операции, составляющие основу всех преобразованных форм. Вычисление матричного умножения и умножения матрицы на вектор будет выполнено с использованием блочного систолического алгоритма [7]. Временные характеристики этих базовых макроопераций приведены в таблицах 1 и 2, где ![]() ![]() ![]() ![]() ![]() ![]() ![]() Таблица 1 Время параллельного выполнения матричных /векторных умножений для блочного систолического алгоритма
Таблица 2 Время коммуникационных операций параллельного выполнения матричных /векторных умножений на основе блочного систолического алгоритма при топологии 2D-тор
Все исследуемые параллельные алгоритмы на основе экспоненциального метода содержат 0-ой подготовительный этап, который выполняется один раз до начала интегрирования и вычисляет блоки матриц: ![]() ![]() ![]() ![]() Для оценки эффективности разработанных экспоненциальных алгоритмов решения линейной задачи Коши проведем сравнение с общепринятыми схемами вычислений на базе ![]() ![]() ![]() ![]() ![]() ![]() ![]() Рисунок 1 – Графики зависимости соотношения времен реализации параллельных алгоритмов экспоненциальной и стандартной явной одношаговой схем с правилом Рунге от порядка метода Аналогичные результаты можно получить при оценке асимптотической сложности различных вычислительных схем на основе вложенных форм. Пусть время выполнения параллельного алгоритма на основе стандартной вложенной схемы равно ![]() ![]() ![]() ![]() ![]() ![]() Рисунок 2 – Графики зависимости времени реализации параллельных вложенных методов на основе стандартной и экспоненциальной схем от размерности задачи ![]() Рисунок 3 – Графики зависимости времени реализации параллельных вложенных методов на основе стандартной и экспоненциальной схем от числа процессоров Для сравнения вычислительной сложности двух параллельных алгоритмов решения СЛОДУ на базе локальной экстраполяции также ограничимся учетом наиболее ресурсоемкой операции. Пусть время выполнения параллельного алгоритма на основе стандартной схемы равно ![]() ![]() ![]() ![]() До сих пор при построении параллельных алгоритмов в качестве топологического решения использовалась замкнутая 2D-решетка или 2D-тор. При переходе на физическую коммутационную сеть иной топологии необходимо иметь гибкий программный механизм логического отображения одной топологии на другую. Математическим аппаратом, способным решить поставленную задачу, являются двоичные рефлексивные коды Грея [7]. Соединение процессоров в коммуникационную сеть по типу гиперкуб одно из наиболее используемых топологических решений в реальных параллельных архитектурах. Рассматривается параллельная вычислительная система с ![]() ![]() Гиперкуб ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 1)помещаем 0 перед каждым кодом в ![]() 2)помещаем 1 перед каждым кодом в реверсированном ![]() 3)записываем последовательно первый и второй полученные списки, имеем код Грея длины ![]() Логическое отображение двумерной замкнутой решетки на гиперкуб выполняется по правилу: процессорному элементу решетки с координатами ![]() ![]() ![]() Заметим, что в результате выполнения такого отображения процессоры, являющиеся “непосредственными соседями” в топологии тор, будут иметь те же свойства в топологии гиперкуб. Таким образом, все параллельные алгоритмы, разработанные для замкнутой решетки, только использованием средств библиотеки MPI, могут быть перенесены без изменения алгоритма на коммуникационную сеть гиперкуб. Построение аналогичного логического отображения описанного множества алгоритмов на параллельные архитектуры с физической топологией кольцо влечет за собой увеличение времени выполнения коммуникационной составляющей алгоритмов и имеет заведомо худшие характеристики параллелизма, чем в случае топологий тор и гиперкуб. Существует другой способ решения возникшей задачи. Для топологии кольцо эффективно применять ленточное (по строкам или по столбцам) разбиение данных и простой алгоритм матричного умножения. Численное решение задачи Коши для неоднородной системы линейных уравнений с постоянными коэффициентами: ![]() можно записать в виде: ![]() где ![]() В случае линейных систем общего вида: ![]() Заключение Численный эксперимент на базе тестов для СОДУ [8] и проведенный сравнительный анализ динамических характеристик параллельных алгоритмов показал, что вне зависимости от способа вычисления локальной погрешности, параллельные алгоритмы, основанные на применении экспоненциального метода решения, имеют меньшую вычислительную сложность и лучшие показатели качества параллелизма по сравнению со своими стандартными аналогами. Исследована эффективность альтернативных способов определения локальной апостериорной погрешности при решении линейной задачи Коши для СОДУ на основе явных схем и выявлены предпочтительные области применения различных алгоритмов вычисления шаговой погрешности. Наименее трудоемкий способ определения локальной апостериорной погрешности решения для управления шагом интегрирования – это методы вложенных форм. Преимущества локальной экстраполяции Ричардсона проявляются при получении высокоточного решения. Перспективным направлением дальнейших исследований является разработка и исследование особенностей применения способов оценки апостериорной локальной погрешности для управления шагом интегрирования при решении задачи Коши параллельными блочными ![]() Литература
І.А.Назарова Експоненційні методи вирішення лінійної задачі Коші з альтернативними засобами оцінки локальної похибки для масивно-паралельних комп’ютерних систем Запропоновані спеціальні паралельні алгоритми чисельного вирішення лінійної задачі Коші на базі експоненціального методу. Досліджена ефективність застосування альтернативних засобів оцінки локальної апостеріорної похибки. Розроблені обчислювальні схеми відображення методів на паралельні структури різної архітектури та топології з’єднання процесорних елементів. I.A.Nazarova Exponential methods for the decision of linear Cauchy’s problem with alternative facilities of local error estimation’s for massive-parallel computer systems There are proposed special parallel algorithms for numerical decision of linear Cauchy’s problem based on exponential methods. The efficiency of applications of alternative facilities of local a posteriori error estimation’s are investigated. The calculable schemes of methods reflection on parallel structures with different architectures and topologies are developed. Статья поступила в редакцию .07.2007. « ![]() |
![]() | Экстраполяционные блочные одношаговые численные методы решения жестких задач Коши | ![]() | В. М. Оверко, В. П. Овсянников – кандидаты техн наук, доценты, Донецкий Национальный технический университет, г. Донецк, Украина |
![]() | Донецкий национальный технический университет, ул. Артема, 58, г. Донецк, Украина 83000 | ![]() | Место проведения: Донецк (Украина), Донецкий национальный технический университет. Адрес: г. Донецк, улица Артёма, дом 96, 3-й учебный... |
![]() | Эффективность параллельных алгоритмов оценки локальной апостериорной погрешности для численного решения задачи Коши | ![]() | Некоторые аспекты развития и повышения экологической безопасности предприятий черной металлургии украины |
![]() | Рая позволяет более подробно изучить процессы образования цен и достижение оптимальной равновесной цены; представить графически изменения... | ![]() | Рассмотрены перспективные направления повышения технического уровня агломерационного производства Украины, пребывающего в начале... |
![]() | Донецкий национальный медицинский университет им. М. Горького, г. Донецк, Украина | ![]() | Государственное высшее учебное заведение Донецкий национальный технический университет, г. Донецк |