Computer mit einem Befehlssatz - One-instruction set computer

Ein Ein-Befehlssatz-Computer ( OISC ), manchmal auch als ultimativer Computer mit reduziertem Befehlssatz ( URISC ) bezeichnet, ist eine abstrakte Maschine , die nur einen Befehl verwendet – wodurch ein Maschinensprachen- Opcode überflüssig wird . Mit einer umsichtigen Wahl für den einzelnen Befehl und gegebenen unendlichen Ressourcen ist ein OISC in der Lage, ein universeller Computer auf die gleiche Weise wie herkömmliche Computer mit mehreren Befehlen zu sein. OISCs wurden als Hilfsmittel beim Unterrichten von Computerarchitekturen empfohlen und wurden als Rechenmodelle in der Structural Computing-Forschung verwendet.

Während 1-Bit- CPUs ansonsten veraltet sind (und keine OISCs waren), ist der erste Kohlenstoff-Nanoröhrchen-Computer ein 1-Bit-Computer mit einem Befehlssatz (und hat nur 178 Transistoren).

Maschinenarchitektur

In einem Turing-vollständigen Modell kann jede Speicherstelle eine beliebige ganze Zahl speichern, und – je nach Modell – beliebig viele Stellen. Die Befehle selbst befinden sich im Speicher als Folge solcher Ganzzahlen.

Es existiert eine Klasse von Universalcomputern mit einem einzigen Befehl basierend auf Bitmanipulation, wie beispielsweise Bitkopieren oder Bitinversion . Da ihr Speichermodell ebenso wie die in realen Computern verwendete Speicherstruktur endlich ist, entsprechen diese Bit-Manipulationsmaschinen eher realen Computern als Turing-Maschinen.

Derzeit bekannte OISCs können grob in drei große Kategorien unterteilt werden:

• Bit-Manipulationsmaschinen
• Durch Transport ausgelöste Architekturmaschinen
• Arithmetik-basierte Turing-vollständige Maschinen

Bit-Manipulationsmaschinen

Bit-manipulierende Maschinen sind die einfachste Klasse.

FlipJump

Die FlipJump- Maschine hat 1 Anweisung, a;b - dreht das Bit a um und springt dann zu b. Dies ist das primitivste OISC, aber es ist immer noch nützlich. Es kann mit Hilfe seiner Standardbibliothek erfolgreich mathematische / logische Berechnungen, Verzweigungen, Zeiger und Aufruffunktionen durchführen.

BitBitJump

Ein Bit-Kopiergerät namens BitBitJump kopiert ein Bit in den Speicher und übergibt die Ausführung bedingungslos an die von einem der Operanden des Befehls angegebene Adresse. Es stellt sich heraus, dass dieser Prozess universell rechnen kann (dh jeden Algorithmus ausführen und jede andere universelle Maschine interpretieren kann), da das Kopieren von Bits den Code, der nachfolgend ausgeführt wird, bedingt modifizieren kann.

Toga-Computer

Eine andere Maschine namens Toga Computer invertiert ein wenig und übergibt die Ausführung abhängig vom Ergebnis der Inversion bedingt. Die eindeutige Anweisung TOGA (a, b) , die für steht TOG GLE a A nd Zweig b , wenn das Ergebnis der Kippoperation wahr ist.

Multi-Bit-Kopiergerät

Ähnlich wie bei BitBitJump kopiert ein Multi-Bit-Kopiergerät mehrere Bits gleichzeitig. Das Problem der rechnerischen Universalität wird in diesem Fall dadurch gelöst, dass vordefinierte Sprungtabellen im Speicher gehalten werden.

Transport-getriggerte Architektur

Transport Triggered Architecture (TTA) ist ein Design, bei dem die Berechnung ein Nebeneffekt des Datentransports ist. Normalerweise führen einige Speicherregister (Triggerports) innerhalb des gemeinsamen Adressraums eine zugewiesene Operation aus, wenn der Befehl auf sie verweist. Beispielsweise erfolgt dies in einem OISC, der einen einzelnen Speicher-zu-Speicher-Kopierbefehl verwendet, durch Triggern von Ports, die beim Beschreiben arithmetische und Befehlszeigersprünge ausführen.

