Rekursion vs. Iteration

[negaH]

Zitat:

Letztlich arbeitet eine (jede?!) CPU sogar nur sequentiell.

Das ist eine Definitionsfrage. CPU=Central Processing Unit=Zentrale Recheneinheit. Wenn wir von einem Rechner=Computer ausgehen so ist die CPU der Kernbestandteil. Dieser könnte ein ASIC aber auch FPGA oder sogar ein ASIC mit internem FPGA sein. FPGAs arbeiten per se erstmal alles in parallel ab und nicht sequientiell. Wenn sequientiell dann weil es der Programmierer mit Hilfe eines Taktes so programmiert hat. Dh. relevante Teile eines Algorithmus können sehr wohl nicht-sequientiell also parallel ausgeführt werden.

Ergo: aus Sicht "Rekurson vs. Iteration", als Schreibweise eines Algorithmus in einer Programmiersprache, kann eine CPU diesen sehr wohl sequentiell wie eben auch nicht-sequentiell abarbeiten.

Beispiel: ein Algorithmus der auf der Boolschen Algebra basiert. Formal schreibt man diesen als Rekursive Formel und programmiert diesen auch exakt so in einem FPGA, in rekursiver Schreibweise. Die Synthese=Compiler, zerlegt diese Formel mit Hilfe der Boolschen Algebra über Matrizen in vollständig definiert Boolsche Ausdrücke. Daraus entsteht dann eine Verschaltung von elektronischen Gattern innerhalb des FPGAs. Man beschreibt also rekursiv das Verhalten einer Hardware. Obwohl also das Problem rekursiv formuliert wurde arbeitet die Elektronik im Zielsystem alles in parallel ab. Damit exitieren also keine Sprungbefehle, keine einzeln nacheinander abzuarbeitenden Befehlssequenzen und somit auch kein Stackframe und finally somit keine Benachteiligung in der Peformance und Resourcen der Schreibweisen "rekursiv vs. iterativ" eines Algos.

Gruß Hagen

[idefix2]

Zitat:

Beispiel: ein Algorithmus der auf der Boolschen Algebra basiert. Formal schreibt man diesen als Rekursive Formel und programmiert diesen auch exakt so in einem FPGA, in rekursiver Schreibweise

Also darunter kann ich mir überhaupt nichts vorstellen. Könntest Du mit einem Beispiel illustrieren, was du meinst?

Zitat:

Wobei der Mechanismus der Rekursion fest in den Prozessor verankert ist ( Stack)

Der Hardwarestack wird von rekursiven Prozedure verwendet, ebenso wie von nicht rekursiven Prozeduren. Der Stack selbst hat mit Rekursion nichts zu tun, sondern nur mit Prozeduraufrufen. Deshalb brauchen natürlich auch rekursive Prozeduren einen Stack.

[negaH]

Code:

  function XorVectorBits(Bits: std_logic_vector, Index: integer) return std_logic;
  variable 
    Result: std_logic;
  begin
    Result := Bits(Index);
    if Index < Bits'High then
      Result := Result xor XorVetorBits(Bits, Index +1);
    end if;
    return Result;
  end function; 

  function XorVextorBits(Bits: std_logic_vector) return std_logic;
  variable 
    Result: std_logic;
    Index: Intger;
  begin
    Result := '0';
    for Index in Bits'Range loop
      Result := Result xor Bits(Index);
    end loop;    
    return Result;
  end function;

Oben sieht man zwei Funktionen in VHDL, erstere ist rekusiv die zweite nutzt eine Schleife. Beide beschreiben ein Verhalten einer späteren Hardware.

Das Signal Bits stellt man sich zb. wie ein Datenbus vor der aus zb. 16 Datenleitungen besteht. Die Boolsche Funktion lautet in Worten: Verknüpfe alle Datenleitungen in Bits per XOR und gebe das Resultat, ein Bit, zurück.

Beides wird bei der Synthese in Hardware exakt identische Resultate erzeugen. Nämlich ein XOR Gatter mit Bits'Range Inputs und einem Output.

Ok, es dürfte klar sein das das ein sehr enfaches Beispiel ist und hier der Vorteil in der formalen Schreibweise einer Rekursion noch nicht zum tragen kommt.

Gruß Hagen

[idefix2]

Ich muss zugeben, dass mich das verblüfft. Ich hätte nicht geglaubt, dass es im wirklichen Leben tatsächlich Systeme gibt, die derartige rekurive Strukturen als Eingabe hernehmen und die Rekursion in parallel arbeitende Harware auflösen.

[negaH]

Denke mal drüber nach warum ich in diesem Thread immer wieder betone das das nur eine Form einer Schreibweise ist und eben nicht direkt im Zusammenhang mit irgendwas Realem, wie eben Hardware, steht.

Rekursiv vs. Iterativ ist eine Frage der Schreibweise eines Algorithmus. Es ist nicht der Algorithmus selber noch dessen praktische Realisierung in Hardware.

Man muß immer strikt abstrahieren und eine Frage, je nach gewünschter Sichtweise, beantworten.

Bei "Rekursv vs. Iterativ" gilt erstmal das es da keinen Unterschied geben kann in der Performance und Speicherverbrauch. Erst wenn man die benutzte Hardware oder Softwaretools berücksichtig ändert sich die Antwort, bzw. erst dann macht es Sinn den Speicherverbrauch/Performance als Entscheidungskriterium heran zu ziehen. Aber..., dann bewertet man nicht mehr "Rekursiv vs. Iterartiv" sondern defakto die Fähigkeiten der btrachteten Softwaretools und Hardware, wie sie die unterschiedlichen Schreibweisen eines Algorithmus umzusetzen in der Lage sind.

Wer also behauptet: Rekursiv sei oft langsammer als Iterativ in der Performance oder eben mehr Speicher verbraucht auf Grund eines notwendigen Stackframes, der bewertet einen ASIC als Hardware, und eben nicht mehr objektiv zwei Schreibweisen eines Algos.

Gruß Hagen