# Test (SYCL): Neighbor Coverage
Let us have a mesh network of `N` devices located in a terrain (represented as points in 2D Euclidean space) and a transmission radius `r` (maximal Euclidean distance for direct communication). We need to determine how many neighbors are directly accessible by each node.

Implement a parallel algorithm in SYCL that solves the neighbor coverage problem. It computes L2 distance from each node to all other nodes (i.e.,` N*(N-1)` distances in total), compares it with the transmission radius `r`, and counts how many neighbors are within the radius for each node.

The node locations are represented as a 2D grid; the first dimension is fixed to size 2 (corresponding to the `x`, `y` coordinates), and the second dimension size is the number of nodes `N`. Since the first dimension is the more compact one, this representation is equivalent to an array of `N` points, where each point is a pair or a structure of `x`, `y` coordinates. The output is a 1D array of size `N`, where the i-th element corresponds to the number of neighbors of the i-th node (and the application writes it to the output file in text format, one number per line).

## Technical details
The starter pack with the serial implementation and makefile is available to you on the `hpc.troja.mff.cuni.cz` server in `/home/teaching/NPRG042/labtest`. The performance will be tested on the `volta02` machine, using two V100 GPUs (same as in the SYCL home assignment).

The referential serial implementation can be found in the `serial.hpp` file (the` operator()` of the `SerialImplementation` class). You need to implement the SYCL version in the `sycl.hpp` file (the interface of the `SyclImplementation` class must be preserved), and the `sycl.hpp` file **is the only file you should submit to ReCodEx**.

The point datasets are available in the `/home/teaching/NPRG042/labtest/data` directory. The `points-*` files will be used for performance evaluation, while the `debug-*` files can be used for debugging, and they will be tested in ReCodEx to verify correctness. Each dataset has a corresponding `*.serial` file with the output of the serial algorithm for the given input.

## Evaluation
ReCodEx only evaluates the correctness of the implementation. You need to test the performance on the `volta02` worker yourselves. Your solution will be tested on the `16k`, `32k`, and `64k` point datasets with radius `r` set to `1.0`, and the harmonic mean of the speedups (of the parallel version over the serial one) will be used to determine your points. The grading table is as follows:

- 50× or less: **0 points**
- 50× to 100×: **1 point**
- 100× to 200×: **2 points**
- 200× to 300×: **3 points**
- 300× or more: **4 points**
You may use the associated `test.sh` script to test the correctness and performance of your implementation. Beware that the testing script uses strict `diff` to compare the results. ReCodEx uses a slightly more benevolent judge, which allows minor differences that may have been caused by the non-deterministic order of floating-point operations in the parallel implementation. So if you encounter validation errors (from the `test.sh` script), it is possible that your solution is actually correct (but it is still advisable to double-check it).

## Hints
Please note that both the `Grid` class and SYCL multi-dimensional buffers use row-major order. **However, they differ in the order in which the dimension coordinates are specified.** In the case of our `Grid`, dimension 0 represents point coordinates (`0=x`, `1=y`), and dimension 1 is the index of the point. When creating the corresponding SYCL buffer, one needs to specify `sycl::range<2>{N, 2}`. If you wish to use `sycl::id<2>` to index into the buffer, you also need to write the dimensions in reverse order (i.e., `id[1]` is the x/y selection, and `id[0]` is the point index).

If you are not comfortable with SYCL multi-dimensional buffers, you can also use 1D buffers and calculate the corresponding 1D index from the 3D/4D coordinates yourselves (and vice versa). The linear buffer should have `N*2` elements, and the i-th point's x/y coordinates are located at `buffer[2*i]` and `buffer[2*i+1]`, respectively.

Note that SYCL imposes limits on the size of the parallel-for index space. So creating an `N x N` index space may be too much for the given datasets. However, you may choose to run parallel-for only over the set of points (`N`), or use a tiling technique (one work-item processes a tile/stripe of points).

The Euclidean distance is symmetric, so if point A is a neighbor of point B, then point B is also a neighbor of point A. However, it is slightly more difficult to correctly iterate over the upper triangle of the distance matrix (to avoid redundant calculations) in a parallel implementation. So it might be better to have the full-matrix solution working first, before trying more difficult optimizations.