- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(floating_point): Use an oracle to obtain information from an external
by Fabio Bossi 13 Sep '10

13 Sep '10

Module: ppl/ppl Branch: floating_point Commit: 33dfccc8af8e5205e24d17b8b7b83cb1d35025f3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=33dfccc8af8e… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Mon Sep 13 10:44:17 2010 +0200 Use an oracle to obtain information from an external analyzer in the linearization function. Temporarily disabled test digitalfilters. --- src/Concrete_Expression.defs.hh | 18 ---- src/Float.defs.hh | 69 +++++++++++++++ src/Linear_Form.defs.hh | 21 ++++- src/Linear_Form.templates.hh | 13 ++- src/linearize.hh | 124 +++++++++++---------------- tests/Concrete_Expression/C_Expr.defs.hh | 71 +--------------- tests/Concrete_Expression/C_Expr.inlines.hh | 40 --------- tests/Concrete_Expression/Makefile.am | 1 - tests/Concrete_Expression/linearform1.cc | 18 ---- tests/Concrete_Expression/linearize.cc | 104 ++++++++++++++++------- 10 files changed, 220 insertions(+), 259 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=33dfccc8…

1 0

[GIT] ppl/ppl(MPI): Merge remote branch 'origin/master' into MPI
by Marco Poletti 12 Sep '10

12 Sep '10

Module: ppl/ppl Branch: MPI Commit: e3f43585b3442b474733d4233b162e61270271e9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e3f43585b344… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 10:57:34 2010 +0200 Merge remote branch 'origin/master' into MPI ---

1 0

[GIT] ppl/ppl(MPI): 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: MPI 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): 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