(57)【要約】【課題】少ない配線面積でプログラムを同プロセッサに柔軟にマッピングできるような配線構造を有する動的再構成可能プロセッサを提供する。【解決手段】動的再構成可能プロセッサにおいて、種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、種類Ａｉの演算回路および種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、演算回路群Ｖｉ内の演算回路間配線Ｘｉを、それ以外の演算回路間配線Ｘｉとは異なる演算回路間配線とし、演算回路群Ｖｉ内での演算回路間の接続順序を変更するスイッチ群Ｓｉとを備えた。【選択図】図１
2007141132.tif 000002
【特許請求の範囲】
【請求項１】
種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、
前記演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される前記種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、
前記種類Ａｉの演算回路および前記種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、
前記演算回路群Ｖｉ内の演算回路間配線Ｘｉを、それ以外の前記演算回路間配線Ｘｉとは異なる演算回路間配線とし、前記演算回路群Ｖｉ内での演算回路間の接続順序を変更するスイッチ群Ｓｉとを備えたことを特徴とする動的再構成可能プロセッサ。
【請求項２】
種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、
前記演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される前記種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、
前記種類Ａｉの演算回路および前記種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、
前記演算回路群Ｖｉ内の演算回路同士を前記演算回路間配線Ｘｉとは異なる順序で接続する前記演算回路間配線Ｘｉに追加された配線Ｚｉと、
前記演算回路間配線Ｘｉと前記配線Ｚｉのどちらか一方を有効にするスイッチ群Ｓｉとを備えたことを特徴とする動的再構成可能プロセッサ。
【請求項３】
請求項１または２記載の動的再構成可能プロセッサにおいて、
前記演算回路群Ｖｉ内において前記演算回路間配線Ｘｉで接続された前記種類Ａｉの演算回路と前記種類Ｂの演算回路からなる組同士を接続する演算回路間配線を前記スイッチ群Ｓｉの状態と連動して変更するスイッチ群Ｔｉを備えたことを特徴とする動的再構成可能プロセッサ。
【請求項４】
種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、前記演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される前記種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、前記種類Ａｉの演算回路および前記種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、前記演算回路群Ｖｉ内の演算回路同士を前記演算回路間配線Ｘｉとは異なる順序で接続する前記演算回路間配線Ｘｉに追加された配線Ｚｉと、前記演算回路間配線Ｘｉと前記配線Ｚｉのどちらか一方を有効にするスイッチ群Ｓｉとを備えた動的再構成可能プロセッサを制御するプロセッサ制御プログラムであって、
前記動的再構成可能プロセッサを動作させる論理的な回路構成の情報に基づいて、前記スイッチ群Ｓｉを制御し、前記種類Ａｉの演算回路と前記種類Ｂの演算回路の接続順序を変更することを特徴とするプロセッサ制御プログラム。
【請求項５】
種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、前記演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される前記種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、前記種類Ａｉの演算回路および前記種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、前記演算回路群Ｖｉ内の演算回路同士を前記演算回路間配線Ｘｉとは異なる順序で接続する前記演算回路間配線Ｘｉに追加された配線Ｚｉと、前記演算回路間配線Ｘｉと前記配線Ｚｉのどちらか一方を有効にするスイッチ群Ｓｉと、前記演算回路群Ｖｉ内において前記演算回路間配線Ｘｉで接続された前記種類Ａｉの演算回路と前記種類Ｂの演算回路からなる組同士を接続する演算回路間配線を変更するスイッチ群Ｔｉとを備えた動的再構成可能プロセッサを制御するプロセッサ制御プログラムであって、
前記動的再構成可能プロセッサを動作させる論理的な回路構成の情報に基づいて、前記スイッチ群Ｓｉを制御し、前記種類Ａｉの演算回路と前記種類Ｂの演算回路の接続順序を変更し、前記スイッチ群Ｓｉの制御信号に連動して前記スイッチ群Ｔｉを制御し、前記演算回路群Ｖｉ内において前記演算回路間配線Ｘｉで接続された前記種類Ａｉの演算回路と前記種類Ｂの演算回路からなる組同士を接続する演算回路間配線を前記スイッチ群Ｓｉの状態と連動して変更することを特徴とするプロセッサ制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構成を動的に変更可能な動的再構成可能プロセッサに関し、特に、複数の演算回路と複数の演算回路間配線を構成要素とするプロセッサに適用して有効な技術に関するものである。
【背景技術】
【０００２】
従来、例えば、特開平１１−２５１４４２号公報（特許文献１）に記載されたような、複数の処理デバイスと複数の処理デバイス間の相互接続を提供する接続マトリクスを備えた再構成可能プロセッサデバイスがあった。
【０００３】
また、従来、異なる種類の演算回路から構成される動的再構成可能プロセッサにおいて、タカユキ  スケガワ、ケイスケ  イデ、アンド  トモヨシ  サトウ著、「ダイナミカリー  リコンフィギュラブル  プロセッサ  インプレメンテッド  ウィズ  アイピーフレックスズ  ダップディーエヌエー  テクノロジー」、アイアイシーイー  トランス  インフォメーション  アンド  システム、ボリューム  イー８７  ディー、ナンバー８、１９９７頁から２００３頁、オーガスト  ２００４（Ｔａｋａｙｕｋｉ  ＳＵＧＡＷＡＲＡ、Ｋｅｉｓｕｋｅ  ＩＤＥ、ａｎｄ  Ｔｏｍｏｙｏｓｈｉ  ＳＡＴＯ、”Ｄｙｎａｍｉｃａｌｌｙ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｐｒｏｃｅｓｓｏｒ  Ｉｍｐｌｅｍｅｎｔｅｄ  ｗｉｔｈ  ＩＰＦｌｅｘ’ｓ  ＤＡＰＤＮＰ  Ｔｅｃｈｎｏｌｏｇｙ”、ＩＥＩＣＥ  ＴＲＡＮＳ．ＩＮＦ．  ＆  ＳＹＳＴＥＭ、Ｖｏｌ．Ｅ８７−Ｄ、Ｎｏ．８、ｐｐ．１９９７−２００３、Ａｕｇｕｓｔ  ２００４）（非特許文献１）に記載されているように、演算回路間配線は均一なものであった。
【０００４】
このようなプロセッサでは演算回路間配線は均一な２方向のバス、ＸバスとＹバス、から構成される相互接続バスであり、データの転送元演算回路と転送先演算回路間のルーティングはＸバスまたはＹバスに含まれる配線をスイッチボックスで選択することによって制御する。このスイッチボックスの機能はあらかじめプログラムされたコンフィギュレーションで設定される。
【０００５】
尚、多数の演算回路が２次元的に配置された動的再構成可能プロセッサにおいて、上記のように異なる種類の演算回路を備えるのは、演算回路の稼働率を向上させるためである。
【０００６】
すべての演算回路が同じ機能を持ち、かつ、加減算・乗算・論理演算などの様々な種類の演算に対応している場合、プログラムをこの演算回路アレイにマッピングするのは容易である。しかし、例えば、乗算を少しだけ含み、加減算と論理演算を多く含むプログラムをこのプロセッサにマッピングする場合、大きな面積を必要とする乗算の多くが利用されず、回路面積の利用効率が悪い。ＬＳＩの面積増大はＬＳＩの価格増大につながるため、これは好ましくない。そこで、なるべく小さい面積で各演算回路の稼働率を向上させることが重要となる。このためには、ある演算回路は乗算を主体とした演算のみを含み、他の演算回路は加減算と論理演算を主体とするなど、不均一な演算回路から構成される演算回路アレイを備えることが１つの解となる。このようなプロセッサでは、プログラミングの容易さを向上させるために多くの配線を備える場合がある。これによって、必要な演算が離れた位置にあっても豊富な配線を使ってその演算回路を容易に利用できる。
【特許文献１】特開平１１−２５１４４２号公報
【非特許文献１】タカユキ  スケガワ、ケイスケ  イデ、アンド  トモヨシ  サトウ著、「ダイナミカリー  リコンフィギュラブル  プロセッサ  インプレメンテッド  ウィズ  アイピーフレックスズ  ダップディーエヌエー  テクノロジー」、アイアイシーイー  トランス  インフォメーション  アンド  システム、ボリューム  イー８７  ディー、ナンバー８、１９９７頁から２００３頁、オーガスト  ２００４（Ｔａｋａｙｕｋｉ  ＳＵＧＡＷＡＲＡ、Ｋｅｉｓｕｋｅ  ＩＤＥ、ａｎｄ  Ｔｏｍｏｙｏｓｈｉ  ＳＡＴＯ、”Ｄｙｎａｍｉｃａｌｌｙ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｐｒｏｃｅｓｓｏｒ  Ｉｍｐｌｅｍｅｎｔｅｄ  ｗｉｔｈ  ＩＰＦｌｅｘ’ｓ  ＤＡＰＤＮＰ  Ｔｅｃｈｎｏｌｏｇｙ”、ＩＥＩＣＥ  ＴＲＡＮＳ．ＩＮＦ．  ＆  ＳＹＳＴＥＭ、Ｖｏｌ．Ｅ８７−Ｄ、Ｎｏ．８、ｐｐ．１９９７−２００３、Ａｕｇｕｓｔ  ２００４）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記従来技術では、例えば、２種類の演算回路ＡとＢから構成され、大半は演算回路Ａで、残りは少数の演算回路Ｂが近接して配置された、不均一な構成の動的再構成可能プロセッサに対して、プログラムを同プロセッサに柔軟にマッピングするためには、均一な演算回路から構成される動的再構成可能プロセッサに比べてより多くの配線を追加することが必要となり、全体として多くの配線面積を消費するという問題点がある。
【０００８】
即ち、均一な配線構造にする必要があるため、演算回路Ｂの周辺だけでなくプロセッサ全体に配線を追加させなければならない。
【０００９】
本発明の目的は、少ない配線面積でプログラムを同プロセッサに柔軟にマッピングできるような配線構造を有する動的再構成可能プロセッサおよびそれを制御するプロセッサ制御プログラムを提供することである。
【課題を解決するための手段】
【００１０】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。
【００１１】
本発明による動的再構成可能プロセッサは、種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、種類Ａｉの演算回路および種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、演算回路群Ｖｉ内の演算回路間配線Ｘｉを、それ以外の演算回路間配線Ｘｉとは異なる演算回路間配線とし、演算回路群Ｖｉ内での演算回路間の接続順序を変更するスイッチ群Ｓｉとを備えたものである。
【００１２】
また、本発明による動的再構成可能プロセッサは、種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、種類Ａｉの演算回路および種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、演算回路群Ｖｉ内の演算回路同士を演算回路間配線Ｘｉとは異なる順序で接続する演算回路間配線Ｘｉに追加された配線Ｚｉと、演算回路間配線Ｘｉと配線Ｚｉのどちらか一方を有効にするスイッチ群Ｓｉとを備えたものである。
【００１３】
また、本発明によるプロセッサ制御プログラムは、種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、種類Ａｉの演算回路および種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、演算回路群Ｖｉ内の演算回路同士を演算回路間配線Ｘｉとは異なる順序で接続する演算回路間配線Ｘｉに追加された配線Ｚｉと、演算回路間配線Ｘｉと配線Ｚｉのどちらか一方を有効にするスイッチ群Ｓｉとを備えた動的再構成可能プロセッサを制御するプロセッサ制御プログラムであって、動的再構成可能プロセッサを動作させる論理的な回路構成の情報に基づいて、スイッチ群Ｓｉを制御し、種類Ａｉの演算回路と種類Ｂの演算回路の接続順序を変更するものである。
【００１４】
また、本発明によるプロセッサ制御プログラムは、種類Ａｉ（ｉ＝１，２，…，Ｎ）の演算回路から構成される演算回路群Ｕｉと、演算回路群Ｕｉに含まれる一部の演算回路群およびそれらに接続される種類Ａｉの演算回路とは異なる種類Ｂの演算回路群からなる演算回路群Ｖｉと、種類Ａｉの演算回路および種類Ｂの演算回路のそれぞれを接続する演算回路間配線Ｘｉと、演算回路群Ｖｉ内の演算回路同士を演算回路間配線Ｘｉとは異なる順序で接続する演算回路間配線Ｘｉに追加された配線Ｚｉと、演算回路間配線Ｘｉと配線Ｚｉのどちらか一方を有効にするスイッチ群Ｓｉと、演算回路群Ｖｉ内において演算回路間配線Ｘｉで接続された種類Ａｉの演算回路と種類Ｂの演算回路からなる組同士を接続する演算回路間配線を変更するスイッチ群Ｔｉとを備えた動的再構成可能プロセッサを制御するプロセッサ制御プログラムであって、動的再構成可能プロセッサを動作させる論理的な回路構成の情報に基づいて、スイッチ群Ｓｉを制御し、種類Ａｉの演算回路と種類Ｂの演算回路の接続順序を変更し、スイッチ群Ｓｉの制御信号に連動してスイッチ群Ｔｉを制御し、演算回路群Ｖｉ内において演算回路間配線Ｘｉで接続された種類Ａｉの演算回路と種類Ｂの演算回路からなる組同士を接続する演算回路間配線をスイッチ群Ｓｉの状態と連動して変更するものである。
【発明の効果】
【００１５】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００１６】
本発明によれば、少ない配線面積増加で、不均一な演算回路群から構成される動的再構成可能プロセッサにプログラムを柔軟にマッピングすることができる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。尚、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００１８】
（実施の形態１）
＜動的再構成可能プロセッサの概要＞
図１により、本発明の実施の形態１に係る動的再構成可能プロセッサの概要について説明する。図１は本発明の実施の形態１に係る動的再構成可能プロセッサの概要を説明するための説明図である。
【００１９】
図１において、Ａｉ（ｉ＝１，２，…，Ｎ）は種類Ａｉの演算回路、Ｂは種類Ａｉの演算回路とは異なる種類Ｂの演算回路、Ｕｉは種類Ａｉの演算回路から構成されるいくつかの演算回路群、Ｖｉは演算回路群Ｕｉに含まれる一部の演算回路群とそれらに接続される種類Ｂの演算回路群、Ｘｉは演算回路間配線、Ｚｉは演算回路間配線Ｘｉに追加された配線であって、演算回路群Ｖｉにおける演算回路同士を演算回路間配線Ｘｉとは異なる順序で接続する配線、Ｓｉは配線Ｘに追加されたスイッチ群であって、演算回路間配線Ｘｉと配線Ｚｉのどちらか一方を有効にするスイッチである。
【００２０】
本実施の形態の動的再構成可能プロセッサは、図１に示すように、種類Ａｉの演算回路の中に、種類Ａｉの演算回路とは異なる種類の種類Ｂの演算回路が存在し、種類Ａｉの演算回路と種類Ｂの演算回路を演算回路間配線Ｘｉによりマトリクス状に配線した構成となっている。
【００２１】
そして、種類Ａｉの演算回路と種類Ｂの演算回路とを接続する演算回路間配線Ｘｉに種類Ａｉの演算回路と種類Ｂの演算回路の接続の順序を変更する配線Ｚｉを設け、スイッチ群Ｓｉを制御することにより、マトリクス状の配線内において、種類Ｂの演算回路の接続箇所を変更できるようになっている。
【００２２】
また、このスイッチ群Ｓｉは、例えば動的再構成可能プロセッサを制御するプロセッサ制御プログラムなどの処理により制御されるようになっている。
【００２３】
これにより、種類Ａｉの演算回路と種類Ｂの演算回路の順番を必要に応じて変更することができ、少ない配線面積増加で、動的再構成可能プロセッサにプログラムを柔軟にマッピングすることが可能である。
【００２４】
＜動的再構成可能プロセッサを含むシステムの構成＞
次に、図２〜図４により、本発明の実施の形態１に係る動的再構成可能プロセッサを含むシステム構成について説明する。図２は本発明の実施の形態１に係る動的再構成可能プロセッサを含むシステムの構成を示す構成図、図３は本発明の実施の形態１に係る動的再構成可能プロセッサの配線切り替えスイッチが上側入力を選択した場合の有効配線を示す図、図４は本発明の実施の形態１に係る動的再構成可能プロセッサ配線切り替えスイッチが下側入力を選択した場合の有効配線を示す図である。
【００２５】
図２において、動的再構成可能プロセッサを含むシステムは、ＣＰＵ１０、メインメモリ２０、バス３０、動的再構成可能プロセッサ１００から構成されている。
【００２６】
動的再構成可能プロセッサ１００は、動的再構成可能プロセッサの構成を表す情報であるコンフィギュレーションを管理するコンフィギュレーション管理ユニット４０、ＡとＢで示される合計６個の２種類の演算回路５０１から５０６が２次元状に並んだ演算回路アレイ部５０、種類Ａの演算回路５０１、５０３、５０４、５０６、種類Ａとは異なる種類Ｂの演算回路５０２、５０５、その左側に接する２本の矢印で表現される配線上のデータから、いずれか１本の配線上のデータを選択して５１０の右側に接する配線に流す配線切り替えスイッチ５１０、演算回路間を縦方向に接続する縦方向演算回路間配線５２０、増設された配線（点線部）５３０、演算回路アレイ部５０のうち、配線が増設された部分を表す配線増設部（破線部）６０、配線切り替えスイッチ５０３の切り替えを制御する演算回路位置変更配線７０、ローカルメモリ８０，８１、データ配線９０から構成されている。
【００２７】
増設された配線５３０を含む配線増設部６０とそれ以外の演算回路アレイ部（演算回路５０３と５０６を含む部分）の配線が異なるため、演算回路アレイ部５０全体から見て配線が不均一であることがわかる。
【００２８】
図２において、配線切り替えスイッチ５１０が上側入力を選択した場合の有効配線は、図３に示すように、図２に示した配線５３０を削除した図になる。この場合、６個の演算回路は単純に縦方向と横方向に接続される。
【００２９】
また、図２において、配線切り替えスイッチ５１０が下側入力を選択した場合の有効配線は、図４に示すように、図１に示した配線５３０が有効になる。この場合、６個の演算回路の接続の仕方は以下のようになる。
【００３０】
まず、上側の演算回路５０１、５０２、５０３の接続を説明する。
【００３１】
左側のローカルメモリ８０から入力されるデータは演算回路５０２に入力され、次に演算回路５０１に入力され、最後に演算回路５０３に入力される。
【００３２】
下側の演算回路についても同様に、左側のローカルメモリ８０から入力されるデータは演算回路５０５に入力され、次に演算回路５０４に入力され、最後に演算回路５０６に入力される。
【００３３】
一方、縦方向の接続は配線切り替えスイッチ５１０の動作によらず、演算回路５０１と５０４、５０２と５０５が常に接続されている。
【００３４】
以上より、配線切り替えスイッチ５１０が下側入力を選択した場合、第１列の演算回路と第２列の演算回路の位置が入れ替わったような接続となることがわかる。
【００３５】
このことは、プログラマーにとって、種類Ｂの演算回路が第１列にあるように見えることを意味する。
【００３６】
即ち、図３と図４からわかることは、プログラマーは配線切り替えスイッチ５１０を切り替えることによって、種類Ｂの演算回路が論理的に第１列にあるようにも第２列にあるようにも制御できる、ということである。
【００３７】
＜動的再構成可能プロセッサのプログラムのマッピング＞
次に、図５〜図１１により、本発明の実施の形態１に係る動的再構成可能プロセッサのプログラムのマッピングについて説明する。図５は本発明の実施の形態１に係る動的再構成可能プロセッサにおいて、プログラマーが選択できる論理的な回路構成の一例を示す図であり、図５（ａ）は図３で示した配線切り替えスイッチ５１０が上側入力を選択した場合の回路構成、図５（ｂ）は図３で示した配線切り替えスイッチ５１０が下側入力を選択した場合の回路構成を示している。図６は本発明の実施の形態１に係る動的再構成可能プロセッサの簡単な表示例を示す図、図７は本発明の実施の形態１に係る動的再構成可能プロセッサ内の演算回路の構造と演算回路内の配線構造の一例を示す図、図８は本発明の実施の形態１に係る動的再構成可能プロセッサのプログラムの一例を示す図、図９は本発明の実施の形態１に係る動的再構成可能プロセッサにおいて図８に示すプログラムに対するコントロール・データフローグラフ（ＣＤＦＧ）を示す図、図１０は本発明の実施の形態１に係る動的再構成可能プロセッサにおいて乗算器を２列目にした場合の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング失敗例を示す図、図１１は本発明の実施の形態１に係る動的再構成可能プロセッサにおいて乗算器を１列目にした場合の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング例を示す図である。
【００３８】
図５において、種類Ａの演算回路では加減算と論理演算、種類Ｂの演算回路では乗算ができると仮定している。
【００３９】
このとき、図５（ａ）では、入力データに対して加減算を行い、乗算を行い、最後に論理演算（図では右シフト”＞＞”を表す）を行うような計算式が演算回路アレイに容易にマッピングできることを表している。
【００４０】
一方、図５（ｂ）では、入力データに対して乗算を行い、加減算を行い、最後に論理演算を行うような計算式が演算回路アレイに容易にマッピングできることを表している。
【００４１】
このような動的再構成可能プロセッサの簡単な表示例を図６に示す。わかりやすくするために、演算回路Ｂは六角形で表示している。また、演算回路間の配線は必要なもの以外は省略して記述する。
【００４２】
以降では、この図６の演算回路アレイ部５０を使って、具体的なプログラムのマッピングを表示し、本実施の形態の有効性を示す。
【００４３】
まず、演算回路の内部構造は図７に示すような構成であり、図７（ａ）は図２での５０１で代表される種類Ａの演算回路を示す。
【００４４】
種類Ａの演算回路５０１は、加減算および論理演算を実行可能なＡＬＵ５０１０を有し、コンフィギュレーションによって、このうちの１つの演算が選択できる。
【００４５】
メモリ５０１１には、定数が格納される。尚、定数の設定はコンフィギュレーションで行う。
【００４６】
また、スイッチとしては、その左側に接する５本の矢印で表現される配線上のデータから、いずれか２本の配線上のデータを選択して５１０２の右側に接する配線に流す配線切り替えスイッチ５０１２、その下側に接する２本の矢印で表現される配線上のデータから、いずれか１本の配線上のデータを選択して５１０３の上側に接する配線に流す配線切り替えスイッチ５０１３、その左側に接する４本の矢印で表現される配線上のデータから、いずれか１本の配線上のデータを選択して５１０４の右側に接する配線に流す配線切り替えスイッチ５０１４を有している。
【００４７】
配線切り替えスイッチ５０１４に接続された配線はスルー配線であり、演算回路５０１を経由して他の演算回路へデータを転送するために用いる。
【００４８】
これによって、上側１本、左側２本、下側１本の入力のうち、２つを選択して演算を行い、演算結果を、上側１本、右側２本（同じ演算結果の出力）、下側１本のうちの任意の配線に出力可能であると共に、上側１本、左側２本、下側１本の入力のうち、１つを選択し、上側１本、右側２本、下側１本のうちの、演算結果の出力に使う配線以外の任意の配線に出力可能である。
【００４９】
また、図７（ｂ）は図２での５０２で代表される種類Ｂの演算回路を示す。
【００５０】
種類Ｂの演算回路５０２は、乗算を実行可能なＡＬＵ５０２０を有し、コンフィギュレーションによって、演算が制御される。その他については、図７（ａ）に示す種類Ａの演算回路５０１の構成を同じである。
【００５１】
また、プログラムの一例としては、図８に示すようなプログラムであり、１行目はｆｏｒループであり、変数ｉの値が０から１つずつ増加してＮ−１（Ｎはある定数）になるまで、２行目と３行目の処理を繰り返す。
【００５２】
２行目は配列ａ，とｘのｉ番目の要素の値を乗算した結果と配列ｂとｙのｉ番目の要素の値を乗算した結果の和をとり、それに１を加えた結果を２で割って配列ｖに代入することを表している。
【００５３】
３行目は配列ａ，とｘのｉ番目の要素の値を乗算した結果と配列ｂとｙのｉ番目の要素の値を乗算した結果の差をとり、それに１を加えた結果を２で割って配列ｚに代入することを表している。
【００５４】
この図８に示すプログラムに対するコントロール・データフローグラフ（ＣＤＦＧ）は図９に示すようなものとなる。
【００５５】
図９において、各矩形はデータまたは演算を表す。乗算は”＊”、加算は”＋”、減算は”−”、２で割る除算は１ビット右シフト”＞＞１”に置き換えて表現している。
矢印はデータの流れを表す。
【００５６】
配列ａ，とｘのｉ番目の要素の値を乗算した結果は加算と減算で利用されるので、乗算結果は”＋”と”−”の両方で利用される。
【００５７】
ここで、図９に示すコントロール・データフローグラフ（ＣＤＦＧ）のマッピングについて説明する。
【００５８】
まず、図１０に示すように、乗算器を２列目にした場合の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピングでは、２つの乗算と加減算はマッピングされているが、右シフトがマッピングされていないので、マッピングは失敗である。
【００５９】
尚、乗算への入力は左側からの２本の矢印で表されているが、上側の１本はスルー配線を表し、下側の１本はメモリ内に格納された定数０と入力データとの演算結果を右側に出力することを表す。後者はスルー配線を使った場合と同じ結果、即ち、入力データをそのまま転送することを表す。これらによって、スルー配線２本と同様な効果を得ることができる。
【００６０】
また、加減算を含む演算回路における折れ線の矢印は、左側から入力したデータを下側（加算の場合）または上側（減算の場合）に転送するスルー配線を表す。
【００６１】
また、図１１に示すように、乗算器を１列目にした場合の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピングでは、マッピングは成功となる。
【００６２】
図１０および図１１に示すように、配線切り替えスイッチ５１０を使って論理的な回路構成を変更することによって動的再構成可能プロセッサの柔軟性が増し、種類Ｂの演算回路が論理的に第１行目にある場合にはマッピングできなかったプログラムが、種類Ｂの演算回路を論理的に第２行目にすることでマッピングが可能になることがわかる。
【００６３】
＜従来の動的再構成可能プロセッサとの比較＞
ここで図１２〜図１７により、比較例として、従来の動的再構成可能プロセッサに図９のＣＤＦＧをマッピングする場合を考察する。図１２は比較例としての従来の動的再構成可能プロセッサの一例を示す図、図１３は図１２における各配線スイッチの構造を示す図、図１４は従来の動的再構成可能の簡単な表示例を示す図、図１５は図１２における演算回路の構造と配線構造を示す図、図１６は従来の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング失敗例を示す図、図１７は配線数を増加させた従来の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング例を示す図である。
【００６４】
図１２において、動的再構成可能プロセッサ１００は配線１１０２で接続されている。
【００６５】
配線１１０２はそれぞれ、スイッチボックス１１００を介して接続されており、４つのひし形各々はルーティングスイッチを表し、上下左右のいずれか１つまたは２つの入力を上下左右のいずれかに出力する機能を持つ。詳細は図１３で説明する。
【００６６】
また、非選択状態も許すスイッチと配線との接合部１１０１を有し、この接合部１１０１は２つの配線１１０２のいずれかに接続された配線を選択することも可能であるが、どちらも選択しないことも可能であるようなスイッチである。
【００６７】
演算回路５０１から５０６は、プログラマーはスイッチボックス１１００内のルーティングスイッチをコンフィギュレーションで設定することによって演算回路アレイ内の配線上のデータの流れを制御し、接合部１１０１内のスイッチをコンフィギュレーションで設定することによって演算回路と配線上のデータのやり取りを制御する。
【００６８】
図１３において、図１３（ａ）は非選択状態も許すスイッチと配線との接合部１１０１を拡大した図である。接合部１１０１は、どの配線にも接続されてない端子１２００と、スイッチ１２０１から構成されている。スイッチ１２０１はコンフィギュレーションによって、配線１２０２を配線１２０３、１２０４のいずれかと接続するか、または、配線１２０２を端子１２００と接続する。後者は配線１２０２をどの配線にも接続しないことと同じである。
【００６９】
図１３（ｂ）はスイッチボックス１１００を拡大した図である。スイッチボックス１１００は、スイッチボックス内の１つのルーティングスイッチ１２０５から構成されている。
【００７０】
図１３（ｃ）はルーティングスイッチ１２０５の構成例である。ルーティングスイッチ１２０５は、図１３（ａ）で示したスイッチ１２０１と同様な機能を持つスイッチ１２０６である。ただし、スイッチ１２０６は１配線と１配線をつなぐか、つながないかを選択する。スイッチ１２０７は図１３（ａ）で示したスイッチ１２０１と同じ機能を持つスイッチである。スイッチ１２０８は右下に接する配線のどちらか一方を必ず選択するスイッチである。
【００７１】
ルーティングスイッチ１２０５によって、上下左右のうちの任意の方向から入力されるデータは、その方向以外の任意の方向に出力できる。また、同時に２つの方向に出力できる場合もある。例えば、左側から入力されるデータは、上側と、右または下側の２方向に出力できる。また、２つのデータ転送を同時にできる場合もある。例えば、左側から入力されるデータを上側に出力することと、右側から入力されるデータを下側に出力することは同時にできる。ただし、左側から入力されるデータを上側以外（右側または下側）に出力する場合は、配線１２０９を使うため、他のデータ転送を同時に行うことはできない。
【００７２】
ここで、図１２に示した従来の動的再構成可能の簡単な表示例を図１４に示す。図１４においては、演算回路間の配線は必要なもの以外は省略して記述する。
【００７３】
以降では、この図１４の演算回路アレイ部５０を使って、図９で示されたＣＤＦＧをマッピングし、配線１１０２が２本ではマッピングできないことと、配線１１０２を３本にするとマッピングできることを示す。
【００７４】
図１５は図１２における演算回路の構造と配線構造を示す。スルー配線がないこと以外、図７で示した演算回路と同じである。
【００７５】
従来の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング失敗例としては、図１６に示すようなものであり、太線はデータの流れを表す。図１６の左端にある４本のデータの流れは、左側ローカルメモリ８０から演算回路アレイ５０に入力されるデータを表す。これらは各々、上側と下側の配線を通って乗算回路に至る。乗算回路５０２の計算結果は、上方向と右方向から出力され、各々、演算回路５０３と５０６に至る。乗算回路５０５の計算結果も同様に、下方向と右方向から出力され、各々、演算回路５０６と５０３に至る。演算回路５０３と５０６における計算結果は各々、上方向と下方向に出力され、各々、演算回路５０１と５０４に至る。
【００７６】
上記のようにすべての演算はマッピングされているが、右シフトの結果を右側ローカルメモリ８１へ出力するための配線がないので、マッピングは失敗である。
【００７７】
また、従来では、動的再構成可能プロセッサへの図９のＣＤＦＧのマッピングを成功させるためには、図１７に示すように、配線数を増加させている。
【００７８】
図１７に示すように、配線１１０２を３本にすることによって、図１６の右シフト結果を右側へ図のように出力することができ、図９のＣＤＦＧのマッピングを成功させることができる。
【００７９】
ここで、図１２に示した従来技術において用いる配線数と図２で示した本実施の形態における総配線長を比較する。
【００８０】
演算回路アレイはｍ行ｎ列、演算回路は正方形とし、各辺の長さをＬ、配線１本はｂビットの配線から構成されているとする。
【００８１】
従来技術において配線１１０２はａ本とする。従来技術において、演算回路と配線１１０２を接続する配線、および、演算回路内の配線の長さは無視できるとする。
【００８２】
このとき、従来技術による総配線長はａ＊ｂ＊Ｌ＊（２＊ｍ＊ｎ＋ｍ＋ｎ）となる。
【００８３】
一方、本発明において配線はａ／２本用いるとする。本配線は演算回路内のスルー配線を表す。
【００８４】
演算回路内のＡＬＵの入出力となる配線や演算回路アレイ内の演算回路同士を接続する配線長は無視できるとする。このとき、スルー配線の総配線長はａ＊ｂ＊ｍ＊Ｌ＊ｎ／２となる。また、配線５３０の総配線長はａ＊ｂ＊ｍ＊Ｌ＊４となる。よって、本発明による総配線長はａ＊ｂ＊ｍ＊Ｌ＊（４＋ｎ／２）となる。
【００８５】
よって、本実施の形態による総配線長の方が、ａ＊ｂ＊Ｌ＊（３＊ｍ＊（ｎ−２）／２＋ｎ）だけ短くなる。これは、即ち、演算回路アレイが２列以上のときは本実施の形態の方が配線面積が小さいことを示す。
【００８６】
（実施の形態２）
実施の形態２は、実施の形態１において、演算回路５０１と演算回路５０４、演算回路５０２と演算回路５０５は縦方向の配線５２０によって接続されていたが、演算回路５０１を演算回路５０２または演算回路５０５と接続できるように、同様にして、演算回路５０３を演算回路５０２または演算回路５０５と接続できるように配線とスイッチを追加したものである。
【００８７】
＜動的再構成可能プロセッサの構成＞
次に、図１８により、本発明の実施の形態２に係る動的再構成可能プロセッサの構成について説明する。図１８は本発明の実施の形態２に係る動的再構成可能プロセッサの構成を示す構成図である。
【００８８】
まず、実施の形態１の図２と本実施の形態の図１８の違いを説明する。
【００８９】
実施の形態１での図２では、演算回路５０１と演算回路５０４、演算回路５０２と演算回路５０５は縦方向の配線５２０によって接続されていた。
【００９０】
本実施の形態の図１８では、演算回路５０１を演算回路５０２または５０５と接続できるように、同様にして、演算回路５０３を演算回路５０２または５０５と接続できるように配線とスイッチを追加している。
【００９１】
図１８においては、動的再構成可能プロセッサは、追加されたスイッチ５２１と、追加された配線５２２を有している。追加されたスイッチ５２１によりスイッチ群Ｔｉを構成している。
【００９２】
また、実施の形態１の図２では演算回路位置変更配線７０は１本だけであるが、本実施の形態の図１８では演算回路位置変更配線７０と演算回路位置変更配線７４の２本があり、各々、別の設定を行うことができる。
【００９３】
配線７１は演算回路位置変更配線７０から分かれた配線であり、演算回路位置変更配線７０と同じ信号を送る。配線７３は演算回路位置変更配線７４から分かれた配線であり、演算回路位置変更配線７４と同じ信号を送る。
【００９４】
配線７１と配線７３からの信号は、排他的論理和を計算する演算器７５に入力され、その演算結果は配線７２を通じてスイッチ５２１に入力される。
【００９５】
スイッチ５２１の近傍に記入された「０」の記号は排他的論理和の演算結果が「０」のときに選択される入力配線を、「１」の記号は排他的論理和の演算結果が「１」のときに選択される入力配線を表す。
【００９６】
即ち、スイッチ５２１に演算器７５から「１」の信号が入力されたときには、本実施の形態で追加された配線５２２からの信号がスイッチ５２１から出力される。
【００９７】
これによって、演算回路位置変更配線７０と演算回路位置変更配線７４に同じ値が流れるときは、縦方向の演算回路は図２と同じ方法で接続される。即ち、演算回路５０１は演算回路５０４と接続され、演算回路５０２は演算回路５０５と接続される。
【００９８】
この状態では、演算回路位置変更配線７０と演算回路位置変更配線７４に同じ値が流れるので、演算回路５０１と演算回路５０２の接続順と演算回路５０４と演算回路５０５の接続順は同じとなる。従って、この状態では常に実施の形態１での接続と同じとなる。
【００９９】
一方、演算回路位置変更配線７０と演算回路位置変更配線７４に異なる値が流れるときは、縦方向の演算回路は、実施の形態１の図２とは異なる方法で接続される。即ち、演算回路５０１は演算回路５０５と接続され、演算回路５０２は演算回路５０４と接続される。
【０１００】
以上によって、例えば、１行目の演算回路を論理的に演算回路５０１、演算回路５０２の順に配置し、２行目の演算回路を論理的に演算回路５０５、演算回路５０４の順に配置したときでも、縦方向の演算回路間の関係は、演算回路５０１と演算回路５０５が接続され、演算回路５０２と演算回路５０４が接続され、演算回路が矛盾なく設定される。
【０１０１】
＜プログラマーが選択できる論理的な回路構成＞
次に、図１９により、本発明の実施の形態２に係る動的再構成可能プロセッサにおいてプログラマーが選択できる論理的な回路構成について説明する。図１９は本発明の実施の形態２に係る動的再構成可能プロセッサにおいてプログラマーが選択できる論理的な回路構成を示す図である。
【０１０２】
まず、図１８において左右方向の演算器の入れ替えを制御するスイッチ５１０は演算回路位置変更配線７０を流れる値が０のときは上側配線を選択し、１のときは下側配線を選択すると仮定する。
【０１０３】
また、配線７０と配線７４に対して各々、信号「０」と「０」を与えた場合、それらの排他的論理和は「０」となって演算回路５０１と演算回路５０４、および、演算回路５０２と演算回路５０５が接続されるため、プログラマーから見える論理的な回路構成は図１９（ａ）で与えられる。ここで、種類Ａの演算回路では加算を種類Ｂの演算回路では乗算を選択したと仮定した。
【０１０４】
一方、配線７０と配線７４に対して各々、信号「１」と「１」を与えた場合、それらの排他的論理和は「０」となって演算回路５０２と演算回路５０５、および、演算回路５０１と演算回路５０４が接続されるため、プログラマーから見える論理的な回路構成は図１９（ｂ）で与えられる。
【０１０５】
次に、配線７０と配線７４に対して各々、信号「１」と「０」を与えた場合、そららの排他的論理和は「１」となって演算回路５０２と演算回路５０４、および、演算回路５０１と演算回路５０５が接続されるため、プログラマーから見える論理的な回路構成は図１８（ｃ）で与えられる。
【０１０６】
最後に、配線７０と配線７４に対して各々、信号「０」と「１」を与えた場合、そららの排他的論理和は「１」となって演算回路５０１と演算回路５０５、および、演算回路５０２と演算回路５０４が接続されるため、プログラマーから見える論理的な回路構成は図１８（ｄ）で与えられる。
【０１０７】
以上より、本実施の形態の動的再構成可能プロセッサにおいてプログラマーは、図１８（ａ）〜図１８（ｄ）で示したような様々な回路構成を設定できるので、プログラミングが非常に容易になる。
【０１０８】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【０１０９】
本発明は、構成を動的に変更可能な動的再構成可能プロセッサに関し、特に、複数の演算回路と複数の演算回路間配線を構成要素とするプロセッサに適用可能である。
【図面の簡単な説明】
【０１１０】
【図１】本発明の実施の形態１に係る動的再構成可能プロセッサの概要を説明するための説明図である。
【図２】本発明の実施の形態１に係る動的再構成可能プロセッサを含むシステムの構成を示す構成図である。
【図３】本発明の実施の形態１に係る動的再構成可能プロセッサの配線切り替えスイッチが上側入力を選択した場合の有効配線を示す図である。
【図４】本発明の実施の形態１に係る動的再構成可能プロセッサ配線切り替えスイッチが下側入力を選択した場合の有効配線を示す図である。
【図５】本発明の実施の形態１に係る動的再構成可能プロセッサにおいて、プログラマーが選択できる論理的な回路構成の一例を示す図である。
【図６】本発明の実施の形態１に係る動的再構成可能プロセッサの簡単な表示例を示す図である。
【図７】本発明の実施の形態１に係る動的再構成可能プロセッサ内の演算回路の構造と演算回路内の配線構造の一例を示す図である。
【図８】本発明の実施の形態１に係る動的再構成可能プロセッサのプログラムの一例を示す図である。
【図９】本発明の実施の形態１に係る動的再構成可能プロセッサにおいて図８に示すプログラムに対するコントロール・データフローグラフ（ＣＤＦＧ）を示す図である。
【図１０】本発明の実施の形態１に係る動的再構成可能プロセッサにおいて乗算器を２列目にした場合の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング失敗例を示す図である。
【図１１】本発明の実施の形態１に係る動的再構成可能プロセッサにおいて乗算器を１列目にした場合の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング例を示す図である。
【図１２】比較例としての従来の動的再構成可能プロセッサの一例を示す図である。
【図１３】図１２における各配線スイッチの構造を示す図である。
【図１４】従来の動的再構成可能の簡単な表示例を示す図である。
【図１５】図１２における演算回路の構造と配線構造を示す図である。
【図１６】従来の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング失敗例を示す図である。
【図１７】配線数を増加させた従来の動的再構成可能プロセッサへの図９のＣＤＦＧのマッピング例を示す図である。
【図１８】本発明の実施の形態２に係る動的再構成可能プロセッサの構成を示す構成図である。
【図１９】本発明の実施の形態２に係る動的再構成可能プロセッサにおいてプログラマーが選択できる論理的な回路構成を示す図である。
【符号の説明】
【０１１１】
Ａｉ（ｉ＝１，２，…，Ｎ）…種類Ａｉの演算回路、Ｂ…種類Ａｉの演算回路とは異なる種類Ｂの演算回路、Ｕｉ…種類Ａｉの演算回路から構成されるいくつかの演算回路群、Ｗｉ…演算回路群Ｕｉに含まれる、ある演算回路群、Ｖｉ…どのＷｉにも含まれないＵｉ中の演算回路群とそれらに接続される種類Ｂの、ある演算回路群、Ｘ…演算回路間配線、Ｚｉ…配線Ｘに追加された配線であって、演算回路群Ｖｉにおける演算回路同士をＸとは異なる順序で接続する配線、Ｓｉ…配線Ｘに追加されたスイッチであって、演算回路間配線Ｘと配線Ｚｉのどちらか一方を有効にするスイッチ、１０…ＣＰＵ、２０…メインメモリ、３０…バス、４０…コンフィギュレーション管理ユニット、５０…演算回路アレイ部、５０１、５０３、５０４、５０６…種類Ａの演算回路、５０２、５０５…種類Ｂの演算回路、５１０…配線切り替えスイッチ、５２０…縦方向演算回路間配線、５３０…増設された配線、６０…配線増設部、７０…演算回路位置変更配線、８０…ローカルメモリ、８１…ローカルメモリ、９０…データ配線、１００…動的再構成可能プロセッサ。
【図１】
2007141132.tif 000003
【図２】
2007141132.tif 000004
【図３】
2007141132.tif 000005
【図４】
2007141132.tif 000006
【図５】
2007141132.tif 000007
【図６】
2007141132.tif 000008
【図７】
2007141132.tif 000009
【図８】
2007141132.tif 000010
【図９】
2007141132.tif 000011
【図１０】
2007141132.tif 000012
【図１１】
2007141132.tif 000013
【図１２】
2007141132.tif 000014
【図１３】
2007141132.tif 000015
【図１４】
2007141132.tif 000016
【図１５】
2007141132.tif 000017
【図１６】
2007141132.tif 000018
【図１７】
2007141132.tif 000019
【図１８】
2007141132.tif 000020
【図１９】
2007141132.tif 000021