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

محورهای موضوعی : مهندسی الکترونیک

حامد امین زاده ¹ (گروه مهندسی برق، دانشگاه پیام نور، 4697-19395، تهران،)

تاریخ دریافت : 1394/03/12 تاریخ پذیرش : 1395/01/24 تاریخ انتشار : 1394/08/28

کلید واژه: آرایه‌های منظقی برنامه‌پذیر (FPGA), حافظه با دسترسی تصادفی, شمارنده, مرتب کننده, Counter, Floating Point Gate Array (FPGA), Random Access Memory (RAM), and Sorter,

چکیده مقاله :

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

چکیده انگلیسی:

Sorting is still one of the main challenges in processing input digital binary data. Depending on implementation of the sorter, the three main factors are speed, chip area and power consumption.  When realized on a floating point gate array (FPGA), sorter acts like an embedded processor beside many other processing units. For these implementations, the number of CLBs occupied by the sorter is very important. In this paper, a new algorithm is proposed to implement sorter on FPGA using minimum number of CLBs. Unlike previous algorithms which employ comparator to sort data, this high-power large-area unit is not needed in and most of the process can be fulfilled by the available random access memory (RAM). In addition to less number of CLBs, this approach also improves reliability. To show the effectiveness of the proposed technique, a 256 word sorter with 16 bits word length is synthesized on xilinx spartan 3 XC3S1500 based on this method.

منابع و مأخذ:

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