calcul parallèle de série infinie

Question

J'ai une petite question, sur la façon d'accélérer les calculs de la série infinie. Ceci est juste un des exemples: arctan (x) = x - x ^ 3/3 + x ^ 5/5 - x ^ 7/7 + ....

Disons que vous avez une bibliothèque qui vous permettent de travailler avec de grands nombres, puis la première solution évidente serait de commencer à ajouter / soustraire chaque élément de la séquence jusqu'à atteindre une cible N.

Vous pouvez également préenregistrer X ^ n donc pour chaque élément suivant au lieu de calculer x ^ (n + 2), vous pouvez faire LASTx * (x ^ 2)

Mais sur tout cela semble être tâche séquentielle, et que pouvez-vous faire pour utiliser plusieurs processeurs (8 +) ??.

Merci beaucoup!

EDIT: Je vais devoir quelque chose de 100k à calculer 1m itérations. Cette application est c ++, mais je suis à la recherche de solution abstraite, donc il ne devrait pas importer. Merci pour la réponse.

Answer 1

Vous devez briser le problème à correspondre au nombre de processeurs ou de fils que vous avez. Dans votre cas, vous pourriez avoir par exemple un travail de processeur sur les termes même et un autre travail sur les termes impairs. Au lieu de précalculer x ^ 2 et en utilisant LASTx * (x ^ 2), vous utilisez LASTx * (x ^ 4) pour sauter tous les autres termes. Pour utiliser 8 processeurs, il faut multiplier le terme précédent par x ^ 16 pour sauter 8 termes.

P.S. La plupart du temps lorsqu'ils sont présentés avec un problème comme celui-ci, il vaut la peine de chercher un moyen plus efficace de calculer le résultat. De meilleurs algorithmes ont battu plus de puissance la plupart du temps.

Answer 2

Si vous essayez de calculer la valeur de pi à des millions d'endroits ou de quelque chose, vous devez d'abord envie de porter une attention de choisir une série qui converge rapidement, et qui se prête à parallellization. Ensuite, si vous avez assez de chiffres, il finira par devenir rentable de les diviser sur plusieurs processeurs; vous devrez trouver ou écrire une bibliothèque bignum qui peut le faire.

Notez que vous pouvez factoriser les variables de différentes manières; par exemple:.

atan(x)= x - x^3/3 + x^5/5 - x^7/7 + x^9/9 ...
       = x*(1 - x^2*(1/3 - x^2*(1/5 - x^2*(1/7 - x^2*(1/9 ...

Bien que la deuxième ligne est plus efficace qu'une mise en œuvre naïve de la première ligne, ce dernier calcul a encore une chaîne linéaire de dépendances du début à la fin. Vous pouvez améliorer votre en combinant des termes parallélisme par paires:

       = x*(1-x^2/3) + x^3*(1/5-x^2/7) + x^5*(1/9 ...
       = x*( (1-x^2/3) + x^2*((1/5-x^2/7) + x^2*(1/9 ...
       = [yet more recursive computation...]

Cependant, ce gain de vitesse est pas aussi simple que vous pourriez penser, depuis le temps pris par chaque calcul dépend de la précision nécessaire pour le maintenir. Dans la conception de votre algorithme, vous devez prendre en compte; En outre, votre algèbre est intimement impliquée; à savoir, pour le cas ci-dessus, vous obtiendrez répéter indéfiniment des fractions si vous faites des divisions régulières par vos chiffres constants, de sorte que vous devez trouver un moyen de faire face à cela, d'une façon ou d'une autre.

Answer 3

Eh bien, pour cet exemple, vous pourriez résumer la série (si j'ai les crochets dans les bons endroits):

(-1)^i * (x^(2i + 1))/(2i + 1)

Ensuite, le processeur 1 de 8 calculer la somme des termes pour i = 1, 9, 17, 25, ...

Ensuite, le processeur 2 de 8 calculer la somme des termes pour i = 2, 11, 18, 26, ...

et ainsi de suite, enfin l'addition des sommes partielles.

Ou, vous pouvez faire ce que vous (presque) suggérez, donner i = 1..16 (par exemple) au processeur 1, i = 17..32 au processeur 2 et ainsi de suite, et ils peuvent calculer chaque puissance successive de x à partir de la précédente. Si vous voulez plus de 8x16 éléments de la série, puis attribuez-lui plus à chaque processeur en premier lieu.

Je doute que, pour cet exemple, il est paralléliser vaut du tout, je pense que vous obtiendrez à double précision précision sur 1 processeur tandis que les fils parallèles se réveillent encore jusqu'à; mais c'est juste une supposition pour cet exemple, et vous pouvez probablement de nombreuses séries pour lesquelles parallélisation vaut l'effort.

Et, comme Ransom a déjà @ Mark dit, un meilleur algorithme doit battre la force brute et beaucoup de processeurs à chaque fois.