(57)【特許請求の範囲】
【請求項１】
データを処理するマルチスレッドを実行する複数のプロセッサと、
各スレッドが処理するデータ数に基づいて、前記複数のプロセッサがスレッドを実行すべき順序が満たすべき条件を決定すると共に複数のスレッドを複数のグループに分け、当該条件を満たすように、前記複数のグループのそれぞれのたかだか１つのスレッドの実行を開始させる手段と
を含むマルチプロセッサシステム。
【請求項２】
前記手段は、
前記スレッドがデータ処理を完了したときに、当該スレッドが属するグループ内にデータを未処理のスレッドがあった場合、当該未処理のスレッドの実行を開始させる
請求項１に記載のマルチプロセッサシステム。
【請求項３】
前記手段は、
前記スレッドがデータ処理を完了したときに、当該スレッドが属するグループ内にデータを未処理のスレッドがなかった場合、データが未処理の他のグループのスレッドの実行を開始させる
請求項１又は２に記載のマルチプロセッサシステム。
【請求項４】
前記手段は、
処理するデータ数が最も多いスレッドを含む第１のグループと、
それぞれが処理するデータ数の合計と第１のグループのスレッドが処理対象とするデータ数の差が所定条件を満足する値未満となる複数のスレッドを含む１又は２以上の第２のグループと、
第１のグループ又は第２のグループに属さないスレッドを含む第３のグループと
を形成する請求項１乃至３のいずれかに記載のマルチプロセッサシステム。
【請求項５】
前記第２のグループは、
処理するデータ数の合計が第１のグループのデータ数以上、かつ第１のグループのデータ数との差が当該第２のグループ内の１つのスレッドが処理するデータ数未満となる当該複数のスレッドを含む
請求項４に記載のマルチプロセッサシステム。
【請求項６】
各スレッドが処理するデータ数に基づいて、複数のプロセッサがスレッドを実行する順序が満たすべき条件を決定すると共に複数のスレッドを複数のグループに分け、
当該条件を満たすように、前記複数のグループのそれぞれのたかだか１つのスレッドの実行を前記複数のプロセッサに開始させる、
マルチスレッド処理方法。
【請求項７】
各スレッドが処理するデータ数に基づいて、複数のプロセッサがスレッドを実行する順序が満たすべき条件を決定すると共に複数のスレッドを複数のグループに分け、
当該条件を満たすように、前記複数のグループのそれぞれのたかだか１つのスレッドの実行を前記複数のプロセッサに開始させる手段としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマルチプロセッサシステム、マルチスレッド処理方法、及びプログラムに関する。
【背景技術】
【０００２】
マルチプロセッサシステムにおいては、マルチスレッドをスケジューリングして処理することによる高速化が行われている。このようなマルチプロセッサシステムの一例が特許文献１に記載されている。
【特許文献１】特開２００６−１５５４８０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
特許文献１に記載のマルチプロセッサシステムでは、マルチプロセッサが複数のデータをまとめて一回のトランザクションで処理し、コミット処理回数とスケジューリングコストを削減し高速化を図る場合に、以下のような問題が発生する。上述のマルチプロセッサシステムでは、一部のスレッドだけ処理するデータ数が多くなったときに、トランザクション全体の処理効率が低下する。
その理由は以下の通りである。マルチプロセッサが各プロセッサに対するスレッド処理割り当てを行う際、マルチプロセッサは、スレッドが処理するデータ数を予測できない。従って、マルチプロセッサが必ずしも処理効率のよい割り当てを行うとは限らない。例えば、マルチプロセッサが、多くのデータを処理しなければならないスレッドの処理を後回しにしてしまった場合、トランザクション全体の処理が遅くなることがある。
本発明の目的は、上述した課題を解決するマルチプロセッサシステム、マルチスレッド処理方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【０００４】
本発明のマルチプロセッサシステムは、データを処理するマルチスレッドを実行する複数のプロセッサと、各スレッドが処理するデータ数に基づいて、前記複数のプロセッサがスレッドを実行する順序が満たすべき条件を決定し、当該条件を満たすように各スレッドの実行を開始させる手段とを含む。
本発明のマルチスレッド処理方法は、各スレッドが処理するデータ数に基づいて、複数のプロセッサがスレッドを実行する順序が満たすべき条件を決定し、当該条件を満たすように各スレッドの実行を複数のプロセッサに開始させる。
本発明のプログラムは、各スレッドが処理するデータ数に基づいて、複数のプロセッサがスレッドを実行する順序が満たすべき条件を決定し、当該条件を満たすように各スレッドの実行を前記複数のプロセッサに開始させる手段としてコンピュータを機能させる。
【発明の効果】
【０００５】
本発明は、処理するデータ数が一部のスレッドだけ多くなったときにも、トランザクション全体の処理効率が低下しにくいという効果を奏する。
【図面の簡単な説明】
【０００６】
【図１】マルチプロセッサシステム００１の構成を示す図である。
【図２Ａ】第１の実施の形態のデータ処理制御部ＣＴ２００の構成を示す図である。
【図２Ｂ】第２の実施の形態のデータ処理制御部ＣＴ２００の構成を示す図である。
【図３】トランザクション処理の例を示した図である。
【図４】マルチプロセッサシステム００１のハードウェア構成を示した図である。
【図５】第１の実施の形態のマルチプロセッサシステム００１の構成を示した図である。
【図６】データ読み込み部ＲＤ２０１の動作を示すフローチャートである。
【図７】データ処理開始部ＦＳ２０２の動作を示すフローチャートである。
【図８】次データ処理開始部ＮＳ２０３の動作を示すフローチャートである。
【図９】データ数が均等な例を示した図である。
【図１０】データに偏りが発生した場合の例を示した図である。
【図１１】データの偏りが分散している例を示した図である。
【図１２】データに偏りが発生し、他のトランザクションの処理も行われた場合の例１を示す図である。
【図１３】データに偏りが発生し、他のトランザクションの処理も行われた場合の例２を示す図である。
【図１４】第２の実施の形態のマルチプロセッサシステム００１の構成を示した図である。
【図１５】データ処理開始部ＦＳ（２）２０５の動作を示すフローチャートである。
【符号の説明】
【０００７】
Ｍ［Ｉ］  振り分けメモリ
Ｐ［Ｉ］  プロセッサ
Ｔ［Ｉ］  スレッド
００１    マルチプロセッサシステム
１００    メインバス
１０１    メインメモリ
１０２    記録媒体
２００    データ処理制御部ＣＴ
２０１    データ読み込み部ＲＤ
２０２    データ処理開始部ＦＳ
２０３    次データ処理開始部ＮＳ
２０４    コミット部ＣＲ
２０５    データ処理開始部ＦＳ（２）
４００    最大処理量レジスタＭＸ
５００    処理量カウンタＰＣ
６００    データベース
【発明を実施するための最良の形態】
【０００８】
図１は、マルチプロセッサシステム００１の構成を示す図である。マルチプロセッサシステム００１は、プロセッサＰ１とプロセッサＰ２と、データ処理制御部ＣＴ２００とを含む。
プロセッサＰ１及びプロセッサＰ２は、データをマルチスレッドで処理する。
データ処理制御部ＣＴ２００は、データ処理開始部ＦＳ２０２を含む。データ処理開始部ＦＳ２０２は、各スレッドが処理するデータ数に基づいて、プロセッサＰ１及びＰ２が処理するスレッドの順番を制御する。
本発明は、処理するデータ数が一部のスレッドだけ多くなったときにも、トランザクション全体の処理効率が低下しにくいという効果を奏する。その理由は、データ処理開始部ＦＳ２０２が、各スレッドにより処理されるデータ数に基づいて、プロセッサＰ１及びＰ２が処理するスレッドの順番を制御するようにしたためである。
本発明の、第１の実施の形態の概要は以下の通りである。第１の実施の形態は、複数のスレッドをなるべく処理するデータ数が均等になるようにスレッドをグループ化して処理を行う。
図２Ａは、データ処理制御部ＣＴ２００の構成を示す図である。データ処理制御部ＣＴ２００は、データ処理開始部ＦＳ２０２を含む。
データ処理開始部ＦＳ２０２は、各スレッドにより処理されるデータ数に応じて、複数のスレッドを複数のグループに分け、複数のグループのそれぞれの１つのスレッドに当該スレッドの実行を開始させるためのデータ処理開始指示を出す。
第１の実施の形態は、処理するデータ数が一部のスレッドだけ多くなったときにも、トランザクション全体の処理効率が低下しにくいという効果を奏する。
その理由は、複数のスレッドをなるべく処理するデータ数が均等になるようにグループ化して処理を行っているためである。
効果の具体例は以下の通りである。
図３は、トランザクション処理の例を示した図である。（ａ）は、発明適用前のトランザクション処理時間が長い例の一つである。（ｂ）は、発明適用後のトランザクション処理時間の例の一つである。
（ｂ）において、データ処理開始部ＦＳ２０２は、スレッドにより処理されるデータ数が最も多いスレッドはＴ１であるため、Ｔ１（１４データ）を第１のグループに、Ｔ６〜Ｔ２を第２のグループ（１５データ）に割り当てる。第２のグループ（Ｔ６〜Ｔ２）のスレッドが処理対象とするデータ数の合計は１５データ数であり、第１のグループ（Ｔ１）のスレッドが処理対象とするデータ数である１４データ数とほぼ同じデータ数である。そして、データ処理開始部ＦＳ２０２は、第１のグループ及び第２のグループのいずれにも属さないスレッド（Ｔ８とＴ７）を第３のグループ（２データ）に割り当てる。
（ａ）の例は、（ｂ）の例より７データ分処理時間が長い。その理由は、以下の通りである。
（ａ）の例では、プロセッサＰ１は、スレッドＴ２とＴ８を処理した後、スレッドの処理を行わない。そのため、プロセッサＰ１は、このトランザクション処理に関しては遊んでいる状態である。一方、プロセッサＰ２は、スレッドＴ６〜Ｔ３、Ｔ７を処理した後、スレッドＴ１を処理している。
これに対し（ｂ）の例では、プロセッサＰ１は、スレッドＴ８の処理は行わないものの、スレッドＴ２だけでなく、（ａ）の例ではプロセッサＰ２により行われていたスレッドＴ６〜Ｔ３の処理を行う。これによりプロセッサＰ１の遊んでいる時間が短くなるため、（ｂ）のトランザクション処理時間は（ａ）より短くなる。
第２の実施の形態の概要は以下の通りである。第２の実施の形態は、処理するデータ数の多いスレッドを優先的に処理する。
図２Ｂは、データ処理制御部ＣＴ２００の構成を示す図である。データ処理開始部ＦＳ（２）２０５は、処理するデータ数が多いスレッドのスレッド優先度を高く設定する（Ｄ００３）。図１（ａ）に示すプロセッサＰ１，Ｐ２がスレッドを処理する場合、スレッド優先度の高いスレッド、即ち、処理するデータ数が多いスレッドから処理を行う。
第２の実施の形態も、処理するデータ数が一部のスレッドだけ多くなったときにも、トランザクション全体の処理効率が低下しにくいという効果を奏する。
その理由は、処理するデータ数の多いスレッドの優先度を高くして処理を行うため、処理するデータ数の多いスレッドの処理を後回しにしないからである。
以下は、第１の実施の形態についての詳細な説明である。
図４は、マルチプロセッサシステム００１のハードウェア構成を示した図である。
マルチプロセッサシステム００１は、プロセッサＰ［Ｉ］（Ｉ＝１〜ｍ）と、メインバス１００と、メインメモリ１０１とを含む。プロセッサＰ［Ｉ］は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）であり、プログラムを実行することにより、後述のマルチプロセッサシステム００１の機能を実現する。
マルチプロセッサシステム００１は、プログラムを格納したコンピュータ読み取り可能な記録媒体１０２の読み取り装置を備えていても良い。プログラムは、コンピュータ読み取り可能な記録媒体１０２からメインメモリ１０１にローディングされて実行される。
図５は、第１の実施の形態のマルチプロセッサシステム００１の構成を示した図である。図５に示した略語の意味は、
［ＣＴ：Ｃｏｎｔｒｏｌ  Ｔｈｒｅａｄ］
［ＲＤ：Ｒｅａｄ  Ｄａｔａ  ｄｅｖｉｃｅ］
［ＦＳ：Ｆｉｒｓｔ  Ｓｔａｒｔ  ｄｅｖｉｃｅ］
［ＮＳ：Ｎｅｘｔ  Ｓｔａｒｔ  ｄｅｖｉｃｅ］
［ＣＲ：Ｃｏｍｍｉｔ／Ｒｏｌｌｂａｃｋ  ｄｅｖｉｃｅ］
［Ｍ：ｓｏｒｔ  Ｍｅｍｏｒｙ］
［ＭＸ：ｒｅｇｉｓｔｅｒ  ｏｆ  ｔｈｅ  ＭａＸ  ｎｕｍｂｅｒ  ｏｆ  ｄａｔａ］
［ＰＣ：Ｐｒｏｃｅｓｓｅｄ  ｄａｔａ  Ｃｏｕｎｔｅｒ］である。
マルチプロセッサシステム００１は、プロセッサＰ［Ｉ］と、データ処理制御部ＣＴ２００と、振り分けメモリＭ［Ｉ］（Ｉ＝１〜ｎ）と、最大処理量レジスタＭＸ４００と、処理量カウンタＰＣ５００と、データベース６００とを含む。スレッドＴ［Ｉ］（Ｉ＝１〜ｎ）は、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ、図示せず）によって生成される。プロセッサＰ［Ｉ］が、割り当てられたスレッドＴ［Ｉ］を実行して対応するデータを処理し、トランザクション処理を行うことにより、マルチプロセッサシステム００１は、データベース６００を更新する。
例えば、図４に示したプロセッサＰ［Ｉ］のいずれかの１つが、プログラム制御の下でデータ処理制御部ＣＴ２００として機能する。データ処理制御部ＣＴ２００は、例えば、スレッドＴ［Ｉ］のプロセスとは別のプロセスで動作する。データ処理制御部ＣＴ２００の果たす機能の実現方法はこれに限らず、プロセッサＰ［Ｉ］とは別のハードウェアで実現する方法でもよい。
データ処理制御部ＣＴ２００は、データ読み込み部ＲＤ２０１と、データ処理開始部ＦＳ２０２と、次データ処理開始部ＮＳ２０３と、コミット部ＣＲ２０４とを含む。
振り分けメモリＭ［Ｉ］と、最大処理量レジスタＭＸ４００と、処理量カウンタＰＣ５００は、例えば、図４に示したメインメモリ１０１内に設けられる。
図５に示した各ブロックの機能は、図６から図８を用いて詳細に説明される。
図６は、データ読み込み部ＲＤ２０１の動作を示すフローチャートである。
データ処理制御部ＣＴ２００のデータ読み込み部ＲＤ２０１が、データベース６００のファイルからデータを取得し、そのデータを処理するスレッドＴ［Ｉ］に対応する振り分けメモリＭ［Ｉ］に保存する。データ読み込み部ＲＤ２０１は、この処理を一トランザクションで処理するデータ数分行い、各スレッドＴ［Ｉ］に割り当てられたデータ数の内、最も大きい値を最大処理量レジスタＭＸ４００に保存する。
具体的には、データ読み込み部ＲＤ２０１は、以下の動作を行う。
まず、データ読み込み部ＲＤ２０１は、データベース６００からデータを読み込む（Ａ００１）。ＯＳは、各プロセスが読み込むファイルの格納位置を一意に決めている。データ読み込み部ＲＤ２０１は、現在処理中のプロセスに対応するファイルが格納されている場所からデータを読み込む。
データ読み込み部ＲＤ２０１は、データを識別し、対応するスレッド用の振り分けメモリＭ［Ｉ］にデータを格納する（Ａ００２）。このデータは、対応するスレッドを特定する情報を含んでいる。データ読み込み部ＲＤ２０１は、この情報を基に、読み出したデータを振り分けメモリＭ［Ｉ］に格納する。
データ読み込み部ＲＤ２０１は、読み込んだデータ数が予定数を満たしたか判断する（Ａ００３）。ユーザは、予め、１トランザクションで処理するデータ数の上限値をマルチプロセッサシステム００１に入力する。データ数の上限値が予定数となる。
データ読み込み部ＲＤ２０１は、各スレッドに割り当てられたデータ数の内、最大データ数を最大処理量レジスタＭＸ４００に登録する（Ａ００４）。
図７は、データ処理開始部ＦＳ２０２の動作を示すフローチャートである。
データ処理開始部ＦＳ２０２は、各スレッドにより処理されるデータ数に応じて、複数のスレッドを複数のグループに分け、複数のグループのそれぞれの１つのスレッドにデータ処理開始指示を出す。具体的に、データ処理開始部ＦＳ２０２は、振り分けメモリＭ［Ｉ］に保存されたデータ数と、最大処理量レジスタＭＸ４００の値とを比較して、以下の条件でスレッドのグループ分けをする。
１．データ数が最大処理量レジスタＭＸ４００の値と等しいスレッド一つ（スレッドにより処理されるデータ数が最も多いスレッド）を第１のグループ
２．グループを形成していないスレッドの内、データ数の和が最大処理量レジスタＭＸ４００の値程度（例、データ数の和が最大処理量レジスタＭＸ４００の値を少し超える程度、（例、データ数の和が最大処理量レジスタＭＸ４００の値以上、かつ第１のグループのデータ数との差がこのグループ内の１つのスレッドが処理するデータ数未満））の複数のスレッドを第２のグループ
３．第１のグループ及び第２のグループのいずれにも属さないスレッド全てを第３のグループ
そして、データ処理開始部ＦＳ２０２は、各グループの内からそれぞれ一つのスレッドに対してデータ処理開始を指示する。
具体的には、データ処理開始部ＦＳ２０２は以下の処理を行う。
まず、データ処理開始部ＦＳ２０２は、処理量カウンタＰＣ５００をリセットする（Ｂ００１）。次に、データ処理開始部ＦＳ２０２は、変数Ｉを０とする（Ｂ００２）。次に、データ処理開始部ＦＳ２０２は、変数Ｓを０とする（Ｂ００３）。次に、データ処理開始部ＦＳ２０２は、Ｉに１を加算する（Ｂ００４）。次に、データ処理開始部ＦＳ２０２は、振り分けメモリＭ［Ｉ］のデータ数がＭＸと等しいか判断する（Ｂ００５）。振り分けメモリＭ［Ｉ］のデータ数がＭＸと等しい場合（Ｂ００５，Ｙｅｓ）、データ処理開始部ＦＳ２０２は、スレッドＴ［Ｉ］を一つのグループとする（Ｂ００６）。なお、データ処理開始部ＦＳ２０２は、スレッドＴ［Ｉ］を一つのグループにする際、例えば、スレッドＴ［Ｉ］の制御表にグループの識別番号を格納する。次に、データ処理開始部ＦＳ２０２は、スレッドＴ［Ｉ］に処理開始指示を行う（Ｂ００７）。
上述のＢ００５の処理で、振り分けメモリＭ［Ｉ］のデータ数がＭＸと等しくない場合（Ｂ００５，Ｎｏ）、データ処理開始部ＦＳ２０２は、Ｓに振り分けメモリＭ［Ｉ］のデータ数を加算する（Ｂ００９）。次に、データ処理開始部ＦＳ２０２は、Ｓ≧ＭＸか判断する（Ｂ０１０）。Ｓ≧ＭＸの場合（Ｂ０１０，Ｙｅｓ）、データ処理開始部ＦＳ２０２は、Ｓを０にする（Ｂ０１１）。次に、データ処理開始部ＦＳ２０２は、Ｉ番目までのスレッドの内、グループを形成していないものを一つのグループとする（Ｂ０１２）。なお、データ処理開始部ＦＳ２０２は、複数のスレッドＴ［Ｉ］を一つのグループにする際、例えば、当該複数のスレッドＴ［Ｉ］の制御表に同一のグループの識別番号等を格納する。次に、データ処理開始部は上述のＢ００７の処理を行う。Ｂ００７の処理が終わった場合、又は、Ｓ≧ＭＸでなかった場合（Ｂ０１０、Ｎｏ）、データ処理開始部ＦＳ２０２は、Ｉはｎと等しいか判断する（Ｂ００８）。
Ｉがｎと等しくない場合（Ｂ００８，Ｎｏ）、データ処理開始部ＦＳ２０２は、Ｂ００４の処理に移行する。逆に、Ｉがｎと等しい場合（Ｂ００８，Ｙｅｓ）、データ処理開始部ＦＳ２０２は、Ｓ＞０か判断する（Ｂ０１３）。Ｓ＞０の場合（Ｂ０１３，Ｙｅｓ）、データ処理開始部ＦＳ２０２は、グループを形成していないものを一つのグループとする（Ｂ０１４）。次に、データ処理開始部ＦＳ２０２は、スレッドＴ［Ｉ］に処理開始指示を行う（Ｂ０１５）。Ｓ＞０ではなかった場合（Ｂ０１３，Ｎｏ）、又は、Ｂ０１５の処理を終了した場合、データ処理開始部ＦＳ２０２は、図７のフローチャートに示した処理を終了する。
Ｂ００７とＢ０１５において、データ処理開始指示を受けた各スレッドＴ［Ｉ］は、空プロセッサが発生次第実行されて、割り当てられたデータを処理する。
図８は、次データ処理開始部ＮＳ２０３の動作を示すフローチャートである。
次データ処理開始部ＮＳ２０３は、あるスレッドがデータの処理を終えたときに処理が完了したデータ数を処理量カウンタＰＣ５００に加算する。そして、次データ処理開始部ＮＳ２０３は、スレッドがデータ処理を完了したときに、当該スレッドが属するグループ内にデータを未処理のスレッドがあった場合、当該未処理のスレッドにデータ処理開始指示を出す。逆に、スレッドがデータ処理を完了したときに、当該スレッドが属するグループ内にデータを未処理のスレッドがなかった場合、次データ処理開始部ＮＳ２０３は、データが未処理の他のグループのスレッドにデータ処理開始指示を出す。そして、次データ処理開始部ＮＳ２０３は、全てのスレッドの処理が完了するまで上記処理を繰り返す。
具体的には、次データ処理開始部ＮＳ２０３は以下の処理を行う。まず、次データ処理開始部ＮＳ２０３は、いずれかのスレッドの処理が完了したか判断する（Ｃ００１）。いずれかのスレッドの処理が完了した場合（Ｃ００１，Ｙｅｓ）、次データ処理開始部ＮＳ２０３は、スレッドが処理を完了したデータ数を処理量カウンタＰＣ５００に加算する（Ｃ００２）。次に、次データ処理開始部ＮＳ２０３は、同グループ中に未処理のスレッドが存在するか判断する（Ｃ００３）。同グループ中に未処理のスレッドが存在しなかった場合（Ｃ００３，Ｎｏ）、次データ処理開始部ＮＳ２０３は、処理量カウンタＰＣ５００の値が最大処理量レジスタＭＸ４００の値以上か判断する（Ｃ００４）。この判断は、第３のグループ等のスレッドが全て実行された場合でも、第１のグループのスレッド等、データ数の多いスレッドが完了するまでは、他のグループのスレッド開始を抑止するためのものである。この抑止により、データ数の多いスレッドの速やかな実行を図る。処理量カウンタＰＣ５００の値が最大処理量レジスタＭＸ４００の値以上であった場合（Ｃ００４，Ｙｅｓ）、次データ処理開始部ＮＳ２０３は、他のグループで未処理のスレッドが存在するか判断する（Ｃ００５）。他のグループで未処理のスレッドが存在する場合（Ｃ００５，Ｙｅｓ）、又は、同グループ中に未処理のスレッドが存在する場合（Ｃ００３，Ｙｅｓ）、次データ処理開始部ＮＳ２０３は、該当する未処理スレッドに処理開始を指示する（Ｃ００６）。
処理量カウンタＰＣ５００の値が最大処理量レジスタＭＸ４００の値以上ではなかった場合（Ｃ００４，Ｎｏ）、又は、他のグループで未処理のスレッドが存在しなかった場合（Ｃ００５，Ｎｏ）、又は、Ｃ００６の処理を完了した場合、以下の処理が行われる。
次データ処理開始部ＮＳ２０３は、全てのスレッドが処理を完了したか判断する（Ｃ００７）。全てのスレッドが処理を完了していなかった場合（Ｃ００７，Ｎｏ）、又は、Ｃ００１の処理で、いずれかのスレッドの処理が完了しなかった場合（Ｃ００１，Ｎｏ）、次データ処理開始部ＮＳ２０３は、Ｃ００１の処理に移行する。
図６、図７、図８に記載された処理を通してスレッドがデータを処理し、マルチプロセッサシステム００１はデータベース６００を更新する。全スレッドがデータの処理を完了したら、コミット部ＣＲ２０４がトランザクションのコミット処理を行う。データ処理制御部ＣＴ２００は、新しいデータを処理するために再び図６の処理を開始する。このとき、既に形成されたスレッドのグループはなくなり、マルチプロセッサシステム００１は処理するデータ数に従って新たなグループを形成する。
次に、実施例が図面を参照して詳細に説明される。プロセッサＰ［Ｉ］の数、スレッドの数、他の演算量、データ数の偏り方等によって本発明の効果の度合いは変化する。実施例は、
・２つのプロセッサＰ１とプロセッサＰ２
・１つのデータ処理制御部ＣＴ２００
・８つのスレッドＴ１−Ｔ８を前提としている。
実施例に於いて、他の演算量、データ数の偏り方は適宜変化する。
プロセッサが２つであるため、同時に演算処理ができるスレッドは２つである。プロセッサＰ１，Ｐ２がどのスレッドを処理するかはプロセッサＰ１，Ｐ２の状態に依存する。プロセッサＰ１，Ｐ２は、処理するスレッドが存在する場合は休まずに処理を行う。プロセッサＰ１，Ｐ２の内、１つのスレッドの処理を完了して空きができた方が、次のスレッドの処理を開始する。
プロセッサＰ１又はＰ２が１つのデータを処理するのにかかる時間はＴであるとする。データ読み込み部ＲＤ２０１の処理時間とコミット部ＣＲ２０４の処理時間はαであるとする。その他制御の時間はβであるとし、Ｔとαに比べて短いものとする。また、以下文中のＭＡＸ（Ａ，Ｂ）は、ＡとＢの内、大きい値を意味する。
図９は、データ数が均等な例を示した図である。
各スレッドに均等にデータが割り当てられた場合は、発明適用前と発明適用後で処理時間は変わらない。図９のように、１つのスレッドあたりのデータ数を４としたとき、プロセッサＰ１とプロセッサＰ２が他の演算に使われなかったとすると、発明適用前はトランザクションにかかる処理時間は１６Ｔ＋α＋βとなる。発明適用後は、各スレッドがそれぞれ１つずつグループを形成することになり、データ処理開始部ＦＳ２０２は全てのスレッドにデータ処理開始を指示する。よって、発明適用前と変わらず、トランザクションにかかる処理時間は１６Ｔ＋α＋βとなる。
図１０は、データに偏りが発生した場合の例を示した図である。
ある一つのスレッドに割り当てられたデータ数が他の全てのスレッドに割り当てられたそれに比べて多かった場合、プロセッサＰ１とプロセッサＰ２の処理割り当てによって１つのトランザクションにかかる時間は変化する。発明適用前に起こる最も処理時間がかかる場合に比べて、発明適用後は処理時間が短くなる。
図１０のように、１つのスレッドＴ１が２５データ、その他の７つのスレッドＴ２−Ｔ８がそれぞれ１データを処理するとする。プロセッサＰ１，Ｐ２が他の演算に使われなかったとすると、発明適用前のトランザクションにかかる処理時間は次の通りとなる。
（１）に示すように、トランザクション処理時間が最小となる１つの例は、２５データを処理するスレッドを１つのプロセッサＰ１が処理し、その他のスレッドＴ２−Ｔ８をもう一つのプロセッサＰ２が処理した場合である。トランザクションにかかる処理時間は（ＭＡＸ（２５Ｔ，７Ｔ）＋α＋β）＝２５Ｔ＋α＋βとなる。
（２）に示すように、トランザクション処理時間が遅延する１つの例は、２つのプロセッサＰ１，Ｐ２が、最初にデータ数１のスレッド６つを、それぞれスレッド３つずつ処理し、その後に残りのスレッドを処理した場合である。トランザクションにかかる処理時間は（３Ｔ＋ＭＡＸ（２５Ｔ，Ｔ）＋α＋β）＝２８Ｔ＋α＋βとなる。
（３）に示すように、発明適用後は、２５データを処理するスレッドが一グループとなり、残りのスレッドがもう１つのグループを形成する。２５データを処理するスレッドＴ１とデータ数１のスレッドの内の１つ（スレッドＴ８）が最初にデータ処理を開始し、データ数１のスレッドＴ８が処理を終えると、その後順番にスレッドが一つずつ処理を開始する。そのため、トランザクションにかかる処理時間は、（ＭＡＸ（２５Ｔ，７Ｔ）＋α＋β）＝２５Ｔ＋α＋βとなり、（２）の発明適用前の時間のかかる例に対して３Ｔ分短縮する。
図１１は、データの偏りが分散している例を示した図である。
データ数が多く割り当てられるスレッドが複数存在する場合も、本発明は、図１０に示した例と同じように効果を奏する。図１１に示すとおり、１つのスレッドＴ１が１４データを処理し、別の１つのスレッドＴ２が１２データを処理し、その他の６つのスレッドＴ３−Ｔ８が１データを処理する。プロセッサＰ１，Ｐ２は他の演算に使われないものとする。発明適用前のトランザクション処理時間は次の通りとなる。
（１）に示すように、トランザクション処理時間が最小となる１つの例は、以下の場合である。１つのプロセッサＰ１が、１４データを処理するスレッドＴ１とデータ数１のスレッドＴ８とスレッドＴ３の２つを処理する。そして、もう１つのプロセッサＰ２が、１２データを処理するスレッドＴ２とデータ数１のスレッドＴ４−Ｔ７の４つを処理する。それぞれの処理が終わった後、プロセッサＰ１，Ｐ２が残りのスレッドを処理する。トランザクションにかかる処理時間は、（ＭＡＸ（１４Ｔ＋Ｔｘ２，１２Ｔ＋Ｔｘ４）＋α＋β）＝１６Ｔ＋α＋βとなる。
（２）に示すように、トランザクション処理時間が長い場合の一つの例は、以下の場合である。１つのプロセッサＰ１が、最初にデータ数１２のスレッドＴ２を処理する。もう一つのプロセッサＰ２が、データ数１の６つのスレッドを処理した後、データ数１４のスレッドＴ１を処理する。トランザクションにかかる処理時間は、（ＭＡＸ（１２Ｔ，Ｔｘ６＋１４Ｔ）＋α＋β）＝２０Ｔ＋α＋βとなる。
これに対して、発明適用後は、データ処理開始部ＦＳ２０２が、データ数１４のスレッドＴ１からなる第１のグループと、データ数１２のスレッドＴ２とデータ数１のスレッドＴ３とスレッドＴ４とからなる第２のグループとを形成する。そして、データ処理開始部ＦＳ２０２が、残りのデータ数１のスレッドＴ５−Ｔ８からなる第３のグループを形成する。その結果、トランザクション処理時間は、次の通りとなる。
（３）に示すように、発明適用後のトランザクション処理時間が短い場合の一つの例では、２つのプロセッサＰ１，Ｐ２が、最初に第１のグループのスレッドＴ１と第２のグループのデータ数１の２つのスレッドＴ４，Ｔ３を処理する。プロセッサＰ２は、スレッドＴ４，Ｔ３の処理を終えると、データ数１２のスレッドＴ２を処理する。最後に、２つのプロセッサＰ１，Ｐ２が、グループ３の４つのスレッドＴ８−Ｔ５を処理する。トランザクションにかかる処理時間は、（ＭＡＸ（１４Ｔ＋Ｔｘ２，１２Ｔ＋Ｔｘ２＋Ｔｘ２）＋α＋β）＝１６Ｔ＋α＋βとなる。
（４）に示すように、発明適用後のトランザクション処理時間が長い場合の一つの例では、２つのプロセッサＰ１，Ｐ２が、最初に第３のグループのスレッドＴ８−Ｔ５と第２のグループのスレッドＴ４−２を処理する。プロセッサＰ２が、データ数の合計の少ない第３のグループのスレッドＴ８−Ｔ５を処理した後に第１のグループのスレッドを処理する。トランザクションにかかる処理時間は、（ＭＡＸ（１２Ｔ＋Ｔｘ２，Ｔｘ４＋１４Ｔ）＋α＋β）＝１８Ｔ＋α＋βとなる。本発明では、データ処理開始部ＦＳ２０２が、グループ１，２，３それぞれの一つのスレッドに対しほぼ同時にデータ処理開始指示を出す。プロセッサ１，２がどのグループのスレッドから処理を開始するかはプロセッサＰ１，Ｐ２の処理状況に依存する。そのため、処理するデータ数が最も多いスレッドＴ１（グループＴ１）の処理が、グループ２，３のスレッドの処理より後になる場合があり、このような場合は発明適用後に時間のかかるケース（４）となる。しかしこの場合でも、発明適用前の時間のかかるケース（２）と比較して、発明適用後に時間のかかるケース（４）は、２Ｔ分処理時間が短い。
図１２は、データに偏りが発生し、他のトランザクションの処理も行われた場合の例１を示す図である。
プロセッサＰ１，Ｐ２が、あるトランザクションＸを処理中に、他のトランザクションＹの処理が割り込んできたとする。トランザクションＸはデータ数の偏りがあり、トランザクションＹはデータ数の偏りがないとする。２つのプロセッサＰ１，Ｐ２がトランザクションＹを均等に処理すると、トランザクションＹに割り込まれた分、トランザクションＸの処理は遅れる。しかし、図１０の例と同様に、本発明は効果を得ることができる。
（１）は発明適用前のトランザクションＸの処理時間が長いパターンであり、（２）は発明適用前のトランザクションＸの処理時間が短いパターンである。（２）は発明適用後のパターンでもある。本発明は上述のグループ分けを行うため、発明適用後の実行順序は、（２）のパターンとなり、（１）のパターンにはならない。そして、（２）は、（１）より３Ｔ処理時間が短い。
図１３は、データに偏りが発生し、他のトランザクションの処理も行われた場合の例２を示す図である。
図１３の例では、トランザクションＸ、Ｙ両方にデータ数の偏りがあり、トランザクションＹが２つのプロセッサＰ１，Ｐ２の処理に割り込む。プロセッサＰ１，Ｐ２において、トランザクションＹが割り込んだ処理の分だけトランザクションの処理時間は長くなる。
（１）及び（２）に示した例では、発明適用前でも、プロセッサＰ１，Ｐ２は未使用時間を作ることなく両方のトランザクションＸ，Ｙを処理する。そのため、両方のトランザクションＸ，Ｙの処理時間は短い。
（３）及び（４）に示した例では、各トランザクションのスレッドのプロセッサＰ１，Ｐ２の割り当て方が（１）及び（２）と異なる。このため、プロセッサＰ１，Ｐ２は、未使用時間を作ってしまい、トランザクションＸ，Ｙの処理時間が長くなっている。即ち、（３）では、トランザクションＸのコミット処理の後、プロセッサＰ１の未使用時間がある。（４）では、トランザクションＹのコミット処理の後、プロセッサＰ２の未使用時間がある。
発明適用後、各トランザクションＸ，Ｙのスレッドは、第１のグループに属するスレッドＴ１と第２のグループに属するスレッドＴ８−Ｔ２のグループに分かれる（トランザクションＹの場合、「Ｔ」が「Ａ」に置換される）。第１のグループ及び第２のグループの１つのスレッドＴ１及びＴ８がプロセッサＰ１，Ｐ２の割り当てを要求する。第２のグループのスレッドは順にプロセッサＰ１，Ｐ２の割り当てを要求する。そのため、発明適用後の実行順序は、（２）（３）（４）ではなく（１）のパターンとなり、（３）（４）と比較してトランザクション処理時間が短いパターンとなる。
トランザクションＸ，Ｙ両方にデータ数の偏りがあり、トランザクションＹが片方のプロセッサＰ２だけに割り込む場合、発明適用前の実行順序は（５）のパターンとなる可能性がある。しかし、発明適用後は、プロセッサＰ１，Ｐ２が、トランザクションＹの最初からプロセッサの割り当てを要求しているスレッドＡ１の処理を（５）のように後回しにすることは無い。
（６）に示すように、プロセッサＰ１，Ｐ２は、スレッドＡ１をＡ７以下のスレッドよりも先に処理する。（６）示した場合では、第１のグループのスレッドＡ１と第２のグループのスレッドＡ８がほぼ同時期にプロセッサＰ１，Ｐ２の割り当て要求を出している。その時点では、第２のグループのスレッドＡ７は、Ａ８の処理が終わっていないので、プロセッサＰ１，Ｐ２に対し処理要求を出していない。そして、プロセッサＰ２が、まず、スレッドＡ８の処理を開始し、完了後、スレッドＡ１の処理を開始する。その後、行う処理がなくなったプロセッサＰ１が、スレッドＡ７以下のトランザクションＹを処理する。このようにして、（６）は、（５）より短い時間でトランザクションが完了する。
以下は、第１の実施の形態の変形例の説明である。
第１の実施の形態は、図１２、図１３でのトランザクションＹを他の処理（演算）に置き換えることにより、プロセッサＰ１，Ｐ２がトランザクション以外の他の処理を行う場合にも適用できる。その場合でも、図１２、図１３の説明の通り、第１の実施の形態は効果を得ることができる。
第１の実施の形態は、動作させるプロセッサＰ［Ｉ］の数を変更することも可能である。動作させるスレッドの数がプロセッサＰ［Ｉ］の数より多い場合に、第１の実施の形態は効果を奏する。
第１の実施の形態は、データ処理制御部ＣＴ２００の数を変更することも可能である。マルチプロセッサシステム００１は、データ処理制御部ＣＴ２００の数と同じ数のトランザクション処理を同時に行うことができる。
第１の実施の形態は、一データの処理に要する時間にバラツキがある場合にも適用できる。その場合、マルチプロセッサシステム００１は、処理の複雑さを相対的な数値で表し、データ数に掛け合わせたものを処理量として、上述の動作例のデータ数と置き換える。
以下は、第１の実施の形態の効果についての説明である。
第１の実施の形態は、処理するデータ数が一部のスレッドだけ多くなったときにも、トランザクション全体の処理効率が低下しにくいという効果を奏する。その理由は、複数のスレッドを、処理するデータ数がなるべく均等になるようにグループ化して処理を行っているためである。
マルチスレッド処理において、各スレッド間のリソース競合は処理性能に影響を及ぼす。この影響を避けるために、システムが、各スレッドがアクセスするテーブルを分割して備えると、各スレッドはリソース競合を避けることができる。そのためには、システムは、データの内容や種別によって各データを処理するスレッドを一意に決める必要がある。ここで、システムが、データの内容や種別によって各データを処理するスレッドを一意に決めると、一部のスレッドだけ処理するデータ数が多くなることがある。例えばこのような場合に、第１の実施の形態は、トランザクション全体の処理効率が下がりにくいという効果を奏する。
以下は、第２の実施の形態についての説明である。第２の実施の形態は、処理するデータ数の多いスレッドの優先度を高くして処理を行う。
図１４は、第２の実施の形態のマルチプロセッサシステム００１の構成を示した図である。図５と比較して、図１４は、データ処理開始部ＦＳ２０２をデータ処理開始部ＦＳ（２）２０５に変更し、次データ処理開始部ＮＳ２０３と処理量カウンタＰＣ５００とを削除している点が異なる。
図１５は、データ処理開始部ＦＳ（２）２０５の動作を示すフローチャートである。
まず、データ処理開始部ＦＳ（２）２０５は、変数Ｉを０とする（Ｄ００１）。次に、データ処理開始部ＦＳ（２）２０５は、Ｉに１を加算する（Ｄ００２）。次に、データ処理開始部ＦＳ（２）２０５は、スレッドＴ［Ｉ］のスレッド優先度を「振り分けメモリＭ［Ｉ］のデータ数÷最大処理量レジスタＭＸ４００の値ＭＸ×最大スレッド優先度」に設定する（Ｄ００３）。
即ち、データ処理開始部ＦＳ（２）２０５は、振り分けメモリＭ［Ｉ］のデータ数を最大処理量レジスタＭＸ４００の値ＭＸで除算することにより、振り分けメモリＭ［Ｉ］のデータ数を最大処理量レジスタＭＸ４００の値ＭＸで規格化する。そして、データ処理開始部ＦＳ（２）２０５は、規格化した値と最大スレッド優先度とを乗算する。
例えば、スレッド優先度の範囲を０〜１０とした場合、処理するデータ数の多いスレッドのスレッド優先度は最大スレッド優先度１０に近くなり、処理するデータ数の少ないスレッドのスレッド優先度は０に近くなる。
ここで、最小スレッド優先度が０はない場合、データ処理開始部ＦＳ（２）２０５は「振り分けメモリＭ［Ｉ］のデータ数÷最大処理量レジスタＭＸ４００の値ＭＸ×（最大スレッド優先度−最小スレッド優先度）＋最小スレッド優先度」をスレッド優先度とする。例えば、最小スレッド優先度が０ではなく１の場合、データ処理開始部ＦＳ（２）２０５は上記式で得られる値をスレッド優先度とすることにより、スレッド優先度の範囲を１〜１０とすることができる。
次に、データ処理開始部ＦＳ（２）２０５は、関数Ｉはｎと等しいか判定する（Ｄ００４）。関数Ｉがｎと等しい場合（Ｄ００４，Ｙｅｓ）、データ処理開始部ＦＳ（２）２０５は、全スレッドＴに対して処理開始指示を行う（Ｄ００５）。関数Ｉがｎと等しくない場合（Ｄ００４，Ｎｏ）、データ処理開始部ＦＳ（２）２０５は、Ｄ００２の処理へ移行する。
データ処理開始部ＦＳ（２）２０５によるＤ００５の処理の後、プロセッサＰ［Ｉ］は、全スレッドＴを処理する。このとき、プロセッサＰ［Ｉ］はスレッド優先度の高いスレッドから処理を行う。
第２の実施の形態も、処理するデータ数が一部のスレッドだけ多くなったときにも、トランザクション全体の処理効率が低下しにくいという効果を奏する。その理由は、データ処理開始部ＦＳ（２）２０５が、処理するデータ数の多いスレッドのスレッド優先度を高く設定し、プロセッサＰ［Ｉ］がスレッド優先度の高いスレッドから処理を行うためである。
以上、実施形態を参照して本願発明を説明した。しかし、本願発明は、上記の実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解しうる様々な変更をすることができる。
本発明は、オンライントランザクションにおけるホストコンピュータでのデータ処理や、バッチ処理におけるホストコンピュータでのデータ処理等に利用可能である。
この出願は、２００８年７月４日に出願された日本出願特願２００８−１７５４５６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
0005510322.tif 000002
【図２Ａ】
0005510322.tif 000003
【図２Ｂ】
0005510322.tif 000004
【図３】
0005510322.tif 000005
【図４】
0005510322.tif 000006
【図５】
0005510322.tif 000007
【図６】
0005510322.tif 000008
【図７】
0005510322.tif 000009
【図８】
0005510322.tif 000010
【図９】
0005510322.tif 000011
【図１０】
0005510322.tif 000012
【図１１】
0005510322.tif 000013
【図１２】
0005510322.tif 000014
【図１３】
0005510322.tif 000015
【図１４】
0005510322.tif 000016
【図１５】
0005510322.tif 000017