2009年06月02日

Cell Challenge 2009ソース公開

ソースコードが公開されました。他のチームのソースをじっくり読もうと思います。

http://www.hpcc.jp/sacsis/2009/cell/

うちのチームのみどころは#include "macro.c"です。

#うちのチームやけにサイズ大きいなと思ったらなぜか実行ファイルがアーカイブに含まれてた……。
posted by chun at 14:44| 日記

2009年05月31日

そろそろCell Challengeについて(ry

我々は非常に運が良かったことがよく分かりました。
後で復習しておこう……。
  • T社さん的には「うちの組み込みエキスパートが頑張るから大丈夫!」
  • 合意したこと「やっぱI社が本気出してないよね」
  • LSはバーターとして理解できるけどやっぱ使いづらいよ! とか言っておきました。
  • メインメモリをLSの一部にmmapみたいにマップできるといいんだけどねー。
  • S田研の学生さんがみな口々に「先生はいま何やってるのか謎」と言う件について
posted by chun at 14:57| 日記

2009年04月30日

豚flu

昨今(Recentlyから書き始めるメソッド)豚インフルエンザが話題となっておりますが、皆様いかがお過ごしでしょうか。
薬学を学んだ者の端くれとして、私は現在の状況を大変憂慮しております。特にデマ的な意味で。

最初に一言、過剰にインフルエンザウィルスを恐れる必要はありません。特にマスコミの皆様は過剰反応ではないかと思います。加えて、インターネット上で危機感を煽る言説、偽科学、決めつけ、などがありますが、皆さん冷静にm9ないしpgrしてください。

信頼できる情報源として国立感染症研究所のページを推奨しておきます。特にQ&Aを一度読まれると良いと思います。
http://idsc.nih.go.jp/disease/swine_influenza/index.html

現時点で話題のウィルスにはオセルタミビル(タミフル)、ザナミビル(リレンザ)が効くことが明らかになっております。従って、恐れる理由は全くありません。これらの薬は発症から48時間以内に投与する必要がありますが、それは日本ではきわめて容易です。保険証さえ持っていれば世界で最も安価な部類に入る治療費で、標準的な治療が受けられる国にいる利益を最大限に享受するべきです。
要するに高熱が出たら医者に行き(上記2つは処方箋薬です、薬局では買えません。追記:病院に行く前に保健所に連絡して下さい)、会社・学校に行かず、寝ていろと。会社・学校に行って同僚に広めないことがいつもより強く望まれるだけです。出来れば治ったと思ってもプラス1日ぐらい休んでください。繰り返しますが恐れる理由はありません。

豚肉はインフルエンザウィルスを媒介しません。買い控えるとか馬鹿な真似はやめてください。

冷静に対処してください。
posted by chun at 01:54| 日記

2009年04月15日

なぜ関数型言語を使うのか→一言で言うと単純且つ強力だから((c) E. Sumii)

なぜ関数型言語を使うのか(再掲・追記)

(この文章は以前(2005-5-15)に書いた記事を再編集して再掲するものです。)

Red-black treeは、平衡木の一種である。その実装は2-3-4木に等しいが、データ構造はより簡便である。

さて、その挿入を実装することを考えよう。Haskellでは、このように書ける。(情報元:sampou.org)

挿入のためには、平衡操作(木の分割と回転)を実装する必要がある。

balance :: RB a -> a -> RB a -> RB a
balance (T R a x b) y (T R c z d) = T R (T B a x b) y (T B c z d)
balance (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance a x b = T B a x b

これに対し、ほとんど同じ実装で私が書いたC++のコードは次のようになる:

  static void rechain(node*& nref, node* less, node* middle, node* greater, node* ll, node* lr, node* rl, node* rr){
    nref = middle;
    middle  -> color = RED;
    middle  -> left  = less;
    middle  -> right = greater;
    less    -> color = BLACK;
    less    -> left  = ll;
    less    -> right = lr;
    greater -> color = BLACK;
    greater -> left  = rl;
    greater -> right = rr;
  }
 
  static void balance(node*& nref){
    // if, tree structure is R (_, _), just ignore and come back later
    if(nref -> color == RED) return;
 
    node *child, *gchild, *ochild;
    // all "4-node"s should be rebalanced to R(B, B)
    if((child = (nref -> left)) && child -> color == RED){
      // B (R, R)
      if((ochild = (nref -> right)) && ochild -> color == RED){
        nref -> color = RED;
        child -> color = BLACK;
        ochild -> color = BLACK;
        return;
      }
 
      // B (R (R, _), _)
      if((gchild = (child -> left)) && gchild -> color == RED){
        rechain(nref, gchild, child, nref,
                gchild -> left, gchild -> right,
                child -> right, nref -> right);
        return;
      }
      // B (R (_, R), _)
      if((gchild = (child -> right)) && gchild -> color == RED){
        rechain(nref, child, gchild, nref,
                child -> left, gchild -> left,
                gchild -> right, nref -> right);
        return;
      }
    }
    if((child = (nref -> right)) && child -> color == RED){
      // B (_, R (R, _))
      if((gchild = (child -> left)) && gchild -> color == RED){
        rechain(nref, nref, gchild, child,
                nref -> left, gchild -> left,
                gchild -> right, child -> right);
        return;
      }
      // B (_, R (_, R))
      if((gchild = (child -> right)) && gchild -> color == RED){
        rechain(nref, nref, child, gchild,
                nref -> left, child -> left,
                gchild -> left, gchild -> right);
        return;
      }
    }
  }

#rotate操作に直すともう少し簡潔に書ける。

読者の多くは、もう何が言いたいかわかったと思う。パターンマッチは偉大である。

僕には、なぜ、アルゴリズムを教えようとする教師がJavaやCを好んで使いたがるのかが理解できない。C系列の手続き型言語は、すべからく(僕が好んで使うC++を含めて)トリビアルな部分で異様なほど時間をとられ、アルゴリズムそのものの勉強に使える時間はきわめて限定されてしまうのに。

(再掲:月記/2005-4-18)
 あなたが難しい問題を解こうとしているなら、 問われているのはパワフルな言語を使うか使わないか、ではない。 
 (a)パワフルな言語を使うか 
 (b)パワフルな言語と等価なインタプリタを書くか 
 (c)自らがパワフルな言語の人間コンパイラとなるか
 、という選択なのだ。

(追記)Scalaでの実装。みずしまさんのツッコミを受けて修正。

  abstract class Node
  case class Leaf() extends Node
  case class R(left: Node, key: int, right: Node) extends Node
  case class B(left: Node, key: int, right: Node) extends Node

  def balance(left: Node, key: int, right: Node) = {
    (left, key, right) match {
      case (R(a, x, b), y, R(c, z, d)) => R(B(a, x, b), y, B(c, z, d))
      case (R(R(a, x, b), y, c), z, d) => R(B(a, x, b), y, B(c, z, d))
      case (R(a, x, R(b, y, c)), z, d) => R(B(a, x, b), y, B(c, z, d))
      case (a, x, R(b, y, R(c, z, d))) => R(B(a, x, b), y, B(c, z, d))
      case (a, x, R(R(b, y, c), z, d)) => R(B(a, x, b), y, B(c, z, d))
      case _ => B(left, key, right)
    }
  }

ちなみに、私は以前教授Aに「データ構造の教育には関数型言語を使うのもアリじゃないですかね」と言ったところ、その話を聞いた別の教授Bから鼻で笑われたことがあって、それ以来ずっと根に持っている :P 。

posted by chun at 15:20| 日記

2009年04月04日

大丈夫かこれ

受かってしまった。なんてことだ。
posted by chun at 21:16| 日記

2009年04月01日

簡潔なMLの実装

もう一つのMLコンパイラを書いてみました。

mini-mlは簡潔なML型言語の実装です。以下の特徴を備えています:
-Hindley-Milner型の型推論
-代数的データ型とパターンマッチング
-例外
-x86_64コード出力

コードは簡潔で、可読性を重視して書きましたが、それでもコードベースは1000行を下回ります。まだ最適化は十分なものではなく、Minilightレイトレーシングでベンチマークを行った結果、g++-4.2.4(-O2)比69%程度の速度となりました。今後は最適化部分に注力して開発を継続したいと思います。

コンパイルにはOMakeが必要です。コンパイル後、"./mini-ml -o a.out foo.ml"とすると実行ファイルa.outをfoo.mlから作成します。

mini-ml-0.0.1.tar.gz

追記: 4月1日はエイプリルフールです。
posted by chun at 08:34| 日記

2009年03月31日

そろそろCell/BEについて一言言っておくか

プログラムを書いてみて思ったのは、とてもじゃないがSPEを使ったプログラミングはペイしない、ということです。高速化に掛かる開発コストが計算コストと比較して高すぎます。計算インテンシブなタスク(今回のタスクは計算量がO(n^2)で通信量がO(n)です)でこうなのですから、通信が大きくなるに従いさらに厳しくなるでしょう。シミュレーション用途ではCellに載っける開発コストが高すぎ、シミュレーション時間と比較してペイするのは相当長時間のタスクです。リアルタイム性能が要求されるゲームでも、よほど重い処理でなければペイしないでしょう。それなら計算する内容を減らせ(減らせないほどこだわりがあるゲームを作るなら別ですが……)と言うことになります。結局、これでは誰のためのCPUなのか分かりません。
いろいろ考えたのですが、大きな問題は次のあたりだと思います。

  • メモリ転送を自分で書く、というモデルはプログラマに仕事を押しつけすぎている。共有メモリと一貫性を取らないキャッシュのように、プログラムから見えないように実装した方が(たとえパフォーマンスが落ちても)ずっと良かっただろう。DMAを書くのは__builtin_prefetch()を書くよりずっと大変。MPIはOpenMPより大変なんです!
  • 言語でのサポートがきわめて貧弱。並列プログラミングはリソースの割り付けが最重要課題なのに、そこへのサポートが無いに等しい。
  • 用意されている通信ライブラリも貧弱。殆ど通信プリミティブしかない。
  • パフォーマンス計測手段が足りない。速いCPUよりボトルネックが見つけやすいCPUが重要。


というかまぁ正直なところ<過激>高速化するのにコンサルタント会社が必要なCPUは滅びて欲しい。</過激>新しい命令セットを持つCPUは、ただでさえ移行コストが高いのですから、ここら辺はCPU以上にお金を掛けて欲しかったと思います。正直なところ、現在のサポート状況を見ていると、供給会社の皆さんが本気でCellを普及させるつもりがあるのか疑問です。つかI○MはPOWERが売れれば良いんじゃないかな……。そうそうSPARCどうなるんだろうね……。新SPARCのレジスタの扱い方気に入ってるんだけどね……。

逆に良いところは、

  • 128 bit幅のレジスタが128個もある。
  • ローカルストレージの存在自体は回路規模と比較すると良い交換だと思う。これがキャッシュならもっと良かったのに……。
  • 通信の粒度に応じたSignal / Mailboxなどの存在。
  • 一見何に使えるのか分からないshuffle命令。萌える。
  • ループ内部はパフォーマンスが予測しやすい。打てば響く高速化は重要。
  • パイプライン可視化ツール。でも命令数増えると動かない。


あたりでしょうか。Larrabeeとかどうなるんかなぁ。
posted by chun at 00:00| 日記

そろそろCell Challenge 2009について一言言っておくか

前のエントリで書いたとおりCell Challenge 2009で優勝しました。優勝と言っても正直予選のスコア差を生かしてハナ差で逃げ切ったので微妙な線ではありますが、まぁ勝ちは勝ちと言うことで。真の優勝者(と僕が勝手に思っている)たるRunSeptetチームさんにはどうやって高速化したのか、是非SACSIS2009で聞きたいと思います。もしここを見ていたらよろしくお願いします。>RunSeptetのみなさん

元々アルバイト先曖昧マッチングのソフトウェアを書いていたこともあって、課題を見た瞬間に「これは入賞できる」とふんでスタートしました(もちろん会社に許可は取りました)。正直なところ一人で申し込んだ時点では「入賞すればいいや」だったのですが、oxy君が加わったのでこれは優勝せねばなぁという感じになりました。既にx86で試し書きしたビット並列の編集距離計算のプログラムを持っていたので、それを128bit化するだけで--ここはかなり大変でしたが--動きました。この最初に動くプログラムを持っていたというのが良かったと思います。これが結局早く動くコードに繋がり、予選でのスコアに繋がり、優勝に繋がったので。

予選は最初にツールキット0.5が出た時点で1 SPEを使った128 bit parallelのコードが動きました。速度的には今と比較して4*7倍ぐらい遅かったと思います。この後でSPEでの並列化をどうしよう、とかメモリ制限的にいまのアルゴリズムだと動かないよね、と考えていました。ツールキット1.03が出た時点でコードががらりと変わったので、しょうがない全部書き直すかという感じで7 SPE並列化したプログラムを書きました。このときのプログラムは原因不明の低速化にいろいろと苦しめられました。最初のプログラムは時々10秒を超えることがあったのです。後で分かったのは、未使用ページへのDMAアクセスが異様に重いとか、DMAはどうもスケジューリングが公平じゃないとかそんな感じでした。ページングをPPE側で行い、signalなどで通信を整理すると安定し、速度も劇的に向上しました。後はoxy君が関数内の高速化をほぼすべてやってくれ、僕自身は最適化を全く行うことなく予選への提出となりました。

予選終了→本選はほとんど僕が手を付けることなく終わってしまいました。政治家先生の「秘書が、秘書が」ならぬ「oxy君が、oxy君が」状態です。予選が終わった段階で自明な枝刈りが出題に含まれることが分かったのですが、内容を把握する前にoxy君が高速化コードを書き上げていて僕はチェックぐらいしかすることがありませんでした。ループ内部についても、ありのままいま起こったことを話すぜ、oxy君があれから25%高速化したよって言ってきた、何を言っているのかわからねーが、です。まぢで。僕はというとDMAをダブルバッファリングに置き換えようかといろいろ測定してみたんですが、最終的に1.5%以下だったので無視することになりました。そのほか、SPE-SPE直接転送とか、通信周りではいろいろ試しましたがどれも遅くなってしまい、結局コミット量はほぼ0でした。なので、予選→本選の高速化は(というか高速化そのものは)ほとんどoxy君の功績です。
posted by chun at 00:00| 日記

2009年03月29日

薬剤師国家試験

ちょっと前になりますが、薬剤師国家試験を受けてきました。以下の中から正しいものをすべて選べ!
  1. 昔やった内容をあまりに忘れていて正直ビビった。有機すら覚えていない
  2. いくつかの内容(法規とか天然物とか)は知識0からスタートした
  3. それなのに過去問が1周半しか終わらない状況で受けた
  4. 2週間前はCell Challenge 2009でそれどころじゃなかった
  5. 直前1週間は追い込みどころじゃなかった
  6. 二日前に成田着だったので時差ボケを治せず試験時間中に2回も寝た
  7. 風邪引いて熱出てた

これで受かってたら世の中の薬剤師を信用できません。来年は2月末のスケジュールを空けておくことにします。あははははー!

#追記: この<li>だろうがなんだろうがお構いなしに<br />を挟むブログの設計はどうかと思う
posted by chun at 13:40| 日記

2009年03月25日

Cell challenge 2009 優勝

http://www.hpcc.jp/sacsis/2009/cell/honsen.htm
しました。最後は非常に接戦だったので危なかったです。予選の点差で逃げ切りました。

これから公開される他のチームの実装を見て勉強しようと思います。危なかった。
posted by chun at 23:46| 日記