Spare register aware prefetching for graph algorithms on GPUs
Spare register aware prefetching for graph algorithms on GPUs
复制标题
DOI：
10.1109/hpca.2014.6835970
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
Nagesh B. Lakshminarayana;Hyesoon Kim
中科院分区：
文献类型：
--
作者：
Nagesh B. Lakshminarayana;Hyesoon Kim
越来越多的图形算法正在支持GPU。图形算法在GPU上的实现具有不规则的控制流，并且是存储器密集型的，具有许多不规则/数据依赖的存储器访问。由于这些因素，图形算法在GPU上的执行效率很低。在这项工作中，我们提出了一种机制，以提高执行效率的图形算法，提高其内存访问延迟容忍。我们提出了一种机制，用于预取数据的负载对，有一个负载依赖于其他-这种对是常见的图形算法。我们的机制检测硬件中的目标负载，并将指令注入流水线，以将数据预取到未被任何活动线程使用的备用寄存器中。通过将数据预取到寄存器中，可以消除预取数据的早期驱逐。我们还提出了一种机制，使用编译器来识别目标负载。我们的机制提高了性能，没有预取平均10%，高达51%的9个内存密集型图形算法内核。
More and more graph algorithms are being GPU enabled. Graph algorithm implementations on GPUs have irregular control flow and are memory-intensive with many irregular/data-dependent memory accesses. Due to these factors graph algorithms on GPUs have low execution efficiency. In this work we propose a mechanism to improve the execution efficiency of graph algorithms by improving their memory access latency tolerance. We propose a mechanism for prefetching data for load pairs that have one load dependent on the other - such pairs are common in graph algorithms. Our mechanism detects the target loads in hardware and injects instructions into the pipeline to prefetch data into spare registers that are not being used by any active threads. By prefetching data into registers, early eviction of prefetched data can be eliminated. We also propose a mechanism that uses the compiler to identify the target loads. Our mechanism improves performance over no prefetching by 10% on average and upto 51% for nine memory intensive graph algorithm kernels.