A TLB (Translation Lookaside Buffer) is a cache in a processor to accelerate the translation of a virtual address to a physical address. Since the working set of application programs has been increasing rapidly, TLB reach - the maximum size of the memory mapped by a TLB - is failing to keep pace with it.
A TLB is a very expensive resource in a processor and it should operate in a high speed. Therefore, there are strong limitations in increasing the number of TLB entries.
Superpage approach was proposed to increase TLB reach without increasing the number of TLB entries. In a superpage TLB, a TLB entry can map a superpage which is several contiguous base pages. There are several strong requirements for using superpages, and they hinder the actual utilization. Two previous schemes, a partial-subblock TLB and the shadow memory were proposed to release the requirements. A partial-subblock TLB releases only a small portion of the requirements and also limits the superpage size. The shadow memory releases most of the requirements but introduces other serious problems.
This dissertation explores various schemes for supporting superpages efficiently and increasing actual utilization of superpages. First, this dissertation proposes a hybrid scheme which integrates the shadow memory and a partial-subblock TLB, thereby enjoying the benefits inherited from both sides.
The hybrid scheme has as high a superpage utilization as the shadow memory, and avoids most of the problems in the shadow memory by virtue of the partial- subblock TLB. The hybrid scheme inherits most of the hardware cost and overhead from both schemes. However, the evaluation shows that the performance gain
overwhelms the cost and overhead.
Second, this dissertation introduces a new TLB structure, called VS-TLBs. They are based on subblock TLBs and add the subblock size field. By virtue of the subblock size field, a subblock in VS-TLBs can be multiple pages, while a subblock in the subblock TLB is fixed at a base page. Thus, VS-TLBs have a much larger TLB reach than subblock TLBs with the cost of a small number of additional bits.
Finally, this dissertation proposes VS-hybrid which changes the partial- subblock TLB in the hybrid scheme to a partial VS-TLB. VS-hybrid supports multi-page subblocks in the hybrid scheme. Therefore, it takes both advantages of the hybrid scheme and the expanded subblock size. VS-hybrid has a considerable performance gain additionally from the hybrid scheme though. Thus, VS-hybrid shows the best performance among the schemes.
We proposed three schemes having different pros and cons in this dissertation.
They have different cost and performance trade-offs. VS-hybrid needs the strongest supports but it guarantees the best performance. VS-TLBs require only a small change in TLB structure. There is the hybrid scheme between VS-TLBs and VS-hybrid in the spectrum of cost and performance trade-offs.
티엘비는 프로세서 내부에 존재하는 가상 주소를 물리 주소로 변환을 빠르게 하는데 사용되는 캐쉬이다. 응용 프로그램의 크기가 급속히 증가함에 따라 티엘비의 용량 증가 속도가 이를 따라갈 수 없는 추세이다. 이는 티엘비가 프로세서의 내부에 존재하고 또한 굉장히 고속으로 동작해야 하기 때문에 티엘비의 엔트리의 갯수를 늘리는 것이 비용이 많이 들기 때문이다.
수퍼페이지 방법은 티엘비 엔트리의 갯수를 늘리지 않고도 티엘비의 용량을 증가시키는 방법이다. 수퍼페이지 티엘비에서는 하나의 엔트리가 여러개의 연속된 기본 페이지가 합쳐진 수퍼페이지를 매핑시킬 수 있어서 티엘비의 용량이 증가하게 된다. 하지만 수퍼페이지를 사용하기 위해서는 여러가지 강력한 조건들을 만족시켜야 하고, 이러한 조건들 때문에 수퍼페이지가 충분히 활용되지 못하는 단점이 있다.
이러한 조건들을 완화시키기 위해서 부분 서브블록 티엘비 (partial-subblock TLB)와 셰도우 메모리 (shadow memory) 방법이 제안되었다. 부분 서브블록 티엘비의 경우는 위의 조건들 중에서 일부만을 완화시킬 수 있고, 또한 수퍼페이지의 크기를 제한하는 단점이 있다. 셰도우 메모리의 경우 위의 조건의 대부분을 완화시키지만, 반면 새롭게 여러 심각한 문제를 야기시킨다.
본 논문은 수퍼페이지를 효과적으로 지원하고 수퍼페이지의 실제 사용량을 증가시킬 있는 여러가지 방안들을 제안한다. 첫째로 셰도우 메모리와 부분 서브블록 티엘비를 결합하는 혼합형 방안 (hybrid scheme)을 제안한다. 혼합형 방안은 양쪽의 장점을 모두 가지게 되는데, 셰도우 메모리와 거의 동일한 수퍼페이지의 높은 활용도를
가진다. 뿐만 아니라 부분 서브블록 티엘비 덕분에 원래 셰도우 메모리가 단독으로 쓰였을 때 발생하는 심각한 문제점들이 해결되어진다. 혼합형의 경우 두 가지 방안을 동시에 쓰기 때문에 비용이 증가하는 단점이 있다. 하지만 실험 결과는 두 가지를
동시에 씀으로서 발생하는 성능 향상이 비용 증가를 훨씬 상회한다는 것을 보여주고 있다.
둘째로 본 논문은 VS-TLB라고 하는 새로운 티엘비 구조를 제안한다. VS-TLB는 서브블록 티엘비를 바탕으로 서브블록 크기 (subblock size)라는 새로운 필드를 각 엔트리마다 추가시킨다. 이 새로운 필드 덕분에 기존의 서브블록 티엘비에서는 서브 블록의 크기가 하나의 기본 페이지로 한정되어 있었지만 VS-TLB에서는 복수 페이지 (multiple pages)가 될 수가 있다. 따라서 추가되는 필드를 위한
몇 개의 비트라는 적은 비용으로 티엘비의 용량이 대폭 증가하는 효과가 발생하게 된다.
마지막으로 본 논문은 앞서 제안한 혼합형 방안에서 부분 서브블록 티엘비를 부분 VS-TLB (partial VS-TLB)로 바꾸는 새로운 혼합형 방안를 제안하고 이를 VS-hybrid라고 명명한다. 이렇게 함으로써 혼합형 방안에서 서브블록의 크기가 하나의 기본 페이지로 한정되어 있던 것이 복수 페이지로 대폭 확장됨으로써 혼합형 방안의 티엘비 용량이 대폭 증가하게 된다. VS-hybrid는 기존 혼합형 방안의 장점을
그대로 가지면서도 동시에 확장된 서브블록의 장점도 동시에 누리게 됨으로써 이때까지의 수퍼페이지 지원 방안중에 가장 뛰어난 성능을 보인다.
본 논문에서 우리는 각각 장단점이 다른 세가지 방안을 제안하고 있다.
각각은 서로 다른 비용과 성능에 대한 트레이드오프를 가지고 있다.
VS-hybrid의 경우 가장 비용이 많이 들긴 하지만, 그에 반해 가장 좋은 성능을 보장해 준다. VS-TLB는 서브 블록 티엘비에 작은 추가만 필요로 한다.
혼합형 방안 (hybrid scheme)은 비용이나 성능면에 있어서 이들 두 방안 사이에 존재하게 된다.
