Exécuter une boucle en parallèle

Version imprimable

Bonjour à tous,

Je souhaiterais me lancer dans un petit projet perso. Je n'ai pas encore décidé le langage que j'allais utiliser. Ma préférence va pour le moment pour Python grâce à sa simplicité et toutes les bibliothèques scientifiques disponibles. Cependant il me reste une interrogation quand au parallélisme, qui pourrait peut-être me faire aller vers Scala...

Il se trouve que dans mon appli, il y a beaucoup (vraiment beaucoup) de boucles imbriquées à exécuter de type
Code:

1 2 3 4 5 6 7 8 9 10 11 12 from numpy import * nA=10 nB=20 A=[random.rand(5,5) for i in range(nA)] B=[random.rand(5,3) for i in range(nB)] C=[] for i in range(nA): for j in range(nB): C.append(dot(A[i],B[j]))
Je voudrais savoir si ce bout de code est facilement parallélisable d'un point de vue pratique (en coupant A en 2 par exemple). Si la réponse est oui, comment faut-il s'y prendre?

Merci pour votre aide

PS: Petite question annexe, est-ce que je peux pré-allouer la taille de la liste C pour aller plus vite?

hmm...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
a = 61
b = 32
A = range(a)
B = range(b)
C = []
for i in A[:a/2]:
    for j in B:
        C.append((i,j))
 
for i in A[a/2:]:
    for j in B:
        C.append((i,j))
 
print len(C), a*b

De cette manière?

01/12/2011, 14h58
Swaraj
lol! Désolé, je ne m'attendais pas à ça!

Le but du jeu serait d'envoyer cette moitié
Code:

1 2 3 for i in A[:a/2]: for j in B: C.append((i,j))
sur un processeur et celle-ci
Code:

1 2 3 for i in A[a/2:]: for j in B: C.append((i,j))
sur un autre

Bref, je souhaiterais partager ma boucle sur plusieurs processeurs.

Je l avais compris, je pensais vous laisser le faire a votre guise. Concernant la distribution pour un CPU donné :aie: par contre, vous pouvez faire appel a des Threads et je pense qeu l os se charge de gérer la distribution du boulot aux CPUs présent.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #!/usr/bin/env python import threading import time a = 61 b = 32 A = range(a) B = range(b) C = [] def f1(): for i in A[:a/2]: for j in B: C.append((i,j)) def f2(): for i in A[a/2:]: for j in B: C.append((i,j)) threading.Thread(None,target=f1).start() threading.Thread(None,target=f2).start() time.sleep(1) # sinon l affichage se fera avant la fin des processus. print len(C), a*b

Hum, je m'excuse, j'avais mal compris le message :/ Avec votre dernier post j'ai un petit peu étoffé le programme pour arriver à ça

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#!/usr/bin/python
# -*-coding:Utf-8 -*
 
import threading
import time
from numpy import *
 
nA=200
nB=200
 
m=500
A=[random.rand(m,m) for i in range(nA)]
B=[random.rand(m,1) for i in range(nB)]
C1=[]
 
t1 = time.clock()
for i in A:
    for j in B:
        C1.append(dot(i,j))
print(time.clock()-t1)
 
 
 
C21=[]
C22=[]
t2=time.clock()
def f1():
    for i in A[:(nA/2)]:
        for j in B:
            C21.append(dot(i,j))
 
def f2():
    for i in A[(nA/2):]:
        for j in B:
            C22.append(dot(i,j))
 
th1=threading.Thread(None,target=f1)
th2=threading.Thread(None,target=f2)
th1.start()
th2.start()
th1.join()
th2.join()
 
print(time.clock()-t2)

Le programme me renvoie:
15.14
22.26

Pourquoi prend-il autant de temps dans le cas multithreadé ???

01/12/2011, 16h53
tyrtamos

Bonjour,

A ma connaissance, les threads s'exécutent sur le même CPU puisque c'est le même processus principal. L'avantage des threads, c'est de permettre des activités asynchrones à notre échelle, mais elles sont nécessairement sérialisées au niveau CPU.

Par contre, il y a plus de chance avec le multiprocessing. Mais c'est l'OS qui se débrouille avec les CPU et pas Python. Pour exploiter les CPU multicores, peut-être faut-il aussi utiliser les dernières versions de Python 3.x?

Des infos intéressantes sur ce genre de question ont déjà été données sur ce forum. Par exemple:http://www.developpez.net/forums/d10.../threads-lock/.

Mais des infos complémentaires sur ce sujet complexe sont toujours les bienvenues...
01/12/2011, 20h52
wiztricks

Salut,

Citation:

Envoyé par tyrtamos

A ma connaissance, les threads s'exécutent sur le même CPU puisque c'est le même processus principal. L'avantage des threads, c'est de permettre des activités asynchrones à notre échelle, mais elles sont nécessairement sérialisées au niveau CPU.

Juste pour préciser: les threads peuvent s'exécuter sur plusieurs CPU, le Python de base à un Global InterLock qui "empêche" l'exécution simultanées de plusieurs threads.
Parfois Python fait appel à une "grosse" bibliothèque C qui permet de résoudre cela sans rien faire, souvent, il faut passer par multiprocessing.
=> Pour ce qui est de numpy c'est l'option 2 voir http://www.scipy.org/ParallelProgramming

Cordialement,
- W
01/12/2011, 22h08
tyrtamos

Bonjour wiztricks,

Oui, apparemment, c'est le verrou général (GIL) de Python qui limite. Par contre, le module multiprocessing semble avoir des possibilités d'utilisation des CPU multicores, et ce déjà avec Python 2.7. Et le GIL a l'air d'avoir été amélioré avec Python 3.2.

Bonjour tout le monde,

A l'aide de tous vos commentaires, et des tutos sur le module multiprocessing suivant
http://www.doughellmann.com/PyMOTW/m...ng/basics.html
http://www.doughellmann.com/PyMOTW/m...unication.html

J'arrive maintenant à ça
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #!/usr/bin/python # -*-coding:Utf-8 -* from multiprocessing import Process, Queue import time from numpy import * def mult(A,B): C=[] for i in A: for j in B: C.append(dot(i,j)) return C def multl(q,A,B,n): t = time.clock() C=[] for i in A[:n]: for j in B: C.append(dot(i,j)) q.put(C) print("time l",time.clock()-t) def multr(q,A,B,n): t=time.clock() C=[] for i in A[n:]: for j in B: C.append(dot(i,j)) q.put(C) print("time r",time.clock()-t) if __name__ == "__main__": nA=200 nB=200 m=500 t0 = time.clock() A=[random.rand(m,m) for i in range(nA)] B=[random.rand(m,1) for i in range(nB)] print("time 0",time.clock()-t0) t1 = time.clock() C1=mult(A,B) print("time 1",time.clock()-t1) print("len(C1)",len(C1)) t2=time.clock() q1=Queue() q2=Queue() pl = Process(target=multl, args=(q1,A,B,nA/2)) pr = Process(target=multr, args=(q2,A,B,nA/2)) pl.start() pr.start() C21=q1.get() C22=q2.get() pl.join() pr.join() print("time 2",time.clock()-t2) print("len(C21)",len(C21)) print("len(C22)",len(C22))
La console me renvoie
('time 0', 1.2)
('time 1', 15.060000000000002)
('len(C1)', 40000)
('time r', 11.17)
('time l', 11.24)
('time 2', 0.6500000000000021)
('len(C21)', 20000)
('len(C22)', 20000)
Sous linux, la commande "top" montre bien 2 processus python qui consomment tous les 2 autant de RAM.

Cela soulève deux questions. Tout d'abord, pourquoi 'time r' et 'time l' ne sont pas plus proches de 8 ou 9? car le blas qu'utilise numpy par défaut dans Ubuntu s'exécute sur un seul thread, du coup dot aussi.

Ensuite, puis-je diminuer l'utilisation de la RAM ? La multiplication de l'emprunte mémoire est à la fois stupide et très gênante pour mes applis. Si on utilise 8 cores on utilise 8 fois plus de RAM ? :aie: On doit peut-être pouvoir s'en sortir en slicant A dans le "__main__" mais ce n'est pas viable.

02/12/2011, 09h03
mont29
Non, c’est bien le problème du multi-processing par rapport au multi-threading*: l’intégralité du processus est dupliqué, avec ses données. Si tu ne peux pas diviser ces données avant de lancer les processus de calcul, avec 8 cœurs tu occuperas (grosso modo) 8 fois plus de mémoire. Sauf peut-être s’il y a moyen de faire de la mémoire partagée en python, mais ça, je n’en sais rien… :?

C’est bien l’intérêt des threads (la mémoire partagée), mais comme dit plus haut, le GIL a pour effet de sérialiser l’exécution des threads python.

Et je m’aperçois que ta question sur la pré-allocation d’une liste est restée sans réponse –*oui, c’est possible*:
Code:

1 2 C = [None]*5 C # [None, None, None, None, None]
Tu peux remplacer None par la valeur par défaut que tu veux. Après, il faut remplacer les C.append() par une assignation avec indice…
03/12/2011, 04h08
Swaraj

Pfffiou, d'après ce que j'ai pu lire par ci par là, une solution serait de passer par mpi4py par exemple... autant faire du C++ avec OpenMP !

Je vais essayer de m'orienter dans cette direction, surtout que j'ai une certaine expérience avec ce langage.

Bonne nuit tout le monde,

J'ai une solution qui n'est pas satisfaisante. En fait d'après http://docs.python.org/library/multi...#all-platforms, il suffit de passer les variables en variables globales. Ça donne le code suivant

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/python
# -*-coding:Utf-8 -*
 
from multiprocessing import Process
import time
from numpy import *
 
def mult():
    c = 0
    for i in A:
        for j in B:
            C[c] = dot(i,j)
            c += 1
 
def multl(n):
    t = time.clock()
    c = 0
    for i in A[:n]:
        for j in B:
            C[c] = dot(i,j)
            c += 1
    print("time l",time.clock()-t)
 
def multr(n):
    t=time.clock()
    c = n
    for i in A[n:]:
        for j in B:
            C[c] = dot(i,j)
            c += 1
    print("time r",time.clock()-t)
 
if __name__ == '__main__':
    nA=200
    nB=200
    m=500
    t0 = time.clock()
    A=[random.rand(m,m) for i in range(nA)]
    B=[random.rand(m,1) for i in range(nB)]
    print("time 0",time.clock()-t0)
 
    t1 = time.clock()
    C = (nA * nB) * [None]
    mult()
    print("time 1",time.clock()-t1)
    t2=time.clock()
 
    C = (nA * nB) * [None]
    pl = Process(target=multl, args=(nA/2,))
    pr = Process(target=multr, args=(nA/2,))
    pl.start()
    pr.start()
    pl.join()
    pr.join()
    print("time 2",time.clock()-t2)

Le problème de ce code c'est qu'il n'est pas portable a priori. Et puis je me vois mal mettre tous mes objets en variables globales... Python n'est pas encore assez mûr pour du multiprocessing :/