EREW-Pram Algorithmus < Technische Inform. < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:22 Di 04.05.2004 | | Autor: | Gloomer |
Hi zusammen.....
nachdem es in Mathe ja mittlerweile bei mir gut läuft ( Gott und lernen sei Dank :D) hab ich nun mal ein etwas anderes Problem.
Und zwar muss ich einen Algorithmus für eine EREW-Pram Maschine schreiben, die das Boolesche ODER berechnet für n Ausdrücke mit Hilfe von nur n/2 Prozessoren.....
ich hab bis jetzt echt nur das UND hinbekommen und hab mal wieder nen Brett vorm Kopp.... ich häng den Algorithmus für das UND mal hier rein, damit ihr ne Starthilfe habt :D
Algorithmus UND <EREW-PRAM>
{ berechnet das boolesche UND in O(n/N + log N) Schritten}
global: A: array[0..n-1] of boolean
U: boolean;
n: integer;
local: N, p: integer {initialisiert}
count,i: Integer;
u: boolean;
n_lokal: integer
begin
{O(log N):}
n_lokal:=get(n) with Algorithmus ReadX {
Algorithmus ReadX <EREW-PRAM>
{ liest X nach x in O(log N)}
global: A: array[0..n-1] of integer; {A[0] = X}
local: N, p: integer; {initialisiert}
x,count: integer;
begin
if (p<1) then { p0}
x:= A[0]; {read A0}
if (1<=p<2) then { p1}
x:= A[p-0]; {read A0}
else if (p<1) then {p0}
A[1]:= x; {A1 write}
if (2<=p<4) then { p2,p3}
x:= A[p-1]; {read A0,A1}
else if (p<2) then {p0,p1}
A[p+2]:= x; {A2,A3 write}
{WrittenCount= 4 {A0..A3}}
{=ReadCount=4 {p0..p3}}
{=:count}
for (count:=16; count*2 < N; count:=count*2) do
if (count <= p < count*2) then {p[count]..p[count*2-1]}
x:= A[p-count]; {read A[0]..A[count-1]}
else if (p<count) then {p[0]..p[count-1]}
A[p+count]:= x; {A[count]..[count*2-1]}
if (count <= p < N) then {p[count]..p[count*2-1]}
x:= A[p-count]; {read A[0]..A[count-1]}
end.};
{O(n/N):}
u:=A[p];
for i:=0 to n_lokal/N do
u:= u AND A[p*n_lokal div N+i];
A[p]:=u; {A[0]..A[N-1] enthalten die Verknüpfungen}
{O(log N):}
for count:=0 to log N do
{if [mm] p
A[p]:=A[p*2] AND A[p*2+1];
if p=0 then
U:=A[0]
end.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:51 Mi 05.05.2004 | | Autor: | Paulus |
Hallo gloomer
ich verstehe zwar dein Programm nicht so ganz (die Bedeutung von p kenne ich nicht so genau, auch verstehe ich nicht, warum bei der for-Schleife mit 16 begonnen wird, und hier:
if (1<=p<2) then { p1}
x:= A[p-0]; {read A0}
sollte es meiner Meinung nach auch eher so heissen:
if (1<=p<2) then { p1}
x:= A[p-0]; {read A1}
(oder ist das gemeint?:
if (1<=p<2) then { p1}
x:= A[p-1]; {read A0}
Auch verstehe ich nicht, wann eine geschweifte Klammer als Kommentar gilt, und wann nicht.
Aber wie dem auch sei, falls dein Algorithmus wirklich getestet ist und das korrekte Resultat liefert, so glaube ich, dass für das ODER lediglich die neuntletzte Zeile
u:= u AND A[p*n_lokal div N+i];
durch
u:= u OR A[p*n_lokal div N+i];
ersetzt werden muss.
ich hoffe, ich irre mich nicht. Ich setze den Status der Frage jedenfalls auf "teilweise beantwortet, damit auch noch Andere auf die Frage aufmerksam werden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:01 Mi 05.05.2004 | | Autor: | Gloomer |
hi und danke erstmal paulus für deine antwort.... werde deinen tip mal einbauen und sehn ob es klappt....
zu den andern sachen:
die for scheleife beginnt bei 16 weil.... weiss auch net :) war irgendwie aus der aufabenstellung zu entnehmen, musst ich auch erst drauf kommen....
das mit den geschweiften klammern scheint ein copy/paste fehler zu sein... normalerweise sind die für kommentare gedacht...
und dann natürlich die sache mit dem A0 lesen :) da hab ich mich tatsächlich vertippt und p-1 ist natürlich korrekt ;)
ich melde mich nochmal wenn es geklappt hat alles zu verbauen
cya
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:43 Mi 05.05.2004 | | Autor: | Marc |
Hallo gloomer!
> Hallo gloomer
>
> ich verstehe zwar dein Programm nicht so ganz (die
> Bedeutung von p kenne ich nicht so genau, auch verstehe ich
> nicht, warum bei der for-Schleife mit 16 begonnen wird, und
> hier:
Ja, ich kann mir auch nicht vorstellen, dass das Programm korrekt ist und out-of-the-box funktioniert (das soll wahrscheinlich ein theoretisches Programm sein, oder?)
> Aber wie dem auch sei, falls dein Algorithmus wirklich
> getestet ist und das korrekte Resultat liefert, so glaube
> ich, dass für das ODER lediglich die neuntletzte Zeile
>
> u:= u AND A[p*n_lokal div N+i];
>
> durch
>
> u:= u OR A[p*n_lokal div N+i];
>
> ersetzt werden muss.
Und --denke ich-- AND durch OR in der viertletzten Zeile ersetzen.
An dieser Stelle sollen ja wahrscheinlich die Teilergebnisse der n/2-Prozessoren zusammengesetzt werden (obwohl ich die Schleife auch nicht verstehe; da würde ich erwarten, dass der Schleifenrumpf irgendwie von "count" abhängt, so wird doch log(N) Mal dasselbe ausgeführt.
Noch zwei Anmerkungen:
a OR b = NOT (NOT(a) AND NOT(b))
So könnte man dein bestehendes Programm für AND bequem auch für OR benutzen.
Desweiteren kann auf die weitere Berechnung des Endergebnisses verzichtet werden, wenn es bereits feststeht:
True OR b = True
Das bedeutet: Wenn dein Zwischenergebnis bereits True ist, kann die Beachtung weiterer Operanden nicht mehr daran ändern.
Ähnliches gilt auch für AND:
False AND b = False
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:03 Mi 05.05.2004 | | Autor: | Gloomer |
jo, also.....
habe mal meinen tutor gefragt wegen der schleife.... der wusste auch net warum das auch so funktioniert ( hab ich halt mal glück gehabt ), er meinte aber da wäre egal, da es darauf nicht in der aufgabe ankam....
die von marc erwähnte zeile hatte ich beim neutippen auch entdeckt und umgeschrieben :D
der vorzeitige abbruch soll nicht passiern marc, da in der aufgabenstellung steht er soll ausnahmslos alle variablen testen.... find ich persönlich auch dumm aber egal.....
jedenfalls läuft er nun der algo...
thx
|
|
|
|
Das habe ich mir auch überlegt, aber in der späten Nacht wieder verschlafen. (gibt es kein Smily, das schläft?)
