JP2006085300A

JP2006085300A - データ処理方法、データ処理装置及びコンピュータプログラム

Info

Publication number: JP2006085300A
Application number: JP2004267528A
Authority: JP
Inventors: Masahiro Yasugi; 昌宏八杉
Original assignee: Kansai Technology Licensing Organization Co Ltd
Current assignee: Kansai Technology Licensing Organization Co Ltd
Priority date: 2004-09-14
Filing date: 2004-09-14
Publication date: 2006-03-30
Anticipated expiration: 2024-09-14
Also published as: JP4719859B2

Abstract

【課題】コピー方式のＧＣ処理等のデータを再配置する処理において、ページ、キャッシュ等の様々なサイズに対して局所性に優れた配置を実現するデータ処理方法、データ処理装置及びコンピュータプログラムを提供する。
【解決手段】走査したデータオブジェクトにより指されている他のデータオブジェクトを配置する位置の限界となる目標を夫々のレベル毎に設定し、配列されているデータオブジェクトに対して第１のレベルの走査を行い、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が目標に達している場合に、第１のレベルより優先順位が低い第２のレベルの走査を行う事により、局所性に優れた配置を実現する。
【選択図】図３

Description

本発明は、走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベル夫々について、列の先頭側から後方側へと走査し、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加するデータ処理方法、該データ処理方法を適用したデータ処理装置、及び該データ処理装置を実現するためのコンピュータプログラムに関し、特にコピー方式のゴミ集め（ＧａｒｂａｇｅＣｏｌｌｅｃｔｉｏｎ）に適用することにより、効率の良いメモリ管理を行うデータ処理方法、データ処理装置及びコンピュータプログラムに関する。

自動的なメモリ領域の管理を行うゴミ集め（ＧａｒｂａｇｅＣｏｌｌｅｃｔｉｏｎ：以下ＧＣという）を用いることで、プログラマはメモリ領域管理の負担から解放されアルゴリズムに関する記述等の本質的な作業に専念することができる。またＧＣを用いることで明示的なメモリ領域管理を行うよりも効率の良いプログラムの実行が可能な場合もある。

代表的なＧＣの一つであるコピー方式のＧＣでは、Ｆｒｏｍスペースと呼ばれるメモリ領域に記録されているデータの中で、今後アクセスされる可能性のある（生きている）データのみをＴｏスペースと呼ばれるメモリ領域にコピーし、Ｆｒｏｍスペースのメモリ領域を、再利用することが可能なメモリ領域として確保する。

コピー方式のＧＣの代表的な方法として、非特許文献１に記載されている方法がある。図１４は従来のコピー方式のＧＣ処理を概念的に示すメモリマップである。図１４（ａ）はＦｒｏｍスペースとして用いられるメモリ領域を示し、図１４（ｂ）はＴｏスペースとして用いられるメモリ領域を示している。各メモリ領域中には、四角形にて示すデータオブジェクトが記録されており、一方のデータオブジェクトに含まれる記憶単位であるワードが他方のデータオブジェクトを指す参照関係については、その関係を矢印により示している。またｓとして示した矢印は、Ｔｏスペースとなるメモリ領域に設定され、走査するデータオブジェクトを指示するスキャンポインタであり、ｂとして示した矢印は、Ｔｏスペースの空き領域の先頭を指示するフリーポインタである。

Ｔｏスペースにおいては、記録されているデータオブジェクトに含まれるワードを先頭側から後方側へ、図１４（ｂ）中の左方から右方へと走査を行い、走査に伴いスキャンポインタが右方へ移動する。走査したワードがＦｒｏｍスペースに記録されているデータオブジェクトを指している場合、指されているＦｒｏｍスペースのデータオブジェクトをフリーポインタの位置にコピーし、フリーポインタを右方へ移動させる。そしてスキャンポインタがフリーポインタに追いついた時点で、今後アクセスされる可能性のあるデータが全てＴｏスペースへコピーされたと判定する。

上述の非特許文献１に記載されている方法を、データオブジェクト間の参照関係が木構造をなす構成のデータオブジェクト群に適用する場合、Ｔｏスペースには幅優先順と呼ばれる順番で夫々のデータオブジェクトが配置される。図１５は従来のコピー方式のＧＣ処理によるデータオブジェクトの配置を概念的に示す説明図である。図１５（ａ）は木構造をなすデータの関係を示しており、図１５（ｂ）は幅優先順でコピーされたデータオブジェクトの配置を示している。なお図１５（ａ）において、データオブジェクトに付された番号は、Ｔｏスペース内に配置される順番を示している。また図１５（ａ）及び図１５（ｂ）において矢印は各データオブジェクト間の参照関係を示している。

また幅優先順と異なる順番でデータオブジェクトを配置する方法として、深さ優先順と呼ばれる順番で夫々のデータオブジェクトを配置する方法がある。図１６は従来のコピー方式のＧＣ処理によるデータオブジェクトの配置を概念的に示す説明図である。図１６（ａ）は木構造をなすデータオブジェクトの関係を示しており、図１６（ｂ）は深さ優先順でコピーされたデータオブジェクトの配置を示している。なお図１６（ａ）において、Ｔｏスペース内の接近した記録位置に配置されるデータオブジェクト同士を一点鎖線で囲んでいる。また図１６（ａ）及び図１６（ｂ）において矢印は各データオブジェクト間の参照関係を示している。

さらに非特許文献２には、関連するデータの位置が接近するようにグループ化（クラスタリング）して配置する方法を用いたコピー方式のＧＣが開示されている。図１７は従来のコピー方式のＧＣ処理を概念的に示すメモリマップである。図１７はＴｏスペースとして用いられるメモリ領域を示しており、ｓとして示した矢印はスキャンポインタであり、ｂとして示した矢印はフリーポインタを示している。また非特許文献２に開示された方法では、未走査データオブジェクトの先頭を指示するスキャンポインタと、空き領域の先頭及び未走査データの末尾を指示するフリーポインタと以外に、ｐとして示す未走査データオブジェクトの一部を指す部分使用ページ内走査ポインタを用いる。なお図中の破線は、記録領域の区切りであるページの境界を示している。

非特許文献２に示す方法では、スキャンポインタとフリーポインタとの間の走査より優先的に、部分使用ページ内走査ポインタとフリーポインタとの間の走査を行う。そしてデータのコピー先となる位置を示すフリーポインタが、部分使用ページ内走査ポインタと異なるページにまで移動した場合、部分使用ページ内走査ポインタをフリーポインタと同じページの先頭を示す位置を指示するように再設定する。部分使用ページ内走査ポインタがフリーポインタに追いついた場合、スキャンポインタが指示する位置から走査を行う。

非特許文献２に示す方法では、スキャンポインタは部分使用ページ内走査ポインタによる走査を既に行っているデータオブジェクトを再度走査する可能性を有するが、参照関係を有するデータオブジェクト同士は同じページとなる可能性が高くなる。即ち参照元のデータオブジェクトと参照先のデータオブジェクトとをできるだけ同一のページに置くことが可能となる一方で、夫々のページの内部では幅優先順のコピーが行われることとなる。

図１８は従来のコピー方式のＧＣ処理によるデータの配置を概念的に示す説明図である。図１８では、上述の非特許文献２に示される様に関連するデータの位置が接近するようにグループ化して配置する方法を、データ間の参照関係が木構造をなす構成のデータオブジェクト群に適用する場合のデータオブジェクトの配置を示している。
チーニイ(Cheney)，非再帰的リスト圧縮アルゴリズム(A NonrecursiveList Compacting Algorithm)，「コミュニケーションズ・オブ・ジ・エイ・シー・エム(Communications of the ACM.)」,（米国），Vol.13，No.11，pp.677-678，1970 ムーン(Moon)，大規模リスプシステムでのゴミ集め(Garbage Collection in a Large Lisp System,Proc.of Conference on Lisp and Functional Programming) ，「リスプと関数プログラミングに関する国際会議予稿集（Proc.ofConference on Lisp and Functional Programming）」,（米国），pp235-246,1984,Aug

しかしながら従来の非特許文献１に記載されているように幅優先順にデータオブジェクトを配置する方法では、参照関係にあるデータオブジェクト同士が離れた位置に配置されることが多く、ＧＣ処理自体及びＧＣ完了後の計算において、データオブジェクトに対するメモリアクセスの局所性が劣化するという問題がある。これは応用プログラムでは、多くの場合、データオブジェクトへの参照を幅優先順に辿ることはないからである。

また従来の深さ優先順にデータオブジェクトを配置する方法では、幅優先順と比較してメモリアクセスの局所性は一部改善されるが、処理時に必要となるスタックは、最悪の場合、生きているデータオブジェクトの個数に比例するという問題がある。また例えば図１５（ａ）に示すような関係でデータオブジェクトを配置した場合、図１５（ａ）中、左方向に参照されるデータオブジェクトについての局所性は優れているが、右方向に参照されるデータオブジェクトについての局所性は劣っているという問題がある。

さらに従来の非特許文献２に記載された方法では、参照元のデータオブジェクトと参照先のデータオブジェクトとをできるだけ同一のページに置くことを目的としている一方で、夫々のページの内部については幅優先順での配置が行われる。従ってページ単位でメモリ及びディスク間のデータ転送や仮想アドレスから実アドレスへの変換を行う仮想記憶の面からは局所性に優れているが、キャッシュの面からは局所性が劣っているという問題がある。

本発明は斯かる事情に鑑みてなされたものであり、順次配列されるデータオブジェクトを優先順位が付与された複数の階層レベルでグループ化すべく、階層レベル毎に目標を設定し、第１の階層レベルについて走査し、走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加え、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替え、第１の階層レベルについての走査の対象がなくなった場合、第１の階層レベルの目標を再設定し、第１の階層レベルの優先順位が最低であるとき、処理を中断し、第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替えることにより、局所性に優れた配置、特に一つのサイズに限らず、ページ、キャッシュ等の様々なサイズに対して局所性に優れた配置を実現するデータ処理方法、該データ処理方法を適用したデータ処理装置、及び該データ処理装置を実現するためのコンピュータプログラムの提供を目的とする。

即ち本発明では、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置する位置の限界となる目標を夫々のレベル毎に設定し、配列されているデータオブジェクトに対して第１のレベルの走査を行い、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が目標に達している場合に、第１のレベルより優先順位が低い第２のレベルの走査を行う事により、局所性に優れた配置を実現するデータ処理方法、該データ処理方法を適用したデータ処理装置、及び該データ処理装置を実現するためのコンピュータプログラムの提供を目的とする。

第１発明に係るデータ処理方法は、走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベル夫々について、列の先頭側から後方側へと走査し、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加するデータ処理装置を用いたデータ処理方法であって、第１の階層レベルの目標を所定の計算方法で設定後、第１の階層レベルについて走査し、走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加え、配列後、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替え、第１の階層レベルについての走査の対象がなくなった場合、第１の階層レベルの目標を再設定し、第１の階層レベルの優先順位が最低であるとき、処理を中断し、第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替えることを特徴とする。

本発明では、データオブジェクトが、複数の階層レベル毎にグループ化された状態で配列されるので、局所性に優れた配置、特に様々なデータ転送の単位、アドレス変換の単位に対しても局所性に優れ、更にはキャッシュ場所の競合に関しても優れた配置を実現することが可能である。

第２発明に係るデータ処理方法は、第１発明において、前記第１の階層レベルの目標の所定の計算方法は、目標設定時の次に配列する位置から第１の階層レベルについて決められた一定距離後方の位置を求める計算方法、又は目標設定時の次に配列する位置から後方に第１の階層レベルについて決められた最初の区切り位置を求める計算方法であることを特徴とする。

本発明では、階層レベル毎に決められている一定距離後方の位置に目標を決定することにより、例えばキャッシュ場所の競合に関して優れた配置を実現することが可能であり、また最初の区切り位置に目標を決定することにより、例えば様々なデータ転送の単位、アドレス変換の単位の局所性に優れた配置を実現することが可能である。

第３発明に係るデータ処理方法は、第１発明又は第２発明において、一のレベルで走査したデータオブジェクトに対しては、他のレベルでの走査を省略することを特徴とする。

本発明では、多重の走査を回避することで、全体としての処理速度を向上させることが可能である。

第４発明に係るデータ処理方法は、第１発明乃至第３発明のいずれかにおいて、前記走査中の第１のデータオブジェクトが第２のデータオブジェクトを指しているときの所定の条件とは、第２のデータオブジェクトがまだ配列されていないという条件であることを特徴とする。

本発明では、データオブジェクトの再配列に利用して、局所性に優れた配置を実現する。

第５発明に係るデータ処理方法は、第１発明乃至第４発明のいずれかにおいて、前記目標に適合しているかどうかの判定が予めできる部分についてはその走査を省略することを特徴とする。

本発明では、走査を省略することにより、全体としての処理速度を向上させることが可能である。

第６発明に係るデータ処理方法は、メモリ領域に順次配列されるデータオブジェクトを、順次配列された列の先頭側から後方側へ、夫々優先順位を付した複数のレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指されている他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置するデータ処理装置を用いたデータ処理方法であって、指されている他のデータオブジェクトを配置する位置の限界として、所定の計算方法を用いて求められたレベル毎の目標を設定し、配列されているデータオブジェクトに対して第１のレベルの走査を行い、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が、第１のレベルに対して設定された目標に達しているか否かを判定し、目標に達していると判定した場合、第１のレベルの走査を中断して、第１のレベルより優先順位が低い第２のレベルの走査を行い、走査に基づいて配置された他のデータオブジェクトの位置が、レベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定し、走査に基づいて他のデータオブジェクトを配置した後、最も優先順位が高いレベルの走査を行うことを特徴とする。

本発明では、優先順位が付与されたレベル毎に設定された目標に応じた様々なサイズでグループ化された状態で配列されるので、局所性に優れた配置、特に様々なデータ転送の単位、アドレス変換の単位に対しても局所性に優れ、更にはキャッシュ場所の競合に関しても優れた配置を実現することが可能である。

第７発明に係るデータ処理方法は、第６発明において、前記所定の計算方法は、当該レベルの前回の目標からの論理的なアドレス上の距離が、レベル毎に設定された優先順位の高い方が低い方以下となる所定値である位置を計算する方法、又は先頭に配置されているデータオブジェクトの位置からの論理的なアドレス上の距離が、所定値である位置を計算する方法であることを特徴とする。

本発明では、前回の目標からの距離が所定値である位置に目標を決定することにより、例えば様々なデータ転送の単位、アドレス変換の単位の局所性に優れた配置を実現することが可能であり、また先頭からの距離が所定値である位置を目標とすることにより、例えばキャッシュ場所の競合に関して優れた配置を実現することが可能である。

第８発明に係るデータ処理方法は、第７発明において、前記所定値を示す数値の受付又は設定読み取りを行うことを特徴とする。

本発明では、データ処理装置が備える各種メモリ領域の仕様に応じたサイズでグループの区分を設定することにより、様々な仕様のいずれに対しても局所性に優れた配置を実現することが可能であり、しかも仕様の変更、移植等の設計変更を要する状況下においても容易に対応することが可能である。

第９発明に係るデータ処理方法は、第６発明乃至第８発明のいずれかにおいて、一のレベルで走査したデータオブジェクトに対しては、他のレベルでの走査を省略することを特徴とする。

第１０発明に係るデータ処理装置は、走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベル夫々について、列の先頭側から後方側へと走査し、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加するデータ処理装置であって、第１の階層レベルの目標を所定の計算方法で設定後、第１の階層レベルについて走査する手段と、走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加える手段と、配列後、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替える手段と、第１の階層レベルについての走査の対象がなくなった場合、第１の階層レベルの目標を再設定する手段と、第１の階層レベルの優先順位が最低であるとき、処理を中断する手段と、第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替える手段とを備えることを特徴とする。

