Representation of piecewise affine schedules in Cloog

[Ana Balevic]

Hello,

I'm just starting with Cloog and would like to add a piecewise affine
schedule to my program.

Can I specify a scattering function like the one below in Cloog?
Otherwise, what's the right way to specify the relationships between
statement sub-domains and elementary scattering functions?

Here's an example schedule for some statement S:
if (i+j <= 10) t(i,j) = i;
else t(i,j) = 10-j;

Thanks in advance for your help.
Ana

[Sven Verdoolaege]

On Tue, Feb 16, 2010 at 01:56:28PM +0100, Ana Balevic wrote:
> Hello,
>
> I'm just starting with Cloog and would like to add a piecewise
> affine schedule to my program.
>
> Can I specify a scattering function like the one below in Cloog?

Are you using the library interface or the file interface?
The library interface should accept union scattering functions.
If it doesn't work, then it's a bug and you should let us know.

> Otherwise, what's the right way to specify the relationships between
> statement sub-domains and elementary scattering functions?
>
> Here's an example schedule for some statement S:
> if (i+j <= 10) t(i,j) = i;
> else t(i,j) = 10-j;

If you are using the file interface, then you can put either

{ [i,j] -> [t] : (i + j <= 10 and t = i) or (i + j > 10 and t = 10 - j) }

or

2

2 5
0 1 -1 0 0
1 0 -1 -1 10

2 5
0 1 0 1 -10
1 0 1 1 -11

where CLooG expects a scattering function.
Note that this will only work if you are using the isl backend.

In any case, you would need the latest git version.

skimo

[Ana Balevic]

Hello,

we're using the file interface (via a jni wrapper), and we have the isl
backend.

With the second variant you gave, I get a [CLooG] ERROR: too many
scattering functions. In file generation code, I have one statement
domain, and add two scattering functions. Please see below the file dump
(note that I had <=5, not 10). Any ideas how to get it through cloog?

Apart from that, I tried splitting the initial statement domain into two
sub-domains by the if condition, and attaching the appropriate elementary
scatterings to each sub-domains. It's not quite clear how to express this
in Cloog. By treating sub-domains as statement domains I managed to get it
through and get a result. Please tell me if it's possible to use
sub-domains; and what's the approach to process code with several
statements and provide appropriate domain-function mappings?

What are the exact relationships between statement domains/subdomains and
scattering functions/elementary scatterings, and what are their
multiplicities? It'd be brilliant if you could explain me this or give me
some doc. :)

Thanks & have a nice weekend
Ana

Cloog file:

# language: C
c

# parameters
1 2
1 1
1

1

# S1: a[i+j] = doSomething(a[i+j])
1
4 4
1 1 0 -1
1 -1 0 4
1 0 1 -1
1 0 -1 4
0 0 0

1
i j
#-------- SCATTERING -------------
2 # number of scattering functions
2 6
# eq/in c0 c1 i j 1
0 1 0 -1 0 0
1 0 0 -1 -1 5
2 6
# eq/in c0 c1 i j 1
0 1 0 0 1 -5
1 0 0 1 1 -6
0

--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

[Sven Verdoolaege]

On Fri, Feb 19, 2010 at 04:57:54PM +0100, Ana Balevic wrote:
> Hello,
>

> we're using the file interface (via a jni wrapper), and we have the
> isl backend.
>
> With the second variant you gave, I get a [CLooG] ERROR: too many
> scattering functions. In file generation code, I have one statement
> domain, and add two scattering functions. Please see below the file
> dump (note that I had <=5, not 10). Any ideas how to get it through
> cloog?

The number of scattering functions should be equal to the number
of domains as each scattering function corresponds to a domain.
However, each scattering function itself can be a union.
So, the scattering function part of your input would look like this:

#-------- SCATTERING -------------
1 # number of scattering functions
2
2 5
# eq/in c0 i j 1

0 1 -1 0 0

1 0 -1 -1 5
2 5
# eq/in c0 i j 1
0 1 0 1 -5
1 0 1 1 -6
0

