Pilot ACE

Die Pilot ACE (Automatic Computing Engine) ist ein von Alan Turing konzipierter Computer der im Jahre 1950 fertiggestellt und unter dem Namen DEUCE verkauft wurde. Die Pilot ACE zeichnet sich insbesondere dadurch aus, daß ihr Befehlssatz nur aus Befehlen der Form "transferiere Daten von Register A zu Register B" besteht.

Der vorliegende Text beschreibt die grundlegenden Merkmale der Architektur der Pilot ACE und erklärt die Programmierung für diesen Computer. Gleichzeitig dient dieser Text als Bedienungsanleitung für eine (Java-)Simulation dieser Maschine.

1. Einführung
1. Geschichte
2. Überblick über die Architektur
2. Architektur
1. Zahlen und Zeit
2. Speicher
3. Arithmetische und logische Operationen
4. Multiplikation
5. Bedingte Befehle, Sprungbefehle
6. Eingabe und Ausgabe
7. Übersicht über alle Herkunfts- und Zieladressen
   
3. Programmierung für die Pilot ACE
1. Übersicht
2. Algorithmische Programmierung
1. Beispiel 1
2. Beispiel 2
3. Detaillierte Programmierung
1. Aufbau eines Befehls
2. Beispiel 3
3. Discrim
4. Beispiel 4
   
4. Die Simulation
1. Übersicht
2. Tutorial
   
5. Kommentierte Literaturliste

Alan Turing erstellte das Design für einen Computer genannt ACE ("Automatic Computing Engine") 1945, welches im darauffolgenden Jahr auch vom zuständigen Gremium (dem National Physical Laboratory) akzeptiert wurde. Da es sich um einen sehr ambitionierten Entwurf handelte, sollten zuerst die wesentlichen Konstruktionsmerkmale an einer kleineren Maschine - der Pilot ACE - ausprobiert werden.

Die Herstellung der Pilot ACE zog sich einige Zeit hin, und erst am 10. Mai 1950 lief das erste Programm auf diesem Rechner. Turing hatte zu diesem Zeitpunkt allerdings, frustriert über die langsamen Fortschritte, das NPL verlassen und arbeitete an der Manchester University.

Die Pilot ACE war der erste elektronische Computer in London und sie war für einige Zeit mit einer Taktfrequenz von 1Mhz der schnellste Computer der Welt. DEUCE - die Produktionsversion der Pilot ACE - verkaufte sich mehr als 30 mal.

Der vollständige ACE wurde erst 1958 fertiggestellt und war kein großer Erfolg.

Die Pilot ACE besteht im Grunde aus einer Kontrolleinheit und einer Anzahl von Speichern, wobei mit manchen Speichern Arithmetische und logische Funktionen verbunden sind.

Ein Programm des Pilot ACE besteht aus einer Serie von Transfers von einem Register zum nächsten. Die Befehle des Pilot ACE werden, genau wie die Daten auf denen das Programm arbeitet, im "Hauptspeicher" gehalten.

Graphik 1 zeigt das prinzipielle Design der (Pilot) ACE. S0 bis S31 bezeichnen die Ausgänge der Speicher, welche durch die Kontrolle aktiviert werden. In dem Moment wo ein Speicher angewählt wird, wird die darin gespeicherte Zahl Bit für Bit auf den Highway geleitet (wobei das least significant bit zuerst kommt) und bei einem auch durch die Kontrolle aktivierten Speicher wieder gespeichert.

Nahezu gleichzeitig wird aus einem der Speicher über den sogenannten Instruction Highway der nächste Befehl geladen.

Innerhalb der Pilot ACE wird das Binäre System benutzt, wobei jeweils nur ein Bit verarbeitet wird; man kann sich also insbesondere den Instruction Highway und den Highway als 1-Bit-Bus vorstellen. Die Bearbeitung eines Bit benötigt immer einen Taktzyklus und damit ca. 1 m s. Jeweils 32 Taktzyklen werden zu einem "Minor Cycle" (im folgenden MiC) zusammengefaßt und 32 MiC´s werden als "Major Cycle bezeichnet (im folgenden MaC).

