Параллельные методы сортировки данных. icon

Параллельные методы сортировки данных.


Смотрите также:
Цель лабораторной ознакомится с различными методами сортировки данных...
«нейроинформатика, её приложения и анализ данных»...
Базы данных, базы знаний и экспертные системы 2...
«Алгоритмы сортировки одномерных массивов»...
Порядок работы на официальном сайте «Реестра государственных контрактов...
Курсовая работа состоит в выполнении 2-х последовательных заданий: 1) задания по быстрому поиску...
План Прикладная политология, ее цели, методы...
Программа дисциплины Компьютерные методы анализа социологических данных (Введение в...
Программа дисциплины «Компьютерные методы анализа социологических данных» (Введение в...
О автор: Тенгиз Куправа www kuprava ru сновы статистического анализа...
Реферат по дисциплине  на тему: «»...
Учебная программа дисциплины Методология и методы психолого-педагогических исследований...



Загрузка...
страницы: 1   2   3   4
вернуться в начало
скачать
^

Лабораторная работа №2





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


Цель работы.

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


^ Теоретическая часть.

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

Задача численного интегрирования состоит в нахождении приближенного значения интеграла . Введём на отрезке расчётную сетку . Точки называют узлами сетки, отрезки – частичными отрезками, – шагами сетки. В этом случае от непрерывной функции необходимо перейти к её дискретным значениям . В качестве приближенного значения интеграла на некоторой расчётной сетке может выступать выражение, аппроксимирующее точное значение с помощью кусочно-постоянных функций (метод трапеций):

.

Основной операцией в нахождении численного значения определённого интеграла является операция суммирования.

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



Рисунок 1.^ Зависимость погрешности вычисления интеграла методом трапеции от количества интервалов разбиения для различных типов данных языка Fortran.

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


Input: a[1..N]

sum = input[1]

c = 0.0

for i = 2, 3,..., N do

y = input[i] - c

t = sum + y

c = (t - sum)- y

sum = t

end for

Output: sum, c


Практическая часть.

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

  2. Провести исследования поведения относительной погрешности численного интегрирования при различных типах данных (float, double, long double для языков С/С++; real*4, real*8, real*16 для языка Фортран) для различных способов суммирования,

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

  4. Оценить арифметическую сложность последовательной и параллельной реализаций метода,

  5. Посчитать теоретическое и практическое ускорение параллельной программы,




Варианты заданий.

  1. Метод прямоугольников,

  2. Метод трапеций,

  3. Метод Симпсона,

  4. Метод Гаусса-4,

  5. Метод Монте-Карло.



^

Лабораторная работа №3





Параллельные методы решения систем линейных

алгебраических уравнений с разреженными матрицами.


^ Цель работы.

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


^ Теоретическая часть.

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

Основной матрично-векторной операцией в итерационных методах является умножение матрицы на вектор. Поэтому для хранения матрицы будем выбирать такой формат, чтобы матрицу хранить по строкам, так как этот вариант разрезания матрицы наиболее перспективен для параллельной реализации умножения матрицы на вектор. Хранить мы будем только ненулевые элементы для каждой строки. Поясним формат на примере следующей матрицы размером N = 5:





Для хранения матрицы определим следующие массивы:

  • row_ptr[6] – массив номеров первых элементов в каждой строке в общей нумерации ненулевых элементов матрицы,

  • val[12] – массив значений элементов матрицы,

  • col_ind[12] – массив номеров столбцов для каждого элемента.

Таким образом, для данной матрицы получим следующие массивы:


real val[12] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0};


integer col_ind[12] = {0, 1, 4, 0, 1, 2, 1, 2, 4, 3, 0, 4};


integer row_ptr[6] ={0, 3, 6, 9, 10, 12};


Для примера будем рассматривать стационарную задачу распределения температуры в области, куда помещён инородный объект с отличной от области теплопроводности. Таким образом, решаемое уравнение имеет вид:


,


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



Рисунок 2. Распределение темепературы, полученной в результате моделирования .


Практическая часть.

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

  2. Провести тестирование реализации на матрице, полученной в результате конечно-элементной аппроксимации приведённой в теоретической части задачи.

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

  4. Исследовать эффективность параллельной реализации.

Варианты заданий.

  1. Метод сопряжённых градиентов,

  2. Локально-оптимальная схема,

  3. Метод бисопряженных градиентов,

  4. Обобщённый метод минимальных невязок (GMRES),

  5. Метод Гаусса – Зейделя.




оставить комментарий
страница2/4
Дата24.08.2011
Размер1 Mb.
ТипЛабораторная работа, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы: 1   2   3   4
плохо
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх