JPH0312739B2

JPH0312739B2 -

Info

Publication number: JPH0312739B2
Application number: JP58139326A
Authority: JP
Inventors: Maikeru Kotsuton Jon
Original assignee: Alcatel NV
Current assignee: Alcatel Lucent NV
Priority date: 1982-08-02
Filing date: 1983-07-29
Publication date: 1991-02-20
Also published as: US4507748A; AR242865A1; NZ204954A; CA1194606A; KR840006089A; ATE48194T1; EP0100511A3; DE3380884D1; ES8500667A1; EP0100511A2; MX155395A; ZA834372B; PH20071A; ES524630A0; IN158682B; AU1737583A; KR910004308B1; EP0100511B1; JPS5943475A; BE897441A

Description

【発明の詳細な説明】

〔発明の技術分野〕この発明は、一般的に連想処理（associative
processing）に関するものであり、特にマスク制
御下で可変数長を有する高速乗算を行う連想処理
アレイに関するものである。この発明の連想処理
アレイはLSI（大規模集積回路）或はVLSI（超大
規模集積回路）形式で使用すると特に有利であ
り、それにおいては回路量およびピン接続の数を
減少させることがこの発明のユニークな回路によ
つて達成される。マスク制御下に可変数長能力を有する前述の高
速乗算を行う連想プロセツサは連想処理コンピユ
ータ中で有用であるだけでなく、高速計算能力を
必要とするシステムにおいても一般に有用であ
る。そのようなシステムは例えばエンジニアワー
クステイシヨン、データーベースマネージメント
システム、位相数学的解析、グラフイツクデイス
プレイ、音声認識、合成開口、エコーおよび航跡
解析および追跡、テキスト編集システムおよびデ
ジタルろ波を含む通信等である。〔発明の技術的背景〕連想プロセツサは各単一セルがその近傍のセル
にのみアクセスする単一パスプロセツサのアレイ
と考えることができる。連想プロセツサは互に並
列のデータ流によりアクセスされることができ、
そのメモリは内容によつてアドレス可能であり、
データ構造はタグに基いている。通常のプロセツサは１時に１データアイテムで
順次動作するが、連想プロセツサは同時に多数の
データ対象で動作する。これが利用されるため
に、データ対象は個々の指令の何れに対しても同
じ形式のものでなければならず、それ故これらの
データ対象で同時に動作するために同じ順次指令
流を供給することは意味のあることである。この
クラスのプロセツサは単一指令多重データ
（Single Instruction Multiple Data以下SIMDと
いう）プロセツサとして知られている。連想プロセツサはLSI中に集積された単一ビツ
トコンピユータの方形アレイから構成することが
でき、例えばそれぞれ2K乃至64Kビツトのメモ
リを有することができる。これらのセルコンピユ
ータはそれぞれそれ自身のデータで動作する同じ
同時の指令に従つて行動する。セルはその四方全
部において近隣のセルおよび外部データ入力およ
び出力レジスタと相互通信することができる。連想プロセツサアレイの行中のセルは任意に定
められた長さ（アレイの幅の制限内）の任意の数
のフイールド中にダイナミツクに（１つの指令か
ら次の指令に）形成されることができる。各フイ
ールドはその時与えられたワード長の計算および
論理操作をすることのできる別々のコンピユータ
であるかのように独立に動作できる。これらのフ
イールドは全て同時に同じ指令に従つて行動し、
或はプログラム制御下に選択的に無能（disable）
にされることができる。真の効果はエネーブルにされた時に異なるデー
タアイテムで同時に同じ計算或は論理操作を行う
任意の定められたワード長の１組のコンピユータ
の効果である。このコンピユータの組はマトリツ
クス計算、代数、ベクトル計算、イメージ
（pixal）処理、およびサーチおよびパターン認識
問題および音声認識に必要な問題に適用されるこ
とができる。それらは任意所望の正確度で固定小
数点および浮動小数点計算の両者を行うことがで
きる。このプロセツサの組のスループツトはアレ
イの大きさ、フイールドの長さおよび数および特
定の動作のためにエネーブルにされるアレイの割
合に依存する。例えば10MHzのクロツクを同時に
使用する８ビツト数2048で動作する128×128セル
アレイは毎秒40億のオーダで加算或は論理操作お
よび毎秒10億のオーダの乗算を行うことが概算さ
れる。時には内容アドレス可能なメモリ（Content
Addressable Memory）と呼ばれる連想メモリ
は一般によく知られており、連想プロセツサにお
いて機能するように構成されており、それにおい
て計算操作は同時にメモリ中に蓄積された１以上
のデジタルワードで行われてもよい。そのような
連想プロセツサは米国特許第4068305号明細書に
記載されている。米国特許第4296475号明細書に
より示されているようなそのような内容アドレス
可能なメモリはワード組織され、メモリを使用す
るために必要な接続ピンの数を減少させることに
努力が拂われている。指令ワードの或るビツトと
前に割当てたフラグ（例えば状態フリツプ・フロ
ツプからの）との間の連想は、データプロセツサ
が１以上の連想ビツトを無視するように指令ワー
ド中のマスクビツトを与えることによつて条件的
に指令を実行するものであることが知られてい
る。このことは米国特許第4010452号明細書に記
載されている。米国特許第4044338号明細書には
分離された連想領域を有する連想メモリが記載さ
れている。各回路素子が連想アドレスを有するデ
ータバスへの回路素子の選択的結合は米国特許第
4188670号明細書に記載されている。米国特許第
4159538号明細書にはLSI連想メモリが示されて
おり、それにおいては多数のピン接続は入力デー
タ、出力データおよびマスク情報により或るパツ
ケージピンを共用することによつて減少されてい
る。直列にアクセスされる連想メモリは米国特許
第4153943号明細書に記載されている。［発明の解決すべき課題］この発明は、連想プロセスセルのアレイがマス
ク制御下に２進の２の補数のような数の可変長高
速乗算を行うように構成された連想プロセツサに
関するものであり、特に可変長高速乗算において
直列乗算が連想アレイ中のセルの位置に関係なく
得られるような連想プロセツサを提供することを
目的とするものである。［課題解決のための手段］この発明の可変長高速乗算能力を有する連想プ
ロセツサは、それぞれ和ビツトおよびキヤリビツ
トを同時に蓄積するように構成されているセルか
らなる連想セルの行および列に配列されたアレイ
を具備し、各セルは、１以上の特定のセルが乗数
或いは被乗数ビツトの何れか或はその組合せを有
していることを特定するためのマスキング手段
と、被乗数ビツトを蓄積する手段と、被乗数ビツ
トと乗数ビツトの乗算を行う手段と、前記セルが
乗算結果の２ビツトを蓄積するように乗算動作中
前記セルをエネーブルにする手段と、前のシフト
時間からの計算操作の結果にマスクされた被乗数
ビツトを加算或は減算して現在の乗算結果を出力
するために乗数ビツトを順次受信する計算論理ユ
ニツト手段と、乗数が隣接セル中で同時に生成さ
れる如く現在の乗算結果をその現在の結果が得ら
れるのと同じシフト時間に隣接する連想セルに結
合する手段とを具備し、この隣接連想セルへ前記
現在の乗算結果を結合する手段はセルが乗算動作
中にデイスエーブルにされた時にセルの入力出力
間にループバツク接続を設けるための手段を具備
し、それによつて直列乗算が連想アレイ中のセル
の位置に関係なく得られることを特徴とする。この発明は以下の実施例に示すように符号の付
された乗算に適した形態にすることができ、それ
においては全てのセルの処理シーケンスはセルが
アレイの行の端部にあつても中央にあつても、ま
た行われることが要求される計算シーケンスに関
係なく互に両立性である。連想セルの構造の１実
施態様においては、分離したキヤリと同時或は交
互にエネーブルにされ付勢される借りセーブパス
（borrow save pass）を有する改良された計算論
理ユニツトが含まれている。［発明の実施例］第１図を参照すると連想アレイ１００がその水
平および垂直マスクレジスタ１０２および１０４
と共に概略ブロツク図で示されている。マスクレ
ジスタ１０２および１０４はアレイ１００の部分
を選択的にエネーブルまたはデイスエーブルに
し、それによつて実効的にアレイ１００のどの区
域がアレイ制御装置１０６からの特定の指令に対
して動作するかを決定する。アレイ制御装置１０
６は適用プログラムを蓄積しマスク指令線１０８
を経てマスクレジスタ１０２および１０４に結合
され、アレイ指令線１１０を経てアレイ１００に
結合されるアレイ動作シーケンスとしてそれらを
ほん訳するためのプログラムされたおよび／また
はプログラム可能なメモリを有する任意の既知の
制御装置で構成することができる。代表的にはそ
のような40本の線１０８および40本の１１０がア
レイ中にあつてよい。線１０８上の指令はマスク
レジスタ１０２および１０４のためのマイクロプ
ログラム制御を行い、アレイアドレスをアドレス
レジスタ１１２に結合する。そのアドレスは後述
の第３図の２１２に示すアレイのセル毎に供給さ
れるメモリ用のアドレスである。線１１０上の指
令はアレイ１００のためのマイクロプログラム制
御を行う。線１０８および１１０上の指令の組合
せ効果はアレイおよびそのマスクレジスタに特定
の性質を有する記録のためにフアイルのサーチを
行わせ、次いでその記録の部分を或る係数で乗算
するために使用できる。連想アレイは連想プロセツサの副装置と考えて
もよく一般的には第２図に示されている。説明す
ると、アレイは20セル×４セルのマトリツクス２
０２からなり、そのセルの１つは２０４で示され
る。連想アレイは４ビツトの水平マスクレジスタ
２０６と、20ビツトの垂直マスクレジスタ２０８
と20ビツトの垂直入出力レジスタ２０９とを備え
ている。第３図を参照するとセル２０４のような単一の
連想セルが連想プロセツサの特徴に従つた構成で
示されている。アレイ２０２中の他の全てのセル
と同一であるセル２０４は１個のＡ型フリツプフ
ロツプ２１０と、８個のＭ型フリツプフロツプ
（２１２としてまとめて示されている）と、関連
する制御論理装置とを備えている。８個のＭ型フ
リツプフロツプはランダムにアクセスできるメモ
リを表わし、フリツプフロツプ２１２はメモリデ
ータレジスタビツトとして作用する。第８番のも
のだけが図示され、8000または64000のような任
意の番号にできる。計算論理ユニツト（以下
ALUと略称する）２１４は周知のように演算操
作を行い、通常の設計でよい。またデータ処理に
おいてよく知られているようにALU２１４が加
算器として使用される時線２１６上の和出力と線
２１８上のキヤリ出力とを有する。ALU２１４
が加算を行つている時、線２１６の和ビツトは選
択スイツチ２２２の入力ゲート２２０においてＡ
フリツプフロツプ２１０に戻すように供給され
る。加算時にキヤリビツトは選択スイツチ２２８
のゲート２２６を通つて低速出力（slow out）
線２２４に結合される。線２３０の高速入力（fast）はデータレジスタ
すなわちＡフリツプフロツプ２１０から選択ゲー
ト２３２へ接続され、例えばサーチのためにセル
のALU２１４部分へオペランドが供給されるこ
とを許容する。高速出力線は第２図のＩ／Ｏレジ
スタ２０９にALU２１４の計算結果を通過させ
るように接続されている。低速出力線は次のセル
へのキヤリまたはシフトビツトである。近傍のセ
ルからのデータ、キヤリ入力またはシフトされる
データの何れかは線２３４に結合される。垂直お
よび水平マスクレジスタ２０６および２０８はそ
れぞれセル２０４と類似した連想セルからなり、
第３図の接続２０５，２０７に接続されている。第４、第５および第６図は第４図で３００，３
０２および３０４として例示的に示したような多
数の同一ユニツトからなる直列並列乗算器の動作
を示す。フリツプフロツプ３０６，３０８および
３１０は被乗数を持つ。乗数は１ビツトづつ線３
１２の高速入力線に供給される。第４図は例えば
５ビツト乗算器の一部（３ユニツト）を示し、そ
の乗算器は第５図に示すように10ユニツトを必要
とする。乗算器ユニツト３０２の動作は次のとおりであ
る。乗数値は高速入力線３１２中に供給され、ゲ
ート３１４で被乗数のそこにあるビツトとアンド
処理され、その結果は加算器３１６への１入力と
して使用される。線３１８による加算器３１６の
第２入力は前のユニツトの低速出力から来るもの
であり、それは線３１２で乗算器からセル３００
中の乗算動作の前のビツトによる乗算動作の結果
を運ぶものである。加算器３１６の第３の入力は
乗算の前のステツプの計算結果の中からフリツプ
フロツプ３２０中に蓄積されたキヤリビツトから
なる。乗算のこのステツプにより行われた加算結
果の和およびキヤリはそれぞれフリツプフロツプ
３２２と３２０とに蓄積される。セル３００と３
０４の動作はセル３０２と同一である。第５図を参照すると直列並列乗算動作が５ビツ
トの被乗数が５ビツトの乗数と乗算される例示的
な乗算動作について記載されている。積は10ビツ
トになるであろう。第５図に示されたような10個
の乗算ユニツトは上述の乗算を行うことができ
る。 10個の乗算ユニツト１乃至１０の列が示されて
いるが、第５図のユニツト列のユニツト１乃至５
のようなそのようなユニツトの５個だけが５×５
の乗算を行うために必要であることに留意された
い。ユニツト６乃至１０は代りにシフトレジスタ
で置換されてもよい。直列計算動作において積ビ
ツトはそれらがユニツト５によに発生される速度
で利用することができる。第５図の各ユニツトは和ビツトＳおよびキヤリ
ビツトＣを同時に蓄積することができる。乗算の
各ステツプを行う時、各ユニツトはその和を右方
へ伝播する。各ユニツト中において入つて来る和
ビツトは第４図を参照して前に説明したように新
しい和ビツトおよび新しいキヤリビツトを生成す
るために存在しているキヤリビツトおよびそこに
ある被乗数と入来する乗数の論理結果と組合され
る。２進加算の結果である２進数は２行からなるも
のとして記載でき、１行は和ビツトを含み、他の
行はキヤリビツトを含んでいる。計算は２進数の
そのような表現で行うことができ、キヤリの最終
の吸収は和ビツトの単一の列からなる最終的な形
態における結果を生成することが必要である時ま
で遅延されることができる。この乗算技術は以下
に説明するような全てのキヤリが最終的に吸収さ
れる乗算の終りまで２進加算の２行表現の効果を
生じる。次の５×５の乗算の数字列は第６図を参照に記
載されている。 MC＝11011 MP＝01110 積は0101111010になる。第６図において乗算ユニツトの列が示されてお
り、それにおいて垂直列は10個の乗算ユニツト或
はその代りに５個の乗算ユニツト（ユニツト１乃
至５）と５段のシフトレジスタ（ユニツト６乃至
１０）の状態を表わしている。図は加算が各ユニ
ツト或は段によつてどのように行われるかを示し
ている。しかしながら５×５乗算に対しては加算
の特徴はユニツト６乃至１０では必要ないことを
理解すべきである。被乗数ビツトはユニツト１乃至５のＭフリツプ
フロツプ３５０，３５２，３５４，３５６，３５
８中に保持されている。これらの被乗数ビツトは
アンドゲート３６０，３６２，３６４，３６６，
３６８として示された各セル内のアンドゲートに
おいて乗数ビツトとアンド処理される。したがつ
て乗数ビツトは被乗数ビツトに対するマスクとし
て作用する。行Ａは乗算が開始される前の10個のユニツト全
部の状態を示す。なお各行の上の欄は左がキヤ
リ、右が和出力を示し、下の欄はアンド処理され
て入力された値を示す。和ビツトおよびキヤリビ
ツトは行Ａの全部のセルにおいてゼロである。行
Ａに示された第１の動作は全ユニツトに対して被
乗数を加えることである。乗数の最下桁のビツト
はゼロであるから、アンド処理の結果として行Ａ
における効果はすでに空であるユニツトに全てゼ
ロを加えることである。この結果は行Ｂに現れ
る。行Ｂ中で全てのキヤリおよび和ビツトは依然
としてゼロであることが認められる。行Ｂにおいて、再び各ユニツトの内容に被乗数
を加えることが所望され、この動作が行われた時
に乗数の最下桁の次のビツトが１であることを認
めることができる。被乗数ビツトは行Ｂの下の位
置に現われる。行Ｂの第１列に関しては１がゼロ
に加算されて行Ｃの第１列に和ビツト１を出力し
またキヤリビツト０を出力するのが認められる。
また行Ｂの第１列において「ゼロ」和「Ｓ」ビツ
トは行Ｂの第２列の「ゼロ」キヤリ「Ｃ」に加算
され、MCビツト「１」と共に和ビツト「１」お
よび行Ｃ第２列のキヤリビツト「０」を生成す
る。セレ中の矢印は各ユニツト中の加算器の動作
を示す。行Ｄにおいては乗数は再び「１」であり、動作
は行Ｃについて説明したのと同じである。行Ｅにおいては全ての「０」が再び各ユニツト
に加えられる。それは例に挙げた２進数では乗数
ビツトが再び「０」であるからである。行Ｅ中に
おいて全ての「０」を加算するのに費される処理
時間は無駄ではない。それは行Ｅにおいて最終の
乗算積を得るに必要であるキヤリビツトが右方へ
伝播されるからである。積ビツトが第５番のユニ
ツトにより発生されると直に使用される際に、行
Ｅにおけるゼロの加算はゼロの加算が行われるま
で積ビツトが「１」か「０」か判らないから必要
である。行Ｆは右方へのキヤリビツトの最終の伝播のた
めに必要である。以上は２進数11011×01110の乗
算によつて積0101111010を得るためのユニツトの
動作の１例である。第４図乃至第６図を参照した上述の直列並列乗
算はこの発明の連想プロセツサ用の連想セルの設
計に組込まれるべき乗算機構の基本である。乗算
だけのために設計された直列並列乗算器において
乗数値を乗算器ハードウエア中にシフトするため
および結果を取り出しそれをどこか他で利用する
ための配線パターンは特定されたサイズの乗算器
ハードウエアに対して予め決定される。この発明
のすぐれた特徴は、連想セルの行中の位置が変化
され、ソフトウエア或はメモリ内容のアクセスに
より決定されることができる選択できるオペラン
ド長の乗数および乗算結果に対する選択的パスの
構成に関係するものである。次に第７図を参照すると任意の或は可変長の乗
算装置のブロツク図が示されている。連想セル装
置を使用するそのような可変長乗算は特に通信の
ライン回路への応用において効果を有している。
それは連想プロセツサを等化器中の再帰性デジタ
ルフイルタとして使用できる。また連想プロセツ
サはハイブリツドフイルタ、トランスバースデジ
タルフイルタ中で使用できる。拡張可能なアレイ
として構成された連想プロセツサを使用する可変
長乗算はまた通信以外の応用において効果があ
り、一般的な信号処理およびデータベース応用に
適用可能である。拡張可能なアレイを得るために乗算動作は可変
長であり、かつマスク制御されなければならな
い。したがつて各連想セルは、乗算動作中にエネ
ーブルにされた時に１ビツトの乗数と、１ビツト
の被乗数を受け、また計算結果の２ビツトを受け
なければならない。計算結果のビツトの１つは被
乗数を重ねて書くために使用できる。各連想セル
は乗算動作中デイスエーブルにされた時その近傍
のセルに接続され、それ故もしもそれが能動領域
の境界にあるならば行われるべき直列乗算をエネ
ーブルにするためアクチブなセルの入力と出力と
の間の必要な「ループ・バツク」接続を与えるよ
うにしなければならない。第７図はこの発明の任意長の乗算動作を示して
いる。矢印はデータの流れを示し、図の上方のＤ
はデイスエーブルマスク、Ｅはエネーブルマスク
状態であることを示す。第８図は乗数Ａと被乗数
Ｂの乗算動作のための初期状態を示し、それらの
数は共に例えば正の２進数の２の補数である。第
７図はまたセルに供給された最初のｎ＋１のシフ
トパルス中の乗算を示す。この期間（ｎ＋１をＡ
におけるビツト数としてｎ＋１のシフトパルス）
の終りに乗数Ａは結果Ｒの最初のｎ＋１（低い桁
の方から）のビツトにより置換される。ｎ＋１の
高い桁のビツトは計算ユニツト中の遅延２進レジ
スタ中およびキヤリ２進レジスタ中に保持され
る。レジスタおよびALUの構成については第４
図を参照することができ、第４図では単なるフリ
ツプ・フロツプが使用されている。最上桁ビツト
は右側にある。連想セルの行を示す第７図の構成において各セ
ルは計算論理ユニツト（ALU）４００，４０１
…４０２、被乗数B₀，B₁…B_oを保持するレジス
タ４０３，４０４…４０５、乗数A_o，A_o-1…A₀
を保持するレジスタ４０６，４０７…４０８を有
しており、レジスタ４０３は最下桁ビツトを保持
し、レジスタ４０６は最上桁ビツトを保持する。
マスクがエネーブルされると処理動作が各セルで
生じる。マスクがデイスエーブルにされるとマス
クエネーブルセクシヨンＥの右端においてレジス
タ４０８の出力はALU４００，４０１…４０２
に結合され、ゼロビツトがデイスエーブルにされ
たセルからライン４１２上に入力する。マスクエ
ネーブルセクシヨンＥの他端において、マスクデ
イスエーブルセルはALU４００を線４１４によ
りレジスタ（フリツプ・フロツプ）４０６に接続
する。第７図の構成では符号乗算を行うことはできな
い。符号乗算は符号を表わしている最上桁ビツト
（MSB）を有して数が表示されるものである。２
の補数の計算ではMSBはゼロが正の数を表わし、
１が負の数を表わす。２の補数の（符号付の）２進数ＰおよびＱであ
る２つの値の乗算を行うとする。２進数Ｐおよび
Ｑは次のように表わされる。Ｐ＝−a_o2ⁿ＋a_(o-1)2^n-1＋a_(o-2)2^n-2…a₀2⁰＝−a_o2ⁿ＋ＡＱ＝−b_o2ⁿ＋b_(o-1)2^n-1＋b_(o-2)2^n-2…b₀2⁰＝−b_o2ⁿ＋Ｂすなわち、Ｐ×Ｑ＝（−a_o2ⁿ）×（−b_o2ⁿ）＋（−a_o2ⁿ）×
Ｂ＋（−b_o2ⁿ）×Ａ＋Ａ×Ｂ再び第７図の乗算器の構成を参照すると、Ｂの
２進の有意状態（aignificance）は位置によるも
のであり、Ａの２進有意状態は係数がシフトして
入れられる時間によつて表わされる。それ故： a_j2^jはa_jT_jにより表わされ、ここでT_jはフリツ
プ・フロツプ４０８からライン４１０へデータを
シフトする第ｊ番目のシフトパルスである。以下は符号乗算の空間／時間表示の１例であ
る。

【表】以上から符号のない数に適用されるのと同じ回
路形態が、数Ｑの最上桁ビツト（b_oにより表わさ
れる）に対する計算論理ユニツトが加算の代りに
減算するように設定されていることにより符号を
有する数に対しても動作できることが決定され
た。またＰの最上桁ビツト（a_oにより表わされ
る）がシフトして入れられる時に予め加算にセツ
トされていた計算論理ユニツトは減算にセツトさ
れなければならず、前に減算にセツトされていた
計算論理ユニツトは加算にセツトされなければな
らない。符号を有する数に対する適切な動作のた
めに2_oのシフトパルスがＰの係数の代りにゼロが
シフトされるように供給されなければならない。
計算結果は第２のセツトの２進数（レジスタ）中
にシフトされなければならないか、或はLS（最下
桁）結果が結果の上位桁の半分がシフトして入れ
られる前のT_oシフトパルス後にどこか他に書く
ために出力されなければならないかの何れかであ
る。第８図を参照すると第７図について説明したセ
ルを変形した連想セルが示されており、それは上
述の特徴を行うことができる。セルの構成は次の
とおりである。すなわち数A_o…A_(o-1)…A_o…A₀
の係数a_o，a_o-1…a₀はその数を保持するために必
要であるだけの数の隣接セルのレジスタ４５０，
４５２，４５４、および４５６中に保持される。
係数B₀…B₁…B_(o-1)…B_oはレジスタ４５８，４６
０，４６２および４６４中に保持される。それら
レジスタはそれぞれALU４６６，４６８，４７
０および４７２に結合されている。マスクエネー
ブルＥ中よりもマスクデイスエーブルＤ中に或る
処理動作が生じることを認めることができる。こ
の有意状態はマスクデイスエーブル機能の利用が
フリツプ・フロツプ４５６の出力とシフトライン
４７１間の接続を行うのみならずまたマスクエネ
ーブルされたALU４６６，４６８および４７２
が加算を行う時（他のALUが減算を行う時に反
対にALU４７２は加算を行う）ALU４７２が減
算機能を行うことを決定するセルを特定すること
である。第７図に示すようにエネーブルされたセ
クシヨンＥの他端におけるマスクデイスエーブル
されたセルはALU４６６をレジスタ（フリツ
プ・フロツプ）４５０に線４７３により接続す
る。第８図の回路は第７図の回路についての改良で
あるが、さらに(1)マスクデイスエーブル区域の端
部セルが両立性があることが保証され、(2)加算動
作からのキヤリビツトが計算ユニツト中の次の減
算動作と両立できることが保証されることが要求
されることが発見された。前述の問題に対する答
を出す前に、その問題について詳細に説明する。第９図は端部セルの両立性の問題の性質を示
す。問題は「端部」におけるセル或はエネーブル
セクシヨンの何れかの側のマスクデイスエーブル
セルの実際の接続によつて生じるのではなく、む
しろ第９図のセルＤにより示されるマスクデイス
エーブル区域の中間にあるセル中で生成される。第９図のセルＤは同時に上述したマスクデイス
エーブル端部セルの両方の動作を行う（フリツ
プ・フロツプＡおよびＢは前の計算から出た値を
含む）。フリツプ・フロツプ４８２の出力は第８
図のレジスタ（フリツプ・フロツプ）４５６が乗
算器シフトライン４７１に接続されているのと同
様にライン４８３に接続され、ALU４８０のキ
ヤリ出力は近傍のマスクデイスエーブルセクシヨ
ンＥのセルによりフリツプ・フロツプＡ４８２の
入力に接続される。さらにALU４８０は第８図
のALU４７２のそれと同じように加算或は減算
を行う。前述の結果はフリツプ・フロツプＡおよびＢ中
の値はマスクエネーブル部分中で行われる乗算中
行中の全てのセルに供給されるシフトパルスシー
ケンスの結果として変形されるということであ
る。値は後続する動作中で必要とされるから変化
しないで残つていなければならないため、これは
許容できない。これらのビツトがどのように変化
されるかの詳細な説明が以下に示される。次に示す真値表は第９図のセルＤのALU４８
０中の減算機能の遂行のための論理状態を示して
いる。ここで、Ａはレジスタ４８２中に保持された数である。Ｂは被乗数として作用するレジスタ４８４中に
保持された数である。 C_iは入つて来るキヤリビツトである。 C₀は出て行くキヤリビツトである。 R_iは前のステツプから入つて来る結果である。 R₀は出力する結果である。状態は値Ａ，ＢおよびC_iによるセルＤの状態で
ある。

