Tabela przeglądowa - Lookup table

W informatyce , A tabeli odnośników jest tablica , która zastępuje runtime obliczeń z prostszych operacji indeksowania tablicy. Oszczędności czasu przetwarzania mogą być znaczące, ponieważ pobieranie wartości z pamięci jest często szybsze niż przeprowadzanie „kosztownych” obliczeń lub operacji wejścia / wyjścia . Tabele mogą być wstępnie obliczane i przechowywane w statycznej pamięci programu, obliczane (lub „wstępnie pobierane” ) jako część fazy inicjalizacji programu ( zapamiętywanie ) lub nawet przechowywane w sprzęcie na platformach specyficznych dla aplikacji. Tabele przeglądowe są również szeroko używane do sprawdzania poprawności wartości wejściowych przez dopasowanie do listy prawidłowych (lub nieprawidłowych) elementów w tablicy, aw niektórych językach programowania mogą zawierać funkcje wskaźnikowe (lub przesunięcia do etykiet) w celu przetworzenia pasujących danych wejściowych. Układy FPGA w szerokim zakresie wykorzystują również rekonfigurowalne, zaimplementowane sprzętowo tabele wyszukiwania, aby zapewnić programowalną funkcjonalność sprzętową.

Historia

Część XX-wiecznej tablicy logarytmów wspólnych w książce Abramowitz and Stegun .

Przed pojawieniem się komputerów tablice przeglądowe wartości były używane do przyspieszania ręcznych obliczeń złożonych funkcji, takich jak trygonometria , logarytmy i statystyczne funkcje gęstości.

W starożytnych (499 rne) Indiach Aryabhata stworzył jedną z pierwszych tablic sinusoidalnych , którą zakodował w systemie liczbowym opartym na literach sanskrytu. W 493 roku Wiktoriusz z Akwitanii napisał 98-kolumnową tablicę mnożenia, która dawała ( cyframi rzymskimi ) iloczyn każdej liczby od 2 do 50 razy, a wiersze były „listą liczb zaczynającą się od tysiąca, malejącą przez setki do jednego. sto, następnie malejąco o dziesiątki do dziesięciu, potem jeden do jednego, a następnie ułamki do 1/144 „Współczesne dzieci w wieku szkolnym często uczą się zapamiętywać„ tabliczki mnożenia ”, aby uniknąć obliczeń najczęściej używanych liczb (do 9 x 9 lub 12 x 12).

Na początku historii komputerów operacje wejścia / wyjścia były szczególnie powolne - nawet w porównaniu do ówczesnych szybkości procesorów. Sensowne było ograniczenie kosztownych operacji odczytu poprzez formę ręcznego buforowania poprzez tworzenie statycznych tabel przeglądowych (osadzonych w programie) lub dynamicznych tablic wstępnie pobranych, aby zawierały tylko najczęściej występujące elementy danych. Pomimo wprowadzenia ogólnosystemowego buforowania, które teraz automatyzuje ten proces, tabele wyszukiwania na poziomie aplikacji mogą nadal poprawiać wydajność elementów danych, które rzadko, jeśli w ogóle, zmieniają się.

Tabele wyszukiwania były jedną z najwcześniejszych funkcji zaimplementowanych w komputerowych arkuszach kalkulacyjnych , a początkowa wersja programu VisiCalc (1979) zawierała LOOKUP funkcję wśród swoich pierwotnych 20 funkcji. Następnie pojawiły się kolejne arkusze kalkulacyjne, takie jak Microsoft Excel , i uzupełniono o funkcje VLOOKUP i HLOOKUP funkcje ułatwiające wyszukiwanie w tabeli pionowej lub poziomej. W programie Microsoft Excel XLOOKUP funkcja została uruchomiona od 28 sierpnia 2019 r.

Przykłady

Proste wyszukiwanie w tablicy, tablicy asocjacyjnej lub liście połączonej (lista nieposortowana)

Jest to znane jako przeszukiwanie liniowe lub przeszukiwanie siłowe , gdzie każdy element jest po kolei sprawdzany pod kątem równości, a związana z nim wartość, jeśli istnieje, jest używana jako wynik wyszukiwania. Jest to często najwolniejsza metoda wyszukiwania, chyba że często występujące wartości pojawiają się na początku listy. W przypadku jednowymiarowej tablicy lub listy połączonej wyszukiwanie ma zwykle na celu określenie, czy istnieje zgodność z wartością danych wejściowych.

Wyszukiwanie binarne w tablicy lub tablicy asocjacyjnej (lista posortowana)

Jako przykład algorytmu dziel i rządź ”, wyszukiwanie binarne polega na znalezieniu każdego elementu poprzez określenie, w której połowie tabeli można znaleźć dopasowanie, i powtarzanie go aż do sukcesu lub niepowodzenia. Jest to możliwe tylko wtedy, gdy lista jest posortowana, ale zapewnia dobrą wydajność nawet przy długich listach.

Trywialna funkcja skrótu

W przypadku trywialnego wyszukiwania funkcji skrótu niepodpisana nieprzetworzona wartość danych jest używana bezpośrednio jako indeks do jednowymiarowej tabeli w celu wyodrębnienia wyniku. W przypadku małych zakresów może to być najszybsze wyszukiwanie, nawet przekraczające prędkość wyszukiwania binarnego z zerowymi rozgałęzieniami i wykonywaniem w stałym czasie .

Liczenie bitów w serii bajtów

Jedynym dyskretnym problemem, który jest kosztowny do rozwiązania na wielu komputerach, jest zliczanie liczby bitów, które są ustawione na 1 w liczbie (binarnej), czasami nazywanej funkcją populacji . Na przykład liczba dziesiętna „37” to „00100101” w systemie dwójkowym, więc zawiera trzy bity, które są ustawione na binarnie „1”.

Prosty przykład kodu C , zaprojektowanego do zliczania 1 bitów w int , mógłby wyglądać następująco:

int count_ones(unsigned int x)
{
    int result = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        result++;
    }
    return result;
}

Ten pozornie prosty algorytm może zająć potencjalnie setki cykli nawet w nowoczesnej architekturze, ponieważ tworzy wiele gałęzi w pętli - a rozgałęzianie jest powolne. Można to poprawić za pomocą rozwijania pętli i kilku innych optymalizacji kompilatora. Istnieje jednak proste i znacznie szybsze rozwiązanie algorytmiczne - wykorzystujące trywialne przeszukiwanie tabeli funkcji skrótu .

Po prostu skonstruuj tablicę statyczną, bits_set , z 256 wpisami, podającymi liczbę bitów ustawionych w każdej możliwej wartości bajtu (np. 0x00 = 0, 0x01 = 1, 0x02 = 1 itd.). Następnie użyj tej tabeli, aby znaleźć liczbę jedynek w każdym bajcie liczby całkowitej za pomocą trywialnego wyszukiwania funkcji skrótu na każdym bajcie po kolei i zsumuj je. Nie wymaga to rozgałęzień i tylko czterech indeksowanych dostępów do pamięci, znacznie szybszych niż wcześniejszy kod.

/* Pseudocode of the lookup table 'uint32_t bits_set[256]' */
/*                    0b00, 0b01, 0b10, 0b11, 0b100, 0b101, ... */
int bits_set[256] = {    0,    1,    1,    2,     1,     2, // 200+ more entries

/* (this code assumes that 'int' is an unsigned 32-bits wide integer) */
int count_ones(unsigned int x)
{
    return bits_set[ x       & 255]
        + bits_set[(x >>  8) & 255]
        + bits_set[(x >> 16) & 255]
        + bits_set[(x >> 24) & 255];
}

Powyższe źródło można łatwo ulepszyć (unikając AND i przesuwania) przez „przekształcenie” „x” jako 4-bajtową tablicę znaków bez znaku i najlepiej zakodowane w linii jako pojedynczą instrukcję zamiast być funkcją. Zwróć uwagę, że nawet ten prosty algorytm może być teraz zbyt wolny, ponieważ oryginalny kod może działać szybciej z pamięci podręcznej nowoczesnych procesorów, a (duże) tabele wyszukiwania nie pasują dobrze do pamięci podręcznych i mogą powodować wolniejszy dostęp do pamięci (dodatkowo w powyższym przykładzie wymaga obliczenia adresów w tabeli, aby wykonać cztery potrzebne wyszukiwania).

Tablice przeglądowe w przetwarzaniu obrazu

Czerwony (A), zielony (B), niebieski (C) 16-bitowy plik tabeli przeglądowej. (Wiersze od 14 do 65524 nie są pokazane)

W zastosowaniach do analizy danych, takich jak przetwarzanie obrazu , tabela przeglądowa (LUT) jest używana do przekształcania danych wejściowych w bardziej pożądany format wyjściowy. Na przykład obraz planety Saturn w skali szarości zostanie przekształcony w kolorowy obraz, aby uwydatnić różnice w jej pierścieniach.

Klasycznym przykładem redukcji obliczeń w czasie wykonywania przy użyciu tabel przeglądowych jest uzyskanie wyniku obliczenia trygonometrycznego , takiego jak sinus wartości. Obliczanie funkcji trygonometrycznych może znacznie spowolnić działanie aplikacji komputerowej. Ta sama aplikacja może zakończyć się znacznie wcześniej, gdy najpierw wstępnie obliczy sinus z pewnej liczby wartości, na przykład dla każdej całkowitej liczby stopni (tabelę można zdefiniować jako zmienne statyczne w czasie kompilacji, co zmniejsza koszty powtarzalnego czasu wykonywania). Gdy program wymaga sinusa wartości, może użyć tabeli przeglądowej do pobrania najbliższej wartości sinusoidalnej z adresu pamięci, a także może interpolować do sinusa żądanej wartości, zamiast obliczać za pomocą wzoru matematycznego. Tabele przeglądowe są zatem używane przez koprocesory matematyczne w systemach komputerowych. Błąd w tabeli przeglądowej był odpowiedzialny za niesławny błąd dzielenia zmiennoprzecinkowego Intela .

Funkcje pojedynczej zmiennej (takiej jak sinus i cosinus) mogą być implementowane przez prostą tablicę. Funkcje obejmujące dwie lub więcej zmiennych wymagają wielowymiarowych technik indeksowania tablic. W tym drugim przypadku można zatem zastosować dwuwymiarową tablicę mocy [x] [y], aby zastąpić funkcję obliczającą x y dla ograniczonego zakresu wartości x i y. Funkcje, które mają więcej niż jeden wynik, można zaimplementować za pomocą tabel przeglądowych, które są tablicami struktur.

Jak wspomniano, istnieją rozwiązania pośrednie, które używają tabel w połączeniu z niewielką ilością obliczeń, często wykorzystując interpolację . Obliczenia wstępne w połączeniu z interpolacją mogą zapewnić wyższą dokładność dla wartości mieszczących się między dwiema wstępnie obliczonymi wartościami. Ta technika wymaga nieco więcej czasu do wykonania, ale może znacznie zwiększyć dokładność w zastosowaniach wymagających większej dokładności. W zależności od obliczanych wstępnie wartości, obliczenia wstępne z interpolacją mogą również służyć do zmniejszania rozmiaru tabeli przeglądowej przy zachowaniu dokładności.

W przetwarzaniu obrazu tabele przeglądowe są często nazywane LUT (lub 3DLUT) i podają wartość wyjściową dla każdego zakresu wartości indeksu. Jedna wspólna tablica LUT, zwana mapą kolorów lub paletą , służy do określania kolorów i wartości intensywności, z którymi będzie wyświetlany określony obraz. W tomografii komputerowej „okienkowanie” odnosi się do pokrewnej koncepcji określania sposobu wyświetlania intensywności mierzonego promieniowania.

Chociaż często skuteczne, stosowanie tabeli przeglądowej może jednak skutkować surową karą, jeśli obliczenia, które zastępuje LUT, są stosunkowo proste. Czas pobierania pamięci i złożoność wymagań dotyczących pamięci mogą zwiększyć czas działania aplikacji i zwiększyć złożoność systemu w porównaniu z tym, co byłoby wymagane w przypadku prostych obliczeń formuł. Problemem może również stać się możliwość zanieczyszczenia pamięci podręcznej . Dostęp do tabel dla dużych tabel prawie na pewno spowoduje utratę pamięci podręcznej . Zjawisko to staje się coraz większym problemem, ponieważ procesory wyprzedzają pamięć. Podobny problem pojawia się w przypadku rematerializacji , czyli optymalizacji kompilatora . W niektórych środowiskach, takich jak język programowania Java , przeszukiwanie tabel może być jeszcze droższe ze względu na obowiązkowe sprawdzanie granic obejmujące dodatkowe porównanie i rozgałęzienie dla każdego wyszukiwania.

Istnieją dwa podstawowe ograniczenia dotyczące tego, kiedy można skonstruować tabelę przeglądową dla wymaganej operacji. Jedną z nich jest ilość dostępnej pamięci: nie można skonstruować tabeli przeglądowej większej niż przestrzeń dostępna dla tabeli, chociaż możliwe jest skonstruowanie tabel wyszukiwania na dysku kosztem czasu wyszukiwania. Drugi to czas wymagany do obliczenia wartości tabeli w pierwszej kolejności; chociaż zwykle trzeba to zrobić tylko raz, jeśli zajmuje to zbyt długi czas, może to spowodować, że użycie tabeli przeglądowej będzie niewłaściwym rozwiązaniem. Jak już wspomniano, w wielu przypadkach tabele można definiować statycznie.

Obliczanie sinusów

Większość komputerów wykonuje tylko podstawowe operacje arytmetyczne i nie może bezpośrednio obliczyć sinusa podanej wartości. Zamiast tego używają algorytmu CORDIC lub złożonej formuły, takiej jak następujący szereg Taylora, do obliczenia wartości sinusa z dużą dokładnością:

(dla x bliskie 0)

Jednak może to być kosztowne do obliczenia, szczególnie na wolnych procesorach, a istnieje wiele aplikacji, szczególnie w tradycyjnej grafice komputerowej , które muszą obliczać wiele tysięcy wartości sinusoidalnych w każdej sekundzie. Typowym rozwiązaniem jest początkowe obliczenie sinusa wielu równomiernie rozłożonych wartości, a następnie, aby znaleźć sinus z x , wybieramy sinus o wartości najbliższej x . Będzie to bliskie poprawnej wartości, ponieważ sinus jest funkcją ciągłą z ograniczoną szybkością zmian. Na przykład:

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)]
Liniowa interpolacja części funkcji sinus

