|
|
| (не показано 11 промежуточных версий 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 Исходный код]
| |
| − |
| |
| − | В данной реализации рекурсия заменяется на систему задач, каждая задача представляет собой подсчет интеграла на отрезке, в случае если необходимая точность не достигнута (см. Математическое описание алгоритма), создаются две новые задачи с меньшими отрезками и распределяются между другими процессорами. Данная реализация в теории решает проблему неравномерности гладких и не гладких участков функции, в случае когда большая часть участков гладкая и лишь небольшой участок функции сильно осциллирует.
| |
