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