2014年3月15日

読書メモ: 魔導書vol3

プログラミングの魔導書vol.3 読書メモ
1

同書"Lock-free入門"(著者:@kumagiさん)を読んだときの読書メモ集約


yoh @yohhoy

魔導書vol3 p10迄: 逐次化不可能ってありえる?ありそうだが具体例分からん/線形化可能性=静止一貫性×逐次一貫性/"単一オブジェクトにおける"SCの意味がやっと分かった/SCはcausalityと言い換え可能?

2014-03-04 00:49:53
yoh @yohhoy

魔導書vol3 p14迄: "悪意"あるスケジューラvs進行保証/O-freeはblockingでも可?block,lockとは/Lock-free=Live L-free+Dead L-free/L-free!=Starvation-free/W-freeうーん

2014-03-04 01:05:17
yoh @yohhoy

http://t.co/4v6aIE8KiQ O-freeを満たすにはownerにschedが回ってこなくてもタイムアウトで解放されないとダメだから既に普通のlock機構じゃないな

2014-03-04 08:34:38
yoh @yohhoy

http://t.co/4v6aIE8KiQ W-freeは再入がある場合に有限step以内が実効上延々と遅延する?phase/cycle的機構が用意されることが前提なの?

2014-03-04 08:50:35
ARIESわからん @kumagi

@yohhoy blockingは「他のスレッドの何かを待つ必要があって、それがないと自分の操作が永久に進行できない」状態の事です。mutexを使っている場合には他のスレッドのアンロックを待つ必要があるのでblockingになりますが、タイムアウトなどがあれば別です。

2014-03-04 13:53:58
yoh @yohhoy

@kumagi ありがとうございます。気になったのはtimeout=権利獲得失敗なので操作としては進行(完了)しないと考えたのです。ここは、失敗による操作完了→O-freeという解釈になるのでしょうか?

2014-03-04 17:50:07
ARIESわからん @kumagi

@yohhoy タイムアウトしてしまったスレッドは確かに失敗になりますが、それによってアクセス権が開放されるので、任意の1スレッドが充分な時間単独で走れば自分の処理を完了させることが可能となり、O-freeの条件を満たします。

2014-03-04 19:59:46
ARIESわからん @kumagi

@yohhoy はい、タイムアウトで開放した際に、ロックによって守られていた不変条件をロールバックする仕組みもセットで必要になるので、気軽な実装では話が済まないです。

2014-03-04 20:01:09
ARIESわからん @kumagi

@yohhoy 実現手段の一つとしてphase番号による成功順の保証という方法があるだけであり、他にもW-freeの実現方法はあります。FetchAndAdd命令もそうですし、もっと言うと普通に変数を読むだけの操作等は他のスレッドによって阻害しようが無いのでW-freeです。

2014-03-04 20:03:54
yoh @yohhoy

魔導書の読書メモ/疑問点を呟くと@kumagi先生から回答を頂けるSNSはtwitterだけ!! (ありがとうございます)

2014-03-04 21:30:11
yoh @yohhoy

@kumagi 言われてみればWait-freeな操作は身近にありますね。 PS 誤植らしき箇所を見つけたのですがどちらに連絡するのがbestでしょうか?

2014-03-04 21:34:15
yoh @yohhoy

魔導書vol3 p22迄: ABA問題とノード名ABCでプチ混乱/LL/SCで偽陰性=弱いLL/SCが前提?強いLL/SCなら平気では/LL/SCでCASはよくあるがCASでLL/SCは初めて見た/強いLL/SCをエミュレーションになるかな?

2014-03-15 22:54:46
yoh @yohhoy

魔導書vol3 p36迄: L-free+追越禁止→先行他スレッド操作を補助してW-free化/同一カウンタ値でもOKの根拠は論文読め/コード中のthread_maxは誤植?/コード動作を追うのは途中で心が折れた(後で再チャレンジ)

2014-03-15 23:04:45
yoh @yohhoy

魔導書vol3 p39迄: lockstack最高性能…本例なら当たり前か/ofstackは実装複雑度からlfstackに負ける…これも当然だがO-freeの意義なくて残念/レイテンシ安定度にX-freeアルゴリズムの存在意義を求めるのはちょっと苦しい説明?

2014-03-15 23:13:13
yoh @yohhoy

魔導書vol3 Lock-free入門読了: 特に前半の概念説明に満足(とはいえ前提要求は厳しいか)。従前のX-freeアルゴリズムに関するテキトーな知識が矯正された。コード処理を追うのは人類には早すぎるので、必要に迫られたら出来合いのものを使いたい。

2014-03-15 23:19:25

同書"OpenACC"(著者:@fjnliさん) を読んだときの読書メモ集約


yoh @yohhoy

魔導書vol3 p44迄: OpenCLはCPU実行もサポート/XcalableMPは知らんかった分散環境用途?/非対応環境で無視されるという利点もあるけど逐次実行からの漸近移行もメリットかなぁ/ MSVCですら→でもOMPv2.0仕様止まりなので悲しい

2014-03-15 23:45:21
yoh @yohhoy

魔導書vol3 p48迄: 図1 I”#と$”#は何?データ化け?/acc kernels指示から必要なデータ転送コードが自動生成→関数分離されると死亡?/分散メモリモデルなのに転送自動化ってもの凄く危険では…/kernelsコンストラクト=計算リージョン?(明確な説明なし)

2014-03-15 23:59:37
yoh @yohhoy

魔導書vol3 p51迄: 自動検出できないループ依存関係→むしろ何が自動検出される?OpenMPとは違う考え方?/aac kernels loop⇔omp parallel forのような関係性?ちょっと違う気もする/今更だが1ホスト-1アクセラレータモデル?

2014-03-16 00:08:37
yoh @yohhoy

魔導書vol3 p52迄: OpenAACでホスト-アクセラレータ間の非同期実行は記述可能?/OpenMP4.0登場でOpenACCは単独で生き残れるのか/吸収併合の未来もありえる?(OMPv4.0からOpenACCへの言及があった気がする)

2014-03-16 00:15:58
yoh @yohhoy

魔導書vol3 OpenACC読了: ディレクティブ型並列化の駆け足紹介。ページ数の関係から仕方ないと思うけど、アクセラレータ型で一番重要なデータ転送関係の情報がもっとあると嬉しかったかなーと。

2014-03-16 00:20:08

同書"ErlangとScalaにおけるアクターモデルの紹介"(著者:@cooldaemonさん)を読んだときの読書メモ集約


yoh @yohhoy

魔導書vol3 p54迄: Erlang/Scala両未経験のため前提未満/選択的受信→メールボックスはアクター間共有? /軽量プロセスの実装ってグリーンスレッド実装と似てる?/軽量プロセス別GC→GCでsched占有なしのつながりを理解できない/GC毎停止するというだけ?

2014-03-16 00:37:46
残りを読む(1)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?