RFID 태그 추적을 위한 캐시와 메인 메모리 기반의 색인기법

Abstract

지난 10년간 CPU의 속도는 메모리의 속도에 비해 급속한 속도로 발전하였다. 그 결과 데이타 베이스 시스템을 포함한 다른 컴퓨터 응용분야에서 메모리의 접근이 병목현상을 일으키게 되었다. 메모리의 접근 속도를 줄이기 위해 캐시 메모리가 도입되었다. 하지만 캐시 메모리는 원하는 데이타가 캐시에 옮겨져 있어야 메모리 접근 속도를 줄일 수 있다. 때문에 응용프로그램에서 데이타를 어떤 순서로 액세스 하느냐에 따라 캐시의 활용도가 달라지고 응용프로그램의 성능이 달라지게 된다. 주기억 색인 기법인 Tmr-트리가 R-트리에 비해서 삽입시간이 오래 걸린다는 단점이 있다. 본 논문은 L2 캐시를 최대한 활용하여 기존 Tmr-트리의 장점을 가지는 새로운 CSTmr-트리(Cache Sensitive Tmr-트리)구조를 제안하고, 이 구조에 삽입, 삭제 등의 알고리즘을 제안하였다. 실험을 통해서 CSTmr-트리가 Tmr-트리보다 1.8 ~ 3 배 정도의 성능이 좋은 것을 알 수 있다.

Over about the last 10 years, the speed of CPU has rapidly increased than the speed of the memory. As a result, main-memory access is bottlenecked by many other computer applications, including database systems. To reduce memory access latency, cache memory is incorporated in the memory subsystem, but cache memories can reduce the memory latency only when the requested data is found in the cache. This mainly depends on the memory access pattern of the application. In main memory-based indexing techniques, Tmr-tree compared to R-tree has a defect takes too long to input. We proposed a CSTmr-tree(Cache Sensitive Tmr-tree) structure which we apply L2 cache this is an advantage to the existing Tmr-tree. We also applied the algorithm to like insert and delete at this structure. By simulation, we have known that the time of CSTmr-tree is faster at about 1.8 ～ 3 times more than the normal time of Tmr-tree.