domingo, 17 de mayo de 2015







 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.





ALUMNO: JUAN GARCÍA GARCÍA.


PROBLEMA DE LA COHERENCIA DE CACHÉ Y SOLUCIONES.



PROBLEMA DE LA COHERENCIA DE CACHÉ

La memoria debe proporcionar un conjunto de direcciones para almacenar valores, y cuando se lea una de estas direcciones debe devolver el último valor escrito  en ella.

 Es en esta propiedad fundamental de las memorias en la que descansan los programas secuenciales cuando usamos la memoria para comunicar un valor desde un punto del programa donde se calcula a otros puntos donde es usado.
También nos basamos en esta propiedad cuando el sistema usa un espacio de direcciones compartido para comunicar datos entre hebras o procesos que se están ejecutando en un procesador. Una lectura devuelve el ´ultimo valor escrito en esa dirección, sin importar el proceso que escribió dicho valor.


 Las cachés (antememorias) no interfieren con el uso de múltiples procesos en un procesador, ya que todos ellos ven la memoria a través de la misma jerarquía de cachés. En el caso de usar varios procesadores, nos gustaría poder basarnos en la misma propiedad cuando dos procesos se ejecuten sobre diferentes procesadores de tal forma que el resultado de ejecutar un programa que usa varios procesos sea el mismo independientemente de si los procesos se ejecutan o no en diferentes procesadores físicos. Sin embargo, cuando dos procesos ven la memoria compartida a través de diferentes cachés, existe el peligro de que uno vea el nuevo valor en su caché mientras que el otro todavía vea el antiguo.

Informalmente se puede decir que un sistema de memoria es coherente si cualquier lectura de un dato devuelve el valor más recientemente escrito de ese dato. Esta definición, aunque intuitivamente correcta, es vaga y simple; la realidad es bastante más compleja. Esta definición simple contiene dos aspectos diferentes del comportamiento del sistema de memoria, siendo los dos críticos a la hora de escribir programas en memoria compartida. El primer aspecto, llamado coherencia definen los datos devueltos por una lectura. El segundo aspecto, llamado consistencia, determina cuando un valor escrito ser´a devuelto por una lectura



Los problemas de coherencia en la caché también ocurren cuando utilizamos un ´único procesador en el caso de las operaciones de E/S. La mayoría de estas operaciones se realizan a través de dispositivos DMA con lo que es posible que que el contenido de la memoria principal y la memoria caché dejen de ser coherentes.



SOLUCIONES

Dado que las operaciones de E/S son mucho menos frecuentes que las operaciones de acceso a memoria, se han adoptado soluciones sencillas como usar direcciones de memoria que se marcan como no almacenables en la memoria caché o eliminar todos los bloques existentes en las cachés de las páginas que se van a utilizar en la operación de E/S antes de proceder a realizar dicha operación. En la actualidad, casi todos los microprocesadores proporcionan mecanismos para soportar la coherencia de cachés


REFERENCIAS

http://www.azulweb.net/ley-de-moore-podcast-5/
http://informatica.uv.es/iiguia/AAC/AA/apuntes/aic_multiproc.pdf
http://es.wikipedia.org/wiki/Coherencia_de_cach%C3%A9

jueves, 26 de marzo de 2015




FECHA: 26 DE MARZO DE 2015.




 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.




 ALUMNO: JUAN GARCÍA GARCÍA.

  

#MULTIPLICACION DE MATRICES CREW
#JUAN GARCIA GARCIA

from threading import Thread
import math

##Usando 2 hilos como nos dice la descripcion del problema
def hilo1(i,j,k):
    C[k][i][j]=int(A[i][k])* int(B[k][j])

def hilo2(i,j,k,l):
    if(((2*k) % (2 **l))==0):
        C2[2*k][i][j]=int(C[2*k][i][j]+C[2*k-(2**(l))][i][j])

print"--------------------------------------------------------------------------------"
print "                        MULTIPLICACION DE MATRICES CREW"
print"--------------------------------------------------------------------------------"
print""

A=[[0 for _ in range(2)] for _ in range(2)]
B=[[0 for _ in range(2)] for _ in range(2)]
C=[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]
C2=[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]
    
