Researchers from both academia and industry agree that future CMPs will accommodate large shared on-chip last-level caches.
However, the exponential increase in multicore processor cache sizes accompanied by growing on-chip wire delays make it difficult
to implement traditional caches with a single, uniform access latency. Non-Uniform Cache Access (NUCA) designs have been
proposed to address this situation. A NUCA cache divides the whole cache memory into smaller banks that are distributed along the
chip and can be accessed independently. Response time in NUCA caches does not only depend on the latency of the actual bank,
but also on the time required to reach the bank that has the requested data and to send it to the core. So, the NUCA cache allows
those banks that are located next to the cores to have lower access latencies than the banks that are further away, thus mitigating
the effects of the cache’s internal wires.
These cache architectures have been traditionally classified based on their placement decisions as static (S-NUCA) or dynamic (DNUCA).
In this thesis, we have focused on D-NUCA as it exploits the dynamic features that NUCA caches offer, like data migration.
The flexibility that D-NUCA provides, however, raises new challenges that hardens the management of this kind of cache
architectures in CMP systems. We have identified these new challenges and tackled them from the point of view of the four NUCA
policies: replacement, access, placement and migration.
First, we focus on the challenges introduced by the replacement policy in D-NUCA. Data migration makes most frequently accessed
data blocks to be concentrated on the banks that are closer to the processors. This creates big differences in the average usage
rate of the NUCA banks, being the banks that are close to the processors the most accessed banks, while the banks that are further
away are not accessed so often. Upon a replacement in a particular bank of the NUCA cache, the probabilities of the evicted data
block to be reused by the program will differ if its last location in the NUCA cache was a bank that are close to the processors, or
not. The decentralized nature of NUCA, however, prevents a NUCA bank from knowing that other bank is constantly evicting data
blocks that are later being reused. We propose three different techniques to dealwith the replacement policy, being The Auction the
most successful one.
Then, we deal with the challenges in the access policy. As data blocks can be mapped in multiple banks within the NUCA cache.
Finding the requesting data in a D-NUCA cache is a difficult task. In addition, data can freely move between these banks, thus the
search scheme must look up all banks where the requesting data block can be mapped to ascertain if it is in the NUCA cache, or
not. We have proposed HK-NUCA. This is a search scheme that uses home knowledge to effectively reduce the average number of
messages introduced to the on-chip network to satisfy a memory request.
With regard to the placement policy, this thesis shows the implementation of a hybrid NUCA cache. We have proposed a novel
placement policy that accomodates both memory technologies, SRAM and eDRAM, in a single NUCA cache.
Finally, in order to deal with the migration policy in D-NUCA caches, we propose The Migration Prefetcher. This is a technique that
anticipates data migrations.
Summarizing, in this thesis we propose different techniques to efficiently manage future D-NUCA cache architectures on CMPs. We
demonstrate the effectivity of our techniques to deal with the challenges introduced by D-NUCA caches. Our techniques outperform
existing solutions in the literature, and are in most cases more energy efficient. / CMPs actuales integran memorias cache de último nivel cada vez más grandes dentro del chip. Roadmaps en la industria y
trabajos en ámbito académico muestran que esta tendencia seguirá en los próximos años. Sin embargo, los altos retrasos en la
red de interconexión y el cableado hace que sea cada vez más difícil de implementar memorias cachés tradicionales con una única
y uniforme latencia de acceso. Para solventar esta situación aparecieron los diseños NUCA (Non-Uniform Cache Access). Una
caché de tipo NUCA divide una memoria grande en bloques más pequeños que se distribuyen a lo largo del chip y pueden ser
accedidos de manera independiente. De esta manera el tiempo de respuesta en una caché NUCA no depende sólo de la latencia
de un banco, sino que también se tiene en cuenta el tiempo de enrutamiento de la petición hasta y desde el banco de la NUCA que
responde. La posición física de un banco en el chip es clave para determinar la latencia de acceso a NUCA, entonces bancos que
se encuentren más cerca de los cores tendrán menores latencias de acceso que otros que estén más alejados.
Las cachés NUCA se pueden clasificar como estáticas (S-NUCA) o dinámicas (D-NUCA), basándonos en sus decisiones de
emplazamiento. Esta tesis se centra en D-NUCA. Este diseño permite a un dato migrar de banco en banco a fín de reducir la
latencia de futuros accesos a ese dato, pero también ofrece otros retos que deben ser investigados para gestionar estas cachés de
manera eficiente. Hemos identificado y explorado estos retos desde el punto de vista de las cuatro políticas NUCA: reemplazo,
acceso, emplazamiento y migración.
En primer lugar nos hemos centrado en la política de reemplazo. La migración de datos permite que los datos que se utilizan más
frequentemente se concentren en aquellos bancos que estan más cerca de los cores. Ésto crea grandes diferencias en el uso
medio de los bancos en NUCA, siendo los bancos cercanos a los cores los más accedidos, mientras que los bancos lejanos no se
acceden tan a menudo. Debido a las diferencias en la frequencia de reemplazos entre bancos, las probabilidades de que el dato
expulsado sea reusado en un futuro crecerán o disminuirán dependiendo del banco donde se efectuó el reemplazo. Por otro lado,
los trabajos previos en la política de reemplazo no son efectivos en este tipo de cachés ya que los bancos trabajan de manera
independiente. Nosotros proponemos tres técnicas de reemplazo para NUCA, siendo The Auction la técnica con mayor beneficio.
En cuanto a los retos con la política de acceso, como los datos se pueden mapear en diversos bancos dentro de la caché NUCA,
encontrarlos se convierte en una tarea complicada y costosa. Aquí, nosotros proponemos HK-NUCA. Es un algoritmo de acceso
que usa el conocimiento integrado en los bancos "home" para reducir de manera eficiente el número medio de accesos necesarios
para resolver una petición de memoria.
Para analizar la política de emplazamiento, esta tesis muestra la implementación de una caché NUCA híbrida. Nuestra política de
emplazamiento permite integrar ambas tecnologías, SRAM y eDRAM, en un único nivel de cache NUCA.
Finalmente, en cuanto a la migración en D-NUCA, hemos propuesto The Migration Prefetcher. Es una técnica que permite anticipar
migraciones de datos usando el conocimiento adquirido por el historial de accesos.
En resumen, esta tesis propone diferentes técnicas para gestionar de manera eficiente las futuras arquitecturas de memoria caché
D-NUCA en un entorno CMP. A lo largo de la tesis, demostramos la efectividad de las técnicas propuestas para paliar los efectos
inducidos por el hecho de utilizar cachés D-NUCA. Estas técnicas, además de obtener mayor rendimiento que otros mecanismos
existentes en la literatura, son en muchos casos más eficientes en términos de energía.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/80381 |
| Date | 25 November 2011 |
| Creators | Lira Rueda, Javier |
| Contributors | González Colás, Antonio, Molina Clemente, Carlos, Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 169 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs. |
Page generated in 0.0031 seconds