JPH0512098A

JPH0512098A - 記憶装置

Info

Publication number: JPH0512098A
Application number: JP18820991A
Authority: JP
Inventors: Hisakazu Sato; 尚和佐藤
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1991-07-02
Filing date: 1991-07-02
Publication date: 1993-01-22

Abstract

(57)【要約】【目的】ハッシュメモリを用いると共に、ハッシュ衝
突時の待避領域を備えた記憶装置において、ハッシュメ
モリの不良による歩留まり低下を抑える。【構成】ハッシュメモリ６０１とハッシュ衝突時の待
避領域として連想メモリ部６０２を有するマッチングメ
モリに、ＮＧレジスタ１と不良検出器２とＡＮＤゲート
３を設ける。ＮＧレジスタ１は不良アドレスを格納する
ためのビットの他に、不良ビットが存在する場合“１”
が設定されるビットをＭＳＢに有する。不良検出器２は
ＮＧレジスタ１の不良アドレスと演算器１０１のハッシ
ュアドレスを比較して、両者が一致するとき“１”を出
力する。ＡＮＤゲート３は不良検出器２の出力とＮＧレ
ジスタ１のＭＳＢが“１”のとき，即ちハッシュアドレ
スが不良アドレスと一致し，かつ不良ビットが存在した
とき“１”となるＮＧ信号を制御部６０６に出力する。
このとき制御部６０６は、ハッシュ衝突が生じたものと
見做して連想メモリ部６０２をアクセスする。これによ
り、不良ビットが存在するハッシュメモリでも不良チッ
プとせずに使用することができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、ハッシュメモリを用
いると共に、ハッシュ衝突時の待避領域を備えた記憶装
置、例えば、識別子の一致するデータの対を生成し、発
火処理するデータ駆動形計算機のマッチングメモリ等に
用いられる記憶装置に関するものである。

【０００２】

【従来の技術】この種のデータ駆動形計算機としては、
図３に示すようなデータ駆動形マイクロプロセッサが既
に本出願人により提案されている（特願平３−４０９８
１号，平成３年２月１２日出願）。図４のプログラム
（データフローグラフ）を実行する場合について、その
動作を説明する。外部から入出力インタフェース部ＩＦ
を経由して入力されたパケットは、図５に示されている
ように、行き先プロセッサ番号（ＰＥ＃）「１」、制御
情報（ＳＥＬ−ＣＯＤＥ）、命令コード（ＯＰＣ）
「＋」、行き先ノード番号＃１、左データ「Ｉ」を含ん
でいる。制御情報ＳＥＬ−ＣＯＤＥのうち、ＰＡＩＲは
マッチングメモリで発火（対生成）処理をするか否か、
ＩＭはデータメモリからオペランド（被演算データ）の
読み出しを行うか否か、Ｉ／Ｏ（Ｏは反転，以下バーＯ
と記す）は演算終了後プロセッサ内で継続処理するか否
か、ＶＥＣＴはベクトル演算対象データであるか否か、
Ｌ／バーＲは発火処理以前に左データ位置に格納されて
いるデータが２項演算の左データとなるデータであるか
否かを示している。

【０００３】外部から入力されたパケット「Ｉ」は、入
出力インターフェース部ＩＦを経由してマッチングメモ
リ部ＭＭに到るが、図５（ａ）に示すように、ＳＥＬ−
ＣＯＤＥのＩＭフラッグが「１」であるため、２項演算
の相手のデータはデータメモリ部ＤＭから読み出すもの
と解釈されて何も処理されずにデータメモリ部ＤＭに送
られる。データメモリ部ＤＭにおいては、ＩＭフラグが
「１」であるため、パケットの右データ位置に格納され
ている値「ｎ」に相当するアドレスに記憶されているデ
ータが読み出され、「ｎ」の代わりに右データ位置に格
納される。

【０００４】データメモリ部ＤＭからは、演算部ＦＡＬ
Ｕとプログラムメモリ部ＰＭに同時にパケットが送出さ
れる。演算部ＦＡＬＵでは、命令コード「＋」に従って
２項演算が実行され、結果データがパケットの左データ
位置に格納される。

【０００５】一方、プログラムメモリ部ＰＭでは、パケ
ットの行き先ノード番号「＃１」に従ってプログラムメ
モリの読み出しが行われ、次の行き先ノード番号「＃
２」、次の命令コード「×」、次の制御情報などが読み
出されてパケット中の相当部分が更新される。なお、行
き先ノード番号が複数あれば、それぞれのノード番号に
対してコピーによるパケットの連続発生が行われる。

【０００６】演算部ＦＡＬＵ、およびプログラムメモリ
部ＰＭで更新されたこれらの情報は、コピー部ＫＣＯＰ
Ｙで連結併合され再び入出力インターフェース部ＩＦに
送られる。コピー部ＫＣＯＰＹでは、１つのノードの演
算結果に対して複数の行き先ノードが存在するような場
合に、演算結果データのコピーが行われ、プログラムメ
モリ部ＰＭで読み出された複数のタグ情報に付与され
て、同一の結果データをもつ複数のパケットが出力され
る。

