Détection du débordement dans la sommation

8

Supposons que l'on me donne un tableau de entiers de largeur fixe (c'est-à-dire qu'ils tiennent dans un registre de largeur ), . Je veux calculer la somme sur une machine avec l'arithmétique du complément à 2, qui effectue des ajouts modulo avec une sémantique enveloppante. C'est facile - mais la somme peut dépasser la taille du registre, et si c'est le cas, le résultat sera erroné.nwune1,une2,unenS=une1++unen2w

Si la somme ne déborde pas, je veux la calculer, et vérifier qu'il n'y a pas de débordement, le plus vite possible. Si la somme déborde, je veux seulement savoir que c'est le cas, je me fiche de toute valeur.

L'ajout naïf de nombres dans l'ordre ne fonctionne pas, car une somme partielle peut déborder. Par exemple, avec des registres 8 bits, est valide et a une somme de , même si la somme partielle déborde la plage de registres .(120,120,-115)125120+120[-128,127]

Évidemment, je pourrais utiliser un plus grand registre comme accumulateur, mais supposons le cas intéressant où j'utilise déjà la plus grande taille de registre possible.

Il existe une technique bien connue pour ajouter des nombres de signe opposé à la somme partielle actuelle . Cette technique évite les débordements à chaque étape, au prix de ne pas être compatible avec le cache et de ne pas tirer grand avantage de la prédiction de branche et de l'exécution spéculative.

Existe-t-il une technique plus rapide qui profite peut-être de l'autorisation de déborder des sommes partielles, et est plus rapide sur une machine typique avec un indicateur de débordement, un cache, un prédicteur de branche et une exécution et des charges spéculatives?

(Il s'agit d'un suivi de la sommation sûre Overflow )

Gilles 'SO- arrête d'être méchant'
la source
Pourquoi la solution de Dave ne fonctionne-t-elle pas bien avec les caches et les pipelines à votre avis? Si vous faites quelque chose de similaire au partitionnement Quicksort en place avec pivot virtuel0, vous traitez bien les caches pendant le partitionnement et la sommation suivante. Je ne connais pas les erreurs de prévision des branches lors du partitionnement, mais la phase de sommation devrait également bien fonctionner à cet égard.
Raphael
@Raphael Dans mon application, le débordement est le cas exceptionnel. Les conditions correspondant à "est-ce que cela déborde?" sont donc bien servis par la prédiction de branche. Les conditions correspondant à «ce nombre est-il positif?» ne peut pas être prédit. L'effet de cache est en effet faible car vous avez deux curseurs au lieu d'un.
Gilles 'SO- arrête d'être méchant'

Réponses:

3

Vous pouvez ajouter n nombres de taille w sans débordement si vous utilisez Journaln+wbits arithmétique. Ma suggestion est de faire exactement cela, puis de vérifier si le résultat est dans la plage. Les algorithmes pour l'arithmétique multi-précision sont bien connus (voir TAOCP section 4.3 si vous avez besoin d'une référence), il existe souvent un support matériel pour l'ajout ( indicateur de report et ajout avec instruction de report ), même sans un tel support, vous pouvez l'implémenter sans saut dépendant des données ( ce qui est bon pour les prédicteurs de sauts) et vous avez besoin d'un seul passage sur les données et vous pouvez visiter les données dans l'ordre le plus pratique (ce qui est bon pour le cache).

Si les données ne tiennent pas en mémoire, le facteur limitant sera l'E / S et la façon dont vous réussirez à chevaucher l'E / S avec le calcul.

Si les données tiennent en mémoire, vous aurez probablement Journalnw(la seule exception à laquelle je peux penser est le microprocesseur 8 bits qui a généralement 64 Ko de mémoire) ce qui signifie que vous faites de l'arithmétique double précision. Les frais généraux sur une boucle faisantw-l'arithmétique des bits peut n'être que deux instructions (l'une pour signer l'extension, l'autre pour l'ajouter avec le report) et une légère augmentation de la pression de registre (mais si j'ai raison, même le registre affamé x86 a suffisamment de registres que le seul accès à la mémoire dans la boucle interne peut récupérer les données). Je pense qu'il est probable qu'un processeur OO sera en mesure de planifier les opérations supplémentaires pendant la latence de chargement de la mémoire afin que la boucle interne soit exécutée à la vitesse de la mémoire et donc l'exercice consistera à maximiser l'utilisation de la bande passante disponible (prefetch ou des techniques d'entrelacement pourraient aider selon l'architecture de la mémoire).