Wie sich der Leser vermutlich bereits gedacht hat, bestehen Zahlen und Befehle damit im Allgemeinen aus jeweils 32 Bit (wobei es allerdings einige 64 Bit Speicher gibt). Positive Ganze Zahlen werden dabei durch 31 Bit und einer 0 als Vorzeichenbit repräsentiert, negative Zahlen x werden durch die binäre Repräsentation von 2³² – x dargestellt. Gleit- und Festkommazahlen werden von der Hardware nicht unterstützt.

In der ursprünglichen Version der Pilot ACE wurden lediglich sogenannte "Acustic Delay Lines" verwendet. Es handelt sich dabei im Prinzip um lange Zylinder aus Kupfer die je nach den anliegenden Signalen auf der einen Seite in Schwingungen versetzt werden. Die Schwingungen wandern dann den Zylinder herunter und werden auf der anderen Seite wieder in elektrische Signale übersetzt. Dieser Speicher zeichnete sich um 1950 dadurch aus, daß er im Vergleich zu Vakuum Röhren sehr billig war, er hatte aber sehr lange Zugriffszeiten und war unglaublich unzuverlässig. Anfang der 50 Jahre wurden diese Speicher im Allgemeinen durch die ersten magnetischen Speicher ersetzt, in der Pilot ACE wurden er allerdings belassen und nur durch einen magnetischen Speicher ergänzt.

Interessant ist auch, welche Lösungen die Architekten des Pilot ACE für das Problem der Zugriffszeiten fanden: so findet sich bereits in diesem Computer eine rudimentäre Speicherhierarchie (gebildet durch kürzere 32 bit und längere 1024 bit Acustic Delay Lines) und es wurde von den Programmieren erwartet, daß sie ihre Instruktionen derartig im Speicher verteilten, daß immer nach der Abarbeitung eines Befehls der nächste sofort lesbar ist.

Alle Befehle der Pilot ACE bestehen nur aus Transfers von einem Speicherort zu einem anderen. Um auch arithmetische und logische Operationen durchzuführen sind einige der Speicheradressen mit solchen Operationen verbunden.

Zum Beispiel werden alle Zahlen die nach D17 transferiert werden auf den Inhalt der Speicheradresse TS16 (TS = temporary storage, das bezeichnet immer eine Speicheradresse mit der Kapazität 32 oder 64 Bit) addiert. Transferiert man eine Zahl nach D18 so wird sie von dem Inhalt von TS16 abgezogen und schließlich kann man auch noch Zahlen nach D16 transferieren um den eigentliche Inhalt von TS16 zu ersetzen

Für die Multiplikation wird die lange Speichereinheit DS14 mit 64 Bit verwendet. Um zwei Zahlen zu multiplizieren, muß der Multiplikand nach TS20 geschickt werden, während der andere Term in einem ungeraden MiC nach DS14 geschickt wird. Schließlich muß noch die zweite Hälfte von DS14 mit Nullen gefüllt werden (dies geschieht indem in einem geraden MiC eine Null nach DS14 transferiert wird) und die Multiplikation wird durch den Transfer einer beliebigen Zahl nach DS19 gestartet. Von diesem Moment an dauert die Multiplikation 65 MiC, wobei in dieser Zeit aber beliebige andere Operationen durchgeführt werden können.

Nach dieser Zeit findet sich das Ergebnis der Multiplikation in DS14.

Es sei noch bemerkt, daß die Multiplikation die Zahlen wie positive ganze Zahlen behandelt und es dem Programmierer überlassen bleibt sich mit den Vorzeichen und evtl. dem Komma zu beschäftigen.

Bedingte Befehle werden in der Pilot ACE mit der Hilfe der Zieladressen D25 und D24, den sogenannten "discriminating destinations" realisiert. Bei beiden dieser Adressen wird, jeweils abhängig von einer Bedingung, der Befehl um 1 MiC später geladen d.h. er kommt von einer anderen Adresse (wie genau wird im Abschnitt über die detaillierte Programmierung klar werden). Welche Bedingung angewandt wird, unterscheidet sich nach den Zieladresse, bei D25 wird darauf überprüft ob die übertragene Zahl nur aus Nullen besteht, bei D24 wird nach dem Vorzeichen unterschieden.