【０００７】この演算結果パケットが入出力インターフ
ェース部ＩＦを経由して再びマッチングメモリ部ＭＭに
到着したとき、すでにデータ「Ｊ」をもつパケット（図
５（ｂ）参照）がマッチングメモリ部ＭＭに到着して格
納されていれば、これら２つのパケットの行き先ノード
番号が何れも「＃２」であることから、発火処理が行わ
れ、２項演算のためのパケットが生成される。一方、相
手となるパケットが未到着であれば、マッチングメモリ
部ＭＭにおいて相手パケットの待ち合わせを行う。マッ
チングメモリ部ＭＭで生成された前記パケットは、ＩＭ
フラグが「０」であることから、データメモリ部ＤＭを
通過し、演算部ＦＡＬＵとプログラムメモリ部ＰＭに送
られる。演算部ＦＡＬＵでは乗算が実行される。また、
プログラムメモリ部ＰＭでは、次のタグ情報が読み出さ
れ、図５（ｃ）に示すようなパケットに付与される。こ
れらの情報は、コピー部ＫＣＯＰＹで連結併合された後
インタフェース部ＩＦに送られるが、図５（ｃ）に示さ
れているようにＳＥＬ−ＣＯＤＥのＩ／バーＯフラグが
０であることから外部に出力される。

【０００８】以上説明したように、２つの入力を受け入
れたプログラム（データフローグラフ）は、所定の処理
を完了し、結果をパケットの形で出力する。

【０００９】図６は上記マッチングメモリ部ＭＭの一構
成例を示すブロック図である。図において、６１２は入
力セレクタであり、後述するＦＩＦＯメモリ６１１から
出力されたパケットと入力されたパケットの何れかを選
択する。なお、ここでは、パケットはそのビットマップ
を図７に示すが如く構成され、６２ビットの幅を有して
いるものとする。選択されたパケットはデータラッチ６
０８に与えられ、そこでデータ入力信号Ｃ０が“Ｈ”の
タイミングでラッチされる。ラッチされたパケットはそ
の３１ビットの識別子のうち、入力データの入力順等の
属性を示すカラー／世代識別番号ＤＮの９ビットと、ノ
ード番号ＮＮの下位９ビットとが、排他的論理和演算を
行いハッシュアドレスを生成するアドレス生成手段であ
る演算器１０１の２つの入力端子に夫々与えられる。こ
こで夫々のビット毎に排他的論理和演算が行われ、その
演算結果がハッシュアドレスとなり、ハッシュメモリ６
０１に与えられる。

【００１０】また、３１ビットの識別子と１８ビットの
オペランドデータＯＤとは連想メモリ部６０２にも与え
られる。また、識別子のうちノード番号ＮＮの下位９ビ
ットを除いた２２ビットと、１８ビットのオペランドデ
ータＯＤとを合わせた４０ビットの書き込みデータがハ
ッシュメモリ６０１に与えられる。

【００１１】図８はハッシュメモリ６０１の構成を示す
ブロック図であり、ハッシュメモリ６０１は４１ビット
のビット幅を有し、ハッシュアドレス９ビット分（２⁹
＝５１２）のアドレス空間を有している。そして、１８
ビットのオペランドデータＯＤと、３１ビットの識別子
のうちノード番号ＮＮの下位９ビットを除いた２２ビッ
トとが格納されると共に、そのアドレスの内容の有効
（ＰＢ＝１）、無効（ＰＢ＝０）の別を示すフラグであ
るプレゼンスビットＰＢが格納されている。ハッシュメ
モリ６０１には前述の如く９ビットのハッシュアドレス
と４０ビットの書き込みデータが与えられると共に、後
述する制御部６０６からそのリードライトサイクルを定
めるリードライト信号Ｗ／バーＲ・Ｈと、プレゼンスビ
ットＰＢの更新を行うセット信号Ｓ／バーＲとが与えら
れ、リードライト信号Ｗ／バーＲ・Ｈ＝“Ｈ”のサイク
ルで書き込みがなされ、Ｗ／バーＲ・Ｈ＝“Ｌ”のサイ
クルで指定されたアドレスの読み出しデータとプレゼン
スビットＰＢとが出力される。

【００１２】図９は連想メモリ部６０２の構成を示すブ
ロック図である。図において、２０１はハッシュ衝突し
たときにデータラッチ６０８からの３１ビットの識別子
と一致するデータを検索する連想メモリ（以下ＣＡＭと
いう）であり、３２ビット×３２アドレスの容量となっ
ている。ＣＡＭ２０１のうち１ビットは前記ハッシュメ
モリ６０１と同様に格納されているデータの有効性を判
別するためのプレゼンスビットＰＢの格納に用いられ
る。ＣＡＭ２０１には各アドレスに対して一致，不一致
検索ライン（以下マッチラインという）が設けられてお
り、与えられた３１ビットの識別子と、ＣＡＭ２０１に
格納された識別子とが全て一致したアドレスの３２ビッ
トのマッチラインの１ビットが“Ｈ”となる判定信号が
出力される。また、ＣＡＭ２０１にはセレクタ２０５を
介してプレゼンスビットＰＢの更新を行うセット信号Ｓ
／バーＲが与えられると共に、リードライトのサイクル
を定めるリードライト信号Ｗ／バーＲ・Ｃが与えられ
る。セレクタ２０５は一端に基準電圧が、他端にセット
信号Ｓ／バーＲが与えられており、その切換端子にはリ
ードライト信号Ｗ／バーＲ・Ｃが与えられており、リー
ドサイクルのときは基準電圧が、ライトサイクルのとき
はセット信号Ｓ／バーＲが選択される。即ちリードサイ
クル（Ｗ／バーＲ・Ｃ＝Ｌ）のときは、プレゼンスビッ
トＰＢ＝１のアドレスだけを検索する必要があるので、
検索データのプレゼンスビットＰＢに相当するビットを
常に１とし、ライトサイクル（Ｗ／バーＲ・Ｃ＝Ｈ）の
ときのみプレゼンスビットＰＢを更新する必要があるた
めにこのセレクタ２０５は用いられる。

【００１３】また、ＣＡＭ２０１からは３２ビットのマ
ッチラインに識別子の一致，不一致の別を示す判定信号
が出力されると共に、空アドレス検出器２０３に各アド
レスのプレゼンスビットＰＢが出力され、そこでプレゼ
ンスビットＰＢにより空アドレスが検出される。空アド
レス検出器２０３は３２ビットの検出信号をアドレスセ
レクタ２０４の一端に出力すると共に、空アドレスがな
くＣＡＭ２０１の全アドレス空間にハッシュ衝突したパ
ケットの識別子が格納されたとき、そのことを示すフル
信号ＦＬを制御部６０６に出力する。なお、検出信号は
ＣＡＭ２０１のアドレスに対応する３２ビットの出力で
あり、その空アドレスのビットが“Ｈ”となっている。
アドレスセレクタ２０４の他端にはマッチラインからの
判定信号が与えられ、その切換端子に与えられたリード
ライト信号Ｗ／バーＲ・Ｃのリードライトに応じアドレ
スセレクタ２０４はリードサイクルのときは判定信号
を、またライトサイクルのときは空アドレス検出器２０
３の検出信号を夫々選択する。アドレスセレクタ２０４
のアドレス選択出力はＲＡＭ２０２に与えられ、それに
より指定されたアドレスがアクセスされる。ＲＡＭ２０
２はオペランドデータを格納するためのものであり、１
８ビット×３２アドレスの容量となっている。リードラ
イト信号Ｗ／バーＲ・Ｃ及びアドレス選択出力に応じて
オペランドデータの読み書きが行われる。即ちリードサ
イクルではＲＡＭ２０２のアドレスラインには判定信号
が与えられ、ＣＡＭ２０１に入力されたパケットの識別
子と一致する識別子がＣＡＭ２０１に格納されている場
合（これをＣＡＭ２０１がヒットしたという）、判定信
号に応じたアドレスの１８ビットのオペランドデータが
読み出しデータとして出力される。この読み出しデータ
は判定信号とマージされ、５０ビットの出力信号として
データラッチ６０９に出力される。またＣＡＭ２０１が
ヒットしなければ判定信号は３２ビット全て“Ｌ”のま
まであり、ＲＡＭ２０２からは如何なるオペランドデー
タも読み出されない。一方、ライトサイクルでは空アド
レス検出器２０３からの検出信号が選択され、ＣＡＭ２
０１とＲＡＭ２０２の何れかのアドレスに３１ビットの
識別子と１８ビットのオペランドデータＯＤとを格納す
るかを指示する。また、ＣＡＭ２０１がヒットした場合
はプレゼンスビットＰＢを更新する必要が生じるので、
ライトサイクルにてＣＡＭ２０１に与えられるアドレス
はヒットしたアドレスである。

【００１４】入力されたパケットとハッシュアドレスと
が等しいハッシュメモリ６０１内の４０ビットの格納デ
ータ、ハッシュメモリ６０１のプレゼンスビットＰＢ及
び連想メモリ部６０２の出力信号は、データラッチ６０
９にクロックＴ１のタイミングでラッチされ、プレゼン
スビットＰＢは制御部６０６へ、また格納データのうち
の２２ビットの識別子は一致検出器６０３の一端へ、格
納データのうち１８ビットのオペランドデータＯＤは出
力セレクタ６０５の一端へ夫々与えられる。また、連想
メモリ部６０２の出力信号のうち３２ビットの判定信号
はヒット検出器６０４へ、また１８ビットのオペランド
データＯＤは出力セレクタ６０５の他端へ与えられる。

【００１５】一致検出器６０３の他端には、入力された
３１ビットの識別子の下位９ビットを除いた２２ビット
の識別子が与えられ、入力された２つの識別子の一致を
検出し、一致している場合は一致信号ＥＱを制御部６０
６に出力する。即ち、一致した場合はハッシュアドレス
として用いた９ビットの識別子と２２ビットの識別子と
が全て一致したことになるため、その旨を一致信号ＥＱ
として制御部６０６へ告知する。

【００１６】また、ヒット検出器６０４はＣＡＭ２０１
からの３２本のマッチラインの判定信号をモニタし、そ
の中の１ビットでも“Ｈ”に立上がったものがあった場
合は（＝ＣＡＭ２０１がヒットすれば）、ヒット信号Ｈ
ＩＴを制御部６０６及び出力セレクタ６０５の切換端子
に与える。

【００１７】出力セレクタ６０５は、入力されたパケッ
トの識別子とハッシュメモリ６０１または連想メモリ６
０２内に格納された識別子とが全て一致する発火対象の
相手データが検索された場合に、一致した識別子を格納
した方のメモリからのオペランドデータＯＤを選択する
ものである。選択結果のオペランドデータＯＤはデータ
ラッチ６１０に与えられ、制御部６０６からのクロック
Ｔ２の“Ｈ”のタイミングでラッチされ、データ対形成
器６０７の一端に与えられる。出力セレクタ６０５の選
択は切換端子に与えられたヒット信号ＨＩＴにより行わ
れ、ＣＡＭ２０１がヒットした場合にのみ連想メモリ部
６０２に格納されていたオペランドデータＯＤを選択
し、ヒットしなかった場合にはハッシュメモリ６０１に
格納されていたデータを選択し、データラッチ６１０に
送る。

【００１８】データ対形成器６０７は、出力セレクタ６
０５により選択されたオペランドデータＯＤが一端に入
力されると共に、他端にはデータラッチ６０８からの６
２ビットの入力されたパケットのデータが与えられる。
そして、２つのデータがマージされて８０ビットの２オ
ペランドデータが形成される。このとき２項演算の減算
命令の如くオペランドの順序関係が重要なものがあるの
で、選択されたオペランドデータＯＤと入力されたパケ
ットのオペランドデータＯＤとは正しく左または右のオ
ペランドとして配置される必要がある。図１０はデータ
対形成器６０７の構成を示すブロック図である。データ
対形成器６０７は２つのデータセレクタ７０１，７０２
からなり、夫々の切換端子には入力されたパケットの左
／右データ選択ビットでその状態を示すセレクタ制御信
号Ｌ／バーＲが与えられる。データセレクタ７０１のＡ
端子及びデータセレクタ７０２のＢ端子にはデータラッ
チ６０８よりの入力されたパケットのオペランドデータ
ＯＤが夫々与えられ、データセレクタ７０１のＢ端子及
びデータセレクタ７０２のＡ端子にはデータラッチ６１
０よりの格納されたオペランドデータＯＤが与えられ
る。そして、入力されたパケットのセレクタ制御信号Ｌ
／バーＲが“１”のときは、夫々のデータセレクタ７０
１，７０２のＡ端子に与えられたオペランドデータが、
またＬ／バーＲが“０”のときはＢ端子に与えられたオ
ペランドデータが選択され、データセレクタ７０１から
の選択出力が左オペランドとなり、データセレクタ７０
２からの選択出力が右オペランドとなり、それらと入力
されたパケットのオペランドデータＯＤを除く他のデー
タとがマージされて出力される。

【００１９】制御部６０６は、プレゼンスビットＰＢ，
ヒット信号ＨＩＴ，一致信号ＥＱ，入力されたパケット
が２入力命令か１入力命令かの別を示すＦＣ処理選択ビ
ットの状態で定まる入力選択信号ＦＣ（２入力命令ＦＣ
＝１，１入力命令ＦＣ＝０）及びフル信号ＦＬが与えら
れ、それらを判断してリードライト信号Ｗ／バーＲ・
Ｃ，Ｗ／バーＲ／Ｈ，セット信号Ｓ／バーＲ，データ出
力信号Ｃ１及び後述するＦＩＦＯメモリ６１１への書き
込み信号ＷＲＦを出力する。またデータ入力信号Ｃ０，
データ出力許可信号バーＡ１が入力され、それらを判断
してデータ入力許可信号バーＡ０，クロックＴ１及び同
Ｔ２を出力する。ここでデータ入力信号Ｃ０及びデータ
入力許可信号バーＡ０は、このマッチングメモリ部ＭＭ
と、このマッチングメモリ部ＭＭに対してデータを与え
る前段処理部との間のデータ転送制御信号であり、デー
タ出力信号Ｃ１及びデータ出力許可信号バーＡ１は、こ
のマッチングメモリ部ＭＭの出力するデータを受取る後
段処理部との間のデータ転送制御信号である。

【００２０】制御部６０６にフル信号ＦＬが入力され、
さらにハッシュ衝突が生じた場合、制御部６０６から２
ポートタイプのＦＩＦＯメモリ６１１に書き込み信号Ｗ
ＲＦが与えられる。このとき、ＦＩＦＯメモリ６１１は
データ対形成器６０７からの出力信号のうち入力された
パケットの６２ビットのデータを格納し、それを所定時
間バッファリングした後、入力セレクタ６１２の他端に
与える。この間に、ハッシュ衝突の原因となったハッシ
ュアドレスのハッシュメモリ６０１内のデータか、また
はＣＡＭ２０１内のデータの何れかのデータが読み出さ
れて発火されている場合は、ＦＩＦＯメモリ６１１を経
由して再び入力されたパケットはこのマッチングメモリ
部ＭＭ内のハッシュメモリ６０１または連想メモリ部６
０２の何れかで待合せを行うことができる。この際、入
力セレクタ６１２は通常外部より与えられるデータをセ
レクトし、ＦＩＦＯメモリ６１１の出力端にバッファリ
ングを施されたデータが存在するときのみ、外部より与
えられるデータとＦＩＦＯメモリ６１１の与えるデータ
を交互にセレクトするよう制御される。

【００２１】次に、以上の如く構成されたマッチングメ
モリ部ＭＭの動作について説明する。なお、ハッシュメ
モリ６０１には対のデータを待つ複数のパケットが格納
されているものとする。図１１は、このマッチングメモ
リ部ＭＭの概略動作を説明するフローチャートである。
パケットが入力されると（Ｓ１）、連想メモリ部６０２
では格納された識別子との一致，不一致を判定（Ｓ１
０）すると共に、９ビットのハッシュアドレスがカラー
／世代識別番号ＤＮ（９ビット）とノード番号ＮＮの下
位９ビットとの排他的論理和により生成される（Ｓ
２）。次に、ハッシュメモリ６０１のそのハッシュアド
レスに有効なデータが既に格納されているか否かが判定
され（Ｓ３）、連想メモリ部６０２の識別子と一致せ
ず、かつＳ３でデータが格納されていない場合は（Ｓ１
３）、入力パケットをハッシュメモリ６０１のそのハッ
シュアドレスに格納し（Ｓ４）、有効なデータが既に格
納されている場合は２２ビットの他の識別子が一致して
いるか否かが判定され（Ｓ５）、一致していない場合は
ハッシュ衝突が生じているので、入力パケットを連想メ
モリ部６０２に格納し（Ｓ７）、一致した場合はハッシ
ュメモリ６０１内の格納データを選択し（Ｓ９）、それ
と入力パケットとをデータ対となす発火処理を行う（Ｓ
１２）。但し、連想メモリ部６０２の識別子と一致せ
ず、かつハッシュメモリ６０１内の２２ビットの他の識
別子が不一致の時に（Ｓ１４）、連想メモリ部６０２が
満杯か否かが判定され（Ｓ６）、満杯のときは入力パケ
ットをＦＩＦＯメモリ６１１に格納し（Ｓ８）、満杯で
ないときは連想メモリ部６０２に格納した後（Ｓ７）、
次の処理に移る。また、入力パケットと連想メモリ部６
０２に格納された識別子との一致，不一致の判定（Ｓ１
０）で一致したときは、連想メモリ部６０２の出力を選
択し（Ｓ１１）、発火処理する（Ｓ１２）。以上が概略
動作である。

【００２２】図１２はこのマッチングメモリ部ＭＭの動
作サイクルを説明するタイミングチャートであり、この
図に示す如く、マッチングメモリ部ＭＭの動作サイクル
は、リードサイクル，処理サイクル及びライトサイクル
の３つのサイクルに分けられる。前段処理部からのデー
タ入力信号Ｃ０が制御部６０６に入力されると、前段処
理部への出力許可信号バーＡ０が“１”→“０”に変化
し、次の入力を禁止し、リードサイクルに入る。リード
サイクルに入ると、入力セレクタ６１２で選択された入
力パケットまたはＣＡＭ２０１のオーバーフローにより
循環されたパケットの何れかが、データ入力信号Ｃ０の
“０”→“１”のタイミングでデータラッチ６０８にラ
ッチされる。データラッチ６０８にパケットが入力され
ると、当該パケットの３１ビットの識別子のうち、カラ
ー／世代識別番号ＤＮの９ビットと２１ビットのノード
番号ＮＮの下位９ビットとが演算器１０１に与えられ、
それらの排他的論理和演算が行われ、９ビットのハッシ
ュアドレスが定められる。なお、この例では演算器１０
１により２種類の識別コードの排他的論理和演算が行わ
れているが、識別コードの演算対象数及び演算内容はこ
れに限るものではなく、演算対象数は３つ以上でもよ
く、また演算内容は加算等の他の逆算可能な演算でもよ
い。

【００２３】ハッシュアドレスが定められると、リード
サイクルではハッシュメモリ６０１と連想メモリ部６０
２とが同時に読み出される。メモリ読み出しに必要な時
間が経過するとクロックＴ１が“０”→“１”に変化
し、読み出されたデータはデータラッチ６０９にラッチ
される。ここから処理サイクルに入り、一致検出器６０
３及びヒット検出器６０４はハッシュメモリ６０１及び
連想メモリ部６０２より読み出された各データに基づい
て一致信号ＥＱ及びヒット信号ＨＩＴを出力する。即
ち、一致検出器６０３はハッシュ衝突が起こっているか
否かを検出するものであり、データラッチ６０８に入力
されているパケットの識別子とハッシュメモリ６０１か
ら読み出されてデータラッチ６０９にラッチされている
識別子との比較を行う。即ち、カラー／世代識別番号Ｄ
Ｎの９ビット，ノード番号ＮＮの上位１２ビット及びプ
ロセッサ識別ビットの１ビットの計２２ビットの比較を
行う。これらの２２ビットが全て等しいと判定される
と、９ビットのハッシュアドレスが等しく、また９ビッ
トのカラー／世代識別番号ＤＮが等しいので、ノード番
号ＮＮの下位９ビットも等しいことになり、３１ビット
識別子の全てが等しいと判定され、一致検出器６０３は
一致信号ＥＱ＝“１”を制御部６０６に出力する。そし
て、ヒット検出器６０４では、連想メモリ部６０２に格
納されている識別子とデータラッチ６０８に入力されて
いるパケットの識別子とが等しい場合，即ち３２ビット
のマッチラインの何れかが“Ｈ”となったときにヒット
信号ＨＩＴ＝“１”を出力する。

