Materiales
  Teoría
  Laboratorio
Tareas
Notas ciclo 2013-2
Fuentes
      

CC301: Algoritmos Paralelos


Introducción al curso

Computación paralela es el uso simultáneo de varios recursos de cómputo para resolver un problema computacional. Los recursos son CPUs o cores, se usan varios a la vez. Pueden estar en una computadora con varios cores, o en varias computadoras conectadas por una red, o en un ambiento mixto.

Un problema se divide en muchas partes que pueden resolverse a la vez, concurrentemente. Cada parte se asigna a un CPU o core distinto. De esta forma se pueden resolver problemas más rápido, o resolver problemas que necesitan más memoria de la que una sola computador dispone

En este curso se estudiarán los algoritmos paralelos para diversos problemas típicos de ciencias de computación y computación científica

Para mayores detalles, ver el syllabus del curso

Objetivos del curso

  • Introducir al alumno a los fundamentos del paralelismo.
  • Describir los modelos de memoria compartida y de paso de mensajes
  • Presentar los tipos de paralelización.
  • Usar MPI y Open MP en C.
  • Presentar algoritmos paralelos y ejemplos de aplicación.

Teoría

Estos materiales no son auto-contenidos. Se necesita asistir a clase para entender todo el material. Los recursos en castellano son escasos, es mejor buscar recursos en ingles.


Laboratorio

Las computadoras disponibles tiene 4 cores. Se usa máquinas virtuales bajo Oracle Virtual Box, para no interferir con las instalaciones de otros cursos. Pedir usuario y password al profesor.


Tareas

La 1ra tarea de teoría es leer un paper, analizar y exponer lo que se ha entendido. GRUPOS de 3 alumnos. Fecha de Entrega : 24/09.

La 1ra tarea de laboratorio. GRUPOS de 2 alumnos. Fecha de Entrega : 27/09.

Sea 4 dimensiones: x,y,z,t. Hay un toro de tamaño variable en el tiempo:

( R(t) - sqrt(x2+y2) )2 +z2 =r(t)2

R(t): distancia del centro del tubo del toro al centro del toro (0,0,0)

r(t): radio del tubo

Dentro del toro se genera energia, con una potencia de P(x,y,z,t) Watts (=Joules/s)

Diga cuanta energia se genera desde el tiempo 0 al tiempo 10 para los siguientes R,r,P:

  • Grupo 1: R(t)=100+t; r(t)=(t-1)2+1; P(x,y,z,t)=abs(x)
    Lapa Romero y Pinto Alva
  • Grupo 2: R(t)=100-t; r(t)=(t+1)2/2; P(x,y,z,t)=abs(z)
    Iparraguirre Paredes y Martinez Vera
  • Grupo 3: R(t)=(t-1)2+19; r(t)=19-t; P(x,y,z,t)=1/exp(z)
    Yarasca Flores y Aparco Cardenas
  • Grupo 4: R(t)=(t-1)2+19; r(t)=11-t; P(x,y,z,t)=1/exp(x2)
    Montalvan Serafin y Huaroto Pachas
  • Grupo 5: R(t)=(1/exp(t2)) +99; r(t)=log(10*t+1)+2; P(x,y,z,t)=abs(x+y)
    Castro Ochante y Rodriguez Condori
  • Grupo 6: R(t)=(1/exp(t)) +99; r(t)=log(101-10*t)+1; P(x,y,z,t)=abs(x-y)
    Ucañay Barreto y Gamarra Ganoza
  • Grupo 7: R(t)=abs(t-3)+90; r(t)=20-t2; P(x,y,z,t)=1/exp(z)
    Arias Levano y VIllegas Herrera
  • Grupo 8: R(t)=90+sqrt(t); r(t)=11-t; P(x,y,z,t)=1/exp((x+y)2)
    Arias Levano y VIllegas Herrera
  • Grupo 9: Igual que grupo 1 pero el toro solo existe entre angulo 0 y 270 respecto a x en el plano xy, y P(x,y,z,t)=abs(y+1)
    Canepa Rodriguez y Zambrano Rojas
  • Grupo 10: Igual que grupo 2 pero el toro solo existe entre angulo 45 y 360 en el corte transversal, y P(x,y,z,t)=abs(x*z)
    Bravo Rocca

La 2da tarea de teoría es hacer un estado del arte sobre paralelismo aplicado a.... GRUPOS de 3 alumnos.

Fecha de Entrega : 29/oct/2013.

  • Finanzas: Lapa, Pinto, Bravo
  • Data mining: Carhuarica, Villegas, Arias
  • Robotica: Zambrano, Canepa, Aparco
  • Electrodinamica y telecomunicaciones: Rodriguez
  • Busqueda en web y redes sociales: Montalvan y Castro
  • Astronomia: Iparraguirre, Martinez, Yarasca
  • Diseño de medicinas (drug design): Gamarra, Ucañay, Casas

