| 内容要旨 | | 1研究の目的 大規模共有メモリ型並列計算機においてスケーラブルな性能向上を得ようとする場合,プロセッサとメモリ実体の間の通信路が長いことで生じるアクセス遅延の影響が問題となる.これを克服する方式として,複数の交替の仕事(スレッド)を予めプロセッサ内部に用意しておき,それを細かい時間間隔で切替えることで,メモリ応答を待つ時間を有効利用し遅延を許容する「多重スレッド方式」が知られている. この方式が有効に機能するには,遅延の許容に十分な数のスレッドの情報をプロセッサ内に保持し,それに割付けられる有効な仕事を供給することが重要である.また,レジスタなどスレッド情報を保存するための資源にも限りがあるので,少ないスレッド数で高い遅延許容能力を発揮できる切替え方式の研究が注目されている.本論文は,この多重スレッド方式における種々の切替え方式を採用した並列機について,その性能を評価することを目的とした. 2スレッド方式の切替え方式 対象とする多重スレッド方式並列機には,交替の仕事の単位をはスレッド(命令流)として,スレッドの情報を保持するプログラム・カウンタやレジスタ・セットを複数搭載し,演算機構,メモリ・インタフェース(ノン・ブロック方式)を共有するプロセッサを想定している. Bootheらによる切替え方式の分類と特徴の考察にあるように,ハードウェア機構で起動される切替え方式は,クロック・サイクル毎方式と何らかのイベントを契機とする方式に大別される.初期のHEPシステムで採用された素朴な切替え方式である「サイクル毎切替え」方式では,パイプラインの各段の依存を避けるため,別のスレッドに属する相互に関係の無い命令を各時点で投入するようにしている.本論文では,まず,処理されるスレッドの順序が予め決定できる,巡回パイプラインを忠実に展開した構成の「固定順」方式について評価を行った.つぎに,キャッシュを搭載した構成を想定し,遅延の変動に対応するようスレッドの追越しを許した「応答順」方式について評価を行った. さらに,イベントで切替える方式として,Alewifeシステム等で採用された,大部分がキャッシュ・ヒットする状況では必要スレッド数が少ない利点を持つ「ミスを契機に切替える方式」について評価を行った.なお最近の研究には,サイクル毎の切替えでも依存を部分的に許すようにしたLaudonの提案する方式などがある. 2.1サイクル毎固定順切替え 「固定順」方式は実現容易であり,パイプラインには相互依存のない命令を投入する方式であるが,各スレッドは切替の周期に一度しか実行されず,一つのスレッドに着目すると処理速度が遅いという欠点も持っている.この方式に関しては,簡単な機構でどれだけの性能が得られるのかを明らかにすることが重要である. 我々は,命令レベル・シミュレータを用い,対象としてSPARCをベースとした多重スレッド方式プロセッサと多段結合ネットワークからなる構成を想定し,グラフ探索問題の処理時間をもとに性能評価を行なった. その結果,スレッド数を大部分の遅延に間合うようにとれば,ほぼ遅延の影響を除けることが判明した.スレッド数の少ない領域では,スレッド数と性能の関係に特徴的な階段状の関係が見られるが,その性質を含めて,問題の直列部分の比とメモリ遅延特性のモデルから性能が予測できることを明らかにした. スレッド数を適切に取った構成については,性能を遅延の無い構成と比較する実験を問題の規模を変えて行った.その結果から,この方式での台数効果は問題の並列度に主に支配されることが明らかになった. 2.2サイクル毎応答順切替え 前に述べた「固定順」方式では,スレッドの追越しを許さないことで制御を簡単にしていた.しかし,スレッド数と性能は階段状の関係を持ち,必要なスレッド数はシステム構成で定まる遅延と密接に関連するため,異なる構成のシステムで共通に利用できる部品とはできない欠点があった.また,キャッシュを搭載した構成では,ヒットした場合とそうでない場合で遅延が大きく異なるため,どのアクセスもほぼ同じ遅延であると想定している固定順方式には不適切である. 我々はその改良型として,スレッド管理に追越しを許す「応答順」切替え方式を提案した.これは,メモリ応答の得られた順にスレッドを処理することで,短い遅延で生じた遅延許容の余力を長い遅延のために回せる方式であると考えられる. スレッドの追越しを許すことでどの程度の性能改善が出来るかについて,同じようにシミュレーション評価を行った.その結果,遅延と必要スレッド数の強い依存が回避できることが明らかになった.また,両方式の性能差の考察から,この方式は従来のメモリ応答受取り失敗によるロスを救うことができ,少ないスレッド数で効率よい処理のできることが明らかになった. 2.3ミスを契機とする切替え 近年では,依存のある命令をパイプラインに投入すること許して必要なスレッド数を減らす「ミスを契機とする切替え方式」がさかんに研究されている.各切替え方式の比較を行うためには,稼働率をミス率等のシステム・パラメータから計算し,スレッド数と遅延許容力の関係を調べるツールが重要である.このための性能評価モデルとして,Weberらのシミュレーションによる各パラメータと性能の関係の研究,Agarwalによるメモリなどを細かく規定した上での解析的モデルの試み,Saavedra-Barreraによる多くの状態を用いるマルコフ過程を用いた解析などがされていた. 我々は,ミスが無相関に起きると仮定し,プロセッサ内の処理可能スレッド数のみによって状態を分け,その間の遷移確率から稼働率を計算するモデルを提案した.このモデルは,状態を簡略化してあるが実際の性能をよく近似でき,性能評価に有効な手段であることを明らかにした. 遅延の許容に必要なスレッド数を見積もる場合に,楽観的な状況想定として「むらなくミスが起こる」と仮定すると,メモリ応答を待っているスレッド数とメモリ要求を発行可能なスレッド数がバランスして,少ないスレッド数で足りると考えられる.モデルの挙動から,一般の状況はかなり楽観的モデルに近いこと,また,スレッド切替えコストが性能向上に大きく影響することも明らかになった. 3問題の並列度変化への対応 問題の持つ並列度(スレッドに割付け可能な仕事の数)は処理の進行に従って変化する.いっぽう並列機の持つ並列度(総スレッド数)は「プロセッサ数×スレッド数」で決まっている.両者の均衡を図り,多重スレッド方式の性能をより高める方式についての研究を行った. 3.1スレッド数の動的管理 Thekkathらによって,あるスレッドによるアクセスの副作用により他のスレッドの必要とするキャッシュ内容が取り込まれたり追い出されたりする「スレッド干渉」の挙動の研究と,その効果を意識したスレッド配置を用いて性能向上を図る研究がされている.まず我々は,実行可能スレッドが多い場合のキャッシュ干渉と多重スレッド方式のモデルから,実行時にスレッド数を変化させて稼働率を高める「スレッド数の動的管理方式」を提案した.これは, Markatosらによる,通常のプロセッサを対象にキャッシュに残ったデータを意識したプロセス割付けを行って性能向上を図る方式(Affinity方式と呼ばれる)とも似ている. プログラムの実行中に得られる指標としてヒット率や実行可能スレッド数を用い,総スレッド数の増減を行なう方式を提案した.ミスを契機にスレッド増減を行なう機構を組込んだアドレス・トレースによるモデル評価より,いたずらにスレッドを切替えるよりも,敢えてアイドルを増やしても稼働率が上がるケースのあることを明らかにした. CullerによるTAMではコンパイラによって積極的にスレッドをスケジュールしているが,我々は,増減の管理をスケジュール機構に組込んだスレッド管理方式を提案した.その方式の効果を,命令レベル・シミュレータを用いてプログラムの実行時間により評価した結果,スレッド数固定よりも高い性能が得られることを明らかにした. 3.2スレッド機構の先読みへの利用 つぎに,問題の並列度が低く起動可能スレッドの少ない状況での改善を試みた. Bianchiniらにより,キャッシュ・ミスで起動される先読み方式(Cache-Miss-Ini-tiated prefetching)が提案されている.これは通常タイプのプロセッサを対象に,キャッシュ・ミスが起きた時に,過去のアクセス傾向の記録やコンパイラのから得たヒントを利用して,次のアクセス位置をハードウェア機構の助けを得て予想し,そのデータをプリフェッチするものである. 我々は,空きスレッドを次のアクセスを予想する機構として利用することを考え,スレッド機構を用いてプログラムの流れを先行して追跡し,将來アクセスされることが確実なデータの先読みを行う「スレッド機構を先読みへ利用する方式」を提案した. これを実現するためのプロセッサとキャッシュ機構について検討し,多重スレッド方式のためのメモリ書込みをnon blockingで行なうライト・スルー方式を基本としてそれぞれの動作を規定し,少量の管理機構の追加で比較的容易に実現できることを示した. モデルと,統計的アクセス系列生成によるシミュレーションから,先読み方式の効果について評価を行った.その結果,実行可能な通常スレッドの少ないとき,データ参照が多いとき,遅延が大きいとき,コードのヒント率が高く流れが追えるとき,スレッド切替えコストが小さく先読みモードの継続が期待できるとき等の場合に,先読みスレッドの働きがいがあり,有意な性能向上が得られることが明らかになった. また,コード・ミスや条件分岐などに出合うことでプログラムの流れの追跡が中断する場合に特に性能が低下するという欠点があることや,本方式は一般に稼働率の低い領域を対象とした改良ではあるものの,稼働率が20%から40%へと向上するケースのあることも明らかとなった. |
| 審査要旨 | | 本論文は,「細粒度高並列応用プログラムの実行機構に関する研究」と題し,8章より構成されている.並列計算機を利用する場合,一つの応用プログラムを多数の細粒度タスクに分割して効率よく実行させる必要がある.並列計算機ではメモリアクセスの遅延が大きくなるため,各プロセッサにはキャッシュメモリを付加するが,それでもキャッシュミスの発生による効率低下が問題になり,この欠点を回避する一つの手段として,プロセッサとして多重スレッド方式のものを使用する並列計算機が提案されている.本論文は,この多重スレッド方式のプロセッサを用いる並列計算機を対象とし,応用プログラムを効率よく実行させるための実行方式について研究したものである. 第1章は序論であり,本研究の背景と目的,従来の研究と本研究の特徴,および,本論文の構成を示している. 第2章は,「多重スレッド方式プロセッサを用いた並列計算機」と題し,以下の準備として,対象とする並列計算機の構成と動作原理,および,性能評価のために試作したシミュレータについて解説している.このシミュレータでは,プロセッサとしてSPARCの実プログラムを命令単位で実行していくものを用いている.したがって,SPARC用の実プログラムの実行時間を評価することができる. 第3章では,「サイクル毎固定順スレッド切替え方式プロセッサの性能評価」の結果を報告している.この方式は,スレッドを固定した順序で1サイクル毎に切替えていくもので,方式自体は早くから提案されていたものである.本論文では,用意したスレッド数と性能の関係をモデルによる解析とシミュレーションによって評価し,スレッド数を増加させていくと性能が階段状に上昇していくがやがて飽和が発生すること,その飽和は主としてプログラムに存在する並列度の不足部分によることを示している. 第4章は,「サイクル毎応答順スレッド切替え方式プロセッサの性能評価」と題し,より少数のスレッドでメモリアクセス遅延の影響を補償することができ,したがってプログラムの並列度の不足の影響をより受けにくい「応答順スレッド切替え方式」を提案し,その性能を評価した結果を報告している.この方式は,スレッドの実行順序を固定しないで,キャッシュメモリでヒットとして実行可能となったスレッドが存在すればそれを先に実行させる方式である.ミスするスレッドが発生してもヒットするスレッドで代行できるため,前章の固定順の方式よりもより少数のスレッドで同等の性能が得られることをシミュレーションによって示している.ただし,プロセッサのハードウエアは若干複雑になっている. 第5章は「多重スレッド方式プロセッサの稼働率評価モデル」と題し、キャッシュメモリがヒットした場合には同一スレッドの実行を継続し,ミスが発生した場合にのみスレッドを切替える方式を取扱っている.この方式自体はすでに提案されているものであるが,本論文では,プロセッサの稼働率を評価するためのモデルを提案している.キャッシュメモリにアクセスするときのミスがランダムに発生するとしたモデルからプロセッサの稼働率を計算し,シミュレーションによって求めた稼働率とよい近似で一致することを示している. 第6章は「多重スレッド方式プロセッサの動的スレッド数管理」と題し,プログラム実行時にスレッド数を動的に管理する方式を提案している.ミスが発生した場合,スレッドを切替えるとプロセッサのアイドリングを防止できるが,キャッシュメモリの容量が限定されているために新しいスレッドの実行を開始することによりミスの発生がさらに増加し,総合的には性能が低下する可能性がある.そこで,実行開始可能で待ち状態にあるスレッドの個数を一定数とするよう使用するスレッド数を増減させる方式を提案し,実際に性能がある程度向上することをシミュレーションによって示している. 第7章は「多重スレッド機構を用いた先読み処理」と題し,プログラムの並列度が小さくなった場合に,実行に利用できないスレッドを使用してメモリの先読みを行わせる方式を提案し,その効果を評価している. 第8章は結言であり,本研究の成果を要約している. 以上を要するに,本論文は,多重スレッド方式のプロセッサを使用した並列機を対象として,細粒度高並列の応用プログラムを効率よく実行させるための実行方式について研究し,いくつかの方式についてその性能を詳細に評価するとともに,応答順切替え方式とこれに付加することのできるスレッド数動的管理方式を提案してその効果を明らかにしており,情報工学上寄与する所が大きい.よって本論文は博士(工学)の学位請求論文として合格と認める. |