Fast and Parallel Sorting with Hardware

• Sidrisha Sarbajna, Computer Engineering, Carnegie Mellon Univeristy

• Chengmo Yang, Electrical and Computer Engineering, University of Delaware

A sorting algorithm rearranges elements in an array in a certain order, often in numerical or lexicographical order, either increasing or decreasing. When implemented in software, sorting algorithms use loops to compare elements in an array and rearrange them accordingly. These loop-based algorithms, however, are not well suited for hardware implementation. Instead, comparator modules are instantiated to create a network that can perform sorting on a fixed number of inputs. Moreover, in hardware implementations, it is important to consider the timing and performance of the design to achieve greater efficiency and lower costs. In this research, two different sorting networks are implemented, namely, batcher odd-even mergesort, and the pairwise sorting network. These designs are implemented on the Zybo Z7 board which features a XC7Z010 FPGA. Their delay and performance are compared to demonstrate the relationship between design performance, power consumption, and hardware cost.