thr3ads.net - llvm dev - [LLVMdev] Question about load clustering in the machine scheduler [Mar 2015]

If this information is useful, please help other people find it:
Share via:

Tom Stellard

2015-Mar-27 14:52 UTC

[LLVMdev] Question about load clustering in the machine scheduler

On Thu, Mar 26, 2015 at 11:50:20PM -0700, Andrew Trick
wrote:> 
> > On Mar 26, 2015, at 7:36 PM, Tom Stellard <tom at stellard.net>
wrote:
> > 
> > Hi,
> > 
> > I have a program with over 100 loads (each with a 10 cycle latency)
> > at the beginning of the program, and I can't figure out how to get
> > the machine scheduler to intermix ALU instructions with the loads to
> > effectively hide the latency.
> > 
> > It seems the issue is with load clustering.  I restrict load
clustering
> > to 4 at a time, but when I look at the debug output, the loads are
> > always being scheduled based on the fact that that are clustered. e.g.
> > 
> > Pick Top CLUSTER
> > Scheduling SU(10) %vreg13<def> = S_BUFFER_LOAD_DWORD_IMM %vreg9,
4; mem:LD4[<unknown>] SGPR_32:%vreg13 SReg_128:%vreg9
> 
> Well, only 4 loads in a sequence should have the “cluster” edges. You
should be able to see that when the DAG is printed before scheduling.
> 
There are 4 consecutive 'Pick Top CLUSTER' then a 'Pick Top
WEAK' and
then the pattern repeats itself.  All of these are loads.
> Even without that limit, stalls take precedence over load clustering. So
when you run out of load resources (15?) the scheduler should choose something
else.
> 
Is this the code that checks for stalls?

  if (tryLess(Zone.getLatencyStallCycles(TryCand.SU),
              Zone.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))


It is disabled if (!SU->isUnbuffered)


> > I have a feeling there is something wrong with my machine model in the
> > R600 backend, but I've experimented with a few variations of it
and have
> > been unable to solve this problem.  Does anyone have any idea what I
> > might be doing wrong?
> 
> Sorry, not without actually looking through the debug output. The output
lists the cycle time at each instruction, so you can see where the scheduler
thinks the stalls are.
> 
There are actually 31 resources defined for loads.  However, there
aren't actually 31 load units in the hardware.  There is 1 load unit
that can hold up to 31 loads waiting to be executed, but only 1 load
can be executed at a time.



Pick Top CLUSTER   
Scheduling SU(43) %vreg46<def> = S_BUFFER_LOAD_DWORD_IMM %vreg9, 48;
mem:LD4[<unknown>] SGPR_32:%vreg46 SReg_128:%vreg9
  SReg_32: 45 > 44(+ 0 livethru)
  VS_32: 51 > 18(+ 0 livethru)
  Ready @46c
  HWLGKM +1x105u
  TopQ.A BotLatency SU(43) 78c
  *** Max MOps 1 at cycle 46
Cycle: 47 TopQ.A
TopQ.A @47c
  Retired: 47
  Executed: 47c
  Critical: 47c, 47 MOps
  ExpectedLatency: 10c
  - Latency limited.
BotQ.A RemLatency SU(1698) 99c
  TopQ.A + Remain MOps: 1692
TopQ.A RemLatency SU(201) 97c
  BotQ.A + Remain MOps: 1647
BotQ.A: 1698 1694 1695


Here is example debugging output which.  Where is the cycle time
here?

> BTW- I just checked in a small fix for in-order scheduling that might make
debugging this easier.
> 
I will take a look at this.

Thanks,
Tom
> Andy
> 
> > Here are my resource definitions from lib/Target/R600/SISchedule.td
> > 
> > // BufferSize = 0 means the processors are in-order.
> > let BufferSize = 0 in {
> > 
> > // XXX: Are the resource counts correct?
> > def HWBranch : ProcResource<1>;  
> > def HWExport : ProcResource<7>;   // Taken from S_WAITCNT
> > def HWLGKM   : ProcResource<31>;  // Taken from S_WAITCNT
> > def HWSALU   : ProcResource<1>;  
> > def HWVMEM   : ProcResource<15>;  // Taken from S_WAITCNT
> > def HWVALU   : ProcResource<1>;
> > 
> > }
> 
> > 
> > Thanks,
> > Tom
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Andrew Trick

