PDF de programación - Parte I: Optimización Secuencial - Técnicas de Computación Científica

Técnicas de Computación Científica

Parte I: Optimización Secuencial

FIM - 2011/12
Vicente Martín
v0.4d

Arquitecturas Secuenciales

● Un sólo procesador con acceso a un único espacio

de direcciones de memoria (física)
– El espacio físico se puede dividir en varios espacios

lógicos de modo que varios procesos puedan
compartir el procesador. El sistema operativo provee
una imágen lineal de la memoria a cada proceso como
si éste tuviese acceso exclusivo a la memoria física.
(Memoria virtual)

Instrucciones y Filosofías de Diseño

● CISC: Complex Instruction Set Computer. “cuanto más haga
una sola instrucción, mejor” eg.: VAX-11/780 (1978) 303 instrucciones, 16
modos de direccionamiento, formatos variables desde 2 a 57 bytes, 456KB de
microcódigo en la CU. Otros: familias Intel 80386 y Motorola 68000.

● RISC: Reduced Instruction Set Computer. “simplifica, evita
todo lo que no sea muy usado, hará más fácil el diseño y más rápido el HW”
Cierto con el apoyo de buenos compiladores. eg.: IBM 801 (experimental, 1975),
RISC I/II (Berkeley, 1985) origen de los SPARC , MIPS (Stanford, 1985). La
gran mayoría de CPUs actuales de propósito general.

● VLIW: Very Long Instruction Word. “dale a la CPU palabras
grandes con toda la información necesaria para utilizar completamente todo su
HW directamente” El compilador tiene que ser muy listo para organizar estas
palabras. La complejidad pasa del HW al SW. eg.: Transmeta (necesita capas de
code morphing), CPUs para dispositivos empotrados, con HW de ayuda parcial al
SW: EPIC (Itanium 1/2)

How an instruction is processed?

● A group of n instructions are predecoded to the Instruction Cache.

– Each group is tagged with flow history bits.

● Instructions within the group are tagged with kind of
instruction (essentially, Functional unit needed) and branch
history bits (color the instructions).
● Predicting a bad branch results in a heavy penalty for CPUs
with long pipelines: discarding the instructions/registers
with a given color.

– Also, fetching of the wrong instructions could occur due
to misprediction.

● Instructions are processed when HW available (funct. Unit,
registers) and reordered to maximize HW use.
● Registers are not committed to memory till the associated
instructions are accepted (retired)

How an instruction is processed? (II)

– Some execution units can have several outstanding instructions

at a given point in time.
● Specially true for memory operations in order to mask
latency.

– When a branch is resolved, it must be communicated to other

execution units in order to free/invalidate
resources/instructions.

– In the final stage the Completed Instruction Buffer holds all
instructions executed till the Retire Unit makes sure that no
previous instruction produced an exception, then it is retired (in
program order)

● A modern CPU can have more than 200 instructions in flight at

any given point in time.

Eg. CPU RISC moderna: IBM Power 4+

Behling 01

Esquema del pipeline. No se representan las unidades funcionales duplicadas. Cada
unidad funcional tiene su propia cola, las instrucciones no se ejecutan necesariamente
en orden. Puede mantener mas de 200 instruciones en ejecución simultánea, lo que hace
que la lógica de control sea muy compleja.

Behling 01

Power 4+

8 unidades funcionales. 170 Millones de transistores. 2 cores, 1.44 MB L2 cache y HW de
comunicaciones en la misma oblea. Posibilidad de formar un SMP de 8 CPUs en un espacio mínimo

Itanium 2

Cambio radical de la IA32. EPIC, parcialmente VLIW,
core “simplificado”, rendimiento más dependiente del
compilador. Sin HW para “glueless” SMP. Cache L3
en la oblea (Madison: version con 6MB). 210 Millones
de transistores (410?? Madison)

Steen 03

Procesadores Vectoriales

NEC SX-6: Arquitectura vectorial tradicional: Vectores
muy grandes. Se accede directamente, sin caches, a una
memoria organizada en bancos para soportar el ancho de
banda necesario para alimentar las unidades vectoriales.

Cray X1: Vectores más cortos (32 elementos),
acceso a través de caches. Menos especializado,
mayor atención al paralelismo.

Parámetros de algunas CPUs Típicas

NEC SX-6
500 Mhz

Itanium-2
1500MHz

Power 4+
1700 MHz

16KB, 64B/Linea, 4-w assoc.
Latencia 1 ciclo. No FP.
24 GB/sec (bus 128b)

32KB, 128B/Linea,2w asoc.
Latencia 1 ciclo.
27.2 GB/sec (bus 128b)

256KB, 128B/Linea, 8-w assoc.
Latencia 5/6 ciclos (Int/FP) 48
GB/sec (bus 256)

1.41 MB, 3 bancos. 128B/linea
4w o 8w. Latencia 8-10 ciclos.
156 GB/sec (32B+8B x 2cores)

6MB, 128B/Linea 24-w assoc.
Latencia 14 ciclos
48 GB/sec (bus 256b)

Hasta 32MB, 8w asoc.
512B/linea. 18.1 GB/sec
(2x16B a 3:1) escalable.

n/a

n/a

n/a

Reloj

L1-D

L2

L3

Bus/Mem
Ppal.

6.4 GB/sec (bus 128b a
400MHz)

6.4 GB/sec (128b a 400MHz)
escalable

32 GB/sec (512b
a 500 MHz)

Rendi-
miento

Otros

Pico Teorico: 6 Gflops
Linpack: 1659/5400 MFlops
SpecFP2000: 2161

Pico Teorico: 6.8 Gflops
Linpack:1486/3884 MFlops
SpecFP2000: 1642

