캐시 교체 기법 오버헤드 분석 및 구역 사상 교체 기법

유수원,이동희 한국정보과학회 2024 정보과학회논문지 Vol.51 No.10

장치 간에 성능 차이를 보완하기 위하여 캐시가 사용되며, 이를 위한 여러 캐시 교체 기법들이 연구되었다. 이러한 캐시 교체 기법들은 메모리 및 실행 오버헤드를 가지고 있지만, 기법들을 평가할 때 캐시 히트율이 사용되고 교체 기법의 오버헤드는 주목받지 못했다. 최근 컴퓨터 시스템의 캐시 크기는 지속적으로 증가하고 있으며, 이에 따라 오버헤드 역시 커지고 있다. 이러한 추세에 따라 본 논문은 교체 기법의 히트율과 함께 오버헤드에도 주목하여 캐시 교체 기법 평가에 새로운 관점을 제공하는 것을 목표로 한다. 본 논문에서는 먼저 LRU, CLOCK, 2Q, ARC, 그리고 RAND 교체 기법의 메모리 및 실행 오버헤드를 분석한다. 그리고 메모리 및 실행 오버헤드가 작은 구역 사상(RM) 기법을 제시한다. 또한 핫/콜드 데이터를 다르게 취급하는 RM2 기법도 제시한다. 분석 및 실제 시스템에서 측정한 실험 결과에 따르면 RM과 RM2 기법은 오버헤드가 크게 작을 뿐 아니라 최신 기법들과 대등한 성능을 보인다. 또한 메모리 오버헤드가 작은 기법은 주어진 캐시 크기에 더 많은 데이터를 캐싱하여 전체적인 데이터 접근 시간을 감소시킨다. Cache has been widely used to improve performance in systems with fast and slow devices. Various cache replacement policies have been studied, but these policies often come with computation and memory overheads. Unfortunately, many studies do not consider these overheads seriously and instead evaluate cache replacement policies based solely on cache hit rate. However, in modern computer systems, cache sizes are constantly increasing, making these overheads more significant. In order to provide a more comprehensive evaluation of cache replacement policies, we aim to consider both overheads and hit rates. In this study, we analyze the memory and computational overheads of popular cache replacement policies such as LRU, CLOCK, 2Q, ARC, and RAND. Additionally, we propose the Region Mapping (RM) policy, which has low memory and computational overheads. Furthermore, we introduce the RM2 policy, which improves hit rates by separating hot and cold data. Our experimental results show that the hit rates of the RM and RM2 policies are competitive with state-of-the-art policies. Moreover, policies with low memory overheads can reduce overall data access time by caching more data within a given cache size.

라스트 레벨 캐쉬 성능 향상을 위한 캐쉬 교체 기법 연구

두 콩 튜안,김철홍,손동오,김종면 한국정보과학회 2014 정보과학회논문지 Vol.41 No.11

Cache replacement algorithms have been developed in order to reduce miss counts. In modern processors, the performance gap between the processor and main memory has been increasing, creating a more important role for cache replacement policies. The Least Recently Used (LRU) policy is one of the most common policies used in modern processors. However, recent research has shown that the performance gap between the LRU and the theoretical optimal replacement algorithm (OPT) is large. Although LRU replacement has been proven to be adequate over and over again, the OPT/LRU performance gap is continuously widening as the cache associativity becomes large. In this study, we observed that there is a potential chance to improve cache performance based on existing LRU mechanisms. We propose a method that enhances the performance of the LRU replacement algorithm based on the access proportion among the lines in a cache set during a period of two successive replacement actions that make the final replacement action. Our experimental results reveals that the proposed method reduced the average miss rate of the baseline 512KB L2 cache by 15 percent when compared to conventional LRU. In addition, the performance of the processor that applied our proposed cache replacement policy improved by 4.7 percent over LRU, on average. 캐쉬 교체 기법은 캐쉬 미스를 감소시키기 위해서 개발되었다. 마이크로프로세서와 주기억장치의 속도 차이를 해결하기 위해서는 캐쉬 교체 기법의 성능이 중요하다. 일반적인 캐쉬 교체 기법으로는 LRU 기법이 있으며 대부분의 마이크로프로세서에서 캐쉬 교체 기법으로 LRU 기법을 사용한다. 그러나, 최근의 연구에 따르면 LRU 기법과 최적 교체(OPT) 기법 간의 성능 차이는 매우 크다. LRU 기법의 성능은 많은 연구를 통해서 검증되었지만, 캐쉬 사상방식이 높아질수록 LRU 기법과 OPT 기법의 성능 차이는 증가한다. 본 논문에서는 기존의 LRU 기법을 활용하여 캐쉬 성능을 향상시키는 캐쉬 교체 기법을 제안하였다. 제안된 캐쉬 교체 기법은 캐쉬 블록의 접근율에 따라 교체 대상을 선정하여 캐쉬 블록을 교체시킨다. 제안된 캐쉬 교체 기법은 512KB L2 캐쉬에서 기존의 LRU 기법과 비교하여 평균 15%의 미스율을 감소시켰고, 프로세서 성능은 4.7% 향상됨을 알 수 있다.

