Existe-t-il des problèmes / algorithmes célèbres dans le calcul scientifique qui ne peuvent pas être accélérés par la parallélisation

Existe-t-il des problèmes / algorithmes célèbres dans le calcul scientifique qui ne peuvent pas être accélérés par la parallélisation? Il me semble qu'en lisant des livres sur CUDA, la plupart des choses peuvent être.

La question principale est la longueur du chemin critique par rapport à la quantité totale de calcul T . Si C est proportionnel à T , alors le parallélisme offre au mieux une accélération constante. Si C est asymptotiquement plus petit que T , il y a place pour plus de parallélisme à mesure que la taille du problème augmente. Pour les algorithmes dans lesquels T est polynomial dans la taille d'entrée N , le meilleur cas est C ∼ log T car très peu de quantités utiles peuvent être calculées en moins de temps logarithmique.$C$$T$$C$$T$$C$$T$$T$$N$$C \sim \log T$

Exemples

• pour une résolution tridiagonale utilisant l'algorithme standard. Chaque opération dépend de la fin de l'opération précédente, il n'y a donc aucune possibilité de parallélisme. Les problèmes tridiagonaux peuvent être résolus en temps logarithmique sur un ordinateur parallèle en utilisant une résolution directe de dissection imbriquée, une décomposition de domaine à plusieurs niveaux ou une multigrille avec des fonctions de base construites en utilisant l'extension harmonique (ces trois algorithmes sont distincts dans plusieurs dimensions, mais peuvent coïncider exactement dans 1D).$C = T$
• Une résolution triangulaire inférieure dense avec une matrice a T = N = O ( m 2 ) , mais le chemin critique n'est que C = m = $m\times m$$T = N = \mathcal O(m^2)$$C = m = \sqrt T$ , donc un certain parallélisme peut être bénéfique.
• Multigrille et FMM ont tous deux , avec un chemin critique de la longueur C = connectent T .$T = N$$C = \log T$
• La propagation explicite des ondes pendant un temps sur un maillage régulier du domaine ( 0 , 1 ) d nécessite k = τ / Δ t ∼ τ N 1 / d pas de temps (pour la stabilité), donc le chemin critique est au moins C = k . La quantité totale de travail est T = k N = τ N ( d + 1 ) / d . Le nombre maximal utile de processeurs est P = $\tau$$(0,1)^d$$k = \tau / \Delta t \sim \tau N^{1/d}$$C = k$$T = k N = \tau N^{(d+1)/d}$ , le facteur N 1 / d restantne peut pas être récupéré par un parallélisme accru.$P = T/C = N$$N^{1/d}$

Complexité formelle

