Area Efficient Sorting Unit Using Scalable Digital CMOS Comparator
 |
International Journal of Engineering Trends and Technology (IJETT) |  |
| © 2014 by IJETT Journal | ||
| Volume-9 Number-13 |
||
| Year of Publication : 2014 | ||
| Authors : B.Sargunam , S.Srinitha |
||
 10.14445/22315381/IJETT-V9P328 |
Citation
B.Sargunam , S.Srinitha. "Area Efficient Sorting Unit Using Scalable Digital CMOS Comparator", International Journal of Engineering Trends and Technology (IJETT), V9(13),677-682 March 2014. ISSN:2231-5381. www.ijettjournal.org. published by seventh sense research group
Abstract
Sorting is the process of arranging the data into a meaningful order so that we can analyze it more effectively. Sorting is a key requirement in many applications like digital signal processing, scientific computing, network processing etc. This paper presents an area efficient technique for designing high throughput and low latency sorting units. Two popular parallel sorting algorithms are used in this paper, they are Bitonic sorting network and odd-even merge sorting network. These sorting units utilize parallel sorting method which uses Compare-and-Exchange (CAE) blocks. When number of inputs increases, the number of CAE blocks also increases and hence the area increases. To obtain an area efficient sorting network, CAE blocks used in parallel sorting units are replaced with scalable CMOS comparators. Sorting units are coded in VHDL, simulated using Modelsim SE 10.0b and implemented in FPGA using Xilinx ISE for analysis.
References
[1] S. Azuma, T. Sakuma, T. Takeo, T. Ando, and K. Shirai, “Diaprism Hardware Sorter - Sort a Million Records within a Second”Available:http://sortbenchmark.org/Y2000_Datamation_DiaprismSorter.pdf, 2000.
[2] N. Govindaraju, J. Gray, R. Kumar, and D. Manocha, “GPUTeraSort: High Performance Graphics Co-Processor Sorting for Large Database Management” in Proc. Conf. Management of Data, 2000. pp. 325- 336.
[3] D. Pok, C.-I. Chen, J. Schamus, C. Montgomery, and J. Tsui, “Chip Design for Monobit Receiver,” IEEE Trans. Microwave Theory and Techniques, vol. 45, no. 12, pp. 2283-2295, Dec. 1997.
[4] Gregerson, M. Schulte, and K. Compton, High-Energy Physics Handbook of Signal Processing Systems, pp. 179-211, Springer, 2010.
[5] K.E. Batcher, “Sorting Networks and Their Applications,” Proc.AFIPS Proc. Spring Joint Computer Conf. pp. 307-314, 1968.
[6] J.-D. Lee and K.E. Batcher, “Minimizing Communication in theBitonic Sort,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 5, pp. 459-474, May 2000.
[7] E. Herruzo, G. Ruiz, J.I. Benavides, and O. Plata, “A New Parallel Sorting Algorithm Based on Odd-Even Mergesort,” Proc. Int’l Conf. Parallel,distributed and Network-Based Processing, pp. 18-22, 2007.
[8] C.J. Kuo and Z.W. Huang, “Modified Odd-Even Merge-Sort Network for Arbitrary Number of Inputs,” Proc. IEEE Int’l Conf. Multimedia and Expo, pp. 929-932, Aug. 2001.
[9] A. Farmahini-Farahani, A. Gregerson,M. Schulte, and K. Compton, “Modular High-Throughput and Low-Latency Sorting Units for FPGAs in the Large Hadron Collider,” Proc. IEEE Int’l Symp. Application Specific Processors, pp. 38-45, June 2011.
[10] A. Farmahini-Farahani, HenryJ.Duwe III, Michael J.Schuttle and Katherine Compton “Modular Design of High-throughput and Low-Latency sorting units,” IEEE Trans on computers, vol.62, no.7, July 2013.
[11] S.-N. Dong, X.-T. Wang and X.-B. Wang, “A Novel High-Speed Parallel Scheme for Data Sorting Algorithm Based on FPGA,” Proc. Int’l Cong. Image and Signal Processing, pp. 1-4, Oct. 2009.
[12] Abdel-Hafeez.S, Gordon-Ross.A,Parhami.B(2013) “Scalable Digital CMOS Comparator Using a Parallel Prefix Tree” IEEE Transcations on Very Large Scale Integration (VLSI) Systems, vol.21, no. 11, pp 1989-1998.
Keywords
Scalable CMOS comparator, Bitonic sorting, odd-even merge sorting, max-set-selection, partial sorting.