第１１発明に係るデータ処理装置は、一又は複数の記録手段を備え、該記録手段に確保されたメモリ領域に順次配列されるデータオブジェクトを、順次配列された列の先頭側から後方側へ、夫々優先順位を付した複数のレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指されている他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置するデータ処理装置であって、指されている他のデータオブジェクトを配置する位置の限界として、所定の計算方法を用いて求められたレベル毎の目標を設定する手段と、配列されているデータオブジェクトに対して第１のレベルの走査を行う手段と、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が、第１のレベルに対して設定された目標に達しているか否かを判定する手段と、目標に達していると判定した場合、第１のレベルの走査を中断して、第１のレベルより優先順位が低い第２のレベルの走査を行う手段と、走査に基づいて配置された他のデータオブジェクトの位置が、レベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定する手段と、走査に基づいて他のデータオブジェクトを配置した後、最も優先順位が高いレベルの走査を行う手段とを備えることを特徴とする。

本発明では、階層レベル毎に決められている一定距離後方の位置に目標を決定することにより、例えば様々なデータ転送の単位、アドレス変換の単位の局所性に優れた配置を実現することが可能であり、また最初の区切り位置に目標を決定することにより、例えばキャッシュ場所の競合に関して優れた配置を実現することが可能である。

第１２発明に係るコンピュータプログラムは、コンピュータに、走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベルの夫々について、列の先頭側から後方側へと走査させ、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加させるコンピュータプログラムであって、コンピュータに、第１の階層レベルの目標を所定の計算方法で設定後、第１の階層レベルについて走査させる手順と、コンピュータに、走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加えさせる手順と、コンピュータに、配列後、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替えさせる手順と、第１の階層レベルについての走査の対象がなくなった場合、コンピュータに、第１の階層レベルの目標を再設定させる手順と、コンピュータに、第１の階層レベルの優先順位が最低であるとき、処理を中断させる手順と、コンピュータに、第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替えさせる手順とを実行させることを特徴とする。

本発明では、コンピュータにて実行することにより、コンピュータがデータ処理装置として動作し、データオブジェクトが、複数の階層レベル毎にグループ化された状態で配列されるので、局所性に優れた配置、特に様々なデータ転送の単位、アドレス変換の単位に対しても局所性に優れ、更にはキャッシュ場所の競合に関しても優れた配置を実現することが可能である。

第１３発明に係るコンピュータプログラムは、一又は複数の記録手段を備えるコンピュータに、記録手段に確保されたメモリ領域に順次配列されるデータオブジェクトを、順次配列された列の先頭側から後方側へ、夫々優先順位を付した複数のレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指されている他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置させるコンピュータプログラムであって、コンピュータに、指されている他のデータオブジェクトを配置する位置の限界として、所定の計算方法を用いて求められたレベル毎の目標を設定させる手順と、コンピュータに、配列されているデータオブジェクトに対して第１のレベルの走査を行う手順と、コンピュータに、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が、第１のレベルに対して設定された目標に達しているか否かを判定させる手順と、コンピュータに、目標に達していると判定した場合、第１のレベルの走査を中断して、第１のレベルより優先順位が低い第２のレベルの走査を行わせる手順と、コンピュータに、走査に基づいて配置された他のデータオブジェクトの位置が、レベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定させる手順と、コンピュータに、走査に基づいて他のデータオブジェクトを配置した後、最も優先順位が高いレベルの走査を行わせる手順とを実行させることを特徴とする。

コンピュータにて実行することにより、コンピュータがデータ処理装置として動作し、階層レベル毎に決められている一定距離後方の位置に目標を決定することにより、例えば様々なデータ転送の単位、アドレス変換の単位の局所性に優れた配置を実現することが可能であり、また最初の区切り位置に目標を決定することにより、例えばキャッシュ場所の競合に関して優れた配置を実現することが可能である。

本発明に係るデータ処理方法、データ処理装置及びコンピュータプログラムでは、順次配列される走査対象に優先順位を付した複数の階層レベル夫々について走査し、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加する。このとき各階層レベルに対して目標を設定し、第１の階層レベルについて走査し、走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指しており、そのデータオブジェクトを次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加える。第１の階層レベルの優先順位が最高でない場合、最高の優先順位が付けられた階層レベルについての走査へと処理を切り替え、第１の階層レベルについての走査の対象がなくなった場合、第１の階層レベルの目標を再設定し、第１の階層レベルの優先順位が最低であるとき、処理を中断し、第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替える。

この構成により、参照元となる第１のデータオブジェクトと、参照先となる第２のデータオブジェクトとが同じブロック（転送単位）に配置される可能性が高まり、また、アクセス頻度の高い複数のデータオブジェクトが貯え場所が競合するアドレスに配置されない様になる可能性が高くなることから、参照を辿ることによりデータへのアクセスの際に、最近のデータブロック転送結果の貯え、或いはアドレス変換結果の蓄えが再利用される確率が高くなり、平均アクセス時間を短縮することが可能である等、優れた効果を奏する。

本発明に係るデータ処理方法、データ処理装置及びコンピュータプログラムでは、メモリ領域に順次配列されるデータオブジェクトを、夫々優先順位が付されたレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指している他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置する。このとき他のデータオブジェクトを配置する位置の限界として、レベル毎に目標を設定しておき、他のデータオブジェクトを配置すべき位置が目標に達している場合、当該レベルより優先順位が低いレベルの走査を行う。また配置したデータオブジェクトの位置がレベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定する。

この構成により、一方のデータオブジェクトが他方のデータオブジェクトを指す参照関係にあるデータオブジェクト同士を同じブロック（転送単位）に配置する可能性を高め、またアクセス頻度の高い複数のデータオブジェクトが貯え場所が競合するアドレスに配置されない様になる可能性が高くなることから、参照関係を辿るデータへのアクセスの際に、最近のデータブロック転送結果の貯え、或いはアドレス変換結果の蓄えが再利用される確率が高くなり、平均アクセス時間を短縮することが可能である等、優れた効果を奏する。

以下、本発明をその実施の形態を示す図面に基づいて詳述する。

図１は本発明のデータ処理装置の構成を示すブロック図である。図１中１０は汎用コンピュータ等のコンピュータを用いた本発明のデータ処理装置であり、データ処理装置１０は、装置全体を制御するＣＰＵ１１、本発明のコンピュータプログラム２０及びデータ等の各種情報を記録するＣＤ−ＲＯＭ等の記録媒体から、各種情報を読み取るＣＤ−ＲＯＭドライブ等の補助記憶手段１２、並びに補助記憶手段１２により読み取った各種情報を記録するハードディスク１３及びＲＡＭ１４を備え、ＣＰＵ１１、補助記憶手段１２、ハードディスク１３及びＲＡＭ１４は、バスライン１５により夫々接続されている。さらにＣＰＵ１１は、演算を行う実行部１１ａ、論理アドレスを物理アドレスに変換した結果等の情報の記録に用いられるＴＬＢ（ＴｒａｎｓｌａｔｉｏｎＬｏｏｋ−ａｓｉｄｅＢｕｆｆｅｒ）１１ｂ、並びに一次キャッシュメモリ１１ｃを備え、更にＣＰＵ１１とバスライン１５との間には２次キャッシュメモリ１６が配設されている。

そして記録媒体から補助記憶手段１２により読み取った本発明のコンピュータプログラム２０等の各種情報を、ハードディスク１３、ＲＡＭ１４、一次キャッシュメモリ１１ｃ、二次キャッシュメモリ１６等の各種メモリ領域に記録して、ＣＰＵ１１の実行部１１ａにより実行することで、コンピュータは本発明のデータ処理装置１０として動作する。なお本発明のコンピュータプログラム２０は単独で実行されるのではなく、Ｊａｖａ（登録商標）、Ｌｉｓｐ、Ｃ＃等のプログラミング言語を用いて作成された主プログラムの実行時に、主プログラムの実行に必要なメモリ管理を補助するプログラムとして実行される。また主プログラムの一部に本発明のコンピュータプログラム２０が含まれている形態でもよい。

