(57)【特許請求の範囲】
【請求項１】
ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて並列実行する実行手段と、
前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信手段と、
前記値と前記順番情報との組を格納するための格納手段と、
前記受信手段が前記組を受信した場合に、
受信された前記順番情報と前記格納手段に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納手段に上書きさせるか、上書きさせないかを制御する制御手段と、
前記実行手段による並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定手段と、
を備え、
前記制御手段は、
前記受信手段による受信があった場合に、
受信された前記順番情報が前記格納手段に格納された順番情報より後順を示しているときには、受信された前記値と前記順番情報との組を前記格納手段に上書きさせ、
受信された前記順番情報が前記格納手段に格納された順番情報より前順を示しているときには、受信された前記値と前記順番情報との組を前記格納手段に上書きさせない
ことを特徴とするマルチスレッド並列実行装置。
【請求項２】
前記ひとつのループ処理における繰り返し単位には、処理を途中で打ち切るためのブレークポイントが設定されており、
前記受信手段が受信する前記組は、前記値と前記順番情報とに加えて、前記ブレークポイントへ到達済みか未到達かを示すフラグを含み、
前記格納手段は、前記値と前記順番情報と前記フラグとを含む組を格納するためのものであり、
前記制御手段は、
前記受信手段により受信された前記組に含まれる前記順番情報と前記フラグを、前記格納手段に格納された前記順番情報と前記フラグとに参照して、前記上書きの制御を行う
ことを特徴とする請求項１に記載のマルチスレッド並列実行装置。
【請求項３】
前記制御手段は、
前記ひとつのループ処理を、逐次処理したと仮定した場合にブレークポイントへ最初に到達した繰り返し単位に対応する値が前記格納手段に格納されていれば、前記上書きを抑止する
ことを特徴とする請求項２に記載のマルチスレッド並列実行装置。
【請求項４】
前記ひとつのループ処理における繰り返し単位は、イタレーションであって、
前記順番情報は、イタレーションの順番を示すイタレーション番号である
ことを特徴とする請求項１に記載のマルチスレッド並列実行装置。
【請求項５】
前記受信手段、前記制御手段および前記確定手段は、前記実行手段による実行対象となる管理スレッドにより構成されている
ことを特徴とする請求項１に記載のマルチスレッド並列実行装置。
【請求項６】
前記実行手段が並列実行する繰り返し単位は複数の種類があり、
前記受信手段は、前記組に加えて前記繰り返し単位の種類を識別するための識別子を受信し、
前記格納手段は、繰り返し単位の種類を識別するための識別子に関連付けて前記組を格納し、
前記制御手段は、受信された識別子に関連付けられた組を対象に上書きの有無の制御を行う
ことを特徴とする請求項１に記載のマルチスレッド並列実行装置。
【請求項７】
前記実行手段は、
前記格納手段が格納している情報を無効化する命令、
前記組を管理用ハードウェアに送信する命令、
または、前記格納手段に格納された値を、実際の変数に反映する命令、
の少なくともいずれか１つの命令を発行することを特徴とする請求項１に記載のマルチスレッド並列実行装置。
【請求項８】
前記実行手段が並列実行する繰り返し単位は複数種類あり、
前記受信手段は、前記組に加えて前記繰り返し単位の種類を識別するための識別子を受信し、
前記格納手段は、繰り返し単位の種類を識別するための識別子に関連付けて前記組を格納し、
前記制御手段は、受信された識別子に関連付けられた組を対象に上書きの有無の制御を行うものであって、
前記実行手段が発行する命令は、実行対象となる識別子を含む
ことを特徴とする請求項７に記載のマルチスレッド並列実行装置。
【請求項９】
放送ストリームを受信する受信手段と、
受信された放送ストリームを復号する復号手段と、
復号された放送ストリームを再生する再生手段とを備え、
前記復号手段は、請求項１記載のマルチスレッド並列実行装置により構成される
ことを特徴とする放送ストリーム再生装置。
【請求項１０】
放送ストリームを受信する受信手段と、
受信された放送ストリームを再符号化する再符号化手段と、
再符号化された放送ストリームを蓄積する蓄積手段とを備え、
前記再符号化手段は、請求項１記載のマルチスレッド並列実行装置により構成される
ことを特徴とする放送ストリーム蓄積装置。
【請求項１１】
ストリームを蓄積する蓄積手段と、
蓄積されたストリームを復号する復号手段と、
復号されたストリームを再生する再生手段とを備え、
前記復号手段は、請求項１記載のマルチスレッド並列実行装置により構成されることを特徴とする蓄積ストリーム再生装置。
【請求項１２】
ストリームを蓄積する蓄積手段と、
蓄積されたストリームを再符号化する再符号化手段とを備え、
前記再符号化手段は、請求項１記載のマルチスレッド並列実行装置により構成されることを特徴とする蓄積ストリーム再符号化装置。
【請求項１３】
ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて並列実行する実行手段と、
前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信手段と、
前記値と前記順番情報との組を格納するための格納手段と、
前記受信手段が前記組を受信した場合に、
受信された前記順番情報と前記格納手段に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納手段に上書きさせるか、上書きさせないかを制御する制御手段と、
前記実行手段による並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定手段と、
を備え、
前記制御手段は、
前記受信手段による受信があった場合に、
受信された前記順番情報が前記格納手段に格納された順番情報より後順を示しているときには、受信された前記値と前記順番情報との組を前記格納手段に上書きさせ、
受信された前記順番情報が前記格納手段に格納された順番情報より前順を示しているときには、受信された前記値と前記順番情報との組を前記格納手段に上書きさせない
ることを特徴とする集積回路。
【請求項１４】
前記実行手段は、マルチスレッドプロセッサから構成される
ことを特徴とする請求項１３に記載の集積回路。
【請求項１５】
前記実行手段は、マルチコアプロセッサから構成される
ことを特徴とする請求項１３に記載の集積回路。
【請求項１６】
ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて実行手段に並列実行させる実行ステップと、
前記実行ステップにおいて前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信ステップと、
前記値と前記順番情報との組を格納手段に格納するための格納ステップと、
前記受信ステップが前記組を受信した場合に、
受信された前記順番情報と前記格納手段に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納手段に上書きさせるか、上書きさせないかを制御する制御ステップと、
前記実行ステップにおける並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定ステップと、
を含み、
前記制御ステップにおいて、
前記受信ステップによる受信があった場合に、
受信された前記順番情報が前記格納手段に格納された順番情報より後順を示しているときには、受信された前記値と前記順番情報との組を前記格納手段に上書きさせ、
受信された前記順番情報が前記格納手段に格納された順番情報より前順を示しているときには、受信された前記値と前記順番情報との組を前記格納手段に上書きさせない
ことを特徴とするマルチスレッド並列実行方法。
【請求項１７】
１つの処理スレッド上で動作しループ処理を含むソースプログラムをコンパイルするマルチスレッドコンパイラであって、
前記ループ処理における繰り返し単位が終了する毎に、実行の結果を示す値と当該繰り返し単位の順番を示す順番情報との組を送信する複数の処理スレッド用のプログラムと、
各処理スレッドから前記組を受信すると、当該組に含まれる順番情報と格納手段にすでに格納された順番情報とを比較して、受信した組に含まれる値と順番情報とを前記格納手段に上書きするか、上書きしないかを制御するデータ更新管理スレッド用のプログラムとを生成する
前記データ更新管理スレッド用のプログラムは、
各処理スレッドから前記組を受信した場合に、
受信した組に含まれる前記順番情報が前記格納手段に格納された順番情報より後順を示しているときには、受信した組に含まれる前記値と前記順番情報とを前記格納手段に上書きさせ、
受信した組に含まれる前記順番情報が前記格納手段に格納された順番情報より前順を示しているときには、受信した組に含まれる前記値と前記順番情報とを前記格納手段に上書きさせない
ことを特徴とするマルチスレッドコンパイラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ループ処理における繰り返し単位を複数のスレッドに分けて並列実行する技術に関する。
【背景技術】
【０００２】
あるひとつのループ処理を、複数のスレッドで分担して並列に処理する（マルチスレッド化する）に際しては、並列して処理した場合と逐次的に処理した場合の両場合で最終的な変数の値が同じ値になっている必要がある。これを「終値保証」と呼ぶ。【０００３】
このような終値保証を図る技術として、特許文献１，２の技術が知られている。【０００４】
特許文献２においては、あるループ処理を並列化するに際して、並列プロセス毎に領域を設ける。それから、各並列プロセスで定義される変数に、最終の繰り返しかどうかを示すコードを付加した後で、対応する領域に格納するようにする。【０００５】
そして、ループ処理に対するすべての並列プロセスの実行が完了すると、各領域に格納された変数に付加されたコードを手がかりとして、最終の繰り返しを担当するプロセスに対応する変数を特定する。続いて、特定した変数を取り出すことにより、変数の値を正しく参照できるとしている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３２６９６３９号公報
【特許文献２】特開平５−１８１６８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献２の手法を上述のループ処理のマルチスレッド化に適用しようとすると、スレッド毎に領域を設けて、各スレッドで扱う変数をこの領域に格納することとなる。【０００８】
このため、スレッド数に比例して必要なメモリ領域が増大するという問題がある。例えば、スレッド数が16個であれば、対応して16個分のメモリ領域が必要となる。【０００９】
本発明は、このような問題を解決するものであり、少量のメモリ領域で終値保証を実現可能なマルチスレッド並列実行装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明に係るマルチスレッド並列実行装置は、ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて並列実行する実行手段と、前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信手段と、前記値と前記順番情報との組を格納するための格納手段と、前記受信手段が前記組を受信した場合に、受信された前記順番情報と前記格納部に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納部に上書きさせるか、上書きさせないかを制御する制御手段と、前記実行手段による並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定手段と、を備えることを特徴とする。
【発明の効果】
【００１１】
本発明に係るマルチスレッド並列実行装置によれば、受信手段が値と順番情報との組を受信すると、格納手段へと受信した情報を上書きするかどうかを、受信された順番情報と格納された順番情報のそれぞれにより示される順番の先後に基づいて異ならせることができるので、適切に上書き制御して終値保証を実現できる。【００１２】
また、格納手段へは値と順番情報とを上書きすることで、マルチスレッド数が増えたとしても、上記格納手段のメモリ領域を増やさないようにすることができる。
【図面の簡単な説明】
【００１３】
【図１】マルチスレッド並列実行装置１０１の機能ブロック図
【図２】データ更新管理部１０３における処理を示すフローチャート
【図３】上書き要否の判定表
【図４】サンプルプログラム１と、このサンプルプログラム１を逐次的に実行した場合の処理結果を示す図
【図５】図４のサンプルプログラム１を、スレッド１，２を利用して並列実行した場合の各イタレーションの処理結果を示す図
【図６】イタレーション番号１→３→２→４の順番で実行された場合の、情報の流れと暫定データ格納部１０４の上書きの有無を説明する図の前半
【図７】イタレーション番号１→３→２→４の順番で実行された場合の、情報の流れと暫定データ格納部１０４の上書きの有無を説明する図の後半
【図８】（ａ）ブレークポイントが設定されているサンプルプログラム２を示す図、（ｂ）サンプルプログラム２を逐次的に実行した場合に、２番目のイタレーションにおいてブレークする様子を示すイメージ図、（ｃ）サンプルプログラム２を、スレッド１，２を利用して並列実行したときのイメージ図
【図９】マルチスレッド並列実行装置９０１の機能ブロック図
【図１０】データ更新管理部９０３における処理を示すフローチャート
【図１１】上書き要否の判定表
【図１２】マルチスレッド並列実行装置１２０１の機能ブロック図
【図１３】マルチスレッドコンパイラ１３０２の構成図
【図１４】処理スレッドプログラム生成部１３０４における処理を示すフローチャート
【図１５】集積回路１５０１の機能ブロック図
【図１６】放送ストリーム再生装置１６０１の機能ブロック図
【図１７】放送ストリーム蓄積装置１７０１の機能ブロック図
【図１８】蓄積ストリーム再生装置１８０１の機能ブロック図
【図１９】蓄積ストリーム再符号化装置１９０１の機能ブロック図
【図２０】変形例を示す図
【図２１】データ更新管理部１０３における処理を示すフローチャート
【図２２】マルチスレッド並列実行装置２２０１の機能ブロック図
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００１５】
（実施の形態１）
図１に示すように、マルチスレッド並列実行装置１０１は、マルチスレッド実行部１０２、データ更新管理部１０３、暫定データ格納部１０４、確定データ格納部１０５を備える。
【００１６】
マルチスレッド実行部１０２は、例えばＣＰＵから構成され、プログラムを実行する。
【００１７】
このプログラムは、ループ処理の繰り返し単位(イタレーションという)に相当する命令群を含んでいる。
【００１８】
マルチスレッド実行部１０２は、このイタレーションを複数のスレッドに分けて並列実行する。
【００１９】
この並列実行中、マルチスレッド実行部１０２は、各スレッドにおけるイタレーションが終了する毎に、イタレーションの実行結果を示す値と、実行したイタレーションがループ処理中で何番目（この順番は、ループ処理を仮に逐次実行した時における実行の順番と一致する。）であるかを示すイタレーション番号ｉ（ｔｈ）の組を受信部１１１へと送信する。
【００２０】
また並列実行終了時には、マルチスレッド実行部１０２は、終了判定部１１３宛に終了を示す終了情報を送る。
【００２１】
データ更新管理部１０３は、マルチスレッド実行部１０２による並列実行に応じて、暫定データ格納部１０４および確定データ格納部１０５のデータ更新を管理する。
【００２２】
データ更新管理部１０３は、受信部１１１、格納制御部１１２、終了判定部１１３、確定部１１４を備える。
【００２３】
受信部１１１は、マルチスレッド実行部１０２から送信されてくる、イタレーションの実行結果を示す値と、実行したイタレーションがループ処理中で何番目であるかを示すイタレーション番号ｉ（ｔｈ）との組を含む情報を受信する。
【００２４】
格納制御部１１２は、暫定データ格納部１０４のデータが無い場合には、受信部１１１が受信した値とイタレーション番号ｉ（ｔｈ）の組を暫定データ格納部１０４に格納する。また、格納制御部１１２は、暫定データ格納部１０４に対応する情報が既に格納されている場合には、後述する条件に従って、上書き格納するかしないかの制御を行う。
【００２５】
終了判定部１１３は、マルチスレッド実行部１０２から上述の終了情報を受信すると、並列実行の終了を判定する。そして終了を判定すると、確定部１１４にその旨を通知する。
【００２６】
なお、並列実行終了の判定は、これに限らず一般的な手法を用いることができる。
【００２７】
確定部１１４は、終了判定部１１３から終了判定した旨の通知を受け取ると、暫定データ格納部１０４に格納されている値を取りだして、確定データ格納部１０５へと反映する（コピーする）。
【００２８】
暫定データ格納部１０４は、マルチスレッド実行部１０２による並列実行中に、上述した値とイタレーション番号ｉとを格納するためのものである。
【００２９】
なお、本明細書では、暫定データ格納部１０４に格納されているイタレーション番号は”ｉ”と表記し、受信部１１１がマルチスレッド実行部１０２から受信したイタレーション番号を”ｉ（ｔｈ）”と区別して表記することとする。
【００３０】
確定データ格納部１０５は、上記ひとつのループ処理の実行結果としての値を格納するためのものである。
【００３１】
なお、両格納部１０４，１０５は例えばＲＡＭ（Random Access Memory）から構成される。
【００３２】
続いてマルチスレッド並列実行時におけるデータ更新管理部１０３の動作について図２を参照しながら説明する。
【００３３】
まず、格納制御部１１２は、暫定データ格納部１０４の内容クリアなどの初期設定を行う（Ｓ２１）。
【００３４】
その後、終了判定部１１３により並列実行の終了が判定される（Ｓ２２：Ｙｅｓ）までは、ステップＳ２３〜Ｓ２５の処理の繰り返しとなる。
【００３５】
受信部１１１が値とイタレーション番号ｉ（ｔｈ）とを受信すると（Ｓ２３：Ｙｅｓ）、格納制御部１１２は、暫定データ格納部１０４の値とイタレーション番号ｉの組を、受信した値とイタレーション番号ｉ（ｔｈ）とにより上書きする必要があるかどうかを判定する（Ｓ２４）。
【００３６】
この判定は、図３の表に沿ったものとなる。つまり、格納制御部１１２は、受信部１１１が受信したイタレーション番号ｉ（ｔｈ）と、暫定データ格納部１０４に格納されているイタレーション番号ｉとの大小関係に基づいて判定を行う。
【００３７】
すなわち、イタレーション番号ｉがイタレーション番号ｉ（ｔｈ）より大きければ（ｉ＞ｉ（ｔｈ））、格納制御部１１２は上書きが不要と判定する（Ｓ２４：Ｎｏ）。
【００３８】
これに対して、イタレーション番号ｉがイタレーション番号ｉ（ｔｈ）以下であれば（ｉ≦ｉ（ｔｈ））、格納制御部１１２は上書きが必要と判定する（Ｓ２４：Ｙｅｓ）。なお、並列実行の開始直後の場合など、暫定データ格納部１０４にデータが格納されていないときにも上書きが必要と判定する。
【００３９】
そして、格納制御部１１２は受信した値とイタレーション番号ｉ（ｔｈ）の組を暫定データ格納部１０４に上書きする（Ｓ２５）。
【００４０】
この上書きにより、格納制御部１１２では、イタレーションの順番が前順の値が消去され、イタレーションの順番がより後順の値が格納されることとなる。
【００４１】
終了判定部１１３により並列実行の終了が判定されると（Ｓ２２：Ｙｅｓ）、確定部１１４は、暫定データ格納部１０４の値を取りだして確定データ格納部１０５に反映する。
【００４２】
なお、暫定データ格納部１０４のデータが無効の場合(マルチスレッド実行部から１つもデータが送信されなかった場合や、送信されたデータがすべてnullだった場合など)には、確定部１１４は値の取り出しを行わないとしてもよい。
【００４３】
以上のようなフローによれば、並列実行中に繰り返されるステップＳ２３〜Ｓ２５により、暫定データ格納部１０４に格納される値は、イタレーションの実行結果として出力される複数の値の中で、順番が最も後ろの順番である値となる。
【００４４】
したがって、並列実行の終了後には、逐次的に処理した場合と、同じ値を確定データ格納部１０５に反映させることができ、終値保証を図ることができる。
【００４５】
しかも、暫定データ格納部１０４に格納するデータは、値とイタレーション番号のひとつの組だけで足り、スレッド毎にメモリ領域を用意する場合と比べて少ないメモリ領域とすることができる。
【００４６】
続いて、並列実行の具体例を挙げてさらに詳しく説明する。
【００４７】
図４は、サンプルプログラム１を示す図である。このサンプルプログラム１のソースコードは、ａ＝０，１，２，３と４回のイタレーションを行うことを示している。
【００４８】
このサンプルプログラム１を逐次的に実行した場合には、
（１）ａ＝０のとき、ｂ［ａ］＝ｂ［０］＝２＞−２よりｃ＝０＋１＝１
（２）ａ＝１のとき、ｂ［ａ］＝ｂ［１］＝１＞−２よりｃ＝１＋１＝２
（３）ａ＝２のとき、ｂ［ａ］＝ｂ［２］＝−１＞−２よりｃ＝２＋１＝３
（４）ａ＝３のとき、ｂ［ａ］＝ｂ［３］＝−２≦−２よりｃは更新されず
となるので、ｃ＝３となり、値”３”が処理結果となる。
【００４９】
このサンプルプログラム１の４回のイタレーションを、スレッド１（ａ＝０，１を担当）とスレッド２（ａ＝２，３を担当）とに２回分ずつ割り当てるとする。
【００５０】
図５に示すように、１番目のイタレーション（a=0）を終えたスレッド”１”は、値１とイタレーション番号”１”の組を、データ更新管理部１０３の受信部１１１へと送信する。
【００５１】
同様に、スレッド１，２は、各回のイタレーションが終了する度に、その処理結果の値とイタレーション番号の組を、データ更新管理部１０３の受信部１１１へ送信することとなる。
【００５２】
さて、図５の４回のイタレーションが、イタレーション番号1→3→2→4の順番で終了した場合を考える。
【００５３】
この場合における各種データの変遷のイメージを図６，図７に示す。
【００５４】
図６（ａ）に示すように、１番目のイタレーション終了時には、マルチスレッド実行部は、データ更新管理部１０３へとイタレーションの実行結果である値"１"と、イタレーション番号"１"とを送る。
【００５５】
この値"１"とイタレーション番号"１"をデータ更新管理部１０３の受信部１１１が受信すると、データ更新管理部１０３の格納制御部１１２は、暫定データ格納部１０４にデータが格納されていないので、上書き必要と判定して上書きを行う（図２，Ｓ２３：Ｙｅｓ，Ｓ２４：Ｙｅｓ，Ｓ２５）。
【００５６】
図６（ｂ）に示すように、３番目のイタレーション終了時には、データ更新管理部１０３の格納制御部１１２は、暫定データ格納部１０４に格納されたイタレーション番号”１”は、受信部１１１が受信したイタレーション番号”３”以下であるので上書き必要と判定して上書きを行う（Ｓ２３：Ｙｅｓ，Ｓ２４：Ｙｅｓ，Ｓ２５）。
【００５７】
図７（ｃ）に示すように、２番目のイタレーション終了時には、データ更新管理部１０３の格納制御部１１２は、暫定データ格納部１０４に格納されたイタレーション番号”３”は、受信部１１１が受信したイタレーション番号”２”より大きいので上書き不要と判定する（Ｓ２３：Ｙｅｓ，Ｓ２４：Ｎｏ）。そして、格納制御部１１２は、受信部１１１が受信した値”２”とイタレーション番号”２”を破棄する。
【００５８】
図７（ｄ）に示すように、４番目のイタレーション終了時には、データ更新管理部１０３の受信部１１１が受信した値は”null”と空であるので格納制御部１１２は上書き不要と判定する（Ｓ２３：Ｙｅｓ，Ｓ２４：Ｎｏ）。そして、格納制御部１１２は、受信部１１１が受信した値” null”とイタレーション番号”４”を破棄する。
【００５９】
図７（ｅ）に示すように、すべてのイタレーションが終了して、マルチスレッド実行部１０２から並列実行の終了を示す終了情報が送信され、データ更新部１０３の終了判定部１１３がこの終了情報を受信すると（Ｓ２２：Ｙｅｓ）、確定部１１４は、暫定データ格納部１０４に格納された値”３”を取得して、確定データ格納部１０５へ格納する（Ｓ２６）。
【００６０】
このように確定データ格納部１０５に格納された値”３”は、逐次的に処理したときの処理結果の値”３”（図４参照）と一致しており終値保証が実現されていることがわかる。
（実施の形態２）
実施の形態２は、ループ処理における繰り返し単位に、処理を途中で打ち切るためのブレークポイントが設定されている場合にも終値保証を図ろうとするものである。
【００６１】
このようにブレークポイントが設定されている場合には、逐次的に実行するときと並列的に実行するときとで実行の態様が異なってくるので、終値保証を実現するためにはさらなる工夫が必要である。具体的に図８を用いて説明する。
【００６２】
図８（ａ）に示すサンプルプログラム２には、４回のイタレーションを含むループ処理が記述されている。
【００６３】
このプログラムを逐次的に実行することを考える。この実行において、２番目のイタレーションでブレークポイントに到達したとすると、３番目，４番目のイタレーションは実行しないこととなる（図８（ｂ））。
【００６４】
ここで、このサンプルプログラム２の４回のイタレーションを、図８（ｃ）に示すように、スレッド１とスレッド２とに２回分ずつ割り当てるとする。
【００６５】
上述したように、逐次的に実行した場合には、３番目，４番目のイタレーションは実行しないので、並列実行の場合にも、３番目，４番目のイタレーションの処理結果を一連の処理の最終的な値としては反映しないようにする必要がある。
【００６６】
そこで、本実施の形態２では、ブレークポイントに到達したかどうかを示すブレークフラグ（到達時にはＯＮ、未到達時にはＯＦＦとなるフラグである）を利用することで、終値保証の実現を図る。
【００６７】
図９に示すように、マルチスレッド並列実行装置９０１は、マルチスレッド実行部９０２、データ更新管理部９０３、暫定データ格納部９０４を備える。
【００６８】
マルチスレッド実行部９０２は、各スレッドにおけるイタレーションが終了する毎に、イタレーションの実行結果を示す値、実行したイタレーションがループ処理中で何番目であるかを示すイタレーション番号ｉ（ｔｈ）、およびブレークポイントに到達したかどうかを示すブレークフラグの組を受信部９１１へと送信する。他の機能はマルチスレッド実行部１０２（図１）と同様である。
【００６９】
データ更新管理部９０３の格納制御部９１２は、受信部９１１が受信した、値とイタレーション番号ｉ（ｔｈ）とブレークフラグの三者の組に基づいて、上書き格納するかしないかの制御を行う。
【００７０】
暫定データ格納部９０４は、マルチスレッド実行部９０２による並列実行中に、値とイタレーション番号ｉとブレークフラグの三者の組を格納するためのものである。
【００７１】
図９のその他の機能ブロックは、図１を用いて説明した機能ブロックと同様なので説明を省略する。
【００７２】
続いて、マルチスレッド並列実行時におけるデータ更新管理部９０３の動作について図１０を参照しながら説明する。
【００７３】
図１０において、図２と同じ番号を付したステップＳ２１〜Ｓ２２，Ｓ２６は、図２と同様のため説明を省略する。
【００７４】
特に、受信部９１１が値とイタレーション番号ｉ（ｔｈ）とブレークフラグの組を受信すると（Ｓ１０３：Ｙｅｓ）、格納制御部９１２は、暫定データ格納部９０４の値とイタレーション番号ｉとブレークフラグとを、受信した値とイタレーション番号ｉ（ｔｈ）とブレークフラグとにより上書きする必要があるかどうかを判定する（Ｓ１０４）。
【００７５】
この判定は、図１１の表に沿ったものとなる。
【００７６】
図１１の表に示すように、受信部９１１が受信したブレークフラグのＯＮ／ＯＦＦ、暫定データ格納部９０４に格納されたブレークフラグのＯＮ／ＯＦＦ、イタレーション番号の大小関係の３つの要素に基づいて、格納制御部９１２は上書きするか上書きしないかを判定する。
【００７７】
以下、図１１の表中、Ｌ１〜Ｌ６の各行において、上書きの有無を異ならせている理由について簡単に説明する。
【００７８】
Ｌ１〜Ｌ２の行は、実施の形態１と同様に、よりイタレーション番号が後順の値を暫定データ格納部９０４に格納することをねらいとしている。
【００７９】
Ｌ３の行は、暫定データ格納部９０４にはブレークしたときの値が格納済みであるので上書きしないとしている。
【００８０】
Ｌ４の行は、受信部９１１が受信した値が、ブレークしたときの値であるので、上書きを行うとしている。
【００８１】
Ｌ５，Ｌ６の行は、複数のイタレーションの中で、２以上のイタレーションにおいてブレークポイントに到達した場合である。このとき、暫定データ格納部１０４には、ブレークポイントへ最初（逐次処理したと仮定した場合の順番において最初）に到達したイタレーションに対応する値を残す必要がある。
【００８２】
従ってＬ５の行では、受信部９１１が受信したイタレーション番号ｉ（ｔｈ）が、暫定データ格納部９０４に格納されたイタレーション番号ｉより前順であれば、上書きを行うとする。Ｌ６の行はＬ５の行の反対となっている。
【００８３】
格納制御部９１２は、図１１の表に従って、上書きが必要と判定すると（Ｓ１０４：Ｙｅｓ）、受信した値とイタレーション番号ｉ（ｔｈ）とブレークフラグの組を暫定データ格納部９０４に上書きする（Ｓ１０５）。
【００８４】
その後、終了判定部１１３により並列実行の終了が判定される（Ｓ２２：Ｙｅｓ）までは、ステップＳ１０３，Ｓ１０４，Ｓ１０５の処理の繰り返しとなる。
【００８５】
そして、終了判定部１１３により並列実行の終了が判定されると（Ｓ２２：Ｙｅｓ）、確定部１１４は、暫定データ格納部９０４に格納された値を確定データ格納部１０５へ反映する（Ｓ２６）。
【００８６】
このとき、暫定データ格納部９０４に格納されている値は、逐次処理したと仮定した場合の順番において、ブレークポイントへ最初に到達したイタレーションに対応する値が格納されているので、終値保証を実現することができる。
（実施の形態３）
実施の形態３は、実施の形態１のデータ更新管理部１０３を、マルチスレッド実行部内の管理スレッドとして構成するものである。
【００８７】
図１２に示すように、マルチスレッド並列実行装置１２０１は、マルチスレッド実行部１２０２を備える。このマルチスレッド実行部１２０２は、ループ処理のイタレーションを分担して処理する処理スレッド１２０２ａ，１２０２ｂと、データ更新管理スレッド１２０３とを含む。
【００８８】
データ更新管理スレッド１２０３は、データ更新管理部１０３（図１）と同等の機能を備えている。
【００８９】
つまり、データ更新管理スレッド１２０３は次の（１）〜（４）の機能を備える。
【００９０】
（１）処理スレッド１２０２ａ，１２０２ｂからイタレーションの実行結果を示す値と、実行したイタレーションがループ処理中で何番目であるかを示すイタレーション番号ｉ（ｔｈ）との組を含む情報を受信する機能（図１：受信部１１１に対応する機能）。
【００９１】
（２）受信した情報を基に、暫定データ格納部１０４に上書き格納するかしないかの制御を行う機能（図１：格納制御部１１２に対応する機能）。
【００９２】
（３）処理スレッド１２０２ａ，１２０２ｂから並列実行の終了を示す終了情報を受信すると、並列実行の終了を判定する機能（図１：終了判定部１１３に対応する機能）。
【００９３】
（４）並列実行の終了を判定すると、暫定データ格納部１０４に格納されている値を取りだして、確定データ格納部１０５へと反映する機能（図１：確定部１１４に対応する機能）。
【００９４】
なお、データ更新管理スレッド１２０３に、実施の形態２で説明したデータ更新管理部９０３（図９）の機能を備えるように構成しても構わない。
（実施の形態４）
実施の形態４では、ソースプログラムから処理スレッドやデータ更新管理スレッド向けのプログラムを生成するマルチスレッドコンパイラについて説明する。
【００９５】
図１３は、マルチスレッドコンパイラ１３０２の構成図である。
【００９６】
図１３において、マルチスレッドコンパイラ１３０２は、ソースプログラム１３０１を入力とし、処理スレッドプログラム１３１０、データ更新管理スレッドプログラム１３１１を生成する。
【００９７】
前処理部１３０３は、ソースプログラム１３０１に対して、ループ最適化などの前処理を実行する。
【００９８】
処理スレッドプログラム生成部１３０４は、並列処理可能なループ処理およびループ内で複数の処理スレッドから代入される変数を導出し、データ更新管理スレッドによる管理対象となる管理対象変数リスト１３０５および並列化処理とデータ更新管理スレッドへの通知処理を付加した処理スレッドプログラムの中間コード１３０６を生成する。
【００９９】
データ更新管理スレッドプログラム生成部１３０７は、管理対象変数リスト１３０５の各変数に対して、図２に示すフローチャートの動作を行うための、データ更新管理スレッドプログラムの中間コード１３０８を生成する。
【０１００】
後処理部１３０９は、処理スレッドプログラムの中間コード１３０６およびデータ更新管理スレッドプログラムの中間コード１３０８に対して、コード変換などの後処理を実行する。
【０１０１】
図１４は、処理スレッドプログラム生成部１３０４のフローチャートである。
【０１０２】
図１４において、処理スレッドプログラム生成部はまず、未解析のループ処理があるかを判定する（Ｓ１４０１）。
【０１０３】
未解析のループ処理がない場合（Ｓ１４０１：Ｎｏ）、処理を終了する。
【０１０４】
未解析のループ処理がある場合（Ｓ１４０１：Ｙｅｓ）、このループのイタレーション間に依存があるかを判定する（Ｓ１４０２）。
【０１０５】
ループのイタレーション間に依存がある場合（Ｓ１４０２：有り）、未解析のループ処理があるかの判定（Ｓ１４０１）に戻る。
【０１０６】
ループのイタレーション間に依存がない場合（Ｓ１４０２：無し）、未解析のループ内代入変数があるかを判定する（Ｓ１４０３）。
【０１０７】
未解析のループ内代入変数がない場合（Ｓ１４０３：Ｎｏ）、並列処理開始、終了処理の付加（Ｓ１４０８）へ進む。
【０１０８】
未解析のループ内代入変数がある場合（Ｓ１４０３：Ｙｅｓ）、以下の処理を行う。
【０１０９】
この変数がループ外で参照される場合（Ｓ１４０４：Ｙｅｓ）、データ更新管理スレッドに通知するためのスレッドデータ更新情報の通知処理を付加する（Ｓ１４０５）。
【０１１０】
ここでいう「スレッドデータ更新情報」とは、各処理スレッドが扱うデータの更新に係る情報である。例えば、イタレーションの実行結果を示す値とイタレーション番号ｉ（ｔｈ）との組を含んでいる。
【０１１１】
この変数がループ内で参照される場合（Ｓ１４０６：Ｙｅｓ）、前記変数を処理スレッド内専用に複製化する（Ｓ１４０７）。
【０１１２】
続いて、並列処理開始処理および終了処理を付加し（Ｓ１４０８）、未解析のループ処理があるかの判定（Ｓ１４０１）に戻る。
【０１１３】
係る構成によれば、データ更新管理スレッドが各処理スレッドからのスレッドデータ更新情報を受信し、データ更新情報を更新するか否かの判定を行い、終値保証に不要なデータは破棄し、必要な１つのデータのみを格納することにより、処理スレッドごとにデータ更新情報を格納する領域を必要としないため、少量のメモリ領域によってマルチスレッド並列実行時の終値保証が可能となる。
【０１１４】
また、マルチスレッド実行手段の上でデータ更新管理スレッドを実行することにより、既存のマルチスレッド実行手段を用いて実現することが可能である。また、マルチスレッドコンパイラによって、１つのスレッドで動作するプログラムからマルチスレッド実行手段の上で動作可能であり、終値保証を実現したプログラムを自動的に生成することができる。
【０１１５】
なお、マルチスレッドコンパイラ１３０２が生成する処理スレッドプログラム１３１０は、１つのプログラムであってもよいし、複数のプログラムで構成されてもよい。
【０１１６】
なお、処理スレッドプログラム１３１０およびデータ更新管理スレッドプログラム１３１１は、ソースプログラムと同じ言語のプログラムでもよいし、マルチスレッド動作手段の上で動作するオブジェクトコードでもよい。
【０１１７】
なお、本実施の形態４では、管理対象変数リスト１３０５、処理スレッドプログラムの中間コード１３０６、およびデータ更新管理スレッドプログラムの中間コード１３０８を生成しているが、ファイルなどに生成してもよいし、コンパイラ内部で情報を保持するだけでもよい。
【０１１８】
また、本実施の形態４では前処理部１３０３をその他処理部と分けて示しているが、前処理部１３０３がない構成も考えられる。また、前処理部１３０３がその他の処理部に含まれる構成も取り得る。
【０１１９】
なお、本実施の形態４では後処理部１３０９をその他処理部と分けて示しているが、後処理部１３０９がない構成も考えられる。また、後処理部１３０９がその他の処理部に含まれる構成も取り得る。
（実施の形態５）
実施の形態５は、実施の形態１などで説明したマルチスレッド並列実行装置を、集積回路（ＬＳＩ）で構成するものである。この集積回路は、デジタルテレビやブルーレイディスクレコーダーなどの各種ＡＶ機器に搭載することができる。
【０１２０】
図１５に示すように、集積回路１５０１は、マルチスレッド実行部１２０２と、暫定データ格納部１０４を備える。
【０１２１】
なお、集積回路は例えばＬＳＩであり、個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。
（実施の形態６）
実施の形態１で説明したマルチスレッド並列実行装置は、様々な装置に組み込んで、復号や再符号化を実行させることが好適である。
【０１２２】
図１６に示す放送ストリーム再生装置１６０１は、放送ストリームを受信する受信部１６０２、受信された放送ストリームを復号する復号部１６０３、復号された放送ストリームを再生する再生部１６０４を備える。この復号部１６０３は、マルチスレッド並列実行装置１０１を含んで構成される。
【０１２３】
図１７に示す放送ストリーム蓄積装置１７０１は、放送ストリームを受信する受信部１６０２、受信された放送ストリームを再符号化する再符号化部１７０５、再符号化された放送ストリームを蓄積する蓄積部１７０６を備える。この再符号化部１７０５は、マルチスレッド並列実行装置１０１を含んで構成される。
【０１２４】
図１８に示す蓄積ストリーム再生装置１８０１は、ストリームを蓄積する蓄積部１７０６、蓄積されたストリームを復号する復号部１６０３、復号されたストリームを再生する再生部１６０４を備える。この復号部１６０３は、マルチスレッド並列実行装置１０１を含んで構成される。
【０１２５】
図１９に示す蓄積ストリーム再符号化装置１９０１は、ストリームを蓄積する蓄積部１７０６、蓄積されたストリームを再符号化する再符号化部１７０５を備える。この再符号化部１７０５は、マルチスレッド並列実行装置１０１を含んで構成される。
【０１２６】
なお、本実施の形態６は、各実施の形態と適宜組み合わせることができる。例えば、実施の形態５で説明した集積回路１５０１を、放送ストリーム再生装置１６０１に組み込んでもよい。
（実施の形態７）
実施の形態１では、暫定データ格納部１０４が格納する情報は、イタレーションの実行結果を示す値とイタレーション番号ｉとの１組であったが、これらの組を複数格納するとしても構わない。
【０１２７】
このように複数の組を格納することにより、複数種類のイタレーションを並列して実行する場合にも終値保証を図ることができる。
【０１２８】
図２２を用いて一例を説明する。マルチスレッド並列実行装置２２０１は、マルチスレッド実行部２２０２、データ更新管理部２２０３、暫定データ格納部２２０４を備える。
【０１２９】
暫定データ格納部２２０４は、それぞれ（１）イタレーションの実行結果を示す値、（２）イタレーション番号ｉ、（３）イタレーションの種類を識別するための識別ＩＤ、の三者からなる組をｎ個（ｎは２以上の整数である。）格納している。
【０１３０】
マルチスレッド実行部２２０２は、複数種類のイタレーションを並列実行する機能を有し、各スレッドにおけるイタレーションが終了する毎に、イタレーションの実行結果を示す値、イタレーション番号ｉ、および識別ＩＤを受信部２２１１へと送信する。
【０１３１】
また、マルチスレッド実行部２２０２は、複数種類のうちのいずれかの全イタレーションが終了すると、終了したイタレーションの種類を識別するための識別ＩＤを含む終了情報を終了判定部２２１３に送信する。
【０１３２】
格納制御部２２１２は、受信部２２１１が値とイタレーション番号ｉと識別ＩＤの三者の組を受信すると、受信したイタレーション番号ｉと、暫定データ格納部２２０４中で受信した識別ＩＤに対応するイタレーション番号ｉの大小関係に基づいて、その識別ＩＤに対応する値およびイタレーション番号ｉを上書き格納するかしないかの制御を行う。
【０１３３】
格納制御部２２１２が上書き格納する際には、暫定データ格納部２２０４が格納している情報の中から、識別ＩＤに対応する値およびイタレーション番号ｉを上書きの対象とする。
【０１３４】
終了判定部２２１３が、マルチスレッド実行部２２０２から上記終了情報を受信すると、確定部２２１４は、暫定データ格納部２２０４に格納された組の中から、この終了情報に含まれる識別ＩＤに対応する値を取得して、確定データ格納部２２０５に格納する。
【０１３５】
なお、どの種類のイタレーションによる処理結果かを区別するために、確定データ格納部２２０５において、値に識別ＩＤを関連付けて格納するとしても構わない。
【０１３６】
以上、本実施の形態７について説明したが、実施の形態２で説明したブレイクフラグを用いる変形例も考えられる。具体的な構成としては、マルチスレッド実行部２２０２は各スレッドにおけるイタレーションが終了する毎に、
（１）イタレーションの実行結果を示す値、
（２）実行したイタレーションがループ処理中で何番目であるかを示すイタレーション番号ｉ（ｔｈ）、
（３）イタレーションの種類を識別するための識別ＩＤ、
（４）ブレークポイントに到達したかどうかを示すブレークフラグ
の４種類の情報を、受信部２２１１へと送信する。そして、格納制御部２２１２は、受信したイタレーション番号ｉと暫定データ格納部２２０４中で受信した識別ＩＤに対応するイタレーション番号ｉとの大小関係、および、受信したブレイクフラグのＯＮ／ＯＦＦと暫定データ格納部２２０４中で受信した識別ＩＤに対応するブレイクフラグのＯＮ／ＯＦＦとに基づいて上書き格納の有無を判定を行う。この判定の方法は、図１１を用いて説明したものと同様であるので説明は省略する。
（実施の形態８）
各実施の形態で説明したマルチスレッド実行部が発行する命令に以下の（１）〜（３）で説明するような内容を含めるとしても構わない。これらの命令はフレキシブルな並列実行に貢献することができる。基本的な構成は図１で説明したものと同様のため、以下の本実施の形態の説明では図１の機能ブロックを用いて行う。
【０１３７】
（１）暫定データ格納部１０４の情報を無効化する命令
マルチスレッド実行部１０２から受信部１１１を介してこの命令を受けた格納制御部１１２は、暫定データ格納部１０４の情報を無効化する（あるいはクリアする。）。係る命令は、マルチスレッド並列実行の初期設定（図２，Ｓ２１）などに利用することができる。
【０１３８】
（２）スレッドデータ更新情報を管理ハードウェアに送信する命令
スレッドデータ更新情報（各処理スレッドが扱うデータの更新に係る情報である。）を管理ハードウェアに送信する命令である。
【０１３９】
（３）暫定データ格納部１０４の情報を実際の変数に反映する命令
暫定データ格納部１０４の情報を、確定データ格納部１０５に格納し実際の変数に反映する命令である。係る命令は、例えば、値の反映処理（図２，Ｓ２６）において利用することができる。
（実施の形態９）
本実施の形態９は、実施の形態７，８を混合したような実施の形態である。以下の説明では図２２の機能ブロックを用いて行う。
【０１４０】
実施の形態９では、実施の形態７同様、暫定データ格納部２２０４は、それぞれ（１）イタレーションの実行結果を示す値、（２）イタレーション番号ｉ、（３）識別ＩＤ、の三者からなる組をｎ個（ｎは２以上の整数である。）格納している。
【０１４１】
そして、マルチスレッド実行部２２０２のスレッドデータ更新情報には、このｎ個の組の中のいずれかを特定するための識別ＩＤを含める。
【０１４２】
また、マルチスレッド実行部２２０２において、以下のような命令を発行するとしてもよい。下記（１）〜（３）のいずれも命令の実行対象を識別するための１以上の識別ＩＤを含む。
【０１４３】
（１）暫定データ格納部２２０４の領域を確保または無効化する命令
暫定データ格納部２２０４内の識別ＩＤ用に対応する領域を確保または無効化する命令である。これらの命令は、マルチスレッド並列実行の初期設定（図２，Ｓ２１）に利用することができる。
【０１４４】
また、確保（無効化）ができなかった場合には、例外処理を起こしたり、各領域の占有状態を管理するステータスレジスタを更新することが考えられる。
【０１４５】
（２）スレッドデータ更新情報を管理ハードウェアに送信する命令
指定した識別ＩＤに対応するスレッドデータ更新情報を管理ハードウェアに送信する命令である。
【０１４６】
（３）暫定データ格納部２２０４の情報を実際の変数に反映する命令
指定した識別ＩＤに対応する暫定データ格納部２２０４の情報を、確定データ格納部２２０５に格納し実際の変数に反映する命令である。係る命令は、例えば、値の反映処理（図２，Ｓ２６）において利用することができる。
【０１４７】
（４）暫定データ格納部２２０４の領域を開放する命令
暫定データ格納部２２０４内の１以上の識別ＩＤ用に対応する領域を開放する命令である。係る命令は、例えば、値の反映処理（図２，Ｓ２６）を経て用が無くなった領域を対象に利用することができる。
【０１４８】
また、前記（３）および（４）に係る処理を１命令で実現するようにしても構わない。
＜補足１＞
以上、本実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連又は付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であっても構わない。
【０１４９】
（１）実施の形態では、図５に示すように、値を更新しないイタレーションの場合に、マルチスレッド実行部１０２はデータが空であることを示す”null”を送信するとして説明したがこれに限られない。例えば、値を更新しないイタレーションに関しては、マルチスレッド実行部１０２は値やイタレーション番号を送信しないとしても構わない。
【０１５０】
（２）実施の形態においては、図１のように暫定データ格納部１０４と確定データ格納部１０５とは、別の格納手段として示したが、同一のデータ格納手段であるとしてもよい。
【０１５１】
（３）実施の形態では、図４のようにfor〜if文の命令を繰り返しの例に挙げて説明したがこれに限られない。例えばＣ言語においては、for文、while文、do while文などを用いることができる。
【０１５２】
（４）実施の形態では、各イタレーションが終了する毎にマルチスレッド実行部１０２がその実行結果である値とイタレーション番号とを送信するとしたが、これに代えて、スレッドの終了を契機に送るようにしてもよい。
【０１５３】
例えば、図２０（ａ）に示すように、スレッド１の処理が終了すると、マルチスレッド実行部１０２は、スレッド１が担当したイタレーションの実行結果を示す値"２"と、スレッド番号"th1"を送る。
【０１５４】
同様にスレッド２の処理が終了すると、マルチスレッド実行部１０２は、スレッド２が担当したイタレーションの実行結果を示す値"３"と、スレッド番号"th2"を送る。
【０１５５】
そして、データ更新部管理部１０３の格納制御部１１２は、スレッド番号の大小関係に基づいて上書きの要否を判断する。
【０１５６】
図２０（ｂ）の例では、暫定データ格納部に格納されているスレッド番号"th2"が受信したスレッド番号"th1"より後順なので上書きしないとしている。
【０１５７】
（５）実施の形態では、図２に示すように初期設定（Ｓ２１）について簡単な説明に留めたが、例えば次のようにしてデータ更新の有無に応じた挙動を行うようにしても構わない。
【０１５８】
すなわち図２１に示すように、初期設定として、格納制御部１１２はイタレーション番号を”−１”に設定する（Ｓ２１０１）。
【０１５９】
そして、並列実行終了後（Ｓ２２：Ｙｅｓ）、格納制御部１１２はイタレーション番号が”−１”のままであれば（Ｓ２１０２：Ｎｏ）、暫定データ格納部１０４の値が並列実行にも関わらず更新されなかったことを意味するので、データの反映（Ｓ２６）をスキップする。
【０１６０】
（６）実施の形態では、図７（ｅ）に示すように、並列実行の終了時には暫定データ格納部１０４に格納された値を”３”、確定データ格納部１０５へと反映するとしているがこれに限られない。
【０１６１】
要は、値”３”が並列実行の結果として確定できるようにすればよい。例えば、結果であることを示す情報を値”３”に付加しても構わない。
【０１６２】
（７）各実施の形態では、マルチスレッド実行部における処理スレッド数は２個として説明したが、これに限らず、２個以上であれば任意の個数を取り得る。
【０１６３】
例えば、処理スレッド数が４個や８個であってもよい。
【０１６４】
（８）実施の形態１〜９や本補足の内容を組み合わせて実施しても構わない。
＜補足２＞
本実施の形態は、以下の態様を含むものである。
【０１６５】
（１）本実施の形態に係るマルチスレッド並列実行装置は、ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて並列実行する実行手段と、前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信手段と、前記値と前記順番情報との組を格納するための格納手段と、前記受信手段が前記組を受信した場合に、受信された前記順番情報と前記格納部に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納部に上書きさせるか、上書きさせないかを制御する制御手段と、前記実行手段による並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定手段と、を備えることを特徴とする。
【０１６６】
（２）前記ひとつのループ処理における繰り返し単位には、処理を途中で打ち切るためのブレークポイントが設定されており、前記受信手段が受信する前記組は、前記値と前記順番情報とに加えて、前記ブレークポイントへ到達済みか未到達かを示すフラグを含み、前記格納手段は、前記値と前記順番情報と前記フラグとを含む組を格納するためのものであり、前記制御手段は、前記受信手段により受信された前記組に含まれる前記順番情報と前記フラグを、前記格納手段に格納された前記順番情報と前記フラグとに参照して、前記上書きの制御を行うこととしても構わない。
【０１６７】
この構成によれば、ブレークポイントが設定されたループ処理においても終値保証を図ることができる。
【０１６８】
（３）前記制御手段は、前記ひとつのループ処理を、逐次処理したと仮定した場合にブレークポイントへ最初に到達した繰り返し単位に対応する値が前記格納手段に格納されていれば、前記上書きを抑止するとしても構わない。
【０１６９】
（４）前記制御手段は、前記受信手段による受信があった場合に、受信された前記順番情報が前記格納部に格納された順番情報より後順を示しているときには、受信された前記値と前記順番情報との組を前記格納部に上書きさせ、受信された前記順番情報が前記格納部に格納された順番情報より前順を示しているときには、受信された前記値と前記順番情報との組を前記格納部に上書きさせないとしても構わない。
【０１７０】
（５）前記ひとつのループ処理における繰り返し単位は、イタレーションであって、前記順番情報は、イタレーションの順番を示すイタレーション番号であるとしても構わない。
【０１７１】
（６）前記受信手段、前記制御手段および前記確定手段は、前記実行手段による実行対象となる管理スレッドにより構成されているとしても構わない。
【０１７２】
（７）前記実行手段が並列実行する繰り返し単位は複数の種類があり、前記受信手段は、前記組に加えて前記繰り返し単位の種類を識別するための識別子を受信し、前記格納手段は、繰り返し単位の種類を識別するための識別子に関連付けて前記組を格納し、前記制御手段は、受信された識別子に関連付けられた組を対象に上書きの有無の制御を行うとしても構わない。
【０１７３】
（８）前記実行手段は、前記格納手段が格納している情報を無効化する命令、前記組を管理用ハードウェアに送信する命令、または、前記格納手段に格納された値を、実際の変数に反映する命令、の少なくともいずれか１つの命令を発行するとしても構わない。
【０１７４】
（９）（８）において、前記実行手段が並列実行する繰り返し単位は複数種類あり、前記受信手段は、前記組に加えて前記繰り返し単位の種類を識別するための識別子を受信し、前記格納手段は、繰り返し単位の種類を識別するための識別子に関連付けて前記組を格納し、前記制御手段は、受信された識別子に関連付けられた組を対象に上書きの有無の制御を行うものであって、前記実行手段が発行する命令は、実行対象となる識別子を含むとしても構わない。
【０１７５】
（１０）放送ストリーム再生装置は、放送ストリームを受信する受信手段と、受信された放送ストリームを復号する復号手段と、復号された放送ストリームを再生する再生手段とを備え、前記復号手段は（１）のマルチスレッド並列実行装置を含んで構成されるとしても構わない。
【０１７６】
（１１）放送ストリーム蓄積装置は、放送ストリームを受信する受信手段と、受信された放送ストリームを再符号化する再符号化手段と、再符号化された放送ストリームを蓄積する蓄積手段とを備え、前記再符号化手段は（１）のマルチスレッド並列実行装置を含んで構成されるとしても構わない。
【０１７７】
（１２）蓄積ストリーム再生装置は、ストリームを蓄積する蓄積手段と、蓄積されたストリームを復号する復号手段と、復号されたストリームを再生する再生手段とを備え、前記復号手段は（１）のマルチスレッド並列実行装置を含んで構成されるとしても構わない。
【０１７８】
（１３）蓄積ストリーム再符号化装置は、ストリームを蓄積する蓄積手段と、蓄積されたストリームを再符号化する再符号化手段とを備え、前記再符号化手段は（１）のマルチスレッド並列実行装置を含んで構成されるとしても構わない。
【０１７９】
（１４）集積回路は、ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて並列実行する実行手段と、前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信手段と、前記値と前記順番情報との組を格納するための格納手段と、前記受信手段が前記組を受信した場合に、受信された前記順番情報と前記格納部に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納部に上書きさせるか、上書きさせないかを制御する制御手段と、前記実行手段による並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定手段と、を備えることを特徴とする。
【０１８０】
（１５）前記実行手段は、マルチスレッドプロセッサから構成されるとしても構わない。
【０１８１】
（１６）前記実行手段は、マルチコアプロセッサから構成されるとしても構わない。
【０１８２】
（１７）本実施の形態に係るマルチスレッド並列実行方法は、ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて実行手段に並列実行させる実行ステップと、
前記実行ステップにおいて前記実行手段が並列実行している間に、各スレッドにおける繰り返し単位の実行の結果を示す値と、当該繰り返し単位の順番を示す順番情報との組を前記実行手段から受信する受信ステップと、前記値と前記順番情報との組を格納手段に格納するための格納ステップと、前記受信ステップが前記組を受信した場合に、受信された前記順番情報と前記格納手段に格納された順番情報のそれぞれにより示される順番の先後に基づいて、受信された前記順番情報と対応する前記値との組を前記格納手段に上書きさせるか、上書きさせないかを制御する制御ステップと、前記実行ステップにおける並列実行が終了すると、前記格納手段に格納されている値を、前記ひとつのループ処理の実行結果として確定する確定ステップと、を含むことを特徴とする。
【０１８３】
（１８）本実施の形態に係るマルチスレッドコンパイラは、１つの処理スレッド上で動作しループ処理を含むソースプログラムをコンパイルするマルチスレッドコンパイラであって、前記ループ処理における繰り返し単位が終了する毎に、実行の結果を示す値と当該繰り返し単位の順番を示す順番情報との組を送信する複数の処理スレッド用のプログラムと、各処理スレッドから前記組を受信すると、当該組に含まれる順番情報と格納手段にすでに格納された順番情報とを比較して、受信した組に含まれる値と順番情報とを前記格納手段に上書きするか、上書きしないかを制御するデータ更新管理スレッド用のプログラムとを生成することを特徴とする。
【産業上の利用可能性】
【０１８４】
本発明に係るマルチスレッド並列実行装置は、ひとつのループ処理における繰り返し単位を、複数のスレッドに分けて並列実行するようなマルチスレッド実行環境において有用である。
【符号の説明】
【０１８５】
１０１，９０１，１２０１，２２０１  マルチスレッド並列実行装置
１０２，９０２，１２０２，２２０２  マルチスレッド実行部
１０３，９０３，２２０３  データ更新管理部
１０４，９０４，２２０４  暫定データ格納部
１０５，２２０５  確定データ格納部
１１１，９１１，２２１１  受信部
１１２，９１２，２２１２  格納制御部
１１３，２２１３  終了判定部
１１４，２２１４  確定部
１２０２ａ，１２０２ｂ  処理スレッド
１２０３  データ更新管理スレッド
１３０２  マルチスレッドコンパイラ
１５０１  集積回路
１６０１  放送ストリーム再生装置
１６０２  受信部
１６０３  復号部
１６０４  再生部
１７０１  放送ストリーム蓄積装置
１７０５  再符号化部
１７０６  蓄積部
１８０１  蓄積ストリーム再生装置
１９０１  蓄積ストリーム再符号化装置
【図１】
0005945779.tif 000002
【図２】
0005945779.tif 000003
【図３】
0005945779.tif 000004
【図４】
0005945779.tif 000005
【図５】
0005945779.tif 000006
【図６】
0005945779.tif 000007
【図７】
0005945779.tif 000008
【図８】
0005945779.tif 000009
【図９】
0005945779.tif 000010
【図１０】
0005945779.tif 000011
【図１１】
0005945779.tif 000012
【図１２】
0005945779.tif 000013
【図１３】
0005945779.tif 000014
【図１４】
0005945779.tif 000015
【図１５】
0005945779.tif 000016
【図１６】
0005945779.tif 000017
【図１７】
0005945779.tif 000018
【図１８】
0005945779.tif 000019
【図１９】
0005945779.tif 000020
【図２０】
0005945779.tif 000021
【図２１】
0005945779.tif 000022
【図２２】
0005945779.tif 000023