JPS60175181A - 並列内積演算方式 - Google Patents
並列内積演算方式Info
- Publication number
- JPS60175181A JPS60175181A JP2948684A JP2948684A JPS60175181A JP S60175181 A JPS60175181 A JP S60175181A JP 2948684 A JP2948684 A JP 2948684A JP 2948684 A JP2948684 A JP 2948684A JP S60175181 A JPS60175181 A JP S60175181A
- Authority
- JP
- Japan
- Prior art keywords
- multiplier
- inner product
- product
- calculation
- circuit
- 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.)
- Granted
Links
Classifications
-
- 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
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computational Mathematics (AREA)
- Computing Systems (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の技術分野〕
仁の発明は並列データ処理装置を用いて高速に内積計算
を行う演算方式に関するものである。
を行う演算方式に関するものである。
Ｃ従来技術〕
従来のこの種の内積計算を行う演算方式には加算機能を
含んだ９組合せ回路による乗算器を、複数組み合わせた
回路を用いる方法がある。今、説明のためにこれらの機
能を持った乗算器として配列型乗算器を考察する。第１
図に示す回路（１］は全加算器（Ｆｕｌｌ Ａｄｄｅｒ
’）であり、入力Ｘｓ ７ｅ Ｅｌ出力ｓ、ｃに関し
次の機能を与える。
含んだ９組合せ回路による乗算器を、複数組み合わせた
回路を用いる方法がある。今、説明のためにこれらの機
能を持った乗算器として配列型乗算器を考察する。第１
図に示す回路（１］は全加算器（Ｆｕｌｌ Ａｄｄｅｒ
’）であり、入力Ｘｓ ７ｅ Ｅｌ出力ｓ、ｃに関し
次の機能を与える。
θ−Ｘ■ｙ■２
０ ！ ｘ−ｙ’＋ｙ−ｇ ＋ Ｚ−Ｘ但し■は排他的
論理和を、・は陶理積を、＋は痢埋和を表わす。この全
加算器（１）を第２図に示す様に規則・的に配置するこ
とにより配列型乗算器が構成される。すなわち第２図中
１回路（２１から回路（２〃はすべて第１図の全加算器
（１）と同様の回路である。
論理和を、・は陶理積を、＋は痢埋和を表わす。この全
加算器（１）を第２図に示す様に規則・的に配置するこ
とにより配列型乗算器が構成される。すなわち第２図中
１回路（２１から回路（２〃はすべて第１図の全加算器
（１）と同様の回路である。
ここで符号を含まない２進数を〔〕２
”ｎ−ｌＸｎ−２°°°ＸＯ
と表わすことにする。すなわち。
［Ｘｎ−Ｉ Ｉｎ−２・・’ Ｘｇ ］２＝ Ｘｎ−Ｉ
Ｘ ２ ｎ−’ ＋ Ｉｎ−２Ｘ ２°−２＋・・・
＋ｘ ｏＸ２°−Σｘ１２１ となる。この表わし方に基づくと、第２図の乗算器は。
Ｘ ２ ｎ−’ ＋ Ｉｎ−２Ｘ ２°−２＋・・・
＋ｘ ｏＸ２°−Σｘ１２１ となる。この表わし方に基づくと、第２図の乗算器は。
被乗数 Ａ ” Ｃａ 、Ｓ ａ ２ ＆１ａ ｏ ］
２２乗数 Ｂ！〔ｂ３ｂ２ｂ１ｂｏ］２ 加算される数 Ｐ＝ｒｐ７ｐ６ｐ５ｐ４ｐ、、ｐ２ｐ１
ｐ□）２Ｑ−ｒｑ、、ｑ２ｑ１ｑｏ）２ 結果 Ｒ” 〔ｒＢｒ ７ｒ６ｒ５ｒ４ｒ４５ｒ２ｒ１
ｒｇ１２を用いて Ｒ謬ＡＢ＋Ｐ＋Ｑ となる。すなわち、全加算器回路（２１〜ａηには、被
乗数１乗数から作成される部分積が各々人力されてお勺
、各全加算器からの和（Ｓ）１桁上げ（０）を順次伝播
し、積をめている。なお全加算器０８〜ｒ２υでは部分
積の入力はなく、最終的な積をめるための桁上げ伝播の
みを行っている。また全加算器（２１〜（５１，＋６１
． ｆｌＱ、 （１４１，（ｌｉｅには、上段からの和
（Ｓ）１桁上げ（ｃ）が存在しないため、加算される数
Ｐ、 Ｑが各桁に合わせて入力される。さて、この配列
型乗算器を用いて内積計算を行うことを考えるために。
２２乗数 Ｂ！〔ｂ３ｂ２ｂ１ｂｏ］２ 加算される数 Ｐ＝ｒｐ７ｐ６ｐ５ｐ４ｐ、、ｐ２ｐ１
ｐ□）２Ｑ−ｒｑ、、ｑ２ｑ１ｑｏ）２ 結果 Ｒ” 〔ｒＢｒ ７ｒ６ｒ５ｒ４ｒ４５ｒ２ｒ１
ｒｇ１２を用いて Ｒ謬ＡＢ＋Ｐ＋Ｑ となる。すなわち、全加算器回路（２１〜ａηには、被
乗数１乗数から作成される部分積が各々人力されてお勺
、各全加算器からの和（Ｓ）１桁上げ（０）を順次伝播
し、積をめている。なお全加算器０８〜ｒ２υでは部分
積の入力はなく、最終的な積をめるための桁上げ伝播の
みを行っている。また全加算器（２１〜（５１，＋６１
． ｆｌＱ、 （１４１，（ｌｉｅには、上段からの和
（Ｓ）１桁上げ（ｃ）が存在しないため、加算される数
Ｐ、 Ｑが各桁に合わせて入力される。さて、この配列
型乗算器を用いて内積計算を行うことを考えるために。
例として下記の内積を扱う。すなわち請求める内積を８
とする′と。
とする′と。
Ｂ −ＡＢ ＋ ＣＤ ＋ ＥＦ ＋ ＧＨ・・・・・
・■但し Ａ ” ＣＦＬｓ ＆２＆１ａｏ］２Ｂ ＝
Ｃｂｓ ｂ２１）１ ｂｏ ］２Ｃ−ＣＣ、％ Ｃ２
Ｃ１Ｑ ｏ ］ ２Ｄ −Ｃｄ ｙ、ｄ ２ ｄ、ｄ
ｏ ）２トＣｅ ｓ ｅ ２ ｅ１１３ ｏ ］ Ｆ
”” Ｃｆ ３ ｆ ２ ｆｌ ｆ ｏ ］２Ｇ−１”
ｇ３ｇ２ｇ１ｇｏ１２． ｎ＝［ｈ３ｈ２ｈ１ｈｏ）２
Ｂ ”” （８９８６８７Ｅ１６８５’８４１ｉ１３８
２８１８０）２この場合には第２図に示す配列型乗算器
τ４個用意する。まず第１の乗算器の乗数、被乗数とし
てＡ、Ｂを入力し加算される故に対応する部分に０を入
力する。すなわち、第１の乗算器の出力には積ＡＢが得
られる。次に第２の乗算器の乗数、被乗数としてＯ，Ｄ
を入力し、加算される数に対応する部分に第１の乗算器
の出力を入力する。第２図の例で示した様に、この加算
される数にはＰ。
・■但し Ａ ” ＣＦＬｓ ＆２＆１ａｏ］２Ｂ ＝
Ｃｂｓ ｂ２１）１ ｂｏ ］２Ｃ−ＣＣ、％ Ｃ２
Ｃ１Ｑ ｏ ］ ２Ｄ −Ｃｄ ｙ、ｄ ２ ｄ、ｄ
ｏ ）２トＣｅ ｓ ｅ ２ ｅ１１３ ｏ ］ Ｆ
”” Ｃｆ ３ ｆ ２ ｆｌ ｆ ｏ ］２Ｇ−１”
ｇ３ｇ２ｇ１ｇｏ１２． ｎ＝［ｈ３ｈ２ｈ１ｈｏ）２
Ｂ ”” （８９８６８７Ｅ１６８５’８４１ｉ１３８
２８１８０）２この場合には第２図に示す配列型乗算器
τ４個用意する。まず第１の乗算器の乗数、被乗数とし
てＡ、Ｂを入力し加算される故に対応する部分に０を入
力する。すなわち、第１の乗算器の出力には積ＡＢが得
られる。次に第２の乗算器の乗数、被乗数としてＯ，Ｄ
を入力し、加算される数に対応する部分に第１の乗算器
の出力を入力する。第２図の例で示した様に、この加算
される数にはＰ。
Ｑ、２個の数が存在するが、第２の乗算器においてはＰ
側を使用し、Ｑ側は０とする。この結果第２の乗算器の
出力には ＡＢ ＋ ＣＤ が得られる０第３．第４の
乗算器についても同様に各々第２゜第３の乗算器の出力
結果を加算される数として入力し、被乗数９乗数を各々
Ｅと？、 ＧとＨとすれば第４の乗算器の出力としてめ
る内積Ｓが侍られる。
側を使用し、Ｑ側は０とする。この結果第２の乗算器の
出力には ＡＢ ＋ ＣＤ が得られる０第３．第４の
乗算器についても同様に各々第２゜第３の乗算器の出力
結果を加算される数として入力し、被乗数９乗数を各々
Ｅと？、 ＧとＨとすれば第４の乗算器の出力としてめ
る内積Ｓが侍られる。
さて以上述べてきた様に第２図に示す配列型乗算器をめ
る内積の積項の数だけ用意し、それらを相互に接続すれ
ば内積計算を行う演算回路は得られる。しかしながら、
これらには次に示す欠点がある。例として、上記の０式
で表わされるデータ長がすべて４ビツトで、データ数が
８１固（積項の数は４個）の場合を考察する。
る内積の積項の数だけ用意し、それらを相互に接続すれ
ば内積計算を行う演算回路は得られる。しかしながら、
これらには次に示す欠点がある。例として、上記の０式
で表わされるデータ長がすべて４ビツトで、データ数が
８１固（積項の数は４個）の場合を考察する。
（１） データ長が１つでも４ビツトを越えるものが存
在した場合、求めるべき内積のデータを４ビツトごとに
分割して何度も第２図の乗算器を使用することになり、
データの取シ出し、データのセットなど無駄な時間を必
要とする。
在した場合、求めるべき内積のデータを４ビツトごとに
分割して何度も第２図の乗算器を使用することになり、
データの取シ出し、データのセットなど無駄な時間を必
要とする。
（２１逆にデータ長が１例えばすべて２ビツトと半分の
長さであっても、データ数は８個に限定され１乗算器の
半分は未使用となる。すなわち使用効率が悪くなる。
長さであっても、データ数は８個に限定され１乗算器の
半分は未使用となる。すなわち使用効率が悪くなる。
以上の点は１乗算器が配列型乗算器の場合だけで 。
なく、任意の組合せ回路による乗算器に関して註えるこ
とである。
とである。
この発明はこれらの欠点を解決するためになされたもの
で、以下に定義する並列データ処理装置を用いて任意の
データ長の任意個の積項から成る内積計算を高速に行え
る演算方式を提供するものである。
で、以下に定義する並列データ処理装置を用いて任意の
データ長の任意個の積項から成る内積計算を高速に行え
る演算方式を提供するものである。
以下この発明の実施例を図面に示し詳細にＮ５！明する
。
。
まずこの発明で使用する並列データ処理装置を定義する
。第３図はこの発明の実施例による演算要素（２）を示
し、以下この演算要素−をセルと呼ぶ。
。第３図はこの発明の実施例による演算要素（２）を示
し、以下この演算要素−をセルと呼ぶ。
セル婚の仕様は次の通りである〇
入カニ ｓｉｎ ｌ ａ１＠ ｂｊ ” ｉｎ （各１
ビツト）出カニ５ａｂｃ（各１ビツト） ｏｕｔ’ ｉ’ ｊ’ ｏｕｔ 内部レジしシフ Ｆ （１ビツトレジスタ）機能： ｉ
ｆ Ｆ−ＯｔｈθｎＢｏｕｔ←８ｉｎ■’１ｎｏｕｔ
ｉｎ １ｎ ａｌｏａｌ ｊ ｉｆ Ｆ−１ｔｈｅｎ ８ｏｕｔ＋−８ｉｎ■ｃｉｎ■
ａ１・ｂｊＣＯｕｔ ’７８ｉｎ”ｉｎ”ｉｎ″２Ｌ１
°ｂｊ＋０ｉｎ”ｉ°ｂ＋＋ ａｌｏａｌ １）ｊ４− ｂｊ 但しθ、・、＋は前述と同様である。
ビツト）出カニ５ａｂｃ（各１ビツト） ｏｕｔ’ ｉ’ ｊ’ ｏｕｔ 内部レジしシフ Ｆ （１ビツトレジスタ）機能： ｉ
ｆ Ｆ−ＯｔｈθｎＢｏｕｔ←８ｉｎ■’１ｎｏｕｔ
ｉｎ １ｎ ａｌｏａｌ ｊ ｉｆ Ｆ−１ｔｈｅｎ ８ｏｕｔ＋−８ｉｎ■ｃｉｎ■
ａ１・ｂｊＣＯｕｔ ’７８ｉｎ”ｉｎ”ｉｎ″２Ｌ１
°ｂｊ＋０ｉｎ”ｉ°ｂ＋＋ ａｌｏａｌ １）ｊ４− ｂｊ 但しθ、・、＋は前述と同様である。
すなわち、Ｆレジスタ（２）が制御レジスタの役割を行
い、もしこの値が％ ｇ ／／ならば＋ ａ１＊ １）
ｊの値を素通シさせると共に８□□とＣ１ユのデータの
加算を行う。またもし１１Ｎならばａｌｌ １）１の値
の素通りと共に８□。、ｃｉ。、ａｌ・ｂｊ の値の加
算を行う。その結果は各々その和が８゜ｕｔに９桁上げ
がＣ０ｕｔに出力される。
い、もしこの値が％ ｇ ／／ならば＋ ａ１＊ １）
ｊの値を素通シさせると共に８□□とＣ１ユのデータの
加算を行う。またもし１１Ｎならばａｌｌ １）１の値
の素通りと共に８□。、ｃｉ。、ａｌ・ｂｊ の値の加
算を行う。その結果は各々その和が８゜ｕｔに９桁上げ
がＣ０ｕｔに出力される。
さて このセル＠を２次元格子状に配置することによシ
この発明の実施例で使用する並列データ処理装置を構成
できる。この例を第４図に示す。
この発明の実施例で使用する並列データ処理装置を構成
できる。この例を第４図に示す。
第４図はセル（ハ）を６Ｘ６個配置した場合を表わして
いる。す、なわちセルＱ４〜セル（ｓ９）山 セル（２
１と同一のものである。
いる。す、なわちセルＱ４〜セル（ｓ９）山 セル（２
１と同一のものである。
以下、このようなセル（至）を２次元配置した屈列デー
タ処理装置を用いて内積をめる方法を述べるＯ まず、第２図の配列型乗算器の変形を考察する。
タ処理装置を用いて内積をめる方法を述べるＯ まず、第２図の配列型乗算器の変形を考察する。
すなわち、第２図中 全加算器（２１〜顛は同一データ
を同一方向に伝播させるが、全加算器側〜Ｑυはその桁
上けｃｉ左方向に伝播する。この全加算器ｆｌ１１−；
ｔ９υを全加算器（２１〜（Ｉ７１と同様に左下方向
に桁上げを伝播させる憾に変形した乗算器紫紺５図に示
す０ 第５図において、全加算器（６０）〜（７５）間の接続
は、第２図の全加算器（２）〜旺η間の接続と同じであ
る。全加算器（７６）−（８９）は、第２図の全加算器
ｔＵｔ〜Ｉ２Ｄ間の接続を他の全加算器（２１〜顛間の
接続と同一となる様に変形したためにっけ加わったもの
である。（但し１図中入力が誉かれていない所は◎７
の入力とする。） さてｖ、５図を構成する全加算器に若干の変形を加える
０まず１部分積の入力が全加算器（６ｏ）〜（７５）で
行われていたが、これらの値を外部から行える様にする
◇すなわち１例えば全加算器（６ｏ）〜（ＩＳ？りには
共通にす。という値が入力されているため。
を同一方向に伝播させるが、全加算器側〜Ｑυはその桁
上けｃｉ左方向に伝播する。この全加算器ｆｌ１１−；
ｔ９υを全加算器（２１〜（Ｉ７１と同様に左下方向
に桁上げを伝播させる憾に変形した乗算器紫紺５図に示
す０ 第５図において、全加算器（６０）〜（７５）間の接続
は、第２図の全加算器（２）〜旺η間の接続と同じであ
る。全加算器（７６）−（８９）は、第２図の全加算器
ｔＵｔ〜Ｉ２Ｄ間の接続を他の全加算器（２１〜顛間の
接続と同一となる様に変形したためにっけ加わったもの
である。（但し１図中入力が誉かれていない所は◎７
の入力とする。） さてｖ、５図を構成する全加算器に若干の変形を加える
０まず１部分積の入力が全加算器（６ｏ）〜（７５）で
行われていたが、これらの値を外部から行える様にする
◇すなわち１例えば全加算器（６ｏ）〜（ＩＳ？りには
共通にす。という値が入力されているため。
この外部人力を全加算器（６ｏ）に与え、他の全加算器
（６１）〜（６３）への入力は、１＠に左方からセル間
を伝播させて行う。次に部分積の入力を必要とする全加
算器（６０）〜（７５）と必要としない全加算器（７６
）〜（８９）とを区別するため、１ビツトの制御レジス
タ（以後、Ｆレジスタと呼ぶ）を設ける。すなわちこの
ＦレジスタがＩ１１＃ならば頓に隣接する今加′算器か
ら送られてぐる入力データがら部分積を作成して加算を
施し、Ｆレジスタが％ｏ〃ならば９部分積の作成は行わ
ない様にする。
（６１）〜（６３）への入力は、１＠に左方からセル間
を伝播させて行う。次に部分積の入力を必要とする全加
算器（６０）〜（７５）と必要としない全加算器（７６
）〜（８９）とを区別するため、１ビツトの制御レジス
タ（以後、Ｆレジスタと呼ぶ）を設ける。すなわちこの
ＦレジスタがＩ１１＃ならば頓に隣接する今加′算器か
ら送られてぐる入力データがら部分積を作成して加算を
施し、Ｆレジスタが％ｏ〃ならば９部分積の作成は行わ
ない様にする。
以上の点を全加算器に付加すると、第３図のセル＠が得
られる。またこのセル＠を第５図の乗算器の全加算器と
置き換えることにより、第６図の乗算器が得られる。但
し、以後の説明のため第６図では第５図の乗算器全体を
４５０時計方向と反対に回転させて図示しである。また
各セル間の接続は使用するラインのみを明記している。
られる。またこのセル＠を第５図の乗算器の全加算器と
置き換えることにより、第６図の乗算器が得られる。但
し、以後の説明のため第６図では第５図の乗算器全体を
４５０時計方向と反対に回転させて図示しである。また
各セル間の接続は使用するラインのみを明記している。
更に外部入力として明記されていない所はｖｋＯ〃入力
と仮定する。
と仮定する。
このように変形することにより、第４図に示した並列デ
ータ処理装置を９Ｘ９個のセルから成る様にした場合、
その内部に第６図の４ビツト乗算器を見い出すことがで
きる。すなわち、第４図７更に大きく１例えば２１Ｘ２
１個のセルから成る様にすれば、４１１ｆｆｉの４ビツ
ト乗算器を構成することがで永、先に式■で示した内積
計算が可能となる。
ータ処理装置を９Ｘ９個のセルから成る様にした場合、
その内部に第６図の４ビツト乗算器を見い出すことがで
きる。すなわち、第４図７更に大きく１例えば２１Ｘ２
１個のセルから成る様にすれば、４１１ｆｆｉの４ビツ
ト乗算器を構成することがで永、先に式■で示した内積
計算が可能となる。
この詳細については具体例を用いて後に述べる。
次にＦレジスタの使い方について説明する０今。
４ビツト乗算器単体として、第６図の乗算器を扱う場合
は、セル（９０）〜（１１９）すべてのＦレジスタを鵞
１Ｎとしておいて問題ない（なぜなら１部分積が必要な
いセルには１０１が入力されているためである）０とこ
ろが後述する様に、並列データ処理装置上に複数の乗算
器が存在する場合には、セル（９０）〜（１ｏｓ）のＦ
レジスタを１１′＃とじ、他のセル（１０６）〜（１１
９）はすべてＦレジスタをゝ０”としなければならない
。なぜなら、セル（９０）〜（１ＯＳ）の機能は入力の
６□。”ｉｎと共にその部分積のａｉｂｊを加算するこ
とであるが、セル（１０６）〜（１１９）の機能は他の
セルで作成された’ｉｎ”ｉｎだけを順次加算していく
ことである。もし、Ｆレジスタが１１〃になっていると
、関係のない部分積を作成し加算を行い９間違った結果
を出すことになる。例えば。
は、セル（９０）〜（１１９）すべてのＦレジスタを鵞
１Ｎとしておいて問題ない（なぜなら１部分積が必要な
いセルには１０１が入力されているためである）０とこ
ろが後述する様に、並列データ処理装置上に複数の乗算
器が存在する場合には、セル（９０）〜（１ｏｓ）のＦ
レジスタを１１′＃とじ、他のセル（１０６）〜（１１
９）はすべてＦレジスタをゝ０”としなければならない
。なぜなら、セル（９０）〜（１ＯＳ）の機能は入力の
６□。”ｉｎと共にその部分積のａｉｂｊを加算するこ
とであるが、セル（１０６）〜（１１９）の機能は他の
セルで作成された’ｉｎ”ｉｎだけを順次加算していく
ことである。もし、Ｆレジスタが１１〃になっていると
、関係のない部分積を作成し加算を行い９間違った結果
を出すことになる。例えば。
セル（１０６）の左端から他のオペランドであるｅ。
という値が入力されており、これは順次セル（１０６）
→（１０７） −＊ （１ｏｓ）→（１ａｔｐ） と伝
播され、その右側の他の乗算器のセルで使用される値と
する（当然データ入力は端から行われるため、この様な
事は起こり得る）。その場合その乗算における部分積と
ハ、無関係なセル（１０６）〜（１０９）で？レジスタ
が１１＃となっていると、各々間違った部分積ａ３９ｇ
＠ａ２ｅ（１ｇ ａ１ｅｏ＋ ａ（１θ。を作成し加算
してしまうことになる。
→（１０７） −＊ （１ｏｓ）→（１ａｔｐ） と伝
播され、その右側の他の乗算器のセルで使用される値と
する（当然データ入力は端から行われるため、この様な
事は起こり得る）。その場合その乗算における部分積と
ハ、無関係なセル（１０６）〜（１０９）で？レジスタ
が１１＃となっていると、各々間違った部分積ａ３９ｇ
＠ａ２ｅ（１ｇ ａ１ｅｏ＋ ａ（１θ。を作成し加算
してしまうことになる。
すなわち、Ｆレジスタを％１Ｎとするセルは、その乗算
にとって必要な被乗数、乗数が送られてくるセルのみで
ある。
にとって必要な被乗数、乗数が送られてくるセルのみで
ある。
次にこの発明の実施例における並列データ処理装置を用
いた並列内積演算方式を具体例を用いて説明する。内積
演算の対象に＃−ｔ、先の式■で表わされたものを用い
る。第７図にこの発明の実施例で使用する並列データ処
理装置の使用例を示す。
いた並列内積演算方式を具体例を用いて説明する。内積
演算の対象に＃−ｔ、先の式■で表わされたものを用い
る。第７図にこの発明の実施例で使用する並列データ処
理装置の使用例を示す。
各点線で囲まれているのが第３図のセル（至）であり。
セル数は２１ Ｘ ２１個の場合を表わしている。なお
セル間接続は省略しであるが、第４図のセル［有］〜（
５９）のようにすべてのセルが隣接するセルと接続され
ている。また、データの入力は上端訃よび左端から行わ
れ、内積の結果は右下端から出力される。但し明記され
ていないデータ入力はすべて１０”とする。また斜線を
施したセルに対しのみＦレジスタを１１＃とじ、他のセ
ルはすべて′ＯＮとする。各乗算の機能を果たすものは
９図中、太い実線で囲んだ乗算回路（１２０）〜（１２
３）である。
セル間接続は省略しであるが、第４図のセル［有］〜（
５９）のようにすべてのセルが隣接するセルと接続され
ている。また、データの入力は上端訃よび左端から行わ
れ、内積の結果は右下端から出力される。但し明記され
ていないデータ入力はすべて１０”とする。また斜線を
施したセルに対しのみＦレジスタを１１＃とじ、他のセ
ルはすべて′ＯＮとする。各乗算の機能を果たすものは
９図中、太い実線で囲んだ乗算回路（１２０）〜（１２
３）である。
まず乗算回路（１２０）について考察を加える。これは
第６図に示す回路とまったく同様である（但しＰ、Ｑｉ
Ｌ’Ｏ〃である）０すなわち１乗算回路（１２０）の右
端からは、＊乗数Ａ１乗数Ｂの積ＡＢが出力される。先
に示した様に左端入力のｄ。〜ｄ、、 、 ｆｏの影響
をなくすため、上方の４Ｘ４のセルのみがＦレジスタに
１１１が設定されている。乗算回路（１２１） も乗算
回路（１２０）と同様の回路であるが、積ＣＤをめると
同時に左方から乗算回路（１２０）の出力１積ＡＢが送
られてくるため、これらの和ＩＡＢ＋ＣＤが右方から出
力される。乗算回路（１２２）〜（１２−ｑ）に関して
もまったく同様であり。
第６図に示す回路とまったく同様である（但しＰ、Ｑｉ
Ｌ’Ｏ〃である）０すなわち１乗算回路（１２０）の右
端からは、＊乗数Ａ１乗数Ｂの積ＡＢが出力される。先
に示した様に左端入力のｄ。〜ｄ、、 、 ｆｏの影響
をなくすため、上方の４Ｘ４のセルのみがＦレジスタに
１１１が設定されている。乗算回路（１２１） も乗算
回路（１２０）と同様の回路であるが、積ＣＤをめると
同時に左方から乗算回路（１２０）の出力１積ＡＢが送
られてくるため、これらの和ＩＡＢ＋ＣＤが右方から出
力される。乗算回路（１２２）〜（１２−ｑ）に関して
もまったく同様であり。
結局９乗算回路（１２υからはめるべき内積ＡＢ ＋
ＣＤ ＋ ＫＦ ＋ ＧＨが出力され、これが残りのセ
ルを伝播していき、最終的に第７図の並列データ処理装
置の右下から出力されることになる。
ＣＤ ＋ ＫＦ ＋ ＧＨが出力され、これが残りのセ
ルを伝播していき、最終的に第７図の並列データ処理装
置の右下から出力されることになる。
以上の説明は、４ピツトの数の８ ｊｌｉ！ａのデータ
に対する内積計算の例であるが、この発明の並列内積演
算方式では、容易にこのデータ長とデータの故を変更す
ることができる。すなわち、並列データ処理装置の各セ
ル内のＦレジスタを操作することにより、任意のデータ
長の任意量の積項から成る内積演算が行える。これによ
シ従来の固定されていたデータ長とデータ故の内積演算
回路の制限をｈＢ除くことができ、柔軟性に富んだ内積
演算回路を構成することができる。
に対する内積計算の例であるが、この発明の並列内積演
算方式では、容易にこのデータ長とデータの故を変更す
ることができる。すなわち、並列データ処理装置の各セ
ル内のＦレジスタを操作することにより、任意のデータ
長の任意量の積項から成る内積演算が行える。これによ
シ従来の固定されていたデータ長とデータ故の内積演算
回路の制限をｈＢ除くことができ、柔軟性に富んだ内積
演算回路を構成することができる。
以上説明した様にこの発明に係る並列内積演算方式によ
れば、全加算器と、入力ＡＮＤ要素及びその全加算器の
入力を制御する制御レジスタとを所有した演算要素を複
数個２次元格子状に配置して゛並列データ処理装置を構
成し、制御レジスタがセットされた演算要素でＡＮＤ演
算並びに全加算を行なうとともに、セットされない演算
要素で半加算を行なうことにより、任意のビット長を持
った任意の個数のデータの内積をめることができる。
れば、全加算器と、入力ＡＮＤ要素及びその全加算器の
入力を制御する制御レジスタとを所有した演算要素を複
数個２次元格子状に配置して゛並列データ処理装置を構
成し、制御レジスタがセットされた演算要素でＡＮＤ演
算並びに全加算を行なうとともに、セットされない演算
要素で半加算を行なうことにより、任意のビット長を持
った任意の個数のデータの内積をめることができる。
第１図は全加算器（Ｆｕｌｌ Ａｄｄｅｒ ）を示す図
。 第２図は第１図の全加算器を用いた４ビット配列型乗算
器を示す図、第３図はこの発明の実施例で使用する並列
データ処理装置のセル構成図、第４図はこの発明の実施
例で使用するセル数６ Ｘ ６ ｇの並列データ処理装
置を示す図、第５図は第２図の配列型乗算器を変形した
乗算器を示す図、第６図は第５図の全加算器に付加機能
ｔつけ加えた乗算器を示す図、第７図はこの発明の実施
例による並列内積演算方式の使用例を説明するための説
明図である。 図中、（１）は全加算器、 １２１−１’２ａは配列型
乗算器で使用する全加痒器、１２３はＦレジスタ、ｌ’
２１は並列データ処理装置を構成するセル、＠〜（５９
）は並列データ処理装置内のセル、（６Ｏ）〜（８９）
は変形された、配列型乗算器内の全加算器＠ （９０）
〜（１１９）は乗算器を構成するセル、（１２０）〜（
１２３）は並列データ処理装置内の乗算回路である。 なお１図中同一符号は、同−又は相尚部分を示す。 出願人 工業技術院長 川田裕部 ”４ 第 ６ 図 手続補正誉（自発） 昭和どθ年ノ 月２３日 特許庁長官殿 １、弧件の表示 ％願昭５９−２９４８６号２ 発明ア
返称 並列内積演算方式 λ 補正をする者 明細書の発明の詳細な説明の欄 ５、補正の内容 ｆｉ＋ 明細書第３頁第１６行の「回路」を削除する０ ＋２）同第４貞第１６行の「入力し加算」す「入力し、
加算Ｊに補正する。 １３１ 同第１０頁第１９行の「すべて」ヲ「のすさて
」に補正する。
。 第２図は第１図の全加算器を用いた４ビット配列型乗算
器を示す図、第３図はこの発明の実施例で使用する並列
データ処理装置のセル構成図、第４図はこの発明の実施
例で使用するセル数６ Ｘ ６ ｇの並列データ処理装
置を示す図、第５図は第２図の配列型乗算器を変形した
乗算器を示す図、第６図は第５図の全加算器に付加機能
ｔつけ加えた乗算器を示す図、第７図はこの発明の実施
例による並列内積演算方式の使用例を説明するための説
明図である。 図中、（１）は全加算器、 １２１−１’２ａは配列型
乗算器で使用する全加痒器、１２３はＦレジスタ、ｌ’
２１は並列データ処理装置を構成するセル、＠〜（５９
）は並列データ処理装置内のセル、（６Ｏ）〜（８９）
は変形された、配列型乗算器内の全加算器＠ （９０）
〜（１１９）は乗算器を構成するセル、（１２０）〜（
１２３）は並列データ処理装置内の乗算回路である。 なお１図中同一符号は、同−又は相尚部分を示す。 出願人 工業技術院長 川田裕部 ”４ 第 ６ 図 手続補正誉（自発） 昭和どθ年ノ 月２３日 特許庁長官殿 １、弧件の表示 ％願昭５９−２９４８６号２ 発明ア
返称 並列内積演算方式 λ 補正をする者 明細書の発明の詳細な説明の欄 ５、補正の内容 ｆｉ＋ 明細書第３頁第１６行の「回路」を削除する０ ＋２）同第４貞第１６行の「入力し加算」す「入力し、
加算Ｊに補正する。 １３１ 同第１０頁第１９行の「すべて」ヲ「のすさて
」に補正する。
Claims (1)
- 【特許請求の範囲】 ＋ＩＪ 全加算器と、入力ＡＮＤ要素およびその全加算
器の入力を制御する少なくとも１ビツトの制御レジスタ
とを所有した演算要素を、複数個２次元格子状に配置し
、かつその隣接する演算要素どうしの入出力線を結合し
た並列データ処理装置であって請求めるべき内積の各積
項の乗数を左端から。 被乗数を上端から入力し、演算要素間で順にその値を伝
播させ、かつ、その各積項の乗数、被乗数が交わる演算
要素の各制御レジスタをセットし。 セットされた演算要素でＡＮＤ演算、並びに全加算を行
い、セットされていない演算要素では半加算を行い、そ
の結果の和は右下の演算要素に１桁上げは下方の演算要
素に送り、内積演算結果を並列データ処理装置の右下端
から出力させることによシ、任意長及び又は任意間のデ
ータの内積をめるようにしたことを特徴とする並列内積
演算方式。 （２）任意長、及び又は任意間のデータの内積を。 非同期にめるようにしたことを特徴とする特許請求の範
囲第１項記載の並列内積演算方式０
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2948684A JPH0246982B2 (ja) | 1984-02-21 | 1984-02-21 | Heiretsunaisekienzanhoshiki |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2948684A JPH0246982B2 (ja) | 1984-02-21 | 1984-02-21 | Heiretsunaisekienzanhoshiki |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60175181A true JPS60175181A (ja) | 1985-09-09 |
| JPH0246982B2 JPH0246982B2 (ja) | 1990-10-18 |
Family
ID=12277405
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2948684A Expired - Lifetime JPH0246982B2 (ja) | 1984-02-21 | 1984-02-21 | Heiretsunaisekienzanhoshiki |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0246982B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63225864A (ja) * | 1987-03-13 | 1988-09-20 | Fujitsu Ltd | 累積演算器 |
-
1984
- 1984-02-21 JP JP2948684A patent/JPH0246982B2/ja not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63225864A (ja) * | 1987-03-13 | 1988-09-20 | Fujitsu Ltd | 累積演算器 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0246982B2 (ja) | 1990-10-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR940002479B1 (ko) | 고속 디지탈 병렬승산기(multiplier) | |
| US8959134B2 (en) | Montgomery multiplication method | |
| Ma et al. | Multiplier policies for digital signal processing | |
| US8793300B2 (en) | Montgomery multiplication circuit | |
| US4639857A (en) | Digital data processor incorporating an orthogonally connected logic cell array | |
| JPH0456339B2 (ja) | ||
| US6202077B1 (en) | SIMD data processing extended precision arithmetic operand format | |
| JP2024509062A (ja) | シストリックアレイにおける乗算器および加算器 | |
| US6513054B1 (en) | Asynchronous parallel arithmetic processor utilizing coefficient polynomial arithmetic (CPA) | |
| JP3227538B2 (ja) | ２進整数乗算器 | |
| JPH0816903B2 (ja) | 積和演算回路 | |
| US5883825A (en) | Reduction of partial product arrays using pre-propagate set-up | |
| JP2600591B2 (ja) | 乗算器 | |
| CA1311062C (en) | Processor suitable for recursive computations | |
| Ferrer et al. | A fast finite field multiplier | |
| Zhu et al. | An area-time efficient architecture for 16 x 16 decimal multiplications | |
| JPH0246982B2 (ja) | Heiretsunaisekienzanhoshiki | |
| Mulkalapally et al. | High speed, area and power efficient 32-bit Vedic multipliers | |
| US6742011B1 (en) | Apparatus and method for increasing performance of multipliers utilizing regular summation circuitry | |
| Aggoun et al. | Bit-level pipelined digit-serial multiplier | |
| GB2166272A (en) | Serial multiplier circuit | |
| JP2812365B2 (ja) | 乗算回路 | |
| JP2607735B2 (ja) | 倍数器の部分積加算方法 | |
| JPH0784762A (ja) | 乗算回路 | |
| JP2025141401A (ja) | 行列演算回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |