Tabelle di Lookup (LUT): Accesso Veloce ai Dati tramite Precomputazione
Tabelle di Lookup (LUT): Accesso Veloce ai Dati tramite Precomputazione
Una **Tabella di Lookup (LUT)** è una struttura dati che sostituisce il **calcolo in fase di esecuzione** con l'**accesso alla memoria**. Mette in corrispondenza chiavi di input con valori di output precalcolati, scambiando spazio di archiviazione per velocità e determinismo.
Concetto Fondamentale
Input (Chiave) ──► [ Memoria LUT ] ──► Output (Valore) Array Indice Dati
- Complessità Temporale: O(1) — Singola lettura di memoria (indice array) o ricerca hash.
- Complessità Spaziale: O(N) — N voci memorizzate.
- Determinismo: Latenza fissa (critico per sistemi real-time / hard RTOS).
Forme di Implementazione
| Forma | Struttura | Caso d'Uso |
|---|---|---|
| Array / Vettore 1D | output = table[input] | Mappatura diretta: Sin(x), Correzione Gamma, Linearizzazione termocoppia, CRC8. |
| Array Multi-D 2D | output = table[x][y] | Interpolazione bilineare, Macchine a stati, Tabelle della verità (porte logiche). |
| Hash Map / Dizionario | output = dict[key] | Chiavi sparse, Chiavi non intere (stringhe, enum), Tabelle dinamiche. |
| Block RAM FPGA/ASIC | Blocchi di memoria hardware | DSP: Seno/Coseno, CORDIC, Coefficienti FIR, Conversione spazio colore (RGB→YUV). Latenza zero. |
| Memoria Texture (GPU) | Texture 1D/2D/3D in cache | Grafica: Filtraggio, Mipmap. Calcolo: LUT interpolate. |
Applicazioni Classiche
- Funzioni trascendenti: sin, cos, log, exp, sqrt — dove l'istruzione HW manca o è lenta (MCU 8-bit, soft-core FPGA).
- Linearizzazione: Termocoppia (Tipo K, J, T), RTD (Callendar-Van Dusen), Polinomio sensore pressione.
- Colore / Gamma: sRGB ↔ Lineare, CMYK ↔ RGB, LUT 3D (Color Grading, cubi 17×17×17).
- Comunicazioni Digitali: Mappatura modulazione (Costellazione QAM), Metriche ramo decodificatore Viterbi, CRC (guidato da tabella).
- Sistemi di Controllo: Programmazione di gain (valvola non lineare → linearizzata), Profili camme.
- Crittografia: S-Box (AES SubBytes), Costanti Montgomery precalcolate.
- Sviluppo Giochi: Lightmap, Shadow map, GI pre-cotto, Curve di animazione.
Considerazioni di Progettazione
- Risoluzione vs Dimensione: Input 8-bit = 256 voci. 16-bit = 65.536 voci. Interpolazione (lineare/cubica) riduce le voci necessarie.
- Costo di Inizializzazione: Calcola una volta all'avvio / in fase di compilazione (constexpr). Incorpora nel binario.
- Località della Cache: LUT piccole entrano in L1 cache. LUT grandi → miss di cache → più lente del calcolo.
- Accuratezza: Errore di quantizzazione (arrotondamento indice input) + Precisione output. L'interpolazione riduce l'errore.
- Volatilità: Statico (ROM/Flash) vs Dinamico (RAM, aggiornato in fase di esecuzione — es. equalizzatore adattivo).
Esempio di Interpolazione (1D Lineare)
float lut_interp(const float* table, int n, float x, float x_min, float x_max) { float idx = (x - x_min) * (n - 1) / (x_max - x_min); int i = (int)floorf(idx); float frac = idx - i; i = clamp(i, 0, n - 2); return table[i] * (1 - frac) + table[i + 1] * frac; }
Quando NON Usare una LUT
- La funzione è semplice e veloce (es.
y = 2*x + 1). Il calcolo vince. - L'intervallo di input è enorme / precisione continua alta (es. float 32-bit → 4 miliardi di voci impossibili).
- Memoria severamente limitata (MCU minuscolo, 2KB RAM) e la funzione è calcolabile in < 10 cicli.
- I dati cambiano ogni ciclo (nessun riutilizzo).
In sintesi: Le LUT sono una **tecnica di ottimizzazione fondamentale** — "Spazio per Tempo". Ubiquitarie in sistemi embedded, DSP, grafica, crittografia e calcolo scientifico. Profila prima: misura cicli di calcolo vs larghezza di banda/latenza della memoria.