Fast fourier transform operation with reduced cache penalty

Details Fast fourier transform operation with reduced cache penalty Fast fourier transform operation with reduced cache penalty

2004-03-25

2008-11-18

Bullock, Jr., Lewis A. (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S400000, C708S403000, C708S408000, C708S409000

Reexamination Certificate

active

07454452

ABSTRACT:
A data processing apparatus having data cache performs an N-point radix-R Fast Fourier Transform. If the data set is smaller than the data cache, the data processing apparatus performs the Fast Fourier Transform in logRN stages on all the data set in one pass. If the data set is larger than the data cache but smaller than R times the data cache, the data processing apparatus performs a first stage radix-R butterfly computation on all the input data producing R independent intermediate data sets. The data processing apparatus then successively performs second and all subsequent stage butterfly computations on each independent intermediate data set in turn producing corresponding output data. During the first stage radix-R butterfly computations, each of R continuous sets are separated in memory by memory locations equal to the size of a cache line.

REFERENCES:
patent: 5293330 (1994-03-01), Sayegh
patent: 6041393 (2000-03-01), Hsu
patent: 6088714 (2000-07-01), Wadleigh
patent: 6366937 (2002-04-01), Shridhar et al.
patent: 6421696 (2002-07-01), Horton
patent: 6591284 (2003-07-01), Brockmeyer et al.

Affiliated with

Also associated with

Rating

Fast fourier transform operation with reduced cache penalty does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast fourier transform operation with reduced cache penalty, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast fourier transform operation with reduced cache penalty will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4040675