FPGAの掲示板まとめ
Ver.1.000 2014.11.1
更新履歴
2014.11.01 Ver.1.000 新規作成
8BIT単位でこれを複数もつ。2個ペアで使うと16ビット、4個なら32ビットという風に。
桁上がりがあるので、ペアと言っても微妙に動作が違ってきます。バイト単位にずらしてスタートする。
8ビット演算が複数あるときは同時並行。
ビット数が全体を超えない範囲で並列化。
1ユニットマイクロプログラムを全体的に組めば桁数が稼げるし、マイクロプログラムを分断させれば並列になる。
処理を全て表で持てば、ほとんど間接アドレッシングで構成できる。
演算も極力、変換表で済ませるというのはどうかな。
CPUという機能だけで解決するということ固執せず、システムとして動作すると考える。
> No.14[元記事へ]
> 8BIT単位でこれを複数もつ。2個ペアで使うと16ビット、4個なら32ビットという風に。
> 桁上がりがあるので、ペアと言っても微妙に動作が違ってきます。バイト単位にずらしてスタートする。
これだと32bitは4クロックかかると思うかもしれませんが、連続的に演算をさせるとパイプラインですから1クロックで32bit演算することになりま
す。
べつに、8bit単位でも連続的に動けば64bitでもパイプラインとしては1クロックで動きます。
要するにパイプラインに次々とデータを流しつづけることができれば、1クロックで演算ができるのです。
そこで、マイクロプログラムコンパイラは、その点を重点的に調整する必要があります。
データにタグをつけてパイプラインをバラバラに流れても出口で並び替えると言う方法もあるかもしれません。もちろん、下からの、あるいは上へのキャリーな
どのフラグもタグにくっつけます。
パイプラインを必要以上に長くします。演算、並び替え、演算、並び替えと言う具合です。
すると途中での並び替えもパプライン処理に組み込まれて、表にロスとして表れません。
また、入口を広くして、出口を狭くするのも効率があがっていいかもしれません。
あと、パプラインの段間のバイパスによるすき間の詰めもあるといいでしょう。
それらが、すべて機能するには、必要以上長くしておいた方が、出口で隙間なくデータを出すことができます。
すると、問題になるのは分岐ですか?
分岐といってもいくつか分類されます。
1)レンジチェック 値が適当かのチェック IF ELSE など
2)繰り返し 繰り返すのが通常で抜けることはまれ
3)SWITCH CASE文 どこに分岐するか予測しにくい。TABLE Jampとできる
4)Go これで終わりということ
5)CALL文 Goと同じ。戻ってくるだけ
大体このくらいに分類されます。繰り返しは、予測ができます。
GoとかCallはOSに制御を移して、タスクスイッチにしてしまった方が楽かもしれない。
短いループやCallはあるサイズ以下は展開してしまうとよいかもしれない。
時間待、フラグ待ちなどはOSに制御を移して、タスクスイッチにしてしまう。
パイプラインを2系統用意して結論が出るまで分岐した場合としなかった場合を同時に実行して結論で片方を捨てるとか...
これだとパイプラインが長くてもなんとかなるかな....
ペナルティは0。
分岐命令までの距離が、あるときはパイプラインは2命令同時進行、分岐命令が近づくと分岐したときとしなかったときに動作が分かれるというのはどうかな。
if a then {b} // @a →{b}
else
//
{
if c then {d }else // A(!a & c)→{d}
{if e then {f} // B(!a
& !c & e)→{f}
}
}
これは,以上から,@,A,Bの3つの文の並行として解釈できます。
このように,b,dとc,eの分岐が相互に依存してなければ、同時実行ができます。
マイクロプログラムへのコンパイルは専用プロセッサが複数あり、実行ユニットはそのマイクロプログラムで動きます。実行ユニットは能動的に状況にあわせて
ダイナミックにマイクロプログラムを実行します。したがって、マイクロプログラムの入れ替え等がおきます。
同時に2つ上の命令を実行しますからそうならざるをえません。
>
マイクロプログラムへのコンパイルは専用プロセッサが複数あり、実行ユニットはそのマイクロプログラムで動きます。実行ユニットは能動的に状況にあわせて
ダイナミックにマイクロプログラムを実行します。したがって、マイクロプログラムの入れ替え等がおきます。
> 同時に2つ上の命令を実行しますからそうならざるをえません。
さて、そうなるとパイプラインからでてきたデータは一体どれのものかとなるので、データにはプロセスIDのタグをつけておかなばなりませんね。また、パイ
プラインにながれているデータと対になるデータの識別のためにもプロセスIDのタグをつけておかなばなりませんね。ついでにプロセスIDのタグに処理(例
えば加算とか被減数とか)もつけておく必要があります。
実行ユニットはそのタグをみて処理すればいいのではないでしょうか。
まあ、これは「CPUを考える」で考えたことに近くなるなあ。
今クラウドコンピューティングが流行だけど、パイプラインがあってIDタグのついたデータがぐちゃぐちゃにながれていて実行ユニットが処理の終わってない
データを処理してパイプラインに流すということかな。パイプラインの出口で隙間なくデータが流れ出れば、最高の処理速度であるということでしょ。
パイプラインにいれるデータとでるデータは2項演算が多ければいれる方が2倍多くなるのですよね。
まあ、積和演算では1倍ですが...
いずれにせよパイプラインからデータが隙間なく流れ出れば、2つのプロセスが同時にこなせるということですよね。つまり、実行性能は2倍までになる?
かってNTTがデジタル交換機を設計していたとき、パケットのサイズを小さくしてタグをつけたほうが、パケットサイズが大きいときより効率がいいと結論し
ました。
したがって、浮動小数点演算ユニットより、細かい2項演算に分解したほうが、単体では見劣りしますがパイプラインの流れ具合をMAXにするならば、その方
が全体性能が稼げるといえるのではないでしょうか。
命令をコンパイルしてロジックをRAMで構成して動的に書き換えてゆくのはどうかな。
そういうブロックを複数持つ。
すると最初から全ての場合を考えた巨大なサイズはいらないわけだ。
ブロックのサイズ内に収まるよう分割する。
すると、書き換えのロスタイムが生ずる。
回避策として、2ブロックをペアにしておく。
命令の実行においては、部分的に同じパターンが出てくる。
たとえば、アドレスの計算とか、スタックの処理とか...
すると、RAMに入れるパターンは、ある程度最初からROMで持っていられるということか。
つまり、マクロとして用意できるということだな。
6809だったかで、UserスタックとHardスタックと分けて、ハードウエア要因はHardスタックを使い、ソフト要因はUserスタックと分けてい
たけど、Userスタックってindexレジスタと大差ないもんね。
ポストインクリメント、デクリメントという修飾もあったけど、それとindexを組み合わせればUserスタックと同じだな。
ローカル変数はスタック上に置かれるんで、スタックってソフトとハードをわけるという発想は納得できるけど、スタックをindexレジスタにコピーすれば
済む話だし、大概コンパイラはそう実装しているんじゃないのかな...
そういうことからすると、indexレジスタは多いほど良い。
TMS9900は、レジスタファイルをメモリ上に持っていて何処にあるかをCPU内のワークスペースポインタというレジスタで管理していた。
レジスタが多いと、タスクのスイッチで大変面倒になる。
CPU内にたくさんレジスタを持たないという発想は、斬新でした。
TMS9900は、レジスタファイルをメモリ上に持っているのですが、メモリが遅いとCPUが遅くなりますが、最近のキャッシュが1MBもありますので、
ペナルティとしてそんなに大きくは作用しないでしょう。
PUSH_USP MACRO STACK_A,REG_A
;REG_Aで指定したレジスタを仮想STACK_Aにpush
PUSH
INDEX ;INDEXのセーブ
LOAD
INDEX,STACK_A ;仮想STACK_Aのロード
DEC INDEX
STORE
(STACK_A),REG_A;REG_AのPUSH
STORE
STACK_A,INDEX ;仮想STACK_Aの保存
POP
INDEX ;INDEXのPOP
ENDM
くらいのマクロを作っておけば,
PUSH_USP USER_STACK,A
という具合に使えるので、STACKには不自由しないと思います。
Gateのディレーが最大プロセスばらつき,最大電源電圧変動範囲、全温度範囲の条件でminが1nS、maxが5nsとします。10段重ねるとminが
10nS、max50nSになります。
すると、動作速度は50nSより遅くすることになります。たとえば,60nSとなるわけですよね。
そこで,パイプライン処理するわけですよね。
3段ごとにD-FFを入れるとします。D-FFのSetupタイムを2nSとすると5X3+2=17nSですから20nSサイクルとするわけですよね。
さて、ICのばらつきが局所的に小さいとなると、たとえば、先に例がGateのディレーがminが2nS、maxが3nsであると、もっとサイクルタイム
は早くできるしパイプラインの段数を減らせます。
そこで、ゲート回路の付近にリングインバータ発振器をおいて、メインクロックと同期してスタートさせるとGateのディレーと発振器のクロックは相間する
はずです。つまり、minとmaxのマージンは小さくできるはずです。
ローカルゲーテッドリングインバータ発振器とゲート回路のパイプラインを組むわけです。
あるいみ、非同期ですが...
パイプラインにDoneフラグをつけます。それでメインクロックに同期させます。
そういう方法は取れないですかね。
むかし、DECのalpha cpuはwindows ntまでサポートされていたが、アプリはなかった。
そこで、アプリをエミュレーションで実行しながら実行中にエミュレーション結果を保存して、何回か実行すると、alphaのコードに置き換わるというもの
でした。
そこで、実行中に流れを解析して、効率的なマイクロプログラムに置き換えてゆくのはどうだろうか。
パイプラインを出来るだけながくして、分岐命令では、2つのプロセスを同時にすすめる。
結論が出たら、パイプライン上の不要なデータは、伝搬させないのはどうかな。
すると、分岐命令から2つの実行ユニットが必要になる。
パイプラインの出口で常にデータが流れ続ければ、2項演算なら入力が2倍処理されるので実効速度が2倍になるのはまえにも述べたとおりなので、パイプライ
ンの出力を絶やさないことを工夫すればいいのです。
したがって、パイプラインの中のデータ数は変動します。でも、0にならなければ絶えることがありません。出口は固定ですから、したがって、パイプラインの
中でバイパスする必要があります。
それには、前にも述べたとおり、データにはタグをつけておく必要があります。
命令としては、例外処理を追加します。ルーチンは、例外設定をしてから、ループを回ります。異常がなければ、そのまま抜けます。ところが、オーバーフロー
などの例外がおきると例外設定に飛びます。
つまり、ループは、オーバーフローチェックなどをしないで回るので早くなります。
このように、例外処理を分けているので、プログラムが高速になります。
たとえば、ルーチンの設定したレンジを越えてないかいちいちチェックしなくてよいのです。問題がおきたら例外処理になるので、それだけ、プログラムもコン
パクトになります。
例外はソフトウエア割り込みになります。例外設定命令は、分岐命令とおなじで、JZならEJZという具合でJZがjump zero
が、ejzになると、zeroで例外割り込みを発生させるということです。
EJZは、zeroで例外割り込みを発生するようにするという命令で、EDEL(例外解除命令)の間で、zeroになると例外が発生するということです。
EDEL命令は、EJZが例外条件をPUSHし、EDELはPOPすることで、例外条件がスタック的につまれてゆくということです。
フラグの更新は、どうしたものかな。
例外処理では、フラグの反映は演算命令の結果によるとするか。
通常命令では、レジスタのロードによってフラグは更新されるとするとか。
例外処理は、それぞれ、エントリーポイントが分かれています。ソフトウエア割り込みですからね。
例外割り込みは、スタックになっていると前にも、書きましたが、例外命令の中で、また、例外命令を書くと、前の例外はスタックにpushされます。例外解
除命令で、popされます。
ですから、2つ以上の条件ではなく、つねに一つです。
それで、例外命令は、
1.キャリーの発生、非発生
2.ゼロの発生、非発生
3.2の補数計算のオーバーフローの発生、非発生
4.2の補数の以上の発生、非発生
5.2の補数の未満の発生、非発生
など、2つ以上のフラグの論理操作を組み込みます。
それで、複雑な複数の例外命令が用意されます。
命令に8bit,16bit,32bit,64bitって修飾があるのは、おかしいと思いませんか。
命令は、命令で、データに修飾があればいい。
つまり、データにタグを付けておけばいいじゃないかな。
var [a]:0x12345678
const data:123
ADD [a],data
とすると、[a]は、4byte、dataは1byteとわかるから、命令は、それに応じて処理をする。
逆にいうと、データに処理が付いている。
ADD
/ \
[a] data
というツリー構造になる。
例えば、1021倍なら
Ax1021=Ax1024-Ax2-Aとすれば、10bitシフトして1bitシフトしたものとAを引けばよい。
1021は、11 1111 1101Bなので、普通の乗算回路では9回の加算があるが、これだと2回のひき算で済む。
この定数計算のやり方は、定数でなくて一般の乗算回路にも当てはまるし、プログラムにも応用できる。
2つの積のうち、演算回数がすくなる方を細工する。
64bitx32bit,32bitx32bitの演算を考えると普通なら32回のシフトと演算になるが、この方法なら、16回以下の演算で済むので2倍
以上速くなる?
32bitの数の1と0の並びを調べる。1が多ければ、いくつか1を足して1が最小になるようにすれば、いいわけだ。どこに1を足したかで答えが分かる。
1の並びの間の0のところがひとつミソだ。そこを埋めて、1の並びの全体がすべて1の列に仕上がったら、最上位の上の桁を1にして、埋めた0のところは引
くところだ。
つまり、
3322 2222 2222 1111 1111 1100 0000 0000
1098 7654 3210 9876 5432 1098 7654 3210
0000 0000 1011 1111 0100 1111 1101 0000
1 1
11 1
---------------------------------------
1
-1
-1-1-1 -1-1
という感じかな。
Ax2^24-Ax2^22-Ax2^15-Ax2^13-Ax2^12-Ax2^5-Ax2^4
ここで、Ax2^4はAを4bitシフトすることだ。するとAを24bitシフトしてAを15bitシフトしたものを引き、Aを13itシフトしたものを
引き、Aを12bitシフトしたものを引き、Aを5bitシフトしたものを引き、Aを4bitシフトしたものを引けば良いので、5回のひき算で済む。
0が多ければ、簡単だ。
3322 2222 2222 1111 1111 1100 0000 0000
1098 7654 3210 9876 5432 1098 7654 3210
0000 0000 1000 1011 0100 0000 1001 0000
---------------------------------------
1
+1+1+1+1 +1 +1
Ax2^23+Ax2^19+Ax2^17+Ax2^16+Ax2^14+Ax2^7+Ax2^4で6回の足し算だ。
最上位の1と最下位の1の間の0と1だけ考えればよい。
最悪は、0,1が交互のばあいで、その時は、足し算を選べばよい。
だから、16回の演算を超えることはない。
bitの数を数える回路や、位置を求める回路は単純なゲート回路なので....
ヒントの1つ目:プライオリティエンコーダを使うと先頭と末尾の1の場所が分かる。
末尾の1はプライオリティエンコーダを順番を逆に繋げば、末尾をさがしてくれる。
ヒントの2つ目:4ビット単位で1の数を考えるのは簡単ですよね。それを32bitなので8個つけて、それぞれを加算すると1の数が求まる。
乗算器の話でした。こんなのは、当たり前かな?
固定小数点計算は80bitだったかだから、この方法では、クロック数がかなり減るね。
データのほうが圧倒的に多い。
とすれば、CPUへとデータを転送するより、CPUはデータ上を動いたほうがいいでしょう。
データ上をスライドするCPUってどうかな。
メモリを多層にして、メモリ層の上にスライド用のスイッチ層を起き、その上にCPUというかプロセス層を置く。
プロセス層は、動的再構成されるハードウエアアレーだ。
いちいちプログラムを運んでくる必要はないからね。
プログラムは、ひとつのプロセスで切って、ハードウエアを動的再構成する。
ハードウエアは並列処理で、プログラムはシーケンシャルだから、圧倒的にハードウエアは早い。
プログラムをハードウエア化するのは、OpenCLなどでC言語から直接FPGAにコンパイルするようになっているようです。
状態遷移図のシーケンサーは、ハードウエア化は簡単ですね。
AHDLでもシーケンサーは書けるしね。
プログラムの部分的ハードウエア化は、そんなに困難ではないと思います。
つまり、並列化できるところは、ハードウエア、全部のまとめが必要なところはマイコンのソフトといった具合で、マイコンのソフトを見なおしてやると
FPGAとマイコンが合体したようなシステムができるでしょう。
それは、マイコンを4コアとかにするよりも実用的だと思いますがね.....
演算パワーが必要なところはFPGAで、複雑な判断が必要なところはソフトでといった具合で、また、高速応答が必要なところはハードウエアで、もっと急ぐ
ときは、FIFOなんかでハードを制御する。
予め、応答パターンが決まっている時は、FIFOとシーケンサーで組む。
FIFOに入れるデータはマイコンで考える。
FIFOにマイクロプログラムというか、シーケンスプログラムを詰め込んで、えい、と、走らせる。
そうすれば、かなり高速応答ができる。
中間コードマシンなら、中間コードを実行する形態は自由である。
メニイコアでも、ASICでも良いし、ASICとプログラムのハイブリッドで良い。
中間コードコンパイラこれは、中間コードで書かれているから共通にできるから良い。
マイクロコードで中間コードを実行してもよい。
中間コードのようにマクロコードマシンは、ハードに依存しないので、便利である。
一時期、検討されたが廃れてしまった。
Javaも、Pコードマシンにすれば、良かったのに、.....
プログラムとASICのハイブリッドは、マクロコードマシンにとって非常に都合がいい。
ASICの並列処理、ステートマシンは、得意とするところである。
FPGAでもARMを一緒にしているので、これで、中間コードマシンに仕上げれば、インタプリタでも早いので、いいんじゃないかな。
インタプリタなら動的再構成もできやすい。
ある中間コードのまとまりを別の中間コードにマイクロコードコンパイルする。
というふうに、アプリから、階層的にトップダウンに変換することができるのではないか。
中間コードでプログラムが書かれているが、中間コードの実行はハードに任されているので、アドレスとかユーザーレベルでは抽象概念である。
ハードに依存しない仮想マシンである。
という事はOSはハードの一部であって、ユーザーレベルではAPIだけしかない。
という事は、ウイルスプログラムができないと言えないだろうか。
ユーザープログラムは独立したプロセスであり、rootのプロセスから派生したものだ。
したがって、所有者はrootのプロセスだろう。
それに対して、関係ないプロセスが他のプロセスをアクセスできないだろうし、通信はあっても良いが、それでウイルス攻撃はできんだろう?
ソフトウエア割り込みをOSのエントリーポイントにしていた時期があったな。
すると、アドレスは、OSとユーザーで切り離せるな。
ユーザーはリターンとかプログラムのアドレスをOSに与えるが、これは、ユーザープログラムの抽象概念で、OSとは関係がない。
ユーザープログラムは、割り込みでOSをコールする。
プロセスごとに、ソフト割り込みを割り当てる。いくつでも構わない。
したがって、ユーザープログラムは相互に独立しているわけだ。
OSは、ユーザーのソフト割り込みで、タスクスイッチする。
ソフトウエア割り込みを処理するプロセスもOSのプロセスである。
ユーザーがOSをコールした段階で、一般にユーザープロセスはWAITになるからね。
ログラム同士の通信は、OSが間に入る。
CPUは、キャッシュメモリをもっていて、OSはメモリをページで管理している。
したがって、CPUはメモリをページでしかアクセスする必要がない。
それは、HDDも同じだ。
となると、アドレスを下位まで送る必要はない。
ページアクセスだからだ。
すると、高速にページ転送する必要がある。
しかしながら、現在はパラレル転送であって、スキューの問題があって、高速転送ができない。
そこで、シリアル転送にして、クロック埋め込みとして、クロックラインをなくす。
また、イーサーネットのように4B/5Bの符号化をすることで、信号の帯域を狭くすることができるので、転送速度を上げることができ、符号化することに
よって増えたデータよりも高速にできる。
メモリとCPUをシリアルでつなぐわけだ。
IDEがSATAになったように。
CPUは数ラインでメモリでつながり、それぞれがページが違うので、これまでより柔軟で早くなる。
シリアル通信で、ページを指定する。
メモリは、アドレス線がなくなるので、シリアル線をたくさん持てる。
だから、メモリから、CPUとビデオチップ、HDDIFなど複数のものが並列につながる。
ページの競合は、めもりが調停する。同時の場合portの番号順で優先順位は決まる。
CPUがメモリのページをアクセスした時、使用中なら、使用中ですと返事が来る。
待ちますというと、ページアクセス終了した時点で空きましたというメッセージと占有権が与えられる。
CPUがキャッシュの更新をするときは、複数のportがあるので、同時に複数のページを更新でき、キャシュの更新は早い。
また、このシステムでは、メモリにつながるすべてのユーザーはキャッシュをもち、ページ単位でアクセスするものとする。
シリアル通信なので、QAMでもいいわけだ。
仮想記憶では、プログラムがページを超えたアクセスをすれば、ページフォルトでOSに制御は移って、OSによって、新しいページが読み込まれるまで、タス
クは止まる。
だから、メモリはページ単位でいいと思う。
キャッシュも2,3段階なので同じじゃないだろうか?
ページが書き換わったら、それを知りたいクライアントデバイスに連絡するのもいいな。
こうすると、デバイス間通信ができるわけだ。
HDDが、指定されたコマンドパケットをページで受け取って、何ページかの書き込みか読み出しを実行が終わったら、終わったよと送るわけだ。
ビデオチップも表示したよとか...
SSDもマルチのシリアルのページメモリにすれば、同時に複数のページが読めるので、より高速になる。
バスという考え方が根本的に変わるわけだ。今まではひとつのバスだったけれど、バスが複数になるわけだ。
CPUから見れば、キャッシュに複数のバスがつながっているので、ある意味ノイマンマシンでなくて、命令メモリとデータメモリが別々のハーバードアーキテ
クチャー?にも見かけ上なるわけで、DSPみたいになるわけだ。
すると、高速になる。
また、バスが複数あって、独立しているからHDDとビデオチップがCPUと無関係に動くし、DMAも要らなくなる。
USBメモリが直接HDDとかビデオチップやメモリにつながる。
メモリのインタフェースを変えるだけで、こんなにも大きな変化ができる。
CPUが命令を読むキャッシュとデータのキャシュを分ければ今でもより高速になるわけだけどね。
シリアルバスのクロスバースイッチを設ければ、動的にバスを集中させたり、分散させたりできるわけだ。
今のマルチコアでなくて、マルチCPUになるわけだから、バスの集中もない分いいわけだし、ヘテロジアスのシステムでもできるわけだ。
熱的に厳しくなれば、CPUをいくつか止めることもできるし、いつでも追加できる。
マルチコアは熱的制約を受けるしね。
独立したCPUなら関係ないし、....
マルチのCPUだから、あるCPUはビデオチップとつながっていたり、あるCPUはメモリと、あるCPUはUSBでIOという具合に、分散処理もできる。
これは、マルチコアではバスが一つしかないので、不利だろう。
CPUがメモリにくっついて、インテジェントなメモリを構成したりして、行列計算のデータの処理に合わせてデータを並び替えて、DSPにデータを流し込む
とアドレス計算をいちいち考える必要がない。
また、データベースでは、メモリに複数のcpuが張り付いて、インテリジェントなメモリになる。
処理マスタCPUから見ると、便利なメモリで、抽象的な命令ができる。
オペランドのアドレス計算ほど馬鹿馬鹿しいものはない。
処理するデータがALUに流れてくれば良い。
どうせ、行列にしても計算は連続なんだから、データを予め列にまとめて流しこめばよい。
それを毎回アドレス計算してたら本末転倒のような気がするんだが....
だから、賢いメモリが、処理に合わせてデータを列にする....
ビデオチップについて考えれば、マルチチップなら、それぞれのチップがメモリの別のページを並列に処理できるので、パフォーマンスが上がる。
また、ページ処理が終わると次の処理へとシーケンシャルに組み立てられる。
ソフトは、いつまでたってもバグは無くならない。それで、パラメータを外のFLASHにおいたりするから厄介だ。
ソフトは極力ハード化する。すると、当然、機能の絞り込んだ小さなものになるはずだ。
すると、バグが減る。
ソフト任せにするといつまでもバグが無くならない。
分岐がn個あれば、2^nの組み合わせができる。
ちいさなモジュールではnが小さいので組み合わせが減る。つまり、バグは減る。
小さなモジュールだとハードにできる。
ハード化するわけだから、慎重になる。
したがって、Pコードマシンは、極力ハードで構成する。
シーケンスマシンは、ハードのほうがバグが少ないし、1クロックで速い。
フォークとスパゲッティと哲学者のデッドロック問題は、1クロック処理なので、起きないんじゃないかな?
つづく