Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Hack The Cell 再び

shinhさんがHack The Cellのまとめ資料を書かれていました。
資料はコンパクトに纏まっていて,さっくりと読めます。楽しく読ませて頂きました。

この資料に感化されて,自分自身のまとめを書いておこうと思いました。たいしたことは書けないのですが,以前の勉強会で触れなかった部分を書いていきたい思います。(勉強会資料-pdf

命令の手動配置について
      手動配置作業ファイル

このファイルは,手作業で命令配置を行ったときのアウトプットです。
表の最初の状態は,左側に「mt行列の計算」,右側に「tempering処理」の命令が書かれていました。左右それぞれeven odd命令を分けて書いています。

「tempering処理」はほとんどがeven命令なので一旦置いておき,「mt行列の計算」から最適化を行います。「mt行列の計算」の命令群を変数の依存関係に注意しながら,できるだけevenとodd命令が重なるように配置していきます。表の色塗り部分が「mt行列の計算」を縮めた結果を示しています。

続いて,「mt行列の計算」の空いている部分に「tempering処理」の命令を入れ込んでいきます。
「tempering処理」の最後の方ではodd命令が現れるため,若干の調整を必要としました。

この表を5ループ分作成します。

配置の確認

表での 配置を終えたら,CSV形式で出力し,even-odd命令が互い違いになるよう1列に並べかえます。この状態で普通のCプログラムになります。ですので,これをコンパイルすることで実行結果を確認でき,配置の正しさを検証することができます。

アセンブラへの変換

実行結果がOKとなったら,続いてアセンブラコードへ変換します。
アセンブラへの変換はCプログラムの文字列を変換するコンバータを作成しました。

この辺り文字列操作に長けている言語を使えれば良いのですが,残念ながらマスターしている言語がないためCで書いています。
     アセンブラ・コンバータ

手抜きプログラムなので,変換元のCプログラムの書き方に色々な制約を課しています。(空白の入れ方等)

これで出力したコードには,まだC変数が書かれていますので,最後にsedでcellのレジスタ名に一括で置換します。これで最適化されたコードが完成です。

スポンサーサイト

Hack The Cell 2009

遅ればせながら Hack The Cell 2009 の結果を書いておきたいと思います。
参加者の多くの方は何かしらのWebサイト/ブログをお持ちで結果を公表しあってました。
こんな状況がうらやましく,今回私もブログを始めてみることにしました。

まずは,実行結果を貼っておきます。

ORIGNAL:         sum=3c927c56, 294950998 ticks
MINE: sum=3c927c56, 2448310 ticks
ORIGNAL: sum=2e987a4d, 425483257 ticks
MINE: sum=2e987a4d, 3531709 ticks
ORIGNAL: sum=ef1b6aef, 313079651 ticks
MINE: sum=ef1b6aef, 2598780 ticks
ORIGNAL: sum=eedd2516, 290962965 ticks
MINE: sum=eedd2516, 2415205 ticks
ORIGNAL: sum=f7e967a8, 14411793 ticks
MINE: sum=f7e967a8, 119837 ticks
ORIGNAL: sum=1f37a7db, 214886708 ticks
MINE: sum=1f37a7db, 1783769 ticks
ORIGNAL: sum=c7d41f36, 295887479 ticks
MINE: sum=c7d41f36, 2456073 ticks
ORIGNAL: sum=aa9d2e9f, 260377511 ticks
MINE: sum=aa9d2e9f, 2161355 ticks
ORIGNAL: sum=8abd398a, 251629392 ticks
MINE: sum=8abd398a, 2088731 ticks
ORIGNAL: sum=a374bd58, 6129418 ticks
MINE: sum=a374bd58, 51100 ticks


結果は僅差の3位のようです(おしい!)。 ソースはこちらからどうぞ。

締切り前日にループ内をフルアセンブラへ移行させ始めるなど,タイムマネージメントの失敗が大きかったなぁと思います。しかしながら,反省会での話や参加者のWebサイト等を見ていくと,3位に入れたのは結構すごいことのように思えました。

来年も是非参加したいと思います。(株)フィックスターズさん,来年も宜しくお願いいたします。

テーマ:プログラミング - ジャンル:コンピュータ

すべてはここから

趣味コーディングを久方ぶりに再開しました。切っ掛けはコレ
  Hack The Cell 2009
本屋で偶然目にした UNIX magazine に載っていたプログラミングコンテストがすべての始まりでした。

この号では,コンテスト主催者である(株)フィックスターズ社による「Cellでの開発」の記事が掲載されていて,この中でHack The Cellの紹介がされていました。プログラムの高速化とSIMDプログラミングは仕事でよくやっていることもあり,何とか行けるかもと軽いノリで参加を決めたのでした。

Hack The Cell の顛末は後で書くとして,コンテスト終了後の有志による勉強会,この勉強会(とその後の飲み会)が私にとってのターニングポイントになったのでした。

この会の中で,聞きなれない(別の意味では聞きなれた)“ゴルフ”というキーワードが出てきました。後で聞くと,お題に対し少ないキーストローク(文字数)でコードを組むことを競うとのことで,何ともグッと来るものでした。また,ICFPというコンテストが面白いという話や,別途shinhさんからはTopCoderというサイトも教えてもらいました。

こんなにも様々なコンテストがあるということで,コーディング意欲がとても高まってきました。しかしながら,社会人の身としてはなかなか纏まった時間がとれませんので,無理せず参加できるものからぼちぼちと活動していきたいと思います。
#Hack The Cellでは無理しすぎました・・・

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。