Teaching Guides Query



Academic Year: 2021/22

439 - Bachelor's Degree in Informatics Engineering

30237 - Multiprocessors


Teaching Plan Information

Academic Year:
2021/22
Subject:
30237 - Multiprocessors
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
Degree:
439 - Bachelor's Degree in Informatics Engineering
ECTS:
6.0
Year:
3
Semester:
Second semester
Subject Type:
---
Module:
---

1. General information

1.1. Aims of the course

The course and its expected learning results respond to the following approaches and objectives:

  • To present simple code analysis techniques to determine if data parallelism exists.
  • To present a vector processor design (organization) that exploits this data parallelism.
  • Flynn's taxonomy. Classification of organizations according to their ability to exploit parallelism.
  • Analyze and understand the basic building blocks underlying the design of modern shared-memory multiprocessors.
  • Achieve the learning outcomes.

IMPORTANT: This course is not taught in English this year.

1.2. Context and importance of this course in the degree

This course completes the knowledge in the Degree in Computer Engineering related to the organization and architecture of computers in the context of Computer Engineering. The exploitation of parallelism, both vectorial and spatial (multiple processors) is in fact the basic lever of all complex digital systems in society: from cell phones to supercomputers, through all kinds of embedded systems, tablets, laptops, desktop computers or data center servers.

1.3. Recommendations to take this course

To take this course it is recommended to have taken Computer Architecture and Organization 2; Concurrent and Distributed Systems Programming; and Operating Systems.

2. Learning goals

2.1. Competences

Upon passing the course, the student will be more competent to...

  • Solve problems and make decisions with initiative, creativity and critical reasoning.
  • Use engineering techniques, skills and tools necessary for engineering practice.
  • Design and build digital systems, including computers, microprocessor-based systems, and communications systems.
  • Develop specific processors and embedded systems, as well as develop and optimize software for such systems.
  • Analyze and evaluate computer architectures, including parallel and distributed platforms, as well as develop and optimize software for them.
  • Analyze, evaluate and select the most appropriate hardware and software platforms for the support of embedded and real-time applications.
  • Analyze, evaluate, select and configure hardware platforms for the development and execution of computer applications and services.

2.2. Learning goals

The student, in order to pass this course, must demonstrate the following results...

  • Knows the multiprocessor families, identifies the main components of a multiprocessor and its functions. Understands coherence and consistency problems and their basic solutions. Knows the theory and practice of automatic parallelism extraction.
  • Knows the organization of commercial multiprocessors, both those integrated on a chip and those formed by several modules or boards, especially regarding memory and interconnection network.
  • Programs simple but multiprocessor-aware algorithms using a multiprocessor programming standard.

2.3. Importance of learning goals

It is clear that from the early stages of software analysis and design it will be necessary to incorporate parallel and/or distributed execution capabilities. For this purpose, it will be very important to know in some detail the possibilities and limitations of the basic technologies.

This course provides an understanding of the current and future landscape of parallel execution information processing platforms. Shared memory multiprocessors are a clear example of this technology. Its market penetration is and will be very large, since practically all commercial chips, for almost all segments, have versions with multiple processors on a single chip. In many cases these chips can be connected together to form large-scale multiprocessors.

Efficient programming, buying or selling multiprocessors, for example, will be of increasing importance in the activity of a computer engineer, and this course will provide the necessary knowledge to better develop these activities.

3. Assessment (1st and 2nd call)

3.1. Assessment tasks (description of tasks, marking system and assessment criteria)

The student must demonstrate that he has achieved the expected learning outcomes through the following assessment activities.

The evaluation will consist of three parts:

  • Defense of laboratory practical work (20 points).
  • Presentation of results on practical work (20 points).
  • Examination of theory and problems (60 points).

To pass the course the student must obtain at least 50 points out of the total and at least 24 points out of 60, that is to say, a 4 out of 10, in the exam. In the case of not achieving a 4 out of 10 in the exam, the student's grade in the call will coincide with the grade obtained in the exam.

The delivery of the results of laboratory practices and practical work will be done coinciding with the dates scheduled for the exam in each call.

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

Follow-up of the learning activities programmed in the course, by means of:

  • personalized correction of exercises proposed in class
  • tuition
  • personalized follow-up in the laboratory session

4.2. Learning tasks

The student will be able to achieve the expected results by doing the following activities:

  • Lectures
  • Problem-solving classes
  • Laboratory practices assistance
  • Practical non-presential work
  • Personalized tutorials on specific aspects
  • Study and personal work

4.3. Syllabus

Module I: Pipelined Vector Processors: Supercomputers
1. Introduction. parallelism

