2025-11-20T07:07:14.857348

Adaptive Hybrid FFT: A Novel Pipeline and Memory-Based Architecture for Radix-$2^k$ FFT in Large Size Processing

Zhao, Xiao, Wang et al.
In the field of digital signal processing, the fast Fourier transform (FFT) is a fundamental algorithm, with its processors being implemented using either the pipelined architecture, well-known for high-throughput applications but weak in hardware utilization, or the memory-based architecture, designed for area-constrained scenarios but failing to meet stringent throughput requirements. Therefore, we propose an adaptive hybrid FFT, which leverages the strengths of both pipelined and memory-based architectures. In this paper, we propose an adaptive hybrid FFT processor that combines the advantages of both architectures, and it has the following features. First, a set of radix-$2^k$ multi-path delay commutators (MDC) units are developed to support high-performance large-size processing. Second, a conflict-free memory access scheme is formulated to ensure a continuous data flow without data contention. Third, We demonstrate the existence of a series of bit-dimension permutations for reordering input data, satisfying the generalized constraints of variable-length, high-radix, and any level of parallelism for wide adaptivity. Furthermore, the proposed FFT processor has been implemented on a field-programmable gate array (FPGA). As a result, the proposed work outperforms conventional memory-based FFT processors by requiring fewer computation cycles. It achieves higher hardware utilization than pipelined FFT architectures, making it suitable for highly demanding applications.
academic

अनुकूली हाइब्रिड FFT: बड़े आकार की प्रक्रिया के लिए Radix-2k2^k FFT के लिए एक नवीन पाइपलाइन और मेमोरी-आधारित आर्किटेक्चर

मूल जानकारी

  • पेपर ID: 2501.01259
  • शीर्षक: अनुकूली हाइब्रिड FFT: बड़े आकार की प्रक्रिया के लिए Radix-2k2^k FFT के लिए एक नवीन पाइपलाइन और मेमोरी-आधारित आर्किटेक्चर
  • लेखक: Fangyu Zhao, Chunhua Xiao, Zhiguo Wang, Xiaohua Du, Bo Dong
  • वर्गीकरण: cs.AR (कंप्यूटर आर्किटेक्चर)
  • प्रकाशन समय/सम्मेलन: IEEE को प्रस्तुत, जनवरी 2025
  • पेपर लिंक: https://arxiv.org/abs/2501.01259

सारांश

