Welcher Mindestbefehlssatz ist erforderlich, damit eine Assemblersprache als nützlich gilt?

StackOverflow https://stackoverflow.com/questions/9439001

Frage

Ich studiere Assembler-Programmierung im Allgemeinen und habe daher beschlossen, einen „virtuellen Mikroprozessor“ in Software zu implementieren, der über Register, Flags und RAM verfügt, mit denen gearbeitet werden kann, implementiert mit Variablen und Arrays.Da ich aber simulieren möchte nur das grundlegendste Verhalten eines Mikroprozessors, möchte ich eine Assemblersprache erstellen, die nur die wesentlichen Anweisungen enthält, nur die Anweisungen, ohne die sie nicht nützlich wäre.Ich meine, es gibt Assemblersprachen, die Multiplikationen und den Austausch von Registerwerten usw. durchführen können, aber diese Operationen sind nicht grundlegend, da Sie sie mit einfacheren Anweisungen implementieren können.Ich möchte solche Anweisungen nicht umsetzen.

Ich kann mir ein paar Anweisungen vorstellen, die (glaube ich) in jeder Assemblersprache immer vorhanden sein müssen, z MOV Bytes verschieben und JP um den Befehlszeiger an eine andere Adresse zu senden.

Könnten Sie eine Reihe der grundlegendsten und wichtigsten Montageanleitungen vorschlagen?Danke!

War es hilfreich?

Lösung

Nun, das ist ein sehr breites Thema.Ich nehme an, Sie müssen sich mit zufällige Zugangsmaschine vertraut machen.Ich bin kein Experte, aber es ist schwer zu sagen, welche Anweisungen von diesem sehr grundlegenden Mikroprozessor unterstützt werden sollten.Zum Beispiel: Subtraktion und Multiplikation können durch Zugaboperation simuliert werden.Multiplikation ist möglich, wenn der Mikroprozessor Sprünge und bedingte Anweisungen unterstützt und die Subtraktion durch Hinzufügen von negativer Zahl möglich ist.

Andere Tipps

Steuerungsstrukturen umfassen das Basismerkmal, ohne das keine Sprache vorhanden ist. Dies bedeutet, dass Ihre Sprache arithmetische Vorgänge auf zwei Variablen liefern muss; und ermöglichen Sie dann ein Programm, den Programmzähler zu ändern - das heißt, basierend auf dem Ergebnis einer Operation. Sehr oft ist der entscheidende Betrieb sub, um einen Operanden von einem anderen zu subtrahieren. Und die Bedingungen, auf denen Sie einen Zweig erlauben würden, sind:

    .
  1. Ergebnis ist Null;
  2. Ergebnis ist größer als Null;
  3. Ergebnis ist weniger als Null.
  4. kein Zustand, d. H. Zweig bedingungslos

    Sie benötigen auch Anweisungen, um Daten zu verschieben: Laden und Laden, sagen Sie.

    Diese drei Bedingungen und deren entsprechenden Zweige (oder übersprungen, was eine andere Möglichkeit ist, es zu tun) sind für jedes Programm erforderlich. Nicht nur das, sondern nur diese drei einfachen Operationen plus Datenbewegungsanweisungen, reichen aus, um in einem Programm in einem Programm zu tun, außer E / A. Wenn Sie eine kooperierende Speicherorganisation gewünscht haben, können Sie Linux mithilfe von Last, Speichern, Hinzufügen, Sub und den drei bedingten Zweigen neu schreiben.

    Der PDP-8 war eine viel leistungsfähigere Maschine als dies: Es hatte ein Rich-Set von acht Anweisungen , einschließlich E / A.

    hth

Überraschenderweise gibt es so etwas wie ein ein Anweisungssatz-Computer .

Der geringste Befehlssatz erfordert keine Anweisung oder vielleicht Null-Anweisung.Ich weiß nicht, ob sie in echte Geräte gelangt sind oder nicht, aber das ein Befehlssatzcomputer (OISC) wurde implementiert und erfolgreich einlaufen Kohlenstoffnanoröhren-Computer Und MAXQ.

Tatsächlich kann x86 auch als OISC-Architektur verwendet werden, weil es ist möglich irgendetwas mit nur einer einzigen mov weil es so war erwies sich als Turing-vollständig.Es gibt sogar einen Compiler namens movfuscator um gültigen C-Code in ein Programm mit nur MOVs zu kompilieren (oder nur entweder XOR, SUB, ADD, XADD, ADC, SBB, AND/OR, PUSH/POP, 1-Bit-Verschiebungen oder CMPXCHG/XCHG)

Allerdings meiner Meinung nach eine Architektur sollte "schnell" genug sein (oder erfordern im Vergleich zu anderen Architekturen nicht zu viele Anweisungen wie OISC für eine Aufgabe) als nützlich erachtet werden.

Die grundlegendsten Befehlstypen für einen Computer sind Datenbewegungen, logische/arithmetische Operationen und Verzweigungen.Für arithmetische Operationen genügt ein add/subtract reicht.Aus logischen Gründen können wir beliebige Funktionen nur mit a berechnen NOR oder NAND, daher wird nur einer benötigt.Zum Springen brauchen wir einen jump on "<=" oder jump on "<" Anweisung.Datenbewegungen können durch Add/Sub emuliert werden.Auf diese Weise können wir 2 Bits verwenden, um 3 Opcodes zu kodieren (add, nand, jump on "<=") und lassen Sie eines für zukünftige Erweiterungen übrig.Aber da dies kein separates hat Anweisungen zum Laden/Speichern, muss es direkt mit einer großen Registerdatei statt mit dem Speicher arbeiten, oder die Anweisungen müssen die Möglichkeit haben, Speicher als Operanden zu verwenden.

