• 並列アルゴリズムとは？
• 研究内容
• 発表論文

私たちは，「一人で処理するには時間のかかる仕事を，複数人で協力する ことによって短時間で処理する」ということをよく行います．これと同じように， 「一台のプロセッサで実行するには時間のかかる計算を，複数のプロセッサで 協力することによって短時間で実行する」という計算が並列計算であり， それを行うためのアルゴリズムが並列アルゴリズムです．

並列アルゴリズムを考えるとき，並列アルゴリズムを実行するための計算機環境 をある程度簡単に捉えた並列計算モデルが必要になります． 並列計算モデルには，PRAM (parallel random access machine), BSP (bulk synchronous parallel), CGM (coarse grained multicomputer), RM (reconfigurable mesh)などがあります． そして，それぞれのモデルに対して効率的な並列アルゴリズムが考えられています． 例えば，n個のデータを比較に頼ってソートする場合， 逐次アルゴリズムではΩ(n log n)時間を要しますが， PRAMではnプロセッサを用いてO(log n)時間で， RMではn2プロセッサを用いてO(1)時間で解くアルゴリズムが既に 提案されています．

このように，並列計算は非常に強力な計算方法なのですが，実際に並列計算を 行うためには，それを実行する並列計算機を用意する必要があります． しかし，上で述べたモデルに近い動きをする並列計算機は， 非常に高価でなかなか用意することができません．しかも，このような 並列計算機では用意できるプロセッサ数には物理的な限界があります． そのため，普通の計算機を普通のネットワークで接続しただけの計算機群を ひとつの並列計算機として利用するクラスタシステムの研究が盛んになって きています．さらに，世界中にはネットワークに接続された無数の計算機が 存在しています．これらをひとつの並列計算機として利用する計算グリッドは， 無限の計算能力をもつシステムとして注目されており，現在最も盛んな並列 分野の研究テーマのひとつとなっています．

本研究室でも，クラスタシステム，計算グリッドを対象とした研究を行っています． とくに，本研究室では，「異種性」に関する考察をメインで行っています． 異種性というのは，システムを構成するプロセッサの計算能力や通信能力に 差があるということです． 例えば，クラスタシステムを作る場合，できるだけ多くの計算機を集めてこようと 思うと新旧いろいろな計算機が混ざってしまいますし，計算グリッドでは 世界中の計算機を利用するので，やはりいろいろな計算機が混ざってしまいます． このように，異種性は非常に重要な特性といえます．本研究室では，このような 異種性をもつクラスタシステム，計算グリッドなどを，まとめて異種並列計算環境 と呼んでいます．

具体的には，次のような研究を行っています．

• 異種並列計算環境における効率的な集合通信操作の設計
集合通信操作とは，プロセッサグループ内でデータをやりとりする操作です． 例えば，ひとつのプロセッサのデータを全プロセッサに配るブロードキャスト， 全プロセッサのデータをひとつのプロセッサに集める収集操作などが挙げら れます．集合通信操作は多くの並列アルゴリズムで基本操作として用いられ ており，集合通信操作を効率的に実行することで並列計算全体を効率的に 実行することができます．本研究室では，さまざまな集合通信操作について， 効率的なアルゴリズムを設計しています．


• 異種並列計算環境における 効率的なタスクスケジューリングアルゴリズムの設計
多くの計算問題は，タスクと呼ばれる小さな計算問題に分割することができます． タスクの集合が与えられたとき，各タスクをどのプロセッサに割り当 ててどのような順番で処理するかを考える問題が，タスクスケジューリングです． 全プロセッサに均等にタスクを割り当てれば良さそうですが，そうでもありません． プロセッサの能力が異なれば，それに応じてタスクを不均等に割り当てる必要が あります．また，多くの場合，タスクの集合は１台の管理プロセッサが保持 しています．その場合は，タスクを各プロセッサに配る時間も考慮する必要が あります．本研究室では，このようにいろいろな場合を想定して，効率的な アルゴリズムを設計しています．