lg=int(math.log(2,2))
print "\n\n                       Matriz A:"
i=0
while(i<2):
    j=0
    while(j<2):
        #Llenado de la Matriz A
        print "Dame la cordenada [",i+1 ,", ",j+1," ]: "
        x=int(raw_input())
        A[i][j]=x
        j=j+1
    i=i+1

print "\n\n                     Matriz B:"
i=0
while(i<2):
    j=0
    while(j<2):
        #Llenado de la Matriz B
        print "Dame la cordenada [",i+1 ,", ",j+1," ]: "
        x=int(raw_input())
        B[i][j]=x
        j=j+1
    i=i+1

#Mostrando la operacion a realizar
print "\nMultiplicaciones : \n"
print "[ ",A[0][0],"  ",A[0][1]," ]      X      [ ",B[0][0],"  ",B[0][1]," ]"
print "[ ",A[1][0],"  ",A[1][1]," ]      X      [ ",B[1][0],"  ",B[1][1]," ]"

k=0
while(k<2):
    i=0
    while(i<2):
        j=0
        while(j<2):
            t=Thread(target=hilo1,args=(i,j,k))
            t.start()
            t.join()
            j=j+1
        i=i+1
    k=k+1

#Descomposicion
print "\n\nPrimer Proceso: ",C

l=0
while(l<lg):
    i=0
    while(i<2):
        j=0
        while(j<2):
            k=0
            while(k<1):
                t=Thread(target=hilo2,args=(i,j,k,l))
                t.start()
                t.join()
                k=k+1
            j=j+1
        i=i+1
    l=l+1

#Resultado de la multiplicacion CREW
print "\nResolucion de  A X B: \n"

print "          [ ",C2[0][0][0],"  ",C2[0][0][1]," ]"
print "          [ ",C2[0][1][0],"  ",C2[0][1][1]," ]"
    

  





FECHA: 19 DE MARZO DE 2015.




 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.




 ALUMNO: JUAN GARCÍA GARCÍA.

  




#ORDENAMIENTO PRAM EREW RECURSIVO
#JUAN GARCIA GARCIA


from threading import Thread

def hilo3(L2,INI,FIN):
    oddEvenMerge(L2,INI,FIN)
    print "procesos: ",L2[1:FIN+1]
 

def OddEvenMerge(L2,INI,FIN):
    t3=Thread(target=oddEvenMerge,args=(L2,INI,FIN))
    t3.start()
    t3.join()

def oddEvenMerge(L2,INI,FIN):
    m=(FIN-INI)+1
    odd=[0 for _ in range((m/2)+1)]
    even=[0 for _ in range((m/2)+1)]
    if(m==2):
        if(L2[INI]>L2[FIN]):
            intercambio(L2,INI,FIN)
    else:
        oddEvenSplit(L2,odd,even,INI,m)
        t=Thread(target=ordena,args=(odd,(m/2)))
        t.start()
        t.join()
        t2=Thread(target=ordena,args=(even,(m/2)))
        t2.start()
        t2.join()
     
        i=1
        while(i<=(m/2)):
            t=Thread(target=mezcla,args=(L2,odd,even,i,1))
            t.start()
            t.join()
            i=i+1
         
        i=1
        while(i<int(m/2)):
            t=Thread(target=HiloOddEven,args=(L2,i))
            t.start()
            t.join()
            i=i+1
        i=1
        while(i<=int(m/2)):
            t=Thread(target=HiloOddEvenC,args=(L2,i))
            t.start()
            t.join()
            i=i+1
     

def intercambio(L2,INI,FIN):
    aux=L2[INI]
    L2[INI]=L2[FIN]
    L2[FIN]=aux


def oddEvenSplit(L2,odd,even,INI,FIN):
    od=1
    ev=1
    x=INI
    while(x<=FIN):
        if((x%2)==0):
            even[ev]=L2[x]
            ev=ev+1
        else:
            odd[od]=L2[x]
            od=od+1
        x=x+1
    print "valor  odd: ",odd[1:FIN+1]
    print "\nvalor  even: ",even[1:FIN+1]

 
def ordena(L2,FIN):
    L3=L2
    numero=FIN
    OddEvenMerge(L3,1,numero)


