(57)【特許請求の範囲】
【請求項１】
ミニコア基盤の再構成可能プロセッサであって、
メッシュ構造で連結された多数のミニコアを含み、
前記ミニコアのそれぞれは、ループ繰り返しを独立して実行するファンクションユニットの集合を含み、
前記多数のミニコアは、第１ループ繰り返しを実行する第１ミニコア及び第２ループ繰り返しを実行する第２ミニコアを含み、前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、前記第１ループ繰り返しと前記第２ループ繰り返しとの間にループスキューが発生するように、且つ前記第１ミニコアと前記第２ミニコアとの間の直接連結を通じて前記依存性に対するデータが伝達されるように、前記多数のミニコアへのループ繰り返しのマッピング状態が調節される、ミニコア基盤の再構成可能プロセッサ。
【請求項２】
前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、
前記第２ミニコアは、前記第１ループ繰り返しの実行が開始された以後に、前記第２ループ繰り返しの実行を開始する、請求項１に記載のミニコア基盤の再構成可能プロセッサ。
【請求項３】
前記ミニコアを連結するための外部リンクをさらに含み、
前記ミニコアのそれぞれは、内部のファンクションユニットを連結するための内部リンクをさらに含む請求項１又は２に記載のミニコア基盤の再構成可能プロセッサ。
【請求項４】
ミニコア基盤の再構成可能プロセッサのためのスケジュール装置であって、
第１ループ繰り返しをメッシュ構造で連結された多数のミニコアのうちの第１ミニコアにマッピングし、
第２ループ繰り返しを前記多数のミニコアのうちの第２ミニコアにマッピングし、
ミニコアのそれぞれは、ループ繰り返しを独立して実行するファンクションユニットの集合を含み、
前記スケジュール装置は、前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、前記第１ループ繰り返しと前記第２ループ繰り返しとの間にループスキューが発生するように且つ前記第１ミニコアと前記第２ミニコアとの間の直接連結を通じて前記依存性に対するデータが伝達されるように、マッピング状態を調節するグローバルスケジューラをさらに含む、
ミニコア基盤の再構成可能プロセッサのためのスケジュール装置。
【請求項５】
前記グローバルスケジューラは、
前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させ、前記第２ループ繰り返しを前記第２ミニコアにマッピングする請求項４に記載のミニコア基盤の再構成可能プロセッサのためのスケジュール装置。
【請求項６】
前記第２ミニコアは、前記第１ミニコアと物理的に連結され、
前記グローバルスケジューラは、
前記第１ループ繰り返しを前記第１ミニコアにマッピングし、
前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させ、
該遅延された第２ループ繰り返しを前記第２ミニコアにマッピングする請求項４又は５に記載のミニコア基盤の再構成可能プロセッサのためのスケジュール装置。
【請求項７】
前記再構成可能プロセッサに含まれた多数のファンクションユニットを前記ミニコアのそれぞれに含まれた前記ファンクションユニットの集合に区分するミニコア構成部をさらに含む請求項４乃至６のいずれか一項に記載のミニコア基盤の再構成可能プロセッサのためのスケジュール装置。
【請求項８】
多数のファンクションユニットを含むミニコア基盤の再構成可能プロセッサのためのスケジューリング方法であって、
前記再構成可能プロセッサに含まれた前記ファンクションユニットをメッシュ構造で連結された多数のミニコアに区分する段階と、
第１ループ繰り返しを第１ミニコアにマッピングする段階と、
第２ループ繰り返しを第２ミニコアにマッピングする段階と、
前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、前記第１ループ繰り返しと前記第２ループ繰り返しとの間にループスキューが発生するように且つ前記第１ミニコアと前記第２ミニコアとの間の直接連結を通じて前記依存性に対するデータが伝達されるように、マッピング状態を調節する段階と、
を含み、
前記多数のミニコアの各ミニコアは、ループ繰り返しを独立して実行するファンクションユニットの集合を含む、ミニコア基盤の再構成可能プロセッサのためのスケジューリング方法。
【請求項９】
前記マッピング状態を調節する段階は、
前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させる段階と、
前記第２ループ繰り返しを前記第２ミニコアにマッピングする段階と、
をさらに含む請求項８に記載のミニコア基盤の再構成可能プロセッサのためのスケジューリング方法。
【請求項１０】
前記第２ミニコアは、物理的に前記第１ミニコアと連結され、
前記マッピング状態を調節する段階は、
前記第１ループ繰り返しを前記第１ミニコアにマッピングする段階と、
前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させる段階と、
遅延された第２ループ繰り返しを前記第２ミニコアにマッピングする段階と、
をさらに含む請求項８又は９に記載のミニコア基盤の再構成可能プロセッサのためのスケジューリング方法。
【請求項１１】
多数のファンクションユニットの集合で再構成されて、メッシュ構造で連結された多数のミニコアを形成する多数のファンクションユニットを含み、
前記ファンクションユニットの集合のうち、それぞれの集合は、ループ繰り返しを独立して実行し、
前記ミニコアのうち、それぞれのミニコアは、前記ファンクションユニットの前記それぞれの集合を含み、前記ファンクションユニットの集合のそれぞれの集合により実行されるループ繰り返しの間に依存性が存在する場合、前記ループ繰り返しの間にループスキューが発生するように、且つ前記ミニコア間の直接連結を通じて前記依存性に対するデータが伝達されるように、前記ファンクションユニットの集合のそれぞれの集合にマッピングされるループ繰り返しのマッピング状態が調節される、
再構成可能プロセッサ。
【請求項１２】
連続する前記ループ繰り返し間に依存性がない場合、
前記ミニコアは、前記ループ繰り返しのうち、１つずつのループ繰り返しの実行を同時に開始する請求項１１に記載の再構成可能プロセッサ。
【請求項１３】
連続する前記ループ繰り返し間に依存性がない場合、
前記ループ繰り返しのうち、直前ループ繰り返しを実行するミニコアが、前記直前ループ繰り返しの実行を開始してから予定された時間ほど経過した後、前記ミニコアのうち、前記ループ繰り返しのうち、第１ループ繰り返しを実行するミニコアを除いたそれぞれのミニコアは、前記ループ繰り返しのうち、１つずつの実行をそれぞれ開始する請求項１１に記載の再構成可能プロセッサ。
【請求項１４】
それぞれの前記ファンクションユニットの集合内の前記ファンクションユニットは、同種のファンクションユニットである請求項１、２、１１乃至１３のいずれか一項に記載の再構成可能プロセッサ。
【請求項１５】
それぞれの前記ファンクションユニットの集合内の前記ファンクションユニットは、異種のファンクションユニットである請求項１、２、１１乃至１３のいずれか一項に記載の再構成可能プロセッサ。
【請求項１６】
外部リンク及び多数の内部リンクで再構成される多数の再構成可能リンクをさらに含み、
前記外部リンクは、前記ミニコアを互いに連結し、
前記内部リンクのうち、それぞれの内部リンクは、前記ミニコアのうち、それぞれのミニコアのファンクションユニットを互いに連結する請求項１１乃至１５のいずれか一項に記載の再構成可能プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、再構成可能アーキテクチャー及びループスケジューリング技法に関する。
【背景技術】
【０００２】
通常、再構成可能アーキテクチャーとは、所定の作業を行うためのコンピューティング装置のハードウェア的構成をそれぞれの作業に最適化されるように変更するアーキテクチャーを意味する。
【０００３】
所定の作業をハードウェア的にのみ処理すれば、固定されたハードウェアの機能によって、作業内容に若干の変更が加えられれば、これを効率よく処理しにくい。また、所定の作業をソフトウェア的にのみ処理すれば、その作業内容に合わせてソフトウェアを変更して処理することが可能であるが、ハードウェアによる処理に比べて速度が遅い。
【０００４】
再構成可能アーキテクチャーは、このようなハードウェア／ソフトウェアの長所をいずれも満足させる。特に、同じ作業が反復的に行われるデジタル信号処理分野では、このような再構成可能アーキテクチャーが多くの注目を浴びている。再構成可能アーキテクチャーの種類は、さまざまであるが、そのうち、粗粒度アレイ（Ｃｏａｒｓｅ−Ｇｒａｉｎｅｄ  Ａｒｒａｙ；以下、ＣＧＡと称する）が代表的である。ＣＧＡは、複数個のプロセッシングユニットからなる。そして、プロセッシングユニット間の連結状態が調節されることによって、所定の作業に最適化されうる。
【０００５】
通常のＣＧＡでのループスケジューリングは、適切な答を求めにくいという問題点を解決するために、多くのヒューリスティックアルゴリズムが開発された。これは、既存のアルゴリズムが普通ＣＧＡのファンクションユニット（Ｆｕｎｃｔｉｏｎａｌ  Ｕｎｉｔ、ＦＵ）の活用度を高めるために、モジュロスケジューリングに基盤を置いているためである。このような場合、ファンクションユニットの数が少ない場合には、高い活用度が得られるが、ファンクションユニットの数が多い場合には、高い活用度が得られにくい。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、ミニコア基盤の再構成可能プロセッサ、そのためのスケジュール装置及び方法を提供することである。
【課題を解決するための手段】
【０００７】
本発明の一態様によるミニコア基盤の再構成可能プロセッサは、多数のミニコアを含み、前記ミニコアのそれぞれは、ループ繰り返しを独立して実行するファンクションユニット（ＦＵ）の集合を含み、前記多数のミニコアは、第１ループ繰り返しを実行する第１ミニコア及び第２ループ繰り返しを実行する第２ミニコアを含む。
【０００８】
この際、前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、前記第２ミニコアは、前記第１ループ繰り返しの実行が開始された以後に、前記第２ループ繰り返しの実行を開始する。
【０００９】
また、前記ミニコアのそれぞれは、同種のファンクションユニットを含みうる。また、前記ミニコアのそれぞれは、異種のファンクションユニットを含みうる。また、前記ミニコアを連結するための外部リンクをさらに含み、前記ミニコアのそれぞれは、内部のファンクションユニットを連結するための内部リンクをさらに含みうる。
【００１０】
本発明の他の態様によるミニコア基盤の再構成可能プロセッサのためのスケジュール装置は、第１ループ繰り返しを多数のミニコアのうちの第１ミニコアにマッピングし、第２ループ繰り返しを多数のミニコアのうちの第２ミニコアにマッピングし、ミニコアのそれぞれは、ループ繰り返しを独立して実行するファンクションユニットの集合を含む。
【００１１】
この際、前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、前記第１ループ繰り返しと前記第２ループ繰り返しとの間にループスキュー（ｌｏｏｐ  ｓｋｅｗ）が発生するようにマッピング状態を調節するグローバルスケジューラをさらに含みうる。
【００１２】
また、前記グローバルスケジューラは、前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させ、前記第２ループ繰り返しを前記第２ミニコアにマッピングすることができる。また、前記第２ミニコアは、前記第１ミニコアと物理的に連結され、前記グローバルスケジューラは、前記第１ループ繰り返しを前記第１ミニコアにマッピングし、前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させ、該遅延された第２ループ繰り返しを前記第２ミニコアにマッピングすることができる。
【００１３】
また、前記再構成可能プロセッサに含まれた多数のファンクションユニットを前記ミニコアのそれぞれに含まれた前記ファンクションユニットの集合に区分するミニコア構成部をさらに含みうる。
【００１４】
本発明のさらに他の態様による多数のファンクションユニットを含むミニコア基盤の再構成可能プロセッサのためのスケジューリング方法は、前記再構成可能プロセッサに含まれた前記ファンクションユニットを多数のミニコアに区分する段階と、第１ループ繰り返しを第１ミニコアにマッピングする段階と、第２ループ繰り返しを第２ミニコアにマッピングする段階と、を含み、前記多数のミニコアの各ミニコアは、ループ繰り返しを独立して実行するファンクションユニットの集合を含む。
【００１５】
この際、前記第１ループ繰り返しと前記第２ループ繰り返しとの間に依存性が存在する場合、前記第１ループ繰り返しと前記第２ループ繰り返しとの間にループスキューが発生するようにマッピング状態を調節する段階をさらに含みうる。
【００１６】
また、前記マッピング状態を調節する段階は、前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させる段階と、前記第２ループ繰り返しを前記第２ミニコアにマッピングする段階と、をさらに含みうる。
【００１７】
また、前記第２ミニコアは、物理的に前記第１ミニコアと連結され、前記マッピング状態を調節する段階は、前記第１ループ繰り返しを前記第１ミニコアにマッピングする段階と、前記第２ループ繰り返しを前記第１ループ繰り返しよりも遅延させる段階と、遅延された第２ループ繰り返しを前記第２ミニコアにマッピングする段階と、をさらに含みうる。
【００１８】
本発明のさらに他の態様による再構成可能プロセッサは、多数のファンクションユニットの集合で再構成されて、多数のミニコアを形成する多数のファンクションユニットを含み、前記ファンクションユニットの集合のうち、それぞれの集合は、ループ繰り返しを独立して実行し、前記ミニコアのうち、それぞれのミニコアは、前記ファンクションユニットの前記それぞれの集合を含み、前記ミニコアのうち、それぞれのミニコアは、多数のループ繰り返しのうち、互いに異なるループ繰り返しを実行する。
【００１９】
この際、連続する前記ループ繰り返し間に依存性がない場合、前記ミニコアは、前記ループ繰り返しのうち、１つずつのループ繰り返しの実行を同時に開始することができる。
【００２０】
また、連続する前記ループ繰り返し間に依存性がない場合、前記ループ繰り返しのうち、直前ループ繰り返しを実行するミニコアが、前記直前ループ繰り返しの実行を開始してから予定された時間が経過した後、前記ミニコアのうち、前記ループ繰り返しのうち、第１ループ繰り返しを実行するミニコアを除いたそれぞれのミニコアは、前記ループ繰り返しのうち、１つずつの実行をそれぞれ開始することができる。
【００２１】
また、それぞれの前記ファンクションユニットの集合内の前記ファンクションユニットは、同種のファンクションユニットであり得る。また、それぞれの前記ファンクションユニットの集合内の前記ファンクションユニットは、異種のファンクションユニットであり得る。
【００２２】
また、外部リンク及び多数の内部リンクで再構成される多数の再構成可能リンクをさらに含み、前記外部リンクは、前記ミニコアを互いに連結し、前記内部リンクのうち、それぞれの内部リンクは、前記ミニコアのうち、それぞれのミニコアのファンクションユニットを互いに連結することができる。
【図面の簡単な説明】
【００２３】
【図１】再構成可能プロセッサの構成の一例を示す図である。
【図２】再構成可能プロセッサの構成の他の例を示す図である。
【図３】再構成可能プロセッサのためのスケジュール装置の一例を示す図である。
【図４】ミニコア基盤のループマッピング方法の一例を示す図である。
【図５】ミニコア基盤のループマッピング方法の他の例を示す図である。
【図６Ａ】ミニコア間の通信構造の実施形態を示す図である。
【図６Ｂ】ミニコア間の通信構造の実施形態を示す図である。
【図７】制御メモリとミニコアとの連結構造の一例を示す図である。
【図８】再構成可能プロセッサの構成のさらに他の例を示す図である。
【図９】再構成可能プロセッサのためのスケジューリング方法のさらに他の例を示す図である。
【発明を実施するための形態】
【００２４】
以下、添付図面を参照して、本発明の実施のための具体例を詳しく説明する。
【００２５】
図１は、再構成可能プロセッサの構成の一例を示す図である。図１を参照すると、本実施形態による再構成可能プロセッサ１００は、多数のミニコア（ｍｉｎｉ−ｃｏｒｅ、ＭＣ）を含みうる。
【００２６】
多数のミニコアのうちのそれぞれのミニコア（ＭＣ）は、多数のファンクションユニット（ＦＵ）を含みうる。それぞれのファンクションユニット（ＦＵ）は、各種の算術演算及び／または論理演算を行うことができる。
【００２７】
それぞれのミニコア（ＭＣ）は、少なくとも１つのループ繰り返しを独立して実行することができる。“独立的”実行とは、他のミニコアの助けなしに、１つのミニコア内で１つのループ繰り返しの実行が完了するということを意味する。例えば、ＭＣ  ＃０は、ＦＵ  ＃０、ＦＵ  ＃１、ＦＵ  ＃４、及びＦＵ  ＃５を用いて、特定のループ繰り返しの実行を完了することが可能である。すなわち、何れか１つのミニコア（ＭＣ）は、何れか１つのループ繰り返しを実行することができるファンクションユニット（ＦＵ）の集合と定義されうる。
【００２８】
それぞれのミニコア（ＭＣ）は、ソフトウェアパイプラインによって、互いに異なるループ繰り返しを実行することができる。例えば、ＭＣ  ＃０は、最初のループ繰り返しを実行し、ＭＣ  ＃１は、二番目のループ繰り返しを実行することができる。言い換えれば、ソフトウェアパイプラインに基づいたループスケジューリングでそれぞれのミニコア（ＭＣ）、すなわち、独立してループ繰り返しを実行することができる１つのＦＵの集合がスケジュール単位になりうる。
【００２９】
一態様によって、最初のループ繰り返しと二番目のループ繰り返しとの間に依存性が存在する場合、二番目のループ繰り返しがマッピングされたミニコア（ＭＣ）は、最初のループ繰り返しの実行が開始された以後に、二番目のループ繰り返しの実行を開始する。
【００３０】
例えば、最初のループ繰り返しがＭＣ  ＃０にマッピングされ、二番目のループ繰り返しがＭＣ  ＃１にマッピングされ、最初のループ繰り返しと二番目のループ繰り返しとの間に依存性が存在する場合、ＭＣ  ＃１は、ＭＣ  ＃０が最初のループ繰り返しの実行を開始した以後に、二番目のループ繰り返しの実行を開始することが可能である。言い換えれば、最初のループ繰り返しと二番目のループ繰り返しとの間にリカレンス（ｒｅｃｕｒｒｅｎｃｅ）が存在する場合、そのリカレンスを考慮して、各ループ繰り返しの実行開始時点が調節される。
【００３１】
各ミニコア（ＭＣ）を構成するファンクションユニット（ＦＵ）は、同種のファンクションユニット（ＦＵ）になりうる。例えば、ＭＣ  ＃０内部のＦＵ  ＃０、ＦＵ  ＃１、ＦＵ  ＃４、及びＦＵ  ＃５は、いずれも同じ構成を有しうる。各ミニコア（ＭＣ）を構成するファンクションユニット（ＦＵ）は、異種のファンクションユニット（ＦＵ）になりうる。例えば、ＭＣ  ＃０内部のＦＵ  ＃０、ＦＵ  ＃１、ＦＵ  ＃４、及びＦＵ  ＃５のうち少なくとも２つのＦＵは、互いに異なる構成を有しうる。ミニコア（ＭＣ）内のファンクションユニット（ＦＵ）のうち少なくとも２つのファンクションユニット（ＦＵ）は、互いに異なるコンピューティングパワーを有しうる。コンピューティングパワーは、ファンクションユニット（ＦＵ）が提供（支援）する演算の種類と定義されうる。例えば、部分コンピューティングパワーを有するファンクションユニット（ＦＵ）で全体コンピューティングパワーを有するミニコア（ＭＣ）を定義することができる。全体コンピューティングパワーは、少なくとも１つのループ繰り返しの実行に必要な演算の種類と定義されうる。
【００３２】
再構成可能プロセッサ１００は、外部リンク１１０をさらに含んでもよく、それぞれのミニコア内に内部リンクをさらに含んでも良い（図１のＭＣ  ＃０内の内部リンクの場合、図面符号が１２０ａである）。外部リンク１１０は、ミニコア（ＭＣ）間の通信経路を提供し、各ミニコア内の内部リンク１２０ａは、ミニコアのファンクションユニット（ＦＵ）間の通信経路を提供することができる。再構成可能プロセッサ１００は、外部リンク１１０及び内部リンク１２０ａの機能を果たす多数の再構成可能リンクを含みうる。
【００３３】
再構成可能プロセッサ１００は、ローカルレジスタファイル（ＲＦ）１３０ａ及びグローバルレジスタファイル１５０をさらに含みうる。ローカルレジスタファイル１３０ａは、ファンクションユニット（ＦＵ）の演算結果またはコンテキスト情報を保存し、グローバルレジスタファイル１５０は、ミニコア（ＭＣ）の演算結果またはコンテキスト情報を保存することができる。
【００３４】
再構成可能プロセッサ１００は、制御メモリ１４０をさらに含みうる。制御メモリ１４０は、ファンクションユニット（ＦＵ）及び／またはミニコア（ＭＣ）の連結状態を定義する。言い換えれば、再構成可能プロセッサ１００の構成は、制御メモリ１４０に保存された構成情報に基づいて実行されるプログラムに最適化されうる。
【００３５】
図２は、再構成可能プロセッサの構成の他の例を示す図である。図２を参照すると、再構成可能プロセッサ２００は、多数のファンクションユニット（ＦＵ）を含む多数のミニコア（ＭＣ）、ローカルレジスタファイル１３０ａ、グローバルレジスタファイル１５０、制御メモリ１４０、及びリンク２１０、２２０を含みうる。ここで、各ファンクションユニット（ＦＵ）、ミニコア（ＭＣ）、ローカルレジスタファイル１３０ａ、グローバルレジスタファイル１５０、及び制御メモリ１４０は、図１で説明したものと同一なので、詳しい説明は省略する。
【００３６】
図２で、再構成可能プロセッサ２００は、４×４メッシュ構造で連結された１６個のファンクションユニット（ＦＵ）が論理的に４個のミニコア（ＭＣ）を形成した形状を例示する。例えば、ミニコア（ＭＣ）間のリンク（例えば、２１０）は、図１の外部リンク１１０の役割を行い、ミニコア（ＭＣ）内部のリンク（例えば、２２０）は、図１の内部リンク１２０ａの役割を行うことができる。
【００３７】
図３は、再構成可能プロセッサのためのスケジュール装置の一例を示す図である。これは、図１及び図２のように、ミニコア基盤の再構成可能プロセッサに適用可能である。
【００３８】
図１ないし図３を参照すると、本実施形態によるスケジュール装置３００は、ミニコア構成部３１０、ローカルスケジューラ３２０、及びグローバルスケジューラ３３０を含みうる。
【００３９】
ミニコア構成部３１０は、再構成可能プロセッサ１００、２００に含まれた多数のファンクションユニット（ＦＵ）を多数のミニコア（ＭＣ）に区分する。ミニコア構成部３１０は、独立してループ繰り返しを実行することができるファンクションユニット（ＦＵ）を集めて、１つのミニコア（ＭＣ）を形成することが可能である。例えば、ミニコア構成部３１０は、再構成可能プロセッサ１００、２００のハードウェア情報を用いて、ミニコア（ＭＣ）を定義することができる。再構成可能プロセッサ１００、２００のハードウェア情報は、各ファンクションユニット（ＦＵ）のコンピューティングパワー及び連結状態に関する情報を含みうる。
【００４０】
ローカルスケジューラ３２０は、ミニコア（ＭＣ）に基づき、第１ループ繰り返しを第１ミニコアにマッピングし、第２ループ繰り返しを第２ミニコアにマッピングする。言い換えれば、ローカルスケジューラ３２０は、ソフトウェアパイプラインによってループをスケジュールする時、ミニコア（ＭＣ）をスケジュール単位で利用することが可能である。
【００４１】
グローバルスケジューラ３３０は、第１ループ繰り返しと第２ループ繰り返しとの間に依存性またはリカレンスが存在する場合、所定のループスキューが生じるようにマッピング状態を調節する。例えば、グローバルスケジューラ３３０は、第２ループ繰り返しを第１ループ繰り返しよりも遅延させて、第２ミニコアにマッピングすることが可能である。この際、第２ミニコアは、第１ループ繰り返しがマッピングされた第１ミニコアと物理的に連結されたミニコアになりうる。
【００４２】
図３で示した各構成の区分は、単にその機能による論理的な区分の一例である。したがって、図３で示したものと異なる基準によって、その機能が区分されることもある。言い換えれば、２つ以上の機能ブロックが、１つの機能ブロックに統合されるか、何れか１つの機能ブロックで行われる機能の一部が、１つまたはそれ以上の他の機能ブロックで行われるということはいうまでもない。
【００４３】
図４は、ミニコア基盤のループマッピング方法の一例を示す図である。
【００４４】
図３及び図４を参照すると、これは、各ループ繰り返し間に依存性がなくて、ローカルスケジューラ３２０のレベルでマッピングがなされたことを表すことができる。
【００４５】
図４で、実行されるループは、Ａ、Ｂ、Ｃ、Ｄのように、４個の実行単位で区分されうる。各実行単位は、例えば、インストラクションになりうる。説明の便宜上、Ａ、Ｂ、Ｃ、Ｄをインストラクションであると仮定する。すなわち、例示されたループは、インストラクションＡ、Ｂ、Ｃ、Ｄが順次に繰り返して実行されるアプリケーションプログラムになりうる。
【００４６】
本実施形態で、各ループ繰り返しには依存性がない。例えば、最初のループ繰り返し（ｉ＝０）のインストラクションＢと二番目のループ繰り返し（ｉ＝１）のインストラクションＢは、並列的に同時に実行可能である。
【００４７】
図３及び図４で、ローカルスケジューラ３２０は、最初のループ繰り返し（ｉ＝０）をＭＣ  ＃０にマッピングし、二番目のループ繰り返し（ｉ＝１）をＭＣ  ＃１にマッピングすることができる。示したように、ミニコア（ＭＣ）が４個であれば、ローカルスケジューラ３２０は、五番目のループ繰り返し（ｉ＝４）を再びＭＣ  ＃０にマッピングし、六番目のループ繰り返し（ｉ＝５）をＭＣ  ＃１にマッピングすることが可能である。
【００４８】
このように、本実施形態によれば、独立してループ繰り返しを実行することができるミニコア（ＭＣ）に基づいてループスケジューリングがなされるために、ファンクションユニットの個数が増加しても、ループスケジューリングの効率性及び拡張性を保証することができる。
【００４９】
図５は、ミニコア基盤のループマッピング方法の他の例を示す図である。
【００５０】
図３及び図５を参照すると、これは、各ループ繰り返し間に依存性があって、ローカルスケジューラ３２０及びグローバルスケジューラ３３０のレベルでマッピングがなされたことを表すことができる。
【００５１】
図５で、実行されるループは、Ａ、Ｂ、Ｃ、Ｄのように、４個の実行単位で区分されうる。各実行単位は、例えば、インストラクションになりうる。説明の便宜上、Ａ、Ｂ、Ｃ、Ｄをインストラクションであると仮定する。すなわち、例示されたループは、インストラクションＡ、Ｂ、Ｃ、Ｄが順次に繰り返して実行されるアプリケーションプログラムになりうる。
【００５２】
この際、各ループ繰り返しには依存性がある。例えば、インストラクションＢのように、最初のループ繰り返し（ｉ＝０）の実行結果が、二番目のループ繰り返し（ｉ＝１）の入力として使われる場合、各ループ繰り返し間に依存性またはリカレンスがあると言える。図５のインストラクション間の点線矢印は、ループとループとのデータ伝送、すなわち、依存性またはリカレンスを表わす。
【００５３】
図３及び図５で、ローカルスケジューラ３２０は、最初のループ繰り返し（ｉ＝０）をＭＣ  ＃０にマッピングし、二番目のループ繰り返し（ｉ＝１）をＭＣ  ＃１にマッピングすることができる。示したように、ミニコア（ＭＣ）が４個であれば、ローカルスケジューラ３２０は、五番目のループ繰り返し（ｉ＝４）を再びＭＣ  ＃０にマッピングし、六番目のループ繰り返し（ｉ＝５）をＭＣ  ＃１にマッピングすることが可能である。
【００５４】
また、ループ繰り返し間の依存性またはリカレンスが存在するので、グローバルスケジューラ３３０は、二番目のループ繰り返し（ｉ＝１）を所定時間（例えば、ｄ）遅延させて、該遅延された二番目のループ繰り返しをＭＣ  ＃１にマッピングすることができる。同様に、三番目のループ繰り返し（ｉ＝２）を所定時間（例えば、２ｄ）遅延させて、該遅延された三番目のループ繰り返しをＭＣ  ＃２にマッピングすることができる。また、グローバルスケジューラ３３０は、四番目のループ繰り返し（ｉ＝３）を所定時間（例えば、３ｄ）遅延させて、該遅延された四番目のループ繰り返しをＭＣ  ＃３にマッピングすることができる。ここで、所定の遅延時間は、依存性またはリカレンスを考慮して、当該リカレンスに対する書き込みは、可能であれば早くなされるようにし、その読み取りは、可能であれば遅くなされるように定義されうる。これは、あるループ繰り返しと次のループ繰り返しとの間の依存性によって生じる二番目のループ繰り返しの遅延時間を最小化するためである。
【００５５】
グローバルスケジューラ３３０は、ミニコア（ＭＣ）間の直接連結を通じてリカレンスに対するデータが伝達されるようにマッピング状態を調節することが可能である。また、選択的に、ローカルレジスタファイル（例えば、１３０ａ）、グローバルレジスタファイル１５０、または外部メモリ（図示せず）を通じてリカレンスに対するデータを伝達させることも可能である。
【００５６】
図５で、依存性またはリカレンスが存在する場合にも、初期段階を経て安定状態になれば、あらゆるミニコア（ＭＣ）が動作することを確認することができる。もし、１つのミニコアの平均ＩＰＣ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｐｅｒ  Ｃｙｃｌｅ）が‘ｋ’である場合、安定状態では、平均的に‘ｋ＊（ミニコアの数）’のＩＰＣを果たすことができることが分かる。
【００５７】
図６Ａ及び図６Ｂは、ミニコア間の通信構造の実施形態を示す図である。
【００５８】
本実施形態によるミニコア（ＭＣ）は、隣接したミニコア（ＭＣ）にデータのみを伝送する場合がほとんどであるために、図６Ａのようなリングバスまたは図６Ｂのようなデータキューを使って、高い拡張性が得られる。また、例えば、遠いループ繰り返し間のデータ伝送のような場合、必要であれば、グローバルレジスタファイルや外部メモリを活用して、データを伝達することも可能である。
【００５９】
図７は、制御メモリとミニコアとの連結構造の一例を示す図である。
【００６０】
本実施形態で、各ミニコア（ＭＣ）は、同じ制御情報を共有することができる。但し、ループ繰り返し間に依存性が存在する場合、各ミニコア（ＭＣ）は、所定の時間差を置いて動作する点のみ異なる。したがって、制御メモリ７０１と連結され、階層構造を有するサブメモリ７２０を通じて制御情報を共有することが可能である。サブメモリ７２０の構成は、特に限定されず、キャッシュあるいはフリップフロップの形態で作られることができる。
【００６１】
図８は、再構成可能プロセッサの構成のさらに他の例を示す図である。図８の実施形態による再構成可能プロセッサ８００は、ループ制御部８１０、電源制御部８２０、及び多数のミニコア（ＭＣｓ）を含みうる。
【００６２】
図８に示すループ制御部８１０とミニコアとが直接連結されることによって、ループ制御部８１０は、各ミニコア（ＭＣ）が所定時間に動作できるように信号を伝達し、最後のループ繰り返しを完了したミニコア（ＭＣ）は、全体ループの反復を終了できるようにループ制御部８１０に信号を伝送する。
【００６３】
電源制御部８２０は、一部のミニコア（ＭＣ）に供給される電源を遮断して、一部のミニコア（ＭＣ）が動作しないようにすることが可能である。如何なるミニコア（ＭＣ）の動作を制限させるかは、スケジュール結果及び応用目的によって多様に可変されうる。
【００６４】
図９は、再構成可能プロセッサのためのスケジューリング方法のさらに他の例を示す図である。
【００６５】
図３及び図９を参照すると、本実施形態によるスケジューリング方法によって、まず、ファンクションユニットがミニコアに区分される（９０１）。例えば、ミニコア構成部３１０が、再構成可能プロセッサに含まれた多数のファンクションユニットを、ループ繰り返しを独立して実行するファンクションユニットの集合と定義されるミニコアに区分することが可能である。
【００６６】
そして、各ループ繰り返しがミニコアにマッピングされる（９０２）。例えば、ローカルスケジューラ３２０が、第１ループ繰り返しを第１ミニコアにマッピングし、第２ループ繰り返しを第２ミニコアにマッピングすることが可能である。
【００６７】
そして、ループ繰り返し間の依存性に基づいてマッピング状態が調節される（９０３）。グローバルスケジューラ３３０が、第１ループ繰り返しと第２ループ繰り返しとの間に依存性が存在する場合、例えば、図５で示すように、その依存性またはリカレンスを考慮したループスキューが生じるようにマッピング状態を調節することが可能である。
【００６８】
前述したように、開示された実施形態によれば、ミニコアを利用し、リカレンスを考慮して、ループをスケジューリングするために、高いＩＰＣが得られ、システムのサイズが大きくなっても、優れた拡張性が得られる。ミニコアを利用し、リカレンスを考慮して、ループをスケジューリングするために、高いサイクル当たりインストラクション処理率（ＩＰＣ：Ｉｎｓｔｒｕｃｔｉｏｎｓ  Ｐｅｒ  Ｃｙｃｌｅ）が得られ、システムのサイズが大きくなっても、優れた拡張性が得られる。
【００６９】
スケジュール装置３００、ＭＣ構成部３１０、ローカルスケジューラ３２０、グローバルスケジューラ３３０、ループ制御部８１０、及び電源制御部８２０は、１つまたはそれ以上のハードウェア構成要素や１つまたはそれ以上のソフトウェア構成要素、またはこれらの組合わせを用いて具現可能である。
【００７０】
一方、本発明の実施形態は、コンピュータで読み取り可能な記録媒体にコンピュータで読み取り可能なコードとして具現しうる。コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み取れるデータが保存されるあらゆる種類の記録装置を含む。
【００７１】
コンピュータで読み取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置などがあり、またキャリアウェーブ（例えば、インターネットを介した伝送）の形態で具現するものを含む。また、コンピュータで読み取り可能な記録媒体は、ネットワークで連結されたコンピュータシステムに分散されて、分散方式でコンピュータで読み取り可能なコードとして保存されて実行可能である。そして、本発明を具現するための関数プログラム、コード及びコードセグメントは、本発明が属する技術分野のプログラマーによって容易に推論されうる。
【００７２】
さらに、前述した実施形態は、本発明を例示的に説明するためのものであって、本発明の権利範囲が、特定の実施形態に限定されるものではない。
【産業上の利用可能性】
【００７３】
本発明は、ミニコア基盤の再構成可能プロセッサ、そのためのスケジュール装置及び方法関連の技術分野に適用可能である。
【符号の説明】
【００７４】
１００、２００、８００  再構成可能プロセッサ
１１０  外部リンク
１２０  内部リンク
１３０  ローカルレジスタファイル（ＲＦ）
１４０  制御メモリ
１５０  グローバルレジスタファイル（ＲＦ）
２１０  リンク
３００  スケジュール装置
３１０  ミニコア構成部
３２０  ローカルスケジューラ
３３０  グローバルスケジューラ
７１０  制御メモリ
７２０  サブメモリ
８１０  ループ制御部
８２０  電源制御部
ＭＣ    ミニコア
ＦＵ    ファンクションユニット
【図１】
0006494155.tif 000002
【図２】
0006494155.tif 000003
【図３】
0006494155.tif 000004
【図４】
0006494155.tif 000005
【図５】
0006494155.tif 000006
【図６Ａ】
0006494155.tif 000007
【図６Ｂ】
0006494155.tif 000008
【図７】
0006494155.tif 000009
【図８】
0006494155.tif 000010
【図９】
0006494155.tif 000011