Créditos ECTS Créditos ECTS: 4.5
Horas ECTS Criterios/Memorias Traballo do Alumno/a ECTS: 74.2 Horas de Titorías: 2.25 Clase Expositiva: 18 Clase Interactiva: 18 Total: 112.45
Linguas de uso Inglés
Tipo: Materia Ordinaria Grao RD 1393/2007 - 822/2021
Centro Escola Técnica Superior de Enxeñaría
Convocatoria: Segundo semestre
Docencia: Sen docencia (En extinción)
Matrícula: Non matriculable (Só alumnado repetidor)
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.
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 (6 horas)
- Programación paralela para sistemas de memoria compartida: OpenMP.
- Programación paralela para sistemas baseados en paso de mensaxes: MPI.
- Programación paralela para sistemas manycore: 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: Introducción teórica á Programación Paralela (2 horas)
- Análese do problema.
- Descomposición do problema.
- Descomposición guiada por tarefas.
- Descomposición guiada por datos.
- Comunicacións.
- Sincronizacións.
- Dependenza de Datos.
- Balanceo da carga.
- Granularidade.
- Entrada/saída en paralelismo.
- Depuración de programas paralelos.
- Análese de prestación e sintonización (tuning) de programas paralelos.
Obxectivo: dar unha introducción de alto nivel aos principais conceptos teóricos da programación paralela. Pretendemos dar unha base teórica mínima para abordar a parte práctica de programación paralela.
Tema 3: Exemplos de Paralelización (4 horas)
Obxectivo: neste tema presentamos varios exemplos de paralelización de programas, partindo dunda versión puramente serie, pasando por versións paralelas pouco eficientes, até chegar á versión paralela máis eficiente.
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, MPI (6 horas)
Obxectivo: familiarizarse coa programación con paso de mensaxes (MPI), 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. (12 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 fíos e tamaño do problema (caracterización de rendemento). O proxecto pode levarse a cabo en grupos de dous alumnos.
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 sirve de soporte para os contidos da materia. Esta é metodoloxía que Intel, intenta que asimilen os programadores ante o reto da programación paralela. Polos contidos do libro, podemos dicir que a maior parte do mesmo é atemporal, e podemos dicir que as metodoloxías de programación paralela non progresan co tempo dunha forma clara.
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.
https://computing.llnl.gov/tutorials/parallel_comp/. Blaise Barney, Lawrence Livermore National Laboratory
Web do Lawrence Livermore National Laboratory que sirve como introducción á programación paralela.
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 aos anteriores, donde se explican detalles de máis baixo nivel para a implementación de programas paralelos.
Kirk, D. B., & Wen-mei, W. H. (2010). Programming massively parallel processors: a hands-on approach. Morgan Kaufmann Publishers.
Conceptos básicos de programación en paralelo e arquitectura da GPU. Explora en detalle varias técnicas para a construción de programas paralelos en GPU.
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.
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). Específicamente:
CG4. Capacidade para definir, avaliar e seleccionar plataformas hardware e software para o desenvolvemento e execución de sistemas, servizos e aplicaciones informáticas, de acordo cos coñecementos adquiridos segundo o establecido no "Acuerdo del Consejo de Universidades del 03/03/2009 para los títulos oficiales en el ámbito de la Ingeniería Técnica Informática".
CG9. Capacidade para resolver problemas con iniciativa, toma de decisións, autonomía e creatividade. Capacidade para saber comunicar e transmitir os coñecementos, habilidades e destrezas da profesión de Enxeñeiro en Informática.
TR1. Instrumentais: capacidade de análese e síntesise. Capacidade de organización e planificación. Comunicación oral e escrita en galego, castelán e inglés. Capacidade de xestión da información. Resolución de problemas. Toma de decisións.
TR2. Personais: Traballo en equipo. Traballo nun equipo multidisciplinar e multilingüe. Habilidades nas relacións interpersonais. Razoamento crítico. Compromiso ético.
TR3. Sistémicas: Aprendizaxe autónomo. Adaptación a novas situacións. Creatividade. Iniciativae espíritu emprendedor. Motivación pola calidade. Sensibilidade por temas medioambientais.
RI1. Capacidade para deseñar, desenvolver, seleccionar e avaliar aplicacións e sistemas informáticos, asegurando a súa fiabilidade, seguridade e calidade, conforme aos principios éticos e a lexislación e normativa vixente.
RI6. Coñecemento e aplicación dos procedimentos algorítmicos básicos das tecnoloxías informáticas para deseñar solucións a problemas, analizando a idoneidade e complexidade dos algoritmos propostos.
RI7. Coñecemento, deseño e utilización de forma eficiente dos tipos e estructuras de datos más axeitadas á resolución dun problema.
RI8. Capacidade para analizar, deseñar, construir e manter aplicacións de forma robusta, segura e eficiente, elixindo o paradigma e as linguaxes de programación máis axeitados.
RI14. Coñecemento e aplicación dos principios fundamentais e técnicas básicas da programación paralela, concorrente, distribuída e de tiempo real.
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.
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 (en horario de acordo cos alumnos ou segundo o fixe o centro), a través de correo electrónico, ou a través do campus virtual.
Desenvolvemento de competencias:
CG4: coa era multinúcleo, a computación na nube e "big data", a programación paralela resulta fundamental. Esta competencia desenvolvese nas clases teóricas no aspecto concreto do contexto de ferramentas para a programación paralela.
CG9: o proxecto constitúe a mayor oportunidade para desenvolver esta competencia, xa que o plantexamento é bastante aberto, e permite ao alumno amosar e desenvolver as súas capacidades en termos de creatividade, toma de decisións, autonomía e iniciativa. O alumno ten o incentivo de desenvolver estas capacidades debido aos criterios de avaliación. Na interacción durante a realización do proxecto o profesor intercambiará ideas ao respecto e guará aos estudantes no desenvolvemento destas competencias.
TR1:
- Capacidade de análese e síntese
As prácticas de programación paralela que se levan a cabo obrigan a exercitar estas capacidades, xa que os alumnos teñen que deseñar a estratexia de paralelización (síntese) e realizar unha análese das ganancias en velocidade que se obteñen (normalmente require analizar a limitación das ganancias en velocidad obtidas).
- Capacidade de organización e planificación
Todos os exercicios e prácticas a entregar teñen plazos estrictos de entrega, polo que
os alumnos teñen un claro incentivo a mellorar as súas capacidades de organización e
planificación. Para axudar aos alumnos, no caso das prácticas, ademais do prazo de entrega,
indícase o número de sesións de prácticas recomendado para cada uha delas.
- Comunicación oral e escrita en lingua nativa e extranxeira
A calidade da presentación e redacción das memorias das prácticas aparecen nos criterios de valoración
das mesmas. Os alumnos teñen que facer unha presentación oral dos resultados da última práctica (proxecto), o cal tamén se ten en conta na nota da mesma.
Na interacción cos alumnos nas clases prácticas, ante as dúbidas dos alumnos, o profesor ten por norma non mirar a pantalla do
ordenador, e polo tanto o alumno ten que explicarlle verbalmente ao profesor o problema que lle xurdiu dun xeito conciso e claro.
En canto á lingua extranxeira, a materia completa impártese en inglés, e os alumnos teñen o incentivo de expresarse tamén nesta lingua en todos os aspectos docentes. Os alumnos teñen que consultar manuais e documentos en inglés para levar a cabo algúns exercicios e prácticas.
- Resolución de problemas
O proceso de paralelización de programas axuda a desenvolver esta competencia.
- Toma de decisións
A práctica 2 (proxecto) especifícase dun xeito bastante aberto, de tal forma que o alumno ten que tomar unha serie de decisións para o seu deseño. Por suposto estas decisións teñen consecuencias na avaliación da práctica.
TR2:
- Traballo en equipo
Parte das prácticas lévanse a cabo en grupos de dúas persoas, o que esixe certa coordinación.
- Razonamiento crítico
A idea da presentación dos resultados da práctica 2 (proxecto) é que o resto de alumos opinen e critiquen dita presentación
- Compromiso ético
Faise moita incidencia na necesidade de evitar o plaxio polo inxusto que resulta, e polos riscos que implica: faise saber que existe
unha normativa antiplaxio na Escola que poder ter serias consecuencias, e que o profesor non vacilará en aplicalo se detecta casos claros.
TR3:
- Aprendizaxe autónomo
Algunhas partes da materia no se explican en detalle en clase e simplemente se lles proporciona
o material para o seu estudo autónomo.
Nas prácticas teñen que traballarse algúns conceptos que non foron explicados en detalle, polo
que o propio alumno ten que profundizar de xeito autónomo.
- Creatividade
Este é un criterio que se valora na notas das prácticas: creatividade e elegancia das solucións aportadas. Na interacción cos alumnos o profesor aproveita para ilustrar con exemplos este aspecto e transmitir ao alumno a importancia do proceso creativo.
- Motivación pola calidade
Este é un criterio que se valora na nota de prácticas e exercicios, facendo un énfase explicito neste aspecto
cando se propoñen os enunciados.
- Sensibilidade cara os temas medioambientais
Polos temas tratados na materia faise énfase no problema do consumo de potencia/enerxía dos procesadores, e a necesidade
de reducilo para contribuir a unha sociedade sostible. Específicamente o profesor faille ver aos alumnos que a programación paralela pode ser un elemento fundamental para aforrar en consumos de potencia/enerxía. Por outra banda, cando é necesrio entregar exercicios ou memorias de prácticas indicase que se utilice o mínimo papel posible, e con materias austeros (por exemplo encadernación con grapas, etc)
RI1: esta capacidade desenvólvese nas clases teóricas e ao longo do proxecto, xa que se fai énfase en que moitas aplicacións informáticas necesitan programación paralela, e nestas é esencial garantir a súa fiabilidade, seguridade e calidade. Transmiteselle ao alumno a dificultade da programación paralela nestes aspectos pola falta de determinismo durante a execución. O proxecto serve para desenvolver esta capacidade xa que os alumnos comproban o complexo que é depurar programas paralelos e o difícil que pode resultar garantir unha aplicación fiable e segura.
RI6: esta competencia trabállase no contexto da programación paralela, mediante numerosos exemplos de algoritmos paralelos básicos en diferentes eidos, que son revisados e analizados nas clases teóricas. Nos exercicios de programación básicos das clases interactivas os alumnos teñen a posibilidade de implementar algúns destes algoritmos básicos.
RI7: esta competencia traballase tamén no contexto da programación paralela, analizando as estructuras de datos máis axeitadas segudo o paradigma de programación en memoria compartida ou paso de mensaxes. Analízanse nas clases teóricas o efecto de diferentes estrcuturas de datos segundo o tipo de problema, en termos de ganancia en velocidade, posibilidade de erros, etc. O proxecto sirve para poñer en prácticas todas estas habilidades.
RI8: Nas clases teóricas analizanse os diferentes paradigmas de programación paralela e as linguaxes e interface s máis utilizadas para expresar o paralelismo. Durante as clases interactivas, os alumnos familiarízanse con estes paradigmas e ferramentas de programación, en principio resolvendo exercicios básicos de programación paralela. No proxecto afianzase esta competencia, realizando xa unha aplicación máis complexa.
RI14: esta competencia é o núcleo central desta materia e trabállase en todas as actividades docentes que realizamos na materia.
Con respecto a:
"Competencias asociadas ao módulo de programación dentro do grao:
PROG1- 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).
PROG2- Coñecer diferentes paradigmas de programación e saber escoller o máis apropiado en cada situación.
PROG3- Coñecemento dos diferentes paradigmas de programación."
Nas clases teóricas explicamos a ley de Amdahl, e as causas das limitacións da ganancia en velocidade das aplicacións paralelas. Tamén se enseña a facer estimacións de complexidade dos algoritmos paralelos, tendo en conta tamén os tempos de comunicación e sincronización segundo o tipo de paradigma de computación paralela que se utilice. Resulta de relevancia tamén a explicación do fenómeno da compartición falsa no paradigma de memoria compartida. Todos estes conceptos ilústranse con exemplos, que logo son analizados polos estudantes nas clases prácticas con exercicios similares. O proxecto resulta ser o mellor medio para afianzar estas competencias, xa que é unha aplicación paralela con certo grao de complexidade, na que os alumnos teñen que aplicar todos estes coñecementos/habilidades para obter resultados aceptables. Os criterios de avaliación do proxecto teñen en conta explícitamente estes aspectos.
Oportunidade 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. Neste apartado avalíanse de forma implícita ou explícita as seguintes competencias: CG4, TR1, RI1, RI6, RI7, RI8 e RI14, PROG1, PROG2, PROG3.
- Adquisición de coñecementos con OpenMP, MPI e CUDA (1.5p): valoráse o grado de coñecemento adquirido coa realización dalgúns exercicios propostos e a calidade dos mesmos. Neste apartado avalíanse de forma implícita ou explícita as seguintes competencias: TR1, TR3, RI6, RI8, RI14, PROG3.
- 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. Neste apartado avalíanse de forma implícita ou explícita as seguintes competencias: TR1, TR3, RI6, RI14.
- 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). Nese apartado avalíanse de forma implícita ou explícita as seguintes compotencias: CG9, TR1, TR2, TR3, RI1, RI7, RI14, PROG1, PROG2, PROG3
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.
Oportunidade de recuperación e convocatoria extraordinaria:
Os mesmos criterios de avaliación que na oportunidade ordinaria. O límite para a entrega do proxecto e prácticas é o día do exame oficial. Os alumnos farán unha presentación do proxecto o día do exame.
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 grado de asimilación da materia que van acadando as alumnas/os ao longo do cuadrimestre.
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.
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.
A entrega dos materiais do curso e as comunicacións electrónicas cos alumnos levarase a cabo coa ferramenta do campus virtual da USC.
Algúns temas e notas de clase están dispoñibles en Inglés.