(57)【要約】【課題】  多重スレッド実行プロセッサ及びその動作方法を提供すること。【解決手段】  多重スレッド実行プロセッサは、プログラムコードを実行するための複数のスレッドのうちから第１スレッドを選択するためのスレッド選択部と、そのスレッド選択部によって選択された第１スレッドを実行し、第１スレッドに対する実行を完了した後で、複数のスレッドのうちからスレッド選択部によって選択された第２スレッドを実行するためのスレッド実行部とを含む。【選択図】      図２
2019160352.tif 000002
【特許請求の範囲】
【請求項１】
プログラムコードを実行するための複数のスレッドのうちから第１スレッドを選択するためのスレッド選択部と、
前記スレッド選択部によって選択された前記第１スレッドを実行するためのスレッド実行部と、
前記第１スレッドを実行するために、発行された命令語のレイテンシーが所定値以上であることに基づいて、当該命令語がスレッド交換を生じさせる通過命令語であるか否かを判断するためのスレッド交換判断部と、を含み、
前記スレッド実行部は、前記第１スレッドに対する実行中に発行された命令語が、前記スレッド交換判断部によって通過命令語であると判断された場合に、スレッド保存部に保存された前記複数のスレッドのうちから前記スレッド選択部によって選択された第２スレッドにスレッド交換を行って、前記第２スレッドを実行し、
前記第１スレッドの状態は、前記第１スレッドから前記第２スレッドへスレッド交換が行われる場合に、準備状態から通過状態に変わり、前記スレッド交換以前に発行された通過命令語に対する処理が完了すると、準備状態に戻され、前記準備状態はスレッドに含まれている命令を実行することが可能な状態であり、前記通過状態はスレッドに含まれている命令を実行することが禁止されている状態である、多重スレッド実行プロセッサ。
【請求項２】
前記複数のスレッドを保存するためのスレッド保存部をさらに含む請求項１に記載の多重スレッド実行プロセッサ。
【請求項３】
前記スレッド保存部に保存された複数のスレッドのそれぞれは、準備状態、通過状態、及び完了状態のうちの何れかの状態にあり、
前記スレッド選択部は、前記複数のスレッドのうちから前記準備状態にある１つのスレッドを選択する請求項２に記載の多重スレッド実行プロセッサ。
【請求項４】
前記スレッド選択部は、前記複数のスレッドのうちから前記複数のスレッドのそれぞれの状態を示すスレッド状態情報を利用して、準備状態のスレッドを選択する請求項３に記載の多重スレッド実行プロセッサ。
【請求項５】
プログラムコードを実行するための複数のスレッドを実行するためのプロセッシングユニットを含み、
前記プロセッシングユニットは、前記複数のスレッドのうちの第１スレッドに対する実行中に発行された命令語のレイテンシーが所定値以上であることに基づいて、当該命令語がスレッド交換を生じさせる通過命令語であると判断した場合に、スレッド交換を行って、第２スレッドを実行する方式で前記複数のスレッドを順次に実行し、
前記第１スレッドの状態は、前記第１スレッドから前記第２スレッドへスレッド交換が行われる場合に、準備状態から通過状態に変わり、前記スレッド交換以前に発行された通過命令語に対する処理が完了すると、準備状態に戻され、前記準備状態はスレッドに含まれている命令を実行することが可能な状態であり、前記通過状態はスレッドに含まれている命令を実行することが禁止されている状態である、多重スレッド実行プロセッサ。
【請求項６】
前記複数のスレッドのそれぞれは、準備状態、通過状態、及び完了状態のうちの何れかの状態にあり、
前記プロセッシングユニットは、前記複数のスレッドのうちから前記準備状態にある１つのスレッドを選択して実行する請求項５に記載の多重スレッド実行プロセッサ。
【請求項７】
前記多重スレッド実行プロセッサは、複数のプロセッシングユニットを含み、
前記複数のプロセッシングユニットのそれぞれは、前記プログラムコードを実行する複数の実行経路のうちの何れか１つの実行経路を特定するプログラムカウンターを使用する請求項５に記載の多重スレッド実行プロセッサ。
【請求項８】
準備状態にある第１スレッドの命令語を順次に実行するスレッド実行部と、
実行される現在の命令語のレイテンシーが所定値を超過すると判断されたことに応じて、前記第１スレッドの状態が通過状態に変わると、前記第１スレッドの実行を中断し、前記第１スレッドの状態が準備状態に戻るまで待機するスレッド選択部と、を含み、
前記スレッド実行部を利用して、前記準備状態に戻った前記第１スレッドの全ての命令語を実行し、前記第１スレッドの実行を完了し、前記スレッド選択部を利用して、前記実行が完了した第１スレッドを完了状態にし、
前記準備状態はスレッドに含まれている命令を実行することが可能な状態であり、前記通過状態はスレッドに含まれている命令を実行することが禁止されている状態である、多重スレッド実行プロセッサ。
【請求項９】
前記スレッド実行部は、第２スレッドが準備状態にあり、前記第１スレッドが前記通過状態にあり、実行が中断されていた場合、前記第２スレッドの命令語を順次に実行する請求項８に記載の多重スレッド実行プロセッサ。
【請求項１０】
プログラムコードを実行するための複数のスレッドを実行するための多重スレッド実行プロセッサの動作方法であって、
前記複数のスレッドのうちの第１スレッドを実行し、実行のために発行された命令語のレイテンシーが所定値以上であるか否かに基づいて、当該命令語がスレッド交換を生じさせる通過命令語であるか否かを判断する段階と、
前記発行された命令語が通過命令語ではないと判断された場合には、前記第１スレッドを実行し続け、前記発行された命令語が通過命令語であると判断された場合には、スレッド交換を行い、前記複数のスレッドのうちの第２スレッドを実行する段階と、
を含み、前記第１スレッドの状態は、前記第１スレッドから前記第２スレッドへスレッド交換が行われる場合に、準備状態から通過状態に変わり、前記スレッド交換以前に発行された通過命令語に対する処理が完了すると、準備状態に戻され、前記準備状態はスレッドに含まれている命令を実行することが可能な状態であり、前記通過状態はスレッドに含まれている命令を実行することが禁止されている状態である、多重スレッド実行プロセッサの動作方法。
【請求項１１】
前記複数のスレッドに対する実行が完了するまで前記スレッド交換を通じて、前記複数のスレッドを順次に実行する請求項１０に記載の多重スレッド実行プロセッサの動作方法。
【請求項１２】
スレッド実行部を利用して、準備状態にある第１スレッドの命令語を順次に実行する段階と、
スレッド選択部を利用して、実行される現在の命令語のレイテンシーが所定値を超過すると判断されたことに応じて、前記第１スレッドの状態が通過状態に変わると、前記第１スレッドの実行を中断し、前記第１スレッドの状態が準備状態に戻るまで待機する段階と、
前記スレッド実行部を利用して、前記準備状態に戻った前記第１スレッドの全ての命令語を実行し、前記第１スレッドの実行を完了し、前記スレッド選択部を利用して、前記実行が完了した第１スレッドを完了状態にする段階と、
を含み、前記準備状態はスレッドに含まれている命令を実行することが可能な状態であり、前記通過状態はスレッドに含まれている命令を実行することが禁止されている状態である、多重スレッド実行プロセッサの動作方法。
【請求項１３】
第２スレッドが準備状態にあり、前記第１スレッドが前記通過状態にあり、実行が中断されていた場合には、前記スレッド実行部を利用して、前記第２スレッドの命令語を順次に実行する段階をさらに含む請求項１２に記載の多重スレッド実行プロセッサの動作方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサ（ｐｒｏｃｅｓｓｏｒ）に関し、より具体的には多重スレッド実行プロセッサ（ｍｕｌｔｉｐｌｅ  ｔｈｒｅａｄｓ  ｅｘｅｃｕｔｉｏｎ  ｐｒｏｃｅｓｓｏｒ）、及びその動作方法等に関する。
【背景技術】
【０００２】
グラフィック処理の基本単位は、主に頂点（ｖｅｒｔｅｘ）と画素（ｐｉｘｅｌ）である。そして、このような基本単位に対する処理は、通常互いに独立した特性がある。したがって、グラフィック処理装置（Ｇｒａｐｈｉｃ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＧＰＵ）でのこれらのそれぞれに対する処理は、独立して実行可能なスレッド（ｔｈｒｅａｄ）と見なされる。ＧＰＵでは、このような多数のスレッドを１つのプロセッサコアで同時に実行する並列処理アルゴリズムに関して多様な研究及び開発が進められている。
【０００３】
最近、汎用グラフィック処理装置（Ｇｅｎｅｒａｌ  Ｐｕｒｐｏｓｅ  ｃｏｍｐｕｔｉｎｇ  ｏｎ  Ｇｒａｐｈｉｃ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＧＰＧＰＵ）が注目を浴びている。ＧＰＧＰＵは、既存のＧＰＵのアーキテクチャー（ａｒｃｈｉｔｅｃｔｕｒｅ）を一般目的の演算にも使わせるために提案されたものである。ＧＰＧＰＵでは、ＧＰＵに適用される並列処理アルゴリズムを用いて中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＣＰＵ）が伝統的に取り扱った応用プログラムの演算を処理する。このようなＧＰＧＰＵ技術の一例として、ＣＵＤＡ（Ｃｏｍｐｕｔｅ  Ｕｎｉｆｉｅｄ  Ｄｅｖｉｃｅ  Ａｒｃｈｉｔｅｃｔｕｒｅ）がある。ＣＵＤＡは、ＧＰＵに適用される並列処理アルゴリズムを、Ｃプログラム言語（Ｃ  ｐｒｏｇｒａｍ  ｌａｎｇｕａｇｅ）を含めた産業標準言語により作成可能にする技術である。
【０００４】
多重スレッドを効率的に実行うための並列処理アルゴリズムの一例として、ＳＩＭＴアーキテクチャー（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｔｈｒｅａｄｓ  ａｒｃｈｉｔｅｃｔｕｒｅ）が提案されている。ＳＩＭＴアーキテクチャーでは、多数のスレッドの同じ命令（ｉｎｓｔｒｕｃｔｉｏｎ）を１つのプロセッサコアに集積された多数のプロセッシングユニット（Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＰＵ）で同時に処理する。そして、各プロセッシングユニット（ＰＵ）は、２つ以上のスレッドの同じ命令を順次に処理することができる。これによれば、同時に実行可能な多数のスレッドを最大限に利用してシステムの性能を高めうる。但し、個別プロセッシングユニット（ＰＵ）で発生するスレッド交換オーバーヘッド（ｔｈｒｅａｄ  ｓｗｉｔｃｈ  ｏｖｅｒｈｅａｄ）は、プロセッシングユニットでレジスタ（ｒｅｇｉｓｔｅｒ）などを活用して、スレッド実行に必要な資源を複製して、多様なスレッドの状態を保有させて解決する。
【０００５】
一方、並列処理アルゴリズムによって、多重スレッドによって処理されるプログラムコードには、１つ以上の分岐発散と収斂（ｂｒａｎｃｈ  ｄｉｖｅｒｇｅｎｃｅ  ａｎｄ  ｃｏｎｖｅｒｇｅｎｃｅ）が含まれうる。本願において収斂は収束と言及されてもよい。この場合に、分岐発散の回数に比例して、当該プログラムコードの処理可能な経路（ｐａｔｈ）は多様になる。並列処理アルゴリズムでも、あらゆるスレッドが必ずしも同じ経路に沿うものではなく、複数のスレッドは、それぞれ固有の経路に沿っても良い。複数のスレッドが、同じ経路に沿ってプログラムコードを処理する場合に、ＳＩＭＴアーキテクチャーでは、あらゆるプロセッシングユニット（ＰＵ）が同時に実行可能なあらゆるスレッドの同じ命令を同時に処理することができるので、制御フロー（ｃｏｎｔｒｏｌ  ｆｌｏｗ）も簡単であり、プロセッシングユニットの資源活用度の側面で非常に優れるが、一方、頻繁なスレッド交換によるオーバーヘッドが発生する恐れがある。一方、複数のスレッドが他の経路に沿ってプログラムコードを処理する場合に、ＳＩＭＴアーキテクチャーでは、互いに異なる経路に沿うスレッドは、制御フローが非常に多様かつ複雑であるだけではなく、分岐命令語の以後には、あらゆるスレッドの同時実行が不可能となって、プロセッシングユニット（ＰＵ）の資源(リソース)活用度が低下する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明が解決しようとする課題は、スレッド交換オーバーヘッドを最小化することができる多重スレッド実行プロセッサ、及びその動作方法を提供することである。
【０００７】
本発明が解決しようとする他の課題は、プロセッシングユニットの資源活用度が高い多重スレッド実行プロセッサ、及びその動作方法を提供することである。
【０００８】
本発明が解決しようとするさらに他の課題は、長いレイテンシー命令（ｌｏｎｇ−ｌａｔｅｎｃｙ  ｉｎｓｔｒｕｃｔｉｏｎ）を含むプログラムコードを迅速に、そして、効率的に処理することができる多重スレッド実行プロセッサ、及びその動作方法を提供することである。
【０００９】
本発明が解決しようとするさらに他の課題は、単純な形態のハードウェア構造を有する多重スレッド実行プロセッサ、及びその動作方法を提供することである。
【課題を解決するための手段】
【００１０】
本発明の一実施形態による多重スレッド実行プロセッサは、プログラムコードを実行するための複数のスレッドのうちから第１スレッドを選択するためのスレッド選択部と、前記スレッド選択部によって選択された前記第１スレッドを実行し、前記第１スレッドに対する実行を完了した後で、前記複数のスレッドのうちから前記スレッド選択部によって選択された第２スレッドを実行するためのスレッド実行部と、を含む。
【００１１】
多重スレッド実行プロセッサは、前記複数のスレッドを保存するためのスレッド保存部をさらに含みうる。
【００１２】
前記スレッド保存部に保存された複数のスレッドそれぞれは、初期状態（ｉｎｉｔｉａｌ  ｓｔａｔｅ）と完了状態（ｔｅｒｍｉｎａｔｅｄ  ｓｔａｔｅ）とのうちの１つの状態を有し、前記スレッド選択部は、前記複数のスレッドのうちから前記初期状態にある１つのスレッドを選択することができる。
【００１３】
前記スレッド保存部は、前記複数のスレッドのうちから前記初期状態のスレッドをラウンドロビン方式によって選択することができる。
【００１４】
前記スレッド選択部は、前記スレッド保存部に保存された複数のスレッドのそれぞれの状態を指示するスレッド状態情報（ｔｈｒｅａｄ  ｓｔａｔｅ  ｉｎｆｏｒｍａｔｉｏｎ）を活用して、前記複数のスレッドのうちから初期状態のスレッドを選択することができる。
【００１５】
前記複数のスレッドのそれぞれは、前記プログラムコードを実行する複数の実行経路のうち、何れか１つの実行経路に沿う。
【００１６】
前記複数の実行経路は、それぞれに対応するプログラムカウンターによって定められうる。
【００１７】
本発明の他の実施形態による多重スレッド実行プロセッサは、プログラムコードを実行するための複数のスレッドのうちから第１スレッドを選択するためのスレッド選択部と、前記スレッド選択部によって選択された前記第１スレッドを実行するためのスレッド実行部と、前記第１スレッドを実行するために、発行された命令語が通過命令語であるか否かを判断するためのスレッド交換判断部と、を含み、前記スレッド実行部は、前記第１スレッドに対する実行中に発行された命令語が、前記スレッド交換判断部によって通過命令語であると判断されれば、前記スレッド保存部に保存された前記複数のスレッドのうちから前記スレッド選択部によって選択された第２スレッドにスレッド交換を行って、前記第２スレッドを実行することができる。
【００１８】
前記多重スレッド実行プロセッサは、前記複数のスレッドを保存するためのスレッド保存部をさらに含みうる。
【００１９】
前記スレッド交換判断部は、前記プログラムコードに明示的に表示されたスレッド交換情報に基づいて、前記発行された命令語が通過命令語であるか否かを判断することができる。
【００２０】
前記スレッド交換情報は、前記プログラムコードのエンコーディング時に含まれうる。前記スレッド交換情報は、前記プログラムコードをエンコーディングする間にプログラマーによって含まれるか、または所定のアルゴリズムによるエンコーディング時に自動的に含まれうる。
【００２１】
前記スレッド保存部に保存された複数のスレッドのそれぞれは、準備状態（ｒｅａｄｙｓｔａｔｅ）、通過状態（ｐａｓｓｅｄ  ｓｔａｔｅ）、及び完了状態（ｔｅｒｍｉｎａｔｅｄ  ｓｔａｔｅ）のうちの１つの状態を有し、前記スレッド選択部は、前記複数のスレッドのうちから前記準備状態にある１つのスレッドを選択することができる。
【００２２】
前記スレッド実行部が、前記第１スレッドから前記第２スレッドにスレッド交換を行えば、前記第１スレッドは、通過状態になり、前記スレッド実行部が、前記スレッド交換以前に発行された通過命令語に対する処理が完了すれば、前記第１スレッドは、準備状態に復元されうる。
【００２３】
前記スレッド選択部は、前記複数のスレッドのうちから前記複数のスレッドのそれぞれの状態を指示するスレッド状態情報を活用して、準備状態のスレッドを選択することができる。
【００２４】
本発明のさらに他の実施形態による多重スレッド実行プロセッサは、プログラムコードを実行するための複数のスレッドを実行するためのプロセッシングユニットを含み、前記プロセッシングユニットは、前記複数のスレッドのうちの１つのスレッドに対する実行を完了し、そして、スレッド交換を行って、前記複数のスレッドのうちの他のスレッドをその次に実行する方式で前記複数のスレッドを順次に実行する。
【００２５】
前記多重スレッド実行プロセッサは、複数のプロセッシングユニットを含み、前記複数のプロセッシングユニットは、前記複数のスレッドを分けて実行することができる。
【００２６】
前記複数のプロセッシングユニットは、それぞれ固有のプログラムカウンター（Ｐｒｏｇｒａｍ  Ｃｏｕｎｔｅｒ）を使うことができる。
【００２７】
本発明のさらに他の実施形態による多重スレッド実行プロセッサは、プログラムコードを実行するための複数のスレッドを実行するためのプロセッシングユニットを含み、前記プロセッシングユニットは、前記複数のスレッドのうちの第１スレッドに対する実行中に発行された命令語が通過命令語である場合に、スレッド交換を行って、第２スレッドを実行する方式で前記複数のスレッドを順次に実行することができる。
【００２８】
前記プロセッシングユニットは、前記プログラムコードに明示的に表示されたスレッド交換情報に基づいて、前記発行された命令語が通過命令語であるか否かを判断することができる。
【００２９】
前記スレッド交換情報は、前記プログラムコードのエンコーディング時にプログラマーによって含まれるか、または所定のアルゴリズムによるエンコーディング時に自動的に含まれうる。
【００３０】
前記複数のスレッドのそれぞれは、準備状態、通過状態、及び完了状態のうちの１つの状態を有し、前記プロセッシングユニットは、前記複数のスレッドのうちから前記準備状態にある１つのスレッドを選択して実行することができる。
【００３１】
前記スレッド交換が起これば、前記第１スレッドは、通過状態になり、前記通過命令語に対する処理が完了すれば、前記第１スレッドは、準備状態に復元されうる。
【００３２】
前記多重スレッド実行プロセッサは、複数のプロセッシングユニットを含み、前記複数のプロセッシングユニットのそれぞれは、前記プログラムコードを実行する複数の実行経路のうちの何れか１つの実行経路を特定するプログラムカウンターを使うことができる。
【００３３】
プログラムコードを実行するための複数のスレッドを実行するための一実施形態による多重スレッド実行プロセッサの動作方法は、前記複数のスレッドのうちの第１スレッドを実行する段階と、スレッド交換を行って、前記複数のスレッドのうちの他のスレッドを実行する段階と、を含み、前記複数のスレッドに対する実行が完了するまで前記複数のスレッドを順次に実行する。
【００３４】
プログラムコードを実行するための複数のスレッドを実行するための他の実施形態による多重スレッド実行プロセッサの動作方法は、前記複数のスレッドのうちの第１スレッドを実行するが、実行のために発行された命令語が通過命令語であるか否かを判断する段階と、前記発行された命令語が通過命令語ではないと判断されれば、前記第１スレッドを実行し続け、前記発行された命令語が通過命令語であると判断されれば、スレッド交換を行って、前記複数のスレッドのうちの第２スレッドを実行する段階と、を含む。
【００３５】
前記複数のスレッドに対する実行が完了するまで前記スレッド交換を通じて、前記複数のスレッドを順次に実行することができる。
【００３６】
前記発行された命令語が通過命令語であるか否かを判断するためのスレッド交換情報は、前記プログラムコードに明示的に表示されている。
【００３７】
本発明のさらに他の実施形態による多重スレッド実行プロセッサの動作方法は、スレッド実行器を使って、準備状態にある第１スレッドの命令語を順次に実行する段階と、スレッド選択器を使って、前記第１スレッドが通過状態になれば、前記第１スレッドの実行を中断し、前記第１スレッドの状態が準備状態に戻って実行を続ける以前に待機する段階と、前記スレッド実行器を使って、前記準備状態に戻った前記第１スレッドのあらゆる命令語を実行して、前記第１スレッドの実行を完了し、前記スレッド選択器を使って、前記実行が完了した第１スレッドを完了状態にする段階と、を含む。
【００３８】
前記スレッド実行器を使って、第２スレッドが準備状態にあり、前記第１スレッドが前記通過状態にあり、実行が中断されていれば、前記第２スレッドの命令語を順次に実行する段階をさらに含みうる。
【００３９】
実行される現在命令語が、処理時間臨界値を超過すれば、前記第１スレッドの実行が中断されて、前記通過状態になりうる。
【００４０】
本発明のさらに他の実施形態による多重スレッド実行プロセッサは、準備状態にある第１スレッドの命令語を順次に実行するスレッド実行器と、前記第１スレッドが通過状態になれば、前記第１スレッドの実行を中断し、前記第１スレッドの状態が準備状態に戻って実行を続ける以前に待機するスレッド選択器と、を含み、前記スレッド実行器を使って、前記準備状態に戻った前記第１スレッドのあらゆる命令語を実行して、前記第１スレッドの実行を完了し、前記スレッド選択器を使って、前記実行が完了した第１スレッドを完了状態にする。
【００４１】
前記スレッド実行器は、第２スレッドが準備状態にあり、前記第１スレッドが前記通過状態にあり、実行が中断されていれば、前記第２スレッドの命令語を順次に実行することができる。
【００４２】
実行される現在命令語が、処理時間臨界値を超過すれば、前記第１スレッドの実行が中断されて、前記通過状態になりうる。
【発明の効果】
【００４３】
本発明の実施形態によれば、選択されたスレッドに対する実行が完了した後で、スレッド交換を行うか、または特定命令語を処理する場合にのみスレッド交換を行う。したがって、スレッド交換によるオーバーヘッドを減少させることができる。
【００４４】
そして、複数のスレッドの経路が同一かまたは同一ではなくても、プロセッシング資源を効率的に活用することができるために、制御フローが複雑な応用プログラムも効率的に動作させることができる。
【００４５】
同時に、レイテンシーが相対的に長い命令語を発行した以後には、スレッド交換を行って、他のスレッドを実行することができるので、効率的な資源活用とレイテンシー隠匿（ｌａｔｅｎｃｙ  ｈｉｄｉｎｇ）とが可能である。
【００４６】
また、スレッド交換時点を静的に固定することができるために、スレッド交換を判断するためのハードウェアロジックが必要なものではない。これは、ハードウェア構造を単純化して、チップのサイズを減らし、また消費電力を減らしうる。
【図面の簡単な説明】
【００４７】
【図１】本発明の一実施形態による多重スレッド実行プロセッサの構成を示すブロック図である。
【図２】本発明の他の実施形態による多重スレッド実行プロセッサの構成を示すブロック図である。
【図３】図２の多重スレッド実行プロセッサで１つのスレッドが有しうる状態、及びその変化を図式的に示すダイヤグラムである。
【図４】本発明の一実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。
【図５】本発明の他の実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。
【図６】本発明のさらに他の実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。
【図７】本発明のさらに他の実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。
【図８Ａ】例題プログラムコードの一例を示す図面であって、通過命令語に対する明示的な表示がない場合である。
【図８Ｂ】例題プログラムコードの他の例を示す図面であって、通過命令語に対する明示的な表示がある場合である。
【図８Ｃ】図８Ａ及び図８Ｂに示された例題プログラムコードの制御フローグラフを示す図面である。
【図９Ａ】図８Ａの例題プログラムコードに従い、またあらゆるスレッドの実行経路が同じである多重スレッドを既存の方法によって１つのプロセッシングユニットで実行する過程を示す図面である。
【図９Ｂ】図８Ａの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを既存の方法によって１つのプロセッシングユニットで実行する過程を示す図面である。
【図９Ｃ】図８Ａの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを既存の方法によって１つのプロセッシングユニットで実行する過程を示す図面である。
【図９Ｄ】図８Ａの例題プログラムコードに従い、またあらゆるスレッドの実行経路が同じである多重スレッドを一実施形態によって１つのプロセッシングユニットで実行する過程を示す図面である。
【図９Ｅ】図８Ａの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを一実施形態によって１つのプロセッシングユニットで実行する過程を示す図面である。
【図１０Ａ】図８Ａの例題プログラムコードに従い、またあらゆるスレッドの実行経路が同じである多重スレッドを既存の方法によって２つのプロセッシングユニットで実行する過程を示す図面である。
【図１０Ｂ】図８Ａの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを２つのプロセッシングユニットで実行する過程を示す図面である。
【図１０Ｃ】図８Ａの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを２つのプロセッシングユニットで実行する過程を示す図面である。
【図１０Ｄ】図８Ａの例題プログラムコードに従い、またあらゆるスレッドの実行経路が同じである多重スレッドを一実施形態によって２つのプロセッシングユニットで実行する過程を示す図面である。
【図１０Ｅ】図８Ａの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを一実施形態によって２つのプロセッシングユニットで実行する過程を示す図面である。
【図１１Ａ】図８Ｂの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを他の実施形態によって１つのプロセッシングユニットで実行する過程を示す図面である。
【図１１Ｂ】図８Ｂの例題プログラムコードに従い、またスレッドの実行経路の異なる多重スレッドを他の実施形態によって２つのプロセッシングユニットで実行する過程を示す図面である。
【発明を実施するための形態】
【００４８】
以下、添付図面を参照して、本発明の実施形態を詳細に説明する。使われる用語は、実施形態での機能を考慮して選択された用語であって、その用語の意味は、ユーザ、運用者の意図または慣例などによって変わりうる。したがって、後述する実施形態で使われた用語の意味は、本明細書に具体的に定義された場合には、その定義に従い、具体的な定義がない場合は、当業者が一般的に認識する意味として解釈されねばならない。
【００４９】
図１は、本発明の一実施形態による多重スレッド実行プロセッサの構成を示すブロック図である。図１を参照すれば、多重スレッド実行プロセッサ１０は、スレッド保存部（ｔｈｒｅａｄ  ｓｔｏｒａｇｅ  ｕｎｉｔ）１２またはスレッドストレージと、スレッド選択部（ｔｈｒｅａｄ  ｓｅｌｅｃｔｉｏｎ  ｕｎｉｔ）１４またはスレッド選択器（ｔｈｒｅａｄ  ｓｅｌｅｃｔｏｒ）と、スレッド実行部（ｔｈｒｅａｄ  ｅｘｅｃｕｔｉｏｎ  ｕｎｉｔ）１６またはスレッド実行器（ｔｈｒｅａｄ  ｅｘｅｃｕｔｏｒ）とを含む。図１に示されたプロセッサ１０の構成は、その機能によって論理的に区分したものであって、各構成要素は、物理的に別個に具現されるか、または２つ以上の構成要素が統合されて１つに具現されることもある。
【００５０】
多重スレッド実行プロセッサ１０は、同じプログラムコードを処理するための複数のスレッドを実行するプロセッサに関連する。同じプログラムコードを処理するための複数のスレッドは、‘多重スレッド（ｍｕｌｔｉｐｌｅ  ｔｈｒｅａｄｓ）’と称される。言い換えれば、多重スレッドは、同じプログラムコードを処理するスレッドの集合（ｔｈｒｅａｄ  ｐｏｏｌ）であると言える。プログラムコードに１つ以上の分岐発散と収斂が含まれている場合、多重スレッドは、いずれも同じ実行経路（ｅｘｅｃｕｔｉｏｎ  ｐａｔｈ）に沿って処理されるか、または互いに異なる実行経路に沿って処理されうる（図８Ｃ参照）。そして、互いに異なる複数の実行経路は、それぞれに対応するプログラムカウンター（Ｐｒｏｇｒａｍ  Ｃｏｕｎｔｅｒ、ＰＣ）によって定められうる。
【００５１】
このような多重スレッド実行プロセッサ１０は、ＣＰＵプロセッサ、ＧＰＵプロセッサ、ＧＰＧＰＵプロセッサなどであり、特定の種類に制限されない。多重スレッド実行プロセッサ１０は、１つ以上のプロセッサコア（ｐｒｏｃｅｓｓｏｒ  ｃｏｒｅ）を含み、各プロセッサコアは、１つまたはそれ以上のプロセッシングユニット（Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔｓ、ＰＵｓ）を含みうる。多重スレッドは、いずれもが１つのＰＵで処理されるか、または複数のＰＵｓで分散されて同時に処理される。
【００５２】
そして、多重スレッド実行プロセッサ１０は、任意のコンピューティングシステム、例えば、パソコン、エンターテイメントシステム、メディアシステム、ゲームシステム、通信デバイス、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、または１つ以上のプロセッサを使う任意のシステムで使われる。コンピューティングシステムは、プロセッサ以外に通常の入出力モジュールとメモリなどを含むが、これら構成要素は、バスを通じて互いに連結されうる。
【００５３】
多重スレッド実行プロセッサ１０は、１つ以上のプロセッサコアを含みうる。そして、１つのプロセッサコアは、１つあるいは多数のプロセッシングユニット（ＰＵ）で構成することができる。多数のプロセッシングユニット（ＰＵ）は、いずれも同じプログラムカウンター（ＰＣ）を使うか、またはそれぞれ固有のプログラムカウンター（ＰＣ）を使うことができる。前者の場合に、多数のプロセッシングユニット（ＰＵ）は、同じ実行経路のスレッドを実行するが、後者の場合に、多数のプロセッシングユニット（ＰＵ）は、それぞれ当該プログラムカウンター（ＰＣ）による実行経路のスレッドを実行するが、その実行経路は異なりうる。また、１つのプロセッシングユニットは、多数のスレッドを実行するが、１つのスレッドの実行完了後で、他のスレッドを実行する方式で多数のスレッドを実行することができる。
【００５４】
スレッド保存部１２は、多重スレッド実行プロセッサ１０で実行される複数のスレッドを保存するためのものである。スレッド保存部１２に保存されている複数のスレッドは、スレッド実行部１６で今後実行されなければならないスレッド、及び／またはスレッド実行部１６で既に実行が完了したスレッドであり得る。本実施形態の他の態様によれば、今後実行されなければならないスレッドと既に実行が完了したスレッドは、他の所に保存されうる。例えば、スレッドは、少なくとも１つのローカルキャッシュメモリ、ローカル保存部、またはネットワーク連結を通じて連結されているハードウェアドライブのような外部のストレージに保存されうる。以下、スレッド実行部１６で今後実行されなければならないスレッドは、‘初期状態’とも言い、スレッド実行部１６で既に実行が完了したスレッドは、‘完了状態’とも言う。本実施形態によれば、‘初期状態’のスレッドは、１つの命令語も処理されていない状態のスレッドを含む。本願において、文脈上、混乱のおそれがない限り「命令語」は「命令」と同義語として使用される。
【００５５】
スレッド保存部１２に保存されている複数のスレッドは、１つ以上の多重スレッドを含みうる。前述したように、多重スレッドは、同じプログラムコードを実行するスレッドの集合である。これは、多重スレッドが、例えば、グラフィックを構成する多数の頂点とピクセルのように同じ特性を有する多数のデータを処理するためのものであるということを意味するが、これに限定されるものではない。そして、多重スレッドのそれぞれの実行経路（一連の命令語）は、いずれも同じであるか、または互いに異なりうる。このような多重スレッドを構成する複数のスレッドのそれぞれは、互いに独立して実行可能であり、また同時に実行することもある。
【００５６】
実施形態の一態様によれば、実行されるスレッドとスレッドグループを選択及び／または決定することは、アルゴリズムによって決定される。実施形態の他の態様によれば、複数のアルゴリズムが、同じオペレーションを実行するが、互いに独立しているために、スレッドになりうる場合もある。例えば、イメージを構成する各ピクセルを処理する場合に、各ピクセルに対して独立したイメージ処理アルゴリズムが使われる。他の例として、３次元（３Ｄ）グラフィック処理を行う場合において、頂点とピクセル隠し（ｖｅｒｔｅｘ  ａｎｄ  ｐｉｘｅｌ  ｓｈａｄｉｎｇ）を行うための処理も含まれうる。
【００５７】
スレッド選択部１４は、スレッド保存部１２に保存されている複数のスレッドのうちからスレッド実行部１６で実行する何れか１つのスレッドを選択するためのものである。この場合に、スレッド選択部１４は、スレッド保存部１２に保存されているスレッドのうちから‘初期状態’であるスレッドをスレッド実行部１６で実行するスレッドに選択することができる。‘完了状態’のスレッドは、既にスレッド実行部１６で実行が完了したので、スレッド選択部１４によって選択されない。もし、‘初期状態’のスレッドが複数個である場合に、スレッド選択部１４は、複数個のスレッドを順次に選択するが、この際、スレッド実行部１６で実行するスレッドを選択するアルゴリズムに関して特別な制限はない。例えば、スレッド選択部１４は、複数のスレッドに対してラウンドロビン方式によってスレッド実行部１６で実行するスレッドを順次に選択することができる。
【００５８】
本実施形態の一側面によれば、スレッド選択部１４は、スレッド保存部１２に保存されている複数のスレッドのそれぞれの状態を指示する情報、例えば、‘スレッド状態情報’を活用して、スレッド実行部１６で実行するスレッドを選択することができる。このようなスレッド状態情報は、スレッド選択部１４を構成する所定の保存部に記録されて保存されるか、または別途の保存部（図示せず）に記録されて保存することができる。
【００５９】
スレッド状態情報は、スレッド選択部１４が生成して管理することができるが、そのフォーマットには、特別な制限がない。そのために、スレッド選択部１４は、スレッド保存部１２に保存されているスレッドの状態を持続的にモニタリングすることができる。実施形態によっては、スレッド選択部１４は、スレッド実行部１６から実行が完了したスレッドについての情報を伝達され、それを活用して、スレッド状態情報に反映することもできる。
【００６０】
スレッド実行部１６は、スレッド選択部１４によって選択されたスレッドを実行するためのものである。より具体的に、スレッド実行部１６は、スレッド選択部１４によって選択された‘初期状態’のスレッドを実行するが、当該スレッドの最初の命令語から最後の命令語まで処理する。言い換えれば、スレッド実行部１６は、当該スレッドの実行が完了するまでは、中間にスレッド交換なしに実行する。その結果、スレッド実行部１６では、スレッド選択部１４によって選択された順次に‘初期状態’のスレッド実行が完了すると当該スレッドは‘完了状態’になる。‘完了状態’のスレッドは、再びスレッド保存部１２に保存される。そして、具現例によっては、スレッド実行部１６は、当該スレッドの実行が完了したということを知らせる情報をスレッド選択部１４に伝達することもできる。
【００６１】
前述したスレッド選択部１４とスレッド実行部１６のそれぞれの機能は、多重スレッド実行プロセッサ１０が１つのプロセッシングユニット（ＰＵ）を備える場合である。もし、多重スレッド実行プロセッサ１０が、複数個のプロセッシングユニット（ＰＵ）を備えている場合であれば、スレッド選択部１４は、‘初期状態’のスレッドのうちからプロセッシングユニット（ＰＵ）の個数に対応する個数ほどスレッドを選択することができる。そして、スレッド実行部１６は、スレッド選択部１４によって選択された複数のスレッドのそれぞれを各プロセッシングユニット（ＰＵ）で同時に、そして、独立して実行することができる。
【００６２】
前述したように、一実施形態による多重スレッド実行プロセッサ１０は、プロセッシングユニット（ＰＵ）単位で‘初期状態’のスレッドを選択して実行するが、‘完了状態’になるまで実行を行う。そして、何れか１つのスレッドに対する実行が完了して初めて他のスレッドを選択して実行する。このような選択及び実行過程を繰り返せば、多重スレッドを構成する全体スレッドが完了状態になるまでスレッドを実行することができる。これによれば、多重スレッド実行プロセッサ１０、より具体的に、プロセッシングユニット（ＰＵ）は、常に何れか１つのスレッドを実行しているので、資源の効率的な活用が可能である。そして、スレッド交換による負担がないだけではなく、ハードウェア構成を簡単にできる。また、多重スレッドの経路が互いに異なって、制御フローが複雑な場合にも、効率的かつ迅速に全体スレッドを実行することができる。
【００６３】
図２は、本発明の他の実施形態による多重スレッド実行プロセッサの構成を示すブロック図である。図２を参照すれば、多重スレッド実行プロセッサ２０は、スレッド保存部２２、スレッド選択部２４、スレッド実行部２６、及びスレッド交換判断部（ｔｈｒｅａｄｓｗｉｔｃｈ  ｄｅｔｅｒｍｉｎｉｎｇ  ｕｎｉｔ）２８を含む。図２に示されたプロセッサ２０の構成も、その機能によって論理的に区分したものであって、各構成要素は、物理的には別個に具現されるか、または２つ以上の構成要素が統合されて１つに具現されることもある。
【００６４】
多重スレッド実行プロセッサ２０も、図１を参照して前述した多重スレッド実行プロセッサ１０と同様に、同じプログラムコードを処理するための複数のスレッドを実行するプロセッサと関連する。そして、多重スレッド実行プロセッサ２０は、ＣＰＵプロセッサ、ＧＰＵプロセッサ、ＧＰＧＰＵプロセッサなどであり、特定の種類に制限されない。多重スレッド実行プロセッサ２０は、１つ以上のプロセッサコアを含み、各プロセッサコアは、１つまたはそれ以上のプロセッシングユニット（ＰＵｓ）を含みうる。多重スレッドは、いずれもが１つのＰＵで処理されるか、または複数のＰＵｓで分散されて同時に処理される。また、多重スレッド実行プロセッサ２０は、任意のコンピューティングシステム、例えば、パソコン、エンターテイメントシステム、メディアシステム、ゲームシステム、通信デバイス、ＰＤＡ、または１つ以上のプロセッサを使う任意のシステムで使われる。
【００６５】
多重スレッド実行プロセッサ２０は、１つ以上のプロセッサコアを含みうる。そして、１つのプロセッサコアは、１つあるいは多数のプロセッシングユニットで構成することができる。また、１つのプロセッシングユニットは、多数のスレッドを実行するが、１つのプロセッサコアで動作する多数のスレッドが定められたコード領域ほどを実行した後で、スレッド交換を行う方式で多数のスレッドを実行することができる。これは、単独のＳＩＭＴアーキテクチャーにより制限される命令語をさらに拡張することにより、分岐発散及び収斂によらず、プログラム構造上、効率的な処理を可能にする数の命令を１つのスレッドが順次に処理し、その後にスレッド交換が行われることを意味する。この場合に、スレッド交換情報は、プログラマーが直接プログラムに明示するか、コンパイラあるいはそれと類似している形態のソフトウェアによって自動で生成されてもよい。
【００６６】
スレッド保存部２２は、多重スレッド実行プロセッサ２０で実行される複数のスレッドを保存するためのものである。スレッド保存部２２に保存されている複数のスレッドは、１つ以上の多重スレッドを含みうる。そして、多重スレッドのそれぞれの経路（一連の命令語）は、いずれも同じであるか、または互いに異なりうる。このような多重スレッドを構成する複数のスレッドのそれぞれは、互いに独立して実行可能であり、また同時に実行することもある。スレッド保存部２２に保存されている複数のスレッドは、‘準備状態’、‘完了状態’、または‘通過状態’であり得るが、これに関しては、図３を参照してより詳しく説明する。
【００６７】
図３は、本実施形態による多重スレッド実行プロセッサ２０のスレッド保存部２２に保存されているスレッドが有しうる状態、及びその変化を図式的に示すダイヤグラムである。図３を参照すれば、スレッドは、準備状態（Ｒｅａｄｙ）３２、通過状態（Ｐａｓｓｅｄ）３４、及び完了状態（Ｔｅｒｍｉｎａｔｅｄ）３６のうちの何れか１つの状態を有しうる。ここで、‘完了状態３６’は、スレッド実行部１６で既にその実行が完了したスレッドを示す。
【００６８】
‘準備状態３２’は、スレッド実行部２６で実行が始まるか、または再開されなければならないスレッドであって、まだその実行が完了していないスレッドを示す。言い換えれば、‘準備状態３２’は、当該スレッドが実行可能な状態にあることを意味する。‘準備状態３２’のスレッドは、１つの命令語も処理されていないスレッド、すなわちスレッドが生成された時の初期状態のスレッド（図１参照）を含むだけでなく、いくつかの命令を処理した後で、特定の命令を処理する場合に一時的に中断されているが、現在引き続き処理の準備が整っているスレッドも含む。したがって、‘準備状態’のスレッドは、図１で説明した‘初期状態’のスレッド及び一部命令語は処理されたが、‘完了状態’または通過状態３４ではないスレッドを含む。‘準備状態３２’のスレッドは、スレッド実行部２６で実行可能であり、実行途中で通過命令語を処理すれば、‘通過状態３４’に転移し、その実行を止めるが、あらゆる命令語を処理して、その実行が完了すれば、‘完了状態３６’に転移する。
【００６９】
そして、‘通過状態３４’は、スレッド実行部２６で特定の命令語を実行している途中でスレッド交換に起因して実行が一時的に止められたスレッドを示す。より具体的には、‘通過状態３４’は、スレッドを実行している最中に他のスレッドに移るスレッド交換が起こった状態であって、スレッド交換以前に発行された命令の処理が完了していない状態を示す。したがって、‘通過状態３４’のスレッドは、スレッド交換以前に発行された命令語の処理が完了するまで再開することができない。そして、スレッド交換以前に発行した命令語に対する処理が完了すれば、当該スレッドは、‘通過状態３４’から再び‘準備状態３２’に転移する。
【００７０】
言い換えれば、実施形態の一態様によれば、スレッドが、現在如何なる状態にあるかということは、当該スレッドが既に進行しており、また進行可能な処理量に依存すると言える。具体的に、準備状態は、スレッドの命令語のうち、何も実行されていないか、または一部のみ実行された状態であると理解され、より重要なのは、そのスレッドは、プロセッサによって実行する準備ができているか、または実行できるということである。そして、完了状態は、スレッドのあらゆる命令語が実行されて完了した状態である。最後に、通過状態は、スレッドが一部命令語は実行したが、依然としてペンディング（ｐｅｎｄｉｎｇ）中である又は処理が途中である他の命令語を有している状態であると理解されうる。そして、準備状態とは対照的に、通過状態のスレッドは、現在、プロセッサによる処理が不可能である（準備が整っていない）。これは、スレッドで次のアイテムのために必要な命令語がプロセッサによって現在は実行されないためである。
【００７１】
そして、実施形態の他の態様によれば、あるスレッドが実行されるために選択されたが、そのスレッドによって必要なプログラムの命令語の一部が既に処理され、また通過したならば、そのスレッドは、プログラムで指示する次の機会が再び到来するまでは通過状態にあり、その後に、そのスレッドは、準備状態になって選択されて実行可能である。処理済のスレッドは、如何なるものでも完了状態になるが、これは、処理が終わったことを示す。単純に言って、処理サイクルが進行する過程で中間に選択されるスレッドは、必要な命令語が再び利用可能であるまで待たなければならない。
【００７２】
また、実施形態のさらに他の態様によれば、プロセッサが以前に発行した命令語を依然として処理しているために、スレッドは通過状態になることもあり、現在処理されていないスレッドに到逹する如何なる命令語実行要請も、スレッドがさらに処理することができないことを意味する。したがって、もし、スレッドが現在処理されていない命令語にあれば、そのスレッドは止められなければならない。それは、準備状態にある他のスレッドに変えられてもよい。これにより、最初のスレッド状態は、“準備状態”から“通過状態”に変更される。プロセッサが変更して、そのスレッドによって要求される命令語を処理し始めるまで、そのスレッドは、このような状態で留まっているが、命令語を処理し始める時点は、そのスレッドが再び処理され、その結果、スレッドの状態が、“通過状態”から再び“準備状態”に変更されうる時点を示す。
【００７３】
また、実施形態のさらに他の態様によれば、プロセッサが命令語をスイッチし、それによって、スレッドが完了できず、また処理することができなければ、そのスレッドは、“通過状態”に進入することができる。この場合は、変更を行うことは、前述したようなスレッド交換命令語であるよりはプロセッサである。但し、その効果は同一であるが、プロセッサとスレッド命令語が、スレッドが再びプロセッサによって処理させて、そのスレッドが“準備状態”になるまで、そのスレッドの状態の“通過状態”に設定される。
【００７４】
このようなスレッドは、最初に生成された以後にスレッド保存部２２に保存されるが、最初には準備状態３２になる。そして、準備状態のスレッドは、スレッド実行部２６で実行されて通過状態３４になるか、または完了状態３６になりうる。後者の場合は、準備状態のスレッドのあらゆる命令語がスレッド実行部２６で処理されて、当該スレッドの実行が完了する場合である。一方、前者の場合は、準備状態のスレッドがスレッド実行部２６で命令語を順次に処理しながら途中で特定の命令（以下、‘通過命令（ｐａｓｓｅｄ  ｉｎｓｔｒｕｃｔｉｏｎ）’と称する）が発行された場合にスレッド交換が生じ、スレッド実行部２６でそれ以上の命令語が処理又は発行（issue）されない場合である。本願において、発行（issue）はイシューと表現されてもよい。この場合に、スレッド実行部２６では、スレッド選択部２４によって選択された他のスレッドの命令語が発行されて処理されうるが、但し、スレッド交換以前にスレッド実行部２６で既に発行された命令語である通過命令語は、一旦スレッド実行部２６によって一旦イシューになったので、処理が完了する。そして、通過命令語の処理が完了すれば、当該スレッドは、通過状態３４から再び準備状態３２に戻る。準備状態３２に戻ったスレッドは、今後再びスレッド選択部２４によって選択されてスレッド実行部３６で実行可能である。
【００７５】
次いで、図２を参照すれば、スレッド選択部２４は、スレッド保存部２２に保存されている複数のスレッドのうちからスレッド実行部２６で実行する何れか１つのスレッドを選択するためのものである。この場合に、スレッド選択部２４は、スレッド保存部２２に保存されているスレッドのうちから‘準備状態’であるスレッドを選択することができる。‘通過状態’のスレッドは、スレッド交換でその実行が中断され、また‘完了状態’のスレッドは、既にスレッド実行部２６で実行が完了したので、スレッド選択部１４によって選択されない。
【００７６】
もし、‘準備状態’のスレッドが複数個である場合に、スレッド選択部２４は、複数個のスレッドを順次に選択するが、この際、スレッド実行部２６で実行するスレッドを選択するアルゴリズムに関して特別な制限はない。例えば、スレッド選択部１４は、複数のスレッドに対してラウンドロビン方式によってスレッド実行部１６で実行するスレッドを順次に選択することができる。但し、‘準備状態’のスレッドのうちからまだその命令語の処理が開始もされていないスレッドと命令語のうちの一部に対する処理が完了したスレッド（図３で、通過状態３４から再び準備状態３２に復元したスレッド）とが混合されている場合には、前者のスレッドに優先順位を置いて選択がなされることもあるが、これは、単に例示的なものである。
【００７７】
スレッド選択部２４は、スレッド保存部２２に保存されている複数のスレッドのそれぞれの状態を指示する情報、例えば、‘スレッド状態情報’を活用して、スレッド実行部２６で実行するスレッドを選択することができる。このようなスレッド状態情報は、スレッド選択部２４を構成する所定の保存部に記録されて保存されるか、または別途の保存部（図示せず）に記録されて保存することができる。
【００７８】
スレッド状態情報は、スレッド選択部２４が生成して管理することができるが、そのフォーマットには、特別な制限がない。そのために、スレッド選択部２４は、スレッド保存部２２に保存されているスレッドの状態を持続的にモニタリングすることができる。実施形態によっては、スレッド選択部２４は、スレッド実行部２６から実行が完了したスレッドについての情報、及び／またはスレッド交換で通過状態になったスレッドに関する情報などを伝達され、それを活用して、スレッド状態情報に反映することもできる。
【００７９】
スレッド実行部２６は、スレッド選択部２４によって選択されたスレッドを実行するためのものである。より具体的に、スレッド実行部２６は、スレッド選択部２４によって選択された‘準備状態’のスレッドを実行する。スレッド実行部２６は、まだ１つの命令語も処理されていない準備状態のスレッドに対しては、最初命令語から順次に処理する。そして、スレッド実行部２６は、スレッド交換でその実行が中断された準備状態のスレッドに対しては、当該スレッドの実行を再開するが、この場合には、その実行が直前に止まった地点、すなわち、通過命令語の次の命令語から命令語を順次に処理する。
【００８０】
そして、スレッド実行部２６は、スレッドを実行しながら通過命令語を処理すれば、当該スレッドに対する実行を中断する。この場合に、実行が中断されたスレッドは、‘通過状態３４（図３参照）’になり、‘通過状態’のスレッドも、既に発行された命令語はスレッド実行部２６で引き続き処理されるということは前述した通りである。‘通過状態’のスレッドは、再びスレッド保存部２２に保存され、発行された命令語に対する処理が完了すれば、再び‘準備状態’になる。そして、具現例によっては、スレッド実行部２６が、当該スレッドの実行が中断されたということを知らせる情報（例えば、通過状態に変換されたということを知らせる情報）または発行された命令語の処理が完了したということを知らせる情報（例えば、通過状態から準備状態に変換されたということを知らせる情報）をスレッド選択部２４に伝達することもできる。実施形態によっては、当該スレッドの実行が中断されたということを知らせる情報（すなわち、通過状態に変換されたということを知らせる情報）は、スレッド交換判断部２８がスレッド選択部２４に伝達することもできる。
【００８１】
もし、スレッド実行部２６でスレッドを実行しながら通過命令語を処理せず、あらゆる命令語を処理すれば、当該スレッドは、実行が完了して‘完了状態３６（図３参照）’になる。‘完了状態’のスレッドは、再びスレッド保存部２２に保存される。そして、具現例によっては、スレッド実行部２６が、当該スレッドの実行が完了したということを知らせる情報をスレッド選択部２４に伝達することもできる。
【００８２】
スレッド交換判断部２８は、スレッド実行部２６で実行するスレッドの現在処理対象となる命令語が通過命令語であるか否かを判断するためのものである。例えば、スレッド交換判断部２８は、スレッド選択部２４によって選択されたスレッドの命令語を１つずつフェッチ及び復号（ｆｅｔｃｈ＆ｄｅｃｏｄｅ）して、スレッド実行部２６で実行させながら、当該命令語が通過命令語に該当するか否かを判断することができる。もし、通過命令語ではない場合には、当該命令語は、スレッド実行部２６で処理され、次いで、スレッド交換判断部２８は、その次の命令語が通過命令語であるか否かを判断する。一方、通過命令語である場合には、当該命令語は、スレッド実行部２６で処理されるが、その後には、他のスレッドがスレッド実行部２６で実行されるように、スレッド選択部２４は、他のスレッドを選択する。そのために、スレッド交換判断部２８は、判断の結果（例えば、フェッチ及び復号された命令語が通過命令語であるか否かを指示する情報）をスレッド選択部２４に伝達することができる。
【００８３】
本実施形態によれば、スレッド交換判断部２８が、現在処理対象となる命令語が通過命令語であるか否かを判断する方法は多様に具現されうる。一例として、スレッド交換判断部２８は、当該命令語が通過命令語であるということを明示的に指示するスレッド交換情報（ｔｈｒｅａｄ  ｓｗｉｔｃｈｉｎｇ  ｉｎｆｏｒｍａｔｉｏｎ）を用いて判断することができる（図８Ｂで、参照番号４２の“＊”表示参照）。そのために、プログラムコードの作成（例えば、命令語セットアーキテクチャー（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ａｒｃｈｉｔｅｃｔｕｒｅ、ＩＳＡ）エンコーディング）時に、このようなスレッド交換情報が含まれるようにエンコーディングになりうる。スレッド交換情報は、プログラマーが任意に含ませるか、または既定のアルゴリズムによってエンコーディング時に自動的に含まれることもある。
【００８４】
または、たとえ通過情報に関する明示的な表示がないとしても、スレッド交換判断部２８は、当該命令語が通過命令語であるか否かを判断することができる。一例として、スレッド交換判断部２８は、通過命令語に関する情報をあらかじめ有しており、それを活用して、復号及びフェッチされた命令語が通過命令語であるか否かを判断することができる。
【００８５】
他の例として、スレッド交換判断部２８は、命令語のレイテンシー（ｌａｔｅｎｃｙ）に基づいて復号及びフェッチされた命令語が通過命令語であるか否かを判断することもできるが、この場合に、レイテンシーが所定の値以上である命令語のみを通過命令語と判断することができる。このように、命令語のレイテンシーが相対的に大きな命令語を通過命令語と判断すれば、当該命令語が処理されれば、スレッド交換が起こるために、レイテンシー隠匿（ｌａｔｅｎｃｙ  ｈｉｄｉｎｇ）が可能である。命令語のレイテンシーを活用するこのような方法は、これに限定されるものではなく、明示的な通過情報を活用する例を含んで前述したあらゆる例に共通して適用されることもある。
【００８６】
前述したように、多重スレッド実行プロセッサ２０も、準備状態のスレッドのうちから選択されたスレッドを実行する。この際、選択されたスレッドが、最初に選択されるスレッドであれば、最初命令語から処理を行うが、通過状態になってから再び準備状態に復元されたスレッドであれば、中断された地点（通過命令語の次の命令語）から処理を行う。そして、スレッドの実行中に処理される命令語が通過命令語に該当すれば、多重スレッド実行プロセッサ２０は、スレッド交換を行って、他のスレッドを選択して実行を始めるか、再開する。この際、スレッド交換以前に実行されたスレッドは、通過状態になり、通過命令語に対する処理が完了すれば、再び準備状態になる。次いで、スレッドの実行中にそれ以上通過命令語が処理されなければ、当該スレッドは、実行が完了して完了状態になる。一方、実行完了前に通過命令語が処理されれば、再びスレッド交換手続きが進行する。そして、このような過程は、保存された命令語がいずれも完了状態になるまで続く。
【００８７】
前述したスレッド選択部２４、スレッド実行部２６、及びスレッド交換判断部２８のそれぞれの機能は、多重スレッド実行プロセッサ２０が１つのプロセッシングユニット（ＰＵ）を備える場合である。もし、多重スレッド実行プロセッサ２０が、複数個のプロセッシングユニット（ＰＵ）を備えている場合であれば、スレッド選択部２４は、‘準備状態’のスレッドのうちからプロセッシングユニット（ＰＵ）の個数に対応する個数ほどスレッドを選択することができる。そして、スレッド実行部２６は、スレッド選択部２４によって選択された複数のスレッドのそれぞれを各プロセッシングユニット（ＰＵ）で同時に、そして、独立して実行することができる。また、スレッド実行部２６が、選択されたスレッドを実行する過程でスレッド交換を行うか否かも、各プロセッシングユニット（ＰＵ）で個別的に判断することができる。
【００８８】
前述したように、多重スレッド実行プロセッサ２０は、プロセッシングユニット（ＰＵ）単位で‘準備状態’のスレッドを選択して実行する。このような選択及び実行過程を繰り返せば、多重スレッドを構成する全体スレッドが完了状態になるまでスレッドを実行することができる。これによれば、多重スレッド実行プロセッサ２０、より具体的に、プロセッシングユニット（ＰＵ）は、常に何れか１つのスレッドを実行しているので、資源の効率的な活用が可能である。そして、スレッド交換による負担がないだけではなく、ハードウェア構成を簡単にできる。また、多重スレッドの経路が互いに異なって、制御フローが複雑な場合にも、効率的かつ迅速に全体スレッドを実行することができる。
【００８９】
図４は、本発明の一実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。図４に示されたフローチャートは、図１に示された多重スレッド実行プロセッサ１０の動作方法であり得る。したがって、以下、不要な重複説明を防止するために、動作方法に関して簡略に説明する。したがって、ここで詳しく説明されていない事項は、図１を参照して前述した事項が同様に適用可能である。
【００９０】
図１及び図４を参照すれば、多重スレッド実行プロセッサ１０は、初期状態のスレッドのうちから１つのスレッドを選択する（ステップＳ１０１）。前述したように、多重スレッド実行プロセッサ１０のスレッド保存部１２は、初期状態のスレッド及び／または完了状態のスレッドを保存し、スレッド選択部１４は、そのうちから初期状態のスレッドのうちの何れか１つを選択することができる。そして、多重スレッド実行プロセッサ１０のスレッド実行部１６は、選択されたスレッドを実行する（ステップＳ１０２）。その次に、段階Ｓ１０４で実行中であるスレッドの実行が完了したか否かを判断するが（ステップＳ１０３）、判断の結果、実行が完了していなければ、選択されたスレッドを実行し続ける（ステップＳ１０２）。そして、段階Ｓ１０３での判断の結果、段階Ｓ１０４で実行中であるスレッドの実行が完了したならば、スレッド保存部１２に準備状態のスレッドがあるか否かを判断する（ステップＳ１０４）。段階Ｓ１０４での判断の結果、スレッド保存部１２に初期状態のスレッドがさらにあれば、前述した段階Ｓ１０１ないしＳ１０４の過程を繰り返す。一方、段階Ｓ１０４での判断の結果、スレッド保存部１２に初期状態のスレッドがなく、完了状態のスレッドのみ存在すれば、当該多重スレッドに対する実行は終了する。
【００９１】
図５は、本発明の他の実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。図５に示されたフローチャートは、図２に示された多重スレッド実行プロセッサ２０の動作方法であり得る。したがって、以下、不要な重複説明を防止するために、動作方法に関して簡略に説明する。したがって、ここで詳しく説明されていない事項は、図２を参照して前述した事項が同様に適用可能である。
【００９２】
図２及び図５を参照すれば、多重スレッド実行プロセッサ２０は、準備状態のスレッドのうちから１つのスレッドを選択する（ステップＳ１１１）。前述したように、多重スレッド実行プロセッサ２０のスレッド保存部２２は、準備状態のスレッド、通過状態のスレッド、及び／または完了状態のスレッドを保存し、スレッド選択部２４は、そのうちから準備状態のスレッドのうちの何れか１つを選択することができる。そして、多重スレッド実行プロセッサ２０のスレッド実行部２６は、選択されたスレッドを実行する（ステップＳ１１２）。
【００９３】
その次に、段階Ｓ１１２で実行中であるスレッドの実行が完了したか否かを判断する（ステップＳ１１３）。判断の結果、選択されたスレッドの実行が完了していなければ、スレッド交換判断部２８は、スレッド交換を行うか否かを判断する（ステップＳ１１４）。もし、スレッド交換と判定され、これにより、実行されているスレッドが“通過状態”に変更されれば、追加的な実行は中止される（ステップＳ１１５）。これは、現在処理されている命令語が通過命令語であるかによって判定されうる。選択されたスレッドの実行が完了したならば、スレッド交換判断部２８は、スレッド保存部２２に準備状態のスレッドがさらにあるか否かを判断する（ステップＳ１１６）。段階Ｓ１１４での判断の結果、スレッド交換を行えなければ、スレッド実行部２６は、選択されたスレッドの実行を続く（ステップＳ１１２）。しかし、段階Ｓ１１４での判断の結果、スレッド交換を行えば、段階Ｓ１１５で実行中であるスレッドは、通過状態で変換し、当該スレッドの実行を中断する。
【００９４】
次いで、段階Ｓ１１３でスレッドの実行が完了したと判断されるか、または段階Ｓ１１４と段階Ｓ１１５とでスレッド交換を行えば、スレッド保存部２２に準備状態のスレッドがさらに存在するか否かを判断する（ステップＳ１１６）。もし、スレッド保存部２２に準備状態のスレッドがさらに存在すれば、段階Ｓ１１１以下の過程を再び行う。一方、スレッド保存部２２に準備状態のスレッドが存在しなければ、スレッド保存部２２に通過状態のスレッドが存在するか否かを判断する（ステップＳ１１７）。段階Ｓ１１７での判断の結果、通過状態のスレッドも存在せず、完了状態のスレッドのみ存在すれば、当該多重スレッドに対する実行は終了する。一方、通過状態のスレッドが存在すると判断されれば、通過状態のスレッドが準備状態になるまで待機した後、以後には、段階Ｓ１１１以下の過程を再び行う。
【００９５】
図６は、本発明のさらに他の実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。図６に示されたフローチャートは、図１または図２に示された多重スレッド実行プロセッサ１０、２０が１つのスレッドの実行を再開するフローチャートであり得る。前述したように、多重スレッド実行プロセッサ１０、２０は、各プロセッシングユニット（ＰＵ）で実行する多数のスレッドを保存及び管理し、これらのうちから与えられた時間に実行する１つのスレッドを選択して、プロセッシングユニット（ＰＵ）で実行させる。
【００９６】
そして、図６に示されたフローチャートは、図４または図５を参照して前述した動作方法と実質的に同一であり得る。但し、図６のフローチャートは、図４または図５のフローチャートとは表面的に差があるが、これは、単に観点の差による表面的な差であり、実質的には、互いに類似している。したがって、ここで詳しく説明されていない事項は、図４または図５を参照して説明した事項が同様に適用可能である。
【００９７】
図６を参照すれば、多重スレッド実行プロセッサは、多重スレッドを構成する複数のスレッド全部が完了状態であるか否かを判断する（ステップＳ１２１）。判断の結果、あらゆるスレッドが完了状態（あらゆるスレッドが、既に正常に実行完了した状態）であれば、多重スレッド実行プロセッサは、当該多重スレッドの実行を終了する。一方、少なくとも１つのスレッドが完了状態ではなければ、準備状態（図１の初期状態を含む。以下、本実施形態で同一である）のスレッドが存在するか否かを判断する（ステップＳ１２２）。判断の結果、準備状態のスレッドがなければ、準備状態のスレッドを待った後（ステップＳ１２３）、段階Ｓ１２２の過程を繰り返す。一方、段階Ｓ１２２で少なくとも１つの準備状態のスレッドが存在すれば、多重スレッド実行プロセッサは、準備状態のスレッドのうちから１つのスレッドを選択し、当該スレッドにスイッチして実行する（ステップＳ１２４）。選択されたスレッドを実行する具体的な過程の一例は、後述する図７に示されている。そして、選択されたスレッドの実行が止めれば、多重スレッド実行プロセッサは、再び段階Ｓ１２１以下の過程を繰り返す。
【００９８】
図７は、本発明のさらに他の実施形態による多重スレッド実行プロセッサの動作方法を示すフローチャートである。図７に示されたフローチャートは、図１または図２に示された多重スレッド実行プロセッサ１０、２０の動作方法であり得るが、これに限定されるものではない。そして、図７に示されたフローチャートは、図４または図５を参照して前述した動作方法と実質的に同一であり、但し、多重スレッド実行プロセッサで特定の１つのスレッドを実行し、管理する観点で記述したフローチャートであるという点で、図４または図５のフローチャートと表面的に差がある。したがって、ここで詳しく説明されていない事項は、図４または図５を参照して説明した事項が同様に適用可能である。
【００９９】
図７を参照すれば、多重スレッド実行プロセッサは、実行中であるスレッドの第ｉ番目の命令語をイシューして処理する（ステップＳ１３１）。実行中であるスレッドは、ｎ（ｎは、２以上の整数）個の命令語で構成することができるが、この際、ｉは、１とｎとの間の任意の整数である。そして、第ｉ番目の命令語に対する処理が完了すれば、当該スレッドの実行が完了したか否かを判断する（ステップＳ１３２）。判断の結果、当該スレッドの実行が完了していないと判断されれば、処理された第ｉ番目の命令語が通過命令語であるか否かを判断する（ステップＳ１３３）。判断の結果、第ｉ番目の命令語が通過命令語ではなければ、ｉの値を１増加させて（ステップＳ１３４）、再び段階Ｓ１３１以下の過程を繰り返す。一方、第ｉ番目の命令語が通過命令語と判断されれば、当該スレッドの実行を止め、また通過状態で管理する（ステップＳ１３５）。一方、段階Ｓ１３２での判断の結果、当該スレッドの実行が完了したと判断されれば、実行完了した当該スレッドを完了状態で管理する（ステップＳ１３６）。
【０１００】
次いで、例題プログラムコードを用いて実施形態による多重スレッド実行プロセッサの動作方法を既存のＳＩＭＴアーキテクチャーによる動作方法と比較して説明する。以下、たとえ特定プログラムコードを用いて説明するが、これは、単に例示的なものであるということは当業者に自明である。前述した実施形態は、例示したプログラムコード以外に他のプログラムコードを処理する場合にも適用可能である。
【０１０１】
図８Ａ及び図８Ｂは、それぞれ例題プログラムコードの一例を示す図面であって、図８Ａは、スレッド交換情報がプログラムコードに明示的に表示されていない場合であり、図８Ｂは、スレッド交換情報がプログラムコードの特定命令語に明示的に表示された場合である。このような特定命令語は、通過命令語と見なされる。図８Ａ及び図８Ｂで、左側カラムは、プログラムカウンター（ＰＣ）であり、右側カラムは、各ＰＣでの命令語である。そして、図８Ａ及び図８Ｂの右側カラムに示したように、プログラムコードは、その制御フローによって１つ以上の命令語のグループＬ０〜Ｌ９の集合と見なされる。図８Ｂでは、ｌｄｗ命令語が全部通過命令語で表示されているが、これは、単に例示的なものである。このような通過命令語を指示する表示（スレッド交換情報）は、プログラマーが手動で表示するか、所定のソフトウェアやハードウェアによって自動で表示されるということは前述した通りである。
【０１０２】
以下、図８Ａの例題プログラムコードを用いて、図４の多重スレッド実行プロセッサの動作方法を例示的に説明し、図８Ｂの例題プログラムコードを用いて、図５の多重スレッド実行プロセッサの動作方法を例示的に説明する。しかし、図８Ａの例題プログラムコードも、たとえ明示的にスレッド交換情報が表示されていないが、内部アルゴリズムなどによって特定命令語（通過命令語）でスレッド交換になる場合には、図５の多重スレッド実行プロセッサの動作方法によって処理されるということは前述した通りである。
【０１０３】
図８Ｃは、図８Ａ及び図８Ｂに示された例題プログラムコードの制御フローグラフ（Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｇｒａｐｈ、ＣＦＧ）を示す図面である。図示の便宜上、図８Ｃには、図８Ｂに表示されているスレッド交換情報は表示していない。図８Ｃを参照すれば、例題プログラムコードは、２回の分岐を有するので、２つの分岐又はブランチを比較することにより、全部で４個の経路のうちの１つの経路を通じて処理されるということが分かる。４個の経路は、次の通りである。
【０１０４】
−経路Ｐ０：Ｌ０→Ｌ１→Ｌ２→Ｌ４→Ｌ９
−経路Ｐ１：Ｌ０→Ｌ１→Ｌ３→Ｌ４→Ｌ９
−経路Ｐ２：Ｌ０→Ｌ５→Ｌ６→Ｌ８→Ｌ９
−経路Ｐ３：Ｌ０→Ｌ５→Ｌ７→Ｌ８→Ｌ９
図９Ａ、図９Ｂ及び図９Ｃ、図９Ｄ、及び図９Ｅは、それぞれ１つのプロセッシングユニット（ＰＵ）を備える多重スレッド実行プロセッサが、図８Ａの例題プログラムコードを実行する過程を示すものであって、図９Ｂと図９Ｃは、図示の便宜上、２つの図面に分離して図示されている。図９Ａないし図９Ｅには、１つのプロセッシングユニット（ＰＵ）が、８個のスレッドを実行する場合を仮定した。そして、図９Ａと図９Ｂ及び図９Ｃは、既存のＳＩＭＴアーキテクチャーによる多重スレッド実行プロセッサでの実行過程であり、図９Ｄ及び図９Ｅは、図１に示された一実施形態による多重スレッド実行プロセッサでの実行過程であり得る。また、図９Ａ及び図９Ｄは、プロセッシングユニット（ＰＵ）で実行される８個のスレッドＴ０〜Ｔ７がいずれも同じ経路、すなわち、経路Ｐ０のみに沿う場合を仮定し、図９Ｂ及び図９Ｃと図９Ｅは、８個のスレッドＴ０〜Ｔ７が、４個の経路Ｐ０〜Ｐ３に分散されて沿う場合であって、スレッドＴ０及びＴ１は、経路Ｐ０、スレッドＴ２及びＴ３は、経路Ｐ１、スレッドＴ４及びＴ５は、経路Ｐ２、そして、スレッドＴ６及びＴ７は、経路Ｐ３に沿う場合を仮定した。
【０１０５】
図９Ａと図９Ｂ及び図９Ｃを参照すれば分かるように、既存のＳＩＭＴアーキテクチャーでは、同じプログラムカウンター（ＰＣ）で読み取られた命令語が全てのスレッドに対して同時に処理される。例えば、プログラムカウンター（ＰＣ）が０×００番地である時、メモリで読み取った’ａｄｄ’命令語を全てのスレッドＴ０〜Ｔ７が処理した後、次のプログラムカウンターに移動する。図９Ａと図９Ｂ及び図９Ｃで、プログラムカウンター（ＰＣ）の変わる時点は、太い実線で表示されている。このような実行方法によれば、１つの命令語の実行に最大８回のスレッド交換が暗黙的に発生することがある。
【０１０６】
図９Ａを参照すれば、全てのスレッドＴ０〜Ｔ７が同じ経路に沿う場合には、各プログラムカウンター（ＰＣ）で得られた命令語は、あらゆるスレッドに対して処理されうる。これによれば、毎プログラムカウンター（ＰＣ）ごとに命令語が処理されないスレッドがないので、プロセッシング資源の活用度が１００％である。これは、既存のＳＩＭＴアーキテクチャーによる多重スレッド実行プロセッサは、あらゆるスレッドの経路が同一である場合に、資源活用度の側面で非常に効果的であるということを示す。
【０１０７】
一方、図９Ｂ及び図９Ｃに示したように、スレッドＴ０〜Ｔ７の経路が異なる場合には、特定プログラムカウンター（ＰＣ）では、一部スレッドに対しては命令語が処理されない。なぜならば、ＳＩＭＴアーキテクチャーでは、同じプログラムカウンター（ＰＣ）で得られた命令語があらゆるスレッドに対して処理されなければならないが、場合によっては、その命令語は、一部スレッドの制御経路上には実行されてはならない命令語であるためである。例えば、０×０３番地のｌｄｗ命令語は、スレッドＴ０、Ｔ１、Ｔ２、Ｔ３に対しては処理されなければならないが、残りのスレッド、すなわち、Ｔ４、Ｔ５、Ｔ６、Ｔ７に対しては処理されてはならない（図９Ｂ及び図９Ｃでは、これが、斜線領域に表示されている）。これによれば、一部プログラムカウンター（ＰＣ）では、一部スレッドに対しては命令語が処理されないために、プロセッシング資源の活用度が１００％未満になるしかない。これは、既存のＳＩＭＴアーキテクチャーによる多重スレッド実行プロセッサは、スレッドの経路が異なる場合には、資源活用度が低下するということを示す。
【０１０８】
一方、図９Ｄ及び図９Ｅを参照すれば分かるように、一実施形態による多重スレッド実行プロセッサの動作方法では、選択された何れか１つのスレッドに対する実行を完了した後で、次のスレッドを実行する。これは、図９Ｄのように、あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合でも、または図９Ｅのように、スレッドＴ０〜Ｔ７の経路が異なる場合でも同一である。図９Ｄ及び図９Ｅで、スレッド交換が起こる時点は、太い実線で表示されている。スレッド交換は、ラウンドロビン（ｒｏｕｎｄ−ｒｏｂｉｎ）アルゴリズムのように、あらゆるスレッドが均等に選択されうるアルゴリズムによってなされ、これに対する特別な制限はない。そして、実行しなければならないスレッドの個数に該当する８回のスレッド交換以後に、あらゆるスレッドに対する実行を終わらせることができる。
【０１０９】
このような実施形態による動作方法と既存のＳＩＭＴアーキテクチャーによる動作方法とを比べると、既存のＳＩＭＴアーキテクチャーでは、１つのプロセッシングユニット（ＰＵ）が同時に８個のスレッドを実行させるのに反して、実施形態では、プロセッシングユニット（ＰＵ）が８個のスレッドを順次に実行させる。あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合、既存の方法はもとより、実施形態も、プロセッシング資源を効率的に使うという点で差がない。一方、スレッドＴ０〜Ｔ７が異なる経路に沿う場合、既存方法では、プロセッシング資源の使用効率が低下することとは異なって、実施形態では、あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合と同様にプロセッシング資源を効率的に使うことができる。
【０１１０】
図１０Ａ、図１０Ｂ及び図１０Ｃ、図１０Ｄ、及び図１０Ｅは、それぞれ２つのプロセッシングユニットＰＵ０、ＰＵ１を備える多重スレッド実行プロセッサが図８Ａの例題プログラムコードを実行する過程を示すものであって、図１０Ｂと図１０Ｃは、図示の便宜上、２つの図面に分離して図示されている。図１０Ａないし図１０Ｅでは、プロセッシングユニットＰＵ０、ＰＵ１は、それぞれ４個のスレッドを実行する場合であって、プロセッシングユニットＰＵ０は、スレッドＴ０、Ｔ１、Ｔ２、Ｔ３を実行し、プロセッシングユニットＰＵ１は、スレッドＴ４、Ｔ５、Ｔ６、Ｔ７を実行すると仮定した。そして、図１０Ａと図１０Ｂ及び図１０Ｃは、既存のＳＩＭＴアーキテクチャーによる多重スレッド実行プロセッサでの実行過程であり、図１０Ｄ及び図１０Ｅは、図１に示された実施形態による多重スレッド実行プロセッサでの実行過程であり得る。また、図１０Ａ及び図１０Ｄは、プロセッシングユニットＰＵ０、ＰＵ１で実行される８個のスレッドＴ０〜Ｔ７がいずれも同じ経路、すなわち、経路Ｐ０のみに沿う場合を仮定し、図１０Ｂ及び図１０Ｄは、８個のスレッドＴ０〜Ｔ７が４個の経路Ｐ０〜Ｐ３に分散されて沿う場合であって、スレッドＴ０及びＴ１は、経路Ｐ０、スレッドＴ２及びＴ３は、経路Ｐ１、スレッドＴ４及びＴ５は、経路Ｐ２、そして、スレッドＴ６及びＴ７は、経路Ｐ３に沿う場合を仮定した。
【０１１１】
図１０Ａと図１０Ｂ及び図１０Ｃを参照すれば分かるように、既存のＳＩＭＴアーキテクチャーでは、２つのプロセッシングユニットＰＵ０、ＰＵ１でスレッドを実行する場合にも、同じプログラムカウンター（ＰＣ）の命令語があらゆるスレッドに対して同時に処理する。すなわち、ＳＩＭＴアーキテクチャーでは、２つのプロセッシングユニットＰＵ０、ＰＵ１が同じプログラムカウンター（ＰＣ）を使う。図１０Ａと図１０Ｂ及び図１０Ｃでも、プログラムカウンター（ＰＣ）の変わる時点は、太い実線で表示されている。このような実行方法によれば、１つの命令語の実行に各プロセッシングユニットＰＵ０、ＰＵ１ごとに最大４回のスレッド交換が暗黙的に発生することがある。そして、２つのプロセッシングユニットＰＵ０、ＰＵ１でスレッドを実行する場合でも、１つのプロセッシングユニットでスレッドを実行する場合（図９Ａと図９Ｂ及び図９Ｃ参照）と同様に、あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合には、プロセッシング資源の活用度が１００％であるが、スレッドＴ０〜Ｔ７の経路が異なる場合には、資源活用度が低下する（図１０Ｂ及び図１０Ｃでも、当該プログラムカウンターで発行された命令語が処理されないスレッドは、斜線領域に表示されている）。
【０１１２】
一方、図１０Ｄ及び図１０Ｅを参照すれば分かるように、各プロセッシングユニットＰＵ０、ＰＵ１は、ＳＩＭＴアーキテクチャーと異ならせてそれぞれ別個のプログラムカウンターＰＣ０、ＰＣ１を使う。これらプログラムカウンターＰＣ０、ＰＣ１は、プログラムコードを実行する複数の実行経路のうちの何れか１つの実行経路を特定する。そして、実施形態による多重スレッド実行プロセッサの動作方法では、選択された何れか１つのスレッドに対する実行を完了した後で、次のスレッドを実行する。これは、図１０Ｄのように、あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合でも、または図１０Ｅのように、スレッドＴ０〜Ｔ７の経路が異なる場合でも同一である。例えば、プロセッシングユニットＰＵ０は、スレッドＴ０、Ｔ１、Ｔ２、Ｔ３の順序でスレッドを実行し、プロセッシングユニットＰＵ１は、スレッドＴ４、Ｔ５、Ｔ６、Ｔ７の順序でスレッドを実行する。図１０Ｄ及び図１０Ｅでも、スレッド交換が起こる時点は、太い実線で表示されている。そして、各プロセッシングユニットＰＵ０、ＰＵ１ごとに実行しなければならないスレッドの個数に該当する４回のスレッド交換以後に、あらゆるスレッドに対する実行を終わらせることができる。
【０１１３】
このような実施形態による動作方法と既存のＳＩＭＴアーキテクチャーによる動作方法とを比べると、既存のＳＩＭＴアーキテクチャーでは、プロセッシングユニットＰＵ０、ＰＵ１がそれぞれ同時に４個のスレッドを実行させるのに反して、実施形態では、プロセッシングユニットＰＵ０、ＰＵ１がそれぞれ４個のスレッドを順次に実行させる。あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合、既存の方法はもとより、本発明の実施形態も、プロセッシング資源を効率的に使うという点で差がない。一方、スレッドＴ０〜Ｔ７が異なる経路に沿う場合、既存方法では、プロセッシング資源の使用効率が低下することとは異なって、実施形態では、あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合と同様に、プロセッシング資源を効率的に使うことができる。
【０１１４】
図１１Ａ及び図１１Ｂは、１つまたは２つのプロセッシングユニット（ＰＵ）を備える多重スレッド実行プロセッサが一実施形態によって図８Ｂの例題プログラムコードを実行する過程を示す図面である。前述したように、図８Ｂの例題プログラムコードは、特定命令語（通過命令語）にスレッド交換情報が表示されているプログラムコードである。図１１Ａでは、１つのプロセッシングユニット（ＰＵ）が８個のスレッドを実行する場合を仮定した。そして、図１１Ｂでは、２つのプロセッシングユニットＰＵ０、ＰＵ１がそれぞれ４個のスレッドを実行する場合を仮定したが、各プロセッシングユニットＰＵ０、ＰＵ１は、それぞれ別個のプログラムカウンターＰＣ０、ＰＣ１を使う。そして、図１１Ａ及び図１１Ｂは、８個のスレッドＴ０〜Ｔ７が４個の経路Ｐ０〜Ｐ３に分散されて沿う場合であって、スレッドＴ０及びＴ１は、経路Ｐ０、スレッドＴ２及びＴ３は、経路Ｐ１、スレッドＴ４及びＴ５は、経路Ｐ２、そして、スレッドＴ６及びＴ７は、経路Ｐ３に沿う場合を仮定した。たとえ図面には図示されていないが、８個のスレッドＴ０〜Ｔ７がいずれも同じ経路、例えば、経路Ｐ０に沿う場合は、図１１Ａ及び図１１Ｂに示された原理が同様に適用可能であるということは当業者に自明である。
【０１１５】
図１１Ａ及び図１１Ｂを参照すれば、一実施形態による多重スレッド実行プロセッサの動作方法では、選択された何れか１つのスレッドに対する実行中に発行された命令語が通過命令語であれば、プロセッシングユニットは、スレッド交換を行って、他のスレッドを選択して実行する。例えば、図１１Ａ及び図１１Ｂでは、ｌｄｗが発行されて処理される度にプロセッシングユニットＰＵ０、ＰＵ１はスレッド交換を行う。この際、以前スレッドは、通過状態になるが、発行された通過命令語に対する処理が完了すれば、再び準備状態になる。図１１Ａ及び図１１Ｂで、スレッド交換が起こる時点は、太い実線で表示されている。このような方式であらゆるスレッドに対する処理が完了するまで通過命令語でスレッド交換を行いながら、スレッドを順次に実行する。これは、あらゆるスレッドＴ０〜Ｔ７が同じ経路に沿う場合も、図１１Ａ及び図１１Ｂのように、スレッドＴ０〜Ｔ７の経路が異なる場合と同様に適用可能である。スレッド交換は、ラウンドロビンアルゴリズムのように、あらゆるスレッドが均等に選択されうるアルゴリズムによってなされ、これに対する特別な制限はない。
【０１１６】
このような実施形態による動作方法によれば、８個のスレッドの経路が同一かまたは同一ではなくても、効率的なプロセッシング資源の活用が可能である。同時に、ロード命令語（ｌｏａｄ  ｉｎｓｔｒｕｃｔｉｏｎ）のように、レイテンシーが長い命令語である場合に、スレッド交換をなさせることによって、長いレイテンシーを隠すことが可能である。例えば、スレッドＴ０の０×０３番地で発行されたｌｄｗ命令語は、今後スレッドＴ０が再び実行される時点まで処理が完了すれば、プロセッシングユニットＰＵ、ＰＵ０、ＰＵ１は止まらず、実行し続けられる。したがって、複雑な制御フローを有したプログラムを資源効率を落とさないながらも、レイテンシーが長い命令語（ｌｏｎｇ−ｌａｔｅｎｃｙ  ｉｎｓｔｒｕｃｔｉｏｎ）のレイテンシーを隠すことが可能である。
【０１１７】
以上の説明は、実施形態に過ぎず、これによって限定されると解釈されてはならない。本発明の技術思想は、特許請求の範囲に記載の発明によってのみ特定されなければならない。したがって、前述した実施形態が、多様な形態で変形されて具現可能であるということは当業者に自明である。
【０１１８】
本発明は、多重スレッド実行プロセッサ、及びその動作方法関連の技術分野に適用可能である。
【０１１９】
以下、本願により教示される手段を例示的に列挙する。
（付記１）
プログラムコードを実行するための複数のスレッドのうちから第１スレッドを選択するためのスレッド選択部と、
前記スレッド選択部によって選択された前記第１スレッドを実行し、前記第１スレッドに対する実行を完了した後で、前記複数のスレッドのうちから前記スレッド選択部によって選択された第２スレッドを実行するためのスレッド実行部と、
を含む多重スレッド実行プロセッサ。
（付記２）
前記複数のスレッドを保存するためのスレッド保存部をさらに含む付記１に記載の多重スレッド実行プロセッサ。
（付記３）
前記スレッド保存部に保存された複数のスレッドそれぞれは、初期状態及び完了状態のうちの一方の状態にあり、
前記スレッド選択部は、前記複数のスレッドのうち前記初期状態にある１つのスレッドを選択する付記２に記載の多重スレッド実行プロセッサ。
（付記４）
前記スレッド保存部は、前記複数のスレッドのうちから前記初期状態のスレッドをラウンドロビン方式によって選択する付記３に記載の多重スレッド実行プロセッサ。
（付記５）
前記スレッド選択部は、前記スレッド保存部に保存された複数のスレッドのそれぞれの状態を示すスレッド状態情報を利用して、前記複数のスレッドのうちから初期状態のスレッドを選択する付記３に記載の多重スレッド実行プロセッサ。
（付記６）
前記複数のスレッドのそれぞれは、前記プログラムコードを実行するための複数の実行経路のうち、何れか１つの実行経路に従う、付記１〜５のうち何れか１項に記載の多重スレッド実行プロセッサ。
（付記７）
前記複数の実行経路は、前記複数の実行経路のそれぞれに対応するプログラムカウンターによって定められる付記６に記載の多重スレッド実行プロセッサ。
（付記８）
プログラムコードを実行するための複数のスレッドのうちから第１スレッドを選択するためのスレッド選択部と、
前記スレッド選択部によって選択された前記第１スレッドを実行するためのスレッド実行部と、
前記第１スレッドを実行するために、発行された命令語が通過命令語であるか否かを判断するためのスレッド交換判断部と、を含み、
前記スレッド実行部は、前記第１スレッドに対する実行中に発行された命令語が、前記スレッド交換判断部によって通過命令語であると判断された場合に、スレッド保存部に保存された前記複数のスレッドのうちから前記スレッド選択部によって選択された第２スレッドにスレッド交換を行って、前記第２スレッドを実行する多重スレッド実行プロセッサ。
（付記９）
前記複数のスレッドを保存するためのスレッド保存部をさらに含む付記８に記載の多重スレッド実行プロセッサ。
（付記１０）
前記スレッド交換判断部は、前記プログラムコードに明示的に表示されたスレッド交換情報に基づいて、前記発行された命令語が通過命令語であるか否かを判断する付記８又は９に記載の多重スレッド実行プロセッサ。
（付記１１）
前記スレッド交換情報は、前記プログラムコードのエンコーディング時に含まれる付記１０に記載の多重スレッド実行プロセッサ。
（付記１２）
前記スレッド交換情報は、前記プログラムコードをエンコーディングする間にプログラマーによって含まれるか、または所定のアルゴリズムによるエンコーディング時に自動的に含まれる付記１１に記載の多重スレッド実行プロセッサ。
（付記１３）
前記スレッド保存部に保存された複数のスレッドのそれぞれは、準備状態、通過状態、及び完了状態のうちの何れかの状態にあり、
前記スレッド選択部は、前記複数のスレッドのうちから前記準備状態にある１つのスレッドを選択する付記９に記載の多重スレッド実行プロセッサ。
（付記１４）
前記スレッド実行部が、前記第１スレッドから前記第２スレッドにスレッド交換を行う場合に、前記第１スレッドは、通過状態になり、
前記スレッド実行部が、前記スレッド交換以前に発行された通過命令語に対する処理が完了した場合に、前記第１スレッドは、準備状態に戻される付記１３に記載の多重スレッド実行プロセッサ。
（付記１５）
前記スレッド選択部は、前記複数のスレッドのうちから前記複数のスレッドのそれぞれの状態を示すスレッド状態情報を利用して、準備状態のスレッドを選択する付記１３に記載の多重スレッド実行プロセッサ。
（付記１６）
プログラムコードを実行するための複数のスレッドを実行するためのプロセッシングユニットを含み、
前記プロセッシングユニットは、前記複数のスレッドのうちの１つのスレッドに対する実行を完了し、そして、スレッド交換を行って、前記複数のスレッドのうちの他のスレッドをその次に実行する方式で前記複数のスレッドを順次に実行する多重スレッド実行プロセッサ。
（付記１７）
前記多重スレッド実行プロセッサは、複数のプロセッシングユニットを含み、
前記複数のプロセッシングユニットは、前記複数のスレッドを分けて実行する付記１６に記載の多重スレッド実行プロセッサ。
（付記１８）
前記複数のプロセッシングユニットは、それぞれ固有のプログラムカウンターを利用する、付記１７に記載の多重スレッド実行プロセッサ。
（付記１９）
プログラムコードを実行するための複数のスレッドを実行するためのプロセッシングユニットを含み、
前記プロセッシングユニットは、前記複数のスレッドのうちの第１スレッドに対する実行中に発行された命令語が通過命令語である場合に、スレッド交換を行って、第２スレッドを実行する方式で前記複数のスレッドを順次に実行する多重スレッド実行プロセッサ。
（付記２０）
前記プロセッシングユニットは、前記プログラムコードに明示的に表示されたスレッド交換情報に基づいて、前記発行された命令語が通過命令語であるか否かを判断する付記１９に記載の多重スレッド実行プロセッサ。
（付記２１）
前記スレッド交換情報は、前記プログラムコードのエンコーディング時にプログラマーによって含まれるか、または所定のアルゴリズムによるエンコーディング時に自動的に含まれる付記２０に記載の多重スレッド実行プロセッサ。
（付記２２）
前記複数のスレッドのそれぞれは、準備状態、通過状態、及び完了状態のうちの何れかの状態にあり、
前記プロセッシングユニットは、前記複数のスレッドのうちから前記準備状態にある１つのスレッドを選択して実行する付記１９〜２１のうち何れか１項に記載の多重スレッド実行プロセッサ。
（付記２３）
前記スレッド交換が生じた場合に、前記第１スレッドは、通過状態になり、
前記通過命令語に対する処理が完了した場合に、前記第１スレッドは、準備状態に戻される付記２２に記載の多重スレッド実行プロセッサ。
（付記２４）
前記多重スレッド実行プロセッサは、複数のプロセッシングユニットを含み、
前記複数のプロセッシングユニットのそれぞれは、前記プログラムコードを実行する複数の実行経路のうちの何れか１つの実行経路を特定するプログラムカウンターを使う付記１９〜２３のうち何れか１項に記載の多重スレッド実行プロセッサ。
（付記２５）
プログラムコードを実行するための複数のスレッドを実行するための多重スレッド実行プロセッサの動作方法であって、
前記複数のスレッドのうちの第１スレッドを実行する段階と、
スレッド交換を行い、前記複数のスレッドのうちの他のスレッドを実行する段階と、を含み、
前記複数のスレッドに対する実行が完了するまで前記複数のスレッドを順次に実行する、多重スレッド実行プロセッサの動作方法。
（付記２６）
プログラムコードを実行するための複数のスレッドを実行するための多重スレッド実行プロセッサの動作方法であって、
前記複数のスレッドのうちの第１スレッドを実行するが、実行のために発行された命令語が通過命令語であるか否かを判断する段階と、
前記発行された命令語が通過命令語ではないと判断された場合には、前記第１スレッドを実行し続け、前記発行された命令語が通過命令語であると判断された場合には、スレッド交換を行い、前記複数のスレッドのうちの第２スレッドを実行する段階と、
を含む多重スレッド実行プロセッサの動作方法。
（付記２７）
前記複数のスレッドに対する実行が完了するまで前記スレッド交換を通じて、前記複数のスレッドを順次に実行する付記２６に記載の多重スレッド実行プロセッサの動作方法。
（付記２８）
前記発行された命令語が通過命令語であるか否かを判断するためのスレッド交換情報は、前記プログラムコードに明示的に表示されている付記２６又は２７に記載の多重スレッド実行プロセッサの動作方法。
（付記２９）
スレッド実行部を利用して、準備状態にある第１スレッドの命令語を順次に実行する段階と、
スレッド選択部を利用して、前記第１スレッドが通過状態になると、前記第１スレッドの実行を中断し、前記第１スレッドの状態が準備状態に戻るまで実行の再開を待機する段階と、
前記スレッド実行部を利用して、前記準備状態に戻った前記第１スレッドの全ての命令語を実行し、前記第１スレッドの実行を完了し、前記スレッド選択部を利用して、前記実行が完了した第１スレッドを完了状態にする段階と、
を含む多重スレッド実行プロセッサの動作方法。
（付記３０）
第２スレッドが準備状態にあり、前記第１スレッドが前記通過状態にあり、実行が中断されていた場合には、前記スレッド実行部を利用して、前記第２スレッドの命令語を順次に実行する段階をさらに含む付記２９に記載の多重スレッド実行プロセッサの動作方法。
（付記３１）
実行される現在の命令語が、処理時間臨界値を超過すると、前記第１スレッドの実行が中断され、前記通過状態になる付記２９又は３０に記載の多重スレッド実行プロセッサの動作方法。
（付記３２）
準備状態にある第１スレッドの命令語を順次に実行するスレッド実行部と、
前記第１スレッドが通過状態になると、前記第１スレッドの実行を中断し、前記第１スレッドの状態が準備状態に戻るまで実行の再開を待機するスレッド選択部と、を含み、
前記スレッド実行部を利用して、前記準備状態に戻った前記第１スレッドの全ての命令語を実行し、前記第１スレッドの実行を完了し、前記スレッド選択部を利用して、前記実行が完了した第１スレッドを完了状態にする多重スレッド実行プロセッサ。
（付記３３）
前記スレッド実行部は、第２スレッドが準備状態にあり、前記第１スレッドが前記通過状態にあり、実行が中断されていた場合、前記第２スレッドの命令語を順次に実行する付記３２に記載の多重スレッド実行プロセッサ。
（付記３４）
実行される現在の命令語が、処理時間臨界値を超過すると、前記第１スレッドの実行が中断され、前記通過状態になる付記３２又は３３に記載の多重スレッド実行プロセッサ。
【符号の説明】
【０１２０】
１０、２０  多重スレッド実行プロセッサ
１２、２２  スレッド保存部
１４、２４  スレッド選択部
１６、２６  スレッド実行部
２８  スレッド交換判断部
【先行技術文献】
【特許文献】
【０１２１】
【特許文献１】特開２０１２−１２８７９１公報
【特許文献２】特開平８−１７１４９４号公報
【特許文献３】特開２００９−７５９４８号公報
【図１】
2019160352.tif 000003
【図２】
2019160352.tif 000004
【図３】
2019160352.tif 000005
【図４】
2019160352.tif 000006
【図５】
2019160352.tif 000007
【図６】
2019160352.tif 000008
【図７】
2019160352.tif 000009
【図８Ａ】
2019160352.tif 000010
【図８Ｂ】
2019160352.tif 000011
【図８Ｃ】
2019160352.tif 000012
【図９Ａ】
2019160352.tif 000013
【図９Ｂ】
2019160352.tif 000014
【図９Ｃ】
2019160352.tif 000015
【図９Ｄ】
2019160352.tif 000016
【図９Ｅ】
2019160352.tif 000017
【図１０Ａ】
2019160352.tif 000018
【図１０Ｂ】
2019160352.tif 000019
【図１０Ｃ】
2019160352.tif 000020
【図１０Ｄ】
2019160352.tif 000021
【図１０Ｅ】
2019160352.tif 000022
【図１１Ａ】
2019160352.tif 000023
【図１１Ｂ】
2019160352.tif 000024