llvm dev - Feb 2018 - [VLIW Scheduler] Itineraries vs. per operand scheduling

Hi,

What is the best way to model a scheduler for a VLIW in-order architecture?
I've looked at the Hexagon and R600 architectures and they are using
itineraries. I wanted to understand the benefit in using itineraries over the
per operand scheduling.

I also found this thread from almost 2 years ago:
http://lists.llvm.org/pipermail/llvm-dev/2016-April/098763.html

At that time it seemed the itineraries are a better choice, but is it still the
case?
Also, in this thread Phil says:
"Some of the constraints that can be found in in-order micro architectures
cannot be expressed in the per-operand scheduling model"
Does anybody have an example of such constraints that will be harder to model
with per operand scheduling?

Thanks,
Marina
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180204/3ef88d19/attachment-0001.html>

>
> I also found this thread from almost 2 years ago:
>
> http://lists.llvm.org/pipermail/llvm-dev/2016-April/098763.html
>
>
>
> At that time it seemed the itineraries are a better choice, but is it
> still the case?
>
> Also, in this thread Phil says:
>
> “Some of the constraints that can be found in in-order micro architectures
> cannot be expressed in the per-operand scheduling model”
>
> Does anybody have an example of such constraints that will be harder to
> model with per operand scheduling?
>
​From the thread you provided, it says

ARM might be a good start for generic superscalar. Hexagon for VLIW style
scheduling.​


​Anyway, I also interest in knowing their difference. :-)

Regards,
chenwj​


-- 
Wei-Ren Chen (陳韋任)
Homepage: https://people.cs.nctu.edu.tw/~chenwj
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180205/6a5dbdd0/attachment.html>

> On Feb 4, 2018, at 9:15 AM, Yatsina, Marina via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
>  
> What is the best way to model a scheduler for a VLIW in-order architecture?
> I’ve looked at the Hexagon and R600 architectures and they are using
itineraries. I wanted to understand the benefit in using itineraries over the
per operand scheduling.
>  
> I also found this thread from almost 2 years ago:
> http://lists.llvm.org/pipermail/llvm-dev/2016-April/098763.html
<http://lists.llvm.org/pipermail/llvm-dev/2016-April/098763.html>
>  
> At that time it seemed the itineraries are a better choice, but is it still
the case?
> Also, in this thread Phil says:
> “Some of the constraints that can be found in in-order micro architectures
cannot be expressed in the per-operand scheduling model”
> Does anybody have an example of such constraints that will be harder to
model with per operand scheduling?
>  
> Thanks,
> Marina
Hi Marina,

Itineraries have stuck around mainly because no one was interested in porting
old itineraries to a new machine description. At least initially, there also
wasn't anyone interested in working on an in-order scheduling implementation
based on the new machine model, even though the machine description itself was
designed for in-order scheduling. There are a handful of targets now using the
new model with MicroOpBufferSize = 0/1 (in-order mode). It's hard for me to
say how widely supported it is, because so many backends using the
MachineScheduler are out-of-tree.

The per-operand model should be much more compile time efficient, but that's
often not a concern. It can be easier now to incrementally bootstrap new machine
descriptions based on similar machines with the same architecture. The subtarget
details no longer need to be tied to the TableGen instruction descriptions. The
new model lets you define the structure of the subtarget scheduling description,
so it can be self-documenting. The new model lets you use a plethora of tablegen
tricks to handle all the variations on vector operations. I believe it's
much more straightfoward to specify special constraints, like bypassing.
It's fairly easy to extend certain opcodes with predicates (callbacks) that
depend on immediate values or any other arbtrary info.

See Javed and Florian's tutorial on the "new" machine model:
https://www.youtube.com/watch?v=brpomKUynEA

Itineraries are not strictly more powerful. The original motivation for the new
machine description is that there were important issue constraints that
weren't being correctly modeled by the itineraries. The only advantage of
itineraries that I'm aware of is that, for instructions that use multiple
machine resources, you can control during which cycle those resources are used
relative to each other (it specifies a full resource matrix for each op). The
per-operand model makes the simplifying assumption that a given resource is
simply used for N cycles. Normally, all instructions begin using a given
resource on the same cycle relative to instruction issue, so that's not an
innaccurate assumption. If you actually need to correct for that, and don't
use itineraries then you need to make use of the the MachineScheduler's
hooks to write a little custom scheduling code.

