Crusoeの未来について考える(大ざっぱなタコ解析編)





そういえば最近Crusoeの話題を聞かない。 搭載されるはずの新型ノートも延期だ。どうしたのだろう...

以前、このサイトの マルチスレッド化で漁夫の利の予感 において、マルチスレッド対応時の適応力の高さについてUPしたばかりだ。 しかるに、Netから流れてくる情報は暗いものばかり。 TM5800の量産遅延によって、採用をあきらめたノートメーカーさえあると聞く。

と言うわけで、今日はCrusoeについて考えてみることにした。 元々の力不足の上に、Cruose関連はいかにも情報が少ないので、今回も仮定がかなり荒っぽい。 なにぶんシロウトの横好きレベルなので、間違いがあったらご容赦ってことで...


●Crusoeの復習   
このCPUを設計しているベンチャーは多士済々の人的資源を誇っている。 CPU自体も実に技術的示唆に富んだ、 教えられる部分の多い設計思想に基づいている。 まずは、その特徴を軽く復習しよう。

Crusoeは基本的にx86系CPUとは全く異なるアーキテクチャである。 というか、直接にはx86命令をまったく実行できない。 32bitのRISC命令(atomと言う)を4つパックして1つの命令のごとく処理する VLIWという特徴あるアーキテクチャを用いているからである。 (Pentium4等のプロセッサも内部はRISC化されているが、CISC-RISC変換はチップ内部で 完結しており、外見上はx86命令セットを持った立派なCISCチップなのである。)

VLIWは単純な命令を複数パックして、みかけ1つの命令として 処理するため、並列処理が得意である。 ただし、命令セットがx86ではない上に、並列性抽出機構を チップ内部に持っていないため (スーパースカラではチップ内に専用回路を持っている。)、 通常はコンパイラの支援を必要とする。 直接Windowsのようなx86系ソフトを実行することができないのだ。

では、一見コンパイラの支援を受けていないように見えるCrusoeは 、どうやってWindowsを動作させているのであろうか?

ここで登場するのがCrusoeの真の主役「CMS」である。 CMSはx86命令をVLIW固有の命令atomに変換する、いわばコンパイラである。 通常のコンパイラと違うのは、実行時にx86命令を直接コンパイルする 方式であることだ。(通常のコンパイラは、予めソースからオブジェクトを 生成する時に用いる。)これは、動的コンパイラと呼ばれる技術である。

ただし、通常のエミュレータの様に、単純なx86命令への 置換を行っているわけではない。 その変換アルゴリズムこそが、CMSの神髄であるのだ。

実はCrusoeがVLIW方式を採用したのは、 CMSとVLIWの相性が良いためであって、 必ずしもVLIWアーキテクチャである必然性は無い。 性能こそ低下するだろうが、スーパースカラのCrusoeは実現可能であろう。 しかし、CMSはCrusoeの核心技術であって、 CMS抜きのCrusoeは存在しえないのである。 たるさんがCMSこそCrusoeの神髄と表現した意味がおわかりいただけようか?

と、VLIWとCMSについて復習したところで、 Cruoseの未来について考えてみることにしよう。


●VLIW+CMS方式の演算処理時間について   
例によってCrusoeのベンチマークを取ったりして評価することはしない。 このような事が目的ならば、こんなタコ・サイトより、 もっと優れたWebサイトがたくさんある。 とりあえず検索サイトを調べて、どこにも載っていないような 風変わりな評価法を試して見る。

復習の項ではVLIW+CMS方式の特徴について述べた。 では、ここで平均的なx86命令を実行する場合を考えてみよう。 単純化のため、誤差が大きくなる事は承知の上で、 チップ内処理のみを考える。

プログラムには、経験則として下記の法則が成り立つと言われている。

平均的なプログラムは、その処理の90%の時間を10%のコードに費やす。

そう。有名な「90/10則」である。

では、この法則を満たす最も単純なプログラムを考えてみよう。 それは、下記のようなフローとなる。

1.処理時間Xサイクルのループ処理を81回繰り返す。
2.その後、処理時間9Xサイクルの処理を1回行う。


もっとも原始的な直接実行CISC方式のCPUがあったとして、 1命令/サイクルの処理能力があると仮定する。 そうすると、上記のプログラムを処理するのに必要な時間は 当然90Xサイクルとなる。 (キャッシュのミスヒットや分岐予測の失敗については、ここでは無視する。)

