Zur Simulation von PRAM durch TM Nachfolgend sind einige wichtige Funktionen in Pseudocode aufgef¨ uhrt, die naheliegend so auf einer TM implementiert werden k¨onnen, dass deren Platzbedarf polynomiell im Zeitbedarf der PRAM ist. F¨ ur weitere, nur benutzte aber nicht definierte, Funktionen dr¨ uckt der Name hoffentlich deutlich genug aus, was sie jeweils tun. Man beachte, dass bei den diversen indirekten rekursiven Aufrufen der allen gemeinsame Parameter ”‘aktuelle betrachteter Zeitpunkt”’ t sp¨atestens bei jedem zweiten Aufruf um 1 dekrementiert wird. Die folgende Funktion check liefert als R¨ uckgabewert • true, falls es richtig ist, dass Prozessor p zum Zeitpunkt start gestartet wird und zum Zeitpunkt t Zeile l des Programms abarbeitet und der Akkumulatorinhalt danach a ist; • false sonst function bool check (proc p, time t, time start, line l , nat a) begin if (t < start) then return (false); fi if (t = start) then if (p = 0 and start = 0) then hder einfachste Fall: es muss l = 0 sein, usw.i ... elsif (p > 0 and start > 0) then return (findForker (p, start, l , a)); else handere F¨ alle sind unm¨ oglichi return (false); fi fi if (t > start) then hInformationen u ¨ber den vorangegangenen Schritt ermittelni (found , l 0 , a 0 ) ← findLineAccu(p, t − 1 , start) if not found then return (false); fi hKonsistenz des vorangegangenen Schritt mit dem aktuellen u ¨berpr¨ ufeni c1 ← checkLine(p, t, l 0 , a 0 , l ); c2 ← checkAccu(p, t, a 0 , l , a); return (c1 and c2 ); fi end 1 Die folgende Funktion findForker liefert als R¨ uckgabewert • true, falls es richtig ist, dass Prozessor p zum Zeitpunkt start in Zeile l des Programms gestartet wird und der Akkumulatorinhalt danach a ist. • false sonst function bool findForker (proc p, time start, line l , nat a) begin for p 0 ← p − 1 to 0 step −1 do for s 0 ← start − 1 to 0 step −1 do for a 0 ← 0 to n · alphSize t do if (checkAccu(p, start, a 0 , l , a)) then for l 0 ← each forkLineWithLabel (l ) do if (check (p 0 , start − 1, s 0 , l 0 , a 0 ) then return (true); fi od fi od od od return (false); end 2 Die folgende Funktion findLineAccu liefert als R¨ uckgabewert • (true, l, a), falls es richtig ist, dass Prozessor p zum Zeitpunkt start gestartet wird und zum Zeitpunkt t aktiv ist. Es ist dann l die zum Zeitpunkt t aktuelle Zeilennummer und a anschließend der Akkumulatorinhalt. • (false, 1, 0) sonst function (bool,line,nat) findLineAccu (proc p, time t, time start) begin found ←false; for a 0 ← 0 to n · alphSize t do for l 0 ← 1 to maxLines do found ← check (p, t, start, l 0 , a 0 ); if (found ) then return (true, l 0 , a 0 ) fi od od return (false, 1, 0); end 3 Die folgende Funktion checkLine liefert als R¨ uckgabewert • true, falls es richtig ist, dass Prozessor p zum Zeitpunkt t aktiv war, sich in Zeile l0 befand, der Akkumulatorinhalt a0 ist und die Nummer der als n¨achstes auszuf¨ uhrenden Zeile l ist. • false sonst function bool checkLine (proc p, time t, line l 0 , nat a 0 , line l ) begin c1 ← (instrInLine(l 0 ) 6= jump) and (instrInLine(l 0 ) 6= jzero or a 0 6= 0) and (l = l 0 + 1); c2 ← ((instrInLine(l 0 ) = jump) or (instrInLine(l 0 ) = jzero and a 0 = 0)) and (jumpLabelInLine(l 0 ) = l ); if (c1 or c2 ) then return (true); else return (false); fi end 4 Die folgende Funktion checkAccu liefert als R¨ uckgabewert • true, falls es richtig ist, dass Prozessor p zum Zeitpunkt t aktiv war, sich in Zeile l befand, vor Ausf¨ uhrung des Befehls der Akkumulatorinhalt a0 ist und nach der Ausf¨ uhrung a. • false sonst function bool checkAccu (proc p, time t, nat a 0 , line l , nat a) begin case instrInLine(l ) of jump: return (a 0 = a); loadDirectGlobal : adr ← extractAdr (l ); for t 0 ← t − 1 step −1 do 0 for p 0 ← 0 to 2t do if checkGlobalWriteOccurs(p 0 , t 0 , adr ) then goto found fi od od found : . . . husw. wie Buch, Seite 78 unteni hdie weiteren Kombinationen von Befehlen und Adressierungsarteni h werden hier nicht aufgef¨ uhrti ... esac end 5