JPH0731601B2 - 情報処理装置 - Google Patents

Description

【発明の詳細な説明】 ［技術分野］ この発明は、情報処理技術さらにはオブジェクト指向言
語で書かれたプログラムを実行するマイクロプロセッサ
に適用して有効な技術に関し、例えばスモールトーク
（Small talk）と呼ばれる言語で動くマイクロプロセッ
サにおけるメソッド（手続き）の探索方式に利用して有
効な技術に関する。

［背景技術］ オブジェクト指向言語を用いたプログラミングでは、デ
ータとそのデータに対する手続きが一体になったオブジ
ェクトなどのオブジェクトを単位としてプログラムが組
み立てられる。

オブジェクト指向言語で書かれたプログラムでは、メッ
セージ送信を基本操作としている。メッセージ送信では
メソッドとの結合の問題となる。従来のメソッド結合ア
ルゴリズムでは、メッセージ送信が起こるとメッセージ
の受け手をスタックから取り出し、メッセージ内のメッ
セージ・セレクタと受け手のクラスからハッシュ関数に
よりハッシュ値求め、このハッシユ値によって第１図に
示すようにメソッド・キャッシュと呼ばれるテーブルMC
を引いてメソッドを探す。そして、メソッド・キャッシ
ュMC内にメソッドがあればメソッド・ハンドルとプリミ
ティブ指標とを使って実行するコードを求める。プリミ
ティブ指標の値が０ならばメソッド・ハンドルが指すオ
ブジェクトの中のメソッドのコード領域からバイトコー
ド（命令コード）を順次読み出して実行していく。

しかも、メソッド・ハンドルを用いてオブジェクトの中
からメソッドを読み出す場合、メソッド・ハンドルを使
ってオブジェクト・テーブルOTを引いて、必要とするプ
ロシージャ（メソッド・オブジェクト）MOを探さなけれ
ばならない（［株］岩波書店、1985年６月24日発行、
「岩波講座マイクロエレクトロニクス７ プログラミン
グ言語とVLSI」第148頁〜160頁参照）。

このように、従来のメソッド探索方式は、実行するコー
ドを求めるのに非常に時間がかかり、プログラムの実行
速度が遅いという問題点があった。

［発明の目的］ この発明の目的は、オブジェクト指向言語で書かれたプ
ログラムを実行するマイクロプロセッサにおけるプログ
ラム実行速度の向上を図ることにある。

この発明の前記ならびにそのほかの目的と新規な特徴に
ついては、本明細書の記述および添附図面から明らかに
なるであろう。

［発明の概要］ 本願において開示される発明のうち代表的なものの概要
を説明すれば、下記の通りである。

すなわち、オブジェクト指向言語で書かれたプログラム
を実行する場合、局所的には同一のメソッド（もしくは
プロシージャ）が頻繁に呼び出されることが多いという
現象（プログラムの局所性）に着目し、メソッド・キャ
ッシュ内に、メソッドの実行コードの位置を示す物理ア
ドレス等、メソッドの属性を入れるフィールドを設け、
一度呼び出されたメソッドが再度呼び出されるときに
は、メソッド・キャッシュ内の情報に基づいてメソッド
・オブジェクトから直接実行コードを読み出して実行で
きるようにし、しかも、これをマイクロプログラムによ
って実行できるようにして、プログラムの実行速度を向
上させるという上記目的を達成するものである。

［実施例］ 第２図には、本発明をオブジェクト指向言語のうち一例
としてスモールトーク（Small talk）で書かれたプログ
ラムにおけるメソッド探索に適用した場合の一例が示さ
れている。

この実施例では、外部メモリ上に割り付けられたメソッ
ド・キャッシュと呼ばれるテーブルMC上に、メソッド探
索用のフィールドT0,T1,‥‥Tnが配列されている。各フ
ィールドTiには、４つの領域がそれぞれ設けられてお
り、最初の領域にはメッセージの受け手のクラス名が入
る。次の領域にはメッセージ・セレクタが、また３番目
の領域には第１図に示すメソッド・キャッシュと同様に
通常はメソッドハンドルが、そして、最後の４番目の領
域には通常はプリミティブ指標がそれぞれ入るようにさ
れている（フィールドT0参照）。

しかして、この実施例では、プログラムの局所性に鑑み
て、一度呼び出されたメソッドについては、メソッド・
キャッシュMC内の各フィールドの３番目と４番目の領域
に、メソッド・ハンドルおよびプリミティブ指標の代わ
りに、そのメソッドの属性を入れるようにされている。
ここで、メソッドの属性とは、例えば、次に実行れる命
令のコードの入っている番地を示す物理アドレス（以
下、インストラクション・アドレスと称する）やメソッ
ドの頭部の番地を指す物理アドレス（以下、ヘッダ・ア
ドレスと称する）がある（フィールドT1参照）。

上記の場合、インストラクション・アドレス領域にはフ
ラグＭを設けて、このフラグＭが「１」のときはプリミ
ティブ指標に対応するマイクロプログラムのエントリ・
アドレスが入っていることを示す。また、フラグＭが
「０」のときは、求めるメソッド内のバイトコードの入
っているコード領域の先頭アドレスが入っていることを
示すようにする。

