従来の並列化と最近/これからの並列化の違い

一昔前の CPU の進化とはシングルスレッド性能を伸ばすことでした。
ソフト屋はこの進化にただ乗りし、ソフトをいったん作ればあとは何もしなくても、新しいハードでは速くなる、時間が経ってハードを買い換えてくれれば速くなるというおいしい状況でした。

Windows XP は発売当時、見た目だけハデにした重い OS と言われたのに、今では軽い OS として評価が高いのはハードの進化のおかげです。ハード進化の一翼が CPU のシングルスレッド性能の伸びでした。MS が Vista 発売にあわせて XP を軽くなるよう改良したわけではありません。

これをソフト屋がおいしい思いをしている、ただ飯を食ってるってことで、フリーランチと言います。


ところが今では CPU は進化の方向を変え、シングルスレッド性能の伸びはゆるやかになり、その代わりコア数が増えていく方向になりました。
これまでのようなソフトを書いていたのでは、ほっといても速くなりません。フリーランチに預かるには、コア数にあわせて速くなるようにプログラムを書く必要があります。


つまり、処理の並列化が必要で、それもこれまでのような一定数のスレッドを使うのではなく、コア数に応じて性能が伸びる仕組みが必要です。そうしなければ、ソフトは新しいハードでも速くならず、競争力がないソフトになってしまいます。数年後に軽いソフトとして評価が上がるということもないわけです。
可能な限りの処理を並列化してしまおうという方向です。
さらに最近は、並列にできない部分が処理のネックという意見も出てきました。そんなこと言われても困ってしまいますが…。


で、ソフト屋が並列に乗っかるにはどうすればいいかという模索が始まり、それが関数型言語だったり、TPL/PLINQ のようなライブラリだったりするというわけです。


いくつか聞いた話をあわせるとこんなところでしょうか。
たまにはこんなことを書いておくのもいいかなと思って書いてみました。

Windows 7 でタスクバーにピンで留めれないプログラムの名前

via http://west-wind.com/weblog/posts/32765.aspx

ちょっと笑える記事w
実行ファイルの名前に「Documentation;Help;Install;More Info;Readme;Read me;Read First;Setup;Support;What's New;Remove」が含まれると「タスク バーにこのプログラムを表示する」が表示されなくてピンで留めることができないそうな。
開発者はご注意を。

キーワードは以下のレジストリにあるそうです。
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\FileAssociation\AddRemoveNames

Caps Lock キーがいらない

http://slashdot.jp/polls/431
選択肢にどーして Caps Lock キーがないんだ。
間違って押して困ったり、間違って押して PC がおかしくなったと助けを求められたりするための罠キーなのに。
パスワード間違ったときの画面にも Caps Lock うんぬんは定番だし。誰得。

半導体の微細化が止まる日

並列まわりの記事をいろいろ読んでるうちに、ふと半導体の微細化が止まったらどうなるんだろうという疑問がわいてきて、ぐぐって見つけた記事を読み漁ったり、とりとめもなくいろんなことをボーっと考えたりしてます。
SSDはもっと安くて大容量になって欲しいし、CPUやDRAMはずいぶん遠くまで来たなあとは思うものの、微細化が止まって進化の大きなピースが欠けたらそれはやっぱりおもしろくないなぁとも思います。新しいPC買ってハエーと喜んだり、1Tが一万円!?とか驚くのが楽しいと思うわけです。って後ろのは半導体じゃないしw

半導体 微細化」でぐぐるとその限界について、様々な意見が出てきます。「ムーアの法則」でぐぐっても悲観的な意見がいろいろ見れます。
ズバリな記事が湯之上 隆さんの記事(続きの記事も参照のこと。とても面白くてシリーズ全部読んでしまったw)、もうひとつ、湯之上さんの blog 記事半導体産業は「LSIの微細化が止まり、技術革新がなくなり、例えて言うなら、鉄鋼業のように、成熟産業になる」と考える人がいたり、CPU/DRAM/SSDが特に大きい影響を受けると予想してたり、非常におもしろい記事です。

ぐぐって見つけたほかの記事も含めて予想のまとめ

  • 微細化は近い将来止まる
    • しかし、これまでも「もう無理」→「できた」の繰り返しなので、まだまだいけるかも
    • でも限界は近い。物理的限界かもしれないし、経済的限界かもしれない(TIなどは45nm世代より先の微細化をしないと発表)
    • どこまでいける?に関しては業界のキーパーソンたちの意見はバラバラ
    • 2013年?2022年?
  • 微細化が止まる前に、ペースが鈍る段階がくる
    • 2010年から?
  • 一方、3次元実装でまだ進化は続くかもしれない
  • 現在の集積回路とは違う何かによって、引き続きコンピュータの能力は上がっていくかもしれない

