Design and Synthesis of an Embedded Processor to Sort Data Based on the Internal Memory of a Programmable Logic Array

Subject Areas : Electronics Engineering

H. Amin Zadeh ¹ (Payam Nor Tehran)

Received: 2015-06-02 Accepted : 2016-04-12 Published : 2015-11-19

Keywords:

Abstract :

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.

References:

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