September 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize further steepest_edge_float_entering_index() for sparse working_cost rows.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: c68f9092edf4b116fc1a595e8a997a3614ab3cac URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c68f9092edf4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:42 2010 +0200 MIP_Problem: optimize further steepest_edge_float_entering_index() for sparse working_cost rows. --- src/MIP_Problem.cc | 18 ++++++++++++------ 1 files changed, 12 insertions(+), 6 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 9db9ffb..1b54d00 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -996,9 +996,13 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { #if USE_PPL_SPARSE_MATRIX const dimension_type tableau_num_columns_minus_1 = tableau_num_columns - 1; + // This is static to improve performance. // A vector of <column_index, challenger_den> pairs, ordered by // column_index. - std::vector<std::pair<dimension_type, double> > columns; + static std::vector<std::pair<dimension_type, double> > columns; + columns.clear(); + // (working_cost.size() - 2) is an upper bound only. + columns.reserve(working_cost.size() - 2); { working_cost_type::const_iterator i = working_cost.lower_bound(1); // Note that find() is used instead of lower_bound(). @@ -1020,12 +1024,14 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { = columns.end(); while (j != j_end && k != k_end) { const dimension_type column = j.index(); - if (k->first != column) { - if (k->first < column) - ++k; - else - j = tableau_i.lower_bound(j, k->first); + while (k != k_end && column > k->first) + ++k; + if (k == k_end) + break; + if (k->first > column) { + j = tableau_i.lower_bound(j, k->first); } else { + PPL_ASSERT(k->first == column); Coefficient_traits::const_reference tableau_ij = *j; WEIGHT_BEGIN(); if (tableau_ij != 0) {

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 30a048b00fe98b60a13b378261908e4373a275d3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=30a048b00fe9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:03 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. --- src/MIP_Problem.cc | 14 +++++++++++--- 1 files changed, 11 insertions(+), 3 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 784880d..9db9ffb 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -871,9 +871,17 @@ PPL::MIP_Problem::process_pending_constraints() { working_cost[last_obj_index] = 1; // Express the problem in terms of the variables in base. - for (dimension_type i = tableau_num_rows; i-- > 0; ) - if (working_cost.get(base[i]) != 0) - linear_combine(working_cost, tableau[i], base[i]); + { + working_cost_type::const_iterator itr = working_cost.end(); + for (dimension_type i = tableau_num_rows; i-- > 0; ) { + itr = working_cost.lower_bound(itr, base[i]); + if (itr != working_cost.end() && itr.index() == base[i] && *itr != 0) { + linear_combine(working_cost, tableau[i], base[i]); + // itr has been invalidated by the call to linear_combine(). + itr = working_cost.end(); + } + } + } // Deal with zero dimensional problems. if (space_dimension() == 0) {

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize second_phase() for sparse working_cost rows.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: f2479e2b3e49803d56e972cf3e036d238037030b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f2479e2b3e49… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:34:19 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows. --- src/MIP_Problem.cc | 18 +++++++++++++----- 1 files changed, 13 insertions(+), 5 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 560b47a..784880d 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1857,12 +1857,20 @@ PPL::MIP_Problem::second_phase() { i = new_cost.begin(), i_end = new_cost.end(); i != i_end; ++i) neg_assign(*i); - // Substitute properly the cost function in the `costs' matrix. const dimension_type cost_zero_size = working_cost.size(); - working_cost_type tmp_cost = working_cost_type(cost_zero_size, - cost_zero_size, - new_cost.flags()); - tmp_cost.swap(working_cost); + + // Substitute properly the cost function in the `costs' matrix. +#if USE_PPL_SPARSE_MATRIX + working_cost.clear(); + working_cost.flags() = Row_Flags(); +#else + { + working_cost_type tmp_cost = working_cost_type(cost_zero_size, + cost_zero_size, + new_cost.flags()); + tmp_cost.swap(working_cost); + } +#endif { working_cost_type::iterator itr

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: fix regression in textbook_entering_index(), introduced in commit 6880A6.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 07dfb14d484ef7b552388152934e3e0ae6f1099b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07dfb14d484e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:26:46 2010 +0200 MIP_Problem: fix regression in textbook_entering_index(), introduced in commit 6880A6. --- src/MIP_Problem.cc | 10 +++++++--- 1 files changed, 7 insertions(+), 3 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 3538b33..560b47a 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1266,9 +1266,13 @@ PPL::MIP_Problem::textbook_entering_index() const { const dimension_type cost_sign_index = working_cost.size() - 1; const int cost_sign = sgn(working_cost.get(cost_sign_index)); PPL_ASSERT(cost_sign != 0); - for (working_cost_type::const_iterator - i = working_cost.lower_bound(1), i_end = working_cost.end(); - i != i_end; ++i) + + working_cost_type::const_iterator i = working_cost.lower_bound(1); + // Note that find() is used instead of lower_bound() because they are + // equivalent when searching the last element in the row. + working_cost_type::const_iterator i_end + = working_cost.find(cost_sign_index); + for ( ; i != i_end; ++i) if (sgn(*i) == cost_sign) return i.index(); // No variable has to enter the base:

1 0

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

14 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f6a93645a5b8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:39:00 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#4). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2c0d6052ae00… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:38:42 2010 +0200 MIP_Problem: avoid an unnecessary copy of the working_cost row, in second_phase(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2d1cbd6415ae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:26:37 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#3). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8bbd7540511b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:24:01 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#2). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=42a7e27f4267… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:21:59 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#1). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b5e34c885640… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:36:09 2010 +0200 MIP_Problem: little optimizations for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6880a6746e15… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:30:38 2010 +0200 MIP_Problem: optimize textbook_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=92e46ffb3c10… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:28:37 2010 +0200 MIP_Problem: optimize steepest_edge_float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c2aa82c4a7c9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:23:52 2010 +0200 MIP_Problem: optimize steepest_edge_exact_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ee1d1d7f9add… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:55 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1c643c264345… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:30 2010 +0200 Sparse_Row: add some assertions. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=24ec2790edae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:39:22 2010 +0200 MIP_Problem: use a sparse working_cost when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ffe3720ee015… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:38:34 2010 +0200 Sparse_Row: add a constructor and two copy-constructors that take a capacity parameter. 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. 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. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=384f089de7b9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 19:33:59 2010 +0200 tests/CO_Tree: modify the tests so that they pass even with 8-bit coefficients. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fbd049063bb7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 19:32:52 2010 +0200 tests/Sparse_Matrix: modify the tests so that they pass even when using 8-bit coefficients. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=eaf5206df76c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 12:14:47 2010 +0200 tests/CO_Tree: use DO_TEST_F8 when a test is expected to fail with 8-bit coefficients.

1 0

[GIT] ppl/ppl(floating_point): Adapted tests on digital filters to latest changes.
by Fabio Bossi 13 Sep '10

13 Sep '10

Module: ppl/ppl Branch: floating_point Commit: ebcd55e82f73703737752a66ca25891ece02661a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ebcd55e82f73… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Mon Sep 13 17:42:12 2010 +0200 Adapted tests on digital filters to latest changes. --- tests/Concrete_Expression/Makefile.am | 1 + tests/Concrete_Expression/digitalfilters1.cc | 371 +++++++++++++++----------- 2 files changed, 210 insertions(+), 162 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=ebcd55e8…

1 0

[GIT] ppl/ppl(floating_point): Do not fail automatically when linearizing approximable
by Fabio Bossi 13 Sep '10

13 Sep '10

Module: ppl/ppl Branch: floating_point Commit: 219f235033052dd7e24399eb9d1e494911ed0401 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=219f23503305… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Mon Sep 13 14:08:29 2010 +0200 Do not fail automatically when linearizing approximable references having more than one associated dimension. --- src/Float.defs.hh | 16 ++++++--- src/linearize.hh | 44 +++++++++++++++++++++----- tests/Concrete_Expression/C_Expr.defs.hh | 12 +++--- tests/Concrete_Expression/C_Expr.inlines.hh | 5 ++- tests/Concrete_Expression/linearize.cc | 45 ++++++++++++++++++++++++-- 5 files changed, 96 insertions(+), 26 deletions(-) diff --git a/src/Float.defs.hh b/src/Float.defs.hh index 059d3e4..ad67317 100644 --- a/src/Float.defs.hh +++ b/src/Float.defs.hh @@ -433,14 +433,18 @@ public: FP_Interval_Type& result) const = 0; /*! \brief - Asks the external analyzer for the space dimension associated to - the approximable reference \p expr. + Asks the external analyzer for the possible space dimensions that + are associated to the approximable reference \p expr. + Result is stored into \p result. + + \return <CODE>true</CODE> if the analyzer was able to return + the (possibly empty!) set, <CODE>false</CODE> otherwise. - \return the associated space dimension if succesful, - <CODE>not_a_dimension()<CODE> otherwise. + The resulting set MUST NOT contain <CODE>not_a_dimension()</CODE>. */ - virtual dimension_type get_associated_dimension( - const Approximable_Reference<Target>& expr) const = 0; + virtual bool get_associated_dimensions( + const Approximable_Reference<Target>& expr, + std::set<dimension_type>& result) const = 0; }; diff --git a/src/linearize.hh b/src/linearize.hh index 0aaa464..8767f80 100644 --- a/src/linearize.hh +++ b/src/linearize.hh @@ -738,15 +738,22 @@ linearize(const Concrete_Expression<Target>& expr, { const Approximable_Reference<Target>* ref_expr = expr.template as<Approximable_Reference>(); - /* Variable references are the only that we are currently - able to analyze */ - dimension_type variable_index = oracle.get_associated_dimension(*ref_expr); - if (variable_index == not_a_dimension()) + std::set<dimension_type> associated_dimensions; + if (!oracle.get_associated_dimensions(*ref_expr, associated_dimensions) + || associated_dimensions.empty()) + /* + We were unable to find any associated space dimension: + linearization fails. + */ return false; - else { - /* If a linear form associated to the referenced variable - exists in lf_store, return that form. Otherwise, return - the simplest linear form. */ + + if (associated_dimensions.size() == 1) { + /* If a linear form associated to the only referenced + space dimension exists in lf_store, return that form. + Otherwise, return the simplest linear form. */ + dimension_type variable_index = *associated_dimensions.begin(); + PPL_ASSERT(variable_index != not_a_dimension()); + typename FP_Linear_Form_Abstract_Store::const_iterator variable_value = lf_store.find(variable_index); if (variable_value == lf_store.end()) { @@ -759,6 +766,27 @@ linearize(const Concrete_Expression<Target>& expr, that an unbounded linear form was saved into lf_store? */ return !result.overflows(); } + + /* + Here associated_dimensions.size() > 1. Try to return the LUB + of all intervals associated to each space dimension. + */ + std::set<dimension_type>::const_iterator i = associated_dimensions.begin(); + std::set<dimension_type>::const_iterator i_end = + associated_dimensions.end(); + FP_Interval_Type lub(EMPTY); + for (; i != i_end; ++i) { + FP_Interval_Type curr_int; + PPL_ASSERT(*i != not_a_dimension()); + if (!oracle.get_interval(*i, curr_int)) + return false; + + lub.join_assign(curr_int); + } + + result = FP_Linear_Form(lub); + return !result.overflows(); + break; } case Cast_Operator<Target>::KIND: diff --git a/tests/Concrete_Expression/C_Expr.defs.hh b/tests/Concrete_Expression/C_Expr.defs.hh index 40de1c0..32104eb 100644 --- a/tests/Concrete_Expression/C_Expr.defs.hh +++ b/tests/Concrete_Expression/C_Expr.defs.hh @@ -227,10 +227,10 @@ class Approximable_Reference<C_Expr> : public Concrete_Expression<C_Expr>, public Approximable_Reference_Common<C_Expr> { public: - //! Builds a reference to the variable having the given index. + //! Builds a reference to the entity having the given index. Approximable_Reference<C_Expr>(Concrete_Expression_Type type, - const Integer_Interval_Type& val, - dimension_type var_index); + const Integer_Interval_Type& val, + dimension_type index); //! Do-nothing destructor. ~Approximable_Reference<C_Expr>(); @@ -241,11 +241,11 @@ public: //! Constant identifying approximable reference nodes. enum { KIND = APPROX_REF }; - //! An interval in which the variable's value falls. + //! An interval in which the referenced entity's value falls. Integer_Interval_Type value; - //! The index of the referenced variable. - dimension_type var_dimension; + //! The set of possible indexes for the referenced entity. + std::set<dimension_type> dimensions; }; } // namespace Parma_Polyhedra_Library diff --git a/tests/Concrete_Expression/C_Expr.inlines.hh b/tests/Concrete_Expression/C_Expr.inlines.hh index accb5d0..d12ccd5 100644 --- a/tests/Concrete_Expression/C_Expr.inlines.hh +++ b/tests/Concrete_Expression/C_Expr.inlines.hh @@ -165,10 +165,11 @@ inline Approximable_Reference<C_Expr>:: Approximable_Reference(Concrete_Expression_Type type, const Integer_Interval_Type& val, - dimension_type var_index) + dimension_type index) : Concrete_Expression<C_Expr>(type, APPROX_REF), value(val), - var_dimension(var_index) { + dimensions() { + dimensions.insert(index); } inline diff --git a/tests/Concrete_Expression/linearize.cc b/tests/Concrete_Expression/linearize.cc index 1cf9ae9..26dcf0e 100644 --- a/tests/Concrete_Expression/linearize.cc +++ b/tests/Concrete_Expression/linearize.cc @@ -58,9 +58,11 @@ public: return true; } - dimension_type get_associated_dimension( - const Approximable_Reference<C_Expr>& expr) const { - return expr.var_dimension; + bool get_associated_dimensions( + const Approximable_Reference<C_Expr>& expr, + std::set<dimension_type>& result) const { + result = expr.dimensions; + return true; } FP_Interval_Abstract_Store int_store; @@ -99,10 +101,13 @@ test02() { Binary_Operator<C_Expr> dif(FP_Type, Binary_Operator<C_Expr>::SUB, &var1, &con); Binary_Operator<C_Expr> mul(FP_Type, Binary_Operator<C_Expr>::MUL, &dif, &var0); FP_Linear_Form result; - linearize(mul, oracle, FP_Linear_Form_Abstract_Store(), result); + if (!linearize(mul, oracle, FP_Linear_Form_Abstract_Store(), result)) + return false; FP_Linear_Form known_result(compute_absolute_error<FP_Interval>(ANALYZED_FP_FORMAT)); + nout << "*** result ***" << endl + << result << endl; nout << "*** known_result ***" << endl << known_result << endl; bool ok = (result == known_result); @@ -274,6 +279,37 @@ test08() { return ok1 && ok2; } +/* + Tests linearization of an approximable reference having more than + one associated index. +*/ +bool +test09() { + Test_Oracle oracle(FP_Interval_Abstract_Store(4)); + oracle.int_store.set_interval(Variable(0), FP_Interval(0)); + oracle.int_store.set_interval(Variable(1), FP_Interval(10)); + oracle.int_store.set_interval(Variable(2), FP_Interval(20)); + oracle.int_store.set_interval(Variable(3), FP_Interval(5)); + Approximable_Reference<C_Expr> ref(FP_Type, Int_Interval(mpz_class(0)), 0); + ref.dimensions.insert(1); + ref.dimensions.insert(3); + FP_Linear_Form result; + if (!linearize(ref, oracle, FP_Linear_Form_Abstract_Store(), result)) + return false; + + FP_Interval known_int(FP_Interval(0)); + known_int.join_assign(FP_Interval(10)); + FP_Linear_Form known_result(known_int); + + nout << "*** result ***" << endl + << result << endl; + nout << "*** known_result ***" << endl + << known_result << endl; + bool ok = (result == known_result); + + return ok; +} + } // namespace BEGIN_MAIN @@ -285,4 +321,5 @@ BEGIN_MAIN DO_TEST(test06); DO_TEST(test07); DO_TEST(test08); + DO_TEST(test09); END_MAIN

1 0

[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