主プログラムの実行時には、各種データへのアクセス時に、最近のブロック転送結果、アドレス変換結果等の情報を実行部１１ａに近い一次キャッシュメモリ１１ｃ等の記録手段に貯え、再利用する記憶階層を用いる。最近のブロック転送結果等の情報は、キャッシュブロック、仮想記憶（ＶＭ：ＶｉｒｔｕａｌＭｅｍｏｒｙ）のページ、ファイル等の単位で貯えられる。最近のアドレス変換結果は、例えばＴＬＢ１１ｂ内に貯えられる。

次に本発明のデータ処理装置１０の処理を説明する。本発明のデータ処理装置１０によるデータ処理方法では、仮想メモリ上でデータオブジェクトの再配置を行うものであり、ここではコピー方式のＧＣを実行する場合において、仮想アドレス空間の仮想メモリに確保されたＦｒｏｍスペースのデータオブジェクトの中で、今後アクセスされる可能性のあるデータオブジェクトを仮想アドレス空間の仮想メモリに確保されたＴｏスペースにコピーする形態に適用する場合を例示する。

先ず本発明のデータ処理方法によるデータオブジェクトの配置結果について説明する。図２は本発明のデータ処理方法による配置の対象となる各データオブジェクトの構成を概念的に示す説明図である。図２に示すように本発明の処理方法が適用されるデータオブジェクト群は、一方のデータオブジェクトが他方のデータオブジェクトを指す参照関係を持つことができる。図２では説明を容易にするため各データ間の参照関係により単純な２分木の木構造を構成する形態を例示している。そして木構造を構成するデータオブジェクトを含むデータオブジェクト群は、一の階層レベルに属する一のグループに他の階層レベルに属する複数のグループが含まれるよう入れ子状に設定された各階層レベルの夫々のグループによりグループ化される。図２に示す具体例では、直線にて囲まれたレベル０の階層レベルのグループにより各グループが区分されており、レベル０の階層レベルの複数のグループは、一点鎖線にて囲まれたレベル１の階層レベルの一のグループに含まれ、レベル１の階層レベルのグループによっても各データオブジェクトはグループ化されることが示されている。更にレベル１の階層レベルの複数のグループは、破線にて囲まれたレベル２の階層レベルの一のグループに含まれ、レベル２の階層レベルのグループによっても各データオブジェクトはグループ化されることが示されている。レベルＮ＋１（Ｎは０以上の整数）の階層レベルのグループは、レベルＮの先頭グループとその中の葉に相当するデータオブジェクトから指される複数のレベルＮの階層レベルの後続グループから構成されるようにする。

図３は本発明のデータ処理方法によりメモリ領域に配置したデータオブジェクトを概念的に示すメモリマップである。図３では、レベル０の階層レベルのグループを直線にて示し、レベル１の階層レベルのグループを一点鎖線にて示し、そしてレベル２の階層レベルのグループを破線にて示している。図３に示すように本発明の処理方法にてメモリ領域に配置されたデータオブジェクトは、どの階層レベルのグループにおいても参照関係にあるデータオブジェクトの局所性が優れている。図３に示す具体例では、レベル１の階層レベルの同一のグループに含まれるレベル０の階層レベルの夫々のグループは、参照関係にあるデータオブジェクトが近い位置になるように配置されていることが示されている。更にレベル２の階層レベルの同一のグループに含まれるレベル１の階層レベルの夫々のグループは、先頭グループに続けて、複数の後続グループを並べる様に配置する。

図２及び図３を用いて説明した様に本発明のデータ処理方法により、再配置されたデータオブジェクトは、入れ子状の複数階層でグループ化され、レベルＮ＋１（Ｎは自然数）の階層レベルの同一のグループに含まれるレベルＮの階層レベルの夫々のグループは、参照関係にあるデータオブジェクトを含むグループ同士が近い位置になるように配置される。従って各グループを、１次キャッシュの転送単位に対応するメモリブロック、２次キャッシュの転送単位に対応するメモリブロック、及び仮想記憶のページ等の転送単位、変換単位にできるだけ一致させる。あるいは各グループを１次キャッシュの容量、２次キャッシュの容量以下のサイズになるようにすることで、転送結果や変換結果を再利用する確率が高まり、平均アクセス時間が短縮される。

次に本発明のデータ処理装置１０の処理の具体例について説明する。図４は本発明のデータ処理装置１０の初期化処理を示すフローチャートである。図４に示す初期化処理は、データ処理装置１０が、ＣＰＵ１１の制御により本発明のコンピュータプログラム２０を実行することにより行われる。データ処理装置１０では、各階層レベルのグループにおいてデータオブジェクトを配置する位置の限界となる目標を先頭オブジェクトの位置から計算する計算式の受付又は設定読取を行い（Ｓ１０１）、グループ内を走査する際の走査ポインタをレベル１以上の各階層レベルについて準備し、走査の中断中として再配置先となるメモリ領域の配列の先頭に設定し（Ｓ１０２）、空き領域の先頭の位置を指示するフリーポインタを設定する（Ｓ１０３）。初期化処理とはデータオブジェクトの再配置を行う前に各階層レベルのグループの目標を先頭オブジェクトの位置から計算する計算式の受付又は設定読取を行い設定する処理であり、人為的な操作によりキーボード等の入力手段を用いて入力される計算式を受け付けるようにしても良く、本発明のコンピュータプログラム２０の内部パラメータとして予め設定されている計算式を読み取る様にしても良い。また計算式を予めコンパイルしたり、展開したりしても良い。また設定する計算式としては、そのレベルで着目するブロック区分において、先頭オブジェクトを含むブロックの末尾を結果とする計算式、先頭オブジェクトの位置からそのレベルが着目するグループサイズに相当する一定の距離だけ後方を結果とする計算式、が用いられる。

図５は本発明のデータ処理方法におけるメモリ領域及び各階層レベルのグループを概念的に示すメモリマップである。図５は初期化処理後の状態であり、Ｍとして示した領域がメモリ領域Ｍを示し、ｂとして示した矢印がフリーポインタｂを示している。そしてｓ１として示した矢印がレベル１の階層レベルに対して設定されたスキャンポインタｓ１を示し、ｓ２、ｓ３及びｓ４として示した矢印が夫々レベル２、レベル３及びレベル４の階層レベルに対して夫々設定された走査ポインタｓ２、走査ポインタｓ３及び走査ポインタｓ４を示している。

メモリ領域Ｍ内の破線で示した四角形が配置されるデータオブジェクト列Ｄの先頭データオブジェクトを示しており、データオブジェクト内の黒点が他のデータオブジェクトを指す参照を示している。なお破線にて示す位置にデータオブジェクトＤが配置された後、フリーポインタｂは現在の位置から移動する。Ｌ１として示した破線の半直線及び該半直線に直交する線分が、レベル１の階層レベルのグループに対してデータオブジェクトを配置する位置の限界として設定される目標を示している。図５に示す初期化処理後の状態では、目標は未設定の状態であるが、後述する様に走査の前に所定の計算方法により順次目標が設定される。本発明にて用いられる目標を設定するための計算方法では、そのレベルで着目するブロック区分において先頭のデータオブジェクトを含むブロックの末尾を結果とする計算式による計算結果、及び先頭のデータオブジェクトの位置からそのレベルが着目するグループサイズに相当する一定の距離だけ後方を結果とする計算式による計算結果が設定される目標となる。従って設定されるべき目標間の距離は必ずしも一定ではない。さらにＬ２、Ｌ３及びＬ４として示した破線の半直線及び半直線に直交する線分により、レベル２、レベル３及びレベル４の夫々の階層レベルのグループに設定されるべき目標を示している。

なお本発明の各階層に対して設定された夫々の走査ポインタｓ１、ｓ２、ｓ３、ｓ４には、グループのサイズが小さい階層レベル程優先して走査が行われるように優先順位が設定される。即ちレベル１の階層レベルに対する走査ポインタｓ１が最も優先度が高く、レベル２の階層レベルの走査ポインタｓ２、レベル３の階層レベルの走査ポインタｓ３、そしてレベル４の階層レベルの走査ポインタｓ４の順で優先順位が低くなる。なお夫々の階層レベルに設定されている目標は、固定されたものではなく、配置されるデータオブジェクトが目標に達したとき、また走査の対象がなくなったとき、当該階層レベルの次の目標を設定する。

図６は本発明のデータ処理装置１０のレベル１の階層レベルの走査ポインタｓ１による走査処理を示すフローチャートである。図６に示す走査処理は、データ処理装置１０が、ＣＰＵ１１の制御により本発明のコンピュータプログラム２０を実行することにより行われる。初期化処理の終了後、データ処理装置１０は、走査する階層レベルに対し、データオブジェクトを配置する位置の限界として階層レベルに対応する目標を所定の計算方法を用いて計算し（Ｓ２０１）、計算した目標を階層レベルに対して設定する（Ｓ２０２）。所定の計算方法とは、目標設定時の次に配列する位置から当該階層レベルについて決められた一定距離後方の位置を求める計算方法、又は目標設定時の次に配列する位置から後方に当該階層レベルについて決められた最初の区切り位置までの範囲を求める計算方法である。言い換えれば、当該レベルの前回の目標からの論理的なアドレス上の距離がレベル毎に決められたグループサイズに基づく所定値である位置を計算する方法、又は先頭に配置されているデータオブジェクトの位置からの論理的なアドレス上の距離が、ブロックサイズに基づく所定値である位置を計算する方法であり、前回の目標からの距離が短い方の目標が設定される。なお最初の目標を計算する場合においては前回の目標とは先頭に配置されているデータオブジェクトの位置となる。グループサイズは、優先順位の高い方が低い方以下となる様に階層レベル毎に設定されるサイズであり、ブロックサイズは、転送単位に基づいて設定されるサイズである。

そして第１のメモリ領域に配列されているデータオブジェクトの走査及び該走査に基づくデータオブジェクトの配置が行われるのであるが、最も優先順位が高いレベル１の階層に対する走査ポインタｓ１を用いた走査から開始される。データ処理装置１０では、走査ポインタｓ１が指す場所及びフリーポインタｂが指す場所を比較し（Ｓ２０３）、異なる場所を指している場合（Ｓ２０３：ＮＯ）、走査ポインタｓ１が指す場所（ワード）のデータオブジェクト列Ｄに参照、所謂ポインタが格納されているか否かを判定する（Ｓ２０４）。

ステップＳ２０４において、データオブジェクト列Ｄに参照が含まれていると判定した場合（Ｓ２０４：ＹＥＳ）、データ処理装置１０では、データオブジェクト列Ｄに含まれている参照が指す参照先が、第２のメモリ領域に記録されているデータオブジェクトであるか否かを判定し（Ｓ２０５）、参照が指す参照先が第２のメモリ領域に記録されているデータオブジェクトであると判定したとき（Ｓ２０５：ＹＥＳ）、第２のメモリ領域に記録されている参照先のデータオブジェクトが、既に第１のメモリ領域に配置されているか否かを判定する（Ｓ２０６）。

ステップＳ２０６において、第２のメモリ領域に記録されている参照先のデータオブジェクトが、未だ第１のメモリ領域に配置されていないと判定した場合（Ｓ２０６：ＮＯ）、データ処理装置１０では、参照先のデータオブジェクトを配置すべき場所が目標に達しているか否かを判定する（Ｓ２０７）。即ちステップＳ２０３〜Ｓ２０５の処理にて走査ポインタｓ１が指すワード（場所）のデータオブジェクト列Ｄを走査し、走査したデータオブジェクト列Ｄにより指されている参照先のデータオブジェクトの配置先とすべき、フリーポインタｂが指す位置が、ステップＳ２０２にて当該レベルに対して設定された目標に達しているか否かを判定する。またステップＳ２０７における判定は、既に再配置したデータオブジェクトの位置が目標に達したか否かの判定としても良い。

ステップＳ２０７において、参照先のデータオブジェクトを配置すべき位置が目標に達していないと判定した場合（Ｓ２０７：ＮＯ）、データ処理装置１０では、走査ポインタｓ１が指すデータオブジェクト列Ｄにより指されている、第２のメモリ領域に記録されている参照先のデータオブジェクトを、フリーポインタｂが指す位置、即ち第１のメモリ領域に配列されているデータオブジェクト列Ｄの後側に配置し（Ｓ２０８）、走査ポインタｓ１が指すデータオブジェクト列Ｄにより指される参照先を、新たに配置したデータオブジェクトを指すように置き換える（Ｓ２０９）。ステップＳ２０９にて参照先を置き換えるまでデータオブジェクト列Ｄに指されていた第２のメモリ領域に記録されているデータオブジェクトには、新たな配置先となる第１のメモリ領域を転送先として指す参照を格納する。

そしてデータ処理装置１０では、ステップＳ２０８にて新たに配置したデータオブジェクトの後側の空き領域を指すようにフリーポインタｂを移動し（Ｓ２１０）、レベル１の階層レベルのグループに対する走査ポインタｓ１を１ワード分後側へ移動し（Ｓ２１１）、ステップＳ２０３へ進み、以降の処理を実行する。即ちステップＳ２０８〜Ｓ２１１の処理を行うことにより、走査に基づいてデータオブジェクトを配置した後、当該レベルの階層レベルに対応する走査ポインタｓ１の参照が移動し、新たに指されたワードがステップＳ２０３以降の処理の対象となる。

ステップＳ２０４において、走査ポインタｓ１が指すワードのデータオブジェクト列Ｄに参照が含まれていないと判定した場合（Ｓ２０４：ＮＯ）、データオブジェクトの再配置は不要と判断し、ステップＳ２１１へ進み、以降の処理を実行する。

ステップＳ２０５において、データオブジェクト列Ｄに含まれている参照が指す参照先が、第２のメモリ領域に記録されているデータオブジェクトではないと判定した場合（Ｓ２０５：ＮＯ）、データオブジェクトの再配置は不要であると判断し、ステップＳ２１１へ進み、以降の処理を実行する。

ステップＳ２０６において、データオブジェクト列Ｄにより指される、第２のメモリ領域に記録されている参照先のデータオブジェクトが、既に第１のメモリ領域に配置されていると判定した場合（Ｓ２０６：ＹＥＳ）、データ処理装置１０では、データオブジェクト列Ｄにより指される参照先を、第１のメモリ領域に既に配置されているのデータオブジェクトを指すように置き換え（Ｓ２１２）、ステップＳ２１１へ進み、以降の処理を実行する。

ステップＳ２０７において、参照先のデータオブジェクトを配置すべき位置が目標に達していると判定した場合（Ｓ２０７：ＹＥＳ）、データ処理装置１０では、レベル１の階層レベルに対する走査ポインタｓ１による以降の走査を中断して（Ｓ２１３）、走査ポインタｓ１を、フリーポインタｂの位置まで移動し（Ｓ２１４）、レベル１の階層レベルより一段優先順位の低いレベル２の階層レベルに対応する走査ポインタｓ２による走査処理に進む（Ｓ２１５）。ステップＳ２１４にて走査ポインタｓ１をフリーポインタｂの位置まで移動することにより、移動前の走査ポインタｓ１とフリーポインタｂとの間に配列されているデータオブジェクトに対しては、走査ポインタｓ１による走査を行わないことになるが、これらのデータオブジェクトに対しては、走査ポインタｓ１より優先度が低い走査ポインタｓ２、ｓ３、ｓ４等の走査ポインタにより走査を行う。

ステップＳ２０３において、走査ポインタｓ１が指す場所及びフリーポインタｂが指す場所が一致すると判定した場合（Ｓ２０３：ＹＥＳ）、ステップＳ２１５へ進み、以降の処理を実行する。

図７は本発明のデータ処理装置１０のレベルＮ（Ｎは自然数）の階層の走査ポインタｓＮによる走査処理を示すフローチャートである。図７に示す走査処理は、データ処理装置１０が、ＣＰＵ１１の制御により本発明のコンピュータプログラム２０を実行することにより行われる。レベルＮ（Ｎは２以上の自然数）の階層レベルの走査ポインタｓＮによる走査処理は、レベルＮ−１の階層レベルの走査ポインタｓＮ−１による走査処理において、所定の条件を満足した場合に行われる。例えば図６を用いて示したレベル１の階層レベルの走査ポインタｓ１による走査処理のステップＳ２０７において、参照先のデータオブジェクトを配置すべき位置が目標に達していると判定した場合、又はステップＳ２０３において、走査ポインタｓ１が指す場所及びフリーポインタｂが指す場所が同じであると判定した場合、レベル２の階層レベルの走査ポインタｓ２による走査処理が開始される。

データ処理装置１０は、走査する階層レベルに対し、データオブジェクトを配置する位置の限界として階層レベルに対応する目標を所定の計算方法を用いて計算し（Ｓ３０１）、計算した目標を対応する階層レベルに対して設定する（Ｓ３０２）。所定の計算方法とは、目標設定時の次に配列する位置から当該階層レベルについて決められた一定距離後方の位置までの範囲を求める計算方法、又は目標設定時の次に配列する位置から後方に当該階層レベルについて決められた最初の区切り位置までの範囲を求める計算方法である。言い換えれば、当該レベルの前回の目標からの論理的なアドレス上の距離がレベル毎に決められたグループサイズに基づく所定値である位置を計算する方法、又は先頭に配置されているデータオブジェクトの位置からの論理的なアドレス上の距離が、ブロックサイズに基づく所定値である位置を計算する方法であり、前回の目標からの距離が短い方の目標が設定される。

データ処理装置１０では、走査ポインタｓＮが指す場所及びフリーポインタｂが指す場所を比較し（Ｓ３０３）、異なる場所を指している場合（Ｓ３０３：ＮＯ）、走査ポインタｓＮが指すデータオブジェクト列Ｄに参照、所謂ポインタが格納されているか否かを判定する（Ｓ３０４）。

ステップＳ３０４において、データオブジェクト列Ｄに参照が含まれていると判定した場合（Ｓ３０４：ＹＥＳ）、データ処理装置１０では、データオブジェクト列Ｄに含まれている参照が指す参照先が、第２のメモリ領域に記録されているデータオブジェクトであるか否かを判定し（Ｓ３０５）、参照が指す参照先が第２のメモリ領域に記録されているデータオブジェクトであると判定したとき（Ｓ３０５：ＹＥＳ）、第２のメモリ領域に記録されている参照先のデータオブジェクトが、既に第１のメモリ領域に配置されているか否かを判定する（Ｓ３０６）。

ステップＳ３０６において、第２のメモリ領域に記録されている参照先のデータオブジェクトが、未だ第１のメモリ領域に配置されていないと判定した場合（Ｓ３０６：ＮＯ）、データ処理装置１０では、参照先のデータオブジェクトを配置すべき位置がレベルＮの階層レベルに対して設定された目標に達しているか否かを判定する（Ｓ３０７）。即ちステップＳ３０３〜Ｓ３０５の処理にて走査ポインタｓＮが指す場所のデータオブジェクト列Ｄを走査し、走査したデータオブジェクト列Ｄにより指されている参照先のデータオブジェクトの配置先とすべき、フリーポインタｂが指す位置が、ステップＳ３０２にて当該レベルに対して設定された目標に達しているか否かを判定する。またステップＳ３０７における判定は、既に再配置したデータオブジェクトの位置が目標に達したか否かの判定としても良い。

ステップＳ３０７において、参照先のデータオブジェクトを配置すべき位置が目標に達していないと判定した場合（Ｓ３０７：ＮＯ）、データ処理装置１０では、走査ポインタｓＮが指す場所のデータオブジェクト列Ｄにより指されている、第２のメモリ領域に記録されている参照先のデータオブジェクトを、フリーポインタｂが指す位置、即ち第１のメモリ領域に配列されているデータオブジェクト列Ｄの後側に配置し（Ｓ３０８）、走査ポインタｓＮが指すデータオブジェクト列Ｄにより指される参照先を、新たに配置したデータオブジェクトを指すように置き換える（Ｓ３０９）。ステップＳ３０９にて参照先を置き換えるまでデータオブジェクト列Ｄに指されていた第２のメモリ領域に記録されているデータオブジェクトには、新たな配置先となる第１のメモリ領域を転送先として指す参照を格納する。

そしてデータ処理装置１０では、ステップＳ３０８にて新たに配置したデータオブジェクトの後側の空き領域を指示するようにフリーポインタｂを移動し（Ｓ３１０）、レベルＮの階層レベルのブロックに対する走査ポインタｓＮを１ワード分後側へ移動し（Ｓ３１１）、最も優先度が高いレベル１の階層レベルに対応する走査ポインタｓ１による走査処理に進む（Ｓ３１２）。

ステップＳ３０４において、走査ポインタｓＮが指すデータオブジェクト列Ｄに参照が含まれていないと判定した場合（Ｓ３０４：ＮＯ）、データオブジェクトの再配置は不要と判断し、データ処理装置１０では、レベルＮの階層レベルのグループに対する走査ポインタｓＮを１ワード分後側へ移動し（Ｓ３１３）、ステップＳ３０３へ進み、以降の処理を実行する。

ステップＳ３０５において、データオブジェクト列Ｄに含まれている参照が指す参照先が、第２のメモリ領域に記録されているデータオブジェクトではないと判定した場合（Ｓ３０５：ＮＯ）、データオブジェクトの再配置は不要であると判断し、ステップＳ３１３へ進み、以降の処理を実行する。

ステップＳ３０６において、データオブジェクト列Ｄにより指される、第２のメモリ領域に記録されている参照先のデータオブジェクトが、既に第１のメモリ領域に配置されていると判定した場合（Ｓ３０６：ＹＥＳ）、データ処理装置１０では、データオブジェクト列Ｄにより指される参照先を、第１のメモリ領域に既に配置されているデータオブジェクトを指すように置き換え（Ｓ３１４）、ステップＳ３１３へ進み、以降の処理を実行する。

ステップＳ３０７において、参照先のデータオブジェクトを配置すべき位置が目標に達していると判定した場合（Ｓ３０７：ＹＥＳ）、データオブジェクトの配置を行うと参照関係にあるデータオブジェクト同士がブロックを超えて配置されると判断し、データ処理装置１０では、レベルＮの階層レベルに対する走査ポインタｓＮによる以降の走査を中断して（Ｓ３１５）、走査ポインタｓＮを、フリーポインタｂの位置まで移動し（Ｓ３１６）、レベルＮの階層レベルよりブロックのサイズが一段階大きいレベルＮ＋１の階層に対応する走査ポインタｓＮ＋１による走査処理に進む（Ｓ３１７）。

ステップＳ３０３において、走査ポインタｓＮが指す場所及びフリーポインタｂが指す場所が一致していると判定した場合（Ｓ３０３：ＹＥＳ）、ステップＳ３１７へ進み、以降の処理を実行する。

レベルＮ＋１の処理に進もうとして、レベルＮ＋１が存在しなかった場合、階層的グループ化による再配置全体を終了する。なお最も優先度が低いレベルＮの階層レベルの目標を第２のメモリ領域の末尾に設定するようにしても良い。

図８は本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。図８にて用いられている各種符号は図５と同様であるので、図５を参照するものとし、その説明を省略する。なお黒丸及び矢印は参照関係を示しており、黒丸が付されたデータが矢印により示されているデータを指示している。またＬ１の太線の部分は、走査ポインタｓ１による走査が完了した箇所を示している。図８は、図５の状態から走査を開始し、レベル１の階層レベルに対する走査ポインタｓ１による走査が行われている状態を示している。また図８は、走査ポインタｓ１の走査により、既に第１のメモリ領域Ｍに２ワードのデータオブジェクト列Ｄ４個分が配置されているが、参照先のデータオブジェクトを配置すべきフリーポインタｂが指している位置が目標に達している状態を示している。このため図８に示す状態の後、走査ポインタｓ１による走査は中断（図６のステップＳ２１３）され、走査ポインタｓ１の移動（図６のステップＳ２１４）を行った後、レベル１の階層レベルより優先度が一段階低いレベル２の階層レベルに対応する走査ポインタｓ２による走査が開始（図６のステップＳ２１５）されることになる。

図９は本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。図９にて用いられている各種符号は図５及び図８と同様であるので、図５及び図８を参照するものとし、その説明を省略する。なおＬ２の太線の部分は、走査ポインタｓ２による走査が完了した箇所を示している。ただし二重線で示した箇所は、走査ポインタｓ１により既に走査が完了しているため、走査をスキップしている。走査のスキップは、例えばレベル１で行った走査の記録をレベル２の走査に引き継ぐことにより実行される。図９は、図８の状態の後、レベル２の階層に対応する走査ポインタｓ２による走査を開始され、その走査により新たなデータオブジェクトが第１のメモリ領域Ｍに配置された状態を示している。図９に示す状態の後、フリーポインタｂの位置の移動（図７のステップＳ３１０）、及び走査ポインタｓ２の移動（図７のステップＳ３１１、但しＮ＝１）を行った上で、走査ポインタｓ１による走査が開始（図７のステップＳ３１２）されることになる。

図１０は本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。図１０にて用いられている各種符号は図５、図８及び図９と同様であるので、図５、図８及び図９を参照するものとし、その説明を省略する。図１０は、図９の状態の後、更に走査が進み、走査ポインタｓ２による走査が行われている状態を示している。また図１０では、走査ポインタｓ２が指すデータオブジェクトを配置すべきフリーポインタが指している位置が目標に達している状態を示している。走査ポインタｓ２が指すデータオブジェクト列Ｄにより指されるデータオブジェクトの配置先とすべき位置が目標に達しているため、図１０に示す状態の後、走査ポインタｓ２による走査は中断（図７のステップＳ３１５、但しＮ＝１）され、走査ポインタｓ２の移動（図７のステップＳ３１６）を行った後、レベル２の階層レベルに対応する走査ポインタｓ２による走査が開始（図７のステップＳ３１７）されることになる。

図１１は本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。図１１にて用いられている各種符号は図５、図８乃至図１０と同様であるので、図５、図８乃至図１０を参照するものとし、その説明を省略する。なおＬ３の太線の部分は、走査ポインタｓ３による走査が完了した箇所を示している。図１１は、図１０の状態の後、更に走査が進み、走査ポインタｓ３による走査が行われている状態を示している。また図１１では、走査ポインタｓ３が指すデータオブジェクト列Ｄの位置と、フリーポインタｂが指す位置とがレベル３の階層レベルの同じブロックに含まれていない状態を示している。走査ポインタｓ３が指すデータオブジェクト列Ｄにより指されるデータオブジェクトの配置先とすべき位置が、走査ポインタｓ３とレベル３の階層レベルの異なるブロックに含まれているため、図１１に示す状態の後、走査ポインタｓ３による走査は中断（図７のステップＳ３１５、但しＮ＝２）され、走査ポインタｓ３の移動（図７のステップＳ３１６）を行った後、レベル４の階層レベルに対応する走査ポインタｓ４による走査が開始（図７のステップＳ３１７）されることになる。

図１２は本発明のデータ処理装置１０の第２の記録領域のメモリ領域入替処理を示すフローチャートである。図１２に示すメモリ領域入替処理は、データ処理装置１０が、ＣＰＵ１１の制御により本発明のコンピュータプログラム２０を実行することにより行われる。データ処理装置１０では、図５及び図６を用いて説明した走査処理により、Ｔｏスペースとして用いられる第１のメモリ領域に配列されたデータを全て走査した後、Ｔｏスペースとして用いられている第１のメモリ領域とＦｒｏｍスペースとして用いられる第２のメモリ領域との役割を入れ替える（Ｓ４０１）。このようにしてコピー方式のＧＣ処理が完了する。

次に本発明のデータ処理方法により再配置したデータオブジェクトに対する処理時間の実験結果について説明する。図１３は様々な処理方法により再配置したデータオブジェクトに対する処理時間の結果を示すグラフである。図１３において、横軸は、２分木探索木のデータのノードの数を示し、縦軸は探索時間を示している。図１３はランダムに作成された２分木探索木を構成するデータを各処理方法により再配置し、再配置したデータに対する探索を行ったものである。図１３中○は、本発明のデータ処理方法を用いて再配置を行ったデータに対する実験結果を示している。なお本発明のデータ処理方法の実行において、５段階の階層レベルのグループのサイズを設定している。さらに図１３中●は再配置していない状態のデータに対する実験結果、△は例えば背景技術の非特許文献１として示した幅優先順で再配置した状態のデータに対する実験結果、並びに□及び×は例えば背景技術の非特許文献２として示したグループ化して再配置した状態に対する実験結果であり、□はページをブロックとしてグループ化しており、×はキャッシュブロックについてグループ化している。図１３（ａ）は、ＵｌｔｒａＳＰＡＲＣ−ＩＩｅ（登録商標）の５００ＭＨｚのＣＰＵを備える装置を用いており、グループのサイズとしては、２次キャッシュブロックサイズである６４Ｂ、ページサイズである８ＫＢ、１次キャッシュ容量である１６ＫＢ及び２次キャッシュ容量である２５６ＫＢを設定している。図１３（ｂ）は、Ｐｅｎｔｉｕｍ４（登録商標）の１．７ＧＨｚのＣＰＵを備える装置を用いての実験結果であり、２次キャッシュブロックサイズである１２８Ｂ、ページサイズである４ＫＢ、一次キャッシュ容量である８ＫＢ及び２次キャッシュ容量である２５６ＫＢを設定している。

図１３（ａ）に示す様に、○で示した本発明のデータ処理方法を用いて再配置したデータに対する探索時間が最も短いという結果が得られている。ノード数が３２０００００個（約７３．２ＭＢ）のデータに対する結果では、△で示した幅優先順で再配置した結果と比べて６１％の処理速度の向上が見込めるという結果になった。また×で示したキャッシュ単位でグループ化する方法により再配置した結果と比べても１８％の処理速度の向上が見込めるという結果となっており、複数階層でグループ化する本発明のデータ処理方法の優位性が示された。

さらに図１３（ｂ）に示す実験においても、○で示した本発明のデータ処理方法を用いて再配置したデータに対する探索時間が最も短いという結果が得られている。ノード数が６４０００００個（約１４６．５ＭＢ）のデータに対する結果では、△で示した幅優先順で再配置した結果と比べて１１０％の処理速度の向上が見込めるという結果になった。また×で示したキャッシュ単位でグループ化する方法により再配置した結果と比べても８．５％の処理速度の向上が見込めるという結果となった。

前記実施の形態では、ＧＣ処理を行う場合に本発明のデータ処理方法を適用する形態を示したが、本発明はこれにかぎらず、データを再配置する様々なデータ処理に適用することが可能である。

本発明のデータ処理装置の構成を示すブロック図である。本発明のデータ処理方法による配置の対象となる各データオブジェクトの構成を概念的に示す説明図である。本発明のデータ処理方法によりメモリ領域に配置したデータオブジェクトを概念的に示すメモリマップである。本発明のデータ処理装置の初期化処理を示すフローチャートである。本発明のデータ処理方法におけるメモリ領域及び各階層レベルのグループを概念的に示すメモリマップである。本発明のデータ処理装置のレベル１の階層レベルの走査ポインタによる走査処理を示すフローチャートである。本発明のデータ処理装置のレベルＮ（Ｎは自然数）の階層の走査ポインタによる走査処理を示すフローチャートである。本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。本発明のデータ処理方法におけるメモリ領域及び各階層のグループを概念的に示すメモリマップである。本発明のデータ処理装置の第２の記録領域のメモリ領域入替処理を示すフローチャートである。様々な処理方法により再配置したデータオブジェクトに対する処理時間の結果を示すグラフである。従来のコピー方式のＧＣ処理を概念的に示すメモリマップである。従来のコピー方式のＧＣ処理によるデータオブジェクトの配置を概念的に示す説明図である。従来のコピー方式のＧＣ処理によるデータオブジェクトの配置を概念的に示す説明図である。従来のコピー方式のＧＣ処理を概念的に示すメモリマップである。従来のコピー方式のＧＣ処理によるデータの配置を概念的に示す説明図である。

