[[ノート/ノート]]

*並列探索 [#j43fd7a1]
**投機的(=無駄な)実行の考え方 [#f3bb5e39]
投機的実行(speculative execution)という考え方がある。言葉上の定義は、「最終的にはその結果を捨ててしまうかもしれない(=無駄になるかも知れない)コードを実行すること」と言えるだろう。[[ウィキペディアの投機的実行の説明より:http://ja.wikipedia.org/wiki/%E6%8A%95%E6%A9%9F%E7%9A%84%E5%AE%9F%E8%A1%8C]]

古くは、CPUの命令実行パイプラインにおいて、条件分岐命令の実行時に、条件成立か不成立かの判断が分岐後の命令の実行開始より遅れるときに使われてきている。たとえば分岐方向を予測してその分岐による処理を判断結果が出るより先行して行い、もし予測が当たっていればそのまま使い、予測が外れていれば結果を捨てて処理しなおす。単純に判断結果が出るまでパイプラインを止める(ストールさせる)よりは、予測が当たっている場合には早く実行できることになる。

このような仕組みを計算時間で評価すると、計算時間の期待値は、(予測が当たる確率×予測側の経路の実行時間)と(予測が当たらない確率×外れた側の経路の実行時間)となるが、予測側はパイプライン効果により時間が短縮されているはずであるのに対し、外れた側はやり直しにより時間がかかる。パイプラインの構造(段数等)自体は変わらないので、全く予測せずにストールさせる場合に比べると必ず時間が短縮されるだろう。

同じような考え方は、たとえばハードディスクやファイルのプリフェッチにも適用される。

最近は、MapReduceやHadoopなど大規模な分散システムで使われている記述がある。
-[[MapReduceのマニュアル:http://hbase.apache.org/book/mapreduce.specex.html]]、
-[[Improving MapReduce Performance in Heterogeneous Environments (OSDI'08 Proceedings of the 8th USENIX conference on Operating systems design and implementation):http://www.usenix.org/event/osdi08/tech/full_papers/zaharia/zaharia_html/]]、
-[[Operating System I/O Speculation: How two invocations are faster than one (Usenix 2003?):http://www.usenix.org/event/usenix03/tech/fraser/fraser_html/node3.html]]、
-[[Speculative execution in a distributed file system (ACM Trans. Comput. Syst, 2006, 361--392):http://www.eecs.umich.edu/Rio/papers/nightingale06_1.pdf]]

**探索問題の並列化と投機的実行 [#u1a915c8]
探索問題は一般に、解析的な手法で最良解が求められないような問題の解を、探索によって求めることと考えられる。簡単な解説は [[ウィキペディア:探索:http://ja.wikipedia.org/wiki/%E6%8E%A2%E7%B4%A2]] を参照。

探索空間がトリー状に与えられている場合、直列計算機では幅優先探索を出発点として、さまざまなヒューリスティックな方法が提案・利用されてきた。(ここではその詳細は省略)

また、探索の一種として、「組合せ最適化」という範疇([[ウィキペディア:組合せ最適化:http://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E6%9C%80%E9%81%A9%E5%8C%96]])では、順序立てて探索するのではなく確率的に探索をする
-遺伝的アルゴリズム
-焼きなまし法
-蟻コロニー最適化(「群知能」)
-タブーリスト
などが提案されている。

これらの確率的な方法の多くは、いくつかの「可能な探索方向」を提案しその中からランダムに(重みはあるかも知れないがとにかくランダムに)探索方向を選択し、必要であれば枝を刈りこむなどの処理を経て、最終的に可能な経路を探し出す。アルゴリズム自体が、たとえば(自己組織的な)エージェント型になっていたり、そうでなくても(つまり1つ頭であっても)いくつかの可能経路を並行的に評価するなど、並列処理に向いているものが多い。

それぞれの方法の良し悪しは、問題空間との整合性や探索効率(経路発見期待値)などによって評価できるのかもしれないが、一般にはかなり大くくりな議論しかされていないように見える。また、ここでそれに踏み込むのは目的ではない。

**自明ではない並列性の利用方法 [#jdb618c2]
並列性の利用の観点から考えるとき、多数のエージェントが自律的に同時並行に部分判断を重ねるようなエージェント型の手法の並列化は、自明と言えるだろう。具体的には、それぞれのエージェントにCPUを割り当て、それらの間の同期や通信量をなるべく少なく抑えることが、性能向上に有効であろう。この問題はここではわきに置くこととする。

ここで、2つの疑問を考えてみたくなる。

1)自律的判断をするエージェントが多数集まったもの(自己組織系と関わるか ?)では無いもの(何らかの中心的判断機構や判断をガイドする機構があるもの、と考えていいのだろうか?)、を考えるとき、「エージェント的」との違いは何だろうか? そして、それらが意味があるのだろうか? 大規模並列を考えるとき、すべての、「人工知能」的探索問題や組合せ最適化が、「エージェント型で解くべきである」という結論なのだろうか? 

2)パフォーマンス上の比較をどのように行えばいいのだろうか? パフォーマンスとは何か。探索問題の場合に、(収束速度、結果の正確さ)を求めると考えられるが、2つの要素のそれぞれをどう定義するか、そしてどうバランスするか?

***自律多エージェント [#i14fff8e]
用語の範囲がどの程度確かであるのか良く分からないので、整理してみたい。
-エージェント~
未整理だが、2つの全く異なる(?)ものに使われているような気がする。
--Carl HewittのActor Model を1つの足掛かりと考えると?(ここまで戻るのか?)~
この枠組み全体は、今考えたいものと同じような気がする。~
その後の研究は、[[Actors and Continuous Functionals:http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-194.pdf]] こちらの方向〜Communicating Sequential Processesの方向へ流れているように思う。今欲しいのはこの流れではない?
--仲介役をするもの、「ソフトウェアエージェント」~
[[ウィキペディア:ソフトウェアエージェント]]では、この枠組みの中で、知的エージェントとか自律エージェントとかが派生したように書いてあるが、本当だろうか?
-自律エージェント~
元のエージェントの定義は自律的と思う。でも敢えて「自律的エージェント」と呼ぶ分野があるようにも見える?~
~
-マルチエージェント~
元のエージェントの定義は、マルチで意味を持つと思う。でも敢えて「マルチエージェント」と呼ぶ分野があるようにも見える~
-エージェント・ベース・モデル
-セルラ・オートマタ


で、非エージェント的、非分散的、解法との違いは、何だろう?

≪もう少し後で書こう≫

**「性能」に関する議論 [#ie074927]
まだ、サーベイをしていない。

「性能」に関する考え方は、多様=ケースバイケースであるような気がする。たとえば、
-なんとなく収束すればよい(たとえば確率的に半分以上のケースで収束すればいい?)。収束速度の多少の差は気にしない。特に、もともと直列型のアルゴリズムでは組合せ爆発するような探索の場合には、このような議論をするのかもしれない。~
イメージは、遺伝的アルゴリズムだったり、蟻コロニーアルゴリズムだったりする。~
でも、もう少し突っ込めるのでは??
-もともと直列型の(まあまあの性能の)アルゴリズムがあって、それを並列に実行する場合~
-もともと直列型の(まあまあの性能の)アルゴリズムがあって、でも、もう少し発散するような計算順序で計算してしかし(無駄な計算を許すが)並列実時間では早くなる場合
-もっとほか?

それが「言い訳」にも使われてきたのかもしれない。

**ゲームの木の探索の並列化? [#lbfee834]
**木の探索の並列化? [#lbfee834]
ゲーム等の木の探索を並列化することを考えてみる。

-幅優先ですべて(exhaustiveに)探索



トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS