subject ：Counting Integer Points in Parametric Polytopes Using Barvinok’s Rational Functions
Time ：2007
meeting / Periodical ：Algorithmica
Research Institute ：

Barvinok

Abstract

Many compiler optimization techniques rely on the ability to calculate the number of elements that meet certain conditions . If these conditions can be expressed by linear constraints , Then these problems are equivalent to calculation （ Possible ） Parametric polyhedron parametric polytopes The number of integer points in .

as everyone knows , The enumerator of such a set can be represented by an explicit function composed of a set of quasi polynomials , Every quasi polynomial is related to a chamber in the parameter space chamber Related to . before , Interpolation is used to obtain these quasi polynomials , But this technology has several disadvantages . Its worst-case calculation time for a single quasi polynomial is the exponent of the input size , Even for fixed dimensions . The worst case size of this quasi polynomial （ The unit is the number of digits required to express the quasi polynomial ） It is also the index of input size . on certain conditions , This technology can't even produce a solution .

Our main contribution is a new method for analytical computation of quasi polynomials . It extends the Barvinok Existing methods of decomposition , Used to calculate the number of integer points in nonparametric polyhedron . Our technique always produces a solution and computes the enumerator of polynomial size in polynomial time （ For fixed dimensions ）.

Key Words. Barvinok’s decomposition, Compiler analysis, Ehrhart quasi-polynomial, Parametric polytope, Polyhedral model, Vector partition function, Signed unimodular decomposition.

1. Introduction

In many program analyses and optimizations, questions starting with “how many” need to be answered, e.g.,
– How many memory locations are touched by a loop? [23]
– How many operations are performed by a loop? [35]
– How many cache lines are touched by a loop? [23]
– How many array elements are accessed between two points in time? [7]
– How many array elements are live at a given iteration (i, j)? [1], [2], [34], [52]
– How many times is a statement executed before an iteration (i, j)? [48], [25]
– How many parallel processing elements can be used when executing a loop on an FPGA? [6], [19], [24], [29]
– How many cache misses does a loop generate? [15], [13], [27]
– How much memory is dynamically allocated by a piece of code? [11]
– How many different array elements are accessed before element (x, y) is accessed? [38]
– How many bytes are transmitted between parallel tasks for a given parallel schedule of computation? [10], [30], [47]

Answering these questions is usually one of the cornerstones of program transformation and optimization , For example, increase parallelism [48]、 Minimize memory size [52]、[48]、 Estimate the worst-case execution time [35]、 Estimated energy consumption [33] 、 Improve cache efficiency [7]、DSP Advanced transformation of applications [25], And converting software loops into parallel hardware implementations [48]、[29]. Based on these program analysis , Impressive procedural improvements have been reported , For example, the memory size in the embedded system should be changed from 262400 Bytes reduced to 257 byte [34], take DSP The execution speed of the application is improved 7 times [25], And reduce execution in parallel and distributed NUMA On the machine , Time times 3.5 times [30].

For many of the above analyses , The counting problem is formalized as calculating the number of integer solutions of linear inequality systems , The problem becomes “ How many integer points are there $\vec{x}\in Z_d$ Satisfy $A\vec{x}\ge \vec{b}$？”, among A Is an integer matrix and b Is an integer vector .

Besides , Many analyses require the answer to be certain parameters $\vec{p}$ Function of , Therefore, the number of integer points in the following set must be calculated ：

among $\vec{p}$ Is the parameter vector ,A and B Is an integer matrix ,$\vec{c}$ Is an integer vector . $P_{\vec{p}}$ It is called parametric polyhedron parametric polytope, When satisfied $A\vec{x}\ge B\vec{p}+\vec{c}$ The number of points of is for $\vec{p}$ Each value of It's all limited . Clauss and Loechner [14] indicate ,$P_{\vec{p}}$ The integer points in can be represented by a set of quasi polynomials quasi-polynomials Express , Each quasi polynomial is in a different chamber chamber Effective in . （ These concepts will be discussed in Chapter 2.2 Section explains .） for example , Consider the picture 1 The cycle in , And suppose we want to know the statement t += A[i+j] How many times , use N and M The functional representation of . The answer to this question can be calculated (2) In the formula, the number of integer points is used to calculate ：

Observe inequality , It is equivalent to ：
$$\begin{gathered} i\ge N \\ i\ge N-M \\ i\le N-M+3 \\ j\ge 0 \\ j\le N-2i \end{gathered}$$

The solution to this question is：

with $\lfloor x\rfloor$ the lower integer part of x. This solution contains four chambers, each with a different quasi-polynomial.

# P A collection P Number of elements of .

In some analyses , The need for parameters depends on the problem instance （ for example , In the existential symbol ​​ In the case of circular boundary No ）, In other technologies , for example [7]、[11]、[13]、[23]、[25 ]、[35]、[38] and [48], The counting problem is parametric in nature . An example of the intrinsic parameter counting problem will be in 5.2 Section example 10 Discuss in . It is also an example of a more general counting problem , Some preprocessing is needed to convert it to formula (1) Constraint system . Many of the program analyses cited above [1]、[2]、[7]、[10]、[13]、[15]、[29]、[30]、[33] Similar pretreatment is required .

lately , New technologies have been developed for similar counting problems , But they either don't support parameters , for example [9] and [41], Or only in a very limited range , for example LattE [18]. On the other hand ,Clauss Methods [14] You can really handle parameters , But in the worst case it's exponential , The only known implementation cannot even be for certain categories of problems [48]、[13] Provide solutions .

In this paper , We propose a new method of enumerating parameter polyhedrons , It is a combination of [14] Decompose into chambers decomposition into chambers and [18] Parameter version of the middle counting algorithm a parametric version of the counting algorithm. Compared with the previous method , The resulting algorithm ：
– handles general parametric polytopes of the form (1),
– always produces an answer,
– computes quasi-polynomials that are only polynomially large in terms of the input size (for fixed dimensions), by using a representation for these quasi-polynomials that differs from the one used in [14], and
– computes each of these quasi-polynomials in polynomial time, when the number of variables in the inequalities is fixed.

In the next section , The basic theoretical background will be introduced . The first 3 Section discusses the method used to calculate the number of integer points in polyhedra Barvinok Algorithm . In the 4 In the festival , It introduces Barvinok Algorithm in (1) Application of parameter polyhedron in . The first 5 Section explains the preprocessing required to handle more general counting problems . The comparison with related work is in the 6 Section . For more details about the implementation of the algorithm, see 7 Described in the section . The first 8 Section evaluate our algorithm and compare it with Claus's method , Use a large number of linear inequality systems generated by several compilers analysis . The first 9 Section is the conclusion . This article is about [50] Revised edition .

2. Basic Concepts

In this section we first recall some basic polyhedral definitions. We further recall some theoretical results on polytope enumeration and introduce some new terminology( The term ).

2.1 Basic Polyhedral Definitions

Affine package affine hull Is the smallest affine set containing a set .
Affine set ： For collection $C$, If you pass through the set $C$ The straight lines of any two points in are still gathering $C$ in , So called $C$ It's an affine set .
Reference resources ：https://www.zhihu.com/question/310774959