Hardware-aware Optimization of List Intersection in Web Search

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.