(57)【要約】【課題】グラフ構造で記述されたプログラムを実行するプロセッサにおいてデッドロックを回避する。【解決手段】グラム構造のプログラムを実行するプロセッサにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析部（５０１）と、暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消部（５０２）と、を備える。デッドロック解消部（５０２）は、暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する。【選択図】図５
2019179412.tif 000002
【特許請求の範囲】
【請求項１】
グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避方法であって、
グラフ構造で記述されたプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析ステップと、
前記暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消ステップと、を備え、
前記デッドロック解消ステップにおいて、
前記暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、
前記処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する、デッドロック回避方法。
【請求項２】
請求項１に記載のデッドロック回避方法であって、
前記開始特定処理において、前記処理開始ノードから処理を開始するように、前記処理開始ノードに対する開始指示情報を付与する、デッドロック回避方法。
【請求項３】
請求項１に記載のデッドロック回避方法であって、
前記開始特定処理において、前記処理開始ノードから処理を開始するように、処理の順番を指示する処理順番情報を付与する、デッドロック回避方法。
【請求項４】
グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避装置であって、
グラフ構造で記述されたプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析部（５０１）と、
前記暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消部（５０２）と、を備え、
前記デッドロック解消部は、
前記暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、
前記処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する、デッドロック回避装置。
【請求項５】
請求項４に記載のデッドロック回避装置であって、
前記デッドロック解消部は、前記開始特定処理において、前記処理開始ノードから処理を開始するように、前記処理開始ノードに対する開始指示情報を付与する、デッドロック回避装置。
【請求項６】
請求項４に記載のデッドロック回避装置であって、
前記デッドロック解消部は、前記開始特定処理において、前記処理開始ノードから処理を開始するように、処理の順番を指示する処理順番情報を付与する、デッドロック回避装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避方法及びデッドロック回避装置に関する。
【背景技術】
【０００２】
プログラムにおいて、２つ以上の処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまうデッドロックを回避するため、デッドロックが発生する場面に応じたデッドロック回避方法が提案されている。下記特許文献１では、割り込み処理に伴って発生するデッドロックを回避する方法が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第２０１２／１２０５７３号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１では、コプロセッサ命令の実行中に割り込み処理によってコプロセッサに対して処理を行うプロセッサシステムにおいて、デッドロックを回避することについては開示がある。
【０００５】
しかしながら、特許文献１に記載の発明では、プログラムをデータと処理とに分割してグラフ構造とし、それを読み込むことで動作するプロセッサ特有のデッドロックを回避することはできない。
【０００６】
本開示は、グラフ構造で記述されたプログラムを実行するプロセッサにおいてデッドロックを回避するデッドロック回避方法及びデッドロック回避装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本開示は、グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避方法であって、グラム構造のプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析ステップと、暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消ステップと、を備えている。デッドロック解消ステップにおいて、暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する。
【０００８】
また本開示は、グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避装置であって、グラム構造のプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析部（５０１）と、暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消部（５０２）と、を備えている。デッドロック解消部は、暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する。
【０００９】
処理開始ノードを特定し、その処理開始ノードから一連の処理が開始するように処理することで、入出力バッファがバッファ単位でループしている場合であっても、適切な処理準を定義することができ、見かけ上のデッドロックを回避して並列実行することができる。
【発明の効果】
【００１０】
本開示によれば、グラフ構造で記述されたプログラムを実行するプロセッサにおいてデッドロックを回避するデッドロック回避方法及びデッドロック回避装置を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、本実施形態の前提となる並列処理について説明するための図である。
【図２】図２は、図１に示される並列処理を実行するためのシステム構成例を示す図である。
【図３】図３は、図２に用いられるＤＦＰの構成例を示す図である。
【図４】図４は、コンパイラの機能的な構成例を説明するための図である。
【図５】図５は、デッドロック回避の一例を説明するための図である。
【図６】図６は、デッドロック回避の一例を説明するための図である。
【図７】図７は、デッドロック回避の一例を説明するための図である。
【図８】図８は、デッドロック回避の一例を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、添付図面を参照しながら本実施形態について説明する。説明の理解を容易にするため、各図面において同一の構成要素に対しては可能な限り同一の符号を付して、重複する説明は省略する。
【００１３】
図１（Ａ）は、グラフ構造で記述されたプログラムコードを示しており、図１（Ｂ）は、スレッドの状態を示しており、図１（Ｃ）は、並列処理の状況を示している。
【００１４】
図１（Ａ）に示されるように、本実施形態が処理対象とするプログラムは、データと処理とが分割されているグラフ構造を有している。このグラフ構造は、プログラムのタスク並列性、グラフ並列性を保持している。
【００１５】
図１（Ａ）に示されるプログラムコードに対して、コンパイラによる自動ベクトル化とグラフ構造の抽出を行うと、図１（Ｂ）に示されるような大量のスレッドを生成することができる。
【００１６】
図１（Ｂ）に示される多量のスレッドに対して、ハードウェアによる動的レジスタ配置とスレッド・スケジューリングにより、図１（Ｃ）に示されるような並列実行を行うことができる。実行中にレジスタ資源を動的配置することで、異なる命令ストリームに対しても複数のスレッドを並列実行することができる。
【００１７】
続いて図２を参照しながら、動的レジスタ配置及びスレッド・スケジューリングを行うアクセラレータとしてのＤＦＰ（Ｄａｔａ  Ｆｌｏｗ  Ｐｒｏｃｅｓｓｏｒ）１０を含むシステム構成例である、データ処理システム２を説明する。
【００１８】
データ処理システム２は、ＤＦＰ１０と、イベントハンドラ２０と、ホストＣＰＵ２１と、ＲＯＭ２２と、ＲＡＭ２３と、外部インターフェイス２４と、システムバス２５と、を備えている。ホストＣＰＵ２１は、データ処理を主として行う演算装置である。ホストＣＰＵ２１は、ＯＳをサポートしている。イベントハンドラ２０は、割り込み処理を生成する部分である。
【００１９】
ＲＯＭ２２は、読込専用のメモリである。ＲＡＭ２３は、読み書き用のメモリである。外部インターフェイス２４は、データ処理システム２外と情報授受を行うためのインターフェイスである。システムバス２５は、ＤＦＰ１０と、ホストＣＰＵ２１と、ＲＯＭ２２と、ＲＡＭ２３と、外部インターフェイス２４との間で情報の送受信を行うためのものである。
【００２０】
ＤＦＰ１０は、ホストＣＰＵ２１の重い演算負荷に対処するために設けられている個別のマスタとして位置づけられている。ＤＦＰ１０は、イベントハンドラ２０が生成した割り込みをサポートするように構成されている。
【００２１】
続いて図３を参照しながら、ＤＦＰ１０について説明する。図３に示されるように、ＤＦＰ１０は、コマンドユニット１２と、スレッドスケジューラ１４と、実行コア１６と、メモリサブシステム１８と、を備えている。
【００２２】
コマンドユニット１２は、コンフィグ・インターフェイスとの間で情報通信可能なように構成されている。コマンドユニット１２は、コマンドバッファとしても機能している。
【００２３】
スレッドスケジューラ１４は、図１（Ｂ）に例示されるような多量のスレッドの処理をスケジューリングする部分である。スレッドスケジューラ１４は、スレッドを跨いだスケジューリングを行うことが可能である。
【００２４】
実行コア１６は、４つのプロセッシングエレメントである、ＰＥ＃０と、ＰＥ＃１と、ＰＥ＃２と、ＰＥ＃３と、を有している。実行コア１６は、独立してスケジューリング可能な多数のパイプラインを有している。
【００２５】
メモリサブシステム１８は、アービタ１８１と、Ｌ１キャッシュ１８ａと、Ｌ２キャッシュ１８ｂと、を有している。メモリサブシステム１８は、システム・バス・インターフェイス及びＲＯＭインターフェイスとの間で情報通信可能なように構成されている。
【００２６】
続いて、図４を参照しながら、本開示のデッドロック回避装置の一例としてのコンパイラ５０について説明する。本開示のデッドロック回避装置の実施形態はコンパイラ５０に限られるものではなく、図１（Ａ）に例示されるグラフ構造で記述されたプログラムをスレッドに展開するものであれば、図２に示されるようなデータ処理システム２や、図３に示されるようなＤＦＰ１０に実装されてもよい。
【００２７】
コンパイラ５０は、機能的な構成要素として、グラフ構造解析部５０１と、デッドロック解消部５０２と、を有している。
【００２８】
グラフ構造解析部５０１は、グラフ構造で記述されたプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出する部分である。
【００２９】
図５に示されるような処理を参照しながら説明する。図５に示される処理では、ｂｕｆ０のデータを用いてｆｕｎｃ１［０］の処理が実行され、その実行結果がｂｕｆ１［０］に保持される。続いて、ｂｕｆ１［０］のデータを用いてｆｕｎｃ２［０］の処理が実行され、その実行結果がｂｕｆ２［０］に保持される。続いて、ｂｕｆ２［０］のデータを用いてｆｕｎｃ１［１］の処理が実行され、その実行結果がｂｕｆ１［１］に保持される。続いて、ｂｕｆ１［１］のデータを用いてｆｕｎｃ２［１］の処理が実行され、その実行結果がｂｕｆ２［１］に保持される。この処理をＮ回行い、最後の計算結果ｆｕｎｃ２［Ｎ］を最終出力とする。
【００３０】
並列実行可能なプロセッサ向けでこのような処理を実現しようとすると、図５のバッファ部分に着目することになり、ｂｕｆ２とｂｕｆ１との間でデッドロックが発生しているように見えるため、並列処理を実行するこができない。
【００３１】
しかしながら、上記説明したように、処理の記述を適切に行い、バッファのインデックスを変更することで、図６に示されるようなデッドロックを回避した処理が可能となる。そこで、グラフ構造解析部５０１は、図５に示されるような箇所を、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所として抽出する（グラフ構造解析ステップ）。
【００３２】
デッドロック解消部５０２は、暫定デッドロック箇所におけるデッドロックを解消する部分である。デッドロック解消部５０２は、暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する（デッドロック解消ステップ）。このようにデッドロック解消部５０２が開始特定処理を実行することで、デッドロック状態を解消し、図６に例示するような処理が可能となる。
【００３３】
開始特定処理の一例としては、図７に示されるように、開始特定処理において、処理開始ノードであるｆｕｎｃ１から処理を開始するように、処理開始ノードであるｆｕｎｃ１に対する開始指示情報を付与する。開始指示情報としては、ｋｉｃｋコマンドが用いられる。
【００３４】
開始特定処理の別例としては、図８に示されるように、開始特定処理において、処理開始ノードであるｆｕｎｃ１から処理を開始するように、処理の順番を指示する処理順番情報を付与する。
【００３５】
上記したように本実施形態は、グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避方法であって、グラフ構造で記述されたプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析ステップと、暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消ステップと、を備えている。デッドロック解消ステップにおいて、暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する。
【００３６】
装置として捉えれば、グラフ構造で記述されたプログラムを実行するプロセッサにおけるデッドロックを回避するデッドロック回避装置であって、グラフ構造で記述されたプログラムにおいて、入出力バッファがバッファ単位でループし見かけ上デッドロックとなる暫定デッドロック箇所を抽出するグラフ構造解析部５０１と、暫定デッドロック箇所におけるデッドロックを解消するデッドロック解消部５０２と、を備えている。デッドロック解消部５０２は、暫定デッドロック箇所において処理を開始する処理開始ノードを特定し、処理開始ノードから一連の処理が開始されるように特定する開始特定処理を実行する。
【００３７】
処理開始ノードを特定し、その処理開始ノードから一連の処理が開始するように処理することで、入出力バッファがバッファ単位でループしている場合であっても、適切な処理準を定義することができ、見かけ上のデッドロックを回避して並列実行することができる。
【００３８】
図７を参照しながら説明したように、デッドロック回避方法では、開始特定処理において、処理開始ノードから処理を開始するように、処理開始ノードに対する開始指示情報を付与することができる。同様に、デッドロック回避装置では、デッドロック解消部５０２が、前記開始特定処理において、前記処理開始ノードから処理を開始するように、前記処理開始ノードに対する開始指示情報を付与することができる。このように、開始指示情報を付与することで、処理開始ノードを特定することができ、並列処理が可能となる。
【００３９】
図８を参照しながら説明したように、デッドロック回避方法では、開始特定処理において、処理開始ノードから処理を開始するように、処理の順番を指示する処理順番情報を付与することができる。同様に、デッドロック回避装置では、デッドロック解消部５０２は、開始特定処理において、処理開始ノードから処理を開始するように、処理の順番を指示する処理順番情報を付与することができる。このように、処理順番情報を付与することで、処理順番を特定することができ、並列処理が可能となる。
【００４０】
以上、具体例を参照しつつ本実施形態について説明した。しかし、本開示はこれらの具体例に限定されるものではない。これら具体例に、当業者が適宜設計変更を加えたものも、本開示の特徴を備えている限り、本開示の範囲に包含される。前述した各具体例が備える各要素およびその配置、条件、形状などは、例示したものに限定されるわけではなく適宜変更することができる。前述した各具体例が備える各要素は、技術的な矛盾が生じない限り、適宜組み合わせを変えることができる。
【符号の説明】
【００４１】
５０１：グラフ構造解析部
５０２：デッドロック解消部
【図１】
2019179412.tif 000003
【図２】
2019179412.tif 000004
【図３】
2019179412.tif 000005
【図４】
2019179412.tif 000006
【図５】
2019179412.tif 000007
【図６】
2019179412.tif 000008
【図７】
2019179412.tif 000009
【図８】
2019179412.tif 000010