Debe introducir al menos 3 caracteres en el buscador.
Inicio / Wikis / Tutoriales / El manual para el clustering con openMosix - Paralelismo (I)

El manual para el clustering con openMosix - Paralelismo (I)

 ***** (4 opiniones)
GNU Free Documentation License Tutorial de miKeL a.k.a.mc2 y Kris Buytaert - 27 de Febrero de 2006
Temas Relacionados: PC
3. Paralelismo (I)

En esta sección se tratará el palalelismo a nivel teórico. Como se explica en la sección de introducción, paralelizar los problemas en problemas más sencillos y distribuirlos entre varios procesadores no siempre es una solución conveniente y dependerá en gran medida de la naturaleza de los problemas que se quieran tratar.

Se hablará de programación paralela y los problemas que pueden surgir cuando se trata de utilizar este paradigma. Para ello debe considerarse el sistema sobre el que se programa y se lanzan los programas paralelos: ya sean multiprocesadores o, como será el caso, multicomputadores. Al explicar estos límites que impone la propia arquitectura tendrá que hablarse forzosamente de la ley de Ahmdal así como de otros problemas relativos a la ordenación de instrucciones debido a dependencias.

En general en esta sección se hablará acerca de todos los conceptos que interesan a la hora de programar aplicaciones y hacerlo utilizando de una manera u otra el paralelismo. Se darán diversos ejemplos de programación con openMosix y explicaciones con PVM o MPI y se profundizará en conceptos como la granularidad del paralelismo o el problema de la transparencia en lo que se refiere a la programación.

Parámetros de rendimiento en computación paralela