칩의 크기가 제한된 단일칩 프로세서를 위한 레벨 1 캐시구조

주영관,김석일,Ju YoungKwan,Kim Sukil 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.2

This paper measured a proper ratio of the size of demand fetch cache $L_1$ to that of prefetch cache $L_P$ by imulation when the size of $L_1$ and $L_P$ are constant which organize space-limited level 1 cache of a single microprocessor chip. The analysis of our experiment showed that in the condition of the sum of the size of $L_1$ and $L_P$ are 16 KB, the level 1 cache organization by constituting $L_P$ with 4 KB and employing OBL and FIFO as a prefetch technique and a cache replacement policy respectively resulted in the best performance. Also, this analysis showed that in the condition of the sum of the size of $L_1$ and $L_P$ are over 32 KB, employing dynamic filtering as prefetch technique of $L_P$ are more advantageous and splitting level 1 cache by constituting $L_1$ with 28 KB and $L_P$ with 4 KB in the case of 32 KB of space are available, by constituting $L_1$ with 48 KB and $L_P$ with 16 KB in the case of 64 KB elicited the best performance. 이 논문에서는 단일 칩 프로세서에서 제한된 공간의 레벨 1 캐시를 구성하고 있는 선인출 캐시 $L_P$와 요구인출 캐시 $L_1$의 합이 일정한 때, $L_1$와 $L_P$의 크기의 적정한 비율을 실험을 통하여 분석하였다. 실험 결과, $L_1$와 $L_P$의 합이 16KB일 경우에는 $L_1$을 12KB, $L_P$를 4KB로 구성하고 $L_P$의 선인출 기법과 캐시교체정책은 각각 OBL과 FEO을 적용시키는 레벨 1 캐시 구조가 가장 성능이 우수함을 보였다. 또한 이 분석은 $L_1$와 $L_P$의 합이 32KB 이상인 경우에는 $L_P$의 선인출 기법으로는 동적필터 기법을 사용하는 것이 유리함을 보였고 32KB의 공간이 가용한 경우에는 $L_1$을 28KB, $L_P$를 4KB로, 64KB가 가용한 경우에는 $L_1$을 48KB, $L_P$를 16KB로 레벨 1 캐시를 분할하는 것이 가장 좋은 성능을 발휘함을 보였다.

계층적 캐시 기법을 이용한 대용량 웹 검색 질의 처리 시스템의 구현

임성채(Lim Sung Chae) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.7

웹을 이용한 정보 공개 및 검색이 확대됨에 따라 웹 검색 엔진도 지속적인 주목을 받고 있다. 이에 따라 웹 검색 엔진의 다양한 기술적 문제를 해결하고자 하는 연구가 있었음에도 웹 검색 엔진의 질의 처리 시스템에 대한 기술적 내용은 잘 다뤄지지 않았다. 질의 처리 시스템의 경우 소프트웨어 아키텍처나 운영 기법을 고안하기 어렵기 때문에 본 논문에서는 구현된 상용 시스템을 바탕으로 관련 기술을 소개하고자 한다. 구현된 질의 처리 시스템은 6,500 만개 웹 문서를 색인하여 일 500만개 이상의 사용자 질의 요청을 수행하는 큰 규모의 시스템이다. 구현한 시스템은 질의 처리 결과를 재사용하기 위해 계층적 캐시 기법을 적용했으며, 저장된 캐시 데이타는 4계층으로 구성된 데이타 저장소에 분산 저장되는 것이 특징이다. 계층적 캐시 기법을 통해 질의 처리 용량을 400% 정도로 향상 시킬 수 있었으며 이를 통해 서버 구축 비용을 70% 정도 절감할 수 있었다. With the increasing demands of information sharing and searches via the web, the web search engine has drawn much attention. Although many researches have been done to solve technical challenges to build the web search engine, the issue regarding its query processing system is rarely dealt with. Since the software architecture and operational schemes of the query processing system are hard to elaborate, we here present related techniques implemented on a commercial system. The implemented system is a very large-scale system that can process 5-million user queries per day by using index files built on about 65-million web pages. We implement a multi-level cache scheme to save already returned query results for performance considerations, and the multi-level cache is managed in 4-level cache storage areas. Using the multi-level cache, we can improve the system throughput by a factor of 4, thereby reducing around 70% of the server cost.

가변적인 쓰기 패턴을 위한 적응형 SSD 캐시 기법

조정우(Jungwoo Jo),박성순(Sungsoon Park),원유집(Youjip Won) 한국정보과학회 2019 정보과학회 컴퓨팅의 실제 논문지 Vol.25 No.1

최근 컴퓨터 하드웨어 기술의 고도화로 인해 컴퓨터 처리 속도의 가속화가 진행되고 있다. 컴퓨팅의 가속화로 인해 처리되는 데이터의 크기가 커지는 반면 하드 디스크 처리 속도가 느려 발생하는 I/O 병목현상 문제가 있다. 이러한 병목현상을 줄이기 위해 최근 하드 디스크보다는 빠르고 램 보다는 용량 대비 저렴한 SSD 장치를 캐시로 사용하는 SSD 캐시 기법을 사용하고 있다. 하지만 서버 환경에서 멀티 프로세스들의 다양한 쓰기 패턴과 지속적인 쓰기 처리를 통해 하드 디스크보다 용량이 작은 SSD 캐시는 빠르게 채워지게 된다. 따라서 본 논문에서는 이러한 SSD 캐시가 빠르게 채워져 쓰기 성능이 급격히 감소하는 SSD 캐시 풀 현상을 지연시키기 위해 가변적인 쓰기 패턴을 식별하여 기록하는 적응형 SSD 캐시 기법을 제안한다. Recently, computer processing speed has been accelerating because of the advanced computer hardware technology. As the speed of computing increases, the amount of data to be processed increases. On the other hand, the I/O bottlenecks occur where the hard disk processing speed is slow. To alleviate these bottlenecks, the SSD cache method, which is faster than the hard disk and uses the SSD device that is cheaper than a RAM, was used to solve the problem. However, in the server environment, the SSD cache which is smaller in capacity than the hard disk, was quickly filled with various write patterns and continuous write processing of multiple processes. In this paper, we propose an adaptive SSD cache method that identifies and writes variable write patterns to delay the SSD cache full phenomenon where the SSD cache is rapidly filled and write performance sharply decreases.

RFUSE의 성능 개선을 위한 N-way 스케줄링 기법

김윤수(Yoonsoo Kim),이동영(Dongyeong Lee),강동현(Donghyun Kang) Korean Institute of Information Scientists and Eng 2025 정보과학회 컴퓨팅의 실제 논문지 Vol.31 No.5