上記実施例に従うと、一度呼び出されたメソッドについ
ては、メソッド・キャッシュMC内にその実行コードを指
す物理アドレスが入っているので、再びそのメソッドを
探索する場合には、ハッシュ値によってメソッド・キャ
ッシュMCを引くことにより、直ちに求めるメソッドを呼
び出すことができる。

これに対し、従来のメソッドサーチ方式では、第１図に
示したように、メソッド・キャッシュMCによってオブジ
ェクト・テーブルOTを引いてメソッドを呼び出す必要が
ある。しかも、メソッド・キャッシュ内のクラスが指す
データ領域内のクラス辞書（第２図参照）をセレクタを
指標にして探しても求めるメソッドが見つからなけれ
ば、そのクラスのスーパクラスのメッセージ辞書を探
す、というようにして次々とスーパクラスを遡って行く
必要があった。

そのため、上記実施例では、メソッド・キャッシュによ
って直ちに実行コードが得られることが非常に多くな
り、メソッド探索に要する時間が大幅に短縮される。

ただし、上記実施例においても、未だ一度も呼び出され
ていないメソッドを探索する際には、従来と同じように
オブジェクト・テーブルを用いてメソッドを呼び出す必
要がある。しかるに、プログラムの局所性から、そのよ
うな探索はまれにしか生じない。

なお、上記実施例の場合、メソッドもメモリ上に形成さ
れるオブジェクトの一種であるので、ガーベッジ・コレ
クションの対象となる。ガーベッジ・コレクションが実
行される場合、メモリの高効率化のため空き領域を結合
するコンパクションによって、メソッドの物理アドレス
も変更されることがある。そのため、メソッド・キャッ
シュMC内にあるインストラクション・アドレス等は使用
できなくなる。従って、その場合には、メソッド・キャ
ッシュMC内のフィールドの３番目と４番目の領域を書き
直して、元のメソッド・ハンドルおよびプリミティブ指
標を入れる。すなわち、本実施例のようにオブジェクト
テーブルを備える場合、コンパクションによってメソッ
ドオブジェクトの物理アドレスが変更されても、その変
更点は当該メソッドオブジェクトに対応されるオブジェ
クトテーブル上のメソッドアドレスに反映されれば充分
であり、オブジェクトテーブル上で当該メソッドアドレ
スに至るためのメソッドハンドルやプリミティブ指標に
変更を要しない。そうであるから、メソッドアドレス変
更のためにオブジェクトテーブルをたどる情報から元の
メソッド・ハンドル及びプリミティブ指標を得て、これ
を変更前のインストラクションアドレスを持つメッソド
探索用フィールドに入れることができる。そして、この
ように元のメソッド・ハンドル及びプリミティブ指標が
戻された後、そのフィールドの参照があった場合には、
改めてオブジェクト・テーブルを引いてメソッドを呼び
出すとともに、そのとき得られたヘッダや実行コードの
物理アドレスをメソッド・キャッシュ内に書き込んでや
ればよい。

上記のようなメソッド探索のアルゴリズムを実現する場
合、従来はマイクロプログラムによって実行するように
していた。そのため、そのプログラムをコンパイルする
のにも時間を要するので、ますますメソッドの探索に要
する時間が長くなっていた。

そこで本発明者らは、上記メソッド探索のアルゴリズム
をマイクロプロセッサ内部のマイクロプログラムで実現
することを考えた。第４図には、メソッド探索をマイク
ロプログラムで実行する場合のフローの一実施例が示さ
れている。

この実施例では、先ず適当なハッシュ関数ｆを用いて、
メッセージの受け手のクラスとメッセージ・セレクタと
から、例えばその排他的論理和をとるような演算を行っ
てハッシュ値を求め、メソッド・キャッシュのベース値
（メソッド・キャッシュの先頭アドレス）とからメソッ
ド・キャッシュを参照するためのエントリー・アドレス
を得る（ステップS1）。次に、このアドレスを用いてメ
ソッド・キャッシュ内のそのアドレス位置にあるデータ
が、受け手のクラスと等しいかチェックする（ステップ
S2）。この場合、（ ）はダイレクト・アドレッシング
であることを示す。

ステップS2で、指示されたデータがクラスと等しいと判
定されるとステップS3へ進み、ここで、アドレスを１つ
更新して、メソッド・キャッシュ内の次の領域に入って
いるデータがメッセージ・セレクタと等しいか判定され
る。

等しい場合すなわちキャッシュが成功した場合には、そ
のクラスの中に求めるメソットジがあり、そのメソッド
の物理アドレスはセレクタの入っている領域の次の領域
に入っていることが分かっているので、最初のアドレス
値に「２」をプラスしてメソッド・キャッシュをアクセ
スし、メソッドの物理アドレスを読み出すことができ
る。

一方、ステップS2とS3においてクラスまたはセレクタが
一致しないと判定されると、スーパクラスへ遡り、その
スーパクラスでのキャッシュに失敗すると更にその上の
スーパクラスへ遡る必要がある。しかして、スーパクラ
スがない場合にはそのクラスのチェインの最後にこれを
識別するための特別な値（NiLと称する）が入ってい
る。

