平成年度

学士学位論文題目
多重集約演算のための並列パイプライン処理方式

前田庸亮
指導教員

年

岩田誠

月日

高知工科大学 情報システム工学科

要 旨

題目
多重集約演算のための並列パイプライン処理方式
前田庸亮

複数の集約演算を並列に処理するアルゴリズムとして、、、などのアルゴリズムが提案されている。これらのアルゴリズムはすべてのノードが直接結ばれているモデルを想定すると、より大規模な並列計算機ではこの仮定が成り立たない。そこで本稿では、より拡張性に優れたリング構造向きのノード間通信アルゴリズムを提案し、並列パイプライン化を適用して通信時間の隠蔽による高速化を図る。提案するアルゴリズムは各ノードが、演算とノード間の通信を交互に繰り返し、集約処理を進める。通信は隣接した特定のノード間で行われ、衝突が起こることは無い。
既存のアルゴリズム評価に用いられているコストモデルに最小限の変更を加えて、、、並列パイプライン化適用前及び、適用後の本アルゴリズムを評価したところ、パイプライン化は全ての場合に効果があり、特にノード数が少ない場合に有力であった。次に、通信速度を変化させた場合、ノード間の通信速度が比較的遅い場合に改善の効果が大きかった。さらに、目標としていたノード数が大きい場合はいずれのアルゴリズムよりも高速であるという良好な見通しを得た。

キーワード

データマイニング 集約演算，並列パイプライン，ノード間通信

目次
第章

序論

第章

提案するアルゴリズム
既存のアルゴリズムの問題点
動作説明

第章

並列パイプライン化
並列パイプライン化構成
プロセッサ間通信コストの隠蔽
内部構成及び動作説明

第章

性能評価
コストモデル
並列パイプライン化の効果との比較
上での試作

第章

謝辞
参考文献

結論

図目次
全体のハードウェアブロック図
本アルゴリズムシーケンス図の役割
ノード間通信アルゴリズムの動作のオーバフローのオーバフロー
プロセッサ間通信アルゴリズムシーケンス図
構成へのデータ送信へのデータ送信と前のノードからのデータ受信のオーバフロー
パイプライン化による性能向上率
ノード数が多い場合のパイプライン化による性能向上率
パイプライン化による性能向上率
ノード数が多い時のパイプライン化による性能向上率
本アルゴリズムの性能向上率
本アルゴリズムの性能向上率
本アルゴリズムの性能向上率

表目次
コストモデルのパラメータ
通信速度による隠蔽時間

第章

序論

巨大データベースからの知識獲得を高速に行い、意思決定を支援する技術としてデータマイニングやが注目されている。データマイニングとは、従来のデータベースのように単純な問い合わせに対する答を出力するのみでなく、データ属性間に成立するルールを導出するような、高度な処理を指す。データマイニングやは、大規模データベース中の属性とそれらの間の関係を、さまざまな観点から分析するために、多次元データキューブとして扱っており、典型的なデータキューブの各セルには、総売上高などの集約演算の結果が格納されている。このようなシステムを実現するためには、多くのセルについてそれぞれ集約演算を行う必要がある。特にでは、オンライン性が要求されるため、応答時間が非常に重要な要素となっている。現在、このような多くの集約演算を処理するために、高速ネットワークをもつ非共有型並列計算機上における複数の集約演算に対する並列アルゴリズムが提案されている計算すべき集約演算が。

個ある時、単一集約演算用のアルゴリズムを回繰り返すことで、すべての集約演算を処理できる。しかしながら、同一のデータベース上においては、さまざまな集約演算が同じソースリレーションから計算されるので、複数の集約演算を並列に行うように拡張できる。単一集約演算用のアルゴリズムとして提案されている、２ゴリズム、アルゴリズム

れぞれ、ｍ２アルゴリズム、ｍ、アルアルゴリズムを複数の集約演算用に拡張したものがそアルゴリズム、ｍアルゴリズムである

最初に集約演算における、リレーションに対しての基本操作を示す。

。

リード
ローカルディスクからメモリまたはバッファへデータを読み込む。
ハッシュ
読み込んだデータから、問い合わせで指定される属性のデータを分類する。

