UC3M _ Doble Grado Ingeniería Informática y ADE _ Arquitectura de Computadores _ Arquitectu

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Arquitectura de Computadores/Ejercicios de Repaso/LEER.txtVer en clase. No los puedo compartir públicamente.
Arquitectura de Computadores/Examen Ordinario 2015-2016/ordinario-2016-sol.pdf
Arquitectura de Computadores/TEMA 1/Ejercicios Amdahl.pdf
Ejercicio 1 
Se dispone de una aplicación que realiza durante el 80% del tiempo cómputo y durante 
el 20% restante operaciones de E/S a disco. 
 Desarrollar una nueva versión de la aplicación que pueda ejecutar en un 
procesador de 8 núcleos. Se asume que el 90% de la parte de cómputo es 
paralelizable. 
 Sustituir el disco magnético por un disco SSD de mayor velocidad. 
 
a) Determine cuál debe ser la aceleración del nuevo disco con respecto al original 
para que compense la sustitución del disco en vez de la adquisición de 
procesador de 8 núcleos. Tenga en cuenta que el incremento de núcleos 
solamente afecta al cómputo. 
b) Asuma que el programa se puede paralelizar para cualquier número de 
procesadores y que la parte paralelizable es siempre el 90% de la parte de 
cómputo. Si la aceleración máxima de la parte de E/S a disco es 4. ¿Cuántos 
procesadores sería necesarios para alcanzar una aceleración global de 5? Tenga 
en cuenta que la aceleración global incluye cómputo y E/S. 
 
 
 
Ejercicio 2 
Se dispone de un computador con un solo núcleo que ejecuta una aplicación de 
evaluación de riesgos financieros. Esta aplicación es intensiva en cálculo, a lo que 
dedica el 90 % del tiempo. El 10 % restante lo dedica a esperar en operaciones de 
entrada/salida a disco. 
Del tiempo que la aplicación pasa ejecutando instrucciones de cálculo un 75 % 
del tiempo lo pasa ejecutando operaciones en coma flotante y un 25 % lo pasa 
ejecutando otras instrucciones. La ejecución de una instrucción de coma flotante 
requiere como promedio 12 CPI. El resto de instrucciones requieren como promedio 
4 CPI. 
Se está valorando la migración de esta aplicación a las siguientes alternativas, 
que no incorporan ninguna mejora para el tiempo de las operaciones de 
entrada/salida a disco: 
■ Alternativa A: Un procesador con un solo núcleo y con una frecuencia de reloj 
un 50 % más alta que la de la máquina original en el que las instrucciones de coma 
flotante requieren un 10 % más de ciclos por instrucción y el resto de 
instrucciones requieren un 25% más de ciclos por instrucción. 
■ Alternativa B: Un procesador con cuatro núcleos y con una frecuencia de reloj 
un 50% más baja que la de la máquina original, en el que las instrucciones de 
coma flotante requieren un 20 % menos de ciclos de reloj y el resto de 
instrucciones los mismos ciclos de reloj. 
Se pide responder de forma justificada a las siguientes cuestiones: 
1. ¿Cuál será la aceleración/deceleración global de la aplicación en el caso A? 
2. ¿Cuál será la aceleración/deceleración global de la aplicación en el caso B si se 
asume que la parte de cálculo es totalmente paralelizable mientras la 
entrada/salida no admite ningún tipo de paralelización? 
 
