Архив категории ‘Параллельные алгоритмы’

Параллельные алгоритмы решения дифференциальных уравнений в частных производных. Результаты вычислительных экспериментов

    На этом шаге мы приведем результаты выполнения последовательного и параллельного алгоритма, а также тексты приложений.     Приведем результаты вычислительных экспериментов для параллельного алгоритма Гаусса-Зейделя при ленточной схеме разбиения данных (таблица 1). Таблица 1. Результаты вычислительных экспериментов для параллельного алгоритма Гаусса-Зейделя (время выполнения приведено в миллисекундах) Размер сетки Последовательный алгоритм Параллельный алгоритм 1 процессор 4 […]

вычислений для систем с распределенной памятью. Оценка трудоемкости операций передачи данных

    На этом шаге мы приведем оценку трудоемкости операций передачи данных.     Время выполнения коммуникационных операций значительно превышает длительность вычислительных команд. Оценка трудоемкости операций приема-передачи может быть осуществлена с использованием двух основных характеристик сети передачи: латентности, определяющей время подготовки данных к передаче по сети, и пропускной способности сети, задающей объем передаваемых по сети за 1 […]

Паралллельные алгоритмы… Организация параллельных вычислений для систем с распределенной памятью. Блочная схема разделения данных

    На этом шаге мы рассмотрим еще одну схему разделения данных.     Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов. При этом столь радикальное изменение способа разбиения сетки практически не потребует каких-либо существенных корректировок рассмотренной схемы параллельных вычислений. Основной новый момент при блочном представлении данных состоит в […]

Организация параллельных вычислений для систем с распределенной памятью

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

Паралллельные алгоритмы… Организация параллельных вычислений для систем с распределенной памятью. Коллективные операции обмена информацией

    На этом шаге мы рассмотрим способ определения погрешности вычислений.     Рассмотрим способы вычисления общей для всех процессоров погрешности вычислений. Возможный очевидный подход состоит в передаче всех локальных оценок погрешности, полученных на отдельных полосах сетки, на один какой-либо процессор, вычисления на нем максимального значения и последующей рассылки полученного значения всем процессорам системы. Однако такая схема […]

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

    На этом шаге мы рассмотрим организацию обмена данными между процессорами.     Параллельный вариант метода сеток при ленточном разделении данных состоит в обработке полос на всех имеющихся процессорах одновременно в соответствии со следующей схемой работы: // действия, выполняемые на каждом процессоре do { // <обмен граничных строк полос с соседями> // <обработка полосы> // <вычисление […]

Паралллельные алгоритмы… Организация параллельных вычислений для систем с распределенной памятью. Разделение данных

    На этом шаге мы рассмотрим способы разделения данных.     В рассматриваемой задаче возможны два различных способа разделения данных - одномерная или ленточная схема или двухмерное или блочное разбиение вычислительной сетки.     При ленточном разбиении область расчетов делится на горизонтальные или вертикальные полосы (не уменьшая общности, далее будем рассматривать только горизонтальные полосы). Число полос определяется […]

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

    На этом шаге мы рассмотрим способ управления вычислительной нагрузкой процессора.     Как уже отмечалось ранее, вычислительная нагрузка при волновой обработке данных изменяется динамически в ходе вычислений. Данный момент следует учитывать при распределении вычислительной нагрузки между процессорами. Так, например, при фронте волны из 5 блоков и при использовании 4 процессоров обработка волны потребует двух параллельных […]

Параллельные алгоритмы решения диф.уравнений в частных производных. Волновые схемы параллельных вычислений

    На этом шаге мы рассмотрим некоторые волновые схемы параллельных вычислений.     Рассмотрим теперь возможность построения параллельного алгоритма, который выполнял бы только те вычислительные действия, что и последовательный метод (может быть только в некотором ином порядке) и, как результат, обеспечивал бы получение точно таких же решений исходной вычислительной задачи. Как уже было отмечено выше, в […]

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

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