2015-Mar-27 19:20 UTC

head link

[LLVMdev] Question about load clustering in the machine scheduler

> On Mar 27, 2015, at 7:52 AM, Tom Stellard <tom at stellard.net>
wrote:
> 
> On Thu, Mar 26, 2015 at 11:50:20PM -0700, Andrew Trick wrote:
>> 
>>> On Mar 26, 2015, at 7:36 PM, Tom Stellard <tom at
stellard.net> wrote:
>>> 
>>> Hi,
>>> 
>>> I have a program with over 100 loads (each with a 10 cycle latency)
>>> at the beginning of the program, and I can't figure out how to
get
>>> the machine scheduler to intermix ALU instructions with the loads
to
>>> effectively hide the latency.
>>> 
>>> It seems the issue is with load clustering.  I restrict load
clustering
>>> to 4 at a time, but when I look at the debug output, the loads are
>>> always being scheduled based on the fact that that are clustered.
e.g.
>>> 
>>> Pick Top CLUSTER
>>> Scheduling SU(10) %vreg13<def> = S_BUFFER_LOAD_DWORD_IMM
%vreg9, 4; mem:LD4[<unknown>] SGPR_32:%vreg13 SReg_128:%vreg9
>> 
>> Well, only 4 loads in a sequence should have the “cluster” edges. You
should be able to see that when the DAG is printed before scheduling.
>> 
> 
> There are 4 consecutive 'Pick Top CLUSTER' then a 'Pick Top
WEAK' and
> then the pattern repeats itself.  All of these are loads.
It sounds like someone has created weak edges to the other non-load instructions
that are ready to schedule, preventing them from being prioritized before the
loads. In the generic scheduler, I think that is only done for copy instructions
to try eliminating interference so the copy can be removed. I don't know why
that would apply to your case.
>> Even without that limit, stalls take precedence over load clustering.
So when you run out of load resources (15?) the scheduler should choose
something else.
>> 
> 
> Is this the code that checks for stalls?
> 
>  if (tryLess(Zone.getLatencyStallCycles(TryCand.SU),
>              Zone.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
> 
> 
> It is disabled if (!SU->isUnbuffered)
Oh right, in your case the loads should not even be in the ready queue unless
there are free resources. But according to your model that is 31 loads. At any
rate, this is not really the issue since your model thinks it can only schedule
one instruction per cycle anyway.
>>> I have a feeling there is something wrong with my machine model in
the
>>> R600 backend, but I've experimented with a few variations of it
and have
>>> been unable to solve this problem.  Does anyone have any idea what
I
>>> might be doing wrong?
>> 
>> Sorry, not without actually looking through the debug output. The
output lists the cycle time at each instruction, so you can see where the
scheduler thinks the stalls are.
>> 
> 
> There are actually 31 resources defined for loads.  However, there
> aren't actually 31 load units in the hardware.  There is 1 load unit
> that can hold up to 31 loads waiting to be executed, but only 1 load
> can be executed at a time.
It's not really clear how to model GPU hardware in terms of a simple
single-cpu in-order machine model. I guess the question is whether you want 31
loads to be scheduled without counting any extra cycles for waiting for the busy
load unit.

It sounds like you're running the GenericScheduler with the SI machine
model. We do want to make sure that works as advertised and fix bugs. On the
other hand, I'm sure you know that the generic heuristics probably
aren't very effective on your target. I thought you were using
R600SchedStrategy?
> Pick Top CLUSTER   
> Scheduling SU(43) %vreg46<def> = S_BUFFER_LOAD_DWORD_IMM %vreg9, 48;
mem:LD4[<unknown>] SGPR_32:%vreg46 SReg_128:%vreg9
>  SReg_32: 45 > 44(+ 0 livethru)
>  VS_32: 51 > 18(+ 0 livethru)
>  Ready @46c
>  HWLGKM +1x105u
>  TopQ.A BotLatency SU(43) 78c
>  *** Max MOps 1 at cycle 46
> Cycle: 47 TopQ.A
The scheduler thinks it will take 47 cycles to execute the instructions that
have been scheduled so far from the top of the schedule.

Andy
> TopQ.A @47c
>  Retired: 47
>  Executed: 47c
>  Critical: 47c, 47 MOps
>  ExpectedLatency: 10c
>  - Latency limited.
> BotQ.A RemLatency SU(1698) 99c
>  TopQ.A + Remain MOps: 1692
> TopQ.A RemLatency SU(201) 97c
>  BotQ.A + Remain MOps: 1647
> BotQ.A: 1698 1694 1695
> 
> 
> Here is example debugging output which.  Where is the cycle time
> here?
> 
> 
>> BTW- I just checked in a small fix for in-order scheduling that might
make debugging this easier.
>> 
> 
> I will take a look at this.
> 
> Thanks,
> Tom
> 
>> Andy
>> 
>>> Here are my resource definitions from lib/Target/R600/SISchedule.td
>>> 
>>> // BufferSize = 0 means the processors are in-order.
>>> let BufferSize = 0 in {
>>> 
>>> // XXX: Are the resource counts correct?
>>> def HWBranch : ProcResource<1>;  
>>> def HWExport : ProcResource<7>;   // Taken from S_WAITCNT
>>> def HWLGKM   : ProcResource<31>;  // Taken from S_WAITCNT
>>> def HWSALU   : ProcResource<1>;  
>>> def HWVMEM   : ProcResource<15>;  // Taken from S_WAITCNT
>>> def HWVALU   : ProcResource<1>;
>>> 
>>> }
>> 
>>> 
>>> Thanks,
>>> Tom
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150327/4fbd9492/attachment.html>

Tom Stellard

2015-Mar-27 19:36 UTC

head link

[LLVMdev] Question about load clustering in the machine scheduler

On Fri, Mar 27, 2015 at 12:20:06PM -0700, Andrew Trick
wrote:> 
> > On Mar 27, 2015, at 7:52 AM, Tom Stellard <tom at stellard.net>
wrote:
> > 
> > On Thu, Mar 26, 2015 at 11:50:20PM -0700, Andrew Trick wrote:
> >> 
> >>> On Mar 26, 2015, at 7:36 PM, Tom Stellard <tom at
stellard.net> wrote:
> >>> 
> >>> Hi,
> >>> 
> >>> I have a program with over 100 loads (each with a 10 cycle
latency)
> >>> at the beginning of the program, and I can't figure out
how to get
> >>> the machine scheduler to intermix ALU instructions with the
loads to
> >>> effectively hide the latency.
> >>> 
> >>> It seems the issue is with load clustering.  I restrict load
clustering
> >>> to 4 at a time, but when I look at the debug output, the loads
are
> >>> always being scheduled based on the fact that that are
clustered. e.g.
> >>> 
> >>> Pick Top CLUSTER
> >>> Scheduling SU(10) %vreg13<def> = S_BUFFER_LOAD_DWORD_IMM
%vreg9, 4; mem:LD4[<unknown>] SGPR_32:%vreg13 SReg_128:%vreg9
> >> 
> >> Well, only 4 loads in a sequence should have the “cluster” edges.
You should be able to see that when the DAG is printed before scheduling.
> >> 
> > 
> > There are 4 consecutive 'Pick Top CLUSTER' then a 'Pick
Top WEAK' and
> > then the pattern repeats itself.  All of these are loads.
> 
> It sounds like someone has created weak edges to the other non-load
instructions that are ready to schedule, preventing them from being prioritized
before the loads. In the generic scheduler, I think that is only done for copy
instructions to try eliminating interference so the copy can be removed. I
don't know why that would apply to your case.
> 
> >> Even without that limit, stalls take precedence over load
clustering. So when you run out of load resources (15?) the scheduler should
choose something else.
> >> 
> > 
> > Is this the code that checks for stalls?
> > 
> >  if (tryLess(Zone.getLatencyStallCycles(TryCand.SU),
> >              Zone.getLatencyStallCycles(Cand.SU), TryCand, Cand,
Stall))
> > 
> > 
> > It is disabled if (!SU->isUnbuffered)
> 
> Oh right, in your case the loads should not even be in the ready queue
unless there are free resources. But according to your model that is 31 loads.
At any rate, this is not really the issue since your model thinks it can only
schedule one instruction per cycle anyway.
>
I was able to get this working as expected by defining IssueWidth and
MicroOpBufferSize in the SIMachineModel:


class SIModel : SchedMachineModel {
  let IssueWidth = 8;
  let MicroOpBufferSize = 32;
}

This isn't quite correct, though, because the real IssueWidth depends on
what kinds of instructions are issued and there isn't a global buffer
for MicroOps, each resource has its own buffer.
> >>> I have a feeling there is something wrong with my machine
model in the
> >>> R600 backend, but I've experimented with a few variations
of it and have
> >>> been unable to solve this problem.  Does anyone have any idea
what I
> >>> might be doing wrong?
> >> 
> >> Sorry, not without actually looking through the debug output. The
output lists the cycle time at each instruction, so you can see where the
scheduler thinks the stalls are.
> >> 
> > 
> > There are actually 31 resources defined for loads.  However, there
> > aren't actually 31 load units in the hardware.  There is 1 load
unit
> > that can hold up to 31 loads waiting to be executed, but only 1 load
> > can be executed at a time.
> 
> It's not really clear how to model GPU hardware in terms of a simple
single-cpu in-order machine model. I guess the question is whether you want 31
loads to be scheduled without counting any extra cycles for waiting for the busy
load unit.
> 
> It sounds like you're running the GenericScheduler with the SI machine
model. We do want to make sure that works as advertised and fix bugs. On the
other hand, I'm sure you know that the generic heuristics probably
aren't very effective on your target. I thought you were using
R600SchedStrategy?
> 
R600SchedStrategy is only for older GPUs.  SI and newer uses the generic
scheduler.  The generic scheduler has worked pretty well so far for SI,
which is more similar to traditional CPUs than the older VLIW GPUs.

-Tom
> > Pick Top CLUSTER   
> > Scheduling SU(43) %vreg46<def> = S_BUFFER_LOAD_DWORD_IMM %vreg9,
48; mem:LD4[<unknown>] SGPR_32:%vreg46 SReg_128:%vreg9
> >  SReg_32: 45 > 44(+ 0 livethru)
> >  VS_32: 51 > 18(+ 0 livethru)
> >  Ready @46c
> >  HWLGKM +1x105u
> >  TopQ.A BotLatency SU(43) 78c
> >  *** Max MOps 1 at cycle 46
> > Cycle: 47 TopQ.A
> 
> The scheduler thinks it will take 47 cycles to execute the instructions
that have been scheduled so far from the top of the schedule.
> 
> Andy
> 
> > TopQ.A @47c
> >  Retired: 47
> >  Executed: 47c
> >  Critical: 47c, 47 MOps
> >  ExpectedLatency: 10c
> >  - Latency limited.
> > BotQ.A RemLatency SU(1698) 99c
> >  TopQ.A + Remain MOps: 1692
> > TopQ.A RemLatency SU(201) 97c
> >  BotQ.A + Remain MOps: 1647
> > BotQ.A: 1698 1694 1695
> > 
> > 
> > Here is example debugging output which.  Where is the cycle time
> > here?
> > 
> > 
> >> BTW- I just checked in a small fix for in-order scheduling that
might make debugging this easier.
> >> 
> > 
> > I will take a look at this.
> > 
> > Thanks,
> > Tom
> > 
> >> Andy
> >> 
> >>> Here are my resource definitions from
lib/Target/R600/SISchedule.td
> >>> 
> >>> // BufferSize = 0 means the processors are in-order.
> >>> let BufferSize = 0 in {
> >>> 
> >>> // XXX: Are the resource counts correct?
> >>> def HWBranch : ProcResource<1>;  
> >>> def HWExport : ProcResource<7>;   // Taken from
S_WAITCNT
> >>> def HWLGKM   : ProcResource<31>;  // Taken from
S_WAITCNT
> >>> def HWSALU   : ProcResource<1>;  
> >>> def HWVMEM   : ProcResource<15>;  // Taken from
S_WAITCNT
> >>> def HWVALU   : ProcResource<1>;
> >>> 
> >>> }
> >> 
> >>> 
> >>> Thanks,
> >>> Tom
> >>> _______________________________________________
> >>> LLVM Developers mailing list
> >>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

llvm dev - Mar 2015 - [LLVMdev] Question about load clustering in the machine scheduler

[LLVMdev] Question about load clustering in the machine scheduler

[LLVMdev] Question about load clustering in the machine scheduler

[LLVMdev] Question about load clustering in the machine scheduler