(Note that I also removed an unconstrained scattering dimension;
I assume you didn't mean to have it, because it will give you
infinite loops.)

> Apart from that, I tried splitting the initial statement domain into
> two sub-domains by the if condition, and attaching the appropriate
> elementary scatterings to each sub-domains. It's not quite clear how
> to express this in Cloog. By treating sub-domains as statement
> domains I managed to get it through and get a result. Please tell me
> if it's possible to use sub-domains; and what's the approach to
> process code with several statements and provide appropriate
> domain-function mappings?

I don't know what you mean. Any subset of a domain is also a domain.
You always need to specify as many scattering functions as domains.
So if after whatever transformation you do, you end up with two
domains, then you need to specify two scattering functions.
I don't see the problem.

skimo

[Ana Balevic]

Hello Sven,

Thank you very much for the example and sorry for answering a bit late.
Your reply is quite helpful. Let me just check few more things with you:

1) Zero at the end - does it signal end of list of scattering functions,
or end of each scattering function?
2) Provided that I have two statements, two scattering functions, where
the first s.f. is simple t=0, and the second s.f. is composed of two
elementary functions like in previous example, can I express it as follows:

#-------- SCATTERING -------------
2 # number of scattering functions
1 # first scattering function has only one elementary s. function

# eq/in c0 i j 1

0 1 0 0 0
2 # second scattering function has 2 elementary s. functions

2 5
# eq/in c0 i j 1
0 1 -1 0 0
1 0 -1 -1 5
2 5
# eq/in c0 i j 1
0 1 0 1 -5
1 0 1 1 -6

0 #signal end of scattering function list

> I don't know what you mean. Any subset of a domain is also a domain.

Yes, of course, I was confused by the cardinality of relationships, but I
think that now I have a clearer idea about it. Can you please confirm if
this is correct order of things in Cloog:
- a program has 1 or more statements
- each statement has 0 or 1 scattering functions
- each scattering function is composed of 1 or more elementary scattering
functions
- each elementary scattering function has 1 or more expressions (schedule
definitions or conditions for sub-domain)
and
- each statement is associated with 1 domain (if the schedule splits it in
two sub-domains, the situation is handled by adding a constraint to the
elementary scattering functions)

Thanks for a reply in advance~!

Cheers,
Ana

[Uday Kumar Reddy]

Hello Ana,

> 1) Zero at the end - does it signal end of list of scattering functions, or end > of each scattering function?

A 0 at the end says that no names have been specified for scattering functions, i.e., the new loop iterators/IVs. Since the number of
scattering functions is already specified, Cloog doesn't need anything more to signal end.

>  Provided that I have two statements, two scattering functions, where the >first s.f. is simple t=0, and the second s.f. is composed of two elementary >functions like in previous example, can I express it as follows:

Yes.

-- Uday

--

You got this message because you subscribed to the CLooG mailing list.
To send messages to this list, use cl...@googlegroups.com
To stop subscribing, send a mail to cloog+un...@googlegroups.com
For more options and to visit the group, http://groups.google.fr/group/cloog?hl=en

[Uday Kumar Reddy]

On Sat, Mar 13, 2010 at 3:06 PM, Ana Balevic <bal...@liacs.nl> wrote:

Hello Sven,

Thank you very much for the example and sorry for answering a bit late.
Your reply is quite helpful. Let me just check few more things with you:

1) Zero at the end - does it signal end of list of scattering functions, or end of each scattering function?
2) Provided that I have two statements, two scattering functions, where the first s.f. is simple t=0, and the second s.f. is composed of two elementary functions like in previous example, can I express it as follows:

 #-------- SCATTERING -------------
 2 # number of scattering functions

 1 # first scattering function has only one elementary s. function

 # eq/in c0 i j 1

      0 1  0 0 0
 2 # second scattering function has 2 elementary s. functions

 2 5
 # eq/in c0 i j 1
      0 1 -1 0 0
      1 0 -1 -1 5
 2 5
 # eq/in c0 i j 1
      0 1 0 1 -5
      1 0 1 1 -6

 0 #signal end of scattering function list

