September 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(MPI): Distributed_Sparse_Matrix: move some code.
by Marco Poletti 12 Sep '10

12 Sep '10

Module: ppl/ppl Branch: MPI Commit: 6c3d9cd541493017fbe0f813f3edbb721c8fa094 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6c3d9cd54149… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 09:11:49 2010 +0200 Distributed_Sparse_Matrix: move some code. --- src/Distributed_Sparse_Matrix.cc | 154 +++++++++++++++++++------------------- 1 files changed, 77 insertions(+), 77 deletions(-) diff --git a/src/Distributed_Sparse_Matrix.cc b/src/Distributed_Sparse_Matrix.cc index ddf67fe..f25675c 100644 --- a/src/Distributed_Sparse_Matrix.cc +++ b/src/Distributed_Sparse_Matrix.cc @@ -1661,83 +1661,6 @@ PPL::Distributed_Sparse_Matrix return entering_index; } -namespace { - -class exact_entering_index_reducer_functor2 { -public: - const std::vector<PPL::Coefficient>& - operator()(std::vector<PPL::Coefficient>& x, - const std::vector<PPL::Coefficient>& y) const { - PPL_ASSERT(x.size() == y.size()); - for (PPL::dimension_type i = x.size(); i-- > 0; ) - x[i] += y[i]; - return x; - } -}; - -} // namespace - -PPL::dimension_type -PPL::Distributed_Sparse_Matrix -::exact_entering_index(const Dense_Row& working_cost) const { - broadcast_operation(EXACT_ENTERING_INDEX_OPERATION, id); - - // Contains the list of the (column) indexes of challengers. - std::vector<dimension_type> columns; - // This is only an upper bound. - columns.reserve(num_columns() - 1); - - const int cost_sign = sgn(working_cost[working_cost.size() - 1]); - for (dimension_type column = 1; column < num_columns() - 1; ++column) - if (sgn(working_cost[column]) == cost_sign) { - columns.push_back(column); - } - - mpi::broadcast(comm(), columns, 0); - - // For each i, challenger_values[i] contains the challenger value for the - // columns[i] column. - std::vector<Coefficient> challenger_values(columns.size()); - PPL_DIRTY_TEMP_COEFFICIENT(squared_lcm_basis); - exact_entering_index__common(columns, challenger_values, local_rows, base, - squared_lcm_basis); - - std::vector<Coefficient> global_challenger_values; - mpi::reduce(comm(), challenger_values, global_challenger_values, - exact_entering_index_reducer_functor2(), 0); - - PPL_DIRTY_TEMP_COEFFICIENT(challenger_num); - PPL_DIRTY_TEMP_COEFFICIENT(current_num); - PPL_DIRTY_TEMP_COEFFICIENT(current_den); - PPL_DIRTY_TEMP_COEFFICIENT(challenger_value); - PPL_DIRTY_TEMP_COEFFICIENT(current_value); - dimension_type entering_index = 0; - for (dimension_type k = 0; k < columns.size(); ++k) { - global_challenger_values[k] += squared_lcm_basis; - Coefficient_traits::const_reference cost_j = working_cost[columns[k]]; - // We cannot compute the (exact) square root of abs(\Delta x_j). - // The workaround is to compute the square of `cost[j]'. - challenger_num = cost_j * cost_j; - // Initialization during the first loop. - if (entering_index == 0) { - std::swap(current_num, challenger_num); - std::swap(current_den, global_challenger_values[k]); - entering_index = columns[k]; - continue; - } - challenger_value = challenger_num * current_den; - current_value = current_num * global_challenger_values[k]; - // Update the values, if the challenger wins. - if (challenger_value > current_value) { - std::swap(current_num, challenger_num); - std::swap(current_den, global_challenger_values[k]); - entering_index = columns[k]; - } - } - - return entering_index; -} - void PPL::Distributed_Sparse_Matrix ::set_artificial_indexes_for_new_rows(dimension_type old_num_rows, @@ -1839,6 +1762,83 @@ PPL::Distributed_Sparse_Matrix } } +namespace { + +class exact_entering_index_reducer_functor2 { +public: + const std::vector<PPL::Coefficient>& + operator()(std::vector<PPL::Coefficient>& x, + const std::vector<PPL::Coefficient>& y) const { + PPL_ASSERT(x.size() == y.size()); + for (PPL::dimension_type i = x.size(); i-- > 0; ) + x[i] += y[i]; + return x; + } +}; + +} // namespace + +PPL::dimension_type +PPL::Distributed_Sparse_Matrix +::exact_entering_index(const Dense_Row& working_cost) const { + broadcast_operation(EXACT_ENTERING_INDEX_OPERATION, id); + + // Contains the list of the (column) indexes of challengers. + std::vector<dimension_type> columns; + // This is only an upper bound. + columns.reserve(num_columns() - 1); + + const int cost_sign = sgn(working_cost[working_cost.size() - 1]); + for (dimension_type column = 1; column < num_columns() - 1; ++column) + if (sgn(working_cost[column]) == cost_sign) { + columns.push_back(column); + } + + mpi::broadcast(comm(), columns, 0); + + // For each i, challenger_values[i] contains the challenger value for the + // columns[i] column. + std::vector<Coefficient> challenger_values(columns.size()); + PPL_DIRTY_TEMP_COEFFICIENT(squared_lcm_basis); + exact_entering_index__common(columns, challenger_values, local_rows, base, + squared_lcm_basis); + + std::vector<Coefficient> global_challenger_values; + mpi::reduce(comm(), challenger_values, global_challenger_values, + exact_entering_index_reducer_functor2(), 0); + + PPL_DIRTY_TEMP_COEFFICIENT(challenger_num); + PPL_DIRTY_TEMP_COEFFICIENT(current_num); + PPL_DIRTY_TEMP_COEFFICIENT(current_den); + PPL_DIRTY_TEMP_COEFFICIENT(challenger_value); + PPL_DIRTY_TEMP_COEFFICIENT(current_value); + dimension_type entering_index = 0; + for (dimension_type k = 0; k < columns.size(); ++k) { + global_challenger_values[k] += squared_lcm_basis; + Coefficient_traits::const_reference cost_j = working_cost[columns[k]]; + // We cannot compute the (exact) square root of abs(\Delta x_j). + // The workaround is to compute the square of `cost[j]'. + challenger_num = cost_j * cost_j; + // Initialization during the first loop. + if (entering_index == 0) { + std::swap(current_num, challenger_num); + std::swap(current_den, global_challenger_values[k]); + entering_index = columns[k]; + continue; + } + challenger_value = challenger_num * current_den; + current_value = current_num * global_challenger_values[k]; + // Update the values, if the challenger wins. + if (challenger_value > current_value) { + std::swap(current_num, challenger_num); + std::swap(current_den, global_challenger_values[k]); + entering_index = columns[k]; + } + } + + return entering_index; +} + PPL::dimension_type PPL::Distributed_Sparse_Matrix::get_unique_id() { static dimension_type next_id = 0;