Niestety, tabela wymaga sporo miejsca: jeśli używane są liczby zmiennoprzecinkowe o podwójnej precyzji IEEE, potrzeba byłoby ponad 16 000 bajtów. Możemy użyć mniej próbek, ale wtedy nasza precyzja znacznie się pogorszy. Dobrym rozwiązaniem jest interpolacja liniowa , która rysuje linię między dwoma punktami w tabeli po obu stronach wartości i umieszcza odpowiedź w tej linii. Jest to nadal szybkie do obliczenia i znacznie dokładniejsze w przypadku płynnych funkcji, takich jak funkcja sinus. Oto przykład wykorzystujący interpolację liniową:

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)

Interpolacja liniowa zapewnia funkcję interpolowaną, która jest ciągła, ale generalnie nie ma ciągłych pochodnych . Aby uzyskać płynniejszą interpolację wyszukiwania w tabeli, która jest ciągła i ma ciągłą pierwszą pochodną , należy użyć sześciennej splajnu Hermite'a .

Innym rozwiązaniem, które zajmuje jedną czwartą miejsca, ale obliczenie zajmuje nieco więcej czasu, byłoby uwzględnienie relacji między sinusem i cosinusem wraz z ich regułami symetrii. W tym przypadku tabela przeglądowa jest obliczana przy użyciu funkcji sinus dla pierwszej ćwiartki (tj. Sin (0..pi / 2)). Kiedy potrzebujemy wartości, przypisujemy zmiennej jako kąt zawinięty do pierwszej ćwiartki. Następnie zawijamy kąt do czterech kwadrantów (nie jest to potrzebne, jeśli wartości są zawsze między 0 a 2 * pi) i zwracamy poprawną wartość (tj. Pierwsza ćwiartka jest prostym powrotem, druga ćwiartka jest odczytywana z pi / 2-x, trzecia i czwarty to negatywy odpowiednio pierwszego i drugiego). Dla cosinusa musimy tylko zwrócić kąt przesunięty o pi / 2 (tj. X + pi / 2). W przypadku tangensa sinus dzielimy przez cosinus (w zależności od implementacji może być potrzebna obsługa dzielenia przez zero):

function init_sine()
    for x from 0 to (360/4)+1
        sine_table[x] = sin(2*pi * x / 360)

function lookup_sine(x)
    x = wrap x from 0 to 360
    y = mod (x, 90)
    if (x <  90) return  sine_table[   y]
    if (x < 180) return  sine_table[90-y]
    if (x < 270) return -sine_table[   y]
    return -sine_table[90-y]

function lookup_cosine(x)
    return lookup_sine(x + 90)

function lookup_tan(x)
    return lookup_sine(x) / lookup_cosine(x)

Podczas korzystania z interpolacji rozmiar tabeli przeglądowej można zmniejszyć, stosując niejednorodne próbkowanie , co oznacza, że ​​gdy funkcja jest bliska prostej, używamy kilku punktów próbkowania, a gdy szybko zmienia wartość, używamy większej liczby punktów próbkowania, aby zachować przybliżenie blisko rzeczywistej krzywej. Aby uzyskać więcej informacji, zobacz interpolację .

Inne zastosowania tabel przeglądowych

Pamięci podręczne

Pamięci podręczne pamięci (w tym dyskowe pamięci podręczne dla plików lub pamięci podręczne procesorów dla kodu lub danych) działają również jak tabela przeglądowa. Tablica jest zbudowana z bardzo szybkiej pamięci zamiast być przechowywana w wolniejszej pamięci zewnętrznej i utrzymuje dwie części danych dla podzakresu bitów tworzących adres pamięci zewnętrznej (lub dysku) (w szczególności najniższe bity dowolnego możliwego adresu zewnętrznego) :

  • jedna sztuka (tag) zawiera wartość pozostałych bitów adresu; jeśli te bity pasują do tych z adresu pamięci do odczytu lub zapisu, to druga część zawiera zbuforowaną wartość tego adresu.
  • druga część przechowuje dane powiązane z tym adresem.

Przeprowadzane jest pojedyncze (szybkie) wyszukiwanie w celu odczytania znacznika w tabeli przeglądowej w indeksie określonym przez najmniejsze bity żądanego adresu pamięci zewnętrznej i określenia, czy adres pamięci został trafiony przez pamięć podręczną. Po znalezieniu trafienia nie jest potrzebny dostęp do pamięci zewnętrznej (z wyjątkiem operacji zapisu, w których buforowana wartość może wymagać asynchronicznej aktualizacji do wolniejszej pamięci po pewnym czasie lub jeśli pozycja w pamięci podręcznej musi zostać zmieniona, aby buforować inną adres).

Sprzętowe tabele LUT

W logice cyfrowej tablicę przeglądową można zaimplementować za pomocą multipleksera, którego linie wyboru są sterowane sygnałem adresowym i którego wejściami są wartości elementów zawartych w tablicy. Te wartości mogą być albo podłączone na stałe, jak w układzie ASIC, którego przeznaczenie jest specyficzne dla funkcji, lub dostarczane przez zatrzaski D, które pozwalają na konfigurowalne wartości. ( ROM , EPROM , EEPROM lub RAM .)

N -bitowego LUT może kodować dowolny n -input funkcji logicznej przez przechowywanie tablicę prawdy funkcji w LUT. Jest to skuteczny sposób kodowania funkcji logicznych Boole'a , a tablice LUT z 4-6 bitami danych wejściowych są w rzeczywistości kluczowym elementem nowoczesnych macierzy bramek programowalnych przez użytkownika (FPGA), które zapewniają rekonfigurowalne możliwości logiki sprzętowej.

Systemy akwizycji i kontroli danych

W systemach akwizycji i kontroli danych tablice przeglądowe są powszechnie używane do wykonywania następujących operacji w:

W niektórych systemach do tych obliczeń można również zdefiniować wielomiany zamiast tabel przeglądowych.

Zobacz też

Bibliografia

Linki zewnętrzne