A cache memory system reduces memory access latencies by storing frequently used data in a fast storage whose size is usually much smaller that that of the main memory. As the speed of a processor increases, it becomes more difficult to design a cache memory that can satisfy the memory requests generated from the fast processor. Addressing cache memory by virtual addresses effectively reduces the cache access time by eliminating the time needed for address translation. The focus of this thesis is to propose virtual cache architectures to reduce the memory access latencies under diverse system architectures, i.e., on fast single processor systems, on shared memory multiprocessors. To achieve this purpose, we investigate the design issues and analyze problems concerned with performance of the virtual caches for those architectures. Then, we have developed three virtual cache schemes as follows in order to overcome the problems caused to be performance constraints.
First, due to the fast cache access time, on-chip direct-mapped virtual caches are popular in fast single processor systems. A direct-mapped cache takes less time for accessing data than a set-associative cache because the time needed for selecting a cache line among the set is not necessary. The hit ratio of a direct-mapped cache, however, is lower due to the conflict misses caused by mapping multiple addresses to the same cache line. In order to solve the above problem, we propose a new virtual cache architecture whose access time is almost the same as the direct-mapped cache while the hit ratio is the same as the set-associative caches. The entire cache memory is divided into n banks, and each process is assigned to a bank. Then, each process runs on the assigned bank, and the cache behaves like a direct-mapped cache. A victim for cache replacement is selected from those that belong to a process which is most remote from being scheduled. Trace-driven simulations confirm that the new scheme removes almost as many conflict misses as does the set-associative cache, while cache access time is similar to a direct-mapped cache.
Second, two-level caches are popular in high performance multiprocessors because the cache at the first-level provides data very fast while the one at the second-level enables high hit ratios. Since the virtual cache makes the cache access time fast, it is adequate for the design of the first-level cache. However, the cache coherence problem in shared memory multiprocessors imposes difficulty in designing two-level cache. It makes the virtual cache complicate, and this complexity will reduce the potential of the virtual cache to match the timing requirements of fast processors. To overcome this drawbacks, we propose a new multi-level cache architecture, where the first-level cache is decomposed into on-chip two-level virtual-physical caches. Unlike other schemes, a virtual-addressed cache and a physical-addressed cache are incorporated into the same first-level data cache. The instruction cache uses virtual addresses to access data in a cache. Meanwhile, the data cache is further divided into two parts, i.e., private data cache and shared data cache. The private data cache is indexed by virtual addresses like the instruction cache, and it is used for caching private data which are referenced from a single processor without sharing. In contrast, the shared data cache is indexed by using physical addresses, and it is used to store data shared by multiple processors. By using physical addresses to access shared data, the cache consistency issue becomes trivial and the synonyms disappear. We use event-driven simulations to demonstrate the advantages of the proposed scheme over a hierarchy of physical addressed caches in the multiprocessor environment.
Third, it may be more efficient to schedule a process on one processor than on another in a multiprogrammed shared memory multiprocessors. By using cache-affinity information in the processor scheduling, the cache performance can be improved, particularly if this information is inexpensive to obtain and exploit. There are a number of cache-affinity scheduling policies for multiprocessors have been proposed. However, most of them do not fully exploit cache-affinity, and several schemes which well consider the cache-affinity are too complex to implement. In order to overcome this limitations, we propose a new virtual cache scheme for exploiting cache-affinity with effect. The key idea of our scheme is to indicate the amount of cache-affinity by referencing scheduling information presented from the OS. Every process has a flag that indicates cache-affinity in its PCB respectively. The OS sets this flag whenever the corresponding process is switched out due to the expiration of time quantum since it means that a large amount of affinity of that process is remained in the cache. When the OS searches a process among candidate processes in the ready queue to assign a processor, the process whose flag is set would be preferentially selected. Since the cache-affinity is more exploited by adopting the affinity flag, the proposed affinity scheduling scheme could effectively reduce cache miss ratios. Moreover, a victim cache line to be replaced is selected by referencing the PIDs of migrated processes or terminated processes, and thus more optimal cache line replacement can be achieved. Trace-driven simulation results show that the new scheme is superior to other compared schemes.
In this thesis, the directions of future work are also discussed, such as more elaborate simulation study and performance evaluation for the proposed schemes with diverse applications, issues to merge the proposed schemes, and issues to extend the proposed schemes to large scale multiprocessors.
캐쉬메모리는 주메모리보다 작은 크기를 갖는 고속의 저장장치에 자주 반복사용하는 데이타를 저장함으로써 메모리 접근지연시간을 줄여준다. 최근 프로세서속도가 향상됨에 따라서, 빠른 프로세서로부터 생성되는 메모리 요구들을 만족 시켜주는 캐쉬 메모리를 설계하는것이 점차 어려워지고 있다. 가상주소를 사용하여 캐쉬를 어드레싱하면 주소변환 시간이 필요없으므로 효과적으로 캐쉬접근시간을 본 논문은 단일프로세서, 다중프로세서와 같은 다양한 시스템구조하에서 메모리 접근시간을 감소시켜주는 가상캐쉬구조들을 제안한다. 이를 위하여, 그와같은 시스템구조하에서 가상캐쉬의 성능에 관련된 설계논점들과 문제점들 깊이있게 연구하고 분석 하였다. 분석한 결과들을 바탕으로하여 성능향상에 장애가 되는 문제점들을 해결할 수 다음과 같은 새로운 가상캐쉬구조들을 제안한다.
첫번째로, 단일프로세서 환경하에서는 빠른 캐쉬접근시간을 갖는 칩내장 직접사상 가상캐쉬가 많이 사용된다. 직접사상캐쉬는 세트내에 캐쉬를 선택하는 시간이 필요없기때문에 세트연관캐쉬보다 적은 캐쉬접근시간을 갖는다. 반면에, 직접사상캐쉬는 동일한 캐쉬라인에 다중주소들이 매핑됨으로써 발생하는 충돌실패들로 인하여 낮은 캐쉬성공률을 나타낸다. 이러한 문제점들을 해결하기 위하여, 우리는 직접사상캐쉬처럼 빠른 캐쉬접근시간과 세트연관캐쉬와 같이 높은 캐쉬성공률을 보이는 새로운 캐쉬구조를 제안한다. 이 구조에서 전체 캐쉬메모리는 n개의 뱅크로 나뉘어지며, 각 프로세스들은 뱅크에 할당된다. 그리고 각 프로세스들은 자신에게 할당된 뱅크상에서 수행된다. 이때 캐쉬는 직접사상캐쉬처럼 동작한다. 캐쉬교체를 위한 희생캐쉬 라인은 가장 늦게 스케쥴될 프로세스에 속한 캐쉬라인들 중에서 선택된다. 트레이스주도 모의실험 결과, 새로 제안된 스킴이 세트연관캐쉬처럼 충돌실패를 감소시켜주면서도 직접사상캐쉬처럼 빠른 캐쉬접근시간을 나타낸다는 것을 알 수 있었다.
두번째로, 2단계 구조를 갖는 캐쉬는 1단계 캐쉬가 빠른 캐쉬접근시간을 제공하고 2단계 캐쉬가 높은 캐쉬 2단계 캐쉬가 높은 캐쉬성공률을 제공하기 때문에 성능이 우수하여, 고성능 다중프로세서 시스템에서 폭넓게 사용되고 있다. 가상캐쉬는 빠른 캐쉬접근시간을 가지기 때문에 1단계 캐쉬로서 적합하다. 그러나 공유메모리 다중프로세서시스템의 캐쉬일관성문제는 가상캐쉬를 사용한 2단계 캐쉬의 설계를 어렵게 한다. 즉 캐쉬일관성 문제로 가상캐쉬가 복잡해지고, 이러한 복잡성으로 인하여 고속 프로세서의 시간적 요구사항을 만족시키기위한 가상캐쉬의 성능이 감소된다. 이와 같은 단점을 해결하기 위하여 우리는 1단계 캐쉬가 가상-실제 칩내장 구조로 구성되어 있는 새로운 다단계 캐쉬구조를 제안한다. 새로운 구조는 다른 캐쉬들과는 달리 가상캐쉬와 실제캐쉬가 1단계캐쉬로서 함께 결합되어 있다. 명령어 캐쉬는 캐쉬내의 데이타에 접근할때 가상주소를 사용한다. 한편, 데이타 캐쉬는 두개의 부분으로 더 다뉘어 진다. 즉 개인전용 데이타캐쉬와 공용데이타캐쉬이다. 개인전용데이타캐쉬는 명령어캐쉬처럼 가상주소를 사용하며, 공유되지 않고 단일프로세서에게만 참조되는 개인전용 데이타만을 저장한다. 반대로 공용데이타캐쉬는 실제주소를 사용하며, 여러 프로세서에 의하여 공유되는 데이타를 저장하는데 사용된다. 이 구조는 공유데이타 접근에 실제주소를 사용함으로써 캐쉬일관성이 용이해지고, synonym은 해결된다. 우리는 다중프로세서 환경에서 실제캐쉬구조에 비하여 새로제안한 스킴이 우수함을 사건주도 모의실험을 이용하여 보였다.
세번째로, 다중프로그래밍 공유메모리다중프로세서 시스템에서 프로세스는 여러 프로세서보다는 한개의 지정된 프로세서에서 수행되는것이 효율적이다. 이처럼 프로세서 스케쥴링시에 캐쉬유사도를 사용한다면 캐쉬성능은 향상될 것이다, 특히 그러한 정보를 용이하게 얻고 활용할수 있다면 더욱 효과적일 것이다. 그동안 다중프로세서 시스템들을 위해 많은 캐쉬유사도 스케쥴링 기법들이 제안되었다. 그렇지만, 그들중 대부분은 캐쉬유사도를 충분히 활용하지 못하고 있으며, 일부는 구현하기에 너무 복잡하다. 이러한 문제점을 해결하기 위하여 캐쉬유사도를 효과적으로 충분히 활용하기 위한 새로운 가상캐쉬구조를 제안한다. 제안한 스킴의 핵심아이디어는 운영체계가 제공하는 스케쥴링 정보를 활용하여 캐쉬유사도의 양을 표시하는 것이다. 모든 프로세스들은 프로세스제어블록내에 캐쉬유사도를 나타낼수 있는 플래그를 갖는다. 운영체계는 이 플래그를 해당프로세스가 주어진 시간단위를 다 사용하여 문맥교환이 일어난 경우에만 세트시킨다. 왜냐하면 그 프로세스는 그만큼 캐쉬내에 많은양의 유사도를 갖고있기 때문이다. 운영체계는 스케쥴시에 준비큐내의 후보프로세스들중에서 플래그가 세트되어있는 프로세스를 우선적으로 수행한다. 이처럼, 캐쉬유사도 플래그를 채택함으로써 캐쉬유사도가 더욱 많이 활용되게 되고, 이에 따라서 새로운 캐쉬유사도 스케쥴링 스킴이 효과적으로 캐쉬실패율을 줄여준다. 또한, 대체될 캐쉬라인들은 종료되었거나 다른 프로세서로 옮겨진 프로세스들의 프로세스식별자를 참조하여 선택되기때문에 보다 최적의 캐쉬라인 대체가 이루어진다. 트레이스주도 모의실험결과는 제안된 스킴이 기존의 스킴들보다 우수함을 보여 주고 있다.
본 논문에서는 보다 정교한 모의실험과 다양한 응용프로그램들을 사용한 성능평가, 제안된 스킴들의 결합에 관련된 논점들, 그리고 제안한 스킴들을 대용량 다중프로세서 시스템에 적용하는데 관련된 논점들과 같이, 향후 연구방향에 대해서도 고찰 하였다.
