Cette question provient d'une discussion qui a été touchée sur cette autre question:
parallèle algorithme de temps linéaire . C'est pas devoirs.
Vous recevez un tableau de numéros Quel est le le plus serré Je ne parle pas de la quantité totale de travail effectuée [qui peut jamais moins que O (n)]. n et une machine avec des processeurs P et un équipage partagé Mémoire (lecture simultanée, écriture exclusive mémoire).
5 Réponses :
Je soupçonne que ceci soit O (n / p) + o (p)
mon algorithme naïf serait à
Cette analyse est trop pessimiste, même sur le matériel réel que nous avons réellement. Réduire une valeur de p Les processeurs peuvent être effectués dans O (LG P) TIME.
La question évidente est la suivante: si p >> n Vous voulez dire que les processeurs 2P feront la tâche plus lente que p processeurs?
Je pense que c'est edit O (n / p ') + O (log2 (p')) , où p '= min {n, p} . P ' Processeurs Recherchez des max de N / P' Éléments chacun, suivi de log2 paire des fonts parallèlement en parallèle . Les premiers P '/ 2 sont effectués par des processeurs paires numérotés, suivant' P '/ 4' - par processeurs à des emplacements divisibles de 8, puis de 16, etc.
p ' est introduit pour couvrir le cas lorsque vous avez des nœuds de processeur significativement plus que les éléments dont vous avez besoin pour rechercher.
Je ne suis pas sûr que l'argument log2 (p) détient: il suppose P% 2 == 0, elle n'envisage également pas le coût de la distribution du travail aux processeurs P, que je soupçonne d'être linéaire
@Eugenrieck Distribution peut être effectué dans O (1) en communiquant n à tous les processeurs et en supposant qu'ils connaissent déjà p et leur propre numéro: premier processeur obtient 0 ..N / p Une partie de la matrice, la seconde obtient `n / p..2n / p ', etc. L'idée principale est que la fusion des résultats peut également être faite en parallèle. Je pense qu'il est indépendant du nombre réel de processeurs.
La communication N pourrait être aussi simple que d'écrire N dans un emplacement prédéterminé en mémoire, où tous les processeurs peuvent la lire simultanément, alors oui. Je conviens que la communication peut être faite dans O (1).
@dasblinkenlight: Considérez si ce compte consolide pour une machine plutôt grande. Ensuite, chaque cycle, les processeurs peuvent réduire la taille de l'entrée de moitié (il y a tellement de transformateurs que même dans le premier cycle, chacun obtient seulement 2 chiffres à comparer). Bien sûr, chaque cycle, le nombre de processeurs avec travail à faire de moitié.
@Arjunsharkar Je pense que cela est déjà comptabilisé: dans les cas où p est proche de n , la valeur de n / p serait proche de 1, le résultat serait donc dominé par Log2 (p).
@dasblinkenlight: Vous avez raison. Je vois maintenant que [1 + log2 (p)] est identique à Log2 (n) lorsque vous N / 2 processeurs :)
@dasblinkenlight: la question évidente est la suivante: si p >> n Vous voulez dire que les processeurs P * P feront la tâche plus lentement que P processeurs?
@Sergedondnchich Votre question évidente est aussi évidente une réponse comme la question elle-même. Après tout, il s'agit d'une réponse à trois lignes dans un forum de questions / réponses et non un article dans un magazine scientifique. La baisse des cas d'angle comme celle-ci est à la fois stupide et contre-productive.
@dasblinkenlight: "La baisse des cas d'angle comme celle-ci est à la fois stupide et contre-productive." Bien. En fait, ce n'est pas un cas d'angle. La question concerne meilleur complexité de temps asymptotique. Et puisque l'utilisateur est libre de croître la taille de l'entrée (N) et du nombre d'éléments de calcul (P), la fonction de temps de calcul résultant est la fonction de ces deux paramètres indépendants. De toute évidence, la fonction de complexité du temps qui pousse avec P est loin d'être optimale (nous augmentons la puissance de calcul pour réduire le temps de calcul - à ne pas la pousser, non?) La fonction de temps fournie est fondamentalement fausse.
@dasblinkenlight: et imo mauvaises réponses est exactement ce que je suis censé bownvote. Mais vous avez l'algorithme de votre réponse qui est très bon. Je vais donc supprimer mon bowvote si vous réparez la fonction de complexité de votre temps.
@ Sergedondndich the log2 Les fantasmes de paires réalisés en parallèle la pièce doivent le rendre abondamment effacer que si p> n , puis pn Les CPU n'auraient rien à fusionner. J'aurais pu ajouter une note disant que p est le nombre effectif Nombre de processeurs requis pour le calcul, mais quiconque avec même une familiarité qui passe avec le sujet le prend pour acquis que les CPU Non utilisé dans un calcul ne contribue pas au coût d'un calcul. Donc, la réponse n'est pas fausse, encore moins être fondamentalement mal.
@dasblinkenlight: alors corrigez ou supprimez votre fonction de complexité de temps et je vais supprimer mon bowvote. Est-ce un problème? La fonction de complexité temporelle de l'IMO est une partie importante de la réponse (voir E.g. Réponse de SDCVVC qui donne la fonction correcte) et l'OMI d'avoir cette partie fausse est une bonne raison pour le bowvote. (à suivre)
(Continuer) @dasblinkenlight: Je pense que la fonction est erronée car deux paramètres naturels pour cette fonction sont la taille de l'entrée (N) et le nombre d'éléments de calcul (P) indépendants et non liés à aucun spécifique. algorithme . Si vous utilisez d'autres paramètres (par exemple, le nombre d'éléments de calcul réellement utilisés par votre algorithme dépend des N et P et spécifiques à votre algorithme ), vous devez les spécifier explicitement . Sinon, la fonction est incomplète et probablement trompeuse (puisque vous avez défini p en tant que nombre de processeurs, il est juste faux).
@dasblinkenlight: Vous pouvez simplement écrire la classe de fonction correcte o (n / p) + o (log2 (max {p, n}) .
@Sergedondndich n'est-ce pas min {p, n} , plutôt que max {p, n} ? Je pense qu'un meilleur moyen de traiter est de redéfinir p comme p '= min {p, n} et l'utiliser à la place: o (n / n / P ') + o (log2 (p'))
@dasblinkenlight: "Je pense qu'un meilleur moyen de traiter est de redéfinir p comme p '= min {p, n} et l'utiliser à la place: O (n / p ') + o (log2 (p')) "IMO n'a pas d'importance. Personnellement, je préfère définir des paramètres supplémentaires (comme p ') uniquement si cela rend la fonction de manière significative plus lisible (qui est imo pas ce cas) mais il est également correct.
@dasblinkenlight: "N'est-ce pas min {p, n}, plutôt que max {p, n}?" Vrai. Bien sûr que c'est. Juste une faute de frappe. Bien sûr, je veux dire O (n / p) + o (log2 (min {p, n})) .
Vous n'avez pas besoin de paramètres supplémentaires P ', la complexité peut être écrite comme O (n / p + journal n) (pourquoi - gauche pour le lecteur)
Cuire, Dwwwk et Reischuk ont montré que tout algorithme d'équipage pour trouver le maximum de N éléments doit être exécuté dans l'heure d'oméga (LG N), même avec un nombre illimité de processeurs et de la mémoire illimitée. Si je me souviens bien, un algorithme avec une limite supérieure correspondante apparaît dans leur papier:
Stephen Cook, Cynthia Dwkwork et Rüdiger Reischuk. Limites de temps supérieur et inférieur pour des machines d'accès aléatoires parallèles sans écrit simultané. Journal Siam sur l'informatique, 15 (1): 87-97, 1986.
Ce qui suit est optimal lié:
si p <= n / journal n Vous pouvez le faire dans O (n / p) heure; Sinon, c'est o (journal n), c'est-à-dire quand p> n / journal n Vous ne gagnez rien comparé à p = n / journal n.
Preuve - Louche inférieure:
La revendication 1: Vous ne pouvez jamais faire plus vite que Ω (n / p), car p processeurs ne peuvent donner que des excédents de p
Revendication 2: Vous ne pouvez jamais faire plus vite que Ω (journal n), en raison du modèle d'équipage (voir le papier de l'imprégli); Si vous souhaitez vérifier si un tableau 0-1 a au moins un 1, vous avez besoin d'une heure (log n).
Proof - Louge supérieure:
La revendication 3: Vous pouvez trouver un maximum d'utiliser des processeurs N / Journal N et dans O (log n) Time
Proof: il est facile de trouver un maximum d'utilisation de N processeurs et de journaliser n Time; Mais en fait, dans cet algorithme, la plupart des transformateurs sont dormants la plupart du temps; En guise de cavité appropriée, le livre de complexité de Papadimitriou), leur nombre peut être abaissé à N / LOG N.
Maintenant, étant donné moins que les processeurs N / LOGN, vous pouvez donner du travail attribué à K processeurs à 1 processeur, cela divise les exigences du processeur de K et multiplie le temps requis par k.
let k = (n / journal n) / p; L'algorithme précédent fonctionne dans le temps O (k journal k) = O (n / p) et nécessite n / (log n * k) = p processeurs.
édité: je viens de réaliser que lorsque p <= n / journal n, l'algorithme de Dasblinkenlight a le même runtime asymptotique:
n / p + journal p <= n / p + journal (n / journal n) <= n / p + journal n <= n / p + n / p <= 2n / p = o (n / p = O (n / p )
Vous pouvez donc utiliser cet algorithme, qui a une complexité O (n / p) lorsque p <= n / journal n et O (journal n) sinon.
+1 Pour un bien pensé de réponse, et pour examiner les problèmes soulevés par deux autres réponses.
pour p = n ^ 2 c'est o (1).
Tous initialisez le tableau Boolean NAYMAX [I] = FALSE
PROC (i, j) Définit PASBEMAX [I] = A [I]
max est un [pasbemax [i] == faux]
Notez que tous les concurrents écrit tenter d'écrire des informations identiques afin que la réponse soit cohérente, quel que soit celui qui réussit.
À droite. +1. L'algorithme que vous décrivez, tout en correct, est pertinent pour un PRAM CRCW avec le schéma d'écriture "commun" . Ma question était spécifiquement destinée à un équipage (lecture simultanée, écrite exclusive), où les écritures simultanées ne sont pas autorisées.
Qu'est-ce que "le plus rapide" signifie ici? Ne dépendrait-il pas des coûts relatifs de l'exécution du code, de la lecture de la mémoire, de la mémoire d'écriture, de la comparaison de numéros, ainsi que de la manière dont le cache fonctionne?
@aix: Vous pourriez avoir raison. Cela ne me dérange pas si quelqu'un le pomple pour un mouvement là-bas. Jusque-là, je le laisse rester ici. Il s'agit toujours de la programmation après tout.
@Paulhankin: Je parle de la complexité ici. c.-à-dire que les constantes telles que "5ms" à lire, "10ns" un cycle, un cycle de cache, etc. considèrent simplement des choses comme "lire", "écrire", "comparer" comme opération: en.wikipedia.org/wiki/analysis_of_algorithms
@casperone Cette question implique des faits et a une réponse correcte unique. Ce n'est pas une question d'opinion, de débat, de vote, etc., donc je pense que cela devrait être rouvert.
@casperone - depuis quand les gens ont-ils commencé à avoir des "opinions" ou "sondages" ou "débats" sur une limite supérieure serrée au temps pris pour résoudre un problème précisément défini?