周回遅れすぎるCrusoe大研究

概要

書いたのが2008/07とか。でも十年後にはCrusoe出たのが2008年なのかどうかすらあやふやなんだろうなー。という

前提知識

CMSとか

参考文献

上みっつぐらいは先に読んでおくのが望ましい

The Technology Behind Crusoe(TM) Processors (PDF)
パブリックに置いてある公式資料の中では一番詳しいCrusoeの中身の説明
Transmeta社のCrusoe
日本語で概要が書いてある。シャドウレジスタ、Gated Store Buffer、Alias Hardwareに触れてる日本語の資料はこれぐらい?
Crusoe(TM) Processor Software Optimization Guide (PDF)
Crusoeの最適化ガイドのミラー(だと思う)。CMS向けに最適化するにはどうすればいいかとか。
Crusoe Exposed I II
Crusoeのネイティブ命令セットの解説など。CMSの処理の解説はPart IIIということになってるけど、Part IIIは書かれなかったもよう。
Crusoe Transmeta CMS Bug
Transmeta本社のサイトから消えてしまった資料が置いてある。
Dynamic Binary Translation
直接関係無いけどBinary Translationの概要。難しいのは単純な命令のエミュレーションだけではないとか。

RDTSCについて

Crusoeでは↓がだいたい最大クロック(595MHz)と同じになる。

ちなみにCPUのクロックを下げてもRDTSCのサイクルは変わらないので注意。 つまりtscのクロックはCPUより速い場合がある。さすがにそれはないので、それっぽくなるようにエミュレーションしてるのだろう

#include <stdio.h>
#include <unistd.h>

unsigned int 
rdtsc()
{
	unsigned int eax, edx;
	asm volatile ("rdtsc"
		      :"=a"(eax), "=d"(edx));

	return eax;
}

int 
main()
{
	unsigned int begin = rdtsc();
	sleep(1);
	unsigned int end = rdtsc();

	printf("%d\n", end-begin);
}

テストコード

基本としては、命令を16回繰り返すループをN回繰り返してRDTSCで時間測定。RDTSC一個 = CPU1cycleとする。

コード

GCC 4.3.1で

 $ gcc -O3 crusoe.c -march=i686

でコンパイル。→ 結果

全体

結果は色々とある資料から予想できる値で、飛び抜けて変な物は無いように思う。

ALUがふたつあって、簡単なベンチマークで調べる限りでは妥当なスケジューリングが行われてるように見える。

何もしないコード(empty, nop)

empty が 0.20[cycle] で、時間は1/16してるので、0.20x16 = 3cycle。ループカウンタインクリメント、比較、条件ジャンプで妥当な値。

nopがこれと同じ値。これから、nopは消える点が確認できる

結果を使わない計算(removedep)

removedep、

    add %eax, %ecx
    xor %ecx, %ecx

これがnopと同じ時間になっているので、DCE(Dead Code Elimination:計算結果を使っていない計算を消す)が行われてる点が確認できる。

あと、ループの後に全レジスタを初期化してるが、他の結果を見る限り、ループ中の処理は消されていないので、基本ブロックを越えてDCEは行われてないように見える

DCEは比較的簡単な最適化というか、依存関係調べるついでぐらいにできる最適化なので、DCEをやっていないというとは、多分基本ブロックをこえる最適化はしていないのだろうと思う

無条件分岐(incpc)

incpc

    jmp 1f
1:

Crusoe Software Optimization Guide[swopt]に無条件分岐は無くなると書いてあったので試した。

empty, nopと同じく0.19ぐらいなので消えてると考えてよさげ

簡単な計算(add, paraadd)

add

    add %eax, %ecx

paraadd(並列実行できる加算)

    add %eax, %ebx
    add %ecx, %edx

両方ともほぼ1。paraaddがほぼ1なので、両方のALUで計算できる命令が並列可能だった場合は、ちゃんとスケジューリングされてることがわかる

paraaddのほうが少し多いのは、addの方は余ったALUでループカウンタのインクリメントしてるからだと予想

32bit乗算(mul,paramul)

mul

     imul %%ecx, %%edx

paramul

     imul %%eax, %%ebx
     imul %%ecx, %%edx

mulが13,14ぐらいで、paramulが28ぐらい。これはひどい。レイテンシが13あって、しかもパイプライン化されてない。

こんな飛び抜けてレイテンシが長い命令実装するのも大変だろうと思う点、パイプライン化されてない点から考えて、サブルーチン呼んでるのでは?と予想。

paramulの時間がmulの処理時間の2倍以上になっているのは、ライブラリ呼び出しABI守るためにレジスタ移動が増えるとか…かなぁ。勝手な予想だが

アドレス生成

addrgen

    leal 4(%%eax,%%ecx), %%eax

paraaddrgen

    leal 4(%%eax,%%ebx), %%eax
    leal 4(%%ecx,%%edx), %%ecx

Crusoe Exposed[exposedII]にアドレス生成がボトルネックなんじゃ?とか書いてあったので試した

Pentiumは上のを1cycleで、しかもALUとは別のポートで実行できるのに対して、Crusoeでは2命令、ALUを使って計算しないといけない、という話

予想に反してaddrgen=1.06, paraaddrgen 1.16cycleと、全然酷くない。

よく見ると、addrgenの場合で言うと、%ecx+4がCSE(Common Subexpression Elimination:同じ計算を一回にまとめる)で消せるのでそれなんじゃないかと。

