2. POLYBENCH Overview

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 $(1)$. 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 $(2)$. 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 $(3)$. This database is compressed because it is quite large: over $20$ GB. Then we apply some sampling for each sub-database in order to reduce the number of constraint systems to be tested when needed $(4)$. 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 $(4)$ (see 6_subsec:polyhedral_databases).

Figure 7: POLYBENCH's schema

The databases contain operands for most available implementations of polyhedral operators, such as LINEAR $C^3$ [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 $(5,6,7)$, then display the comparisons in graphical form $(9)$. We also analyze some characteristics of those databases $(8)$.