+ Numerical scientific problems
+ Performance of an addition of vectors by scalar processors

- Pipelined, superpipelined, and superscalar

+ Vector version of the vector addition.

2. Vector Extension of a ld/st architecture

+ Architecture and Organization

+ Basic instruction set (DLXV)

+ Organizations and pipelining

- Vector register file

- Functional units (ALUs)

- Multibank memory (synchronous and concurrent access)

+ Five organizations of vector processor and basic pipelining

+ Performance measures without strip mining: Rn, R∞, N½, Nv

+ ZV processor organization: a pipelined vector processor supporting DLXV

3. Two aspects of programming: vector length and vector stride

+ Vector length and strip mining

+ Two schemes for strip mining code generation. AXPY example

+ Performance with strip mining:

- Assembler example AXPY

- Rn, R∞, N½, Nv when processing noncontiguous elements of a vector (stride)

4. Conflicts in accessing memory banks

+ Introduction. Storage scheme. Fundamental property.

+ Tight Systems

+ Loose Systems

5. DLXV architecture: full instruction set

6. Vector Compilation = automatic extraction of vector operations

+ Introduction

+ Previous transformations that simplify dependency analysis

+ Analysis of dependencies. Dependency graph. Approximate tests

+ Architecture independent optimizations: rename, scalar expansion, vector copy

+ Vectorization

- Basic Procedure. Full vs. partial vectorization: loop distribution and loop exchange. Reduction

7. Final Thoughts: Amdahl's Law

8. Commercial Vector Processors

+ Introduction

+ Table of Supercomputers

+ Family NEC SX-4 and SX-9 ACE (it may change)

- Concept of partitioned data path

+ Vector Extensions Intel: from SSE to AVX512 (it may change)

Module II: Shared Memory Multiprocessors

1. Classification of parallel computers from M.J. Flynn

+ SISD, SIMD and MIMD

2. Objectives and problems of the MIMD machines

3. Simple model of H.S. Stone to distribute processes in processors

4. Shared-memory multiprocessors. Overview

+ Architecture-Programming: communication, synchronization, process creation

+ Organization: caches, interconnection network, main memory

5. Interconnection Network

+ Conflict, degradation, topology, cost, circuit switching or packet switching , performance, availability

+ Dynamic Topologies (indirect networks): bus, multibus, crossbar, multi-stage networks

+ Static Topologies (direct network): star, ring, mesh, tree, hypercube

6. Synchronization Mechanisms

+ Instruction set: Test & Set, Fetch & Op, Load Linked

+ Implementation. Combination of requests

+ Barriers

7. Parallel Compilation

+ Automatic extraction of parallel tasks

8. The problem of consistency

+ System, multiprocessor, multi-level cache, more examples

+ Copy-back and write-through

9. The memory model

+ Sequential consistency, pros and cons

+ A definition of consistency

10. coherence protocols based on diffusion

+ Invalidation. Diffusion vs. selective shipping

+ Examples of invalidation + CB + Bus: MSI, EI, Write Once, MESI

+ Snoopy protocols

11. Hierarchy of multilevel caches

12. coherence protocols based on directory

+ Hw requirements and some sample transactions

+ Simple protocol directory

13. Examples of current chip with more than one processor (core)

+ SUN, Intel, AMD, ARM, ...

4.4. Course planning and calendar

Schedule of sessions and labs:

Please see the academic calendar published by EINA.

Expected distribution of student work:

     Lectures: 30 hours
     Problems: 15 hours
     Labs: 15 hours
     Personal practice: 12 hours
     Personal study: 73 hours
     Rating: 5 hours


Curso Académico: 2021/22

439 - Graduado en Ingeniería Informática

30237 - Multiprocesadores


Información del Plan Docente

Año académico:
2021/22
Asignatura:
30237 - Multiprocesadores
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
Titulación:
439 - Graduado en Ingeniería Informática
Créditos:
6.0
Curso:
3
Periodo de impartición:
Segundo semestre
Clase de asignatura:
---
Materia:
---

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

  • Presentar técnicas sencillas de análisis de código para determinar si exite paralelismo de datos
  • Presentar un diseño de procesador vectorial (organización) que explote este paralelismo de datos
  • Taxonomía de Flynn. Clasificación del organizaciones de acuerdo a su capacidad para explotar el paralelismo
  • Analizar y comprender los bloques básicos que fundamentan el diseño de multiprocesadores de memoria compartida modernos
  • Alcanzar los resultados de aprendizaje

1.2. Contexto y sentido de la asignatura en la titulación

Esta asignatura completa los conocimientos en el Grado en Ingeniería Informática relativos a la organización y arquitectura de computadores en el contexto de la Ingeniería de Computadores. La explotación del paralelismo, tanto vectorial como espacial (múltiples procesadores) es de hecho la palanca básica de todos los sistemas digitales complejos en la sociedad: desde los teléfonos móviles a los supercompuatdores, pasando por todo tipo de sistemas empotrados, tablets, laptops, ordenadores de sobremesa o servidores de centros de datos.

1.3. Recomendaciones para cursar la asignatura

Para cursar esta asignatura se recomienda haber cursado la asignatura Arquitectura y Organización de Computadores 2; Programación de Sistemas Concurrentes y Distribuidos; y Sistemas Operativos.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para...

  • Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.
  • Usar las técnicas, habilidades y herramientas de la Ingeniería necesarias para la práctica de la misma.
  • Diseñar y construir sistemas digitales, incluyendo computadores, sistemas basados en microprocesador y sistemas de comunicaciones.
  • Desarrollar procesadores específicos y sistemas empotrados, así como desarrollar y optimizar el software de dichos sistemas.
  • Analizar y evaluar arquitecturas de computadores, incluyendo plataformas paralelas y distribuidas, así como desarrollar y optimizar software para las mismas.
  • Analizar, evaluar y seleccionar las plataformas hardware y software más adecuadas para el soporte de aplicaciones empotradas y de tiempo real.
  • Analizar, evaluar, seleccionar y configurar plataformas hardware para el desarrollo y ejecución de aplicaciones y servicios informáticos.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

  • Conoce las familias de multiprocesadores, identifica los componentes principales de un multiprocesador y sus funciones. Entiende los problemas de coherencia y consistencia y sus soluciones básicas. Conoce la teoría y la práctica de la extracción automática de paralelismo.
  • Conoce la organización de multiprocesadores comerciales, tanto los integrados en un chip como los formados por varios módulos o placas, especialmente en lo relativo a la memoria y la red de interconexión.
  • Programa algoritmos sencillos, pero conscientes de la organización del multiprocesador, mediante algún estándar de programación para multiprocesadores.

2.3. Importancia de los resultados de aprendizaje

Está claro que desde las primeras etapas de análisis y diseño de software va a ser necesario incorporar capacidades de ejecución paralela y/o distribuida. Para ello va a ser muy importante conocer con cierto grado de detalle las posibilidades y limitaciones de las tecnologías de base.

Esta asignatura permite comprender el panorama actual y futuro de las plataformas de procesado de información con ejecución paralela. Los multiprocesadores de memoria compartida son un ejemplo claro de esta tecnología.  Su penetración en el mercado es y va a ser muy grande, ya que prácticamente todos los chips comerciales, para casi todos los segmentos, tienen versiones con múltiples procesadores en un solo chip. En muchos casos estos chips se pueden conectar entre sí para formar multiprocesadores de gran escala.

Programar de forma eficiente; comprar o vender multiprocesadores, por ejemplo, va a tener una importancia creciente en la actividad de un ingeniero informático, y esta asignatura va a ofrecer los conocimientos necesarios para desarrollar mejor estas actividades.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluacion

La evaluación constará de tres partes:

  1. Defensa de las prácticas de laboratorio (20 puntos).
  2. Presentación de resultados sobre trabajo práctico no presencial (20 puntos).
  3. Examen de teoría y problemas (60 puntos).

Para superar la asignatura el alumno deberá obtener al menos 50 puntos sobre el total y al menos 24 puntos sobre 60, es decir, un 4 sobre 10, en el examen. En el caso de no alcanzar un 4 sobre 10 en el examen, la nota del alumno en la convocatoria coincidirá con la obtenida en dicho examen.

La entrega de resultados de prácticas de laboratorio y trabajo práctico no presencial se realizará coincidiendo con las fechas programadas para examen en cada convocatoria.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

Seguimiento de las actividades de aprendizaje programadas en la asignatura, mediante:

- correción personalizada de ejercicios propuesto en clase

- tutorías

- seguimiento personalizado en las sesiones de laboratorio

4.2. Actividades de aprendizaje

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

  • Clases magistrales.
  • Clases de resolución de problemas.
  • Prácticas de laboratorio asistidas.
  • Trabajo práctico no presencial.
  • Tutorías personalizadas sobre aspectos específicos
  • Estudio y trabajo personal.

4.3. Programa

Módulo I: Procesadores Vectoriales Segmentados: supercomputadores

1. Introducción. El paralelismo
+ Problemas científicos numéricos
+ Rendimiento de una suma de vectores en procesadores escalares
- Segmentado, supersegmentado y superescalar
+ Versión vectorial de la suma de vectores.
2. Extensión vectorial de una arquitectura ld/st
+ Arquitectura y Organización
+ Repertorio básico de instrucciones vectoriales
+ Organizaciones y Segmentación
- Banco de registros vectoriales
- Unidades funcionales (ALUs)
- Memoria multibanco (acceso síncrono y concurrente)
+ Cinco organizaciones de procesador vectorial y segmentación básica
+ Medidas de rendimiento sin seccionar: Rn, R∞, N½, Nv
+ Organización ZV: un procesador vectorial segmentado sencillo
3. Dos aspectos de programación: vector length y vector Stride
+ Vector length y seccionado (strip mining)
+ Dos esquemas de generación de código seccionado. Ejemplo AXPY
+ Rendimiento con seccionado:
- ejemplo AXPY en ensamblador
- Rn, R∞, N½, Nv
+ Procesado de elementos no contiguos de un vector (stride)
4. Conflictos en el acceso a bancos de memoria
+ Introducción. Esquema de almacenamiento. Propiedad fundamental.
+ Sistemas Ajustados
+ Sistemas Sobrados
5. Arquitectura DLXV: repertorio completo de instrucciones
6. Compilación vectorial = extracción automática de operaciones vectoriales
+ Introducción
+ Transformaciones previas que simplifican el análisis de dependencias
+ Análisis de dependencias. Grafo de dependencias. Tests aproximados
+ Optimizaciones independientes de la arquitectura: renombrar, expansión escalar, copia de vectores
+ Vectorización. Procedimiento básico. Vectorización parcial vs. total: distribución e intercambio de bucles. Reducción
7. Consideraciones finales: Ley de Amdhal
8. Procesadores Vectoriales Comerciales
+ Introducción
+ Tabla de Supercomputadores
+ Familia NEC: del SX-4 al SX-9 ACE (puede cambiar)
- Concepto de ruta de datos particionada
+ Extensiones vectoriales Intel: desde SSE hasta AVX512. Vigilancia Tecnológica.
Módulo II: Multiprocesadores Memoria Compartida
1. Clasificación de computadores paralelos según M.J. Flynn
+ SISD, SIMD y MIMD
2. Objetivos y problemas de las máquinas MIMD
3. Modelo sencillo de H.S. Stone para repartir procesos en procesadores
4. Multiprocesadores de Memoria compartida. Visión general
+ Arquitectura-Programación: comunicación, sincronización, creación de procesos
+ Organización: caches, red de interconexión, memoria principal
5. Red de interconexión
+ Conflicto, degradación, topología, coste, conmutación circuitos o de paquetes, prestaciones, disponibilidad
+ Topologías Dinámicas (redes indirectas): bus, multibus, crossbar, redes multietapa
+ Topologías Estáticas (redes directas): estrella, anillo, malla, árbol, hipercubo
6. Mecanismos de Sincronización
+ Repertorio de instrucciones: Test&Set, Fetch&Op, Linked Load
+ Implementación. Combinación de peticiones
+ Barreras
7. Compilación paralela
+ extracción automática de tareas paralelas
8. El problema de la coherencia
+ sistema, multiprocesador, cache multinivel, más ejemplos
+ escritura retardada e inmediata (animaciones)
9. El modelo de memoria
+ consistencia secuencial, pros y contras
+ una definición de coherencia
10. Protocolos de coherencia basados en difusión
+ Invalidación. Difusión vs. envío selectivo
+ ejemplos invalidación + CB + Bus: MSI, EI, Write Once, MESI
+ Protocolos comerciales
11. Jerarquía de caches multinivel
12. Protocolos de coherencia basados en directorio
+ requisitos hw y algunos transacciones de ejemplo
+ protocolo sencillo de directorio
13. Ejemplos de chips actuales con más de un procesador (core)
+ SUN, Intel, AMD, ARM, ...
 

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Calendario de sesiones presenciales y presentación de trabajos

Se concretará cuando se apruebe el calendario académico.

Trabajo del estudiante

  • clases magistrales:                  30 horas
  • clases de problemas:               15 horas
  • clases de prácticas:                 15 horas
  • trabajo práctico no presencial:  12 horas
  • estudio personal:                     73 horas
  • evaluación:                             5 horas

 

La asignatura se compone de clases magistrales, clases de problemas, prácticas de laboratorio y trabajo práctico no presencial.

El calendario detallado de las diversas actividades a desarrollar se establecerá una vez que la Universidad haya aprobado el calendario académico del curso correspondiente. En cualquier caso, las fechas de las diferentes actividades serán anunciadas con suficiente antelación en la plataforma de apoyo a la enseñanza presencial Moodle 2 del Anillo Digital Docente (http://add.unizar.es) de la Universidad.