StudyDocs.ru Logo

Otchet_o_laboratornoy_rabote_2.docx


Листинг кода программы#include <math.h>#include <stdlib.h>#include <stdio.h>#include <time.h>#include<conio.h>#include <malloc.h>#include<omp.h>#define Max(a,b) ((a)>(b)?(a):(b))//#define N 139double maxeps = 0.1e-7;int itmax;int i, j, k;double eps;double* A;double* B;int do_it = 1;int N;int processor_amount;void relax();void resid();void init();void verify();int get_value();//void wtime();int main(){ int it,thread_number; clock_t time0, time1; printf("Input itmax\n"); itmax = get_value(); printf("Input processor amount\n"); processor_amount = get_value(); printf("Input N - array size\n"); N= get_value(); if ((itmax >= 0) && (processor_amount >= 0) && (N >= 0)) { init(); if (do_it == 1) { time0 = clock(); /* time0=omp_get_wtime (); */ //wtime(&time0);#pragma omp parallel num_threads(processor_amount) {#pragma omp for schedule(dynamic) for (it = 1; it <= itmax; it++) { eps = 0.; relax(); resid(); printf("it=%4i eps=%f\n", it, eps); thread_number = omp_get_thread_num(); printf("Working_thread_number: %d\n\n", thread_number); if (eps < maxeps) break; } } time1 = clock(); //wtime(&time1); /* time1=omp_get_wtime (); */ printf("Time in seconds=%d\t", (time1 - time0) / CLOCKS_PER_SEC); verify(); free(A); free(B); } } _getche(); return 0;}void init(){ A = malloc(N*N*N*sizeof(double)); B = malloc(N*N*N*sizeof(double)); printf("Memory need:%d Bytes\n", 2*N*N*N*sizeof(double)); if ((A != NULL) && (B != NULL)) {//#pragma omp parallel num_threads(1) //{//#pragma omp for for (i = 0; i <= N - 1; i++) for (j = 0; j <= N - 1; j++) for (k = 0; k <= N - 1; k++) { if (i == 0 || i == N - 1 || j == 0 || j == N - 1 || k == 0 || k == N - 1) A[i*N*N + j*N + k] = 0.; else A[i*N*N + j*N + k] = (4. + i + j + k); } //} } else { printf("There is not enough memory for arrays A and B"); do_it = 0; }}void relax(){//#pragma omp parallel num_threads(1)//{//#pragma omp for schedule(static, processor_amount) for (i = 1; i <= N - 2; i++) for (j = 1; j <= N - 2; j++) for (k = 1; k <= N - 2; k++) { B[i*N*N + j*N + k] = (A[(i - 1)*N*N + j*N + k] + A[(i + 1)*N*N + j*N + k] + A[i*N*N + (j - 1)*N + k] + A[i*N*N + (j + 1)*N + k] + A[i*N*N + j*N + k - 1] + A[i*N*N + j*N + k + 1]) / 6.; }//}}void resid(){ int thread;///#pragma omp parallel num_threads(1)//{//#pragma omp for schedule(static, processor_amount) for (i = 1; i <= N - 2; i++) for (j = 1; j <= N - 2; j++) for (k = 1; k <= N - 2; k++) { double e; e = fabs(A[i*N*N + j*N + k] - B[i*N*N + j*N + k]); A[i*N*N + j*N + k] = B[i*N*N + j*N + k]; eps = Max(eps, e); }//}}void verify(){ double s; s = 0.;//#pragma omp parallel reduction(+:s) num_threads(1) //{//#pragma omp for for (i = 0; i <= N - 1; i++) for (j = 0; j <= N - 1; j++) for (k = 0; k <= N - 1; k++) { s = s + A[i*N*N + j*N + k] * (i + 1)*(j + 1)*(k + 1) / (N*N*N); } //} printf(" S = %f\n", s);}/*void wtime(double *t){ static int sec = -1; struct timeval tv; gettimeofday(&tv, (void *)0); if (sec < 0) sec = tv.tv_sec; *t = (tv.tv_sec - sec) + 1.0e-6*tv.tv_usec;}*/int get_value(){ char ch = 'a'; int a = 0; while (ch != '\n') { ch = getchar(); if (((ch >= '0') && (ch <= '9')) || (ch == '\n')) { if ((ch >= '0') && (ch <= '9')) a = a * 10 + (ch - '0'); } else { printf("error"); goto towards_end; } } return a;towards_end: return -1000;}Проблемы и сложности, возникшие при выполнении данной работыВ приведённом в техническом задании коде алгоритма используются статические массивы, что не позволяет создать массив большого размера (так как память под статические массивы выделяется на стеке, размер которого очень ограничен), поэтому в своём коде (см. листинг) я использовал динамические массивы (память под которые выделяется в куче).Компилировать код лучше под x64, так как под x86 операционная система может адресовать только 4 ГБ (гигабайта) оперативной памяти, из которых под прикладные программы можно использовать только 2 ГБ, независимо от объёма физической оперативной памяти. Перед запуском программы откройте диспетчер задач (рис.1) и посмотрите, сколько оперативной памяти свободно на данный момент. Выбирать размер массива надо так, чтобы удвоенное количество памяти (так как в программе используется 2 массива) не превышало объём свободной физической оперативной памяти. В противном случае компьютер зависнет.
Рис. 1. Диспетчер задачДля того, чтобы избежать трудностей с использованием тройных указателей, трёхмерные массивы были пересчитаны в одномерные по формулеВ некоторых Visual Studio не разрешается использование scanf, поэтому пришлось реализовать и использовать вспомогательную функцию get_value. Безопасной она также не является.Таймер также пришлось переделать, отказавшись от предложенной в техническом задании (начальной реализации) функции wtime и записав вредя до начала и после выполнения алгоритма в переменные time0, time1; типа clock_t и вывести время в секундах строчкой printf("Time in seconds=%d\t", (time1 - time0) / CLOCKS_PER_SEC);Распараллелить удалось только цикл for в main. Попытки распараллелить циклы в функциях relax и resid приводили к замедлению работы программыВременная сложность и стоимостьВ данной реализации алгоритма в процедурах relax и resid имеется по 3 цикла, поэтому стоимость алгоритма -, соответственно временная сложность - , где p – число задействованных процессоров. Поясню, сто означает словосочетание «число задействованных процессоров». Пусть, к примеру, у вас 2 логических ядра. Если программа работает в один поток, то исполнять её будет только одно ядро, независимо от того, сколько их – четыре, восемь или больше. Если программу распараллелить на 2 потока, то у двухъядерного процессора её будет исполнять два ядра, у четырёхъядерного по прежнему 2. Прирост скорости будет примерно в 2 раза. Но при распараллеливании на 3 потока на двухъядерном процессоре получится или увеличение времени работы, или оно останется прежним, так как всё равно будут задействованы 2 логических процессора. На четырёхъядерном получится сокращение времени работы, так как будут задействованы 3 процессора.Вычислительный эксперимент Таблица №1

NitmaxПоследовательный алгоритм, время с. Параллельный алгоритм
1 ядро2 ядра
Время с.УскорениеВремя с.Ускорение
13913002524+4%13+48%
17113004645+2,2%26+44%
203130075750%49+35%
2351300117116+0,8%82+30%
2671300172176-2,3%129+25%
Замечание: не везде ускорение для 2 – х ядер равно 50%. Это может быть связано с аппаратными особенностями ЭВМ, например, технология HyperThreading, которая заставляет работать одно физическое ядро как 2 логических. В результате производительность увеличивается не в 2 раза, а, к примеру, в 1,5 раза.