1命令セットコンピュータ

1命令セットコンピュータ（OISC ）は、究極の縮小命令セットコンピュータ（URISC）とも呼ばれ、機械語オペコードを必要としない、1つの命令のみを使用する抽象マシンです。^{[1] [2] [3]} 1つの命令を賢明に選択し、任意の数のリソースを与えられると、OISCは複数の命令を持つ従来のコンピュータと同じように汎用コンピュータになることができます。 ^{[2] : 55} OISCは、コンピュータアーキテクチャの教育の補助として推奨されており^{[1] : 327  [2] : 2}、構造コンピューティング研究の計算モデルとして使用されています。^[3]最初のカーボンナノチューブコンピュータは1ビットの1命令セットコンピュータです（トランジスタは178個しかありません）。^[4]

チューリング完全なモデルでは、各メモリ位置に任意の整数を格納でき、モデルによっては^{[説明が必要]} 任意の数のメモリ位置が存在する場合があります。命令自体は、このような整数のシーケンスとしてメモリ内に存在します。

ビットコピーやビット反転などのビット操作に基づく単一命令を備えた汎用コンピュータのクラスが存在します。実際のコンピュータで使用されるメモリ構造と同様に、メモリモデルは有限であるため、これらのビット操作マシンはチューリングマシンではなく実際のコンピュータと同等です。^[5]

現在知られている OISC は、おおまかに次の 3 つのカテゴリに分けられます。

• ビット操作マシン
• トランスポートトリガーアーキテクチャマシン
• 算術ベースのチューリング完全マシン

ビット操作マシンは最も単純なクラスです。

FlipJump マシンには、ビット a を反転し、b にジャンプする命令が 1 つあります。これは最も原始的な OISC ですが、それでも便利です。標準ライブラリの助けを借りて、数学/論理計算、分岐、ポインタ、関数の呼び出しを正常に実行できます。

BitBitJumpと呼ばれるビットコピーマシン^[5]は、メモリ内の1ビットをコピーし、命令のオペランドの1つで指定されたアドレスに無条件に実行を渡します。このプロセスは、ビットのコピーによって、その後実行されるコピーアドレスを条件付きで変更できるため、汎用計算（つまり、任意のアルゴリズムを実行し、他の汎用マシンを解釈できる）が可能であることがわかっています。

Toga コンピュータと呼ばれる別のマシンは、ビットを反転し、反転の結果に応じて条件付きで実行を渡します。固有の命令は TOGA(a,b) で、これはTOG gle a Aを表し、トグル操作の結果が true の場合は bに分岐します。

BitBitJump と同様に、マルチビット コピー マシンは複数のビットを同時にコピーします。この場合、計算の普遍性の問題は、メモリ内に定義済みのジャンプ テーブルを保持することで解決されます。^{[説明が必要]}

トランスポート トリガー アーキテクチャ(TTA) は、計算がデータ転送の副作用となる設計です。通常、共通アドレス空間内の一部のメモリ レジスタ (トリガー ポート) は、命令が参照したときに割り当てられた操作を実行します。たとえば、単一のメモリ間コピー命令を使用する OISC では、書き込み時に算術演算と命令ポインタ ジャンプを実行するトリガー ポートによってこれが実行されます。

算術ベースのチューリング完全マシンは、算術演算と条件付きジャンプを使用します。前の 2 つの汎用コンピュータと同様に、このクラスもチューリング完全です。命令は整数に対して実行されますが、整数はメモリ内のアドレスである場合もあります。

現在、このクラスの OISC は、さまざまな算術演算に基づいていくつか知られています。

• 加算（addleq、ゼロ以下の場合は加算して分岐）^[6]
• デクリメント（DJN、ゼロでなければデクリメントして分岐（ジャンプ） ）^[7]
• 増分（P1eq、Pに1を足し、別の値と等しい場合は分岐）^[8]
• 減算（減算、減算、ゼロ以下の場合は分岐）^[9] [ ^10]
• 可能な場合は正の減算、そうでない場合は分岐（算術機械）^[11]

単一命令の一般的な選択肢は次のとおりです。

• 0以下の場合は減算して分岐する
• 減算して負の場合は分岐する
• 正の場合は減算、それ以外の場合は分岐
• 逆引きして、借りる場合はスキップする
• 移動（トランスポートトリガーアーキテクチャの一部として使用される）^[12]

