Problema de la Coherencia de Caché y Soluciones

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Problema de la Coherencia de Caché y Soluciones

Profesor: Ing Elfego Gutierrez Ocampo

Alumno: Eduardo Manuel Flores Vera

PROBLEMA DE LA COHERENCIA DE CACHÉ

Pensemos por un momento cual es el modelo intuitivo que tenemos de lo que debe ser una memoria.


La memoria debe proporcionar un conjunto de direcciones para almacenar valores, y cuando se lea una de estas direcciones debe devolver el ´ultimo 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´an 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

Sin embargo, 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://informatica.uv.es/iiguia/AAC/AA/apuntes/aic_multiproc.pdf
http://www.azulweb.net/ley-de-moore-podcast-5/
http://es.wikipedia.org/wiki/Coherencia_de_cach%C3%A9

Suma PRAM CREW----- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Suma PRAM CREW----- Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera


#Flores Vera Eduardo Manuel
import threading
import math
import os
#Definicion del hilo
def hilo(i,j):
    a[j]=a[j]+a[j-pow(2,i-1)]
    print a

#Programa Principal
print 'SUMA CREW'
a=[]
x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
    n=int(raw_input("INGRESE DATO:"))
    a.append(n)
    print a
    i+=1


n1=len(a)
lg=int(math.log(n1))

for i in range(1,lg):
    for j in range((pow(2,i-1)+1),n1):
        h = threading.Thread(target=hilo,args=(i,j))
        h.start()
        h.join()
        print i,j

print a


os.system('pause')

Multiplicación de Matrices CREW----- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Multiplicación de Matrices CREW----- Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera


#Flores Vera Eduardo Manuel
from threading import Thread
import math
import os

#Definicion de Funciones



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])


#Programa Principal

print "================MULTIPLICACION DE MATRICES CREW==========================="


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             LLENADO DE LA MATRIZ A:"
i=0
while(i<2):
    j=0
    while(j<2):
       
        print "INGRESE EL VALOR DE LA COORDENADA [",i+1 ,", ",j+1," ]: "
        x=int(raw_input())
        A[i][j]=x
        j=j+1
    i=i+1

print "\n\n             LLENADO DE LA MATRIZ B:"
i=0
while(i<2):
    j=0
    while(j<2):
       
        print "INGRESE EL VALOR DE LA COORDENADA [",i+1 ,", ",j+1," ]: "
        x=int(raw_input())
        B[i][j]=x
        j=j+1
    i=i+1


print "\nPROCEDIMIENTO DE LAS MULTIPLICACIONES : \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


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


print "\nRESULTADO de LAS MULTIPLICACIONES DE LAS MATRICES A Y B: \n"

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

os.system('pause')

Ordenamiento PRAM EREW Recursivo con Odd-Even Merge Paralelo------- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Ordenamiento PRAM EREW Recursivo con Odd-Even Merge Paralelo-------Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera






#Flores Vera Eduardo Manuel
from threading import Thread
import os
import math


#Definicion de Funciones
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)



#Programa Principal
print "====================ORDENAMIENTO PRAM EREW RECURSIVO========================="
print""
print "\n INGRESE EL NUMERO DE VALORES A INGRESAR : "
print"(NOTA: SOLO PUEDE INGRESAR UN NUMERO PAR DE VALORES A ORDENAR)"
n=int(raw_input())
while((n%2)!=0):
    print "EL NUMERO DE VALORES NO ES PAR"
    print "INGRESE UN NUMERO DE VALORES QUE SEA PAR: "
    n=int(raw_input())

L=[0 for _ in range(n+1)]
 
i=0
while(i<n):
    print "\nINGRESE VALOR NUMERO ",i+1
    x=int(raw_input())
    L[i+1]=x
    i=i+1
 
print "VALORES INICIALES: ",L[1:n+1]
OddEvenMerge(L,1,n)

print "\nVALORES ORDENADOS: ",L[1:n+1]

os.system('pause')

Ordenamiento PRAM EREW Recursivo con Merge Secuencial------- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Ordenamiento PRAM EREW Recursivo con Merge Secuencial-----Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera






#Flores Vera Eduardo Manuel
import os


#Definicion de Funciones
def mergeSort(alist):
    print("DIVIDIENDO ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("UNIENDO ",alist)

#Programa Principal
alist = []
x=int(raw_input("INGRESE EL NUMERO DE VALORES A INGRESAR"))
i=1
while (i<=x):
    n=int(raw_input("INGRESE UN VALOR"))
    alist.append(n)
    i=i+1
             
   
print 'VALORES ORDENADOS:'
print(alist)

os.system('pause')

Ordenamiento PRAM CRCW------ Código en Python

Universidad Autónoma de Estado de México
Facultad de Ingeniería
Programación Paralela y Distribuida


Ordenamiento  PRAM CRCW ------ Código en Python
Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera

#Flores Vera Eduardo Manuel

from threading import Thread

import os

import math

#Definicion de Funciones

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)

#Programa Principal

L=[]

L2=[]

WIN=[]

indexMin=[]

print"==================ORDENAMIENTO CRCW========================"

n=int(raw_input("INGRESE EL NUMERO DE VALORES A ORDENAR: "))

i=0

while(i<n):

    print "INGRESE VALOR",i+1,":",

    x=int(raw_input())

    L.append(x)

    L2.append(0)

    i=i+1

n=len(L)

print "\nVALORES DE ENTRADA:           ",L

i=1

while(i<=n):

    t=Thread(target=hilo1,args=(WIN,i))

    t.start()

    t.join()

    i=i+1

print "\nINICIALIZANDO UN VECTOR AUXILIAR WIN 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 "\nVALORES ORDENADOS:             ",L2

os.system('pause')

Búsqueda CRCW--------Código en Python

Universidad Autónoma de Estado de México
Facultad de Ingeniería
Programación Paralela y Distribuida


Búsqueda PRAM CRCW ------ Código en Python
Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera

#Flores Vera Eduardo Manuel

import os

import math

from threading import Thread

#Definicion de Funciones

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"========================================================================================"

L=[]

x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))

i=1

while (i<=x):

    n1=int(raw_input("INGRESE DATO:"))

    L.append(n1)

    print L

    i+=1

Win=[1,1,1,1,1,1,1,1,1,1,1,1,1]

ind=[1000000000000000000000000]

i=0

n=len(L)

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 "Señalando el valor minimo con un cero en el vector 0\n", Win 

        

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

os.system('pause')