Comment réduire les résultats de complexité parallèle à constamment plusieurs cœurs?

J'ai eu du mal à accepter la vue théorique de la complexité de "efficacement résolue par algorithme parallèle" qui est donnée par la classe NC :

NC est la classe des problèmes qui peuvent être résolus par un algorithme parallèle dans le temps à processeurs avec . $O(\log^cn)$ $p(n) \in O(n^k)$ $c,k \in \mathbb{N}$

Nous pouvons assumer un PRAM .

Mon problème est que cela ne semble pas en dire long sur les "vraies" machines, c'est-à-dire les machines avec une quantité limitée de processeurs. Maintenant , on me dit que « on sait » que nous pouvons « efficacement » simuler un algorithme de processeur processeurs. $O(n^k)$ $p \in \mathbb{N}$

Que signifie "efficacement" ici? Est-ce du folklore ou existe-t-il un théorème rigoureux qui quantifie les frais généraux causés par la simulation?

Ce qui me fait peur, c'est que j'ai un problème qui a un algorithme séquentiel et aussi un algorithme parallèle "efficace" qui, lorsqu'il est simulé sur processeurs, prend également du temps (ce qui est tout ce qui peut être attendu à ce niveau d'analyse de granularité si l'algorithme séquentiel est asymptotiquement optimal). Dans ce cas, il n'y a aucune accélération de ce que nous pouvons voir; en fait, l'algorithme parallèle simulé peut être plus lent que l'algorithme séquentiel. C'est-à-dire que je recherche vraiment des déclarations plus précises que les Bounds (ou une déclaration d'absence de tels résultats). $O(n^k)$ $p$ $O(n^k)$ $O$

complexity-theory reference-request parallel-computing Raphael
la source

Théorème de Brent?

cic

Voulez-vous dire

? Si c'est le cas, cela (afaik) n'est applicable que dans certaines circonstances et ne permet pas non plus de traduire immédiatement les temps d'exécution. Si tel est le cas, veuillez préciser dans une réponse.

T_{p} < \frac{W}{p} + D

$T_p < \frac{W}{p} + D$

Raphael

NC répond à la question "est-il possible d'échanger plus de matériel pour moins de temps d'exécution?" Vous voudrez peut-être vous limiter à un matériel constant et cela revient à vous limiter à une mémoire constante, une meilleure modélisation de certains problèmes. Pour une utilisation pratique, voir les additionneurs de têtes de recherche, plus de matériel pour que l'ajout de

bits se fasse dans

N

$N$

O (N)

$O(N)$

AProgrammer

Réponses:

Si vous supposez que le nombre de processeurs est limité par une constante, alors vous avez raison de dire qu'un problème en NC ne signifie pas grand-chose dans la pratique. Étant donné que tout algorithme sur une PRAM avec k processeurs et t temps parallèle peut être simulé avec une RAM à processeur unique en temps O ( kt ), le temps parallèle et le temps séquentiel ne peuvent différer que d'un facteur constant si k est une constante.

Cependant, si vous supposez que vous pouvez préparer un ordinateur avec plus de processeurs à mesure que la taille d'entrée augmente, un problème en NC signifie que tant que vous pouvez préparer plus de processeurs, le temps d'exécution sera «très court» ou, plus précisément, polylogarithmique dans la taille d'entrée. Si vous pensez que cette hypothèse est irréaliste, comparez-la à l'hypothèse de mémoire illimitée: les ordinateurs réels n'ont qu'une quantité finie d'espace, mais dans l'étude des algorithmes et de la complexité, nous supposons presque toujours qu'un appareil de calcul n'a pas de valeur supérieure constante. lié à l'espace. En pratique, cela signifie que nous pouvons préparer un ordinateur avec plus de mémoire à mesure que la taille d'entrée augmente, c'est ainsi que nous utilisons habituellement les ordinateurs dans le monde réel. NC modélise une situation analogue dans le calcul parallèle.

Tsuyoshi Ito
la source

O

$O$

k

$k$

k / 2

$k/2$

k - 1

$k-1$

n \leq 20

$n \leq 20$

Raphael

@Raphael: La question de savoir si un certain problème appartient à NC ou non ne modélise pas votre question. Je ne dis pas que votre question est sans intérêt; Je dis simplement que NC n'est pas la bonne classe de complexité pour modéliser cela.

Tsuyoshi Ito

Je suis vraiment heureux d'entendre cela; une personne prétend cependant le contraire. Pas nécessairement avec NC mais avec des résultats théoriques de complexité en général. Comment ça se passe avec les autres classes?

Raphael

O (\sqrt{n})

$O(\sqrt{n})$

O (\log n)

$O(\log n)$

@JeffE: Ce n'est pas une correction. J'ai seulement écrit «préparer plus de processeurs» sans donner son sens rigoureux (parce que je pensais que cela obscurcirait le propos).

Tsuyoshi Ito

$NC$

$p = 1$ $NC$

Mais attendez, il y a plus.

$NC$

$P$ $O(n^\epsilon), 0 < \epsilon < 1$ $NC$ $n$ $n$ $\sqrt n < \lg^3 n$ $n \leq 0.5 \times 10^9$ $NC$

Dans l'une des réponses, il a été observé que "En pratique, cela signifie que nous pouvons préparer un ordinateur avec plus de mémoire à mesure que la taille d'entrée augmente, ce qui est la façon dont nous utilisons habituellement les ordinateurs dans le monde réel. NC modélise une situation analogue dans calcul parallèle ".

Je suis partiellement d'accord avec ce point de vue. Nous achetons un nouvel ordinateur parallèle avec plus de mémoire lorsqu'un ancien supercalculateur est mis hors service également parce que les puces DRAM sont moins coûteuses à temps et pour équilibrer quelque peu l'ordinateur parallèle en ce qui concerne ses principaux composants (processeurs, mémoire, interconnexion, etc.).

$p$ $n$ $p$

Par conséquent, il est de plus en plus important de concevoir des algorithmes parallèles évolutifs en mémoire, car ils sont pratiques pour les gros problèmes.

$n^3$ $n$

Massimo Cafaro
la source