うーん、微細化が続くのはあと数世代、近い将来についに終わるかもしれないんですね。マジっすか……。その先は3D実装しだい?

PC用のCPUに限って言えば急速な性能アップ時代は既に過去のことなので、ソフトウェアが肥大化して遅くなってもいい(ハードを買い換えれば速くなるので)時代はもう終わってたと言えそうです。Vistaは肥大化時代の最後の象徴?ソフトの肥大化は今後も続きそうな気がするので、機能が増えても遅くならない方向に舵を切るのかなぁ。
PCはどうなるんだろう。ケータイやモバイルはどうなるんだろう。ソフト屋の各セグメントはどうなるんだろう。湯之上さんの blog のつづきが読みたいです。

頻出飽和集合とかのメモ2

2つやったことの記録。ビットマップ化と振り分け処理の改良失敗。
振り分け処理の改造は、ハッシュ(Dictionary)を使っているところを、マージ(マージソートのマージ。併合)にしてみたけど遅くなった。もう少し改造してみるけど早くなりそうな気はしない…。
ビットマップ化は、アイテムが疎なら遅くなるって最初の入門PDFにも書いてあるけど、ビット黒魔術で遊びたかった。そして、遅くなっただけだったw

ビットマップ化はグラフの隣接行列表現

グラフ理論のグラフを表現する方法として、主に隣接行列と隣接リストの2つがある。隣接行列は頂点と頂点の間に辺があれば1、なければ0とした行列で表現する方法。メモリの都合上、密なグラフでは隣接行列がよく、疎なグラフでは隣接リストがよい。

レコード(トランザクション)とアイテムを頂点とした2部グラフ(前回のメモ参照)と考えたときに、それをあらわす隣接行列がビットマップ。

A {1,2,3,4}
B {1,2,3,5}
C {1,2,3,6}

とあれば、アイテムを各ビット位置であらわし、1 => 00 0001, 2 => 00 0010, ... ,6 => 10 0000とすると

  | 654321
A | 001111
B | 010111
C | 100111

となる。列が654321のアイテムで、行がABCのレコードの行列になる。64個以下のアイテムしかなければ、1レコードが64bitで表現できる。あとはANDを取るだけで共通アイテムが求められる。
ちなみに、ビットマップ化してないときは配列でレコードを持ち、さらにレコードの配列でデータベース全体を表現している。ごくごく普通。リンクリストを使って隣接リスト表現してたりはしません。
アイテムの種類が多く、グラフが疎なときには、隣接行列が大きくなってしまう。1000種類のアイテムがあれば、1レコード1000bitになって、配列でレコードを持つよりデカイかもしれない。なので、アイテムが64個以下のときだけビットマップ化して計算するようにしてみたけど、ビットマップ化してはすぐビットマップでの計算が終わり、またビットマップ化しては(以下ry の繰り返しで、むしろ遅くなりましたとさ。ビットマップ化する際の条件を厳しくしても遅いまま。密なデータなら効果的らしい。
頻出集合を求めるのも、頻出飽和集合を求めるのも、上のABCのレコードの行列を縦に見て横に見てってことの繰り返し。
MJが亡くなったと聞いてここで書く気が失せたので、またいずれ。

頻出飽和集合とかのメモ

前回のデータマイニングの続き。ちゃんと書きたいけど、まだよくわかってないので今はちょっとだけメモ。

宇野先生の研究業績のページで頻出集合や頻出飽和集合関連のわかりやすい資料を見つけた。超大作パワポ「いいプログラムはコーディング技術だけではない」。中身とタイトルはあまりあってないですw 言いたいことはわかるけど・・・
前回冒頭に挙げた頻出集合アルゴリズムの入門PDFあわせて読みたい

あの後、LCM のコードはほとんどみてないけど(論文を読んでまねしてコードを書く部分を楽しんでるのと、ぱっと見てわかんなかったから)、頻出飽和集合が一発で求められるようになりました。後処理で削除してた部分がいらなくなり、前回1.2秒と言ってた処理が今や0.3秒で終わります。前処理も除けば0.15秒ほど。LCM と答えあわせをしてみると、答えの件数が一致するのであってるっぽい。

とりあえず、宇野先生の飽和集合関連のいくつかの論文に出てくる極大2部クリークって何さ?ってところをまとめた。
http://docs.google.com/Presentation?id=dqf99wm_1632cn22mpd7

極大2部クリークよりも頻出飽和集合のほうが具体的なんで、わかりやすい。
2部グラフって小学生のテストとかに出てくる「線で結びなさい」ってやつを思い浮かべるといいかもw