Lookup table

Una lookup table (de l'anglès "taula de consulta") és, en informàtica, una estructura de dades, normalment una formació (array, en anglès) o una formació associativa, que es fa servir per substituir una subrutina o rutina de computació amb una simple indexació de les formacions. Són molt útils alhora d'estalviar temps de processament, perquè treu un valor de memòria informàtica i é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 d'obtenir resultats de funcions sense necessitat de fer el càlcul, utilitzant com a valor indexat el valor d'entrada, i com a valor que pren la posició el valor de la sortida de la funció. Quan es fa servir per al processament d'imatges, acostuma a anomenar-se LUT.

Història

Abans de l'arribada dels computadors, les LUT es feien servir per accelerar els càlculs a mà que havia de fer la gent per a funcions complexes, com la trigonometria, logaritmes o funcions d'estadística. És similar en l'actualitat a les taules de multiplicar, en què els nens a l'escola les han de memoritzar per evitar els càlculs més comuns.

En els inicis de la història dels ordinadors, les operacions d'entrada i sortida solien ser particularment lentes, fins i tot en comparació amb les velocitats dels processadors de l'època. No tenia gaire sentit reduir costoses operacions de lectura, per una forma d'emmagatzematge en memòria cau manual mitjançant la creació de taules de consulta, que pot ser o bé estàtica (integrada en el programa), o bé amb matrius dinàmiques precercades que continguessin únicament els elements més usats. Tot i la introducció de l'emmagatzematge en memòria cau de tot el sistema que ara automatitza aquest procés, en l'aplicació de taules de cerca per nivell encara es pot millorar el rendiment d'elements de dades, que canvien poques vegades o no ho fan mai.

Exemples

L.U.T.s en processament d'imatges

En les aplicacions d'anàlisi de dades, com ara processament d'imatges, una taula de cerca (LUT) es fa servir per transformar les dades entrants en un format de sortida més desitjable. Per exemple, una imatge en escala de grisos del planeta Saturn es transformarà en una imatge en color per emfatitzar les diferències en els seus anells.

Un exemple clàssic de la reducció de càlculs en temps d'execució utilitzant taules de consulta és per obtenir el resultat d'un càlcul de trigonometria, com ara el sinus d'un valor. Calcular funcions trigonomètriques és substancialment lent en una aplicació informàtica. La mateixa aplicació pot acabar molt abans quan per primera vegada pre-calcules el sinus d'un nombre de valors, per exemple, per a cada nombre enter de graus (a la taula es pot definir com a variables estàtiques en temps de compilació, reduint els costos d'execució). Quan el programa requereix el sinus d'un valor, pot utilitzar la taula de cerca per recuperar el valor més proper a una adreça de memòria, i pot també donar el pas d'interpolació al sinus del valor desitjat, en comptes de calcular-ho mitjançant una fórmula matemàtica. Les taules de consulta són utilitzades per les matemàtiques co-processades en els sistemes informàtics. Un error en una taula de consulta va ser el responsable d'un bug a Intel.

Les funcions d'una sola variable (per exemple, sinus i cosinus) podran ser utilitzades per una matriu simple, en canvi, en les funcions en què participen dues o més variables multidimensionals, requereixen tècniques d'indexació de matrius. L'últim cas, és el que pot emprar una matriu bidimensional de poder [x] [i] per substituir una funció per calcular xi per a una gamma limitada de valors x i i. Les funcions que tenen més d'un resultat poden ser implementades amb taules de cerca que són arranjaments d'estructures.

Com s'ha esmentat, hi ha solucions intermèdies que utilitzen les taules en combinació amb una petita quantitat de càlcul, sovint mitjançant la interpolació. L'ús del precàlcul combinat amb la interpolació pot produir una major precisió dels valors que cauen entre dos valors pre-calculats. Aquesta tècnica requereix una mica més de temps per fer-se, però pot millorar enormement la precisió en aplicacions que requereixen la major precisió. Depenent dels valors que es precalculen, el precàlcul juntament amb la interpolació també es pot utilitzar per reduir la mida de la taula de cerca mentre es manté la precisió.

En el processament d'imatges, les taules de cerca sovint s'anomenen LUT i donen un valor de sortida per a cada un d'una sèrie de valors indexats. Una LUT comú, denominada mapa de colors o paleta, es fa servir per determinar els colors i valors d'intensitat amb la qual es mostra una imatge en particular. Del sistema windows a la tomografia computada es refereix a un concepte relacionat.

Tot i que sovint resulta eficaç utilitzar una taula de cerca, pot tenir com a efecte una sanció severa si el càlcul que substitueix la LUT és relativament simple. El temps de recuperació de la memòria i la complexitat dels requisits de memòria, poden augmentar el temps de funcionament i aplicació del sistema en relació a la complexitat del que seria necessari per al càlcul formulat. La possibilitat de contaminació de la memòria cau també es pot convertir en un problema. Els accessos per a taules grans és, gairebé segur, que causen un error de memòria cau. Aquest fenomen s'està convertint en una qüestió molt important pels processadors de memòria. Un problema similar apareix en rematerialització, una optimització del compilador. En alguns entorns, com el llenguatge de programació Java, les recerques de la taula poden ser encara més costoses a causa dels límits obligatoris de comprovació de la participació addicional, i una comparació per a cada branca de cerca.

Hi ha dues limitacions importants quan és possible construir una taula de consulta per a una operació necessària. Una és la quantitat de memòria que està disponible: no es pot construir una taula de cerca més gran que l'espai disponible per a la taula, encara que és possible construir taules de cerca basades en disc a costa de temps de cerca. L'altra és el temps necessari per calcular els valors de la taula en la primera instància, encara que això generalment s'ha de fer només una vegada, si es pren un temps excessivament llarg, pot fer l'ús d'una taula de cerca una solució adequada. Com ja es va assenyalar, però, les taules poden ser definides de forma estàtica en molts casos.

Càlcul sinusoidal

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

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

(per x fins 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 sinusoidals per segon. Una solució que es fa servir inicialment és calcular el sinus de molts valors que estan distribuïts, i llavors trobar el sinus de x el valor que li correspon. Això serà un valor correcte perquè el sinus és una funció contínua amb un rang que va canviant. Per exemple:

funció real de la taula del sinus[-1000..1000]
per a x de -1000 a 1000
taula del sinus[x] := sinus (pi * x / 1000)

funció del sinus en lookup (x)
tornar a la taula del sinus[round(1000 * x / pi)]

Afortunadament, la taula que necessitem és un espai de bits: des de la IEEE que és de doble precisió, com a flotant o altres valors utilitzats, fins a uns 16000 bytes que poden ser necessitats. Es pot 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 en la qual cada costat del valor es correspon amb una posició d'aquesta línia. Això és fàcil de calcular, i la majoria d'ordinadors l'utilitzen per calcular per exemple la funció del sinus. Un exemple de la interpolació lineal és la següent:

funció del sinus en lookup(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

// C 8-bit Sine Table
const unsigned char sinetable[256] = {
	128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174,
	176,179,182,185,188,191,193,196,199,201,204,206,209,211,213,216,
	218,220,222,224,226,228,230,232,234,236,237,239,240,242,243,245,
	246,247,248,249,250,251,252,252,253,254,254,255,255,255,255,255,
	255,255,255,255,255,255,254,254,253,252,252,251,250,249,248,247,
	246,245,243,242,240,239,237,236,234,232,230,228,226,224,222,220,
	218,216,213,211,209,206,204,201,199,196,193,191,188,185,182,179,
	176,174,171,168,165,162,159,156,152,149,146,143,140,137,134,131,
	128,124,121,118,115,112,109,106,103,99, 96, 93, 90, 87, 84, 81, 
	79, 76, 73, 70, 67, 64, 62, 59, 56, 54, 51, 49, 46, 44, 42, 39, 
	37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 18, 16, 15, 13, 12, 10, 
	9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 
	0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 
	9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 25, 27, 29, 31, 33, 35, 
	37, 39, 42, 44, 46, 49, 51, 54, 56, 59, 62, 64, 67, 70, 73, 76, 
	79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124
};

Altres utilitzacions de LUT

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 d'una forma molt ràpida, 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 aquests bits coincideixen amb els de l'adreça de memòria per 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, en les quals 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 de cert temps, o si la posició en la memòria cau ha de ser reemplaçada a una altra direcció cau).

Maquinari LUT

En la lògica digital, una taula de cerca de n bits es pot implementar amb un multiplexor en què les línies de selecció són les entrades de la LUT i els resultats són constants. Una LUT de n bits pot codificar qualsevol n-input funció Booleana en modelar funcions com ara taules de veritat. Aquesta és una forma eficient de codificació de les funcions de Boole, i les taules de recerca amb 4-6 bits d'entrada són, de fet, el component clau de les FPGAs modernes.