La classe de complexité NC caractérise les problèmes qui peuvent être résolus efficacement en parallèle (c'est-à-dire en temps polylogarithmique). On ne sait pas si , mais il est largement supposé être faux. Si c'est effectivement le cas, alors P-complete caractérise les problèmes qui sont "intrinsèquement séquentiels" et ne peuvent pas être accélérés de manière significative par le parallélisme.$NC = P$

Pour donner un aspect théorique à cela, $NC$ est défini comme la classe de complexité qui peut être résolue en temps sur un système avec O ( n k ) processeurs parallèles. On ne sait toujours pas si P = N C (bien que la plupart des gens pensent que ce n'est pas le cas) où P est l'ensemble des problèmes pouvant être résolus en temps polynomial. Les problèmes "les plus difficiles" à paralléliser sont connus sous le nom de problèmes P- complets dans le sens où chaque problème dans P peut être réduit à un problème P- complet via$O(log^c n)$$O(n^k)$$P=NC$$P$$P$$P$$P$Réductions de N C. Si vous montrez qu'un seulproblème P complet est dans N C , vous prouvez que P = N C (bien que ce soit probablement faux comme mentionné ci-dessus).$NC$$P$$NC$$P=NC$

Ainsi, tout problème qui est complet serait intuitivement difficile à paralléliser (bien que de grandes accélérations soient toujours possibles). Un programme complet en P pour lequel nous n'avons même pas de très bonnes accélérations à facteur constant est la programmation linéaire (voir ce commentaire sur l'échange OR).$P$$P$

Commencez par bloquer la loi d'Amdahl . Fondamentalement, tout ce qui comporte un grand nombre d'étapes en série bénéficiera de manière insignifiante du parallélisme. Quelques exemples incluent l'analyse, l'expression régulière et la plupart des compressions à rapport élevé.

En dehors de cela, le problème clé est souvent un goulot d'étranglement dans la bande passante mémoire. En particulier, avec la plupart des GPU, vos flops théoriques dépassent largement la quantité de nombres à virgule flottante que vous pouvez obtenir pour vos ALU, car ces algorithmes à faible intensité arithmétique (flops / cache-miss) passeront une grande majorité du temps à attendre sur la RAM.

Enfin, chaque fois qu'un morceau de code nécessite une ramification, il est peu probable qu'il obtienne de bonnes performances, car la logique d'ALU est généralement supérieure à la logique.

En conclusion, un exemple vraiment simple de quelque chose qui serait difficile à obtenir un gain de vitesse à partir d'un GPU est simplement de compter le nombre de zéros dans un tableau d'entiers, car vous devrez peut-être souvent créer une branche, tout au plus effectuer 1 opération (incrémenter de un) dans le cas où vous trouvez un zéro et effectuez au moins une extraction de mémoire par opération.

Un exemple exempt du problème de branchement est de calculer un vecteur qui est la somme cumulée d'un autre vecteur. ([1,2,1] -> [1,3,4])

Je ne sais pas si ceux-ci comptent comme "célèbres" mais il y a certainement un grand nombre de problèmes avec lesquels le calcul parallèle ne vous aidera pas.

La (célèbre) méthode de marche rapide pour résoudre l'équation Eikonal ne peut pas être accélérée par la parallélisation. Il existe d'autres méthodes (par exemple des méthodes de balayage rapide) pour résoudre l'équation Eikonal qui se prêtent mieux à la parallélisation, mais même ici, le potentiel d'accélération (parallèle) est limité.

Le problème avec l'équation Eikonal est que le flux d'informations dépend de la solution elle-même. En gros, les informations circulent le long des caractéristiques (c'est-à-dire les rayons lumineux en optique), mais les caractéristiques dépendent de la solution elle-même. Et le flux d'informations pour l'équation Eikonale discrétisée est encore pire, nécessitant des approximations supplémentaires (comme implicitement présentes dans les méthodes de balayage rapide) si une accélération parallèle est souhaitée.

Pour voir les difficultés de la parallélisation, imaginez un joli labyrinthe comme dans certains des exemples de la page Web de Sethian . Le nombre de cellules sur le chemin le plus court à travers le labyrinthe (probablement) est une limite inférieure pour le nombre minimal d'étapes / itérations de tout algorithme (parallèle) résolvant le problème correspondant.

(J'écris "(probablement) est", car les bornes inférieures sont notoirement difficiles à prouver et nécessitent souvent des hypothèses raisonnables sur les opérations utilisées par un algorithme.)

Une autre classe de problèmes difficiles à paralléliser dans la pratique sont les problèmes sensibles aux erreurs d'arrondi, où la stabilité numérique est obtenue par la sérialisation.

Considérons par exemple le processus de Gram – Schmidt et sa modification en série. L'algorithme fonctionne avec des vecteurs, vous pouvez donc utiliser des opérations vectorielles parallèles, mais cela ne s'adapte pas bien. Si le nombre de vecteurs est grand et la taille du vecteur est petite, l'utilisation de Gram – Schmidt classique parallèle et la réorthogonalisation peuvent être stables et plus rapides que Gram – Schmidt modifié unique, bien que cela implique de faire plusieurs fois plus de travail.