डिजिटल सिग्नल प्रोसेसिंग के क्षेत्र में, तीव्र फूरियर रूपांतरण (FFT) एक मौलिक एल्गोरिदम है। इसके प्रोसेसर कार्यान्वयन आमतौर पर दो आर्किटेक्चर का उपयोग करते हैं: पाइपलाइन आर्किटेक्चर (उच्च थ्रूपुट अनुप्रयोगों के लिए उपयुक्त लेकिन हार्डवेयर उपयोग दर कम) और मेमोरी-आधारित आर्किटेक्चर (क्षेत्र-सीमित परिदृश्यों के लिए उपयुक्त लेकिन कठोर थ्रूपुट आवश्यकताओं को पूरा नहीं कर सकता)। यह पेपर एक अनुकूली हाइब्रिड FFT आर्किटेक्चर प्रस्तावित करता है जो दोनों आर्किटेक्चर के लाभों को जोड़ता है। इस आर्किटेक्चर की विशेषताएं हैं: उच्च-प्रदर्शन बड़े पैमाने की प्रक्रिया का समर्थन करने के लिए radix-2k2^k बहु-पथ विलंबित विनिमायक (MDC) इकाइयों का एक सेट विकसित किया गया; निरंतर डेटा प्रवाह सुनिश्चित करने के लिए संघर्ष-मुक्त मेमोरी पहुंच योजना तैयार की गई; बिट-आयामी क्रमपरिवर्तन की एक श्रृंखला का अस्तित्व साबित किया गया, जो परिवर्तनशील लंबाई, उच्च मूलांक और मनमानी समानता के व्यापक अनुकूलन आवश्यकताओं को संतुष्ट करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

  1. मूल समस्या: पारंपरिक FFT प्रोसेसर आर्किटेक्चर में अंतर्निहित खामियां हैं
    • पाइपलाइन आर्किटेक्चर: उच्च थ्रूपुट लेकिन कम हार्डवेयर उपयोग दर, छोटे FFT संचालन में बड़ी मात्रा में हार्डवेयर निष्क्रिय रहता है
    • मेमोरी-आधारित आर्किटेक्चर: उच्च हार्डवेयर उपयोग दर लेकिन बढ़े हुए कंप्यूटिंग चक्र, वास्तविक समय प्रसंस्करण प्रदर्शन को प्रभावित करते हैं
  2. समस्या की महत्ता:
    • FFT वायरलेस संचार, छवि प्रसंस्करण, रडार सिग्नल प्रसंस्करण आदि क्षेत्रों में व्यापक रूप से लागू होता है
    • बड़े पैमाने पर डेटा प्रसंस्करण की मांग लगातार बढ़ रही है, जिसके लिए कुशल और लचीले FFT प्रोसेसर की आवश्यकता है
    • मौजूदा आर्किटेक्चर एक साथ उच्च थ्रूपुट और उच्च हार्डवेयर उपयोग दर को संतुष्ट नहीं कर सकते
  3. मौजूदा विधियों की सीमाएं:
    • पाइपलाइन आर्किटेक्चर में छोटे FFT को संभालते समय हार्डवेयर उपयोग दर 15% तक कम हो सकती है
    • मेमोरी-आधारित आर्किटेक्चर को कई पुनरावृत्तियों की आवश्यकता होती है, जिससे कंप्यूटिंग विलंबता बढ़ता है
    • मौजूदा संघर्ष-परिहार योजनाएं मुख्य रूप से radix-2 एल्गोरिदम तक सीमित हैं, उच्च-मूलांक गणना का समर्थन नहीं करती हैं
  4. अनुसंधान प्रेरणा:
    • दोनों आर्किटेक्चर के लाभों को जोड़कर अनुकूली पुनः कॉन्फ़िगरेशन प्राप्त करना
    • बड़े पैमाने की FFT प्रक्रिया का समर्थन करना (अधिकतम 512K बिंदु)
    • हार्डवेयर उपयोग दर में सुधार करते हुए उच्च थ्रूपुट सुनिश्चित करना

मुख्य योगदान

  1. अनुकूली हाइब्रिड FFT प्रोसेसर आर्किटेक्चर प्रस्तावित करना: पाइपलाइन और मेमोरी-आधारित दोनों मोड का समर्थन करता है, अधिकतम 512K बिंदु FFT को संभाल सकता है
  2. Radix-2k2^k बहु-पथ विलंबित विनिमायक (MDC) विकसित करना: radix-252^5 एल्गोरिदम का समर्थन करता है, कंप्यूटिंग चरणों की संख्या में उल्लेखनीय कमी
  3. संघर्ष-मुक्त मेमोरी पहुंच तकनीक डिजाइन करना: पूर्ण स्थान-में मेमोरी परिवर्तन के निरंतर प्रवाह FFT गणना को लागू करना
  4. सार्वभौमिक बिट क्रमपरिवर्तन विधि का निर्माण: विभिन्न FFT लंबाई, मूलांक और समानता के हार्डवेयर बाधाओं के अनुकूल

विधि विवरण

कार्य परिभाषा

एक पुनः कॉन्फ़िगरेशन योग्य FFT प्रोसेसर डिजाइन करना जो निम्नलिखित को संभाल सकता है:

  • इनपुट: N-बिंदु जटिल अनुक्रम (N = 2^n, अधिकतम 512K)
  • आउटपुट: संबंधित आवृत्ति-डोमेन प्रतिनिधित्व
  • बाधाएं: radix-2k2^k (k≤5) एल्गोरिदम का समर्थन करता है, कॉन्फ़िगरेशन योग्य समानता P, संघर्ष-मुक्त मेमोरी पहुंच को लागू करता है

मॉडल आर्किटेक्चर

1. शीर्ष-स्तरीय आर्किटेक्चर डिजाइन

इनपुट डेटा → डेटा पुनः व्यवस्था मॉड्यूल → FFT मुख्य प्रोसेसर → आउटपुट डेटा
         ↑                ↑
    मेमोरी बैंक समूह        MDC इकाई समूह
    पता पीढ़ी इकाई      (P समानांतर)
    समानांतर शाखा क्रमपरिवर्तन सर्किट
    पुनः व्यवस्था सर्किट

2. मुख्य घटक विवरण

बहु-पथ विलंबित विनिमायक (MDC) इकाई:

  • radix-252^5/24/23/22 मिश्रित गणना का समर्थन करता है
  • संशोधित radix-252^5 एल्गोरिदम का उपयोग करता है, घूर्णन कारकों को वर्गीकृत करता है:
    • स्थिरांक (C): ROM में पूर्व-संग्रहीत
    • गैर-तुच्छ (NT): जटिल गुणक की आवश्यकता है
    • तुच्छ (T): सरल ±1, ±j संचालन

डेटा पुनः व्यवस्था रणनीति: बिट-आयामी क्रमपरिवर्तन के आधार पर तीन-स्तरीय परिवर्तन को लागू करना: σNs,k,P=σN,3s,k,P∘σN,2s,k,P∘σN,1s,k,P\sigma^{s,k,P}_N = \sigma^{s,k,P}_{N,3} \circ \sigma^{s,k,P}_{N,2} \circ \sigma^{s,k,P}_{N,1}

जहां:

  • σN,1s,k,P\sigma^{s,k,P}_{N,1}: क्रमिक बिट-आयामी क्रमपरिवर्तन
  • σN,2s,k,P\sigma^{s,k,P}_{N,2}: समानांतर शाखा विनिमय
  • σN,3s,k,P\sigma^{s,k,P}_{N,3}: सूक्ष्म सूचकांक समायोजन

3. संघर्ष-मुक्त मेमोरी पहुंच योजना

पाइपलाइन मोड:

  • इंटरलीव्ड पता पैटर्न का उपयोग करता है: प्राकृतिक क्रम और उलटा क्रम
  • पढ़ने-लिखने के पते का संबंध: σWi=σRi−1\sigma^i_W = \sigma^{i-1}_R
  • निरंतर डेटा प्रवाह संघर्ष-मुक्त सुनिश्चित करता है

मेमोरी-आधारित मोड:

  • स्थान-में भंडारण के लिए अतिरिक्त क्रमपरिवर्तन σ~N,1s,k,P\tilde{\sigma}^{s,k,P}_{N,1} का परिचय देता है
  • N ∈ (2^{2k}, 2^{3k}] की बड़े पैमाने की प्रक्रिया के लिए लागू होता है

तकनीकी नवाचार बिंदु

  1. एकीकृत radix-2k2^k आर्किटेक्चर: संशोधित एल्गोरिदम के माध्यम से हार्डवेयर पुनः उपयोग को लागू करता है, एक ही हार्डवेयर कई मूलांकों का समर्थन करता है
  2. अनुकूली पुनः कॉन्फ़िगरेशन क्षमता: FFT आकार और प्रदर्शन आवश्यकताओं के अनुसार गतिशील रूप से कार्य मोड का चयन करता है
  3. सार्वभौमिक बिट क्रमपरिवर्तन सिद्धांत: मौजूदा विधि को विस्तारित करता है, किसी भी मूलांक, लंबाई और समानता का समर्थन करता है
  4. अनुकूलित मेमोरी पहुंच पैटर्न: विभिन्न मोड के लिए विशेष संघर्ष-मुक्त पहुंच रणनीति डिजाइन करता है

प्रायोगिक सेटअप

हार्डवेयर प्लेटफॉर्म

  • FPGA: Xilinx Virtex UltraScale+ VCU118 (xcvu9p-flga2104-2L-e)
  • विकास उपकरण: Chisel HDL, Xilinx Vivado 2019.2
  • मेमोरी कार्यान्वयन:
    • डेटा भंडारण: Ultra RAMs (URAMs), प्रत्येक मेमोरी 256K पता×32-बिट
    • घूर्णन कारक भंडारण: Block RAMs (BRAMs)

मूल्यांकन मेट्रिक्स

  1. हार्डवेयर उपयोग दर: सक्रिय तितली इकाइयों का औसत अनुपात
  2. कंप्यूटिंग चक्र संख्या: FFT को पूरा करने के लिए आवश्यक घड़ी चक्र
  3. प्रसंस्करण समय: पुनरावृत्ति संख्या × प्रति पुनरावृत्ति चक्र संख्या
  4. संसाधन खपत: DSP48E2, LUT, FF आदि हार्डवेयर संसाधन उपयोग

