細々と不定期連載を続けている愛用ヌメ革製品の日焼け状態をさらす日記です。以前のものはBREEタグをつけた日記一覧で見ることが出来ます。
まずはカバン。相変わらずしっかりしていていますが、使用頻度が落ちているからかもしれません。一度雨の日があるとカバンを取り替えてしまい、翌日以降晴れていてもこのカバンを使わないことが多いです。日焼けは前とそんなにかわりないかも。
色が濃くなっているのはこの財布が一番。毎日使っているからか、手垢がつくからか手入れをする度に汚れがたくさん落ちます。ところどころ痛んできていますが、まだまだ使えそうです。鞄と同じく4年選手です。
一番使用頻度が低いのが名刺入れ、研究開発職だと名刺交換をする機会が少なくてついつい鞄の中に入れたっきりにしてしまいます。もうちょっと使ってあげないとな。
せっかくなので色の変化を時系列で並べてみました。こんな感じで色がついていくという参考になれば。
◯2005年12月
◯2006年8月
◯2007年4月
◯2009年5月
◯2010年5月
いよいよアルゴリズムの並行化に着手する。今回は並列和、プリフィックススキャン、セレクションの3種類。
◯並列和
配列の和を全部求めるよくある処理。楽なのはOpenMPやTBBを使ってリダクション処理をそのまま利用すること。
自前で実装するなら配列をスレッド数で分割して個別に小計を計算。全スレッドが計算終わったら小計を全部足して合計をもとめるというやり方がおすすめ。
◯プリフィックススキャン
[3, 5, 2, 5, 7, 9, 4, 6]という配列を与えたときに[3, 8, 10 15, 22, 31, 35, 41]という配列を求める。配列のN番目に元の配列の0〜N番目までの和を入れておく処理に当たる。包含的プリフィックススキャンとも言うらしい。
先頭を覗いて[0, 3, 8, 10, 15, 22, 31, 35]の配列を求める排他的プリフィックススキャンの方法もある。
並列化の手法として、スレッド数で配列を分割し、個別にプリフィックススキャンを行う。次に末尾の要素を使って前後のチャンクに伝搬させる値を計算する。計算が終わったそれぞれのスレッドが担当するチャンクに値を加算してプリフィックススキャンを完了する。
さっきの例を3スレッドでやるとこんな感じになる。2と4のステップが並列化可能になる。
2から3、3から4に移るときに毎回スレッドを生成/破棄するとオーバーヘッドになるので、スレッドのイベント通知機能を上手く使って使いまわすのが吉。
1. 入力をスレッド数で分割
[3, 5, 2, 5, 7, 9, 4, 6] -> [3, 5, 2], [5, 7, 9], [4, 6]2. 個別にプリフィックススキャン
[3, 5, 2], [5, 7, 9], [4, 6] -> [3, 8, 10], [5, 12, 21], [4, 10]3. 配列の末尾の値で排他的プリフィックススキャンを行い、伝搬させる値を計算する
[3, 8, 10], [5, 12, 21], [4, 10] -> [10, 21, 10] -> [0, 10, 31]4. 3で求めた値を2の処理結果にそれぞれ加算
[3, 8, 10]+0, [5, 12, 21]+10, [4, 10]+31 -> [3, 8, 10, 15, 22, 31, 35, 41]
◯セレクション
配列をソートしてN番目の値を取ってくるという処理。
ソートしてもいいけど、1回しか呼ばれないとか、適宜順番が変わるような配列だとセレクションがおすすめ。
公知のセレクションアルゴリズムがあって、その中でいくつかを並列化する。
1. 配列数がQ(本では5を勧めている)より小さければデータをソートして、k番目の要素を返す。Qより多ければ次のステップへ
2. チャンクから中央値を選ぶ(本では配列を分割して中央値を求め、その中からさらに中央値を求めるやり方をしているけど、配列の中身が適度にバラバラなら適当に選んでもいいかも)
3. データを A.中央値より小さい値を持つ B.中央値と同じ値である C.中央値より大きい値を持つ の3種類に分け、A,B,Cの数を数える。
4. 求めるk番目の要素がどこに入るかを調べる。Bに入るなら値を返して終了、AかCなら再帰的に1から処理を続ける。
本で高速化しているのはこのうちの2の処理、3の処理、4の処理の一部である。ポイントは4の処理で、再帰的に呼び出す際の配列の部分集合を使うのにプリフィックススキャンを使って詰め直し先のインデックス値を求めている。逐次処理に慣れきっていると重そうだけど、実際実行してみたら早いのかな? 要検証。
ソフトウェア開発者のみならず、あらゆる分野でその道を極めようとしている人におすすめです。プログラマ固有のところは極めて少なく、自分の人生を自分で切り開いていくために必要な情報が分かりやすく整理されています。
以下この本で気になった所を引用しておきます。この本がプログラマ以外の人にも示唆に富む内容であることが伝わるのではないかと。
より良い製品を作って仕事を確保することだけが大切なのではない。より実りある人生を送るためのスキルと感性を磨くことも大切だ。人生には素晴らしいことがたくさんある。仕事はそのひとつに過ぎない。(David Heinemeier Hansson)
偉大になることを望んでいる人のほうが、自分の仕事をこなせれば良いと思っている人よりも、偉大になる可能性がずっと高いからだ。
何かのスペシャリストであると言うことを、単に他のことを知らないという意味で使っている人が多すぎる。
ビジネスの仕組みを知りもしないで、ビジネスが利益を上げるために想像力を働かせて協力できるだろうか?
・・・
想像力を働かせて付加価値を高めるためには、自分が関わるビジネスについての徹底的な理解が必要だ。
本当の意味で何かを習得しようと思ったら、誰かに教えてみることをおすすめする。自分の理解をはっきりした形にする一番いい方法は、自分の言葉を使って、他の人にもわかるように説明することだ。
プロセスを身につけたいなら実践しろ。
いいマネージャの役割は、チームの仕事に優先順位を設定し、チームが仕事をこなすために必要なものを用意し、チームがやる気と生産性を維持出来るように配慮し、最終的に要求を実現することにある。
短く働いた方が、より多くの成果をあげられる。
ソフトウェアの品質が本当の意味で試されるのは、何か問題が起きた時だ。
本当に出来ないときに臆せずに「できません」と言える強さを持ったチームメンバーがいれば、彼らの「できます」という言葉には偽りが無いと確信出来る。
多くのソフトウェア開発者は勘違いしている。事情に通じたマネージャや雇い主なら自分の技能を見ぬいて当然だと思い込んでいるんだ。・・・全部言い訳。彼らは怖がっているだけさ。
誰かが何かすごいことをしても誰もそれを知らなければ何もなかったのと同じだって言うんだ。
大局的に見るなら、作文技術は必要かつ供給不足なんだ。
君ももっと大量の文章を書くことになる。文章を書くことが仕事の一部になるとすれば、もっと作文技術を磨いた方がいい。
君に信念がないと、こういうことはできない。会社の連中が間違った事をするのを傍観していられない。改善の余地があるなら君が変えなければ。
目立つっていうのは、聞かれる前からみんなが君のことを話題にするっていう意味なんだ。
君のキャリアにとって本当に重要なのは昇進でも昇給でも無い。重要なのは、そういう成果を得るために努力した時間だ。もっと重要なのは、そういう成果とは関係ないところで努力した時間だ。
短いので今週は2章分まとめて読みました。
◯第４章 マルチスレッドアプリケーション設計の8つのルール
・8つのルール
・ルール1: 真に独立した処理を特定する
これが最も重要。 処理が互いに独立していなければ並行実行できない。
・ルール2: 並行性はより上位で実装する
並行性を見つける方法は2種類ある。
どちらを選ぶにせよ、より上位で並行化した方が良い。 アルゴリズムの上位レイヤほど、より多くの独立した処理を含んでいるからである。
・ルール3: コア数増加に備えスケーラビリティ対応を早期に計画する
今後もプロセッサコア数は増加の一途であることが予想される。 開発中のソフトウェアであっても、このことは考慮に入れておくべき。
並行性の設計はタスク分解とデータ分解の2種類があったが、 アプリケーション内の独立した処理とデータサイズではデータサイズの方が増える傾向が強いため、 データ分解設計の方がスケーラビリティーでは有利である。
設計中のソフトウェア/システムが計画している処理能力を十分に達成できても、 将来要求される処理能力は増加する可能性が高い。 処理能力に余裕があれば、処理するデータはまだ誰かが持っている。
・ルール4: スレッドセーフなライブラリを使用する
車輪の再発明は決していい方法ではない。 一般的なライブラリ関数で置換可能であればそれを使うこと。
使用の際には、マニュアルを参照してライブラリがスレッドセーフであるかを必ず確認する。 自作ライブラリなら関数がリエントラントであるように設計する。
・ルール5: 適切なスレッドモデルを採用する
スレッドの明示的な使用(Pthread/Windowsスレッドの直接的な利用)は避けるべき。 抽象化ライブラリ(OpenMP/Intel Threading Building Blocks)を通してスレッドを利用すること。 多くの並行化作業はスレッドを明示的に操作する必要があるほど柔軟性が求められておらず、 実装が複雑になるとバグが入る可能性が高くなる。
開発上の規約などにより、抽象化ライブラリの使用が禁止されている場合でも、 プロトタイプは抽象化ライブラリを使うことで手間を省くことが出来る。
・ルール6: 実行順序を前提としない
スレッドの実行はOSなどのスケジューラで管理されるものであり、 アプリケーション側で順序を決定することは出来ない(非決定性がある)。 スレッドがどんな順序で実行されても正しい結果を返すように設計すること。
また性能の観点から、出来る限りスレッドの実行に制約を課すべきではない。 例えばスレッド処理の待ち合わせをするときは本当に必要か立ち止まって考える必要がある。
・ルール7: ローカル変数を使用する、できなければロックで保護する
同期処理は必要悪だが、最小限の使用に留める必要がある。 共有変数の更新が少ないほど、オーバーヘッドも少なく済む。
まずはスレッドごとに持たせるローカル変数で問題が解決出来ないかを考える。 駄目なら適切なロックを共有データに対して適用する。 デッドロックの温床となるため、1データに対して複数のロックを対応付けてはならない。
・ルール8: 並行性向上のためのアルゴリズム変更を恐れない
逐次処理では最良だったアルゴリズムが、並行処理では最良でないことがある。 並行化出来なかったり、他のアルゴリズムの方が並行化による恩恵を受けやすいことがある。
◯第５章 スレッドライブラリ
・抽象化ライブラリ
スレッドの制御(作成・管理・同期)を抽象化し、プログラマに楽をさせてくれるライブラリ。 スレッドを明示的に作成する処理は無く、柔軟性は落ちる。
・OpenMP
専用のpragma、指示文(ディレクティブ)、環境変数を用いて並行処理可能な部分を指定する。 並行実行コードはコンパイラにより生成される。 並列環境と非並列環境でほぼ同一のソースコードを使用できるという利点がある。
スレッドの管理はfork-joinモデルを採用している。 マスタスレッドが並行処理可能な領域(パラレルリージョン)に到達すると、子スレッドが生成され(fork)、 各スレッドがパラレルリージョンを実行する。 パラレルリージョンの終了時には子スレッドが待ち合わせ(join)、 パラレルリージョン後からメインスレッドが処理を続行する。
・Intelスレッディング・ビルディング・ブロック
並列アルゴリズムが定義、実装、提供されており、 並行処理がカプセル化されたクラスを通して使用する。 商用バージョンとオープンソースバージョンがある。
・明示的スレッドライブラリ
PthreadとWindowsスレッドがある。提供される関数は大差ないはず、必要に応じて調べて使いましょう。
フジテレビの深夜放送を追いかけ続け、ようやく見終わりました。録画に失敗した回は全部で2回、うち1回は巨人の優勝による放送時間の変更だったのでかなりの確率で録画できたんじゃないかと。もっとも録画の成功は妻によるところが大きいのですが・・・シーズン8はぜひ1週間の集中放映に戻して欲しいのですが、どうなるのでしょうか。
内容的には結局いつも通りなのかなという感想です。舞台がワシントンDCに代わって、所属する組織がFBIに変わってもストーリーの作り方がどことなく既視感を覚えます。シーズン8で終わってしまうのは寂しい気もしますが丁度いいところなんじゃないですかね。
![モンスターズ・インク [DVD]](http://ecx.images-amazon.com/images/I/51kdmy0EEXL._SL160_.jpg)
「今まで見てなかったの？」というぐらい遅れていますがようやく見ました。Pixarの映画の中でもピカイチで面白かったと思います。設定も面白く、ラストも綺麗な終わり方でした。
娘がもうちょっと大きくなったらぜひ一緒に見たいと思います。娘が気に入ったらDVDも買ってあげないとな。文句なしに5ツ星です。
少しずつ難しい話も増えてきたかな? 第３章です。
「第３章 正当性の検証と性能測定」
◯第３章で学ぶ内容
◯Ben-Ariの4つの並行実行一般化
どんなプログラムも最小の実行単位に分けられる。並行処理は”最小の実行単位”が様々な組み合わせで実行される。実装されるアルゴリズム/プログラムはいかなる組み合わせでも正しく実行されなければならない。正しく実行するとは特定の処理が意味もなく除外されないことも含む…ということだと理解しました。
◯クリティカルセクション問題を例にBen-Ariの性質を学ぶ
共有変数を参照/更新するソースコード部分”クリティカルセクション”の実現の方法を通して、Ben-Ariの性質を学ぶ。本では5つの段階を追って解説していますが、ここでは割愛。問題にしたポイントは以下のとおりです。
ということで、スレッドプログラミングでよく陥りそうな問題が満載です。最終的に第５段階として紹介されているのがデッカーのアルゴリズム – Wikipediaです。でもこのアルゴリズムだと2つのスレッドしか排他制御出来ないので、ランポートのパン屋のアルゴリズム – Wikipediaやピーターソンのアルゴリズム – Wikipediaが実用にはいいそうです。でもこの節で学ぶべきは使うアルゴリズムの選択じゃなくて、どういう所に着目して問題を見つけるのかというやり方なので、きちんと学んだことがなければ本を当たった方がいいと思います。
◯デッドロックを発生させる4つの条件
4つの条件はANDで発生する。どれか1つでも成立しなければデッドロックには成り得ない。
デッドロックを避けるにはどれか1つでも起きないようにすればいいらしいけど、複数リソースのロックとか危ういものは出来るだけ避けた方がいいと思う。
◯並行化によってどれぐらい性能が上がったか?
高速化率はどう伝えるべきか? 筆者いわく倍数がいいとのこと。 105%の高速化率と言っても元より5%速くなっただけかもしれないし、205%の高速かもしれない。2倍といったら受けてが迷うこと無いよね とのこと。確かにその通りかも。
逐次処理を並行処理に置き換えた際にどれぐらい高速化出来るかの見積はアムダールの法則 – Wikipediaやグスタフソンの法則 – Wikipediaで出来る。グラフを書いてみると一目瞭然だけど、並行化出来ない処理がたとえ25％でも含まれていると、どんなにコア数を増やしても3倍までしか速くならない。
翻訳の質が低くて残念
言いたいことは全てAmazonに投稿されている書評で言ってもらった気がします。
翻訳の質が低くて残念です。
すでにgitについてある程度の知識を持っている人でないと、そういったミスリーディングな翻訳文から真の意味をつかむのは難しいと思います。
「入門git」と「入門Git」を制覇して次のステップを目指す人が、翻訳のまずさを自力で補う覚悟のうえで買うのなら、よい本です。
駄目な本かというとそうではなくて、Gitについてこの本より詳しく記述された文章はネットでもないので貴重だと思います。個人的にもgit-svnの使い方が大変勉強になりました。そこだけで3000円ぐらい払っても惜しくないぐらいです。たまに出てくる意味が取りにくい訳がなければ星4つ、O’reilly独特の言い回しが邦訳で取り払われていれば星5つだったと思います。
Gitのオブジェクト管理についてはWEB DB Press Vol.50でも、入門Gitでも紹介されていますが、この本が一番詳しく、説明が丁寧で、わかりやすかったです。Gitをじっくり学びたい人におすすめです。使いたいだけなら入門Gitでいいでしょう。
![トランスフォーマー スペシャル・コレクターズ・エディション [DVD]](http://ecx.images-amazon.com/images/I/51b8%2Bm6RccL._SL160_.jpg)
映像だけが取り柄のB級大作映画。長いくせに前半がグダグダなのでそこで見限らないように注意が必要。
ロボットがかっこいいんだけど何度も変身してると飽きてくるし、敵か見方か一見してわかりにくいのもマイナスだと思う。
吹き替え版で見たんだけど、主役級ロボットのオプティマスプライムの口調がおかしくて仕方がなかった。子供の頃は大好きだったはずなんだけど…
![デトロイト・メタル・シティ スタンダード・エディション [DVD]](http://ecx.images-amazon.com/images/I/61fhXeYBxKL._SL160_.jpg)
GO TO DMC! GO TO DMC!! GO TO DMC!!!
ということで、原作を読んでいた自分ですが、割と忠実に映像化してくれていて楽しむことが出来ました。Amazonのレビューの焼き増しになってしまいますが序盤急ぎ足でエピソードが消化不良なのと、オリジナルのラストがイマイチだった以外は登場キャラが皆ハマリ役だったと思います．
© 2012 tune web · Proudly powered by WordPress & Green Park 2 by Cordobo.
Valid XHTML 1.0 Transitional | Valid CSS 3
