JPH05197741A - インターリーブド乗算器累算器 - Google Patents
インターリーブド乗算器累算器Info
- Publication number
- JPH05197741A JPH05197741A JP17203392A JP17203392A JPH05197741A JP H05197741 A JPH05197741 A JP H05197741A JP 17203392 A JP17203392 A JP 17203392A JP 17203392 A JP17203392 A JP 17203392A JP H05197741 A JPH05197741 A JP H05197741A
- Authority
- JP
- Japan
- Prior art keywords
- pipeline
- multiplier
- accumulator
- segments
- interleaved
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
- G06F7/5443—Sum of products
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
- G06F2207/3804—Details
- G06F2207/386—Special constructional features
- G06F2207/3884—Pipelining
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Physics (AREA)
- Computational Mathematics (AREA)
- Computing Systems (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- Complex Calculations (AREA)
- Advance Control (AREA)
Abstract
(57)【要約】
【目的】 高い処理能力及び効率的な行列乗算を実行す
ることが可能なインターリーブド乗算器累算器を提供す
る。 【構成】 本発明に基づくインターリーブド乗算器累算
器は、それぞれが乗算器素子とパイプラインレジスタを
含む複数の直列接続された乗算器セグメントとそれぞれ
が加算器素子とパイプラインレジスタを含む複数の直列
接続された累算器セグメントから構成され、行列乗算な
どのデータは直列接続された最初の乗算セグメントに送
られ、全てのパイプラインレジスタがクロックされ、直
列接続された最後の乗算器セグメントからの出力は直列
接続された最初の累算器セグメントに加えら、直列接続
される最後の累算器セグメントの出力は最初の累算器セ
グメントの入力に加えられ、乗算器累算器の全体として
の出力は最後の累算器セグメントの出力から得られる。
ることが可能なインターリーブド乗算器累算器を提供す
る。 【構成】 本発明に基づくインターリーブド乗算器累算
器は、それぞれが乗算器素子とパイプラインレジスタを
含む複数の直列接続された乗算器セグメントとそれぞれ
が加算器素子とパイプラインレジスタを含む複数の直列
接続された累算器セグメントから構成され、行列乗算な
どのデータは直列接続された最初の乗算セグメントに送
られ、全てのパイプラインレジスタがクロックされ、直
列接続された最後の乗算器セグメントからの出力は直列
接続された最初の累算器セグメントに加えら、直列接続
される最後の累算器セグメントの出力は最初の累算器セ
グメントの入力に加えられ、乗算器累算器の全体として
の出力は最後の累算器セグメントの出力から得られる。
Description
【０００１】
【産業上の利用分野】本発明は、ディジタル信号処理及
びグラフィックスシステムに置いて使用されるような乗
算器累算器に関し、特に行列乗算を含む用途に関する。
びグラフィックスシステムに置いて使用されるような乗
算器累算器に関し、特に行列乗算を含む用途に関する。
【０００２】
【従来の技術】最近のディジタル信号処理及びグラフィ
ックスシステムの分野において、特に、実時間画像処理
及び多次元制御システムなどの応用分野において、多く
の積和計算を頻繁に実行する必要がある。一般的に、か
かる応用分野では、高速の行列乗算、あるいは多数の連
立方程式の解法が必要である。これらの問題の解法に
は、次のような形式の項を含む計算が必要とされる。
ックスシステムの分野において、特に、実時間画像処理
及び多次元制御システムなどの応用分野において、多く
の積和計算を頻繁に実行する必要がある。一般的に、か
かる応用分野では、高速の行列乗算、あるいは多数の連
立方程式の解法が必要である。これらの問題の解法に
は、次のような形式の項を含む計算が必要とされる。
【０００３】
【数１】
【０００４】典型的には、これらの計算は、乗算器累算
器として、あるいは乗算器累算器のアレイとして構成さ
れたディジタルハードウェアの助けを借りて実行され
る。
器として、あるいは乗算器累算器のアレイとして構成さ
れたディジタルハードウェアの助けを借りて実行され
る。
【０００５】乗算器累算器はその構成部分の乗算器及び
累算器から命名されている。乗算器部分は２つのディジ
タル入力を受け取りディジタル積を演算する。累算器
は、ディジタル加算器と格納素子又はパイプラインレジ
スタの２つの二次構成部分から構成される。一般的に、
累算器は、パイプラインレジスタの出力が加算器の入力
の１つに接続されて、加算器の出力が格納素子の入力に
接続されて、各連続加算に伴いパイプラインレジスタ内
のディジタル値が加算された量分増加する。
累算器から命名されている。乗算器部分は２つのディジ
タル入力を受け取りディジタル積を演算する。累算器
は、ディジタル加算器と格納素子又はパイプラインレジ
スタの２つの二次構成部分から構成される。一般的に、
累算器は、パイプラインレジスタの出力が加算器の入力
の１つに接続されて、加算器の出力が格納素子の入力に
接続されて、各連続加算に伴いパイプラインレジスタ内
のディジタル値が加算された量分増加する。
【０００６】加算器累算器の中には、固定小数点（又は
２値整数）の数値に関してのみ動作するものもあり、他
方浮動小数点の数値に関してのみ動作するものもある。
いずれの場合にも、回路トポロジーは同じである。唯一
の相違は乗算器と累算器の固有の設計に見られるのみで
ある。浮動小数点及び固定小数点の乗算器及び累算器の
双方とも周知であり、当業界において広く使用されてい
るので、それらの設計の詳細についてはここでは述べな
い。
２値整数）の数値に関してのみ動作するものもあり、他
方浮動小数点の数値に関してのみ動作するものもある。
いずれの場合にも、回路トポロジーは同じである。唯一
の相違は乗算器と累算器の固有の設計に見られるのみで
ある。浮動小数点及び固定小数点の乗算器及び累算器の
双方とも周知であり、当業界において広く使用されてい
るので、それらの設計の詳細についてはここでは述べな
い。
【０００７】乗算器累算器は特に積和計算に適するもの
である。積が計算されると、その積を以前の加算結果を
含む格納レジスタの内容に加算可能である。結果が格納
レジスタに格納されて、次の乗算が実行される。
である。積が計算されると、その積を以前の加算結果を
含む格納レジスタの内容に加算可能である。結果が格納
レジスタに格納されて、次の乗算が実行される。
【０００８】典型的な乗算器累算器の構成例を図１及び
図２に示す。これらの図中には、以下の素子が示されて
いる：すなわち、乗算器１１０、２１０；加算器１２
０、２２０；パイプラインレジスタ１３０、２３０、２
９０；クロック１４０、２４０；乗算器入力１５０、１
６０、２５０、２６０；加算器入力１７０、１８０、２
７０、２８０が示されている。
図２に示す。これらの図中には、以下の素子が示されて
いる：すなわち、乗算器１１０、２１０；加算器１２
０、２２０；パイプラインレジスタ１３０、２３０、２
９０；クロック１４０、２４０；乗算器入力１５０、１
６０、２５０、２６０；加算器入力１７０、１８０、２
７０、２８０が示されている。
【０００９】図１において、乗算器及び累算器は、２つ
の入力「Ｘ」及び「Ａ」（前述の積和の「Ｘ」及び
「Ａ」項に相当する）が乗算器の入力に加えられ、乗算
器の出力が累算器（加算器１２０）の一方の入力に加え
られるように、接続される。累算器（加算器１２０）の
出力は、その出力が累算器（１２０）の他方の入力に接
続されているエッジトリガパイプラインレジスタに入力
されている。
の入力「Ｘ」及び「Ａ」（前述の積和の「Ｘ」及び
「Ａ」項に相当する）が乗算器の入力に加えられ、乗算
器の出力が累算器（加算器１２０）の一方の入力に加え
られるように、接続される。累算器（加算器１２０）の
出力は、その出力が累算器（１２０）の他方の入力に接
続されているエッジトリガパイプラインレジスタに入力
されている。
【００１０】図２の乗算器累算器は図１のものと同様で
あるが、エッジトリガパイプラインレジスタ２９０が乗
算器出力及び累算器入力の間に配置されている。
あるが、エッジトリガパイプラインレジスタ２９０が乗
算器出力及び累算器入力の間に配置されている。
【００１１】図１の乗算器累算器においては、入力１６
０「Ａn 」及び１５０「Ｘn 」（ここで、添え字「ｎ」
は図示していないがサンプリング時間「ｎ」に関連して
いる）が乗算器１１０に関して動作して、ライン１７０
に結果「ＡＸn 」を生じる。この結果が次いで累算器１
２０の一方の入力に加えられる。累算器１２０の出力は
パイプラインレジスタ１３０に送られる。レジスタ１３
０の出力はライン１８０を介して累算器１２０の他方の
入力に接続されている。次の入力「Ａn+1 」及び「Ｘn+
1 」は、結果「ＡＸn 」がパイプラインレジスタにより
ラッチされるまで（クロック１４０）、乗算器に入力さ
れることはない。最小クロック周期は、乗算器入力とレ
ジスタの間の全ての直列遅れを考慮に入れる必要があ
る。この周期は次式により与えられる。
０「Ａn 」及び１５０「Ｘn 」（ここで、添え字「ｎ」
は図示していないがサンプリング時間「ｎ」に関連して
いる）が乗算器１１０に関して動作して、ライン１７０
に結果「ＡＸn 」を生じる。この結果が次いで累算器１
２０の一方の入力に加えられる。累算器１２０の出力は
パイプラインレジスタ１３０に送られる。レジスタ１３
０の出力はライン１８０を介して累算器１２０の他方の
入力に接続されている。次の入力「Ａn+1 」及び「Ｘn+
1 」は、結果「ＡＸn 」がパイプラインレジスタにより
ラッチされるまで（クロック１４０）、乗算器に入力さ
れることはない。最小クロック周期は、乗算器入力とレ
ジスタの間の全ての直列遅れを考慮に入れる必要があ
る。この周期は次式により与えられる。
【００１２】
【数２】
【００１３】図２の乗算器累算器はほぼ図１の装置と同
様であり、図１と似た番号が付された乗算器２１０、累
算器（加算器部分）２２０、レジスタ２３０、及びライ
ン２４０、２５０、２６０、２７０、及び２８０を備え
ている。主な相違は、乗算器２２０の出力に第２のパイ
プラインレジスタ２９０が付加された点にある。二重の
パイプライン構成により、この構成の最小のクロック周
期は次式により与えられる。
様であり、図１と似た番号が付された乗算器２１０、累
算器（加算器部分）２２０、レジスタ２３０、及びライ
ン２４０、２５０、２６０、２７０、及び２８０を備え
ている。主な相違は、乗算器２２０の出力に第２のパイ
プラインレジスタ２９０が付加された点にある。二重の
パイプライン構成により、この構成の最小のクロック周
期は次式により与えられる。
【００１４】
【数３】
【００１５】この構成は、図１の乗算器累算器と同様の
構成によって、より高速に動作することが可能である
が、結果がレジスタ２３０の出力に現れる前に、付加的
な遅れのクロック周期が必要である。
構成によって、より高速に動作することが可能である
が、結果がレジスタ２３０の出力に現れる前に、付加的
な遅れのクロック周期が必要である。
【００１６】図１及び図２の乗算器及び累算器の伝搬遅
れが等しく、ｔpdの数値を有し、さらにレジスタとクロ
ックに関連する遅れが無視できるものと仮定すると、ｎ
×ｎの行列にｎ×１のベクトルを乗算するために必要な
式はそれぞれ次式により与えられる。
れが等しく、ｔpdの数値を有し、さらにレジスタとクロ
ックに関連する遅れが無視できるものと仮定すると、ｎ
×ｎの行列にｎ×１のベクトルを乗算するために必要な
式はそれぞれ次式により与えられる。
【００１７】
【数４】
【００１８】画像処理及びグラフィックスのアプリケー
ションが大きくなると、より高速な表示解度及びより良
好なユーザ応答性に対するニーズが高まる。これはより
高速の行列乗算に関するニーズの増加と換言できる。多
くの高速画像処理システムが設計されているが、これら
は、速度を改良するためのディジタルハードウェアの量
的なディジタルハードウェアの並行処理に基づいてい
る。明らかに、かかるシステムは非常に高価となる可能
性がある。
ションが大きくなると、より高速な表示解度及びより良
好なユーザ応答性に対するニーズが高まる。これはより
高速の行列乗算に関するニーズの増加と換言できる。多
くの高速画像処理システムが設計されているが、これら
は、速度を改良するためのディジタルハードウェアの量
的なディジタルハードウェアの並行処理に基づいてい
る。明らかに、かかるシステムは非常に高価となる可能
性がある。
【００１９】これらの用途のために、可能な限り低いコ
ストで最良の動作性能を得ることができる乗算器累算器
に対するニーズが存在する。
ストで最良の動作性能を得ることができる乗算器累算器
に対するニーズが存在する。
【００２０】
【発明が解決しようとする課題】したがって、本発明の
目的は、従来の乗算器累算器よりも良好な処理能力を有
する乗算器累算器を提供することである。
目的は、従来の乗算器累算器よりも良好な処理能力を有
する乗算器累算器を提供することである。
【００２１】さらに本発明の別な目的は、行列乗算時間
を相当短縮可能な乗算器累算器を提供することである。
を相当短縮可能な乗算器累算器を提供することである。
【００２２】さらに本発明の別の目的は、従来の乗算器
累算器よりも乗算器累算器に関する最小クロック周期を
相当短縮することである。
累算器よりも乗算器累算器に関する最小クロック周期を
相当短縮することである。
【００２３】
【課題を解決するための手段】本発明によれば、インタ
ーリーブド乗算器累算器は、複数の直列接続された乗算
器セグメントと、複数の直列接続された累算器セグメン
トから構成される。各乗算器セグメントは、乗算器素子
とパイプラインレジスタとを含んでいる。各累算器セグ
メントは加算器（その他の演算ユニット）素子とパイプ
ラインレジスタを含んでいる。行列乗算に関するような
データは、直列接続された乗算セグメントの最初のセグ
メントに送られ、全てのパイプラインレジスタがクロッ
クされる。直列接続された乗算器セグメントの最後のセ
グメントからの出力は直列接続された累算器セグメント
の最初のセグメントに加えられる。直列接続される累算
器セグメントの最後のセグメントの出力は累算器セグメ
ントの最初のセグメントの他方の入力に加えられる。乗
算器累算器の全体としての出力は最後の累算器セグメン
トの出力から得られる。
ーリーブド乗算器累算器は、複数の直列接続された乗算
器セグメントと、複数の直列接続された累算器セグメン
トから構成される。各乗算器セグメントは、乗算器素子
とパイプラインレジスタとを含んでいる。各累算器セグ
メントは加算器（その他の演算ユニット）素子とパイプ
ラインレジスタを含んでいる。行列乗算に関するような
データは、直列接続された乗算セグメントの最初のセグ
メントに送られ、全てのパイプラインレジスタがクロッ
クされる。直列接続された乗算器セグメントの最後のセ
グメントからの出力は直列接続された累算器セグメント
の最初のセグメントに加えられる。直列接続される累算
器セグメントの最後のセグメントの出力は累算器セグメ
ントの最初のセグメントの他方の入力に加えられる。乗
算器累算器の全体としての出力は最後の累算器セグメン
トの出力から得られる。
【００２４】本発明のある特徴によれば、別のパイプラ
イン段を最後の乗算器及び累算器セグメントの出力に直
列接続することが可能である。
イン段を最後の乗算器及び累算器セグメントの出力に直
列接続することが可能である。
【００２５】本発明のある特徴によれば、乗算器及び加
算器素子を別の演算ユニットと構成し、レジスタをメモ
リ内に集中することが可能である。
算器素子を別の演算ユニットと構成し、レジスタをメモ
リ内に集中することが可能である。
【００２６】本発明のインターリーブド乗算器累算器
は、そのパイプライン乗算器及び累算器構成により高い
処理能力と効果的な行列乗算を実行可能である。
は、そのパイプライン乗算器及び累算器構成により高い
処理能力と効果的な行列乗算を実行可能である。
【００２７】他の目的、特徴及び効果については、以下
の説明により明らかになろう。
の説明により明らかになろう。
【００２８】
【実施例】図３は、パイプライン乗算器（３０６−３２
０）、パイプライン加算器又は累算器（３５６−３７
０）、及び多数の追加パイプラインレジスタ（３２２，
３２４，３２６，３７２，３７４，３８０）から成る乗
算器累算器３００を示している。乗算器は、それぞれが
パイプラインレジスタ（３０８，３１２，３１６，３２
０）を介して次のセグメントに送られるｋ個のパイプラ
インセグメント（乗算器３０６，３１０，３１４，３１
８）と、ｊ個の別に直列接続されたパイプラインレジス
タ（３２２，３２４，３２６）から構成されて、パイプ
ラインレジスタの総数（ｋ＋ｊ）が同じ次数（ｎ）のベ
クトルに乗算される正方行列の次数（ｎ）と等しくなっ
ている。
０）、パイプライン加算器又は累算器（３５６−３７
０）、及び多数の追加パイプラインレジスタ（３２２，
３２４，３２６，３７２，３７４，３８０）から成る乗
算器累算器３００を示している。乗算器は、それぞれが
パイプラインレジスタ（３０８，３１２，３１６，３２
０）を介して次のセグメントに送られるｋ個のパイプラ
インセグメント（乗算器３０６，３１０，３１４，３１
８）と、ｊ個の別に直列接続されたパイプラインレジス
タ（３２２，３２４，３２６）から構成されて、パイプ
ラインレジスタの総数（ｋ＋ｊ）が同じ次数（ｎ）のベ
クトルに乗算される正方行列の次数（ｎ）と等しくなっ
ている。
【００２９】また、本発明によれば、同様に構成された
加算器連鎖（３５６−３７０）が存在しており、それ
は、それぞれがパイプラインレジスタ（３５８，３６
２，３６６，３７０）を介して次のセグメントに送られ
る同数のｋ個のパイプライン加算器セグメント（３０
６，３１０，３１４，３１８）と、同数のｊ個の別の直
列接続されたパイプラインレジスタ（３７２，３７４，
３８０）を備えている。最後のパイプラインレジスタ３
８０の出力は最初のパイプライン加算器セグメントの入
力３５４の一方にフィードバックされる。他方の入力３
５２は前述のパイプライン乗算器の最後のパイプライン
レジスタ３２６の出力に接続されている。
加算器連鎖（３５６−３７０）が存在しており、それ
は、それぞれがパイプラインレジスタ（３５８，３６
２，３６６，３７０）を介して次のセグメントに送られ
る同数のｋ個のパイプライン加算器セグメント（３０
６，３１０，３１４，３１８）と、同数のｊ個の別の直
列接続されたパイプラインレジスタ（３７２，３７４，
３８０）を備えている。最後のパイプラインレジスタ３
８０の出力は最初のパイプライン加算器セグメントの入
力３５４の一方にフィードバックされる。他方の入力３
５２は前述のパイプライン乗算器の最後のパイプライン
レジスタ３２６の出力に接続されている。
【００３０】最初に、ゼロ入力を乗算器一方または双方
に加え、累算器フィードバック３５４をゼロに強制し、
さらに、全てのレジスタがゼロで満たされるまでシステ
ムをクロッキングする（クロック３９０を参照）ことに
より、あるいは、ダイレクト手段によりレジスタを並行
ロードすることにより、あるいは累算器フィードバック
信号をゼロに強制することにより、全てのレジスタがク
リアされる（ゼロで満たされる）。
に加え、累算器フィードバック３５４をゼロに強制し、
さらに、全てのレジスタがゼロで満たされるまでシステ
ムをクロッキングする（クロック３９０を参照）ことに
より、あるいは、ダイレクト手段によりレジスタを並行
ロードすることにより、あるいは累算器フィードバック
信号をゼロに強制することにより、全てのレジスタがク
リアされる（ゼロで満たされる）。
【００３１】初期化の後に、乗算及び累算される入力対
が、クロック３９０の１周期ごとに１対の割合で対の連
続形式で（例えば、Ａ1 とＸ1 、Ａ2 とＸ1 といったよ
うに）乗算器累算器に加えられる。ｋクロック周期の後
に、最初に終了した積（すなわちＸ1 とＡ1 との積）が
パイプラインレジスタ３２０の出力に表れる。他の３つ
の積はパイプライン中において処理中であるが（すなわ
ち、レジスタ３１６内におけるＡ2 Ｘ2 、レジスタ３１
２内におけるＡ3 Ｘ3 、及びレジスタ３０８内における
Ａ4 Ｘ4 ）、未だ全てが解法されてはいない。さらにｊ
クロック後に、最初の積、Ａ1 Ｘ1 が累算器の入力３５
２に表れる。さらにｎクロック後に、全ての累算器パイ
プラインレジスタが、内部に１つの積の項を有すること
になる（各々にゼロ値が加算されるが、数値は、ｋ番面
緒レジスタ３７０に到達するまで、完全に解法されるわ
けではない）。レジスタ３５８はＡn Ｘn を備え、レジ
スタ３６２はＡn-1 Ｘn-1 を備えるといったように続
き、レジスタ３８０がＡ1 Ｘ1 を備えることになる。次
のクロックで、レジスタ３８０の出力が乗算器パイプラ
インの次の積、Ａn+1 Ｘn+1 に加算される。この処理
が、パイプライン内の全てのレジスタがｎクロック間隔
だけ間を置いた積の和を含むようになるまで継続され
る。すなわち、ｎが８であり、レジスタ３８０がＡ1 Ｘ
1 ＋Ａ9 Ｘ9 を有する場合には、レジスタ３７４はＡ2
Ｘ2 ＋Ａ10Ｘ10を含むといったようになる。
が、クロック３９０の１周期ごとに１対の割合で対の連
続形式で（例えば、Ａ1 とＸ1 、Ａ2 とＸ1 といったよ
うに）乗算器累算器に加えられる。ｋクロック周期の後
に、最初に終了した積（すなわちＸ1 とＡ1 との積）が
パイプラインレジスタ３２０の出力に表れる。他の３つ
の積はパイプライン中において処理中であるが（すなわ
ち、レジスタ３１６内におけるＡ2 Ｘ2 、レジスタ３１
２内におけるＡ3 Ｘ3 、及びレジスタ３０８内における
Ａ4 Ｘ4 ）、未だ全てが解法されてはいない。さらにｊ
クロック後に、最初の積、Ａ1 Ｘ1 が累算器の入力３５
２に表れる。さらにｎクロック後に、全ての累算器パイ
プラインレジスタが、内部に１つの積の項を有すること
になる（各々にゼロ値が加算されるが、数値は、ｋ番面
緒レジスタ３７０に到達するまで、完全に解法されるわ
けではない）。レジスタ３５８はＡn Ｘn を備え、レジ
スタ３６２はＡn-1 Ｘn-1 を備えるといったように続
き、レジスタ３８０がＡ1 Ｘ1 を備えることになる。次
のクロックで、レジスタ３８０の出力が乗算器パイプラ
インの次の積、Ａn+1 Ｘn+1 に加算される。この処理
が、パイプライン内の全てのレジスタがｎクロック間隔
だけ間を置いた積の和を含むようになるまで継続され
る。すなわち、ｎが８であり、レジスタ３８０がＡ1 Ｘ
1 ＋Ａ9 Ｘ9 を有する場合には、レジスタ３７４はＡ2
Ｘ2 ＋Ａ10Ｘ10を含むといったようになる。
【００３２】特に有用で説明しやすい特殊事例が以下に
示すような４×４の行列ベクトル乗算である。
示すような４×４の行列ベクトル乗算である。
【００３３】
【数５】
【００３４】結果として得られるベクトルは、以下の４
項を有している。 １）ＡＸ＋ＢＹ＋ＣＺ＋ＤＷ ２）ＥＸ＋ＦＹ＋ＧＺ＋ＨＷ ３）ＩＸ＋ＪＹ＋ＫＺ＋ＬＷ ４）ＭＸ＋ＮＹ＋ＯＺ＋ＰＷ
項を有している。 １）ＡＸ＋ＢＹ＋ＣＺ＋ＤＷ ２）ＥＸ＋ＦＹ＋ＧＺ＋ＨＷ ３）ＩＸ＋ＪＹ＋ＫＺ＋ＬＷ ４）ＭＸ＋ＮＹ＋ＯＺ＋ＰＷ
【００３５】図４は、前述の４×４行列ベクトル積を計
算するための乗算器累算器４００の構造を示している。
以下の素子が示されているが、詳細な説明は不要であろ
う。乗算器４０６，４１０，４１４，４１８；加算器４
５６，４６０，４６４，４６８；乗算器４０２，４０４
に対する入力；加算器４５２，４５４に対する入力；パ
イプラインレジスタ４０８，４１２，４１６，４２０，
４５８，４６２，４６６，４７０及びクロック入力４９
０である。
算するための乗算器累算器４００の構造を示している。
以下の素子が示されているが、詳細な説明は不要であろ
う。乗算器４０６，４１０，４１４，４１８；加算器４
５６，４６０，４６４，４６８；乗算器４０２，４０４
に対する入力；加算器４５２，４５４に対する入力；パ
イプラインレジスタ４０８，４１２，４１６，４２０，
４５８，４６２，４６６，４７０及びクロック入力４９
０である。
【００３６】レジスタ遅れが（適当に近似された）乗算
器及び加算器遅れに比較して無視可能であり、さらに、
図４に示すように、乗算器及び累算器がそれぞれ４つの
内部パイプラインセクション（レジスタの後に各演算ユ
ニットが続く）を備えるようにばらばらにされているも
のとするならば、使用され得る最小クロック周期は、乗
算器遅れもまた４つの大体等しいセグメントに分解され
るため、おおまかにいってｔPD(MUL) ／４となる。これ
は図２の乗算器累算器クロック速度の約４倍であり、図
１の乗算器累算器のクロック速度の約８倍である。
器及び加算器遅れに比較して無視可能であり、さらに、
図４に示すように、乗算器及び累算器がそれぞれ４つの
内部パイプラインセクション（レジスタの後に各演算ユ
ニットが続く）を備えるようにばらばらにされているも
のとするならば、使用され得る最小クロック周期は、乗
算器遅れもまた４つの大体等しいセグメントに分解され
るため、おおまかにいってｔPD(MUL) ／４となる。これ
は図２の乗算器累算器クロック速度の約４倍であり、図
１の乗算器累算器のクロック速度の約８倍である。
【００３７】従来の乗算器累算器は以下の順番の入力が
表れる。 ＡＸ，ＢＹ，ＣＺ，ＤＷ，ＥＸ，ＦＹ，ＧＺ，ＨＷ …
表れる。 ＡＸ，ＢＹ，ＣＺ，ＤＷ，ＥＸ，ＦＹ，ＧＺ，ＨＷ …
【００３８】本発明に基づく乗算器累算器内では内部パ
イプライン処理がされているので、処理のためのデータ
表示の順番は代わりに次のようになる。 ＡＸ，ＥＸ，ＩＸ，ＭＸ，ＢＹ，ＦＹ，ＪＹ，ＮＹ …
イプライン処理がされているので、処理のためのデータ
表示の順番は代わりに次のようになる。 ＡＸ，ＥＸ，ＩＸ，ＭＸ，ＢＹ，ＦＹ，ＪＹ，ＮＹ …
【００３９】本発明に基づくデータ処理の「インターリ
ーブド」の特質のため、「インターリーブド乗算器累算
器」と言及する。
ーブド」の特質のため、「インターリーブド乗算器累算
器」と言及する。
【００４０】図５は、４×４行列ベクトル乗算に関する
データタイミングとフローであり、図１及び図２の乗算
器累算器に関しては、それぞれ、「０１」及び「０２」
と言及され、本発明のインターリーブド乗算器累算器に
関しては「Ｉ」として言及されている。
データタイミングとフローであり、図１及び図２の乗算
器累算器に関しては、それぞれ、「０１」及び「０２」
と言及され、本発明のインターリーブド乗算器累算器に
関しては「Ｉ」として言及されている。
【００４１】図５より、ｎ＝ｋ＝４の場合の事例に関す
る比較が容易に行え、各乗算器累算器の待ち時間は（イ
ンターリーブド乗算器累算器クロック周期の時間単位に
おいて）次のようになる。 ０１：ｔ＝１２８時間単位 ０２：ｔ＝ ６８時間単位 Ｉ ：ｔ＝ ２０時間単位（クロック周期）
る比較が容易に行え、各乗算器累算器の待ち時間は（イ
ンターリーブド乗算器累算器クロック周期の時間単位に
おいて）次のようになる。 ０１：ｔ＝１２８時間単位 ０２：ｔ＝ ６８時間単位 Ｉ ：ｔ＝ ２０時間単位（クロック周期）
【００４２】ｎ≧ｋである場合の待ち時間は（再びイン
ターリーブド乗算器累算器クロック周期の時間単位にお
いて）次のようになる（０１及び０２については比較の
ために示されている。 ０１：ｔ＝２ｋｎ2 ０２：ｔ＝ｋｎ2 ＋ｋ Ｉ ：ｔ＝ｎ2 ＋ｎ
ターリーブド乗算器累算器クロック周期の時間単位にお
いて）次のようになる（０１及び０２については比較の
ために示されている。 ０１：ｔ＝２ｋｎ2 ０２：ｔ＝ｋｎ2 ＋ｋ Ｉ ：ｔ＝ｎ2 ＋ｎ
【００４３】連続動作に関する３つの方法の処理能力Ｔ
（毎秒の行列ベクトル乗算）は次のようになる。 ０１：Ｔ＝１／（２ｋ2 ｔclk ） ０２：Ｔ＝１／（ｎ2 ｔ＋ｋclk ） Ｉ ：Ｔ＝ｋ／（ｎ2 ｔclk ）
（毎秒の行列ベクトル乗算）は次のようになる。 ０１：Ｔ＝１／（２ｋ2 ｔclk ） ０２：Ｔ＝１／（ｎ2 ｔ＋ｋclk ） Ｉ ：Ｔ＝ｋ／（ｎ2 ｔclk ）
【００４４】このように、本発明のインターリーブド乗
算器累算器は、図１の乗算器累算器よりも２ｋ倍高速で
あり、図２の乗算器累算器よりもｋ倍高速である。４×
４行列ベクトル乗算に関する事例では、インターリーブ
ド乗算器累算器よりも８倍高速であり、図２の乗算器累
算器の４倍高速である。
算器累算器は、図１の乗算器累算器よりも２ｋ倍高速で
あり、図２の乗算器累算器よりもｋ倍高速である。４×
４行列ベクトル乗算に関する事例では、インターリーブ
ド乗算器累算器よりも８倍高速であり、図２の乗算器累
算器の４倍高速である。
【００４５】
【発明の効果】特許請求の範囲に記載されたインターリ
ーブド乗算器累算器に関しては、 (a) パイプラインレジスタはラッチやメモリのようなコ
ンピュータの格納装置内で実行可能であり； (b) クロック信号はいかなる周期的信号でも構わず； (c) 乗算器及び加算器は、乗算器、加算器、除算器、減
算器などの本発明の場合には関数（ｆ）及び（ｇ）を実
行するインターリーブドユニットとして広範に表現され
ているような任意の演算関数（演算論理ユニット）とす
ることが可能であることに留意されたい。
ーブド乗算器累算器に関しては、 (a) パイプラインレジスタはラッチやメモリのようなコ
ンピュータの格納装置内で実行可能であり； (b) クロック信号はいかなる周期的信号でも構わず； (c) 乗算器及び加算器は、乗算器、加算器、除算器、減
算器などの本発明の場合には関数（ｆ）及び（ｇ）を実
行するインターリーブドユニットとして広範に表現され
ているような任意の演算関数（演算論理ユニット）とす
ることが可能であることに留意されたい。
【００４６】以上のように、本発明に基づくインターリ
ーブド乗算器累算器は、そのパイプライン乗算器及び累
算器構成により、高い処理能力及び効率的な行列乗算を
実行することが可能である。
ーブド乗算器累算器は、そのパイプライン乗算器及び累
算器構成により、高い処理能力及び効率的な行列乗算を
実行することが可能である。
【図１】従来の単一パイプライン乗算器累算器の構造を
示すブロック図である。
示すブロック図である。
【図２】従来の二重パイプライン乗算器累算器の構造を
示すブロック図である。
示すブロック図である。
【図３】本発明の乗算器累算器の好適な実施例の構造を
示すブロック図である。
示すブロック図である。
【図４】４×４行列乗算用に特に設計された本発明の好
適な実施例を示すブロック図である。
適な実施例を示すブロック図である。
【図５】４×４行列ベクトル乗算用の本発明の乗算器累
算器を通過するデータフローを示すデータフロー及びタ
イミング図である。
算器を通過するデータフローを示すデータフロー及びタ
イミング図である。
３００ 乗算器累算器 ３０２−３０４ 乗算器入力 ３０６−３２０ パイプライン乗算器 ３２２−３２６ パイプラインレジスタ ３６２−３５４ 累算器入力 ３５６−３７０ パイプライン加算器 ３７２−３８０ パイプラインレジスタ ３９０ クロック入力
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ウェン−ウィ ティ アメリカ合衆国、カリフォルニア州 95035、ミルピタス、サラトガ ドライブ 1423
Claims (10)
- 【請求項１】２つのデータ入力と；１つのデータ出力
と；クロック信号を受信するための手段と；パイプライ
ン乗算器であって、前記２つのデータ入力に接続され、
複数の直列接続されたパイプライン乗算器セグメントを
備え、さらに第１の最終パイプラインレジスタを含み、
パイプラインセグメントが存在する数と同じ数の乗算が
処理可能であり、各クロック信号が各部分的に解決され
た乗算項を次に直列接続されたパイプラインセグメント
に進め、さらに前記第１の最終パイプラインレジスタの
出力が前記パイプライン乗算器のデータ出力とされるよ
うに構成されるものと；パイプライン累算器であって、
２つの入力と１つのデータ出力と複数の直列接続された
パイプライン累算器セグメントを備え、さらに第２の最
終パイプラインレジスタを含み、パイプラインセグメン
トが存在する数と同じ数の加算（累算）が処理可能であ
り、各クロック周期が各部分的に解決された加算（累
算）項を次に直列接続されたパイプラインセグメントに
進め、さらに第２の最終パイプラインレジスタの出力が
前記パイプライン累算器のデータ出力とされるように構
成されるものと；からなり、前記パイプライン乗算器及
び前記パイプライン累算器が、前記パイプライン乗算器
の前記第１の最終パイプラインレジスタの出力が前記パ
イプライン累算器の１つの入力に接続され、前記パイプ
ライン累算器の前記第２の最終パイプラインレジスタの
出力が前記パイプライン累算器の他の入力に接続されて
さらにインターリーブド乗算器累算器の出力ともされる
ように相互接続されており；さらに、前記パイプライン
レジスタが前記クロック信号を受信する手段に応答する
べく接続されていることを特徴とする、インターリーブ
ド乗算器累算器。 - 【請求項２】前記パイプラインレジスタが１つのコンピ
ュータ格納装置内に置かれることを特徴とする、請求項
１に記載のインターリーブド乗算器累算器。 - 【請求項３】前記パイプライン乗算器セグメントの数が
パイプライン累算器セグメントの数と同数であることを
特徴とする、請求項１に記載のインターリーブド乗算器
累算器。 - 【請求項４】乗算器内のパイプラインセグメントの数が
乗算器動作をパイプライン処理するために必要な数より
も多く、パイプライン乗算器の剰余が直列接続されたパ
イプラインレジスタから形成されることを特徴とする、
請求項３に記載のインターリーブド乗算器累算器。 - 【請求項５】累算器内のパイプラインセグメントの数が
累算器動作をパイプライン処理するために必要な数より
も多く、パイプライン乗算器の剰余が直列接続されたパ
イプラインレジスタから形成されることを特徴とする、
請求項３に記載のインターリーブド乗算器累算器。 - 【請求項６】行列ベクトル乗算用に構成され、パイプラ
イン乗算器内のパイプラインセグメントの数及びパイプ
ライン累算器内のパイプラインセグメントの数がそれぞ
れ処理される行列ベクトル乗算の次数（ｎ）と同じ数で
あり、行列項が前記インターリーブド乗算器累算器の１
つの入力に頂部から底部に及び左から右に向かい入力さ
れ、ベクトル項が前記インターリーブド乗算器累算器の
他方の入力に左から右に向かって順次、但し「ｎ番目」
のクロック毎にのみ進むように入力されることを特徴と
する、請求項３に記載のインターリーブド乗算器累算
器。 - 【請求項７】前記パイプライン乗算器と前記パイプライ
ン累算器が２値整数乗算及び加算のみ用に構成されてい
ることを特徴とする、請求項１に記載のインターリーブ
ド乗算器累算器。 - 【請求項８】前記パイプライン乗算器及び前記パイプラ
イン累算器が浮動小数点乗算及び加算用に構成されてい
ることを特徴とする、請求項１に記載のインターリーブ
ド乗算器累算器。 - 【請求項９】２つのデータ入力と；１つのデータ出力
と；周期的に信号を受信するための手段と；第１の関数
（ｆ）を実行するための第１のパイプライン演算装置で
あって、前記２つのデータ入力に接続されて複数の直列
接続されたパイプライン第１演算セグメントを備え、さ
らに第１の最終パイプラインレジスタを含み、パイプラ
インセグメントが存在する数と同数の第１の関数が処理
可能であり、各周期信号が各部分的に解決される第１の
関数項を次に直列接続されたパイプラインセグメントに
進め、さらに前記第１の最終パイプラインレジスタの出
力が前記第１のパイプライン演算装置の出力とされるも
のと；第２の関数（ｇ）を実行するための第２のパイプ
ライン演算装置であって、２つの入力と１つのデータ出
力とさらに複数の直列接続されたパイプライン第２演算
セグメントを備え、第２の最終パイプラインレジスタを
含み、さらにパイプラインセグメントが存在する数と同
数の第２の関数が処理可能であり、各周期信号が各部分
的に解決された第２の関数項を次に直列接続されたパイ
プラインセグメントに進め、さらに前記第２の最終パイ
プラインレジスタの出力が前記第２のパイプライン演算
装置のデータ出力とされるものと；からなり、前記パイ
プライン第１の演算装置と前記第２のパイプライン演算
装置が、前記第１の最終パイプラインレジスタの出力が
前記第２のパイプライン演算装置の入力の１つに接続さ
れるように相互接続され；前記第２の最終パイプライン
レジスタの出力が前記第２のパイプライン演算装置の他
方に入力に接続されて前記インターリーブド演算装置の
出力ともされ；さらに、前記パイプラインレジスタが前
記周期的に信号を受信するための手段に応答するように
接続されることを特徴とする、インターリーブド演算装
置。 - 【請求項１０】前記パイプラインレジスタが１つのコン
ピュータ格納装置内に配置されることを特徴とする、請
求項９に記載のインターリーブド演算装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US71107891A | 1991-06-06 | 1991-06-06 | |
| US07/711078 | 1991-06-06 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05197741A true JPH05197741A (ja) | 1993-08-06 |
Family
ID=24856684
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP17203392A Withdrawn JPH05197741A (ja) | 1991-06-06 | 1992-06-05 | インターリーブド乗算器累算器 |
Country Status (2)
| Country | Link |
|---|---|
| EP (1) | EP0517241A3 (ja) |
| JP (1) | JPH05197741A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010501938A (ja) * | 2006-08-18 | 2010-01-21 | クゥアルコム・インコーポレイテッド | マルチステージ浮動小数点アキュームレータ |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE69715570T2 (de) * | 1996-11-27 | 2003-08-07 | Texas Instruments Inc., Dallas | Multipliziereinheit |
| US5787273A (en) * | 1996-12-13 | 1998-07-28 | Advanced Micro Devices, Inc. | Multiple parallel identical finite state machines which share combinatorial logic |
| US5963460A (en) * | 1996-12-17 | 1999-10-05 | Metaflow Technologies, Inc. | Apparatus for computing transcendental functions quickly |
| US5889691A (en) * | 1997-01-06 | 1999-03-30 | Texas Instruments Incorporated | Apparatus and method for a multiplier unit with high component utilization |
| US6175911B1 (en) | 1998-08-21 | 2001-01-16 | Advanced Micro Devices, Inc. | Method and apparatus for concurrently executing multiplication and iterative operations |
| US6957327B1 (en) | 1998-12-31 | 2005-10-18 | Stmicroelectronics, Inc. | Block-based branch target buffer |
| EP1547253A1 (en) * | 2002-09-25 | 2005-06-29 | Koninklijke Philips Electronics N.V. | Circuit for recursively calculating data |
| US9558156B1 (en) * | 2015-11-24 | 2017-01-31 | International Business Machines Corporation | Sparse matrix multiplication using a single field programmable gate array module |
| US10489479B1 (en) * | 2016-09-12 | 2019-11-26 | Habana Labs Ltd. | Matrix multiplication engine |
| US11321092B1 (en) | 2017-11-08 | 2022-05-03 | Habana Labs Ltd. | Tensor-based memory access |
| US10915297B1 (en) | 2017-11-15 | 2021-02-09 | Habana Labs Ltd. | Hardware accelerator for systolic matrix multiplication |
| CN114115805B (zh) * | 2020-08-28 | 2025-06-06 | 广州希姆半导体科技有限公司 | 乘累加运算装置和乘累加运算方法 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2624283B1 (fr) * | 1987-12-08 | 1992-09-18 | Thomson Csf | Circuit integre de calcul numerique pour calculs glissants du type convolution |
| JP2690932B2 (ja) * | 1988-03-18 | 1997-12-17 | 株式会社日立製作所 | ディジタル信号処理プロセッサおよびディシタル信号処理プロセッサシステム |
-
1992
- 1992-06-05 JP JP17203392A patent/JPH05197741A/ja not_active Withdrawn
- 1992-06-05 EP EP19920109537 patent/EP0517241A3/en not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010501938A (ja) * | 2006-08-18 | 2010-01-21 | クゥアルコム・インコーポレイテッド | マルチステージ浮動小数点アキュームレータ |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0517241A2 (en) | 1992-12-09 |
| EP0517241A3 (en) | 1993-06-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11137983B2 (en) | Programmable device implementing fixed and floating point functionality in a mixed architecture | |
| US5844830A (en) | Executing computer instrucrions by circuits having different latencies | |
| US7043520B2 (en) | High-speed/low power finite impulse response filter | |
| EP0924601B1 (en) | Parallel data processing in a single processor | |
| US5790446A (en) | Floating point multiplier with reduced critical paths using delay matching techniques | |
| EP0466997A1 (en) | Improved digital signal processor architecture | |
| US4156922A (en) | Digital system for computation of the values of composite arithmetic expressions | |
| EP0186958A2 (en) | Digital data processor for matrix-vector multiplication | |
| JPH05197741A (ja) | インターリーブド乗算器累算器 | |
| EP2140345A1 (en) | Multiply and multiply- accumulate unit for signed and unsigned operands | |
| Soniya | A review of different type of multipliers and multiplier-accumulator unit | |
| US4802111A (en) | Cascadable digital filter processor employing moving coefficients | |
| US4799182A (en) | Cellular floating-point serial pipelined multiplier | |
| US4860240A (en) | Low-latency two's complement bit-serial multiplier | |
| US8577952B2 (en) | Combined binary/decimal fixed-point multiplier and method | |
| Chowdari et al. | Realization of multiplexer logic-based 2-D block FIR filter using distributed arithmetic | |
| Campbell et al. | Resource and delay efficient matrix multiplication using newer FPGA devices | |
| KR100481586B1 (ko) | 모듈러 곱셈 장치 | |
| US5457646A (en) | Partial carry-save pipeline multiplier | |
| Jiang et al. | Parallelized radix-2 scalable Montgomery multiplier | |
| Verma et al. | A Comparative Study of Wallace Tree Multiplier and Binary Multiplier Performance | |
| Smith et al. | Radix-4 modules for high-performance bit-serial computation | |
| Piestrak et al. | Architecture of efficient RNS-based digital signal processor with very low-level pipelining | |
| US5119325A (en) | Multiplier having a reduced number of partial product calculations | |
| Gopi et al. | 128 Bit unsigned multiplier design and implementation using an efficient SQRT-CSLA |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19990831 |