Fast Multiplication in Binary Fields on GPUs via Register Cache
Fast Multiplication in Binary Fields on GPUs via Register Cache
复制标题
通过寄存器缓存在 GPU 上进行二进制字段的快速乘法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Eran Tromer
中科院分区：
文献类型：
--
作者：
Eli Ben;Matan Hamilis;M. Silberstein;Eran Tromer
特征2的有限字段 - “二进制字段” - 在密码和数据存储中的各种应用中使用。在许多这些应用中，两个有限场元素的乘法是一个基本操作，也是众所周知的计算瓶颈，因为它们通常需要大量元素的乘法。在这项工作中，我们着重于在大于232的“大”二进制二进制字段中加速乘法。我们设计了一种针对GPU上执行的新的并行算法。该算法使得可以繁殖大量有限的场元素，并通过位剪接和细粒并行化实现高性能。有效实现算法的关键是我们称为寄存器缓存的一种新颖的性能优化方法。此方法可以加快通过转换代码以使用每线程寄存器的代码来缓存其在共享内存中的输入的算法。我们展示了如何用Shuffle（）内部 - WARP通信指令替换共享内存访问，从而大大减少甚至消除共享内存访问。我们彻底分析了寄存器缓存方法，并表征其收益和局限性。我们将寄存器缓存方法应用于GPU上的二进制有限场乘法算法的实现。在流行的，高度优化的数字理论库（NTL）[26]上，我们最多达到了138倍的速度，它使用了专业的CLMUL CPU指令，超过30倍，对于2256以下的较大尺寸的较大字段。我们的寄存器缓存实现了。与传统的基于共享记忆的设计相比，启用高达50％的性能。
Finite fields of characteristic 2 -- "binary fields" -- are used in a variety of applications in cryptography and data storage. Multiplication of two finite field elements is a fundamental operation and a well-known computational bottleneck in many of these applications, as they often require multiplication of a large number of elements. In this work we focus on accelerating multiplication in "large" binary fields of sizes greater than 232. We devise a new parallel algorithm optimized for execution on GPUs. This algorithm makes it possible to multiply large number of finite field elements, and achieves high performance via bit-slicing and fine-grained parallelization. The key to the efficient implementation of the algorithm is a novel performance optimization methodology we call the register cache. This methodology speeds up an algorithm that caches its input in shared memory by transforming the code to use per-thread registers instead. We show how to replace shared memory accesses with the shuffle() intra-warp communication instruction, thereby significantly reducing or even eliminating shared memory accesses. We thoroughly analyze the register cache approach and characterize its benefits and limitations. We apply the register cache methodology to the implementation of the binary finite field multiplication algorithm on GPUs. We achieve up to 138x speedup for fields of size 232 over the popular, highly optimized Number Theory Library (NTL) [26], which uses the specialized CLMUL CPU instruction, and over 30x for larger fields of size below 2256. Our register cache implementation enables up to 50% higher performance compared to the traditional shared-memory based design.
DOI：
10.1145/2503210.2503268
发表时间：
2013-11
期刊：
2013 SC - International Conference for High Performance Computing, Networking, Storage and Analysis (SC)
影响因子：
--
作者：
A. Magni;Christophe Dubach;M. O’Boyle
通讯作者：
A. Magni;Christophe Dubach;M. O’Boyle