오토마타 기반 XML 스트림 필터링 시스템에서의 캐시-친화형 질의 인덱스 (A Cache-conscious Query Index for Automata-based XML Stream Filtering Systems)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 20권 / 1호 / 46 ~ 50페이지
· 저자명 : 최대한, 이경하, 김수형, 이윤준

초록

오토마타 기반 XML 스트림 필터링 시스템에서 질의 처리는 인 메모리 기반으로 수행된다. 이에 따라, 캐싱이 필터링 시스템의 전체 성능을 결정하는 주요 요인이 된다. 하지만, 해시 테이블로 구현되는 오토마타라는 질의 인덱스 특성상 인덱스에 대한 접근 패턴은 메모리 내의 임의 접근이 될 수 밖에 없으며 그로 인해 많은 캐시 미스를 유발한다. 이 논문에서는 XML 스트림 필터링 과정에 있어 캐시 히트율을 높이는 것을 목적으로 한다. 이를 위해 높은 적재율과 상수 탐색 시간을 보장할 수 있도록 Splash 해시테이블과 SIMD 명령어에 의한 탐색 병렬화 기법을 적용하였다. 또한 질의 인덱스에서 빈번하게 자주 접근되는 일련의 상태 전이들을 찾아 해시테이블 내에 같은 버켓에 저장함으로써 보다 캐시 히트율을 높이는 방안을 고안하였다.

영어초록

The automata-based XML stream filtration has achieved recognition as an efficient solution for processing many queries over XML streaming data simultaneously. However, the current implementations of the automata-style query indexes, i.e. hash tables, have been reported to involve frequent random memory accesses, causing many cache misses. We focus on improving the hash tables for the automata-based XML stream filtration in this paper. We first adopt the Splash hash table which guarantees the high load factor and the constant lookup time. We also provide two optimization techniques that further improve the overall throughput of the XML stream filtration: 1) SIMD CPU commands for parallelizing hash lookups and 2) identifying and grouping the state transitions which frequently occur together into the same bucket.

참고자료

· 없음