In order to provide a tool comparing similar methods, we build up a polyhedral benchmark, made of a large number of polyhedral operations that we extract from the execution of real-life program analyses and transformations.
In this section, we present our polyhedral benchmark framework, called POLYBENCH, by commenting 6_fig:Polyhedral_benchmark_schema step by step. PIPS [PIPb,IJT91], which stands for ``Paralléliseur Interprocédural de Programmes Scientifiques'', is an analyzer-transformer of programs that uses polyhedral abstraction [PIPb,IJT91]. A PIPS phase can perform analyses and transformations on Fortran programs, such as Array Privatization, Dependence Testing, Memory Effects, Preconditions, Expression Optimizations, Forward Substitution, Parallelization, etc...
Standard benchmarks like the PerfectClub [BCK$^$89] and SPEC CFP 95 [SPE], henceforth called SPEC95 for short, have been chosen for polyhedral data generation as PIPS's input . For our benchmark, we have chosen the transformers and preconditions since they are often used in other analyses, and array regions due to its high computational demand . During PIPS execution on these benchmarks, polyhedra in form of constraint systems are traced and stored in a large database of directory-structured files, divided by polyhedral operators . This database is compressed because it is quite large: over GB. Then we apply some sampling for each sub-database in order to reduce the number of constraint systems to be tested when needed . Since we want to measure implementations' performance in general cases, these sampled databases should be representative. However, we are sometimes interested in a biased database, for special purposes, therefore we also use some criterion-based filters, for instance to retrieve only the larger polyhedra (see 6_subsec:polyhedral_databases).
The databases contain operands for most available implementations of polyhedral operators, such as LINEAR [PIPa,CAI00], CDD [FUK], JANUS [SOG], LRS [Avi], POLYLIB [LOE,Wil], PPL [PAR,BRZaH02] and New POLKA [JEA,JEA00]. The implementations having different data structures are encapsulated by converters, which we implemented for each library. We measure the performances of similar implementations , then display the comparisons in graphical form . We also analyze some characteristics of those databases .