previous_group previous up next next_group
Previous: 5. Results for Minimization Up: 5. Results for Minimization Next: 2. Overflow and Timeout

1. $C^3$ approach: constraints versus generators, 64-bit

In this section, we compare the 64-bit implementation of the minimization operator that manipulates directly the constraint systems, denoted N64, and the implementation using the double description method for 64-bit, denoted NDD64, which minimizes the polyhedron in question by converting its constraint system to generating system [*]. The first one was already available in $C^3$, and the second one was implemented by me, in order to compare the two approaches. The polyhedral databases used here are the minimization sampled databases (see 6_subsec:polyhedral_databases).

As we have explained in the author's thesis, the semantics of this minimization operator is open enough. Thus the two above algorithms can result in constraint systems which are physically quite different, but should represent two equivalent polyhedra. As a matter of fact, this difference does not affect the meaning of our comparison, since we are interested in an effective implementation of the abstract minimization operator with a correct semantics. Our evaluation permits us checking the equivalence of the output of these two approaches.

In 6_fig:PerfectClub_minimization_dimension_N64_NDD64_100, the histogram shows three colors red, blue and green. The red zones present the cases where constraint manipulation N64 is faster than double description method NDD64, the green zones imply the cases where NDD64 is faster than N64, whereas the blue zones mean that our implementation cannot tell which one is faster than the other, i.e. the run time is about equal, because of the time resolution.

This histogram has two axes representing the number of variables in the constraint system (also known as the dimension space of the polyhedron corresponding), and the number of constraint systems available in PerfectClub polyhedral sampled database. We can see this information in the first line of the figure header, as well the percentages: N64 is faster in $100$ percent of all tests, NDD64 is never faster.

Furthermore, total accumulated run times of all tests are compared, from which the global acceleration is derived and displayed in the second line of figure header: the total run time of NDD64 divided by the total run time of N64 which shows that N64 is approximately $450$ times faster than NDD64.

Figure 28: PerfectClub: Dimension N64 vs NDD64 in sampled database
\begin{figure}
\centering\epsfig {file=POLYBENCH_evaluations/PerfectClub_N64_NDD...
..._DATABASE_100/dimension_N64_NDD64_crite.eps,height=5.9cm,width=14cm}\end{figure}

As for satisfiability test in 6_sec:satisfiability_results, histograms with dimension axis are more informative than the others.

The conclusion for run times of two algorithms is N64 is much faster than NDD64, for PerfectClub sampled database: $450$ times faster. The same results are seen for SPEC95.

The big difference in performance of N64 and NDD64 suggests that in case of performance problems for Double-Description-method-based libraries such as New POLKA, POLYLIB and PPL, implementations using direct manipulation on constraint systems can be a solution.


previous_group previous up next next_group
Previous: 5. Results for Minimization Up: 5. Results for Minimization Next: 2. Overflow and Timeout
Nguyen Que Duong
2006-09-16