【表】状態０，２，５，７は安定であるが、状態６は
状態１になり、それは次いで状態７になり、状態
４は状態０になる。前述のことから、全てのマス
クデイスエーブルセルは第１０図のセルＣにより
示されるマスクデイスエーブル区域Ｄの一番左端
にあるセルＣを除いてはデイスエーブルでなけれ
ばならないことが発見された。第１０図のセルＣ
は被乗算の最上桁ビツトを含み、明細書の後の部
分および特許請求の範囲中でそのように参照され
るものであることを注意しなければならない。セ
ルの差或は特定の方法はこの特定のセルに対して
入力データビツトを供給することによつて、或は
前の指令によつて設定されることのできる第２の
内部識別ビツトを有することによつて行われるこ
とができる。第１０図はセルＡ，ＢおよびＣ中の３ビツト乗
算を行う連想セルの行を示す。各セルは第９図で
説明したセルと同一であり、したがつてその動作
の説明は第８図を参照することができる。セル
Ｄ，ＥおよびＦは第９図で説明したセルと同一で
あり、それぞれ第９図について前に説明したよう
にフリツプ・フロツプおよびALUを備えている。上に挙げた第２の問題、すなわちALU中の後
続の減算を有する加算動作からのキヤリの両立性
の問題について説明する。実際上「キヤリセー
ブ」加算器である交互の加算および減算を有する
ものとして説明することもできるこの問題は同時
或は交互の何れかでアクチブにされる別別のキヤ
リおよび借りセーブパス（borrow save pass）
を有するようにALU回路を変形することによつ
て解決することができる。第１１図には上述の特定化の問題を解決するこ
とのできるALU回路が示されている。真値表に記載されるような、周知の設計の複合
論理回路で構成することのできる加算・減算回路
５００は、例えば乗数および被乗数であつてよい
数ａおよびｂ、或は動作させるための他の数を結
合されている。数ａおよびｂはアンドゲート５０
２および入力端子Ｆを経て加算・減算回路５００
に結合される。前のセル段からの結果R′および
前のシフト時間は線５０４で遅延フリツプ・フロ
ツプ５０６へ、次いで加算・減算回路５００の端
子R′へ結合される。前のシフト時間からのキヤ
リC′は遅延フリツプ・フロツプ５０８から得ら
れ、この遅延フリツプ・フロツプ５０８は回路５
００のＣ出力端子からキヤリＣを受け、それを１
シフト時間遅延させて回路５００のC′入力端子に
供給する。同様に回路５００の借りＢ出力は遅延
フリツプ・フロツプ５１０に供給され、１シフト
時間遅延されて前のシフト時間からの借りとして
回路５００のB′入力端子に供給される。アンド
ゲート５０２からのデータ中の高速（Fast）は
回路５００のＦ入力端子に供給される。計算結果
Ｒは回路５００のＲ出力端子から次のセルに結合
され、次のセルに対するR′入力となる。第１１図の計算論理ユニツトの加算・減算回路
５００の加算および減算機能に対する真値表を以
下に示すが、それにおいて、Ｆは入力２進数である。 R′は前の段および前のシフト時間からの計算
結果である。 C′は前のシフト時間からのキヤリである。 B′は前のシフト時間からのボロウである。Ｒは現在の計算結果である。Ｃは現在のキヤリである。Ｂは現在のボロウである。加算Ｒ＝Ｆ＋R′＋C′−B′に対する真値表は次
のとおりである。

