(57)【特許請求の範囲】
【請求項１】
コンピュータ・システムにおいてデータ・ページを一時的に記憶するキャッシュ記憶システムを動作させる方法であって、
前記キャッシュ記憶システムへの各参照について、同じページに対する２つの参照の間に行われる参照数を示す再使用距離を求めるステップと、
前記再使用距離の度数を累算することによって再使用分布を生成するステップと、
反復ページ参照数を求め、再使用シフト量を計算するステップと、
前記再使用分布を計算された前記再使用シフト量だけシフトすることにより、前記キャッシュ記憶システムのキャッシュ・ミス率曲線を生成するステップとを含む方法。
【請求項２】
前記再使用距離を求めるステップが、
データ・ストリーム内の各新規データ・ページ参照について固有の参照カウント番号を割り当てるステップと、
前記データ・ページが以前に参照されている場合、前記データ・ページの直前の参照カウント番号を決定するステップと、
前記再使用距離を、前記キャッシュ内の現行データ・ページ参照の参照カウントから同じデータ・ページの直前の参照カウントを引いた値に設定するステップとを含む、請求項１に記載の方法。
【請求項３】
前記再使用距離を設定するステップが、現行データ・ページの参照カウント番号が同じデータ・ページの直前の参照カウント番号より小さいか否かを判断するステップと、それに応答して、最大参照カウント値から前記直前の参照カウント番号を引き、現行参照カウント番号を加えることによって、前記再使用距離を求めるステップとを含む、請求項２に記載の方法。
【請求項４】
コンピュータ・システムにおいてデータ・ページを一時的に記憶するキャッシュ記憶システムであって、
データ・ページを受け入れるキャッシュ記憶装置と、
前記キャッシュ記憶システムへの各データ・ページ参照について同じページに対する２つの参照の間に行われる参照数を示す再使用距離を求め、前記再使用距離の度数を累算することによって再使用分布を生成し、反復ページ参照数を求め、再使用シフト量を計算し、前記再使用分布を計算された前記再使用シフト量だけシフトすることにより、前記キャッシュ記憶システムのキャッシュ・ミス率曲線を生成するキャッシュ・コントローラとを含むシステム。
【請求項５】
前記キャッシュ・コントローラが、
前記データ・ストリーム内の各新規データ・ページ参照について固有の参照カウント番号を割り当て、
前記データ・ページが以前に参照されている場合、前記データ・ページの直前の参照カウント番号を決定し、
前記再使用距離を、前記キャッシュ内の現行データ・ページ参照の参照カウントから同じデータ・ページの直前の参照カウントを引いた値に設定することによって、再使用距離を求める、請求項４に記載のシステム。
【請求項６】
前記キャッシュ・コントローラが、現行データ・ページの参照カウント番号が同じデータ・ページの直前の参照カウント番号より小さいか否かを判断し、それに応答して、最大参照カウント値から前記直前の参照カウント番号を引き、現行参照カウント番号を加えることによって前記再使用距離を求めることによって、前記再使用距離を設定する、請求項５に記載のシステム。
【請求項７】
コンピュータ・システムにおいてデータ・ページを一時的に記憶するキャッシュ記憶システム用のキャッシュ・コントローラであって、
中央処理装置と、
前記中央処理装置がそれを介して１つまたは複数のコンピュータと通信するネットワーク・インタフェースと、
前記中央処理装置によって実行され、前記キャッシュ記憶システムへの各データ・ページ参照について同じページに対する２つの参照の間に行われる参照数を示す再使用距離を求め、前記再使用距離の度数を累算することによって再使用分布を生成し、反復ページ参照数を求め、再使用シフト量を計算し、前記再使用分布を計算された前記再使用シフト量だけシフトすることにより、前記キャッシュ記憶システムのキャッシュ・ミス率曲線を生成するプログラム・ステップを含むプログラム・メモリとを含むキャッシュ・コントローラ。
【請求項８】
前記中央処理装置が、
前記データ・ストリーム内の各新規データ・ページ参照について固有の参照カウント番号を割り当て、
前記データ・ページが以前に参照されている場合、前記データ・ページの直前の参照カウント番号を決定し、
前記再使用距離を、前記キャッシュ内の現行データ・ページ参照の参照カウントから同じデータ・ページの直前の参照カウントを引いた値に設定することによって、再使用距離を求める、請求項７に記載のキャッシュ・コントローラ。
【請求項９】
前記中央処理装置が、現行データ・ページの参照カウント番号が同じデータ・ページの直前の参照カウント番号より小さいか否かを判断し、最大参照カウント値から前記直前の参照カウント番号を引き、現行参照カウント番号を加えることによって前記再使用距離を求めることによって、前記再使用距離を設定する、請求項８に記載のキャッシュ・コントローラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般にネットワーク・コンピュータ・システムに関し、詳細にはクライアント・コンピュータからサーバ・コンピュータへのデータの効率的な転送に関する。
【０００２】
【従来の技術】
コンピュータ・システムは、データの供給速度よりも高速で稼働することはできない。ほとんどのコンピュータ・ネットワークは、ネットワーク・リンクを介して互いにデータを交換する多数のサーバ・コンピュータとクライアント・コンピュータを含む。クライアントとサーバは、メモリおよびデータ記憶装置を共用することができる。たとえば、多くのコンピュータ・システムは、一次記憶装置を備えた階層メモリ記憶域を有し、一時記憶装置としては、たとえばディスク・ライブラリおよびＲＡＩＤ（Redundant Array of Inexpensive Disks：冗長性を持つ低価格ディスク・アレイ）がある。ディスク・ライブラリとＲＡＩＤシステムは、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）などの記憶装置と比較して低速なため、頻繁に使用される可能性が高いと思われるデータはキャッシュ・メモリと呼ばれるより高速のメモリに一時的に記憶される。このようなコンピュータ・システムのパフォーマンスを向上させる可能性の多くは、メモリ階層の効率的な制御にかかっている。
【０００３】
キャッシュなどのメモリ階層の効率は、キャッシュ・ミス率によって特徴づけられる。キャッシュ・ミスは、データ参照が要求されたが、キャッシュ内で見つからない時間の割合である。一般に、キャッシュが大きい方がキャッシュ・ミス率が低くなり、システム・パフォーマンスが向上する。これは、キャッシュ・ミスがあると、ディスク・メモリなどのより低速で安価なデータ記憶装置からデータを検索する必要があり、したがって、プロセッサがデータを待つためにシステム・データ操作が遅くなるためである。キャッシュは一般に、半導体メモリを使用して作られ、高価格な場合があるため、キャッシュは通常、サイズが限られ、目標ミス率に合わせて設計される。システム管理作業は、使用可能資源と許容可能なミス率にとって最も効率的なキャッシュを決定することである。さらに、キャッシュは区画化することができ、作業負荷ストリームにキャッシュ区分を割り振ることによってデータ記憶調整を行うことができる。システム管理作業は、キャッシュ・サイズ決定とキャッシュ割振りによって対処する作業負荷分散問題になる。
【０００４】
データ参照の作業負荷ストリームが固定していることを考えると、キャッシュ・ミス率はキャッシュ・サイズの関数としてプロットすることができる。したがって、プロットされたキャッシュ・ミス率曲線によって、キャッシュ・サイズの増大の効果が逓減する点に達する時点がわかり、したがってキャッシュ・ミス率曲線を使用して、キャッシュ・サイズと作業負荷へのキャッシュ割振りに関する決定を行うことができる。キャッシュ・ミス率曲線を経験により判断するには、作業負荷を用意し、その作業負荷を使用して様々なサイズのキャッシュを動作させ、その間、発生したミス率の統計をとり続ける必要がある。キャッシュ・サイズの範囲は膨大になり得るため、これはきわめて困難であり、時間がかかる可能性がある。たとえば、キャッシュ・サイズは、優に１０メガバイト（ＭＢ）から１０ギガバイト（ＧＢ）のデータまで変わり得る。
【０００５】
キャッシュ動作のオフライン・シミュレーションによって、所与のサイズと所与の作業負荷についてキャッシュ・ミス率を決定することが可能である。このシミュレーションは、所定の作業負荷を使用してシステム・トレースを生成することによって行われる。これは、コンピュータ・システムにおいて必要なすべてのデータ参照の履歴記録である。たとえば、システム・トレースは、対象期間に参照されたすべてのデータ・ページ（４Ｋバイトのデータのブロック）を含む作業負荷の結果とすることができる。シミュレーションするキャッシュのサイズによってヒットがあるかミスがあるかが決まるため、各データ参照の実際のシステム結果は、シミュレーションにとって重要ではない。シミュレーション・プログラムはトレースを受け取り、トレース内の各要求を処理し、トレース内の各データ参照の結果、キャッシュ・ヒットとミスのどちらになったかをシミュレーションしたキャッシュのサイズに応じて判断する。このようなシミュレーションで使用されるシステム・トレースは、「ＴＰＣ−Ｃ」や「ＴＰＣ−Ｄ」と呼ばれる公知のトレース・ベンチマークなどの業界標準のベンチ・マークとすることができる。
【０００６】
したがって、システム・トレースとオフライン・シミュレーションを使用すれば、様々なキャッシュ・サイズを構成して動作させなくても、キャッシュ・ミス率曲線を導き出すことができる。しかし残念ながら、システム・トレースは、かなり大きなファイルとなることがあり、シミュレーションの実行には長時間かかることがある。有効なシミュレーション結果が得られるように保証するために、トレースのサイズは一般に、シミュレートする最大キャッシュのサイズの少なくとも１０倍になる。したがって、キャッシュの動作をシミュレートし、キャッシュ・ミス率曲線を導き出す技法が開発されている。キャッシュ・ミス率を求める１つの方法は、キャッシュ動作を参照の列、またはスタックとしてシミュレートすることである。このような技法はスタック・アルゴリズムと呼ばれる。１つのこのようなキャッシュ分析技法は、ＬＲＵ（最長期間不使用）キャッシュとして編成されたキャッシュとして構成されたキャッシュを使用する。ＬＲＵキャッシュでは、データ参照がスタックとして保持され、新しいデータ参照がスタックの最上部に入れられ、古いデータ参照はスタックの下の方に下げられる。各データ参照には、スタックの最上部からキャッシュ項目が入れられている場所までの距離を表すスタック距離が関連づけられる。システム・トレース内の各データ参照ごとに、スタック距離によってキャッシュ・ヒットがあるかキャッシュ・ミスがあるかが決まる。
【０００７】
どのキャッシュもデータ・スタックとして表すことができ、システム・トレースを適用して、特定のサイズのキャッシュについてキャッシュ・ヒットとミスを決定することができる。たとえば、図１は、ＬＲＵスタックのシステム・トレースにおけるデータ参照のシーケンスに対応する複数の列を示すキャッシュ動作のスタック図である。最初は空のスタックを左から右に進み、図１の左端の列１０２は、最初のデータ参照がデータ「Ａ」に対する要求であることを示しており、これは、たとえば特定の４Ｋデータ・ブロックまたはページの要求である。Ａは最初はスタック内に入っていないため、Ａに対する要求はキャッシュ・ミスである。そのため、Ａはキャッシュに入れられることになり、したがってスタックの最上部であるキャッシュ場所「１」に置かれる。次の列１０４に移ると、次のデータ参照は「Ｂ」に対する要求であり、これも最初はキャッシュに入っておらず、キャッシュ・ミスになる。したがって、Ｂがキャッシュに入れられ、それによってＡはスタック内でスタック場所「２」に押し下げられ、Ｂが最上部に置かれる。同様に、図１の３番目の列１０６は次のデータ参照が「Ｃ」であることを示し、これも別のキャッシュ・ミスになり、その結果Ｃがキャッシュに入れられ、したがってスタックの最上部に置かれる。
【０００８】
当業者なら、図１の４番目の列１０８が、次のデータ参照がすでにキャッシュに入っているＢページを指していることを示していることがわかるであろう。このＬＲＵスタックでは、このデータ参照を受け取ったときのＢの「スタック距離」は、直前の列１０６内でＢが最上部から１つ下の２番目のスタック位置にあるため、２であると言える。実際のキャッシュ動作では、データ・ページＢの参照の結果、キャッシュ内でＢが探索され、Ｂがキャッシュ内にあるか否かが解決されることになる。これを、Ｂページ参照の解決の参照間隔と呼ぶ。キャッシュをスタックとしてシミュレーションすると、Ｂに対する参照の結果、Ｂページがスタックの最上部に移動し、現行スタック間隔１０８でＣが押し下げられる。キャッシュが少なくとも２つのページ・メモリ場所を有する場合、Ｂはキャッシュ内の１０６にあり、その時点でのＢに対するデータ参照の結果、１０８でキャッシュ・ヒットになることは明らかであろう。図１の次の列１１０は、キャッシュ内にない「Ｄ」に対する参照を示す。この結果、キャッシュ・ミスになり、Ｄがスタックの最上部に置かれる。
【０００９】
６番目の列１１２は、キャッシュ内にあるＣに対する他のデータ参照が発生したことを示し、したがってＣがスタックの最上部に移動する。前の列１１０で、Ｃのスタック距離は３であった。したがって、１１０でＣに対する要求を受け取ったとき、キャッシュが少なくとも３つのページ・メモリ場所を有する場合は、シミュレーションされているキャッシュでキャッシュ・ヒットが起こり、そうでない場合にはキャッシュ・ミスになる。最後に、図１の７番目の列１１４は、Ａに対する他の参照を示し、これがスタックの最上部に移動する。直前の列１１２で、Ａのスタック距離は４であった。したがって、４データ・ページ以上のキャッシュ・サイズであれば、１１２におけるＡに対するデータ参照がキャッシュ・ヒットになり、それより小さい場合にはキャッシュ・ミスになることが明らかであろう。
【００１０】
したがって、キャッシュ・ミス率曲線を求めるには、データ参照のキャッシュ距離を求め、ヒットとミスのいずれがあったかを判断する必要があり、スタック全体を探索してスタック内の参照の場所を見つける必要がある。このシミュレーションのこの局面に必要な探索の量によって、大量のシステム資源が消費される可能性がある。最近、キャッシュ・ミス率曲線の導出を向上させようとして、スタック分析技法が取り入れられている。
【００１１】
たとえば、米国特許第５６２７９９４号には、キャッシュ・アーキテクチャに要求ストリームとメモリ資源を割り振る方法が記載されており、スタック分析によってスタック距離分布を求める。このようなスタック分析技法を使用して、キャッシュ・サイズ決定の問題に対処し、システム・パフォーマンスを向上させることができる。
【００１２】
キャッシュ記憶システムの供給者やメモリ管理プログラム供給者は、キャッシュ・パラメータを調整する多くの機会を提供している。１つの最適な技法は、キャッシュ・パラメータの動的自己調整を可能にし、キャッシュ区分と参照ストリーム割振りの効果を自動的に判断するものであろう。手動と自動のいずれで調整行うかを問わず、情報に基づくキャッシュ・パラメータの調整を行うには、様々な動作パラメータについてキャッシュ・ミス曲線を求める必要があることは明らかであろう。また、システム動作の低下を避けるため、動的自己調整技法によってきわめて効率的にキャッシュミス率曲線を導き出さなければならないことも明らかであろう。
【００１３】
【発明が解決しようとする課題】
以上の説明から、広範囲なキャッシュ・サイズのキャッシュ・ミス率を効率的に導き出せるスタック分析技法が必要であることが明らかであろう。本発明は、この必要を満たすものである。
【００１４】
【課題を解決するための手段】
本発明は、スタック再使用距離を定義し、最近使用されたページの中で反復使用されたページ参照の数を除いたスタック再使用距離を求めることによってスタック距離を近似計算することができることを認める。本発明によると、スタック再使用距離を、１つのデータに対する最初の参照と同じデータに対する次の参照との間の参照数と定義し、それによって、ストリーム内のデータ参照のカウントを維持することによってスタック再使用距離を容易に計算することができるようにする。さらに、本発明は、キャッシュ内の同じページに対する２つの参照間の反復ページ参照数を、確率的方式で近似計算することができ、それによってキャッシュ分析の効率が向上することを認める。これによって、スタック距離を通常のシステム動作中に近似計算することができ、データ参照作業負荷に応答して最適なキャッシュ調整を行うために、スタック分析を動的方式で行うことができるようにして、スタック距離を効率的に導き出すことができる。したがって、キャッシュ・ミス率曲線は、システム・トレースからオフライン・モードで、または通常のシステム動作中にリアルタイムで生成される。このようにして、様々なキャッシュ動作パラメータを静的環境でも動的環境でも調整することができる。
【００１５】
本発明の一態様では、データ・ストリーム内の各参照ごとに再使用距離を計算し、そのストリームの特性である再使用分布を生成する。再使用距離と再使用分布は両方とも、キャッシュ記憶システムが動作するときにデータを累算することによって容易に生成される。本発明の他の態様では、再使用距離がデータ・ストリーム内の参照の各対間の距離より小さくなる累積確率によって、重複ページ数を近似計算する。これによって、データ・ストリームがオフライン・システム・トレースである必要がなく、データ参照の進行中のストリームとすることができるほど、十分に高い効率でスタック分析を行うことができ、それによってキャッシュ・パラメータの動的調整を容易に行うことができる。
【００１６】
【発明の実施の形態】
本発明は、所与の参照のスタック距離を求める際に最も困難なのは、現行ページの参照間隔中に参照される他のページ数を計算に入れることであると認識する。さらに本発明は、データ参照（またはページ要求）のストリームを調べ、同一ページに対する２つの参照の間の、他のページに対する反復参照を計算にいれる必要があることを認識する。本発明によると、参照「再使用距離」を定義し、それを使用してスタック距離を近似計算し、そこからキャッシュ・ミス率曲線を作成する。具体的には、現行ページに対するデータ参照の再使用距離を、現行ページに対する最後の参照以来の他のページに対する参照数であると定義する。好ましい実施形態では、スタック距離は、再使用距離の累積分布から近似計算される。再使用距離の累算は、システム処理資源とデータ記憶コストの両方の相対効率で行うことができる。このようにして、広範囲なキャッシュ・サイズのキャッシュ・メモリ・システムのキャッシュミス率を求めることができる。この技法の効率は、キャッシュ動作パラメータの動的調整を行うことができるような効率である。
【００１７】
スタック図
前述のように、キャッシュは優先順位関数に従って順序づけされたスタックとして表すことができる。好ましい実施形態では、スタックはＬＲＵ（最長期間不使用）スタックとして編成され、最も最近に参照された（または要求された）データ・ブロックまたはページが最上位に置かれる。参照が置かれたスタック・レベルをそのスタック距離と呼び、そのページが存在する最小キャッシュ・サイズを表す。ＬＦＵ（最低使用頻度）を含むその他のスタック順序づけ技法およびその他の技法も、当業者には周知であろう。最も一般的なのは、ＬＲＵであり、本明細書では特に記載のない限りＬＲＵを使用するものとする。当業者なら、キャッシュ・ミス率はスタック距離の度数分布を累算することによって計算することができることがわかるであろう。具体的には、サイズＣのキャッシュと１ストリームのデータ参照について、スタック分布と呼ぶ累算スタック度数分布を以下の数式１によって求められる。
【数１】
0003657170.tif 000002
【００１８】
上式でｈｉｔ（ｉ）はスタック分布、Ｎはデータ参照のストリーム内の総参照数である。
【００１９】
図２に、本発明により定義された参照の再使用距離を示す。図２の隣り合ったボックスは、データ参照ｒ1、ｒ2、．．．ｒi、ｒi+1、．．．ｒjのストリームを示し、これらのデータ参照は、ｒiにおける最も早期の参照からｒjにおける最も最近の参照までの特定のページのデータの要求である。本発明によると、データ参照Ｒのスタック距離関数は、Ｒへの再使用距離から、Ｒに対する最後の参照以来の参照重複または反復参照数を引くことによって求められ、以下の数式２によって表される。
【数２】
Stack DistanceR(x)＝Reuse DistanceR(x)−Repeated PagesR(x)      （２）
【００２０】
上式で、ｘはストリーム内の特定のデータ参照を示す。したがって、図２のｒjにおけるＡに対する参照の場合、再使用距離は、最初のＡの参照からｒjにおける最後のＡの参照までの距離（ページ数）、すなわち７である。重複または反復参照数には、Ｂ（１回）とＣ（２回）が含まれ、３になることがわかる。したがって、図２のスタック距離は、７−３＝４である。数式２によって得られた図２に示す参照ストリームの結果、図１のスタック図になることに留意されたい。
【００２１】
最後の参照以来の重複ページ数は、一般に、再使用距離の累積分布である再使用分布によって決まることがわかっている。また、スタック距離は、重複ページを綿密に計算に入れることにより、再使用分布から推定することができることもわかっている。したがって、ｒi，ｒ1+1．．．によって与えらるデータ参照のストリームが、ｐi，ｐi+1，．．によって与えられる対応するデータ・ページを有し、特定の現行データ参照ｊであり、再使用距離はｄｉｓｔａｎｃｅreuse（ｊ）によって与えられ、スタック距離はｄｉｓｔａｎｃｅstack（ｊ）によって与えられ、ｐi＝ｐj、ｐi＝ｐkであり、［ｉ＜ｋ＜ｊ］である場合、ｄｉｓｔａｎｃｅreuseおよびｄｉｓｔａｎｃｅstackはそれぞれ、以下の数式３および数式４によって求められる。
【数３】
distancereuse(j)＝j-i        （３）
【数４】
distancestack(j)＝distancereuse(j)−Dup(i+1,j-1)    （４）
【００２２】
上式で、Ｄｕｐ（ｘ，ｙ）は参照されたページｐx，ｐx+1．．．，ｐyのストリーム中の重複ページ数を示す。本発明によると、次に指数づけ関数Ｘを定義する。Ｘは以下の数式５によって求められる。
【数５】
0003657170.tif 000003
【００２３】
次に、以下の数式６によって、Ｄｕｐ（ｘ，ｙ）が求められることがわかる。
【数６】
0003657170.tif 000004
【００２４】
次に、以下の数式７、数式８、および数式９に示すように、重複ページ関数の期待値Ｅを求めることができる。
【数７】
0003657170.tif 000005
【数８】
0003657170.tif 000006
【数９】
0003657170.tif 000007
【００２５】
上式で、Ｆreuse（ｋ）は、再使用距離の累積度数分布を示す。その結果、本発明によると、以下の数式１０によって求められる関係によってスタック距離を近似することができる。
【数１０】
0003657170.tif 000008
【００２６】
上式により、特定の参照ｊについてのスタック距離が得られる。
【００２７】
したがって、再使用距離と再使用距離の確率分布とから、参照のスタック距離を推定することができる。このような推定には多くの演算を行う必要がある。実際の演算数は、対象キャッシュ・サイズ内のページ数と同程度である。この推定をすべての参照に対して行った場合、システム資源のコストが所期のコストよりも高くつく可能性がある。本発明により構成されたシステムは、すべての参照について再使用距離の計算を必要とする、すべての参照のスタック距離の推定を回避する。本発明は、再使用距離の分布を累算し、スタック距離分布を定期的に推定することを企図する。スタック距離の累積確率分布をＦstack（ｋ）で表した場合、スタック分布は、以下の数式１１のように重複ページ関数の期待値によって近似することができる。
【数１１】
0003657170.tif 000009
【００２８】
この技法により、キャッシュ・ミス率をより迅速に求めることができ、その結果、キャッシュ管理タスクが簡略化される。この計算を行う処理の例について、以下に詳述する。
【００２９】
スタック分布を求め、最終的にキャッシュ・ミス率を求めるこの簡略化された技法によって、オフライン分析でも動的調整方式でも、キャッシュ調整が容易になることが、当業者ならわかるであろう。したがって、本発明により構築されたキャッシュ・コントローラを有するキャッシュ記憶システムによって、システム資源の動作効率と使用効率が向上する。
【００３０】
キャッシュ管理システムのブロック図
図３は、本発明により構築されたキャッシュ管理システム３００のブロック図である。ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）の形態のキャッシュ記憶装置３０２が、キャッシュ・コントローラ３０４の制御により稼働する。キャッシュ・コントローラは、キャッシュ・メモリ３０５を含む。キャッシュ・コントローラは、ネットワーク３０６およびネットワークに接続されているその他のコンピュータ３１０、３１２、３１４と通信する。コンピュータ３１０、３１２、３１４から、データの要求を含むデータ参照がネットワーク３０６を介してキャッシュ・コントローラ３０４に送られる。各要求は、４ＫＢページなどの所定のデータ・ブロックを求める要求である。キャッシュ・コントローラは、要求されたデータがキャッシュ３０２内にあるか否かを判断する。そのページがキャッシュに入っている場合はキャッシュ・ヒットと呼ばれる条件であり、キャッシュ・コントローラはそれに肯定応答で応答し、データの処理が続けられる。そのページがキャッシュ内にない場合はキャッシュ・ミスと呼ばれ、キャッシュ・コントローラは、ネットワーク上の他のデータ記憶装置、恐らくはコンピュータ３１０、３１２、３１４のうちの１つに対してデータを要求し、そのデータをキャッシュ３０２にロードし、要求されたデータの処理を続ける。
【００３１】
図４は、図３に示すキャッシュ・コントローラ３０４のコンピュータ・ブロック図４０２である。図３に示すコンピュータ・システムのうちの他のコンピュータ３１０、３１２、３１４は、図４に示すものと類似した構成を有しており、したがって、図４のコンピュータ４０２に関して述べる詳細はシステム３００のすべてのコンピュータに適用されるものと理解されたい。あるいは、他のコンピュータと通信することができ、それらの間でデータ・ブロックを転送することができる限り、コンピュータ３０４、３１０、３１２、３１４のいずれも、様々な構成を有することができる。
【００３２】
各コンピュータ４０２は、中央処理装置（ＣＰＵ）４０４と、プログラム・メモリ４０８およびデータ・メモリ４１０を含むメイン・メモリ４０６と、キーボードや表示装置などの入出力装置４１２と、ハード・ディスク・ドライブなどの直接アクセス記憶装置（ＤＡＳＤ）４１４とを含む。メイン・メモリ４０６は、典型的には、揮発性半導体ランダム・アクセス・メモリ（ＲＡＭ）を含む。ＤＡＳＤ４１４は、典型的には、実行されるとコンピュータ４０２のオペレーティング・システムを実現する命令を記憶するために使用される。オペレーティング・システムは、マイクロソフト社の「Ｗｉｎｄｏｗｓ９８」やアップル・コンピュータ社の「Ｍａｃｉｎｔｏｓｈ」などの多種多様なシステムのいずれかとすることができる。
【００３３】
各コンピュータ４０２は、プログラム製品記憶装置４１８を受け入れるプログラム製品読取装置４１６を含むことが好ましく、プログラム製品読取装置はプログラム製品記憶装置からデータを読み取ることができる（任意選択によりデータの書き込みもできる）。プログラム製品読取装置４１６は、たとえばディスク・ドライとすることができ、プログラム製品４１８は、磁気フロッピィ・ディスク、ＣＤ−Ｒ光磁気ディスク、またはＣＤ−ＲＷディスクなどの取り外し可能媒体とすることができる。システムの各コンピュータ４２０は、ネットワーク・インタフェース４２０を介してネットワーク３０６で他のコンピュータと通信することができ、それによってネットワーク・ノードを構成する。
【００３４】
各コンピュータ４０２は、メイン・メモリ４０６のプログラム記憶域４０８に記憶されている命令を実行することによってその機能を実行する。プログラム命令が実行されると、コンピュータはその機能を実行する。これは、キャッシュ・コントローラ３０２の場合はキャッシュ管理機能である。この命令は、プログラム製品記憶装置読取装置４１６またはネットワーク・インタフェース４２０を介してＤＡＳＤ４１４から受け取ることができる。記憶装置読取装置４１６は、プログラム製品記憶装置４１８を受け入れ、プログラム製品記憶装置に記録されているプログラム・ステップを読み取り、それらのプログラム・ステップをメイン・メモリ４０６に転送する。前述のように、プログラム製品記憶装置は、フロッピィ・ディスクやＣＤ記憶装置を含めて、コンピュータ可読命令を有する複数の取り外し可能媒体のいずれとすることもできる。その他の適合するプログラム製品記憶装置としては、磁気テープや半導体メモリがある。このようにして、本発明による動作に必要な処理ステップを、プログラム製品上で実施することができる。あるいは、プログラム・ステップは、ネットワーク３０６を介して動作メモリ４１０に受け入れることもできる。後者の方法では、コンピュータは、周知の方法によってネットワーク通信が確立された後で、ネットワーク・インタフェース４２０を介してメイン・メモリ４０８にデータを受け入れる。この確立方法は詳述しなくても当業者ならわかるであろう。
【００３５】
スタック距離からのキャッシュ・ミス率の計算
図５は、本発明によりキャッシュ・ミス率曲線の計算を行うために、図３のコンピュータ処理システムによって実行される処理ステップを示す流れ図である。すなわち、本発明により構築されたキャッシュ・コントローラまたはその他のコンピュータは、図５に示す処理ステップを行って、各参照ごとにキャッシュ距離を計算せずにキャッシュ・ミス率を求める。
【００３６】
参照番号５０２が付された流れ図ボックスによって示された最初の処理ステップで、コンピュータが再使用距離を求める。前述のように、本発明は「再使用距離」を、同じページに対する２つの参照の間に行われる参照数と定義する。本発明によると、ボックス５０２の処理では、ストリーム内の各参照について、介在するページ参照数を求める。たとえば、図２で、ｒjにおけるＡに対する２番目の参照を受け取った時点での再使用距離は７ページである。各再使用距離の度数を累算することによって、再使用分布を生成する。図２の例では、Ａに対する２番目の参照を処理するときに、ｄｉｓｔａｎｃｅreuse＝７の度数カウントを１だけ増分する。流れ図ボックス５０４に示すように、ストリーム内のすべての参照を処理した後、すべてのｄｉｓｔａｎｃｅreuse値の度数の分布によって再使用分布が得られる。この再使用分布を求める処理について、以下に詳述する。
【００３７】
キャッシュ内のすべての処理済みデータ参照について再使用カウントを維持し、新しい参照を受け取ったときに再使用カウントを増分することによって、各新規着信（現行）参照の処理時に再使用距離を容易に求められることが明らかであろう。新規参照で受け取ったページがすでにキャッシュ内にある場合の再使用カウントが、その参照の再使用距離になる。システムによっては、ページ置換方策の向上のために、このようなカウントを自動的にとるものもあることが、当業者ならわかるであろう。そのようなシステムでは、本発明のこの態様を実施するのに必要なプログラミングの量は最小限になる。このようにして、ボックス５０４の処理によって生成された再使用距離分布は、横（ｘ）軸に沿ってプロットされた再使用距離を有し、縦（ｙ）軸に沿ってプロットされた度数を有することになる。
【００３８】
キャッシュ・ミス率を生成する次の処理ステップは、流れ図ボックス５０６によって示されており、反復ページ参照を計算に入れるために再使用シフトを計算する。前述のように、スタック距離は、再使用距離から反復ページ数を引いた値と定義される。最初の処理ステップ５０２で再使用距離が得られ、このステップ５０６で反復ページ数が得られる。この値は、前掲の数式９を使用して再使用距離から容易に求めることができる。このような処理は、キャッシュ・コントローラによるキャッシュ・ディレクトリ処理によって実施することができる。再使用シフトによって、再使用分布曲線が水平方向に移動する。
【００３９】
本発明は、各参照の度数を増して重複ページ数を求めるのではなく、確率的な方式で重複ページ・カウントを求めることを企図する。この計算によって、実際の統計値の妥当な近似値をより高い効率で得られることがわかっている。この近似値は、前掲の数式１１によって規定された数学的関係によって得られる。したがって、ボックス５０６の処理は、上述の処理ではなく数式１１の計算を含むことができ、参照毎にカウントを維持する。この近似計算は、キャッシュ・ミス率を求めるのに必要な重複ページ情報を得る、より効率的な手段である。
【００４０】
重複ページ・カウント処理の後、次のステップ５０８は前のステップ５０６によって求められた再使用シフトを引くことによって、再使用分布曲線をシフトすることである。このシフト・ステップでは、再使用分布処理を行った各キャッシュ・サイズについて、対応する再使用シフト量を求める。再使用シフトを求めて差し引いた後、次の処理ステップは、流れ図ボックス５０８が示すように、キャッシュ・ミス率曲線として調整された再使用分布曲線を生成することである。
【００４１】
図６は、図５の流れ図に示すステップによって行われた処理をグラフで表したものである。図６の最初の曲線６０２は、参照ストリームの処理によって求めることができる累積再使用分布を示す。この曲線は、図５のボックス５０２の処理によって生成される。参照ストリームはデータ参照のストリームであり、このような参照は、システム・トレースなどからのオフライン・データ、またはシステムの動作中に行われるリアルタイム参照のストリームとすることができることを理解されたい。図６の２番目の曲線６０４は、データ・ストリーム内の各参照の重複ページのカウントから計算された累積分布を示す。この曲線は、図５のボックス５０４の処理を表す。曲線６０４の矢印は、再使用分布において行う負のシフトを示す。負のシフトは分析する各キャッシュ・サイズについて行われることを理解されたい。すなわち、キャッシュ・サイズ分析の細分性のレベルで、重複ページ・シフトの計算が行われる。図６の最後の曲線６０６は、重複ページ・シフトが適用され、再使用分布における負のシフトが実施された後に計算された結果のキャッシュ・ミス率曲線を示す。この曲線は、図５のボックス５０８の処理に対応する。
【００４２】
したがって、ストリーム内の各参照についてスタック距離を求めずに、キャッシュ・ミス率が得られる。これにより、キャッシュ動作のシミュレーションの処理と実行の効率が向上する。このようにして、最適処理のためのキャッシュ・パラメータの調整が容易になる。
【００４３】
再使用分布の生成
図７は、再使用分布を生成する際に図３のコンピュータ処理システムによって実行される処理ステップを示す流れ図である。これは、キャッシュ・ミス率を求めるための基礎になる初期分布である。
【００４４】
ボックス７０２の流れ図で示された最初の処理ステップで、コンピュータ処理システムはキャッシュ項目に索引付けしてキャッシュ索引を作成する。キャッシュ内の各項目はそれに関連づけられた索引またはキャッシュ内の場所を有することになる。本発明により構築されたＬＲＵキャッシュの場合、当業者に周知のようにハッシュ・テーブルを使用してキャッシュ・ディレクトリを実施する。具体的には、ハッシュ・テーブル内の各項目には連係リストを指すポインタが入れられ、したがって、キャッシュ内の各ページに対応する連係リスト項目がある。連係リストは、ページが最後に参照された時点に従って順序づけられる。新しい参照を受け取ると、そのページ・アドレスをハッシュしてハッシュ・テーブルでそのページ・アドレスを見つける。ページがハッシュ・テーブルにある場合、ポインタに従って連係リスト項目を見つける。次にその項目をリストの先頭（最上位）に移動させる。ページがキャッシュ内にない場合、また、キャッシュがいっぱいの場合は、連係リスト内の最後の項目を調べて置き換えるページを選択する。このようにして、ＬＲＵキャッシュは一定数の操作を使用して参照を処理する。したがって、１サイズのキャッシュのキャッシュ・ミス率が求められる。一定範囲のサイズについてキャッシュ・ミス率曲線を求めるには、すべての参照のスタック距離を求めなければ成らず、きわめて高くつく可能性がある。
【００４５】
次に、各キャッシュ項目または索引場所について、処理システムは、最後の参照の参照番号を決定する。この処理を、流れ図ボックス７０４で示す。システムは、連続番号または操作間隔をデータ・ストリーム内の各参照のオカレンスと関連づける参照番号を維持する。ページが参照されるたびに、システムは参照番号カウントを増分し、その参照番号カウントを参照されたページに関連づける。
【００４６】
次に、システムは各新規参照またはデータ要求を順に処理する。処理する参照のストリームは、オフライン・モードで分析されるシステム・トレース・データとシステムで受け取られるときにリアル・タイムの実際の参照のストリームのいずれであってもよいことを理解されたい。すなわち、本発明は、キャッシュ・ミス率のリアルタイム計算を可能にし、それによって、キャッシュ・サイズやワークストリーム割振りを含むキャッシュ動作パラメータの動的調整を可能にする。図７の流れ図のボックス７０６に示す各新規現行参照を処理するには、システムは、要求されたデータ・ブロックがキャッシュ内にあるか（キャッシュ・ヒット）またはデータ・ブロックが見つからない（キャッシュ・ミス）かを判断する。この処理は、ボックス７０２に関して前述したようにハッシュ・テーブルを使用して実施することができる。
【００４７】
キャッシュ・ヒット／ミスの決定を図７の決定ボックス７０８に示す。参照がキャッシュ内に見つかった場合はキャッシュ・ヒットがあったことであり、決定ボックスの結果は肯定になり、ボックス７１０でシステムは、現行参照の再使用距離を、現行参照番号から直前の参照番号を引いた値に設定する。これは、前述の数式３の処理によって得られる結果と等しい。
【００４８】
ボックス７１０の再使用距離の設定では、参照カウントを維持し、そのカウントを、参照される各データ・ブロックまたはページに関連づけることに留意されたい。いずれかのデータ・ページが参照されるたびに、参照カウントが増分されて固有の識別番号が生成される。関連づけられた参照番号とページ番号は、ページが最後に参照された最後の時点を追跡するディレクトリまたはテーブルで維持することができる。その場合、再使用距離の決定は、単純に新しいカウントから古いカウントを引くだけである。たとえば、図２に、参照Ａ、Ｂ、Ｃ、Ｂ、Ｄ、Ｃ、Ｃ、Ａのストリームを示す。対応する参照カウント１、２、３、．．．、８の場合、ページＡが最初に参照されたとき、ページＡにはＲ＝１の参照カウントＲが関連づけられることは明らかであろう。ページＡが次に参照されたとき、参照カウントはＲ＝８である。システムは、ページＡが最後の参照カウントＲ＝１で参照されたことを呼び起こし、したがって（ボックス７１０）で再使用距離ＲがＲ＝８＝８−１＝７であると決定する。
【００４９】
参照カウンタは、たとえば３２ビット・カウンタで実施することができ、それによって、カウンタ値が折り返すまで、すなわちゼロから始まるまで、約１０億個の参照をカウントすることができる。折り返し点で、「古い」ページの参照カウントが現行ページの参照カウントよりも小さくなることは明らかであろう。好ましい実施形態は、ページが参照されてからの経過時間が長いほど、そのページがキャッシュ・ディレクトリ内にとどまっている可能性が低くなるという認識によって、折り返し状況を比較的単純な方式で処理する。したがって、古いページの参照カウントが現行ページの参照カウントよりも大きい場合、システムは、参照カウンタが１回折り返したものと想定し、現行参照カウンタの決定を調整する。参照カウンタのサイズは、この想定が本発明が実施されるシステムにとって有効になるように選定される。３２ビット・カウンタはほとんどのシステムにとって妥当なサイズであることがわかっている。
【００５０】
具体的には、折り返し調整は、折り返し状況が検出されるとシステムが最大カウント・サイズから古い参照カウント値を引き、次に新しい（現行）参照カウント値を加えるようにして実施することができる。たとえば、参照カウンタ値がＲ＝２５５で折り返す場合であって、図２の例の最初のＡページ参照に参照カウント値Ｒ＝２５４が関連づけられている場合、参照カウンタ値がＲ＝５のときにページＡの２番目の参照が行われる。システムがキャッシュ・ディレクトリでページＡを検索し、新しい参照カウント値が古い参照カウント値よりも小さいとわかった場合、システムは折り返しが行われたと想定する。それに応答して、システムは、古いものから新しいものを引くことによって、再使用距離を求めるのではなく、以下の数式１２によって再使用距離を求める。
【数１２】
Ｒ＝Ｍａｘcount−Ｏｌｄｅｒcount＋Ｃｕｒｒｅｎｔcount    （１２）
【００５１】
上式で、この例の場合、Ｒ＝２５６−２５４＋５＝７である。これは、ボックス７１０の処理のために示した第１の例で計算されたのと同じ値であることに留意されたい。
【００５２】
キャッシュ・ミスがあった場合、すなわちボックス７０８の結果が否定の場合、現行参照の再使用距離は所定の値、典型的にはキャッシュにおける参照について予測されるよりも大きい値に設定され、それによって、後でキャッシュ・ミスの数が比較的決定しやすくなる。この処理を流れ図のボックス７１２に示す。
【００５３】
キャッシュ・ヒットかキャッシュ・ミスかの決定が行われた後、処理がキャッシ・ディレクトリ項目を新しい参照番号に更新する処理に進む。すなわち、キャッシュ「スタック」の最上位が新規データによって更新される。この処理を流れ図ボックス７１４に示す。次に、新たに求められた再使用距離が再使用計数に加えられ、再使用分布関数の計算が維持される。この処理を流れ図のボックス７１６に示す。
【００５４】
最後に、コンピュータ・システムは処理する参照が他にないか調べる。前述のように、この追加の参照は、オフライン処理されるシステム・トレースでの他のデータ参照を指していても、データ参照の順次リアルタイム・ストリームにおけるデータ参照を指していてもよい。いずれも場合も、処理する追加の参照がある場合、ボックス７１８の結果が肯定になり、処理はボックス７０６に戻り次の（現行）参照を調べる。リアルタイム分析が終わったか、またはシステム・トレースの処理が終わったために、処理する参照がそれ以上ない場合、ボックス７１８での否定の処理結果により、他のシステム処理が続けられることが示される。
【００５５】
キャッシュ管理の実行
図８は、本発明によるキャッシュ管理タスクを実行するために図３のコンピュータ処理システムによって実行される処理ステップを示す流れ図である。前述のように、キャッシュ・ミス率を使用して、キャッシュ・サイズやデータベース間を流れる作業負荷ストリームの割振りなどのキャッシュ動作パラメータを決定する。本発明によると、キャッシュ・ミス率を求めるためのトレース・データのオフライン処理が効率化され、それによって、システム・データのリアルタイム処理がシステム動作中にキャッシュ・ミス率を決定し、それに応じてキャッシュ動作パラメータを調整することが十分に可能になる。このような機能を図８の流れ図に示す。
【００５６】
流れ図のボックス８０２に示すシステム操作の最初のステップは、初期キャッシュ動作パラメータを設定する初期ステップである。たとえば、履歴データまたはその他のデフォルトの割振り方法に基づいて、初期キャッシュ・サイズまたは割振りを行うことができる。次の処理ステップは、データ・ストリームの再使用分布を求めることである。流れ図のボックス８０４に示すこのようなキャッシュ・ミス率処理は、適切な分布データが決定されるように各新規参照について行われる。
【００５７】
再使用分布処理が完了した後、再使用シフトを計算してからでなければ、キャッシュ・ミス率を求めることができない。スタック再使用統計からキャッシュ・ミス率を求める上述の技法は十分に効率的であるため、参照のデーター・ストリームを受け取って、リアルタイムで処理してキャッシュ・ミス率を求めることができるが、リアルタイムよりも幾分遅くシステムを動作させることが望ましい場合もある。したがって、図８の決定ボックス８０６に、各参照に関する再使用分布を累算する決定を示す。図５に関して前述したように再使用分布を定期的に統計的に解釈し、キャッシュ・ミス率曲線を生成する。このようにして、動的キャッシュ動作パラメータ調整を、累算データに基づいて定期的な間隔で、または参照サイズやその他の効率測定基準などの所定のデータ事象に応答して行うことができる。しかし、通常は、再使用分布および近似再使用シフトは、システムが動作しているときにリアルタイムで絶えず計算する。
【００５８】
トリガ事象またはデフォルトにより、再使用シフトを計算する時点が示された場合、決定ボックス８０６での結果が肯定の場合の処理は、再使用シフトを計算することと、キャッシュ・ミス率を求めることである。この処理は、流れ図のボックス８０８に示されている。再使用シフトを計算するか否かを問わず、システムはキャッシュ動作パラメータの動的調整を可能にする。すなわち、キャッシュ・パラメータは、ミス率が所定のレベルに達した場合にのみ調整することが望ましい場合がある。さらに、システム動作特性は、キャッシュ調整決定を行うのに現行計算再使用シフトとキャッシュ・ミス率が必要がないようなものでなければならない。したがって、再使用シフトを計算しない場合、すなわち決定ボックス８０６の結果が否定の場合、再使用シフトとキャッシュ・ミス率が計算された後、システムは決定ボックス８１０でキャッシュ・パラメータの調整に関する決定を行う。したがって、この決定では、キャッシュ・ミス率がトリガ・レベルであるかどうかを調べるか、計算時刻または作業負荷量の決定を行う。
【００５９】
キャッシュ調整を行う必要がある場合、すなわち決定ボックス８１０で肯定の結果になった場合、システムはキャッシュ動作パラメータをそれに応じて調整する。この調整処理を流れ図のボックス８１２に示す。前述のように、これには、特定のデータベースを必要とするデータ・ストリームを異なるキャッシュ区分に割り振るか、またはキャッシュ・サイズに割り振られた記憶資源の調整を行う。このような処理８１２は、受け取った参照ストリームに応答してリアルタイムで行うことができる。調整が不要な場合、すなわちボックス８１０で否定の結果の場合、一般的なシステム動作が続けられる。
【００６０】
結果
ＴＰＣ−ＣおよびＴＰＣ−Ｄと呼ばれる業界標準データベース・ベンチマークに類似した作業負荷からとられたトレースを使用して、シミュレーションを行った。本発明により構築されたシステムを使用したこのシミュレーションの結果を図９に示す。１２８ＭＢの固定データベース・バッファ・プール・サイズを仮定した。キャッシュには「ウォームアップ」動作期間があった。図９に、４Ｋおよび１６Ｍの参照の推定間隔の結果を示す。すなわち、キャッシュ内で参照されるデータ・ブロックのサイズは、４Ｋまたは１６Ｍのブロックである。キャッシュが所定のウォームアップ期間後にいっぱいになったところでのみ、データ・ポイントをプロットしている。本発明による技法は、実際のＬＲＵスタックをきわめてい近く近似計算し、実際に、ＴＰＣ−Ｃベンチマークに類似した作業負荷の場合、この曲線は実質的に区別できないことがわかる。
【００６１】
ＴＰＣ−Ｄプロットの右端方向の不一致は、大きいキャッシュ・サイズで良好な近似検査を可能にするには参照数が不十分であった結果であることがわかった。この技法は推定間隔または細分性の影響を受けないように思われることに留意されたい。ＴＰＣ−ＣおよびＴＰＣ−Ｄデータに関して得られた良好な結果は、様々な大企業のピーク実働データベース作業負荷から得られたテスト・データでも再現された。一般に、再使用シフトを行う前に必要な観測数は、少なくとも期待再使用距離と同等でなければならないことがわかった。さらに、シミュレーションを開始する前にキャッシュをいっぱいにするために、トレース作業負荷をしばらく実行してウォーム・スタートと呼ばれるものを行った。
【００６２】
以上、本発明を理解できるように、本発明について現在のところ好ましい実施形態を示して説明した。しかし、本明細書に特に記載していないが、本発明を適用することができるキャッシュ管理システムの構成は多数ある。したがって、本発明は、本明細書に記載の特定の実施形態に限定されると見なすべきではなく、本発明はキャッシュ管理システム一般に対して広く適用可能であるものと理解すべきである。したがって、特許請求の範囲内のあらゆる変更、変形、または同等の構成および実施態様が、本発明の範囲に含まれるとみなすべきである。
【図面の簡単な説明】
【図１】キャッシュ・ヒットおよびミスを生成するデータ参照のシーケンスを示す、キャッシュのスタック図である。
【図２】本発明により定義されたキャッシュ再使用距離を示す、キャッシュ内の参照のストリームを示すスタック図である。
【図３】本発明により構成されたキャッシュ管理システムを示すブロック図である。
【図４】図３に図示するキャッシュ制御コンピュータを示す詳細ブロック図である。
【図５】本発明によるキャッシュ・ミス率曲線の導出を実施するために、図３のコンピュータ処理システムによって実行される処理ステップを示す流れ図である。
【図６】図５のプログラム・ステップによって実行されるデータ処理を示す図である。
【図７】再使用分布を生成する際に、図３のコンピュータ処理システムよって実行される処理ステップを示す流れ図である。
【図８】本発明によるキャッシュ管理タスクを行うために、図３のコンピュータ処理システムによって実行される処理ステップを示す流れ図である。
【図９】本発明により構成されたシステムのトレース方式シミュレーションの結果を示すグラフである。
【符号の説明】
３００  キャッシュ管理システム
３０２  キャッシュ記憶装置
３０４  キャッシュ・コントローラ
３０５  キャッシュ・メモリ
３０６  ネットワーク
３１０  ユーザ・コンピュータ
３１２  ユーザ・コンピュータ
３１４  ユーザ・コンピュータ
４０２  コンピュータ
４０４  中央処理装置
４０６  メイン・メモリ
４０８  プログラム・メモリ
４１０  データ・メモリ
４１６  プログラム製品読取装置
４１８  プログラム製品記憶装置
４１４  直接アクセス記憶装置
４２０  ネットワーク・インタフェース
【図１】
0003657170.tif 000010
【図２】
0003657170.tif 000011
【図３】
0003657170.tif 000012
【図４】
0003657170.tif 000013
【図５】
0003657170.tif 000014
【図６】
0003657170.tif 000015
【図７】
0003657170.tif 000016
【図８】
0003657170.tif 000017
【図９】
0003657170.tif 000018