## 30237 - Multiprocessors

### Syllabus Information

2020/21
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:
---

### 4.1. Methodological overview

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

• corrección personalizada de ejercicios propuesto en clase
• tutorías
• seguimiento personalizado en las sesiones de laboratorio

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 (may change)

- Concept of partitioned data path

+ Vector Extensions Intel: from SSE to AVX512 (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

+ 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:

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

### 4.5. Bibliography and recommended resources

[BB Bibliografía básica] BB Computer architecture : a quantitative approach / John Hennessy, David A. Patterson ; with contributions by Andrea C. Arpaci-Dusseau ... [et al.] . 4th ed. San Francisco : Morgan Kaufmann, 2007 BB Culler, David E.. Parallel Computer Architecture : A Hardware-Software Approach / David E. Culler, Jaswinder Pal Singh ; with Anoop Gupta . - [1st ed.] San Francisco : Morgan Kaufmann, cop. 1999 BB Dally, William James. Principles and practices of interconnection networks / William James Dally, Brian Towles San Francisco : Morgan Kaufmann, cop. 2004 BB Patterson, David A.. Computer organization and desing : the hardware, software interface / David A. Patterson, John L. Hennessy ; with contributions by Perry Alexander ... [et al.] . 5th ed. Amsterdam : Elsevier : Morgan Kaufmann, cop. 2014

### Información del Plan Docente

2020/21
Asignatura:
110 - Escuela de Ingeniería y Arquitectura
Titulación:
Créditos:
6.0
Curso:
3
Periodo de impartición:
Segundo semestre
Clase de asignatura:
---
Materia:
---

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

Esta asignatura completa los conocimientos 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.

### 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.

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.

#### 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 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.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.1. Presentación metodológica general

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

- correción personalizada de ejercicios propuesto en clase

- tutorías

- seguimiento personalizado en las sesiones de laboratorio

#### 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

1. Introducción. El paralelismo
+ Problemas científicos numéricos
+ Rendimiento de una suma de vectores en procesadores escalares
+ 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
- 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
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
- 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.
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
+ Introducción
+ 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.
1. Clasificación de computadores paralelos según M.J. Flynn
+ SISD, SIMD y MIMD
2. Objetivos y problemas del 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
+ 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, mas 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.

### 4.5. Bibliografía y recursos recomendados

[BB: Bibliografía básica / BC: Bibliografía complementaria]

• [BB] John Hennessy, David A. Patterson. Computer architecture: a quantitative approach. 5th ed. San Francisco : Morgan Kaufmann, 2012.
• [BB] Culler, Singh, and Gupta. Parallel Computer Architecture : A Hardware-Software Approach, 1st ed. San Francisco : Morgan Kaufmann, cop. 1999
• [BB] Dally and Towles. Principles and practices of interconnection networks: Morgan Kaufmann, cop. 2004
• [BC] Patterson and Hennessy. Computer organization and desing: the hardware, software interface. 5th ed. Morgan Kaufmann. 2014
• [BC] Sorin, Hill, and Wood, A primer on memory consistency and cache coherence. Synthesis Lectures on Computer Architecture, Morgan & Claypool Publishers, 2011.
• [BB] Dubois, M. Annavaram, and Stenström. Parallel Computer Organization and Design, Cambridge University Press, 2012.