集計
ハッシュの結果であるハッシュテーブルを用いて、集約演算を行う。ハッシュテーブルに必要なメモリサイズは、演算の結果得られるグループ数に比例する。仮にグループ数が多く、ハッシュの結果、そのデータが属するグループがメモリからあふれるような場合には、集約演算を行わず、データをメモリ上のパーティションファイルに書き出す。
エクストラプロセス
集計でメモリあふれが生じた場合には、パーティションファイルから逐次、データを読み出して集約演算を行う。これをパーティションファイルの数だけ繰り返す。
エクストラ
メモリがあふれて、パーティションファイルを作成する場合、これが余計な入出力となって、アルゴリズムのパフォーマンスに影響を及ぼす。この余計な入出力をエクストラという。

基本的な集約演算の流れはスリレーションについて

リードからハッシュ集計 である。全ての集約演算のソーを適用する。以上の基本操作を用いて、以下につのアルゴリズムの動作を説明する。
アルゴリズムアルゴリズムではノードはつのフェーズに分けて処理を行う。第一フェーズにおいて、各回のリードに対して、個のハッシュ及び集計を行う。第フェーズでは、各ノードの部分的に得られた結果をさらに集計して最終結果を求める処理を行う。
アルゴリズムは、

アルゴリズムの第フェーズを並列に行うように拡張したものである。

を用いると、個の集約演算に対して、ソースデータを度しか読み込む必要が無いため、読み込みコストは減少する。しかし、必要なメモリ量がゴリズムの倍になり、エクストラアルのコストが増大するなどの問題点が挙げられる。

アルゴリズムアルゴリズムは、度のリードに対して個 の 集 約 演 算 に 対 す る ハッシュを 行 い 、集 計 を 担 当 す る ノ ー ド へ デ ー タ の 送 信 再 配 分 を 行 う。受 信 し た ノ ードは、それぞれのデータに対して集計を行う。
を並列に処理する。

は後者の、個の集約演算を用いて複数の集約演算を並列に実行すると、大きなメモリを必要とするが、基本となるアルゴリズムが、アルゴリズムよりも効 率 的に メ モリ を扱 う こと から 、複 数の 集 約演 算 を処 理す る のに 有利 で ある 。
しかし、個の集約演算を処理するルゴリズムを処理する

ｍ

アルゴリズムのアルゴリズムの通信コストは、単一ア倍大きくなるなどの問題点が挙げられる。

アルゴリズムアルゴリズムは、各ノードが並列にリードしたデータをすべてのノードにブロードキャストし、集計を担当するノード以外は不要なデータを破棄するアルゴリズムである。

アルゴリズムとは、 度のブロードキャストに対して、受信したノードが集約すべきグループならば個の集約演算に対するハッシュと集計を並列に行う。

アルゴリズムのコストはアルゴリズムのコストと同じであるのに対して、他のアルゴリズムは倍となっている。しかし、アルゴリズムはソースリレーションと比べて、少数の集約演算を処理するのには適していないという問題点もある。

本稿では、データベースの巨大化が進んでいる現状を鑑みて、より大規模な並列計算機上で効率よく動作する多重集約演算の並列アルゴリズムを提案し、評価する。

第章では、提案するアルゴリズムの手法、動作説明を行う。

第章では第章で提案したアルゴリズムに並列パイプライン化を適用した時の全体構成及び、利点について詳しく述べる。
第章では、並列パイプライン化の有効性の評価を行った後、アルゴリズムとの性能比較を行い、提案方式の有効性を示す。
第章では、本論文の結論ならびに今後の展望について考察する。

アルゴリズム、

第章

提案するアルゴリズム

既存のアルゴリズムの問題点
文献によると、のつのアルゴリズムについて、ブロードキャストバスをもつハードウェアモデル上で評価したところ、集約演算の対象となるデータ数が大きい時に最も高速にデータを処理するのはアルゴリズムである。しかし、全てのノード間が直接結ばれているようなハードウェアモデルでは、より大規模な超並列計算機は実現不可能である。そこで本章では、基本処理ユニットであるノードを拡張性に優れたリング状の通信路で接続した構造に適した、ノード間通信アルゴリズムを提案する。

