「タイトル未定」というタイトル

Entries

Re:Re:Re:CPU関連の話

http://d.hatena.ne.jp/mkomiya/20060427#p1

　かなりコンピュータ将棋寄りの話になってます。私の主な興味は「コンピュータ将棋がどれだけ高速に動くか」なのでご了承下さい＞読者の方々

> >　私は次期バージョンでハッシュを少し改良して、ハッシュコードだけを保存する表と実データを保存する表に分けようと思ってるんですよ。そうすれば、ハッシュコードはL2に載りそうなのでハッシュにヒットするかどうかの判定が高速化出来るんじゃないかと考えています。
>
> 　それは面白いですね。詰め将棋じゃなくて通常探索は、そもそもそんなにハッシュヒットしないらしいので、むしろハッシュ容量を減らして、L2収めるのも面白いかも？
>
> 　コードだけ入れて、実データは、ポインターでアクセスってことになるんでしょうかね。

　え、L2にハッシュを収めるんですか！？ 1エントリー40Byteと仮定しても、4MBのL2に10万エントリーしか入りませんよね。あ、でもどうせヒットしないなら、そっちの方が速くなるかも。

　ハッシュ容量を減らすなら、ヒットしやすい場合としにくい場合を統計的に見極めるのが重要になりそうですね。キャッシュからの追い出しアルゴリズムも、LRUではなくて別のアルゴリズムが必要かも。例えば深いノードのエントリーから追い出していくとか。

　ポインタを使うかどうかは迷っているのですが、ハッシュコードを格納する表のn行目でヒット判定をして、ヒットしていたら実データを格納する表のn行目にアクセスする、という方式でも良さそうです。

> >　ちなみに私はTransmeta信者です。もうパソコン向けにはCPUを売ってないみたいですが（泣
>
> 　そうなんですね。
>
> 　いわゆるコンパイラに並列抽出をさせてVLIWと、CPUが回路で自分でするスーパースケーラと分けると、
>
> 　CPUがソフトで実行時に並列抽出するTransmetaのやり方が好きだってことですね？

　そうですね。CMSのオーバーヘッドはあっても大規模な最適化が可能なTransmetaの方式が好きです。

> >　おー、PARROTですか。すっかり忘れていました。これにx86の皮をかぶったIA-64を足せば最強！とか言ってみます。
>
> 　PARROTとかのアプローチはTransmetaな感じですよね？
>
> 　IA-64自体は、普及しないから悪いだけで、方式自体はすごく良いと私も思います。
>
> 　あまり詳しくないですが、Itaniumuだと、並列数を仮想的にしておいて、実際のハードの並列度が将来増えても、コードはそのまま有効になるんですよね？
>
> 　VLIWの欠点をカーバーしてますよね。
>
> 　ただ、普及しないネックとして、互換性は、
>
> 　x86の皮を被せれば、良いということですね。
>
> 　この仕組みって、x86からIA-64のコードに変換した後の結果をキャッシュできるようにすれば、変換での遅延とか無くせますよね。

　確かに、Intelの人も「TransmetaがCMSを使っているのは、パワフルなハードウェア（動的なスケジュール用のハードの事だと思います）を持っていないからだ」と言っていましたから、類似性はありますよね。

　IA-64は命令セット的には優れていますし、ハードの設計も（多分）x86よりはシンプルですし。変換結果のキャッシュが実現すればかなり期待できますねぇ。今回のリストラで実現しないでしょうか。

> >　メニーコアになると多数のコアが同時にキャッシュアクセスする可能性が高まるので、共有型の方が設計が難しくなりそうです。SunのNiagaraでは8コア（同時実行スレッドは32）でL2を共有してますが、同時アクセスはどうなってるか気になります。
>
> 　なるほど。
>
> 　ただ、非共有だとコアごとにL2用意することになると、レイアウト的にももったいないと思うんですよね。
>
> 　たとえば8coreで1MBx8の非共有L2があるとすると、全体で8MBもあるのに、コア単体は1MBしか使えない（そしてあふれる）
>
> 　Niagaraの記事を見ると、8wayでもL2同時アクセスは4wayで充分と考えてるようですね。
>
> 　スレッドレベルのパイプラインが、Niagaraは面白いと思います。
>
> 　通常の命令レベルのパイプラインより、粒度が荒い並列処理ですね。

　うーん、結局L2共有か非共有かは設計者の好みになっていくんでしょうか。

　4wayだったんですね、L2同時アクセスは。情報thxです。

　Niagaraはスレッドレベルの並列性を追及した設計なので、Intel・AMDやIBMと比べるとかなり独特ですよね。

　この先、x86プロセッサも同じ方向に向かうと、コンピュータ将棋の並列化方式もきちんと検討しないといけなくなりそうです。20～30スレッドなら特定ノードから先を並列化すればOKですけど、それ以上はスレッドを用意出来なさそうな感じが。

> >> 詰め将棋もありますけど、静止探索をやっても面白いと思います。
>
> >確かにそれも面白そうですね。私の場合は、末端での評価関数が複雑な上チョコチョコと実装が変わるので、静止探索は難しそうですが。
>
> 　ハードで静止探索をやるなら、評価関数はばっさりシンプルにすることになると思いますね。
>
> 　たとえば、駒得だけとかでもいいかも。王の位置で、フィルターしてやって、位置の評価だけでも入れておけば、そこそこ動くような気がします。

　なるほど。評価関数はシンプルにしておいて、大まかな値を高速に得る、と。正確な値を知りたければ、再度探索すればOKですよね。

　Bonanzaとかは駒得＋αのシンプルな評価関数らしいので、FPGAと相性がいいかも。って、これ以上Bonanzaが高速になったら (((( ；゜Д゜)))ガクガクブルブル

この記事に対してトラックバックを送信する（FC2ブログユーザー）: http://streakeagle.blog15.fc2.com/tb.php/502-a4d44e38

0件のトラックバック

0件のコメント

コメントの投稿

Appendix

QRコード

プロフィール

アベント

@author アベント
@mail murakumo_xp@yahoo.co.jp
アセンブラなんて分からないニュージェネレーションのJAVAプログラマ。
でもJAVA実習の単位は落とした経験あり。二回目もC判定。＜だめジャン
でもJAVAが好き。
2ch プログラム板にも出没。
- おまいら最強の将棋プログラムしてみろよ
- すれ立てるまでもない質問はここで
- Java質問・相談スレッド
- クラス名・変数名に迷ったら書き込むスレ