Exécuter une boucle en parallèle

**Swaraj** · 01/12/2011, 14h42

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

**afranck64** · 01/12/2011, 14h50

hmm...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

**Swaraj** · 01/12/2011, 14h58

lol! Désolé, je ne m'attendais pas à ça!

Le but du jeu serait d'envoyer cette moitié

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

sur un processeur et celle-ci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**afranck64** · 01/12/2011, 15h13

Je l avais compris, je pensais vous laisser le faire a votre guise. Concernant la distribution pour un CPU donné

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Swaraj** · 01/12/2011, 16h19

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é ???

**tyrtamos** · 01/12/2011, 16h53

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...

**wiztricks** · 01/12/2011, 20h52

Salut,

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

**tyrtamos** · 01/12/2011, 22h08

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.

**Swaraj** · 02/12/2011, 04h56

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

On doit peut-être pouvoir s'en sortir en slicant A dans le "__main__" mais ce n'est pas viable.

**mont29** · 02/12/2011, 09h03

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 python :

Sélectionner tout - Visualiser dans une fenêtre à part

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…

**Swaraj** · 03/12/2011, 04h08

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.

**Swaraj** · 06/12/2011, 03h53

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :/

Exécuter une boucle en parallèle

Python

Discussions similaires

Partager

Partager