Identifying Set (parallel) blocks during AST Generation

[Pedro Silvestre]

Hello,

I am using isl to find a schedule for some (computationally heavy) statements using the schedule constraints interface. The resulting schedule trees contain both Sequence and Set nodes. 

Set nodes, as I understand, do not impose any ordering on their subtrees, while Sequence nodes do. I wish to take advantage of this.

During AST generation, however, the AST emitted by isl contains only block nodes, which are a sequence of statements. Thus, I cannot tell if two statements which are in the same block could actually be executed in parallel (e.g. using a fork-join paradigm).

What I would like to find is some way to differentiate which statements in a block AST node can actually be executed in parallel.  

Perhaps I am fundamentally misunderstanding Set nodes, but I cannot find any way to achieve this.

Ideally, for my use-case, this would be achieved by having isl generate blocks inside blocks, tagging those blocks whose inner statements can be executed in parallel with some tag which I could later find while processing the AST.

Thank you in advance for those that offer advice on achieving this.

Best,

Pedro

[Pedro Silvestre]

Let me perhaps add that the option "ast_build_group_coscheduled" seems related. 

It's description can be found at page 245 of the user manual:

"If two domain elements are assigned the same schedule point, then they may be
executed in any order and they may even appear in different loops. If this options
is set, then the AST generator will make sure that coscheduled domain elements
do not appear in separate parts of the AST. [...]"

However, I am not clear on how I could use it to achieve what I want.

[Sven Verdoolaege]

The AST generator does indeed generate sequence and set nodes in the same way.
So, if you want to add such tags, you should do it on the schedule tree.
You could, for example, add mark nodes on top of the (grand)children
of the set node. These will be preserved by the AST generator
(as AST mark nodes) and you can then exploit them while printing the AST.
If any further manipulation is needed during the AST generation,
you can also use before_each_mark/after_each_mark callbacks.

skimo

[Pedro Silvestre]

Hi Sven,

Thank you for the help. I followed something similar to your advice. 

I'll report my attempt for future users searching for a similar solution. I'd also appreciate any input as to whether this is valid, or if I'm creating an invalid AST.

1. After obtaining a ScheduleTree, use map_schedule_node_bottom_up to modify it.
   1. The callback should check for Set Nodes and use insert_mark to insert a mark above the Set nodes
2. During AST generation, check for mark nodes.
   1. If a mark node is seen, then:
      1. If the child node is a block, each AST child (e.g. user, if_) of that block can be executed in parallel.
      2. If the child is not a block node (e.g. user) then ignore the mark and proceed to child.

I hope this is semantically valid, but haven't tested actually executing parallel blocks in parallel. 

I've attached some diagrams of an example ScheduleTree before and after applying the mark mapping, as well as, my translated ast.

(Note that the domains of Domain nodes are not empty, I'm just not printing them)

Best,

Pedro 

[Sven Verdoolaege]

On Mon, Feb 12, 2024 at 10:05:14AM -0800, Pedro Silvestre wrote:
> Hi Sven,
>
> Thank you for the help. I followed something similar to your advice.
> I'll report my attempt for future users searching for a similar solution.
> I'd also appreciate any input as to whether this is valid, or if I'm
> creating an invalid AST.
>
>

> 1. After obtaining a ScheduleTree, use map_schedule_node_bottom_up to
> modify it.
> 1. The callback should check for Set Nodes and use insert_mark to

> insert a mark above the Set nodes

I think it's safer to put the marks on the children (of the filter nodes),
as I suggested.
The AST generator could in theory exploit the set node and
overlap the children in any way it sees fit,
even though I don't think it currently does anything like that.
For example, it could (again, in theory) turn a set with sequence children
into a sequence with set children.

skimo