Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal
Two-dimensional discrete Fourier transform (DFT) is an extensively used and computationally intensive algorithm, with a plethora of applications. 2D images are, in general, nonperiodic but are assumed to be periodic while calculating their DFTs. This leads to cross-shaped artifacts in the frequency...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | International Journal of Reconfigurable Computing |
| Online Access: | http://dx.doi.org/10.1155/2018/1403181 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832555390855806976 |
|---|---|
| author | Faisal Mahmood Märt Toots Lars-Göran Öfverstedt Ulf Skoglund |
| author_facet | Faisal Mahmood Märt Toots Lars-Göran Öfverstedt Ulf Skoglund |
| author_sort | Faisal Mahmood |
| collection | DOAJ |
| description | Two-dimensional discrete Fourier transform (DFT) is an extensively used and computationally intensive algorithm, with a plethora of applications. 2D images are, in general, nonperiodic but are assumed to be periodic while calculating their DFTs. This leads to cross-shaped artifacts in the frequency domain due to spectral leakage. These artifacts can have critical consequences if the DFTs are being used for further processing, specifically for biomedical applications. In this paper we present a novel FPGA-based solution to calculate 2D DFTs with simultaneous edge artifact removal for high-performance applications. Standard approaches for removing these artifacts, using apodization functions or mirroring, either involve removing critical frequencies or necessitate a surge in computation by significantly increasing the image size. We use a periodic plus smooth decomposition-based approach that was optimized to reduce DRAM access and to decrease 1D FFT invocations. 2D FFTs on FPGAs also suffer from the so-called “intermediate storage” or “memory wall” problem, which is due to limited on-chip memory, increasingly large image sizes, and strided column-wise external memory access. We propose a “tile-hopping” memory mapping scheme that significantly improves the bandwidth of the external memory for column-wise reads and can reduce the energy consumption up to 53%. We tested our proposed optimizations on a PXIe-based Xilinx Kintex 7 FPGA system communicating with a host PC, which gives us the advantage of further expanding the design for biomedical applications such as electron microscopy and tomography. We demonstrate that our proposed optimizations can lead to 2.8× reduced FPGA and DRAM energy consumption when calculating high-throughput 4096×4096 2D FFTs with simultaneous edge artifact removal. We also used our high-performance 2D FFT implementation to accelerate filtered back-projection for reconstructing tomographic data. |
| format | Article |
| id | doaj-art-b82982c1b4364732b774e3107846fa9b |
| institution | Kabale University |
| issn | 1687-7195 1687-7209 |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Reconfigurable Computing |
| spelling | doaj-art-b82982c1b4364732b774e3107846fa9b2025-02-03T05:48:23ZengWileyInternational Journal of Reconfigurable Computing1687-71951687-72092018-01-01201810.1155/2018/14031811403181Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact RemovalFaisal Mahmood0Märt Toots1Lars-Göran Öfverstedt2Ulf Skoglund3Department of Biomedical Engineering, Johns Hopkins University, Baltimore, MD 21218, USAStructural Cellular Biology Unit, Okinawa Institute of Science and Technology (OIST), Okinawa, JapanStructural Cellular Biology Unit, Okinawa Institute of Science and Technology (OIST), Okinawa, JapanStructural Cellular Biology Unit, Okinawa Institute of Science and Technology (OIST), Okinawa, JapanTwo-dimensional discrete Fourier transform (DFT) is an extensively used and computationally intensive algorithm, with a plethora of applications. 2D images are, in general, nonperiodic but are assumed to be periodic while calculating their DFTs. This leads to cross-shaped artifacts in the frequency domain due to spectral leakage. These artifacts can have critical consequences if the DFTs are being used for further processing, specifically for biomedical applications. In this paper we present a novel FPGA-based solution to calculate 2D DFTs with simultaneous edge artifact removal for high-performance applications. Standard approaches for removing these artifacts, using apodization functions or mirroring, either involve removing critical frequencies or necessitate a surge in computation by significantly increasing the image size. We use a periodic plus smooth decomposition-based approach that was optimized to reduce DRAM access and to decrease 1D FFT invocations. 2D FFTs on FPGAs also suffer from the so-called “intermediate storage” or “memory wall” problem, which is due to limited on-chip memory, increasingly large image sizes, and strided column-wise external memory access. We propose a “tile-hopping” memory mapping scheme that significantly improves the bandwidth of the external memory for column-wise reads and can reduce the energy consumption up to 53%. We tested our proposed optimizations on a PXIe-based Xilinx Kintex 7 FPGA system communicating with a host PC, which gives us the advantage of further expanding the design for biomedical applications such as electron microscopy and tomography. We demonstrate that our proposed optimizations can lead to 2.8× reduced FPGA and DRAM energy consumption when calculating high-throughput 4096×4096 2D FFTs with simultaneous edge artifact removal. We also used our high-performance 2D FFT implementation to accelerate filtered back-projection for reconstructing tomographic data.http://dx.doi.org/10.1155/2018/1403181 |
| spellingShingle | Faisal Mahmood Märt Toots Lars-Göran Öfverstedt Ulf Skoglund Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal International Journal of Reconfigurable Computing |
| title | Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal |
| title_full | Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal |
| title_fullStr | Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal |
| title_full_unstemmed | Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal |
| title_short | Algorithm and Architecture Optimization for 2D Discrete Fourier Transforms with Simultaneous Edge Artifact Removal |
| title_sort | algorithm and architecture optimization for 2d discrete fourier transforms with simultaneous edge artifact removal |
| url | http://dx.doi.org/10.1155/2018/1403181 |
| work_keys_str_mv | AT faisalmahmood algorithmandarchitectureoptimizationfor2ddiscretefouriertransformswithsimultaneousedgeartifactremoval AT marttoots algorithmandarchitectureoptimizationfor2ddiscretefouriertransformswithsimultaneousedgeartifactremoval AT larsgoranofverstedt algorithmandarchitectureoptimizationfor2ddiscretefouriertransformswithsimultaneousedgeartifactremoval AT ulfskoglund algorithmandarchitectureoptimizationfor2ddiscretefouriertransformswithsimultaneousedgeartifactremoval |