符号の説明

１０データ処理装置
１１ＣＰＵ
１１ａ実行部
１１ｂＴＬＢ
１１ｃ一次キャッシュメモリ
１２補助記憶手段
１３ハードディスク
１４ＲＡＭ
１５バスライン
１６二次キャッシュメモリ
２０コンピュータプログラム
Ｄデータオブジェクト列
Ｍ第１のメモリ領域
ｂフリーポインタ
Ｌ１レベル１の階層レベルのグループ
Ｌ２レベル２の階層レベルのグループ
Ｌ３レベル３の階層レベルのグループ
Ｌ４レベル４の階層レベルのグループ
ｓ１レベル１の階層レベルに対して設定された走査ポインタ
ｓ２レベル２の階層レベルに対して設定された走査ポインタ
ｓ３レベル３の階層レベルに対して設定された走査ポインタ
ｓ４レベル４の階層レベルに対して設定された走査ポインタ

Claims

走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベル夫々について、列の先頭側から後方側へと走査し、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加するデータ処理装置を用いたデータ処理方法であって、
第１の階層レベルの目標を所定の計算方法で設定後、第１の階層レベルについて走査し、
走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加え、
配列後、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替え、
第１の階層レベルについての走査の対象がなくなった場合、
第１の階層レベルの目標を再設定し、
第１の階層レベルの優先順位が最低であるとき、処理を中断し、
第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替える
ことを特徴とするデータ処理方法。
前記第１の階層レベルの目標の所定の計算方法は、目標設定時の次に配列する位置から第１の階層レベルについて決められた一定距離後方の位置を求める計算方法、又は目標設定時の次に配列する位置から後方に第１の階層レベルについて決められた最初の区切り位置を求める計算方法であることを特徴とする請求項１に記載のデータ処理方法。
一のレベルで走査したデータオブジェクトに対しては、他のレベルでの走査を省略することを特徴とする請求項１又は請求項２に記載のデータ処理方法。
前記走査中の第１のデータオブジェクトが第２のデータオブジェクトを指しているときの所定の条件とは、第２のデータオブジェクトがまだ配列されていないという条件であることを特徴とする請求項１乃至請求項３のいずれかに記載のデータ処理方法。
前記目標に適合しているかどうかの判定が予めできる部分についてはその走査を省略することを特徴とする請求項１乃至請求項４のいずれかに記載のデータ処理方法。
メモリ領域に順次配列されるデータオブジェクトを、順次配列された列の先頭側から後方側へ、夫々優先順位を付した複数のレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指されている他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置するデータ処理装置を用いたデータ処理方法であって、
指されている他のデータオブジェクトを配置する位置の限界として、所定の計算方法を用いて求められたレベル毎の目標を設定し、
配列されているデータオブジェクトに対して第１のレベルの走査を行い、
走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が、第１のレベルに対して設定された目標に達しているか否かを判定し、
目標に達していると判定した場合、第１のレベルの走査を中断して、第１のレベルより優先順位が低い第２のレベルの走査を行い、
走査に基づいて配置された他のデータオブジェクトの位置が、レベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定し、
走査に基づいて他のデータオブジェクトを配置した後、最も優先順位が高いレベルの走査を行う
ことを特徴とするデータ処理方法。
前記所定の計算方法は、当該レベルの前回の目標からの論理的なアドレス上の距離が、レベル毎に設定された優先順位の高い方が低い方以下となる所定値である位置を計算する方法、又は先頭に配置されているデータオブジェクトの位置からの論理的なアドレス上の距離が、所定値である位置を計算する方法であることを特徴とする請求項６に記載のデータ処理方法。
前記所定値を示す数値の受付又は設定読み取りを行うことを特徴とする請求項７に記載のデータ処理方法。
一のレベルで走査したデータオブジェクトに対しては、他のレベルでの走査を省略することを特徴とする請求項６乃至請求項８のいずれかに記載のデータ処理方法。
走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベル夫々について、列の先頭側から後方側へと走査し、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加するデータ処理装置であって、
第１の階層レベルの目標を所定の計算方法で設定後、第１の階層レベルについて走査する手段と、
走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加える手段と、
配列後、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替える手段と、
第１の階層レベルについての走査の対象がなくなった場合、
第１の階層レベルの目標を再設定する手段と、
第１の階層レベルの優先順位が最低であるとき、処理を中断する手段と、
第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替える手段と
を備えることを特徴とするデータ処理装置。
一又は複数の記録手段を備え、該記録手段に確保されたメモリ領域に順次配列されるデータオブジェクトを、順次配列された列の先頭側から後方側へ、夫々優先順位を付した複数のレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指されている他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置するデータ処理装置であって、
指されている他のデータオブジェクトを配置する位置の限界として、所定の計算方法を用いて求められたレベル毎の目標を設定する手段と、
配列されているデータオブジェクトに対して第１のレベルの走査を行う手段と、
走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が、第１のレベルに対して設定された目標に達しているか否かを判定する手段と、
目標に達していると判定した場合、第１のレベルの走査を中断して、第１のレベルより優先順位が低い第２のレベルの走査を行う手段と、
走査に基づいて配置された他のデータオブジェクトの位置が、レベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定する手段と、
走査に基づいて他のデータオブジェクトを配置した後、最も優先順位が高いレベルの走査を行う手段と
を備えることを特徴とするデータ処理装置。
コンピュータに、走査対象として順次配列されるデータオブジェクトを、優先順位が付けられた複数の階層レベルの夫々について、列の先頭側から後方側へと走査させ、走査中のデータオブジェクトが指している他のデータオブジェクトを選択的に次に配列して走査対象に追加させるコンピュータプログラムであって、
コンピュータに、第１の階層レベルの目標を所定の計算方法で設定後、第１の階層レベルについて走査させる手順と、
コンピュータに、走査中の第１のデータオブジェクトが所定の条件で第２のデータオブジェクトを指している場合、かつ、次に配列する位置が第１の階層レベルの目標に適合している場合、第２のデータオブジェクトを次に配列して走査対象に加えさせる手順と、
コンピュータに、配列後、第１の階層レベルの優先順位が最高でない場合、最高の優先順位がつけられた階層レベルについての走査へと処理を切り替えさせる手順と、
第１の階層レベルについての走査の対象がなくなった場合、
コンピュータに、第１の階層レベルの目標を再設定させる手順と、
コンピュータに、第１の階層レベルの優先順位が最低であるとき、処理を中断させる手順と、
コンピュータに、第１の階層レベルの優先順位が最低でないとき、一段優先順位の低い第２の階層レベルについての走査へと処理を切り替えさせる手順と
を実行させることを特徴とするコンピュータプログラム。
一又は複数の記録手段を備えるコンピュータに、記録手段に確保されたメモリ領域に順次配列されるデータオブジェクトを、順次配列された列の先頭側から後方側へ、夫々優先順位を付した複数のレベル毎に走査し、走査したデータオブジェクトが他のデータオブジェクトを指している場合に、指されている他のデータオブジェクトを、配列している最後部のデータオブジェクトの後側に配置させるコンピュータプログラムであって、
コンピュータに、指されている他のデータオブジェクトを配置する位置の限界として、所定の計算方法を用いて求められたレベル毎の目標を設定させる手順と、
コンピュータに、配列されているデータオブジェクトに対して第１のレベルの走査を行う手順と、
コンピュータに、走査したデータオブジェクトにより指されている他のデータオブジェクトを配置すべき位置が、第１のレベルに対して設定された目標に達しているか否かを判定させる手順と、
コンピュータに、目標に達していると判定した場合、第１のレベルの走査を中断して、第１のレベルより優先順位が低い第２のレベルの走査を行わせる手順と、
コンピュータに、走査に基づいて配置された他のデータオブジェクトの位置が、レベルに対して設定されている目標に達したとき、当該レベルに対する次の目標を設定させる手順と、
コンピュータに、走査に基づいて他のデータオブジェクトを配置した後、最も優先順位が高いレベルの走査を行わせる手順と
を実行させることを特徴とするコンピュータプログラム。