캐싱 이론

캐싱의 통합 이론이 있습니까? 즉, 캐시 구성 및/또는 최적화를위한 정리 및 알고리즘 모음이 있습니까?캐싱 이론

질문은 의도적으로 광범위합니다. 내가 찾고있는 결과가 광범위하기 때문에. 달성 가능한 속도 향상을위한 수식, 캐싱 알고리즘에 대한 메트릭 등. 대학 수준의 교과서가 아마도 이상적 일 것입니다.

2009-06-17 Jørgen Fogh

캐시 적중이 캐시 누락보다 훨씬 빠르다 고 생각할 수 있다면 초과 사용시 캐시 미스가있는 경우에도 캐시를 사용하면 캐시를 사용하지 않는 것보다 빠르거나 빠를 수 있습니다.

는 수학은 아래를 참조하십시오 :

AverageTime = Infinity*TimePerHit/Infinity - #CacheMisses*TimePerHit/Infinity + #CacheMisses*TimePerMiss/Infinity

Number of hits = NumRequests - #CacheMisses 

AverageTime = ((NumRequests-#CacheMisses) * TimePerHit + #CacheMisses * TimePerMiss)/NumRequests

우리는 다음 NumRequests 무한대라고 가정하면 (이것은 제한 문제는, 미적분을 두려워하지 않음), 우리는이를 볼 수 있습니다 #CacheMisses와

두 용어는 0이되지만 전체 방정식을 해결합니다

AverageTime = TimePerHit

이 부여 요청 수가 무한대 인 경우이지만 캐시를 사용하여 시스템의 속도를 높이는 방법을 알 수 있습니다.

출처

2009-06-17 11:23:00 samoz

귀하의 계산은 매우 좋아 보인다. 불행히도 이것은 캐시 미스의 수가 상수라는 가정을 암시합니다. 이는 거의있을 법하지 않습니다. 올바른 숫자는 다음과 같습니다. HitProbability * TimePerHit + (1 - HitProbability) * TimePerMiss –

나는 수학이 약간 iffy라는 것을 알고 있습니다. 이것은 내가 지난 가을에 수강 한 수업을 배워야한다는 증거이며, 나는 그곳에서 그것을 되찾기 위해 노력했다. CacheHits 대 CacheMisses가 있기 때문에 귀하의 요점을 주소 지정, 이것은 비율, 그래서 hit 확률을 사용하여 같은 일이 wouldnt? – samoz

아닙니다. 캐시 미스의 일정한 0이 아닌 확률이 있다고 가정하면, 무한한 시도가 수행되면 무한히 많은 미스가 발생합니다. 캐시가 요청 된 모든 데이터를 저장할 수있을만큼 큰 경우 수식이 정확합니다. 그런 다음 누락 횟수에 상한선이 있습니다. –

실제 캐싱의 대부분은 "80-20 규칙"또는 Pareto distribution을 사용합니다. 보이는 방법은 아래를 참조하십시오

이 같은 응용 프로그램에서 자체 명단

Pareto distribution

런타임의 대부분은 (유효 CPU에서 코드 캐시를 만드는) 동일한 코드 조각에 소요되는

종종 변수가 액세스 될 때 곧 다시 액세스됩니다 (CPU의 데이터 캐시를 효과적으로 만듭니다)
브라우저가 웹 사이트의 호스트 이름을 한 번 조회하면 가까운 장래에 자주 액세스하게됩니다 (m aking DNS 캐시가 효과적입니다.)

따라서 캐싱 이론은 가장 활동적인 반복 작업을 보완하기 위해 일반적으로 "희소하지만"빠른 몇 가지 추가 리소스를 사용하는 것입니다. 할거야.

이렇게하는 이유는 위의 매우 비뚤어진 차트를 기반으로 "느리게"작업을 수행하는 횟수를 "수평으로"줄이려고하기 때문입니다.

출처

2009-06-22 22:26:37

내가 찾고있는 주제 인 것 같아서 online algorithms, 으로 나를 가르키는 나의 학교의 교수 중 한 사람과 이야기했다.

캐싱 알고리즘과 페이지 교체 알고리즘 간에는 많은 부분이 중복됩니다. 이 주제에 대해 더 많이 알게되면이 주제에 대한 WikiPedia 페이지를 편집하여 연결을 명확히 할 것입니다.

출처

2009-07-06 13:36:25

답변

관련 문제