先週は、以下のことを勉強した。
組み込み用プロセッサでは、8bit 程度のCPUであることが多く、レジスタ の数も多くはない。したがってレジスタ関連の最適化はそれほど難しくは ない。しかしメモリが限られていることがからコードの大きさの縮小 などが重要である。Micro-C は、この用途に設計されている。また、 Real-time monitor やI/Oアクセスと同時に用いられることが多く、 アセンブラとの協調が必要である。
RISCプロセッサは現在の汎用計算機の主流であり、命令レベルの並列度を 利用する。10年前は1命令1クロックなどと言われていたが現在ではバス 幅を増やし、1クロックに複数の命令を実行するできるようになっている。 命令レベルの並列度には2種類あり、RISCの方式として以下のように区別 される。
ベクトルプロセッサは、配列や行列の高速実行に適したアーキテク チャである。そのために、長い浮動小数点パイプラインを複数本持 ち、専用の命令を持つ。RISCプロセッサでもソフト的にベクトル処 理をおこなうことが行われている。ベクトルプロセッサ用のコンパ イラでは配列処理をよりきめ細かに分析し、並列度とともに配列の 効率的なアクセスを可能にするようなコードを出力しなくてはなら ない。
最近の数値計算マシンの主流は、ベクトル計算を備えた並列マシン であり、この分野では日本の技術は他の追従を許していない。(た だしあまり宣伝もしていない) アメリカのイリノイ大学はこの分野 のメッカであるが、実はここでの研究を主導したのは日本人である と言って良いだろう。WWWはイリノイの計算機センタ(NCSA)の成果 を広めるために開発されたともいえる。
しかし、並列計算機のコンパイラに関しては、まだ系統的に最適化 をおこなうようなアルゴリズムやコンパイラ設計手法は確立されて いない。現実には並列アーキテクチャは、個々のアーキテクチャの 違いが大きく、人間による命令単位の調節がものをいう。特にプロ セッサ間の通信のタイミングによりパフォーマンスは数10%も変わ ってしまう。一つの手法は、データ並列と呼ばれるもので、とにか く相互に依存度の低いデータをプロセッサごとに割り付けてしまう という方法がある。
8bit CPUや、IBM/360, PDP-11, VAX あるいは MC68000 系のCPUで は複雑な命令が用意されており、それらを使うことによる最適化が 重要である。これらのアーキテクチャ内部には並列度はあまりなく、 レジスタもそう多くはない。しかもアドレッシングは複雑である割 に、どのアドレッシングもそれほど実行時間に差があるわけではな いので、できるだけ複雑な動作を一命令で実行することが重要にな る。
このような場合に有効な手法は、動的計画法による最適化とスーパ ーオプティマイザである。
RISC CPUでは、従来の2段から3段といったパイプライン実行ではな く、7段から10段といった深いパイプラインが採用されている。こ れは一つの命令の実行が終る前に数命令先が既に読み込まれ実行さ れつつあることを意味している。この時に先に実行されている命令 が条件分岐命令であった時には、次の命令をどこから取って来るか を予測することはできなくなってしまう。この時、CPU は分岐先が 決まるまで実行を一時中断する必要がある。これをストール(stall) といい5-7 clockのlossが生じる。条件分岐は実行時間の大半を支 配する一番内側のループに必ずあるわけだから、このpenaltyは大 きい。
このペナルティを防ぐにはいくつか方法がある。
PowerPC の分岐予測 8つのflag brach bit
RISCの引き続く命令は、そのままの順序で実行されたのと同等に実 行されなければならない。しかし、引き続く命令の関連がなければ、 それらの順序を変えても良いし、並列に実行しても良い。並列に実 行できないような場合は、命令に依存関係がある場合である。これ らの干渉はパイプラインでも生じる問題である。パイプラインの場 合にはパイプラインのストールという症状になる。
複数演算を同時に実行する命令 (内積演算、MMX)
ソフトウェアパイプライン
ベクトルプロセッサの場合は、配列全体の依存関係を見ているだけでは 不十分である。同じ配列をアクセスする演算でも、その演算の干渉が なければ、それを別々のパイプライン(の命令)にすることにより高速な 実行が可能となる。
添字の干渉の判定(diophantos equation)
Fortran Syndorome
ポータブル計算機に必要とされるコンピュータ言語の機能と、その コンパイルについて1000-2000字程度で考察せよ。