動作説明
提案するアルゴリズムの基本的なアイデアは、リング状に接続された多数のノードが演算と通信を交互に繰り返すことにより、システム全体をあたかも巨大なパイプラインとみなして処理を進行させるという点にある。図
バッファ、メモリに示すように、ローカルディスク、プロセッサ、からなる基本処理ユニットをノードと呼ぶ。
各ノードのディスクは、重複しないように分割された初期データを持っており、最終的な集約演算も、各ノードで異なるように割り当てる。これらのデータを並列にハッシュしていくと、各ノード毎に集計すべきデータの種類が異なり、自ノードで集計すべきデータと集計すべきでないデータが発生する。自ノードで集計すべきデータは各ノード毎に処理され、集動作説明

計すべきでないデータは次ノードのバッファへ送信される。本アルゴリズムではノード数に対して、ｍアルゴリズムでは単位時間あたり最大であった通信量が、へと削減できる。

図全体のハードウェアブロック図

次に本アルゴリズムの動作の手順を説明する。図に動作手順をシーケンス図にて記す。
ディスクからバッファにデータを送信する。
バッファからメモリへデータを送信する。
個のデータに対して並列にハッシュを行う。
集約すべきデータは各ノード毎に集約し、集約すべきでないデータに関してはプロセッサから、次ノードのバッファへ送信する。以後、～を繰り返し、ディスクから送信されたデータすべてに関してハッシュを行う。
すべてのデータに対してのハッシュ終了後、個のデータに対して、同時に集計を行う。

動作説明

図

本アルゴリズムシーケンス図

以上のような流れで処理を行うのであるが、解決すべき問題点がまずつ目の問題として、図つ挙げられる。に示すようにバッファは基本的に前のノードからデータを受け取る役割と、メモリへのデータ送信する役割、ディスクからのデータの受信という処理を行わなければいけないが、これらすべてを同時にこなすことは不可能である。前のノードからのデータの受信とメモリへのデータの送信は同時にバッファは処理できる。またディスクからのデータの受信とメモリへのデータ送信も同時に処理を行うことができる。しかし、前のノードからのデータの受信とディスクからのデータの受信は同時に処理することはできない。したがって、次ノードへのデータ送信のタイミングと、ディスクからのデータ送信のタイミングの調整が重要となる。

動作説明

図の役割

まず、ノード間通信のタイミングについて検討する。ノード間の通信はなるべくデータをまとめて通信したほうが通信回数が減り合理的である。しかし、一度に大量のデータを送信することで、バッファのオーバフローがおきやすくなる。そこで、バッファ内部をズに分けた図のような流れの処理を提案する。

図

ノード間通信アルゴリズムの動作

フェー

動作説明

図の動作の流れを下記に記す。

データがディスクからバッファ内部に読み込まれて格納されている。この時、各ノード毎に並列にデータがバッファ内部に読み込まれる。図に分かれており、ディスクからす。図には度のリードでのバッファ内部はフェーズフェーズ分のデータを読み込んだことを表つのノードでの構成図しか図示していないが、ノード数が増えた場合も同様に、どのノードのバッファ内部もフェーズに分けられ、この処理は並列に行われる。

バッファ内部 に読み 込まれ たデー タのう ちフェーズ分 のデー タをメ モリへ 送信し、メモリ内部で並列にハッシュする。この処理は各ノード毎に並列に行われる。

で ハッシュさ れ た デ ー タ は 、自 ノ ー ド で 集 約 す べ き デ ー タ に 関 し て は 自 ノ ードのメモリ内に格納し、そうでないデータに関しては次のノードに送る。この時、並行してメモリ内では、再びバッファ内部からフェーズ分のデータがメモリ内に送信され、ハッシュ処理が行われる。

回 の ディス ク か ら バッファへ の 送 信 に よって 得 ら れ た デ ー タ の ハッシュ処 理 を行い、バッファ内部にフェーズ分の空きができたら再びディスクからバッファへとデータを送信していることを示している。図ではとなっている。空きフェーズがい場合、ディスクからのデータ読み込みは行われない。ノード毎に、～に達しなまでの処理を繰り返すことによってすべてのデータに対するハッシュが完了する。
ノード間通信はフェーズ分のデータをハッシュし、自ノードで処理すべきでないデータはそのつど次のノードへ送信するものとする。送信するタイミングは、各ノードのバッファがメモリへデータ送信を行う間に送信するものとする。
次にディスクから再度新しいデータを送信するタイミングについて検討する。まず、バッファ変数が大きいほど、システム全体の性能は向上する。しかし、本アルゴリズムの実現に必要な高機能を実現するバッファのハードウェアコストは極めて高く、かつ動作説明で増加する。本稿では、アルゴリズムの検討を中心に行うため、ハードウェアの条件が最も悪い状態を想定する。すなわち、ディスクからバッファへ送信するデータ量に対して、 フェーズ分のデータしか格納されていない時に、ディスクからバッファへの読み込みを行うものとする。つまり、ノード間通信により、前のノードから送信されるデータ量は、 回に高々 フェーズ分のデータ量であり、バッファ内部に格納されているデータ量が残り、 フェーズ分になった時にディスクからデータ送信をするので、内部をフェーズに分けるとすると、バッファオーバフローを起こさないためにはフェーズ という式が成り立つ必要があり、第 章でのアルゴリズム評価ではと想定する。

