GPU-Accelerated Bulk Execution of Multiple-Length Multiplication with Warp-Synchronous Programming Technique

Takumi HONDA  Yasuaki ITO  Koji NAKANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.12   pp.3004-3012
Publication Date: 2016/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016PAP0027
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
Category: GPU computing
multiple-length multiplication,  GPU,  GPGPU,  parallel processing,  warp-synchronous,  

Full Text: PDF(523KB)>>
Buy this Article

In this paper, we present a GPU implementation of bulk multiple-length multiplications. The idea of our GPU implementation is to adopt a warp-synchronous programming technique. We assign each multiple-length multiplication to one warp that consists of 32 threads. In parallel processing using multiple threads, usually, it is costly to synchronize execution of threads and communicate within threads. In warp-synchronous programming technique, however, execution of threads in a warp can be synchronized instruction by instruction without any barrier synchronous operations. Also, inter-thread communication can be performed by warp shuffle functions without accessing shared memory. The experimental results show that our GPU implementation on NVIDIA GeForce GTX 980 attains a speed-up factor of 52 for 1024-bit multiple-length multiplication over the sequential CPU implementation. Moreover, we use this 1024-bit multiple-length multiplication for larger size of bits as a sub-routine. The GPU implementation attains a speed-up factor of 21 for 65536-bit multiple-length multiplication.