Efficient serial implementation of Odd-Even transposition sort on FPGA

Abstract

Sorting is known to be executed very frequently on many computers, mostly in software to handle wide variety of tasks. However software implementations suffer from low speed when dealing with large number of keys. On the other hand, little work has been done to implement sorting in hardware. Most of these implementations suffer from high resource consumption, where sorting large number of keys is prohibitively expensive and thus unrealistic. This thesis presents the implementation of a serial Odd – Even Transposition sorting algorithm. The main motivation of the proposed implementation is the ability to sort large number of keys in real time. Therefore, a bit-wise implementation is proposed; reducing the size of each sorting cell. This, in turn, lead to a higher clock rate, while maintaining its high parallelism. The advantages of such implementation are twofold. First, it is not affected by the width of each key, as opposed to word-wise implementation. Second, it leads to a higher clock rate than previous implementations. These advantages, along with high parallelism, lead to real time sorting. This serial implementation is simulated on FPGA Virtex IV and hosted by FPGA Virtex II Labview PCI card with a DMA based data transfer from computer to FPGA.