SUMA EREW

SUMA EREW (Exclusive Read Exclusive Write)

Reducción Paralela

Algoritmo:

for i=1 to log₂  n do 

    forall P_j where 1≤ j ≥n/2 doinparallel

        if (2j modulo 2ⁱ)=0 then

a[2j]←a[2j]+a[2j-2^i-1]

        endif

    end forall

end for

En python:

import threading
import math

#Definicion del hilo
def hilo(i,j):
    if(((2*j)%int(pow(2,i)))==0):
       a[2*j]=a[2*j]+a[int((2*j)-pow(2,i-1))]

#Programa Principal
a=[0,5,2,10,1,8,12,7,3]

n=len(a)
lg=int(math.log(n,2))

for i in range(1,lg+1):
    for j in range(1,(n/2)+1):
        h = threading.Thread(target=hilo,args=(i,j))
        h.start()
        h.join()

print a