木曜日, 5月 23, 2013

命令セット

現在設計中のプロセッサは、命令語長4ビット、データ語長32ビットの合わせて36ビット幅で内部メモリへのアクセスを行います。

命令フェッチの際、4ビット長の命令と同時に読み出された32ビット長のデータを、命令実行の際のオペランドYとします。

 

 命令(4ビット)  オペランドY(32ビット)

 

レジスタとしては、プログラムカウンタPCの他に、32ビットのレジスタXに1ビットのキャリーフラグCを付加した33ビット長のアキュムレータAccを持ちます。

 

 プログラムカウンタPC

 

アキュムレータAcc(33ビット):

 キャリーフラグC  レジスタX(32ビット)

 

ちなみにDE0-Nano上のFPGA(EP4CE22)では36ビット×16Kワードの内部メモリが確保可能なので、プログラムカウンタPCは14ビットになります。

その他、各プロセッサ要素固有の内部状態として、排他制御用のロック状態フラグlockがあります。ロック状態フラグはLOCK(TRYLOCK)命令でセットされ、UNLOCK命令でリセットされます。ロック状態のセットは対象となるプロセッサでしか実行できませんが、リセットはオペランドでプロセッサを指定できるので、任意のプロセッサで実行可能です。

命令コードとその動作内容を、内部状態の変化として表したものが以下の表になります。ただし、これはあくまでも暫定的なもので、実装の都合により変更される可能性があります。(8/16変更しました)

 

コード Y[31..28] 命令 PC関連 Acc関連 その他動作内容
0000   GET, DATA PC := X X := Y  
0001 0000  JUMP PC := Y    
0001 0001 JUMPNZ if(X!=0) PC := Y
else PC := PC + 1
   
0001 0010 JUMPNP if(X<=0) PC := Y
else PC := PC + 1
   
0001 0011  JUMPM if(X<0) PC := Y
else PC := PC + 1
   
0001 0100 JUMPNM if(X>=0) PC := Y
else PC := PC + 1
   
0001 0101 JUMPP if(X>0) PC := Y
else PC := PC + 1
   
0001 0110 JUMPZ if(X==0) PC := Y
else PC := PC + 1
   
0001 0111 UNLOCK PC := PC + 1   unlock(Y)
0001 100- JUMPNC if(C==0) PC := Y
else PC := PC + 1
   
0001 101- JUMPC if(C==1) PC := Y
else PC := PC + 1
   
0001 110- TRYLOCK if(!lock) PC := Y
else PC := PC + 1
  lock := 1
0001 111- LOCK if(lock) PC := Y
else PC := PC + 1
 
0010 code PUT if(collision) PC := PC
else PC := PC + 1
  if(!collision) [Y] := code:X
0011   HALT PC := PC    
0100   MUL PC := PC + 1 X := Y * X  
0101   MULH X := (Y * X) >> 32  
0110   SHIFT if(Y<0) Acc := X>>Y
else Acc := X<<Y
 
0111   IO Acc := io_port(Y, Acc)  
1000   LOAD X := Y  
1001   OR X := Y or X  
1010   AND X := Y and X  
1011   XOR X := Y xor X  
1100   ADD Acc := Y + X  
1101   SUB Acc := Y — X  
1110   ADC Acc := Y + X + C  
1111   SBB Acc := Y — X — C  

 

基本的に4ビットの命令コードで命令実行内容が決定されますが、一部ジャンプ命令等はオペランドYの上位4ビットを利用して命令の拡張が行われています。

ジャンプ命令は条件に応じてPCの値を変化させるものですが、その後PCの下位ビットがメモリバンクと一致しない間は内部的にHALT命令を実行し、回転待ちを行います。

PUT命令によるメモリ書込みは、実際にはスレッドが目的のメモリバンクに到達した時点まで遅延されます。ここでもし、あるバンクへの書き込みが未完了の状態で、また同一バンクへの書き込みを実行しようとした場合(collision=1)、一旦PC := PCとして一周分の回転待ちの間に全ての遅延書き込みを完了させた上で、再び書き込み命令を実行します。二度目の書き込みでは全ての遅延書き込みが完了しているため、今度は必ず成功します。

PUT命令によるオペランド書き換えの際、実際にはYの上位4ビットの値で命令コードの書き換えも行われます。これは、命令コードとオペランドを同一メモリにした方が効率が良い(パリティビットが使える)のと、排他制御の際に同時書き換えができた方が都合が良いといった理由があります。ただ、オペランドだけ書き換える際にも命令コードを指定しなければならないので、ハンドアセンブルの場合は若干面倒です。基本的には、こういった作業をコンパイラ等で自動化することを想定した設計となっています。

ここで、設計上最も悩ましいのがランダムアクセス読み出しです。このプロセッサでは配列やテーブルの機能を実現するために最低限必要な命令として、DATA命令を実装しています。DATA命令はLOAD命令と同様にオペランドYの値をレジスタXに代入しますが、同時に代入実行前のレジスタXで指定された番地へのジャンプも実行します。基本的な使い方としては、レジスタXに戻り番地を入れて目的のDATA命令へのジャンプを実行することになりますが、このジャンプの飛び先を変化させることでランダムアクセスが可能になります。とはいえ、いちいちジャンプ命令のオペランドを書き換えていたのでは、あまりに効率が悪くて話になりません。

ところがなんと、不思議なことに同じ命令を利用することでこれが解決します。

例えば、1000番地にデータとしてオペランド値123を持つDATA命令を置いたとします。100番地からのコードで、まずLOAD 1000でレジスタXに1000を代入し、次に101番地で次の命令番地の102をオペランドとするDATA命令を実行します。するとまず、101番地のDATA命令の結果、レジスタXの値は102となり、1000番地にジャンプします。次に1000番地のDATA命令の実行により、レジスタXの値は123となり、102番地へのジャンプが実行されます。この結果、101番地のDATA命令は、表面的にはレジスタXで指定した番地のデータを取得(X := [X])し、ついでにオペランドで指定された番地へのジャンプ(PC := Y)を実行する命令として動作します。101番地と1000番地のDATA命令は実行内容は同じですが、プログラム内での意味合いは全く違ったものになりますので、101番地の方は同じ命令コードでGETという名前を割り当てることにします。

 

PC 命令 Y X
100 LOAD 1000 1000
101 DATA(GET) 102 102
1000 DATA 123 123
102 次の命令…    

 

GET命令によるランダムアクセス読み出しは、ハードウェア的には簡単な命令を一つ実装するだけで済むので非常に低コストです。しかし、実行時にはジャンプを2回実行しなくてはならないため、回転待ちのコストが掛かります。特に、上の例の様にGET命令の戻り番地を命令の次の番地にした場合、必ず1周分の回転待ちが発生します。これがもし、GET命令、DATA命令、戻り番地を隣接するメモリバンクに配置することが可能であれば、回転待ちは2命令分にまで減少します。実際には、同じDATA命令にアクセスするGET命令が複数あると考えられるので、そう単純にはいきませんが、命令やデータの配置を工夫することで、実行効率の改善が期待されます。こういった最適化の技法は、今後興味深い研究対象として発展する可能性があります。

火曜日, 2月 12, 2013

マルチプロセッサの回路設計

それではまず、レジスタレスアーキテクチャの基本要素となる、アキュムレータマシンの回路を実際に設計してみましょう。

データの流れに従って、大まかにブロック図を描いてみます。アキュムレータマシンの内部状態は基本的に、プログラムカウンタ(PC)とアキュムレータ(Acc)のみになります。その他の状態フラグ等はとりあえず省略します。

dataflow_block.png

プロセッサは、古い内部状態(PC, Acc)をもとにメインメモリから命令とデータを同時に読み出し、演算命令やジャンプ命令を実行して新しい内部状態(PC’, ACC’)に更新します。また、PUT命令を実行する場合はメインメモリの書き換えも同時に実行します。新しい内部状態をまた古い内部状態の入力に接続すると、そのままシングルプロセッサの出来上がりです。簡単ですね。

