(57)【特許請求の範囲】
【請求項１】
分岐と演算を含み、分岐条件の組み合わせによりｎ本のパスを通りうるアルゴリズムを複数回繰り返すことで、変数に対し繰り返し演算を実行する処理回路であって、
前記アルゴリズムのｎ本のパスのそれぞれを通過した場合の最大ｎ通りの候補演算結果をそれぞれ出力する候補演算部と、
該候補演算部から入力する最大ｎ通りの候補演算結果のうちの１つを前記アルゴリズムの分岐条件により選択して出力する選択部と、
該選択部の出力を１クロック分遅延させる遅延素子と、
該遅延素子を介して入力する前記選択部の出力と初期値との一方を開始信号に応じて選択して前記候補演算部に入力させる初期値入力回路と、
を有することを特徴とする処理回路。
【請求項２】
前記アルゴリズムがｍ個の分岐を持ち、
前記選択部が、前記ｍ（ｍ≧２）個の分岐に対応してセレクタをｍ段のツリー状に積み重ねた構成でｍ本の選択信号入力を持ち、
前記ｍ段のそれぞれの分岐のどちらを選択するかの分岐条件判断結果を出力するｍ本の出力をもつ分岐条件演算部を有し、
該分岐条件演算部のｍ本の出力が、前記選択部のｍ本の選択信号入力にそれぞれ接続されていることを特徴とする請求項１に記載の処理回路。
【請求項３】
前記候補演算部は、１つあるいは複数の演算回路が直列に接続された候補演算回路を前記最大ｎ通りの候補演算結果に対応するように最大ｎ組持ち、
該候補演算回路において、直列に接続された前記演算回路のうち、前記初期値入力回路からの出力を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする請求項１または２に記載の処理回路。
【請求項４】
前記初期値入力回路の出力が、前記分岐条件演算部に入力されており、
前記分岐条件演算部は、１つあるいは複数の演算回路が直列に接続された分岐条件演算回路を前記ｍ本の出力に対応するようにｍ組持ち、
前記分岐条件演算部において、直列に接続された前記演算回路のうち、前記初期値入力回路からの出力結果を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする請求項２または３に記載の処理回路。
【請求項５】
分岐と演算を含み、分岐条件の組み合わせによりｎ本のパスを通りうるアルゴリズムをｋ（ｋ≧２）回毎複数回繰り返すことで、変数に対し繰り返し演算を実行する処理回路であって、
前記ｋ回繰り返した場合に通りうるｎｋ本のパスのそれぞれを通過した場合のｎｋ通りの候補演算結果をそれぞれ出力する候補演算部と、
該候補演算部から入力するｎｋ通りの候補演算結果のうちの１つを前記アルゴリズムの分岐条件により選択して出力する選択部と、
該選択部の出力を１クロック分遅延させる遅延素子と、
該遅延素子を介して入力する前記選択部の出力との初期値との一方を開始信号に応じて選択して前記候補演算部に入力させる初期値入力回路と、
を有することを特徴とする処理回路。
【請求項６】
前記アルゴリズムがｍ個の分岐を持ち、
前記選択部が、前記ｍ個の分岐に対応してセレクタを最大でｍ×ｋ段のツリー状に積み重ねた構成で、最大で該セレクタの個数分の選択信号入力を持ち、
前記ｍ×ｋ段のそれぞれの分岐のどちらを選択するかの分岐条件判断結果を出力する最大で前記セレクタの個数分の出力をもつ分岐条件演算部を有し、
該分岐条件演算部の各出力が、前記選択部の各選択信号入力に接続されていることを特徴とする請求項５に記載の処理回路。
【請求項７】
前記候補演算部は、１つあるいは複数の演算回路が直列に接続された候補演算回路をｎｋ通りの候補演算結果に対応するようにｎｋ組持ち、
前記候補演算回路において、直列に接続された前記演算回路のうち、前記初期値入力回路からの出力を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする請求項５または６に記載の処理回路。
【請求項８】
前記初期値入力回路の出力が、前記分岐条件演算部に入力されており、
前記分岐条件演算部は、１つあるいは複数の演算回路が直列に接続された分岐条件演算回路を、最大で前記セレクタの数の組だけもち、
前記分岐条件演算部において、直列に接続された前記演算回路のうち、前記選択部からの出力結果を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする請求項６又は７に記載の処理回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐と演算を含んだアルゴリズムを繰り返し演算する処理を高速に行うための処理回路に関するものである。
【背景技術】
【０００２】
複数のデータに対し演算処理を行う回路の高速化手法としては、パイプラインと呼ばれる手法が広く知られている（非特許文献１、非特許文献２）。この手法は、全体の回路を処理時間が概ね等しくなるような複数セグメントに分割し、各セグメント間にデータラッチ（同期レジスタ）を挿入するものである。この手法では、演算を完了するまでに、分割したセグメントの個数分のクロックサイクルの時間が必要になるが、回路を細かなセグメントに分割することで、クロックの高速化が可能となり、かつ１クロック毎に１つの演算結果が出力されるため、演算処理能力の向上が図れる。
【０００３】
具体例として、図１５のフローチャートを回路化することを考える。フローチャートをそのまま回路化したものが図１６である。まず、演算「Ｒ＋Ａ」を行う演算器１１と、演算器１１を通さないパスを接続した１番目のセレクタ２１を、分岐条件１によって駆動する。このセレクタ２１の出力が２分割され演算「Ｒ＋Ｂ」を行う演算器１２と演算「Ｒ＋Ｃ」を行う演算器１３にそれぞれ入力される。これら２つの演算器１２，１３の出力が２番目のセレクタ２２に接続されこのセレクタ２２は分岐条件２によって切り替えられるようになっている。２番目のセレクタ２２の出力も２分割され演算「Ｒ＋Ｄ」を行う演算器１４と演算「Ｒ＋Ｅ」を行う演算器１５にそれぞれ入力される。これら２つの演算器１４，１５の出力が３番目のセレクタ２３に接続され、このセレクタ２３は分岐条件３によって切り替えられるようになっている。３番目のセレクタ２３からの出力は、クロックによってデータをラッチするＤフリップフロツプ３３に入力される。
【０００４】
このような構成では、データが３段のセレクタと３個の演算器を通過する時間よりもクロックサイクルを短くすることができないため、クロック速度が高められない。そのため図１７のように、回路の途中に２個のＤフリップフロップ３１，３２を挿入し、３個のセグメントに分割するパイプライン化が行われる。このパイプライン化により、演算器１段とセレクタ１段の処理を行う時間までクロックサイクルを短くできるため、クロック速度を約３倍に高速化することができる。このパイプライン化により、１つのデータを投入してからその演算結果が得られるまでに３クロックかかるようになるものの、１クロックごとに１データの処理結果が得られるため、トータルの演算性能は約３倍に高められる。
【０００５】
【非特許文献１】森下  巌、「岩波講座マイクロエレクトロニクス５  マイクロコンピュータのハードウエア」、１２６−１２８頁、岩波書店、１９８４年
【非特許文献２】Kai Hwang、堀越  彌、「コンピュータの高速演算方式」、３７７−３８０頁、近代科学社、１９８０年）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、このパイプラインを用いて高速化するためには、各クロックごとにパイプラインに投入されるデータに因果関係がないことが前提となる。投入するデータに因果関係がなければ、各クロックサイクルごとに連続してパイプライン回路にデータを投入できるが、パイプライン回路の演算結果が次にパイプラインに投入されるデータに影響を与えるような場合は、必要とされる演算結果がパイプラインから出力されるまで、そのデータをパイプライン回路に投入できず、待ち時間が生じる。この現象をパイプラインハザードと呼び、パイプライン回路の効率を落とす原因として広く知られている。
【０００７】
図１５のアルゴリズムにフィードバックを加えた図１８のようなアルゴリズムの場合、常に演算回路からの出力を次の次の演算の入力として利用することになるために、パイプライン化による高速化は不可能となる。図１７の処理回路にフィードバックを加えた図１９Ｂの回路では、フィードバックする演算結果が得られるまでに３クロックかかるため、次のデータの入力が行えるのは必然的に３クロック後となり、３クロックに１度しか演算結果が得られなくなるため、パイプライン化の意味をなさない。
【０００８】
この場合は、図１６にフィードバック接続を行った図１９Ａのような回路にせざるを得ず、パイプライン手法を用いたクロックの高速化が行えないため、演算のスループットが低くなると言う課題があった。また、並列処理が不可能なため、１クロックで１ループ分の演算しか行えず、処理能力向上に限界があった。
【０００９】
本発明の目的は、このようにパイプライン化による高速化が不可能な、フィードバックループをもったアルゴリズムを高速に演算できる処理回路を実現することである。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、請求項１にかかる発明の処理回路は、分岐と演算を含み、分岐条件の組み合わせによりｎ本のパスを通りうるアルゴリズムを複数回繰り返すことで、変数に対し繰り返し演算を実行する処理回路であって、前記アルゴリズムのｎ本のパスのそれぞれを通過した場合の最大ｎ通りの候補演算結果をそれぞれ出力する候補演算部と、該候補演算部から入力する最大ｎ通りの候補演算結果のうちの１つを前記アルゴリズムの分岐条件により選択して出力する選択部と、該選択部の出力を１クロック分遅延させる遅延素子と、該遅延素子を介して入力する前記選択部の出力と初期値との一方を開始信号に応じて選択して前記候補演算部に入力させる初期値入力回路と、を有することを特徴とする。
請求項２にかかる発明は、請求項１に記載の処理回路において、前記アルゴリズムがｍ（ｍ≧２）個の分岐を持ち、前記選択部が、前記ｍ個の分岐に対応してセレクタをｍ段のツリー状に積み重ねた構成でｍ本の選択信号入力を持ち、前記ｍ段のそれぞれの分岐のどちらを選択するかの分岐条件判断結果を出力するｍ本の出力をもつ分岐条件演算部を有し、該分岐条件演算部のｍ本の出力が、前記選択部のｍ本の選択信号入力にそれぞれ接続されていることを特徴とする。
請求項３にかかる発明は、請求項１または２に記載の処理回路において、前記候補演算部が、１つあるいは複数の演算回路が直列に接続された候補演算回路を前記最大ｎ通りの候補演算結果に対応するように最大ｎ組持ち、該候補演算回路において、直列に接続された前記演算回路のうち、前記初期値入力回路からの出力を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする。
請求項４にかかる発明は、請求項２または３に記載の処理回路において、前記初期値入力回路の出力が、前記分岐条件演算部に入力されており、前記分岐条件演算部は、１つあるいは複数の演算回路が直列に接続された分岐条件演算回路を前記ｍ本の出力に対応するようにｍ組持ち、前記分岐条件演算部において、直列に接続された前記演算回路のうち、前記初期値入力回路からの出力結果を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする。
請求項５にかかる発明の処理回路は、分岐と演算を含み、分岐条件の組み合わせによりｎ本のパスを通りうるアルゴリズムをｋ（ｋ≧２）回毎複数回繰り返すことで、変数に対し繰り返し演算を実行する処理回路であって、前記ｋ回繰り返した場合に通りうるｎｋ本のパスのそれぞれを通過した場合のｎｋ通りの候補演算結果をそれぞれ出力する候補演算部と、該候補演算部から入力するｎｋ通りの候補演算結果のうちの１つを前記アルゴリズムの分岐条件により選択して出力する選択部と、該選択部の出力を１クロック分遅延させる遅延素子と、該遅延素子を介して入力する前記選択部の出力との初期値との一方を開始信号に応じて選択して前記候補演算部に入力させる初期値入力回路と、を有することを特徴とする。
請求項６にかかる発明は、請求項５に記載の処理回路において、前記アルゴリズムがｍ個の分岐を持ち、前記選択部が、前記ｍ個の分岐に対応してセレクタを最大でｍ×ｋ段のツリー状に積み重ねた構成で、最大で該セレクタの個数分の選択信号入力を持ち、前記ｍ×ｋ段のそれぞれの分岐のどちらを選択するかの分岐条件判断結果を出力する最大で前記セレクタの個数分の出力をもつ分岐条件演算部を有し、該分岐条件演算部の各出力が、前記選択部の各選択信号入力に接続されていることを特徴とする。
請求項７にかかる発明は、請求項５または６に記載の処理回路において、前記候補演算部が、１つあるいは複数の演算回路が直列に接続された候補演算回路をｎｋ通りの候補演算結果に対応するようにｎｋ組持ち、前記候補演算回路において、直列に接続された前記演算回路のうち、前記初期値入力回路からの出力を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする。
請求項８にかかる発明は、請求項６又は７に記載の処理回路において、前記初期値入力回路の出力が、前記分岐条件演算部に入力されており、前記分岐条件演算部は、１つあるいは複数の演算回路が直列に接続された分岐条件演算回路を、最大で前記セレクタの数の組だけもち、前記分岐条件演算部において、直列に接続された前記演算回路のうち、前記選択部からの出力結果を受け取って演算を行う演算回路が直列接続の最終段になるように接続されていることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、演算と分岐が組み合わさりフィードバックループをもったアルゴリズムでも、演算をまとめて行うことで、クリティカルパスとなるフィードバックループの遅延時間を削減できるため、クロックが高速化でき、演算速度の向上が可能となる。さらに、複数回繰り返した分の演算結果を候補演算部で演算しておくことにより、１クロックで複数回分の演算が可能となり、演算のスループットを高めることが可能となる。
【発明を実施するための最良の形態】
【００１２】
本発明は、分岐と演算を含み、分岐条件の組み合わせによりｎ本のパスを通りうるアルゴリズムを複数回繰り返すことで、変数に対し繰り返し演算を実行するとき、投入した初期値について、前記アルゴリズムのｎ本のパスのそれぞれを通過した場合のｎ通りの演算を行い、該演算結果のうちの１つを前記アルゴリズムの分岐条件により選択し、該選択した演算結果について１クロック分遅延させてから、前記アルゴリズムのｎ本のそれぞれを通過した場合のｎ通りの演算を行い、これを繰り返すものである。
【００１３】
＜実施例１＞
以下、本発明の実施例１を示す。図１８のフローチャートにて示されるアルゴリズムを実行する実施例１の処理回路について説明する。図１８のフローチャートは、分岐条件１、２、３の３段の分岐と演算Ａ、Ｂ、Ｃ、Ｄ、Ｅの６個の演算からなるフィードバックループを持つ。変数Ｒに初期値ｉｎｉｔが与えられた後、分岐条件１によって変数Ｒに対する演算Ａ（Ｒ＝Ｒ＋Ａ）が行われるか何も行わないかが選択される。その後、分岐条件２によって演算Ｂ（Ｒ＝Ｒ＋Ｂ）または演算Ｃ（Ｒ＝Ｒ＋Ｃ）のどちらが行われるかが選択される。最後に、分岐条件３によって演算Ｄ（Ｒ＝Ｒ＋Ｄ）または演算Ｅ（Ｒ＝Ｒ＋Ｅ）のどちらが行われるかが選択され、その演算結果が再び分岐条件１の上部へ戻され演算が繰り返される。変数Ｒは、演算の途中で適宜読み出されるが、その読み出しについてはフローチャート中に図示していない。
【００１４】
実施例１の処理回路は、図１のような構成をとる。この処理回路は大きく分けて候補演算部１００と、選択部２００と、Ｄフリップフロップ３００と、分岐条件演算部４００と、初期値入力回路５００からなる。候補演算部１００は中に８組の候補演算回路１０１〜１０８を含み、この８組の候補演算回路１０１〜１０８が、図１８のフローチャートの全てのパスを通った場合の８通りの演算結果を出力する。
【００１５】
この８通りの演算結果は選択部２００に入力される。選択部２００は３段の２入力セレクタからなり、１段目は４個のセレクタ２０１〜２０４、２段目は２個のセレクタ２０５，２０６、３段目は１個のセレクタ２０７で、計７個のセレクタがツリー状に接続されている。１段目の４個のセレクタ２０１〜２０４のそれぞれに、候補演算部１００からの出力が２本ずつ、計８本接続されている。選択部２００の１段目の４個のセレクタ２０１〜２０４の選択信号には、４個全てに分岐条件３の分岐条件判断結果が入力され、この選択信号により各セレクタ２０１〜２０４の２つの入力のどちらかを選択するようになっている。同様に、２段目の２個のセレクタ２０５，２０６の選択信号には、分岐条件２の分岐条件判断結果が入力され、３段目の１個のセレクタ２０７の選択信号には、分岐条件１の分岐条件判断結果が入力され、それぞれセレクタの２つの入力のうちどちらかを選択するようになっている。
【００１６】
初期値入力回路５００は、Ｄフリップフロップ３００により遅延された選択部２００の出力と、開始入力とが接続されており、開始信号に従ってセレタタ５０１を切り替えることで、候補演算部１００に初期値ｉｎｉｔ、あるいはフィードバック値のいずれかを入力する。
【００１７】
分岐条件演算部４００は、分岐条件１、分岐条件２、分岐条件３のそれぞれの判断を行った結果を出力する３本の信号線をもっており、この３本の判断結果が前述のように選択部２００に入力され、選択部２００の各セレクタ２０１〜２０７に接続されている。
【００１８】
この回路の考え方について以下に説明する。図１８に示されるフローチャートでは、２分岐が３段つながった構成となっており、このフローチャートが１サイクルで通りうるパスは、２の３乗の８通りとなる。具体的には、分岐条件１によって、演算「Ｒ＝Ｒ＋Ａ」が行われるか何も行われないかのどちらかが、分岐条件２によって、演算「Ｒ＝Ｒ＋Ｂ」が行われるか演算「Ｒ＝Ｒ＋Ｃ」が行われるかがどちらかが、最後に、分岐条件３によって、演算「Ｒ＝Ｒ＋Ｄ」が行われるか演算「Ｒ＝Ｒ＋Ｂ」が行われるかのどちらかが選択される。すなわち、通りうる全てのパスは、「何もしない、Ｒ＝Ｒ＋Ａ」の２つと、「Ｒ＝Ｒ＋Ｂ，Ｒ＝Ｒ＋Ｃ」の２つと、「Ｒ＝Ｒ＋Ｄ，Ｒ＝Ｒ＋Ｅ」の２つとから、それぞれ１つずつを選んだ組み合わせ和であることから、このフローチャートは、図２に示すような、８本のパスに展開されたフローチャートに書き換えられる。
【００１９】
さらに、この８本のパスでそれぞれ行われる演算を最後にまとめると、図３Ａのようになり、さらに図３Ａの１つのパスの演算をまとめると、このフローチャートの１サイクルでは図３Ｂに示すように、
Ｒ＝Ｒ＋Ａ＋Ｂ＋Ｄ
Ｒ＝Ｒ＋Ａ＋Ｂ＋Ｅ
Ｒ＝Ｒ＋Ａ＋Ｃ＋Ｄ
Ｒ＝Ｒ＋Ａ＋Ｃ＋Ｅ
Ｒ＝Ｒ＋Ｂ＋Ｄ
Ｒ＝Ｒ＋Ｂ＋Ｅ
Ｒ＝Ｒ＋Ｃ＋Ｄ
Ｒ＝Ｒ＋Ｃ＋Ｅ
・・・(1)
の８通りの演算のうちのいずれかを行うことになる。すなわち、図１８のフローチャートは、この８種類の演算から、分岐条件１、分岐条件２、分岐条件３によって適切な結果を選ぶフローチャートに書き換えられることが理解できる。
【００２０】
このフローチャートを回路化すると、この８通りの全ての演算を行い、８種類の演算結果を出力する候補演算部１００と、その８種の演算結果から適切なひとつの結果を選択するために、図３Ａ、Ｂの７個の分岐にそれぞれ対応したセレクタ２０１〜２０７を組み合わせた選択部２００とによって構成でき、図１の回路によって図１８のフローチャートの演算ができることが理解できる。
【００２１】
このような構成によれば、同じフローチャートを演算する図１９Ａの従来例の回路が演算器を２段あるいは３段通過するのに対し、図１の構成では候補演算部１００の候補演算回路１０１〜１０８として、１段の３入力または４入力演算器ですみ、通過する演算器の個数を減らすことができる。
【００２２】
この回路をさらに高速化するため、図１の回路は図４のような構成をとってもよい。図４に示す回路は、Ｒ以外の項を全て事前に演算しておき、この演算結果にフィードバック値Ｒを加えることで、８通りの演算が行われるように図１の候補演算部１００を候補演算回路１１１〜１１８に組み替えたものである。例えば、候補演算回路１１７では、「Ｒ＋Ｃ＋Ｄ」を演算する場合には、まず「Ｃ＋Ｄ」をあらかじめ演算しておき、この結果に選択部２００からフィードバックされたＲを加え「Ｒ＋（Ｃ＋Ｄ）」を計算するようにしてある。
【００２３】
このようにすれば、フィードバック値Ｒは、２入力加算器１段のみ通過するだけでよくなる。他の候補演算についても同様の書き換えが行われている。このような構成にすることで、図１の場合に比べ、候補演算回路１１１〜１１８として、この回路の動作速度を決めるフィードバック値Ｒが通過する演算器を、４入力演算器または３入力演算器から、より高速な２入力演算器に変更することができるため、回路の動作速度をさらに高めることができる。
【００２４】
また、この回路は図５のような候補演算回路１２１〜１２８の構成を取ってもよい。図５に示す候補演算回路１２１〜１２８は、図４の候補演算部１００の複数の候補演算回路１１１〜１１８のうち、冗長な部分を共通化したものである。例えば、候補演算回路１２１において「Ａ＋Ｂ＋Ｄ」を演算するため、候補演算回路１２５で演算した「Ｂ＋Ｄ」の結果を用い、この結果にＡを加算することで「Ａ＋Ｂ＋Ｄ」を得ている。このように、候補演算回路の一部の演算結果を複数の候補演算回路で共有することで、図４の構成に比べ回路規模を削減することができる。
【００２５】
以上のような処理回路を用いることで、パイプライン演算が不可能な、フィードバックループをもった多段の演算においても、フィードバック値が通過する演算器を１段だけにすることができるため、演算の高速化が実現できる。なお、図５では候補演算回路の一部の演算結果を複数の候補演算回路で共有したが、演算内容によっては、特定の候補演算回路の全部を他の候補演算回路と共有することもできる。この場合、候補演算回路の数を共有する数だけ削減できる。つまり、候補演算回路の数は、アルゴリズムのパスの数がｎ本であるとすると、最大でｎ個となる。
【００２６】
＜実施例２＞
図６は、実施例２の処理回路が実行するアルゴリズムのフローチャートである。変数Ｒに初期値ｉｎｉｔが与えられた後、ループを繰り返すことで変数Ｒの値を書き換えていくアルゴリズムであり、定数αｎ、βｎ、γｎはループを通過するごとに変化し、添え字ｎがループをｎ回目に通過した場合の定数であることを示す。
【００２７】
まず、Ｒに対して初期値ｉｎｉｔが与えられ、分岐１においてＲがγ１以下であるかどうか、分岐判断が行われる。分岐１がＹであれば、ループによって再び分岐１へ戻り、Ｙでなければ演算Ａが行われる。演算Ａによって、Ｒにα１を加えたものを新たなＲとし、分岐２の判断が行われる。分岐２では、Ｒがβ１以下か否かの判断が行われ、Ｙであればループによって分岐１へ戻り、Ｙでなければ演算Ｂによって、Ｒにβ１を加えたものを新たなＲとしたのち、ループにより分岐１へ戻る。ループの２回目になる分岐１では、Ｒとγ２を比較し、以降１回目と同様に分岐判断と演算を行う。
【００２８】
このフローチャートを従来の回路で実現すると、図７のようになる。まず、フィードバックされたＲの値は、初期値入力セレクタ５１を通過した後、演算Ａを行う演算器１６を通るか、直接セレクタ２４に入るかの２つのルートに分かれる。演算Ａを行う演算器１６の出力は２分割され、そのままセレクタ２５に入る経路と、演算Ｂを行う演算器１７を通ってセレクタ２５に入る経路の１つのルートに別れる。セレクタ２５からの出力は、セレクタ２４の入力に接続されている。このように接続されているため、セレクタ２４によって、演算Ａを経由するか、演算Ａを経由せずそのまま出力されるかのいずれかが選択され、また、セレクタ２５によっては、演算Ａを経由した後に、そのまま出力されるか、演算Ｂを経由して出力されるかが選択される。
【００２９】
つまり、セレクタ２４が分岐１を、セレクタ２５が分岐２を担っており、セレクタ２４を分岐１の分岐条件（Ｒ＜γｎ）の演算結果にて分岐条件演算回路４１で駆動し、セレクタ２５を分岐２の分岐条件（Ｒ＜βｎ）の演算結果にて分岐条件演算回路４２で駆動すれば、図６のフローチャートどおりの演算が行われる。ただし、この従来例の回路では、ループ１回分の演算を行うのに、演算Ａ→演算Ｂ→セレクタ２５→セレクタ２４と、最大で演算２段と分岐２段を通過する必要があり、演算処理に時間がかかる問題がある。
【００３０】
これを改善した実施例２の処理回路を図８に示す。この回路は、大きく分けて候補演算部１００、選択部２００、Ｄフリップフロップ３００、分岐条件演算部４００、初期値入力回路５００の５ブロックからなる。
【００３１】
候補演算部１００は、図６の３本のパスにそれぞれ対応する、３個の候補演算回路１３１〜１３３をもつ。候補演算回路１３１は、図６のフローチャートのパス１に対応している。パス１ではＲに何の演算も行わずそのままフィードバックループヘ進むため、候補演算回路１３１は入力されたＲに何の演算も行わないで、そのまま出力する。
【００３２】
候補演算回路１３２は、図６のフローチャートのパス２に対応しており、パス２で通過する演算Ａを行う演算器Ａをもち、αｎとフィードバックループからのＲが入力され、「Ｒ＋αｎ」の演算を行った結果を出力する。
【００３３】
候補演算回路１３３は、図６のフローチャートのパス３に対応しており、パス３では、演算Ａ（Ｒ＝Ｒ＋αｎ）と演算Ｂ（Ｒ＝Ｒ＋βｎ）の２つの演算が行われ、（Ｒ＝Ｒ＋αｎ＋βｎ）という演算結果がフィードバックループヘ戻される。このため、候補演算回路１３３は、フィードバック値Ｒとαｎ、βｎが入力され、「Ｒ＋αｎ＋βｎ」を出力するようになっている。この演算を行うにあたっては、まずはじめに「αｎ＋βｎ」の演算を行い、その結果とフィードバック値Ｒを加算し、「Ｒ＋αｎ＋βｎ」を得ることで、フィードバック値Ｒが１段の２入力加算器のみを通過する構成としている。
【００３４】
分岐条件演算部４００は、図６の２つの分岐に対応した、２個の分岐条件演算回路４０１，４０２をもつ。分岐条件演算回路４０１は、図６のフローチャートの分岐１の分岐条件であるＲ＜γｎの真偽を判断するもので、大小比較器にＲとγｎが入力されその判定結果が出力される。
【００３５】
分岐条件演算回路４０２は、図６のフローチャートの分岐２の分岐条件であるＲ＜βｎの真偽を判断するものである。ただし、図６のフローチャートの上部から分岐２に至るまでには演算Ａを経ているため、フィードバック値Ｒの値にαｎが加えられていることに注意が必要である。すなわち、分岐条件演算回路４０２が行うべき比較は「（Ｒ＋αｎ）＜βｎ」となる。この比較は、「Ｒ＜βｎ−αｎ」と等価であるため、分岐条件演算回路４０２は、「Ｒ＜βｎ−αｎ」の真偽の結果を出力するように構成されている。さらに、候補演算回路１３３と同様、フィードバック値Ｒが通過する演算器の段数数を減らすため、あらかじめ「βｎ一αｎ」を演算しておき、これとＲを大小比較器で比較することによって、Ｒに対する加減算を行う必要を省き、Ｒが大小比較器を１度通過するだけで結果が出力されるような構成としている。
【００３６】
選択部２００は、分岐条件演算部４００からの判断結果に基づき、候補演算部１００からの３本の出力から適切なものを１つ選ぶように、２個のセレクタ２１１とセレクタ２１２が接続された構成となっている。
【００３７】
セレクタ２１１は、図６のフローチャートの分岐１に相当し、Ｒの値をそのままフィードバックするか分岐２へ行くかの選択を行うため、候補演算回路１３１の出力（Ｒの値そのまま）とセレクタ２１２の出力が接続されており、分岐条件演算回路４０１の出力によって切り替えられる。
【００３８】
セレクタ２１２は、フローチャートの分岐２に相当し、候補演算回路１３２から出力される「Ｒ＋αｎ」と候補演算回路１３３から出力される「Ｒ＋αｎ＋βｎ」とが接続されており、このどちらかを選択した結果をセレクタ２１１へ出力する。セレクタ２１２は、分岐条件演算回路４０２の出力によって切り替えられる。
【００３９】
初期値入力回路５００は、Ｄフリップフロップ３００により１クロック遅延させたフィードバック値と初期値ｉｎｉｔとの切換えを行う開始開始信号が入力されている。開始信号がアクティブになると、初期値入力回路５００は初期値ｉｎｉｔを選択し、初期値ｉｎｉｔがＲとして候補演算部１００に入力され、計算がスタートする。計算がスタートしてからは、開始信号を非アクティブにし、フィードバック値が候補演算部１００に入力されるようにして、ループ演算を繰り返し行う。
【００４０】
このような構成により、図６のフローチャートに従った演算を行う回路が実現できる。理解しやすくするために、図６のフローチャートを図９のように書き換え、全ての演算をパスの最後に持ってきたものを考えれば、図８はこれを回路化したものと考えることもできる。
【００４１】
図８のような構成にすることにより、図７では、フィードドバックされたＲの値が最大２段の演算器を通らねばならなかったものが、１段の演算器しか通らないように構成でき、回路の動作速度を決めるＲのフィードバックループの演算段数を減らすことができ、高速演算を実現できるようになる。
【００４２】
＜実施例３＞
実施例３も、実施例２で用いた図６のフローチャートで示したアルゴリズムを実行する処理回路である。このアルゴリズムをさらに高速に演算するため、ループ２回分の処理を１クロックで行う回路を考える。
【００４３】
図６のフローチャートのループを２回通過した場合を考えると、フローチャートは図１０のように、図６からループを除いた部分を、ループの１順目、２順目に対応するように２段縦積みにし、２順目の最後から１順日の分岐１の手前ヘループする形に展開できる。図１０のように展開した場合、１順目では奇数番の演算が、２順目では偶数番の演算が行われるため、フローチャート中のγｎを１順目ではγ２ｎ−１に、２順目ではγ２ｎに変更しておく（αｎ、βｎについても同様）。
【００４４】
この図１０のフローチャートを、実施例１で行ったのと同様な手法でさらに展開する。図１０のフローチャートの１順目にあたる部分には３本のパスがあり、「何もしない、Ｒ＝Ｒ＋α２ｎ−１、Ｒ＝Ｒ＋α２ｎ−１＋β２ｎ−１」の３種類のうちいずれかが選ばれる。図１０のフローチャートの２順目も、「何もしない、Ｒ＝Ｒ＋α２ｎ、Ｒ＝Ｒ＋α２ｎ＋β２ｎ」の３種類のうちいずれかが選ばれる。すなわち、図１０のフローチャートが取りうる全てのパスは、これら３種類の選択肢の２つの組み合わせで、３×３の９通りとなり、この９通り全てを展開して書き直したフローチャートが図１１である。
【００４５】
さらに、この図１１のフローチャートの演算と分岐を分離し、演算をパスの最後にまとめて書くと、フローチャートは図１２のように、選択のみを行う選択部と、演算のみを行う候補演算部の２つに分けて書くことができ、図１１のフローチャートの９本のパスそれぞれにおいて、
Ｒ＝Ｒ
Ｒ＝Ｒ＋α２ｎ
Ｒ＝Ｒ＋α２ｎ＋β２ｎ
Ｒ＝Ｒ＋α２ｎ−１
Ｒ＝Ｒ＋α２ｎ−１＋α２ｎ
Ｒ＝Ｒ＋α２ｎ−１＋α２ｎ＋β２ｎ
Ｒ＝Ｒ＋α２ｎ−１＋β２ｎ−１
Ｒ＝Ｒ＋α２ｎ−１＋α２ｎ＋β２ｎ−１
Ｒ＝Ｒ＋α２ｎ−１＋α２ｎ＋β２ｎ−１＋β２ｎ
・・・(2)
の演算が行われることが分かる。
【００４６】
すなわち、これら９種類の演算結果から、分岐１−１〜分岐２ｃ−２で表される８種類の分岐条件を組み合わせ適切なものを１つ選び出せば、図６のフローチャートのループ２回分の計算を行った結果が得られる。
【００４７】
このとき、分岐条件にもＲが用いられているため、図１２のフローチャートにおいてはパスの途中で通過する演算を分岐条件に反映させ、分岐条件を書き換えてある点に注意が必要である。例えば、分岐１−２では、図１１において途中で演算Ａ（Ｒ＝Ｒ＋α２ｎ−１）を通過した後に行われる判断があるため、分岐２（Ｒ＜β２ｎ−１）のＲをＲ＋α２ｎ−１ に書き換え、「（Ｒ＋α２ｎ−１）＜β２ｎ−１」と改めている。他の分岐についても、同様の書き換えを行っている。
【００４８】
この図１２のフローチャートを回路化すると、図１３のようになる。この回路も、実施例２の図８の回路と同様、大きく分けて候補演算部１００、選択部２００、Ｄフリップフロップ３００、分岐条件演算部４００、初期値入力回路５００の５ブロックからなる。
【００４９】
候補演算部１００は、図１３中の９種類の演算に対応した９個の演算回路１４１〜１４９をもち、それぞれの演算回路から１本ずつの計９本の演算結果が出力される。ただし、候補演算部１４１〜１４９の出力のうち、図中で最も上の演算回路１４１から出力される１本は、Ｒ＝Ｒの演算に対応しており、何も演算を行う必要がないため、演算回路は図示せず直結で表現されている。
【００５０】
選択部２００は、図１２のフローチャートの選択部に含まれる８個の分岐に対応した、８個のセレクタ２２１〜２２８をもつ。分岐条件演算部４００は、それぞれのセレクタの分岐条件に対応した大小比較器からなる８個の分岐条件演算回路４１１〜４１８をもち、それぞれの分岐条件演算回路から出力される８本の出力が選択部２００の８個のセレクタ２２１〜２２８にそれぞれ接続されており、この信号によってセレクタ２２１〜２２８が切換えられ適切なパスを選択するようになっている。
【００５１】
初期値入力回路５００は、Ｄフリップフロップ３００により１クロック遅延させたフィードバック値と初期値ｉｎｉｔとの切換えを行う開始開始信号が入力されている。開始信号がアクティブになると、初期値入力回路５００は初期値ｉｎｉｔを選択し、初期値ｉｎｉｔが候補演算部１００に入力され、計算がスタートする。計算がスタートしてからは、開始信号を非アクティブにし、フィードバック値が候補演算部１００に入力されるようにして、ループ演算を繰り返し行う。
【００５２】
以上のように回路を構成することで、１クロックでループ２回分の演算が可能となり、１クロックで１ループを実行する回路の２倍の処理能力が可能となる。
【００５３】
図１３の回路をさらに高速化するために、候補演算部１００と分岐条件演算部４００を図１４のようにしてもよい。図１４の回路の動作原理は図１３と全く同じであり、候補演算部１００と分岐条件演算部４００の内部構成のみが異なるので、この２点の差異をもとに図１４の回路について説明する。
【００５４】
候補演算部１００は、図１２のフローチャートの９本のパスに対応する９個の候補演算回路１５１〜１５９からなるが、これら候補演算回路１５１〜１５９のうち３入力以上のもの（項が３個以上あるもの）は、Ｒ以外の全ての項をあらかじめ加算しておく事前演算器（左側）と、その事前演算器の演算結果にＲを加える加算器（右側）の２段構成とし、クリティカルパスとなるフィードバック値Ｒが通過する演算器を、２入力演算器を１個だけに抑える。例えば、「Ｒ＝Ｒ＋α２ｎ＋β２ｎ」を演算する候補演算回路１５３は、まず「α２ｎ＋β２ｎ」を事前演算器において演算し、この演算結果とＲを加えることで「Ｒ＋α２ｎ＋β２ｎ」を演算する構成とする。
【００５５】
分岐条件演算部４００の分岐条件演算回路４２１〜４２８も同様に、分岐条件をＲとそれ以外の値の演算結果との比較に書き直し、それ以外の値の演算を事前演算器（左側）において演算しておき、これとＲを比較器（右側）で比較するようにする。例えば、「Ｒ＋α２ｎ−１＜β２ｎ−１の条件判断を行う分岐条件演算回路４２７では、この比較式を「Ｒ＜β２ｎ−１−α２ｎ−１」と書き換え、事前演算器（左側）で「β２ｎ−１−α２ｎ−１」を計算しておき、この計算結果とＲとを比較器（右側）で比較した結果を出力とする。これによって、フィードドバック値Ｒが通過するのは比較器１段だけに抑えることができる。
【００５６】
このような構成にすることで、クリティカルパスであるフィードバック値Ｒの演算が、２ループ分を演算するにも関わらず、比較器または加算器を１段のみしか通過しない構成となり、クロックのさらなる高速化が可能となり、処理速度の大幅な向上が図れる。
【００５７】
なお、パス数をｎ、分岐数をｍ、アルゴリズムの繰り返し単位をｋとすれば、実施例３ではｎ＝３、ｍ＝２、ｋ＝２となる。そして、候補演算部１００の出力数はｎｋ＝９本となり、選択部２００のセレクタの段数はｍ×ｋ＝４となり、分岐演算部４００からの出力数はセレクタの個数分と同じで８本となる。さらに、これを発展させたときは、選択部２００の段数は共通部分によりｍ×ｋよりも少なくなる場合があり得るが、最大でｍ×ｋ段となる。また、セレクタの個数は、最大で（１＋ｎ＋ｎ２＋ｎ３＋・・・＋ｎｋ−１）×ｍ個（ｋ≧２）となる。
【図面の簡単な説明】
【００５８】
【図１】本発明の実施例１の処理回路のブロック図である。
【図２】図１８のフローチャートを展開したフローチャートである。
【図３Ａ】図１８のフローチャートを展開し、演算と分岐に分離したフローチャートである。
【図３Ｂ】図１８のフローチャートを展開し、演算と分岐に分離したフローチャートである。
【図４】本発明の実施例１において、フィードバック演算を候補演算回路の最後に行うように書き換えた処理回路のブロック図である。
【図５】本発明の実施例１において、一部回路を共有化した処理回路のブロック図である。
【図６】本発明の実施例２のフローチャートである。
【図７】図６のフローチャートを従来手法で回路化した処理回路のブロック図である。
【図８】本発明の実施例２の処理回路のブロック図である。
【図９】図６のフローチャートを書き換えたフローチャートである。
【図１０】本発明の実施例３のフローチャートである。
【図１１】図１０のフローチャートを書き換えたフローチャートである。
【図１２】図１０のフローチャートを展開し、演算と分岐に分離したフローチャートである。
【図１３】本発明の実施例３の処理回路のブロック図である。
【図１４】本発明の実施例３において、フィードバック演算を候補演算回路の最後に行うように書き換えた処理回路のブロック図である。
【図１５】ある演算のフローチャートである。
【図１６】図１５のフローチャートを回路化した従来の処理回路のブロック図である。
【図１７】図１５のフローチャートをパイプライン回路化した従来の処理回路のブロック図である。
【図１８】フィードバックループをもつある演算のフローチャートである。
【図１９Ａ】図１８のフローチャートを回路化した従来例の処理回路のブロック図である。
【図１９Ｂ】図１８のフローチャートを回路化した従来例の処理回路のブロック図である。
【符号の説明】
【００５９】
１１〜１７：演算器
２１〜２５：セレクタ
３１〜３４：Ｄフリップフロップ
４１，４２：分岐条件演算回路
５１：セレクタ
１００：候補演算部、１０１〜１０８，１１１〜１１８，１２１〜１２８１３１〜１３３，１４１〜１４９，１５１〜１５９：候補演算回路
２００：選択部、２０１〜２０７，２１１，２１２，２２１〜２２８：セレクタ
３００：Ｄフリップフロップ
４００：分岐条件演算部、４０１〜４０８，４１１〜４１８，４２１〜４２８：分岐条件演算回路
５００：初期値入力回路、５０１：セレクタ
【図１】
0004958224.tif 000002
【図２】
0004958224.tif 000003
【図３Ａ】
0004958224.tif 000004
【図３Ｂ】
0004958224.tif 000005
【図４】
0004958224.tif 000006
【図５】
0004958224.tif 000007
【図６】
0004958224.tif 000008
【図７】
0004958224.tif 000009
【図８】
0004958224.tif 000010
【図９】
0004958224.tif 000011
【図１０】
0004958224.tif 000012
【図１１】
0004958224.tif 000013
【図１２】
0004958224.tif 000014
【図１３】
0004958224.tif 000015
【図１４】
0004958224.tif 000016
【図１５】
0004958224.tif 000017
【図１６】
0004958224.tif 000018
【図１７】
0004958224.tif 000019
【図１８】
0004958224.tif 000020
【図１９Ａ】
0004958224.tif 000021
【図１９Ｂ】
0004958224.tif 000022