Hardware-aware Optimization of List Intersection in Web Search
- Title
- Hardware-aware Optimization of List Intersection in Web Search
- Authors
- 김성환
- Date Issued
- 2020
- Publisher
- 포항공과대학교
- Abstract
- This dissertation studies the optimization of list intersection, as a fundamental building block of search engine.
Though modern architectures contribute to expedite predictable data accesses, by using caching, hardware prefetching and vectorization, accelerating list intersection is impaired by non-contiguous memory accesses and control-flow divergence, which we name as two bottlenecks for list intersection - memory latency and branch misprediction penalty respectively.
To overcome this phenomenon, dissertation proposes the following two contributions.
First, we identify the magnitude of impacts for the two bottlenecks on the execution of state-of-the-art list intersection algorithms, then propose a cost-based optimization methodology by generating a cost model of a state-of-the-art algorithm with very high accuracy.
Second, we propose new data structures and algorithms that break the identified bottlenecks.
The proposed data structure improves cache efficiency by replacing several random accesses with sequential scan, and each proposed algorithm offers various parallel optimization methods such as branchless computation, software pipelining, and software prefetching.
- URI
- http://postech.dcollection.net/common/orgView/200000336011
https://oasis.postech.ac.kr/handle/2014.oak/111133
- Article Type
- Thesis
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.