ANALISIS DE ALGORITMOS

FACULTAD DE INGENIERIA INFORMATICA

CLAUDIA LORENA DIAZNOVIEMBRE 2013

ALGORITMO SECUENCIALALGORITMO SECUENCIAL

La estructura secuencial es aquella en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso.

Ejemplo

En este otro ejemplo encontraremos el área de un triangulo solicitando al usuario la base y la altura del mismo,

INICIO REAL= B,H,AR; Escriba("digite base"); Lea(B); Escriba("digite altura"); Lea(H); AR= b*h/2; Escriba("el área del triangulo es=«AR»); FINAL

Después de ejecutada una determinada acción, la siguiente está indicada sin ambigüedades. Si después de ejecutada una acción existen dos o más que podrían ejecutarse y no existe un criterio para seleccionar la que corresponde, no es un algoritmo secuencial.

ALGORITMO SECUENCIALALGORITMO SECUENCIAL

La secuencia de acciones debe finalizar en algún momento, cuando el problema esté resuelto. Una secuencia de acciones que podría llegar a ejecutarse indefinidamente, no es un algoritmo secuencial.

Tienen un Único flujo de ejecución.

Por sí solos, resuelven problemas muy simples y cortos.

Son usados en conjunción en otros algoritmos con procesos selectivos e iterativos.

ALGORITMO PARALELOALGORITMO PARALELO

Es un algoritmo que puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento, para finalmente unir todas las partes y obtener el resultado correcto.

Algunos algoritmos son fácilmente divisibles en partes; como por ejemplo, un algoritmo que calcule todos los números primos entre 1 y 100, donde se podría dividir los números originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los números originales; al final, uniríamos todos los resultados y tendríamos la solución final del algoritmo.

Los algoritmos paralelos son importantes porque es más rápido tratar grandes tareas de computación mediante la paralelización que mediante técnicas secuenciales. Esta es la forma en que se trabaja en el desarrollo de los procesadores modernos, ya que es más difícil incrementar la capacidad de procesamiento con un único procesador que aumentar su capacidad de cómputo mediante la inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de instrucciones dentro del procesador.

Hay que ser cauto con la excesiva paralelización de los algoritmos ya que cada algoritmo paralelo tiene una parte secuencial y debido a esto, los algoritmos paralelos puedes llegar a un punto de saturación. Por todo esto, a partir de cierto nivel de paralelismo, añadir más unidades de procesamiento puede sólo incrementar el coste y la disipación de calor.

COSTE O COMPLEIDAD DE ALGORITMOS COSTE O COMPLEIDAD DE ALGORITMOS PARALELOSPARALELOS

El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio (memoria) y tiempo (ciclos de procesador) que requiera. T(n) = n(n − 1)/2

T(n) = t 1 x t 2 x N

Los algoritmos paralelos también necesitan optimizar la comunicación entre diferentes unidades de procesamiento. Esto se consigue mediante la aplicación de dos paradigmas de programación y diseño de procesadores distintos: memoria compartida o paso de mensajes.

Memoria compart idaEn informática, la memoria compartida es aquel tipo de memoria que puede ser

accedida por múltiples programas, ya sea para comunicarse entre ellos o para evitar copias redundantes. La memoria compartida es un modo eficaz de pasar datos entre aplicaciones. Dependiendo del contexto, los programas pueden ejecutarse en un mismo procesador o en procesadores separados.

El intercambio de datos entre dos programas o aplicaciones ejecutándose al mismo tiempo, crea un área en la memoria RAM a la que el otro pueda acceder.

Dado que ambos procesos pueden acceder al área de memoria compartida como memoria de trabajo regular, esta es una forma de comunicación veloz.De aquí que hacemos referencia al múltiple paralelismo, que puede saturar la memoria ocupándola completamente y recalentándola.

Interfaz de Paso de MensajesMPI (Interfaz de Paso de Mensajes) es un estándar que define la sintaxis y la semántica de las funciones contenidas en una biblioteca de paso de mensajes diseñada para ser usada en programas que exploten la existencia de múltiples procesadores.El paso de mensajes es una técnica empleada en programación paralela para aportar sincronización entre procesos.Los elementos principales que intervienen en el paso de mensajes son el proceso que envía, el que recibe y el mensaje.La técnica paso de mensajes usa canales y mensajes pero esta comunicación añade un coste al bus, memoria adicional para las colas y los mensajes.

Los procesadores paralelos se usan para acelerar la resolución de problemas de alto coste computacional.La finalidad principal consiste en reducir el tiempo de ejecución: si el tiempo secuencial t(n) se intentará que usando p procesadores el tiempo se reduzca a t(n)/p.El tiempo de ejecución de un programa secuencial depende de: tamaño de las variables de entrada, numero de recurrencias y tiempo de ejecución  t(n). En un programa paralelo la estimación del tiempo es más compleja. Además de los parámetros anteriores, depende de: número de procesadores t(n,p),los módulos de memoria (memoria compartida o distribuida)Es el tiempo transcurrido desde que empieza la ejecución del primero de los  procesadores hasta que acaba el último de ellos. Tiempo de ejecución paralelo.A lo largo de la ejecución de un programa paralelo hay puntos de sincronización de los que no siempre podemos determinar  su  duración  al  no  saber  en  el  orden  en  que van a llegar los distintos procesos a estos puntos.