SPEC-Benchmarks

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Unter dem Namen „System Performance Evaluation Cooperative" (SPEC) schlossen sich 1988 vier Herstellerfirmen, vor allem Hersteller von RISC-Mikroprozessoren, zusammen um durch eine Zusammenstellung von geeigneten Benchmarks eine einheitliche Basis für die Leistungsbewertung von Computern und speziell von Mikroprozessoren des oberen Leistungsbereichs zu schaffen. Inzwischen sind weitere bedeutende Firmen beigetreten, heute beteiligen sich an SPEC AT&T, Bull, CdC, Compaq, Data General, DEC, Du Pont, Fujitsu, Hewlett-Packard, IBM, Intergraph, MIPS, Motorola, NCR, Siemens Nixdorf, Silicon Graphics, Solbourne, Stardent, SUN und Unisys.

Ausgangspunkt für SPEC war ein weit verbreitetes Gefühl der Unzufriedenheit mit Leistungsangaben insbesondere in der Mikroprozessor-Welt: Jeder Hersteller gibt MIPS- und MFLOPS-Werte für seine Produkte an, aber es gab und gibt keine verbindliche Definition, wie diese Werte zu gewinnen sind [1]. Die wörtliche Definition von MIPS als „Million Instructions Per Second" hat für Vergleiche zwischen unterschiedlichen Prozessorlinien und vor allem zwischen RISC- und CISC-Prozessoren (Reduced bzw. Complex Instruction Set Computer) jegliche Relevanz als Maßstab für den Kunden verloren. Der RISC-Ansatz bedeutet ja gerade, ein Programm aus der höheren Sprache in mehr, aber einfachere und daher wesentlich schnellere Befehle zu übersetzen. Auch der Ausweg, die wörtliche Bedeutung von „MIPS" zu ignorieren und unter der MIPS-Zahl das Verhältnis der Leistung im Vergleich zu VAX11/780 zu verstehen (ein in der Handelspresse oft übliches Verfahren), hat seine Probleme, denn die Auswahl der zu messenden Programme, der Programmiersprache und der Compiler für die VAX hat großen Einfluß auf das Ergebnis.

Einen Ausweg bieten Benchmark-Programme, die für einen bestimmten Bereich der Programmierung (z.B. numerische Programmierung, Systemprogrammierung) repräsentativ sind. Sie wurden entweder als „Kernels" aus häufig durchlaufenen Programmteilen von realen Anwendungsprogrammen herausdestilliert oder als synthetische Benchmarkprogramme eigens zur Leistungsmessung konstruiert. Heute werden vor allem Whetstone und Linpack (für Numerik-Programmierung) sowie Dhrystone (für System-Programmierung) eingesetzt [2]. Wenn auch synthetische Benchmark-Programme den Vorteil haben, daß sich ihre Eigenschaften wie die Prozentzahlen für die verschiedenen Statement-Arten und Datentypen beobachteten Programmprofilen gut anpassen lassen, haben sie doch zwei wesentliche Nachteile:

