Komputer z jedną instrukcją - One-instruction set computer

Komputer z jednym zestawem instrukcji ( OISC ), czasami nazywany ostatecznym komputerem o zredukowanym zestawie instrukcji ( URISC ), jest abstrakcyjną maszyną, która używa tylko jednej instrukcji - eliminując potrzebę użycia kodu operacyjnego języka maszynowego . Dzięki rozsądnemu wyborowi pojedynczej instrukcji i nieograniczonym zasobom, OISC może być uniwersalnym komputerem w taki sam sposób, jak tradycyjne komputery, które mają wiele instrukcji. OISC są rekomendowane jako pomoc w nauczaniu architektury komputerowej i są wykorzystywane jako modele obliczeniowe w badaniach obliczeń strukturalnych.

Podczas gdy 1-bitowe procesory są poza tym przestarzałe (i nie były OISC), pierwszy komputer z nanorurek węglowych jest 1-bitowym komputerem z jednym zestawem instrukcji (i ma tylko 178 tranzystorów).

Architektura maszyny

W modelu Turing-complete każda lokalizacja pamięci może przechowywać dowolną liczbę całkowitą i – w zależności od modelu – może być dowolnie wiele lokalizacji. Same instrukcje znajdują się w pamięci jako sekwencja takich liczb całkowitych.

Istnieje klasa uniwersalnych komputerów z pojedynczą instrukcją opartą na manipulacji bitami, takiej jak kopiowanie bitów lub inwersja bitów . Ponieważ ich model pamięci jest skończony, podobnie jak struktura pamięci używana w prawdziwych komputerach, te maszyny do manipulacji bitami są równoważne prawdziwym komputerom, a nie maszynom Turinga.

Obecnie znane OISC można z grubsza podzielić na trzy szerokie kategorie:

• Maszyny do manipulowania bitami
• Maszyny architektury wyzwalanej przez transport
• Kompletne maszyny Turinga oparte na arytmetyce

Maszyny do manipulowania bitami

Maszyny manipulujące bitami to najprostsza klasa.

FlipSkok

FlipJump Maszyna posiada 1 instrukcja, a; b - odwraca bitowy, a następnie przeskakuje do b. Jest to najbardziej prymitywny OISC, ale nadal jest użyteczny. Może z powodzeniem wykonywać obliczenia matematyczne/logiczne, rozgałęzianie, wskaźniki i wywoływanie funkcji za pomocą swojej standardowej biblioteki.

BitBitJump

Maszyna do kopiowania bitów, zwana BitBitJump, kopiuje jeden bit do pamięci i przekazuje wykonanie bezwarunkowo pod adres określony przez jeden z argumentów instrukcji. Proces ten okazuje się być zdolny do uniwersalnych obliczeń (tzn. być w stanie wykonać dowolny algorytm i zinterpretować dowolną inną uniwersalną maszynę), ponieważ kopiowanie bitów może warunkowo modyfikować kod, który zostanie następnie wykonany.

Komputer Toga

Inna maszyna, zwana Komputerem Toga , odwraca nieco i przekazuje wykonanie warunkowo w zależności od wyniku inwersji. Unikalną instrukcją jest TOGA(a,b), co oznacza TOG gle a A i gałąź na b, jeśli wynik operacji przełączania jest prawdziwy.

Kopiarka wielobitowa

Podobnie jak BitBitJump, wielobitowa maszyna kopiująca kopiuje jednocześnie kilka bitów. Problem uniwersalności obliczeniowej rozwiązuje się w tym przypadku poprzez przechowywanie w pamięci predefiniowanych tablic skoków.

Architektura wyzwalana przez transport

Architektura wyzwalana przez transport (TTA) to projekt, w którym obliczenia są efektem ubocznym transportu danych. Zwykle niektóre rejestry pamięci (porty wyzwalające) w obrębie wspólnej przestrzeni adresowej wykonują przypisaną operację, gdy instrukcja się do nich odwołuje. Na przykład w OISC korzystającym z pojedynczej instrukcji kopiowania z pamięci do pamięci odbywa się to poprzez wyzwolenie portów, które wykonują skoki arytmetyczne i instrukcje podczas zapisywania.

Kompletne maszyny Turinga oparte na arytmetyce

Oparte na arytmetyce maszyny Turing-complete wykorzystują operację arytmetyczną i skok warunkowy. Podobnie jak dwa poprzednie komputery uniwersalne, ta klasa jest również zgodna z Turingiem. Instrukcja operuje na liczbach całkowitych, które mogą być również adresami w pamięci.

Obecnie istnieje kilka znanych OISC tej klasy, opartych na różnych operacjach arytmetycznych:

• dodawanie (addleq, dodawać lub rozgałęzionym, jeśli L ess niż lub równoważnika UAL do zera)
• zmniejszania (DJN, D ecrement i składnika ( J UMP) czy N onzero)
• przyrost (P1eq, P lus 1 , a odgałęzienie jeśli równ UAL na inną wartość)
• odejmowanie (subleq, sub oddechowych lub rozgałęzionym, jeśli L ess niż lub równoważnika UAL do zera)
• odejmowanie dodatnie, jeśli to możliwe, w przeciwnym razie gałąź (maszyna arytmetyczna)

Rodzaje instrukcji

Typowe wybory dla pojedynczej instrukcji to:

• Odejmij i rozgałęź, jeśli jest mniejsze lub równe zero
• Odejmij i rozgałęź, jeśli jest ujemny
• Odejmij, jeśli dodatni inny oddział
• Odwróć odejmowanie i pomiń, jeśli pożyczasz
• Przenieś (używany jako część architektury wyzwalanej przez transport)
• Odejmij i rozgałęź, jeśli niezerowe (SBNZ a, b, c, miejsce docelowe)
• Cryptoleq (heterogeniczne obliczenia zaszyfrowane i nieszyfrowane)

Tylko jedna z tych instrukcji jest używana w danej implementacji. W związku z tym nie ma potrzeby, aby opcode identyfikował, którą instrukcję wykonać; wybór instrukcji jest nieodłącznie związany z projektem maszyny, a OISC jest zwykle nazwany po instrukcji, której używa (np. SBN OISC, język SUBLEQ itp.). Każda z powyższych instrukcji może być użyta do skonstruowania kompletnego Turinga OISC.

W tym artykule przedstawiono tylko instrukcje oparte na odejmowaniu spośród tych, które nie są wyzwalane przez transport. Możliwe jest jednak zbudowanie kompletnych maszyn Turinga za pomocą instrukcji opartej na innych operacjach arytmetycznych, np. dodawaniu. Na przykład jedna odmiana znana jako DLN (Dekrementacja i skok, jeśli nie zero) ma tylko dwa operandy i używa dekrementacji jako operacji podstawowej. Aby uzyskać więcej informacji, zobacz języki pochodne Subleq [1] .

Odejmij i rozgałęź, jeśli nie jest równe zero

SBNZ a, b, c, d Instrukcji ( „ odejmowanie lub rozgałęzionym, o ile nie są równe zero ”) odejmuje się zawartość w adresowej a z zawartością na adres b , przechowuje się wynik na adres C , a następnie , jeśli wynik nie oznacza 0 , przekazuje sterowanie do adresu d ( jeśli wynik jest równy zero, wykonanie przechodzi do następnej instrukcji w sekwencji).

Odejmij i rozgałęź, jeśli jest mniejsze lub równe zero

Subleq instrukcja ( „ odejmować i oddziału, jeżeli mniejsze lub równe zeru ”) odejmuje zawartość pod adresem A z treści pod adresem b , zapisuje wynik w adresie B , a potem, jeśli wynik nie jest pozytywny , przekazuje sterowanie do adres c (jeśli wynik jest pozytywny, wykonanie przechodzi do następnej instrukcji w kolejności). Pseudokod :

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

Rozgałęzienie warunkowe można stłumić, ustawiając trzeci operand równy adresowi następnej instrukcji w sekwencji. Jeśli trzeci operand nie jest zapisany, to pominięcie jest implikowane.

Możliwy jest również wariant z dwoma argumentami i wewnętrznym akumulatorem , gdzie akumulator jest odejmowany od lokalizacji pamięci określonej przez pierwszy argument. Wynik jest przechowywany zarówno w akumulatorze, jak i w lokalizacji pamięci, a drugi argument określa adres gałęzi:

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

Chociaż wykorzystuje to tylko dwa (zamiast trzech) operandów na instrukcję, odpowiednio więcej instrukcji jest wtedy potrzebnych do wykonania różnych operacji logicznych.

Zsyntetyzowane instrukcje

Możliwe jest zsyntetyzowanie wielu typów instrukcji wyższego rzędu przy użyciu tylko instrukcji subleq .

Oddział bezwarunkowy:

JMP c

  subleq Z, Z, c

Dodawanie można przeprowadzić przez wielokrotne odejmowanie, bez warunkowego rozgałęzienia; Np. poniższe instrukcje powodują dodanie treści w lokalizacji a do treści w lokalizacji b :

DODAJ a, b

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

Pierwsza instrukcja odejmuje zawartość w lokalizacji a od zawartości w lokalizacji Z (czyli 0) i przechowuje wynik (który jest ujemną zawartością w a ) w lokalizacji Z . Druga instrukcja odejmuje ten wynik od b , przechowywanie w b tej różnicy (co jest obecnie suma zawartości pierwotnie w i B ); trzecia instrukcja przywraca wartość od 0 do Z .

Podobnie można zaimplementować instrukcję kopiowania; Np. poniższe instrukcje powodują zastąpienie treści w lokalizacji b treścią w lokalizacji a , ponownie przy założeniu, że treść w lokalizacji Z jest utrzymywana jako 0:

MOV a, b

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

Można zbudować dowolny test arytmetyczny. Na przykład warunek branch-if-zero można złożyć z następujących instrukcji:

BEQ b, c

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

Subleq2 może być również użyty do syntezy instrukcji wyższego rzędu, chociaż generalnie wymaga więcej operacji dla danego zadania. Na przykład, nie mniej niż 10 instrukcji subleq2 jest wymaganych do odwrócenia wszystkich bitów w danym bajcie:

Ani

  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

Współzawodnictwo

Poniższy program (napisany w pseudokodzie ) emuluje wykonanie OISC opartego na podlegu :

 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

Ten program zakłada, że memory[] jest indeksowane nieujemnymi liczbami całkowitymi. W konsekwencji, dla instrukcji subleq ( a , b , c ) program interpretuje a < 0 , b < 0 lub wykonaną gałąź na c < 0 jako warunek zatrzymania. Podobne tłumaczy pisemnych w subleq opartym na języku (czyli samo-tłumaczy , który może wykorzystywać samodzielne modyfikowanie kodu , jak pozwala na to charakter subleq instrukcją) można znaleźć w poniższych linków zewnętrznych.

Kompilacja

Istnieje kompilator o nazwie Higher Subleq napisany przez Olega Mazonkę, który kompiluje uproszczony program w C do kodu subleq .

Odejmij i rozgałęź, jeśli jest ujemny

Subneg instrukcja ( „ odejmowania i oddziału, jeżeli negatywna ”), zwany również SBN , jest określona w sposób podobny do subleq :

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

Rozgałęzienie warunkowe można stłumić, ustawiając trzeci operand równy adresowi następnej instrukcji w sekwencji. Jeśli trzeci operand nie jest zapisany, to pominięcie jest implikowane.

Zsyntetyzowane instrukcje

Możliwe jest zsyntetyzowanie wielu typów instrukcji wyższego rzędu przy użyciu tylko instrukcji subneg . Dla uproszczenia pokazano tutaj tylko jedną zsyntetyzowaną instrukcję, aby zilustrować różnicę między subleq i subneg .

Oddział bezwarunkowy:

JMP c

  subneg POS, Z, c

gdzie Z i POS są lokalizacjami wcześniej ustawionymi na odpowiednio 0 i dodatnią liczbę całkowitą;

Bezwarunkowe rozgałęzienie jest gwarantowane tylko wtedy, gdy Z początkowo zawiera 0 (lub wartość mniejszą niż liczba całkowita przechowywana w POS ). Wymagana jest kolejna instrukcja, aby wyczyścić Z po rozgałęzieniu, przy założeniu, że zawartość Z musi być utrzymana jako 0.

subneg4

Możliwy jest również wariant z czterema argumentami – subneg4. Odwrócenie odcinków i odcinków ułatwia implementację sprzętową. Nieniszczący wynik upraszcza instrukcje syntetyczne.

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

Maszyna arytmetyczna

Próbując uczynić maszynę Turinga bardziej intuicyjną, ZA Melzac rozważa zadanie obliczeń na liczbach dodatnich. Maszyna posiada nieskończone liczydło, nieskończoną ilość liczników (kamyków, patyczków) początkowo w specjalnym miejscu S. Maszyna jest w stanie wykonać jedną operację:

Weź z lokalizacji X tyle żetonów, ile jest w lokalizacji Y i przenieś je do lokalizacji Z i przejdź do następnej instrukcji.

Jeśli ta operacja nie jest możliwa, ponieważ nie ma wystarczającej liczby liczników w Y, pozostaw liczydło bez zmian i przejdź do instrukcji T.

Zasadniczo jest to podneg, w którym test jest wykonywany przed, a nie po odjęciu, w celu utrzymania wszystkich liczb dodatnich i naśladowania ludzkiego operatora obliczającego na liczydle ze świata rzeczywistego. Pseudo kod:

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

Po podaniu kilku programów: mnożenia, gcd, obliczania n- tej liczby pierwszej, reprezentacji w bazie b dowolnej liczby, sortowania według wielkości, Melzac pokazuje wyraźnie, jak symulować dowolną maszynę Turinga na swojej maszynie arytmetycznej.

Wspomina, że ​​za pomocą elementów funkcji rekurencyjnych można łatwo wykazać, że każda liczba obliczona na maszynie arytmetycznej jest obliczalna. Dowód na to dał Lambek na równoważnej maszynie dwuinstrukcyjnej: X+ (zwiększenie X) i X− w przeciwnym razie T (zmniejszenie X, jeśli nie jest puste, w przeciwnym razie przeskocz do T).

Odwróć odejmowanie i pomiń, jeśli pożyczasz

W instrukcji reverse subtract and skip if lend (RSSB) akumulator jest odejmowany od komórki pamięci, a następna instrukcja jest pomijana, jeśli pożyczono pożyczkę (lokalizacja pamięci była mniejsza niż akumulator). Wynik jest przechowywany zarówno w akumulatorze, jak iw lokalizacji pamięci. Licznik programu jest mapowany do lokalizacji pamięci 0. Akumulator jest mapowany do lokalizacji pamięci 1.

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

Przykład

Aby ustawić x na wartość 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]

• [Uwaga 1] Jeśli wartość przechowywana w „temp” jest początkowo wartością ujemną i instrukcja, która została wykonana tuż przed pierwszą „RSSB temp” w tej procedurze pożyczonej, to do działania tej procedury będą wymagane cztery instrukcje „RSSB temp”. .
• [Uwaga 2] Jeśli wartość przechowywana w „z” jest początkowo wartością ujemną, to końcowy „RSSB x” zostanie pominięty, a zatem procedura nie będzie działać.

Architektura wyzwalana przez transport

Architektura wyzwalana transportem wykorzystuje tylko instrukcję move , stąd pierwotnie nazywano ją „maszyną ruchu”. Ta instrukcja przenosi zawartość jednej komórki pamięci do innej komórki pamięci, łącząc się z bieżącą zawartością nowej lokalizacji:

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

Wykonywana operacja jest określona przez docelową komórkę pamięci. Niektóre komórki specjalizują się dodatkowo, inne w mnożeniu itp. Tak więc komórki pamięci nie są prostym przechowywaniem, ale są połączone z konfiguracją jednostki arytmetyczno-logicznej (ALU), aby wykonać tylko jeden rodzaj operacji z bieżącą wartością komórki. Niektóre komórki to instrukcje przepływu sterowania, które zmieniają wykonanie programu za pomocą skoków, wykonania warunkowego , podprogramów , if-then-else , for-loop itp.

Wyprodukowano komercyjny mikrokontroler o architekturze wyzwalanej transportem o nazwie MAXQ, który ukrywa widoczną niedogodność OISC za pomocą „mapy transferu”, która reprezentuje wszystkie możliwe miejsca docelowe dla instrukcji ruchu .

kryptoq

Procesor Cryptoleq wyprodukowany w NYU Abu Dhabi

Cryptoleq to język składający się z jednej tytułowej instrukcji, zdolny do wykonywania obliczeń ogólnego przeznaczenia na zaszyfrowanych programach i jest bliski krewny Subleqa. Cryptoleq działa na ciągłych komórkach pamięci przy użyciu adresowania bezpośredniego i pośredniego i wykonuje dwie operacje O ₁ i O ₂ na trzech wartościach A, B i C:

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

gdzie a, b i c są adresowane przez wskaźnik instrukcji, IP, z wartością adresowania IP a, IP + 1 punkt do b i IP + 2 do c.

W Cryptoleq operacje O ₁ i O ₂ są zdefiniowane w następujący sposób:

${\ Displaystyle {\ zacząć {tablica} {lcl} O_ {1} (x, y) i = i x_ {N ^ {2}} ^ {-1} y \ {\ bmod {\,}} N ^ { 2}\end{tablica}}}$

${\ Displaystyle {\ zacząć {tablica} {lcl} O_ {2} (x) & = i \ lewo \ l piętro {\ Frac {x-1} {N}} \ prawo \ r piętro \ koniec {tablica}}}$

Główna różnica w Subleq polega na tym, że w Subleq O ₁ ( x,y ) po prostu odejmuje y od x , a O ₂ ( x ) równa się x . Cryptoleq jest również homomorficzny z Subleq, modułowa inwersja i mnożenie jest homomorficzne z odejmowaniem, a działanie O ₂ odpowiada testowi Subleq, jeśli wartości były niezaszyfrowane. Program napisany w Subleq może działać na maszynie Cryptoleq, co oznacza kompatybilność wsteczną. Jednak Cryptoleq implementuje w pełni homomorficzne obliczenia, a ponieważ model jest w stanie wykonywać mnożenia. Mnożenie w zaszyfrowanej domenie jest wspomagane przez unikalną funkcję G, która z założenia jest trudna do odtworzenia i umożliwia ponowne zaszyfrowanie wartości w oparciu o operację O ₂ :

${\ Displaystyle G (x, y) = {\ zacząć {przypadki} {\ tylda {0}} i {\ tekst {jeśli}} O_ {2} ({\ bar {x}}) {\ tekst {} }\leq 0\\{\tylda {y}},&{\text{otherwise}}\end{cases}}}$

gdzie jest ponownie zaszyfrowaną wartością y i jest zaszyfrowanym zerem. x jest zaszyfrowaną wartością zmiennej, niech będzie m i równa się . ${\displaystyle {\tylda {y}}}$${\displaystyle {\tylda {0}}}$${\displaystyle {\bar {x}}}$${\ Displaystyle Nm+1}$

Algorytm mnożenia opiera się na dodawaniu i odejmowaniu, wykorzystuje funkcję G i nie posiada skoków warunkowych ani rozgałęzień. Szyfrowanie Cryptoleq opiera się na kryptosystemie Paillier .

Zobacz też

• FRAKRAN
• Zarejestruj maszynę
• Tarpit Turinga
• Komputer z zestawem instrukcji zerowych

Bibliografia

Zewnętrzne linki

• Subleq na wiki ezoterycznych języków programowania – interpretery, kompilatory, przykłady i języki pochodne
• Reductio ad absurdum na YouTube autorstwa Christophera Domasa
• Komputer laboratoryjny subleq – implementacja FPGA z wykorzystaniem VHDL
• Muzeum Retrokomputerów – emulator SBN i przykładowe programy
• Komputer laboratoryjny SBN – realizowany z układami scalonymi serii 7400
• RSSB na wiki ezoterycznych języków programowania – interpretery i przykłady
• 32-bitowa implementacja OISC dr. Dobba – architektura wyzwalana transportem (TTA) na FPGA przy użyciu Verilog
• Wprowadzenie do Architektury MAXQ – zawiera diagram mapy transferu
• Emulator OISC – wersja graficzna
• TrapCC (ostatnie MMU Intel x86 są w rzeczywistości kompletnymi OISC Turinga.)
• Symulator SBN – symulator i projekt inspirowany CARDboard Illustrative Aid to Computation
• Obliczenia jednobitowe przy 60 Hz – pośrednie między komputerem a maszyną stanów
• Maszyna NOR  – informacje o budowie procesora za pomocą tylko jednej instrukcji
• Cryptoleq  – repozytorium zasobów Cryptoleq
• CAAMP  – architektura komputerowa z minimalistycznej perspektywy
• DawnOS – system operacyjny dla architektury SUBLEQ
• Unileq – wariant SUBLEQ używający liczb całkowitych bez znaku