(57)【特許請求の範囲】
【請求項１】
複数のプロセッサによって並列実行される複数のプログラム間の順序関係を解析する順序関係解析装置であって、
プログラムの実行が割り当てられたプロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報とを収集する収集手段と、
プログラムの順序値を表す複数の要素を有するデータフォーマットを記憶する記憶手段と、
プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記データフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定手段と、
プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算手段とを備え、
前記計算手段は、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算する
ことを特徴とする順序関係解析装置。
【請求項２】
前記決定手段は、前記要素同士が前記プロセッサ毎に排他的となるよう、前記対応要素を決定する
ことを特徴とする請求項１に記載の順序関係解析装置。
【請求項３】
前記データフォーマットが有する前記要素の数は、プログラムを実行可能な前記プロセッサの総数のＮ（Ｎ＝１以上の整数）倍である
ことを特徴とする請求項１又は請求項２に記載の順序関係解析装置。
【請求項４】
前記収集手段は、プログラムの実行中に発生したメモリアクセスの種別、メモリアクセスの順序、メモリアクセスの対象のメモリアドレス及び前記プログラムを特定するメモリアクセス情報を更に収集し、
前記メモリアクセス情報に基づいて、同一のメモリアドレスへのメモリアクセスが発生する複数のプログラム間の順序値を解析し、前記複数のプログラム間の順序関係が成立しない場合、排他制御エラーとして検出する第１検出手段を更に備え、
前記第１検出手段は、
前記メモリアクセス情報によって特定される前記メモリアクセスの順序及び前記プログラムを用いて、前記プログラムに対応付けられた前記対応要素が表す前記順序値であり前記メモリアクセスの属するセグメントに対して計算された順序値を特定し、前記順序値を用いて、前記メモリアクセスの種類及び前記メモリアドレス毎のアクセス状態を記憶するアドレス状態情報を更新する更新手段と、
プログラムの実行中に前記メモリアクセスが発生した場合、前記メモリアクセスの発生前に同一のメモリアドレスに対して発生した第１メモリアクセスに対して更新された前記アドレス状態情報と、現在発生した前記メモリアクセスの属する前記セグメントに対して計算された順序値とを用いて、第１メモリアクセスが属する前記セグメントと、現在発生した前記メモリアクセスの属する前記セグメントとの間に順序関係が成立するか否かを解析する第２検出手段とを有する
ことを特徴とする請求項３に記載の順序関係解析装置。
【請求項５】
前記計算手段は、プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記対応要素が表す前記順序値を計算して、前記対応要素が表す順序値と前記プログラムを特定するプログラム識別情報とを対応付けて前記記憶手段に記憶し、
前記更新手段は、前記メモリアクセス情報によって特定される前記メモリアクセスの順序及び前記プログラムを用いて、前記プログラム識別情報を取得すると共に、前記プログラムに対応付けられた前記対応要素が表す前記順序値であり前記メモリアクセスの属するセグメントに対して計算された順序値を特定し、前記プログラム識別情報及び前記順序値を用いて、前記メモリアクセスの種類及び前記メモリアドレス毎のアクセス状態を記憶するアドレス状態情報を更新し、
前記第２検出手段は、プログラムの実行中に前記メモリアクセスが発生した場合、前記メモリアクセスの発生前に同一のメモリアドレスに対して発生した第１メモリアクセスに対して更新された前記アドレス状態情報と、現在発生した前記メモリアクセスの属する前記セグメントに対して計算され前記データフォーマットに記憶された順序値及び前記プログラム識別情報とを用いて、第１メモリアクセスが属する前記セグメントと、現在発生した前記メモリアクセスの属する前記セグメントとの間に順序関係が成立するか否かを解析する
ことを特徴とする請求項４に記載の順序関係解析装置。
【請求項６】
前記同期情報は、同期処理の種別及び同期相手のプログラムを特定可能であり、
前記同期処理の種別には、同期元処理と同期先処理とがあり、
前記計算手段は、プログラムの実行中に前記同期処理が発生した場合且つ前記同期情報によって特定される前記同期処理の種別が前記同期元処理である場合、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を増加させ、前記対応要素を表す前記順序値を前記プログラムの同期対応情報として第２記憶手段に記憶させ、プログラムの実行中に前記同期処理が発生した場合且つ前記同期情報によって特定される前記同期処理の種別が前記同期先処理である場合、前記同期情報によって特定される前記同期相手のプログラムの前記同期対応情報として記憶された前記対応要素が表す前記順序値と、前記同期先処理に対応して決定された第２対応要素が表す前記順序値とを用いて、前記第２対応要素が表す順序値を更新する
ことを特徴とする請求項１乃至５のいずれか一項に記載の順序関係解析装置。
【請求項７】
複数のプロセッサによって各々実行されることにより並列実行される複数のプログラム間の順序関係を解析する順序関係解析装置であって、
プログラムの実行が割り当てられた前記プロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報と、プログラムの実行中に発生したメモリアクセスの種別、メモリアクセスの順序、メモリアクセスの対象のメモリアドレス及び前記プログラムを特定するメモリアクセス情報とを収集する収集手段と、
プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記プログラムの順序値を表す複数の要素を有するデータフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定手段と、
プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算手段と、
前記メモリアクセス情報に基づいて、同一のメモリアドレスへのメモリアクセスが発生する複数のプログラム間の順序値を解析し、前記複数のプログラム間の順序関係が成立しない場合、排他制御エラーとして検出する第１検出手段とを備え、
前記計算手段は、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算し、
前記第１検出手段は、前記メモリアクセス情報によって特定される前記メモリアクセスの順序及び前記プログラムを用いて、前記プログラムに対応付けられた前記対応要素が表す前記順序値であり前記メモリアクセスの属するセグメントに対して計算された順序値を特定し、前記順序値を用いて、前記メモリアクセスの種類及び前記メモリアドレス毎のアクセス状態を記憶するアドレス状態情報を更新する更新手段と、プログラムの実行中に前記メモリアクセスが発生した場合、前記メモリアクセスの発生前に同一のメモリアドレスに対して発生した第１メモリアクセスに対して更新された前記アドレス状態情報と、現在発生した前記メモリアクセスの属する前記セグメントに対して計算された順序値とを用いて、第１メモリアクセスが属する前記セグメントと、現在発生した前記メモリアクセスの属する前記セグメントとの間に順序関係が成立するか否かを解析する第２検出手段とを有する
ことを特徴とする順序関係解析装置。
【請求項８】
前記セグメントは、前記同期処理毎に分割される
ことを特徴とする請求項１乃至請求項７いずれか一項に記載の順序関係解析装置。
【請求項９】
前記データフォーマットは、所定のプロセッサで実行されるプログラムが関連する同期処理によって保証される順序関係を順序値として表す複数の要素を有し、
前記複数の要素は、前記所定のプロセッサで実行されるプログラムと、他のプロセッサで実行される各プログラムとの相対的な順序関係を表す第１要素と、前記所定のプロセッサが自身で実行するプログラムが関連する同期処理によって自身が保証する順序関係を表す第２要素とを含み、
前記計算手段は、前記所定のプロセッサのプログラムの実行中に同期処理として当該プログラムが同期元になる同期元処理が発生した場合、前記第２要素が表す順序値を更新する
ことを特徴とする請求項１乃至請求項８のいずれか一項に記載の順序関係解析装置。
【請求項１０】
複数のプロセッサによって各々実行されることにより並列実行される複数のプログラム間の順序関係を解析する順序関係解析方法であって、
プログラムの実行が割り当てられた前記プロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報とを収集する収集ステップと、
プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記プログラムの順序値を表す複数の要素を有するデータフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定ステップと、
プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算ステップとを含み、
前記計算ステップでは、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算する
ことを特徴とする順序関係解析方法。
【請求項１１】
複数のプロセッサによって各々実行されることにより並列実行される複数のプログラム間の順序関係を解析するコンピュータに実行させるための順序関係解析プログラムであって、
プログラムの実行が割り当てられた前記プロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報とを収集する収集ステップと、
プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記プログラムの順序値を表す複数の要素を有するデータフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定ステップと、
プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として前記決定手段が決定した前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算ステップとを含み、
前記計算ステップでは、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算する
ことを特徴とする順序関係解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列に実行されたプログラム間の順序関係を解析する順序関係解析装置、方法及びプログラムに関する。
【背景技術】
【０００２】
共有メモリを有するマルチプロセッサにおける並列プログラミング環境として、例えば、POSIX threadに代表されるマルチスレッド方式がある。このマルチスレッド方式で記述されたプログラムにおいては、複数のスレッド間の同期関係が正しく記述されていることが重要である。スレッド間の同期関係が正しく記述されなかった場合には、例えば、以下のような問題が発生することが知られている。複数のスレッドが同時に同じメモリ領域を更新してしまうデータレースと呼ばれる問題である。
【０００３】
このデータレースを検出するための手段として、スレッドごとの論理的な時間を定義するLogical Vector Clock(ベクター)を利用して実行されたスレッド内区間の半順序関係を記憶し、メモリ内の同じアドレスにアクセスしたスレッド内区間同士に順序関係が存在したかどうかを検査する方式がある（例えば、特許文献１、非特許文献１参照）。この方式では、実行されたスレッドごとに実行状態をトレース情報として収集し、このトレース情報から得られる情報をもとにして、実行されたスレッド間の順序関係を示すLogical Vector Clockを計算する。一般的にLogical Vector Clockによる順序関係解析では、Logical Vector Clockの各要素にそれぞれ異なるスレッドから見た時刻を記憶していくため、解析対象となるスレッドの数と同数の要素数を持ったLogical Vector Clockを利用する必要がある。このため、特許文献１や非特許文献１などの従来技術においては、実行されたスレッドの数に比例して解析のためのデータサイズ(Logical Vector Clockのサイズ)も増えてしまい、多数のスレッドで実現する並列処理においては解析そのものにかかるリソースも増大してしまう。
【０００４】
近年では、Logical Vector Clockの要素数をスレッド数未満で固定にしておいて、解析に必要な情報が極力欠落しないようにしつつ、スレッド数未満に限定された数の要素を複数のスレッドが再利用しながら解析を行う手法も提案されている（例えば、非特許文献２参照）。
【０００５】
【特許文献１】US patent, 6593940 : “Method for finding errors in multithreaded applications”,2003
【非特許文献１】”A Theory of Data Race Detection”, PADTAD-IV 2006, Intel
【非特許文献２】A. Gidenstam, “Adaptive Plausible Clocks”, Technical Report no. 2003-7, Goterborg University, 2003
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献２に記載されたNUREVと呼ばれる技術は、同時に並列実行されうる処理の間でも要素を共有することを目的としている。このため、この技術では、同期処理が発生するたびにスレッドの時刻を示すための要素を決定するための処理が必要となり、要素の決定自体に処理負担が掛かる。また同期処理ごとに割り当てる要素のマッピングが動的に変更されるために、マッピングに関する情報を保持するメモリ容量も大きくなってしまう。また非特許文献２に記載されたREVと呼ばれる技術についても、スレッドのＩＤをLogical Vector Clockのサイズで割った剰余値を利用して、割り当てる要素を決定しているだけなので、同時に実行されたスレッド等でも同じ要素を共有してしまうといった問題がある。
【０００７】
本発明は、上記に鑑みてなされたものであって、情報の欠落を回避しながらリソースの消費を低減させてプログラム間の順序関係を解析可能な順序関係解析装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明は、複数のプロセッサによって並列実行される複数のプログラム間の順序関係を解析する順序関係解析装置であって、プログラムの実行が割り当てられたプロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報とを収集する収集手段と、プログラムの順序値を表す複数の要素を有するデータフォーマットを記憶する記憶手段と、プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記データフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定手段と、プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算手段とを備え、前記計算手段は、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算することを特徴とする。
【０００９】
また、本発明は、複数のプロセッサによって各々実行されることにより並列実行される複数のプログラム間の順序関係を解析する順序関係解析装置であって、プログラムの実行が割り当てられた前記プロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報と、プログラムの実行中に発生したメモリアクセスの種別、メモリアクセスの順序、メモリアクセスの対象のメモリアドレス及び前記プログラムを特定するメモリアクセス情報とを収集する収集手段と、プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記プログラムの順序値を表す複数の要素を有するデータフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定手段と、プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算手段と、前記メモリアクセス情報に基づいて、同一のメモリアドレスへのメモリアクセスが発生する複数のプログラム間の順序値を解析し、前記複数のプログラム間の順序関係が成立しない場合、排他制御エラーとして検出する第１検出手段とを備え、前記計算手段は、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算し、前記第１検出手段は、前記メモリアクセス情報によって特定される前記メモリアクセスの順序及び前記プログラムを用いて、前記プログラムに対応付けられた前記対応要素が表す前記順序値であり前記メモリアクセスの属するセグメントに対して計算された順序値を特定し、前記順序値を用いて、前記メモリアクセスの種類及び前記メモリアドレス毎のアクセス状態を記憶するアドレス状態情報を更新する更新手段と、プログラムの実行中に前記メモリアクセスが発生した場合、前記メモリアクセスの発生前に同一のメモリアドレスに対して発生した第１メモリアクセスに対して更新された前記アドレス状態情報と、現在発生した前記メモリアクセスの属する前記セグメントに対して計算された順序値とを用いて、第１メモリアクセスが属する前記セグメントと、現在発生した前記メモリアクセスの属する前記セグメントとの間に順序関係が成立するか否かを解析する第２検出手段とを有することを特徴とする。
【００１０】
また、本発明は、複数のプロセッサによって各々実行されることにより並列実行される複数のプログラム間の順序関係を解析する順序関係解析方法であって、プログラムの実行が割り当てられた前記プロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報とを収集する収集ステップと、プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記プログラムの順序値を表す複数の要素を有するデータフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定ステップと、プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として決定された前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算ステップとを含み、前記計算ステップでは、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算することを特徴とする。
【００１１】
また、本発明は、複数のプロセッサによって各々実行されることにより並列実行される複数のプログラム間の順序関係を解析するコンピュータに実行させるための順序関係解析プログラムであって、プログラムの実行が割り当てられた前記プロセッサを特定する割当先プロセッサ情報と、プログラムの実行中に発生した同期処理の順序及び前記プログラムを特定する同期情報とを収集する収集ステップと、プログラムの実行が開始された場合、前記割当先プロセッサ情報に基づいて、前記プログラムの順序値を表す複数の要素を有するデータフォーマットの有する複数の要素のうち、前記プログラムに対応付ける対応要素を決定する決定ステップと、プログラムの実行中に前記同期処理が発生した場合、前記同期情報に基づいて、前記プログラムに対応付ける要素として前記決定手段が決定した前記対応要素が表す前記順序値を、前記プログラムを１つ以上に分割したセグメント毎に計算する計算ステップとを含み、前記計算ステップでは、前記複数の要素のうち第１対応要素に対応付けられた第１プログラムの実行が終了した後に実行が開始される第２プログラムに対応付ける要素として前記第１対応要素が決定された場合、前記第２プログラムの先頭のセグメントが前記第１プログラムの最後のセグメントに後続するセグメントであるとして、前記第１対応要素が表す前記順序値を計算することにより、前記第２プログラムの順序値を計算することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、スレッドの実行が割り当てられたプロセッサに応じて、データフォーマットの有する複数の要素の中から、当該スレッドに対応付ける要素を決定することにより、データフォーマットの有する要素数を低減させることができる。また、セグメント毎に順序値を計算することにより、同一の要素に対応付けられた異なるスレッドの順序値を連続するセグメントの順序値として時系列に正しく計算することができる。このため、情報の欠落を回避しながらリソースの消費を低減させてスレッド間の順序関係を解析することができる。
【発明を実施するための最良の形態】
【００１３】
以下に添付図面を参照して、この発明にかかる順序関係解析装置、方法及びプログラムの最良な実施の形態を詳細に説明する。
【００１４】
（１）構成
＜解析システムの構成＞
図１は、解析システムＳＹＭの全体構成を示すブロック図である。本実施の形態に係る解析システムＳＹＭは、システム１とシステム２とから構成され、システム１とシステム２とはバス３によって接続されている。システム１は、プロセッサＰ１０〜Ｐ１３と、これらのプロセッサＰ１０〜Ｐ１３が共有するメモリＭ１０とから構成される。また、システム１には外部記憶装置Ｍ１１が接続される。メモリＭ１０には、データレースの検出対象であるマルチスレッドプログラムや各スレッドの実行を制御するためのスケジュール管理プログラムなどの制御プログラムなどの各種プログラムが記憶される。プロセッサＰ１０は、メモリＭ１０に記憶されたスケジュール管理プログラムを実行することにより、マルチスレッドプログラムに含まれる各スレッドの実行を管理する。以降、プロセッサＰ１０をスケジューラという。スケジューラは、具体的には、マルチスレッドプログラムに含まれる各スレッドに対してプロセッサＰ１１〜Ｐ１３のいずれかを割り当てベクターを割り当てたり、プロセッサＰ１１〜Ｐ１３による各スレッドの開始や実行状態などを制御する。プロセッサＰ１１〜Ｐ１３は、プロセッサＰ１０の制御の下、メモリＭ１０に記憶されたマルチスレッドプログラムに含まれる複数のスレッドを各々実行する。ここでは、この複数のスレッドが、順序関係を解析する対象の複数のプログラムに相当する。外部記憶装置Ｍ１１には、各種プログラムや各種データが記憶される。
【００１５】
システム２は、プロセッサＰ２０とメモリＭ２０とから構成される。また、システム２には外部記憶装置Ｍ２１が接続される。メモリＭ２０には、スレッド間の順序関係を解析するための順序関係解析プログラムやデータレースを検出するためのデータレース検出プログラムが記憶されている。また、メモリＭ２０には、スレッド間の順序関係を解析するためのトレース情報が記憶される。トレース情報は、システム１からバス３を介してシステム２に転送される。トレース情報の詳細については後述する。外部記憶装置Ｍ１１には、各種プログラムや各種データが記憶される。
【００１６】
＜スレッド実行モデル＞
ここで、システム１で実行されるマルチスレッドプログラムの動作について説明する。図２は、マルチスレッドプログラムの動作を概念的に示した図である。マルチスレッドプログラムにおける各スレッドの実行は、上述のスケジューラにより管理される。スケジューラは、マルチスレッドプログラムにおいて生成された(create)スレッドをReady Groupとして管理し、プロセッサＰ１１〜Ｐ１３のうちスレッドを実行可能なプロセッサ（実行プロセッサという）が見つかれば、Ready Groupに属するスレッドの１つを選択してその実行プロセッサに実行を割り当てる(start)。そして、スケジュール装置は、実行を割り当てたスレッドをExe Groupとして管理する。一方、スレッドが割り当てられた実行プロセッサは、そのスレッドを実行し、新たなスレッドの生成(create)や、他のスレッドによる同期通知待ち（wait）や、他のスレッドの同期待ちの解除（signal）や、スレッドの終了通知(finish)などのイベントをスケジューラを介して実行する。
【００１７】
本実施の形態では、実行プロセッサがスレッドを実行中に、メモリＭ１０を介して他のスレッドを実行中の他の実行プロセッサとデータの授受を行うことが可能である。このような構成において、「wait」と「signal」との組、もしくは「create」と「start」との組による同期関係が正しく指定されていない場合には、並列実行されているスレッドが同時に同じメモリアドレスに対して更新処理を行うといったデータレースが発生しうる。本実施の形態における解析システムＳＹＭはこのようなデータレースを検出する。
【００１８】
次に、上述のように実行されるスレッドの状態遷移について説明する。図３は、スレッドの状態遷移を概念的に示した図である。スレッドは、生成（create）されるとready状態になり、スケジューラにより、図２のReady Groupに追加され、実行が割り当てられる（start）とexe状態となり、割り当てられた実行プロセッサにより実行される。さらにexe状態のスレッドは、自身でwait処理を行うことによってsleep状態に遷移し、他のスレッドからの同期待ちの解除（signal）の通知を受けたスケジューラによってawake処理が行われると再びexe状態になる。さらにexe状態中に処理が終了するとfinish処理が行われdone状態に遷移する。
【００１９】
以上のマルチスレッドプログラムの実行モデルは公知技術を利用しているが、本実施の形態において特徴となるのは、exe状態にあるスレッドをスケジューラがready状態に遷移させないことである。つまり本実施の形態において、一旦実行が開始されたスレッドはその処理が終了するまで割り当てられた実行プロセッサに割り当てられ続けることが特徴である。その他の部分に関しては代替しうる全ての技術で置き換えても良い。
【００２０】
次に、複数のスレッドが並列実行される実行例について説明する。図４は、５つのスレッドが並列実行される様子を示した図である。５つのスレッドには、スレッドを識別するためのスレッド識別情報に相当するスレッドＩＤ(TID)として「Ｔ１」,「Ｔ２」,「Ｔ３」,「Ｔ４」,「Ｔ５」が各々付与されているものとする。尚、TIDについては、本来整数値で十分であるが、スレッドのIDであることを明確にするために、ここでは「T1」、「T2」、・・・のように”T”をその順番を示す数値の前に付したものを示している。各スレッドに対するID(TID)は例えば上述のスケジューラにより付与される。
【００２１】
スレッド間の破線矢印は同期処理を示しており、その種別が「create」もしくは「signal」であることが示されている。また「ＷＲ」および「ＲＤ」はあるアドレス「0x1000」に対してメモリアクセスが発生したことを示しており、それぞれ該アドレスに対する書き込み処理及び読み出し処理を各々示している。各スレッドＴ１〜Ｔ５は、「start」してから「create」、「signal」、「awake」及び「finish」が発生するごとに、セグメントに分割されるものとする。例えば、スレッドＴ３においては、「start」から一番目の「create」が発生するまでを１つのセグメントとし、一番目の「create」が発生してから二番目の「create」が発生するまでを別の１つのセグメントとする。
【００２２】
＜解析システムの機能的構成＞
次に、解析システムＳＹＭの機能的構成について説明する。図５は、解析システムＳＹＭの機能的構成を示した図である。解析システムＳＹＭの機能は、トレース収集部１０と、順序情報更新部１１と、データレース検出部１２と、トレース情報ＤＢ２０と、順序関係情報テーブル２２と、アドレス状態情報テーブル２３と、TID-vec_ID対応表２１とから構成される。
【００２３】
トレース収集部１０は、システム１で所定のプログラムが実行されることにより実現される機能であり、システム１でマルチスレッドプログラムが実行されている場合に発生した同期処理に関する情報やメモリアクセスに関する情報をトレース情報として収集し、トレース情報ＤＢ２０に順次記憶させる。このトレース収集部の構成は、例えば、特許文献１で示されるような公知技術によって実現可能である。本実施の形態においては、収集すべきトレース情報には特徴があるが、その収集方法については特に限定しない。トレース情報の詳細な構成については後述する。
【００２４】
順序情報更新部１１は、システム２で順序情報更新プログラムが実行されることにより実現される機能であり、トレース情報ＤＢ２０に記憶されているトレース情報に基づいて、スレッドに対応つけるベクターの要素を決定したり、順序関係情報テーブル２２を更新したりする。順序情報更新部１１の詳細な構成については後述する。
【００２５】
データレース検出部１２は、システム２でデータレース検出プログラムが実行されることにより実現される機能であり、トレース情報ＤＢ２０に記憶されているトレース情報がメモリアクセスに関する情報であった場合には、TID-vec_ID対応表２１及び順序関係情報テーブル２２に基づいて、データレース検出処理を行って検出結果を出力すると共に、アドレス状態情報テーブル２３を更新する。
【００２６】
トレース情報ＤＢ２０は、トレース情報を記憶するデータベースであり、システム２のメモリＭ２０に記憶される。順序関係情報テーブル２２は、順序関係情報を記憶するものであり、メモリＭ２０に記憶される。アドレス状態情報テーブル２３は、アドレス状態情報を記憶するものであり、メモリＭ２０に記憶される。TID-vec_ID対応表２１は、スレッドとベクターとの対応関係を示すテーブルであり、メモリＭ２０に記憶される。以下、トレース情報、順序関係情報、アドレス状態情報及びTID-vec_ID対応表２１のデータ構成について各々説明する。
【００２７】
＜トレース情報＞
図６は、トレース情報のデータ構成を例示する図である。同図は、上述の図４に示した５つのスレッドT１〜Ｔ５が並列に実行された場合のトレース情報を例示している。トレース情報は、イベントの発生毎にシステム１で生成されシステム２に転送されてトレース情報ＤＢ２０に記憶される。同図においては、上から下に向かってイベントの発生時期が新しい順にトレース情報が並んでいる。尚、イベントの種別には、同期処理「sync」と、メモリアクセス「mem」とがある。種別が同期処理のイベントには、上述した「start」,「 awake」,「create」,「signal」,「finish」がある。このうち、「create」,「signal」は同期元処理であり、「start」,「 awake」は、同期先処理である。「また、種別がメモリアクセスのイベントには、「Write」, 「Read」がある。これらの「start」,「 awake」,「create」,「signal」,「finish」，「Write」, 「Read」はイベント名として便宜的に取り扱う。図６に示されるように、トレース情報は、イベントを発生させたスレッドのＩＤ（TID）と、発生させたイベントが「start」だった場合に当該スレッドを実行するプロセッサのID（PID）と、イベントの種別（event_type）と、イベント名(event_name)と、イベントが「start」もしくは「awake」だった場合の同期元識別ID(sync_src)と、イベントが「create」もしくは「signal」だった場合の同期先識別ID(sync_dst)と、イベントの種別がメモリアクセスだった場合のアクセス先のメモリアドレス(mem_addr)とを含む。各プロセッサのPIDについては、図１のプロセッサＰ１１のPIDを「１」とし、プロセッサＰ１２のPIDを「２」とし、プロセッサＰ１３のPIDを「３」とする。また同期元識別ＩＤ及び同期先識別ＩＤとして、「start」から「create」への関係においては新たに起動されるスレッドのTIDを用いることとし、「signal」から「awake」への関係においては同期変数名を用いることとする。
【００２８】
トレース情報に含まれるプロセッサのID（PID）は割当先プロセッサ情報に相当し、イベントの種別（event_type）が「sync」である場合のイベント名(event_name)と、イベントが「start」もしくは「awake」だった場合の同期元識別ID(sync_src)と、イベントが「create」もしくは「signal」だった場合の同期先識別ID(sync_dst)とが同期情報に相当する。
【００２９】
＜順序関係情報＞
図７は順序関係情報のデータ構成を例示する図である。順序関係情報は、vec_IDとvec_valueとの組からなるベクターにより構成される。vec_IDは、ベクターのＩＤを示すものであり、整数値を取る。vec_IDの数は、本実施の形態においては、マルチスレッドプログラムを実行可能なプロセッサ（ここでは、プロセッサＰ１１〜Ｐ１３である）の数と同数である。即ち、ここでは、その数は３であるから、vec_IDの数は３であり、vec_IDが取る値は各々「１」、「２」、「３」とする。vec_valueは、複数の要素を含み、各要素に整数値を取る。vec_valueは、順序値に相当する。vec_valueは、データレースの検出が開始される前に全ての要素の値が「０」に初期化されるものとする。vec_valueに含まれる要素数は、データレースの検出が開始される前に決定される。尚、本実施の形態においては、要素数は、マルチスレッドプログラムを実行可能なプロセッサＰ１１〜Ｐ１３の数と同数「３」とし、各要素はプロセッサＰ１１〜Ｐ１３にその順に各々対応するものとする。
【００３０】
具体的には、順序関係情報は、プロセッサＰ１１〜Ｐ１３にその順に各々対応する要素を含む３次元のデータをvec_ID毎、即ち、プロセッサ毎に有するデータフォーマットにより定義される。データフォーマットとは、所定のプロセッサで実行されるスレッドが関連する同期処理によって保証される順序関係を順序値として表すものであり、順序関係を表す複数の要素を有する。複数の要素は、各々異なる順序関係を表す要素であり、所定のプロセッサで実行されるスレッドと他のプロセッサで実行される各スレッドとの相対的な順序関係を表す値や、所定のプロセッサが自身で実行するスレッドが関連する同期処理によって自身が保証する順序関係を表す値がある。また、所定のプロセッサ自身が保証する順序関係を表す要素の値は、所定のプロセッサが実行するスレッドが同期元処理を発生させる場合に順序情報更新部１１によりインクリメントされる。
【００３１】
より具体的には、データフォーマットは、vec_ID「１」に対応する３次元のデータ(y11,y12,y13)と、vec_ID「２」に対応する３次元のデータ(y21,y22,y23)と、vec_ID「３」に対応する３次元のデータ(y31,y32,y33)とを有する。(y11,y12,y13)は、プロセッサＰ１１で実行されるスレッドが関連する同期処理によって保証される順序関係を表す順序値である。要素y12は、プロセッサＰ１１で実行されるスレッドと、プロセッサＰ１２で実行される各スレッドとの相対的な順序関係を表す。要素y13は、プロセッサＰ１１で実行されるスレッドと、プロセッサＰ１３で実行される各スレッドとの相対的な順序関係を表す。要素y11は、プロセッサＰ１１が自身で実行するスレッドが関連する同期処理によって自身が保証する順序関係を表す。要素y11の値は、プロセッサＰ１１が実行するスレッドが同期元処理を発生させる場合にインクリメントされる。(y21,y22,y23)は、プロセッサＰ１２で実行されるスレッドが関連する同期処理によって保証される順序関係を表す順序値である。要素y21は、プロセッサＰ１２で実行されるスレッドと、プロセッサＰ１１で実行される各スレッドとの相対的な順序関係を表す。要素y23は、プロセッサＰ１２で実行されるスレッドと、プロセッサＰ１３で実行される各スレッドとの相対的な順序関係を表す。要素y22は、プロセッサＰ１２が自身で実行するスレッドが関連する同期処理によって自身が保証する順序関係を表す。要素y22の値は、プロセッサＰ１２が実行するスレッドが同期元処理を発生させる場合にインクリメントされる。(y31,y32,y33)は、プロセッサＰ１２で実行されるスレッドが関連する同期処理によって保証される順序関係を示す順序値である。要素y31は、プロセッサＰ１３で実行されるスレッドと、プロセッサＰ１１で実行される各スレッドとの相対的な順序関係を表す。要素y32は、プロセッサＰ１３で実行されるスレッドと、プロセッサＰ１２で実行される各スレッドとの相対的な順序関係を表す。要素y33は、プロセッサＰ１３が自身で実行するスレッドが関連する同期処理によって自身が保証する順序関係を表す。要素y33の値は、プロセッサＰ１３が実行するスレッドが同期元処理を発生させる場合にインクリメントされる。尚、順序情報更新部１１が各要素y11,y22,y33の値をインクリメントする動作については後述の動作欄で詳述する。
【００３２】
＜アドレス状態情報＞
図８はアドレス状態情報のデータ構成を例示する図である。アドレス状態情報は、メモリアドレスごとのアクセス履歴を記憶するための情報であり、アクセスされる対象のメモリアドレスと、Last Writeと、Last Readとの組から構成される。Last Writeは、対象のメモリアドレスに最後に書き込まれたときのベクターを示すものであり、vec_IDと、elem_valueとを含む。Last Readは、対象のメモリアドレスに最後に読み出されたときのベクターを示すものであり、vec_IDと、elem_valueとを含む。elem_valueとは、上述のvec_valueに含まれる要素のうちの１つであり、ここでは、スレッドを実行している実行プロセッサに対応する要素の取る値を示す。尚、アドレス状態情報のデータ構成は、例えば、非特許文献１で示されているような様々な方式に対して適用可能である。
【００３３】
＜TID-vec_ID対応表＞
図９はTID-vec_ID対応表のデータ構成を例示する図である。TID-vec_ID対応表２１は、スレッドのＩＤ（TID）と、スレッドに割り当てられたベクターのＩＤ(vec_ID)との組からなる。
【００３４】
＜順序情報更新部＞
次に、順序情報更新部１１の詳細な構成について説明する。図１０は順序情報更新部１１の詳細な構成を示したブロック図である。順序情報更新部１１は、要素番号決定部１１Ａと、順序情報計算部１１Ｂとから構成される。順序情報計算部１１Ｂは、同期対応表１１Ｃを有する。
【００３５】
要素番号決定部１１Ａは、トレース情報ＤＢ２０に記憶されているトレース情報のうち、発生時期が最も古いイベントに関するイベント情報であって種別が同期処理である第１イベント情報を取得し、これを基にTID-vec_ID対応表２１を参照してvec_IDを特定し、当該vec_IDと当該第１イベント情報とを順序情報計算部１１Ｂに引き渡す。尚、第１イベント情報は、図６に示したトレース情報における一行分の情報のうち、スレッドのＩＤ（TID）と、プロセッサのＩＤ（PID）と、イベント名（event_name）と、同期元識別ＩＤ（sync_src）と、同期先識別ＩＤ（sync_dst）とから構成される。順序情報計算部１１Ｂは、vec_IDと第１イベント情報とを基に、同期対応表１１Ｃに同期情報を記憶して、順序関係情報テーブル２２を更新する。
【００３６】
図１１は、同期対応表１１Ｃのデータ構成を例示する図である。同期対応表１１Ｃは、例えばメモリＭ２０に記憶され、同期情報を記憶する。同期対応表１１Ｃは、スレッドの実行中に同期処理として同期元処理となるイベント（「create」もしくは「signal」）が発生した時に、その同期先識別ＩＤ(sync_ID)及び当該スレッドに対応するベクターについて順序関係情報テーブル２２におけるvec_valueを同期元の情報（同期情報）として記憶する。順序情報計算部１１Ｂは、この同期情報を、同期先処理となるイベント（「start」もしくは「awake」）が処理されるまでの間同期対応表１１Ｃに記憶させておく。
【００３７】
＜データレース検出部＞
次に、データレース検出部１２の詳細な構成について説明する。図１２はデータレース検出部１２の詳細な構成を示したブロック図である。データレース検出部１２は、競合アクセス検出部１２Ａとアドレス状態更新部１２Ｂとから構成される。競合アクセス検出部１２Ａは、トレース情報ＤＢ２０に記憶されているトレース情報のうち、発生時期が最も古いイベントに関するイベント情報であって種別がメモリアクセスである第２イベント情報を取得し、これを基にデータレース検出処理を行う。なお第２イベント情報は、図６に示したトレース情報における一行分の情報のうち、スレッドのＩＤ（TID）と、イベント名（event_name）と、メモリアドレス（mem_addr）とから構成される。アドレス状態更新部１２Ｂは、競合アクセス検出部１２Ａがデータレース検出処理を行った後、第２イベント情報を基に、TID-vec_ID対応表２１及び順序関係情報テーブル２２を参照して、アドレス状態情報テーブル２３を更新する。
【００３８】
（２）動作
次に、本実施の形態の解析システムＳＹＭの動作について説明する。まず、解析システムＳＹＭが行う処理の概略的な手順について説明する。図１３は、解析システムＳＹＭが行う処理の概略的な手順を示すフローチャートである。解析システムＳＹＭは、トレース情報ＤＢ２０にトレース情報が記憶されている場合（ステップＳ１：ＮＯ）、イベントの発生時期が最も古いトレース情報を読み出し(ステップＳ２)、当該トレース情報に含まれるイベントの種別（event_type）を用いて、イベントの種別を判断する(ステップＳ３)。そして、イベントの種別（event_type）が同期処理(sync)であった場合には、順序情報更新部１１が、当該トレース情報から上述の第１イベント情報を取得して順序情報更新処理を行い、順序関係情報テーブル２２を更新する(ステップＳ４)。イベントの種別（event_type）がメモリアクセス(mem)であった場合には、データレース検出部１２が自当該トレース情報から上述の第２イベント情報を取得してデータレース検出処理を行って検出結果を出力すると共に、アドレス状態情報テーブル２３を更新する(ステップＳ５)。以上のように、解析システムＳＹＭは、トレース情報ＤＢ２０に記憶されたトレース情報をイベントの発生時期が古い順にトレース情報をチェックして、順序情報更新処理又はデータレース検出処理を適宜行う。
【００３９】
＜順序情報更新処理＞
図１４は順序情報更新処理の手順を示したフローチャートである。順序情報更新部１１の要素番号決定部１１Ａは、上述の第１イベント情報を取得し、当該第１イベント情報に含まれるイベント名（event_name）が「finish」か否かを判断する（ステップＳ１０）。当該判断結果が肯定的である場合、要素番号決定部１１Ａは、イベント情報に含まれるTIDに対応するエントリをTID-vec_ID対応表２１から削除して（ステップＳ２０）、処理を終了する。
【００４０】
ステップＳ１０の判断結果が否定的である場合、要素番号決定部１１Ａは、イベント名（event_name）が 「start」か否かを判断する(ステップＳ１１)。当該判断結果が肯定的である場合、スレッドの実行を開始することを意味するから、要素番号決定部１１Ａは、第１イベント情報に含まれるPIDを、当該スレッドに割り当てるvec_IDとして決定する（ステップＳ１２）。そして、要素番号決定部１１Ａは、第１イベント情報に含まれるTIDと、ステップＳ１２で決定したvec_IDとの組をTID-vec_ID対応表２１に記憶して、vec_IDと第１イベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１３）。そして処理は、ステップＳ１５に進む。ステップＳ１１の判断結果が否定的である場合、要素番号決定部１１Ａは、TID-vec_ID対応表２１を参照して、第１イベント情報に含まれるTIDに対応するvec_IDを検索して、検索の結果見つかったvec_IDとイベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１４）。そして処理は、ステップＳ１５に進む。
【００４１】
ステップＳ１５では、順序情報計算部１１Ｂが、第１イベント情報に含まれるイベント名（event_name）が何であるかを判断する。イベント名（event_name）が「create」又は「signal」であると判断した場合は、順序情報計算部１１Ｂは、順序関係情報テーブル２２において、vec_IDに対応するvec_valueに対して、vec_IDと同数番目の要素の値を１インクリメントする（ステップＳ１６）。更に、順序情報計算部１１Ｂは、イベント情報に含まれる同期先識別ＩＤと、ステップＳ１６でインクリメントしたvec_valueとの組を、同期先識別ＩＤと、src_vec_valueとの組として同期対応表１１Ｃに記憶する(ステップＳ１７)。また、ステップＳ１５で、イベント名（event_name）が「start」又は「awake」であると判断した場合は、順序情報計算部１１Ｂは、同期対応表１１Ｃを参照して、第１イベント情報に含まれるsync_srcによって示される同期元識別ＩＤと同じＩＤを示す同期先識別ＩＤを検索し、当該同期先識別ＩＤに対応するsrc_vec_valueを読み出す（ステップＳ１８）。そして、順序情報計算部１１Ｂは、このエントリを同期対応表１１Ｃから削除する。次に、順序情報計算部１１Ｂは、ステップＳ１８で読み出したsrc_vec_valueで示されるベクター値と、順序関係情報テーブル２２におけるvec_IDに対応するvec_valueで示されるベクター値に対して各要素の比較を行い、大きい方の要素を当該vec_IDに対応する新しいvec_valueの値として順序関係情報テーブル２２を更新する（ステップＳ１９）。
【００４２】
但し、イベント情報に含まれるsync_srcによって示される同期元識別ＩＤと同じＩＤを示す同期先識別ＩＤ及び当該同期先識別ＩＤに対応するsrc_vec_valueが同期対応表１１Ｃに記憶されていない場合、ステップＳ１９では、順序情報計算部１１Ｂは、順序関係情報テーブル２２におけるvec_IDに対応するvec_valueの値自体を新しいvec_valueの値として順序関係情報テーブル２２を更新する。
【００４３】
以上のように、本実施の形態においては、順序関係を解析したいスレッドのTIDの代わりにスレッドが実行されたPIDを基に決定されたvec_IDを用いて解析を行い、かつ同期処理が「start」だった際に同じvec_IDに割り当てられた直前のスレッドが有していたvec_valueを引き継ぐことによって直前のスレッドと新たに「start」したスレッドが同一スレッドの連続したセグメントであるとして解析することを特徴としている。それ以外のvec_valueの更新方法そのものに関しては限定されない。例えば本実施の形態においては同期処理の発生ごとに対応するvec_valueを更新しているが、それ以外のイベントでもインクリメントによるvec_valueの更新を行っても構わない。またインクリメントする際に「２」以上の整数値を加算するなどしても構わない。
【００４４】
図１５はデータレース検出処理の手順を示したフローチャートである。データレース検出部１２の競合アクセス検出部１２Ａは、上述の第２イベント情報を取得し、当該第２イベント情報に含まれるメモリアドレス（mem_addr）と同じメモリアドレスに関するアドレス状態情報がアドレス状態情報テーブル２３に既に存在しているか否かを判断する（ステップＳ３０）。当該判断結果が否定的である場合、ステップＳ３６に進む。ステップＳ３０の判断結果が肯定的である場合、競合アクセス検出部１２Ａは、次に、第２イベント情報に含まれるイベント名（event_name）が「Write」であるか「Read」であるかを判断する(ステップＳ３１)。イベント名（event_name）が「Write」であると判断した場合、競合アクセス検出部１２Ａは、アドレス状態情報テーブル２３に記憶されているアドレス状態情報のうち、第２イベント情報に含まれるメモリアドレス（mem_addr）と同じメモリアドレスに関するアドレス状態情報を参照し、当該アドレス状態情報に含まれるLast Readに対して競合判断処理を行う(ステップＳ３２)。
【００４５】
図１６は、競合判断処理の手順を示すフローチャートである。競合アクセス検出部１２Ａは、TID-vec_ID対応表２１を参照し、第２イベント情報に含まれるTIDに対応するvec_IDを取得する（ステップＳ４０）。次いで、競合アクセス検出部１２Ａは、ステップＳ４０で取得したvec_IDと、アドレス状態情報テーブル２３に記憶されているアドレス状態情報に含まれるLast Readのvec_IDとが同じであるか否かを判断する（ステップＳ４１）。当該判断結果が肯定的である場合、競合アクセス検出部１２Ａは、競合判断処理を終了する。ステップＳ４１の判断結果が否定的である場合、競合アクセス検出部１２Ａは、順序関係情報テーブル２２を参照し、ステップＳ４０で取得したvec_IDに対応するvec_valueを取得する（ステップＳ４２）。そして、競合アクセス検出部１２Ａは、ステップＳ４２で取得したvec_valueの中から、アドレス状態情報に含まれるLast Readのvec_IDと同数番目の要素の値を取得してこれをelem_val_sucとする（ステップＳ４３）。また、競合アクセス検出部１２Ａは、アドレス状態情報に含まれるLast Readのelem_valueで示される値をelem_val_preとする（ステップＳ４４）。次いで、競合アクセス検出部１２Ａは、elem_val_sucがelem_val_pre以下であるか否かを判断する（ステップＳ４５）。elem_val_sucがelem_val_pre以下であると判断した場合（ステップＳ４５：ＮＯ）、競合アクセス検出部１２Ａは、競合アクセスの発生をマークする（ステップＳ４６）。一方、elem_val_sucがelem_val_preより大きいと判断した場合（ステップＳ４５：ＹＥＳ）、競合アクセス検出部１２Ａは、競合判断処理を終了する。
【００４６】
図１５に戻り、ステップＳ３１で、イベント名（event_name）が「Read」であると判断した場合、もしくはステップＳ３１でイベント名が「Write」であると判断されてステップＳ３２を完了した後、競合アクセス検出部１２Ａは、アドレス状態情報テーブル２３に記憶されているアドレス状態情報のうち、第２イベント情報に含まれるメモリアドレス（mem_addr）と同じメモリアドレスに関するアドレス状態情報を参照し、当該アドレス状態情報に含まれるLast Writeに対して競合判断処理を行う(ステップＳ３３)。Last Writeに対する競合判断処理の手順は、上述の図１５に示したものと略同様であるため、その図示及び説明を省略する。上述のLast Readに対する競合判断処理と異なる点は、ステップＳ４３で、競合アクセス検出部１２Ａが、ステップＳ４２で取得したvec_valueの中からvec_IDと同数番目の要素の値を取得するのが、アドレス状態情報テーブル２３のLast Writeからであるという点である。
【００４７】
ステップＳ３３の後ステップＳ３４に進む。ステップＳ３４では、競合アクセス検出部１２Ａは、データレースを検出したか否かを判断する。図１５のステップＳ３５で競合アクセスの発生がマークされていた場合には、当該判断結果が肯定的となり、この場合、競合アクセス検出部１２Ａは、データレースの発生を報告して、ステップＳ３６に進む。ステップＳ３４の判断結果が否定的である場合、即ち、競合アクセスの発生がマークされていない場合には、ステップＳ３６に進む。ステップＳ３６では、アドレス状態更新部１２Ｂが、アドレス状態情報テーブル２３において、第２イベント情報に含まれるメモリアドレス（mem_addr）と同じメモリアドレスに対応するアドレス状態情報を更新する。
【００４８】
図１７は、アドレス状態情報を更新する処理の手順を示す図である。アドレス状態更新部１２Ｂは、第２イベント情報に含まれるメモリアドレス（mem_addr）と同じメモリアドレスに対応するアドレス状態情報がアドレス状態情報テーブル２３に存在しない場合(ステップＳ４９：ＮＯ)、当該メモリアドレスに対応する新しいアドレス状態情報を生成してこれをアドレス状態情報テーブル２３に登録する（ステップＳ５０）。次いで、アドレス状態更新部１２Ｂは、第２イベント情報に含まれるイベント名（event_name）を参照して、当該メモリアドレスに対するアクセスの種別が「Write」なのか「Read」なのかを判断する（ステップＳ５１）。イベント名（event_name）が「Write」であると判断した場合、アドレス状態更新部１２Ｂは、第２イベント情報に含まれるTIDに対応するvec_IDをID-vec_ID対応表２１から取得し、当該vec_IDをアドレス状態情報のLast Writeに記憶する（ステップＳ５２）。そして、アドレス状態更新部１２Ｂは、順序関係情報テーブル２２を参照して、ステップＳ５２で取得したvec_IDに対応するvec_valueを取得し、当該vec_valueに含まれる要素のうちvec_IDと同数番目の要素の値をアドレス状態情報のLast Writeのelem_valueとして記憶する(ステップＳ５３)。
【００４９】
一方、ステップＳ５１で、イベント名（event_name）が「Read」であると判断した場合、アドレス状態更新部１２Ｂは、第２イベント情報に含まれるTIDに対応するvec_IDをTID-vec_ID対応表２１から取得し、当該vec_IDをアドレス状態情報のLast Readに記憶する（ステップＳ５４）。そして、アドレス状態更新部１２Ｂは、順序関係情報テーブル２２を参照して、ステップＳ５４で取得したvec_IDに対応するvec_valueを取得し、当該vec_valueに含まれる要素のうちvec_IDと同数番目の要素の値をアドレス状態情報のLast Readのelem_valueとして記憶する(ステップＳ５５)。
【００５０】
なお、本実施の形態においては、データレース検出処理の方法及びアドレス状態情報を更新する処理の方法は上述したものに限らず、例えば、非特許文献１で示されているような様々な方法を適用可能である。ただしこれらの方法を適用する際にはTIDを直接用いる代わりにvec_IDを用いて解析を行う。
【００５１】
＜解析例＞
図１８〜２０は、図６に示されるトレース情報に基づいた、順序関係情報テーブル２２、TID-vec_ID対応表２１及びアドレス状態情報テーブル２３の各更新状態を各々示す図である。図２０については、メモリアドレス「0x1000」へのメモリアクセスに対するデータレース検出処理の結果も示している。これら各図において一番左の列(event)はイベントの種別を簡略的に示したラベルであり、これは図６で示すトレース情報と行ごとに一対一で対応しており、行毎にそのラベルによって示されるイベントが発生したときの各情報の値を示している。尚、図１８の一番最初の行の「init」を示すラベルは、初期処理を示している。２行目のラベル「Start T1@P1」は、イベントとして、PID「P1」のプロセッサＰ１１がスレッドT1の実行を開始したことを示しており、３行目のラベル「Start T2@P3」は、イベントとして、PID「P3」のプロセッサＰ１３がスレッドＴ２の実行を開始したことを示しており、４行目のラベル「Create T2→T3」は、イベントとして、スレッドT2がスレッドT3を生成したことを示しており、５行目のラベル「WR 0x1000@T2」は、イベントとして、スレッドT2がメモリアドレス「0x1000」へ書き込むことを示している。また残りの列にはそれぞれの情報がどのように更新されていくのかについて、更新された場合のみ表記されている。また図１８に示した順序関係情報テーブル２２において、メモリアクセスに関するイベントはvec_valueの更新に特に関係しないのでグレーの網掛けを行っている。図２０に示したアドレス状態情報テーブル２３において、同期処理に関するイベントはアドレス状態情報の更新に特に関係しないのでグレーの網掛けを行っている。さらに、TID-vec_ID対応表２１については、各ＴＩＤに関するエントリが生成されてから削除されるまでの期間のみを白で示し、エントリ自体が存在しない区間についてはグレーの網掛けを行っている。
【００５２】
以下、イベントの発生順に各情報がどのように更新されていき、どのようにデータレースが検出されるのかについて上述の動作欄で説明した処理の手順に従って説明する。
【００５３】
（init）
順序情報更新部１１は、初期処理として、順序関係情報テーブル２２において、全てのvec_IDに対するvec_valueについて、要素数が３でその各値が「０」の（0,0,0）として記憶する。
【００５４】
（Start T1@P1）
図６に示される１行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ１」、プロセッサのＩＤ「１」と、イベント名（event_name）「Start」、同期元識別ＩＤ（sync_src）「空値」及び同期先識別ＩＤ（sync_dst）「空値」を取得する。ここでは、イベント名（event_name）が「start」であるから（図１４のステップＳ１１：ＹＥＳ）、要素番号決定部１１Ａは、イベント情報に含まれるPID「１」を、当該スレッドに割り当てるvec_IDとして決定し(ステップＳ１２)、イベント情報に含まれるTID「Ｔ１」と、ステップＳ１２で決定したvec_ID「１」との組をTID-vec_ID対応表２１に記憶して、vec_ID「１」とイベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１３）。次いで、順序情報計算部１１Ｂはイベント名（event_name）が「start」であるから(ステップＳ１５：strat)、同期対応表１１Ｃを参照して、第１イベント情報に含まれるsync_srcによって示されるスレッドのＩＤと同じＩＤを示すsrc_TIDを検索する。ここでは、同期対応表１１Ｃには同期先識別ＩＤ及び当該同期先識別ＩＤに対応するsrc_vec_valueが未だ記憶されていないため、順序情報計算部１１Ｂは、順序関係情報テーブル２２においてvec_ID「１」に対応するvec_valueを(0,0,0)として更新する（ステップＳ１８〜１９）。
【００５５】
（Start T2@P3）
次に、図６に示される２行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ２」、プロセッサのＩＤ「３」と、イベント名（event_name）「Start」、同期元識別ＩＤ（sync_src）「空値」及び同期先識別ＩＤ（sync_dst）「空値」を取得する。ここでは、イベント名（event_name）が「start」であるから（図１４のステップＳ１１：ＹＥＳ）、要素番号決定部１１Ａは、イベント情報に含まれるPID「３」を、当該スレッドに割り当てるvec_IDとして決定し(ステップＳ１２)、イベント情報に含まれるTID「Ｔ２」と、ステップＳ１２で決定したvec_ID「３」との組をTID-vec_ID対応表２１に記憶して、vec_ID「１」とイベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１３）。次いで、順序情報計算部１１Ｂはイベント名（event_name）が「start」であるから(ステップＳ１５：strat)、同期対応表１１Ｃを参照して、第１イベント情報に含まれるsync_srcによって示される同期元識別ＩＤと同じＩＤを示す同期先識別ＩＤを検索する。ここでは、同期対応表１１Ｃには同期先識別ＩＤ及び当該同期先識別ＩＤに対応するsrc_vec_valueが未だ記憶されていないため、順序情報計算部１１Ｂは、順序関係情報テーブル２２においてvec_ID「３」に対応するvec_valueを(0,0,0)として更新する（ステップＳ１８〜１９）。
【００５６】
（Create T2→T3）
次に、図６に示される３行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ２」、プロセッサのＩＤ「空値」と、イベント名（event_name）「Create」、同期元識別ＩＤ（sync_src）「空値」及び同期先識別ＩＤ（sync_dst）「Ｔ３」を取得する。ここでは、イベント名（event_name）が「create」であるから（図１４のステップＳ１１：ＮＯ、ステップＳ１５：create）、要素番号決定部１１Ａは、TID-vec_ID対応表２１を参照して、イベント情報に含まれるTID「Ｔ２」に対応するvec_IDを検索して、検索の結果見つかったvec_ID「３」とイベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１４）。また、順序情報計算部１１Ｂは、順序関係情報テーブル２２において、vec_ID「３」に対応するvec_value(0,0,0)に対して、vec_ID「３」と同数番目(３番目)の要素の値を１インクリメントして、(0,0,1)とする（ステップＳ１６）。更に、順序情報計算部１１Ｂは、第１イベント情報に含まれる同期先識別ＩＤ「Ｔ３」と、ステップＳ１６でインクリメントしたvec_value(0,0,1)との組を、同期先識別ＩＤと、src_vec_valueとの組として同期対応表１１Ｃに記憶する(ステップＳ１７)。
【００５７】
（WR 0x1000@T2）
次に、図６に示される４行目のトレース情報に含まれるイベントの種別（event type）は、「mem」であり、イベントの種別がメモリアクセスであることを示しているから、ここでは、データレース検出部１２がデータレース検出処理を開始する。データレース検出部１２の競合アクセス検出部１２Ａは、第２イベント情報として、スレッドのＩＤ（TID）「Ｔ２」、イベント名（event_name）「Write」及びメモリアドレス（mem_addr）「0x1000」を取得する。そして、競合アクセス検出部１２Ａは、メモリアドレス「0x1000」に関するアドレス状態情報がアドレス状態情報テーブル２３に既に存在しているか否かを判断する（図１５のステップＳ３０）。ここでは、当該アドレス状態情報がアドレス状態情報テーブル２３に存在しないため、データレースは発生しないものとして、ステップＳ３６に進む。ステップＳ３６の具体的な処理として、図１７のステップＳ５０で、アドレス状態更新部１２Ｂが、メモリアドレス「0x1000」に関するアドレス状態情報をアドレス状態情報テーブル２３に登録する。メモリアクセスの種別は「write」であるから、ステップＳ５２では、アドレス状態更新部１２Ｂは、TID-vec_ID対応表２１を参照して、イベント情報に含まれるTID「Ｔ2」に対応するvec_ID「3」を取得し、この値「３」をメモリアドレス「0x1000」に関するアドレス情報のLast Writeのvec_IDとして記憶する。さらに、アドレス状態更新部１２Ｂは、順序関係情報テーブル２２に記憶されている順序関係情報のvec_ID「3」に対応するvec_value(0,0,1)を参照し、vec_IDと同数番目（3番目）の要素の値「１」を求め、この値「１」をメモリアドレス「0x1000」に関するアドレス状態情報のLast Writeのelem_valueとして記憶する。（ステップＳ５３）。
【００５８】
（Start T3@P2）
次に、図６に示される５行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ３」、プロセッサのＩＤ「２」と、イベント名（event_name）「Start」、同期元識別ＩＤ（sync_src）「Ｔ３」及び同期先識別ＩＤ（sync_dst）「空値」を取得する。ここでは、イベント名（event_name）が「start」であるから（図１４のステップＳ１１：ＹＥＳ）、要素番号決定部１１Ａは、イベント情報に含まれるPID「２」を、当該スレッドに割り当てるvec_IDとして決定し(ステップＳ１２)、イベント情報に含まれるTID「Ｔ３」と、ステップＳ１２で決定したvec_ID「２」との組をTID-vec_ID対応表２１に記憶して、vec_ID「２」とイベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１３）。次いで、順序情報計算部１１Ｂはイベント名（event_name）が「start」であるから(ステップＳ１５：strat)、同期対応表１１Ｃを参照して、第１イベント情報に含まれるsync_srcによって示される同期元識別ＩＤと同じＩＤを示す同期先識別ＩＤを検索する（ステップＳ１８）。ここでは、同期対応表１１Ｃには同期先識別ＩＤ「Ｔ３」と当該同期先識別ＩＤに対応するsrc_vec_value(0,0,1)とが記憶されているため、順序情報計算部１１Ｂは、当該src_vec_value(0,0,1)と、順序関係情報テーブル２２においてvec_ID「２」に対応するvec_value(0,0,0)との各要素の大小関係を判断し、各々大きい値を選択して(0,0,1)を得てこれを順序関係情報テーブル２２に記憶されている、vec_ID「2」に対応する順序関係情報のvec_valueとする（ステップＳ１９）。また、順序情報計算部１１Ｂは、参照した同期対応表１１Ｃのエントリを削除する。
【００５９】
（Finish T2）
次に、図６に示される６行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ２」、プロセッサのＩＤ「空値」と、イベント名（event_name）「Finish」、同期元識別ＩＤ（sync_src）「空値」及び同期先識別ＩＤ（sync_dst）「空値」を取得する。ここでは、イベント名（event_name）が「Finish」であるから（図１４のステップＳ１０：ＹＥＳ）、要素番号決定部１１Ａは、TID-vec_ID対応表２１からTID「Ｔ2」に関するエントリを削除する(ステップＳ２０)。
【００６０】
（Signal T1→T3）
次に、図６に示される７行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ１」、プロセッサのＩＤ「空値」と、イベント名（event_name）「Signal」、同期元識別ＩＤ（sync_src）「空値」及び同期先識別ＩＤ（sync_dst）「SIG１」を取得する。ここでは、イベント名（event_name）が「Signal」であるから（図１４のステップＳ１１：ＮＯ、ステップＳ１５：Signal）、要素番号決定部１１Ａは、TID-vec_ID対応表２１を参照して、イベント情報に含まれるTID「Ｔ１」に対応するvec_IDを検索して、検索の結果見つかったvec_ID「１」とイベント情報とを順序情報計算部１１Ｂに引き渡す（ステップＳ１４）。また、順序情報計算部１１Ｂは、順序関係情報テーブル２２において、vec_ID「１」に対応するvec_value(0,0,0)に対して、vec_ID「１」と同数番目(１番目)の要素の値を１インクリメントして、(1,0,0)とする（ステップＳ１６）。更に、順序情報計算部１１Ｂは、第１イベント情報に含まれる同期先識別ＩＤ「SIG１」と、ステップＳ１６でインクリメントしたvec_value(1,0,0)との組を、同期先識別ＩＤと、src_vec_valueとの組として同期対応表１１Ｃに記憶する(ステップＳ１７)。
【００６１】
（Finish T1）
次に、図６に示される８行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ１」、プロセッサのＩＤ「空値」と、イベント名（event_name）「Finish」、同期元識別ＩＤ（sync_src）「空値」及び同期先識別ＩＤ（sync_dst）「空値」を取得する。ここでは、イベント名（event_name）が「Finish」であるから（図１４のステップＳ１０：ＹＥＳ）、要素番号決定部１１Ａは、TID-vec_ID対応表２１からTID「Ｔ１」に関するエントリを削除する(ステップＳ２０)。
【００６２】
（Awake T1→T3）
次に、図６に示される９行目のトレース情報に含まれるイベントの種別（event type）は、「sync」であり、イベントの種別が同期処理であることを示しているから、ここでは、順序情報更新部１１が順序情報更新処理を開始する。順序情報更新部１１の要素番号決定部１１Ａは、第１イベント情報として、スレッドのＩＤ（TID）「Ｔ３」、プロセッサのＩＤ「空値」と、イベント名（event_name）「Awake」、同期元識別ＩＤ（sync_src）「SIG1」及び同期先識別ＩＤ（sync_dst）「空値」を取得する。ここでは、イベント名（event_name）が「Awake」であるから（ステップＳ１１：ＮＯ，ステップＳ１５：Awake）、要素番号決定部１１Ａは、TID-vec_ID対応表２１を参照して、イベント情報に含まれるTID「Ｔ3」に対応するvec_ID「2」を取得し（ステップＳ１４）、取得したvec_ID「２」とイベント情報とを順序情報計算部１１Ｂに引き渡す。ここでは、同期対応表１１Ｃには同期先識別ＩＤ「SIG1」と当該同期先識別ＩＤに対応するsrc_vec_value(1,0,0)とが記憶されているため、順序情報計算部１１Ｂは、当該src_vec_value(1,0,0)と、順序関係情報テーブル２２においてvec_ID「２」に対応するvec_value(0,0,1)との各要素の大小関係を判断し、各々大きい値を選択して(1,0,1)を得てこれを順序関係情報テーブル２２に記憶されている順序関係情報のvec_ID「2」に対応するvec_valueとする（ステップＳ１８〜１９）。また、順序情報計算部１１Ｂは、参照した同期対応表１１Ｃのエントリを削除する。
【００６３】
（RD 0x1000@T3）
次に、図６に示される１０行目のトレース情報に含まれるイベントの種別（event type）は、「mem」であり、イベントの種別がメモリアクセスであることを示しているから、ここでは、データレース検出部１２がデータレース検出処理を開始する。データレース検出部１２の競合アクセス検出部１２Ａは、第２イベント情報として、スレッドのＩＤ（TID）「Ｔ３」、イベント名（event_name）「read」及びメモリアドレス（mem_addr）「0x1000」を取得する。そして、競合アクセス検出部１２Ａは、メモリアドレス「0x1000」に関するアドレス状態情報がアドレス状態情報テーブル２３に既に存在しているか否かを判断する（図１５のステップＳ３０）。ここでは、当該エントリがアドレス状態情報テーブル２３に存在しており（ステップＳ３０：ＹＥＳ）、イベント情報に含まれるイベント名（event_name）が「Read」であるため（ステップＳ３１：ＲＤ）、競合アクセス検出部１２Ａは、当該アドレス状態情報のLast Writeに対して競合判断処理を行う。
【００６４】
競合アクセス検出部１２Ａは、TID-vec_ID対応表２１を参照し、イベント情報に含まれるTID「Ｔ３」に対応するvec_ID「２」を取得する（図１６のステップＳ４０）。次いで、競合アクセス検出部１２Ａは、ステップＳ４０で取得したvec_ID「２」と、アドレス状態情報のLast Writeのvec_ID「３」とが同じであるか否かを判断する(ステップＳ４１)。当該判断結果は否定的となるから、競合アクセス検出部１２Ａは、順序関係情報テーブル２２を参照し、ステップＳ４０で取得したvec_ID「２」に対応するvec_value(1,0,1)を取得する（ステップＳ４２）。そして、競合アクセス検出部１２Ａは、ステップＳ４２で取得したvec_value(1,0,1)の中から、アドレス状態情報のLastWriteのvec_ID「３」と同数番目(3番目)の要素の値「１」を取得してelem_val_sucとする（ステップＳ４３）。また、競合アクセス検出部１２Ａは、アドレス状態情報のLastWriteのelem_value「１」で示される値をelem_val_preとする（ステップＳ４４）。次いで、競合アクセス検出部１２Ａは、elem_val_suc「１」がelem_val_pre「１」以下であるか否かを判断する（ステップＳ４５）。ここでは、elem_val_sucがelem_val_pre以下であるため（ステップＳ４５：ＮＯ）、競合アクセス検出部１２Ａは、競合アクセスの発生をマークする（ステップＳ４６）。
【００６５】
そして、アドレス状態情報を更新処理に移る。アドレス状態更新部１２Ｂは、TID-vec_ID対応表２１を参照して、第２イベント情報に含まれるTID「Ｔ３」に対応するvec_ID「２」を取得し、この値「２」をメモリアドレス「0x1000」に関するアドレス状態情報のLastReadのvec_IDとして記憶する(図１７のステップＳ５４)。さらに、アドレス状態更新部１２Ｂは、順序関係情報テーブル２２に記憶されている順序関係情報のvec_ID「２」に対応するvec_value(1,0,1)を参照し、vec_ID「２」と同数番目（２番目）の要素の値「０」を求め、この値「０」をメモリアドレス「0x1000」に関するエントリのLast Readの項目のelem_valueとして記憶する。（ステップＳ５５）。
【００６６】
以下、図６に示される１１行目以降のトレース情報についても同様にして処理を行う。
【００６７】
以上のような構成によって、順序関係情報においてスレッド間の順序関係を表現するためのベクターの要素数（vec_valueの要素数）を、プロセッサの個数と同数に制限し、要素同士がプロセッサ毎に排他的となるよう、vec_IDをスレッドに対応つけるようにする。これによってスレッド間の順序関係を解析するために必要なメモリの容量を節約することができるようになるとともに、要素の再利用による情報の欠落を回避することができ、各要素を比較しながら行うベクターの更新作業のための計算量も削減することができるようになる。
【００６８】
また本実施の形態において得られるスレッド間の順序関係によれば、実際に発生した同期関係に加えて、さらに同じvec_IDに割り当てられたスレッド間に同期関係が擬似的に存在したように見えるだけなので、従来技術によって得られる順序関係によって検出されるデータレースの一部または全部が検出されることになり、誤検出が発生することはない。
【００６９】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【００７０】
＜変形例１＞
上述の実施の形態の解析システムＳＹＭで実行される各種プログラムは、外部記憶装置Ｍ１１，Ｍ２１に記憶されていても良いし、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記憶媒体に記憶して提供するように構成してもよい。さらに、当該プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。
【００７１】
また、上述の実施の形態においては、順序関係解析プログラムとデータレース検出プログラムとを別個のプログラムとして取り扱ったが、これらを一体的なプログラムとして構成するようにしても良い。
【００７２】
＜変形例２＞
また、上述の実施の形態においては、トレース収集部１０の機能は、システム１で所定のプログラムの実行により実現される構成としたが、たとえばシステム１とシステム２と分散して実行される形態であっても良い。またトレース収集部１０の一部または全部の機能をハードウェアにより実装しても良い。同様に、順序情報更新部１１及びデータレース検出部１２の各機能についても同様に、システム１とシステム２と分散して実行される形態であっても良いし、一部または全部の機能をハードウェアにより実装しても良い。
【００７３】
また、上述の実施の形態においては、解析システムＳＹＭをシステム１とシステム２とに分離した構成としたが、これらが一体的に構成されたものを解析システムＳＹＭとするようにしても良い。この場合、トレース収集部１０、順序情報更新部１１及びデータレース検出部１２の各機能を少なくとも２以上組み合わせて実現させるように構成しても良い。
【００７４】
＜変形例３＞
上述の実施の形態においては、トレース情報を一つのシーケンシャルなデータで表現したが、これに限らず、たとえばシステム１のプロセッサ毎に発生したイベントをトレース情報として記憶したり、同期処理に関する情報とメモリアクセスに関する情報とを分離して記憶したりしても構わない。
【００７５】
また、上述の実施の形態においては、トレース情報のうち、順序情報更新部１１が第１イベント情報を取得し、データレース検出部１２が第２イベント情報を取得するように構成したが、これらの各部はトレース情報自体を取得するようにしても良いし、これらの各部が取得する情報の構成を同じにしても良い。
【００７６】
＜変形例４＞
上述の実施の形態においては、スケジューラとして機能するプロセッサＰ１０をシステム１に設けたが、これを設けるのではなく、プロセッサＰ１１〜Ｐ１３の少なくとも１つが上述のスケジュール管理プログラムを実行することにより、スケジューラとしての機能も実現させるようにしても良い。また、スケジューラとしての機能をオペレーションシステムに組み込み、これを実行することにより当該機能を実現させるようにしても良い。
【００７７】
＜変形例５＞
上述の実施の形態においては、同期対応表１１Ｃ、トレース情報ＤＢ２０、TID-vec_ID対応表２１、順序関係情報テーブル２２及びアドレス状態情報テーブル２３のうち少なくとも２つ以上は同じ記憶手段に記憶されても良いし、各々別の記憶手段に記憶されても良い。
【００７８】
＜変形例６：PIDからvec_IDへのマッピングを1:Nにする＞
上述の実施の形態においては、vec_IDの個数を、マルチスレッドプログラムを実行可能なプロセッサ数に限定した、即ち、プロセッサ数の１倍に限定した。しかし、これに限らず、vec_IDの個数をこのプロセッサ数のＮ倍（Ｎ：１以上の整数）にするように構成しても良い。図２１は、この場合における順序情報更新処理の手順を示すフローチャートである。同図における順序情報更新処理の手順では、vec_IDを選択する手順が上述の図１４に示した順序情報更新処理の手順と以下のように異なる。図１４のステップＳ１２の代わりに、要素番号決定部１１Ａは、第１イベント情報に含まれるPIDを用いて、スレッドに割り当てるvec_IDの候補を設定する（ステップＳ１２Ａ）。具体的には、要素番号決定部１１Ａは、（PID×N）〜（PID×(N+1)−１）までのN個の値を、当該スレッドに割り当て可能なvec_IDの候補とする。そして、要素番号決定部１１Ａは、vec_IDの候補のうち値の小さいものからラウンドロビンにvec_IDを選択する（ステップＳ１２Ｂ）。例えば選択は以下のようになる。
・ある実行可能プロセッサに１番目に割り当てられたスレッドに対して、このプロセッサのＩＤ(PID)×Nをvec_IDとして選択する。
・ある実行可能プロセッサに２番目に割り当てられたスレッドに対して、このプロセッサのＩＤ(PID)×N＋１をvec_IDとして選択する。
・ある実行可能プロセッサにN番目に割り当てられたスレッドに対して、このプロセッサのＩＤ(PID)×Nをvec_IDとして選択する。
【００７９】
図２２〜２４は、「Ｎ=２」としたときに、図６で示したトレース情報に基づいた、順序関係情報テーブル２２、TID-vec_ID対応表２１及びアドレス状態情報テーブル２３の更新状態を各々示す図である。これらの結果において、最後に発生したイベント「WR 0x1000@T4」に対して、図１５に示したデータレース検出処理の結果、データレースの発生（Race with WR）が検出される。一方、「Ｎ=１」である第１の実施の形態においては、図２０に示したように、イベント「WR 0x1000@T4」に対してはデータレースの発生は検出されない。
【００８０】
即ち、以上のような構成によれば、Ｎの値の増加に伴い、検出可能なデータレースを増加させることが可能となる。またこのようにＮの値を増やしても順序関係情報テーブル２２において各スレッドの順序関係を表現するためのベクターの要素数は、プロセッサの個数とＮの値によって制限され、スレッド数によらない。このため、メモリの容量を節約することができるようになるとともに、ベクターの更新作業のための計算量も削減することができる。また、本変形例の構成によっても、従来技術によって得られる順序関係によって検出されるデータレースの一部または全部が検出されることになり、誤検出が発生することはない。
【００８１】
なお本変形例においては、vec_IDの決定については、スレッドが実行されたプロセッサのＩＤ（PID）ごとにN個ずつの排他的なvec_IDの候補を用意してそれらをスレッドが実行されるたびにラウンドロビンに選択する方式としたが、実行されたPIDに応じてvec_IDを排他的に割り当てる方式であれば、これに限らない。例えば、PIDごとに異なる数のvec_IDの候補を割り当てる方式や、TIDを利用して候補の中からvec_IDを選択して決定する方式など様々な方式が考えられる。
【００８２】
＜変形例７：同じvec_ID間でもデータレースを検出＞
上述の実施の形態においては、同じvec_IDに割り当てられたスレッド間でのデータレース検出は行わなかったが、同じvec_IDに割り当てられたスレッド間でもデータレースの検出を可能としても良い。この場合、順序関係情報テーブル２２においては、vec_IDごとのvec_valueとともに、vec_valueを更新した同期処理のイベントを発生させたスレッドのＩＤ（TID）を記憶する。図２５は、本変形例における順序関係情報のデータ構成を例示する図である。また、アドレス状態情報テーブル２３においては、Last Write及びLast Readに、vec_IDと、elem_valueとともにそれらの値を更新したメモリアクセスのイベントを発生させたスレッドのＩＤ（TID）を記憶する。図２６は、本変形例におけるアドレス状態情報のデータ構成を例示する図である。図２７は、本変形例における競合判断処理の手順を示すフローチャートである。同図に示されるデータレース検出処理の手順は、図１６に示した競合判断処理の手順と以下の点で異なる。図１６に示した競合判断処理では、ステップＳ４２で、競合アクセス検出部１２Ａは、ステップＳ４０で取得したvec_IDと、アドレス状態情報テーブル２３のLast Readの項目のvec_IDとが同じであるか否かを判断したが、図２７に示した競合判断処理では、競合アクセス検出部１２Ａは、イベント情報に含まれるTIDとアドレス状態情報テーブル２３のLast Readの項目に格納されたTIDとが同じであるか否かを判断する(ステップＳ４１Ａ)。そして、競合アクセス検出部１２Ａは、当該判断結果が肯定的である場合、競合アクセス検出処理を終了し、当該判断結果が否定的である場合、ステップＳ４２，Ｓ４４に進む。
【００８３】
図２８は、スレッドの実行例を示す図である。本変形例の構成によれば、同図に示されるようにスレッド実行がされた場合、図２６に示される競合判断処理では、スレッドT4で実行されたイベントであるメモリアクセス(WR 0x1000@T4)と、スレッドT2で実行されたイベントであるメモリアクセス（WR 0x1000@T2）との両方について、データレースの発生を検出することができる。これら２つのスレッドＴ２、Ｔ４は同じプロセッサＰ１３（PID=3）で実行されているため、上述の実施の形態においてはデータレースを検出することができなかった。
【００８４】
即ち、以上のように、順序関係情報及びアドレス状態情報においてスレッドのＩＤ（TID）を保持することで、同じvec_IDが割り当てられる異なるスレッドの各ベクターを判別することができ、このようなスレッド間のデータレースが検出できるようになる。また、本変形例の構成によっても、従来技術によって得られる順序関係によって検出されるデータレースの一部または全部が検出されることになり、誤検出が発生することはない。
【００８５】
＜変形例８＞
上述の実施の形態においては、順序関係を解析する対象の複数のプログラムとして、マルチスレッドプログラムに含まれる複数のスレッドを取り扱ったが、これに限らず、並列動作し一部のメモリ空間を共有するものであれば、プロセスであっても良いし、プログラム自体であっても良い。
【００８６】
＜変形例９＞
上述の実施の形態においては、順序関係情報を定義するデータフォーマットとして、プロセッサＰ１１〜Ｐ１３にその順に各々対応する要素を含む３次元のデータをvec_ID毎、即ち、プロセッサ毎に有するデータフォーマットを用いたが、プログラムの順序値を表す複数の要素を有するデータフォーマットであれば、これに限らない。
【図面の簡単な説明】
【００８７】
【図１】本実施の形態に係る解析システムＳＹＭの全体構成を示すブロック図である。
【図２】マルチスレッドプログラムの動作を概念的に示した図である。
【図３】スレッドの状態遷移を概念的に示した図である。
【図４】５つのスレッドが並列実行される様子を示した図である。
【図５】解析システムＳＹＭの機能的構成を示した図である。
【図６】トレース情報のデータ構成を例示する図である。
【図７】順序関係情報のデータ構成を例示する図である。
【図８】アドレス状態情報のデータ構成を例示する図である。
【図９】TID-vec_ID対応表のデータ構成を例示する図である。
【図１０】順序情報更新部１１の詳細な構成を示したブロック図である。
【図１１】同期対応表１１Ｃのデータ構成を例示する図である。
【図１２】データレース検出部１２の詳細な構成を示したブロック図である。
【図１３】解析システムＳＹＭが行う処理の概略的な手順を示すフローチャートである。
【図１４】順序情報更新処理の手順を示したフローチャートである。
【図１５】データレース検出処理の手順を示したフローチャートである。
【図１６】競合判断処理の手順を示すフローチャートである。
【図１７】アドレス状態情報を更新する処理の手順を示す図である。
【図１８】順序関係情報テーブル２２の更新状態を示す図である。
【図１９】TID-vec_ID対応表２１の更新状態を示す図である。
【図２０】アドレス状態情報テーブル２３の更新状態を示す図である。
【図２１】本実施の形態の一変形例に係る順序情報更新処理の手順を示すフローチャートである。
【図２２】順序関係情報テーブル２２の更新状態を示す図である。
【図２３】TID-vec_ID対応表２１の更新状態を示す図である。
【図２４】アドレス状態情報テーブル２３の更新状態を示す図である。
【図２５】本実施の形態の一変形例に係る順序関係情報のデータ構成を例示する図である。
【図２６】アドレス状態情報のデータ構成を例示する図である。
【図２７】競合判断処理の手順を示すフローチャートである。
【図２８】スレッドの実行例を示す図である。
【符号の説明】
【００８８】
１  システム
２  システム
３  バス
１０  トレース収集部（収集手段）
１１  順序情報更新部
１１Ａ  要素番号決定部（決定手段）
１１Ｂ  順序情報計算部(計算手段)
１１Ｃ  同期対応表
１２  データレース検出部（第１検出手段）
１２Ａ  競合アクセス検出部（第２検出手段）
１２Ｂ  アドレス状態更新部（更新手段）
２０  トレース情報ＤＢ
２１  TID-vec_ID対応表
２２  順序関係情報テーブル
２３  アドレス状態情報テーブル
Ｍ１０  メモリ
Ｍ１１  外部記憶装置
Ｍ２０  メモリ
Ｍ２１  外部記憶装置
Ｐ１０  プロセッサ
Ｐ１１  プロセッサ
Ｐ１２  プロセッサ
Ｐ１３  プロセッサ
Ｐ２０  プロセッサ
ＳＹＭ  解析システム
【図１】
0004937022.tif 000002
【図２】
0004937022.tif 000003
【図３】
0004937022.tif 000004
【図４】
0004937022.tif 000005
【図５】
0004937022.tif 000006
【図６】
0004937022.tif 000007
【図７】
0004937022.tif 000008
【図８】
0004937022.tif 000009
【図９】
0004937022.tif 000010
【図１０】
0004937022.tif 000011
【図１１】
0004937022.tif 000012
【図１２】
0004937022.tif 000013
【図１３】
0004937022.tif 000014
【図１４】
0004937022.tif 000015
【図１５】
0004937022.tif 000016
【図１６】
0004937022.tif 000017
【図１７】
0004937022.tif 000018
【図１８】
0004937022.tif 000019
【図１９】
0004937022.tif 000020
【図２０】
0004937022.tif 000021
【図２１】
0004937022.tif 000022
【図２２】
0004937022.tif 000023
【図２３】
0004937022.tif 000024
【図２４】
0004937022.tif 000025
【図２５】
0004937022.tif 000026
【図２６】
0004937022.tif 000027
【図２７】
0004937022.tif 000028
【図２８】
0004937022.tif 000029