Ich bin gerade dabei, eine Implementierung der binären Suche zu erstellen. Mit einigen speziellen Anweisungen, um dies zu messen, habe ich festgestellt, dass der Code etwa 20% Fehlvorhersagequote hat. Ich bin neugierig, ob es irgendeinen Weg gibt zu überprüfen, wie viele Zyklen ich dadurch möglicherweise verliere. Es ist eine MIPS-basierte Architektur.
Schlagen Sie es in den Dokumenten für Ihre CPU nach. Wenn Sie diese Informationen nicht speziell finden können, ist die Länge der CPU-Pipeline eine ziemlich gute Schätzung.
Da es sich um MIPS handelt und es sich um ein 300-MHz-System handelt, werde ich vermuten, dass es sich um eine ziemlich kurze Pipeline handelt. Wahrscheinlich 4-5 Stufen, also ist eine Kosten von 3-4 Zyklen pro Fehlvorhersage wahrscheinlich eine vernünftige Schätzung.
Sie verlieren 0.2 * N Zyklen pro Iteration, wobei N die Anzahl der Zyklen ist, die benötigt werden, um die Pipelines nach einem falsch vorhergesagten Zweig zu leeren. Wenn N = 10 ist, bedeutet das, dass Sie pro Aggregation 2 Uhren pro Iteration verlieren. Es sei denn, Sie haben eine sehr kleine innere Schleife, dann wird dies wahrscheinlich kein signifikanter Leistungseinbruch sein.
Schauen Sie sich Ihre Daten für diese Information an und wenn das scheitert, führen Sie sie eine Milliarde Mal aus und halten Sie sie außerhalb Ihres Programms (Stopp von etwas). Führen Sie sie dann ohne Fehl und Vergleich aus.
Bei einer CPU in der richtigen Reihenfolge können Sie die ungefähren Fehlpunktzahlen als ein Produkt aus der Anzahl der Fehlprädikate und den falschen Kosten berechnen (was im Allgemeinen eine Funktion eines Teils der Pipeline ist)
Auf einer modernen Out-of-order CPU ist eine solche allgemeine Berechnung jedoch normalerweise nicht möglich möglich. Es kann eine große Anzahl von Anweisungen im Flug 1 geben, von denen nur einige durch eine Fehlvorhersage gelöscht werden. Der umgebende Code kann durch eine oder mehrere Ketten abhängiger Anweisungen Latenzzeit gebunden sein, oder er kann Durchsatz sein, der auf Ressourcen wie Ausführungseinheiten, Umbenennungsdurchsatz usw. hängt, oder er kann irgendwo dazwischen liegen.
Bei einem solchen Kern ist die Strafe pro Fehlvorhersage selbst mit Hilfe von Leistungsindikatoren sehr schwer zu bestimmen. Sie können ganze Artikel zu diesem Thema finden fand eine Penalty-Größe von 9 bis 35 Zyklen über die gesamten Benchmarks gemittelt: Wenn man sich ein kleines Stück Code anschaut, wird der Bereich noch größer: Eine Strafe von Null ist einfach zu demonstrieren, und man könnte ein Szenario mit der Strafe erstellen ist in den 100ern von Zyklen.
Wo bleibt Ihnen das, wenn Sie nur versuchen, die Fehlvorhersagekosten in Ihrer binären Suche zu ermitteln? Nun, ein einfacher Ansatz ist nur, um die Anzahl der Fehlvorhersagen zu kontrollieren und den Unterschied zu messen! Wenn Sie Ihre Benchmark-Eingabe so einrichten, dass sie verschiedene Verhaltensweisen aufweist, beginnend mit dem gleichen Verzweigungsmuster, bis hin zu einem zufälligen Muster, können Sie die Fehlvorhersage-Zählung gegen die Laufzeit-Verschlechterung grafisch darstellen. Wenn Sie dies tun, teilen Sie Ihr Ergebnis!
1 Hunderte von Instruktionen im Flug bei modernen großen Kernen, wie sie die x86-, ARM- und POWER-Architekturen bieten.