1

私のHacker's Delightのコピーは家にあり、私が見つけたWebリソースはこの詳細について明確ではありません.

よく知られている「行と列の正方形」アルゴリズムを使用して、次の 8 レベルの LRU を作成しました。（もっと良い名前はありますか？）。

#include <stdint.h>

typedef union {
  uint8_t rows[8];  
  uint64_t cols;
} lru_state;

void lru_init(lru_state *this) {
  this->cols=0;
}

void lru_up(lru_state *this, int used /* in 0..7 */) {
  this->rows[used]=0xff;
  this->cols &= ~(0x0101010101010101 << used);
}

int lru_get(lru_state *this) {
  int i;
  for (i=1; i<8 ; i++) {
    if (0==(this->rows[i])) return i;
  }
  return 0;
}

最も使用頻度の低い行はすべてゼロになるという私の仮定の確認をお願いします。うまくいくようですが、満足のいくものであることを証明する数学がありません。

それで、これは正しいですか？または、各行の最小ハミング重みを計算する必要がありますか?

4

1 に答える 1

1

あなたの仮定は正しいです。

矛盾によって証明できます。

LRU 候補 (最もゼロのビットが多いバイト) が c で、位置 x にビットが設定されているとします。

これは、行 x が行 c の後に使用されていないことを意味します。したがって、x には、c が持つすべてのゼロ ビットと、位置 x のゼロが含まれている必要があります。c はゼロ ビットが最も多いバイトであるため、これは矛盾しているため、c にビットを設定することはできないと結論付けます。

于 2013-11-21T22:40:57.660 に答える