EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

FourierPIM: High-throughput in-memory Fast Fourier Transform and polynomial multiplication

Orian Leitersdorf, Yahav Boneh, Gonen Gazit, Ronny Ronen, Shahar Kvatinsky

Memories - Materials, Devices, Circuits and Systems · 2023-07 · 4 · 100034

DOI: 10.1016/j.memori.2023.100034 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Memories - Materials, Devices, Circuits and Systems, 2023-07. Verfasst von Orian Leitersdorf und 4 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Horizon 2020, Israel Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Discrete Fourier Transform (DFT) is essential for various applications ranging from signal processing to convolution and polynomial multiplication. The groundbreaking Fast Fourier Transform (FFT) algorithm reduces DFT time complexity from the naive O(n^2) to O(n log n), and recent works have sought further acceleration through parallel architectures such as GPUs. Unfortunately, accelerators such as GPUs cannot exploit their full computing capabilities as memory access becomes the bottleneck. Therefore, this paper accelerates the FFT algorithm using digital Processing-in-Memory (PIM) architectures that shift computation into the memory by exploiting physical devices capable of storage and logic (e.g., memristors). We propose an O(log n) in-memory FFT algorithm that can also be performed in parallel across multiple arrays for high-throughput batched execution, supporting both fixed-point and floating-point numbers. Through the convolution theorem, we extend this algorithm to O(log n) polynomial multiplication - a fundamental task for applications such as cryptography. We evaluate FourierPIM on a publicly-available cycle-accurate simulator that verifies both correctness and performance, and demonstrate 5-15x throughput and 4-13x energy improvement over the NVIDIA cuFFT library on state-of-the-art GPUs for FFT and polynomial multiplication.

Förderung

  • Horizon 2020
  • Israel Science Foundation

Zitieren

APA

Leitersdorf, O., Boneh, Y., Gazit, G., Ronen, R., & Kvatinsky, S. (2023). FourierPIM: High-throughput in-memory Fast Fourier Transform and polynomial multiplication. Memories - Materials, Devices, Circuits and Systems, 4, 100034. https://doi.org/10.1016/j.memori.2023.100034

Vancouver

Leitersdorf O, Boneh Y, Gazit G, Ronen R, Kvatinsky S. FourierPIM: High-throughput in-memory Fast Fourier Transform and polynomial multiplication. Memories - Materials, Devices, Circuits and Systems. 2023;4:100034. doi:10.1016/j.memori.2023.100034

BibTeX
@article{Leitersdorf2023,
  author = {Leitersdorf, Orian and Boneh, Yahav and Gazit, Gonen and Ronen, Ronny and Kvatinsky, Shahar},
  title = {FourierPIM: High-throughput in-memory Fast Fourier Transform and polynomial multiplication},
  journal = {Memories - Materials, Devices, Circuits and Systems},
  year = {2023},
  volume = {4},
  pages = {100034},
  doi = {10.1016/j.memori.2023.100034}
}
Kostenlos starten →