Improving memory access efficiency for real-time rendering in tile-based GPU architectures

Abstract

(English) Following the growing demands of applications mobile GPUs have greatly evolved in the past decade with expectations for continued advancement. These developments must address the rising performance demands and prioritize energy efficiency to accommodate the energy and temperature constraints of battery-powered, handheld devices. Main memory accesses are one of the main sources of energy consumption and occasionally a source of performance bottleneck in GPUs. The adoption of Tile-Based Rendering (TBR) architecture for many mobile GPUs in the late 1990s, marks a leap towards energy efficiency for mobile GPUs by enhancing locality and minimizing bandwidth-intensive memory accesses. The objective of this thesis is to enhance memory access efficiency in TBR GPU architectures for graphics applications. The strategy involves fine-tuning the structures in the memory hierarchy or altering the memory access patterns directed towards the memory hierarchy. By capitalizing on the unique characteristics of graphics applications, the goal is to boost both performance and energy efficiency with minimal hardware adjustments, thereby avoiding any adverse impact on general-purpose workloads running on GPUs. TBR architectures introduce an overhead through the creation of a specialized data structure for tiling which is stored in memory and cached in L1 and shared L2 caches. The OPT replacement policy, has been formally proven as optimal for minimizing misses but it is near-impossible to implement in hardware. The first proposal in this thesis brings the OPT to life, for this data structure. Along with other improvements in the L2, this proposal called TCOR results in a 13.8% decrease in the memory hierarchy energy consumption and an increased throughput in the Tiling Engine. DTexL, the second proposal in this thesis, increases the aggregated capacity of certain L1 caches by reducing replication of memory blocks. Contemporary GPUs have multiple GPU cores and a scheduler that distributes work (warps) among them, focusing on load balancing. These load balancing techniques are detrimental to texture memory locality in the L1 caches. We propose a new workload scheduler that favours texture locality and to overcome the resulting load imbalance, we propose a minor modification to the GPU architecture. DTexL results in a 46.8% decrease in L2 Accesses, a 19.3% increase in performance and a 6.3% decrease in total GPU energy. All this with a negligible overhead. Literature is plentiful in works exploiting cache locality for GPUs. A majority of them explore replacement or bypassing policies. In our third proposal, we surpass this exploration by fabricating a formal proof for a no-overhead quasi-optimal caching technique in the shared L2 for textures. We exploit the frame-to-frame reuse of textures by traversing frames in a boustrophedonic manner w.r.t. the conventional frame-to-frame tile order. We first approximate the texture access trace to a circular trace and then forge a formal proof for our proposal being optimal for such traces. We call our proposal Boustrophedonic Frames. Hiding memory latency is becoming a problem in contemporary GPUs. To address this challenge, we introduce WaSP as the final work in this thesis, a lightweight warp scheduler tailored for GPUs in graphics applications. WaSP strategically mimics prefetching by initiating a select subset of warps, termed priority warps, early in execution to reduce memory latency for subsequent warps. WaSP reduces average memory latency while maintaining locality for the majority of warps. While maximizing memory parallelism utilization, WaSP prevents saturating the caches with misses to avoid filling up the MSHRs. This approach reduces cache stalls that halt further accesses to the cache. Overall, WaSP yields a 3.9% performance speedup with a negligible overhead.

(Català) De resultes dels creixents requeriments de les aplicacions, les GPUs per a mòbils han evolucionat enormement en la passada dècada, i s'espera que continuïn progressant. Aquests desenvolupaments han de donar resposta a exigències de rendiment creixents i han de prioritzar l'eficiència energètica per cenyir-se a les restriccions d'energia i temperatura de dispositius portàtils alimentats per bateries. Els accessos a memòria principal de les GPUs són una de les majors fonts de consum d'energia i ocasionalment la causa de colls d'ampolla del rendiment. L'objectiu d'aquesta tesi és millorar l'eficiència en l'accés a memòria d'una GPU amb arquitectura del tipus Tile-Base Rendering (TBR) per a aplicacions gràfiques (habitual en GPUs per a mòbils) Les arquitectures TBR introdueixen un cost afegit ja que requereixen una estructura de dades especialitzada per al "tiling", la qual s'emmagatzema en memòria i s’hi accedeix per mitjà d'una memòria cau L1 i una L2 compartida. La política de reemplaçament OPT ha estat formalment demostrada òptima per a minimitzar fallades però és quasi impossible d'implementar en hardware. La primera proposta d'aquesta tesi dona vida a OPT per a aquesta estructura de dades. Juntament amb altres millores de la L2, aquesta proposta anomenada TCOR produeix una reducció del 13,8% en l'energia consumida per la jerarquia de memòria, i un augment de productivitat en el Tiling Engine. DTexL, la segona proposta d'aquesta tesi, augmenta la capacitat agregada de certes memòries cau L1 reduint-hi la replicació de blocs de memòria. Les GPUs contemporànies tenen múltiples nuclis i un planificador que distribueix les tasques (warps) entre ells centrant-se en equilibrar la càrrega. Aquestes tècniques d'equilibri de càrrega perjudiquen la localitat de les textures a les memòries cau L1. Nosaltres proposem un nou planificador de tasques per afavorir la localitat de les textures, així com una petita modificació de l'arquitectura per tal de vèncer el desequilibri de càrrega resultant. DTexL resulta en una reducció del 46,8% dels accessos a L2, un 19,3% d'augment del rendiment i un 6,3% de reducció de l'energia total de la GPU. Tot això amb un cost addicional insignificant. La literatura és plena de treballs que exploten la localitat en GPUs. La majoria exploren polítiques de reemplaçament o de bypass. En la nostra tercera proposta anem més enllà d'aquesta exploració inventant una demostració formal d'una tècnica sense cost i quasi òptima per a textures a la L2 compartida. Explotem la reutilització de textures entre fotogrames per mitjà de recórrer-los en ordre bustrofèdic en comptes de l'ordre convencional dels tiles fotograma a fotograma. Primer aproximem la traça dels accessos a textures a una traça circular, i llavors demostrem formalment que la nostra proposta és òptima per a tals traces. La nostra proposta l'anomenem Boustrophedonic Frames. Ocultar la latència de memòria està esdevenint un problema en les GPUs actuals. Per encarar aquest repte, introduïm WaSP com a darrer treball d'aquesta tesi, un planificador de tasques lleuger fet a mida per a GPUs en aplicacions gràfiques. WaSP imita estratègicament una prebúsqueda tot iniciant precoçment l'execució d'un subgrup seleccionat de warps, que anomenem prioritaris, per tal de reduir la latència dels warps subsegüents. Alhora que es maximitza el paral·lelisme en l'ús de la memòria, WaSP prevé la saturació de les memòries cau amb fallades per evitar que s'omplin els MSHRs. Aquest enfoc redueix les parades de la memòria cau que n'aturarien posteriors accessos. En general, WaSP produeix un guany de rendiment del 3,9% amb un cost addicional insignificant.

(Español) Las GPU móviles han evolucionado enormemente en la última década debido a la continua demanda de las aplicaciones. Estos diseños deben abordar la creciente demanda de rendimiento y priorizar la eficiencia energética para adaptarse a las limitaciones de energía y temperatura de los dispositivos móviles. La memoria principal es una de las principales fuentes de consumo de energía y, en muchas ocasiones, llega a convertirse en el principal cuello de botella que limita el rendimiento de las GPUs. El objetivo de esta tesis es mejorar la eficiencia de los accesos a memoria en arquitecturas Tile-Based Rendering (TBR), que son las que implementan las GPU móviles, para la ejecución de aplicaciones gráficas. Las arquitecturas TBR utilizan una estructura de datos que almacena la información de las primitivas de cada región (tile) de la pantalla, que reside en la memoria principal y en la caché L1 (Tile Cache) y en la L2 compartida. Se ha demostrado que la política de reemplazo OPT es óptima para minimizar los fallos de caché pero es casi imposible de implementar en hardware. La primera propuesta de esta tesis da vida a la política OPT y la incorpora en la Tile Cache. Junto con otras mejoras en la L2, esta propuesta, denominada TCOR, resulta en una disminución del 13,8% en el consumo de energía de la jerarquía de memoria y un mayor rendimiento del Tiling Engine. DTexL, la segunda propuesta de esta tesis, aumenta la capacidad agregada de las cachés de texturas, al reducir la replicación de los bloques de memoria que éstas almacenan. Las GPU modernas integran múltiples núcleos junto a un planificador que distribuye el trabajo (en forma de warps) entre ellos, tratando de equilibrar la carga de trabajo. Sin embargo, estas técnicas de balanceo de la carga son contraproducentes para la localidad de los bloques almacenados en las cachés de texturas. Se ha propuesto un nuevo planificador que favorece la localidad de las texturas y, para compensar el desequilibrio de la carga resultante, se propone una modificación menor en la arquitectura de la GPU. DTexL da resulta en una disminución del 46,8% en los accesos a la L2, un aumento del 19,3% en el rendimiento y una disminución del 6,3% en la energía total de la GPU. Todo ello, con unos sobrecostes insignificantes. En la literatura existen muchos trabajos que explotan la localidad de las cachés de las GPUs, la mayoría de ellos enfocados en las políticas de reemplazo. En la tercera propuesta, se realiza una prueba formal de una técnica de almacenamiento de las texturas en la L2 compartida cuasi óptima, con un sobrecoste nulo. Explota la reutilización de texturas de un fotograma al siguiente, para lo que se recorren los fotogramas de forma “boustrofedónica” en lugar de usar el recorrido convencional de los tiles por filas (o en Z-order). En primer lugar, se aproxima la traza de acceso a texturas a una traza circular y se demuestra formalmente que la propuesta es óptima para este tipo de trazas. Ocultar la latencia de la memoria se está convirtiendo en un problema en las GPU contemporáneas. Para abordar este reto, presentamos como trabajo final de esta tesis el mecanismo denominado WaSP, que consiste en un planificador de warps ligero para GPUs y centrado en la ejecución de aplicaciones gráficas. WaSP imita a los mecanismos de pre-búsqueda tradicionales ya que lanza un subconjunto warps, elegidos de forma estratégica y denominados warps prioritarios, al comienzo de la ejecución para reducir la latencia de memoria de los warps siguientes. La propuesta reduce la latencia media de la memoria gracias a preservar la localidad para la mayoría de los warps. Al tiempo que maximiza la utilización del paralelismo de memoria (MLP), WaSP reduce los fallos de las cachés para evitar llenar sus MSHRs. Gracias a esto, se reducen las detenciones de dichas cachés que acabarían frenando los accesos posteriores. En conjunto, WaSP consigue una mejora del rendimiento del 3,9% con una sobrecarga insignificante.