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 بحجم كبير

المعلومات الأساسية

  • معرّف الورقة: 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. قيود الطرق الموجودة:
    • معمارية خط الأنابيب قد يكون استخدام الأجهزة فيها منخفضاً جداً (15%) عند معالجة FFT صغير
    • معمارية قائمة على الذاكرة تتطلب تكرارات متعددة، مما يزيد من تأخير الحساب
    • خطط تجنب التضارب الموجودة تقتصر بشكل أساسي على خوارزمية radix-2 ولا تدعم الحسابات ذات الأساس العالي
  4. دافع البحث:
    • دمج مزايا كلا المعمارتين لتحقيق إعادة تكوين تكيفية
    • دعم معالجة FFT بحجم كبير (حتى 512K نقطة)
    • تحسين استخدام الأجهزة مع ضمان إنتاجية عالية

المساهمات الأساسية

  1. اقتراح معمارية معالج FFT هجينة تكيفية: تدعم كلا من وضع خط الأنابيب والوضع القائم على الذاكرة، قادرة على معالجة FFT بحد أقصى 512K نقطة
  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، 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: 183,76 وحدة
  • FF: 1,500 وحدة
  • Block RAMs: 444 وحدة
  • Ultra RAMs: 768 وحدة
  • تردد التشغيل: 196.8 MHz

الاكتشافات الرئيسية

  1. تحسن الكفاءة الحسابية: من خلال خوارزمية radix-252^5، يتم تقليل عدد التكرارات إلى ⌈n/5⌉، مما يقلل بأكثر من 40% مقارنة بالطرق التقليدية
  2. تحسين استخدام الأجهزة: من خلال التوازي التكيفي، يتم تحسين استخدام الأجهزة للـ FFT الصغير بمعامل 2-4 مرات
  3. تحسن القابلية للتوسع: دعم معالجة FFT في نطاق واسع من 32 نقطة إلى 512K نقطة

الأعمال ذات الصلة

الاتجاهات البحثية الرئيسية

  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. استكشاف التطبيقات في معجلات الذكاء الاصطناعي

التقييم المتعمق

المزايا

  1. ابتكار قوي: أول اقتراح لمعمارية FFT هجينة تكيفية، حل التناقض المتأصل في المعماريات التقليدية
  2. اكتمال النظرية: توفير إطار نظري كامل لترتيب البتات، بقوة عامة عالية
  3. تجارب شاملة: من التحليل النظري إلى تطبيق FPGA، التحقق من فعالية الطريقة
  4. قيمة عملية عالية: دعم FFT بـ 512K نقطة، تلبية احتياجات معالجة البيانات الحديثة الكبيرة

أوجه القصور

  1. زيادة التعقيد: آلية التكيف تزيد من تعقيد التصميم والتحقق
  2. مقارنة غير شاملة: نقص المقارنة مع أحدث نوى FFT التجارية
  3. غياب تحليل الطاقة: الطاقة عامل اعتبار مهم في التطبيقات المحمولة والمدمجة

التأثير

  1. المساهمة الأكاديمية: توفير نموذج معمارية جديد لتصميم معالجات FFT
  2. القيمة الهندسية: يمكن تطبيقها مباشرة في معالجة الإشارات في الاتصالات 5G ومعالجة إشارات الرادار
  3. قابلية التكرار: توفير معاملات تصميم وتفاصيل تطبيق مفصلة

السيناريوهات المطبقة

  1. الحوسبة عالية الأداء: تطبيقات الحوسبة العلمية التي تتطلب معالجة FFT بحجم كبير
  2. أنظمة الاتصالات: وحدات معالجة الإشارات في محطات 5G/6G الأساسية
  3. أنظمة الرادار: معالجة الإشارات في الوقت الفعلي والكشف عن الأهداف
  4. معالجة الصور: تحليل المجال الترددي للصور عالية الدقة

المراجع

تستشهد الورقة بـ 17 مرجعاً ذا صلة، تغطي خوارزميات FFT وتطبيقات FPGA وتحسينات وصول الذاكرة وجوانب أخرى متعددة، مما يوفر أساساً نظرياً متيناً للبحث.

التقييم الشامل: هذه ورقة عالية الجودة في مجال معمارية الحاسوب، ذات قيمة نظرية وعملية مهمة في مجال تصميم معالجات FFT. من خلال التصميم المعماري الماهر والتحليل النظري الدقيق، نجح المؤلفون في حل المشاكل المتأصلة في معمارية FFT التقليدية، مما يوفر أفكاراً واتجاهات جديدة لتطور هذا المجال.