• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1990007151A1
    申请号:PCT/JP1989/001249
    申请日:1989-12-13
    公开日:1990-06-28
    发明作者:Hirotoshi Maekawa；Hiroyuki Yasuda
    申请人:Sony Corporation；
    IPC主号:G06F13-00
    专利说明:
    [0001] データ管理方式
    [0002] 本発明は、 コ ンピュータの主記憶のデータ管理方式に関し、 特に 技
    [0003] 人工知能， 数式処理， 自然言明語処理等の記号処理分野で基本的かつ 不可欠なリ ス ト構造データの仮想細化を効率良く実現するものである 分
    [0004] 1 o
    [0005] 背 景 技 術野
    [0006] 一般に、 コ ンピュータによる人工知能， 数式処理， 自然言語処理 等の記号処理分野では、 リス ト構造のデータをメ モリ上で管理しな
    [0007] 1 5 がら、 目的の記号処理を行うようにしている。
    [0008] 従来より、 上記リ ス ト構造のデータとしては、 ノ ー ド間がポイ ン タでリ ンクされている構造を持つた所謂 pointer- linked data が広 く知られている。 上記 pointer- linked data において、 ポイ ンタは. 多く の場合一方向にだけ持ち、 また、 ノー ドは、 他のノー ドへのポ
    [0009] Z 0 ィ ンタ と自身のデータを持ち、 そのボイ ンタ数が二つの所謂 2分木
    [0010] (binary tree) ¾造が多い <>
    [0011] 例えば、 リ ス ト構造のデータを扱う代表的な言語として知られて いる リ スプ（LISP)言語では、 第 1 図にリ ス ト構造のデータ例を示し てあるように、 中間ノー ド（Ν10) , (Ν1 Ζ) , (Ν14) , (Ν15) , (Ν17) , (Ν20) , (N22) , ( 24) , (N2 J がポイ ンタを二つ持ち、 端末に位置するノー ド ( π) , ( , 3) , ( ι6) , (N I B) , ( i 9) , (ΝΖ 1 ) , (ΝΖ 3) , ( 25) , (Ν'ζ7) , (ΝΖ 8) に具体的データを持ち、 上記靖末の構成状態が情報を持っている。
    [0012] また、 上述のようなリ ス ト構造のデータをメモリ上で扱う場合は、 例えば第 2図に示すように、 番地付けられたメ モリ上の記億空間
    [0013] (Μ) にノード（ 。），（Νη) , (Ν1 Ζ) , (Ν13) を表現し、 その記憶空 簡（Μ) のア ド レスによりポイ ンタを表現するようにして、 コ ンビュ —タにより上記データを管理するようにしている。
    [0014] ところで、 上記記号処理分野で扱われている上記リス ト構造のデ ータは、 切れたり繫がったり、 伸びたり縮んだり して、 そのデータ 構造として与えられる情報が自在に変化する勣的構造を有し、 試行 錯誤的な振る舞いをする。
    [0015] また、 このようなリス ト構遣のデータをコ ンピュータによりメモ リ上で管理する場合、 そのデータ構造がメ モ リ上に分散され、 メ モ リ上に新たなノ一ドが無くなつてしまったり、 使用済で不要なノ一 ドができるので、 不要なノー ドを画収して新しいノー ド'として再使 用するガーべジコ レク ショ ン（GC: Garbage Collection) が行われる < さらに、 ガ一ベジコ レク シ ョ ンを行っても実記憶空間が足りない ときには、 記憶空間（M) を仮想化により拡張するようにして、 例え ば第 3図や第 4図に示すように、 記憶空間をページ単位で管理して 実記憶空間（RM)と仮想記憶空間（IM)との間でページ単位でのデータ 転送（swapping)が 4亍ゎれている。
    [0016] ところで、 現在のコ ンビュータアーキテクチャは、 静的構造を有 する局所的なデータを処理するようにデザィ ンされており、 上記記 号処理分野で扱われているような上記リ ス ト構造のデータの処理に は適さず、 例えば処理対象が動的に分散されているガーべジコ レク シヨ ンを実行するのに非常に長い時間を要する。 また、 従来、 デー タの局所性を前提として記憶空間をページ単位で管理するようにし て記憶空間を仮想化しており、 上記ぺージは記憶空間上の固定領域 であるが、 上記リ ス ト構造のデータは動的に変化してい く ので、 そ の構造は複数のページ間に複雑に入り組んでしまい、 ページフオ ル 卜が頻繁に発生し効率が悪い。 特に、 仮想化した記憶空間に対して ガーべジコ レク ショ ンを実行した場合には、 実記憶空間と仮想記憶 空間との間でベージ単位でのデータ転送を行うために、 実行効率が 著しく低下する。
    [0017] そこで、 本発明は、 上述の如き従来の実情に鑑み、 人工知能， 数 式処理， 自然言語処理等の記号処理分野で基本的かつ不可欠なリ ス ト構造データの仮想記憶化を効率良く実現することを目的とする。 発 明 の 開 示 本発明に係るデータ管理方式は、 上述の目的を達成するために、 実記憶空間ではその実記憶空間内のァ ドレスによりボイ ンタを表し 、 仮想記憶空間ではその仮想記憶空間内のァ ドレスと上記実記憶空 間へのァ ドレスによりボイ ンタを表し、 上記実記憶空間上のノ一ド
    [0018] Z 0 から仮想記憶空間上のノー ドを間接参照するようにして、 ノー ド間 がボイ ンタでリ ンクされた構造のデータを実記憶空間と仮想記憶空 間とに亘つて表現し、 上記ノ一 ド間がボイ ンタでリ ンクされた構造 のデータをそのリ ンク情報を用いたリ ス ト構造単位で実記憶空間と 仮想記憶空間との間で移動させることを特徴とする。
    [0019] Z 5 本発明に係るデータ管理方式では、 実記憶空間ではその実記憶空 藺内のァ ド レスによりボイ ンタを表し、 仮想記憶空間ではその仮想 記憶空間内のァ ド レスと上記実記憶空 ¾1へのァ ド レスによりボイ ン タを表し、 上記実記憶空間上のノー ドから仮想記憶空間上のノード を間接参照するようにして、 ノー ド-間がポイ ンタでリ ンクされた構 造のデータを実記憶空間と仮想記憶空間とに亘つて表現することに よって、 ボイ ンタにより全記憶空間を表現する必要が無く なる。 ま た、 上記ノ一ド間がボイ ンタでリ ンクされた構造のデータをそのリ ンク情報を用いたリ ス ト構造単位で実記憶空間と仮想記憶空間との 間で移動させることにより、 動的なデータを静的に区分することな く動的データ構造をそのまま反映させた状態で管理する。 図面の簡単な説明 第 1図は一般的なリ ス ト構造のデータ例を示す模式図、 第 2図は リ ス ト構造のデータを記憶空間上に表現した模式図、 第 3図および 第 4図は従来の一般的な仮想化により拡張した記憶空間の構成例を 示す各模式図である。
    [0020] 第 5図は本発明を適用したマルチプロ セ ッ サシステムの構成を示 すブロック図、 第 6図は本発明を適用したプロセッサシステムにお いて扱う リ ス ト構造のデータを実記憶空簡と仮想記憶空簡に亘つて 表現したデータ例を示す模式図、 第 7図は実記憶空藺に表現したリ ス ト構造のデータの具体例を示す模式図、 第 8図は上記第 7 11に示 したリス ト構造のデータを実記憶空間と仮想記憶空間に亘つて表現 した具体例を示す模式図、 第 9図は実記憶空簡から仮想記憶空間に リ ス トアウ トする リ ス ト構造単位の構成例を示す模式図、 第 1 0図 A , 第 1 0図 B , 第 1 0図 C , 第 1 0図 D , 第 1 0図 Eおよび第 1 0図 Fは上記第 9図に示したリ ス ト構造単位を実記憶空間から仮想 記憶空間にリ ス トァゥ 卜するための上記実記憶空間上でのリ ス トア ゥ 卜動作の手順を説明するための各模式図、 第 1 1図は上記第 9図 に示したリ ス ト構造単位を実記憶空間から仮想記憶空間にリ ス ト ア ゥ ト した状態を示す模式図、 第 1 2図は仮想記憶空間から実記憶空 間にリ ス トイ ンするリ ス ト構造単位の構成例を示す模式図、 第 1 3 図 A , 第 1 3図 B , 第 1 3図 Cおよび第 1 3図 Dは上記第 1 2図に 示したリ ス ト構造単位を仮想記憶空間から実記憶空間にリ ス ト イ ン するための上記実記憶空間上でのリ ス トイ ン動作の手順を説明する ための各模式図、 第 1 4図はリ ス トァゥ トにより実記憶空間上に間 接ボイ ンタが残存した状態のリ ス ト構造を示す模式図、 第 1 5図は 上記第 1 4図に示した間接ボイ ンタを削除したリ ス ト構造を示す模 式図、 第 1 6図 Aおよび第 1 6図 Bは仮想記憶空間上にリ ス ト アゥ 卜された各リ ス ト構造単位を一括管理するために設けられる各種参 照表の構成を示す各模式図である。 発明を実施するための最良の形態
    [0021] 以下、 本発明の一実施例について、 図面に従い詳細に説明する。 第 5図は、 本発明に係るデータ管理方式を適用してリ ス ト構造の データを取り扱うようにしたマルチプロ セ ッ サ システムの概念的な 構成を示すブロ ック図である。 このマルチプロセ ッサシステムは、 複数のプロ セ ッ サ（l a) , ( l b) 〜 （I n) によ り それぞれメ モ リ コ ン ト ローラ（2a) , (2b) 〜 （2n) を介してア ク セスされる実記憶空間をな す主記憶装置（3) と仮想記憶空間をなすハ一 ドディ ス ク装置等の二 次記憶装置（4) とを備え、 仮想化による記憶容量の拡張が図られて いる。
    [0022] なお、 上記主記憶装置（3) は複数のメ モリバンク（3a), (3b) 〜 (3n)と上記各メ モリバンク （3a) , (3b) 〜 （3n) の接続面路（3A)とで 構成されている。
    [0023] このマルチプロセ ッサシステムにおいて取り扱う リ ス ト構造のデ ータは、 実記億空間ではその実記憶空間内のァ ドレスによりボイ ン タを表し、 また、 .仮想記憶空藺ではその仮想記憶空間内のァ ドレス と上記実記億空間へのァ ドレスによりボイ ンタを表し、 上記実記憶 空簡上のノ一ドから仮想記憶空間上のノ -ドを簡接ボイ ンタにより 参照するようにして、 第 6図に示すようにノード間がポィ ンタでリ ンクされたリス ト構造のデータ として上記主記憶装置（3) による実 記憶空間（Rfl)と上記二次記億装置（4) による仮想記憶空間（ I M)とに 亘つて表現され、 上記第 6図に破線で翻んで示すようなリ ス ト構造 単位（IU), (ϋ2) で上記実記憶空間（RM)と仮想記憶空間（ΙΜ)との間で データ転送（Swapping)される。
    [0024] なお、 上記第 6図中には、 上記仮想記憶空間上のノー ドを参照す る間接ボイ ンタを設定した上記実記憶空間上のノ一ドを口で示し、 他のノードを〇で示してある。
    [0025] ここで、 上記リス ト構造のデータの具体的表現例について説明す る。
    [0026] 例えば第 7図に示すように、 上記主記憶装置（3) による実記憶空 簡（RM)上に表現された 9個のノード （N10), ( l t), (N12), ( 13), (Nzo), (N21), (N22), (Nz3), (N30) が上記実記憶空間（RM)上の実記憶 空藺ァ ドレスで表現したボイ ンタにより リ ンクされてなるリ ス ト構 造のデータは、 上記第 Ί図中に破線にて囲んで示す 4個のノー ド (N, ,) , (N! Z) , (N21) , (Νζ ζ) による リ ス ト構造単位（ϋ。）を上記二次記 憶装置（4) による仮想記憶空間（ΙΜ)上に移した場合、 第 8図のよう に表現される。
    [0027] ; 第 8図において、 上記仮想記憶空間（ΙΜ)上に移した上記リ ス ト構 造単位（Uo)を構成する 4個のノー ド（η, ,) , (η， ζ) , (nz l)，（n22) は、 上記仮想記憶空間（IM)上の各ノ一ド（n21), (n22) の仮想記憶空間ァ ドレスおよび上記実記憶空間（RM)上の各ノ一ド（N, ,)，（N12)，（N， 3), ( Z3) の実記憶空間ァ ドレスを直接表現した各ボイ ンタにより、 上 , 記各ノー ド（η21) , (n22) , :， J , (Ν12) , (Ν13) , (N23) とリ ンクされる < また、 上記実記憶空間（RM)上の各ノ ー ド（N ），（N'1 Z) は、 上記仮想 記憶空間（IM)上の上記リ ス ト構造単位（U。）の各ノー ド（ni l)，（n12) の仮想記憶空間ァ ドレスを表現した間接ポイ ンタにより、 上記各ノ ー ド（η, ,) , (η, 2) とリ ンクされる。
    [0028] ; 上述の如きリ ス ト構造のデータを取り扱う このシステムでは、 上 記リ ス トデータの動的な変化過程において、 上記実記憶空間（RM)上 に必要なノ一ドが無く、 リ ス トフォール トが発生し、 そのノー ドが 上記仮想記憶空間（ΙΜ)上にある場合に、 そのノー ドを舍む一連のリ ス ト構造単位のデータを上記仮想記憶空間（ΙΜ)から上記実記憶空間
    [0029] Z 0 (RM)にデータ転送（Swap- in) することにより、 後述する手順に従つ てリ ス ト イ ンを行う。
    [0030] また、 このシステムでは、 上記実記憶空間（R-M)上のフリーノー ド の数を監視しており、 上記実記憶空間（RM)上のフ リーノ ー ドが無く なると、 不要なノー ドをフ リーノ一 ドとして回収するガーべジコ レ
    [0031] Z 5 ク ショ ンを行い、 このガーべジコ レク ショ ンにより フ リ ーノー ドの 数が所定の閾値 Sh 以上になれば、 本来のデータ処理に復帰する。 上記ガ一ベジコ レク ショ ンによりフリ一ノー ド-の数が所定の閾値 S h 以上にならない場合には、 その時点で上記実記憶空間（BM)上に不 要なリス トデータへのボンタを抽出して、 後述する手順に従って上 記実記憶空間 (RM)から上記仮想記憶空間（IM)へのリス ト構造単位の データ転送（Swap- out)するためのリ ス トァゥ ト動作を上記実記億空 藺（RM)上で行う。 上記実記憶空間（RM)上でリ ス トアウ ト したリ ス ト 構造単位のデータ数が少なく所定の閾値 S s に満たない場合には、 上記実記憶空間（RM)上に不要なリ ス トデータへのポ ンタをさらに抽 出して、 新たなリ ス トデータのリス トアゥ ト動作を上記実記憶空間 上で繰り返し行う。 そして、 上記実記憶空間（RM)上でリス トア ゥ ト したリス ト構造単位のデータ数が上記 ί値 S s に達すると、 上 記実記憶空簡（RM)でリス トアウ トされたリス ト構造単位のデータを 上記実記憶空簡（RM)から上記仮想記憶空間（ΙΜ)へデータ転送（Swap - out)し、 リ ス トアウ トの動作を終了して、 本来のデータ処理に復帰 する。
    [0032] 上記実記憶空間（RM)から上記仮想記憶空間（IM)へのリ ス トアウ ト の動作は、 リス ト構造を掃査して、 各ノ一ドのリ ンク数をリ フ ァ レ ンスカウンタにより参照しながら間接ポィ ンタを用いて次のように 亍： れる。 - 例えば第 9図に示すように、 実記憶空簡（RM)上の 7個のノード (N10), (N, ,) , (N ） ， ( 13) , (K2。） ， (Ν21) , (Ν22) 間がボイ ンタにより リ ンクされたリス ト構造単位（U10) を上記実記憶空間（RM)から仮想 記憶空間（IM)へリス トアゥ トする場合について説明すると、 先ず、 上記実記憶空簡 上において、 その作業領域 に上記リ ス ト構 造単位（Ι 。） を第 1 0図 Α〜第 1 0図 Fに示すような手順でリス ト ァゥ トする。
    [0033] すなわち、 先ず、 上記実記憶空間（1 Μ)上の上記リ ス ト構造単位 (U,o) の開始位置にあるノー ド例えばノー ド（N , 0) に着目 して、 第 > 1 0図 Aに示すように、 上記ノー ド（N10) に対する リ ンクを実記憶 空間ァ ド レスで表現した逆参照ボイ ンタ と上記ノ一ド（N,。） のボイ ンタにより リ ンクされているノー ド（N, ,) に対する リ ンクを実記憶 空間ァ ド レスで示した逆参照ボイ ンタを有するノー ド（ 。） を上記 仮想記憶空間（IM)に移すノ - ドとして上記実記憶空間（RM)上の作業 , 領域（WA)に設け、 上記仮想記憶空間（IM)に移す上記ノ ー ド （η ι。） へ のリ ンクを表現した間接ボイ ンタを上記実記憶空間（RM)上のノ一ド (N.o) に設定する。
    [0034] 次に、 上記実記憶空間（RM)上の上記ノー ド（N1 0) にリ ンク してい た上記ノー ド（NH) に着目して、 第 1 0図 Bに示すように、 上記ノ i — ド（Ν, ,) に対する リ ンクを実記憶空間ア ドレスで表現した逆参照 ボイ ンタ と上記ノー ド（N , , ) のポィ ンタにより リ ンクされている各 ノー ド（N12)，（N21) に対する各リ ンクを実記憶空間ア ド レスで表現 した各逆参照ボイ ンタを有するノ一ド（n, ,) を上記作業領域（WA)に 設ける。 そして、 上記作業領域（WA)の上記ノー ド（ηι へのリ ンク を表現した間接ボイ ンタを上記ノー ド（Nn) に設定するとともに、 上記作業領域（WA)の上記ノ一ド（n,。） のボイ ンタによる上記実記憶 空間（RM)上の上記ノー ド（N12) へのリ ンクを該ノード（N12) に対応 する上記作業領域（WA)の上記ノ一ド（nl z) へのリ ンク に移して、 上 記ノ ー ド（N1 Z) への逆参照ポイ ンタを上記ノー ド（IIH) への リ ンク を仮想記憶空間ァ ド レスによ り表現した内容のボイ ンタ に変更する < その次に、 上記実記憶空間（RM)上の上記ノー ド（N H ) にリ ンク し ていた上記ノ ー ド（N ） に着 gして、 このノ ー ド（N'1 2) のポイ ンタ によるノー ド（N1 3) へのリ ンクを手繰って、 上記実記憶空間上の各 ノ ード（N 1 2) , (N 1 3) を上記作業領域（WA)に移して、 第 1 0図 Cに示 すように、 上記ノー ド（n i のポイ ンタにより リ ンクされるノード (n1 2) と、 このノ ー ド（nl z) のボイ ンタにより リ ンク されるノ ー ド (n1 3) を上記作業領域（WA)に設ける。
    [0035] 次に、 上記作業領域（WA)の上記ノード（ni l) の逆参照ボイ ンタに より リ ンクされている上記実記憶空間 上の上記ノ一ド（K2 l) に 着目して、 このノ ー ド（Ν21) のポイ ンタによるノ 一 ト "（Ν22) へのリ ンクを手操ることにより、 上記実記憶空簡（RM)上の各ノー ド（ΝΖ 1) , (Ν2 Ζ) を上記作業領域（WA)に移して、 第 1 0図 Dに示すように、 上 記ノ ー ド（ii H ) のポイ ンタにより リ ンク されるノ ー ド（n21) と、 こ のノ ー ド（nz l) のポイ ンタにより リ ンク されるノー ド（n22) を上記 作業領域（WA)に設ける。 さらに、 上記作業領域（WA)の上記ノー ド
    [0036] (n22) の逆参照ボイ ンタによる上記実記億空間（RM)上の上記ノード ( n) へのリ ンクを上記ノー ド（Nu) に対応する上記作業領域（WA) の上記ノー ド（nn) へのリ ンクに付け替える。
    [0037] さらに、 上記実記憶空間（RM)上の上記リス ト構造単位（U1 0) の他 の開始位置にある未掃査のノード（N20) に着目して、 第 1 0図 Eに 示すように、 上記ノー ド（N20) に対するリ ンクを実記憶空間ァ ドレ スで表現した逆-参照ボイ ンタ と上記ノ一ド（M20) のボイ ンタにより リ ンクされている上記ノード（ H) に対するリ ンクを実記憶空藺ァ ドレスで示した逆参照ポイ ンタを有するノー ド（n2。） を上記作業領 域（《A)に設けるとともに、 このノード（n20) へのリ ンクを表現した 間接ポィ ンタを上記実記憶空間（βΜ)上のノ一ド（Ν20) に設定する。 そして、 上記作業領域（WA)の上記ノ一ド（η2。） の逆参照ボイ ンタ による上記実記憶空間（RM)上の上記ノ ー ド（ ，） へのリ ンクを該ノ ー ド（Ν Η) に対応する上記作業領域（WA)の上記ノ ー ド（n i l) へのリ ンクに付け替えて、 第 1 0図 Fに示すよう に、 上記実記憶空間上 (RM)の上記ノ ー ド（Ν, ,) を上記作業領域（WA)の上記ノ ー ド（η ι ,) に 完全に移動させるこ とにより、 上記実記憶空間（RM)上の作業領域 (WA)への上記リ ス ト構造単位（U,。） のリ ス トァゥ トを終了する。 最後に、 上記リ ス ト構造単位（l 。） のデータを上記主記憶装置
    [0038] (3) による実記憶空間（RM)上の作業領域（WA)から上記二次記憶装置
    [0039] (4) による仮想記憶空間（IM)へデータ転送（Swap-out)するこ とによ り、 上記リ ス ト構造単位（ 。） を上記仮想記憶空間（IM)へ第 1 1図 に示すようにリ ス トアウ トする。
    [0040] このように、 間接ポィ ンタを用いることにより上記リ ス ト構造単 位（U10) の如き環状リ ス ト構造も旨 く リ ス トァゥ トする こ とができ , しかも、 上記主記憶装置（3) による実記憶空間（RM)上でリ ス トアゥ ト したリ ス ト構造単位のデータを上記実記憶空間（RM)から上記二次 記憶装置（4) による仮想記憶空間（IM)へのデータ転送（Swap- out)す ることにより、 上記仮想記憶空間（IM)に効率よ く迅速にリ ス トアゥ トすることができる。
    [0041] こ こで、 上記実記憶空間（RM)上のノ一ドに対する リ ンクを実記憶 空間ァ ド レスにより表現し、 また、 上記仮想記憶空間（IM)上のノ一 ドに対する リ ンクを仮想記憶空間ァ ドレスをそれぞれ各記憶空間内 で表現して、 それぞれの記憶空間内でのリ ンクを直接表現した通常 のボイ ンタと、 上記仮想記憶空間（IM)上のノ一ドの仮想記憶空間ァ ドレスを表現した上記実記憶空間（β«)上のノー ド（N J , (N1 Z) 等の 間接ポイ ンタや、 上記実記憶空間 上のノー ドに対する リ ンクを 実記憶空間ァ ドレスで表現した上記仮想記憶空簡（IM)上のノ一ド (nl 0) , (n^) 等の逆参照ボイ ンタ とは、 例えばそのポイ ンタで指さ れているノ一 ドの種類を示すタグをポィ ンタに付加しておく ことに より、 上記タグの内容により識別される。
    [0042] 次に、 上記二次記憶装置（4〉 による仮想記憶空間（IM)から上記主 記憶装置（3) による実記憶空間（RM)へのリス トイ ンは、 アクセスし よう とするノードが上記実記憶空間（RM)上になく間接ポンィ ンタに より示される仮想記憶空間（IM)上のノードであった場合に、 次のよ うに ί亍ゎれる。
    [0043] 例えば、 第 1 2図に示すように、 上記実記憶空簡（RM)上の各ノー ド（Ν:1 0) , (Ν Η) の間接ボイ ンタにより リ ンクされた上記仮想、記憶空 間（ΙΜ)上のノ ー ド 1 0) , (nl z) , (n1 3) , (n20) , (nz l) , (η2Ζ) に よる リ ス 卜構造単位（ϋ2。） を上記仮想記憶空藺（IM)から上記実記憶 空間 ヘリ ス トイ ンする場合について説明すると、 先ず、 上記リ ス ト構造単位（ϋζ。） のデータ上記実記憶空間（RM)上の作業領域（WA) にデータ転送（Swap- in) し、 上記実記憶空間（RM)上において、 第 1 3図 A〜第 1 3図 Dに示すような手順で上記作業領域（WA)から上記 リ ス ト構造単位（ϋ2。）'のリ ス トイ ンの動作を行う。
    [0044] すなわち、 上記仮想記憶空閭（ΙΜ)から上記実記憶空間（RM)にデ一 タ転送（Swap-in) された第 1 3図 Aに示す如き上記作業領域（WA)の リス ト構造単位（ϋ2。） について、 先ず、 上記リ ス ト構造単位（ϋ20) を掃查し、 第 1 3図 Βに示すように、 上記リ ス ト構造単位（1^。) を 構成している各ノー ド（nn) , (n12) , (n13) , (n21)，（n2z) に逆参照ポ イ ンタを設定して、 上記ノ ー ド（n， J , (n, 2)，（n13) , (n21)，（nZ2) に 対応する各ノー ド（N, J, ( 1 E), (NI 3) , (N21) , (N2Z) を上記実記憶空 間（RM)上に設ける。
    [0045] 次に、 再度上記リ ス ト構造単位（ϋ2。） を掃查し、 第 1 3図 Cに示 すように、 上記作業領域（WA)の上記リ ス ト構造単位（U2。） を構成し ている上 谷ノ —— ド in 1 0リ ,（ni l), (n 1 z) , i s) , (n2 o) . (n z i ) , (nZz) の仮想記憶空間ァ ドレスで表現されているボイ ンタを上記実記憶空 間（RM)上の上記各ノ一 ド（N, , (N12) , (N13), (NZ 1)， ( 2Z) にリ ンク する実記憶空間ァ ドレスによる逆参照ボイ ンタに付け替える。
    [0046] そして、 三度上記リ ス ト構造単位（ϋ 20) を掃査して、 第 1 3図 D に示すように、 上記作業領域（WA)の上記リ ス ト構造単位（U2。） を構 成している上記各ノ ー ド （n10), (tin), (n12), (n13) , (n20), (n21), (n22) の内容を上記実記憶空間（RM)上の各ノー ド （!^。），（^ ， (N12), ( , 3) , (Νζο) , ( ζι) , (N22) に移すこ とにより、 上記リ ス ト構 造単位（U2。） を上記作業領域（WA)から上記実記憶空間（RM)に全て移 動し、 上記二次記憶装置（4) による仮想記憶空間（IM)から上記主記 憶装置（3) による実記憶空間（RM)への上記リ ス ト構造単位（U2。） の リ ス ト イ ンを終了する。
    [0047] なお、 上記仮想記憶空間（IM)から上記実記憶空間（RM)へのリ ス ト
    [0048] Z 0 ィ ンは、 上述の実記憶空間（RM)から仮想記憶空間（IM)へのリ ス トア ゥ ト と同様な方法で行う こともできる。
    [0049] こ こで、 上記主記憶装置（3) による実記憶空間（RM)を上記二次記 憶装置（4) による仮想記憶空間（IM)により拡張して処理を行う際に は、 上記仮想記憶空間（IM)上のリ ス トアウ トされたリ ス ト構造単位
    [0050] Z 5 のソ一ドから上記実記憶空間（RM)上のソ一ドへの参照がしばしばし ば発生し、 例えば、 第 1 4 11に示すように、 上記仮想記憶空間（I M) 上のリ ス ト構造単位（I )のノ―ド（NA)から参照されている上記実記 憶空間（BM)上のノ一ド（KB )が、 上記実記憶空間（RM)上の他のノ一 ドから参照されることなく、 上記仮想記憶空間（I M)上のリ ス ト構造 単位（U c)のノ ー ド（ c)への間接ポイ ンタ となることがある。 この ような場合には、 上記実記憶空間（RM)上のノ一ド（ΝΒ)に対する上記 仮想記憶空簡（Ι Μ)からの参照を書き替えることにより、 第 1 5図に 示すように、 上記間接ポイ ンタを削除して、 上記実記憶空間 上 のフリーノードの数を増やすことが可能である。
    [0051] 上述の如き簡接ボイ ンタを削除するための一連の操作は、 原理的 には、 各々の間接ポイ ンタへの逆参照表を作成して、 リ ス トアウ ト の際にリス トアウ トされたリ ス ト構造単位内の該当する間接ボイ ン タへの参照を書き替えることで実現可能である。 この操作では、 仮 想記憶空間内のリス ト構造を操作する動作を含んでいるので、 ァク セス時間の長い上記仮想記憶空間へのァクセスが増加する。
    [0052] そこで、 このシステムでは、 第 1 6図 Αに示すように、 仮想記憶 空間（I M)にリ ス トアウ トされた各リ ス ト構造単位を一括して管理す るス ト ラクチヤ参照表（s r) と、 上記仮想記憶空間（IM)にリ ス トア ゥ 卜 されたリ ス ト構造単位で外部ノ一ドへの参照を管理する外部参 照表（XRT) とを実記憶空簡（ )上に設けるとともに、 第 1 6図 Bに 示すように、 上記仮想記憶空間（I M)から実記憶空間（RM)への参照を 管理する逆参照表（DRT) を上記実記憶空藺（RM)上に設けて、 上記仮 想記憶空間にリ ス トアゥ トされた各リ ス ト構造単位間の参照を一括 して扱い、 上記仮想記憶空藺（I M)へのアクセスを減少させるように している 0 上記ス ト ラ ク チャ参照表（SRT) は、 上記仮想記憶空間（R) に リ ス トァゥ ト された各リ ス 卜構造単位を特定する情報 sr t. idと、 リ ス ト 構造単位のノ ー ドの外部からの参照数 rei.c と、 上記外部参照表 (XRT) へのポイ ンタ xrt が格納されており、 上記外部参照表（XRT) の管理、 検索等に用いられる。 また、 上記外部参照表（XRT) は、 リ ス トアウ ト されたリ ス ト構造単位毎に割り 当てられ、 対応する リ ス 卜構造単位内で、 外部を参照しているノ一ドを特定する情報 ptr. id と、 上記ノ 一 ドが参照している外部のノ ー ドを特定するボイ ンタ dst が格納される。 さ らに、 上記逆参照表（DRT) は、 上記実記憶空 間（RM)上のノ一ドを参照している上記仮想記憶空間（IM)上のノ一ド をリ ス ト構造単位で特定するデータ Ptr. listと、 上記上記実記憶空 間（RM)上のノ一ドを特定するデータ dst. idが格納される。
    [0053] 上記各参照表（SRT) , (XRT) , (DRT) のエ ン ト リ は、 例えば上記ス ト ラ ク チャ参照表（SRT) はリ ス ト構造単位のス ト ラ ク チャ番号で、 ま た、 外部参照表（XRT) はリ ス ト構造単位のス ト ラ ク チ ャ内ア ド レス で、 そ して、 上記逆参照表（DRT) は実記憶空間ア ド レスでハ ッ シュ すれば良く、 各参照表（SRT) , (XRT), (DRT) の検索などを高速化する こ とができる。 なお、 被参照ノ ー ドが実記憶空間に存在しない場合 には、 上記逆参照表（DRT) へのハ ッ シュはできないが、 上記仮想記 憶空間上のリ ス ト構造単位のノ ー ドからの逆参照ボイ ンタを逆参照 表（DRT) へのエ ン ト リ とする こ とができる。
    [0054] こ こで、 上述の実施例では 2分木のリ ス ト構造データの管理を行 つたが、 本発明に係るデータ管理方式において取り扱う こ とのでき る リ ス ト構造データは、 2分木のリ ス ト構造データに限定されるこ とな く 、 n分木構造のリ ス ト構造データに拡張する こ とができる。 また、 本発明に係るデータ管理方式は、 上述の実施例の如きマルチ プロセッサシステムのみに適用なものではな く、 一般的なプロセ ッ サシステムに適用することも勿論可能である。
    [0055] 以上のように、 本発明に係るデータ管理方式では、 実記憶空間で はその実記憶空間内のァ ドレスによりボイ ンタを表し、 仮想記憶空 間ではその仮想記憶空間内のァ ドレスと上記実記憶空間へのァ ドレ スによりボイ ンタを表し、 上記実記憶空間上のノ一ドから仮想記憶 空間上のノ一ドを簡接参照するようにして、 ノ一ド簡がボイ ンタで リ ンクされた構造のデータを実記憶空間と仮想記憶空間とに亘つて 表現することによって、 ポイ ンタにより全記憶空間を表現する必要 が無いので、 記憶容量を節約することができ実質的に記憶容量を増 加させることがきる。
    [0056] また、 本発明に係るデータ管理方式では、 上記ノ一ド間がボイ ン タでリ ンクされた構造のデータをそのリ ンク情報を用いたリス ト搆 造単位で実記憶空間と仮想記憶空間との間で移動させることにより 、 動的データを静的に区分することな く動的データ構造をそのまま 反映させた状態で管理するので、 仮想記憶空間のアクセス面数を減 らしてメ モリァクセス効率を著しく向上させることができる。 特に 、 ガ一ベジコ レク ショ ンの実行効率を顕著に高めることができ極め
    [0057] Z 0 て有効である。
    [0058] 従って、 本発明に係るデータ管理方式を適用することによつて、 人工知能， 数式処理， 自然言語処理等の記号処理分野で基本的かつ 不可欠なリ ス ト構造データの仮想化を効率良く実現することができ るようになる。
    [0059] Z 5
    权利要求:
    Claims
    ― J ―
    請 求 の 範 囲 実記憶空間ではその実記憶空間内のァ ドレスによりポィ ンタを表 し、 仮想記憶空間ではその仮想記憶空間内のァ ドレスと上記実記憶 空間へのア ドレスによりポイ ンタを表し、 上記実記憶空間上のノ一 ドから仮想記憶空間上のノー ドを間接参照するようにして、 ノ ー ド 間がボイ ンタでリ ンクされた構造のデータを実記憶空間と仮想記憶 空間とに亘つて表現し、 上記ノ一ド間がボイ ンタでリ ンクされた構 造のデータをそのリ ンク情報を用いたリ ス ト構造単位で実記憶空間 と仮想記憶空間との間で移動させることを特徴とするデータ管理方 式。
    Z 0
    类似技术:
    公开号 | 公开日 | 专利标题
    US20160162504A1|2016-06-09|Information searching apparatus, information managing apparatus, information searching method, information managing method, and computer product
    US8725956B2|2014-05-13|Memory sharing among computer programs
    Zorn1993|The measured cost of conservative garbage collection
    Davis1978|The architecture and system method of DDM1: A recursively structured data driven machine
    EP0069250B1|1988-06-01|Replacement control for second level cache entries
    US6049853A|2000-04-11|Data replication across nodes of a multiprocessor computer system
    Demaine2002|Cache-oblivious algorithms and data structures
    CN101652758B|2013-10-16|分级式不可变内容可寻址存储器处理器
    US4210961A|1980-07-01|Sorting system
    US6434576B1|2002-08-13|Popular-object handling in a train-algorithm-based garbage collector
    US5699539A|1997-12-16|Virtual memory management system and method using data compression
    US6529919B1|2003-03-04|Incremental class unloading in a train-algorithm-based garbage collector
    Appel1989|Simple generational garbage collection and fast allocation
    DE69825751T2|2005-07-07|Garbage-sammlungs-anordnung und verfahren mit begrenzter pausenzeit und mit einer schreibschranke die mit einer quelleninstanz eines partiell relokierten objektes assoziiert ist
    Cohen1981|Garbage collection of linked data structures
    US6480862B1|2002-11-12|Relation-based ordering of objects in an object heap
    US7640544B2|2009-12-29|Work stealing queues for parallel garbage collection
    CN104364775B|2017-12-08|具有段偏移寻址的专用存储器访问路径
    US6526422B1|2003-02-25|Striding-type generation scanning for parallel garbage collection
    US8868926B2|2014-10-21|Cryptographic hash database
    Dennis et al.1974|A preliminary architecture for a basic data-flow processor
    US7035884B2|2006-04-25|Placement of allocation trains in the train algorithm
    JP2809961B2|1998-10-15|マルチプロセッサ
    US6185581B1|2001-02-06|Train-algorithm-based garbage collector employing fixed-size remembered sets
    US4528624A|1985-07-09|Method and apparatus for allocating memory space based upon free space in diverse memory devices
    同族专利:
    公开号 | 公开日
    EP0417293A1|1991-03-20|
    DE68928782T2|1998-12-24|
    US5694599A|1997-12-02|
    DE68928782D1|1998-09-17|
    EP0417293A4|1992-01-22|
    EP0417293B1|1998-08-12|
    US6067607A|2000-05-23|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1990-06-28| AK| Designated states|Kind code of ref document: A1 Designated state(s): KR US |
    1990-06-28| AL| Designated countries for regional patents|Kind code of ref document: A1 Designated state(s): DE FR GB |
    1990-07-25| WWE| Wipo information: entry into national phase|Ref document number: 1990900984 Country of ref document: EP |
    1991-03-20| WWP| Wipo information: published in national office|Ref document number: 1990900984 Country of ref document: EP |
    1998-08-12| WWG| Wipo information: grant in national office|Ref document number: 1990900984 Country of ref document: EP |
    优先权:
    申请号 | 申请日 | 专利标题
    JP63/315652||1988-12-14||
    JP31565288||1988-12-14||
    JP1059390A|JPH02263233A|1988-12-14|1989-03-10|Data control system|
    JP1/59390||1989-03-10||KR90701710A| KR950005525B1|1988-12-14|1989-12-13|데이터관리방식|
    DE68928782T| DE68928782T2|1988-12-14|1989-12-13|Datenverwaltungssystem|
    EP90900984A| EP0417293B1|1988-12-14|1989-12-13|Data management system|
    [返回顶部]