shttl

dst/仕様/ライブラリ/shttl.md

概要

• ハードウェア構造のテンプレートライブラリ
• 各クラスの構造は基本的に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