Paralelizacion

CAPÍTULO III
PARALELIZACIÓN


3.1 Introducción

En la mayoría de las tareas de optimización en aplicaciones del mundo real se presentan varias limitaciones que por lo general no permiten la utilización de métodos exactos. La complejidad de estos problemas, que a menudo son de tipo NP-duros se enfrentan a limitados recursos para resolverlos como por ejemplo el tiempo, la memoria, etc.En estos casos, las metaheurísticas proporcionan una solución factible en tiempo razonable, ya que su uso permite reducir significativamente el tiempo del proceso de búsqueda y la dimensión de muchas tareas. Por lo tanto, el paralelismo es un enfoque empleado no sólo para reducir el consumo de tiempo, sino también se define como objetivo particular mejorar la calidad de las soluciones debido aque los algoritmos paralelos se ejecutan en un modelo de búsqueda diferente con respecto al algoritmo secuencial.

3.2 Definición de paralelismo
Consiste en ejecutar varias tareas en diferentes procesadores locales, ya sea para acceso a datos o para cómputo intensivo.
Existen dos tipos de paralelismo, el paralelismo explícito y el paralelismo implícito. El paralelismo explícito,consiste en que el programa indica explícitamente como cooperan los procesadores para resolver un problema específico; el paralelismo implícito, se usan los programas actuales y el compilador inserta las instrucciones necesarias para ejecutar el programa en forma paralela.
Las principales razones por las cuáles es importante paralelizar son para resolver problemas grandes rápidamente, para eladecuado aprovechamiento de los procesadores y del hardware, cambios y actualizaciones en los programas utilizados.

Para llevar a cabo la paralelización, es necesario contar con las herramientas necesarias, ya que, dependiendo de la que se utilice es la forma en la que será segmentado el código para que sea ejecutado en varios procesadores, es así como surge el término de granularidad.Granularidad se lleva a cabo si el código puede ser particionado en numerosos procesos independientes, ya que se puede asignar las diferentes tareas a distintos procesadores. La granularidad en paralelismo se puede clasificar en paralelismo de grano fino y paralelismo de grano grueso.
El paralelismo de grano fino es cuando un ciclo se divide en varios ciclos a nivel de sentencia, donde cada una queejecutan en paralelo. Es común encontrar ciclos cuyas iteraciones son independientes entre sí. Se pueden dividir el número de iteraciones de dichos ciclos entre los procesadores. Si la cantidad de trabajo realizada en cada iteración es casi la misma, con solo dividir las iteraciones de manera uniforme a través de los procesadores se logrará el máximo paralelismo. Lo expresado en [Aho08] lo conocecomo paralelismo de datos.
El paralelismo de grano grueso es a nivel de subrutinas o segmentos de código, donde dichos segmentos son escasos y de cómputo más intensivo que las de grano fino. Se le llama también paralelismo de tareas, por lo que es difícil mantener todos los procesadores ocupados todo el tiempo.

3.3 Medir desempeño en paralelo
Los aspectos importantes de la evaluación deun problema en específico, las fuentes de prueba, medir el rendimiento de algoritmos en manera significativa, el análisis y la presentación clara de los resultados representan a menudo gran dificultad para elaborarlos correctamente. Existen diferentes métricas para medir el rendimiento de algoritmos paralelos. Como por ejemplo la aceleración (speedup) y la eficiencia.

3.3.1 Speeup

En[Alb05] se explica que la medida más importante de un algoritmo paralelo es el aumento de velocidad (speedup). Este indicador compara dos veces: la proporción entre los tiempos secuenciales y paralelos. En un sistema cuando un algoritmo se ejecuta de forma secuencial, el procesador ejecuta instrucciones, normalmente sin incluir el tiempo para el problema de los datos de entrada, salida de los...