diff --git a/CG_Parallel/CG_Parallel.cpp b/CG_Parallel/CG_Parallel.cpp index 6e4f8d6..ed0c036 100644 --- a/CG_Parallel/CG_Parallel.cpp +++ b/CG_Parallel/CG_Parallel.cpp @@ -1,209 +1,248 @@ // // Created by shernand on 29/05/19. // /** * @file CG_Serial.cpp * @author Sergio Hernandez * This file is part of the Conjugate Gradient Project * * This class implements the parallel version of the Conjugate Gradient * */ #include #include #include #include +#include #include "CG_Parallel.hpp" /** * Complete constructor of the CG solver. * @param matrixA std::vector NxN symmetric definite positive * @param vectorB Nx1 std::vector right side vector * @param tol double Tolerance for our stopping criterion * @param maxIter int Maximum number of iterations of the stopping criterion */ CG_Parallel::CG_Parallel(std::vector const &matrixA, std::vector const &vectorB, double const &tol, int const &maxIter) { setMatrixA(matrixA); setVectorB(vectorB); setTol(tol); setMaxIterations(maxIter); - std::vector timings(3,0.0); } /** * Computes the CG solver * @param x_0 Nx1 std::vecotr the initial guess for the solution * @return std::tuple x, int n_iterations> The tuple ,int> CG_Parallel::computeCG(std::vector &x_0) { +void CG_Parallel::computeCG(std::vector &x_0) { + int size,rank; + MPI_Comm_size(MPI_COMM_WORLD, &size); + MPI_Comm_rank(MPI_COMM_WORLD, &rank); std::vector b = getVectorB(); std::vector mA = getMatrixA(); int max_iter = getMaxIterations(); double tol = getTol(); std::vector x_k = x_0; std::vector r_k = matrixVector(mA,x_k); r_k = vectorScalarMul(r_k,-1.0); r_k = vectorVectorSum(b,r_k); std::vector d_k = r_k; double norm_res = vectorVectorDot(r_k,r_k); int k = 0; while ((norm_res>tol)&&(k A_dk = matrixVector(mA,d_k); double dk_A_dk = vectorVectorDot(d_k,A_dk); double alpha_k = norm_res/dk_A_dk; x_k = vectorVectorSum(x_k,vectorScalarMul(d_k,alpha_k)); A_dk = vectorScalarMul(A_dk,-alpha_k); r_k= vectorVectorSum(r_k,A_dk); double norm_r_k_1 = vectorVectorDot(r_k,r_k); double beta_k_1 = norm_r_k_1/norm_res; d_k = vectorVectorSum(r_k,vectorScalarMul(d_k,beta_k_1)); norm_res=norm_r_k_1; k+=1; } - return std::make_tuple(x_k,k); + if(rank==0) { + setSolution(x_k); + setNIterations(k); + } +} +/** + * Saves the solution vector, and the number of iterations into a file. + * @param vector + * @param n_iterations + * @param filename + */ +void CG_Parallel::saveVector(std::string &filename){ + std::ofstream myfile; + std::vector vector = getSolution(); + int n_iterations = getNIterations(); + int n = vector.size(); + //Opens the file + myfile.open (filename); + myfile << n_iterations<<"\n"; + for(int i=0;i * @param pScalar double * @return mul_vector Nx1 std::vector mult element wise of the scalar and the vector */ std::vector CG_Parallel::vectorScalarMul(const std::vector &pVector1, const double pScalar) { int size,rank; MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); int n = pVector1.size(); int batchSize = n / size; std::vector mul_vector(n,0.0); std::vector subVec1(batchSize, 0.0); std::vector subMul(batchSize, 0.0); double scalar = pScalar; MPI_Bcast(&scalar, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Scatter(pVector1.data(), batchSize, MPI_DOUBLE, subVec1.data(), batchSize, MPI_DOUBLE, 0, MPI_COMM_WORLD); for(int i=0;i * @param pVector2 Nx1 std::vector * @return sum_vector Nx1 std::vector sum element wise of the two vectors */ std::vector CG_Parallel::vectorVectorSum(const std::vector &pVector1, const std::vector pVector2) { int size,rank; MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); int n = pVector1.size(); std::vector sum_vector(n,0.0); int batchSize = n / size; //Should manage the offset if n is not exactly divisible bz size. // if (n % size) { // batchSize++; //} std::vector subVec1(batchSize, 0.0); std::vector subVec2(batchSize, 0.0); std::vector subSum(batchSize, 0.0); MPI_Scatter(pVector1.data(), batchSize, MPI_DOUBLE, subVec1.data(), batchSize, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Scatter(pVector2.data(), batchSize, MPI_DOUBLE, subVec2.data(), batchSize, MPI_DOUBLE, 0, MPI_COMM_WORLD); for (int i = 0;i * @param pVector2 Nx1 std::vector * @return double the resulting dot product */ double CG_Parallel::vectorVectorDot(const std::vector &pVector1, const std::vector pVector2) { int size, rank; MPI_Status status; MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); int const batchSize = pVector1.size()/size; std::vector subVec1(batchSize, 0.0); std::vector subVec2(batchSize, 0.0); MPI_Scatter(pVector1.data(), batchSize, MPI_DOUBLE, subVec1.data(), batchSize, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Scatter(pVector2.data(), batchSize, MPI_DOUBLE, subVec2.data(), batchSize, MPI_DOUBLE, 0, MPI_COMM_WORLD); double partial_dot_product = 0.0; double total_dot_product = 0.0; for (int i=0;i * @param pVector Nx1 vector std::vector * @return prod_vecotr Nx1 std::vector */ std::vector CG_Parallel::matrixVector(const std::vector &pMatrix, const std::vector pVector) { int size, rank; MPI_Status status; MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); int n = pVector.size(); int nRows = n/size; std::vector vector =pVector; MPI_Bcast(vector.data(), n, MPI_DOUBLE, 0, MPI_COMM_WORLD); std::vector subMatrix(n*nRows,0.0); MPI_Scatter(pMatrix.data(), n*nRows, MPI_DOUBLE, subMatrix.data(), n*nRows, MPI_DOUBLE, 0, MPI_COMM_WORLD); std::vector prod_vector(n,0.0); std::vector subProd(nRows, 0.0); for(int i=0;i &CG_Parallel::getMatrixA() const { return matrixA; } void CG_Parallel::setMatrixA(const std::vector &matrixA) { CG_Parallel::matrixA = matrixA; } const std::vector &CG_Parallel::getVectorB() const { return vectorB; } void CG_Parallel::setVectorB(const std::vector &vectorB) { CG_Parallel::vectorB = vectorB; } double CG_Parallel::getTol() const { return tol; } void CG_Parallel::setTol(double tol) { CG_Parallel::tol = tol; } int CG_Parallel::getMaxIterations() const { return max_iterations; } void CG_Parallel::setMaxIterations(int maxIterations) { max_iterations = maxIterations; } +const std::vector &CG_Parallel::getSolution() const { + return vectorSolution; +} + +void CG_Parallel::setSolution(const std::vector &vectorSolution) { + CG_Parallel::vectorSolution = vectorSolution; +} +int CG_Parallel::getNIterations() const { + return n_iterations; +} + +void CG_Parallel::setNIterations(int nIterations) { + n_iterations = nIterations; +} \ No newline at end of file diff --git a/CG_Parallel/CG_Parallel.hpp b/CG_Parallel/CG_Parallel.hpp index 685c50a..9ab91e6 100644 --- a/CG_Parallel/CG_Parallel.hpp +++ b/CG_Parallel/CG_Parallel.hpp @@ -1,45 +1,52 @@ // // Created by shernand on 29/05/19. // /** * @file CG_Serial.hpp * @author Sergio Hernandez * This file is part of the Conjugate Gradient Project * * This class implements the parallel version of the Conjugate Gradient * */ #ifndef CG_SERIAL_CG_PARALLEL_HPP #define CG_SERIAL_CG_PARALLEL_HPP #include #include #include class CG_Parallel { public: CG_Parallel(std::vector const &matrixA, std::vector const &vectorB, double const &tol, int const &maxIter); - std::tuple,int> computeCG(std::vector &x_0); + void computeCG(std::vector &x_0); std::vector vectorScalarMul(const std::vector &pVector1, const double pScalar); std::vector vectorVectorSum(const std::vector &pVector1, const std::vector pVector2); double vectorVectorDot(const std::vector &pVector1, const std::vector pVector2); std::vector matrixVector(const std::vector &pMatrix, const std::vector pVector); + void saveVector(std::string &filename); //Getter and Setters methods const std::vector &getMatrixA() const; void setMatrixA(const std::vector &matrixA); const std::vector &getVectorB() const; void setVectorB(const std::vector &vectorB); + const std::vector &getSolution() const; + void setSolution(const std::vector &vectorSolution); double getTol() const; void setTol(double tol); int getMaxIterations() const; void setMaxIterations(int maxIterations); - + int getNIterations() const; + void setNIterations(int nIterations); private: std::vectormatrixA; std::vectorvectorB; + std::vectorvectorSolution; double tol; int max_iterations; + int n_iterations; + }; #endif //CG_SERIAL_CG_PARALLEL_HPP diff --git a/CG_Parallel/main.cpp b/CG_Parallel/main.cpp index f778e48..4d25f31 100644 --- a/CG_Parallel/main.cpp +++ b/CG_Parallel/main.cpp @@ -1,147 +1,131 @@ /** * @file main.cpp * @author Sergio Hernandez * This file is part of the Conjugate Gradient Project * * Ths is the entry point of the project. * */ #include #include #include "CG_Parallel.hpp" #include #include "ConfigFileParser.hpp" #include /** * Constant to inform the user the correct usage of the program in case of a misuse. */ #define USAGE "Please enter correctly one argument (a config file). Example: ./CG_Parallel configFile.txt" /** * Constant which defines the correct number of arguments the program can receive. */ #define N_ARGS 2 int main(int argc, char* argv[]) { MPI_Init(&argc, &argv); int rank, size; MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); if(argc!=N_ARGS){ std::cout< A;//Filled with 0.0 std::vector b;//Filled with 1.0 std::string fName = argv[1]; ConfigFileParser parser = ConfigFileParser(); parser.parseFile(fName); parser.verify(); std::cout << "Finished parsing the file " << std::endl; //This could be an executer std::map data = parser.getData(); //Size of the matrix std::string tempKey = "N"; N = stoi(data[tempKey]); std::cout << " N = " << N << std::endl; //Tolerance tempKey = "tol"; tol = stof(data[tempKey]); std::cout << " tol = " << tol << std::endl; //max iterations tempKey = "max_iter"; max_iter = stoi(data[tempKey]); std::cout << " max_iter = " << max_iter << std::endl; //type input tempKey = "type_input"; type_input = data[tempKey]; //number_outputs tempKey = "number_outputs"; number_outputs = stoi(data[tempKey]); tempKey = "type_output"; type_output = data[tempKey]; tempKey = "outputFile"; outputFile = data[tempKey]; if (type_input=="tridiagonal") { std::cout<<"Matrix A is: "< 0) { A[i + N * j] = 1.0; //Downer } } if (j == i) { A[i + N * j] = -2.0; //Main diagonal } } } } else if(type_input=="hilbert"){ A.resize(N*N);//Fills it with 0s. b.resize(N,1.0);//Fills it with 0s. std::fill(b.begin(), b.end(), 1);//Fills it with 1s. for(int i=0;i x_0 (N,0.0); std::cout<< "Preparing to solve"<,int> result = solver.computeCG(x_0); - std::vector x = std::get<0>(result); - int k = std::get<1>(result); + std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); + solver.computeCG(x_0); if(rank==0){ - std::chrono::high_resolution_clock::time_point t3 = std::chrono::high_resolution_clock::now();//calculating the final exection time - std::chrono::duration time_span_1 = std::chrono::duration_cast>(t2 - t1); - std::chrono::duration time_span_2 = std::chrono::duration_cast>(t3 - t2); - std::cout << "Initialization Time : "< time_span_1 = std::chrono::duration_cast>(t2 - t1); + std::chrono::duration time_span_2 = std::chrono::duration_cast>(t3 - t2); + std::cout << "Initialization Time : "< +#include #include "CG_Serial.hpp" /** * Complete constructor of the CG solver. * @param matrixA std::vector NxN symmetric definite positive * @param vectorB Nx1 std::vector right side vector * @param tol double Tolerance for our stopping criterion * @param maxIter int Maximum number of iterations of the stopping criterion */ CG_Serial::CG_Serial(std::vector const &matrixA, std::vector const &vectorB, double const &tol, int const &maxIter) { setMatrixA(matrixA); setVectorB(vectorB); setTol(tol); setMaxIterations(maxIter); } /** * Computes the CG solver * @param x_0 Nx1 std::vecotr the initial guess for the solution * @return std::tuple x, int n_iterations> The tuple ,int> CG_Serial::computeCG(std::vector &x_0) { +void CG_Serial::computeCG(std::vector &x_0) { std::vector b = getVectorB(); std::vector mA = getMatrixA(); int max_iter = getMaxIterations(); double tol = getTol(); std::vector x_k = x_0; std::vector r_k = matrixVector(mA,x_k); r_k = vectorScalarMul(r_k,-1.0); r_k = vectorVectorSum(b,r_k); std::vector d_k = r_k; double norm_res = vectorVectorDot(r_k,r_k); int k = 0; while ((norm_res>tol)&&(k A_dk = matrixVector(mA,d_k); double dk_A_dk = vectorVectorDot(d_k,A_dk); double alpha_k = norm_res/dk_A_dk; x_k = vectorVectorSum(x_k,vectorScalarMul(d_k,alpha_k)); A_dk = vectorScalarMul(A_dk,-alpha_k); r_k= vectorVectorSum(r_k,A_dk); double norm_r_k_1 = vectorVectorDot(r_k,r_k); double beta_k_1 = norm_r_k_1/norm_res; d_k = vectorVectorSum(r_k,vectorScalarMul(d_k,beta_k_1)); norm_res=norm_r_k_1; k+=1; } - return std::make_tuple(x_k,k); + setSolution(x_k); + setNIterations(k); +} +/** + * Saves the solution vector, and the number of iterations into a file. + * @param vector + * @param n_iterations + * @param filename + */ +void CG_Serial::saveVector(std::string &filename){ + std::ofstream myfile; + std::vector vector = getSolution(); + int n_iterations = getNIterations(); + int n = vector.size(); + //Opens the file + myfile.open (filename); + myfile << n_iterations<<"\n"; + for(int i=0;i * @param pScalar double * @return mul_vector Nx1 std::vector mult element wise of the scalar and the vector */ std::vector CG_Serial::vectorScalarMul(const std::vector &pVector1, const double pScalar) { std::vector mul_vector = pVector1; for(int i=0;i * @param pVector2 Nx1 std::vector * @return sum_vector Nx1 std::vector sum element wise of the two vectors */ std::vector CG_Serial::vectorVectorSum(const std::vector &pVector1, const std::vector pVector2) { std::vector sum_vector = pVector1; for(int i=0;i * @param pVector2 Nx1 std::vector * @return double the resulting dot product */ double CG_Serial::vectorVectorDot(const std::vector &pVector1, const std::vector pVector2) { double dot_product = 0; for(int i=0;i * @param pVector Nx1 vector std::vector * @return prod_vecotr Nx1 std::vector */ std::vector CG_Serial::matrixVector(const std::vector &pMatrix, const std::vector pVector) { std::vector prod_vector = pVector; for(int i=0;i &CG_Serial::getMatrixA() const { return matrixA; } void CG_Serial::setMatrixA(const std::vector &matrixA) { CG_Serial::matrixA = matrixA; } const std::vector &CG_Serial::getVectorB() const { return vectorB; } void CG_Serial::setVectorB(const std::vector &vectorB) { CG_Serial::vectorB = vectorB; } double CG_Serial::getTol() const { return tol; } void CG_Serial::setTol(double tol) { CG_Serial::tol = tol; } int CG_Serial::getMaxIterations() const { return max_iterations; } void CG_Serial::setMaxIterations(int maxIterations) { max_iterations = maxIterations; } +int CG_Serial::getNIterations() const { + return n_iterations; +} + +void CG_Serial::setNIterations(int nIterations) { + n_iterations = nIterations; +} +const std::vector &CG_Serial::getSolution() const { + return vectorSolution; +} + +void CG_Serial::setSolution(const std::vector &vectorSolution) { + CG_Serial::vectorSolution = vectorSolution; +} \ No newline at end of file diff --git a/CG_Serial/CG_Serial.hpp b/CG_Serial/CG_Serial.hpp index c0bb9c6..62508ec 100644 --- a/CG_Serial/CG_Serial.hpp +++ b/CG_Serial/CG_Serial.hpp @@ -1,45 +1,52 @@ // // Created by shernand on 29/05/19. // /** * @file CG_Serial.hpp * @author Sergio Hernandez * This file is part of the Conjugate Gradient Project * * This class implements the serial version of the Conjugate Gradient * */ #ifndef CG_SERIAL_CG_SERIAL_HPP #define CG_SERIAL_CG_SERIAL_HPP #include #include #include class CG_Serial { public: CG_Serial(std::vector const &matrixA, std::vector const &vectorB, double const &tol, int const &maxIter); - std::tuple,int> computeCG(std::vector &x_0); + void computeCG(std::vector &x_0); std::vector vectorScalarMul(const std::vector &pVector1, const double pScalar); std::vector vectorVectorSum(const std::vector &pVector1, const std::vector pVector2); double vectorVectorDot(const std::vector &pVector1, const std::vector pVector2); std::vector matrixVector(const std::vector &pMatrix, const std::vector pVector); + void saveVector(std::string &filename); //Getter and Setters methods const std::vector &getMatrixA() const; void setMatrixA(const std::vector &matrixA); const std::vector &getVectorB() const; void setVectorB(const std::vector &vectorB); double getTol() const; void setTol(double tol); int getMaxIterations() const; void setMaxIterations(int maxIterations); + const std::vector &getSolution() const; + void setSolution(const std::vector &vectorSolution); + int getNIterations() const; + void setNIterations(int nIterations); private: std::vectormatrixA; std::vectorvectorB; + std::vectorvectorSolution; + int n_iterations; double tol; int max_iterations; }; #endif //CG_SERIAL_CG_SERIAL_HPP diff --git a/CG_Serial/main.cpp b/CG_Serial/main.cpp index ab6c5d2..7620744 100644 --- a/CG_Serial/main.cpp +++ b/CG_Serial/main.cpp @@ -1,105 +1,108 @@ /** * @file main.cpp * @author Sergio Hernandez * This file is part of the Conjugate Gradient Project * * Ths is the entry point of the project. * */ #include #include #include "CG_Serial.hpp" #include "ConfigFileParser.hpp" /** * Constant to inform the user the correct usage of the program in case of a misuse. */ #define USAGE "Please enter correctly one argument (a config file). Example: ./CG_Parallel configFile.txt" /** * Constant which defines the correct number of arguments the program can receive. */ #define N_ARGS 2 int main(int argc, char* argv[]) { - //TODO Temporal - using Tridiagonal matrix if(argc!=N_ARGS){ std::cout< A;//Filled with 0.0 std::vector b;//Filled with 1.0 std::string fName = argv[1]; ConfigFileParser parser = ConfigFileParser(); parser.parseFile(fName); parser.verify(); std::cout << "Finished parsing the file " << std::endl; //This could be an executer std::map data = parser.getData(); //Size of the matrix std::string tempKey = "N"; N = stoi(data[tempKey]); std::cout << " N = " << N << std::endl; //Tolerance tempKey = "tol"; tol = stof(data[tempKey]); std::cout << " tol = " << tol << std::endl; //max iterations tempKey = "max_iter"; max_iter = stoi(data[tempKey]); std::cout << " max_iter = " << max_iter << std::endl; //type input tempKey = "type_input"; type_input = data[tempKey]; //number_outputs tempKey = "number_outputs"; number_outputs = stoi(data[tempKey]); tempKey = "type_output"; type_output = data[tempKey]; tempKey = "outputFile"; outputFile = data[tempKey]; if (type_input=="tridiagonal") { std::cout<<"Matrix A is: "< 0 ){ + A[i+N*j] = 1.0; //Downer + } + } + if (j == i){ + A[i+N*j] = -2.0; //Main diagonal + } } } - if (j == i-1){ - if (i > 0 ){ - A[i+N*j] = 1.0; //Downer + } else if(type_input=="hilbert"){ + A.resize(N*N);//Fills it with 0s. + b.resize(N,1.0);//Fills it with 0s. + std::fill(b.begin(), b.end(), 1);//Fills it with 1s. + for(int i=0;i x_0 (N,0.0); - CG_Serial solver = CG_Serial(A,b,tol,max_iter); - std::tuple,int> result = solver.computeCG(x_0); - std::vector x = std::get<0>(result); - int k = std::get<1>(result); - std::cout << "Solution was found after : "< x_0 (N,0.0); + CG_Serial solver = CG_Serial(A,b,tol,max_iter); + solver.computeCG(x_0); + solver.saveVector(outputFile); + int k = solver.getNIterations(); + std::cout << "Solution was found after : "<