Questions sur les algorithmes ou les programmes qui calculent sur plusieurs unités de traitement simultanément. A ne pas confondre avec l'informatique concurrente ou distribuée!
Il y a quelques années, MapReduce a été salué comme une révolution de la programmation distribuée. Il y a eu aussi des critiques, mais dans l'ensemble, il y a eu un battage médiatique enthousiaste. Il a même été breveté! [1] Le nom rappelle mapet reducedans la programmation fonctionnelle, mais...
J'entends souvent des gens parler d' informatique parallèle et d'informatique distribuée , mais j'ai l'impression qu'il n'y a pas de frontière claire entre les 2, et les gens ont tendance à confondre cela assez facilement, alors que je pense que c'est très différent: L' informatique parallèle est...
Lorsqu'on examine la programmation simultanée, deux termes sont couramment utilisés, à savoir simultané et parallèle. Et certains langages de programmation réclament spécifiquement le support de la programmation parallèle, tels que Java . Cela signifie-t-il que la programmation parallèle et la...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Existe-t-il un algorithme très difficile à paralléliser ou la recherche est-elle toujours active? Je voulais connaître tout algorithme ou tout domaine de recherche en calcul parallèle. Tout ce que j'ai recherché a une implémentation «parallèle». Je veux juste faire une étude sur n'importe quel...
J'ai récemment lu sur les algorithmes de vérification de la bisimilarité et lu que le problème est P-complet . En outre, une conséquence de cela est que ce problème, ou tout problème P-complet, est peu susceptible d'avoir des algorithmes parallèles efficaces. Quelle est l'intuition derrière cette...
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 à p ( n ) ∈ S ( n k ) processeurs avec c , k ∈ N .O (...
Je me demande si les unités de calcul massivement parallèles fournies dans les cartes graphiques de nos jours (celle qui est programmable dans OpenCL , par exemple) sont assez bonnes pour simuler efficacement les automates cellulaires 1D (ou peut-être les automates cellulaires 2D?). Si nous...
Considérez le programme informatique très simple suivant: for i = 1 to n: y[i] = x[p[i]] Ici, et sont des tableaux d'octets à éléments, et est un tableau de mots à éléments. Ici, est grand, par exemple, (de sorte que seule une fraction négligeable des données tient dans n'importe quel type de...
Disons que nous avons une grande collection de tâches et une collection de processeurs identiques (en termes de performances) qui fonctionnent complètement dans parallèle. Pour les scénarios d'intérêt, nous pouvons supposer . Chaque prend un certain temps / cycles à terminer une fois qu'il est...
J'ai un certain nombre de questions connexes sur ces deux sujets. Tout d' abord, la plupart des textes de complexité de brillant que sur la classe . Existe-t-il une bonne ressource qui couvre la recherche de manière plus approfondie? Par exemple, quelque chose qui traite de toutes mes questions...
J'ai implémenté un tri topologique basé sur l'article Wikipedia que j'utilise pour la résolution des dépendances, mais il renvoie une liste linéaire. Quel type d'algorithme puis-je utiliser pour trouver les chemins
Je pensais que cette question était mieux servie dans la partie CS de Stack Exchange. Maintenant que nous avons des GPGPU avec des langages comme CUDA et OpenCL, les extensions multimédia SIMD (SSE / AVX / NEON) ont-elles toujours une utilité? J'ai lu récemment un article sur la façon dont les...
J'essaie de résoudre un problème SAT de 25k clauses 5k variables. Comme il fonctionne depuis une heure (précosat) et que j'aimerais en résoudre de plus gros par la suite, je cherche un Solveur SAT multicœur. Comme il semble y avoir beaucoup de solveurs SAT, je suis assez perdu. Quelqu'un...
Il faut trouver la puissance (entier positif) de la matrice des nombres réels. Il existe de nombreux algorithmes de multiplication matricielle efficaces (par exemple, certains algorithmes parallèles sont ceux de Cannon, DNS ), mais existe-t-il des algorithmes qui sont exactement destinés à trouver...
Nous avons été présentés en classe avec un algorithme pour trouver le maximum dans un tableau en parallèle en complexité temporelle avec ordinateurs.O(1)O(1)O(1)n2n2n^2 L'algorithme était: Étant donné un tableau A de longueur n: Créez un tableau d'indicateurs B de longueur n et initialisez-le avec...
Tout en essayant d'améliorer les performances de ma classe de détection de collision, j'ai constaté que ~ 80% du temps passé sur le processeur graphique, il passait sur les conditions if / else à essayer de comprendre les limites des compartiments qu'il devait parcourir. Plus précisément: chaque...
Dans Girard's Proofs and Types, nous pouvons lire: D'un point de vue algorithmique, le calcul séquentiel n'a pas d'isomorphisme de Curry-Howard, en raison de la multitude de façons d'écrire la même preuve. Cela nous empêche de l'utiliser comme un -calculus typé, bien que nous apercevions une...
Un algorithme de réseau neuronal artificiel pourrait-il être exprimé en termes d'opérations de réduction de carte? Je m'intéresse également plus généralement aux méthodes de parallélisation appliquées aux RNA et à leur application au cloud computing. Je pense qu'une approche consisterait à exécuter...
Supposons que nous voulons joindre deux relations sur un prédicat. Est-ce en NC? Je me rends compte qu'une preuve qu'il n'est pas en NC équivaudrait à une preuve que P≠ NCP≠NCP\not=NC , donc j'accepterais comme preuve un problème ouvert comme réponse. Je m'intéresse au cas général ainsi qu'aux cas...