Efficiency of radix-K transforms on computers with cache

Author

Stasinski, Ryszard M.

Author_Institution

Hoegskolen i Narvik, Norway

Volume

3

fYear

1999

fDate

15-19 Mar 1999

Firstpage

1525

Abstract

The impact of the most critical part of the up-to-date computer memory hierarchy, the cache, on the efficiency of fast transform algorithms (e.g. FFT, DCT/DST, DWHT, including multidimensional generalizations) is analyzed. Cache misses can severely deteriorate the efficiency of a computer program, and indeed, it is shown that for large data vectors a modification of a fast transform algorithm realization may change their number dramatically. Several memory managing problems are pointed out, and suggestions for their amelioration are given. Formulae on the minimum number of data-related cache misses for radix-2 ^s transform realizations are given, s is an integer

Keywords

Hadamard transforms; cache storage; digital arithmetic; discrete cosine transforms; fast Fourier transforms; signal processing; DCT/DST; DWHT; FFT; computer memory hierarchy; computer program; data-related cache misses; digital signal processing; fast transform algorithm; fast transform algorithms efficiency; large data vectors; memory managing problems; multidimensional transforms; radix-K transforms; Computer aided instruction; Memory management; Multidimensional systems; Pervasive computing; Pipeline processing; Random access memory; Read-write memory; Reduced instruction set computing; Registers; Signal processing algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 1999. Proceedings., 1999 IEEE International Conference on

Conference_Location

Phoenix, AZ

ISSN

1520-6149

Print_ISBN

0-7803-5041-3

Type

conf

DOI

10.1109/ICASSP.1999.756274

Filename

756274