(57)【要約】【課題】パイプライン演算器の構成と演算要素間の関係がある特定のものであるとき、演算要素を前段のパイプラインステージに移設することにより、演算機能の等価性を保ちつつ動作速度を向上する。【解決手段】前段のパイプラインステージにある演算要素の入力部分に後段のパイプラインステージから演算要素を移設するときに、前記入力部分の入力数に応じて移設対象を複製し、また後段のパイプラインステージ数が複数あるときには、移設先演算要素を複製してパイプライン構造の組み替えを行い機能の等価性を確保しつつ高速化を果たす。【選択図】図１
2006113989.tif 000002
【特許請求の範囲】
【請求項１】
第一のパイプラインステージの出力に第二のパイプラインステージが接続し前記第二のパイプラインステージの出力に１個以上の第三のパイプラインステージが接続し、前記第二のパイプラインステージは第一の演算要素ｆ１ｉと第二の演算要素ｆ２ｉと第三の演算要素ｆ３ｉを有しかつ前記第一の演算要素ｆ１ｉは前記第二のパイプラインステージの入力部分に位置し前記第三の演算要素ｆ３ｉは前記第二のパイプラインステージの出力部分に位置しかつ前記第一の演算要素ｆ１ｉの出力は前記第二の演算要素ｆ２ｉの入力および前記第三の演算要素ｆ３ｉの第二の入力に接続しさらに前記第二の演算要素ｆ２ｉの出力は前記第三の演算要素ｆ３ｉの第一の入力に接続し、さらに前記第一のパイプラインステージは出力部分に演算要素ｆ３ｈを有しまた前記第三のパイプラインステージの１個は入力部分に演算要素ｆ１ｊを有し前記第三のパイプラインステージの２個目以降は入力部分に演算要素ｆ１ｋを有する論理的機能のパイプライン演算器であって、
このとき前記第二のパイプラインステージの第一の演算要素ｆ１ｉと前記第一のパイプラインステージの演算要素ｆ３ｈの第二の入力側に関して演算順序の入れ替えを行っても機能的に等価性が保たれ、かつ前記第三のパイプラインステージにおける演算要素ｆ１ｊまたは演算要素ｆ１ｋと前記第二のパイプラインステージの第三の演算要素ｆ３ｉの第二の入力側に関して演算順序の入れ替えを行っても機能的に等価性が保たれる性質を有するとき、
前記第二のパイプラインステージの第一の演算要素ｆ１ｉを前記第一のパイプラインステージの演算要素ｆ３ｈの第二の入力部分に移設し、かつ前記第二のパイプラインステージの第三の演算要素ｆ３ｉを複製して前記第三のパイプラインステージの個数分だけ用意し、かつ前記第三のパイプラインステージの１個における演算要素ｆ１ｊを前記第二のパイプラインステージの第三の演算要素ｆ３ｉにおける第二の入力部分に移設し、かつ前記第三のパイプラインステージの２個目以降における演算要素ｆ１ｋを前記第二のパイプラインステージの第三の演算要素ｆ３ｉの複製における第二の入力部分に移設し、以上により得られる構成を持つものであって、
これらにより演算要素の移設前の論理的機能に対する等価性を保ちつつ、パイプラインステージにおける信号経路長を演算要素３段から演算要素２段に短縮して動作速度の向上を図り、とくにパイプラインステージの出力部分に位置する演算要素の伝播遅延が他の演算要素に比べて十分小さいときには、パイプラインステージの信号伝播遅延を演算要素の移設前に比べて半分近くにまで短縮し動作速度を向上したパイプライン演算器。
【請求項２】
「請求項１」記載のパイプライン演算器の演算器移設前の構成に対して、第二のパイプラインステージの入力部分に第四の演算要素ｆ４ｉを追加しかつ前記演算要素ｆ４ｉは演算順序の入れ替えに関して演算要素ｆ１ｉと同等の性質を有し、また前記第二のパイプラインステージにおいて前記第四の演算要素ｆ４ｉの出力は第二の演算要素ｆ２ｉに新たに追加した第二の入力に接続し、また同時に前記第四の演算要素ｆ４ｉの出力は前記第三の演算要素ｆ３ｉに新たに追加した第三の入力にも接続し、また第一のパイプラインステージの演算要素ｆ３ｈには新たに第三の入力を追加し、以上により得られる論理的機能を有するパイプライン演算器であって、
演算要素の移設はすべて「請求項１」の記載のとおりとし、さらに加えて前記第二のパイプラインステージの第一の演算要素ｆ１ｉを第一のパイプラインステージに移設するにあたっては前記第一の演算要素ｆ１ｉの複製を設け、前記ｆ１ｉの複製を前記第一のパイプラインステージの前記演算要素ｆ３ｈの第三の入力部分に配置し、また第三のパイプラインステージの１個における演算要素ｆ１ｊを第二のパイプラインステージに移設するにあたっては前記演算要素ｆ１ｊの複製を設け、前記ｆ１ｊの複製を前記第二のパイプラインステージの前記第三の演算要素ｆ３ｉの第三の入力部分に配置し、また第三のパイプラインステージの２個目以降における演算要素ｆ１ｋを第二のパイプラインステージに移設するにあたっては前記ｆ１ｋの複製を設け、前記ｆ１ｋの複製を前記第二のパイプラインステージの第三の演算要素ｆ３ｉの複製における第三の入力部分に配置し、以上によって得られる構成を持つものであって、
これらによって演算要素の移設を行う前の論理的機能に対する等価性を保ちつつ、パイプラインステージにおける信号経路長を演算要素３段から演算要素２段に短縮して動作速度の向上を図り、とくにパイプラインステージの出力部分に位置する演算要素の伝播遅延が他の演算要素に比べて十分小さいときには、パイプラインステージの信号伝播遅延を演算要素の移設前に比べて半分近くにまで短縮し動作速度を向上したパイプライン演算器。
【請求項３】
第二のパイプラインステージの第一の演算要素ｆ１ｉと第四の演算要素ｆ４ｉと第三のパイプラインステージの演算要素ｆ１ｊ、ｆ１ｋが加算器であり、第二のパイプラインステージの第二の演算要素ｆ２ｉが比較器であり、第二のパイプラインステージの第三の演算要素ｆ３ｉと第一のパイプラインステージの演算要素ｆ３ｈがマルチプレクサである「請求項２」記載のパイプライン演算器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路におけるデジタル演算回路の設計技術に属し、パイプライン構造を持つ演算回路の高速化手段に関する。
【背景技術】
【０００２】
半導体集積回路におけるデジタル演算回路のうちで、パイプライン構造を持ちかついくつかの種類の演算要素が相互接続して繰り返し構造をとるものがある。図４はその事例であり、第一のパイプラインステージ１の出力にパイプラインレジスタ５を介して第二のパイプラインステージ２が接続し、さらに第二のパイプラインステージ２の出力にパイプラインレジスタ５を介して第三のパイプラインステージ３、４が接続している。図４は第三のパイプラインステージが２個以上ある事例であり、パイプラインステージ４をもって２個目以降を代表させている。ここで第二のパイプラインステージ２は、第一の演算要素ｆ１ｉ  ２１と第二の演算要素ｆ２ｉ  ２２と第三の演算要素ｆ３ｉ  ２３を有しており、第一の演算要素ｆ１ｉ  ２１は第二のパイプラインステージ２の入力部分に位置し、第三の演算要素ｆ３ｉ  ２３は第二のパイプラインステージ２の出力部分に位置している。また第一の演算要素ｆ１ｉ  ２１の出力は、第二の演算要素ｆ２ｉ  ２２の入力および第三の演算要素ｆ３ｉ  ２３の第二の入力に接続しており、さらに第二の演算要素ｆ２ｉ  ２２の出力は第三の演算要素ｆ３ｉ  ２３の第一の入力に接続している。この事例では、第二のパイプラインステージ２における演算要素の相互接続構成が基本構成となって、同様の構成が第一のパイプラインステージ１にも第三のパイプラインステージ３および４の中にも現れている。
【０００３】
このような回路構成のパイプライン演算器では、パイプラインステージ１個における最長信号経路は、演算要素２１と演算要素２２と演算要素２３の直列接続経路であり、信号経路長は演算要素３段である。ここで演算要素ｆ１ｉ  ２１の信号伝搬遅延をｄｆ１ｉ、演算要素ｆ２ｉ  ２２の信号伝搬遅延をｄｆ２ｉ、演算要素ｆ３ｉ  ２３の信号伝搬遅延をｄｆ３ｉとすると、パイプラインステージ２の信号伝搬遅延は  ｄｆ１ｉ＋ｄｆ２ｉ＋ｄｆ３ｉで表され、他のパイプラインステージも同様の回路構成を持つならば、図４のパイプライン演算器の動作クロック周期は、前記ｄｆ１ｉ＋ｄｆ２ｉ＋ｄｆ３ｉの値に近いものとなる。正確には、それにパイプラインレジスタ５の遅延時間を加えたものとなる。このような構成のパイプライン演算器を高速化する一般的な方法は、最長信号経路上にある演算要素各々の内部の設計を改良してそれら各々の信号伝搬遅延を短縮するしかなかった。
【０００４】
図５は、図４の回路構成を内部に含んでさらに演算要素が追加され接続構造が少し複雑になったパイプライン演算器の事例である。図５は図４と同様に、第一のパイプラインステージ１、第二のパイプラインステージ２、第三のパイプラインステージ３
、４からなるパイプライン演算器であり、図４との違いは、パイプラインステージ２を用いて説明すると、パイプラインステージの入力部分に第四の演算要素ｆ４ｉ  ２４が追加され、それにともなって演算要素ｆ２ｉ  ２２および演算要素ｆ３ｉ  ２３の各々に入力線が各１本追加され、演算要素ｆ４ｉ  ２４の出力が接続していることである。
図５の事例においても、パイプラインステージ２における演算要素の相互接続構成が基本構成となって、同様の構成が第一のパイプラインステージ１にも第三のパイプラインステージ３および４の中にも現れている。またパイプラインステージ１個における信号経路長は、図４の事例と同様に演算要素３段である。また追加された演算要素ｆ４ｉ  ２４の信号伝搬遅延が演算要素ｆ１ｉ  ２１の信号伝搬遅延と同じならば、図５のパイプライン演算器の動作クロック周期は図４の場合と同じになる。図５のパイプライン演算器を高速化する一般的な方法は、図４の場合と同じく最長信号経路上にある演算要素各々の内部の設計を改良してそれら各々の信号伝搬遅延を短縮するしかなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
図４および図５に示すような論理的機能を有するパイプライン演算器で演算要素どうしの間にある特定の性質がある場合に、パイプライン演算器の論理的機能を保存しつつ、演算要素の内部にはいっさい手を加えずに、パイプラインステージ１個における信号経路長を短縮する新たな手段を考案してパイプライン演算器の高速化を図る。
【課題を解決するための手段】
【０００６】
図４のパイプライン演算器において、第二のパイプラインステージ２の第一の演算要素ｆ１ｉ  ２１と第一のパイプラインステージ１の演算要素ｆ３ｈ  １３の第二の入力側すなわち信号Ｆ１Ｏｈが入力される側に関して、演算順序の入れ替えを行っても機能的に等価性が保たれる場合を考える。これは論理関数で表現するならば、  ｆ１ｉ（ｆ３ｈ（ｆ２ｈ，Ｆ１Ｏｈ），Ｅ１ｉ）＝ｆ３ｈ（ｆ２ｈ，ｆ１ｉ（Ｆ１Ｏｈ，Ｅ１ｉ）  ）  が成立するという意味である。また同時に、第三のパイプラインステージ３における演算要素ｆ１ｊ  ３１または演算要素ｆ１ｋ  ４１と、第二のパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３の第二の入力側すなわち信号Ｆ１Ｏｉが入力される側に関しても、演算順序の入れ替えを行っても機能的に等価性が保たれる性質があるものとする。
このとき、第二のパイプラインステージの第一の演算要素ｆ１ｉを第一のパイプラインステージの演算要素ｆ３ｈの第二の入力部分に移設する。また第二のパイプラインステージの第三の演算要素ｆ３ｉを複製して第三のパイプラインステージの個数分だけ用意する。そして第三のパイプラインステージの１個における演算要素ｆ１ｊを第二のパイプラインステージの第三の演算要素ｆ３ｉにおける第二の入力部分に移設し、さらに第三のパイプラインステージの２個目以降における演算要素ｆ１ｋを第二のパイプラインステージの第三の演算要素ｆ３ｉの複製における第二の入力部分に移設する。これらによって得られるパイプライン演算器は、演算要素の移設を行う前の論理的機能に対する等価性を保ちつつ、パイプラインステージにおける信号経路長を演算要素３段から演算要素２段に短縮したものとなり、動作速度が向上する。
【０００７】
図５のパイプライン演算器においても、図４のパイプライン演算器の場合と同様に、演算順序の入れ替えを行っても機能的に等価性が保たれる場合を考える。
このとき、第二のパイプラインステージの第一の演算要素ｆ１ｉを移設するにあって複製を設け、もとの演算要素ｆ１ｉを第一のパイプラインステージの演算要素ｆ３ｈの第二の入力部分に移設し、演算要素ｆ１ｉの複製を演算要素ｆ３ｈの第三の入力部分に移設する。また第二のパイプラインステージの第三の演算要素ｆ３ｉを複製して第三のパイプラインステージの個数分だけ用意する。そして第三のパイプラインステージの１個における演算要素ｆ１ｊを第二のパイプラインステージに移設するにあたっては複製を設け、もとの演算要素ｆ１ｊを演算要素ｆ３ｉにおける第二の入力部分に移設し、演算要素ｆ１ｊの複製を演算要素ｆ３ｉの第三の入力部分に移設する。さらに第三のパイプラインステージの２個目以降における演算要素ｆ１ｋを第二のパイプラインステージに移設するにあたっても複製を設け、それらを第三の演算要素ｆ３ｉの複製における第二および第三の入力部分に移設する。これらによって得られるパイプライン演算器は、演算要素の移設を行う前の論理的機能に対する等価性を保ちつつ、パイプラインステージにおける信号経路長を演算要素３段から演算要素２段に短縮したものとなり、動作速度が向上する。
【発明の効果】
【０００８】
本発明によれば、パイプライン演算器がある特定の機能および演算要素相互間の関係を有するときに、動作速度の速いパイプライン演算器が実現でき、最も良い場合ではパイプラインステージの遅延時間を約半分まで短縮した高速のパイプライン演算器が得られる。
【発明を実施するための最良の形態】
【０００９】
本発明の実施の形態について、以下図を用いながら説明する。図１は、図４に示すパイプライン演算器と論理的機能が等しく、本発明によって高速化したパイプライン演算器の実施の形態を示すものであり、特許請求の範囲の請求項1に対応した実施の形態となっている。
はじめに図４のパイプライン演算器の構成について述べる。第一のパイプラインステージ１の出力に第二のパイプラインステージ２が接続し、第二のパイプラインステージ２の出力に１個以上の第三のパイプラインステージが接続する。ここでは第三のパイプラインステージの１個目を３とし、第三のパイプラインステージの２個目以降を代表するものを４とする。第二のパイプラインステージ２は第一の演算要素ｆ１ｉ  ２１と第二の演算要素ｆ２ｉ  ２２と第三の演算要素ｆ３ｉ  ２３を有する。第一の演算要素ｆ１ｉ  ２１は第二のパイプラインステージ２の入力部分に位置し、第三の演算要素ｆ３ｉ  ２３は第二のパイプラインステージ２の出力部分に位置する。また第一の演算要素ｆ１ｉ  ２１の出力は第二の演算要素ｆ２ｉ  ２２の入力および第三の演算要素ｆ３ｉ  ２３の２個ある入力の一方（これを第二の入力と呼ぶ）に接続し、さらに第二の演算要素ｆ２ｉ  ２２の出力は第三の演算要素ｆ３ｉ  ２３のもう一方の入力（これを第一の入力と呼ぶ）に接続する。さらに第一のパイプラインステージ１は出力部分に演算要素ｆ３ｈ  １３を有する。また第三のパイプラインステージ３は入力部分に演算要素ｆ１ｊを有し、第三のパイプラインステージ４は入力部分に演算要素ｆ１ｋを有するような論理的機能のパイプライン演算器である。
【００１０】
このとき、第二のパイプラインステージ２の第一の演算要素ｆ１ｉ  ２１と第一のパイプラインステージ１の演算要素ｆ３ｈ  １３の第二の入力信号側すなわちＦ１Ｏｈが入力される側に関して、演算順序の入れ替えを行っても機能的に等価性が保たれる場合を考える。これは論理関数で表現するならば、  ｆ１ｉ（ｆ３ｈ（ｆ２ｈ，Ｆ１Ｏｈ），Ｅ１ｉ）＝ｆ３ｈ（ｆ２ｈ，ｆ１ｉ（Ｆ１Ｏｈ，Ｅ１ｉ）  ）  が成立するという意味である。また同時に、第三のパイプラインステージにおける演算要素ｆ１ｊ  ３１または演算要素ｆ１ｋ  ４１と、第二のパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３の第二の入力側すなわち信号Ｆ１Ｏｉが入力される側に関しても、演算順序の入れ替えを行っても機能的に等価性が保たれる性質があるものとする。
【００１１】
このとき、図４に示したパイプライン演算器の演算要素を以下にしたがって移設することで得られる回路構成が図１に示す実施の形態である。
すなわち第二のパイプラインステージ２の第一の演算要素ｆ１ｉ  ２１を第一のパイプラインステージ１の演算要素ｆ３ｈ  １３の第二の入力部分に移設する。これが図１におけるｆ１ｉ  ２１である。また第二のパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３を複製して第三のパイプラインステージの個数分だけ用意する。これが図１におけるｆ３ｉ  ２３とｆ３ｉ  ２３１である。後者が複製したものである。そして第三のパイプラインステージ３における演算要素ｆ１ｊ  ３１を第二のパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３における第二の入力側すなわちＦ１Ｏｉが接続する側に移設する。さらに第三のパイプラインステージ４における演算要素ｆ１ｋ  ４１を第二のパイプラインステージ２の第三の演算要素の複製ｆ３ｉ  ２３１における第二の入力部分に移設する。これらの演算要素の番号は図１におけるものである。これらによって得られるパイプライン演算器は、演算要素の移設を行う前の論理的機能に対する等価性を保ちつつ、パイプラインステージにおける信号経路長を演算要素３段から演算要素２段に短縮したものとなっており、動作速度が向上する。
【００１２】
より厳密な議論をするならば、図４に図示されているパイプラインレジスタ５の各々は、図１ではパイプラインステージ１つ分だけ左側（信号経路の上流側）に移動された意味合いを持つ。別の言い方をすると、例えば図１のパイプラインステージ２では、演算要素２２，２３，２３１の３個は本来のクロックタイミングより１周期遅れて動作しているが、パイプラインステージ３から移動してきた演算要素３１、４１は本来のクロックタイミングで動作しており、パイプラインステージ２の出力でパイプラインステージ３に供給される信号のＦ１Ｏｊ、Ｆ１Ｏｋは、図４のパイプラインステージ３の中で生成されるのと同じタイミングで生成されている。すなわち図１の実施の形態は、本当は演算要素２１を前段のパイプラインステージに移設したのではなく、演算要素２１は移設せずに演算要素２２、２３を後段のパイプラインステージに移動させ、２サイクルかけて一連の演算をおこなうようにパイプラインを組み替えたとも言えるものである。図４ではパイプラインレジスタを通過するのは次のパイプラインステージへの入力信号であるＩ１ｉ等であるが、図１の構成では信号Ｆ１Ｏｉ等であり、それらは図４では演算要素ｆ１ｉ  ２１等の出力信号であったものである。このように動作タイミングは図４と図１の構成で変化しているが、演算内容は両者で機能的に等価なものとなっている。
【００１３】
図１において、演算要素ｆ１ｉ  ２１の信号伝搬遅延をｄｆ１ｉ、演算要素ｆ２ｉ  ２２の信号伝搬遅延をｄｆ２ｉ、演算要素ｆ３ｉ  ２３の信号伝搬遅延をｄｆ３ｉ、演算要素ｆ１ｊ  ３１の信号伝搬遅延をｄｆ１ｊ、演算要素ｆ１ｋ  ４１の信号伝搬遅延をｄｆ１ｋとすると、パイプラインステージ２の信号伝搬遅延は  ｍａｘ（ｄｆ２ｉ，ｄｆ１ｊ，ｄｆ１ｋ）＋ｄｆ３ｉで表される（ｍａｘは最大値を選ぶ関数）。このときにｄｆ１ｉ，ｄｆ２ｉ，ｄｆ１ｊ，ｄｆ１ｋが同程度に大きく一方ｄｆ３ｉが十分に小さいならば、パイプラインステージ２の遅延は近似的にｄｆ２ｉとなる。一方図４におけるパイプラインステージの伝搬遅延はｄｆ１ｉ＋ｄｆ２ｉ＋ｄｆ３ｉでありこれは近似的に２×ｄｆ２ｉなので、演算要素が上記のような遅延の大小関係を持つ場合には、図１の実施の形態により、図４の構成に比べて２倍近い速度向上が得られることになる。
【００１４】
つぎに、特許請求の範囲の請求項２に対応した実施の形態について説明する。図２は、図５に示すパイプライン演算器と論理的機能が等しく、本発明によって高速化したパイプライン演算器の実施の形態を示すものである。
はじめに図５のパイプライン演算器の構成について述べる。第一のパイプラインステージ１の出力に第二のパイプラインステージ２が接続し、第二のパイプラインステージ２の出力に１個以上の第三のパイプラインステージが接続する。ここでは第三のパイプラインステージの１個目を３とし、第三のパイプラインステージの２個目以降を代表するものを４とする。第二のパイプラインステージ２は第一の演算要素ｆ１ｉ  ２１と第二の演算要素ｆ２ｉ  ２２と第三の演算要素ｆ３ｉ  ２３と第四の演算要素ｆ４ｉ  ２４を有する。第一の演算要素ｆ１ｉ  ２１および第四の演算要素ｆ４ｉ  ２４は第二のパイプラインステージ２の入力部分に位置し、第三の演算要素ｆ３ｉ  ２３は第二のパイプラインステージ２の出力部分に位置する。また第一の演算要素ｆ１ｉ  ２１の出力は第二の演算要素ｆ２ｉ  ２２の第一の入力および第三の演算要素ｆ３ｉ  ２３の第二の入力に接続し、また第四の演算要素ｆ４ｉ  ２４の出力は第二の演算要素ｆ２ｉ  ２２の第二の入力および第三の演算要素ｆ３ｉ  ２３の第三の入力に接続し、さらに第二の演算要素ｆ２ｉ  ２２の出力は第三の演算要素ｆ３ｉ  ２３の第一の入力に接続する。さらに第一のパイプラインステージ１は出力部分に演算要素ｆ３ｈ  １３を有し、また演算要素ｆ３ｈは第一から第三の入力を有する。また第三のパイプラインステージ３は入力部分に演算要素ｆ１ｊを有し、第三のパイプラインステージ４は入力部分に演算要素ｆ１ｋを有するような論理的機能のパイプライン演算器である。
【００１５】
このとき、第二のパイプラインステージ２の第一の演算要素ｆ１ｉ  ２１と、第一のパイプラインステージ１の演算要素ｆ３ｈ  １３の第二および第三の入力信号側すなわち信号Ｆ１ＯｈおよびＦ４Ｏｈが入力される側に関して、演算順序の入れ替えを行っても機能的に等価性が保たれる場合を考える。これは論理関数で表現するならば、  ｆ１ｉ（ｆ３ｈ（ｆ２ｈ，Ｆ１Ｏｈ，Ｆ４Ｏｈ），Ｅ１ｉ）＝ｆ３ｈ（ｆ２ｈ，ｆ１ｉ（Ｆ１Ｏｈ，Ｅ１ｉ），ｆ１ｉ（Ｆ４Ｏｈ，Ｅ１ｉ）  ）  が成立するという意味である。また同時に、第三のパイプラインステージにおける演算要素ｆ１ｊ  ３１または演算要素ｆ１ｋ  ４１と、第二のパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３の第二および第三の入力側すなわち信号Ｆ１ＯｉおよびＦ４Ｏｉが入力される側に関しても、演算順序の入れ替えを行っても機能的に等価性が保たれる性質があるものとする。
【００１６】
このとき、図５に示したパイプライン演算器の演算要素を以下にしたがって移設することで得られる回路構成が図２に示す実施の形態である。
すなわち第二のパイプラインステージ２の第一の演算要素ｆ１ｉ  ２１を第一のパイプラインステージ１に移設するにあたって演算要素ｆ１ｉ  ２１の複製ｆ１ｉ  ２１１を設け、演算要素ｆ１ｉ  ２１をパイプラインステージ１の演算要素ｆ３ｈ  １３の第二の入力部分に移設し、また複製された演算要素ｆ１ｉ  ２１１をパイプラインステージ１の演算要素ｆ３ｈ  １３の第三の入力部分に移設する。移設後の配置は図２の同番号で示すとおりである。また第二のパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３を複製して第三のパイプラインステージの個数分だけ用意する。これが図２におけるｆ３ｉ  ２３とｆ３ｉ  ２３１である。後者が複製したものである。そして第三のパイプラインステージ３における演算要素ｆ１ｊ  ３１を第二のパイプラインステージ２に移設するにあたっては演算要素ｆ１ｊ  ３１の複製ｆ１ｊ  ３１１を設け、演算要素ｆ１ｊ  ３１をパイプラインステージ２の第三の演算要素ｆ３ｉ  ２３における第二の入力部分に移設し、複製された演算要素ｆ１ｊ  ３１１を第三の演算要素ｆ３ｉ  ２３における第三の入力部分に移設する。さらに第三のパイプラインステージ４における演算要素ｆ１ｋ  ４１を第二のパイプラインステージ２に移設するにあたっては演算要素ｆ１ｋ  ４１の複製ｆ１ｋ  ４１１を設け、演算要素ｆ１ｋ  ４１をパイプラインステージ２の第三の演算要素の複製ｆ３ｉ  ２３１における第二の入力部分に移設し、複製された演算要素ｆ１ｋ  ４１１を第三の演算要素の複製ｆ３ｉ  ２３１における第三の入力部分に移設する。これら演算要素の番号は図２に示してあるものである。これらによって得られるパイプライン演算器は、演算要素の移設を行う前の論理的機能に対する等価性を保ちつつ、パイプラインステージにおける信号経路長を演算要素３段から演算要素２段に短縮したものとなっており、動作速度が向上する。
【００１７】
図２において、演算要素ｆ１ｉ  ２１の信号伝搬遅延をｄｆ１ｉ、演算要素ｆ２ｉ  ２２の信号伝搬遅延をｄｆ２ｉ、演算要素ｆ３ｉ  ２３の信号伝搬遅延をｄｆ３ｉ、演算要素ｆ４ｉ  ２４の信号伝搬遅延をｄｆ４ｉ、演算要素ｆ１ｊ  ３１の信号伝搬遅延をｄｆ１ｊ、演算要素ｆ１ｋ  ４１の信号伝搬遅延をｄｆ１ｋとすると、パイプラインステージ２の信号伝搬遅延は  ｍａｘ（ｄｆ２ｉ，ｄｆ１ｊ，ｄｆ１ｋ）＋ｄｆ３ｉで表される（ｍａｘは最大値を選ぶ関数）。このときにｄｆ１ｉ，ｄｆ２ｉ，ｄｆ４ｉ，ｄｆ１ｊ，ｄｆ１ｋが同程度に大きく一方ｄｆ３ｉが十分に小さいならば、パイプラインステージ２の遅延は近似的にｄｆ２ｉとなる。一方図５におけるパイプラインステージの伝搬遅延はｍａｘ（ｄｆ１ｉ，ｄｆ４ｉ）＋ｄｆ２ｉ＋ｄｆ３ｉでありこれは近似的に２×ｄｆ２ｉなので、演算要素が上記のような遅延の大小関係を持つ場合には、図２の実施の形態により、図５の構成に比べて２倍近い速度向上が得られることになる。
【実施例１】
【００１８】
図３は、特許請求の範囲の請求項３に対応する実施例である。図６は、図３の実施例と機能が同じパイプライン演算器の従来例である。はじめに図６の従来例について説明すると、これは図５の従来例において、演算要素ｆ１ｉ、ｆ４ｉ、ｆ１ｊおよびｆ１ｋを加算器とし、演算要素ｆ２ｉを比較器とし、演算要素ｆ３ｉおよびｆ３ｈをマルチプレクサとしたものである。ここでマルチプレクサの選択信号は演算要素ｆ２ｉおよびｆ２ｈの出力である。また演算要素ｆ２ｉの出力を出力信号Ｙｉとして外部に引き出している。図６の従来例は、ブロック符号の最尤復号回路としてよく用いられるものであり、近年磁気記録や光記録メディアの動作速度の向上に伴って、高速化が強く望まれているものである。
【特許文献１】特開平０７−２７３６７０
【００１９】
図３は、図２に示した実施の形態とほとんど同じ構成で、演算要素がより具体化されたものであり、演算要素ｆ１ｉ、ｆ４ｉ、ｆ１ｊおよびｆ１ｋを加算器とし、演算要素ｆ２ｉを比較器とし、演算要素ｆ３ｉおよびｆ３ｈをマルチプレクサとしたものである。また演算要素ｆ２ｉの出力を出力信号Ｙｉとして外部に引き出している。加算器はマルチプレクサの前段に移設しても論理的機能の等価性を損なわないので、図３の実施例は図６のパイプライン演算器と比べて、同じ機能を保ちながら、パイプラインステージ１個の信号経路長を演算要素３段から２段に短縮して動作速度を向上している。またこのような演算要素を用いる場合には、加算器と比較器の伝播遅延時間が同程度に大きく、一方マルチプレクサの伝播遅延時間は加算器に比べて十分小さいことから、図３におけるパイプラインステージ２の伝播遅延時間は近似的に加算器１個の伝播遅延時間となる。一方図６のパイプラインステージ２における伝播遅延時間は、近似的に加算器２個分の伝播遅延時間であることから、図３の実施例は図６の従来例に比べて２倍近い高速化を実現したことになる。
【産業上の利用可能性】
【００２０】
本発明は、パイプライン演算器の高速化を可能にするものとして産業上の有用性が高いが、とくに磁気記録再生装置や光記録再生装置用ＬＳＩの高速化を可能にするものとして利用可能性がきわめて高い。
【図面の簡単な説明】
【００２１】
【図１】パイプライン演算器の実施の形態を示した説明図である。
【図２】パイプライン演算器の実施の形態を示した説明図である。
【図３】パイプライン演算器の実施例を示した説明図である。(実施例１)
【図４】パイプライン演算器の従来例を示した説明図である。
【図５】パイプライン演算器の従来例を示した説明図である。
【図６】パイプライン演算器の従来例を示した説明図である。
【符号の説明】
【００２２】
１，２，３，４  パイプラインステージ
５  パイプラインレジスタ
１１，１２，１３，１４，２１，２２，２３，２４  演算要素
３１，３２，３３，３４，４１，４２，４３，４４  演算要素
２１１，２３１，３１１，４１１，３３１，４３１  演算要素
【図１】
2006113989.tif 000003
【図２】
2006113989.tif 000004
【図３】
2006113989.tif 000005
【図４】
2006113989.tif 000006
【図５】
2006113989.tif 000007
【図６】
2006113989.tif 000008