Pico: 8 Gflops
Linpack: 1161/7575 MFlops
SpecFP2000: no medido

410?!! Mill. Transistores
Sin logica adicional SMP.

2 cores/chip, montables en un
grupo de 4 con bus de 60 GB/s

primera CPU vectorial en un chip.
Earth Simul. +5000 procesadores.

Latencias.

IBM Power4 a 1.3 GHz, Intel Itanium2 a 1 Ghz con 3 MB de L3 y NEC SX6. En azul claro las caches incluidas en
el mismo chip que la CPU. En azul oscuro las externas. Los anchos de banda son la suma de los anchos de banda en
lectura y escritura. En el Power4 las caches L2 y L3 son compartidos entre los dos cores (hay una version del chip
con un solo core, para HPC que no comparte caches.



InSide, spring 2003

No todo es lo que parece

Incluso en parámetros aparentemente fáciles de definir, como el ancho de banda, hay
muchos detalles escondidos. Los fabricantes no suelen dejar claro a qué se refieren
en las “macrocifras”... eg.: anchos de banda detallados del Power4:

Grassl 02

Parece inviable seguir complicando las
CPUs incrementando el numero de unidades
funcionales y el HW asociado para mantener-
las llenas. Aumentar el numero de etapas en
cada unidad para llevarlas a mayores
velocidades tambien complica el HW y
empiezan a ser muy graves los problemas de
disipación. El gap de velocidad entre la
memoria y la CPU se incrementa. De
momento las soluciones van por incluir
soporte especifico para hilos de ejecución
(SMT: Symmetric Multithreading), que
incrementa las posibilidades de llenado de
unidades funcionales y la tolerancia a la
latencia en la memoria. Como el soporte para
hilos tambien complica el HW se prefiere
incluir más cores en un solo chip que añadir
soporte para mas hilos. Un chip Power 5 es
visto como 4 CPUs por el SO: 2 cores con
dos hilos por core. Se añade además soporte
para comunicaciones off-chip: multiproceso,
I/O y se hace algo más rápida la jerarquia de
memoria. Tendencias similares en AMD o
Intel.

R. Kalla et al. “IBM Power5 Chip: A dual-core multithreaded
processor” IEEE Micro, Mar-apr. 2004, pag. 40

Optimización Secuencial

● Nuestro objetivo es usar de la manera más eficiente posible el HW
que, para un ordenador secuencial, consideraremos dividido en dos
grandes bloques:

➔ Memoria
➔ CPU

y tendremos que hacernos alguna idea de si la eficiencia con la que se ejecuta
un programa es razonable o no y los posibles motivos por los que el
rendimiento no es óptimo.

En esta sección mostraremos algunas técnicas básicas, para
que un programa se aproxime al rendimiento ideal en un sistema
monoprocesador

● El procesador de un

SMP con ocho
“procesadores”
(Pwr5: 16 hilos de
ejecución, el SO los
ve como si fueran 16
CPUs) Power 5,
incluyendo la
jerarquia de memoria
hasta los 32MB de
cache L3

● 32-way Power 4

System Showing 4
MCMs and L3
Cache

Power 6

● Evolución de Power 4/5: mismas

ideas básicas.

● Aspectos destacados:

– Vuelven los incrementos

notables de la velocidad de
reloj (5 GHz)

– Baja disipación, con énfasis

en fiabilidad.

– Base tecnológica del

Power7, máquinas
multipetaflops. (PERCS:
Productive, Easy to Use,
Reliable Computing System)
– Duplica la velocidad de los
procesadores más rápidos
(con el mismo número de
cores, specfp2006, en el
momento de su presentación:
Agosto 07)

(50 GB/s)

● Creación de “Virtual Vector Architecture” concatenando varios
Power6
● Soporte de aritmética decimal: IBM quiere servir con un sólo diseño
de CPU a todas las series de ordenadores (incluyendo la zSeries de
uso financiero). Se incluye también en “blades”.

8 cores/chip
4 FPUs/core
1 vector unit

Optoelectronical comm-
unications module.
1128 GB/sec

32 cores/Multichip module
1 Tflop. 800 Watt power consumption
1.28 Gflops/Watt (double than
Current best Intel quadcore)

1200 Mill. Transistors.
32KB L1 D, 256 KB L2
80 MB L3 (shared 8 cores)

Power 7

Blade, Water cooled

* Also a 16 cores version
* Each core 4 ways SMT

* First servers mid 2014 (e.g. 32 TB, 384 cores, 3082 threads).
* First version 12 cores “only”: More memory, less cores...
* Each core 8 ways SMT
* On Chip PCI-express 3 controllers with coherent memory
protocols to External accelerators (CAPI). Generic
“upgradeable” memory contoller (integrated with L4)
* Memory hierarchy to L4 cache
* Expect ~3000 mill. Transistors.
* 4 FPU, 2 VMX vector math units.
* One cryptographic unit

Power 8

~3000 Mill. Transistors.
*64KB L1 D, L1 to L2 bus 64 bits
(double Pwr7) 512 KB L2
*Better prefetching.
* 96 MB L3 (shared 12 cores,
8 MB/Core), segmented, better protocol
* Up to 128 MB L4 cache
* L4->L3 128 GB/s; L3->L4 96 GB/s
* L2-> core 256 GB/s; core->L2 64 GB
* 4 TB/sec L2 bandwidth (12 cores)
* 3 TB/sec L3 bandwidth (12 cores)
* Approx 2.5x Power7 performance.
* 410 GB/s DRAM bandwidth

OpenPower licensing initiative

Intel.

● En el segmento de las
CPUs para consumo
masivo.
– Más cores:

Quadcores por 600 €
– Más cuidado con la
potencia disipa