Lookup-Tabelle

Definition und Grundaufbau

Lookup-Tabellen (LUT), auch Umsetzungstabellen genannt, sind Tabellen in der Informatik und Digitaltechnik. Sie definieren Informationen statisch und stellen sie zur Laufzeit eines Programms bereit. Dadurch können aufwändige Berechnungen oder ein hoher Speicherverbrauch vermieden werden.

Für bestimmte Konstellationen enthalten sie vorberechnete Ergebnisse oder andere Informationen. Jeder Eintrag wird entweder über einen Kurzcode als Suchbegriff oder über seine Position identifiziert; beispielsweise kann Eintrag 01–nn für den Sachverhalt 1–nn stehen. Ein Eintrag enthält die vordefinierte Information und bei Bedarf weitere Attribute. Während der Programmausführung wird über einen im Programm gebildeten oder verfügbaren Schlüssel auf den passenden Tabelleneintrag zugegriffen.

Nutzen und Verwaltung

LUTs ersetzen komplexe Berechnungen zur Programmlaufzeit durch eine in der Regel schnellere Wertsuche. Außerdem kann Speicherplatz eingespart werden: In großen Datenbeständen wird nur ein Kurzcode gespeichert, während die zugehörige Langbezeichnung aus der Tabelle verwendet wird.

Kurzcodes und Auswahlboxen mit möglichen Eingaben verringern den Erfassungsaufwand und die Fehlerwahrscheinlichkeit. Ausgelagerte Informationen, etwa Langbezeichnungen, lassen sich ändern, ohne die eigentlichen Datenbestände anzupassen.

Lookup-Tabellen können intern im Programm gespeichert werden, beispielsweise in speicherinternen Datenstrukturen. Alternativ liegen sie extern in einer Datenbanktabelle oder Datei und werden entweder direkt verwendet oder beim Programmstart in den internen Speicher geladen. Die Inhalte können statisch im Programm definiert, automatisch ermittelt und temporär gespeichert oder mit einer eigenen Anwendung beziehungsweise Standardwerkzeugen gepflegt werden. Statisch im Programm definierte Inhalte erfordern bei Änderungen eine neue Programmversion. Externe LUTs unterscheiden sich hinsichtlich ihrer Speicherungstechnik nicht von anderen Daten; ihre besondere Eigenschaft ist lediglich die Verwendung zum Nachschlagen.

Vorberechnete Ergebnisse und Interpolation

Bei einer LUT werden die Werte einer Funktion vorab berechnet und als Tabelle gespeichert. Das entspricht der Nutzung von Zinstabellen, Tafeln oder bestimmten Rechenschiebern aus der Zeit vor dem Taschenrechner. Technisch wird meist ein (assoziatives) Array verwendet. Ein einfacher indizierter Zugriff ersetzt dann eine komplizierte Berechnung und bringt einen deutlichen Geschwindigkeitsgewinn, sofern der Speicherzugriff schneller ist als die direkte Berechnung.

Da der Index mit einem geringerwertigen Datentyp gespeichert werden kann als die eigentlichen Tabellenwerte, kann die LUT zusätzlich Speicherplatz sparen. Ein klassisches Beispiel ist eine Sinustabelle: Einige Sinuswerte werden beispielsweise für jede ganze Gradzahl berechnet und gespeichert. Für einen später angeforderten Winkel rundet die Funktion auf eine ganze Gradzahl und liest den entsprechenden Wert aus der Tabelle.

Ein reelles Argument mit Nachkommastellen muss zunächst auf einen natürlichen Integer-Index abgebildet werden. Bei einer periodischen Funktion wird das Argument, wenn nur Werte aus der ersten Periode um 0 herum gespeichert sind, zuerst in das Periodenintervall abgebildet („reelles Modulo“) und danach gehasht, also auf eine Speicherstelle abgebildet. Zur Verbesserung der Genauigkeit kann zwischen mehreren benachbarten Tabelleneinträgen interpoliert werden, etwa zwischen der darüber und darunter liegenden ganzen Gradzahl. Dafür sind zusätzliche Berechnungen nötig; die Genauigkeit kann sich jedoch stark verbessern. Bei gleicher Genauigkeit kann die Tabelle dadurch auch kleiner ausfallen.

