G4011449 - Programación de Sistemas Multinúcleo e Multiprocesador (Programación) - Curso 2013/2014

Información

• Créditos ECTS
• Créditos ECTS: 4.50
• Total: 4.5
• Horas ECTS
• Clase Expositiva: 12.00
• Clase Interactiva Laboratorio: 27.00
• Horas de Titorías: 1.00
• Total: 40.0

Outros Datos

• Tipo: Materia Ordinaria Grao RD 1393/2007
• Departamentos: Electrónica e Computación
• Áreas: Arquitectura e Tecnoloxía de Computadores
• Centro: Escola Técnica Superior de Enxeñaría
• Convocatoria: 2º Semestre de Titulacións de Grao/Máster
• Docencia e Matrícula: null

Profesores

Nome	Coordinador
ANTELO SUAREZ, ELISARDO.	SI

Horarios

Nome	Tipo Grupo	Tipo Docencia	Horario Clase	Horario exames
Grupo CLE01	Ordinario	Clase Expositiva	SI	SI
Grupo CLIL_01	Ordinario	Clase Interactiva Laboratorio	SI	SI
Grupo TI-ECTS01	Ordinario	Horas de Titorías	NON	NON

Programa

Existen programas da materia para os seguintes idiomas:

Castelán

Galego

Inglés

Obxectivos da materia
Esta materia ten como obxectivo introducir aos estudantes no tópico da programación paralela de sistemas múltinúcleo con memoria compartida e de sistemas multiprocesador. Faráse un énfase especial en desenvolver abstraccións de alto nivel para facilitar a detección de concurrencia nas aplicacións que lles permitan optimizar o rendemento. Asimesmo os alumnos aprenderán os mecanismos que lle permiten programar a concurrencia nos sistemas de computación e caracterizar o seu rendemento.
Contidos
PROGRAMA

O programa teórico desenvolveráse nun total de 12 clases maxistrais. Dedícanse un total de 27 horas de clase a resolución e discusión de casos e realización de prácticas.


TEORÍA


Tema 1: Mecanismos de Implementación para Programación Paralela (4 horas)

- Programación paralela para sistemas de memoria compartida: OpenMP e introducción a TBB.
- Programación paralela para sistemas baseados en paso de mensaxes: MPI.
- Escalamento e ley de Amdahl: caracterización de rendemento (gañancia en velocidade, isoeficiencia).

Obxectivo: dar a coñecer as interfaces para programar a concorrencia nos programas con dous paradigmas amplamente aceptados: paso de mensaxes e memoria compartida.
Introducir o concepto de escalamento e os seus límites e as diferentes técnicas de caracterización de rendemento.

Tema 2: Deseño Baseado en Patróns de Concurrencia para Optimización do Rendemento (2 horas)

- Descomposición guiada por tarefas.
- Descomposición guiada por datos.
- Agrupación eficiente de tarefas.
- Ordenación eficiente de tarefas.
- Datos compartidos.
- Avaliación do deseño para concurrencia.

Obxectivo: dada unha aplicación, definir estratexias con un alto nivel de abstracción para descompoñer o problema dun xeito efectivo para súa paralelización e optimizar o rendemento. As descricións están apoiadas en exemplos.

Tema 3: Deseño a Nivel Algorítmico para Optimización de Rendemento (3 horas)

- Algoritmos baseados en tarefas paralelas.
- Algoritmos divide e vencerás.
- Descomposición xeométrica.
- Algoritmos recursivos.
- Computación en pipeline.
- Coordinación baseada en eventos.

Obxectivo: describir estratexias de coordinación do esquema de descomposición elexido para a paralelización optimizando o rendemento. Estas estratexias indican como se organizará a computación, baseado nas dependenzas que se observen na descomposición de alto nivel. As descricións están apoiadas en exemplos.

Tema 4: Estructuras de Soporte para Optimización do Rendemento en Programación Paralela (3 horas)

- Simple programa múltiples datos.
- Maestro-escravo.
- Paralelismo de lazo.
- Modelo baseado na creación-terminación dinámica de tarefas.
- Datos compartidos.
- Colas compartidas.
- Arrays distribuidos.

Obxectivo: descrición de esquemas de organización da computación paralela próximo aos linguaxes de programación. Indícanse xeitos de estructurar a programación e de como compartir estructuras de datos para optimizar o rendemento.

PRÁCTICAS

