Accès ouvert · CC BY

Instruction scheduling heuristic for an efficient FFT in VLIW processors with balanced resource usage

Article scientifique 2016 Sciences mathématiques et statistiques Anglais

Résumé

The fast Fourier transform (FFT) is perhaps today’s most ubiquitous algorithm used with digital data; hence, it is still being studied extensively. Besides the benefit of reducing the arithmetic count in the FFT algorithm, memory references and scheme’s projection on processor’s architecture are critical for a fast and efficient implementation. One of the main bottlenecks is in the long latency memory accesses to butterflies’ legs and in the redundant references to twiddle factors. In this paper, we describe a new FFT implementation on high-end very long instruction word (VLIW) digital signal processors (DSP), which presents improved performance in terms of clock cycles due to the resulting low-level resource balance and to the reduced memory accesses of twiddle factors. The method introduces a tradeoff parameter between accuracy and speed. Additionally, we suggest a cache-efficient implementation methodology for the FFT, dependently on the provided VLIW hardware resources and cache structure. Experimental results on a TI VLIW DSP show that our method reduces the number of clock cycles by an average of 51 % (2 times acceleration) when compared to the most assembly-optimized and vendor-tuned FFT libraries. The FFT was generated using an instruction-level scheduling heuristic. It is a modulo-based register-sensitive scheduling algorithm, which is able to compute an aggressively efficient sequence of VLIW instructions for the FFT, maximizing the parallelism rate and minimizing clock cycles and register usage.

Citer ce document

Bahtat, M., Belkouch, S., Elleaume, P., & Gall, P. L. (2016). Instruction scheduling heuristic for an efficient FFT in VLIW processors with balanced resource usage. https://doi.org/10.1186/s13634-016-0336-0

Exporter : BibTeX · RIS (Zotero, Mendeley, EndNote)

Accès au document

Texte intégral archivé sur SPHAERO, en accès ouvert : lisible gratuitement en ligne après connexion. Le document reste aussi disponible à sa source. Se connecter

Voir l'article sur le site de la revue

Licence et provenance

Licence : CC BY

Notice moissonnée depuis OpenAlex le 25/08/2026. Le document reste hébergé par sa source.
Voir le document à la source →

Statistiques

Consultations (hors robots) : 10

Téléchargements (hors robots) : 0

Méthode de comptage