細々と不定期連載を続けている愛用ヌメ革製品の日焼け状態をさらす日記です。以前のものは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スレッドがある。提供される関数は大差ないはず、必要に応じて調べて使いましょう。
少しずつ難しい話も増えてきたかな? 第３章です。
「第３章 正当性の検証と性能測定」
◯第３章で学ぶ内容
◯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でいいでしょう。
勉強会の2回目があったのでメモ、1回目は下のリンクからどうぞ。
「第2章 並行か非並行か？それが問題だ」
◯大前提
全ての処理を並列化することは出来ない。世の中には並列化が不可能な処理があり、何がそうなのか知っておく必要がある。並行化できないアルゴリズムは以下が代表例。
◯並行アルゴリズムの設計モデル
順序に依存しない処理を並行に実行する「タスク分解」と、大量のデータの個別の部分を並行して処理する「データ分解」がある。
どちらを選んでも基本のフレームワークは変わらない。タスクを準備し、スレッドへ処理を割り当て、次の処理へ進む前に全てのタスクが完了したことを確認する。
◯タスク分解
スレッドに割り当てるタスクを抽出する難易度はソースコードや処理内容に対する理解に反比例する。良く知っていればタスクの抽出も容易になる。タスクを簡単に見つけ出す裏技はないが、処理時間を多く占めるホットスポットにおいて、ループに着目するとそこがタスク抽出に適していることが多い。数値計算もタスク抽出のポイントとしておすすめ。
抽出したタスクの数にもポイントが有る。まずタスクの数はスレッド数(≒コア数)と同じ数以上にする。これはアイドルスレッドを避けるためである。次にタスクの粒度は出来るだけ大きい方が良い。これは並列化によるオーバーヘッドが生じることが影響している。タスクが大きい方がメモリキャッシュが効くなど性能面で有利な点がある。
タスク同士の間には2種類の依存性がある。1つ目は順序の依存で、あるタスクが他のタスクの処理結果に基づいて実行される場合が該当する。2つ目はデータ依存で、変数の使い方で問題が生じることがある。
タスクの割り当ては最初に決めてしまう静的割り当てと、動的にタスクを決める動的割り当てがある。タスクの処理時間が固定の時は静的割り当てが簡単でオーバーヘッドもなくてよい。処理時間にばらつきがある場合は動的にタスクを割り当てる必要がある。
◯データ分解
基本ルールはタスク分解と同じ。分割する数はスレッド数よりも多くする、細かすぎると並列化によるオーバーヘッドが問題になるので大きい粒度で。処理対象となる分割されたデータ領域をチャンクと呼ぶ。チャンク分割はタスクの粒度と境界長の比率が最大になるように分割すると良い。
チャンクの境界において、別チャンクのデータを参照する必要があると工夫がいる。簡単なのは境界部分を予めスレッドごとにコピーしておく方法がある(ゴーストセル)。そうでなければ処理時に必要に応じて参照させる方法があるが、参照対象のデータが未処理の場合、参照処理をまたしておく必要がある。どちらも一長一短がある。
「業務が組み込みメインでもそろそろ並行処理も避けて通れないよね」という雰囲気を年初から職場で醸し出し、勉強会を開くことにこぎつけました。内容は並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング
「職場の1人ができてもしょうがなくて、みんなの基礎がある程度揃ってないと話もかみ合わなくなるだろう」という思いが勉強会を選んだ理由の1つ。もう1つの理由は「勉強会ならサボらず最後まで読まざるをえないよね」という自分へのハッパがあります。今は他にも実用Git
前置きが長くなりましたが、まずは第１章「速くしたい人、手を挙げて！」です。
◯並列と並行の違い
・並行：複数の動作を同時に実行状態に保てる機能を備えていること。
・並列：複数の動作を同時に実行できること。
スレッドライブラリを使ってマルチスレッドプログラミングを実装し、シングルコア(Pentiumとか)でプログラムを実行した→並行処理
スレッドを使ったプログラムをCore i7で実行した→並列処理
ということですね。並列処理は並行処理に完全に包含される関係があります。
◯効率的な並行アルゴリズム
コア数に応じて処理時間が短くなる(2コアで1/2、4コアで1/4) が理想だけど、処理の一部は逐次処理が不可避な場合がほとんどで理想的な性能を得られることは殆どない。
特定のコア数を念頭においたアルゴリズムではなく、今後新しく発売されるCPU(16コアとか、32コアとか…)に応じて望ましい性能がそのまま発揮出来るように実装するのが目標。
◯スレッド化のステップ
通常の開発が1.仕様定義、2.設計、3.実装、4.テスト、5.チューニング、6.保守の流れを取るのに対し、スレッド化のステップは以下をとる。
逐次処理のソースで動く実装を固めるのが第１、いきなり並行処理アルゴリズムを実装すると元々の問題か、平行化に起因する問題か切り分けが必要になる。
◯歴史的な話
古くは複数の機器を組み合わせて処理を平行化する分散メモリプログラミングが主流だった。最近はCPUのマルチコア化が進んでいるので共有メモリプログラミングに移っている(本にはこんな記述無いんだけど理解があってるかな?)。
◯これから学んでいくこと
本屋で見かけたらどうにも気になってしまい購入して読みました。最初にこの本の存在を知ったのは日本半導体・敗戦から復興へ JBpress(日本ビジネスプレス)だったかな? この本の主張は前半部に固まっており、Webで読むことができるし、Amazonの書評を見ても大体わかるようになってます。
本書だと図やグラフ、実際のデータも使って説明されていますがざっくりまとめると
サラッと読めるので、興味があれば立ち読みしてみることをおすすめします。半導体に限らず他の業種でも同じような現象は少なからず起きているのではないかと。
あとはこの本がお勧めできない理由です。
この本の正しい使い方。
97個も話があると似たような話があります。もうちょっと整理してくれたら30個ぐらいにできたのに。
息抜きに読むとたまにヒントが得られる本だと思います。もっと砕けた感じが良ければアドレナリンジャンキーがおすすめです。
・・・
以下は自分が良いなと思ったエッセイです。
◯03 最大の問題は、多分技術的なことではない
相手を人として尊重し、憶測で非難しないこと。話しあうこと
◯08 すべてのものは、かならずエラーを起こす
エラーの影響を緩和するために何かを導入する度に、それが新しいエラーを増やしていく。
◯18 一般性よりも単純性、再利用よりもまず最初に使えること
推測による汎用性よりも、経験を通じた単純性の方が役に立つ。
単に汎用的であることを目標として設計された多くのものは、良く考えられていても何の役にも立たない。
◯37 ソフトウェア・アーキテクチャが倫理的な意味を持つことを考えよ
必須フィールドは特に害が無いように見えるかもしれないけど、設計者の都合をユーザに押し付けてしまっている。
設計者が楽をするためにわずかずつであっても他人の生活を不便にすることは倫理的ではない。
◯54 あなたの知識と経験を共有しよう
経験は1つだけど、そこから出来るだけ大きな知恵を引き出すためには経験に合理的な説明を加えなければならない。
簡単に説明出来るようになるまでは、対象を完全に理解しているとは言えない。
◯61 データがすべて
データはコードよりも概念として小さく、複雑度もかなり低い。
◯72 優れたコンテンツは優れたシステムを作る
新しくシステムを設計するときには、開発プロセスの一部を既存コンテンツの評価に当てるべき。
◯82 本当の顧客は目の前の顧客ではない
本当の顧客はあなたの顧客の顧客。
あなたの顧客の顧客が成功すれば、あなたの顧客が成功する。そうすればあなたも成功する。
◯日06 手段的な技術と陳腐化しない本質的な技術
ノウハウ的な知識ばかりが増えても背景にある理論を理解しないと作れないソフトが有る。
作業の90%はノウハウの積み重ねでソフトウェアの魅力が高められる。しかし残り10%で本質的な知識が要求される。そしてそこでソフトウェアの革新性が決定される。
© 2012 tune web · Proudly powered by WordPress & Green Park 2 by Cordobo.
Valid XHTML 1.0 Transitional | Valid CSS 3