【００２４】上述の操作に必要な時間が経過すると、ク
ロックＴ２が“０”→“１”に変化し、ライトサイクル
に入る。ライトサイクルでは、プレゼンスビットＰＢの
更新を含むメモリの書き込みとデータ対の生成が行われ
る。これらの操作に必要な時間が経過すると、制御部６
０６はデータ出力信号Ｃ１を出力し、クロックＴ１，Ｔ
２及びデータ入力許可信号バーＡ０の復帰を行い、一連
の処理を終了する。但し、データ出力信号Ｃ１の出力は
入力されたパケットが発火したときだけであり、発火し
なかった場合は、クロックＴ１，Ｔ２及びデータ入力許
可信号バーＡ０の復帰だけを行い、データ出力信号Ｃ１
は出力されない。そして、このライトサイクルでは、プ
レゼンスビットＰＢ，一致信号ＥＱ，ヒット信号ＨＩ
Ｔ，フル信号ＦＬ及び入力選択信号ＦＣによってリード
ライト信号Ｗ／バーＲ・Ｈ，Ｗ／バーＲ・Ｃ，ＦＩＦＯ
メモリ６１１の書き込み信号ＷＲＦ及びセット信号Ｓ／
バーＲが制御部６０６で生成される。この真理値表を図
１３に示す。これにより、ハッシュメモリ６０１及び連
想メモリ部６０２に、入力されたパケットを書き込むか
否かを定め、下記の如くの動作をする。

【００２５】図１３の（１）は１入力命令が与えられた
場合を示し、ハッシュメモリ６０１の内容を何ら更新す
ることなく１オペランドデータがそのまま出力される。
図１３の（２）〜（７）は２入力命令が与えられた場合
を示し、データを出力するか否かは各種の条件により定
まる。（２）はハッシュメモリ６０１の入力パケットに
より定められたハッシュアドレスにデータが格納されて
おり（ＰＢ＝１）、それがハッシュ衝突を起こすことが
なかった（ＥＱ＝１）場合を示す。ハッシュメモリ６０
１と連想メモリ部６０２とに重複してデータが格納され
ることはないので、この場合、ＣＡＭ２０１がヒットす
ることはない（ＨＩＴ＝０）。このとき、ライトサイク
ルにおいてはハッシュメモリ６０１のプレゼンスビット
ＰＢをリセットする必要があるのでリードライト信号Ｗ
／バーＲ・Ｈ＝１，セット信号Ｓ／バーＲ＝０とする。
連想メモリ部６０２には手を加える必要がないので、リ
ードライト信号Ｗ／バーＲ・Ｃ＝０とする。入力された
パケットはハッシュメモリ６０１の内容と発火したの
で、ライトサイクルの終了と同時にデータ出力信号Ｃ１
を出力する。図１３の（３）及び（４）は、ハッシュメ
モリ６０１に有効なデータが格納されていたが、それが
ハッシュ衝突を起こした場合を示す（ＰＢ＝１，ＥＱ＝
０）。そして（３）ではＣＡＭ２０１でもヒットしなか
ったため（ＨＩＴ＝０）、入力されたデータは連想メモ
リ部６０２に格納され（Ｗ／バーＲ・Ｃ＝１，Ｓ／バー
Ｒ＝１）、データの出力は行われない（Ｃ１＝０）。
（４）ではＣＡＭ２０１がヒットしたため（ＨＩＴ＝
１）、入力されたパケットは連想メモリ部６０２の内容
と発火し、出力される（Ｃ１＝１）。ここでＣＡＭ２０
１のプレゼンスビットＰＢがリセットされなければいけ
ないので、リードライト信号Ｗ／バーＲ・Ｃ＝１，セッ
ト信号Ｓ／バーＲ＝０とされる。（５）及び（６）はハ
ッシュメモリ６０１に有効なデータが格納されていなか
った場合であり（ＰＢ＝０）、一致信号ＥＱの値に意味
はない。（５）ではＣＡＭ２０１がヒットしなかった場
合を示し（ＨＩＴ＝０）、入力されたパケットはハッシ
ュメモリ６０１に書き込まれる（Ｗ／バーＲ・Ｈ＝１，
Ｓ／バーＲ＝１，Ｃ１＝０）。（６）ではＣＡＭ２０１
がヒットしており、（４）と同様な操作を行う。また、
（７）はハッシュメモリ６０１に有効なデータが格納さ
れていたが、それがハッシュ衝突を起こし（ＰＢ＝１，
ＥＱ＝０）、連想メモリ部６０２に格納する必要が生じ
たが、ＣＡＭ２０１が満杯となり全アドレスが有効とな
った場合（ＦＬ＝１）を示し、入力されたパケットはＦ
ＩＦＯメモリ６１１に所定時間バッファリングされる
（ＷＲＦ＝１）。図１３を参照して上述した動作は全て
ライトサイクルにおけるものであり、ライトサイクル以
外の動作ではリードライト信号Ｗ／バーＲ・Ｈ，Ｗ／バ
ーＲ・Ｃは常に“０”となっている。

【００２６】これらの動作で発火することが判明したパ
ケット及びデータはデータ対形成器６０７に送られ、オ
ペランド対パケットが形成されて出力される。このよう
にマッチングメモリ部ＭＭにハッシュメモリ６０１と連
想メモリ部６０２とを併用し、両者の読み出しを同時に
行うことにより、ハッシュ衝突の如何に拘らず同じ速度
で処理ができ、制御も図１３に示した如く簡潔に行え
る。

【００２７】

