correccion de clases

Algoritmo paralelo para el cálculo de matrices de probabilidades de transición:
aplicación a la modelación de yacimientos lateríticos mediante cadenas de
Markov
Parallel algorithm to compute probability transition matrices: application to the
modeling of lateritic deposits using Markov chains
Dannier Trinchet. M.Sc.1 & Asnay Guirola. M.Sc.2
1. Universidad de las Ciencias Informáticas, Ciudad deLa Habana, Cuba.
2. Universidad de las Ciencias Informáticas, Ciudad de La Habana, Cuba.
trinchet@uci.cu, aguirola@uci.cu
Recibido para revisión 04 de junio de 2010, aceptado 28 de junio de 2011, versión final 28 de junio de 2011

Resumen─ En el presente trabajo se propone un algoritmo paralelo
para la obtención de matrices de probabilidades de transición. El
algoritmo propuesto es aplicado a lamodelación de yacimientos
lateríticos a partir de un modelo matemático basado en cadenas
de Markov. El modelo genera un hipercubo de probabilidades
condicionales, cuya cantidad de dimensiones queda fijada por la cantidad
de variables que intervienen en el modelado. Se realiza un análisis teórico
del algoritmo y se implementa en dos variantes: usando MPI para su
ejecución sobre un cluster Beowulf y apartir de un sistema distribuido
para su ejecución en una red local de estaciones de trabajo heterogéneas.
Los resultados teóricos y prácticos obtenidos demostraron que el
algoritmo es escalable y óptimo en cuanto a Ganancia de Velocidad y
Eficiencia. Se propone además, una representación matricial adecuada
para el almacenamiento de hipercubos dispersos que persigue un ahorro
significativo dememoria con el menor comprometimiento posible de
tiempo durante la ejecución del algoritmo.
Palabras claves─ Computación paralela y distribuida, Matrices de
probabilidades de transición, Modelación de yacimientos lateríticos.
Abstract─ The present paper proposes a parallel algorithm to
compute transition matrixes and it’s application in the modeling
of lateritic deposits using Markov Chains. We makesa theoretical
analysis of the algorithm and implemented it in two variants, using
MPI for execution over a Beowulf cluster and using a distributed
system to run on a network of workstations. The analytical and
empirical results shows that the algorithm is scalable and optimal
in terms of speed-up and efficiency. It also proposes a matrix
representation for store the results of modeling pretendingreduces
memory needed attend to time required for algorithm’s execution.
Keywords─ Parallel and distributed computing, High throughput
computing, Deposits lateritic modeling.

I. INTRODUCCIÓN

L

as matrices de probabilidades de transición (en lo adelante
MPT) son ampliamente usadas dentro de la modelación
matemática de procesos. Muchas veces son aplicadas como
simples herramientas paradeterminar posibles comportamientos
del proceso que se modela i.e Economía, Ecología, Ciencias
Sociales, Marketing [1]-[4]; y en otras ocasiones como parte de
modelos más complejos i.e Teoría de Autómatas Probabilísticos
y Modelado de Procesos Estocásticos [5],[6]. Formalmente una
matriz de probabilidades de transición P se define como:

 p11

p
P =  21
 

 pn1

p12 
p22 
 
pn 2 

p1n 

p2 n
 

pnn 

donde n es la cantidad de estados en los cuales puede estar
el proceso a modelar, y pij la probabilidad de que el sistema
pase del estado i al j , esta matriz cumple que:

∀i, j ∈ [1, n ] : 0 ≤ pij ≤ 1

(1)

n

∀i ∈ [1, n ] : ∑ pij =1
j =1

(2)

Suponiendo que se tiene un conjunto O de observaciones del
proceso a modelar, y en cada una de ellas el estado en el cual se
encuentra,entonces para ese proceso, P puede obtenerse mediante
el Algoritmo 1. Donde el procedimiento ajustar_probabilidad_
en_P(e1,e2), actualiza las probabilidades pe1,e 2 y pe 2,e1 , así
como todas las probabilidades que estén en la fila e1 y la e2 ,
nótese que debe garantizarse el cumplimiento de la condición (2).

Revista Avances en Sistemas e Informática, Vol.8 No.2, julio de 2011 - Medellín. ISSN...