Алговики - Вклад [ru]

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-08T12:33:58Z

Лиджиев Данир Владимирович: /* Информационный граф */

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

{{algorithm
| name = Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки
| input_data = <math>O(1)</math>
| output_data = <math>O(1)</math>
}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен, так как на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double f(double x)
{
return (1/x*x)*sin(1/(x*x))*sin(1/(x*x));
}

const double eps = 0.00001;

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

Функция получает координаты начала и конца отрезка. В цикле проверяется условие if (|sAB - sACB| ≥ ε|sACB|). Если оно соблюдается, то один отрезок помещается в стек, а на другом продолжаются вычисления до тех пор, пока не достигается необходимая точность. Затем вычисляется интеграл на отрезках, концы которых берутся из стека.

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png|700px|center|thumb|Рис.1.]]

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

[[Файл:Adaptive mesh informac graph.png|700px|center|thumb|Рис.2. Информационный граф для алгоритма глобального стека. [a,b] - выбор отрезка, calcSquare - вычисление площади, Div - деление отрезка пополам, Check - проверка достижения точности, Wr - запись отрезка в локальный/глобальный стек, Sum - общая сумма]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Файл:Adaptive mesh informac graph.png

2017-02-08T12:19:19Z

Лиджиев Данир Владимирович:

Обсуждение участника:Greno4ka

2017-02-06T00:05:32Z

Лиджиев Данир Владимирович: /* Пункт 1.10 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы (сделано)
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

Ответ: в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Ответ: Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.
(сделано)

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию? (сделано)

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK) (сделано)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Обсуждение участника:Greno4ka

2017-02-06T00:05:04Z

Лиджиев Данир Владимирович: /* Статья Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы (сделано)
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

Ответ: в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Ответ: Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.
(сделано)

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию? (сделано)

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-06T00:04:53Z

Лиджиев Данир Владимирович:

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

{{algorithm
| name = Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки
| input_data = <math>O(1)</math>
| output_data = <math>O(1)</math>
}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен, так как на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double f(double x)
{
return (1/x*x)*sin(1/(x*x))*sin(1/(x*x));
}

const double eps = 0.00001;

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

Функция получает координаты начала и конца отрезка. В цикле проверяется условие if (|sAB - sACB| ≥ ε|sACB|). Если оно соблюдается, то один отрезок помещается в стек, а на другом продолжаются вычисления до тех пор, пока не достигается необходимая точность. Затем вычисляется интеграл на отрезках, концы которых берутся из стека.

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Обсуждение участника:Greno4ka

2017-02-06T00:02:45Z

Лиджиев Данир Владимирович: /* Пункт 1.9 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

Ответ: в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Ответ: Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.
(сделано)

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию? (сделано)

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-06T00:02:20Z

Лиджиев Данир Владимирович: /* Схема реализации последовательного алгоритма */

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен, так как на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double f(double x)
{
return (1/x*x)*sin(1/(x*x))*sin(1/(x*x));
}

const double eps = 0.00001;

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

Функция получает координаты начала и конца отрезка. В цикле проверяется условие if (|sAB - sACB| ≥ ε|sACB|). Если оно соблюдается, то один отрезок помещается в стек, а на другом продолжаются вычисления до тех пор, пока не достигается необходимая точность. Затем вычисляется интеграл на отрезках, концы которых берутся из стека.

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Обсуждение участника:Greno4ka

2017-02-05T23:50:43Z

Лиджиев Данир Владимирович: /* Пункт 1.5 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

Ответ: в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Ответ: Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию? (сделано)

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Обсуждение участника:Greno4ka

2017-02-05T23:48:35Z

Лиджиев Данир Владимирович: /* Пункт 1.2 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

Ответ: в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию? (сделано)

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-05T23:47:48Z

Лиджиев Данир Владимирович:

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен, так как на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double f(double x)
{
return (1/x*x)*sin(1/(x*x))*sin(1/(x*x));
}

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Обсуждение участника:Greno4ka

2017-02-04T22:07:21Z

Лиджиев Данир Владимирович: /* Пункт 1.10 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию? (сделано)

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Обсуждение участника:Greno4ka

2017-02-04T22:05:18Z

Лиджиев Данир Владимирович: /* Пункт 1.5 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

Да, оно отличается, но здесь имеются в виду разные ситуации:
В пункте 1.2 мы говорим, что при соблюдении условия <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
мы ''останавливаем'' вычисления.
В то время как в 1.5 при abs(sAB - sACB) >= eps * abs(sACB) мы ''продолжаем'' вычисления методом локального стека.

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию?

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Обсуждение участника:Greno4ka

2017-02-04T21:50:08Z

Лиджиев Данир Владимирович: /* Пункт 1.2 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

в некоторых точках значение подынтегральной функции вычисляется более одного раза. Например, в точке А функция будет вычислена k раз, где k - число выполнения цикла do-while. Никаких проблем с сохранением значений нет. Это было взято из рекомендованной книги... Переписали без этого пункта

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию?

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-04T21:49:59Z

Лиджиев Данир Владимирович: /* Математическое описание алгоритма */

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен, так как на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-04T21:49:45Z

Лиджиев Данир Владимирович: /* Математическое описание алгоритма */

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен так как на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Обсуждение участника:Greno4ka

2017-02-04T21:42:09Z

Лиджиев Данир Владимирович: /* Пункт 1.4 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека. (сделано)

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию?

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Обсуждение участника:Greno4ka

2017-02-04T21:41:24Z

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание (сделано)
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5 (сделано)
* Не указан вклад каждого автора (сделано)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека.

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию?

* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Графы, приведённые в разделе 1.7, не являются информационными графами (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 16:41, 3 февраля 2017 (MSK)

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-02T07:27:18Z

Лиджиев Данир Владимирович:

{{Assignment}}

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

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

== Макроструктура алгоритма ==

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

== Последовательная сложность алгоритма ==

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

== Информационный граф ==

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

== Ресурс параллелизма алгоритма ==

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

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Лиджиев Данир Владимирович

2017-02-02T06:51:40Z

Лиджиев Данир Владимирович: Новая страница: «Лиджиев Данир Владимирович, группа 604»

Лиджиев Данир Владимирович, группа 604

Обсуждение участника:Lineprinter

2016-10-18T21:06:05Z

Лиджиев Данир Владимирович:

== Перенос ==
Статья: [[Участник:Бобцов Борис/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]]
Выполняет: [[Участник:Бобцов Борис| Бобцов Борис]]

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]]
Выполняют: [[Участник:Greno4ka| Устинов Григорий ]] и [[ Лиджиев Данир ]]

Статья: [[Кластеризация сетями Кохонена]]
Выполняют: [[Участник:Kravtsovkirill| Кравцов Кирилл]] и [[Участник:Emaksimov| Максимов Егор]]

Статья: [[Нахождение собственных чисел квадратной матрицы методом QR разложения (2)]]
Выполняют: Баев Олег и Шевелев Александр

Статья: [[Стабилизированный метод биспоряженных градиентов (BiCGSTAB)]]
Выполняют: Гаврилов Алексей и Новиков Александр

Статья: [[Участники: Бобошко А., Юмакаева А./Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка]];
Выполняют: Бобошко Алексей и Юмакаева Алина

Статья: [[Алгоритм кластеризации, основанный на сетях Кохоннена]];
Выполняют: Логвиненко Александра и Адиев Тохтар

Статья: [[Ортогонализация Грама-Шмидта]];
Выполняют: [[Участник:KibAndrey| Кибанов Андрей]] и Аджиева Татьяна

Статья: [[Самоорганизующиеся карты Кохонена]];
Выполняет: [[Участник:Anton goy| Гой Антон]]

Статья:[[ЕМ-алгоритм_(Тематическое_моделирование)]];
Выполняют: Мурат Апишев и Андрей Заночкин

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья: [[Алгоритм_k-средних]]
Выполняют: [[Участник:Error2407|Богомазов Евгений]], [[Участник:Илья_Егоров|Егоров Илья]]

Статья: [[Алгоритм k-means]]
Выполняют: [[Участник:Бротиковская Данута|Данута Бротиковская]] и [[Участник:DennZo1993|Денис Зобнин]]

Статья: [[Partitioning Around Medoids (Алгоритм)]]
Выполняют: [[Участник:Denemmy| Галеев Данил]] и [[Участник:Ivan.Z| Запутляев Иван]]

Статья: [[Нечеткий_алгоритм_С_средних]]
Выполняют: [[Участник:Demon smd|Д.А.Гуськов]], [[Участник:marina abramenkova|М.А.Абраменкова]]

Статья: [[Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка]];
Выполняют: [[Участник:Алимов_Дамир_Алиевич|Алимов Дамир]] и [[Участник:Anlesnichiy|Антон Лесничий]]

Статья: [[Строгий_алгоритм_С_средних_(Hard_C-Means,_HCM)]];
Выполняют: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]] и [[Участник:Юрий_Комаров|Комаров Юрий]]

Статья: [[Алгоритм кластеризации, основанный на минимальном остовном дереве]];
Выполняет: [[Участник:Astandrik | Стандрик Антон Сергеевич]]

Статья: [[Умножение разреженной матрицы на вектор]];
Выполняет: [[Участник:Lexaloris | Новоселов Алексей]], Выполняет: [[Участник:kochet|П.А. Кочетков]]

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Участница:JuliaA|Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Статья:[[EM-алгоритм_кластеризации]]
Выполняет: [[Участник:Noite|Зинченко Дмитрий]]

Статья:[[Алгоритм_k_means]]
Выполняют: [[Участник:IanaV| Валуйская Яна]], [[Участник:GlotovES| Глотов Евгений]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы ЗП |Метод Якоби вычисления собственных значений симметричной матрицы ЗП]];
Выполняют: [[Участник:Зиновьев Владимир|Зиновьев В.С.]], [[Участник:Пронин Андрей|Пронин А.М.]]

Статья:[[Алгоритм_кластеризации,_основанный_на_минимальном_покрывающем_дереве]]
Выполняет: [[Участник:Kanast74|Дмитриева Анастасия]]

Статья:[[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(4)]]
Выполняют: [[Участник:F-morozov|Морозов Ф. В.]], [[Участник:Nataliya|Пащенко Н. Ф.]]

Статья:[[Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор]];
Выполняют: [[Участник:Trrufina|Третьякова Р.М.]] и [[Участник:Екатерина_Буторина|Буторина Е.В.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений2]];
Выполняет: [[Участник:Лукьянова Анна|Лукьянова А.Я.]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы]];
Выполняют: [[Участник: Galkina|Галкина А.С.]], [[Участник: Игорь|Плахов И.А.]]

Статья: [[Метод рекурсивной координатной бисекции]];
Выполняют: [[Участник: Obirvalger|Гордеев Михаил]], [[Участник: KolmakovEA|Колмаков Евгений]]

Статья: [[Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)]];
Выполняют: [[Участник: Эльвира Ахиярова|Ахиярова Эльвира]]

Статья: [[Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор]];
Выполняют: [[Участник: Janyell|Сычева Евгения]], [[Участник: Ahahalin|Хахалин Анатолий]]

Статья: [[Построение матрицы Адамара произвольного размера]];
Выполняют: [[Участник: Бугаков Юрий|Бугаков Юрий]], Кужамалиев Ернур

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки (1)]]
Выполняют: [[Участница:Sannikovats| Санникова Татьяна Сергеевна]], [[Участник:Plukshin| Лукшин Петр Андреевич]]

Статья: [[Алгоритм кластеризации, основанный на построении каркаса]];
Выполняют: [[Участник:SenderovichNikita| Сендерович Никита]]

Статья: [[Алгоритм кластеризации, основанный на максимизации ожидания]];
Выполняют: Готман Мария, Лукашкина Юлия

Статья: [[Partitioning_Around_Medoids_(PAM)]]
Выполняют: [[Участник:Avasilenko|А.Э.Василенко]], [[Участник:Anastasia|А.В.Тузикова]]

Статья: [[Нечеткий алгоритм С-средних (Fuzzy C-means)]]
Выполняют: [[Участник:Nikmedoed|Н.А. Муромцев]], [[Участник:illusive_mike|М.С. Дворецкий]]

Статья: [[Нечеткий алгоритм C средних]]
Выполняют: [[Участник:Gkhazeeva|Гелана Хазеева]], [[Участник:Yushin|Павел Юшин]]

Статья: [[Плотностный алгоритм кластеризации DBSCAN]]
Выполняют: [[Участник:Elena777mc|Малахова Е.С.]], [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]]

Статья: [[Кластеризация Partitioning Around Medoids (PAM)]]
Выполняют:[[ Участник:Тодуа Антон| Тодуа Антон]], [[Участник:Гусева Юлия| Гусева Юлия]]

Статья: [[Участник:Бугаков Юрий (613 группа), Кужамалиев Ернур (601 группа)/Построение матрицы Адамара произвольной размерности]]
Выполняют:[[ Участник:Бугаков Юрий| Бугаков Юрий]], [[Участник:Кужамалиев Ернур| Кужамалиев Ернур]]

Статья: [[Участник:Nikita/Построение_матрицы_Адамара|Построение матрицы Адамара]]
Выполняют: [[Участник:Nikita|Иванов Никита]], [[Участник:Tsyganov Nikita|Цыганов Никита]]

Статья: [[Метод Ньютона для решения систем нелинейных уравнений]]
Выполняют: [[Участник:Александр Чернышев|Александр Чернышев]], [[Участник:Захаров Никита|Захаров Никита]]

Статья: [[BIRCH|Сбалансированный итеративный алгоритм редукции и кластеризации с использованием иерархий
(BIRCH)]]
Выполняют: [[Участник:Светлана Морозова|Морозова Светлана]], [[Участник:Smirnov.maxim|Смирнов Максим]]

Статья: [[Плотностный_алгоритм_кластеризации|Плотностный_алгоритм_кластеризации]], Выполняют: [[Участник:Ramon93i7|Шемякин Роман]], [[Участник:Dadrik|Вашуров Илья]]

Статья: [[Алгоритм CLOPE кластеризации категориальных данных]].
Выполняют: [[Участник:Артем_Карпухин|Карпухин Артем]], [[Участник:Артем_Желтков|Желтков Артем]].

Статья: [[Участник:Борис/Алгоритм_Рунге-Кутты]]
Выполняет: [[Участник:Борис| Савков Борис]] и Степанов Евгений.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:04:08Z

Лиджиев Данир Владимирович: /* ЧАСТЬ. Литература */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

.

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

== Свойства алгоритма ==

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:03:39Z

Лиджиев Данир Владимирович: /* Существующие реализации алгоритма */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:27:39Z

Лиджиев Данир Владимирович: /* Локальность данных и вычислений */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:27:25Z

Лиджиев Данир Владимирович: /* ЧАСТЬ. Свойства и структура алгоритмов */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:21:06Z

Лиджиев Данир Владимирович: /* = Общее описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Свойства и структура алгоритмов =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:20:45Z

Лиджиев Данир Владимирович: /* ЧАСТЬ. Программная реализация алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма =

== Математическое описание алгоритма ==

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:16:50Z

Лиджиев Данир Владимирович: /* Общее описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:15:56Z

Лиджиев Данир Владимирович: /* Схема реализации последовательного алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

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

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:14:45Z

Лиджиев Данир Владимирович: /* Макроструктура алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

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

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:14:27Z

Лиджиев Данир Владимирович: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==

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

== Математическое описание алгоритма ==

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

Последовательные алгоритмы

Метод трапеций

Метод рекурсивного деления

Метод локального стека

== Схема реализации последовательного алгоритма ==

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-11T21:09:32Z

Лиджиев Данир Владимирович: /* ЧАСТЬ. Свойства и структура алгоритмов */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-11T17:40:38Z

Лиджиев Данир Владимирович: /* ЧАСТЬ. Свойства и структура алгоритмов */

= ЧАСТЬ. Свойства и структура алгоритмов =
Свойства

== Общее описание алгоритма ==

== Математическое описание алгоритма ==

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

== Существующие реализации алгоритма ==