Überlauf in Summe erkennen

Angenommen, ich bekomme ein Array von $n$ ganzen Zahlen mit fester Breite (dh sie passen in ein Register der Breite $w$ ), $a_1, a_2, \dots a_n$ . Ich möchte die Summe $S = a_1 + \ldots + a_n$ auf einer Maschine mit 2er-Komplementarithmetik berechnen , die Additionen modulo $2^w$ mit umlaufender Semantik ausführt . Das ist einfach - aber die Summe kann die Registergröße überschreiten, und wenn dies der Fall ist, ist das Ergebnis falsch.

Wenn die Summe nicht überläuft, möchte ich sie berechnen und so schnell wie möglich überprüfen, ob kein Überlauf vorliegt. Wenn die Summe überläuft, möchte ich nur wissen, dass dies der Fall ist. Mir ist kein Wert wichtig.

Das naive Hinzufügen von Zahlen in der Reihenfolge funktioniert nicht, da eine Teilsumme überlaufen kann. Beispielsweise ist bei 8-Bit-Registern gültig und hat eine Summe von , obwohl die Teilsumme den Registerbereich überläuft . $(120, 120, -115)$ $125$ $120+120$ $[-128,127]$

Natürlich könnte ich ein größeres Register als Akkumulator verwenden, aber nehmen wir den interessanten Fall an, in dem ich bereits die größtmögliche Registergröße verwende.

Es gibt eine bekannte Technik, um Zahlen mit dem entgegengesetzten Vorzeichen als aktuelle Teilsumme hinzuzufügen . Diese Technik vermeidet Überläufe bei jedem Schritt, auf Kosten der Uncache-Freundlichkeit und der geringen Nutzung der Verzweigungsvorhersage und der spekulativen Ausführung.

Gibt es eine schnellere Technik, die möglicherweise die Berechtigung zum Überlaufen von Teilsummen nutzt und auf einem typischen Computer mit einem Überlaufflag, einem Cache, einem Verzweigungsprädiktor und spekulativer Ausführung und Laden schneller ist?

(Dies ist eine Folge der sicheren Überlaufsummierung. )

algorithms arrays integers numerical-analysis Gilles 'SO - hör auf böse zu sein'
quelle

Warum funktioniert Daves Lösung Ihrer Meinung nach nicht gut mit Caches und Pipelines? Wenn Sie eine ähnliche Quicksort-Partitionierung mit virtuellem Pivot

, behandeln Sie Caches sowohl während der Partitionierung als auch während der folgenden Summierung gut. Ich weiß nichts über Verzweigungsfehler während der Partitionierung, aber die Summierungsphase sollte auch in dieser Hinsicht gut abschneiden.

0

$0$

Raphael

@ Raphael In meiner Anwendung ist Überlauf der Ausnahmefall. Bedingungen entsprechend "Überlauf?" sind somit gut durch Verzweigungsvorhersage bedient. Bedingungen entsprechend "Ist diese Zahl positiv?" kann nicht vorhergesagt werden. Der Cache-Effekt ist in der Tat gering, da Sie zwei Cursor anstelle von einem haben.

Gilles 'SO - hör auf böse zu sein'

Antworten:

