Unterthema: Eine Anwendung des Assembler-Konstruktors GUY
Unterthema: Ein Beispiel für die vom Disassembler erzeugte Ausgabe
Unterthema: Occam-PAR-Konstrukt
Unterthema: Code des ALT-Konstrukts
Die auf dem Hoareschen Konzept `Communicating Sequential Processes´ (vgl. [3]) basierende Programmiersprache Occam (vgl. [7]) ist auf die effiziente Programmierung paralleler Prozesse auf Transputern zugeschnitten.
Der vom britischen Halbleiterhersteller Inmos entwickelte Occam-Compiler, der Bestandteil sowohl des `Transputer Development System - TDS´ als auch des `Occam-Compiler-Server-System - OCS´ ist, bietet darüber hinaus die Möglichkeit, mit dem Assembler-Konstruktor GUY in einem Occam-Programm auf Assemblerebene des Transputers zu programmieren. Das ist normalerweise selten nötig, da der Occam-Compiler effizienten Transputermaschinencode erzeugt.
Die Verwendung der Assemblersprache ist aber dann von Vorteil, wenn es um die Bewältigung spezieller Probleme geht, wie sie zum Beispiel das Debugging aufwirft, das manchmal die Analyse des ausführbaren Codes erfordert. Mit Hilfe eines Disassemblers für den Transputertyp T414 kann man ein Occam-Programm und seinen Transputercode zu diesem Zweck vergleichen. Im folgenden werden also der Konstruktor GUY und einige seiner Anwendungen sowie die Realisation der Haupt-Konstruktoren von Occam - PAR und ALT - auf Transputercodeebene vorgestellt.
GUY kann nicht nur wie alle anderen Occam-Konstruktoren benutzt werden, sondern ermöglicht auch die Verwendung der im herkömmlichen Occam-Programm deklarierten Variablen in einem Transputermaschinenbefehl. Dadurch kann man direkt auf Variablen, Kanäle, Register und Speicherzellen zugreifen. Diese Eigenschaft kann beim Testen von Occam-Programmen erfolgreich eingesetzt werden.
Der Befehlsatz ist von der internen Wortlänge eines Transputers (16 oder 32 Bit) unabhängig. Mit den Transputerbefehlen PFIX und NFIX kann die Größe eines Operanden beliebig erweitert und mit dem Operationscode OPR der Inhalt des Operand-Registers als die auszuführende Operation interpretiert werden. PFIX lädt seine vier Operand-Bits in das Operand-Register und verschiebt dann den Inhalt vier Bits nach links, so daß die vier niederwertigen Bits des Operand-Registers wieder frei und zum Laden des Operanden des nächsten Befehls bereit sind.
NFIX funktioniert genauso, außer, daß das Operand-Register vor dem Verschieben komplementiert wird. Um beispielsweise die Konstante 50 zu laden, werden die Befehle `PFIX 3´ und `LDC 2´ benötigt, während die Konstante -50 mit `NFIX 3´ und `LDC #E´ geladen wird. Es ist hier noch besonders zu erwähnen, daß PFIX und NFIX die einzigen Befehle sind, die das Operand-Register nach getaner Arbeit nicht löschen.
Ein Transputer hat einen nur aus den drei Registern A, B und C bestehenden Rechenstack, in dem die meisten arithmetischen und logischen Operationen durchgeführt werden. Außerdem besitzen Transputer
Für die Prozesse, die den Verzögerungsoperator AFTER enthalten, sind weitere spezielle Register vorgesehen. Außer den sechs Spezialregistern gibt es insgesamt noch acht weitere.
Unter GUY gibt es folgende Vorteile:
GUY LDL x ADC-30 STL x
GUY LDC #80000000 LDDNL 9
INT Ws.Adr, Ws.Inh:
...
GUY
LDL 0
STL Ws.Inh
LDLP 0
STL Ws.Adr
...
den Workspace-Zeiger, also den Inhalt des Workspace-Registers, das momentan auf den Workspace des gerade ausgeführten Prozesses zeigt. Die Variable Ws.Inh enthält den Inhalt der nullten Speicherzelle im Workspace, also der vom Workspace-Zeiger referierten Speicherzelle.
Jeder parallele Prozeß hat einen eigenen Workspace, wo seine lokalen Variablen, Kanäle und Parameter abgespeichert sind. Der Workspace ist so vergeben, daß in der Notationsreihenfolge später deklarierte Variablen oder Kanäle kleinere Offsets relativ zum Workspace-Zeiger haben.
Der Workspace des Fakultät-Programms besteht, wie in der Abbildung zur Workspace-Belegung zu sehen, aus zwei Teilen, die hier als System- und Program-Workspace bezeichnet sind. Der Program-Workspace kann wieder aus mehreren lokalen Workspaces von parallel laufenden Prozessen bestehen, während ein Programm nur einen System-Workspace hat, der immer aus 17 Wörtern besteht und im wesentlichen für die vom TDS definierten Systemkanäle gebraucht wird:
SEQ i = 1 FOR ngebraucht und enthält die Anzahl der noch zu verarbeitenden Schleifendurchläufe. Im folgenden wird für den Begriff `Program-Workspace´ die Abkürzung `Workspace´ verwendet.
Auch um direkt auf das Instruktions-Register zugreifen zu können, kann man GUY benutzen. Auf Assemblerebene im Schutze von GUY sieht das folgendermaßen aus:
INT Instr, Instr.Adr:
...
GUY
LDC -1
LDPI
STL Instr.Adr
LDL Instr.Adr
LDNL 0
STL Instr
...
Die Speicheradresse des Befehls LDPI wird dabei in Instr.Adr abgelegt. Instr enthält vier Befehle (4 Bytes), den Befehl LDPI selbst und seine Nachbarn. Die letzten zwei Bits in Instr.Adr geben darüber Auskunft, welches der Bytes den Befehl LDPI beinhaltet; zum Beispiel Byte 1, wenn die letzten beiden Bits gleich 01 sind.
Ein Kanal k befindet sich im Kommunikationszustand `leer´, falls keiner der beiden durch ihn verbundenen Prozesse kommunizieren will. k hat in diesem Fall den Zustandswert #80000000. Ist ein Prozeß bereit, über den Kanal k Nachrichten zu senden oder zu empfangen, sein Kommunikationspartnerprozeß aber noch nicht zum Empfangen oder Senden bereit, so wird der Deskriptor des zur Kommunikation bereiten Prozesses in k abgespeichert. (Ein Deskriptor (vgl. [5, S. 29]) eines Prozesses ist die Summe seines Workspace-Zeigers und seiner Priorität, die nur den Wert 0 oder 1 annehmen kann und im letzten Bit des Prozeß-Deskriptors untergebracht ist.)
Nach Ausführung des Programmfragments:
CHAN OF INT k:
INT k.Zustand:
...
GUY
LDL k
STL k.Zustand
...
enthält die Variable k.Zustand den Kommunikationszustand des Kanals k.
Die Systemkanäle werden wie normale Kanäle behandelt, zum Beispiel nach Ausführung des Programmfragments
PROC scr.keyb(CHAN OF ANY keyboard, screen)
INT scr.Zustand, scr.Adr, keyb.Zustand, keyb.Adr:
...
LDL screen
STL scr.Zustand
LDLP screen
STL scr.Adr
LDL keyboard
STL keyb.Zustand
LDLP keyboard
STL keyb.Adr
...
enthalten scr.Zustand und keyb.Zustand jeweils die Zustände von screen und keyboard. Die Adressen von screen und keyboard sind den Variablen scr.Adr und keyb.Adr zugeordnet. Unter TDS gilt:
scr.Adr = #801F0054 keyb.Adr = #801F004CSie werden im System-Workspace abgespeichert. screen enthält als Anfangszustand übrigens nicht #80000000, sondern #801EFE7D.
Wenn ein Prozeß wegen einer Verzögerungsoperation (AFTER) auf den Ablauf seiner Verzögerungszeit wartet, wird er vom Scheduler aus der Warteschlange der zur Ausführung bereiten Prozesse herausgenommen. Sein Workspace-Zeiger wird abgespeichert.
Alle solchen Prozesse bilden eine Zeit-Warteschlange. Die Speicherzelle #80000024 (bzw. #80000028) enthält den Workspace-Zeiger des ersten Prozesses in der Zeit-Warteschlange für Prozesse mit Priorität 0 oder für solche mit Priorität 1. Mit Hilfe von GUY kann man auf sie zugreifen:
...
INT TPtrLoc0, TPtrLoc1:
...
GUY
LDC #80000024
LDNL 0
STL TPtrLoc0
LDC #80000028
LDNL 0
STL TPtrLoc1
...
Wenn kein Prozeß auf den Ablauf seiner Verzögerungszeit wartet, dann haben TPtrLoc0 und TPtrLoc1 den Wert #80000000.
Die vom TDS-Compiler erzeugte ausführbare Datei mit der Extension `.CE1´ kann mit dem Disassembler disassembliert werden. Die Eingabe des Disassemblers ist der ausführbare Maschinencode eines Programms, hier zum Beispiel des abgedruckten Quellprogramms `addieren´; die entsprechende Ausgabe des Disassemblers ist darunter abgebildet.
Die zweite Spalte (hinter dem Doppelpunkt) gibt den Inhalt der CE1-Datei an, also den ausführbaren Maschinencode. Die relative Adresse des Maschinencodes in der CE1-Datei befindet sich in der ersten Spalte. Die dritte und vierte Spalte (vor dem Semikolon) enthält Assemblerbefehle für den T414. Adresse und Code beziehungsweise Operand der Befehle sind in hexadezimaler Darstellung angegeben.
Die CE1-Datei ist folgendermaßen aufgebaut. Das erste 4-Byte-Wort (Adressen #0 bis #3) stellt die um eins verminderte Größe der CE1-Datei dar (Anzahl der Wörter). In diesem Beispiel ist das erste Wort gleich #0000000E, das heißt, die Größe der CE1-Datei beträgt #F (= #E + 1 = 15) Wörter, also 60 Bytes.
Die 7 nachfolgenden Wörter (Adressen #4 bis #1F) sind nur eine Markierung. Aus dem achten Wort (Adressen #20 bis #23) ergibt sich die Größe des benötigten Workspace für den Lauf des Occam-Programms. Der eigentliche Maschinencode eines Occam-Programms beginnt in dieser Darstellung immer bei Adresse #24. Die Adresse des ersten auszuführenden Befehls ergibt sich aus dem um 4 erhöhten Wert des vorletzten Wortes (Adressen #34 bis #37):
#00000020 vorletzt_Wort + 4 = #24Es ist nur ein Zufall, daß in diesem Beispiel die Anfangsadresse #24 und die Adresse des ersten auszuführenden Befehls übereinstimmen. Das letzte Wort ist immer gleich 0. Die wesentliche Befehlsfolge für das Occam-Programm `addieren´ befindet sich zwischen den Adressen #26 bis #2D. Die Offsets der lokalen Variablen a, b und c relativ zum Workspace-Zeiger sind in diesem Beispiel jeweils 2, 1 und 0.
In den Listings zum PAR-Konstruktor sind P1, P2 und P3 jeweils die Fragmente #24-#2B, #2C-#31 und #32-#3D. Sie können nur durch die dem Konstruktor PAR entsprechende Befehlsfolge (#46-#63) gestartet werden, die folgendermaßen wirkt:
Dem Disassemblerlisting ist zu entnehmen, daß zunächst die letzte Guard eines ALT-Prozesses getestet wird. (Guards sind die formulierten Bedingungen, die über Ausführbarkeit eines Lesevorganges entscheiden.) Wenn mehrere Guards gleichzeitig ausführbar (vgl. [7, S. 130]) sind, wird immer die letzte davon ausgewählt. Diese Implementation weicht von Occams Sprachdefinition ab, die ein nichtdeterministisches Verhalten für diesen Fall vorsieht.
Der Konstruktor ALT wird als eine Befehlsfolge (#24-#3F) interpretiert, die grundsätzlich aus zwei Teilen besteht (#26-#2F und #32-#3D). Von #26 bis #2F werden alle Guards nacheinander getestet, ob sie ausführbar sind. Wenn keine Guard ausführbar ist, wird der ALT-Prozeß bis zum Befehl ALTWT (#30-#31) ausgeführt und aus der Warteschlange der zur Ausführung bereiten Prozesse herausgenommen - so lange - bis eine der Guards ausführbar wird.
Von #32 bis #3D werden alle Guards nochmals nach der dargestellten Reihenfolge durchgeprüft. Die zuerst angetroffene ausführbare Guard, das heißt die letzte im Quellprogramm, wird ausgewählt und ihre Sprungweite von ALTEND zum entsprechenden Zweig im Workspace abgespeichert (#35-#37 bzw. #3B-#3D). Aufgrund dieser Sprungweite verzweigt ALTEND zur ausgewählten ALTernative.
Den an der Assemblersprache des Transputers interessierten Lesern kann ich die Lektüre von [4, 5 und 2] empfehlen. In [4] wird die Wirkung aller Transputerbefehle für den T414, T212 und M212 grafisch dargestellt. [5] zeigt die Implementation von Occam auf dem Transputer und [2] beschreibt die Semantik der Befehle.
Zum Schluß möchte ich Herrn Detlef Feldmann und Herrn Frank Scherwa herzlichen Dank für ihre wichtigen Vorschläge und sprachlichen Verbesserungen sagen. (bb)
[2] Gerd Häußler, Die Assemblersprache des Transputers, mc, Juni 1988
[3] C. A. R. Hoare, Communicating Sequential Processes, Comm. ACM 21(8), 1978
[4] Inmos, T2/T4 transputer instruction set, (72 TRN 106 00), July 1986
[5] Inmos, The transputer instruction set - a compiler writers´ guide, (72 TRN 119 01), February 1987
[6] David May, Roger Shephard, Catherine Keane, Communicating Process Architecture: Transputer and Occam, Inmos April 1986
[7] Alois Schütte, Programmieren in Occam, Addison-Wesley, 1988
[8] Inmos, Transputer development system 2.0 Programming interface, (72 TDS 112 00) IMS D700 C / IMS D800 C, April 1987
[9] Inmos, Transputer development system 2.0 User manual, (72 TDS 110 00) IMS D700 C / IMS D800 C, April 1987
PROC Fakultaet(CHAN OF ANY keyboard, screen)
-- eine positive ganze Zahl n von der Tastatur einlesen
-- x = n! auf dem Bildschirm ausgeben
#USE "\tdsiolib\userio.tsr"
INT n, x, char, end:
SEQ
write.full.string(screen, "n = ")
read.echo.int(keyboard, screen, n, char)
-- n wird von der Tastatur eingelesen.
x := 1
SEQ i = 1 FOR n
SEQ
GUY -- x := x * i
LDL x -- lokale Variable x geladen
LDL i -- lokale Variable i geladen
MUL -- x mit i multipliziert
STL x -- Reg. A (= x * i) in x abgespeichert
write.full.string(screen, "x = ")
write.int(screen, x, 0)
-- x = n! wird auf dem Bildschirm gezeigt.
keyboard ? end
:
Kasten 2
PROC addieren(CHAN OF ANY keyboard, screen)
INT a, b, c:
SEQ
a := 4
b := 5
c := a + b
:
00000000: 00 J 00000000 ; jump
00000001: 00 J 00000000 ; jump
00000002: 00 J 00000000 ; jump
00000003: 0E J 0000000E ; jump
00000004: 6162636465666768696A6B6C6D6E6F70 LDL 6A4C2E00;
load local
00000014: 71 LDL 00000001 ; load local
00000015: 72 LDL 00000002 ; load local
00000016: 73 LDL 00000003 ; load local
00000017: 74 LDL 00000004 ; load local
00000018: 75 LDL 00000005 ; load local
00000019: 76 LDL 00000006 ; load local
0000001A: 77 LDL 00000007 ; load local
0000001B: 78 LDL 00000008 ; load local
0000001C: 79 LDL 00000009 ; load local
0000001D: 7A LDL 0000000A ; load local
0000001E: 7B LDL 0000000B ; load local
0000001F: 7C LDL 0000000C ; load local
00000020: 00 J 00000000 ; jump
00000021: 00 J 00000000 ; jump
00000022: 00 J 00000000 ; jump
00000023: 05 J 00000005 ; jump
00000024: 60BD AJW FFFFFFFD ; adjust workspace
00000026: 44 LDC 00000004 ; load constant
00000027: D2 STL 00000002 ; store local
00000028: 45 LDC 00000005 ; load constant
00000029: D1 STL 00000001 ; store local
0000002A: 72 LDL 00000002 ; load local
0000002B: 71 LDL 00000001 ; load local
0000002C: F5 ADD ; add
0000002D: D0 STL 00000000 ; store local
0000002E: B3 AJW 00000003 ; adjust workspace
0000002F: 22F0 RET ; return
00000031: 50 LDNLP 00000000 ; load non-local pointer
00000032: 50 LDNLP 00000000 ; load non-local pointer
00000033: 50 LDNLP 00000000 ; load non-local pointer
00000034: 00 J 00000000 ; jump
00000035: 00 J 00000000 ; jump
00000036: 00 J 00000000 ; jump
00000037: 2000 J 00000000 ; jump
00000038: 00 J 00000000 ; jump
00000039: 00 J 00000000 ; jump
0000003A: 00 J 00000000 ; jump
0000003B: 00 J 00000000 ; jump
Kasten 3
...
INT y, x:
CHAN OF INT k1, k2:
PAR
-- P1
k1 ? y
-- P2
k2 ! 10
-- P3
SEQ
k1 ! 5
k2 ? x
...
---------- P1 ---------- -- k1 ? y 24: 70 LDL 0 25: 55 LDNLP 5 -- Adresse von y geladen 26: 70 LDL 0 27: 53 LDNLP 3 -- Adresse von k1 geladen
28: 44 LDC 4 -- 4 Bytes Nachrichten 29: F7 IN -- eingeben -- P1 endet 2A: 11 LDLP 1 -- WS-PAR geladen 2B: F3 ENDP -- P1 beendet ---------- P2 ---------- -- k2 ! 10 2C: 71 LDL 1 2D: 52 LDNLP 2 -- Adresse von k2 geladen
2E: 4A LDC #A -- Konstante 10 (dez.) geladen 2F: FF OUTWORD -- ein Wort ausgeben -- P2 endet 30: 16 LDLP 6 -- WS-PAR geladen 31: F3 ENDP -- P2 beendet ---------- P3 ---------- -- k1 ! 5 32: 71 LDL 1 33: 53 LDNLP 3 -- Adresse von k1 geladen
34: 45 LDC 5 -- Konstante 5 geladen 35: FF OUTWORD -- ein Wort ausgeben -- k2 ? x 36: 71 LDL 1 37: 54 LDNLP 4 -- Adresse von x geladen
38: 71 LDL 1 39: 52 LDNLP 2 -- Adresse von k2 geladen
3A: 44 LDC 4 -- 4 Bytes Nachrichten 3B: F7 IN -- eingeben -- P3 endet 3C: 1B LDLP 11 -- WS-PAR geladen 3D: F3 ENDP -- P3 beendet
---------- Befehlsfolge des Konstruktors PAR ---------- -- Anfang von PAR 46: 43 LDC 3 -- Anzahl der par. lauf. Prozesse ist 3 47: D1 STL 1 -- und wird mit Offset 1 abgespeichert
48: 2148 LDC #18
4A: 21FB LDPI
4C: D0 STL 0 -- #64 (=#4C+#18) Nachfolgeadr. von PAR
-- mit Offset 0 abgespeichert, d.h.
-- nach Terminieren von PAR laeuft
-- das Programm ab #64 weiter
-- P1 gestartet 4D: 10 LDLP 0 -- WS-PAR geladen 4E: 60DF STL -1 -- mit Offset -1 abgespeichert
50: 634F LDC -#31
52: 601F LDLP -1
54: FD STARTP -- P1 gestartet, Anfangsadr. ist #24
-- (=#55-#31), Workspace-Zeiger WS-P1
-- hat Offset -1 relativ zu WS-PAR.
-- P2 gestartet
55: 10 LDLP 0 -- WS-PAR geladen
56: 60DB STL -5 -- mit Offset -5 abgespeichert
58: 634F LDC -#31
5A: 601A LDLP -6
5C: FD STARTP -- P2 gestartet, Anfangsadr. ist #2C
-- (=#5D-#31), Workspace-Zeiger WS-P2
-- hat Offset -6 relativ zu WS-PAR.
-- P3 gestartet
5D: 10 LDLP 0 -- WS-PAR geladen
5E: 60D6 STL -#A -- mit Offset -#A abgespeichert
60: 60B5 AJW -#B -- Workspace-Zeiger WS-P3 hat Offset
-- -#B relativ zu WS-PAR
62: 630E J -#32 -- zu #32 (=#64-#32) Anfangsadr. von
-- P3 springen, P3 gestartet
---------- Nachfolge des gesamten PAR-Prozesses ----------
64:
Kasten 4
...
INT x:
CHAN OF INT ein1, ein2, aus:
PAR
ALT
ein1 ? x
aus ! 1
ein2 ? x
aus ! 2
...
---------- Befehlsfolge des Konstruktors ALT ----------
-- Anfang von ALT
24: 24F3 ALT -- ALT-Anfangszustand MinInt+1
-- im Workspace abgespeichert
-- Guard2 (ein2 ? x) getestet, ob schon zur Komm. bereit
26: 71 LDL 1
27: 53 LDNLP 3 -- Adresse von ein2 geladen
28: 41 LDC 1 29: 24F8 ENBC -- Komm.Zustand von ein2 getestet
-- Guard1 (ein1 ? x) getestet, ob schon zur Komm. bereit 2B: 71 LDL 1 2C: 54 LDNLP 4 -- Adresse von ein1 geladen
2D: 41 LDC 1 2E: 24F8 ENBC -- Komm.Zustand von ein1 getestet
30: 24F4 ALTWT -- warten, wenn kein Proz. bereit ist,
-- ueber ein1/ein2 Nachrichten zu senden.
-- Guard2 getestet, ob mittlerweile zur Komm. bereit
32: 71 LDL 1
33: 53 LDNLP 3 -- Adresse von ein2 geladen
34: 41 LDC 1
35: 4B LDC B -- B ist die Sprungweite
-- von ALTEND zu Zweig 2
36: 22FF DISC -- Komm.Zustand von ein2 getestet
-- Guard1 getestet, ob mittlerweile zur Komm. bereit 38: 71 LDL 1 39: 54 LDNLP 4 -- Adresse von ein1 geladen
3A: 41 LDC 1
3B: 40 LDC 0 -- 0 heisst kein Sprung
-- von ALTEND zu Zweig 1
3C: 22FF DISC -- Komm.Zustand von ein1 getestet
3E: 24F5 ALTEND -- ALT beendet, nach dem Testergebnis zu
-- dem ausgewaehlten Zweig springen
---------- Zweig 1 ----------
-- ein1 ? x
40: 71 LDL 1
41: 55 LDNLP 5 -- Adresse von x geladen
42: 71 LDL 1 43: 54 LDNLP 4 -- Adresse von ein1 geladen
44: 44 LDC 4 -- 4 Bytes Nachrichten 45: F7 IN -- eingeben -- aus ! 1 46: 71 LDL 1 47: 52 LDNLP 2 -- Adresse von aus geladen
48: 41 LDC 1 -- Konstante 1 geladen 49: FF OUTWORD -- ein Wort ausgeben
4A: 0A J A -- zu #55 (=#4B+#A) springen
---------- Zweig 2 ---------- -- ein2 ? x 4B: 71 LDL 1 4C: 55 LDNLP 5 -- Adresse von x geladen
4D: 71 LDL 1 4E: 53 LDNLP 3 -- Adresse von ein2 geladen
4F: 44 LDC 4 -- 4 Bytes Nachrichten 50: F7 IN -- eingeben -- aus ! 2 51: 71 LDL 1 52: 52 LDNLP 2 -- Adresse von aus geladen
53: 42 LDC 2 -- Konstante 2 geladen 54: FF OUTWORD -- ein Wort ausgeben ---------- Nachfolge des gesamten ALT-Prozesses --- 55: