大量のコンピューティングリソースを活用するためのソウトウェア基盤

横山 大作

アイテムタイプ

学位論文 / Thesis or Dissertation

言語

日本語

著者

横山大作

著者別名

ヨコヤマダイサク

Abstract

近年、並列・分散計算環境は急激に普及している。素子の発熱などの問題により単体計算機の性能向上が妨げられている現在、高性能な計算機を現実的なコスト性能比で構築するためには、多数の計算機を用いた並列計算を用いなければならない。また、計算機は急速にコモデティ化しているため、普及型CPUを多数集めて構成した大規模計算機や、パーソナルコンピュータを一般的なネットワークで接続したPCクラスタといった構成が多く使われている。また、ネットワーク技術の発展により、複数のクラスタを結合させたグリッドや、個人の遊休計算機を使用するデスクトップグリッドなど、より広域に広がった分散計算環境も実用的な存在となってきた。さらに、単体CPU内においてもマルチコアプロセッサが一般的なものとして普及を始めている。このように、近年の計算機はさまざまなレベルの並列性を持ち、大量の計算リソースを一度に利用できる並列環境を利用することも比較的簡単になりつつある。しかし、現在のソフトウェア開発においてこのような環境を十分に活用することは依然として難しい。これは、並列プログラムを作る際に、(1)いかに実行効率が良好な設計を行なえるか//(2)いかに正しく実装するか//の二つの側面において、未解決な問題点が存在しているためである。//(1) 実行効率の良いプログラムを設計するためには、あるアルゴリズムがある環境ではどれくらいの時間で実行できるのか、を正確に把握するための計算量モデルが必要になってくる。これまでにいくつかの並列計算量モデルが提案されてはいるが、これらは単純過ぎて現実の計算環境を表現できていなかったり、特定の環境や特定のアルゴリズムに限定したモデルになってしまっていたりと、満足できるものにはなっていない。アルゴリズム設計において必要とされるのは、特定の環境における実行時間の精密な見積もりよりは、現在のさまざまな計算環境とこれから使用可能になるであろう計算環境とで、対象アルゴリズムがどのような振る舞いを示すのか、を定性的に示すようなモデルである。現在、シングルコア、マルチコアSMPからデスクトップグリッドまで、規模もネットワーク構成も大きく異なる多種の計算環境が利用可能であり、これら並列環境の構成方式のトレンドも日々変化している。このような多種多様な環境を、何らかのモデル化によって統一的に扱い、与えられたアルゴリズムが共通にどのような振る舞いを起こすのか、という実行性能予測を可能にするような計算量モデルが求められているのである。そこで、計算コストは通信コストであるという基本理念の元に構築した新しい並列計算量モデル「アクセス計算量モデル」を提案し、その有効性を実証することを試みた。アクセス計算量モデルの提案では、単体計算機内部のメモリ階層から、LAN、インターネットといったグローバルなネットワークを用いた通信までを、統一的にかつ簡潔に表現し、ネットワークトポロジなど並列計算環境の具体的な構造に依存しない、一般性の高い計算モデルを構築しようと考えた。アクセス計算量モデルでは、メモリがある密度で広がる空間を考え、計算はメモリ上の任意の地点で、任意の密度で行えるとする。計算を行うものを計算実体と呼ぶことにするが、これはレジスタなどの記憶を持たず、メモリ上に現在いる「場所」と、プログラム中の実行箇所を示す「プログラムカウンタ」の状態のみを保持している。メモリ空間には何らかの距離の指標が定義されており、計算実体からメモリ上のある地点に存在するデータヘアクセスする際には、その距離に従ったアクセスコストがかかるものとする。計算の過程は、演算に必要なデータを計算実体のある場所まで移動し、そこで演算を行い、演算結果を所定のメモリ位置に通信によって書き込む、という一連の流れで表現される。計算にかかるコストは、この通信にかかる時間コストのみであり、演算にはコストがかからないとする。計算自体は同一点でいくらでも行うことができるが、通信路には容量があり、通信路の混雑によって計算に必要なデータが届かないため、同一点でいくらでも多くの計算を同時に実行できるわけではない。本論文では、このような概念に基づくモデルを提案した。より詳細に、1次元のメモリ空間と、局所的な負荷が表現できる通信路からなるモデルを定め、そのようなモデル上でのプログラムを表現できる仮想機械を定義、設計した。また、よく知られた並列アルゴリズムであるbitonic sort、merge sort、FFTについて解析的に計算量を求め、実計算機上の実行結果を用いた評価を通して、モデルの妥当性と実用性を示した。//(2) バグのない並列プログラムを書くことは、それ自身難しいことである。並列計算環境はマルチコアやマルチプロセッサなどの共有メモリ型からPCクラスタ、ベクトル計算機やデスクトップグリッドまでさまざまな種類があり、それぞれの構成において計算性能を上げやすいプログラミングモデル、通信ライブラリが異なっている。ある環境である問題を並列に解きたいときにどのような計算モデルや通信ライブラリを選択するのか、あるいは複数の手法を組み合わせていかなければならないのか、という決断はプログラマに深い知識と経験を要求する。また、別の計算環境が使えるようになったり、計算機の規模が大きくなったりという変化があったとき、プログラムの変更が必要になるようでは生産性も低く、バグも入りやすい。さまざまな環境で同一のプログラムが正しく動く、というプログラミング手法が求められるのである。さらに、大規模問題を解くためには長期間、多数の計算機を使う必要があるが、長期間同じ計算機を占有し続けられる状況は珍しく、多くの場合は使用可能な計算機が増減する。また、多数の計算機を使うとどこかで故障が発生する確率が高まるため、部分的な故障で計算全体が停止してしまうようなプログラムでは計算が進まない。よって、動的な計算資源の増減への対応、耐故障性の実現などが求められるのであるが、深い知識と多大な労力が必要となるため、プログラマが自分で実現することは難しい。プログラマの負担を減らすための一つの方法に、並列計算フレームワークがある。ある問題領域に適用範囲を絞り、その問題に特有の並列化手法を専門家があらかじめ実装しておくことで、プログラマは並列化手法の詳細について悩むことなく並列プログラムを書くことができる。また、このフレームワークは並列環境の差異を隠蔽し、それぞれの環境で効率のよい実装を使い分けるなどして実装されているため、ひとつのプログラムで、さまざまな環境で効率よく計算することが可能になる。耐故障性の導入なども、問題領域を絞ることでプログラマへの負担を軽減した形で実現できる。科学技術計算などの構造が単純な問題においてはこのようなフレームワークが存在し、高性能計算を簡単なものにしているが、より複雑な構造を持つ問題、例えば組合せ最適化やゲーム木探索などに代表される探索問題については、まだ研究が不十分な点も多い。探索問題は実社会においても応用範囲が広く、規模が大きくなると莫大な計算量を必要とするため、並列計算の技法を用いて実用的な時間でより大きな問題を解けるようにすることが強く求められている。探索問題において特に問題になるのは、共通の部分問題に依存した多くの部分問題が存在する点である。単純に並列化を行うと、これらの共通問題を別々の計算機で重複して計算してしまうため、無駄な計算が増えて探索性能の向上に結びつかない。このような共通部分問題を効率よく発見し、計算結果を再利用しながら並列計算を行うような手法が求められている。そこで、このような性質を持つ探索問題をターゲットとする並列計算フレームワークを設計・構築し、並列プログラム開発のための基盤技術とすることを試みた。提案する並列探索手法は、親タスクが子タスクを再帰的に生成し、子タスクの計算結果を使って親タスクの結果を計算するような構造の問題を対象とし、分散ハッシュ表(DHT)の考え方を用いて部分問題を管理する。対象とする問題領域では、部分問題は共通性が発見できるよう一意にコード化されるので、ハッシュ表を用いて共通部分問題を効率よく発見し、計算結果を再利用しながら探索を進める。DHTは近年研究が盛んであるが、多数の計算機でファイルなどの情報を保持するための手法として捉えられていることが多い。また、DHTの考え方を探索に用いる研究もあったが、分散システムの重要な特性である耐故障性能について考慮したものは存在していなかった。今回の提案では、故障時には失われた部分問題を必要とする親問題が子問題を再実行し、必要な探索途中結果をDHT上に再構成する、という方法で耐故障性を実現する。本論文では、提案する手法が、共通部分問題を含む問題領域において良い探索効率を与えること、故障が発生した際も性能悪化が少ないことを、既存の分散計算手法であるマスタワーカとの比較シミュレーションによって示した。また、提案する手法をフレームワークとして利用できるようにインタフェースを整理し、実装を行い、シンプルな探索問題を用いて評価を行った。このような2つの領域の研究の両方がそろって初めて、現在身近になり、これからさらに普及し続けると考えられる並列計算環境を「活用」することができると考えている。本論文では、新しい並列計算量理論と、共通部分計算を持つ探索問題の大規模耐故障並列化フレームワークの提案を行うことで、並列プログラムをさまざまな環境で効率よく、正しく簡単に実装できるような基盤技術を拡充することができた。

発行年

2006-09-13

日本十進分類法

007

学位名

博士(科学)

学位

doctoral

学位分野

Science(Kagaku)(科学)

学位授与機関

University of Tokyo (東京大学)

研究科・専攻

Graduate School of Frontier Sciences (新領域創成科学研究科)

学位授与年月日

2006-09-13

学位授与番号

乙第16590号

学位記番号

第16590号

UTokyo Repository

Language

インデックスツリー