طراحی و سنتز یک پردازنده جانبی به منظور مرتب سازی اطلاعات با استفاده از حافظه داخلی آرایه‌های برنامه پذیر

مهندسی مخابرات جنوب

مقاله 6، دوره 5، شماره 17، آبان 1394، صفحه 39-44

نوع مقاله: مقاله پژوهشی

نویسنده

حامد امین زاده^*

گروه مهندسی برق، دانشگاه پیام نور، 4697-19395، تهران،

چکیده

 مرتب سازی داده‌ها یکی از مسائل مهم در هنگام پردازش اطلاعات دیجیتال می‌باشد. بسته به نحوه پیاده سازی مرتب کننده، معمولاً سه پارامتر سرعت، سطح اشغالی بر روی تراشه و توان مصرفی از اهمیت ویژه برخوردار هستند. وقتی مرتب کننده بر روی آرایه‌های منظقی برنامه­پذیر (FPGA) پیاده سازی شود، از آنجا که این بلوک به عنوان یک پردازشگر جانبی در کنار سایر بلوک‌های افزاری قرار می‌گیرد، تعداد CLBهای اشغال شده پارامتری مهم می‌باشد. در این مقاله، از الگوریتم جدیدی به منظور پیاده سازی مرتب کننده استفاده نموده‌ایم تا حداقل تعداد CLBها اشغال گردند. بر خلاف همه الگوریتم‌های قبلی که از مقایسه کننده به منظور مرتب سازی استفاده می‌کنند در این روش، نیازی به این بلوک وجود ندارد و عمده پردازش، با کمک حافظه با دسترسی تصادفی انجام می‌شود. در نتیجه علاوه بر اینکه تعداد کمتری از CLB ها بر روی تراشه اشغال شده و ساختار ساده‌تر می‌شود، قابلیت اطمینان نیز بالاتر می‌رود. به منظور نشان دادن کارایی این نحوه پیاده سازی، سنتز یک مرتب کننده 256 کلمه‌ای و با طول کلمه 16 بیتی بر روی یک FPGA از نوع Xilinx Spartan3 XC3S1500 انجام شده است.

کلیدواژه‌ها

آرایه‌های منظقی برنامه‌پذیر (FPGA)؛ حافظه با دسترسی تصادفی؛ شمارنده؛ مرتب کننده

مراجع

1. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison- MA, 1973.
2. G. H. Gonnet, Handbook of Algorithms and Data Structures, Addison-Wesley, Reading, MA, 1984.
3. MITCHELLWHEAT, Sorting with near linear speed-up on tightly coupled multiprocessors, John Wiley & Sons, 1991
4. Trevor A York, Survey of field programmable logic devices, Butterworth-Heinemann Ltd Microprocessors And Microsystems Volume 17, 1993.
5. Kjell Oystein Arisland, Anne Cathrine AasbPr and Are Nundal,VLSI parallel shift sort algorithm and design, VLSI journal 2 (1984) 331-347, Elsevier,1994
6. R. C. Agarwal, "A super scalar sorting algorithm for RISC Processors", in Proc. 1996 ACM SIGMOD Conference, pp. 240-246, June 1996
7. M. Cramer,Stochastic Analysis of the Merge Sort Algorithm, John Wiley & Sons,1997
8. Hyeong-Seok Yu,Joon-Yeop Lee And Jun-Dong Cho,A Fast VLSI Implementation Of Sorting Algorithm for Standard Median Filters,IEEE, 1999
9. Hardware Algorithm for Data Compression in Future Communication Systems”, Proceedings of the 12th International Workshop on Rapid System Prototyping, SP’0E, 2001
10. Tae-Wook Lee, Jong-Hwa Lee, Sang-Bock Cho,FPGA IMPLEMENTATION OF A 3 X 3 WINDOW MEDIAN FILTER BASED ON A NEW EFFICIENT BIT-SERIAL SORTING ALGORITHM, Proceedings of the 71h Korea- Russia Inrernntionnl Symposium,KORUS, 2003
11. V. A. Pedroni, Compact hamming-comparator-based rank order filter for digital VLSI and FPGA implementations, in: IEEE International Symposium on Circuits and Systems, vol. 2, pp. 585–588, 2004
12. José Martínez, René Cumplido, Claudia Feregrino,An FPGA-based Parallel Sorting Architecture for the Burrows Wheeler Transform, international Conference on Reconfigurable Computing and FPGAs (ReConFig 2005),2005
13. Xilinx Spartan-3 FPGA family datasheet, Using Block RAM in Spartan-3 Generation FPGAsXAPP463 (v2. 0), 2005
14. D. Baron and Y. Bresler, “Antisequential Suffix Sorting For BWT-Base Data Compression”, IEEE Transactions on Computers, Vol. 54, No4, 2005
15. Hiroshi Inoue, Takao Moriyama, Hideaki Komatsu and Toshio Nakatani,AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors, 16th International Conference on Parallel Architecture And Compilation Techniques (PACT 2007), 2007
16. Meng-Chun Lin_, Lan-Rong Dung,On VLSI design of rank-order filtering using DCRAM architecture, the VLSI journal 41 (2008) 193–209, Elsevier, 2007