La 2da tarea de laboratorio. GRUPOS de 2 alumnos. UN tema por grupo. Fecha de Entrega : 12/nov.

  1. Problema de la mochila, probar con mochila de tamaño 400, y 150 objetos aleatorios de tamaños entre 1 y 30 y precios entre 1 y 20 (http://en.wikipedia.org/wiki/Knapsack_problem) usando OpenMP. Use el algoritmo de su elección. Testear el programa con 1, 2 y 4 núcleos. No solo se quiere el programa, también que lo explique el razonamiento detrás del programa.
    • Bravo y Carhuarica
    • Castro y Rodriguez
    • Huaroto
  2. Visibilidad de lineas. Probar con 200 lineas al azar de tamaño entre 1 y 5 dentro de un área de 800x800, en MPI. Una línea X es visible desde un punto P, si visualmente ninguna otra línea tapa la visión de todo o parte de X a una persona parada en P. Una línea de canto se considera que SI bloquea la visión. El programa debe decir que líneas son visibles desde el punto P. Antes de pedir P, el programa debe crear un archivo de texto con las coordenadas de los extremos de las líneas. Testear el programa con 1, 2 y 4 núcleos. No solo se quiere el programa, también que lo explique el razonamiento detrás del programa.
    • Pinto y Lapa
    • Arias y Villegas
    • Montalvan y Canepa
  3. Haga un programa paralelo en MPI que solucione el problema de la intersección de líneas usando computación paralela. Se generan N líneas al azar de longitud máxima L en un espacio entre 0<=x<=100, 0<=y<=100. El objetivo del problema es obtener todas las líneas que llegan a intersectarse con otra línea, y el punto (x,y) de intersección de ellas. N y L se piden al usuario humano; pruebe con N=1000 y L=4 para testear el programa con 1, 2 y 4 núcleos. No solo se quiere el programa, también que lo explique el razonamiento detrás del programa.
    • Iparraguirre y Martinez
    • Ucañay y Gamarra

La 3ra tarea de laboratorio. GRUPOS de 2 alumnos. Fecha de Entrega : 3/dic. Informe sobre programa paralelo usando OPENMP que implementa successive over-relaxation (SOR) del mismo problema que esta en poissonparalelo.c

La 4ta tarea de laboratorio. GRUPOS de 2 alumnos. Fecha de Entrega : 6/dic. Blog y/o sitio web de paralelismo con estadistica de visitas y un enlace prominente al sitio web del curso

Notas 2013-2

    1ra nota TEORIA 2da nota TEORIA 1ra nota LAB 2da nota LAB 3ra nota LAB 4ta nota LAB
Aparco C David 15   no se presento      
Arias L. Raul 14 14 no se presento   13  
Bravo R. Gusseppe 15 13 8 14    
Canepa R Hugo 15   no se presento      
Carhuarica A Luis 14 14 8 14    
Casas R. Tomas no se presento   8      
Castro O Jose 15 13 9 14 14  
Gamarra G Paul no se presento 12 9 9    
Huaroto P Eduardo 15   no se presento   10  
Iparraguirre Nhalim 15 10 15 15 15  
Lapa R. Noemi 15 13 9 13    
Martinez Jason 15 10 15 15 15  
Montalvan S Jonathan 14 13 no se presento   10  
Pinto A. Leticia 15 13 9 13    
Rodriguez C Elio 15   9 14 14  
Ucañay B Dany no se presento 12 9 9    
Villegas H Javier 14 14 no se presento   13  
Yarasca  Martin 15   no se presento      
Zambrano R Kevin 15   no se presento      

Fuentes

Directorio con programas cap.2: dar click aquí

Directorio con programas cap.3: dar click aquí

Directorio con programas MPI Intermedio: dar click aquí

Directorio con programas Open MP: dar click aquí

Directorio con programas sobre números pseudo aleatorios: dar click aquí

Directorio con programas fuente de matrices y ecuaciones lineales: dar click aquí

Directorio con programas fuente de sorting: dar click aquí

Directorio con programas fuente de grafos: dar click aquí



Propiedad de Glen Rodríguez, email: grodriguez@uni.edu.pe — OJO, leo esta casilla de mail cada 3 dias, si no contesto pronto es por eso. Tambien pueden ver mi otro site AQUI

gp1
1.881185e+009
gp2
2.665976e+008
gp3
2.308566e+011
gp4
4.974282e+003
gp5
5.727655e+007
gp6
2.480359e+007
gp7
3.518919e+037
gp8
3.510075e+003
gp10
1.436244e+010

Last Change: 11/10/2013