(57)【要約】【課題】プログラムによるデータ読み出しに先立って効率良くデータの先読みを行う。【解決手段】プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置であって、プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、履歴に記録された複数のデータ読み出しに対応する複数の先読みを生成する先読み生成部と、履歴に基づいて、複数の先読みの実行順序を決定する先読み手順決定部と、実行順序が決定された後にプログラムが実行されたことに応じて、複数の先読みのそれぞれを実行順序により実行するプリフェッチ部とを備える先読み装置を提供する。【選択図】図２
2006260067.tif 000002
【特許請求の範囲】
【請求項１】
プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置であって、
前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、
前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成部と、
前記履歴に基づいて、前記複数の先読みの実行順序を決定する先読み手順決定部と、
前記実行順序が決定された後に前記プログラムが実行されたことに応じて、前記複数の先読みのそれぞれを前記実行順序により実行するプリフェッチ部と
を備える先読み装置。
【請求項２】
前記先読み手順決定部は、
前記履歴に基づいて、前記複数の先読みの実行順序を決定する順序決定部と、
前記複数の先読みを、１以上の先読みを含む複数のグループに分割する分割部と、
それぞれの前記グループに対応して、当該グループに含まれる前記１以上の先読みを開始するグループ開始タイミングを決定するタイミング決定部と
を有し、
前記プリフェッチ部は、前記実行順序および前記グループ開始タイミングが決定された後に前記プログラムが実行されたことに応じて、それぞれの前記グループについて、当該グループに対応する前記グループ開始タイミングに当該グループに含まれる前記１以上の先読みの実行を開始する
請求項１に記載の先読み装置。
【請求項３】
前記分割部は、先読みにより前記バッファに読み出され、前記プログラムにより前記バッファから読み出されていないデータによる前記バッファの使用量が、予め定められた上限値を超えないように前記複数の先読みを前記複数のグループに分割し、
前記タイミング決定部は、前記バッファの使用量が前記上限値を超えないようにそれぞれの前記グループについて前記グループ開始タイミングを決定する
請求項２に記載の先読み装置。
【請求項４】
前記タイミング決定部は、前記バッファの使用量が予め定められた下限値未満となる場合に次のグループに含まれる前記先読みが開始されるように、それぞれの前記グループに対応する前記グループ開始タイミングを決定する請求項３に記載の先読み装置。
【請求項５】
当該先読み装置は、前記プログラムを実行する情報処理装置上において、前記プログラムと並行して先読み用プログラムを実行することにより実現され、
前記プリフェッチ部は、前記情報処理装置上で動作するオペレーティングシステムにより実現される前記バッファであるファイルキャッシュに対し、それぞれの前記データ読み出しの対象となるデータを予めキャッシュさせることにより対応する前記先読みを実行する
請求項１に記載の先読み装置。
【請求項６】
前記プログラムがデータ読み出しを発行したことに応じて、前記プログラムが読み出しを要求したデータ量の合計値を計測する計測部を更に備え、
前記先読み手順決定部は、
前記履歴に基づいて、前記複数の先読みの実行順序を決定する順序決定部と、
前記複数の先読みを、１以上の先読みを含む複数のグループに分割する分割部と、
それぞれの前記グループに対応して、前記データ量の合計値が当該グループについて定めた基準データ量を超えたことを条件として当該グループに含まれる先読みを開始することを決定するタイミング決定部と
を有し、
前記計測部は、前記データ量の合計値が次に実行すべき前記グループに対応する前記基準データ量を超えたことを条件として、前記プリフェッチ部を呼び出し、
前記プリフェッチ部は、前記計測部の呼び出しに応じて次に実行すべき前記グループに含まれる前記先読みを実行する
請求項５に記載の先読み装置。
【請求項７】
前記プリフェッチ部は、
前記計測部の呼び出しを受けたことに応じて前記ファイルキャッシュの使用量を取得し、
前記ファイルキャッシュの使用量が予め定められた基準使用量未満であることを条件として２以上の前記グループに含まれる前記先読みを順次実行する
請求項６に記載の先読み装置。
【請求項８】
前記履歴記録部は、前記プログラムの複数の命令処理と、それぞれの命令処理に用いられるデータをそれぞれ読み出す複数のデータ読出処理とを実行したタイミングを前記履歴に記録し、
前記先読み手順決定部は、
前記複数の命令処理同士および前記複数のデータ読出処理同士がそれぞれ逐次実行されることを前提として、それぞれの前記データ読出処理を開始すべき読出開始タイミングを、当該データ読出処理により読み出したデータを用いる前記命令処理を開始する前に当該データ読出処理を完了させ、かつ、当該データ読出処理を当該命令処理以前に実行される他の前記命令処理と並行に行わせるように決定する読出開始タイミング決定部と、
前記複数の先読み同士がそれぞれ逐次実行されることを前提として、前記複数のデータ読出処理のそれぞれについて、当該データ読出処理の前記読出開始タイミングにおいて当該データ読出処理に対応する前記先読みが完了しているように前記複数の先読みの先読み開始タイミングを決定する先読み開始タイミング決定部と、
２以上の前記先読みが前記ファイルを記憶する記憶装置上の連続する２以上の領域のそれぞれからデータを読み出すものであり、かつ、当該２以上の先読みを当該連続領域のデータを前記バッファに先読みする１つの前記先読みに置き換えてもいずれの前記データ読出処理の完了タイミングも当該データ読出処理により読み出されたデータを用いる命令処理の開始タイミングより遅らせないことを条件として、当該２以上の先読みを当該連続領域のデータを前記バッファに先読みする１つの前記先読みに置き換える先読み最適化部と
を有する請求項６に記載の先読み装置。
【請求項９】
前記分割部は、
それぞれの前記グループについて、連続する１以上の前記先読みを順次当該グループに加えていき、
前記先読みにより前記バッファに読み出され、前記プログラムにより前記バッファから読み出されていないデータによる前記バッファの使用量が予め定められた上限値を超え、かつ、前記グループに最後に加えられた前記先読みが完了してから前記計測部が次の前記先読みを実行させるべく前記先読みプログラムを呼び出すまでの間に前記データ読み出しが発行される旨の履歴が記録されていることを条件として、当該次の先読みを当該グループの次の前記グループに加える
請求項８に記載の先読み装置。
【請求項１０】
前記先読み手順決定部は、２以上の前記先読みが前記ファイルを記憶する記憶装置上の連続する２以上の領域のそれぞれからデータを読み出すことを条件として、当該２以上の先読みを当該連続領域のデータを前記バッファに先読みする１つの前記先読みに置き換える請求項１に記載の先読み装置。
【請求項１１】
前記プリフェッチ部は、少なくとも１つの前記先読みによりファイルから前記バッファにデータを読み出すのに要した時間が予め定められた基準時間未満であることを検出したことを条件として、前記実行順序が当該先読みより後の前記先読みの実行を中止する請求項１に記載の先読み装置。
【請求項１２】
前記履歴記録部は、複数のプログラムのそれぞれについて、当該プログラムが実行中に発行したデータ読み出しの履歴を記録し、
前記先読み生成部は、それぞれの前記プログラムについて、前記履歴に記録された前記複数の読み出しに対応する前記複数の先読みを生成し、
前記先読み手順決定部は、それぞれの前記プログラムについて、前記複数の先読みの実行順序を決定し、
前記プリフェッチ部は、
前記実行順序が決定された後にいずれかの前記プログラムが実行されたことに応じて、当該プログラムについての前記実行順序を取得する先読み手順取得部と、
取得した前記実行順序により当該プログラムについての前記複数の先読みのそれぞれを実行するプリフェッチ実行部と
を有する請求項１に記載の先読み装置。
【請求項１３】
前記プログラムが読み出しを要求したデータ量の合計値を計測する計測部を更に備え、
前記先読み手順決定部は、それぞれの前記先読みに対応して、前記データ量の合計値が当該先読みについて定めた基準データ量を超えたことを条件として当該先読みを開始することを決定する開始条件決定部を有し、
前記プリフェッチ部は、それぞれの前記先読みについて、前記データ量の合計値が当該先読みについて定めた前記基準データ量を超えた場合に、当該先読みを実行する
請求項１に記載の先読み装置。
【請求項１４】
プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み方法であって、
前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録段階と、
前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成段階と、
前記履歴に基づいて、前記複数の先読みの実行順序を決定する先読み手順決定段階と、
前記実行順序が決定された後に前記プログラムが実行されたことに応じて、前記複数の先読みのそれぞれを前記実行順序により実行するプリフェッチ段階と
を備える先読み方法。
【請求項１５】
プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置用の先読みプログラムであって、
当該先読みプログラムは、前記先読み装置を、
前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、
前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成部と、
前記履歴に基づいて、前記複数の先読みの実行順序を決定する先読み手順決定部と、
前記実行順序が決定された後に前記プログラムが実行されたことに応じて、前記複数の先読みのそれぞれを前記実行順序により実行するプリフェッチ部と
して機能させる先読みプログラム。
【請求項１６】
プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置であって、
前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、
前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成部と、
それぞれの前記先読みに対応して、当該先読みを開始する条件として、前記プログラムが読み出しを要求したデータ量の合計値が満たすべき基準データ量を決定する開始条件決定部と、
前記プログラムが読み出したデータ量の合計値を計測する計測部と、
前記複数の先読みを開始する条件が決定された後に前記プログラムが実行されたことに応じて、それぞれの前記先読みについて、前記データ量の合計値が当該先読みについて定めた前記基準データ量を超えた場合に、当該先読みを実行するプリフェッチ部と
を備える先読み装置。
【請求項１７】
プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み方法であって、
前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録段階と、
前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成段階と、
それぞれの前記先読みに対応して、当該先読みを開始する条件として、前記プログラムが読み出しを要求したデータ量の合計値が満たすべき基準データ量を決定する開始条件決定段階と、
前記プログラムが読み出したデータ量の合計値を計測する計測段階と、
前記複数の先読みを開始する条件が決定された後に前記プログラムが実行されたことに応じて、それぞれの前記先読みについて、前記データ量の合計値が当該先読みについて定めた前記基準データ量を超えた場合に、当該先読みを実行するプリフェッチ段階と
を備える先読み方法。
【請求項１８】
プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置用の先読みプログラムであって、
当該先読みプログラムは、前記先読み装置を、
前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、
前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成部と、
それぞれの前記先読みに対応して、当該先読みを開始する条件として、前記プログラムが読み出しを要求したデータ量の合計値が満たすべき基準データ量を決定する開始条件決定部と、
前記プログラムが読み出したデータ量の合計値を計測する計測部と、
前記複数の先読みを開始する条件が決定された後に前記プログラムが実行されたことに応じて、それぞれの前記先読みについて、前記データ量の合計値が当該先読みについて定めた前記基準データ量を超えた場合に、当該先読みを実行するプリフェッチ部と
して機能させる先読みプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、先読み装置、先読み方法、および先読みプログラムに関する。特に本発明は、プログラムによるデータの読み出しに先立ってファイルからバッファにデータを先読みする先読み装置、先読み方法、および先読みプログラムに関する。
【背景技術】
【０００２】
近年のプロセッサの高速化に伴い、ハードディスク・ドライブ等の外部記憶装置からデータを読み込むのに要する時間がプロセッサの処理時間と比較して非常に大きくなっている。このため、プロセッサは、外部記憶装置からデータを読み出して処理する場合において、外部記憶装置へ読み出しを要求してから読み出しの完了までの間頻繁に入出力待ち（ＩＯ  ｗａｉｔ）状態となってしまう。
この入出力待ち時間による性能低下を抑える方法として、外部記憶装置からデータを予め先読み（プリフェッチ）する技術が各種提案されている。
【０００３】
非特許文献１および２は、プログラムの実行時に、ファイルが逐次読み出しされているか否かを検出し、逐次読み出しされている場合には逐次的にファイルを先読みする技術を開示する。
【０００４】
非特許文献３から５は、プログラムを事前に実行してプログラムがアクセスするファイルの情報をプロファイルとして収集し、プロファイルに基づいてファイルを先読みする技術を開示する。非特許文献３から４は、各プログラムがアクセスする一連のファイルのアクセス順序をプロファイルに基づいて生成しておき、プログラムの実行時にあるファイルがアクセスされると、次のファイルを先読みする技術を開示する。非特許文献５は、ハードディスクのクラスタ毎に、当該クラスタの次にアクセスされる可能性が高いクラスタを指定する情報を記憶させておく。そして、あるクラスタが読み出されると、次にアクセスされる可能性が高いクラスタを先読みする。
【０００５】
非特許文献６および７は、外部記憶装置から先読みすべきデータをプログラム上で指定することにより、適切に先読みを行う方法を開示する。
【０００６】
非特許文献８は、プログラムをコンパイラにより解析してファイルのアクセスパターンを検出し、コンパイラにより実行コード中に先読み処理を挿入する方法を開示する。
【０００７】
非特許文献９および１０は、実行するプログラムから不要な処理等を取り除いた先読み用プログラムを用いて先読みを行う方法を開示する。すなわち、先読み用プログラムを元のプログラムに先行して実行して先読みを行わせ、元のプログラムに先読みしたデータを利用させる。
【０００８】
非特許文献１１および１２は、ハードディスクに対して発行されたアクセス要求の順序を並べ替えて、ヘッドのシーク時間を短縮する技術を開示する。
【０００９】
【非特許文献１】R. J. Feiertang and E. I. Organisk, "The Multics Input/Output System", in Proceedings of Third Symposium on Operating System Principles, pp.35-41, １９７１年
【非特許文献２】M. K. McKusick, W. J. Joy, S. J. Leffler, and R. S. Fabry, "A Fast File System for Unix", ACM Transactions on Computer Systems, 2(3), pp.181-197, １９８４年
【非特許文献３】H. Lei and D. Duchamp, "An Analytical Approach to File Prefetching", USENIX 1997, １９９７年
【非特許文献４】J. Griffioen and R. Appleton, "Reducing File System Latency using a Predictive Approach", in Proceedings of the USENIX Summer Technical Conference, pp. 197-207, １９９４年
【非特許文献５】K. S. Grimsrud, J. K. Archibald, and B. E. Nelson, "Multiple Prefetch Adaptive Disk Caching", IEEE Transaction on Knowledge and Data Engineering, Vol. 5, No. 1, pp. 88-103, １９９３年
【非特許文献６】Jeffrey Richter, "Advanced Windows - The Developer's Guide to the Win32(r) API for Windows NT(tm) 3.5 and Windows 95" , Microsoft Press, １９９５年
【非特許文献７】R. H. Patterson, et. al., "Informed Prefetching and Caching", in Proceeding of Fifteenth Symposium on Operating System Principles, pp. 79-95, １９９５年
【非特許文献８】T. C. Mowry, A. K. Demke, and O. Krieger, "Automatic Compiler-Inserted I/O Prefetching for Out-of-Core Application", in Proceedings of the 2nd USENIX Symposium on Operating Systems Design and Implementation, １９９６年
【非特許文献９】C. K. Yang, T. Mitra, and T. C. Chiueh, "A Decoupled Architecture for Application-Specific File Prefetching", USENIX 2002, ２００２年
【非特許文献１０】K. Fraser and F. Chang, "Operating System I/O Speculation: How two invocations are faster than one", USENIX 2003, ２００３年
【非特許文献１１】C. C. Gotlieb and G. H. MacEwen, "Performance of Movable-Head Disk Strage Devices", Journal of ACM, Vol. 20, No. 4, pp. 604-623, １９７３年
【非特許文献１２】R. Geist and S. Daniel, "A Continuum of Disk Scheduling Algorithms, ACM Transactions on Computer Systems," Vol. 5, No. 1, pp. 77-92, １９８７年
【発明の開示】
【発明が解決しようとする課題】
【００１０】
近年、ネットワーク上に複数の情報処理装置が接続された情報システムとして、Ｊａｖａ（登録商標）によるプログラムを用いるシステムが普及している。Ｊａｖａ（登録商標）のプログラム環境においては、プログラムの実行単位となる多数のクラスがＪＡＲファイル（Ｊａｖａ（登録商標）  ＡＲｃｈｉｖｅ  Ｆｉｌｅ）に格納されている。このため、Ｊａｖａ（登録商標）によるアプリケーションプログラムを実行する場合、アプリケーションプログラムの起動時に、多数のクラスをＪＡＲファイルから読み出す必要がある。
【００１１】
この起動時の読み出しにおいては、必要なクラスファイルが順次読み出されるので、ＪＡＲファイルに対して不規則なアクセス位置の読み出しが発行される。
【００１２】
これに対し、非特許文献１および２の先読み方法においては、ファイルを逐次的に先読みするので、Ｊａｖａ（登録商標）のプログラム環境において先読みを適切に行うことができない。
【００１３】
また、非特許文献３から５の先読み方法においては、先読みしたデータを格納するキャッシュの容量、および先読みするタイミングを考慮しておらず、プログラムによっては先読みの効果が得られない可能性がある。
【００１４】
また、非特許文献６および７の先読み方法においては、先読みすべきデータをプログラム作成者が指定する必要があり、プログラム作成の負担が増大する。
【００１５】
また、非特許文献８の先読み方法においては、コンパイラで解析可能な範囲を越える比較的広いコード領域に応じた先読みを行うのが困難である。
【００１６】
また、非特許文献９および１０の先読み方法においては、実行すべきプログラムの一部を取り除いたことにより先読み用プログラムの動作フローが実行すべきプログラムと不一致となる場合がある。この場合には、誤ったデータを先読みしてしまう。また、先読み用プログラムを並行して実行するため、プログラム実行のオーバーヘッドが大きくなる。
【００１７】
非特許文献１１および１２においては、プログラムが読み出しを要求したデータの読み出し速度を向上することができるが、プロセッサが入出力待ち状態となるのを回避することができない。
【００１８】
そこで本発明は、上記の課題を解決することのできる先読み装置、先読み方法、および先読みプログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００１９】
本発明の第１の形態によると、プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置であって、前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成部と、前記履歴に基づいて、前記複数の先読みの実行順序を決定する先読み手順決定部と、前記実行順序が決定された後に前記プログラムが実行されたことに応じて、前記複数の先読みのそれぞれを前記実行順序により実行するプリフェッチ部とを備える先読み装置、および当該先読み装置に関する先読み方法および先読みプログラムを提供する。
【００２０】
本発明の第２の形態によると、プログラムによるデータの読み出しに先立ってファイルからバッファに当該データを先読みする先読み装置であって、前記プログラムが実行中に発行したデータ読み出しの履歴を記録する履歴記録部と、前記履歴に記録された複数の前記データ読み出しに対応する複数の先読みを生成する先読み生成部と、それぞれの前記先読みに対応して、当該先読みを開始する条件として、前記プログラムが読み出しを要求したデータ量の合計値が満たすべき基準データ量を決定する開始条件決定部と、前記プログラムが読み出したデータ量の合計値を計測する計測部と、前記複数の先読みを開始する条件が決定された後に前記プログラムが実行されたことに応じて、それぞれの前記先読みについて、前記データ量の合計値が当該先読みについて定めた前記基準データ量を超えた場合に、当該先読みを実行するプリフェッチ部とを備える先読み装置、および当該先読み装置に関する先読み方法および先読みプログラムを提供する。
【００２１】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００２２】
本発明によれば、プログラムによるデータ読み出しに先立って効率良くデータの先読みを行うことができる。
【発明を実施するための最良の形態】
【００２３】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００２４】
図１は、本実施形態に係る情報処理装置１９００のハードウェア構成の一例を示す。本実施形態において、情報処理装置１９００は、プログラム１０を実行し、プログラム１０からの要求に応じてファイル２０からデータを読み出してプログラム１０に供給する。また、情報処理装置１９００は、本発明に係る先読み装置としても機能し、情報処理装置１９００上で実行されるプログラム１０によるデータの読み出しに先立って、ファイル２０からバッファ３０に当該データを先読み（プリフェッチ）する。これにより、プログラム１０は、ハードディスクドライブ２０４０からのデータ読み出しに代えてバッファ３０から当該データを取得することができ、最小限の入出力待ちで命令処理をすることができる。
【００２５】
本実施形態に係る情報処理装置１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【００２６】
ホスト・コントローラ２０８２は、読み書き可能なメモリであるＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００２７】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、情報処理装置１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する記憶装置である。ハードディスクドライブ２０４０は、ＲＡＭ２０２０と比較して大容量であるが、アクセス時間が長い。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【００２８】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、情報処理装置１９００が起動時に実行するブート・プログラムや、情報処理装置１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。
【００２９】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介して情報処理装置１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【００３０】
プログラム１０は、情報処理装置１９００内のハードディスクドライブ２０４０にインストールされ、または通信インターフェイス２０３０を介して外部から取得される。プログラム１０は、情報処理装置１９００により実行されて、先読みの対象となるデータを読み出しつつ情報処理装置１９００による情報処理を行う。プログラム１０は、例えばＣＰＵ２０００により実行可能なバイナリ形式のアプリケーションプログラムであってよく、これに代えて、Ｊａｖａ（登録商標）バーチャルマシンの命令形式等の実行時に実行可能形式に変換されるプログラムであってもよい。
【００３１】
情報処理装置１９００を先読み装置として機能させる先読みプログラムは、情報処理装置１９００内のハードディスクドライブ２０４０にインストールされ、プログラム１０によるデータの読み出しに先立ってハードディスクドライブ２０４０に格納されたファイル２０からＲＡＭ２０２０上に設けたバッファ３０に当該データを先読みする。
【００３２】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤやＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを情報処理装置１９００に提供してもよい。
【００３３】
図２は、本実施形態に係る情報処理装置１９００の機能構成を示す。本実施形態に係る情報処理装置１９００は、プログラム１０、オペレーティングシステム２００、および先読みプログラムを実行する。そして情報処理装置１９００は、先読みプログラムを実行することにより先読み装置２１０としても機能する。
【００３４】
プログラム１０は、情報処理装置１９００上で実行され、命令処理と、次の命令処理に用いるデータを読み出すデータ読出処理とを交互に行うことにより所望の情報処理を行う。プログラム１０は、データ読出処理において、オペレーティングシステム２００に対しデータ読み出しを発行し、オペレーティングシステム２００が読み出しの対象となるファイル２０から読み出したデータを受け取る。
【００３５】
オペレーティングシステム２００は、情報処理装置１９００上で実行され、情報処理装置１９００のハードウェア資源を管理してプログラム１０等のアプリケーションプログラムに使用させる。オペレーティングシステム２００は、バッファ３０を有する。バッファ３０は、情報処理装置１９００上で動作するオペレーティングシステム２００により実現される。一例としてバッファ３０は、オペレーティングシステム２００が管理するファイルキャッシュであってよい。このファイルキャッシュは、ハードディスクドライブ２０４０内のファイル２０から読み出したデータをキャッシュし、プログラム１０からの要求に応じて再利用させるためにオペレーティングシステム２００により提供される。
【００３６】
先読み装置２１０は、ハードディスクドライブ２０４０等にインストールされた先読みプログラムを、情報処理装置１９００上でプログラム１０と並行して実行することにより実現され、プログラム１０によるデータの読み出しに先立ってファイル２０からバッファ３０にデータを先読みする。当該先読みプログラムは、データ読出中継モジュール、先読み生成モジュール、先読み手順決定モジュール、およびプリフェッチモジュールを有する。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、情報処理装置１９００を、データ読出中継部２２０と、先読み生成部２３０と、先読み手順決定部２４０と、プリフェッチ部２６５としてそれぞれ機能させる。
【００３７】
データ読出中継部２２０は、プログラム１０が実行中にオペレーティングシステム２００に対して発行したデータ読み出しを取得して、当該データ読み出しに応じた先読み装置２１０の処理を起動する。そして、データ読出中継部２２０は、取得したデータ読み出しをオペレーティングシステム２００に対して発行し、オペレーティングシステム２００によりデータを読み出させてプログラム１０へと返送させる。この機能は、例えばオペレーティングシステム２００が提供するデータ読出関数をフックしたり、当該データ読出関数を書き換えてデータ読出中継部２２０の機能を呼び出したり等することにより実現することができる。
【００３８】
データ読出中継部２２０は、情報処理装置１９００に履歴記録モジュールおよび計測モジュールを実行させることにより実現される履歴記録部２２２および計測部２２４を含む。履歴記録部２２２は、プログラム１０が実行中に発行したデータ読み出しの履歴をプロファイルとして記録する。計測部２２４は、先読み装置２１０が次の先読み処理を開始すべき条件が満たされたか否かを判断する先読み開始判断部として機能する。本実施形態において計測部２２４は、プログラム１０がデータ読み出しを発行したことに応じて、プログラム１０が読み出しを要求したデータ量の合計値を計測する。そして、当該データ量の合計値が次に実行すべき先読み処理に対応して先読み手順決定部２４０により予め定められた基準データ量となったことに応じて、当該先読み処理を開始すべき条件が満たされたと判断する。先読み処理を開始すると判断すると、計測部２２４は、プリフェッチ部２６５内のプリフェッチ実行部２６９を呼び出して先読み処理を実行させる。
【００３９】
先読み生成部２３０は、履歴記録部２２２により履歴に記録された複数のデータ読み出しに対応する複数の先読みを生成する。先読み手順決定部２４０は、履歴記録部２２２により記録された履歴に基づいて、先読み生成部２３０により生成された複数の先読みの実行順序を決定する。
【００４０】
先読み手順決定部２４０は、複数の先読みの実行順序、および、複数の先読みを開始する開始条件としての開始タイミングを決定する。そして先読み手順決定部２４０は、決定した実行順序および開始タイミングの情報を含む先読み手順を作成し、計測部２２４および先読み手順取得部２６７に供給する。先読み手順決定部２４０は、情報処理装置１９００に順序決定モジュール、分割モジュール、およびタイミング決定モジュールを実行させることにより実現される順序決定部２４５、分割部２５０、およびタイミング決定部２５５を含む。
【００４１】
順序決定部２４５は、履歴記録部２２２が記録した履歴に基づいて、先読み生成部２３０が生成した複数の先読みの実行順序および先読み開始タイミングを決定する。順序決定部２４５は、先読み最適化部２４７を含む。先読み最適化部２４７は、複数の先読みの実行順序を最適化する。本実施形態に係る先読み最適化部２４７は、ハードディスクドライブ２０４０上の連続領域を個別に読み出す２以上の先読みをまとめて１つの先読みに置き換えることにより先読みの最適化を図る。
【００４２】
分割部２５０は、複数の先読みを、１以上の先読みを含む複数のグループに分割する。本実施形態に係るプリフェッチ実行部２６９は、計測部２２４からの呼び出し毎に、次に処理されるべきグループに属する１以上の先読みをまとめて実行する。これにより、計測部２２４がプリフェッチ実行部２６９を呼び出す回数を削減し、先読みのオーバーヘッドを低減する。
【００４３】
タイミング決定部２５５は、本発明に係るタイミング決定部及び／又は開始条件決定部として機能し、複数の先読みのそれぞれを開始する開始条件として、それぞれの先読みの開始タイミングを決定する。本実施形態においてタイミング決定部２５５は、分割部２５０により生成されたそれぞれのグループに対応して、当該グループに含まれる１以上の先読みを開始するグループ開始タイミングを決定する。より具体的には、本実施形態に係るタイミング決定部２５５は、グループ開始タイミングを、計測部２２４が計測するデータ量の合計値が満たすべき条件として決定する。
【００４４】
タイミング決定部２５５は、読出開始タイミング決定部２５７と、先読み開始タイミング決定部２５９とを含む。読出開始タイミング決定部２５７は、履歴記録部２２２が記録したデータ読み出しの履歴に基づいて、先読みによりプログラム１０を効率良く実行した場合にそれぞれのデータ読出処理が開始されるべき読出開始タイミングを決定する。先読み開始タイミング決定部２５９は、それぞれのデータ読出処理について、読出開始タイミングにおいて先読みが完了しているように当該データ読み出しに対応する先読みを開始する先読み開始タイミングを決定する。本実施形態において先読み開始タイミング決定部２５９は、それぞれの先読みに対応して、当該先読みを開始する条件として、プログラム１０が読み出しを要求したデータ量の合計値が満たすべき基準データ量の条件を決定する。
【００４５】
プリフェッチ部２６５は、先読み手順決定部２４０により先読みの実行順序および開始タイミングが決定されて先読み手順を受け取った後にプログラム１０が実行されたことに応じて、複数の先読みのそれぞれを当該先読み手順に記述された実行順序および開始タイミングにより実行する。プリフェッチ部２６５は、情報処理装置１９００に先読み手順取得モジュールおよびプリフェッチ実行モジュールを実行させることにより実現される先読み手順取得部２６７およびプリフェッチ実行部２６９を含む。先読み手順取得部２６７は、プログラム１０が実行されたことに応じて、当該プログラム１０についての先読み手順を先読み手順決定部２４０から取得する。
【００４６】
プリフェッチ実行部２６９は、先読みを開始する条件が満たされたことに応じて計測部２２４により呼び出され、先読み手順取得部２６７が取得した先読み手順によりプログラム１０についての複数の先読みのそれぞれを実行する。より具体的には、プリフェッチ実行部２６９は、計測部２２４により呼び出されて１つのグループに含まれる１以上の先読みを実行し、待ち状態となる。そして、次に計測部２２４から呼び出されると、次のグループに含まれる１以上の先読みを実行する。
【００４７】
本実施形態に係るプリフェッチ実行部２６９は、先読み処理において、プログラム１０のデータ読み出しに先立って、ファイル２０内の対象データを読み出すことをオペレーティングシステム２００に指示する。これによりオペレーティングシステム２００は、当該対象データをファイル２０からバッファ３０に読み込む。この結果、オペレーティングシステム２００は、プログラム１０からのデータ読み出しを受けると、バッファ３０に既に読み込まれた当該対象データを返送することができる。
【００４８】
以上に示した先読み装置２１０によれば、プログラム１０によるデータ読み出しの履歴を取得し、履歴に基づいて適切な先読み手順を生成する。これにより先読み装置２１０は、当該先読み手順を生成した後にプログラム１０が実行されると、当該先読み手順に応じて適切に先読みを行うことができる。また、計測部２２４は、プログラム１０の各データ読み出しに対しては、読み出されたデータ量を合計値に加算する処理および合計値を基準データ量と比較する処理を行えばよい。また、プリフェッチ実行部２６９は、先読みの開始条件が満たされた場合に呼び出され、グループに属する１以上の先読みをまとめて実行する。これにより先読み装置２１０は、少ないオーバーヘッドで効率良く先読みを行うことができる。
【００４９】
なお、先読み装置２１０は、オペレーティングシステム２００内のバッファ３０を用いて先読みを行なう構成に代えて、先読み装置２１０内部にバッファ３０およびバッファ３０を管理するバッファ管理部を有する構成としても良い。この構成においては、プリフェッチ実行部２６９は、先読み処理において、オペレーティングシステム２００内のファイルキャッシュに格納することなく先読み装置２１０に対して対象データを返送するよう指示しても良い。また、先読み装置２１０内部に設けるバッファ管理部は、先読みした対象データをバッファ３０に記憶し、プログラム１０からのデータ読み出しに応じて対象データをプログラム１０に返送する。
【００５０】
図３は、本実施形態に係る先読み装置２１０の動作フローを示す。
まず、先読み手順を生成していない状態でプログラム１０が実行されると、履歴記録部２２２は、プログラム１０が実行中に発行したデータ読み出しの履歴をプロファイルとして記録する（Ｓ３００）。履歴記録部２２２は、プログラム１０がオペレーティングシステム２００に対して発行する、例えばファイル２０のオープン（ｏｐｅｎ）、クローズ（ｃｌｏｓｅ）、読み出し（ｒｅａｄ）、書き込み（ｗｒｉｔｅ）、ファイルのアクセスポインタの移動（ｌｓｅｅｋ）、およびオープンしているファイルの識別子の複製（ｄｕｐ２）等のハードディスクドライブ２０４０の入出力処理について、引数、戻り値、スレッド識別子、実行に要した時間等を履歴として記録してよい。また、本実施形態に係る履歴記録部２２２は、プログラム１０の複数の命令処理と、それぞれの命令処理に用いられるデータをそれぞれ読み出す複数のデータ読出処理とを実行したタイミングを履歴に記録する。すなわち例えば履歴記録部２２２は、プログラム１０がデータ読み出しを発行したタイミングと、オペレーティングシステム２００が当該データ読み出しに対しプログラム１０へデータを返送したタイミングとの間の期間をプログラム１０がデータ読出処理を実行した期間として履歴に記録する。そして、各データ読み出しが完了したタイミングから次のデータ読み出しが開始されるまでの間の期間を、直前に完了したデータ読み出しにより読み出されたデータを用いる命令処理の期間とみなして履歴に記録する。
【００５１】
次に、読出開始タイミング決定部２５７は、先読みを行わない状態でプログラム１０が実行された履歴から、先読みによりプログラム１０を効率良く実行した場合にそれぞれのデータ読出処理が開始されるべき読出開始タイミングおよびデータ読出処理が完了するべき読出完了タイミングを決定する（Ｓ３１０）。
【００５２】
次に、先読み生成部２３０は、履歴に記録された複数のデータ読み出しに対応する複数の先読みを生成し、先読み開始タイミング決定部２５９は生成されたそれぞれの先読みを開始するべき先読み開始タイミングおよび完了するべき先読み完了タイミングを決定する（Ｓ３２０）。次に、先読み最適化部２４７は、複数の先読みの実行順序を最適化する（Ｓ３３０）。
【００５３】
次に、分割部２５０は、先読み生成部２３０により生成され、順序決定部２４５により実行順序が決定された複数の先読みを、１以上の先読みを含む複数のグループに分割する（Ｓ３４０）。次に、先読み手順決定部２４０は、Ｓ３１０からＳ３４０までの処理により作成された先読み手順をハードディスクドライブ２０４０またはＲＡＭ２０２０等の記憶装置に記録する（Ｓ３５０）。
【００５４】
次に、先読み手順を生成した状態でプログラム１０が実行されると、当該プログラム１０と並行して先読みプログラムが実行される（Ｓ３６０）。これにより情報処理装置１９００は、先読み装置２１０としても機能し、プログラム１０のデータ読み出しに先立ってファイル２０からバッファ３０に対象データが先読みする。
【００５５】
図４は、本実施形態に係る先読み装置２１０におけるＳ３１０の処理を示す。
Ｓ３１０の前処理として、先読み生成部２３０は、履歴記録部２２２が記録した履歴を読み出し、履歴に記録された複数のデータ読み出しを時系列順に並べる。ここで先読み生成部２３０は、読み出しの対象となるファイル２０毎にデータ読み出しを時系列順に並べてよい。なお、本実施形態に係る先読み生成部２３０は、履歴記録部２２２が記録したデータ読み出しのうち、ハードディスクドライブ２０４０に対する読出命令が発行されないデータ読み出しを除外し、ハードディスクドライブ２０４０に対する読出命令が発行されるデータ読み出しについて上記の系列を作成する。すなわち、ハードディスクドライブ２０４０がクラスタ等のブロック単位でアクセスされる記憶装置である場合、先読み生成部２３０は、１または複数のファイル２０を記録した各ブロックのうち、既に読み出されたブロックからデータを読み出すデータ読み出しを除外し、未だ読み出されていないブロックからデータを読み出すデータ読み出しについて上記の系列を作成する。
【００５６】
次に、先読み生成部２３０は、上記の系列中の複数のデータ読み出しのそれぞれについて、当該データ読み出しの対象データを予め読み出す先読み処理を生成する。ここで先読み生成部２３０は、これら複数の先読み処理を、データ読み出しと同じ実行順序で並べておく。
【００５７】
次に、タイミング決定部２５５は、図４に示した処理により、複数の命令処理同士および複数のデータ読出処理同士がそれぞれ履歴に記録された順序で逐次実行されることを前提として、命令処理とデータ読出処理を並行して実行させた場合に各データ読出処理を実行するべきタイミング（時刻）を求める。ここでタイミング決定部２５５は、それぞれのデータ読出処理を開始すべき読出開始タイミングを、当該データ読出処理により読み出したデータを用いる命令処理を開始する前に当該データ読出処理を完了させ、かつ、当該データ読出処理を当該命令処理以前に実行される他の命令処理と並行に行わせることができる範囲内で、最も遅いタイミングに決定する。
【００５８】
より具体的には、タイミング決定部２５５は、図中４行目からの繰り返し処理により、先読み生成部２３０により生成された、複数の先読みを含む暫定的な先読み手順中の先頭の先読みから順に、図中の５行目から１３行目の処理を行う。タイミング決定部２５５は、５行目において、処理対象の先読みＰに対応するデータ読み出しの開始タイミングから先読みＰの直前の先読みに対応するデータ読み出しの完了タイミングＴｃｌｒを減じて、先読みＰの直前の先読みに対応するデータ読み出しにより読み出したデータを用いる命令処理に要する時間Ｔｃを求める。次に、タイミング決定部２５５は、６行目において、Ｔｃｌｒを、先読みＰに対応するデータ読み出しの完了タイミングに更新する。
【００５９】
次に、タイミング決定部２５５は、７行目において、データ読み出しの処理時間の合計値Ｔｒ＿ｔｏｔａｌに先読みＰに対応するデータ読み出しの処理時間を加えて更新する。次に、タイミング決定部２５５は、８行目から１３行目において、先読みＰに対応するデータ読み出しの最終読出完了タイミングを求める。より具体的には、タイミング決定部２５５は、前のデータ読み出しの完了タイミングＴ＿ｔｏｔａｌに、当該前のデータ読み出しにより読み出されたデータを用いる命令処理を行う時間Ｔｃを加えて、先読みＰに対応するデータ読み出しを用いる命令処理をＣＰＵ２０００が開始できるタイミングＴ＿ｔｏｔａｌ＋Ｔｃを求める。そして、タイミング決定部２５５は、このタイミングと、ハードディスクドライブ２０４０の読み出し速度の制約上先読みＰに対応するデータ読み出しを終えることができるタイミングＴｒ＿ｔｏｔａｌとを比較し、より後のタイミングを上記の最終読出完了タイミングとする。
【００６０】
以上の処理により、タイミング決定部２５５は、それぞれのデータ読み出しについて最終読出完了タイミングを求めることができる。タイミング決定部２５５は、それぞれのデータ読み出しについての最終読出完了タイミングと、履歴上における当該データ読み出しの処理時間とに基づいて、当該データ読み出しを開始する最終の読出開始タイミングを求める。
【００６１】
図５は、本実施形態に係る先読み装置２１０におけるＳ３２０の処理を示す。
先読み開始タイミング決定部２５９は、複数の先読み同士がそれぞれ逐次実行されることを前提として、複数のデータ読出処理のそれぞれについて、当該データ読出処理に対し先読み開始タイミング決定部２５９により決定された読出開始タイミングにおいて当該データ読出処理に対応する先読みが完了しているように複数の先読みの先読み開始タイミングを決定する。
【００６２】
より具体的には、先読み開始タイミング決定部２５９は、暫定的な先読み手順中の最後の先読みから順に遡って、当該先読みを開始すべき最終の先読み開始タイミングを決定していく。まず先読み開始タイミング決定部２５９は、２行目において、最後の先読みＰ０の先読み開始タイミングを、最後のデータ読出処理の最終読出開始タイミングから当該データ読出処理の処理時間を減じた値とする。これにより、先読みＰ０の完了後にデータ読出処理が開始されるので、プログラム１０の入出力処理待ちを最小にすることができる。
【００６３】
以下、繰り返し処理における処理対象の先読みＰについて、先読み開始タイミング決定部２５９は、６行目から１１行目において、後続の先読みの最終先読み開始タイミングＴ＿ｄｅａｄｌｉｎｅまたは当該先読みにより読み出したデータを用いるデータ読み出しの最終読出開始タイミングのうち、より前のタイミングから当該先読みＰに対応するデータ読み出しの処理時間を減じて、当該先読みＰの開始タイミングを決定する。
【００６４】
以上の処理により、先読み開始タイミング決定部２５９は、それぞれの先読みについての最終先読み開始タイミングを求めることができる。先読み装置２１０は、このタイミングを満たすようにそれぞれの先読みを順次発行することで、プログラム１０の入出力処理待ちを最小にしつつ、命令処理とデータ読出処理とを効率良く並列に処理させることができる。
【００６５】
図６は、本実施形態に係る先読み装置２１０におけるＳ３３０の処理を示す。順序決定部２４５内の先読み最適化部２４７は、２以上の先読みが、ファイル２０を記憶する記憶装置上の連続する２以上の領域のそれぞれからデータを読み出すことを条件として、当該２以上の先読みを、当該連続領域のデータをバッファ３０に先読みする１つの先読みに置き換える。これにより先読み装置２１０は、それぞれの先読みの最終先読み完了タイミングを満たす範囲で複数の先読みの実行順序を入れ替え、隣接する記憶領域に対する２以上の先読みを連続領域への１つの先読みに置換することができる。この結果、先読み装置２１０は、個別に先読みを行うのと比較して先読み処理の総時間を短縮し、ハードディスクドライブ２０４０からのデータ読み出しを最適化することができる。
【００６６】
Ｓ３３０において、先読み最適化部２４７は、Ｓ３２０の処理の結果得られる先読み手順の先頭の先読みから順に、先読みＰ１と、次の先読みＰ２とを選択していく（１、２、２３、および２４行目）。そして、最初の先読みの開始タイミングを０とし（２行目）、先読みＰ２が先読み手順の末尾の先読みとなるまで（４行目）、先読みＰ１の開始タイミングに当該先読みＰ１の処理時間を加えて次の先読みＰ２の開始タイミングを求めていく（２２行目）。
【００６７】
各先読みＰ１について、先読み最適化部２４７は、次に示す処理を行う。
まず、先読み最適化部２４７は、先読みＰ１の処理に用いてもよい空き時間ｆｒｅｅ＿ｔｉｍｅを求める（６行目から８行目）。この空き時間ｆｒｅｅ＿ｔｉｍｅは、先読みＰ１の開始タイミングから次の先読みＰ２の最終開始タイミングまでの間の時間、および、先読みＰ１の開始タイミングから先読みＰ１に対応するデータ読み出しが発行されるタイミングまでの間の時間のうち、より小さい値となる。
【００６８】
空き時間ｆｒｅｅ＿ｔｉｍｅが先読みＰ１の処理時間より大きいことを条件として、先読み最適化部２４７は、２以上の先読みを結合して１つの先読みに置換することを試みる（９行目）。すなわち、先読み最適化部２４７は、先読みＰ１により読み出されるハードディスクドライブ２０４０の領域およびハードディスクドライブ２０４０上で当該領域の前に位置する領域を１つの先読みにより読み出す処理時間ｌｏｗｅｒと、先読みＰ１により読み出されるハードディスクドライブ２０４０の領域およびハードディスクドライブ２０４０上で当該領域の後に位置する領域を１つの先読みにより読み出す処理時間ｕｐｐｅｒとを求める（１１から１２行目）。
【００６９】
次に、先読み最適化部２４７は、評価関数ｉｓＬｏｗｅｒＳｅｌｅｃｔｅｄおよび評価関数ｉｓＵｐｐｅｒＳｅｌｅｃｔｅｄにより、先読みＰ１に前の領域を読み出す他の先読みを結合すべきか、または先読みＰ１に後の領域を読み出す他の先読みを結合すべきかを評価する（１３行目、１５行目）。評価関数ｉｓＬｏｗｅｒＳｅｌｅｃｔｅｄは、処理時間ｌｏｗｅｒ、処理時間ｕｐｐｅｒ、および空き時間ｆｒｅｅ＿ｔｉｍｅを用いて、先読みＰ１の前の領域からデータを読み出す先読みＰａが先読み手順の後方に存在し、当該先読みＰａを先読みＰ１に結合して１つの先読みＰ１に置換することが有効であり、かつ置換後の先読みＰ１が空き時間ｆｒｅｅ＿ｔｉｍｅ以内に完了することを条件として、当該先読みＰａを先読みＰ１に結合すべきことを戻り値として示す。ここで、先読み最適化部２４７は、後の領域からデータを読み出す先読みＰｂも先読み手順の後方に存在する場合には、先読みＰａを先読みＰ１に結合した方が先読みＰｂを先読みＰ１に結合するより効果的であることを条件として、先読みＰａを先読みＰ１に結合して１つの先読みＰ１に置換することが有効である旨を示してよい。すなわち例えば、先読み最適化部２４７は、処理時間ｌｏｗｅｒが処理時間ｕｐｐｅｒより小さい場合、または処理時間ｌｏｗｅｒの方が処理時間ｕｐｐｅｒより元の先読みＰ１の処理時間に近い場合に、先読みＰａを先読みＰ１に結合することが有効である旨を示してよい。
【００７０】
先読み最適化部２４７は、評価関数ｉｓＬｏｗｅｒＳｅｌｅｃｔｅｄの処理により、前の領域に対する先読みＰａを先読みＰ１に結合すべきと判断すると、先読みＰａおよび先読みＰ１を結合して、１つの先読みＰ１に置換する（１４行目）。
【００７１】
評価関数ｉｓＵｐｐｅｒＳｅｌｅｃｔｅｄは、処理時間ｌｏｗｅｒ、処理時間ｕｐｐｅｒ、および空き時間ｆｒｅｅ＿ｔｉｍｅを用いて、先読みＰ１の後の領域からデータを読み出す先読みＰｂが先読み手順の後方に存在し、当該先読みＰｂを先読みＰ１に結合して１つの先読みＰ１に置換することが有効であり、かつ置換後の先読みＰ１が空き時間ｆｒｅｅ＿ｔｉｍｅ以内に完了することを条件として、当該先読みＰｂを先読みＰ１に結合すべきことを戻り値として示す。ここで、先読み最適化部２４７は、評価関数ｉｓＬｏｗｅｒＳｅｌｅｃｔｅｄと同様にして、前の領域からデータを読み出す先読みＰａも先読み手順の後方に存在する場合には、先読みＰｂを先読みＰ１に結合した方が先読みＰａを先読みＰ１に結合するより効果的であることを条件として、先読みＰｂを先読みＰ１に結合して１つの先読みＰ１に置換することが有効である旨を示してよい。
【００７２】
先読み最適化部２４７は、評価関数ｉｓＵｐｐｅｒＳｅｌｅｃｔｅｄの処理により、後の領域に対する先読みＰｂを先読みＰ１に結合すべきと判断すると、先読みＰｂおよび先読みＰ１を結合して、１つの先読みＰ１に置換する（１６行目）。
【００７３】
先読み最適化部２４７は、以上の処理により、先読みＰ１の前後の先読みをまとめて１つの先読みＰ１に置換していく。そして、先読み最適化部２４７は、更に前後の先読みを先読みＰ１に結合できなくなると結合処理を終え、次の先読みに対して上記の処理を進める（１０行目、１８行目）。
【００７４】
以上に示した処理により、先読み最適化部２４７は、隣接する２以上の領域からそれぞれデータを読み出す２以上の先読みを、これらの２以上の領域を含む連続領域のデータをバッファ３０に先読みする１つの先読みに置き換えることができる。この置き換えにおいて、先読み最適化部２４７は、２以上の先読みがファイル２０を記憶する記憶装置上の連続する２以上の領域のそれぞれからデータを読み出すものであること、および、当該２以上の先読みを当該連続領域のデータをバッファ３０に先読みする１つの先読みに置き換えてもいずれのデータ読出処理の完了タイミングも当該データ読出処理により読み出されたデータを用いる命令処理の開始タイミングより遅らせないことを条件とする。これにより先読み最適化部２４７は、プログラム１０の処理を遅延させることなく先読みを効率化することができる。
【００７５】
図７は、本実施形態に係る先読み装置２１０におけるＳ３４０の処理を示す。分割部２５０は、Ｓ３４０の処理により、順序決定部２４５により実行順序が決定された複数の先読みを１以上の先読みをそれぞれ含む複数のグループに分割する。
【００７６】
分割部２５０は、それぞれのグループについて、連続する１以上の先読みを順次当該グループに加えていき（２行目から１６行目）、生成したグループ毎に計測部２２４と同期をとるための情報を生成する（１７行目）。より具体的には、分割部２５０は、先読み手順の先頭の先読みを１番目のグループとし（２行目）、当該先読みと同一のグループとすべき後続の先読みを順次グループに加えていく。そして、分割部２５０は、次のグループとすべき先読みを検出すると、当該先読みを次のグループとして、同様に処理を続ける。
【００７７】
分割部２５０は、グループに次の先読みＰを加えるか否かを、以下のように判断する。まず分割部２５０は、先読みＰの前の先読みを完了するタイミングＴｐ＿ｃｕｒｒｅｎｔに、先読みＰの処理時間を加える。次に、分割部２５０は、先読みによるバッファ３０の使用量を求める。より具体的には、分割部２５０は、先読みＰ以前におけるバッファ３０の使用量に、先読みＰによりバッファ３０に新たに読み出されるデータ量を加え（７行目）、先読みＰが完了するまでにプログラム１０によりデータが読み出され、使用済みとなるデータ量を減じる（８行目）。これにより、分割部２５０は、当該使用量として、先読みによりバッファ３０に読み出され、プログラム１０によりバッファ３０から読み出されていないデータによるバッファ３０の使用量を求めることができる。
【００７８】
次に、分割部２５０は、次の先読みの最終開始タイミングより、計測部２２４およびプリフェッチ実行部２６９の同期に要する時間だけ前のタイミングＴ＿ｔａｒｇｅｔを求める（９行目）。このタイミングＴ＿ｔａｒｇｅｔは、次の先読みを次のグループに含めた場合に、計測部２２４が当該グループの実行開始を指示するべき最終タイミングとなる。また、分割部２５０は、先読みＰの後に最初にプログラム１０が発行するデータ読み出し処理のタイミングをＴ＿ｎｅｘｔＲｅａｄとする（１０行目）。そして、バッファ３０の使用量が予め定められた上限のしきい値を超えず、先読みＰが完了するタイミングＴｐ＿ｃｕｒｒｅｎｔが、次の先読みを開始するために計測部２２４がプリフェッチ実行部２６９を呼び出すべき最終タイミングＴ＿ｔａｒｇｅｔより前であり、かつ、当該タイミングＴ＿ｔａｒｇｅｔまでの間にプログラム１０からデータ読み出しが発行されることを条件として（１１行目）、次の先読みを次のグループの先頭となる先読みとする（１２行目）。これにより、分割部２５０は、バッファ３０の使用量が予め定められた上限値を超えないように複数の先読みを複数のグループに分割することができる。ただし、分割部２５０は、当該グループ分割が適切でない場合には、バッファ３０の使用量が上限値を超えるとしても次の先読みを当該グループに追加する。例えば、分割部２５０は、計測部２２４からプリフェッチ実行部２６９への呼び出しのオーバーヘッドにより次の先読みの開始が遅延し最終の先読み開始タイミングを満たせなくなる場合、または、次に計測部２２４がプリフェッチ実行部２６９を呼び出すべきタイミングまでの間にプログラム１０からデータ読み出しが発行されず、計測部２２４が動作できない場合には、次の先読みを当該グループに追加する。
【００７９】
次に、分割部２５０は、タイミング決定部２５５に図中１６行目のＳ３４５の処理を行わせ、プログラム１０が発行するいずれのデータ読み出しに応じて計測部２２４からプリフェッチ実行部２６９を呼び出し、次のグループに含まれる先読みを開始させるかを決定する。これによりタイミング決定部２５５は、バッファ３０の使用量が上限値を超えない範囲で、それぞれのグループについてグループ開始タイミングを決定することができる。さらにタイミング決定部２５５は、グループに最後に加えられた先読みが完了してから計測部２２４が次の先読みを実行させるべく先読みプログラム中のプリフェッチ部２６５を呼び出すまでの間に、プログラム１０からデータ読み出しが発行される旨の履歴が記録されていることを条件として、当該次の先読みを次のグループに加えることができる。
【００８０】
図８は、本実施形態に係る先読み装置２１０におけるＳ３４５の処理を示す。タイミング決定部２５５は、履歴記録部２２２が記録した履歴に基づいて、図７の処理により分割部２５０が決定した最後の先読みＰの完了後、最終タイミングＴ＿ｔａｒｇｅｔまでの間にプログラム１０から発行されるデータ読み出しを順に調査する（３行目、４行目）。そして、タイミング決定部２５５は、いずれのデータ読み出しに応じて計測部２２４からプリフェッチ実行部２６９に対して次のグループの先読みの開始を呼び出させるかを決定する。
【００８１】
分割部２５０は、各データ読み出しについて、当該データ読み出しにより使用され、使用済みとなるデータ量をバッファ３０の使用量から減じていく（６行目）。そして、タイミング決定部２５５は、バッファ３０の使用量が予め定められた下限値未満となる場合に、当該データ読み出しに応じて計測部２２４からプリフェッチ実行部２６９を呼び出して次のグループに含まれる先読みを開始させることを定める。これにより、タイミング決定部２５５は、それぞれのグループに対応するグループ開始タイミングを順次決定していく。なお、本実施形態に係るタイミング決定部２５５は、当該データ読み出しまでにプログラム１０が読み出しを要求したデータ量の合計値を、次のグループの実行を開始する開始タイミングを規定する基準データ量とする。
【００８２】
以上に示した分割部２５０およびタイミング決定部２５５によれば、複数の先読みを、各先読みの最終開始タイミングを満たすようにグループ化して、各グループの実行を開始すべきグループ開始タイミングを決定することができる。この決定において、タイミング決定部２５５は、バッファ３０の使用量が下限値未満となる場合に、先読みを開始すべきことを決定する。これにより先読み装置２１０は、先読みによりバッファ３０の使用量が増加することによりＲＡＭ２０２０の消費量が増加し、プログラム１０の実行性能が低下するのを防ぐと共に、先読みしたデータが不足してプログラム１０が入出力待ちとなるのを防ぐことができる。
【００８３】
図９は、本実施形態に係る先読み装置２１０においてＳ３５０の処理により記録される、プログラム１０毎の先読み手順の一例を示す。図９の先読み手順は、基準データ量テーブル９００、先読みグループテーブル９１０、１または複数の先読み手順テーブル９２０、およびファイル管理テーブル９３０を含むテーブルにより記述され、ＲＡＭ２０２０及び／又はハードディスクドライブ２０４０等の記憶装置に格納される。
【００８４】
基準データ量テーブル９００は、複数のグループのそれぞれについて、当該グループに属する先読みを開始するグループ開始タイミングを規定する。本実施形態において、タイミング決定部２５５は、それぞれのグループに対応して、プログラム１０が読み出しを要求したデータ量の合計値が当該グループについて定めた基準データ量を超えたことを条件として当該グループに含まれる先読みを開始することを決定する。そして、タイミング決定部２５５は、それぞれのグループに対応して定めた基準データ量を、基準データ量テーブル９００に格納する。
【００８５】
先読みグループテーブル９１０は、それぞれのグループに対応して、先読みコマンドの数と、先読みコマンドのパラメータを記憶する先読み手順テーブル９２０へのポインタを格納する。先読み手順テーブル９２０は、それぞれのグループに対応して設けられ、当該グループに含まれる１以上の先読みのそれぞれのパラメータを記述する。本実施形態に係る先読み手順テーブル９２０は、当該パラメータとして、先読みの対象となるファイル２０を識別するためのファイル識別情報、ファイル２０内での先読み対象となる領域の位置を示す情報、および、先読みするデータ量（サイズ）を示す情報を格納する。
【００８６】
ファイル管理テーブル９３０は、先読み手順テーブル９２０に格納されたファイル識別情報のそれぞれに対応するファイル２０を管理する。各ファイル２０は、ファイル管理テーブル９３０において、ファイル名、ファイルが記録されたパス名、およびファイル属性の組により管理される。
【００８７】
図１０は、本実施形態に係る情報処理装置１９００におけるＳ３６０の処理を示す。
情報処理装置１９００は、プログラム１０を実行することにより、プログラム１０に記述された複数の命令処理（Ｓ１００５）と、複数のデータ読み出し処理（Ｓ１０１０）とを交互に繰り返す（Ｓ１０００、Ｓ１０１５）。これにより情報処理装置１９００は、プログラム１０に記述された情報処理を行う。
【００８８】
先読み装置２１０内のデータ読出中継部２２０は、プログラム１０の処理によりデータ読み出しが発行される度に呼び出される。本実施形態に係る先読み装置２１０は、先読み手順決定部２４０により先読み手順が生成された後は、履歴記録部２２２による履歴の記録を行わないようにする。これにより一旦先読み手順を生成した後は、履歴の記録によりプログラム１０の実行性能が低下するのを避けることができる。なお、先読み装置２１０は、プログラム１０またはファイル２０が更新されたことを条件として、生成した先読み手順を消去し、履歴記録部２２２により再度履歴を記録させてもよい。
【００８９】
計測部２２４は、データ読み出しが発行されたことに応じて、プログラム１０が読み出しを要求したデータ量を合計値に加算していく（Ｓ１０２０）。そして、計測部２２４は、データ量の合計値が次に実行すべきグループに対応する基準データ量を超えたことを条件として、プリフェッチ部２６５を呼び出す（Ｓ１０２５：Ｙｅｓ、Ｓ１０３５）。この呼び出しは、一例としてプリフェッチ実行部２６９の動作を行う情報処理装置１９００上のプロセス又はスレッドに対してシグナルを送ることにより実現される。計測部２２４は、プリフェッチ部２６５の呼出し後、更に次のグループへ処理を移行する（Ｓ１０４０）。
【００９０】
Ｓ１０２５の条件を満たさなかった場合、またはＳ１０２５の条件を満たしＳ１０４０の処理を終えた場合、計測部２２４は、プログラム１０から受けたデータ読み出しをオペレーティングシステム２００へ転送し、オペレーティングシステム２００からプログラム１０へとデータを返送させる（Ｓ１０３０）。
【００９１】
プリフェッチ部２６５内のプリフェッチ実行部２６９は、情報処理装置１９００上において、プログラム１０および計測部２２４とは独立したプロセス又はスレッドとして動作する。プリフェッチ実行部２６９は、計測部２２４からの呼び出しに応じて、次に実行すべきグループに含まれる先読みを実行する。
【００９２】
プリフェッチ実行部２６９を実現するプログラムは、プログラム１０の起動時に起動され、プログラム１０と並行して実行される。プリフェッチ実行部２６９は、複数のグループのそれぞれを、最初のグループから順に処理する（Ｓ１０５０、Ｓ１０５５、Ｓ１０７５）。プリフェッチ実行部２６９は、各グループについて、まず、当該グループに含まれる１以上の先読みを実行する（Ｓ１０６０）。本実施形態に係るプリフェッチ実行部２６９は、情報処理装置１９００上で動作するオペレーティングシステム２００により実現されるバッファ３０に対し先読みを発行して、プログラム１０が発行するそれぞれのデータ読み出しの対象となるデータを予めキャッシュさせることにより先読みを実行する。そして、先読みの実行を指示されたグループについての先読みを終えると、処理をＳ１０６５に進める。
【００９３】
以上に代えて、プリフェッチ実行部２６９は、バッファ３０の使用量が少ないことを条件として、計測部２２４からの１回の呼び出しに対し、２以上のグループについて先読みを実行してもよい。より具体的には、プリフェッチ実行部２６９は、まず、計測部２２４の呼び出しを受けたことに応じてバッファ３０の使用量をオペレーティングシステム２００から取得する。そして、バッファ３０の使用量が予め定められた基準使用量未満であることを条件として、２以上のグループに含まれる先読みを順次実行する。これにより、先読み装置２１０は、バッファ３０の空き容量に応じて予め先読み処理を済ませ、より小さいオーバーヘッドでプログラム１０を実行させることができる。
【００９４】
また、プリフェッチ実行部２６９は、当該グループに含まれる先読みの対象となるデータが既にバッファ３０に登録されていると判断したことを条件として、当該グループに含まれる先読みを中止してもよい。より具体的には、プリフェッチ実行部２６９は、まず、グループ内の各先読みによりファイル２０からバッファ３０にデータを読み出すのに要した時間を計測する。次に、プリフェッチ実行部２６９は、少なくとも１つの先読みによりファイル２０からバッファ３０にデータを読み出すのに要した時間が予め定められた基準時間未満であることを検出したことを条件として、当該グループに属する先読みのうち、実行順序が当該先読みより後の先読みの実行を中止する。これにより、先読み装置２１０は、不要な先読みの発行を中止し、情報処理装置１９００の負荷を低減することができる。
【００９５】
Ｓ１０６０により最後のグループの先読みを終えた場合、プリフェッチ実行部２６９は、処理を終了する（Ｓ１０６５：Ｙｅｓ）。最後のグループの先読みを終えていない場合、プリフェッチ実行部２６９は、次のグループの先読みを指示する呼び出しを計測部２２４から受けるまで待つ（Ｓ１０７０）。
【００９６】
以上に示した先読み装置２１０によれば、プログラム１０が発行するデータ読み出しの履歴に基づいて、プログラム１０が使用するデータを予め適切に先読みすることができる。これにより、プログラム１０を変更することなくデータの先読みによりプログラム１０の処理性能を向上させることができる。
【００９７】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００９８】
例えば先読み装置２１０は、複数のプログラム１０のそれぞれに対応して図９に示した先読み手順を生成し、先読みを実行してもよい。すなわち、履歴記録部２２２は、複数のプログラム１０のそれぞれについて、当該プログラム１０が実行中に発行したデータ読み出しの履歴を記録する。先読み生成部２３０は、それぞれのプログラム１０について、履歴に記録された複数の読み出しに対応する複数の先読みを生成する。先読み手順決定部２４０は、それぞれのプログラム１０について、複数の先読みを必要に応じてグループ化して、複数の先読みの実行順序および開始タイミングを決定する。
【００９９】
そして、プリフェッチ部２６５内の先読み手順取得部２６７は、実行順序が決定された後にいずれかのプログラム１０が実行されたことに応じて、当該プログラム１０についての実行順序を取得する。プリフェッチ実行部２６９は、取得した実行順序により当該プログラム１０についての複数の先読みのそれぞれを実行する。
【０１００】
また、先読み手順決定部２４０は、プログラム１０として、複数のサブルーチン及び／又は関数を含むプログラム全体に対応して先読み手順を生成してもよく、これに代えて各サブルーチン及び／又は関数単位で先読み手順を生成してもよい。
【０１０１】
また、先読み装置２１０は、プログラム１０が実行される情報処理装置１９００とは別個の装置として実現されてもよい。例えば、先読み装置２１０は、データベースを管理する情報処理装置であるデータベースサーバ装置と、プログラム１０を動作させる情報処理装置であるアプリケーションサーバ装置との間に接続され、アプリケーションサーバ装置上で動作するプログラム１０からデータ読み出しに先立って、先読み装置２１０内に設けたバッファ３０に対象データを読み込んでもよい。
【０１０２】
また、先読み装置２１０は、各グループを実行する基準となる基準データ量を、前のグループを実行した後にプログラム１０が読み出したデータ量として定めてもよい。
【０１０３】
また、計測部２２４およびプリフェッチ実行部２６９は、同一のプロセス又はスレッドにより実現されてもよい。この場合、プリフェッチ実行部２６９は、先読みとして非同期のファイルデータ読み出しをオペレーティングシステム２００に発行し、処理をプログラム１０に戻してよい。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施形態に係る情報処理装置１９００のハードウェア構成の一例を示す。
【図２】本発明の実施形態に係る情報処理装置１９００の機能構成を示す。
【図３】本発明の実施形態に係る先読み装置２１０の動作フローを示す。
【図４】本発明の実施形態に係る先読み装置２１０におけるＳ３１０の処理を示す。
【図５】本発明の実施形態に係る先読み装置２１０におけるＳ３２０の処理を示す。
【図６】本発明の実施形態に係る先読み装置２１０におけるＳ３３０の処理を示す。
【図７】本発明の実施形態に係る先読み装置２１０におけるＳ３４０の処理を示す。
【図８】本発明の実施形態に係る先読み装置２１０におけるＳ３４５の処理を示す。
【図９】本発明の実施形態に係る先読み装置２１０においてＳ３５０の処理により記録される先読み手順を示す。
【図１０】本発明の実施形態に係る情報処理装置１９００におけるＳ３６０の処理を示す。
【符号の説明】
【０１０５】
１０  プログラム
２０  ファイル
３０  バッファ
２００  オペレーティングシステム
２０５  プログラム
２１０  先読み装置
２２０  データ読出中継部
２２２  履歴記録部
２２４  計測部
２３０  先読み生成部
２４０  先読み手順決定部
２４５  順序決定部
２４７  先読み最適化部
２５０  分割部
２５５  タイミング決定部
２５７  読出開始タイミング決定部
２５９  先読み開始タイミング決定部
２６５  プリフェッチ部
２６７  先読み手順取得部
２６９  プリフェッチ実行部
９００  基準データ量テーブル
９１０  先読みグループテーブル
９２０  先読み手順テーブル
９３０  ファイル管理テーブル
１９００  情報処理装置
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
2006260067.tif 000003
【図２】
2006260067.tif 000004
【図３】
2006260067.tif 000005
【図４】
2006260067.tif 000006
【図５】
2006260067.tif 000007
【図６】
2006260067.tif 000008
【図７】
2006260067.tif 000009
【図８】
2006260067.tif 000010
【図９】
2006260067.tif 000011
【図１０】
2006260067.tif 000012