As prácticas levaránse a cabo nos multprocesadores do CESGA e en sistemas multinúcleo dispoñibles na ETSE ou estructuras asociadas.

BLOQUE 1: Programación básica con OpenMP e MPI (4 horas)

Obxectivo: familiarizarse coa programación con paso de mensaxes (MPI) e a programación con memoria compartida (OpenMP).

BLOQUE 2: Programación paralela de algoritmos básicos. (6 horas)

Obxectivo: aplicar a exemplos básicos a metodoloxía de programación paralela descrita nas clases teóricas, utilizando OpenMP e MPI. Optimizar e caracterizar o rendemento.

BLOQUE3: Proxecto de programación paralela. (14 horas)

Obxectivo: paralelizar unha aplicación de certa complexidade aplicando a metodoloxía descrita nas clases de teoría para optimizar o rendemento. Optimizar a implementación para obter un escalamento axeitado. Facer un estudo de escalamento dependente do número de procesadores e tamaño do problema (caracterización de rendemento). O proxecto pode levarse a cabo en grupos de dous alumnos.

Bibliografía básica e complementaria
Básica:

T.G. Mattson, B.A. Sanders and B.L. Massingill, “Patterns for Parallel Programming”, Addison-Wesley, 2005.

Esta é a referencia fundamental para as clases de teoría. Expón unha medoloxía baseada en patróns para programación paralela, que se corresponde directamente cos contidos da materia. Esta é metodoloxía que Intel, o fabricante de sistemas múltinúcleo máis importante, intenta que asimilen os programadores ante o reto da programación paralela.


P. Pacheco, "An Introduction to Parallel Programming", Morgan Kaufmann Publishers, 2011.

Libro de introducción á programación paralela que complementa o anterior, que explica as metodoloxías e exemplos para programar con OpenMP e MPI.

Complementaria:

S. Akhter and J. Roberts, “Multi-core Programming. Increasing Performance through Software Multi-threading”, Intel Press, 2006.

Este é un libro editado por Intel, que sirve de complemento ao anterior, donde se explican detalles de máis baixo nivel para a implementación de programas paralelos.


J. Reinders, “Intel Threading Building Blocks”, O’Reilly, 2007.

O autor describe un dos últimos esforzos de Intel para simplificar a programación paralela. É probable que esta metodoloxía baseada en patróns sexa aceptada por un elevado número de programadores.

M.J. Quinn, “Parallel Programming in C with MPI and OpenMP”, McGraw-Hill, 2004.

Libro de referencia para programación con MPI e OpenMP, e descripción de exemplos sinxelos de programación paralela utilizando estas ferramentas.


B. Chapman, G. Jost and . van der Pas, "Using OpenMP: Portable Shared Memory Parallel Programming", The MIT Press, 2007

Libro de referencia para programación con OpenMP, centrado na obtención de elevadas prestacións con numerosos exemplos e explicación en profundidade da funcionalidade de OpenMP.
Competencias
Contribuír a acadar as competencias recollidas na memoria do título de Grao en Enxeñería Informática na USC (CG4, CG9, TR1, TR2, TR3, RI1, RI6, RI7, RI8, RI14).


Competencias asociadas ao módulo de programación dentro do grao:

- Saber calcular a complexidade computacional dun algoritmo e avaliar a implementación máis axeitada dun algoritmo determinado de acordo cos recursos dispoñibles (memoria e tempo de execución).

- Coñecer diferentes paradigmas de programación e saber escoller o máis apropiado en cada situación.

- Coñecemento dos diferentes paradigmas de programación.
Metodoloxía da ensinanza
Esta materia ten un enfoque eminentemente práctico, donde a aprendizaxe é a través de exercicios e un proxecto de programación. Plantexamos os seguintes tipos de clases:

Clases maxistrais (12 horas): Nestas clases o profesor desenvolverá dun xeito resumido os contidos do programa teórico, que serve de base para a posterior aplicación nas clases prácticas de programación. Os alumnos poderán acceder o material que se expoñerá na clase con antelación, polo que se espera que o alumno participe na discusión dos conceptos que se traten. O profesor promoverá un ambiente participativo e asignaralle a algúns alumnos certas partes do programa para que as expliquen.