• 減算してゼロでない場合は分岐する (SBNZ a、b、c、宛先)
• Cryptoleq (異種暗号化および非暗号化計算)

特定の実装では、これらの命令のうち1 つだけが使用されます。したがって、どの命令を実行するかを識別するためのオペコードは必要ありません。命令の選択はマシンの設計に固有のものであり、OISC は通常、使用する命令にちなんで命名されます (例: SBN OISC、 ^{[2] : 41} SUBLEQ 言語、^{[3] : 4}など)。上記の各命令を使用して、チューリング完全な OISC を構築できます。

この記事では、トランスポート トリガーではない減算ベースの命令のみを紹介します。ただし、加算などの他の算術演算に基づく命令を使用してチューリング完全なマシンを構築できます。たとえば、DLN (ゼロでない場合は減算してジャンプ) と呼ばれるバリエーションには、オペランドが 2 つしかなく、減算を基本操作として使用します。詳細については、Subleq 派生言語 [1] を参照してください。

命令SBNZ a, b, c, d （「減算してゼロでない場合は分岐」）は、アドレスaの内容をアドレスbの内容から減算し、その結果をアドレスcに格納し、結果が 0 でない場合は制御をアドレスdに移します（結果がゼロの場合は、次の命令に進みます）。^[3]

subleq命令（「減算してゼロ以下の場合は分岐」）は、アドレスaの内容をアドレスbの内容から減算し、その結果をアドレスbに格納し、結果が正でない場合は制御をアドレスcに移します（結果が正の場合は、実行は次の命令に進みます）。^{[3] ：4–7}疑似コード：

命令 subleq a, b, c
    メモリ[b] = メモリ[b] - メモリ[a]
    (Mem[b] ≤ 0)
        の場合、 c
へ進む

条件分岐は、3 番目のオペランドを次の命令のアドレスに設定することで抑制できます。3 番目のオペランドが書き込まれていない場合は、この抑制が暗黙的に行われます。

2 つのオペランドと内部アキュムレータを使用するバリアントも可能です。この場合、アキュムレータは最初のオペランドで指定されたメモリ位置から減算されます。結果はアキュムレータとメモリ位置の両方に格納され、2 番目のオペランドは分岐アドレスを指定します。

命令 subleq2 a, b
    Mem[a] = Mem[a] - ACCUM
    ACCUM = メモリ[a]
    (Mem[a] ≤ 0)
        の場合、 b
へ進む

この場合、命令ごとに 3 つではなく 2 つのオペランドのみが使用されますが、さまざまな論理演算を実行するには、それに応じてより多くの命令が必要になります。

subleq命令のみを使用して、多くの種類の高階命令を合成することが可能である。^{[3] ：9–10}

無条件分岐:

JMP c

  部分集合Z 、Z 、c   

加算は、条件分岐なしで減算を繰り返すことによって実行できます。たとえば、次の命令では、場所aの内容が場所bの内容に追加されます。

a、bを加える

  部分集合a 、Z部分集合Z 、b 部分集合Z 、Z  
    
    

最初の命令は、位置aの内容を位置Zの内容 (0) から減算し、その結果 ( aの内容の負数) を位置Zに格納します。2 番目の命令は、この結果をbから減算し、その差 (元のaとb の内容の合計) をbに格納します。3 番目の命令は、値 0 をZに戻します。

コピー命令も同様に実装できます。たとえば、次の命令を実行すると、場所bの内容が場所aの内容に置き換えられます。ここでも、場所Zの内容は0 のままであると仮定します。

移動 a, b

  部分集合b 、b部分集合a 、Z部分集合Z 、b 部分集合Z 、Z  
    
    
    

任意の算術テストを構築できます。たとえば、次の命令から、ゼロの場合の分岐条件を組み立てることができます。

BEQb、c

  サブレクb 、Z 、L1サブレクZ 、Z 、OUT L1:サブレクZ 、ZサブレクZ 、b 、c OUT: ...   
     

    
     

  

Subleq2 は高次の命令を合成するためにも使用できますが、通常、特定のタスクにはより多くの操作が必要になります。たとえば、特定のバイトのすべてのビットを反転するには、少なくとも 10 個の subleq2 命令が必要です。

