Evaluating the hardware performance of a million-bit multiplier

Yarkin Doröz, Erdinç Öztürk, Berk Sunar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

In this work we present the first full and complete evaluation of a very large multiplication scheme in custom hardware. We designed a novel architecture to realize a million-bit multiplication architecture based on the Schönhage-Strassen Algorithm and the Number Theoretical Transform (NTT). The construction makes use of an innovative cache architecture along with processing elements customized to match the computation and access patterns of the FFT-based recursive multiplication algorithm. When synthesized using a 90nm TSMC library operating at a frequency of 666 MHz, our architecture is able to compute the product of integers in excess of a million bits in 7.74 milliseconds. Estimates show that the performance of our design matches that of previously reported software implementations on a high-end 3 Ghz Intel Xeon processor, while requiring only a tiny fraction of the area.

Original languageEnglish (US)
Title of host publicationProceedings - 16th Euromicro Conference on Digital System Design, DSD 2013
Pages955-962
Number of pages8
DOIs
StatePublished - Dec 16 2013
Event16th Euromicro Conference on Digital System Design, DSD 2013 - Santander, Spain
Duration: Sep 4 2013Sep 6 2013

Publication series

NameProceedings - 16th Euromicro Conference on Digital System Design, DSD 2013

Other

Other16th Euromicro Conference on Digital System Design, DSD 2013
Country/TerritorySpain
CitySantander
Period9/4/139/6/13

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering

Keywords

  • FFT
  • Homomorphic encryption
  • Large multiplier
  • Number theoretical transform

Fingerprint

Dive into the research topics of 'Evaluating the hardware performance of a million-bit multiplier'. Together they form a unique fingerprint.

Cite this