仕様/ライブラリ/shttl

Table of Contents

概要 定義 SHTTL_DISABLE_DEBUG SHTTL_DEBUG コレクション array2d counter_array shttl_bitset sd_container sd_srray sd_list xbitset テーブル directmap_table table setassoc_table ハッシュ hasher simple_hasher std_hasher static_off_hasher double hasher 要素 counter リプレースアルゴリズム replacement sd_replacement,sd_replacement_array replacement_array lru,lru_array nlu,nlu_array ユーティリティ shttl_types.h shttl_integrity_test.h bit.h integer.h その他 破棄 アライメント設定が追加で必要なもの

概要 †

• ハードウェア構造のテンプレートライブラリ
• 各クラスの構造は基本的にSTLを踏襲
  • iteratorの構造やメソッド名，アロケータなど

定義 †

SHTTL_DISABLE_DEBUG †

定義されているとSHTTL_DEBUGの定義を行わない．

SHTTL_DEBUG †

• 定義されていると，各種のアサートやチェックが有効化される．
• デフォルトで定義される
• 定義が外されると，tableやreplacementなどの純粋仮想関数は取り除かれる
  • これらは派生クラスでの定義を義務付けるためだけに存在するため，

コレクション †

array2d †

可変長二次元配列（初期化時のみサイズ指定可能）

• ファイル
  • array2d.h

• 使用例

  array2d<int> a(row,col);
  a[0][0] = 0;

• コンストラクタ，デストラクタ
  • array2d (const size_type r, const size_type c, const T &t=T())

  • array2d ()

• イテレータ
  • const_iterator begin () const
  • const_iterator end () const
  • iterator begin ()
  • iterator end ()

• サイズ
  • size_type size () const throw ()
  • size_type max_size () const throw ()

• 参照
  • const const_iterator operator[] (const size_type r) const
  • iterator operator[] (const size_type r)

counter_array †

カウンタの配列

• ファイル
  • counter_array.h

• 使い方

  counter_array<u8> c(3,3); // 3bitカウンタを3つ（カウンタ本体はu8型として確保）
  counter<u8> ci = c[0];
  ci++;
  ci.dec();

• 実装
  • カウンタそのものはcounter_arrayの中で，生データの配列として保持している
  • counterはそのポインタを受け取り，操作を提供する
  • 指定した型よりも大きなビット数を指定すると例外を投げる

shttl_bitset †

stl互換の軽量bitset

• ファイル
  • bitset.h

• 指定した型を値として保持することにより，軽量化
  • 現状，構造体が勝手に8バイトアラインされるため効果はない

    template<size_t N, class T = u64>
    class shttl_bitset

• stlのbitsetを上書きしている部分は破棄

sd_container †

共有データ付きコンテナのベース

• ファイル
  • sd_container.h
  • sd_ref.h

• 目的：容量をケチりたい
  • コンテナ内で共通のデータをオブジェクトから切り離し，コンテナ側で保持．
  • ex. セット連想キャッシュのway数とか．（全てのセットで共通）
  • ナイーブに実装すると 共通データのコピーを全てのオブジェクトが持つ

• 実装
  • コンテナ内で，共有データと個別データに分けて保持し，それらに対する操作を行うクラスを別に定義する
  • 共有データと個別データは，このコンテナの要素にアクセスする際に動的にバインドされる

• 使い方：コンテナに格納するクラスを特殊な方法で定義しておく
  • 共通データ
  • 個別データ
  • コンテナ要素クラス
    • sd_ref<shared_data,private_data>を継承
    • あるいは，sdとpdの参照をコンストラクタで受け取るクラスを定義

struct shared_data
{
   int size;
};

struct private_data
{
   int data;
};

class A : public sd_ref<shared_data, private_data>
{
public:
  A(shared_data& sd, private_data& pd) : 
    sd_ref<shared_data, private_data>(sd,pd)
  {
  }
};

sd_srray †

共有データ付き配列

• ファイル
  • sd_container.h

sd_list †

共有データ付き配列

• ファイル
  • sd_container.h

xbitset †

shttl_bitsetにfindを追加したもの．

• ファイル
  • xbitset.h

• find(value, start_pos)
  • start_posビット目から，上位に向かってvalueの出現位置を探索する
  • サイズが3以下の場合は，find(0,0)は特殊な高速版が使用される
  • find(0,0)は，下位0ビット目から連続してビットが立っている数を数える操作に相当

テーブル †

directmap_table †

ダイレクトマップなテーブル

• ファイル
  • directmap_table.h

table †

各種テーブルの基底

• ファイル
  • table.h

setassoc_table †

セットアソシアティブなテーブル

• ファイル
  • setassoc_table.h

ハッシュ †

hasher †

ハッシュの基底

• ファイル
  • hasher.h

simple_hasher †

値をそのまま返すハッシュ

• ファイル
  • simple_hasher.h

std_hasher †

基本的なハッシュ機構の実装．インデックスとオフセットのビット長を動的に指定．

• ファイル
  • std_hasher.h

• 使い方

  std_hasher<u32> hash(4,2); // インデックスは4bit，オフセットは2bit
  
  u32 index = hash.index( addr );
  u32 tag   = hash.tag  ( addr );

static_off_hasher †

オフセット長をテンプレート引数で指定．それ以外はstd_hasherと同じ

• ファイル
  • static_off_hasher.h

double hasher †

pairを受け取るハッシュ機構?

• index計算の際，secondでxorを取る

  return ((p.first >> off_bit()) ^ p.second) & idx_mask();

• ファイル
  • double_hasher.h

• 使い方

  double_hasher hash(4); // インデックスは4bit
  pair<u32,u32> addr;
  u32 index = hash.index( addr );
  u32 tag   = hash.tag  ( addr );

要素 †

counter †

カウンタ

• ファイル
  • counter.h

• counter_array中の要素を扱う際に用いられる
  • 詳細はcounter_arrayを参照

• メソッド
  • 上限や下限を超えた場合
    • operator--,operator++ 飽和させる
    • inc(),dec 例外を投げる

リプレースアルゴリズム †

replacement †

リプレースアルゴリズムの基底．派生クラスで定義するべきメソッドの規定と定数の定義．

• ファイル
  • replacement.h

sd_replacement,sd_replacement_array †

sd_containerを使用したreplacementのベースクラス．lruやnluで使用．

• ファイル
  • sd_replacement.h

replacement_array †

リプレースアルゴリズムの配列の基底．派生クラスで定義するべきメソッドの規定と定数の定義．

• ファイル
  • replacement.h

lru,lru_array †

LRUアルゴリズム

• ファイル
  • lru.h

nlu,nlu_array †

NLUアルゴリズム

• ファイル
  • nlu.h

ユーティリティ †

shttl_types.h †

基本型の定義

shttl_integrity_test.h †

SHTTLライブラリの動作チェックルーチン

bit.h †

ビットマスクや符号拡張など

integer.h †

• 与えたビットサイズに対し，それが収まる最小の整数型を定義する

その他 †

破棄 †

• 実装が不完全なため，一旦破棄
  • bit_vector
  • bitset_table
  • xbitset_array
  • lru_array

• boost内に同等のものが存在
  • mdarray
    • これ自体，実装がバグってる

• fifo
  • そもそもfifoによるリプレースアルゴリズム自体が不明
  • 実装も意味不明

アライメント設定が追加で必要なもの †

構造体の配置設定を追加しないと，狙い通りに機能しない（改修予定）

• shttl_bitset
• counter
• integer