Compte tenu du dernier point, il est difficile de penser à d'autres algorithmes avec de meilleures performances. Les sauts dépendant des données (et donc non prévisibles) sont hors de question, de même que plusieurs passes sur les données. Même essayer d'utiliser les différents cœurs du processeur d'aujourd'hui serait difficile car la bande passante mémoire sera probablement saturée, mais cela pourrait être un moyen facile de mettre en œuvre un accès entrelacé.

AProgrammer
la source
Je ne peux pas augmenter la taille des registres sur ma machine. Supposons que j'utilise déjà la plus grande taille de registre possible.
Gilles 'SO- arrête d'être méchant'
@Gilles, les processeurs que je connais qui ont le drapeau de débordement que vous souhaitez que nous profitions ont également un carry et un add avec l' instruction de transport . Même sur ceux qui ne le font pas (autre chose que MIPS?), L'arithmétique multiprécision serait un candidat sérieux (il n'a qu'une seule passe sur les données - bon pour le cache -, y accéder séquentiellement - bon pour le pré-remplissage du cache - -, et peut être implémenté sans saut dépendant des données - bon pour les prédicteurs de saut).
AProgrammer
Qu'entendez-vous par «arithmétique multiprécision»? Je pensais que tu voulais dire virgule flottante. Mais de nombreuses architectures n'ont pas de registres à virgule flottante suffisamment grands, le cas échéant. Supposons que j'ajoute des entiers 64 bits sur amd64 ou des entiers 32 bits sur ARM sans VFP.
Gilles 'SO- arrête d'être méchant'
@ Gilles, je voulais dire ce qui est décrit dans la section 4.3 de TAOCP: l'utilisation de plusieurs mots pour représenter des valeurs qui ne peuvent pas être contenues dans un seul mot. Bignum est une variante où le nombre de mots est ajusté dynamiquement, je suppose qu'ici vous pouvez déterminer une limite maximale pour le nombre de mots nécessaires (c'est-à-dire 2 si vos données sont en mémoire; si ce n'est pas le cas, travailler sur le chevauchement des IO avec calcul sera le premier point d'action, vous serez lié à IO) et utilisez-le, il sera suffisamment faible pour que la gestion d'un nombre variable de mots soit plus coûteuse.
AProgrammer
Ah ok. Pourriez-vous clarifier cela dans votre réponse? Avez-vous des références avec des timings et des comparaisons avec d'autres méthodes?
Gilles 'SO- arrête d'être méchant'
1

Sur une machine où les types entiers se comportent comme un anneau algébrique abstrait [ce qui signifie essentiellement qu'ils s'enroulent], on pourrait calculer les sommes des éléments [i] et (item [i] >> 16) pour environ 32767 éléments. La première valeur donnerait les 32 bits inférieurs de la somme correcte. Cette dernière valeur donnerait les bits 16 à 47 de quelque chose proche de la somme correcte, et en utilisant l'ancienne valeur, elle peut être facilement ajustée pour produire les bits 16 à 47 de la somme exacte exacte.

Le pseudocode serait quelque chose comme:

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

Après le code ci-dessus, Sum2 et Sum1 ensemble doivent produire la somme correcte, indépendamment des débordements intermédiaires. S'il est nécessaire de totaliser plus de 32768 nombres, ils peuvent être divisés en groupes de 32768, et après avoir calculé Sum2 pour chaque groupe, on peut l'ajouter à une "grosse somme" à deux variables pour tous les groupes dans leur ensemble.

Dans certaines langues, l'opérateur de décalage vers la droite pourrait être remplacé par une division par 65536. Cela fonctionne généralement lors du calcul de Sum2, mais pas lors de l'extraction de Sum1MSB. Le problème est que certaines langues arrondissent les divisions vers zéro alors qu'il est nécessaire ici d'effectuer un arrondi de division au nombre inférieur suivant (vers l'infini négatif). Les erreurs de calcul de Sum2 seraient corrigées plus tard, mais les erreurs de calcul de Sum2LSB affecteraient le résultat final.

Notez que rien dans les résultats finaux n'indiquerait si l'un des calculs impliquant Sum1 avait «débordé», mais si les valeurs sont garanties pour boucler proprement, le code ne devrait pas avoir à se soucier si un débordement s'est produit.

supercat
la source