【表】

【表】加算Ｒ＝Ｆ−R′＋C′−Ｂに対する真値表は次の
とおりである。

【表】以上、この発明をその好ましい実施例と関連し
て説明したが、当業者には自明である多くのその
他の実施例、変形および応用も特許請求の範囲に
記載された発明の技術的範囲に含まれることを理
解すべきである。

【図面の簡単な説明】

第１図は連想プロセツサの簡略化したブロツク
図、第２図は垂直および水平マスクを有する20×
４のセルの連想アレイの簡略図、第３図は単純な
セルの論理回路図、第４図は直列・並列乗算装置
の論理回路図、第５図は行中の10個のセルの概略
図、第６図は直列・並列乗算用のデータの流れを
示す図、第７図は連想セルの任意長乗算形式のも
ののブロツク図、第８図は追加の計算能力を有す
る第７図の回路の変形、第９図は連想セルの動作
をさらに示すブロツク図、第１０図はこの発明に
よる乗算を行う連想セルの行を示す概略図、第１
１図はこの発明の動作を説明する連想セルの計算
論理ユニツトのブロツクおよび論理図である。１００……連想アレイ、１０２……水平マスク
レジスタ、１０４……垂直マスクレジスタ、１０
６……アレイ制御装置、１１２……アドレスレジ
スタ、２０２……セルマトリツクス、２０４……
セル、２０６……水平マスクレジスタ、２０８…
…垂直マスクレジスタ、２０９……垂直入出力レ
ジスタ、２１０……Ａ型フリツプ・フロツプ、２
１２……Ｍ型フリツプ・フロツプ、２１４……計
算論理ユニツト、２２２，２２８……選択スイツ
チ、２３２……選択ゲート、３０６，３０８，３
１０，３２０，３２２……フリツプ・フロツプ、
３１４……アンドゲート、３１６……加算器、４
００，４０１，４０２……論理計算ユニツト、４
０３，４０４，４０５……被乗数レジスタ、４０
６，４０７，４０８……乗数レジスタ、４５０，
４５２，４５４，４５６，４５８，４６０，４６
２，４６４……レジスタ、４６６，４６８，４７
０，４７２，４８０……計算論理ユニツト、４８
２……フリツプフロツプ（レジスタ）、５００…
…加算・減算回路、５０２……アンドゲート、５
０６，５０８，５１０……遅延フリツプ・フロツ
プ。

