Data-Parallel Algorithms for Efficient Query Processing on Modern Hardware

现代硬件上高效查询处理的数据并行算法

• 批准号: RGPIN-2020-06639
• 负责人: Chester, Sean
• 金额: $ 1.75万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=717860
• 关键词: Data; Parallel; Algorithms; Efficient; Query

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.

联合国强调了可持续发展目标（8.4），即到2030年提高全球资源效率并“使经济增长与环境退化脱钩”。数据分析是这一挑战的典型例子：它是知识经济的推动力，但它也在以指数级增长。我们目前管理指数级增长的能源需求的解决方案是通过将分析转移到超大规模数据中心（如Amazon EC2）来提高效率。然而，根据国际能源署最新的数字化报告，到2020年，这一举措将完成一半（以TWh衡量）;也就是说，这一提高效率的来源将很快耗尽。数据分析迫切需要另一个来源。 今天所有的计算机都很复杂，包括那些形成超大规模云的计算机。然而，充分利用现代计算机是非常困难的：它会自动重新排序计算，同时执行多个指令，并在多个处理器和专用加速器之间协调计算。此外，“现代计算机”是一个移动的目标，因为英特尔，AMD和Nvidia等制造商不知疲倦地创新。因此，毫不奇怪，有一些计算任务-特别是那些涉及高价值文本、时空和社会数据源的任务-浪费了每台计算机内部用于并行计算的大部分机会。 我们需要新颖的算法和数据结构，能够更有效地利用所有复杂的现代计算机，并可以在云中扩展，以便单个分析查询不会扩展到不必要的程度。也许更重要的是，我们需要各种高素质的人才，他们拥有足够先进的技能，将这些想法应用到一个更具资源效率和创新性的加拿大产业中。 具体来说，该研究计划将设计新颖的算法和数据结构，以使现代计算机和专用图形处理单元（GPU）中的额外并行性民主化。我们将为支持自然语言处理（NLP）最新进展的文本创建并行友好的数据结构，以便并行分析和现代NLP可以共同发展。我们将为GPU上的图形处理定义一个更简单的计算范例，使分析师能够从GPU的“延迟隐藏”中受益，同时专注于更高级别的算法概念。我们将为多维数据定义新的以GPU为中心的数据结构，这些数据可以跨服务器扩展，以便传统的数据分析可以更好地利用多级并行性。总而言之，这项研究将拓宽什么类型的数据可以有效利用现代计算平台的范围。因此，科学家和行业专业人士可以更快地产生更多的知识，更多的数据，以更有效的资源利用方式。