35340

Vista previa del material en texto

Universidad de Costa Rica
Escuela de Ciencias de la Computación e Informática
Tesis de Graduación
por el grado de Licenciatura en Computación e Informática
Diseño y desarrollo de algoritmos paralelos para recuperación en una memoria 
de casos distribuida: Un Modelo Computacional Paralelo y Distribuido de la 
Memoria
Estudiante: Juan Carlos Saborío Morales, Bach.
Carné A24562
Director: Álvaro de la Ossa Osegueda, Dr.
Fecha: 15 de Noviembre de 2012
Hoja de Aprobación 
El día 27 de Julio de 2012, se presentó el trabajo final de graduación titulado "Diseño y 
Desarrollo de Algoritmos Paralelos para Recuperación en una Memoria de Casos Distribuida", para 
optar ·por el grado académico de Licenciatura en Computación e Informática, ante el siguiente Tribunal 
examinador. 
Dra. Elena Gab1rS!a.lS~inte 
D" 13 
Escuela de Ciencias de la Computación e Informática, 
Presidente del Tnbunal 
~~ 
Dr. Arturo Camacho Lo:zano 
Profesor Invitado al Tribunal 
~a<-<.C- ~ /el 
r.~~- lleana AlpízM as 
Miembro del Comité esor 
Dr. José Castro Mora 
Miembro del Comité Asesor 
Reconocimientos
Al Colaboratorio Nacional de Computación Avanzada (CNCA), del Centro 
Nacional de Alta Tecnología (CeNAT), institución que facilitó recursos imprescindibles para 
la realización del proyecto.
iii
Índice General
1.Introducción.................................................................................................10
1.1. Antecedentes............................................................................................................11
1.2. Justificación.............................................................................................................14
1.3. Descripción y alcance...............................................................................................15
2.Objetivos ...................................................................................................17
2.1. Objetivo General......................................................................................................17
2.2. Objetivos Específicos..............................................................................................17
3.Marco Teórico .............................................................................................18
3.1. Memoria Computacional .........................................................................................18
3.1.1. Modelos computacionales de la memoria.........................................................21
3.2. Razonamiento Basado en Casos...............................................................................23
3.2.1. Ciclo del Razonamiento Basado en Casos........................................................25
3.2.2. Razonamiento basado en casos y razonamiento por analogías.........................26
3.2.3. Formalización de una memoria de casos..........................................................27
3.3. Computación Paralela..............................................................................................38
3.3.1. Definición y justificación.................................................................................38
3.3.2. Medidas de desempeño....................................................................................40
3.3.3. Tipos de problemas..........................................................................................42
3.3.4. Arquitecturas Paralelas.....................................................................................43
3.3.5. Diseño de Programas Paralelos........................................................................46
3.4. Algoritmos paralelos de búsqueda en árboles y grafos.............................................51
3.4.1. Búsqueda en profundidad.................................................................................51
iv
3.4.2. Búsqueda Mejor-Primero.................................................................................57
4.Construcción de una memoria de casos....................................................61
4.1. Razonamiento basado en casos y memoria de casos................................................61
4.2. Índices......................................................................................................................62
4.2.1. Selección del vocabulario.................................................................................63
4.2.2. Selección de los índices....................................................................................64
4.2.3. Estructuras lógicas para organizar índices y casos............................................65
4.2.4. Construcción de una estructura a partir de los índices......................................66
4.2.5. Recuperación de casos......................................................................................68
4.2.6. Adaptación y presentación...............................................................................71
5.Metodología..................................................................................................72
6.Desarrollo.....................................................................................................78
6.1. Diseño del sistema lógico.........................................................................................78
6.1.1. Estructura lógica...............................................................................................78
6.1.2. Diseño de funciones básicas.............................................................................84
6.1.3. Diseño de la recuperación de casos..................................................................88
6.2. Diseño del sistema computacional...........................................................................90
6.2.2. Estructura de datos...........................................................................................91
6.2.3. Definición de componentes..............................................................................93
6.2.4. Distribución de los datos..................................................................................94
6.2.5. Análisis sintáctico (parsing)..............................................................................96
6.2.6. Estrategias de distribución y separación del dominio.......................................98
6.2.7. Recuperación de casos....................................................................................100
6.2.8. Búsqueda recursiva.........................................................................................102
v
6.2.9. Similitud.........................................................................................................104
6.2.10. Construcción de la red de discriminación redundante..................................105
6.2.11. Sistema completo.........................................................................................107
6.3. Aspectos de implementación..................................................................................108
6.3.1. Base de casos del sistema CABATA..............................................................109
6.3.2. Descripción del dominio................................................................................110
6.3.3. Colección de casos.........................................................................................110
6.3.4. Formalización de los casos.............................................................................110
6.3.5. Selección del vocabulario...............................................................................111
6.3.6. Selección de los índices..................................................................................112
6.3.7. Distribución....................................................................................................112
6.3.8. Similitud.........................................................................................................1127.Evaluación y análisis de resultados.........................................................114
7.1. Validez...................................................................................................................114
7.2. Rendimiento...........................................................................................................115
7.3. Análisis de complejidad.........................................................................................117
7.3.1. Solución secuencial........................................................................................118
7.3.2. Solución paralela............................................................................................118
7.4. Análisis de rendimiento..........................................................................................120
7.4.1. Diseño del experimento..................................................................................120
7.4.2. Medición del tiempo de respuesta..................................................................122
7.4.3. Aceleración y eficiencia.................................................................................125
7.4.4. Escalabilidad..................................................................................................129
7.5. Uso de computación cluster...................................................................................131
7.6. Resultados..............................................................................................................131
vi
8.Conclusiones generales y recomendaciones............................................139
8.1. Síntesis de los logros del trabajo............................................................................139
8.2. Incógnitas resueltas................................................................................................145
8.3. Problemas pendientes o separados.........................................................................146
9.Bibliografía................................................................................................149
vii
Resumen
El objetivo de esta investigación es proponer, diseñar y desarrollar algoritmos 
paralelos en un ambiente distribuido, que permitan implementar el paradigma clásico de 
razonamiento basado en casos de forma innovadora y que reduzcan los problemas de 
escalabilidad propios de esta representación del conocimiento.
El razonamiento basado en casos provee un marco de referencia para modelar el 
razonamiento humano cuando este se basa en la adaptación de experiencias y conocimiento 
previo hacia situaciones nuevas. Este tipo de razonamiento no ha sido desarrollado 
extensivamente mediante modelos formales, ya que presenta un difícil tratamiento 
matemático. Por otra parte, al representar experiencias y contextos, el razonamiento basado 
en casos provee un mecanismo de simulación computacional de la memoria episódica.
Como componentes metodológicos importantes en este proyecto se destacan el 
diseño y análisis de algoritmos paralelos y de estructuras de datos complejas, el diseño de un 
modelo computacional, y la aplicación de diversas técnicas analíticas, de suma importancia 
para la computación paralela y científica. Se utilizó como problema de ejemplo la base de 
casos del sistema CABATA, la cual representa conocimiento sobre viajes. A partir de esta 
base de casos se construyó una red que permitió ejecutar los algoritmos de recuperación 
diseñados y obtener medidas de desempeño reales.
La investigación finaliza con un análisis de rendimiento y complejidad 
computacional. Se realizan también recomendaciones metodológicas para refinar los 
aspectos formales y representativos del paradigma, y se sugiere posible trabajo futuro en el 
viii
área de escalabilidad en ambientes paralelos.
ix
 
