Расчет определённого интеграла. Фролова Ксения. 6 курс — различия между версиями

Версия 13:26, 18 января 2016

Постановка задачи

Необходимо вычислить определенный интеграл [math]\int^1_0x^2dx[/math] с использованием средств параллельного программирования на основе MPI.

Используемый метод

В вычислительных системах с распределенной памятью процессоры работают независимо друг от друга. Для организации параллельных вычислений в таких условиях необходимо иметь возможность распределять вычислительную нагрузку и организовать информационное взаимодействие (передачу данных) между процессорами. Параллельное программирование служит для создания программ, эффективно использующих вычислительные ресурсы за счет одновременного исполнения кода на нескольких вычислительных узлах. Для создания параллельных приложений используются параллельные языки программирования и специализированные системы поддержки параллельного программирования, такие как MPI и OpenMP. Итак, MPI - это библиотека передачи сообщений, собрание функций на C/C++ (или подпрограмм в Фортране), облегчающих коммуникацию (обмен данными и синхронизацию задач) между процессами параллельной программы с распределенной памятью. Акроним MPI установлен для Message Passing Interface (интерфейс передачи сообщений). Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов. Все процессы порождаются один раз, образуя параллельную часть программы. Каждый процесс работает в своем адресном пространстве, никаких общих переменных или данных в MPI нет. Процессы могут выполняться на разных процессорах, но на одном процессоре могут располагаться и несколько процессов (в этом случае их исполнение осуществляется в режиме разделения времени).

Реализация

Для расчета указанного интеграла используется метод трапеций - метод численного интегрирования функции одной переменной, заключающийся в замене на каждом элементарном отрезке подинтегральной функции на многочлен первой степени, то есть линейную функцию. Площадь под графиком функции аппроксимируется прямоугольными трапециями. Отрезок [a..b] (в данной задаче [0..1]) разбивается на заданное количество интервалов (в данной задаче n=100000000), и на каждом из элементарных отрезков применяется формула трапеций. Cуммирование даст составную формулу трапеций:

[math]\int^b_a f(x)\,dx \approx \sum_{i=0}^{n-1} \frac{ f(x_i) + f(x_{i+1}) }{2} (x_{i+1} - x_{i}) [/math]

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

Результаты

Вычислен определенный интеграл [math]\int^1_0x^2dx[/math].

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