तुलना विधियां

  1. मेमोरी-आधारित आर्किटेक्चर: Tsai'11, Kaya'23, Wang'20
  2. पाइपलाइन आर्किटेक्चर: Garrido'13

प्रायोगिक परिणाम

मुख्य परिणाम

1. मेमोरी-आधारित आर्किटेक्चर के साथ तुलना

आर्किटेक्चरमूलांकFFT लंबाईसमानतापुनरावृत्ति संख्याप्रसंस्करण समय में कमी
Tsai'11radix-2³64~4K2⌈n/3⌉70%+
Kaya'23radix-22K~16K2⌈n/2⌉70%+
Wang'20radix-2³32~32K4⌈n/3⌉70%+
यह पेपरradix-2⁵32~512K8⌈n/5⌉आधार

2. पाइपलाइन आर्किटेक्चर के साथ तुलना

कॉन्फ़िगरेशनFFT लंबाईऔसत हार्डवेयर उपयोग दरसुधार परिमाण
Garrido'13 (P=1)2K~512K75%-
Garrido'13 (P=1)64~1K40%-
Garrido'13 (P=1)2~3215%-
यह पेपर (P=1)2K~512K75%समान
यह पेपर (P=2)64~1K80%2 गुना
यह पेपर (P=4)2~3260%4 गुना

3. FPGA कार्यान्वयन परिणाम (N=512K, P=1)

  • DSP48E2: 45,365 इकाइयां
  • LUT: 76,183 इकाइयां
  • FF: 1,500 इकाइयां
  • Block RAMs: 444 इकाइयां
  • Ultra RAMs: 768 इकाइयां
  • कार्य आवृत्ति: 196.8 MHz

मुख्य निष्कर्ष

  1. कंप्यूटिंग दक्षता में सुधार: radix-252^5 एल्गोरिदम के माध्यम से, पुनरावृत्ति संख्या ⌈n/5⌉ तक कम हो जाती है, पारंपरिक विधियों की तुलना में 40% से अधिक की कमी
  2. हार्डवेयर उपयोग दर अनुकूलन: अनुकूली समानता के माध्यम से, छोटे FFT की हार्डवेयर उपयोग दर 2-4 गुना बढ़ जाती है
  3. स्केलेबिलिटी में वृद्धि: 32 बिंदु से 512K बिंदु तक की व्यापक श्रेणी FFT प्रसंस्करण का समर्थन करता है

संबंधित कार्य

मुख्य अनुसंधान दिशाएं

  1. पाइपलाइन FFT आर्किटेक्चर: Groginsky & Works (1970) द्वारा प्रतिनिधित्व, उच्च थ्रूपुट की खोज करता है
  2. मेमोरी-आधारित FFT आर्किटेक्चर: हार्डवेयर संसाधनों को कम करने के लक्ष्य के साथ, क्षेत्र-सीमित अनुप्रयोगों के लिए उपयुक्त
  3. उच्च-मूलांक FFT एल्गोरिदम: radix-2k2^k एल्गोरिदम कंप्यूटिंग जटिलता और हार्डवेयर कार्यान्वयन कठिनाई को संतुलित करता है

इस पेपर के सापेक्ष लाभ

  1. आर्किटेक्चर संलयन: पहली बार पाइपलाइन और मेमोरी-आधारित आर्किटेक्चर के अनुकूली स्विचिंग को लागू करता है
  2. मूलांक विस्तार: अधिकतम radix-252^5 का समर्थन करता है, मौजूदा radix-232^3 सीमा से अधिक
  3. सिद्धांत में सुधार: सार्वभौमिक बिट क्रमपरिवर्तन सिद्धांत ढांचा प्रदान करता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. अनुकूली हाइब्रिड आर्किटेक्चर पाइपलाइन और मेमोरी-आधारित आर्किटेक्चर के लाभों को सफलतापूर्वक जोड़ता है
  2. radix-252^5 MDC डिजाइन बड़े पैमाने की FFT की कंप्यूटिंग दक्षता में उल्लेखनीय सुधार करता है
  3. सार्वभौमिक बिट क्रमपरिवर्तन विधि विभिन्न कॉन्फ़िगरेशन के लिए सैद्धांतिक गारंटी प्रदान करती है
  4. प्रयोग ने हार्डवेयर उपयोग दर और कंप्यूटिंग दक्षता के संदर्भ में आर्किटेक्चर के महत्वपूर्ण सुधार को सत्यापित किया है