def mezcla(L2,odd,even,j,aux):
    m=L2
    impar=odd
    par=even
    m[(2*j)-1]=impar[j]
    m[2*j]=par[j]


def HiloOddEven(num,i):
    numero=num
    j=i
    a=(2*j)
    b=(2*j)+1
    if(numero[a]>numero[b]):
        intercambio(numero,a,b)

def HiloOddEvenC(num,i):
    numero=num
    j=i
    a=(2*j)-1
    b=(2*j)
    if(numero[a]>numero[b]):
        intercambio(numero,a,b)







print "                                ORDENAMIENTO PRAM EREW RECURSIVO"
print"-------------------------------------------------------------------------------"
print"(SOLO CON MULTIPLOS DE 2 (2-4-8-etc))"
print""
print "\n Con cuantos datos desea trabajar? : "
n=int(raw_input())
while((n%2)!=0):
    print "La dimension de la lista no es multiplo de 2!"
    print "Ingrese una dimension que sea multiplo de 2: "
    n=int(raw_input())

L=[0 for _ in range(n+1)]
 
i=0
while(i<n):
    print "\nDame numero ",i+1
    x=int(raw_input())
    L[i+1]=x
    i=i+1
 
print "Vector Inicial: ",L[1:n+1]
OddEvenMerge(L,1,n)

print "\nVector Ordenado: ",L[1:n+1]




FECHA: 17 DE MARZO DE 2015.




 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.




 ALUMNO: JUAN GARCÍA GARCÍA.



#ORDENAMIENTO CRCW
#JUAN GARCIA GARCIA




from threading import Thread

#Procesos de Hilos

def hilo1(win,i):
    win.insert(i,0)


def hilo2(win,i,j):
    if(L[i]>L[j]):
        win[i]=win[i]+1
    else:
        win[j]=win[j]+1


def hilo3(i,win):
    L2.insert(win[i],L[i])
    L2.pop(win[i]+1)



L=[]
L2=[]
WIN=[]
indexMin=[]

print"                                  ORDENAMIENTO CRCW"
print"---------------------------------------------------------------------------"
print""

n=int(raw_input("Con que cantidad de datos deseas Trabajar: "))
i=0
while(i<n):
    print "Dame numero",i+1,":",
    x=int(raw_input())
    L.append(x)
    L2.append(0)
    i=i+1

n=len(L)
print "\nVector de Entrada:           ",L
i=1
while(i<=n):
    t=Thread(target=hilo1,args=(WIN,i))
    t.start()
    t.join()
    i=i+1
print "\nInicializa WIN:              ",WIN
i=0

while(i<=n):
    j=i+1
    while(j<n and i<j):
        t=Thread(target=hilo2,args=(WIN,i,j))
        t.start()
        t.join()
        j=j+1  
    i=i+1

print "\nLlenando el indice de  WIN:  ",WIN
i=0
while(i<n):
    t=Thread(target=hilo3,args=(i,WIN))
    t.start()
    t.join()
    i=i+1
print "\nVector Ordenado:             ",L2


  

  





FECHA: 14 DE MARZO DE 2015.




 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.




 ALUMNO: JUAN GARCÍA GARCÍA.

  

  
#BUSQUEDA PRAM CRCW
#JUAN GARCIA GARCIA


import math
from threading import Thread

#HILOS

def hilo1(Win,i):
    Win[i]=0
    
def hilo2(L,Win,i,j):
    if(L[i]>L[j]):
        Win[i]=1
    else:
        Win[j]=1
    
def hilo3(Win,i,ind):
    if(Win[i]==0):
        ind[0]=i


print "                              BUSQUEDA PRAM CRCW"
print"----------------------------------------------------------------------------"

#Aqui esta el vector inicial estatico  Dado
L=[95,34,6,56]
Win=[1,1,1,1]
ind=[10000000]
i=0
n=len(L)

#WHILES......

while(i<n):
    if(i>=0):
        t = Thread(target=hilo1, args = (Win,i))
        t.start()
        t.join()
    i=i+1
i=0
j=i+1

print "PROCESO 1"
print "Vector original:----->", L
print Win

while(j<n):
    if(i<j):
        if(i>=0):
            t = Thread(target=hilo2, args = (L,Win,i,j))
            t.start()
            t.join()
    i=i+1
    j=j+1
i=0
print "\nPROCESO 2"
print Win



while(i<n):
    if(i>=0):
        t = Thread(target=hilo3, args = (Win,i,ind))
        t.start()
        t.join()
        i=i+1

print "\nPROCESO 3"
print "Encontrando el minimo señalado con un 0\n", Win 

        
print " \nEl valor minimo es:  ", L[ind[0]]





FECHA: 12 DE MARZO DE 2015.




 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.




 ALUMNO: JUAN GARCÍA GARCÍA.

  

  
#BUSQUEDA PRAM EREW
#JUAN GARCIA GARCIA

import math
from threading import Thread


def hilo1(Temp2,i,j):
    Temp2.insert(j,Temp2[j-(2**i-1)])
    

def hilo2(K,Temp2,x,n):
    if(x<(n-1)):
        if(K[x]==Temp2[x]):
            Temp2[x]=x+1
        else:
            Temp2[x]=99999


def hilo3(Temp2,n,k):
    if(Temp2[(2**(k))-1]>Temp2[2**k]):
        Temp2[k]=Temp2[2*k]
    else:
        Temp2[k]=Temp2[(2**(k))-1]


def Broadcast(Temp,x,n):
    Temp2=[]
    Temp2=Temp
    Temp2.insert(0,numero)
    Temp2.insert(1,numero)
    i=1
    while(i<=lg):
        j=(2**(i-1))+1
        while(j<=2**i):
            t=Thread(target=hilo1,args=(Temp2,i,j))
            t.start()
            t.join()
            j=j+1
        i=i+1
        


def SearchPram(Temp,lista,n):
    i=0
    while(i<=n):
        t=Thread(target=hilo2,args=(lista,Temp,i,n))
        t.start()
        t.join()
        i=i+1


def MinPram(Temp,n):
    i=1
    while(i<=lg):
        j=1
        while(j<=int(n/(2**j))):
            t=Thread(target=hilo3,args=(Temp,n,i))
            t.start()
            t.join()
            j=j+1
        i=i+1





a=[]
Temp=[]
lista=[2,-1,23,-4,2,5,-2,5,-2,0,5,1,5,-5,8,5,3,-2]
n=len(lista)
lg=int(math.log(n,2))
# ->  Esta parte es estatica solo agregar a la variable  numero el numero a buscar
numero=0 
print "                             BUSQUEDA PRAM EREW"
print "------------------------------------------------------------------------"
print "VECTOR DE ENTRADA:"
print lista
Broadcast(Temp,numero,n)
print "------------------------------------------------------------------------"
print "\nVECTOR TEMPORAL: "
print Temp
SearchPram(Temp,lista,n)
print "------------------------------------------------------------------------"
print "\nINDICES:"
print Temp
MinPram(Temp,n)
h=1
while(h<len(Temp)):
    if(Temp[h]!=99999):
        pos=Temp[h]
        break
    h=h+1
print "------------------------------------------------------------------------"
print "DONDE",numero," ESTA EN LA POSICION NUMERO: ",pos





FECHA: 10 DE MARZO DE 2015.




 CLASE: PROGRAMACIÓN PARALELA Y DISTRIBUIDA.




 PROFESOR: DR. GUTIERREZ OCAMPO ELFEGO.




 ALUMNO: JUAN GARCÍA GARCÍA.

  

  
#SUMA PRAM CREW
#JUAN GARCIA GARCIA


import math
from threading import Thread


def hilo(i,j):
    b[j] = a[j]+a[int(j-2**(i-1))]

# --> Aqui agregamos el arreglo estatico que se desea SUMAR
print "                           SUMA PRAM CREW"
print "------------------------------------------------------------------------"
a = [0,5,2,10,1,8,12,7,3]
b=[0,0,0,0,0,0,0,0,0]
n = len(a)-1
lg = int(math.log(n,2))
print a
print "Vector Inicial"
print ""
i = 1
while(i<lg):
    j=i
    while(j<=n):
        if((2**(i-1))+1<=j):
            t = Thread(target=hilo, args=(i,j))
            t.start()
            j = j+1
            t.join()
        else:
            b[j]=a[j]
            j=j+1
        print "Proceso Suma"
        print b
    i=i+1
    a=b