RFUSE는 사용자 공간에서 파일시스템을 관리할 수 있도록 지원하는 프레임워크이며, 다중 링 채널을 사용하여 기존 FUSE 보다 우수한 성능을 보장한다. 그러나 RFUSE의 다중 링 채널 분배 기법은 특정 CPU 코어에 작업이 집중되는 경우, 링 채널의 사용이 불균형 하게 이루어져 자원 활용을 제한하는 문제점이 있다. 이에, 본 논문에서는 자원 활용률을 향상시키기 위해, 집합 연관 캐시 기법을 기반으로 작업을 분산하는 새로운 링 채널 분배 기법인 N-way 기법을 제안한다. 제안 기법은 다중 링 채널을 N개의 집합으로 구성하고 집합 내부에서는 라운드-로빈(Round-robin) 방식으로 작업을 할당함으로써, CPU 캐시의 낭비를 줄이고 전체 링 채널을 균등하게 사용할 수 있다. 제안 기법의 성능을 확인하기 위해, Filebench와 YCSB 벤치마크를 사용하여 평가를 진행하였다. 실험 결과, 제안 기법이 기존 RFUSE의 채널 분배 기법보다 최대 25% 향상된 성능을 보여주었다. RFUSE is a framework that supports managing the filesystem in user space. It employs multiple ring channels to guarantee better performance than a traditional FUSE framework. However, RFUSE can cause imbalanced resource utilization when intensive jobs have concentrated on a specific CPU because of the channel distribution policy of RFUSE. In this paper, we proposed a new distribution policy, called N-way, that could improve resource utilization by decreasing conflict with other jobs on CPUs based on the set-associative policy, like the CPU cache mechanism, to address the performance bottleneck issue. Since the proposed policy forms multiple ring channels into sets and assigns each job to one channel in a round-robin manner inside a set, the N-way policy can reduce the waste of CPU cache and ensure suitable scheduling among CPUs. To confirm the performance of the proposed scheduling policy, we evaluated the N-way policy using Filebench and YCSB benchmarks. As a result, the proposed policy showed higher performance than traditional RFUSE policies by up to 25%.

RFUSE의 성능 개선을 위한 N-way 스케줄링 기법

김윤수,이동영,강동현 한국정보과학회 2025 정보과학회 컴퓨팅의 실제 논문지 Vol.31 No.5

RFUSE는 사용자 공간에서 파일시스템을 관리할 수 있도록 지원하는 프레임워크이며, 다중 링 채널을 사용하여 기존 FUSE 보다 우수한 성능을 보장한다. 그러나 RFUSE의 다중 링 채널 분배 기법은 특정 CPU 코어에 작업이 집중되는 경우, 링 채널의 사용이 불균형 하게 이루어져 자원 활용을 제한하는 문제점이 있다. 이에, 본 논문에서는 자원 활용률을 향상시키기 위해, 집합 연관 캐시 기법을 기반으로 작업을 분산하는 새로운 링 채널 분배 기법인 N-way 기법을 제안한다. 제안 기법은 다중 링 채널을 N개의 집합으로 구성하고 집합 내부에서는 라운드-로빈(Round-robin) 방식으로 작업을 할당함으로써, CPU 캐시의 낭비를 줄이고 전체 링 채널을 균등하게 사용할 수 있다. 제안 기법의 성능을 확인하기 위해, Filebench와 YCSB 벤치마크를 사용하여 평가를 진행하였다. 실험 결과, 제안 기법이 기존 RFUSE의 채널 분배 기법보다 최대 25% 향상된 성능을 보여주었다. RFUSE is a framework that supports managing the filesystem in user space. It employs multiple ring channels to guarantee better performance than a traditional FUSE framework. However, RFUSE can cause imbalanced resource utilization when intensive jobs have concentrated on a specific CPU because of the channel distribution policy of RFUSE. In this paper, we proposed a new distribution policy, called N-way, that could improve resource utilization by decreasing conflict with other jobs on CPUs based on the set-associative policy, like the CPU cache mechanism, to address the performance bottleneck issue. Since the proposed policy forms multiple ring channels into sets and assigns each job to one channel in a round-robin manner inside a set, the N-way policy can reduce the waste of CPU cache and ensure suitable scheduling among CPUs. To confirm the performance of the proposed scheduling policy, we evaluated the N-way policy using Filebench and YCSB benchmarks. As a result, the proposed policy showed higher performance than traditional RFUSE policies by up to 25%.

