[llvm-exegesis] Opcode stabilization / reclusterization (PR40715)
Summary:
Given an instruction `Opcode`, we can make benchmarks (measurements) of the
instruction characteristics/performance. Then, to facilitate further analysis
we group the benchmarks with *similar* characteristics into clusters.
Now, this is all not entirely deterministic. Some instructions have variable
characteristics, depending on their arguments. And thus, if we do several
benchmarks of the same instruction `Opcode`, we may end up with *different*
performance characteristics measurements. And when we then do clustering,
these several benchmarks of the same instruction `Opcode` may end up being
clustered into *different* clusters. This is not great for further analysis.
We shall find every `Opcode` with benchmarks not in just one cluster, and move
*all* the benchmarks of said `Opcode` into one new unstable cluster per `Opcode`.
I have solved this by making `ClusterId` a bit field, adding a `IsUnstable` bit,
and introducing `-analysis-display-unstable-clusters` switch to toggle between
displaying stable-only clusters and unstable-only clusters.
The reclusterization is deterministically stable, produces identical reports
between runs. (Or at least that is what i'm seeing, maybe it isn't)
Timings/comparisons:
old (current trunk/head) {F8303582}
```
$ perf stat -r 25 ./bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-old.html
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-old.html'
...
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-old.html'
Performance counter stats for './bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-old.html' (25 runs):
6624.73 msec task-clock # 0.999 CPUs utilized ( +- 0.53% )
172 context-switches # 25.965 M/sec ( +- 29.89% )
0 cpu-migrations # 0.042 M/sec ( +- 56.54% )
31073 page-faults # 4690.754 M/sec ( +- 0.08% )
26538711696 cycles # 4006230.292 GHz ( +- 0.53% ) (83.31%)
2017496807 stalled-cycles-frontend # 7.60% frontend cycles idle ( +- 0.93% ) (83.32%)
13403650062 stalled-cycles-backend # 50.51% backend cycles idle ( +- 0.33% ) (33.37%)
19770706799 instructions # 0.74 insn per cycle
# 0.68 stalled cycles per insn ( +- 0.04% ) (50.04%)
4419821812 branches # 667207369.714 M/sec ( +- 0.03% ) (66.69%)
121741669 branch-misses # 2.75% of all branches ( +- 0.28% ) (83.34%)
6.6283 +- 0.0358 seconds time elapsed ( +- 0.54% )
```
patch, with reclustering but without filtering (i.e. outputting all the stable *and* unstable clusters) {F8303586}
```
$ perf stat -r 25 ./bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-new-all.html
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-new-all.html'
...
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-new-all.html'
Performance counter stats for './bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-new-all.html' (25 runs):
6475.29 msec task-clock # 0.999 CPUs utilized ( +- 0.31% )
213 context-switches # 32.952 M/sec ( +- 23.81% )
1 cpu-migrations # 0.130 M/sec ( +- 43.84% )
31287 page-faults # 4832.057 M/sec ( +- 0.08% )
25939086577 cycles # 4006160.279 GHz ( +- 0.31% ) (83.31%)
1958812858 stalled-cycles-frontend # 7.55% frontend cycles idle ( +- 0.68% ) (83.32%)
13218961512 stalled-cycles-backend # 50.96% backend cycles idle ( +- 0.29% ) (33.37%)
19752995402 instructions # 0.76 insn per cycle
# 0.67 stalled cycles per insn ( +- 0.04% ) (50.04%)
4417079244 branches # 682195472.305 M/sec ( +- 0.03% ) (66.70%)
121510065 branch-misses # 2.75% of all branches ( +- 0.19% ) (83.34%)
6.4832 +- 0.0229 seconds time elapsed ( +- 0.35% )
```
Funnily, *this* measurement shows that said reclustering actually improved performance.
patch, with reclustering, only the stable clusters {F8303594}
```
$ perf stat -r 25 ./bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-new-stable.html
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-new-stable.html'
...
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-new-stable.html'
Performance counter stats for './bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-new-stable.html' (25 runs):
6387.71 msec task-clock # 0.999 CPUs utilized ( +- 0.13% )
133 context-switches # 20.792 M/sec ( +- 23.39% )
0 cpu-migrations # 0.063 M/sec ( +- 61.24% )
31318 page-faults # 4903.256 M/sec ( +- 0.08% )
25591984967 cycles # 4006786.266 GHz ( +- 0.13% ) (83.31%)
1881234904 stalled-cycles-frontend # 7.35% frontend cycles idle ( +- 0.25% ) (83.33%)
13209749965 stalled-cycles-backend # 51.62% backend cycles idle ( +- 0.16% ) (33.36%)
19767554347 instructions # 0.77 insn per cycle
# 0.67 stalled cycles per insn ( +- 0.04% ) (50.03%)
4417480305 branches # 691618858.046 M/sec ( +- 0.03% ) (66.68%)
118676358 branch-misses # 2.69% of all branches ( +- 0.07% ) (83.33%)
6.3954 +- 0.0118 seconds time elapsed ( +- 0.18% )
```
Performance improved even further?! Makes sense i guess, less clusters to print.
patch, with reclustering, only the unstable clusters {F8303601}
```
$ perf stat -r 25 ./bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-new-unstable.html -analysis-display-unstable-clusters
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-new-unstable.html'
...
no exegesis target for x86_64-unknown-linux-gnu, using default
Parsed 43970 benchmark points
Printing sched class consistency analysis results to file '/tmp/clusters-new-unstable.html'
Performance counter stats for './bin/llvm-exegesis -mode=analysis -analysis-epsilon=0.5 -benchmarks-file=/home/lebedevri/PileDriver-Sched/benchmarks-inverse_throughput.yaml -analysis-inconsistencies-output-file=/tmp/clusters-new-unstable.html -analysis-display-unstable-clusters' (25 runs):
6124.96 msec task-clock # 1.000 CPUs utilized ( +- 0.20% )
194 context-switches # 31.709 M/sec ( +- 20.46% )
0 cpu-migrations # 0.039 M/sec ( +- 49.77% )
31413 page-faults # 5129.261 M/sec ( +- 0.06% )
24536794267 cycles # 4006425.858 GHz ( +- 0.19% ) (83.31%)
1676085087 stalled-cycles-frontend # 6.83% frontend cycles idle ( +- 0.46% ) (83.32%)
13035595603 stalled-cycles-backend # 53.13% backend cycles idle ( +- 0.16% ) (33.36%)
18260877653 instructions # 0.74 insn per cycle
# 0.71 stalled cycles per insn ( +- 0.05% ) (50.03%)
4112411983 branches # 671484364.603 M/sec ( +- 0.03% ) (66.68%)
114066929 branch-misses # 2.77% of all branches ( +- 0.11% ) (83.32%)
6.1278 +- 0.0121 seconds time elapsed ( +- 0.20% )
```
This tells us that the actual `-analysis-inconsistencies-output-file=` outputting only takes ~0.4 sec for 43970 benchmark points (3 whole sweeps)
(Also, wow this is fast, it used to take several minutes originally)
Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=40715 | PR40715 ]].
Reviewers: courbet, gchatelet
Reviewed By: courbet
Subscribers: tschuett, jdoerfert, llvm-commits, RKSimon
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D58355
llvm-svn: 354441
diff --git a/llvm/tools/llvm-exegesis/lib/Clustering.cpp b/llvm/tools/llvm-exegesis/lib/Clustering.cpp
index 36e6c5b..bebb535 100644
--- a/llvm/tools/llvm-exegesis/lib/Clustering.cpp
+++ b/llvm/tools/llvm-exegesis/lib/Clustering.cpp
@@ -8,8 +8,11 @@
#include "Clustering.h"
#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
+#include <algorithm>
#include <string>
+#include <vector>
namespace llvm {
namespace exegesis {
@@ -147,10 +150,102 @@
}
}
+// Given an instruction Opcode, we can make benchmarks (measurements) of the
+// instruction characteristics/performance. Then, to facilitate further analysis
+// we group the benchmarks with *similar* characteristics into clusters.
+// Now, this is all not entirely deterministic. Some instructions have variable
+// characteristics, depending on their arguments. And thus, if we do several
+// benchmarks of the same instruction Opcode, we may end up with *different*
+// performance characteristics measurements. And when we then do clustering,
+// these several benchmarks of the same instruction Opcode may end up being
+// clustered into *different* clusters. This is not great for further analysis.
+// We shall find every opcode with benchmarks not in just one cluster, and move
+// *all* the benchmarks of said Opcode into one new unstable cluster per Opcode.
+void InstructionBenchmarkClustering::stabilize(unsigned NumOpcodes) {
+ // Given an instruction Opcode, in which clusters do benchmarks of this
+ // instruction lie? Normally, they all should be in the same cluster.
+ std::vector<llvm::SmallSet<ClusterId, 1>> OpcodeToClusterIDs;
+ OpcodeToClusterIDs.resize(NumOpcodes);
+ // The list of opcodes that have more than one cluster.
+ llvm::SetVector<size_t> UnstableOpcodes;
+ // Populate OpcodeToClusterIDs and UnstableOpcodes data structures.
+ assert(ClusterIdForPoint_.size() == Points_.size() && "size mismatch");
+ for (const auto &Point : zip(Points_, ClusterIdForPoint_)) {
+ const ClusterId &ClusterIdOfPoint = std::get<1>(Point);
+ if (!ClusterIdOfPoint.isValid())
+ continue; // Only process fully valid clusters.
+ const unsigned Opcode = std::get<0>(Point).keyInstruction().getOpcode();
+ assert(Opcode < NumOpcodes && "NumOpcodes is incorrect (too small)");
+ llvm::SmallSet<ClusterId, 1> &ClusterIDsOfOpcode =
+ OpcodeToClusterIDs[Opcode];
+ ClusterIDsOfOpcode.insert(ClusterIdOfPoint);
+ // Is there more than one ClusterID for this opcode?.
+ if (ClusterIDsOfOpcode.size() < 2)
+ continue; // If not, then at this moment this Opcode is stable.
+ // Else let's record this unstable opcode for future use.
+ UnstableOpcodes.insert(Opcode);
+ }
+ assert(OpcodeToClusterIDs.size() == NumOpcodes && "sanity check");
+
+ // We know with how many [new] clusters we will end up with.
+ const auto NewTotalClusterCount = Clusters_.size() + UnstableOpcodes.size();
+ Clusters_.reserve(NewTotalClusterCount);
+ for (const size_t UnstableOpcode : UnstableOpcodes.getArrayRef()) {
+ const llvm::SmallSet<ClusterId, 1> &ClusterIDs =
+ OpcodeToClusterIDs[UnstableOpcode];
+ assert(ClusterIDs.size() > 1 &&
+ "Should only have Opcodes with more than one cluster.");
+
+ // Create a new unstable cluster, one per Opcode.
+ Clusters_.emplace_back(ClusterId::makeValidUnstable(Clusters_.size()));
+ Cluster &UnstableCluster = Clusters_.back();
+ // We will find *at least* one point in each of these clusters.
+ UnstableCluster.PointIndices.reserve(ClusterIDs.size());
+
+ // Go through every cluster which we recorded as containing benchmarks
+ // of this UnstableOpcode. NOTE: we only recorded valid clusters.
+ for (const ClusterId &CID : ClusterIDs) {
+ assert(CID.isValid() &&
+ "We only recorded valid clusters, not noise/error clusters.");
+ Cluster &OldCluster = Clusters_[CID.getId()]; // Valid clusters storage.
+ // Within each cluster, go through each point, and either move it to the
+ // new unstable cluster, or 'keep' it.
+ // In this case, we'll reshuffle OldCluster.PointIndices vector
+ // so that all the points that are *not* for UnstableOpcode are first,
+ // and the rest of the points is for the UnstableOpcode.
+ const auto it = std::stable_partition(
+ OldCluster.PointIndices.begin(), OldCluster.PointIndices.end(),
+ [this, UnstableOpcode](size_t P) {
+ return Points_[P].keyInstruction().getOpcode() != UnstableOpcode;
+ });
+ assert(std::distance(it, OldCluster.PointIndices.end()) > 0 &&
+ "Should have found at least one bad point");
+ // Mark to-be-moved points as belonging to the new cluster.
+ std::for_each(it, OldCluster.PointIndices.end(),
+ [this, &UnstableCluster](size_t P) {
+ ClusterIdForPoint_[P] = UnstableCluster.Id;
+ });
+ // Actually append to-be-moved points to the new cluster.
+ UnstableCluster.PointIndices.insert(UnstableCluster.PointIndices.cend(),
+ it, OldCluster.PointIndices.end());
+ // And finally, remove "to-be-moved" points form the old cluster.
+ OldCluster.PointIndices.erase(it, OldCluster.PointIndices.cend());
+ // Now, the old cluster may end up being empty, but let's just keep it
+ // in whatever state it ended up. Purging empty clusters isn't worth it.
+ };
+ assert(UnstableCluster.PointIndices.size() > 1 &&
+ "New unstable cluster should end up with more than one point.");
+ assert(UnstableCluster.PointIndices.size() >= ClusterIDs.size() &&
+ "New unstable cluster should end up with no less points than there "
+ "was clusters");
+ }
+ assert(Clusters_.size() == NewTotalClusterCount && "sanity check");
+}
+
llvm::Expected<InstructionBenchmarkClustering>
InstructionBenchmarkClustering::create(
const std::vector<InstructionBenchmark> &Points, const size_t MinPts,
- const double Epsilon) {
+ const double Epsilon, llvm::Optional<unsigned> NumOpcodes) {
InstructionBenchmarkClustering Clustering(Points, Epsilon * Epsilon);
if (auto Error = Clustering.validateAndSetup()) {
return std::move(Error);
@@ -160,6 +255,10 @@
}
Clustering.dbScan(MinPts);
+
+ if (NumOpcodes.hasValue())
+ Clustering.stabilize(NumOpcodes.getValue());
+
return Clustering;
}