Shared memory multiprocessors in which each processor has its own TLB must manage consistency among TLBs and a page table. As the large-scale CC-NUMA (cache-coherent non-uniform memory access) shared memory multiprocessors be-come popular, it is important for TLB consistency management algorithms to be highly scalable.
In this paper, I propose a TLB update-hint algorithm as a scalable TLB consistency management solution for CC-NUMA multiprocessors. By using a lazy TLB invalidation approach, I reduced the number of unnecessary processor interruptions and idle-waiting time, and achieved a high level of scalability.
Using a shared memory simulator, I evaluated the TLB update-hint algorithm. For performance comparison, I also simulated the TLB shootdown algorithm, one of the most popular TLB consistency algorithms. The simulations demonstrated that the TLB update-hint algorithm scales well in systems with a large number of processors. At 64 node systems, the TLB update-hint algorithm shows 47~87% better performance than the TLB shootdown algorithm.
처리기가 주소를 변환하기 위해 매번 메모리 안의 페이지 테이블을 접근해야 한다면 메모리 트래픽 (traffic)이 너무 많아지게 된다. 그러므로 대부분의 메모리 관리 유닛 (MMU)은 최근의 주소 변환을 케시해 두는 티엘비 (translation lookaside buffer, TLB)를 포함한다. 티엘비는 하드웨어로 구현되고, 적은 수의 항 (entry) (전형적으로 64에서 256)으로 구성되어 있다. 각 항은 가상 페이지를 물리적 페이지로 맵한다. 메모리 관리 유닛은 매 주소 변환 연산마다 이 캐시를 검사한다. 만약 캐시에서 변환을 찾으면, 접근 비용이 비싼 메모리내의 주소 변환 맵을 찾아 볼 필요가 없다.
공유 메모리 (shared-memory) 다중프로세서 (multiprocessors) 에서 티엘비의 일관성 (consistency)을 유지하는 것은 훨씬 복잡한 문제이다. 모든 처리기들이 비록 메인 메모리를 공유하지만, 각자는 자신의 티엘비를 따로 갖고 있다. 한 처리기가 다른 처리기에서 활성 상태인 페이지 테이블의 한 항을 바꿀 때 문제가 발생한다. 후자의 처리기는 그 항의 복사본을 자신의 티엘비에 가지고, 따라서 이미 낡은 매핑을 계속 사용할 수 있다. 그 페이지 테이블을 사용하고 있는 모든 처리기의 티엘비로 변경을 전달하는 것이 필수적이다.
티엘비 격추 (TLB-shootdown) 알고리즘은 티엘비 일관성을 유지하는 방법으로 가장 널리 사용되고 있는 방법이다. 그것은 티엘비 격추 알고리즘이 구현이 쉽고 거의 모든 하드웨어 환경에서 사용가능할 정도로 일반적인 방식이기 때문이다. 하지만 티엘비 격추 알고리즘은 많은 수의 다중프로세서 시스템에서는 확장성이 부족한 문제점을 가진다. 캐시일관성을 지원하는 누마 (CC-NUMA) 다중프로세서가 널리 사용됨에 따라서, 확장 가능하게 티엘비의 일관성을 유지하는 알고리즘이 중요해지고 있다.
이 논문에서는 캐시일관성을 지원하는 누마 다중프로세서에 대해서 확장 가능하게 티엘비의 일관성을 유지하는 방법인 티엘비 갱신 힌트 (TLB update-hint) 알고리즘을 제안한다. 게으른 (lazy) 티엘비 무효화 (invalidation)를 사용하여 불필요한 프로세서간 인터럽트와 유휴 상태 시간 (idle-waiting time)의 수를 줄일 수 있어서 높은 확장성을 달성할 수 있다. 케쉬일관성을 지원하는 누마의 케쉬 무효화/청소 (flush) 방법과 디렉토리 제어기 (controller)를 사용해서, 페이지 테이블의 변화를 알려주는 방법과 잘못된 접근을 발견하는 방법을 구현했다. 티엘비 무효화에 대해서 프로세서간의 인터럽트를 실제로 티엘비를 사용하는 순간까지 연기함으로써 불필요한 프로세서간 인터럽트의 수를 줄였다. 티엘비 일관성을 위한 공지 (notification)를 보내는 때와 티엘비를 무효화하는 때를 분리함으로써 분주한 대기 (busy-waiting) 시간을 줄일수 있었다.
공유 메모리 시물레이터를 사용하여 티엘비 갱신 힌트 알고리즘을 구현하였다. 이 논문에서는 또한 성능 비교를 위해서 가장 널리 사용되는 티엘비 일관성 알고리즘 중 하나인 티엘비 격추 알고리즘을 구현하여 실험하였다. 시물레이션 결과 티엘비 갱신 힌트 알고리즘은 많은 수의 프로세서를 사용하는 시스템에서 잘 동작했다. 64 노드 시스템에서 티엘비 갱신 힌트 알고리즘은 티엘비 격추 알고리즘에 비해서 47~87% 의 더 좋은 성능을 보이는 것을 확인했다.