Arquitectura de Computadores/TEMA 2/es-m6-01-openmp-lect.pdf
Programación paralela con OpenMP
Programación paralela con OpenMP
Arquitectura de Computadores
J. Daniel García Sánchez (coordinador)
David Expósito Singh
Javier García Blas
J. Manuel Pérez Lobato
Grupo ARCOS
Departamento de Informática
Universidad Carlos III de Madrid
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 1/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 2/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
¿Qué es OpenMP?
Es un API (y un conjunto de directivas) para expresar
aplicaciones paralelas en sistemas de memoria
compartida.
Componentes:
Directivas de compilador.
Funciones de biblioteca.
Variables de entorno.
Simplifica la forma de escribir programas paralelos.
Mappings para FORTRAN, C y C++.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 3/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Construcciones
Directivas:
#pragma omp directiva [clausulas]
Ejemplo: Fijar el número de hilos.
#pragma omp parallel num_threads(4)
Funciones de biblioteca
#include <omp.h> // Incluir para llamar funciones OpenMP
ejemplo: Obtener el número de hilos usado.
int n = omp_get_num_threads();
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 4/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Construcciones
Directivas:
#pragma omp directiva [clausulas]
Ejemplo: Fijar el número de hilos.
#pragma omp parallel num_threads(4)
Funciones de biblioteca
#include <omp.h> // Incluir para llamar funciones OpenMP
ejemplo: Obtener el número de hilos usado.
int n = omp_get_num_threads();
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 4/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Ejercicio 1: Secuencial
exseq.cpp
#include <iostream>
int main() {
using namespace std;
int id = 0;
cout << "Hola(" << id << ") " ;
cout << "Mundo(" << id << ")";
return 0;
}
Imprime en salida estándar.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 5/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Ejercicio 1: Paralelo
exseq.cpp
#include <iostream>
#include <omp.h>
int main() {
using namespace std;
#pragma omp parallel
{
int id = omp_get_thread_num();
cout << "Hola(" << id << ") " ;
cout << "Mundo(" << id << ")";
}
return 0;
}
Flags de compilación:
gcc: -fopenmp
Intel Linux: -openmp
Intel Windows:
/Qopenmp
Microsft Visual Studio:
/openmp
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 6/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Ejercicio 1
Objetivo: Verificar que el entorno funciona.
Actividades:
1 Compilar la versión secuencial y ejecutar.
2 Compilar la versión paralela y ejecutar.
3 Introduzca la función omp_get_num_threads() para
imprimir el número de hilos:
a) Antes del pragma.
b) Justo después del pragma.
c) Dentro del bloque.
d) Antes de salir del programa, pero fuera del bloque.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 7/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Ejercicio 1
Objetivo: Verificar que el entorno funciona.
Actividades:
1 Compilar la versión secuencial y ejecutar.
2 Compilar la versión paralela y ejecutar.
3 Introduzca la función omp_get_num_threads() para
imprimir el número de hilos:
a) Antes del pragma.
b) Justo después del pragma.
c) Dentro del bloque.
d) Antes de salir del programa, pero fuera del bloque.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 7/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Observaciones
Modelo de memoria compartida multi-hilo.
Comunicación mediante variables compartidas.
Compartición accidental→ condiciones de carrera.
Resultado dependiente de la planificación de los hilos.
Evitar condiciones de carrera.
Sincronización para evitar conflictos.
Coste de sincronización.
Modificación en patrón de accesos.
Minimizar sincronizaciones necesarias.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 8/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Observaciones
Modelo de memoria compartida multi-hilo.
Comunicación mediante variables compartidas.
Compartición accidental→ condiciones de carrera.
Resultado dependiente de la planificación de los hilos.
Evitar condiciones de carrera.
Sincronización para evitar conflictos.
Coste de sincronización.
Modificación en patrón de accesos.
Minimizar sincronizaciones necesarias.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 8/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Introducción
Observaciones
Modelo de memoria compartida multi-hilo.
Comunicación mediante variables compartidas.
Compartición accidental→ condiciones de carrera.
Resultado dependiente de la planificación de los hilos.
Evitar condiciones de carrera.
Sincronización para evitar conflictos.
Coste de sincronización.
Modificación en patrón de accesos.
Minimizar sincronizaciones necesarias.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 8/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 9/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Paralelismo fork-join
Aplicación secuencial con secciones paralelas:
Hilo maestro: Iniciado con el programa principal.
En una sección paralela se arranca un conjunto de hilos.
Se puede anidar el paralelismo.
Una región paralela es un bloque marcado con la directiva
parallel.
#pragama omp parallel
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 10/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Paralelismo fork-join
Aplicación secuencial con secciones paralelas:
Hilo maestro: Iniciado con el programa principal.
En una sección paralela se arranca un conjunto de hilos.
Se puede anidar el paralelismo.
Una región paralela es un bloque marcado con la directiva
parallel.
#pragama omp parallel
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 10/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Selección del número de hilos
Invocando a una función
de biblioteca.
Ejemplo
// ...
omp_set_num_threads(4);
#pragma omp parallel
{
// Región paralela
}
Directiva OpenMP.
Ejemplo
// ...
#pragma omp parallel num_threads(4)
{
// Región paralela
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 11/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Selección del número de hilos
Invocando a una función
de biblioteca.
Ejemplo
// ...
omp_set_num_threads(4);
#pragma omp parallel
{
// Región paralela
}
Directiva OpenMP.
Ejemplo
// ...
#pragma omp parallel num_threads(4)
{
// Región paralela
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 11/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Ejercicio 2: Cálculo de π
Cálculo de π.
π =
∫ 1
0
4
1 + x2
dx
Aproximación:
π ≈
N∑
i=0
F (xi)∆x
Suma del área de N rectángulos.
Base: ∆x .
Altura: F (xi ).
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 12/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Ejercicio 2: Cálculo de π
Cálculo de π.
π =
∫ 1
0
4
1 + x2
dx
Aproximación:
π ≈
N∑
i=0
F (xi)∆x
Suma del área de N rectángulos.
Base: ∆x .
Altura: F (xi ).
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 12/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Ejercicio 2: Versión secuencial
Cálculo de π
#include <iostream>
#include <iomanip>
#include <chrono>
int main() {
using namespace std;
using namespace std::chrono;
constexpr long nsteps = 10000000;
double step = 1.0 / double(nsteps);
using clk = high_resolution_clock;
auto t1 = clk :: now();
double sum = 0.0;
for ( int i=0;i<nsteps; ++i) {
double x = (i+0.5) ∗ step;
sum += 4.0 / (1.0 + x ∗ x) ;
}
double pi = step ∗ sum;
auto t2 = clk :: now();
auto diff = duration_cast<microseconds>(t2−t1);
cout << "PI= " << setprecision(10) << pi << endl;
cout << "Tiempo= " << diff .count() << "us" << endl;
return 0;
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 13/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Medición del tiempo en C++11
Ficheros de include:
#include <chrono>
Tipo para el reloj:
using clk = chrono::high_resolution_clock;
Obtener un punto del tiempo:
auto t1 = clk :: now();
Diferencias de tiempo (puede especificar unidad).
auto diff = duration_cast<microseconds>(t2−t1);
Obtención del valor de la diferencia.
cout << diff .count() ;
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 14/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Ejemplo de medida de tiempo
Ejemplo
#include <chrono>
void f () {
using namespace std;
using namespace std::chrono;
using clk = chrono::high_resolution_clock;
auto t1 = clk :: now();
g() ;
auto t2 = clk :: now();
auto diff = duration_cast<microseconds>(t2−t1);
cout << "Time= " << diff .count << "microseconds" << endl;
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 15/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Medición de tiempo en OpenMP
Punto del tiempo.
double t1 = omp_get_wtime();
Diferencia de tiempo.
double t1 = omp_get_wtime();
double t2 = omp_get_wtime();
double diff = t2−t1;
Diferencia de tiempo entre 2 ticks sucesivos:
double tick = omp_get_wtick();
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 16/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Hilos en OpenMP
Ejercicio 2
Crear una versión paralela del programa de cálculo de π
usando una clausula parallel.
Observaciones:
Incluya mediciones de tiempo.
Imprima el número de hilos que se están usando.
Tenga cuidado con las variables compartidas.
Idea: Use un array y acumule una suma parcial en cada
hilo en la región paralela.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 17/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 18/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
Mecanismos de sincronización
Sincronización: Mecanismo usado para establecer
restricciones sobre el orden de acceso a datos
compartidos.
Objetivo: Evitar carreras de datos.
Alternativas:
Alto nivel: critical, atomic, barrier, ordered.
Bajo nivel: flush, cerrojos.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 19/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
Mecanismos de sincronización
Sincronización: Mecanismo usado para establecer
restricciones sobre el orden de acceso a datos
compartidos.
Objetivo: Evitar carreras de datos.
Alternativas:
Alto nivel: critical, atomic, barrier, ordered.
Bajo nivel: flush, cerrojos.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 19/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
critical
Garantiza exclusión mutua.
Solamente un hilo a la vez puede entrar en la región
crítica.
Ejemplo
#pragma omp parallel
{
for ( int i=0;i<max;++i) {
x = f ( i ) ;
#pragma omp critical
g(x) ;
}
Las llamadas a f() se realiza en
paralelo.
Solamente un hilo puede entrar a la
vez en g().
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 20/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
critical
Garantiza exclusión mutua.
Solamente un hilo a la vez puede entrar en la región
crítica.
Ejemplo
#pragma omp parallel
{
for ( int i=0;i<max;++i) {
x = f ( i ) ;
#pragma omp critical
g(x) ;
}
Las llamadas a f() se realiza en
paralelo.
Solamente un hilo puede entrar a la
vez en g().
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 20/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
atomic
Garantiza la actualización atómica de una posición de
memoria.
Evita carrera de datos en actualización a variable
Ejemplo
#pragma omp parallel
{
for ( int i=0;i<max;++i) {
x = f ( i ) ;
#pragma omp atomic
s += g(x)
}
Las llamadas a f() se realiza en
paralelo.
Las actualizaciones a s son
thread-safe.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 21/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
atomic
Garantiza la actualización atómica de una posición de
memoria.
Evita carrera de datos en actualización a variable
Ejemplo
#pragma omp parallel
{
for ( int i=0;i<max;++i) {
x = f ( i ) ;
#pragma omp atomic
s += g(x)
}
Las llamadas a f() se realiza en
paralelo.
Las actualizaciones a s son
thread-safe.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 21/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización
Ejercicio 3
Modifique su programa del ejercicio 2.
Evalúe:
a) Sección crítica.
b) Acceso atómico.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 22/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 23/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Parallel for
División de bucle: Realiza una partición de las
iteraciones de un bucle entre los hilos disponible.
Sintaxis
#pragma omp parallel
{
#pragma omp for
for ( i=0; i<n; ++i) {
f ( i ) ;
}
}
omp for→ División de bucle for.
Se generar una copia privada de i
para cada hilo.
Se puede hacer también con
private(i)
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 24/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Parallel for
División de bucle: Realiza una partición de las
iteraciones de un bucle entre los hilos disponible.
Sintaxis
#pragma omp parallel
{
#pragma omp for
for ( i=0; i<n; ++i) {
f ( i ) ;
}
}
omp for→ División de bucle for.
Se generar una copia privada de i
para cada hilo.
Se puede hacer también con
private(i)
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 24/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Ejemplo
Código secuencial
for ( i=0;i<max;++i) { u[ i ] = v[ i ] + w[i ]; }
Región paralela
#pragma omp parallel
{
int id = omp_get_thread_num();
int nthreads = omp_get_num_threads();
int istart = id ∗ max / nthreads;
int iend = ( id==nthreads−1) ?
(( id + 1) ∗ max / nthreads):max;
for ( int i= istart ; i<iend;++i)
{ u[ i ] = v[ i ] + w[i ]; }
}
Región paralela + Bucle
paralelo
#pragma omp parallel
#pragma omp for
for ( i=0;i<max;++i)
{ u[ i ] = v[ i ] + w[i ]; }
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 25/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Ejemplo
Código secuencial
for ( i=0;i<max;++i) { u[ i ] = v[ i ] + w[i ]; }
Región paralela
#pragma omp parallel
{
int id = omp_get_thread_num();
int nthreads = omp_get_num_threads();
int istart = id ∗ max / nthreads;
int iend = ( id==nthreads−1) ?
(( id + 1) ∗ max / nthreads):max;
for ( int i= istart ; i<iend;++i)
{ u[ i ] = v[ i ] + w[i ]; }
}
Región paralela + Bucle
paralelo
#pragma omp parallel
#pragma omp for
for ( i=0;i<max;++i)
{ u[ i ] = v[ i ] + w[i ]; }
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 25/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Ejemplo
Código secuencial
for ( i=0;i<max;++i) { u[ i ] = v[ i ] + w[i ]; }
Región paralela
#pragma omp parallel
{
int id = omp_get_thread_num();
int nthreads = omp_get_num_threads();
int istart = id ∗ max / nthreads;
int iend = ( id==nthreads−1) ?
(( id + 1) ∗ max / nthreads):max;
for ( int i= istart ; i<iend;++i)
{ u[ i ] = v[ i ] + w[i ]; }
}
Región paralela + Bucle
paralelo
#pragma omp parallel
#pragma omp for
for ( i=0;i<max;++i)
{ u[ i ] = v[ i ] + w[i ]; }
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 25/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Construcción combinada
Se puede usar una forma abreviada combinando las dos
directivas.
Dos directivas
vector<double> vec(max);
#pragma omp parallel
{
#pragma omp for
for ( i=0; i<max; ++i) {
vec[ i ] = generate(i) ;
}
}
Directiva combinada
vector<double> vec(max);
#pragma omp parallel for
for ( i=0; i<max; ++i) {
vec[ i ] = generate(i) ;
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 26/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Construcción combinada
Se puede usar una forma abreviada combinando las dos
directivas.
Dos directivas
vector<double> vec(max);
#pragma omp parallel
{
#pragma omp for
for ( i=0; i<max; ++i) {
vec[ i ] = generate(i) ;
}
}
Directiva combinada
vector<double> vec(max);
#pragma omp parallel for
for ( i=0; i<max; ++i) {
vec[ i ] = generate(i) ;
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 26/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Construcción combinada
Se puede usar una forma abreviada combinando las dos
directivas.
Dos directivas
vector<double> vec(max);
#pragma omp parallel
{
#pragma omp for
for ( i=0; i<max; ++i) {
vec[ i ] = generate(i) ;
}
}
Directiva combinada
vector<double> vec(max);
#pragma omp parallel for
for ( i=0; i<max; ++i) {
vec[ i ] = generate(i) ;
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 26/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Reducciones
Ejemplo
double sum = 0.0;
vector<double> v(max);
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Una reducción es una operación de
acumulación en un bucle.
Clausula de reducción: reduction
(op:var)
Efectos:
Copia privada de
cada variable.
Actualización de
copia local en cada
iteración.
Copias locales
combinadas al final.
Ejemplo
double sum = 0.0;
vector<double> v(max);
#pragma omp parallel for reduction(+:suma)
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 27/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Reducciones
Ejemplo
double sum = 0.0;
vector<double> v(max);
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Una reducción es una operación de
acumulación en un bucle.
Clausula de reducción: reduction
(op:var)
Efectos:
Copia privada de
cada variable.
Actualización de
copia local en cada
iteración.
Copias locales
combinadas al final.
Ejemplo
double sum = 0.0;
vector<double> v(max);
#pragma omp parallel for reduction(+:suma)
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 27/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Reducciones
Ejemplo
double sum = 0.0;
vector<double> v(max);
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Una reducción es una operación de
acumulación en un bucle.
Clausula de reducción: reduction
(op:var)
Efectos:
Copia privada de
cada variable.
Actualización de
copia local en cada
iteración.
Copias locales
combinadas al final.
Ejemplo
double sum = 0.0;
vector<double> v(max);
#pragma omp parallel for reduction(+:suma)
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Arquitectura de
Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 27/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Reducciones
Ejemplo
double sum = 0.0;
vector<double> v(max);
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Una reducción es una operación de
acumulación en un bucle.
Clausula de reducción: reduction
(op:var)
Efectos:
Copia privada de
cada variable.
Actualización de
copia local en cada
iteración.
Copias locales
combinadas al final.
Ejemplo
double sum = 0.0;
vector<double> v(max);
#pragma omp parallel for reduction(+:suma)
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 27/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Reducciones
Ejemplo
double sum = 0.0;
vector<double> v(max);
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Una reducción es una operación de
acumulación en un bucle.
Clausula de reducción: reduction
(op:var)
Efectos:
Copia privada de
cada variable.
Actualización de
copia local en cada
iteración.
Copias locales
combinadas al final.
Ejemplo
double sum = 0.0;
vector<double> v(max);
#pragma omp parallel for reduction(+:suma)
for ( int i=0; i<max; ++i) {
suma += v[i];
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 27/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Operaciones de reducción
Operaciones que son asociativas.
(a⊕ b)⊕ c = a⊕ (b ⊕ c)
Valor inicial definido por la operación.
Operadores básicos:
+ (valor inicial: 0).
* (valor inicial: 1).
- (valor inicial: 0).
Operadores avanzados:
& (valor inicial: 0).
| (valor inicial: 0).
ˆ (valor inicial: 0).
&& (valor inicial: 1).
|| (valor inicial: 0).
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 28/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Operaciones de reducción
Operaciones que son asociativas.
(a⊕ b)⊕ c = a⊕ (b ⊕ c)
Valor inicial definido por la operación.
Operadores básicos:
+ (valor inicial: 0).
* (valor inicial: 1).
- (valor inicial: 0).
Operadores avanzados:
& (valor inicial: 0).
| (valor inicial: 0).
ˆ (valor inicial: 0).
&& (valor inicial: 1).
|| (valor inicial: 0).
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 28/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Operaciones de reducción
Operaciones que son asociativas.
(a⊕ b)⊕ c = a⊕ (b ⊕ c)
Valor inicial definido por la operación.
Operadores básicos:
+ (valor inicial: 0).
* (valor inicial: 1).
- (valor inicial: 0).
Operadores avanzados:
& (valor inicial: 0).
| (valor inicial: 0).
ˆ (valor inicial: 0).
&& (valor inicial: 1).
|| (valor inicial: 0).
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 28/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Bucles paralelos
Ejercicio 4
Modifique el programa de cálculo de π.
Intente que el programa sea lo más parecido posible al
programa secuencial.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 29/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 30/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Barreras
Permite sincronizar todos los hilos en un punto.
Se espera hasta que todos los puntos llegan a la barrera.
Ejemplo
#pragma omp parallel
{
int id = omp_get_thread_num();
v[ id ] = f ( id ) ;
#pragma omp barrier
#pragma omp for
for ( int i=0;i<max;++i) {
w[i ] = g( i ) ;
} // Barrera implí cita
#pragma omp for nowait
for ( int i=0;i<max;++i) {
w[i ] = g( i ) ;
} // nowait −> No hay barrera implícita
v[ i ] = h( i ) ;
} // Barrera implí cita
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 31/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Ejecución única: master
La clausula master marca un bloque que solamente se
ejecuta en el hilo maestro.
Ejemplo
#pragma omp parallel
{
f () ; // En todos los hilos
#pragma omp master
{
g() ; // Solamente en maestro
h() ; // Solamente en maestro
}
i () ; // En todos los hilos
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 32/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Ejecución única: single
La clausula single marca un bloque que solamente se
ejecuta en un hilo.
No tiene por qué ser el hilo maestro.
Ejemplo
#pragma omp parallel
{
f () ; // En todos los hilos
#pragma omp single
{
g() ; // Solamente en algún hilo
h() ; // Solamente en algún hilo
}
i () ; // En todos los hilos
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 33/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Ordenación
Una región ordered se ejecuta en orden secuencial.
Ejemplo
#pragma omp parallel
{
#pragma omp for ordered reduction(+:res)
for ( int i=0;i<max;++i) {
double tmp = f(i) ;
#pragma ordered
res += g(tmp);
}
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 34/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Cerrojos simples
Cerrojos de la biblioteca OpenMP.
También hay cerrojos anidados.
Ejemplo
omp_lock_t l;
omo_init_lock(&l);
#pragma omp parallel
{
int id = omp_get_thread_num();
double x = f( i ) ;
omp_set_lock(&l);
cout << "ID=" << id << " tmp= " << tmp << endl;
omp_unset_lock(&l);
}
omp_destroy_lock(&l);
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 35/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Otras funciones de biblioteca
Cerrojos anidados:
omp_init_nest_lock(), omp_set_nest_lock(),
omp_unset_nest_lock(), omp_test_next_lock(),
omp_destroy_nest_lock().
Consulta de procesadores:
omp_num_procs().
Número de hilos:
omp_set_num_threads(), omp_get_num_threads(),
omp_get_thread_num(), omp_get_max_threads().
Comprobación de región paralela:
omp_in_parallel().
Selección dinámica de número de hilos:
omp_set_dynamic(), omp_get_dynamic().
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 36/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Sincronización con master
Variables de entorno
Número de hilos por defecto:
OMP_NUM_THREADS
Modo de planificación:
OMP_SCHEDULE
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 37/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 38/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
Atributos de almacenamiento
Modelo de programación en memoria compartida:
Variables compartidas.
Variables privadas.
Compartidas:
Variables globales (alcance de fichero y espacio de
nombres).
Variables static.
Objetos en memoria dinámica (malloc() y new).
Privadas:
Variables locales de funciones invocadas desde una región
paralela.
Variables locales definidas dentro de un bloque.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 39/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
Atributos de almacenamiento
Modelo de programación en memoria compartida:
Variables compartidas.
Variables privadas.
Compartidas:
Variables globales (alcance de fichero y
espacio de
nombres).
Variables static.
Objetos en memoria dinámica (malloc() y new).
Privadas:
Variables locales de funciones invocadas desde una región
paralela.
Variables locales definidas dentro de un bloque.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 39/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
Atributos de almacenamiento
Modelo de programación en memoria compartida:
Variables compartidas.
Variables privadas.
Compartidas:
Variables globales (alcance de fichero y espacio de
nombres).
Variables static.
Objetos en memoria dinámica (malloc() y new).
Privadas:
Variables locales de funciones invocadas desde una región
paralela.
Variables locales definidas dentro de un bloque.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 39/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
Modificación de atributos de almacenamiento
Atributos en clausulas paralelas:
shared.
private.
firstprivate.
private crea una nueva copia local por hilo.
El valor de las copias no se inicializa.
Ejemplo
void f () {
int x = 17;
#pragma omp parallel for private(x)
for ( int i=0;i<max;++i) {
x += i ; // x inicialmente vale 17
}
cout << x << endl; // x==17
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 40/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
Modificación de atributos de almacenamiento
Atributos en clausulas paralelas:
shared.
private.
firstprivate.
private crea una nueva copia local por hilo.
El valor de las copias no se inicializa.
Ejemplo
void f () {
int x = 17;
#pragma omp parallel for private(x)
for ( int i=0;i<max;++i) {
x += i ; // x inicialmente vale 17
}
cout << x << endl; // x==17
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 40/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
firstprivate
Caso particular de private.
Cada copia privada se inicia con el valor de la variable en
el hilo maestro.
Ejemplo
void f () {
int x = 17;
#pragma omp parallel for firstprivate (x)
for (long i=0;i<maxval;++i) {
x += i ; // x inicialmente vale 17
}
std :: cout << x << std ::endl; // x==17
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 41/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
firstprivate
Caso particular de private.
Cada copia privada se inicia con el valor de la variable en
el hilo maestro.
Ejemplo
void f () {
int x = 17;
#pragma omp parallel for firstprivate (x)
for (long i=0;i<maxval;++i) {
x += i ; // x inicialmente vale 17
}
std :: cout << x << std ::endl; // x==17
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 41/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
lastprivate
Pasa el valor de una variable privada de la última iteración
secuencial a la variable global.
Ejemplo
void f () {
int x = 17;
#pragma omp parallel for firstprivate (x) lastprivate (x)
for (long i=0;i<maxval;++i) {
x += i ; // x inicialmente vale 17
}
std :: cout << x << std ::endl; // x valor iteraci ón i==maxval−1
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 42/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Compartición de datos
lastprivate
Pasa el valor de una variable privada de la última iteración
secuencial a la variable global.
Ejemplo
void f () {
int x = 17;
#pragma omp parallel for firstprivate (x) lastprivate (x)
for (long i=0;i<maxval;++i) {
x += i ; // x inicialmente vale 17
}
std :: cout << x << std ::endl; // x valor iteraci ón i==maxval−1
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 42/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 43/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
Secciones
Define un conjunto de secciones
de código.
Cada sección se pasa a un hilo
distinto.
Por defecto hay una barrera al
final del bloque sections
Ejemplo
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
f () ;
#pragma omp section
g() ;
#pragma omp section
h() ;
}
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 44/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
Secciones
Define un conjunto de secciones
de código.
Cada sección se pasa a un hilo
distinto.
Por defecto hay una barrera al
final del bloque sections
Ejemplo
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
f () ;
#pragma omp section
g() ;
#pragma omp section
h() ;
}
}
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 44/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
Planificación de bucles
schedule(static) | schedule(static,n):
Planifica bloques de iteraciones (de tamaño n) para cada
hilo.
schedule(dynamic) | schedule(dynamic,n):
Cada hilo toma un bloque de n iteraciones de una cola
hasta que se han procesado todas.
schedule(guided) | schedule(guided,n):
Cada hilo toma un bloque iteraciones hasta que se han
procesado todas. Se comienza con un tamaño de bloque
grande y se va reduciendo hasta llegar a un tamaño n.
schedule(runtime) | schedule(runtime,n):
Se usa lo indicado en OMP_SCHEDULE o por la biblioteca
en tiempo de ejecución.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 45/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
Planificación de bucles
schedule(static) | schedule(static,n):
Planifica bloques de iteraciones (de tamaño n) para cada
hilo.
schedule(dynamic) | schedule(dynamic,n):
Cada hilo toma un bloque de n iteraciones de una cola
hasta que se han procesado todas.
schedule(guided) | schedule(guided,n):
Cada hilo toma un bloque iteraciones hasta que se han
procesado todas. Se comienza con un tamaño de bloque
grande y se va reduciendo hasta llegar a un tamaño n.
schedule(runtime) | schedule(runtime,n):
Se usa lo indicado en OMP_SCHEDULE o por la biblioteca
en tiempo de ejecución.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 45/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
Planificación de bucles
schedule(static) | schedule(static,n):
Planifica bloques de iteraciones (de tamaño n) para cada
hilo.
schedule(dynamic) | schedule(dynamic,n):
Cada hilo toma un bloque de n iteraciones de una cola
hasta que se han procesado todas.
schedule(guided) | schedule(guided,n):
Cada hilo toma un bloque iteraciones hasta que se han
procesado todas. Se comienza con un tamaño de bloque
grande y se va reduciendo hasta llegar a un tamaño n.
schedule(runtime) | schedule(runtime,n):
Se usa lo indicado en OMP_SCHEDULE o por la biblioteca
en tiempo de ejecución.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 45/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Secciones y planificación
Planificación de bucles
schedule(static) | schedule(static,n):
Planifica bloques de iteraciones (de tamaño n) para cada
hilo.
schedule(dynamic) | schedule(dynamic,n):
Cada hilo toma un bloque de n iteraciones de una cola
hasta que se han procesado todas.
schedule(guided) | schedule(guided,n):
Cada hilo toma un bloque iteraciones hasta que se han
procesado todas. Se comienza con un tamaño de bloque
grande y se va reduciendo hasta llegar a un tamaño n.
schedule(runtime) | schedule(runtime,n):
Se usa lo indicado en OMP_SCHEDULE
o por la biblioteca
en tiempo de ejecución.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 45/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
1 Introducción
2 Hilos en OpenMP
3 Sincronización
4 Bucles paralelos
5 Sincronización con master
6 Compartición de datos
7 Secciones y planificación
8 Conclusión
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 46/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Resumen
OpenMP permite anotar código secuencial para hacer uso
de paralelismo fork-join.
Basado en el concepto de región paralela.
Los mecanismos de sincronización pueden ser de alto
nivel o bajo nivel.
Los bucles paralelos combinados con las reducciones
permiten preservar el código original de muchos
algoritmos.
Los atributos de almacenamiento permiten controlar las
copias y compartición de datos con las regiones paralelas.
OpenMP ofrece varios tipos de planificación.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 47/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Resumen
OpenMP permite anotar código secuencial para hacer uso
de paralelismo fork-join.
Basado en el concepto de región paralela.
Los mecanismos de sincronización pueden ser de alto
nivel o bajo nivel.
Los bucles paralelos combinados con las reducciones
permiten preservar el código original de muchos
algoritmos.
Los atributos de almacenamiento permiten controlar las
copias y compartición de datos con las regiones paralelas.
OpenMP ofrece varios tipos de planificación.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 47/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Resumen
OpenMP permite anotar código secuencial para hacer uso
de paralelismo fork-join.
Basado en el concepto de región paralela.
Los mecanismos de sincronización pueden ser de alto
nivel o bajo nivel.
Los bucles paralelos combinados con las reducciones
permiten preservar el código original de muchos
algoritmos.
Los atributos de almacenamiento permiten controlar las
copias y compartición de datos con las regiones paralelas.
OpenMP ofrece varios tipos de planificación.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 47/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Resumen
OpenMP permite anotar código secuencial para hacer uso
de paralelismo fork-join.
Basado en el concepto de región paralela.
Los mecanismos de sincronización pueden ser de alto
nivel o bajo nivel.
Los bucles paralelos combinados con las reducciones
permiten preservar el código original de muchos
algoritmos.
Los atributos de almacenamiento permiten controlar las
copias y compartición de datos con las regiones paralelas.
OpenMP ofrece varios tipos de planificación.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 47/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Resumen
OpenMP permite anotar código secuencial para hacer uso
de paralelismo fork-join.
Basado en el concepto de región paralela.
Los mecanismos de sincronización pueden ser de alto
nivel o bajo nivel.
Los bucles paralelos combinados con las reducciones
permiten preservar el código original de muchos
algoritmos.
Los atributos de almacenamiento permiten controlar las
copias y compartición de datos con las regiones paralelas.
OpenMP ofrece varios tipos de planificación.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 47/49
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Referencias
Libros:
An Introduction to Parallel Programming. P. Pacheco.
Morgan Kaufmann, 2011. (Cáp 5).
Multicore and GPU Programming. G. Barlas. Morgan
Kaufmann. 2014. (Cáp 4).
Páginas Web:
OpenMP: http://www.openmp.org.
Lawrence Livermore National Laboratory Tutorial: https:
//computing.llnl.gov/tutorials/openMP/.
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 48/49
http://www.openmp.org
https://computing.llnl.gov/tutorials/openMP/
https://computing.llnl.gov/tutorials/openMP/
http://www.arcos.inf.uc3m.es
Programación paralela con OpenMP
Conclusión
Programación paralela con OpenMP
Arquitectura de Computadores
J. Daniel García Sánchez (coordinador)
David Expósito Singh
Javier García Blas
J. Manuel Pérez Lobato
Grupo ARCOS
Departamento de Informática
Universidad Carlos III de Madrid
Arquitectura de Computadores – Grupo ARCOS – http://www.arcos.inf.uc3m.es 49/49
http://www.arcos.inf.uc3m.es
	Introducción
	Hilos en OpenMP
	Sincronización
	Bucles paralelos
	Sincronización con master
	Compartición de datos
	Secciones y planificación
	Conclusión
Arquitectura de Computadores/TEMA 2/OpenMP_consoluciones.zip
Lab1/ej1/ex1par.cpp
#include <iostream>
#include <omp.h>
int main() {
 using namespace std;
 #pragma omp parallel
 {
 int id = omp_get_thread_num();
 cout << "Hola(" << id << ") ";
 cout << "Mundo(" << id << ")";
 }
 return 0;
}
Lab1/ej1/ex1seq.cpp
#include <iostream>
int main() {
 using namespace std;
 int id = 0;
 cout << "Hola(" << id << ") ";
 cout << "Mundo(" << id << ")";
 return 0; 
}
Lab1/ej1/Makefile
CC=g++
CFLAGS=-std=c++14
PARFLAGS=-fopenmp
all: bin bin/seq bin/par
bin:
	mkdir -p bin
bin/seq:	ex1seq.cpp
	$(CC) $(CFLAGS) $< -o $@
bin/par:	ex1par.cpp
	$(CC) $(CFLAGS) $(PARFLAGS) $< -o $@
Lab1/ej2/Makefile
CC=g++
CFLAGS=-std=c++14 -O3 -DNDEBUG
PARFLAGS=-fopenmp
all: bin bin/seq bin/par 
bin:
	mkdir -p bin
bin/seq:	seq.cpp
	$(CC) $(CFLAGS) $< -o $@
bin/par:	par.cpp
	$(CC) $(CFLAGS) $(PARFLAGS) $< -o $@
Lab1/ej2/par.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
#include <vector>
#include <algorithm>
#include <omp.h>
#include <iostream>
int main() {
 using namespace std;
 using namespace std::chrono;
 constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 int nthreads;
 #pragma omp parallel
 nthreads = omp_get_num_threads();
 vector<double> sum(nthreads);
 using clk = high_resolution_clock;
 auto t1 = clk::now();
 #pragma omp parallel 
 {
 int id = omp_get_thread_num();
 for (int i=id; i<nsteps; i+=nthreads) 
 {
 double x = (i+0.5) * step;
 sum[id] += 4.0 / (1.0 + x * x);
 }
 }
 double pi = step * accumulate(begin(sum), end(sum), 0);
 auto t2 = clk::now();
 auto diff = duration_cast<microseconds>(t2-t1);
 cout << "Threads= " << nthreads << endl;
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Tiempo= " << diff.count() << "us" << endl;
 return 0; 
}
Lab1/ej2/seq.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
int main() {
 using namespace std;
 using namespace std::chrono;
 constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 using clk = high_resolution_clock;
 auto t1 = clk::now();
 double sum = 0.0;
 for (int i=0;i<nsteps; ++i) {
 double x = (i+0.5) * step;
 sum += 4.0 / (1.0 + x * x);
 }
 double pi = step * sum;
 auto t2 = clk::now();
 auto diff = duration_cast<microseconds>(t2-t1);
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Tiempo= " << diff.count() << "us" << endl;
 return 0; 
}
Lab1/ej3/Makefile
CC=g++
CFLAGS=-std=c++14 -O3 -DNDEBUG
PARFLAGS=-fopenmp
all: bin bin/seq bin/parcrit bin/paratom
bin:
	mkdir -p bin
bin/seq:	seq.cpp
	$(CC) $(CFLAGS) $< -o $@
bin/parcrit:	parcrit.cpp
	$(CC) $(CFLAGS) $(PARFLAGS) $< -o $@
bin/paratom:	paratom.cpp
	$(CC) $(CFLAGS) $(PARFLAGS) $< -o $@
Lab1/ej3/paratom.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
#include <vector>
#include <algorithm>
#include <omp.h>
#include <iostream>
int main() {
 using namespace std;
 using namespace std::chrono;
constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 int nthreads;
 #pragma omp parallel
 nthreads = omp_get_num_threads();
 double pi = 0.0;
 using clk = high_resolution_clock;
 auto t1 = clk::now();
 #pragma omp parallel 
 {
 int id = omp_get_thread_num();
 double sum = 0.0;
 for (int i=id; i<nsteps; i+=nthreads)
 {
 double x = (i+0.5) * step;
 sum += 4.0 / (1.0 + x * x);
 }
 #pragma omp atomic
 pi += sum * step;
 }
 auto t2 = clk::now();
 auto diff = duration_cast<microseconds>(t2-t1);
 cout << "Threads= " << nthreads << endl;
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Tiempo= " << diff.count() << "us" << endl;
 return 0; 
}
Lab1/ej3/parcrit.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
#include <vector>
#include <algorithm>
#include <omp.h>
#include <iostream>
int main() {
 using namespace std;
 using namespace std::chrono;
 constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 int nthreads;
 #pragma omp parallel
 nthreads = omp_get_num_threads();
 double pi = 0.0;
 using clk = high_resolution_clock;
 auto t1 = clk::now();
 #pragma omp parallel 
 {
 int id = omp_get_thread_num();
 double sum = 0.0;
 for (int i=id; i<nsteps; i+=nthreads)
 {
 double x = (i+0.5) * step;
 sum += 4.0 / (1.0 + x * x);
 }
 #pragma omp critical
 pi += sum * step;
 }
 auto t2 = clk::now();
 auto diff = duration_cast<microseconds>(t2-t1);
 cout << "Threads= " << nthreads << endl;
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Tiempo= " << diff.count() << "us" << endl;
 return 0; 
}
Lab1/ej3/seq.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
int main() {
 using namespace std;
 using namespace std::chrono;
 constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 using clk = high_resolution_clock;
 auto t1 = clk::now();
 double sum = 0.0;
 for (int i=0;i<nsteps; ++i) {
 double x = (i+0.5) * step;
 sum += 4.0 / (1.0 + x * x);
 }
 double pi = step * sum;
 auto t2 = clk::now();
 auto diff = duration_cast<microseconds>(t2-t1);
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Tiempo= " << diff.count() << "us" << endl;
 return 0; 
}
Lab1/ej4/Makefile
CC=g++
CFLAGS=-std=c++14 -O3 -DNDEBUG
PARFLAGS=-fopenmp
all: bin bin/seq bin/par 
bin:
	mkdir -p bin
bin/seq:	seq.cpp
	$(CC) $(CFLAGS) $< -o $@
bin/par:	par.cpp
	$(CC) $(CFLAGS) $(PARFLAGS) $< -o $@
Lab1/ej4/par.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
#include <omp.h>
int main() {
 using namespace std;
 using namespace std::chrono;
 using clk = chrono::high_resolution_clock;
 
 auto t1 = clk::now();
 constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 double sum = 0.0;
 #pragma omp parallel for reduction(+:sum)
 for (int i=0;i<nsteps; ++i) {
 double x = (i+0.5) * step;
 sum += 4.0 / (1.0 + x * x);
 }
 double pi = step * sum;
 auto t2 = clk::now();
 auto dif = duration_cast<microseconds>(t2-t1);
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Time= " << dif.count() << "us" << endl;
 return 0; 
}
Lab1/ej4/seq.cpp
#include <iostream>
#include <iomanip>
#include <chrono>
int main() {
 using namespace std;
 using namespace std::chrono;
 using clk = chrono::high_resolution_clock;
 
 auto t1 = clk::now();
 constexpr long nsteps = 10000000;
 double step = 1.0 / double(nsteps);
 double sum = 0.0;
 for (int i=0;i<nsteps; ++i) {
 double x = (i+0.5) * step;
 sum += 4.0 / (1.0 + x * x);
 }
 double pi = step * sum;
 auto t2 = clk::now();
 auto dif = duration_cast<microseconds>(t2-t1);
 cout << "PI= " << setprecision(10) << pi << endl;
 cout << "Time= " << dif.count() << "us" << endl;
 return 0; 
}
Arquitectura de Computadores/TEMA 3/Ejercicios ILP-ex-sol.pdf
Soluciones a ejercicios de Paralelismo a Nivel de instrucción
J. Daniel García Sánchez (coordinador)
David Expósito Singh
Javier García Blas
J. Manuel Pérez Lobato
Arquitectura de Computadores
Grupo ARCOS
Departamento de Informática
Universidad Carlos III de Madrid
1. Ejercicios de examen
Ejercicio 1 Examen de junio de 2015.
Considere un procesador tipo MIPS con arquitectura segmentada (pipeline) que tiene dos bancos
de registros separados uno para números enteros y otro para números en coma �otante. El banco de
registros enteros dispone de 32 registros. El banco de registros de coma �otante dispone de 16 registros
de doble precisión ($f0, $f2, . . . , $f30).
Se supone que se dispone de su�ciente ancho de banda de captación y decodi�cación como para
que no se generen detenciones por esta causa y que se puede iniciar la ejecución de una instrucción en
cada ciclo, excepto en los casos de detenciones debidas a dependencias de datos.
La siguiente tabla muestra las latencias adicionales de algunas categorías de instrucciones, en caso
de que haya dependencia de datos. Si no hay dependencia de datos la latencia no es aplicable.
Cuadro 1: Latencias adicionales por instrucción
Instrucción Latencia adicional Operación
ldc1
+2 Carga un valor de 64 bits en un registro de coma �otante.
sdc1
+2 Almacena un valor de 64 bits en memoria principal.
add.d
+4 Suma registros de coma �otante de doble precisión.
mul.d
+6 Multiplica registros de coma �otante de doble precisión.
addi
+0 Suma un valor a un registro entero.
subi
+0 Resta un valor a un registro entero.
bnez
+1 Salta si el valor de un registro no es cero.
La instrucción bnez usa bifurcación retrasada con una ranura de retraso (delay slot).
En esta máquina se desea ejecutar el siguiente código:
J. Daniel Garcia et al.
cbed ARCOS@uc3m
1 Arquitectura de Computadores
buc le : ldc1 $f0 , ($t0 )
ldc1 $f2 , ($t1 )
add.d $f4 , $f0 , $ f2
mul.d $f4 , $f4 , $ f6
sdc1 $f4 , ($t2 )
addi $t0 , $t0 , 8
addi $t1 , $t1 , 8
subi $t3 , $t3 , 1
bnez $t3 , buc le
addi $t2 , $t2 , 8
Inicialmente los valores de los registros son:
$t0: 0x00100000.
$t1: 0x00140000.
$t2: 0x00180000.
$t3: 0x00000100.
Se pide:
1. Enumere las dependencias de datos RAW que hay en el código anterior.
2. Indique todas las detenciones que se producen al ejecutar una iteración del código anterior, e
indique el número total de ciclos por iteración.
3. Intente plani�car el bucle para reducir el número de detenciones.
4. Desenrolle el bucle de manera que en cada iteración se procesen cuatro posiciones de los arrays
y determine el speedup conseguido. Utilice nombres de registros reales ($f0, $f2, . . . , $f30).
IMPORTANTE: Se considerarán incorrectas soluciones que no usen registros realmente existentes
(p. ej. $f2' o $f2� son nombres no válidos).
Solución 1
Depenencias Si se numeran las instrucciones consecutivamente comenzando en I1 (hasta I10), se
pueden identi�car las siguientes dependencias RAW:
1. $f0: I1 → I3.
2. $f2: I2 → I3.
3. $f4: I3 → I4.
4. $f4: I4 → I5.
5. $t3: I8 → I9.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
2 Arquitectura de Computadores
Detenciones A continuación se indican las detenciones que se producen al ejecutar el código:
ldc1 $f0 , ($t0 ) #I1
ldc1 $f2 , ($t1 ) #I2
<s t a l l > x 2
add.d $f4 , $f0 , $ f2 #I3
<s t a l l > x 4
mul.d $f4 , $f4 , $ f6 #I4
<s t a l l > x 6
sdc1 $f4 , ($t2 ) #I5
addi $t0 , $t0 , 8 #I6
addi $t1 , $t1 , 8 #I7
subi $t3 , $t3 , 1 #I8
bnez $t3 , buc le #I9
addi $t2 , $t2 , 8 #I10
En total se requieren 22 ciclos.
Plani�cación de bucle Si se reordenan las instrucciones se puede reducir el número de detenciones:
ldc1 $f0 , ($t0 ) #I1
ldc1 $f2 , ($t1 ) #I2
addi $t0 , $t0 , 8 #I6
addi $t1 , $t1 , 8 #I7
add.d $f4 , $f0 , $ f2 #I3
subi $t3 , $t3 , 1 #I8
<s t a l l > x 3
mul.d $f4 , $f4 , $ f6 #I4
<s t a l l > x 6
sdc1 $f4 , ($t2 ) #I5
bnez $t3 , buc le #I9
addi $t2 , $t2 , 8 #I10
En
total se requieren 19 ciclos.
Bucle desenrollado Al desenrollar el bucle con un factor de cuatro se obtiene.
ldc1 $f0 , ($t0 )
ldc1 $f2 , ($t1 )
ldc1 $f8 , 8($t0 )
ldc1 $f10 , 8($t1 )
ldc1 $f14 , 16($t0 )
ldc1 $f16 , 16($t1 )
ldc1 $f20 , 24($t0 )
ldc1 $f22 , 24($t1 )
add.d $f4 , $f0 , $ f2
add.d $f12 , $f8 , $ f10
add.d $f18 , $f14 , $ f16
add.d $f24 , $f20 , $ f22
<s t a l l >
mul.d $f4 , $f4 , $ f6
mul.d $f12 , $f12 , $ f6
mul.d $f18 , $f18 , $ f6
mul.d $f24 , $f24 , $ f6
addi $t0 , 32
addi $t1 , 32
<s t a l l >
sdc1 $f4 , ($t2 )
sdc1 $f12 , 8($t2 )
sdc1 $f18 , 16($t2 )
sdc1 $f24 , 24($t2 )
subi $t3 , 4
bnez $t3 , buc le
addi $t2 , 32
En total se requieren 27 ciclos cada 4 iteraciones. Esto es 6,75 ciclos por iteración
Ejercicio 2 Examen de enero de 2015.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
3 Arquitectura de Computadores
Sea el siguiente fragmento de código se encuentra almacenado a partir de la dirección de memoria
0x1000100C en una máquina en la que todas las instrucciones ocupan 4 bytes:
buc le : lw $r2 , 0( $r0 )
addi $r3 , $r2 , 20
sw $r3 , 0( $r1 )
addi $r0 , $r0 , 4
addi $r1 , $r1 , 4
bnez $r2 , buc le
Dicho código se ejecuta en una máquina que dispone de una caché L1 para datos asociativa por
conjuntos de 2 vías y con un tamaño de 32 KB y una caché L1 para instrucciones de iguales caracte-
rísticas. También dispone de una caché L2 uni�cada asociativa por conjuntos de 8 vías con un tamaño
de 1 MB. En ambos casos el tamaño de línea es de 32 bytes. Se asume que un acierto en la caché
L1 requiere 4 ciclos, y un acierto en la caché L2 requiere 14 ciclos adicionales y la penalización por
traer un bloque de memoria principal a la caché de nivel 2 es de 80 ciclos. Todas las cachés tienen una
política de escritura write-back.
Inicialmente el valor de los registros es:
$r0: 0x00010000.
$r1: 0x00080000.
A partir de la posición 0x00010000 todos los valores en memoria son distintos de cero hasta la
posición 0x000100FC. En la posición de memoria 0x000100FC hay un valor de cero.
1. Determine cuál debería ser el tiempo medio de acceso asumiendo que un programa (distinto del
facilitado) realiza en promedio 2 accesos a datos por instrucción y tiene las siguientes tasas de
fallo:
L1 instrucciones: 10%
L1 datos: 5%
L2: 2%
2. Determine el número de fallos que se producen durante la ejecución del fragmento de código
facilitado en el enunciado para las cachés L1 de datos, L1 de instrucciones y L2.
3. 1.3: Elabore un diagrama de tiempos para una arquitectura MIPS con un pipeline de 5 etapas
para la primera iteración del bucle asumiendo que inicialmente no hay datos ni instrucciones en
las cachés y con las siguientes consideraciones:
No hay hardware de forwarding.
La arquitectura permite que una instrucción escriba en un registro y otra instrucción lea
ese mismo registro sin problemas.
Las bifurcaciones se tratan vaciando el pipeline.
La dirección efectiva de salto se calcula en la etapa de ejecución.
NOTA: Tenga en cuenta en el cronograma las detenciones debidas a los fallos en toda la jerarquía
de caché tanto para instrucciones (etapa IF) como para lecturas y escrituras de datos (etapa M).
4. Repita el diagrama de tiempos para la segunda iteración.
Solución 2
J. Daniel Garcia et al.
cbed ARCOS@uc3m
4 Arquitectura de Computadores
Tiempo medio de acceso En cuanto a los accesos a la caché de nivel 1, se tiene que se realiza 2
accesos a datos por cada acceso a instrucciones. Por tanto la tasa de fallos se obtiene mediante media
ponderanda:
mL1 =
mL1I + 2 ·mL1D
3
mL1 =
0,1 + 2 · 0,05
3
=
0,2
3
= 0,0667
Por tanto el tiempo medio de acceso sería:
T = 4 +mL1 · (14 +mL2 · 80) = 4 + 0,0667 · (14 + 0,02 · 80) = 5,04 ciclos
Número de fallos El bucle se ejecuta un total de 2
8
4 = 2
6 = 64 iteraciones.
Analizaremos por separado los accesos de instrucciones y datos.
La primera instrucción se almacena en la dirección 0x1000100C. La última instrucción se almacena
en la dirección en la dirección 0x1000100C +(6− 1) ∗ 4 = 0x10001020.
En la primera iteración, la primera instrucción genera un fallo de caché y trae el bloque de direccio-
nes 0x10001000 � 0x1000101F, que contiene una instrucción de interés. Las siguientes instrucciones
(I2, I3, I4, e I5) generan aciertos. Por último, la instrucción I6 vuelve a generar un fallo. Por tanto,
la primera iteración genera 2 fallos y 4 aciertos. El resto de iteraciones generan aciertos en todos los
casos.
Como el bucle se ejecuta 64 veces, el acceso a las instrucciones genera los siguientes accesos:
Fallos L1I: 2
Aciertos L1I: 4 + 63 · 6
Fallos L2: 1
Aciertos L2: 0
En cada iteración del bucle se lee una dirección de memoria en el rango 0x00010000 � 0x000100FC.
Esto se corresponde con 2
8
25
= 8 líneas de caché.
Igualmente se escriben valores en las direcciones 0x00080000 � 0x000800FC, que se escriben en
8 líneas de la caché. Como las cachés son asociativas por conjuntos no se dan con�ictos entre los datos
leídos y escritos. Como no se expulsa ninguna línea de la caché L1 no hay escrituras en la caché L2.
1. Fallos L1D: 8 lecturas + 8 escrituras
2. Aciertos L1D: 56 lecturas + 56 escrituras
3. Fallos L2: 8 lecturas
4. Aciertos L2: 0
J. Daniel Garcia et al.
cbed ARCOS@uc3m
5 Arquitectura de Computadores
Diagrama de tiempos para primera iteración Si se numeran las instrucciones de la siguiente
forma:
buc le : lw $r2 , 0( $r0 ) #1
addi $r3 , $r2 , 20 #2
sw $r3 , 0( $r1 ) #3
addi $r0 , $r0 , 4 #4
addi $r1 , $r1 , 4 #5
bnez $r2 , buc le #6
Se tienen las siguientes dependencias RAW:
1. $r2: I2 → I1
2. $r3: I3 → I2
3. $r0: I4 → I1
4. $r1: I3 → I5
Al no haber forwarding, cuando hay una dependencia RAW debe esperarse al ciclo WB de la
instrucción fuente para inicial el ciclo de la instrucción destino. La Tabla 2 muestra el correspondiente
diagrama de tiempos.
La primera instrucción se detiene 98 ciclos (80+14+4) en el fetch por ser un fallo en toda la
jerarquía de memoria.
La lectura de datos de la primera instrucción es un fallo de lectura y requiere 98 ciclos también.
La segunda instrucción es un acierto y requiere cuatro ciclos para realizar la captación de la caché
L1I.
La instrucción I3 es un acierto y requiere cuatro ciclos para realizar la captación de la caché L1I.
La escritura de datos de la instrucción I3 es un fallo de escritura y requiere 98 ciclos.
La instrucción I4 es un acierto y requiere cuatro ciclos para realizar la captación de la caché L1I.
La instrucción I4 no puede iniciar su ciclo de memoria hasta que no termine el acceso a memoria
de I3.
La instrucción I5 es un acierto y requiere cuatro ciclos para realizar la captación de L1I.
La instrucción I5 no puede iniciar su ciclo de ejecución hasta que no termine la ejecución de I4.
La instrucción I6 es un fallo y requiere 98 ciclos para realizar la captación de L1I.
La instrucción I7 (la siguiente a la bnez) no puede comenzar la captación hasta que no se libera
la unidad de fetch.
Si bien se conoce la dirección de salto al �nal de la etapa de decodi�cación de I6, el sentido de
salto (tomar o no tomar) no se conoce hasta el �nal de la etapa de ejecución.
En total se requieren 310 ciclos.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
6 Arquitectura de Computadores
In
st
ru
c
c
ió
n
1�
98
99
10
0
10
1
10
2
10
3�
19
8
19
9
20
0
20
1
20
2
20
3
20
4
20
5
20
6
20
7
20
8
20
9
21
0
I1
:
lw
$
r2
,
0
($
r0
)
IF
ID
E
X
M
M
M
W
B
I2
:
a
d
d
i
$
r3
,
$
r2
,
2
0
IF
1
IF
2
IF
3
IF
4
�
ID
E
X
M
W
B
I3
:
sw
$
r3
,
0
($
r1
)
IF
1
IF
2
IF
3
IF
4
ID
E
X
M
M
M
M
M
M
I4
:
a
d
d
i
$
r0
,
$
r0
,
4
IF
1
IF
2
IF
3
IF
4
ID
E
X
�
�
I5
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
1
IF
2
IF
3
IF
4
In
st
ru
c
c
ió
n
21
1
21
2
21
3
21
4
21
5�
30
2
30
3
30
4
30
5
30
6
30
7
30
8
30
9
31
0
31
1
31
2
I1
:
lw
$
r2
,
0
($
r0
)
I2
:
a
d
d
i
$
r3
,
$
r2
,
2
0
I3
:
sw
$
r3
,
0
($
r1
)
M
M
M
M
M
W
B
I4
:
a
d
d
i
$
r0
,
$
r0
,
4
�
�
�
�
�
M
W
B
I5
:
a
d
d
i
$
r1
,
$
r1
,
4
ID
�
�
�
�
E
X
M
W
B
I6
:
b
n
e
z
$
r2
,
b
u
c
le
IF
IF
IF
IF
IF
IF
IF
IF
IF
IF
IF
ID
E
X
M
I7
:
?
IF
�u
sh
I1
:
lw
$
r2
,
0
($
r0
)
IF
C
ua
dr
o
2:
D
ia
gr
am
a
de
ti
em
p
os
de
la
pi
m
er
a
it
er
ac
ió
n
de
l
ej
er
ci
ci
o
2.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
7 Arquitectura de Computadores
In
stru
c
c
ió
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
I1
:
lw
$
r2
,
0
($
r0
)
IF
IF
IF
IF
ID
E
X
M
M
M
M
W
B
I2
:
a
d
d
i
$
r3
,
$
r2
,
2
0
IF
IF
IF
IF
�
�
ID
E
X
M
W
B
I3
:
sw
$
r3
,
0
($
r1
)
IF
IF
IF
IF
ID
E
X
M
M
M
M
W
B
I4
:
a
d
d
i
$
r0
,
$
r0
,
4
IF
IF
IF
IF
ID
E
X
M
I5
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
IF
IF
In
stru
c
c
ió
n
22
23
24
25
26
27
28
29
30
I1
:
lw
$
r2
,
0
($
r0
)
I2
:
a
d
d
i
$
r3
,
$
r2
,
2
0
I3
:
sw
$
r3
,
0
($
r1
)
I4
:
a
d
d
i
$
r0
,
$
r0
,
4
W
B
I5
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
ID
E
X
M
W
B
I6
:
b
n
e
z
$
r2
,
b
u
c
le
IF
IF
IF
IF
ID
E
X
M
W
B
I7
:
?
IF
�ush
I1
:
lw
$
r2
,
0
($
r0
)
IF
C
uadro
3:
D
iagram
a
de
tiem
p
os
de
la
segunda
iteración
del
ejercicio
2.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
8 Arquitectura de Computadores
Diagrama de tiempos para segunda iteración La Tabla 3 muestra el correspondiente diagrama
de tiempos. En total se requieren 28 ciclos de reloj.
Ejercicio 3 Examen de octubre de 2014.
Sea el siguiente fragmento de código:
buc le : lw $f0 , 0( $r1 )
lw $f2 , 0( $r2 )
mul . f $f4 , $f0 , $ f2
add.d $f6 , $f6 , $ f4
addi $r1 , $r1 , 4
addi $r2 , $r2 , 4
sub $r3 , $r3 , 1
bnez $r3 , buc le
1. Haga una lista con todas las posibles dependencia de datos, sin considerar una estructura espe-
cí�ca de la arquitectura segmentada. Para cada dependencia debe indicar, registro, instrucción
de origen, instrucción de destino y tipo de dependencia.
2. Elabore un diagrama de tiempos para una arquitectura MIPS con un pipeline en 5 etapas, con
las siguientes consideraciones:
No hay hardware de forwarding.
La arquitectura permite que una instrucción escriba en un registro y otra instrucción lea
ese mismo registro sin problemas.
Las bifurcaciones se tratan vaciando el pipeline.
Las referencias a memoria requieren un ciclo de reloj.
La dirección efectiva de salto se calcula en la etapa de ejecución.
3. Determine cuantos ciclos se necesitan para ejecutar N iteraciones del bucle.
4. Elabore un diagrama de tiempos para una arquitectura MIPS con un pipeline en 5 etapas con
las siguientes consideraciones:
Hay hardware completo de forwarding.
Asuma que las bifurcaciones se tratan prediciendo todos los saltos como tomados.
5. Determine cuantos ciclos se necesitan para ejecutar N iteraciones del bucle en las condiciones del
apartado 4.
Solución 3
Dependencias de datos Si se numeran las instrucciones desde I1 (primera instrucción) hasta I8
(última instrucción) se tienen las siguientes dependencias:
$f0: I1 → I3 (RAW)
$f2: I2 → I3 (RAW)
$f4: I3 → I4 (RAW)
$r3: I7 → I8 (RAW)
J. Daniel Garcia et al.
cbed ARCOS@uc3m
9 Arquitectura de Computadores
In
stru
c
c
ió
n
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
I1
:
lw
$
f0
,
0($
r1
)
ID
ID
E
X
M
W
B
I2
:
lw
$
f2
,
0($
r2
)
IF
ID
E
X
M
W
B
I3
:
m
u
l.f
$
f4
,
$
f0
,
$
f2
IF
�
�
ID
E
X
M
W
B
I4
:
a
d
d
.d
$
f6
,
$
f6
,
$
f4
IF
�
�
ID
E
X
M
W
B
I5
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
ID
E
X
M
W
B
I6
:
a
d
d
i
$
r2
,
$
r2
,
4
IF
ID
E
X
M
W
B
I7
:
su
b
$
r3
,
$
r3
,
1
IF
ID
E
X
M
W
B
I8
:
b
n
e
z
$
r3
,
b
u
c
le
IF
�
�
ID
E
X
M
W
B
I9
:
(sig
a
b
n
e
z)
IF
I1
:
lw
$
f0
,
0
($
r1
)
IF
ID
E
X
M
W
B
C
uadro
4:
P
rim
er
diagram
a
de
tiem
p
os
del
ejercicio
3.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
10 Arquitectura de Computadores
Primer diagrama de tiempos Al no haber forwarding, cuando hay una dependencia RAW debe
esperarse al ciclo WB de la instrucción fuente para inicial el ciclo de la instrucción destino. La Tabla 4
muestra el correspondiente diagrama de tiempos.
La instrucción I3, tiene una detención hasta que I2 haya escrito el valor leído en $f2. Se puede
realizar la lectura de banco de registros en el mismo ciclo en que I2 escribe en el banco de registros
(ciclo 6).
La instrucción I4 no puede comenzar la captación hasta que no se libera la unidad de fetch (ciclo
6).
La instrucción I4, tiene una detención hasta que I3 haya escrito el valor calculado en $f4. Se
puede realizar la lectura de banco de registros en el mismo ciclo en que I3 escribe en el banco de
registros (ciclo 9).
La instrucción I5 no puede comenzar la captación hasta que no se libere la unidad de fetch (ciclo
9).
La instrucción I8 tiene una detención hasta que I7 haya escrito el valor $r3. Se puede realizar la
lectura de banco de registros en el mismo ciclo en que I7 escribe en el banco de registros (ciclo
15).
La instrucción I9 (la siguiente a la bnez) no puede comenzar la captación hasta que no se libera
la unidad de fetch (ciclo 15).
Si bien se conoce la dirección de salto al �nal de la etapa de decodi�cación de I8, el sentido
de salto (tomar o no tomar) no se conoce hasta el �nal de la etapa de ejecución Por tanto la
captación se repite en el ciclo 17.
Primera estimación de ciclos Para determinar el número de ciclos se debe determinar, cuántos
ciclos se requieren para cualquier iteración y cuántos para la última iteración.
El coste de una iteración distinta de la última se obtiene determinando el número de ciclos desde
que se inicia la ejecución de I1 hasta que esta se vuelve a iniciar. Esto son 16 ciclos.
El coste de la última iteración se obtiene determinando el número de ciclos hasta que se �naliza la
ejecución de la instrucción I8. Estos son 18 ciclos.
Coste = 16 · n+ 2
.
Segundo diagrama de tiempos Ahora se permite forwarding siempre que sea posible y no hay
que esperar a la etapa de WB. La Tabla 5 muestra el correspondiente diagrama de tiempos.
La instrucción I3 puede iniciar ejecución tras la etapa de memoria de I2 (ciclo 6) gracias al
forwarding.
La instrucción I4 no puede iniciar la decodi�cación hasta que no se ha liberado la unidad de
decodi�cación (ciclo 6).
La instrucción I4 puede iniciar ejecución tras la etapa de ejecución de I3 (ciclo 7) gracias al
forwarding.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
11 Arquitectura de Computadores
In
stru
c
c
ió
n
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
I1
:
lw
$
f0
,
0($
r1
)
ID
ID
E
X
M
W
B
I2
:
lw
$
f2
,
0($
r2
)
IF
ID
E
X
M
W
B
I3
:
m
u
l.f
$
f4
,
$
f0
,
$
f2
IF
ID
�
E
X
M
W
B
I4
:
a
d
d
.d
$
f6
,
$
f6
,
$
f4
IF
�
ID
E
X
M
W
B
I5
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
ID
E
X
M
W
B
I6
:
a
d
d
i
$
r2
,
$
r2
,
4
IF
ID
E
X
M
W
B
I7
:
su
b
$
r3
,
$
r3
,
1
IF
ID
E
X
M
W
B
I8
:
b
n
e
z
$
r3
,
b
u
c
le
IF
ID
E
X
M
W
B
I1
:
lw
$
f0
,
0
($
r1
)
IF
ID
E
X
M
W
B
C
uadro
5:
Segundo
diagram
a
de
tiem
p
os
del
ejercicio
3.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
12 Arquitectura de Computadores
La instrucción I5 no puede iniciar la captación hasta que no se libera la unidad de fetch (ciclo
6).
La instrucción I8 no puede iniciar la decodi�cación hasta que no se ha calculado el valor de $r3
(ciclo 10) y se le pasa mediante forwarding (ciclo 11).
Segunda estimación de ciclos El coste de una iteración distinta de la última es de 10 ciclos. La
última iteración requiere 14 ciclos.
Coste = 10 · n+ 4
Ejercicio 4 Octubre de 2014.
Sea el siguiente fragmento de código:
buc le : lw $f0 , 0( $r1 )
lw $f2 , 0( $r2 )
s ub . f $f4 , $f0 , $ f2
mul.d $f4 , $f4 , $ f4
add.d $f6 , $f6 , $ f4
addi $r1 , $r1 , 4
addi $r2 , $r2 , 4
sub $r3 , $r3 , 1
bnez $r3 , buc le
1. Haga una lista con toda la posible dependencia de datos, sin considerar una estructura especí�ca
de la arquitectura segmentada. Para cada dependencia debe indicar, registro, instrucción de
origen, instrucción de destino y tipo de dependencia.
2. Elabore un diagrama de tiempos para una arquitectura MIPS con un pipeline en 5 etapas, con
las siguientes consideraciones:
No hay hardware de forwarding.
La arquitectura permite que una instrucción escriba en un registro y otra instrucción lea
ese mismo registro sin problemas en el mismo ciclo de reloj.
Las bifurcaciones se tratan vaciando el pipeline.
Las referencias a memoria requieren un ciclo de reloj.
La dirección efectiva de salto se calcula en la etapa de ejecución.
3. Determine cuantos ciclos se necesitan para ejecutar N iteraciones del bucle.
4. Elabore un diagrama de tiempos para una arquitectura MIPS con un pipeline en 5 etapas con
las siguientes consideraciones:
Hay hardware completo de forwarding.
Asuma que las bifurcaciones se tratan prediciendo todos los saltos como tomados.
5. Determine cuantos ciclos se necesitan para ejecutar N iteraciones del bucle en las condiciones del
apartado 4.
Solución 4
J. Daniel Garcia et al.
cbed ARCOS@uc3m
13 Arquitectura de Computadores
Depdencias de datos Si se numeran las instrucciones desde I1 (primera instrucción) hasta I9
(última instrucción) se tienen las siguientes dependencias:
$f0: I1 → I3 (RAW)
$f2: I2 → I3 (RAW)
$f4: I3 → I4 (RAW, WAW)
$f4: I4 → I5 (RAW)
$r3: I8 → I9 (RAW)
Primer diagrama de tiempos Al no haber forwarding, cuando hay una dependencia RAW debe
esperarse al ciclo WB de la instrucción fuente para inicial el ciclo de la instrucción destino. La Tabla 6
muestra el correspondiente diagrama de tiempos.
La instrucción I3, tiene una detención hasta que I2 haya escrito el valor leído en $f2. Se puede
realizar la lectura de banco de registros en el mismo ciclo en que I2 escribe en el banco de registros
(ciclo 6).
La instrucción I4 no puede comenzar la captación hasta que no se libera la unidad de fetch (ciclo
6).
La instrucción I4, tiene una detención hasta que I3 haya escrito el valor calculado en $f4. Se
puede realizar la lectura de banco de registros en el mismo ciclo en que I3 escribe en el banco de
registros (ciclo 9).
La instrucción I5 no puede comenzar la captación hasta que no se libere la unidad de fetch (ciclo
9).
La instrucción I5, tiene una detención hasta que I4 haya escrito el valor calculado de $f4. Se
puede realizar la lectura de banco de registros en el mismo ciclo en que I4 escribe en el banco de
registros (ciclo 12).
La instrucción I6 no puede comenzar la captación hasta que no se libere la unidad de fetch (ciclo
12).
La instrucción I9 tiene una detención hasta que I8 haya escrito el valor $r3. Se puede realizar la
lectura de banco de registros en el mismo ciclo en que I7 escribe en el banco de registros (ciclo
18).
La instrucción I10 (la siguiente a la bnez) no puede comenzar la captación hasta que no se libera
la unidad de fetch (ciclo 18).
Si bien se conoce la dirección de salto al �nal de la etapa de decodi�cación de I9, el sentido
de salto (tomar o no tomar) no se conoce hasta el �nal de la etapa de ejecución Por tanto la
captación se repite en el ciclo 20.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
14 Arquitectura de Computadores
In
st
ru
c
c
ió
n
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
I1
:
lw
$
f0
,
0(
$
r1
)
IF
ID
E
X
M
W
B
I2
:
lw
$
f2
,
0
($
r2
)
IF
ID
E
X
M
W
B
I3
:
su
b
.f
$
f4
,
$
f0
,
$
f2
IF
�
�
ID
E
X
M
W
B
I4
:
m
u
l.
d
$
f4
,
$
f4
,
$
f4
IF
�
�
ID
E
X
M
W
B
I5
:
a
d
d
.d
$
f6
,
$
f6
,
$
f4
IF
�
�
ID
E
X
M
W
B
I6
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
ID
E
X
M
W
B
I7
:
a
d
d
i
$
r2
,
$
r2
,
4
IF
ID
E
X
M
W
B
I8
:
su
b
$
r3
,
$
r3
,
4
IF
ID
E
X
M
W
B
I9
:
b
n
e
z
$
r3
,
b
u
c
le
IF
�
�
ID
E
X
M
W
B
I1
0
:
(s
ig
ui
en
te
a
b
n
e
z
)
IF
�
I1
:
lw
$
f0
,
0(
$
r1
)
IF
ID
C
ua
dr
o
6:
P
ri
m
er
di
ag
ra
m
a
de
ti
em
p
os
de
l
ej
er
ci
ci
o
4.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
15 Arquitectura de Computadores
Primera estimación de ciclos Para determinar el número de ciclos se debe determinar, cuántos
ciclos se requieren para cualquier iteración y cuántos para la última iteración.
El coste de una iteración distinta de la última se obtiene determinando el número de ciclos desde
que se inicia la ejecución de I1 hasta que esta se vuelve a iniciar. Esto son 19 ciclos.
El coste de la última iteración se obtiene determinando el número de ciclos hasta que se �naliza la
ejecución de la instrucción I9. Estos son 21 ciclos.
Coste = 19 · n+ 2.
Segundo diagrama de tiempos Ahora se permite forwarding siempre que sea posible y no hay
que esperar a la etapa de WB. La Tabla 7 muestra el correspondiente diagrama de tiempos.
La instrucción I3 puede iniciar ejecución tras la etapa de memoria de I2 (ciclo 6) gracias al
forwarding.
La instrucción I4 no puede iniciar la decodi�cación hasta que no se ha liberado la unidad de
decodi�cación (ciclo 6).
La instrucción I4 puede iniciar ejecución tras la etapa de ejecución de I3 (ciclo 7) gracias al
forwarding.
La instrucción I5 no puede iniciar la captación hasta que no se libera la unidad de fetch (ciclo
6).
La instrucción I5 puede iniciar ejecución tras la etapa de ejecución de I4 (ciclo 8) gracias al
forwarding.
La instrucción I9 no puede iniciar la decodi�cación hasta que no se ha calculado el valor de $r3
(ciclo 11) y se le pasa via forwarding (ciclo 12).
Segunda estimación de ciclos El coste de una iteración distinta de la última es de 11 ciclos. La
última iteración requiere 15 ciclos.
Coste = 11 · n+ 4
Ejercicio 5 Examen de junio de 2014.
En un determinado procesador se dispone de la tabla 8 de latencia entre instrucciones:
En esta máquina se desea ejecutar el siguiente trozo de código:
BUCLE: L.D F0 , 0(R1)
L.D F2 , 0(R2)
ADD.D F4 , F0 , F2
S.D F4 , 0(R3)
DADDUI R1 , R1 , #−8
BNE R1 , R4 , BUCLE
Inicialmente se tienen los siguientes valores:
R1: Último elemento de primer array origen.
R2: Último elemento de segundo array origen.
R3: Último elemento de array destino.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
16 Arquitectura de Computadores
In
st
ru
c
c
ió
n
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
I1
:
lw
$
f0
,
0(
$
r1
)
IF
ID
E
X
M
W
B
I2
:
lw
$
f2
,
0
($
r2
)
IF
ID
E
X
M
W
B
I3
:
su
b
.f
$
f4
,
$
f0
,
$
f2
IF
�
ID
E
X
M
W
B
I4
:
m
u
l.
d
$
f4
,
$
f4
,
$
f4
IF
�
ID
E
X
M
W
B
I5
:
a
d
d
.d
$
f6
,
$
f6
,
$
f4
IF
ID
E
X
M
W
B
I6
:
a
d
d
i
$
r1
,
$
r1
,
4
IF
ID
E
X
M
W
B
I7
:
a
d
d
i
$
r2
,
$
r2
,
4
IF
ID
E
X
M
W
B
I8
:
su
b
$
r3
,
$
r3
,
4
IF
ID
E
X
M
W
B
I9
:
b
n
e
z
$
r3
,
b
u
c
le
IF
�
ID
E
X
M
W
B
I1
:
lw
$
f0
,
0(
$
r1
)
IF
ID
E
X
M
W
B
C
ua
dr
o
7:
Se
gu
nd
o
di
ag
ra
m
a
de
ti
em
p
os
de
l
ej
er
ci
ci
o
4.
J. Daniel Garcia et al.
cbed ARCOS@uc3m
17 Arquitectura de Computadores
Cuadro 8: Latencia entre instrucciones
Instrucción que produce el resultado Instrucción que usa el resultado Latencia
Operación ALU FP Otra operación ALU FP 6
Operación ALU FP Almacenar doble 3
Cargar doble Operación ALU FP 2
Cargar doble Almacenar doble 0
R4: Precalculado. Tal que 8(R4) sea el primer elemento del primer array origen.
Todos los arrays tienen un tamaño de 4000 elementos.
Se pide:
1. Determine cuántos ciclos se requiere para ejecutar todas las iteraciones del bucle si no se realiza
ninguna modi�cación.
2. Determine cuántos ciclos se requiere para ejecutar todas las iteraciones si se realiza plani�cación
del bucle.
3. Determine cuántos ciclos se requiere para ejecutar todas las iteraciones si se desenrolla el bucle
para cada dos iteraciones.
4. Determine cuántos ciclos se requiere para ejecutar todas las iteraciones si se desenrolla el bucle
para cada cuatro iteraciones.
Solución 5
Apartado 1 La ejecución de una iteración del bucle sería:
L.D F0 , 0(R1)
L.D F2 , 0(R2)
<s t a l l > x 2
ADD.D F4 , F0 , F2
<s t a l l > x 3
S.D F4 , 0(R3)
DADDUI R1 , R1 , #−8
BNE R1 , R4 , BUCLE
En total cada iteración requiere 11 ciclos para haber iniciado todas las instrucciones. Lo que da
lugar a un total de 44,000 ciclos.
Apartado 2 La instrucción DADDUI podría adelantarse:
L.D F0 , 0(R1)
L.D F2 , 0(R2)
DADDUI R1 , R1 , #−8
<s t a l l > x 1
ADD.D F4 , F0 , F2
<s t a l l > x 3
S.D F4 , 0(R3)
BNE R1 ,