Whatever you do, there's no sense in using both kinds of machine
descriptions. Support is only there for the purpose of bootstrapping using ARM
A9, since that was the latest in-tree ARM cpu at the time. It's just useless
complexity now.

-Andy

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180207/036bb809/attachment.html>

Hi Krzysztof,

2018-02-08 13:32 GMT+08:00 Andrew Trick via llvm-dev <
llvm-dev at lists.llvm.org>:
>
>
> On Feb 4, 2018, at 9:15 AM, Yatsina, Marina via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hi,
>
> What is the best way to model a scheduler for a VLIW in-order architecture?
> I’ve looked at the Hexagon and R600 architectures and they are using
> itineraries. I wanted to understand the benefit in using itineraries over
> the per operand scheduling.
>
> ​Do you have time to give comment on why Hexagon still use itineraries,
rather than switching to per operand scheduling like ARM does? I really
like to hear your opinion.

Thanks.​ :-)

-- 
Wei-Ren Chen (陳韋任)
Homepage: https://people.cs.nctu.edu.tw/~chenwj
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180208/92667e0c/attachment.html>

Thank you so much for the detailed answer!
Our target only uses one resource at a time, so based on what you said,
itineraries do not have any advantage over the new scheduling model.
The per operand model seems to be the way to go.

Thanks,
Marina
From: Andrew Trick [mailto:atrick at apple.com]
Sent: Thursday, February 08, 2018 07:33
To: Yatsina, Marina <marina.yatsina at intel.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] [VLIW Scheduler] Itineraries vs. per operand scheduling




On Feb 4, 2018, at 9:15 AM, Yatsina, Marina via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi,

What is the best way to model a scheduler for a VLIW in-order architecture?
I’ve looked at the Hexagon and R600 architectures and they are using
itineraries. I wanted to understand the benefit in using itineraries over the
per operand scheduling.

I also found this thread from almost 2 years ago:
http://lists.llvm.org/pipermail/llvm-dev/2016-April/098763.html

At that time it seemed the itineraries are a better choice, but is it still the
case?
Also, in this thread Phil says:
“Some of the constraints that can be found in in-order micro architectures
cannot be expressed in the per-operand scheduling model”
Does anybody have an example of such constraints that will be harder to model
with per operand scheduling?

Thanks,
Marina

Hi Marina,

Itineraries have stuck around mainly because no one was interested in porting
old itineraries to a new machine description. At least initially, there also
wasn't anyone interested in working on an in-order scheduling implementation
based on the new machine model, even though the machine description itself was
designed for in-order scheduling. There are a handful of targets now using the
new model with MicroOpBufferSize = 0/1 (in-order mode). It's hard for me to
say how widely supported it is, because so many backends using the
MachineScheduler are out-of-tree.

The per-operand model should be much more compile time efficient, but that's
often not a concern. It can be easier now to incrementally bootstrap new machine
descriptions based on similar machines with the same architecture. The subtarget
details no longer need to be tied to the TableGen instruction descriptions. The
new model lets you define the structure of the subtarget scheduling description,
so it can be self-documenting. The new model lets you use a plethora of tablegen
tricks to handle all the variations on vector operations. I believe it's
much more straightfoward to specify special constraints, like bypassing.
It's fairly easy to extend certain opcodes with predicates (callbacks) that
depend on immediate values or any other arbtrary info.

See Javed and Florian's tutorial on the "new" machine model:
https://www.youtube.com/watch?v=brpomKUynEA

Itineraries are not strictly more powerful. The original motivation for the new
machine description is that there were important issue constraints that
weren't being correctly modeled by the itineraries. The only advantage of
itineraries that I'm aware of is that, for instructions that use multiple
machine resources, you can control during which cycle those resources are used
relative to each other (it specifies a full resource matrix for each op). The
per-operand model makes the simplifying assumption that a given resource is
simply used for N cycles. Normally, all instructions begin using a given
resource on the same cycle relative to instruction issue, so that's not an
innaccurate assumption. If you actually need to correct for that, and don't
use itineraries then you need to make use of the the MachineScheduler's
hooks to write a little custom scheduling code.

Whatever you do, there's no sense in using both kinds of machine
descriptions. Support is only there for the purpose of bootstrapping using ARM
A9, since that was the latest in-tree ARM cpu at the time. It's just useless
complexity now.

-Andy

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180211/f6f9047c/attachment.html>