(57)【特許請求の範囲】
【請求項１】
アプリケーションによって要求される次のデータブロックを予測する方法であって、
（ａ）前記アプリケーションの今回のデータブロック要求を、状態空間に記憶するステップと、
（ｂ）前記アプリケーションの前回のデータブロック要求およびストライドを、検出されたストライド・パターンのそれぞれについて記憶することのできるパターン・キャッシュを調べ、該前回のデータブロック要求に該ストライドを加算した値が前記今回のデータブロック要求に等しいストライド・パターンが存在するかどうかを判断するステップと、
（ｃ）前記ステップ（ｂ）において前記ストライド・パターンが存在しなければ、
（ｃ１）前記状態空間を調べ、前記今回のデータブロック要求と共に新たなストライド・パターンを形成する２つのデータブロック要求が存在するかどうかを判断し、
（ｃ２）前記新たなストライド・パターンを形成する２つのデータブロック要求が前記状態空間に存在するならば、該新たなストライド・パターンのストライドおよび前記今回のデータブロック要求を、前記パターン・キャッシュに記憶し、
（ｃ３）前記今回のデータブロック要求に、該新たなストライド・パターンについて前記パターン・キャッシュに記憶された前記ストライドを加算して、次のデータブロックを予測するステップと、
（ｄ）前記ステップ（ｂ）において前記ストライド・パターンが存在するならば、
（ｄ１）該ストライド・パターンについて前記パターン・キャッシュに記憶されている前回のデータブロック要求を、前記今回のデータブロック要求に更新し、
（ｄ２）前記今回のデータブロック要求に、該ストライド・パターンについて前記パターン・キャッシュに記憶されているストライドを加算して、次のデータブロックを予測するステップと、
を含む方法。
【請求項２】
前記ストライドが１である順次パターンについて、前記ステップ（ａ）から（ｄ）を実行することを含む、請求項１に記載の方法。
【請求項３】
前記ステップ（ｃ１）は、さらに、
（１）前記状態空間における前記アプリケーションの前記今回のデータブロック要求に、第１の目印を設定するステップと、
（２）前記状態空間において、前記アプリケーションの最も古いデータブロック要求に、第２の目印を初期的に設定するステップと、
（３）前記状態空間において、前記アプリケーションの次に最も古いデータブロック要求に、第３の目印を初期的に設定するステップと、
（４）前記第１の目印により示されるデータブロック要求および前記第３の目印により示されるデータブロック要求の間の第１の差を、前記第３の目印により示されるデータブロック要求および前記第２の目印により示されるデータブロック要求の間の第２の差と比較して、該第１の差が該第２の差に等しいかどうか判断するステップと、
（５）前記第２および第３の目印の少なくとも１つを、前記状態空間の少なくとも１つの他の位置に動かすステップと、
（６）前記状態空間全体について、前記ステップ（４）および前記ステップ（５）を繰り返すステップと、を含み、
前記ステップ（４）において前記第１の差が前記第２の差に等しいと判断されたとき、前記第２の目印および第３の目印により示されるデータブロック要求を、前記新たなストライド・パターンを形成する２つのデータブロックと判断する、請求項１に記載の方法。
【請求項４】
前記新たなストライド・パターンが見いだされたとき、前記ステップ（ｃ１）を停止させるステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記パターン・キャッシュに記憶されるストライド・パターンにおける第１のデータブロック要求に関する情報をトリガー配列に格納して、該第１のデータブロック要求を用いた新たなパターンが形成されないようにする、請求項１に記載の方法。
【請求項６】
前記ステップ（ｄ）は、さらに、
前記次のデータブロックの非同期先読みが前に発行されたかどうかを判断するステップと、
前記ストライド・パターンにおける第１のデータブロック要求に関する情報を格納するよう前記トリガー配列を更新するステップと、
前記次のデータブロックの非同期先読みが前に発行されていなければ、該次のデータブロックの非同期先読みを発行するステップと、
を含む、請求項５に記載の方法。
【請求項７】
前記ステップ（ｃ２）において、前記新たなストライド・パターンを形成する２つのデータブロック要求が前記状態空間に存在するならば、さらに、
検出されたパターンの数を増やすように、有効なキャッシュカウントを更新するステップと、
前記次のデータブロックの非同期先読みが前に発行されたかどうかを判断するステップと、
前記新たなストライド・パターンにおける第１のデータブロック要求に関する情報を格納するよう、前記トリガー配列を更新するステップと、
前記次のデータブロックの非同期先読みが前に発行されていなければ、該次のデータブロックの非同期先読みを発行するステップと、
を含む、請求項５に記載の方法。
【請求項８】
前記パターン・キャッシュは、さらに、該キャッシュに記憶されるストライド・パターンのそれぞれについて、前記ステップ（ｂ）においてストライド・パターンが存在すると判断された回数を示す強さの値を有しており、
前記強さの値がオペレーティングシステムによって使用されることにより、該パターン・キャッシュに記憶されたパターンに基づいて発行される非同期先読みの量を算出することできるようにする、請求項１に記載の方法。
【請求項９】
前記ストライド・パターンは、データブロック要求が均一でない時間間隔で隔てられたストライド・パターン、および、混在する複数のストライド・パターンのそれぞれを含むことができる、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
このアプリケーションは、一般にコンピュータの先読み操作に関し、より具体的には、読み出しパターンを認識して、先読み（ｒｅａｄ  ａｈｅａｄ）操作が、マルチスレッド化されたアプリケーションによるアクセスと同様に、順次アクセスおよび非順次アクセスの両方に使用されることを可能にするメカニズムに関する。
【０００２】
【従来の技術】
近頃のコンピュータでは、オペレーティングシステムは、近い未来に読み出されるファイルの次のセクション（区画）を予測しようとする。この予測は、アプリケーションがその動作を要求する前に行われる。予測されたファイルのセクションが、ディスクからコンピュータのメモリにもって来られ、それゆえ先読みとして知られている。先読みは、ディスクからデータブロックを受けとるのを待つのに費やす時間を軽減するために開発された。例えば、同期読み出しを発行するのにＸ秒かかり、データがディスクから抽出されるまで待つ場合には、データがディスクから抽出されるたびに、Ｘ秒が処理時間に加えられる。従って、どのデータブロックがアプリケーションによって抽出されるかを予測して、予測されたデータブロックの非同期読出し要求を発行することにより、アプリケーションは、既存のデータを処理し続けることができる。また、アプリケーションがファイルのその次のブロックを要求する時、その次のブロックがすでにメモリにあることを見つける傾向があり、操作をより速く完了する。
【０００３】
しかし、従来技術の予測メカニズムは、前向きのシーケンスに限られる。すなわち、次のブロックが、読み出された最後のブロックより１ブロック大きいかどうかを予測する（例えば、ファイルブロック１、２、３、４）。こうして、予測された場合には、従来技術のメカニズムは、オペレーティングシステムに現ブロックの読み出しを発行させ、現ブロックに１を加えたブロックの非同期読み出しを発行させる。従来技術の予測メカニズムは、最後のブロックに１を加えたものが現ブロックに等しければ、次の順次ブロック、すなわち現ブロックに１を加えたものの非同期読み出しを発行する、というものである。ＯＳ、すなわちオペレーティングシステムは、通常ｖノード（アプリケーションが読んでいるファイルに関連する）と呼ばれる他のデータ構造を保持する。ｖノードは、ファイルを追跡するのにＯＳによって使用される。ｖノードは、最後のブロック読み出しだけでなく、ファイルを構成するブロックのリスト、およびそれらのそれぞれのディスク上の物理的位置を維持する。こうして、予測メカニズムは、ファイルのｖノードを調べ、現在の要求が最後のブロック読出しに１を加えたものに等しいかどうか判断する。もし等しければ、現在の要求の読み出しおよび次のブロックの非同期読出しを発行し、予測された要求を示すよう、ｖノードの最後のブロック読出しのエントリを更新する。例えば、現在の要求がブロック２であり、前の要求がブロック１であるならば、ブロック２の読み出しが発行され、ブロック３の非同期読み出しが発行される。ｖノードの最後のブロック読出しのエントリは、ブロック３に変更される。現在の要求が前のものに１加えたものに等しくない場合には、現在の要求の読出しだけが発行され、いかなる非同期読み出しも発行されない。ｖノードの最後のブロックエントリは、現在の要求に変更される。例えば、現在の要求がブロック５であり、前の要求がブロック１であるならば、ブロック５の読み出しが発行され、ｖノードの最後のブロック読出しのエントリは、ブロック５に変更される。しかし、このアプローチにはいくつかの問題がある。それは、主に予測メカニズムが、順次ブロックアクセス（たとえば、ファイルブロック１、２、３、４）を行うアプリケーションを検出できるにすぎないからである。
【０００４】
予測メカニズムが、ファイルを後方に読むアプリケーション（例えば、ファイルブロック６、５、４、３）を検出できないということに注意すべきである。これは、現在の要求が、前の読出しブロックに１を加えるのか、それとも１を引くのかを単に調べることにより克服されてきた。
【０００５】
また、メカニズムが、またいで（ｓｔｒｉｄｅ、以下「ストライド」という）アクセスを行うアプリケーション（例えば、ファイルブロック１、３、５、７など）を検出できない点に注意すべきである。この問題は、ｖノードを修正して、最後および最後から２番目の読出しを保持することにより克服されてきた。こうして、予測メカニズムは、現在の読み出し要求と最後のブロック読み出しとの隔たりが、最後のブロック読み出しと最後から２番目のブロック読み出しとの隔たりと同じであるかどうか確認する。もし同じであるならば、アプリケーションは、一定のストライドで読み出すよう予測され、次のブロックの非同期読出し（これは、現ブロックから１ストライドである）が発行される。例えば、最後のブロックがブロック３であり、最後から２番目のブロックがブロック１であり、現ブロックはブロック５であるならば、メカニズムはブロック５をブロック３と比較し、ストライドが２（これは、ブロック１からブロック３へのストライドに等しい）と判断する。その後、ＯＳはブロック５の読み出しおよびブロック７の非同期読出しを発行する。ｖノードの最後および最後から２番目のブロックは、ブロック７および５にそれぞれ更新される。ファイルをストライドで後方に読むアプリケーション（たとえば、ファイルブロック１７、１５、１３、１１）を検出するには、負のストライドのメカニズムが使用される。
【０００６】
さらに、複数のアプリケーションまたは１つのアプリケーションの複数のスレッドが、同じ時に同じファイルを読む場合には、従来技術のメカニズムは、読み出されているブロックの順次またはストライドのいずれをも検出できない。例えば、従来技術のメカニズムは、１、１００、２、１０１の順にファイルブロックを検出できない（ここで、ブロック１および２は、アプリケーションＡ（または、アプリケーションＣのスレッドＡ）により要求され、ブロック１００および１０１はアプリケーションＢ（または、アプリケーションＣのスレッドＢ）により要求された）。これは、ｖノード（複数の読み出しを追跡する）がファイルに関連し、アプリケーションまたはスレッドに関連しないからである。このように、アプリケーションまたは代わりのスレッドのために、ｖノードのエントリのパターンが混乱させられる。例えば、最後の読出しが１００で、最後から２番目の読み出しが１と仮定する。現在の読み出し２が、最後および最後から２番目のものと比較されるとき、２は１００の後に順次ではなく、２−１００は−９８のストライドに等しく、このストライドは１００−１からの＋９９のストライドに等しくない。このように、いかなるパターンも検出されず、いかなる先読みも発行されない。これは、それらのアプリケーションまたはスレッドの性能に否定的な影響を与える。いかなる予測もなされないとき、オペレーティングシステムはメモリにデータを速く送ることができず、それぞれのアプリケーションまたはアプリケーションのスレッドは、ディスク操作が完了するのを待つのにそれぞれの読み出しで立ち往生する。この問題は、産業および消費者が、マルチプロセスまたはマルチスレッドを使用することのできるアプリケーションを備えるシステムを使用し始めるにつれ、より顕著になってきた。
【０００７】
以下は、マルチスレッド化されたシステムの例であり、従来技術の予測メカニズムを使用して直面する問題である。システムは、３つのレベル、高（Ｈ）、中（Ｍ）および低（Ｌ）で垂直に走査して、ファイルにデータを送り込むレーダ局である。局が走査してリセットし、走査してリセットし、．．．等を行うにつれ、局は、垂直に走査することによって、Ｈ−Ｍ−Ｌ−Ｈ−Ｍ−Ｌ−Ｈ−Ｍ−Ｌ−Ｈ−Ｍ−Ｌのデータストリームの形で大気の断面を生成する。アプリケーションが任意の所与のレベル（たとえば、高レベルまたは低レベル）のデータを処理したい、と仮定する。よって、アプリケーションは、Ｈ−Ｈ−Ｈ−ＨまたはＬ−Ｌ−Ｌ−Ｌのようにデータを読み出したいと欲する。レコード間の距離が一定なので、アプリケーションは従来技術のストライド・リーダ（ｓｔｒｉｄｅ  ｒｅａｄｅｒ）を要求する。しかし、アプリケーションがマルチスレッド化されている場合には、Ｈ（高）を処理するのに１つのスレッドを開始し、Ｍを処理するのに２番目のスレッドに開始し、Ｌを処理するのに３番目のスレッドを開始するのはありそうなことである。それぞれのスレッドが、同じファイルから同時に読み出しており、それぞれのスレッドがストライド・リーダである。それぞれのスレッドがファイルから読み出すので、ｖノードの最後および最後から２番目の値は、それに応じてリセットされ、したがって従来技術のストライド予測メカニズムは、読み出しパターンを決して認識しない。さらに、従来技術の順次リーダは、Ｈが、ＭまたはＬとは異なる処理時間を持つことがあるので、Ｈ−Ｍ−Ｌ−Ｈ−Ｍ−Ｌパターンを拾わず、よって読み出されるパターンはＨ−Ｍ−Ｌ−Ｈ−Ｍ−Ｌではなく、むしろＨ−Ｍ−Ｌ−Ｌ−Ｍ−Ｈ−Ｍ−Ｍ−Ｌ等である。このように、いかなる予測も起こりえず、それぞれのデータブロックは、直接ディスクから読み出されている。これはシステムを遅くすることがあり、１つのスレッドまたはプロセスが、マルチスレッドまたはプロセスを持つよりも速くデータを処理することとなる。
【０００８】
ファイルレベルからプロセスまたはスレッドレベルに予測メカニズムを移すことが、上記述べた問題点のいくつかを克服することができるが、非常に劣化した性能をもたらす新しい問題を招く。この例では、アプリケーションの３つのスレッドがあり、１つはＨを読み出し、１つはＭを読み出し、１つはＬを読み出す。それぞれのスレッドがＣＰＵを介して時間を切り換えられるので、それらのアクセス要求は、それらがそれぞれストライド・リーダであることを示す。このように、ＯＳは、一連のＨの要求をディスクに発行し、その後おそらく一連のＭおよびＬを発行する。この方法でディスクからの情報を読み出すのは、ディスクが、Ｈデータを読むためにＭおよびＬデータを飛ばす（ｓｋｉｐ）ので、多数のシークを招く。これは、ＭおよびＬデータについても同様である。さらに、ＯＳは、それが実際に順次リーダであることをファイルレベルで認識していない（順次リーダは、ファイルレベルの順次予測メカニズムにより検出され、シークなしで多くの先読みを実行する）。さらに、ハードディスク自体が順次先読みを行うキャッシュを持つので、より速い抽出のため、読み出しの際にブロック１、ブロック２および３がディスクキャッシにロードされる。こうして、順次読み出しを発行せずに代わりにストライド読み出しを発行することにより、この機能がディスエーブルされ、ディスクドライブの性能が落ちる。予測メカニズムをアプリケーションレベルに移すことによって、より多くのシークのコストがかかり、性能が下がる。
【０００９】
【発明が解決しようとする課題】
上記の問題は、ファイルがメモリより大きいときに特に関連するので、ファイルの一部が、ハードディスクまたはＣＤ−ＲＯＭのような他の大容量記憶媒体上に常駐しなければならない。したがって、マルチプロセスまたはマルチスレッドのシステム（ランダムアクセスと見えるパターンを作る）により発行される複雑な読み出しパターンで隠された前方ストライド、後方ストライド、前方順次および後方順次のパターンを認識することができる予測メカニズムが、従来技術に対して必要である。このようなシステムは、オペレーティングシステムが、パス（ｐａｔｈ）上のデータを速くさせることを可能にする。
【００１０】
【課題を解決するための手段】
これらおよび他の目的、特徴および技術上の利点が、ファイルアクセスの時間順の状態空間を構成して、予測についての規則に従うファイルアクセスを探しながら状態空間を調べるシステムおよび方法によって達成される。第１の規則は、予測された前のストライドアクセスに等しい距離だけ離れたブロックが、後の時間にあるかどうか判断する。このように、本発明のメカニズムは、予測をキャッシュに入れて、連続操作についてキャッシュを調べ、連続するパターンをより速く検出する。第２の規則は、現在評価されている２つのブロックに等しい距離だけ離れたブロックが、後の時間にあるかどうか判断する。第３の規則は、状態空間で調べられている現ブロックより１大きい（または１小さい）ブロックが、後の時間にあるかどうか判断する。第１の規則は、現在の要求ブロックが、既存のパターンの論理的な連続であるかどうか確認する。第２の規則はストライド・リーダを識別し、第３の規則は順次リーダを識別する。
【００１１】
例えば、アプリケーションが、ファイルブロック１、２の要求または読み出しの発行をすると仮定する。これは、順次アクセス動作でファイルを読んでいるアプリケーションのアクセス動作である。メカニズムは、エントリが第３の規則を満足すると判断し、ブロック３が次に読まれることを予測し、ブロック３の先読みを発行する。メカニズムは、パターンを規定するキャッシュ・エントリを形成する。アプリケーションが、次にブロック３を要求すると仮定する。これは、順次アクセス動作でファイルを読み出し続けているアプリケーションのアクセス動作である。メカニズムは、この新規のエントリが第１の規則を満たすことを検出し、ブロック４が次に読み出されると予測し、ブロック４の先読みを発行する。メカニズムは、新規の要求についてパターン・キャッシュを更新する。
【００１２】
他の例は、アプリケーションがファイルブロック９、７、５を要求することがある場合である。これは、ストライド・アクセス動作でファイルを読んでいるアプリケーションのアクセス動作である。メカニズムは、エントリが第２の規則を満足することを検出し、ブロック３の先読みを発行する。メカニズムは、パターンを規定するキャッシュ・エントリを形成する。
【００１３】
さらなる例は、アプリケーションが、マルチスレッド化されている場合またはマルチプロセスを持つシステム上で操作される場合である。ここで、読出し要求のシーケンスは、１、９、１００、２、１０、１０１、３、１１、１０２であり、あるプロセスはブロック１、９、１００を読み、他のプロセスはブロック２、１０、１０１を読み、さらに他のプロセスは、ブロック３、１１、１０２を読む。これが、前述したレーダの例をたどる点に注意すべきである。メカニズムは、ブロック１、２、３が第３の規則を満たすと判断し、ブロック４の先読みを発行する。またメカニズムは、ブロック９、１０、１１が第３の規則を満たすと判断し、ブロック１２の先読みを発行する。さらにメカニズムは、ブロック１００、１０１、１０２が第３の規則を満たすと判断し、ブロック１０３の先読みを発行する。それぞれのプロセスが効果的に他のプロセスと組み合わされて、３つの順次リーダのパターンを作るが、それぞれのプロセスが実際にはストライド・リーダであることに注意すべきである。これは、アプリケーションが、列の順番で書かれたマトリクスを、行の順番で読んでいるときに起こり、それぞれのプロセスは、特定の列を処理することに対して責任を負う。したがって、パターンを状態空間に形成することを可能にすることによって、協力的なファイルアクセスのパターンを検出することが可能である。
【００１４】
本発明のメカニズムの技術的特徴は、トリガー配列であり、これは予測の再発行を防ぐのに使用される。メカニズムが予測を行うときはいつでも、メカニズムは、傾向すなわちパターンの第１の要素に、「予測に使用された」として印をつける。これが後に使用され、いかなる再発行も行われないことを保証する。
【００１５】
本発明のメカニズムの他の技術的特徴は、予測の強さである。既存のパターンの連続が検出されるたびに、強さがインクリメント（ｉｎｃｒｅｍｅｎｔ）される。この情報が集められるので、いかに積極的に先読みを発行するかについてオペレーティングシステムに知らせるのに、これを使用することができる。
【００１６】
本発明のメカニズムのさらなる技術的特徴は、有効なキャッシュ・エントリの数が保持されることである。これは、連続パターンを検出しようとする時に検索されるべきキャッシュ・エントリの数を減らすのに使用される。
【００１７】
本発明のメカニズムのさらなる技術的特徴は、状態空間がいっぱいになるとき、メカニズムが、状態空間の内容の論理シフトおよびトリガー・インジケータの論理シフトを行うことによって、状態空間を古くさせる（ａｇｅ）ことである。
【００１８】
本発明のメカニズムのさらなる技術的特徴は、メカニズムを既存のオペレーティングシステムと組み合わせることができ、または新規のオペレーティングシステムに書き込まれることができるという点で、メカニズムがモジュール式であり、かつ移植可能なことである。メカニズムは、ストライドおよび順次アクセスパターンを見せる大部分のアプリケーションと共に動く。
【００１９】
前述したことは、本発明の特徴および技術の利点を広く概説したものであり、以下に続く本発明の詳細な説明でより良く理解することができる。本発明のさらなる特徴および利点は、この後に記述されており、本発明の特許請求の範囲の主題を形成する。当該技術分野の当業者には、開示される概念および特定の実施形態を、本発明の同じ目的を実行する他の構造を改良または設計するのに基本として使用することができるということが、認識されるであろう。当該技術分野の当業者には、このような等価な構造が、特許請求の範囲に記述される本発明の精神および範囲から離れることがないということが理解されるであろう。
【００２０】
【発明の実施の形態】
図１は、本発明の予測メカニズム１０の流れ図を示す。それぞれの新規の要求１１が到着するとき、状態空間が更新される（ステップ１２）。状態空間２０は、配列またはスタックであり、ハードディスクまたは他の記憶媒体上に格納されるデータブロックについてアプリケーションにより発行される読み出し要求のリストを保持するのに使用される。図２（Ａ）は、５つのスロットを備える状態空間を示す。示されるように、これは、要求１、２、３、５、７、９および４が発行されるにつれ時間とともに満たされる。状態空間を更新（ステップ１２）した後、パターン・キャッシュが分析され（ステップ１３）、新規の要求が何らかの確立されたパターンに合うかどうか判断する。図２（Ｂ）は、５つのスロットを備えるパターン・キャッシュ３０を示し、要求ｌ、２、３、５、７、９および４が発行されるにつれ、時間とともにその内容が変わる。パターン・キャッシュ３０は、それぞれの検出されたパターンについての情報を格納する。格納される３つの値は、第１のブロックの状態空間の索引、第２の要求ブロックおよびパターンのストライドである。メカニズム１０は、新規の要求が前に検出されたパターンの一部であると判断した場合には、パターン・キャッシュのヒット（ｈｉｔ）が生じ、キャッシュが更新され（ステップ１４）、第１のブロックの索引および第２のブロックのエントリをそのパターンについて変更する。次に、トリガーが更新され（ステップ１５）、予測されたブロックの先読みが発行される。この予測されたブロックは、新規の要求ブロックに認識されたパターンのストライドを加えたものである。
【００２１】
トリガーすなわちトリガー配列は、状態空間に対応した配列であり、同じブロックから複数のパターンが形成されるのを防ぐフラグを保持するのに使用される。トリガー配列は、それぞれのパターンの第１のブロックの状態空間の索引を格納する。パターンのそれぞれの連続する要求が受け取られる時、または予測されたブロックの先読みが発行されるとき、第１のブロック（従って、索引）が変わり、更新されるという点に注意すべきである。例えば、要求シーケンスが１、２、３、５、７であれば、これは２つのパターン、つまり第１の１、２、３および第２の１、３、５、７を含む。前のシーケンス・パターンは、１および２から識別され、ブロック３の先読みが発行される。このように、ブロック３がシーケンス・パターンの連続でも、このシーケンス・パターンの第１のブロックはブロック２であり、従ってストライド・パターンが３、５、７から識別される。しかし、要求シーケンスが、１、２、３、４、５、７である場合には、ブロック４が受け取られるとき、ブロック３がシーケンス・パターンの第１のブロックになり、よってブロック３は、３、５、７のパターンを判断するのに使用されることができない。再び、パターンの第１のブロックの索引だけが、トリガー配列においてフラグがたてられることに注意すべきである。また、このことは、同じ要求シーケンスの繰り返しに基づいて先読みの再発行することを防ぐ。トリガー配列は更新され、それぞれのパターンの現在の第１のブロックの索引を保持する。トリガーを更新して調査した後に、先読みが発行され（ステップ１６）、メカニズムはこの要求で起動された操作を終える。
【００２２】
先読みが発行される前に、ｉｎ＿ｓｔａｔｅ＿ｓｐａｃｅと呼ばれるさらなる機能が状態空間を調査し、すでに状態空間にあるブロックについて先読みが発行されるのを防ぐのは任意である。例えば、図２（Ａ）に示されるように、ブロック４の要求が受け取られるとき、それが既存の前方シーケンス・パターンの一部であるとわかり、次のブロックの先読み（ここでは、５）が発行される。しかし、ｉｎ＿ｓｔａｔｅ＿ｓｐａｃｅは、ブロック５がすでに状態空間のスロット２にあり、よって読出しはすでに発行され、先読みが発行される必要はないと判断する。このように、先読みが発行されるようとするたびに状態空間が調査され、ブロックが見つからない場合に、先読みが発行される。
【００２３】
メカニズム１０が、新規の要求が前に検出されたパターンの一部でないと判断する場合には、パターン・キャッシュのミス（ｍｉｓｓ）が生じ、状態空間が検索され（ステップ１７）、状態空間の他のエントリとともに新規の要求がパターンを形成するかどうか判断する。いかなるパターンも見つからない、すなわちパターン検索がミスした（果たされなかった）場合には、メカニズムはこの要求を終了する。パターンが見つかった場合、すなわちパターン検索がヒットした場合には、キャッシュにおける既存のパターンが更新される（ステップ１８）。また、キャッシュのエントリ数を常に把握している有効なキャッシュカウントが更新される（ステップ１８）。新規のキャッシュ・エントリが新しいパターンについて作られ（ステップ１９）、これはキャッシュに挿入される。キャッシュ・エントリは、パターンの第１のブロックの状態空間の索引、パターンの第２のブロックおよびパターンのストライドを詳述する。次に、トリガーが更新され（ステップ１５）、予測されたブロックの先読みが発行され（これは、新規の要求ブロックにパターンのストライドを加えたものである）、メカニズムはこの要求を終える。
【００２４】
図２（Ａ）および図２（Ｂ）は、一連の要求がアプリケーションから送られる時の状態空間およびパターン・キャッシュの推移を示す。第１の要求はブロック１である。状態空間２０は、状態空間のスロット５にブロック１を置くことによって更新される。キャッシュが分析され、ブロック１が前のパターンの連続でないことがわかる。状態空間が検索され、ブロック１が他のエントリとともにパターンを形成するかどうか判断する。他のいかなるエントリも無いので、いかなるパターンも見つからない。よって、メカニズムはこの要求を終え、ブロック１の読出し要求が発行される。
【００２５】
次のブロック要求であるブロック２が受け取られる。状態空間２０は、状態空間のスロット５にブロック２を置くことによって更新され、ブロック１をスロット４に動かす。キャッシュが分析され、ブロック２が前のパターンの連続でないことがわかる。状態空間が検索され、ブロック２がブロック１とともにパターン（具体的には、前方シーケンス）を形成することが判断される。キャッシュが他のエントリをまったく含まないので、更新されるべき他のいかなるキャッシュ・エントリも無い。メカニズムは、新規のパターン・キャッシュのエントリを形成する。このエントリは、このパターンを形成する第１のブロックの状態空間の索引すなわちスロット４、パターンの第２のブロックすなわちブロック２、およびパターンのストライドすなわち１を含む。こうして、エントリ４、２、１がキャッシュのスロット０に挿入される。トリガー配列が更新され、ブロック１がパターンを形成するのに使用されたこと、およびブロック３の非同期要求が発行されたことを示す。その後、メカニズムはブロック３の非同期要求を発行し、ブロック２の要求によって起動された操作を終える。要求されたブロックの読出し要求がＯＳによって発行され、本発明のメカニズムが、識別されたパターンまたは既存のパターンに対応する予測されたブロックの先読みを発行し、またはＯＳにそう命令して先読みを発行させることができるという点に注意すべきである。
【００２６】
その後、アプリケーションはブロック３を要求する。状態空間は、スロット５に３を置くことにより更新され、２および１をスロット４および３にそれぞれ動かす。キャッシュが分析され、メカニズムは、３が、前に規定されたパターンの連続であると判断する。メカニズムは、ブロック３が第２のブロック（ここでは２）に１のストライドを加えたものに等しいということに気づくことにより、この判断を行う。メカニズムはパターンの最後の２つを維持するにすぎないので、キャッシュ・エントリが更新され、第１のブロックの索引が、ブロック２の４であるようにする。第２のブロックは３であり、ストライドは１のままである。トリガーが更新され、ブロック４の非同期読み出しが発行されたことを示す。また、トリガー配列が更新され、ブロック２がパターンの第１のブロックであることを示す。その後、メカニズムはブロック４の非同期読み出しを発行し、ブロック３の要求により起動された操作を終える。ブロック３の非同期要求がすでに発行されて、そのことが状態空間に示されているので、ブロック３のいかなる読み出し要求も発行されないことに注意すべきである。
【００２７】
その後、アプリケーションはブロック５の要求を発行する。状態空間２０は、状態空間のスロット５にブロック５を置くことによって更新され、３、２および１をそれぞれスロット４、３および２に動かす。キャッシュが分析され、ブロック５が前のシーケンス・パターンの連続でないことがわかる。状態空間が検索され、ブロック５が他のエントリとともにパターンを形成するかどうか判断し、その結果何も見つからない。ブロックｌ、３および５がパターンを形成しない点に注意すべきである。これは、ブロック１がシーケンス・パターン１、２、３のオリジナルの第１のブロックであったので、ブロック１がトリガー配列において印をつけられているからである。パターンのオリジナルのブロックは、別のパターンの開始ブロックとして使用されることができない。こうして、メカニズムはこの要求によって起動された操作を終え、ブロック５の読出し要求が発行される。
【００２８】
次のブロック要求であるブロック７が受け取られる。状態空間のスロット５にブロック７を置くことによって状態空間２０が更新され、５、３、２および１を、それぞれスロット４、３、２および１に動かす。キャッシュが分析され、ブロック７がシーケンス・パターンの連続でないことがわかる。状態空間が検索され、ブロック７がブロック３および５とともにパターンを形成すると判断される（２の前方ストライド）。シーケンス・パターンのキャッシュ・エントリが更新され、パターンの要素の状態空間における新規の位置を反映する（具体的には、第１のブロックの索引は現在２であり、第２のブロックおよびストライドは、それぞれ３および１のままである）。メカニズムは、新しいパターンのキャッシュ・エントリを形成する。このエントリは、このパターンを形成する第１のブロックの状態空間の索引すなわちスロット４、パターンの第２のブロックすなわちブロック７、およびパターンのストライドすなわち２を含む。こうして、エントリ４、７、２がキャッシュのスロット１に挿入される。トリガー配列が更新され、ブロック３がパターンを形成するのに使用されたことを示し、ブロック９の非同期要求が発行されたことを示す。その後、メカニズムはブロック９の非同期要求を発行し、ブロック７の要求により起動された操作を終える。
【００２９】
その後、アプリケーションはブロック９を要求する。スロット５に９を置くことにより状態空間が更新され、７、５、３、２および１を、スロット４、３、２、１および０に動かす。キャッシュが分析され、メカニズムは９が前に規定されたパターンの連続であると判断する。メカニズムは、ブロック９が第２のブロック（ここでは７）に２のストライドを加えたものに等しいと気づくことにより、この判断を行う。キャッシュ・エントリが更新され、エントリ０については、第１のブロックの索引が１で、第２のブロックおよびストライドは、それぞれ３および１のままであり、キャッシュ・エントリ１については、第１のブロックの索引が４で、第２のブロックは９で、ストライドは２のままであるようにする。トリガーが更新され、非同期要求がブロック１１について発行されたことを示す。また、トリガー配列が更新され、ブロック７がパターンの第１のブロックであることを示す。その後、メカニズムはブロック１１の非同期要求を発行し、ブロック９の要求によって起動された操作を終える。
【００３０】
その後、アプリケーションはブロック４を要求する。スロット５に４を置くことによって状態空間が更新され、９、７、５、３および２をスロット４、３、２、１および０に動かす。キャッシュが分析され、メカニズムは４が前に規定されたパターンの連続であると判断する。メカニズムは、ブロック４が第２のブロック（ここでは３）に１のストライドを加えたものに等しいと気づくことにより、この判断を行う。キャッシュ・エントリが更新され、エントリ０については、それぞれ第１のブロックの索引がブロック３についての１であり、第２のブロックが４であり、ストライドが１のままであるようにする。キャッシュ・エントリ１については、第１のブロックの索引は３であり、第２のブロックおよびストライドはそれぞれ９および２のままであるようにする。トリガーが更新され、ブロック３が予測のため使用されたことを示す。メカニズムは、任意に状態空間を調査することができ、ブロック５の要求がすでに発行されて状態空間にあることに気づくので、ブロック５の非同期要求を発行することはない。こうして、メカニズムはブロック５の要求を終える。
【００３１】
パターン検出メカニズムが２つのエントリ（すなわち１および２のエントリ）でシーケンスを検出して、それが３を予測する点に注意すべきである。しかし、ストライドについては、９を予測するのに、検出の前に３つのエントリ（すなわち３、５、７）を必要とする。これは、順次読出しが、１だけ離れた２つのブロックであるよう定義されるのに対し、ストライド読出しは、ＡおよびＢの間の距離が、ＢおよびＣの間の距離と同じであるよう定義されるので、検出の前に３つのブロックＡ、ＢおよびＣを必要とする。
【００３２】
また、パターン・キャッシュのミスがあると（これは、一致するパターンが存在しないということを意味する）、ブロックのすべての可能な組合せについて状態空間全体が調べられることに注意すべきである。これは、コストのかかる操作であるので、パターン・キャッシュが、新規のエントリごとのパターン検索の必要性を減らす。図２（Ａ）および（Ｂ）のｌ、２、３、５、７、９および４の要求の順番をもつパターン検索は、次のようになる。ブロック４の要求が到着するときにパターン検索が行われ、状態空間は４、９、７、５、３および２をスロット５〜０にそれぞれ保持すると仮定する。検索は、３つの目印、Ｍａ、ＭｂおよびＭｃを状態空間のスロットに置く。ここで、Ｍａの初期位置はスロット５に、Ｍｂは状態空間の最も古いスロットすなわちスロット０に、ＭｃはＭｂ＋１（これは、２番目に古いスロット、すなわちスロット１）にある。第１の比較の後、Ｍａ−ＭｃがＭｃ−Ｍｂに等しければ一致が生じ、Ｍｃが１スロットだけ動かされ、他の比較が行われる。これは、Ｍｃがスロット４に達するまで続き、それからＭｂが１スロットだけ動かされ、ＭｃはＭｂ＋１に設定される。検索は、Ｍｂがスロット３に、Ｍｃがスロット４にくるまで続き、これは、状態空間が完全に検索されたことを示す。
【００３３】
検索は、以下のシーケンスを生じさせる。（Ｍａ，Ｍｃ，Ｍｂ）：  （４，３，２）  （４，５，２）  （４，７，２）  （４，９，２），  （４，５，３）  （４，７，３）  （４，９，３）  （４，７，５）  （４，９，５）および（４，９，７）。第１のシーケンス（４，３，２）は、１のストライドをもつ前方シーケンスを示し、状態空間に、２の次に３、その次に４と置かれることを意味する。このように、検索は、距離が同じだけ離れている３つのブロックの任意の可能な組合せを探しながら、すべての可能な並べ換えを介して繰り返される。これが、検索がコストがかかり、かつキャッシュが必要となる理由である。しかし、検索が、完全なＮの３乗の検索でないことに注意すべきである。それは、Ｍａが状態空間の最も最近のエントリに設定され、検索の間に動かされることが無いからである。ブロック９（または７，５，３または２）に設定されるＭａを持つ検索は以前に起こったので、そのような検索を繰り返す必要がない。また、検索は１つの方向にのみ行われ、状態空間を上方に進む必要がない。また検索は、有効なキャッシュカウントを介して状態空間のエントリ数を常に把握しているので、空のスロットは検索されない。また、一致が見つけられると検索が停止されるので、上記の例においては、第１のシーケンスが検索された後に検索は停止する。検索は、１のストライド距離（正だろうが負だろうが）だけ離れた２つのブロックがあるかどうか確認し、また等しい距離（正だろうが負だろうが）だけ離れた３つのブロックがあるかどうか確認する。
【００３４】
状態空間およびキャッシュが、それぞれ簡略化するため６つのスロットおよび５つのスロットとして示され、他のサイズを使用することもできる点に注意すべきである。さらに、プロセスにおけるキャッシュ線の特定の数に適合させるようサイズを調整するのが、特に有利である。このように、空間およびパターン・キャッシュは、プロセスのオンチップ・キャッシュにおさまり、メモリはこの評価には使用されない。例えば、符号なし（ｕｎｓｉｇｎｅｄ）の要素を持つ１５のスロットの状態空間は、４本のキャッシュ線を占領する。２本のキャッシュ線の状態空間では、順次性を検出できる。４本のキャッシュ線の状態空間では、ファイルの異なる位置にある２つの同時に起こる順次リーダを検出することができる。１５の状態スロットを持ち、３つのブロックで１つのパターンを作ることによって、多くとも５つのパターンが状態空間に存在するので、パターン・キャッシュは５つのパターンを保持すべき点に注意しなければならない。パターンの数を、並列プロセス数、またはアプリケーションが持つことのできる同時に操作する並列スレッド数に従って、設定することができる点に注意しなければならない。
【００３５】
図３は、本発明の予測メカニズムの他の実施形態を表す。図３は、図２（Ｂ）のパターン・キャッシュを示すが、予測の強さを表す追加のエントリを持つ。予測が行われ、その後に正しいと証明されたとき、未来の予測を、より起こりそうなものとして、すなわちより強いとみることができる。このように、パターンが認識されるときはいつでも、強さは１に設定される。しかし、メカニズムがパターンの連続を検出するたびに、強さは１だけ増やされる。こうして、ブロック３の要求が到着した後、順次パターンの強さは２に増やされる。ブロック４の要求が到着した後、強さは３に増やされる。ブロック９の要求が到着するとき、ストライド・パターンの強さは３に増やされる。
【００３６】
この強さは、いくつのブロックを先読みするかを決定する際にオペレーティングシステムにより使用されることができる。例えば、強さが５０の場合には、パターンに合った次の５００個のブロックについて、オペレーティングシステムは先読みを発行することができる。これは、１度に１つの非同期先読みを発行する待ち時間のオーバーヘッドを削減する。処理時間が非同期読み出し時間より小さいとき、これは重要であり、プロセスまたはスレッドが渇望するのを防ぐ。
【００３７】
プログラムの写しを、参考資料として提出する。プログラムは、広範囲にわたって注釈されており、ユーザがメカニズムの操作を理解するのを助ける。１つの「ｓｔｒｕｃｔ  ｐａｔｔｅｒｎ」が、それぞれのファイルに必要とされ、ｖノードに加えられる。また、「ターム（ｔｅｒｍ）・ファイル」が、仮想記憶ファイル（スワップ領域）だけでなく両方のデータファイル、実行可能ファイル、Ｍマップ・ファイルを含む点に注意すべきである。さらに、「ｐａｔｔｅｒｎ＿ｓｅａｒｃｈ」が行う第１のステップが、新規の要求を、前に検出されたパターンの連続として調べようとし、かつ位置づけようとすることに注意すべきである。また、前方の順次読出しおよび後方の順次読み出しが個別に呼び出されるが、実際の数値演算は、それぞれについて同じものである。順次検出は、２つのポイントまたは３つのポイントに基づくことができる。ｐｒｉｎｔｆの位置は、オペレーティングシステムへの非同期読出しコマンドが、プログラムで発行されるところであり、言い換えると、ＯＳとのインタフェースが置かれるところである。上述したように、ＴＸ２、ＸおよびＴＸがＭａ、ＭｂおよびＭｃにそれぞれ対応する。ＴＸ２は、Ｘサイズから１を減じたものであり、これが最も最近の要求である。トリガーは、データの所与の１つの新規なポイントに基づいて複数のパターンを形成するのを防ぐ。
【００３８】
本発明およびその利点を詳細に記述したけれども、多様な変更、代替を、特許請求の範囲により規定される本発明の精神および範囲から離れることなく行うことができるということを理解すべきである。
【００３９】
本発明は例として次の実施態様を含む。
（１）現在の要求（１１）および少なくとも１つの前の要求に基づいて、複数の実行ストリームを持つアプリケーション操作により要求される次のデータブロックを予測する（１６）方法であって、
前記アプリケーションにより作られた前記現在の要求および前の２つの要求の間にストライド・パターンが存在するかどうか検出するステップ（１３、１７）と、
前記検出するステップの結果に基づいて前記次のブロックを予測するステップ（１６）と、を含む次のデータブロックを予測する方法。
【００４０】
（２）前記現在の要求および少なくとも１つの前の要求の間に、順次パターンが存在するかどうか検出するステップを含む上記（１）に記載の次のデータブロックを予測する方法。
（３）状態空間にそれぞれの要求を読み出すステップと、
それぞれの検出されたパターンについての情報をキャッシュに格納するステップと、を含む上記（１）に記載の次のデータブロックを予測する方法。
（４）前記検出するステップが、
前記キャッシュを分析して、前記現在の要求が、任意の既存のパターンの連続であるかどうか判断するステップ（１３）と、
前記分析するステップ（１３）が、前記現在の要求が任意の既存のパターンの連続でないと判断すれば、前記状態空間を検索して、前記現在の要求が任意の前の要求とともにパターンを形成するかどうか判断するステップ（１７）と、を含む上記（３）に記載の次のデータブロックを予測する方法。
【００４１】
（５）前記検索するステップが、
前記状態空間（２０）における現在の要求に第１の目印を設定するステップと、
最初に、前記状態空間における最も古い要求に第２の目印を設定するステップと、
最初に、前記状態空間における次に最も古い要求に第３の目印を設定するステップと、
前記第１の目印および前記第３の目印により示されるブロックの第１の差を、前記第３の目印および前記第２の目印により示されるブロックの第２の差と比較して、該第１の差が該第２の差に等しいかどうか判断するステップと、
前記第２および第３の目印の少なくとも１つを、前記状態空間の少なくとも１つの他の位置に動かすステップと、
前記状態空間全体について、前記比較するステップおよび前記動かすステップを繰り返すステップとを含み、
前記第１の差が前記第２の差に等しいとき、パターンが置かれるようにする上記（４）に記載の次のデータブロックを予測する方法。
【００４２】
（６）前記検索するステップが、
前記パターンが置かれるとき、前記検索するステップを停止させるステップを含む上記（５）に記載の次のデータブロックを予測する方法。
（７）前記次のブロックに関する情報をトリガー配列に格納し、前記次のブロックの非同期先読みの再発行することを防ぐステップを含む上記（４）に記載の方法。
【００４３】
（８）前記分析するステップが、前記現在の要求が既存のパターンの連続であると判断する場合において、前記検出するステップが、
前記キャッシュを更新して現在の要求についての情報を含めるステップ（１４）と、前記現在の要求および前記既存のパターンのストライドを合計することにより、パターンの次のブロックを判断するステップと、
前記トリガー配列を調べ、次のブロックの非同期先読みが、前に発行されたかどうか判断するステップ（１５）と、
次のブロックの非同期先読みが、前に発行されていなければ、前記トリガー配列を更新するステップ（１５）と、
前記次のブロックの非同期先読みが前に発行されていなければ、前記次のブロックの非同期先読みを発行するステップ（１６）と、を含む上記（７）に記載の次のデータブロックを予測する方法。
【００４４】
（９）前記検索するステップが、前記現在の要求が、少なくとも１つの前の要求と共に新規なパターンを形成すると判断する場合において、前記検出するステップが、
有効なキャッシュカウントを更新して、既存のパターンの数を増やすステップ（１８）と、
新規のキャッシュ・エントリを、前記新規なパターンについての情報を備えるキャッシュに挿入するステップ（１９）と、
前記現在の要求および前記新規なパターンのストライドを合計して、前記新規なパターンの次のブロックを判断するステップと、
前記トリガー配列を調べ、前記次のブロックの非同期先読みが、前に発行されたかどうか判断するステップ（１５）と、
前記次のブロックの非同期先読みが、前に発行されていなければ、前記トリガー配列を更新するステップ（１５）と、
前記次のブロックの非同期先読みが、前に発行されていなければ、前記次のブロックの非同期先読みを発行するステップ（１６）と、を含む上記（７）に記載の次のデータブロックを予測する方法。
【００４５】
（１０）前記新規のキャッシュ・エントリ（４０）が、前記分析するステップにより判断された新規のパターンの連続数を示す強さの値を含んでおり、
該強さの値がオペレーティングシステムにより使用され、前記新規のパターンに基づいて発行された非同期先読みの量を判断する上記（９）に記載の次のデータブロックを予測する方法。
【００４６】
【発明の効果】
本発明によると、マルチプロセスまたはマルチスレッドのシステムにより発行される複雑な読み出しパターンにおける前方ストライド、後方ストライド、前方順次および後方順次のパターンを認識することができる予測メカニズムを提供することにより、オペレーティングシステムが、メモリにデータを速く送ることができる。
【図面の簡単な説明】
【図１】本発明の予測メカニズムの流れ図。
【図２】読み出し要求のシーケンスが、図１の流れ図によるアプリケーションから受け取られる時の、状態空間およびパターン・キャッシュの経過を示す図。
【図３】図２（Ｂ）に類似し、予測の強さを規定するエントリを含むパターン・キャッシュを示す図。
【符号の説明】
２０    状態空間
３０    パターン・キャッシュ
【図１】
0003587710.tif 000002
【図２】
0003587710.tif 000003
【図３】
0003587710.tif 000004