• Bei der Kürze der Programme fällt es Compiler-Autoren verhältnismäßig leicht, die Codeerzeugung und die Auswahl der Optimierungen auf diese Benchmarks abzustimmen; einzelne Elemente des Benchmarkprogramms können dann bei gezielt ausgewählten Codeoptimierungen die Laufzeit überproportional beeinflussen.
• Da die Programme verhältnismäßig kurz sind (Whetstone: meist unter 256 Byte pro Modul; Linpack/saxpy: 240 Byte; Dhrystone: ca. 1000 Byte) (Codelänge-Angaben für die Meßschleifen oder (bei Linpack) für das die Ausführungszeit dominierende Unterprogramm „saxpy", compiliert für VAX 11 mit Compilern von Berkeley UNIX), werden sie fast vollständig aus dem Cache heraus ausgeführt, das Speichersystem wird - außer bei Linpack für den Datenbereich - nicht realistisch getestet.

Aus diesem Grund hat sich SPEC zur Aufgabe gemacht, große Anwendungsprogramme zu sammeln und in normierter Form als Benchmark-Suite zur Verfügung zu stellen. Dies ist ein nichttriviales Unternehmen, da viele Programme, die vorher neben den kurzen Benchmarks für Leistungsmessungen verwendet wurden (z.B. nroff, yacc), eine UNIX-Lizenz erfordern und daher nicht frei weitergegeben werden können.

Die erste SPEC-Suite wurde im Herbst 1989 freigegeben, sie umfaßt 10 Programme mit zusammen etwa 150000 Zeilen Quellcode. Vier der Programme sind in C geschrieben, sechs in FORTRAN. Auch die Charakteristiken der Programme sind unterschiedlich; bei manchen (z.B. „matrix 300") hat der Code hohe Lokalität, bei anderen durchläuft der Befehlsstrom viele Teile des Programms relativ gleichmäßig. Die Programme wurden vom „Steering Committee" von SPEC aus über 50 Vorschlägen ausgewählt. Sie machen zwar einige Betriebssystem-Aufrufe (die Programme sind unter UNIX ablauffähig, wurden jedoch auch mit VMS gemessen), sind aber so CPU-intensiv, daß die Laufzeit für die Betriebssystem-Funktionen vernachlässigt ist.

SPEC selbst nimmt keine Messungen vor, Interessenten können die Benchmarks von SPEC gegen eine Schutzgebühr von 450.- $ auf Magnetband beziehen. Die Mitgliedsfirmen von SPEC können ihre Ergebnisse im SPEC-Newsletter veröffentlichen, wobei alle Daten (benutzte Hardware-Konfiguration, benutzte Compiler usw.) vollständig dokumentiert werden müssen. Die Gefahr einer geschönten Darstellung glaubt man dadurch ausgeschlossen zu haben, daß die SPEC-Benchmarks öffentlich zugänglich und damit alle Messungen jederzeit nachvollziehbar sind; die Veröffentlichung von falschen Daten würde langfristig dem betreffenden Hersteller mehr schaden als nutzen.

Eine kurze Charakterisierung der SPEC-Benchmarks wird in Tabelle 1 gegeben. Eine etwas ausführlichere Erörterung findet sich in [3], ein Auszug daraus (Beschreibung der SPEC-Benchmarks) in [4].

Als Maß für die Leistung eines Systems wird für jedes der 10 Programme die „SPEC-Ratio" berechnet, das Verhältnis der Laufzeiten einer Referenzmaschine und des Systems. Als Referenzmaschine wurde die VAX 11/780 mit den VMS-Compilern von DEC gewählt. Eine zusammenfassende Charakterisierung, die „SPECmark", ist definiert als das geometrische Mittel der (zur Zeit) 10 einzelnen „SPECRatios". SPEC war sich darüber im klaren, daß eine solche zusammenfassende Zahl ähnlich der MIPS-Zahl von Vertriebsabteilungen und der Handelspresse gebildet werden würde, und hat deshalb selbst diesen Mittelwert definiert. SPEC rät aber dringen dazu, nicht nur diesen zusammenfassenden Wert, sondern alle 10 Werte zu betrachten, und verpflichtet die teilnehmenden Firmen zu einer Darstellung der Ergebnisse, die alle Rohdaten und alle Relativ-Werte enthält. Der potentielle Kunde soll dann entscheiden, an welchen Werten er sich orientiert, ausgehend von einem Vergleich seines Programmprofils mit den einzelnen SPEC-Benchmarks. Abbildung 1 gibt ein Beispiel für die graphische Darstellung von SPEC-Resultaten; die vollständige Darstellung umfaßt zusätzlich alle Rohdaten und die verwendete Systemkonfiguration.

Abb. 1. Beispiel für SPEC-Ergebnisse: MIPS RC3260 (Messung 5/1990)

Seit Herbst 1989 werden laufend Ergebnisse für die SPEC-Benchmarks veröffentlicht. Unter den ersten gemessenen Systemen waren vor allem Workstations und Mikroprozessor-Systeme mit RISC-Prozessoren, inzwischen sind weitere Systeme dazugekommen. Dabei zeigen sich einige Tendenzen, die allgemeine Gültigkeit zu haben scheinen:

• Gegenüber der Referenzmaschine VAX 11/780 - die ja inzwischen schon recht alt ist - haben die neueren RISC-Prozessoren, wie erwartet, eine erhebliche Leistungssteigerung gebracht; dabei wurde die Integer-Leistung in höherem Maße verbessert als die Floating-Point-Leistung.
• Vergleicht man die von den Herstellern angegebenen MIPS-Zahlen mit dem Durchschnittswert der SPEC-Integer-Benchmarks, so sieht man, daß fast alle Hersteller mit der von ihnen angegebenen MIPS-Zahl (die von der Handelspresse meist als Integer-Leistungsverhältnis zur VAX 11/780 aufgefaßt wird) die eigenen Prozessoren in einem zu guten Licht erscheinen lassen, wobei allerdings erhebliche Unterschiede zwischen den einzelnen Herstellern und Produktlinien bestehen.
• Die zehn Einzelwerte streuen teils stärker, teils weniger stark um den Mittelwert, die SPECmark; dabei gibt es im allgemeinen beim LISP-Interpreter („li") und bei manchen Floating-Point-Benchmarks die größten Schwankungen.
• „Superskalare" Prozessoren, die durch parallele Funktionseinheiten mehr als einen Befehl pro Zyklus anstoßen können, realisieren ihren Geschwindigkeitsvorteil überwiegend bei Floating-Point-Benchmarks, und zwar bei denen, die vektorisierbaren Code enthalten. Offenbar läßt sich die Parallelarbeit - jedenfalls bei den gegenwärtigen Prozessor-Designs, wo es vor allem um Parallelarbeit zwischen Integer- und Floating-Point-Einheit geht - im wesentlichen nur bei Programmen, die eine sehr reguläre Code-Struktur haben, in signifikantem Maß nutzen; dann aber trägt sie zu einer erheblichen Leistungssteigerung bei.

Trotz der kurzen Zeit seit Beginn der Arbeit von SPEC haben sich die Benchmarks als ein nützliches Mittel zum Leistungsvergleich von Computersystemen vor allem im Workstation-Bereich erwiesen; sie sind unbestreitbar ein Fortschritt im Gebiet Benchmarking. Trotzdem kann es auf bei ihnen Probleme geben:

• Die Benchmark-Programme müssen zu einem frühen Zeitpunkt „eingefroren" werden, damit alle mit demselben Programm arbeiten. Vor allem manche FORTRAN-Benchmarks können aus Code bestehen, der schon recht alt ist („dusty deck") und neuere Erkenntnisse des Software Engineering noch nicht berücksichtigt (z.B. Vermeiden der früher relativ „teuren" Prozeduraufrufe, Benutzung von globalen statt lokalen Variablen); „docuc" ist hierfür ein Beispiel. Damit sind sie zwar oft für die in Rechenzentren derzeit ablaufenden Programme repräsentativ, es wäre aber bedauerlich, wenn Rechnerarchitekten sich bei ihren Optimierungs-Überlegungen auf dem Weg über die SPEC-Benchmarks von veralteten Programmier-Praktiken leiten ließen.
• Auch für einzelne der SPEC-Benchmarks kann es Compiler-Optimierungen geben, die sie besonders beschleunigen; und bei der Größe der Programme sind solche Benchmark-bezogenen Optimierungen wesentlich schwerer zu entdecken als bei den kurzen synthetischen Benchmarks. Dies ist nur dann unproblematisch, wenn auch „normale" Programme von diesen Optimierungen profitieren.
• In der Handelspresse zeigt sich trotz der guten Absichten von SPEC eine bedauerliche Tendenz, sich nur auf den Mittelwert, die SPECmark, zu konzentrieren. Dann wird, wie das obige Beispiel von der besonderen Eignung superskalarer Prozessoren für vektorisierbaren Code zeigt, die Auswahl der Benchmarks besonders wichtig; eine „geschickte" Auswahl kann Prozessoren in der Durchschnittswertung besser oder schlechter erscheinen lassen.

Die beim ersten Release in der SPEC-Suite enthaltenen Benchmarks decken nur den Bereich der CPU-intensiven Programmierung ab; man hat sich für den Start der SPEC-Aktivitäten auf das beschränkt, was relativ schnell machbar war. Release 2.0 wird neben weiteren CPU-Benchmarks auch I/O-intensive Programme enthalten. SPEC plant, weitere Benchmarks z.B. für Graphik-Anwendungen und für Multiprozessor-Systeme zu sammeln und zu veröffentlichen; außerdem ist geplant, die Benchmark-Sammlung auch auf weitere Programmiersprachen (COBOL, Ada) zu erweitern.

Adresse von SPEC:
SPEC-System Performance Evaluation Cooperative
(Kim Shanley, Secretary)
c/o Waterside Associates
39150 Paseo Padre Pkwy, Suite 350,
Premont, CA 94538, USA

Telefon: +1-415-792-2901; Fax: +1-415-792-4748
shanley@cup.portal.com

                   Artikelanfang   Seitenanfang

Literatur

1. Serlin, O.: MIPS, Dhrystones and Other Tales, Datamation 32, 112-118 (1988)
2. Weicker, R.P.: An Overview of Common Benchmarks. IEEE Comput. (im Druck)
3. Uniejewski, J.: Characterizing System Performance Using Application Level Benchmarks. Proc. BUSCON Conf., Malborough (Mass.), Sept. 1989, p. 159-167
4. SPEC Benchmarks Suite Release 1.0. SPEC Newslett. 2 (3), 3-4 (1990)

                   Artikelanfang   Seitenanfang

Autor & Copyright
R. Weicker (München)

© 1990 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang   Seitenanfang

Bioinformatik

• Kurzinfo
• Erläuterung
• Literatur
• Autor & Copyright

Kurzinfo Die Bioinformatik tangiert einerseits die Molekularbiologie, die Biochemie und die Genetik, andererseits die Theoretische und Praktische Informatik und die Computerlinguistik. Sie verfügt über einen homogenen und breiten Bestand an offenen Problemen. Sie gewinnt immer mehr an Bedeutung in Biologie und Genetik und wird schon industriell eingesetzt.

Erläuterung

Ziele der Bioinformatik

Die Proteine sind komplexe Moleküle, die Bausteine aller Lebensformen sind. Die Vielfalt an Proteinen ist gewaltig: Zum Beispiel kommen im menschlichen Körper über eine Million von verschiedenen Proteinen vor. Proteine setzen sich aus Aminosäuren in einer Weise zusammen, die in der DNA („deoxyribose nucleic acid" oder Desoxyribonukleinsäure) kodiert ist. Die DNA ist ein lineares Polymer, das aus 4 Nukleotiden aufgebaut ist. Eine Teilsequenz aus 3 Nukleotiden heißt Kodon. Jede der 20 Aminosäuren wird durch 1 bis 6 der 4³ = 64 Kodons kodiert, die meisten in mehrfacher Weise. Ein Ziel der Sequenzanalyse ist es, die Bereiche der DNA zu finden, die ein Protein kodieren. Dies ist sehr komplex: Es gibt viele nichtkodierende Bereiche; die Anfänge von kodierenden Bereichen und nichtkodierenden Bereichen sind schwierig zu erkennen; die kodierenden Bereiche sind nicht notwendigerweise verbunden. Zur Sequenzanalyse werden derzeit Informatikmethoden mit biochemischen Laboruntersuchungen kombiniert.

Die DNA-Analyse und die Verarbeitung natürlicher Sprachen haben vieles gemeinsam: „Kodierungen" werden aus Sequenzen erkannt; riesige Mengen von empirisch gewonnen Daten stehen zur Verfügung; Gesetzmäßigkeiten sind erkennbar, die bisher nur teilweise verstanden wurden; die systematische Erfassung von Ähnlichkeiten ist notwendig; die Grenze zwischen wohlgeformten und nichtwohlgeformten Zeichenfolgen ist fließend. In beiden Bereichen werden stochastische Methoden wie stochastische Grammatiken und Hidden-Markov-Modelle eingesetzt.

Die Vorhersage der Proteinstruktur ist ein Hauptziel der Biowissenschaften, weil die Funktion eines Proteins von seiner 3dimensionalen Gestalt abhängt. Ihre vollständige Lösung käme in Medizin und Pharmazie einer wissenschaftlichen und wirtschaftlichen Revolution gleich. Um schwierige Laboruntersuchungen zu vermeiden, werden Informatikmethoden zur Proteinfaltung eingesetzt, die die Struktur eines Proteins aus seiner Aminosäuresequenz ermitteln. Man unterscheidet die Primär-, Sekundär-, Tertiär- und Quartär- (oder Quaternär-) Strukturen eines Proteins. Die Primärstruktur ist die Aminosäuresequenz. Die Sekundärstruktur ist eine Abstraktion der 3dimensionalen Gestalt in Form von lokalen Faltungsmustern namens <alpha>-Helix, <beta>-Faltblatt und Turn. Die Tertiärstruktur ist die 3dimensionale Gestalt von Proteinuntereinheiten. Die Quartärstruktur gibt wieder, wie sich die verschiedenen Untereinheiten eines Proteins räumlich zusammenlagern. Bisher sind die Tertiärstrukturen von nur ca. 9.000 Sequenzen bekannt. Die homologiebasierte Vorhersage der Tertiärstruktur beruht auf einem Vergleich der Sequenz, deren Struktur ermittelt werden soll, mit Sequenzen, deren Tertiärstrukturen schon bekannt sind. Bei der Ab-Initio-Strukturvorhersage werden Tertiärstrukturen mit minimaler freier Energie durch globale Optimierungsmethoden ermittelt. Die Frage ob und wie ein Protein mit anderen Molekülen einen stabilen Komplex bilden kann, heißt Protein-Docking-Problem. Verfahren zum 1:1-Docking einzelner Proteinpaare liefern eine relative Positionierung der Moleküle zueinander.

Beim 1:n-Docking werden in einer Moleküldatenbank Docking-Partner für ein gegebenes Protein gesucht. Zum 1:n-Docking sowie zur homologiebasierten Strukturvorhersage werden Verfahren der Molekulardynamik, diskrete Techniken, genetische Algorithmen, geometrische Algorithmen sowie DataMining- und Knowledge-discovery-Methoden eingesetzt.

Derzeit gibt es mehr als hundert verschiedene Datenbanken in der Molekularbiologie: u.a. DDBJ, EMBL, GenBank, PIR und SwissProt. Viele dieser Datenbanken sind sehr groß. GenBank enthält z. B. ca. 4 x 10**6 Nukleotidsequenzen, die insgesamt aus ca. 3 x 10**12 Vorkommen von Nukleotiden bestehen. Den Biodatenbanken liegt kein einheitliches Schema zu Grunde. Die Verknüpfung heterogener Biodatenbanken und die Schemaintegration für Biodatenbanken sind weitgehend noch ungelöste Probleme von großer wirtschaftlicher Bedeutung.

Die Evolution verändert mit der Zeit die in der DNA kodierten Proteine. Es ist möglich durch computergestütze Sequenzanalysen und Klassifizierung diese Veränderungen und daraus die Stammbäume, phylogenetische Bäume genannt, von verwandten Spezies zu ermitteln. Der Ansatz wird u.a. in der evolutionären Paläontologie eingesetzt.

In letzter Zeit gewinnt die computergestützte Ermittlung von metabolischen und regulatorischen Pfaden an Wichtigkeit. Ein metabolischer Pfad ist eine abstrakte Darstellung eines Stoffwechselprozesses, der die daran beteiligten Proteine und Moleküle auflistet. Ein regulatorischer Pfad stellt die Informationsflüsse in einem Zelltyp dar, deren Mißverhalten die Grundlage für viele Krankheiten – wie etwa Krebs – bildet. Um die Ähnlichkeit von metabolischen bzw. regulatorischen Pfaden in unterschiedlichen Organismen zu untersuchen, werden Methoden der Mustererkennung, der Ähnlichkeitssuche in Datenbanken und der Sequenzanalyse eingesetzt.

Gene sind DNA-Bereiche, die Proteine kodieren und dadurch Erbeigenschaften bestimmen. Ein Gen kann in Zellen eines bestimmten Typs „exprimiert", d. h. zur Proteinentwicklung „abgelesen", werden. Man spricht von Genexpression. Mit einem einzelnen DNA-Chip können die Konzentrationen oder Expressionsniveaus von tausenden bis hunderttausenden Genen gemessen werden, die in einem bestimmten Zelltyp exprimiert werden. In differentiellen Displays lassen sich die Unterschiede zwischen den Expressionsniveaus in gesunden und kranken Zellen desselben Zelltyps feststellen. Die sehr umfangreichen Daten, die in dieser Weise erhalten werden, sind der Ausgangspunkt für neue Ansätze zur Diagnose und Therapie, die Informatikmethoden und biochemischen Laboruntersuchungen kombinieren.

Etwas abseits der Bioinformatik, jedoch in bezug dazu ist die Grundlagenforschung zum Thema Biocomputing. Damit wird der Einsatz von molekularbiologischen Methoden wie Gelelektrophorese und Polymerasekettenreaktion zur Berechnung komplexer mathematischer Probleme wie etwa kryptographischer Entschlüsselung bezeichnet. Die Durchsetzungschancen des Biocomputings sind noch völlig offen.

Die Bioinformatik in der Industrie

Unter den bereits etablierten industriellen Anwendungen der Bioinformatik finden sich die Arzneimittelentwicklung, die Gentherapie, die Erkennung von genetischen Risikofaktoren wie die Geisteskrankheit Fragile-X-Syndrom und die Huntingtons-Krankheit, die nicht unumstrittene Genveränderung in der Agrar- und Züchtungswirtschaft und die biometrischen Unterschriften. Die für die pharmazeutische Industrie hochrelevante Genexpression trägt viel zum gegenwärtigen industriellen Interesse an der Bioinformatik bei. Führende Konzerne wie BASF, Hoechst, Hoffmann-La Roche (mit Boehringer Mannheim), Merck, Millenium Pharmaceutical, Rhône Poulenc und SmithKline Beecham und Unternehmen wie Affymetrix, Artemis, Incyte und LION AG betreiben in erheblichem Umfang Forschung und Entwicklung in der Bioinformatik. Unternehmen wie Medigenomix, GPC, Epidaurus und Switch Biotech, die in der Genomanalytik tätig sind, nutzen die Bioinformatik intensiv.

Methoden und Perspektiven der Bioinformatik

Die Bioinformatik setzt Methoden aus verschiedenen Gebieten der Informatik ein: u.a. Kombinatorische Optimierung, Integer Linear Programming, Constraint-Programmierung, Algorithmik und Formale Sprachen, Genetische Algorithmen, Geometrische Algorithmen, Stochastische Algorithmen, Neuronale Netze, Mustererkennung, Maschinelles Lernen, Inductive Logic Programming, Knowledge Discovery und Data Mining, Computerlinguistik. Wegen einerseits der gewaltigen Datenmengen, die behandelt werden müssen, und andererseits den allgegenwärtigen Ausnahmen zu erkennbaren Gesetzmäßigkeiten bieten die Biowissenschaften ein herausragendes Anwendungsfeld für die moderne Informatik. Die potentielle Einsatzmöglichkeiten der Informatik in Biowissenschaften gehen weit über ihre derzeitigen Anwendungen hinaus. Die Rolle, die die Informatik bei den Biowissenschaften nun spielt, ähnelt der Rolle der Mathematik in der Physik: Erst der Einsatz von Informatikmethoden ermöglicht es, in Biowissenschaften Modelle zu bilden und mit ihnen zu rechnen statt im Reagenzglas zu experimentieren.

Der Wichtigkeit der Bioinformatik sowohl für die Biowissenschaften als auch für die Informatik wird derzeit in der Lehre noch nicht ausreichend Rechnung getragen. Hochschulabsolventen, die eine fundierte Informatik- und Biologieausbildung vorweisen können, sind derzeit „Mangelware". Nur an wenigen Universitäten werden Studiengänge in Bioinformatik angeboten oder eingerichtet.

In der Bioindustrie wird die Bioinformatik als Schlüsseltechnologie angesehen. Nicht zuletzt junge Biotechnologieunternehmen wie diejenigen der „BioTech-Regionen" (www.bioregio.com) sind auf eine starke universitäre Bioinformatik angewiesen.

Danksagung

Die Autoren danken den anonymen Gutachtern für ihre konstruktiven Hinweise.

                   Artikelanfang   Seitenanfang

Literatur

1. Baldi, P., Brunak, S.: Bioinformatics – The machine learning approach. Harvard: MIT Press 1998
2. Baxevanis, A. D., Ouellette, F.: Bioinformatics – A practical guide to the analysis of genes and proteins. New York: Wiley 1998
3. Durbin, R. et al. Biological sequence analysis. Cambridge: Cambridge Univ Press 1998
4. Giegerich, R. et al.: Empfehlung zur Einrichtung von Studiengängen im Fach Bioinformatik, Fachgruppe 4.0.2 der GI, 1997 –
   http://wwwiti.cs.uni-magdeburg.de/iti_bm/fb4/gi/bioinfocurric.ps
5. Gusfield, G.: Algorithms on strings, trees, and sequences: Computer science and computational biology. Cambridge Univ Press 1997
6. Hunter, L. (ed.): Artificial intelligence and molecular biology. Hrvard: MIT Press 1993
7. Lengauer, T. et al.: Bioinformatik – Diagnose von Krankheiten und Entwicklung von Wirkstoffen mit Hilfe des Computers, Software, Spektrum-der-Wissenschaft-Dossier 2, 38–43 (1999)
8. Searls, D. B.: The computational linguistics of biological sequences in . Hunter, L. ed. Artificial intelligence and molecular biology. Harvard: MIT Press 1993
9. Suhai, S. (ed.): Theoretical and computational methods in genome research. New York London: Plenum Press 1997
10. Waterman, M.: Introduction to computational biology. London: Chapmann & Hall 1995

                   Artikelanfang   Seitenanfang

Autor & Copyright

Rolf Backofen¹, François Bry¹, Peter Clote¹, Hans-Peter Kriegel¹, Thomas Seidl¹, Klaus Schulz²

¹ Institut für Informatik der Ludwig-Maximilians-Universität München, Oettingenstr. 67 D-80538 München
² Centrum für Informations- und Sprachverarbeitung der Ludwig-Maximilians-Universität München, Oettingenstr. 67, D-80538 München

© 1999 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang   Seitenanfang

Datenbanken in der Bioinformatik

• Erläuterung
• Literatur
• Autor & Copyright

Erläuterung

Die Bioinformatik kann als Anwendung von Informatikmethoden zur Untersuchung von Problemen der Molekularbiologie definiert werden, die auf sehr großen Datenmengen beruhen und einer umfangreichen Datenanalyse bedürfen [2].Folglich spielen Datenbanken in der Bioinformatik eine zentrale Rolle.

Die Bioinformatikdatenbanken haben interessante Merkmale, die in herkömmlichen Datenbanken selten vorkommen. Insbesondere zeigen Datenbanken mit unterschiedlichen Molekularbiologiedaten einheitliche Merkmale.

Fragestellungen, Daten und Verwendung von Datenbanken

Sequenzdatenbanken zur DNS-Analyse und Sequenzierung

Proteine, die "Bausteine des Lebens ", sind aus Aminosäuren nach einem Bauplan zusammengesetzt, der in der DNS kodiert ist. Die DNS ist ein lineares Polymer, Sequenz genannt, das aus vier Nukleinsäuren aufgebaut ist. Innerhalb der DNS gibt es kodierende sowie nichtkodierende Abschnitte, deren Grenzen schwierig zu erkennen sind. Ziel der Sequenzierung ist es, die kodierenden sowie die nichtkodierenden Bereiche in der DNS-Sequenz eines Organismus zu ermitteln. DNS-Analyse-Methoden werden eingesetzt, um kodierende sowie weitere Bereiche zu erkennen. Die Daten werden in (meist sehr großen)Sequenzdatenbanken verwaltet: GenBank [4] enthält z.B.ca.2 * 10 ** 7 Nukleotidsequenzen und referenziert ca.2 * 10 ** 10 Vorkommen von Nukleotiden. Das Wachstum der meisten Sequenzdatenbanken ist exponentiell.

Proteinsequenz- und Proteinstrukturdatenbanken zur Strukturvorhersage

Die Funktion eines Proteins hängt von seiner 3D-Struktur ab, sodass die Vorhersage der Struktur von Proteinmolekülen aus ihrer Sequenz, die sog. Proteinfaltung, ein Hauptziel der Biologie ist. Bioinformatikmethoden werden eingesetzt, um Annäherungen an die tatsächliche Struktur von Proteinen zu berechnen und damit Laboruntersuchungen einzuschränken. Homologiebasierte Ansätze vergleichen dabei die Aminosäuresequenzen bereits bekannter Proteine mit der Sequenz des unbekannten Proteins. Dafür werden Proteinsequenz- und Proteinstrukturdatenbanken aufgebaut und Ähnlichkeitsanfragen an solche Datenbanken gestellt.

Biochemische Pfade

Ein biochemischer Pfad ist eine abstrakte Modellierung von aufeinander folgenden chemischen Reaktionen in einer Zelle. Besondere Beachtung finden metabolische Pfade (Reaktionswege im Stoffwechsel)und regulatorische Pfade (Kontrollmechanismen in der Genexpression). Zum Auffinden biochemischer Pfade werden unter anderem Sequenzdatenbanken verwendet. Die so gewonnenen Daten werden in speziellen Datenbanken verwaltet.

Sequenzdatenbanken zur Ermittlung phylogenetischer Bäume

Die Evolution verändert über die Jahre hinweg die Kodierung der Proteine in der DNS. Modelle dieser Veränderung werden auf die Daten von Sequenzdatenbanken angewandt, um die Stammbäume, phylogenetische Bäume genannt, einzelner Organismen zu ermitteln.

Genexpressionanalyse

Ein Gen wird meist als DNS-Abschnitt definiert, der ein Protein kodiert. Zellen besitzen Mechanismen für die sog. Genexpression, d.h.,um ein spezielles Gen in der DNS zu lesen und daraus das kodierte Protein zu synthetisieren. Mit sog. DNS-Chips kann das Expressionsniveau (intuitiv: die "Konzentration ") mehrerer tausend Gene gemessen werden, die eine Zelle zu einem Zeitpunkt exprimiert. Datenbanktechniken zum Data-Mining (z.B. Clustering-Methoden) werden dazu benutzt, Gene mit ähnlichen Expressionsmustern in Gruppen zusammen zu fassen.

Inhaltliche Unterschiede

Die Bioinformatikdatenbanken sind sehr unterschiedlich bezüglich ihres Inhaltes. Manche Datenbanken speichern die Daten aus einem einzigen, möglicherweise schon abgeschlossenen Forschungsprojekt. Andere Datenbanken sind das Ergebnis einer weltweiten und andauernden Zusammenarbeit zwischen Forschungsteams. Manche Datenbanken beinhalten Daten über einen einzigen Organismus, andere über alle Vorkommen eines Proteins in allen möglichen Organismen. In manche Datenbanken werden neue Daten erst nach Korrektheit- und Konsistenzüberprüfungen aufgenommen. In anderen Datenbanken finden solche Überprüfungen nicht statt. Dennoch haben die Bioinformatikdatenbanken erstaunlich viele Gemeinsamkeiten, was Datenmodellierung und -management angeht.(Einen Überblick über die verbreitesten Datenbanken der Bioinformatik gibt der Computational Biology Database Digest [4].)

Datenmodellierung und -management

Bemerkenswert ist, dass Datenmodellierung und -management kaum von der Art der Molekularbiologiedaten abhängen.

Datenmodelle

Bioinformatikdatenbanken verwenden vier Formen der Datenmodellierung:

• ASCII-Texte ("Flat-Files");
• Datenmodelle, die für herkömmliche Datenbanken entwickelt wurden;
• das Object-Protocol-Modell (OPM);
• das ACEDB-Datenmodell.

Flat-Files. Die Datensätze aus Bioinformatikdatenbanken, die als Sammlungen von Flat-Files implementiert sind, sind entweder unstrukturiert (Abb.1) oder mittels textueller Bezeichner (line type) stukturiert (Abb.2). Es gibt keinen einheitlichen Satz an solchen Bezeichnern, der in den meisten (oder vielen) Bioinformatikdatenbanken verwendet wird. Sowohl die Kodierung von Begriffen mit "line types" wie auch die Begriffe selbst können sich zwischen Bioinformatikdatenbanken erheblich unterscheiden.

Sehr viele Bioinformatikdatenbanken sind immer noch als Sammlungen von Flat-Files implementiert: ca.40% der von uns untersuchten Bioinformatikdatenbanken sind Flat-File-Sammlungen [4].Zudem sind Flat-Files der De-facto-Standard zum Datenaustausch in der Bioinformatik.

Relationale und Objektdatenmodelle. Etwa 35% der untersuchten Bioinformatikdatenbanken werden von einem herkömmlichen (relationalen, objektorientierten oder objektrelationalen) Datenbanksystem verwaltet [4].Ihre Daten werden folglich unter Verwendung des relationalen oder des Objektdatenmodells repräsentiert. Mit dem Objektdatenmodell werden die (meist weitgehend strukturierten) Molekularbiologiedaten gut repräsentiert. Mit dem relationalen Modell werden die Daten meist unübersichtlich und wenig intuitiv repräsentiert.

Object-Protocol-Modell (OPM). OPM [6] wurde zur Repräsentation von wissenschaftlichen (Labor-)Experimenten entwickelt. Es eignet sich besonders gut zur Repräsentation der zeitlichen Bedingungen und des Datenflusses zwischen Teilexperimenten. Folglich eignet sich OPM gut zur Repräsentation von Phänotypdaten, d.h. Daten über die Dynamik von biologischen Prozessen. OPM weist viele Merkmale von SDM [7] und dem Datenmodell von O ₂ [3] auf.

ACEDB-Datenmodell. ACEDB (mit großem "E";[1]) ist ein Datenbankmanagementsystem mit einem eigenen, speziellen Datenmodell, das ursprünglich für die Bioinformatikdatenbank ACeDB (mit kleinem "e") entwickelt wurde (ACeDB ist das Kürzel von "A C.elegans Database"). ACEDB findet in den Bioinformatikdatenbanken breite Anwendung zur Repräsentation von genetischen Daten. Grund dafür ist die Flexibilität des Datenmodells, das viele Aspekte des semistrukturierten Ansatzes zur Datenmodellierung [5] besitzt

Datenbankmanagement

Viele (über 30% der in [4] untersuchten) Bioinformatikdatenbanken werden mit einem relationalen Datenbankmanagementsystem (DBMS) verwaltet, obwohl das relationale Datenmodell zur Repräsentation von molekularbiologischen Daten wenig geeignet ist. Nur wenige (ca.9% der in [4] untersuchten) Bioinformatikdatenbanken werden mit einem objektorientierten DBMS verwaltet, obwohl die objektorientierte Modellierung von molekularbiologischen Daten sehr passend ist. Diese Lage ist sicherlich auch auf die rasche Entwicklung der Bioinformatik, auf das extrem schnelle Wachstum der Bioinformatikdatenbanken sowie auf den beschränkten Erfolg der objektorientierten DBMS zurückzuführen. Das speziell für die Bioinformatik entwickelte DBMS ACEDB ([4]) wird zur Verwaltung von noch wenigeren (ca.4% der in [4] untersuchten) Bioinformatikdatenbanken eingesetzt.

Querverweise

Oft verweisen Datensätze von Bioinformatikdatenbanken auf Beschreibungen der Experimente, durch die die Daten gewonnen wurden, und/oder auf ähnliche Daten in derselben Datenbank oder in anderen Bioinformatikdatenbanken. Meist werden diese Verweise mittels (künstlicher) Primärschlüssel realisiert und als Hypertextlinks implementiert.

Die Hypertextverlinkung ist ein besonders auffälliges Merkmal der Bioinformatikdatenbanken.

Anfragen und Crawling

Die meisten Bioinformatikdatenbanken bieten (oft hierarchisch organisierte) Webformulare, womit Anfragen an die Datenbank gestellt werden können. Solche Schnittstellen sind leicht zu benutzen, ermöglichen aber meist nur begrenzte Anfragen.

Anfragesprachen im herkömmlichen Sinn werden selten zur Verfügung gestellt, u.a.weil ihre Verwendung Fachkenntnisse erfordert, über die nur wenige Benutzer von Bioinformatikdatenbanken verfügen. Zusätzlich stellen fast alle Bioinformatikdatenbanken ihre Daten in den unterschiedlichsten Formaten als Flat-Files zum Herunterladen zur Verfügung.

Das System SRS zur Integration von Bioinformatikdatenbanken bietet eine originelle Anfragesprache. Mit dieser Anfragesprache kann eine Navigation durch Datenbanken und Datensätze spezifiziert werden. Auffällig originell sind die Crawling-Konstrukte der SRS-Anfragesprache zur Verfolgung von Hypertextlinks. Interessanterweise bietet keine Anfragesprache für XML [5] solche Crawling-Konstrukte.

Datenanalyse und -integration

Auch bei der Datenanalyse gibt es überwiegend Gemeinsamkeiten zwischen den Bioinformatikdatenbanken, unabhängig von der Art der gespeicherten Daten. Viele Werkzeuge zur Datenanalyse sind zwar tendenziell eher einer gewissen Art von Daten zu zuordnen, dennoch werden sie oft auch für Daten anderer Art angeboten und benutzt.

Datenbanken, Datenanalyse und Data-Mining

Die meisten Bioinformatikdatenbanken stellen Bioinformatiksoftware für die Datenanalyse zur Verfügung. Diese Software sind entweder Implementierungen von verbreiteten Bioinformatikalgorithmen (z.B. dem Smith-Watermann-Algorithmus) oder Werkzeuge (z.B. BLAST), die auf bekannten und/oder weniger bekannten Algorithmen und Verfahren beruhen. Einige dieser Werkzeuge (z.B. 3Dee) beziehen sich auf Datenbanken, sodass die Unterscheidung zwischen einer Methode zur Datenanalyse, die eine bestimmte Datenbank verwendet, und einer Datenbank, die eine bestimmte Methode zur Datenanalyse anbietet, schwierig sein kann. Viele Bioinformatikdatenbanken bieten auch elementare Computerlinguistiksoftware zur Schlagwortsuche und Übersetzungen zwischen den geläufigsten Datenformaten von Bioinformatikdatenbanken.- Einen Überblick über die verbreitesten Methoden und Werkzeuge gibt der Database Digest [4].

Mit dem raschen und stetigen Wachstum der Bioinformatikdatenbanken sind Verfahren zum Knowledge-Discovery und Data-Mining unabdingbar geworden. Sie sind Gegenstand aktueller Forschung.

Datenintegration

Die Integration von Daten unterschiedlicher Art und/oder aus unterschiedlichen Bioinformatikdatenbanken ist ein akutes Problem. Es treten semantische Konflikte auf, z.B. werden grundlegende Begriffe wie "Gen" in verschiedenen Datenbanken unterschiedlich ausgelegt. Frühe Systeme zur Datenintegration in der Bioinformatik (wie Bio-Kleisli und SRS) berücksichtigen semantische Konflikte nicht. Neuere Ansätze (wie Tambis) versuchen semantische Konflikte meist mit Ontologien zu lösen.

Das Problem, dass Daten unterschiedlicher (insbesondere auch sehr schlechter) Qualität integriert werden, ist bisher von keinem Integrationsansatz zufrieden stellend behandelt worden.

                   Artikelanfang   Seitenanfang

Literatur

1. ACEDB Dokumentationssammlung:
   http://genome.cornell.edu/acedocs/
2. Backofen, R., Bry, F., Clote, P., Kriegel, H.-P., Seidl, T., Schulz, K.: Bioinformatik. Informatik Spektrum 22(9), 376-378 (1999).
3. Bancilhon, F., Delobel, C., Kanellakis, P.: Building an object-oriented database system: The story of O₂. San Francisco: Morgan Kaufmann 1992
4. Bry, F., Kröger, P.: A computational biology database digest: data, data analysis, and data management. Research Report PMS-FB-2002-8, Institut für Informatik, Universität München. http://www.pms.informatik.uni-muenchen.de/publikationen/ #PMS-FB-2002-8 wird erscheinen in: International Journal on Distributed and Parallel Data-bases, Kluwer Academic Press
5. Bry, F., Kraus, M., Olteanu, D., Schaffert, S.: Semistrukturierte Daten. Informatik Spek-trum 24(4), 230-233 (2001).
6. Chen, I.-M., Markowitz, V.: An overview of the object protocol model (OPM) and the OPM data management tools. Information Systems 20(5), 393-418 (1995)
7. Hammer, M., McLeod, D.: Database description with SDM: A semantic database model. ACM Transactions on Database Systems 6(3), 1981

Hinweis: Die URLs entsprechen dem Stand bei der Veröffentlichung des Artikels und werden nicht aktualisiert.

                   Artikelanfang   Seitenanfang

Autor & Copyright
François Bry · Peer Kröger
Institut für Informatik,
Ludwig-Maximilians-Universität München,
http://www.pms.informatik.uni-muenchen.de

© 2002 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang   Seitenanfang

Bytecode-Interpretierung

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Nicht nur Java und Smalltalk; auch viele andere Programmiersprachen wie Lisp, Prolog, ML und Pascal besitzen einen Bytecode-Interpretierer als Basis einer ihrer Implementierungen.

Bevor ein Programm das in einer höheren Programmiersprache geschrieben ist, auf einer konkreten Maschine ausgeführt werden kann, muß es in eine semantisch äquivalente Folge von Instruktionen der konkreten Maschine übersetzt werden. Da jede konkrete Maschine mit einem eigenen Instruktionssatz gesteuert wird, ist insbesondere die Codegenerierungsphase des Übersetzungsprozesses sehr maschinenabhängig und die Entwicklung eines portablen Übersetzers aufwendig.

Ein alternativer Ansatz zur portablen Implementierung einer Programmiersprache basiert auf einem Übersetzer, der ein Quellprogramm in eine Folge von Instruktionen einer virtuellen Maschine überträgt. Die Instruktionen der virtuellen Maschine werden Bytecodes genannt, wenn sie in 8 Bits kodiert sind. Zur Ausführung der Bytecodes emuliert ein Bytecode-Interpretierer die virtuelle Maschine. Die Emulation der virtuellen Maschine verlängert die Laufzeit von Programmen 2- bis 10fach. Der Bytecode-Ansatz bietet jedoch einige Vorteile, die den Nachteil der längeren Laufzeit aufwiegen:

• Programmgröße
  Der Instruktionssatz einer konkreten Maschine ist vom Hersteller als optimale Schnittstelle zwischen Software und Hardware vorgegeben. Der Instruktionssatz einer virtuellen Maschine kann dagegen frei entworfen und der Quellsprache angepaßt werden. Standard Operationen höherer Sprachen benötigen im Extremfall nur eine virtuelle Instruktion, anstelle mehrerer konkreter Instruktionen. Typischerweise existieren für die Lisp-Operationen car, cdr und cons sowie für den Zugriff auf Objektkomponenten in objektorientierten Sprachen spezielle Instruktionen. Die Folge ist sehr kompakter Objektcode, eine Anforderung mit hoher Priorität bei Anwendungen mit beschränktem Speicherplatz (z.B. Steuerungen) [12]. Zur genauen Bestimmung der Programmgröße muß die konstante Größe des Bytecode-Interpretierers allerdings mitgezählt werden.
   
• Codegenerierung
  Die Tatsache, daß für einen maschinenunabhängigen und der Quellsprache angepaßten Instruktionssatz Code erzeugt wird, vereinfacht und beschleunigt die Codegenerierungsphase des Übersetzungsprozesses [9]. Es ist nicht notwendig, Eigenheiten verschiedener Prozessoren zu berücksichtigen.
   
• Portabilität
  Die Unabhängigkeit des Instruktionssatzes einer virtuellen Maschine erleichtert auch die Portierung. In Bytecode übersetzte Programme sind auf jeder konkreten Maschine ablauffähig, auf der ein Bytecode-Interpretierer installiert ist. Der Portierungsaufwand beschränkt sich somit auf die einmalige Portierung des Bytecode-Interpretierers (in der Regel wenige Kilobyte [9]). Ist der Bytecode-Interpretierer zudem in einer weit verbreiteten Sprache wie C geschrieben, vereinfacht sich die Portierung noch einmal.
   
• Softwareentwicklung
  Durch die Emulation der virtuellen Maschine kann die Ausführung eines Programms vollständig kontrolliert werden. Der Zustand der virtuellen Maschine – bestimmt durch Register, Keller, Programmzeiger etc. – kann dynamisch analysiert und modifiziert werden. Für die Anbindung von Softwareentwicklungs-Werkzeugen zur komfortablen Fehlerkorrektur ist dies eine wichtige Voraussetzung. Da in Bytecode vorliegende Programme als Laufzeitdaten (nicht darstellbare Zeichenketten) repräsentiert sind, können weiterhin alternative Übersetzungstechniken wie Übersetzung zur Laufzeit und dynamisches Binden, unabhängig vom Betriebssystem und mit geringem Aufwand eingesetzt werden [3, 14].
   
• Sicherheit
  Der Sicherheitsaspekt spielt bei Programmen, die über Computernetze versendet werden, eine wichtige Rolle. Die Emulation der virtuellen Maschine stellt unter diesem Gesichtspunkt eine Sicherheitsebene dar, in der die Emulation von lokalen Ressourcen (Speicher Dateisystem, Drucker, etc.) einbezogen ist. Die Abbildung von virtueller nach realer Funktionalität kann kontrolliert und einem Programm unter Umständen der Zugriff auf bestimmte Ressourcen verwehrt werden.

Der Bytecode-Ansatz liegt bezüglich der Programmrepräsentation, sowie der damit verbundenen Vor- und Nachteile zwischen den Extremen direkte Interpretierung und Maschinencodeübersetzung. Im ersten Fall sind die Instruktionen der virtuellen Maschine die Standardoperationen der Quellsprache; bei der Übersetzung in Maschinencode fallen virtuelle und konkrete Maschine zusammen.

Interpretierer bieten Interaktivität und sind leicht zu implementieren. Im Vergleich zu Maschinencodeprogrammen ist die Laufzeit interpretierter Programme jedoch deutlich länger. Mit dem Bytecode-Ansatz werden Quellprogramme in eine Zwischenrepräsentation übersetzt, die effizienter interpretiert werden kann, da syntaktische und lexikale Analysen entfallen, und der Code in linearer Form vorliegt. Aufgrund der einfachen Codegenerierung können in einer interaktiven Schleife einzelne Ausdrücke in Bytecode übersetzt und sogleich ausgeführt werden. Trotz der schnelleren Interpretierung übersetzter Ausdrücke ist die Antwortzeit eines solchen inkrementellen Übersetzers länger als die eines Quellprogramm-Interpretierers da für jede Eingabe das Übersetzerprogramm gestartet wird. Inkrementelle Übersetzung in Bytecodes verbindet somit Interaktivität mit akzeptabler Geschwindigkeit.

Der einfachste Ansatz zur Implementierung eines Bytecode-Interpretierers verwendet eine Schleife, die mit Hilfe eines Programmzeigers den aktuellen Bytecode lädt, dekodiert und die entsprechende Instruktion anspricht. Diese Schritte müssen vor Aufführung jeder virtuellen Instruktion durchgeführt werden und sind maßgeblich für die längere Laufzeit von Interpretierern verantwortlich [2]. Bessere Laufzeiten werden erzielt wenn die Instruktionen der virtuellen Maschine als Adressen der entsprechenden Instruktionsroutinen (direkt oder indirekt) kodiert sind [1, 4].

Zusätzliche Beschleunigung kann mit spezialisierten Instruktionen erreicht werden. Beispielsweise empfiehlt es sich, aufgrund der relativen Häufigkeit der Addition mit 1, neben einer allgemeinen Additionsinstruktion auch eine Instruktion zur Inkrementierung bereitzustellen. Weiterhin kann mit Hilfe dynamischer Analysen eine Codekomprimierung um bis zu 75 % erreicht werden, indem häufig aufeinanderfolgende Instruktionen in einer Instruktion zusammengefaßt werden [8].

In einigen Systemen werden unter bestimmten Voraussetzungen in Bytecode vorliegende Programme zur Effizienzsteigerung weiter in Maschinencode übersetzt [3, 6]. Im Allgemeinen eignen sich Bytecodes allerdings nicht als universelle Zwischenrepräsentation. Wenn auch maschinenunabhängig, so ist die Repräsentation zu maschinennah, und sie reflektiert in der Regel die Semantik einer bestimmten Programmiersprache.

Die ersten Bytecode-Systeme wurden in den 70er Jahren für BCPL [15], Forth [12], SNOBOL4 [4, 5] und Pascal [13] geschrieben. Erwähnenswert sind auch die Bytecode-Implementierungen für Smalltalk [3, 10] und Java [6, 11].

Wie bereits angedeutet, erlaubt die Portabilität in Bytecode übersetzter Programme, diese innerhalb eines heterogenen Computernetzes zu verschicken. Solange die empfangende Maschine eine Implementierung der entsprechenden virtuellen Maschine in Form eines Bytecode-Interpretierers besitzt, kann das verschickte Programm dort ausgeführt werden. Die kompakte Bytecode-Repräsentation der Programme hilft, die Belastung des Netzes zu verringern und die Übertragungszeit gering zu halten.

Der Java-Instruktionssatz [6, 7] ist durch eine monomorphe Typisierung der Instruktionen ausgezeichnet. Aus den Typen der Argumente einer Instruktion kann eindeutig der resultierende Typ geschlossen werden; zudem müssen Kontrollpfade in gleichen Typen zusammenkommen. Die monomorphe Typisierung der Instruktionen und ein Protokoll zur Anbindung neuer Klassen erlauben, ein in Bytecodes vorliegendes Programm vor der Ausführung auf unerlaubte Datenkonvertierungen und illegale Zugriffe auf Objektkomponenten zu prüfen.

Zusammenfassend kann gesagt werden, daß Bytecode-Interpretierung eine einfache Technik zur Realisierung einer Programmiersprache darstellt. Im Gegensatz zu optimierenden Übersetzern die in der Regel Speicherplatz zugunsten von Geschwindigkeit opfern, ermöglicht der Bytecode-Ansatz – bei akzeptabler Geschwindigkeit – Portabilität, geringen Speicherbedarf sowie direkten Zugriff auf die Laufzeitumgebung (z.B. zur Realisierung von Sicherheitsanforderungen in heterogenen Computernetzen oder zur Anbindung von Softwareentwicklungs-Werkzeugen. Eine weiterführende Diskussion über Techniken zur Optimierung von Interpretierern findet sich bei Debaere et al. [2].

                   Artikelanfang  Seitenanfang

Literatur

1. Bell, J. R.: Threaded code. Communications of the ACM 16(6):370–373, 1973
2. Debaere, E. H.,Van Campenhout, J. M.: Interpretation and Instruction Path Coprocessing. The MIT Press. 1990
3. Deutsch, P., Schiffman, A. M.: Efficient implementation of the Smalltalk-80 system. In Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, pp 297–302, January 1984
4. Dewar, R. B. K.: Indirect threaded code. Communications of the ACM,18(6):330–331 1975
5. Dewar, R. B. K., McCann, A. P.: MACRO SPITBOL – A SNOBOL4 compiler. Software – Practice and Experience, 7:95–113, 197
6. Gosling, J.: Java intermediate bytecodes. ACM SIGPLAN Notices, 30(3):111–118, March 1995
7. Gosling, J., Joy, B., Steele, G.: The Java Language Specification. AddisonWesley, 1996
8. Hehner, E. C. R.: Computer design to minimize memory requirements. Computer, 9(8):65–70, 1976
9. Islint, P.: Interpretation techniques. Software – Practice and Experience. 11(9):963–973 September 1981
10. Krasner, G., editor: Smalltalk-80: Bits of History. Words of Advice. Addison-Wesley, Reading 1983
11. Lindholm, T., Yellin, F.: The Java Virtual Machine Specification. Addison-Wesley 1996
12. Moore, C. H.: Forth: A new way to program a computer. Astronomy and Astrophysics Supplement, (15):497–511, 1974
13. Nori, K. V., Ammann, U., Jensen, K., Nageli, H. H., Jacobi, C.: Pascal-P implemenation notes. In Barron, D. W., editor: Pascal – The Language and its Implementation, pp125–170. Wiley & Sons, Ltd. 1991
14. Notkin, D., Griswold, W. G.: Enhancement through extension: The extension interpreter. SIGPLAN Notices, 22(7):45–55, 1987
15. Richards, M.: The portability of the BCPL compiler. Software – Practice and Experience, 1:135–146, 1971

                   Artikelanfang  Seitenanfang

Autor & Copyright
Andreas Kind
School of Mathematical Sciences,
University of Bath,
Bath BA2, email: ak1@maths.bath.ac.uk
ak1@maths.bath.ac.uk

© 1997 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang