Lookup table

De Viquipèdia
Dreceres ràpides: navegació, cerca

En informàtica, una "lookup table" és una estructura de dades, normalment una array o una array associativa, que és feta servir per reemplaçar una rutina de computació amb una simple indexació d'arrais. Són molt útils si parlem d'estalvi de temps de processament perquè treure un valor de memòria és molt més ràpid que fer una gran computació.

Un exemple pràctic de la utilitat d'una lookup table és el seu ús per obtenir resultats de funcions sense necessitat de fer el càlcul, utilitzant com a valor d'indexació el valor d'entrada i com a valor que pren la posició, el valor de sortida de la funció. Quan s'utilitza per al processament d'imatges, s'acostuma a anomenar LUT, i es pot utilitzar per exemple com a paleta de colors, per a obtenir valors de brillantor i intensitat d'una imatge.

Exemples[modifica | modifica el codi]

Càlcul sinusoïdal[modifica | modifica el codi]

La majoria d'ordinadors, que només fan operacions bàsiques aritmètiques, no poden directament calcular el sinus d'un valor. Normalment usen un algorisme o una fórmula complexa com poden ser les sèries de Tailor, a partir d'aquests, calculen el sinus d'un valor amb força precisió:

\operatorname{sin}(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}

(perxfins a 0)

Normalment, això pot arribar a ser un càlcul complex, especialment en alentir els processadors, i altres aplicacions, especialment si són càlculs gràfics, que necessiten calcular milers de valors sinusoïdals per segon. Una solució que s'usa inicialment és calcular el si de molts valors que estan distribuïts, i llavors trobar del sinus dexel valor que li correspon. Això serà un valor correcte perquè el sinus és una funció continua amb un rang que va canviant. Per exemple:

 Real arraysine_table [-1000 .. 1000]
 For xfrom -1000to 1000
     sine_table [x]: = sine (pi * x / 1000)
 Function lookup_sine (x)
     Return sine_table [round (1000 * x / pi)]
Interpolació lineal d'un fragment del sinus

Afortunadament, la taula que necessitem és un espai de bits: si la IEEE de doble precisió, coma flotant o altres valors usats, fins a uns 16.000 bytes que poden ser necessitats. Nosaltres podem utilitzar uns quants exemples, però llavors la nostra precisió significativa serà més dolenta, ja que no serà tan precisa. Una bona solució és la interpolació lineal, que dibuixa una línia entre dos punts en una taula on a cada costat del valor correspon a una posició d'aquesta línia. Això és fàcil de calcular, i la majoria d'ordinadors l'utilitzen per calcular ara la funció del sinus. Un exemple de la interpolació lineal és la següent:

 Function lookup_sine (x)
     x1: = floor (x * 1000/pi)
     y1: = sine_table [x1]
     y2: = sine_table [x1 +1]
     Return y1 + (y2-y1) * (x * 1000/pi-x1)

Exemple de taula Look Up Table a partir de la interpolació lineal:

Exemple de la taula del sinus[modifica | modifica el codi]

// C 8-bit Sine Table

Altres utilitzacions de LUT[modifica | modifica el codi]

Cache

Caches d'emmagatzematge (incloent dipòsits en disc per a arxius, o cachés de processador, ja sigui per al codi o dades) que treballen també com una taula de cerca. La taula es construeix amb la memòria molt ràpidament en comptes de ser emmagatzemada en una memòria externa més lenta, i manté dos tipus d'informació per a un sub-rang de bits que componen una adreça de memòria externa (o disc).

Una peça (l'etiqueta) conté el valor dels bits restants de la direcció, i si aquests bits coincideixen amb els de l'adreça de memòria per a llegir i escriure, i després l'altra peça conté el valor emmagatzemat en memòria cau d'aquesta direcció. L'altra peça manté les dades associades a aquesta direcció.

Un simple (ràpid) porta a terme operacions de cerca per llegir l'etiqueta a la taula de cerca a l'índex especificat pels bits més baixos de la direcció d'emmagatzematge externa desitjada, i per determinar si l'adreça de memòria és colpejada per la memòria cau. Un cop es troba, no és necessari l'accés a la memòria externa (a excepció de les operacions d'escriptura, on el valor emmagatzemat a la memòria cau pot ser necessari actualitzar-lo de manera asincrònica a la memòria més lenta després d'algun temps, o si la posició en la memòria cau ha de ser reemplaçat a una altra direcció cau).

Maquinari LUT

En lògica digital, una lookup table de n bits pot ser implementada amb un multiplexor, on les línies seleccionades són les entrades de la LUT i les sortides són constants. Una LUT de n bits pot codificar qualsevol funció booleana de n entrades simulant cada funció com una taula de veritat. Aquesta és una solució eficient per codificar les funcions lògiques booleanes, i les LUT de 4-6 bits són el component clau de les FPGAs modernes.