1. Vom Programm zur theoretischen Informatik und zur Rechnerarchitektur

Diese Vorlesung setzt voraus, dass in den Semestern 1+2 schon erste Kenntnisse in der Programmierung erworben wurden. Es ist also bekannt, was ein Programm ist, was eine Programmiersprache ist, was es heisst einen Sourcecode zu kompilieren, so dass ein maschinenlesbares Programm entsteht.

Es wird auch vorausgesetzt, dass bekannt ist, dass und wie man mit einem Programm einen Algorithmus realisieren kann. Ein Algorithmus ist ein effektives Verfahren, bei dem zu jedem Zeitpunkt klar ist, welcher Schritt als nächster auszuführen ist und der nach endlich vielen Schritten stoppen kann. Eine theoretische Behandlung effektiver Verfahren erfolgt in der Parallelveranstaltung theoretische Informatik.

Für die Lehrveranstaltung Rechnerarchitektur ist es nun wichtig, dass Algorithmen durch Automaten realisiert werden können, denen in der Realität Mikrocomputer entsprechen. Die theoretischen Konzepe von Automaten wie z.B. die Turingmaschine oder die Registermaschine werden ebenfalls in der theoretischen Informatik behandelt. In der Vorlesung Rechnerarchitektur interessieren wir uns für die technische Realisierung der theoretischen Konzepte effektiver Verfahren. Dabei wird ein besonderes Gewicht auf die Tatsache gelegt werden, dass in den letzten 10 Jahren die Verbindung von Hardware und Software sowohl immer enger wie auch immer komplexer wird; 'reine Hardware' gibt es fast garnicht mehr.

START

2. Vom effektiven Verfahren zum Automaten

Zum Einstieg in die Welt der realen Rechnerarchitekturen betrachten wir zunächst den Vorgang, wenn ein menschlicher Akteur als Zeichenbenutzer den endlichen Text eines Algorithmus liest und in die entsprechenden Handlungen umsetzt.

Ein Programm, das einen Algorithmus realisiert, ist für einen menschlichen Akteur normalerweise ein endlicher Text auf einem Blatt Papier. Der Text ist nicht beliebig, sondern besteht aus Zeichen, die einem zuvor festgelegten endlichen Zeichenvorrat ('Alphabet') entnommen werden. Ferner ist die Anordnung solcher Zeichen nicht willkürlich, sondern gehorcht bestimmten syntaktischen Regeln, die zusammen eine Grammatik ('Syntax') bilden. Der Akteuer ist in diesem Fall ein Zeichenbenutzer, der in der Lage ist, den Zeichenketten des Textes bestimmte Bedeutungen zuzuordnen. Im allgemeinen kann man zwei Arten von Bedeutungsinhalten unterscheiden: Objekte und Handlungen mit Objekten. Die Bedeutungen müssen so klar sein, dass der Zeichenbenutzer zu jedem Zeitpunkt genau weiss, welche Objekte durch welche Handlungen als nächstes wie zu verändern sind. Ohne Beschränkung der Allgemeinheit nehmen wir hier an, dass die Handlungen sich auf das Löschen oder Schreiben von Zeichen auf dem Blatt Papier beschränken.

Es ist ein Ergebnis der theoretischen Bemühungen der Informatik -die historisch aus Logik und Mathematik hervorgegangen ist, siehe die Vorlesung theoretische Informatik-, dass man den menschlichen Zeichenbenutzer mehr und mehr durch künstliche Automaten ersetzen kann. Solche Automaten nennt man dann auch 'semiotische Maschinen' bzw. die Disziplin, die sich damit beschäftigt, 'Computersemiotik' ('Computational Semiotics').

Das historisch berühmteste und bis heute wichtigste Beispiel eines zeichenverstehenden Automaten ist die Turingmaschine (so genannt von Alonzo Church bei einer Besprechung der entscheidenden Arbeit von Turing im Jahr 1937). Ohne hier auf die Details einzugehen -siehe dazu die Vorlesung Theoretische Informatik- sei hier nur folgendes angenommen (siehe auch Schaubild):

Um einen menschlichen Zeichenbenutzer durch einen Automaten hinreichend simulieren zu können,muss man im Prinzip aufzeigen, dass alle charakteristischen Eigenschaften des menschlichen Zeichenbenutzers im simulierenden Automaten auch gegeben sind. Dieser Aufweis soll hier informell und schrittweise geschehen.

1. Die Umgebung ('environment') des menschlichen Zeichenbenutzers sind Texte endlicher Länge. Diese Umgebung wird dadurch simuliert, dass man annimmt, die Umgebung liegt als ein Band vor, das mindestens nach einer Seite beliebig lang sein kann und das so aufgeteilt ist, dass in ein Feld des Bandes genau ein Zeichen geschrieben werden kann.




2. Das Lesen bzw. Schreiben eines Textes durch den menschlichen Zeichenbenutzer wird dadurch simuliert, dass der Automat einen Schreib-Lese-Kopf besitzt. Dieser Schreib-Lese-Kopf steht zu einem bestimmten Zeitpunkt immer über genau einem Feld. Der Inhalt dieses Feldes kann sowohl gelesen als auch geschrieben werden. Ausserdem kann der Schreib-Lese-Kopf entweder ein Feld nach links bzw. ein Feld nach rechts bewegt werden.




3. Es wird auch angenommen, dass das Handeln des Zeichenbenutzers im Lesen bzw. Schreiben besteht.




4. Das Verstehen -auch 'Interpretieren'- der Zeichenketten besteht darin, dass der menschliche Zeichenbenutzer in der Lage ist, bestimmten Zeichenketten ganz bestimmte Handlungen zuzuweisen, die entweder zur Beendigung des Verstehens führen oder aber im Verändern von Zeichenketten bestehen. Man kann auch sagen, dass die Aktivität des Verstehens an spezifische innere Zustände ('internal states') des Zeichenbenutzers gebunden ist. dieses Verstehen wird im Automaten dadurch simuliert, dass er eine endliche Menge von inneren Zuständen besitzt, die so beschaffen sind, dass für jedes Zeichen, das gelesen werden kann, festgelegt ist, welches Zeichen stattdessen an dieser Stelle zu schreiben ist (z.B. auch das gleiche), welche Bewegung der Schreib-Lese-Kopf ausführen soll und in welchen Folgezustand der Automat übergehen soll. Einen Maschinenzustand kann man auch einen 'Befehl' nennen und die Menge der Maschinenbefehle eine 'Maschinentafel'. Den Zustand eines solchen Automaten schreibt man oft auch als ein 5-Tupel im format:

   
   < S_i, a,b,M, S_j >

   mit

   • S_i := der aktuelle Zustand, in dem sich der Automat befindet

   • a := Zeichen, das gerade gelesen wird

   • b := Zeichen, das geschrieben werden soll

   • M := Welche Bewegung der Schreib-Lese-Kopf ausführen soll {L := Left, R := Right, H := Anhalten}

   • S_j der Zustand, in den der Automat übergehen soll

Diese kurze Beschreibung mag genügen, um zu illustrieren, warum man sagen kann, dass sich das Verhalten eines menschlichen Zeichenbenutzers in dem geschilderten Rahmen durch einen Automaten simulieren lässt.

START

3. Vom logischen Zustand zum physikalischen Zustand

Der soeben informell geführte Nachweis, dass man einen menschlichen Zeichenbenutzer durch einen Automaten im Format der Turingmaschine simulieren kann, hat zwar gezeigt, dass man auf einer begrifflichen, logischen Ebene das eine Verhalten auf das andere abbilden kann, aus ihm geht aber noch nicht hervor, ob sich diese theoretischen Konzepte auch technisch realisieren lassen.

Dass dieser Übergang vom theoretischen Konzept zur technischen Realisierung keineswegs trivial ist, zeigt das Leben von Turing selbst. Obwohl Alan Matthew Turing (1912-1954) zu seiner Zeit sicher einer von den Menschen war, die die theoretischen Perspektiven einer kommenden 'Computerwissenschaft' am weitesten voraussahen, war es ihm selbst nicht vergönnt, die Realisierung dieser Ideen zu erlebe; zu seiner Zeit war es noch nicht möglich, diese Konzepte technisch hinreichend umzusetzen.

Hier einige Meilensteine aus der Frühzeit der Computer:

Die 103 Jahre von Babbages Analytical Engine bis zur von Neumann Architektur zeigen, dass es keineswegs trivial ist, logische Konzepte in technische Prozesse umzusetzen. Also, wie kommt man vom logischen Konzept des Automaten zum technischen Gerät Computer?

Der Brückenschlag vom theoretischen Konzept zum realen Gerät gelingt, wenn man sich klar macht, wie man die Zustände eines Automaten physikalisch realisieren kann.

1. Im Zeitalter reiner Mechanik (siehe Babbage) hatte man nur unterschiedliche Stellungen von mechanischen Teilen zur Verfügung, um Zustände zu realisieren, z.B. die Stellung eines Zahnrades.

2. Mit der Verfügbarkeit von Relais konnte man die unterschiedlichen Stellungen eines durch Strom schaltbaren Relais ausnutzen (siehe Zuse).

3. Durch die Verwendung von Röhren konnte man die unterschiedlichen Spannungsbereiche am Ausgang von Röhren mit bestimmten Zuständen identifizieren.

4. Mit der Verfügbarkeit von Transistoren verfeinerte sich dieses Prinzip. Transistoren waren billiger, brauchten weniger Platz, waren schneller und zuverlässiger.

Das Prinzip, wie sich Zustände mittels Transistoren realisieren lassen, sei noch ein wenig mehr erläutert (siehe Schaubild, nach [TANENBAUM/GOODMAN 2001]):

In Abbildung (a) sieht man die Grundschaltung eines Transistors (der Kreis). Es gibt drei Verbindungen zur Aussenwelt: (i) die Basis, (ii) der Kollektor und (iii) der Emitter. Der Emitter liegt an Masse und der Kollektor über einen Widerstand (gezackte Linie) am Potential V_cc (z.B. 5V). Liegt die Eingangsspannung V_in unter einem bestimmten Schwellwert (z.B. 0.8V), ist also 'low', dann ist der Transistor gesperrt; dies führt dazu, dass V_out einen Wert nahe V_cc hat (also z.B. 5V), also 'high'. Liegt V_in über dem Schwellwert (= high), dann schaltet der Transistor durch und die Spannung an V_out liegt nahe bei der Masse (0 V)(= low). Da hier der Ausgang gerade entgegengesetzt ist zum Eingang (High bei Low und umgekehrt), realisiert dieser Transistor logisch eine Inversion, d.h. er verhält sich wie ein Inverter.

Abbildung (b) zeigt zwei Transistoren, die in Reihe geschaltet sind. Hier ist die Ausgangsspannung V_out nur dann low, wenn sowohl V₁ als auch V₂ 'high' sind. Diese Schaltung realisiert also ein NAND-Gatter (s.u.).

Abbildung (c) zeigt zwei Transistoren, die parallel geschaltet sind. Hier ist die Ausgangsspannung V_out gleich low wenn entweder V₁ oder V₂ 'high' sind. Diese Schaltung realisiert ein NOR-Gatter.

Damit ist ein erster Ansatzpunkt gegeben, von dem aus prinzipiell Zustände von Automaten physikalisch realisiert werden können. Allerdings kann man noch nicht sehen, wie man auf diese Weise unterschiedliche Zeichen (= Objekte) darstellen und auch nicht, wie man Operationen mit Zeichen realisieren kann.

START

4. Physikalische Gatter und binäre Logik

Die Antwort auf die Frage nach der Realisierung von Zeichen bzw. Zeichenketten liegt in der Möglichkeit, elementare Zustände, also Basisgatter, miteinander zu komplexeren Einheiten zu verknüpfen. Zur Beschreibung solcher komplexer Schaltungen macht man sich die Tatsache zunutze, dass das Schaltverhalten der elementaren Gatter sich durch die Reduzierung auf 'low' und 'high' (bzw. auf '0' und '1' bzw. auf 'false' und 'true') auf eine binäre Logik zurückführen lässt, die sich mit den Mitteln der klassischen Aussagenlogik (oder auch einer 'boolschen Logik') beschreiben lässt.

Mit Hilfe der Gesetze der Aussagenlogik lassen sich dann aus den elementaren Gattern 'NOR', 'NAND', 'NOR', 'NOT', 'AND' und 'OR' beliebige Kombinationen zusammenbauen.

Die rein logische Struktur repräsentiert in diesem Zusammenhang aber nur einen Teil dessen, was mittels Gattern physikalisch realisiert werden kann. Zusätzlich zur logischen Struktur muss man auch das Zeitverhalten einbeziehen. Im allgemeinen Fall sind die Gatter in Schaltungen eingebettet, in denen die Eingangssignale kein beliebiges Zeitverhalten zeigen, sondern in der Regel bestimmte Taktgeber (Oszillatoren) die Spannungsänderungen in einer bestimmten Form und mit einem definierten Zeitverhalten ausführen. Dadurch entstehen genormte Signale, die es allererst möglich machen, ein transparentes Schaltverhalten zu erzeugen.

Es folgen zwei Screenshots von Schaltungen, die mit dem Opensource-Programm KLogic erstellt wurden. Die erste Schaltung zeigt einen Oszillator, der 10 Einheiten high ist und 10 einheiten low. Sein signal wird auf zwei Leitungen aufgespalten; in einer leitung sitzt ein Verzögerungselement mit einer Verzögerung von 5 Einheiten/ sec. Man kann erkennen, wie daraus zwei versetzte signale entstehen.

Die zweite Schaltung enthält ein UND-Gatter mit zwei Eingängen. Die eingänge werden über Schalter mit signalen versorgt. Wird der Schalter nicht betätigt, dann hat er den Wert high, bei Betätigung den Wert low. Der Ausgang des UND-Gatters liegt an einer LED. Sobald ein Schalter betätigt wird, geht das Signal auf LOW und damit das ganze Gatter.

Es wird Gegenstand der nächsten Vorlesungen sein, zu zeigen, wie man aus diesen Grundschaltungen solche Strukturen realisieren kann, mit denen sich dann Zeichenketten darstellen und durch Operationen verändern lassen.

START

5. Testfragen und Übungsaufgaben

START