局所性の分類
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/14 14:36 UTC 版)
参照の局所性には以下の3種類が存在する。 時間的局所性 （英: temporal locality） ある時点で参照されたリソースが近い将来にも再び参照される可能性が高いことを表す概念 空間的局所性 （英: spatial locality） あるリソースが参照されたとき、その近傍のリソースが参照される可能性が高いことを表す概念 逐次的局所性 （英: sequential locality） メモリが逐次アクセスされるという概念 これらの概念が真となるかどうかは、プログラムの作成方法に依存する。一般に関連するデータ群はメモリ内の近い位置に格納される。情報処理の一般的なパターンとして、ある項目を処理したら次へというように逐次的に処理が行われる。これが意味するのは、多くの処理をする場合に1つの項目に複数回アクセスすることになり、それによって時間的局所性が生じるということである。さらに次の項目に移るということは次の項目を参照するということであり、メモリ上の配置がまとまっていれば空間的局所性も生じる。 参照の局所性を増大させて利用することは最適化の一般的な技術である。これはメモリ階層の各レベルで行われている。ページング方式は空間的局所性を利用している。キャッシュは時間的局所性を利用している。キャッシュメモリは高速だが容量が小さいため、最近アクセスしたデータ(あるいはコード)とその近傍のみを格納することで大幅にシステム性能を向上させている。キャッシュ上のデータ群は必ずしも主記憶上で空間的に近いわけではなく、キャッシュラインという小さな単位でキャッシュに格納される。つまり、キャッシュラインのサイズを考慮するとここでも空間的局所性が利用されており、ある参照データのごく近い位置(同一キャッシュライン内)にあるデータが同時にキャッシュに置かれることで性能向上に寄与している。時間的局所性は最も基本的なレベルでも重要であり、最近の参照の結果はレジスタに保持される。また、ファイルシステムにおいても参照の局所性を利用した最適化が行われることがある。あるファイルの一部をリードしたプログラムはその続きをリードする可能性が高いため、最初のリード時に要求よりも大きめの単位で読み込んでおくといった空間的局所性を利用した最適化である。
※この「局所性の分類」の解説は、「参照の局所性」の解説の一部です。
「局所性の分類」を含む「参照の局所性」の記事については、「参照の局所性」の概要を参照ください。
- 局所性の分類のページへのリンク