Arithmetik-basierte Turing-vollständige Maschinen

Auf Arithmetik basierende Turing-vollständige Maschinen verwenden eine arithmetische Operation und einen bedingten Sprung. Wie die beiden vorherigen Universalcomputer ist auch diese Klasse Turing-komplett. Der Befehl arbeitet mit ganzen Zahlen, die auch Adressen im Speicher sein können.

Derzeit sind mehrere OISCs dieser Klasse bekannt, die auf unterschiedlichen arithmetischen Operationen basieren:

• Zugabe (addleq, hinzuzufügen und Zweig wenn l ess als oder eq UAL Null)
• Dekrement (DJN, D ecrement und Zweig ( J UMP) , wenn N onzero)
• increment (P1eq, P lus 1 und Verzweigung , falls eq UAL auf einen anderen Wert)
• Subtraktion (subleq, sub - Darm - Trakt und Zweig wenn l ess als oder eq UAL Null)
• positive Subtraktion, wenn möglich, sonst Verzweigung (Rechenmaschine)

Befehlstypen

Häufige Auswahlmöglichkeiten für den Einzelbefehl sind:

• Subtrahieren und verzweigen, wenn kleiner oder gleich Null
• Subtrahiere und verzweige wenn negativ
• Subtrahiere, wenn positiv, sonst Zweig
• Umgekehrt subtrahieren und überspringen, wenn borgen
• Verschieben (wird als Teil einer durch Transport ausgelösten Architektur verwendet)
• Subtrahieren und verzweigen, wenn nicht Null (SBNZ a, b, c, Ziel)
• Cryptoleq (heterogene verschlüsselte und unverschlüsselte Berechnung)

In einer gegebenen Implementierung wird nur einer dieser Befehle verwendet. Daher besteht keine Notwendigkeit für einen Opcode, um zu identifizieren, welcher Befehl ausgeführt werden soll; die Wahl des Befehls liegt in der Konstruktion der Maschine, und ein OISC wird typischerweise nach dem von ihm verwendeten Befehl benannt (z. B. ein SBN-OISC, die SUBLEQ-Sprache usw.). Jede der obigen Anweisungen kann verwendet werden, um eine Turing-vollständige OISC zu konstruieren.

In diesem Artikel werden nur subtraktionsbasierte Anweisungen unter denen vorgestellt, die nicht durch den Transport ausgelöst werden. Es ist jedoch möglich, vollständige Turing-Maschinen unter Verwendung einer Anweisung zu konstruieren, die auf anderen arithmetischen Operationen, zB Addition, basiert. Beispielsweise hat eine als DLN (Decrement and jump if not zero) bekannte Variante nur zwei Operanden und verwendet die Dekrementierung als Basisoperation. Weitere Informationen finden Sie unter abgeleitete Subleq-Sprachen [1] .

Subtrahiere und verzweige wenn ungleich Null

Der SBNZ a, b, c, d Befehl (" subtrahieren und verzweigen, wenn ungleich Null ") subtrahiert den Inhalt an Adresse a vom Inhalt an Adresse b , speichert das Ergebnis an Adresse c und überträgt dann, wenn das Ergebnis nicht 0 ist , die Steuerung an Adresse d ( wenn das Ergebnis gleich Null ist, geht die Ausführung zum nächsten Befehl in Folge).

Subtrahieren und verzweigen, wenn kleiner oder gleich Null

Der subleq- Befehl (" subtrahieren und verzweigen, wenn kleiner oder gleich Null ") subtrahiert den Inhalt an Adresse a vom Inhalt an Adresse b , speichert das Ergebnis an Adresse b und überträgt dann, wenn das Ergebnis nicht positiv ist , die Steuerung an Adresse c (wenn das Ergebnis positiv ist, geht die Ausführung zum nächsten Befehl in Folge). Pseudocode :

Instruction subleq a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] ≤ 0)
        goto c

Bedingte Verzweigung kann unterdrückt werden, indem der dritte Operand gleich der Adresse des nächsten Befehls in Folge gesetzt wird. Wenn der dritte Operand nicht geschrieben wird, wird diese Unterdrückung impliziert.

Auch eine Variante mit zwei Operanden und einem internen Akkumulator ist möglich , wobei der Akkumulator von dem durch den ersten Operanden angegebenen Speicherplatz abgezogen wird. Das Ergebnis wird sowohl im Akkumulator als auch im Speicherplatz gespeichert, und der zweite Operand gibt die Verzweigungsadresse an:

Instruction subleq2 a, b
    Mem[a] = Mem[a] - ACCUM
    ACCUM = Mem[a]
    if (Mem[a] ≤ 0)
        goto b

Dies verwendet zwar nur zwei (statt drei) Operanden pro Befehl, jedoch werden dann entsprechend mehr Befehle benötigt, um verschiedene logische Operationen auszuführen.

Synthetisierte Anweisungen

Es ist möglich, viele Arten von Befehlen höherer Ordnung zu synthetisieren, indem nur der untergeordnete Befehl verwendet wird.

Unbedingte Verzweigung:

JMP c

  subleq Z, Z, c

Die Addition kann durch wiederholte Subtraktion ohne bedingte Verzweigung durchgeführt werden; Beispiel ergeben sich die folgenden Anweisungen in den Inhalt an der Position a an der Position zu dem Inhalt hinzugefügt werden , b :

HINZUFÜGEN a, b

  subleq a, Z
  subleq Z, b
  subleq Z, Z

Der erste Befehl subtrahiert den Inhalt an der Stelle a aus dem Inhalt an der Position Z (das gleich 0 ist ) und speichert das Ergebnis (die das Negativ des Gehalt an ist a ) in Position Z . Die zweite Anweisung subtrahiert dieses Ergebnis von b und speichert diese Differenz in b (die jetzt die Summe der Inhalte ursprünglich bei a und b ist ); die dritte Anweisung stellt den Wert 0 auf Z wieder her .

Ein Kopierbefehl kann ähnlich implementiert werden; Beispielsweise führen die folgenden Anweisungen dazu, dass der Inhalt an Ort b durch den Inhalt an Ort a ersetzt wird , wiederum unter der Annahme, dass der Inhalt an Ort Z als 0 beibehalten wird:

MOV a, b

  subleq b, b
  subleq a, Z
  subleq Z, b
  subleq Z, Z

Jeder gewünschte arithmetische Test kann gebaut werden. Zum Beispiel kann eine Verzweigungs-wenn-Null-Bedingung aus den folgenden Anweisungen zusammengesetzt werden:

BEQ b, c

  subleq b, Z, L1
  subleq Z, Z, OUT
L1:
  subleq Z, Z
  subleq Z, b, c
OUT:
  ...

Subleq2 kann auch verwendet werden, um Befehle höherer Ordnung zu synthetisieren, obwohl es im Allgemeinen mehr Operationen für eine bestimmte Aufgabe erfordert. Zum Beispiel sind nicht weniger als 10 subleq2-Anweisungen erforderlich, um alle Bits in einem bestimmten Byte umzukehren:

Kein

  subleq2 tmp          ; tmp = 0 (tmp = temporary register)
  subleq2 tmp
  subleq2 one          ; acc = -1
  subleq2 a            ; a' = a + 1
  subleq2 Z            ; Z = - a - 1
  subleq2 tmp          ; tmp = a + 1
  subleq2 a            ; a' = 0
  subleq2 tmp          ; load tmp into acc
  subleq2 a            ; a' = - a - 1 ( = ~a )
  subleq2 Z            ; set Z back to 0

Emulation

Das folgende Programm (in Pseudocode geschrieben ) emuliert die Ausführung eines subleq- basierten OISC:

 int memory[], program_counter, a, b, c
 program_counter = 0
 while (program_counter >= 0):
     a = memory[program_counter]
     b = memory[program_counter+1]
     c = memory[program_counter+2]
     if (a < 0 or b < 0):
         program_counter = -1
     else:
         memory[b] = memory[b] - memory[a]
         if (memory[b] > 0):
             program_counter += 3
         else:
             program_counter = c

Dieses Programm geht davon aus, dass memory[] durch nichtnegative ganze Zahlen indiziert ist . Folglich interpretiert das Programm für einen untergeordneten Befehl ( a , b , c ) a < 0 , b < 0 oder eine ausgeführte Verzweigung zu c < 0 als eine Haltebedingung. Ähnliche Interpreter, die in einer subleq- basierten Sprache geschrieben sind (dh Selbst-Interpreter , die selbstmodifizierenden Code verwenden können, wie es die Natur der Subleq- Anweisung erlaubt ) können in den folgenden externen Links gefunden werden.

Zusammenstellung

Es gibt einen Compiler namens Higher Subleq , der von Oleg Mazonka geschrieben wurde und ein vereinfachtes C-Programm in Subleq- Code kompiliert.

Subtrahiere und verzweige wenn negativ

Die Subneg- Anweisung (" subtract and branch if negativ "), auch SBN genannt , ist ähnlich wie subleq definiert :

Instruction subneg a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] < 0)
        goto c

Bedingte Verzweigung kann unterdrückt werden, indem der dritte Operand gleich der Adresse des nächsten Befehls in Folge gesetzt wird. Wenn der dritte Operand nicht geschrieben wird, wird diese Unterdrückung impliziert.

Synthetisierte Anweisungen

Es ist möglich, viele Arten von Befehlen höherer Ordnung zu synthetisieren, indem nur der Subneg- Befehl verwendet wird. Der Einfachheit halber wird hier nur ein synthetisierter Befehl gezeigt, um den Unterschied zwischen subleq und subneg zu veranschaulichen .

Unbedingte Verzweigung:

JMP c

  subneg POS, Z, c

wobei Z und POS Positionen sind, die zuvor so eingestellt wurden, dass sie 0 bzw. eine positive ganze Zahl enthalten;

Eine unbedingte Verzweigung ist nur gewährleistet, wenn Z anfänglich 0 enthält (oder einen Wert kleiner als die in POS gespeicherte ganze Zahl ). Eine Folgeanweisung ist erforderlich, um Z nach der Verzweigung zu löschen , vorausgesetzt, der Inhalt von Z muss als 0 beibehalten werden.

subneg4

Eine Variante ist auch mit vier Operanden möglich – subneg4. Die Umkehrung von Minuend und Subtrahend erleichtert die Implementierung in Hardware. Das zerstörungsfreie Ergebnis vereinfacht die synthetischen Anweisungen.

Instruction subneg s, m, r, j
    (* subtrahend, minuend, result and jump addresses *)
    Mem[r] = Mem[m] - Mem[s]
    if (Mem[r] < 0)
        goto j

Rechenmaschine

Um die Turing-Maschine intuitiver zu gestalten, betrachtet ZA Melzac die Aufgabe des Rechnens mit positiven Zahlen. Die Maschine hat einen unendlichen Abakus, eine unendliche Anzahl von Zählern (Kieselsteine, Zählstäbe) zunächst an einer speziellen Stelle S. Die Maschine kann eine Operation ausführen:

Nehmen Sie von Standort X so viele Spielsteine ​​wie an Standort Y und übertragen Sie sie auf Standort Z und fahren Sie mit der nächsten Anweisung fort.

Wenn dieser Vorgang nicht möglich ist, weil in Y nicht genügend Zähler vorhanden sind, lassen Sie den Abakus unverändert und fahren Sie mit Anweisung T fort.

Dies ist im Wesentlichen ein Subneg, bei dem der Test vor und nicht nach der Subtraktion durchgeführt wird, um alle Zahlen positiv zu halten und einen menschlichen Operator zu imitieren, der auf einem realen Abakus berechnet. Pseudocode:

Instruction melzac X, Y, Z, T
    if (Mem[Y] < Mem[X])
        goto T
    Mem[Z] = Mem[Y] - Mem[X]

Nach einigen Programmen: Multiplikation, gcd, Berechnung der n- ten Primzahl, Darstellung einer beliebigen Zahl in der Basis b , Sortierung nach Größenordnung, zeigt Melzac explizit, wie man eine beliebige Turingmaschine auf seiner Rechenmaschine simulieren kann.

Er erwähnt, dass mit den Elementen rekursiver Funktionen leicht gezeigt werden kann, dass jede auf der arithmetischen Maschine berechenbare Zahl berechenbar ist. Ein Beweis dafür wurde von Lambek auf einer äquivalenten Maschine mit zwei Befehlen gegeben: X+ (inkrementiere X) und X− sonst T (dekrementiere X, wenn es nicht leer ist, sonst springe zu T).

Umgekehrt subtrahieren und überspringen, wenn borgen

Bei einem umgekehrten Subtrahieren und Überspringen-wenn-Ausleih- (RSSB)-Befehl wird der Akkumulator von der Speicherstelle subtrahiert und der nächste Befehl wird übersprungen, wenn ein Ausleihen vorhanden war (der Speicherort war kleiner als der Akkumulator). Das Ergebnis wird sowohl im Akkumulator als auch im Speicherplatz gespeichert. Der Programmzähler wird auf Speicherplatz 0 abgebildet. Der Akkumulator wird auf Speicherplatz 1 abgebildet.

Instruction rssb x
    ACCUM = Mem[x] - ACCUM
    Mem[x] = ACCUM
    if (ACCUM < 0)
        goto PC + 2

Beispiel

So setzen Sie x auf den Wert von y minus z:

# First, move z to the destination location x.
  RSSB temp # Three instructions required to clear acc, temp [See Note 1]
  RSSB temp
  RSSB temp
  RSSB x    # Two instructions clear acc, x, since acc is already clear
  RSSB x
  RSSB y    # Load y into acc: no borrow
  RSSB temp # Store -y into acc, temp: always borrow and skip
  RSSB temp # Skipped
  RSSB x    # Store y into x, acc
# Second, perform the operation.
  RSSB temp # Three instructions required to clear acc, temp
  RSSB temp
  RSSB temp
  RSSB z    # Load z
  RSSB x    # x = y - z [See Note 2]

• [Anmerkung 1] Wenn der unter "temp" gespeicherte Wert anfänglich ein negativer Wert ist und der Befehl, der direkt vor dem ersten "RSSB temp" in dieser Routine ausgeführt wurde, ausgeliehen ist, dann sind vier "RSSB temp"-Befehle erforderlich, damit die Routine funktioniert .
• [Anmerkung 2] Wenn der bei "z" gespeicherte Wert anfänglich ein negativer Wert ist, wird das letzte "RSSB x" übersprungen und somit funktioniert die Routine nicht.

Transport-getriggerte Architektur

Eine transportgetriggerte Architektur verwendet nur den Bewegungsbefehl , daher wurde sie ursprünglich als "Bewegungsmaschine" bezeichnet. Dieser Befehl verschiebt den Inhalt eines Speicherplatzes an einen anderen Speicherplatz und kombiniert ihn mit dem aktuellen Inhalt des neuen Speicherplatzes:

Instruction movx a, b (also written a -> b)
    OP = GetOperation(Mem[b])
    Mem[b] := OP(Mem[a], Mem[b])

Die durchgeführte Operation wird durch die Zielspeicherzelle definiert. Einige Zellen sind zusätzlich spezialisiert, andere auf Multiplikation usw. Speicherzellen sind also nicht einfach zu speichern, sondern mit einem Aufbau einer arithmetischen Logikeinheit (ALU) gekoppelt , um nur eine Art von Operation mit dem aktuellen Wert der Zelle durchzuführen. Einige der Zellen sind Kontrollflussanweisungen zum Ändern der Programmausführung mit Sprüngen, bedingter Ausführung , Unterroutinen , if-then-else , for-loop , etc...

Es wurde ein kommerzieller Mikrocontroller mit verkehrsgesteuerter Architektur namens MAXQ entwickelt, der die offensichtlichen Unannehmlichkeiten eines OISC verbirgt, indem er eine "Übertragungskarte" verwendet, die alle möglichen Ziele für die Bewegungsanweisungen darstellt .

Kryptoleq

Cryptoleq-Prozessor hergestellt an der NYU Abu Dhabi

Cryptoleq ist eine Sprache, die aus einer gleichnamigen Anweisung besteht, in der Lage ist, universelle Berechnungen für verschlüsselte Programme durchzuführen und ein enger Verwandter von Subleq ist. Cryptoleq arbeitet mit kontinuierlichen Speicherzellen mit direkter und indirekter Adressierung und führt zwei Operationen O ₁ und O ₂ mit drei Werten A, B und C durch:

Instruction cryptoleq a, b, c
    Mem[b] = O1(Mem[a], Mem[b])
    if O2(Mem[b]) ≤ 0
        IP = c
    else
        IP = IP + 3

