Page MenuHomePhabricator

[MCA] Highlight kernel bottlenecks in the summary view.
ClosedPublic

Authored by andreadb on Feb 27 2019, 10:58 AM.

Details

Summary

This patch adds a new flag named -bottleneck-analysis to print out information about throughput bottlenecks.

MCA knows how to identify and classify dynamic dispatch stalls. However, it doesn't know how to analyze and highlight kernel bottlenecks.
The goal of this patch is to teach MCA how to correlate increases in backend pressure to backend stalls (and therefore, the loss of throughput).

From a Scheduler point of view, backend pressure is a function of the scheduler buffer usage (i.e. how the number of uOps in the scheduler buffers changes over time). Backend pressure increases (or decreases) when there is a mismatch between the number of opcodes dispatched, and the number of opcodes issued in the same cycle.
Since buffer resources are limited, continuous increases in backend pressure would eventually leads to dispatch stalls. So, there is a strong correlation between dispatch stalls, and how backpressure changed over time.

This patch teaches how to identify situations where backend pressure increases due to:

  • unavailable pipeline resources.
  • data dependencies.

Data dependencies may delay execution of instructions and therefore increase the time that uOps have to spend in the scheduler buffers. That often translates to an increase in backend pressure which may eventually lead to a bottleneck.
Contention on pipeline resources may also delay execution of instructions, and lead to a temporary increase in backend pressure.

Internally, the Scheduler classifies instructions based on whether register/memory operands are available or not.

An instruction is marked as "ready to execute" only if data dependencies are fully resolved.
Every cycle, the Scheduler attempts to execute all instructions that are ready to execute. If an instruction cannot execute because of unavailable pipeline resources, then the Scheduler internally updates a BusyResourceUnits mask with the ID of each unavailable resource.

ExecuteStage is responsible for tracking changes in backend pressure. If backend pressure increases during a cycle because of contention on pipeline resources, then ExecuteStage sends a "backend pressure" event to the listeners.
That event would contain information about instructions delayed by resource pressure, as well as the BusyResourceUnits mask.

Note that ExecuteStage also knows how to identify situations where backpressure increased because of delays introduced by data dependencies.

The SummaryView observes "backend pressure" events and prints out a "bottleneck report".

Example of bottleneck report:

Cycles with backend pressure increase [ 99.89% ]
Throughput Bottlenecks:
  Resource Pressure       [ 0.00% ]
  Data Dependencies:      [ 99.89% ]
   - Register Dependencies [ 0.00% ]
   - Memory Dependencies   [ 99.89% ]

A bottleneck report is printed out only if increases in backend pressure eventually caused backend stalls.

About the time complexity:
The average slowdown tends to be in the range of ~5-6%.

Time complexity is linear in the number of instructions in the Scheduler::PendingSet.
For memory intensive kernels, the slowdown can be significant if flag -noalias=false is specified. In the worst case scenario I have observed a slowdown of ~30% when flag -noalias=false was specified.
We can definitely recover part of that slowdown if we optimize class LSUnit (by doing extra bookkeeping to speedup queries).

This new analysis is disabled by default, and it can be enabled via flag -bottleneck-analysis.
Users of MCA as a library can enable the generation of pressure events through the constructor of ExecuteStage.

This patch partially addresses https://bugs.llvm.org/show_bug.cgi?id=37494
A follow up patch will extend the "scheduler-stats" view to also print out:

  • the most problematic register dependencies (top 3)
  • the most problematic memory dependencies (top 3)
  • instructions mostly affected by bottlenecks caused by pipeline pressures (top 3).

That change plus this patch should fully address PR37494.

Let me know if okay to commit.

-Andrea

Diff Detail

Event Timeline

andreadb created this revision.Feb 27 2019, 10:58 AM
ormris added a subscriber: ormris.Feb 27 2019, 11:28 AM
lebedev.ri added inline comments.Feb 27 2019, 12:34 PM
include/llvm/MCA/HWEventListener.h
143
HWPressureEvent(GenericReason reason,

?

147

GenericReason?

lib/MCA/HardwareUnits/Scheduler.cpp
232–233

Isn't ReadySet a std::vector?
It would be best to do something like Insts.insert(Insts.end(), ReadySet.begin(), ReadySet.end());
E.g. because this way you avoid constant reallocations since you tell beforehand the amount of entries you want to insert.

mattd accepted this revision.Feb 27 2019, 2:59 PM

I like this and think users will find it very helpful. The changes seem sensible to me; however, I had a few nits... mostly stylistic things, no big deals. Anyways, I'll mark this patch as accept, as long as you cover the suggestions made by @lebedev.ri.

include/llvm/MCA/Stages/ExecuteStage.h
33

Where is 'DispatchStallCycle' used? I see it initialized, but not accessed anywhere in this patch.

35

'True if this stage should notify listeners of HWPressureEvents'

lib/MCA/HardwareUnits/Scheduler.cpp
186

As a side note, perhaps we should consider addding a getDesc() accessor to InstRef. The pattern getInstruction().getDesc() or similar, is used throughout MCA.

250

Suggestion: Remove the last 'continue' and add an 'else { RegDeps.emplace_back(IR); }'

tools/llvm-mca/Views/SummaryView.cpp
28

Perhaps we should introduce a constructor to struct BackPressureInfo that initializes the instance, instead of explicitly zeroing the members here.

70

Seems like the case of INVALID should never occur. If my assumption is true, should we toss in an assert here?

tools/llvm-mca/llvm-mca.cpp
180

s/the fault/default/

This revision is now accepted and ready to land.Feb 27 2019, 2:59 PM
andreadb edited the summary of this revision. (Show Details)Feb 28 2019, 3:45 AM
andreadb updated this revision to Diff 188708.Feb 28 2019, 4:30 AM
andreadb marked 17 inline comments as done.

Patch updated.

Addressed review comments.

mattd accepted this revision.Mar 1 2019, 10:29 AM
RKSimon accepted this revision.Mar 3 2019, 6:08 AM

LGTM

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMar 4 2019, 3:52 AM