研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

理論的計算量の見積もりに関して - その3

2010-06-30 19:20:28 | Weblog
2. 行列積
計算量はいうまでもなく O(n^3) だが、性能差が非常に大きい。

N: 3重ループ
B: ブロッキング(block=64)
G: GotoBLAS2

まずは n=1000 と n=2000 とした nxn 正方行列の積から。
n=1000
N: 6.07s, B: 1.99s G: 0.03s
n=2000
N: 60.19s, B: 16.78s, G: 1.38s

次に n=2000 でマルチスレッド計算[使用したプロセッサ数]
n=2000
G[1]: 1.38s, G[2]: 0.69s, G[4] 0.35s, G[8] 0.20s

このように、n=2000時で最も単純なものと高速化されたライブラリでの性能差は、60.19 / 0.20 ≒ 300.95 倍にも及ぶ。

このように計算量は非常に重要ではあるが、性能は単に計算量で決まるわけでもないことを念頭に入れてほしいと願っている。理論的に計算量を見積もるプロセスを研究している方は多いが、実験的にも行おうとしている方は非常に少なく感じる。

理論的計算量の見積もりに関して - その2

2010-06-29 19:19:41 | Weblog
1 の続き
前回、sorting は比較の回数を基準に計算量を見積もっているため、quicksort の最悪時である O(n^2) の比較回数があったとしても、実際には実行時間は極端に長くならない(むしろ短い)。

この swap 操作にかかる計算量が比較回数に比べが大きいという検証のために 2種類の BucketSort の実行結果を比べてみる。

・BucketSort1
データ領域は入力のものだけ。スワップを繰り返し行う。

・BucketSort2
一時的なデータ領域を確保し、スワップではなくデータ移動を繰り返し行う。

BucketSort1 : 22.2s
BucketSort2 : 1.3s

このように swap 操作をデータ移動に置き換えることで、22.2 / 1.3 ≒ 17 倍程の性能差が生じてしまう。

理論的計算量の見積もりに関して - その1

2010-06-28 19:18:56 | Weblog
計算量の見積り方法はアルゴリズム分野において重要な意味を持っている。同様のことを行う場合、より計算量が小さいアルゴリズムを選択することでより効率的に処理を終える事ができる。しかしながら、実際にソフトウェアを書くことを想定すると、計算量でつく優劣が計算機上の性能の優劣と必ずしも一致しない場合も少なくない。

例を挙げて説明していく。

1. Sorting
アルゴリズム分野にいる人であれば QuickSort は平均では θ(nlogn) だが、最悪時 O(n^2) となってしまうという共通知識が存在する。特に O(n^2) になってしまうときはすでに並び替えが終わっている(昇順 or 降順)場合である。そのため、並び替えが終わったデータ列に対して QuickSort を行うと非常に遅いとされてきた。

QuickSort のプログラムを組んだことのある方は当たり前のことと知っておられるかと思うが、実際、実行時間はそうならない。

ex. 58M のデータの並び替え
環境: Intel Xeon X5460 3.16GHz / GCC 4.1.2

未ソートデータ列に対する QuickSort(K&R) : 8.57s
ソート済データ列に対する QuickSort(K&R) : 5.21s

このようにソート済みの方が実行時間が短い。sorting における計算量では比較回数を基準に見積もっているため、このような現象が起きる。比較演算に比べ swap 演算はコストが非常に大きい。
struct aline_t {
  int tail, head, length;
};

static __inline__ void swap(int i, int j, aline_t *a) {
  aline_t t = a[j];
  a[j] = a[i];
  a[i] = t;
}

void kr_qsort(int left, int right, aline_t *a) {
  int i, m;
  if (left >= right || right == -1) return;
  swap(left, left + (right - left)/2, a);
  m = left;
  for (i = left+1; i  right; i++) {
    if (a[i].head  a[left].head) {
      swap(++m, i, a);
    }
  }
  swap(left, m, a);
  kr_qsort(left, m-1, a);
  kr_qsort(m+1, right, a);
}

SCOPE @ つくば - 2日目

2010-06-27 22:32:15 | Weblog
今回は前乗りを含めて２泊３日の研究会だったわけですが、やはりこういった大掛かりなものを実行するためにはマンパワーが必須。

関係者のみなさまには厚く御礼申し上げます。また来年もぜひ参加させていただきたいと思います。

SCOPE @ つくば - 1日目

2010-06-26 22:32:41 | Weblog
人生初座長ということで、１日目の１つ目のセッションを任せていただきました。座長といえばコメントがないときにするという非常に重い任務を背負っているのはですが、この筑波合宿では他の研究会以上に皆さんコメントをしていただけるので、盛り上がりますし正直ありがたいです。実際、それぞれ興味深い内容を発表されているので必然なのかもしれません。

MuseScore 0.9.5

2010-06-24 19:50:31 | Weblog
MuseScore というフリーの楽譜作成ソフトウェア。MacOSX にも対応しかなり洗練された使い心地。Finale にも引けは取らないと書かれているが、実際そうかもしれない。

スコアメーカーは version を重ねる度に使いづらくなるので、こういったフリーのものが出てくるのは非常にありがたい。

MuseScore
http://musescore.org/ja

wine on MacOSX - その3

2010-06-23 19:29:23 | Weblog
結局 Miku Installer でのインストールに。するとすんなり日本語フォントが認識され、スコアメーカーもとりあえず使える状況になった。めでたしめでたし。何回もためしてしまったので、どれが正しいのかは全く分かりません。

ちなみに MacOS 版の Office 2008 ではマクロ機能が使えないということもあり、やはり Windows は根強いなと感じたのであります。

それにしても Finale という超大物ソフトウェアがあるのだから、コンバータくらい配布してくれてもいいのではないかと思うところ。

wine on MacOSX - その2

2010-06-22 19:28:57 | Weblog
まず Wine を導入する方法として2種類あるそうで、
　1. Wine(port, fink, .dmg)
　2. Miku Installer
1 は Wine 本家のものなので確実に入るだろう。2 だと version は最新のものではないが、日本語フォントがついているため簡単。なんとなく 2 は余計なものまで入ってしまう気がして、1 を選択。

1 といっても port や fink では必ず時間かかるし、まずは .dmg を探してみる。
(port や fink でいれるのであれば、ソースコードでビルドしてしまうことが多い)

● WineBottler
http://winebottler.kronenberg.org/

とすぐ見つかるので試されると良いだろう。WineBottler は wine で起動するための windows binary を単独で実行できるように梱包してくれるソフトウェアである。

● 使用感
→日本語フォントの設定がよくわからないため、うまくできませんでした。これは Windows の知識不足かなと。それからスコアメーカー2.1は Program files ではなく、C: ドライブの直下に専用のディレクトリを掘ってしまうため、設定の仕方もうーむというところ。

wine on MacOSX - その1

2010-06-21 19:28:21 | Weblog
Windows 環境から MacOSX 環境に移り、メインは MacOS という感覚でいる。

環境が変わるとそれまでのソフトウェアが使用できなくなるということから、完全に Windows を排除することは難しい。私の場合は趣味の楽譜ファイルが多いため、MacOS でももちろん動作する PrintMusic(Finale の廉価版) に変更したものの windows でしか動作しない河合スコアメーカーで作成したファイルが読めない。Finale ファイルへのコンバータもないため、なんとなく困ってしまう。

Wine は触ったこともなく、少々戸惑ったので作業メモを書いておく。

TeX: program 用環境

2010-06-18 16:00:07 | Weblog
program と code を作ってみた。

documentclass[10pt]{article}
usepackage{ascmac}
usepackage{fancybox}

newenvironment{program}{
  VerbatimEnvironment
  baselineskip=.80normalbaselineskip
  begin{quote}begin{screen}begin{footnotesize}begin{Verbatim}
}{
  end{Verbatim}end{footnotesize}end{screen}end{quote}
  baselineskip=normalbaselineskip
}

newenvironment{code}[2]{
  VerbatimEnvironment
  baselineskip=.80normalbaselineskip
  begin{quote}begin{itembox}[#1]{footnotesize #2}begin{footnotesize}begin{Verbatim}
}{
  end{Verbatim}end{footnotesize}end{itembox}end{quote}
  baselineskip=normalbaselineskip
}

begin{document}
begin{program}
int main(void) { return 0; }
end{program}

begin{code}{l}{sample}
$ cc f.c -o f && ./f && echo $?
0
end{code}
end{document}


#10 -> #11

2010-06-16 23:18:53 | Weblog
Moleskine Squared Notebook Large を 購入。

非常に高価な代物なので文房具店でいいなーと思ってもあまりにも高く手が届かなかったが、数ヶ月使うものだし気に入ったものをと思って今回からは良いものを。

実はちょうど良い大きさ(~A5)でgridが引いてあり、紙がそこそこ良いものって以外とない。あんまりページ数が少ないとすぐに交換することになるし、電車の中などでも書けるように、下敷きいらずなハードカバーがおすすめ。

定価 2,730 ですが、Amazon で買うと 1580円(日本版 2,184円) と半額程に。そもそもノートに日本語版も英語版もないので、安い方をおすすめします。