そこで、ステップS4では、クラスの最後にこのNiLがあ
るかないかを見てスーパクラスがあるか判定し、スーパ
クラスがないときはエラーとする。スーパクラスがあっ
たときは、ステップS5へ進み、そのスーパクラスを新し
いクラスとしてその中で辞書を探す。（辞書はクラス内
の２番目のフィールドに入っている（第３図参照）の
で、スーパクラスの先頭アドレスに、「１」を加え
る。）また、ステップS5では辞書を探すための準備作業
（Ｄ→I,サイズ→Max）を行う。ステップS6→S7→S8→S
6は、辞書を探すループであり、このループ内のステッ
プS6でセレクタが一致したと判定されると、それによっ
てメソッドのアドレスが分かるので探索は終了する。

しかして、クラス内の辞書をすべて捜してもメソッドが
見つからないときは、ステップS7からステップS9へ進み
スーパクラスを次のクラスとする処理を行う。そして、
再びステップS4へ戻って、上記手順を繰り返すことによ
り次々とスーパクラス内の辞書を捜す。

上記フローに従ってマイクロプログラムを記述すること
により、容易にメソッド探索のアルゴリズムが実現され
る。これによって、メソッド探索はマイクロプログラム
で実行されるようになるので、従来のマイクロプログラ
ムによる方式に比べて高速の探索が可能になる。

なお、上記実施例では、メソッド・キャッシュが外部メ
モリ上に割り付けられていると説明したが、それに限定
されるものでなく、マイクロプロセッサLSIのチップ上
に形成された大容量レジスタ上に割り付けるようにして
もよい。

［効果］ メソッド・キャッシュ内に、呼び出されるメソッドの実
行コードの物理アドレス等、メソッドの属性を入れるフ
ィールドを設けたので、一度呼び出されたメソッドが再
度呼び出されるときには、メソッド・キャッシュ内の情
報に基づいてメソッド・オブジェクトから直接実行コー
ドを読み出して実行できるという作用により、オブジェ
クト指向言語で書かれたプログラムを実行するマイクロ
プロセッサにおけるプログラム実行速度が向上される。
しかも、上記メソッド探索アルゴリズムをマイクロプロ
グラムで実現するようにしたので、さらにメソッド探索
に要する時間が短縮されるという効果がある。

以上本発明者によってなされた発明を実施例に基づき具
体的に説明したが、本発明は上記実施例に限定されるも
のではなく、その要旨を逸脱しない範囲で種々変更可能
であることはいうまでもない。例えば、上記実施例で
は、スモールトーク（Small talk）で書かれたプログラ
ムを実行可能なマイクロプロセッサに適用した場合につ
いて説明したが、スモールトーク（Small talk）以外の
オブジェクト指向言語で書かれたプログラムにおいて、
プロシージャと呼ばれる手続きを探索する場合に適用す
ることができる。

［利用分野］ 以上の説明では主として本発明者によってなされた発明
をその背景となった利用分野であるオブジェクト指向言
語で書かれたプログラムを実行するマイクロプロセッサ
に適用した場合について説明したが、この発明はそれに
限定されず、テーブルを用いたデータの探索を行う情報
処理システム一般に利用することができる。

【図面の簡単な説明】

第１図は、従来のメソッド探索方式の一例を示す説明
図、 第２図は、本発明に係るメソッド探索方式の一例を示す
説明図、 第３図は、メソッド・キャッシュにおける辞書の参照方
式を示す説明図、 第４図は、本発明に係るメソッド探索アルゴリズム実現
するマイクロプログラムのフローの一実施例を示すフロ
ーチャートである。 MC……テーブル（メソッド・キャッシュ）、OT……オブ
ジェクトテーブル、MO……メソッド・オブジェクト、TO
〜Tn……フィールド。

Claims (2)

【特許請求の範囲】
1. 【請求項１】オブジェクト指向言語で書かれたプログラ
   ムを実行可能な情報処理装置であって、そのアドレス空
   間には、メッセージの受け手の種類とメッセージの一部
   とを指標としてメッセージに対応して呼び出されるべき
   手続きを含むオブジェクトを探索するための第１テーブ
   ルと、プログラム実行のために呼び出されるべき手続き
   を含む複数のオブジェクトの所在を示す第２テーブルと
   を備え、 前記第１テーブルは、探索の指標とされる上記メッセー
   ジの受け手の種類及びメッセージの一部と共に、当該指
   標に対応して呼び出されるべき手続きを含むオブジェク
   トの所在を示す情報に至る第２テーブルの指標を格納
   し、一度呼び出された手続きに対してはその手続きを含
   むオブジェクトの所在に対応される上記第２テーブルの
   指標に代えて、当該手続きを保有する領域の所在を示す
   情報を格納する領域を有して成るものであることを特徴
   とする情報処理装置。
2. 【請求項２】上記手続きの探索を制御するためのマイク
   ロプログラムを有するものであることを特徴とする特許
   請求の範囲第１項記載の情報処理装置。