メモリアクセスの出力とタイミングを合わせるため、内部状態は同じクロック数だけ遅延された上でプロセッサに入力されます。演算命令はアキュムレータの変更、ジャンプ命令はプログラムカウンタの変更として実現できるので、プロセッサ内部は基本的に組み合わせ回路のみで構成可能となります。そして、以下の前提のもとで、CPI(命令実行あたりのクロックサイクル数)を1にすることができます。

  1. メインメモリがデュアルポート(命令読み出しとデータ書き込みが同時に可能)
  2. メモリアクセスの遅延が1クロックのみ
  3. プロセッサ内部が組み合わせ回路のみで構成

最近のFPGAの埋め込みメモリはデュアルポートで1クロックアクセス可能なものが普通なので、上の条件は特に難しくありません。CPIを1とすることはプロセッサアーキテクチャにおける一つの目標であり、これを超えるには命令の先読みや命令レベル並列化といった複雑な技法が必要となります。したがって、プロセッサ単位ではこの程度の単純な構造に留め、あとはマルチプロセッサ化による性能改善を図ることにします。

このプロセッサを複数、内部状態の入出力を接続してリング状に結合すると、マルチプロセッサが出来上がります。メインメモリは、各プロセッサにバンク分割したものを割り当てますが、この構造のままでは、PUT命令による書き込みの際にプロセッサと同じバンクにしか書き込めないという問題が生じます。そういった不便さに目をつぶってなんとか使うという手もありますが、本質的にプロセッサ間でのデータ転送手段がアキュムレータ以外にないことになるので、単に不便なだけでなく、このままでは処理性能もあまり期待できないことになります。

dual_bad.png

実は、こういったリング状の構造(ネットワーク・トポロジー)を持つマルチプロセッサでは、回路がシンプルになる反面、ランダムアクセスに弱いという欠点があります。PUT命令はランダムアクセス書き込みのための命令ですが、他のバンクへの書き込みも間接的なプロセッサ間通信手段なので、できれば実現したいものです。とはいえ、単純に各プロセッサから全てのバンクに書き込み信号を接続したのでは、各バンクにプロセッサ数だけの書き込みポートが必要となり、せっかくリング状でシンプルな構造にしたのにこれでは台無しです。

quad_bad.png

実は、ランダムアクセス書き込みに関しては、メモリ一貫性の条件を緩和することで、この問題を回避することができます。例えば、ハードディスクの書き込みはヘッドのシークや回転待ちの関係もあって、即座に実行するのは難しいのですが、その間コンピュータが止まっていては話にならないので、大抵のOSは書き込みデータを一旦メモリに溜めて、後でまとめて遅延書き込みを行います。このマルチプロセッサでも、例えばバンク0への書き込みを、次にバンク0の読み出しを実行するまで遅延させても実際の動作には影響ありません。そこで、他のバンクへの書き込みを一旦保留して、そのバンクに到着した時についでに書き込みを行う方式を考えます。

dual_block.png

この方式では、プログラムが自分自身で書き込んだ内容を、ちゃんと読み出せることが保障されます。ただし、他のプログラムが書いた内容が、即座にメモリ内容に反映されるわけではありません。メモリ一貫性でいえば、プログラム内でのメモリ一貫性は保障されるものの、複数プログラム間でのメモリ一貫性は保障されないことになります。ただ、書き込み側のプログラムがプロセッサを一周する間にはメモリ内容にも反映されますので、こういった遅延を配慮したプログラムを書けば問題ありません。

quad_block.png

これは4プロセッサの例ですが、バンク書き込み信号が増えた分、配線は複雑になりますが、十分なプロセッサ間データ転送量を確保できる上に、各バンクメモリはデュアルポートで済むようになります。

ただし、ランダムアクセス読み出しに関しては、もう少し考える必要があります。

(つづく)

火曜日, 1月 22, 2013

アキュムレータマシンと自己書き換え