하이브리드 메인 메모리의 성능 향상을 위한 페이지 교체 기법

이민호(Minhoe Lee),강동현(Dong Hyun Kang),김정훈(Junghoon Kim),엄영익(Young Ik Eom) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.1

DRAM은 빠른 쓰기/읽기 속도와 무한한 쓰기 횟수로 인해 컴퓨터 시스템에서 주로 메인 메모리로 사용되지만 저장된 데이터를 유지하기 위해 지속적인 전원공급이 필요하다. 반면, PCM은 비휘발성 메모리로 전원공급 없이 저장된 데이터를 유지할 수 있으며 DRAM과 같이 바이트 단위의 접근과 덮어쓰기가 가능하다는 점에서 DRAM을 대체할 수 있는 메모리로 주목받고 있다. 하지만 PCM은 느린 쓰기/읽기 속도와 제한된 쓰기 횟수로 인해 메인 메모리로 사용되기 어렵다. 이런 이유로 DRAM과 PCM의 장점을 모두 활용하기 위한 하이브리드 메인 메모리가 제안되었고 이에 대한 연구가 활발하다. 본 논문에서는 DRAM과 PCM으로 구성된 하이브리드 메인 메모리를 위한 새로운 페이지 교체 기법을 제안한다. PCM의 단점을 보완하기 위해 제안 기법은 PCM 쓰기 횟수를 줄이는 것을 목표로 하며 실험결과에서 알 수 있듯이 본 논문의 제안 기법은 다른 페이지 교체 기법에 비해 PCM 쓰기 횟수를 80.5% 줄인다. In modern computer systems, DRAM is commonly used as main memory due to its low read/write latency and high endurance. However, DRAM is volatile memory that requires periodic power supply (i.e., memory refresh) to sustain the data stored in it. On the other hand, PCM is a promising candidate for replacement of DRAM because it is non-volatile memory, which could sustain the stored data without memory refresh. PCM is also available for byte-addressable access and in-place update. However, PCM is unsuitable for using main memory of a computer system because it has two limitations: high read/write latency and low endurance. To take the advantage of both DRAM and PCM, a hybrid main memory, which consists of DRAM and PCM, has been suggested and actively studied. In this paper, we propose a novel page replacement algorithm for hybrid main memory. To cope with the weaknesses of PCM, our scheme focuses on reducing the number of PCM writes in the hybrid main memory. Experimental results shows that our proposed page replacement algorithm reduces the number of PCM writes by up to 80.5% compared with the other page replacement algorithms.

aRFS+: 높은 네트워크 성능을 위한 새로운 플로우 스티어링 기법

박재현,황재현 한국정보과학회 2024 정보과학회논문지 Vol.51 No.5

최근의 데이터센터 서버에서는 네트워크 처리 오버헤드를 줄이기 위해 다이렉트 캐시 액세스 (DCA) 기법이 사용되고 있다. 그러나 기존의 플로우 스티어링 기법들이 DCA나 멀티코어 환경을 고려하지 않아 네트워크 응용의 최적 성능을 달성하지 못한다. 본 논문에서는 aRFS+ 라는 새로운 플로우 스티어링 기법을 제안하며, 다음의 세 가지 설계사항을 고려하였다. 첫째, 네트워크 응용에 대해 DCA가 적용되는 NUMA 노드의 CPU 코어에서 동작되도록 하는 애플리케이션 스티어링 기법을 적용하였다. 둘째, 멀티코어 환경의 이점을 극대화하기 위해 네트워크 패킷 수신처리를 위한 코어와 응용 코어가 분리되도록 하였다. 더불어 두 코어가 같은 DCA 적용 NUMA 노드 코어에서 선택되도록 하여 높은 CPU 효율을 달성하도록 하였다. 셋째, 매 패킷에 대한 메모리 관리 오버헤드를 줄이는 최적화 기법을 도입하였다. 이를 통해 기존 기법 대비 최대 약 60%의 성능 향상을 보임을 확인하였다. Recent studies indicate that a significant portion of central processing unit (CPU) usage in network stack processing is attributed to the transfer of data between kernel and user spaces. Direct Cache Access (DCA) has been recognized to enhance data copy efficiency by allowing applications to perform data copy operations utilizing L3 caches. However, current flow steering mechanisms lack awareness of caches; they often employ random selection methods or allocate processing tasks to cores based on the location of corresponding applications subsequently resulting in suboptimal throughput. To address this issue, in this paper, we propose a novel flow steering scheme named aRFS+. The three key ideas of aRFS+ are as follows. First, we dynamically allocated network applications to the DCA-capable NUMA node, enabling them to exploit DCA advantages during data copy operations. Second, we decouple application cores from network processing cores to maximize the benefits of multicore environments. Incoming packets are steered to a CPU distinct from the application core but situated within the same NUMA node. Third, we introduce an optimization technique that significantly mitigates the overhead associated with memory management. Our experimental evaluations demonstrated that aRFS+ substantially improved the overall throughput, with an enhancement of up to 60% compared to existing schemes.

