Identifying data space accessed inside a block.

[harish c]

Hi All,

I am going through the paper https://dl.acm.org/doi/10.1145/1345206.1345210 to implement data movement between memories.

This paper talks about Automatic Data Management in Scratchpad Memories in GPUs. The part I'm interested is in identifying the data that needs to be moved.

In this paper, a framework takes iteration spaces and access functions of all array references to derive data space accessed by a reference in a statement (Section 3.1). I understood the theory behind it, but don't know how to actually derive (to get data accessed) this programmatically (in isl). Can someone guide me on this.

Thanks in advance.

Regards,

Harish C

[Harish]

Thank you for Michael, I'll try contacting the authors.

On Tue, May 25, 2021 at 11:54 PM Michael Kruse <Michae...@meinersbur.de> wrote:

Hi Harish C,

the paper you are referring to does not use Polly. Did you consider
contacting the authors directly? If your question is how to do in isl
what the authors did in PolyLib, consider the isl mailing list
(https://groups.google.com/g/isl-development).

Michael

> --
> You received this message because you are subscribed to the Google Groups "Polly Development" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to polly-dev+...@googlegroups.com.
> To view this discussion on the web, visit https://groups.google.com/d/msgid/polly-dev/0e3503cb-6c9d-45f2-aebe-b0cced19c770n%40googlegroups.com.



--
Tardyzentrismus verboten!

[Harish]

Dear Michael,

Apologies for not framing it correctly earlier; please bear with me. I will provide a little context with an example of what I'm trying to achieve here and need your expertise to guide me.

I'm writing a SCOP pass to identify the memory access for a loop.

AST dump:

:: isl ast :: main :: %for.body---%for.end

if (1)
    for (int c0 = 0; c0 <= 1023; c0 += 4) { //loop1
      for (int c1 = 0; c1 <= 3; c1 += 1) //loop2
        Stmt0(c0 + c1);
    }
else
    {  /* original code */ }

Statement dump:

    Statements {
    	Stmt6
            Domain :=
                { Stmt6[i0, i1] : 0 <= i0 <= 255 and 0 <= i1 <= 3 };
            Schedule :=
                { Stmt6[i0, i1] -> [i0, i1] };
            MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
                { Stmt6[i0, i1] -> MemRef0[4i0 + i1] };
            Instructions {
                  %p_conv = sitofp i32 %2 to float
                  store float %p_conv, float* %scevgep, align 4, !alias.scope !2, !noalias !4
            }
    }

Memory access dump:

{ MemRef0[i0] : i0 >= 0 and i0 <= 1023 }

Expected output:

if (1)
    for (int c0 = 0; c0 <= 1023; c0 += 4) { //loop1
      //calculate data access required for loop2
      //{ MemRef0[i0] : i0 >= c0 and i0 <= c0+4 }
      for (int c1 = 0; c1 <= 3; c1 += 1) //loop2
        Stmt0(c0 + c1);
    }
else
    {  /* original code */ }

Questions:

• Is it possible to get the data accessed by the loop2 alone? When I tried to dump the memory accessed, I got the memory required for the whole block (loop1 and loop2).

I'm new to the polyhedral model and finding it difficult to understand it properly. It would be beneficial if you could guide me.

Thanks in advance.

Regards,

Harish C

[Michael Kruse]

Am Fr., 28. Mai 2021 um 00:42 Uhr schrieb Harish <haris...@gmail.com>:
> Is it possible to get the data accessed by the loop2 alone? When I tried to dump the memory accessed, I got the memory required for the whole block (loop1 and loop2).

thanks for providing more context. To get the set of memory accessed
by any i1 (dimension of outer loop), for any i0 (dimension of outer
loop), use the project_out function. You may want to intersect with
the statement's domain to only get accesses that are actually
executed:

https://tinyurl.com/u7azd79c

Important note 1: The identifier `c0` only exists in the generated
code, but not in the internal domain/access/schedule tree
representation. Loops are represented by schedule tree bands.

Important note 2: The AST output is after the rescheduling
transformations. i0,i1,.. etc. of the domain and array access
correspond to loops in the IR representation. To work on loops of the
out, you need to work on the schedule tree (or union_map schedule).

Michael


--
Tardyzentrismus verboten!

[Harish]

This is exactly what I'm looking for. Thank you so much :)

BTW are there any polly irc channels where i can post my questions?   

Regards,

Harish C

[Michael Kruse]

Am Fr., 28. Mai 2021 um 11:48 Uhr schrieb Harish <haris...@gmail.com>:
> BTW are there any polly irc channels where i can post my questions?

You could try LLVM's IRC, but I am rarely online.

Michael

--
Tardyzentrismus verboten!

[Harish]

Thanks! You're of great help.

[Harish]

Dear Michael,

Is it possible to get the lower and upper bounds of the accessed memory as llvm::Value? 

{i0→MemRef0(o0)∣0≤i0≤255∧4i0≤o0≤3+4i0}

Expected output:

For the above map,i need bounds for o0 as llvm::Value:

lower bound  : 4*i0

upper bound : 3+4*i0

Thanks in advance.

Regards,

Harish C

[Michael Kruse]

For getting an llvm::Value, you first need to convert the set into an isl(_pw)_aff. For instance, project-out all the dimensions you are not interested and get the lexical minimum/maximum ( isl_set_lexmax_pw_multi_add, isl_set_lexmin_pw_multi_aff). Convert the result to an isl_multi_pw_aff using isl_multi_pw_add_from_pw_multi_aff, then get the isl_pw_aff from it using isl_pw_multi_aff_get_pw_aff.

You can generate an llvm::Value from an isl_pw_aff using isl_ast_build_expr_from_pw_aff and IslExprBuilder::create.

Michael

--

Tardyzentrismus verboten!

[Harish]

Thanks a lot. 

[Harish]

I've tried your suggestions and have a few more questions.

1. Does isl_ast_build_expr_from_pw_aff work only on sets? When I tried it on the map, I got a "spaces don't match" error.

2. So, I tried to get bounds by just taking the range(MemRef0) of below map:

 {i0→MemRef0(o0)∣0≤i0≤255∧4i0≤o0≤3+4i0}

Dump:

{ [i0] -> MemRef0[o0] : i0 >= 0 and i0 <= 255 and o0 >= 4i0 and o0 <= 3 + 4i0 }
i64 0 ; lower bound
i64 1023 ; upper bound

3. I was expecting in  terms of i0, something like below: Is it possible?

lower bound  : 4*i0

upper bound : 3+4*i0

To give you more context, I'm writing a pass to utilize scratchpad memory. Since the capacity is limited, I planned to move just the required data for a single iteration. In the above example, I'll move data between MemRef0[4*i0] and MemRef0[3+4*i0] for the iteration i0.

I am attaching the code for reference. I've added both cases in the code. Appreciate your time for helping in this.

Regards,

Harish C

[Michael Kruse]

Am Di., 8. Juni 2021 um 05:58 Uhr schrieb Harish <haris...@gmail.com>:

I've tried your suggestions and have a few more questions.

1. Does isl_ast_build_expr_from_pw_aff work only on sets? When I tried it on the map, I got a "spaces don't match" error.

The function works in isl_pw_aff objects (not sets). Without knowing how you called it, I cannot tell where the error comes from.

 

2. So, I tried to get bounds by just taking the range(MemRef0) of below map:

 {i0→MemRef0(o0)∣0≤i0≤255∧4i0≤o0≤3+4i0}

Dump:

{ [i0] -> MemRef0[o0] : i0 >= 0 and i0 <= 255 and o0 >= 4i0 and o0 <= 3 + 4i0 }
i64 0 ; lower bound
i64 1023 ; upper bound

I don't see a question

 

3. I was expecting in  terms of i0, something like below: Is it possible?

lower bound  : 4*i0

upper bound : 3+4*i0

Seems you projected-out the i0 dimension. Try using isl_map_lexmin_pw_multi_aff/isl_map_lexmax_pw_multi_aff instead.

 

To give you more context, I'm writing a pass to utilize scratchpad memory. Since the capacity is limited, I planned to move just the required data for a single iteration. In the above example, I'll move data between MemRef0[4*i0] and MemRef0[3+4*i0] for the iteration i0.

PPCG implements something similar for GPU private and shared memory. You might want to take a look at it.

Michael

--

Tardyzentrismus verboten!

[Harish]

Thanks, I'll check it out.