レジスタレスアーキテクチャによるマルチプロセッサは、ちょうどこんな風に、プログラムがプロセッサの上をぐるぐる追いかけっこしながら実行するイメージになります。

smp_image.png

プログラムがプロセッサ間を移動するためにはできるだけ身軽な方が良いので、なるべくレジスタの少ないアーキテクチャを採用することになります。こういったアーキテクチャの代表格に、アキュムレータマシンがあります。アキュムレータマシンは、例えば以下の様な形式の命令を実行します。

ADD メモリアドレス

これは実際には、唯一の汎用レジスタであるアキュムレータAccの値に、メモリアドレスで指定されたメモリの内容を足す命令になります。

Acc ← Acc + (メモリの内容)

アキュムレータマシンは回路が非常にコンパクトになる反面、メモリアクセスが多くなるため高速化にはあまり向きません。例えば上の「ADD メモリアドレス」の場合、まずADD命令とメモリアドレスの読み出しで最低1回、そしてメモリ内容の読み出しでもう1回、最低でも計2回のメモリアクセスが必要となります。

現在のプロセッサは、なるべくメモリアクセスを減らす方向に進化を続けていますので、それに反するアキュムレータマシンは古典的なものとしてほとんど忘れ去られてしまいました。しかし、この弱点を除けば、小規模マルチプロセッサの要素として望ましい性質を備えています。そこで、アキュムレータマシンを改良して、小規模マルチプロセッサに組み込むことを考えます。

もしアキュムレータ以外にレジスタがあれば、メモリアドレスの代わりにレジスタ番号を指定して

ADD レジスタ番号 { Acc ← Acc + レジスタ }

とすることで、メモリアクセスの1つをレジスタ読み出しに置き換えることができます。それでも、レジスタ読み出しにはまずレジスタ番号が確定する必要があるので、命令読み出しと同時には実行できません。実際には、以下の4つの段階に分けて命令が実行されます。

  1. 命令読み出し
  2. レジスタ読み出し
  3. 足し算の計算
  4. 結果の書き込み

現在多くのプロセッサは、これらの段階をパイプライン処理で同時に実行して、高性能をたたき出しています。しかし、実際にこの方法で性能を発揮させるには様々な工夫が必要であり、現在のプロセッサの複雑化の一因となっています。

結局、レジスタを使ったとしても、命令実行のためのパラメータ(足し算の場合は+の左辺と右辺)が命令読み出しと同時に確定しない限り、こういった問題はどうしても避けられません。手立てはただ一つ、命令のパラメータを固定値(イミディエイト/即値)に限定することです。足し算命令の場合はこうなります。

ADD 固定値 { Acc ← Acc + 固定値 }

命令とパラメータを同時に読み出せれば、メモリアクセスは1回で済みます。その後すぐに足し算ができますので、基本的に複雑なパイプラインは不要となります。もちろん、パラメータが固定値だけではプロセッサとして使い物になりませんが、これについてはコードの書き換えを用いることで解決が可能です。具体的には、パラメータで指定されたアドレスにある命令のパラメータを、現在のアキュムレータの値に書き換えるPUTという命令を用意します。

PUT 命令アドレス { [命令アドレス] ← Acc }

PUT命令自体の命令アドレス指定も他のPUT命令で書き換えられるので、配列や可変アドレスでも大丈夫です。この命令があることで、あらゆる命令のパラメータを、事実上の汎用レジスタとして利用することが可能になります。

コードの自己書き換えは、現在のプロセッサでは特別な場合を除いてほとんど使われないテクニックです。セキュリティやメモリ保護の問題もありますが、何よりもキャッシュメモリやパイプライン処理において、コード書き換えの処理が非常に効率が悪いというのが理由だと考えられます。このように現在ではすっかり主流から外れてしまった自己書き換えという手法を、レジスタレスアーキテクチャでは積極的に利用します。

まとめると、レジスタレスアーキテクチャは、アキュムレータマシンと自己書き換えという、現在主流から外れてしまったテクニックを、小規模マルチプロセッサの要素として復活させたものになります。