Sie können Zahlen der Größe ohne Überlauf hinzufügen, wenn Sie die Arithmetik Bits verwenden. Mein Vorschlag ist, genau das zu tun und dann zu überprüfen, ob das Ergebnis im Bereich liegt. Algorithmen für die Multipräzisionsarithmetik sind bekannt (siehe TAOCP-Abschnitt 4.3, wenn Sie eine Referenz benötigen). Oft gibt es Hardware-Unterstützung für das Hinzufügen ( Übertragsflag und Hinzufügen mit Übertragsanweisung ), auch ohne diese Unterstützung können Sie sie ohne datenabhängigen Sprung implementieren ( Dies ist gut für Sprungvorhersagen. Sie benötigen nur einen Durchgang für die Daten und können die Daten in der bequemsten Reihenfolge aufrufen (was für den Cache gut ist). $n$ $w$ $\lceil \log n\rceil + w$

Wenn die Daten nicht in den Speicher passen, ist der begrenzende Faktor die E / A und wie gut es Ihnen gelingt, die E / A mit der Berechnung zu überlappen.

Wenn die Daten in den Speicher passen, haben Sie wahrscheinlich (die einzige Ausnahme, die ich mir kann, ist ein 8-Bit-Mikroprozessor, der normalerweise 64 KB Speicher hat), was bedeutet, dass Sie Arithmetik mit doppelter Genauigkeit ausführen. Der Overhead über eine Schleife macht $\lceil \log n\rceil \leq w$ $w$ -Bits-Arithmetik kann nur aus zwei Befehlen bestehen (einer zum Vorzeichen erweitern, der andere mit Carry hinzufügen) und einem leichten Anstieg des Registerdrucks (aber wenn ich recht habe, hat selbst das ausgehungerte x86-Register genügend Register, auf die der einzige Speicher zugreifen kann Die innere Schleife kann die Daten abrufen. Ich denke, es ist wahrscheinlich, dass ein OO-Prozessor in der Lage sein wird, die zusätzlichen Operationen während der Speicherladezeit zu planen, so dass die innere Schleife mit der Speichergeschwindigkeit ausgeführt wird und die Übung darin besteht, die Nutzung der verfügbaren Bandbreite zu maximieren (Prefetch) oder Interleaving-Techniken können je nach Speicherarchitektur hilfreich sein.

In Anbetracht des neuesten Punktes ist es schwierig, sich andere Algorithmen mit besserer Leistung vorzustellen. Datenabhängige (und damit nicht vorhersehbare) Sprünge kommen ebenso nicht in Frage wie mehrere Durchgänge der Daten. Selbst der Versuch, die verschiedenen Kerne des heutigen Prozessors zu verwenden, wäre schwierig, da die Speicherbandbreite wahrscheinlich gesättigt sein wird, aber es könnte eine einfache Möglichkeit sein, verschachtelten Zugriff zu implementieren.

Ein Programmierer
quelle

Ich kann die Register auf meinem Computer nicht vergrößern. Angenommen, ich verwende bereits die größtmögliche Registergröße.

Gilles 'SO - hör auf böse zu sein'

@ Gilles, Prozessoren, von denen ich weiß, dass sie das Überlauf-Flag haben, das wir nutzen sollen, haben auch ein Carry-Flag und ein Add-with-Carry- Befehl. Selbst für diejenigen, die dies nicht tun (etwas anderes als MIPS?), Wäre die Multipräzisionsarithmetik ein ernstzunehmender Kandidat (sie hat nur einen Datenübergang - gut für den Cache -, Zugriff nacheinander - gut für den Cache-Vorfüller - - und kann ohne datenabhängigen Sprung implementiert werden - gut für Sprungvorhersagen).

AProgrammer

Was meinst du mit "Multipräzisionsarithmetik"? Ich dachte du meinst Gleitkomma. Viele Architekturen verfügen jedoch nicht über ausreichend große Gleitkommaregister, sofern vorhanden. Angenommen, ich füge 64-Bit-Ganzzahlen auf amd64 oder 32-Bit-Ganzzahlen auf ARM ohne VFP hinzu.

Gilles 'SO - hör auf böse zu sein'

@ Gilles, ich meinte, was in Abschnitt 4.3 von TAOCP beschrieben wird: die Verwendung mehrerer Wörter zur Darstellung von Werten, die nicht in einem Wort enthalten sein können. Bignum ist eine Variante, bei der die Anzahl der Wörter dynamisch angepasst wird. Ich vermute, dass Sie hier eine maximale Grenze für die Anzahl der benötigten Wörter bestimmen können (dh 2, wenn sich Ihre Daten im Speicher befinden; wenn dies nicht der Fall ist, arbeiten Sie daran, die zu überlappen E / A mit Berechnung ist der erste Aktionspunkt (Sie sind an E / A gebunden) und verwenden Sie es einfach. Es ist niedrig genug, damit die Verarbeitung einer unterschiedlichen Anzahl von Wörtern teurer wird.

AProgrammer

Ah, ok. Könnten Sie dies in Ihrer Antwort klarstellen? Haben Sie Referenzen mit Timings und Vergleiche mit anderen Methoden?

Gilles 'SO - hör auf böse zu sein'

Auf einer Maschine, auf der sich ganzzahlige Typen wie ein abstrakter algebraischer Ring verhalten (was im Grunde bedeutet, dass sie umbrochen werden), könnte man die Summen von Element [i] und (Element [i] >> 16) für bis zu 32767 Elemente berechnen. Der erste Wert würde die unteren 32 Bits der korrekten Summe ergeben. Der letztere Wert würde die Bits 16-47 von etwas ergeben, das nahe an der korrekten Summe liegt, und unter Verwendung des ersteren Werts kann er leicht angepasst werden, um die Bits 16-47 der exakten korrekten Summe zu ergeben.

Pseudocode wäre so etwas wie:

Sum1=0 : Sum2 = 0
For up to 32768 items L[i] in list
  Sum1 = Sum1 +L[i]
  Sum2 = Sum2 +(L[i] >> 16) ' Use sign-extending shift
Loop
Sum1MSB = Sum1 >> 16 ' Cannot use division of numbers can be negative--see below
Sum2Mid = Sum2 and 65535
Sum2Adj = Sum1MSB - Sum2Mid
If Sum2Adj >= 32768 then Sum2Adj = Sum2Adj - 65536
Sum2 += Sum2Adj

Nach dem obigen Code sollten Sum2 und Sum1 zusammen die richtige Summe ergeben, unabhängig von dazwischenliegenden Überläufen. Wenn es notwendig ist, mehr als 32768 Zahlen zu summieren, können sie in Gruppen von 32768 unterteilt werden. Nach der Berechnung von Sum2 für jede Gruppe kann man sie zu einer "großen Summe" mit zwei Variablen für alle Gruppen als Ganzes hinzufügen.

In einigen Sprachen könnte der Operator für die Verschiebung nach rechts durch eine Division durch 65536 ersetzt werden. Dies funktioniert im Allgemeinen bei der Berechnung von Sum2, nicht jedoch beim Extrahieren von Sum1MSB. Das Problem ist, dass einige Sprachen Divisionen gegen Null runden, während hier eine Divisionsrundung auf die nächst niedrigere Zahl (gegen negative Unendlichkeit) durchgeführt werden muss. Fehler bei der Berechnung von Sum2 würden später korrigiert, Fehler bei der Berechnung von Sum2LSB würden sich jedoch auf das Endergebnis auswirken.

Beachten Sie, dass nichts in den Endergebnissen darauf hindeutet, ob eine der Berechnungen mit Sum1 "übergelaufen" ist. Wenn jedoch garantiert wird, dass die Werte sauber umbrochen werden, sollte sich der Code nicht darum kümmern müssen, ob ein Überlauf aufgetreten ist.

Superkatze
quelle