ではない

  subleq2 tmp ; tmp = 0 (tmp = 一時レジスタ) 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 ; tmp を acc にロードsubleq2 a ; a' = - a - 1 ( = ~a ) subleq2 Z ; Z を 0 に戻す           
   
             
               
               
             
               
             
               
               

次のプログラム (疑似コードで記述) は、 subleqベースの OISCの実行をエミュレートします。

 intメモリ[]、プログラムカウンタ、a 、b 、cプログラムカウンタ= 0 while (プログラムカウンタ>= 0 ) : a =メモリ[プログラムカウンタ] b =メモリ[プログラムカウンタ+ 1 ] c =メモリ[プログラムカウンタ+ 2 ] if ( a < 0またはb < 0 ) :プログラムカウンタ= -1 else :メモリ[ b ] =メモリ[ b ] -メモリ[ a ] if (メモリ[ b ] > 0 ) :プログラムカウンタ+= 3 else :プログラムカウンタ= c     
   
    
       
       
       
            
           
     
             
            
               
         
               

このプログラムは、memory[]が非負の整数でインデックス付けされていることを前提としています。したがって、 subleq命令 ( a、b、c ) の場合、プログラムはa < 0、b < 0 、または実行されたc < 0への分岐を停止条件として解釈します。subleq ベースの言語で書かれた同様のインタープリタ(つまり、subleq命令の性質によって許可される自己変更コードを使用できる自己インタープリタ) は、以下の外部リンクにあります。

Dawn OSと呼ばれる汎用SMP対応64ビットオペレーティングシステムが、エミュレートされたSubleqマシンに実装されています。このOSにはCのようなコンパイラが含まれています。仮想マシンの一部のメモリ領域は、キーボード、マウス、ハードドライブ、ネットワークカードなどの周辺機器に使用されます。このOS用に書かれた基本的なアプリケーションには、メディアプレーヤー、ペイントツール、ドキュメントリーダー、科学計算用計算機などがあります。^[13]

グラフィックディスプレイとキーボードを備えた32ビットのSubleqコンピュータ「Izhora」は、Yoel Matveyevによって大規模なセルラーオートメーションのパターンとして構築されました。 ^{[14] [15]}

Oleg Mazonkaによって書かれたHigher Subleqと呼ばれるコンパイラがあり、これは簡略化されたCプログラムをsubleqコードにコンパイルします。^[16]

あるいは、リチャード・ジェームズ・ハウが書いた、Subleq VM上で動作し、Subleqマシンの対話型プログラミングが可能なセルフホスティングForth実装がある^[17]

subneg命令（「減算して負の場合は分岐する」）はSBNとも呼ばれ、subleqと同様に定義される：^{[2] ：41、51–52}

命令 subneg a, b, c
    メモリ[b] = メモリ[b] - メモリ[a]
    (Mem[b] < 0)
        の場合、 c
へ移動します

条件分岐は、3 番目のオペランドを次の命令のアドレスに設定することで抑制できます。3 番目のオペランドが書き込まれていない場合は、この抑制が暗黙的に行われます。

subneg命令のみを使用して、多くの種類の高階命令を合成することができます。簡単にするために、ここではsubleqとsubnegの違いを示すために、合成された命令を 1 つだけ示します。

無条件分岐: ^{[2] : 88–89}

JMP c

  サブ負POS 、Z 、c   

ここで、ZとPOS はそれぞれ 0 と正の整数を含むように事前に設定された場所です。

無条件分岐は、 Z に最初に 0 (またはPOSに格納されている整数より小さい値) が含まれている場合にのみ保証されます。 Zの内容を 0 に維持する必要があると仮定すると、分岐後にZ をクリアするための後続の命令が必要です。

オペランドが 4 つの場合のバリアント (subneg4) も可能です。被減数と減数を逆にすると、ハードウェアでの実装が容易になります。結果が非破壊的であるため、合成命令が簡素化されます。

命令 (* 減数、被減数、結果、ジャンプ アドレス *)subneg s, m, r, j
    
    Mem[r] = Mem[m] - Mem[s]
    (Mem[r] < 0)
        の場合、 j
へ進む

チューリング マシンをより直感的にするために、ZA Melzak は正の数の計算タスクを検討しました。マシンには無限のそろばんと、最初は特別な場所 S にある無限の数のカウンター (小石、タリー スティック) があります。マシンは次の 1 つの操作を実行できます。