paraaddrgenのほうが少し長いのは、CSEしても、ループの外に出したりはしてないので、その分の計算が増えてるのではないかと予想。

この結果から、(多分)基本ブロックの中でCSEが行われてると見てよいと思う

MMX

レイテンシ4で、片方のALUだけで実行できてパイプライン化されているという、まあ、普通。

VLIWなのをいいことにMMX実装してないんでは?ということは無さげ。

エイリアスするポインタ

para_loadstore

int
para_loadstore(int a, int b, int n, int x)
{
	int ret;
	unsigned int begin, end;
	int i;
	int *p;

	int stack, stack2;

	if (alias_flag) {
		p = &stack2;
	} else {
		p = &stack;
	}

	begin = rdtsc();
	for (i=0; i<n; i++) {
		asm volatile (A16("add %%ecx, (%%eax)\n\t"
				  "add %%edx, (%%esi)\n\t")
			      :
			      :"a"(p), "S"(&stack2)
			      :"ecx", "edx");
	}
	end = rdtsc();

	time_para_loadstore[x] = end-begin;

	return ret;
}

Crusoeの紹介[shokai]にAlias Hardwareとか書いてあって面白そうなので試した

eaxとesiが同じアドレス指してると命令に依存があって、違うアドレス指してると依存が無い

でこれの結果が面白い

コンパイル後一回目 :

paraloadstore # alias無し
1:182.812500
7:161.776786
49:1000.936224
343:2.387937
2401:1.829030
16807:1.763432
117649:1.768545
823543:1.759886
5764801:1.759250

paraloadstore # aliasあり
1:177.312500
7:11235.741071
49:14.660714
343:8.907799
2401:8.511454
16807:8.590624
117649:8.428394
823543:8.423217
5764801:8.464740

二回目 :

paraloadstore # alias無し
1:199.000000
7:71.741071
49:12.147959
343:8.902697
2401:8.479410
16807:8.516444
117649:16.962044
823543:8.431737
5764801:8.447198

paraloadstore # aliasあり
1:195.875000
7:59.607143
49:12.123724
343:8.903608
2401:8.450073
16807:8.542096
117649:16.998664
823543:8.529005
5764801:8.442343

一回目はエイリアスを恐れないで積極的にスケジュールしてレイテンシ1.75(load のレイテンシが3か?)。 で、それだと、alias有りの場合にトラップが大量に入って、最初は遅い。

で、しばらくすると、(多分)aliasしても大丈夫なようにスケジュールされてレイテンシ8.4。 で、一旦aliasしても大丈夫なようにスケジュールされると、aliasしない場合でもレイテンシ8.4。あとはレイテンシ8.4で固定、となっている

indirectjmpの性能をどうやって実現してるか謎

あと

面倒なので略

まとめ

特にまとめることは無い。

独断と偏見に満ちた妄想

多分CMSがやってる最適化は、

  1. 基本ブロック選ぶ
  2. 基本ブロック内の命令のDAG(Directed Acyclic Graph)作る。この時DCEされるはず。
  3. CSEする
  4. スケジューリング

だと予想。確たる根拠は無いので想像の範囲を出るものでは無い。 ちなみにこれらは古典にも載ってるのでマジックでもなんでもない。

これらをやってるのであれば、それなりにまともな最適化エンジンだと呼んでいいはず。

--

Crusoeが流行ったころ、

「エミュレーションでこれなら、Crusoeってネイティブ実行したらスゲー速いんでね?」

「そんなことない。x86向けに最適化してるのでCrusoeはx86を実行した時に本当の性能が出る」

みたいなやりとりがあったが、両方とも正しくない。CMSは見た感じまともな最適化をしてるので、 エミュレーションと言っても、Atomのネイティブ実行に近い性能は出てるはず。

んで、CMSがやってる最適化はx86に特殊化されたものではないので、x86コードを実行した時に本当の性能が出る、というものでもない。

あと、素人考えではあるけど、この構成であれば、x86向けの特殊なハードウェアが無くてもまともな性能は出せると思うので、 x86向けの特殊なハードウェアも存在してないだろうと思う。フラグレジスタの構成がx86と一緒とかはあるだろうけど。 ごくフツーのVLIWなCPUとソフトウェアonlyのCMSで構成されてる…はず。

エミュレーション向けの機能は、Alias HardwareとShadow Registerか。Shadow Registerはよくわからん。 Alias Hardwareはエミュレーションを専用にするCrusoeを特徴付ける機能だと呼んでいいと思う。普通のCPUには存在しない。

--

最後、Crusoeはなんで遅かったか

直感でヤバいと思う点は以下。

演算器が少ない。leaでアドレス生成を駆使してると、PentiumIIIでは1cycleでALU無しで計算、CrusoeではALU使って、加算+シフトを計算、ってなるのでこの差はあるはず。

乗算が遅い。乗算の遅さはヤバい。PentiumIIIがレイテンシ4でパイプライン化された乗算を1cycle二回、Crusoeはパイプライン化されてないのがレイテンシ13なので、ピーク性能で26倍。平均しても8倍くらい違うのでは?という気がする

基本ブロックを越えて最適化しない。デスクトップアプリでは小さな基本ブロックがゴロゴロしてるだろうけど、Crusoeはそれなりに大きな基本ブロックが無いとスケジューリングができない。アウトオブオーダー実行ならば、なんとなく基本ブロックを越えてスケジュールされるので、この違いはあると思う。

なお、実際にちゃんと計測したわけでは無いので信用しないように

履歴

2008/07/04 Ver 1.0 書いた