|
|
| (не показано 6 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | Незаконченный вариант статьи
| |
| | | | |
| − | == Свойства и структура алгоритма ==
| |
| − |
| |
| − | === Общее описание алгоритма ===
| |
| − |
| |
| − | '''Адаптивное интегрирование''' - метод быстрого вычисления интеграла функции, который использует адаптивное изменение плотности сетки интегрирования. На промежутках, где функция гладкая, сетка разреженная, на промежутках со значительными колебаниями значений сетка гуще для получения необходимой точности.
| |
| − |
| |
| − | === Математическое описание алгоритма ===
| |
| − |
| |
| − | Формулы метода:
| |
| − |
| |
| − | # Интеграл функции вычисляется по квадратурной [https://ru.wikipedia.org/wiki/Формула_Симпсона формуле Симпсона] с числом узловых точек равным 4 и 8 на отрезке [a, b].
| |
| − | # Вычисляется разность найденных значений
| |
| − | ## Если разность интегралов меньше либо равна желаемой точности интегрирования ε - заканчиваем процедуру.
| |
| − | ## Если разность больше, то отрезок разбивается на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.
| |
| − | Алгоритм имеет рекурсивную природу.
| |
| − |
| |
| − | === Макростуктура алгоритма ===
| |
| − |
| |
| − | Основную часть метода составляют рекурсивные вызовы интегралов отрезков меньшей длинны.
| |
| − |
| |
| − | === Входные данные ===
| |
| − |
| |
| − | * Функция.
| |
| − | * Отрезок вида [a, b].
| |
| − | * Желаемая точность интегрирования ε.
| |
| − |
| |
| − | === Выходные данные ===
| |
| − |
| |
| − | * Интеграл функции на отрезке [a, b] с точностью ε.
| |
| − |
| |
| − | == Программная реализация алгоритма ==
| |
| − |
| |
| − | === Исходный код реализованного алгоритма ===
| |
| − |
| |
| − | Весь исходный код в статье можно найти в репозитории на [https://github.com/bvdmitri/aintegrate GitHub].
| |
| − |
| |
| − | === Реализации на одном процессоре ===
| |
| − |
| |
| − | Простейшую рекурсивную реализацию данного алгоритма , которая не использует ресурсы параллелизма можно посмотреть [https://github.com/bvdmitri/aintegrate/blob/master/src/method/sequential/SequentialMethod.cpp здесь].
| |
| − |
| |
| − | <source lang="c++">
| |
| − | #include "SequentialMethod.h"
| |
| − |
| |
| − | SequentialMethod::SequentialMethod(double eps, const std::function<double(double)> &f) : IntegrationMethod(eps, f) {}
| |
| − |
| |
| − | double SequentialMethod::integrate(double a, double b) {
| |
| − | double x = simpson(a, b, 4);
| |
| − | double y = simpson(a, b, 8);
| |
| − | if (fabs(x - y) < eps) {
| |
| − | return y;
| |
| − | } else {
| |
| − | return integrate(a, (a + b) / 2.0) + integrate((a + b) / 2.0, b);
| |
| − | }
| |
| − | }
| |
| − |
| |
| − | SequentialMethod::~SequentialMethod() {}
| |
| − | </source>
| |
| − |
| |
| − | <br>
| |
| − | Реализация с помощью библиотеки [https://www.threadingbuildingblocks.org Intel TBB] для более эффективного использования многоядерных процессоров можно посмотреть [https://github.com/bvdmitri/aintegrate/blob/master/src/method/tbb/TBBMethod.cpp здесь].
| |
| − |
| |
| − | <source lang="c++">
| |
| − |
| |
| − | #include "TBBMethod.h"
| |
| − |
| |
| − | TBBMethod::TBBMethod(double eps, const std::function<double(double)> &f) : IntegrationMethod(eps, f) {}
| |
| − |
| |
| − | double TBBMethod::integrate(double a, double b) {
| |
| − | double x = simpson(a, b, 4);
| |
| − | double y = simpson(a, b, 8);
| |
| − | if (fabs(x - y) < eps) {
| |
| − | return y;
| |
| − | } else {
| |
| − | tbb::task_group group;
| |
| − |
| |
| − | group.run([&] {
| |
| − | x = integrate(a, (a + b) / 2.0);
| |
| − | });
| |
| − |
| |
| − | group.run_and_wait([&] {
| |
| − | y = integrate((a + b) / 2.0, b);
| |
| − | });
| |
| − |
| |
| − | return x + y;
| |
| − | }
| |
| − | }
| |
| − |
| |
| − | TBBMethod::~TBBMethod() {}
| |
| − |
| |
| − | </source>
| |
| − |
| |
| − | === Параллельная реализации ===
| |
| − |
| |
| − | ==== Реализация с помощью MPI для межпроцессорного взаимодействия и [https://www.threadingbuildingblocks.org Intel TBB] для внутрипроцессорного взаимодействия ====
| |
| − |
| |
| − | [https://github.com/bvdmitri/aintegrate/blob/master/src/method/mpi_tbb/MPI_TBBMethod.cpp Исходный код]
| |
| − |
| |
| − | В данной реализации отрезок [a, b] делится на число доступных процессоров, каждый отрезок считается на своем процессоре, рекурсия заменяется на [https://www.threadingbuildingblocks.org/tutorial-intel-tbb-task-based-programming систему] задач библиотеки Intel MPI для более эффективного использования многоядерных процессоров.
| |
| − |
| |
| − | ==== Реализация только с помощью MPI ====
| |
| − |
| |
| − | [https://github.com/bvdmitri/aintegrate/tree/master/src/method/mpi_farm Исходный код]
| |
| − |
| |
| − | В данной реализации рекурсия заменяется на систему задач, каждая задача представляет собой подсчет интеграла на отрезке, в случае если необходимая точность не достигнута (см. Математическое описание алгоритма), создаются две новые задачи с меньшими отрезками и распределяются между другими процессорами. Данная реализация в теории решает проблему неравномерности гладких и не гладких участков функции, в случае когда большая часть участков гладкая и лишь небольшой участок функции сильно осциллирует.
| |
| − |
| |
| − | === Тесты производительности ===
| |
| − |
| |
| − | ==== MPI + TBB ====
| |
| − |
| |
| − | [[file:Mpi_tbb_1.png|thumb|center|500px|Рисунок 1. Результаты масштабируемости для MPI + TBB реализации]]
| |
| − | [[file:Mpi_tbb_2.png|thumb|center|500px|Рисунок 2. Результаты масштабируемости для MPI + TBB реализации]]
| |