wobei a, b und c durch den Befehlszeiger IP adressiert werden, wobei der Wert der IP-Adressierung a, IP + 1 auf b und IP + 2 auf c zeigt.

In Cryptoleq-Operationen sind O ₁ und O ₂ wie folgt definiert:

${\displaystyle {\begin{array}{lcl}O_{1}(x,y)&=&x_{N^{2}}^{-1}y\,{\bmod {\,}}N^{ 2}\end{array}}}$

${\displaystyle {\begin{array}{lcl}O_{2}(x)&=&\left\lfloor {\frac {x-1}{N}}\right\rfloor \end{array}}}$

Der Hauptunterschied zu Subleq besteht darin, dass in Subleq O ₁ ( x,y ) einfach y von x subtrahiert und O ₂ ( x ) gleich x ist . Cryptoleq ist auch homomorph zu Subleq, modulare Inversion und Multiplikation ist homomorph zu Subtraktion und die Operation von O ₂ entspricht dem Subleq-Test, wenn die Werte unverschlüsselt wären. Ein in Subleq geschriebenes Programm kann auf einem Cryptoleq-Rechner ausgeführt werden, was Abwärtskompatibilität bedeutet. Cryptoleq implementiert jedoch vollständig homomorphe Berechnungen und da das Modell in der Lage ist, Multiplikationen durchzuführen. Die Multiplikation auf einer verschlüsselten Domäne wird durch eine einzigartige Funktion G unterstützt, von der angenommen wird, dass sie schwer zurückzuentwickeln ist und die die erneute Verschlüsselung eines Werts basierend auf der O ₂ -Operation ermöglicht:

${\displaystyle G(x,y)={\begin{cases}{\tilde {0}},&{\text{if }}O_{2}({\bar {x}}){\text{ } }\leq 0\\{\tilde{y}},&{\text{sonst}}\end{cases}}}$

wo ist der neu verschlüsselte Wert von y und ist verschlüsselt null. x ist der verschlüsselte Wert einer Variablen, sei es m und gleich . ${\displaystyle {\tilde{y}}}$${\displaystyle {\tilde {0}}}$${\displaystyle {\bar {x}}}$${\displaystyle Nm+1}$

Der Multiplikationsalgorithmus basiert auf Addition und Subtraktion, verwendet die Funktion G und hat keine bedingten Sprünge oder Verzweigungen. Die Cryptoleq-Verschlüsselung basiert auf dem Paillier-Kryptosystem .

Siehe auch

• FRACTRAN
• Maschine registrieren
• Turing-Plane
• Computer mit Nullbefehlssatz

Verweise

Externe Links

• Subleq im Wiki für esoterische Programmiersprachen – Interpreter, Compiler, Beispiele und abgeleitete Sprachen
• Reductio ad absurdum auf YouTube von Christopher Domas
• Labor-Subleq-Computer – FPGA- Implementierung mit VHDL
• The Retrocomputing Museum – SBN-Emulator und Beispielprogramme
• Labor-SBN-Computer – implementiert mit integrierten Schaltkreisen der Serie 7400
• RSSB im Wiki für esoterische Programmiersprachen – Interpreter und Beispiele
• Dr. Dobbs 32-Bit-OISC-Implementierung – Transport Triggered Architecture (TTA) auf einem FPGA mit Verilog
• Einführung in die MAXQ-Architektur – inklusive Transfer-Map-Diagramm
• OISC-Emulator – grafische Version
• TrapCC (neuere Intel x86-MMUs sind eigentlich Turing-vollständige OISCs.)
• SBN-Simulator – Simulator und Design inspiriert von CARDboard Illustrative Aid to Computation
• One-Bit Computing bei 60 Hertz – Zwischen einem Computer und einer Zustandsmaschine
• Die NOR-Maschine  – Infos zum Bau einer CPU mit nur einer Anweisung
• Cryptoleq  – Cryptoleq-Ressourcen-Repository
• CAAMP  – Computerarchitektur Eine minimalistische Perspektive
• DawnOS – ein Betriebssystem für die SUBLEQ-Architektur
• Unileq – eine Variante von SUBLEQ mit vorzeichenlosen Ganzzahlen