सीमाएं

  1. अनुप्रयोग श्रेणी सीमा: मेमोरी-आधारित मोड केवल N ∈ (2^{2k}, 2^{3k}] के लिए लागू होता है
  2. हार्डवेयर जटिलता: कई मूलांकों का समर्थन करना नियंत्रण तर्क की जटिलता को बढ़ाता है
  3. बिजली खपत विश्लेषण की कमी: विस्तृत बिजली खपत तुलना विश्लेषण प्रदान नहीं किया गया है

भविष्य की दिशाएं

  1. बड़े पैमाने की FFT प्रसंस्करण के समर्थन का विस्तार करना
  2. बिजली खपत दक्षता को अनुकूलित करना
  3. AI त्वरक में अनुप्रयोग की खोज करना

गहन मूल्यांकन

शक्तियां

  1. मजबूत नवाचार: पहली बार अनुकूली हाइब्रिड FFT आर्किटेक्चर प्रस्तावित करता है, पारंपरिक आर्किटेक्चर के अंतर्निहित विरोधाभास को हल करता है
  2. सिद्धांत में पूर्णता: पूर्ण बिट क्रमपरिवर्तन सिद्धांत ढांचा प्रदान करता है, बहुत मजबूत सामान्यता के साथ
  3. पर्याप्त प्रयोग: सैद्धांतिक विश्लेषण से FPGA कार्यान्वयन तक, विधि की प्रभावशीलता को सत्यापित करता है
  4. उच्च व्यावहारिक मूल्य: 512K बिंदु FFT का समर्थन करता है, आधुनिक बड़े डेटा प्रसंस्करण आवश्यकताओं को पूरा करता है

कमियां

  1. जटिलता में वृद्धि: अनुकूली तंत्र डिजाइन जटिलता और सत्यापन कठिनाई को बढ़ाता है
  2. अपूर्ण तुलना: नवीनतम वाणिज्यिक FFT IP कोर के साथ प्रदर्शन तुलना की कमी
  3. बिजली खपत विश्लेषण की कमी: मोबाइल और एम्बेडेड अनुप्रयोगों में बिजली खपत एक महत्वपूर्ण विचार कारक है

प्रभाव

  1. शैक्षणिक योगदान: FFT प्रोसेसर डिजाइन के लिए एक नया आर्किटेक्चर प्रतिमान प्रदान करता है
  2. इंजीनियरिंग मूल्य: 5G संचार, रडार सिग्नल प्रसंस्करण आदि क्षेत्रों में सीधे अनुप्रयोग के लिए उपयोग किया जा सकता है
  3. पुनरुत्पादनीयता: विस्तृत डिजाइन पैरामीटर और कार्यान्वयन विवरण प्रदान करता है

लागू परिदृश्य

  1. उच्च-प्रदर्शन कंप्यूटिंग: बड़े पैमाने की FFT को संभालने की आवश्यकता वाले वैज्ञानिक कंप्यूटिंग अनुप्रयोग
  2. संचार प्रणाली: 5G/6G बेस स्टेशन की सिग्नल प्रसंस्करण इकाई
  3. रडार प्रणाली: वास्तविक समय सिग्नल प्रसंस्करण और लक्ष्य पहचान
  4. छवि प्रसंस्करण: बड़े रिजोल्यूशन छवि का आवृत्ति-डोमेन विश्लेषण

संदर्भ

पेपर FFT एल्गोरिदम, FPGA कार्यान्वयन, मेमोरी पहुंच अनुकूलन आदि कई पहलुओं को कवर करते हुए 17 संबंधित संदर्भों का हवाला देता है, जो अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करता है।

समग्र मूल्यांकन: यह कंप्यूटर आर्किटेक्चर के क्षेत्र में एक उच्च-गुणवत्ता वाला पेपर है, FFT प्रोसेसर डिजाइन के क्षेत्र में महत्वपूर्ण सैद्धांतिक और व्यावहारिक मूल्य रखता है। लेखकों ने चतुर आर्किटेक्चर डिजाइन और कठोर सैद्धांतिक विश्लेषण के माध्यम से, पारंपरिक FFT आर्किटेक्चर की अंतर्निहित समस्याओं को सफलतापूर्वक हल किया है, इस क्षेत्र के विकास के लिए नए विचार और दिशा प्रदान करता है।