Tools for the Evaluation of HPF Communications

5 Tools for the Evaluation of HPF Communications

In the previous section we have reduced the problem of evaluating HPF communications of a statement S to counting the elements of a set C( S). This section presents the tools used to automatically build C( S) and to count its elements. We illustrate the use of these tools on the following HPF program:

Program MatInit
!HPF$ PROCESSORS P(8,8)                     do i=1,n
!HPF$ TEMPLATE T(n,m)                         do j=1,m
!HPF$ DISTRIBUTE T(CYCLIC,CYCLIC) ONTO P         A(i,j)=B(i) (S1)
  real A(n,m), B(n)                           end do
!HPF$ ALIGN A(i,j) WITH T(i,*)              end do
!HPF$ ALIGN B(i) WITH T(i,1)              end

We have integrated the different tools into an interactive program called CIPOL. CIPOL provides a lisp-like textual interface to the tools, and pretty-prints their results.

5.1 Manipulation of Polyhedra

Our main tool is the polyhedral library developed by Wilde [16]. Most of the operations on polyhedra (union, intersection, image, etc.) are implemented in this library which allows to define a polyhedron by a set of constraints or a set of rays. For our application, we only need the first definition scheme.

The generic sets F_W_{_S}^-1(J) and F_R_{_S}(I) described in the previous section are computed using the image and pre-image functions of the polyhedral library.

The generic sets for our example are:

F_A^-1(j₁,j₂,n,m)= ì
í
î

1£ j₁£ n Ù i₁=j₁

1£ i₂£ m
, F_B(i₁,i₂,n,m)= ì
í
î

1£ i₁£ n Ù j'₁=i₁

j'₂=1
.
The first set means that the i^th row of array A is duplicated on each element of the i^th row of template T. The second set shows that array B is aligned with the first column of template T.

5.2 Using the PIP Software to Compute Inclusion

The evaluation of the non inclusion in definition (2) is not easy to implement since it implies that a generic condition must be verified for each value from a given set. It is simpler to verify an inclusion condition. In this case we just have to verify that a condition is verified for one value from a given set. Hence an inclusion condition can be modelized by an integer programming problem and can be resolved by a software such as PIP (see [8]). So, in place of counting the number of elements in C( S) we compute the number of elements in the following set:

C( S)

JÎ D_T

ì
ï
í
ï
î

(J, S

(I)) | IÎF

-1

(J) , p_T(J)Î p_T(F

(I))

ü
ï
ý
ï
þ

. (5)

The final result is obtained using the following relation:

Card( C( S))= Card

(

JÎ D_T

ì
ï
í
ï
î

(J, S

(I)) | IÎF

-1

(J)

ü
ï
ý
ï
þ

)-Card

æ
è

C( S)

ö
ø

. (6)

The PIP software is able to find the lexicographical minimum of a parametric set of integer vectors defined by a set of linear constraints S(P). It may also take into account linear constraints on the parameters, this other set of constraints C is called the context. We denote by lexmin(C,S(P)) the result computed by PIP. Since the initial set of integer vectors is parametric, PIP does not return an unique vector but a quast (Quasi-Affine Selection Tree). Indeed, the minimum depends on the values of the parameters, hence PIP splits the domain of the parameters in sub-domains on which the minimum can be expressed in a parametric way. If there is no solution for a sub-domain of the parameter space (because for these values of the parameters S(P) is void), PIP denotes by ^ the lack of solution.

Let us solve the following integer program:

lexmin(C,S(I,J)) , C=

ì
ï
í
ï
î

JÎ D_T

IÎF

-1

(J)

, S(I,J)=

ì
í
î

J'ÎF

(I)

p_T(J)=p_T(J')

. (7)

Consider now the sub-domains of the parameter space for which PIP gives a solution other than ^. It is easy to deduce, from what we said about PIP, that the number of elements in these sub-domains is equal to the number of elements in

C( S)

Remember that PIP only deals with linear constraints with respect to the parameters and the variables of the problem. Function p_T involves euclidian divisions but there is a well known method to linearize p_T that may be found in [5]. We just have to introduce three new integer vectors to replace the initial definition (4) of the distribution function by a definition which gives p_T(J) as the solution of the following system (the * operator is an element-wise vector multiplication):

ì
í
î

r_T(J-T

min

)=N*k_T+R Ù N=Q*(P

max

-P

min

)+ p_T(J)-P

min

£ p_T(J) £ P

max

Ù N ³ 0 Ù Q ³ 0 Ù 0 £ R < k_T

. (8)

One may note that N_i gives the block number for T(J) with respect to the ith dimension. The previous system is effectively linear only if k_T and P^max-P^min are constant vectors. Computation of a parametric solution in other cases is left for future work but it is possible to obtain a result by asking the user to provide the values of some key parameters.

Integer program (7) may so be rewritten with only linear constraints.

For our program example MatInit, the template is distributed on the processor grid using two CYCLIC patterns, hence the distribution is defined by:

r_T æ
è

j₁

j₂
ö
ø = æ
è

j₁

j₂
ö
ø , k_T = æ
è

1

1
ö
ø .
The integer problem to solve is lexmin(C(n,m),S(i₁,i₂,j₁,j₂)) with

C(n,m)= {

1£ j₁£ n Ù 1£ j₂£ m Ù i₁=j₁ Ù 1£ i₂£ m
,

S(i₁,i₂,j₁,j₂)= ì
ï
í
ï
î

j'₁=i₁ Ù j'₂=1 Ù 1£ p₁£ 8 Ù 1£ p₂£ 8

j₁-1=8q₁+p₁-1 Ù j₂-1=8q₂+p₂-1

j'₁-1=8q'₁+p₁-1 Ù j'₂-1=8q'₂+p₂-1

q₁³ 0 Ù q₂³ 0 Ù q'₁³ 0 Ù q'₂³ 0
.

One may note that, in this example, there is no variable representing the remainder in the division by k_T (as R in (8)) since the block sizes are equal to 1. The result of PIP is that there exists a solution not equal to ^ in the polyhedron defined by:

C
(n,m)= {

1£ j₁£ n Ù 1£ j₂£ m Ù i₁=j₁ Ù 1£ i₂£ m Ù j₂-1=8q Ù q³ 0
.
The new parameter q is used to express that j₂-1 must be a multiple of 8.

5.3 Counting the Elements of the Communication Set

The last stage of our method consists in counting the number of integer vectors in the sub-domains computed by PIP. These parametric sub-domains D(I,J,P) are defined in function of a parameter J representing the subscript of a general template element T(J), in function of a parameter I which represents the subscript of an operation storing a value on T(J) and in function of a vector of program parameters P. We need to compute the number of integer vectors in D(I,J,P) in function of the program parameters. Fortunately, Loechner and Wilde have extended the polyhedron library to include a function able to count the number of integer vectors in a parametric polyhedron (see [4]). Like PIP, this function splits the parameter space in sub-domains on which the result can be given by a parametric expression. Hence, to apply relation (6) one has to implement an addition on Quasts.

For the example MatInit the final result (in the context n³ 1 and m³ 1) is

Count(C(n,m))- Count(

C
(n,m)) = n.m æ
ç
ç
ç
ç
ç
è

7m

8
- é
ê
ê
ë 0,

7

8
,

3

4
,

5

8
,

1

2
,

3

8
,

1

4
,

1

8
ù
ú
ú
û

m
ö
÷
÷
÷
÷
÷
ø
The brackets on the previous expression denote a periodic number: if we denote by v the vector (0,7/8,3/4,5/8,1/2, 3/8,1/4,1/8), the value of the periodic number is v_m%8.

When the parameter m is a multiple of 8 we have the expected result of 7n.m²/8 atomic communications at the template level.

For a detailled description of how the pre-evaluation can be done in an automatic way take a look at the report available at the URL
ftp://ftp.lifl.fr/pub/reports/AS-publi/an98/as-182.ps.gz