【発明が解決しようとする課題】以上のように従来、ハ
ッシュメモリを用いたマッチングメモリでは、ハッシュ
衝突時のパケットの待避領域として連想メモリを用い、
かつデータ検索時にはハッシュメモリと連想メモリを同
時にアクセスすることにより、高速なデータ検索を可能
としていた。しかしながら、ハッシュメモリの物理的な
不良に対しては何の対策もなされていなかった。すなわ
ち、ハッシュメモリ上のあるワードに製造工程上の問題
等で１ビットでもビット不良が生じたときには、そのビ
ットを含むワードが不良アドレスとなって使用できず、
不良チップとして処分されるので、ハッシュメモリの歩
留まりが低下する。半導体メモリでは、製造工程におけ
るビット不良発生は避けがたい問題であり、これに起因
する歩留まり低下は重要な問題となっている。特に、図
３に示したデータ駆動形マイクロプロセッサのようなＶ
ＬＳＩチップの場合は、その影響が非常に大きい。

【００２８】この発明は上記のような問題点を解決する
ためになされたもので、ハッシュメモリの不良による歩
留まり低下を抑えることができる記憶装置を得ることを
目的とする。

【００２９】

【課題を解決するための手段】この発明は、ハッシュメ
モリを用いると共に、ハッシュ衝突時の待避領域を備え
た記憶装置において、上記ハッシュメモリ内に存在する
不良アドレスを記憶する記憶手段と、上記ハッシュメモ
リをアクセスするハッシュアドレスと上記記憶手段に記
憶された不良アドレスを比較する比較手段と、この比較
結果に基づきハッシュアドレスが不良アドレスと一致す
るときはハッシュ衝突が生じたものと見做す制御手段と
を備えたものである。

【００３０】

【作用】この発明においては、ハッシュアドレスが不良
アドレスを示すときはハッシュ衝突が生じたものと見做
して、ハッシュメモリに対するアクセスを禁止し、従来
からあるハッシュ衝突時の待避領域をアクセスするよう
制御する。従って、半導体製造時に生じたメモリ不良が
１ハッシュアドレス，あるいは２〜３のハッシュアドレ
ス以内の領域に納まっていれば、これを直ちに不良チッ
プとせずに済み、ハッシュメモリの不良による歩留まり
低下を抑えることができる。

【００３１】

【実施例】以下、この発明の一実施例を図について説明
する。図１は、本発明を図６に示した従来のマッチング
メモリ部ＭＭに適用した一実施例を示すブロック図であ
り、同一符号を付した部分は重複するのでその説明は省
略する。図において、１は製造時のアセンブリテストや
システム立ち上げ時のセルフテスト等で既知の不良アド
レスを格納するためのＮＧ（不良）レジスタ（記憶手
段）であり、ここでは、ハッシュアドレスと同一ビット
幅の不良アドレスを格納するための９ビットの他に、不
良ビットが存在する場合は“１”，存在しない場合は
“０”が設定される１ビットを最上位ビット（ＭＳＢ）
に有する計１０ビットからなる。２は上記ＮＧレジスタ
１に格納された不良アドレス９ビットと演算器１０１に
より生成されたハッシュアドレス９ビットをビット単位
に比較して、両者が一致するか否かを検出する不良検出
器（比較手段）であり、それぞれ対応するビットが入力
される９個のＥＸＯＲ（排他的論理和）ゲートと、それ
らの出力が入力されるＮＯＲゲートから実現でき、その
出力はハッシュアドレスが不良アドレスに一致するとき
は“１”、一致しないときは“０”となる。３は上記不
良検出器２の出力とＮＧレジスタ１のＭＳＢが入力され
るＡＮＤゲートであり、両者が“１”のとき，すなわち
ハッシュアドレスが不良アドレスと一致し，かつ不良ビ
ットが存在したとき“１”となるＮＧ信号が出力され、
この信号が制御部６０６に入力される。

【００３２】本実施例は、以上のように、従来技術の図
６に示したマッチングメモリ部ＭＭに、ＮＧレジスタ
１，不良検出器２，ＡＮＤゲート３を付加したものであ
り、制御部６０６には新たにＮＧ信号が与えられるが、
その制御内容は図２に示す真理値表の通りとなる。図１
３に示した従来のものに（８）〜（１０）が追加された
形になっているが、これらは従来からの（３），
（４），（７）に示すプレゼンスビットＰＢが“１”で
あり、かつ一致信号ＥＱが“０”の場合，すなわちハッ
シュ衝突時と同じである。したがって、ＮＧ信号とＰＢ
の論理和をとるＯＲゲート，ＮＧ信号の反転をとるＮＯ
Ｔゲート，及びこの出力と一致信号ＥＱの論理積をとる
ＡＮＤゲートからなる簡単な論理回路により実現でき
る。なお、制御部６０６は従来のままとし、上述したよ
うな論理回路を外部に設けて、その出力信号を各々プレ
ゼンスビットＰＢ，一致信号ＥＱとして制御部６０６に
与えるように構成することも可能である。また、ＮＧレ
ジスタ１に１ビット余分なビットを設けて不良ビットが
存在するか否かを設定できるようにし、これと不良検出
器２の出力の論理積をとるＡＮＤゲート３を設けたの
は、アドレスの比較のみでは不良ビットがない場合にも
ハッシュアドレスの何れかがレジスタ値と一致してしま
い、使用可能な領域が１ワード分少なくなってしまう不
具合をなくすためであるが、記憶容量が大きくて１ワー
ドの減少を無視できるような場合は、これらの構成を省
略することも可能である。

