English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Efficient Multiplication of Polynomials on Graphics Hardware

Emeliyanenko, P. (2009). Efficient Multiplication of Polynomials on Graphics Hardware. In Dou, Yong, Gruber, Ralf, Joller, & Josef (Eds.), Advanced Parallel Processing Technologies (pp. 134-149). Berlin: Springer. doi:10.1007/978-3-642-03644-6_11.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-183A-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-4CE7-4
Genre: Conference Paper

Files

show Files
hide Files
:
gpgpu_mul.pdf (Any fulltext), 365KB
 
File Permalink:
-
Name:
gpgpu_mul.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Emeliyanenko, Pavel1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We present the algorithm to multiply univariate polynomials with integer coefficients efficiently using the Number Theoretic transform (NTT) on Graphics Processing Units (GPU). The same approach can be used to multiply large integers encoded as polynomials. Our algorithm exploits fused multiply-add capabilities of the graphics hardware. NTT multiplications are executed in parallel for a set of distinct primes followed by reconstruction using the Chinese Remainder theorem (CRT) on the GPU. Our benchmarking experiences show the NTT multiplication performance up to 77 GMul/s. We compared our approach with CPU-based implementations of polynomial and large integer multiplication provided by NTL and GMP libraries.

Details

show
hide
Language(s): eng - English
 Dates: 2009-09-2520092009
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518278
DOI: 10.1007/978-3-642-03644-6_11
Other: Local-ID: C1256428004B93B8-CA00677497561C7EC125763C0044A41A-emel_gpgpu_09
 Degree: -

Event

show
hide
Title: 8th International Conference on Advanced Parallel Processing Technologies
Place of Event: Rapperswil, Switzerland
Start-/End Date: 2009-08-24 - 2009-08-25

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advanced Parallel Processing Technologies
  Subtitle : 8th International Symposium, APPT 2009, Rapperswil, Switzerland, August 24-25, 2009 Proceedings
  Abbreviation : APPT 2009
Source Genre: Proceedings
 Creator(s):
Dou1, Editor
Yong1, Editor
Gruber1, Editor
Ralf1, Editor
Joller1, Editor
Josef1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 134 - 149 Identifier: ISBN: 978-3-642-03643-9

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 5737 Sequence Number: - Start / End Page: - Identifier: -