G4011443 - Sistemas paralelos (Enxeñaría de Computadores) - Curso 2013/2014

Información

• Créditos ECTS
• Créditos ECTS: 4.50
• Total: 4.5
• Horas ECTS
• Clase Expositiva: 9.00
• Clase Interactiva Laboratorio: 28.00
• Horas de Titorías: 1.00
• Total: 38.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: 1º 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 principal obxectivo darlles a coñecer ás/aos alumnas/os a arquitectura dos sistemas con procesadores que operan de xeito paralelo, dende grandes supercomputadores e servidores, pasando por clústers e incluíndo tamén os multiprocesadores nun chip. Un aspecto fundamental é dar a coñecer os niveis conceptuais e tecnolóxicos que permitan entender a arquitectura dos sistemas actuais e a medio prazo. Outros obxectivos son dar a coñecer a interface coa capa software, e os fundamentos sobre rendemento e eficiencia neste tipo de sistemas.
Contidos
PROGRAMA

Para a distribución temporal de horas presenciais estimamos 9 horas de clase para teoría, 10 horas para resolución de cuestións e problemas e 18 para prácticas.

TEORÍA

Os catro primeiros temas describen diferentes aspectos hardware dos sistemas paralelos, polo que todos os temas presentan unha importancia semellante. O último tema trata os aspectos do rendemento e eficiencia en sistemas paralelos, que ten unha importancia menos significativa para os obxectivos da materia.

Tema 1: Contexto Tecnolóxico

O tema xustifica a necesidade dos sistemas paralelos, e mostra os diferentes niveis que é necesario estudar neste tipo de sistemas. Poñemos en contexto os conceptos que vamos a estudar mediante unha breve revisión da historia dos sistemas de altas prestacións, e dos datos que se poden obter da lista Top500 (en cada momento contén os 500 supercomputadores máis rápidos do mundo). Introduciremos un modelo simple para predicir a evolución dos nodos de computación na era dos procesadores multinúcleo, e rematamos o tema presentando algúns microprocesadores populares nos sistemas de computación de altas prestacións.

- Sistemas multiprocesador para problemas complexos: exemplos.
- Breve historia dos sistemas de altas prestacións: supercomputadores.
- Evolución dos sistemas paralelos: a lista Top500.
- Arquitectura dos nodos de procesamento: evolución e perspectivas.
- Procesadores comerciais para sistemas de computación de altas prestacións.

Dedicación en horas presenciais: 2 horas.


Tema 2: Topoloxías de Interconexión para Sistemas Multiprocesador

Neste tema iniciamos o estudo ao nivel de rede para a interconexión dos nodos de computación. En concreto estudamos as topoloxías de interconexión para sistemas de altas prestacións e as súa figuras de mérito. A topoloxía de rede é un aspecto fundamental neste tipo de sistemas.

- Bus, múltiple bus, medidas de prestacións.
- Redes baseadas en conmutadores: conmutador n x n.
- Redes multietapa bloqueantes baseadas en conmutadores: banyan, omega, bolboreta.
- Redes multietapa sen bloqueo por reconfiguración: rede de Benes.
- Redes multietapa non bloqueantes: Clos, fat tree.
- k-ary n-cubes (hipercubo, mallas e toros).
- Análise de topoloxías: ancho de banda, latencia, ancho de bisección, complexidade hardware, distancia media.

Dedicación en horas presenciais: 2 horas.


Tema 3: Arquitecturas Baseadas en Paso de Mensaxes

Neste tema completamos os estudo da rede de interconexión, cos algoritmos de encamiñamento e control de fluxo, o problema dos interbloqueos e a súa eliminación, e a implementación de todas estas técnicas nun conmutador actual para redes de altas prestacións. Outro aspecto importante que abordamos é o da interface coa rede para obter altas prestacións. Completamos a visión dun multiprocesador baseado en paso de mensaxes estudando os fundamentos do seu modelo de programación e un exemplo de interface co programador (MPI). Estudaremos exemplos de redes para clusters por medio da realización dun proxecto.


