Top K Sort

Overview

Top K Sort is a sorting algorithm which is used to calculate the maximum or the minimum K number of elements in the input stream. The algorithm is quite easy, and we can only get one data per clock due to the design requirements in L2 API. So in our design, we use a simple insert sort with ajustable maximum sorting number to get much better performance.

Algorithm

Top K Sort algorithm implementation:

cnt = 0
tmp[K] = {} //desending array
for each pair(key, pld) in
    if(cnt < K)
        insert_sort(tmp[], pair)
    else
        if(pair.key > tmp[k].key)
            insert_sort(tmp[], pair)

Implemention

The input stream should ensure that it have same number of key and pld. The internal design is based on insert sort algorithm.

The algorithm implemention is shown as the figure below:

Figure 1 : Architecture of Top K Sort

Profiling

The hardware resource utilizations are listed in the following table.

Table 1 : Hardware resources for Top K Sort with maximum sorting number 64

Table 1 Hardware resources for Sort Top K (Maximum sortNUM = 64)

Report	BRAM	URAM	DSP	FF	LUT	Frequency(MHz)
top_k_sort	0	0	0	5438	14061	300