Clases prácticas (24 horas): estas clases dedicaránse a desenvolver o programa de prácticas da materia. Básicamente consistirá na realización de programas paralelos de complexidade crecente até asignarlle un proxecto completo de programación paralalela a grupos de dous alumnos. Os alumnos serán o elemento activo nestas clases, e o profesor guiará a aprendizaxe ante as cuestións e dúbidas plantexadas . Os enunciados das prácticas, así como o material de axuda (tutoriales, etc) estarán dispoñibles no campus virtual da USC.

Clases de discusión (3 horas): Nestas clases os alumnos expoñerán os proxectos realizados, discutindo a súa implementación a diferentes niveis e o grado de escalamento da aplicación.

As titorías poderán ser presenciais (horario a determinar en acordo con alumnos, no despacho 22 do Departamento de Electrónica e Computación ou nos lugares que especifique o centro) ou a través de correo electrónico (á dirección elisardo.antelo@usc.es).

Sistema de evaluación
Convocatoria ordinaria:

Contribución á nota final e criterios de avaliación (sobre 10 puntos):

- Participación no desenvolvemento das clases teóricas (1.5p): o alumno recibirá unha nota de até 1.5 puntos en función da súa participación nas clases teóricas. Pode participar presentado algúns conceptos ou discutindo e plantexando dúbidas ou resolvendo dúbidas plantexadas por outros compañeiros.
- Adquisición de coñecementos con OpenMP e MPI (1.5p): valoráse o grado de coñecemento adquirido coa realización dalgúns exercicios propostos e a calidade dos mesmos.
- Realización de programas paralelos sinxelos (2p): valoraráse a apliación das metodoloxías descritas nas clases teóricas, o uso de estructuras eficientes de programación con OpenMP e MPI aplicadas a cada problema concreto.
- Proxecto de programación paralela (5p): valoraráse a aplicación da metodoloxía para programación paralela descrita nas clases teóricas, o grao de dificultade elexido polos alumnos para o proxecto proposto (a proposta por parte do profesor será relativamente aberta, e serán os alumnos os que decidan o grado de dificultade que queiran acadar), calidade do estudo de escalamento e caracterización do programa, presentación de resultados (oral e escrita).

Non existe un mínimo a acadar en ningunha das partes. Para superar a materia, debe acadarse unha puntución de 5 ou superior.

Os alumnos que non sexan de nova matrícula non conservan notas de cursos anteriores.

Convocatoria extraordinaria:

Os mesmos criterios de avaliación que na convocatoria ordinaria. O límite para a entrega do proxecto e prácticas é o día do exame oficial.

Condición para cualificación de non presentado: non presentar ningunha práctica ou proxecto.


As titorías, as discusións na clase, e a interacción nas clases prácticas permitiranlle ao profesor coñecer de xeito informal o grao de asimilación da materia que van acadando as alumnas/os ao longo do cuadrimestre.

Tempo de estudo e traballo persoal
Con 4.5 créditos ECTS, o traballo persoal do alumno debe ser dunhas 67.5 horas, distribuídas do seguinte xeito:

- Estudo autónomo: 20 horas, dedicadas á asimilacíon dos contidos teóricos para aplicación ás prácticas e ao proxecto, e preparación de asignacións por parte do profesor para desenvolver na clase algunha das partes do programa teórico.
- Escritura de exercicios, conclusións e outros traballos: 5 horas, fundamentalmente dedicadas á preparación da presentación de resultados do proxecto (oral e escrita).
- Programación/experimentación: 35 horas, dedicadas á resolución das prácticas e proxecto propostos.
- Actividades de avaliación: 7.5 horas, dedicadas á propia presentación de resultados do proxecto, e modificacións requeridas do proxecto logo da corrección e exposición, incorporarndo as propostas do profesor e do resto de compañeiros.

A programación da materia será de tal xetio que a distribución do número de horas de traballo persoal ao longo do cuadrimestre sexa o máis uniforme posible. A distribución deste esforzo pode variar ao longo do cuadrimestre, en especial na etapa de preparación do proxecto, e na elaboración e presentación de resultados de prácticas.

Recomendacións para o estudo da materia
Resulta recomendable ter coñecementos de programación en C. Tamén resulta interesante ter cursada a materia do grado Sistemas Paralelos, ou a de ETIS Sistemas Distribuídos e Paralelos.

A materia está deseñada para que o alumno participe activamente e de xeito regular durante o seu desenvolvemento.

Observacións
A entrega dos materiais do curso e as comunicacións electrónicas cos alumnos levarase a cabo coa ferramenta do campus virtual da USC.

A materia será impartida en inglés (clases e material).