Grenzen der Laufzeitoptimierung

Eine Lookup-Tabelle ist nicht immer schneller als eine direkte Berechnung. Bei einfachen Berechnungen können langsame Speicherzugriffe, der zusätzliche Speicherbedarf und eine Beeinträchtigung des Prozessor-Caches die LUT sogar ungünstiger machen. Das gewinnt an Bedeutung, weil Mikroprozessoren zunehmend schneller als Speicherchips werden. Daher sind Optimierungen wie Sinustabellen bei modernen Prozessorgenerationen häufig unnötig oder sogar kontraproduktiv.

LUTs in integrierten Schaltungen

In der digitalen Schaltungstechnik werden auch sehr einfache Funktionen wie AND, OR und XOR durch LUTs ersetzt. Eine Tabelle lässt sich leichter anpassen als eine Transistorschaltung. Deshalb werden LUTs besonders in programmierbarer Logik, etwa in FPGAs, sowie bei kundenspezifisch hergestellten ICs (ASICs) eingesetzt.

Bei FPGAs wird die Tabelle in einem kleinen SRAM-Feld gespeichert. Mit einem Speicher von 16×1 Bit lässt sich jede logische Funktion mit 4 Eingängen realisieren und durch Programmierung ändern. Wie viele Eingänge eine LUT besitzt, hängt von der jeweiligen FPGA-Architektur ab.

In ASICs wird eine LUT unter anderem als (Masken-)ROM realisiert. Bei Gate-Arrays werden variable Grundschaltungen als LUTs vorgefertigt; nur wenige Fertigungsschritte, insbesondere die Metallisierung, werden speziell für den Kunden ausgeführt. Eine weitere Schaltungsvariante verwendet einen 2^n-nach-1-Multiplexer mit n Steuereingängen und 2^n Speicherstellen. Außerdem wurden PROM-Speicher zur Realisierung einer 8-Bit-ALU verwendet.

Lookup-Tabellen für Wertausprägungen

LUTs können beliebige anwendungsbezogene Inhalte enthalten, zum Beispiel Informationen je Bundesland, Branche, Kfz-Ortskennzeichen, Währung oder Fehlercode. Die Einträge bestehen in der Regel aus einer Kurz-Identifikation und weiteren Attributen, etwa einer ausführlichen Bezeichnung.

Bei der Datenerfassung werden nur in der LUT vorhandene Werte als gültig akzeptiert oder zur Auswahl angeboten. In den eigentlichen betrieblichen Daten wird statt der ausführlichen Bezeichnung nur der Kurzcode gespeichert; die Langbezeichnung kann bei Bedarf aus der LUT angezeigt werden. Änderungen an der Schreibweise müssen dadurch nur in der LUT vorgenommen werden.

Im Beispiel muss eine Bank monatlich die Kredithöhe je Branche melden. Die Meldung verlangt pro Branche eine Zeile mit ausführlicher Bezeichnung, etwa „Land- und Forstwirtschaft“, „öffentliche Haushalte“ oder „Industrie und Handwerk“. Die Reihenfolge ist fest vorgegeben. Die LUT enthält dafür Branchenschlüssel, Branchenbezeichnung und Zeilennummer. Für jeden Kredit beziehungsweise Kunden wird ein dreistelliger Branchenschlüssel gespeichert. Zur Meldung werden die Kreditsummen je Branchenschlüssel gebildet, nach der Zeilennummer aus der LUT sortiert und mit der zugehörigen Branchenbezeichnung ergänzt. Beispielhafte Zeilen sind „01 Öffentliche Haushalte – 1.234.567“ und „02 Land- und Forstwirtschaft – 567.890“; die Bezeichnung stammt aus der LUT, die Kreditsumme wird über den Branchenschlüssel aggregiert.