(57)【要約】【課題】マルチコアCPUを搭載する並列計算機においては、ループ制御変数の要素を分割することによる要素並列化のみ、もしくはループ内の命令列を分割して並列実行するセクション並列化のみの適用では、性能劣化を引き起こす可能性がある。本発明が解決しようとする課題は、マルチコアCPU搭載計算機の構成を考慮した並列化を実現することである。【解決手段】マルチコアCPUチップ間で要素並列化し、同時に、チップ内CPUコア間でセクション並列化する並列化コンパイルを行う。得られたオブジェクトコード実行時の複数スレッドの内、ループ制御変数の同一要素を担当する複数スレッドを、同一CPUチップ下のCPUコアで実行させる。【選択図】図１
2006268070.tif 000002
【特許請求の範囲】
【請求項１】
与えられたソースコードプログラムを、それぞれが１つもしくは複数のＣＰＵコアを含む複数のＣＰＵチップで構成される並列計算機で並列実行可能なオブジェクトコードに変換する並列化コンパイル方法であって、
前記プログラム中の各ループを、ループ制御変数の要素で分割することにより前記複数のＣＰＵチップに対応した複数のループに分割し、
更に、該分割されたループの各々を、ループ内の命令列の並列化可能な複数のセクションに分割することにより、更に複数のループに分割し、
該複数ループの各々を異なるスレッドで並列実行させるオブジェクトコードを出力することを特徴とする並列化コンパイル処理方法。
【請求項２】
前項出力するオブジェクトコードは、複数のスレッドを起動した後、該複数スレッドの内ループ制御変数の同一要素を担当する各スレッドを、同一のCPUチップ上の１つもしくは複数のCPUコアで実行させる手段を持つオブジェクトコードであることを特徴とする請求項１に記載の並列化コンパイル処理方法。
【請求項３】
前項出力するオブジェクトコードが起動する複数のスレッドは、該複数スレッドの内ループ制御変数の同一要素を担当する複数のスレッドの各々が、ループ制御変数の同一要素を担当することを示す識別子を持つことを特徴とする請求項１に記載の並列化コンパイル処理方法。
【請求項４】
前項出力するオブジェクトコードは、前記CPUチップ内のCPUコアが、CPUコア内の資源を複数に分割し複数のスレッドを同時に実行可能であるマルチスレッディングの機能を持つ場合には、１CPUチップが、１CPUコアが同時に実行可能なスレッド数と１CPUチップ上の物理的なCPUコア数との乗数分のCPUコアを持つと見なして、起動した複数スレッドの内ループ制御変数の同一要素を担当する各スレッドを同一のCPUチップ上のCPUコアで実行させるオブジェクトコードである、請求項１に記載の並列化コンパイル処理方法。
【請求項５】
前記プログラム中に検出した複数のループで、単一のループに融合可能である場合には、該複数ループを単一のループに融合させた上で、並列化の適用を行うことを特徴とする、請求項１記載の並列化コンパイル処理方法。
【請求項６】
前記各ループを並列化する際に、同一要素を担当する複数のスレッドが一定時間間隔、もしくはループ制御変数の一定要素個数が進行するごとに、互いに同期を取ることが可能な命令を追加する手順を更に有し、複数スレッドの進行を揃えることを特徴とする請求項１に記載の並列化コンパイル処理方法。
【請求項７】
それぞれが１つもしくは複数のＣＰＵコアを含む複数のＣＰＵチップで構成される並列計算機に対して供給されるオブジェクトプログラムであって、原プログラムに含まれるループを、当該ループの制御変数の要素で分割する要素並列化法でスレッドに分割して前記複数のＣＰＵチップ間で並列実行させ、各ＣＰＵチップの内部では、各ＣＰＵチップに割り当てたスレッドを、前記ループを構成する命令列の複数のセクションに分割するセクション並列化法で更にスレッドに分割して並列実行させる事を特徴とするオブジェクトプログラム。
【請求項８】
前記ＣＰＵコアは資源を複数に分割して複数のスレッドを同時に実行可能であるマルチスレッディングの機能を持ち、各ＣＰＵチップの内部では、前記各ＣＰＵチップに割り当てたスレッドを、１CPUコアが同時に実行可能なスレッド数と１CPUチップ上の物理的なCPUコア数との乗数分のセクションに前記ループを構成する命令列を分割するセクション並列化法で分割して並列実行させることを特徴とする請求項７記載のオブジェクトプログラム。
【請求項９】
並列計算機で動作するオペレーティングシステムであって、
実行するオブジェクトコード中の１つもしくは複数のループが、ループ制御変数の要素を分割することにより複数のループに分割する要素並列化手法が適用され、
更に、該分割されたループの各々を、ループ内の命令列を並列化可能な複数のセクションに分割することにより、更に複数のループに分割するセクション並列化が適用され、
該複数ループの各々を異なるスレッドで並列実行する手段を持つオブジェクトコードである際に、複数のスレッドを起動した後、該複数スレッドの内ループ制御変数の同一要素を担当する各スレッドを、同一のCPUチップ上の１つもしくは複数のCPUコアで実行させる手段を持つことを特徴とするオペレーティングシステム
【請求項１０】
前記並列計算機が搭載するCPUチップ内のCPUコアが、CPUコア内の資源を複数に分割し複数のスレッドを同時に実行可能であるマルチスレッディングの機能を持つ場合には、１CPUチップが、１CPUコアが同時に実行可能なスレッド数と１CPUチップ上の物理的なCPUコア数との乗数分のCPUコアを持つと見なして、実行時のスレッドを割り当てる手段を持つことを特徴とする請求項９に記載のオペレーティングシステム。
【請求項１１】
複数のCPUを搭載する並列計算機で、
オブジェクトコード中の１つもしくは複数のループが、ループ制御変数の要素を分割することにより複数のループに分割する要素並列化手法が適用され、
更に、該分割されたループの各々を、ループ内の命令列を並列化可能な複数のセクションに分割することにより、更に複数のループに分割するセクション並列化が適用され、
該複数ループの各々を異なるスレッドで並列実行する手段を持つオブジェクトコードを実行する際、複数のスレッドを起動した後、該複数スレッドの内ループ制御変数の同一要素を担当する各スレッドを、同一のCPUチップ上の１つもしくは複数のCPUコアで実行させる手段を持つことを特徴とする並列計算機。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算機のためのプログラムの並列化コンパイル処理方法、並列化されたオブジェクトコードを実行する並列計算機、及びそのオペレーティングシステムに関する。
【背景技術】
【０００２】
複数のCPUを搭載する並列計算機において、あるプログラムを複数CPUで並列に動作させる場合の手法として、与えられたプログラムから並列化可能な命令を抽出する、要素並列化、もしくはセクション並列化、と呼ばれる並列化手法がある。これらの並列化手法は、主にプログラムのコンパイル時に適用される。
要素並列化では、図２に示すように、プログラム中のループについて、ループの制御変数Iの各要素を、実行するCPU数で均等に割った分のループを複数スレッドで実行し、該複数スレッドの各々を複数のCPUが担当する。図２の例では、制御変数Iの範囲である１〜ＮまでをCPU数４で均等に割った分の要素について各スレッド０〜３が担当し、その各スレッドをCPUコア１０１、１０２、１０３、１０４が並列に実行する。
セクション並列化では、図３に示すようにプログラム中のループについて、ループ中の命令列を互いに独立な命令列（セクション）に分け、その各セクションについてのループを各スレッド０〜３が担当し、その各スレッドをCPU１０１、１０２、１０３、１０４が並列に実行する。
しかし近年、半導体プロセスの進歩により、１チップ内に複数CPUコアを搭載するマルチコアチップが登場しつつある（非特許文献１）。一方、物理的な１CPUを仮想的に複数CPUに見せて複数スレッドを同時に実行できるマルチスレッディング機構を実装したCPUも主流となりつつある（INTEL/Pentium4(登録商標)など、非特許文献２）。このようなCPUを搭載する並列計算機では、図４のような構成となり、CPUコア０とCPUコア１の関係とCPUコア０とCPUコア２の関係は、キャッシュを共有するか否かという相違があることになる。このような構成の並列計算機において、上記の並列化手法では問題が起こる可能性がある。
【０００３】
【非特許文献１】The Power4 Processor Introduction and Tuning Guide (IBM Redbooks, 2001)
【０００４】
【非特許文献２】David Koufaty, Deborah T. Marr, HYPERTHREADING TECHNOLOGY IN THE NETBURST MICROARCHITECTURE, IEEE MICRO March-April 2003，pp56-65
【発明の開示】
【発明が解決しようとする課題】
【０００５】
図４に示すような，マルチコアCPUを搭載する並列計算機を考える。該並列計算機は、１チップ上に２つのCPUコアを搭載したマルチコアCPUを２個搭載する。このような計算機を用いて、図２、３のように、プログラムを要素並列化もしくはセクション並列化により実行する場合、要素並列化、セクション並列化にはそれぞれ以下のようなデメリットがある。
まず図２の要素並列化では、CPUコアが増大するにつれて１CPU当たりのループ長が短くなり、ループ起動時のオーバヘッドの影響が大きくなる。図４のように全CPUコア数が４つ程度であればそれほど影響はないが、現在は数十個ものCPUコアを搭載する並列計算機が存在し、今後その数は増える傾向にあると言える。実行するCPUコア数が増えるほど、要素並列化時の各CPUコアが実行を担当するループのループ長は短くなるため、ループ起動時オーバヘッドが無視できなくなる可能性がある。また、要素並列化では、各CPUがロードしなければならない配列の数は逐次実行と変わらないため、図２のように多くのストリームが存在するループの場合、アーキテクチャによっては全てのストリームにプリフェッチを発行できず、性能が大幅に劣化する可能性がある。通常、メモリからのデータプリフェッチが可能なストリーム数はCPUコアごとに制限があり、無数のストリームにプリフェッチを発行できるわけではないからである。図２の例のプログラムでは、例えばループ分割によって４つのループに分割することもできるが、ループ長が長い場合、B1、B2、C1、D1、F1など再利用性のある配列を再度メモリからロードしなければならず、やはり性能は劣化する。
【０００６】
図３のセクション並列化では、第一に、多数CPUコアに対してセクションを分割しにくいという問題がある。例えば、図４の並列計算機ように全CPUコア数が４つの場合、図３のループは４セクションに分けて各CPUコア数で実行することができるが、それ以上のCPUコア数構成の場合、セクション並列化は困難になる。また、セクション(1)〜(4)の実行速度が大きく異なる場合、並列化効率が落ちるという問題も生じる。また、マルチコアチップではチップ内に各CPUコア間で共有されるキャッシュを持つことが多いが、セクション(1)〜(4)の実行速度が大きく異なる場合、再利用性のある配列B1、B2、C1、D1、F1もキャッシュアウトする可能性がある。仮にキャッシュヒットであっても、例えば配列E1、F1のアクセス時にはチップ間の通信が発生し、性能低下の原因となる可能性がある。
【課題を解決するための手段】
【０００７】
本発明の代表的実施例における並列化コンパイル処理方法の特徴は、生成したオブジェクトプログラムを実行する並列計算機の構成に対応したプログラム並列化を行う点にある。より詳細には、マルチコアCPU、もしくはマルチスレッド実装CPUを搭載する並列計算機のためのプログラムの並列化であってその対象計算機のＣＰＵ構成に対応して要素並列化とセクション並列化を組み合わせるた並列化を行うことを特徴とする。
図４の構成の並列計算機を例にとって、本発明のコンパイル処理方法を説明する。図５のようにプログラム中のループに対し、CPUチップ数２で要素並列化し、更にその並列化されたループをループ内の(1)(2)(3)(4)のセクションに分割して並列化する。並列化されたプログラムの実行時に８個のスレッドを起動し、チップ間で要素並列実行、チップ内でセクション並列実行となるように、ループ制御変数の同一要素を担当する複数スレッドが全て同一のチップ下のCPUコアで実行されるように並列化する。
【発明の効果】
【０００８】
以上の並列化手法、及び、並列実行方法により、単純に要素並列化もしくはセクション並列化を行った場合と比べて以下のような効果を期待できる。
まず、要素並列化に対する優位点として、全CPUコア間で要素並列化する場合と違い、チップ内のCPUコア数倍にループ長を長くすることができ、ループ起動オーバヘッドの影響を少なくすることができる。また、１CPUコア当たりのストリーム数が減るため、プリフェッチ可能なストリーム数制限を越えてしまう多ストリームループにおいてもプリフェッチを有効に発行できることが期待できる。例えば図５のソースコードでは、全部でB1、C1、D1、E1、F1、G1、B2、C2、D2、D3の１０個のロードストリームが存在する。しかし本発明の並列化方式によれば、CPUチップ０下で実行される４つのループの内、上２つをCPUコア０、下２つをCPUコア1で実行する場合には、CPUコア０でのロードストリーム数は６個、CPUコア１でのロードストリーム数が４個と、CPUコア当たりのストリーム数を減らすことができる。加えて、CPUコア当たりのストリーム数が減ることにより、１ストリーム当たりの共有キャッシュ容量が相対的に大きくなり、キャッシュヒットの確率が高くなる効果も期待できる。
【０００９】
セクション並列化に対する優位点としては、チップ内CPUコア数でのセクション並列化のため、全CPUコア数で分割するよりもセクションを分割しやすいことが挙げられる。加えて、チップ内のCPUコア間でのセクション並列化のため、チップ内のCPUコア間で実行速度が均等になるようにセクションを分割し易く、全CPUコアごとのセクション並列と比べ並列化効率が高くなると期待できる。さらに、チップ内に共有キャッシュメモリがある場合、同一イタレーションの配列データはチップ内の共有キャッシュにあると期待できるため、余計なチップ間通信が発生しない。
加えて、マルチスレッディングを実装したCPUにおける本発明のメリットについて述べる。一般に、マルチスレッディングを実装したCPUでは、複数の仮想CPUに対して同質のコードを流すより、使用するCPU資源が極力競合しないように異質のコードを流す方が実効効率が高くなる。本発明による並列化手法では、単純な要素並列化と異なり複数CPUコアに対してセクション並列化を利用するため、性質の異なるコードを実行させ易い。マルチスレッディングを実装したCPUでは以上の効果も期待できる。
【実施例１】
【００１０】
本発明の代表的なコンパイル処理の流れは図１の通りである。本実施例におけるコンパイラは、コンパイル対象のプログラムが実行される並列計算機の構成の内、搭載するCPUチップが保持するCPUコア数を、コンパイルオプションもしくはオペレーティングシステムの設定パラメータもしくは環境変数から引数として受け取る。この場合のCPUコア数は、該CPUコアがマルチスレッディングの機能を搭載している場合は、１CPUコアが同時に実行可能なスレッド数とCPUチップが保持するCPUコア数の乗数と見なされる。
コンパイル中のプログラム並列化処理においてコンパイラは、プログラム中にループを検出すると、図１の処理を行う。図４に記載の並列計算機を対象とする場合を例としてその流れを以下に説明する。図４の計算機２００は、CPUチップ１０、２０を持ち、該CPUチップの各々が、CPUコア１０１、１０２とCPUコア１０３、１０４を持つ。また、CPUチップ１０、２０はそれぞれ２CPUコアに共有されるキャッシュメモリ１２１、１２２を持つ。更に、該計算機２００は２CPUチップから共有される主メモリ１３０を持つ。
コンパイラは最初に、ループ中の再利用性のある配列の有無を調べる。図５のループにおいては、配列B1、B2、C1、D1、F1が再利用性のあるループである。
【００１１】
再利用性のある配列がない場合で、かつループ長がｎ以上（このｎはコンパイル時オプション、もしくはアーキテクチャの特徴によりコンパイラに既定の値）の場合は、ループ分割を行う。ループ分割とは、図５のプログラムにおいては、(1)(2)(3)(4)をそれぞれループ制御変数は同等の４つのループに分割することを指す。ループ長がｎ未満の場合、ループ分割を行うとループが増えることによるループ起動オーバーヘッドの増分が実行時間に占める比率が高くなるため、ループ分割は行わずに、要素並列化が可能かどうかの判定をする。
ループ中に再利用性のある配列がある場合は、ループ分割をするとデータの再利用性が失われ、キャッシュを活用できないため、要素並列化が可能かどうかの判定に進む。要素並列化が可能であると判定された場合は、次に該ループのロードストリーム数が、１CPUコア当たりがプリフェッチ可能なストリーム数（この値はコンパイル時オプション、もしくはアーキテクチャの特徴によりコンパイラに既定の値）を超えているかどうかの判定をする。該ループのストリーム数がプリフェッチ可能なストリーム数以内であれば要素並列化のみを適用する。図５のプログラムのように、ループのストリーム数がプリフェッチ可能なストリーム数を超えている場合は、次にセクション並列化が可能かどうかの判定を行う。
【００１２】
セクション並列化が可能かどうかの判定のため、最初にループ内の命令列を互いに非依存の最小単位にセクション分割する。ただしこの際、新たに逐次性を生むような分割、例えば、A1(I) = B1(I) + C1(I) + D1(I) の命令を A1(I) = B1(I) + C1(I) とA1(I) = A1(I) + D1(I) とに分割することは、両スレッドに逐次性が発生することになり、並列実行できないため行わない。図５のループでは、(1)(2)(3)(4)の４セクションに分割することができる。次に、分割されたセクションの個数がCPUチップ内CPUコア数と同等かそれ以上であることを確認する。この条件が満たされない場合は、セクション並列化は不可能として、ループのストリーム数がプリフェッチ可能なストリーム数以内の場合と同様、要素並列化のみ適用する。図４に搭載されるCPUチップ内CPUコア数は２であるため、この条件が満たされる図５のようなループの場合には、要素並列化を適用したループに対して更に、セクション(1)(2)(3)(4)に分割するセクション並列化を適用する。
以上の並列化処理をプログラム内ループの全てに行った後、コンパイラより出力される並列化されたオブジェクトコードの動作については実施例３に記載する。
【実施例２】
【００１３】
実施例１の並列化処理において、並列化処理の前にループ融合による最適化を行う方法を説明する。
図８のソースコード#1のように、ループを融合しソースコード#2のようなソースコードに変換できるとコンパイラが判断した場合には、ループを融合した後に、実施例１の並列化処理を行う。
以上の方法により、配列B1、B2、C1、D1、F1のアクセスに再利用性を持たせることが可能となり、メモリからのデータ転送を削減することが可能となる。
【実施例３】
【００１４】
本発明の代表的な並列化オブジェクトコードの実行時の動作は図６の通りである。図６に示す並列化されたプログラムのオブジェクトコードは、並列化されたループである並列実行部を３つ持ち、該並列実行部の両端には逐次実行部を持つ。
図６のオブジェクトを図４の計算機で実行する際の動作を下記に記述する。図４の計算機２００は、CPUチップ１０、２０を持ち、該CPUチップの各々が、CPUコア１０１、１０２とCPUコア１０３、１０４を持つ。また、CPUチップ１０、２０はそれぞれ２CPUコアに共有されるキャッシュメモリ１２１、１２２を持つ。更に、該計算機２００は２CPUチップから共有される主メモリ１３０を持つ。
該オブジェクトコード実行時には、実行オプションとして、要素並列化数を与える。図４の計算機では、全CPUコアで実行する場合にはCPUチップ数である要素並列化数２を実行時オプションとして与え、オブジェクトコードを実行する。
該オブジェクトコードは、並列実行部１、２、３のループがそれぞれ要素並列化されており、さらに、並列実行部１、２に関してはループ内命令がそれぞれセクション(1)〜(4)の４つと、セクション(5)〜(9)に分割されセクション並列化されている。
そのため該オブジェクトコードは、要素並列化数２と、並列実行部１、２、３の内最も多いセクション並列化数である並列実行部２のセクション数５、との乗数である１０個のスレッド、すなわち、図６の表で表すスレッド＃０〜９の１０個のスレッドで並列実行される。逐次実行部１〜４はスレッド＃０が担当するものとし、並列実行部１、２、３は図６の表のように各スレッドが担当する。
該オブジェクトコードが起動するスレッド＃０〜９は、自身が担当するループ制御変数の要素により、グループ識別子を持つ。図４の並列計算機で動作するオペレーティングシステムは、スレッド＃０〜９のグループ識別子を読み取り、識別子が同じスレッドを、同一CPUチップ下のCPUコアで実行させる。図６の例では、スレッド＃０〜４をCPUチップ０下のCPUコア０、１で、スレッド＃５〜９をCPUチップ１下のCPUコア２、３で実行させる。各CPUチップ下の２つCPUコアの内どちらで実行されるかはオペレーティングシステムのタイムシェアリングシステムにより任意に選択される。
【実施例４】
【００１５】
実施例１の並列化コンパイラによって並列化されたオブジェクトコードを実施例３に記載の方法で実行した場合、各スレッドの実行の進行状況によっては、再利用性のある配列のアクセスがキャッシュミスを引き起こす可能性がある。例えば、図６の並列実行部１の実行時に、スレッド＃０の進行がスレッド＃１に比べ非常に早い場合を考える。ここで、図７のように並列実行部１のスレッド＃０、１にのみ注目し、時間T1〜T4における各スレッドのループ制御変数の進行状況を表に示す。ここで、図４の計算機の持つ共有キャッシュ１２１、１２２は512キロバイトのキャッシュ容量を持ち、配列の１要素は8バイトであるとすると、時間T3の時、既にスレッド＃０は制御変数I=10000まで進行しており、A1(I)、B1(I)、C1(I)、D1(I)、E1(I)、F1(I)、G1(I)の７つの配列のI=100〜10000までの容量は512キロバイトを超える。従って、スレッド＃１が配列B1(100)、C1(100)、D1(100)をアクセスした時には、既にキャッシュアウトしており、キャッシュミスする。
このような事態を避けるために、グループ識別子が同じ複数スレッド同士で、一定間隔ごとに同期を取り、進行速度をそろえることが考えられる。並列実行部１では、ロードとストアのストリーム数は合計で１４個あるため、
512キロバイト × 1024 / 8 / 14 = 4681
の計算で、全スレッドが4681個の要素をアクセスすると古いデータからキャッシュアウトすると考えられる。従って、全スレッドがループ制御変数が4681の倍数になるごとに各スレッドで同期を取り、再利用性のある配列アクセス時のキャッシュミスを回避する。
【産業上の利用可能性】
【００１６】
本発明は、プログラムの並列化手法、並列化コンパイラ、並列化されたオブジェクトコード、オペレーティングシステム、並列計算機に関する。特に１CPUチップに複数のCPUコアを搭載するマルチコアCPUや、CPUコア内の資源を複数に分割し複数のスレッドを同時に実行可能であるマルチスレッディングの機能を持つCPUを搭載する計算機において有効に利用可能である。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施例の並列化コンパイル処理方法を示すフローチャートでありる。
【図２】要素並列化を示すする概念図である。
【図３】セクション並列化を示す概念図である。
【図４】上記実施例で生成された並列化オブジェクトプコードを実行するマルチコアCPUチップを搭載する並列計算機のシステム構成図である。
【図５】上記実施例の列化コンパイル処理方法によるループの並列化過程を示す概念図である。
【図６】上記実施例で生成された並列化されたオブジェクトコードの動作をを示す概念図である。
【図７】本発明の別の実施例における並列化されたオブジェクトコードの起動するスレッド間での同期について示す概念図である。
【図８】本発明の更に別の実施例のコンパイル処理方法におけるループ融合を示す概念図である。
【符号の説明】
【００１８】
１０、２０：ＣＰＵチップ
１０１、１０２、１０３、１０４：ＣＰＵコア
１２１，１２２：キャッシュメモリ
１３０：メインメモリ。
【図１】
2006268070.tif 000003
【図２】
2006268070.tif 000004
【図３】
2006268070.tif 000005
【図４】
2006268070.tif 000006
【図５】
2006268070.tif 000007
【図６】
2006268070.tif 000008
【図７】
2006268070.tif 000009
【図８】
2006268070.tif 000010