1.Introducción
El Razonamiento Basado en Casos (RBC) se popularizó principalmente entre las 
décadas de 1980 y 1990, gracias al trabajo de Roger Schank (1982) y Janet Kolodner (1993a). 
Entre sus principales aportes se encuentra la caracterización computacional de algunos procesos 
mentales relacionados con la memoria, así como un modelo lógico que permite simular el 
recuerdo cuando este se basa en la recuperación de eventos. Si bien este paradigma continua 
vigente como representación computacional del conocimiento, sus problemas computacionales 
intrínsecos, como rendimiento y eficiencia, continuan abiertos, aunque su impacto es 
relativamente manejable dada la capacidad computacional actual (mayor memoria RAM, 
frecuencia de procesador, almacenamiento masivo, etc.). Estos aspectos teóricos computacionales 
son inherentes a la modelación y se manifiestan claramente al utilizar grandes colecciones de 
datos. Esta es una razón de importancia para adaptar los modelos existentes hacia una plataforma 
moderna de ciencia computacional, que incluya modelación matemática y computación paralela y 
distribuida. Por otra parte, el RBC plantea un escenario interesante para el diseño de paralelos, 
como su eficiencia, aceleración y escalabilidad, y desarrollar técnicas analíticas para comprender 
mejor la relación entre aceleración, eficiencia, tiempo de respuesta, cantidad de procesadores, 
cantidad de procesos y tamaño del problema.
En las siguientes subsecciones se desarrollará los antecedentes y justificación que 
fundamentan esta propuesta, y se procederá a describir y delimitar con mayor detalle el problema 
por resolver.
10
11
1.1. Antecedentes
El interés por el paralelismo en modelación computacional de la memoria 
aparece desde hace varios años. A inicios de la década de los ochenta, cuando se 
popularizaron teorías conexionistas sobre la cognición, los modelos de redes neuronales 
cobran especial fuerza por su paralelismo intrínseco.1 Por ejemplo, Hopfield propuso un 
modelo de red recurrente que permite modelar memoria asociativa (Hopfield, 1982), 
mientras que McClelland planteó modelos paralelos de la memoria semántica y mecanismos 
para explicar cómo la información podría estar distribuida en la red (McClelland, 1994 y 
2000). El conexionismo asume que el procesamiento en el modelo es paralelo y distribuido 
ya que cada unidad depende sólo de sus entradas y salidas (por ejemplo en una red 
neuronal).
Kolodner, por otra parte, trabajó con modelos simbólicos como el razonamiento 
basado en casos (Kolodner, 1993a). Este paradigma facilita el tratamiento de varios 
problemas abiertos de la inteligencia artificial: toma de decisiones, razonamiento por 
analogías, recuperación de conocimiento y su adaptación posterior para resolver problemas. 
Kolodner utiliza principalmente mecanismos simbólicos de representación, como redes de 
discriminación y grafos, que aunque no son esencialmente modelos paralelos como una red 
conexionista, sí pueden ser redefinidos en un ambiente paralelo. El razonamiento basado en 
casos es apropiado para modelar aspectos de alto nivel de abstracción (procesos simbólicos), 
difíciles de implementar mediante una red neuronal.
1 Un modelo conexionista utiliza redes de unidades muy simples conectadas entre sí de forma masiva, las 
cuales pueden ejercer diferentes efectos una sobre otra. Se llaman también modelos subsimbólicos ya que 
la representación es principalemente numérica, y puede existir diferentes formas de representación en 
diferentes niveles de la red (capas, por ejemplo). Se parte del supuesto que existen fenómenos de mayor 
nivel que emergen de la interacción masiva.
12
Kolodner destacó que las colecciones de casos y las representaciones de alto 
nivel sobre la que se basa el razonamiento basado en casos podrían crecer aceleradamente, y 
planteó la necesidad de extender los modelos existentes para hacer uso del procesamiento 
paralelo (Kolodner, 1993a). Por la redundancia propia de los mecanismos de representación 
lógica del paradigma de razonamientobasado en casos, el tiempo de duración para un 
algoritmo secuencial de recuperación podría crecer aceleradamente con respecto a la 
cardinalidad del conjunto de casos.2 Sin embargo, con excepción de algunos esfuerzos, no 
ha existido mayor motivación por adaptar los modelos existentes de razonamiento basado en 
casos hacia una plataforma moderna de computación de alto rendimiento. Por ejemplo, 
Myllymäki y Tirri describieron una posible implementación “masivamente paralela” de este 
paradigma, utilizando para ello una red conexionista (sin que este sea un modelo de 
computación paralela) (Myllymäki y Tirri, 1994). Su propuesta utiliza una red neuronal para 
clasifición automática, lo cual reduce el problema de indización y generación de una 
estructura de datos, pero por otro lado es posible que se pierda algunas de las cualidades 
representativas de un modelo simbólico. Por otra parte, investigadores como Juell y Paulson 
diseñaron técnicas híbridas de aprendizaje (por reforzamiento) para un razonador basado en 
casos, que utiliza una red neuronal con algoritmo de retro-propagación para calcular la 
similitud de casos (Juell y Paulson, 2003). Sin embargo, en dicha propuesta no se replantean 
los fundamentos del paradigma, como los modelos lógicos de representación del 
conocimiento o los algoritmos de recuperación de casos. Wang propone también utilizar una 
red neuronal de retropropagación para recuperación de casos (Wang, 2009) . El paralelismo 
presente en esta familia de modelos (conexionistas) es inherente al modelo en el nivel 
conceptual, pero no necesariamente existe un mapeo con una arquitectura de procesamiento 
físicamente paralelo.
2 El orden de complejidad de un recorrido exhaustivo en amplitud-primero en un árbol n-ario con factor de 
ramificación r y profundidad p es O(rp), pues hace r comparaciones por cada nivel.
13
Hasta donde se pudo investigar, no se conocen implementaciones relevantes del 
paradigma propuesto por Kolodner (1993a), y específicamente de la recuperación de casos 
en redes de discriminación redundante, para modelar el razonamiento basado en casos en 
ambientes paralelos.
1.2. Justificación
El razonamiento basado en casos permite simular computacionalmente aspectos 
de la memoria humana relacionados con recuperación y adaptación de recuerdos, en 
contextos como la resolución de problemas y la clasificación. Si bien el modelo es útil y ha 
sido utilizado ampliamente (ver ejemplos en Kolodner, 1993a), su aplicación en tiempo real 
requiere la manipulación de grandes cantidades de información en el menor tiempo posible. 
El razonamiento basado en casos implementa aprendizaje basado en ejemplos, 
por lo que la construcción de una solución para un problema dado requiere de múltiples 
casos relevantes. La recuperación de más de un caso implica, consecuentemente, múltiples 
recuperaciones, las cuales pueden ser ejecutadas concurrentemente si el sistema utiliza 
cómputo paralelo. La recuperación concurrente es paricularmente importante al considerar 
bases de casos cada vez más grandes, y tomando en cuenta que la estructura representacional 
(red de discriminación redundante) en RBC crece aceleradamente con respecto a la cantidad 
de casos (Saborío, 2010).
Por su naturaleza compleja RBC constituye un escenario apropiado para el 
diseño de algoritmos paralelos, un área de interés personal. Adicionalmente, proyectos de 
14
investigación en computación paralela promueven el uso de la infraestructura para 
computación de alto rendimiento disponible actualmente en el país.
Por otra parte, si bien el paradigma de RBC no ha sido objeto de estudio en años 
recientes, aún es utilizado en aplicaciones como la predicción de eventos de red, asistencia o 
soporte técnico, redes de intermediarios (como bolsa de valores), y en general contextos 
donde se requiera clasificación y toma de decisiones automática. Algunas de estas 
aplicaciones, particularmente el soporte técnico y la bolsa de valores, son sensibles al tiempo 
de respuesta, por lo que se verían beneficiadas al implementar RBC en ambientes paralelos. 
Sin embargo, los fundamentos del razonamiento basado en casos no han sido revisados desde 
inicios de la década de 1990, por lo que es importante desarrollar teoría que permita adaptar 
este y otros modelos simbólicos a plataformas computacionales modernas.
Vale destacar que el desarrollo metodológico necesario para realizar esta 
investigación es aplicable a otros dominios de la inteligencia artificial, particularmente 
aquellos que se basan en modelos simbólicos.
1.3. Descripción y alcance
El presente trabajo posee como componente principal un enfoque teórico, 
centrado en el diseño de un algoritmo de recuperación de casos y una estructura de datos 
para ambientes de memoria distribuida, para implementar el paradigma de Razonamiento 
Basado en Casos en particular, y en general paradigmas simbólicos de representación del 
conocimiento, en máquinas paralelas y distribuidas.
15
Acompañando el componente teórico, se diseñó y programó el modelo propuesto 
utilizando recursos de computación paralela, lo cual permitió obtener medidas de desempeño 
que reflejan el rendimiento del sistema en aplicaciones reales.
El diseño y creación de un razonador basado en casos completo incluye varias 
etapas: modelación del problema mediante casos, generación de índices para organizar los 
casos, construcción de una estructura que organice o agrupe los índices, algoritmos de 
recuperación para localizar casos que se ajusten a un problema o situación, la adaptación de 
los casos para resolver un problema, y el mantenimiento de la colección de casos 
incorporando nuevas experiencias o refinando experiencias previas. Si bien Kolodner 
plantea que el aprendizaje en un sistema basado en casos es en gran parte un 
comportamiento que emerge del funcionamiento normal del razonador (Kolodner, 1993b), 
construir un sistema completo no está dentro de los objetivos del proyecto. Para efectos de 
esta investigación, se trató únicamente el problema de recuperación, el cual usualmente va 
acompañado de equiparación (matching) y adaptación de casos. La equiparación consiste en 
comparar casos previos con un problema nuevo de forma que se obtenga criterios de 
similitud y relevancia para resolver un problema abierto. La adaptación consiste en aplicar 
una serie de transformaciones de modo que se construya una solución apropiada para el 
problema nuevo, basada en el caso recuperado. El trabajo realizado incluye algoritmos para 
equiparación y comparación de casos, pero no para adaptación (los cuales estarían 
fuertemente ligados al área de aplicación). El modelo propuesto y el programa 
implementado contemplan entonces las etapas de generación y selección de índices, 
generación de una estructura de datos para representación del conocimiento y recuperación 
de casos relevantes (acompañado de equiparación).
16
El modelo y el software fueron diseñados tomando en cuenta la arquitectura del 
cluster del CNCA3: múltiples nodos multi-procesador de memoria local compartida (UMA), 
memoria global distribuida, con interconexión de red de alta velocidad. El cluster corre bajo 
GNU/Linux, y se utilizó el lenguaje C++ y MPICH2 para paso de mensajes.
3 Colaboratorio Nacional de Computación Avanzada, Centro Nacional de Alta Tecnología (CeNAT).
 
2.Objetivos 
2.1. Objetivo General
Proponer una solución algorítmica paralela y distribuida que permita implementar un 
mecanismo de recuperación para un modelo computacional de la memoria, utilizando el 
paradigma de razonamiento basado en casos.
2.2. Objetivos Específicos
1.Diseñar una estructura de datos (apropiada para el paradigma de Razonamiento 
Basado en Casos) que pueda ser representada en forma consistente (sin pérdida de 
datos) en un ambiente distribuido.
2.Diseñar algoritmos de recuperación paralela que operen sobre la estructura delobjetivo anterior.
3.Diseñar un modelo de memoria de casos que incluya representación distribuida del 
conocimiento y recuperación paralela.
4.Implementar el modelo en un ambiente computacional distribuido y paralelo (un 
cluster de computadoras), programado utilizando las estructuras y algoritmos de los 
objetivos anteriores.
5.Probar el sistema propuesto con un conjunto de datos estándar que permita 
comparar su desempeño con otros sistemas existentes.
17
18
3.Marco Teórico 
Esta investigación plantea un enfoque multidisciplinario. Si bien el núcleo del 
trabajo se basa en teoría y métodos propios de las ciencias de la computación, es importante 
elaborar un cuerpo teórico que respalde el trabajo realizado desde diferentes áreas del 
conocimiento. El RBC hace referencia a facultades humanas (como la memoria y toma de 
decisiones), por lo cual se explica brevemente el estado de la cuestión en estudios 
psicológicos. Estos y otros estudios han alimentado el campo de la Inteligencia Artificial y 
permiten fundamentar los modelos computacionales con los que se trabaja. Se incluye 
también una formalización del paradigma de razonamiento basado en casos, que dará pie 
para formular una memoria de casos en un ambiente distribuido y paralelo. La teoría en 
computación paralela es un área de suma importancia en este trabajo, razón por la cual se 
incluye material referente a arquitecturas computacionales, diseño de algoritmos y 
programas y métodos analíticos en computación paralela.
3.1. Memoria Computacional 
El razonamiento basado en casos puede entenderse como un modelo 
computacional de algunos aspectos relacionados con la capacidad de la memoria humana 
para codificar y representar información, que es posteriormente utilizada para resolver 
problemas específicos. En inteligencia artificial se trabaja con modelos computacionales de 
capacidades humanas usualmente relacionadas con comportamiento inteligente, y son estos 
modelos los que nos permiten comprender mejor los mecanismos mediante los cuales podría 
gestarse el comportamiento inteligente en seres humanos. Muchos modelos de la I.A. son 
19
especificados mediante instrucciones suficientemente detalladas en lenguajes formales, lo 
que permite su implementación en una computadora.
Antes de explorar las familias de modelos computacionales que existen para 
trabajar con memoria humana, es necesario desarrollar algunos fundamentos que permiten 
justificar las suposiciones y aseveraciones que se hacen al modelarla. Baddeley define 
memoria como la capacidad de codificar, almacenar y recuperar información (Baddeley, 
2002). Por otro lado Gaonac'h apunta que el concepto de memoria tiene que ver con estados 
mentales que acarrean información, y que el aprendizaje se refiere a la transición entre 
estados (Gaonac'h, 2004). La memoria también puede entenderse como la retención, con el 
paso del tiempo, de representaciones internas dependientes de experiencias, así como la 
capacidad para reactivar o reconstruir dichas representaciones (Dudai y otros, 2007).
Aunque existen avances teóricos sobre activación cerebral que sugieren algún 
tipo de unidad estructural, muchos autores hacen algunas distinciones funcionales en cuanto 
a la memoria (Gaonac'h, 2004; Baddeley, 2002). Estas se refieren al tiempo que permanece 
un objeto o entidad activo en la memoria (sensorial, de corto plazo, de trabajo y de largo 
plazo). Sobre el tipo de conocimiento representado, este puede consistir en algún tipo de 
imágenes mentales o lenguaje natural y ser accesible a la conciencia, lo que se conoce como 
Memoria Declarativa.
Existen dos divisiones de la Memoria Declarativa: episódica (situaciones 
espaciotemporales, dependientes de un contexto) y semántica (conocimiento general 
independiente de tiempo y lugar). Por otra parte, los procesos perceptuales y motrices y sus 
contenidos (prácticamente inaccesibles por la conciencia) se conocen como Memoria 
20
Procedimental.
Dudai plantea que la memoria es una representación interna de naturaleza 
biológica, donde la experiencia es capaz de modificar esas representaciones codificadas 
mediante circuitos neuronales (Dudai, 2004). Él considera que los recuerdos no se 
almacenan como estados de actividad espaciotemporal del sistema nervioso, sino que 
probablemente son reconstruidos cada vez, y la recuperación (de recuerdos) es una 
activación inducida o espontánea de la representación. Dudai plantea dos escenarios 
posibles para explicar qué tipo de objetos son almacenados en la memoria: podría ser que el 
reconocimiento es la activación de un circuito dedicado, idéntico a aquel activado durante el 
entrenamiento, o bien se almacena un núcleo comprimido o un índice que permite la 
reconstrucción de toda la representación.
Algunos de los modelos psicológicos, como la memoria de trabajo de Baddeley-
Hitch, se centran principalmente en componentes funcionales de la memoria humana 
(Baddeley, 2002; Baddeley, Eysenck, Anderson, 2009). El carácter funcionalista4 de estas 
descripciones facilita la representación formal de las mismas, lo que permite la construcción 
de modelos computacionales que puedan simular tales procesos, con el objetivo de 
estudiarlos y explicarlos. También es posible construir un modelo computacional de la 
memoria humana que atienda principalmente a la biofísica cerebral, lo que implica un 
tratamiento diferente de la información contenida en tales activaciones (no simbólica), y se 
enfocaría más bien en la consolidación de patrones sinápticos ya que hacer referencia a 
funciones de alto nivel (como recuerdos) sería extremadamente complejo.
4 En Filosofía de la Mente, el Funcionalismo postula que los estados mentales son equivalentes a su función, 
por lo cual pueden ser realizados (instanciados) en máquinas biológicas como un cerebro humano, o 
máquinas no biológicas como una Máquina Universal de Turing.
21
Por otra parte, muchos modelos constituyen representaciones formales del 
conocimiento (pues representan, precisamente, varios niveles de información), y se pueden 
utilizar para abordar una variedad de problemas en dominios muy diversos. Algunos 
modelos de este tipo son el de Roger Schank (1982), y el de Janet Kolodner (1993a). 
Dentro de las ventajas de estos modelos con respecto a otros, como los sistemas basados en 
reglas, está la flexibilidad para incorporar nuevo conocimiento y modificar el existente.
3.1.1. Modelos computacionales de la memoria
Los modelos computacionales de la memoria humana pueden ser clasificados en 
una o más de las siguientes categorías (Howard, 2009):
– Modelos formales o matemáticos: Modelan el comportamiento externamente visible 
de algún aspecto sobre la memoria, como puede ser la memoria de trabajo (encargada de 
retener información necesaria para resolver problemas), sin necesidad de hacer 
referencia a la biología del fenómeno. Un ejemplo es el modelo de búferes de Atkinson 
y Shiffrin, que plantea una relación jerárquica desde memoria perceptual y de corto 
plazo hasta la memoria de largo plazo (Howard, 2009).
– Modelos conexionistas: Constituyen un nivel de representación intermedio, y utilizan 
redes con unidades simples interconectadas de forma masiva, que podrían estar 
mapeadas con regiones o funciones neuronales o no (por ejemplo etapas del 
procesamiento visual). Estas redes pueden ser simuladas mediante computadoras y 
pueden incorporar algoritmos de aprendizaje (Elman, 2004; Montage y Dayan, 2004). 
McClelland, Rumelhart y el grupo de investigación PDP (como referencia al tema, 
consultar McClelland, 1994 y 2000) propusieron en los años 80 varios modelos 
22
conexionistas de la memoria en un contexto distribuido y paralelo, principalmente en el 
contexto de redes neuronales artificiales. Del mismo modo Hopfield propuso un modelo 
de memoria asociativa basado en redes de neuronas (Hopfield, 1982).
– Modelos biofísicos: Representanprocesos cerebrales utilizando modelos de activación 
neuronal, no solamente plausibles, sino tan físicamente precisos como sea posible. 
Típicamente hacen referencia a propiedades eléctricas y computacionales como 
potencial, corrientes iónicas, plasticidad, transmisión sináptica, codificación de 
información y código neuronal. Por estas y otras razones, estos modelos son 
complicados de simular computacionalmente. Sin embargo permiten elaborar modelos 
complejos de neuronas individuales.
La memoria humana es un tema complejo y amplio, que involucra una gran 
cantidad de diferentes disciplinas y diferentes niveles de explicación. A pesar de 
popularmente se asemeja la memoria humana con un almacén de información, que es 
consultado, borrado o modificado, la evidencia contemporánea indica que la memoria, como 
proceso cognitivo superior, está presente en mucho más que sólo el recuerdo y la 
consolidación a largo plazo. Desde la perspectiva matemática-computacional, el 
razonamiento basado en casos es un modelo que incorpora resolución de problemas, 
comprensión, y aprendizaje, integrados como procesos de memoria. Involucra también la 
capacidad para adaptar conocimiento previo a situaciones innovadoras o inesperadas, y la 
capacidad para reorganizar el conocimiento preexistente de acuerdo con el recién adquirido.
Por otra parte, al representar experiencias y el conocimiento ligado a estas, el 
razonamiento basado en casos constituye un modelo formal de la memoria episódica, donde 
cada episodio está relacionado con otros mediante un conjunto de índices y vocabulario 
23
representativo. Cada caso puede ser un episodio o experiencia completa, o puede contener 
elementos de una experiencia compuesta por un conjunto de casos. En la siguiente sección 
se desarrollan los aspectos más relevantes de este paradigma.
3.2. Razonamiento Basado en Casos
A diferencia de los sistemas basados en reglas, donde el razonamiento se realiza 
por lo general desde un punto inicial en el que no se tiene conocimiento del problema, el 
razonamiento basado en casos (RBC) modela el razonamiento humano basado en la 
recuperación, reconstrucción y adaptación de recuerdos (circunstancias, contextos, 
conocimiento) relevantes para resolver problemas nuevos. En RBC la fuente primaria de 
conocimiento es una memoria o colección de casos almacenados previamente. Un caso es 
una porción contextualizada de conocimiento que representa una experiencia, la cual 
contiene una lección fundamental para alcanzar las metas del razonador. Un caso tiene dos 
partes principales: la lección que enseña, y el contexto en el cual es apropiado utilizarla 
(descrito por sus índices) (Kolodner, 1993a). La unidad básica de representación del 
conocimiento en RBC es el caso, el cual puede ser implementado mediante alguna de 
muchas técnicas que propone la inteligencia artificial (marcos, redes semánticas, predicados, 
reglas, pares atributo-valor, etc.).
La resolución de problemas y clasificación en RBC están basados en dos 
principios fundamentales: primero, que el mundo representado es regular (problemas 
similares tienen soluciones similares) y segundo que los tipos de problemas encontrados 
ocurren frecuentemente (y por lo tanto problemas futuros serán semejantes a problemas 
actuales).
24
El RBC constituye un modelo de razonamientos generales en áreas del 
conocimiento como resolución de problemas matemáticos, diagnóstico (médico, mecánico, 
etc.), explicación de eventos anómalos y toma de decisiones bajo presión (Leake, 1996). Sin 
embargo, el conocimiento general no es suficiente en muchos casos, y es por eso que RBC 
incorpora también representación para situaciones específicas, como aquellas en las que una 
solución no funcionó o no son generalizables (Kolodner, 1993a).
El RBC permite reducir muchas de las deficiencias de los sistemas basados en 
conocimiento. Algunas de estas características mencionadas por Leake son:
1)Adquisición de conocimiento: Algunos dominios son naturales para RBC, y la 
adquisición de ese conocimiento tiene un costo muy bajo. Evidentemente no todos 
los dominios son naturales para RBC, en cuyo caso pueden no existir casos o existir 
de una forma muy compleja de utilizar. Para ambos casos el conocimiento se 
obtiene a partir de episodios específicos, por lo que no es necesario descomponer 
experiencias y generalizarlas en reglas.
2)Mantenimiento del conocimiento: El RBC permite agregar nuevos casos sin la 
intervención de un experto. Dado que un sistema de RBC necesita conocer sólo los 
tipos de problemas que suelen ocurrir (con una probabilidad suficientemente alta) y 
no todos aquellos posibles, puede ser utilizado con un conjunto inicial de casos 
limitado, que sería aumentado sí y sólo si este resulta ser insuficiente.
3)Eficiencia en solución de problemas: A pesar de que los problemas cotidianos son 
por lo general NP-complejos,5 reutilizar soluciones anteriores incrementa la 
5 Un problema P es NP-complejo (NP-hard en inglés) si y sólo si existe un problema NP-completo P' que es 
reducible en tiempo polinomial a P. Un problema es NP (non-deterministic polynomial) si es resoluble en 
25
eficiencia pues se utiliza razonamientos ya resueltos en lugar de repetir todo el 
proceso. Adicionalmente, RBC almacena casos fallidos, por lo que se pueden evitar 
acciones específicas.
4)Calidad de la solución: Cuando los principios del dominio no son entendidos 
claramente, las reglas pueden contener errores. En RBC las soluciones sugeridas por 
los casos son más precisas, puesto que los casos reflejan lo que sucedió en un 
escenario (una serie de circunstancias).
5)Aceptación del usuario: En los sistemas basados en reglas, la explicación de las 
decisiones se realiza haciendo referencia a las reglas mismas, lo que se puede generar 
confusión o rechazo. En un sistema de RBC, los casos que llevaron al sistema a 
tomar una decisión pueden ser utilizados como explicaciones concretas.
3.2.1. Ciclo del Razonamiento Basado en Casos
El RBC realiza dos tipos de tareas: interpretación y resolución de problemas 
(Leake, 1996). RBC interpretativo utiliza casos como puntos de referencia para clasificar o 
caracterizar situaciones nuevas. El objetivo es clasificar o emitir un juicio acerca de una 
situación, comparándola y contrastándola con casos previamente clasificados. Un ejemplo 
de este tipo de tarea es el diagnóstico médico o mecánico, donde la sintomatología de un 
paciente u objeto puede ser comparada con la de pacientes u objetos de casos previos, con el 
fin de emitir un criterio. La resolución de problemas mediante RBC utiliza casos anteriores 
para sugerir soluciones que podrían aplicar para nuevas circunstancias. Se busca una 
solución anterior que permita resolver un problema nuevo.
tiempo polinomial por una máquina de Turing no determinista (paralela y no sincronizada). Finalmente, es 
NP-completo si el problema es tanto NP como NP-complejo (ver Weisstein, 2011).
26
Ambos tipos de tareas poseen las siguientes fases:
– Estimación de la situación para determinar qué características son relevantes.
– Recuperación de casos anteriores relevantes, según la estimación de la situación.
– Comparación de los casos recuperados con la situación presentada, con el fin de 
determinar una interpretación.
– Actualización de la memoria de casos para incluir la situación actual y su interpretación.
Adicionalmente, en la resolución de problemas mediante RBC se utilizan las 
similitudes y diferencias entre casos nuevos y existentes para determinar cómo la solución a 
un problema previo puede ser adaptada a la situación actual.
3.2.2. Razonamiento basado en casos y razonamiento por analogías
El razonamiento por analogías es un proceso de construcción de 
correspondencias a diferentes niveles. Holyoak y Thagard mencionan posibles estructuras 
mediante las cuales establecer correspondencias (Holyoak y Tharard,1995). Las siguientes 
estructuras se ejemplifican utilizando notación de predicados de primer orden:
– Atributos y objetos: Estos son principalmente de primer orden, es decir, conjuntos 
o elementos de conjuntos, pero no funciones o predicados. La abstracción de 
características permite establecer relaciones entre estos objetos. Por ejemplo, se 
puede establecer que los elementos “perro” y “Sahara” comparten la propiedad de ser 
color café mediante café(perro) y café(Sahara).
– Relaciones: En este caso la similitud entre objetos se determina a partir de las 
relaciones entre ellos. Por ejemplo, másGrande(avión, automóvil), 
27
másGrande(árbol, manzana). A partir de la relación másGrande, se puede 
establecer una correspondencia analógica entre avión y árbol, y automóvil y 
manzana. Este tipo de analogías se representa por lo general de la forma A:B::C:D.
– Sistemas: Existen situaciones complejas done los atributos y relaciones de los 
objetos constituyen un sistema (de relaciones, posiblemente de causa–efecto). En 
este caso, se definen relaciones entre objetos así como slots o ranuras, y los valores 
posibles constituyen el núcleo de la correspondencia. De esta forma ser podría 
establecer un isomorfismo entre dos sistemas.
En un sistema basado en casos, se debe construir una correspondencia una 
situación nueva con otra conocida, mediante diferentes criterios de similitud y relevancia. 
Una vez que se establece la correspondencia, el caso se adapta para reutilizar el 
razonamiento en una situación análoga. Holyoak y Thagard consideran que la analogía es 
una fuente de conjeturas plausibles, no conclusiones garantizadas (Holyoak y Thagard, 
1995). Esto describe también el razonamiento basado en casos, donde se parte de ejemplos 
y experiencias almacenadas para elaborar una solución posible para un problema nuevo.
3.2.3. Formalización de una memoria de casos
Un caso es una representación del conocimiento que contiene una lección (un 
problema y cómo resolverlo) y el contexto donde se aplica. Los casos se organizan de forma 
ordenada en una estructura de red, compuesta por nodos de diferentes tipos. Los nodos de 
tipo índice y los nodos de tipo norma permiten representar información generalizada para 
clasificar los casos jerárquicamente según su pertenencia a categorías o similitud entre sí. 
Todos los nodos contenidos en una norma comparten las características descritas en ella, 
28
mientras que un índice permite clasificar un caso por una dimensión (par atributo – valor) 
específica dentro de esa norma. Los nodos tipo caso no poseen sucesores, y pueden tener 
múltiples predecesores (índices en diferentes normas).
A continuación se desarrolla una formalización lógica de una memoria de casos 
propuesta originalmente por Michael Mehl (Mehl, 1992). Este modelo permite definir, en 
secciones posteriores, estructuras matemáticas y computacionales para implementar RBC. 
Las definiciones están acompañadas de su interpretación intuitiva.
Definiciones
1.Caso
Sean A un conjunto finito de atributos, V un conjunto finito de valores, a ∈ A y 
v, v' ∈ V. Entonces
C⊆A×Ves un caso⇔∀(a,v),(a,v') ∈C,v=v'
Es decir, un objeto C, cuyo contenido es alguna combinación de pares en A y V, se considera 
caso si y sólo si no posee atributos con valores diferentes.
2.Vector de Atributos
Sean C ⊆ AxV un caso, A = {a1, a2, ..., an}, desconocido ∉ V. El vector de 
atributos de C es v = (v1, v2, ..., vn) si:
1.∀i.1⩽i⩽n.vi∈V∪{desconocido}
2.∀i.1⩽i⩽n.(ai,vi)∈C∨vi=desconocido
Lo cual se lee de la siguiente manera: todos los valores del vector de atributos de un caso 
29
deben ser miembros del conjunto V, o ser desconocidos. Igualmente todos los valores de 
este vector deben estar asociados a un único atributo.
3.Memoria de Casos No Ordenada
Sean M un conjunto finito de nodos en una estructura de tipo grafo, el nodo raíz 
M0 ⊆ M, A un conjunto finito de atributos , V un conjunto finito de valores.
Se define la Relación de Indización como:
Dif⊆M×A×V×M.
La relación de indización es un subconjunto generado a partir de una relación entre los 
nodos de la red, y los atributos y valores de la colección. Esto es una relación entre dos nodos 
de la red conectados mediante un arco etiquetado con un par atributo-valor, lo cual permite 
recorrer la memoria de casos.
Además, se define la Relación de Información como:
Norma⊆M×A×V.
La relación de información describe los pares atributo-valor contenidos en una norma.
Una memoria de casos no ordenada MC se define como:
30
MC=〈M,M0,A,V,Norma,Dif〉.
4.Función Sucesor
Generando los sucesores de un nodo se puede recorrer una memoria de casos 
desde la raíz hasta algún nodo específico (recorrido hacia adelante). Sean MC una memoria 
de casos no ordenada, M ∈ MC un conjunto de nodos. Entonces se define la función Δ 
(sucesor) de la siguiente forma:
Δ: M → P(M).
Δ(M) = {M' ∈ M | ∃ a ∈ A . v ∈ V . (M, a, v, M') ∈ Dif}.
Es decir, la función sucesor está definida en M y su rango en el conjunto potencia de M. Los 
sucesores de un nodo constituyen un conjunto M' determinado por una relación de 
indización con M a través de un atributo y un valor de la colección.
Propiedades:
1.Δ0(M) = {M}.
2.Δn+1(M) = {Δ(M') | ∀ M' ∈ Δn(M)}.
3.Δ⁺(M) = ∪
i=1
∞
Δi(M) (Clausura transitiva).
4.Δ*(M) = ∪
i=0
∞
Δi(M) (Clausura reflexiva y transitiva).
1.El sucesor de nivel cero de un nodo o conjunto de nodos es un conjunto que contiene al 
31
mismo nodo.
2.El sucesor de un nodo a un nivel dado se obtiene calculando los sucesores de todos los 
elementos en el nivel anterior.
3.La clausura transitiva de un nodo es un conjunto que contiene los sucesores en todos los 
niveles.
4.La clausura transitiva y reflexiva de un nodo es un conjunto que contiene los sucesores 
en todos los niveles, así como el nodo mismo.
5.Función Predecesor
Generando los predecesores de un nodo se puede recorrer la memoria de casos 
desde algún nodo dado hasta la raíz (recorrido hacia atrás). Sea MC una memoria de casos 
no ordenada, entonces se define la función predecesor:
∇: M → P(M).
∇(M) = {M' ∈ M | ∃ a ∈ A, v ∈ V, (M', a, v, M) ∈ Dif}.
Es decir, la función predecesor está definida en M y su rango en el conjunto potencia de M. 
Los predecesores de un nodo constituyen un conjunto M' determinado por una relación de 
indización con M a través de un atributo y un valor de la colección.
Propiedades:
1.∇0(M) = {M}
2.∇n+1(M) = {∇(M') | M' ∈ ∇n(M)}
32
3.∇⁺(M) = ∪
i=1
∞
∇i(M) (Clausura transitiva)
4.∇*(M) = ∪
i=0
∞
∇i(M) (Clausura reflexiva y transitiva)
1.El predecesor de nivel cero de un nodo o conjunto de nodos es un conjunto que contiene 
al mismo nodo.
2.El predecesor de un nodo a un nivel dado se obtiene calculando los predecesores de 
todos los elementos en el nivel anterior.
3.La clausura transitiva de un nodo es un conjunto que contiene los predecesores en todos 
los niveles.
4.La clausura transitiva y reflexiva de un nodo es un conjunto que contiene los 
predecesores en todos los niveles, así como el nodo mismo.
6.Memoria de Casos
Una memoria MC = {M, M0, A, V, Norma, Dif} está ordenada si:
∀M',M'',M'''∈M,a∈A,v∈V:
1.M'∈Δ*(M0)
2.M'∉Δ+(M)
3.(M',a,v,M'') ∈ Dif∧(M',a,v,M''') ∈ Dif⇒M''=M'''
4.(M',a,v,M'') ∈ Dif⇒(M',a,v) ∉ Norma
5.(M',a,v,M'') ∈ Dif⇒(M'',a,v) ∈ Norma
6.(M',a,v) ∈ Norma∧(M'a,v') ∈ Norma⇒v=v'
Estos se leen formal e intuitivamente de la siguiente manera. Para los conjuntos de nodos 
33
M', M'' y M''', así como un atributo a y un valor v:
1.M' se encuentra en la clausura transitiva y reflexiva de la raíz. Es decir, la memoria 
tiene un nodo raíz, y cualquier otro nodo es alcanzable desde la raíz.
2.M' no se encuentra en la clausura transitiva de sí mismo. Es decir, no hay ciclos en la 
memoria.
3.Si M' y M'' poseen una relación de indización a través del atributo a y el valor v y M' 
posee la misma relación con M''', entonces M'' y M''' deben ser el mismo objeto.
4.Enla relación de indización entre M' y M'', M' y el par a,v no forman parte de la 
norma.
5.En la relación de indización entre M' y M'', M'' y el par a,v constituyen la norma.
6.Si un nodo M' forma una norma con un par a,v así como un par a,v', entonces v debe 
ser el mismo valor que v'.
7.Recuperación
Consiste en obtener uno o más casos de la memoria que por sus características 
sobresalientes permiten resolver un problema: se debe completar una descripción 
inicialmente incompleta. La entrada para este proceso es un conjunto de pares atributo-valor 
y un problema P, donde (a,v) ∈ P, P ⊆ AxV. Entonces:
P={(a1,v1),…,(an,vn)},dadoMC=(M,M0,A,V,Norma,Dif)
El proceso de recuperación consiste en:
34
(1)Elegir un nodo inicial N = N0.
(2)Elegir un par (a,v) ∈ P, tal que (N, a, v, N') ∈ Dif.
(3)Hacer N = N'.
(4)Repetir (2) y (3) mientras ∃ (N, a, v, N') ∈ Dif
Este proceso retorna la información del último nodo N, y considera únicamente aquellos 
índices en Dif que pueden ser generados a partir de los pares de entrada.
8.Información
La información de un nodo es el par, datos o representación del conocimiento 
contenida en ese nodo, así como las generalizaciones obtenidas de los nodos que componen 
el recorrido desde la raíz hasta su predecesor inmediato. Conforme aumenta la profundidad 
(nodos sucesores) la información es menos general y permite redefinir rasgos descritos por 
nodos predecesores.
El proceso de recuperación tiene dos componentes: recorrido hacia delante 
(función sucesor) para identificar el caso más relevante, y recorrido hacia atrás (función 
predecesor) para obtener los nodos anteriores hasta la raíz.
8.1.Reunificación
Sean C un caso, y el operador ⊕: (A×V) × (A×V) → (A×V), tal que:
1.∀C⊆A×V,C⊕∅ =C
2.∀C,C'⊆A×V,a∈A,v∈V.C ⊕ (C'∪{(a,v)})
35
donde
C ⊕ (C'∪{(a,v)}) = {C⊕C' si∃v'∈V:(a,v')∈C(C⊕C')∪{(a,v)} si no }
Es decir, la reunificación de un caso dado con un conjunto vacío retorna el caso original. En 
general, la reunificación de dos casos retorna una descripción con los pares atributo-valor 
contenidos en el primero. Si el segundo caso posee pares que no están presentes en el 
primero, entonces la reunificación utiliza estos.
8.2.Ruta
Sean MC una memoria de casos ordenada y M un conjunto de nodos. Una ruta 
R de M' a M'' en MC es una secuencia finita de nodos, R = (M1, ..., Mn) tal que:
1.∀i.1⩽i⩽n.Mi∈M.
2.M1=M'∧Mn=M''.
3.∀i.1⩽i<n.Mi+1∈Δ(Mi).
Es decir, todos los elementos de la ruta son nodos (1). Además, la ruta inicia en M' y 
finaliza en M''. Finalmente, cada nodo en la ruta es un sucesor del nodo que le antecede.
8.3.Contenido informativo
Sea R = (M0, M1, ..., Mn) la ruta que lleva a una solución (secuencia de nodos 
36
recorridos) para la entrada P. El contenido informativo I de R se determina de la siguiente 
manera:
I=P⊕((Mn,a',v')⊕( (Mn−1,a'',v'') ⊕(...⊕(M0,a''',v'''))))
donde toda tupla (Mi, a, v) ∈ Norma y ⊕ es el operador de reunificación con prioridad para 
el argumento izquierdo cuando existan pares (a,v') y (a,v'').
Formalmente, se define el contenido informativo I(R) ⊆ A×V de la siguiente 
manera. Sean MC una memoria de casos ordenada y R una ruta en MC. Luego:
1.I(R)=∅si R no tiene elementos.
2.I(R)=(Mn,a,v) ∈Norma⊕ I(R').R'=(M1,...,Mn−1).n⩾1.
Es decir, el contenido informativo de la ruta es el resultado de reunificar sucesivamente 
todos los nodos desde el último hasta el primero.
8.4.Ruta Solución
Sea MC una memoria de casos ordenada con raíz M0 y P ⊆ A×V un problema. 
Una ruta RS(P) = (M1, ..., Mn) se llama ruta solución de P con respecto a MC si:
1.M1=M0.
2.∀i.1⩽i⩽n−1.∃ (Mi,a,v,Mi+1) ∈ Dif∧ (a,v)∈P.
3.∀(a,v) ∈P.∀M'∈M .(Mn,a,v,M') ∉ Dif.
4.∀(a,v) ∈P.Δ(Mn) ∉ RS(P).
37
Lo cual se lee intuitivamente como:
1.El primer nodo de la ruta es el nodo raíz de la memoria de casos.
2.Todas las relaciones de indización entre dos nodos en la ruta contienen pares 
atributo-valor presentes en la descripción del problema.
3.El último nodo de la ruta no contiene relaciones de indización.
4.Los sucesores del último nodo de la ruta no están presentes en la ruta.
El conjunto de rutas solución de P con respecto a una memoria de casos MC se 
denota S(MC, P). Un objetivo de la recuperación paralela es generar el conjunto de rutas 
solución para una memoria de casos dada, en el menor tiempo posible.
8.5.Solución
 Sea MC una memoria de casos ordenada y P ⊆ A×V un problema. S(P) ⊆ A×V 
es una solución de P con respecto a MC si
1.∃ RS(P) respecto aMC.
2.S(P) =P⊕I(RS(P)).
Es decir, existe una ruta solución de P en MC (1). La solución está dada por la reunificación 
de la descripción del problema con el contenido informativo de la ruta solución (2).
Este modelo describe formalmente una memoria de casos, así como sus 
38
mecanismos de manipulación, almacenamiento y recuperación. En la siguiente sección se 
desarrollan conceptos de computación paralela que permiten diseñar y formalizar un modelo 
de recuperación de casos en ambientes físicamente paralelos.
3.3. Computación Paralela
El interés por el procesamiento computacional paralelo ha acompañado la 
investigación científica desde hace varias décadas. Desde la década de 1970, cuando se 
utilizaban supercomputadores de muy alto costo, se ha logrado incrementar cada vez más la 
capacidad de procesamiento de máquinas de laboratorio con el fin de resolver problemas 
cada vez más complejos, en el menor tiempo posible. La relación costo-rendimiento ha 
decrecido considerablemente desde entonces, lo cual ha permitido que centros universitarios 
y de investigación de diferentes tamaños y presupuestos tengan acceso a máquinas paralelas 
que les permitan resolver problemas de diferentes escalas. Las redes avanzadas de 
información, como Internet2 o RedCLARA, facilitan el acceso a computadoras de gran 
escala, por lo que la computación paralela es, en la actualidad, un recurso presente en todo el 
quehacer científico.
3.3.1. Definición y justificación
Un trabajo computacional usualmente consiste en la resolución de un conjunto 
de tareas, aplicadas a un conjunto de datos. La computación paralela o procesamiento 
paralelo se puede definir intuitivamente como una estrategia de trabajo colaborativo, 
semejante a la que realizamos los seres humanos, que favorece la distribución o repartición 
de tareas o de datos y su posterior asignación a diferentes unidades de procesamiento. Estas 
39
unidades pueden requerir comunicarse entre sí o sincronizarse para lograr sus objetivos. 
Finalmente, cuando todas las tareas han finalizado y se han agotado los datos, se puede 
construir una respuesta final formada por alguna combinación de los resultados parciales de 
cada unidad de procesamiento.
Por otra parte, un algoritmo paralelo es aquel que realiza múltiples instrucciones 
por unidad de tiempo. Para que estas instrucciones sean realizadas en forma concurrente 
(físicamente paralelas), se requiere una arquitectura computacional paralela, con más de un 
CPU.
La importancia de la computación paralela radica en tres principios, 
fundamentados en la realidad física:
1.Límites de la computación secuencial
La velocidad de transmisión de los componentes electrónicos depende del medio 
físico y la proximidad de dichos componentes. Sin embargo existen límites para la 
miniaturización de componentes (aún si estos fuesen de escala atómica) y por ende para la 
cantidad y proximidad de estos. En términos económicos, las interfaces de comunicación 
modernas (buses, redes de datos, etc.) convierten el uso de múltiples CPU's en una 
alternativa más atractiva que un solo CPU “extremadamente” rápido.
2.Complejidad de los fenómenos naturales
En el mundo natural, muchos eventos suceden simultáneamente y sus 
40
componentes están fuertemente relacionados entre sí. Algunos ejemplos son la formación 
de galaxias, el cambio climático y el ensamblaje de automóviles.
3.Resolución de problemas complejos
La mayoría de modelos matemáticosque representan fenómenos naturales son 
de naturaleza compleja, es decir, requieren muchas instrucciones con respecto a la cantidad 
de datos por procesar, lo cual se traduce en tiempos de duración muy extensos. Con un solo 
CPU, la resolución de estos problemas es impráctico, ya que podrían tardar incluso décadas.
3.3.2. Medidas de desempeño
El diseño de algoritmos en general, y en particular paralelos, requiere de 
métodos analíticos que permitan optimizar los métodos y algoritmos empleados. Para esto, 
se abordan medidas de desempeño utilizadas frecuentemente en el análisis y diseño de 
algoritmos paralelos.
Sean TS y Tp los tiempos de ejecución de un programa secuencial y de un 
programa paralelo, respectivamente. La aceleración A se define como:
A=
TS
TP
(1)
La eficiencia es la medida de utilización de recursos de un programa paralelo 
con respecto al programa secuencial. Utilizando p procesadores para resolver un problema 
41
se puede calcular su eficiencia E de la siguiente manera:
E=
A
p
=
TS
pTP
(2)
Una observación importante acerca de (2) es que si la aceleración es un valor 
constante entonces la eficiencia se aproxima a 0 conforme se incrementa la cantidad de 
procesadores.
La escalabilidad de un sistema es, intuitivamente, la capacidad para incrementar 
su rendimiento cuando se incrementan los recursos disponibles. En el caso de un programa 
paralelo, este se dice escalable si (Dongarra y otros, 2002):
1)Su tiempo de duración es inversamente proporcional a la cantidad de procesadores 
utilizados.
2)Al incrementar el tamaño del problema y el número de procesadores 
proporcionalmente,6 el tiempo permanece igual.
Existen razones por las que no siempre se alcanza alta escalabilidad en 
aplicaciones paralelas. En primer lugar, puede existir una región de la aplicación que no 
puede ejecutarse en paralelo (no paralelizable). Si TS es el tiempo requerido para resolver un 
problema utilizando un procesador y r es la fracción paralelizable del programa, su 
aceleración, con p procesadores, está dada por la ley de Amdahl (Pacheco, 1997):
6 La razón de proporcionalidad se puede determinar a través de un análisis que involucra la complejidad del 
algoritmo y aspectos propios de la arquitectura computacional, como la latencia y el overhead.
42
A(p) =
TS
(1−r)TS+
rTS
p
=
1
(1−r) +
r
p
(3)
y su eficiencia:
E=
TS
p(1−r)TS+rTS
=
1
p(1−r) +r
(4)
Sin embargo, los procesos en un ambiente computacional paralelo usualmente 
requieren comunicación o sincronización (por ejemplo haciendo uso de buses del sistema o 
redes de datos), lo cual puede añadir latencia, incrementar el tiempo de ejecución global y 
afectar la aceleración. El tiempo invertido en dichas tareas de sincronización y 
comunicación es logarítmico en el mejor caso. Una ecuación que tome en cuenta este 
aspecto tiene la forma (Dongarra y otros, 2002):
E= 1
p(1−r)+r+clog(p)
= O( 1log(p)) (5)
donde c log(p) representa dicha latencia, la cual eventualmente domina la ecuación cuando p 
es suficientemente grande. En este caso la aceleración empieza a declinar, y 
consecuentemente la eficiencia.
Finalmente, un mal balanceo de cargas también influye negativamente en la 
aceleración, ya que una mala repartición de datos o tareas podría generar cuellos de botella 
donde muchos procesadores deben esperar que alguno finalice con una alta carga de trabajo.
Un aspecto relevante de la ley de Amdahl es que esta asume que el tiempo de 
43
procesamiento es independiente de la cantidad de procesadores, observación planteada 
inicialmente por Gustafson (Gustafson, 1988). En la práctica el tamaño de la tarea se debe 
ajustar a la cantidad de procesadores disponibles (es decir, se distribuye). Por esta razón 
Gustafson considera más apropiado asumir que el tiempo de ejecución se mantiene 
“constante” y que la cantidad de procesadores crece proporcionalmente al tamaño de la 
tarea. Este principio constituye un eje fundamental del análisis de escalabilidad de 
algoritmos paralelos.
3.3.3. Tipos de problemas
Un modelo computacional debe estar escrito en un lenguaje formal y debe 
contener una descripción clara de los componentes de un fenómeno, así como las relaciones 
entre estos. De esta forma, el modelo puede ser simulado por una computadora. Desde la 
perspectiva de cómputo paralelo, los problemas se pueden clasificar en alguna de las 
siguientes categorías, según el tipo de relaciones entre sus componentes.
1)Trivialmente paralelizables: Aquellos que pueden ser separados en dominios 
funcional y estructuralmente independientes, no existen relaciones de dependencia, y 
requieren, por lo tanto, pocas instrucciones de comunicación y sincronización.
2)Fuertemente acoplados: Los elementos de estos problemas están estrechamente 
ligados mediante dependencias funcionales o estructurales. Probablemente, la 
solución a estos problemas requerirá muchas instrucciones de sincronización y 
comunicación entre hilos o procesos.
3)Híbridos: Presentan características intermedias, con dependencias entre 
componentes y necesidad de sincronización y comunicación.
44
3.3.4. Arquitecturas Paralelas
Existen múltiples tipos de máquinas paralelas, cada una con modelos de 
programación asociados a su jerarquía de memoria y componentes físicos. Si bien la 
mayoría de máquinas modernas permite programar con herramientas casi independientes de 
la plataforma, es conveniente conocer la arquitectura del hardware paralelo con el fin de 
hacer un uso óptimo de los recursos disponibles. Flynn definió una taxonomía de máquinas 
de acuerdo con la cantidad de instrucciones físicas que puede manejar un CPU, por unidad 
de tiempo (Flynn, 1972):
• SISD (Single Instruction, Single Data): Máquinas que procesan una única instrucción 
y una sola variable por unidad de tiempo, como cualquier CPU's casero con un único 
núcleo.
• SIMD (Single Instruction, Multiple Data): Máquinas con múltiples núcleos que 
ejecutan copias de la misma instrucción, sobre diferentes flujos de datos o variables. 
Por ejemplo: GPU's,7 IBM Cell, entre otros.
• MISD (Multiple Instruction, Single Data): Arquitectura poco común, que puede 
aplicar diferentes flujos de instrucciones a los mismos datos. Una aplicación 
potencial es la criptografía (cifrado), donde se podría requerir la ejecución 
simultánea de diferentes algoritmos de decodificación.
• MIMD (Multiple Instruction, Multiple Data): Las máquinas en esta categoría pueden 
7 Graphical Processing Unit. Usualmente conocidos como “tarjetas de video” pero que en la actualidad 
cuentan con ambientes de desarrollo para propósito general. Su valor radica en la rapidez de su memoria y 
componentes internos, y la gran cantidad de núcleos de CPU SIMD de bajo consumo eléctrico, apto para 
aplicaciones numéricas que puedan correr con gran cantidad de hilos.
45
ejecutar diferentes secuencias de instrucciones sobre diferentes variables o datos. Se 
pueden construir a partir de componentes SIMD, como es el caso de muchos clusters 
de computadoras.
De acuerdo con su jerarquía de memoria, las máquinas paralelas MIMD pueden 
clasificarse en alguna de las siguientes categorías (Dongarra y otros, 2002):
a) Memoria compartida: Conocido típicamente como Multiprocesamiento Simétrico 
(SMP), cada procesador posee su propia memoria caché, y está interconectado junto con 
otros procesadores a la memoria principal mediante un medio físico (por ejemplo un bus). 
En esta organización, los procesadores tienen acceso a un espacio compartido de direcciones 
de memoria, y el hardware se encarga de mantener coherencia entre las memorias caché 
vigilando el bus de sistema e invalidando copias cacheadas de bloques que han sido escritos. 
Esta arquitectura se puede subdividir según el tiempo de acceso a memoria: UMA (Uniform 
Memory Access) y NUMA (Non-Uniform Memory Access) (Barney, 2011). Los programas 
para estas máquinas deben controlar operacionescomo lectura y escritura de modo que estas 
no produzcan inconsistencias. Un inconveniente del SMP es la cantidad limitada de 
procesadores y el alto costo en conectividad interna.
b) Memoria distribuida (no compartida): Resuelve algunos de los problemas de 
crecimiento de las máquinas SMP pues utiliza procesadores con memoria local 
interconectados mediante una red. El acceso a datos locales es rápido, sin embargo no es 
posible leer la memoria de otros nodos de la red directamente, por lo que se debe utilizar 
paso de mensajes. Esto consume ancho de banda y produce retrasos en el procesamiento, 
por lo que una buena práctica es enviar pocos mensajes largos.
46
c) Sistemas híbridos: Los dos enfoques anteriores pueden ser combinados de diferentes 
formas. Algunas máquinas de memoria distribuida (memoria-compartida distribuida, DSM) 
permiten que un procesador lea un dato remoto de forma directa. La latencia aumenta con 
la distancia entre las máquinas, y el mantenimiento de la coherencia de caché usualmente 
involucra redes sofisticadas. Para sistemas de paralelismo masivo, uno de los enfoques 
híbrido más populares son los clusters SMP, donde se cuenta con un sistema de memoria 
distribuida donde cada nodo es una máquina SMP. Recientemente se ha difundido el uso de 
los clusters GPGPU (General Purpose computation on Graphics Processing Units), donde cada 
nodo posee múltiples GPU's cada uno con muchos núcleos SIMD. Estos dos enfoques 
permiten alcanzar alta eficiencia dentro de un nodo, y permiten escalar el sistema a miles de 
procesadores. Sin embargo, la programación de estas máquinas debe afrontar los retos de 
sistemas de memoria distribuida y compartida.
3.3.5. Diseño de Programas Paralelos
Aún con hardware computacional muy potente, un algoritmo mal diseñado suele 
ser ineficiente. Según la naturaleza del problema que se debe resolver y la arquitectura 
elegida, existen diferentes etapas y enfoques para el diseño de algoritmos paralelos.
a)Identificación del paralelismo
Es importante identificar regiones del programa que pueden ser ejecutadas en 
paralelo. Según Dongarra y otros, el significado de un programa se define en términos de su 
implementación secuencial (Dongarra y otros, 2002). Bajo esta perspectiva, un programa 
47
paralelo debe producir los mismos resultados que su versión secuencial para que pueda 
considerarse correcto. El problema consiste en determinar cuándo dos (o más) cálculos de 
un programa secuencial pueden ser ejecutados en paralelo (de forma asíncrona) de modo 
que produzcan los mismos resultados que el programa secuencial.
Una solución simple es paralelizar regiones que no comparten datos. Sin 
embargo, áreas que comparten datos que únicamente serán leídos tampoco requieren de 
sincronización. Compartir la escritura de datos entre procesos puede ocasionar algunos 
problemas, como lecturas erróneas o sobreescritura (pérdida) de datos. En Dongarra y otros 
(2002) se presenta un conjunto de condiciones que capturan la esencia de este argumento: 
Dos cómputos C1 y C2 pueden ser ejecutados en paralelo sin sincronización si y sólo si no se 
cumple que:
• C1 escribe en una ubicación que es leída posteriormente por C2. Conocido como 
lectura tras escritura (RAW, read-after-write).
• C1 lee una ubicación que luego es escrita por C2. Conocido como escritura tras 
lectura (WAR, write-after-read).
• C1 escribe en una ubicación que luego es sobreescrita por C2. Conocido como 
escritura tras escritura (WAW, write-after-write).
b)Estrategias de paralelización
Se suelen aplicar dos estrategias básicas para dividir la solución a un problemas, 
de forma que este pueda ser resuelto en paralelo. Una estrategia se enfoca en tareas (task 
partitioning) y otra en datos (data partitioning) (Dongarra y otros, 2002).
48
Si se identifican las fases o tareas dentro del programa y las dependencias entre 
ellas, aquellas que no son interdependientes pueden ser procesadas en paralelo. De esta 
forma diferentes procesadores ejecutan diferentes funciones. Este enfoque se conoce como 
paralelización por tareas.
Por otra parte, el dominio del problema puede ser dividido en subdominios o 
regiones mapeadas a diferentes procesos o procesadores. Este acercamiento puede 
favorecer la escalabilidad del programa, ya que permite controlar directamente la relación 
entre el tamaño del problema y la cantidad de procesadores. Esta estrategia, llamada 
paralelización por datos, es usada ampliamente ya que mantiene más procesadores activos.
Adicionalmente, estas dos estrategias pueden ser combinadas de varias maneras. 
Por ejemplo se puede diseñar un pipeline, semejante a la operación de un CPU, con 
múltiples etapas dentro de cada tarea, y cada etapa mapeada con una sección diferente del 
conjunto de datos. Si las etapas tienen una duración similar, un pipeline de n etapas 
proveería una aceleración adicional de proporcional a n cuando se llene.
c)Modelos de programación paralela
Los modelos de programación paralela más conocidos son el modelo de 
memoria compartida y el modelo de memoria distribuida. Estos dos enfoques nacieron 
ligados a las arquitecturas de computadoras paralelas disponibles hace varias décadas. Sin 
embargo en la actualidad estos modelos constituyen estrategias de diseño de programas, y no 
dependen de la arquitectura computacional dónde se ejecute el programa. Otros modelos de 
49
programación paralela utilizados ampliamente son los hilos, paralelismo de datos, y enfoques 
híbridos (Dongarra y otros, 2002; Barney, 2011).
En el modelo de memoria compartida, las aplicaciones residen en una memoria 
global que puede ser leída por todos los procesadores, por lo que cada uno de ellos realiza 
operaciones (lectura y escritura de datos) en cualquier ubicación de forma independiente y 
concurrente. Es necesario asegurar la sincronización para preservar la integridad de los 
datos y estructuras de datos compartidas, por ejemplo recurriendo a semáforos que regulen 
el acceso a la memoria compartida. Si bien se facilita la labor de programar pues la 
comunicación no tiene que ser explícita, mantener los datos de una tarea de forma local para 
cada procesador es complicado.
El modelo de memoria distribuida recurre al paso de mensajes para acceder 
datos que asociados con procesadores o procesos específicos, y comúnmente se asocia con 
arquitecturas de memoria distribuida no compartida. Las primitivas para enviar y recibir 
toman el lugar de la sincronización. Por ejemplo MPI (Message Passing Interface) es una 
especificación para un API de paso de mensajes. Una implementación popular de MPI es 
MPICH2, la cual implementa rutinas, bibliotecas y compiladores para C, C++ y Fortran, y es 
ampliamente utilizada en clusters de computadoras.
El modelo de hilos involucra un proceso con múltiples rutas de ejecución 
concurrentes. Cada hilo tiene datos locales, pero además comparte todos los recursos del 
proceso principal, así como la totalidad de su espacio de direcciones. Es necesario que 
exista sincronización, para asegurar que sólo un hilo modifique una dirección global en un 
tiempo dado. Los hilos pueden crearse y destruirse, pero el proceso principal permanece 
50
presente para proveer los recursos compartidos necesarios hasta que finalice la aplicación. 
El modelo de hilos se suele asociar con arquitecturas y sistemas operativos de memoria 
compartida. Dos implementaciones comúnmente utilizadas son OpenMP y POSIX Threads. 
OpenMP es un API para programación paralela en C y C++ disponible para múltiples 
arquitecturas de memoria compartida, puede utilizar código secuencial y utiliza directivas de 
precompilador para indicar regiones con ejecución paralela y estrategias de paralelización. 
Por otra parte, POSIX Threads (PThreads), especificado por el estándar IEEE POSIX 
1003.1c, está basado en bibliotecas e involucra paralelismo multi-hilo explícito.El modelo de programación conocido como paralelismo de datos plantea la 
aplicación de un conjunto de operaciones sobre datos organizados en una estructura común, 
como un arreglo o un cubo. Las operaciones se realizan simultáneamente pero son aplicadas 
a diferentes secciones de la misma estructura de datos, por lo que se realiza la misma tarea 
pero cada instancia manipula datos diferentes. En arquitecturas de memoria compartida 
centralizada, es posible que todas las tareas puedan acceder a la estructura de datos mediante 
la memoria global, mientras que en máquinas de memoria compartida distribuida o memoria 
distribuida no compartida, la estructura de datos debe ser dividida y copiada a la memoria 
local de cada tarea o procesador, por ejemplo mediante paso de mensajes.
Estos modelos no son mutuamente excluyentes; usualmente se utilizan modelos 
híbridos que combinan dos o más de los enfoques mencionados. Por ejemplo, una 
aplicación puede implementar paso de mensajes mediante MPI, donde cada proceso posea 
múltiples hilos de OpenMP. Este modelo se ajusta muy fácilmente a arquitecturas populares 
como los clusters SMP.
51
Existen dos enfoques adicionales de alto nivel, que pueden implementarse 
mediante cualquier combinación de las estrategias de programación descritas. Single 
Program Multiple Data (SPMD – un programa, múltiples datos), plantea la utilización de un 
único programa que es ejecutado por todos los procesos simultáneamente. Un programa 
SPMD debe tener la lógica necesaria, como saltos y condicionales, para ejecutar sólo las 
secciones necesarias. Además, cada proceso puede leer o manipular diferentes datos. Por 
otra parte, Multiple Program Multiple Data (MPMD – múltiples programas, múltiples datos) 
plantea el diseño de aplicaciones paralelas con diferentes ejecutables o programas, donde 
cada proceso podría ejecutar un programa diferente y manipular datos diferentes de forma 
simultánea. Las aplicaciones SPMD son comúnmente utilizadas en clusters de memoria 
distribuida, implementadas mediante paralelismo de datos y paso de mensajes.
Si bien estos modelos constituyen abstracciones del hardware y jerarquías de 
memoria, es posible implementarlos en diversas arquitecturas paralelas. Se podría utilizar, 
por ejemplo, paso de mensajes en una máquina multiprocesador de memoria compartida, 
donde el paso de mensajes se lleva a cabo entre los procesadores mismos (a través de los 
buses del sistema) y no mediante una red. Ya que la latencia es mucho menor en un bus 
interno que en una red, esta estrategia tiene rendimiento comparable con un modelo de 
memoria compartida.
En la siguiente sección se presentan algoritmos paralelos para recorridos en 
grafos y árboles, estructuras necesarias para representar una memoria de casos.
3.4. Algoritmos paralelos de búsqueda en árboles y grafos
52
Una memoria de casos puede ser representada computacionalmente mediante 
estructuras de datos como grafos o árboles. Un grafo dirigido acíclico permite representar 
los principios fundamentales de la memoria de casos formalizada en la sección 3.2.3. Una 
modificación de la definición de árbol, donde un nodo puede tener múltiples padres o 
predecesores, es equivalente a un grafo dirigido acíclico. Del mismo modo, mediante un 
árbol n-ario se pueden representar explícitamente todas las rutas existentes en un grafo desde 
un nodo inicial hasta cada una de las hojas.
En esta sección se discuten formulaciones paralelas para familias típicas de 
algoritmos de búsqueda en árboles y grafos. En la literatura, por lo general, se entiende 
procesadores como entidades de procesamiento abstractas. No necesariamente estos 
procesadores son CPU's físicos; podrían ser procesos, hilos o agentes computacionales. El 
sistema implementado utiliza un mecanismo complejo de recuperación de casos, donde la 
búsqueda en árboles es un recurso del cual se dispone para encontrar un caso relevante en la 
estructura de datos seleccionada. La búsqueda, por lo tanto, no es equivalente a la 
recuperación.
3.4.1. Búsqueda en profundidad
Se conoce como profundidad primero o búsqueda en profundidad la clase de 
algoritmos en los que se recorre los sucesores de un nodo antes que sus hermanos (los 
sucesores de su predecesor). Grama y Kumar (1995) mencionan que las técnicas de 
búsqueda en profundidad son frecuentemente utilizadas para resolver problemas de 
optimización discreta que pueden caracterizarse como un problema de búsqueda en un grafo, 
53
con un nodo inicial y uno o más nodos meta.8 La búsqueda en profundidad inicia 
expandiendo el nodo inicial, generando sus sucesores y agregándolos a una pila de 
procesamiento. En pasos subsecuentes, se extrae el primer nodo en la pila y este es 
expandido (y sus sucesores agregados a la pila). Si el nodo expandido no posee sucesores (y 
por ende soluciones) se puede realizar retroceso (backtracking), y expandir el siguiente nodo 
en la pila. La búsqueda finaliza cuando se encuentra la solución deseada, cuando se 
determina que no existe solución, o cuando la pila se vacíe (se ha terminado de procesar el 
grafo). Una ventaja de esta búsqueda es que el requerimiento de almacenamiento es 
proporcional a la profundidad del recorrido. En un algoritmo paralelo con p procesos, el 
requerimiento de espacio se tendría que multiplicar por p.
En un ambiente paralelo, el árbol generado por este recorrido puede ser asignado 
de forma estática a tantos procesadores como nodos existan, sin embargo estos árboles 
suelen ser irregulares por lo que es necesario balancear la carga de datos (la cantidad de 
nodos por procesador). Un elemento importante en la formulación paralela de un algoritmo 
de búsqueda en profundidad es la utilización de técnicas dinámicas de balanceo de cargas 
que minimicen la comunicación y el tiempo ocioso de los procesadores. En el proceso de 
distribución del dominio se pueden distinguir las siguientes fases:
– Partición de tareas: las dos técnicas más frecuentes son stack splitting (partición por pila) 
y node splitting (partición por nodos). La pila de un procesador es su conjunto de datos, 
o en este caso nodos en los que debe buscar. Si se utiliza partición por pila, la pila de 
8 Un problema de optimización discreta puede ser expresado como una tupla (S, f), donde S es un conjunto a 
lo sumo de cardinalidad infinita contable que contiene todas las soluciones que satisfacen un conjunto de 
requisitos. La función f mapea cada elemento de S con un número real. El objetivo consiste en encontrar 
una solución xopt tal que f(xopt) < f(x) ∀ x ∈ S (Grama y otros, 2003).
54
trabajo de un nodo se divide en dos, y una de estas pilas se transfiere a otro nodo (que ha 
solicitado carga de trabajo). Utilizando partición por nodos, cada uno de los sucesores 
generados por un nodo es transferido individualmente, como una subtarea, a un 
procesador ocioso.
– Distribución de subtareas: involucra dos aspectos clave: la estrategia de generación y la 
estrategia de transferencia. Las subtareas se pueden generar cuando un procesador 
ocioso solicita trabajo (generación de subtareas iniciada por receptor), o bien por 
“iniciativa” de un procesador (generación de subtareas iniciada por emisor). La 
distribución de tareas entre procesadores utiliza los mismos elementos: puede ser bajo 
demanda (transferencia iniciada por receptor) o sin demanda (transferencia iniciada por 
emisor).
A continuación se presentan algunos ejemplos de algoritmos paralelos de 
búsqueda en profundidad.
1)Búsqueda en profundidad primero, división por pila y generación de subtareas 
y transferencia iniciada por receptor
El algoritmo 1 presenta la forma más básica de la búsqueda secuencial en 
profundidad (Depth-First Search, DFS) con retroceso simple (Grama y Kumar, 1995).
1. programa búsqueda_profundidad
2. seleccionar nodo inicial y agregar a la pila
3. repetir
4. inicio