SimEng icon indicating copy to clipboard operation
SimEng copied to clipboard

Updating Branch Predictors to replace hash-map with Fetch Target Queue

Open ABenC377 opened this issue 1 year ago • 0 comments

This update to the branch predictors (both Perceptron and Generic) replaces the hashmap that was previously being used to keep previous-state information between predict and update with a queue (called a Fetch Target Queue or FTQ) of previous-state information for the in-flight branches. The FTQ allows speculative updating of the global history (which is also included in this PR).

In terms of performance, it seems to be quite lateral. a full breakdown of stats across our benchmark suite is provided below. To summarise the results, most benchmarks have an improved misprediction rate with the update, but the changes in execution time are hit and miss with many becoming a bit slower (probably due to an increased number of interactions with the branch predictor through the pipeline).

I think this is still a worthwhile change to make to SimEng even though there isn't a clear-cut performance upgrade because it makes the flow of branches through the branch predictor more regular and so should facilitate more complicated branch predictors in the future (e.g., TAGE).

Benchmark GP time GP mispredict GP + FTQ time GP + FTQ mispredict Performance change (percentage) Mispredict change (raw)
CloverLeaf serial gcc8.3.0 armv8.4 251655 35.70% 162159 +26.20% -35.56% ✅ -9.50% ✅
CloverLeaf serial gcc9.3.0 armv8.4 171576 34.50% 160908 +25.90% -6.22% ✅ -8.60% ✅
CloverLeaf serial gcc10.3.0 armv8.4 173001 36.70% 158659 +27.60% -8.29% ✅ -9.10% ✅
CloverLeaf serial armclang20 armv8.4 142201 31.60% 136051 +25.00% -4.32% ✅ -6.60% ✅
CloverLeaf openmp gcc8.3.0 armv8.4 227772 34.60% 209607 +25.40% -7.98% ✅ -9.20% ✅
CloverLeaf openmp gcc9.3.0 armv8.4 225624 33.50% 210659 +24.70% -6.63% ✅ -8.80% ✅
CloverLeaf openmp gcc10.3.0 armv8.4 226401 34.50% 210617 +25.00% -6.97% ✅ -9.50% ✅
CloverLeaf openmp armclang20 armv8.4 193129 31.60% 178385 +23.10% -7.63% ✅ -8.50% ✅
miniBUDE openmp gcc8.3.0 armv8.4 201411 9.96% 219208 +8.34% +8.84% ❌ -1.62% ✅
miniBUDE openmp gcc9.3.0 armv8.4 201666 9.93% 219094 +8.53% +8.64% ❌ -1.40% ✅
miniBUDE openmp gcc10.3.0 armv8.4 201324 10% 219502 +8.53% +9.03% ❌ -1.47% ✅
miniBUDE openmp armclang20 armv8.4 183828 11.60% 199540 +10.50% +8.55% ❌ -1.10% ✅
STREAM serial gcc8.3.0 armv8.4 74849 0.62% 85893 +1.39% +14.76% ❌ +0.77% ❌
STREAM serial gcc9.3.0 armv8.4 76025 0.94% 85933 +1.31% +13.03% ❌ +0.37% ❌
STREAM serial gcc10.3.0 armv8.4 76237 0.65% 85774 +1.49% +12.51% ❌ +0.84% ❌
STREAM serial armclang20 armv8.4 84461 1.16% 93544 +2.71% +10.75% ❌ +1.55% ❌
STREAM openmp gcc8.3.0 armv8.4 129391 11.50% 124696 +2.98% -3.63% ✅ -8.52% ✅
STREAM openmp gcc9.3.0 armv8.4 127899 11% 122549 +2.73% -4.18% ✅ -8.27% ✅
STREAM openmp gcc10.3.0 armv8.4 126097 11.40% 123878 +4.08% -1.76% ✅ -7.32% ✅
STREAM openmp armclang20 armv8.4 131196 14.40% 128109 +5.26% -2.35% ✅ -9.14% ✅
TeaLeaf 2D serial gcc8.3.0 armv8.4 128641 24.90% 134308 +17.10% +4.41% ❌ -7.80% ✅
TeaLeaf 2D serial gcc9.3.0 armv8.4 127964 25% 134974 +17.00% +5.48% ❌ -8.00% ✅
TeaLeaf 2D serial gcc10.3.0 armv8.4 129052 24.90% 134227 +17.20% +4.01% ❌ -7.70% ✅
TeaLeaf 2D serial armclang20 armv8.4 233988 13.40% 246787 +12.50% +5.47% ❌ -0.90% ✅
TeaLeaf 2D openmp gcc8.3.0 armv8.4 217511 27.60% 188418 +10.60% -13.38% ✅ -17.00% ✅
TeaLeaf 2D openmp gcc9.3.0 armv8.4 214477 25.40% 198443 +10.50% -7.48% ✅ -14.90% ✅
TeaLeaf 2D openmp gcc10.3.0 armv8.4 216781 27.60% 191269 +11.10% -11.77% ✅ -16.50% ✅
TeaLeaf 2D openmp armclang20 armv8.4 598907 16.50% 631897 +14.30% +5.51% ❌ -2.20% ✅
TeaLeaf 3D serial gcc8.3.0 armv8.4 153938 17.30% 159683 +12.50% +3.73% ❌ -4.80% ✅
TeaLeaf 3D serial gcc9.3.0 armv8.4 158193 18.60% 159172 +12.60% +0.62% ❌ -6.00% ✅
TeaLeaf 3D serial gcc10.3.0 armv8.4 156685 17.90% 161965 +13.60% +3.37% ❌ -4.30% ✅
TeaLeaf 3D serial armclang20 armv8.4 220240 29.20% 225462 +25.30% +2.37% ❌ -3.90% ✅
TeaLeaf 3D openmp gcc8.3.0 armv8.4 297986 27.90% 258964 +12.40% -13.10% ✅ -15.50% ✅
TeaLeaf 3D openmp gcc9.3.0 armv8.4 307134 28.50% 259513 +12.20% -15.50% ✅ -16.30% ✅
TeaLeaf 3D openmp gcc10.3.0 armv8.4 300711 28% 258227 +14.00% -14.13% ✅ -14.00% ✅
TeaLeaf 3D openmp armclang20 armv8.4 489231 28.80% 488426 +22.40% -0.16% ✅ -6.40% ✅
CloverLeaf serial gcc8.3.0 armv8.4+sve 169930 35.20% 156132 +26.40% -8.12% ✅ -8.80% ✅
CloverLeaf serial gcc9.3.0 armv8.4+sve 166786 34.20% 153951 +25.70% -7.70% ✅ -8.50% ✅
CloverLeaf serial gcc10.3.0 armv8.4+sve 171339 36.50% 153704 +28.10% -10.29% ✅ -8.40% ✅
CloverLeaf serial armclang20 armv8.4+sve 159721 33% 144697 +24.00% -9.41% ✅ -9.00% ✅
CloverLeaf openmp gcc8.3.0 armv8.4+sve 225588 34.30% 206026 +24.90% -8.67% ✅ -9.40% ✅
CloverLeaf openmp gcc9.3.0 armv8.4+sve 221890 33.40% 205715 +24.50% -7.29% ✅ -8.90% ✅
CloverLeaf openmp gcc10.3.0 armv8.4+sve 223602 34.10% 202572 +25.10% -9.41% ✅ -9.00% ✅
CloverLeaf openmp armclang20 armv8.4+sve 206803 32.50% 187130 +23.20% -9.51% ✅ -9.30% ✅
miniBUDE openmp gcc8.3.0 armv8.4+sve 84149 23.60% 87757 +14.50% +4.29% ❌ -9.10% ✅
miniBUDE openmp gcc9.3.0 armv8.4+sve 81961 25.10% 85029 +14.20% +3.74% ❌ -10.90% ✅
miniBUDE openmp gcc10.3.0 armv8.4+sve 80809 24% 85333 +14.60% +5.60% ❌ -9.40% ✅
miniBUDE openmp armclang20 armv8.4+sve 80084 22.90% 86089 +20.80% +7.50% ❌ -2.10% ✅
STREAM serial gcc8.3.0 armv8.4+sve 40075 1.68% 44505 +4.57% +11.05% ❌ +2.89% ❌
STREAM serial gcc9.3.0 armv8.4+sve 40034 1.84% 44595 +4.74% +11.39% ❌ +2.90% ❌
STREAM serial gcc10.3.0 armv8.4+sve 39628 2.04% 44212 +4.49% +11.57% ❌ +2.45% ❌
STREAM serial armclang20 armv8.4+sve 24085 2.13% 25849 +4.27% +7.32% ❌ +2.14% ❌
STREAM openmp gcc8.3.0 armv8.4+sve 91458 19.50% 81615 +5.52% -10.76% ✅ -13.98% ✅
STREAM openmp gcc9.3.0 armv8.4+sve 91222 19.70% 81992 +4.92% -10.12% ✅ -14.78% ✅
STREAM openmp gcc10.3.0 armv8.4+sve 89951 19.50% 82990 +7.82% -7.74% ✅ -11.68% ✅
STREAM openmp armclang20 armv8.4+sve 76133 18.30% 65854 +5.94% -13.50% ✅ -12.36% ✅
TeaLeaf 2D serial gcc8.3.0 armv8.4+sve 130373 25% 132175 +17.20% +1.38% ❌ -7.80% ✅
TeaLeaf 2D serial gcc9.3.0 armv8.4+sve 129521 24.90% 131964 +17.10% +1.89% ❌ -7.80% ✅
TeaLeaf 2D serial gcc10.3.0 armv8.4+sve 131156 25% 132608 +17.20% +1.11% ❌ -7.80% ✅
TeaLeaf 2D serial armclang20 armv8.4+sve 99518 19.50% 101456 +17.10% +1.95% ❌ -2.40% ✅
TeaLeaf 2D openmp gcc8.3.0 armv8.4+sve 217552 27.40% 187829 +10.60% -13.66% ✅ -16.80% ✅
TeaLeaf 2D openmp gcc9.3.0 armv8.4+sve 214994 26.50% 191139 +10.70% -11.10% ✅ -15.80% ✅
TeaLeaf 2D openmp gcc10.3.0 armv8.4+sve 213683 27.50% 190455 +11.40% -10.87% ✅ -16.10% ✅
TeaLeaf 2D openmp armclang20 armv8.4+sve 822471 16.40% 610613 +13.80% -25.76% ✅ -2.60% ✅
TeaLeaf 3D serial gcc8.3.0 armv8.4+sve 130973 26.40% 134340 +20.00% +2.57% ❌ -6.40% ✅
TeaLeaf 3D serial gcc9.3.0 armv8.4+sve 131887 26.40% 135390 +21.20% +2.66% ❌ -5.20% ✅
TeaLeaf 3D serial gcc10.3.0 armv8.4+sve 132279 26.10% 135742 +21.70% +2.62% ❌ -4.40% ✅
TeaLeaf 3D serial armclang20 armv8.4+sve 219685 29.90% 230342 +27.70% +4.85% ❌ -2.20% ✅
TeaLeaf 3D openmp gcc8.3.0 armv8.4+sve 269587 31.30% 233953 +15.20% -13.22% ✅ -16.10% ✅
TeaLeaf 3D openmp gcc9.3.0 armv8.4+sve 273317 30.70% 230628 +14.70% -15.62% ✅ -16.00% ✅
TeaLeaf 3D openmp gcc10.3.0 armv8.4+sve 273946 32.10% 233027 +16.20% -14.94% ✅ -15.90% ✅
TeaLeaf 3D openmp armclang20 armv8.4+sve 530223 30.80% 502673 +19.70% -5.20% ✅ -11.10% ✅
Benchmark PP time PP mispredict PP + FTQ time PP + FTQ mispredict Performance change (percentage) Mispredict change (raw)
CloverLeaf serial gcc8.3.0 armv8.4 161811 25% 140894 6.63% -12.93% ✅ -18.37% ✅
CloverLeaf serial gcc9.3.0 armv8.4 158353 23% 140826 6.63% -11.07% ✅ -16.37% ✅
CloverLeaf serial gcc10.3.0 armv8.4 163963 24.80% 138751 7.32% -15.38% ✅ -17.48% ✅
CloverLeaf serial armclang20 armv8.4 134777 22.50% 127074 8.60% -5.72% ✅ -13.90% ✅
CloverLeaf openmp gcc8.3.0 armv8.4 205901 24.10% 186108 5.92% -9.61% ✅ -18.18% ✅
CloverLeaf openmp gcc9.3.0 armv8.4 199719 22.60% 180077 5.21% -9.83% ✅ -17.39% ✅
CloverLeaf openmp gcc10.3.0 armv8.4 200722 23.50% 176673 5.95% -11.98% ✅ -17.55% ✅
CloverLeaf openmp armclang20 armv8.4 170551 20.50% 166734 7.76% -2.24% ✅ -12.74% ✅
miniBUDE openmp gcc8.3.0 armv8.4 203321 8.64% 238863 6.22% +17.48% ❌ -2.42% ✅
miniBUDE openmp gcc9.3.0 armv8.4 202440 8.59% 237718 6.24% +17.43% ❌ -2.35% ✅
miniBUDE openmp gcc10.3.0 armv8.4 202448 8.61% 238361 6.29% +17.74% ❌ -2.32% ✅
miniBUDE openmp armclang20 armv8.4 185367 11.40% 217350 9.59% +17.25% ❌ -1.81% ✅
STREAM serial gcc8.3.0 armv8.4 77580 0.60% 96276 0.46% +24.10% ❌ -0.14% ✅
STREAM serial gcc9.3.0 armv8.4 78402 0.77% 96264 0.46% +22.78% ❌ -0.32% ✅
STREAM serial gcc10.3.0 armv8.4 78152 0.84% 96151 0.40% +23.03% ❌ -0.44% ✅
STREAM serial armclang20 armv8.4 87023 1.24% 104494 0.89% +20.08% ❌ -0.36% ✅
STREAM openmp gcc8.3.0 armv8.4 113201 2.76% 136471 1.34% +20.56% ❌ -1.42% ✅
STREAM openmp gcc9.3.0 armv8.4 115083 2.40% 136789 1.28% +18.86% ❌ -1.12% ✅
STREAM openmp gcc10.3.0 armv8.4 112675 2.75% 135985 1.40% +20.69% ❌ -1.35% ✅
STREAM openmp armclang20 armv8.4 123741 5.07% 140465 2.00% +13.52% ❌ -3.07% ✅
TeaLeaf 2D serial gcc8.3.0 armv8.4 126449 20.70% 144119 10.00% +13.97% ❌ -10.70% ✅
TeaLeaf 2D serial gcc9.3.0 armv8.4 126731 21.60% 144538 10.00% +14.05% ❌ -11.60% ✅
TeaLeaf 2D serial gcc10.3.0 armv8.4 128624 20.80% 144965 9.92% +12.70% ❌ -10.88% ✅
TeaLeaf 2D serial armclang20 armv8.4 236103 10.90% 272149 6.81% +15.27% ❌ -4.09% ✅
TeaLeaf 2D openmp gcc8.3.0 armv8.4 182287 11.20% 205839 4.91% +12.92% ❌ -6.29% ✅
TeaLeaf 2D openmp gcc9.3.0 armv8.4 183910 11.70% 205207 4.76% +11.58% ❌ -6.94% ✅
TeaLeaf 2D openmp gcc10.3.0 armv8.4 183236 11.50% 206025 5.24% +12.44% ❌ -6.26% ✅
TeaLeaf 2D openmp armclang20 armv8.4 585522 9.29% 690239 4.05% +17.88% ❌ -5.24% ✅
TeaLeaf 3D serial gcc8.3.0 armv8.4 146189 11.20% 166166 6.50% +13.67% ❌ -4.70% ✅
TeaLeaf 3D serial gcc9.3.0 armv8.4 152422 12.50% 172168 7.65% +12.95% ❌ -4.85% ✅
TeaLeaf 3D serial gcc10.3.0 armv8.4 152368 12.90% 173059 7.58% +13.58% ❌ -5.32% ✅
TeaLeaf 3D serial armclang20 armv8.4 216672 22.40% 246273 13.10% +13.75% ❌ -9.30% ✅
TeaLeaf 3D openmp gcc8.3.0 armv8.4 240845 9.66% 266520 5.00% +10.66% ❌ -4.80% ✅
TeaLeaf 3D openmp gcc9.3.0 armv8.4 248632 11.10% 275962 5.84% +10.99% ❌ -5.26% ✅
TeaLeaf 3D openmp gcc10.3.0 armv8.4 242736 10.50% 269717 5.60% +11.12% ❌ -4.90% ✅
TeaLeaf 3D openmp armclang20 armv8.4 449169 17.30% 534762 8.49% +19.06% ❌ -8.81% ✅
CloverLeaf serial gcc8.3.0 armv8.4+sve 150743 24.30% 136084 6.74% -9.72% ✅ -17.56% ✅
CloverLeaf serial gcc9.3.0 armv8.4+sve 149215 22.90% 133611 6.37% -10.46% ✅ -16.53% ✅
CloverLeaf serial gcc10.3.0 armv8.4+sve 149683 25.20% 135469 7.55% -9.50% ✅ -17.65% ✅
CloverLeaf serial armclang20 armv8.4+sve 137543 21.70% 136314 8.08% -0.89% ✅ -13.62% ✅
CloverLeaf openmp gcc8.3.0 armv8.4+sve 198457 23.60% 177343 6.00% -10.64% ✅ -17.70% ✅
CloverLeaf openmp gcc9.3.0 armv8.4+sve 194197 22.30% 181489 5.78% -6.54% ✅ -16.52% ✅
CloverLeaf openmp gcc10.3.0 armv8.4+sve 195536 23.40% 174100 6.03% -10.96% ✅ -17.37% ✅
CloverLeaf openmp armclang20 armv8.4+sve 179017 21.60% 173794 7.25% -2.92% ✅ -14.35% ✅
miniBUDE openmp gcc8.3.0 armv8.4+sve 80624 16.50% 93548 9.12% +16.03% ❌ -7.38% ✅
miniBUDE openmp gcc9.3.0 armv8.4+sve 77745 16.70% 90967 8.80% +17.01% ❌ -7.90% ✅
miniBUDE openmp gcc10.3.0 armv8.4+sve 77152 16.50% 91225 8.82% +18.24% ❌ -7.68% ✅
miniBUDE openmp armclang20 armv8.4+sve 80877 22.60% 92141 16.60% +13.93% ❌ -6.00% ✅
STREAM serial gcc8.3.0 armv8.4+sve 40545 1.90% 49812 1.18% +22.86% ❌ -0.72% ✅
STREAM serial gcc9.3.0 armv8.4+sve 41154 2.10% 49807 1.45% +21.03% ❌ -0.65% ✅
STREAM serial gcc10.3.0 armv8.4+sve 40867 2.02% 49638 1.49% +21.46% ❌ -0.53% ✅
STREAM serial armclang20 armv8.4+sve 24842 1.88% 29444 1.18% +18.53% ❌ -0.70% ✅
STREAM openmp gcc8.3.0 armv8.4+sve 77394 5.01% 90226 2.61% +16.58% ❌ -2.40% ✅
STREAM openmp gcc9.3.0 armv8.4+sve 78769 6.66% 89966 2.31% +14.21% ❌ -4.35% ✅
STREAM openmp gcc10.3.0 armv8.4+sve 77005 5.41% 89132 2.92% +15.75% ❌ -2.49%
STREAM openmp armclang20 armv8.4+sve 65194 5.69% 73018 2.38% +12.00% ❌ -3.31% ✅
TeaLeaf 2D serial gcc8.3.0 armv8.4+sve 128608 21.30% 144121 10.00% +12.06% ❌ -11.30% ✅
TeaLeaf 2D serial gcc9.3.0 armv8.4+sve 127291 21.70% 144311 10.00% +13.37% ❌ -11.70% ✅
TeaLeaf 2D serial gcc10.3.0 armv8.4+sve 128176 20.70% 144900 9.94% +13.05% ❌ -10.76% ✅
TeaLeaf 2D serial armclang20 armv8.4+sve 95118 14.20% 104716 7.30% +10.09% ❌ -6.90% ✅
TeaLeaf 2D openmp gcc8.3.0 armv8.4+sve 185782 11.60% 205119 4.90% +10.41% ❌ -6.70% ✅
TeaLeaf 2D openmp gcc9.3.0 armv8.4+sve 192862 11.70% 204917 4.78% +6.25% ❌ -6.92% ✅
TeaLeaf 2D openmp gcc10.3.0 armv8.4+sve 180638 11.90% 205666 5.28% +13.86% ❌ -6.62% ✅
TeaLeaf 2D openmp armclang20 armv8.4+sve 576071 8.79% 661934 3.55% +14.90% ❌ -5.24% ✅
TeaLeaf 3D serial gcc8.3.0 armv8.4+sve 130850 20.60% 147334 10.60% +12.60% ❌ -10.00% ✅
TeaLeaf 3D serial gcc9.3.0 armv8.4+sve 131509 20.80% 147962 10.80% +12.51% ❌ -10.00% ✅
TeaLeaf 3D serial gcc10.3.0 armv8.4+sve 130915 21.70% 149008 10.50% +13.82% ❌ -11.20% ✅
TeaLeaf 3D serial armclang20 armv8.4+sve 212249 23.10% 242318 11.90% +14.17% ❌ -11.20% ✅
TeaLeaf 3D openmp gcc8.3.0 armv8.4+sve 228886 14.10% 252720 7.49% +10.41% ❌ -6.61% ✅
TeaLeaf 3D openmp gcc9.3.0 armv8.4+sve 234772 14.30% 251433 7.46% +10.20% ❌ -6.84% ✅
TeaLeaf 3D openmp gcc10.3.0 armv8.4+sve 226325 15.50% 249401 7.29% +10.20% ❌ -8.21% ✅
TeaLeaf 3D openmp armclang20 armv8.4+sve 481883 17.40% 541649 8.61% +12.40% ❌ -8.79% ✅

ABenC377 avatar Feb 27 '24 11:02 ABenC377