High Performance FFT Algorithms for Cache-Coherent Multiprocessors
| Autor: | Kevin R. Wadleigh |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
020203 distributed computing
Snoopy cache Hardware_MEMORYSTRUCTURES Cache coloring Computer science Fast Fourier transform Pipeline burst cache 010103 numerical & computational mathematics 02 engineering and technology Parallel computing Cache-oblivious algorithm 01 natural sciences Theoretical Computer Science Smart Cache Hardware and Architecture 0202 electrical engineering electronic engineering information engineering Cache 0101 mathematics Cache algorithms Algorithm Software |
| Zdroj: | The International Journal of High Performance Computing Applications. 13:163-171 |
| ISSN: | 1741-2846 1094-3420 |
| DOI: | 10.1177/109434209901300206 |
| Popis: | Computing one-dimensional fast Fourier transforms (FFTs) on microprocessors requires different algorithms, depending on whether the problem fits in the data cache. This paper describes efficient algorithms for both cases. Some implementations of out-of-cache one-dimensional FFTs use a six-step approach to reduce the number of cache misses. The six-step approach may be altered into a seven-step approach that allows increased data cache reuse. A natural parallelism is also developed. Performance results using these techniques are given for the Hewlett-Packard HP 9000 V-Class V2250 server. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|