Download Caché de último nivel parcialmente compartida

Caché de último nivel parcialmente
compartida basada en distancia
Antonio García-Guirado
1
1
1
1
Ricardo Fernández-Pascual Alberto Ros José M. García
Tiled-CMP de 64 núcleos
L1
Controlador
de memoria
Controlador
de memoria
Controlador
de memoria
Núcleo
Controlador
de memoria
Controlador
de memoria
Banco de L2
Controlador
de memoria
Controlador
de memoria
Estructura de una celda
Controlador
de memoria
Es común
queunaloscaché
multiprocesadores
en
un
chip
(CMPs)
utilicen
de
último
nivel
(LLC)
parcialmente
compartida
ya que deestaacceso
opcióny
proporciona
un
equilibrio
entre
latencia
aprovechamiento
de la capacidad
de almacenamiento.
En
este
trabajo
proponemos
una
nueva
manera
dequema-se
pear
direcciones
de
memoria
a
bancos
de
LLC
basa
en laa distancia
entre los bancos
y enfoques
los núcleostradique
acceden
ellos.
Al
contrario
que
los
cionales,
nuestrolosmapeo
noLLCcreaquegrupos
departe
núcleos
que
comparten
bancos
forman
del
grupo,
sino
que
cada
núcleo
accede
a
un
grupo
distintorecorrida
de bancos
cercanos,
reduciendo
la distancia
media
en
los
accesos
a
la
LLC.
Los
resultados
para
un
CMP
de
64
núcleos
indican
que
nuestra
propuesta
mejora
el tiempo
ejecución ycon
el usoun demapeo
energía
de
lacional.
red unAdemás,
13% enlosdecomparación
tradicostes
de implementar
esta propuesta
en
hardware
son
insignicantes
y
sus
benecios
aumentan a la vez que el número de núcleos.
Resumen
Interfaz de red
Fig. 1.
Diagrama de un tiled-CMP de 64 núcleos con cuatro
clusters de 16 núcleos. La líneas de puntos separan los 4
clusters de tiles que comparten sus bancos de LLC.
En este trabajo describimos nuestra propuesta
DAPSCO (Distance-Aware Partially Shared Cache
I. Introducción
L
OS tiled-CMPs (CMPs basados en celdas) son
actualmente la mejor manera de mantener viva
la ley de Moore gracias a su baja complejidad de
diseño comparada con la de otras alternativas y a
la facilidad para incrementar el número de núcleos
añadiendo más tiles (celdas).
En un tiled-CMP, los bancos del último nivel
de caché (LLC) físicamente están distribuidos uni-
Organization) que consiste en usar un mapeo estático distinto para cada núcleo, de manera que cada
núcleo acceda a los bancos de LLC que le rodean. El
mapeo sigue siendo estático, con lo que los cambios
necesarios en el hardware son simples e introducen
una sobrecarga insignicante. DAPSCO reduce notablemente la latencia de acceso a la LLC y mejora
el tiempo de ejecución (13 %) y el consumo de energía
de la red (13 %).
formemente por el chip, aunque lógicamente distintas organizaciones son posibles, desde una LLC totalmente privada hasta una totalmente compartida,
para intentar reducir la latencia de la LLC o el
número de costosos accesos a la memoria fuera del
chip [1], respectivamente. Las organizaciones intermedias [2, 3, 4], en las que se crean clusters de núcleos que comparten sus bancos de LLC (ver Figura 1) proporcionan un buen equilibrio entre estas dos
alternativas extremas.
En un CMP con una LLC (parcialmente) compartida, la latencia y la energía necesarias para resolver
las peticiones a la LLC representan un porcentaje
importante del tiempo de ejecución y la energía consumida por el chip. Tanto la latencia como la energía
dependen directamente de la distancia entre el núcleo
que accede y el banco de LLC accedido.
La organización tradicional de LLC no tiene en
cuenta la distancia entre un núcleo y los bancos que
accede. De hecho, existen grandes diferencias entre
distintos núcleos del mismo cluster. En promedio, los
núcleos en el centro del cluster ven los bancos más
cerca que los núcleos en los bordes o esquinas, por lo
que éstos últimos salen perjudicados.
1 Universidad de Murcia, e-mail:
jmgarcia}@ditec.um.es.
{toni, rfernandez, aros,
II. Background
Las arquitecturas objeto de nuestra propuesta son
los tiled-CMPs como los de la Figura 1. Cada tile
contiene un núcleo, cachés L1 privadas de datos e
instrucciones, un banco de la LLC (L2) y una interfaz de red para comunicación con otros tiles. Clusters de núcleos comparten sus bancos de LLC. Usaremos el término grado de compartición para denotar
el número de núcleos que acceden a cada banco de la
LLC. Para la coherencia de caché se usa un protocolo
MOESI.
El mapeo de bloques de memoria a bancos de LLC
se suele realizar usando algunos bits de la dirección
(log2
gc
bits, donde
gc
es el grado de compartición)
como puede verse en la Figura 2. Se utiliza un directorio para mantener la coherencia de caché entre
clusters.
A. Coherencia de caché
En una LLC parcialmente compartida son necesarios dos niveles de coherencia: un primer nivel para
mantener la coherencia entre las cachés privadas de
un cluster, y un segundo nivel para mantener la coherencia entre los bancos de caché de distintos clusters. Asumimos una caché de directorio distribuida
por dirección en los bancos de LLC para el primer
Direccion de memoria
3 2.5 2.5
Tag
Selector de Banco
0
1
2
...
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
Set index
Selector de Banco Banco de LLC
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
15
Fig. 2.
Block offset
000000
000001
000010
000011
001000
001001
001010
001011
010000
010001
010010
010011
011000
011001
011010
011011
3
3 2.5 2.5
3
2.5
2
2 2.5 2.5
2
2 2.5
2.5
2
2 2.5 2.5
2
2 2.5
3 2.5 2.5
3
3 2.5 2.5
3
3 2.5 2.5
3
3 2.5 2.5
3
2.5
2
2 2.5 2.5
2
2 2.5
2.5
2
2 2.5 2.5
2
2 2.5
3 2.5 2.5
3
3 2.5 2.5
3
Fig. 3. Distancia media en número de enlaces de cada núcleo
a los bancos de LLC accedidos en un CMP con 64 núcleos
y 4 clusters (grado de compartición de 16).
Seleción de banco en uno de los clusters de una LLC
parcialmente compartida con gc de 16. Los 16 núcleos de
cada cluster comparten sus bancos de LLC. Los números
en los tiles representan sus identicadores.
de los fallos encuentran el dato en otro cluster o en
memoria.
Es por ello que la latencia media de los fallos de
TABLA I
L1 está determinada principalmente por la distancia
Overhead de la información de compartición sobre la
entre el núcleo y el banco de LLC del cluster en que
capacidad de caché del chip.
se encuentra el dato. Por tanto, el mapeo de bloques
Núcleos
a bancos de LLC es clave para mejorar el rendimien-
Grado de compartición
1
2
4
8
16
32
64
44 %
22 %
11 %
6.3 %
4.2 %
4.2 %
5.6 %
128
89 %
45 %
23 %
12 %
7%
5.6 %
6.9 %
11 %
256
178 %
89 %
45 %
23 %
13 %
8.3 %
8.3 %
13 %
22 %
512
356 %
178 %
89 %
45 %
24 %
14 %
11 %
14 %
24 %
64
128
256
512
to del CMP, ya que determina la distancia de cada
núcleo a los bancos de LLC que accede.
Las cachés parcialmente compartidas no hacen na-
44 %
da para reducir esta distancia. Los núcleos se agrupan en clusters dando lugar a accesos a la LLC con
nivel de coherencia y una caché de directorio distribuida entre los controladores de memoria para el
segundo nivel. Ocho controladores de memoria se
reparten por los bordes del chip y las direcciones de
memoria se distribuyen entre ellos.
El directorio necesario para una LLC parcialmente
compartida supone una sobrecarga menor que para
una LLC privada o totalmente compartida, debido a
que las entradas de directorio son más pequeñas. El
primer nivel de coherencia necesita entradas con tantos bits como L1s acceden al banco de LLC (es decir,
el grado de compartición), y el segundo nivel necesita tantos bits como clusters existen. Sin embargo,
una LLC privada o totalmente compartida necesita
entradas con tantos bits como núcleos hay en el chip,
latencias largas. Como ejemplo, la Figura 3 muestra
la distancia media en número de enlaces de cada núcleo a los bancos de LLC que accede. Conforme nos
acercamos a los bordes del cluster la distancia media del núcleo a la LLC aumenta, y esta diferencia
se hace mayor cuanto mayor es el grado de compartición.
Este tipo de LLC parcialmente compartida tenía
sentido cuando cada cluster de núcleos se encontraba
en un chip distinto, ya que acceder a los bancos de
LLC dentro del chip era mucho menos costoso. Sin
embargo, en un escenario de many-core CMPs todos
los núcleos se encuentran en el mismo chip, por lo
que una organización parcialmente compartida como
ésta no optimiza el acceso a los bancos de LLC.
es decir, entradas de mayor tamaño.
III. DAPSCO: Distance-Aware Partially
La Tabla I muestra el overhead de los vectores
de
compartición
para
distintos
números
de
Shared Cache Organization
nú-
cleos y grados de compartición, suponiendo siempre
una caché de directorio poco densa con un sobreaprovisionamiento de 4× y bancos de LLC (L2) con
un tamaño ocho veces superior al de un banco de L1.
El menor overhead suele encontrarse en una organización con grado de compartición intermedio.
B. Mapeo de bloques y distancia a la LLC
Una organización de LLC con grado de compartición
g
está denida por dos elementos. El primero
son las relaciones de acceso entre núcleos y bancos de
LLC, accediendo cada núcleo a
g
bancos de LLC y
siendo cada banco accedido a su vez por
g núcleos. El
segundo elemento es la asignación de una parte igual
a
1/g
del espacio de memoria a cada banco, de forma
que varios bancos almacenan bloques de cada una de
estas partes. Para que la organización funcione cada
La LLC actúa como la última barrera para evi-
núcleo debe ser capaz de acceder a todo el espacio
tar costosos accesos a memoria principal. Para tener
de memoria a través de los bancos de LLC a los que
buen rendimiento la tasa de fallos de la LLC debe
tiene acceso.
ser muy baja, por lo que los fallos en L1 deben re-
La idea principal de DAPSCO consiste en permitir
solverse obteniendo el dato del banco de LLC desea-
a cada núcleo acceder a un conjunto distinto de los
do. Nuestros experimentos con benchmarks variados
bancos de LLC, de modo que podamos hacer que
muestran que, de media, más del 70 % de los fallos de
cada núcleo acceda a bancos cercanos, como puede
L1 se resuelven con un acceso a un banco de la LLC
observarse en la Figura 4. Para conseguir esto, la
dentro del cluster, más de un 10 % con una trans-
función de mapeo que determina el banco de LLC
ferencia caché a caché dentro del cluster, y el resto
que almacena un bloque debe ser distinta en cada
Grado de Comparticion 8
Grado de Comparticion 16
Tradicional
DAPSCO
Tradicional
DAPSCO
0
1
2
3
0
1
2
3
5
2
1
0
7
3
6
4
0
1
2
3
0
1
2
3
6
1
9
14 11
3
4
8
4
5
6
7
4
6
7
7
4
3
6
2
0
1
4
5
6
7
4
5
6
7
15
2
7
12 10
0
5
13
1
2
3
0
1
2
3
6
0
5
9
10 11
8
9
10 11
4
15
6
2
7
4
5
6
7
4
5
6
7
3
1
2
9
14 12
1
0
1
2
3
0
1
2
3
4
7
6
111
000
000
111
000
111
5
0
111
000
000
111
000
111
5
4
5
6
7
4
5
6
7
2
0
0
1
2
3
0
1
2
3
6
1
4
5
6
7
4
5
6
7
5
3
111
000
000
111
000
111
000
111
000
111
000
111
Numero medio de enlaces a la LLC
Media del chip
2 enlaces
2 enlaces
1.75 enlaces
2
3
11
00
00
11
00
11
0
1
5
6
7
4
9
10 11
8
4
1
3
7
2
8
7
0
4
6
5
12 13 14 15 12 13 14 15
3
5
2
1
0
0
1
5
1
4
6
7
3
4
7
2
3
0
2
4
8
4
0
6
7
5
1
11
00
00
11
000
111
000
111
000
111
000
111
111
000
000
111
1.25 enlaces
Media del chip
1.37 enlaces
11
00
00
11
00
11
00
11
5
8
3
1
11
00
00
11
00
11
13
4
10 11
3
5
12
2
5
6
7
7
14
6
11
7
8
0
9
10 11
3
9
0
10 12
5
3
9
8
13 15
4
2
14
6
Numero medio de enlaces a la LLC
1.75 enlaces
13
2
12 13 14 15 12 13 14 15
Numero medio de enlaces a la LLC
0
11 10
11
00
00
11
Numero medio de enlaces a la LLC
3 enlaces
3 enlaces
Media del chip
2.5 enlaces
1
15
11
00
00
11
00
11
00
11
Media del chip
2.81 enlaces
1.88 enlaces
2.14 enlaces
Grado de Comparticion 32
Tradicional
DAPSCO
0
1
2
7
24
6
10 28 18
2
8
9
10 11 12 13 14 15
11
7
12 21
23 20 19
16 17 18 19 20 21 22 23
0
13 31
24 25 26 27 28 29 30 31
5
14 25 15 26 16
0
1
2
7
16 27
8
9
10 11 12 13 14 15
30 17
16 17 18 19 20 21 22 23
19 20
11
00
00
11
000
111
000
111
000
111
000
111
3
3
4
4
5
5
6
111
000
000
111
000
111
6
24 25 26 27 28 29 30 31
Numero medio de enlaces a la LLC
Media del chip
Fig. 4.
5 enlaces
5 enlaces
3.88 enlaces
111
000
000
111
8
3
9
1
4
111
000
000
111
000
111
29 22 17 30
8
27
13 14
1
6
4
9
28 24 11 25
2
29 21 12
0
31
3
7
15
22 26 23 18
5
10
Numero medio de enlaces a la LLC
11
00
00
11
00
11
00
11
Media del chip
4.59 enlaces
3.44 enlaces
3.35 enlaces
Bancos de LLC accedidos por los núcleos de una malla. Cada núcleo rayado accede a los bancos sombreados que le
rodean. Los números en los tiles representan la porción del espacio de memoria servida por los bancos de LLC. Fíjese en que
cada núcleo siempre tiene acceso a todas las porciones del espacio de memoria. DAPSCO reduce notablemente el número
de enlaces medios recorridos para acceder a la LLC.
núcleo. Además, todos los núcleos que acceden a un
Operador A: dos bancos de LLC que almacenan
mismo banco deben acceder a la misma porción del
distintas porciones del espacio de memoria inter-
espacio de memoria a través de él.
cambian dichas porciones. Esto también implica
DAPSCO no modica el protocolo de coherencia
que los núcleos que accedían a uno de estos ban-
ni aumenta la sobrecarga de la información nece-
cos ahora deben acceder al otro para mantener
saria para mantener la coherencia en comparación
las restricción de que cada núcleo accede a todo
con las organizaciones de caché parcialmente com-
el espacio de memoria a través de la LLC.
partidas tradicionales, como mostraremos en la Sec-
Operador B: dos núcleos que acceden a dos ban-
ción III-B.
cos distintos de la LLC para la misma porción
Encontrar el DAPSCO óptimo para un número de
núcleos y un grado de compartición determinados es
del espacio de memoria intercambian estos dos
bancos.
un problema NP-completo, por lo que en este tra-
Es trivial demostrar que cualquier organización de
bajo usamos algoritmos heurísticos para encontrar
LLC resultante de la aplicación de estos operadores
conguraciones óptimas o cercanas a la óptima.
es válida, así como que cualquier organización válida puede obtenerse mediante la aplicación de una
A. Explorando el espacio de búsqueda de DAPSCO
secuencia adecuada de estos operadores.
B. Detalles de implementación
Para encontrar el mejor DAPSCO posible tanto
para mallas como para toros hemos utilizado dos
conocidos algoritmos de optimización global: ascen-
Para implementar DAPSCO sólo son necesarios los
siguientes cambios en el hardware ya existente:
sión de colinas y temple simulado. La metodología
1. La función que cada núcleo utiliza para mapear
explicada en esta sección es aplicable a cualquier
direcciones de memoria a bancos de LLC debe
topología. Estos algoritmos heurísticos comienzan
representar el mapeo de DAPSCO en lugar del
con la organización de LLC parcialmente compartida
tradicional.
tradicional en la que núcleos agrupados en clusters
2. La función que mapea los bits del primer nivel
comparten sus bancos de LLC. Los algoritmos gen-
de directorio a bancos de L1 debe concordar con
eran y evalúan nuevas organizaciones que surgen de
las relaciones de acceso de núcleos a bancos de
la aplicación de los siguientes dos operadores:
LLC de DAPSCO.
TABLA II
TABLA III
Tamaño de los circuitos de mapeo de dirección a
CMP simulado.
banco en DAPSCO para grado de compartición de 8.
Procesadores
Núcleos Número de transistores Máximo no de transispor tile
tores en el camino crítico
64
64
8
128
72
8
256
72
8
512
75
8
64 UltraSPARC-III+ 3 GHz.
2-vías, en orden.
L1 Cache
I&D Separadas. Tamaño: 64KB.
Asociatividad: 4-vías. 64 bytes/bloque.
Latencia: 1 ciclo.
L2 Cache
Tamaño: 1MB cada banco. 64MB total.
Asociatividad: 8-vías. 64 bytes/bloque.
Latencia: 2 (tag) + 3 (data) ciclos.
RAM
4 GB DRAM.
8 controladores en los bordes del chip.
Latencia: 150 ciclos + retardo on-chip.
3. La función que mapea los bits del segundo nivel
Interconexión
Malla bidimensional y toro 8x8.
16 bytes por enlace.
de directorio a bancos de LLC debe concordar
Latencia mesh: 2 ciclos/link. Toro: 4 ciclos/link.
con las asignaciones de fracciones de espacio de
memoria a bancos de LLC de DAPSCO.
Estas funciones se implementan como circuitos
combinacionales. Hemos generado el layout de todos
estos circuitos tanto para la organización tradicional
como para DAPSCO. En los casos (2) y (3) no existe diferencia en el número total de transistores ni
en la longitud del camino crítico de estos circuitos
entre la organización tradicional y DAPSCO. En el
caso (1) la organización tradicional utiliza directamente algunos bits de la dirección de memoria para
generar el identicador del banco de LLC a acceder,
mientras que en DAPSCO es necesario el uso de un
circuito que traduzca estos bits en el identicador.
La Tabla II muestra el número de transistores necesarios para realizar esta traducción en DAPSCO en
una malla con un grado de compartición igual a 8. El
consumo energético y el área ocupada por estos transistores es insignicante. Además, el número de transistores necesarios escala bien con el número de núcleos y la longitud del camino crítico se mantiene constante. La latencia de estos circuitos puede además
ocultarse si son accedidos en paralelo a los tags de
L1. Como conclusión, las modicaciones en el hardware necesarias para implementar DAPSCO no crean
ningún aumento de consumo, área o latencia.
IV. Evaluación
A. Efectividad de los DAPSCO hallados
mejores conguraciones encontradas por los algoritmos, tanto para mallas como para toros. Se muestran
tres valores distintos por topología: la organización
tradicional, una cota inferior y el mejor DAPSCO
encontrado. La cota inferior supone que cada núcleo
accede a los bancos de LLC que tiene más cerca, lo
cual normalmente no es posible en la práctica, ya que
si esto fuera así, los bancos en las esquinas y bordes
del chip serían accedidos por menos núcleos que los
bancos en el centro, dando lugar a una conguración
inválida. Incluimos esta cota para comprobar la efectividad de la búsqueda de DAPSCOs.
Un hecho importante es que, al aumentar el grado
de compartición, la distancia con la LLC aumenta
y la mejora relativa obtenida con DAPSCO también
aumenta. Por tanto, DAPSCO será más benecioso
para el rendimiento y el consumo de energía cuanto
mayor sea el grado de compartición ya que las latencias y consumos invariables (como los accesos a los
arrays de tags y datos de las cachés) suponen una
fracción menor del total y la comunicación con la
LLC supone una fracción mayor.
B. Metodología de simulación
Para
la
evaluación
hemos
usado
el
simulador
GEMS [5] para modelar un tiled-CMP cuyas características pueden verse en la Tabla III, los simu-
Para realizar la búsqueda de DAPSCOs utilizamos
ladores Garnet [6] y Orion [7] para modelar la red y
un algoritmo de ascensión de colinas y otro de temple
su consumo energético, y cargas tanto cientícas (lu,
simulado, como explicamos en la Sección III-A. Estos
lunc, tomcatv, volrend, watersp) como comerciales
algoritmos se ejecutaron repetidamente para varias
(apache y jbb).
combinaciones de grado de compartición y número
de núcleos, y seleccionamos la mejor solución encontrada para cada una de estas combinaciones. En total, los algoritmos se ejecutaron en un cluster de 268
núcleos (Intel Xeon a 2.33GHz en su mayoría) durante una semana. Los algoritmos se reiniciaban cada
vez que la generación de dos millones de nuevas organizaciones consecutivas no mejoraba la mejor solución encontrada por la ejecución actual del algoritmo.
Se implementaron algunas optimizaciones que mejoraron la eciencia de los algoritmos, tales como sólo
aplicar operadores que redujeran la distancia media
a la LLC de alguno de los núcleos afectados por el
operador para dirigir la búsqueda.
La Figura 5 muestra el número medio de enlaces
entre los núcleos y la LLC proporcionado por las
Hemos evaluado cuatro conguraciones distintas:
8Tradicional:
organización
de
caché
parcial-
mente compartida tradicional con grado de compartición de 8.
8DAPSCO: DAPSCO con grado de compartición de 8.
16Tradicional: organización de caché parcialmente compartida tradicional con grado de compartición de 16.
16DAPSCO: DAPSCO con grado de compartición de 16.
Hemos usado dos topologías de red distintas: malla y toro. Añadimos los sujos malla y toro a los
nombres de las cuatro conguraciones anteriores para
distinguir la topología utilizada.
Numero Medio de Enlaces a la LLC
12
malla base
malla mejor DAPSCO
malla cota optimista
toro base
toro mejor DAPSCO
toro cota optimista
10
8
6
4
2
0
64
6
6
1
1
1
1
2
2
2
2
2
2
5
5
5
5
5
5
5
6
1
/4 4/8 4/1 4/3 28/ 28/ 28/ 28/ 28/ 56/ 56/ 56/ 56/ 56/ 56/ 12/ 12/ 12/ 12/ 12/ 12/ 12/
6
8
16
32
64
4
8
16
32
64
12
4
8
16
32
64
12
25
2
4
8
8
6
Numero de Nucleos/Grado de Comparticion
Fig. 5.
Número medio de enlaces de los núcleos a los bancos de LLC. El eje x representa el número de núcleos en el chip (de
64 a 512) y el grado de compartición (de 4 a 256).
TABLA IV
Distancia media a la LLC Mejora sobre tradicional
(enlaces)
8TradicionalMalla
1.75
8DAPSCOMalla
1.37
16TradicionalMalla
2.5
16DAPSCOMalla
2.14
8TradicionalToro
1.75
8DAPSCOToro
1.25
16TradicionalToro
2.5
16DAPSCOToro
1.88
24 %
17 %
4p
33 %
8TradicionalMalla
8DAPSCOMalla
16TradicionalMalla
16DAPSCOMalla
3.0
2.0
1.0
0.0
Fig. 6.
4p
c6
lun
tom
4p
tv6
ca
p
p
64
nd
64
sp
ter
wa
Workload
lre
vo
ac
ap
4p
16TradicionalMalla
16DAPSCOMalla
c6
lun
4p
tv6
ca
tom
nd
p
64
p
64
sp
ter
wa
Workload
lre
vo
e
h
ac
ap
jbb
ge
era
Av
Fig. 8. Tiempo de ejecución normalizado usando una malla.
4.0
4p
8TradicionalMalla
8DAPSCOMalla
lu6
5.0
lu6
1.2
1.1
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
40 %
he
jbb
ge
era
Av
Tiempo de ejecución
Nº medio de enlaces atravesados
Conguración
Tiempo de ejecución
Distancia media de los núcleos a los bancos de LLC.
1.3
1.2
1.1
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
8TradicionalToro
8DAPSCOToro
4p
lu6
4p
c6
lun
16TradicionalToro
16DAPSCOToro
Número medio de enlaces atravesados para acceder a
4p
tv6
ca
tom
nd
lre
vo
p
64
p
64
sp
ter
wa
Workload
e
h
ac
ap
jbb
ge
era
Av
Fig. 9. Tiempo de ejecución normalizado usando un toro.
la LLC. Malla.
El número medio de enlaces para llegar a la LLC
en cada conguración se muestra en la Tabla IV.
corresponde al toro y un grado de compartición de
8, con un 40 %.
C. Resultados
La reducción en enlaces atravesados se traduce en
La mayor parte de los fallos de L1 se resuelven
mejoras en el tiempo de ejecución y en el consumo
obteniendo el dato de la LLC. Estos fallos se bene-
de energía de la red. Las Figuras 8 y 9 muestran
cian de la menor distancia a la LLC de DAPSCO.
el tiempo de ejecución de las ocho conguraciones
Las Figuras 6 y 7 muestran el número medio de en-
evaluadas. Al usar una malla el rendimiento del sis-
laces atravesados para resolver estos fallos usando
tema mejora un 4 % y un 6 % con DAPSCOs para
una malla o un toro. Estos resultados experimentales
grados de compartición de 8 y 16, respectivamente.
encajan con los valores medios de DAPSCO mostra-
Con el toro estas mejoras suben hasta un 10 % y
dos anteriormente en la Tabla IV. La máxima mejora
un 13 %, respectivamente. A pesar de que la reducción en número de enlaces es menor con un grado de
Nº medio de enlaces atravesados
compartición de 16 que con uno de 8, la ganancia en
8TradicionalToro
8DAPSCOToro
tiempo de ejecución de DAPSCO es mayor con el de
16TradicionalToro
16DAPSCOToro
16 ya que el porcentaje de latencia debido a atrav-
5.0
4.0
esar la red supone una fracción mayor del tiempo de
3.0
ejecución cuanto mayor es el grado de compartición.
2.0
Las Figuras 10 y 11 muestran el consumo de en-
1.0
ergía de la malla y del toro. De nuevo, gracias a la
0.0
Fig. 7.
4p
lu6
4p
c6
lun
tom
4p
tv6
ca
p
64
nd
lre
vo
p
64
sp
ter
wa
Workload
ac
ap
he
jbb
ge
era
Av
Número medio de enlaces atravesados para acceder a
la LLC. Toro.
reducción en número de enlaces y routers atravesados
para acceder a la LLC, la energía se reduce al usar
DAPSCO un 4 % y un 6 % con la malla y un 10 % y
un 13 % con el toro para grados de compartición de
Consumo de energía de la red
1.3
1.2
1.1
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
8TradicionalMalla
8DAPSCOMalla
CA mejora un 3 % de media (hasta un 7 %) al activar
16TradicionalMalla
16DAPSCOMalla
DAPSCO.
VI. Conclusiones
Hemos optimizado la organización de caché parcialmente compartida de los CMPs haciendo que calu6
4p
c6
lun
4p
4p
tv6
ca
tom
p
64
nd
lre
vo
sp
ter
wa
Workload
p
64
ac
ap
he
jbb
ge
era
Av
da núcleo acceda a bancos de LLC cercanos. Los
costes en hardware de la nueva organización son in-
Fig. 10. Consumo de energía normalizado de la malla.
signicantes y las mejoras obtenidas en tiempo de
ejecución y consumo de energía de la red en compara-
Consumo de energía de la red
ción con la organización tradicional son notables.
1.3
1.2
1.1
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
8TradicionalToro
8DAPSCOToro
16TradicionalToro
16DAPSCOToro
Hemos mostrado ejemplos que mejoran el rendimiento de un CMP de 64 núcleos en un 4 % y un 6 %
al usar una malla y un 10 % y un 13 % al usar un
toro con respecto a la organización tradicional. El
consumo de energía de la red también se reduce de
manera similar. También hemos mostrado como al
lu6
4p
p
64
c
lun
c
tom
4p
6
atv
l
vo
p
64
d
ren
sp
ter
p
64
wa
Workload
e
ch
a
ap
jbb
ge
ra
ve
A
aumentar el número de núcleos y el grado de compartición los benecios son aún más considerables.
Fig. 11. Consumo de energía normalizado del toro.
8 y 16, respectivamente. Estos resultados muestran
la efectividad de DAPSCO.
No obstante, el potencial de DAPSCO aumentará
conforme aumente el número de núcleos y el grado de
compartición ya que la reducción de enlaces atravesados en el acceso a la LLC tendrá mayor impacto en
Agradecimientos
Este trabajo ha sido nanciado por el MEC y
la Comisión Europea FEDER mediante los proyectos
Consolider
Ingenio-2010
TIN2009-14475-C04-02.
DAPSCO es ortogonal a otras propuestas que utilizan cachés parcialmente compartidas, como Reactive NUCA [8]. Reactive NUCA se basa en clasicar
dinámicamente cada bloque en uno de varios tipos
de bloque predeterminados (instrucciones, datos privados y datos compartidos), y en aplicar un grado de
compartición distinto predeterminado a cada uno de
estos tipos de bloque para mejorar el rendimiento.
Hemos aplicado Reactive NUCA a un CMP de 64
núcleos con una malla, y mediante tests exhaustivos
hemos determinado que los mejores grados de compartición son: cuatro para instrucciones, uno para
y
García-Guirado
también es beneciario de una beca FPU del MEC
(FPU AP2008-04387).
Referencias
el tiempo de ejecución y el consumo de la red.
V. Ortogonalidad de DAPSCO
CSD2006-00046
Antonio
[1] Chun Liu, Anand Sivasubramaniam, and Mahmut Kandemir, Organizing the Last Line of Defense before Hitting
Proceedings of the 10th
International Symposium on High Performance Computer Architecture (HPCA), 2004, pp. 176185.
the Memory Wall for CMPs, in
[2] B. A. Nayfeh, K. Olukotun, and J. P. Singh,
The Im-
pact of Shared-Cache Clustering in Small-Scale Shared-
Proceedings of the 2nd IEEE
Symposium on High-Performance Computer Architecture
(HPCA), 1996, pp. 7484.
Memory Multiprocessors, in
[3] Jaehyuk Huh, Changkyu Kim, Hazim Sha, Lixin Zhang,
Doug Burger, and Stephen W. Keckler, A NUCA Subin Proceedings
of the 19th annual international conference on Supercomputing (ICS), 2005, pp. 3140.
strate for Flexible CMP Cache Sharing,
[4] Mohammad Hammoud, Sangyeun Cho, and Rami Melhem,
Dynamic Cache Clustering for Chip Multiproces-
Proceedings of the 23rd International Conference
on Supercomputing (ICS), 2009, pp. 5667.
sors, in
datos privados y ocho para datos compartidos. Poste-
[5] Milo M. K. Martin, Daniel J. Sorin, Bradford M. Beck-
riormente, hemos sustituido la organización de caché
mann, Michael R. Marty, Min Xu, Alaa R. Alameldeen,
parcialmente compartida de Reactive NUCA por
DAPSCO. La Figura 12 muestra la comparativa de
rendimiento entre Reactive NUCA y Reactive NUCA más DAPSCO. El rendimiento de Reactive NU-
Kevin E. Moore, Mark D. Hill, and David A. Wood, Multifacet's general execution-driven multiprocessor simulator
(GEMS) toolset,
SIGARCH Comput. Archit. News, vol.
33, no. 4, pp. 9299, 2005.
[6] Niket Agarwal, Tushar Krishna, Li-Shiuan Peh, and Niraj K. Jha,
GARNET: A Detailed On-Chip Network
in International Symposium on Performance Analysis of Systems and
Software (ISPASS), 2009, pp. 3342.
Model Inside a Full-System Simulator,
1.1
RNUCA
DAPSCO-RNUCA
[7] Andrew B. Kahng, Bin Li, Li-Shiuan Peh, and Kambiz
1.0
Samadi, ORION 2.0: a Fast and Accurate NoC Power and
Tiempo de ejecución
0.9
Area Model for Early-Stage Design Space Exploration, in
0.8
0.6
Proceedings of the Conference on Design, Automation and
Test in Europe (DATE), 2009, pp. 423428.
0.5
[8] Nikos Hardavellas, Michael Ferdman, Babak Falsa, and
0.7
0.4
Anastasia Ailamaki,
0.3
Reactive NUCA: Near-Optimal
Block Placement and Replication in Distributed Caches,
0.2
Proceedings of the 36th Annual International Symposium on Computer architecture (ISCA), 2009, pp. 184
in
0.1
0.0
lu6
4p
64
c
lun
p
p
4
tv6
ca
tom
4p
6
nd
lre
vo
p
64
sp
ter
wa
he
ac
ap
jbb
ge
era
Av
Workload
Fig. 12. Rendimiento de Reactive NUCA sin y con DAPSCO.
195.