- Modelo de programación.
- Algoritmos de encamiñamento: determinista, sen información da rede e adaptativo.
- Implementación do encamiñamento: táboas de camiños e algorítmico.
- Control de fluxo: sen buffers (descarte, circuíto conmutado), con buffers de paquete (almacenar-enviar, enviar inmediato), con buffers para flits (burato de verme, canles virtuais).
- Arquitectura dun conmutador para control de fluxo con canles virtuais.
- Interbloqueos: eliminación en encamiñamento determinista e adaptativo. Teorema de Duato.
- Mensaxes de latencia infinita.
- Interfaces de rede eficientes para paso de mensaxes: especificación VIA (Infiniband).
- API de programación: MPI.
- Clusters. Exemplos de redes para clusters: Myrinet, Quadrics, Infiniband.
- Computación Grid.

Dedicación en horas presenciais: 2 horas.


Tema 4: Arquitecturas Multiprocesador con Memoria Compartida

Neste tema estúdanse os elementos hardware e software que se teñen que engadir a un sistema multiprocesador para facer que o mapa de memoria sexa único (memoria compartida por todos os procesadores). Profundizamos no estudo das implementación dos algoritmos de coherencia cache (xa introducidos na materia Arquitectura de Computadores), e as cuestións de sincronización. Ademais estudamos o modelo de consistencia cache implementado en OpenMP.

- Repaso de algoritmos de coherencia cache: algoritmo MESI.
- Detalles de implementación das variantes MESIF e MOESI.
- Sistemas NUMA con conexións punto a punto.
- Exemplos de implementación industriais.
- Sincronización: locks, fundamentos de memoria transaccional.
- Modelos de consistencia: exemplo en OpenMP.

Dedicación en horas presenciais: 2 horas.


Tema 5: Outros Conceptos Relevantes en Arquitecturas Multiprocesador

Este tema introduce os fundamentos teóricos para o estudo do rendemento e eficiencia dos sistemas paralelos. Estes aspectos poden ser útiles para a toma de decisións na configuración de grandes sistemas. Tamén se estudan aspectos no deseño para alto rendemento de sistemas de almacenamento paralelos, e os conceptos de fiabilidade, dispoñibilidade e mantemento en grandes sistemas de computación paralelos.

- Ganancia en velocidade (“speedup”).
- Eficiencia.
- Lei de Amdahl. Lei de Gustafson-Barsis.
- Isoeficiencia. Modelos para predicir a ganancia en velocidade.
- Deseño de sistemas de almacenamento paralelos de altas prestacións.
- Fiabilidade, dispoñibilidade e mantemento en grandes sistemas paralelos.

Dedicación en horas presenciais: 1 horas.


PRÁCTICAS

PRÁCTICA 1: deseño dun conxunto de programas de proba para medir as prestacións da rede dun supercomputador (Supercomputador Finisterrae do CESGA) e unha rede de estacións de traballo (a da propia aula de informática na que se realicen as prácticas). Tomaremos como referencia o conxunto de programas de proba para comunicacións con MPI “Pallas” (propiedade actualmente de Intel). Os programas estarán escritos en C utilizando a librería de MPI de uso libre MPICH.

PRÁCTICA 2: Simulación de redes de interconexión para multiprocesadores. Simularanse diferentes configuracións utilizando un simulador de uso libre, cambiando a topoloxía de rede, algoritmos de encamiñamento e parámetros asociados ao control de fluxo. Tomaranse medidas de ancho de banda (taxa de extracción da rede) e latencia dos paquetes. O/A alumno/a debe sacar as súas propias conclusións dos experimentos realizados, intentado obter dos datos a maior información posible dun xeito estruturado para caracterizar o comportamento deste tipo de redes.

Dedicación en horas presenciais. Práctica 1: 12 horas. Práctica 2 : 6 horas.

PROXECTOS (equipos de dúas ou tres alumnas/os): deseño dun clúster para computación paralela: análise da capacidade computacional/custo/espazo físico/potencia e software perseguindo o cumprimento dalgún obxectivo de deseño concreto (altas prestacións baixo calquera custo, boa relación custo-prestacións, boa relación custo-potencia, etc). Utilizarase internet para obter os datos dos diferentes compoñentes. Será necesario analizar polo menos dúas redes a elixir entre Myrinet, Quadrics ou Infiniband.


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

1- E. Antelo, “Arquitectura dos Sistemas Paralelos”. Dispoñible electrónicamente para os alumnos da materia.

Este libro está elaborado polo profesor expresamente para esta materia, e será a principal fonte de contidos.

Complementaria:

2- J. Dally and B.P. Towles, “Principles and Practices of Interconnection Networks”, Morgan Kaufmann, 2004.

