Internals of Bitonic SortΒΆ
This document describes the structure and execution of Bitonic Sort, implemented as bitonicSort function. Bitonic sort is a special kind of sorting network, where the sequence of comparisons is not data-dependent. This makes sorting networks suitable for implementation in hardware or in parallel processor arrays. The computing complexity of bitonic sort is O(n*log(n)2).
Bitonic sort have giant data throughput and it demands large resource same time. It is well-fitted for the application with high band of data input. The table shows the resource consumption for an instance of bitonic sort with input bitwidth=32.
BitonicSortNumber 8 16 32 64 Lantency 22 42 79 149 Interval 9 17 33 65 LUT 2647 7912 21584 58064 Register 3136 9291 26011 69160
If the bitonic sort number grow twice, the resource consumption of bitonic sort will grow around four times theoretically.
Important
The current version of bitonic sort is stream in and stream out. The bitonic sort number must be a power of two because of the algorithm restriction. Combine it with Merge Sort primitive can achieve arbitrary sort number, see reference Internals of Merge Sort.
Caution
The size of bitonic sort number should be set with the consideration of FPGA resource to pass place and route.
This bitonicSort
primitive has one port for key input, one port for payload input, one port for key output, one port for payload output and one boolean sign for indicating ascending sort or descending sort.