# A Modified KNN Algorithm for High-Performance Computing on FPGA of Real-Time m-QAM Demodulators
## 2 Scalable Multicore KNN-Based Demodulator
### Scalable Multicore Architecture Based on Cupus  
We propose a scalable multicore architecture based on CuPUs to improve the performance of the KNN algorithm. This architecture was designed for field-programmable gate array (FPGA), seeking to exploit the inherent parallelism that characterizes them. Scalable design is intended to be used in different FPGA targets. We define a parameter \(N\) as the number of cores of each of the CuPUs used in the design, i.e., \(N=3\) implies using 3 Calculate Distances CuPU, 3 Sort Distance CuPU, and 3 Calculate Mode CuPU, see Figure 1.  
We define \(N\) as the number of symbols entering the CuPUs for processing in parallel. Optimization directives such as pipelining, unrolling, and partitioning are added to the  
Figure 1: A general architecture for the KNN algorithm using N numbers of CuPUs in parallel.  
CuPUs to increase operational concurrency and improve performance. All High-Level Synthesis (HLS) tools use optimization directives for algorithm acceleration on hardware.  
In a communications system, a transmitter sends symbols through a single channel or multiple channels to the receiver. For this reason, our design stores the symbol streams in buffers for separating into \(N\) independent symbols for parallel processing in different CuPUs, see Figure 2. The independence in the operations on each input symbol in the KNN algorithm allows the parallel processing of multiple channels using the same training data. In turn, each channel can be processed on multiple cores, expressing this as \(N=C\times N_{C}\), where \(C\) is the number of channels, and \(N_{C}\) is the number of cores per channel.  
A Calculate Distance CuPU computes the distance between each symbol and the \(L\) training samples. The \(L\) distance calculations applied to each symbol are also independent operations allowing unrolling operation on the loop. The unroll directive increases the consumption of hardware resources, and when resources are limited, it is convenient to perform a partial unroll. The combination of unrolling and the pipeline directive allows the reuse of resources.  
After the distance calculation, it is necessary to sort the L values of the distance array in the Sort Distance CuPU. The sorting algorithm used is a Restructured Merge Sort [27], and it is a sorting algorithm optimized through directives in HLS for implementation in FPGA. The training data labels are sorted simultaneously with the distance array. \(N\) label array copies guarantee the parallel processing in the \(N\) cores, see Figure 3.  
The Calculation Mode CuPU selects the first \(K\) labels from the sorted array, see Figure 3. The modal value serves to assign the right cluster of the constellation to the input symbol. In m-QAM schemes, there are \(m\) different labels.  
This section presented the design of a scalable multicore architecture based on CuPUs. The architecture considers the particularities of communication systems when implementing real-time demodulators based on the KNN algorithm on FPGAs. The design has a focus on m-QAM, but it is not limited to this type of modulation. In the following section, we propose a modified version of the KNN algorithm to reduce the number of operations bringing the focus closer to m-QAM based on the constellation shape.  
Figure 2: Calculate distance CuPUs by processing \(N\) symbols in parallel. The buffer converts the serial data in parallel.