つ目の問題点は、プロセッサ間通信速度と送信するタイミング、ハッシュ処理速度、ディスクからバッファへのデータ送信速度とタイミング、ディスクへのデータ送信速度とタイミングの問題からバッファオーバフローという問題である。本アルゴリズムのバッファでは、ディスクからの送信データ、前のノードからの送信データ、メモリへの送信データを制御し、効率の良い処理を行わせる役割を果たしている。もしあるつのノードのバッファがオーバフローしてしまうと連鎖的に各ノードのバッファがオーバフローしてしまい、動作不可能な状態が生まれてしまう。そこで、図にて示すように、自ノードのバッファがオーバフローを起こしている時は、オーバフローを起こしているバッファ内部のデータを自ノードのディスクへ送信し、バッファ内部に空き容量をつくることでバッファのオーバフローの連鎖を防ぐ。ディスクへの送信はバッファ→メモリ→ディスクの順に行われる。この処理は、プロセッサ時間をかなり消費するが、後に述べる簡単なハッシュ処理プログラムの試作によれ
ば、処理負荷を調整し、適当なバッファの空きを確保することで、バッファのあふれをほとんど避けることができる。このため、今回はソフトウェアによる対策をとるものとする。

動作説明

図のオーバフローつ目の問題としては、ハッシュ処理した結果テーブルのテーブルをメモリ内部にて格納するのだが、メモリの空き領域が足りなくなった時のエクストラエクストラれのが生じるのは、ハッシュテーブルあふれの問題が挙げられる。

パーティションファイルあふ種類がある。この時も、メモリ内のデータ格納領域が一杯になった時点で、メモリに格納されているデータを自ノードのディスクへ格納する。ディスクへの送信は図ように、メモリ→プロセッサ→ディスクの順に行われる。

図のオーバフローに示す

動作説明のエクストラが生じた場合、最終的な集計の時に、すべてのデータに対してのハッシュが終了した後、メモリ内に格納されているハッシュ結果を一度すべてディスクへ送信し、グループ毎に最終的な集計を行う。のエクストラが生じた場合は、一度ディスクに送信し、ディスク中のデータに割りこませて、再びハッシュを行う。

第章

並列パイプライン化

並列パイプライン化構成
データマイニングでは、ソースリレーションや集約演算数が大きくなると入出力にかかる時間がボトルネックになりやすい。この入出力にかかる時間を最小化するために、本アルゴリズムのノード間通信時間を隠蔽するように、並列パイプライン化について検討する。並列パイプライン化した時のハードウェアは、第章で提案したアルゴリズムと同様である。並列パイプライン化の適用前と適用後の違いは、ハードウェア毎の処理及び、各ハードウェア間の通信時間を同一にすることで、各ノード間が並列にパイプライン処理をおこない、入出力にかかる時間を最小化できるところである。また提案したアルゴリズムは、単一通信により全体の構造がリング構造となっているため、他のアルゴリズムと比べると並列パイプライン化の適用が容易である。

プロセッサ間通信コストの隠蔽
本節では、プロセッサ間通信コストの隠蔽について図明する。図に記されているシーケンス図内の矢印はデータの流れを表している。上から順にディスクからバッファへの矢印は図への矢印はおけるに示すシーケンス図を用いて説におけるのリードを、バッファからメモリのデータ送信を表す。 つ目のメモリからプロセッサへの矢印は、図にの処理すべきでないデータを次ノードへ送るための、メモリからプロセッサへのデータ送信を表し、最後のプロセッサからバッファへの矢印はのノード間のデータ送信

プロセッサ間通信コストの隠蔽を表している。
図の、はバッファ内部でのデータをフェーズ毎に分ける処理時間である。

でははプロセッサ間通信時間を表している。

メモリ内部でのハッシュ処理時間を表している。

この図を見ると、並列パイプライン化を適用することで、（ ）のノード間通信部分に重複している、、の時間を隠蔽できることがわかる。したがって、はじめのプロセッサ間通信から最後のハッシュ処理をするまでの、、の部分の隠蔽が可能となる。そこで重要となるのが隠蔽率の最適化である。隠蔽率とは、隠蔽される時間の割合である。例えばの時間がるが、この時、の時間より大きい場合、の時間と、の時間により、の時間との差が小さいほど隠蔽率が高いといえる。パイ

プライン化するにあたって隠蔽率の最適化が重要な要素となる。

図の時間が隠蔽されプロセッサ間通信アルゴリズムシーケンス図

内部構成及び動作説明

内部構成及び動作説明
ここでは、本アルゴリズムの処理の流れで、重要な役割をもたらすバッファ内部の処理説明を行う。図にバッファ構成を示す。

図

構成

まず、バッファの内部構成について説明していく。バッファ本体はフェーズに区分けされており、それぞれのフェーズ毎にデータの有効性を判定するための分のハードウェアフラグが取り付けられているものとする。またバッファ内にデータが格納された順番どおりにメモリへ読み込まれるため、どのフェーズにあるデータが先頭のデータであるかという判別を行う必要性がある。これもフラグ判定部分と同様にハードウェアにて実装するものとし図行う。

ではとして表す。以上のようなハードウェアを用いてバッファ内部の処理を

内部構成及び動作説明

図にバッファの処理の流れを示し、図の流れに沿ってバッファの動作を説明する。

図

ここではまずディスクからへのデータ送信ページ分のデータを読み込み、それらをデータに区分けする流れを記している。まずフェーズ分のフェーズ分の先頭のデータをすべてのフェー内部構成及び動作説明ズに入力する。この時、各フェーズ毎にフラグ判定が行われる。 のフラグがたっている場
合は、そのフェーズには有効なデータが格納されていないということを表し、 のフラグがたっている場合は自データの前に他のデータがあることを表す。しかし、ここで入力されているデータは最初のデータ バッファ内部が空の状態の時 なので、すべてのフラグはなっている。そこでを参照し、そのフェーズ部分のフラグ判定がとである場合、そのフェーズに入力されたデータを先頭データとし、そのフェーズのフラグにをたてる。また、そのフェーズ以外に入力されているデータはすべて削除される。
次に入力されたデータも、にて入力されたフェーズではと同様にまず全フェーズに入力される。この時、のフラグがたっており、それ以外のフェーズではがたっている。そこで、自フェーズのフラグがているフェーズを探し、 のフラグをを削除する。以後こののフラグで、 つ前のフェーズのフラグにがたっにして、 のフラグがたっているフェーズのデータと同様の処理をすることで、 ページ分のデータがバッファ内においてフェーズ単位での区分けが可能となる。

上記の流れでバッファ内にデータを格納していく。次にメモリへデータを出力する時のバッファ内の処理について述べる。図にメモリへのデータ出力の流れを記す。

まずメモリへデータを出力するわけであるが、どのデータを送信するかを述べると、のデータをメモリ内に出力する。出力されたデータが格納されていたフェーズは空となっているため、 のフラグを立てる。または次フェーズに移行される。したがってのデータが順にメモリへ送信されていく。
ここでは、前のノードからの送信データについてのバッファ処理を述べる。前のノードから送信されたデータもと同様に処理されバッファ内に格納される。

内部構成及び動作説明

図

以上のへのデータ送信と前のノードからのデータ受信の流れでバッファの処理は行われる。しかし、この一連の流れはバッファがオーバフローを起こしていない時の流れである。そこでオーバフローが発生した時のバッファ内部の処理を次に記す。図

はバッファのオーバフローが起きた時のバッファ内の状態を示している。
この場合フラグはすべてのフェーズにがたっており、前のノードから送信されてきたデータを格納する場所が無く、バッファはオーバフローを起こし、この状況が連鎖的に各ノードに飛火してしまう。そこで、すべてのフラグにあるデータたっている場合には、バッファ内に部分のデータ を一時的に自ノードのディスクに格納することでバッファ

