2010-12-06

僕が抱える不治の病のひとつに、floorとceilのどっちがどっちだか永遠に覚えられないという病気がある。
特に問題なのが、あの記号である。あの記号は、僕の直感とは反対の意味を持つ。

僕の直感では、↓この記号は「天井が降りてきて値が減る」というイメージ

↓この記号は、「床が上がってきて値が増える」というイメージ

なのであった。これは逆で、上の記号のほうがceilで切り上げ、下の記号のほうがfloorで切り捨てである。

と、いうわけで、仕方が無いので、僕はこれを「自分の直感とは逆なんだからねっ!!」というように覚えていたのだが、そういう覚えかたは肝心なときに、「あれ…逆ってどっちだったっけ…」とかなりがちである。
この覚えかたを、「可動式床天井方式」…それの反対なので…「反可動式床天井式(以後、反可式)」としておこう。

僕は長いこと反可式で覚えていたわけだが、あまりにどっちがどっちだかわからなくなり続けるので、イライラして、別の方法で覚えることを決意した。
名付けて、「排気穴方式」である。
排気穴方式は、「なんかへこんでるものって吸引してそうじゃね？」という僕の直感を利用した覚えかたで、図であらわすと以下のようになる。

でっぱっているものが吸いこんでいるのは、直感に反する。よって、「吸い込んでるほうが正義」とだけ覚えておけば、間違えることはなくなる。

以上によって、僕はfloorとceilどっちがどっちだかわからない病を克服するのであった。あれ？そうか？floorとceilは相変わらずどっちがどっちだかわからなくね？

同様の問題に、「必要と十分のどっちがどっちかわからない病」がある。昔数学の教師が「先が必要と覚えるように」と言っていて、それだけははっきり覚えているのだが、「必要としているのが先なの？必要とされているのが先なの？」といった感じで、多分これも一生覚えられないんだろうなと思う。

個人的には、並列化の問題は、メモリの問題だと思っている。メモリの問題が他の問題と比べて面倒くさい原因は、メモリの問題はモジュラリティを下げるという点にある。

マルチコア時代には、演算性能が増えるわけだが、メモリ性能はそれと比べるとあまり増えない。これにはどう対応するのがよいだろうか。

ハードウェアによるメモリキャッシュは、どんな問題にも対応できる、というわけでは無いが、メモリ性能についてハードウェアで改善できる要素はそれ以外あまり無いので、ハードウェアが進歩するに従って基本的にキャッシュは巨大化/複雑化する。

キャッシュが巨大化/複雑化するデメリットは、

演算に使えるトランジスタが減る
コヒーレンシプロトコルが複雑化する

というのがある。

これらのデメリットは、コアを増やして演算性能を上げる、という目標と対立するので、演算性能の向上だけを目指すならば、できればハードウェアキャッシュは無いほうがいい。

この問題に対する革新的な技術として、比較的普及したものとしてはCell/B.E.とGPUがあって、

Cell/B.E.は

ローカルメモリをソフトウェア制御にして、容量の無駄を減らした
ローカルメモリをソフトウェア制御にして、ハードウェアによるコヒーレンシの維持という概念をそもそも無くした

GPUは

十分な並列性があればメモリのレイテンシの大きさは無視できる
消費電力はとりあえず無視してメモリのスループットはバス幅で維持する
これでレイテンシ/スループット両方問題無くなるので、ローカルメモリはあんまり必要無くなる

この革新的な技術の考えかたの中心としては、ハードウェアの問題をプログラマの根性に変換するという話で、まあ、実際は革新的というか、なんか昔に戻ったという感じであった。
ただ、違いとして、昔の泥臭い技術というのは、命令数を削減するという作業だったが、現代の問題では、メモリアクセスを改善しないといけない。

この点で、現代の問題は、昔の問題よりも面倒臭い。
命令数の削減は、変更を局所的、例えば関数単位での改善やらモジュール単位の改善に閉じ込めることができる。
それに対して、メモリアクセスの改善は、変更を局所的に抑えられないことがよくある。

例えば、リンクリスト内の要素それぞれを3倍して、合計を求める、というような処理を考えよう。

struct list {
    list *chain;
    int val;
};

void mul3(list *l) {
    while (l) {
        l->val *= 3;
        l = l->chain;
    }
}

int sum(list *l) {
    int s = 0;
    while (l) {
        s += l->val;
        l = l->chain;
    }
}

int func(list *l) {
    mul3(l);
    return sum(l);
}

ここで、昔のように、32bit乗算が遅いのを改善するとかだと、x86だとlea一命令でできるもんねーなどと言いながら、

void mul3(list *l) {
    while (l) {
#ifdef __i386__
        asm ("leal (%0,%0,2), %0"
             :"+r"(l->val));
#else
        l->val *= 3;
#endif
        l = l->chain;
    }
}

とかのように変更すれば全ての問題は解決した。この時、変更は、mul3内に留められており、モジュラリティは非常に良い。

だが、現代では、乗算は全然問題ではなく、こういう例だとリンクリストを辿るメモリアクセスのほうが問題になる。乗算は最悪でも3,4cycleぐらいの時間で処理が終わるが、メモリアクセスは最悪の場合数百cycleになる。

メモリアクセスを改善するにはどうすればよいだろうか。とりあえず、アクセスするデータ量を減らすことを考える。

