La meilleure façon de calculer le résultat d'une formule?

Question

J'ai actuellement une application qui peut contenir 100s de formules définies par l'utilisateur. À l'heure actuelle, j'utilise la notation polonaise inverse pour effectuer les calculs (valeurs et des variables poussant à une pile, puis les sauter de la pile et l'évaluation). Quelle serait la meilleure façon de commencer parallélisation ce processus? Dois-je envisager un langage fonctionnel?

Les calculs sont effectués sur des tableaux de nombres ainsi par exemple simple A + B pourrait en fait signifier 100s des ajouts. Je suis actuellement en utilisant Delphi, mais ce n'est pas une exigence à l'avenir. Je vais utiliser l'outil le plus adapté à la tâche. Les formules peuvent aussi dépendre les uns des autres, nous pouvons donc avoir une formule C = A + B et une seconde D = C + A par exemple.

Answer 1

Supposons que vos formules (équations) ne sont pas cyclique, sinon vous ne pouvez pas « juste » les évaluer. Si vous avez vectorisé équations comme A = B + C où A, B et C sont des tableaux, nous allons les diviser conceptuellement en équations sur les composants, de sorte que si la taille du tableau est 5, cette équation est divisée en

a1 = b1 + c1
a2 = b2 + c2
...
a5 = b5 + c5

Maintenant, en supposant cela, vous avez un grand ensemble d'équations sur les quantités simples (si entier, rationnel ou autre chose).

Si vous avez deux équations E et F, disons que F depends_on E si le côté droit de F mentionne le côté gauche de E, par exemple

E: a = b + c
F: q = 2*a + y

Maintenant, pour obtenir à la façon de calculer cela, vous pouvez toujours utiliser itération aléatoire pour résoudre ce (ce qui est juste une étape intermédiaire dans l'explication), suivant cet algorithme:

1 while (there is at least one equation which has not been computed yet)
2   select one such pending equation E so that:
3     for every equation D such that E depends_on D:
4       D has been already computed
5   calculate the left-hand side of E

Ce processus se termine par la bonne réponse quelle que soit la façon dont vous faites vos sélections en ligne // 2. Maintenant, la chose est cool qu'il parallélise aussi facilement. Vous pouvez l'exécuter dans un nombre arbitraire de fils! Qu'est-ce que vous avez besoin est une file d'attente de sécurité qui contient les concurrency équations dont les conditions (ces équations dépendent) ont été calculés, mais qui ne l'ont pas encore été calculé eux-mêmes. Chaque fil ressorte (fil en toute sécurité) une équation de cette file d'attente à un moment, calcule la réponse, puis vérifie s'il y a maintenant de nouvelles équations de sorte que toutes les conditions préalables ont été calculés, et ajoute ces équations (fil en toute sécurité) à la file d'attente de travail. Fait.

Answer 2

Sans savoir plus, je suggère de prendre une approche de style SIMD si possible. Cela est, créer des threads pour calculer toutes les formules pour un seul ensemble de données. Essayer de diviser le calcul des formules pour les paralléliser ne donnerait pas beaucoup d'amélioration de la vitesse que la logique nécessaire pour être en mesure de diviser les calculs en unités discrètes appropriées pour le filetage serait difficile d'écrire et plus difficile à obtenir le droit, les frais généraux annulerait tous les gains de vitesse. Il souffrirait aussi rapidement de rendements décroissants.

Maintenant, si vous avez un ensemble de formules qui sont appliquées à de nombreux ensembles de données puis la parallélisation devient plus facile et escaladeraient mieux. Chaque thread fait tous les calculs pour un ensemble de données. Créer un thread par noyau de CPU et de définir son affinité pour chaque noyau. Chaque thread instancie une instance du code d'évaluation de la formule. Créer un superviseur qui charge un ensemble de données unique et il passe un fil de repos. Si aucune discussion sont au repos, attendez le premier fil pour terminer le traitement de ses données. Lorsque tous les ensembles de données sont traités et tous les sujets ont terminé, puis se termine. En utilisant cette méthode, il n'y a aucun avantage à avoir plus de fils qu'il y a de noyaux sur la CPU en tant que changement de fil est lente et aura un effet négatif sur la vitesse globale.

Si vous avez seulement un ensemble de données alors il est pas une tâche triviale. Il faudrait analyse l'arbre d'évaluation des branches sans dépendances sur d'autres branches et l'agriculture ces branches à séparer les discussions en cours d'exécution sur chaque noyau et attendre les résultats. Vous obtenez alors des problèmes de synchronisation des données et d'assurer la cohérence des données.