Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Informatica
Área: Area II: Sistemas de Computacion
(Programa del año 2008)
(Programa en trámite de aprobación)
(Programa presentado el 05/08/2008 10:38:22)
I - Oferta Académica
Materia Carrera Plan Año Periodo
(OPTATIVAS) FUNDAMENTOS DE LOS SISTEMAS PARALELOS LIC.EN CS.DE LA COMPUTACION 2008 2° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
PICCOLI, MARIA FABIANA Prof. Responsable P.Adj Exc 40 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total B - Teoria con prácticas de aula y laboratorio Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
7 Hs.  Hs.  Hs.  Hs. 7 Hs. 2º Cuatrimestre 11/08/2008 21/11/2008 15 105
IV - Fundamentación
El auge de las nuevas tecnologías y la constante demanda de mejores resultados en las aplicaciones hace imprescindible el estudio de nuevas técnicas y metodologías de programación. La enseñanza de la disciplina Sistemas Paralelos tiene como objetivo proveer las herramientas básicas para permitir al licenciado considerar la computación paralela como la alternativa natural a la programación secuencial en el desarrollo de aplicaciones. Además, le permitiría iniciarse en el campo de la investigación científica y en desarrollos propios de su área de interés.
En el Plan de Estudio de la Licenciatura se introduce el tema en distintas asignaturas a través de dos tópicos fundamentales: el hardware y el software. La presente asignatura pretende establecer el marco teórico para analizar y desarrollar aplicaciones paralelas eficientes y adecuadas a ejecutarse en cualquier arquitectura.
V - Objetivos
Si bien la computación paralela surgió como el candidato natural para cubrir la insistente demanda de mayor performance, no logró imponerse aún como paradigma de computación.
Al hablar de paralelismo surgen dos conceptos bien diferenciados y muy relacionados: el hardware paralelo y el software paralelo. La mayoría de los estudios teóricos y prácticos sobre computación paralela, generalmente están enfocados a analizar diferentes arquitecturas y lenguajes de programación o herramientas paralelas reales.
El diseño de programas paralelos y su eficiencia están fuertemente relacionados a la arquitectura paralela subyacente y al modelo de programación aplicado. Para obtener eficiencia, un programa paralelo debe ser adecuado a las características de la máquina paralela real. Esto se logra, si el programa paralelo es: diseñado siguiendo un modelo de computación paralela, implementado a través de un modelo de programación y evaluado según un modelo de costo.
Fundamentos de la Programación Paralela es una asignatura que tiene como objetivo establecer el marco teórico adecuado para estudiar y desarrollar software paralelo eficiente e independiente de la arquitectura y las tecnologías existentes. Para lograrlo, se prevé un estudio formal de los sistemas paralelos, retomando los conceptos vistos en las materias anteriores y analizandolos desde el punto de vista de los modelos de computación paralela y los distintos paradigmas.

Todo modelo de computación define la conducta de una máquina teórica. Su objetivo es facilitar el diseño y análisis de algoritmos que, en un amplio rango de arquitecturas, pueden ejecutarse con la eficiencia preestablecida. Un modelo de computación tiene siempre asociado un modelo de programación, el cual brinda las herramientas necesarias para implementar la metodología propuesta por el modelo de computación. Existen varios modelo de computación paralela, en esta asignatura analizaran algunos de ellos: PRAM y BSP, y se consideraran diferentes modelos de programación, principalmente aquellos propuestos por diferentes librerías de pasaje de mensajes orientadas o no a cada modelo de computación
VI - Contenidos
Programa analítico y de examen


1- Sistemas Paralelos.
Hardware y Software. Características de un Sistema Paralelo. Limitaciones de un Sistema Paralelo
Aspectos a considerar para desarrollar una aplicación paralela: división del problema, comunicaciones y asignación de tareas a procesadores.
Técnicas para la resolución de problemas paralelos: técnica "divide y vencerás" y técnica de "ramificación y acotación".
Análisis de la performace de un Sistema Paralelo. Variables de medición de la performance de un Sistema Paralelo: eficiencia, portabilidad, escalabilidad, costo, trabajo y aceleración.

2- Modelos de Computación.
Características de los Modelos de Computación. Necesidad de un modelo de Computación.
Modelo de Programación. Propiedades de los modelos de programación. Clasificación de los modelos de programación.
Modelo de Análisis de Costo. Características y propiedades de los modelos de costo.
Relación entre Modelo de Computación, Modelo de Programación y Modelo de Análisis de Costo.
Paradigmas de Computación Paralela: Paralelismo de Datos, de Tareas, Anidado de Datos, Pipeline, en Memoria Compartida, en Memoria Distribuida.

3- Modelo de Computación PRAM.
Características generales.
Computadora PRAM. Resolución de Conflictos de acceso a Memoria
Modelo de Programación PRAM. Activación y Asignación de Procesadores. Políticas de Asignación de Procesadores.
Modelo de Costo PRAM. Características. Problemas NC.
Cuestionamientos al modelo PRAM. Factibilidad del modelo PRAM.

4- Modelo de Computación BSP
Características generales.
Computadora BSP. Computadora teórica vs. Computadoras reales.
Modelo de Programación BSP. Conceptos de paso y superpaso. Relación entre comunicación, cómputo y sincronización.
Modelo de Costo. Características. Parámetros del Modelo BSP: L, g.
Predicción del rendimiento de un programa BSP. Análisis del costos de un superpaso: cómputo y comunicaciones. Concepto de h-relación.
Relación entre modelo PRAM y modelo BSP.

5- Modelos de Programación definidos por librerías estándares.
Librería PVM. Modelo de programación asociado. PVM y modelo PRAM. PVM y modelo BSP.
Librería MPI. Modelo de programación asociado. MPI y modelo PRAM. MPI y modelo BSP.
Librería BSPpub. Modelo de programación asociado. BSPpub y modelo PRAM. BSPpub y modelo BSP. Características propias de la librería: Grupos, objetos BSP y sincronización costo cero.
Relación entre PVM, MPI y BSPpub

VII - Plan de Trabajos Prácticos
Práctico 1: Revisión: PVM y MPI.
Práctico 2: Modelo PRAM - Programación y Análisis de Costos.
Práctico 3: Modelo BSP - Desarrollo de Programas de Aplicación
Práctico 4: Modelo BSP - Análisis de Costos
Práctico 5: Modelo BSP - Librería BSPpub.
Práctico 6: Modelo PRAM - Librerías: PVM, MPI y BSPpub.
Práctico 7: Modelo BSP - Librerías: PVM, MPI y BSPpub.
Práctico 8: Trabajo Práctico evaluativo.
VIII - Regimen de Aprobación
Acerca del dictado de la Materia:

Las clases tendrán la modalidad teórico-práctica.

Acerca de la regularización de la materia:

El alumno debe:
1- Tener como mínimo un 80% de asistencia a las clases teórico-prácticas.
2- Por cada práctico ( prácticos 1 al 7), la cátedra exigirá la entrega de un ejercicio tipo.
3- Desarrollo de un trabajo práctico evaluativo (práctico 8) consistente de:
3.1- La programación de una aplicación paralela considerando alguno de los modelos de computación vistos.
3.2- Confección de un informe. Dicho informe deberá: especificar los aspectos teóricos y tener un análisis detallado y justificado de las decisiones tomadas.
3.3- Exposición del trabajo realizado.
Los puntos 3.1 y 3.2 tendrán una recuperación.

Acerca de la aprobación de la materia:

Por promoción: Si la nota obtenida en el trabajo práctico evaluativo obtiene una nota mayor a 7, y el desempeño del alumno durante la cursada fue satisfactorio.
Por examen regular: Si el alumno regularizó la materia, puede acceder a un examen regular el cual puede ser oral o escrito y versará sobre los temas del programa.

Dadas las características de la materia y la importancia de los desarrollos prácticos, no se permiten alumnos libres.
IX - Bibliografía Básica
[1] O. Bonorden et all - PUB library, Release 6.0 - User guide and function reference. 1998.
[2] O. Bonorden et all - The Puderborn University BSP (PUB) Library- Desing, Implementation and performance. 1999.
[3] Foster I. - Designing and Building Parallel Programs. Addison-Wesley. 1994.
[4] M. Gou and Layang – High Performance Computing : Paradigm and Infrastructure. Wiley. 2006.
[5] M. Goudreau et all - Towards Efficiency and Portability: Programming with the BSP model. 1996.
[6] A. Grama, A. Gupta, G. Karypis, and V. Kumar - Introduction to Parallel Computing. Addison-Wesley, 2003.
[7] Keller, J., Kesler, C., Larsson, J. – Practical PRAM Programming. John Wiley & sons, inc.. 2001.
[8] Leopold, C. – Parallel and Distributed Computing: a survey of Models, paradigms and approaches. John Wiley & Son, Inc. 2001.
[9] W.F. Mccoll - General Purpose parallel Architectures. 1990.
[10] W.F. Mccoll - BSP Programming. 1994.
[11] Quinn M.- Parallel Computing. Theory and Practice. Second Edition. McGraw-Hill, Inc. 1994.
[12] Skillicorn, D., Talia, D. – Programming Languajes for Parallel Processing. IEEE Computer Society press. 1995.
[13] L.G. Valiant - A Bridging Model for Parallel Computation. 1990.
[14] Wilkinson B. & Allen M. - Parallel programming: Techniques and Application using Networked Workstations and Parallel Computer. Prentice-Hall. 1999.
X - Bibliografia Complementaria
[1] Apuntes de la Cátedra
[2] Artículos de Internet
XI - Resumen de Objetivos
El diseño de programas paralelos y su eficiencia están fuertemente relacionados a la arquitectura paralela subyacente y al modelo de programación aplicado. Para obtener eficiencia, un programa paralelo debe ser adecuado a las características de la máquina paralela real. Esto se logra, si el programa paralelo es: diseñado siguiendo un modelo de computación paralela, implementado a través de un modelo de programación y evaluado según un modelo de costo.
Fundamentos de la Programación Paralela es una asignatura que tiene como objetivo establecer el marco teórico adecuado para estudiar y desarrollar software paralelo eficiente e independiente de la arquitectura y las tecnologías existentes. Para lograrlo, se prevé el estudio de la temática desde el punto de vista de los modelos de computación paralela y los distintos paradigmas.
Los modelo de computación definen la conducta de una máquina teórica y facilitan el diseño y análisis de algoritmos que pueden ejecutarse con una eficiencia preestablecida. Un modelo de computación tiene asociado un modelo de programación y un modelo de análisis de costo. Los modelos de computación a analizar son: PRAM y BSP, y de programación: aquellos propuestos por diferentes librerías de pasaje de mensajes orientadas o no a cada modelo de computación.
XII - Resumen del Programa
1- Sistemas Paralelos.
2- Modelos de Computación.
3- Modelo de Computación PRAM.
4- Modelo de Computación BSP
5- Modelos de Programación definidos por las librerías estándares MPI, PVM y BSPpub.
XIII - Imprevistos