Este libro constitúe a fonte fundamental para o estudo de redes de interconexión para redes de altas prestacións. Complementa e amplía abundantemente os contidos da referencia 1 nos contidos dos temas 2 e 3.

3- Patterson e Hennessy, "Computer Architecture. A Quantitative Approach", 5ª Edition, Morgan Kaufmann, 2011.

Referencia clásica nos cursos de arquitectura de computadores, este libro resulta útil para complementar á referencia 1 nos contidos do temas 1, 4 e 5. O máis interesante para esta materia é o capítulo 4 sobre multiprocesadores e paralelismo multifio.

4- H. El-Rewini et al. "Advanced Computer Architecture and Parallel Processing", Wiley 2005.

Este libro cubre algúns aspectos dos temas 2, 3, 4 e 5, e pode resultar de interese para complementar algúns aspectos da referencia 1.

Competencias
Contribuír a acadar as competencias recollidas na memoria do título de Grao en Enxeñería Informática na USC (CG4, CG6, CG9, CG11, TR1, TR2, TR3, FB5, RI1, RI9, RI14, TI2, TI5).


Competencias asociadas ao módulo de enxeñería de computadores dentro do grao:

- Coñecemento da arquitectura dos sistemas paralelos e distribuidos tando dende o punto de vista hardware e de implementación como dende o punto de vista da súa programación.
Metodoloxía da ensinanza
A metodoloxía de ensinanza que empregamos ten por obxectivo que o/a alumno/a participe de xeito activo no desenvolvemento da materia ao longo do cuadrimestre, buscando a máxima interacción co profesor e co resto de compañeiros. Para conseguir este obxectivo propoñemos os seguintes tipos de clases:

- Clases maxistrais: esta serán clases introdutorias para cada tema ao cargo do profesor, no que se fará fincapé nos aspectos máis relevantes do tema, orientando ao alumno nos aspectos fundamentais para a comprensión do tema. Segundo o tema dedicarase unha ou dúas horas (ver sección de contidos). Documentación: o alumno terá dispoñible na referencia 1 da bibliografía o material necesario para cada tema. O alumno terá coñecemento do calendario de clases maxistrais para que poida realizar unha lectura previa do tema.
- Clases de discusión do test: cada tema levará asociado un test con preguntas cortas, que pretende actuar de elemento motivador para o estudo do tema. Os alumnos deberán entregar o test antes do comezo da clase por calquera dos medios dispoñibles (papel ou electrónicamente). Nesta clase resolveranse as cuestións máis relevantes do test, preferiblemente coa intervención activa dos alumnos. O test estará dispoñible electrónicamente na USC virtual (incluíndo o material externo necesario, como por exemplo algún artigo).
- Clases de problemas: cada tema leva asociado un boletín de problemas. Os alumnos deben entregar os problemas resoltos antes do comezo da clase. Nesta clase resolveranse os problemas máis relevantes, preferiblemente por parte dos propios alumnos. Os problemas estarán dispoñibles electrónicamente na USC virtual (incluíndo o material externo necesario, como por exemplo algún artigo).
- Clases prácticas: os alumnos levarán a cabo as prácticas propostas, no número de sesións indicado para cada práctica. O traballo debe ser autónomo, e individual, buscando interactuar co profesor e o resto de compañeiros para a resolución de dúbidas e verificación de resultados. As primeiras sesións de prácticas estarán dedicadas a unha introdución a MPI, que é necesario para a realización da práctica 1. Combinarán breves explicacións das rutinas máis importantes coa realización de exercicios sinxelos, tanto na aula de informática como no supercomputador do CESGA. O material para estás prácticas, que estará dispoñible electrónicamente, será unha presentación coa explicación das rutinas de MPI, e un tutorial onde se indica paso a paso os aspectos prácticos para poder facer programas con MPI e correlos tanto na aula de informática como no supercomputador. Para a práctica 1, os alumnos terán a súa disposición, electrónicamente , o enunciado da práctica, tempo estimado para realizala e criterios de avaliación. Tamén estará dispoñible a documentación adicional necesaria: documento de Pallas describindo a metodoloxía utilizada no seu conxunto de programas de proba. Para a práctica 2, estará dispoñible electrónicamente o enunciado da práctica, o tempo estimado para realizala e os criterios de avaliación. Ademais estará dispoñible o manual do simulador de redes.

