JPH04205041A - マルチプロセッサシステム - Google Patents
マルチプロセッサシステムInfo
- Publication number
- JPH04205041A JPH04205041A JP2325895A JP32589590A JPH04205041A JP H04205041 A JPH04205041 A JP H04205041A JP 2325895 A JP2325895 A JP 2325895A JP 32589590 A JP32589590 A JP 32589590A JP H04205041 A JPH04205041 A JP H04205041A
- Authority
- JP
- Japan
- Prior art keywords
- block
- way
- data
- cache
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/12—Replacement control
- G06F12/121—Replacement control using replacement algorithms
- G06F12/123—Replacement control using replacement algorithms with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/12—Replacement control
- G06F12/121—Replacement control using replacement algorithms
- G06F12/126—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning
- G06F12/127—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning using additional replacement algorithms
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0804—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with main memory updating
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0815—Cache consistency protocols
- G06F12/0831—Cache consistency protocols using a bus scheme, e.g. with bus monitoring or watching means
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［産業上の利用分野］
本発明はマルチプロセッサシステムの個々のプロセッサ
に備えられるキャッシュメモリブロック置換方式に関す
るものである。
に備えられるキャッシュメモリブロック置換方式に関す
るものである。
［従来の技術］
従来、キャッシュメモリ（以下、キャッシュという）の
ブロック置換の際の置換対象ブロックの選択には、プロ
グラム実行時における一般的特性である参照局所性に鑑
みて、それ以降のプログラム実行において最も参照され
る可能性が低いと思われるブロックを選択する方式が用
いられてきた。具体的には、置換対象候補ブロック中で
最も長い期間参照されていないブロックを選択するＬ
ＲＵ （Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ ）
方式、最も遠い過去に格納されたブロックを選択するＦ
ＩＦＯ（Ｆｉｒｓｔ−Ｉｎ Ｆｉｒｓｔ−Ｏｕｔ）方式
等が用いられてきた。
ブロック置換の際の置換対象ブロックの選択には、プロ
グラム実行時における一般的特性である参照局所性に鑑
みて、それ以降のプログラム実行において最も参照され
る可能性が低いと思われるブロックを選択する方式が用
いられてきた。具体的には、置換対象候補ブロック中で
最も長い期間参照されていないブロックを選択するＬ
ＲＵ （Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ ）
方式、最も遠い過去に格納されたブロックを選択するＦ
ＩＦＯ（Ｆｉｒｓｔ−Ｉｎ Ｆｉｒｓｔ−Ｏｕｔ）方式
等が用いられてきた。
さらにブロック置換時の置換対象ブロックの選択方式（
ＦＩＦＯ，ＬＲＵ等）に加え、元来キャツシュは、単一
プロセッサシステムにおいて、ＣＰＵの主記憶アクセス
要求に対し高速にサービスを実行することが唯一の目的
であったため、ＣＰＵの書込み命令発行時にキャッシュ
内の当該データと主記憶製雪内の当該データとを同時に
書き変えるライト・スル一方式に対して、ＣＰＵの書込
み命令発行時にはキャッシュ内の当該データのみを書き
変え、主記憶装置に対しては必要となった時点、即ち、
そのデータを含むブロックが置き換えの対象として選択
された時点で始めて更新を行うコピー・バック方式が用
いられてきた。
ＦＩＦＯ，ＬＲＵ等）に加え、元来キャツシュは、単一
プロセッサシステムにおいて、ＣＰＵの主記憶アクセス
要求に対し高速にサービスを実行することが唯一の目的
であったため、ＣＰＵの書込み命令発行時にキャッシュ
内の当該データと主記憶製雪内の当該データとを同時に
書き変えるライト・スル一方式に対して、ＣＰＵの書込
み命令発行時にはキャッシュ内の当該データのみを書き
変え、主記憶装置に対しては必要となった時点、即ち、
そのデータを含むブロックが置き換えの対象として選択
された時点で始めて更新を行うコピー・バック方式が用
いられてきた。
即ち、キャッシュは単一プロセッサシステムにおいて開
発され発展してきたと言える。
発され発展してきたと言える。
［発明が解決しようとする課題］
しかしながら上記従来例では、−律に参照局所性のみを
前提した制御方式であるために、複数のプロセッサが並
行に動作する、例えば、複数のプロセッサと主記憶装置
が相互に単一バスで結合した構成であり、かつ、キャッ
シュが各プロセッサに設けられているマルチプロセッサ
システム（以下、システムという）においては以下に述
べるような問題点があった。
前提した制御方式であるために、複数のプロセッサが並
行に動作する、例えば、複数のプロセッサと主記憶装置
が相互に単一バスで結合した構成であり、かつ、キャッ
シュが各プロセッサに設けられているマルチプロセッサ
システム（以下、システムという）においては以下に述
べるような問題点があった。
即ち、各プロセッサに設けられているキャッシュ相互及
びキャッシュと主配憶装置とのデータ一貫性が考慮され
ねばならないが、システムが、ＣＰＵの書込み命令発行
時の主配憶更新方式にコピー・バック方式を採用してい
る場合、書込みデータが主記憶装置に直ちには反映され
ないために、キャッシュと主記憶装置との間でデータ内
容の不一致が生じる。そのようなデータを含むブロック
はダーティブロックと呼ばれているが、ダーティブロッ
クを主記憶装置に書き戻す（つまり、主記憶装置とキャ
ッシュとのデータ整合性を回復する）動作は、次の２つ
タイミングで行われてきた。即ち、 （１）他のプロセッサでの当該ブロックに対するキャッ
シュ・ミス発生時、そして、 （２）当該ブロックがブロック置換方式により置き換え
対象ブロックとして選択された時である。
びキャッシュと主配憶装置とのデータ一貫性が考慮され
ねばならないが、システムが、ＣＰＵの書込み命令発行
時の主配憶更新方式にコピー・バック方式を採用してい
る場合、書込みデータが主記憶装置に直ちには反映され
ないために、キャッシュと主記憶装置との間でデータ内
容の不一致が生じる。そのようなデータを含むブロック
はダーティブロックと呼ばれているが、ダーティブロッ
クを主記憶装置に書き戻す（つまり、主記憶装置とキャ
ッシュとのデータ整合性を回復する）動作は、次の２つ
タイミングで行われてきた。即ち、 （１）他のプロセッサでの当該ブロックに対するキャッ
シュ・ミス発生時、そして、 （２）当該ブロックがブロック置換方式により置き換え
対象ブロックとして選択された時である。
これらの場合、主記憶装置に対する書き戻し動作にバス
アクセスが必要となるが、 （１）はキャッシュ・ミスが発生したプロセッサで、そ
のデータが用いられるという意味で有効なバスアクセス
であるのに対し、 （２）はデータの有効利用といった観点からは有効なバ
スアクセスであるとは言えない。
アクセスが必要となるが、 （１）はキャッシュ・ミスが発生したプロセッサで、そ
のデータが用いられるという意味で有効なバスアクセス
であるのに対し、 （２）はデータの有効利用といった観点からは有効なバ
スアクセスであるとは言えない。
さらに（１）と（２）が組み合わさった条件、つまり、
あるプロセッサが所定のブロック置換方式に従ってダー
ティブロックを主記憶装置に書き戻した直後、別のプロ
セッサで該ブロックに対するキャッシュ・ミスが生じる
と、はぼ同時に同一ブロックに対して２回バスアクセス
が発生する。
あるプロセッサが所定のブロック置換方式に従ってダー
ティブロックを主記憶装置に書き戻した直後、別のプロ
セッサで該ブロックに対するキャッシュ・ミスが生じる
と、はぼ同時に同一ブロックに対して２回バスアクセス
が発生する。
このうち１回はダーティブロックの主記憶への書き戻し
をもう少し遅らせていれば回避できたものである。しか
し、このような条件が多発すると、バスアクセス頻度が
増加しバスアクセス待ちの可能性が高まりシステム性能
の低下をもたらす恐れがある。
をもう少し遅らせていれば回避できたものである。しか
し、このような条件が多発すると、バスアクセス頻度が
増加しバスアクセス待ちの可能性が高まりシステム性能
の低下をもたらす恐れがある。
本発明は上記従来例に鑑みて成されたもので、マルチプ
ロセッサシステムに適したバスアクセス頻度を軽減する
キャッシュメモリブロック置換方式を提供することを目
的とする。
ロセッサシステムに適したバスアクセス頻度を軽減する
キャッシュメモリブロック置換方式を提供することを目
的とする。
［課題を解決するための手段］
上記目的を達成するために本発明のキャッシュメモリブ
ロック置換方式は、以下の様な構成からなる。即ち、 複数のプロセッサ各々がキャッシュメモリを備えるマル
チプロセッサシステムにおいて、複数の区別されたデー
タ格納ブロックを有するキャッシュメモリと、前記マル
チプロセッサシステムの情報を記憶する記憶手段と、前
記キャッシュメモリに新たなデータブロックを前記記憶
手段から入力する際に、前記キャッシュメモリ内の前記
データ格納ブロックデータの中から、データ不参照期間
と、前記記憶手段内のデータ内容との一貫性に基づいて
、データ置換ブロックとするデータ格納ブロックを選択
する選択手段とを有することを特徴とするキャッシュメ
モリブロック置換方式を備える。
ロック置換方式は、以下の様な構成からなる。即ち、 複数のプロセッサ各々がキャッシュメモリを備えるマル
チプロセッサシステムにおいて、複数の区別されたデー
タ格納ブロックを有するキャッシュメモリと、前記マル
チプロセッサシステムの情報を記憶する記憶手段と、前
記キャッシュメモリに新たなデータブロックを前記記憶
手段から入力する際に、前記キャッシュメモリ内の前記
データ格納ブロックデータの中から、データ不参照期間
と、前記記憶手段内のデータ内容との一貫性に基づいて
、データ置換ブロックとするデータ格納ブロックを選択
する選択手段とを有することを特徴とするキャッシュメ
モリブロック置換方式を備える。
［作用］
以上の構成により本発明は、複数のプロセッサ各々がキ
ャッシュメモリを備えるマルチプロセッサシステムにお
いて、キャッシュメモリ内のブロックデータ置換時に、
記憶手段との間でのデータ一貫性があり、かつ、最もデ
ータ不参照期間が長いブロックをデータ置換対象ブロッ
クとして選択するよう動作する。
ャッシュメモリを備えるマルチプロセッサシステムにお
いて、キャッシュメモリ内のブロックデータ置換時に、
記憶手段との間でのデータ一貫性があり、かつ、最もデ
ータ不参照期間が長いブロックをデータ置換対象ブロッ
クとして選択するよう動作する。
［実施例］
以下添付図面を参照して本発明の好適な実施例を詳細に
説明する。
説明する。
第４図は、本実施例におけるマルチプロセッサシステム
のブロック構成図である。
のブロック構成図である。
同図において、４１．４２、・・・、４ｎはプロセッサ
エレメント（ＰＥ）であり、ＰＥ４１は、各種処理を行
うプロセッサ４１１と、このプロセッサ４１１のための
キャッシュメモリ４１２とを含んでいる。
エレメント（ＰＥ）であり、ＰＥ４１は、各種処理を行
うプロセッサ４１１と、このプロセッサ４１１のための
キャッシュメモリ４１２とを含んでいる。
プロセッサ４１１は、主記憶４０にアクセスし、その情
報の一部をキャッシュメモリ４１２にフビーして利用し
、また、その内容を必要に応じて書き換えるものである
。
報の一部をキャッシュメモリ４１２にフビーして利用し
、また、その内容を必要に応じて書き換えるものである
。
他のＰＨの構成・動作も同様である。
第１図は本発明の代表的な実施例である４ウエイ・セッ
トアソシアティブ方式のキャッシュメモリ（以下、キャ
ッシュという）の一部の構成を示す図である。第１図に
おいて、１はキャッシュ中に格納されるブロックの属性
情報を記憶するタグアレイ、２はそのキャッシュ・ライ
ン中に有効なブロックが格納されているか否かを示す有
効ビット（Ｖａｌｉｄ ｂｉｔ ： Ｖ−ｂｉｔ） 、
３はキャッシュアクセス時のアドレス比較に用いるア
ドレスタグ、４はそのキャッシュ・ライン中に格納され
ているブロックが最後にアクセスされた時刻を示すタイ
ムスタンプ、５，６はマルチキャッシュ−貫性保持のた
めに用いるビットで、そのキャッシュ・ライン中に格納
されているブロックの状態を示すものであり、５はその
ブロックと主記憶中の対応ブロックとの一致がとられて
いるか否かを示すダーティビット（Ｄｉｒｔｙ ｂｉｔ
： Ｄ−ｂｉｔ） 、 ６は他プロセツサのキャッシ
ュ中にもそのブロックと同一のものが格納されている可
能性があるか否かを示す共有ビット（Ｓｈａｒｅｄ ｂ
ｉｔ： ５−ｂｉｔ） 、 ７は新たなブロックのキャ
ッシュへのローディング時にどのキャッシュ・ラインに
格納するかを決定する論理回路である。ここで、キャッ
シュ・ライン中に有効なブロックが格納されていれば、
Ｖ−ｂｉｔはオンに有効なブロックが格納されていなけ
れば、Ｖ−ｂｉｔはオフになる。次にキャッシュ中、ブ
ロックと主記憶中の対応ブロックとの一致がとられてれ
ば、Ｄ−ｂｉｔはオフに、ブロックと主記憶中の対応ブ
ロックとの一致がないならば、Ｄ−ｂｉｔはオンである
とする。
トアソシアティブ方式のキャッシュメモリ（以下、キャ
ッシュという）の一部の構成を示す図である。第１図に
おいて、１はキャッシュ中に格納されるブロックの属性
情報を記憶するタグアレイ、２はそのキャッシュ・ライ
ン中に有効なブロックが格納されているか否かを示す有
効ビット（Ｖａｌｉｄ ｂｉｔ ： Ｖ−ｂｉｔ） 、
３はキャッシュアクセス時のアドレス比較に用いるア
ドレスタグ、４はそのキャッシュ・ライン中に格納され
ているブロックが最後にアクセスされた時刻を示すタイ
ムスタンプ、５，６はマルチキャッシュ−貫性保持のた
めに用いるビットで、そのキャッシュ・ライン中に格納
されているブロックの状態を示すものであり、５はその
ブロックと主記憶中の対応ブロックとの一致がとられて
いるか否かを示すダーティビット（Ｄｉｒｔｙ ｂｉｔ
： Ｄ−ｂｉｔ） 、 ６は他プロセツサのキャッシ
ュ中にもそのブロックと同一のものが格納されている可
能性があるか否かを示す共有ビット（Ｓｈａｒｅｄ ｂ
ｉｔ： ５−ｂｉｔ） 、 ７は新たなブロックのキャ
ッシュへのローディング時にどのキャッシュ・ラインに
格納するかを決定する論理回路である。ここで、キャッ
シュ・ライン中に有効なブロックが格納されていれば、
Ｖ−ｂｉｔはオンに有効なブロックが格納されていなけ
れば、Ｖ−ｂｉｔはオフになる。次にキャッシュ中、ブ
ロックと主記憶中の対応ブロックとの一致がとられてれ
ば、Ｄ−ｂｉｔはオフに、ブロックと主記憶中の対応ブ
ロックとの一致がないならば、Ｄ−ｂｉｔはオンである
とする。
第２図は置換対象ブロック選択論理回路７の構成を示す
ブロック図である。同図において、８は各ウェイのタイ
ムスタンプを入力とし、ＬＲＵ順（つまり、最も長い期
間参照されていない順）にウェイ番号（ＬＲＵＷＯ〜３
）と、Ｌ ＲＬＩ Ｗ ｉとＬＲＵＷｉ＋１ （ｉ＝ｏ
〜２）のタイムスタンプの差（ｄｉｆＯ−１，ｄｉｆｌ
−２，ｄｉｆ２−３）とを出力するウェイ番号及びウェ
イ間時間差出力回路であり、９は回路８の出力と各ウェ
イのＤ−ｂｉｔを入力とし、それら入力に基づいて置換
対象ウェイを選択する置換対象ウェイ選択回路である。
ブロック図である。同図において、８は各ウェイのタイ
ムスタンプを入力とし、ＬＲＵ順（つまり、最も長い期
間参照されていない順）にウェイ番号（ＬＲＵＷＯ〜３
）と、Ｌ ＲＬＩ Ｗ ｉとＬＲＵＷｉ＋１ （ｉ＝ｏ
〜２）のタイムスタンプの差（ｄｉｆＯ−１，ｄｉｆｌ
−２，ｄｉｆ２−３）とを出力するウェイ番号及びウェ
イ間時間差出力回路であり、９は回路８の出力と各ウェ
イのＤ−ｂｉｔを入力とし、それら入力に基づいて置換
対象ウェイを選択する置換対象ウェイ選択回路である。
次に置換対象ウェイを選択する方式について、第３図に
示すフローチャートを参照しながら説明する。
示すフローチャートを参照しながら説明する。
まずステップＳＩＯにおいて、システムのいづれかのプ
ロセッサにおいてキャッシュ・ミスが検知されると、ス
テップＳ１５では当該セットの全てのラインのＶ−ｂｉ
ｔ、タイムスタンプ、及び、Ｄ−ｂｉｔの値がタグアレ
イ１から置換対象ブロック選択論理回路７へ読み込まれ
る。これに続いてステップＳ２０では、置換対象ブロッ
ク選択論理回路７が、有効でないブロックの存在の有無
を調べる。本実施例においては、ウェイ０、ウェイ１、
ウェイ２、ウェイ３の順にＶ−ｂｉｔのチエツクが行わ
れ（ステップＳ２５〜５４０）、有効でないウェイ、即
ち、Ｖ−ｂｉｔがオンではないウェイが確認された場合
、そのウェイに対して新たなブロックのローディングが
行われる（ステップＳ４５〜５６０）。
ロセッサにおいてキャッシュ・ミスが検知されると、ス
テップＳ１５では当該セットの全てのラインのＶ−ｂｉ
ｔ、タイムスタンプ、及び、Ｄ−ｂｉｔの値がタグアレ
イ１から置換対象ブロック選択論理回路７へ読み込まれ
る。これに続いてステップＳ２０では、置換対象ブロッ
ク選択論理回路７が、有効でないブロックの存在の有無
を調べる。本実施例においては、ウェイ０、ウェイ１、
ウェイ２、ウェイ３の順にＶ−ｂｉｔのチエツクが行わ
れ（ステップＳ２５〜５４０）、有効でないウェイ、即
ち、Ｖ−ｂｉｔがオンではないウェイが確認された場合
、そのウェイに対して新たなブロックのローディングが
行われる（ステップＳ４５〜５６０）。
さて全てのウェイに有効なブロックが格納されていた場
合、処理はステップＳ６５に進みウェイ番号及びウェイ
間時間差出力回路８を起動する。
合、処理はステップＳ６５に進みウェイ番号及びウェイ
間時間差出力回路８を起動する。
さらにステップＳ７０ではウェイ番号及びウェイ間時間
差出力回路８がウェイ番号（ＬＲＵＷＯ〜３）及びウェ
イ間時間差（ｄｉｆＯ−１，ｄｉｆｌ−２，ｄｉｆ２−
３）を出力する。ステップＳ７５では置換対象ウェイ選
択回路９が起動され、ウェイ番号（ＬＲＵＷＯ〜３）、
ウェイ間時間差（ｄｉｆｏ−１，ｄｉｆｌ−２，ｄｉｆ
２−３）及び各ウェイのＤ−ｂｉｔの値を読み込む。
差出力回路８がウェイ番号（ＬＲＵＷＯ〜３）及びウェ
イ間時間差（ｄｉｆＯ−１，ｄｉｆｌ−２，ｄｉｆ２−
３）を出力する。ステップＳ７５では置換対象ウェイ選
択回路９が起動され、ウェイ番号（ＬＲＵＷＯ〜３）、
ウェイ間時間差（ｄｉｆｏ−１，ｄｉｆｌ−２，ｄｉｆ
２−３）及び各ウェイのＤ−ｂｉｔの値を読み込む。
次に置換対象ウェイ選択回路９では、最終的な置換対象
ブロックを以下のように選択する。
ブロックを以下のように選択する。
ステップＳ８０ではＬＲＵＷＯのＤ−ｂｉｔがオンであ
るかどうかを調べる。ここで、オフとなっている場合、
即ち、そのウェイを置換対象ブロックとして選択しても
、キャッシュ−主記憶装置間でデータの一致があるため
に主記憶にデータを書き戻す必要がない場合、処理はス
テップ５１１５に進み、そのウェイが置換対象ブロック
として選択される。これに対して、Ｄ−ｂｉｔがオンと
なっていた場合、即ち、そのウェイを置換対象ブロック
として選択すると、キャッシュ−主記憶装置間でデータ
の不一致があるためにデータ主記憶に書き戻す必要があ
る場合、処理はステップＳ８５に進み、ＬＲＵＷＩをチ
エツクする。ここで、ＬＲＵＷｌのＤ−ｂｉｔがオフで
あるなら処理はさらにステップＳ９０に進み、ｄｉｆＯ
−１の値を調べる。
るかどうかを調べる。ここで、オフとなっている場合、
即ち、そのウェイを置換対象ブロックとして選択しても
、キャッシュ−主記憶装置間でデータの一致があるため
に主記憶にデータを書き戻す必要がない場合、処理はス
テップ５１１５に進み、そのウェイが置換対象ブロック
として選択される。これに対して、Ｄ−ｂｉｔがオンと
なっていた場合、即ち、そのウェイを置換対象ブロック
として選択すると、キャッシュ−主記憶装置間でデータ
の不一致があるためにデータ主記憶に書き戻す必要があ
る場合、処理はステップＳ８５に進み、ＬＲＵＷＩをチ
エツクする。ここで、ＬＲＵＷｌのＤ−ｂｉｔがオフで
あるなら処理はさらにステップＳ９０に進み、ｄｉｆＯ
−１の値を調べる。
ここで、ｄｉｆＯ−１の値が所定の値より小さい場合、
即ち、ＬＲＵＯとＬＲＵ １の時刻があまり違わない場
合は処理はステップ５１２０に進み、ＬＲＵＷＩを置換
対象ブロックとして選択する。
即ち、ＬＲＵＯとＬＲＵ １の時刻があまり違わない場
合は処理はステップ５１２０に進み、ＬＲＵＷＩを置換
対象ブロックとして選択する。
これに対してｄｉｆｏ−１の値が所定の値に比べて大き
い場合、即ち、ＬＲＵＯとＬＲＵＩの時刻がかなり異な
る場合は処理はステップ５１１５に進み、ＬＲＵＷＯを
置換対象ブロックとして選択する。
い場合、即ち、ＬＲＵＯとＬＲＵＩの時刻がかなり異な
る場合は処理はステップ５１１５に進み、ＬＲＵＷＯを
置換対象ブロックとして選択する。
以下同様にして、ＬＲＬＩＷＩのＤ−ｂｉｔがオンであ
る場合、ＬＲＵＷ２のＤ−ｂｉｔがオンである場合、そ
して、ＬＲＵＷ３のＤ−ｂｉｔがオンである場合ステッ
プ３９５〜５１１０の処理が行われ、ステップ５１１５
〜１３０のいずれかの処理が選択されＬＲＵＷＯＡ−Ｗ
３のいずれかのウェイが置換対象となる。最後に、ステ
ップ８１１５〜５１３０の処理に従って、ステップ５１
３５〜５１５０では対象となるブロックのローディング
が実行される。
る場合、ＬＲＵＷ２のＤ−ｂｉｔがオンである場合、そ
して、ＬＲＵＷ３のＤ−ｂｉｔがオンである場合ステッ
プ３９５〜５１１０の処理が行われ、ステップ５１１５
〜１３０のいずれかの処理が選択されＬＲＵＷＯＡ−Ｗ
３のいずれかのウェイが置換対象となる。最後に、ステ
ップ８１１５〜５１３０の処理に従って、ステップ５１
３５〜５１５０では対象となるブロックのローディング
が実行される。
従って本実施例に従うなら、データ参照されない期間が
最も長いブロックが自動的に置換対象ブロックとして選
択される訳ではな（、データ参照されない期間が長いブ
ロックグループであってもキャッシュと主記憶装置間の
データ一貫性を考慮し、キャッシュと主記憶装置間のデ
ータ一貫性があるブロック（データを書き戻す必要がな
いブロック）が置換対象ブロックとして選択され、また
全てのブロックにキャッシュと主記憶装置間のデータ一
貫性がない場合には、データ参照されない期間が最も長
いブロックが置換対象ブロックとして選択される。
最も長いブロックが自動的に置換対象ブロックとして選
択される訳ではな（、データ参照されない期間が長いブ
ロックグループであってもキャッシュと主記憶装置間の
データ一貫性を考慮し、キャッシュと主記憶装置間のデ
ータ一貫性があるブロック（データを書き戻す必要がな
いブロック）が置換対象ブロックとして選択され、また
全てのブロックにキャッシュと主記憶装置間のデータ一
貫性がない場合には、データ参照されない期間が最も長
いブロックが置換対象ブロックとして選択される。
［発明の効果］
以上説明したように本発明によれば、単にデータ不参照
期間の長さによるのではなく、キャッシュ−主記憶装置
間のデータ一貫性をも考慮して置換対象ブロックを選択
するので、主記憶装置−プロセッサ間のアクセス頻度を
軽減するという効果がある。従って、マルチプロセッサ
システムのシステムの総合性能を向上させるという利点
も有する。
期間の長さによるのではなく、キャッシュ−主記憶装置
間のデータ一貫性をも考慮して置換対象ブロックを選択
するので、主記憶装置−プロセッサ間のアクセス頻度を
軽減するという効果がある。従って、マルチプロセッサ
システムのシステムの総合性能を向上させるという利点
も有する。
第１図は本発明の代表的な実施例である４ウエイ・セッ
トアソシアティブ・キャッシュのタグアレイの構成を示
す図、 第２図は置換対象ブロック選択論理回路の構成を示す図
、 第３図は置換対象ブロック選択処理を示すフローチャー
ト、そして、 第４図は実施例のマルチプロセッサシステムのブロック
構成図である。 図中、１・・・タグアレイ、２・・・有効ビット、３・
・・アドレスタグ、４・・・タイムスタンプ、５・・・
ダーティビット、６・・・共有ビット、７・・・置換ブ
ロック選択論理回路、８・・・ウェイ番号及びウェイ間
時間差出力回路、９・・・置換対象ウェイ選択回路であ
る。 特許出願人 キャノン株式会社 代理人 弁理士 大塚康徳（他１名）、〜二二・ ゝコー二＝た１
トアソシアティブ・キャッシュのタグアレイの構成を示
す図、 第２図は置換対象ブロック選択論理回路の構成を示す図
、 第３図は置換対象ブロック選択処理を示すフローチャー
ト、そして、 第４図は実施例のマルチプロセッサシステムのブロック
構成図である。 図中、１・・・タグアレイ、２・・・有効ビット、３・
・・アドレスタグ、４・・・タイムスタンプ、５・・・
ダーティビット、６・・・共有ビット、７・・・置換ブ
ロック選択論理回路、８・・・ウェイ番号及びウェイ間
時間差出力回路、９・・・置換対象ウェイ選択回路であ
る。 特許出願人 キャノン株式会社 代理人 弁理士 大塚康徳（他１名）、〜二二・ ゝコー二＝た１
Claims (1)
- 【特許請求の範囲】 複数のプロセッサ各々がキャッシュメモリを備えるマ
ルチプロセッサシステムにおいて、複数の区別されたデ
ータ格納ブロックを有するキャッシュメモリと、前記マ
ルチプロセッサシステムの情報を記憶する記憶手段と、 前記キャッシュメモリに新たなデータブロックを前記記
憶手段から入力する際に、前記キャッシュメモリ内の前
記データ格納ブロックデータの中から、データ不参照期
間と、前記記憶手段内のデータ内容との一貫性に基づい
て、データ置換ブロックとするデータ格納ブロックを選
択する選択手段とを有することを特徴とするキャッシュ
メモリブロック置換方式。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP32589590A JP3236287B2 (ja) | 1990-11-29 | 1990-11-29 | マルチプロセッサシステム |
| US07/799,091 US5386546A (en) | 1990-11-29 | 1991-11-27 | Block substitution method in a cache memory of a multiprocessor system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP32589590A JP3236287B2 (ja) | 1990-11-29 | 1990-11-29 | マルチプロセッサシステム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04205041A true JPH04205041A (ja) | 1992-07-27 |
| JP3236287B2 JP3236287B2 (ja) | 2001-12-10 |
Family
ID=18181800
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP32589590A Expired - Fee Related JP3236287B2 (ja) | 1990-11-29 | 1990-11-29 | マルチプロセッサシステム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5386546A (ja) |
| JP (1) | JP3236287B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5729711A (en) * | 1993-06-02 | 1998-03-17 | Sharp Kabushiki Kaisha | Data driven information processing system using address translation table to keep coherent cache and main memories and permitting parallel readings and writings |
| JPH10149310A (ja) * | 1996-09-30 | 1998-06-02 | Internatl Business Mach Corp <Ibm> | モバイル・ユーザ・ファイル・システムにおけるキャッシュ管理のためのシステムおよび方法 |
| JP2010123130A (ja) * | 2008-11-21 | 2010-06-03 | Nvidia Corp | 複数クラスデータキャッシュポリシー |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5493668A (en) * | 1990-12-14 | 1996-02-20 | International Business Machines Corporation | Multiple processor system having software for selecting shared cache entries of an associated castout class for transfer to a DASD with one I/O operation |
| JPH07152693A (ja) * | 1993-11-29 | 1995-06-16 | Canon Inc | 情報処理装置 |
| US5551048A (en) * | 1994-06-03 | 1996-08-27 | Digital Equipment Corporation | Ring based distributed communication bus for a multiprocessor network |
| US5715106A (en) * | 1994-10-17 | 1998-02-03 | Adaptec, Inc. | Disk system with headerless track format, embedded servo fields and constant density recording |
| US6021472A (en) * | 1995-08-21 | 2000-02-01 | Canon Kabushiki Kaisha | Information processing device and control method thereof |
| US5860110A (en) * | 1995-08-22 | 1999-01-12 | Canon Kabushiki Kaisha | Conference maintenance method for cache memories in multi-processor system triggered by a predetermined synchronization point and a predetermined condition |
| US5865308A (en) * | 1996-10-29 | 1999-02-02 | Baxter International Inc. | System, method and device for controllably releasing a product |
| US5822759A (en) * | 1996-11-22 | 1998-10-13 | Versant Object Technology | Cache system |
| JPH10154100A (ja) * | 1996-11-25 | 1998-06-09 | Canon Inc | 情報処理システム及び装置及びその制御方法 |
| US5940862A (en) * | 1997-03-24 | 1999-08-17 | Adaptec, Inc. | Data sector mark generation for a headerless disk drive architecture |
| US6000018A (en) * | 1997-06-17 | 1999-12-07 | Adaptec, Inc. | System for aligning control words for identifying boundaries of headerless data sectors using automatic incrementing and discarding of data frame numbers |
| US7013305B2 (en) | 2001-10-01 | 2006-03-14 | International Business Machines Corporation | Managing the state of coupling facility structures, detecting by one or more systems coupled to the coupling facility, the suspended state of the duplexed command, detecting being independent of message exchange |
| US6728839B1 (en) * | 1998-10-28 | 2004-04-27 | Cisco Technology, Inc. | Attribute based memory pre-fetching technique |
| US6282617B1 (en) * | 1999-10-01 | 2001-08-28 | Sun Microsystems, Inc. | Multiple variable cache replacement policy |
| US7275135B2 (en) * | 2001-08-31 | 2007-09-25 | Intel Corporation | Hardware updated metadata for non-volatile mass storage cache |
| US7613870B2 (en) * | 2004-11-18 | 2009-11-03 | International Business Machines Corporation | Efficient memory usage in systems including volatile and high-density memories |
| EP1870813B1 (en) * | 2006-06-19 | 2013-01-30 | Texas Instruments France | Page processing circuits, devices, methods and systems for secure demand paging and other operations |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3848234A (en) * | 1973-04-04 | 1974-11-12 | Sperry Rand Corp | Multi-processor system with multiple cache memories |
| US4410944A (en) * | 1981-03-24 | 1983-10-18 | Burroughs Corporation | Apparatus and method for maintaining cache memory integrity in a shared memory environment |
| US4429363A (en) * | 1981-10-15 | 1984-01-31 | International Business Machines Corporation | Method and apparatus for managing data movements from a backing store to a caching buffer store |
| US4463420A (en) * | 1982-02-23 | 1984-07-31 | International Business Machines Corporation | Multiprocessor cache replacement under task control |
| US4783735A (en) * | 1985-12-19 | 1988-11-08 | Honeywell Bull Inc. | Least recently used replacement level generating apparatus |
| US4802086A (en) * | 1987-01-09 | 1989-01-31 | Motorola, Inc. | FINUFO cache replacement method and apparatus |
| US5224217A (en) * | 1988-12-30 | 1993-06-29 | Saied Zangenehpour | Computer system which uses a least-recently-used algorithm for manipulating data tags when performing cache replacement |
| US5043885A (en) * | 1989-08-08 | 1991-08-27 | International Business Machines Corporation | Data cache using dynamic frequency based replacement and boundary criteria |
-
1990
- 1990-11-29 JP JP32589590A patent/JP3236287B2/ja not_active Expired - Fee Related
-
1991
- 1991-11-27 US US07/799,091 patent/US5386546A/en not_active Expired - Lifetime
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5729711A (en) * | 1993-06-02 | 1998-03-17 | Sharp Kabushiki Kaisha | Data driven information processing system using address translation table to keep coherent cache and main memories and permitting parallel readings and writings |
| JPH10149310A (ja) * | 1996-09-30 | 1998-06-02 | Internatl Business Mach Corp <Ibm> | モバイル・ユーザ・ファイル・システムにおけるキャッシュ管理のためのシステムおよび方法 |
| JP2010123130A (ja) * | 2008-11-21 | 2010-06-03 | Nvidia Corp | 複数クラスデータキャッシュポリシー |
| US8868838B1 (en) | 2008-11-21 | 2014-10-21 | Nvidia Corporation | Multi-class data cache policies |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3236287B2 (ja) | 2001-12-10 |
| US5386546A (en) | 1995-01-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2822588B2 (ja) | キャッシュメモリ装置 | |
| JPH04205041A (ja) | マルチプロセッサシステム | |
| US5091851A (en) | Fast multiple-word accesses from a multi-way set-associative cache memory | |
| US6912628B2 (en) | N-way set-associative external cache with standard DDR memory devices | |
| JP3620473B2 (ja) | 共有キャッシュメモリのリプレイスメント制御方法及びその装置 | |
| EP0077453A2 (en) | Storage subsystems with arrangements for limiting data occupancy in caches thereof | |
| JPS61156346A (ja) | 記憶階層の先取り装置 | |
| US6832294B2 (en) | Interleaved n-way set-associative external cache | |
| JPH09223118A (ja) | スヌープキャッシュメモリ制御システム | |
| US6332179B1 (en) | Allocation for back-to-back misses in a directory based cache | |
| US6715040B2 (en) | Performance improvement of a write instruction of a non-inclusive hierarchical cache memory unit | |
| JP3929872B2 (ja) | キャッシュメモリ、プロセッサ及びキャッシュ制御方法 | |
| US7353341B2 (en) | System and method for canceling write back operation during simultaneous snoop push or snoop kill operation in write back caches | |
| KR20070040340A (ko) | 소형 캐시 시스템에서 원자적 보존 라인에 라이트백하는것을 배제하는 방법 및 시스템 | |
| JPH04230549A (ja) | 多重レベル・キャッシュ | |
| US6839806B2 (en) | Cache system with a cache tag memory and a cache tag buffer | |
| JP3733604B2 (ja) | キャッシュメモリ | |
| US6401173B1 (en) | Method and apparatus for optimizing bcache tag performance by inferring bcache tag state from internal processor state | |
| US6397295B1 (en) | Cache mechanism for shared resources in a multibus data processing system | |
| JPH0210446A (ja) | バッファ記憶装置 | |
| JP2000047942A (ja) | キャッシュメモリ制御装置及びその制御方法 | |
| JPH01228035A (ja) | データ処理装置 | |
| JP2001222467A (ja) | キャッシュ装置 | |
| EP0604030A2 (en) | Copy back cache tag memory | |
| JPH02224161A (ja) | 高速データ処理装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070928 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080928 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090928 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090928 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100928 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |