/*
CPP_CONTEST=2015
CPP_PROBLEM=C
CPP_LANG=CPP+OPENMP
CPP_PROCESSES_PER_NODE=jupiter 1
*/
#include
#include
#include
#include
#include
#include
/* RECORD January 25, 2017
Francisco Muñoz Martínez
student of Methodology of Parallel Programming,
University of Murcia
time 65 msec
speed-up 461.54
*/
/* The main idea consists of reducing in an order the executing time of the algorithm. In the original, for each element in matrix A (i, j), the code
adds all the elements in the rectangular matrix, giving for each position of A an execution time of R[i, j]*C[i, j] which it may be even until N*M. With my implementation, for each element in matrix A, the code only has to add R[i,j] elements in the rectangular matrix.
To getting this fact, i have used another matrix "sumas" which contains the accumulated additions of the rows. In this way, the value of the position i, j in matrix "sumas" is the next:
sumas[i, 0]=A[i,0] | i=[0 to N]
sumas[i, j] = sumas[i, j-1] | i=[0 to N] and j=[1 to M]
With this matrix, i do not need to add all the elements in a rectangular matrix because the rows has already been add (sumas[i,j]). So that, the code only has to add R[i,j] elements in matrix "sumas".
Obviusly at first, i have to calculate the matrix "sumas" but it is a time of N*M, so it is not a problem.
*/
using namespace std;
void escribirsubmatrix(int n,int m,int ld,double *a){
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
cout << setiosflags(ios::fixed) << setprecision(4) <0) {
s-=sumas[k*M + (j-1)];
}
}
return s;
}
void sec(int N, int M, int *R, int *C, double *A)
{
double* sumas = new double[N*M]; /* This is the matrix which contains the accumulate additions. */
#pragma omp parallel /* */
{
#pragma omp for /* The work of adding the accumulate additions is done by all the threads. This work is statically partitioned */
for(int i=0; i=N and lc=M) //the rows go outside the matrix, but the columns do not
{
sum+=sumsubmatrix(N, M, i, j, lr, M-1, sumas);
sum+=sumsubmatrix(N, M, i, 0, lr, lc%M, sumas);
}
else
{
sum+=sumsubmatrix(N, M, i, j, N-1, M-1, sumas);
sum+=sumsubmatrix(N, M, 0, j, lr%N, M-1, sumas);
sum+=sumsubmatrix(N, M, i, 0, N-1, lr%M, sumas);
sum+=sumsubmatrix(N, M, 0, 0, lr%N, lr%M, sumas);
//sum+=sumsubmatrix(N-i,M-j,M,&A[i*M+j]);
//sum+=sumsubmatrix(lr%N+1,M-j,M,&A[j]); //the upper matrix obtained cyclically
//sum+=sumsubmatrix(N-i,lr%M+1,M,&A[i*M]); //the left matrix obtained cyclically
//sum+=sumsubmatrix(lr%N+1,lr%M+1,M,A); //the upper-left matrix obtained cyclically
}
A[i*M+j]=sum;
}
}
delete[] sumas;
}