Velocidad de ejecución rate (R). Mide salidas (outputs) por unidad de tiempo. Según la naturaleza de las salidas, tendremos:

  • $ R= \frac{instrucciones}{segundo}$ que se miden con MIPS (instrucciones x $ 10^6$ por segundo).
  • $ R= \frac{op's}{segundo}$ que se miden con MOPS (operaciones x $ 10^6$ por segundo).
  • $ R= \frac{op's flotantes}{segundo}$ que se miden con MFLOPS (op's coma flotante x $ 10^6$ por segundo).



Acceleración (speedup $ S_p$). Ratio entre el tiempo de una ejecución serie y una paralela.

$\displaystyle \displaystyle S_p=\frac{t_1}{t_p}$ (2.1)


 

$ t_1$: tiempo requerido para realizar la computación en $ 1$ procesador,
$ t_p$: tiempo requerido para realizar la computación en $ p$ procesadores.
Normalmente se da la relación $ 1 \leq S_p \leq p$, debido al tiempo que se pierde en la inicialización, sincronización, comunicación y otros factores de overhead que se requieren en la computación paralela.



Eficiencia (E). Ratio entre la acceleración de una ejecución paralela y el número de procesadores.

$\displaystyle \displaystyle E=\frac{S_p}{p}=\frac{t_1}{p\ t_p}$ (2.2)


 



Redundancia (R). Ratio entre el número de operaciones realizadas utilizando $ p$ procesadores en una ejecuciópn paralela y su correspondiente ejecución serie en 1 procesador.

$\displaystyle \displaystyle R=\frac{O_p}{O_1}$ (2.3)


 



Utilización (U). Ratio entre $ O_p$ y el número de operaciones que podrian realizarse utilizando $ p$ procesadores en $ t_p$ unidades de tiempo.

$\displaystyle \displaystyle U=\frac{O_p}{p\ t_p}$ (2.4)


 

Modelos matemáticos

I. PRINCIPIO ARMÓNICO PONDERADO



Sea $ t_n$ el tiempo requerido en computar $ n$ operaciones de $ k$ tipos diferentes, donde cada tipo de operación consiste en $ n_i$ operaciones simples las cuales requieren $ t_i$ segundos cada una para su ejecución. Luego:

$ \displaystyle t_n=\sum_1^k n_i t_i $ y $ n=\sum_1^k n_i$. Por definición sabemos que $ R_n=\frac{n}{t_n}=\frac{n}{\sum_1^k n_i t_i}$ MFlops.



Si definimos:

$ f_i=\frac{n_i}{n}$ como fracción de operaciones ejecutadas a una velocidad $ R_i$,
$ t_i=\frac{1}{R_i}$ velocidad de ejecución en computar 1 operación,

luego

$\displaystyle \displaystyle R_n=\frac{1}{\sum_1^k f_i t_i}=\frac{1}{\sum_1^k\frac{f_i}{R_i}}$ (2.5)


 

donde $ \sum_i f_i =1, R_i=\frac{1}{t_i}$.



Lo importante de esta ecuación es que muestra que una sola operación donde su ejecución no sea equiparable con el resto, en cuanto al tiempo de ejecución, tiene una gran influencia en el rendimiento global del sistema.




II. LEY DE AMDAHL

$\displaystyle \displaystyle R(f)=\frac{1}{\frac{f}{R_H}+ \frac{1-f}{R_L}}$ (2.6)


 

Para comprender esta ley sería conveniente recuperar la analogía del problema que se planteaba en el primer tema, acerca de la persona que debía colocar los libros en dos partes. En el caso de la ordenación de la biblioteca se llegaba a la conclusión de que era estúpido contratar a 200 personas para que organizasen una biblioteca de 200 ejemplares, por la falta de eficiencia en las operaciones.

El speedup -o mejora de rendimiento - idealmente aumenta linealmente con el número de unidades de procesamiento que posea el sistema. Esto es en un principio cierto, pero estamos contando en todo momento con un programa modelo ideal, sin tener en cuenta la naturaleza de dicho programa. En el caso de programas concretos hemos de contar con la naturaleza del programa, qué pretende solucionar y la manera en la que lo soluciona. Eso permitirá poder dar con la medida real del speedup.

En cualquier programa paralelizado existen dos tipos de código: el código paralelizado y el código secuencial. Como es sabido existen ciertas secciones de código que ya sea por dependencias, por acceso a recursos únicos o por requerimientos del problema no pueden ser paralelizadas. Estas secciones conforman el código secuencial, que debe ser ejecutado por un solo elemento procesador. Es pues lógico afirmar que la mejora de rendimiento de un programa dependerá completamente de:

  1. El tiempo en el que se ejecuta el código serie $ R_L$.
  2. El tiempo en el que se ejecuta el código paralelizable $ R_H$.
  3. El número $ f$ de operaciones ejecutadas de forma paralela (en tiempo $ R_H$).



Esta es la llamada ley de Amdahl y fue descrita por Gene Amdahl en 1967. Las implicaciones que trae esta ecuación son, a pesar de que no tenga en cuenta las características de cada sistema en concreto:

  • el rendimiento no depende completamente del número de procesadores que posea el sistema: en la mayoría de los casos dependerá del número de procesadores máximo que se aprovecharán simultáneamente para ejecutar un programa.
  • cuanto mejor paralelizado esté un programa más susceptible será de aumentar su speedup y por tanto explotar el rendimiento del sistema paralelo que lo ejecute.

Supongamos ahora que tenemos un programa que inicialmente no hemos paralelizado, cuyos tiempos de ejecución son 12% y 88%, en serie y en paralelo respectivamente.

Figura: Paralelismo. Ejemplo de incremento de speedup obtenido con la ley de Amdahl
Image amdahl_speedup

Como se puede ver en la figura, la parte no paralelizable del código impide que se pueda escalar de forma lineal, llegará un momento que añadir nuevos procesadores no añadirá una ventaja real al sistema, porque todo lo que estará en ejecución será código secuencial. Por lo tanto para maximizar el aprovechamiento de los sistemas paralelos debe tenerse mucho cuidado con la forma de paralelizar las aplicaciones: cuanto más código secuencial tengan, más problemas de escalabilidad.



La ley de Amdahl es un caso particular del Principio Armónico Ponderado, anteriormente descrito. Si recuperamos:

$ \displaystyle R_n=\frac{1}{\sum_1^k \frac{f_i}{R_i}}$ y hacemos $ K=2$ queda $ \displaystyle R_2=\frac{1}{\sum_1^2 \frac{f_i}{R_i}}$



si se igualan

$ f_1=f$: fracción paralela
$ f_2=(1-f)$: fracción serie

da la forma de la Ec.([*]) $ \rightarrow$ $ \displaystyle R(f)=\frac{1}{\frac{f}{R_H}+ \frac{1-f}{R_L}}$ .




III. LíMITES DE LA COMPUTACIÓN PARALELA



Un programa paralelo requiere sincronizar las tareas de que se compone. Estas tareas se distribuyen entre los diferentes procesadores del sistema paralelo. La suma de los tiempo de ejecución de estas tareas en un sistema paralelo es más grande que la suma de los tiempos de ejecución en un solo proesador. Esto es debido a diferentes tiempos adicionales de procesamiento (overhead).

Sean:

$ t_s$ : tiempo de sincronización
$ t$ : granularidad de la tarea. valor medio del tiempo de ejecución de las diferentes tareas.
$ t_0$ : overhead de la tarea debido a su ejecución en paralelo.
$ N$ : número de tareas entre puntos de sincronización.
$ p$ : número de procesadores.

El tiempo requerido para ejecutar $ N$ tareas, cadauna con un tiempo de ejecución $ t$ en un solo procesador viene dado por

$ \displaystyle t_1=N\ t$



En un entorno paralelo cada tarea requiere $ t+t_0$ unidades de tiempo para su ejecución. El tiempo requerido para ejecutar $ N$ tareas en $ p$ procesadores será pues:

$ \displaystyle t_{N,p}=t_s+ \left\lceil \frac{N}{p}\right\rceil (t+t_0)$

y recuperando el speedup, esta vez siendo el cómputo las $ N$ tareas

$\displaystyle \displaystyle S_{N,p}=\frac{T_{1}}{T_{N,p}}=\frac{N\ t}{t_s + \lceil \frac{N}{P}\rceil (t+t_{0})}$ (2.7)


 

y la eficiencia ahora quedaria determinada como

$\displaystyle \displaystyle E_{N,p}=\frac{S_{N,p}}{p}$ (2.8)


 

Los límites de la computación paralela estan reflejados en el cuadro [*].


Tabla: Paralelismo. Límites de la computación paralela
Parámetro $ p \rightarrow \infty$ , $ N$ fijo $ N \rightarrow \infty$ , $ p$ fijo
$ \displaystyle S_{N,p}$ $ \displaystyle \frac{N}{1+\frac{t_s+t_0}{t}}$ $ \displaystyle \frac{p}{1+\frac{t_0}{t}}$
$ \displaystyle E_{N,p}$ 0 $ \displaystyle \frac{1}{1+\frac{t_0}{t}}$
Tabla de contenidos
Autor y licencia de 'El manual para el clustering con openMosix - Paralelismo (I)'
miKeL a.k.a.mc2 y Kris Buytaert Extraído de: http://es.tldp.org/Manuales-LuCAS/doc-manual-openMosix-1.0/doc-manual-openMosix_html-1.0/ GNU Free Documentation License
Licencia GNU Free Documentation License: http://www.es.gnu.org/licencias/fdles.html
Este contenido ha sido recopilado por el equipo de Wikilearning. Todo el contenido recopilado se ha obtenido respetando y comunicando en nuestro site la licencia de cada fuente.
Wikilearning tiene permiso expreso por escrito de los autores para publicar los contenidos que ha extraído de otras webs, incluyendo su uso comercial.

Wikis relacionados con 'El manual para el clustering con openMosix - Paralelismo (I)'

Hierbas Mágicas de la A a la Z. Parte I - De la A a la E
Este es el Diccionario de Plantas Mágicas elaborado por nosotr@s. Esta basado en nuestra propia... Más »
Josep Palau i Fabre, la voz subversiva del alquimista
Josep Palau i Fabre, poeta barcelonés nacido en 1917, es uno de los máximos representantes... Más »
Creación de componentes VCL (I)
En los últimos años, el desarrollo basado en componentes se ha convertido en una de... Más »
Manual Aprendiendo a aprender Linux
El principal objetivo de este documento es lograr que el lector adquiera la capacidad de... Más »
Reflexiones en torno al Llibre d'amic i amat de Ramón Llull
Reflexión panorámica de los famosos aforismos en El Libro de amigo y de Amante, del... Más »
¿Estás seguro de que deseas eliminar este capítulo?