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: