JPH04344568A - マイクロプロセッサのデータ登録、探索方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、テーブルを用いたデー
タ登録、探索方式に関し、特に、ハッシュ法におけるハ
ッシュテーブルを構成して行なうマイクロプロセッサの
データ登録、探索方式に関する。

【０００２】

【従来の技術】従来のハッシュ法におけるハッシュテー
ブルの構成では、ハッシュ関数の値の最小値と最大値の
範囲の大きさのハッシュテーブルを用意し、ハッシュテ
ーブルの各項目に探索データへのポインタを格納してい
る。そして、探索データが持つ探索キーからハッシュ関
数を用いてハッシュテーブルのアドレスを得て、目的の
ハッシュテーブル中の探索データへのポインタを参照し
ている。

【０００３】

【発明が解決しようとする課題】上述した従来のハッシ
ュ法におけるハッシュテーブルの構成では、登録すべき
探索データが持つ探索キーの集合が既知でない場合は、
探索データが持つ探索キーからハッシュ関数を用いて得
たハッシュテーブルのアドレスの衝突を少なくするため
に、大きな範囲の値をとるハッシュ関数が必要となり、
それにともないハッシュテーブルも大きくしなくてはい
けない。しかし、登録した探索データの数が少なかった
場合は、ハッシュテーブルの大きさに対する登録した探
索データの個数の割合が小さくなり、ハッシュテーブル
に無駄な領域が多数存在する、という課題があった。

【０００４】また、データ登録、探索の高速化のために
は、例えばリロケーション方式のリロケーションレジス
タのような特別なハードウェアを用意する場合があるが
、ハードウェアを用意できない場合は、データ登録、探
索の高速化が難しい、という課題もあった。

【０００５】本発明は上述の課題を解決するもので、特
別なハードウェアを用意する必要がなく、ハッシュテー
ブルに無駄な領域を確保する必要のないマイクロプロセ
ッサのデータ登録、探索方式を得ることを目的とする。

【０００６】

【課題を解決するための手段】本発明のデータ登録、探
索方式では、探索データが持つ探索キーからハッシュ関
数を用いて得るハッシュアドレスと、プログラム実行に
必要なアドレス変換テーブルと共存させるために仮想ア
ドレス空間中の未使用領域をハッシュアドレスとして確
保するハッシュテーブルと、このハッシュテーブルのア
ドレス変換情報をもとにマイクロプロセッサのアドレス
変換機能を利用して前記ハッシュアドレスをアドレス変
換して得られる格納アドレスと、この格納アドレスを探
索データを格納している仮想アドレスとして再度前記ア
ドレス変換テーブル中のプログラムの実行に必要なアド
レス変換情報を用いてアドレス変換して得られる探索デ
ータを格納している実アドレスとを有する。

【０００７】

【作用】本発明のマイクロプロセッサのデータ登録、探
索方式においては、探索データが持つ探索キーからハッ
シュ関数を用いて得たハッシュアドレスを、マイクロプ
ロセッサのアドレス変換機能を利用して、アドレス変換
テーブル中のハッシュテーブルとしてのアドレス変換情
報によって格納アドレスにアドレス変換して、この格納
アドレスを再度仮想アドレスとみなし、アドレス変換テ
ーブル中のプログラムの実行に必要な探索データを格納
している実アドレスに変換するので効率的なテーブル作
成ができる。

【０００８】

【実施例】次に、本発明について図面を参照して説明す
る。

【０００９】図１は本発明の一実施例であるマイクロプ
ロセッサのデータ登録、探索方式の概要図である。

【００１０】図１から、探索データが持つ探索キー１か
らハッシュ関数２を用いて得たハッシュアドレス３を、
マイクロプロセッサのアドレス変換機能を利用して、ア
ドレス変換テーブル７中のハッシュテーブル（４）とし
てのアドレス変換情報により格納アドレス４に変換し、
その格納アドレス４を探索データを格納している仮想ア
ドレス５として再度マイクロプロセッサのアドレス変換
機能により探索データを格納したプログラム実行に必要
な実アドレス６として変換する様に構成されている。

【００１１】図２は、本発明のマイクロプロセッサのア
ドレス変換機能のブロック図である。

【００１２】図２において、２０１はアドレス変換機能
を備えた一般的なマイクロプロセッサであり、ここで機
能する仮想アドレスをたとえば３２ビットとしてその仮
想空間は４Ｇバイトの大きさで、さらに１つのセクショ
ンはＩＧバイトの大きさを持ち複数のエリアから成り、
１つのエリアはＩＭバイトの大きさで複数のページから
成り、１つのページは４Ｋバイトの大きさだとする。

【００１３】命令実行部２０５からアクセス要求がある
と、アドレス変換部２０３の内部にあるエリアテーブル
のエリアテーブルベースレジスタが変換すべき仮想アド
レスのポインタによって選択される、これは３２ビット
中の上位２ビット分等に相当するものとする、これと、
選択されたレジスタに保持されているエリアテーブルベ
ースアドレスと変換すべき仮想アドレスのエリア番号に
よって主記憶２０２上のエリアテーブルエントリが選択
され、主記憶制御部２０４によって読み込まれ、読み込
まれたエリアテーブルエントリ内のページテーブルベー
スレジスタと変換すべき仮想アドレスのページ番号によ
り主記憶２０２上のページテーブルエントリが選択され
、主記憶制御部２０４に読み込まれる、読み込まれたペ
ージテーブルエントリ内の実ページ番号と変換すべき仮
想アドレスのページ下位ビット部が連接されて実アドレ
スとなる様に機能する。

【００１４】図３は、本発明のマイクロプロセッサのデ
ータ登録、探索方式の説明図であり、３は３２ビットと
して表示されるハッシュアドレス、４はハッシュアドレ
ス３に対応して変換されるハッシュテーブルによる格納
アドレスであり、１０はマイクロプロセッサ２０１のア
ドレス変換機能２０３におけるエリアテーブルレジスタ
である。１２は同じくエリアテーブル、１３はページテ
ーブル、１１はアドレス変換動作としてのエリア加算器
であり、１４は同じくページ加算器である。

【００１５】図４は、本発明の探索データの格納例を示
す図である。

【００１６】ａはハッシュアドレス空間、ｂは格納アド
レス空間、ｃは仮想アドレス空間として３記憶空間の関
係を表わす、探索データ０×３ｆｆｆｆ、０×２０００
０、０×０００００は３２ビット空間域の３ビットに対
応している、図５は、本発明の探索データの探索成功の
例を示す図である。

【００１７】図６は、本発明の探索失敗の例を示す図で
ある。

【００１８】次に動作について説明する。

【００１９】ここでは、本発明の一実施例として、サイ
ズが４Ｇバイトの仮想アドレス空間中の最上位１Ｇバイ
トとして図４に示す番地（０×ｃ０００００００番地か
ら０×ｆｆｆｆｆｆｆｆ番地）が未使用仮想アドレスの
場合に、サイズが４Ｋバイトの探索データの探索、登録
、削除を行なう例を用いて説明する。

【００２０】図３から、探索データが持つ探索キー１か
らハッシュ関数２を用いて、上位２ビットに０ｂ１１、
中位１８ビットに探索データが持つ探索キーによって一
意に決まる値（０×０００００から０×３ｆｆｆｆ）、
下位１２ビットに０×０００、からなる３２ビットの値
をハッシュアドレス３として得る。さらに、ハッシュア
ドレス３が、マイクロプロセッサ２０１のアドレス変換
機能を利用して、あらかじめ用意した、アドレス変換テ
ーブル７中のハッシュテーブル（４）としてのアドレス
変換情報を用いて、格納アドレス４にアドレス変換され
る機能上の変換手順は、上位２ビット０ｂ１１は、エリ
アテーブルレジスタペア１０のレジスタを選択保持し、
エリヤ番号とエリア加算器１１で加算してエリアテーブ
ルエントリアドレスを得てこれから１８ビットについて
もページテーブルベースとページ番号をページ加算器１
３により加算してページテーブルエントリアドレスを得
て最後に下位１２ビットを連接して格納アドレス４に変
換される。

【００２１】今、ハッシュ関数２を用いて得たハッシュ
アドレス３の中位１８ビットの値が、０×０００００か
ら０×３ｆｆｆｆの値を取る探索キー１を持つ探索デー
タをそれぞれ、探索データ０×０００００から探索デー
タ０×３ｆｆｆｆとし、すでに、探索データ０×０００
００、探索データ０×２００００、探索データ０×３ｆ
ｆｆｆが登録されている場合を考える。

【００２２】プログラムの実行に必要なコード部、デー
タ部と探索データ０×０００００、探索データ０×２０
０００、探索データ０×３ｆｆｆｆは、図４Ｃのように
、仮想アドレス空間ｃに配置されているとする。その時
、格納アドレス空間ｂ中には、図ｂのように、探索デー
タ０×０００００、探索データ０×２００００、探索デ
ータ０×３ｆｆｆｆを、仮想アドレス空間ｃと同じアド
レスに配置する。さらに、ハッシュアドレス空間ａ中に
は、図ａのように、探索データ０×０００００、探索デ
ータ０×２００００、探索データ０×３ｆｆｆｆを、各
探索データが持つ探索キーからハッシュ関数２を用いて
得たハッシュアドレス３に配置する。そして、探索デー
タ０×０００００、探索データ０×２００００、探索デ
ータ０×３ｆｆｆｆのハッシュアドレス３を対応する各
探索データの格納アドレス４へ割り付けるハッシュテー
ブル（４）としてのアドレス変換情報を、アドレス変換
テーブル７中に作成する。

【００２３】ここで図５を参照して探索例を示すと、図
４の状態で、すでに登録されている探索データ０×２０
０００を探索しようとする場合は、探索データ０×２０
０００が持つ探索キー１からハッシュ関数２を用いて得
たハッシュアドレス３（０×ｅ０００００００番地）を
、マイクロプロセッサ２０１のアドレス変換機能を利用
して、あらかじめ用意した、アドレス変換テーブル７中
のハッシュテーブル（４）としてのアドレス変換情報を
用いて、アドレス変換を行なえば、探索データ０×２０
０００が格納されている仮想アドレス５と同じアドレス
の格納アドレス４（０×ｂｆｆｆｅ０００番地）を得ら
れることがわかる。このあと仮想アドレス５をマイクロ
プロセッサ２０１のアドレス変換機能を利用して実アド
レス６に変換すればプログラム実行ができる。

【００２４】また未登録、探索データの場合は、図６に
示すように、図４の状態で、図示されてないまだ登録さ
れていない探索データを仮りに０×２０００１としてこ
れを探索しようとする場合は、探索データ０×２０００
１が持つ探索キー１からハッシュ関数２を用いて得たハ
ッシュアドレス３（０×ｅ０００１０００番地とすると
）を、マイクロプロセッサ２０１のアドレス変換機能を
利用して、あらかじめ用意した、アドレス変換テーブル
７中のハッシュテーブル（４）としてのアドレス変換情
報を用いて、アドレス変換を行なうことになり、実アド
レス６が割り付けられていない仮想アドレス５を参照し
ようとした場合にメモリ管理例外が発生するのと同様に
、格納アドレス４が割り付けられていないハッシュアド
レス３を参照しようとすることになるため、メモリ管理
例外が発生して探索の失敗を検出できることがわかる。

【００２５】また、図４の状態で、まだ登録されていな
い探索データ０×２０００１を登録しようとする場合は
、探索データ０×２０００１が持つ探索キー１から探索
データ０×２０００１の探索が成功するよう、すなわち
、探索データ０×２０００１が持つ探索キー１からハッ
シュ関数２を用いて得たハッシュアドレス３（０×ｅ０
００１０００番地）を、マイクロプロセッサ２０１のア
ドレス変換機能を利用して、あらかじめ用意した、アド
レス変換テーブル中７のハッシュテーブル（４）として
のアドレス変換情報を用いて、アドレス変換を行なえば
、探索データ０×２０００１を格納している仮想アドレ
ス５と同じ格納アドレス４（０×ｅ０００１０００番地
）に変換できるよう、アドレス変換テーブル７中のハッ
シュテーブル（４）としてのアドレス変換情報を変更す
れば可能である。

【００２６】同様に、図４の状態で、すでに登録されて
いる探索データ０×２００００を削除しようとする場合
は、探索データ０×２００００が持つ探索キー１から探
索データ０×２００００の探索が失敗するよう、すなわ
ち、探索データ０×２００００が持つ探索キー１からハ
ッシュ関数２を用いて得たハッシュアドレス３（０×ｅ
０００００００番地）を、マイクロプロセッサ２０１の
アドレス変換機能を利用して、あらかじめ用意した、ア
ドレス変換テーブル７中のハッシュテーブル（４）とし
てのアドレス変換情報を用いて、アドレス変換を行なう
際に、格納アドレス４が割り付けられていないハッシュ
アドレス３を参照になるため、メモリ管理例外が発生し
て探索の失敗を検出できるよう、アドレス変換テーブル
７中のハッシュテーブル（４）としてのアドレス変換情
報を変更すれば削除可能である。

【００２７】

【発明の効果】以上説明したように本発明では、仮想ア
ドレス空間中の未使用仮想アドレスの領域と、マイクロ
プロセッサのアドレス変換機能を利用して、あらかじめ
用意した、アドレス変換テーブル中のハッシュテーブル
としてのアドレス変換情報を用いて、ハッシュアドレス
から格納アドレスへアドレス変換を行なうことにより、
登録すべき探索データが持つ探索キーの集合が既知でな
い場合でも、ハッシュテーブルであるアドレス変換テー
ブルの大きさは、登録した探索データの個数に応じて可
変となるため、登録した探索データの個数にかかわらず
、ハッシュテーブルに無駄な領域ができない、という効
果がある。さらに、特別なハードウェアがなくとも、マ
イクロプロセッサのアドレス変換機能のためのハードウ
ェアを利用するため、高速なデータの探索を行なうこと
が可能となる、という効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例であるマイクロプロセッサの
データ登録、探索方式の概要図である。

【図２】本発明のマイクロプロセッサのアドレス変換機
能のブロック図である。

【図３】本発明のマイクロプロセッサのデータ登録、探
索方式の説明図である。

【図４】本発明の探索データ格納例を示す図である。

【図５】本発明の探索データの探索成功の例を示す図で
ある。

【図６】本発明の探索データの探索失敗の例を示す図で
ある。

【符号の説明】

１　　　　探索キー ２　　　　ハッシュ関数 ３　　　　ハッシュアドレス ４　　　　格納アドレス （４）　　　　ハッシュテーブル ５　　　　仮想アドレス ６　　　　実アドレス ７　　　　アドレス変換テーブル ２０１　　　　マイクロプロセッサ ２０３　　　　アドレス変換部

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　探索データが持つ探索キーからハッシ
   ュ関数を用いて得るハッシュアドレスと、プログラム実
   行に必要なアドレス変換テーブルと共存させるために仮
   想アドレス空間中の未使用領域を前記ハッシュアドレス
   として確保するハッシュテーブルと、このハッシュテー
   ブルのアドレス変換情報をもとにマイクロプロセッサの
   アドレス変換機能を利用して前記ハッシュアドレスをア
   ドレス変換して得られる格納アドレスと、この格納アド
   レスを探索データを格納している仮想アドレスとして再
   度前記アドレス変換テーブル中のプログラムの実行に必
   要なアドレス変換情報を用いてアドレス変換して得られ
   る探索データを格納している実アドレスとを有するマイ
   クロプロセッサの登録、探索方式。