内部構成及び動作説明内部に空きフェーズを設ける。この時、前のノードはバッファからオーバフローであるという信号を受け取り、一時的に次ノードへの送信をとめておく。バッファ内に空きフェーズができると、前のノードは次ノードへのデータ送信を開始する。また、ディスクに送信されたデータは以後、処理される。以上の流れでオーバフローの問題を解決する。

図のオーバフロー

第章

性能評価

コストモデル文献
対して、のコストモデルパラメータを表に示す。この表では、 つのリレーションに個の集約演算が存在し、各集約演算は個の集約演算を含んでいると仮定している。これらはディスク上に格納されたリレーションに対して直接、働くものとして、事前に各ノードが分配されているものとする。
文献のコストモデルは、ネットワークの調停、、などの重複を含んでおらず、ノード間にブロードキャストバスを持つを対象としている。この結果、本稿で想定するようなデータ量が大きい場合には、が最も高速に動作するという証言がなされている。これに対して、本稿で用いるコストモデルは、ノード間の接続がリングにより行われていると仮定している点が異なるが、他の点は文献のモデル及びパラメータをそのまま用いる。また、すべてのプロセッサが完全に並列に働くものとしている。このような前提条件により単一ノードにおける部分的なフォーマンスを計算することができる。とのコストの合計から全体のパコストモデル

表記号

コストモデルのパラメータ説明

値

リレーションのサイズのタプル数
ノード に分配されたタプル数再配分されたタプルの数
集約演算の数変数

ソースリレーションを読み込む回数

変数

つの集約演算中の集約演算の数
グルーピングセレクティビティ

変数

プロジェクティビティ
ページサイズ
ハッシュテーブルサイズ
ディスクから１ページをバッファに読み込む 書き込む時間
タプルをへ書き込む時間

タプルをへ書き込む時間を計算する時間

集約演算を処理する時間
ノード間でページを送信する時間

ページをブロードキャストする時間（ｍノード数（－変数

結果のタプルサイズ

次に表に表記されているコストモデルパラメータを用いて、ｍアルゴリズムとアルゴリズムと並列パイプライン化適用前と適用後の提案アルゴリズムのトモデルを示す。

つのコスコストモデル

アルゴリズムから通信への読み込みコスト
からタプルを取り込むコストのコスト
集約演算のコストのコスト
結果タプルを生成するコスト
ローカルディスクに格納するコスト
ブロードキャストするコスト

アルゴリズムからへの読み込みコストからセレクトするコスト
するコスト
通信に書き込むコスト

再分配のための送受信コスト
受信したデータを通信から読み込み、集約演算を計算するコスト
コスト
結果タプルを生成するコスト
ローカルディスクに格納するコスト

コストモデル

並列パイプライン化適用前の提案アルゴリズムから通信への読み込みコスト
からタプルを取り込むコストのコスト
ローカルディスクへの格納コスト
結果タプルを生成するコスト
プロセッサ間通信コスト
最終結果をへ格納するコスト

並列パイプライン化適用後の提案アルゴリズムから通信への読み込みコスト
からタプルを取り込むコストのコスト
ローカルディスクへの格納コスト
結果タプルを生成するコスト
プロセッサ間通信コスト
最終結果をへ格納するコスト

注 並列パイプライン化を適用することで、、、、のコストの間で隠蔽が可能となる。

上記の並列パイプライン化適用前と適用後の本アルゴリズムのコストモデルでは 、各 ノ ー ド ご と に デ ー タ が 平 均 的 に 分 か れ て お り

処理では均等に処理されるものと考えてい るので、バッファのオーバフローはお きないものと考え ている。また 、上 記 の 提 案 ア ル ゴ リ ズ ム の コ ス ト モ デ ル は ｍ

ア ル ゴ リ ズ ム と ハ ー ド ウェアの 量 を 同 じ に し て い る た め 、バッファを 追 加 し た 時 の コ ス ト を は 新 た に 発 生 し な い並列パイプライン化の効果ものとしている。以上のことを踏まえて次にｍアルゴリズム、アルゴリズム、並列パイプライン化適用前と適用後の提案アルゴリズムのコストモデルでの評価を行う。

並列パイプライン化の効果
はじめに並列パイプライン化の適用前と、適用後の本アルゴリズムの性能向上率を調べる。性能向上率とは、この場合ノード数の増加に伴う性能の変化を表す。図に並列パイプライン化の適用前と適用後の性能向上率のグラフを示す。このグラフはただしである。また、ノード間の通信速度がと比較的遅い場合である。グラフを見てもわかるように、パイプライン化を適用することで通信時間が隠蔽され、ノード数が少ない時に大きい性能の向上がみられる。また図のグラフは、図のノード数が多い時の部分を拡大したグラフである。このグラフを見ると、並列パイプライン化適応前と適応後の性能の差は、ノード数が少ない時ほど大きくないものの、性能が向上している。

図

パイプライン化による性能向上率

並列パイプライン化の効果

図

次にノード数が多い場合のパイプライン化による性能向上率と通信速度が比較的早い場合にどのようになるのかを調べる。図にの時の並列パイプライン化の適用前と適用後の性能向上率のグラフを示す。図のグラフと比較すると、通信速度が速いので全体的に性能が向上しているのがわかる。また、通信速度が速くなっても通信時間の隠蔽による性能向上率は、比較的遅い時と同じようにノード数が少ない時に性能が向上していることがわかる。また図は図のグラフのノード数が多い時の部分を拡大したグラフであるが、これも通信速度が遅い時と同じように、並列パイプライン化適応前と適応後の性能の差は、ノード数が少ない時ほど大きくないものの、性能が向上している。

並列パイプライン化の効果

図

図

パイプライン化による性能向上率

ノード数が多い時のパイプライン化による性能向上率

との比較

最後に表にがとの時に並列パイプライン化により隠蔽された時間を記す。この表を見てもわかるようにノード間の通信速度が速い場合に比べ、通信速度が遅い場合の方がより隠蔽される時間が多くなる。本節での評価結果から、本アルゴリズムは単一方向にしかノード間通信を行わないため、通信量があまり無くノード数の増加に対しての拡張性に優れている。また、並列パイプライン化を適用することによって更なる性能の向上が可能となるということが言える。また、通信速度が速い場合より、比較的遅い場合に隠蔽率が高くなることから、本アルゴリズムは通信速度が比較的遅い場合に適していることもわかった。

ノード数の時の隠蔽時間

表の時の隠蔽時間

通信速度による隠蔽時間との比較
前節にて並列パイプライン化の有効性がわかった。そこで次に、並列パイプライン化を適用した本アルゴリズム、アルゴリズム、ｍアルゴリズムとの性能向上率の比較をとの比較に本方式と行う。図及びのグラフを示す。また、がとのの時の性能向上率と比較的遅い場合を判定する。このグラフから、、に比べて本アルゴリズムがノード数の増加に対しての拡張性がどのくらい優れているかが見てとれる。ノード数が ～ の時、にアルゴリズムが最も性能が優れており、順、本アルゴリズムになっている。しかしノード数を増加させると、まずノード数がの時にリズムととの性能が入れ替わり、さらにノード数を増やすことで、本アルゴとではノード数が以上の時に、とではノード数が以上の時にそれぞれ本アルゴリズムのほうが性能が優れていることがわかる。

図次に本アルゴリズムの性能向上率、の時、図まず図と 通 信 速 度 を 速 く し た 場 合 の 性 能 を 評 価 す る 。図にの通信速度がにの時のグラフをそれぞれ示す。の時のグラフから、ノード数が ～リズムが最も性能が優れており、順に数が増加させると、まずノード数がの時、アルゴ、本アルゴリズムになっている。しかしノードの時にノード数を増やすことで、本アルゴリズムととの性能が入れ替わり、さらにとの比較ではノード数が以上の時

との比較に、との比較ではノード数が以上の時にそれぞれ本アルゴリズムのほうが性能が優れていることがわかる。

図

さらに、図
時、本アルゴリズムの性能向上率の通信速度がの時のグラフを見てみると、ノード数が ～アルゴリズムが最も性能が優れており、順にる。しかしノード数が増加させると、まずノード数が、本アルゴリズムになっていの時に入れ替わり、さらにノード数を増やすことで、本アルゴリズムと以上の時に、とではノード数が性能が優れていることがわかる。のとの性能がとではノード数が以上の時にそれぞれ本アルゴリズムのほうが上での試作

図本アルゴリズムの性能向上率

これら、 つのグラフから共通していえることは、ノード数の増加に対して、は性能が格段に落ちているのに対して、本アルゴリズムはノード数の増加に対して性能の減退が非常に少ないことが言える。なぜこのような結果になっているかを考察すると、では回の通信量が、ノード数に対してとなるためノード数に対する、拡張性が少なく、大規模な並列計算機としては向いていないためである。
信量がに関しては、 回の通よりは少なく本アルゴリズムと同様であるが、通信経路はになるため、ノード数の増加に対して、その分のコストと同様にでが増大し性能が減退する。

それらに比べ本アルゴリズムは、通信経路が単一方向にしかなく、一回の通信量が各ノード毎に単一方向に回と少ないためノード数の増加に対して、で性能が減退し最終的にほぼ一定の性能を得る。

上での試作
実際の環境でメモリ内でのハッシュ処理の並列パイプライン化を検証するため、現在、寺田、岩田研究室で開発している、同時並行処理性、パイプライン並列性を活かした細粒上での試作度の並列処理を得意とする自己タイミング型パイプラインを持つ、データ駆動プロセッサを対象に、単一プロセッサ用のハッシュ処理プログラムを作成し、シミュレーションを行った。その結果、レスポンスタイムはプットはグツールである

サイクル、スルーと処理速度はあまり速くは無かったが、新型プログラミンを用いることで、現在の約 ～ 倍の性能が得られる見通しを得た。

また、今回作成したハッシュ処理プログラムを実行したところ、出力される全てのデータの間隔が均一であったため、処理の負荷を考慮したプログラミングにより、バッファのオーバフローは起こりにくくできることが裏付けられた。

第章

結論

本稿では、多重集約演算の並列処理に関して、拡張性に優れたリング構造向きのノード間通信アルゴリズムを提案し、さらに並列パイプライン化を適用することで通信時間の隠蔽を可能とする方式を提案した。
第章では、既存のアルゴリズムの問題点を述べ、提案するアルゴリズムについての構成及び、動作手順について説明した後、本アルゴリズムを実装するにあたっての問題点となるバッファのオーバフロー、メモリのオーバフロー、ノード間通信のタイミングについての詳細説明とその解決策を提案した。
第章では、提案するアルゴリズムの通信時間を隠蔽するため 並列パイプライン化を提案した。まず、並列パイプライン化適用前と適用後の違いについて述べ、全体の処理時間の中で、隠蔽される部分をシーケンス図を用いて述べ、最後に本アルゴリズムの特徴である拡張されたバッファの構成及び、処理について詳しく述べた。
第章では、リング構造を対象とするコストモデルを考案し、並列パイプライン化適用前と適用後の本アルゴリズム、の、ノード数が増加した時により有利となるつのアルゴリズムに対する性能評価を行った。まず並列パイプライン化の有効性を考察するため並列パイプライン化適用前と適用後の本アルゴリズムについて評価したところ、全体的に処理速度が向上することがわかると同時に、比較的ノード数が少ない時に有効であるという結果も得られた。次に、通信速度を変化させた場合、ノード間通信時間が比較的遅い場合に改善の効果が大きかった。さらに、リズムとの性能比較を行った結果、、、並列パイプライン化した本アルゴあるいはが最も速くなる場合もあるが、目標としていたノード数が大きい場合はいずれのアルゴリズムよりも並列パイプライン化した

本アルゴリズムが高速であった。最後にハッシュプログラムを作成し、本アルゴリズムの動作を確認した。
今後の課題としては、今回行っていないシステム全体のシミュレーションを行い、個々のハードウェアに対して最適化を行うことで実用的なものにする。

謝辞
本研究において、懇切なる御指導、御鞭撻を賜った岩田 誠助教授、大森 洋一助手に心より感謝の意を表します。
日頃から御支援、適切な御指導を頂いた細美 俊彦氏に感謝の意を表します。
日頃から御支援を頂いた情報システム工学科岩田研究室の方々、森川 大智氏、橋本 正和氏、森安 亮氏、古家 俊之氏、別役 宣奉氏、假屋 文彦氏に感謝の意を表します。

参考文献
松澤 福田“ 複数の集約演算のための並列アルゴリズム ” 信学論“”福田 森本 森下 徳山“ データマイニングの最新動向 ” 情報処理学会誌“

前田 大森 岩田“ 複数の集約演算に対する並列パイプライン化 ”