previous_group previous up next next_group
Previous: 1. Benchmarking Conventions Up: 2. Constitution of a Next: 3. Execution Time Measurements

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
\begin{figure}
\centering\epsfig {file=Figures/polybench_schema.eps,width=15cm}\end{figure}

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)$.


previous_group previous up next next_group
Previous: 1. Benchmarking Conventions Up: 2. Constitution of a Next: 3. Execution Time Measurements
Nguyen Que Duong
2006-09-16