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 Processing Structure

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.

Bitonic Sort Resource Consumption in FPGA

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.