Die Eingabe und Ausgabe von Befehlen und Daten geschieht üblicherweise über sogenannte Hollorith (Loch-) Karten und unter Verwendung einiger spezieller Ziel- und Herkunftsadressen. Eine genaue Beschreibung dieses Mechanismus geht allerdings über den Rahmen diese Arbeit hinaus, der interessierte Leser sei auf die kommentierte Literaturliste verwiesen.

Über die Hollorith Karten hinaus gibt es noch die Möglichkeiten einzelne Befehle per Hand einzugeben (über eine Leiste von 32 Schaltern, welche über die Herkunftsadresse 0 ausgelesen werden können). Auch gibt es eine dazu entsprechende Ausgabeadresse D28, bei der die hier gespeicherte Zahl durch eine Leiste von Lampen dargestellt wird.

Um die Gelegenheit zu haben die Zahl auch abzulesen bzw. im richtigen Moment etwas einzugeben, gibt es eine weitere Möglichkeit zur Interaktion zwischen Benutzer und Maschine: die sogenannten "Stopper Instructions" vor denen die Maschine so lange verweilt bis ein Knopf an der Maschine gedrückt wird.

In den frühen Versionen der Pilot ACE gab es schließlich auch noch eine Klingel mit der die Maschine den Bediener aufwecken konnte.

Im Speicher der Pilot ACE befinden sich die folgenden Speichereinheiten:

• 8 große Speicher (jeder mit 1024 Bit), sie werden im folgenden mit DL1 - DL7 und DL26 bezeichnet.
• 8 kleinere Speicher (jeder mit 32 Bit), die im folgenden mit TS8 – TS11, TS15, TS16, TS26 und TS27 bezeichnet werden.
• 2 kleine Speicher mit doppelter Länge (= 64Bit) mit den Namen DS12 und DS14.
  

Mit den genannten Speichern sind verschiedene Ziel- und Herkunftsadressen verbunden, die unter Umständen verschiedene logische und arithmetische Funktionen auf den Speicherinhalten durchführen, die folgende Tabelle zeigt sie alle in der Übersicht.

(*: Weitere in Rahmen dieser Arbeit nicht besprochene Funktionen, die sich meist auf die Ein- und Ausgabe über Hollorith Karten beziehen).

Um ein Programm für die Pilot ACE zu schreiben, empfehlen die Konstrukteure ein mehrstufiges Verfahren. Zuerst wird der Algorithmus prinzipiell betrachtet, d.h. solche Dinge wie das Plazieren der Befehle im Speicher, der Ort des nächsten Befehls, der wirkliche Aufbau von Sprungbefehlen und die Ein- und Ausgabe wird ignoriert. Allerdings wird der Algorithmus schon hier nur als eine Folge von Transfers von einem Speicherort zum nächsten aufgefaßt (eine Ausnahme sind die Sprungbefehle).

Im zweiten Schritt wird dann betrachtet wie tatsächlich jeweils die nächsten Instruktionen geladen wird und wo die Instruktionen und die Daten im Speicher zu finden sind.

Im letzten Schritt schließlich müssen die Instruktionen so aufgearbeitet werden, daß sie tatsächlich über Hollorith Karten eingelesen werden können und die Ergebnisse auch wieder auf diese Karten geschrieben werden.

Nur die ersten beiden Schritte werden in dieser Text behandelt und die Simulation wird die Fragen der Ein- und Ausgabe aussparen und auf der Ebene des zweiten Schrittes arbeiten.

Es sei noch hinzugefügt, daß hier kein Anspruch auf Vollständigkeit erhoben wird, lediglich sollen nur die einfacheren Funktionen vorgestellt werden, wobei alles im folgenden Beschrieben auch in der Simulation ausprobiert werden kann.

