# Note tecniche e cronologia del kNN OpenCL

Questo documento raccoglie il percorso sperimentale che ha portato al motore kNN OpenCL. Per installazione, compilazione e uso dei binari consultare `README.md`.

## Obiettivo

Input:

```text
float32[N][128]
```

Gli embedding sono normalizzati L2, quindi cosine similarity e prodotto scalare coincidono. Output:

```text
indices[query_count][TOPK]
scores[query_count][TOPK]
```

## Baseline

```text
DIM=128
TOPK=32
QUERIES=256
LANES_PER_QUERY=8
CHUNK_SIZE=50000
```

## Risultati sperimentali principali

### Numero di lane

```text
LANES=4:   9.60 GOP/s
LANES=8:  10.57 GOP/s
LANES=16:  4.04 GOP/s
LANES=32:  1.49 GOP/s
```

Otto lane sono risultate la configurazione più equilibrata.

### Stage benchmark

```text
DOT:             72.79 M vector/s
DOT+threshold:   83.47 M vector/s
TOPK score:      77.94 M vector/s
TOPK+indici:     76.28 M vector/s
kNN completo:    75.22 M vector/s
```

### Vettorizzazione

```text
scalar: 74.37 M vector/s
float4: 84.14 M vector/s
float8: 83.49 M vector/s
```

Database e query entrambi float4 hanno raggiunto 84.13 M vector/s.

### Accumulatori

```text
F4 singolo accumulatore: 74.53 M vector/s
F4 quattro accumulatori: 83.47 M vector/s
F4 quattro acc + unroll2: 70.53 M vector/s
F8 quattro accumulatori: 82.76 M vector/s
```

L'unrolling esplicito ha peggiorato il code generation del compilatore Mali.

### Pressione sui registri

Una query mantenuta in `private float4 query[DIM4]` ha ridotto le prestazioni a 17.85 M vector/s. Rimuovendo l'array privato si è risaliti a circa 65 M vector/s.

### Strategie TOPK

```text
sorted insertion:        78.37 M vector/s
min-replace:             81.99 M vector/s
threshold + min-replace: 82.02 M vector/s
```

### Dimensione TOPK

```text
TOPK=8:  73.87 M vector/s
TOPK=16: 84.60 M vector/s
TOPK=32: 82.53 M vector/s
TOPK=64: 78.81 M vector/s
```

## Benchmark da 350000 embedding

```text
Database: 350000
Query: 256
Dimensione: 128
TOPK: 32
Chunk: 50000
Confronti: 89600000
```

Variante min-replace:

```text
KNN kernel: 1244.576 ms
Merge GPU: 8.022 ms
Merge CPU globale: 14.039 ms
Tempo complessivo: 1266.638 ms
Vector rate: 71.992 M vector/s
Dot rate: 18.430 GFLOP/s
Traffico: 36.860 GB/s
Indici non validi: 0
```

Benchmark parametrico:

```text
CPU: 9663.226 ms
OpenCL: 1373.797 ms
Speedup: 7.034x
Posizioni TOPK identiche: 8192 / 8192
Exact ratio: 100%
```

## Trasformazione in motore dinamico

Il kernel produttivo usa definizioni configurabili:

```c
#ifndef DIM
#define DIM 128
#endif

#ifndef TOPK
#define TOPK 32
#endif

#ifndef QUERY_COUNT
#define QUERY_COUNT 1
#endif

#ifndef LANES_PER_QUERY
#define LANES_PER_QUERY 8
#endif
```

Il limite fisso `q >= 256` è diventato `q >= QUERY_COUNT`. Le definizioni vengono passate a `clBuildProgram` insieme a `-cl-fast-relaxed-math`.

## Backend CPU

È stato generalizzato per conteggi e dimensione dinamici, TOPK sicuro, ordinamento deterministico, rifiuto di valori non finiti e layout identico a OpenCL.

## Backend OpenCL

Il backend:

1. enumera piattaforme e GPU;
2. seleziona preferibilmente Mali-G610;
3. carica il kernel da file;
4. compila con parametri runtime;
5. alloca buffer riutilizzabili;
6. copia il database a chunk;
7. esegue il kernel;
8. legge indici e score;
9. converte indici locali in globali;
10. effettua il merge TOPK;
11. rilascia le risorse tramite RAII.

## Diagnostica Mali

Il runtime Mali emette `arm_release_ver` direttamente su stdout. La CLI devia temporaneamente stdout verso stderr durante OpenCL e lo ripristina prima della scrittura JSON.

## Validazione reale

Prototype:

```text
0 IMG_0145.JPG cluster_medoid
1 IMG_0141.JPG cluster_medoid
2 IMG_0193.JPG cluster_medoid
3 IMG_0143.JPG greedy_leave_one_out_gain
4 IMG_0146.JPG greedy_leave_one_out_gain
```

Risultato:

```text
Query: 21
Prototype: 5
Riconosciuti: 20
Sotto soglia: 1
Copertura: 95.2%
Caso sotto soglia: IMG_0183.JPG
Score: 0.466428
Miglior prototype: IMG_0143.JPG
```

Python contro C++ CPU:

```text
Query confrontate: 21
Mismatch top-1: 0
Mismatch decisione: 0
Errore massimo: 2.643e-7
```

C++ CPU contro OpenCL:

```text
Dopo leave-one-out: 100 / 100 posizioni identiche
TOPK grezzo: 105 / 105 posizioni identiche
Errore massimo: 3.58e-7
```

## File di riferimento

```text
modules/knn-opencl/reference/knn_benchmark.cpp
modules/knn-opencl/reference/knn_float4_minreplace_validate_benchmark.cpp
modules/knn-opencl/reference/validation-opencl-350k.txt
modules/knn-opencl/reference/validation-minreplace-350k.txt
modules/knn-opencl/reference/VALIDATION.md
VALIDATION_JESSICA.md
```

## Sviluppi futuri

```text
backend auto
cache del programma OpenCL
indice persistente dei prototype
margine fra prima e seconda identità
modalità shadow applicativa
metriche operative
```