Posto que se espera que o alumno participe de xeito activo, necesitará coñecer con precisión o calendario para cada un dos diferentes tipos de clases. É fundamental que o alumno dispoña de tempo suficiente entre o momento do estudo do tema e as clases que marcan o límite para a entrega do test e os problemas. Como referencia terán como mínimo dúas semanas sempre entre as clases maxistrais dun tema e a corrección do test, e tres semanas antes da corrección dos problemas.


As titorías poderán ser presenciais (en horario de acordo cos alumnos ou segundo o fixe o centro, no despacho 22 do Departamento de Electrónica e Computación ou nas dependencias que fixe 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):

- Exame na data oficial ao final do cuadrimestre, na que se avalía mediante cuestións cortas os contidos estudados durante as clases de teoría. O alumno pode levar calquera material que desexe ao exame. Contribución: 3 puntos.
- Proxecto: na súa avaliación terase en conta o grado de elaboración do proxecto (opcións comparadas, criterios de selección), obxectivos cumpridos e presentación de resultados, en proporcionalidade ao número de integrantes do grupo que presenta o proxecto (máximo 3). Contribución: 2 puntos.
- Práctica 1: na súa avaliación terase en conta o número de programas de proba realizado (mínimo 3 e máximo 6), o grado de elaboración das conclusións do experimento e presentación de resultados. Contribución: 2 puntos.
- Práctica 2: na súa avaliación terase en conta o número de simulacións realizadas, a calidade e elaboración das conclusións das diferentes simulacións e presentación de resultados. O mínimo será a realización do primeiro apartado das prácticas (influenza dos algoritmos de encamiñamento no ancho de banda e a latencia). Contribución: 1 punto.
- Realización de test e problemas: terase en conta na súa avaliación o número de cuestións correctas levadas a cabo en cada test, e problemas resoltos correctamente. Acadarase a máxima puntuación neste apartado (2 puntos) entregando para cada test o 50% das cuestións, e para cada boletín dous problemas, en ámbolos dous casos resoltos de xeito correcto. Os alumnos que entreguen cuestións resoltas do test ou problemas, en número inferior a estes, obterán a cualificación proporcional á máxima. Os alumnos que entreguen un número superior de cuestións e problemas, poderán compensar (a contribución en nota será proporcional aos criterios dados para acadar a máxima nota) a nota do exame, de tal xeito que a suma da nota do exame a nota por entrega de exercicios non superará o 5, e a nota relativa sobre 10 do exame no debe ser inferior a 4 (equivalente a 1.2 na nota absoluta).


Para superar esta convocatoria son necesarios os seguintes mínimos: mínimo dunha contribución dun 1.2 no exame (4 sobre 10 na nota relativa de exame), e os mínimos indicados para as prácticas 1 e 2. A realización do proxecto non é estritamente obrigatoria para superar esta convocatoria.

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

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 excepto que o exame pasa a contar cun peso de 5 puntos e non se teñen en conta as contribucións por entrega de test e boletíns de problemas. 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 presentarse ao exame e non presentar ningunha práctica ou proxecto.


As titorías, a resolución de exercicios e casos prácticos na clase, e as 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: 22 horas, dedicadas á asimilacíon dos contidos teóricos.
- Escritura de exercicios, conclusións e outros traballos: 20.5 horas, fundamentalmente dedicadas á preparación dos problemas e exercicios e ao proxecto.
- Programación/experimentación: 10 horas, dedicadas á resolución das prácticas e preparación de resultados para a súa presentación.
- Actividades de avaliación: 15 horas, dedicadas á realización do exame e actividades adicionais relacionadas coa avaliación de prácticas, exercicios e proxecto.

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 elaboración e presentación de resultados de prácticas, problemas e exercicios.



Recomendacións para o estudo da materia
Resulta recomendable ter superadas (ou polo menos estudadas) as materias Arquitectura de Computadores e Enxeñería de Computadores, e coñecementos de programación en linguaxe C.

A realización dos exercicios propostos (test e problemas) en paralelo co desenvolvendo dos diferentes temas resulta decisiva para a asimilación dun xeito resolto e ordenado dos diferentes conceptos que se estudan.

Observacións
Os materiais do curso e as comunicacións electrónicas cos alumnos levarase a cabo coa ferramenta WebCT, como parte do campus virtual da USC.

A materia “Programación de Sistemas Multinúcleo e Multiprocesadores” constitúe o complemento perfecto desta materia.

A materia impártese en galego (clases e material).