--- 超並列NEC研究室 ---

問題に応じて柔軟に構造を変更できる適応型超並列システムの研究

梶原 信樹

(日本電気株式会社 C&C研究所）

　超並列NEC研究室では、問題に応じて柔軟に構造を変更し、問題の持つ並列性を最大限に引き出し高速に実行できる、適応型超並列システムの開発を目標に、アーキテクチャ、プログラミング手法、応用の3つのテーマで研究を進めています。

　現在の計算機は、比較的単純で機能が固定したハードウェア(CPU)の上にソフトウェアにより論理を積み上げ、複雑で大規模なシステムを構築しています。しかし、CPUの提供する論理的な機能は固定されているので、問題によっては、効率良く実行ができない場合があります。問題に応じてその機能を変更できるアーキテクチャがあれば、より効率的な実行が可能となります。また、問題の持つ並列性を、細かな粒度から大きな粒度まで引き出すことができ、データ並列からパイプラインという多様な並列処理のパラダイムも、問題の構造に合わせて最適に実現し高速に実行することができます。

　近年、FPGA(Field Programmable Gate Array)、PLD(Programmable Logic Device)と呼ばれる新しいタイプのデバイスが発展してきています。もともとは、少量生産される装置の論理回路を、安価に素早く開発するために開発されたデバイスですが、その柔軟性ゆえに、論理回路だけでなく、プログラム、アルゴリズムをそのまま展開して高速に実行しようとする試みも行われており、速度、集積度の向上とともに応用が広がっています。

　しかし、FPGAは、そのままで適応型超並列システムとして使うには幾つかの問題点を持っています。

　1つは、大規模なプログラム、アルゴリズムをマッピングするには機能が低いということです。例えば、FPGAでALUを合成しようとすると、最新の高速CPUに比べると10倍くらい遅くなります。また、合成に必要なゲートも大量に消費してしまい、問題の並列性を引き出すのに必要な数のALUを充分に提供できないという問題があります。

　もう1つの問題点は、大規模データの扱いです。大規模なデータを扱うためには、一般的にはFPGAの外部にメモリを設けます。外部メモリへのアクセスがあると、そこで従来のCPUと同じ、ノイマンボトルネックに遭遇してしまいます。

　このため、我々の研究室では、適応型超並列システムとして図1に示すSOP(Sea Of Processors)アーキテクチャを提案し、プログラムをマップするのに適した論理素子、記憶素子、接続素子の設計を行っています。論理素子は、ALUも効率的に合成出来るように、1ビットの全加算器を基本素子とするアーキテクチャを検討しています。記憶素子としては、連想メモリをベースとし、SIMD的な並列処理や最大値、最小値の検索、リスト操作を行うことのできるものを検討しています。

図１ SOPアーキテクチャ

　SOPアーキテクチャでは、アルゴリズムを逐次的に実行するのではなく、直接ハードウェアにマッピングしようとするため、マッピングの技術が非常に重要です。C言語に準拠する記述から、プログラムのデータ依存、制御依存関係を抽出し、アルゴリズムの持つ並列性を最大限引き出すことを目標に、コンパイラの開発を進めています。

　第0バージョンとして、C言語の基本的な制御構造だけをサポートし、配列と複雑なデータ構造を除いた記述からXNFフォーマット(ザイリンクス社のFPGA用のネットリスト・フォーマット)を出力するコンパイラを試作しました。コンパイラは、ソースコードを解析し、制御/データフローに従って関数呼び出し、演算（四則演算、等）をハードウエアに展開し、図2に示すようなゲートレベルのネットリストを生成します。この方法により、データフローマシンと同様に問題の持つ並列性を容易に引き出すことができます。また、制御/データフローはハードに直接マッピングされるため、データフローマシンにおけるパケット生成が不要で、より効率的な実行が可能です。より多くの並列性を引き出すため、新しく変数間の依存関係の解析手法も開発しました。

　SOPアーキテクチャの有効性を確認するために、多くの並列性を内在する応用問題の研究も行っています。TOYプログラムではなく、それ自体でも意味のある応用問題として、遺伝子情報処理の研究を行っています。隠れマルコフモデル(HMM: Hidden MarkovModel)という確率的モデルを用い、蛋白質のアミノ酸配列から、モチーフと呼ばれる重要な特徴を抽出する手法を開発し、高い抽出精度を達成しました。現在は、ここで用いたHMMアルゴリズムのFPGAへのマッピングを行っています。疎行列をリストベクトルで表現し、かつ効率的にパイプライン処理することにより、ザイリンクス社FPGAでRISC CPU R4400(150MHz) の約10倍の処理速度が可能となります。実応用をマッピングすることによりFPGAの問題点を洗い出し、SOPアーキテクチャへ反映させています。

図２ 関数呼び出し・演算マッピング例

　今後、実応用をマッピングしながら、SOPアーキテクチャの各機能素子の詳細化を行い、RWC後期にはチップ化を目指します。また、コンパイラは配列、構造体等のデータ構造の記述や、ユーザがスレッドレベルの並列性を記述できるように拡張を行い、アルゴリズムの持つ並列性を最大限抽出し、SOPアーキテクチャにマッピングできる開発環境を目指します。