aws memo

AWS関連の備忘録 (※本ブログの内容は個人的見解であり、所属組織及び企業の意見を代弁するものではありません。1年以上古いエントリは疑ってかかってください)

訳:HPC : 並列処理におけるLinked List とTree

Dr. Dobb's | Go Parallel | Linked Lists Are, Like, So Last Century | Dr. Dobb's and Intel Go Parallel Programming

http://drdobbs.com/go-parallel/blogs/parallel/232400466

====

リンクドリストは、直列に並んだ(特に未ソートの)データ集合を保持する用途に使われる動的データ構造である。最も単純なパターンでは、「ヘッド」ポインタがリストの先頭ノードを指し示す。ノード群は自身が持つデータと、リスト上の「次」のノードへのポインタを持つ。「次」のポインタがNULLだった場合、そのノードはリストの終端である。追加のポインタは、より速いアクセスを行うための特殊なものである。例えば、リストの末尾を指す「tail」ポインタは、リストの最後尾に新しいノードを追加する処理を速くする。

なぜリンクドリストは開発されたのか?配列は悪かったのか?リンクドリストがリスト中の要素に対してランダムアクセスをサポートしていない一方、ノードの挿入、削除、再配置をO(1)で行う。そして、(システムのメモリ使用可能量以外において)リストが保持できるノード数に制限が無い。アクセスとデータ移動の制限があるので、配列とリンクドリストは補完的な関係に見える。プログラマは、アルゴリズムの状況にベストフィットする使い方を学ぶ必要がある。

並列プログラミングの時代に入って、リンクドリストは依然としてその地位があるだろうか? ワシントン大学のDan Grossman曰く「No」。SIGCSEカンファレンスでGrossman教授によってプレゼンされたその急進的なアイディアを同僚から聞いた。その主張はこうだ。ツリーは、リンクドリストを使いたいと思ういかなる場所にも使える。(私の中では、リンクドリストとツリーがAnnie Get Your Gunの「Anything You Can Do」を歌っているアニメが見えた。すべてのデータ構造が パイを焼ける(bake a pie)とは思えない)Grossman教授のアイディアは異教なのか、それとも先進的なのか?後半で説得させてほしい。

リンクドリストは、逐次処理に適した直列データ構造である。ツリーは、以前の3ポストにわたって解釈したようにfork-join並列化の典型である。リンクドリストと同様、ツリーは動的に拡張でき、構築できる。新しいリーフノード追加に要する時間は一定ではないが、よく組織化されたツリーではO(log n)で可能であり、tailポインタ無しでリスト末尾に追加するために2つのポインタを捜査するのに必要なO(n)よりも良い。リンクドリストを使いたい時に、他に行う操作は何だろうか?それらは、特に並列環境では、ツリーでエミュレート可能だろうか?ここに、いくつかのリンクドリストの操作と、それをツリーで「模倣」する方法がある。

全ノードを処理する場合

逐次にリンクリストの全要素を処理する場合、シンプルにリストの先頭ノードから開始し、ノードを処理し、次のノードに移動し、それをノードの末尾まで繰り返して完了する。もし、ノードの処理が他ノードの処理と独立した関係であれば、ノード処理はどのような順序でも可能であり、マルチプロセスかマルチスレッドで並行可能である。データがツリー構造であれば、スレッド(タスク)によって処理される前か後に、現在のノードの全子ノードをルートとするツリーを処理する並列タスクとすることができる。システムリソースが逼迫するのに十分なタスクを生成すると、それ以上新しいタスクを生成せず、既存タスクにより子ノードを処理する。

タスクによるノード処理負荷をより良くバランスさせるために、ツリー構造はバランスかバランスに近い状態にすべきである。タスク群が、ツリーの同一階層で生成された場合、各タスクは同数のノードを処理する。利用可能なバランス木の種類はたくさんある。良いデータ構造を探す選択肢を学ぶべきだ。どんな操作が必要なのか、最も使われているのか、によって選択が決まり、複数スレッドがアクセス可能なのかどうか、並列に更新可能な木なのかどうか?を考える。

探索

この事例では、ソートされていない探索を考える(もしすでにソート済みデータを持っていれば、タスクを生成するオーバーヘッド無しに、2分探索木でほしいノードに降りることができる)。二分木には3つの標準的な探索アルゴリズムがある。 preorderと inorder、そしてpostorderだ。3つとも再帰的に定義されているので、すぐに並列タスクを生成すべき箇所を見つけだせる。もしこれらの探索操作に不慣れなら、データ構造のリファレンスを再度見直すとよい。

データ集合内のある値を探したら、現在実行中のタスクに対して探索完了・停止の信号を出し、停止中のタスクが実行を始めないようにする、といった並列探索の巧妙な点を行う。他方、探索対称の値の複製がツリー内にあり、それを徹底的に探索するなら、値が見つかっても探索を終了させてはならない。

キューやスタックを模倣する

この2つの事例では、共通の構造でデータが挿入・削除される。これらは、「排他制御」という言葉に留意する。キューやスタックを模倣する共有リンクドリストのように、同様の機能を行うツリーは2つ以上のスレッドによる要素の追加・削除(もしくはその組み合わせ)される際に守る必要があるため、データのロスト、重複、破壊が無いことを保証しなくてはならない。(I hope these last few sentences were just wasted typing on my part and you already were aware of all that.)

キューやスタックの模倣のように、優先度キューも、ツリー上でヒープ構造を使うことで簡単に模倣できる。単純キューやスタックの厳格な実装は、ツリーでは多少複雑になる。並列実行順序は非決定論的(結果は決定論的)になりうることを考慮すべきである。

並列計算でスタックとしてリンクドリストを使うなら、並行処理の本質により、要素の処理順序は多くの場合で不定ある(もしアルゴリズムが特定の処理順序を求めているなら、並行処理を使うべきではない)。データの挿入・削除を安全に行う方法さえあれば、ヒープのようにどんなツリー実装でも行える。

非ソートデータを並列処理する際に、直列リンクドリストをあきらめてツリー構造を選ぶことにご納得いただけただろうか?私はだいたい納得した。良い考えであり、上記の記述で考えが動いたが、実用に落とす機会がない。データに対して伝統的なリンクドリスト操作がある場合、ツリーにすることができない。最初に思いついたのは、ソート済みfrequency list である。この構造は逐次アクセス・探索に基づいている。Can you think of any list access method/algorithm that could execute in parallel, but requires a sequential linked list or whose structure could not be made to fit into some variation of a tree?