1 0

[GIT] ppl/ppl(MPI): MIP_Problem: use Distributed_Sparse_Matrix:: exact_entering_index().
by Marco Poletti 12 Sep '10

12 Sep '10

Module: ppl/ppl Branch: MPI Commit: 316e8514be96641ad7a3b9e8ff9f545011c74d67 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=316e8514be96… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 08:58:40 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::exact_entering_index(). --- src/MIP_Problem.cc | 5 ++++- 1 files changed, 4 insertions(+), 1 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index d5a7566..1069730 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1176,7 +1176,8 @@ PPL::dimension_type PPL::MIP_Problem::steepest_edge_exact_entering_index() const { #if USE_PPL_DISTRIBUTED_SPARSE_MATRIX PPL_ASSERT(distributed_tableau == tableau); -#endif + return distributed_tableau.exact_entering_index(working_cost); +#else // !USE_PPL_DISTRIBUTED_SPARSE_MATRIX const dimension_type tableau_num_rows = tableau.num_rows(); PPL_ASSERT(tableau_num_rows == base.size()); // The square of the lcm of all the coefficients of variables in base. @@ -1332,6 +1333,8 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { #endif // !USE_PPL_SPARSE_MATRIX return entering_index; + +#endif // !USE_PPL_DISTRIBUTED_SPARSE_MATRIX }

1 0

[GIT] ppl/ppl(MPI): Distributed_Sparse_Matrix: add an exact_entering_index( ) method.
by Marco Poletti 12 Sep '10

12 Sep '10

Module: ppl/ppl Branch: MPI Commit: 248a43ded5052d330693a15edf18e0651fe005f2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=248a43ded505… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 08:58:14 2010 +0200 Distributed_Sparse_Matrix: add an exact_entering_index() method. --- src/Distributed_Sparse_Matrix.cc | 189 +++++++++++++++++++++++++++++++++ src/Distributed_Sparse_Matrix.defs.hh | 11 ++ 2 files changed, 200 insertions(+), 0 deletions(-) diff --git a/src/Distributed_Sparse_Matrix.cc b/src/Distributed_Sparse_Matrix.cc index fa19973..ddf67fe 100644 --- a/src/Distributed_Sparse_Matrix.cc +++ b/src/Distributed_Sparse_Matrix.cc @@ -72,6 +72,7 @@ PPL::Distributed_Sparse_Matrix::num_operation_params[] = { 3, // REMOVE_ROW_FROM_BASE_OPERATION: id, rank, row_index 1, // SET_BASE_OPERATION: id 1, // GET_BASE_OPERATION: id + 1, // EXACT_ENTERING_INDEX_OPERATION: id }; const mpi::communicator* @@ -234,6 +235,10 @@ PPL::Distributed_Sparse_Matrix worker.get_base(op.params[0]); break; + case EXACT_ENTERING_INDEX_OPERATION: + worker.exact_entering_index(op.params[0]); + break; + case QUIT_OPERATION: PPL_ASSERT(false); @@ -897,6 +902,85 @@ PPL::Distributed_Sparse_Matrix } } +namespace { + +class exact_entering_index_reducer_functor { +public: + const PPL::Coefficient& + operator()(PPL::Coefficient& x, const PPL::Coefficient& y) const { + PPL::lcm_assign(x, x, y); + return x; + } +}; + +} // namespace + +void +PPL::Distributed_Sparse_Matrix +::exact_entering_index__common(const std::vector<dimension_type>& columns, + std::vector<Coefficient>& challenger_values, + const std::vector<Sparse_Row>& rows, + const std::vector<dimension_type>& base, + Coefficient& squared_lcm_basis) { + // The normalization factor for each coefficient in the tableau. + std::vector<Coefficient> norm_factor(rows.size()); + { + // Compute the lcm of all the coefficients of variables in base. + PPL_DIRTY_TEMP_COEFFICIENT(local_lcm_basis); + local_lcm_basis = 1; + for (dimension_type i = rows.size(); i-- > 0; ) + lcm_assign(local_lcm_basis, local_lcm_basis, rows[i].get(base[i])); + + PPL_DIRTY_TEMP_COEFFICIENT(global_lcm_basis); + mpi::all_reduce(comm(), local_lcm_basis, global_lcm_basis, + exact_entering_index_reducer_functor()); + + // Compute normalization factors for local rows. + for (dimension_type i = rows.size(); i-- > 0; ) + exact_div_assign(norm_factor[i], global_lcm_basis, + rows[i].get(base[i])); + + // Compute the square of `global_lcm_basis', exploiting the fact that + // `global_lcm_basis' will no longer be needed. + global_lcm_basis *= global_lcm_basis; + std::swap(squared_lcm_basis, global_lcm_basis); + } + + PPL_DIRTY_TEMP_COEFFICIENT(scalar_value); + + const dimension_type columns_size = columns.size(); + + for (dimension_type i = rows.size(); i-- > 0; ) { + const Sparse_Row& row = rows[i]; + Sparse_Row::const_iterator j = row.begin(); + Sparse_Row::const_iterator j_end = row.end(); + // This will be used to index the columns[] and challenger_values[] + // vectors. + dimension_type k = 0; + while (j != j_end) { + while (k != columns_size && j.index() > columns[k]) + ++k; + if (k == columns_size) + break; + PPL_ASSERT(j.index() <= columns[k]); + if (j.index() < columns[k]) + j = row.lower_bound(j, columns[k]); + else { + Coefficient_traits::const_reference tableau_ij = *j; + // FIXME: Check if the test against zero speeds up the sparse version. + // The test against 0 gives rise to a consistent speed up: see + // http://www.cs.unipr.it/pipermail/ppl-devel/2009-February/014000.html + if (tableau_ij != 0) { + scalar_value = tableau_ij * norm_factor[i]; + add_mul_assign(challenger_values[k], scalar_value, scalar_value); + } + ++k; + ++j; + } + } + } +} + void PPL::Distributed_Sparse_Matrix::init(dimension_type num_rows1, dimension_type num_cols1) { @@ -1577,6 +1661,83 @@ PPL::Distributed_Sparse_Matrix return entering_index; } +namespace { + +class exact_entering_index_reducer_functor2 { +public: + const std::vector<PPL::Coefficient>& + operator()(std::vector<PPL::Coefficient>& x, + const std::vector<PPL::Coefficient>& y) const { + PPL_ASSERT(x.size() == y.size()); + for (PPL::dimension_type i = x.size(); i-- > 0; ) + x[i] += y[i]; + return x; + } +}; + +} // namespace + +PPL::dimension_type +PPL::Distributed_Sparse_Matrix +::exact_entering_index(const Dense_Row& working_cost) const { + broadcast_operation(EXACT_ENTERING_INDEX_OPERATION, id); + + // Contains the list of the (column) indexes of challengers. + std::vector<dimension_type> columns; + // This is only an upper bound. + columns.reserve(num_columns() - 1); + + const int cost_sign = sgn(working_cost[working_cost.size() - 1]); + for (dimension_type column = 1; column < num_columns() - 1; ++column) + if (sgn(working_cost[column]) == cost_sign) { + columns.push_back(column); + } + + mpi::broadcast(comm(), columns, 0); + + // For each i, challenger_values[i] contains the challenger value for the + // columns[i] column. + std::vector<Coefficient> challenger_values(columns.size()); + PPL_DIRTY_TEMP_COEFFICIENT(squared_lcm_basis); + exact_entering_index__common(columns, challenger_values, local_rows, base, + squared_lcm_basis); + + std::vector<Coefficient> global_challenger_values; + mpi::reduce(comm(), challenger_values, global_challenger_values, + exact_entering_index_reducer_functor2(), 0); + + PPL_DIRTY_TEMP_COEFFICIENT(challenger_num); + PPL_DIRTY_TEMP_COEFFICIENT(current_num); + PPL_DIRTY_TEMP_COEFFICIENT(current_den); + PPL_DIRTY_TEMP_COEFFICIENT(challenger_value); + PPL_DIRTY_TEMP_COEFFICIENT(current_value); + dimension_type entering_index = 0; + for (dimension_type k = 0; k < columns.size(); ++k) { + global_challenger_values[k] += squared_lcm_basis; + Coefficient_traits::const_reference cost_j = working_cost[columns[k]]; + // We cannot compute the (exact) square root of abs(\Delta x_j). + // The workaround is to compute the square of `cost[j]'. + challenger_num = cost_j * cost_j; + // Initialization during the first loop. + if (entering_index == 0) { + std::swap(current_num, challenger_num); + std::swap(current_den, global_challenger_values[k]); + entering_index = columns[k]; + continue; + } + challenger_value = challenger_num * current_den; + current_value = current_num * global_challenger_values[k]; + // Update the values, if the challenger wins. + if (challenger_value > current_value) { + std::swap(current_num, challenger_num); + std::swap(current_den, global_challenger_values[k]); + entering_index = columns[k]; + } + } + + return entering_index; +} + void PPL::Distributed_Sparse_Matrix ::set_artificial_indexes_for_new_rows(dimension_type old_num_rows, @@ -2279,6 +2440,34 @@ PPL::Distributed_Sparse_Matrix::Worker::get_base(dimension_type id) const { mpi::gather(comm(), itr->second.base, 0); } +void +PPL::Distributed_Sparse_Matrix::Worker +::exact_entering_index(dimension_type id) const { + // Contains the list of the (column) indexes of challengers. + std::vector<dimension_type> columns; + + mpi::broadcast(comm(), columns, 0); + + // For each i, challenger_values[i] contains the challenger value for the + // columns[i] column. + std::vector<Coefficient> challenger_values(columns.size()); + + row_chunks_const_itr_type itr = row_chunks.find(id); + + PPL_DIRTY_TEMP_COEFFICIENT(squared_lcm_basis); + if (itr == row_chunks.end()) { + std::vector<Sparse_Row> rows; + std::vector<dimension_type> base; + exact_entering_index__common(columns, challenger_values, rows, base, + squared_lcm_basis); + } else + exact_entering_index__common(columns, challenger_values, itr->second.rows, + itr->second.base, squared_lcm_basis); + + mpi::reduce(comm(), challenger_values, + exact_entering_index_reducer_functor2(), 0); +} + template <typename Archive> void PPL::Distributed_Sparse_Matrix::Operation diff --git a/src/Distributed_Sparse_Matrix.defs.hh b/src/Distributed_Sparse_Matrix.defs.hh index f714c65..72f42eb 100644 --- a/src/Distributed_Sparse_Matrix.defs.hh +++ b/src/Distributed_Sparse_Matrix.defs.hh @@ -133,6 +133,7 @@ public: void remove_row_from_base(dimension_type row_index); void set_base(const std::vector<dimension_type>& base); void get_base(std::vector<dimension_type>& base) const; + dimension_type exact_entering_index(const Dense_Row& working_cost) const; bool OK() const; @@ -175,6 +176,13 @@ private: const std::vector<Sparse_Row>& rows, std::vector<double>& results); + static void exact_entering_index__common( + const std::vector<dimension_type>& columns, + std::vector<Coefficient>& challenger_values, + const std::vector<Sparse_Row>& rows, + const std::vector<dimension_type>& base, + Coefficient& squared_lcm_basis); + void init(dimension_type num_rows, dimension_type num_columns); static dimension_type get_unique_id(); @@ -239,6 +247,7 @@ private: dimension_type local_row_index); void set_base(dimension_type id); void get_base(dimension_type id) const; + void exact_entering_index(dimension_type id) const; private: struct Row_Chunk { @@ -325,6 +334,8 @@ private: SET_BASE_OPERATION, //! Parameters: id GET_BASE_OPERATION, + //! Parameters: id + EXACT_ENTERING_INDEX_OPERATION, }; // This associates to each operation code the number of dimension_type

1 0

[GIT] ppl/ppl(master): MIP_Problem: improve a little bit the get_exiting_base_index() performance.
by Marco Poletti 12 Sep '10

12 Sep '10

Module: ppl/ppl Branch: master Commit: 620592736a503f2ee3d40880a6ca4ee25a6a7bd9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=620592736a50… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 10:56:32 2010 +0200 MIP_Problem: improve a little bit the get_exiting_base_index() performance. --- src/MIP_Problem.cc | 13 ++++++------- 1 files changed, 6 insertions(+), 7 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 882af9e..6d1981a 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1467,9 +1467,8 @@ PPL::MIP_Problem PPL_DIRTY_TEMP_COEFFICIENT(challenger); // These pointers are used instead of references in the following loop, to // improve performance. - const matrix_type::row_type* t_e = &(tableau[exiting_base_index]); - Coefficient t_e0 = t_e->get(0); - Coefficient t_ee = t_e->get(entering_var_index); + Coefficient t_e0 = tableau[exiting_base_index].get(0); + Coefficient t_ee = tableau[exiting_base_index].get(entering_var_index); for (dimension_type i = exiting_base_index + 1; i < tableau_num_rows; ++i) { const matrix_type::row_type& t_i = tableau[i]; Coefficient_traits::const_reference t_ie = t_i.get(entering_var_index); @@ -1477,21 +1476,21 @@ PPL::MIP_Problem const int t_ie_sign = sgn(t_ie); if (t_ie_sign != 0 && t_ie_sign == sgn(t_ib)) { WEIGHT_BEGIN(); + Coefficient_traits::const_reference t_i0 = t_i.get(0); lcm_assign(lcm, t_ee, t_ie); exact_div_assign(current_min, lcm, t_ee); current_min *= t_e0; abs_assign(current_min); exact_div_assign(challenger, lcm, t_ie); - challenger *= t_i.get(0); + challenger *= t_i0; abs_assign(challenger); current_min -= challenger; const int sign = sgn(current_min); if (sign > 0 || (sign == 0 && base[i] < base[exiting_base_index])) { exiting_base_index = i; - t_e = &(tableau[exiting_base_index]); - t_e0 = t_e->get(0); - t_ee = t_e->get(entering_var_index); + t_e0 = t_i0; + t_ee = t_ie; } WEIGHT_ADD(1044); }

1 0

[GIT] ppl/ppl(MPI): New commits
by Roberto Bagnara 11 Sep '10

11 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d24ba0b9b02b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 22:26:10 2010 +0200 Distributed_Sparse_Matrix: don't pass reverse_mapping to compute_working_cost__common(), it's not needed. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a6848cb44992… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 22:03:05 2010 +0200 Distributed_Sparse_Matrix: exploit the nodes' base[] vectors. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1ddb135172c0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 22:01:31 2010 +0200 MIP_Problem: check the Distributed_Sparse_Matrix copy of base, in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=881049158437… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 22:01:00 2010 +0200 Distributed_Sparse_Matrix: store a copy the relevant part of MIP_Problem's base[] in each node. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4c60bace7754… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 18:36:31 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::set_artificial_indexes_for_new_rows(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a8e2719b4ac8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 18:36:07 2010 +0200 Distributed_Sparse_Matrix: add a set_artificial_indexes_for_new_rows() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=799bf02ef126… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 18:35:35 2010 +0200 Distributed_Sparse_Matrix: add more debug messages in operator==(const Sparse_Matrix&). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c6292245feb1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 16:37:28 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::float_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=34519d2a4b00… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 16:36:55 2010 +0200 Distributed_Sparse_Matrix: add a float_entering_index() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=61eb29577a31… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 15:25:42 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::get_scattered_row() in OK().

1 0

[GIT] ppl/ppl(MPI): New commits
by Roberto Bagnara 11 Sep '10

11 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c07027f4ae53… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 12:35:20 2010 +0200 MIP_Problem: add comments. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ba8994e5ce5e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 12:33:27 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::get_scattered_row(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=044e5f9b2967… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 12:32:34 2010 +0200 Distributed_Sparse_Matrix: add get_scattered_row() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7ef1649be065… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 11:32:25 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::get_column() in compute_generator(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4b1152731037… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 10:35:22 2010 +0200 Distributed_Sparse_Matrix: use PPL macros to declare and define ASCII dump/load methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0644f37aec25… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 10:32:06 2010 +0200 Distributed_Sparse_Matrix: add an ascii_load() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=09a9894fc059… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 10:18:14 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::get_column() in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d930d1c08366… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 10:17:28 2010 +0200 Distributed_Sparse_Matrix: add a get_column() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6b96c2965e1c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 11 09:22:18 2010 +0200 Distributed_Sparse_Matrix: rename row_mapping and reverse_row_mapping into mapping and reverse_mapping. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=42e5ed2affa5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 19:30:19 2010 +0200 Distributed_Sparse_Matrix: exploit the nodes' copies of reverse_row_mapping, avoiding a scatter() operation. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1b0df8de05c8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 19:24:07 2010 +0200 Distributed_Sparse_Matrix: improve add_row() performance. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3808e089c9ea… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 19:19:17 2010 +0200 Distributed_Sparse_Matrix: greatly improve add_zero_rows() performance. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cb5ff6b570b2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 18:39:57 2010 +0200 Distributed_Sparse_Matrix: exploit the nodes' copies of reverse_row_mapping in remove_trailing_rows(), removing a scatter operation. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5a1c81a75ad2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 18:24:47 2010 +0200 Distributed_Sparse_Matrix: broadcast the id and the index, instead of sending them separately, in get_row() and set_row().

1 0

[GIT] ppl/ppl(MPI): New commits
by Roberto Bagnara 10 Sep '10

10 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e0a34325e3d6… Merge: 262fd31e77b59abfafba4ee7b1fb8f4adf5de2ac ad3694d4bbf7a930d3d262568487cce8066f55fd Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 17:50:58 2010 +0200 Merge remote branch 'origin/master' into MPI Conflicts: src/MIP_Problem.cc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ad3694d4bbf7… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Sep 9 17:13:48 2010 +0200 Reflected the changes in http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8966 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4974d4f39e8c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 9 08:25:24 2010 +0200 MIP_Problem: don't copy Coefficient objects to cache accesses, in steepest_edge_exact_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ab1231051fa8… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Wed Sep 8 07:31:19 2010 +0200 Mentioned the fix to Interval::Interval(const char*). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3e2fe287b4ef… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Tue Sep 7 23:13:17 2010 +0200 Fixed interval construction from strings. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=22c92f00fb9e… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Sep 7 20:01:44 2010 +0200 Announced a couple of new features and bugfixes. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f949a0fced31… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Sep 7 19:31:56 2010 +0200 Mention the use of sparse matrices in MIP and PIP solvers. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46655e57eb7d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 7 19:05:39 2010 +0200 MIP_Problem: fix some debug messages and comments, in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8df25ad97af2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 7 18:49:40 2010 +0200 MIP_Problem: fix typos in some debug messages and comments, in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=359b3a83e66e… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Sep 7 16:07:22 2010 +0200 test06 fails with 8-bit coefficients.

1 0

[GIT] ppl/ppl(MPI): Distributed_Sparse_Matrix: optimize compute_working_cost_reducer_functor.
by Marco Poletti 10 Sep '10

10 Sep '10

Module: ppl/ppl Branch: MPI Commit: 262fd31e77b59abfafba4ee7b1fb8f4adf5de2ac URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=262fd31e77b5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 17:47:07 2010 +0200 Distributed_Sparse_Matrix: optimize compute_working_cost_reducer_functor. --- src/Distributed_Sparse_Matrix.cc | 42 ++++++++++++++++++------------------- 1 files changed, 20 insertions(+), 22 deletions(-) diff --git a/src/Distributed_Sparse_Matrix.cc b/src/Distributed_Sparse_Matrix.cc index 3b44eaf..9ec2f61 100644 --- a/src/Distributed_Sparse_Matrix.cc +++ b/src/Distributed_Sparse_Matrix.cc @@ -583,21 +583,18 @@ namespace { struct compute_working_cost_reducer_functor { typedef std::pair<std::pair<PPL::Coefficient, PPL::Coefficient>, PPL::Sparse_Row> pair_type; - pair_type - operator()(const pair_type& x, const pair_type& y) const { - pair_type result(x); - const PPL::Coefficient& x_scaling = x.first.first; - const PPL::Coefficient& x_reverse_scaling = x.first.second; + const pair_type& + operator()(pair_type& x, const pair_type& y) const { + PPL::Coefficient& x_scaling = x.first.first; + PPL::Coefficient& x_reverse_scaling = x.first.second; + PPL::Sparse_Row& x_row = x.second; const PPL::Coefficient& y_scaling = y.first.first; const PPL::Coefficient& y_reverse_scaling = y.first.second; + const PPL::Sparse_Row& y_row = y.second; PPL_ASSERT(x_scaling != 0); PPL_ASSERT(x_reverse_scaling != 0); PPL_ASSERT(y_scaling != 0); PPL_ASSERT(y_reverse_scaling != 0); - const PPL::Sparse_Row& y_row = y.second; - PPL::Coefficient& scaling = result.first.first; - PPL::Coefficient& reverse_scaling = result.first.second; - PPL::Sparse_Row& row = result.second; PPL::Coefficient x_normalized_scaling = x_scaling * y_reverse_scaling; PPL::Coefficient y_normalized_scaling = y_scaling * x_reverse_scaling; @@ -606,19 +603,20 @@ struct compute_working_cost_reducer_functor { PPL::exact_div_assign(x_normalized_scaling, x_normalized_scaling, gcd); PPL::exact_div_assign(y_normalized_scaling, y_normalized_scaling, gcd); - scaling *= y_scaling; - reverse_scaling = gcd; - PPL_ASSERT(scaling != 0); - PPL_ASSERT(reverse_scaling != 0); - PPL::normalize2(scaling, reverse_scaling, scaling, reverse_scaling); - PPL_ASSERT(scaling != 0); - PPL_ASSERT(reverse_scaling != 0); - - PPL::dimension_type n = x.second.size(); - PPL::Dense_Row tmp(n, PPL::Row_Flags()); - row.linear_combine(y_row, y_normalized_scaling, x_normalized_scaling); - // TODO: Check if the copy can be avoided. - return result; + x_scaling *= y_scaling; + x_reverse_scaling = gcd; + + x_row.linear_combine(y_row, y_normalized_scaling, x_normalized_scaling); + + x_row.normalize(gcd); + x_reverse_scaling *= gcd; + + PPL::normalize2(x_scaling, x_reverse_scaling, + x_scaling, x_reverse_scaling); + + // This return is needed because mpi::reduce() requires it. + // x will be assigned to itself, so the data will not be copied. + return x; } };

1 0

[GIT] ppl/ppl(MPI): Distributed_Sparse_Matrix: add TODO.
by Marco Poletti 10 Sep '10

10 Sep '10

Module: ppl/ppl Branch: MPI Commit: dc2fc3585c8459ca6383271c2b442ae3eff56430 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dc2fc3585c84… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 17:46:07 2010 +0200 Distributed_Sparse_Matrix: add TODO. --- src/Distributed_Sparse_Matrix.cc | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) diff --git a/src/Distributed_Sparse_Matrix.cc b/src/Distributed_Sparse_Matrix.cc index bff6c62..3b44eaf 100644 --- a/src/Distributed_Sparse_Matrix.cc +++ b/src/Distributed_Sparse_Matrix.cc @@ -763,6 +763,8 @@ PPL::Distributed_Sparse_Matrix::linear_combine_with_base_rows__common( i != i_end; ++i) row_k[i.index()] += global_reverse_scaling * *i; + // TODO: row_k seems to be already normalized, check whether this can be + // removed or not. row_k.normalize(); }

1 0

[GIT] ppl/ppl(MPI): Init: call MPI_Init and MPI_Finalize directly, instead of using an mpi::environment, avoiding crashes on some systems.
by Marco Poletti 10 Sep '10

10 Sep '10

Module: ppl/ppl Branch: MPI Commit: 4b615df4b01f520c6a3f67ccd2af4dfe7db19670 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4b615df4b01f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 10 12:01:54 2010 +0200 Init: call MPI_Init and MPI_Finalize directly, instead of using an mpi::environment, avoiding crashes on some systems. --- src/Init.cc | 11 +++++------ src/Init.defs.hh | 1 - 2 files changed, 5 insertions(+), 7 deletions(-) diff --git a/src/Init.cc b/src/Init.cc index c5eaf18..1c4a9d6 100644 --- a/src/Init.cc +++ b/src/Init.cc @@ -52,8 +52,7 @@ unsigned int PPL::Init::count = 0; PPL::fpu_rounding_direction_type PPL::Init::old_rounding_direction; #if USE_PPL_DISTRIBUTED_SPARSE_MATRIX -boost::mpi::communicator* PPL::Init::mpi_communicator; -boost::mpi::environment* PPL::Init::mpi_environment; +boost::mpi::communicator* PPL::Init::mpi_communicator = NULL; #endif // USE_PPL_DISTRIBUTED_SPARSE_MATRIX extern "C" void @@ -189,11 +188,11 @@ PPL::Init::Init() { #if USE_PPL_DISTRIBUTED_SPARSE_MATRIX // Initialize MPI - int fake_argc = 0; + int fake_argc = 1; char c = '\0'; char *fake_argv0 = &c; char **fake_argv = &fake_argv0; - mpi_environment = new boost::mpi::environment(fake_argc, fake_argv); + MPI_Init(&fake_argc, &fake_argv); mpi_communicator = new boost::mpi::communicator(); if (mpi_communicator->rank() == 0) { Distributed_Sparse_Matrix::init_root(*mpi_communicator); @@ -201,7 +200,7 @@ PPL::Init::Init() { // WARNING: worker nodes will block here until process termination Distributed_Sparse_Matrix::worker_main_loop(*mpi_communicator); delete mpi_communicator; - delete mpi_environment; + MPI_Finalize(); exit(0); } #endif // USE_PPL_DISTRIBUTED_SPARSE_MATRIX @@ -215,7 +214,7 @@ PPL::Init::~Init() { // Release MPI resources. Distributed_Sparse_Matrix::quit_workers(); delete mpi_communicator; - delete mpi_environment; + MPI_Finalize(); #endif // USE_PPL_DISTRIBUTED_SPARSE_MATRIX #if PPL_CAN_CONTROL_FPU diff --git a/src/Init.defs.hh b/src/Init.defs.hh index 7df6a7e..f9f2ed3 100644 --- a/src/Init.defs.hh +++ b/src/Init.defs.hh @@ -86,7 +86,6 @@ private: static fpu_rounding_direction_type old_rounding_direction; #if USE_PPL_DISTRIBUTED_SPARSE_MATRIX static boost::mpi::communicator* mpi_communicator; - static boost::mpi::environment* mpi_environment; #endif friend void set_rounding_for_PPL();

1 0