【００３３】次に動作について説明する。ハッシュメモ
リに不良ビットが存在する場合に不良ビットが含まれる
アドレスは、全アドレスに対し読み出し，書き込みテス
トを行うことによって容易に知ることが可能である。こ
こで知り得た不良アドレスは、当該ハッシュメモリを含
むシステム，ここではデータ駆動形計算機の立ち上げ時
に、図１中のＮＧレジスタ１に格納される。ＮＧレジス
タ１は、前述したように、ハッシュアドレスより１ビッ
トだけ大きなビット幅を有しており、不良ビットが存在
するならば１ビット余ったビット（ここではＭＳＢとす
る）に“１”が、それ以降の領域に不良アドレスが格納
される。不良ビットが存在しなければＭＳＢには“０”
が格納される。システム動作中、ハッシュアドレスが不
良ビットを含むワードを指示したときＮＧ信号が“１”
となり、それ以外ではＮＧ＝０となる。それぞれの場合
における動作は、図２に示す真理値表の通りである。す
なわち、ＮＧ＝１の場合、ハッシュメモリ６０１は常に
ハッシュ衝突を起こしたものと見做される。言い換えれ
ば、ＮＧ＝１の場合、ハッシュメモリ６０１の存在は無
視される。

【００３４】従って、半導体製造時に生じたメモリ不良
が１ハッシュアドレス，あるいは２〜３のハッシュアド
レス以内の領域に納まっていれば、これを直ちに不良チ
ップとせずに済み、ハッシュメモリの不良による歩留ま
り低下を抑えることができる。なお、上記実施例では、
説明を分かり易くするためもあってメモリ不良が１ハッ
シュアドレスの場合について示したが、複数アドレスの
不良に対応可能とするには、ＮＧレジスタ１，不良検出
器２等を複数セット設ければ良い。

【００３５】また、上記実施例では、ハッシュメモリ内
に存在する不良アドレスを記憶する記憶手段としてレジ
スタを用いた場合について示したが、ＰＲＯＭ，ＥＰＲ
ＯＭ，ＥＥＰＲＯＭ等の不揮発性メモリを用いることも
可能である。

【００３６】更に、上記実施例では、この発明の記憶装
置をデータ駆動形計算機のマッチングメモリ部に適用し
た場合を説明したが、この発明はこれに限るものではな
く、キーワード等の識別子によりデータ検索を行う一般
的なマッチングメモリ等において、ハッシュメモリを用
いると共に、ハッシュ衝突時の待避領域を備えた記憶装
置に対して適用できることは言うまでもない。

【００３７】

【発明の効果】以上のように、この発明によれば、ハッ
シュメモリを用いると共に、ハッシュ衝突時の待避領域
を備えた記憶装置において、上記ハッシュメモリ内に存
在する不良アドレスを記憶する記憶手段と、上記ハッシ
ュメモリをアクセスするハッシュアドレスと上記記憶手
段に記憶された不良アドレスを比較する比較手段と、こ
の比較結果に基づきハッシュアドレスが不良アドレスと
一致するときはハッシュ衝突が生じたものと見做す制御
手段とを備えたので、ハッシュメモリの不良による歩留
まり低下を抑えることができる効果がある。

【図面の簡単な説明】

【図１】この発明の一実施例を示すブロック図である。

【図２】図１のマッチングメモリ部のライトサイクルの
真理値表を示す図である。

【図３】データ駆動形計算機の全体構成例を示すブロッ
ク図である。

【図４】データ駆動形計算機で実行するプログラム（デ
ータフローグラフ）の一例を示す図である。

【図５】データ駆動形計算機で図４に示すプログラムを
実行した場合のパケットの変遷を示す図である。

【図６】従来のマッチングメモリ部の構成例を示すブロ
ック図である。

【図７】従来のデータパケットの一例を示す図である。

【図８】従来のハッシュメモリの構成例を示す図であ
る。

【図９】従来の連想メモリ部の構成例を示すブロック図
である。

【図１０】従来のデータ対形成器の構成例を示すブロッ
ク図である。

【図１１】従来のマッチングメモリ部の概略動作を説明
するフローチャートである。

【図１２】従来のマッチングメモリ部の動作サイクルの
説明図である。

【図１３】従来のマッチングメモリ部のライトサイクル
の真理値表を示す図である。

【符号の説明】

１ＮＧレジスタ（記憶手段）２不良検出器（比較手段）３ＡＮＤゲート１０１演算器６０１ハッシュメモリ６０２連想メモリ部６０３一致検出器６０４ヒット検出器６０５出力セレクタ６０７データ対形成器６０６制御部（制御手段）

Claims

【特許請求の範囲】【請求項１】ハッシュメモリを用いると共に、ハッシ
ュ衝突時の待避領域を備えた記憶装置において、上記ハ
ッシュメモリ内に存在する不良アドレスを記憶する記憶
手段と、上記ハッシュメモリをアクセスするハッシュア
ドレスと上記記憶手段に記憶された不良アドレスを比較
する比較手段と、この比較結果に基づきハッシュアドレ
スが不良アドレスと一致するときはハッシュ衝突が生じ
たものと見做す制御手段とを備えたことを特徴とする記
憶装置。