Effiziente Möglichkeit, MIPS-Ausdruck zu berechnen

Question

Ich schreibe ein Programm für einen eingebetteten Computer und habe sehr wenig Arbeitsspeicher und Prozessorleistung.

y und a sind gespeichert verdoppelt in Gleitkommaregister und x ist ein Array von Doppel. Was ist der effizienteste Weg, um diesen Ausdruck in MIPS zu schreiben?

y = y + a * x[i]; 

Answer 1

ich in MIPS-Assembler nicht fließend bin, so werde ich mit dem tatsächlichen MIPS Anweisungen nicht stören, ich so etwas wie normale Englisch auf halbem Weg zu z80 verwenden/x86 TASM, hoffentlich werden Sie bekommen die Idee.

Und ich nehme an, dass Sie ein ganzes Array hinzufügen möchten, nicht nur diese einzelne Zeile, denn das ändert alles über die Aufgabe.

Wenn Sie wirklich nur diese einzelne Linie optimieren möchten, gibt es wenig Platz, um es auszustatten. Lade einfach x [i], multipliziere es mit a und füge das Ergebnis zu y hinzu.

Wenn Sie über eine bestimmte Größe Array (wie Größe 4 in Matrizen) sprechen, kann es einige direkte abgerollt Weg, es schneller als die folgende Sache von mir zu tun.

Wenn wir über einige Array sprechen, das ist etwas anderes (aber man sollte es so gebucht haben), können Sie viele speichern (n-1) Multiplikationen durch die x-Array Summieren zuerst:

load r1, x_array_pointer 
    load r2, x_array_end_pointer 
    load fpr0, zero_value 
:loop_sum_x_array 
    add fpr0,[r1] 
    add r1,size_of_double 
    cmp r1,r2 
    jump_less loop_sum_x_array ; till whole array is summed 
    mul fpr0, *a* ; now multiply sum{x} by "a" 
    add fpr0, *y* ; and add initial "y" value 
    ; fpr0 contains result 

"Algorithmus": y + a * x0 + a * x1 + a * x2 + ... = y + a * (x0 + x1 + x2 + ...) (Wenn Sie nicht haben dieses alleine, bevor du bei SO geschrieben hast, du hast es entweder gar nicht versucht, oder du bist 8 Jahre alt, oder du solltest ernsthaft etwas nachdenken und einfache mathematische Übungen machen, weil das offensichtlich ist tatsächlich, bei diesem Schwierigkeitsgrad ist es purer Spaß, warum lässt du andere bei SO leben deins Spaß? Sie sind sehr großzügig, mein Herr. :))

Speicher: dies keinen zusätzlichen Speicher nicht verwendet, nur die Eingabe y, ein und x, müssen Sie einige temporäre Register (R1, R2, fpr0) (so lange, wie Sie nicht 8bit CPU-Übung tun, sollten Sie genug von Ersatz dafür haben).

Rechenleistung: Komplexität des Algorithmus ist O (n) (und da Sie jeden Wert von X-Array hinzufügen müssen, können Sie nicht schlagen). Die innere Schleife verwendet ziemlich grundlegende Anweisungen: eine Gleitkomma-Addition, eine Ladung mit einem Doppelwert aus dem Speicher, eine Adresseninkrementierung, einen Vergleich und einen bedingten Sprung. Dann braucht es buchstäblich ein Fließkomma-Multiplikation und eine weitere fp-Addition. Auf das x-Array wird sequentiell zugegriffen, so dass Speicher-Cache-Misses minimal sein sollten.

Wenn Ihre CPU spezielle Anweisungen wie MMX hat, kann die Summe für große Arrays wahrscheinlich schneller geschrieben werden, indem diese verwendet werden. Aber bei moderner CPU + RAM für große Arrays wird man meistens durch die Speicher-Cache-Geschwindigkeit begrenzt, da diese innere Schleife für die GHz-CPU nicht existiert (außer dem Laden des Wertes aus dem Speicher natürlich).

edit: wie Michael bemerkt, mit C-Compiler ist der richtige Weg, ich habe meine Antwort nur zum Spaß des Schreibens einige Pseudo-Assembler. Ich bin mir nicht sicher, was Ihre Plattform ist, aber wenn es etwas wert ist, muss es einen Cross-Compiler für PC plus Weg geben, um das binäre Ergebnis zum Ziel zu bekommen.