LRU square 알고리즘에서 가장 적게 사용 된 행은 항상 0입니까?

Hacker 's Delight의 내 복사본은 집에 있으며, 내가 찾은 웹 리소스는이 세부 사항에 명확하지 않습니다.LRU square 알고리즘에서 가장 적게 사용 된 행은 항상 0입니까?

잘 알려진 "행 - 열 사각형"알고리즘을 사용하여 다음 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; 
}

내가 가장 최근에 사용 된 행이 모두 0이 될 것이라고 내 가정의 확인을 부탁

. 그것은 효과가있는 것으로 보이지만 나는 그것을 만족스럽게 증명할 수학적 지식이 없습니다.

그럼,이게 맞습니까? 아니면 각 행에 대한 최소 해밍 웨이트를 계산해야합니까?

출처

2013-11-21 markrages

참고 :'lru_get()'의 for 루프는'rows [0]'을 테스트하지 않습니다. 이것이 당신의 의도입니까, 아니면 당신이 고용하기를 희망하고 있습니까? – chux

나는 그저 넘어져있게 내버려 둔다. 이 질문에 대한 대답에 따라 루프로 넘어 가게됩니다. – markrages

내 2 센트의 전문 지식 : 당신의 주장에 동의하십시오. 이식성 문제 : 일부 컴퓨터는 크거나 작은 엔디안이며 기능에 영향을 미칩니다. 좋은 컴파일러는'uint64_t FF = 0xff; cols | = FF << (used * 8);와'rows [used] = 0xff; '를 비교하여 합집합의 필요성을 없앴습니다. – chux

귀하의 가정은 정확합니다.

우리는 모순 증명할 수

는 LRU 후보 (대부분 제로 비트 바이트)를 가정하는 것은 C이고, x 위치에 설정된 비트를 갖는다.

이것은 라인 c가 라인 c 다음에 사용되지 않았 음을 의미하므로 x는 c의 모든 제로 비트와 위치 x에 0을 더한 값을 가져야합니다. 이것은 c가 가장 0 비트를 갖는 바이트이기 때문에 모순이다. 따라서 우리는 c가 어떤 비트 세트도 가질 수 없다고 결론 내린다.

출처

2013-11-21 22:40:57

LRU square 알고리즘에서 가장 적게 사용 된 행은 항상 0입니까?

답변

관련 문제