Слайд 2 ВЫЧИСЛЕНИЕ ОПРЕДЕЛЕННОГО ИНТЕГРАЛА
![ВЫЧИСЛЕНИЕ ОПРЕДЕЛЕННОГО ИНТЕГРАЛА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-1.jpg)
Слайд 4Последовательность выполнения
Последовательная версия.
Базовая реализация алгоритма интегрирования
Эффект применения компилятора
Использование предварительных
![Последовательность выполнения Последовательная версия. Базовая реализация алгоритма интегрирования Эффект применения компилятора Использование](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-3.jpg)
вычислений сложных функций
Алгоритмическая оптимизация
Параллельная версия.
Варианты распараллеливание базового алгоритма
Распараллеливание оптимизированного алгоритма
Слайд 5Базовый алгоритм
Должен содержать код, несколько раз запускающий тестируемую реализацию алгоритма вычислений.
Должен вычислять
![Базовый алгоритм Должен содержать код, несколько раз запускающий тестируемую реализацию алгоритма вычислений.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-4.jpg)
минимальное, максимальное и среднее времена ее работы.
Должен представлять результаты вычислений.
Параметры вычислений задаются в программе.
Провести анализ использования разных режимов компиляции.
Слайд 6Распараллеливание базового алгоритма
Геометрическая декомпозиция данных (разделение данных на части и применение к
![Распараллеливание базового алгоритма Геометрическая декомпозиция данных (разделение данных на части и применение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-5.jpg)
ним одного и того же алгоритма).
Локализация данных.
Анализ результатов (гонка данных).
Слайд 7Геометрическая декомпозиция данных
По столбцам
По строкам
Блочно
1
2
3
![Геометрическая декомпозиция данных По столбцам По строкам Блочно 1 2 3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-6.jpg)
Слайд 8Оптимизация базового алгоритма
Предварительное вычисление сложных математических функций (sin, cos, exp и др.).
Алгоритмическая
![Оптимизация базового алгоритма Предварительное вычисление сложных математических функций (sin, cos, exp и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-7.jpg)
оптимизация (исключение многократного вычисления одних и тех же данных, предварительные расчеты).
Буферизация.
Слайд 9Распараллеливание оптимизированного алгоритма
Распараллеливание с учетом уже полученных результатов:
В данной задаче наилучшие результаты
![Распараллеливание оптимизированного алгоритма Распараллеливание с учетом уже полученных результатов: В данной задаче](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-8.jpg)
дает распараллеливание с разделением сетки интегрирования по столбцам (внешний цикл).
Распараллелить основные вычислительные циклы.
Слайд 11Структура программы
main()
experiment()
integral()
![Структура программы main() experiment() integral()](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-10.jpg)
Слайд 12 Пример выполнения вычислений
Базовый алгоритм
![Пример выполнения вычислений Базовый алгоритм](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-11.jpg)
Слайд 13Основная программа
int main () {
int i;
double time, res, min_time, max_time,
![Основная программа int main () { int i; double time, res, min_time,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-12.jpg)
avg_time;
int numbExp = 10;
min_time = max_time = avg_time = experiment(&res);
for(i = 0; i < numbExp - 1; i ++) {
time = experiment(&res);
avg_time += time;
if(max_time < time) max_time = time;
if(min_time > time) min_time = time; }
printf(“Интеграл равен: %lf; \n", res);
printf(«Время выполнения: %lf; %lf; %lf \n",
avg_time / numbExp, min_time, max_time);
return 0;
}
Слайд 14Функция experiment
double experiment(double *res)
{
double stime, ftime;
double a1 = 0.0
![Функция experiment double experiment(double *res) { double stime, ftime; double a1 =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-13.jpg)
;
double a1 = a2 = 0.0 ;
double b1 = 16.0;
double b2 = 16.0;
double h = 0.001;
stime = omp_get_wtime( );
integral(a1, b1, a2, b2, h, res);
ftime = omp_get_wtime( );
return (ftime - stime);
}
Слайд 15Функция integral
void integral(const double a1, const double b1,
const double a2, const double
![Функция integral void integral(const double a1, const double b1, const double a2,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-14.jpg)
b2, const double h,
double *res){
int i, j, n1, n2; double sum, x, y;
n1 = (int)((b1 - a1) / h); n2 = (int)((b2 - a2) / h);
sum = 0.0;
for( i = 0; i < n1; i++) {
for(j = 0; j < n2; j++) {
x = a1 + i * h + h / 2;
y = a2 + j * h + h / 2;
sum += ((exp(sin(x * PI) * cos(y * PI)) + 1) / ((b1 - a1) * (b2 - a2))) * h * h; } }
*res = sum;
}
Слайд 16 Пример выполнения вычислений
Базовый алгоритм - распараллеливание
![Пример выполнения вычислений Базовый алгоритм - распараллеливание](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-15.jpg)
Слайд 17Распараллеливание по столбцам
#pragma omp parallel for
for(i = 0; i < n1;
![Распараллеливание по столбцам #pragma omp parallel for for(i = 0; i {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-16.jpg)
i++)
{
for(j = 0; j < n2; j++)
{
x = a1 + i * h + h / 2;
y = a2 + j * h + h / 2;
sum += ((exp(sin(x * PI) * cos(y * PI)) + 1) / ((b1 - a1) *
(b2 - a2))) * h * h;
}
}
Слайд 18Распараллеливание по столбцам с учетом data race
#pragma omp parallel for private (x, y,
![Распараллеливание по столбцам с учетом data race #pragma omp parallel for private](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-17.jpg)
j)
reduction(+: sum)
for(i = 0; i < n1; i++)
{
for(j = 0; j < n2; j++)
{
x = a1 + i * h + h / 2;
y = a2 + j * h + h / 2;
sum += ((exp(sin(x * PI) * cos(y * PI)) + 1) / ((b1 - a1) *
(b2 - a2))) * h * h;
}
}
Слайд 19Распараллеливание по строкам
for(i = 0; i < n1; i++)
{
#pragma
![Распараллеливание по строкам for(i = 0; i { #pragma omp parallel for](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-18.jpg)
omp parallel for private (x, y)
reduction(+: sum)
for(j = 0; j < n2; j++)
{
x = a1 + i * h + h / 2;
y = a2 + j * h + h / 2;
sum += ((exp(sin(x * PI) * cos(y * PI)) + 1) / ((b1 - a1) *
(b2 - a2))) * h * h;
}
}
Слайд 20Блочное разделение данных
omp_set_nested(true);
#pragma omp parallel for
for (i = 0; i <
![Блочное разделение данных omp_set_nested(true); #pragma omp parallel for for (i = 0;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-19.jpg)
n1; i++)
{
#pragma omp parallel for private (x, y)
reduction(+: sum)
for(j = 0; j < n2; j++)
{
x = a1 + i * h + h / 2;
y = a2 + j * h + h / 2;
sum += ((exp(sin(x * PI) * cos(y * PI)) + 1) /
((b1 - a1) * (b2 - a2))) * h * h;
}
}
Слайд 22Влияние параметров распараллеливания циклов
![Влияние параметров распараллеливания циклов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-21.jpg)
Слайд 23 Пример выполнения вычислений
Оптимизированный алгоритм –
распараллеливание
![Пример выполнения вычислений Оптимизированный алгоритм – распараллеливание](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-22.jpg)
Слайд 24Использование предварительных вычислений сложных функций
void integral(const double a1, const double b1,
const
![Использование предварительных вычислений сложных функций void integral(const double a1, const double b1,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-23.jpg)
double a2, const double b2, const double h, double *res) { int i, j, n1, n2; double sum, x, y, *sinx, *cosy; n1 = (int)((b1 - a1) / h);
n2 = (int)((b2 - a2) / h); sum = 0.0;
sinx = new double [n1]; cosy = new double [n2];
for(i = 0; i < n1; i++)
{ x = a1 + i * h + h / 2; sinx[i] = sin(x * PI); }
for(j = 0; j < n2; j++)
{ y = a2 + j * h + h / 2; cosy[j] = cos(y * PI); }
for(i = 0; i < n1; i++)
{ for(j = 0; j < n2; j++) {sum += ((exp(sinx[i] * cosy[j]) + 1) / ((b1 - a1) * (b2 - a2))) * h * h; } } *res = sum;
delete [] sinx; delete [] cosy; }
Слайд 26Загрузка ядер процессора
Последовательный алгоритм
Оптимизированный параллельный алгоритм
Параллельный алгоритм
![Загрузка ядер процессора Последовательный алгоритм Оптимизированный параллельный алгоритм Параллельный алгоритм](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-25.jpg)
Слайд 27 Пример выполнения вычислений
Вычисление интеграла методом Монте-Карло
![Пример выполнения вычислений Вычисление интеграла методом Монте-Карло](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-26.jpg)
Слайд 29Функция integral
void integral(const double a1, const double b1, const double a2, const
![Функция integral void integral(const double a1, const double b1, const double a2,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/951501/slide-28.jpg)
double b2, const double h, double *res) {
int n=0; double sum, x, y, f;
for(long int i=1;i<= nMax;i++) { x=abs((double)(rand()%((int)(b1 - a1)*Mrand))) /Mrand;
y=abs((double)(rand()% ((int)(b2 - a2)*Mrand)))/Mrand;
f=abs((double)(rand()% ((int)(Fmax*Mrand))))/Mrand;
if(func(x+a1, y+a2, a1, b1, a2, b2) <= f) n++; }
sum=(b1 - a1)*(b2 - a2)*(Fmax)*n/nMax;
*res = sum;
}