FFT PROCESSOR DESIGN_论文_stanford university

kevinwjs

2 The Fourier Transform 4
2.1 The Continuous Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 The Discrete Fourier Transform (DFT) . . . . . . . . . . . . . . . . . . . . . 6
2.3 The Fast Fourier Transform (FFT) . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.2 Simple Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.3 Relative Efficiencies . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.4 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Common FFT Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Common-Factor Algorithms . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Prime-Factor Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.3 Other FFT Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 29
vii
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Low-Power Processors 32
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.1 Power vs. Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Power Consumption in CMOS. . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Short-Circuit Power . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2 Leakage Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Switching Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Constant-Current Power . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Common Power Reduction Techniques . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 Power Supply Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Algorithmic and Architectural Design . . . . . . . . . . . . . . . . . 38
3.3.3 Circuit Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.4 Fabrication Technology . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.5 Reversible Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.6 Asynchronous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.7 Software Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 The Cached-FFT Algorithm 50
4.1 Overview of the Cached-FFT . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.1 Basic Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.2 Key Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.1.3 Relevant Cached-FFT Definitions . . . . . . . . . . . . . . . . . . . . 52
4.2 FFT Algorithms Similar to the Cached-FFT. . . . . . . . . . . . . . . . . . 53
4.3 General FFT Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 The RRI-FFT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4.1 Existence of the RRI-FFT . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5 Existence of the Cached-FFT . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6 A General Description of the RRI-FFT. . . . . . . . . . . . . . . . . . . . . 66
4.7 A General Description of the Cached-FFT . . . . . . . . . . . . . . . . . . . 69
4.7.1 Implementing the Cached-FFT . . . . . . . . . . . . . . . . . . . . . 76
4.7.2 Unbalanced Cached-FFTs . . . . . . . . . . . . . . . . . . . . . . . . 78
viii
4.7.3 Reduction ofMemory Traffic . . . . . . . . . . . . . . . . . . . . . . 79
4.7.4 Calculating Multiple Transform Lengths . . . . . . . . . . . . . . . . 79
4.7.5 Variations of the Cached-FFT. . . . . . . . . . . . . . . . . . . . . . 80
4.7.6 Comments on Cache Design . . . . . . . . . . . . . . . . . . . . . . . 80
4.8 Software Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 An Energy-Efficient, Single-Chip FFT Processor 83
5.1 Key Characteristics and Goals . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Algorithmic Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Radix Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 DIT vs. DIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.3 FFT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.4 Programmable vs. Dedicated Controller . . . . . . . . . . . . . . . . 86
5.3 Architectural Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.1 Memory System Architecture . . . . . . . . . . . . . . . . . . . . . . 87
5.3.2 Pipeline Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.3.3 Datapath Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3.4 Required Functional Units . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3.5 Chip-Level Block Diagram. . . . . . . . . . . . . . . . . . . . . . . . 93
5.3.6 Fixed-Point Data Word Format . . . . . . . . . . . . . . . . . . . . . 93
5.4 Physical Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.4.1 MainMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.4.2 Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.4.3 Multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.4.4 WN Coefficient Storage . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.4.5 Adders/Subtracters . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.4.6 Controllers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.4.7 Clocking Methodology, Generation and Distribution . . . . . . . . . 120
5.4.8 Testing and Debugging . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.5 Design Approach and Tools Used . . . . . . . . . . . . . . . . . . . . . . . . 124
5.5.1 High-Level Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.5.2 layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
ix
5.5.3 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6 Measured and Projected Spiffee Performance 127
6.1 Spiffee1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.1.1 Low-Power Operation . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.1.2 High-Speed Operation . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.1.3 General Performance Figures . . . . . . . . . . . . . . . . . . . . . . 130
6.1.4 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2 Low-Vt Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.2.1 Low-Vt 0.26 μmSpiffee . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.2.2 ULP 0.5 μmSpiffee . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7 Conclusion 143
7.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7.2.1 Higher-Precision Data Formats . . . . . . . . . . . . . . . . . . . . . 144
7.2.2 Multiple Datapath-Cache Processors . . . . . . . . . . . . . . . . . . 146
7.2.3 High-Throughput Systems . . . . . . . . . . . . . . . . . . . . . . . . 147
7.2.4 Multi-Dimensional Transforms . . . . . . . . . . . . . . . . . . . . . 147
7.2.5 Other-Length Transforms . . . . . . . . . . . . . . . . . . . . . . . . 148

jjw3310

qqqqqqq3qqqqqqqqqqqq

iseesky

very good,thanks!

aswine

hao wen

kresit

找了很久了,谢谢楼主啦

unclebearbear

very good very good

unclebearbear

good good good

basildy

basildy