ORGANIZACIÓN DE COMPUTADORAS - Aicitel's Weblog · COMPUTADORAS DRA. LETICIA FLORES PULIDO ....

ORGANIZACIÓN DE COMPUTADORAS

DRA. LETICIA FLORES PULIDO

FACTOR DE VELOCIDAD

¤  Sabemos que p se identifica como el número de procesadores o procesos

¤  Multiprocesador será entonces el término que se puede utilizar para referirse a cualquier sistema paralelo de computadora que posea más de un procesador.

¤  La mayoría de las ocasiones el punto principal de paralelizar un proceso es el preguntarse ¿cuál será el factor de velocidad sobre el cual se obtendrá una mejora o beneficio?

Dra. Leticia Flores Pulido / DCSCE / Primavera 2013

2

FACTOR DE VELOCIDAD

¤  Considerando lo anterior se puede considerar inicialmente tomar una solución normal algorítmica

¤  Después se puede probar en un sistema con un solo procesador y después comparar dicha solución contra la solución del sistema de multiprocesamiento


3

S (p) =

Tiempo de ejecución utilizado por un sistema con procesador simple (con el mejor algoritmo secuencial)

Tiempo de ejecución utilizado por un sistema multiprocesador con p procesadores

FACTOR DE VELOCIDAD

¤  Utilizaremos

¤  ts = tiempo de ejecución del mejor algoritmo secuencial ejecutado en un sistema con un procesador simple

¤  tp = tiempo de ejecución para resolver el mismo problema en un mutiprocesador

¤  Además del procesador, también debemos tomar en cuenta la entrada de datos, pero por el momento solo haremos uso del factor p


4

FACTOR DE VELOCIDAD

¤  S(p) proporciona el aumento en velocidad que se utiliza en el multiprocesador

¤  En un análisis teórico, el factor de velocidad puede ser incluso expresado en términos computacionales:


5

S(p)=

Número de pasos computacionales utilizados en un procesador

Número de pasos computacionales con p procesadores

FACTOR DE VELOCIDAD

¤  Para cálculos secuenciales, es común comparar diferentes algoritmos utilizando análisis de complejidad

¤  El análisis de complejidad puede extenderse en los algoritmos paralelos y aplicarse al factor de velocidad.

¤  Pero podemos observar que el solo analizar los pasos computacionales no es suficiente

¤  Esto se debe a que la naturaleza de las aplicaciones paralelas puede requerir múltiples comunicaciones entre sí y eso puede tener mas influencia en costo computacional que tan solo los pasos del código


6

Factor de Velocidad

¤  El máximo en velocidad posible, es usualmente p con p procesadores (velocidad lineal)

¤  La velocidad de p puede ser alcanzada cuando el calculo puede ser dividido en procesos de igual duración por medio de un mapeo a memoria dentro del mismo procesador siempre que no haya un vuelco de memoria en la solución paralela:


7

Eficiencia

¤  La eficiencia es algo útil que puede conocerse para casos de grandes procesamientos y se define como:


8

E=

Tiempo de Ejecución utilizado por un procesador

Tiempo de Ejecución utilizado en un multiprocesador X número de procesadores

Eficiencia

¤  Lo cual nos guía a:

¤  Cuando E está dado como un porcentaje.

¤  Ejemplo: ¤  Si E = 50% los procesadores están utilizándose la mitad del

tiempo sobre el cálculo real en promedio

¤  Si E= 100% se da cuando todos los procesadores están utilizándose todo el tiempo durante los cálculos


9

¿Cuál es la máxima velocidad?

¤  Existen algunos factores que implican una sobrecarga en las versiones paralelas y que por lo tanto limitan la velocidad de las mismas: ¤  LOS PERIODOS DE TIEMPO CUANDO NO TODOS LOS

PROCESADORES ESTAN UTILIZANDOSE Y ESTAN EN ESTADO OCIOSO

¤  CÁLCULOS EXTRA EN LAS VERSIONES PARALELAS QUE NO APARECEN NORMALMENTE EN LAS VERSIONES SECUENCIALES (CÁLCULO O INICIALIZACIÓN DE CONSTANTES)

¤  TIEMPOS DE COMUNICACIÓN ENTRE PROCESOS


10


¤  Es razonable tomar en cuenta que algunos cálculos no son posible llevarlos a cabo de manera concurrente o dividirlos paralelamente

¤  En esos casos debemos considerar que la programación debe ser secuencial inevitablemente

¤  EJEMPLO: ¤  Configuración inicial à un procesador

¤  Espera à los demás procesadores


11


¤  Supongamos que existen entonces algunas partes que son realizadas solo por un procesador

¤  Lo ideal sería que los demás procesadores trabajaran tal vez en la misma tarea de manera concurrente


12


¤  Si existe una fracción de cálculo que no es posible dividirla en tareas concurrentes la llamamos f y no se incurre en sobrecargas, entonces el tiempo de ejecución del cálculo con p procesadores está dado por:


13



14


¤  Entonces la parte serial se puede distribuir a través del proceso de cálculo

¤  El factor de velocidad estaría dado entonces por:


15

Ley de Amdahl

¤  Esta ecuación es conocida como la Ley de Amdahl en 1976


16

Ley de Amdahl


17

¤  El número de procesadores contra el factor f se muestra a continuación

Ley de Amdahl

¤  La fracción de cálculo que requiere ser ejecutada por procesos concurrentes tiene que ser una parte substancial del cálculo total si es que se desea un aumento en velocidad


18

Ley de Amdahl

¤  Aun así, si un número infinito de procesadores está disponible, la máxima velocidad está limitada a 1/f, es decir:

¤  Por ejemplo, con solamente el 5% de los cálculos que son seriales, es posible alcanzar un máximo de velocidad de 20 independientemente del número de procesadores


19

Ley de Amdahl

¤  Amdahl utiliza el argumento de promover los sistemas de procesadores simples también en los 60’s

¤  Por supuesto debemos tener en cuenta que aun un factor de velocidad de 20 puede ser impresionante.

¤  El mejoramiento o aumento en esta magnitud es posible solo en ciertas circunstancias


20

Ley de Amdahl

¤  En una implementación paralela, las soluciones pueden encontrarse de manera casi inmediata y de manera simultánea

¤  En una versión secuencial, suponga que x sub espacios son buscados y que la solución es encontrada en un tiempo Δt dentro del siguiente sub espacio de búsqueda

¤  El número de sub espacios previos es indeterminado y dependerá del problema


21

Ley de Amdahl

¤  En la versión paralela la solución se encuentra inmediatamente en un tiempo Δt , como se ilustra a continuación:

¤  La velocidad está dada por:


22

Ley de Amdahl


23

Ley de Amdahl


24

Ley de Amdahl

¤  El peor caso de la búsqueda secuencial es cuando la solución se encuentra dentro del último sub espacio de búsqueda, y la versión paralela ofrece grandes beneficios frente a esto:


25

Ley de Amdahl

¤  La ventaja mas deseable en programación paralela puede ser que la solución sea encontrada en el primer sub espacio de búsqueda de la búsqueda secuencial:

¤  La velocidad real dependerá de el sub espacio que contenga la solución y de que pudiera ser extremadamente grande


26

ORGANIZACIÓN DE COMPUTADORAS - Aicitel's Weblog · COMPUTADORAS DRA. LETICIA FLORES PULIDO ....

Documents

Transcript of ORGANIZACIÓN DE COMPUTADORAS - Aicitel's Weblog · COMPUTADORAS DRA. LETICIA FLORES PULIDO ....