場所 X から場所 Y にあるのと同じ数のカウンターを取り出し、場所 Z に転送して、命令 y に進みます。

Xに十分なカウンターがないためこの操作が不可能な場合は、そろばんをそのままにして命令nに進みます。^[18]

すべての数字を正の値に保ち、現実世界のそろばんで計算する人間のオペレーターを模倣するために、減算の前にテストが実行されます。疑似コード:

命令 if (Mem[X] < Mem[Y])
         goto nmelzak X, Y, Z, n, y
    
    メモリ[X] -= メモリ[Y]
    メモリ[Z] += メモリ[Y]
    行く​

乗算、gcd、n番目の素数の計算、任意の数のb進数での表現、大きさの順序によるソートなど、いくつかのプログラムを示した後、Melzak は、彼の算術マシンで任意のチューリング マシンをシミュレートする方法を明示的に示します。

MUL p、q の倍数

multiply: 
melzak P 、ONE 、S 、stop ; 1 つのカウンターを P から S に移動します。不可能な場合は、stop に移動します。melzak S 、Q 、ANS 、multiply 、multiply ; q 個のカウンターを S から ANS に移動します。最初の命令に移動します。stop:                      
         

ここで、メモリ位置 P はp、 Q はq、 ONE は 1 、 ANS は最初は 0 で最後にpq、 S は大きな数です。

彼は、再帰関数の要素を使用して、算術マシンで計算可能なすべての数値が計算可能であることが簡単に示されると述べています。その証明は、Lambek ^[19]によって、同等の2つの命令マシンで与えられました：X+（Xをインクリメント）とX− else T（空でない場合はXをデクリメントし、そうでない場合はTにジャンプします）。

逆減算および借用スキップ(RSSB) 命令では、アキュムレータがメモリ位置から減算され、借用があった場合 (メモリ位置がアキュムレータより小さかった場合)、次の命令がスキップされます。結果はアキュムレータとメモリ位置の両方に格納されます。プログラム カウンタはメモリ位置 0 にマップされます。アキュムレータはメモリ位置 1 にマップされます。^[2]

命令 rssb x
    ACCUM = メモリ[x] - ACCUM
    メモリ[x] = ACCUM
    (ACCUM < 0)
        の場合、 PC + 2
に移動します。

x を y から z を引いた値に設定するには:

# まず、z を宛先位置 x に移動します。
RSSB temp # acc、temp をクリアするには 3 つの命令が必要です [注 1 を参照] RSSB temp RSSB temp RSSB x # acc はすでにクリアされているため、2 つの命令で acc、x をクリアしますRSSB x RSSB y # y を acc にロードします。借用はありませんRSSB temp # -y を acc、temp に格納します。常に借用してスキップしますRSSB temp # スキップしましたRSSB x # y を x、acc に格納します# 次に、操作を実行します。RSSB temp # acc、temp をクリアするには 3 つの命令が必要ですRSSB temp RSSB temp RSSB z # z をロードしますRSSB x # x = y - z [注 2 を参照]    
   
   
       
   
       
    
    
       

    
   
   
       
       

• [注 1] 「temp」に格納されている値が最初は負の値であり、このルーチンの最初の「RSSB temp」の直前に実行された命令が借用された場合、ルーチンが機能するには 4 つの「RSSB temp」命令が必要になります。
• [注 2] 「z」に格納された値が最初に負の値である場合、最後の「RSSB x」はスキップされ、ルーチンは機能しません。

トランスポートトリガーアーキテクチャは移動命令のみを使用するため、元々は「移動マシン」と呼ばれていました。この命令は、あるメモリ位置の内容を別のメモリ位置に移動し、新しい位置の現在の内容と組み合わせます。^{[2] : 42  [20]}

命令（  a -> bとも表記）movx a, b
    OP = GetOperation(Mem[ b ])
    Mem[ b ] := OP(Mem[ a ], Mem[ b ])

実行される演算は、宛先のメモリ セルによって定義されます。一部のセルは加算に特化しており、他のセルは乗算などに特化しています。したがって、メモリ セルは単純なストアではなく、セルの現在の値を使用して 1 種類の演算のみを実行する算術論理ユニット(ALU) セットアップと結合されています。一部のセルは、ジャンプ、条件付き実行、サブルーチン、if-then-else、for-loopなど でプログラム実行を変更する制御フロー命令です。

MAXQと呼ばれる商用トランスポートトリガーアーキテクチャマイクロコントローラが開発され、移動命令のすべての可能な宛先を表す「転送マップ」を使用することでOISCの明らかな不便さを隠しています。^[21]

Cryptoleq ^[22]はSubleqに似た言語である。これは1つの同名の命令で構成されており、暗号化されたプログラムに対して汎用計算を実行することができる。Cryptoleqは直接および間接アドレス指定を使用してメモリの連続セルで動作し、3つの値A、B、Cに対して 2つの操作O ₁とO _{2を実行する。}

命令 
    Mem[b] = O 1 (Mem[a], Mem[b])
     if O 2 (Mem[b]) ≤ 0cryptoleq a, b, c
        IP = c
    それ以外
        IP = IP + 3

ここで、a、b、c は命令ポインター IP によってアドレス指定され、IP の値は a をアドレス指定し、IP + 1 は b を、IP + 2 は c を指します。

Cryptoleq 演算では、O ₁とO _{2 は}次のように定義されます。

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

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

Subleq との主な違いは、Subleq ではO ₁ ( x,y ) は単にxからy を減算し、O ₂ ( x ) はxに等しいことです。 Cryptoleq も Subleq と準同型であり、モジュラー反転と乗算は減算と準同型であり、値が暗号化されていない場合、 O ₂の演算は Subleq テストに対応します。 Subleq で書かれたプログラムは Cryptoleq マシンで実行できるため、下位互換性があります。 ただし、 Cryptoleq は完全に準同型の計算を実装しており、乗算が可能です。 暗号化されたドメインでの乗算は、リバースエンジニアリングが困難であると想定され、 O 2_演算に基づいて値の再暗号化を可能にする独自の関数 G によって支援されます。

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

ここで、 はyの再暗号化された値であり、はゼロで暗号化されています。xは変数の暗号化された値で、mとすると、⁠ ⁠と等しくなります。 ${\displaystyle {\tilde {y}}}$${\displaystyle {\tilde {0}}}$${\displaystyle {\bar {x}}}$${\displaystyle Nm+1}$

乗算アルゴリズムは加算と減算に基づいており、関数 G を使用し、条件ジャンプや分岐はありません。Cryptoleq 暗号化はPaillier 暗号システムに基づいています。

• フラクトラン
• ブール代数の最小公理
• レジスターマシン
• チューリングタールピット
• 縮小命令セットコンピュータ
• 複合命令セットコンピュータ
• 明示的に並列命令の計算
• 最小命令セットコンピュータ
• 非常に長い命令語
• ゼロ命令セットコンピュータ

• 難解なプログラミング言語に関するWikiのSubleq – インタプリタ、コンパイラ、例、派生言語
• YouTubeのChristopher Domas によるReductio ad absurdum
• 実験室サブレクコンピュータ - VHDLを使用したFPGA実装
• レトロコンピューティング博物館 – SBN エミュレーターとサンプル プログラム
• 研究室用SBNコンピュータ – 7400シリーズ集積回路で実装
• 難解なプログラミング言語に関する wiki の RSSB – インタプリタと例
• Dr. Dobb の 32 ビット OISC 実装 - Verilogを使用したFPGA上のトランスポート トリガー アーキテクチャ (TTA)
• MAXQアーキテクチャの紹介 - 転送マップ図を含む
• OISC エミュレータ – グラフィカル バージョン
• TrapCC (最近の Intel x86 MMU は実際にはチューリング完全な OISC です。)
• Izhora – セルラーオートメーションとして構築されたヨエル・マトヴェイエフのSubleqコンピューター
• SBN シミュレーター – CARDboard Illustrative Aid to Computationにインスパイアされたシミュレーターとデザイン
• 60 ヘルツの 1 ビット コンピューティング – コンピューターとステート マシンの中間
• NOR マシン – たった 1 つの命令で CPU を構築する方法
• SUBLEQ eFORTH SUBLEQ OISC 上で実行される完全な Forth インタープリター。
• Cryptoleq – Cryptoleq リソース リポジトリ
• CAAMP – コンピュータアーキテクチャのミニマリスト的視点
• SICO – シングル命令コンピュータ: 符号なし整数を使用する SUBLEQ の変種