Claims

【特許請求の範囲】１それぞれ和ビツトおよびキヤリビツトを同時
に蓄積するように構成されているセルからなる連
想セルの行および列に配列されたアレイを具備
し、各セルは、１以上の特定のセルが乗数或いは被乗数ビツト
の何れか或はその組合せを有していることを特定
するためのマスキング手段と、被乗数ビツトを蓄積する手段と、被乗数ビツトと乗数ビツトトの乗算を行う手段
と、前記セルが乗算結果の２ビツトを蓄積するよう
に乗算動作中セルをエネーブルにする手段と、前のシフト時間からの計算操作の結果にマスク
された被乗数ビツトを加算或は減算して現在の乗
算結果を出力するために乗数ビツトを順次受信す
る計算論理ユニツト手段と、乗数が隣接セル中で同時に生成される如く現在
の乗算結果をその現在の結果が得られるのと同じ
シフト時間に隣接する連想セルに結合する手段と
を具備し、この隣接連想セルへ前記現在の乗算結果を結合
する手段はセルが乗算動作中にデイスエーブルに
された時にセルの入力出力間にループバツク接続
を設けるための手段を具備し、それによつて直列
乗算が連想アレイ中のセルの位置に関係なく得ら
れることを特徴とする連想プロセツサ。２プロセツサにより実行されるべき多ビツト指
令ワードを受信するためおよびプロセツサによる
前記指令の実行を制御するための制御手段が設け
られ、この制御手段はマスキング手段に対してプ
ロセツサのエネーブルおよびデイスエーブル部分
のためにまたプロセツサに対してそこに蓄積する
ために多ビツト指令ワードを結合する手段を備え
ている特許請求の範囲第１項記載の連想プロセツ
サ。３被乗数および乗数ビツトは前記信号が実時間
で前記プロセツサにより乗算されるようにデジタ
ル信号情報を表している特許請求の範囲第１項記
載の連想プロセツサ。４データフイールド中のデータが２進数の２の
補数で構成されている特許請求の範囲第１項記載
の連想プロセツサ。５２進数の２の補数は前記マスキング手段の制
御下にアレイの各セル中で動作される特許請求の
範囲第４項記載の連想プロセツサ。６乗数および被乗数が次式で表わされる数であ
り、Ｐ＝−a_o2ⁿ＋a_(o-1)2^(n-1)＋a_(o-2)2^(
n-2)…a₀2⁰＝−a_o2ⁿ＋ＡＱ＝−b_o2ⁿ＋b_(o-1)2^(n-1)＋b_(o-2)2^(
n-2)…b₀2⁰＝−b_o2ⁿ＋ＢＢの２進有意状態はアレイ中の位置により決定
され、Ａの２進有意状態は係数がアレイ内でシフ
トされる時間により決定される特許請求の範囲第
４項記載の連想プロセツサ。７マスクデイスエーブル区域中の被乗数の最上
桁ビツトを含むセルのデイスエーブルを阻止する
ために前記マスキング手段により前記乗算動作中
セルがその都度デイスエイブルにされるように動
作する手段が設けられている特許請求の範囲第１
項記載の連想プロセツサ。８行のマスクデイスエーブル区域中の被乗数の
最上桁ビツトを含むセルを特定する手段を備えて
いる特許請求の範囲第７項記載の連想プロセツ
サ。９前記セルを特定する手段は前記セルに入力デ
ータビツトを供給する手段を備えている特許請求
の範囲第８項記載の連想プロセツサ。１０前記セルを特定する手段がセル内に内部フ
リツプ・フロツプおよびそのフリツプ・フロツプ
を設定および不設定にする手段を備えている特許
請求の範囲第８項記載の連想プロセツサ。１１前記アレイ手段中の各セルに対する前記計
算論理ユニツト手段は、加算動作からのキヤリは
それに続く減算動作と両立性であり、減算動作か
らの借りはそれに続く加算動作と両立性であるよ
うに同時或は交互の何れかで活性にされる如く構
成された別々のキヤリおよび借りセーブパスを与
える手段を備えている特許請求の範囲第１項記載
の連想プロセツサ。１２前記アレイ中の各セルに対する前記論理計
算ユニツト手段が、入力Ｆを加算・減算回路に結合する手段と、前のセル段と前のシフト時間からの結果R′と
を前記加算・減算回路に結合する手段と、前のシフト時間からのキヤリC′を１シフト時間
遅延させた後に前記加算・減算回路に結合する手
段と、前記加算・減算回路の借りＢを１シフト時間だ
け遅延させ、前のシフト時間からの遅延された借
りB′を結合する手段と、および前記加算・減算回路から前記入力２進数Ｆにつ
いての計算結果Ｒを得て、その結果Ｒを次に隣接
するセルにそのR′入力として結合させる手段と
を具備している特許請求の範囲第１１項記載の連
想プロセツサ。１３被乗数ビツトを蓄積する手段がフリツプ・
フロツプで構成されている特許請求の範囲第１項
記載の連想プロセツサ。１４乗数ビツトを蓄積する手段がシフトレジス
タを具備している特許請求の範囲第１項記載の連
想プロセツサ。１５被乗数ビツトのマスキング手段はアレイの
行または列のそれぞれと連想するマスクセルを具
備し、かつ各アレイセルにおいて前記被乗数ビツ
トと前記乗数ビツトとのアンド論理動作を行つて
アレイセルに対する高速乗算入力を得る手段を具
備している特許請求の範囲第１項記載の連想プロ
セツサ。１６連想プロセスセルの連想プロセスアレイ中
で可変長の２進数の高速乗算を行う方法におい
て、各指令が動作フイールド、データフイールドお
よびマスキングフイールドを含んでいる複数の２
進指令を蓄積し、前記動作フイールドの制御下に前記セルに結合
された直列乗数において各セルの計算論理ユニツ
ト中の高速乗算動作を実行するためにマスキング
フイールドに応じて前記プロセスセルの個々のも
のをエネーブルおよびデイスエネーブルにし、セルの計算論理ユニツトに対する高速乗算入力
を得るために被乗数を乗数ビツトと乗算し、前記被乗数を並列にかつ前記乗数ビツトを直列
に前記連想アレイセルのそれぞれにおける計算論
理ユニツトに結合して乗算積結果を導出し、任意のデジツト長の被乗数および乗数に対して
各セル中で同時に乗算が実行されるように同じシ
フト時間に各セル中の前記乗算積結果を隣接セル
に結合させ、セルが乗算動作中にデイスエーブルにされた時
にセルの入力出力間にループバツク接続を設けて
それによつて前記乗算が連想アレイ中のセルの位
置に関係なく得ることを特徴とする可変長２進数
の高速乗算方法。１７マスキング過程においてデイスエーブルに
されたセル中の被乗数の最上桁ビツトを含むセル
のマスキング手段により乗算処理中デイスエーブ
ルになることが阻止される特許請求の範囲第１６
項記載の方法。１８マスキング過程において行のマスクデイス
エーブル区域のセルを特定するサブステツプを含
む特許請求の範囲第１７項記載の方法。１９加算動作からのキヤリが次の減算動作と両
立性であり、減算動作からの借りが次の加算動作
と両立性であるように同時或は交互の何れかによ
り活性化されるように構成された別々のキヤリお
よび借りセーブパスが結合される特許請求の範囲
第１６項記載の方法。２０前記２進指令が２の補数のデータである特
許請求の範囲第１６項記載の方法。