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.