메인 메모리 다차원 인덱스를 위한 효율적인 MBR 압축 기법

김정준,강홍구,김동오,한기준,Kim, Joung-Joon,Kang, Hong-Koo,Kim, Dong-Oh,Han, Ki-Joon 한국공간정보학회 2007 한국공간정보시스템학회 논문지 Vol.9 No.2

최근 실시간 서비스의 요구 사항을 갖는 위치 기반 서비스와 텔레매틱스 서비스를 효율적으로 제공하기 위해서 공간 메인 메모리 DBMS에 대한 관심이 급증하고 있다. 이러한 공간 메인 메모리 DBMS에서 기존의 디스크 기반 다차원 인덱스들을 메인 메모리에 최적화하기 위해 엔트리 크기를 줄여 캐시 접근 실패를 최소화한 다차원 인덱스 구조들이 제안되고 있다. 그러나 엔트리 크기를 줄이기 위하여 부모 노드의 MBR을 기준으로 압축하거나 중복된 MBR을 제거하기 때문에 인덱스 갱신 시 MBR 재구성 비용이 증가하고 인덱스 검색 시 효율이 떨어지는 문제점이 있다. 본 논문에서는 MBR 재구성 비용을 줄이기 위하여 넓은 분포의 경우와 좁은 분포의 경우로 나누어 압축 기준점을 다르게 적용하는 RSMBR(Relative-Sized MBR) 압축 기법을 제시하였다. RSMBR 압축 기법은 넓은 분포일 경우 부모 노드 확장 MBR의 좌하점을 기준으로 압축하고, 좁은 분포일 경우 전체 MBR을 일정 크기의 셀로 나누고 각 셀의 좌하점을 기준으로 압축한다. 또한 인덱스 검색 시 검색 비용을 줄이기 위하여 상대 좌표와 크기를 이용하여 MBR을 압축한다. 마지막으로, 본 논문에서는 실제 데이타를 통한 성능 평가를 수행하여 RSMBR 압축 기법의 우수성도 입증하였다. Recently there is growing Interest in LBS(Location Based Service) requiring real-time services and the spatial main memory DBMS for efficient Telematics services. In order to optimize existing disk-based multi-dimensional Indexes of the spatial main memory DBMS in the main memory, multi-dimensional index structures have been proposed, which minimize failures in cache access by reducing the entry size. However, because the reduction of entry size requires compression based on the MBR of the parent node or the removal of redundant MBR, the cost of MBR reconstruction increases in index update and the efficiency of search is lowered in index search. Thus, to reduce the cost of MBR reconstruction, this paper proposed the RSMBR(Relative-Sized MBR) compression technique, which applies the base point of compression differently in case of broad distribution and narrow distribution. In case of broad distribution, compression is made based on the left-bottom point of the extended MBR of the parent node, and in case of narrow distribution, the whole MBR is divided into cells of the same size and compression is made based on the left-bottom point of each cell. In addition, MBR was compressed using a relative coordinate and size to reduce the cost of search in index search. Lastly, we evaluated the performance of the proposed RSMBR compression technique using real data, and proved its superiority.