LUT (Look Up Table)

Una lookup table (de l'anglès "taula de consulta") és, en informàtica, una estructura de dades, normalment una array o una array associativa, que s'utilitza per substituir una subrutina o rutina de computació amb una simple indexació de les arrays. Son 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ó . Quant s'utilitza pel processament d'imatges, acostuma ha 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 funcions complexes com la trigonometria, logaritmes o funcions d'estadística. Similar a l'actualitat amb les taules de multiplicar, en que els nens a l'escola se les han de memoritzar per evitar els càlculs més comuns.

En els inicis de la història dels ordinadors, operacions d'entrada / sortida solien ser particularment lentes - fins i tot en comparació amb les velocitats del processador 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 ja sigui estàtica (integrada en el programa) o matrius dinàmiques precercades que continguessin únicament 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, l'aplicació de taules de cerca per nivell encara pot millorar el rendiment d'elements de dades que poques vegades o mai canvien.

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) s'utilitza 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 direcció de memòria, i pot també donar el pas d'interpolació al sinus del valor desitjat, en lloc de calcular-ho mitjançant una fórmula matemàtica. Les taules de consulta són utilitzatdes 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.

Funcions d'una sola variable (per exemple, sinus i cosinus) podran ser utilitzades per una matriu simple. Funcions que participen dos o més variables multidimensionals requereixen tècniques d'indexació de matrius. L'últim cas, 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ó. Pre-cà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 fer-se, però pot millorar enormement la precisió en aplicacions que requereixen la major precisió. Depenent dels valors que es pre-calculen, pre-càlcul 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, s'utilitza per determinar els colors i valors d'intensitat amb la qual es mostra una imatge en particular. De finestres a la tomografia computada es refereix a un concepte relacionat.

Tot i que sovint 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 pel 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 causa un error de memòria cau. Aquest fenomen s'està convertint en una qüestió tan 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'altre é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 sinusoïdal

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, 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 0)

Normalment, això pot arribar a ser un càlcul complex, especialment al alentir els processadors, i altres aplicacions, especialment si son càlculs gràfics, que necessiten calcular milers de valors sinusoïdals per segon. Una solució que s'utilitza 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:

 real array sine_table[-1000..1000]
 for x from -1000 to 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 utilitzats, fins uns 16000 bytes que poden ser necessitats. Es pot utilitzar uns quants exemples, però llavors la nostre precisió significativa serà més dolenta, ja que no serà tan precisa. Una bona solució és la interpolació lineal, que dibuixa una línea entre dos punts en una taula on a cada costat del valor correspon a una posició d'aquesta línea. Això és fàcil de calcular, i la majoria d'ordinadors utilitzen per calcular per exemple 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

// 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 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 composen una direcció 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 la direcció 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 un altre direcció cau).

Maquinari LUT

A la lògica digital, una taula de cerca de n bits es pot implementar amb un multiplexor on 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 al modelar funcions com ara taules de veritat. Aquesta és una forma eficient de codificació de les funcions de Boole , i taules de recerca amb 4-6 bits d'entrada són, de fet, el component clau de les FPGAs modernes.

Exemples

Càlcul sinusoïdal

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, 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 0)

Normalment, això pot arribar a ser un càlcul complex, especialment al alentir els processadors, i altres aplicacions, especialment si son càlculs gràfics, que necessiten calcular milers de valors sinusoïdals per segon. Una solució que s'utilitza 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:

 real array sine_table[-1000..1000]
 for x from -1000 to 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 utilitzats, fins uns 16000 bytes que poden ser necessitats. Es pot utilitzar uns quants exemples, però llavors la nostre precisió significativa serà més dolenta, ja que no serà tan precisa. Una bona solució és la interpolació lineal, que dibuixa una línea entre dos punts en una taula on a cada costat del valor correspon a una posició d'aquesta línea. Això és fàcil de calcular, i la majoria d'ordinadors utilitzen per calcular per exemple 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

// 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
};

Enllaços externs

• Fast table lookup using input character as index for branch table
• Art of Assembly: Calculation via Table Lookups
• Color Presentation of Astronomical Images

ca:Lookup table