Criba de eratostenes

2014

0

Instituto Tecnológico
de Acapulco

Ingeniería en sistemas computacionales
Asignatura: Computo Distribuido
Profesor: Daniel Enrique Vázquez Solís
Reporte de Práctica 2
Practica 2

Integrantes del equipo
1. Flor Angelis Bartolo Castillo
2. Josué Iván Morales González
3. Erik Iván Ruiz Giles

Horario 10:00–11:00 A.M.
26 Noviembre 2014

INDICE
INTRODUCCIÓN................................................................................................................................... 3
MARCO TEÓRICO ................................................................................................................................. 4
DESARROLLO PRÁCTICO...................................................................................................................... 7
RESULTADOS ....................................................................................................................................... 8
BIBLIOGRAFIA .................................................................................................................................... 14
CONCLUSIONES................................................................................................................................. 14

pág. 2

INTRODUCCIÓN
En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos
clásicos o algoritmos secuenciales, 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 resultadocorrecto.
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. Otro
ejemplo, puedeser el cálculo de Pi en paralelo.
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 decómputo
mediante la inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de
instrucciones dentro del procesador. Pero 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 (ver Ley de Amdahl). Por todo esto, a
partirde cierto nivel de paralelismo, añadir más unidades de procesamiento puede sólo
incrementar el coste y la disipación de calor.
El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio
(memoria) y tiempo (ciclos de procesador) que requiera. Los algoritmos paralelos también
necesitan optimizar la comunicación entre diferentes unidades de procesamiento. Esto seconsigue mediante la aplicación de dos paradigmas de programación y diseño de procesadores
distintos: memoria compartida o paso de mensajes.
La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que
se modifique simultáneamente por dos procesadores, por lo que se produce un coste extra en
ciclos de CPU desperdiciados y ciclos de bus. También obliga a serializaralguna parte del
algoritmo.

pág. 3

MARCO TEÓRICO
El procesamiento paralelo es un término que se usa para denotar un grupo de técnicas
significativas que se usan para proporcionar tareas simultáneas de procesamiento de datos con el
fin de aumentar la velocidad computacional de un sistema de computadoras. En lugar de procesar
cada instrucción en forma secuencial como es una computadora...