Yes, of course, I was confused by the cardinality of relationships, but I think that now I have a clearer idea about it. Can you please confirm if this is correct order of things in Cloog:
- a program has 1 or more statements
- each statement has 0 or 1 scattering functions

Either there are no scattering functions or every statement has one scattering function (which could be be piece-wise).  You can't have some statements without any scattering function and some with; otherwise, given the current file format, Cloog wouldn't know the domains that have no 

associated scattering functions.

 

- each scattering function is composed of 1 or more elementary scattering functions
- each elementary scattering function has 1 or more expressions (schedule definitions or conditions for sub-domain)
 and

The dimensionality of the scattering function should be the same for each statement. Note that this does not lead to any loss in freedom or generality.

 

- each statement is associated with 1 domain (if the schedule splits it in two sub-domains, the situation is handled by adding a constraint to the elementary scattering functions)

A statement can have multiple domains; it's the union of these that is scanned. 

-- Uday

On Sat, Mar 13, 2010 at 3:06 PM, Ana Balevic <bal...@liacs.nl> wrote:

--

[Sven Verdoolaege]

On Sat, Mar 13, 2010 at 09:06:32PM +0100, Ana Balevic wrote:
> Yes, of course, I was confused by the cardinality of relationships,
> but I think that now I have a clearer idea about it. Can you please
> confirm if this is correct order of things in Cloog:
> - a program has 1 or more statements
> - each statement has 0 or 1 scattering functions

Either no scattering functions are specified, or each
statement has exactly one scattering function.

> - each scattering function is composed of 1 or more elementary
> scattering functions
> - each elementary scattering function has 1 or more expressions
> (schedule definitions or conditions for sub-domain)
> and

I'm not sure what expressions you are talking about here.
In any case, the only thing that the isl backend allows
extra compared to the CLooG documentation is that

Scattering ::= Nb_functions Domain_list Naming

is replaced by

Scattering ::= Nb_functions Domain_list' Naming

with

Domain_list' ::= Domain' Domain_list' | (void)
Domain' ::= _Domain | Domain_union

skimo

[Uday Kumar Reddy]

On Tue, Feb 16, 2010 at 8:39 AM, Sven Verdoolaege <skimo...@kotnet.org> wrote:

If you are using the file interface, then you can put either

   { [i,j] -> [t] : (i + j <= 10 and t = i) or (i + j > 10 and t = 10 - j) }

or

   2

   2 5
   0     1    -1     0     0
   1     0    -1    -1    10

   2 5
   0     1     0     1   -10
   1     0     1     1   -11

where CLooG expects a scattering function.

I didn't know this feature was added and now scattering functions could contain inequalities. This looks like an easy way to specify piece-wise 

schedules. But, when a user specifies:

{ [i,j] -> [t] : (i + j <= 10 and t = i) or (i + j >= 12 and t = 10 - j) }

Points with i+j = 11 will not be scanned I assume?

Thanks,

Uday

 

[Sven Verdoolaege]

On Sat, Mar 13, 2010 at 05:37:51PM -0500, Uday Kumar Reddy wrote:
> I didn't know this feature was added and now scattering functions could
> contain inequalities.

This isn't new. Inequalities have always been allowed in the CLooG
input format. It's the (old) scoplib format where inequalities
were no longer allowed. The new scoplib format should restore
that capability.

> This looks like an easy way to specify piece-wise
> schedules. But, when a user specifies:
>
> { [i,j] -> [t] : (i + j <= 10 and t = i) or (i + j >= 12 and t = 10 - j) }
>
> Points with i+j = 11 will not be scanned I assume?

Indeed.

skimo

[Ana Balevic]

super, thanks for such a quick reply!

On Sat, 13 Mar 2010 22:17:58 +0100, Uday Kumar Reddy <uday...@gmail.com>
wrote:

>> cloog+un...@googlegroups.com<cloog%2Bunsu...@googlegroups.com>

>> For more options and to visit the group,
>> http://groups.google.fr/group/cloog?hl=en
>>
>

[Ana Balevic]

There's some issue when we pass this to cloog:

#-------- SCATTERING -------------
1 # number of scattering functions

2 # number of contained elementary scattering functions

2 5
# eq/in c0 i j 1
0 1 -1 0 0
1 0 -1 -1 5
2 5
# eq/in c0 i j 1
0 1 0 1 -5
1 0 1 1 -6
0

Cloog.cloog(s) output:
java: isl_input.c:34: isl_basic_set_read_from_file_polylib: Assertion
`sscanf(line, "%u %u", &n_row, &n_col) == 2' failed.

I tried it on a simple example, and it also doesn't get through

#-------- SCATTERING by ANA-------------

1 # number of scattering functions

1 # number of contained elementary scattering functions
1 5

# eq/in c0 i j 1

0 1 0 0 0
0
Cloog.cloog(s) output:
java: isl_input.c:34: isl_basic_set_read_from_file_polylib: Assertion
`sscanf(line, "%u %u", &n_row, &n_col) == 2' failed.

It looks like the line 2 (# number of contained elementary scattering
functions) gets it confused.
How to make it work with these examples?

Thanks again, Ana

On Sat, 13 Mar 2010 22:17:58 +0100, Uday Kumar Reddy <uday...@gmail.com>
wrote:

> Hello Ana,

>> cloog+un...@googlegroups.com<cloog%2Bunsu...@googlegroups.com>

>> For more options and to visit the group,
>> http://groups.google.fr/group/cloog?hl=en
>>

[Uday Kumar Reddy]

Are you sure you are using the latest git version? I tried your .cloog (also attached).

$ ./cloog piece-wise.cloog                                                                                                                              

/* Generated from piece-wise.cloog by CLooG 0.14.0-271-gaa1e292 gmp bits in 0.00s. */                                                                                               

for (c1=1;c1<=3;c1++) {                                                                                                                                                             

  for (j=1;j<=-c1+5;j++) {                                                                                                                                                          

    S1(c1,j);                                                                                                                                                                       

  }                                                                                                                                                                                 

  for (i=c1+1;i<=4;i++) {                                                                                                                                                           

    S1(i,-c1+5);                                                                                                                                                                    

  }                                                                                                                                                                                 

}

S1(4,1);

$ git describe; (cd isl; git rev-parse HEAD)

cloog-0.14.0-271-gaa1e292

912bfcebab74d8a68b980ec6001895f53d4d706e

If you are not using the git version, please see instructions here to get one:

http://www.bastoul.net/cloog/download.php

  -- Uday

[Ana Balevic]

Hi Uday,

I just tested the git version on my home pc and it does produce the same
result. Thanks for doing the test for me, now I can be sure that at least
my cloog description is OK.

Can you please tell me since which version is there a support for complex
scattering functions? I'll have to check what we have at work and if it
could be updated.

Thanks & have a good week
Ana

On Sun, 14 Mar 2010 03:15:43 +0100, Uday Kumar Reddy <uday...@gmail.com>
wrote:

>>>> <cloog%2Bunsu...@googlegroups.com<cloog%252Buns...@googlegroups.com>

>>>> >
>>>>
>>>> For more options and to visit the group,
>>>> http://groups.google.fr/group/cloog?hl=en
>>>>
>>>>
>>
>> --
>> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>>
>

[Sven Verdoolaege]

On Sun, Mar 21, 2010 at 10:23:41PM +0100, Ana Balevic wrote:
> Can you please tell me since which version is there a support for
> complex scattering functions? I'll have to check what we have at
> work and if it could be updated.

According the commit message, that should be cloog-0.14.0-266-gd34f16e,
but it may not have worked properly back then, so
cloog-0.14.0-270-g7ee1261 may be the first version in which it actually
worked. In any case, it's best to just use the latest version.

skimo