previous_group previous up next next_group
Next: 1. Benchmarking

Benchmarking polyhedral libraries

Duong NGUYEN QUE

In the author's thesis, we present the polyhedral interfaces with some differences in names, a survey of algorithms and existing implementations, as well as problems concerning each polyhedral operator. Details on the most important algorithms and some propositions for improvement are given. The question of precision versus approximation is raised, as well as computational issues like $32-bit$, $64-bit$, $128-bit$ or GNU multi-precision arithmetic. Practical issues, such as incompatibilities among polyhedral libraries, are listed.

In this paper, we motivate our benchmarking effort with several examples to showing the impact of exceptions and large operands on abstract interpretation result (6_subsec:motivation). Then we introduce our POLYBENCH framework, which we designed to analyze automatically the run-times and exceptions of the many available libraries presented in the author's thesis with respect to thousands of polyhedral operations traced from PIPS [PIPb,IJT91] static analyzer execution (6_subsec:examples_of_problems). We used our POLYBENCH tools to obtain experimental results about the cases used and about five different key polyhedral operators: the integer and rational satisfiability (6_sec:satisfiability_results), dual conversion (6_sec:dual_conversion_results), projection(6_sec:projection_results), minimization(6_sec:minimization_results) and convex hull(6_sec:convex_hull_results).





Nguyen Que Duong
2006-09-16