現代ではメモリアクセスは、64byte(CBEでは128byte)単位で行われており、1byteでもメモリアクセスしたら、周辺64byteを使わないと、メモリアクセスに無駄が発生する。
数値一個だけを含むリンクリストをmallocする場合を考えると、

struct entry {
   struct entry *chain;
   int value;
};

mallocの管理領域4byteを足して、12byte。で、8byteアラインが必要なので、合計16byte。メモリ帯域の効率は25%になる。
とか、考えると、メモリ帯域の無駄遣いをやめるためには、リンクリストを捨てて、値の入った配列にしたい。

処理は、↓こうしたい。

void mul3(int *arr, int len) {
    for (int i=0; i<len; i++) {
        arr[i] *= 3;
    }
}
int sum(int *arr, int len) {
    int s = 0;
    for (int i=0; i<len; i++) {
        s += arr[i];
    }
    return s;
}

が、この時、変更は関数内に閉じることができなくて、お漏らししてしまうのであった。

int func(list *l) {
    mul3(l); // !?
    return sum(l); // !?
}

実際にプログラムを書く場合、速度のためにモジュラリティを壊すなんてのは、相当の理由が無いとやらないと思う。

これは、昔にあったような「可読性の低いアセンブリでゴリゴリ最適化」とかよりも、ずっと実現性が低い。
アンドキュメンテッドで黒魔術な自己修正機械語コードを書いたアホなプログラマがトラックに轢かれても、モジュラリティが維持されてれば、最悪の場合 #ifdef を消せば昔の挙動に戻すことが可能だ。

しかし、モジュラリティがぶっ壊れる場合は、他人に影響を与えるので、「何故それが必要なのか」と、「具体的にどう変更するのか」が、きちんとドキュメンテーションされてなくてはならない。そこまでするほど余裕がある人はあんまいないだろう。

このようにして、ソフトウェアによるメモリ最適化は、実際にはあまり行われることはなくて、キャッシュの増加というハードウェアの進歩任せになりがちである。

だがしかし、この時、GPUとかCBEとかのように革新的な技術を持ったコンピュータ上では、メモリ空間が複数存在するので、モジュラリティの革新的な破壊が強制されるのであった。
具体的には、「構造体にポインタが入ってるコードは全部書き直す」という作業をやらされる。あ、もちろん、STLのコンテナとかみたいな具体的なメモリレイアウトのわからない抽象データ型は全部再実装してくださいね。

その見返りとして、GPUやCBEは、x86を上回る性能を手に入れられるわけだが、大多数のソフトウェアが、モジュラリティを破壊してまで最適化しないという都合上、GPUやCBEの上で動くプログラムは限られたものになってしまい、生産数の問題とかで、長い目で見ると価格あたり、電力あたり、面積あたり、全ての点で、x86上で動くプログラムのほうが性能が良くなっていく。今あるGPUのプログラムは、10年後のGPUでは動かないと予想されるが、x86のプログラムは10年後のx86でも動くだろう。その時には、x86のプログラムは、今のGPUのプログラムよりも速くなってるに違いない。

というわけで、実際に得られる見返りは、「現時点でのみ」という条件が付く。これが、「将来に渡って性能が保証される」とかなら、モジュラリティに革命を起こすのもそんなに悪い選択肢では無いと思うのだが。

今のところx86はこの問題を抱えていない。だが、数年前に言われたような、「これからはコア数が倍々になっていく」みたいなのが現実になった場合、コアごとに数MBのキャッシュを持つとか、全体でコヒーレンシを維持するとかみたいなのは現実的ではなくなっていくわけで、メモリアクセスの問題が表面化する日も来るかもしれない。というか、PCのx86 CPUがここ数年間2,4コアのままなのを考えると、すでにその問題が表面化してると言えるかもしれない。(まあ、コア数増えない一番の理由は性能よりも省電力のほうがニーズがあったからだと思うが)

このメモリアクセスとモジュラリティの問題を解決することはできるだろうか？

上の例の、リストアクセスと配列アクセスみたいなのは、一応、コンパイラの最適化の強化とかでなんとかなる問題ではある。ただ、グローバルな解析をしてそこらへんをなんとかする実用的なコンパイラは、まだ見たことが無い。(ここでは性能がメインテーマなので、GCC/ICCよりも遅いコンパイラは問題外ですよ)

そもそもキャッシュでしか解決できない問題もある。ある程度大きな領域に対してランダムアクセスをする場合、演算器と同じ速さで動くタグアレイが欲しい。

並列化とかは「開発環境が整備されれば」みたいなことが言われるわけだが、並列化の問題はコア数が増えてくればいつかメモリの問題に行き付くことは確実であり(だからこそCBEはあんなアホな構造になってるわけで)、メモリの問題が上のような問題を含んでることを考えると、そもそも、開発環境が整備された程度ではどうにもならない問題なのでは？という気がしないでもない。

CPUと等速で動く大容量メモリみたいなのが誕生して、キャッシュが必要無くなる、みたいな世界にならない限り、問題を根本的に解決するのは不可能なんではないだろうか。

w_o’s diary

floorとceilどっちがどっちかわからない病

FermiのL1て書き込みどうなってんだっけ…

マルチコア時代のメモリアクセス問題

■