MicrosoftAcademicSearchのすゝめ
Microsoft Academic Searchみなさん使ってますよね！
Microsoft Academic Researchではありません。
研究する上で知らないわけにはいかない情報をまとめて知ることが出来るお役立ち検索サイトです。
http://academic.research.microsoft.com/
こんなトップページを開いて、検索窓から好きな研究者や研究テーマに付いて検索してみましょう。
ここはArt of mutiprocessor programmingの著者であるMaurice先生について検索してみます。
あっさり見つかりましたね。
PublicationやCitationといった数を閲覧できます。想像付くと思いますが、publicationは出版論文数、Citationは被引用数です。
出版論文が242件に対して被引用数7255件でかなりの活躍っぷりが想像されます。
研究者のパラメータとして、被引用数は一つの指標になります、多いほど注目されてる事を意味します。
名前の下には最近出した論文のリストが並びます、Citation数も一緒に出てて親切ですね。
名前のすぐ下に出てる研究分野の所をクリックすると
その研究分野でのすごい人をCitation順に閲覧できます。
どうやらIan T. Fosterという人がこの「Distributed & Parallel Computing」の分野において被引用数25000件超えで、ぶっちぎりで活躍している研究者っぽいです。
その名前をクリックすることで
その人の出版論文や被引用数、論文名リストなどを閲覧できます。
引用数25000件超えとか神がかってますね、一体何がこの人をこれほどまでに神格化しているのでしょうか。それを調べるにはその人の出版論文をCitation順に並べてみるとわかります。
The Grid: blueprint for a future computing infrastructureという論文が1690件の引用を受けてますね。グリッドコンピューティングを考えた人でしょうか。どうやらグリッドコンピューティングを知るにはこの論文に目を通しておかないと話にならなさそうな雰囲気が伝わってきます。
あとは論文名にてgoogle先生で検索してみて入手方法を検討してみましょう。
この一連の流れで研究のために何から手を付けてみたらいいかが明白になったと思います。これから研究をする人は参考にしてみてください。
http://academic.research.microsoft.com/
からあなたの研究を始めましょう！
深いこと考えずにpypyを揉む
pypyという大変coolなプロジェクトが有ります。
「PythonそのものによるPython処理系」という、一見よくわからない取り組みですが驚く事にJITコンパイルを搭載しています。
お陰でC実装のPythonよりも高速に実行できるという驚きの処理系です。
動かすには
http://pypy.org/download.html
に飛んでコンパイル済みのバイナリを配ってるのでダウンロードして起動
$ tar xvf pypy-1.6-linux64.tar.bz2
$ cd pypy-1.6/bin
$ ./pypy
Python 2.7.1 (d8ac7d23d3ec, Aug 17 2011, 11:51:19)
[PyPy 1.6.0 with GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information
And now for something completely different: ``good, tests are useful
sometimes :-)''
あっさり立ち上がります。
このままだと使いにくいので/usr/bin/以下にでも置いておきたいのですが
システムの何か大事な物がPythonに依存していたりすると惨事に見舞われます。
CentOSで使われているyumはpython2.4に依存しているらしくGAEの為に2.5に上げたらyumが動かなくなったり
pypyで遊びたいけれどシステムは壊したくない という人はvirtualenvを使いましょう。
以下細かい設定など
perfでぺろぺろしていたら詰まった
perfという大変優秀なプロファイラがあります。どう優秀かというと
・gprofと違い、-pgなど付けなくとも既存のバイナリに対して実行できます
・バイナリに対して実行できるという事はあらゆる言語の実行を観察できます
sudo apt-get install linux-tools
まずこれで必要なツールは入ります。
試しに何かのパフォーマンスを見てみましょう
$ perf stat ruby -e'100000.times{|n|p n}'
実行にかかったCPUサイクル数、分岐の数、分岐予測ミス数、キャッシュ参照数、キャッシュミス数などがズラズラ出ます。IPCなども計算されてプログラムの性質がわかります。
これでは物足りない人は、自分の好みの通りにセッティングを変えることもできます。
$ perf list
で観測可能なモノのリストが表示されるので、その中から好きなものをコンマで繋いで例えば
$ perf stat -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses,dTLB-loads,dTLB-load-misses ruby -e'100000.times{|n|p n}'
などと書けばキャッシュの中でもL1のヒット状況やTLBの様子なども観察できます。
perf statはお試し機能のようなモノで、実はperf recordとperf annotateがもっとプロファイラらしい細かい情報を提供してくれます。
$ perf record -e ./do.sh
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.372 MB perf.data (~16254 samples) ]
のように記録して
$ perf report
と打てばこのような画面。
また
$ perf annotate
で逆アセンブル結果と並べて観察できます。
実際に経過している時間と表示される場所とに誤差が出ますが、高速化のとても大きなヒントになります。
なので徹底的にperfで様々なパラメータを追いかけたいと考えるのは自然な流れなのですが…
$ perf record -e branches ./do.sh
Error: perfcounter syscall returned with -1 (Operation not supported)
Fatal: No hardware sampling interrupt available. No APIC? If so then you can boot the kernel with the "lapic" boot parameter to force-enable it.
などと出て計測できません。
APICというハードウェアカウンタがカーネルから使える状態になっていないようです。カーネルのboot parameterにlapicと付け加えろと言ってるようなので設定を編集します。
以下の事を実践すると環境を破壊する恐れがあります。自己責任でお願いします。
cat << EOF
linux ${rel_dirname}/${basename} root=${linux_root_device_thisversion} ro ${args}
EOF
と、ヒアドキュメントっぽい書き方してる所があるので
cat << EOF
linux ${rel_dirname}/${basename} root=${linux_root_device_thisversion} ro lapic ${args}
EOF
と書き換えます。
そして
で、/etc/grub.d/*の情報をもとに/boot/grub/grub.cfgの中身を書き換えてくれます。
結果は
$ cat /proc/cmdline
BOOT_IMAGE=/boot/vmlinuz-2.6.35-28-generic-pae root=UUID=1602199c-46d4-47bb-afda-0c224c7eccb6 ro lapic quiet splash
のようにして見れます。lapicの文字が加わっているところを見るに大丈夫そうです。
そして
$ perf record -e branches ./do.sh
と打つと…
Error: perfcounter syscall returned with -1 (Operation not supported)
Fatal: No hardware sampling interrupt available. No APIC? If so then you can boot the kernel with the "lapic" boot parameter to force-enable it.
同じこと言われたー！orz
となったところで今日はここまでにします。
実用例
「スレッド間で共有する変数のアクセス権制御を C++ コンパイラで強制する方法」
http://developer.cybozu.co.jp/kazuho/2009/06/c-c79a.html
をupgrade_lockを利用して実装してみます。
これはmutexと保護対象オブジェクトを密結合させたオブジェクトを作る事で、ロック無しでアクセスする危険なコードを禁止することを目的としています。read lockを確保した場合にはconstでしか値を取れないためうっかり書き換える心配もありません。
ヘッダ
// rwsync.hpp #include <boost/thread.hpp> #include <boost/noncopyable.hpp> template <typename T> class rwsync : boost::noncopyable{ T m_obj; typedef boost::shared_mutex smutex; smutex lock; friend class read_ref; friend class upgrade_ref; friend class write_ref; public: class read_ref : public boost::noncopyable{ // read lock boost::shared_lock<smutex> m_lock; const rwsync<T>* const m_ref; public: read_ref(rwsync& mutex):m_lock(mutex.lock),m_ref(&mutex){} const T& operator*() const { return m_ref->m_obj; } const T* operator->() const { return &operator*(); } }; class write_ref; class upgrade_ref : public boost::noncopyable{ // upgrade lock friend class write_ref; boost::upgrade_lock<smutex> m_lock; rwsync<T>* const m_ref; public: upgrade_ref(rwsync& mutex):m_lock(mutex.lock),m_ref(&mutex){} const T& operator*() const { return m_ref->m_obj; } const T* operator->() const { return &operator*(); } }; class write_ref : public boost::noncopyable{ // unique lock boost::upgrade_to_unique_lock<smutex> m_lock; rwsync<T>* const m_ref; public: write_ref(upgrade_ref& lock):m_lock(lock.m_lock),m_ref(lock.m_ref){} T& operator*() { return m_ref->m_obj; } T* operator->() { return &operator*(); } const T& operator*() const { return m_ref->m_obj; } const T* operator->() const { return &operator*(); } }; };
このようなヘッダを用意しておくことで
// 使用例 #include "rwsync.hpp" rwsync<std::vector<int> > sync_vector; // 宣言はこんなに簡単！ bool reader(){ rwsync<std::vector<int> >::read_ref vector_ref(sync_vector); // このようにロックを取ったオブジェクト経由でしかアクセスできない for(std::vector<int>::const_iterator iter = vector_ref->begin(); iter != vector_ref->end(); ++iter){ // 何か処理 } } bool writer(){ rwsync<std::vector<int> >::upgrade_ref vector_up_ref(sync_vector); if(vector_up_ref->front == 10){ // 配列の先頭が10なら rwsync<std::vector<int> >::write_ref vector_ref(vector_up_ref); vector_ref->push_back(20); } }
のように書けます
rwsyncから何らかのrefを通さない限りロックされているオブジェクトには触れられません。
また、read_refやupgrade_refからはconst付きのポインタ/参照しか得られないためオブジェクトに不用意に触れそうになったらコンパイラがエラーを吐いてくれます。
それを使ってハッシュマップを保護してみた例が以下に続きます。
unordered_mapでmemcached風のセマンティクスを実装します。
■
Boostに以前からread-writeロックは実装されていたようですがバグがあったとかで最近の物ではupgrade_lock, upgrade_to_unique_lockにさし変わっています。
ただのロックと比べてパフォーマンスが出やすい上に素性の良い設計だと思うので紹介してみようと思います。
read lock
read-lockをする場合はshared_mutexを引数にshared_lock
#include <boost/thread.hpp> using namespace boost; shared_mutex mutex; void reader(){ shared_lock<shared_mutex> read_lock(mutex); // ここでロック！ // クリティカルセクション }
スコープを外れると同時にshared_lockのデストラクタでアンロックされます。
write lock
write-lockする場合はshared_mutexに対して upgrade_lock → upgrade_to_unique_lockの順で取得してやる必要があります
#include <boost/thread.hpp> using namespace boost; shared_mutex mutex; void writer(){ upgrade_lock<shared_mutex> up_lock(mutex); upgrade_to_unique_lock write_lock(up_lock); // ここでロック！ // クリティカルセクション }
upgrade_lockというのは「同時に一つしか取れない特別なread lock」と考える事ができます。
read lockが既に取られているかどうかに関わらずupgrade_lockはただ一つのスレッドだけが保持可能です。これによりwriter同士の衝突ポイントをreaderとは別の段階で解決する事ができ、read lock→write lockの途切れない昇格が可能となります。*1
同時に一つのスレッドからしか取れないread lockですが、その他のshared_lockを排他する事無くreaderを邪魔しません。
何のためにあるのかというと
#include <boost/thread.hpp> using namespace boost; shared_mutex mutex; void hoge(){ upgrade_lock<shared_mutex> up_lock(mutex); // 書き換える必要があるかどうか調べる if(/* 書き換える必要があるなら */){ upgrade_to_unique_lock write_lock(up_lock); // ここでロック！ // readerを全て追い出した後のwrite処理 }else { // こっちの処理はreaderを排他せずに行える } }
のように書く事でread_lockと共存可能な利点を生かしスループットの向上が期待できます。
もし教科書的なread writeロックを用いて同様の目的を達成するなら
shared_mutex mutex; void hoge(){ read_lock rlock(mutex); // read lockを獲得 // 書き換える必要があるかどうか調べる if(/* 書き換える必要があるなら */){ rlock.unlock(); // デッドロックを避けるためにread lockを開放する必要がある write_lock wlock(mutex); // write lockを獲得 // 書き換える必要があるかどうか調べる(2度目! if(/* 書き換える必要があるなら */){ // やっと本命の処理 } } }
このようにread lockとwrite lock確保後にそれぞれチェックする書き方になります、書き換える必要性をチェックする処理が重い場合にはパフォーマンス低下を招きます。
2度チェックするのを避けるには、書き換える必要の無いときにもreaderを全て排斥するwrite lockを獲得するしかありません*2
upgrade_lock達の関係はすこしややこしいので
https://gist.github.com/22c650c292e94631bb84
このようなコードを書いて動作を試してみると良いかも知れません。
「矢印元のロックが確保されている状態で矢印先のロックを新規に確保できるか」を図に表すとこんな感じです。
Lock-free Stack
ではLock-free Stackについて図とプログラムを交えながら説明します。C++ではなくCを使います。
これは複数スレッドからロックによる排他無しで共有できるスタックで、外部には
node* top; void push(const T*, node** top); bool pop(T*, node** top);
を提供します。*1
このスタックはbottomへと繋がる線形リストをベースとして動作するため、配列ベースのスタックにパフォーマンスで劣ることもあります。*2
その線形リストを構成するノードのデータ構造から見てみましょう。
struct node{
T data;
node* next;
};
ごく典型的な線形リストのノードと同じです。
道具の紹介
lock-freeデータ構造を構成する場合に頻出のCompare And Swap。
C言語の擬似コードで書くと以下のような動作をします
bool compare_and_swap(void* address, int expected, int to_swap){ if(*address == expected){ // addressの中身が期待通りだったら *address = to_swap; // 上書きしてtrueを返す return true; }else{ return false; // 違ったらfalseを返す } }
上記の関数と同じ事をアトミックに実行してくれるCompare And Swap(以後CASと略)というCPU命令があります。
x86のCPUではcmpxchgという名前です。*3
push操作
void push(const T* data, node** top){ // ノードをコピーして node* newnode = (node*)malloc(sizeof(node)); newnode->data = *data; newnode->next = NULL; node* oldtop; // スレッドの作業用ローカルデータ do{ newnode->next = oldtop = *top; // ターゲットを定めて }while(!__sync_bool_compare_and_swap(top, oldtop, newnode)); // topの更新に成功するまで続ける }
プログラムではピンと来ないと思うので図に書くと
こんな感じの動作を目的としています。
・CASの動作前に既に下準備が全て終わっている事
・CASがアトミックな操作であること
がポイントです。このようにする事で
どのような競合があってもCASによりtopが自分を指すよう更新成功するのは1スレッドのみなので、正常なスタックを構成できます。
pop操作
bool pop(T* data, node** top){ node *nexttop, *oldtop; do{ oldtop = *top; if(oldtop == NULL){return false;} nexttop = oldtop->next; }while(!__sync_bool_compare_and_swap(top, oldtop, nexttop)); *data = oldtop->data; // 戻り値を用意 free(oldtop); // dataは退避済みなので消してよし return true; // pop成功
ルールとしてはこちらも「CASに成功した奴が正義」という点で同じです。
CASの成功を排他成功と見なし、自分が取り出しに成功したnodeの中身を返します。
non-blockingの意味するところ
海外の文献を読み漁っていると気づくのですが
2003年を境にこの文脈で使われる言葉の定義が変わります。
↑2003年ごろまでの構図
↑現在の構図。*1
non-blocking = obstruction-free という理解でもおおよそ間違いではないとは思いますが
論文を読むに当たって
non-blocking = ロックを使わないアルゴリズム全般
obstruction-free = 非lock-freeだけどロックだけはしない
というニュアンスの違いを感じます。
以後、現在の構図の方を前提に話します。ご注意ください。
まずは3つの分類の違いから
wait-free
操作が「他のスレッドの動向に関わらず有限ステップで完了できる」場合、そのアルゴリズムはwait-freeと呼ばれます。starvation-freeと呼んだりもします。
実際には初めからここに分類されるアルゴリズムは多くありませんが、例えばスレッド数に制約をつけたりすることでこちらに分類される場合もあります。
一見パフォーマンスが高そうに見えますが、必ずしもそうとは限りません。
少ないコア数の場合にはロックによる排他よりもスループットが低い場合も有り得ます。
実際にこの保証のあるアルゴリズムの必要性がある場面は私の知る限りではリアルタイム動作を保証したい場合のみで
・ロボットの操作（関節の操作が遅れると転んじゃう！）
・音響ソフトウェア（音が遅れて聞こえちゃう！）
などです。
ですがLinuxなどの非リアルタイムOS上でどうしてもwait-freeじゃないと…という状況は思いつきません。*2
また誤解が多いのですが「一定ステップで終了する事」ではなく「ステップ数の上限が固定できること」が条件なので
例えば「さすがに20スレッドに追い越される前には動作を必ず完了できる」場合などにもwait-freeの名前が付きます。
lock-free
操作が「いつも必ずどれかのスレッドで有効に行われている」場合、そのアルゴリズムはlock-freeと呼ばれます。進行保証が付いているとも言います。
歴史的な経緯からか意味と名前がいまいちぴったり来なくて、個人的にはwaste-freeとか呼べばいいのにと思っているけれど他に気にしてる人は居ないようです。
wait-freeと比べてstarvationが発生する危険があります。具体的に言うといつまで経っても他のスレッドに邪魔されて動作を完了できないスレッドが発生し得ます。*3
しかし前述したようにそれは必ずしもパフォーマンスの低下を意味しておらず、強いて言えば「レイテンシ保証を犠牲にスループットを手に入れた」という形容が適切な場合もあります。
obstruction-free
操作が「他のスレッドに邪魔さえされなければ終わる」場合、そのアルゴリズムはobstruction-freeと呼ばれます。lock-freeと比べて進行保証が付いていない特徴があります。
進行保証が無いと、複数のスレッドが走っていても「どのスレッドも全体での進行に寄与しない」瞬間が存在してしまいます。
lockを用いて居ないのになぜこのような事態になるかというと、複数のスレッドがお互いを邪魔しないよう動作した結果です。
詳しくはSTMの実装などを読んでください*4
一見性能が悪そうに見えますが、そもそも成そうとしている事が複雑なため必要なコストでしょう。
Nir Shavit先生も「STMをwait-freeもしくはlock-freeになるよう設計する事は可能だが満足のいくパフォーマンスは得られないだろう」と断言しています。*5
