データ駆動型スケジューリングに基づく大規模並列化の研究

点击翻译按钮获取中文摘要

組み合わせ問題を解くメモ化手法の分散並列化は、メモの効率の良い共有の問題のために、高い台数効果を出しにくい。本研究の最終目的は、1000コア以上のCPUを持つスパコン上でも高い性能を発揮できることを研究代表者が示してきた、データ駆動型ワークスケジューリング手法(DDS)を、理論的および実装的な観点から一般化し、様々なメモ化手法を手軽に大規模並列化できるようなDDSライブラリを開発することであった。この目標達成のために、得られた研究成果は次の通りである。まず、プランニングやパズルといった人工知能における典型的な題材を利用して、DDSのスケーラビリティの限界を実験的に徹底的に調査し、DDSの利点・欠点を明らかにした。これによって、DDSライブラリが構築できた際に、性能を予測することの一助につながることが期待できる。次に、DDSにとって重要な対象並列計算機環境である、クラウド環境において、理論的および実験的な成果が得られた。クラウド環境では、計算機資源量と利用時間に基づいて、利用コストが発生するので、DDSを用いるメモリ・インテンシブな並列アルゴリズムは、計算時間だけでなく、利用コストも少なくする必要がある。しかし、最適な利用コストの計算には、並列アルゴリズムが必要とする計算機資源量が既知である必要があり、DDSを用いるメモリ・インテンシブなアルゴリズムでは、一般にこの前提条件は成り立たない。本研究で開発したアルゴリズムでは、必要な利用コストは、最適利用コストの4倍以内で必ず抑えられることを理論的に示し、さらに前述のプランニングやバイオインフォーマティックスで重要な題材であるシーケンスアライメント問題では、ほぼ最適な利用コストで計算できることを実験的に示した。最後に、産業界から高い需要が期待されるスマートグリッドに利用できる「フロンティア法」の共有メモリ環境における並列化を、DDSの特殊ケースとみなせる方法に基づいて行い、有望な初期結果を得た。