Die allgemeine Form eines Befehls für die Pilot ACE ist wie bereits mehrfach erwähnt immer der Transfer von einer Speicheradresse zu einer anderen. Handelt es sich dabei um einen Transfer zwischen zwei kurzen Speicheradressen (=32Bit), so wird dies in der Form

notiert.

Unter Umständen ist es wichtig zu bestimmen wie lange der Transfer dauern soll (z.B. wenn man eine Zahl zu einer anderen addiert). Aufgeschrieben wird dies so:

Haltende Befehle (die oben beschriebenen Stopper), d.h. Befehle die warten bis ein Knopf an der Maschine gedrückt wird, werden durch ein X hinter dem Befehl geschrieben. Also:

Schließlich werden Sprungbefehle in der algorithmischen Programmierung textuell beschrieben.

Mit diesen wenigen Befehlen und den unter 2.7 genannten Speicheradressen kann man bereits ein einfaches Programm schreiben welches die unglaublich sinnvolle Aufgabe erfüllt zu einer Zahl in TS16 immer wieder eine Eins zu addieren, diese mit den Lampen auszugeben, danach zu warten und zu beenden, wenn die Zahl so groß geworden ist, daß das Sign Bit eins ist (Overflow).

2: 16 - 28 # Register 16 mit den Lampen ausgeben

3: 25 - 17 X # Warten und dann eine Eins auf 16 addieren

4: Wenn Sign Bit dann Ende sonst 2.

Schon etwas sinnvoller ist die Ausrechnung der Fibonaccizahlen.

Das Programm orientiert sich an folgendem Pseudocode:

a = 0;

b = 1;

while (true) {

c = a+b;

System.out.println(c);

a = b;

b = c;

}

1: 28 - 26 # Eine Null nach 26 schreiben

2: 25 - 27 # Eine Eins nach 27 schreiben

3: 28 - 16 # Eine Null nach 16 schreiben

4: 26 - 17 # Inhalt von 26 auf den von 16 addieren

5: 27 - 17 # Inhalt von 27 auf den von 16 addieren

6: 16 - 28 # Die momentane Zahl in 16 mit den Lampen ausgeben

7: 27 - 26 X # Warten und dann den Inhalt von 27 nach 26

8: 16 - 27 # Den Inhalt von 16 nach 27

9: wieder bei 3 anfangen

In diesem Code wurde zusätzlich zu dem bisher beschriebenen noch ein unbedingter Sprung verwendet, dieser wird nicht über die "discriminating destinations" realisiert, sondern durch eine geschickte Angabe des Ortes des nächsten Befehls. Wie genau dies geschieht, wird im nächsten Paragraph beschrieben.

Bisher wurde nicht berücksichtigt wo die Befehle im Speicher liegen und wie lange evtl. nach einer Befehl auf den nächsten gewartet werden muß.

Um dies zu bestimmen bestehen die Befehle aus ein paar mehr Teilen als den bisher erwähnten.

Jeder Befehl besteht aus 32 Bit die in 7 Teile geteilt sind:

N: Bits 2-4 Herkunft des nächsten Befehls.

S: Bits 5-9 Herkunft der Daten die transferiert werden sollen.

D: Bits 10-14 Ziel für den Transfer.

s: Bit 15 Bestimmt einen Teil der Reihenfolge der Befehle, im Rahmen

Dieses Textes kann man diesen Teil aber ignorieren.

W: Bits 17-21 s.u.

T: Bits 25-29 s.u.

G: Bit 32 Ist eins genau dann, wenn dieser Befehl ein Stopper ist.

Die restlichen Bits werden nicht benötigt und waren wohl gedacht um die im vollständigen ACE zusätzlich vorhandenen Register anzusprechen.

Von den Teilen des Befehls wurden bisher nur der S, D und der G Teil behandelt, da sich die anderen Teile auf die tatsächliche Plazierung der Befehle im Speicher beziehen.

Wie bereits oben beschrieben werden die Befehle auch in den Speichereinheiten gehalten. Betrachtet man jetzt die tatsächliche Speicherung der Befehle, so würde man erwarten, daß die Befehle in der Reihenfolge der Abarbeitung in den Registern liegen (in diesem Fall währe es dann nicht notwendig die Adresse des nächsten Befehls anzugeben, da sie außer bei Sprüngen trivialerweise gegeben währe). Betrachtet man allerdings die Kontrolleinheit der Pilot ACE so stellt man fest, daß diese es nicht erlaubt Befehle in zwei aufeinanderfolgenden MiCs zu lesen, und die sukzessive Speicherung der Befehle in einem großen Register würde es dann unter Umständen erfordern 30 MiCs zu warten bis der nächste Befehl abzurufen währe. Auch mag es für Schleifenkonstrukte sinnvoll sein einige Befehle derartig zu speichern, daß sie immer schnell erreichbar sind. Um solche Probleme zu lösen, ist der Programmierer der Pilot ACE aufgefordert die Befehle "ideal" über die verschiedenen Speicherorte zu verteilen und es ist notwendig in den Befehlen zu spezifizieren von wo und wann der nächste Befehl abgerufen werden soll.

Wie bereits festgestellt ist es notwendig zu bestimmen wann der nächste Befehl geladen werden soll und wie oft der Transfer einer Zahl wiederholt werden sollte - dies geschieht durch die Teile W und T.

Angenommen der aktuelle Befehl ist im m`ten MiC fertig geladen, dann beginnt der Transfer der Zahlen im MiC (m+W+2) und endet im MiC (m+T+2), der Transfer dauert also (T-W+1) MiC´s. An dem einfachsten Beispiel m=0, T=0, W=0 erklärt, bedeutet dies, daß der Transfer im MiC 2 beginnt und auch wieder endet, also genau einen MiC lang dauert.

Gleichzeitig mit dem Ende des Transfers (also im MiC (m+T+2)) wird auch der nächste Befehl aus dem durch N beschriebenen Register geladen.

Mit der oben beschriebenen Struktur der Befehle ist es nun bereits möglich das bereits vorgestellte Beispiel der Berechnung der Fibonacci Zahlen auf dem Level der detaillierten Programmierung zu beschreiben.

Üblicherweise werden in diesem Level die Programme in Tabellen beschrieben, wobei jede Tabelle jeweils für eines der Register steht und die Zeilenindizes die Position des aktuellen Befehls in diesem Register beschreiben.

In dem hier besprochenen Beispiel genügt ein langes Register um das ganze Programm zu speichern, weshalb hier nur die Tabelle für den DL1 angegeben wird (alle anderen Register sind vollständig mit Nullen gefüllt).

Index: N: S-T: W: T: G:

0. 1 28 - 26 0 0 0

2. 1 25 - 27 0 0 0

4. 1 28 - 16 0 0 0

6. 1 26 - 17 0 0 0

8. 1 27 - 17 0 0 0

10. 1 16 - 28 0 0 0

12. 1 27 - 26 0 0 1

14. 1 16 - 27 20 20 0

In den vorherigen Abschnitten wurden bedingte Sprünge textuelle beschrieben, während der detaillierten Programmierung werden diese Beschreibungen durch die realistische Benutzung der Discrim Register ersetzt.

Wird eine Zahl in eines der Discrim Register geschickt, so wird der nächste Befehl nach folgenden Regeln bestimmt:

D25: Wird eine Zahl nach D25 transferiert so wird der nächste Befehl aus dem Register N im (m+2+T)´ten MiC geladen, wenn die transferierte Zahl nur aus Nullen besteht. Ist in der transferierten Zahl mindestens eine Eins enthalten so wird der nächste Befehl aus dem (m+3+T)´ten MiC geladen.

D24: Wird eine Zahl nach D24 transferiert so wird der nächste Befehl aus dem Register im (m+2+T)´ten MiC geladen, wenn die transferierte Zahl positiv ist. Ist die Zahl negativ, so kommt der nächste Befehl aus dem (m+3+T)´ten MiC.

Mit den Discrim Register kann man nun auch das Beispiel 1 detailliert aufschreiben (wobei einmal angenommen sei, der Befehl 3 ist bereits der erste Befehl des nächsten Programmes und so äquivalent zu dem im Beispiel 1 verwendeten "ende").

Index: N: S-T: W: T: G:

0. 1 28 - 16 0 0 0

2. 1 16 - 28 0 0 0

3. ... .... . . .

4. 1 25 - 17 0 0 1

6. 1 16 - 24 26 26 0

Die von den Autoren programmierte Simulation erlaubt das Ausführen einfacher Programme auf einer simulierten Pilot ACE wobei die Programme auf dem oben beschriebenen Level der detaillierten Programmierung eingegeben werden müssen.

Um die Komplexität in einem erträglichen Rahmen zu halten, beschränkt sich die Simulation auf eine kleine Teilmenge der Funktionen der Pilot ACE. Konkret sind die folgenden Register implementiert und können wie oben beschrieben benutzt werden:

• DL1 (für dieser Register können am Anfang die Befehle eingetragen werden und zwar in die aus dem Abschnitt über die detaillierte Programmierung bekannten Tabellen.)
• DL2 (hier können anfängliche Zahlen eingegeben werden.).
• TS16 mit Zieladressen 17 und 18
• TS26
• TS27
• Herkunstadressen 25, 28 und 29
• Zieladressen 28 und 24

Eine weitere Einschränkung ist, daß es nicht möglich ist auf den Befehlen arithmetische Operationen auszuführen. Auch ist es nicht möglich Zahlen als Befehl zu interpretieren und Auszuführen.

Um das Programm zu verwenden muß man in der jetzigen Version einfach auf die Datei jv.bat (startet das Programm als Application) oder apv.bat (startet des Programm als Applet aus der Datei PilotACE.html unter Verwendung des Appletviewers) Doppelklicken.

Es erscheint das Programmfenster. Um die PilotACE zu simulieren, muß man nun ein Programm eingeben. Dafür klickt man im oberen Teil des Fensters auf den Reiter mit dem Titel "Programming". Nun kann man z.B. das 3. Beispielprogramm eingeben (die Berechnung der Fibonaccizahlen). Wie genau das Programm eingegeben werden sollte, zeigt Graphik 3. Ist man mit der Eingabe fertig, klickt man unten auf den "Compile" Knopf und behebt eventuell angezeigte Fehler.

Wurde das Programm erfolgreich kompiliert kann man es durch den "Start" Knopf starten. Um den Programm beim Ausführen zuzusehen, klickt man auf den Reiter "Status" (hier sieht man den dynamisch aktualisierten Inhalt der Register) oder auf den Reiter "Simulation" (hier sieht man eine schematische Darstellung der Struktur der simulierten PilotACE, wobei die momentan aktiven Teile jeweils rot werden).

Die Tasten "Slow" und "Fast" erlauben es die Geschwindigkeit des Programms in 7 Stufen zu verändern (wobei in der schnellsten Stufe die Animationen deaktiviert wird). Der "Continue" Knopf dient dazu, die Simulation nach einem stoppenden Befehl wieder zu starten (die Maschine piept um den Benutzer auf das Anhalten aufmerksam zu machen). Schließlich dient der "Clear" Knopf zum Löschen des momentanen Lampenstatus (wie bereits erwähnt wird nach dem Transfer einer neuen Zahl B in das Lampenregister das Bitweise Oder der vor dem Transfer im Lampenregister gespeicherten und der neuen Zahl B angezeigt).

[1] Progress Report on the Automatic Computing Engine, J.H. Wilkinson, April 1948;

Department of Sientific and Industrial Research, National Physical Laboratory.

(www.alanturing.net).

[2] The Logical Design of the Pilot Model ACE, J.H. Wilkinson, Sept 1951;

Department of Sientific and Industrial Research, National Physical Laboratory.

(www.alanturing.net).

[3] Programming and Coding for the Pilot Model ACE, by Wilkinson, 20 Nov 1951; Department of Sientific and Industrial Research, National Physical Laboratory.

(www.alanturing.net).