Page MenuHomePhabricator

[AMDGPU] Implement dependency heuristic for prioritizing candidate SchedGroups for a given pipeline instruction.
Needs ReviewPublic

Authored by jrbyrnes on Sep 15 2022, 12:19 PM.

Details

Summary

Since we assign the instructions in top-down order, the relevant dependency for a given instruction is its predecessors. For each instruction, we track which SchedGroup its predecessors have been assigned to (if any). When deciding which SchedGroups to prioritize for an instruction, we look at the last (in top-down order) SchedGroup assigned for all its predecessors. We prioritize candidate SchedGroups that occur at or after (in top-down order) that SchedGroup. These SchedGroups will be the earliest possible SchedGroups that do not violate dependencies. Next, we look at the second-to-last SchedGroup assigned to an instructions predecessors. We prioritize candidate SchedGroups that occur at or after that SchedGroup. These SchedGroups will be earliest possible SchedGroups that violate one dependency. And so on.

This heuristic is much less computationally expensive than the cost heuristic. Additionally, we expect it to produce a good search order in the general case, but perhaps not as good as the cost heuristic. The search order will likely get better once we have a more intelligent processing order of pipeline instructions.

This patch also does a little bit to consolidate handling of heuristics.

Change-Id: I47b9e89f154b98a00cb54d30b1ed5ba34d29d11d

Diff Detail

Unit TestsFailed

TimeTest
2,290 msx64 debian > AddressSanitizer-x86_64-linux-dynamic.TestCases/Linux::uar_signals.cpp
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -shared-libasan -std=c++11 -O1 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/Linux/uar_signals.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxDynamicConfig/TestCases/Linux/Output/uar_signals.cpp.tmp -pthread && /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxDynamicConfig/TestCases/Linux/Output/uar_signals.cpp.tmp

Event Timeline

jrbyrnes created this revision.Sep 15 2022, 12:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 15 2022, 12:19 PM
jrbyrnes requested review of this revision.Sep 15 2022, 12:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 15 2022, 12:19 PM
jrbyrnes updated this revision to Diff 460480.Sep 15 2022, 12:22 PM

Add comment for new function