では、VLIW+CMS方式では何サイクル必要なのだろうか? ここから、Crusoeの歩む道を予想してみよう。


○第一ステップ:命令の翻訳   
Crusoeはx86命令をVLIW命令に変換しないことには、ただの1つも命令を実行できない。 だから、まず第一にすべき事はx86−atom変換である。 この変換はもっとも基本的なものだから、変換支援命令をatom (CrusoeネイティブのRISC命令)に持たせていることは間違いないだろう。 では、Crusoeは1サイクルに何命令を変換できるのであろうか?

ここで注目すべきなのは、Crusoeのx86-atom変換処理能力ではなく、 そのバス幅である。 CrusoeのVLIW命令は128bitだから、L1キャッシュのバス幅は非公開ながら、当然 128bitであると予想できる。 これとは別に、Crusoe(TM5400)の外部バス幅は64bitである。(これは公開されている。) L2のバス幅は不明であるが、以上から 64bitか128bitのいずれかである事は間違いないだろう。

L1キャッシュ内で命令を変換するのは いかにも範囲が狭いが、メインメモリを基準に考えると アクセスが遅い事が響いてくる。従って、変換ブロックサイズは L2キャッシュ容量程度を基準単位に考えてみよう。 ここで、仮にL2が64bitと仮定すると、atomは32bitだから 最大2atom/サイクルでしかメモリに書き込めないのである。

x86-atomの変換は1回しか行われない単純な置換作業の繰り返しであるから、 分岐予測を気にする必要がないし、ループ処理も繰り返す必要がない。 つまり、変換命令がどれだけ効率的に変換を行うことができたとしても、 最大変換効率は2atom/サイクルであると言うことだ。

もしCrusoeがx86命令1つにつき平均2atomに分解していると仮定すると、 これはx86命令では1命令/サイクルに相当する。 Pentium4の項では2.5μOPS/x86と予想したが、Crusoeの場合、 4atomをパックするVLIWなので 平均2atom/x86の方がパックしやすくて都合がいいのだ。

以上からわかるとおり、Crusoeの単純変換能力はx86換算で1命令/サイクルと 予想できる。

この予想値から第一ステップ:命令の翻訳の所要時間を計算してみると 下記の通りになる。 (ここでは、ループ処理を繰り返す必要が無いことに注意して欲しい。)

1.命令翻訳の処理時間= プログラム長/単位時間当たりの変換能力=10Xサイクル


○第二ステップ:並列実行命令の抽出   
前に書いたとおり、もしCrusoeが単純なx86変換実行プロセッサであるならば、 変換ロス分だけ処理が遅くなるので、ものの役には立たない。その処理能力はネイティブ実行タイプの1/3程度だろう。 (だから、はじめてCrusoeを見た時に「高速化は不可能」との感想を持ったのである。) つまり、ロス分をどこかで取り戻さなければならないのである。

これを行うのが、VLIWによる並列実行だ。 もし仮に、この作業で平均4atomの並列性が抽出できるとすると、 4atomをパックするCrusoeのVLIWエンジンは、 4倍の速度で処理を行うことができる、という事を意味する。 第一ステップでロスった分を取り戻すチャンスはここしかない。

しかし、並列実行を行うためには事前に依存性の無い命令を 抽出・検証しておく必要がある。 勝手気ままに並列実行を行うと、命令の手順前後により誤った値を生成したりして 危険この上ないのである。

このための下準備が並列命令の抽出作業だ。 この作業には冗長性命令の消去作業も含まれる。

まず、ここで並列実行命令抽出の範囲を決めよう。 これは、スーパースカラではリザーベーションユニットに相当する。 いわゆる命令ウインドウである。 ただ、スーパースカラと異なるのは、Crusoeの場合の命令ウインドウは 電子回路ではなく、物理的実体を持たないバーチャルな ソフト・ウインドウである と言う点だ。

このウインドウサイズをnとする。 そうすると、その中から並列実行可能なatomを抽出するのに必要な処理時間は どうなるのであろうか?

まず、プログラムのサイズは10Xである。 そうすると、ウインドウサイズがnであるから、抽出作業の繰り返し回数は 20X/n回となる。 (x86命令1個につき2atomに変換と仮定したので10X/n回にはならない。)

