Understanding query complexity and its implications for energy-efficient web search
Emily Bragg, Marisabel Guevara, Benjamin C. Lee · 2013
Today’s largest datacenters dissipate megawatts of power. Efficiency is rapidly becoming the primary determinant of datacenter capability. To understand microarchitectural factors that affect efficiency, we must study datacenter workloads. Most studies treat the workload as a large, monolithic piece of software. But a workload is often comprised of many, diverse software tasks. For example, a web search engine executes many individual queries. There is a vast difference between the complexity of searching for a single term and that of searching for a collection of related terms interspersed with Boolean and wildcard operators, which are increasingly common in search engines [1,6]. Methodology. We use Nutch to crawl Wikipedia and gather a set of 50,065 documents across a wide range of topics. We then use Solr and Lucene to search and index text. We implement a query generator that produces queries with a specified number of terms and Boolean operators. The algorithm starts with an initial word and finds other words that commonly occur in its proximity to add a term to the query. Recursively invoking this algorithm produces a query of the desired length. Finally, the algorithm combines multiple query terms using various Boolean operators. We deploy web search in cycle-accurate simulation for a detailed analysis of microarchitectural activity. In contrast, a recent study of search query complexity considers Bing on physical Xeons and Atoms [4]. This study of Bing anonymizes query types whereas we provide transparent insight. We use MARSSx86, a cycle-accurate processor simulator that models x86-64 architectures [3]. McPAT provides power estimates for the processor cores [2]. We link the simulator to DRAMSIM2, which models memory performance and power [5]. We focus on the differences between a variety of in-order (IO) and out-of-order (OOO) cores.