(つづく)

金曜日, 1月 18, 2013

マルチプロセッサとメモリアクセス

近年、ノートPCや携帯機器までマルチコアが普通に載るようになってきて、今ではスマートフォンにまでクアッドコア(4CPU)が登場するようになりました。だったらもっと載せればいいじゃないという話になりそうですが、実際はそう簡単にはいきません。

世の中のプログラムは必ずしも並列化できない(アムダールの法則)というのもありますが、もし並列化できたとしても、メモリアクセスの限界(フォン・ノイマン・ボトルネック)で、どうしても性能が抑えられてしまいます。CPUが計算するためには、まずメモリからプログラムとデータを読んで、計算結果をメモリに書き込む必要があります。CPUだけがどんなに速くても、メモリアクセスが間に合わなければ、全く意味がないわけです。

では、現在のマルチプロセッサはどのようにしてこの問題に対処しているのでしょうか?

cache_memory.png

現在、世の中に出回っている大部分のマルチコアプロセッサが、基本的にはこのような分散キャッシュメモリを持つ構成になります。この構成では各プロセッサは必要となるプログラムやデータの一部分をキャッシュメモリにコピーして使うので、共有メモリへのアクセスは格段に減ります。マルチコアプロセッサでは通常、キャッシュメモリと共有バスは外部の共有メモリよりも遥かに高速で動作しますので、ちゃんとプロセッサが増えただけの性能を発揮することができます。

キャッシュメモリの容量はプロセッサの性能に直結するので、今やプロセッサの中で最も電力と面積を必要とする部品となっています。キャッシュメモリは元々、外部メモリとプロセッサ内部の速度差を埋める役割を果たしていたのですが、マルチコアになるとキャッシュ一貫性によりメモリの同時アクセスのために欠かせない機構となりました。でも、メモリを内蔵する構成のプロセッサにおいては、当然ながら無用の長物です。

では、メモリを内蔵する小規模なマルチプロセッサは、どのような構成にすればよいでしょうか? まず考えられるのは、力技です。

shared_memory.png

マルチポートメモリを利用することにより、共有メモリとプロセッサを直結することが理論的には可能です。ですが、面積効率が悪く(ポート数の2乗に比例するといわれている)、またFPGAでは利用できないため(大抵は2ポートまで)、この方式は却下となります。

もう一つ考えられるのは共有メモリを諦めてプロセッサ毎に専用のメモリを持たせ、代わりに通信用のバスを用意する方式です。ハードウェアの設計が楽なのでこの構成は比較的よく見られ、例えばPS3Cellプロセッサはこれに近い構造となっています。

local_memory.png

これはハードウェア設計は楽なのですが、ソフトウェアの方は大変です。特に小規模の場合、ただでさえ少ないメインメモリが、プロセッサ毎に分割されてしまうのは論外といえます。無理やり他のプロセッサのメモリをアクセスする構成も考えられなくはないですが、プロセッサに負荷が掛かる分、複雑な割に効率が悪そうです。

共有メモリの分割をプロセッサ毎ではなく、アドレス領域に応じたメモリバンク分割にすることにより、また違った構成が考えられます。

crossbar_switch.png

クロスバースイッチにより、複数のプロセッサが別々のメモリバンクにアクセスする限りにおいて、同時アクセスが可能となります。ただし、複数のプロセッサが同一のバンクにアクセスしようとした場合には、一つを除いて他のアクセスがブロックされます。プロセッサが増えるとクロスバー機構が急激に肥大化するのが問題ですが、それをうまく簡略化するための研究が昔から盛んなようです。(例えばこことか)

もしここで、アドレスをプロセッサ数で割った余りでメモリバンク分割すると、面白いことが起きます。例えば上の図でメモリバンク0~3を、アドレスを4で割った余りが0から3の領域のメモリとします。もしある時点で4つのプロセッサの実行アドレスが100, 201, 302, 403とすると、それぞれ4で割った余りは0, 1, 2, 3となるので同時に別々のメモリから命令読み出しアクセスができます。次の時点では実行アドレスが101, 202, 303, 404となるので余りは1, 2, 3, 0となり、また同時アクセスが可能です。こうして、ジャンプ命令を実行しない限り、4つのプロセッサは同時アクセス可能な状態を維持し続けます。

