No | 114932 | |
著者(漢字) | 田中,清史 | |
著者(英字) | Tanaka,Kiyofumi | |
著者(カナ) | タナカ,キヨフミ | |
標題(和) | 軽量ハードウェアによる分散共有メモリの研究 | |
標題(洋) | Study on Distributed Shared Memory Managed by Lightweight Hardware | |
報告番号 | 114932 | |
報告番号 | 甲14932 | |
学位授与日 | 2000.03.29 | |
学位種別 | 課程博士 | |
学位種類 | 博士(理学) | |
学位記番号 | 博理第3696号 | |
研究科 | 理学系研究科 | |
専攻 | 情報科学専攻 | |
論文審査委員 | ||
内容要旨 | 計算機における逐次処理の性能向上が飽和の兆候を見せ始め、それに置き換わるものとして並列計算機、更には超並列計算機に対する要求が高まりつつある。並列/分散システムにおいて汎用性を維持し、容易なプログラミング環境を提供するためには共有メモリが有効である。その際、遠隔データ参照が実行性能を落とすのを避けるために共有データをキャッシュすることが求められる。キャッシュ方式を採用することはコンシステンシ維持管理が必要であることを意味する。分散共有メモリ(DSM)は、集中共有メモリ(SMP)が実現可能な規模を越えた共有メモリシステムを構築する場合の有力な方式である。DSMの実現方式は、ハードウェア、ソフトウェアによるアプローチともすでに多数提案されてきた。DSMを実現するためには、要素プロセッサの持つキャッシュメモリへのデータコピーの生成、キャッシュミス/ヒットおよび共有の有無等キャッシュされたブロックの状態の判定および判定結果に基づくコヒーレンス管理、特に書き込み時のコヒーレンス維持操作の実現が必要である。 DSM実現方式には大きく分けて、ソフトウェアによるもの、一部ハードウェアによるもの、ハードウェアによるものがある。ソフトウェア方式では、要素プロセッサにおけるソフトウェア実行によりDSMを実現するアプローチをとる。すなわち、要素プロセッサがデータコピー(キャッシュ)の生成、キャッシュミス/ヒットの判定およびコヒーレンス管理や通信起動を実現するものである。複雑なハードウェアサポートが要求されないことに利点があるが、要素プロセッサを時分割でキャッシュ管理に使用するため、ソフトウェアオーバヘッドが大きい。 第二の実現方式は仮想共有メモリであり、プロセッサが持つページ管理機構、すなわちプロセッサ内のTLBを含むMMUを使用し、ページフォルトトラップの発生時にソフトウェアにより遠隔メモリアクセスとコヒーレンス維持操作を起動する。キャッシュヒット時の読み出しはオーバヘッドがないが、共有されているデータへの書き込み時にはコンシステンシをとるためのソフトウェアオーバヘッドが存在する。また、データ転送/管理単位が基本的にページ単位の大きさであるためfalse sharingによりネットワーク性能が無駄に使用され性能が低下する可能性が大きい。一般的に、ソフトウェアが介在するDSM方式では、ソフトウェアオーバヘッドだけでなく通信網の低い性能が大きなボトルネックになる傾向があるので、通信量を減らす最適化が必須である。 第三の方式であるハードウェア方式では、プロセッシングノードにDSM管理を行う専用ハードウェアを用意することにより、要素プロセッサでのソフトウェアオーバヘッドを削減することが可能である。この方法は、プロセッサと通信/DSM管理ハードウェアが並行に実行することにより、高いパフォーマンスを達成する可能性がある。しかし、ソフトウェアによる方法が特別なハードウェアを必要とせず、市販のPCやワークステーションクラスタ上で実現可能であるのに対し、DSM実現のために付加するハードウェアのコストを考慮しなければならない。ソフトウェア分散共有メモリにおいて、緩和されたコンシステンシモデルや通信最適化コンパイラの利用により実行性能が向上してきているが、それに対してハードウェアによるシステムがコストに見合う性能向上を得られなければその存在意義がなくなる。 本論文では低いコストかつ軽い制御で効率の良いハードウェアDSMシステムを構築する方式を目標とする。ハードウェアDSMシステムの構築には、低コストで短期間に実現可能な方式を求めることが課題である。以下の条件を達成することにより、軽いハードウェアによるDSMを実現する。 1.メモリ使用量が小さいディレクトリ構成 2.ディレクトリ,タグおよび状態を格納する専用メモリの除去 3.専用プロトコルプロセッサの除去 大規模システムにおいて、現存するfullmapディレクトリなどの、プロセッサ台数に比例したサイズのディレクトリ方式を使用するのは困難である。共有情報を不完全に持つことにより、サイズを縮小し、かつアクセスレイテンシが低く、ソフトウェア実行やブロードキャストを必要としない方式を求めることが必要である。 ハードウェアDSMにおいて、最もコストを上昇させる要因はディレクトリ、タグおよび状態を格納する専用SRAMの使用である。高速メモリの使用による性能改善は、プログラム中の共有変数アクセスの出現およびキャッシュミスの頻度に左右される。それらの頻度が小さければ、高価なSRAMを大容量用意することはコストパフォーマンスの障害となる。 現存するDSMシステムに見られるプロトコルプロセッサの使用は、複雑なコンシステンシプロトコルを実現する場合に有効であるが、SMPシステムではすべてハードウェアで実現されるメモリ制御に対し、プロセスの起動、命令実行を介在させるために大きなオーバヘッドを引き起こす。プロトコルプロセッサのコストは要素プロセッサに匹敵、あるいはそれ以上になる可能性があり、また、構造が複雑であるために長い開発期間を要する。並列計算機で市販のプロセッサを使用する場合には、プロトコルプロセッサをはじめ他のシステム構成要素の設計がプロセッサの外部インタフェースに大きく依存する。プロセッサの高速化および世代交替が急速であることを考慮すると、システムの開発期間が長くなることはコスト上昇に匹敵する障害となる。したがってコストパフォーマンスの観点からプロトコルプロセッサを軽いハードウェア制御に置き換える方法を確立することが重要である。 本論文では、上記の要因を排除した軽いハードウェアによる分散共有メモリ方式を提案する。提案する方式におけるディレクトリ方式である階層最大共有距離ディレクトリ(Hierarchical Coarse Directory)は、共有するプロセッサへの距離を用いることによりスケーラブルな構成を実現するものである。そのサイズはプロセッサ数をNとした場合、loglogNであり、現存するいかなるディレクトリ方式よりも小さいメモリ使用量を達成する。また、ディレクトリ、タグおよび状態を主記憶内に格納することにより、分離した高速なSRAM要素の使用によるコストの上昇を避ける。また専用プロトコルプロセッサを使用しないことによってプログラム実行の介在しない低オーバヘッドの制御および低コスト化を実現する。ただし、提案する方式ではディレクトリ情報を簡素化し、プロトコルプロセッサを省略する代償としてコンシステンシ維持管理に必要なネットワーク通信量が増大するが、ネットワークによる動的な階層マルチキャストおよびコンバイニング機構の利用により通信の増加を補い、効率の良い共有メモリを実現する。本方式は基本的な分散メモリ型並列計算機に対して、メモリコントローラとネットワークのスイッチングノード内に少量の論理回路を付加することによってCC-NUMA(Cache Coherent Non-Uniform Memory Access)の実現を可能とする。 軽量ハードウェアによる分散共有メモリおよび通信メッセージのコンバイニングを並列計算機プロトタイプ上に実装した。実際のプログラムを使用して評価を行った結果、通信メッセージのコンバイニングにより、行列の冪乗計算において8台実行時に最大7.7%の性能向上を得た。またSPLASH-2のLU-Contigプログラムを実行した結果、本分散共有メモリ方式の使用により8台の実行が1台の実行に対して81%実行時間を短縮した(表1)。このことから、簡略化されたプロトコル管理方式にコンバイニングを組み合わせる方式が並列化の効果を得ることが示された。また、大規模システムをターゲットとした考察を行なった。従来のfullmapディレクトリ方式と比較し、本DSMで用いた階層最大共有距離ディレクトリ方式とマルチキャストおよびコンバイニングの組み合わせは、共有数が大きい場合に高速なコヒーレンス処理が可能なことが示された。本方式は将来の大規模並列計算機上におけるハードウェアDSMとして有力な方式であることが示された。 | |
審査要旨 | 本論文は9章から成り、第一章は分散共有メモリの実現に関する導入を行い、第二章は、分散共有メモリにおいて、キャッシュコピーの実在場所を指定する小規模で新しいディレクトリ方式およびその管理方法の提案を行い、第三章は効率の良い処理を行うための結合網における通信メッセージに対するマルチキャスト/コンバイニングの方法を述べている。第四章は提案する方式を実際のキャッシュ管理に適用する例を述べ、第五章で、実際にプロトタイプ並列計算機上に実装した方法を述べている。第六章ではプロトタイプ並列計算機上において実際のプログラムの実行を行ったことから、その性能評価を行っている。第七章は、提案する方式を大規模な並列システムに適用した場合の考察を、既存の方式と比較することにより行っている。第八章でハードウェアによる分散共有メモリおよび通信メッセージの削減技法に関する関連研究を述べ、第九章が結論である。 本論文で提案されているディレクトリ方式であるhierarchical coarse directoryは、結合網内の階層情報を利用し、プロセッサ間の階層距離を用いることにより、プロセッサ数nの並列システムの場合でメモリ使用量をlog log nとしている。この量は既存のいかなるディレクトリ方式よりも小さいことが特徴である。また、ディレクトリの値を簡素な回路で生成可能であることが述べられており、ソフトウェア方式よりも高速であることが示されている。更に、キャッシュの共有情報であるディレクトリ、タグ、状態情報を専用メモリではなく主記憶に格納する方式が検討されている。実際のプログラムを使用し、それらにおいて共有変数アクセスの頻度を調べ、この主記憶に格納する方式がプログラム実行においてコストパフォーマンスに優れていることが示されている。 本論文の第三章において、既存の方式を拡張することによって、generalized combiningを提案している。この方式は従来の通信メッセージに対するコンバイニング技法と比較し、大幅に小規模なハードウェアによって実現可能であり、かつコンバイニングの成功率を高めることが可能であることが評価される。従来は、結合網のスイッチ回路内に専用のメッセージキューを用意することが必要であったが、これを単純なメモリベース演算に置き換えることにより、低コスト/効率化を実現している。 提案された方式は、実際にプロトタイプ並列計算機上に実装されている。プロトタイプ計算機のプリント基盤およびFPGA内のロジックの全ては、論文提出者である田中が設計/実装したものであり、実際に安定して動作している。実装方法および実現の際のハードウェア量に関して第五章で示されており、軽量ハードウェアであることが数値を伴って示されている。本プロトタイプ計算機の性能評価において、まず基本通信性能において、実際の並列計算機として十分高速な通信が達成されていることが示されている。また、行列のべき乗計算において、generalized combiningを使用することにより、計算時間が7.7パーセント短縮されていることから、コンバイニング技法の可能性が示されている。更にSPLASH-2ベンチマークのLU分解プログラムの実行において、本論文で提案された軽量ハードウェアによる分散共有メモリ機構がプロトタイプ上で十分な台数効果を達成することが示されている。以上において、実際に設計/実装し、性能測定を行うことにより、提案された方式が実際に実現可能であり、効率の良い実行を支援することが明らかになった。 提案する方式であるhierarchical coarse directoryとマルチキャスト/コンバイニングの組み合わせによるキャッシュ管理が、大規模システムにおいて適用された場合の考察が第七章で述べられているが、プロトタイプの設計/実装で得られた各構成要素上での所要時間を用いることにより正確な評価が行われている。二種類の形状かつ二種類のデータ転送幅の結合網をターゲットとし、既存のfullmapディレクトリ方式と比較した結果、データコピーの数が10を超えた場合にはいずれも、提案方式が大幅に高速にキャッシュの一貫性維持操作を行うことが可能であることが示されている。また、コピー数が少ないときにfullmap方式よりも処理が遅い場合があるが、最大で1.6倍程度であり、ディレクトリ情報が不完全であることの代償は大きくないことが示されている。 本論文は、小規模ディレクトリと軽量ハードウェアロジックによるキャッシュ管理を、結合網によるマルチキャストおよびコンバイニングと組み合わせることにより、効率の良い分散共有メモリ機構が実現可能であることを実証しており、これにより、将来の分散共有メモリ並列計算機を低コストで実現する道が大きく開かれたと結論できる。また、本論文の三章は平木、松本との共同研究であるが、田中が主体となって提案および実装を行っており、論文提出者の寄与が十分であると判断する。これらの点において本論文は高く評価され、審査員全員で博士(理学)の学位を授与するに値すると判断した。 | |
UTokyo Repositoryリンク | http://hdl.handle.net/2261/54755 |