Wenn mehr Geschwindigkeit benötigt wird, können etwas mehr Logik, Verzweigungsanweisungen und möglicherweise Laden/Speichern hinzugefügt werden, wodurch der Opcode-Speicherplatz auf 3 Bits erhöht wird.Der Befehlssatz kann sein:

  1. Belastung
  2. speichern
  3. hinzufügen
  4. Und
  5. noch
  6. Springe auf weniger als
  7. gleich aufspringen

Linksverschiebung ist möglich add Da die Rechtsverschiebung jedoch schwieriger ist, möchten Sie möglicherweise auch eine Rechtsverschiebung hinzufügen, um einige gängige Vorgänge zu vereinfachen

Mit einem minimalen Befehlssatz, der nur aus besteht, können Sie perfekt überleben SOB: subtrahiere eins und verzweige.Ganze Programme können und wurden damit geschrieben.

Schauen Sie sich kommerzielle Implementierungen an

Die beste Antwort dürfte ein Blick auf bestehende kommerzielle Implementierungen sein.

Alles, was nicht kommerziell verkauft wird, ist wahrscheinlich nicht nützlich.

Was ist die Definition einer Anweisung?

Ich könnte zum Beispiel eine Anweisung erstellen, die den Unzip-Algorithmus implementiert, basierend auf einer Hardware-Implementierung von unzip, und das wäre natürlich die effizienteste Maschine, die zum Entpacken möglich ist.

Wäre es jedoch kommerziell attraktiv?Unwahrscheinlich, da diese Hardware wahrscheinlich zu spezialisiert wäre, um die Entwicklungskosten zu rechtfertigen.

Aber es gibt viel nuanciertere Fälle als diesen Extremfall, und die Antwort wird wahrscheinlich mit der Zeit je nach bestehenden Konkurrenztechnologien und Marktnachfrage variieren, was die Sache noch schlimmer macht.

Unter „effizienter Hardware“ versteht man im Endeffekt:

  • Nehmen Sie eine Reihe von Benchmarks und weisen Sie jedem ein Wichtigkeitsgewicht zu
  • Schreiben Sie optimale Software, die diese Benchmarks löst

Mögliche Gründe, warum sehr kleine Turing-vollständige ISAs ineffizient sein können

  • Die wenigen Anweisungen, die sie haben, sind sehr komplex und verursachen bei jedem Aufruf hohe Kosten, z. B.Sie können bestimmte Pipeline-Optimierungen nicht durchführen
  • Die Codedichte ist sehr gering, was Folgendes impliziert:
    • Die Leistung kann durch das Abrufen von Anweisungen eingeschränkt sein
    • Nicht gut für eingebettete Geräte mit kleinem ROM-Speicher

Bemerkenswerte OISC-Implementierungen

Es wäre interessant, diese zu analysieren, um eine konkretere Antwort zu erhalten.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Toy C-Compiler für x86, der genau das verwendet mov x86-Anweisungen, die sehr konkret zeigen, dass eine einzelne Anweisung ausreicht.

Die Turing-Vollständigkeit scheint in einer Arbeit bewiesen worden zu sein: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

untergeordnet

Bildungs-OSIC, zuvor erwähnt unter https://stackoverflow.com/a/9439153/895245 aber ohne Namen:

Siehe auch:https://esolangs.org/wiki/Subleq

Siehe auch

https://softwareengineering.stackexchange.com/questions/230538/what-is-the-absolute-minimum-set-of-instructions-required-to-build-a-turing-comp/325501

theoretisch ist ein einzelner Anweisungscomputer möglich. Bei echter Hardware benötigen Sie jedoch ein Minimum von 4. Angenommen, die einzige Speicher-Architektur (keine vom Benutzer zugänglichen Register).

MOV MEM1 MEM2 - Kopieren Sie den Inhalt des Speicherplatzes MEM1 auf den Speicherplatz MEM2, der MEM1 unverändert verlässt

nand mem1 mem2 bis mem3- Führen Sie einen bitweise logischen Nand zwischen den Daten an MEM1 und MEM2 durch und schreiben Sie das Ergebnis an MEM3

Bitshiftr MEM1 MEM2 MEM3 BITSHIFT RECHTS Die Daten an MEM1 MEM2-Stellen und schreiben Sie den Ausgang an MEM3

jmpcond mem1 mem2 - testen Sie das am wenigsten signifikante Bit an MEM1 und wenn es true ist (1) Springe zu MEM2

Jetzt wird es nicht super schnell sein, und es wird die Speicherbandbreite wie verrückt essen, kann jedoch verwendet werden, um eine virtuelle Maschine mit einem beliebigen, beliebigen Anweisungssatz zu implementieren. Zusätzlich gibt es bestimmte Programmiereinschränkungen, wie die Notwendigkeit, in allen Startdaten zu programmieren, oder der höchsten Speicherort mit nur dem LSB-Set auf 1. Hardware-Peripheriegeräte müssen DMA für den E / A-Zugriff verwenden, und wenn auf a Harvard-Architektur Das Programm hat keinen direkten Zugriff auf Dinge wie Zeiger.

Sie möchten möglicherweise auch Vollständigkeit aufsuchen.

http://de.wikipedia.org/wiki/ting_completess

http://c2.com/cgi/wiki?turingComplete

Was ist das Turing Complete?

Es bedeutet, dass eine Sprache ausreicht, um etwas zu berechnen, das berechnet werden kann.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top