この状況で、プロセッサ自体を回転させることができれば、クロスバー機構がまったく要らなくなります。回転といってもIC内部で物理的に回転させるわけにはいかないので、実際には全ての内部状態を信号としてつないで転送することになります。

cyclic_smp.png

プロセッサの内部状態というと、当然全てのレジスタの値も含まれますので、レジスタがたくさんある場合にはそれも全部隣に送らないといけません。つまりこの場合、レジスタが少なければ少ないほど有利なわけです。

ここで、レジスタレスアーキテクチャによる小規模マルチプロセッサの可能性が浮かび上がってきます。

(つづく)

火曜日, 1月 15, 2013

レジスタレスアーキテクチャとは

レジスタレスアーキテクチャとは、文字通りレジスタを省略したマイクロプロセッサアーキテクチャです。

とはいえ、レジスタが全く無いプロセッサでは何もできないので、実際には必要最小限のレジスタを持ち、さらにメインメモリを汎用レジスタとしても利用できるプロセッサということになります。

RISC出現以前の古典的なプロセッサでは、こうしたメインメモリをレジスタの代わりとして利用できる形式のものがよく見られました。その中でも特に有名なのは、Apple II初代ファミコンで使われた8ビットCPUの6502です。6502はプロセッサ内部のレジスタが少ない代わりに、メインメモリの0番地から255番地までの256バイトの領域を、ゼロページとして事実上汎用レジスタのように利用可能であるという特徴がありました。この当時はCPUクロックも1~2MHz程度で、プロセッサ内部のレジスタと外部のメインメモリの速度差があまりないことから、こういった設計もアリでした。

現在の高性能プロセッサは内部ではGHz単位で動作しますので、外部メモリとの速度差を埋めるために大量のレジスタやキャッシュメモリが欠かせません。しかし、FPGAをメインメモリとプロセッサが同居するマイクロコントローラとして利用する場合には、少し事情が変わってきます。この構成では外部にメモリを接続しなくてもよい代わりに、貴重な内部メモリ資源をレジスタやメインメモリに振り分けなければならないため、あまり大量のレジスタを持つとそれだけメインメモリを圧迫してしまうことになります。そして、レジスタとメインメモリは結局同じ内部メモリを使うことになるので、レジスタによるメインメモリアクセスの削減は、もともとあまり意味がないわけです。

ということで、FPGA内部の埋め込みメモリを、全てメインメモリとして利用可能であるのが、このアーキテクチャの第一の意義であるといえます。

そして、このアーキテクチャのもう一つの重要な意義は、マルチコア化にあります。マルチコアとはマルチプロセッサの一形態で、大まかにいえば、一つのICパッケージ内に複数のプロセッサを詰め込んだものです。昔はICの実装密度が低く、プロセッサが別々のパッケージに分かれているのが普通でした。しかし、プロセッサの信号は本数が多い上に高速で、その分基板設計は大変でした。ICの実装密度が上がるにつれてマルチコア化が可能となり、コンパクトな上に基板設計が楽なので、今ではほとんどのマルチプロセッサがマルチコアとなりました。

高速な信号を基板上に出した途端、素人にはとても手の出せないものになりますが、FPGA内部であれば、せいぜい設計ツールとの格闘でなんとかなります。マルチコアプロセッサとメインメモリを同一のFPGA内に収めれば、あとはハードウェア記述言語で書ける世界なので、これが素人がマルチコアを設計するための、現状ではほぼ唯一の手段となります。ただし、そのためには一つのFPGAパッケージ内に収まるだけの、(常識的にはありえない)コンパクトな回路でマルチコアプロセッサを実現する必要があります。レジスタレスアーキテクチャは、そのための設計論でもあります。

(つづく)