prog //
Penser sur le parallélisme genre GPU pour processeur
Pour commencer, je ne pense pas être le 1er avoir eux cette idée bien sur.
A l’heure actuel, une nouvelle façon de compter la complexité d’un algorithme est apparu, se basant sur le parallélisme.
On peut donc dire O(n) pour un algorithme classique.
Et O(N,P) P étant le nombre de parallélisme possible.
Un pixel shader actuellement, et nous en avons vraiment énormément que ca soit sur votre telephone portable ou votre ordinateur,est aussi puissant qu un ordinateur des années 90.
De cet façon, certain mauvais algorithme, deviennent bon, mais d autre, bon avant mais pas du tout parallélisable, deviennent mauvais !
Imaginons que vous devez trouver le plus grand float dans 4 giga de donnees.
En pensant de facon normal, il n y a aucun choix : il faut tout parcourir
En pensant en //, le problème devient beaucoup plus simple : chaque processeur fait un bloc d’une certaine taille, et envoie a une position sont résultat…puis ce bloc est a son tour fait ainsi…
L execution est devenu énormément plus rapide.
Autre exemple :
Imaginons un arbre binaire non trier,et nous cherchons un noeud specifique.
Avec un seul CPU, pas le choix : on doit parcourir l arbre entier jusqu a la fin.
En parallèle, cela devient different : l algorithme dit en fait “je vais gauche,puis droite” en permanence avec un seul CPU. donc, pour la 1er iteration :
( G pour Gauche,D pour Droite )
GGGGGGGGG
2eme :
GGGGGGGGD
3eme :
GGGGGGGDG
puis
GGGGGGGDD
bref avec 0 pour G et 1 pour droite, on obtient :
000000011 pour le dernier
Ceci permet d’encoder le parcours a suivre pour le processeur N.
Donc pour un arbre de profondeur de 1024, 1024 CPU suffisent, et la complexite est constante : O(1024) soit O(1) .
A voir : GPU.JS pour tester sur JS ce concept.
Ou Julia qui permet de compiler sur cpu et gpu.