また、抽出作業時間はウインドウ内命令の組み合わせ数 n(n−1)/2に比例する。 さらに、atom実行における処理時間を1単位とした場合の、抽出作業の 比較検証コスト倍率をχとしよう。これは、χ=2ならば、 命令Aと命令Bの依存性探索に平均2サイクルかかると言うことを意味する。 すると処理時間は下記の通りになる。

2.同時実行命令のパック処理時間= χ×(n(nー1)/2)×(20X/n)


○第三ステップ:パックしたVLIW命令の実行   
さて、第二ステップで並列命令の抽出を行ったので、ようやくパックされたVLIW命令の 本領発揮である。ここで、第二ステップで抽出された並列実行可能な命令の出現確率を ηとしよう。本当はこれを数値で出したかったが、アプリによって かなり差があるようであきらめた。

すると、VLIW命令の実行時間は下記の通りになる。

3.VLIW命令処理時間=逐次処理時間/平均並列実行命令数 =180X/(1+(n−1)η)

ここで分母がnηではなく1+(n−1)ηになっているのは、並列命令の出現率が 最悪だったとしても、逐次処理と同じ処理時間以上には ならない事を考慮した結果である。(つまり、nη>1である。)

また、分子が90Xではなく180Xとなっているのはx86命令1つにつき2atomに 変換した結果である。


●総処理時間の計算   
では、このプログラムを行うCrusoeの処理時間はいかほどであろうか?

総処理時間=1.+2.+3.=10X+χ×(n(nー1)/2)×(20X/n) +180X/(1+(n−1)η)

ここで、抽出作業の比較検証コスト倍率を実行効率と同じと考えてχ=1と仮定し、 また、並列実行命令の出現頻度を50%と仮定して、η=0.5と仮定してみよう。 すると、総処理時間は上記の式から下記の通り計算される。 (nはバーチャルな数なので、処理時間が最短になるように決める。)

総処理時間=110X (n=5 このとき平均並列実行命令数は3atom)

nとχを振ってグラフにしてみた。ηは50%固定である。 最初は逐次実行の場合を基準に図を書いたのだが、 これでは、直感で性能がつかみにくい。 そこで分かりやすいように、性能はPentiumIII比としてみた。 (分かりやすくするため、誤差大を承知の上の変換だ。 だから、絶対値は気休め程度に考えて於いて欲しい。) 逐次実行方式の処理時間90Xサイクルを PentiumIIIの平均同時実行命令数である1.8命令(x86)/サイクルで 割った値を基準とした相対値のグラフである。



先ほどの総処理時間110XサイクルはPentiumIII換算で約45%となった。

な〜んだ、全然速くないじゃん!と思ったあなたはするどい!  実はCMSの神髄は「繰り返し使われる部分だけ最適化する。」 という点にあるのだ。 上記の式では、プログラムの全体を最適化していたのである。 つまり今回試した方法は、実際のCMSよりアルゴリズムがプアなのだ。

ただ、注意して欲しい点がある。それは、この命令ウインドウ ・エントリ数と 処理能力の関係である。普通に考えれば、命令ウインドウ内の エントリ数nが大きいほど 抽出できる命令数が増えるので、同時実行可能な命令数も増える。 つまり、グラフの右側に行けば行くほど処理能力が増えるはずなのである。

しかし、グラフの関数は比較検証コスト倍率にもよるが、χ=1の場合n=5で 最大値となり、これ以降は逆に処理能力が低下してしまうのである。

これは、上式で言う第二項の処理負担が、nの増大によって 急激に大きくなるために発生する。 つまり、「VLIW+CMS方式はスーパースカラと違って命令の並列性を プログラム全体まで拡大して抽出することができる。 だから、スーパースカラより性能が高い。」 という、某エレクトロニクス専門誌に書かれていた 常識は、たるさんが考えるに明らかに誤りであると言うことである。 これは、第二項の関数の中の組み合わせ項n(n−1)/2式の次数が nからnに成らない限り、 原理上の制約となって改善不可能である。 つまり、O(n)である限り、 どのようにアルゴリズムを変えても、 (ピークの位置や高さは変わるかもしれないが) 本質的には変わらないのである。

では次回は、この部分最適化の効果について検討してみる事にする。(続く)