Data-Parallel Algorithms for Efficient Query Processing on Modern Hardware

点击翻译按钮获取中文摘要

The United Nations has highlighted a Sustainable Development Goal (8.4) to improve global resource efficiency and "decouple economic growth from environmental degradation" by 2030. Data analytics is a characteristic example of this challenge: it is an impetus of the knowledge economy, but it also is growing at an exponential scale. Our current solution to manage the energy demands of exponential growth is to gain efficiency by moving analytics into hyperscale data centres, like Amazon EC2. However, according to the International Energy Agency's latest digilisation report, this move will be half complete by 2020 (measured in terms of TWh); that is to say, this source for efficiency gains will soon be exhausted. Data analytics imminently needs another source. All computers today are complex, including those that form hyperscale clouds. Fully utilising a modern computer, however, is very difficult: it automatically reorders computations, executes multiple instructions simultaneously, and coordinates computation across multiple processors and specialised accelerators. Furthermore, a "modern computer" is a moving target, as manufacturers such as Intel, AMD, and Nvidia tirelessly innovate. Unsurprisingly, then, there are computational tasks---particularly those involving high-value text, spatio-temporal, and social data sources---that squander most of the opportunities inside each computer for parallel computing. We need novel algorithms and data structures that more efficiently utilise all of a complex, modern computer and can scale in the cloud so that individual analytics queries do not scale out so unnecessarily far. Perhaps even moreso, we need diverse highly qualified personnel with sufficiently advanced skills to apply these ideas to an even more resource-efficient and innovative Canadian industry. Concretely, this research program will design novel algorithms and data structures to democratise access to additional parallelism in modern computers and dedicated graphics processing units (GPUs). We will create parallel-friendly data structures for text that support recent advances in natural language processing (NLP) so that parallel analytics and modern NLP can co-develop. We will define a simpler computational paradigm for graph processing on GPUs that allows analysts to benefit from GPU "latency hiding" while focusing on higher-level algorithmic concepts. And we will define new GPU-centric data structures for multi-dimensional data that scales across servers so that traditional data analytics can better exploit multiple levels of parallelism. In all, this research will broaden the scope of what types of data can effectively leverage modern computing platforms. As a result, scientists and industry professionals alike can generate more knowledge faster, with more data, in a more resource-efficient manner.