Suchkosten im Vergleich zu Berechnungen

Ich bin daran interessiert, Berechnungen aufzustellen, um zu prüfen, ob ein Abstandskriterium erfüllt ist: Das heißt, der Abstand zwischen einem Vektor ${\bf x}_i$ und einem anderen Vektor ${\bf x}_j$ sollte kleiner sein als ein Wert $r_{\rm max}$ . Meine Daten sind nach einem orthogonalen Koordinatenraster unterteilt. Da mein Grenzwert kleiner ist als der Abstand zwischen den Endpunkten der Koordinaten des nächsten Nachbarn, möchte ich eine "Oktanten" -Variable hinzufügen, um zu überprüfen, ob die Einstellungen korrekt sind:

if octant[j] in allowed_list continue

als "Kurzschluss" zu

if dist(x[i], x[j]) < r_max

Meine Frage lautet: Wie effizient sind boolesche Suchen und Vergleiche im Vergleich zu Gleitkommaoperationen rechnerisch? Lohnt sich dies für moderne Architekturen?

Meine Faustregel ist, dass es besser ist, neu zu berechnen, als zu speichern, wenn Sie eine Menge effizient berechnen können (gute Auslastung der FPU), und zwar in weniger als 50 Flops pro doppeltem Präzisionswert. Der seit Jahrzehnten anhaltende Trend geht dahin, dass sich die Fließkommafähigkeit schneller verbessert als die Speicherleistung, und aufgrund physikalischer Einschränkungen und des Energiebedarfs des schnellen Speichers wahrscheinlich nicht nachlässt. Der Wert 50 ist für alle gängigen Computerplattformen (Intel / AMD, Blue Gene und GPUs) gleich groß.

Ungefähre Kostenschätzungen pro Kern

[Richtlinien für 2011/2012 Intel- und AMD-basierte Maschinen]

• ns: Zeit für eine Gleitkommaoperation mit doppelter Genauigkeit als Teil eines vektorisierten Codes ohne Datenabhängigkeiten und verschachteltes Multiplizieren / Addieren$0.05$
• ns: Zeit für eine nicht vektorisierte Gleitkommaoperation ohne Vektorisierung oder Datenabhängigkeiten$0.2$
• ns: Zeit für eine nicht vektorisierte Gleitkommaoperation ohne Vektorisierung oder Datenabhängigkeiten, jedoch ohne verschachtelte Multiplikation / Addition (1 Taktzyklus)$0.4$
• bis 0,8 ns: Latenz zum Referenz-L1-Cache$0.4$$0.8$
• ns: Latenz einer Gleitkommaoperation (vektorisiert oder nicht)$2$
• bis 5 ns: Zeit zum Laden eines Wertes mit doppelter Genauigkeit aus dem Speicher als Teil eines perfekt vorabgerufenen und voll ausgelasteten Streams$3$$5$
• bis 5 ns: indirekter Funktionsaufruf (virtuelle Methode oder Funktionszeiger, ohne Registerdruck)$3$$5$
• ns: bedingte Verzweigung falsch vorhergesagt$5$
• bis 8 ns: Zeit für eine Division (vektorisiert oder nicht, kann nicht gleichzeitig mit anderen Anweisungen ausgeführt werden)$4$$8$
• ns: L1-Cache-Fehler von lokalem L2 erfüllt$12$
• ns: Best-Case-Befehl zum Vergleichen und Vertauschen oder Abrufen und Hinzufügen von Atomen$12$
• - 50 ns: L1-Schreib-Cache-Fehler oder Atomic-Befehl, bei dem die Cache-Zeile lokal verfügbar ist, der aktuelle Core jedoch exklusiven Zugriff erhalten muss$30$$50$
• ns: Cache-Miss oder Atomic-Befehl aus dem Off-Socket oder Speicher erfüllt$100$
• $10^3$$1$ $\mu$
• $10^4$$10$ $\mu$
• $10^6$
• $2\cdot 10^6$MPI_Allreduce
• $10^7$
• $5\cdot 10^8$
• $1.8\cdot 10^{12}$

Weitere Lektüre

• Agner Nebels Anweisungstabellen
• Latenzzahlen, die jeder Programmierer kennen sollte
• Paul McKenney schiebt auf Threading